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


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200
							<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>完全公平调度算法 | 操作系统实验</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/27.9fdfa008.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/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/61.8ebdd979.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 router-link-active">
  实验3-进程调度算法
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Lab/Lab4/" class="nav-link">
  实验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 router-link-active">
  实验3-进程调度算法
</a></li><li class="dropdown-subitem"><a href="/OS_lab_tutorial/Linux/Lab/Lab4/" class="nav-link">
  实验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/Lab3/" aria-current="page" class="sidebar-link">任务说明</a></li><li><a href="/OS_lab_tutorial/Linux/Lab/Lab3/RR.html" aria-current="page" class="active sidebar-link">RR调度算法</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/OS_lab_tutorial/Linux/Lab/Lab3/RR.html#调度策略与算法原理" class="sidebar-link">调度策略与算法原理</a></li><li class="sidebar-sub-header"><a href="/OS_lab_tutorial/Linux/Lab/Lab3/RR.html#实验步骤" class="sidebar-link">实验步骤</a></li><li class="sidebar-sub-header"><a href="/OS_lab_tutorial/Linux/Lab/Lab3/RR.html#实验结果" class="sidebar-link">实验结果</a></li></ul></li><li><a href="/OS_lab_tutorial/Linux/Lab/Lab3/SJF.html" class="sidebar-link">SJF调度算法</a></li><li><a href="/OS_lab_tutorial/Linux/Lab/Lab3/CFS.html" class="sidebar-link">CFS调度算法</a></li><li><a href="/OS_lab_tutorial/Linux/Lab/Lab3/MLFQ.html" class="sidebar-link">MLFQ调度算法</a></li></ul></section></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="完全公平调度算法"><a href="#完全公平调度算法" class="header-anchor">#</a> 完全公平调度算法</h1> <h2 id="调度策略与算法原理"><a href="#调度策略与算法原理" class="header-anchor">#</a> 调度策略与算法原理</h2> <p>	RR（Round-Robin，轮转调度）是一种常见的进程调度策略，它以时间片（固定时间段）为单位，依次为每个进程分配CPU时间。每个进程在就绪队列中按照到达顺序排队，并且每个进程都能够在一个时间片内获得一定的CPU执行时间，然后被放回队列尾部继续等待执行。</p> <p>基本原则和策略：</p> <ol><li>时间片：RR调度策略将CPU时间划分为固定的时间片。当一个进程获得CPU执行时，它被允许执行一个时间片的长度，然后被放回队列等待下一次执行。</li> <li>队列调度：进程按照到达顺序排队在就绪队列中，每个进程依次获得执行机会。当一个进程的时间片用完后，==它被放回队列的尾部==，下一个进程开始执行。</li> <li>循环执行：RR调度策略按照循环的方式执行进程，每个进程都能获得一定的CPU时间，以确保公平性。</li> <li>非抢占式调度：一个进程在执行过程中不会被强制中断或抢占，直到它的时间片用完。</li></ol> <p>	RR调度策略具有公平性和响应性，因为每个进程都能获得一定的执行时间，并且长时间运行的进程不会占用所有的CPU时间。然而，如果时间片过小，会导致频繁的上下文切换，增加系统开销；如果时间片过大，会影响系统对紧急任务的响应时间。</p> <p>	RR调度策略在操作系统中被广泛应用，尤其是在分时系统和交互式系统中，它能够合理分配CPU时间，提供良好的用户体验。</p> <h2 id="实验步骤"><a href="#实验步骤" class="header-anchor">#</a> 实验步骤</h2> <p>	以下实验编写的属于单进程运行的程序，难以展现出操作系统内核中真实情况下并行计算的场景。不过作者希望通过模拟该算法的实现，学生能够体会到RR进程调度的算法步骤以及特点。</p> <p>（1）我们设计一个系统内通用的进程控制块，保存进程的所有数据，包括但不限于以下内容：</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token keyword">struct</span> <span class="token class-name">Process</span> <span class="token punctuation">{</span>
	<span class="token keyword">int</span> pid<span class="token punctuation">;</span>          <span class="token comment">// 进程ID</span>
	string name<span class="token punctuation">;</span>      <span class="token comment">// 进程名称</span>

	<span class="token comment">// 以下时间都以 ns 为单位</span>
	<span class="token keyword">int</span> arrive_time<span class="token punctuation">;</span>  <span class="token comment">// 进程到达时间</span>
	<span class="token keyword">int</span> burst_time<span class="token punctuation">;</span>   <span class="token comment">// 进程的总共需要执行时间(为了模拟进程运行而做出的假设)</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre></div><p>（2）我们不仅仅需要模拟RR调度算法，还需要模拟在调度过程中操作系统为RR调度器提供了什么样的帮助，比如在下面的实现中，就使用了CPU时间（无需复制该代码，该代码在第3点的scheduleRR函数中）：</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token comment">/* 操作系统的变量 */</span>
<span class="token keyword">int</span> current_cpu_time <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>  <span class="token comment">// 假设目前系统刚刚启动，时间为0</span>
</code></pre></div><p>（3）调度算法的实现：</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token keyword">void</span> <span class="token function">schedule</span><span class="token punctuation">(</span>Process proc<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> n<span class="token punctuation">,</span> <span class="token keyword">int</span> time_slice<span class="token punctuation">)</span> <span class="token punctuation">{</span>
	<span class="token function">sort</span><span class="token punctuation">(</span>proc<span class="token punctuation">,</span> proc <span class="token operator">+</span> n<span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">(</span>Process a<span class="token punctuation">,</span> Process b<span class="token punctuation">)</span> <span class="token punctuation">{</span>
		<span class="token keyword">return</span> a<span class="token punctuation">.</span>arrive_time <span class="token operator">&lt;</span> b<span class="token punctuation">.</span>arrive_time<span class="token punctuation">;</span>
	<span class="token punctuation">}</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 按到达时间排序</span>

	<span class="token keyword">int</span> current_cpu_time <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>  <span class="token comment">// 假设目前系统刚刚启动，时间为0</span>
	<span class="token keyword">int</span> min_notarrive_time<span class="token punctuation">;</span>

	<span class="token keyword">bool</span> notfinished<span class="token punctuation">;</span>
	<span class="token keyword">do</span> <span class="token punctuation">{</span>
		notfinished <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span>   
		min_notarrive_time <span class="token operator">=</span> INT_MAX<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> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
			Process<span class="token operator">*</span> curr <span class="token operator">=</span> <span class="token operator">&amp;</span>proc<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>

			<span class="token keyword">int</span> burst <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>

			<span class="token keyword">if</span> <span class="token punctuation">(</span>curr<span class="token operator">-&gt;</span>arrive_time <span class="token operator">&lt;=</span> current_cpu_time<span class="token punctuation">)</span> <span class="token punctuation">{</span>  <span class="token comment">// 进程到达</span>
				<span class="token comment">// 执行一个时间片</span>
				burst <span class="token operator">=</span> <span class="token function">min</span><span class="token punctuation">(</span>time_slice<span class="token punctuation">,</span> curr<span class="token operator">-&gt;</span>burst_time<span class="token punctuation">)</span><span class="token punctuation">;</span>
				cout <span class="token operator">&lt;&lt;</span> <span class="token string">&quot;执行进程 &quot;</span> <span class="token operator">&lt;&lt;</span> curr<span class="token operator">-&gt;</span>pid <span class="token operator">&lt;&lt;</span> <span class="token string">&quot;，执行时间片 &quot;</span> <span class="token operator">&lt;&lt;</span> burst <span class="token operator">&lt;&lt;</span> <span class="token string">&quot; ns&quot;</span> <span class="token operator">&lt;&lt;</span> endl<span class="token punctuation">;</span>
				curr<span class="token operator">-&gt;</span>burst_time <span class="token operator">-=</span> burst<span class="token punctuation">;</span>
			<span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>  <span class="token comment">// 未到达</span>
				min_notarrive_time <span class="token operator">=</span> <span class="token function">min</span><span class="token punctuation">(</span>min_notarrive_time<span class="token punctuation">,</span> curr<span class="token operator">-&gt;</span>arrive_time<span class="token punctuation">)</span><span class="token punctuation">;</span>
			<span class="token punctuation">}</span>

			<span class="token keyword">if</span> <span class="token punctuation">(</span>curr<span class="token operator">-&gt;</span>burst_time <span class="token operator">&gt;</span> <span class="token number">0</span><span class="token punctuation">)</span> notfinished <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
			
			<span class="token keyword">if</span> <span class="token punctuation">(</span>burst<span class="token punctuation">)</span> current_cpu_time <span class="token operator">+=</span> burst<span class="token punctuation">;</span>
			<span class="token keyword">else</span> current_cpu_time <span class="token operator">=</span> min_notarrive_time<span class="token punctuation">;</span>
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span> <span class="token keyword">while</span> <span class="token punctuation">(</span>notfinished<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><p>（4）写下main程序：</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
	Process proc<span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">{</span>
		<span class="token punctuation">{</span>
			<span class="token number">0</span><span class="token punctuation">,</span>
			<span class="token string">&quot;init&quot;</span><span class="token punctuation">,</span>
			<span class="token number">500'0000</span><span class="token punctuation">,</span>
			<span class="token number">10'000'000</span><span class="token punctuation">,</span>
		<span class="token punctuation">}</span><span class="token punctuation">,</span>
		<span class="token punctuation">{</span>
			<span class="token number">1</span><span class="token punctuation">,</span>
			<span class="token string">&quot;apic driver&quot;</span><span class="token punctuation">,</span>
			<span class="token number">0</span><span class="token punctuation">,</span>
			<span class="token number">10'000'000</span><span class="token punctuation">,</span>
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span><span class="token punctuation">;</span>

	<span class="token function">schedule</span><span class="token punctuation">(</span>proc<span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">500'0000</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> <img src="/OS_lab_tutorial/assets/img/RR-result.975d3019.png" alt="image-20230710171839016" style="zoom:80%;"></div> <footer class="page-edit"><!----> <!----></footer> <div class="page-nav"><p class="inner"><span class="prev">
      ←
      <a href="/OS_lab_tutorial/Linux/Lab/Lab3/" class="prev router-link-active">
        任务说明
      </a></span> <span class="next"><a href="/OS_lab_tutorial/Linux/Lab/Lab3/SJF.html">
        SJF调度算法
      </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/27.9fdfa008.js" defer></script>
  </body>
</html>