使用链表管理内存时分配内存的算法

首次适配算法

存储管理器沿着段链表进行搜索，直到找到一个足够大的空闲区，除非空闲区大小和要分配的空间大小正好一样，否则将该空闲区分为两部分，一部分供进程使用，另一部分形成新的空闲区。

下次适配算法

工作方式和首次适配算法基本相同，不同点是每次找到合适的空闲区时都记录当时的位置，以便在下次寻找空闲区时从上次结束的地方开始搜索。

最佳适配算法

搜索整个链表，找到能够容纳进程的最小空闲区。

最差适配算法

总是分配最大的可用空闲区

虚拟内存

每个程序拥有自己的地址空间，这个空间被分割成若干个块，每块被称作一页或页面。每一页有连续的地址范围。这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时，由硬件立刻执行必要的映射。当程序引用到一部分不在物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。

由程序产生的地址叫虚拟地址，它们构成一个虚拟地址空间。在使用虚拟内存的情况下，虚拟地址不是被送到内存总线上，而是被送到mmu（内存管理单元），mmu将虚拟地址映射为物理内存地址。 内存管理单元管理着地址空间和物理内存的转换，其中的页表存储着页（程序地址空间）和页框（物理内存空间）的映射表。 一个虚拟地址分成两个部分，一部分存储页面号，一部分存储偏移量。

页面置换算法

在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。

最佳置换算法

置换最长时间内不被访问的页面。

最近未使用页面置换算法(NRU)

每个页面都会有两个状态位：R与M，当页面被访问时设置页面的 R=1,当页面被修改时设置M=1。其中R位会定时被清零。可以将页面分成以下四类：

当发生缺页中断时，NRU算法随机地从类编号最小的非空类中挑选一个页面将它们换出。 NRU优先换出已经被修改的脏页面（R=0,M=1），而不是被频繁使用的干净页面（R=1,M=0）

先进先出页面置换算法

选择换出的页面是最先进入的页面。

但是最先进入的页面也有可能经常被访问到，可能导致缺页率升高。

第二次机会页面置换算法

FIFO 算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改： 当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候，检查最老页面的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。

时钟页面置换算法

第二次机会算法需要在链表中移动页面，降低了效率。时钟算法使用环形链表将页面连接起来，再使用一个指针指向最老的页面。

首先检查表针指向的页面，如果它的R位是0就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置，如果R位是1就清除R位并把表针前移一个位置。

最近最少使用页面置换算法

虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。 为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。 因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。