武大操作系统复习

1、操作系统n主讲教师：郑鹏n电话Email：操作系统复习操作系统复习n操作系统的基本概念操作系统的基本概念n操作系统的定义操作系统的定义n操作系统的地位操作系统的地位n操作系统的特征操作系统的特征n操作系统的类型操作系统的类型n批处理批处理n分时系统分时系统n实时系统实时系统操作系统复习操作系统复习n进程和线程进程和线程n进程的引入进程的引入n进程的特征：进程的特征：动态性,并发性,独立性,异步性,结构特征n进程的基本状态进程的基本状态n进程的控制进程的控制n线程概念线程概念n进程同步进程同步n互斥和同步互斥和同步n信号量信号量n管程机制管程机制n经典问题经典问题n进程

2、通信进程通信操作系统复习操作系统复习n调度n调度类型n调度算法nFCFSnSJF/SPFnPrioritynRRnHRNnMLQnMFQnFSS操作系统复习操作系统复习n死锁n死锁概念n死锁原因和必要条件n死锁定理n解决死锁的方法n预防n避免n检测n解除操作系统复习操作系统复习n内存管理n基本概念n具体方法n分区分配n伙伴系统n分页n分段n段页式操作系统复习操作系统复习n虚拟存储器n程序局部性原理n请求分页n页面置换nOptimalnFIFOnLRUnClocknPage bufferingn性能分析n请求分段操作系统复习操作系统复习n设备管理n设备组成和分类n输入/输出控制方式nI/O系统结

3、构n缓冲技术n设备分配nI/O软件层次nSPOOLING系统操作系统复习操作系统复习n文件系统n基本概念n逻辑结构与物理结构n外存空间的管理n文件目录n文件共享和保护例题例题-1n生产围棋的工人不小心把相等数量的黑子和白子混装载一个箱子里，现要用自动分拣系统把黑子和白子分开，该系统由两个并发执行的进程组成，功能如下：n（1）进程A专门拣黑子，进程B专门拣白子；n（2）每个进程每次只拣一个子，当一个进程在拣子时不允许另一个进程去拣子；n分析：分析：n第一步：确定进程间的关系。由功能（2）可知进程之间是互斥的关系。n第二步：确定信号量及其值。由于进程A和进程B要互斥进入箱子去拣棋子，箱子是两个进程

4、的公有资源，所以设置一个信号量s，其值取决于公有资源的数目，由于箱子只有一个，s的初值就设为1。例题例题-1n实现：实现：beginbegin s:semaphore; s:semaphore; s:=1; s:=1; cobegincobegin process Aprocess A beginbeginL1: P(s);L1: P(s); 拣黑子；拣黑子； V(s); V(s); gotogoto L1; L1; end; end; coendcoend; ;end;end; process B process B begin begin L2: P(s);L2: P(s); 拣白子；拣白

5、子； V(s); V(s); gotogoto L2; L2; end; end;例题例题-1n在前例的基础之上再添加一个功能：n（3）当一个进程拣了一个棋子（黑子或白子）以后，必让另一个进程拣一个棋子（黑子或白子）。n分析：分析：n第一步：确定进程间的关系。由功能（1）（2）（3）可知，进程间的关系为同步关系。n第二步：确定信号量及其值。进程A和B共享箱子这个公有资源，但规定两个进程必须轮流去取不同色的棋子，因而相互间要互通消息。对于进程A可设置一个私有信号量s1，该私有信号量用于判断进程A是否能去拣黑子，初值为1。对于进程B同样设置一个私有信号量s2，该私有信号量用于判断进程B是否能去拣白

6、子，初值为0。当然也可以设置s1初值为0，s2初值为1。例题例题-1n实现实现: :begin s1,s2:semaphore; s1:=1;s2:=0; cobeginprocess A beginL1: P(s1); 拣黑子; V(s2); goto L1; end; coend; end; process B begin L2: P(s2); 拣白子; V(s1); goto L2; end; 例题例题-2n某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，厅外的购票者可立即进入，否则需要在外面等待。每个购票者可看成一个进程。n分析：第一步：确定进程间的关系

7、。售票厅是各进程共享的公有资源，当售票厅中多于20名购票者时，厅外的购票者需要在外面等待。所以进程间是互斥的关系。第二步：确定信号量及其值。只有一个公有资源：售票厅，所以设置一个信号量s。售票厅最多容纳20个进程，即可用资源实体数为20，s的初值就设为20。n当购票者进入售票厅前要执行P(s)操作，执行后若s大于或等于零，说明售票厅的人数还未满可进入。执行后若s小于零，则说明售票厅的人数已满不能进入。这个实现中同时最多允许20个进程进入售票厅购票，其余进程只能等待。例题例题-2n实现：实现：begins:semaphore; s:=20; cobeginprocess PI(I=1,2,) b

8、egin P(s); 进入售票厅；进入售票厅；购票；购票； 退出；退出； V(s); end; coend;end例题例题-3n设在公共汽车上，司机和售票员的活动分别是：司机：启动车辆，正常行车，到站停车。售票员：上乘客，关车门，售票，开车门，下乘客。用PV操作对其控制。例题例题-3n分析：分析：n第一步：确定进程间的关系。司机到站停车后，售票员方可工作。同样，售票员关车门后，司机才能工作。所以司机与售票员之间是一种同步关系。n第二步：确定信号量及其值。由于司机与售票员之间要互通消息，司机进程设置一个私有信号量run，用于判断司机能否进行工作，初值为0。售票员进程设置一个私有信号量stop，用

9、于判断是否停车，售票员是否能够开车门，初值为0。例题例题-3n实现：begin stop ,run:semaphore stop:=0;run:=0; cobegin driver: begin L1: P(run); 启动车辆； 正常行车； 到站停车； V(stop); goto L1; end;coend;end;conductor: begin L2: 上乘客； 关车门； V(run); 售票； P(stop); 开车门； 下乘客； goto L2; end;例题例题-4n假定某系统有同类资源m个，可被n个进程共享，请问每个进程最多可以申请多少个资源能保证系统一定不会发生死锁？n分析：若

10、某进程获得全部资源，则可完成，不会出现死锁。设每个进程最多可申请x个资源，则n(x-1)+1=m时，不会有死锁。所以x1+m/n。 例题例题-5n下图中，存在死锁吗？例题例题-6n考虑一个请求分页系统,测得如下的时间利用率： CPU:20%, 分页磁盘: 97.7 %,其他外设: 5%.下列措施中哪个(些)可改善CPU的利用率?说明理由。n更换速度更快的CPU；n更换更大容量的分页磁盘;n增加内存中的用户进程数;n挂起内存中某个(些)用户进程;n采取更快的I/O设备。n答：CPU的利用率指的是系统整个运行时间里，CPU有多少时间是真正处理用户的数据运算。由于磁盘利用率已达97.7%，说明磁盘I

11、/O频繁,而影响CPU利用率，更换大容量的磁盘不能提高CPU利用率。慢速外设往往同快速CPU不匹配。因此提高I/O设备的速度，也可以提高CPU的效率。内存中进程数减少，可以提高CPU的利用率。例题例题-7n一个OS有20个进程，竞争使用65个同类资源，申请方式是逐个进行的，一旦某个进程获得它所需要的全部资源，则立即归还所有资源。每个进程最多使用三个资源。若仅考虑这类资源，该系统有无可能产生死锁，为什么？n答：不可能。因为死锁产生的原因有两点：系统资源不足或推进顺序不当，在本题中，进程所需的最大资源数为60，而系统共有该类资源65个，其资源数已足够系统内各进程使用。例题例题-8n死锁和饥饿的主要

12、差别是什么？n答：简言之，死锁是某进程等待一个不会发生的事件的一种现象；而饥饿现象是某进程正等待这样一个事件，它发生了但总是受到其它进程的影响，以至轮不到（或很难轮到）该进程。例题例题-9n设UNIX文件系统中的目录结构如下图所示： bin dev etc lib lost+found mnt tmp usr mengqc liu sub1 m1.c m2.c file_a例题例题-9n(1)设当前工作目录是/usr，那么，访问文件file_a的绝对路径名和相对路径名各是什么？n(2)现在想把工作目录改到liu，应使用什么命令（写出完整命令行）？n(3)如果用 ls l /usr/mengqc

13、命令列出指定目录的内容，其中有如下所示的一项：n- r w r - - - - - 2 mengqc 那么，该文件m2.c对文件主、同组用户、其他用户分别规定了什么权限？例题例题-9n答: n(1) 访问文件file_a的绝对路径名是：n/usr/mengqc/sub1/file_an访问文件file_a的相对路径名是： mengqc/sub1/file_an(2) cd /usr/liu 或者 cd liun(3) 文件主权限是： 可读、可写，但不可执行n 同组用户权限是：只可读n 其他用户权限是：无（即：不能读、写或执行） 例题例题-10n在实现文件系统时，为加快文件目录的检索速度，在实现

14、文件系统时，为加快文件目录的检索速度，可利用可利用“文件控制块分解法文件控制块分解法”。假设目录文件存放。假设目录文件存放在磁盘上，每个盘块在磁盘上，每个盘块512字节。文件控制块占字节。文件控制块占64字字节，其中文件名占节，其中文件名占8字节。通常将文件控制块分解成字节。通常将文件控制块分解成两部分，第两部分，第1部分占部分占10字节（包括文件名和文件内字节（包括文件名和文件内部号），第部号），第2部分占部分占54字节（包括文件内部号和文字节（包括文件内部号和文件其他描述信息）。件其他描述信息）。n（1）假定某一目录文件共有）假定某一目录文件共有254个文件控制块，试分别个文件控制块，试分

15、别给出采用分解法前和分解法后，查找该目录的某一个文件给出采用分解法前和分解法后，查找该目录的某一个文件控制块的平均访问磁盘次数。控制块的平均访问磁盘次数。n（2）一般地，若目录文件分解前占用）一般地，若目录文件分解前占用n个盘块，分解后改个盘块，分解后改用用m个盘块存放文件名和文件内部号，请给出访问磁盘次个盘块存放文件名和文件内部号，请给出访问磁盘次数减少的条件。数减少的条件。例题例题-10n答：n（1）采用分解法前，一个盘块存放5l2/64=8目录项，254个目录项需要32个盘块，查找一个文件的平均访问的盘块数：(1+32)/2=16.5次； 采用分解法后，一个盘块存放5l2/10=51目录

16、项，254个目录项需要5个盘块，查找一个文件的第1部分平均访问的盘块数：(1+5)/2=3次；查找第2部分需要访问磁盘1次，故查找一个文件控制块的平均访问磁盘次数是314次。n（2）访问磁盘次数减少的条件为：（n1）/2（m1）/21 即 mn2 例题例题-11n一个二元信号量是一个其值只能取0、1的信号量，给出一个用二元信号量实现一般信号量p、v操作的程序。例题例题-11n一个二元信号量的值只能是0或1，二元信号量的定义：np（s）：if（s=1）s=0； else 将进程放入等待队列nv（s）：if（队列为空）s=1； else 将等待队列队首进程移出并放入就绪队列例题例题-11n本题使用

17、两个二元信号量及一个变量：nm用来互斥访问变量c，初值为1。nb用来代替信号量S，初值为0。将应挂在信号量S上的进程挂在b上。nc中存放信号量S的值n用二元信号量实现一般信号量S的描述如下：例题例题-11nP(S) p(m)； c=c-1； if (c0) v(m); p(b); else v(m);例题例题-11nV(S) p(m); c=c+1; if (ca0导出的是什么调度算法n（2）ab0导出的是什么调度算法例题例题-15n（1）先来先服务n（2）后进先出例题例题-16n有一个具有两道作业的批处理系统，作业采用短作业优先调度算法，进程调度采用基于优先级的抢占式调度算法。在如下所示的作

18、业序列中，作业优先数即为进程优先数，优先数越小优先级越高。n作业 到达时间 估计运行时间 优先数nA 10：00 40min 5nB 10：20 30min 3nC 10：30 50min 4nD 10：50 20min 6例题例题-16n本题中的作业和进程推进顺序如下：n10:00时，A到达，作业调度将A调入内存，进程调度程序调度它运行。n10:20时，B到达，作业调度将B调入内存，因B的优先级高于A，进程调度暂停A的运行，调度B运行。n10:30时，C到达，因内存中已有两道作业，故C在后备队列中等待。例题例题-16n10:50时，B运行30分钟结束，D到达。因系统中只有A在内存，按短作业优

19、先调度策略，作业D被装入内存，作业C仍在后备队列等待。内存中，A的优先级高于D，A运行。n11:10时，A运行40分钟结束。因系统中只有D在内存，作业调度将C装入内存。因C的优先级高于D，C运行。n12:00时，C运行50分钟结束。D运行。n12:20时，D作业运行20分钟结束。例题例题-16n由上述分析可得出各作业进入内存和结束时间，如下表所示。作业名进入时间结束时间A10:0011:10B10:2010:50C11:1012:00D10:5012:20例题例题-16n各作业执行时的周转时间为：n作业A：70分钟n作业B：30分钟n作业C：90分钟n作业D：90分钟n作业的平均周转时间为：（

20、70309090）/4=70分钟。例题例题-17n考虑一个请求分页系统，测得如下的利用率数据：ncpu利用率20%；分页硬盘的利用率97%；其他I/O设备利用率5%。下列措施中，哪些可改善cpu的利用率？n（1）使用速度更快的cpun（2）使用容量更大的分页硬盘n（3）减少系统内程序的道数n（4）增加系统内程序的道数n（5）使其他外部设备的速度更快第17题n（1）降低利用率n（2）无作用n（3）有作用n（4）可能更低n（5）可能有很小作用例题例题-18n考虑一个请求分页系统，它是用一个分页盘。利用全局LRU置换算法和一种平均分配给进程内存的策略。测得系统的CPU和分页硬盘的利用率为：n（1）c

21、pu利用率13%；盘的利用率为97%；n（2）cpu利用率87%；盘的利用率为3%；n（3）cpu利用率13%；盘的利用率3%；n上述哪种情况可能出现什么问题？能否用增加程序道数来增加CPU利用率？例题例题-19n有一矩阵int a100100按先行后列次序存放，在虚拟页式存储管理中，采用LRU淘汰算法，一个进程有3页内存空间，每页存放200个整数，其中第1页存放程序，且假定程序已在内存，试分别计算程序A和程序B的缺页次数？n程序A 程序B for (i=0;i100;i+) for (j=0;j100;j+) for (j=0;j100;j+) for (i=0;i100;i+) aij=0; aij=0;例题例题-19n因数组以行为主存放，每页可