五种进程调度的算法实现（⼀）
实验要求
1、基于Event-Driven（事件驱动）实现模拟进程调度，包括
最短⼯作优先（SJF）；
最短剩余时间优先（SRTF）；
最⾼响应⽐优先（HRRF）；
优先级调度（Priority）；
轮转调度（RR）。
其中，SJF、SRTF为⾮抢占式调度，其余为抢占式调度。
2、要求⽤C语⾔实现这五种调度算法。（⽅便起见，引⼊了C++头⽂件使⽤cout进⾏输出）
基础知识
⼀、进程
1.1 进程的含义
⼴义地说，进程是⼀个具有独⽴功能的程序关于某个数据集合的⼀次运⾏活动。
进程是⼀种抽象的概念，是对程序的抽象。程序是⼀连串的代码或指令，是静态的东西，就像⼀本书放在那⾥。
那什么时候，程序会“动”起来呢？当然是我们执⾏了它。⽐如⽤⿏标双击Word的快捷⽅式，那么过⼀会⼉，Word程序就会呈现在你眼前。究其过程，不是“你”执⾏了程序，⽽是你让计算机执⾏了程序。那计算机是怎么执⾏程序的呢？众所周知，这就要涉及到它的内部，甚⾄是它的⼤脑——中央处理器（CPU）了。
CPU是⼲什么的呢？CPU就是⽤来执⾏特定指令的。上⾯说道程序就如同⼀本书，那么CPU的⾓⾊就相当于读者，书上的⽂字相当于指令，CPU“读”了“书”之后，有所感悟，就去做相当的事情，完成相当的任务。
打个⽐⽅，要以书来⽐喻指令，那么⽤菜谱来说就再贴切不过了。
以菜谱为例，⽐如现在要做⼀道菜，按照菜谱上的10个步骤来。这⾥，做菜的时候，⾸先要准备⾷材、调料等，这都不是指令是什么回事？其实，计算机中的程序⽂件（可执⾏⽂件）除了包含代码之外，还包含数据，例如应⽤程序的图标等。接下来，“你”——CPU，就要按照步骤做菜了。做菜途中要等，就得等。⼀系列步骤下来，最终，⼀道上好的菜摆在你眼前，⾊⾹味俱全。这印证着定义中“具有独⽴功能”的含义，做⼀道特⾊的菜，就是独⽴完成⼀种任务。
1.2 进程的状态
最简单的概括（三态模型）是：进程的状态分为——等待态、就绪态、运⾏态。五态模型⽐三态模型多了新建态和终⽌态。
以同时炒多道菜为例。进程就相当于炒菜的过程。
等待态——某道菜可能需要煮、蒸、焖⼀会⼉，这时就需要等待它完成；
就绪态——某道菜煮、蒸、焖完了，需要你去处理，然⽽你现在正在做另⼀道菜，还没来得及切换过来；
运⾏态——炒当前的某道菜；
新建态——正准备做这道菜；
终⽌态——这道菜做完了，要做⼀些收尾⼯作。
1.3 进程的特征
进程的特征有四点：动态性、并发性、独⽴性、异步性。
仍以同时炒多道菜为例。
动态性——⽩天炒菜的整个过程，进程是“活”的，因为“你”正在⼯作。⽽到了晚上，厨房空⽆⼀⼈，进程是“死”的，厨房内的设施都回到了原位，如同没有⼈在这⾥炒过菜⼀样。进程在⼀天⼀夜之间有状态的切换，因此是动态的；
并发性——你可以同时炒多道菜；
独⽴性——你准备的调料是以某道菜的需求⽽准备的，⽽不是⾥⾯的某块⾁。菜谱中的步骤必须按部就班来，不能少不能乱。⼀种菜谱完成⼀道菜，不同菜谱完成的菜不同。你炒这道菜的过程不会影响炒那道菜的过程；
异步性——每道菜被烹饪的过程是间断的（由于是炒多道菜），被中断的时间是未知的。每次炒多道菜的总体时间并不相同，这也体现了炒多道菜的不可预知性。
以上是我的譬喻，⽽⽂字描述是这样的：
动态性——进程的实质是程序在多道程序系统中的⼀次执⾏过程，既然是过程就要有始有终，所以进程会产⽣、会消亡。进程执⾏完毕后，⼀般不会留下关于它运⾏的⼀丝痕迹；
并发性——任何进程都可以同其他进程⼀起并发执⾏，并发是任意时刻只有⼀个程序在运⾏（要与并⾏相区别）；
独⽴性——进程是⼀个能独⽴运⾏的基本单位，同时也是系统分配资源和调度的独⽴单位；
异步性——由于进程间的相互制约，使进程具有执⾏的间断性，即进程按各⾃独⽴的、不可预知的速度向前推进。
1.4 进程的调度
进程的调度分为抢占式和⾮抢占式（或剥夺式和⾮剥夺式）。
抢占式调度，正如它的名称“抢占”，抢过来⾃⼰占⽤，所以体现有两点——“抢”和“占”。
何为抢？依照算法，该任务权重⼤或者优先级⾼，⾃然⽽然就会“抢”到运⾏的机会。如果当时时刻系统
没有运⾏其它任务，那么该任务A被运⾏；如果当时时刻系统正在运⾏其它任务B，那么依照算法，如果该任务A有“抢”的资格，那就像抢凳⼦⼀样，A抢到了，B没有抢到，那么就暂停运⾏B，开始运⾏A。
何为占？任务抢到运⾏机会（即CPU时间）后，占有相应的运⾏时间。在这个时间内，系统只运⾏该任务，直到下⼀次系统利⽤算法重新分配任务的运⾏时间之前。
因此，正如抢凳⼦，抢凳⼦也是⼀种分配资源的⽅式，谁体形⼤、⼒⽓⼤、反应短，抢到的机会就多。在这其中，存在多⼈抢同⼀凳⼦的情况，这就是“竞争”；“好”的凳⼦，抢的⼈就多，竞争就越激烈。败者不⽢⼼，想尽快在下次争夺中取胜；胜者保持优势，战略上蔑视败者，但不能⾃⼤。
这⾥就要说到“队列”。假如你要完成⼀系列的事项，以菜谱为例，⼀共10个步骤。你现在把这10个步骤写在10个纸⽚上，然后把它们⼀个个摞起来，那么当前纸堆的最上⾯的纸⽚上就是你当前要做的步骤Step1，你把Step1做完后，把Step1丢弃，那么纸堆顶就是Step2，如此类推，最后剩下Step10，做完之后纸⽚就全部没有了，此时队列为“空”。
⽆论是抢占式还是⾮抢占式，都要依照这个“队列”中任务的先后顺序来运⾏它们。所以，队列代表着任务的“⽣存周期”。只要任务还在队列中，任务就没有“死”，即没有运⾏结束⽽消亡；任务就没有“⽣”，即任务还未开始运⾏。
现在，重点就是怎么安排这个队列，这就提到上述五种调度算法了。“调度”，可以看成安排队列的⼀种⽅式。
以队列为基础。抢占式调度意味着某任务A⼀旦运⾏之后，可能被其它任务B抢占，现在就要把A移到堆底，把B移到堆顶；⾮抢占式调度意味着某任务A⼀旦运⾏之后，就⼀直运⾏A直到结束，期间如果任务B也想要开始运⾏，就只能把B放在A的下⾯了，即任务的运⾏顺序从它们加⼊队列时就确定了，以后队列的顺序不会更改。
⼆、线程
2.1 线程的含义
线程是程序执⾏流的最⼩单元，是被系统独⽴调度和分派的基本单位。
如同进程是⼀种抽象⼀样，线程也是⼀种抽象，⼀种更⾼度的抽象。原先⼀个进程只能同时完成⼀种任务，现在需求多了，促使⼀个进程要同时完成多个任务，如果没有线程的概念，那么同⼀进程内的任务只能串⾏运⾏（按序运⾏）。
现在，把进程也看作⼀个系统，那么进程的“进程”就是线程了。进程原先作为任务调度的基本单位，与线程相⽐，进程太“⼤”了，所以相⽐较⽽⾔，线程的粒度更⼩。
2.2 线程的状态
线程的状态与进程的状态⼀样，也是五态模型，可以参照进程的五态模型。
2.3 线程的特点
线程是操作系统调度的基本单位；
线程的状态切换⽐进程更迅速且开销更⼩；
线程不拥有资源，只是任务的⼀种抽象，同⼀进程内的线程共享该进程的资源；
对单核CPU⽽⾔，同⼀时刻只能运⾏⼀个线程；
⼀个进程⾄少有⼀个线程，且是它的主线程。
2.4 线程与进程的区别
进程之间相互独⽴（资源的独⽴），⽽某⼀进程的各线程间共享资源（如果不能共享，岂不就与进程没多⼤区别了）；
由于进程的独⽴性，当进程间要相互通信时，系统只能提供各种外部⽅法，⽐较繁琐，⽽线程间的通信可以通过共享数据来实现；
线程的状态切换⽐进程更快捷且开销更⼩；
在多线程系统中，线程才是可执⾏对象，因为线程是进程中的并发任务的⼀种抽象。原先，进程是运⾏任务的主体，有了线程之后，运⾏任务的重担就落到了线程⾝上。
2.5 线程的优点
充分利⽤CPU资源（如下的超线程技术会提到这点）；
实现了进程内并发，使⽤任务的粒度分得更细，有利于开发⼈员对任务的分解、抽象（分解与抽象原则）；
实现了进程内异步事件的处理，尤其是GUI事件、服务端应⽤等；
提⾼了程序的运⾏效率。
三、同步与异步
3.1 同步的含义
同步，简单地说，就是调⽤⼀个过程时，假如过程还在执⾏状态，没有返回结果，那么在该过程返回之前，就不能继续做下⼀件事情。
举个例⼦来说，⽐如要先穿袜⼦再穿鞋，顺序不能颠倒，所以我概括同步的特点就是：顺序性、确定性、简易性。
顺序性，就是运⾏次序不会颠倒错乱，⼀切按顺序来；
确定性，就是运⾏顺序是确定的，可以预见的，就像数学的计算过程⼀样，最后的答案是确定的；
简易性，因为同步不牵涉到线程的概念，运⾏⼀个简单的单线程程序时，不会⽤到系统提供的线程同步机制（API）。
3.2 异步的含义
异步是相对于同步⽽⾔的，意思与同步相反。即调⽤⼀个过程时，就接着做下⾯的事情，不⽴即获得该过程的返回值。
打个⽐⽅，⽤微波炉加热⾷物，按下“启动”键，微波炉就开始运⾏了。这时，你不会去苦苦等待它加热，可以做其他的事情。等到听到⼀
声“叮”时，你知道加热完毕了，就会去拿出⾷物。
这⾥涉及到⼏个细节：你去⼲别的事、听到“叮”的⼀声就跑过去。
你去做别的事，那么现在⼀共有两件事正在做的过程当中，抽象成线程，就是两个线程在同时运⾏；
听到“叮”的⼀声就跑过去，说明过程返回了，但你并没有苦苦等这个过程返回，这个“返回”是巧妙的。
进程间通信和线程间通信的区别
因此，要实现异步，你得学会做两件事——添加新任务（创建线程），知道旧任务已经结束了并跑去处理（状态、通知和回调）。
3.3 实现异步的⽅法
创建线程可以通过调⽤API来实现，那么怎么知晓旧任务已经运⾏结束了呢？
状态，即设⼀共享变量（FLAG），旧任务结束时，变量置有效值，之后旧任务结束，新任务循环检测变量是否有效；
通知，即像下载软件⼀样，下载完，系统会通知你，即旧任务向新任务发通知或消息，发完之后，旧任务结束；
回调，就是把旧任务做完后要做的收尾⼯作交给旧任务本⾝，这样，旧任务做完收尾⼯作后便结束。
上述三种⽅法当中，“回调”，旧任务与新任务之间没有关系；“通知”，旧任务和新任务有直接联系；“状态”，旧任务和新任务有间接联系，通过状态变量。
回调时，新任务可以不管旧任务的事情；
通知时，新任务必须间断地等待是否有通知，如果有通知，就处理它。等待的时候，新任务⼀般处于阻塞状态；
状态时，新任务不必进⾏等待操作，它只需要适时检测（判断）这个状态变量是否有效（即是否为有效值）就可以了，这种⽅法也就是轮询。
四、并发与并⾏
4.1 并发的含义
当有多个进程在运⾏时，如果系统是单核的CPU，那它根本不可能真正地同时运⾏⼀个以上的进程。系统只能把CPU运⾏时间划分成若⼲个时间段（在每个时刻段的起始时刻使⽤调度算法分配任务），再将每个时间段分配给每个进程执⾏。在⼀个时间段内，某进程在运⾏时，其它进程处于挂起状态（就绪状态）。这种⽅式我们称之为并发（Concurrent）。
⾸先，上述讲到的进程调度就涉及到了进程并发。并发的精髓就是分配时间⽚，微观上是间断的，宏观上是连续的。假如系统⼀共有26个进程，在⼀个时间段内，只运⾏进程A，接着在下⼀个时间段内运⾏进程B，直到运⾏完进程Z，那么所有进程都被运⾏过了。进程被“重视”的标志就是它的CPU时间，时间多了，运⾏的就久，进度就越快。当前A-Z的顺序只是⼀个例⼦，在真实情况中很少出现这种情况。
上⾯的定义中，提到了单核的概念。
单核是和多核相区分的，可以这么理解，某时刻，单核CPU只能做⼀个任务，⽽多核CPU可以做多个任务。任务做的越多，任务的进度就越快速，系统完成任务的效率就⾼了。
还有⼀个概念是超线程（Hyperthreading Technology）。
超线程技术就是通过采⽤特殊的硬件指令，可以把两个逻辑内核模拟成两个物理超线程芯⽚，在单处理器中实现线程级的并⾏计算，同时在相应的软硬件的⽀持下⼤幅度提⾼运⾏效能，从⽽实现在单处理器
上模拟双处理器的效能。其实，从实质上说，超线程是⼀种可以将CPU内部暂时闲置处理资源充分“调动”起来的技术。
虽然采⽤超线程技术能够同时执⾏两个线程（如果每个进程同⼀时刻只能运⾏它的⼀个⼦线程的话，那就等同个能够同时执⾏两个进程），但它并不像两个真正的CPU那样，每个CPU都具有独⽴的资源。当两个线程都同时需要某⼀个资源时，其中⼀个要暂时停⽌，并让出资源，直到这些资源闲置后才能继续。因此超线程的性能并不等于两颗CPU的性能。
超线程与多核的区别主要取决于资源的独⽴性。当运⾏的这两个线程属于同⼀进程，那么对于超线程技术，就会遇到两个线程的资源发⽣冲突的情况；对于多核，就不会发⽣这种情况，因此两个线程在两个不同的CPU之中运⾏，纵使它们属于同⼀进程。
4.2 并⾏的含义
当系统有⼀个以上CPU（即多核）时，则线程的操作有可能不是并发的。当⼀个CPU执⾏⼀个线程时，另⼀个CPU可以执⾏另⼀个线
程，两个线程互不抢占CPU资源，可以同时进⾏，这种⽅式我们称之为并⾏（Parallel）。
并⾏是多核CPU的概念。并发是微观上间断，宏观上连续，⽽并⾏在微观上离“连续”更近了⼀步。
4.3 并发与并⾏的区别
并发与并⾏这两个概念很容易混淆。
并⾏是指两个或者多个事件在同⼀时刻发⽣；并发是指两个或多个事件在同⼀时间间隔内发⽣。
并发是单核CPU的产物，微观上间断，宏观上连续；并⾏是多核CPU的产物，微观上更连续，宏观上更连续。
以数硬币为例，总共⼀堆硬币。并发是⼀个⼈A数，并⾏是多个⼈B1-Bn数。
对A来说。选择⼀：从头到底埋头数；选择⼆：将硬币分成⼤致相同的N份，⼀会⼉数这⼀份，⼀会⼉数那⼀份。
对B来说。B将硬币分成⼤致相同的N份，因此B有N个⼈，所以这N个⼈分别数这N份硬币，由于⼈多⼒量⼤，所以B⽐A先数完。
A的选择⼀即为单道程序，选择⼆为多道程序即并发；B的选择即并⾏。
并⾏的程序⽐并发的程序效率⾼，资源利⽤率⾼，但编程更复杂，且结果不可预见，调试困难；
并⾏会有对资源的争夺，⽽并发不会（某时刻只有⼀个程序独占资源），因⽽并⾏会有互斥与同步问题，还有由此导致的死锁问题；
并发是单核CPU的产物，微观上间断，宏观上连续；并⾏是多核CPU的产物，微观上更连续，宏观上更连续。
4.4 死锁
4.4.1 死锁的定义
死锁的规范定义：集合中的每⼀个进程都在等待只能由本集合中的其他进程才能引发的事件，那么该组进程是死锁的。
4.4.2 死锁发⽣的四个必要条件
1. 互斥条件：指进程对所分配到的资源进⾏排它性使⽤，即在⼀段时间内某资源只由⼀个进程占⽤。如果此时还有其它进程请求资源，
则请求者只能等待，直⾄占有资源的进程⽤毕释放。
2. 请求和保持条件：指进程已经保持⾄少⼀个资源，但⼜提出了新的资源请求，⽽该资源已被其它进程占有，此时请求进程阻塞，但⼜
对⾃⼰已获得的其它资源保持不放。
3. 不剥夺条件：指进程已获得的资源，在未使⽤完之前，不能被剥夺，只能在使⽤完时由⾃⼰释放。
4. 环路等待条件：指在发⽣死锁时，必然存在⼀个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待⼀个P1
占⽤的资源，P1正在等待P2占⽤的资源，……，Pn正在等待已被P0占⽤的资源

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。