操作系统进程篇（详解进程相关概念及调度算法）_可抢占处理机的优先调度算法进程状态图

操作系统进程篇（详解进程相关概念及调度算法）

1 进程概念简介

1.1 进程的定义

• 进程是程序的一次执行过程。
• 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
• 进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单元。

进程概略图：

1.2 进程的特征

• 动态性：进程是程序的一次执行，它有着创建、活动、暂停、终止等过程，具有一定的生命周期，是动态地产生、变化和消亡的。动态性是进程最基本的特征。
• 并发性：指多个进程实体同时存于内存中，能在一段时间内同时运行。并发性是进程的重要特征，同时也是操作系统的重要特征。引入进程的目的就是为了使程序能与其他进程的程序并发执行，以提高资源利用率。
• 独立性：指进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单元。凡未建立PCB的程序都不能作为一个独立的单元参与运行。
• 异步性：由于进程的相互制约，使得进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进。异步性会导致执行结果的不可再现性，为此在操作系统中必须配置相应的进程同步机制。
• 结构性：每个进程都配置一个PCB对其进行描述。从结构上看，进程实体是由程序段、数据段和进程控制块三部分组成的。

1.3 进程与线程的区别

• 进程是处于执行期的程序以及相关的资源的总称。
• 线程是进程中活动的对象，**内核的调度对象是线程，但调度级别仍然是进程级别。**当内核线程阻塞时，进程也阻塞，其它线程也阻塞。
• Linux下对线程和进程不作区分，线程是轻量级进程。
• 进程是资源分配的最小单位，线程是程序执行的最小单位（资源调度的最小单位）
• 进程有自己的独立地址空间，每启动一个进程，系统就会为它分配地址空间，建立数据表来维护代码段、堆栈段和数据段，这种操作非常昂贵。
  而线程是共享进程中的数据的，使用相同的地址空间，因此CPU切换一个线程的花费远比进程要小很多，同时创建一个线程的开销也比进程要小很多。
• 线程之间的通信更方便，同一进程下的线程共享全局变量、静态变量等数据，而进程之间的通信需要以通信的方式（IPC)进行。不过如何处理好同步与互斥是编写多线程程序的难点。

1.4 进程的状态与转换

• 运行态：进程正在处理机上运行。在单机处理机环境下，每个时刻最多只有一个进程处于运行态。
• 就绪态：进程获得了除处理机外的一切所需资源，一旦得到处理机，便可立即运行。系统中处于就绪状态的进程可能有多个，通常将他们排成一个队列，成为就绪队列。
• 阻塞态：又称等待态。进程正在等待某一事件而暂定运行，如等待某资源为可用或等待输入/输出完成。即使处理机空闲，该进程也不能运行。
• 创建态：进程正在被创建，尚未转到就绪态。创建进程通常需要多个步骤：首先申请一个空白的PCB，并向PCB中填写一些控制和管理进程的信息，然后由系统为该进程分配运行时所必须的资源，最后把该进程转入就绪态。
• 终止态：进程正从系统中消失，可能是进程正常结束或其他原因中断退出运行。进程需要结束运行时，系统首先必须置该进程为结束态，然后再进一步处理资源释放和回收等工作。

进程状态转换图：

2 进程的创建与调度

说起进程的创建与调度，不得不提一下进程的同步问题，进程的同步问题会直接影响操作系统的运行效率、运行时间，由于该问题所讨论的东西较多，就另写一篇博文来具体讲述。

进程的调度算法就先从处理机（CPU）的调度算法开始说起，还会大概讲解一下作业的定义及其调度算法。

2.1 处理机调度算法的目标

2.1.1 处理机调度算法的共同目标

1. 资源利用率。为提高系统资源的利用率，应使系统中的处理机和其它所有资源都尽可能的处于忙碌状态；其中CPU的利用率可以使用该式计算：

   CPU的利用率=CPU的有效工作时间/（CPU有效工作时间+CPU空闲等待时间）；

2. 公平性。公平性是指应使各个进程都获得合理的CPU时间，不会发生进程饥饿现象；但是公平是相对的，即同一类进程应获得相同的服务，但是不同类的进程由于进程的紧急程度或者重要性不同，则应区别对待；

3. 平衡性。系统中的资源多种多样，有的属于计算型作业，有的属于IO型，调度算法应使系统资源的使用保持平衡；

4. 策略强制执行。对于所制定的策略，如安全策略，只要需要，就必须准确地执行；

2.1.2 批处理系统的目标

1. 平均周转周期短。作业的周转周期是指从作业提交给系统到作业完成为止这段时间；周转周期通常由四部分组成：作业在外存上后备队列中的等待时间、进程在就绪队列中的时间、执行时间和等待IO操作等阻塞的时间；

   对于用户而言，希望自己的作业周转周期尽可能地短；对于系统而言，希望作业的平均周转周期短，这样不但有利于提高系统资源的利用率也可以使大多数用户满意；总的来说，应使作业的周转周期和平均周转周期都较短；

   平均周转周期T=(所有作业的周转周期之和)/作业总数；

   为了进一步反映调度的性能，更清晰地描述进程在其周转时间中等待和执行时间的具体分配状况，通常使用加权周转时间W，即作业的周转时间T与系统为它提供服务的时间Ts之比：W=T/Ts；平均加权周转周期为各个作业的加权周转时间之和/作业总数；

2. 系统吞吐量大。如果单纯为了提高系统的吞吐量，应尽量执行较短的作业运行；吞吐量被定义为单位时间里，系统完成的作业数；

3. 处理机效率高。由于CPU十分昂贵，使得处理机的利用率成为衡量系统性能的重要指标；而调度方式和调度算法由对处理机的利用率起着十分重要的作用。如果单纯提高处理机效率，那么应选择计算量大的作业运行。

2.1.3 分时系统的目标

1. 响应时间快。响应时间快是分时系统中调度算法的重要准则，所谓响应时间由三部分组成：命令输入时间、CPU处理时间、命令结果返回时间；
2. 均衡性。不同的用户对响应时间的要求不同，简单任务要求较短的响应时间，复杂的任务允许较长的响应时间，均衡性是指，系统的响应时间应该和用户所请求任务的复杂度相适应；

2.1.4 实时系统的目标

1. 对截止时间的保证。对实时系统而言，调度算法的一个主要目标就是保证实时任务对截止时间的要求；其中对HRT任务，需要调度方式和调度算法必须确保对截止时间的要求；对SRT任务，要求调度方式和调度算法基本可以保证对截止时间的要求；
2. 可预测性。在实时系统中，可预测性十分重要，主要是通过可预测性提高系统的实时性；

2.2 作业与作业调度

2.2.1 作业的定义

​ 作业是用户提交给系统的一项独立的工作。作业是比程序更加广泛的概念，其中包括程序、数据和作业说明书，系统根据作业说明书来对程序的运行进行控制；

2.2.2 作业控制块（JCB）

1. 引入作业控制块的目的：管理和调度作业，系统为每个作业设置一个作业控制块JCB，它是作业在系统中存在的标记；
2. 作业控制块的内容：它保存了系统对作业进行管理和调度所需要的全部信息。这些内容有：作业标记、用户名称、用户账号、作业类型（CPU型繁忙型、IO型、批量型、终端型）、作业状态、调度信息（优先级、作业运行时间）、资源需求（预计运行时间、内存大小等）、资源的使用状况等；

2.2.3 作业运行的三种状态

1. 收容状态。操作员将作业输入到硬盘上，为其建立JCB，将其放入作业后备队列中，等待调度，此时的状态称为收容状态；此时作业在外存上；
2. 运行状态。作业被调度算法选中，为其分配了所需要的资源并建立了进程，将其进程插入到就绪队列中。从作业第一次进入就绪队列开始到作业完成，作业均处于运行状态；
3. 完成状态。当作业完成、或者发生异常情况而提前结束时，作业将进入完成状态，系统中的相应程序将回收分配的资源和JCB，并将作业运行的结果输出；

2.2.4 作业调度的主要任务

作业调度的主要任务就是根据JCB中的内容，检查系统资源情况是否满足作业的要求，并按照一定的调度算法，从外存的后备队列中选择某些作业调入内存，为它们创建进程、分配资源，然后将进程插入到就绪队列中等待调度；其实归根到底需要解决两个问题：

1. 接纳多少个作业

   这是由系统的多道程序度（Degree of Multiprogramming）决定的，即允许多少个作业同时出现在内存中；对系统而言，当然希望装入较多的作业以提高CPU的利用率和系统的吞吐量，但是内存中的作业过于多时，由于内存不够而引发的中断就会急剧增加，从而影响系统效率和服务质量；因此，多道程序度是由计算机系统的规模、运行速度、作业大小、以及能否获得较好的系统性能等确定的；

2. 接纳那些作业

   最简单的调度算法是先到先服务算法；较常见的一中调度算法是短作业优先算法；另一种常见的算法是基于作业优先级的调度算法；比较好的调度算法是响应比高者优先算法；

2.3 进程调度

2.3.1 进程调度的任务

进程调度的主要任务有三：

1. 保留处理机线程。将当前进程的处理机现场记录到PCB中，包括程序计数器、多个通用寄存器的内容；
2. 按照某种算法选择下一个执行的进程。调度程序将从就绪队列中选择一个进程，改变其运行状态，将处理机分配给它；
3. 将处理机分配给进程。由分派程序将处理机分配给该进程，此时需要将对应的PCB中的内容装入相应的寄存器内，让其从上一次中断的地方开始执行；

2.3.2 进程调度机制

为实现进程调度，进程调度机制中，应具有以下三个部分：排队器、分派器和上下文切换器；

1. 排队器的主要任务是将就绪状态的进程组织为一个或多个队列，以便调度程序可以可以快速找到它；每当一个进程转入就绪状态，排队器就把它插入到相应的就绪队列；
2. 分派器的主要任务是将调度程序所选择的进程从就绪队列中取出来，然后进行从分派器到新进程的上下文切换；
3. 上下文切换器的主要任务是，在发生进程切换时，首先将当前进程的相关信息存储到对应的PCB中，然后装入分派程序；然后将分派程序的上下文移出，装入新进程的处理机信息；即一次进程切换中，发生了两次处理机上下文的切换；

由于一次上下文切换中需要执行大量的load和store命令，所以比较费时，现代系统以实现靠硬件来减少上下文切换时间；当然也可以采用两组寄存器，其中一组寄存器供处理机在系统态时使用，另一组寄存器供应用程序使用。这样只需改变指针即可实现上下文的切换；

2.3.3 进程调度的方式

早期系统大多采用非抢占式调度方式，但是这很难满足交互性作业和实时任务的需求，后来在进程调度方式中又引入了抢占式调度方式；

1. 非抢占式调度

   非抢占式调度方式中，一旦把处理机分配给某个进程，就让它一直运行下去，绝不会因为时钟中断或其他原因而抢占当前正在运行进程的处理机，直到该进程完成或者因某事件而阻塞，才将处理机分配给其他进程；非抢占方式中，引起进程调度的原因有：

   1. 正在执行的进程正常结束，或者因为某事件而无法继续执行；
   2. 正在执行的进程提出IO请求而暂停执行；
   3. 在进程同步和通信中，执行了某种原语操作，如挂起原语等；

   这种调度方法的特点是系统开销小，简单，适合大多数批处理系统，但是不能用于分时系统和实时系统；

2. 抢占式调度

   抢占式调度中，允许调度程序按照某种原则，暂停某个正在执行的进程；将已分配给该进程的处理机分配给另一进程；现代OS中广泛采用抢占式调度，这是因为，抢占式调度方法可以防止一个长进程长时间占用CPU，以确保处理机能为各个进程提供更为公平的服务，另外在分时系统中，只有抢占式调度才能实现人-机交互。实时系统中，抢占式可以满足实时任务的要求。但是抢占式实现起来比较复杂，系统开销较大；

   抢占不是一种任意的行为，它必须遵守一定的规则：

   1. 优先权原则：只有优先级高的进程才能抢占优先级低的进程的处理机，反之不行；
   2. 短进程优先原则：当新来进程所要求的服务时间明显少于当前执行进程还需要执行的时间时，发生抢占；
   3. 时间片原则：各进程按时间片轮转执行时，当正在执行的进程的一个时间片用完后，便停止该进程的执行；

3 调度算法

了解了基本概念之后，咱们可以来讨论调度算法了，调度算法对于进程、线程、作业都有共通之处，在于如何理解并使用调度算法。如果学的很好的话，可以选择性地更改调整调度算法已达到我们的目的。对于调度算法，我会给出两个C++程序来模拟进程调度算法。耐心看完哦！你会有很多收获的.

3.1 先来聊聊作业的调度算法

3.1.1 先来先服务算法（FCFS，First-Come First-Served）

FCFS调度算法中，优先选择先到的作业或者进程进行服务，或者说，它选择的是在队列中等待时间最长的作业或者进程，而没有考虑作业自身的情况，比如作业的优先级、作业的预计运行时间等；基本上FCFS算法很少作为系统的主调度算法，但经常把它和其他调度算法相结合使用。

该调度算法既可以用于作业调度也可以用于进程调度（即适用于长程调度和短程调度）；

3.1.2 短作业优先调度算法（SJF，Short-Job First）

短作业优先算法使用作业或者进程的长短来标记它们的优先级，越短的作业（进程）其优先级越高；

短作业优先调度算法相比先来先服务算法有了明显的感改进（考虑了作业或者进程自身的相关信息），但是仍然有缺点：

1. 必须预知作业的运行时间，这不是很容易做到，如果估计偏低，那么系统可能会提前终止作业，而作业此时尚未完成；所以一般都偏长估计；
2. 对长作业非常不利，一个极端的现象就是长作业根本得不到运行，即系统中总是有比该作业更短的作业，从而出现饥饿现象；即便在普通情况下，长作业的周转周期也会明显增长；
3. 无法实现人机交互（需要交互的程序得不到运行）；
4. 没有考虑作业的紧急程度，不能保证紧迫的作业得到及时的处理；

本博文后面会持续更新，短作业后面会给出相关的C++模拟进程多作业调度算法实现案例。

该调度算法既可以用于作业调度也可以用于进程调度；

3.1.3 优先级调度算法（PSA，Priority-Scheduling Algorithm）

​ 优先级调度算法中选择作业或者进程的标准是它们的优先级，优先级越高，越早获得调度而执行；其实FCFS中，作业或者进程的等待时间就相当于其优先级；SJF中，作业的长度就相当于其优先级；但是这种优先级并不能反映作业或者进程的紧急程度；PSA算法就是要保证紧迫性任务得到优先运行；

该调度算法既可以用于作业调度也可以用于进程调度；

3.1.4 高响应比优先调度算法（HRRN，Highest Response Radio Next）

​ FCFS算法中，只考虑作业或者进程等待的时间；SJF算法中，只考虑了作业或者进程的运行时间；高响应比优先调度算法既考虑了等待时间也考虑了作业或者进程的要求时间；是一种动态优先级设定；其优先权计算公式：优先权=（要求服务的时间+等待时间）/要求服务的时间；这样，当两个作业或者进程等待了相同时间时，短作业将获的较大的优先级，类似SJF调度方式；当两个进程要求服务时间相同时，等待时间长的作业将获得较大的优先级，类似于FCFS调度方法；这种调度方法的问题就在于每次进行调度时需要进行响应比的计算，于是会增加一定的系统开销；

后面会给出高响应比优先调度算法的C++模拟进程调度案例。可以看看下面的时间片轮转调度算法及优先级调度算法的C++程序案例。

3.2 然后聊聊进程的调度算法

3.2.1 轮转调度算法（RR，Round Robin）

分时系统中最简单也是最常用的算法；该方式采用非常公平的处理机分配方法，即采用FCFS策略组织就绪队列，让就绪队列中的每一个进程每次都运行一个时间片；这种方法中，进程的切换发生在：

1. 若时间片尚未用完，正在执行的进程便已完成，就立即激活调度程序；将其从就绪队列中删除，从就绪队列中选择队首进程运行，同时启动一个新的时间片；
2. 若时间片用完，计时器中断处理程序被激活；如果进程尚未运行完毕，就把它送入就绪队列的末尾，重新排队；(注：我给的程序并未进行重新排列，而是通过判断所剩运行时间来进行判断该进程是否已结束，如果结束，该进程不在执行，与重新排队的思路差不多)。

下面给出一个C++程序模拟轮转调度算法，进程是由结构体进行模拟。

/*通过C++程序模拟进程通过时间片轮转调度算法进行调度*/
#include<iostream>
#include<string>
#include<stdio.h>
#include<windows.h>
#include<ctime>
using namespace std;
typedef struct pcb {
	string pName;//进程名
	struct pcb *next;//指向下一个进程
	float arriveTime;//到达时间
	float serviceTime;//服务时间
	float estimatedRunningtime;//估计运行时间
	float startTime;//开始时间
	float finishTime;//完成时间
	float turnaroundTime;//周转时间
	float weightedTuraroundTime;//带权周转时间
	char state;//进程的状态
}PCB;

void createProcess(PCB *p, int n) {//创建n个进程，带头结点
	cout << endl << endl << "创建进程" << endl;
	PCB *q = p;//工作指针的前一个结点指针
	PCB *r = new PCB;//工作指针
    srand((unsigned int)time(NULL));
	for (int i = 0; i<n; i++) {
		r ->pName = 'A'+i;
		r->arriveTime = rand()%10 + 1; //通过随机函数随机生成到达时间时间与服务时间，也可改为手动输入
        r->serviceTime = rand()%10 + 1;
        cout<<"进程名 "<<r->pName<<" 到达时间 "<<r->arriveTime<<" 服务时间 "<<r->serviceTime<<endl;

		r->startTime = 0;
		r->finishTime = 0;
		r->estimatedRunningtime = r->serviceTime;
		r->turnaroundTime = 0;
		r->weightedTuraroundTime = 0;
		r->state = 'R';
		q->next = r;
		q = r;
		r->next = new PCB;
		r = r->next;
	}
	r->next = NULL;
	q->next = NULL;
	q = NULL;
	delete q;
	delete r;
	cout << endl << endl;
}

void sortOfArriveTime(PCB *p, int n) {//按到达时间对进程排序
	PCB *t = new PCB;
	PCB *q = new PCB;
	PCB *m = new PCB;
	for (int i = 0; i<n - 1; i++) {//冒泡循环
		q = p->next;//q指向链表中的第一个进程
		for (int j = 0; j<n - i - 1; j++) {
			m = q->next;
			if (q->arriveTime>m->arriveTime) {//结点信息进行交换
				t->pName = q->pName;
				t->arriveTime = q->arriveTime;
				t->serviceTime = q->serviceTime;
				t->estimatedRunningtime = q->estimatedRunningtime;
				q->pName = m->pName;
				q->arriveTime = m->arriveTime;
				q->serviceTime = m->serviceTime;
				q->estimatedRunningtime = m->estimatedRunningtime;
				m->pName = t->pName;
				m->arriveTime = t->arriveTime;
				m->serviceTime = t->serviceTime;
				m->estimatedRunningtime = t->estimatedRunningtime;
			}
			q = q->next;
		}
	}
	t = NULL;
	m = NULL;
	q = NULL;
	delete t;
	delete m;
	delete q;
}

void runProcess(PCB *p, int n) {//运行进程
	PCB *q = new PCB;
	PCB *m = new PCB;
	PCB *s = new PCB;
	int a = n;
	sortOfArriveTime(p, n);
	q = p;
	m = p->next;
	int currentTime = 0;//定义当前时间
	int i = 0;
	int number = 0;
	int counNum = 0;
	while (true) {
            //运行五次暂停一次
        if(counNum==5){
            getchar();
            counNum=0;
        }else{
            counNum++;

        }
		currentTime++;
		if (i == 0 && m->arriveTime>currentTime)//首次运行进程
			continue;
		number = 0;
		while (m&&m->state == 'C' || m&&m->arriveTime>currentTime) {//寻找应该访问的进程
			number++;
			q = m;
			m = m->next;
			if (m == NULL) {
				q = p;
				m = p->next;
			}
			if (number>n)
				break;
		}
		if (number>n)//所有进程都不能进行访问
			continue;
		cout << "正在运行的进程" << endl;
		cout << "当前时间:" << currentTime << endl;
		cout << "进程名\t到达时间 服务时间 已运行时间 还剩运行时间" << endl;//输出当前正在运行的进程
		cout << m->pName << "\t" << m->arriveTime << "\t " << m->serviceTime << "\t  ";
		cout << m->serviceTime - m->estimatedRunningtime << "\t     " << m->estimatedRunningtime << endl;
		m->estimatedRunningtime--;
		m->finishTime = currentTime + 1;
		if (m->estimatedRunningtime == 0)
			m->state = 'C';
		cout << "进程" << m->pName << "执行一次之后就绪队列中的进程" << endl;
		cout << "进程名\t到达时间 服务时间 已运行时间 还剩运行时间" << endl;
		s = p->next;
		while (s) {//输出就绪队列
			if (s->estimatedRunningtime > 0) {
				cout << s->pName << "\t" << s->arriveTime << "\t " << s->serviceTime << "\t  ";
				cout << s->serviceTime - s->estimatedRunningtime << "\t     " << s->estimatedRunningtime << endl;
			}else{
			    cout<<s->pName<<" was finished"<<endl;
			}
			s = s->next;
		}
		Sleep(500);
		cout << endl << endl << endl;
		q = m;
		m = m->next;//q、m指针后移
		if (m == NULL) {//回到链表头部
			q = p;
			m = p->next;
		}
		s = p->next;
		while (s&&s->state == 'C')
			s = s->next;
		if (s == NULL)//若所有进程已完成，则退出循环
			break;
		i++;
	}
	q = p;
	m = p->next;
	for (int i = 0; i<n; i++) {//计算开始时间、周转时间、带权周转时间
		if (i == 0) {
			m->startTime = m->arriveTime;
			m->turnaroundTime = m->finishTime - m->arriveTime;
			m->weightedTuraroundTime = m->turnaroundTime*1.0 / m->serviceTime;
		}
		else {
			m->startTime = q->startTime + 1>m->arriveTime ? q->startTime + 1 : m->arriveTime;
			m->turnaroundTime = m->finishTime - m->arriveTime;
			m->weightedTuraroundTime = m->turnaroundTime*1.0 / m->serviceTime;
		}
		m = m->next;
	}
	q = NULL;
	m = NULL;
	s = NULL;
	delete q;
	delete m;
	delete s;
	cout << endl;
}

void printProcess(PCB *p) {//输出所有进程的信息
	PCB *q = p->next;
	cout << endl << "所有进程运行完成后进程的相关信息" << endl;
	cout << "进程名\t到达时间 服务时间 开始时间 完成时间 周转时间 带权周转时间" << endl;
	while (q) {
		cout << q->pName << "\t" << q->arriveTime << "\t " << q->serviceTime << "\t  ";
		cout << q->startTime << "\t   " << q->finishTime << "\t    " << q->turnaroundTime << "\t     " << q->weightedTuraroundTime << endl;
		q = q->next;
	}
	cout << endl << endl;
}

//主程序入口
int main() {
	PCB *p = new PCB;
	int n;
	cout << "请输入进程的个数:";
	cin >> n;
	createProcess(p, n);
	runProcess(p, n);
	printProcess(p);
	getchar();
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206

时间片大小的选取对系统性能有着很大的影响；若选择小的时间片，那么短作业则可能在一次时间片中就结束运行，但是时间片过小，那么系统将频繁发生进程调度和处理机上下文切换，增加系统开销；反之，若时间片太长，则RR退化为FCFS，无法满足短作业和交互式作业的需求；一个可取的策略就是时间片大小应略大一一次交互所需要的时间，这样使大多数交互式作业可以在一个时间片里完成，从而获得较小的响应时间；

3.2.2 优先级调度算法

优先级调度算法中，将处理机分配给就绪队列中优先级最高的进程。按照是否允许抢占，分为抢占式和非抢占式；

1. 非抢占式优先级调度算法

   该算法中，一旦将处理机分配给就绪队列中优先级最高的进城后，该进程便一直执行下去，直到结束（正常结束或者被阻塞、挂起等）才将处理机分配给就绪队列中另一优先级最高的进程；

2. 抢占式优先级调度算法

   该算法中，把处理机分配给优先级最高的进程，使之执行，但是如果在其执行期间出现优先级更高的进程，调度程序就将处理机分配给新的优先级最高的进程；抢占式优先级调度算法常用于对实时性要求较高的系统中；

这里给出一个C++程序模拟优先级调度算法

/*C++程序模拟优先级调度算法*/
#include"stdio.h"
#include"stdlib.h"
#include "string.h"
#include "ctime"
#include <iostream>
#include<stdlib.h>
#include<windows.h>
#define WAIT 1
#define RUN 2
#define FINISH 3
using namespace std;
typedef struct pcb
{
  int num;
  struct pcb *next;
  int priority;//优先级
  int timeneed;//运行时间
  int state;//状态
}pcb;/*用此结构体来模拟一个进程*/

struct pcb *head;
struct pcb *run;

pcb *jccreat(int n)/*此函数用于创建进程队列*/
{
 int i=1;
 pcb *head,*p,*q;
 head=(pcb *)malloc(sizeof(pcb));/*创建一个空表头*/
 p=head;
 //获取系统时间，用于随机函数，如果放到for循环里里面，则会导致生成的随机函数相同
 srand((unsigned int)time(NULL));//
 for(i=1;i<=n;i++)/*用循环来创建指定个结点*/
 {

  q=(pcb *)malloc(sizeof(pcb));
                p->next=q;
  q->num=i;
  q->next=NULL;

  q->priority=1+(10*rand()/(RAND_MAX+1.0));/*随机产生优先级*/
  q->timeneed=1+(100*rand()/(RAND_MAX+1.0));/*随机产生运行时间*/
  q->state=WAIT;
  p=q;
 }

 return head;/*返回表头指针*/
}

pcb *getmaxpriority(struct pcb *head)/*此函数用来挑选一个优先级最大的进程来执行*/
{
  struct pcb *p,*q;
  int max;
  p=head->next;
  max=p->priority;/*初始max为队首结点的优先级*/
  q=p;
  while(p)
  {
   if(p->priority>max)/*逐一比较，选出优先级最大的结点*/
   {max=p->priority;
    q=p;}
   p=p->next;
  }
  return q;
}

void delect(struct pcb *head,struct pcb *run)/*此函数用来将运行完的进程删除出进程队列*/
{
	struct pcb *q=head;

	while(q->next)/*扫描进程队列，找到执行完了的进程*/
	{
		if(q->next->num==run->num)/*判断是不是已完成的进程*/
		{
			if(run->next!=NULL)
				q->next=run->next;
			else q->next=NULL;
			free(run);/*释放申请的空间*/
			return;
		}
	q=q->next;
	}

}
int i=0;
void control()/*此函数是用来控制各个进程的执行和调度*/
{
	struct pcb *p;
	run=head->next;/*初始让第一个进程运行*/
	run->state=RUN;
	while(run)
	{
		if(run->timeneed>0)/*如果当前run指针指向的进程所需时间不为零，状态为运行状态，就让这个进程运行*/
		if(run->state==RUN)
		{
			printf("pcb%d is running.\n",run->num);
			printf("Waiting list:");/*显示整个等待队列*/
			p=head->next;
			while(p)//遍历其他未运行的在队列之中的进程
			{
				if(p!=run)
				printf("pcb%d  ",p->num);
				p=p->next;
			}
			printf("\n");
			Sleep(500);/*模拟进程运行*/
			if(run->timeneed>10)
				run->timeneed=run->timeneed-run->timeneed/10;/*进程需要时间减少*/
			else
				run->timeneed--;
			run->priority=run->priority-1;/*进程优先级减1*/
			cout<<run->timeneed;
			cout<<"\t";
			cout<<run->priority;
			cout<<"\n";
			if(i==5)
			{ i=0;
			  getchar();}
			else
			  i++;
			}

			if(run->timeneed!=0)
			{

				if(run->priority<=getmaxpriority(head)->priority)/*如果当前运行完的进程的优先级低于队列中优先最大的优先权时，切换到该最大优先级进程*/
				{	run->state=WAIT;
					run=getmaxpriority(head);/*则从进程队列中挑选一个优先级最大的进程来运行*/
					run->state=RUN;}
			}
			else
            { printf("pcb%d is finished.\n",run->num);
              Sleep(500);
              delect(head,run);/*删除该结点*/
              if(head->next!=NULL)/*判断进程队列是不是为空*/
              {run=head->next;
              run->state=RUN;}
              else
              {
printf("All progresses are done.\n");
               		return;
}
             }
       }
}

int main()
{
	int n;
	int flag=1;

	printf("Enter the number of the progresses:");
	scanf("%d",&n);/*输入要创建的进程的数量*/

	head=jccreat(n);/*创建进程队列，将链表的表头赋给head指针*/
	run=head->next;/*run指针指向正在运行的进程的pcb*/
	while(run)
	{
		printf("num: %d ,priority: %d ,timeneed: %d \n",run->num,run->priority,run->timeneed);
 		run=run->next;
	} /*将刚创建的进程队列打印出来*/
	while(flag)/*由flag的值判断是否继续执行control()函数*/
	{
		if(head->next)/*判断进程是否完成*/
			control();
		else flag=0;
	}
	getchar();
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171

优先级的类型——静态优先级和动态优先级：

1. 静态优先级在创建进程的时候就已经设定，其运行周期内不再改变；常使用0-255中的一个整数来表示其优先级大小；设定静态优先级时需要考虑进程的类型，通常系统进程的优先级高于用户进程的优先级；进程对于资源的需求量，一般来说，需求量小的具有较高的优先级；用户的要求；静态优先级实现较为简单，系统开销小，但是不够精确，可能出现优先级低的进程长时间得不到运行的情况；
2. 动态优先级是指进程的优先级会随着其运行发生改变，常见的需要考虑的变量有进程的初始优先级和等待时间等；

3.2.3 多队列调度算法

多列调度算法中，将就绪队列组织为多个按照不同调度算法调度的就绪队列，以满足不同用户对调度策略的不同要求，并且这些就绪队列本身也可以设定优先级，方便在多处理机系统中为每个处理机设置一个单独的就绪队列；避免了仅有一个就绪队列时调度算法的固定、单一。这样对于含有多个线程的进程，可以将这些线程分配在一个就绪队列中，全部在一个处理机上运行；对于一组需要相互合作的进程而言，可以将其安排在一组处理机所对应的多个就绪队列中，使它们可以同时获得处理机并发执行；

1. 多级反馈队列调度算法（Multileved feedback queue）

   前面介绍的进程调度算法，或多或少都有一定的局限性，如果未能指明进程的长度，则短进程优先和基于进程长度的抢占式调度算法都将无法使用。多级反馈队列不用提前知道各种进程的执行时间，还可以较好地满足各种类型进程的需要，是目前公认的一种较好地进程调度算法；它的核心为

   1. 设置多个就绪队列；系统中设置多个就绪队列，并且每个就绪队列也有自己的优先级。第一个队列的优先级最高，以此降低；该算法为每个队列中的进程所分配的时间片大小也是不同的，优先级越高的队列，其所分配的时间片越小（便于进程向低优先级转移）；
   2. 每个队列都采用FCFS算法。当新进程进入内存时，将其放入第一队列的末尾，然后按照FCFS等待调度；如果该进程在时间片内完成，便撤离系统；否则进入第二队列末尾等待调度；当进程进入最后一个队列时，便采用RR方式运行；
   3. 按照队列优先级调度。调度程序首先调度最高优先级队列中的进程运行，仅当第一队列空闲时才调度第二队列中的进程；如果处理机正在第x队列中为某进程服务时，有新进程进入任意优先级较高的队列，那么该进程立即被送回第x队列末尾，将处理机交给新到的高优先级进程；

   多级反馈队列中，可以使短作业较早的完成，而且长作业经过第1,2,3…队列的执行，到最后一个队列时，采用RR调度算法，也不用担心过其作业长期得不到处理；

2. 基于公平原则调度算法

   以上几种调度算法，保证了优先运行，但是并不能保证作业占用多少处理时间。另外也没有考虑调度的公平性；这里有两种相对公平的调度算法

   1. 保证调度算法，它向用户所做出的保证不是优先运行而是明确的性能保证，一种比较容易实现的性能保证算法是处理机分配的公平。如果系统中有n个进程，那么需要保证每个进程都获得相同的处理机时间1/n；实施公平调度算法时，系统需要：

      1. 跟踪计算每个进程自创建以来已执行的时间；
      2. 计算每个进程应该获得的处理机时间；
      3. 计算进程获得处理机时间的比率；
      4. 比较各个进程的这个比率，然后选择最小的进程，将处理机分配给它，并让该进程一直运行下去，直到超过最接近它的进程比率为止；

   2. 公平分享调度算法

      公平的角度不同，所使用的算法也就不同；保证调度算法对进程是公平的，但是对用户就不一定：有的用户拥有的进程多，有的用户拥有的进程少。公平分享算法是用户层面的公平调度算法。

4、结语

今天是20201024，所以发一篇高质量的博文，耗费了我不少时间，希望能帮助爱学习的人更快更深层次的了解进程相关概念及其调度算法，这篇博文还未达到我预期的效果，后面会逐渐完善更新。