操作系统(三):内存管理,分页地址映射,页面置换算法LRU,NRU,FIFO,第二次机会算法和时钟算法_操作系统lru页面置换算法求物理地址

---

一、虚拟内存

虚拟内存的目的是为了让无力内存扩充成更大的逻辑内存，从而让程序获得更多可用的内存。

为了更好管理内存，操作系统将内存抽象成地址空间。每一个程序拥有自己的地址空间，这个地址空间被分成多个页，并被映射到物理内存中（不需要连续），当程序引用到不在物理内存中的页的时候，由硬件执行必要的映射，并将缺失的部分装入物理内存中并重新执行之前失败的指令。

二、分页系统地址映射

内存管理单元MMU管理着地址空间和物理内存的转换，其中的页表存储着页（程序地址空间）和页框（物理内存空间）的映射表。

注意，一个虚拟地址分成两个部分，一部分存储页面号，一部分存储偏移量。

例如下图的页表存放着16个页，这16个页虚需要用4个比特位来进行索引定位。比如对于虚拟地址(0010 000000000100),前4位是存储页面号2，读取表项内容为(110 1), 页表项最后一位表示是否存在于内存中，1表示存在。后12位存储偏移量。这个页对应的页框地址为(110 000000000100)。

三、页面置换算法

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

页面置换算法的主要目的是让页面置换频率最低，即增加页表命中的概率。

最佳置换算法

所选择的被换出的页面将是最长时间内不被访问的，通常这样可以保证获得最低的缺页率。然而这只是一种理论上的算法，因为我们并不能知道一个页面具体多长事件不会被访问。

LRU 最近最久未使用算法

虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。

为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。

NRU 最近未使用

每隔页面增设两个状态位: R 和 M。当页面被访问的时候设置页面的R = 1， 当页面被修改的时候设置M = 1。 其中R会定时被清零，NRU算法优先换出已经被修改的脏页面（R = 0， M = 1）。

FIFO 先进先出

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

第二次机会算法

该算法主要是解决FIFO算法中可能会把经常使用的页面置换出去的问题，为了避免这一个问题，对FIFO算法做出一个简单的修改。

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

时钟算法

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

四、内存分段

虚拟内存采用的是分页技术，也就是将地址空间划分成固定大小的页，然而对于某些动态增长的程序来说，分页内存会导致覆盖问题。

内存分段就是把每一个表分成段，一个段构成一个独立的地址空间，每个段的长度可以不同并且可以动态增长。

五、段页式

程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。

六、分页和分段的比较

1. 对程序员的透明性不同： 分页透明，但是分段需要程序员手动划分每个段。
2. 地址空间的维度： 分页是一维空间，分段是二维。
3. 大小是否可变： 页的大小不可变，段的大小可变。
4. 出现原因： 分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护

---