操作系统课件复习

1、第第1 1章章 操作系统引论操作系统引论一、操作系统的目标一、操作系统的目标 能够能够高效高效地控制和管理计算机硬件和软件资源、地控制和管理计算机硬件和软件资源、公平公平合理地合理地对各类作业进行调度、使各用户能够灵活对各类作业进行调度、使各用户能够灵活方便方便有效地使用计算机。有效地使用计算机。有良好的有良好的开放开放性和性和可扩充可扩充性。性。高效：高效：CPU,内存内存,I/O设备设备,文件文件(程序和数据程序和数据)利用率提高利用率提高公平公平: 应公平合理应公平合理, 否则会产生否则会产生“死锁死锁”或或“饥饿饥饿”方便方便: 用户界面友好，使用灵活方便。用户界面友好，使用灵活方便。

2、开放开放: 遵循开放系统互连遵循开放系统互连 OSI 国际标准规范国际标准规范, 彼此兼容彼此兼容可扩充：可扩充：层次化结构，便于增加新的功能层次化结构，便于增加新的功能 充分地利用资源充分地利用资源 更好的提供服务更好的提供服务1. 1. 标准服务提供者标准服务提供者 操作系统是在硬件基础上的第一层软件操作系统是在硬件基础上的第一层软件, , 是用户及应是用户及应用软件和硬件系统的接口用软件和硬件系统的接口 命令方式命令方式 系统调用方式系统调用方式 图形窗口方式图形窗口方式给用户提供需要的标准工具如给用户提供需要的标准工具如: :标准库标准库, ,窗口系统窗口系统用户通过用户通过OSOS能

3、方便快捷安全可靠地操纵计算机硬件和运行能方便快捷安全可靠地操纵计算机硬件和运行自己的程序自己的程序操作系统的作用？操作系统的作用？2. 2. 操作系统作为操作系统作为 管理者管理者(government)(government) 高效合理地管理资源。四类资源高效合理地管理资源。四类资源: : 处理器、内存、处理器、内存、 I/OI/O设备、信息设备、信息( (程序和数据，作业和文件程序和数据，作业和文件) ) 提供安全、保密措施，共享和保护提供安全、保密措施，共享和保护3. 3. 操作系统作为操作系统作为 仲裁者（协调者）仲裁者（协调者） 使多个应用程序使多个应用程序/ /用户高效，公平地一起

4、工作保护用户不互用户高效，公平地一起工作保护用户不互相干扰。相干扰。 例子：并发，存储保护，文件系统，网络例子：并发，存储保护，文件系统，网络 4. 操作系统作为操作系统作为 幻觉制造者幻觉制造者(illusionist) 提供硬件的高层界面提供硬件的高层界面(虚拟机虚拟机), 取消硬件限制。取消硬件限制。 操作系统提供无限的内存、无限的操作系统提供无限的内存、无限的CPU。 扩充机器扩充机器，增强功能，增强功能 。1)1) 多路性多路性: : 一台主机同时联接多个终端一台主机同时联接多个终端, ,系统按分时的原则为系统按分时的原则为每个用户服务每个用户服务, , 共享资源。共享资源。2)2)

5、 独立性独立性: : 用户各占一个终端用户各占一个终端, , 感觉像独占主机感觉像独占主机3)3) 及时性及时性: : 用户请求能在容许的响应周期内及时获得响应用户请求能在容许的响应周期内及时获得响应, , 响响应周期通常在应周期通常在3 3秒以内。秒以内。4)4) 交互性交互性: : 用户通过终端与系统进行广泛的人机对话用户通过终端与系统进行广泛的人机对话, , 以请求以请求系统提供多方面的服务。系统提供多方面的服务。分时系统的特点分时系统的特点现代操作系统的基本特性现代操作系统的基本特性1. 并发并发(concurrence) 计算机内存中同时存在多个程序计算机内存中同时存在多个程序, 宏

6、观上这些程序是同时宏观上这些程序是同时在执行的在执行的, 但在微观上任何时刻只有一个程序在执行。即微观但在微观上任何时刻只有一个程序在执行。即微观上这些程序在上这些程序在CPU上轮流执行。上轮流执行。 注意它和并行的区别注意它和并行的区别, 并行是多个程序在不同的硬件上同并行是多个程序在不同的硬件上同时执行时执行, 即在微观上这些程序也是真正的同时执行。即在微观上这些程序也是真正的同时执行。2. 2. 共享共享(sharing)(sharing) 操作系统与多个用户的程序共同使用计算机系统中的资操作系统与多个用户的程序共同使用计算机系统中的资源源( (硬件和软件硬件和软件) )。两种资源共享方

7、式。两种资源共享方式: :互斥共享方式和同时访问方式互斥共享方式和同时访问方式3. 虚拟虚拟(Virtual) 把一个物理时体把一个物理时体“虚拟虚拟”为多个逻辑体，如：为多个逻辑体，如： 虚拟处理机、虚拟内存、虚拟设备和虚拟信道。虚拟处理机、虚拟内存、虚拟设备和虚拟信道。4. 异步性异步性(asynchronism)(不确定性不确定性) 多个进程并发执行时多个进程并发执行时, 各进程都是以走走停停的方式运行各进程都是以走走停停的方式运行, 运行顺序无法预测运行顺序无法预测, 即进程以异步方式运行。即进程以异步方式运行。 因此因此, 操作系统必须随时对以不可预测的不确定的次序随机操作系统必须随

8、时对以不可预测的不确定的次序随机发生的事件进行响应。发生的事件进行响应。现代操作系统的功能现代操作系统的功能1. 1. 处理机管理处理机管理进程控制、进程同步、进程通信、进程调度进程控制、进程同步、进程通信、进程调度2. 2. 内存管理内存管理内存分配、内存保护、地址映射、内存扩充内存分配、内存保护、地址映射、内存扩充3. 3. 设备管理设备管理设备分配设备分配, ,缓冲管理缓冲管理, ,设备驱动设备驱动, , 虚拟设备虚拟设备4. 4. 文件管理文件管理文件存储空间管理、目录管理、读写管理、文件保护文件存储空间管理、目录管理、读写管理、文件保护5. 5. 用户接口用户接口命令接口命令接口(

9、(联机脱机联机脱机), ), 程序接口程序接口, , 图形接口图形接口, , 多媒体接口多媒体接口微内核结构采用了微内核结构采用了3 3项技术：项技术：客户客户/ /服务器模式服务器模式面向对象技术面向对象技术微内核技术微内核技术为了保证系统的安全，为了保证系统的安全，CPUCPU执行的程序分为系统态执行的程序分为系统态( (管态管态) )和用户和用户态态( (目态目态), OS), OS程序工作在管态程序工作在管态, , 是系统的管理和控制者是系统的管理和控制者, , 它享有它享有特权又称为管理程序、监督程序。应用程序工作在目态又称为目特权又称为管理程序、监督程序。应用程序工作在目态又称为目

10、的程序、用户程序它们没有特权。用户程序需要系统为之服务时的程序、用户程序它们没有特权。用户程序需要系统为之服务时必须通过系统调用必须通过系统调用( (访管指令访管指令) )引起一次中断转入引起一次中断转入OSOS程序。程序。微内核操作系统结构微内核操作系统结构第二章第二章 进程管理进程管理 结构性：结构性：由程序由程序+ +数据数据+ +进程控制块组成了进程实体进程控制块组成了进程实体, , 称之为进程映称之为进程映像。进程控制块是进程存在的标志。像。进程控制块是进程存在的标志。 动态性动态性进程是进程实体的执行过程进程是进程实体的执行过程, , 它由创建而产生它由创建而产生, , 由调度而由

11、调度而执行执行, ,因某事件而暂停因某事件而暂停, , 由撤销而消亡。在生命周期内由撤销而消亡。在生命周期内, , 进程在三种基本状态之间动态转换进程在三种基本状态之间动态转换 并发性并发性 多个进程同时存于内存中多个进程同时存于内存中, ,一起向前推进一起向前推进, ,并发执行并发执行 独立性独立性 进程是独立获得资源和独立调度的基本单位进程是独立获得资源和独立调度的基本单位 异步性异步性 各进程都各自独立的不可预知的速度向前推进各进程都各自独立的不可预知的速度向前推进进程的基本特征进程的基本特征进程控制块的作用：进程控制块的作用： 系统为管理进程设置一个专门的数据结构系统为管理进程设置一个

12、专门的数据结构进程控制块进程控制块(Process Control Block), (Process Control Block), 用它来记录进程的外部特征，描用它来记录进程的外部特征，描述进程的运动变化过程述进程的运动变化过程 ( (从结构的观点上看从结构的观点上看, , 程序与进程的程序与进程的区别就在于有没有区别就在于有没有PCB)PCB)。 进程与进程与PCBPCB一一对应一一对应, , 在进程的整个生命期内在进程的整个生命期内, PCB, PCB随进随进程的创建而产生随进程的终止而消失程的创建而产生随进程的终止而消失, , 系统利用系统利用PCBPCB来控制来控制和管理进程和管理进

13、程, , 系统根据系统根据PCBPCB感知进程的存在感知进程的存在, , 所以所以PCBPCB是进程是进程存在的存在的唯一标志。唯一标志。存放控制进程所需的数据存放控制进程所需的数据( (进程属性进程属性) )。运行运行就绪就绪阻塞阻塞进程的三种基本状态及其转换进程的三种基本状态及其转换调度调度超时超时I/O请求请求I/O完成完成临界资源临界资源( (互斥资源互斥资源) )：critical resourcecritical resource 系统中一次只允许一个进程访问的资源系统中一次只允许一个进程访问的资源; ; 这些资源既包括这些资源既包括I/OI/O设备设备, , 如打印机等资源如打印

14、机等资源, , 也包括软件资源也包括软件资源, , 如共享变量、共如共享变量、共享文件等。享文件等。临界区临界区( (互斥区互斥区): ): critical sectioncritical section 并发执行的进程并发执行的进程中中, , 访问临界资源的必须互斥执行的程序段访问临界资源的必须互斥执行的程序段叫叫临界区。临界区。 临界区临界区分散在每个要分散在每个要并发执行的并发执行的进程中进程中, , 它们都对某个共它们都对某个共享的数据结构享的数据结构( (共享资源共享资源) )进行访问进行访问1) 1) 信号量的物理含义：信号量的物理含义：S0S0表示有表示有S S个资源可用个资源

15、可用S=0S=0表示无资源可用表示无资源可用S0Sl页表始址页表始址 p0+页号页号p p 页内地址页内地址dbd物理地址寄存器物理地址寄存器页表寄存器页表寄存器逻辑地址逻辑地址页表页表01.008003 4C8 003 4C8 2AC4C84C8比较比较0123+2AC页面分配与置换页面分配与置换请求调页中操作系统提供的支持请求调页中操作系统提供的支持 请求调页时请求调页时, , 把所需的页从外存调入内存把所需的页从外存调入内存 置换时置换时, , 将内存的某些页调至外存将内存的某些页调至外存问题：问题：进程正常运行所需的最少物理块是多少？进程正常运行所需的最少物理块是多少？每个进程分配的物

16、理块数是固定的吗？每个进程分配的物理块数是固定的吗？每个进程分配的物理块数依据是什么？每个进程分配的物理块数依据是什么？1. 1. 最小物理块数的确定最小物理块数的确定 最小物理块数与硬件结构、指令格式、寻址方式有关。最小物理块数与硬件结构、指令格式、寻址方式有关。 直接寻址方式最少块数为直接寻址方式最少块数为2 2 间接寻址方式最少块数为间接寻址方式最少块数为3 3 功能较强的机器最少块数为功能较强的机器最少块数为6 62. 2. 页面分配和置换策略页面分配和置换策略( (固定分配、可变分配固定分配、可变分配) ) 1) 1) 固定分配局部置换固定分配局部置换 系统中驻留的进程数与分配给进程

17、的页数是什么关系？系统中驻留的进程数与分配给进程的页数是什么关系？（正比？反比？）（正比？反比？） 块数太多会出现什么问题？块数太多会出现什么问题？ 块数太少会出现什么问题？块数太少会出现什么问题？2) 2) 可变分配全局置换可变分配全局置换 空闲物理块由谁管理？空闲物理块由谁管理？(OS?(OS?进程？）进程？） 缺页中断时从何处获得空闲页？缺页中断时从何处获得空闲页？ 调入调出什么时候发生（空闲页用完还是给进程分配的调入调出什么时候发生（空闲页用完还是给进程分配的页用完？）页用完？）3) 3) 可变分配局部置换可变分配局部置换 为每个进程所分配的物理块数相对固定为每个进程所分配的物理块数相

18、对固定 从每个进程所分配的页面中进行换入换出。从每个进程所分配的页面中进行换入换出。 从全局的角度动态调整每个进程所分配的页面从全局的角度动态调整每个进程所分配的页面抖动抖动 在虚存中在虚存中, , 页面在内存与外存之间频繁调度页面在内存与外存之间频繁调度, , 以至于调以至于调度页面所需时间比进程实际运行的时间还多度页面所需时间比进程实际运行的时间还多, , 此时系统效此时系统效率急剧下降率急剧下降, , 甚至导致系统崩溃甚至导致系统崩溃, , 这种现象为抖动。这种现象为抖动。产生原因：产生原因：页面淘汰算法不合理页面淘汰算法不合理分配给进程的工作集窗口尺寸太小分配给进程的工作集窗口尺寸太小

19、出现出现: CPU: CPU利用率下降利用率下降调入新的进程调入新的进程 从其它进程获从其它进程获得物理块得物理块缺页中断次数增加缺页中断次数增加CPUCPU利用率进一步下降的利用率进一步下降的恶性循环恶性循环 某程序在内存中分配三个块，访问页的走向为4，3，2，1，4，3，5，4，3，2，1，5，按FIFO、 LRU、OPT算法分别计算缺页次数。（假设开始时所有页均不在内存）例1FIFO 4 3 2 1 4 3 5 4 3 2 1 5页1 4 3 2 1 4 3 5 5 5 2 1 1页2 4 3 2 1 4 3 3 3 5 2 2页3 4 3 2 1 4 4 4 3 5 5 x x x x

20、 x x x x x 共缺页中断9次FIFO LRU 4 3 2 1 4 3 5 4 3 2 1 5页1 4 3 2 1 4 3 5 4 3 2 1 5页2 4 3 2 1 4 3 5 4 3 2 1页3 4 3 2 1 4 3 5 4 3 2 x x x x x x x x x x共缺页中断10次 LRU OPT 4 3 2 1 4 3 5 4 3 2 1 5页1 4 3 2 1 1 1 5 5 5 2 1 1页2 4 3 3 3 3 3 3 3 5 5 5页3 4 4 4 4 4 4 4 4 4 4 x x x x x x x 共缺页中断7次OPT例2某程序在内存中分配四个块，访问页的走向

21、为4，3，2，1，4，3，5，4，3，2，1，5，按LRU、OPT算法分别计算缺页次数。（假设开始时所有页均不在内存）LRU 4 3 2 1 4 3 5 4 3 2 1 5页1 4 3 2 1 4 3 5 4 3 2 1 5页2 4 3 2 1 4 3 5 4 3 2 1页3 4 3 2 1 4 3 5 4 3 2页4 4 3 2 1 1 1 5 4 3 x x x x x x x x共缺页中断8次OPT 4 3 2 1 4 3 5 4 3 2 1 5页1 4 3 2 1 1 1 5 5 5 5 1 1页2 4 3 2 2 2 2 2 2 2 5 5页3 4 3 3 3 3 3 3 3 3 3

22、页4 4 4 4 4 4 4 4 4 4 x x x x x x 共缺页中断6次第五章第五章 设备管理设备管理I/O I/O 控制方式控制方式 程序程序I/OI/O方式方式适用于结构简单，只需少量硬件的电路；早期计算机无中断机构，处适用于结构简单，只需少量硬件的电路；早期计算机无中断机构，处理机对理机对I/OI/O设备的控制采用程序设备的控制采用程序I/OI/O方式或称忙等的方式。方式或称忙等的方式。 中断驱动中断驱动I/OI/O控制方式控制方式 适用于高效场合，须有中断机构支持。适用于高效场合，须有中断机构支持。 DMADMA控制方式控制方式适用于传输速率要求高的块设备；须有适用于传输速率要

23、求高的块设备；须有DMA控制器支持。控制器支持。 I/OI/O通道控制方式通道控制方式适用于同时实现适用于同时实现CPU，通道和，通道和I/O设备三者并行操作的场合。设备三者并行操作的场合。 1.1.设备独立性设备独立性(Device Independence)(Device Independence) 为了提高为了提高OSOS的可适应性和可扩展性的可适应性和可扩展性, , 现代现代OSOS都实现了设都实现了设备独立性备独立性( (设备无关性设备无关性), ), 引入了逻辑设备和物理设备两个概引入了逻辑设备和物理设备两个概念念, ,使应用程序用逻辑设备名来请求某类设备使应用程序用逻辑设备名来请

24、求某类设备, , 独立于具体独立于具体的物理设备。的物理设备。OSOS将逻辑设备名转换为具体的物理设备。带来将逻辑设备名转换为具体的物理设备。带来的好处是的好处是: : (1) (1) 设备分配的灵活性设备分配的灵活性 (2) (2) 易于实现易于实现I/OI/O的重定向的重定向2. 2. 设备独立性软件设备独立性软件(1) (1) 执行所有设备的公有操作执行所有设备的公有操作 对独立设备的分配和回收对独立设备的分配和回收 将逻辑设备名映射为物理设备名找到驱动程序将逻辑设备名映射为物理设备名找到驱动程序 对设备进行保护对设备进行保护 缓冲管理缓冲管理 差错控制差错控制(2) (2) 向用户层软

25、件提供统一接口向用户层软件提供统一接口 I/OI/O软件组织成一种软件组织成一种层次结构层次结构, ,低层软件用来屏蔽具体设低层软件用来屏蔽具体设备细节备细节, ,高层软件则为用户提供一个简洁规范的界面高层软件则为用户提供一个简洁规范的界面。它体现。它体现了了I/O I/O 设计的关键的概念设计的关键的概念: :设备无关性设备无关性, , 其含义就是使程序员其含义就是使程序员写的软件无须修改写的软件无须修改, ,就能进行不同设备上的就能进行不同设备上的I/OI/O操作。操作。如对各如对各种设备的读操作都使用种设备的读操作都使用read;read;对各种设备的写操作都使用对各种设备的写操作都使用

26、writewrite。I/OI/O软件的层次结构及功能软件的层次结构及功能进行进行I/O;I/O;格式化格式化I/OI/O命名命名; ;保护保护; ;缓冲缓冲; ;分配分配; ;阻塞阻塞建立设备寄存器建立设备寄存器; ;检测状态检测状态I/OI/O结束时唤醒服务子程序结束时唤醒服务子程序执行执行I/OI/O操作操作中断处理程序中断处理程序设备驱动程序设备驱动程序设备无关软件设备无关软件I/OI/O应答应答I/OI/O请求请求用户进程用户进程硬件硬件 3. 3.逻辑设备名到物理设备名映射逻辑设备名到物理设备名映射(1) (1) 逻辑设备表逻辑设备表(LUT)(LUT)逻辑设备名逻辑设备名 物理设

27、备名物理设备名驱动程序入口地址驱动程序入口地址 /dev/tty/dev/tty 3 3 1024 1024 /dev/print /dev/print 5 5 2048 2048(2) (2) 逻辑设备表的设置逻辑设备表的设置 整个系统只设一张整个系统只设一张LUTLUT不允许有相同的逻辑设备名不允许有相同的逻辑设备名, , 用在单用户系统中。用在单用户系统中。 每个用户设一张每个用户设一张LUT, LUT, 用户登录建立进程时用户登录建立进程时, ,建立一建立一张张LUTLUT并将该表放入该进程的并将该表放入该进程的PBCPBC中中, ,用在多用户系统中。用在多用户系统中。 设备驱动程序的

28、功能和特点设备驱动程序的功能和特点1.1.设备驱动程序的功能设备驱动程序的功能(1) (1) 将接受到的抽象将接受到的抽象( (逻辑逻辑) )要求转化为具体要求转化为具体( (物理物理) )要求。要求。(2) (2) 检查用户检查用户I/OI/O请求的合法性请求的合法性, , 读出和检查读出和检查I/OI/O设备的状态设备的状态, , 传递有关参数传递有关参数, , 设置设备的工作方式。设置设备的工作方式。(3) (3) 发出发出I/OI/O命令命令, ,若设备空闲则启动的若设备空闲则启动的I/OI/O设备设备, , 否则将请求否则将请求进程挂到设备等待队列上。进程挂到设备等待队列上。(4)

29、(4) 及时响应由控制器或通道发来的中断请求及时响应由控制器或通道发来的中断请求, , 并根据中断类并根据中断类型调用相应的中断处理程序进行处理。型调用相应的中断处理程序进行处理。(5) (5) 对于设置通道的计算机系统对于设置通道的计算机系统, , 驱动程序还应能够根据用户驱动程序还应能够根据用户的的I/OI/O请求请求, , 自动地构造通道程序。自动地构造通道程序。2. 2. 设备处理方式设备处理方式 (1) (1) 为每类设备设置一个为每类设备设置一个I/OI/O进程。进程。 (2) (2) 整个系统设置一个整个系统设置一个I/OI/O进程。进程。 (3) (3) 只为各类设备设置相应的

30、设备处理程序供调用。只为各类设备设置相应的设备处理程序供调用。3. 3. 设备驱动程序的特点设备驱动程序的特点(1) (1) 驱动程序主要是在请求驱动程序主要是在请求I/OI/O的进程与设备控制器之间的进程与设备控制器之间的一个通信程序。的一个通信程序。(2) (2) 驱动程序与驱动程序与I/OI/O设备的特性密切相关。设备的特性密切相关。(3) (3) 驱动程序与驱动程序与I/OI/O控制方式相关。控制方式相关。(4) (4) 有些驱动程序固化在有些驱动程序固化在ROMROM上。上。1.1. 将抽象的要求转化为具体的要求将抽象的要求转化为具体的要求如如: :将逻辑盘块号转换为具体的盘面、磁道

31、和扇区将逻辑盘块号转换为具体的盘面、磁道和扇区2. 2. 检查检查I/OI/O请求的合法性请求的合法性如如: :打印机请求读打印机请求读, , 以读方式打开磁盘后请求写以读方式打开磁盘后请求写3. 3. 读出并检查设备的状态读出并检查设备的状态如如: :读并查状态是否为就绪读并查状态是否为就绪, , 确定启动控制器或等待确定启动控制器或等待4. 4. 传送必要的参数传送必要的参数如如: :启动磁盘启动磁盘, , 先将字节数和内存起始地址送控制器先将字节数和内存起始地址送控制器5. 5. 工作方式的设置工作方式的设置如如: :异步通信异步通信, , 先设置波特率、校验方式、停止位等先设置波特率、

32、校验方式、停止位等6. 6. 启动启动I/OI/O设备设备: :向控制器发送控制命令向控制器发送控制命令, , 将自己将自己阻塞阻塞进入睡眠进入睡眠状态。状态。由控制器由控制器控制下进行控制下进行指定的指定的I/OI/O操作。操作。7. 7. 完成完成I/OI/O后后, ,设备控制器向设备控制器向CPUCPU发出中断请求发出中断请求;CPU;CPU响应转向响应转向中中断处理程序唤醒断处理程序唤醒相应的设备驱动进程。相应的设备驱动进程。5.5.25.5.2设备驱动程序的处理过程设备驱动程序的处理过程 在设备控制器的控制下在设备控制器的控制下, , 设备设备完成完成I/OI/O操作后操作后, ,

33、设备控设备控制器便向制器便向CPUCPU发出一个发出一个中断请求中断请求; CPU; CPU响应后响应后, , 转向转向中断处理中断处理程序程序, ,中断处理含以下几个步骤：中断处理含以下几个步骤：(1) (1) 唤醒唤醒被阻塞的驱动被阻塞的驱动( (程序程序) )进程进程(2) (2) 保护被中断进程的保护被中断进程的CPUCPU环境环境(3) (3) 分析中断原因转入相应的设备分析中断原因转入相应的设备处理程序处理程序(4) (4) 进行中断处理进行中断处理(5) (5) 恢复恢复被中断进程的现场被中断进程的现场I/OI/O完成完成中断处理程序的处理过程中断处理程序的处理过程恢复恢复被中断

34、进程的现场被中断进程的现场继续执行被中断进程继续执行被中断进程唤醒唤醒被阻塞的驱动程序进程被阻塞的驱动程序进程保护被中断进程的保护被中断进程的CPU环境环境分析中断原因分析中断原因转入相应的设备转入相应的设备处理程序处理程序打印机中断打印机中断处理程序处理程序键盘中断键盘中断处理程序处理程序磁盘访问时间（磁盘访问时间（Ta)Ta) 寻道时间寻道时间Ts: Ts: 把磁头移动定位到指定磁道把磁头移动定位到指定磁道所经历的时间所经历的时间, , 启动时间启动时间s s与移动与移动n n条磁道时间之和条磁道时间之和 Ts=mTs=m n+s n+s 一般为一般为530ms530ms 旋转时间旋转时间

35、TrTr 等待指定等待指定扇区扇区旋转旋转移动到磁头下面所经历的时间移动到磁头下面所经历的时间 5400r/min=90r/sec5400r/min=90r/sec的硬盘的硬盘: :平均平均TrTr=1/2r=5.55ms=1/2r=5.55ms 传输时间传输时间TtTt 从磁盘到内存读写数据实际经历的从磁盘到内存读写数据实际经历的时间时间: Tt=b/rN : Tt=b/rN 其中其中b b为为读写字节数读写字节数N N为一条磁道总字节数为一条磁道总字节数 访问时间访问时间: :Ta= Ta= Ts+Ts+1/2r+b/rN 1/2r+b/rN 主要与主要与TsTs有关有关 磁盘调度算法磁盘

36、调度算法 先来先服务先来先服务FCFSFCFS、 最短寻道时间优先最短寻道时间优先SSTFSSTF 扫描算法扫描算法SCANSCAN电梯调度算法电梯调度算法 循环扫描循环扫描(CSCAN)(CSCAN) N-Step-SCAN N-Step-SCAN: : 分为多个长度为分为多个长度为N N的子队列的子队列 FSCANFSCAN算法算法: : 分分2 2个子队列个子队列( (当前和另一队列长度不定当前和另一队列长度不定) )第六章第六章 文件管理文件管理文件系统的功能文件系统的功能(1) (1) 统一的存储空间管理统一的存储空间管理, , 实施存储空间的分配与回收实施存储空间的分配与回收(2)

37、 (2) 实现文件的按名存取实现文件的按名存取 名字空间名字空间 映射映射 存储空间存储空间( (逻辑地址转换为物理地址逻辑地址转换为物理地址) )(3) (3) 实现文件信息的共享实现文件信息的共享, ,并提供文件的保护和保密措施并提供文件的保护和保密措施(4) (4) 对文件的读写管理、目录管理对文件的读写管理、目录管理(5) (5) 系统维护及向用户提供有关信息系统维护及向用户提供有关信息(6) (6) 提供与提供与I/OI/O设备的统一接口设备的统一接口(7) (7) 向用户提供方便使用的命令接口和程序接口向用户提供方便使用的命令接口和程序接口 ( (提供对文件系统和对文件的操作命令和

38、语句提供对文件系统和对文件的操作命令和语句) ) 混合索引分配方式混合索引分配方式 索引分配方式的索引块花费较多空间索引分配方式的索引块花费较多空间, ,小文件索引块利用率小文件索引块利用率更低。更低。UNIXUNIX用用混合混合索引模式避免此缺点。每个文件的索引结点含索引模式避免此缺点。每个文件的索引结点含1313个地址项个地址项 i.addr(0) i.addr(12), i.addr(0) i.addr(12), 每项每项2 2个字节个字节; ; 前前1010项存项存放直接地址放直接地址( (物理块号物理块号), ), 若文件大于若文件大于40kB40kB，则用，则用i.addr(10)

39、i.addr(10)指指向单级索引块进行一次间接寻址向单级索引块进行一次间接寻址, ,该块中最多可放该块中最多可放1k1k个物理块号个物理块号, ,文件可长达文件可长达4MB; 4MB; 还可用还可用 i.addr(11) i.addr(11) 和和 i.addr(12) i.addr(12) 作为二次作为二次和三次间接寻址和三次间接寻址, , 文件最大长度分别可达文件最大长度分别可达4GB4GB和和4TB4TB。.datadata.datadatadata.data.datadata.datadatadata.datamodeownerstime stampssizeblock counti

40、.addr( 0)i.addr( 1)i.addr( 9)i.addr( 10)i.addr( 11)i.addr( 12).间接间接地址项地址项混合索引方式混合索引方式直接直接地址项地址项DatamodeownerDirect block 0Direct block 1Direct block 11Single indirectDouble indirectTriple indirectinodeDataDataIndexDataDataIndexIndexIndexIndexIndexIndexIndexIndexDataDataDataDataUNIX FilesWith 4K Bloc

41、ks4K x 12 = 48KFor Single Indirect1000 Indices/Block4K x 1000 = 4MFor Double Indirect4K x 1,000,000 For Triple Indirect4K x ? 文件目录管理文件目录管理目录管理的基本要求目录管理的基本要求: :实现实现 按名存取按名存取 提高对目录的检索速度提高对目录的检索速度允许文件共享允许文件共享允许文件重名允许文件重名文件控制块文件控制块(FCB):(FCB): 是操作系统为管理文件而设置的用是操作系统为管理文件而设置的用于描述和控制文件的数据结构于描述和控制文件的数据结构, ,存

42、放了为管理文件所需的存放了为管理文件所需的所有有关信息。所有有关信息。 文件和文件和FCBFCB一一对应一一对应, FCB, FCB的有序集称为文件目录的有序集称为文件目录, , 一一个个FCB FCB 就是一个目录项就是一个目录项, , 为实现对文件目录的管理为实现对文件目录的管理, , 通通常将文件目录以文件的形式保存在外存上常将文件目录以文件的形式保存在外存上, ,这个文件就叫这个文件就叫目录文件。目录文件。索引结点索引结点(i(i结点结点) ) 当目录中文件很多时当目录中文件很多时, ,文件目录要占用大量的盘块文件目录要占用大量的盘块, , 查找目查找目录时需要将这些盘块逐块调入内存录

43、时需要将这些盘块逐块调入内存, , 将给定的文件名与目录中将给定的文件名与目录中的文件名逐一比较的文件名逐一比较; ;假如一个假如一个FCBFCB为为64B, 1KB64B, 1KB的盘块只能存的盘块只能存1616个个FCB,FCB,一个目录有一个目录有640640个个FCB, FCB, 需占用需占用4040个盘块个盘块, , 查找一个目录平查找一个目录平均要启动磁盘均要启动磁盘2020次。次。 检索目录时只用到了文件名检索目录时只用到了文件名, , 如果将如果将FCBFCB中的文件名而和描中的文件名而和描述信息分开存储述信息分开存储, , 就可以增加目录的每个盘块中的文件数就可以增加目录的每

44、个盘块中的文件数, ,减少减少访盘次数访盘次数, ,加快检索速度加快检索速度;UNIX;UNIX系统中就采用这种方法系统中就采用这种方法, , 将文件将文件描述信息单独存放在索引结点中描述信息单独存放在索引结点中( (简称简称i i结点结点), ), 目录项仅由文件目录项仅由文件名和指向该文件对应的名和指向该文件对应的 i i结点的指针构成结点的指针构成, UNIX, UNIX的目录项仅占的目录项仅占16B, 1KB16B, 1KB的盘块能存的盘块能存6464个目录项访盘次数降到原来的个目录项访盘次数降到原来的1/41/4。UNIX文件系统结构文件系统结构 i i i i i i i i ir

45、oot目录目录bin user dev bin目录目录s1 user目录目录Liu Lidev目录目录 Liu目录目录f1 t1 Li目录目录t1 e2 文件存储空间管理文件存储空间管理 空闲表法空闲表法: : 对应与文件的连续分配方式对应与文件的连续分配方式 空闲链表法空闲链表法: : 空闲簇链空闲簇链, , 显式链接显式链接 位示图位示图: : 分配置分配置1 1, , 回收回收置置0 0 成组链接法成组链接法: : 空闲块的组织、分配和回收空闲块的组织、分配和回收文件共享与文件保护文件共享与文件保护 基于索引结点的共享方式基于索引结点的共享方式, , 用符号链实现文件共享用符号链实现文件

46、共享 文件保护文件保护: : 用户验证、存取控制用户验证、存取控制操作系统接口操作系统接口 作业级接口作业级接口 程序级接口程序级接口 处理器的状态处理器的状态 根据运行程序对资源和机器指令的使用权限将处理器设置为根据运行程序对资源和机器指令的使用权限将处理器设置为不同状态不同状态 多数系统将处理器工作状态划分为管态和目态多数系统将处理器工作状态划分为管态和目态 管态：管态：操作系统管理程序运行的状态，较高的特权级别操作系统管理程序运行的状态，较高的特权级别, , 又称为特权态又称为特权态( (特态特态) )、系统态、系统态 目态：目态：用户程序运行时的状态用户程序运行时的状态, , 较低的特

47、权级别较低的特权级别, , 又称为又称为普通态普通态( (普态普态) )、用户态、用户态 管态和目态的差别管态和目态的差别处理器处于管态时：处理器处于管态时： 全部指令（包括特权指令）可以执行全部指令（包括特权指令）可以执行 可使用所有资源可使用所有资源 并具有改变处理器状态的能力并具有改变处理器状态的能力处理器处于目态时：处理器处于目态时： 只有非特权指令能执行只有非特权指令能执行特权级别不同可运行指令集合也不同特权级别不同可运行指令集合也不同 特权级别越高，可以运行指令集合越大特权级别越高，可以运行指令集合越大 高特权级别对应的可运行指令集合包含低特权级的高特权级别对应的可运行指令集合包含

48、低特权级的系统调用与一般过程调用的对比系统调用与一般过程调用的对比不同点：不同点：(1)(1) 一般过程调用一般过程调用, ,调用程序和被调用程序都运行在相调用程序和被调用程序都运行在相同状态同状态( (核心态或用户态核心态或用户态), ), 而系统调用而系统调用, , 调用程序在用户态调用程序在用户态, , 被被调用程序在核心态。调用程序在核心态。(2)(2)一般过程调用调用时不涉及系统状态转换一般过程调用调用时不涉及系统状态转换, ,直接转向被调用过直接转向被调用过程程; ; 而系统调用调用时涉及系统状态的转换而系统调用调用时涉及系统状态的转换, , 不允许由调用过不允许由调用过程直接转向

49、被调用过程程直接转向被调用过程, , 要先通过要先通过软中断机制软中断机制由用户态转换为核由用户态转换为核心态心态, , 在在OS OS 核心分析后核心分析后, , 再转向相应的系统调用处理子程序。再转向相应的系统调用处理子程序。(3)(3)抢占式调度系统中抢占式调度系统中, ,系统调用返回时会引起重新调度系统调用返回时会引起重新调度相同点相同点: : 改变指令流程改变指令流程, ,转去执行公用程序段转去执行公用程序段, , 可嵌套。可嵌套。系统调用的处理步骤系统调用的处理步骤 (1) (1) 将处理机状态由用户态转为系统态将处理机状态由用户态转为系统态; ; 由硬件和内核程由硬件和内核程序进

50、行一般性处理序进行一般性处理, , 即保护现场即保护现场: : 将处理机状态字将处理机状态字PSWPSW、程、程序计数器序计数器PCPC、系统调用号、用户栈指针和通用寄存器内容压、系统调用号、用户栈指针和通用寄存器内容压入堆栈入堆栈; ; 再将用户定义的的参数传送到指定的地方。再将用户定义的的参数传送到指定的地方。 (2)(2) 分析系统调用类型分析系统调用类型, , 按系统调用入口表转入相应的系按系统调用入口表转入相应的系统调用处理子程序统调用处理子程序( (并传递参数并传递参数); ); 该表目含该系统调用自带该表目含该系统调用自带参数的个数参数的个数( (与参数表指针与参数表指针) )和

51、入口地址。和入口地址。 (3) (3) 执行系统调用处理子程序。执行系统调用处理子程序。 (4) (4) 执行完后执行完后, , 恢复被中断的或设置新进程的恢复被中断的或设置新进程的CPUCPU现场现场, , 然然后返回被中断进程或进入新进程。后返回被中断进程或进入新进程。 系统调用系统调用 入口表入口表 (1) 转核心态转核心态 保护现场保护现场(2) 取系统调取系统调 用功能号用功能号 找到入口找到入口 传递参数传递参数A0A1Ai AnA0 A1AiAnSub0Sub1SubiSubn 用户程序用户程序系统调用系统调用处理过程处理过程(3) 恢复现场恢复现场 返回原处返回原处或或 重新调

52、度重新调度 设新现场设新现场 进新进程进新进程陷入处理机构陷入处理机构 系统子程序系统子程序另一进程另一进程 DOS: INT 21h 软中断软中断, 寄存器传递参数和入口。寄存器传递参数和入口。Linux: 0 x80 (或或128)中断向量用来实现系统调用中断向量用来实现系统调用 现代操作系统一般不直接提供系统调用指令接口现代操作系统一般不直接提供系统调用指令接口, 通常做法通常做法: 提供一套方便实用的应用程序函数库提供一套方便实用的应用程序函数库(API ) 从应用层面重新封装系统调用、屏蔽复杂的系统调用从应用层面重新封装系统调用、屏蔽复杂的系统调用传参问题、提供高级语言接口传参问题、

53、提供高级语言接口, 有助于快速开发有助于快速开发在更高层面提供系统程序设计模板库和类库在更高层面提供系统程序设计模板库和类库, 如如: Windows 2000/XP 提供封装系统调用提供封装系统调用 Win32 API和高层编程设施和高层编程设施MFC以及以及ATL。 Linux 提供封装系统调用提供封装系统调用, 符合符合POSIX标准的标准的 API和和C运行库。运行库。作业在整个活动期间经历的四种状态是：作业在整个活动期间经历的四种状态是： 提交状态：把一个作业输入到计算机中的一个过程。 后备状态：作业在磁盘上的后备队列中所处的状态。 执行状态：把处于后备状态的作业调入内存的状态。 完

54、成状态：一个作业的主进程执行结果时所处的状态。提交状态后备状态完成状态运行状态运行就绪等待作业调度Spooling衡量调度性能的指标衡量调度性能的指标1 1、调度算法应达到的目标、调度算法应达到的目标 每次运行尽可能多的作业 让处理机保持忙碌状态 使输入输出设备得以充分利用 对所有的作业公平合理吞吐量利用率问题公平性原则2 2、确定调度算法时应考虑的因素、确定调度算法时应考虑的因素 调度算法应与系统的总体设计目标一致 注意系统资源的均衡使用，使输入输出繁忙的作业与CPU繁忙的作业搭配运行 应保证进入系统的作业在规定的截至时间内运行结束3 3、调度算法性能的衡量、调度算法性能的衡量批处理系统中衡

55、量作业调度算法性能的两个指标：批处理系统中衡量作业调度算法性能的两个指标：平均周转时间和平均带权周转时间平均周转时间和平均带权周转时间（1 1）周转时间：）周转时间：i i作业的周转时间定义为：作业的周转时间定义为：T Ti i=T=Tsisi-T-Ttiti其中：其中：TsiTsi为为i i作业完成时间，作业完成时间，TtiTti为作业的提交时间。为作业的提交时间。 平均周转时间：平均周转时间：T=T=1 1n ni=1i=1n nT Ti i一个作业的周转时间可分为一个作业的周转时间可分为2 2部分：部分：（1 1）等待时间（从后备态到执行态）；（）等待时间（从后备态到执行态）；（2 2）

56、执行时间）执行时间可以表示为：可以表示为：T Ti i=T=Twiwi+T+Triri（2 2）带权周转时间：）带权周转时间：i i= =其中：其中：Ti是作业周转时间是作业周转时间, , Tri是作业执行时间是作业执行时间T Ti iT Triri平均带权周转时间：平均带权周转时间：n ni=1i=11 1n nW= =i i4.2 .3 4.2 .3 作业调度算法作业调度算法1 1、先来先服务调度算法：、先来先服务调度算法：严格按照作业先来后到的次序进行调度。严格按照作业先来后到的次序进行调度。例：例：有四个作业，它们的提交、执行时间如下有四个作业，它们的提交、执行时间如下作业号提交时间执

57、行时间111.02.0211.21.0311.40.5411.50.3带权周转时间1.02.86.211.0完成时间13.014.014.514.8周转时间2.02.83.13.3开始时间11.013.014.014.52 2、短作业优先调度算法：、短作业优先调度算法：选取执行时间最短的作业作为下次服务的对象选取执行时间最短的作业作为下次服务的对象例：例：有四个作业，它们的提交、执行时间如下有四个作业，它们的提交、执行时间如下作业号提交时间执行时间开始时间111.02.011.0完成时间13.013.313.814.8周转时间2.01.82.43.6带权周转时间1.06.04.83.6411.

58、50.313.0311.40.513.3211.21.013.8作业号提交时间执行时间111.02.0211.21.0311.40.5411.50.3例：例：有一个具有有一个具有2 2道作业的批处理系统，作业调度采用短作业优先的调度算道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用高优先级优先的抢占式调度算法。在下表所示的作业法，进程调度采用高优先级优先的抢占式调度算法。在下表所示的作业序列作业优先数即为进程优先数，优先数越小，优先级越高。序列作业优先数即为进程优先数，优先数越小，优先级越高。作业名到达时间估计运行时间优先数A10：0040（分）5B10：20303C10：3

59、0504D10：50206进入内存时间10：0010：2011：1010：50 列出所有作业进入内存时间及结束时间 计算平均周转时间结束时间11：1010：5012：0012：20文件系统功能 对于一个较完善的文件系统，应具备一系列的功能，包括对文件存储对于一个较完善的文件系统，应具备一系列的功能，包括对文件存储空间的管理、目录管理、文件的读写管理以及文件的共享与保护等。空间的管理、目录管理、文件的读写管理以及文件的共享与保护等。其中，有些功能对用户是透明的，就呈现在用户面前的功能来说，可其中，有些功能对用户是透明的，就呈现在用户面前的功能来说，可通过用户对文件所能施加的操作来表现。通过用户对

60、文件所能施加的操作来表现。 对文件的操作可分为两大类：一类是对文件自身的操作，包括文件的对文件的操作可分为两大类：一类是对文件自身的操作，包括文件的创建、删除、读、写、截断及文件读创建、删除、读、写、截断及文件读/ /写位置的设置；一类是对记录写位置的设置；一类是对记录的操作，包括记录的遍历（即检索所有记录）、单个记录的检索以及的操作，包括记录的遍历（即检索所有记录）、单个记录的检索以及记录的插入、修改和删除。记录的插入、修改和删除。UNIX文件和目录的布局文件和目录的布局(1)UNIX文件和目录的布局文件和目录的布局(1)/etc目录 供系统维护管理用的命令和配置文件passwd，hosts