操作系统习题分析.ppt

操作系统习题分析,总问题,概念要清楚、定义要准确 叙述要清楚、具体 解题过程要详细 有关PV操作的题必须编写程序，给出算法,第1章 补充作业,1、设在内存中有三道程序A、B和C，并按A、B、C的优先次序运行，其内部计算和I/O操作的时间如图1所示。若处理机调度程序每次进行程序状态转换的时间为2ms，请画出多道程序系统中在处理机调度程序管理下各程序状态转换的时间关系图，并计算出完成这三道程序共花多少时间？比单道运行节省了多少时间？,图1 各程序内部计算和I/O操作的时间,图2 各程序执行与状态转换的时间关系图,解：多道程序系统中，在处理机调度程序管理下各程序状态转换的时间关系图如图2所示。,单道系统中，三道程序共运行的时间为： T=60+2+30+2+40+2+50+2+20+2+50+2+70+2+50+2+40+2+30+2+20+2 =482 多道运行比单道运行节省时间为：482306=176,第3章 进程管理,教材 p83 2、6、7、8、9、10、11、13、14、15,第3章 进程管理,1.设有三个并发进程R、M、P，它们共享一个缓冲区。R负责从输入设备读信息，每读一个记录后，就把它存放在缓冲区中；M在缓冲区中加工读入的记录；P把加工后的记录打印输出。读入的记录经加工输出后，缓冲区又可存放下一个记录。试写出它们能正确执行的程序。,缓冲区,输入进程R,打印进程P,处理进程M,3.6 进程同步,计算进程PC ：反复地把每次计算结果放入缓冲区Buf中 打印进程PP ：将计算进程每次放入缓冲区Buf中的数据取出，通过打印机打印输出 缓冲区Buf ：一次只可放一个数据,例，共享一个缓冲区的合作进程,Begin Sc,Sp: semaphore; Sp=0; /*信号量Sp，表示缓冲区Buf 是否存放计算结果*/ Sc=1; /*信号量Sc，表示缓冲区Buf 是否为空*/ Cobegin Pc: While (计算未结束); /*计算进程*/ 计算； P(Sc); /*缓冲区是否为空？若非空，则等待*/ Buf计算结果； V(Sp); Pp: While (打印未完成); /*打印进程*/ P(Sp); /*缓冲区是否为数据？若无，则等待*/ 从缓冲区Buf取数据； V(Sc); 打印数据； Coend End,分析,缓冲区是临界资源，必须互斥访问 信号量empty：表示缓冲区是否为空，初值为1 信号量Sr：进程R是否已输入信息，初值Sr=0 信号量Sm：进程M是否已加工信息，初值Sm=0,begin empty, Sr, Sm, Sp : semaphore empty:=1; Sr:=0; Sm:=0 ; Cobegin Pr: Repeat 从输入设备读一个记录； P(empty); 将记录存入缓冲区； V(Sr); Until false Pm: Repeat P(Sr); 在缓冲区中加工记录； V(Sm); Until false,Pp: Repeat P(Sm); 从缓冲区取出一个记录； V(empty); 打印记录； Until false Coend end,第3章 进程管理,2.有一阅览室，读者进入时必须先在一张登记表上进行登记。该表为每一座位列出一个表目，包括座号、姓名。读者离开时撤消登记信息。阅览室有100个座位，试问： （1）为描述读者的动作，应编写几个程序，应该设置几个进程？进程和程序之间的对应关系如何？ （2）试用P、V操作描述这些进程间的同步算法。,分析,读者动作：登记、读书、撤消 座位总数：100 登记/撤消都需要在登记表修改信息，一次只能有一个读者对登记表进行访问 登记表是临界资源，必须互斥访问 一个读者一个进程 信号量的设置 S：用于读者互斥访问（登记/撤消）登记表，初值为1 Sn：表示空座位数，初值为100 每个座位设一个状态位：满/空（类似信箱通讯）,程 序,begin S, Sn : Semaphore; S:=1 ; Sn:=100; Cobegin process Reader i (i=1, 2, , n ） begin P(Sn); P(S) ; 选择标志为空的座位X； 登记； 置座位X的标志为满； V(S);,读书； P(S) 在登记表中查找座位X； 撤消登记信息； 置座位X的标志为空； V(Sn) V(S) end Coend 讨论并分析上述程序： 采用指针形式（类似生产者-消费者问题） 给每个座位设置一个信号量（类似哲学家就餐问题）,第3章 补充题,3. 桌上有一只盘子，每次只能放入一个水果。爸爸专向盘中放苹果，妈妈专向盘中放桔子，一个女儿专等吃盘中的苹果，一个儿子专等吃盘中的桔子。试用P、V操作写出他们能同步的程序。 分析： 信号量S：表示盘子是否为空，初值为1 信号量So：表示盘中是否有桔子，初值为0 信号量Sa：表示盘子是否有苹果，初值为0,程序,begin S, Sa, So : semaphore S=1; Sa=0; So=0; Cobegin father: Repeat P(S); 将苹果放入盘中； V(Sa); Until false mother: Repeat P(S); 将桔子放入盘中； V(So); Until false,daughter: Repeat P(Sa); 从盘中取出苹果； V(S); 吃苹果； Until false son: Repeat P(So); 从盘中取出桔子； V(S); 吃桔子； Until false Coend end,第3章 补充题,4、某大学军训正在进行实弹练习。现有一保管员负责管理枪支弹药，有A、B两组学生，A组学生每人都有一支枪，B组学生每人都备有足够的子弹，任一学生只要有枪和子弹就可以进行实弹练习。在打靶场有一个可以放一只枪或一发子弹的盒子，当盒中无物品时，保管员就可以任意放一支枪或一发子弹供学生取用。当盒中有学生所需材料时，每次允许一个学生从中取出自己所需的材料，材料取走后，保管员再放一件材料。 （1）试说明A、B两组学生、保管员之间的相互制约关系。 （2）应设置哪些信号量，它们的初值是什么？ （3）试用P、V写出他们并发执行的程序（类C或类PASCAL语言）。,解答,解： （1）这是一个生产者-消费者问题。 A、B两组学生是消费者，保管员是生产者，盒子是缓冲区，是一个临界资源。 它们之间的相互制约关系是：保管员与学生之间不仅要同步，而且保管员与A、B两组学生之间、以及A、B两组学生之间还要互斥。 （2）设置3个信号量如下： 公用信号量S：初值为1，表示盒子是否为空； 私用信号量Sgun：表示盒子中是否有一支枪，初值为0； 私用信号量Sbullet：表示盒子中是否有一发子弹，初值为0,程序如下：,Begin S, Sgun, Sbullet : semaphore S=1; /*表示盒子是否为空，初值为1*/ Sgun=0; /*表示盒子中是否有一支枪，初值为0*/ Sbullet=0; /*表示盒子中是否有一发子弹，初值为0*/ Cobegin Keeper： Repeat P(S); 将一支枪或一发子弹放入盒子中； If 放入的是一支枪 Then V(Sgun) Else V(Sbullet) fi Until false,Student Ai (i=1,2,) Repeat P(Sbullet); 从盒子中取出子弹； V(S); 打靶； Until false Student Bj (j=1,2,) Repeat P(Sgun); 从盒子中取出枪； V(S); 打靶； Until false Coend end,5、假定系统中有五个进程P0，P1，P2，P3，P4和三种类型的资源A，B，C，每种资源的数量分别为10，5，7，在T时刻的资源分配情况如表所示。 （1）T时刻系统是否为安全状态，若是，请给出安全序列。 （2）如果进程P4此时提出资源申请（3，3，1），系统能否将资源分配给它？为什么？,第3章 补充题,解： （1）进程的最大资源需求数减去当前进程已分配到的资源数就是进程仍需要的资源数。此时各进程的仍需资源数向量为,已知：系统的可用资源向量为W=（10， 5，7） 已分配的资源向量为P=（7，2，5） 则，系统的当前剩余资源向量为S=（3，3，2） 在T时刻系统存在如下进程执行序列，可以使进程顺利进行完毕，所以该状态是安全的，安全序列为P1、P3、P0、P4、P2。具体如下：,（2）如果进程P4此时提出资源申请（3，3，1），系统满足进程P4的请求，则系统的可用资源数变为（0，0，1）。而此时各进程的仍需资源数向量为：,这时系统的可用资源数（0，0，1）不能满足任何一个进程，系统处于不安全状态。 因此，系统不能将资源分配给进程P4。,P83 3.10,P62 经典生产者-消费者问题,经典生产者消费者问题,设生产者进程和消费者进程是互相等效的，其中，各生产者进程使用过程deposit(data)，各消费者使用的过程remove(data) 生产者-消费者问题是一个同步问题 消费者想接收数据时，缓冲区中至少有一个单元是满的 生产者想发送数据时，缓冲区中至少有一个单元是空的 生产者-消费者问题是一个互斥问题 缓冲区是临界资源,经典生产者消费者问题,设置信号量 公用信号量mutex：保证生产者进程和消费者进程之间的互斥；初值为1，表示没有进程进入临界区 私用信号量avail：生产者进程的私用信号量，表示可用缓冲区数，初值为n 私用信号量full：消费者进程的私用信号量，表示产品数目，初值为 0,生产者消费者进程描述,生产者进程,生产一种产品 P(avail) P(mutex) 产品送入缓冲区 V(full) V(mutex),消费者进程,P(full) P(mutex) 从缓冲区取一产品 V(avail) V(mutex) 消耗该产品,生产者指针P 消费者指针R,为什么要互斥访问缓冲区？,什么情况下，出现阻塞？,经典生产者消费者问题,设置信号量 公用信号量S：初值为1，表示没有进程进入临界区，用于实现进程互斥 私用信号量S0：表示产品数目，初值为0 私用信号量Sn：表示可用缓冲区数，初值为n,生产者消费者进程描述,生产者进程,生产一种产品 P(Sn) P(S) 产品送入缓冲区 V(S0) V(S),消费者进程,P(S0) P(S) 从缓冲区取一产品 V(Sn) V(S) 消耗该产品,Begin B:array0n-1 of integer; P, R: integer; S, Sn, S0: semaphore; P:=R:=0; S:=1; Sn:=n; S0 :=0; Cobegin Process Produce i (i=1, 2, ,m) Begin L1: produce a product P(Sn); P(S); BP:=product; P:=(P+1) mod n; V(S0); V(S);,go to L1 end Process consumer j (j=1, 2, ,k) Begin L2: P(S0); P(S); take a product from BR; R:=(R+1) mod n; V(Sn); V(S); consume go to L2 end Coend end,P83 3.10,解：设互斥信号量mutexn为缓冲区的公用信号量，初始值为1。 设信号量S1为生产者进程信号量，初始值为m。 设信号量S2为消费者信号量，初始值为0。 各生产者进程使用的过程Deposit(data)如下： Deposit(data) Begin P(S1) 选择第n个空缓冲区 P(mutexn) 送数据入第n个缓冲区 V(S2) V(mutexn) End,各消费者进程使用的过程Remove(data)如下： Remove(data) Begin P(S2) 选择一个已有数据的缓冲区k P(mutexk) 取出缓冲区k中的数据 V(S1) V(mutexk) End,P83 3.11,P61 例,P61 例，设进程PA和PB通过缓冲区队列传递数据(如图3.14)。 PA为发送进程， PB为接收进程。 PA发送数据时调用发送过程deposit(data)， PB接收数据时调用过程remove(data)。且数据的发送和接收过程满足如下条件： 在PA至少送一块数据入一个缓冲区之前， PB不可能从缓冲区中取出数据（假定数据块长等于缓冲区长度） PA往缓冲队列发送数据时，至少有一个缓冲区是空的 由PA发送的数据块在缓冲队列中按先进先出(FIFO)方式排列 描述发送进程deposit(data)和接收进程remove(data),图3.14 缓冲区队列,P83 3.11,解：由题可知，进程PA调用发送过程deposit(data)和进程 PB调用过程remove(data)必须同步执行，因此， 设： Bufempty为进程PA的私用信号量，初值Bufempty=n Buffull为进程PB的私用信号量，初值Buffull=0 则，过程deposit(data)和remove(data)描述如下：,P83 3.11,设：有两个缓冲区队列i=1、2，每个缓冲区队列有n个缓冲区。 bufi(k) 表示第i个缓冲队列的第k个缓冲区 bufempty0，buffull1为PA的私有信号量 buffull0，buffempty1是PB的私有信号量 bufempty0=bufempty1=n buffull0=buffull1=0 PA调用send(0,m)发送数据， receive(1,m)接收数据； PB调用send(1,m)发送数据， receive(0,m)接收数据；,发送过程 send(i,m) begin P(bufemptyi) FIFO方式选择一个空缓冲区k bufi(k)=m bufi(k)置满标记 V(buffulli) End,接收过程 Receive(i,m) begin P(buffulli) FIFO方式选择一个满缓冲区k m=bufi(k) bufi(k)置空标记 V(bufemptyi) end,P84 3.13（参考p72 例2）,#include Main() int i,r,P1,P2,fd3; char buf50,s50; pipe(fd); while(P1=fork()=-1); if(P1=0) lockf(fd1,1,0); sprintf(buf,”child process P1 is sending messages!n”); printf(“child process P1!n”); write(fd1,buf,50); sleep(5); lockf(fd1,0,0); exit(0); ,Else while(P2=fork()=-1); if(P2=0) lockf(fd1,1,0); sprintf(buf,”child process P2 is sending messages!n”); printf(“child process P2!n”); write(fd1,buf,50); sleep(5); lockf(fd1,0,0); exit(0); ,Else while(P3=fork()=-1); if(P3=0) lockf(fd1,1,0); sprintf(buf,”child process P3 is sending messages!n”); printf(“child process P3!n”); write(fd1,buf,50); sleep(5); lockf(fd1,0,0); exit(0); ,Wait(0); If(r=read(fd0,s,50)=-1) Printf(“cant read pipen”); Else printf(“%sn”,s); Wait(0); If(r=read(fd0,s,50)=-1) Printf(“cant read pipen”); Else printf(“%sn”,s); Wait(0); If(r=read(fd0,s,50)=-1) Printf(“cant read pipen”); Else printf(“%sn”,s); Exit(0); ,3.14 哲学家就餐问题(习题p15),有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子 每个哲学家的行为是思考，感到饥饿，然后吃通心粉 为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子,Repeat 思考； 取forki ;/*取左边筷子*/ 取fork(i+1) mod 5；/*取右边筷子*/ 进食； 放forki;/*放左边筷子*/ 放fork(i+1) mod 5；/*放右边筷子*/ Until false;,方法：为每根筷子单独设置一个信号量，取筷子执行P操作，放筷子执行V操作 Var chopstick: array04 of semaphore; For i=0 to 4 chopsticki=1 Next i Pi: Repeat think; P(chopsticki); P(chopsticki+1 mod 5); eat; V(chopsticki); V(chopsticki+1 mod 5); Until false;,存在问题,上述方法简单，并能保证任何时候均不存在两个相邻的哲学家同时在吃饭。 但由于进程的并发执行与CPU的调度问题，可能使得每个哲学家都只能拿到了自己左边的筷子，那么这一组进程就会发生死锁现象。,为防止死锁发生可采取的措施： 最多允许4个哲学家同时坐在桌子周围 仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（） 给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之 为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿,state:array04 of (思考，饥饿，进食）； ph: array04 of semaphore; mutex:semaphore; i:04;,Procedure test(i:=04); begin if (state i = 饥饿) And (state(i-1)mod5进食) And (state(i+1)mod5进食) then state i =进食 V(ph i ) fi end,Procedure philosopher(i: 04) Begin Repeat 思考； statei :=饥饿； P(mutex); test(i); V(mutex); P(ph i ); 拿左筷子； 拿右筷子； 进食； 放左筷子； 放右筷子；,P(mutex) state i :=思考； test(i-1mod5); tset(i+1mod5); V(mutex); until fales End state I =思考 ph I =0 mutex=1,第4章 处理机调度,P108 习题2、4、5、6,第4章 处理机调度,4.6 假设有4道作业，它们的提交时刻和执行时间由下表给出：,计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。,1.先来先服务(FCFS)调度算法,将用户作业和就绪进程按提交顺序或变为就绪状态的先后排队，按照先来先服务的方式调度 对于作业调度，该算法就是从后备作业队列中（按进入的时间顺序排队）选择队首一个或几个作业，调入内存，创建进程，放入就绪队列 对于进程调度，该算法就是从就绪队列中选择一个最先进入队列的进程，将CPU分配于它 表面上，FCFS算法是公平的。但对于执行时间较短的作业或进程，当它们处于某些执行时间很长的作业或进程之后到达，则它们将等待很长的时间,采用先来先服务调度算法时的周转时间和带权周转时间如下表所示，计算可得： 平均周转时间为：T=157m=2.6167h 平均带权周转时间为：W=4.8075 它们的调度顺序是：作业1作业2作业3作业4,先来先服务算法（FCFS）,最短作业优先法(SJF),方法：选择那些估计需要执行时间最短的作业投入执行 优点：系统在同一时间内处理的作业个数最多，吞吐量大于其他调度方式 问题： SJF需要事先知道或至少需要估计每个作业所需的处理机时间 只要不断的有短作业进入系统，就有可能使长作业长期得不到运行而“饿死” SJF 偏向短作业，不利于分时系统（由于不可抢占性）,采用最短作业优先法时的周转时间和带权周转时间如下表所示（情况1：将作业收集成一批再处理），计算可得： 平均周转时间为：T=123m=2.05h 平均带权周转时间为：W=1.8875 它们的调度顺序是：作业4作业3作业2作业1,最短作业优先法（SJF）,采用最短作业优先法时的周转时间和带权周转时间如下表所示（情况2 ：有作业就执行），计算可得： 平均周转时间为：T=123m=2.05h 平均带权周转时间为：W=1.8875 它们的调度顺序是：作业1 作业4作业3作业2,最短作业优先法（SJF）,第5章 存储管理,p144 习题2、3、4、6、9、10、11、15、16、19,补充作业,1、存储管理系统中，假定某进程分得三个内存块，其页面走向为以下序列： 5、0、1、2、1、3、2、4、2、3、0、3、2、1、2、0、1、5、0、1 试用先进先出（FIFO）、最近最久未使用（LRU）和理想置换算法分别计算程序访问过程中所发生的缺页次数和缺页率。,FIFO算法的缺页中断次数F=11，缺页率f=11/20=55%,LRU算法的缺页中断次数F=10，缺页率f=10/20=50%,理想置换算法的缺页中断次数F=9 缺页率f=9/20=45%,补充题,2、某系统采用请求分页存储管理，页长为2 KB（即2048B），某作业的页表如下所示。请简述执行指令 60 LOAD A, 5168 的地址变换过程。,解：执行指令60 LOAD A,5168的地址变换过程为： （1）取指令：首先根据该指令的逻辑地址60，得到相应的逻辑页式地址为（0，60），然后查页表得到其物理块为3，计算出物理地址为： 32048+606204 所以，从6204单元中取出指令执行。 （2）取数据：首先根据数据的逻辑地址5168，得到相应的逻辑页式地址为（2，1072），然后查页表得到其物理块为8，计算出物理地址为： 82048+107217456 所以，从174