操作系统实验 动态最高优先级调度算法（C++实现）

一、前言

参考文章：

• 1、https://blog.csdn.net/weixin_44949135/article/details/116539292
• 2、https://blog.csdn.net/qq_40159978/article/details/90934681
• 3、http://c.biancheng.net/view/480.html

轻微强迫症最后为了对齐每个数据的格式，调了好多次才非常整齐！本文主要参考文章2完成了操作系统实验最高优先级调度算法，参考文章3学习了priority_queue容器的用法，扩展内容为参考文章1其他几种调度算法的学习。

二、实验简介和算法流程图

动态最高优先级调度算法是指在进程创建时先确定一个初始优先数， 以后在进程运行中随着进程特性的改变不断修改优先数，这样，由于开始优先数很低而得不到CPU的进程，就能因为等待时间的增长而优先数变为最高而得到CPU运行。

算法流程图：

三、算法实现思路

priority_queue 容器适配器定义了一个元素有序排列的队列。默认队列头部的元素优先级最高。因为它是一个队列，所以只能访问第一个元素，这也意味着优先级最高的元素总是第一个被处理。
这里我们就利用这个容器就能非常容易完成实验，
首先，先初始化pcb，获取输入的进程名、优先级、运行时间后加入队列中，根据重载运算符的规则自动排序，权值大的优先，如果权值一样，时间短的优先，每次push都会有一次排序的操作；
然后，就是不断的出队顶端进程运算，如果运行时间为0即运行完毕不再入队否则继续入队运行；
最后，所有进程运行完毕退出！其实也就是算法流程图的具体实现。

四、实验源码

#include
#include
#include

using namespace std;

typedef struct pcb {
	string pName;//进程名
	int priorityNumber;//优先数
	float needTime;//估计服务时间
	float runTime;//已运行时间
	char state;//进程状态  W等待  R运行 D结束
	friend bool operator<(pcb a, pcb b){
        if (a.priorityNumber == b.priorityNumber)
            return a.needTime > b.needTime; //时间小的优先
        return a.priorityNumber < b.priorityNumber;//权值大的优先
    } 
}PCB;
 
priority_queue<PCB> waitList;//就绪队列 
int n;//进程个数 

void init_pcb()//初始化pcb，输入进程信息 
{
	printf("\n\n\n\t\t\t--------------------\n");
    printf("\t\t\t|最高优先级调度算法|\n");
    printf("\t\t\t|  作者：q_bing   |\n");
    printf("\t\t\t| 2022年11月29日  |\n");
    printf("\t\t\t--------------------\n");
	cout << "请输入进程的个数:";
	cin >> n;
	PCB r;//临时工作结点
	for (int i = 0; i<n; i++) {
		cout << "请输入第" << i + 1 << "个进程的名字、优先数、服务时间(例如:A 12 8 ):";
		cin >> r.pName;
		cin >> r.priorityNumber;
		cin >> r.needTime;
		r.runTime = 0;
		r.state = 'W';
		waitList.push(r);
	}
	cout << endl;
}
 
void showProcess(priority_queue<PCB> waitList) //显示进程信息 
{
	PCB s;//临时工作结点
	cout << "进程名\t|优先数 |服务时间|已运行时间|" << endl;
	while (waitList.size() != 0) {
		s = waitList.top();
		cout << s.pName << "\t|" << s.priorityNumber << "\t|" << s.needTime << "\t |"<< s.runTime << "\t    |" << endl;
		waitList.pop();
	}
	cout << endl;
}
 
void runProcess(priority_queue<PCB> &waitList) {//运行进程
	PCB s;
	while(waitList.size()!=0){
	    s = waitList.top();
		waitList.pop();
		cout << "正在运行的进程" << endl;
		cout << "进程名\t|优先数 |服务时间|已运行时间|" << endl;//输出当前进程
		cout << s.pName << "\t|" << s.priorityNumber << "\t|" << s.needTime << "\t |"<< s.runTime << "\t    |" << endl;
		s.priorityNumber--;//优先数-1
		s.runTime++;//已运行时间+1 
		s.needTime--;//还需要时间-1 
		if (s.needTime == 0) {
			s.state = 'D';
			cout<<"已完成进程"<<"---------------------------------------->"<<s.pName<<endl<<endl;
		}
		else
			waitList.push(s);
		
		if (waitList.empty()) {
			cout<<"\n所有进程运行完毕！"<<endl;
			return;
		}
		cout << "进程" << s.pName << "执行一次之后就绪队列中的进程" << endl;
		showProcess(waitList);
	}
	cout << endl;
}

int main() {
	init_pcb();
	showProcess(waitList);
	runProcess(waitList);
	system("pause");
	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

在参考程序输入测试数据
001 6 3
003 6 2
002 5 4
005 4 4
004 3 4

应该得到的结果顺序
003
001
002
005
004

本程序验证的运行数据
003
001
002
005
004

五、实验结果截图