存储器管理第五章

第五章存储器管理

5.1程序的装入和链接5.2连续分配存储管理方式5.3分页存储管理方式5.4分段存储管理第五章存储器管理

存储管理的功能内存分配、回收存储保护地址变换存储共享存储扩充第五章存储器管理

存储管理的功能内存分配、回收存储保护确保每道用户进程都在自己的内存空间中运行，互不干扰，冲突和破坏;多道：用户进程不允许访问OS的程序和数据；而且用户进程不允许访问其他用户进程的程序和数据空间。第五章存储器管理

存储管理的功能存储保护每个进程都分别有一个上界限地址寄存器和一个下界限地址寄存器，每次访问内存时都与这两个界限寄存器比较，判断是否越界。程序A0100H01FFH0100H01FFH下界限地址寄存器上界限地址寄存器内存需要硬件来实现:第五章存储器管理

存储管理的功能地址变换将逻辑地址转化为物理地址程序1程序20000H0FFFH0000H08FFHOS区程序10000H0FFFH程序20000H08FFH1000H1FFFH2000H28FFHJMP0421H×JMP2421H第五章存储器管理

存储管理的功能存储共享多个进程共用同一系统软件，如编译程序，存放编译程序的内存区即为共享内存区;在逻辑上扩充内存容量，采用虚拟存储器技术。存储扩充一个用户源程序变为可在内存中执行的程序，步骤：用户源程序

编译多个目标模块

链接一个装入模块

装入装入内存(可在内存中执行的程序)第五章存储器管理

5.1程序的装入和链接一、程序的装入1.绝对装入方式

由装入程序根据装入模块中的地址,将程序和数据装入内存。逻辑地址：源程序经过编译后形成的目标模块或装配链接程序的地址编码。物理地址：程序在主存储器中的地址编码。逻辑地址=物理地址5.1程序的装入和链接一、程序的装入2.可重定位装入方式

…Moveah,[300]4789……0100300400

程序

内存装入并进行静态地址重定位1000…Moveah,[1300]4789……110013001400装入位置内存中代码的地址部分已经被修改5.1程序的装入和链接一、程序的装入2.可重定位装入方式

物理地址=逻辑地址+本程序在内存中的起始地址---静态重定位

在程序执行之前进行的重定位，在程序装入内存时一次性完成指令中地址的修改。静态重定位无需硬件的支持，由装入模块负责完成;缺点：程序装入内存后，不允许移动在内存中的位置;5.1程序的装入和链接一、程序的装入3.动态运行时装入方式

…Moveah,[300]4789……0100300400

程序

内存1000…Moveah,[300]4789……110013001400装入位置原封不动装入执行到语句时，进行地址重定位1000重定位寄存器加法器30010001300动态重定位的实现5.1程序的装入和链接一、程序的装入3.动态运行时装入方式

装入主存的程序仍然保持原来的逻辑地址，由逻辑地址到物理地址的转换在程序真正执行时进行。---动态重定位动态重定位必须有硬件的支持

重定位寄存器—存放程序在内存的起始地址

加法器—将起始地址与相对地址相加获得物理地址优点：装入内存后，代码可以移动二、程序的链接5.1程序的装入和链接1.静态链接

对相对地址进行修改;变换外部调用符号;二、程序的链接5.1程序的装入和链接2.装入时动态链接

3.运行时动态链接

对某些模块的链接推迟到执行时才执行;优点:加快程序的装入过程，而且可节省大量的内存空间。

优点：便于修改和更新。(2)便于实现对目标模块的共享。

程序是在连续区域中，还是划分成若干块放在不同区域中？内存是事先还是动态划分？对于不同的内存分配方案，采用的地址变换技术也不同。5.2连续分配存储管理方式5.2连续分配存储管理方式连续分配：是指为一个用户程序分配一个连续的内存空间。分类：单一连续分配方式分区式分配方式固定分区式动态分区(可变分区)5.2.1单一连续分配适用于单用户、单任务的操作系统中;内存分为两个区域：系统区，用户区在DOS中就采用了这种方法。

系统区仅提供给OS使用，通常放在内存的低址部分；用户区是指除系统区以外的全部内存空间，提供给用户使用。5.2连续分配存储管理方式5.2.2固定分区分配一、划分分区的方法5.2连续分配存储管理方式缺点:缺乏灵活性。任何程序，无论多小，都要占据一个分区，造成内存空间的浪费;程序太大，不能放到分区中;内部碎片：分配给进程的分区中，进程没有使用的部分1.分区大小相等

示意图2.分区大小不等

示意图优点:克服分区大小相等而缺乏灵活性的缺点，可根据程序的大小为之分配适当的分区。缺点:还是有内部碎片；仍然存在作业太大不能运行的问题；内存分配§6.2分区式存储管理程序132k程序250k内存分成大小相等的分区64k64k64k64k64k程序3120k没有足够大的分区程序1程序2空闲空间称为内部碎片内部碎片1.分区大小相等

2.分区大小不等

程序132k程序250k内存分成大小不等的分区16k32k64k128k程序3120k32k程序1程序2程序3程序4180k

作业太大内部碎片5.2.2固定分区分配二、内存分配5.2连续分配存储管理方式

分区使用表：分区由小到大进行排队，记录分区的大小，起始地址，是否已分配等信息20未分配5.2.3动态分区分配5.2连续分配存储管理方式

分区的个数和大小不是固定不变的，而是可变的，随装入的作业动态划分；且不会产生内部碎片。动态分区(可变分区)

示意图克服外部碎片的一种技术是压缩（紧凑）。移动进程，使零散的小空闲空间连成一片。

必须采用动态重定位—可重定位分区分配（5.2.4）外部碎片：若存储块长度为n，在该系统所采用的调度算法下较长时间内无法选出一道长度不超过该块的进程，则称该块为外部碎片。5.2.3动态分区分配5.2连续分配存储管理方式

实现动态分区(可变分区)分配时，须解决的问题一、分区分配中的数据结构二、分区分配算法三、分区分配、回收操作020OS程序18k程序232k2860程序4120k92程序332k212512程序6256k程序524k8446832k128k44k程序18k程序524k程序n206k程序730k程序848k程序m40k外部碎片外部碎片5.2.3动态分区分配一、分区分配中的数据结构1.空闲分区表

2.空闲分区链5.2.3动态分区分配二、分区分配算法1.首次适应算法FF。2.循环首次适应算法空闲分区链以地址递增的次序链接；进行内存分配时，从链首开始顺序查找。算法描述：缺点：低址不断划分，致使留下许多难以利用的、很小的空闲分区；每次从低址部分开始，增加查找可用空闲分区开销。空闲分区链以地址递增的次序链接；进行内存分配时，从上次找到的空闲分区的下一个空闲分区开始查找。算法描述：特点：减少查找开销，空闲分区分布的更均匀。但缺乏大的空闲分区。5.2.3动态分区分配二、分区分配算法3.最佳适应算法空闲分区由小到大形成空闲分区链，每次从链首找，找到的第一个，必然是最小的；算法描述：缺点：划分后剩余的空闲区最小；每次为作业分配内存时，总是把满足要求的、最小的空闲分区分配给作业。“最佳”含义：5.2.3动态分区分配二、分区分配算法例：某操作系统采用可变分区分配存储管理方法，用户区主存为512K，且始址为0，分配时截取空闲块的前半部分（小地址部分）。初始时用户区的512K空间空闲。在执行了如下操作序列后：申请300K，申请100K，释放300K，申请150K，申请30K，申请40K，申请60K，释放30K。1.采用首次适应算法，有哪些空闲块（指出大小及始址）。2.采用最佳适应算法，有哪些空闲块（指出大小及始址）。3.如再申请100K，针对1、2各有什么结果？说明了什么问题。5.2.3动态分区分配二、分区分配算法例：1.采用首次适应算法，空闲块有大小起始地址30K150K20K280K112K400K2.采用最佳适应算法，空闲块有大小起始地址30K400K42K470K90K210K3.如再申请100K，则首次适应算法可满足，而最佳适应算法不能满足，说明最佳适应算法并不总优于首次适应算法。三、分区分配、回收操作1.分配内存m.size：空闲区大小；u.size：请求大小；size：事先规定的不再切割的剩余分区的大小。5.2.3动态分区分配三、分区分配、回收操作2.回收内存A空闲释放分配B空闲释放分配空闲释放空闲C分配释放分配D当进程运行完毕释放内存时，系统根据回收区首址，从空闲分区链中找到相应的插入点。此时出现四种情况：5.2.4动态重定位分区分配5.2连续分配存储管理方式一、动态重定位的引入5.2.4动态重定位分区分配5.2连续分配存储管理方式二、动态重定位的实现动态运行时装入方式示意图实现:不需对程序作任何修改,“紧凑”时修改重定位寄存器内容，用程序在内存的新起始地址，去置换原来的起始地址即可。5.2.4动态重定位分区分配三、动态重定位分区分配算法

是址5.3分页存储管理方式引入：连续分配产生“碎片”，“紧凑”付出很大开销；离散分配：

将一个进程直接分散的分配到不相邻接的分区中(不必“紧凑”)。分类：分页存储管理方式分段存储管理方式段页式存储管理方式5.3.1分页存储管理的基本方法5.3.2地址变换机构5.3分页存储管理方式5.3.1

分页存储管理的基本方法一、页面和物理块将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页；页面：物理块：内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)；在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。页内碎片：进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”；分页存储管理的基本思想：示意图5.3分页存储管理方式二、地址结构5.3.1

分页存储管理的基本方法位移量W页号P3112110若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：5.3分页存储管理方式三、页表5.3.1

分页存储管理的基本方法页面映射表。记录了相应的页在内存中对应的物理块号，实现了从页号到物理块号的地址映射。示意图5.3分页存储管理方式0页1页2页3页4页...

n页用户进程3页0页

1页

2页

内存01234519021421931页号块号页表程序原封不动的装入内存中，采用动态重定位页表5.3.1

分页存储管理的基本方法基本思想5.3.1

分页存储管理的基本方法四、页面大小的选择2.页面的大小应选择得适中，通常在29至212之间，即512B至4KB之间。1.页面大小由机器的地址结构所决定,亦即由硬件决定;一种机器只能采用一种大小的页面。5.3分页存储管理方式5.3.2地址变换机构一、基本任务

实现逻辑地址到物理地址的转换，借助页表实现。----分页存储管理的动态重定位5.3分页存储管理方式5.3.2地址变换机构二、基本地址变换机构页表的功能可以由一组专门寄存器实现;---适用于较小系统页表大多驻留在内存中;概念：131924120

页号块号64页表始址页表长度页表项长度页表项地址=页表始址+页号*页表项长度5.3分页存储管理方式§6.3分页式存储管理CPU页表始址页表长度页号块号0417253348页表寄存器内存>越界中断+页号页内地址逻辑地址块号页内地址物理地址二、基本地址变换机构段页式存储5.3.2地址变换机构二、基本地址变换机构示意图存放当前运行进程的页表始址和页表长度，每个进程装入内存时，页表始址和页表长度先存放在本进程的PCB中，运行时才放入页表寄存器;----多道程序环境中，需一个页表寄存器页表寄存器页表在内存，CPU每存取一个数据,需两次访问内存,使计算机的处理速度降低近1/2。5.3分页存储管理方式5.3.2地址变换机构三、具有快表的地址变换机构1.引入基本地址变换机构中，页表在内存，CPU每存取一个数据,需两次访问内存，使计算机的处理速度降低近1/2。在地址变换机构中，增设具有并行查寻能力的特殊高速缓冲存储器，又称“联想存储器”或“快表”。快表中存放最近访问的页表项。5.3分页存储管理方式三、具有快表的地址变换机构2.地址变换过程5.3分页存储管理方式例题：设有一单纯分页系统，页的大小为1KB。假定一进程的代码段长度为10页，页表如表一所示，快表如表二所示：

页号物理块号08172431049::92页号物理块号081724310表一：表二：现进程有如下访问序列：其逻辑地址为：0AC5H、0EC3H、12C5H、62C3H。试问给定的这些地址能否进行转换？若能，请说明转换过程及相应的物理地址；若不能，则说明理由。5.3分页存储管理方式答案：页面大小为1KB，页内位移为10位，逻辑地址为十六进制，转换为二进制，右边10位即为页内位移d，其余左边高位为页号P。OAC5H=0000101011000101Bp=2，d=02C5H，查快表，得物理地址(4)2C5H0EC3H=0000111011000011Bp=3，d=02C3H，查快表，得物理地址(A)2C3H12C5H=0001001011000101Bp=4，d=02C5H，该页号不在快表，需到主存页表项中寻找对应物理块号，得内存物理块号P=9，d=02C5H，得物理地址(9)2C5H62C3H=0110001011000011Bp=24，d=02C3H，页号超出页表范围，不可转换，作为越界处理。5.4分段存储管理5.4.1分段存储管理方式的引入5.4.2分段系统的基本原理5.4.3段页式存储管理方式5.4.1分段存储管理方式的引入5.4分段存储管理引入分段存储管理方式，主要是为了满足用户和程序员的下述一系列需要：方便编程信息共享信息保护动态增长动态链接5.4.2分段系统的基本原理5.4分段存储管理一、分段作业的地址空间被划分成若干个段，离散的分配在内存中不相邻接的分区中；每个段有自己的名字，都从0开始编址，定义了一组逻辑信息；放在连续的存储区域上；由于每个段的长度可以不同，因而每个段的内存分配和回收类似于动态分区的分配和回收办法。会产生外部碎片。示意图5.4分段存储管理二、地址结构段内地址段号3116150分段的地址空间是二维的。5.4.2分段系统的基本原理三、段表5.4分段存储管理示意图每个段表项必须给出相应的段在主存中的起始地址和段的长度，实现由逻辑地址到物理地址的映射，并确保不会使用无效地址。地址变换机构5.4.2分段系统的基本原理图4-16利用段表实现地址映射分段段表5.4.2分段系统的基本原理四、地址变换机构5.4分段存储管理四、地址变换机构段表的功能可以由一组专门寄存器实现;---适用于较小系统段表大多驻留在内存中;存放当前运行进程的段表始址和段表长度;段表寄存器段表在内存，CPU每存取一个数据,需两次访问内存,使计算机的处理速度降低近1/2。在地址变换机构中，增设“快表”,存放最近访问的段表项---具有快表的地址变换机构。5.4.2分段系统的基本原理5.4分段存储管理五、分页和分段的主要区别1.