操作系统原理与设计中

《操作系统原理与设计中》由会员分享，可在线阅读，更多相关《操作系统原理与设计中（151页珍藏版）》请在装配图网上搜索。

1、ICH6 存储管理存储管理.1446.1存储管理的功能.1446.1.1主存储器空间的分配和去配.1446.1.2主存储器空间的共享.1446.1.3存储保护.1456.1.4主存储器空间的扩充.1456.2连续存储空间管理.1456.2.1重定位.1456.2.2单连续存储管理.1466.2.3固定分区存储管理.1476.2.4可变分区存储管理.1486.3分页式存储管理.1516.3.1分页式存储管理的基本原理.1516.3.2相联存储器和快表.1536.3.3分页式存储空间的分配和去配.1536.3.4页的共享和保护.1546.4分段式存储管理.1556.4.1程序的分段结构.1556.

2、4.2分段式存储管理的基本思想.1556.4.3段页式存储管理.1566.4.4段的共享.1566.4.5分段和分页的比较.1566.5虚拟存储管理的概念.1566.6分页式虚拟存储系统.1576.6.1分页式虚拟存储系统的基本原理.1576.6.2页面调度.1596.6.3页面调度算法.1606.6.4页式虚拟存储系统的几个设计问题.1636.7分段式虚拟存储系统.1666.8实例研究：INTEL的 PENTIUM.167CH7 设备管理设备管理.1727.1设备管理的基本功能.1727.2I/O 硬件原理.1727.2.1I/O设备的分类.1737.2.2I/O控制方式.1737.2.3设

3、备控制器.1747.2.4直接主存存取DMA.1757.2.5输入输出处理器通道.176II7.3I/O 软件原理.1777.3.1I/O中断处理程序.1787.3.2设备驱动程序.1797.3.3与硬件无关的I/O软件.1807.3.4用户空间的I/O软件.1817.4具有通道的 I/O 系统管理.1827.4.1I/O指令.1827.4.2通道命令和通道程序.1837.4.3通道启动和I/O操作过程.1837.5缓冲技术.1847.5.1单缓冲.1847.5.2双缓冲.1847.5.3多缓冲.1857.6驱动调度技术.1857.6.1循环排序.1857.6.2优化分布.1867.6.3交替

4、地址.1877.6.4搜查定位.1877.7设备分配.1897.7.1设备独立性.1897.7.2设备分配.1897.8虚拟设备.1907.8.1问题的提出.1907.8.2斯普林系统的设计和实现.1917.9实例研究：WINDOWS2000 的设备管理.1937.9.1Windows NT4的设备管理.1937.9.2Windows 2000设备管理的扩展.196CH8 文件管理文件管理.1998.1文件系统概述.1998.1.1文件的概念.1998.1.2文件系统及其功能.1998.2文件.2008.2.1文件的命名.2008.2.2文件的类型.2008.2.3文件的属性.2018.2.4

5、文件的存取.2018.2.5文件的使用.2028.3文件目录.2028.3.1文件目录与文件目录项.2028.3.2一级目录结构.2038.3.3二级目录结构.204III8.3.4树形目录结构.2048.4文件组织与数据存储.2058.4.1文件的存储.2058.4.2文件的逻辑结构.2078.4.3文件的物理结构.2118.5文件的保护和保密.2168.5.1文件的保护.2168.5.2文件的保护.2188.6文件系统其他功能的实现.2188.6.1目录的查找和打开文件表.2188.6.2文件操作的实现.2198.6.3文件操作的执行过程.2218.6.4辅存空间管理.2228.7实例研究

6、：WINDOWS 2000 文件系统.2248.7.1Windows 2000文件系统概述.2248.7.2NTFS的实现层次.2268.7.3NTFS在磁盘上的结构.227CH9 操作系统安全性操作系统安全性.2309.1安全性概述.2309.2隔离.2309.2.1状态隔离：.2309.2.2空间隔离.2319.3分级安全管理.2319.3.1系统级安全管理.2319.3.2用户级安全管理.2329.3.3文件级安全管理.2329.4通信网络安全管理.2329.5信息安全管理.2339.6预防、发现和消除计算机病毒.2339.7实例研究：WINDOWS2000 的安全性.2349.7.1W

7、indows2000安全性概述.2349.7.2Windows2000安全性系统组件.2359.7.3Windows2000保护对象.2359.7.4Windows2000安全审核.2389.7.5Windows2000登录过程.2399.7.6Windows2000的活动目录.2419.7.7分布式安全性扩展.2419.7.8Windows2000的文件加密.2429.7.9安全配置编辑程序.2439.8实例研究：UNIXWARE 2.1/ES 操作系统.244CH10 死锁死锁.245IV10.1死锁的产生.24510.2死锁的定义.24610.3驼鸟算法.24710.4死锁的防止.247

8、10.4.1死锁产生的条件.24710.4.2静态分配策略.24810.4.3层次分配策略.24810.5死锁的避免.24910.5.1单种资源的银行家算法.24910.5.2资源轨迹图.25010.5.3多种资源的银行家算法.25010.6死锁的检测和恢复.25210.7混合策略.253CH11 实时任务管理实时任务管理.25611.1实时操作系统概述.25611.1.1实时操作系统的基本概念.25611.1.2实时操作系统的基本术语.25611.1.3实时数字控制系统.25711.1.4实时操作系统的特点.25811.1.5实时任务.25911.2实时任务的设计.26111.2.1实时任务

9、之间的同步通信.26111.2.2定时任务和延迟任务.26311.3实时系统的实现.26411.3.1实时任务调度.26411.3.2实时任务命令的实现.26611.3.3建立任务命令程序实现流程.267CH12 操作系统结构操作系统结构.26812.1操作系统设计目标.26812.2操作系统的构件.27012.2.1内核27112.2.2进程27312.2.3线程27312.2.4管程27312.2.5类程27312.3操作系统结构概述.27412.4整体式结构.27412.5层次式结构.27612.5.1层次式结构概述.27612.5.2分层的原则.277V12.5.3对层次结构的分析.2

10、7812.6虚拟机系统.27812.7客户/服务器结构（微内核结构）.28012.7.1微内核(Microkernel)技术.28012.7.2微内核结构概述.28012.7.3微内核结构的优点.28112.7.4微内核的性能.28212.7.5微内核的设计.28312.8实例研究：WINDOWS2000 的系统结构.28512.8.1Windows2000系统结构的设计目标.28512.8.2Windows2000的关键系统组件.286144CH6存储管理存储管理存储管理是操作系统的重要组成部分，它负责管理计算机系统的存储器。存储器可分成主存储器（简称主存）和辅助存储器（简称辅存）两类，本章

11、讨论主存储器空间的管理，有关辅助存储器空间的管理可参见第四节。主存储器的存储空间一般分中两部分：一部分是系统区，存放操作系统以及一些标准子程序，例行程序等；另一部分是用户区，存放用户的程序和数据等。存储管理主要是对主存储器中的用户区域进行管理。6.1存储管理的功能存储管理的功能计算机系统采用多道程序设计技术后，往往要在主存储器中同时存放多个作业的程序，而这些程序在主存储器中的位置是不能预先知道的，所以用户在编写程序时不能使用绝对地址。现代计算机的指令中地址部分所指示的地址通常是地址，逻辑地址可从开始编号。用户按逻辑地址编写程序。当要把程序装入计算机时，首先，操作系统要为其分配一个合适的主存空间

12、。由于逻辑地址经常与分配到的主存空间的绝对地址不一致，而处理器执行指令是按绝对地址进行的，所以必须把逻辑地址转换成绝对地址才能得到信息的真实存放处。把逻辑地址转换成绝对地址的工作称地址转换。多个作业共享主存储器时，必须对主存储器中的程序和数据进行保护，并进行合理有效地调动，以达到充分发挥主存储器的效率。为方便用户编制程序，使用户编写程序时不受主存储器实际容量的限制，可以采用一定的技术“扩充”主存储器容量，可使用得到比实际容量大的主存空间。总之，存储管理的目的是要尽可能地方便用户和提高主存储器的效率。具体地说，存储管理有下面四个功能。6.1.1主主存存储储器器空空间间的的分分配配和和去去配配要把

13、作业装入主存时，必须按照规定的方式向操作系统提出申请，由存储管理进行具体分配。存储管理设置一张表格记录存储空间的分配情况，根据申请乾的要求按一定的策略分析存储空间的使用情况找出足够的空闲区域分配情况不能满足申请要求时，则让申请者处于等待主存资源的状态，直到有足够的主存空间时再分配给他。当主存储器中某个作业撤离或主动归还主存资源时，存储管理要收回它所占用的全部或部分存储空间，使它们成为空闲区域（也叫自由区），这时也要修改表格的有关项。收回存储区域的工作也称 “去配”。6.1.2主主存存储储器器空空间间的的共共享享主存储器空间的共享为了提高主存空间的利率效率，所谓主存储器空间共享有两方面的含义：共

14、享主存储器资源。采用多道程序设计技术使若干个程序同时进入主存储器，各自占用一定数量的存储空间，共同使用一个主存储器。共享主存储器的某些区域。若干个作业有共同的程序段或数据时，可将这些共同的程序段或数据存放在某个存储区域内，各作业执行时都可访问它145们。6.1.3存存储储保保护护主存储器中不仅有系统程序，而且还有若干道用户作业的程序。为了避免主存中的若干道程序相互干扰，必须对主存中的程序和数据进行保护。通常由硬件提供保护功能，软件配合实现。当要访问主存某一单元时，由硬件检查是否允许访问，若允许则执行，否则产生中断，由操作系统进行相应的处理。最基本的保护措施是规定各道程序只能访问属于它的那些区域

15、或存取公共区域中的信息，不过对公共的访问应该加以限制，一般说，一个程序执行时可能有下列三种情况：对属于自己主存区域中的今年既可读又可写；对公共区域中允许共享的信息或获得可使用的别的用户的信息，可读而不准修改；对未获得授权使用的信息，既不可读又不可写。对于不同结构的主存储器，采用的保护方法是各不相同的，在以后各节将作介绍。6.1.4主主存存储储器器空空间间的的扩扩充充在计算机硬件的支撑下，软硬件协作，可把磁盘等辅助存储器作为主存储器的扩充部分来使用。当一个大型的程序要装入主存时，可先把其中的一部分装入主存储器，其余部分存放在磁盘上，如果程序执行中需用不在主存中的信息时，由操作系统采用覆盖技术将其

16、调入主存，这样，用户编制程序时还需考虑实际主存空间的容量，就他能使用一个足够的主存储器一样。这种主存空间的扩充大大地方便了用户，使他们在编制程序量可免去考虑繁杂的覆盖问题。6.2连续存储空间管理连续存储空间管理6.2.1重重定定位位在采用多道程序设计技术的计算机系统中，往往要在主存器中时存放多个用户作业。为了方便用户都可以认为自己作业的程序和数据是存放在主存储器中从 “”单元开始的一组连续地址空间中，我们把这组地址空间称为 “逻辑地址”空间。当用户把作业交给计算机系统执行时，存储管理就为其分配一个合适的主存空间，这个分配到的主存空间可能是从“”单元开始的一个连续地址空间，称为 “绝对地址”空间

17、。由于逻辑地址经常与分到的主存空间的绝对地址不一致，而且对于每个用户的逻辑地址空间在主存储器中也没有一个固定的绝对地址空间与对应。因此，不能根据逻辑地址直接到主存储器中去取信息，但处理器执行指令是按绝对地址进行的。为保证使用的正确执行，必须根据分配到的主存区域存放指令和数据的逻辑地址转换成绝对地址。把逻辑地址转换成绝对地址的工作称 “地址转换”或“重定位”。重定位方式可以分成静态定位和动态定位两种。静态定位：在装入一个作业时，把该作业中程序的指令地址和数据地址全部转换成绝对地址。由于地址转换工作是在程序执行前集中一次完成的，所以在程序执行过程中就城需再进行地址转换工作。这种定位方式称静态146

18、定位。动态定位：动态定位是靠硬件的地址转换机构来实现的。硬件设置一个定位寄存器，当存储管理为程序分配了一个主存区域后，装入程序直接把程序装入到所分配的区域中，然后把该主存区域的起始地址存入定位寄存器中。在程序执行过程中动态地进行地址转换，只需将逻辑地址与定位寄存器中的值相加就可得到绝对地址。这种定位方式是在指令过程中进行的，所以称动态定位。采用动态定位可实现程序在主存中移动。在程序执行过程中，若需要改变程序所占的主存区域时，则把程序移到一个新的区域后，只要改变定位寄存器的内容，该程序仍可正确执行，但采用静态定位时，程序执行过程中是不能移动的。6.2.2单单连连续续存存储储管管理理单连续存储管理

19、适用于单用户的情况，个人计算机和专用计算机系统可采用这种存储管理方式。采用单连续存储管理时主存分配十分简单，主存储器中的用户区域全部归一个用户作业所占用。在这种情况管理方式下，在任一时刻主存储器最多只有一道程序，各个作业的程序只能按次序一个个地装入主存储器。单连续存储管理的地址转换多采用静态定位，如图 6-1 所示。具体来说，可设置一个栅栏寄存器（Fence Register）用来指出主存中的系统区和用户区的地址界限；通过装入程序把程序装入到从界限地址开始的区域，由于用户是按逻辑地址来编排程序的，所以当程序被装入主存时，装入程序必须对它的指令和数据进行重定位；存储保护也是很容易实现的，由装入程

20、序检查其绝对地址是否超过栅栏地址，若是，则可以装入；否则，产生地址错误，不能装入，于是一个被装入的程序执行时，总是在它自己的区域内进行，而不会破坏系统区的信息。图 6-1 采用静态重定位的单连续存储管理单连续存储管理的地址转换也可以采用动态定位，如图 6-2 所示。具体来说，可设置一个定位寄存器，它既用来指出主存中的系统区和用户区的地址界限，又作为用户区的基地址；通过装入程序把程序装入到从界限地址开始的区域，但不同时进行地址转换；程序执行过程中动态地将逻辑地址与定位寄存器中的值相加就可得到绝对地址；存储保护的实现很容易，程序执行中由硬件的地址转换机构根据逻辑地址和定位寄存器的值产生绝对地址，且

21、检查该绝对地址是否存在所分配的存储区域内，若超出所分配的区域，则产生地址错误，不允许访问该单元中的信息。图 6-2 采用动态重定位的单连续存储管理操作系统区作业i 的程序、数据等界限地址 界限寄存器作业2作业1界限地址 + 逻辑地址装入程序操作系统区用户区界限地址定位寄存器逻辑地址CPU绝对地址147由于单连续存储管理只适合单道程序系统，采用这种管理有几个主要缺点：当正在执行的程序因等待某个事件，比如，等待从外部输入数据，处理器便处于空闲状态；不管用户作业的程序和数据量的多少，都是一个作业独占存储区域，这就可能降低存储空间的利用率；计算机的外围设备利用不高。在 70 年代由于小型计算机和微型计

22、算机的主存容量不大，所以单连续存储管理曾得到了广泛的应用。例如 IBM7094 的 FORTRAN 监督系统，IBM1130 磁盘监督系统，MIT 兼容分时系统 CISS 以及微型计算机 cromemco 的 CDOS 系统，Digital Research和 Dyhabyte 的 CP/M 系统，DJS0520 的 0520FDOS 等等均采用单连续存储管理。6.2.3固固定定分分区区存存储储管管理理固定分区存储管理是预先把可分配的主存储器空间分割成若干个连续区域，每个区域的大小可以相同，也可以不同。如图 6-3 所示。图 6-3 固定分区存储管理示意为了说明各分区的分配和使用情况，存储管理

23、需设置一张 “主存分配表”，该表如图 6-4 所示。分区号起始地址长度占用标志18K8K0216K16KJob1332K16K0448K64K0564K32KJob2696K32K0图 6-4 固定分区存储管理的主存分配表主存分配表指出各分区的起始地址和长度，表中的占用标志位用来指示该分区是否被占用了，当占用的标志位为 “0”时，表示该分区尚未被占用。进行主存分配时总是选择那些标志为“0”的分区，当某一分区分配给一个作业后，则在占用标志栏填上占用该分区的作业名，在图 6-4 中，第 2、5 分区分别被作业 Job1 和 Job2 占用，而其余分区为空闲。由于固定分区存储管理是预先将主存分割成若

24、干个区，如果分割时各区的大小是按顺序排列的，如图 6-3，那么固定分区存储管理的主存分配算法十分简单，有兴趣的同学可以把它作为课后练习。操作系统区（8K）用户分区1（8K）用户分区2（16K）用户分区3（16K）用户分区4（16K）用户分区5（32K）用户分区6（32K）148固定分区存储管理的地址转换可以采用静态定位方式，装入程序在进行地址转换时检查其绝对地址是否在指定的分区中，若是，则可把程序装入，否则不能装入，且应归还所分析的区域。固定分区方式的主存去配很简单，只需将主存分配表中相应分区的占用标志位置成“0”即可。固定分区存储管理的地址转换也可以采用动态定位方式。如图 6-5 所示，系统

25、专门设置一对地址寄存器上限/下限寄存器；当一个进程占有 CPU 执行时，操作系统就从主存分配表中取出相应的地址占有上限 /下限寄存器；硬件的地址转换机构根据下限寄存器中保存的基地址 B 与逻辑地址得到绝对地址；硬件的地址转换机构同时把绝对地址和上限/下限寄存器中保存的相应地址进行比较，从而实现存储保护。图 6-5 固定分区存储管理的地址转换和存储保护采用固定分区存储管理，主存空间的利用不高，例如图 6-4 中若 Job1 和 Job2 两个作业实际只是 10和 18的主存，但它们却占用了 16和 32的区域，共有 20的主存区域占而不用，所以这种分配方式存储空间利用率不高，然而这种方法简单，因

26、此，对于程序大小和出现频繁次数已知的情形，还是合适的。例如IBM 的OS/MFT，它是任务数固定的多道程序设计系统，它的主存分配就采用固定分区方式。6.2.4可可变变分分区区存存储储管管理理1、主主存存空空间间的的分分配配和和去去配配可变分区方式是按作业的大小来划分分区。当要装入一个作业时，根据作业需要的主存量查看主存中是否有足够的空间，若有，则按需要量分割一个分区分配给该作业；若无，则令该作业等待主存空间。由于分区的大小是按作业的实际需要量来定的，且分区的个数也是随机的，所以可以克服固定分区方式中的主存空间的浪费。图 6-6 可变分区存储管理的主存分配示例随着作业的装入、撤离，主存空间被分成

27、许多个分区，有的分区被作业占用，而有的分区是空闲的。当一个新的作业要求装入时，必须找一个足够大的空闲区，把作业装入该区，如果找到的空闲区大于作业需要量，则作业装入后又把原来的空闲区分成两部分，一部分给作业占用了；另一部分又分成为一个较小的空闲区。当一作主行B下限寄存器逻辑地址CPU绝对地址操作系统区用户分区1用户分区2用户分区3B+L2上限寄存器B+L2越界中断用户分区1用户分区2用户分区3操作系统作业1空闲区作业2空闲区4K10K46K52K128K操作系统作业1空闲区作业2空闲区4K10K40K46K52K128K作业3操作系统作业1空闲区4K10K40K128K作业3149结束撤离时，它

28、归还的区域如果与其它空闲区相邻，则可合成一个较大的空闲区，以利大作业的装入。采用采用可变分区方式的主存分配示例如图 6-6。从图 6-6 可以看出，主存中分区的数目和大小随作业的执行而不断改变。为了方便主存的分配和去配，主存分配表可由两张表格组成，一张 已分配区的情况表，另一张是未分配区的情况表，如图 6-7。分区号起始地址长度标志14K6KJob1246K6KJob2（a）已分配区情况表分区号起始地址长度标志110K36K未分配252K76K未分配（b）未分配区情况表图 6-7 可变分区存储管理的主存分配表图 6-7 的两张表的内容是按图 6-6 最左边的情况填写的，当要装入长度为 30K

29、的作业时，从未分配情况表中可找一个足够容纳它的长度 36K 的人空闲区，将该区分成两部分，一部分为 30K，用来装入作业，成为已分配区；另一部分为 6K，仍是空闲区。这时，应从已分配区情况表中找一个空栏目登记作业占用的起址、长度，同时修改未分配区情况表中空闲区的长度和起址。当作业撤离时则已分配区情况表中的相应状态改成“空”，而将收回的分区登记到未分配情况表中，若有相邻空宋区则将其连成一片后登记。由于分区的个数不定，所以表格应组织成链表。常用的可变分区管理方式的分配算法有：1）最先适用分配算法。对可变分区方式可采用最先适用分配算法，每次分配时，总是顺序查找未分配表，找到第一个能满足长度要求的空闲

30、区为止。分割这个找到的未分配区，一部分分配给作业，另一部分仍为空闲区。这种分配算法可能将大的空间分割成小区，造成较多的主存 “碎片”。作为改进，可把空闲区按地址从小到大排列在未分配表中，于是为作业分配主存空间时，尽量利用了低地址部分的区域，而可使高地址部分保持一个大的空闲区，有利于大作业的装入。但是，这给收回分区带来一些麻烦，每次收回一个分区后，必须搜索未分配区表来确定它在表格中的位置且要移动表格中的登记 。2）最优适应分配算法。可变分区方式的另一种分配算法是最优适应分配算法，它是从空闲区中挑选一个能满足作业要求的最小分区，这样可保证不去分割一个更大的区域，使装入大作业时比较容易得到满足。采用

31、这种分配算法时可把空闲区按长度以递增顺利排列，查找时总是从最小的一个区开始，直到找到一个满足要求的区为止。按这种方法，在收回一个分区时也必须对表格重新排列。最优适应分配算法找出的分区如果正好满足要求则是最合适的了，如果比所要求的略大则分割后使剩下的空闲区就很小，以致无法使用。 3）最坏适应分配算法。最坏适应分配算法 是挑选一个最大的空闲区分割给作业使用，这样可使剩下的空闲区不至于太小，这种算法对中、小作业是有利的。1502、地地址址转转换换与与存存储储保保护护对可变分区方式采用动态定位装入作业，当作业执行是硬件完成地址转换。硬件设置两个专门的特权寄存器：基址寄存器和限长寄存器。基址寄存器存放分

32、配给作业使用的分区的最小绝对地址值，限长寄存器存放作业占用的连续存储空间的长度。当作业占有 CPU 运行后，操作系统可把该区的始址和长度送入基址寄存器和限长寄存器，启动作业执行时由硬件根据基址寄存器进行地址转换得到绝对地址，地址关系转换如图 6-8。 图 6-8 可变分区存储管理的地址转换和存储保护当地逻辑地址小于限长值时，则逻辑地址加基址寄存器值就可得绝对值地址；当逻辑地址大于限长值时，表示作业欲访问的地址超出了所分得的区域，这时，不允许访问，达到了保护的目的。在多道程序设计系统中，仍只需一对基址 /限长寄存器的。作业在执行过程中出现等待等，操作系统把基址 /限长寄存器的内容随同该作业的其它

33、信息，如 PSW，通用寄存器等一起保存起来。当作业被选中执行时，则把选中作业的基址 /限长值再送入基址/限长寄存器。3、移移动动技技术术当在未分配表中找不到一个足够大的空闲区来装入作业时，可采用移动技术把在主存中的作业改变存放区域，同时修改它们的基址限长值，从而使分散的空闲区汇集成一片而有利于作业的装入。移动分配的示例如图 6-9。 (a) 原主存分配情况 (b) 移动主存中的作业 (c) 装入作业 4图 6-9 移动分配示例移动虽可汇集主存的空闲区，但也增加了系统的开销，而且不是任何时候都能对一道程序进行移动的。由于外围设备与主存储器交换信息时，通道总是按已经确定的主存绝对地址完成信息传输的

34、。所以当一道程序正在与外围设备交换数据时往往不能移动，故应尽量设法减少移动。比如，当要装入一道作业时总是先挑选不经移动就可装入的作业；在不得移动时力求移动的道数最少。采用移动技术分配主存的算法如下：基址基址寄存器逻辑地址CPU绝对地址操作系统区空闲分区1用户作业1空闲分区2限长限长寄存器P。则每个作业的也表长度为 S/P（为简单起见，假定每个页表项占用一个字）。AGJDBCFEKLHI164在作业的最后一页，假定耗费主存 P/2 字。若定义f = (浪费的存储字/作业所需总存储量)来表示一个作业耗损主存量的比率，则对一个作业而言，有：浪费的存储字 = 页表使用的主存空间 + 内部碎片 = S/

35、P + P/2f = (S/P + P/2) / S = 1/P + P/2S对于确定的 S，可视 f 是页面尺寸 P 的函数。于是可以求使 f 最小的 P 值。方法是先对 P 求一阶导数f(P) = df /dP = -1/P2 + 1/2S令 df /dP = 0，求得 P0 = 开根号(2S)再对 P 求二阶导数f ”(P) = d2f /dP2 = 2/P3将 P0 = 开根号(2S)代入，得到f”(P0) = 2/(开根号(2S)3 0这表明函数 f(P)在 P0处取得极小值。也就是说，当选取 P0 = 开根号(2S)时，存储耗损比率 f0 = (开根号(2/S)为最小。这是称 P0

36、为最佳页面尺寸。反之，对于给定的页面尺寸，也可以使用同样的方法求得一个最佳的作业长度S0。下表给出了各种页面尺寸 P0 (2 的幂次)时对应的 f0和 S0值。页面尺寸（字）作业大小（S0）存储耗损率（f0）832251612813325126642K31288K1.625632K0.4512128K0.21024512K可以看出，总的趋势是当程序和页面尺寸增加时，存储耗损率（包括内部碎片和页表）下降。2、工工作作集集模模型型从充分地共享系统资源这一角度出发，当然希望主存中的作业数越多越好。但是从保证作业顺利执行、使 CPU 能够有效地得到利用的角度出发，就应该限制主存中的作业数，以避免频繁地

37、进行页面调入 /调出，导致系统的抖动。为此， P.J.Denning 认为，应该将处理机调度和主存管理结合起来进行考虑，并在 1968 年提出了工作集模型。从程序的局部性原理可知，在一段时间内作业的运行只涉及某几个页面。所谓工作集，就是指在某一段时间内作业运行所要访问的那些页面的集合。可以想象，随着作业的执行，工作集不断变化，所包含的页面数时而增多，时而减少。当执行进入某一个新阶段时，由于过渡，这一段时间的工作集所包含的页面会出现剧烈的变动，如图 6-19 所示。165图 6-19 工作集的演变过程从图上看，当作业开始运行而一次一次地把页面从辅存调入主存时，系统将分配给它很多主存块。当对存储的

38、需求暂时趋于平稳状态时，就形成了第一个工作集。随着时间的推移，作业的访问将进到下一个工作集，中间出现一个用曲线表示的过渡工作集。最初曲线是上升趋势，这是因为程序运行促使新页面的调入，工作集膨胀。一旦下一个工作集逐渐稳定时，就可以淘汰不必要的页面，而形成第二个工作集。所以工作集的一次转移，会出现先上升后下降的曲线。由此可见，如果在一段时间内，作业占用的主存块数目小于工作集时，运行过程中就会不断出现缺页中断，从而导致系统的抖动。所以为了保证作业的有效运行，在相应时间段内就应该根据工作集的大小分配给它主存块，以保证工作集中所需要的页面能够进入主存。推而广之，为了避免系统发生抖动，就应该限制系统内的作

39、业数，使它们的工作集总尺寸不超过主存块总数。通常，用 W(t, w)表示从时刻 t-w 到时刻 t 之间所访问的不同页面的集合，这就是作业在时刻 t 时的工作集。用 Nw(t, w) 表示工作集中所包含的页面数。如果系统能随Nw(t, w)的大小来分配主存块的话，就既能有效的利用主存，又可以使缺页中断尽量少地发生。通过工作集来管理主存的分配和使用，从理论上来说是一件非常好的事情，但工作集算法的实现有很多困难，目前仍然在研究和试验中。3、局局部部和和全全局局分分配配分页式虚拟存储系统排除了主存储器实际容量的约束，能使更多的作业同时多道运行，从而提高了系统的效率，但缺页中断的处理要付出相当的代价，

40、由于页面的调入、调出要增加 I/O 的负担而且影响系统效率，因此应尽可能的减少缺页中断的次数。到目前为止，我们一直没有讨论如何在相互竞争的多个可运行进程之间分配内存。当出现一次缺页中断时，页面调度算法的作用范围究竟应该局限于本进程的页面还是整个系统的页面。如果页面调度算法的作用范围是整个系统，称为全局页面调度算法。它可以在可运行进程之间动态地分配页架。如果页面调度算法的作用范围局限于本进程，称为局部页面调度算法。它实际上需要为每个进程分配固定的内存片断。在通常情况下，尤其是工作集大小会在进程运行期间发生变化时，全局算法比局部算法好。如果使用局部算法，那么即使有大量的空闲内存区存在，工作集的增长

41、仍然会导致颠簸；如果工作集收缩了，局部算法又会浪费内存。但是使用全局算法时，系统必须不断地确定应该给每个进程分配多少内存，这是比较困难的。时间过渡工作集过渡工作集第1个工作集第1个工作集过渡工作集第1个工作集第1个工作集工作集页面数166比较简单的方法是根据进程数平均分配内存，这对于大程序是不合理的。也可以根据进程数和进程大小按比例分配内存，但是缺页中断率的大小，或者说系统的颠簸也可能与之无关。一种更好的解决方法是 PEF 算法，它根据缺页中断率直接控制内存分配。具体方法是设置两个缺页中断率阀值 A 和 B。A 是较高的缺页中断率阀值，当一个进程在某段时间内的缺页中断率高于 A，就可以考虑给它

42、分配更多的内存以降低缺页中断的次数。B 是较低的缺页中断率阀值，当一个进程在某段时间内的缺页中断率低于B，就可以考虑收回分配给它的多余内存。如果发现一直不能使内存中的所有进程的缺页中断率低于 A，就应该从内存中暂时移出一些进程，以便让出部分内存，降低整个系统的缺页中断率，这事实上是一种负载控制，即中级调度。6.7分段式虚拟存储系统分段式虚拟存储系统分段式虚拟存储系统也为用户提供比主存实际容量大的存储空间。分段式虚拟存储系统把作业的所有分段的副本都存放在辅助存储器中，当作业被调度投入运行时，首先把当前需要的一段或几段装入主存，在执行过程中访问到不在主存的段时再把它们装入。因此，在段表中必须说明哪

43、些段已在主存，存放在什么位置，段长是多少。哪些段不在主存，它们的副本在辅助存储器的位置。还可设置该是否被修改过，是否能移动，是否可扩充，能否共享等标志。格式如图 6-20：图 6-20 段式虚拟存储管理的段表扩展其中：特征位: 00(不在内存)；01(在内存)；11(共享段)；存取权限: 00(可执行)；01(可读)；11(可写)；扩充位: 0(固定长)；1(可扩充)；标志位: 00(未修改)；01(已修改)；11(不可移动)；在作业执行中访问某段时，由硬件的地址转移机构查段表，若该段在主存，则按分段式存储管理中给出的办法进行地址转换得到绝对地址。若该段不在主存中，则硬件发出一个缺段中断。操作

44、系统处理这个中断时，查找主存分配表，找出一个足够大的连续区域容纳该分段。如果找不到足够大的连续区域则检查空闲区的总和，若空闲区总和能满足该分段要求，那么进行适当移动后，将该分装入主存。若空闲区总和不能满足要求，则可调出一个或几个分段在辅助存储器上，再将该分段装入主存。段号扩充位主存始址特征存取权限辅存始址标志限长167在执行过程中，有些表格或数据段随输入数据多少而变化。例如，某个分段在执行期间因表格空间用完而要求扩大分段。这只要在该分段后添置新信息就行，添加后的长度应不超过硬件允许的每段最大长度。对于这种变化的数据段，当要往其中添加新数据时，由于欲访问的地址超出原有的段长，硬件产生一个越界中断

45、。操作系统处理这个中断时，先判别一下该段的 “扩充位”标志，如可以扩充，则增加段的长度，必要时还要移动或调出一个分段以腾出主存空间。如该段不允许扩充，那么这个越界中断就表示程序出错。缺段中断和段扩充处理流程如图 6-21。图 6-21 分段式存储管理的地址转换和存储保护6.8实例研究：实例研究：Intel 的的 PentiumIntel 的 Pentium 和 Pentium Pro 既有分段机制又有分页机制，它包括 16K 个独立的段，每个段最多可以容纳 10 亿个 32 位字。Pentium 虚拟存储器的核心是两张表：LDT（局部描述符表）和 GDT（全局描述符表）。每个程序都有自己的 L

46、DT，但是所有计算机上的所有程序共享一个 GDT。LDT 描述局部于每个程序的段，包括代码、数据、堆栈等，GDT 描述系统段，包括操作系统自己。为了引用一个段，Pentium 程序必须把这个段的选择符（ selector）装入机器的 6个段寄存器中的某一个。在运行过程，要求段寄存器 CS 保存代码段的选择符，段寄存器 DS 保存数据段的选择符。每个选择符是一个 16 位数，如图 6-22 所示。选择符中的一位指出这个段是局部的还是全局的，其他 13 位是 LDT 和 GDT 的入口号。因此最多允许 8K 个段描述符索引，段描述符索引 0 是禁止使用的，它可以被装入一个段寄存器中来表示这个段寄存

47、器不可用。另外还有两位用作保护。S 段在内存否是BS 段长度发越界中断是否形成绝对地址继续执行指令移动或调出分段S 段末端相邻的空闲区长度满足要求地址错S 段可扩充是装入S 段重新启动指令调整S 段段表及主存分配表操作系统硬件否符合存取权限发保护中断是否发缺段中断非法存取否主存中有满足S 段长度的连续空闲区是否是移动或调出分段168图 6-22 Pentium 的选择符在选择符被装入段寄存器时，对应的描述符被从 LDT 和 GDT 中取出装入微程序寄存器中，以便被快速引用。一个描述符由 8 各自结构称，包括段的基址、长度和其他信息，如图 6-23 所示。图 6-23 Pentium 的代码段描

48、述符，数据段描述符略有区别其中：基地址共 32 位（分三处合并），生成内存段的首址，加上 32 位偏移形成内存地址。对于 286 程序，基地址的 2431 位不用，恒为 0；所以，286 只能处理 24 位基址。长度位共 20 位，限定段描述符寻址的内存段的长度，注意段长度的计量单位可以是字节或页。G 位用于描述颗粒大小，即段长度的计量单位。 G=0 表示长度以字节为单位；G=1 表示长度以页为单位，在 Pentium 中页的长度是固定的，为4KB。于是段的长度分别为 220字节或 2204KB=232字节。D 位：当 D=1 时，为 32 位段；当 D=0 时，为 16 位段。P 位表示内存

49、段是否在物理主存中，若 P=1，表示段在内存中，若 P=0，表示段不在内存中。Dpl 位（2 位）表示特权级（03），用于保护。0 为内核级；1 为系统调用级，2 为共享库级，3 为用户程序级。Windows 95 只用两级：0 级和3 级，即系统级和用户级。S 位为段位，当 S=1 时，表示当前段为应用程序；当 S=0 时，表示描述符将引用内存段外的系统信息（如 OS 的特别数据结构）。类型字段（3 位）表示内存段类型，如可执行代码段、只读数据段、调用门等等。A 位为访问位，表示是否访问过内存段，为淘汰作准备选择符的格式经过了精心的挑选，定位描述符十分方便。首先根据第二位选择LDT 或 GD

50、T；随后选择符被拷贝进一个内部寄存器中并且它的低三位被清零；最后LDT 或 GDT 表的起始地址被加到它上面，得到一个直接指向描述符的指针。例如选择符 72 指向 GDT 的第 9 个入口，它位于 GDT+72。现在让我们跟踪一个（选择符，偏移）被转换为物理地址的过程。只要微程序直到哪一个段寄存器正在被使用，它就能从内部寄存器中找到对应于这个选择符的完整的描述符，如果段不存在（选择符为 0），就会发生一次陷入（中断）；如果段已经被换出，就会发生一次陷入（缺段中断）。索引131 20=GDT / 1=LDT特权级（0-3）DPL基址0-15长度0-15基址24-31基址16-23G D 0长度1

51、6-19PS类型A169它随后检查偏移量是否超出了段的结尾，如果是也会发生一次陷入（越界中断）。假设段在内存中并且偏移量也在范围内，就把描述符中 32 位的基地址和偏移量相加形成所谓的线性地址（linear address），如图 6-24 所示。为了和只有 24 位基地址的保护模式（80286）以及使用 16 位段寄存器来描述 20 位基地址的实模式（8086/8088）兼容，基址被分成 3 片分布在描述符的各个位置。实际上，基址允许各个段的起始地址在 32 位线性地址空间的任何位置。图 6-24 选择符，偏移被转换为线性地址的过程如果通过全局控制寄存器中的 1 位禁止分页的话，线性地址就被

52、解释为物理地址并被送往存储器用于读写。因此在分页被禁止时，我们就得到了一个纯的分段解决方案，各个段的基址在它的描述符中。顺便提一句，段允许互相覆盖，这是因为用硬件来检查所有的段都互不重叠代价太大，完全可以通过操作系统的软件机制加以解决。在另一方面，如果分页被允许，线性地址将被解释成一个虚地址并通过页表映射成为物理地址。这里唯一真正复杂的是在 32 位虚地址和 4K 页面的情况下，一个段可能包括多达一百万个页。因此 Pentium 使用了一种两级映射以在段较小的情况下减少页表的尺寸。每个运行程序都有一个由 1024 个 32 位表项组成的页目录（page directory），它的地址由一个全局

53、寄存器指出。目录中的每一个表项都指向一个也包含1024 个 32 位表项的页表，页表项指向页架（块），这个方案如图 6-25 和图 6-26 所示。线性地址被分成 3 个域：Dir、Page 和 Offset。Dir 域被作为索引在页目录找到指向正确页表的指针；随后，Page 域被作为索引在页表找到页架的物理地址；最后， Offset 被加到页架的地址上得到需要的字节或字的物理地址。图 6-25 允许分页时线性地址的组成图 6-26 线性地址转换为物理地址的过程描述符 选择符偏移量基地址长度其他的域线性地址101012DirPageOffset线性地址1024表项页目录页表DirPage 页架

54、Offset 170如图 6-27 所示，页目录项和页表项的结构是类似的，均为 32 位，其中 20 位是页表位置/页架号，其余的未包括了由硬件设置的供操作系统使用的引用位、修改位、保护位、和其他一些有用的位。 页目录项31 12 0页表起址DAU/SR/WP 页表项31 12 0页面地址DAU/SR/WP图 6-27 页目录项和页表项的结构其中：D 位：修改位，当该页程序修改后，应先纪录为淘汰做准备。A 位：（读/写）引用位，凡对程序读写均置为已访问（ accessed），淘汰时先找 A=0 的页面（Windows 用 LRU 法）。P 位：存在位，页面在内存时， P=1。U/S 位：用户/

55、管理员（User/Supervisor）位，若 U/S=0，该页为一个管理员页面（OS 页面），用户不能访问。R/W 位：读/写（Read/Write）位，R/W=1 时允许页修改；R/W=0 时，不允许页修改；通常程序区的 R/W=0。每个页表有描述 1024 个 4K 页架的表项，因此一个页表可以处理 4M 的内存。一个小于 4M 的段将有且仅有一个页表。因此通过这种方法，短的段的地址转换只需要访问两个页。为了加快地址转换的速度， Pentium 也设置了相联存储器，又称为翻译后援存储器TLB(Translation Lookaside Buffer)，它把最近使用过的 Dir/Page

56、暂存起来，这样就可以不通过页表而快速地把线性地址转化成物理地址。Pentium 允许禁止分页，如 80286 以前的保护模式和实模式就是纯的段式系统。同样 Pentium 也可以被设置成纯的页式系统，这是只要让所有的段寄存器都被设置成同一个选择符，它的描述符基址是 0，长度是最大的。这样，只有一个 32 位的地址空间被使用，指令偏移将成为线性地址，实际上就是一般的分页。必须承认，Pentium 的设计非常巧妙，它实现了互相冲突的目标：段页式存储管理、纯的页式存储管理、纯的段式存储管理、同 80286 以前的保护模式和实模式兼容。下面讨论一下 Pentium 的保护机制。它支持 4 个保护级别，

57、0 级权限最高，3 级权限最低。一种典型的应用是把 4 个保护级别依次设定为：0 级为操作系统内核级。处理 I/O、存储管理、和其他关键操作。1 级为系统调用处理程序级。用户程序可以通过调用这里的过程执行系统调用，但是只有一些特定的和受保护的过程可以被调用。2 级为共享库过程级。它可以被很多正在运行的程序共享，用户程序可以调用这些过程，都去它们的数据，但是不能修改它们。1713 级为用户程序级。它受到的保护最少。当然，上面的保护级别划分并不是一定的，各个操作系统实现可以采用不同的策略，如 Windows-95 只使用了 0 级和 3 级。在任何时刻，运行程序都处在由 PSW 中的两位所指出的某

58、个保护级别上，系统中的每一个段页由一个级别。只要运行程序使用与它同级的段，一切都会很正常。对更高级别数据的存取是允许的，而对更低级别数据的存取是非法的并会引起陷入（保护中断）。调用不同级别的过程是允许的，但是要通过一种被严格控制着的方法。为了执行越级调用，CALL 指令必须包含一个选择符而不是地址，选择符指向一个称为调用门（call gate）的描述符，由它给出被调用过程的地址。因此要跳转到任何一个不同级别的代码段的中间都是不可能的，必须正式地指定入口点。陷入和中断采用了一种和调用门类似的机构，它们引用的也是描述符而不是地址，这些描述符指向将被执行的特定过程。描述符的类型域可以区分是代码段、数

59、据段、还是各种门。 172CH7设备管理设备管理7.1设备管理的基本功能设备管理的基本功能现代计算机系统中配置了大量外围设备。一般说，计算机的外围设备分为两大类：一类是存储型设备，如磁带机、磁盘机等。以存储大量信息和快速检索为目标，它在系统中作为主存储器的扩充，所以，又称辅助存储器；另一类是输入输出型设备，如显示器、卡片机、打印机等。它们把外界信息输入计算机，把运算结果从计算机输出。设备管理是操作系统中最庞杂和琐碎的部分，普遍使用 I/O 中断、缓冲器管理、通道、设备驱动调度等多种技术，这些措施较好地克服了由于外部设备和主机速度上不配所引起的问题，使主机和外设并行工作，提高了使用效率。但是，在

60、另一方面却给用户的使用带来极大的困难，它必须掌握 I/O 系统的原理，对接口和控制器及设备的物理特性要有深入了解，这就使计算机推广应用受到很大限制。为了方便地使用各种外围设备。以上两类外围设备的物理特性各不相同，因此，操作系统对它们的管理也有很大差别。为了使这些设备在用户面前具有统一的格式和一致的面貌，对于存储型设备，信息以文件为单位存取；对于输入输出设备，信息以文件为单位输入输出。这样，用户可以通过“按名存取”文件实现对外围设备的访问，而不必考虑直接控制外围设备时应做的许多繁琐工作。操作系统除了要提供文件系统外，还必须要有实现对外围设备上文件信息的物理存取和设备控制的功能。操作系统中完成这一

61、功能的程序就是设备管理。设备管理要达到的主要目标是：提供统一界面、方便用户使用，发挥系统的并行性，提高 I/O 设备使用效率。为此，设备管理通常应具有以下功能：外围设备中断处理缓冲区管理外围设备的分配外围设备驱动调度虚拟设备及其实现其中，前四项是设备管理的基本功能，最后一项是为了进一步提高系统效率而设置的，往往在规模较大操作中才提供，每一种功能对不同的系统、不同的外围设备配置也有强有弱。7.2I/O 硬件原理硬件原理不同的人对于 I/O 硬件有着不同的理解。在电气工程师看来， I/O 硬件就是一堆芯片、电线、电源、马达和其他设备的集合体；而程序员则主要注意它为软件提供的接口，即硬件能够接受的命

62、令、它能够完成的功能、以及能报告的各种错误等。作为操作系统的设计者，我们的立足点主要是针对如何利用 I/O 硬件的功能进行程序设计已提供一个方便用户的实用接口，而并非研究 I/O 硬件的设计、制造和维护。通常把 I/O 设备及其接口线路、控制部件、通道和管理软件称为 I/O 系统，把计173算机的主存和外围设备的介质之间的信息传送操作称为输入输出操作。随着计算机技术的飞速进步和应用领域扩大，计算机的输入输出信息量急剧增加，输入输出操作不仅影响计算机的通用性和扩充性，而且成为计算机系统综合处理能力及性能价格比的重要因素。7.2.1I/O 设设备备的的分分类类按照输入输出特性，I/O 设备可以划分

63、为输入型外围设备、输出型外围设备和存储型外围设备三类。按照输入输出信息交换的单位， I/O 设备则可以划分为字符设备和块设备。输入型外围设备和输出型外围设备一般为字符设备，它与内存进行信息交换的单位是字节，即一次交换 1 个或多个字节。所谓块是连续信息所组成的一个区域，块设备则一次与内存交换的一个或几个块的信息，存储型外围设备一般为块设备。存储型外围设备又可以划分为顺序存取存储设备和直接存取存储设备。顺序存取存储设备严格依赖信息的物理位置进行定位和读写，如磁带。直接存取存储设备的重要特性是存取任何一个物理块所需的事件几乎不依赖于此信息的位置，如磁盘。7.2.2I/O 控控制制方方式式输入输出控

64、制在计算机处理中具有重要的地位，为了有效地实现物理I/O 操作，必须通过硬、软件技术，对 CPU 和 I/O 设备的职能进行合理分工，以调解系统性能和硬件成本之间的矛盾。按照 I/O 控制器功能的强弱，以及和 CPU 之间联系方式的不同，可把 I/O 设备的控制方式分为四类，它们的主要差别在于中央处理器和外围设备并行工作的方式不同，并行工作的程度不同。中央处理器和外围设备并行工作有重要意义，它能大幅度提高计算机效率和系统资源的利用率。询问方式：又称程序直接控制方式，在这种方式下，输入输出指令或询问指令测试一台设备的忙闲标志位，决定主存储器和外围设备是否交换一个字符或一个字。早期计算机和微机往往

65、采用这种方式，中央处理机的大量时间用在等待输入输出的循环检测上，使主机不能充分发挥效率，外围设备也不能得到合理使用，整个系统的效率很低。中断方式：中断机构引入后，外围设备有了反映其状态的能力，仅当操作正常或异常结束时才中断中央处理机。实现了一定程度的并行操作，这叫程序中断方式。由于输入输出操作直接由中央处理器控制，每传送一个字符或一个字，都要发生一次中断，因而仍然消耗大量中央处理器时间。若为外围设备增加缓冲寄存器存放数据，则可大大减少中断次数。中央处理器在外围设备与缓冲寄存器交换信息期间可执行其它指令。例如行式打印机、卡片机、字符显示器等均配置数据缓冲寄存器，提高了中央处理器和外围设备并行工作

66、的程度。DMA 方式：在直接主存存取方式中， I/O 控制器有更强的功能，它不仅设有中断机构，而且，还增加了 DMA 控制机构。在 DMA 控制器的控制下，它采用偷窃总线控制权的方法，让设备和主存之间成批交换数据，而不必由 CPU 干予。这样可减轻 CPU 的负担，因每次传送数据时，不必进入中断系统；只要 CPU 暂停几个周期，从而，使 I/O 数据的速度也大大提高。目前，在小型、微型机中的快速设备均采用这种方式， DMA 的操作全部由硬件实现，不影响 CPU 寄存器的状态。DMA 方式线路简单，价格低廉，但功能较差，不能满足复杂的 I/O 要求。因而，在中大型机中174使用通道技术。通道技术：通道又称输入输出处理器。它能完成主存储器和外围设备之间的信息传送，与中央处理器并行地执行操作。采用通道技术主要解决了输入输出操作的独立性和各部件工作的并行性。由通道管理和控制输入输出操作，大大减少了外围设备和中央处理器的逻辑联系。从而，把中央处理器从琐碎的输入输出操作中解放出来。此外，外围设备和中央处理器能实现并行操作；通道和通道之间能实现并行操作；各通道上的外围设备也能实现并行操作，以达到提高