《操作系统原理复习》PPT课件.ppt

操作系统原理复习,例：设有4个进程，其执行的先后流图如下图所 示。用P、V操作实现其同步。,p1() 执行P1自 己的程序; V(s12); V(s13); ,p2() P(s12); 执行P2自 己的程序; V(s24); ,p3() P(s13); 执行P3自 己的程序; V(s34); ,p4() P(s24) P(s34) 执行P4自 己的程序; ,semaphore s12=0,s13=0,s24=0s,s34=0 main() Cobegin p1();p2();p3();p4(); Coend ,设公共汽车上，司机和售票员的活动分别是 司机活动：启动车辆；正常运行；到站停车。 售票员活动：关门；售票；开门。用信号量和P、V操作实现它们的关系。,启动车辆； 正常运行； 到站停车；,关门； 售票； 开门；,答：设置两个信号量：S1、S2， S1表示门是否关上，其初值为0。 S2表示车是否停下，其初值为1。,Driver() While(true) p(S1); 启动车辆； 正常行车； 到站停车； v(S2)； ,Busman( ) While(true) 关车门； V（S1）； 售票； P（S2）； 开车门； 上下乘客； ,semaphore s1=0; semaphore s2=1; main( ) Cobegin Driver( ); Busman(); Coend ,举例： 用P、V操作实现下述问题。桌子上有一个盘子，可以存放一个水果，父亲总是放苹果到盘子中，而母亲总是放香蕉到盘子中；一个儿子专等吃盘中的香蕉，而一个女儿专等吃盘中的苹果。,设dish=1表示盘子是否为空；apple=0表示盘中是否有苹果；banana=0表示盘中是否有香蕉。 semaphore dish=1; semaphore apple=0; semaphore banana=0; Main() cobegin father(); mather(); son(); daughter(); coend ,Father() while(ture) p(dish); 将苹果放入盘中； v(apple); Mother() while(ture) p(dish); 将香蕉放入盘中； v(banana); ,son() while(ture) p(banana); 从盘中取出香蕉； v(dish); 吃香蕉； daughter() while(ture) p(apple); 从盘中取出苹果； v(dish); 吃苹果； ,某寺庙，有小、老和尚若干，有一水缸，有小和尚提水入缸供老和尚饮用。水缸可容10桶水，水取自同一井中。水井径窄，每次只能容一个桶取水。水桶总数为3个。每次入、取缸水仅为1桶，且不可同时进行。试给出取水、入水的算法描述,设置5个信号量：互斥信号量mutex1,用于实现对水井的互斥使用，其初值为1；互斥信号量mutex2，用于实现对水缸的互斥使用，其初值为1；信号量empty，用于记录水缸中还可以装入水的桶数，其初值为10；信号量full，用于记录水缸中已装入水的桶数，其初值为0；信号量count，用于记录可用水桶数目，其初值为3。 Semaphore mutex1=1， mutex2=1， empty=10， full=0， count=3； Main( ) cobegin Get(); Use(); Coend ,Get( ) while(ture) p(empty); P(count); P(mutex1); 从井中取水； V(mutex1); P(mutex2); 将水倒入水缸； V(mutex2); V(count); V(full); ,Use( ) while (ture) P(full); P(count); P(mutex2); 从缸中取水； V(mutex2); V(count); V(empty); ,用PV原语描述生产者消费者问题。把系统中使用某一类资源的进程称为该资源的消费者，而把释放同类资源的进程称为该资源的生产者。生产者消费者满足如下条件： 消费者想接收数据时，有界缓冲区中至少有一个单元是满的； 生产者想发送数据时，有界缓冲区中至少有一个单元是空的； 由于有界缓冲区是临界资源，因此各生产者和各消费者进程之间必须互斥执行。,设公用信号量mutex保证生产者消费者进程之间的互斥,其初值为1，设信号量avail为生产者进程的私有信号量，表示有界缓冲区中空单元的数目，其初值为n，full为消费者进程的私有信号量，表示有界缓冲区中非空单元的数目，其初值为0 Semaphore mutex=1， avail =n， full=0；,remove() P(full) P(mutex) 取缓冲区中某单元数据 V(avail) V(mutex) ,deposit() P(avail) P(mutex) 送数据入缓冲区某单元 V(full) V(mutex) ,Main( ) cobegin deposit()； remove()； Coend ,有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子，每个哲学家的行为是思考，感到饥饿，然后吃通心粉，为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子，请用P、V原语描述每个哲学家的进餐过程。,设公用信号量si 表示是否有第i个筷子（i=0,1,2,3,4 ）， 其初值均为1。 Semaphore s5； s0=s1=s2=s3=s4=1;,Main( ) cobegin p0()； p1()； p2(); p3(); p4(); Coend ,i=0,1,2,3,4 Pi() think; SP(si, s(i+1) mod 5); eat; SV(si, s(i+1) mod 5); ,有两组并发进程：读者和写者，共享一个文件F，要求：允许多个读者同时执行读操作,任一写者在完成写操作之前不允许其它读者或写者工作, 写者执行写操作前，应让已有的写者和读者全部退出,用PV原语描述读者写着问题。,设互斥信号量Wmutex实现写者和读者，写者和写者互斥访问，其初值为1；设置一个整型变量Readcount表示正在读的进程数目，其初值为0，设置一个互斥信号量rmutex实现读者对Readcount 变量的互斥访问，其初值为1。 Semaphore Wmutex=1， rmutex =1； Int Readcount=0;,Main( ) cobegin Reader ()； writer ()； Coend ,Reader() P(rmutex); readcount +; if (readcount=1) P (Wmutex); V(rmutex); 读; P(rmutex); readcount -; if (readcount=0) V(Wmutex); V(rmutex); ;,writer () P(Wmutex); 写; V(Wmutex); ;,有5个批处理作业（A、B、C、D、E）分别于0，1，2，3，4时刻到达，估计的运行时间分别为2，4，6，8、10分钟，它们的优先数分别为1，2，3，4，5（1为最低优先级），对下面的 每种调度算法，分别计算作业的平均周转时间和平均带权周转时间。 1 最高优先级先 2 时间片轮转（时间片为2分钟）(把作业当成进程) 3 FCFS 4 短作业优先 5 高响应比优先,最高优先级先 执行顺序：ACEDB A的完成时间为2，周转时间为2-0=2，带权周转时间为2/2=1 B的完成时间为30，周转时间为30-1=29，带权周转时间为29/4 C的完成时间为8，周转时间为8-2=6，带权周转时间为6/6=1 D的完成时间为26，周转时间为26-3=23，带权周转时间为23/8 E的完成时间为18，周转时间为18-4=14，带权周转时间为14/10 平均周转时间为（2+29+6+23+14）/5=14.8 平均带权周转时间为(1+29/4+1+23/8+14/10)/5=2.705,时间片轮转法 执行顺序：ABCDEBCDECDEDE A的完成时间为2，周转时间为2-0=2，带权周转时间为2/2 B的完成时间为12，周转时间为12-1=11，带权周转时间为11/4 C的完成时间为20，周转时间为20-2=18，带权周转时间为18/6 D的完成时间为26，周转时间为26-3=23，带权周转时间为23/8 E的完成时间为30，周转时间为30-4=26，带权周转时间为26/10 平均周转时间为（2+11+18+23+26）/5=16 平均带权周转时间为(1+11/4+3+23/8+26/10)/5=2.445,FCFS 执行顺序：ABCDE A的完成时间为2，周转时间为2-0=2，带权周转时间为2/2=1 B的完成时间为6，周转时间为6-1=5，带权周转时间为5/4 C的完成时间为12，周转时间为12-2=10，带权周转时间为10/6 D的完成时间为20，周转时间为20-3=17，带权周转时间为17/8 E的完成时间为30，周转时间为30-4=26，带权周转时间为26/10 平均周转时间为（2+5+10+17+26）/5=12 平均带权周转时间为(1+5/4+10/6+17/8+26/10)/5=1.728,短作业优先 执行顺序：ABCDE A的完成时间为2，周转时间为2-0=2，带权周转时间为2/2=1 B的完成时间为6，周转时间为6-1=5，带权周转时间为5/4 C的完成时间为12，周转时间为12-2=10，带权周转时间为10/6 D的完成时间为20，周转时间为20-3=17，带权周转时间为17/8 E的完成时间为30，周转时间为30-4=26，带权周转时间为26/10 平均周转时间为（2+5+10+17+26）/5=12 平均带权周转时间为(1+5/4+10/6+17/8+26/10)/5=1.728,高响应比优先 执行顺序：ABCDE A的完成时间为2，周转时间为2-0=2，带权周转时间为2/2=1 B的完成时间为6，周转时间为6-1=5，带权周转时间为5/4 C的完成时间为12，周转时间为12-2=10，带权周转时间为10/6 D的完成时间为20，周转时间为20-3=17，带权周转时间为17/8 E的完成时间为30，周转时间为30-4=26，带权周转时间为26/10 平均周转时间为（2+5+10+17+26）/5=12 平均带权周转时间为(1+5/4+10/6+17/8+26/10)/5=1.728,在银行家算法中，若出现表2所示的资源分配情况，试问： 表2资源分配表,该状态是否安全？ 如果进程P2提出请求request(1,2,2,2)后，系统能否将资源分配给它。,利用安全性算法对此刻的资源分配情况进行分析，可得到如表所示的安全检测情况。 从表中可以看出，此时刻存在着一个安全序列P0,P3,P4,P1,P2,故该系统是安全的。,P2提出请求（1，2，2，2），按银行家算法检查： Request2(1,2,2,2)Need2(2,3,5,6) Request2(1,2,2,2)Available(1,6,2,2) 试分配并修改相应数据结构，由此形成的资源分配情况如图所示：,再利用安全性算法检查系统是否安全，可利用资源Available(0,4,0,0)已不能