主存器和连续存储管理市公开课一等奖省赛课获奖课件

操作系统教程(第4版)

第四章存放管理高等教育出版社4月主存器和连续存储管理第1页笫四章存放管理

4.1存放器4.2连续存放空间管理4.3分页式存放管理4.4分段式存放管理4.5虚拟存放管理4.6Intelx86分段和分页存放结构4.7Linux虚拟存放管理4.8Windows虚拟存放管理主存器和连续存储管理第2页存放管理功效分配和去配：进程可请求对主存区独占式使用，主存区请求和释放（即分配和去配）操作由存放器管理完成。抽象和映射：主存放器被抽象，使得进程认为分配给它地址空间是一个大且连续地址所组成数组；同时建立抽象机制支持进程用逻辑地址来映射到物理主存单元，实现地址转换。隔离和共享：系统负责隔离已分配给进程主存区，互不干扰，确保进程对存放单元独占式使用，以实现存放保护功效；系统允许多个进程共享主存区。存放扩充：物理主存容量不应限制应用程序大小在这种情况下，超越隔离机制并授权进程允许共享访问，到达既能提升主存利用率又能共享主存某区目标主存器和连续存储管理第3页4.1存放器

4.1.1存放器层次4.1.2地址转换与存放保护

主存器和连续存储管理第4页4.1.1存放器层次

存放器高速缓存主存放器磁盘缓存固定磁盘可移动存放介质存放管理设备管理速度快主存器和连续存储管理第5页存放器层次结构功效：储存以二进位形式表示程序和数据分类：内存放器/外存放器内存放器外存放器(简称外存或辅存)存取速度很快较慢存放容量较小(因单位成本较高)很大(因单位成本较低)性质断电后信息消失断电后信息保持用途存放已经开启运行程序和需要马上处理数据长久存放计算机系统中几乎全部信息与CPU关系CPU所处理指令及数据直接从内存中取出程序及相关数据必须先送入内存后才能被CPU使用主存器和连续存储管理第6页4.1.2地址转换与存放保护(1)在多道程序环境下，程序要运行必须为之创建进程，而创建进程第一件事，就是要将程序和数据装入内存。怎样将一个用户源程序变为一个可在内存中执行程序，通常要经过以下几步:（1）编译：由编译程序（Compiler）将用户源代码编译成若干个目标模块（ObjectModule）；（2）链接：由链接程序（Linker）将编译后形成目标模块以及它们所需要库函数，链接在一起，形成一个装入模块（LoadModule）；（3）装入：由装入程序（Loader）将装入模块装入内存。主存器和连续存储管理第7页程序编译、链接、装入和执行

链接动态重定位静态重定位…源程序模块1源程序模块2源程序模块n…目标代码1目标代码2目标代码n可重定位目标代码(装载代码)(辅存)编译装入执行程序名字空间逻辑地址空间物理地址空间可执行二进制代码(主存)库代码可执行二进制代码(主存)

源程序中符号名集合所限定空间主存器和连续存储管理第8页1)静态链接：在装入内存前链接成一个大装入模块module。但需要处理两个问题，即：(1)修改相对地址。(2)变换外部调用符号。2)装入时动态链接：边装入边链接，即装入一个模块时，便去找它调用模块，如有便再装入，同时修改目标模块中相对地址。因为分开装入：便于模块更新修改；便于模块共享。3)运行时动态链接:将对一些目标模块链接推迟到执行时才进行。凡在执行过程中未被用到目标模块，都不会被调入内存或被链接到装入模块上，这么不但可加紧程序装入过程，而且可节约大量内存空间。程序链接程序链接示意图主存器和连续存储管理第9页2.程序装入绝对装入方式可重定位装入方式（静态重定位）动态运行时装入方式（动态重定位）主要术语：

逻辑地址，是目标程序中地址。这种地址普通以0为基地址，次序编址。一个作业或进程目标程序（准确地说应是装入模块）逻辑地址集合称为该作业或进程逻辑地址空间，或称地址空间或虚拟空间。逻辑地址也称相对地址或虚拟地址。

物理地址，是物理存贮器单元地址。物理地址集合称为物理地址空间，或称存放空间或实地址空间。物理地址也称绝对地址或实地址。

重定位（或地址转换）：把装入模块中指令逻辑地址以及数据逻辑地址变换成内存中物理地址过程称为重定位。主存器和连续存储管理第10页1）绝对装入：只能将目标模块装入指定内存位置缺点：（1）在程序中必须由程序员给出绝对地址。或者说此时相对地址和绝对地址一样；（2）要求程序员对内存使用情况非常熟悉。事先知道自己程序将要装在什么地方；（3）只适合于单道程序环境。比如：某个程序员想在内存200处编一个程序：Movax,[204]35h200204Movax,[204]35h装入程序逻辑地址相对地址内存中进程绝对地址物理地址….2002040主存器和连续存储管理第11页2）可重定位装入：装入时将逻辑地址转换为物理地址(重定位)，逻辑地址从0开始。适合于多道程序环境。地址变换在装入时一次性完成，以后不变，可看作是静态重定位。Movax,[2500]3650100025005000比如:准备将程序装入内存10000处1000015000Movax,[2500]3651100012500Movax,[12500]365注意：这种装入后程序不便在内存中移动。Why?主存器和连续存储管理第12页3）动态运行时装入：模块装入内存后没有马上重定位，依然是相对地址；只有当CPU执行到含有相对地址代码时才去重定位，所以是动态重定位。Movax,[2500]365010002500500010000150001100012500Movax,[2500]3652500相对地址10000重定位存放器＋这种装入后程序能够内存中移动，但需要重定位存放器硬件支持。12500物理地址主存器和连续存储管理第13页地址转换与存放保护(2)

存放保护（包括预防地址越界和控制正确存取。）通常进程运行时所产生全部主存访问地址都应进行检验，确保进程仅访问自己主存区，这就是地址越界保护。依赖硬件，惯用有有界地址和存放键。进程在访问分配给自己主存区时，要对访问权限（如允许读、写、执行等）进行检验。主存器和连续存储管理第14页4.2连续存放空间管理4.2.1固定分区存放管理4.2.2可变分区存放管理4.2.3搭档系统4.2.4主存不足存放管理技术主存器和连续存储管理第15页4.2.2固定分区存放管理

固定分区存放管理基本思想：主存空间被划分成数目固定不变分区，各分区大小不等，每个分区只装入一个作业。若多个分区中都装有作业，则它们能够并发执行。系统一开启后就已经分好了分区。（支持多道程序设计最简单管理技术）固定分区存放管理数据结构：主存分配表，统计主存放器中划分分区及其使用情况。主存器和连续存储管理第16页4.2.2固定分区存放管理

作业进入固定分区排队策略（2种)：一个是每个分区有单独作业等候队列，调度程序选中作业后，创建用户进程并将其排入一个能够装入它最小分区进程等候队列尾部，当此分区空闲时，就装入队首进程执行。另一个是全部等候处理作业排成一个等候队列，每当有分区空闲时，就从队首起依次搜索分区长度能容纳作业方便装入执行，为了预防小作业占用大分区，也能够搜索分区长度所能容纳最大作业装入执行。主存器和连续存储管理第17页固定分区存放管理地址转换和存放保护B下限存放器逻辑地址CPU绝对地址操作系统区用户分区1用户分区2用户分区3B+L2上限存放器<B+L2越界中止用户分区4用户分区5用户分区6主存器和连续存储管理第18页固定分区分配怎样分配

（a）分区使用表：表中包含每个分区起始地址、大小、状态。（b）分配方法：在分区使用表中找出一个能满足要求、还未分配分区。将该分区分给程序、并修改分区使用表点击鼠标：对1k、9k、33k、121k作业分配内存，并修改分区状态浪费（阴影部分）：7k23k87k211k总浪费：328k操作系统0K20K28K60K180K512k-1分区1分区2分区3分区4内存分区情况分区号起始地址大小状态1未分配2未分配3未分配4未分配180k20k8k例题：某系统采取固定分区管理方式，内存分区如图。现有大小为1k、9k、33k、121k要求进入内存，画出他们进入内存空间分配情况，说明主存浪费多大。28k60k32k120k332k分区使用表1k9k33k121k已分配已分配已分配已分配主存器和连续存储管理第19页4.2.2可变分区存放管理

可变分区存放管理是按作业实际大小来划分分区，且分区个数也是随机,实现多个作业对主存共享，深入提升主存资源利用率。系统刚开启时并不分区。系统把作业装入主存时，依据其所需要主存容量查看是否有足够空间，如有，则按需要分割一个分区分配给此作业；若无，则令此作业等候主存资源。主存器和连续存储管理第20页可变分区存放管理数据结构

用来描述空闲分区和已分配分区情况。惯用数据结构有以下两种形式：空闲分区链：以链表形式统计每个空闲分区情况。空闲分区表：以表结构形式统计每个空闲分区情况。主存器和连续存储管理第21页可变分区回收算法

回收内存：当进程运行完成释放内存时，系统依据回收区首地址，从空闲分区表（链）中找到对应插入点，将回收区插入到空闲分区表（链）中适当位置。此时，可能出现以下四种情况之一：1.回收区前连空闲区2.回收区后连空闲区3.回收区前、后连空闲区4.回收区前、后都不连空闲区AXBABAX

A

XB

B

x

变为变为变为变为X终止前X终止后黑色区域为空闲区，X作业撤离主存器和连续存储管理第22页链表空闲区管理方法空闲区开头单元存放本空闲区长度及下个空闲区起始地址,把全部空闲区都链接起来,设置第一块空闲区地址指针,让它指向第一块空闲区地址。申请空闲区;偿还空闲区。主存器和连续存储管理第23页可变分区管理分配算法

1）最先适应分配算法2）下次适应分配算法3)最优适应分配算法4）最坏适应分配算法5)快速适应分配算法

主存器和连续存储管理第24页（1）最先适应算法：从空闲分区表或分区链（按照地址递增次序排列）头上开始查找，找到第一个满足要求分区为止，分配内存，余下部分然仍留在空闲分区表中。优点：倾向于优先利用内存低地址部分空闲分区；保留了高地址部分空闲分区。缺点：低地址部分不停被划分，留下很多碎片.（2）下次适应算法总是从未分配区上次扫描结束处次序查找未分配区表或链表，直至找到第一个能满足要求空闲去为止。

例题：主存器和连续存储管理第25页例题：已知主存有256k容量，其中os占地端内存20k，有以下作业序列：分析内存分配情况和空闲分区表情况作业1要求80k；作业2要求16k；作业3要求140k作业1完成；作业3完成；作业4要求60k；作业5要求120k操作系统0k20k256k-1空闲分区表分区号起始地址大小120k236k作业1来到操作系统0k20k256k-1空闲分区表分区号起始地址大小1100k156k作业1100k刚开始时主存器和连续存储管理第26页作业216k作业3140k分别来到后空闲分区表分区号起始地址大小1100k156k操作系统0k20k256k-1作业1100k作业2作业3116k1116k140k0作业1完成作业3完成操作系统0k20k256k-1作业1100k作业2作业3116k空闲分区表分区号起始地址大小120k80k2116k140k作业460k作业5120k（12k?)分别来到180k20k作业4作业51236k20kback主存器和连续存储管理第27页（3）最正确适应算法：每次为作业分配内存时，总是找一个既能满足要求、又是最小空闲分区分配给作业。特点：为提升程序中查找速度，经常将分配表按照分区容量按照从小到大排列，查找时只需要从表首按次序查找最适当。缺点：都在找最适当分割，常会剩下一些小碎片例题：主存器和连续存储管理第28页例题：已知内存分配情况以下列图。要求填写空闲分区表，并分配以下作业序列作业4大小2k，作业5大小6k，作业6大小2k操作系统作业10k20k256k-110k25k作业23k35k45k作业3156k48k100k分区号起始地址大小空闲分区表125k10k245k3k3100k156k作业4247k1k作业5131k4k作业6133k2k改进：空闲分区表（按大小排列，便于程序）分区号起始地址大小225k10k3100k156k145k3k主存器和连续存储管理第29页（4）最坏适应算法每次分配总是挑选出分配表（链）中最大分区进行分配（5）快速适应算法又称为分类搜索算法，将空闲分区依据其容量大小进行分类，对于每一类含有相同容量全部空闲分区，单独设置一个空闲分区链表。

主存器和连续存储管理第30页可变分区地址转换与存放保护

基址基址存放器逻辑地址CPU绝对地址操作系统区空闲分区1用户作业1空闲分区2限长限长存放器<限长越界中止主存器和连续存储管理第31页多对基址/限长存放器

进程B虚CPU进程A虚CPU物理主存进程A私有空间进程B私有空间共享区重定位存放器1限长存放器1重定位存放器2限长存放器2重定位存放器1限长存放器1重定位存放器2限长存放器2

多对重定位存放器支持主存共享主存器和连续存储管理第32页4.2.3搭档系统(1)搭档原理任何尺寸为2i空闲块都可被分为来那个尺寸为2i-1空闲块，这两个空闲块称作搭档。搭档经过对大块物理主存划分而取得假如从第0个页面开始到第3个页面结束主存每次都对半划分，那么第一次划分取得大小为2页搭档，如0、1和2、3深入划分，能够取得大小为1页搭档，比如0和1，2和301230123主存器和连续存储管理第33页搭档系统(2)

1搭档系统原理128k256k384k512k640k768k896k1MA128256512AB64256512AB64C128512128B64C128512128BDC12851212864DC128512256C1285121024主存器和连续存储管理第34页2Linux搭档系统1)以page结构为数组元素mem_map[]数组2)以free_area_struct结构为数组元素free_area数组3)位图数组(bitmap)主存器和连续存储管理第35页3Linux基于搭档slab分配器(1)为何要使用slab分配器?slab结构slab操作Slab举例主存器和连续存储管理第36页为何要使用slab分配器?

内核需要主存量远远小于页框大小，如inode、vma、task_struct等，为了更经济地使用内核主存资源，引入基于搭档系统slab分配器，基本思想：为经常使用小对象建立缓存，小对象申请与释放都经过slab分配器来管理，仅当缓存不够用时才向搭档系统申请更多空间。主存器和连续存储管理第37页Linux基于搭档slab分配器(2)

cacheslabslabslabslabslabslabslabcachecacheslabslab满slab半满slab空slabslab分配器组成存pcb存inode存vma主存器和连续存储管理第38页例子task_structslab内核用全局变量存放指向task_structslab指针：kmem_struct_t*task_struct_cachep;初始化时，在fork_init()中调用kmem_cache_create()函数创建高速缓存，存放类型为task_struct对象。每当进程调用fork()时，调用内核函数do_fork()，它再使用kmem_cache_alloc()函数在对应slab中建立一个task_struct对象。进程执行结束后，task_struct对象被释放，返还给task_struct_cachepslab。主存器和连续存储管理第39页slab分配器主要操作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()与kme