操作系统习题分析课件

《操作系统》习题分析《操作系统》习题分析1总问题概念要清楚、定义要准确叙述要清楚、具体解题过程要详细有关PV操作的题必须编写程序，给出算法总问题概念要清楚、定义要准确2第1章补充作业1、设在内存中有三道程序A、B和C，并按A、B、C的优先次序运行，其内部计算和I/O操作的时间如图1所示。若处理机调度程序每次进行程序状态转换的时间为2ms，请画出多道程序系统中在处理机调度程序管理下各程序状态转换的时间关系图，并计算出完成这三道程序共花多少时间？比单道运行节省了多少时间？图1各程序内部计算和I/O操作的时间

第1章补充作业1、设在内存中有三道程序A、B和C，并按A、3图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多道运行比单道运行节省时间为：482－306=176图2各程序执行与状态转换的时间关系图解：多4第3章进程管理教材p832、6、7、8、9、10、11、13、14、15第3章进程管理教材p835第3章进程管理1.设有三个并发进程R、M、P，它们共享一个缓冲区。R负责从输入设备读信息，每读一个记录后，就把它存放在缓冲区中；M在缓冲区中加工读入的记录；P把加工后的记录打印输出。读入的记录经加工输出后，缓冲区又可存放下一个记录。试写出它们能正确执行的程序。缓冲区输入进程R打印进程P处理进程M第3章进程管理1.设有三个并发进程R、M、P，它们共63.6进程同步缓冲区计算进程PC打印进程PP计算进程PC

：反复地把每次计算结果放入缓冲区Buf中打印进程PP

：将计算进程每次放入缓冲区Buf中的数据取出，通过打印机打印输出缓冲区Buf

：一次只可放一个数据例，共享一个缓冲区的合作进程3.6进程同步缓冲区计算进程PC打印进程PP计算进程PC7BeginSc,Sp:semaphore;Sp=0;/*信号量Sp，表示缓冲区Buf

是否存放计算结果*/Sc=1;/*信号量Sc，表示缓冲区Buf是否为空*/CobeginPc:While(计算未结束);/*计算进程*/{计算；P(Sc);/*缓冲区是否为空？若非空，则等待*/Buf←计算结果；V(Sp);}Pp:While(打印未完成);/*打印进程*/{P(Sp);/*缓冲区是否为数据？若无，则等待*/从缓冲区Buf取数据；V(Sc);打印数据；}CoendEndBegin8分析缓冲区是临界资源，必须互斥访问信号量empty：表示缓冲区是否为空，初值为1信号量Sr：进程R是否已输入信息，初值Sr=0信号量Sm：进程M是否已加工信息，初值Sm=0分析缓冲区是临界资源，必须互斥访问9beginempty,Sr,Sm,Sp:semaphoreempty:=1;Sr:=0;Sm:=0;CobeginPr:Repeat从输入设备读一个记录；P(empty);将记录存入缓冲区；V(Sr);UntilfalsePm:RepeatP(Sr);在缓冲区中加工记录；V(Sm);Untilfalsebeginempty,Sr,Sm,Sp:sem10

Pp:RepeatP(Sm);从缓冲区取出一个记录；V(empty);打印记录；UntilfalseCoendendPp:Repeat11第3章进程管理2.有一阅览室，读者进入时必须先在一张登记表上进行登记。该表为每一座位列出一个表目，包括座号、姓名。读者离开时撤消登记信息。阅览室有100个座位，试问：（1）为描述读者的动作，应编写几个程序，应该设置几个进程？进程和程序之间的对应关系如何？（2）试用P、V操作描述这些进程间的同步算法。第3章进程管理2.有一阅览室，读者进入时必须先在一张登记12分析读者动作：登记、读书、撤消座位总数：100登记/撤消都需要在登记表修改信息，一次只能有一个读者对登记表进行访问登记表是临界资源，必须互斥访问一个读者一个进程信号量的设置

S：用于读者互斥访问（登记/撤消）登记表，初值为1Sn：表示空座位数，初值为100每个座位设一个状态位：满/空（类似信箱通讯）分析读者动作：登记、读书、撤消13程序beginS,Sn:Semaphore;S:=1;Sn:=100;CobeginprocessReaderi(i=1,2,……,n）beginP(Sn);P(S);选择标志为空的座位X；登记；置座位X的标志为满；V(S);程序beginS,Sn:Semaphore;14

读书；P(S)在登记表中查找座位X；撤消登记信息；置座位X的标志为空；V(Sn)V(S)endCoend讨论并分析上述程序：采用指针形式（类似生产者-消费者问题）给每个座位设置一个信号量（类似哲学家就餐问题）读书；15第3章补充题3.桌上有一只盘子，每次只能放入一个水果。爸爸专向盘中放苹果，妈妈专向盘中放桔子，一个女儿专等吃盘中的苹果，一个儿子专等吃盘中的桔子。试用P、V操作写出他们能同步的程序。分析：信号量S：表示盘子是否为空，初值为1信号量So：表示盘中是否有桔子，初值为0信号量Sa：表示盘子是否有苹果，初值为0第3章补充题3.桌上有一只盘子，每次只能放入一个水果。16程序beginS,Sa,So:semaphoreS=1;Sa=0;So=0;Cobeginfather:RepeatP(S);将苹果放入盘中；V(Sa);Untilfalsemother:RepeatP(S);将桔子放入盘中；V(So);Untilfalse程序begin17

daughter:RepeatP(Sa);从盘中取出苹果；V(S);吃苹果；Untilfalseson:RepeatP(So);从盘中取出桔子；V(S);吃桔子；UntilfalseCoendenddaughter:Repeat18第3章补充题4、某大学军训正在进行实弹练习。现有一保管员负责管理枪支弹药，有A、B两组学生，A组学生每人都有一支枪，B组学生每人都备有足够的子弹，任一学生只要有枪和子弹就可以进行实弹练习。在打靶场有一个可以放一只枪或一发子弹的盒子，当盒中无物品时，保管员就可以任意放一支枪或一发子弹供学生取用。当盒中有学生所需材料时，每次允许一个学生从中取出自己所需的材料，材料取走后，保管员再放一件材料。（1）试说明A、B两组学生、保管员之间的相互制约关系。（2）应设置哪些信号量，它们的初值是什么？（3）试用P、V写出他们并发执行的程序（类C或类PASCAL语言）。第3章补充题4、某大学军训正在进行实弹练习。现有一保管员19解答解：（1）这是一个生产者-消费者问题。A、B两组学生是消费者，保管员是生产者，盒子是缓冲区，是一个临界资源。它们之间的相互制约关系是：保管员与学生之间不仅要同步，而且保管员与A、B两组学生之间、以及A、B两组学生之间还要互斥。（2）设置3个信号量如下：公用信号量S：初值为1，表示盒子是否为空；私用信号量Sgun：表示盒子中是否有一支枪，初值为0；私用信号量Sbullet：表示盒子中是否有一发子弹，初值为0解答解：20程序如下：BeginS,Sgun,Sbullet:semaphoreS=1;/*表示盒子是否为空，初值为1*/Sgun=0;/*表示盒子中是否有一支枪，初值为0*/Sbullet=0;/*表示盒子中是否有一发子弹，初值为0*/CobeginKeeper：RepeatP(S);将一支枪或一发子弹放入盒子中；If放入的是一支枪ThenV(Sgun)ElseV(Sbullet)fiUntilfalse程序如下：Begin21StudentAi(i=1,2,…)RepeatP(Sbullet);从盒子中取出子弹；V(S);打靶；UntilfalseStudentBj(j=1,2,…)RepeatP(Sgun);从盒子中取出枪；V(S);打靶；UntilfalseCoendendStudentAi(i=1,2,…)225、假定系统中有五个进程{P0，P1，P2，P3，P4}和三种类型的资源{A，B，C}，每种资源的数量分别为10，5，7，在T时刻的资源分配情况如表所示。

（1）T时刻系统是否为安全状态，若是，请给出安全序列。

（2）如果进程P4此时提出资源申请（3，3，1），系统能否将资源分配给它？为什么？资源进程最大需求矩阵M分配矩阵RABCABCP0P1P2P3P4753322902222433010200302211002第3章补充题5、假定系统中有五个进程{P0，P1，P2，P3，P4}和三23解：（1）进程的最大资源需求数减去当前进程已分配到的资源数就是进程仍需要的资源数。此时各进程的仍需资源数向量为进程仍需资源数QP0743P1122P2600P3011P4431解：进程仍需资源数QP07424已知：系统的可用资源向量为W=（10，5，7）已分配的资源向量为P=（7，2，5）则，系统的当前剩余资源向量为S=（3，3，2）在T时刻系统存在如下进程执行序列，可以使进程顺利进行完毕，所以该状态是安全的，安全序列为P1、P3、P0、P4、P2。具体如下：进程系统可用资源数SP1完成后：5，3，2P3完成后：7，4，3P0完成后：7，5，3P4完成后：7，5，5P2完成后：10，5，7已知：系统的可用资源向量为W=（10，5，7）进程系统可用25（2）如果进程P4此时提出资源申请（3，3，1），系统满足进程P4的请求，则系统的可用资源数变为（0，0，1）。而此时各进程的仍需资源数向量为：进程仍需资源数P0743P1122P2600P3011P4100这时系统的可用资源数（0，0，1）不能满足任何一个进程，系统处于不安全状态。因此，系统不能将资源分配给进程P4。（2）如果进程P4此时提出资源申请（3，3，1），系统满足进26P833.10P62经典生产者-消费者问题P833.10P62经典生产者-消费者问题27经典生产者—消费者问题设生产者进程和消费者进程是互相等效的，其中，各生产者进程使用过程deposit(data)，各消费者使用的过程remove(data)生产者-消费者问题是一个同步问题消费者想接收数据时，缓冲区中至少有一个单元是满的生产者想发送数据时，缓冲区中至少有一个单元是空的生产者-消费者问题是一个互斥问题缓冲区是临界资源经典生产者—消费者问题设生产者进程和消费者进程是互相等效的，28经典生产者—消费者问题设置信号量公用信号量mutex：保证生产者进程和消费者进程之间的互斥；初值为1，表示没有进程进入临界区私用信号量avail：生产者进程的私用信号量，表示可用缓冲区数，初值为n私用信号量full：消费者进程的私用信号量，表示产品数目，初值为0经典生产者—消费者问题设置信号量29生产者—消费者进程描述生产者进程生产一种产品P(avail)P(mutex)产品送入缓冲区V(full)V(mutex)消费者进程P(full)P(mutex)从缓冲区取一产品V(avail)V(mutex)消耗该产品生产者—消费者进程描述生产者进程生产一种产品消费者进程P(f30操作系统习题分析课件31生产者指针P

消费者指针R

有界缓冲区初始状态RP…

I12J……n为什么要互斥访问缓冲区？…

I12J…中间状态RP…n什么情况下，出现阻塞？生产者指针P消费者指针R有界缓冲区初始状态32经典生产者—消费者问题设置信号量公用信号量S：初值为1，表示没有进程进入临界区，用于实现进程互斥私用信号量S0：表示产品数目，初值为0私用信号量Sn：表示可用缓冲区数，初值为n经典生产者—消费者问题设置信号量33生产者—消费者进程描述生产者进程生产一种产品P(Sn)P(S)产品送入缓冲区V(S0)V(S)消费者进程P(S0)P(S)从缓冲区取一产品V(Sn)V(S)消耗该产品生产者—消费者进程描述生产者进程生产一种产品消费者进程P(S34BeginB:array[0..n-1]ofinteger;P,R:integer;S,Sn,S0:semaphore;P:=R:=0;S:=1;Sn:=n;S0:=0;CobeginProcessProducei(i=1,2,…,m)BeginL1:produceaproductP(Sn);P(S);B[P]:=product;P:=(P+1)modn;V(S0);V(S);Begin35

gotoL1endProcessconsumerj(j=1,2,…,k)BeginL2:P(S0);P(S);takeaproductfromB[R];R:=(R+1)modn;V(Sn);V(S);consumegotoL2endCoendendgotoL136P833.10解：设互斥信号量mutex[n]为缓冲区的公用信号量，初始值为1。设信号量S1为生产者进程信号量，初始值为m。设信号量S2为消费者信号量，初始值为0。各生产者进程使用的过程Deposit(data)如下：Deposit(data) Begin P(S1) 选择第n个空缓冲区 P(mutex[n]) 送数据入第n个缓冲区 V(S2)V(mutex[n])EndP833.10解：设互斥信号量mutex[n]为缓冲区的37各消费者进程使用的过程Remove(data)如下：Remove(data) Begin P(S2) 选择一个已有数据的缓冲区kP(mutex[k]) 取出缓冲区k中的数据 V(S1) V(mutex[k]) End各消费者进程使用的过程Remove(data)如下：38P833.11P61例P833.11P61例39P61例，设进程PA和PB通过缓冲区队列传递数据(如图3.14)。PA为发送进程，PB为接收进程。PA发送数据时调用发送过程deposit(data)，PB接收数据时调用过程remove(data)。且数据的发送和接收过程满足如下条件：在PA至少送一块数据入一个缓冲区之前，PB不可能从缓冲区中取出数据（假定数据块长等于缓冲区长度）PA往缓冲队列发送数据时，至少有一个缓冲区是空的由PA发送的数据块在缓冲队列中按先进先出(FIFO)方式排列描述发送进程deposit(data)和接收进程remove(data)图3.14缓冲区队列P833.11P61例，设进程PA和PB通过缓冲区队列传递数据(如图340解：由题可知，进程PA调用发送过程deposit(data)和进程PB调用过程remove(data)必须同步执行，因此，设：Bufempty为进程PA的私用信号量，初值Bufempty=nBuffull为进程PB的私用信号量，初值Buffull=0则，过程deposit(data)和remove(data)描述如下：解：由题可知，进程PA调用发送过程deposit(data)41操作系统习题分析课件42操作系统习题分析课件43P833.11设：有两个缓冲区队列i=1、2，每个缓冲区队列有n个缓冲区。buf[i](k)表示第i个缓冲队列的第k个缓冲区bufempty[0]，buffull[1]为PA的私有信号量buffull[0]，buffempty[1]是PB的私有信号量bufempty[0]=bufempty[1]=nbuffull[0]=buffull[1]=0PA调用send(0,m)发送数据，receive(1,m)接收数据；PB调用send(1,m)发送数据，receive(0,m)接收数据；P833.11设：有两个缓冲区队列i=1、2，每个缓冲区44发送过程send(i,m)begin P(bufempty[i]) FIFO方式选择一个空缓冲区k buf[i](k)=m buf[i](k)置满标记 V(buffull[i])End发送过程45接收过程Receive(i,m)begin P(buffull[i]) FIFO方式选择一个满缓冲区k m=buf[i](k) buf[i](k)置空标记 V(bufempty[i])end接收过程46P843.13（参考p72例2）#include<stdio.h>Main(){ inti,r,P1,P2,fd[3]; charbuf[50],s[50]; pipe(fd); while((P1=fork())==-1); if(P1==0){ lockf(fd[1],1,0); sprintf(buf,”childprocessP1issendingmessages!\n”); printf(“childprocessP1!\n”); write(fd[1],buf,50); sleep(5); lockf(fd[1],0,0); exit(0); }P843.13（参考p72例2）#include<st47 Else{ while((P2=fork())==-1); if(P2==0){ lockf(fd[1],1,0); sprintf(buf,”childprocessP2issendingmessages!\n”); printf(“childprocessP2!\n”); write(fd[1],buf,50); sleep(5); lockf(fd[1],0,0); exit(0); } Else{48 Else{ while((P3=fork())==-1); if(P3==0){ lockf(fd[1],1,0); sprintf(buf,”childprocessP3issendingmessages!\n”); printf(“childprocessP3!\n”); write(fd[1],buf,50); sleep(5); lockf(fd[1],0,0); exit(0); } Else{49 Wait(0); If(r=read(fd[0],s,50)==-1) Printf(“can’treadpipe\n”); Elseprintf(“%s\n”,s); Wait(0); If(r=read(fd[0],s,50)==-1) Printf(“can’treadpipe\n”); Elseprintf(“%s\n”,s);Wait(0); If(r=read(fd[0],s,50)==-1) Printf(“can’treadpipe\n”); Elseprintf(“%s\n”,s); Exit(0); } }} Wait(0);503.14哲学家就餐问题(习题p15)

有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子每个哲学家的行为是思考，感到饥饿，然后吃通心粉为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子3.14哲学家就餐问题(习题p15) 有五个哲学51Repeat

思考；取fork[i];/*取左边筷子*/取fork[(i+1)mod5]；/*取右边筷子*/进食；放fork[i];/*放左边筷子*/放fork[(i+1)mod5]；/*放右边筷子*/Untilfalse;Repeat52方法：为每根筷子单独设置一个信号量，取筷子执行P操作，放筷子执行V操作Varchopstick:array[0..4]ofsemaphore;Fori=0to4chopstick[i]=1NextiPi:Repeatthink;P(chopstick[i]);P(chopstick[i+1mod5]);eat;V(chopstick[i]);V(chopstick[i+1mod5]);Untilfalse;方法：为每根筷子单独设置一个信号量，取筷子执行P操作，放筷子53存在问题上述方法简单，并能保证任何时候均不存在两个相邻的哲学家同时在吃饭。但由于进程的并发执行与CPU的调度问题，可能使得每个哲学家都只能拿到了自己左边的筷子，那么这一组进程就会发生死锁现象。存在问题上述方法简单，并能保证任何时候均不存54

为防止死锁发生可采取的措施：最多允许4个哲学家同时坐在桌子周围仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（）给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿 为防止死锁发生可采取的措施：55state:array[0..4]of(思考，饥饿，进食）；ph:array[0..4]ofsemaphore;mutex:semaphore;i:0..4;state:array[0..4]of56Proceduretest(i:=0…4);beginif(state[i]=饥饿)And(state[(i-1)mod5]<>进食)And(state[(i+1)mod5]<>进食)thenstate[i]=进食V(ph[i])fiendProceduretest(i:=0…4);57Procedurephilosopher(i:0～4)BeginRepeat

思考；state[i]:=饥饿；P(mutex);test(i);V(mutex);P(ph[i]);

拿左筷子；拿右筷子；进食；放左筷子；放右筷子；Procedurephilosopher(i:0～4)58P(mutex)state[i]:=思考；test([i-1]mod5);tset([i+1]mod5);V(mutex);untilfalesEndstate[I]=思考ph[I]=0mutex=1P(mutex)59第4章处理机调度P108习题2、4、5、6第4章处理机调度P108习题2、4、5、660第4章处理机调度4.6假设有4道作业，它们的提交时刻和执行时间由下表给出：作业号提交时刻/小时执行时间/小时110:002210:201310:400.5410:500.3计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。第4章处理机调度4.6假设有4道作业，它们的提交时刻611.先来先服务(FCFS)调度算法将用户作业和就绪进程按提交顺序或变为就绪状态的先后排队，按照先来先服务的方式调度

对于作业调度，该算法就是从后备作业队列中（按进入的时间顺序排队）选择队首一个或几个作业，调入内存，创建进程，放入就绪队列对于进程调度，该算法就是从就绪队列中选择一个最先进入队列的进程，将CPU分配于它表面上，FCFS算法是公平的。但对于执行时间较短的作业或进程，当它们处于某些执行时间很长的作业或进程之后到达，则它们将等待很长的时间1.先来先服务(FCFS)调度算法将用户作业和就绪进程按提交62

采用先来先服务调度算法时的周转时间和带权周转时间如下表所示，计算可得：平均周转时间为：T=157m=2.6167h平均带权周转时间为：W=4.8075它们的调度顺序是：作业1→作业2→作业3→作业4作业号提交时间Tin执行时间Tr开始时间TS结束时间Tc周转时间T(m)带权周转时间W110:002(120)10:0012:00T1=120(2h)WA=1210:201(60)12:0013:00T2=160(2.67h)WB=2.67310:400.5(30)13:0013:30T3=170(2.83h)WC=5.67410:500.3(18)13:3013:48T4=178(2.97h)WD=9.89平均T=157m=2.6167hW=4.8075

先来先服务算法（FCFS）

采用先来先服务调度算法时的周转时间和带权周转时63最短作业优先法(SJF)方法：选择那些估计需要执行时间最短的作业投入执行优点：系统在同一时间内处理的作业个数最多，吞吐量大于其他调度方式问题：SJF需要事先知道或至少需要估计每个作业所需的处理机时间只要不断的有短作业进入系统，就有可能使长作业长期得不到运行而“饿死”SJF偏向短作业，不利于分时系统（由于不可抢占性）最短作业优先法(SJF)方法：选择那些估计需要执行时间最短的64

采用最短作业优先法时的周转时间和带权周转时间如下表所示（情况1：将作业收集成一批再处理），计算可得：平均周转时间为：T=123m=2.05h平均带权周转时间为：W=1.8875它们的调度顺序是：作业4→作业3→作业2→作业1作业号提交时间Tin执行时间Tr开始时间TS结束时间Tc周转时间T(m)带权周转时间W110:002(120)12:3814:38T1=278W1=2.3167210:201(60)11:3812:38T2=138W2=2.3310:400.5(30)11:0811:38T3=58W3=1.93410:500.3(18)10:5011:08T4=18W4=1平均T=123m=2.05hW=1.8875最短作业优先法（SJF）

采用最短作业优先法时的周转时间和带权周转时间如65

采用最短作业优先法时的周转时间和带权周转时间如下表所示（情况2：有作业就执行），计算可得：平均周转时间为：T=123m=2.05h平均带权周转时间为：W=1.8875它们的调度顺序是：作业1→作业4→作业3→作业2作业号提交时间Tin执行时间Tr开始时间TS结束时间Tc周转时间T(m)带权周转时间W110:002(120)10:0012:00T1=120(2h)W1=1210:201(60)12:4813:48T2=208(3.47h)W2=3.467310:400.5(30)12:1812:48T3=128(2.13h)W3=4.267410:500.3(18)12:0012:18T4=88(1.46h)W4=4.889平均T=136m=2.265hW=3.4057最短作业优先法（SJF）

采用最短作业优先法时的周转时间和带权周转时间如66第5章存储管理p144习题2、3、4、6、9、10、11、15、16、19第5章存储管理p14467补充作业1、存储管理系统中，假定某进程分得三个内存块，其页面走向为以下序列：5、0、1、2、1、3、2、4、2、3、0、3、2、1、2、0、1、5、0、1试用先进先出（FIFO）、最近最久未使用（LRU）和理想置换算法分别计算程序访问过程中所发生的缺页次数和缺页率。补充作业1、存储管理系统中，假定某进程分得三个内存块，其页面68走向50121324230321201501页150121324230321201501页25012132423032120150页3500213342203312015缺页××××√×√×√√×√√×√×√×√√走向50121324230321201501页150122334440021111500页25011223334402222155页3500112223340000211缺页××××√×√×√√×√××√√√××√FIFO算法的缺页中断次数F=11，缺页率f=11/20=55%

LRU算法的缺页中断次数F=10，缺页率f=10/20=50%

走向50121324230321201501页150121369走向50121324230321201501页150122334440001111555页25011223333330000111页3500002222222222000缺页√√√√√√√√√√√理想置换算法的缺页中断次数F=9缺页率f=9/20=45%

走向50121324230321201501页150122370补充题2、某系统采用请求分页存储管理，页长为2KB（即2048B），某作业的页表如下所示。请简述执行指令60LOADA,5168的地址变换过程。358补充题2、某系统采用请求分页存储管理，页长为2KB（即2071解：执行指令60LOADA,5168的地址变换过程为：（1）取指令：首先根据该指令的逻辑地址60，得到相应的逻辑页式地址为（0，60），然后查页表得到其物理块为3，计算出物理地址为：3×2048+60＝6204所以，从6204单元中取出指令执行。（2）取数据：首先根据数据的逻辑地址5168，得到相应的逻辑页式地址为（2，1072），然后查页表得到其物理块为8，计算出物理地址为：8×2048+1072＝17456所以，从17456单元中取出数据，放入寄存器A中。具体来说，该指令的执行过程是：首先从内存的6204单元取指令，然后再从17456单元取数据，放入寄存器A中。解：执行指令60LOADA,5168的地址变换过程为72补充作业3．在一个系统中采用动态分区法管理内存，假定内存中按地址递增顺序依次有5个空闲区，如表1所示。现有4道作业J1、J2、J3、J4依次要进入内存，它们各需要的内存大小分别为3KB、11KB、98KB、44KB。试分别用最先适应法和最佳适应法进行分配，给出各个作业的分配情况与最终的可用空闲区情况。补充作业3．在一个系统中采用动态分区法管理内存，假定内存中按73表1可用空闲区表

区号分区长度起始地址113K70K25K100K3198K130K448K480K525K600K表1可用空闲区表区号分区长度起始地址113K70K2574解：

（1）对于最先适应法，可用分区表与作业请求表如表1、2所示：表1可用分区表区号分区长度起始地址113K70K25K100K3198K130K448K480K525K600K作业号请求长度J13KJ211KJ398KJ444K表2作业请求表解：

（1）对于最先适应法，可用分区表与作业请求表如表1、275系统分配过程如下：对于J1，系统从分区1中划出3KB分配给J1，分区1还剩下10KB；对于J2，系统从分区3中划出11KB分配给J2，分区3还剩下187KB；对于J3，系统从分区3中划出98KB分配给J3，分区3还剩下89KB；对于J4，系统从分区3中划出44KB分配给J4，分区3还剩下45KB；因此，每个作业都分配到所需要的内存空间，此时系统中的可用分区如表3所示，作业分配情况如表4所示。系统分配过程如下：76表3可用分区表区号分区长度起始地址110K73K25K100K345K283K448K480K525K600K作业号作业长度首地址J13K70KJ211K130KJ398K141KJ444K239K表4作业分配情况表表3可用分区表区号分区长度起始地址110K73K25K177（2）对于最佳适应法，可用分区表与作业请求表如表5、6所示：表5可用分区表区号分区长度起始地址25K100K113K70K525K600K448K480K3198K130K作业号请求长度J13KJ211KJ398KJ444K表6作业请求表（2）对于最佳适应法，可用分区表与作业请求表如表5、6所示：78系统分配过程如下：对于J1，系统从分区2中划出3KB分配给J1，分区2还剩下2KB；对于J2，系统从分区1中划出11KB分配给J2，分区1还剩下2KB；对于J3，系统从分区3中划出98KB分配给J3，分区3还剩下100KB；对于J4，系统从分区4中划出44KB分配给J4，分区4还剩下4KB；因此，每个作业都分配到所需要的内存空间，此时系统中的可用分区如表7所示，作业分配情况如表8所示。系统分配过程如下：79表7可用分区表区号分区长度起始地址22K103K12K81K44K524K525K600K3100K228K作业号作业长度首地址J13K100KJ211K70KJ398K130KJ444K480K表8作业分配情况表表7可用分区表区号分区长度起始地址22K103K12K880第8章文件系统p221习题3、7、8、9、10、13第8章文件系统p22181第8章补充题1、某系统磁盘空间使用“空间块成组链接法”进行管理（每组50块）（1）通过图1所示的当前状态，为某文件分配4个空闲块。请写出该文件分配到的磁盘块号，并图示出分配后有关表的内容及相互关系。（2）某文件刚删除，可回收5个物理块109、110、136、137、148。结合图2，给出回收后的有关表格和磁盘块结构图。第8章补充题1、某系统磁盘空间使用“空间块成组链接法”进82操作系统习题分析课件83答：（1）该文件分配了99、112、66、78四个物理块。答：（1）该文件分配了99、112、66、78四个物理块。84第9章设备管理p245习题2、3、4、5、6、7、8、11、15第9章设备管理p24585《操作系统》习题分析《操作系统》习题分析86总问题概念要清楚、定义要准确叙述要清楚、具体解题过程要详细有关PV操作的题必须编写程序，给出算法总问题概念要清楚、定义要准确87第1章补充作业1、设在内存中有三道程序A、B和C，并按A、B、C的优先次序运行，其内部计算和I/O操作的时间如图1所示。若处理机调度程序每次进行程序状态转换的时间为2ms，请画出多道程序系统中在处理机调度程序管理下各程序状态转换的时间关系图，并计算出完成这三道程序共花多少时间？比单道运行节省了多少时间？图1各程序内部计算和I/O操作的时间

第1章补充作业1、设在内存中有三道程序A、B和C，并按A、88图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多道运行比单道运行节省时间为：482－306=176图2各程序执行与状态转换的时间关系图解：多89第3章进程管理教材p832、6、7、8、9、10、11、13、14、15第3章进程管理教材p8390第3章进程管理1.设有三个并发进程R、M、P，它们共享一个缓冲区。R负责从输入设备读信息，每读一个记录后，就把它存放在缓冲区中；M在缓冲区中加工读入的记录；P把加工后的记录打印输出。读入的记录经加工输出后，缓冲区又可存放下一个记录。试写出它们能正确执行的程序。缓冲区输入进程R打印进程P处理进程M第3章进程管理1.设有三个并发进程R、M、P，它们共913.6进程同步缓冲区计算进程PC打印进程PP计算进程PC

：反复地把每次计算结果放入缓冲区Buf中打印进程PP

：将计算进程每次放入缓冲区Buf中的数据取出，通过打印机打印输出缓冲区Buf

：一次只可放一个数据例，共享一个缓冲区的合作进程3.6进程同步缓冲区计算进程PC打印进程PP计算进程PC92BeginSc,Sp:semaphore;Sp=0;/*信号量Sp，表示缓冲区Buf

是否存放计算结果*/Sc=1;/*信号量Sc，表示缓冲区Buf是否为空*/CobeginPc:While(计算未结束);/*计算进程*/{计算；P(Sc);/*缓冲区是否为空？若非空，则等待*/Buf←计算结果；V(Sp);}Pp:While(打印未完成);/*打印进程*/{P(Sp);/*缓冲区是否为数据？若无，则等待*/从缓冲区Buf取数据；V(Sc);打印数据；}CoendEndBegin93分析缓冲区是临界资源，必须互斥访问信号量empty：表示缓冲区是否为空，初值为1信号量Sr：进程R是否已输入信息，初值Sr=0信号量Sm：进程M是否已加工信息，初值Sm=0分析缓冲区是临界资源，必须互斥访问94beginempty,Sr,Sm,Sp:semaphoreempty:=1;Sr:=0;Sm:=0;CobeginPr:Repeat从输入设备读一个记录；P(empty);将记录存入缓冲区；V(Sr);UntilfalsePm:RepeatP(Sr);在缓冲区中加工记录；V(Sm);Untilfalsebeginempty,Sr,Sm,Sp:sem95

Pp:RepeatP(Sm);从缓冲区取出一个记录；V(empty);打印记录；UntilfalseCoendendPp:Repeat96第3章进程管理2.有一阅览室，读者进入时必须先在一张登记表上进行登记。该表为每一座位列出一个表目，包括座号、姓名。读者离开时撤消登记信息。阅览室有100个座位，试问：（1）为描述读者的动作，应编写几个程序，应该设置几个进程？进程和程序之间的对应关系如何？（2）试用P、V操作描述这些进程间的同步算法。第3章进程管理2.有一阅览室，读者进入时必须先在一张登记97分析读者动作：登记、读书、撤消座位总数：100登记/撤消都需要在登记表修改信息，一次只能有一个读者对登记表进行访问登记表是临界资源，必须互斥访问一个读者一个进程信号量的设置

S：用于读者互斥访问（登记/撤消）登记表，初值为1Sn：表示空座位数，初值为100每个座位设一个状态位：满/空（类似信箱通讯）分析读者动作：登记、读书、撤消98程序beginS,Sn:Semaphore;S:=1;Sn:=100;CobeginprocessReaderi(i=1,2,……,n）beginP(Sn);P(S);选择标志为空的座位X；登记；置座位X的标志为满；V(S);程序beginS,Sn:Semaphore;99

读书；P(S)在登记表中查找座位X；撤消登记信息；置座位X的标志为空；V(Sn)V(S)endCoend讨论并分析上述程序：采用指针形式（类似生产者-消费者问题）给每个座位设置一个信号量（类似哲学家就餐问题）读书；100第3章补充题3.桌上有一只盘子，每次只能放入一个水果。爸爸专向盘中放苹果，妈妈专向盘中放桔子，一个女儿专等吃盘中的苹果，一个儿子专等吃盘中的桔子。试用P、V操作写出他们能同步的程序。分析：信号量S：表示盘子是否为空，初值为1信号量So：表示盘中是否有桔子，初值为0信号量Sa：表示盘子是否有苹果，初值为0第3章补充题3.桌上有一只盘子，每次只能放入一个水果。101程序beginS,Sa,So:semaphoreS=1;Sa=0;So=0;Cobeginfather:RepeatP(S);将苹果放入盘中；V(Sa);Untilfalsemother:RepeatP(S);将桔子放入盘中；V(So);Untilfalse程序begin102

daughter:RepeatP(Sa);从盘中取出苹果；V(S);吃苹果；Untilfalseson:RepeatP(So);从盘中取出桔子；V(S);吃桔子；UntilfalseCoendenddaughter:Repeat103第3章补充题4、某大学军训正在进行实弹练习。现有一保管员负责管理枪支弹药，有A、B两组学生，A组学生每人都有一支枪，B组学生每人都备有足够的子弹，任一学生只要有枪和子弹就可以进行实弹练习。在打靶场有一个可以放一只枪或一发子弹的盒子，当盒中无物品时，保管员就可以任意放一支枪或一发子弹供学生取用。当盒中有学生所需材料时，每次允许一个学生从中取出自己所需的材料，材料取走后，保管员再放一件材料。（1）试说明A、B两组学生、保管员之间的相互制约关系。（2）应设置哪些信号量，它们的初值是什么？（3）试用P、V写出他们并发执行的程序（类C或类PASCAL语言）。第3章补充题4、某大学军训正在进行实弹练习。现有一保管员104解答解：（1）这是一个生产者-消费者问题。A、B两组学生是消费者，保管员是生产者，盒子是缓冲区，是一个临界资源。它们之间的相互制约关系是：保管员与学生之间不仅要同步，而且保管员与A、B两组学生之间、以及A、B两组学生之间还要互斥。（2）设置3个信号量如下：公用信号量S：初值为1，表示盒子是否为空；私用信号量Sgun：表示盒子中是否有一支枪，初值为0；私用信号量Sbullet：表示盒子中是否有一发子弹，初值为0解答解：105程序如下：BeginS,Sgun,Sbullet:semaphoreS=1;/*表示盒子是否为空，初值为1*/Sgun=0;/*表示盒子中是否有一支枪，初值为0*/Sbullet=0;/*表示盒子中是否有一发子弹，初值为0*/CobeginKeeper：RepeatP(S);将一支枪或一发子弹放入盒子中；If放入的是一支枪ThenV(Sgun)ElseV(Sbullet)fiUntilfalse程序如下：Begin106StudentAi(i=1,2,…)RepeatP(Sbullet);从盒子中取出子弹；V(S);打靶；UntilfalseStudentBj(j=1,2,…)RepeatP(Sgun);从盒子中取出枪；V(S);打靶；UntilfalseCoendendStudentAi(i=1,2,…)1075、假定系统中有五个进程{P0，P1，P2，P3，P4}和三种类型的资源{A，B，C}，每种资源的数量分别为10，5，7，在T时刻的资源分配情况如表所示。

（1）T时刻系统是否为安全状态，若是，请给出安全序列。

（2）如果进程P4此时提出资源申请（3，3，1），系统能否将资源分配给它？为什么？资源进程最大需求矩阵M分配矩阵RABCABCP0P1P2P3P4753322902222433010200302211002第3章补充题5、假定系统中有五个进程{P0，P1，P2，P3，P4}和三108解：（1）进程的最大资源需求数减去当前进程已分配到的资源数就是进程仍需要的资源数。此时各进程的仍需资源数向量为进程仍需资源数QP0743P1122P2600P3011P4431解：进程仍需资源数QP074109已知：系统的可用资源向量为W=（10，5，7）已分配的资源向量为P=（7，2，5）则，系统的当前剩余资源向量为S=（3，3，2）在T时刻系统存在如下进程执行序列，可以使进程顺利进行完毕，所以该状态是安全的，安全序列为P1、P3、P0、P4、P2。具体如下：进程系统可用资源数SP1完成后：5，3，2P3完成后：7，4，3P0完成后：7，5，3P4完成后：7，5，5P2完成后：10，5，7已知：系统的可用资源向量为W=（10，5，7）进程系统可用110（2）如果进程P4此时提出资源申请（3，3，1），系统满足进程P4的请求，则系统的可用资源数变为（0，0，1）。而此时各进程的仍需资源数向量为：进程仍需资源数P0743P1122P2600P3011P4100这时系统的可用资源数（0，0，1）不能满足任何一个进程，系统处于不安全状态。因此，系统不能将资源分配给进程P4。（2）如果进程P4此时提出资源申请（3，3，1），系统满足进111P833.10P62经典生产者-消费者问题P833.10P62经典生产者-消费者问题112经典生产者—消费者问题设生产者进程和消费者进程是互相等效的，其中，各生产者进程使用过程deposit(data)，各消费者使用的过程remove(data)生产者-消费者问题是一个同步问题消费者想接收数据时，缓冲区中至少有一个单元是满的生产者想发送数据时，缓冲区中至少有一个单元是空的生产者-消费者问题是一个互斥问题缓冲区是临界资源经典生产者—消费者问题设生产者进程和消费者进程是互相等效的，113经典生产者—消费者问题设置信号量公用信号量mutex：保证生产者进程和消费者进程之间的互斥；初值为1，表示没有进程进入临界区私用信号量avail：生产者进程的私用信号量，表示可用缓冲区数，初值为n私用信号量full：消费者进程的私用信号量，表示产品数目，初值为0经典生产者—消费者问题设置信号量114生产者—消费者进程描述生产者进程生产一种产品P(avail)P(mutex)产品送入缓冲区V(full)V(mutex)消费者进程P(full)P(mutex)从缓冲区取一产品V(avail)V(mutex)消耗该产品生产者—消费者进程描述生产者进程生产一种产品消费者进程P(f115操作系统习题分析课件116生产者指针P

消费者指针R

有界缓冲区初始状态RP…

I12J……n为什么要互斥访问缓冲区？…

I12J…中间状态RP…n什么情况下，出现阻塞？生产者指针P消费者指针R有界缓冲区初始状态117经典生产者—消费者问题设置信号量公用信号量S：初值为1，表示没有进程进入临界区，用于实现进程互斥私用信号量S0：表示产品数目，初值为0私用信号量Sn：表示可用缓冲区数，初值为n经典生产者—消费者问题设置信号量118生产者—消费者进程描述生产者进程生产一种产品P(Sn)P(S)产品送入缓冲区V(S0)V(S)消费者进程P(S0)P(S)从缓冲区取一产品V(Sn)V(S)消耗该产品生产者—消费者进程描述生产者进程生产一种产品消费者进程P(S119BeginB:array[0..n-1]ofinteger;P,R:integer;S,Sn,S0:semaphore;P:=R:=0;S:=1;Sn:=n;S0:=0;CobeginProcessProducei(i=1,2,…,m)BeginL1:produceaproductP(Sn);P(S);B[P]:=product;P:=(P+1)modn;V(S