操作系统课件8.ppt

1、第八章 实存储器管理技术8.1 主存储器的物理组织、多级存储器 n当今许多计算机把存储器分为三级：n高速缓冲存储器（缓存）、主存储器（主存）和外部存储器（外存）。n三级存储器的比较n速度：缓存主存外存n价格：缓存主存外存n大小：缓存主存外存n存储器：能接收和保存数据、而且能根据命令提供数据的装置。 n内存储器（简称内存、主存、物理存储器）n处理机能直接访问的存储器。用来存放系统和用户的程序和数据，其特点是存取速度快，存储方式是以新换旧，断电信息丢失。n外存储器（简称外存、辅助存储器）n处理机不能直接访问的存储器。用来存放用户的各种信息，存取速度相对内存而言要慢得多，但它可用来长期保存用户信息。

2、在文件系统中介绍。3、为何要采用高速缓存？n引入缓存主要是解决主存与CPU速度不匹配问题。缓存最初应用于大型计算机系统中，但随着CPU速度越来越高，动态存储器（即内存、主存）的速度难以满足CPU对速度的要求，一般情况下，CPU访问主存需要插入等待周期，因而不能充分利用CPU的性能，缓存是面向CPU的存储器，用于存放CPU访问比较频繁的数据和代码，采用缓存可明显改善系统的性能。 4、内存的物理组织n物理地址物理地址： 把内存分成若干个大小相等把内存分成若干个大小相等的存储单元，每个单元给一的存储单元，每个单元给一个编号，这个编号称为内存个编号，这个编号称为内存地址（物理地址、绝对地址、地址（物理

3、地址、绝对地址、实地址），存储单元占实地址），存储单元占8位，位，称作字节（称作字节（byte）。）。n物理地址空间：物理地址空间： 物理地址的集合称为物理地物理地址的集合称为物理地址空间（主存地址空间），址空间（主存地址空间），它是一个一维的线性空间。它是一个一维的线性空间。5、程序的逻辑结构n程序地址：程序地址：用户编程序时所用的地址（或称逻用户编程序时所用的地址（或称逻辑地址辑地址 、虚地址、虚地址 ），基本单位可与内存的基），基本单位可与内存的基本单位相同，也可以不相同。本单位相同，也可以不相同。n程序地址空间程序地址空间（逻辑地址空间、虚地址空间）（逻辑地址空间、虚地址空间）:用户的

4、程序地址的集合称为逻辑地址空间，它用户的程序地址的集合称为逻辑地址空间，它的编址总是从的编址总是从0开始的，可以是一维线性空间，开始的，可以是一维线性空间，也可以是多维空间。也可以是多维空间。n为什么程序使用逻辑地址而不是物理地址？用户需要精确计算空间与存放地址；支持多道程序运行十分困难；程序的可移植性差。5、主存管理的主要功能n主存分配和回收：n主要任务：将主存分配给多个程序，以提高主存利用率。n选择合适的分配和回收算法及相应的数据结构，以提高主存利用率和分配、回收的速度。n地址转换和重定位：n主要任务：屏蔽物理内存使用细节，解决用户程序装入（可以部分装入）。n可执行文件生成中的链接技术n程

5、序加载(装入)时的重定位技术n进程运行时硬件和软件的地址变换技术和机构5、主存管理的主要功能n存储保护和主存共享：n解决如何在多用户和多任务环境下，实现程序代码和数据共享和保护。n代码和数据共享n地址空间访问权限（读、写、执行）n存储器扩充：n解决用户对内存容量要求与内存实际容量之间的矛盾，使运行的程序不受主存大小的限制。n由应用程序控制：覆盖；n由OS控制：交换（整个进程空间），虚拟存储的请求调入和预调入（部分进程空间）8.2 固定分区 1、基本概念 ：把主存分成若干个固定大小的存储区，每个分区给一个作业使用，直到该作业完成后才将该区归还系统。 n固定指各分区的位置和大小固定。通常在系统启动

6、后就确定了。n分区可分为用户分区和系统分区，用户分区存放用户程序，系统分区存放系统程序和管理信息。 8.2 固定分区2、固定分区分单道作业和多道作业 n单道作业下：固定分区中只划分了一个用户分区，用于用户程序，其他为系统分区。 n多道作业下：固定分区中只划分了若干个用户分区和若干个系统分区，因此，主存中可以同时存放多个用户程序。 8.2 固定分区3、用户分区的划分可用两种方式 n分区大小相等：指所有的用户分区大小都相等。 n缺点： n程序小于分区大小，可能出现内部碎片，造成主存浪费 n程序大于分区，程序无法在一个分区内装入，导致程序无法运行。 n分区大小不等：指所有用户分区的大小并不都相等 n

7、克服分区大小相等的缺点，一般划分出多个较小的分区、适量中等分区和少量大分区。小程序分配小分区。 8 M8 M8 M8 M8 MOperating SystemOperating System8 M12 M8 M8 M6 M4 M2 M固定分区(大小相同)固定分区(多种大小)8.2 固定分区4、存储分块表（MBT）n当分区大小不等时，系统需要对每个分区的信息进行记录，以便管理。n用来存储分区管理信息的数据基。nMBT中一般记录三项信息 n大小：存储块的大小，以字节为单位 n位置：存储块在主存中的起始地址 n状态：存储块是否使用标记 8.2 固定分区大小大小位置位置状态状态8K300K正使用正使用

8、8K308K未使用未使用16K316K正使用正使用16K332K正使用正使用32K348K未使用未使用128K380K正使用正使用n MBT一般放在系统分区内，通常由存储分配和释放两个模块对它进行操作。 n MBT在系统分区占用一个连续的内存空间8.2 固定分区n优点n管理简单；n硬件支持要求少，一对界地址寄存器；n缺点n主存利用率不高，存在内部碎片。n分区总数固定，限制了并发执行的程序数目。 n采用静态重定位。n可以采用一对界地址寄存器实现储存器保护。 8.3 可变分区多道管理技术 n起因：固定分区主存利用率不高，使用不灵活。n定义：指事先并未将主存划分为一块块分区，而是在作业进入主存时，按

9、作业的大小动态地建立分区，分给作业使用。 工作过程例子：计算机系统有2560KB主存，按照可变分区方式，系统首先为OS分配一个系统分区，剩余的作为一个整的分区作为用户分区。OS需要400KB，则用户区为2160KB。系统启动后，其主存分配图（a），此时有5个作业依次进入内存，其内存要求和进入时间如表： 进程进程主存主存时间时间P1600KB10P21000KB5P3300KB20P4700KB8P5500KB15OS400K2160K2560KOS400KP12560K1000KP22000KP32300KOS400KP12560K1000K2000KP32300KOS400KP12560K1

10、000K2000KP32300KP41700KOS400K2560K1000K2000KP32300KP41700KOS400K2560K1000K2000KP32300KP41700KP5900K(a)(b)(c)(d)(e)(f) n由于作业的大小以及进入主存的时间不同。形成以下特点：n分区个数可变，分区大小不固定。n主存中分布着个数和大小都是变化的自由分区。 n必须解决的问题 n记录分区信息的数据结构 n分配算法 n分配和回收操作 n数据基 由于可变分区的特点，系统需要建立一个记录分区信息的数据基，可变分区的数据基有以下几种组织方法： n存储分块表（MBT）： 与固定分区的MBT结构一样

11、。但用于可变分区存在以下缺点：n表长难确定，由于分区个数变化，因此MBT表项也需变化；n查找速度慢，由于空闲分区在表中一般没有按大小排序，查找一个可供分配的分区需要察看更多的表项。 n两个存储管理表： 为了提高查找速度，将主存分区用两个表来管理： n已分分区表（UBT）：存放已在分配使用的分区信息。n空闲分区表（FBT）：存放空闲、尚未分配使用的分区信息。 这样，分配内存只需查找FBT。 注意：表中的空表目是由于存储块在分配和回收过程中，没有对表项进行删除维护造成的。 大小位置状态8k312k已分32k320k已分-空表目120k384k-大小位置状态32k352k空闲-已分520k504k空

12、闲-空表目-空表目UBTFBTn空闲存储块链（FBC）： n原因：以上两种方式采用表格方式，表长难以确定的问题仍未解决。 n定义：采用链指针方式将空闲分区块链结在一起。 n实现方法：系统中单独在主存中申请一个空间，存放链表头指针，空闲存储块按大小组成链表，链表指针放在空闲存储块的起始位置，最后空闲存储块的链表指针存放链尾标志。 n已分存储块的管理：由于存储块分配给作业或进程后，存储块信息（大小和起始位置）在JCB或PCB中有记录，无需链表来管理。 大小:200指针:400大小:100指针:600大小:400指针:NULL指针:100存储分配算法 可变分区的主存分配算法一般有以下三种：n最佳适应

13、法： n定义：按分区的在内存的次序从头查找，找到其大小与要求相差最小的满足要求的空闲分区进行分配。 n思想：避免“大材小用”，使分区内未用部分最少。 n为了便于查找，一般对空闲存储块由小到大顺序排列，这样，第一次找到的满足要求的空闲块就是最佳的空闲块。n缺点：孤立地看，该方法似乎是最佳的，然而，从宏观和长远看，由于每次剩余的部分重是最小的，这样，在主存中会留下许多难以利用的小空闲区（外部碎片）。 n优点：较大的空闲分区可以被保留。 最先适应法n定义：按分区在内存的先后次序从头查找，找到符合要求的第一个分区进行分配。n分析：由于分区序号通常由低向高排列，因此，该算法倾向于优先利用主存的低地址部分

14、的空闲分区，高地址的空闲分区很少被利用，可以保留高端大空闲区。 n一般要求对空闲分区按地址递增的次序排列。 n优点：该算法的分配和回收的时间性能较好，可以保留高端大空闲区。 n缺点：随着低端分区不断划分，低端会出现很多较小的空闲分区，由于分配查找从低端开始，因此查找时间开销会增大。 最坏适应法 n定义：按分区在内存的先后次序从头查找，找到最大的满足要求的空闲分区进行分配。 n一般要求对空闲存储块按其大小以递增顺序排列。 n优点：减少了最佳适应法中出现过多外部碎片的缺点。 n缺点：不利于大作业的分配。 n以上分配方法各有其有优缺点，不同情况下，不同的结果 。例：某一时刻，内存分布如右图，有进程P

15、1(190K)， P2（300K），P3(20K)。问：下列情况下，采用哪种方式可使所有进程装入内存？(a)：进入内存次序为P1,P2,P3。(b):进入内存次序为P3,P2,P1。200K 350K(a)：进入内存次序为P1,P2,P3时，最佳、最先可以；最坏不可以。(b)：进入内存次序为P3,P2,P1时，最坏可以；最佳、最先不可以。存储器的紧缩和程序的浮动 n原因：固定分区和可变分区都是一种连续分配方式。 n连续分配方式：指为用户程序分配的是一个地址连续的内存空间。 n在可变分区中，会出现大量小的空闲分区，即使这些分区的总容量大于一个用户程序的要求，由于地址离散，而不能为程序所用，形成外

16、部碎片，造成内存的浪费。 存储器的紧缩和程序的浮动n解决方法： n改变连续分配方式：把程序分成若干部分，装入不同的分区中，可以解决碎片问题，但同时也带来了程序管理和执行上的复杂性。 n紧缩和浮动：通过移动程序，将碎片集中起来形成一个大分区。 n存储器紧缩 :指在主存中把离散的碎片集中起来形成一个完整的大分区的方法。 n程序浮动：指在主存中将用户程序移动。 n紧缩和浮动带来的问题： n经过紧缩后，用户程序在内存中的位置发生了变化，若要程序能正确运行，必须对程序代码和数据的地址进行变换，即进行重定位。 n重定位有两种：静态和动态重定位。 n静态重定位不行，最好的方法是采用动态重定位。 动态重定位的

17、可变分区多道管理 n动态重定位：指在程序执行过程中，每当访问指令或数据时，将要访问的程序或数据的逻辑地址转换为物理地址。由于重定位过程是在程序执行期间随着指令的执行逐步完成的，故称为动态重定位。 n说明：采用动态重定位技术，由于地址转换在程序执行期间，随着对每条指令和数据的访问而自动进行，因此，当系统进行紧缩和程序浮动时，不需要对程序做任何修改，只需将程序在主存的起始地址进行更新即可。 动态重定位的具体过程Mov r1,500100050059912345001000Mov r1,500110010001500160012340.n硬件支持 n重定位寄存器 n加法器 n界地址寄存器 n动态重定

18、位可变分区分配算法 n动态重定位可变分区分配算法与无重定位的分区算法基本上相同，采用的数据基也一样。 n区别在于：动态重定位可变分区算法中，增加了“紧缩算法”。 紧缩算法的实施时机 n通常有两种 :n在某分区被释放后立即进行紧缩。 n优点：系统主存非常整洁，只有一个连续的空闲分区，没有任何碎片，有利于空闲分块表的管理和主存分配 。n缺点：紧缩工作需要耗费系统资源，会降低CPU利用率和系统吞吐量。 n当“请求分配模块”找不到足够大的空闲分区时，再进行紧缩 n优点：减少紧缩次数，提高CPU利用率和系统吞吐量。 n缺点：增加了空闲分块表管理的复杂性。 n动态重定位可变分区分配算法的优缺点 n优点：提

19、高了主存的利用率，没有碎片。 n缺点：需要更多硬件支持，紧缩工作需要耗费机时 。8.4 多重分区管理 1、单对界地址管理技术 n定义：存储保护采用一对界地址寄存器。 n缺点： n为解决碎片问题，对存储器实施紧缩技术时，需要硬件支持。 n采用一对界地址，实施单分区存储管理技术，不便于进程间的数据共享。 2、多重分区管理技术 n定义：在系统中设置多个界地址寄存器，并且在为每个作业或进程分配主存时，可按界地址寄存器对的个数为其分配多个空闲分区，这些分区可以不相邻。 n优点： n改善了碎片情况 n便于共享 n缺点： n增加了管理的复杂性 n提高了硬件成本 8.5 简单分页 1、基本思想 n固定和可变分

20、区有碎片存在，解决碎片的两种方法，简单分页采取由连续分配变为离散分配的方法。 2、基本作法 n等分主存 n把主存划分为相同大小的存储块，称为页架，并按其在内存中的地址顺序从0开始对其编号，记为页架号或块号。 n不同系统，页架的大小不相同，但对一个特定的计算机系统来说，其大小固定不变。 n用户逻辑地址空间分页： n将用户程序的逻辑地址空间划分成若干个与页架大小相等的部分，每个部分称为页，同样，按逻辑地址顺序从0开始对页进行编号，记为页号。 n逻辑地址表示： 在分页系统中，每个逻辑地址用一个数对表示：（p,d） 其中：p：页号； d：页内偏移地址。例如：逻辑地址A，页大小为 L，则：p = INT

21、A/Ld = A mod L 逻辑地址2500，页大小1024，则p = 2，d = 452，逻辑地址可表示为（2，452）。 3、主存分配原则 n主存以页架为单位进行分配； n分配的页架可以连续，也可以不连续； n可以将作业的任意一页放入主存的任意一页架中； n作业所有页一次性全部装入主存，若主存空间不够，则作业等待。 4、页表 n定义：用于管理和维护进程页和页架映射关系的数据结构，称为页表，也叫页映象表，记为PMT。 页号页号块号块号021426384、页表n系统创建进程时，同时为其产生一个PMT。进程结束时，PMT删除。 n每个进程的页表存放在主存的一个连续地址空间中。 n系统中由一个页

22、表寄存器中，存放进程的页表的起始地址和页表长度。 5、页面大小的确定 n页面大小由机器的地址结构所决定 n地址场分两部分：页号和页内偏移 ；n地址场的长度决定最大逻辑地址空间 。n页面较小，可使页内碎片小，有利于提高主存利用率，但会使页面数量增多，导致页表过长，占用过多主存。 n页面较大，可减少页表长度，但又会使页内碎片增加。 n页面大小的选择应结合计算机指令运算的效率，通常页大小取2的幂。 n如：Intel X86，其逻辑地址结构为： 可知其地址场长度为32位，逻辑地址空间为：4G。页大小为4K(212)，页表长为1M(220) 3112 11 P d6、地址转换过程 n从逻辑地址中求出页号

23、和页偏移； n以页号为索引查找页表，得到相应的块号 ；n将块号转换为块的物理内存地址，并与页偏移相加获得相应的物理地址。 例：一个进程的PMT如图，每页1024字节，求出逻辑地址为2865的物理地址。 02142638解： P = INT2865/1024 = 2 d = 2865 mod 1024 = 817 物理地址：6x1024+817 = 6961AL281702142638681769617、简单分页优缺点n优点 n主存利用率高，不存在页外碎片，极少页内碎片，存在于每个进程最后页内。 n主存分配和释放快。 n分区管理简单。 n缺点： n要求一次将进程全部页装入主存；n存在页内碎片。8

24、.6 简单分段 1、段的定义：一组逻辑信息的集合。 2、分段的引入：主要目的是为了满足用户在编程和内存使用上要求： n方便编程：通常，一个程序是由若干个自然段组成，因而，用户希望能够把程序按逻辑关系分成若干个段，每个段有段名和长度，用户程序在执行时可按段名和段内地址进行访问。 n共享和保护：在实现程序和数据共享和保护时，都是以信息逻辑单位为基础的，比如，共享例程和函数。而在分页系统中，每页是存放信息的物理单位，本身并没有完整的意义，因而不便于实现信息共享和保护，而段是信息的逻辑单元 。3、简单分段的基本思想： n逻辑地址空间划分和表示 ：n每个进程的地址空间被划分为若干段，每段有段名； n每段

25、都从0开始连续编址，段的长度由相应的逻辑信息组的长度决定。 n段间可以不连续编址。 n采用二维地址空间来表示， V =（S，W）；其中， S：段号，W：段内地址。 n主存分配： n以段为单位进行主存分配 ；n段内连续存放：每段分配一个连续的主存物理空间； n段间可以不连续：段和段之间在主存中地址可以是离散的。 B0SA0NY0LX0PM0K逻辑段号逻辑段号01234作业作业1的地址空间的地址空间10003200500060008000PKSLN主存主存K 3200P 1500L 6000N 8000S 5000长度长度 段地址段地址01234操作系统操作系统n段表： n定义：用于记录和管理进程

26、分段信息的数据表称为段表。段表应包含：段号、段长和段的主存起始地址。n系统创建进程时,同时为其产生一个段表。进程结束时，段表删除。 n每个进程的段表存放在主存的一个连续地址空间中。 n系统中由一个段表寄存器中，存放进程的段表的起始地址和段表长度。 段号段长起始地址01K6K18004K230010K段表：n段的地址转换： 已知逻辑地址V = (2,200)， （1K=1024字节） AL220001K18002600330083926k4k8k10kNo Size Addrn简单分段的特点： n没有内部碎片； n便于共享和保护； n存在外部碎片； n由于段内连续分配，段的长度受内存空闲区大小的

27、限制； n需要更多硬件支持。 8.7 页式和段式系统的区别 n不同点： n页是信息的物理单位，分页是为了实现离散分配方式，以减少内存的碎片，提高内存利用率。或者说，分页仅仅是由于系统管理的需要，而不是用户的需要。 段是信息的逻辑单位，它含有一组其意义相对完整的信息，分段的目的是为了能更好地满足用户的需要。 n页的大小固定且由系统确定，把逻辑地址划分为页号和页内地址两部分是由硬件实现的，因而，一个系统只能有一种大小的页面。 段的长度不固定，取决于用户编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。 n分页的逻辑地址空间是一维的，即单一的线性地址空间，程序员只需利用一个地址符。即可表示一个地址。 分段的逻辑地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。 n相同点 n采用离散分配方式； n通过地址映射机构实现地址变换。 小结n掌握n固定分区n可变分区n存储分配算法：最佳、最近和最坏n存储器紧缩和程序浮动n简单分页n简单分段