期末复习-例题汇总.ppt

1、第一章 操作系统概述,本章要点,计算机系统结构：了解操作系统的地位 什么是操作系统：四种基本观点 现代操作系统的特征、功能 、类型 基本概念 ：批处理、多道程序设计、作业、任务、进程与线程、接口、虚拟存储、文件,实例分析：多道程序设计的实现,在单CPU和两台I/O（I1,I2）设备的多道程序设计环境下，同时投入三个作业运行。它们的执行轨迹如下： Job1：I2(30ms)、CPU(10ms)、I1(30ms)、CPU(10ms) Job2：I1(20ms)、CPU(20ms)、I2(40ms) Job3：CPU(30ms)、I1(20ms) 如果CPU、I1和I2都能并行工作，优先级从高到低为

2、Job1、Job2和Job3，优先级高的作业可以抢占优先级低的作业的CPU。求： （1）每个作业从投入到完成分别所需的时间。 （2）作业从投入到完成CPU的利用率。 （3）I/O设备利用率,实例分析：多道程序设计的实现,【参考答案】 （1）Job1从投入到运行完成需80ms，Job2从投入到运行完成需90ms，Job3从投入到运行完成需90ms； （2）CPU空闲段：60ms-70ms、80ms-90ms，所以CPU利用率为： （90-20）/90100%=77.78% （3）设备I1空闲段：20ms-40ms，故I1的利用率为： （90-20）/90100%=77.78% 设备I2空闲段：3

3、0ms-50ms，故I2的利用率为： （90-20）/90100%=77.78%,思考题,假定有4个程序，每个程序花费80%的时间执行I/O，20%的时间使用CPU。每个程序的启动时间和其需要使用CPU进行计算的分钟数如下表所示。 试计算4个程序执行完成所需要的时间（响应时间）分别是多少？系统的平均响应时间是多少？与单道执行环境相比，系统平均响应时间节约了多少分钟？并分析每个程序以80%（I/O）和20%（CPU）的资源占有情况进行运行，在不考虑内存容量的情况下，当程序道数为多少的时候CPU的利用率是最高的？并总结在多道程序设计环境下CPU利用率的计算公式。,参考答案, ,单道：20；35-1

4、0=25； 45-15=30；55-20=35,第二章进程管理,本章要点,基础：进程描述及控制 策略：进程调度 实现：互斥与同步 避免：死锁与饥饿 解决：几个经典问题 关于：进程通信,短进程优先,例：若在后备作业队列中等待运行的同时有1、2、3，已知它们各自的运行时间为a，b，c，且满足a0即证。,由于短作业优先调度算法总是在后备作业队列中选择运行时间最短的作业作为调度对象，因此对短作业优先调度算法而言，这三个作业的总周转时间为 T1=a+(a+b)+(a+b+c)=3a+2b+c 若不按短作业优先调度算法来调度这三个作业，不失一般性，假定调度顺序为2、1、3，其总周转时间为： T2=b+(b

5、+a)+(b+a+c)=3b+2a+c -式得： T2-T1=b-a 由此可见，短作业优先调度算法能获得最小平均周转时间。,时间片轮转调度法,例:对某系统进行检测后表明，每个进程在I/O阻塞之前的运行时间为T。一次进程切换的系统开销时间为S。若采用时间片长度为Q的时间片轮转法，对下列各种情况计算出CPU利用率？ Q= QT SQT Q=S（ ST、S T呢？） Q0,时间片轮转调度法,参考答案： （1）T/(T+S) （2）T/(T+S) （3）Q/(Q+S) （4）50% （5）0,综合实例分析,题1:下表给出作业1，2，3的到达时间和运行时间。采用短作业优先调度算法和先来先服务调度算法，试

6、问平均周转时间各是多少？是否还有更好的调度策略存在？,题2、在下表中给出进程的到达时间、执行时间和优先级，请给出三种调度算法的进程执行次序和三种调度算法的平均周转时间。这三种调度算法是：短作业优先调度算法、优先级高者优先调度算法和简单轮转法（简单轮转法中的时间片为2个单位）。（抢占式调度策略）,参考答案： 短进程调度策略 调度次序：P1、P2、P3、P4、P5、P1 平均周转时间：29/5 优先级高者调度策略： 调度次序：P1、P2、P3、P5、P1、P4 平均周转时间：8 时间片轮转法调度策略： 调度次序：P1、P2、P3、P4、P5、P1、P5、P1、P5、P1、P1 平均周转时间：33/

7、5,题3、设有两个处理机P1、P2，它们各有一个硬件高速缓存C1、C2和各有一个主存M1、M2，其性能如下：,假定两个处理机的指令系统相同，它们的指令执行时间与存储器的平均存取周期成正比。如果执行某个程序时，所需的指令或数据在缓存存储器中存取到的概率P为0.7，试问这两个处理机的处理速度谁快？当P0.9时，处理机的速度哪个快？,解：处理机的平均存取时间：TT1（1P）T2 其中，T1为高速缓存存取时间，T2为主存存取时间（1ns1000s） （1）当P0.7时， P1的平均存取时间为： 60（10.7）1000360ns P2的平均存取时间为： 80（10.7）0.91000350ns 所以P

8、2比P1处理速度快,（2）当P0.9时， P1的平均存取时间为： 60（10.9）1000160ns P2的平均存取时间为： 80（10.9）0.91000170ns 所以P1比P2处理速度快,思考与设计,请根据下列情况，试设计一个合适的调度算法，以期能满足各类用户的需要，并能较好体现“CPU世界的公平性”，并总结调度算法的设计经验。,进程,优先级：,执行时间： 1ms 5ms； 20ms 40ms 5ms 30ms,例：设实时系统从两个不同的数据源DA和DB周期性地收集数据并进行处理（DA周期为30ms，DB周期为75ms），相应数据如下表所示：采用结束时限越近的优先权越高。,给出调度顺序和

9、相应的时间调度图,实例分析,Eg.1、桌上有一空盘，允许存放一只水果。爸爸可向盘中存放苹果，也可向盘中存放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。,daughter（） while (1) wait（Sa）； 从盘中取出苹果; signal（S）； 吃苹果； ,son（） while (1) wait（So）； 从盘中取出桔子； signal（S）； 吃桔子； ,father（） while (1) Wait（S）； 将水果放入盘中； if（放入的是桔子） signal (So); els

10、e signal（Sa）； ,类似题目拓展：,类似 （1）桌上有一个盘子，最多可以容纳两个水果，每次只能放入或取出一个水果。爸爸专向盘子中放入苹果（apple），妈妈专向盘子中放入桔子（orange），两个儿子专等吃盘中的桔子，两个女儿专等吃盘子中的苹果。请用P、V操作来实现爸爸、妈妈、儿子、女儿之间的同步互斥关系。,int mutex=1; int empty=2; int apple=0; int orange=0; main( ) cobegin father( ); mother( ); son( ); daughter( ); coend ,Father() while(1) p (

11、empty); p (mutex); 向盘中放苹果； v（mutex）； V（apple）； ,mother() while(1) p (empty); p (mutex); 向盘中放桔子； v（mutex）； V（orange）； ,soni() while(1) p (orange); p (mutex); 取盘中桔子； v（mutex）； V（empty）； i1、2,daugheri() while(1) p (apple); p (mutex); 取盘中苹果； v（mutex）； V（empty）； i1、2,（2）桌上有一个盘子，可以存放一个水果，爸爸专向盘子中放入苹果，妈妈专向盘

12、子中放入香蕉，一个儿子专等吃盘中的香蕉，一个女儿专等吃盘子中的苹果。请用P、V操作来实现爸爸、妈妈、儿子、女儿之间的同步互斥关系。,int mutex=1; int apple=0; int banana=0; main( ) cobegin father( ); mother( ); son( ); daughter( ); coend ,Father() while(1) p (mutex); 向盘中放苹果； V（apple）； ,mother() while(1) p (mutex); 向盘中放香蕉； V（banana）； ,soni() while(1) p (banana); 取盘中

13、香蕉； v（mutex）； i1、2,daughteri() while(1) p (apple); 取盘中苹果； v（mutex）； i1、2,解：设信号量empty1、empty2分别表示缓冲区1和缓冲区2是否为空，其初值为1，full1、full2分别表示缓冲区1和缓冲区2是否有记录可供处理，其初值为0。请描述同步PA、PB、PC之间的同步关系。,2、,Eg.2,Eg.3、下面是两个并发执行的进程。它们能正确运行吗？若不能。请举例说明，并改正之。,解答： 它们不能正确运行。因为题中的P1、P2之间有一个共享变量X，由于进程的并发执行，可能会产生与时间有关的错误。（X变量的值会被修改），为

14、了保证P1、P2能正确执行，必须设置一互斥信号量。 程序改正如下：,Parbegin var X:integer; mutex：semaphore; mutex:=1; process P1 var y,z:integer; begin P(mutex); x:=1; y:=0; if x=1 then y:=y+1; V(mutex); z:=y; end,process P2 Var t,u:integer; begin P(mutex); x:=0 t:=0; if x=1 then t:=t+2; V(mutex); u:=t; end parend,P54,用信号量实现前趋图,举例,

15、T0时刻的资源分配情况 假定系统中有四个进程P1,P2,P3,P4和三种类型的资源R1,R2,R3，每一种资源的数量分别为9、3、6，T0时刻的资源分配情况如表2.4所示：,进 程,资 源,T0时刻的安全性,利用安全性算法，分析T0时刻的资源分配情况，可得如表2.5所示的信息。 从T0时刻的安全性分析可知，T0时刻存在着一个安全序列,故T0时刻系统是安全的。,假设T0时刻，进程P1申请资源，其请求向量为Request1(0,0,1),系统按银行家算法进行检查： Request1 (0,0,1) Need1(2,2,2)，且 Request1 (0,0,1) Available (0,1,1)

16、故，系统试探性地为P1分配资源，并修改Available,Allocation1和Need1向量如表2.6所示。,利用安全性算法检查此时系统是否安全: 此时，系统的可用资源向量为Available（0,1,0），比较各进程的需求向量Need，系统不能满足任何进程的资源请求，系统进入不安全状态。 所以，P1请求的资源不能分配，只能让进程P1阻塞等待。,假设T0时刻，进程P4申请资源，其请求向量为Request4(1,2,0),系统按银行家算法进行检查： Request4 (1,2,0) Need4(4,2,0)，且 Request4 (1,2,0) Available (0,1,1) P4的请求

17、向量超过系统的可用资源向量，故P4的请求不能满足。进程P4阻塞等待 请读者考虑，如果T0时刻，进程P4申请资源，其请求向量为Request4(0,1,0),系统是否能将资源分配给它。,例：试简化下列资源分配图。并利用死锁定理给出相应的结论。,第三章 存储管理,本章要点,存储管理的任务 程序装入技术 内存划分与分配技术 简单存储管理技术 虚拟存储管理技术,Eg.1、下表给出了某系统中的空闲分区表，系统采用可变式分区管理策略。现有以下作业序列：96K、20K、200K。若采用首次适应算法和最佳适应算法来处理这些作业，试问哪一种算法可以满足作业序列的请求，为什么？,连续存储实例分析,首次适应算法 下

18、次适应算法 最佳适应算法 最差时应算法 快速适应算法,Eg.2、在某系统中，采用固定分区分配管理方式，内存分区（单位字节）情况如下图所示。现有大小为1K、9K、33K、121K的多个作业要求进入内存，试画出它们进入内存后的空间分配情况，并说明主存浪费有多大？,0,20K,28K,60K,180K,512K1,例：在某系统中，采用固定分区分配管理方式，内存分区（单位字节）情况如图所示，现有大小为1K、9K、33K、121K的多个作业要求进入内存，试画出它们进入内存后的空间分配情况，并说明主存浪费多大？,分区说明表,（2）分区说明表,(3)主存浪费空间=(8-1)+(32-9)+(120-33)+

19、(331-121) =7+23+87+210=327(k),解：根据分区说明表，将4个分区依次分配给4个作业，同时修改分区说明表，其内存分配和分区说明表如下所示：,Eg.3给定存储器的划分，依次为：100K、450K、250K、300K和600K，现有4个进程分别依次为：212K、417K、112K、426K。为了在给定的存储空间中安置进程，现有三种算法：首次适应算法、最佳适应算法和最坏适应算法。在这三种算法中，那一种算法更能充分利用存储空间。,分页系统实例分析,问题（1）怎样由页号和页内相对地址物理地址？ （2）地址变换的速度？（访问数据的速度？）,例1、设页面长度为1K，指令load 1,

20、2500的逻辑地址为100。且页表如下所示，求出指令的和数据的物理地址分别是多少？分析访存的次数？如果提高访存速度？,8,2,3,1,2,0,页号 块号,解： （1）为了描述方便，设页号为P，页内位移W，逻辑地址为A，页面大小为L，则： Pint（A/L） W=A mod L 所以：根据上述计算公式有： 指令的页号为：0 页内地址为：100 则由页表： 指令的物理地址为：21k100 数据的页号为：Pint（2500/1024）=2 W=2500 mod 1024=452 则由页表： 数据的物理地址为：81024452,（）需要两次访问内存：其中第一次读取内存页表获取指令或者数据的物理地址，第

21、二次根据物理地址取得相应的指令或者数据。 （3）采用快表并行处理。,例2：设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048字节，内存总共有8个存储块，问逻辑地址至少应该为多少位？内存空间有多大？,参考答案 （1）因为：2101024 2112048 2416 所以：逻辑地址应该为11415位 （2）8204816K,例3：在一分页存储系统中，逻辑地址长度为16位，页面大小为4096字节，现有一逻辑地址为2F6AH，且第0、1、2页依次存放在物理块5、10、11中，问相应的物理地址？,解：因为页面大小为4096 所以需要用12位来表示（2124096）于是用来表示页号的

22、位数为4位。又因为逻辑地址2F6AH的二进制表示为： 0010 111101101010 由上可知：P2 ，对应的块号为11，用十六进制表示块号为B，所以物理地址为：BF6AH,例4、有一页式系统，其页表放在内存中。 （1）如果对主存的一次存取需要1.5微秒，试问实现一次页面访问的存取时间式多少？ （2）如果系统加有快表，平均命中率为85，当页表项在快表中时，其查找时间忽略为0，试问此时的存取时间是多少？,参考答案： （1）因为2次访存，所以时间为21.5 （2）1.5851.5215,计算4,一个有快表的请页式虚存系统，设内存访问周期为1微秒，内外存传送一个页面的平均时间为5毫秒，如果快表命

23、中率为75%，缺页中断率为10%。忽略快表访问时间，试求内存的有效存取时间。,解答： 内存命中率15% 内存的有效存取时间： 175%+215%+(5000+2)10%=501.25微秒,课堂练习 在分页系统中地址结构长度为16位，页面大小为2K，作业地址空间为6K，该作业的各页依次存放在2，3,6 号物理块中,相对地址2500处有一条指令Store 1，4500，请给出该作业的页表，该指令的物理单元地址和数据存放的物理单元地址。,答案,页面大小为2K，即2048字节；作业地址空间6K，则占用页数为3，编号为0、1、2，依次存放在2、3、6号物理块中，作业页表如下： 相对地址为2500字节，应

24、在第2500/2048=1号页面，余数452即为页内位移，所以对应的物理块号为3，得到物理地址为2048*3+452=6596；相对地址4500/2048=2号页面，页内位移为404，对应的物理块号为6，得到物理地址为2048*6+404=12692。,分段系统实例分析,例1、在一个段式存储管理系统中，其段表为：,求下列逻辑地址所对应的物理地址是多少？,参考答案： （1）210+430=640 （2）2350102360 （3）所给逻辑地址非法 （4（5）所给逻辑地址非法 （6）所给逻辑地址非法,参考答案： （1）210+430=640 （2）2350102360 （

25、3）所给逻辑地址非法 （4（5）所给逻辑地址非法 （6）所给逻辑地址非法,（4）实例分析,例题1：在一个请求分页存储管理系统中，一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数分别为3、4时，试计算采用下述页面淘汰算法时的缺页率，并比较其结果。 （1）最佳置换淘汰算法 （2）先进先出淘汰算法 （3）最近最久未使用淘汰算法,解： （1）页面置换情况如下：,缺页率f7/12,缺页率f6/12 增加分配的块数可以降低缺页率,（2）页面置换情况如下：,缺页率f9/12,缺页率f10/12,增加分配的块数反而增加了缺页率，这一现象称为：Belady现象！出现的原因就是没有考虑程序执行的动态性！,（3）页面置换情况如下：,缺页率f10/12,缺页率f8/12 增加分配的块数可以降低缺页率,例题2、有一请求页式存储管理系统，页面大小为每页100字节，有一个505