进程的优先级算法和时间片段轮转算法（C++实现）

• 前言
• 一、进程优先级调度算法
• 二、时间片轮转调度算法
• 三、示例代码（注意：优先级调度算法是采用非抢占算法）
• • 1.引入库
  • 2.读入数据
  • 3.输出用例
• 四、总结

提示：了解进程优先级算法和时间片轮转算法的基本原理再进行代码学习。

提示：以下是本篇文章正文内容，下面案例可供参考

1. 基本原理：
   按照进程的优先级高低来进行调度，使高优先级进程优先得到处理机的调度算法称为优先级调度算法（即优先级数值大的先进行调度）。但在许多采用优先级调度算法的系统中，通常使用动态优先级。一个进程的优先级不是固定的，可能会随许多因素的变化而变化，例如，进程的等待时间、已使用的处理机时间或其他资源的使用情况。

2. 优先级调度算法又可分为下述两种：
   ①非抢占式的优先级调度算法。一旦某个高优先级的进程得到处理机，就一直运行下去，直到由于其自身的原因（任务完成或等待事件）而主动让出处理机，才让另一个高优先级进程运行。
   ②抢占式的优先级调度算法。任何时刻都严格按照优先级高的进程在处理机上运行的原则进行调度，或者说，在处理机上运行的进程永远是就绪进程队列中优先级最高的进程。在进程运行过程中，一旦有另一个优先级更高的进程出现（如一个高优先级的等待状态进程因事件的到来而成为就绪状态），进程调度程序就迫使原运行进程让出处理机给更高优先级的进程使用，或称为抢占处理机。

3. 例题
   (1)非抢占式
   各进程到达就绪队列的时间、需要的运行时间、进程优先数如下表所示。使用非抢占式的优先级调度算法，分析进程运行情况。(优先数越大，优先级越高)

   调度过程：正在处理的进程处理结束，接下来每次调度时选择当前已到达且优先级最高的进程。

4. 
   注:以下括号内表示当前处于就绪队列的进程
   0时刻(P1):只有P1到达，P1上处理机。 7时刻(P2、P3，P4):P1运行完成主动放弃处理机，其余进程都已到达，P3优先级最高，P3上处理机。8时刻(P2、P4):P3完成，P2P4优先级相同，由于P2先到达，因此P2优先上处理机。
   —————————————
   
   （2）抢占式
   各进程到达就绪队列的时间、需要的运行时间、进程优先数如下表所示。使用抢占式的优先级调度算法，分析进程运行情况。(优先数越大，优先级越高)
   调度过程：每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。就是在运行进程的过程中，放弃当前进行，去进行优先级高的进程。
   —————————————
   
   0时刻(P1):只有P1到达，P1上处理机。
   2时刻(P2):P2到达就绪队列，优先级比P1更高，发生抢占。P1回到就绪队列，P2上处理机。
   4时刻(P1、P3):P3到达，优先级比P2更高，P2回到就绪队列，P3抢占处理机。
   5时刻(P1、P2、P4):P3完成，主动释放处理机，同时，P4也到达，由于P2比P4更先进入就绪队列，因此选择P2上处理机
   7时刻(P1P4):P2完成，就绪队列只剩P1、P4，P4上处理机。11时刻(P1):P4完成，P1上处理机
   16时刻():P1完成，所有进程均完成
   —————————————
   

1. 基本原理：
   根据先来先服务的原则，将需要执行的所有进程按照到达时间的大小排成一个升序的序列，每次都给一个进程同样大小的时间片，在这个时间片内如果进程执行结束了，那么把进程从进程队列中删去，如果进程没有结束，那么把该进程停止然后改为等待状态，放到进程队列的尾部，直到所有的进程都已执行完毕

2. 进程的切换
   时间片够用：意思就是在该时间片内，进程可以运行至结束，进程运行结束之后，将进程从进程队列中删除，然后启动新的时间片
   时间片不够用：意思是在该时间片内，进程只能完成它的一部分任务，在时间片用完之后，将进程的状态改为等待状态，将进程放到进程队列的尾部，等待cpu的调用。

3. 关于时间片大小的选择
   时间片过小，则进程频繁切换，会造成cpu资源的浪费
   时间片过大，则轮转调度算法就退化成了先来先服务算法。

4. 例题
   1.完成下列表格
   
   2.解析：
   进程处理的流程(P=1) :

代码如下（示例）：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;


///PCB控制块信息
typedef struct PCB
{
    int id;                     ///进程id
    int priority;               ///进程优先级
    int status;                 ///进程状态 0：就绪 1：运行
    int ptime;                  ///进程到达时间 		// 上一个进程的完成时间 = 这个进程的开始时间
    int start;                  ///开始运行时间
    int finish;					///完成时刻时间          //完成时间 = 开始时间 + 运行时间
    int runtime;                ///进程运行时间
    bool operator< (const PCB &t) const
	{
		if( ptime != t. ptime) return  ptime < t. ptime;
		return runtime < t.runtime;
	};
}PCB;


///就绪队列
typedef struct ReadyNode
{
    PCB data;                  				 ///已就绪的进程id
    ReadyNode *next;            			///用next来指向下一个进程
};

PCB pcb[100];								///结构体PCB数组，用来存放已经创建PCB控制块,即处于就绪状态
int N = 0;									///记录当前已经创建的进程数目
typedef struct ReadyNode *Ready; 			///定义一个 ReadyNode 指针方便后续的应用


const int M = 100;	//最长100个时间单位 
PCB pcb_list[100];	//进程列表
vector table[M];	//进程时刻表
queue que;		//进程队列
int n,t,q,sjp;	//进程数，总计时，固定时间片，运转时间片
int max_time;	//最大时间


///判断进程是否已创建,如果存在则返回 1，否则返回 0.
int isOrNot(int num)
{
    for(int i = 0;i < N;i++)
    {
        if(num == pcb[i].id)
        {
            cout << "该进程已创建！" << endl;
            return 1;
        }
    }
    return 0;
}


///创建进程：申请PCB,填入进程参数
int Create()
{
	
    int num;
    int i = 0;
	cout << "请输入你的进程数" << endl;
	cin >> N;
    ///如果要申请的进程数大于当前系统的内存,直接结束该功能
    if( N >100)
    {
        cout << "当前内存已满!" << endl;
        return 0;
    }
	while(i < N )
	{

	    cout << "输入要创建的进程的id：" ;
	    cin >> num;
	    getchar();
	
	    while( isOrNot( num ) == 1 ) ///判断输入的 id 是否存在在进程中，如果存在，则重新输入。
	    {
	        cout << "请重新输入：";
	        cin >> num;
	        getchar();
	    }
	
	    pcb[i].id = num;
	
	    cout << "输入要创建的进程的优先级：";
	    cin >> pcb[i].priority;
	    getchar();
	
	    cout << "输入进程到达时间：";
	    cin >> pcb[i].ptime;
	    getchar();
	
	    cout << "输入进程运行时间：";
	    cin >> pcb[i].runtime;
	    getchar();
	
	    pcb[i].status = 0;              /// 把进程的状态设置为就绪状态。
	    //pcb[N].start = pcb[N].ptime;   /// 把 进程的到达时间 作为 进程开始运行 的起点
	    i++;                       			/// 创建一个进程 i + 1；
	    cout << "创建成功!" << endl;
    }
    return 0;
}


///初始化就绪队列gg
Ready init()
{
    Ready head;
    head = (Ready)malloc( sizeof(struct ReadyNode) );
    head->next = NULL;
    return head;
}

///按到达时间对进程进行排序 ( 到达时间 从小到大 进行排序 )
/// 即 第一个进程 的到达时间比第二个进程的到达时间大，需要先执行先到达的进程，慢来的进程往后放。
int ptime()
{
    PCB temp;
    for(int i = 0;i < N - 1;i++)      				// 嵌套循环进行比较，到达时间小的放前面。
    {
        for(int j = i + 1;j < N;j++)
        {
            if( pcb[j].ptime < pcb[i].ptime)
            {
                temp = pcb[i];
                pcb[i] = pcb[j];
                pcb[j] = temp;
            }
        }
    }
    return 0;
}


///按优先级调用
int Prioritycall(Ready r)
{
	Create();
    int end;
    PCB temp;
    Ready p = r;

    if(r == NULL)
    {
        cout << "当前无可调用进程！" << endl;
        return 0;
    }

    ptime();   /// 必须先按到达时间进行排序后才能进行优先级调度算法，不然有些进程优先级高，
                /// 但没有到达

    pcb[0].start = pcb[0].ptime;            /// 先把第一个进程的到达时间作为最开始的到达时间。
    end = pcb[0].start + pcb[0].runtime;    /// end 表示该进程的结束时间

    for(int i = 1;i < N-1;i++)    	//从第二个开始找 找到优先级数最大的那个，依次从大到小排列
    {
        for(int j = i+1;j < N;j++)
        {  /// 注意这里多一个条件：这个进程的到达时间必须小于上个进程的结束时间，不符合就下一个进程
            if( pcb[i].priority < pcb[j].priority && pcb[j].ptime <= end )
            {
                temp=pcb[i];
                pcb[i]=pcb[j];
                pcb[j]=temp;
            }
        }
        end += pcb[i].runtime;
    }

  for(int i=0;i
        pcb[i].status=1;
        p->next=(Ready)malloc(sizeof(struct ReadyNode));
        p->next->data.id=pcb[i].id;
        p->next->data.priority=pcb[i].priority;
        p->next->data.ptime=pcb[i].ptime;
        p->next->data.status=pcb[i].status;
        p->next->data.runtime=pcb[i].runtime;
        if(i==0){
            pcb[i].start=pcb[i].ptime;
        }else{
            pcb[i].start=pcb[i-1].start+pcb[i-1].runtime;
        }
        p->next->data.start=pcb[i].start;
        p->next->next=NULL;
        p=p->next;
    }
    cout << "调用成功！" << endl;
    
    
    p = r->next;
    if(p == NULL)
    {
        cout << "当前无正在运行的进程！" << endl;
        return 0;
    }

    while(p != NULL )
    {
        printf("进程名:%dt优先级:%dt到达时间:%dt开始时间:%dt运行时间:%dn",p->data.id,p->data.priority,p->data.ptime,p->data.start,p->data.runtime);
        p = p->next;
    }
    return 0;
}

void query() {	//查询当前是否有进程到达，有则入队
	//将当前时刻的所有进程入队
	for(int i = 0; i < table[t].size(); i++)
		que.push(table[t][i]);
}
void run() {
	cout << "当前时刻t" << "运行进程t" << "剩余服务时间" << endl;
	PCB cur = pcb_list[0];	//初始化当前进程
	sjp = q;	//初始化时间片 
	for(t = 0; t <= max_time; t++) {	//跑时间 
		query();	//当前是否有进程到达，有则入队
		if(que.empty()) continue;	//如果队列空，跳过
		if(!sjp || !cur.runtime) {	//时间片用完了 或 当前进程运行完了，则调度 
			sjp = q;	//恢复时间片
			que.pop();	//队首出队
			if(cur.runtime) que.push(cur);	//如果当前进程没有运行完，则移到队尾
			else pcb_list[cur.id].finish = t;	//运行完了，设置完成时刻 
			if(!que.empty()) cur = que.front();	//取新的队首
			else continue;	//已经空了，跳过 
		}
		cout << t << "tt" << cur.id << "tt" << cur.runtime << endl;	//输出当前时刻状态 
		sjp--,cur.runtime--;	//时间片-1，当前进程服务时间-1 
	}
}
void set_max_time() {
	for(int i = 0; i < n; i++)
		max_time += pcb_list[i].runtime;
	max_time+=5;//多加一点避免边界问题（删掉也没关系,程序已经很完备了） 
}

int RR() 
{
	printf("时间片轮转调度算法nn");
		printf("请输入进程数 时间片n");
		cin >> n >> q;	//输入进程数和时间片时长
		printf("请输入每个进程的进程名 到达时间 服务时间n");
		for(int i = 0; i < n; i++)
			cin >> pcb_list[i].id >> pcb_list[i].ptime >> pcb_list[i].runtime;
		sort(pcb_list,pcb_list+n);	//对进程按到达时间排序
		for(int i = 0; i < n; i++) {
			pcb_list[i].id = i;	//给进程编号 
			table[pcb_list[i].ptime].push_back(pcb_list[i]);	//将进程送到时刻表 
		}
		set_max_time();	//设置最大运行时间
		run();	//开始运行
		cout << "进程名字t" << "完成时间t" << "周转时间t" << "带权周转时间" << endl;
		for(int i = 0; i < n; i++) {
			int zzsj = pcb_list[i].finish-pcb_list[i].ptime;
			double dqzzsj = (double)zzsj / pcb_list[i].runtime;
			printf("%dtt%dtt%dtt%.2lfn",pcb_list[i].id+1,pcb_list[i].finish,zzsj,dqzzsj);
		}
		return 0;
}

int menu(Ready r)
{
    int n;
    while(1)
    {
        cout << "n***********进程演示系统*************" << endl;
        cout << "        1.按优先级调用进程"<< endl;
        cout << "        2.时间片段轮转算法"<< endl;
        cout << "        8.退出程序"<< endl;
        cout << "************************************"<< endl << endl;
        cout << "请输入你的选择（1-8）："<< endl;
        cin >> n;
        switch(n)
        {
            case 1:Prioritycall(r);
            break;
            case 2:RR();
            break;
            case 8:
				return 0;
            default:cout << "没有这个选项！";
            break;
        }
    }
    return 0;
}

int main()
{
    Ready r;
    r = init(); 					/// 创建进程单链表，便于删除操作
    menu(r);
    return 0;
}

代码如下（示例）：

1. 优先级调度算法
   
2. 时间片轮转调度算法
   

1. 优先级调度算法
   
2. 时间片轮转调度算法
   

以上就是今天要讲的内容，本文仅仅简单介绍了进程优先级调度算法和时间片段轮转算法。代码尚有不足之处，如果有大佬能完善代码请多多指正我，私聊发我一份。
注意：
（1）必须了解其基本原理才进行代码学习
（2）必须考虑每个进程的到达时间，判断它是否在当前时刻是否到达（即对进程的到达时间进行排序），基于这个基础上进行进程优先级调度算法和时间片轮转调度算法。