CH4-4.1主存器和4.2连续存储管理

1、操作系统教程(第4版)第四章 存储管理高等教育出版社 2008年4月1笫四章 存储管理4.1 存储器 4.2 连续存储空间管理 4.3 分页式存储管理 4.4 分段式存储管理 4.5 虚拟存储管理 4.6 Intel x86分段和分页存储结构4.7 Linux虚拟存储管理 4.8 Windows2003虚拟存储管理 2存储管理的功能分配和去配：进程可请求对主存区的独占式使用，主存区的请求和释放（即分配和去配）操作由存储器管理完成。抽象和映射：主存储器被抽象，使得进程认为分配给它的地址空间是一个大且连续地址所组成的数组；同时建立抽象机制支持进程用逻辑地址来映射到物理主存单元，实现地址的转换。隔离

2、和共享：系统负责隔离已分配给进程的主存区，互不干扰，确保进程对存储单元的独占式使用，以实现存储保护功能；系统允许多个进程共享主存区。存储扩充：物理主存容量不应限制应用程序的大小在这种情况下，超越隔离机制并授权进程允许共享访问，达到既能提高主存利用率又能共享主存某区的目的34.1 存储器4.1.1存储器的层次 4.1.2地址转换与存储保护 44.1.1 存储器的层次寄存器高速缓存主存储器磁盘缓存固定磁盘可移动存储介质存储管理设备管理速度快5存储器的层次结构功能：储存以二进位形式表示的程序和数据分类：内存储器/外存储器内存储器外存储器(简称外存或辅存)存取速度很快较慢存储容量较小(因单位成本较高)

3、 很大(因单位成本较低) 性质断电后信息消失断电后信息保持用途存放已经启动运行的程序和需要立即处理的数据长期存放计算机系统中几乎所有的信息与CPU关系CPU所处理的指令及数据直接从内存中取出程序及相关数据必须先送入内存后才能被CPU使用64.1.2 地址转换与存储保护(1)在多道程序环境下，程序要运行必须为之创建进程，而创建进程的第一件事，就是要将程序和数据装入内存。如何将一个用户源程序变为一个可在内存中执行的程序，通常要经过以下几步 :（1）编译：由编译程序（Compiler）将用户源代码编译成若干个目标模块（Object Module）；（2）链接：由链接程序（Linker）将编译后形成的

4、目标模块以及它们所需要的库函数，链接在一起，形成一个装入模块（Load Module）；（3）装入：由装入程序（Loader）将装入模块装入内存。7程序的编译、链接、装入和执行 链接动态重定位静态重定位源程序模块1源程序模块2源程序模块n目标代码1目标代码2目标代码n可重定位目标代码(装载代码)(辅存)编译装入执行程序名字空间逻辑地址空间物理地址空间可执行二进制代码(主存)库代码可执行二进制代码(主存) 源程序中的符号名集合所限定的空间81)静态链接：在装入内存前链接成一个大的装入模块module。但需要解决两个问题，即： (1) 修改相对地址。 (2) 变换外部调用符号。2)装入时动态链接：

5、边装入边链接，即装入一个模块时，便去找它的调用模块，如有便再装入，同时修改目标模块中的相对地址。由于分开装入：便于模块更新修改；便于模块的共享。3)运行时动态链接:将对某些目标模块的链接推迟到执行时才进行。凡在执行过程中未被用到的目标模块，都不会被调入内存或被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。程序的链接 程序链接示意图 92. 程序的装入绝对装入方式可重定位装入方式（静态重定位）动态运行时装入方式（动态重定位）重要的术语： 逻辑地址，是目标程序中的地址。这种地址一般以0为基地址，顺序编址。一个作业或进程的目标程序（准确地说应是装入模块）的逻辑地址的集合称

6、为该作业或进程的逻辑地址空间，或称地址空间或虚拟空间。逻辑地址也称相对地址或虚拟地址。 物理地址，是物理存贮器的单元地址。物理地址的集合称为物理地址空间，或称存储空间或实地址空间。物理地址也称绝对地址或实地址。 重定位（或地址转换）：把装入模块中指令的逻辑地址以及数据的逻辑地址变换成内存中物理地址的过程称为重定位。101）绝对装入：只能将目标模块装入指定的内存位置 缺点：（1）在程序中必须由程序员给出绝对地址。或者说此时的相对地址和绝对地址一样；（2）要求程序员对内存使用情况非常熟悉。事先知道自己的程序将要装在什么地方；（3）只适合于单道程序环境。例如：某个程序员想在内存200处编一个程序：M

7、ov ax,20435h200204Mov ax,20435h装入程序逻辑地址相对地址内存中进程绝对地址物理地址.2002040112）可重定位的装入：装入时将逻辑地址转换为物理地址(重定位)，逻辑地址从0开始。适合于多道程序环境。地址变换在装入时一次性完成，以后不变，可看作是静态重定位。Mov ax,25003650100025005000例如:准备将程序装入内存10000处1000015000Mov ax,25003651100012500Mov ax,12500365注意：这种装入后程序不便在内存中移动。Why?123）动态运行时装入：模块装入内存后没有立即重定位，仍然是相对地址；只有当

8、CPU执行到具有相对地址的代码时才去重定位，因此是动态重定位。Mov ax,2500365010002500500010000150001100012500Mov ax,25003652500相对地址10000重定位寄存器这种装入后程序可以内存中移动，但需要重定位寄存器的硬件支持。12500物理地址13 地址转换与存储保护(2)存储保护（涉及防止地址越界和控制正确存取。）通常进程运行时所产生的所有主存访问地址都应进行检查，确保进程仅访问自己的主存区，这就是地址越界保护。依赖硬件，常用有有界地址和存储键。进程在访问分配给自己的主存区时，要对访问权限（如允许读、写、执行等）进行检查。144.2 连

9、续存储空间管理4.2.1 固定分区存储管理 4.2.2 可变分区存储管理 4.2.3 伙伴系统4.2.4 主存不足的存储管理技术154.2.2 固定分区存储管理固定分区存储管理的基本思想：主存空间被划分成数目固定不变的分区，各分区的大小不等，每个分区只装入一个作业。若多个分区中都装有作业，则它们可以并发执行。系统一启动后就已经分好了分区。（支持多道程序设计的最简单的管理技术）固定分区存储管理的数据结构：主存分配表，记录主存储器中划分的分区及其使用情况。164.2.2 固定分区存储管理作业进入固定分区排队策略（2种)：一种是每个分区有单独的作业等待队列，调度程序选中作业后，创建用户进程并将其排入

10、一个能够装入它的最小分区的进程等待队列尾部，当此分区空闲时，就装入队首进程执行。另一种是所有等待处理的作业排成一个等待队列，每当有分区空闲时，就从队首起依次搜索分区长度能容纳的作业以便装入执行，为了防止小作业占用大分区，也可以搜索分区长度所能容纳的最大作业装入执行。17固定分区存储管理的地址转换和存储保护B下限寄存器逻辑地址CPU绝对地址操作系统区用户分区1用户分区2用户分区3B+L2上限寄存器B+L2越界中断用户分区4用户分区5用户分区618固定分区分配 如何分配 （a）分区使用表：表中包含每个分区的起始地址、大小、状态。 （b）分配方法：在分区使用表中找出一个能满足要求的、尚未分配的分区。

11、将该分区分给程序、并修改分区使用表点击鼠标：对1k、9k、33k、121k作业分配内存，并修改分区状态浪费（阴影部分）：7k23k87k211k总浪费：328k操作系统0K20K28K60K180K512k-1分区1分区2分区3分区4内存分区情况分区号起始地址大小状态1未分配2未分配3未分配4未分配180k20k8k例题：某系统采用固定分区管理方式，内存分区如图。现有大小为1k、9k、33k、121k要求进入内存，画出他们进入内存的空间分配情况，说明主存浪费多大。28k60k32k120k332k分区使用表1k9k33k121k已分配已分配已分配已分配194.2.2 可变分区存储管理 可变分区

12、 存储管理是按作业的实际大小来划分分区，且分区个数也是随机的,实现多个作业对主存的共享，进一步提高主存资源利用率。系统刚启动时并不分区。系统把作业装入主存时，根据其所需要的主存容量查看是否有足够的空间，如有，则按需要分割一个分区分配给此作业；若无，则令此作业等待主存资源。20可变分区存储管理数据结构用来描述空闲分区和已分配分区的情况。常用的数据结构有以下两种形式：空闲分区链：以链表形式记录每个空闲分区的情况。空闲分区表：以表结构形式记录每个空闲分区的情况。21可变分区回收算法 回收内存： 当进程运行完毕释放内存时，系统根据回收区的首地址，从空闲分区表（链）中找到相应的插入点，将回收区插入到空闲

13、分区表（链）中的适当位置。 此时，可能出现以下四种情况之一： 1. 回收区前连空闲区 2. 回收区后连空闲区 3. 回收区前、后连空闲区 4. 回收区前、后都不连空闲区 A X B A B A X A X B B x 变为变为变为变为X终止前X终止后黑色区域为空闲区，X作业撤离22链表空闲区管理方法空闲区开头单元存放本空闲区长度及下个空闲区起始地址,把所有空闲区都链接起来,设置第一块空闲区地址指针,让它指向第一块空闲区地址。申请空闲区;归还空闲区。23可变分区管理分配算法1）最先适应分配算法 2）下次适应分配算法3) 最优适应分配算法 4）最坏适应分配算法5) 快速适应分配算法 24（1）最先

14、适应算法： 从空闲分区表或分区链（按照地址递增次序排列）头上开始查找，找到第一个满足要求的分区为止，分配内存，余下的部分然仍留在空闲分区表中。 优点：倾向于优先利用内存低地址部分的空闲分区；保留了高地址部分的空闲分区。 缺点：低地址部分不断被划分，留下很多碎片.（2）下次适应算法 总是从未分配区的上次扫描结束处顺序查找未分配区表或链表，直至找到第一个能满足要求的空闲去为止。 例题：25例题：已知主存有256k容量，其中os占地端内存20k，有下列作业序列：分析内存分配情况和空闲分区表情况 作业1 要求 80k；作业2 要求 16k；作业3 要求 140k 作业1完成；作业3完成； 作业4 要求

15、60k；作业5 要求 120k操作系统0k20k256k-1空闲分区表分区号起始地址大小120k236k作业1来到操作系统0k20k256k-1空闲分区表分区号起始地址大小1100k156k作业1100k刚开始时26作业2 16k作业3 140k分别来到后空闲分区表分区号起始地址大小1100k156k操作系统0k20k256k-1作业1100k作业2作业3116k1116k140k0作业1 完成作业3 完成操作系统0k20k256k-1作业1100k作业2作业3116k空闲分区表分区号起始地址大小120k80k2116k140k作业4 60k作业5 120k（12k?)分别来到180k20k作

16、业4作业51236k20kback27（3）最佳适应算法： 每次为作业分配内存时，总是找一个既能满足要求、又是最小的空闲分区分配给作业。 特点：为提高程序中查找速度，常常将分配表按照分区容量按照从小到大排列，查找时只需要从表首按顺序查找最合适的。 缺点：都在找最合适的分割，常会剩下一些小碎片 例题：28例题：已知内存分配情况如下图。要求填写空闲分区表，并分配如下作业序列 作业4 大小2k，作业5 大小6k， 作业6 大小2k操作系统作业10k20k256k-110k25k作业23k35k45k作业3156k48k100k分区号起始地址大小空闲分区表125k10k245k3k3100k156k作

17、业4247k1k作业5131k4k作业6133k2k改进：空闲分区表（按大小排列，便于程序）分区号起始地址大小225k10k3100k156k145k3k29（4）最坏适应算法 每次分配总是挑选出分配表（链）中最大的分区进行分配（5）快速适应算法 又称为分类搜索算法，将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表。 30可变分区地址转换与存储保护 基址基址寄存器逻辑地址CPU绝对地址操作系统区空闲分区1用户作业1空闲分区2限长限长寄存器限长越界中断31多对基址/限长寄存器 进程B虚CPU进程A虚CPU物理主存进程A私有空间进程B私有空间共享区重

18、定位寄存器1限长寄存器1重定位寄存器2限长寄存器2重定位寄存器1限长寄存器1重定位寄存器2限长寄存器2 多对重定位寄存器支持主存共享324.2.3 伙伴系统(1)伙伴原理任何尺寸为2i的空闲块都可被分为来那个尺寸为2i-1的空闲块，这两个空闲块称作伙伴。伙伴通过对大块的物理主存划分而获得假如从第0个页面开始到第3个页面结束的主存每次都对半划分，那么第一次划分获得大小为2页的伙伴，如0、1和2、3进一步划分，可以获得大小为1页的伙伴，例如0和1，2和30123012333 伙伴系统(2) 1伙伴系统原理 128k 256k 384k 512k 640k 768k 896k 1M A 128 25

19、6 512 AB64 256 512 AB64 C 128 512 128B64 C 128 512 128BD C 128 512 12864D C 128 512 256 C 128 512 1024342 Linux伙伴系统1) 以page结构为数组元素的mem_map 数组2) 以free_area_struct结构为数组元素的free_area数组3) 位图数组(bitmap) 353 Linux基于伙伴的slab分配器(1)为什么要使用slab分配器?slab的结构slab的操作 Slab举例36为什么要使用slab分配器?内核需要的主存量远远小于页框大小，如inode、vma、t

20、ask_struct等，为了更经济地使用内核主存资源，引入基于伙伴系统的slab分配器，基本思想：为经常使用的小对象建立缓存，小对象的申请与释放都通过slab分配器来管理，仅当缓存不够用时才向伙伴系统申请更多空间。 37Linux基于伙伴的slab分配器(2) cacheslabslabslabslabslabslabslabcachecacheslabslab满slab半满slab空slabslab分配器组成存pcb存inode存vma38例子task_struct slab内核用全局变量存放指向task_struct slab的指针：kmem_struct_t *task_struct_c

21、achep;初始化时，在fork_init( )中调用kmem_cache_create( )函数创建高速缓存，存放类型为task_struct的对象。每当进程调用fork( )时，调用内核函数do_fork( )，它再使用kmem_cache_alloc( )函数在对应slab中建立一个task_struct对象。进程执行结束后，task_struct对象被释放，返还给task_struct_cachep slab。39slab分配器主要操作 1）kmem_cache_create（）函数：创建专用cache，规定对象的大小和slab的构成，并加入cache管理队列；2）kmem_cache_alloc（）与kmem_cache_free（）函数：分别用于分配和释放一个拥有专用slab队列的对象；3）kmem_cache_grow（）与kmem_cache_reap（）函数：kmem_cache_grow（）它向伙伴系统申请向cache增加一个slab；kmem_cache_reap（）用于定时回收空闲slab；4)kmem_cache_destroy( )与kmem_cache_shrink( )：用于cache的销毁和收缩；5)kmalloc（）与kfree（）函数：用来从通用的缓冲区队列中申请