虚拟内存在逻辑上实现了对内存容量的扩充&＃xff0c;既满足了用户的需要&＃xff0c;又改善了系统性能。这篇文章总结了虚拟内存的基本概念、实现方式以及几种页面置换算法。最后是几种文件分配方式。
基本概念
局部性原理&＃xff1a;程序执行时&＃xff0c;在一较短时间内&＃xff0c;程序的执行仅仅局限于某一部分&＃xff0c;其访问的存储空间也局限于某个区域。主要表现在两个方面&＃xff1a;
- 时间局限性&＃xff1a;如果某条指令被执行&＃xff0c;不久以后该指令可能再次执行&＃xff1b;如果某些数据被访问&＃xff0c;不久以后该数据可能再次被访问&＃xff1b;
- 空间局限性&＃xff1a;如果某段存储单元被访问&＃xff0c;其附近的存储单 元可能也会被访问。
基于局部性原理&＃xff0c;在加载程序时&＃xff0c;只需将当前执行所需的部分页面或段装入内存。程序执行时&＃xff0c;如果要访问的页面或段不在内存中&＃xff0c;则发生缺页中断&＃xff0c;于是 OS 利用请求调页功能将相应的页面或段调入内存&＃xff0c;继续执行。如果内存已满&＃xff0c;则利用置换功能&＃xff0c;将内存中暂时不用的页面或段调出到外存&＃xff0c;再将所需的页面或段调入内存&＃xff0c;使程序继续执行。
虚拟内存是指具有请求调入功能和置换功能&＃xff0c;从逻辑上对内存容量进行扩充的一种内存系统。实现方式有三种&＃xff1a;请求分页存储管理方式、请求段式存储管理方式和请求段页式存储管理方式。
请求分页存储管理
请求分页存储管理是在分页存储管理的基础上&＃xff0c;增加请求调页和页面置换功能。它允许用户程序只装入部分页面就启动程序运行。在运行中如果发现所需页面不在内存中&＃xff0c;则发出缺页中断&＃xff0c;OS 就会将外存中相应的页面调入内存使其继续运行。每次调入和换出的基本单位是长度固定的页面。
请求分页存储管理中的地址转换与分页式相比&＃xff0c;在页表项中添加了一些标志位&＃xff1a;
- 状态位&＃xff1a;表示该页是否已调入内存。
- 修改位&＃xff1a;表示该页在调入内存后是否被修改过。在置换该页时&＃xff0c;判断是否要把它写回外存。
- 访问位&＃xff1a;表示该页在一段时间内被访问的次数。供置换算法在选择换出页面时参考。
- 外存地址&＃xff1a;表示该页在外存上的地址。
请求分页存储管理系统中&＃xff0c;在进行地址转换时&＃xff0c;首先在快表中查找要访问的页。如果找到&＃xff0c;便修改页表项中的访问位&＃xff0c;供置换算法选择换出页面时参考。如果是写指令&＃xff0c;还需要将修改位置为 1&＃xff0c;表示该页在调入内存后被修改过。然后利用页表项中的物理块号和页内地址&＃xff0c;得到物理地址。
如果在快表中未找到该页的页表项&＃xff0c;则应到内存中去查找页表&＃xff0c;再从找到的页表项中的状态位来判断该页是否调入内存。如果该页已调入&＃xff0c;则应将该页的页表项写入快表&＃xff1b;如果该页没有调入内存&＃xff0c;则应该产生缺页中断&＃xff0c;操作系统从外存中找到缺失的页面。
如果内存已满&＃xff0c;则利用置换算法选择一页换出&＃xff0c;如果该页被修改过&＃xff0c;则需要将该页写回到外存中。最后将缺页从外存换入到内存中&＃xff0c;继续运行程序。
页面置换算法
最优算法&＃xff08;Optimal&＃xff09;
置换在未来最长时间内不再被访问的页面。这只是一种理想情况&＃xff0c;只能用来评价其他置换算法的性能。
先进先出算法&＃xff08;FIFO&＃xff09;
选择进入内存时间最长的页面进行置换。在实现时维护一个所有已调入内存的页面的链表&＃xff0c;按照进入内存的先后次序排序&＃xff0c;链首最早&＃xff0c;链尾最进。在出现缺页时&＃xff0c;选择链首的页面进行置换&＃xff0c;将新页面添加到链尾。
这种算法实现简单。但调出的页面可能会经常访问&＃xff0c;性能较差&＃xff0c;一般和其他算法结合使用。
最近最久未使用算法&＃xff08;LRU&＃xff09;
选择最长时间没有使用的页面进行置换。它依据的是如果某个页面长时间没有被访问&＃xff0c;则在将来一段时间可能还不会访问。
在实现时维护一个按最近一次访问时间排序的链表&＃xff0c;链表首是刚使用过的页面&＃xff0c;链表尾是最久未使用的页面。在访问页面时&＃xff0c;找到相应的页面&＃xff0c;将其移动到链表首&＃xff1b;在出现缺页时&＃xff0c;删除链表尾节点&＃xff0c;将新页面添加到链表首。
这种算法是最优算法的一种近似&＃xff0c;但实现起来仍然比较复杂。
时钟算法&＃xff08;Clock&＃xff09;
也称为最近未使用算法&＃xff08;NRU&＃xff09;。在实现时&＃xff0c;在页表项中增加一个访问位&＃xff0c;表示过去一段时间内是否被访问过&＃xff0c;初始时都置为 0&＃xff0c;另外将页面组织成环形链表&＃xff0c;添加一条指针指向最先被调入内存的页面。
当访问某页面时&＃xff0c;将其访问项置为 1。在出现缺页异常时&＃xff0c;从指针处开始查找&＃xff0c;如果页面没有被访问过&＃xff0c;即访问项为 0&＃xff0c;则进行置换&＃xff1b;如果被访问过&＃xff0c;则将访问项置为 0&＃xff0c;暂不换出&＃xff0c;再将指针指向下一个页面继续查找&＃xff0c;直到找到可以置换的页面。
最少使用算法&＃xff08;LFU&＃xff09;
置换最近一段时间访问次数最少的页面。在实现时&＃xff0c;对每个页面设置一个访问计数&＃xff0c;在访问页面时&＃xff0c;对访问计数加 1&＃xff1b;在出现缺页异常时&＃xff0c;置换访问计数最少的页面。
文件分配
文件分配实际上是如何表示分配给一个文件的数据块的位置和顺序。主要有以下几种分配方式&＃xff1a;连续分配、链式分配和索引分配。
连续分配
使用连续的若干个数据块来存储文件。它在文件控制块中记录起始第一个数据块的位置和长度。
采用连续分配方式&＃xff0c;读取文件的顺序访问和随机访问效率较高&＃xff0c;但是剩余的碎片难以利用&＃xff0c;另外文件长度增长也比较复杂。
链式分配
将文件以数据块链表的形式存储。文件控制块中包含了第一个数据块和最后一个数据块的指针。
链式分配方式在创建、增大、缩小文件时比较容易&＃xff0c;而且没有碎片&＃xff0c;但是不能实现真正的随机访问&＃xff0c;另外一个数据块被破坏&＃xff0c;后面的数据块就都丢了。
索引分配
为每个文件创建一个索引数据块&＃xff0c;索引数据块中存储了指向文件数据块的指针列表&＃xff0c;文件控制块中包含了指向索引数据块的指针。
这种实现在创建文件、增大、缩小文件时比较容易&＃xff0c;也没有碎片&＃xff0c;也支持随机访问。但是在文件很小时&＃xff0c;存储索引开销相对较大&＃xff0c;在文件很大时&＃xff0c;需要增加额外的索引快。
UFS&＃xff08;Unix File System&＃xff09;
UFS 的多级索引分配&＃xff1a;在文件控制块中&＃xff0c;如果数据块小于 10&＃xff0c;采用直接索引&＃xff1b;如果大于 10 块&＃xff0c;第 11 块开始采用一级间接索引&＃xff0c;它先指向一个索引块&＃xff0c;索引块中再指向实际的数据块。如果数据块大到一定程度&＃xff0c;会采用二级间接索引&＃xff0c;依次类推。
多级索引分配方式大大提高了文件大小的限制阈值&＃xff0c;可以动态分配数据块&＃xff0c;文件扩展很容易&＃xff0c;对于小文件开销较小&＃xff0c;对于大文件使用间接索引也比较合理。
京公网安备 11010802041100号