主要是指动态分区分配时所采用的几种算法。 动态分区分配又称为可变分区分配,是一种动态划分内存的分区方法。这种分区方法不预先将内存划分,而是在进程装入内存时,根据进程的大小动态地建立分区,并使分区的大小正好适合进程的需要。因此系统中分区的大小和数目是可变的。
首次适应(First Fit)算法: 空闲分区以地址递增的次序链接。分配内存时顺序查找,找到大小能满足要求的第一个空闲分区。
最佳适应(Best Fit)算法: 空闲分区按容量递增形成分区链,找到第一个能满足要求的空闲分区。
最坏适应(Worst Fit)算法: 又称最大适应(Largest Fit)算法,空闲分区以容量递减的次序链接。找到第一个能满足要求的空闲分区,也就是挑选出最大的分区。
把主存空间划分为大小相等且固定的块,块相对较小,作为主存的基本单位。每个进程也以块为单位进行划分,进程在执行时,以块为单位逐个申请主存中的块空间。
因为程序数据存储在不同的页面中,而页面又离散的分布在内存中,因此需要一个页表来记录逻辑地址和实际存储地址之间的映射关系,以实现从页号到物理块号的映射。
由于页表也是存储在内存中的,因此和不适用分页管理的存储方式相比,访问分页系统中内存数据需要两次的内存访问(一次是从内存中访问页表,从中找到指定的物理块号,加上页内偏移得到实际物理地址;第二次就是根据第一次得到的物理地址访问内存取出数据)。
为了减少两次访问内存导致的效率影响,分页管理中引入了快表机制,包含快表机制的内存管理中,当要访问内存数据的时候,首先将页号在快表中查询,如果查找到说明要访问的页表项在快表中,那么直接从快表中读取相应的物理块号;如果没有找到,那么访问内存中的页表,从页表中得到物理地址,同时将页表中的该映射表项添加到快表中(可能存在快表换出算法)。
在某些计算机中如果内存的逻辑地址很大,将会导致程序的页表项会很多,而页表在内存中是连续存放的,所以相应的就需要较大的连续内存空间。为了解决这个问题,可以采用两级页表或者多级页表的方法,其中外层页表一次性调入内存且连续存放,内层页表离散存放。相应的访问内存页表的时候需要一次地址变换,访问逻辑地址对应的物理地址的时候也需要一次地址变换,而且一共需要访问内存3次才可以读取一次数据。
分页是为了提高内存利用率,而分段是为了满足程序员在编写代码的时候的一些逻辑需求(比如数据共享,数据保护,动态链接等)。
分段内存管理当中,地址是二维的,一维是段号,一维是段内地址;其中每个段的长度是不一样的,而且每个段内部都是从0开始编址的。由于分段管理中,每个段内部是连续内存分配,但是段和段之间是离散分配的,因此也存在一个逻辑地址到物理地址的映射关系,相应的就是段表机制。段表中的每一个表项记录了该段在内存中的起始地址和该段的长度。段表可以放在内存中也可以放在寄存器中。
访问内存的时候根据段号和段表项的长度计算当前访问段在段表中的位置,然后访问段表,得到该段的物理地址,根据该物理地址以及段内偏移量就可以得到需要访问的内存。由于也是两次内存访问,所以分段管理中同样引入了联想寄存器。
页是信息的物理单位,是出于系统内存利用率的角度提出的离散分配机制;段是信息的逻辑单位,每个段含有一组意义完整的信息,是出于用户角度提出的内存管理机制
页的大小是固定的,由系统决定;段的大小是不确定的,由用户决定
如果存在一个程序,所需内存空间超过了计算机可以提供的实际内存,那么由于该程序无法装入内存所以也就无法运行。单纯的增加物理内存只能解决一部分问题,但是仍然会出现无法装入单个或者无法同时装入多个程序的问题。但是可以从逻辑的角度扩充内存容量,即可解决上述两种问题。
基于局部性原理,在程序装入时,可以将程序的一部分装入内存,而将其余部分留在外存,就可以启动程序执行。在程序执行过程中,当所访问的信息不在内存时,由操作系统将所需要的部分调入内存,然后继续执行程序。另一方面,操作系统将内存中暂时不使用的内容换出到外存上,从而腾出空间存放将要调入内存的信息。这样,系统好像为用户提供了一个比实际内存大得多的存储器,称为虚拟存储器。
虚拟存储器的特征:
- 多次性:一个作业可以分多次被调入内存。多次性是虚拟存储特有的属性
- 对换性:作业运行过程中存在换进换出的过程(换出暂时不用的数据换入需要的数据)
- 虚拟性:虚拟性体现在其从逻辑上扩充了内存的容量(可以运行实际内存需求比物理内存大的应用程序)。虚拟性是虚拟存储器的最重要特征也是其最终目标。虚拟性建立在多次性和对换性的基础上行,多次性和对换性又建立在离散分配的基础上。
最佳置换算法: 只具有理论意义的算法,用来评价其他页面置换算法。置换策略是将当前页面中在未来最长时间内不会被访问的页置换出去。
先进先出置换算法: 简单粗暴的一种置换算法,没有考虑页面访问频率信息。每次淘汰最早调入的页面。
最近最久未使用算法LRU: 算法赋予每个页面一个访问字段,用来记录上次页面被访问到现在所经历的时间t,每次置换的时候把t值最大的页面置换出去(实现方面可以采用寄存器或者栈的方式实现)。
时钟算法clock(也被称为是最近未使用算法NRU): 页面设置一个访问位,并将页面链接为一个环形队列,页面被访问的时候访问位设置为1。页面置换的时候,如果当前指针所指页面访问为为0,那么置换,否则将其置为0,循环直到遇到一个访问为位0的页面。
改进型Clock算法: 在Clock算法的基础上添加一个修改位,替换时根究访问位和修改位综合判断。优先替换访问位和修改位都是0的页面,其次是访问位为0修改位为1的页面。
最少使用算法LFU: 设置寄存器记录页面被访问次数,每次置换的时候置换当前访问次数最少的。