2012-12计算机操作系统期末总复习.ppt

1、计算机操作系统 期末总复习,2012年12月,操作 系统,基本概念,处理机管理,设备管理,作业管理 用户接口,存储管理,文件管理,操作系统定义 OS的作用 OS特征 OS的主要功能 OS分类 OS结构设计,多道程序设计 进程基本概念 进程同步互斥 进程间通信 进程调度 死锁,I/O系统 I/O控制方式 缓冲技术 I/O软件组成 设备独立性 设备分配 驱动程序 虚设备技术 通道技术 磁盘调度,文件基本概念 文件的逻辑结构 文件的物理结构 文件目录 外存空间管理 文件共享与保护 数据一致性,用户接口 作业基本概念 批处理系统作业管理 分时系统作业管理,程序的装入与链接 存储管理任务 动态分区分配

2、交换技术 页式存储管理 段式存储管理 段页式 虚拟存储技术,批处理操作系统 分时系统 实时操作系统 个人计算机操作系统 网络操作系统 分布式操作系统,操作系统定义,OS功能,OS特征,OS分类,硬件运行环境,操作系统设计,并发 共享 虚拟 异步,有效管理 合理调度 使用方便,吞吐量 时间片 虚机器,操作系统设计目标 操作系统结构设计,CPU状态 系统堆栈 中断技术 时钟 通道 地址映射 存储保护,处理机管理 存储管理 设备管理 文件管理 用户接口,操作系统基本概念,第一章 引论,1、OS的定义与作用 2、三种基本操作系统的基本原理和异同 多道程序设计、时间片轮转法、及时性 3、OS的特征和功能

3、 4、用户接口 5、OS的结构设计,进程 进程状态及转换 进程控制块 系统并发度 进程控制 进程特性 可重入程序,共享内存 消息缓冲 Send/Receive原语 管道通信 信箱,调度算法选择原则 算法： 先进先出 时间片轮转 基于优先数 高响应比优先 抢占式 实时调度技术,进程同步 进程互斥 临界区 进程同步机制 信号量 P、V操作 生产者与消费者问题 读者写者问题 哲学家进餐问题,死锁的有关结论 产生死锁的必要条件 死锁预防 死锁避免 死锁检测解除 资源分配图,多道程序设计,进程基本概念,进程同步互斥,进程间通信,进程调度,死锁,顺序环境 并发环境 与时间有关的错误 不可在现性,进程 管理

4、,第二章 进程管理,1、进程和线程的概念 2、进程的基本状态及状态转换的原因 3、PCB的作用 4、进程控制的原语操作 5、进程互斥、临界区、进程同步的基本概念、同步准则 6、记录型信号量 7、信号量的应用 8、经典进程同步问题；生产者与消费者问题 9、进程间通信的原理和实现方法 信箱,第二章 进程管理的典型问题,进程的三种基本状态及其转变原因。 进程互斥、临界区 三种经典同步问题及其变型 同步约束条件的分析，信号量的初值的设定 单缓冲区的一个生产者一个消费者同步问题 单缓冲区的一个生产者多个消费者同步问题 多个生产者多个消费者多个缓冲区的同步问题,第三章 处理机调度与死锁,1、处理机调度的基

5、本概念和种类 2、选择调度算法的准则，周转时间，带权周转时间，响应时间 3、常见调度算法， 抢占，响应比 4、常见的两种实时调度算法 处理死锁的基本方法 5、死锁产生的原因，四个必要条件 6、死锁的预防 7、利用银行家算法避免死锁 8、死锁的检测与解除,段式存储管理 页式存储管理 段页式存储管理,虚拟存储器 虚拟存储技术 程序局部性原理 虚拟页式管理 虚拟段式管理 页面淘汰算法 抖动（颠簸）,用户程序划分 逻辑地址 内存空间划分 内存分配 管理考虑 硬件支持 地址映射过程,装入与链接 对换技术 覆盖技术,高速缓存 内存 磁盘 系统区 用户区,内存管理分配回收 存储共享 存储保护 内存扩充 地址

6、映射,存储体系,存储管理任务,存储管理方案,虚拟存储管理,其他,存储 管理,第四章 存储管理的重点、难点,重定位的基本概念：为什么要引入 如何提高内存利用率：离散分配、对换机制、动态链接、虚拟存储器、存储器共享 动态分区分配方式：分配、回收算法 基本分页存储管理方式：为什么引入；地址变换机构和过程（含具有快表的情况） 基本分段存储管理方式：为什么引入；地址变换机构和过程（含具有快表的情况）；信息的共享和保护 虚拟存储器的基本概念：为什么要引入；特征；实现虚拟存储的关键技术 请求分页系统的基本原理：页表机制；地址变换过程；页面置换算法,第四章的典型问题,存储器管理的基本任务 动态重定位的概念、实

7、现方式，什么情况下需要重定位 比较连续分配与离散分配 基于空闲分区链的内存分配与回收算法的应用实例：首次适应法，循环首次适应法，最佳适应法 在某分页系统中，给定内存容量和物理块大小，计算物理块的数量；对给定的进程页表，将给定的逻辑地址，计算出其对应的物理地址并画出地址变换流程图。 在某分段系统中对给定的进程段表，将给定的逻辑地址，计算出其对应的物理地址并画出地址变换流程图。 请求分页系统过程的各种问题，并用流程图的方式表示地址变换过程 对给定的问题，按各种页面置换算法，写页面调入过程，计算和分析缺页率，并对多种算法的性能作比较分析,设备管理重要性 设备独立性 设备分类 设备管理任务 设备管理功

8、能,用户进程 与设备无关软件 设备驱动程序 中断处理程序,SPOOLing技术 共享打印机,设备管理 设备分配回收 独占设备分配 共享设备分配,基本概念,I/O软件组成,缓冲技术,设备处理,虚设备技术,设备驱动程序,设备 管理,磁盘访问时间 磁盘调度 先来先服务 最短寻道时间优先 扫描（电梯算法） CSCAN,磁盘存储管理,第五章设备管理的重点、难点,I/O 控制方式：四种I/O 方式的基本原理；四种I/O 方式由低到高效的演变 缓冲管理 缓冲的概念，为什么引入缓冲 单缓冲如何提高I/O 速度，它存在哪些不足，双缓冲、循环缓冲又如何提高CPU 与I/O 设备的并行性 缓冲池是为了解决什么问题而

9、引入，引入缓冲池后系统将如何处理I/O 设备和CPU 间的数据输送 缓冲池的工作方式及Getbuf和Putbuf过程 设备独立性 什么是设备独立性 如何实现设备独立性 设备驱动程序, 纯代码,第五章设备管理的重点、难点,虚拟设备和SPOOLing 技术 什么是虚拟设备 什么是SPOOLing技术，SPOOLing系统的组成 如何利用SPOOLing技术实现共享打印机 磁盘调度 磁盘调度的目标 磁盘访问时间的计算 FCFS、SSTF、SCAN、CSCAN 等算法的应用及这些调度算法的演变过程，分别解决了哪些问题；各算法的性能比较,第五章设备管理的典型问题,各种I/O 控制方式的比较 为什么引入缓

10、冲区 缓冲如何提高I/O 速度 为什么引入设备独立性，如何实现 什么是虚拟设备，实现虚拟设备的关键技术 SPOOLing技术的组成，如何利用SPOOLing 技术实现共享打印机 设备处理程序的功能和处理过程 对各种磁盘调度算法，计算访问次序和平均寻道时间，性能 磁盘访问时间的组成和计算,文件控制块 文件目录 目录文件 目录项 树型目录结构 目录项分解法 目录检索,文件 文件系统 文件分类 文件管理功能 文件逻辑结构 文件物理结构 文件存取方式,外存空间管理 主要数据结构 文件系统使用 文件系统安全、保护、保密、可靠性、一致性,系统打开文件表 用户打开文件表,物理块 磁盘结构 磁带,文件目录,文

11、件基本概念,文件系统实现,存储介质,创建、打开、读写、关闭、删除、拷贝、重命名,文件存取控制,文件 管理,第六章文件管理的重点、难点,文件的逻辑结构：顺序文件、索引文件和索引顺序文件 原理和特征 组织方式、访问方法及各种文件形式的比较 外存分配方式：连续分配、链接分配和索引分配原理、优缺点 显示链接FAT、混合索引分配 目录管理：目录管理的要求 文件控制块（FCB） 索引结点 目录结构：单级、两级和多级 文件磁盘空间管理 空闲表法和空闲链法 位示图法：分配和回收的具体计算 成组链接法,第六章 文件管理的典型问题,画出链接分配方式的链接情况和FAT 的链接情况、FAT长度计算等。 混合索引分配的

12、的寻址方式、地址转换的计算和索引结点的地址映射图 对给定的位示图和文件的分配和回收需求，具体写出分配过程和回收过程。 Unix系统的成组链接法 目录管理的要求；目前广泛采用的目录结构及其优点 说明在树形目录结构中线性检索的过程，并画出相应的流程图 文件的共享,第七章 操作系统接口,联机命令接口 联机命令 终端处理程序 命令解释程序 程序接口 系统调用与一般过程调用的区别 中断与陷入 图形用户接口,选择、填空、判断题,主要考查操作系统课程的基本概念。 以进程的基本概念为主，兼顾其它各章内容。 特别是 Ch2,ch3,ch4三章,名词解释,1.多道程序系统 11.临界资源 2.进程 12.死锁 3

13、.管道 13.最小物理块数 4.进程的静态优先权 14.脱机输入/输出 5.低级调度 15.并发性 6.重定位 16.进程控制块PCB 7.地址变换 17.碎片（内、外） 8.虚拟设备 18.纯代码（可重入代码） 9.进程高级通信（低级通信）19.设备无关性 10.文件控制块（FCB） 20.操作系统,简答题1,1.一个现代操作系统有哪些基本特征。 2.进程有哪三个基本状态，画图说明引起进程状态切换的原因。 3.简述进程同步机制遵循的四条准则。 4.何谓临界资源和临界区? 5.何谓内存分配中的内碎片？ 6.简述分页存储管理系统的请求调页策略。 7.简述段式管理和页式管理的特点。 8.试述缺页中

14、断与一般中断的主要区别。 9.什么是设备的独立性？ 10.最基本的磁盘调度算法有哪三种？每种算法优先考虑的问题是什么？ 11.文件管理中对文件目录管理的要求有哪些？ 12.进行文件的“打开”操作时，为什么需要把进行该操作的用户的用户名作为操作的一个参数？ 13.试述文件的逻辑结构。 14.试述文件存储空间管理中的位示图法。 15.用户与OS之间的接口有哪些方式？它们在什么情况下使用的？,简答题2,1.操作系统的基本功能有哪些？ 2.简述进程的基本特征。 3.简述产生进程死锁的必要条件，以及预防死锁的方法。 4.何谓虚拟存储器? 5.磁盘文件的目录表通常包含哪些内容 ？ 6.简述文件系统中，文件

15、按不同分类方法可以分为哪些种类的文件。 7.简述资源信号量的物理含义。 8.试述分时操作系统的的特征。 9.设备管理中通常采用哪些数据结构。 10.进程实体的组成包含哪三部分？ 11.进程调度通常采取哪两种方式 ？ 12.操作系统为用户提供了哪两类接口？ 13.MSDOS和UNIX系统的命令解释程序分别是什么？ 14.试述请求分页存储管理FIFO页面置换算法中的Belady现象。 15.试述操作系统中设备管理的SPOOLING技术？,计算题,1、作业（进程）的周转时间（平均周转时间、平均等待时间、平均带权周转时间 等）。 先来先服务，短作业/进程优先，时间片轮转，优先权，高响应比优先调度算法，

16、响应比的计算 2、动态分区分配的空闲分区表和内存分配图。 首次适应，循环首次适应，最佳适应，最坏适应等算法 3、内存分页管理中，地址结构的计算。 4、内存分页、分段管理中，将用户地址空间中的逻辑地址变换为内存空间中的物理地址。 页表（段表），地址变换机构,计算题,5、请求分页技术中的页面置换算法，描述内存映象图，并计算出缺页率。 最佳置换OPT、FIFO、LRU等算法 6、磁道访问的调度图以及计算平均寻道长度 FCFS、SSTF、SCAN、CSCAN算法 7、用位示图管理磁盘，计算位示图的组织，实现盘块的分配和回收。 8、画出文件链接分配方式的链接情况和FAT 的链接情况、FAT长度计算等 9

17、、外存空闲空间的成组链接法的分组计算和画成组链接图。,设计题,利用信号量进行进程的同步、互斥的程序设计,设计题,吃水果的同步关系,有个盘子，可以容纳两个水果，每次只能放入或取出一个水果，爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，两个儿子专等吃橘子，两个女儿专等吃苹果。试用信号量的P，V操作实现此过程，并给出信号量和初始值。 分析：盘子是临界资源，而爸爸和妈妈可以同时向其中放水果，因此要设置一个互斥信号量mutex盘子最多容纳两个水果，因此，要对放入盘子的水果进行计数，就是要设置一个信号量empty,初值为2。由于盘子可以放两个水果，即当盘子里有一个水果时，存在即可以放也可以取的情况，因此，除

18、了对放水果进行互斥外，对取水果也要互斥。此外，爸爸和女儿，妈妈和儿子之间存在同步关系，要设置信号量apple和orange实现同步，初值都是0。,begin varmutex=1,empty=2 :semaphore; varapple=0,orange=0:semaphore; cobegin processfather begin repeat p(empty); p(mutex); 放入苹果； v(mutex); v(apple); until false end,processmotherbegin repeat p(empty);p(mutex); 放入橘子； v(mutex); v

19、(orange); until false end,processson-i(i=1,2) begin repeat p(orange); p(mutex); 取橘子； v(mutex); v(empty); until false end,processdaughter-i(i=1,2) begin repeat p(apple); p(mutex); 取苹果； v(mutex); v(empty); until false end coendend,注：要注意盘子的容量，当盘子的容量大于时，不仅要考虑同步，还要考虑互斥。变形后：一个盘子，可以放一个水果，爸爸放苹果，妈妈放香蕉，一个儿子专等

20、吃香蕉，一个女儿专等吃苹果。,排队等候服务的同步关系,税务局缴税大厅有n个柜员,每个纳税人进入缴税大厅后先取一个号,并且等着叫号,当一个柜员空闲后，就叫下一个号。试用信号量的P，V操作实现此过程，并给出信号量和初始值。 分析:将纳税人号码排成一个队列,纳税人进入缴税大厅领取号码后,将号码由队尾插入;柜员空闲时,从队首取得纳税人号码,并且为这个纳税人服务,由于队列为若干进程共享,所以需要互斥。柜员空闲时,若有纳税人,就叫下一个纳税人为之服务。因此,需要设置一个信号量来记录等待服务的纳税人数。,int mutex=1, taxpayer_count=0: semaphore; Taxpayer()

21、 while(1) 取号码； P（mutex）； 进入队列； V（mutex）； V（taxpayer_count） Servers(i=1.n) while(1) P(taxpayer_count); P（mutex）； 从队列中取下一个号码； V（mutex）； 为该号码持有者服务； ,已知某分页系统，主存容量为64K，页面大小为1K，对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。 （1）将十进制的逻辑地址1023、2500、3500、4500转换成物理地址？ （2）以十进制的逻辑地址1023为例画出地址变换过程图？,计算题例子1,答： 逻辑地址1023：10

22、23/1K，得页号为0，页内地址为1023，查页表找到对应的物理块号为2，故物理地址为21K+1023=3071 逻辑地址2500：2500/1K，得页号为2，页内地址为452，查页表找到对应的物理块号为6，故物理地址为61K+452=6596 逻辑地址3500：3500/1K，得页号为3，页内地址为428，查页表找到对应的物理块号为7，故物理地址为71K+428=7596 逻辑地址4500：4500/1K，得页号为4，页内地址为404，因页号不小于页表长度，故产生越界中断。,（2）地址变换过程图,计算题例子2,假定系统为某进程分配了3个物理块，进程运行时的页面走向为 1,2,3,4,1,2,

23、5,1,2,3,4,5 开始时3个物理块均为空，给出下列置换算法时页面置换情况(画出置换图内存映象图 )，并计算出该算法的缺页率？ （1）先进先出淘汰算法（FIFO）； （2）最近最久未使用淘汰算法（LRU）。,（1）采用FIFC置换算法：缺页率=9/12=0.75 。置换图如下：,（2）采用LRU置换算法：缺页率=10/12=0.83 。置换图如下：,一个磁盘系统，平均寻道时间为12ms，转速为10000转/分，每个磁道有18个扇区，每个扇区512个字节。请问要读取一个扇区所花的时间是多少？ 解： TA = TS + TR + TT= TS + 1/2r + b/rN TS = 12ms T

24、R = 1/2r = 60100000.5 = 3ms TT = b/rN = (51260)(1851210000)= 0.33ms TA = TS + TR + TT =12 + 3 + 0.33 = 15.33ms 读取一个扇区所花的时间是15.33ms。,计算题例子3,计算题例子4,设某磁盘有200个柱面，编号为0，1，2，199，磁头刚从140磁道移到143磁道完成了读写。若某时刻有9个磁盘请求分别对如下各磁道进行读写： 86，147，91，177，94，150，102，175，130 试分别求SSTF及SCAN磁盘调度算法响应请求的次序(调度图)、磁头移动的总距离及平均寻道长度 。

25、,（1）采用SSTF算法调度时，磁头（磁盘存取移动臂）移动的顺序为： 143147150130102949186175177 磁头移动的总距离为： （147-143）+（177-175）=162（柱面） 平均寻道长度=162/9=18 （柱面） （2）采用SCAN算法调度时，磁头（磁盘存取移动臂）移动的顺序为： 143147150175177130102949186 磁头移动的总距离为： （147-143）+（91-86）=125（柱面） 平均寻道长度=125/9=13.89（柱面）,解：,计算题例子5,假定盘块的大小为1KB,硬盘的大小为500MB,采用显示链接分配方式时,其FAT需占用多少

26、存储空间（FAT表项占2.5个字节）? 如果文件A占用硬盘的11, 12 , 16, 14四个盘块,试画出文件A中各盘块在FAT表中的链接情况。,解：此时硬盘共有500M/1K=500K个盘块， FAT表项共有500K 2.5B=1250KB,FAT,FCB,计算题例子6,存放在某个磁盘上的文件系统，对于采用混合索引分配方式，其FCB中共有13项地址项，第09个地址项为直接地址，第10个地址项为一次间接地址，第11个地址项为二次间接地址，第12个地址项为三次间接地址。如果每个盘块的大小为512字节，若盘块号需要3个字节来描述，而每个盘块最多存放170个盘块地址： (1) 该文件系统允许的最大长

27、度是多少？ (2) 将文件的字节偏移量5000、15000转换为物理块号和块内偏移量。 (3) 假设某文件的索引结点已在内存中，但其他信息均在外存，为了访问该文件中某个位置的内容，最多需要几次访问磁盘？,图 混合索引方式,混合索引分配方式,（1）文件的最大长度为： 10+170+1702+1703=4942080块=2471040KB （2）5000/512得商9，余数为392。即逻辑块号为9，块内偏移为392。故可直接从该文件的FCB的第9个地址处得到物理盘块号，块内偏移为392。 15000/512得商为29，余数为152。即逻辑块号为29，块内偏移为152。由于102910+170,而29-10-19，故可从FCB的第10个地址项，即一次间址项中得到一次间址块；并从一次间址块的19项中获得对应的物理盘块号，块内偏移为152。 (3) 由于文件的索引结点已在内存，为了访问文件中的某个位置的内容，最少需要1次访问磁盘（即通过直接地址直接读文件盘块），最多需要4次访问磁盘（第一次是读三次间址块，第二次读二次间址块，第三次读一次间