操作系统大题

第二章1.司机只有在售票员关车门后，才能启动汽车。售票员只有在司机到站停车后，才能开车门。解：Semaphoreclose=0，stop=0；driver(){/*司机*/while(True){P(close);启动车辆;正常行车;到站停车;V(stop);}}Conductor(){/*售票员*/while(True){关车门;V(close);售票;P(stop);开车门;上下乘客;}}Main(){parbegin(driver,conductor);}2.假定系统有3个并发进程get、copy和put共享缓冲器B1和B2。进程get负责从输入设备上读信息，每读出一条记录后放到B1中。进程copy从缓冲器B1中取出一条记录拷贝后存入B2。进程put取出B2中的记录打印输出。B1和B2每次只能存放一条记录。要求3个进程协调完成任务，使打印出来的与读入的记录个数、次序完全一样。请用记录型信号量写出并发程序。解：设置4个信号量，其中empty1对应空闲的缓冲区B1，其初值为1；full1对应缓冲区B1中的记录，其初值为0；empty2对应空闲的缓冲区B2，其初值为1；full2对应缓冲区B2中的记录，其初值为0。相应进程描述为：get(){while(1){从输入设备读入一条记录;P(empty1);将记录存入缓冲区B1；V(full1);}}copy(){while(1){P(full1);从缓冲区B1中取出一条记录;V(empty1);P(empty2);将取出的记录存入缓冲区B2；V(full2);}}put(){while(1){P(full2);从缓冲区B2中取出一条记录;V(empty2);将取出的记录打印出来；}}•Main(){parbegin(get,copy,put);}3.桌上有一只盘子，最多可容纳两个水果，每次只能放入或取出一个水果。爸爸专向盘中放苹果，妈妈专向盘中放橘子；儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。请用P、V操作实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。答：设置信号量empty表示还可以向盘中放几个水果，其初值为2；apple对应已放入盘中的苹果，orange对应已放入盘中的橘子，它们的初值均为0；mutex用来实现对盘子的互斥访问（包括放和取），其初值为1。•father(){mother(){while(1){while(1){P(empty);P(empty);P(mutex);P(mutex);向盘中放苹果；向盘中放橘子；V(mutex);V(mutex);V(apple);V(orange);}}}}•son(){daughter(){while(1){while(1){P(orange);P(apple);P(mutex);P(mutex);从盘中取橘子；从盘中取苹果；V(mutex);V(mutex);V(empty);V(empty);吃橘子；吃苹果；}}}}4.一个主修动物行为学、辅修计算机科学的学生参加一个课题，调查花果山的猴子是否能理解死锁。他找到一个峡谷，横跨峡谷拉了一根绳索（假设为南北方向），以便于猴子越过峡谷。只要它们朝着相同的方向，同一时刻可以有多只猴子通过。但是如果在相反的方向同时有猴子通过则会发生死锁(这些猴子将被卡在绳索中间，假设这些猴子无法在绳索上从另一只猴子身上翻过去)。如果一只猴子想越过峡谷，它必须看当前是否有别的猴子在逆向通过。请用信号量机制写一个避免死锁的算法来解决该问题。解：将猴子越过峡谷的南北方向分别标记为S和W；并用整形变量countS、countW分别表示往S、W方向上已爬上绳索的猴子数，它们的初值为0；再设置三个初值为1的互斥信号量：SS用来实现对countS的互斥访问，SW用来实现对countW的互斥访问。mutex用来实现两个方向上猴子对绳索的互斥使用。则可将往S方向上猴子的动作描述为：wait(SS);if(countS=0)thenwait(mutex);countS:=countS+1;sigal(SS);猴子通过绳索由北向南越过峡谷；wait(SS);countS:=countS-1;if(countS=0)thensingal(mutex);sigal(SS);•W方向上猴子的算法与S方向类似，只需将SS替换为SW，countS替换成countW即可。•有一个理发师，一把理发椅和n把供等候理发的顾客坐的椅子。•如果没有顾客，则理发师便在理发椅上睡觉；•当一个顾客到来时，他必须先唤醒理发师。如果顾客到来时理发师正在理发，则如果有空椅子，可坐下来等；否则离开。信号量max;//初始n+1，表示理发店可容纳的顾客总数。信号量chair；//初始n，空闲的椅子信号量barber_chair；//初始1,表示理发椅空闲信号量finished；//初始0，表示一次理发结束信号量ready；//初始0，表示客人准备就绪解：customer(){barber(){while(1){while(1){P(max);P(ready);P(chair);…barbering…P(barber_chair);V(finished);V(chair);V(barber_chair);V(ready);}…barbered…}P(finished);V(max);}}3.有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。如下表所示(作业的优先数即为进程的优先数，优先数越小越好)。作业名到达时间估计运行时间优先数A10:00405B10:20303C10:30504D10:50206（1）列出所有作业进入内存时刻及结束时刻？（2）计算平均周转时间？（1）作业A、B、C、D进入内存时刻分别为：10:00、10:20、11:10、10:50。它们的结束时刻为：11:10、10:50、12:00、12:20。（2）作业A、B、C、D的周转时间分别为70，30，90，90分钟，平均周转时间为70分钟。4.设系统仅有一类数量为M的独占型资源，系统中N个进程竞争该类资源，其中各进程对该类资源的最大需求为W。当M，N，W分别取下列值时，试判断下列哪些情况会发生死锁？为什么？(1)M=2;N=2，W=2；(2)M=3;N=2，W=2；(3)M=3;N=2，W=3；(4)M=5;N=3，W=2；(5)M=6;N=3，W=3；判断是否发生死锁，可用以下经验公式：公式表明，若要系统不发生死锁，则进程的最大需求量W不得超过x；若超过则可能导致死锁。利用资源分配图举一个死锁例子便可。将M、N代入公式，得到以下结果：(1)x=1,xW，可能会死锁；(2)x=2;x=W，不会死锁；(3)x=2;xW，可能会死锁；(4)x=7/3;xW，不会死锁；(5)x=8/3;xW，可能会死锁；（3）（5）一台计算机有10台磁带机被n个进程竞争，每个进程最多需要3台磁带机，那么n最多为_____时，系统没有死锁的危险？解：n最大为4。假设有m个资源，每个进程最多可申请k个资源，则系统要想避免死锁的发生，允许的最多进程数n为1+（m-k）/（k-1）。当后面一项是小数时，总是取整数。2：某系统采用页式存储管理策略，拥有逻辑空间32页，每页2K，拥有物理空间1M①写出逻辑地址的格式②若不考虑访问权限等，进程的页表有多少项？每项至少有多少位？③如果物理空间减少一半，页表结构应相应作怎样的改变？答：①该系统拥有逻辑空间32页，故逻辑地址中页号必须用5位描述；而每页为2K，因此，页内地址必须用11位描述，格式如下：1511100②每个进程最多32个页面，因此进程的页表项最多为32项；页表项只需给出页所对应的物理块块号，1M的物理空间可分为29个内存块，故每个页表项至少有9位。③如果物理空间减少一半，则页表中页表项数不变，但每项的长度减少1位。3：已知某分页系统，主存容量为64K，页面大小为1K，对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。（1）将十进制的逻辑地址1023、2500、3500、4500转换成物理地址？（2）以十进制的逻辑地址1023为例画出地址变换过程图？答：（1）①逻辑地址1023：1023/1K，得页号为0，页内地址为1023，查页表找到对应的物理块号为2，故物理地址为2×1K+1023=3071②逻辑地址2500：2500/1K，得页号为2，页内地址为452，查页表找到对应的物理块号为6，故物理地址为6×1K+452=6596③逻辑地址3500：3500/1K，得页号为3，页内地址为428，查页表找到对应的物理块号为7，故物理地址为7×1K+428=7596④逻辑地址4500：4500/1K，得页号为4，页内地址为404，因页号不小于页表长度，故产生越界中断（2）地址变换过程：5：某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面对应的物理块号如下表：页号物理块号051102437则逻辑地址0A5C（H）所对应的物理地址为多少？解：•0A5C＝0000,1010,0101,1100•页号为2，对应块号为4，有：•物理地址：0001，0010,0101,1100•即：125C（H）6：对于下面的段表，请将逻辑地址（0,137），（1,4000），(2,3600)，(5,230)转换成物理地址。段号内存始址段长050K10K160K3K270K5K3120K8K4150K4K解：(1)物理地址为：50K+137=51337(2)段内地址超过段长3K，产生越界中断。(3)物理地址为：70K+3600=75280(4)段号等于段表长，段号不合法，产生越界中断。第五章1、假定磁盘有200个柱面，编号0~199，当前存取臂的位置在143号柱面上，并刚刚完成了125号柱面的服务请求，如果请求队列的先后顺序是：86，147，91，177，94，150，102，175，130；试问：为完成上述请求，下列算法存取臂移动的总量是多少？并算出存取臂移动的顺序。(1)先来先服务算法FCFS；(2)最短查找时间优先算法SSTF；(3)扫描算法SCAN。(4)C-SCAN算法。解：•(1)先来先服务:磁头移动顺序为:143→86→147→91→177→94→150→102→175→130,磁头移动共565柱面。•最短寻道时间优先（SSTF）:磁头移动顺序为:143→147→150→130→102→94→91→86→175→177,磁头移动共162柱面。•SCAN算法：磁头移动顺序为:143→147→150→175→177→130→102→94→91→86,磁头移动共125柱面。CSCAN算法：磁头移动顺序为:143→147→150→175→177→86→91→94→102→130,磁头移动共169柱面。2.假设磁盘有200个磁道，磁盘请求队列中是一些随机请求，它们按照到达的次序分别处于98、183、37、122、14、124、65、67号磁道上，当前磁头在53号磁道上，并向磁道号减小的方向上移动。请给出按先来先服务算法（FCFS）、最短寻道时间优先算法(SSTF)、扫描算法（SCAN）及循环扫描算法（CSCAN）算法进行磁盘调度时满足请求的次序，并算出它们的平价寻道长度?FCFSSSTFSCANCSCAN被访问的下一个磁道号移动的磁道数被访问的下一个磁道号移动的磁道数被访问的下一个磁道号移动的磁道数被访问的下一个磁道号移动的磁道数98456512371637161838567214231423371463730655118316912285142367212459141089884983112221241101222412224982465591242124267316721835918359652平均寻道长度80平均寻道长度29.5平均寻道长