522固定分区分配FixedPartitionAllocation市公开课一等奖省赛课获奖课件

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

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

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

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

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

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

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

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

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

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

该策略分配满足作业要求最大一块空闲空间。522固定分区分配FixedPartitionAllocation第5页三、分区分配操作

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

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

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

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

回收区F2

回收区F1F1

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

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

522固定分区分配FixedPartitionAllocation第13页5.2.5

IBM-PC微机中存放管理方式

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

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

IBM-PC微机中存放管理方式

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

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

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

SwappinginMulti-programmingEnvironment

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

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

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

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

Basicmethodsofpagedmemorymanagement

522固定分区分配FixedPartitionAllocation第22页一、页面和块

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

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

地址变换机构

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

BasicAddressTransformMechanism522固定分区分配FixedPartitionAllocation第27页二、含有快表地址变换机构

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

页表长度页内地址页号b

db物理地址逻辑地址L页表存放器页表+>越界中止块号页号图5--18含有快表地