2．某虛擬存儲器的用戶編程空間共32個頁面，每頁為1KB，內存為16KB。假定某時刻一用戶頁表中已調入內存的頁面的頁號和物理塊號的對照表如下：

頁號

物理塊號

0

3

1

7

2

11

3

8

則邏輯地址0A5C(H)所對應的物理地址是什么？要求：寫出主要計算過程。

3．對于如下的頁面訪問序列：

1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 5

當內存塊數量分別為3和4時，試問：使用FIFO、LRU置換算法產生的缺頁中斷是多少？（所有內存開始時都是空的，凡**次用到的頁面都產生一次缺頁中斷）

4. 在某個計算機系統中，磁頭當前在15柱面，移臂方向為從小到大。磁盤訪問請求序列為：15、20、9、16、24、13、29。請給出最短尋道時間優先算法和電梯調度算法的柱面移動數。（要求寫出簡單的計算過程）

5.一個進程被分配了4個頁幀。下表列出了各頁的虛擬頁號，各頁被裝入頁幀的時間，各頁最近被訪問的時間，以及各頁的引用位和修改位（時間從進程啟動時開始計算）。

虛擬頁號

頁幀號

裝入時間

引用時間

引用位

修改位

2

1

60

161

0

1

1

2

130

160

0

0

0

3

26

162

1

0

3

4

20

163

1

1

①假如發生一個訪問頁號為4的頁面缺頁中斷，試分別使用FIFO、LRU和NUR算法選擇淘汰頁面。

②對于下面的內存訪問序列：4,0,0,0,2,4,2,1,0,3,2，如果使用窗口大小為4 的工作集方法來取代固定分配頁幀的方法，則會出現多少次缺頁中斷？

6.假定把如表所示的4個作業同時提交給系統并進入后備隊列，若使用最短作業優先調度算法，則作業的平均等待時間是多少？若使用最高優先數隊列的調度算法，則作業的平均周轉時間是多少？

作業

所需運行時間/小時

優先數

1

2

4

2

5

9

3

8

2

4

3

8

7. 有5個任務A、B、C、D、E，它們的到達時間依次是1、3、4、5、7，預計它們的運行時間為8、6、3、5、10(min)。其優先級分別為3、5、2、4、1，這里5為最高優先級。對于下列每一種調度算法，計算其平均周轉時間。（要求寫出簡單的計算過程）

（1）先來先服務算法。

（2）搶占式的優先級調度算法。

2．

(1) 非搶占式優先級算法

作業1 作業3 作業2

(2)

作業

到達時間

運行時間

完成時間

周轉時間

帶權周轉時間

1

0

10

10

10

1.0

2

1

4

17

16

4.0

3

2

3

13

11

3.7

平均周轉時間

12.3

平均帶權周轉時間

2.9

3．125C（H） （要求寫出計算步驟）

[分析]：頁式存儲管理的邏輯地址分為兩部分：頁號和頁內地址。

由已知條件“用戶編程空間共32個頁面”，可知頁號部分占5位；由“每頁為1KB”，1K=210，可知內頁地址占10位。由“內存為16KB”，可知有16塊，塊號為4位。

邏輯地址0A5C（H）所對應的二進制表示形式是：000 1010 0101 1100 ，根據上面的分析，下劃線部分為頁內地址，編碼 “000 10” 為頁號，表示該邏輯地址對應的頁號為2。查頁表，得到物理塊號是4（十進制），即物理塊地址為：01 00 ，拼接塊內地址10 0101 1100，得01 0010 0101 1100，即125C（H）。

4．

FIFO淘汰算法：

內存塊為3時，缺頁中斷（或稱缺頁次數、頁面故障）為9；

內存塊為4時，缺頁中斷為10。

LRU淘汰算法：

內存塊為3時，缺頁中斷為10；

內存塊為4時，缺頁中斷為8。

（具體計算過程省略，解答時請同學們寫出計算過程。）

5.

按照最短尋道時間優先算法，柱面的訪問次序是：15、16、13、9、20、24、29，所以最短尋道時間優先算法的柱面移動數為：1+3+4+11+4+5=28；

按照電梯調度算法，柱面的訪問次序是：15、16、20、24、29、13、9，所以電梯調度算法的柱面移動數為：1+4+4+5+16+4=34。

6.

（1）若使用FIFO方法選擇淘汰頁面，則應為裝入時間最早的頁面，即第3頁。若使用LRU方法選擇淘汰頁面，則應為最近訪問時間最早的頁面，即第1頁。若使用NUR方法選擇淘汰頁面，則應選擇未引用且未修改的頁面。從表中可看出，在時刻161系統將修改位全部清0，這里應選擇引用位和修改位均為0的頁面，即第1頁。

（2）使用工作集方法的運行情況如表所示。從表中可以看出，總共會產生5次缺頁中斷。

訪問頁面

當前工作集

是否產生缺頁中斷

4

{1,2,0,3}

是

0

{2,0,3,4}

否

0

{0,3,4}

否

0

{0,3,4}

否

2

{0,3,4,2}

是

4

{0,3,4,2}

否

2

{0,3,4,2}

否

1

{3,4,2,1}

是

0

{4,2,1,0}

是

3

{2,1,0,3}

是

2

{2,1,0,3}

否

7.

對給定的4個作業，當采用最短作業優先調度算法時，作業的執行次序是1,4,2,3，它們的等待時間分別為0,2,5,10。所以，作業平均等待時間是

(2+5+10)h/4=4.25h

若用最高優先數隊列的調度算法，則作業的執行次序是2,4,1,3，其周轉時間分別為5,8,10,18。因此，作業的平均周轉時間是

(5+8+10+18)h/4=10.25h

8.

（1）采用先來先服務調度算法時，5個任務在系統中完成時間及周轉時間如表所示。

作業

到達時間

運行時間

開始時間

完成時間

周轉時間

A

1

8

1

9

8

B

3

6

9

15

12

C

4

3

15

18

14

D

5

5

18

23

18

E

7

10

23

33

26

根據表中的計算結果，5個進程的平均周轉時間為：

(8+12+14+18+26)/5=15.6min

（2）采用高優先級調度算法時，5個任務在系統中的完成時間及周轉時間如表所示。

作業

到達時間

運行時間

優先級

開始時間

完成時間

周轉時間

A

1

8

3

1

20

19

B

3

6

5

3

9

6

C

4

3

2

20

23

19

D

5

5

4

9

14

9

E

7

10

1

23

33

26

它們的平均周轉時間為：

(19+6+19+9+26)/5=15.8min。