操作系统(复试)

1、7:101操作系统复习南京大学软件学院南京大学软件学院7:107:102复试题型 一、单项选择题 二、名词解释 三、简答题 四、计算题/应用题27:103主要内容主要内容 第一章：操作系统概述第一章：操作系统概述 第二第二/ /三章：进程和处理机管理、进程同步、互斥、通信与三章：进程和处理机管理、进程同步、互斥、通信与死锁死锁 第四章：存储管理第四章：存储管理 第五章：设备管理和第五章：设备管理和I/OI/O系统系统 第六章：文件管理第六章：文件管理37:104名词解释题型分析名词解释题型分析第一章（操作系统概述）第一章（操作系统概述） 操作系统的定义操作系统的定义 第二第二/ /三章（进程）

2、三章（进程） 进程进程 原语原语 临界资源临界资源 第五章（设备管理）第五章（设备管理） 虚拟设备虚拟设备第六章（文件）第六章（文件） 文件系统文件系统47:105简答题型分析简答题型分析第一章（操作系统概述）第一章（操作系统概述） 分时操作系统和实时操作系统分时操作系统和实时操作系统 并发与并行并发与并行 操作系统的四大基本特性操作系统的四大基本特性 第二第二/ /三章（进程）三章（进程） 进程与程序进程与程序 死锁的四大必要条件死锁的四大必要条件 第四章（存储管理）第四章（存储管理） 分页和分段分页和分段第五章（设备管理）第五章（设备管理） SPOOLingSPOOLing工作原理工作原理

3、第六章（文件系统）第六章（文件系统） FAT32FAT32文件系统原理文件系统原理57:106计算题型分析计算题型分析 第二第二/ /三章（进程）三章（进程） CPUCPU调度算法调度算法 PVPV操作操作第四章（存储）第四章（存储） 连续分配，分区分配：适配算法连续分配，分区分配：适配算法 地址转换计算：分页管理方式；分段管理方式。地址转换计算：分页管理方式；分段管理方式。 页面置换算法页面置换算法 第五章（设备管理）第五章（设备管理） 磁盘调度算法磁盘调度算法第六章（文件）第六章（文件） 文件系统的计算文件系统的计算 ( (多重索引结构多重索引结构) )67:107第一章 概述 操作系统的

4、定义：操作系统是计算机系统的一个系统软件，它是这样的一些程序模块的集合：他们能有效的组织和管理计算机系统中的硬件及软件资源，合理的组织计算机工作流程，控制程序的执行，并向用户提供各种服务功能， 使得用户能够灵活、方便、有效的使用计算机，使整个计算机系统能高效运行。简单版本：操作系统是一种控制和管理计算机系统硬件和软件资源，合理地组织计算机工作流程以及方便用户的程序集合提供接口：1.用户界面 2.编程接口（API）7:108第一章 概述 操作系统的四大基本特性：并发性：同一时间间隔（并行：同一时刻）共享性：系统资源供不同并发进程使用。（磁盘、打印机等）虚拟技术：时分复用技术（多道程序设计）和空分

5、复用技术（页面置换）异步性：并发性导致了异步性，进程控制及同步机制保证了一定同步性（PV）7:109第一章 概述 分时操作系统和实时操作系统:分时操作系统（Unix）： 1.人机交互 2.共享主机 3.便于用户上机 实时操作系统 （导弹制导系统）： 1.实时控制 2.实时信息处理 3.高可靠性 7:1010第一章 概述 分时操作系统和实时操作系统:比较：1.多路性：后者也会有分时原则，但主要体现在系统周期性地对多路现场进行采集，以及对多个对象进行控制。而前者则与用户情况有关，时多时少。 2.及时性：实时信息处理两者类似。实时控制，则后者严格一些。 3.交互性：侧重点不同。 4.可靠性：后者采取

6、多级容错措施来保障系统的安全性及数据的安全性。 7:1011第一章 概述 中断技术（很重要但是不好考）：- 中断是指计算机在执行期间，系统内发生任何不寻常的或者非预期的急需处理的事件，使得CPU暂时中断当前正在执行的程序而转去执行相应的事件处理程序，待处理完毕后又返回原来被中断处继续执行或调度新的进程执行的过程。- 引起中断发生的事件称为中断源。- 中断源向CPU发出的请求中断处理信号称为中断请求。- CPU收到中断请求后转到相应的事件处理程序的过程称为中断相应。 7:1012第一章 概述 硬中断（强迫性中断）：事件不是正在运行的程序所期待的，而是由于某种事故或外部请求信息所引起的。 - 机器

7、故障中断。（掉电，主存储器出错） - 程序性中断。（地址越界，/0） - 外部中断事件。（定时中断，控制台控制信息） - 输入输出中断。（设备出错） 软中断（自愿性中断）：事件是正在运行的程序所期待的事件。- 进程的切换 7:1013第一章 概述 中断处理过程：1，CPU检查响应中断的条件是否满足。2，如果CPU响应中断，则CPU关中断，使其进入不可再次响应中断的状态。3，保存被中断进程现场。4，分析中断原因，调用中断处理子程序。5，执行中断处理子程序。6，退出中断，回复中断进程的现场或调度,新的进程占据处理机7，开中断，CPU继续执行。 7:1014第二、三章 进程管理 进程是一个具有一定独

8、立功能的程序在一个数据集合上的一次动态执行过程。 进程与线程：（同学就餐）进程是资源分配的基本单位。线程是调度和分派的基本单元。 临界资源：是指计算机系统中需要互斥使用的硬件或软件资源，如外设、共享代码段、共享数据结构等。（在一段时间内，只允许一个进程访问的资源） 原语：是由若干条指令组成的，不可中断的用于完成一定功能的一个过程。 死锁的四大必要条件：1.互斥条件 2.请求和保持条件 3.不可掠夺 4.循环等待 15进程映像进程映像 进程控制控制块：存储进程标志标志信息、现场现场信息和控制控制信息。 进程程序程序块：被执行的程序，规定进程一次运行应完成的功能。通常它是纯代码，作为一种系统资源可

9、被多个进程共享。 进程核心栈核心栈：每个进程捆绑一个，进程在核心态下工作时使用，用来保存中断/异常现场，及执行函数调用的参数和返回地址，系统调用的参数和返回地址等。 进程数据块数据块：即进程私有地址空间，存放各种私有数据，用户栈也在数据块中开辟，用于函数调用时存放栈帧、局部变量等参数，包括程序数据、用户栈和可修改的程序包括程序数据、用户栈和可修改的程序。 进程的描述和组成进程的描述和组成16程序块程序块数据块数据块PCBPCB进程映像进程映像（线程共享）核心栈核心栈7:1017处理器调度算法 FCFS (先来先服务先来先服务) SPN (最短进程优先最短进程优先)7:1018SPN (最短进程

10、优先) 非抢占式非抢占式调度调度 选择选择所需处理时间最短所需处理时间最短的进程的进程 短进程短进程将会越过长进程，将会越过长进程，优先优先获得调度获得调度187:1019SPN (最短进程优先)0510152012345197:1020SPN (最短进程优先) 问题问题 只要持续不断地提供更短的进程，长进程就有可能饿死。只要持续不断地提供更短的进程，长进程就有可能饿死。207:1021例子： 假定在单假定在单CPU条件下有下列要执行的作业：条件下有下列要执行的作业： 作业作业 运行时间运行时间 优先级优先级 1 10 2 2 4 3 3 3 5 作业到来的时间是按作业编号顺序进行的（即后面作

11、业依次比前一个作作业到来的时间是按作业编号顺序进行的（即后面作业依次比前一个作业迟到一个时间单位）。业迟到一个时间单位）。 （1）用一个执行时间图描述在分别采用）用一个执行时间图描述在分别采用FCFS算法、算法、SPN算法算法 时执行这时执行这些作业的情况。些作业的情况。 （2）对于上述算法，各个作业的周转时间是多少？平均周转时间是多）对于上述算法，各个作业的周转时间是多少？平均周转时间是多少？少？ （3）对于上述算法，各个作业的带权周转时间是多少？平均带权周转）对于上述算法，各个作业的带权周转时间是多少？平均带权周转时间是多少？时间是多少？217:1022PV操作与进程状态转换模型（排队）

12、运行态就绪态等待态选中落选出现等待事件等待事件结束P(s) 操作V(s) 操作7:1023PV操作与进程状态队列模型（医院例子）处理器处理器指派指派提交提交完成完成超时超时事件事件1 1等待队列等待队列事件事件2 2等待队列等待队列事件事件n n等待队列等待队列就绪队列就绪队列等待事件等待事件1 1等待事件等待事件2 2等待事件等待事件n n事件事件1 1出现出现事件事件2 2出现出现事件事件n n出现出现P(s) 操作V(s) 操作7:1024一个生产者一个生产者/一个消费者一个消费者/多个缓单元多个缓单元process producerbegin L1: produce a product

13、； P(empty); Bputptr := product； putptr :=(putptr+1) mod k; V(full); goto L1;end;process consumer begin L2: P(full); Product:= Bgetptr； getptr:=(getptr+1) mod k; V(empty); consume a product； goto L2;end;B : ARRAY0.k-1 of integer;empty: semaphore； /* 可以使用的空缓冲区数 */full: semaphore; /* 缓冲区内可以使用的产品数 */emp

14、ty := k; /* 缓冲区内允许放入k件产品 */full:= 0; /* 缓冲区内没有产品 */putptr, getptr : integer; putptr:=0; getptr:=0; 7:1025读者/写者问题 读者与写者问题(reader-writer problem) (Courtois, 1971)也是一个经典的并发程序设计问题。有两组并发进程：读者和写者，共享一个文件F，要求： (1)允许多个读者可同时对文件执行读操作 (2)只允许一个写者往文件中写信息 (3)任意写者在完成写操作之前不允许其他读者或写者工作 (4)写者执行写操作前，应让已有的写者和读者全部退出 使用PV

15、操作求解该问题7:1026读者/写者问题semaphore rmutex，wmutex；rmutex=1; wmutex=1; int readcount=0; /读进程计数process reader_i( ) while (true) P(rmutex); if (readcount=0) P(wmutex); readcount+; V(rmutex); 读文件； P(rmutex); readcount-; if(readcount=0) V(wmutex); V(rmutex); process writer_i( ) while(true) P(wmutex); 写文件； V(wm

16、utex); ? 什么问题读者优先！7:1027哲学家就餐问题(1) 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘于，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子 哲学家顺时针编号哲学家顺时针编号01234102347:1028semaphore fork5;for (int i=0;i5;i+)forki=1;cobeginprocess philosopher_i( ) /i= 0,1,2,3,4 while(true) think( ); P(forki);/先取右手的叉子 P

17、(fork(i+1)%5);/再取左手的叉子 eat( ); V(forki); V(fork(i+1)%5); coend哲学家就餐问题存在什么问题？存在什么问题？死锁！死锁！7:1029 semaphore fork5; for (int i=0;i5;i+) forki= 1;cobeginprocess 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)

18、;V(fork(i+ 1 % 5); coend哲学家就餐问题的正确解哲学家就餐问题的正确解先取左手的叉子先取左手的叉子再取右手的叉子再取右手的叉子7:1030死锁的四个必要条件死锁死锁：是指系统中：是指系统中多个进程无限制的等待多个进程无限制的等待永远不会发生永远不会发生的条件。的条件。 系统形成死锁的四个必要条件 互斥条件(mutual exclusion)：系统中存在临界资源，进程应互斥地使用这些资源 占有和等待条件(hold and wait)：进程请求资源得不到满足而等待时，不释放已占有的资源 不剥夺条件(no preemption)：已被占用的资源只能由属主释放，不允许被其它进程剥

19、夺 循环等待条件(circular wait)：存在循环等待链，其中，每个进程都在链中等待下一个进程所持有的资源，造成这组进程永远等待7:1031银行家算法 某一系统进程的资源分配“瞬间状态”为 已分配资源矩阵 最多资源矩阵 可用资源向量 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 0 6 5 2 P4 0 0 1 4 0 6 5 6 使用银行家算法回答：系统是否安全？如果进程P1要求(0，4，2，0)，系统能否立即满足进程的要求？7:1032第四章 存储管理存储管理的基本原理：内存管理

20、主要包括内存分配和回收、地址变换、内存扩充、内存共享和保护等功能。内存的管理分区（固定分区，可变分区）分页分段段页式7:1033常用的动态分区分配算法（1） （重点 记忆） 最先适配法最先适配法 按分区在内存的先后次序从头查找，找到符合要求的第一个分区进行分配。该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端，但是随着低端分区不断划分，会产生较多小分区，每次分配时，查找时间开销便会增大。 下次适配法下次适配法( (邻近适配邻近适配) ) 按分区在内存的先后次序，从上次分配的分区起查找（到最后分区时，再从头开始），找到符合要求的第一个分区进行分配。该算法的分配和释放的时间性能

21、较好，使空闲分区分布得更均匀，但较大的空闲分区不易保留。7:1034常用的动态分区分配算法（2） （重点 记忆） 最佳适配法最佳适配法 按分区在内存的先后次序从头查找，找到其大小与要求相差最小的空闲分区进行分配。从个别来看，外碎片较小，但从整体来看，会形成较多外碎片。这种方法的优点是较大的空闲分区可以被保留下来。 最坏适配法最坏适配法 按分区在内存的先后次序从头查找，找到最大的空闲分区进行分配。基本不留下小空闲分区，不易形成外碎片。但由于较大的空闲分区不被保留，因此当有对内存需求较大的进程需要运行时，其要求不易被满足。7:1035适配算法例题在一个分区存储管理系统中，按地址从低到高排列的空闲分

22、区的长度分别是：10KB,4KB,20KB,18KB,7KB,9KB,12KB,15KB.对于下列顺序的段请求：12KB,10KB，15KB，18KB分别使用首次适应算法、下次适应算法和最坏适应算法，对其进行由低到高的地址排序。7:1036页式存储管理的地址转换和存储保护 页表基址寄存器物理地址逻辑地址01p b 页表CPUp db d主存分页存储管理的地址转换7:1037逻辑地址物理地址某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：页号 物理块号0 31 72 113 8则逻辑地址0A5C(H)所对应

23、的物理地址是什么？要求：写出主要计算过程。7:1038多级页表结构的本质 多级不连续多级不连续导致多级索引多级索引。 以二级页表为例以二级页表为例，用户程序的页面不连续存放，要有页面地址索引，该索引是进程页表；进程页表又是不连续存放的多个页表页页表页，故页表页也要页表页地址索引，该索引就是页目录。页目录。 页目录项页目录项是页表页的索引，而页表页项是进程程序的页面索引。7:1039程序的分段结构 分段存储管理引入的主要原因 模块化程序设计的分段结构 分页分页存储管理-一维地址结构 分段分段存储管理-二维地址结构7:1040分页分页 vs. 分段分段 区别区别 分页对程序员是分页对程序员是不可见

24、的，有内部碎片，无外部碎片不可见的，有内部碎片，无外部碎片 分段对程序员通常是分段对程序员通常是可见的，无内部碎片，有外部碎片可见的，无内部碎片，有外部碎片 分段的特点分段的特点 为组织程序和数据的一种方便手段提供给程序员。一般情况下，程序员为组织程序和数据的一种方便手段提供给程序员。一般情况下，程序员或编译器把程序和数据指定到不同的段。为了实现模块化程序设计地目或编译器把程序和数据指定到不同的段。为了实现模块化程序设计地目的，程序或数据可能进一步分成多个段的，程序或数据可能进一步分成多个段 7:1041虚拟存储的意义虚拟存储的意义 为什么内存不能像磁盘一样大呢？ 虚拟存储器可定义如下：在具有

25、层次结构存储器的计算机系统中，采用自动实现部分装入和部分替换功能，能从逻辑上为用户提供一个比物理主存容量大得多的，可寻址的一种“主存储器” 实际上虚拟存储器对用户隐蔽可用物理存储器的容量和操作细节，它的容量与物理主存大小无关，而受限于计算机的地址结构及可用的磁盘容量，如Intel x86的地址线是32位，则程序可寻址范围是4GB，Windows便为应用进程提供一个4GB的逻辑主存7:1042抖动抖动 如果一块正好将要被用到之前扔出，操作系统有不得不很快如果一块正好将要被用到之前扔出，操作系统有不得不很快把它取回来，太多的这类操作会导致一种称为系统抖动的情把它取回来，太多的这类操作会导致一种称为

26、系统抖动的情况况 在处理缺页中断期间，处理器的大部分时间都用于交换块，在处理缺页中断期间，处理器的大部分时间都用于交换块，而不是用户进程的执行指令而不是用户进程的执行指令7:1043页面置换已知某程序访问以下页面：0、1、4、2、0、2、6、5、1、2、3、2、1、2、6、2、1、3、6、2，如果程序有3个页框可用且使用下列替换算法，求出现缺页的次数。（1）FIFO替换算法（2）LRU替换算法。7:1044第四章 设备管理 （理解即可） 程序直接控制（轮询方式） 中断驱动方式 DMA方式 （记忆） 虚拟设备虚拟设备：用共享设备来模拟独占设备的操作，从而提高系统的效率和设备利用率。这种技术称为虚

27、拟设备技术，它模拟的设备称为虚拟设备。7:1045455.5.4 搜查定位(1)移臂调度有若干策略 (1)先来先服务算法 (FCFS) (3)“最短查找时间优先”算法(SSTF) (4)“扫描”算法 (SCAN) 7:104646搜查定位(2) 先来先服务算法 磁头臂磁头臂按照FCFS队列顺序移动，处理队列中的请求，不考虑各I/O请求之间的相对次序和移动臂当前所处位置，进程等待I/O请求的时间会过长，寻道性能较差。 公平公平7:104747搜查定位(4) SSTF“最短查找时间优先最短查找时间优先”算法算法 本算法考虑了各个请求之间的区别，总是先执行查找时间最短的那个磁盘请求，从而，较“先来先

28、服务”算法有较好的寻道性能。存在“饥饿”现象。 7:104848搜查定位(5) “扫描扫描”算法算法 磁头臂每次沿一个方向移动，扫过所有柱面，遇到最近的I/O请求便进行处理，直到最后一个柱面后，再向相反方向移动回来。 与“电梯调度”算法的不同在于：即使该移动方向暂时没有I/O请求，移动臂也需扫描到头。“最短查找时间优先”算法虽有较好寻道性能，但可能会造成进程“饥饿”，本算法能克服这一缺点。扫描算法偏爱那些最接近里面或靠外面的请求，对最近扫描跨过去的区域的I/O请求的响应会较慢。 7:104949FCFSIllustration shows total head movement of 640

29、cylinders.Total=6407:105050SSTF (Cont.)Total=2367:105151SCAN (Cont.)Total=208 回到0点7:1052磁盘调度策略磁盘调度策略 寻道时间是影响性能差异的重要原因寻道时间是影响性能差异的重要原因 一个磁盘可能接收到一组一个磁盘可能接收到一组I/OI/O请求请求 如果随机选择并响应这些如果随机选择并响应这些I/OI/O请求，可能得到最坏的性能请求，可能得到最坏的性能7:1053磁盘调度策略磁盘调度策略 先进先出先进先出 First-in, first-out (FIFO) 按顺序处理请求按顺序处理请求 对于所有进程是公平的对于所有进程是公平的7:1054 虚拟设备虚拟设备 虚拟设备虚拟设备 使用一类物理设备模拟另一类物理设备的技术使用一类物理设备模拟另一类物理设备的技术 通常是使用共享型外围设备模拟独占型外围设备通常是使用共享型外围设备模拟独占型外围设备 （虚存，磁盘存储技术）（虚存，磁盘存储技术）7:105555SPOOLing “井井”是用作缓冲的存储区域，采用井的技术能调节供求之是用作缓冲的存储区域，采用井的技术能调节供求之间的矛盾，消除人工干预