操作系统思考题答案

《操作系统思考题答案》由会员分享，可在线阅读，更多相关《操作系统思考题答案（13页珍藏版）》请在装配图网上搜索。

1、【思考题】1. 如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个;等待进程最多几个，最少几个？解：我们考虑在微机的操作系统中：系统的调度管理进程至少是在运行状态。当有N个用户进程启动后，那么我们可以说用户的进程最多有一个在运行状态，最少有0个？有了这个条件，我们不难推出就绪进程和等待进程可能的数量。如果我们讨论的多CPU平台的使用的操作系统，就是另外一种情况了。所以我想题目应该给出一个系统的运行环境。2. 有没有这样的状态转换，为什么？等待运行；就绪等待解：进程状态转换：在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换

2、就绪运行调度程序选择一个新的进程运行运行就绪运行进程用完了时间片，运行进程被中断，因一高优先级进程处于就绪状态运行等待当一进程必须等待时OS尚未完成服务 对一资源的访问尚不能进行 初始化I/O且必须等待结果 等待某一进程提供输入(IPC)等待就绪当所等待的事件发生时观察下面答案就明确了运仃进程的状态及其转换3. 一个状态转换的发生，是否一定导致另一个转换发生，列出所有的可能解：一般情况下，当一个状态发生转换，系统调度会将当前进程置入相应状态队列，再从相应的队列中唤醒相关进程进程队列就绪队列无优先级（例：HFQ医当事件n发生，对应队列移进就绪队列5要不要对缓冲区（临界资源）进行互斥操作？解：对于

3、是“只读”的临界资源，我们可以认为不需要互斥操作。但，一定有一个对“只读”临界资源进行维护的“写”操作，那么必须要考虑缓冲区的互斥操作。6.用P.V操作解决下图之同步问题:CcJpgetC3复制一个记录:Cobeginget;copy;put;Coendg(1,2)(1,2,3)fst初始状态3,4,.,m22g,c,p4,5,.,m33设信息长度为mf1.mofarraySmutex,Sempty,Sfull:=1,1,0;/(f，s，t，g均为单缓冲区，不需要互斥量Smutex，Tmutex)Tmutex,Tempty,Tfull:=1,1,0Intx,y=1,1;/设有m个记录长度，一次

4、get一个记录Processget。wait(Sempty);wait(f);wait(Smutex);/wait(s);和copy互斥get过程，fxTs(x号记录)；x+;signal(Smutex);/signal(s);signal(f);signal(Sfull);。processcopywait(Sfull);wait(Tempty);wait(Smutex);/和get互斥wait(Tmutex);/和put互斥copy过程，sTt(y号记录)y+;signal(Tmutex)；signal(Smutex)；signal(Tfull);signal(Sempty);process

5、putwait(Tfull);wait(g);wait(Tmutex);/和copy互斥put过程tgy(y号记录)；signal(Tmutex);signal(g)；signal(Tempty)；解决下面的问题，首先你要掌握P(wait)、V(signal)操作和互斥信号量的概念。【作业】1. 推广例子中的消息缓冲问题。消息缓冲区为k个，有1个发送进程，n个接收进程，每个接收进程对发送来的消息都必须取一次，若有m个发送进程呢？解：)这是一个典型的题目，在我们设计网络上的“聊天室”时所必须要解决的问题。为了便于理解，我们也可以把这个问题先类比成一个读者优先的“读者写者”问题，即：先考虑只有一个

6、消息缓冲区(单缓冲区)1. 当消息缓冲区空时，n个读者(接收进程)等待，一个写者(发送进程)允许写入2. 当消息缓冲区满时，n个读者进行阅读(接收)，此时和写者进程互斥，直到所有读者阅读完毕。释放读写互斥量和缓冲区。注意这里我们不能简单的按照例子中的那样，将readcount简单的计数。可以用下面的方法：为了保证n个读者(接收进程)都必须读一次，我们可以用nbit二进制位来作为n个读者(接收进程)是否接收的标志(0未读，1已读)，直到所有的位翻转成1后，释放读写互斥量(Wmutex)和缓冲区。在具体写代码时，我们可以使用一个数组readcountn来表示nbitarrayreadcount1.

7、n=0,.,0n个接收进程已读标志Wmutex=1;/允许发送进程写数据到临界缓冲区Rmutex=1;/允许接收进程修改已读标志读者i(接收进程i)：while(true)P(Rmutex);For(intj:=1;jn)P(RWmutex);/nbit全0，第一个读者(接收进程)启动，禁止接收readcounti=1;V(Rmutex);读(接收)P(Rmutex);For(j:=1;jn)V(RWmutex);/nbit全1,所有读者(接收进程)都读过了，/释放写互斥信号量V(Rmutex);写者(发送进程)：while(true)P(RWmutex);写V(RWmutex);现在我们再来

8、考虑若有m个发送进程呢？如果还使用单缓冲区，那么问题变得简单了，上面的程序可以不加修改的应用在这种情况下。再进一步，我们有m个发送进程，缓冲区为k个，n个接收进程，问题变的复杂些了。如果我们还是沿用上面“读者写者”的思路，在发送进程写数据时不允许接收进程读(读时也不允许写)，显然执行的效率大大下降。所以我们要换一个思路，你可以先读懂我后面附中的“经典的生产者一消费者问题”的n个缓冲区、m个生产者和k个消费者的实现方法，那么这个问题也就明了许多。我们只要把这个算法的消费者Q进程改进成“每个缓冲区buffer”被所有n个接收进程都接收后再j=(j+1)%n读下一个缓冲即可。shou2. 第二类读者

9、写者问题：读者优先算法：设置两个互斥信号量：rwmutex用于写者与其他读者/写者互斥的访问共享数据rmutex用于读者互斥的访问读者计数器readcountvarrwmutex,rmutex：semaphore:=1,1；intreadcount=0;cobeginreaderibegin/i=l,2,.P(rmutex);Readcount+;If(readcount=l)P(rwmutex);V(rmutex);读数据；P(rmutex);Readcount-;If(readcount=0)V(rwmutex);V(rmutex);EndWriterjbegin/j=l,2,.P(rwm

10、utex);写更新；V(rwmutex);EndCoend写者优先条件：1) 多个读者可以同时进行读2) 写者必须互斥(只允许一个写者写，也不能读者写者同时进行)3) 写者优先于读者(一旦有写者，则后续读者必须等待，唤醒时优先考虑写者)解1：如果读者数是固定的，我们可采用下面的算法：rwmutex:用于写者与其他读者/写者互斥的访问共享数据rmutex：该信号量初始值设为10，表示最多允许10个读者进程同时进行读操作varrwmutex,rmutex:semaphore:=1,10；cobeginreaderibegin/i=l,2,.P(rwmutex);/读者、写者互斥P(rmutex);

11、V(rwmutex);/释放读写互斥信号量，允许其它读、写进程访问资源读数据；V(rmutex);EndWriterjbegin/j=l,2,.P(rwmutex);For(i=l;i=l0;i+)P(rmutex);/禁止新读者，并等待已进入的读者退出写更新；For(i=l;i=l0;i+)V(rmutex);/恢复允许rmutex值为l0V(rwmutex);EndCoend7解2：如果读者数不固定，采用下面的算法：设置三个互斥信号量：rwmutex用于写者与其他读者/写者互斥的访问共享数据rmutex用于读者互斥的访问读者计数器readcountnrmutex用于写者等待已进入读者退出，

12、所有读者退出前互斥写操作varrwmutex,rmutex，nrmutex：semaphore:=1，1，1；intreadcount=0;cobeginreaderibegin/i=l,2,.P(rwmutex);P(rmutex);Readcount+;If(readcount=l)P(nrmutex);/有读者进入，互斥写操作V(rmutex);V(rwmutex);/及时释放读写互斥信号量，允许其它读、写进程申请资源读数据；P(rmutex);Readcount-;If(readcount=0)V(nrmutex);/所有读者退出，允许写更新V(rmutex);EndWriterjbe

13、gin/j=l,2,.P(rwmutex);/互斥后续其它读者、写者P(nrmutex);/如有读者正在读，等待所有读者读完写更新；V(nrmutex);/允许后续新的第一个读者进入后互斥写操作V(rwmutex);/允许后续新读者及其它写者EndCoend8附经典的生产者一消费者问题同步问题：P进程不能往“满”的缓冲区中放产品，设置信号量为S1Q进程不能从“空”的缓冲区中取产品，设置信号量S2P：while(true)生产一个产品;P(s1);送产品到缓冲区;V(s2);Q：while(true)P(s2);从缓冲区取产品;V(s1);消费产品;S1初值为1，S2初值为09多个缓冲区的生产者

14、和消费者：P：i=0;while(true)生产产品;P(S1);往Bufferi放产品;V(S2);i=(i+1)%n;Q：j=0;while(true)P(S2);从Buffer取产品;V(S1);消费产品;j=(j+1)%n;10#n个缓冲区、m个生产者和k个消费者:生产产品;从取产品往放产品消费产品SPOOLing技术原理答：SPOOLing技术就是用于将一台独占设备改造成共享设备的一种行之有效的技术。详见书P219管道（POSIX）（见第3章第10题作业）Windows2000体系结构12#executiveI/Omanager1)2)3)系统采用分层结构设计保护模式h户用模式g子系

15、统集HAL(ha环境申仿真不同操作系统b）（提供安全功能的保护子系统用信号解:securityexiobjectrdwareiabsifactionprocessecutive.agorplugandplaymanagervirtualmemorymanage境的了系统统(securitysubsystems)network量机制实现写者优先的读者-写者见思考题2.第二类读者写者问kernel#thardwareabstractionlayer假定定某系统有进程p0,P1,P2,P3，资源A,B,C,每类资源的数量分别为10，5|7；若在T0吋亥畑个进程已分配的资源分别为（玄00）、（21舟、

16、00,2）、Y3去1*试岷行家算法判断羽一时刻系统是否安仝?hardware解系统还有可用资源为：（3,3,3）分情况判定？在一个请求分页系统中，假定为某进程分配3个物理块且该进程的页面引用次序为：0,4,1,4,1,5,1,6,2,6,3,6,2,6,4,5；试计算页面置换算法分别为最佳、FIFO、LRU时的缺页次数。FIFO041415页1041115页204441页30004xxxx1626362645562233334515662222344155666623xxxxx最佳OPT0414151626362页10011111666666页2400055522222页34444444433

17、3xxxxxxx共缺页中断9次解：最佳算法是一种理论上的算法：被淘汰的是永不使用或者是最长时间不再被访问的页面645645222333xx先进先出页面置换算法：淘汰最先进入内存的页面共缺页中断9次最近最久未使用置换算法：每个页面有一个记录自上次被访问以来所经历的时间的字段LRU0414151626362645栈顶0014151626362645401415162636264栈底40044511223326xxxxxxxxx共缺页中断9次假定某计算机系统有3，000个空闲磁盘块并用成组链接法对之进行管理（每组200个盘块）试画出相应的链接图，并说明空闲盘块的分配与回收过程。解：（见第9章第11题作业）13