《第1學(xué)期《操作系統(tǒng)原理》期中試卷(答案)》由會員分享，可在線閱讀，更多相關(guān)《第1學(xué)期《操作系統(tǒng)原理》期中試卷(答案)（6頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、
2012-2013 學(xué)年第 1 學(xué)期《操作系統(tǒng)原理》期中試卷（答案）
一、選擇題（本題共
10 小題，每題
2 分，滿分
20 分）
1、 C
2 、 D 3 、D 4 、 B 5 、 D 6 、 D 7 、 D 8 、 C 9 、 B 10 、 B
二、計算題（本題共
3 小題，每題
20 分，滿分
60 分）
1、答：畫出三個作業(yè)并行工作圖如下
( 圖中著色部分為作業(yè)等待時間
) ：
CPU
2、
Job3
Job2
Job1
Job2
Job3
Job1
Job3
I1
Job2
Job1
Job3
Job3
I2
Job1
Job2
Job1
Job1
I2
CPU
I1
CPU
I2
Job2
I1
CPU
CPU
I2
Job3
CPU
CPU
3、
I1
CPU
I1
時間
(ms)
0
10 20 30
40 50 60 70
80 90 100
110
(1) Job1 從投入到運行完成需 110ms，Job2 從投入到運行完成需
運行完成需 110ms。
90ms， Job3 從投入到
(2) CPU 空閑時間段為： 60ms 至 70ms， 80ms 至 90ms，100ms 至 110ms。所以 CPU 利用率為 (110-30)/110=72.7% 。
(3) 設(shè)備
4、I1 空閑時間段為： 20ms 至 40ms， 90ms 至 100ms，故 I1 的利用率為
(110-30)/110=72.7% 。設(shè)備 I2 空閑時間段為： 30ms 至 50ms，故 I2 的利用率為
(110-20)/110=81.8%.
2、（1） SJF（ 10 分）
1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12)
A
D
B
C
高響應(yīng)比優(yōu)先： （ 10
分）
1
2
3
4
5
6
7
8
5、9
1
1
1
0
1
2
A
B
D
C
（ 2） SJF平均周轉(zhuǎn)時間為 25/4=6.25；高響應(yīng)比優(yōu)先： 26/4=6.5。
3、下表給出了四個進程需要的資源以及已申請到的資源信息
（資源為
R1）。試 用銀行家 算
法判斷此時系統(tǒng)至少需要多少資源才能保證系統(tǒng)的安全？為什么？
進程
已分配資源
最大資源需求
R1
R1
P1
1
3
P2
1
2
P3
3
9
P4
2
7
6、
答案：最少需要
3 個資源。當給定
3 個資源時，進程執(zhí)行安全序列和
work
向量變化如下：
work=3 → P2 work=4 → P1 work=5 → P4 work=7
源，則系統(tǒng)在執(zhí)行安全性算法如下步驟后處于死鎖狀態(tài)：
work=4 。因此，系統(tǒng)至少需要 3 個資源。
→
P3 work=10
work=2 →
。如果系統(tǒng)僅有
P2 wor
7、k=3 →
2 個資
P1
三、綜合題（ 本題滿分 60 分，每題 15 分）
1、有兩個協(xié)作進程 p_input() 和 p_comput() 分別完成數(shù)據(jù)的輸入與處理工作。試給出這兩
個進程的制約關(guān)系，并用 WAIT,SIGNAL操作寫出進程的同步算法。
答案： var mutex, empty, full semaphore:=1,1,0;
begin
parbegin
p_input: begin
repeat
wait(empty);
wait(mutex);
input data;
8、signal(mutex);
signal(full);
until false;
end
p_comput: begin
repeat
wait(full);
wait(mutex);
compute data;
signal(mutex);
signal(empty);
until false;
end
parend
end
2. 一座小橋 (最多只能承重兩個人 )橫跨南北兩岸，任意時刻同一方向只允許一人過橋，南
側(cè)橋段和北側(cè)橋段較窄只能通過一人， 橋中央一處寬敞， 允許兩個人通過或歇息。
9、試用
信號燈和 PV 操作寫出南、北兩岸過橋的同步算法。
答案：共需要三個信號量， num 用來控制橋上人數(shù)，初值為 2，表示橋上最多有 2 人； north
用來控制北段橋的使用，初值為 1，用于對北段橋互斥； south 用來控制南段橋的使用，初
值為 1，用于對南段橋互斥。
var num, north, south semaphore:=2,1,1;
begin
parbegin
go_north:begin
repeat
wait(num);
wait(south);
通過橋南側(cè)；
到達橋
10、中間；
signal(south);
wait(north);
通過橋北側(cè)；
signal(north);
signal(num);
until false;
end
go_south:begin
repeat
wait(num);
wait(north);
通過橋北側(cè)；
到達橋中間；
signal(north);
wait(south);
通過橋南側(cè)；
signal(south);
signal(num);
until false;
end
parend
end
11、
3. 某系統(tǒng)有 R1， R2，R3 三種資源，在 T0 時刻 P1， P2， P3， P4 四個進程對資源的占用和
需求情況如表 1 所示，此刻系統(tǒng)的可用資源向量為（2, 1, 2
），問題：
① 將系統(tǒng)中各種資源總數(shù)和此刻各進程對各資源的需求數(shù)目用向量或矩陣表示出來；
② 如果此時
P1 和 P2 均發(fā)出資源請求向量
Request （ 1, 0, 1
），為了保持系統(tǒng)安全性，
應(yīng)該如何分配資源給這兩個進程？說明你所采用策略的原因；
③ 如果②中兩個請求立刻得到滿足后，系統(tǒng)此刻是否處于死鎖狀態(tài)？
表 1
T0
12、 時刻 P1， P2， P3， P4 四個進程對資源的占用和需求情況表
Maximum demand
Current allocation
R1
R2
R3
R1
R2
R3
P1
3
2
2
1
0
0
P2
6
1
3
4
1
1
P3
3
1
4
2
1
1
P4
4
2
2
0
0
2
答案：
(1)Available=(2,1,2) ，資源總數(shù)為 (9, 3, 6) ，Need= 2
2
2
2
0
2
1
0
3
4
2
0
(
13、2) 如果分配資源給
P1，則 Need=1 2 1
Available=(1,1,1) ，死鎖。
2 0 2
1 0 3
4 2 0
應(yīng)該分配給 P2 ，分配之后是安全的。安全的分配資源順序和
work=(6,2,3) → P3 work=(8,3,4) → P4 work=(8,3,6) →
（3）立即處于死鎖狀態(tài)。
work 向量變化如下：
P1 work=(9,3,6) 。
P2
4、 分析下面用信號量解決哲學(xué)家進餐問題的同步算法是否滿足同步機制的四條準則。
若不
滿足，說
14、明為什么，并給出滿足同步機制四條準則的同步算法。
解法 I （ 1）var fork ：array[0..4] of semaphore;
fork[0] := fork[1] := fork[2] := fork[3] := fork[4] := 1;
begin
parbegin
Pi :begin
repeat /* 第 i 個哲學(xué)家的生活過程
ThinkForWhile;
*/
P(fork[i]);
P(fork[(i+1) mod 5]);
EatForW
15、hile;
V(fork[i]);
V(fork[(i+1) mod 5]);
until false;
end
parend
end
答案：不滿足“有限等待”準則，當每個哲學(xué)家都只拿到一把叉子時，發(fā)生死鎖。改進的算法很多，可以選擇不允許多個哲學(xué)家同時拿筷子來解決，其算法如下：
解法 I ： var fork ： array[0..4] of semaphore;
var mutex:semaphore;
fork[0] := fork[1] := fork[2] := fork[3] := fork[4] := 1;mutex :=1;
begin
parbegin
Pi : repeat // 第 i 個哲學(xué)家的生活過程
ThinkForWhile;
P(mutex); //解法 2 設(shè) mutex 的初值 =4
P(fork[i]);
P(fork[(i+1) mod 5]);
V(mutex);
EatForWhile;
V(fork[i]);
V(fork[(i+1) mod 5]);
until false;
parend
end //解法 3 用信號量集
第1學(xué)期《操作系統(tǒng)原理》期中試卷(答案)
