基于优先级的时间片轮转调度算法
2019-02-14 本文已影响0人
萌萌饭团君
1、假定系统有5个进程，每个进程用一个进程控制块PCB来代表，进程控制块的结构如下图1.1所示：
| 进程名 | 优先级 | 要求运行时间 | 已运行时间 | 进程状态 | 指针 |
|---|
其中：
进程名：作为进程的标识，假设五个进程的进程名分别为p1，p2，p3，p4，p5。
指针：进程按顺序排成循环链表，用指针指出下一个进程的进程控制块首地址，最后一个进程中的指针指出第一个进程的进程控制块首地址。
要求运行时间：假设进程需要运行的单位时间数。
已运行时间：假设进程已经运行的单位时间数，初值为0。
状态：可假设有两种状态，就绪状态和结束状态。进程的初始状态都为就绪状态。
2、每次运行所设计的处理器调度程序调度进程之前，为每个进程随机确定它的要求运行时间和优先级（数值越大，优先级越高）。
3、进程调度依据优先级进行，优先级随着时间动态增加，每经过一个时间片，优先级加1。
4、此程序是模拟处理器调度，因此，被选中的进程并不实际启动运行，而是执行
已运行时间+1
来模拟进程的一次运行，表示进程已经运行过一个单位时间。
5、在所设计的程序中应有显示语句，能显示每次被选中的进程名以及运行一次后进程队列的变化。
实验代码：
#include <iostream>
#include <string>
#include <cstdlib>
#define maxNTime 10
using namespace std;
struct pcb {
string name;
int priority;
int needTime;
int runTime;
int pstate;
pcb * next;
};
pcb* input(int pNum) {
pcb * head = NULL;
pcb * p;
for (int i = 0; i < pNum; i++) {
p = head;
cout << "请输入" << i + 1 << "第个进程名:";
head = new pcb;
cin >> head->name;
head->priority = (rand() % pNum) + 1;
head->needTime = (rand() % maxNTime) + 1;
head->runTime = 0;
head->pstate = 0;
head->next = p;
}
for (p = head; p->next != NULL; p = p->next);
p->next = head;
return head;
}
void output(pcb* head, int pNum) {
pcb* p = head;
cout << "------------------------------------------------\n";
string sta[3] = { "就绪","运行","完成" };
for (int i = 0; i < pNum; i++) {
cout << p->name << "\t" << p->runTime << "\t" << p->needTime << "\t\t" << p->priority << "\t" << sta[p->pstate] << "\n";
p = p->next;
}
}
pcb* findHP(pcb* p, int pNum) {
pcb * high = p;
for (int i = 0; i < pNum; i++) {
if (p->pstate == 1);
else if (p->priority >= high->priority) high = p;
p = p->next;
}
return high;
}
void runP(pcb* head, pcb* p, int pNum, int timePs) {
int datTime = 0;
datTime = (p->needTime <= timePs) ? p->needTime : timePs;
cout << "正在运行:" << p->name << endl;
for (int i = 0; i < datTime; i++) {
p->pstate = 1;
p->runTime++;
p->needTime--;
}
p->pstate = (p->needTime == 0) ? 2 : 0;
output(head, pNum);
p = p->next;
for (int i = 0; i < pNum - 1; i++) {
if (p->pstate != 1) p->priority += 1;
p = p->next;
}
}
bool allDone(pcb* head, int pNum) {
pcb* p = head;
for (int i = 0; i < pNum; i++) {
if (p->pstate == 0) return 0;
else p = p->next;
}
return 1;
}
int main() {
int pNum, timePs;
pcb * head, *p;
cout << "请输入进程数:";
cin >> pNum;
head = input(pNum);
cout << "请输入时间片:";
cin >> timePs;
p = head;
cout << "进程名\t已运行\t还需时间\t优先级\t状态\n";
while (!allDone(head, pNum)) {
p = findHP(p, pNum);
runP(head, p, pNum, timePs);
}
// output(head,pNum);
return 0;
}
运行：
请输入进程数:5
请输入1第个进程名:P1
请输入2第个进程名:P2
请输入3第个进程名:P3
请输入4第个进程名:P4
请输入5第个进程名:P5
请输入时间片:4
进程名 已运行 还需时间 优先级 状态
正在运行:P2
------------------------------------------------
P5 0 5 3 就绪
P4 0 9 4 就绪
P3 0 5 5 就绪
P2 1 0 5 完成
P1 0 8 2 就绪
正在运行:P3
------------------------------------------------
P5 0 5 4 就绪
P4 0 9 5 就绪
P3 4 1 6 就绪
P2 1 0 5 完成
P1 0 8 3 就绪
正在运行:P4
------------------------------------------------
P5 0 5 5 就绪
P4 4 5 6 就绪
P3 4 1 6 就绪
P2 1 0 6 完成
P1 0 8 4 就绪
正在运行:P2
------------------------------------------------
P5 0 5 6 就绪
P4 4 5 6 就绪
P3 4 1 7 就绪
P2 1 0 7 完成
P1 0 8 5 就绪
正在运行:P3
------------------------------------------------
P5 0 5 7 就绪
P4 4 5 7 就绪
P3 5 0 8 完成
P2 1 0 7 完成
P1 0 8 6 就绪
正在运行:P4
------------------------------------------------
P5 0 5 8 就绪
P4 8 1 8 就绪
P3 5 0 8 完成
P2 1 0 8 完成
P1 0 8 7 就绪
正在运行:P5
------------------------------------------------
P5 4 1 9 就绪
P4 8 1 8 就绪
P3 5 0 9 完成
P2 1 0 9 完成
P1 0 8 8 就绪
正在运行:P2
------------------------------------------------
P5 4 1 9 就绪
P4 8 1 9 就绪
P3 5 0 10 完成
P2 1 0 10 完成
P1 0 8 9 就绪
正在运行:P3
------------------------------------------------
P5 4 1 10 就绪
P4 8 1 10 就绪
P3 5 0 11 完成
P2 1 0 10 完成
P1 0 8 10 就绪
正在运行:P4
------------------------------------------------
P5 4 1 11 就绪
P4 9 0 11 完成
P3 5 0 11 完成
P2 1 0 11 完成
P1 0 8 11 就绪
正在运行:P5
------------------------------------------------
P5 5 0 12 完成
P4 9 0 11 完成
P3 5 0 12 完成
P2 1 0 12 完成
P1 0 8 12 就绪
正在运行:P1
------------------------------------------------
P5 5 0 12 完成
P4 9 0 12 完成
P3 5 0 13 完成
P2 1 0 13 完成
P1 4 4 13 就绪
正在运行:P2
------------------------------------------------
P5 5 0 13 完成
P4 9 0 13 完成
P3 5 0 14 完成
P2 1 0 14 完成
P1 4 4 13 就绪
正在运行:P3
------------------------------------------------
P5 5 0 14 完成
P4 9 0 14 完成
P3 5 0 15 完成
P2 1 0 14 完成
P1 4 4 14 就绪
正在运行:P4
------------------------------------------------
P5 5 0 15 完成
P4 9 0 15 完成
P3 5 0 15 完成
P2 1 0 15 完成
P1 4 4 15 就绪
正在运行:P5
------------------------------------------------
P5 5 0 16 完成
P4 9 0 15 完成
P3 5 0 16 完成
P2 1 0 16 完成
P1 4 4 16 就绪
正在运行:P1
------------------------------------------------
P5 5 0 16 完成
P4 9 0 16 完成
P3 5 0 17 完成
P2 1 0 17 完成
P1 8 0 17 完成
