06第六章+存储管理（2）1.ppt

1、6.4外部存储资源管理：外部存储空间被划分为静态等长2i，称为块。块是外部存储分配和输入输出传输的基本单位。外部内存空间分配自由区块链(慢速)自由块表(UNIX)位图、交换空间、文件空间、输入井、输出井、进程和外部内存对应关系，每个进程边界地址占用一组外部内存连续块；每个进程占用两组外部存储器连续块(双边界)。页面内存是一页，外部内存是一页。段类型：每个段占用外部存储器中几个连续的块。分段页面内存是一页，外部内存是一页。6.5虚拟存储系统，没有虚拟问题不能运行大于内存的程序；所有进程都被加载到内存中，这浪费了空间(进程活动是本地的)。具有单一控制流的进程需要较少的内存；具有多个控制流的进程需要

2、更多内存。虚拟存储过程部分加载到内存中，部分(或完全)加载到外部内存中，运行时访问在外部内存中动态转移，因此内存不足以消除。6.5.1虚拟页面存储系统，基本原则在进程运行之前：它们都被加载到外部内存中，有些被加载到内存中。当进程运行时：访问页不在内存中，并且发生缺页中断。中断处理程序：在外部存储器中找到访问页的地址；在内存中找到空闲页面；如果不是，根据消除算法消除一个；如有必要，将废弃页面写回外部存储器，并修改页面表和总页面表；阅读所需页面(切换过程)；重新启动中断命令。6.5.1虚拟页面存储管理(续。)，虚拟页存储管理地址映射，指令给出逻辑地址(P，D)，P查找快速表得到F，发现F和D的组合

3、物理地址0pl-1是越界中断，B和P在页表中查找F，页在内存中，丢失的页被中断。更新页表和快速表，恢复站点、f、t、t、(f、d)如果快速表已满，请删除一个条目、硬件和软件逻辑页码、页框号、访问权限修改标志、p f r、w、e (0，1)、6.5.1.2内存页面帧分配策略(静态策略)1。平均分配，例如128页内存，25个进程，每个进程5帧。按照工艺长度S=si的比例分配pi；内存中有m页。根据流程优先级进行分配4。根据进程长度和优先级比例分配静态策略不反映：(1)程序结构；(2)不同时期节目的行为特征。外部存储块1的6.5.1.3分配策略。外部内存的静态分配保留进程的所有页面：优点：速度快-过

4、时时不需要写回(未修改的情况)缺点：浪费外部内存2。外部内存的动态分配只保留进程不在内存中的页面：优点：节省外部内存缺点：速度慢-过时时必须写回，6.5.1。2.页面错误前的预分页，即在访问时调用(根据程序顺序行为不一定准确)。预寻呼必须辅之以请寻呼。用于页面消除、段消除和快速表格消除。目标：最低页面错误率。1.最佳消除算法(OPT -最优)将消除那些在未来最长时间后使用的算法。最有效率，不可怕。6.5.1.5替换算法，2。先进先出(先进先出)以消除首次调用。根据：的第一个条目可能已经用完。实现：队列负情况：一些代码和数据可能在整个程序运行中使用。belady异常：示例：1、2、3、4、1、2

5、、5、1、2、3、4、5内存3物理页面：页面故障率=9/12内存4物理页面：页面故障率=10/12，先进先出消除算法(Belady异常)，页面故障率=。替换使用时间最长的页面。实现：当一个页面被访问时，栈被从栈中取出并被压到顶部，栈的底部是： LRU页面。示例：引用字符串33604，7，0，7，1，0，1，2，7，1，2，A前堆栈，B前堆栈，A，B，LRU算法，4。最近未使用以消除最近未使用的。实现：在每个页面上添加一个访问标志，将访问设置为1，定期清除它，当它被清除时，取0。LRU算法的近似：参考字符串： 2，3，5，6，4，2，5，6，7，5，6，8，标志清除为0，选择性消除LRU: 3

6、NUR: 2，3，4任意，5。根据：活动访问页面应该有大量的访问。患者： (1)在早期使用，但以后不再使用，因此很难更换；(2)刚传入的页面参考文献很少，可能会被换出。实现：调用计数器清除0，访问增加1，最小的一个被删除。6.最常用的MFU是最常用的。根据：它可能已经用完了。在整个程序运行过程中使用了：程序的部分组件。7。第二次机会，删除加载时间最长且最近未被访问的页面。实现：采用拉链数据结构。8。时钟算法，它将页面组织成一个环，指针指向当前位置。每次需要删除一个页面时，从指针指向的页面开始检查。如果当前页的访问位为0，即自上次检测以来该页未被访问过，则该页将被替换。如果当前页面的访问位为1，

7、将其清零，并将指针顺时针移动到下一个位置。重复上述步骤，直到找到访问位为0的页面。可以看出，时钟算法的消除效果与二次机会算法基本相同。不同之处在于两种算法采用的数据结构不同。第二次机会使用链表，这需要额外的存储空间，并且链断开和进入的速度非常慢。时钟算法可以直接使用页表中的参考位并添加指针，速度快且节省空间。第6页/r=1，第3页/r=1，第4页/r=0，第8页/r=0，第10页/r=1，第9页/r=0，第0页/r=0，第1页/r=1，第9页/r=0，第0页/r=0，第1页/r=1，方框12，方框23，方框51，方框6，方框81，方框96，方框60，方框5，访问第18页，时钟算法，改进的时钟算

8、法，考虑修改标记m r=0，m=0:最佳废弃页r=0，m=1:在废弃之前写回r=1，m=0:不废弃r=1，m=1:不废弃，改进的时钟算法，步骤1:从指针的当前位置开始扫描，选择最佳废弃页，不改变参考位，步骤2:如果步骤1失败，再次从原始位置开始，找到r=0和m=1的页，将满足上述要求的第一页作为废弃页，并且第三步：如果第二步失败，指针再次回到原来的位置，再次执行第一步。如果仍然失败，请再次执行步骤2，此时您会发现它。第6页/r=1 m=1，第3页/r=1，第18页/r=1 m=0，第8页/r=1 m=0，第10页/r=1 m=0，第9页/r=0 m。第6页/r=1 m=1，第3页/r=1 m=

9、1，第18页/r=1 m=0，第8页/r=1 m=0，第10页/r=1 m=0，第9页/r=0 m=1，第0页第6页/r=0 第9页/r=0 m=1，第0页/r=0 m=1第6页/r=1 m=1，第3页/r=1 m=1，第18页/r=1 m=0，第8页/r=0 m=0，第10页/r=0 m=0，第15页/r=1 m=0，第0页/r=0 m=1。进程空间和内存空间为64k，页面长度为1K，一个进程有6个页面，内存分配有4个页面帧。 页表和时钟在280小时的数据结构如下：0页，2页，3页，5页，第5帧，第12帧，第8帧，第3帧，(顺时针)，2010 (2)使用先进先出替换算法，物理页帧号是多少？物

10、理地址是什么？(3)使用时钟替换算法的页面帧号是多少？物理地址是什么？2010考研试题，(1)将逻辑地址13B7H转换成二进制数0001001110110111，其中最后10位为页面地址，前6位为逻辑页码，即逻辑页码为4。(2)第4页不在内存中，发生缺页中断。根据先进先出替换算法，第5页应该被替换，从而产生第3页帧号，形成物理地址000011110110111，该地址以十六进制标记为0FB7H。(3)使用时钟替换算法，页0被消除以获得页帧5，并且物理地址是0001011110110111，其以十六进制标记为17B7H。6.5.1.6颠簸页面经常在内存和外部内存之间来回切换。原因：(1)分配给进

11、程的物理帧太少；(2)剔除算法不合理。处理：(1)增加分配给进程的物理帧的数量；(2)改进剔除算法。在一些虚拟页存储管理系统中，内存中总是有一个空闲的物理页架。这有什么好处？6.5.1.7工作集模型，工作集):是一个进程在一段时间内访问的页面的集合。ws (t)，=5，7，1，6，2，261 57 7 5 1 6 2 1 2 3(页面引用)，t，称为窗口大小。丹宁认为，为了使程序有效运行，工作集应该能够被放入内存。t，工作集与时间有关：工作集与窗口大小有关：程序大小，WS，窗口大小确定：太小：不能加载所有活动页面，页面失败率高；太大：浪费内存。多诺万建议，马尼克：一万次访问。实现：增加访问位：

12、在页表中，开始时全部清零，结束时(新打开开始时)置1，这是本周期的工作集，n 1=wn(1)-n，6.5.1.8页失败率反馈模型，PFFB(Page Fault Feed Back)页失败率高(达到某一上限)，页失败率低(达到某一下限):内存页多，页少。6.5.2虚拟段存储系统，在进程运行之前，它们都被加载到外部存储器中，并且其中一些被加载到存储器中。当访问段不再在内存中时，会发生段中断。、6.5.2虚拟段存储系统(续。)、虚拟段存储管理地址映射、指令确定逻辑地址(s，d)和s查找快速表得到b和l，找出后，b和d得到物理地址0sl-1，这是越界中断，b和s查找段表，这是在内存中，但丢失的段被中断，并保存站点。修改段表和表达表并恢复站点。f、f、t、t、(s、b、l)如果快速表已满，将删除一个条目。、硬件和软件将完成，t，0dl-1，t，F，修改段表，.动态连接：运行时连接由操作系统完成。静态连接的缺点是连接时间长