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

頁號

物理塊號

0

3

1

7

2

11

3

8

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

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

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

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

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

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

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

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

6.假定把如表所示的4個作業(yè)同時提交給系統(tǒng)并進入后備隊列，若使用最短作業(yè)優(yōu)先調(diào)度算法，則作業(yè)的平均等待時間是多少？若使用最高優(yōu)先數(shù)隊列的調(diào)度算法，則作業(yè)的平均周轉(zhuǎn)時間是多少？

作業(yè)

所需運行時間/小時

優(yōu)先數(shù)

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)。其優(yōu)先級分別為3、5、2、4、1，這里5為最高優(yōu)先級。對于下列每一種調(diào)度算法，計算其平均周轉(zhuǎn)時間。（要求寫出簡單的計算過程）

（1）先來先服務算法。

（2）搶占式的優(yōu)先級調(diào)度算法。

2．

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

作業(yè)1 作業(yè)3 作業(yè)2

(2)

作業(yè)

到達時間

運行時間

完成時間

周轉(zhuǎn)時間

帶權(quán)周轉(zhuǎn)時間

1

0

10

10

10

1.0

2

1

4

17

16

4.0

3

2

3

13

11

3.7

平均周轉(zhuǎn)時間

12.3

平均帶權(quán)周轉(zhuǎn)時間

2.9

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

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

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

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

4．

FIFO淘汰算法：

內(nèi)存塊為3時，缺頁中斷（或稱缺頁次數(shù)、頁面故障）為9；

內(nèi)存塊為4時，缺頁中斷為10。

LRU淘汰算法：

內(nèi)存塊為3時，缺頁中斷為10；

內(nèi)存塊為4時，缺頁中斷為8。

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

5.

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

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

6.

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

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

訪問頁面

當前工作集

是否產(chǎn)生缺頁中斷

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個作業(yè)，當采用最短作業(yè)優(yōu)先調(diào)度算法時，作業(yè)的執(zhí)行次序是1,4,2,3，它們的等待時間分別為0,2,5,10。所以，作業(yè)平均等待時間是

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

若用最高優(yōu)先數(shù)隊列的調(diào)度算法，則作業(yè)的執(zhí)行次序是2,4,1,3，其周轉(zhuǎn)時間分別為5,8,10,18。因此，作業(yè)的平均周轉(zhuǎn)時間是

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

8.

（1）采用先來先服務調(diào)度算法時，5個任務在系統(tǒng)中完成時間及周轉(zhuǎn)時間如表所示。

作業(yè)

到達時間

運行時間

開始時間

完成時間

周轉(zhuǎn)時間

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

根據(jù)表中的計算結(jié)果，5個進程的平均周轉(zhuǎn)時間為：

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

（2）采用高優(yōu)先級調(diào)度算法時，5個任務在系統(tǒng)中的完成時間及周轉(zhuǎn)時間如表所示。

作業(yè)

到達時間

運行時間

優(yōu)先級

開始時間

完成時間

周轉(zhuǎn)時間

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

它們的平均周轉(zhuǎn)時間為：

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