操作系统习题1-1

生产者–消费者问题（即有界缓冲区问题）问题一群生产者向一个有界缓冲区存放产品，只要缓冲区未满，就可以存入；又有一群消费者从有界缓冲区取走产品，只要缓冲区未空，就可以取走。要求存与存之间、取与取之间和存与取之间不能同时进行，即一次只能有一个生产者或者一个消费者进入缓冲区，也就是所有的生产者与消费者必须互斥地访问缓冲区。当缓冲区满时，生产者停止放入产品，当缓冲区空时，消费者停止取走产品，即生产与消费同步。这里，生产的产品与消费的产品是等效的。用P、V操作解决。设置信号量：互斥使用有界缓冲区的信号量S，初值为1；同步信号量：有界缓冲区的大小，即可以存放产品的最大数n，初值为k；有界缓冲区中已经存放的产品个数m，初值为0。生产者–消费者问题的解决如图所示。图生产者-消费者问题生产产品→缓冲区生产者P(n)V(s)P(s)V(m)缓冲区→取走产品消费者P(m)V(s)P(s)V(n)问题(课本pp42的问题)：（1）若消费速度较生产速度快得多，上图可以简化吗？如何简化？（2）若P(n)与P(s)颠倒，会产生什么问题？（3）若V(s)与V(m)颠倒，会如何？V(s)与V(n)呢？解答（1）若消费速度较生产速度快得多，上图可以简化吗？如何简化？答案：可以简化，简化结果如图。因为消费速度较生产速度快得多，缓冲区总是空的，相当于p(n)操作不会出现等待状态，故可以省略简化，v(n)不需要唤醒，也可以省略简化。简化结果图生产者-消费者问题简化结果生产产品→缓冲区生产者V(s)P(s)V(m)缓冲区→取走产品消费者P(m)V(s)P(s)解答（2）若P(n)与P(s)颠倒，会产生什么问题？答案：若P(n)与P(s)颠倒，会产生死锁问题。因为有可能出现缓冲区满，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的利用率提高多少？解答1.每个进程等待的百分比率为p，则n个进程同时等待的概率为pn，当n个进程同时等待I/O期间CPU是空闲的，故CPU的利用率是1-pn2.除去操作系统占用的内存，剩余内存能容纳4个用户进程，由于每个用户进程等待I/O的时间为80％，故CPU的利用率为1-(80%)4=59%解答1.若再增加1M内存，内存就能容纳9个用户进程了，CPU的利用率为1-(80%)9=87%2.利用率提高为(87%)/(59%)=147%147％－100％＝47％增加1M内存CPU利用率47％。问题若内存中存在3道程序A、B、C，它们按照A、B、C的优先次序运行。各程序的计算轨迹为：–A：计算(20ms)、I/O(30ms)、计算(10ms)–B：计算(40ms)、I/O(20ms)、计算(10ms)–C：计算(10ms)、I/O(30ms)、计算(20ms)问：如果三道程序都使用相同的设备进行I/O(即程序用串行方式使用设备，调度开销忽略不计)。试分别画出单道和多道运行的时间关系图。两种情况下，CPU的平均利用率各为多少？解答•单道：总运行时间是190ms，CPU的利用率是110/190＝61.3％。解答•多道的总运行时间140ms，CPU的利用率是110/140＝78.6％。问题假设有一种低级调度算法是让“最近使用处理器较少的进程”运行，试解释这种算法对“I/O繁重”型作业有利，但并不是永远不受理“处理器繁重”型作业。解答因为I/O繁忙作业忙于I/O，所以使用CPU较少，按照调度策略算法优先执行。一个进程等待CPU时间够长，是最近最少使用CPU进程，被优先调度。题二:计算作业周转时间操作系统中采用多道程序设计技术以提高CPU及各种资源的利用率,试以下例比较说明.假定系统中有一个CPU,一台I/O设备,二者可同时工作,有三个作业X,Y,Z,各自的程序行为是:I/OCPUI/OCPUI/O(单位:ms)X2020203020Y40304010Z302030①假若采用单道串行方式调度运行,总的周转时间是多少?②假若采用多道程序设计技术调度,调度优先权X最高,Y其次,Z最低,当前三个作业都已就绪.试画出调度时序图,给出各自的以及总的周转时间.题二续①各自的周转时间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/3153tXYZI/OYYXXXZI/OCPUI/OCPUI/O(单位:ms)X2020203020Y40304010Z30203020202020203020304010303020题三：银行家算法在银行家算法中，若出现下述的资源分配情况：ProcessAllocationNeedAvailablep01,0,2,37,6,6,13,0,1,4p12,1,0,16,6,5,7p21,0,4,13,5,1,5p30,3,2,13,1,2,8p43,2,1,03,2,2,5p50,1,2,62,0,1,2试问:（１）该状态是否安全？（要写出银行家算法的过程）（２）若进程p１提出请求Request(2,0,1,1)后，系统能否将资源分配给它？为什么？Available的变化p53,1,3,10p33,4,5,11p46,6,6,11p18,7,6,12p09,7,8,15p210,7,12,16（1）安全！needAvailableP14,6,4,61,0,0,3如果满足（2，0，1，1）请求，则所有其它请求再也无法满足，造成死锁。