计算机操作系统课件

“操作系统原理”课程

总复习（10级）

一、期末试卷组成题型分数单项选择题10分析解答题20应用题60综合题10合计100二、各教学单元比重引论(1章)5’处理机管理(2,3章)33’存储器管理(4章)19’设备管理(5章)12’文件管理(6章)

19’操作系统接口(7章)

2’综合

（全书）10’三、教材中删除章节1.53.44.3.4-4.3.74.8.3-4.8.46.6-6.7第8章及以后四、需掌握的典型算法及应用1.调度算法（范围：先来先服务、短优先、非剥夺式优先级）2.银行家算法3.页面置换算法（范围：先进先出、理想型、最近最久未使用）4.页式管理之地址变换5.磁盘调度算法（范围：先来先服务、最短寻道时间优先、SCAN）6.位示图的分配回收7.FAT计算8.i结点混合索引

9.进程同步控制—生产者-消费者问题及变形10.SPOLLING及应用、成组链接法例1：4个进程ABCD的到达时间和要求系统的服务时间如下表，请分析按照FCFS算法进行调度时的执行过程，并填写下表。执行过程如下进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.99ABCD0进程时间1101102202Wi=Ti/TSTi=T完成i-T提交i答：例1：4个进程ABCD的到达时间和要求系统的服务时间如下表，请分析按照SPF算法进行调度时的执行过程，并填写下表。执行过程如下进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.99ABCD0进程时间1101102202Wi=Ti

/TSTi=T完成i-T提交i答：例2：考虑5个进程P1P2P3P4P5如下表，规定进程的优先数越小优先级越高，请分析按照非剥夺式优先级调度算法时各进程执行过程，并计算采用每算法时的平均周转时间（假设忽略进程的调度时间）。非剥夺式HPF过程如下:391318进程创建时刻运行时间／ms优先数P1033P2265P3441P4652P58240进程时间P1P2P3P4P520T1＝3-0＝3T2＝9-2＝7T3＝13-4＝9T4＝18-6＝12T5＝20-8＝12T＝（3+7+9+12+12）／5＝8.60Ti=T完成i-T提交i答：例3：设系统中有三种类型的资源（A、B、C）和五个进程（P1、P2、P3、P4、P5），当前系统中出现下述资源分配情况：AllocationNeedAvailableP0003200121622P110001750P213542356P303320652P400140656利用银行家算法，试问：（要求写出判断过程）（1）该状态是否安全？（2）如果进程P2提出资源请求Request（1，2，2，2）后，系统能否将资源分配给它？1）此刻安全性分析情况：WorkNeedAllocationWork+AllocationFinishP01622001200321654TP31654065203321986TP419860656001419910TP1199101750100029910TP229910235613543121414T此时存在一个安全序列{P0，P3，P4，P1,P2},故该状态是安全的。答：2）P2请求Request（1，2，2，2），按银行家算法检查：①

Request（1，2，2，2）≤Need（2，3，5，6）

②Request（1，2，2，2）≤Available（1，6，2，2）

答：

试分配,并修改相应的数据结构，资源分配情况如下：再利用安全性算法检查系统状态是否安全，可利用资源向量Available（0，4，0，0）已不能满足任何进程的需要，故系统进入不安全状态，所以系统不能将资源分配给它。

例4：请求分页系统中一进程P共有10页，系统为其在内存中分配三个物理块，初始均为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5。当采用FIFO置换算法时，计算访问过程中发生的缺页中断率。内存缺页？4，3，2，1，4，3，5，4，3，2，1，5443432132214143321是是是是是是是435否435435否是352是521否521共缺页中断9次，缺页中断率为：9／12＝75％为了方便找出先进来的那个页，采用模拟队列的写法更方便例4：请求分页系统中一进程P共有10页，系统为其在内存中分配三个物理块，初始均为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5。当采用OPT置换算法时，计算访问过程中发生的缺页中断率。内存缺页？4，3，2，1，4，3，5，4，3，2，1，5443432431431431是是是是否否是435否435435否是235是215否215共缺页中断7次，缺页中断率为：7／12＝58.3％例4：请求分页系统中一进程P共有10页，系统为其在内存中分配三个物理块，初始均为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5。当采用LRU置换算法时，计算访问过程中发生的缺页中断率。内存缺页？4，3，2，1，4，3，5，4，3，2，1，5443432132142143是是是是是是是543否543543否是243是213是215共缺页中断10次，缺页中断率为：10／12＝83.3％例5：一个分页式存储管理系统中，用户虚拟空间共有32个页面，每页1KB，假定某时刻用户的第0，1，2，3页分别分配的物理块号为10，8，4，17，求：（1）逻辑地址的有效位是多少？并给出逻辑地址的结构。（2）将逻辑地址（2500）D转换为物理地址。答：1）逻辑地址的有效位数是15位。

逻辑地址结构表示：

例5：一个分页式存储管理系统中，用户虚拟空间共有32个页面，每页1KB，假定某时刻用户的第0，1，2，3页分别分配的物理块号为10，8，4，17，求：（1）逻辑地址的有效位是多少？并给出逻辑地址的结构。（2）将逻辑地址（2500）D转换为物理地址。答：2）对逻辑地址（2500）D：P＝int（2500／1K）＝2W＝2500％1K＝452由已知，页号P＝2对应的页面号P’＝4，逻辑（2500）D对应物理地址＝P’×1K＋W＝（4548）D

例6：针对某盘面的磁盘服务请求顺序如下:55,58,39,18,90,160,150,38,184号磁道(当前磁头在100号磁道上且向增加方向移动).分析按先来先服务、最短寻道时间优先、扫描算法执行的顺序及平均寻道距离。总寻道距离如下:|55-100|+|58-55|+|39-58|+|18-39|+|90-18|+|160-90|+|150-160|+|38-150|+|184-38|=498平均寻道距离:498/9=55.3先来先服务满足请求的次序是55，58，39，18，90，160，150，38，184

总寻道距离如下:|90-100|+|58-90|+|55-58|+|39-55|+|38-39|+|18-38|+|150-18|+|160-150|+|184-160|=248平均寻道距离:248/9=27.55例6：针对某盘面的磁盘服务请求顺序如下:55,58,39,18,90,160,150,38,184号磁道(当前磁头在100号磁道上且向增加方向移动).分析按先来先服务、最短寻道时间优先、扫描算法执行的顺序及平均寻道距离。最短寻道时间优先满足请求的次序是90，58，55，39，38，18，150，160，184

例6：针对某盘面的磁盘服务请求顺序如下:55,58,39,18,90,160,150,38,184号磁道(当前磁头在100号磁道上且向增加方向移动).分析按先来先服务、最短寻道时间优先、扫描算法执行的顺序及平均寻道距离。扫描算法总寻道距离如下:|150-100|+|160-150|+|184-160|+|90-184|+|58-90|+|55-58|+|39-55|+|38-39|+|18-38|=250平均寻道距离:250/9=27.8满足请求的次序是150，160，184，90，58，55，39，38，18

位示图利用一个二进制位反映磁盘空间中每个块的分配使用情况。每个物理块对应一个Bit位,一般，已分配物理块为1，未分配为0。

m×n大小的位示图可以表示的磁盘总块数为m╳n。位示图可以用二维数组描述：map[m,n]1.盘块的分配

(1)顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。(2)将所找到的一个或一组二进制位，转换成与之相应的盘块号。假定找到的其值为“0”的二进制位，位于位示图的第i行、第j列，则其相应的盘块号应按下式计算：b=n(i-1)+j式中，n代表每行的位数。(3)修改位示图，令map［i,j］=1。位示图2.盘块的回收

(1)将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为：

i=(b-1)DIVn+1j=(b-1)MODn+1(2)修改位示图。令map［i,j］=0。位示图

b=n×i+j+1

i=(b-1)DIVn

j=(b-1)MODn位示图注意：若行列号均从0开始编号，盘块号从1开始编号。则：例7:某文件系统采用半字节寻址方式，如果磁盘容量为500MB，盘块大小为1KB，采用显式链接分配方式时，问：1）每个FAT表项需占多少二进制位？其FAT需占多少存储空间？2）如果文件A依次占用11、23、25号盘块，画出A中各盘块间的链接情况及FAT的情况。答：1）盘块个数为500MB/1KB＝500K（个）由FAT表项个数与磁盘块个数的对应关系可知，FAT共有500K个表项（表项编号为0～500K-1）

256K<500K<512K,每个FAT表项最少用19位二进制表示，若系统限定采用半字节寻址，则可扩展为20位。FAT表空间大小＝20b/8b×500K=1250KBFAT表每项位数需扩展到8的倍数，即24位二进制表示请你思考：若系统限定采用单字节寻址呢？

FATA的FCB

112325文件名：A首块号：11............

2325EOF......答：2）图示如下：例7:某文件系统采用半字节寻址方式，如果磁盘容量为500MB，盘块大小为1KB，采用显式链接分配方式时，问：1）每个FAT表项需占多少二进制位？其FAT需占多少存储空间？2）如果文件A依次占用11、23、25号盘块，画出A中各盘块间的链接情况及FAT的情况。例8:存放在某磁盘上的文件系统采用混合索引分配方式，文件的FCB中共有13个地址项，其中第0—9项是直接地址，第10、11、12项分别是一次、二次、三次间接地址。设每个盘块的大小为1K字节，一个盘块号占4字节。问：1）该系统允许一个文件最多可以占用多少个磁盘块的空间？2）若文件所有信息均在外存，描述访问文件中字节偏移量为263168的信息的过程？并指出该过程中需要启动磁盘几次？答：1）每个盘块最多存放1KB/4B=256个盘块地址该系统允许一个文件最多可以使用磁盘块的个数为：

10+256+2562+2563块2）若文件所有信息均在外存，描述访问文件中字节偏移量为263168的信息的过程？并指出该过程中需要启动磁盘几次？偏移量263168/1024=257

所以字节偏移量263168对应逻辑块号为257，块内偏移量为0，由于10<257<266，而257-10=247，故可以直接从文件的FCB的第10个地址项处得到一次间址块的地址，并从一次间址块的第247项中获得对应得物理盘块号，到该块块内偏移量为0处访问即可。该过程中需要启动磁盘3次。例9:操作系统在键盘管理中引入了键盘缓冲区，键盘缓冲区采用循环队列，键盘输入进程pin负责将用户键入的字符存入缓冲区，键盘输出进程pout负责从缓冲区