522固定分区分配FixedPartitionAllocation

最早的一种可运行多道程序的存储管理方式。它将内存空间划分为若干个固定大小的区域，在每个分区中可以装入一道作业。一.划分分区的方法1.分区大小相等所有的内存分区都大小相等，其缺点是明显的:(空间浪费或者使大程序无法运行)。2.分区大小不等为了克服分区大小相等分配方法的缺点，可在内存中划分出多个较小的分区、适量的中等分区及少量的大分区。二、内存分配（见图5-6）通常将这些分区根据其大小进行排队,并为之建立一张分区使用表。5.2.2固定分区分配

FixedPartitionAllocation分区号大小(kb)始址(k)状态1234153050100304575125已分配已分配已分配已分配操作系统作业A作业B作业C

030k45k75k125k225kA:B:C=15:30:50图5--6固定分区使用表(a)分区说明表;(b)存储空间分配情况（a）（b）5.2.3动态分区分配

DynamicPartitionAllocation动态分区分配是根据进程的实际需要，动态地为之分配连续的内存空间。在实现可变分区存储管理方式时，必须解决下述三个问题：（1）分区分配中所用的数据结构（2）分区的分配算法（3）分区分配操作一、分区分配中的数据结构常用的数据结构有两种：1.空闲分区表2.空闲分区链序号1分区大小(kb)分区始址(k)状态12346424403044132210270可用可用可用可用5图5--7空闲分区说明表N个字节可用前向指针N+20后向指针N+20图5--8空闲链结构二.分区分配算法

PartitionAllocationAlgorithm（1）首次适应策略（First-FitStrategy）

分配主存中第一次遇到的适合该作业要求的空闲空间。(要求空闲分区链以地址递增的次序链接)

特点:倾向于使用低地址部分,从而保留了高地址部分的大的空闲区;但,低地址部分的分区数量增多,从而增加了查找空闲区的开销。（2）循环首次适应策略（CyclicFirst-fitstrategy）

查找空闲区从上次找到的空闲区的下一空闲区开始，并循环查找。（需要设置一起始查找指针。）

特点：空闲区分布均匀，从而减少了查找的开销；但会缺乏大的空闲区。（3）最佳适配策略（Best-fitstrategy）

从空闲区中挑选一个能满足作业要求的最小分区。（空闲区以其空间大小递增顺序形成空闲区链）（缺点：更容易形成碎片）（4）最坏适应策略（Worst-fitstrategy）

该策略分配满足作业要求的最大一块空闲空间。三、分区分配操作

PartitionAllocationOperation1、分配内存(MemoryAllocation)u.size:请求的分区大小；

m.size:表中每个空闲分区的大小；

size:事先规定的不再切割的剩余分区的大小。内存分配流程（见图5-9）从头开始查表检查完否?M.size>u.size?M.size-u.size<size?从该分区中划出U.size大小的分区将该分区分配给请求者修改有关数据结构返回将该分区从链中移走继续检索下一个表项返回图5-9内存分配流程NYYYNN三、分区分配操作

PartitionAllocationOperation2、回收操作(ReturnOperation)当内存运行完毕释放内存时，系统根据回收区的首址，从空闲链中找到相应的插入点，此时可能出现四种情况之一：（1）回收区与插入点的前一个分区相邻接。（2）回收区与插入点的后一个分区相邻接。（3）回收区与插入点的前、后两个分区相邻接。（4）回收区不与插入点的前、后两个分区相邻接。F2

回收区F2

回收区F1F1

回收区(a)(b)(c)图5--10内存回收时的情况顺序地检索可用资源表直至找到某表目的m.addr>aa或m.size=0不是第一个表目且与前一可用区相邻?所释放可用区的size=0?与后一可用分区相邻且不为空表目?与后一可用区相邻?所释放的可用区与后一可用区合并将该表目以上的所有表目上移一格,并插入、新释放的可用区表目把所释放的可用区与前一分区合并与后一可用区合并将该表目以上的所有表目；下移一格返回是否是否是否mfree图5--11内存回收流程Y操作系统用户程序1用户程序610KB用户程序330KB操作系统26KB用户程序914KB用户程序1用户程序9用户程序3用户程序680KB(a)(b)图5--12紧凑的示意(a)紧凑前;(b)紧凑后5.2.4动态重定位分区分配一、紧凑(Compact)二、动态重定位

DynamicRelocationLOAD1,2500365250010000365LOAD1,2500+处理机一侧存储器一侧图5--13动态重定位示意01002500500010000101001250015000主存作业J相对地址重定位寄存器修改有关的数据结构检索空闲分区链(表)进行紧凑形成连续空闲区修改有关的数据结构按动态分区方式进行分配找到大于u.size的可用区否?空闲分区总和>u.size?返回分区号及首址无法分配返回请求分配u.size分区否否是图5--14动态分区分配算法流程三、动态重定位分区分配算法DynamicRelocationPartitionAllocationAlgorithm

5.2.5

IBM-PC微机中的存储管理方式

MemoryManagementinIBM-PC一.段寄存器和作业的分段

在IBM-PC微机中，采用了多重定位的存储器管理方式。在PC机中共设置了四个段寄存器：代码段寄存器CS(CodeSegment)；数据段寄存器DS(DataSegment)；栈段寄存器SS(StackSegment)；附加段寄存器ES(ExpandedSegment)。相应地，在PC机中运行的作业也可分成四个段：即代码段，数据段，供程序使用的栈段，以及作为用户工作区的附加段。这几个段的地址空间可以邻接；也可部分或全部重叠。因此，一个作业的最大地址空间可为256KB，每一个段可以存放在内存用户区的任何位置，如图5-15所示。附加段栈段数据段代码段SSESCSDS段寄存器图5--15段寄存器与作业的分段5.2.5

IBM-PC微机中的存储管理方式

MemoryManagementinIBM-PC二、形成访问内存物理地址

Intel8086芯片具有访问20位地址总线，能直接访问1MB的内存空间；而8086中所有的寄存器都是16位的，其寻址能力只达64KB。为了利用16位的寄存器来形成访问内存所需的20位物理地址，可用下述方法：每当需要产生一个20位的物理地址时，会自动地选择一有关段寄存器，先将它的内容左移4位，然后与一个16位的地址偏移量（即段内相对地址）相加，其结果便是所需要的20位的访问内存的物理地址。即：(段寄存器)左移4位+段内偏移量>物理地址三、多重定位的实现在Intel8086处理器的四个段寄存器中，其每一个作用与前面所介绍的重定位寄存器相似，可用来实现动态重定位。5.3对换(Swapping,交换）

对换技术，最早用在MIT的兼容分时系统CTSS中。该系统是单用户系统，在内存中仅驻留一道用户作业。所有其它作业都驻留在外存的后备队列上，每次只调入一个作业进入内存运行；此作业的时间片用完时，又将该作业调至外存，再将后备队列上的另一个作业调入内存；也让它运行一个时间片的时间，然后又将它调出，再调下一个作业进入内存。这就是早期的交换技术，此时引入交换技术的目的，是为了解决由于内存不足而无法同时容纳多达数十甚至数百个用户程序，以参加运行的问题。但这种最初的交换技术已很少再用，因为其效率太低，其CPU大约有一半的时间，都处于空闲状态，以等待前一作业的调出和后一作业的调入。5.3.1多道程序环境下的对换

SwappinginMulti-programmingEnvironment

多道程序环境下的资源浪费，导致系统吞吐量下降。所谓“对换”，是指把内存中暂不能运行的进程，或暂时不用的程序和数据，换出到外存上，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需的程序和数据，换入内存。对换是提高内存利用率的有效措施。在UNIX和WindowsOS都引入了对换功能。换入、换出是由系统的对换进程来完成的。对换的分类：整体对换或进程对换；部分对换或页面对换（分段对换）。（虚拟存储的基础。）5.3.2对换空间的管理

ManagementofSwappingSpace在具有对换功能的OS中，通常把外存分为文件区和对换区。前者用于存放文件，由于通常的文件都是较长久地驻留在外存上，故对文件区管理的主要目标，是提高文件存储空间的利用率。为此，系统采用离散分配方式。后者则用于存放从内存换出的进程，由于这些进程在对换区中驻留的时间是短暂的，而对换操作又较频繁，故对对换空间管理的主要目标，则是提高进程的换入、换出速度，为此，所应采取的管理策略是用连续分配方式，较少考虑外存中的碎片问题。对对换区中的空闲盘块，可采用空闲区表或空闲区链进行管理。对对换区空间的分配与回收，与动态分区方式时的内存的分配与回收方法雷同。5.3.3进程的换入与换出

SwapinandSwapoutofProcess一、进程的换出在进程换出时，是将内存中的某些进程调至对换区，以腾出内存空间，换出过程分以下两步：1.选出被换出的进程选择标准：进程状态、优先级、在内存的驻留时间2.换出过程非共享的程序和数据段的换出；共享的程序和数据段的换出。二、进程的换入当对换进程去执行换入操作时，便去检查PCB集合中所有进程的状态，从中找出“就绪且换出”状态的进程。5.4分页存储管理方式

PagedMemoryManagement连续分配方式会形成许多“碎片(fragmentation)”，虽然可通过“紧凑”方法将碎片拼接成可用的大块空间，但须为此付出很大开销。如果允许将一个进程直接分散地分配到许多不相邻接的分区中，就不必再进行“紧凑”。基于这一思想而产生了离散分配方式。根据离散分配时所用基本单位的不同，又可分为三种：1.分页存储管理(Pagedmemorymanagement)2.分段存储管理(Segmentedmemorymanagement)3.段页式存储管理(Segmentdmemorymanagement)02213438690页1页2页3页4页N页5页5图5-16页表的作用012345678910用户程序页表页号块号内存5.4.1分页存储管理的基本方法

Basicmethodsofpagedmemorymanagement

一、页面和块

PageandBlock把一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页(Page)。相应地，内存空间也分成页相同大小的若干个存储块，或称为物理块(Block)或页框(frame)。在为进程分配内存时，以块为单位将进程中的若干页分别装入多个可以不相邻接的块中。由于进程的最后一页经常装不满一块，而形成不可利用的碎片--“页内碎片”。分页存储管理方式中的地址结构：其中：P=INT[A/L],d=[A]MODL，这里A是逻辑地址，L是页面大小，INT是整除函数，MOD是取余函数。例如L=1KB，A=2170B，则P=2，d=122。页号P位移量d二、页表PageTable在分页系统中，允许将进程的每一页离散地存储在内存的任一物理块中，但系统应能保证进程的正确运行，即能在内存中找到每个页面所对应的物理块。为此，系统又为每个进程建立一张页面映射表(PageMappingTable)，简称页表。页表的作用是实现从页号到物理块号的地址映射。即使在简单的分页系统中，也常在页表的表项中设置一存取控制字段，用于对该存储块中的内容进行保护。控制字段的格式：1bit：readonly/readandwrite；2bit：read/write、readonly、executeonlyetc。计算机类型页面字节数IBMAS/400VAX系列NS32032Intel80386Motorola6803051251251240964096三、页面大小的选择

SelectionofPageSize在分页系统中页面的大小是由机器的地址结构所决定的，亦即由硬件决定。对于某一种机器只能采用一种大小的页面。例如，IBMAS/400的页面大小为512B。页面小，则内存碎片小，内存利用高；但每个进程的页面多，页表长，占内存，页面换入换出的效率低。页面大，则页表短，提高换入换出效率，但碎片又大。因此，页面的大小应选择的适中，一般在512B~4KB之间。目前常见的几种计算机中所选用的页面大小如下表所示：5.4.2

地址变换机构

AddressTransformMechanism为了能将用户用户地址空间中的逻辑地址，变换为内存空间中的物理地址，在系统中须设置地址变换机构。其基本任务是实现从LA到PA的转换。由于页内地址和物理地址是一一对应的，例如，对于大小是1KB的页内地址是0~1023，其相应的物理块内的地址也是从0~1023，无须再进行变换。地址变换机构的任务，实际上只是将逻辑地址中的页号，转换为内存中的物理块号。又因为页面映射表的作用就是用于实现从页号到物理块号的变换，因此，地址变换的任务是借助于页表来完成的。页表始址1页表长度页内地址页号(3)b物理地址逻辑地址L页表寄存器PTR页表+>越界中断块号页号0123图5--17分页系统的地址变换机构一、基本的地址变换机构

BasicAddressTransformMechanism二、具有快表的地址变换机构

AddressTransformMechanismwithFast-table使用上述方式进行地址变换，使CPU每次要存取一个数据时，都要两次访问内存。第一次是查页表，找块号，形成物理地址；第二次访问内存时，才从第一步所得地址中获得所需数据（或向此地址中写入数据）。因此，将使计算机的处理速度降低近1/2。可见，以此高昂代价来换取存储空间利用率的提高，实属得不偿失。为了提高地址变换速度，可在地址变换机构中，增设一个具有并行查询能力的特殊高速缓冲存储器(Cache)，又称为“联想存储器”(AssociativeMemory)或“快表”，用以存放当前访问的那些页表项。图5-18示出了具有快表的地址变换机构。页表始址

页表长度页内地址页号b

db物理地址逻辑地址L页表寄存器页表+>越界中断块号页号图5--18具有