操作系统思考题答案.doc

操作系统部分思考题及简答题 【思考题】1如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？解：我们考虑在微机的操作系统中： 系统的调度管理进程至少是在运行状态。当有N个用户进程启动后，那么我们可以说用户的进程最多有一个在运行状态，最少有0个？ 有了这个条件，我们不难推出就绪进程和等待进程可能的数量。 如果我们讨论的多CPU平台的使用的操作系统，就是另外一种情况了。 所以我想题目应该给出一个系统的运行环境。2. 有没有这样的状态转换，为什么？ 等待运行； 就绪等待解：进程状态转换：在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换就绪运行 调度程序选择一个新的进程运行运行就绪 运行进程用完了时间片，运行进程被中断，因一高优先级进程处于就绪状态运行等待 当一进程必须等待时 OS尚未完成服务 对一资源的访问尚不能进行 初始化I/O 且必须等待结果 等待某一进程提供输入 (IPC)等待就绪 当所等待的事件发生时观察下面答案就明确了运行就绪等待进程的状态及其转换jklm3. 一个状态转换的发生，是否一定导致另一个转换发生，列出所有的可能解：一般情况下，当一个状态发生转换，系统调度会将当前进程置入相应状态队列，再从相应的队列中唤醒相关进程4. 举3个日常生活中类似进程的例子 医院看病的过程： 等待医院开门挂号看病划价付钱医院关门5要不要对缓冲区（临界资源）进行互斥操作？解：对于是“只读”的临界资源，我们可以认为不需要互斥操作。但，一定有一个对“只读”临界资源进行维护的“写”操作，那么必须要考虑 缓冲区 的互斥操作。6 . 用P.V操作解决下图之同步问题:getcopyputfstgGcCgPcgpp get复制一个记录:Cobegin get; copy; put;Coendf s t g初始状态 3,4,.,m 2 2 (1,2)g,c,p 4,5,.,m 3 3 (1,2,3) 设信息长度为mf1.m of arraySmutex,Sempty,Sfull:=1,1,0; /(f，s，t，g均为单缓冲区，不需要互斥量Smutex，Tmutex)Tmutex,Tempty,Tfull:=1,1,0Int x,y =1,1;/设有m个记录长度，一次get一个记录Process get。 wait(Sempty); wait (f); wait(Smutex); /wait(s); 和copy互斥 get 过程，fx s (x号记录) ； x+; signal(Smutex); /signal(s); signal(f); signal(Sfull); 。process copy wait(Sfull); wait(Tempty); wait(Smutex); /和get 互斥 wait(Tmutex); /和 put 互斥 copy 过程， st (y号记录) y+;signal（Tmutex）； signal（Smutex）； signal (Tfull); signal (Sempty);process put wait (Tfull); wait (g); wait(Tmutex); /和 copy 互斥 put 过程 tgy （y号记录）; signal (Tmutex); signal (g); signal (Tempty);解决下面的问题，首先你要掌握P（wait）、V（signal）操作和互斥信号量的概念。【作业】1. 推广例子中的消息缓冲问题。 消息缓冲区为k个，有1个发送进程， n个接收进程，每个接收进程对发送来的消息都必须取一次，若有m个发送进程呢？解： ：）这是一个典型的题目，在我们设计网络上的“聊天室”时所必须要解决的问题。 为了便于理解，我们也可以把这个问题先类比成一个读者优先的“读者写者”问题，即： 先考虑只有一个消息缓冲区（单缓冲区）1. 当消息缓冲区空时，n个读者（接收进程）等待，一个写者（发送进程）允许写入 2当消息缓冲区满时，n个读者进行阅读（接收），此时和写者进程 互斥，直到所有读者阅读完毕。 释放 读写互斥量 和 缓冲区。 注意这里我们不能简单的按照例子中的那样，将readcount 简单的计数。可以用下面的方法：为了保证n个读者（接收进程）都必须读一次，我们可以用n bit 二进制位来作为 n个读者（接收进程）是否接收的标志（0未读，1已读），直到所有的位翻转成1后，释放 读写互斥量（Wmutex） 和 缓冲区。 在具体写代码时，我们可以使用一个数组readcountn 来表示n bit array readcount1.n =0,0 /n个接收进程 已读标志 Wmutex = 1; / 允许发送进程写数据到 临界缓冲区 Rmutex = 1; / 允许接收进程 修改 已读标志读者i(接收进程i)： while (true) P(Rmutex); For(int j:=1;jn) P (RWmutex); /n bit全0，第一个读者（接收进程）启动，禁止接收 readcount i=1; V(Rmutex); 读（接收） P(Rmutex); For(j:=1;jn) V (RWmutex); / n bit全1,所有读者（接收进程）都读过了，/ 释放写互斥信号量 V(Rmutex); ; 写者(发送进程)： while (true) P(RWmutex); 写 V(RWmutex); ;现在我们再来考虑若有m个发送进程呢？如果还使用 单缓冲区，那么问题变得简单了，上面的程序可以不加修改的应用在这种情况下。再进一步，我们有m个发送进程，缓冲区为k个，n个接收进程，问题变的复杂些了。如果我们还是沿用上面“读者写者”的思路，在发送进程写数据时不允许接收进程读（读时也不允许写），显然执行的效率大大下降。所以我们要换一个思路，你可以先读懂我后面附中的“经典的生产者消费者问题”的n个缓冲区、m个生产者和k个消费者 的实现方法，那么这个问题也就明了许多。我们只要把这个算法的消费者Q进程改进成“每个缓冲区bufferj ”被所有n个接收进程都接收后再 j = (j+1)%n 读下一个缓冲即可。shou2.第二类读者写者问题：读者优先算法：设置两个互斥信号量：rwmutex 用于写者与其他读者/写者互斥的访问共享数据rmutex 用于读者互斥的访问读者计数器readcountvar rwmutex, rmutex ： semaphore := 1,1 ；int readcount = 0;cobeginreaderi begin / i=1,2,.P(rmutex);Readcount+;If (readcount = 1) P(rwmutex);V(rmutex);读数据；P(rmutex);Readcount-;If (readcount = 0) V(rwmutex);V(rmutex);EndWriterj begin / j = 1,2,.P(rwmutex);写更新；V(rwmutex);End Coend 写者优先条件：1）多个读者可以同时进行读2）写者必须互斥（只允许一个写者写，也不能读者写者同时进行）3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）解1：如果读者数是固定的，我们可采用下面的算法：rwmutex：用于写者与其他读者/写者互斥的访问共享数据 rmutex： 该信号量初始值设为10，表示最多允许10个读者进程同时进行读操作var rwmutex, rmutex ： semaphore := 1,10 ；cobeginreaderi begin / i=1,2,.P(rwmutex); /读者、写者互斥P(rmutex);V(rwmutex); / 释放读写互斥信号量，允许其它读、写进程访问资源读数据；V(rmutex);EndWriterj begin / j = 1,2,.P(rwmutex);For (i=1;i=10;i+) P(rmutex); /禁止新读者，并等待已进入的读者退出写更新；For (i=1;i=10;i+) V(rmutex); / 恢复允许rmutex 值为10V(rwmutex); End Coend 解2：如果读者数不固定，采用下面的算法：设置三个互斥信号量：rwmutex 用于写者与其他读者/写者互斥的访问共享数据rmutex 用于读者互斥的访问读者计数器readcountnrmutex 用于写者等待已进入读者退出，所有读者退出前互斥写操作var rwmutex, rmutex，nrmutex ： semaphore := 1，1，1 ； int readcount = 0;cobeginreaderi begin / i=1,2,.P(rwmutex); P(rmutex);Readcount+;If (readcount = 1) P(nrmutex); /有读者进入，互斥写操作V(rmutex);V(rwmutex); / 及时释放读写互斥信号量，允许其它读、写进程申请资源读数据；P(rmutex);Readcount-;If (readcount = 0) V(nrmutex); /所有读者退出，允许写更新V(rmutex);EndWriterj begin / j = 1,2,.P(rwmutex); / 互斥后续其它读者、写者P(nrmutex); /如有读者正在读，等待所有读者读完写更新；V(nrmutex); /允许后续新的第一个读者进入后互斥写操作 V(rwmutex); /允许后续新读者及其它写者End Coend 附经典的生产者消费者问题同步问题： P进程不能往“满”的缓冲区中放产品，设置信号量为S1 Q进程不能从“空”的缓冲区中取产品，设置信号量S2P： Q：while (true) while (true) 生产一个产品; P(s2); P(s1) ; 从缓冲区取产品; 送产品到缓冲区; V(s1); V(s2); 消费产品; ;S1初值为1，S2初值为0多个缓冲区的生产者和消费者：P：i = 0;while (true) 生产产品; P(S1); 往Buffer i放产品; V(S2); i = (i+1) % n; ;Q： j = 0;while (true) P(S2); 从Bufferj取产品; V(S1); 消费产品; j = (j+1) % n; ;n个缓冲区、m个生产者和k个消费者：P：i = 0;while (true) 生产产品; P(S1); P(mutex1); 往Buffer i放产品; i = (i+1) % n; V(mutex1); V(S2); ;Q： j = 0; while (true) P(S2); P(mutex2); 从Bufferj取产品; j = (j+1) % n; V(mutex2); V(S1); 消费产品;SPOOLing 技术原理答：SPOOLing 技术就是用于将一台独占设备改造成共享设备的一种行之有效的技术。详见书P219管道（POSIX）（见第3章第10题作业） Windows 2000 体系结构1) 系统采用分层结构设计 2) 保护模式 HAL（hardware abstraction layer）, kernel, executive.3) 户用模式 子系统集a) 仿真不同操作系统环境的子系统b) 提供安全功能的保护子系统 （security subsystems）用信号量机制实现写者优先的 读者写者 算法。解：（见思考题 2.第二类读者写者问题） 假定某系统有进程P0,P1,P2,P3,资源A,B,C，每类资源的数量分别为 10,5,7；若在T0时刻每个进程已分配的资源分别为(2,0,0)、(2,1,1)、(0,0,2)、(3,1,1)；试用银行家算法判断T0时刻系统是否安全？解：系统还有可用资源为：（3,3,3）分情况判定？在一个请求分页系统中，假定为某进程分配3个物理块且该进程的页面引用次序为：0,4,1,4,1,5,1,6,2,6,3,6,2,6,4,5 ；试计算页面置换算法分别为最佳、FIFO、LRU时的缺页次数。解： 最佳算法是一种理论上的算法：被淘汰的是永不使用或者是最长时间不再被访问的页面最佳OPT 0 4 1 4 1 5 1 6 2 6 3 6 2 6 4 5页1 0 0 1 1 1 1 1 6 6 6 6 6 6 6 4 5页2 4 0 0 0 5 5 5 2 2 2 2 2 2 2 2页3 4 4 4 4 4 4 4 4 3 3 3 3 3 3 x x x x x x x x x 共缺页中断9次 先进先出页面置换算法：淘汰最先进入内存的页面FIFO 0 4 1 4 1 5 1 6 2 6 3 6 2 6 4 5页1 0 4 1 1 1 5 5 6 2 2 3 3 3 3 4 5页2 0 4 4 4 1 1 5 6 6 2 2 2 2 3 4页3 0 0 0 4 4 1 5 5 6 6 6 6 2 3 x x x x x x x x x 共缺页中断9次 最近最久未使用置换算法：每个页面有一个记录自上次被访问以来所经历的时间的字段LRU 0 4 1 4 1 5 1 6 2 6 3 6 2 6 4 5栈顶 0 0 1 4 1 5 1 6 2 6 3 6 2 6 4 5 4 0 1 4 1 5 1 6 2 6 3 6 2 6 4栈底 4 0 0 4 4 5 1 1 2 2 3 3 2 6 x x x x x x x x x 共缺页中断9次 假定某计算机系统有3，000 个空闲磁盘块并用成组链接法对之进行管理（每组200个盘块），试画出相应的链接图，并说明空闲盘块的分配与回收过程。解：(见第9章第11题作业)12