[工学]操作系统期末复习.pptVIP

一、选择题（10分） 二、填空题（20分） 三、名词解释（10分） 四、简答题（20分） 五、计算题（30分） 六、分析题（10分）,考试题型,操作系统复习,第一章 操作系统概论 第二章 进程与并发控制 第三章 数据存储与管理 第四章 设备与I/O管理 第五章 文件系统原理与应用,第一章 操作系统概论,操作系统的概念； 操作系统的基本特征； 操作系统的主要功能； 操作系统的发展过程； 操作系统的分类；,第二章 进程与并发控制,进程的基本概念、特征、状态及状态之间的转换；进程控制块 进程控制：进程的创建、终止、阻塞与唤醒、挂起与激活； 进程同步：进程之间的两种制约关系； 同步机制：信号量机制、管程机制； 经典进程的同步问题； 进程通信（三种高级通信方式）； 线程；,进程的状态变迁图,第二章 进程与并发控制,进程同步的机制信号量机制 记录型信号量： Type semaphore=record value:integer; L: list of process; end Var S: semaphore;,用P、V操作解决进程间互斥问题,信号量及P、V操作讨论（演示）,对于两个并发进程，互斥信号量的值仅取1、0和-1三个值 若s1表示没有进程进入临界区 若s0表示有一个进程进入临界区 若s-1表示一个进程进入临界区，另一个进程等待进入。,第二章 进程与并发控制,wait和signal操作描述： wait(S)： S.value:=S.value-1; if S.value0 then block(S.L); signal(S): S.value:=S.value+1; if S.value=0 then wakeup(S.L);,【练习2】司机-售票员问题 在一辆公共汽车上，司机和售票员各行其职，司机负责开车和到站停车；售票员负责售票和开、关门，当售票员关好车门后，司机才能继续开车行驶。试用P、V操作实现司机与售票员之间的同步。,司 机,售票员,正常行驶,到站停车,启动车辆,售 票,开车门,关车门,假设汽车正在行进中： s1表示是否允许司机启动汽车，初值为0；s2表示是否 允许售票员开门，初值为0. VAR s1,s2: semaphore:=0,0; 司机活动： 售票员活动： Repeat Repeat 正常行驶; 售 票; 到站停车; P(S2); V(S2); 开车门; P(S1); 关车门; 启动车辆; V(S1); Until false Until false,第二章 进程与并发控制,进程同步的例题1： 一条南北方向的公路桥，任何时刻同时只能允许一个方向的汽车通过它。试用P、V操作写出南或北向的一辆车到达桥，通过它，然后离开它到达对岸的同步算法（桥上可有多辆车）。,第二章 进程与并发控制,设置分别用来计数两组读者数目的计数器变量c1和c2，初值均为0；两组读者进程互斥使用临界资源的互斥信号量sab（初值为1），两组进程互斥访问计数器变量c1和c2的互斥信号量s1和s2，初值为1。,分析：本题相当于两组读者进程互斥使用临界资源，同组的读者进程可同时读，但不同组的读者要争夺资源。为两组读者进程各设置一个计数器变量。,第二章 进程与并发控制,semaphore sab=1,s1=1,s2=1; int c1=0,c2=0; main() cobegin south(); north(); coend ,第二章 进程与并发控制,south() wait(s1); if c1=0 then wait(sab); c1:=c1+1; signal(s1); 上桥;过桥;下桥; wait(s1); c1:=c1-1; if c1=0 then signal(sab); signal(s1); ,north() wait(s2); if c2=0 then wait(sab); c2:=c2+1; signal(s2); 上桥;过桥;下桥; wait(s2); c2:=c2-1; if c2=0 then signal(sab); signal(s2); ,第二章 进程与并发控制,进程同步的例题： 一条南北方向的公路桥，任何时刻同时只能允许一个方向的汽车通过它。试用P、V操作写出南或北向的一辆车到达桥，通过它，然后离开它到达对岸的同步算法（桥上可有多辆车）。 如果增加一个条件：公路桥的最大载重负荷为4辆汽车，应如何修改？,增加一个资源信号量count，初值为4； 在“上桥;过桥;下桥”语句前面加上 wait(count)，后面加上signal(count)。,第二章 进程与并发控制,三级调度、两种调度方式 各种调度算法（FCFS、SPF/SJF、最短剩余时间优先SRT、RR-Round Robin、优先权调度算法-HPF、HRRN、多级反馈队列调度算法-FB），除最后一种算法外，要求会计算平均周转时间、平均带权周转时间 死锁的概念、产生死锁的原因、产生死锁的必要条件、处理死锁的方法（死锁的预防、避免、检测和解除）,第二章 进程与并发控制,例题： 设系统中有下述解决死锁的办法： （1）银行家算法 （2）检测死锁，终止处于死锁状态的进程，释放该进程所占有的资源 （3）资源预分配 请问哪种办法允许最大的并发性，即哪种办法允许更多的进程无等待地向前推进？请按“并发性”从大到小对上述三种办法进行排序。,第二章 进程与并发控制,三种办法中，检测死锁允许更多的进程无等待地向前推进。因为该方法允许死锁出现，即允许进程最大限度地申请并分配资源，直到出现死锁再由系统来解决；,其次是银行家算法，允许进程动态申请资源，只是在进程申请资源时检查系统是否处于安全状态，若是，则分配；若不是，则拒绝分配；,最后是资源预分配，因为预分配要求进程在运行之前申请所需的全部资源才可以开始运行，这样会使许多进程因得不到资源无法运行。,第二章 进程与并发控制,例题： 按序分配是预防死锁的一种策略。什么是按序分配？为什么按序分配可以预防死锁？ 答：按序分配是将系统中所有资源按类型进行线性排队，并赋予不同的编号，规定所有进程对资源的请求必须严格按照资源序号递增的次序提出。 按序分配可破坏产生死锁的四个必要条件中的“循环等待条件”，证明如下（反证法）：,第二章 进程与并发控制,假设存在一组循环等待的进程： P0,P1,P2,Pn，其中Pi拥有资源Ri，Ri编号为F(Ri)，根据按序分配原则，有 F(R0)F(R1)F(Rn)， 因存在循环等待，所以Pn所申请的下一个资源应为P0所占的资源R0；若Pn能正常运行，则应依据资源按序分配，即下次申请资源编号应比它所占资源编号大，即有F(Rn)F(R0)，此结论与不等式中F(R0)F(Rn)矛盾，所以不存在循环等待。,第二章 进程与并发控制,用银行家算法来避免死锁： 设Requesti是进程Pi的请求向量，设Requesti j =k，表示进程Pi请求分配Rj类资源k个。当进程Pi 发出资源请求后，系统按如下步骤进行检查： (1)如RequestijNeedi,j,转(2);否则出错，因为进程申请资源量超过它声明的最大量。 (2)如Requestij Availablej,转(3);否则表示资源不够，需等待。,第二章 进程与并发控制,用银行家算法来避免死锁： (3)系统试分配资源给进程Pi，并作如下修改： Availablej:= Availablej- Requestij Allocationi,j:= Allocationi,j+ Requestij Needi,j:= Needi,j- Requestij (4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，则正式进行分配，否则恢复原状态，让进程Pi等待。 课本上的例题,例1：4个进程ABCD的到达时间和要求系统的服务时间如下表，请分析按照FCFS算法进行调度时的执行过程，并填写下表。,执行过程如下,1,101,102,202,Wi=Ti / TS,Ti=T完成i-T提交i,答：,例1：4个进程ABCD的到达时间和要求系统的服务时间如下表，请分析按照SPF算法进行调度时的执行过程，并填写下表。,执行过程如下,1,101,102,202,Wi=Ti / TS,Ti=T完成i-T提交i,答：,例2：考虑5个进程P1P2P3P4P5如下表，规定进程的优先数越小优先级越高，请分析按照 非剥夺式优先级调度算法时各进程执行过程，并计算采用每算法时的平均周转时间（假设忽略进程的调度时间）。,非剥夺式HPF过程如下:,3,9,13,18,20,T13-03,T29-27,T313-49,T418-612,T520-812,T（3+7+9+12+12）58.60,Ti=T完成i-T提交i,答：,例3：设系统中有三种类型的资源（A、B、C）和五个进程（P1、P2、P3、P4、P5），当前系统中出现下述资源分配情况：,利用银行家算法，试问：（要求写出判断过程） （1）该状态是否安全？ （2）如果进程P2提出资源请求Request（1，2，2，2）后，系统能否将资源分配给它？,1）此刻安全性分析情况：,此时存在一个安全序列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）已不能满足任何进程的需要，故系统进入不安全状态，所以系统不能将资源分配给它。,第三章 数据存储与管理,存储器的层次结构 内存分配方式： 连续分配方式（单一连续分配，固定分区分配，动态分区分配，可重定位动态分区分配） 离散分配方式（基本分页存储管理，基本分段存储管理，段页式存储管理） 虚拟存储管理：虚拟存储器、请求分页存储管理（几种页面置换算法）、请求分段存储管理,第三章 数据存储与管理,存储器的层次结构,设置在CPU 和主存储器之间，完成高速与CPU交换信息的SRAM（静态存储器），尽量避免CPU不必要地多次直接访问相对慢速的主存储器，从而提高计算机系统的运行效率。,硬盘和内存之间的Cache就叫做磁盘高速缓存。它是在内存中开辟一块位置，来临时存取硬盘中的数据。,第三章 数据存储与管理,例题1： 在分页系统中地址结构长度为16位，页面大小为2K，作业地址空间为6K，该作业的各页依次存放在2、3、6号物理块中，相对地址2500处有一条指令store 1,4500，请给出该作业的页表，该指令的物理单元和数据存放的物理单元。,第三章 数据存储与管理,第三章 数据存储与管理,解答：,逻辑地址2500所在页面号为 2500 div 2048=1，页内地址为 2500 mod 2048=452，查页表，1号页面 装入3号物理块中，所以物理地址为： 2K*3+452=6596 由题目知，数据所在逻辑地址为4500，求得页面号为2，页内地址为404，查页表，对应的物理块号为6，故物理地址为： 2K*6+404=12692,页面大小为2KB，作业地址空间为6KB，该作业被硬件自动分为3个页面，页面号分别为0、1、2，由题目知：各页依次存放在2、3、6号物理块中，所以页表为：,第三章 数据存储与管理,例题2： 页面置换算法中有LRU、FIFO和最佳页面置换算法。针对以下条件，计算上述三个算法下的页面置换过程和缺页中断率： （1）页面访问序列：2,3,2,1,5,2,4,5,3,2,5,2 （2）分配内存块数：3块，开始时3块都为空,第三章 数据存储与管理,解答： LRU页面置换算法： 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2,2,x,x,3,x,1,2,块1,块2,块3,2,3,x,2,3,2,1,5,2,5,1,2,5,x,4,2,5,4,x,5,4,3,x,3,5,2,3,5,2,3,5,2,3,1,2,4,缺页中断次数=7；缺页率=7/12,缺页否,第三章 数据存储与管理,解答： FIFO页面置换算法： 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2,2,x,x,3,x,1,2,块1,块2,块3,2,3,x,2,3,1,2,5,1,2,5,x,4,2,5,4,x,4,3,x,3,3,5,3,5,2,3,4,缺页中断次数=9；缺页率=9/12,5,x,2,2,4,x,缺页否,第三章 数据存储与管理,性能比较： OPT：理论上性能最优，但无法实现； LRU：性能较好，但实现起来困难； FIFO：简单易行，但性能较差。,第三章 数据存储与管理,例题3： 考虑一个500字的程序的下述逻辑地址访问序列：10，11，104，170，73，309，185，245，246，434，458，364。假定采用页式虚拟内存管理，页面大小为100字，内存中有2个物理块供程序使用，且在开始时物理块没有被任何进程占用。 （1）若采用FIFO页面置换算法，有关该访问序列的缺页中断次数是多少？ （2）若采用LRU页面置换算法，有关该访问序列的缺页中断次数是多少？,第四章 设备与I/O管理,I/O系统（I/O设备、设备控制器、通道） 总线I/O系统，具有通道的I/O系统 四种I/O控制方式 缓冲管理 I/O软件（设备独立性） 设备分配（设备分配时使用的数据结构、独占设备的分配） SPOOLing技术，如何实现虚拟打印机？ 磁盘存储器管理（各种磁盘调度算法）,第五章 文件系统原理与应用,文件系统模型 文件的逻辑结构 文件的物理结构（外存分配方式） 目录管理（文件控制块、索引结点、目录结构） 文件存储空间的管理（空闲表法、位示图法、成组链接法） 文件共享（基于索引结点的共享方式、利用符号链实现文件共享）,1. 文件与文件系统的概念 2. 文件结构： 无结构文件 逻辑结构 顺序文件 有结构文件 索引文件 索引顺序文件 连续结构 物理结构 链接结构 索引结构(混合索引）,第六章 文件系统,逻辑结构：以用户观点所观察到的文件组织方式,物理结构：从实现的观点出发，文件在外存上的存放组织形式,例子：