转载声明：文章来源https://www.cnblogs.com/bajdcc/p/4707544.html

实验要求

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占用的资源