操作系统课设，题目二 设计一个按照优先级调度算法实现处理机调度的程序_操作系统课设最高优先数

操作系统课设

题目一：设计一个按照时间片轮转法实现处理机调度的程序
虽然该文内容的是题目二，但是题目一和题目二也就调度方式不一样，其他都是完全相同的，也可以作为参考。

题目二：设计一个按照优先级调度算法实现处理机调度的程序
优先级调度算法实现处理机调度的程序设计提示如下：
（1） 假设系统有n个进程，每个进程用一个进程控制块（PCB）来代表。进程控制块的格式如下表所示，且参数意义也相同。进程的优先数、到达时间和估计运行时间由用户程序任意设定，且优先数越低，优先级越高。调度时，总是选择优先级最高的进程运行。

进程名
链接指针
进程的到达时间
进程的优先级
估计运行时间
进程状态

（2） 为了调度方便，设计一个指针指向就绪队列的第一个到达进程。另外再设一个当前运行进程指针，指向当前正运行的进程。
（3） 处理机调度时，总是选择已经到达队列的优先级最高的进程运行。为了采用动态优先级调度，进程每运行一次，其优先级就减1。
（4） 由于本题目是模拟实验，所以对被选中的进程并不实际启动运行，而只是执行如下操作：1）优先数加1；
2）估计运行时间减1；
3）输出当前运行进程的名字。
用这三个操作来模拟进程的一次运行。
（5） 进程运行一次后，应判断该进程的剩余运行时间是否为0，若不为0，且其优先级低于就绪队列的其他进程的优先级，则选择一个高优先级进程抢占CPU运行，若该进程的剩余运行时间为0，则将该进程的状态置为完成状态“C”，并撤出就绪队列。
（6） 若就绪队列不为空，则重复上述的步骤（4）和（5）直到所有进程都运行完为止。
（7） 在所设计的调度程序中，应包含显示或打印语句，以便显示或打印每次选中进程的名称及运行一次后进程的变化以及就绪队列中各进程排队情况。

数据结构

• 每一个进程控制块都有多个数据项，可以用结构体将多个进程连成链表
  struct pid {
  string name;//进程名
  pid* next;//链接指针
  int arrive_time = 0;//到达时间
  int grade = 0;//进程的优先级数
  int run_time = 0;//预计运行时间
  string state;//进程状态
  };

• 需要一个指针来指向当前就绪列表里面优先级最高的进程（也就是当前运行的进程）

• 还需要一个指针来指向优先度最高的进程的上一个节点（用于进程执行完成，进程移出就绪队列）

• 还需要设置一个全局变量来代表系统运行的时间

函数

• 创建链表函数
  创建一个头指针，尾指针，数据项指针。
  给头尾节点分配内存， 头节点的下一个节点为空，尾节点等于头节点。
  然后用一个循环，里面给数据项指针分配空间，然后初始化数据项，再把数据项节点加到链表尾部，该节点成为新的尾节点。
  结束后返回头指针。

• 展示运行后就绪列表函数
  把头指针作为参数传进来。
  利用到达时间和当前系统时间对比判断，输出当前时间已经进入就绪列表的进程的情况。
  利用指针下一项为空做结束标志。

• 找到优先级最高的进程并执行函数（也就是修改数据和输出）
  把头指针作为参数传进来。
  将当前最高优先级指针设置为空。
  利用循环，找出当前时间已经到达的就绪队列里面优先级最高的进程。
  用指针下一项是否为空作为结束标志，结束了代表遍历了一遍链表。
  刚进入的时候判断进程在当前时间是否到达就绪列表，如果到达并且当前最高优先级指针为空则用当前最高优先级指针指向它，
  进程在当前时间都到达就绪列表的情况下，先看谁的优先级数更小，优先级数越小，进程优先级越大，如果指针指向的进程的优先级数更小，则用该进程节点替换掉就绪队列最高优先级指针中的内容。
  如果两个判断语句都没有进入，那指针就指向下一个节点。
  循环结束之后，就代表当前系统最高优先级的进程已经被找出来，修改数据。输出当前系统时间，系统时间+1。
  判断当前最高优先级指针是否为空，不为空则调用展示运行后就绪列表函数把就绪列表中的进程进行输出，然后判断该进程的预计运行时间是否为0，为0则把最高优先级指针置为空，并把该进程节点从链表删除，（利用一开始设置的当前运行进程的前一个节点指针）
  如果当前最高优先级指针为空则输出说明当前时间就绪列表内没有进程。

• 主函数
  创建一个指针，接受调用创建链表函数的返回值。
  利用while循环，用链表是否为空做判断，循环调用找到优先级最高的进程并执行函数。

源码

#include<iostream>
#include<ctime>
#include<string>
#include<stdlib.h>
using namespace std;

struct pid {
	string name;//进程名
	pid* next;//链接指针
	int arrive_time = 0;//到达时间
	int grade = 0;//进程的优先级
	int run_time = 0;//预计运行时间
	string state;//进程状态
};
pid* runing = new pid;//指向正在运行的进程的指针
pid* runing_last = new pid;//指向正在运行的进程的上一个进程的指针
int M = 0;//系统时间
pid* creat() {//初始化创建进程列表
	pid* head, * end, * normal;
	int a = 97;
	int m;//进程的数目
	srand((unsigned)time(NULL));
	m = rand() % 5 + 1;//随机生成1-5个进程
	head = new pid;//分配内存
	end = head;
	end->next = NULL;
	while (m) {//运行m次，生成m个进程
		normal = new pid;
		normal->name = a;//初始化进程名
		normal->arrive_time = rand() % 5 + 1;//进程到达时间随机初始化为1-10
		normal->grade = rand() % 5 + 1;//进程优先级随机初始化为1-10
		normal->run_time = rand() % 5 + 1;//进程预计运行时间随机初始化为1-5
		normal->state = "就绪";//设置进程状态
		end->next = normal;//将新的进程放在尾节点的进程后面
		end = normal;//新的进程成为尾进程
		m--;//自减，用来计数
		a++;//用来起名，保证每一个进程名不同
	}
	end->next = NULL;//创建完成之后，将尾节点的下一个节点置为空
	pid* p;
	p = head;//将头节点传递给p指针
	cout << "队列中的情况:" << endl;
	cout << "进程名" << '\t' << "到达时间" << '\t' << "优先数" << '\t' << "估计运行时间" << '\t' << "进程状态" << endl;
	while (p->next != NULL) {//输出初始化生成的进程数据
		p = p->next;
		cout << p->name << '\t' << p->arrive_time << '\t' << '\t' << p->grade << '\t' << p->run_time << '\t' << '\t' << p->state << endl;
	}
	cout << "-------------------------分割线--------------------------" << endl;
	return head;//返回头指针
}
void display(pid* head) {
	pid* p = head;//将头指针传给p指针
	if (p->next == NULL) {//p指针指向的下一个节点为空则代表链表为空，
		cout << "就绪队列中已经没有进程了！";
	}
	else {
		cout << "运行完成后就绪队列中的情况:" << endl;
		cout << "进程名" << '\t' << "到达时间" << '\t' << "优先数" << '\t' << "估计运行时间" << '\t' << "进程状态" << endl;
		while (p->next != NULL) {
			if (p->next->arrive_time <= M) {//链表不为空，则把链表内到达时间小于等于系统时间的进程输出
				p = p->next;
				cout << p->name << '\t' << p->arrive_time << '\t' << '\t' << p->grade << '\t' << p->run_time << '\t' << '\t' << p->state << endl;
			}
			else {
				p = p->next;
			}
		}
		cout << "-------------------------分割线--------------------------" << endl;
	}
}
int run(pid* head) {
	pid* p;
	p = head;//将头指针传给p指针
	M++;//M自增，代表系统时间加一
	while (1) {//循环遍历整个链表，找出优先级最高的进程

		if (p->next == NULL) {//如果p指向的下一个节点为空，则代表已经遍历了链表，退出循环
			break;
		}
		if ((p->next->arrive_time <= M) && runing==NULL) {//进程到达时间小于等于当前系统时间，并且当前最高优先级指针为空则用指针指向该节点
			runing = p->next;//用当前运行进程指针指向第一个符合条件的进程
			runing_last = p;//用指针指向第一个符合条件的进程的上一个节点
			p = p->next;
		}
		
		else if (runing!=NULL&&(p->next->arrive_time <= M) && (p->next->grade) < (runing->grade) ) {//按照优先数越小，优先级越高，并且只有当前最该优先级指针不为空才会进行优先级比较
			runing = p->next;//如果p的下一个节点优先级更高，则用p的下一个节点内容替换当前系统运行指针的内容
			runing_last = p;
			p = p->next;//p等于p的下一个节点	
		}
		
		else {
			p = p->next;//如果上面都不符合，p也等于下一个节点
			
		}
	}


cout << "当前的时间为：" << M << endl;//输出当前系统时间
if (runing != NULL) {//如果当前运行进程指针不为空，则代表就绪列表中有进程，可以进行输出
	cout << "当前运行的进程为：" << runing->name << "进程！" << endl;
	runing->grade = (runing->grade) + 1;//优先级数加一
	runing->run_time = (runing->run_time) - 1;//预计运行时间减一
	runing->state = "运行";//状态变为运行态
	if (runing->run_time == 0) {//判断进程是否进入完成态
		cout << "进程" << runing->name << "已经运行完毕，退出就绪队列！" << endl;
		runing->state = "C";//置进程的状态为完成态
		runing_last->next = runing->next;//从链表中删除该节点
		delete runing;//释放内存
		runing = NULL;//节点删除之后，把当前最高优先级指针置为空
		display(head);//调用函数，输出当前就绪队列中的情况
	}
	else {//如果没运行完成，则把进程的状态切换回就绪态，
		display(head);
		runing->state = "就绪";
	}
}
else {//就绪队列中没有进程
	cout << "当前就绪列表无进程!" << endl;
}

return 0;//返回0
}

void main() {
	runing = NULL;//一开始把当前最高优先级指针置空
	pid* p;//声明指针
	p = creat();//创建链表，用指针接受返回的头指针
	while (p->next!=NULL) {//利用循环，一直到链表中的进程全部退出链表才会结束循环
		run(p);//调用函数，进行优先级调度

	}
}
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

运行结果

注意事项

1.当前运行指针指向的进程优先级和就绪列表中的进程优先级相同的时候，运行当前指针指向的进程。（也就是不作交换）
2.注意到达时间，系统到了到达时间，进程才进入系统。

如果有错，可以指出啊！谢谢！啊哈哈哈！