计算机操作系统 第四版 汤小丹 课件 第4章

1、第4章存储管理、4.1存储层4.2程序加载和链接4.3连续分配存储管理方法4.4比较(Swapping) 4.5分页存储管理方法4.6段存储管理方法练习，运行4.1存储层计算机时几乎所有说明都包括存储访问，因此存储访问速度必须与处理器运行速度一致。或者，内存必须非常快，并且能够与处理器的速度匹配。否则，可能会对处理器的操作产生显着影响。此外，存储容量必须非常大，而且价格便宜。4.1.1多层存储系统1。存储的多层结构对于公用计算机，存储层必须至少为三个级别：CPU寄存器、中间基本存储和子存储。在更高端的计算机上，根据特定的功能，还可以细分为6层：寄存器、缓存、主存储、磁盘缓存、固定磁盘、可移动存

2、储介质。图4-1所示。图4-1计算机系统存储分层结构，2 .在可执行存储计算机系统的存储层中，寄存器和主存储也称为可执行内存。与存储在计算机上的信息和存储在子存储库中的信息相比，计算机使用的访问机制有所不同，需要很长时间。进程可以在极小的时钟周期内使用一个load或store命令访问执行存储。但是，由于对辅助存储的访问是通过I/O设备进行的，因此访问所需的停机时间、设备驱动程序和物理设备操作所需的时间远远超过访问可执行存储的时间，通常相差3个以上。4.1.2主内存和寄存器1。主内存主内存简单地称为内存或主内存，是用于存储进程运行时程序和数据的计算机系统的主要部件，也称为执行内存。2 .寄存器寄

3、存器与处理器的速度相同，寄存器访问速度最快，可以与CPU完美地工作，但是容量不能很大，因为价格非常昂贵。4.1.3缓存和磁盘缓存1。高速缓存缓存是最新计算机结构的重要组件，寄存器和存储之间的存储，主要备份主内存中较常用的数据，减少处理器访问主存储的次数，从而显着提高程序执行速度。缓存容量比寄存器大，但比内存小约2-3倍，访问速度比主存储(从数十KB到数MB)快。2 .磁盘缓存当前磁盘的I/O速度远远低于主存储的访问速度，因此，为了缓解两者之间的速度不一致，将设置磁盘缓存，主要用于临时存储某些常用磁盘数据和信息，从而减少磁盘访问次数。但是，与磁盘缓存不同，磁盘缓存使用主存储库中的部分存储空间，其

4、中临时存储从磁盘读取或写入的信息，而不是实际存在的存储。主存储也可以看作次存储的缓存，因为次存储中的数据必须复制到主存储才能使用，反之，数据在输出到次存储之前必须作为主存储存在。4.2程序加载和链接用户程序要在系统上运行，必须首先将用户程序加载到内存中，然后将其转换为可运行的程序。通常，请遵循以下步骤：(1)在编译、编译程序(Compiler)中编译用户源程序，以编译多个目标模块(object module)。(2)链接程序(Linker)连接编译的目标模块集和所需的库函数，以创建完整的加载模块(load module)。(3)加载，加载程序将加载模块加载到内存中。图4-2显示了此三阶段过程。

5、本节简要介绍了程序(包含数据)的链接和加载过程。图4-2介绍了用户程序的处理步骤，为了说明4.2.1程序的加载方便，不需要先链接的各个目标模块的加载过程。目标模块是装载模块。将一个加载模块加载到内存中时，可以通过三种方式装载：1 .绝对加载模式如果计算机系统较小，并且只运行单个程序，则可以准确地知道程序将驻留在内存中的位置。您可以使用绝对挂载。编译用户程序时，将生成绝对地址，即物理地址的目标代码。2 .可重定位装载模式绝对装载方法只能将目标模块装载到内存中的预指定位置，并且仅适用于单通道程序环境。在多通道程序环境中，无法预测编译后的结果目标模块在内存中的位置。因此，对于由用户程序编译形成的某些

6、目标模块，开始地址通常从0开始，程序中的其他地址也相对于开始地址进行计算。如果图4-3操作加载到内存中，则为3。动态运行时加载方法可以将装载模块装载到允许可重新定位的装载内存的任何位置，以便在多程序环境中使用。但是，此方法不允许程序在运行时在内存中移动位置。4.2.2方案的链接1。“静态链接”(Static Linking)在程序运行之前将每个目标模块和所需的库函数链接到完整的组件模块，以后不会分解。已编译的三个目标模块a、b和c如图4-4(a)所示，其长度分别为l、m和n。模块a具有调用模块B的CALL B语句。模块b具有调用模块C的CALL C语句。b和c都属于外部调用符号，因此将这些目标

7、模块装配为一个装载模块时，必须解决以下两个问题：(1)修改相对地址。(2)转换外部调用符号。图4-4程序链接图，2 .加载时动态链接是指编译用户源程序后获得的一组目标模块，在加载内存时使用装载角链接的方法。如果在加载目标模块时发生外部模块调用事件，则加载程序会找到相应的外部目标模块，将其加载到内存中，然后修改目标模块的相对地址，如图4-4所示。加载时动态链接方法具有以下优点：(1)易于修改和更新。(2)轻松共享目标模块。3 .运行时动态链接很多情况下，每次运行应用程序时，要运行的模块可能不相同。但是，您无法提前知道这次要运行的模块，因此可以将所有可运行的模块都装入内存，在安装时连接它们。这显然

8、是无效的，因为目标模块的某些部分通常根本无法运行。典型的示例是用于错误处理的目标模块，很明显，如果程序在运行过程中没有发生错误，就不会使用它。4.3连续分配存储管理方法4.3.1单连续分配在单个程序环境中，存储管理将内存分为系统区域和用户区域，系统区域只能用于操作系统，通常放在内存的较低地址部分。用户区域内存中只有一个用户程序。也就是说，整个内存中的用户空间由程序独占使用。这种存储分配方法称为单个连续分配方法。4.3.2固定分区分配1。分割分割区方法可让您使用两种方法，将记忆体中的使用者空间分割成多个固定大小的分割区：(1)分区大小相同(所有内存分区大小相同)。(2)分区大小不同。2 .为了便

9、于内存分配，分区通常按大小排队，并创建包含每个分区的起始地址、大小和状态(是否已分配)的分区使用表，如内存分配图4-5所示。，图4-5固定分区使用情况表，4.3.3动态分区分配1。动态分区分配的数据结构中常用的数据结构有两种形式：闲置分割表格，设定记录系统中每个闲置分割区状况的闲置分割表格。每个可用分区表示包含数据项的表条目，如分区编号、分区大小和分区起始地址，如图4-6所示。空闲分区链。为可用切片的分配和链接，请设置用于控制每个切片开始处切片分配的一些信息，以及用于连接每个切片的正向指针，并在切片结束处设置反向指针。通过前后链接指针，所有可用分区都可以通过双向链连接，如图4-7所示。图4-6

10、空闲分区表，图4-7空闲链结构，2。为了将新任务加载到内存中，动态分区分配算法必须根据特定分配算法在空闲分区表或空闲分区链中选择分配给任务的分区。内存分配算法对系统性能影响很大，因此通过更广泛、更深入的研究，产生了很多动态分区分配算法。3 .分区分配任务1)分配内存系统必须使用分配算法在可用分区链(表)中查找所需大小的分区。可以将请求的分区大小设置为u.size，并将表中每个可用分区的大小显示为m.size。图4-8内存分配流程，2)内存回收流程运行完成后，系统根据回收区域的第一个地址在可用区域链(表)中查找相应的插入点。此时可能出现以下四种情况之一：(1)回收区域与插入点的前一空闲区域F1相

11、邻，然后图4-9(见a)。此时，回收区不应修改旧分区F1的大小，而应与插入点的旧分区合并，而不必将新表条目分配给回收分区。(2)恢复分区与插入点处的剩馀空分区F2相邻，参见图4-9(b)。您也可以合并两个分割区以构成新的可用分割区。但是，新可用分割区的第一个位址是两个分割区的总和。(3)回收区域请参见图4-9(c)。合并三个分区，使用F1的表条目和F1的第一个地址，F2的表条目取消为三个总和。(4)回收区域与F1不相邻，与F2不相邻。必须为“回收”区域单独创建新表条目，其中已填写“回收”区域的第一个地址和大小，并根据该地址插入到空闲链中的相应位置。图4-10显示内存回收过程。图4-9内存回收时

12、，图4-10内存回收过程，基于4.3.4顺序搜索的动态分区分配算法1。以初始自适应(firstf，FF)算法可用分区链为例，说明了采用FF算法时的分配。FF算法要求空闲分区链按地址增加的顺序连接。分配内存时，从链的开头开始按顺序查找，直到找到满足要求的大小的可用分区。然后，根据作业大小在相应的分区上绘制内存空间，将其分配给请求者，其馀空闲分区保留在空闲链上。如果从链开始到链结束都找不到满足要求的分区，则系统分配给该进程的内存不足，内存分配失败并返回。2 .next fit(NF)算法旨在减少留下大量小空分区和查找可用空分区的开销，因此，循环初始自适应算法不是每次在进程中分配内存空间时都从链开始

13、，而是从上次找到的可用分区的下一个可用分区开始，直到找到满足要求的可用分区为止。此算法将与请求大小相同的内存空间分配给操作。3 .最佳拟合(best fit，BF)算法所谓的“最佳”是指每次为操作分配内存时始终满足要求，并且将最小可用分区分配给操作以避免“大材料使用量”。为了加快搜索速度，此算法要求所有可用分区按从小到大的顺序形成空闲分区链。，4。最差自适应(worst fit，WF)算法由于最差自适应分配算法，选择可用分区的策略与最佳自适应算法相反。在扫描整个可用分区表或链路表时，总是选择最大的可用区域之一，以分割要用于操作的部分存储空间，并在存储上明显缺少可用分区，因此称为最差的适应算法。

14、基于4.3.5索引搜索的动态分区分配算法1。快速fit算法(也称为分类搜索)根据可用分区的容量大小对可用分区进行分类，为每个类的所有可用分区单独创建一个可用分区关联列表，从而使系统中存在多个可用分区关联表。此外，每个索引表条目对应于可用分区类型，并且内存中记录了指向该类型可用分区链接表标题的指针的索引表管理设置。2 .合作伙伴系统(buddy system)该算法规定，无论分配的分区还是空闲分区，大小均为2的k次方(k表示整数，LKM)。通常，2m是可分配的内存总大小(即最大分区大小)。假设系统的可用空间容量为2m字，则系统启动时整个内存区域是一个大小为2m的可用分区。系统运行时连续分区，创建

15、多个离散空闲分区，这些空闲分区按分区大小分类。为大小相同的所有可用分区设置单独的可用分区双向链接列表，以便不同大小的可用分区构成k个可用分区链接的列表。在伙伴系统中，对于大小为2k且地址为x的内存块，伙伴块的地址显示为budyk (x)。这个公式是，3。散列算法。上述分类搜索算法和合作伙伴系统算法中的可用分区根据分区大小进行分类，并为大小相同的每个可用分区建立单独的可用分区列表。向进程分配空间时，必须从管理索引表(查找与所需空间大小对应的表条目)中获取相应的可用分区链接表标题指针，以获取查询的可用分区。如果进一步细化空闲分区，则该索引表的表条目也会更多，从而显着增加检索索引表的表条目所需的时间

16、开销。4.3.6动态可重新定位分区分配1。紧凑的连续分配方法的一个重要特点是，一个系统或用户程序必须装载在一个连续的内存空间中。计算机运行一段时间后，内存空间将被分割为许多没有大可用空间的小分区。即使这些分布式小分区的容量总和大于要装载的程序，也不能将程序加载到内存中，因为这些分区不相邻。图4-11的紧凑示意图，2 .动态重新定位是在4.2.1部分所述的动态运行时装载方法中，自作业加载到内存后的所有地址仍然是相对(逻辑)地址。将相对地址转换为绝对(物理)地址的操作将推迟到程序命令实际运行时进行。要防止地址转换影响命令执行速度，必须有硬件地址转换机构的支持。也就是说，必须向系统添加将程序(数据)的起始地址保存在内存中的置换寄存器。程序运行时实际访问的内存地址是通过将相对地址与重新定位寄存器的地址相加而形成的。图4-12动态重新定位图，3 .动态重新定位分割分配算法动态重新定位分割分配算法与动态分割分配算法基本相同，不同之处在于在此分配算法中添加了小功能。通常，如果此算法找不到足够大小的可用分区来满足用户要求，如果所有较小可用分区的容量总和大于用户的要求，则应“缩小”内存并将其“缩小”后获得的较大可用分区分配给用户。如果所有小