#include <iostream>
using namespace std;
#include <iomanip>
typedef struct PCB//进程控制块
{
char pname[10];//进程名
int priority;//优先数(优先数越大，优先级越高)
int btime;//需要运行时间
int rtime;//已用CPU时间
int atime;//进程到达时间
char state;//进程状态(R为就绪状态，C为结束状态)
bool operator>(const PCB a)const
{
return (priority > a.priority || atime < a.atime);
}
}PCB;
typedef struct PCBlist//进程链表
{
PCB data;
struct PCBlist* next;
}PNODE;
void InsertSort(PNODE** head, PCB x);//插入排序
void InitProcess(PNODE** head);//初始化进程
void ShowProcess(PNODE** head,int a);//展示进程信息
void DropProcess(PNODE** head, PNODE** end);//进程退出就绪队列
void HPF(PNODE** head, PNODE** end);//HPF调度
void RunHPF(PNODE** ready, PNODE** end);//HPF相关处理
void InitRR(PNODE** head);//初始化轮转进程
void InsertTail(PNODE** head, PCB x);//尾部插入
void RR(PNODE** head, PNODE** end,int time);//RR调度
void RunRR(PNODE** head, PNODE** end,int time);//RR调度相关处理
void destroyend(PNODE** end);//销毁结束队列
int main()
{
int x = 0, y = 1,time = 0;
PNODE* ready = NULL,* end = NULL;
cout << "处理机调度实验" << endl;
while (y)
{
cout << "——————请输入————————\n0:最高优先级优先调度\n1:简单轮转法调度" << endl;
cin >> x;
if (x == 0) RunHPF(&ready, &end);
else if (x == 1)
{
cout << "请输入时间片大小：";
cin >> time;
RunRR(&ready, &end, time);
}
else cout << "输入错误!请输入0或1!\n";
cout << "\n——————要继续进行调度吗？————————\n0:退出\n1:继续" << endl;
cin >> y;
}
cout << "程序结束！" << endl;
system("pause");
}
void InsertSort(PNODE** head, PCB x)
/*按进程优先级插入排序
head：头指针 x：要插入的结点
*/
{
PNODE* p1, * p2, * p;
p = new PNODE;
p->data = x;
p->next = NULL;
if (!*head)//若链表为空
*head = p;
else
{
p2 = p1 = *head;
while (p2 != NULL && (p2->data > p->data))//寻找p的插入位置
{
p1 = p2;
p2 = p2->next;
}
if (p2 == NULL)//若p的优先级最低
p1->next = p;//插入至尾部
else if (p1 == p2)//若p的优先数最高
{
p->next = *head;//插入至首部
*head = p;
}
else//否则插入至p1,p2中间
{
p->next = p2;
p1->next = p;
}
}
}
void InitProcess(PNODE** head)
/*初始化进程链表*/
{
int n;
PCB process = {"None",0,0,0,0,'R'};
cout << "—————————最高优先级优先调度——————————\n";
cout << "请输入进程总数:";
cin >> n;
for (int i = 0; i < n; i++)
{
cout << "第" << i + 1 << "个进程的名称、优先数、所需运行时间为:" << endl;
cin >> process.pname >> process.priority >> process.btime;
InsertSort(head, process);
}
cout << "—————————正在生成就绪队列———————————\n" << endl;
}
void ShowProcess(PNODE** head,int a)
/*显示就绪队列中的进程信息*/
{
PNODE* p = *head;
if (p)
{
cout << "———————————就绪队列—————————————" << endl;
if (a == 0)
{
cout << "\n进程名\t优先数\t所需运行时间\t已用CPU时间\t进程状态" << endl;
do
{
cout << setw(4) << (p->data).pname
<< setw(8) << (p->data).priority
<< setw(10) << (p->data).btime
<< setw(15) << (p->data).rtime
<< setw(16) << (p->data).state << endl;
p = p->next;
} while (p);
cout << "\n————————————————————————————" << endl;
}
else
{
cout << "\n进程名\t到达时间 所需运行时间\t已用CPU时间\t进程状态" << endl;
do
{
cout << setw(4) << (p->data).pname
<< setw(8) << (p->data).atime
<< setw(12) << (p->data).btime
<< setw(14) << (p->data).rtime
<< setw(15) << (p->data).state << endl;
p = p->next;
} while (p);
cout << "\n————————————————————————————" << endl;
}
}
}
void DropProcess(PNODE** head, PNODE** end)
/*进程进入结束队列*/
{
PNODE* p = *head;
PNODE* x = new PNODE;
x->data = p->data;
if (!*end)//若结束队列为空
{
x->next = *end;
*end = x;
}
else//若结束队列不为空
{
PNODE* p1 = *end;
while (p1->next) p1 = p1->next;
p1->next = x;//插入至尾部
x->next = NULL;
}
*head = (*head)->next;
delete p;
p = nullptr;
PNODE* e = *end;
cout << "已经结束的进程为：";
while (e)
{
cout << (e->data).pname << " ";
e = e->next;
}
cout << endl;
}
void HPF(PNODE** head, PNODE** end)
/*最高优先级调度*/
{
while (*head)//若就绪队列不为空
{
PNODE* p = *head;//p为当前正在运行的进程
cout << "当前正在运行的进程为：" << (p->data).pname << endl;
(p->data).priority--;//优先数减一
(p->data).rtime++;//已用CPU时间加一
if ((p->data).btime != (p->data).rtime)//若进程未完成
{
cout << "时间片结束，该进程未完成。" << endl;
*head = (*head)->next;
InsertSort(head, p->data);//将进程重新加入就绪队列
}
else//若进程已完成
{
cout << "时间片结束，该进程已完成！" << endl;
(p->data).state = 'C';//状态置为完成
DropProcess(head, end);//退出就绪队列，移入结束队列
}
ShowProcess(head,0);
}
cout << "————————进程已全部完成！————————————" << endl;
}
void RunHPF(PNODE** ready, PNODE** end)
{
InitProcess(ready);
ShowProcess(ready,0);
HPF(ready, end);
destroyend(end);
}
void InitRR(PNODE** head)
/*初始化轮转进程列表*/
{
int n;
PCB process = { "None",0,0,0,0,'R'};
cout << "—————————简单轮转法调度————————————\n";
cout << "请输入进程总数:";
cin >> n;
for (int i = 0; i < n; i++)
{
cout << "第" << i + 1 << "个进程的名称、到达时间、所需运行时间为:" << endl;
cin >> process.pname >> process.atime >> process.btime;
InsertSort(head, process);
}
cout << "—————————正在生成就绪队列———————————\n" << endl;
}
void InsertTail(PNODE** head, PCB x)
{
PNODE* p;
p = new PNODE;
p->data = x;
p->next = NULL;
if (!*head)
*head = p;
else
{
PNODE* p1;
p1 = *head;
while (p1->next) p1 = p1->next;
p1->next = p;
}
}
void RR(PNODE** head, PNODE** end,int time)
{
while (*head)//若就绪队列不为空
{
PNODE* p = *head;//p为当前正在运行的进程
cout << "当前正在运行的进程为：" << (p->data).pname << endl;
if ((p->data).rtime + time > (p->data).btime)//如果进程即将完成
{
int nextq = (p->data).rtime + time - (p->data).btime;//但时间片未用完
if (p->next) ((p->next)->data).rtime += nextq;//则给下一个进程使用
}
(p->data).rtime += time;//已用CPU时间加时间片
if ((p->data).btime > (p->data).rtime)//若进程未完成
{
cout << "时间片结束，该进程未完成。" << endl;
*head = (*head)->next;
InsertTail(head, p->data);//将进程送回就绪队列末尾
}
else//若进程已完成
{
cout << "时间片结束，该进程已完成！" << endl;
(p->data).state = 'C';//状态置为完成
DropProcess(head, end);//退出就绪队列，移入结束队列
}
ShowProcess(head,1);
}
cout << "————————进程已全部完成！————————————" << endl;
}
void RunRR(PNODE** ready, PNODE** end,int time)
{
InitRR(ready);
ShowProcess(ready,1);
RR(ready, end,time);
destroyend(end);
}
void destroyend(PNODE** end)
{
PNODE* p;
while ((*end))
{
p = *end;
*end = (*end)->next;
delete p;
}
}
本文为原创文章，转载请注明出处！