操作系统习题分析.ppt

《操作系统习题分析.ppt》由会员分享，可在线阅读，更多相关《操作系统习题分析.ppt（85页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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负责从输入设备读信息，每读一个记录后，负责从输入设备读信息，每读一个记录后，就把

3、它存放在缓冲区中；就把它存放在缓冲区中；M在在缓冲区中加工读入缓冲区中加工读入的记录；的记录；P把加工后的记录打印输出。读入的记录把加工后的记录打印输出。读入的记录经加工输出后，缓冲区又可存放下一个记录。试经加工输出后，缓冲区又可存放下一个记录。试写出它们能正确执行的程序。写出它们能正确执行的程序。缓冲区缓冲区输入进程输入进程R打印进程打印进程P处理进程处理进程M3.6 进程同步缓冲区缓冲区计算进程计算进程PC打印进程打印进程PP计算进程计算进程PC：反复地把每次计算结果放入缓冲区：反复地把每次计算结果放入缓冲区Buf中中打印进程打印进程PP：将计算进程每次放入缓冲区：将计算进程每次放入缓冲区

4、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);/*缓冲区是否为数据？若无，则等待*/从缓冲

5、区Buf取数据；V(Sc);打印数据；CoendEnd分析缓冲区是临界资源，必须互斥访问缓冲区是临界资源，必须互斥访问信号量信号量empty：表示缓冲区是否为空，初值为表示缓冲区是否为空，初值为1信号量信号量Sr：进程进程R是否已输入信息，初值是否已输入信息，初值Sr=0信号量信号量Sm：进程进程M是否已加工信息，初值是否已加工信息，初值Sm=0begin empty,Sr,Sm,Sp:semaphore empty:=1;Sr:=0;Sm:=0;Cobegin Pr:Repeat 从输入设备读一个记录；从输入设备读一个记录；P(empty);将将记录存入缓冲区；记录存入缓冲区；V(Sr);U

6、ntil false Pm:Repeat P(Sr);在缓冲区中加工记录；在缓冲区中加工记录；V(Sm);Until false Pp:Repeat P(Sm);从缓冲区取出一个记录；从缓冲区取出一个记录；V(empty);打印记录；打印记录；Until false Coendend 第3章 进程管理2.有一阅览室，读者进入时必须先在一张登记表上有一阅览室，读者进入时必须先在一张登记表上进行登记。该表为每一座位列出一个表目，包括进行登记。该表为每一座位列出一个表目，包括座号、姓名。读者离开时撤消登记信息。阅览室座号、姓名。读者离开时撤消登记信息。阅览室有有100个座位，试问：个座位，试问：（1

7、）为描述读者的动作，应编写几个程序，）为描述读者的动作，应编写几个程序，应该设置几个进程？进程和程序之间的对应关系应该设置几个进程？进程和程序之间的对应关系如何？如何？（2）试用）试用P、V操作描述这些进程间的同步操作描述这些进程间的同步算法。算法。分析读者动作：登记、读书、撤消读者动作：登记、读书、撤消座位总数：座位总数：100登记登记/撤消都需要在登记表修改信息，一次只能有一撤消都需要在登记表修改信息，一次只能有一个读者对登记表进行访问个读者对登记表进行访问 登记表是临界资源，必须互斥访问登记表是临界资源，必须互斥访问一个读者一个进程一个读者一个进程信号量的设置信号量的设置 S：用于读者互

8、斥访问（登记用于读者互斥访问（登记/撤消）登记表，初值为撤消）登记表，初值为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

9、的标志为空；的标志为空；V(Sn)V(S)end Coend讨论并分析上述程序：讨论并分析上述程序：采用指针形式（类似生产者采用指针形式（类似生产者-消费者问题）消费者问题）给每个座位设置一个信号量（类似哲学家就餐问题）给每个座位设置一个信号量（类似哲学家就餐问题）第3章 补充题3.桌上有一只盘子，每次只能放入一个水果。爸爸桌上有一只盘子，每次只能放入一个水果。爸爸专向盘中放苹果，妈妈专向盘中放桔子，一个女专向盘中放苹果，妈妈专向盘中放桔子，一个女儿专等吃盘中的苹果，一个儿子专等吃盘中的桔儿专等吃盘中的苹果，一个儿子专等吃盘中的桔子。试用子。试用P、V操作写出他们能同步的程序。操作写出他们能同

10、步的程序。分析：分析：信号量信号量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);从盘中取出苹果；

11、从盘中取出苹果；V(S);吃苹果；吃苹果；Until false son:Repeat P(So);从盘中取出桔子；从盘中取出桔子；V(S);吃桔子；吃桔子；Until false Coendend第3章 补充题4、某大学军训正在进行实弹练习。现有一保管员负责管理枪、某大学军训正在进行实弹练习。现有一保管员负责管理枪支弹药，有支弹药，有A、B两组学生，两组学生，A组学生每人都有一支枪，组学生每人都有一支枪，B组学生每人都备有足够的子弹，任一学生只要有枪和子弹组学生每人都备有足够的子弹，任一学生只要有枪和子弹就可以进行实弹练习。在打靶场有一个可以放一只枪或一就可以进行实弹练习。在打靶场有一个可以

12、放一只枪或一发子弹的盒子，当盒中无物品时，保管员就可以任意放一发子弹的盒子，当盒中无物品时，保管员就可以任意放一支枪或一发子弹供学生取用。当盒中有学生所需材料时，支枪或一发子弹供学生取用。当盒中有学生所需材料时，每次允许一个学生从中取出自己所需的材料，材料取走后，每次允许一个学生从中取出自己所需的材料，材料取走后，保管员再放一件材料。保管员再放一件材料。（1）试说明）试说明A、B两组学生、保管员之间的相互制约关系。两组学生、保管员之间的相互制约关系。（2）应设置哪些信号量，它们的初值是什么？）应设置哪些信号量，它们的初值是什么？（3）试用）试用P、V写出他们并发执行的程序（类写出他们并发执行的

13、程序（类C或类或类PASCAL语言）。语言）。解答解：解：（1）这是一个生产者）这是一个生产者-消费者问题。消费者问题。A、B两组学生是消费者，保管员是生产者，盒子是缓两组学生是消费者，保管员是生产者，盒子是缓冲区，是一个临界资源。冲区，是一个临界资源。它们之间的相互制约关系是：保管员与学生之间不仅要它们之间的相互制约关系是：保管员与学生之间不仅要同步，而且保管员与同步，而且保管员与A、B两组学生之间、以及两组学生之间、以及A、B两组学两组学生之间还要互斥。生之间还要互斥。（2）设置）设置3个信号量如下：个信号量如下：公用信号量公用信号量S：初值为：初值为1，表示盒子是否为空；，表示盒子是否为

14、空；私用信号量私用信号量Sgun：表示盒子中是否有一支枪，初值为：表示盒子中是否有一支枪，初值为0；私用信号量私用信号量Sbullet：表示盒子中是否有一发子弹，初值为：表示盒子中是否有一发子弹，初值为0程序如下：Begin S,Sgun,Sbullet:semaphore S=1;/*表示盒子是否为空，初值为表示盒子是否为空，初值为1*/Sgun=0;/*表示盒子中是否有一支枪，初值为表示盒子中是否有一支枪，初值为0*/Sbullet=0;/*表示盒子中是否有一发子弹，初值为表示盒子中是否有一发子弹，初值为0*/Cobegin Keeper：Repeat P(S);将一支枪或一发子弹放入盒子

15、中；将一支枪或一发子弹放入盒子中；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 Coendend5、假定系统中有五个进程P0，P1，P2，P3，P4和三种类型的资源A，B，C，每种资源的数量分别为10，5，7，在T时刻的资源

16、分配情况如表所示。（1）T时刻系统是否为安全状态，若是，请给出安全序列。（2）如果进程P4此时提出资源申请（3，3，1），系统能否将资源分配给它？为什么？资源资源进程进程最大需求矩阵最大需求矩阵M分配矩阵分配矩阵R A B CA B CP0P1P2P3P47 5 33 2 29 0 22 2 24 3 30 1 02 0 03 0 22 1 10 0 2第3章 补充题解：解：（1）进程的最大资源需求数减去当前进程已分）进程的最大资源需求数减去当前进程已分配到的资源数就是进程仍需要的资源数。此时配到的资源数就是进程仍需要的资源数。此时各进程的仍需资源数向量为各进程的仍需资源数向量为进进程程仍需仍

17、需资资源数源数QP07 4 3P11 2 2P26 0 0P30 1 1P44 3 1已知：系统的可用资源向量为已知：系统的可用资源向量为W=（10，5，7）已分配的资源向量为已分配的资源向量为P=（7，2，5）则，系统的当前剩余资源向量为则，系统的当前剩余资源向量为S=（3，3，2）在在T时刻系统存在如下进程执行序列，可以使进程顺时刻系统存在如下进程执行序列，可以使进程顺利进行完毕，所以该状态是安全的，安全序列为利进行完毕，所以该状态是安全的，安全序列为P1、P3、P0、P4、P2。具体如下：。具体如下：进进程程系系统统可用可用资资源数源数SP1完成后：完成后：5，3，2P3完成后：完成后：

18、7，4，3P0完成后：完成后：7，5，3P4完成后：完成后：7，5，5P2完成后：完成后：10，5，7（2）如果进程）如果进程P4此时提出资源申请（此时提出资源申请（3，3，1），系统满足），系统满足进程进程P4的请求，则系统的可用资源数变为（的请求，则系统的可用资源数变为（0，0，1）。）。而此时各进程的仍需资源数向量为：而此时各进程的仍需资源数向量为：进进程程仍需仍需资资源数源数P07 4 3P11 2 2P26 0 0P30 1 1P41 0 0 这时系统的可用资源数（这时系统的可用资源数（0，0，1）不能满足任何）不能满足任何一个进程，系统处于不安全状态。一个进程，系统处于不安全状态。

19、因此，系统不能将资源分配给进程因此，系统不能将资源分配给进程P4。P83 3.10 P62 经典生产者经典生产者-消费者问题消费者问题经典生产者消费者问题设生产者进程和消费者进程是互相等效的，其中，各生产者进程使用过程设生产者进程和消费者进程是互相等效的，其中，各生产者进程使用过程deposit(data)，各消费者使用的过程，各消费者使用的过程remove(data)生产者生产者-消费者问题是一个同步问题消费者问题是一个同步问题消费者想接收数据时，缓冲区中至少有一个单元是满的消费者想接收数据时，缓冲区中至少有一个单元是满的生产者想发送数据时，缓冲区中至少有一个单元是空的生产者想发送数据时，缓

20、冲区中至少有一个单元是空的生产者生产者-消费者问题是一个互斥问题消费者问题是一个互斥问题缓冲区是临界资源缓冲区是临界资源经典生产者消费者问题设置信号量设置信号量公用信号量公用信号量mutex：保证生产者进程和消费者进程之：保证生产者进程和消费者进程之间的互斥；初值为间的互斥；初值为1，表示没有进程进入临界区，表示没有进程进入临界区私用信号量私用信号量avail：生产者进程的私用信号量，表示可：生产者进程的私用信号量，表示可用缓冲区数，初值为用缓冲区数，初值为n私用信号量私用信号量full：消费者进程的私用信号量，表示产品：消费者进程的私用信号量，表示产品数目，初值为数目，初值为 0生产者消费者

21、进程描述生产者进程生产者进程生产一种产品生产一种产品P(avail)P(mutex)产品送入缓冲区产品送入缓冲区V(full)V(mutex)消费者进程消费者进程P(full)P(mutex)从缓冲区取一产品从缓冲区取一产品V(avail)V(mutex)消耗该产品消耗该产品生产者指针P 消费者指针R 有界缓冲区有界缓冲区初始状态初始状态R P I12Jn为什么要互斥访问缓冲区？为什么要互斥访问缓冲区？I12J中间状态中间状态RPn什么情况下，出现阻塞？什么情况下，出现阻塞？经典生产者消费者问题设置信号量设置信号量公用信号量公用信号量S：初值为初值为1，表示没有进程进入临界区，用，表示没有进程

22、进入临界区，用于实现进程互斥于实现进程互斥私用信号量私用信号量S0：表示产品数目，初值为表示产品数目，初值为0私用信号量私用信号量Sn：表示可用缓冲区数，初值表示可用缓冲区数，初值为为n生产者消费者进程描述生产者进程生产者进程生产一种产品生产一种产品P(Sn)P(S)产品送入缓冲区产品送入缓冲区V(S0)V(S)消费者进程消费者进程P(S0)P(S)从缓冲区取一产品从缓冲区取一产品V(Sn)V(S)消耗该产品消耗该产品Begin B:array0.n-1 of integer;P,R:integer;S,Sn,S0:semaphore;P:=R:=0;S:=1;Sn:=n;S0:=0;Cobe

23、gin 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 CoendendP83 3.10解：设互斥信号量解：设互斥信号量mutexn为缓冲区的公用信号量，初始为缓冲区的公用信号量，初始值为

24、值为1。设信号量设信号量S1为生产者进程信号量，初始值为为生产者进程信号量，初始值为m。设信号量设信号量S2为消费者信号量，初始值为为消费者信号量，初始值为0。各生产者进程使用的过程各生产者进程使用的过程Deposit(data)如下：如下：Deposit(data)BeginP(S1)选择第选择第n个空缓冲区个空缓冲区P(mutexn)送数据入第送数据入第n个缓冲区个缓冲区V(S2)V(mutexn)End各消费者进程使用的过程各消费者进程使用的过程Remove(data)如下：如下：Remove(data)BeginP(S2)选择一个已有数据的缓冲区选择一个已有数据的缓冲区k P(mute

25、xk)取出缓冲区取出缓冲区k中的数据中的数据V(S1)V(mutexk)EndP83 3.11P61 例例P61 例，设进程例，设进程PA和和PB通过缓冲区队列传递数据通过缓冲区队列传递数据(如图如图3.14)。PA为发送进程，为发送进程，PB为接收进程。为接收进程。PA发送数据时调用发送过发送数据时调用发送过程程deposit(data)，PB接收数据时调用过程接收数据时调用过程remove(data)。且数据的发送和接收过程满足如下条件：。且数据的发送和接收过程满足如下条件：在在PA至少送一块数据入一个缓冲区之前，至少送一块数据入一个缓冲区之前，PB不可能从缓不可能从缓冲区中取出数据（假定

26、数据块长等于缓冲区长度）冲区中取出数据（假定数据块长等于缓冲区长度）PA往缓冲队列发送数据时，至少有一个缓冲区是空的往缓冲队列发送数据时，至少有一个缓冲区是空的由由PA发送的数据块在缓冲队列中按先进先出发送的数据块在缓冲队列中按先进先出(FIFO)方式排方式排列列描述发送进程描述发送进程deposit(data)和接收进程和接收进程remove(data)图3.14 缓冲区队列P83 3.11解：由题可知，进程解：由题可知，进程PA调用发送过程调用发送过程deposit(data)和进和进程程 PB调用过程调用过程remove(data)必须同步执行，因此，必须同步执行，因此，设：设：Bufe

27、mpty为进程为进程PA的私用信号量，初值的私用信号量，初值Bufempty=nBuffull为进程为进程PB的私用信号量，初值的私用信号量，初值Buffull=0 则，过程则，过程deposit(data)和和remove(data)描述如下：描述如下：P83 3.11设：有两个缓冲区队列设：有两个缓冲区队列i=1、2，每个缓冲区队列有，每个缓冲区队列有n个缓冲区。个缓冲区。bufi(k)表示第表示第i个缓冲队列的第个缓冲队列的第k个缓冲区个缓冲区 bufempty0，buffull1为为PA的私有信号量的私有信号量 buffull0，buffempty1是是PB的私有信号量的私有信号量 b

28、ufempty0=bufempty1=n buffull0=buffull1=0PA调用调用send(0,m)发送数据，发送数据，receive(1,m)接接收数据；收数据；PB调用调用send(1,m)发送数据，发送数据，receive(0,m)接接收数据；收数据；发送过程发送过程send(i,m)beginP(bufemptyi)FIFO方式选择一个空缓冲区方式选择一个空缓冲区kbufi(k)=mbufi(k)置满标记置满标记V(buffulli)End接收过程接收过程Receive(i,m)beginP(buffulli)FIFO方式选择一个满缓冲区方式选择一个满缓冲区km=bufi(k

29、)bufi(k)置空标记置空标记V(bufemptyi)endP84 3.13（参考p72 例2）#includeMain()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);Elsewhile(P2=fork()

30、=-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);Elsewhile(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

31、,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 哲学家就餐问题(习题p1

32、5)有五个哲学家围坐在一圆桌旁，桌中央有一盘有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一通心粉，每人面前有一只空盘子，每两人之间放一只筷子只筷子 每个哲学家的行为是思考，感到饥饿，然后吃每个哲学家的行为是思考，感到饥饿，然后吃通心粉通心粉 为了吃通心粉，每个哲学家必须拿到两只筷子，为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子并且每个人只能直接从自己的左边或右边去取筷子Repeat 思考；思考；取取forki;/*取左边筷子取左边筷子*/取取fork(i+1)mod 5；/*取右边筷子取右边筷子*/进食；进食；放放

33、forki;/*放左边筷子放左边筷子*/放放fork(i+1)mod 5；/*放右边筷子放右边筷子*/Until false;方法：为每根筷子单独设置一个信号量，取筷子执行方法：为每根筷子单独设置一个信号量，取筷子执行P操作，放筷子执行操作，放筷子执行V操作操作Var chopstick:array0.4 of semaphore;For i=0 to 4 chopsticki=1 Next iPi:Repeat think;P(chopsticki);P(chopsticki+1 mod 5);eat;V(chopsticki);V(chopsticki+1 mod 5);Until fal

34、se;存在问题 上述方法简单，并能保证任何时候均不存在上述方法简单，并能保证任何时候均不存在两个相邻的哲学家同时在吃饭。两个相邻的哲学家同时在吃饭。但由于进程的并发执行与但由于进程的并发执行与CPU的调度问题，的调度问题，可能使得每个哲学家都只能拿到了自己左边的筷可能使得每个哲学家都只能拿到了自己左边的筷子，那么这一组进程就会发生死锁现象。子，那么这一组进程就会发生死锁现象。为防止死锁发生可采取的措施：为防止死锁发生可采取的措施：最多允许最多允许4 4个哲学家同时坐在桌子周围个哲学家同时坐在桌子周围仅当一个哲学家左右两边的筷子都可用时，才允许仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子

35、（他拿筷子（）给所有哲学家编号，奇数号的哲学家必须首先拿左给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之边的筷子，偶数号的哲学家则反之为了避免死锁，把哲学家分为三种状态，思考，饥为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿饿，进食，并且一次拿到两只筷子，否则不拿state:array0.4 of (思考，饥饿，进食）；思考，饥饿，进食）；ph:array0.4 of semaphore;mutex:semaphore;i:0.4;Procedure test(i:=04);begin if(state i =饥饿饥饿)And

36、(state(i-1)mod5进食进食)And (state(i+1)mod5进食进食)then state i=进食进食 V(ph i)fi endProcedure 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 falesEndstate I=思考思考ph

37、 I=0mutex=1第4章 处理机调度P108 习题习题2、4、5、6第4章 处理机调度4.6 假设有4道作业，它们的提交时刻和执行时间由下表给出：作业号作业号提交时刻提交时刻/小小时时执行时间执行时间/小小时时110:002210:201310:400.5410:500.3计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。1.先来先服务(FCFS)调度算法将用户作业和就绪进程按提交顺序或变为就绪将用户作业和就绪进程按提交顺序或变为就绪状态的先后排队，按照先来先服务的方式调度状态的先后排队，按照先来先服务的方式调度 对

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

39、等待很长的时间进程之后到达，则它们将等待很长的时间 采用先来先服务调度算法时的周转时间和带权周转时间如下表所示，计算可得：平均周转时间为：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=17

40、0(2.83h)WC=5.67410:500.3(18)13:3013:48T4=178(2.97h)WD=9.89平均平均T=157m =2.6167hW=4.8075 先来先服务算法（先来先服务算法（FCFS）最短作业优先法(SJF)方法：选择那些估计需要执行时间最短的作业投入执行方法：选择那些估计需要执行时间最短的作业投入执行优点：系统在同一时间内处理的作业个数最多，吞吐量大优点：系统在同一时间内处理的作业个数最多，吞吐量大于其他调度方式于其他调度方式问题：问题：SJF需要事先知道或至少需要需要事先知道或至少需要估计每个作业所需的处理估计每个作业所需的处理机时间机时间只要不断的有短作业进

41、入系统，就有可能使长作业长期只要不断的有短作业进入系统，就有可能使长作业长期得不到运行而得不到运行而“饿死饿死”SJF 偏向短作业，不利于分时系统（由于不可抢占性）偏向短作业，不利于分时系统（由于不可抢占性）采用最短作业优先最短作业优先法时的周转时间和带权周转时间如下表所示（情况1：将作业收集成一批再处理），计算可得：平均周转时间为：T=123m=2.05h平均带权周转时间为：W=1.8875它们的调度顺序是：作业4作业3作业2作业1作作业业号号提交提交时间时间 Tin执执行行时间时间Tr开始开始时间时间TS结结束束时间时间Tc周周转时间转时间T(m)带权带权周周转时间转时间W110:002(

42、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）采用最短作业优先最短作业优先法时的周转时间和带权周转时间如下表所示（情况2：有作业就执行），计算可得：平均周转时间为：T=123m=2.05h平均带权周转时间为：W=1.8875它们的调度顺序是：作业1 作业4作业3作业2作作业业号号提交提交时间时间

43、 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）第5章 存储管理p144 习题习题2、3、4、6、9、10

44、、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）和理想置换算法分别计算程序访问过）和理想置换算法分别计算程序访问过程中所发生的缺页次数和缺页率。程中所发生的缺页次数和缺页率。走向走向5 0 121 324230321201501页页15 0 121 324230321201501页页25 012 1324230

45、32120150页页3500 213342203312015缺页缺页 走向走向5 0121324 230321201501页页15 0122334 440021111500页页25011223 334402222155页页3500112 223340000211缺页缺页 FIFO算法的缺页中断次数算法的缺页中断次数F=11，缺页率，缺页率f=11/20=55%LRU算法的缺页中断次数算法的缺页中断次数F=10，缺页率，缺页率f=10/20=50%走向走向50121324 230321201501页页150122334 440001111555页页25011223 333330000111页页3

46、500002 222222222000缺页缺页 理想置换算法的缺页中断次数理想置换算法的缺页中断次数F=9 缺页率缺页率f=9/20=45%补充题补充题2、某系统采用请求分页存储管理，页长为、某系统采用请求分页存储管理，页长为2 KB（即（即2048B），某作业的页表如下所示。请简述），某作业的页表如下所示。请简述执行指令执行指令 60 LOAD A,5168 的地址变换的地址变换过程。过程。358解：执行指令解：执行指令60 LOAD A,5168的地址变换过程为：的地址变换过程为：（1）取指令：首先根据该指令的逻辑地址）取指令：首先根据该指令的逻辑地址60，得到相，得到相应的逻辑页式地址为

47、（应的逻辑页式地址为（0，60），然后查页表得到其），然后查页表得到其物理块为物理块为3，计算出物理地址为：，计算出物理地址为：32048+606204 所以，从所以，从6204单元中取出指令执行。单元中取出指令执行。（2）取数据：首先根据数据的逻辑地址）取数据：首先根据数据的逻辑地址5168，得到，得到相应的逻辑页式地址为（相应的逻辑页式地址为（2，1072），然后查页表），然后查页表得到其物理块为得到其物理块为8，计算出物理地址为：，计算出物理地址为：82048+107217456 所以，从所以，从17456单元中取出数据，放入寄存器单元中取出数据，放入寄存器A中。中。具体来说，该指令的执

48、行过程是：首先从内存的具体来说，该指令的执行过程是：首先从内存的6204 单元取指令，然后再从单元取指令，然后再从17456单元取数据，单元取数据，放入寄存器放入寄存器A中。中。补充作业补充作业3在一个系统中采用动态分区法管理内存，假定在一个系统中采用动态分区法管理内存，假定内存中按地址递增顺序依次有内存中按地址递增顺序依次有5个空闲区，如表个空闲区，如表1所示。现有所示。现有4道作业道作业J1、J2、J3、J4依次要进依次要进入内存，它们各需要的内存大小分别为入内存，它们各需要的内存大小分别为3KB、11KB、98KB、44KB。试分别用最先适应法。试分别用最先适应法和最佳适应法进行分配，给

49、出各个作业的分配情和最佳适应法进行分配，给出各个作业的分配情况与最终的可用空闲区情况。况与最终的可用空闲区情况。表1 可用空闲区表 区号区号分区分区长长度度起始地址起始地址113K70K25K100K3198K130K448K480K525K600K解：解：（1）对于最先适应法，可用分区表与作业请）对于最先适应法，可用分区表与作业请求表如表求表如表1、2所示：所示：表表1 可用分区表可用分区表区号区号分区分区长长度度起始地址起始地址113K70K25K100K3198K130K448K480K525K600K作业号作业号请求长度请求长度J13K J211KJ398KJ444K表表2 作业请求表

50、作业请求表系统分配过程如下：系统分配过程如下：对于对于J1，系统从分区，系统从分区1中划出中划出3KB分配给分配给J1，分区，分区1还剩下还剩下10KB；对于对于J2，系统从分区，系统从分区3中划出中划出11KB分配给分配给J2，分，分区区3还剩下还剩下187KB；对于对于J3，系统从分区，系统从分区3中划出中划出98KB分配给分配给J3，分，分区区3还剩下还剩下89KB；对于对于J4，系统从分区，系统从分区3中划出中划出44KB分配给分配给J4，分，分区区3还剩下还剩下45KB；因此，每个作业都分配到所需要的内存空间，此时因此，每个作业都分配到所需要的内存空间，此时系统中的可用分区如表系统中