【408&预推免复习】操作系统之虚拟存储器

浅浅的花香味﹌ 2022-09-02 03:41 212阅读 0赞

【408&预推免复习】操作系统之虚拟存储器  
![在这里插入图片描述][resize_m_lfit_w_962_pic_center]

文章目录
    1 虚拟存储器概述
    2 请求分页存储管理方式
    3 页面置换算法
    	3.1 最佳(Optimal)置换算法
    	3.2 先进先出(FIFO)页面置换算法
    	3.3 最近最久未使用LRU(Least Recently Used)
    	3.4 最少使用(Least Frequently Used，LFU)置换算法
    	3.5 Clock置换算法
    4 “抖动”与工作集
    5 请求分段存储管理方式

# 1 虚拟存储器概述 #

局部性原理（理论基础）1968年P.Denning 提出，即在一较短时间内，程序的执行仅限于某个部分，且所访问的存储空间也局限于某个区域。

程序执行时，大多数情况下是顺序执行的。  
过程调用会使程序的执行轨迹从一部分内存区域转至另一部分区域， 但过程调用的深度不会超过5。  
程序中有许多循环语句，这些语句会重复多次执行。  
程序中对数据结构，如数组的操作，往往局限在很小的范围内。

时间局限性  
程序中的的某条指令被执行，不久后会可能再次被执行；如果某数据被访问过，不久以后该数据可能再次被访问。  
空间局限性  
程序一旦访问某存储单元，不久后会访问其附近的存储单元

虚拟存储器的定义  
**所谓虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。**  
其逻辑容量由内存和外存之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。

![在这里插入图片描述][d79768b65bbe43f78a596307f7923e2d.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]

# 2 请求分页存储管理方式 #

![在这里插入图片描述][a29db5d8c1714f039e29fb09efc70ac0.png_x-oss-process_imagetype_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][273a68c656ce49319403c0ead74eb8fe.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]  
缺页率：  
假设一个进程的逻辑空间为n页，系统为其分配的内存物理块数为m(m≤n)。如果在进程的运行过程中，访问页面成功(即所访问页面在内存中)的次数为S，访问页面失败(即所访问页面不在内存中，需要从外存调入)的次数为F，则该进程总的页面访问次数为A = S + F，那么该进程在其运行过程中的缺页率即为。

![在这里插入图片描述][70710ea1710a40b9887e8b7fa15b785f.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]

# 3 页面置换算法 #

## 3.1 最佳(Optimal)置换算法 ##

![在这里插入图片描述][a4c707ad1fd547a4951e2a4daea32f73.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]

## 3.2 先进先出(FIFO)页面置换算法 ##

![在这里插入图片描述][4286bb37c9a044ac8d1a41e8124a9884.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]

## 3.3 最近最久未使用LRU(Least Recently Used) ##

![在这里插入图片描述][4e1a255eb3f84513b3a16903f8149077.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][b3533031a1954c65af3d8bb0ceea0a7f.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]  
两种方法实现  
移位寄存器  
为某个进程在内存中的每个页面配置一个移位寄存器（R=Rn-1Rn-2Rn-3…R2R1R0）  
当进程访问某块时，将该块所对应的移位寄存器的最高位（Rn-1位）置成1。  
系统中的定时器每隔一定时间（例如10ms）将所有的移位寄存器右移1位。  
将每个寄存器看成一个整数，则淘汰时，具有最小整数的寄存器对应的页面就是最近最久未被使用的页面

栈  
用一个特殊的栈保存当前使用的各个页面的页面号，当进程访问某页时  
如果该页在栈内，则将该页从栈内弹出并压入栈顶  
如果该页不在栈内，则直接压入栈顶  
淘汰时，在栈底的页就是最近最久未使用的页

![在这里插入图片描述][c611e6aea24f43399be07ed4e79f4757.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]

## 3.4 最少使用(Least Frequently Used，LFU)置换算法 ##

思想：淘汰最近一段时间使用次数最少的页面。  
实现：  
为每个页面设置一个移位寄存器，用来记录页面的访问频率。  
每次访问某页，就将移位寄存器最高位置1，定期右移移位寄存器  
淘汰时，选择寄存器值 最小的页面

## 3.5 Clock置换算法 ##

![在这里插入图片描述][57d774f327ed422a9805204a25f5394b.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]  
改进型Clock置换算法  
在将一个页面换出时，如果该页已被修改过，便须将该页重新写回到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘。换而言之，对于修改过的页面，在换出时所付出的开销比未修改过的页面大，或者说，置换代价大。  
在改进型Clock算法中，除须考虑页面的使用情况外，还须再增加一个因素——置换代价。  
Clock算法将页面分类（A表示访问位，M表示修改位）  
A=0,M=0:既未访问，又未修改  
A=0,M=1:未访问但已修改  
A=1,M=0:已访问但未修改  
A=1,M=1:已访问且已修改

# 4 “抖动”与工作集 #

![在这里插入图片描述][1df85767dc5a41cb9aeb2c74e684c782.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]  
\*\*所谓工作集，是指在某段时间间隔Δ里，进程实际所要访问页面的集合。\*\*Denning指出，虽然程序只需要少量的几页在内存便可运行，但为了较少地产生缺页，应将程序的全部工作集装入内存中。然而我们无法事先预知程序在不同时刻将访问哪些页面，故仍只有像置换算法那样，用程序的过去某段时间内的行为作为程序在将来某段时间内行为的近似。

# 5 请求分段存储管理方式 #

请求分段存储管理方式是以分段为单位进行换入、换出  
程序在运行之前，只需先调入少数几个分段便可启动运行，当所访问的段不在内存中时，可请求OS将所缺的段调入内存

![在这里插入图片描述][e3779861d7a6421287f915e343621b4d.png_x-oss-process_imagetype_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]

[resize_m_lfit_w_962_pic_center]: /images/20220829/acb54547960d467bb6d4c5b28ac6b959.png
[d79768b65bbe43f78a596307f7923e2d.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/8d221ee8284d4ea080db0988fda8d876.png
[a29db5d8c1714f039e29fb09efc70ac0.png_x-oss-process_imagetype_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/b2b8cd601f4e4a5680d23cfcfb1c2f35.png
[273a68c656ce49319403c0ead74eb8fe.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/904136001f634d28bfa691e1bf4bd832.png
[70710ea1710a40b9887e8b7fa15b785f.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/289af06a33cd4546af3e7ff0d59b5324.png
[a4c707ad1fd547a4951e2a4daea32f73.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/302715ba616a4de5b1b62f6e5940a779.png
[4286bb37c9a044ac8d1a41e8124a9884.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/9ac74f3ed0924180a6ae0d2ede5b9b88.png
[4e1a255eb3f84513b3a16903f8149077.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/bf8a094310294c7faabe48ea3d5370d6.png
[b3533031a1954c65af3d8bb0ceea0a7f.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/0919fb8d27db492981e673baef2f7742.png
[c611e6aea24f43399be07ed4e79f4757.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/7a0ed003f10648c8833b01de5c75c18d.png
[57d774f327ed422a9805204a25f5394b.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/63dff47b084445818b7fc1f9c71811ae.png
[1df85767dc5a41cb9aeb2c74e684c782.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/22905388b4274073b2f872f9f01031b4.png
[e3779861d7a6421287f915e343621b4d.png_x-oss-process_imagetype_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/2613941cc8554d9d8dda9c8e2be04cd5.png