1、连续分配方式

　　连续分配方式：为用户程序分配一个连续的内存空间。

　　连续分配有4种方式，分别为单一连续分配、固定分区分配、动态分区分配及动态重定位分配。

1.1、单一连续分配

　　作用与单用户、单任务操作系统。

　　内存被分为系统区和用户区，系统区供OS使用，通常放在内存低址部分；用户区指除系统区外的全部内存空间，供用户使用。

　　优点：实现简单；无外碎片；不一定需要内存保护

　　缺点：只能用于单用户、单任务OS；有内碎片；存储器利用率低。

1.2、固定分区分配

　　固定分区分配将内存用户空间划分若干个固定大小的区域，在每个分区中只装入一道作业，将用户空间划分为几个分区，就有几道作业可以并发运行。一旦有空闲分区，便可以从外存的后备作业队列中选择一个适当大小的作业装入该分区。

1、划分分区的方法

1.1、分区大小相等

　　所有分区内存大小相等。

　　缺乏灵活性，程序太小会造成空间浪费；程序太大，分区无法装入，程序无法运行。

1.2、分区大小不等

　　为解决分区大小相等的缺陷，内存划分有小分区，中等分区及大分区。

2、内存分配

　　为便于内存分配，为分区建立一张分区使用表。表项包括每个分区的起始地址、大小及是否已分配状态。

　　当有一用户程序要装入时，由内存分配程序检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为"已分配"；若未找到大小足够的分区，则拒绝为该用户程序分配内存。

分区说明表如下：

存储空间分配情况：

1.3、动态分区分配

1、如何记录内存使用情况

　　系统中配置了相应的数据结构来描述空闲分区和已经分配分区。

1.1、空闲分区表

　　在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。

1.2、空闲分区链

　　为给个分区的起始部分，设置控制分区分配的信息，以及用于连接各分区所用的前向指针，在分区尾部则设置后向指针，通过前、后向链接指针，将所有的空闲分区链接成一个双向链。已分配出去的分区，状态位由"0"改为"1"。

2、选择哪个分区给新进程

　　把一个新作业转入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。

2.1、首次适应算法(first fit)

　　以空闲分区链为例，FF算法要求空闲分区链以地址递增的次序链接，在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。

　　该算法优先利用内存中低址部分的空闲分区，保留高址部分的大空闲区，为大作业分配大的内存空间创建了条件。

　　低址部分不断被划分，会留下难以利用的小空闲分区。

2.2、循环首次适应算法

　　该算法由首次适应算法演变而成的，为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直到找到能满足要求的空闲分区。

　　实现该算法，需设置一起始查询指针，用于指示下一次起始查询的空闲分区。

　　该算法能使内存中的空闲分区分布得更均匀，减少查询空闲分区时的开销。

2.3、最佳适应算法

　　所有空闲分区按其容量以从小到大的顺序形成一空闲分区链。

2.4、最坏适应算法

　　最坏适应分配算法要扫描整个空闲分区表或链表，总是挑选一个最大的空闲区分割给作业使用。

　　可使剩下的空闲区不至于太小，对小作业有利；存储器会缺乏大的空闲分区。

2.5、快速适应算法

　　快速适应算法又被称为分类搜索算法，将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，系统中存在多个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该空闲分区链表表头的指针。

　　该算法查找效率高，仅需要根据进程长度，寻找到能容纳它的最小空闲区链表，并取下第一块进行分配即可。

　　该算法在分区归还主存时，算法复杂，系统开销大。分配空闲分区时，以进程为单位，一个分区只属于一个进程。

3、已使用的分区如何回收

　　当程序运行完毕释放内存时，系统根据回收区的首址，从空闲区链中找到相应的插入点。

　　回收区与相邻空闲区要合并，并更新空闲分区表或空闲分区链。

1.4、动态重定位分配

1、动态重定位

　　当无足够大的空闲区装入程序时，可将内存中的所有作业进行移动，使它们全部相邻接，将原来分散的多个小分区拼接成一个大分区，将作业装入该区。

　　将多个分散的小分区拼接成大分区的方法，称为拼接。

　　每次拼接后，都必须对程序或数据进行重定位。

2、动态重定位的实现

　　动态运行时装入，作业转入内存后所有地址都是相对地址，相对地址转换为物理地址的工作，推迟到程序指令真正执行时进行。

　　为使地址的转换不会影响到指令的执行速度，须在系统中增设一个重定位寄存器，用来存放程序(数据)在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中地址相加而形成的。

　　动态重定位的实现原理如下：

　　地址变换过程是在程序执行期间，随着对每条指令或数据的访问自动进行的，因此成为动态重定位。

3、动态重定位的分配算法

　　动态重定位的分配算法与动态分区分配算法基本一致，差别在于：动态重定位算法，增加了拼接功能。

　　动态分配算法流程图：

1.5、对换

　　在多道程序环境下，内存中的某些进程由于某事件尚未发生而被阻塞运行，但该进程占用了大量的内存空间，甚至可能出现在内存中给所有进程都被阻塞而迫使CPU停止下来等待的情况，使系统吞吐量下降，为解决这一问题，引入了对换。

1、对换

　　把内存中在暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存。

对换被应用于分时系统中，目的是迎来解决内存紧张问题，并可进一步提高内存的利用率。

　　若对换以进程为单位，被称为整体对换或进程对换；

　　若对换以页或段为单位，则分别称为页面对换或分段对换，统称为部分对换。这种对换方式，是为了支持虚拟存储系统。

　　系统需事先对换空间管理、进程的换出及进程的换入三方面的功能。

2、进程对换

2.1、对换空间管理

　　在对换功能的OS总，外存分为文件区和对换区。文件区用来存放文件，对换区用来存放从内存中换出的进程。

　　因文件是较长久地驻留在外存上，对文件区管理的主要目标是提高存储空间的利用率。对文件区采取离散分配方式。

　　进程在对换区中驻留的时间短暂，对换操作频繁，对换空间管理的主要目标是提高进程换入和换出的速度。对换区采取的是连续分配方式。

　　OS以空闲分区表或空闲分区链对对换区中的空闲盘块进行管理。

　　对换分区的分配是采用连续分配方式，所以对换空间的分配与回收与动态分区方式的内存分配和回收类似。

2.2、进程的换入与换出

2.2.1、进程的换出

　　当进程由于创建子进程需要更多的内存空间，但无足够的内存空间时，系统应将某进程换出。

过程如下：

　　OS首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动磁盘，将该进程的程序和数据传送到磁盘的对换区上，回收该进程占用的内存空间，并对该进程的进程控制块做相应的修改。

2.2.2、进程的换入

　　系统定时地查看所有进程的状态，从中找出"就绪"状态但已换出的进程，将其中换出时间最久(换出到磁盘上)的进程作为换入进程，将之换入，直至无可换入的进程或无可换出的进程为止。

2、基本分页存储管理方式

　　基本份额存储管理，采用离散分配方式，离散分配的基本单位是页，将一个进程直接分散地装入到许多不相邻接的分区中。

2.1、页面与页表

1、页面

1.1、页面与物理块

　　分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号。

　　把内存空间分成与页面相同大小的若干个存储块，称为块或页框，为它们加以编号。

　　为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为"页内碎片"，即内碎片。

1.2、页面大小

　　页面大小是2的幂，通常为512B ~ 8KB。

1.3、地址结构

　　分页地址包含两部分，前一部分为页号P，后一部分为位移量W(页内地址)。

　　0 - 11 位为页面地址，每页大小为4KB；

　　12 -31 位为页号，地址空间最多允许有1M页。

2、页表

　　分页系统，允许将进程的各个页离散地存储在内存不同的物理块，为保证系统能在内存中找到每个页面所对应的物理块，系统为每个进程建立一张页面映像表，简称页面。

　　页表的作用是实现页号到物理块号的地址映射。

2.2、地址变换机构

　　地址变换机制的作用：将用户地址空间中的逻辑地址变换为内存空间中的物理地址。

　　该机构的基本你任务是实现从逻辑地址到物理地址的转换。

　　地址变换任务基于页表来完成，因为页内地址和物理地址一一对应，地址变换机构的任务实际上是将逻辑地址中的页号转换为内存中的物理块号，页面映射表实现页号到物理块号的映射。

1、基本的地址变换机构

1.1、概念

　　页表大多驻留在内存中，系统中设置一个页表寄存器(PTR Page-Table Register)，在其中存放页表在内存的始址和页表的长度。

　　进程未执行时，页表的始址和长度存放在本进程的PCB中，当调度到某进程时。才将者两个数据装入页表寄存器。

1.2、地址变换过程

　　进程访问某个逻辑地址中的数据时，逻辑地址到物理地址的变换过程：

　　1、分页地址变换机构自动将逻辑地址分为页号和页内地址两部分，再以页号作为索引去检索页表；

　　2、执行检索之前，先将页号与页表长度做比较，页号大于等于页表长度，表示本次所访问的地址已超越进程的地址空间，产生越界中断；若未出现越界错误，将页表始址和页号相加，获得该表项在页表中的位置，从页表中找到物理块号，装入物理地址寄存器中。

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

2.1、快表的引入

　　基本地址变换机构，页表存放在内存中，CUP每存取一个数据，要两次访问内存，第一次访问内存中的页表，找到指定页的物理块，再将快好与业内偏移量W拼接，形成物理地址；第二次访问内存时，从第一次得到的地址中获取数据。

　　为提高地址变换速度，在地址变换机构汇总增加一个高速缓冲寄存器，称为"快表"。

　　快表用来存放当前访问的页表项。

2.2、地址变换过程

　　在CPU给出逻辑地址后，由地址变换机构自动的将页号P送入高数缓冲寄存器，并将此页号与高速缓存中的所有页号进行比较：

　　若其中有与此项匹配的页号，表示要访问的页表项在块表中，直接从快表中读出该页对应的物理块号，并装入物理地址寄存器中；

　　在快表中未找到对应的页表项，需访问内存中页表，找到后，从页表项中读出物理块号送地址寄存器，同时，将此页表项存入快表的一个寄存器单元中，重新修改快表。

3、两级页表

　　现代计算机系统，支持非常大的逻辑地址空间，如此页表就变得非常大，占用极大的内存空间，且内存空间必须是连续的。

　　OS使用离散分配方式解决难以找到一块连续的大内存空间问题；

　　只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。

1、两级页表解决问题

　　两级页表主要解决要求连续空间存放页表的问题。

2、两级页表的实现

　　将页表进行分页，离散的将各个页面分别存放在不同的物理块中，同样的需要为离散分配的页表再建立一张页表，称为外层页表。在每个外层页表的页表项中记录页表页面的物理块号。

3、两级页表的逻辑地址结构

4、两级页表结构

　　地址变换机构中需要增设一个外层页表寄存器，用于存放外层页表的始址，并利用逻辑地址中的外层页号。作为外层页表的索引，从中找到指定页表分页的始址，再利用P2作为指定页表分页的索引，找到指定的页表项，其中及含有该页在内存的物理块号、用该块号和页内地址可构成访问的内存物理地址。

5、两级页表地址变换机构

　　对页表采用离散分配的方式，解决了大页表无需大片存储空间问题，并未减少页表所占用的存储空间。

　　要解决页表占用的存储空间，将当前需要的一批页表项调入内存，根据需要陆续调入。对正在运行的进程，在外层页表项中增设一个状态为，标识该页表是否调入内存中。

　　进程原型是，地址变换机构根据逻辑地址P1，查找外层页表，若找到页表项中的状态为0，则产生中断信号，请求OS将该页表分页调入内存。

3、基本分段存储管理方式

　　存储管理方式从固定分区 -> 动态分区 -> 分页存储管理，为了提高内存利用率。

3.1、分段存储管理方式引入

　　引入分段存储管理方式是为了满足用户在编程和使用上的要求。

1、信息共享、保护

　　实现对程序和数据共享时，以信息的逻辑单位为基础。页是存放信息的物理块，段是信息的逻辑单位。

　　信息保护同样是对信息的逻辑单位进行保护。

2、动态增长

3、动态链接

　　动态链接是以段为管理的单位。

　　动态链接是指在运行运行前，并不把目标程序段链接起来；运行时，先将主程序对应的目标程序转入内存并启动运行，当运行过程中需要调用某段是，才将该段调入内存并进行链接。

3.2、分段系统的基本原理

1、分段

　　在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。

分段地址的结构如下：

　　在该地址结构中，作业最长有64个段，每个段的最大长度为64KB。

2、段表

　　动态分区分配方式，系统为整个进程分配一个连续的内存空间。

　　分段式存储管理中，为每个分段分配一个连续的分区，而进程中的各个段可以离散地移入内存中不同的分区中。

　　为了能从物理内存中招呼从每个逻辑段对应的位置，为每个进程建立一张段映射表。简称"段表"。

　　每个段在表中占有一个表项，记录了段在内存中的起始地址和段的长度。

　　段表是用于实现从逻辑段到物理内存区的映射。

3、地址变换机构

　　系统设置段寄存器，用于存放段表始址和段表长度 TL。

　　进行地址变换时，系统将逻辑地址中的段号与段表长度TL进行比较，若 S > TL，表示段号太大，产生越界中断；若未越界，则根据段表的始址和段号，计算出该段对应段表项位置，从中读出该段在内存的起始地址，该段的基址和段内地址相加，得到要访问的内存物理地址。

4、分页与分段的异同

　　分页和分段都采用离散分配方式，都需要通过地址映射机构来实现地址变换。

4.1、页是信息的物理单位，段是信息的逻辑单位

　　分页是为了提高内存的利用率，仅是系统管理的需要；分段式为了能更好地满足用户的需要。

4.2、页大小固定，段大小不固定

　　页的大小固定，系统逻辑地址划分为页号和页内地址两部分。

　　段的长度不固定，取决于用户编写的程序。

4.3、分页的作业地址空间是一维的，分段的作业地址空间是二维的

　　分页的作业地址空间是单一的线性地址空间；分段的作业地址空间是二维的，在标识地址时，需要段名和段内地址。

3.3、段页式存储管理方式

　　分页系统能有效提高内存的利用率，分段系统能很好的满足用户需要，结合起来形成段页式系统。

1、基本原理

　　段页式系统的基本原理，是分页和分段原理的结合，先将用户程序分成若干段，再把每个段分成若干个页，并为每一个段赋予一个段名。

地址空间结构：

段页式系统中，地址结构由短号、段内页号及业内地址三部分组成。　　

2、地址变换过程

　　系统设置一个段表寄存器，存放段表始址和段表长TL。

　　进行地址变换时，先利用段号S，将它与段表长TL进行比较。若S < TL，表示未越界，利用段表始址和短号求出该段所定应段表项在段表中的位置，从中得到该段的页表地址，并利用逻辑地址中的段内页号P来获得对应页的页表项位置，从中得出该页所在的物理块号b，利用b和页内地址来构成物理地址。

4、虚拟内存存储器

4.1、虚拟储存技术解决的问题

　　当内存容量不够大时，从逻辑上扩充内存容量。

4.2、虚拟存储器的定义

　　虚拟存储器：具有请求调入和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。逻辑容量由内存容量和外存容量之和决定。

4.3、虚拟存储器的实现方法

　　在虚拟存储器中，允许将一个作业分多次调入内存，离散分配的存储管理方式是实现虚拟存储器的基础。

4.3.1、分页请求系统

　　分页系统增加了请求调页功能和页面置换功能锁形成的页式虚拟存储系统。

　　允许只转入少数页面的程序，便启动运行，之后通过调页及页面置换功能，陆续将要运行的页面调入内存，同时把暂不运行的页面换出到外存上。

置换以页面为单位

4.3.2、分段请求系统

　　分段系统增加了请求调页功能和页面置换功能锁形成的页式虚拟存储系统。

　　允许只转入少数页面的程序，便启动运行，之后通过调段及段置换功能将把暂不运行的段换出到外存上，同时调入即将运行的段。