操作系统期末复习

1、第三章：处理机调度与死锁3.1：高级调度对象是作业，作用是将作业从外存调入内存； 低级调度的对象是进程，作用是决定哪个进程将获得处理机而运行。常见的低级调度有非抢占方式和抢占方式两种抢占式调度主要有以下原则优先权原则:重要作业赋予高优先权,优先占用处理机短作业(进程)优先原则:执行时间短的进程优先执行时间片原则:时间片用完后停止执行,适用于分时系统 中级调度；运行频率:低级调度>中级调度>高级调度3.2调度队列模型与调度准则1.调度队列模型(最基本的一种)：每个进程在执行时,可能有以下三种情况 进程在给定时间片内已完成,释放处理机后为完成状态 进程在时间片内未完成,进入就绪队列末尾

2、 进程在执行期间因某事件而阻塞,进入阻塞队列2.选择调度方式和调度算法的若干准则：面向用户的准则：(1) 周转时间短；(2)响应时间快；(3)截止时间保证；(4)优先权准则面向系统的准则：(1)系统吞吐量高；(2)处理机利用率高；(3)各类资源的平衡利用3.3调度算法周转时间=结束执行时间-进入磁盘时间带权周转时间=周转时间/服务时间高响应比=(等待时间+服务时间)/服务时间 或=等待时间/服务时间1. 先来先服务和短作业优先算法先来先服务调度算法(FCFS) 有利于长作业（CPU繁忙型）,而不利于短作业(IO繁忙型)短作业优先算法（JFS）不利于长作业*特别注意这两种算法在内存总量有限情况下

3、的应用，且在不移动的可变分区方式下的内存具体实例见ppt2. 高优先权优先调度算法(1)如果作业的等待时间相同,则要求服务的时间愈短,其优先权愈高,因而该算法有利于短作业。(2)当要求服务的时间相同时,作业的优先权决定于其等待时间,等待时间愈长,其优先权愈高,因而它实现的是先来先服务。 所以说该算法是FCFS与JFS的结合3. 基于时间片的轮转调度算法（按照老师方法做题）书本P96图3-63.4实时调度实现实时调度的基本条件：1.提供必要的信息就绪时间（开始截止时间和完成截止时间；处理时间；资源要求；优先级）2. 系统处理能力强假定系统中有m个周期性的硬实时任务,它们的处理时间可表示为Ci,周

4、期时间表示为Pi,则在单处理机情况下,必须满足下面的限制条件,系统才是可调度的。若采用多处理机（N个），则满足即可。3. 采用抢占式调度机制 4.具有快速切换机制实时调度算法分类：（1）按实时任务性质分：硬实时调度算法，软实时调度算法。（2）按调度方式分：非抢占式调度算法，抢占式调度算法。（3）按调度时间分：静态调度算法，动态调度算法。（4）在多处理机下，还分为集中式调度和分布式调度。常用的几种实时调度算法：1.最早截止时间优先EDF算法2.最低松弛度优先即LLF算法3.5产生死锁的原因和必要条件产生死锁的原因：（1）竞争资源（可剥夺性资源，如内存处理机；非可剥夺性资源，如打印机，磁带机；临时

5、性资源：由一个进程产生,被另一进程使用后就再也无用的资源）（2）进程推进顺序不当引起死锁 产生死锁的必要条件：1.互斥条件（对资源的排他性使用）2.请求和保持条件（在已经拥有了至少一个资源后又申请其他被占用的资源）3.不剥夺条件（进程已获得的资源在未使用完之前不能被剥夺。）4.环路等待条件（发生死锁时,必然存在一个进程-资源的环形链） 只要一个不满足，则就能破坏死锁。处理死锁的基本方法：(1)预防死锁(2)避免死锁(3)检测死锁(4)解除死锁3.6预防死锁的方法因为产生死锁的四个条件中的1.互斥条件无法被改变，所以就只能从其他四个入手。分为：1.摒弃请求和保持条件；2.摒弃不剥夺条件；3.摒弃

6、环路等待条件利用银行家算法避免死锁（例题见ppt后题）3.7 死锁的检测与解除死锁的检测可以在资源分配图中采用死锁定理，详见书本P112-113死锁的解除有两种方法：（1）剥夺资源(从其他进程剥夺资源给死锁进程)（2）撤销进程第四章存储器管理4.1程序的装入与链接源程序要运行通常经过编译，链接，装入等几个步骤程序的装入可分为：1.绝对装入方式2.可重定位装入方式3.动态运行时装入方式程序的链接分为：1.静态链接方式2. 装入时动态链接(边装入边链接)3. 运行时动态链接(对某些模块的链接推迟到执行时才去做)4.2连续分配方式连续分配方式为一个用户程序分配一个连续的内存空间1. 单一连续分配：只

7、能用于单用户、单任务的操作。这种方式把系统中的内存分为系统区和用户区两部分,系统区仅提供给OS使用。2. 固定分区分配：最简单的可运行多道程序的存储管理方式。将内存用户空间划分为若干个固定大小的区域,每个分区中只装入一道作业。3. 动态分区分配：根据进程的实际需要,动态地为之分配内存空间。分区分配算法: (1)首次适应算法FF（要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，知道找到一个大小符合的空闲分区）(2)循环首次适应算法（从上次找到的空闲分区的下一空闲分区开始查找，知道找到合适的）(3)最佳适应算法（要求将所有空闲分区按其容量从小到大的顺序形成空闲分区链。每次分配

8、时，总把既能满足要求又是最小的分配出去。）(4)最差(坏)适应算法（与（3）相反，从大到小，找最大的分出去）(5)快速适应算法(分类搜索法)回收内存的四种情况P1254.伙伴系统：不断地平分较大的空闲内存块来获得较小的空闲内存块，直到获得所需的内存块；当内存释放时，尽可能的合并空闲内存块。（分配与合并都采用以2的幂次方为单位）5. 可重定位分区分配：把内存中的所有作业移动，使他们相邻接，即可把分散的空闲小分区拼为大分区。6. 对换：指把内存中暂时不能运行的进程或者暂时不用的程序和数据,调出到外存上，把已具备运行条件的进程或进程所需要的程序和数据,调入内存。在具有对换功能的OS中，把外存分为文件

9、区和对换区，前者用于存放文件，后者用于存放从内存换出的进程。如果允许一个进程直接分散地装入到许多不相邻接的分区中,称为离散分配方式。离散分配方式有分页存储管理方式（离散分配的基本单位是页）、分段存储管理方式（离散分配的基本单位是段）和段页存储管理方式4.3基本分页存储管理方式页面与页表将用户作业的地址空间分成若干个大小相同的区域,称为页面或页,并为每个页从“0”开始编号；相应的，主存空间也分成与页大小相同的若干个存储块,或称为物理块。在为进程分配内存时，以块为单位将进程中的若干个页分别装入多个可以不相邻接的物理块中。为每个进程建立一张页面映像表,简称页表,页表大多驻留在内存中，是实现从页号到物

10、理块号的地址映射。（访问两次内存）程序的逻辑地址包括页号和页内地址(页内位移量)。若给定一个逻辑地址空间中的地址为A,页面的大小为L,则页号P和页内地址d可按下式求得: 例:系统页面大小为1KB,逻辑地址为2170B,求页号与页内地址。解答：页号 P=INT2170/1024=2；页内地址d=2170 mod 1024 =122B第0页 01023第1页 10242047第2页 20483071地址变换机构：用于实现从逻辑地址到物理地址的转换以页号查页表,得到对应页装入内存的块号。内存地址物理块号×页大小页内地址例题1: 有一系统采用分页存储管理,有一作业大小是8KB,页大小为2KB

11、,依次装入内存的第7、9、A、5,试将逻辑地址0AFEH字节转换成内存地址。答:逻辑地址0AFEH字节0000 1010 1111 1110 (页面大小为2KB，即2的11方，从末尾往前数11位即为页内地址，剩余为页号)P1； W010 1111 1110字节页号1对应的块号为9，2进制为1001，加上页内地址即为0100 1010 1111 1110（前面补0）内存地址0100 1010 1111 11104AFEH字节例题2：有一系统采用分页存储管理,有一作业大小是8KB,页大小为2KB,依次装入内存的第7、9、10、5块,试将逻辑地址7145字节转换成内存地址。答：逻辑地址 7145字节

12、 ，页大小为2KB=2048BPINT7145/20483；W7145 mod 20481001字节所以内存地址=5*2048+1001=11241字节，即逻辑地址7145字节的内存地址是:11241字节。4.4 基本分段存储管理方式在分段式存储管理中，为每个分段分配一个连续的分区，而各段可以离散的移入内存的不同分区中。供用户使用的逻辑地址为段号(段名)+段内地址。在装入作业时,用一张段表记录每个分段在主存中的起始地址和长度，实现从逻辑段到物理内存区的映射。（访问两次内存）分页存储管理的主要目的是为了提高内存利用率,分段存储管理的主要目的是为了满足用户在编程和使用上的要求。分页和分段的主要区别

13、：页是信息的物理单位，为了系统管理而存在；1.段是信息的逻辑单位，是为了满足用户而存在。2.页的大小固定且由系统决定，而段的长度却不固定,决定于用户所编写的程序。3. 分页的作业地址空间是一维的，而分段的作业地址空间则是二维的。段页式存储管理方式：段页式管理中,逻辑地址由段号、段内页号及页内地址三部分所组成（访问三次内存）4.5虚拟存储器的基本概念程序在运行之前，没必要全部装入内存，仅需将要用的调入，其余部分留在盘上。在程序运行时，若所需要的页（段）尚未调入，则请求调入，若内存已满，则将暂时不用的置换出去虚拟存储器是指具有请求调入功能和置换功能,能从逻辑上对内存容量加以扩充的一种存储器系统。虚

14、拟存储器的实现主要通过请求分页系统和请求分段系统两种方式。虚拟存储器的特征主要为：离散性、多次性（将一个作业分多次调入）、对换性、虚拟性.4.6请求分页存储管理方式缺页中断：在请求分页系统中，每当所要访问的页面不在内存中时，便产生一缺页中断，请求OS将所缺之页调入内存。4.7页面置换算法1.FIFO页面置换算法；2.LRU页面置换算法（可以通过栈来实现，具体见书本P152）；3.Clock置换算法第五章设备管理5.1 I/O系统（1）I/O设备的类型：按传输速率分类：低速设备，中速设备，高速设备。 按信息交换的单位分类：块设备（基本特征是其传输速率较高，可寻址，属于有结构设备，磁盘就属于块设备

15、）；字符设备（基本特征是其传输速率较低，不可寻址，通常采用中断驱动方式，属于无结构设备，例:交互式终端、打印机）按设备的共享属性分类：独占设备（不可寻址），共享设备（可寻址且可以随机访问），虚拟设备（2）设备并不是直接与CPU通信，而是通过设备控制器（位于CPU和设备之间，接收CPU发来的命令,控制一个或多个I/O设备,以实现I/O设备和计算机之间的数据交换）。设备与设备控制器之间的接口有：数据信号线：用于在设备和设备控制器之间传送数据信号控制信号线：作为由设备控制器向I/O设备发送控制信号时的通路状态信号线：用于传送指示设备当前状态的信号设备控制器的组成：设备控制器与处理机的接口；设备控制器

16、与设备的接口；I/O逻辑。（3）I/O通道是一种特殊处理机，只具有执行I/O指令的能力。位于CPU和设备控制器之间，即实现内存与外设之间的传输。没有自己的内存，与CPU共享内存。通道类型：(1) 字节多路通道连接中低速设备；（2）数组选择通道高速传输数据，每次只有一台设备进行数据传送,形成独占；(3)数组多路通道结合了（1）（2）的优点。解决瓶颈问题的方法是增加通路。5.2 I/O控制方式内存与外设的控制方式主要有四种:程序I/O方式（有“忙等待” 现象）、中断驱动I/O方式（以字节为单位，CPU与I/O设备并行操作）、直接存储访问DMA I/O控制方式（在DMA控制器的作用下，数据传输的基本

17、单位为块，如磁盘）和I/O通道控制方式。DMA控制器的组成：主机与DMA控制器的接口，DMA控制器与块设备的接口，I/O控制逻辑。（为了实现在主机与DMA控制器之间成块数据的直接交换, 必须在DMA控制器中设置如下四类寄存器:命令/状态寄存器CR，内存地址寄存器MAR，数据寄存器DR，数据计数器DC）。5.3 缓冲管理引入缓冲区目的：(1)缓和CPU与I/O设备间速度不匹配的矛盾。 (2)减少对CPU的中断频率,放宽对CPU中断响应时间的限制。 (3)提高CPU和I/O设备之间的并行性。 根据系统设置缓冲区的个数,将缓冲技术分为:单缓冲、双缓冲、循环缓冲、缓冲池。当输入与输出速度基本匹配时,双

18、缓冲能获得较好效果;当速度相差较大时,可引入多个缓冲,组织成循环缓冲（多个缓冲区）的形式。循环缓冲：用于装输入数据的空缓冲区R，已装满数据的满缓冲区G，计算进程正在使用的现行工作缓冲区C。多个指针：指示计算进程下一可用缓冲区Nextg，指示输入进程下一可用空缓冲区Nexti，指示计算进程正在使用的缓冲区Current(1)Nexti指针追赶上Nextg指针输入进程速度大于计算进程,全部空缓冲区已满,无可用缓冲区,输入进程阻塞(2)Nextg指针追赶上Nexti指针计算进程速度大于输入进程,全部缓冲区空,无可用数据,计算进程阻塞。缓冲池：因为以上的专用缓冲的利用率不高,因此设置公用缓冲池。5.4

19、设备分配SPOOLing系统的组成：输入井和输出井：在磁盘上的两个存储空间。输入井模拟脱机输入,暂存输入数据；输出井模拟脱机输出,暂存输出数据。输入缓冲区和输出缓冲区：在内存中。用来缓和CPU与磁盘之间的速度的矛盾输入进程SPi和输出进程SPo：模拟脱机I/O时的外围控制机。SPi模拟脱机输入时的外围控制机；SPo模拟脱机输出时的外围控制机。5.5 磁盘存储器管理磁盘调度先来先服务FCFS；最短寻道时间优先SSTF（有“饥饿”现象）；扫描(SCAN)算法（可防止进程出现“饥饿”现象，又称为 “电梯调度算法”）；循环扫描(CSCAN)算法；N-Step-SCAN（将磁盘请求队列分成若干个长度为N的子队列,磁盘调度将按FCFS算法依次处理这些子队列。而每处理一个队列时又是按SCAN算法。当N很大时，趋于SCAN算法，N=1时，蜕化为FCFS算法） 磁盘高速缓存：利用内存中的存储空间,来暂存从磁盘中读出的一系列盘块中的信息。是一组在逻辑上属于磁盘,而物理上是驻留在内存中的盘块。提高磁盘I/O速度的其它方法：提前读，延迟写，优化物理块分布，虚拟盘。六文件管理6.1文件和文件系统文件可分为有结构文件(记录式文件)和无结构文件（流式文件），有结构文件中，文件由若干