操作系统精美版2013os8章内存管理

第8章内存管理8.1背景8.2交换8.3连续内存分配8.4分页8.5页表结构8.6分段8.7实例：IntelPentium8.1背景P236※为了解决CPU和存储器之间速度上的不匹配，存储系统分为三级存储结构快，贵，小主存地址，字节，统一编址存放CPU频繁访问的数据外存，辅存，慢，大频繁访问的磁盘数据放内存贵小快存储管理设备管理增加：存储管理的主要任务存储管理的4个主要任务：(1)支持多道程序并发，互不干扰的共享存储资源(2)方便用户，减少用户对存储器的管理(3)提高存储器的利用率和系统吞吐量(4)从逻辑上扩充内存空间，支持大程序能在小的内存空间运行或允许更多的进程并发执行。(虚拟存储)增加：存储管理的主要功能存储管理的6个主要功能：1.存储空间的分配和回收2.地址转换逻辑地址转换为物理地址的过程称作重定位或地址映射

2种重定位方式

(1)静态重定位(2)动态重定位3.主存空间的共享4.主存空间的保护(避免相互干扰)5.主存储空间的扩充(虚拟存储逻辑上扩充内存容量)6.交换（内外存交换）8.1.1基本硬件程序必须调入内存才可运行完全调入，部分调入内存中有2个区域操作系统区域（常驻内存）一般在内存低地址端，因为中断向量在低地址用户进程区域每个进程都有自己独立的内存空间通过基地址寄存器和界限寄存器来确定合法的内存地址（内存保护）P236图8.1

基地址寄存器和界限寄存器定义的逻辑地址空间操作系统进程进程进程基地址界限P236P237图8.2

采用基地址寄存器和界限寄存器的硬件地址保护地址基地址基地址＋界限地址操作系统监视器陷阱——寻址错误内存P2378.1.2地址绑定进程的程序和数据必须调入内存才可运行在磁盘上等待调入内存的进程形成输入队列用户程序在运行之前需要经历若干步骤（见下一页）。在这些步骤中，地址可能有不同的表示形式符号（源程序中）可重定位的地址（目标模块）绝对地址（内存映像）运行前需要得到内存的物理地址(绝对地址)P238图8.3一个用户程序的多步骤处理源程序编译器和汇编器编译时间加载时间执行时间其它目标模块目标模块链接器加载模块系统库加载器动态链接的系统库动态链接二进制内存镜像3种地址绑定方式：编译时：编译时生成绝对地址(MS-Dos的文件)

加载时：装入/加载时，相对地址变换为绝对地址(静态重定位)

运行时：运行时动态链接，程序执行时，相对地址变换为绝对地址（动态重定位）P238增加：程序的编译、链接、装入和运行1.编辑阶段：使用某种编辑软件，编辑源程序文件，如file1.c2.编译阶段：将初始的文本文件(file1.c)变成CPU可以识别的一系列二进制代码文件(file1.o)3.链接阶段：将编译后得到的一组目标模块以及它们所需的库函数装配成一个完整的装入模块3种链接方式：

静态链接

装入时动态链接运行时动态链接4.装入阶段：用户程序装入内存（要进行重新定位）相对地址→绝对地址5.运行阶段：经调度程序调度，进入CPU运行8.1.3逻辑地址与物理地址空间逻辑地址：由CPU生成；也称为虚拟地址(用户永远只能看到逻辑地址)物理地址：内存单元所看到的地址(内存中的实际存放地址)地址映射：运行时逻辑地址到物理地址的映射由内存管理单元MMU完成(硬件)动态重定位：需要设置重定位寄存器(基址寄存器)P239图8.4使用重定位寄存器的动态重定位逻辑地址重定位寄存器物理地址内存内存管理单元P2398.1.4动态加载一个子程序只有在调用时才被加载一般子程序库采用动态加载优点：更好的内存空间利用率，不用的子程序不会被装入内存8.2交换交换：内外存交换中级调度（换入，换出）滚进、滚出－根据进程的优先级来交换滚出：高优先级进程来了，换出低优先级进程，以便装入和执行高优先级的进程滚入：当高优先级进程执行完，低优先级进程可以换入内存以继续执行。滚入滚出的交换策略本在许多系统中被采用。（如UNIX,Linux及Windows)交换时间与需要交换的内存空间大小直接成正比。P241图8.5使用磁盘作为备份存储的两个进程的交换操作系统用户空间内存进程P1进程P2换出换入备用存储空间P241增加：储存管理方式目的：1.提高存储器的利用率2.提高系统吞吐量分配方式分类（3大类）：1.连续分配方式(分配连续内存空间)

(1)单一连续分配方式

(2)分区式分配方式

a.固定分区分配方式

b.动态分区分配方式

c.可重定位分区分配方式2.离散分配方式(不要求连续内存空间)(1)分页存储管理(2)分段存储管理方式(3)段页式存储管理3.虚拟存储系统(逻辑上扩充内存容量)(1)请求分页系统(2)请求分段系统(3)

请求段页式系统8.3连续内存分配连续分配方式(分配连续内存空间)(1)单一连续分配方式（单分区分配）(2)分区式分配方式

a.固定分区分配方式

b.动态分区分配方式（可变分区）

c.可重定位分区分配方式（紧缩技术解决外碎片）8.3.1单一连续分配۝

用于单用户单任务操作系统۝

内存分为系统区和用户区，操作系统用系统区，单用户使用全部用户区空间۝

优点：

不需要硬件支持，简单۝

缺点：单道，内存浪费，CPU利用率低P244图8.6重定位寄存器和界限地址寄存器的硬件支持逻辑地址物理地址界限地址寄存器重定位寄存器捕获：地址错误P2448.3.2内存分配۝

把内存分为一些大小相等或不等的多个区域，一旦划分结束，则保持不变۝

划分分区的方法

(1)分区大小相等(无法装入大进程，小进程有内碎片，浪费空间)

(2)分区大小不等(多个小分区，适量中等分区，少量大分区)۝

内存分配与回收

(1)数据结构：分区说明表(按分区大小排队)

(2)内存分配和回收算法固定分区分配图分区大小不等的固定分区示意图分区4分区3分区2分区1操作系统多个等待队列单个等待队列分区4分区3分区2分区1操作系统图固定分区分配的分区说明表图固定分区分配的内存回收算法۝

分配算法：见右图۝

回收算法：简单(将分区状态改为"未分配")动态分区分配（可变分区分配）۝

动态分区分配(可变分区分配)：根据作业运行的实际需要，动态地为之分配内存空间۝

不预先设置分区的数目和大小，在作业装入内存时，根据实际情况确定分区数目和大小۝

不存在内碎片，可能有外碎片۝

动态分区分配中的数据结构：

(1)

空闲分区表

(2)空闲分区链图可变分区分配的空闲分区表0K15K38K48K68K80K110K120K空闲区表已分配区表空空未分配30K80K未分配20K48K未分配23K15K标志长度始址空J410K110K空J312K68KJ210K38KJ115K0K标志长度始址分区分配表：分区分配表示意图可变分区分配0K15K38K48K68K80K110K120K空闲区表已分配区表空空未分配12K98K未分配20K48K未分配23K15K标志长度始址J55K80KJ410K110KJ613K85KJ312K68KJ210K38KJ115K0K标志长度始址85K98K若有2个进程申请5K,13K空间空闲分区链动态分区分配算法■为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一个分区分配给该作业。■目前常用的有5种分配算法①首次/最先适应算法(firstfit)②循环首次适应算法(nextfit)(下次适应算法)③最佳适应算法(bestfit)④最坏适应算法(worstfit)⑤快速适应算法(quickfit)顺序搜索法分类搜索法1.首次/最先适应算法■要求：空闲分区表或链按起始地址递增的次序排列■分配过程：1.从空闲分区表(链)首开始顺序查找，找到第一个大于或等于所要求内存长度的分区，则结束查找2.然后从该分区中划出所要求的内存长度分配给请求者，余下的空闲分区仍留在空闲分区表(链)中，并修改表(链)项■特点：1.优先利用内存低地址部分的空闲分区，从而保留高地址部分的大空闲区2.由于低地址部分不断被划分，致使低地址端留下许多难以利用的小空闲分区(外碎片)3.每次查找都是从低地址部分开始，增加了查找可用空闲分区的开销2.循环首次/下次适应算法■类似首次适应算法■不同之处：不再每次从空闲分区表(链)首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找■特点：1.使存储空间的利用更加均衡2.减少了查找空闲分区的开销3.但会导致缺乏大的空闲分区3.最佳适应算法■要求：空闲分区按容量大小递增的次序排列■查找：从空闲分区表(链)首开始顺序查找，找到第一个大于或等于所要求内存长度的分区，则结束查找（找到满足作业要求又与作业大小最接近的空闲分区）■特点：1.尽可能为作业选择大小一致的空闲分区，从而保留大的空闲分区2.但空闲分区一般不可能正好和作业申请的内存空间大小相等，因而将其分割成两部分时致使留下许多难以利用的小空闲分区(外碎片)（宏观上不一定最佳）4.最坏适应算法■要求：空闲分区按容量大小递减的次序排列■查找：查找第一个空闲分区，若不满足，则分配失败，否则分配■特点：1.总是挑选满足作业要求的最大分区分配给作业，这样使分给作业后剩下的空闲分区也比较大，能装下其它作业（宏观上不一定最坏）2.由于最大的空闲分区总是因首先分配而划分，当有大作业到来时，其存储空间的申请往往得不到满足5.快速适应算法■要求：空闲分区按容量大小容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表（多个空闲分区链表，一个索引表）。■容量确定：一般为进程常用空间大小，如2KB,4KB,8KB等■分配：根据进程的长度，寻找到能容纳它的最小空闲分区链表，取下第一块分配即可■特点：1.分配时不用任何分割，能保留大的分区，也不存在碎片2.但归还主存时算法复杂，系统开销大，一个分区只属于一个进程，非常浪费存储空间动态分区分配流程u.size：作业请求的分区大小m.size：每个空闲分区的大小size：可再分配的最小分区大小动态分区回收■当进程运行结束释放内存时，系统要回收已经使用完毕的空闲区，并将其插入空闲分区表(链)。在将回收的空闲区插入空闲分区表(链)时，要考虑剩余空闲区的合并问题■有4种情况(问题：空闲区数目、首地址、大小如何改变)动态分区的分配和回收实例1.初始时只有一个分区2.按FIFO为进程ABCD分配内存3.在某一时刻，进程C运行完后释放内存4.进程E(设需要内存50K)和进程F(设需要内存18K)，要求采用最先适应算法为进程EF分配内存5.进程BD完成后释放内存动态分区分配习题习题1：某系统主存容量为512KB,采用动态存储区管理方式，某时刻t，主存中有3个空闲区，它们的首地址和大小分别为：空闲区1(30KB,100KB)，空闲区2(180KB,36KB)，空闲区3(260KB,60KB)(1)画出t时刻内存分布图(2)用首次适应算法和最佳适应算法画出t时刻空闲区的队列结构60KB第3块36KB第2块100KB第1块30KB180KB260KB0512KB-1习题1(1)解答：动态分区分配习题习题1(2)解答：首次适应算法，链表按地址从低到高排列∧60KB0180KB100KB0260KB36KB030KB队列指针空闲区标志位空闲区大小下一空闲区地址动态分区分配习题习题1(2)解答：最佳适应算法，链表按容量从小到大排列∧100KB0260KB36KB030KB60KB0180KB队列指针动态分区分配习题习题2：某操作系统采用可变分区存储管理，用户区主存512KB，自由区有可用分区表管理，若分配时采用分配自由区的低地址部分，假设初始时全为空，对于下述申请次序：req(300KB),req(100KB),release(300KB),req(150KB),req(30KB),req(40KB),req(60KB)，回答下列问题(1)采用首次适应算法FF，自由空区中有哪些空块（给出地址，大小）(2)若采用最佳适应算法BF，回答(1)中问题(3)若采用最坏适应算法BF，回答(1)中问题(4)如果再申请90KB，针对(1)(2)(3)各有什么结果动态分区分配习题习题3：用可变分区管理主存时，假定主存中按地址顺序依次有5个空闲区，空闲区的大小依次为32KB,10KB,8KB,228KB,100KB，现有5个作业J1,J2,J3,J4和J5，它们各需主存量为1KB,10KB,108KB,28KB,115KB，（1）若采用最先适应分配算法，能把这5个作业按J1~J5的顺序全部装入主存吗？按怎样的次序装入这5个作业可使主存利用率最高（2）若采用下次适应，最佳适应，最坏适应算法，顺序装入J1~J5的情况怎样？在各种适应算法中，各按什么顺序装入5个作业使主存利用率最高动态分区分配习题习题4：设某时刻系统中有3个空闲区，其大小和首地址分别为(35KB,100KB),(12KB,156KB),(28KB,200KB)，设作业序列及其内存请求为(Job1,20KB),(Job2,15KB),(Job3,15KB),(Job4,13KB)，设操作系统分配空闲区时，从空闲区的高地址开始分配（1）分别使用首次适应，最佳适应，最坏适应3种算法对该作业序列进行分配。分别画出空闲区队列的初始状态和分配后的状态（2）根据分配的情况进行算法比较增加：伙伴系统■固定分区方式限制了活动进程的数目，当进程大小与空闲分区大小不匹配时，内存利用率很低■动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大■伙伴系统是对以上2种内存分区方式的折中方案■伙伴系统规定：无论是已分配分区或空闲分区，其大小均为2的k次幂(k为某个正整数)。■例如：当用户申请长度为n的内存时，分配的空闲分区大小为2i，通过(2i-1＜n≤2i)可计算出i。■对每一类具有相同大小的所有空闲分区，都设置一个空闲分区双向链表（多个空闲分区链表）增加：伙伴系统1）空闲分区链表结构

★假设系统的可利用内存空间容量为2m个字(地址从0到2m-1)★开始运行时，整个内存是一个大小为2m的空闲分区★在运行了一段时间之后，被分隔成若干已分配分区和空闲分区★为了再分配时查找方便，将所有大小相同的空闲分区构成一个双向链表，这样的链表可能有m+1个★将这m+1个链表头指针用向量结构组织成一个表，称为可利用空间表增加：伙伴系统2）伙伴系统的分配和回收空间：分配空间时可能需要多次分割回收空间时可能需要多次合并可利用空间表示意图伙伴系统习题习题1：已知一个大小为512的存储区，假设先后有6个用户申请大小为23，45，52，100，11，19的存储空间，然后再顺序释放45，52，11的占用分区，假设以伙伴系统实现存储管理。（1）画出可利用空间表的初始状态（2）画出为6个用户分配后可利用空间表的状态，以及每个用户得到的存储块的起始地址（3）画出回收3个占用块之后的可利用空间表的状态伙伴系统习题习题1解答：（1）画出可利用空间表的初始状态说明：双向链表0首地址0：未被占用9：29（空闲分区大小为512）29∧28∧27∧26∧25∧24∧23∧22∧21∧20900伙伴系统习题习题1：（2）画出为6个用户分配后可利用空间表的状态，以及每个用户得到的存储块的起始地址分析：202122232425262728291248163264128256512要求分配的大小：23，45，52，100，11，19实际应给分区大小：3264641281632分配：23，45，52，100，11，1905120642562561283212864322304525625612832128643223045256256643212864322319252045128256643212864322319252384100045128256641612864322319252384100110451282563216128643223192523841001119224习题1解答：（2）画出为6个用户分配后可利用空间表的状态，以及每个用户得到的存储块的起始地址∧29∧2827∧262524∧23∧22∧21∧2040485022470384序号要求大小起始地址123024564352128410025651132619192回收：45，52，1104512825632161286432231925238410011192240128256321612864322319252384100111922464不能合并0128256321612864322319264384100111922464不能合并0128256321612864322319264384100161922464合并1282563212864322319264384100192246432考虑：若接下来将19回收，会怎么样？习题1解答：（3）画出回收3个占用块之后的可利用空间表的状态∧29∧2827∧262524∧23∧22∧21∧2060647038460128603260224伙伴系统习题习题2：在下图所示伙伴系统中，回收2块首地址分别为768及128，大小为27的存储块，请画出回收后该伙伴系统的状态图习题2解答：地址为768与896的两个27空闲块，合并为28空闲块，再与前面地址为512的28空闲块合并为一个地址为512的29的空闲块，地址为128和256的2个27空闲块由于不是伙伴，不能合并8.3.3碎片◆可重定位（动态重定位）引入原因

碎片问题：经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为碎片或零头，造成存储资源的浪费◆碎片分类：内碎片、外碎片◆碎片问题的解决紧凑技术：（紧缩技术，拼接技术，浮动技术，搬家技术）——通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域，消除了内零头

问题：1.开销大；2.移动时机（当找不到足够大的空闲分区且空闲分区的总容量可以满足作业要求时进行拼接）动态重定位紧缩技术图动态重定位分配算法8.4分页离散分配方式的引入◎问题：在动态分区的存储空间中，由于是连续分配，存在“零头”问题（碎片问题）。尽管采用“紧凑”技术可以解决这个问题，但要为移动大量信息花去不少的处理机时间，代价较高。◎解决：离散分配（页式，段式，段页式）◎离散分配：允许将进程分散地装入到许多不相邻接的分区中

分页存储管理方式：离散分配的基本单位是页

分段存储管理方式：离散分配的基本单位是段

段页存储管理方式：先分段，段内再分页8.4.1分页的基本方法1.页面和物理块■分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号。从0开始编制页号，页内地址是相对于0编址。■相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理/内存)块或页框/帧(frame)■在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。

（逻辑上相邻的页，物理上可不相邻）2.页面大小的确定■页面的大小应选择得适中页面太小，页内碎片少，但进程所占页面多，页表大页面太大，页表数目减少，但页内碎片增多■页面大小应是2的幂，通常为512B~8KB3.分页的地址结构■分页地址中的地址结构如下：位移量W页号P311090■对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面大小为L，则页号P和页内地址w可按下式求得：4.页表■页表列出了作业的逻辑页与其在主存中的物理块的对应关系（页号，块号）■见P247图8.7图8.8■见P249图8.9■地址映射：将用户地址空间的逻辑地址变换为内存空间的物理地址，

借助页表来完成地址映射分页存储管理的地址映射页表首地址页表长度页表寄存器<越界中断P247图8.7分页的硬件支持分页模型逻辑内存物理内存页表帧号■页表的每一个表目称为页描述子.除了包含指向页框的指针外，还包括一个存取控制字段P247图8.8逻辑内存和物理内存的分页模型分页例子逻辑内存物理内存页表P249图8.9使用4B的页对32B的内存进行分页的例子增加:分页实例■例如：指令LOAD1,2500的地址变换过程如下：虚拟起址页号位移量页数页表起址块号位移量块号存储控制若页号>页表大小则中断若访问不允许则中断物理地址页号块号权限021328指令页表寄存器页描述子页表内存①①⑦②②+③③④④⑤⑥⑥⑥⑦5.分页的碎片问题■分页存储管理不会产生外碎片，可能在最后一页产生页内碎片。■思考:最大和最小的页内碎片是多少6.空闲帧空闲帧组织方法:1.列表法(见P250图8.10)2.位示图法0310/10/10/10/10/1017……空闲块数……空闲帧的组织空闲帧列表空闲帧列表新进程新进程分配前分配后新进程的页表P250图8.10空闲帧8.4.2硬件支持(相联存储器TLB)■问题：如果把页表放在主存中，无疑会影响系统的性能。这是因为每次访问主存，首先必须访问页表，读出页描述子，之后根据形成的实际地址再访问主存，这样使访问主存的次数加倍(2次访存)，因而使总的处理速度明显下降■解决：采用一组高速缓冲寄存器(Cache，联想寄存器，快表,转换表缓冲区TLB)，存放当前访问过的页的页描述子■实现：每次访问主存时，首先查找快表，若找到所需的页描述子，则快速形成物理地址。否则从页表中查找后形成物理地址，同时把页描述子写入快表。如果设计得当，快表的命中率可以很高。带快表的分页系统逻辑地址物理地址物理内存页表页号帧号TLB:转换表缓冲区(相联存储器)TLB命中TLB失效关键:尽可能提高快表命中率图8.11带TLB的分页硬件P2528.4.3内存保护帧号有效-无效位页表图8.12在页表中的有效位(v)和无效位(i)■页描述子中除包含帧号、还包含有效－无效位、存取控制位（读写位）P2538.4.4共享页进程P1进程P2进程P3P1的页表P2的页表P3的页表图8.13在分页环境下的代码共享P2548.5页表结构■问题：现代的大多数计算机系统，都支持非常大的逻辑地址空间(232~264)。页表就变得非常大，要占用相当大的内存空间■解决：可采用两个方法来解决这一问题：①采用离散分配方式来解决难以找到一块连续的大内存空间的问题：②只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入8.5.1层次页表■将页表进行分页，离散的将大页表的各个页面存放在不同的物理块中。■用外层页表来记录页表页面的物理块号■例如：32位逻辑地址，页面大小4KB，则1级页表有20位页号2级页表有12位外层页内地址，10位外层页号两级页表外部页表页表页表的页P256图8.14一个两级页表方案二级页表的地址转换逻辑地址外页表页表的页P256图8.15二级32位分页体系的地址转换多级页表■32位机器，可采用两级页表■64位机器，需要采用3级页表■原因：64位机，假设页面大小为4K(12位)，则页内位移为12位，页表位移为12位，则剩下40位为页目录偏移，则共有240个页表项，则要占240个连续空间，令人无法忍受■解决：用3级页表哈希页表逻辑地址哈希函数哈希表物理地址物理内存P258图8.16哈希页表处理超过32位地址空间的常用方法是使用哈希页表（要解决冲突问题）反向页表逻辑地址物理地址物理内存搜索页表P259图8.17反向页表反向页表：对每一个真正的内存才有一个页表条目优点：节省页表空间（不在内存中的页没有页表条目）缺点：搜索费时（不能直接计算页表条目的地址，只能顺序搜索）增加：页式内存管理的分配和回收■页式的内存分配：（修改PCB和位示图/空闲块表）①计算一个作业所需要的总块数N②查位示图或空闲块表，看看是否还有N个空闲块③如果有足够的空闲块，则页表长度设为N，可填入PCB中；申请页表区，把页表始址填入PCB④依次分配N个空闲块，将块号和页号填入页表⑤修改位示图■页式的内存回收：

回收页表空间，修改进程的PCB，修改位示图和空闲块个数页式习题■习题：假定某采用页式存储管理的系统中，主存容量为1M，被分成256块，块号为0，1，2，……，255.现有一个共4个页面（页号为0，1，2，3）的作业被依次装入主存的第2，4，1，5块中。请回答：（1）主存地址应该用多少位来表示（2）作业每一页的长度是多少字节？逻辑地址中的页内地址部分应占多少位？（3）写出作业中的每一个占用主存的主存块的起始地址（4）若作业执行中需要从第0页的第75单元和第3页的第548单元读信息，那么，实际应从主存的哪两个单元读信息，请把应访问的主存绝对地址用二进制编码的十六进制数表示8.6分段■在分页存储系统中，作业