北大操作系统原理5

第五章存储管理5.1概述5.2分区存储管理5.3页式存储管理5.4段式存储管理5.5段页式存储管理5.6交换技术与覆盖技术5.7虚拟存储5.1概述5.1.1存储体系存储器的层次结构：Cache主存磁盘

高速缓存Cache：

少量的、非常快速、昂贵、易变的内存RAM：

若干兆字节、中等速度、中等价格、易变的磁盘：数百兆或数千兆字节、低速、价廉、不易变的

由操作系统协调这些存储器的使用

重要性：直接存取要求内存速度尽量快到与CPU取指速度相匹配，大到能装下当前运行的程序与数据，否则CPU执行速度就会受到内存速度和容量的影响而得不到充分发挥

内存：

是由存储单元（字节或字）组成的一维连续的地址空间，简称内存空间。用来存放当前正在运行程序的代码及数据，是程序中指令本身地址所指的、亦即程序计数器所指的存储器内存可以分为：系统区：用于存放操作系统用户区：用于装入并存放用户程序和数据5.1.2存储管理目的

用户对内存的使用要求1、充分利用内存，为多道程序并发执行提供存储基础2、尽可能方便用户使用自动装入用户程序用户程序中不必考虑硬件细节3、系统能够解决程序空间比实际内存空间大的问题4、程序在执行时可以动态伸缩5、内存存取速度快6、存储保护与安全7、共享与通信8、了解有关资源的使用状况9、实现的性能和代价

5.1.3存储管理的任务

前提:引入多道程序设计技术满足用户要求1、内存空间的管理、分配与回收记录内存的使用情况——设置相应的内存分配表（内存分配回收的依据）内存空间划分问题？静态或动态，等长或不等长内存空间的管理、分配与回收

内存分配表

位示图表示法：用一位（bit）表示一个空闲页面（0：空闲，1：占用）0…...110…...第0页第1页第i页

第n-1页内存空间的管理、分配与回收

空闲页面表：包括首页面号和页面个数，连续若干的页面作为一组登记在表中

空闲块表：空闲块首址和空闲块长度，没有记录的区域即为进程所占用

空闲块链表：将所有的空闲块链成一个链表内存空间的管理、分配与回收确定分配算法实施内存分配回收内存

分配回收方式:静态分配与动态分配内存空间的管理、分配与回收

连续性；离散性驻留性；交换性一次性；多次性2、存储共享内存共享：两个或多个进程共用内存中相同区域目的：节省内存空间，提高内存利用率实现进程通信（数据共享）共享内容：代码共享，要求代码为纯代码数据共享3、存储保护与安全

保护目的：为多个程序共享内存提供保障,使在内存中的各道程序,只能访问它自己的区域，避免各道程序间相互干拢，特别是当一道程序发生错误时,不致于影响其他程序的运行。通常由硬件完成保护功能，由软件辅助实现。（特权指令不能完成存储保护。）存储保护

保护系统程序区不被用户侵犯（有意或无意的）不允许用户程序读写不属于自己地址空间的数据（系统区地址空间，其他用户程序的地址空间）保护过程防止地址越界每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界。即当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生地址越界中断，由操作系统进行相应处理保护过程防止地址越界一般由硬件提供一对寄存器：

基址寄存器：存放起始地址

限长寄存器：存放长度（上界寄存器/下界寄存器）保护过程防止操作越权

对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。如果一个进程对共享区域的访问违反了权限规定，则发生操作越权即读写保护4内存“扩充”通过虚拟存储技术实现

用户在编制程序时，不应该受内存容量限制，所以要采用一定技术来"扩充"内存的容量，使用户得到比实际内存容量大的多的内存空间内存“扩充”具体实现是在硬件支持下，软硬件相互协作，将内存和外存结合起来统一使用。通过这种方法把内存扩充，使用户在编制程序时不受内存限制5地址映射（地址重定位，地址变换）(1)逻辑地址（相对地址，虚地址）(2)物理地址（绝对地址，实地址）(3)地址映射地址映射LoadA2003456。。1200物理地址空间LoadAdata1data13456源程序LoadA20034560100200编译连接逻辑地址空间BA=1000(1)逻辑地址（相对地址，虚地址）用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都相对于首地址而编址不能用逻辑地址在内存中读取信息(2)物理地址（绝对地址，实地址）内存中存储单元的地址，可直接寻址(3)地址映射为了保证CPU执行指令时可正确访问存储单元，需将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址，这一过程称为地址映射03456......LOADA200......0100200300.........LOADA2003456逻辑地址空间110012001300物理地址空间200VR+1000BR

原因:当程序装入内存时,操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致,而CPU执行指令时，是按物理地址进行的，所以要进行地址转换静态重定位当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换（一般在装入内存时由软件完成）动态重定位在程序运行过程中要访问数据时再进行地址变换（即在逐条指令执行时完成地址映射。一般为了提高效率，此工作由硬件地址映射机制来完成。硬件支持，软硬件结合完成）硬件上需要一对寄存器的支持5.1.4各种存储管理方案单一用户（连续区）存储管理：单用户系统在一段时间内，只有一个进程在内存，故内存分配管理十分简单，内存利用率低。内存分为两个区域，一个供操作系统使用，一个供用户使用用户程序位于RAM中的操作系统0xFFF...0位于RAM中的操作系统用户程序0ROM中的设备驱动程序用户程序位于RAM中的操作系统05.2分区存储管理方案系统把内存用户区划分为若干分区，分区大小可以相等，也可以不等。一个进程占据一个分区固定分区可变分区5.2.1固定分区预先把可分配的主存储器空间分割成若干个连续区域，称为一个分区。每个分区的大小可以相同也可以不同，如图所示。但分区大小固定不变，每个分区装一个且只能装一个作业存储分配：如果有一个空闲区,则分配给进程分区4分区3分区2分区1操作系统多个等待队列单个等待队列分区4分区3分区2分区1操作系统固定分区内存管理：设置内存分配表内存分配：内存回收：简单缺点：内存利用率不高分区号起始地址长度状态进程名5.2.2可变分区1、基本思想内存不是预先划分好的，而是当作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配。若有足够的空间，则按需要分割一部分分区给该进程；否则令其等待主存空间2、内存管理设置内存空闲块表——记录了空闲区起始地址和长度3、内存分配动态分配4、内存回收当某一块归还后，前后空间合并，修改内存空闲块表内存分配：三种分配算法首先适配算法：当接到内存申请时，查空闲块表，找到第一个不小于请求的空块，将其分割并分配（特点：简单、快速分配）最佳适配算法：接到内存申请时，在空闲块表中找到一个不小于请求的最小空块进行分配（特点：用最小空间满足要求）最坏适配算法：

接到内存申请时，在空闲块表中找到一个不小于请求的最大空块进行分配（特点：当分割后空闲块仍为较大空块）0K15K38K48K68K80K110K120K空闲区表已分配区表始址长度标志15K23K未分配48K20K未分配80K30K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ4空空0K15K38K48K68K80K110K120K空闲区表已分配区表始址长度标志15K23K未分配48K20K未分配98K12K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ685K98K碎片问题：经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为碎片

造成存储资源的浪费碎片问题的解决：紧凑技术：通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域（紧缩技术，紧致技术，浮动技术，搬家技术）

问题：开销大；移动时机

讨论：分区的保护：设置界地址寄存器保护键优点：

便于动态申请内存便于共享内存便于动态链接缺点： 碎片问题(外碎片)，内存利用率不高受实际内存容量限制5.3段式存储管理5.3.1基本思想（工作原理）...0S工作区段[B]主程序段[M]......0EP子程序段[X]0K...CALL[X][E].........CALL[Y][F]CALL[A]116......0FL子程序段[Y]0116N数组[A]12345...操作系统.....B0SA0NY0LX0PM0K逻辑段号01234作业1的地址空间10003200500060008000PKSLN主存K

3200P1500L6000N8000S5000长度段地址01234操作系统用户程序划分按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的逻辑地址内存划分内存空间被动态的划分为若干个长度不相同的区域，这些区域被称为物理段，每个物理段由起始地址和长度确定段号段内地址内存分配

以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放5.3.2管理段表：它记录了段号，段的首（地）址和长度之间的关系每一个程序设置一个段表，放在内存属于进程的现场信息段号012段首址段长度58K20K100K110K260K140K空闲块管理：记录了空闲区起始地址和长度内存的分配算法：首先适配；最佳适配；最坏适配5.3.3硬件支持系统设置一对寄存器段表始址寄存器：用于保存正在运行进程的段表的始址段表长度寄存器：用于保存正在运行进程的段表的长度（例如上图的段表长度为3）

Cl

Cb+段号S

段内地址d比较比较b+d段表S>=Cl快表物理地址段表始址寄存器段表长度寄存器逻辑地址lb...Slb地址越界d>=1d>=1地址映射及存储保护机制地址越界地址越界比较介于内存与寄存器之间的存储机制，它又叫快表用途：保存正在运行进程的段表的子集（部分表项）特点：按内容并行查找相联（联想）存储器（associativememory）

TLB（Translationlookasidebuffers）引入快表的作用：

为了提高地址映射速度快表项目：段号；段始址；段长度；标识（状态）位；访问位（淘汰位）快表淘汰问题？段的共享？段的保护？优点：便于动态申请内存管理和使用统一化便于共享便于动态链接缺点：产生碎片思考：与可变分区存储管理方案的相同点与不同点？5.4页式存储管理5.4.1基本思想（工作原理）1.用户程序划分把用户程序按逻辑页划分成大小相等的部分，称为页。从0开始编制页号，页内地址是相对于0编址逻辑地址用户程序的划分是由系统自动完成的，对用户是透明的。一般，一页的大小为2的整数次幂，因此，地址的高位部分为页号，低位部分为页内地址页号页内地址0111231页号P页内位移量W编号0~1048575相对地址0~4095内存空间：按页的大小划分为大小相等的区域，称为内存块（物理页面，页框）内存分配：

以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻...01234560123456作业的地址空间页框（物理块）页号页表主存中页框（物理块）.......5.4.2管理1.页表：系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系页表放在内存，属于进程的现场信息2.空块管理——位示图3.内存的分配与回收0310/10/10/10/10/1017……空闲块数……空块管理——位示图计算一个作业所需要的总块数N查位示图，看看是否还有N个空闲块如果有足够的空闲块，则页表长度设为N，可填入PCB中；申请页表区，把页表始址填入PCB依次分配N个空闲块，将块号和页号填入页表修改位示图5.4.3硬件支持1．系统设置一对寄存器：

页表始址寄存器页表长度寄存器2．相联存储器——快表快表表项：页号；内存块号；标识位；淘汰位p’页表地址越界

l比较P>=1pp’...快表

b+页号p页内地址dP’d物理地址页表地址寄存器页表长度寄存器逻辑地址地址映射机制5.4.6优缺点优点：解决了碎片问题便于管理缺点：不易实现共享不便于动态连接思考：页的共享？页的保护？5.5段页式存储管理5.5.1产生背景及基本思想背景：结合了二者优点克服了二者的缺点基本思想：

用户程序划分：按段式划分（对用户来讲，按段的逻辑关系进行划分；对系统讲，按页划分每一段）逻辑地址：内存划分：按页式存储管理方案内存分配：以页为单位进行分配段号段内地址页号页内地址5.5.2管理1.段表：记录了每一段的页表始址和页表长度2.页表：记录了逻辑页号与内存块号的对应关系（每一段有一个，一个程序可能有多个页表）3.空块管理：同页式管理4.分配：同页式管理5.5.3硬件支持段表始址寄存器

段表长度寄存器

相联存储器（快表）5.6交换技术与覆盖技术在多道环境下扩充内存的方法，用以解决在较小的存储空间中运行较大程序时遇到的矛盾覆盖技术主要用在早期的操作系统中交换技术被广泛用于小型分时系统中，交换技术的发展导致了虚存技术的出现

交换技术与覆盖技术共同点：进程的程序和数据主要放在外存，当前需要执行的部分放在内存，内外存之间进行信息交换不同点：如何控制交换？5.6.1覆盖技术把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域程序段先保存在磁盘上，当有关程序段的前一部分执行结束，把后续程序段调入内存，覆盖前面的程序段（内存“扩大”了）覆盖：一个作业的若干程序段，或几个作业的某些部分共享某一个存储空间一般要求作业各模块之间有明确的调用结构，程序员要向系统指明覆盖结构，然后由由操作系统完成自动覆盖A8KE4KF10KC10KB8KD12K作业X的调用结构作业X的常驻区

A（8K）覆盖区0（10K）覆盖区1（12K）BCDEF

缺点：对用户不透明，增加了用户负担

例子：目前这一技术用于小型系统中的系统程序的内存管理上，MS-DOS的启动过程中，多次使用覆盖技术；启动之后，用户程序区TPA的高端部分与COMMAND.COM暂驻模块也是一种覆盖结构5.6.2交换技术当内存空间紧张时，系统将内存中某些进程暂时移到外存，把外存中某些进程换进内存，占据前者所占用的区域，这种技术是进程在内存与外存之间的动态调度。多用于分时系统中

交换技术实现中的几个问题：

1、选择原则即：将哪个进程换出/内存？例子：分时系统，时间片轮转法或基于优先数的调度算法，在选择换出进程时，要确定换出的进程是要长时间等待的需要特殊考虑的是：任何等待I/O的进程中存在的问题解决：从不换出处于等待I/O状态的进程有些I/O进程因DMA而不能换出内存或换出前需要操作系统的特殊帮助

2、交换时机的确定何时需发生交换？例子：只要不用就换出（很少再用）只在内存空间不够或有不够的危险时换出3、交换时需要做哪些工作？需要一个盘交换区：必须足够大以存放所有用户程序的所有内存映像的拷贝；必须对这些内存映像的直接存取4、换入回内存时位置的确定换出后再换入的内存位置一定要在换出前的原来位置上吗？受地址“绑定”技术的影响，即绝对地址产生时机的限制

与覆盖技术相比，交换技术不要求用户给出程序段之间的逻辑覆盖结构；而且，交换发生在进程或作业之间，而覆盖发生在同一进程或作业内。此外，覆盖只能覆盖那些与覆盖段无关的程序段5.7虚拟存储连续性；离散性驻留性；交换性一次性；多次性以CPU时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术5.7.1概述

1、问题的提出程序大于内存程序暂时不执行或运行完是否还要占用内存

虚拟存储器的基本思想是：程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换虚拟存储器支持多道程序设计技术CPUMMU内存磁盘控制器总线虚拟地址物理地址MMU：内存管理单元XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K虚地址空间物理地址空间}虚页页框1514131211109

87654321000000000000000011110000101100000000000001111001000111010011010100010000000000100110000000000100110在/不在内存页表虚地址8196物理地址245802、程序局部性原理在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面时间局部性：一条指令被执行了，则在不久的将来它可能再被执行空间局部性：若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用3、虚拟存储技术虚存：把内存与外存有机的结合起来使用，从而得到一个容量很大的“内存”，这就是虚存实现思想：当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存工作目的：提高内存利用率5.7.2虚拟页式存储管理1、基本工作原理在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面2、页表表项页号、驻留位、内存块号、外存地址、访问位、修改位 驻留位（中断位）：表示该页是在内存还是在外存访问位：根据访问位来决定淘汰哪页（由不同的算法决定）修改位：查看此页是否在内存中被修改过页号中断位内存块号外存地址访问位修改位3、缺页中断（PageFault）在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的驻留位及相应的内存块号若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存4、页面淘汰算法先进先出页面淘汰算法（FIFO）

选择在内存中驻留时间最长的页并淘汰之第二次机会淘汰算法(SCR)

按照先进先出算法选择某一页面，检查其访问位，如果为0，则淘汰该页，如果为1，则给第二次机会，并将访问位置0理想淘汰算法—最佳页面算法（OPT）

淘汰以后不再需要的或最远的将来才会用到的页面最近最少使用页面淘汰算法（LRU）

选择最后一次访问时间距离当前时间最长的一页并淘汰之即淘汰没有使用的时间最长的页实现代价很高时间戳或硬件方法LRU的软件解决方案：最不经常使用（NFU）

选择访问次数最少的页面淘汰之实现：软件计数器，一页一个，初值为0。每次时钟中断时，计数器加R。发生缺页中断时，选择计数器值最小的一页淘汰改进：计数器在加R前先右移一位

R位加到计数器的最左端称为老化算法最近未使用页面淘汰算法（NRU）

选择在最近一段时间内未使用过的一页并淘汰之实现：设置两位访问位（R），修改位（M）

启动一个进程时，R、M置0

R被定期清零发生缺页中断时，操作系统检查R，M：

第0类：无访问，无修改第1类：无访问，有修改第2类：有访问，无修改第3类：有访问，有修改操作系统随机从编号最小的非空类中选择一页淘汰例子1：计算缺页次数某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5FIFO432143543215页1432143555211页243214333522页34321444355

xxxxxxx

x

x共缺页中断9次

LRU432143543215页1432143543215页243214354321页34321435432

xxxxxxx

xxx共缺页中断10次

OPT432143543215页1432111555211页243333333555页34444444444

xxxx

x

xx

共缺页中断7次例子2：计算缺页次数

某程序在内存中分配m页初始为空，页面走向为1，2，3，4，1，2，5，1，2，3，4，5。当m=3，m=4时缺页中断分别为多少？用FIFO算法例子2：计算缺页次数m=3时，缺页中断9次m=4时，缺页中断10次注：FIFO页面淘汰算法会产生异常现象（Belady现象），即：当分配给进程的物理页面数增加时，缺页次数反而增加5、影响缺页次数的因素(1)分配给进程的物理页面数(2)页面本身的大小(3)程序的编制方法(4)页面淘汰算法例子3：内存分配一页，初始时第一页在内存；页面大小为128个整数；矩阵A128X128按行存放程序编制方法1：

Forj:=1to128Fori:=1to128A[i,j]:=0;程序编制方法2：

Fori:=1to128Forj:=1to128A[i,j]:=0;5.7.3性能问题1、颠簸（抖动）在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖动原因：页面淘汰算法不合理分配给进程的物理页面数太少2、工作集（WorkingSet）模型

基本思想：根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理页面数太少了，使该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生中断如果能为进程提供与活跃页面数相等的物理页面数，则可减少缺页中断次数工作集：对于给定的访问序列选取定长的区间，称为工作集窗口，落在工作集窗口中的页面集合称为工作集内容取决于页的三个因素：访页序列特性时刻Ti

窗口长度(△)例：26157775162341234443434441327||t1||t2

ws(t1)={1,2,5,6,7}

ws(t2)={3,4}5.7.4虚拟段式存储管理1、段表内容增加：特征位（在/不在内存，是否可共享），存取权限位（读，写，执行），标志位（是否修改过，能否移动），扩充位（固定长/可扩充）2、越界中断处理进程在执行过程中，有时需要扩大分段，如数据段。由于要访问的地址超出原有的段长，所以发越界中断。操作系统处理中断时，首先判断该段的“扩充位”，如可扩充，则增加段的长度；否则按出错处理3、缺段中断处理检查内存中是否有足够的空闲空间

①若有，则装入该段，修改有关数据结构，中断返回

②若没有，检查内存中空闲区的总和是否满足要求，是则应采用紧缩技术，转①

；否则，淘汰一（些）段，转①4、段的动态链接大型程序：若干程序段，若干数据段一些熟知的事实：进程的某些程序段在进程运行期间可能根本不用互斥执行的程序段没有必要同时驻留内存有些程序段执行一次后不再用到

静态链接：为了程序正确执行，必须由连接装配程序把它们连接成一个可运行的目标程序，并在程序运行前都装入内存。问题：花费时间，浪费空间（1）段的动态链接在程序开始运行时，只将主程序段装配好并调入内存，其它各段的装配是在主程序段的运行过程中逐步完成。每当需要调用一个新段时，再将这个新段装配好，并与主程序段链接页式存储管理：难以完成动态链接，其逻辑地址是一维的（2）链接间接字和链接中断机器指令：直接寻址，间接寻址LOAD100LOAD100600600800直接寻址间接寻址100100数据间接字数据

采用间接寻址时，间接地址指示的单元的内容称为间接字，在间接字中，