操作系统期末复习.ppt

《操作系统期末复习.ppt》由会员分享，可在线阅读，更多相关《操作系统期末复习.ppt（48页珍藏版）》请在金锄头文库上搜索。

1、v一、选择题（一、选择题（1010分）分）v二、填空题（二、填空题（2020分）分）v三、名词解释（三、名词解释（1010分）分）v四、简答题（四、简答题（2020分）分）v五、计算题（五、计算题（3030分）分）v六、分析题（六、分析题（1010分）分）考试题型考试题型操作系统复习操作系统复习第一章第一章 操作系统概论操作系统概论第二章第二章 进程与并发控制进程与并发控制第三章第三章 数据存储与管理数据存储与管理第四章第四章 设备与设备与I/OI/O管理管理第五章第五章 文件系统原理与应用文件系统原理与应用第一章第一章 操作系统概论操作系统概论 操作系统的概念；操作系统的概念； 操作系统的基

2、本特征；操作系统的基本特征； 操作系统的主要功能；操作系统的主要功能； 操作系统的发展过程；操作系统的发展过程； 操作系统的分类；操作系统的分类；第二章第二章 进程与并发控制进程与并发控制 进程的基本概念、特征、状态及状态之间的转进程的基本概念、特征、状态及状态之间的转换；进程控制块换；进程控制块 进程控制：进程的创建、终止、阻塞与唤醒、进程控制：进程的创建、终止、阻塞与唤醒、挂起与激活；挂起与激活； 进程同步：进程之间的两种制约关系；进程同步：进程之间的两种制约关系； 同步机制：信号量机制、管程机制；同步机制：信号量机制、管程机制； 经典进程的同步问题；经典进程的同步问题； 进程通信（三种高

3、级通信方式）；进程通信（三种高级通信方式）； 线程；线程； 进程的状态变迁图第二章第二章 进程与并发控制进程与并发控制进程同步的机制进程同步的机制信号量机制信号量机制 记录型信号量：记录型信号量： Type semaphore=record Type semaphore=record value:integervalue:integer; ; L: list of process; L: list of process; end end VarVar S: semaphore; S: semaphore; 用P、V操作解决进程间互斥问题P(mutex)V(mutex)P(mutex)P(mut

4、ex)V(mutex)V(mutex)信号量及P、V操作讨论（演示） 对于两个并发进程，互斥信号量的值仅取1、0和-1三个值 v若s1表示没有进程进入临界区v若s0表示有一个进程进入临界区v若s-1表示一个进程进入临界区，另一个进程等待进入。 第二章第二章 进程与并发控制进程与并发控制waitwait和和signalsignal操作描述：操作描述： wait(Swait(S) )： S.valueS.value:=S.value-1; :=S.value-1; if if S.valueS.value0 then 0 then block(S.Lblock(S.L);); signal(Ssi

5、gnal(S): ): S.valueS.value:=S.value+1; :=S.value+1; if if S.valueS.value=0 then =0 then wakeup(S.Lwakeup(S.L); ); 【练习练习2 2】司机-售票员问题 在一辆公共汽车上，司机和售票员各行其职，司机负责开车和到站停车；售票员负责售票和开、关门，当售票员关好车门后，司机才能继续开车行驶。试用P、V操作实现司机与售票员之间的同步。司司 机机售票员售票员正常行驶正常行驶到站停车到站停车启动车辆启动车辆售售 票票开车门开车门关车门关车门假设汽车正在行进中：假设汽车正在行进中：s1表示是否允许司

6、机启动汽车，初值为表示是否允许司机启动汽车，初值为0；s2表示是否表示是否允许售票员开门，初值为允许售票员开门，初值为0.VAR s1,s2: semaphore:=0,0; 司机活动：司机活动： 售票员活动：售票员活动： Repeat Repeat 正常行驶正常行驶; 售售 票票; 到站停车到站停车; P(S2); V(S2); 开车门开车门; P(S1); 关车门关车门; 启动车辆启动车辆; V(S1); Until false Until false第二章第二章 进程与并发控制进程与并发控制进程同步的例题进程同步的例题1 1： 一条南北方向的公路桥，任何时刻同时只能一条南北方向的公路桥，

7、任何时刻同时只能允许一个方向的汽车通过它。试用允许一个方向的汽车通过它。试用P P、V V操作写出操作写出南或北向的一辆车到达桥，通过它，然后离开它南或北向的一辆车到达桥，通过它，然后离开它到达对岸的同步算法（桥上可有多辆车）。到达对岸的同步算法（桥上可有多辆车）。第二章第二章 进程与并发控制进程与并发控制 设置分别用来计数两组读者数目的计数器变设置分别用来计数两组读者数目的计数器变量量c1c1和和c2c2，初值均为，初值均为0 0；两组读者进程互斥使用临；两组读者进程互斥使用临界资源的互斥信号量界资源的互斥信号量sabsab（初值为（初值为1 1），两组进程），两组进程互斥访问计数器变量互斥

8、访问计数器变量c1c1和和c2c2的互斥信号量的互斥信号量s1s1和和s2s2，初值为，初值为1 1。 分析：本题相当于两组读者进程互斥使用分析：本题相当于两组读者进程互斥使用临界资源，同组的读者进程可同时读，但不同临界资源，同组的读者进程可同时读，但不同组的读者要争夺资源。为两组读者进程各设置组的读者要争夺资源。为两组读者进程各设置一个计数器变量。一个计数器变量。第二章第二章 进程与并发控制进程与并发控制 semaphore sab=1,s1=1,s2=1; int c1=0,c2=0;main() cobegin south(); north(); coend 第二章第二章 进程与并发控制

9、进程与并发控制south()south() wait(s1);wait(s1); if c1=0 then if c1=0 then wait(sabwait(sab);); c1:=c1+1; c1:=c1+1; signal(s1);signal(s1); 上桥上桥; ;过桥过桥; ;下桥下桥; ; wait(s1);wait(s1); c1:=c1-1; c1:=c1-1; if c1=0 then if c1=0 then signal(sabsignal(sab);); signal(s1);signal(s1); north()north() wait(s2);wait(s2);

10、if c2=0 then if c2=0 then wait(sabwait(sab);); c2:=c2+1; c2:=c2+1; signal(s2);signal(s2); 上桥上桥; ;过桥过桥; ;下桥下桥; ; wait(s2);wait(s2); c2:=c2-1; c2:=c2-1; if c2=0 then if c2=0 then signal(sabsignal(sab);); signal(s2);signal(s2); 第二章第二章 进程与并发控制进程与并发控制进程同步的例题：进程同步的例题： 一条南北方向的公路桥，任何时刻同时只能一条南北方向的公路桥，任何时刻同时只

11、能允许一个方向的汽车通过它。试用允许一个方向的汽车通过它。试用P P、V V操作写出操作写出南或北向的一辆车到达桥，通过它，然后离开它南或北向的一辆车到达桥，通过它，然后离开它到达对岸的同步算法（桥上可有多辆车）。到达对岸的同步算法（桥上可有多辆车）。 如果增加一个条件：公路桥的最大载重负荷如果增加一个条件：公路桥的最大载重负荷为为4 4辆汽车，应如何修改？辆汽车，应如何修改？ 增加一个资源信号量增加一个资源信号量countcount，初值为，初值为4 4； 在在“上桥上桥; ;过桥过桥; ;下桥下桥”语句前面加上语句前面加上 wait(countwait(count) )，后面加上，后面加上

12、signal(countsignal(count) )。第二章第二章 进程与并发控制进程与并发控制 三级调度、两种调度方式三级调度、两种调度方式 各种调度算法（各种调度算法（FCFSFCFS、SPF/SJFSPF/SJF、最短剩余时、最短剩余时间优先间优先SRTSRT、RR-Round RobinRR-Round Robin、优先权调度算法、优先权调度算法- -HPFHPF、HRRNHRRN、多级反馈队列调度算法、多级反馈队列调度算法-FB-FB），除最），除最后一种算法外，要求会计算平均周转时间、平均后一种算法外，要求会计算平均周转时间、平均带权周转时间带权周转时间 死锁的概念、产生死锁的原

13、因、产生死锁的死锁的概念、产生死锁的原因、产生死锁的必要条件、处理死锁的方法（死锁的预防、避免、必要条件、处理死锁的方法（死锁的预防、避免、检测和解除）检测和解除）第二章第二章 进程与并发控制进程与并发控制 例题：例题： 设系统中有下述解决死锁的办法：设系统中有下述解决死锁的办法： （1 1）银行家算法）银行家算法 （2 2）检测死锁，终止处于死锁状态的进程，）检测死锁，终止处于死锁状态的进程，释放该进程所占有的资源释放该进程所占有的资源 （3 3）资源预分配）资源预分配 请问哪种办法允许最大的并发性，即哪种办请问哪种办法允许最大的并发性，即哪种办法允许更多的进程无等待地向前推进？请按法允许更

14、多的进程无等待地向前推进？请按“并并发性发性”从大到小对上述三种办法进行排序。从大到小对上述三种办法进行排序。第二章第二章 进程与并发控制进程与并发控制 三种办法中，检测死锁允许更多的进程无等三种办法中，检测死锁允许更多的进程无等待地向前推进。因为该方法允许死锁出现，即允待地向前推进。因为该方法允许死锁出现，即允许进程最大限度地申请并分配资源，直到出现死许进程最大限度地申请并分配资源，直到出现死锁再由系统来解决；锁再由系统来解决； 其次是银行家算法，允许进程动态申请资源，其次是银行家算法，允许进程动态申请资源，只是在进程申请资源时检查系统是否处于安全状只是在进程申请资源时检查系统是否处于安全状

15、态，若是，则分配；若不是，则拒绝分配；态，若是，则分配；若不是，则拒绝分配； 最后是资源预分配，因为预分配要求进程在最后是资源预分配，因为预分配要求进程在运行之前申请所需的全部资源才可以开始运行，运行之前申请所需的全部资源才可以开始运行，这样会使许多进程因得不到资源无法运行。这样会使许多进程因得不到资源无法运行。第二章第二章 进程与并发控制进程与并发控制 例题：例题： 按序分配是预防死锁的一种策略。什么是按序按序分配是预防死锁的一种策略。什么是按序分配？为什么按序分配可以预防死锁？分配？为什么按序分配可以预防死锁？ 答：按序分配是将系统中所有资源按类型进行答：按序分配是将系统中所有资源按类型进

16、行线性排队，并赋予不同的编号，规定所有进程对线性排队，并赋予不同的编号，规定所有进程对资源的请求必须严格按照资源序号递增的次序提资源的请求必须严格按照资源序号递增的次序提出。出。 按序分配可破坏产生死锁的四个必要条件中按序分配可破坏产生死锁的四个必要条件中的的“循环等待条件循环等待条件”，证明如下（反证法）：，证明如下（反证法）：第二章第二章 进程与并发控制进程与并发控制 假设存在一组循环等待的进程：假设存在一组循环等待的进程： P0,P1,P2,P0,P1,P2,PnPn ，其中，其中PiPi拥有资源拥有资源RiRi，RiRi编编号为号为F(RiF(Ri) )，根据按序分配原则，有，根据按序

17、分配原则，有 F(R0)F(R1)F(R0)F(R1)F(RnF(Rn) )， 因存在循环等待，所以因存在循环等待，所以PnPn所申请的下一个资所申请的下一个资源应为源应为P0P0所占的资源所占的资源R0R0；若；若PnPn能正常运行，则应能正常运行，则应依据资源按序分配，即下次申请资源编号应比它依据资源按序分配，即下次申请资源编号应比它所占资源编号大，即有所占资源编号大，即有F(RnF(Rn)F(R0)F(R0)，此结论与不，此结论与不等式中等式中F(R0)F(R0)F(RnF(Rn) )矛盾，所以不存在循环等待。矛盾，所以不存在循环等待。第二章第二章 进程与并发控制进程与并发控制 用银行家

18、算法来避免死锁：用银行家算法来避免死锁： 设设RequestRequesti i是进程是进程PiPi的请求向量，设的请求向量，设RequestRequesti i j =kj =k，表示进程，表示进程PiPi请求分配请求分配RjRj类资源类资源k k个。当进个。当进程程Pi Pi 发出资源请求后，系统按如下步骤进行检查：发出资源请求后，系统按如下步骤进行检查：(1)(1)如如RequestRequesti ijNeedi,jjNeedi,j,转转(2);(2);否则出错，因否则出错，因为进程申请资源量超过它声明的最大量。为进程申请资源量超过它声明的最大量。(2)(2)如如RequestRequ

19、esti ijj AvailablejAvailablej,转转(3);(3);否则表示否则表示资源不够，需等待。资源不够，需等待。第二章第二章 进程与并发控制进程与并发控制 用银行家算法来避免死锁：用银行家算法来避免死锁： (3)(3)系统试分配资源给进程系统试分配资源给进程PiPi，并作如下修改：，并作如下修改：AvailablejAvailablej:= := AvailablejAvailablej- - RequestRequesti ijj Allocationi,jAllocationi,j:= := Allocationi,jAllocationi,j+ + RequestRe

20、questi ijj Needi,jNeedi,j:= := Needi,jNeedi,j- - RequestRequesti ijj (4) (4)系统执行安全性算法，检查此次资源分配后，系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，则正式进行分配，系统是否处于安全状态。若安全，则正式进行分配，否则恢复原状态，让进程否则恢复原状态，让进程PiPi等待。等待。 课本上的例题课本上的例题例例1：4个进程个进程ABCD的到达时间和要求系统的服务时间如下表，的到达时间和要求系统的服务时间如下表，请分析按照请分析按照FCFS算法进行调度时的执行过程，并填写下表。算法进行调度时

21、的执行过程，并填写下表。执行过程如下执行过程如下进程名进程名进程名进程名到达时间到达时间到达时间到达时间服务时间服务时间服务时间服务时间开始执行时间开始执行时间开始执行时间开始执行时间完成时间完成时间完成时间完成时间周转时间周转时间周转时间周转时间带权周转时间带权周转时间带权周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.99ABCD0进程进程时间时间1101102202Wi=Ti / TSTi=T完成完成i-T提交提交i答答：例例1：4个进程个进程ABCD的到达时间和要求系统的服务时间如下表，的到达时间和要求系统的服务

22、时间如下表，请分析按照请分析按照SPF算法进行调度时的执行过程，并填写下表。算法进行调度时的执行过程，并填写下表。执行过程如下执行过程如下进程名进程名到达时间到达时间服务时间服务时间开始执行时间开始执行时间完成时间完成时间周转时间周转时间带权周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.99ABCD0进程进程时间时间1101102202Wi=Ti / TSTi=T完成完成i-T提交提交i答答：例例2：考虑：考虑5个进程个进程P1P2P3P4P5如下表，规定进程的优先数越小优先级越高，如下表，规定进程的优先数越小优先级越

23、高，请分析按照请分析按照 非剥夺式优先级调度非剥夺式优先级调度算法时各进程执行过程，并计算采用每算法算法时各进程执行过程，并计算采用每算法时的平均周转时间（假设忽略进程的调度时间）。时的平均周转时间（假设忽略进程的调度时间）。非剥夺式非剥夺式HPF过程如下过程如下:391318进程进程创建时刻创建时刻运行时间运行时间ms优先数优先数P1033P2265P3441P4652P58240进程进程时间时间P1P2P3P4P520T13-03T29-27T313-49T418-612T520-812T（3+7+9+12+12）58.60Ti=T完成完成i-T提交提交i答答：例例3：设系统中有三种类型的

24、资源（设系统中有三种类型的资源（A、B、C）和五个进程（）和五个进程（P1、P2、P3、P4、P5），当前系统中出现下述资源分配情况：），当前系统中出现下述资源分配情况：AllocationNeedAvailableP00 0 3 2 00 1 2 1 6 2 2P11 0 0 0 17 5 0P21 3 5 4 23 5 6P30 3 3 2 06 5 2P40 0 1 4 06 5 6利用银行家算法，试问：（要求写出判断过程）利用银行家算法，试问：（要求写出判断过程） （1）该状态是否安全？）该状态是否安全？ （2）如果进程）如果进程P2提出资源请求提出资源请求Request（1，2，2，

25、2）后，系统能否将资源分配给它？）后，系统能否将资源分配给它？ 1）此刻安全性分析情况：）此刻安全性分析情况：WorkWorkNeedNeedAllocationAllocationWork+AllocationWork+AllocationFinFinishishP0P0P0P01 1 1 16 6 6 62 2 2 22 2 2 20 0 0 00 0 0 01 1 1 12 2 2 20 0 0 00 0 0 03 3 3 32 2 2 21 1 1 16 6 6 65 5 5 54 4 4 4T T T TP3P3P3P31 1 1 16 6 6 65 5 5 54 4 4 40 0

26、0 06 6 6 65 5 5 52 2 2 20 0 0 03 3 3 33 3 3 32 2 2 21 1 1 19 9 9 98 8 8 86 6 6 6T T T TP4P4P4P41 1 1 19 9 9 98 8 8 86 6 6 60 0 0 06 6 6 65 5 5 56 6 6 60 0 0 00 0 0 01 1 1 14 4 4 41 1 1 19 9 9 99 9 9 910101010T T T TP1P1P1P11 1 1 19 9 9 99 9 9 9101010101 1 1 17 7 7 75 5 5 50 0 0 01 1 1 10 0 0 00 0 0

27、00 0 0 02 2 2 29 9 9 99 9 9 910101010T T T TP2P2P2P22 2 2 29 9 9 99 9 9 9101010102 2 2 23 3 3 35 5 5 56 6 6 61 1 1 13 3 3 35 5 5 54 4 4 43 3 3 3121212121414141414141414T T T T此时存在一个安全序列此时存在一个安全序列P0，P3，P4，P1,P2,故该状态是故该状态是安全安全的。的。 答答：2）P2请求请求Request（1，2，2，2），），按银行家算法检查：按银行家算法检查： RequestRequest（1 1，2 2

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

29、。 第三章第三章 数据存储与管理数据存储与管理 存储器的层次结构存储器的层次结构 内存分配方式：内存分配方式： 连续分配方式（单一连续分配，固定分区分配，连续分配方式（单一连续分配，固定分区分配，动态分区分配，可重定位动态分区分配）动态分区分配，可重定位动态分区分配） 离散分配方式（基本分页存储管理，基本分段离散分配方式（基本分页存储管理，基本分段存储管理，段页式存储管理）存储管理，段页式存储管理） 虚拟存储管理：虚拟存储器、请求分页存储管虚拟存储管理：虚拟存储器、请求分页存储管理（几种页面置换算法）、请求分段存储管理理（几种页面置换算法）、请求分段存储管理第三章第三章 数据存储与管理数据存储

30、与管理 存储器的层次结构存储器的层次结构寄存器寄存器高速缓存高速缓存主存储器主存储器磁盘缓存磁盘缓存固定磁盘固定磁盘可移动存储介质可移动存储介质设置在设置在CPU CPU 和主存储器之和主存储器之间，完成高速与间，完成高速与CPUCPU交换交换信息的信息的SRAMSRAM（静态存储器）（静态存储器），尽量避免，尽量避免CPUCPU不必要地不必要地多次直接访问相对慢速的多次直接访问相对慢速的主存储器，从而提高计算主存储器，从而提高计算机系统的运行效率。机系统的运行效率。硬盘和内存之间的硬盘和内存之间的CacheCache就叫做磁盘高速缓存。就叫做磁盘高速缓存。它是在内存中开辟一块它是在内存中开辟

31、一块位置，来临时存取硬盘位置，来临时存取硬盘中的数据。中的数据。第三章第三章 数据存储与管理数据存储与管理 例题例题1 1： 在分页系统中地址结构长度为在分页系统中地址结构长度为1616位，页面大小位，页面大小为为2K2K，作业地址空间为，作业地址空间为6K6K，该作业的各页依次存，该作业的各页依次存放在放在2 2、3 3、6 6号物理块中，相对地址号物理块中，相对地址25002500处有一条处有一条指令指令store 1,4500store 1,4500，请给出该作业的页表，该指，请给出该作业的页表，该指令的物理单元和数据存放的物理单元。令的物理单元和数据存放的物理单元。第三章第三章 数据存

32、储与管理数据存储与管理 页表长度页表长度页表始址页表始址页内地址页内地址w页号页号(3)wbb01234页表寄存器页表寄存器逻辑地址逻辑地址页表页表物理地址物理地址块号块号页号页号第三章第三章 数据存储与管理数据存储与管理解答：解答： 页号页号物理块号物理块号021326逻辑地址逻辑地址25002500所在页面号为所在页面号为2500 div 2048=12500 div 2048=1，页内地址为，页内地址为2500 mod 2048=4522500 mod 2048=452，查页表，查页表，1 1号页面号页面装入装入3 3号物理块中，所以物理地址为：号物理块中，所以物理地址为：2K*3+45

33、2=65962K*3+452=6596由题目知，数据所在逻辑地址为由题目知，数据所在逻辑地址为45004500，求得，求得页面号为页面号为2 2，页内地址为，页内地址为404404，查页表，对应，查页表，对应的物理块号为的物理块号为6 6，故物理地址为：，故物理地址为：2K*6+404=126922K*6+404=12692页面大小为页面大小为2KB2KB，作业地址空间为，作业地址空间为6KB6KB，该作业，该作业被硬件自动分为被硬件自动分为3 3个页面，页面号分别为个页面，页面号分别为0 0、1 1、2 2，由题目知：各页依次存放在，由题目知：各页依次存放在2 2、3 3、6 6号物理号物理

34、块中，所以页表为：块中，所以页表为：第三章第三章 数据存储与管理数据存储与管理 例题例题2 2： 页面置换算法中有页面置换算法中有LRULRU、FIFOFIFO和最佳页面置换和最佳页面置换算法。针对以下条件，计算上述三个算法下的页算法。针对以下条件，计算上述三个算法下的页面置换过程和缺页中断率：面置换过程和缺页中断率： （1 1）页面访问序列：）页面访问序列：2,3,2,1,5,2,4,5,3,2,5,22,3,2,1,5,2,4,5,3,2,5,2 （2 2）分配内存块数：）分配内存块数：3 3块，开始时块，开始时3 3块都为空块都为空第三章第三章 数据存储与管理数据存储与管理 解答：解答：

35、 LRULRU页面置换算法：页面置换算法： 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 22, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 2xx3x12块块1 1块块2 2块块3 323x2321525125x4254x543x3523523523124缺页中断次数缺页中断次数=7=7；缺页率；缺页率=7/12=7/12缺页否缺页否第三章第三章 数据存储与管理数据存储与管理 解答：解答： FIFOFIFO页面置换算法：页面置换算法： 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 22, 3, 2, 1, 5, 2, 4, 5, 3

36、, 2, 5, 2 2xx3x12块块1 1块块2 2块块3 323x23125125x4254x43x33535234缺页中断次数缺页中断次数=9=9；缺页率；缺页率=9/12=9/125x224x缺页否缺页否第三章第三章 数据存储与管理数据存储与管理 性能比较：性能比较： OPTOPT：理论上性能最优，但无法实现；：理论上性能最优，但无法实现； LRULRU：性能较好，但实现起来困难；：性能较好，但实现起来困难； FIFOFIFO：简单易行，但性能较差。：简单易行，但性能较差。第三章第三章 数据存储与管理数据存储与管理 例题例题3 3： 考虑一个考虑一个500500字的程序的下述逻辑地址访

37、问序列：字的程序的下述逻辑地址访问序列：1010，1111，104104，170170，7373，309309，185185，245245，246246，434434，458458，364364。假定采用页式虚拟内存管理，页面大。假定采用页式虚拟内存管理，页面大小为小为100100字，内存中有字，内存中有2 2个物理块供程序使用，且在个物理块供程序使用，且在开始时物理块没有被任何进程占用。开始时物理块没有被任何进程占用。（1 1）若采用）若采用FIFOFIFO页面置换算法，有关该访问序列的缺页面置换算法，有关该访问序列的缺页中断次数是多少？页中断次数是多少？（2 2）若采用）若采用LRULRU

38、页面置换算法，有关该访问序列的缺页面置换算法，有关该访问序列的缺页中断次数是多少？页中断次数是多少？第四章第四章 设备与设备与I/OI/O管理管理 I/OI/O系统（系统（I/OI/O设备、设备控制器、通道）设备、设备控制器、通道） 总线总线I/OI/O系统，具有通道的系统，具有通道的I/OI/O系统系统 四种四种I/OI/O控制方式控制方式 缓冲管理缓冲管理 I/OI/O软件（设备独立性）软件（设备独立性） 设备分配（设备分配时使用的数据结构、独占设备分配（设备分配时使用的数据结构、独占设备的分配）设备的分配） SPOOLingSPOOLing技术，如何实现虚拟打印机？技术，如何实现虚拟打印

39、机？ 磁盘存储器管理（各种磁盘调度算法）磁盘存储器管理（各种磁盘调度算法）第五章第五章 文件系统原理与应用文件系统原理与应用 文件系统模型文件系统模型 文件的逻辑结构文件的逻辑结构 文件的物理结构（外存分配方式）文件的物理结构（外存分配方式） 目录管理（文件控制块、索引结点、目录结构）目录管理（文件控制块、索引结点、目录结构） 文件存储空间的管理（空闲表法、位示图法、文件存储空间的管理（空闲表法、位示图法、成组链接法）成组链接法） 文件共享（基于索引结点的共享方式、利用符文件共享（基于索引结点的共享方式、利用符号链实现文件共享）号链实现文件共享）1.文件与文件系统的概念文件与文件系统的概念2.

40、文件结构：文件结构：无结构文件无结构文件逻辑结构逻辑结构顺序文件顺序文件有结构文件有结构文件索引文件索引文件索引顺序文件索引顺序文件连续结构连续结构物理结构物理结构链接结构链接结构索引结构索引结构(混合索引）混合索引）第六章第六章文件系统文件系统逻辑结构：以用户观点所观察逻辑结构：以用户观点所观察到的文件组织方式到的文件组织方式物理结构：从实现的观点出物理结构：从实现的观点出发，文件在外存上的存放组发，文件在外存上的存放组织形式织形式例例子子：假假定定磁磁盘盘块块的的大大小小为为1K1K，对对于于540M540M的的磁磁盘盘，其其文文件件分分配配表表FATFAT需需要要占占用用多多少少存存储储

41、空空间间？当当硬硬盘盘容容量量为为1.2G1.2G时时，FATFAT需需要要占用多少空间？占用多少空间？解：硬盘大小解：硬盘大小540M540M，磁盘块大小磁盘块大小1K1K，所以硬盘共有盘块：所以硬盘共有盘块： 540M/1K=540K(540M/1K=540K(个个) )又又 512K540K1024K(512K540K1024K(即即2 21919540K2540K22020) )故故540K540K个个盘盘块块号号要要用用2020位位二二进进制制表表示示，即即FATFAT表表的的每每个个表表目目为为2.52.5字节。字节。FATFAT要占用的存储空间总数为：要占用的存储空间总数为：2.

42、5*540K=1350K2.5*540K=1350K计算计算FATFAT表的开销。表的开销。vvDOSDOSn n对于对于1.2MB1.2MB软盘，盘块大小为软盘，盘块大小为1KB1KB，每个每个FATFAT表项占表项占1212位，在每个位，在每个FATFAT中共中共1.2k1.2k个表项，故共个表项，故共1.8k.1.8k.当硬盘大小为当硬盘大小为1.2G,1.2G,硬盘共有盘块：硬盘共有盘块：1.2G/1K=1.2M(1.2G/1K=1.2M(个个) )又又 1M1.2M2M1M1.2M2M（即即2 220201.2M21.2M22121）故故1.2M1.2M个个盘盘块块号号要要用用212

43、1位位二二进进制制表表示示。为为了了方方便便文文件件分分配配表表的的存存取取，每每个个表表目目用用2424位位表表示示，即即3 3个个字字节节。FATFAT要要占占用用的的存存储空间总数为：储空间总数为：3*1.2M=3.6M3*1.2M=3.6M3.目录管理目录管理1)文件目录：实现按名存取文件目录：实现按名存取2)文文件件控控制制块块：一一个个文文件件目目录录项项，包包含含文文件件名名、文文件件属属性性和和文文件件数数据据在在磁磁盘盘上上的的地地址址等等，是是描述和控制文件的数据结构。描述和控制文件的数据结构。两种组织结构：属性放在目录中；索引结点两种组织结构：属性放在目录中；索引结点3)层次目录系统层次目录系统单级目录：简单、不允许重名单级目录：简单、不允许重名二二级级目目录录：允允许许重重名名、不不允允许许用用户户建建立立自自己己的的子子目录目录树树型型目目录录：提提高高目目录录检检索索速速度度、允允许许重重名名、便便于于实现文件共享实现文件共享目录查询技术（线性）目录查询技术（线性）5.文件的使用：建立、删除、读、写、打开、关闭文件的使用：建立、删除、读、写、打开、关闭6.文件共享：链接（索引结点、符号链接）文件共享：链接（索引结点、符号链接）7.数据的一致性控制数据的一致性控制