《操作系统习题ppt课件.ppt》由会员分享，可在线阅读，更多相关《操作系统习题ppt课件.ppt（19页珍藏版）》请在三一办公上搜索。
1、生产者消费者问题（即有界缓冲区问题）问题 一群生产者向一个有界缓冲区存放产品，只要缓冲区未满，就可以存入；又有一群消费者从有界缓冲区取走产品，只要缓冲区未空，就可以取走。要求存与存之间、取与取之间和存与取之间不能同时进行，即一次只能有一个生产者或者一个消费者进入缓冲区，也就是所有的生产者与消费者必须互斥地访问缓冲区。当缓冲区满时，生产者停止放入产品，当缓冲区空时，消费者停止取走产品，即生产与消费同步。这里，生产的产品与消费的产品是等效的。,用P、V操作解决。设置信号量：互斥使用有界缓冲区的信号量S，初值为1；同步信号量：有界缓冲区的大小，即可以存放产品的最大数n，初值为k；有界缓冲区中已经存放
2、的产品个数m，初值为0。生产者消费者问题的解决如图所示。,问题(课本pp42的问题)：,（1）若消费速度较生产速度快得多，上图可以简化吗？如何简化？（2）若P(n)与P(s)颠倒，会产生什么问题？（3）若V(s)与V(m)颠倒，会如何？V(s)与V(n)呢？,解答,（1）若消费速度较生产速度快得多，上图可以简化吗？如何简化？答案：可以简化，简化结果如图。因为消费速度较生产速度快得多，缓冲区总是空的，相当于p(n)操作不会出现等待状态，故可以省略简化，v(n)不需要唤醒，也可以省略简化。,简化结果,解答,（2）若P(n)与P(s)颠倒，会产生什么问题？答案：若P(n)与P(s)颠倒，会产生死锁问
3、题。因为有可能出现缓冲区满，n=0，s=1的情形：生产者执行P(s)，则s变为s=0；生产者执行P(n)，则n变为n=-1，生产者阻塞。消费者执行P(m)；消费者执行P(s)，则s变为s=-1，消费者阻塞；这样进入相互等待状态，如果没有外界作用，则导致死锁。,解答,（3）若V(s)与V(m)颠倒，会如何？V(s)与V(n)呢？答案：不会死锁。因为v操作，是释放资源，不存在死锁的条件。,问题,有一台计算机，具有1MB内存，操作系统占用200KB，每个用户占用200KB。如果用户进程等待I/O的时间为80%，若增加1MB内存，则CPU的利用率提高多少？,解答,每个进程等待的百分比率为p，则n个进程
4、同时等待的概率为pn，当n个进程同时等待I/O期间CPU是空闲的，故CPU的利用率是 1-pn除去操作系统占用的内存，剩余内存能容纳4个用户进程，由于每个用户进程等待I/O的时间为80，故CPU的利用率为 1-(80%)4=59%,解答,若再增加1M内存，内存就能容纳9个用户进程了，CPU的利用率为 1-(80%)9=87%利用率提高为 (87%)/(59%)=147% 14710047 增加1M内存CPU利用率47。,问题,若内存中存在3道程序A、B、C，它们按照A、B、C的优先次序运行。各程序的计算轨迹为：A：计算(20ms)、I/O(30ms)、计算(10ms)B：计算(40ms) 、I
5、/O(20ms)、计算(10ms)C：计算(10ms)、I/O(30ms)、计算(20ms)问：如果三道程序都使用相同的设备进行I/O(即程序用串行方式使用设备，调度开销忽略不计)。试分别画出单道和多道运行的时间关系图。两种情况下，CPU的平均利用率各为多少？,解答,单道：总运行时间是190ms，CPU的利用率是110/19061.3。,解答,多道的总运行时间140ms，CPU的利用率是110/14078.6。,问题,假设有一种低级调度算法是让“最近使用处理器较少的进程”运行，试解释这种算法对“I/O繁重”型作业有利，但并不是永远不受理“处理器繁重”型作业。,解答,因为I/O繁忙作业忙于I/O
6、，所以使用CPU较少，按照调度策略算法优先执行。一个进程等待CPU时间够长，是最近最少使用CPU进程，被优先调度。,题二:计算作业周转时间,操作系统中采用多道程序设计技术以提高CPU及各种资源的利用率, 试以下例比较说明. 假定系统中有一个CPU, 一台I/O设备, 二者可同时工作, 有三个作业X,Y,Z, 各自的程序行为是: I/O CPU I/O CPU I/O (单位: ms) X 20 20 20 30 20 Y 40 30 40 10 Z 30 20 30 假若采用单道串行方式调度运行, 总的周转时间是多少? 假若采用多道程序设计技术调度, 调度优先权X最高, Y其次, Z最低,当前
7、三个作业都已就绪. 试画出调度时序图, 给出各自的以及总的周转时间.,题二续,各自的周转时间 X=（20+20+20+30+20） =110 (ms) Y = （20+20+20+30+20）+（40+30+40+10） = 230 (ms) Z = （20+20+20+30+20）+（40+30+40+10）+（30+20+30）=310(ms)总的=110+230+310=570，平均=570/3=190各自的周转时间X:110(ms) Y:140 (ms)Z:210(ms)总的=110+140+210=460，平均=460/3153,t,X,Y,Z,I/O,Y,Y,X,X,X,20,20
8、,20,20,20,30,20,30,40,10,30,30,20,题三：银行家算法,在银行家算法中，若出现下述的资源分配情况： Process Allocation Need Available p0 1,0,2,3 7,6,6,1 3,0,1,4 p1 2,1,0,1 6,6,5,7 p2 1,0,4,1 3,5,1,5 p3 0,3,2,1 3,1,2,8 p4 3,2,1,0 3,2,2,5 p5 0,1,2,6 2,0,1,2试问:（）该状态是否安全？ （要写出银行家算法的过程） （）若进程p提出请求Request(2,0,1,1)后，系统能否将资源分配给它？为什么？,need Available P1 4,6,4,6 1,0,0,3如果满足（2，0，1，1）请求，则所有其它请求再也无法满足，造成死锁。,
