2012-2013学年第1学期《操作系统原理》期中试卷(答案)

2012-2013学年第1学期《操作系统原理》期中试卷（答案）一、选择题（本题共10小题，每题2分，满分20分）1、C2、D3、D4、B5、D6、D7、D8、C9、B10、B二、计算题（本题共3小题，每题20分，满分60分）1、答：画出三个作业并行工作图如下(图中着色部分为作业等待时间)：(1)Job1从投入到运行完成需110ms，Job2从投入到运行完成需90ms，Job3从投入到运行完成需110ms。(2)CPU空闲时间段为：60ms至70ms，80ms至90ms，100ms至110ms。所以CPU利用率为(110-30)/110=72.7%。(3)设备I1空闲时间段为：20ms至40ms，90ms至100ms，故I1的利用率为(110-30)/110=72.7%。设备I2空闲时间段为：30ms至50ms，故I2的利用率为(110-20)/110=81.8%.2、（1）SJF（10分）1)2)3)4)5)6)7)8)9)10)11)1112)ADBC高响应比优先：（10分）123456789101112ABDC（2）SJF平均周转时间为25/4=6.25；高响应比优先：26/4=6.5。3、下表给出了四个进程需要的资源以及已申请到的资源信息（资源为R1）。试用银行家算法判断此时系统至少需要多少资源才能保证系统的安全？为什么？进程已分配资源最大资源需求R1R1P113P212P339P427CPUI1I2Job1Job2Job3时间(ms)CPUCPU0102030405060708090100110CPUI1I1I1CPUCPUI2I2CPUI1CPUI2Job1Job2Job3Job2Job1Job2Job3Job1Job3Job2Job1Job1Job3Job3答案：最少需要3个资源。当给定3个资源时，进程执行安全序列和work向量变化如下：work=3→P2work=4→P1work=5→P4work=7→P3work=10。如果系统仅有2个资源，则系统在执行安全性算法如下步骤后处于死锁状态：work=2→P2work=3→P1work=4。因此，系统至少需要3个资源。三、综合题（本题满分60分，每题15分）1、有两个协作进程p_input()和p_comput()分别完成数据的输入与处理工作。试给出这两个进程的制约关系，并用WAIT,SIGNAL操作写出进程的同步算法。答案：varmutex,empty,fullsemaphore:=1,1,0;beginparbeginp_input:beginrepeatwait(empty);wait(mutex);inputdata;signal(mutex);signal(full);untilfalse;endp_comput:beginrepeatwait(full);wait(mutex);computedata;signal(mutex);signal(empty);untilfalse;endparendend2.一座小桥(最多只能承重两个人)横跨南北两岸，任意时刻同一方向只允许一人过桥，南侧桥段和北侧桥段较窄只能通过一人，桥中央一处宽敞，允许两个人通过或歇息。试用信号灯和PV操作写出南、北两岸过桥的同步算法。答案：共需要三个信号量，num用来控制桥上人数，初值为2，表示桥上最多有2人；north用来控制北段桥的使用，初值为1，用于对北段桥互斥；south用来控制南段桥的使用，初值为1，用于对南段桥互斥。varnum,north,southsemaphore:=2,1,1;beginparbegingo_north:beginrepeatwait(num);wait(south);通过桥南侧；到达桥中间；signal(south);wait(north);通过桥北侧；signal(north);signal(num);untilfalse;endgo_south:beginrepeatwait(num);wait(north);通过桥北侧；到达桥中间；signal(north);wait(south);通过桥南侧；signal(south);signal(num);untilfalse;endparendend3.某系统有R1，R2，R3三种资源，在T0时刻P1，P2，P3，P4四个进程对资源的占用和需求情况如表1所示，此刻系统的可用资源向量为（2,1,2），问题：①将系统中各种资源总数和此刻各进程对各资源的需求数目用向量或矩阵表示出来；②如果此时P1和P2均发出资源请求向量Request（1,0,1），为了保持系统安全性，应该如何分配资源给这两个进程？说明你所采用策略的原因；③如果②中两个请求立刻得到满足后，系统此刻是否处于死锁状态？表1T0时刻P1，P2，P3，P4四个进程对资源的占用和需求情况表MaximumdemandCurrentallocationR1R2R3R1R2R3P1322100P2613411P3314211P4422002答案：(1)Available=(2,1,2)，资源总数为(9,3,6)，Need=222202103420(2)如果分配资源给P1，则Need=121Available=(1,1,1)，死锁。202103420应该分配给P2，分配之后是安全的。安全的分配资源顺序和work向量变化如下：P2work=(6,2,3)→P3work=(8,3,4)→P4work=(8,3,6)→P1work=(9,3,6)。（3）立即处于死锁状态。4、分析下面用信号量解决哲学家进餐问题的同步算法是否满足同步机制的四条准则。若不满足，说明为什么，并给出满足同步机制四条准则的同步算法。解法I（1）varfork：array[0..4]ofsemaphore;fork[0]:=fork[1]:=fork[2]:=fork[3]:=fork[4]:=1;beginparbeginPi:beginrepeat/*第i个哲学家的生活过程*/ThinkForWhile;P(fork[i]);P(fork[(i+1)mod5]);EatForWhile;V(fork[i]);V(fork[(i+1)mod5]);untilfalse;endparendend答案：不满足“有限等待”准则，当每个哲学家都只拿到一把叉子时，发生死锁。改进的算法很多，可以选择不允许多个哲学家同时拿筷子来解决，其算法如下：解法I：varfork：array[0..4]ofsemaphore;varmutex:semaphore;fork[0]:=fork[1]:=fork[2]:=fork[3]:=fork[4]:=1;mutex:=1;beginparbeginPi:repeat//第i个哲学家的生活过程ThinkForWhile;P(mutex);//解法2设mutex的初值=4P(fork[i]);P(fork[(i+1)mod5]);V(mutex);EatForWhile;V(fork[i]);V(fork[(i+1)mod5]);untilfalse;parendend//解法3用信号量集