《期末复习例题汇总》由会员分享，可在线阅读，更多相关《期末复习例题汇总（82页珍藏版）》请在金锄头文库上搜索。
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都能并行工作，优先级从高到低为J
2、ob1、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空闲段：30
3、ms-50ms，故I2的利用率为： （90-20）/90100%=77.78%,思考题,假定有4个程序，每个程序花费80%的时间执行I/O，20%的时间使用CPU。每个程序的启动时间和其需要使用CPU进行计算的分钟数如下表所示。 试计算4个程序执行完成所需要的时间（响应时间）分别是多少？系统的平均响应时间是多少？与单道执行环境相比，系统平均响应时间节约了多少分钟？并分析每个程序以80%（I/O）和20%（CPU）的资源占有情况进行运行，在不考虑内存容量的情况下，当程序道数为多少的时候CPU的利用率是最高的？并总结在多道程序设计环境下CPU利用率的计算公式。,参考答案,http:/ http:/
4、 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+a)+(b
5、+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/5,题3、设有两
7、个处理机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 所以P2比P1处理速度快,
8、（2）当P0.9时， P1的平均存取时间为：60（10.9）1000160ns P2的平均存取时间为：80（10.9）0.91000170ns 所以P1比P2处理速度快,思考与设计,请根据下列情况，试设计一个合适的调度算法，以期能满足各类用户的需要，并能较好体现“CPU世界的公平性”，并总结调度算法的设计经验。,进程,优先级：,执行时间：1ms 5ms；20ms 40ms5ms 30ms,例：设实时系统从两个不同的数据源DA和DB周期性地收集数据并进行处理（DA周期为30ms，DB周期为75ms），相应数据如下表所示：采用结束时限越近的优先权越高。,给出调度顺序和相应的时间调度图,实例分析,E
9、g.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);else signal（Sa）； ,类似题目拓展：,类似
10、 （1）桌上有一个盘子，最多可以容纳两个水果，每次只能放入或取出一个水果。爸爸专向盘子中放入苹果（apple），妈妈专向盘子中放入桔子（orange），两个儿子专等吃盘中的桔子，两个女儿专等吃盘子中的苹果。请用P、V操作来实现爸爸、妈妈、儿子、女儿之间的同步互斥关系。,int mutex=1; int empty=2; int apple=0; int orange=0; main( ) cobeginfather( );mother( );son( );daughter( );coend ,Father()while(1)p (empty);p (mutex);向盘中放苹果；v（mutex）
11、；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）桌上有一个盘子，可以存放一个水果，爸爸专向盘子中放入苹果，妈妈专向盘子中放入香蕉，一个儿子专等吃盘中的香蕉，一个女儿专等吃盘子中的苹果。请用P、V操作来实现爸爸、妈妈、儿子、女
12、儿之间的同步互斥关系。,int mutex=1; int apple=0; int banana=0; main( ) cobeginfather( );mother( );son( );daughter( );coend ,Father()while(1)p (mutex);向盘中放苹果；V（apple）； ,mother()while(1)p (mutex);向盘中放香蕉；V（banana）； ,soni()while(1)p (banana);取盘中香蕉；v（mutex）； i1、2,daughteri()while(1)p (apple);取盘中苹果；v（mutex）； i1、2,解：
13、设信号量empty1、empty2分别表示缓冲区1和缓冲区2是否为空，其初值为1，full1、full2分别表示缓冲区1和缓冲区2是否有记录可供处理，其初值为0。请描述同步PA、PB、PC之间的同步关系。,2、,Eg.2,Eg.3、下面是两个并发执行的进程。它们能正确运行吗？若不能。请举例说明，并改正之。,解答： 它们不能正确运行。因为题中的P1、P2之间有一个共享变量X，由于进程的并发执行，可能会产生与时间有关的错误。（X变量的值会被修改），为了保证P1、P2能正确执行，必须设置一互斥信号量。程序改正如下：,Parbeginvar X:integer;mutex：semaphore;mutex:=1;process P1var y,z:integer;beginP(mutex);x:=1;y:=0;if x=1 then y:=y+1;V(mutex);z:=y;end,process P2Var t,u:integer;beginP(mutex);x:=0t:=0;if x Available (0,1,1)P4的请求向量超过系统的可用资源向量，故P4的请求不能满足。进程P4阻塞等待请读者考虑，如果T0时刻，进程P4申请资源，其请求向量为Request4(0,1,0),系统是否能将资源分配给它。,
