DragonOS-Community
/
OS_lab_tutorial
mirror of https://github.com/DragonOS-Community/OS_lab_tutorial.git


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213
							<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>最近最久未使用算法（LRU） | 操作系统实验</title>
    <meta name="generator" content="VuePress 1.9.10">
    
    <meta name="description" content="Welcome!">
    
    <link rel="preload" href="/OS_lab_tutorial/assets/css/0.styles.dbcc0abd.css" as="style"><link rel="preload" href="/OS_lab_tutorial/assets/js/app.de832b6b.js" as="script"><link rel="preload" href="/OS_lab_tutorial/assets/js/2.6cca19a7.js" as="script"><link rel="preload" href="/OS_lab_tutorial/assets/js/1.2e5d3cee.js" as="script"><link rel="preload" href="/OS_lab_tutorial/assets/js/61.8ebdd979.js" as="script"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/10.e3ae3b6e.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/11.c389195a.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/12.15e02b09.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/13.e100960d.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/14.3675c8e8.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/15.5542c093.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/16.01c35b5f.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/17.bd8d538c.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/18.6d3b94c1.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/19.eb35cfee.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/20.c11ec329.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/21.160e1109.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/22.8c6c68bf.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/23.6c245a02.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/24.c2cc382b.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/25.3a441277.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/26.7dca1b95.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/27.9fdfa008.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/28.ea152bf8.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/29.310b119e.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/3.5322f14a.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/30.1be87618.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/31.e60e769a.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/32.ed12ff5e.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/33.d0e6ffd8.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/34.fb25dd7d.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/35.38b1a166.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/36.f2dcdc62.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/37.85edb076.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/38.a07efacb.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/39.2e2bced7.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/4.ba0ffc9e.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/40.7564ba2d.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/41.7bc98649.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/42.ee9b7b13.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/43.dbdee45b.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/44.f24405f8.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/45.bebd92ee.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/46.5d70de3f.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/47.0df811bd.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/48.3f21f3a0.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/49.4ceb6d85.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/5.1674539b.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/50.9d21087d.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/51.760bed26.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/52.78b43a02.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/53.fd428cc4.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/54.4937721a.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/55.b040b54f.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/56.f538318b.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/57.47c5385e.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/58.c8103992.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/59.7a4c397a.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/6.44f67c6a.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/60.1f64a100.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/62.6cab9dfb.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/63.380a795e.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/64.57bfd1e1.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/65.54ffadf5.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/66.dccb9c04.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/7.21830bc0.js"><link rel="prefetch" href="/OS_lab_tutorial/assets/js/vendors~docsearch.cf079a49.js">
    <link rel="stylesheet" href="/OS_lab_tutorial/assets/css/0.styles.dbcc0abd.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/OS_lab_tutorial/" class="home-link router-link-active"><!----> <span class="site-name">操作系统实验</span></a> <div class="links"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="/OS_lab_tutorial/" class="nav-link">
  首页
</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="Linux" class="dropdown-title"><span class="title">Linux</span> <span class="arrow down"></span></button> <button type="button" aria-label="Linux" class="mobile-dropdown-title"><span class="title">Linux</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>
          实验教程
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Lab/Lab1.html" class="nav-link">
  实验1-熟悉类Linux系统
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Lab/Lab2.html" class="nav-link">
  实验2-进程创建与进程间通信
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Lab/Lab3/" class="nav-link">
  实验3-进程调度算法
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Lab/Lab4/" class="nav-link router-link-active">
  实验4-存储管理算法
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Lab/Lab5.html" class="nav-link">
  实验5-文件管理系统
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Lab/Lab6.html" class="nav-link">
  实验6-网络编程(暂定)
</a></li></ul></li><li class="dropdown-item"><h4>
          课程练习
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Assignment/Lab1.html" class="nav-link">
  实验1-熟悉类Linux系统
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Assignment/Lab2.html" class="nav-link">
  实验2-进程创建与进程间通信
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Assignment/Lab3.html" class="nav-link">
  实验3-进程调度算法
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Assignment/Lab4.html" class="nav-link">
  实验4-存储管理算法
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Assignment/Lab5.html" class="nav-link">
  实验5-文件管理系统
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Assignment/Lab6.html" class="nav-link">
  实验6-网络编程(暂定)
</a></li></ul></li><li class="dropdown-item"><h4>
          附录
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Appendix/Lab1.html" class="nav-link">
  实验1-熟悉类Linux系统
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Appendix/Lab2.html" class="nav-link">
  实验2-进程创建与进程间通信
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Appendix/Lab3.html" class="nav-link">
  实验3-进程调度算法
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Appendix/Lab4.html" class="nav-link">
  实验4-存储管理算法
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Appendix/Lab5.html" class="nav-link">
  实验5-文件管理系统
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Appendix/Lab6.html" class="nav-link">
  实验6-网络编程(暂定)
</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="DragonOS" class="dropdown-title"><span class="title">DragonOS</span> <span class="arrow down"></span></button> <button type="button" aria-label="DragonOS" class="mobile-dropdown-title"><span class="title">DragonOS</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>
          实验教程
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/OS_lab_tutorial/DragonOS/Lab/Lab1.html" class="nav-link">
  实验-文件系统
</a></li></ul></li><li class="dropdown-item"><h4>
          课程练习
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/OS_lab_tutorial/DragonOS/Assignment/Lab1.html" class="nav-link">
  实验-文件系统
</a></li></ul></li><li class="dropdown-item"><h4>
          附录
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/OS_lab_tutorial/DragonOS/Appendix/Lab1.html" class="nav-link">
  实验-文件系统
</a></li></ul></li></ul></div></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"><div class="nav-item"><a href="/OS_lab_tutorial/" class="nav-link">
  首页
</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="Linux" class="dropdown-title"><span class="title">Linux</span> <span class="arrow down"></span></button> <button type="button" aria-label="Linux" class="mobile-dropdown-title"><span class="title">Linux</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>
          实验教程
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Lab/Lab1.html" class="nav-link">
  实验1-熟悉类Linux系统
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Lab/Lab2.html" class="nav-link">
  实验2-进程创建与进程间通信
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Lab/Lab3/" class="nav-link">
  实验3-进程调度算法
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Lab/Lab4/" class="nav-link router-link-active">
  实验4-存储管理算法
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Lab/Lab5.html" class="nav-link">
  实验5-文件管理系统
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Lab/Lab6.html" class="nav-link">
  实验6-网络编程(暂定)
</a></li></ul></li><li class="dropdown-item"><h4>
          课程练习
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Assignment/Lab1.html" class="nav-link">
  实验1-熟悉类Linux系统
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Assignment/Lab2.html" class="nav-link">
  实验2-进程创建与进程间通信
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Assignment/Lab3.html" class="nav-link">
  实验3-进程调度算法
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Assignment/Lab4.html" class="nav-link">
  实验4-存储管理算法
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Assignment/Lab5.html" class="nav-link">
  实验5-文件管理系统
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Assignment/Lab6.html" class="nav-link">
  实验6-网络编程(暂定)
</a></li></ul></li><li class="dropdown-item"><h4>
          附录
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Appendix/Lab1.html" class="nav-link">
  实验1-熟悉类Linux系统
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Appendix/Lab2.html" class="nav-link">
  实验2-进程创建与进程间通信
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Appendix/Lab3.html" class="nav-link">
  实验3-进程调度算法
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Appendix/Lab4.html" class="nav-link">
  实验4-存储管理算法
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Appendix/Lab5.html" class="nav-link">
  实验5-文件管理系统
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Appendix/Lab6.html" class="nav-link">
  实验6-网络编程(暂定)
</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="DragonOS" class="dropdown-title"><span class="title">DragonOS</span> <span class="arrow down"></span></button> <button type="button" aria-label="DragonOS" class="mobile-dropdown-title"><span class="title">DragonOS</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>
          实验教程
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/OS_lab_tutorial/DragonOS/Lab/Lab1.html" class="nav-link">
  实验-文件系统
</a></li></ul></li><li class="dropdown-item"><h4>
          课程练习
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/OS_lab_tutorial/DragonOS/Assignment/Lab1.html" class="nav-link">
  实验-文件系统
</a></li></ul></li><li class="dropdown-item"><h4>
          附录
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/OS_lab_tutorial/DragonOS/Appendix/Lab1.html" class="nav-link">
  实验-文件系统
</a></li></ul></li></ul></div></div> <!----></nav>  <ul class="sidebar-links"><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading open"><span>存储管理</span> <span class="arrow down"></span></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/OS_lab_tutorial/Linux/Lab/Lab4/" aria-current="page" class="sidebar-link">任务说明</a></li><li><a href="/OS_lab_tutorial/Linux/Lab/Lab4/FIFO.html" class="sidebar-link">FIFO页面置换算法</a></li><li><a href="/OS_lab_tutorial/Linux/Lab/Lab4/LRU.html" aria-current="page" class="active sidebar-link">LRU页面置换算法</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/OS_lab_tutorial/Linux/Lab/Lab4/LRU.html#置换策略与算法原理" class="sidebar-link">置换策略与算法原理</a></li><li class="sidebar-sub-header"><a href="/OS_lab_tutorial/Linux/Lab/Lab4/LRU.html#实验步骤" class="sidebar-link">实验步骤</a></li><li class="sidebar-sub-header"><a href="/OS_lab_tutorial/Linux/Lab/Lab4/LRU.html#实验样例" class="sidebar-link">实验样例</a></li></ul></li><li><a href="/OS_lab_tutorial/Linux/Lab/Lab4/CLOCK.html" class="sidebar-link">CLOCK页面置换算法</a></li></ul></section></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="最近最久未使用算法-lru"><a href="#最近最久未使用算法-lru" class="header-anchor">#</a> 最近最久未使用算法（LRU）</h1> <h2 id="置换策略与算法原理"><a href="#置换策略与算法原理" class="header-anchor">#</a> 置换策略与算法原理</h2> <p>	LRU页面置换算法的置换策略是淘汰最近最久未使用的页面，选择在内存中最长时间没有被访问的页面予以淘汰，而替换此时需要调用的页面。</p> <p>	LRU页面置换算法的算法原理是根据页面调入内存后的使用情况来做决策的。无法预估页面将来的使用情况，利用过去的页面使用情况来进行置换的。</p> <p>	LRU页面置换算法的一种实现方法是使用一个数组<code>pages[]</code>存放当前正在内存中的页面，每一次访问页面就只需要更新<code>time_access</code>变量，当需要页面置换的时候，选出<code>pages[]</code>中<code>time_access</code>最小的页面，然后把他从数组替换成需要调入的页面。</p> <p>	※ LRU页面置换算法的另一种比较合理和高效实现方法是利用一个哈希表和一个双向链表来模拟缓存系统。哈希表用于记录每个页面的地址，双向链表用于记录每个页面被访问的先后顺序。每当进程访问页面时，便将该页面从链表中删除，并将它插入到链表头部。这样，链表头部始终是最新被访问页面的地址，而链表尾部则是最近最久没有被使用的页面的地址。</p> <p>	LRU页面置换算法的优点是能够较好地反映程序局部性原理，即最近被访问过的页面很可能在不久后再次被访问。因此，LRU算法能够减少缺页次数，提高程序性能。</p> <p>	LRU页面置换算法的缺点是实现起来比较复杂，需要维护额外的数据结构来记录每个页面的使用情况，并且需要频繁地更新这些数据结构。因此，LRU算法需要较多的时间和空间开销。</p> <h2 id="实验步骤"><a href="#实验步骤" class="header-anchor">#</a> 实验步骤</h2> <p>	接上文，在这里继续完成置换算法的实现</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token comment">// 假设页面的结构体定义如下</span>
<span class="token keyword">struct</span> <span class="token class-name">Page</span> <span class="token punctuation">{</span>
  <span class="token keyword">int</span> read<span class="token punctuation">;</span> <span class="token comment">// 读标志</span>
  <span class="token keyword">int</span> write<span class="token punctuation">;</span> <span class="token comment">// 写标志</span>
  <span class="token keyword">int</span> time_arrive<span class="token punctuation">;</span> <span class="token comment">// 到达时间</span>
  <span class="token keyword">int</span> time_access<span class="token punctuation">;</span> <span class="token comment">// 访问时间</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>

<span class="token comment">// 定义一个页面置换算法LRU类</span>
<span class="token keyword">class</span> <span class="token class-name">LRU</span> <span class="token punctuation">{</span>
<span class="token keyword">private</span><span class="token operator">:</span>
  <span class="token keyword">int</span> page_num<span class="token punctuation">;</span> <span class="token comment">// 页面数量</span>
  <span class="token keyword">int</span> mem_size<span class="token punctuation">;</span> <span class="token comment">// 内存大小</span>
  Page<span class="token operator">*</span> pages<span class="token punctuation">;</span> <span class="token comment">// 页面数组</span>
  Page<span class="token operator">*</span><span class="token operator">*</span> memory<span class="token punctuation">;</span> <span class="token comment">// 内存数组，用于存放当前正在内存中的页面</span>
  <span class="token keyword">int</span> page_faults<span class="token punctuation">;</span> <span class="token comment">// 缺页次数</span>

<span class="token keyword">public</span><span class="token operator">:</span>
  <span class="token comment">// 构造函数，根据给定的页面数量，内存大小和页面数组初始化类的成员变量</span>
  <span class="token function">LRU</span><span class="token punctuation">(</span><span class="token keyword">int</span> pn<span class="token punctuation">,</span> <span class="token keyword">int</span> ms<span class="token punctuation">,</span> Page<span class="token operator">*</span> ps<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    page_num <span class="token operator">=</span> pn<span class="token punctuation">;</span>
    mem_size <span class="token operator">=</span> ms<span class="token punctuation">;</span>
    pages <span class="token operator">=</span> ps<span class="token punctuation">;</span>
    memory <span class="token operator">=</span> <span class="token keyword">new</span> Page<span class="token operator">*</span><span class="token punctuation">[</span>mem_size<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">// 动态分配内存数组的空间</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> mem_size<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 初始化内存数组，开始时都为空</span>
      memory<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token keyword">nullptr</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    page_faults <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>

  <span class="token comment">// 析构函数，释放内存数组的空间</span>
  <span class="token operator">~</span><span class="token function">LRU</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">delete</span><span class="token punctuation">[</span><span class="token punctuation">]</span> memory<span class="token punctuation">;</span>
  <span class="token punctuation">}</span>

  <span class="token comment">// 执行页面置换算法的函数，根据给定的页面访问序列进行操作，并输出结果</span>
  <span class="token keyword">void</span> <span class="token function">run</span><span class="token punctuation">(</span>Page<span class="token operator">*</span> query<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> len<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> len<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 遍历所有页面访问序列</span>
      <span class="token keyword">bool</span> hit <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span> <span class="token comment">// 是否命中标志</span>
      <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> mem_size<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 遍历所有内存块</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>memory<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">==</span> query<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 如果当前访问的页面已经在内存中</span>
          hit <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span> <span class="token comment">// 设置命中标志为真</span>
          memory<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">-&gt;</span>time_access <span class="token operator">=</span> i <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment">// 更新该页面的访问时间为当前序号加一（避免为零）</span>
          <span class="token keyword">break</span><span class="token punctuation">;</span> <span class="token comment">// 跳出循环</span>
        <span class="token punctuation">}</span>
      <span class="token punctuation">}</span>
      <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>hit<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 如果没有命中</span>
        page_faults<span class="token operator">++</span><span class="token punctuation">;</span> <span class="token comment">// 缺页次数加一</span>
        <span class="token keyword">int</span> min_time <span class="token operator">=</span> INT_MAX<span class="token punctuation">;</span> <span class="token comment">// 最小访问时间，初始为最大整数值</span>
        <span class="token keyword">int</span> min_index <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment">// 最小访问时间对应的内存块索引，初始为-1</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> k <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> k <span class="token operator">&lt;</span> mem_size<span class="token punctuation">;</span> k<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 遍历所有内存块，寻找最小访问时间的页面</span>
          <span class="token keyword">if</span> <span class="token punctuation">(</span>memory<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token operator">-&gt;</span>time_access <span class="token operator">&lt;</span> min_time<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 如果当前内存块中的页面访问时间小于最小访问时间</span>
            min_time <span class="token operator">=</span> memory<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token operator">-&gt;</span>time_access<span class="token punctuation">;</span> <span class="token comment">// 更新最小访问时间为当前访问时间</span>
            min_index <span class="token operator">=</span> k<span class="token punctuation">;</span> <span class="token comment">// 更新最小访问时间对应的内存块索引为当前索引</span>
          <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        memory<span class="token punctuation">[</span>min_index<span class="token punctuation">]</span> <span class="token operator">=</span> query<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">// 将当前访问的页面放入内存中，替换最近最久未使用的页面</span>
        memory<span class="token punctuation">[</span>min_index<span class="token punctuation">]</span><span class="token operator">-&gt;</span>time_access <span class="token operator">=</span> i <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment">// 更新该页面的访问时间为当前序号加一（避免为零）</span>
      <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 输出结果</span>
    cout <span class="token operator">&lt;&lt;</span> <span class="token string">&quot;LRU page replacement algorithm results:&quot;</span> <span class="token operator">&lt;&lt;</span> endl<span class="token punctuation">;</span>
    cout <span class="token operator">&lt;&lt;</span> <span class="token string">&quot;Page faults: &quot;</span> <span class="token operator">&lt;&lt;</span> page_faults <span class="token operator">&lt;&lt;</span> endl<span class="token punctuation">;</span>
    cout <span class="token operator">&lt;&lt;</span> <span class="token string">&quot;Memory contents: &quot;</span> <span class="token operator">&lt;&lt;</span> endl<span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> mem_size<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      cout <span class="token operator">&lt;&lt;</span> <span class="token string">&quot;Memory block &quot;</span> <span class="token operator">&lt;&lt;</span> i <span class="token operator">&lt;&lt;</span> <span class="token string">&quot;: &quot;</span><span class="token punctuation">;</span>
      <span class="token keyword">if</span> <span class="token punctuation">(</span>memory<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">!=</span> <span class="token keyword">nullptr</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        cout <span class="token operator">&lt;&lt;</span> <span class="token string">&quot;Page &quot;</span> <span class="token operator">&lt;&lt;</span> memory<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">-</span> pages <span class="token operator">&lt;&lt;</span> endl<span class="token punctuation">;</span>
      <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
        cout <span class="token operator">&lt;&lt;</span> <span class="token string">&quot;Empty&quot;</span> <span class="token operator">&lt;&lt;</span> endl<span class="token punctuation">;</span>
      <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre></div><h2 id="实验样例"><a href="#实验样例" class="header-anchor">#</a> 实验样例</h2></div> <footer class="page-edit"><!----> <!----></footer> <div class="page-nav"><p class="inner"><span class="prev">
      ←
      <a href="/OS_lab_tutorial/Linux/Lab/Lab4/FIFO.html" class="prev">
        FIFO页面置换算法
      </a></span> <span class="next"><a href="/OS_lab_tutorial/Linux/Lab/Lab4/CLOCK.html">
        CLOCK页面置换算法
      </a>
      →
    </span></p></div> </main></div><div class="global-ui"></div></div>
    <script src="/OS_lab_tutorial/assets/js/app.de832b6b.js" defer></script><script src="/OS_lab_tutorial/assets/js/2.6cca19a7.js" defer></script><script src="/OS_lab_tutorial/assets/js/1.2e5d3cee.js" defer></script><script src="/OS_lab_tutorial/assets/js/61.8ebdd979.js" defer></script>
  </body>
</html>