操作系统(复试)课件

1、操作系统复习南京大学软件学院*2022/8/211复试题型一、单项选择题二、名词解释 三、简答题四、计算题/应用题22022/8/212主要内容第一章：操作系统概述第二/三章：进程和处理机管理、进程同步、互斥、通信与死锁第四章：存储管理第五章：设备管理和I/O系统第六章：文件管理32022/8/213名词解释题型分析第一章（操作系统概述）操作系统的定义 第二/三章（进程）进程 原语 临界资源 第五章（设备管理）虚拟设备第六章（文件）文件系统42022/8/214简答题型分析第一章（操作系统概述）分时操作系统和实时操作系统并发与并行操作系统的四大基本特性 第二/三章（进程）进程与程序 死锁的四大

2、必要条件 第四章（存储管理）分页和分段第五章（设备管理）SPOOLing工作原理第六章（文件系统）FAT32文件系统原理52022/8/215计算题型分析 第二/三章（进程）CPU调度算法 PV操作第四章（存储）连续分配，分区分配：适配算法地址转换计算：分页管理方式；分段管理方式。页面置换算法 第五章（设备管理）磁盘调度算法第六章（文件）文件系统的计算 (多重索引结构)62022/8/216第一章 概述操作系统的定义：操作系统是计算机系统的一个系统软件，它是这样的一些程序模块的集合：他们能有效的组织和管理计算机系统中的硬件及软件资源，合理的组织计算机工作流程，控制程序的执行，并向用户提供各种服

3、务功能， 使得用户能够灵活、方便、有效的使用计算机，使整个计算机系统能高效运行。简单版本：操作系统是一种控制和管理计算机系统硬件和软件资源，合理地组织计算机工作流程以及方便用户的程序集合提供接口：1.用户界面 2.编程接口（API）2022/8/217第一章 概述操作系统的四大基本特性：并发性：同一时间间隔（并行：同一时刻）共享性：系统资源供不同并发进程使用。（磁盘、打印机等）虚拟技术：时分复用技术（多道程序设计）和空分复用技术（页面置换）异步性：并发性导致了异步性，进程控制及同步机制保证了一定同步性（PV）2022/8/218第一章 概述分时操作系统和实时操作系统:分时操作系统（Unix）：

4、 1.人机交互 2.共享主机 3.便于用户上机 实时操作系统 （导弹制导系统）： 1.实时控制 2.实时信息处理 3.高可靠性 2022/8/219第一章 概述分时操作系统和实时操作系统:比较：1.多路性：后者也会有分时原则，但主要体现在系统周期性地对多路现场进行采集，以及对多个对象进行控制。而前者则与用户情况有关，时多时少。 2.及时性：实时信息处理两者类似。实时控制，则后者严格一些。 3.交互性：侧重点不同。 4.可靠性：后者采取多级容错措施来保障系统的安全性及数据的安全性。 2022/8/2110第一章 概述中断技术（很重要但是不好考）：中断是指计算机在执行期间，系统内发生任何不寻常的或

5、者非预期的急需处理的事件，使得CPU暂时中断当前正在执行的程序而转去执行相应的事件处理程序，待处理完毕后又返回原来被中断处继续执行或调度新的进程执行的过程。引起中断发生的事件称为中断源。中断源向CPU发出的请求中断处理信号称为中断请求。CPU收到中断请求后转到相应的事件处理程序的过程称为中断相应。 2022/8/2111第一章 概述硬中断（强迫性中断）：事件不是正在运行的程序所期待的，而是由于某种事故或外部请求信息所引起的。 - 机器故障中断。（掉电，主存储器出错） - 程序性中断。（地址越界，/0） - 外部中断事件。（定时中断，控制台控制信息） - 输入输出中断。（设备出错）软中断（自愿性

6、中断）：事件是正在运行的程序所期待的事件。- 进程的切换 2022/8/2112第一章 概述中断处理过程：1，CPU检查响应中断的条件是否满足。2，如果CPU响应中断，则CPU关中断，使其进入不可再次响应中断的状态。3，保存被中断进程现场。4，分析中断原因，调用中断处理子程序。5，执行中断处理子程序。6，退出中断，回复中断进程的现场或调度,新的进程占据处理机7，开中断，CPU继续执行。 2022/8/2113第二、三章 进程管理进程是一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。进程与线程：（同学就餐）进程是资源分配的基本单位。线程是调度和分派的基本单元。临界资源：是指计算机系

7、统中需要互斥使用的硬件或软件资源，如外设、共享代码段、共享数据结构等。（在一段时间内，只允许一个进程访问的资源）原语：是由若干条指令组成的，不可中断的用于完成一定功能的一个过程。 死锁的四大必要条件：1.互斥条件 2.请求和保持条件 3.不可掠夺 4.循环等待 2022/8/211415进程映像进程控制块：存储进程标志信息、现场信息和控制信息。进程程序块：被执行的程序，规定进程一次运行应完成的功能。通常它是纯代码，作为一种系统资源可被多个进程共享。进程核心栈：每个进程捆绑一个，进程在核心态下工作时使用，用来保存中断/异常现场，及执行函数调用的参数和返回地址，系统调用的参数和返回地址等。进程数据

8、块：即进程私有地址空间，存放各种私有数据，用户栈也在数据块中开辟，用于函数调用时存放栈帧、局部变量等参数，包括程序数据、用户栈和可修改的程序。 进程的描述和组成16程序块数据块PCB进程映像（线程共享）核心栈处理器调度算法FCFS (先来先服务)SPN (最短进程优先)2022/8/2117SPN (最短进程优先)非抢占式调度选择所需处理时间最短的进程短进程将会越过长进程，优先获得调度182022/8/2118SPN (最短进程优先)0510152012345192022/8/2119SPN (最短进程优先)问题只要持续不断地提供更短的进程，长进程就有可能饿死。202022/8/2120例子：

9、假定在单CPU条件下有下列要执行的作业：作业 运行时间 优先级1 10 22 4 33 3 5作业到来的时间是按作业编号顺序进行的（即后面作业依次比前一个作业迟到一个时间单位）。（1）用一个执行时间图描述在分别采用FCFS算法、SPN算法 时执行这些作业的情况。（2）对于上述算法，各个作业的周转时间是多少？平均周转时间是多少？（3）对于上述算法，各个作业的带权周转时间是多少？平均带权周转时间是多少？212022/8/2121PV操作与进程状态转换模型（排队） 运行态就绪态等待态选中落选出现等待事件等待事件结束P(s) 操作V(s) 操作2022/8/2122PV操作与进程状态队列模型（医院例子

10、）处理器指派提交完成超时事件1等待队列事件2等待队列事件n等待队列就绪队列等待事件1等待事件2等待事件n事件1出现事件2出现事件n出现P(s) 操作V(s) 操作2022/8/2123一个生产者/一个消费者/多个缓单元process producerbegin L1: produce a product； P(empty); Bputptr := product； putptr :=(putptr+1) mod k; V(full); goto L1;end;process consumer begin L2: P(full); Product:= Bgetptr； getptr:=(getp

11、tr+1) mod k; V(empty); consume a product； goto L2;end;B : ARRAY0.k-1 of integer;empty: semaphore； /* 可以使用的空缓冲区数 */full: semaphore; /* 缓冲区内可以使用的产品数 */empty := k; /* 缓冲区内允许放入k件产品 */full:= 0; /* 缓冲区内没有产品 */putptr, getptr : integer; putptr:=0; getptr:=0; 2022/8/2124读者/写者问题读者与写者问题(reader-writer problem)

12、(Courtois, 1971)也是一个经典的并发程序设计问题。有两组并发进程：读者和写者，共享一个文件F，要求：(1)允许多个读者可同时对文件执行读操作(2)只允许一个写者往文件中写信息(3)任意写者在完成写操作之前不允许其他读者或写者工作(4)写者执行写操作前，应让已有的写者和读者全部退出使用PV操作求解该问题2022/8/2125读者/写者问题semaphore rmutex，wmutex；rmutex=1; wmutex=1; int readcount=0; /读进程计数process reader_i( ) while (true) P(rmutex); if (readcount

13、=0) P(wmutex); readcount+; V(rmutex); 读文件； P(rmutex); readcount-; if(readcount=0) V(wmutex); V(rmutex); process writer_i( ) while(true) P(wmutex); 写文件； V(wmutex); ? 什么问题读者优先！2022/8/2126哲学家就餐问题(1)有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘于，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子 哲学

14、家顺时针编号01234102342022/8/2127semaphore fork5;for (int i=0;i5;i+)forki=1;cobeginprocess philosopher_i( ) /i= 0,1,2,3,4 while(true) think( ); P(forki);/先取右手的叉子 P(fork(i+1)%5);/再取左手的叉子 eat( ); V(forki); V(fork(i+1)%5); coend哲学家就餐问题存在什么问题？死锁！2022/8/2128 semaphore fork5; for (int i=0;i5;i+) forki= 1;cobegi

15、nprocess philosopher_i( )/*i=0,1,2,3 */while(true) think( );P(forki;/先取右手的叉子 /*i=4,P(fork0)*/P(fork(i+1)%5 ) ; /再取左手的叉子 /*i=4,P(fork4)*/ eat( );V(forki);V(fork(i+ 1 % 5); coend哲学家就餐问题的正确解先取左手的叉子再取右手的叉子2022/8/2129死锁的四个必要条件死锁：是指系统中多个进程无限制的等待永远不会发生的条件。 系统形成死锁的四个必要条件互斥条件(mutual exclusion)：系统中存在临界资源，进程应互

16、斥地使用这些资源占有和等待条件(hold and wait)：进程请求资源得不到满足而等待时，不释放已占有的资源不剥夺条件(no preemption)：已被占用的资源只能由属主释放，不允许被其它进程剥夺循环等待条件(circular wait)：存在循环等待链，其中，每个进程都在链中等待下一个进程所持有的资源，造成这组进程永远等待2022/8/2130银行家算法某一系统进程的资源分配“瞬间状态”为 已分配资源矩阵 最多资源矩阵 可用资源向量 P0 0 0 1 2 0 0 1 2 1 5 2 0 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 6 3 2

17、0 6 5 2 P4 0 0 1 4 0 6 5 6使用银行家算法回答：系统是否安全？如果进程P1要求(0，4，2，0)，系统能否立即满足进程的要求？2022/8/2131第四章 存储管理存储管理的基本原理：内存管理主要包括内存分配和回收、地址变换、内存扩充、内存共享和保护等功能。内存的管理分区（固定分区，可变分区）分页分段段页式2022/8/2132常用的动态分区分配算法（1） （重点 记忆）最先适配法按分区在内存的先后次序从头查找，找到符合要求的第一个分区进行分配。该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端，但是随着低端分区不断划分，会产生较多小分区，每次分配时，

18、查找时间开销便会增大。下次适配法(邻近适配)按分区在内存的先后次序，从上次分配的分区起查找（到最后分区时，再从头开始），找到符合要求的第一个分区进行分配。该算法的分配和释放的时间性能较好，使空闲分区分布得更均匀，但较大的空闲分区不易保留。2022/8/2133常用的动态分区分配算法（2） （重点 记忆）最佳适配法按分区在内存的先后次序从头查找，找到其大小与要求相差最小的空闲分区进行分配。从个别来看，外碎片较小，但从整体来看，会形成较多外碎片。这种方法的优点是较大的空闲分区可以被保留下来。最坏适配法按分区在内存的先后次序从头查找，找到最大的空闲分区进行分配。基本不留下小空闲分区，不易形成外碎片。

19、但由于较大的空闲分区不被保留，因此当有对内存需求较大的进程需要运行时，其要求不易被满足。2022/8/2134适配算法例题在一个分区存储管理系统中，按地址从低到高排列的空闲分区的长度分别是：10KB,4KB,20KB,18KB,7KB,9KB,12KB,15KB.对于下列顺序的段请求：12KB,10KB，15KB，18KB分别使用首次适应算法、下次适应算法和最坏适应算法，对其进行由低到高的地址排序。2022/8/2135页式存储管理的地址转换和存储保护 页表基址寄存器物理地址逻辑地址01p b 页表CPUp db d主存分页存储管理的地址转换2022/8/2136逻辑地址物理地址某虚拟存储器的

20、用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：页号 物理块号0 31 72 113 8则逻辑地址0A5C(H)所对应的物理地址是什么？要求：写出主要计算过程。2022/8/2137多级页表结构的本质多级不连续导致多级索引。以二级页表为例，用户程序的页面不连续存放，要有页面地址索引，该索引是进程页表；进程页表又是不连续存放的多个页表页，故页表页也要页表页地址索引，该索引就是页目录。页目录项是页表页的索引，而页表页项是进程程序的页面索引。2022/8/2138程序的分段结构分段存储管理引入的主要原因模块化程序设计的分段结

21、构分页存储管理-一维地址结构分段存储管理-二维地址结构2022/8/2139分页 vs. 分段区别分页对程序员是不可见的，有内部碎片，无外部碎片分段对程序员通常是可见的，无内部碎片，有外部碎片分段的特点为组织程序和数据的一种方便手段提供给程序员。一般情况下，程序员或编译器把程序和数据指定到不同的段。为了实现模块化程序设计地目的，程序或数据可能进一步分成多个段 2022/8/2140虚拟存储的意义为什么内存不能像磁盘一样大呢？虚拟存储器可定义如下：在具有层次结构存储器的计算机系统中，采用自动实现部分装入和部分替换功能，能从逻辑上为用户提供一个比物理主存容量大得多的，可寻址的一种“主存储器”实际上

22、虚拟存储器对用户隐蔽可用物理存储器的容量和操作细节，它的容量与物理主存大小无关，而受限于计算机的地址结构及可用的磁盘容量，如Intel x86的地址线是32位，则程序可寻址范围是4GB，Windows便为应用进程提供一个4GB的逻辑主存2022/8/2141抖动 如果一块正好将要被用到之前扔出，操作系统有不得不很快把它取回来，太多的这类操作会导致一种称为系统抖动的情况在处理缺页中断期间，处理器的大部分时间都用于交换块，而不是用户进程的执行指令2022/8/2142页面置换已知某程序访问以下页面：0、1、4、2、0、2、6、5、1、2、3、2、1、2、6、2、1、3、6、2，如果程序有3个页框可

23、用且使用下列替换算法，求出现缺页的次数。（1）FIFO替换算法（2）LRU替换算法。2022/8/2143第四章 设备管理（理解即可）程序直接控制（轮询方式）中断驱动方式DMA方式（记忆）虚拟设备：用共享设备来模拟独占设备的操作，从而提高系统的效率和设备利用率。这种技术称为虚拟设备技术，它模拟的设备称为虚拟设备。2022/8/2144455.5.4 搜查定位(1)移臂调度有若干策略 (1)先来先服务算法 (FCFS) (3)“最短查找时间优先”算法(SSTF) (4)“扫描”算法 (SCAN) 2022/8/214546搜查定位(2) 先来先服务算法 磁头臂按照FCFS队列顺序移动，处理队列中

24、的请求，不考虑各I/O请求之间的相对次序和移动臂当前所处位置，进程等待I/O请求的时间会过长，寻道性能较差。 公平2022/8/214647搜查定位(4) SSTF“最短查找时间优先”算法 本算法考虑了各个请求之间的区别，总是先执行查找时间最短的那个磁盘请求，从而，较“先来先服务”算法有较好的寻道性能。存在“饥饿”现象。 2022/8/214748搜查定位(5) “扫描”算法磁头臂每次沿一个方向移动，扫过所有柱面，遇到最近的I/O请求便进行处理，直到最后一个柱面后，再向相反方向移动回来。与“电梯调度”算法的不同在于：即使该移动方向暂时没有I/O请求，移动臂也需扫描到头。“最短查找时间优先”算法

25、虽有较好寻道性能，但可能会造成进程“饥饿”，本算法能克服这一缺点。扫描算法偏爱那些最接近里面或靠外面的请求，对最近扫描跨过去的区域的I/O请求的响应会较慢。 2022/8/214849FCFSIllustration shows total head movement of 640 cylinders.Total=6402022/8/214950SSTF (Cont.)Total=2362022/8/215051SCAN (Cont.)Total=208 回到0点2022/8/2151磁盘调度策略寻道时间是影响性能差异的重要原因一个磁盘可能接收到一组I/O请求如果随机选择并响应这些I/O请求，可能得到最坏的性能2022/8/2152磁盘调度策略先进先出 First-in, first-out (FIFO)按顺序处理请求对于所有进程是公平的2022/8/2153 虚拟设备虚拟设备使用一类物理设备模拟另一类物理设