说明：
1、假设有只两种状态，就绪状态和结束状态。进程的初始状态都为就绪状态。
2、每次运行所设计的处理器调度程序调度进程之前，为每个进程随机生成它的要求运行时间。
3、模拟处理器调度，被选中的进程并不实际启动运行，而是执行已运行时间+1来模拟进程的一次
运行，表示进程已经运行过一个单位时间
主要算法的流程图。
1、非抢占式（包括FCFS，SJF，Priority）：
2、抢占式（包括SRTF）：
3、轮转调度（包括Round_Robin）：
1、数据结构：
class
Process_Control_Block
;
//
进程控制单元类，用于存储进程信息
class
PCB_LIST
;
//
循环链表类，用于存储和处理事件队列
enum
PCB_State
{
READY
,
FINISH
};
//
进程的两种状态，就绪状态和结束状态
2
、符号说明：
using
PCB
=
Process_Control_Block
;
//
将PCB定义为Pross_Control_Block的别名
2
、头文件：
#include <iostream>
#include<string>
#include <cstdlib>
#include<ctime> //srand()要用
#include <iomanip> //setw()要用
using namespace std;
具体声明：
//
进程控制单元类
class
Process_Control_Block
{
public
:
string
name;
//
进程名
int
arriveTime;
//
到达时间
int
needTime;
//
要求运行时间
int
remainTime;
//
剩余运行时间
int
runTime;
//
已运行时间
int
beginTime;
//
开始时间
bool
isFirstExe;
//
判断是否第一次执行
int
endTime;
//
结束时间
int
priority;
//
作业优先级
int
turnaroundTime;
//
轮转时间
PCB_State
state;
//
进程状态类型
Process_Control_Block
* next;
//
指向下一个的指针
Process_Control_Block();
//
无参构造
Process_Control_Block(
string
pcb_name
,
int
pcb_atime
,
int
pcb_priority
);
//
带参构造
Process_Control_Block(
const
PCB
*
sour
);
//
拷贝构造
void
showPCB();
//
打印PCB信息
};
//
用于存储进程队列的循环链表类
class
PCB_LIST
{
public
:
PCB
* head;
//
表头结点
PCB_LIST() {
head =
new
PCB
();
head->next = head;
//
初始时头结点的下一个还是头结点
}
void
InsertByArriveTime(
PCB
*
pcb
);
//
按到达时间插入
void
InsertByNeedTime(
PCB
*
pcb
);
//
按进程所需时间插入
void
InsertByEndTime(
PCB
*
pcb
);
//
按进程结束时间插入
void
InsertByPriority(
PCB
*
pcb
);
//
按进程优先级插入
void
InsertByRemainTime(
PCB
*
pcb
);
//
按进程剩余时间插入
void
InsertAtTail(
PCB
*
pcb
);
//
插入到队列最后
bool
deleteByName(
string
pcb_name
);
//
根据进程名删除进程
bool
updata(
PCB
*
pcb
);
//
更新某进程的状态
void
showAll();
//
打印全部进程状态
bool
isEmpty();
//
判断链表中所有进程任务都已完成
int
getSize();
//
获得队列长度
PCB
* getTail();
//
获得队列中最后一个PCB
double
getAverTurnTime();
//
获得平均轮转时间
double
getAverWaitTime();
//
计算平均等待时间
double
getThroughput();
//
获得吞吐量
double
getResponseTime();
//
获得平均响应时间
void
clear_list();
//
清空队列
PCB
* FetchFirstPCB();
//
获取队列中第一个PCB
};
（其中函数具体实现代码见附录）
3
、程序清单及注释：
函数声明：
//
打印进程信息表头
void
print_header();
//
计算并打印进程总体信息（如吞吐量，CPU利用率等）
void
showInfo(
PCB_LIST
*
finishQueue
);
//
输入作业信息,按发生时间插入队列
void
wirite_list(
PCB_LIST
*
pcb_list
);
//PCB
的拷贝方法(不改变指针指向，只改变内容)
void
CopyPCB(
PCB
*
dest
,
const
PCB
*
sour
);
//
最短作业时间优先
void
SJF(
PCB_LIST
*
pcb_list
);
//
先来先服务
void
FCFS(
PCB_LIST
*
pcb_list
);
//
最短剩余时间优先
void
SRTF(
PCB_LIST
*
pcb_list
);
//
按优先级，运行一个时间片后下调优先级别(时间片长度为2)
void
Priority(
PCB_LIST
*
pcb_list
);
//
时间片轮转（时间片大小为2）
void
Round_Robin(
PCB_LIST
*
pcb_list
);
具体实现：
//
最短作业时间优先
void
SJF(
PCB_LIST
*
pcb_list
) {
int
currentTime = 0;
//
当前时间
bool
isCPU_Busy =
false
;
//CPU
忙碌状态
PCB_LIST
* readyQueue =
new
PCB_LIST
();
//
就绪队列
PCB_LIST
* finishQueue =
new
PCB_LIST
();
//
结束队列
PCB
* run_pcb =
pcb_list
->FetchFirstPCB();
//
正在运行的pcb
PCB
* arrived_pcb = run_pcb;
//
当前已经到达的pcb
while
(!
pcb_list
->isEmpty()) {
//
判断事件队列是否为空
while
(arrived_pcb !=
pcb_list
->head && currentTime >= arrived_pcb->arriveTime) {
if
(isCPU_Busy) {
//
如CPU忙碌，则按作业时间插入就绪队列
readyQueue->InsertByNeedTime(arrived_pcb);
}
else
{
run_pcb = arrived_pcb;
//
如CPU空闲，将到达的pcb设为正在运行的pcb
}
arrived_pcb = arrived_pcb->next;
}
if
(run_pcb->state ==
PCB_State
::
READY
) {
isCPU_Busy =
true
;
if
(run_pcb->isFirstExe) {
//
第一次执行记录开始时间
run_pcb->beginTime = currentTime;
//
进程发生时间为当前时间
run_pcb->isFirstExe =
false
;
}
run_pcb->runTime = currentTime – run_pcb->beginTime;
//
已运行时间
run_pcb->remainTime = run_pcb->needTime – run_pcb->runTime;
//
剩余运行时间
if
(run_pcb->runTime == run_pcb->needTime) {
run_pcb->endTime = currentTime;
//
设定结束时间
run_pcb->turnaroundTime = run_pcb->endTime – run_pcb->arriveTime;
run_pcb->state =
PCB_State
::
FINISH
;
//
状态改为结束
finishQueue->InsertByEndTime(run_pcb);
//
按结束时间插入结束队列
}
currentTime++;
}
if
(run_pcb->state ==
PCB_State
::
FINISH
) {
cout
<<
”
时间：”
<<
currentTime – 1
<<
endl;
cout
<<
”
此时运行的进程：”
<<
endl;
print_header();
run_pcb->showPCB();
cout
<<
”
结束的进程：”
<<
endl;
print_header();
finishQueue->showAll();
string
finish_name = run_pcb->name;
//
已结束进程的名字
isCPU_Busy =
false
;
readyQueue->deleteByName(finish_name);
if
(!readyQueue->isEmpty()) {
run_pcb = readyQueue->FetchFirstPCB();
//
取就绪队列的第一个
}
pcb_list
->deleteByName(finish_name);
cout
<<
”
就绪队列状态：”
<<
endl;
print_header();
readyQueue->showAll();
cout
<<
endl;
}
}
showInfo(finishQueue);
//
打印总体信息
}
//
先来先服务
void
FCFS(
PCB_LIST
*
pcb_list
) {
int
currentTime = 0;
//
当前时间
bool
isCPU_Busy =
false
;
//CPU
忙碌状态
PCB_LIST
* readyQueue =
new
PCB_LIST
();
//
就绪队列
PCB_LIST
* finishQueue =
new
PCB_LIST
();
//
结束队列
PCB
* run_pcb =
pcb_list
->FetchFirstPCB();
//
取最先到达的进程运行
PCB
* arrived_pcb = run_pcb;
//
当前已经到达的pcb
while
(!
pcb_list
->isEmpty()) {
//
判断事件队列是否为空
while
(arrived_pcb !=
pcb_list
->head) {
readyQueue->InsertByArriveTime(arrived_pcb);
arrived_pcb = arrived_pcb->next;
}
if
(run_pcb->state ==
PCB_State
::
READY
) {
isCPU_Busy =
true
;
if
(run_pcb->arriveTime > currentTime) {
currentTime = run_pcb->arriveTime;
}
run_pcb->beginTime = currentTime;
run_pcb->endTime = run_pcb->beginTime + run_pcb->needTime;
run_pcb->runTime = run_pcb->needTime;
currentTime = run_pcb->endTime;
run_pcb->remainTime = 0;
run_pcb->turnaroundTime = run_pcb->endTime – run_pcb->arriveTime;
run_pcb->state =
PCB_State
::
FINISH
;
finishQueue->InsertByEndTime(run_pcb);
}
if
(run_pcb->state ==
PCB_State
::
FINISH
) {
cout
<<
”
时间：”
<<
currentTime – 1
<<
endl;
cout
<<
”
在运行的进程：”
<<
endl;
print_header();
run_pcb->showPCB();
cout
<<
”
已完成的线程：”
<<
endl;
print_header();
finishQueue->showAll();
string
finish_name = run_pcb->name;
//
已结束进程的名字
isCPU_Busy =
false
;
readyQueue->deleteByName(finish_name);
if
(!readyQueue->isEmpty()) {
run_pcb = readyQueue->FetchFirstPCB();
//
取就绪队列的第一个开始运行
}
pcb_list
->deleteByName(finish_name);
cout
<<
”
就绪队列状态：”
<<
endl;
print_header();
readyQueue->showAll();
cout
<<
endl;
}
}
showInfo(finishQueue);
//
打印总体信息
}
//
按优先级(每次运行后优先级不变)
void
Priority(
PCB_LIST
*
pcb_list
)
{
int
currentTime = 0;
//
当前时间
bool
isCPU_Busy =
false
;
//CPU
忙碌状态
PCB_LIST
* readyQueue =
new
PCB_LIST
();
//
就绪队列
PCB_LIST
* finishQueue =
new
PCB_LIST
();
//
结束队列
PCB
* run_pcb =
pcb_list
->FetchFirstPCB();
//
正在运行的pcb
PCB
* arrived_pcb = run_pcb;
//
当前已经到达的pcb
while
(!
pcb_list
->isEmpty()) {
//
判断事件队列是否为空
while
(arrived_pcb !=
pcb_list
->head && currentTime >= arrived_pcb->arriveTime) {
if
(isCPU_Busy) {
//
如CPU忙碌，则按作业优先级插入就绪队列
readyQueue->InsertByPriority(arrived_pcb);
}
else
{
run_pcb = arrived_pcb;
//
如CPU空闲，将到达的pcb设为正在运行的pcb
}
arrived_pcb = arrived_pcb->next;
}
if
(run_pcb->state ==
PCB_State
::
READY
) {
isCPU_Busy =
true
;
if
(run_pcb->isFirstExe) {
//
第一次执行记录开始时间
run_pcb->beginTime = currentTime;
//
进程发生时间为当前时间
run_pcb->isFirstExe =
false
;
}
run_pcb->runTime = currentTime – run_pcb->beginTime;
//
已运行时间
run_pcb->remainTime = run_pcb->needTime – run_pcb->runTime;
//
剩余运行时间
if
(run_pcb->runTime == run_pcb->needTime) {
run_pcb->endTime = currentTime;
//
设定结束时间
run_pcb->turnaroundTime = run_pcb->endTime – run_pcb->arriveTime;
//
计算轮转时间
run_pcb->state =
PCB_State
::
FINISH
;
//
状态改为结束
finishQueue->InsertByEndTime(run_pcb);
//
按结束时间插入结束队列
}
currentTime++;
}
if
(run_pcb->state ==
PCB_State
::
FINISH
) {
cout
<<
”
时间：”
<<
currentTime – 1
<<
endl;
cout
<<
”
在运行的进程：”
<<
endl;
print_header();
run_pcb->showPCB();
cout
<<
”
已完成的进程：”
<<
endl;
print_header();
finishQueue->showAll();
string
finish_name = run_pcb->name;
//
已结束进程的名字
isCPU_Busy =
false
;
readyQueue->deleteByName(finish_name);
if
(!readyQueue->isEmpty()) {
run_pcb = readyQueue->FetchFirstPCB();
//
取就绪队列的第一个
}
pcb_list
->deleteByName(finish_name);
cout
<<
”
就绪队列状态：”
<<
endl;
print_header();
readyQueue->showAll();
cout
<<
endl;
}
}
showInfo(finishQueue);
//
打印总体信息
}
//
按优先级，运行一个时间片后下调优先级别(时间片长度为2)
void
Priority_2(
PCB_LIST
*
pcb_list
) {
int
currentTime = 0;
//
当前时间
bool
isCPU_Busy =
false
;
//CPU
忙碌状态
PCB_LIST
* readyQueue =
new
PCB_LIST
();
//
就绪队列
PCB_LIST
* finishQueue =
new
PCB_LIST
();
//
结束队列
int
timeSlice = 2;
//
时间片大小为2
PCB
* run_pcb =
pcb_list
->FetchFirstPCB();
//
正在运行的pcb（最先到达的进程）
PCB
* arrived_pcb = run_pcb;
//
当前已经到达的pcb
while
(!
pcb_list
->isEmpty()) {
//
判断事件队列是否为空
while
(arrived_pcb !=
pcb_list
->head && currentTime >= arrived_pcb->arriveTime) {
//
如当前时间已超过到达时间，则插入就绪队列
if
(isCPU_Busy) {
//
如CPU忙碌，则按到达时间插入就绪队列末尾
cout
<<
”
就绪队列状态：”
<<
endl;
readyQueue->showAll();
run_pcb = readyQueue->FetchFirstPCB();
}
else
{
run_pcb = arrived_pcb;
//
如CPU空闲，将到达的pcb设为正在运行的pcb
}
arrived_pcb = arrived_pcb->next;
//
到达的pcb指向下一个
}
if
(!readyQueue->isEmpty())
run_pcb = readyQueue->FetchFirstPCB();
//
取就绪队列的第一个
else
{
//
如就绪队列为空，就直接取事件队列第一个，并将当前时间设为它的到达时间
run_pcb =
pcb_list
->FetchFirstPCB();
}
if
(run_pcb->state ==
PCB_State
::
READY
) {
isCPU_Busy =
true
;
if
(run_pcb->isFirstExe) {
run_pcb->beginTime = currentTime;
//
进程发生时间为当前时间
run_pcb->isFirstExe =
false
;
}
currentTime += timeSlice;
//
每次加时间片的长度
run_pcb->runTime += timeSlice;
//
已运行时间+时间片长度
run_pcb->remainTime = run_pcb->needTime – run_pcb->runTime;
//
计算剩余时间
run_pcb->priority += 2;
if
(run_pcb->remainTime <= 0) {
run_pcb->endTime = currentTime + run_pcb->remainTime;
//
设定结束时间(减去小于0的部分)
run_pcb->turnaroundTime = run_pcb->endTime – run_pcb->arriveTime;
//
计算轮转时间
run_pcb->state =
PCB_State
::
FINISH
;
//
状态改为结束
run_pcb->remainTime = 0;
//
保证剩余时间不是负数
finishQueue->InsertByEndTime(run_pcb);
//
按结束时间插入结束队列
}
pcb_list
->updata(run_pcb);
//
更新事件队列中的信息
PCB
* temp =
new
PCB
(run_pcb);
readyQueue->deleteByName(run_pcb->name);
//
删除原队列中正在运行的进程
if
(temp->state ==
PCB_State
::
READY
)
//
如没有结束
readyQueue->InsertByPriority(temp);
//
重新插入就绪队列尾部
while
(arrived_pcb !=
pcb_list
->head && arrived_pcb->arriveTime <= currentTime) {
//
查看此时有无到达的队列
readyQueue->InsertByPriority(arrived_pcb);
//
插入到达的进程
arrived_pcb = arrived_pcb->next;
//
到达的pcb指向下一个
}
if
(temp->state !=
PCB_State
::
READY
) {
//
如进程结束了就打印信息
cout
<<
”
时间：”
<<
currentTime
<<
endl;
cout
<<
”
在该时间片运行进程：”
<<
endl;
print_header();
temp->showPCB();
cout
<<
”
结束的进程：”
<<
endl;
print_header();
finishQueue->showAll();
cout
<<
”
运行结束后就绪队列状态：”
<<
endl;
print_header();
readyQueue->showAll();
cout
<<
endl;
}
}
if
(run_pcb->state ==
PCB_State
::
FINISH
) {
string
finish_name = run_pcb->name;
//
已结束进程的名字
isCPU_Busy =
false
;
readyQueue->deleteByName(finish_name);
if
(!readyQueue->isEmpty()) {
run_pcb = readyQueue->FetchFirstPCB();
//
取就绪队列的第一个
}
pcb_list
->deleteByName(finish_name);
}
}
showInfo(finishQueue);
//
打印总体信息
}
//
最短剩余时间优先
void
SRTF(
PCB_LIST
*
pcb_list
) {
int
currentTime = 0;
//
当前时间
bool
isCPU_Busy =
false
;
//CPU
忙碌状态
PCB_LIST
* readyQueue =
new
PCB_LIST
();
//
就绪队列
PCB_LIST
* finishQueue =
new
PCB_LIST
();
//
结束队列
PCB
* run_pcb =
pcb_list
->FetchFirstPCB();
//
正在运行的pcb
PCB
* arrived_pcb = run_pcb;
//
当前已经到达的pcb
while
(!
pcb_list
->isEmpty()) {
//
判断事件队列是否为空
while
(arrived_pcb !=
pcb_list
->head && currentTime >= arrived_pcb->arriveTime) {
//
如当前时间已超过到达时间，则插入就绪队列
if
(isCPU_Busy) {
//
如CPU忙碌，则按作业剩余时间插入就绪队列
readyQueue->InsertByRemainTime(arrived_pcb);
//
将新进入的进程插入就绪队列
if
(arrived_pcb->remainTime <= run_pcb->remainTime) {
//
新进入的进程剩余时间小于正在运行的进程，则终止正在运行的进程，重新插入就绪队列
PCB
* re_run =
new
PCB
(run_pcb);
readyQueue->deleteByName(run_pcb->name);
//
删除原队列中的数据
readyQueue->InsertByRemainTime(re_run);
//
重新插入队列中
run_pcb = readyQueue->FetchFirstPCB();
//
新的运行进程为就绪队列最前的进程
}
}
else
{
run_pcb = arrived_pcb;
//
如CPU空闲，将到达的pcb设为正在运行的pcb
}
arrived_pcb = arrived_pcb->next;
}
if
(run_pcb->state ==
PCB_State
::
READY
) {
isCPU_Busy =
true
;
if
(run_pcb->isFirstExe) {
run_pcb->beginTime = currentTime;
//
进程发生时间为当前时间
run_pcb->isFirstExe =
false
;
}
run_pcb->runTime++;
//
已运行时间+1
run_pcb->remainTime = run_pcb->needTime – run_pcb->runTime;
//
计算剩余时间
if
(run_pcb->remainTime == 0) {
run_pcb->endTime = currentTime;
//
设定结束时间
run_pcb->turnaroundTime = run_pcb->endTime – run_pcb->arriveTime;
//
计算轮转时间
run_pcb->state =
PCB_State
::
FINISH
;
//
状态改为结束
finishQueue->InsertByEndTime(run_pcb);
//
按结束时间插入结束队列
}
currentTime++;
}
if
(run_pcb->state ==
PCB_State
::
FINISH
) {
cout
<<
”
时间：”
<<
currentTime – 1
<<
endl;
cout
<<
”
此时运行的进程：”
<<
endl;
print_header();
run_pcb->showPCB();
cout
<<
”
结束的进程：”
<<
endl;
print_header();
finishQueue->showAll();
string
finish_name = run_pcb->name;
//
已结束进程的名字
isCPU_Busy =
false
;
readyQueue->deleteByName(finish_name);
if
(!readyQueue->isEmpty()) {
run_pcb = readyQueue->FetchFirstPCB();
//
取就绪队列的第一个
isCPU_Busy =
true
;
}
pcb_list
->deleteByName(finish_name);
cout
<<
”
就绪队列状态：”
<<
endl;
print_header();
readyQueue->showAll();
cout
<<
endl;
}
}
showInfo(finishQueue);
//
打印总体信息
}
//
时间片轮转（时间片大小为2）
void
Round_Robin(
PCB_LIST
*
pcb_list
) {
int
currentTime = 0;
//
当前时间
bool
isCPU_Busy =
false
;
//CPU
忙碌状态
PCB_LIST
* readyQueue =
new
PCB_LIST
();
//
就绪队列
PCB_LIST
* finishQueue =
new
PCB_LIST
();
//
结束队列
int
timeSlice = 2;
//
时间片大小为2
PCB
* run_pcb =
pcb_list
->FetchFirstPCB();
//
正在运行的pcb（最先到达的进程）
PCB
* arrived_pcb = run_pcb;
//
当前已经到达的pcb
while
(!
pcb_list
->isEmpty()) {
//
判断事件队列是否为空
while
(arrived_pcb !=
pcb_list
->head && currentTime >= arrived_pcb->arriveTime) {
//
如当前时间已超过到达时间，则插入就绪队列
if
(isCPU_Busy) {
//
如CPU忙碌，则按到达时间插入就绪队列末尾
run_pcb = readyQueue->FetchFirstPCB();
}
else
{
run_pcb = arrived_pcb;
//
如CPU空闲，将到达的pcb设为正在运行的pcb
}
arrived_pcb = arrived_pcb->next;
//
到达的pcb指向下一个
}
if
(!readyQueue->isEmpty())
run_pcb = readyQueue->FetchFirstPCB();
//
取就绪队列的第一个
else
{
//
如就绪队列为空，就直接取事件队列第一个，并将当前时间设为它的到达时间
run_pcb =
pcb_list
->FetchFirstPCB();
}
if
(run_pcb->state ==
PCB_State
::
READY
) {
isCPU_Busy =
true
;
if
(run_pcb->isFirstExe) {
run_pcb->beginTime = currentTime;
//
进程发生时间为当前时间
run_pcb->isFirstExe =
false
;
}
currentTime += timeSlice;
//
每次加时间片的长度
run_pcb->runTime += timeSlice;
//
已运行时间+时间片长度
run_pcb->remainTime = run_pcb->needTime – run_pcb->runTime;
//
计算剩余时间
if
(run_pcb->remainTime <= 0) {
run_pcb->endTime = currentTime + run_pcb->remainTime;
//
设定结束时间(减去小于0的部分)
run_pcb->turnaroundTime = run_pcb->endTime – run_pcb->arriveTime;
//
计算轮转时间
run_pcb->state =
PCB_State
::
FINISH
;
//
状态改为结束
run_pcb->remainTime = 0;
//
保证剩余时间不是负数
finishQueue->InsertByEndTime(run_pcb);
//
按结束时间插入结束队列
}
pcb_list
->updata(run_pcb);
//
每次更新时间队列中的信息
PCB
* temp =
new
PCB
(run_pcb);
readyQueue->deleteByName(run_pcb->name);
//
删除原队列中正在运行的进程
if
(temp->state ==
PCB_State
::
READY
)
//
如没有结束
readyQueue->InsertAtTail(temp);
//
重新插入就绪队列尾部
while
(arrived_pcb !=
pcb_list
->head && arrived_pcb->arriveTime <= currentTime) {
//
查看此时有无到达的队列
readyQueue->InsertAtTail(arrived_pcb);
//
插入到达的进程
arrived_pcb = arrived_pcb->next;
//
到达的pcb指向下一个
}
if
(temp->state !=
PCB_State
::
READY
) {
//
如进程结束了就打信息
cout
<<
”
时间：”
<<
currentTime
<<
endl;
cout
<<
”
在该时间片运行进程：”
<<
endl;
print_header();
temp->showPCB();
cout
<<
”
结束的进程：”
<<
endl;
print_header();
finishQueue->showAll();
cout
<<
”
运行结束后就绪队列状态：”
<<
endl;
print_header();
readyQueue->showAll();
cout
<<
endl;
}
}
if
(run_pcb->state ==
PCB_State
::
FINISH
) {
string
finish_name = run_pcb->name;
//
已结束进程的名字
isCPU_Busy =
false
;
readyQueue->deleteByName(finish_name);
if
(!readyQueue->isEmpty()) {
run_pcb = readyQueue->FetchFirstPCB();
//
取就绪队列的第一个
}
pcb_list
->deleteByName(finish_name);
}
}
showInfo(finishQueue);
//
打印总体信息
}
//
打印表头
void
print_header() {
cout
<<
setw(8)
<<
”
进程名”
<<
setw(10)
<<
”
到达时间”
<<
setw(10)
<<
”
所需时间”
<<
setw(10)
<<
”
开始时间”
<<
setw(10)
<<
”
结束时间”
<<
setw(10)
<<
”
运行时间”
<<
setw(10)
<<
”
剩余时间”
<<
setw(8)
<<
”
优先级”
<<
endl;
}
//
打印进程总体信息
void
showInfo(
PCB_LIST
*
finishQueue
) {
cout
<<
“CPU Utilization: 100%”
<<
endl;
cout
<<
“Throughput: ”
<<
finishQueue
->getThroughput()
<<
endl;
cout
<<
“Average turnaround time: ”
<<
finishQueue
->getAverTurnTime()
<<
endl;
cout
<<
“Average waiting time: ”
<<
finishQueue
->getAverWaitTime()
<<
endl;
cout
<<
“Response time: 0”
<<
endl;
}
//
输入作业信息,按发生时间插入队列
void
wirite_list(
PCB_LIST
*
pcb_list
) {
pcb_list
->InsertByArriveTime(
new
PCB
(
“B”
, 2, 1));
pcb_list
->InsertByArriveTime(
new
PCB
(
“A”
, 0, 1));
pcb_list
->InsertByArriveTime(
new
PCB
(
“C”
, 5, 2));
pcb_list
->InsertByArriveTime(
new
PCB
(
“D”
, 5, 1));
pcb_list
->InsertByArriveTime(
new
PCB
(
“E”
, 12, 4));
pcb_list
->InsertByArriveTime(
new
PCB
(
“F”
, 15, 2));
}
//PCB
的拷贝方法(不改变指针指向，只改变内容)
void
CopyPCB(
PCB
*
dest
,
const
PCB
*
sour
) {
dest
->arriveTime =
sour
->arriveTime;
dest
->name
=
sour
->name;
dest
->needTime =
sour
->needTime;
dest
->priority =
sour
->priority;
dest
->remainTime =
sour
->remainTime;
dest
->runTime =
sour
->runTime;
dest
->beginTime =
sour
->beginTime;
dest
->state =
sour
->state;
dest
->endTime =
sour
->endTime;
dest
->isFirstExe =
sour
->isFirstExe;
dest
->turnaroundTime =
sour
->turnaroundTime;
}
主函数：
int
main()
{
PCB_LIST
* pcb_list =
new
PCB_LIST
();
//
新建事件队列
cout
<<
“—————SRTF—————”
<<
endl;
wirite_list(pcb_list);
SRTF(pcb_list);
pcb_list->clear_list();
cout
<<
“—————SJF—————”
<<
endl;
wirite_list(pcb_list);
SJF(pcb_list);
pcb_list->clear_list();
cout
<<
“—————FCFS—————”
<<
endl;
wirite_list(pcb_list);
FCFS(pcb_list);
pcb_list->clear_list();
cout
<<
“—————Priority—————”
<<
endl;
wirite_list(pcb_list);
Priority(pcb_list);
pcb_list->clear_list();
cout
<<
“—————Round_Robin—————”
<<
endl;
wirite_list(pcb_list);
Round_Robin(pcb_list);
pcb_list->clear_list();
}
附录
循环链表类
PCB_LIST
及进程控制块类
PCB
函数实现代码：
1
、
PCB
类：
void
Process_Control_Block
::showPCB() {
cout
<<
setw(8)
<<
name
<<
setw(10)
<<
arriveTime
<<
setw(10)
<<
needTime
<<
setw(10)
<<
beginTime
<<
setw(10)
<<
endTime
<<
setw(10)
<<
runTime
<<
setw(10)
<<
remainTime
<<
setw(8)
<<
priority
<<
endl;
}
//
拷贝构造
Process_Control_Block
::Process_Control_Block(
const
PCB
*
sour
) {
arriveTime =
sour
->arriveTime;
name
=
sour
->name;
needTime =
sour
->needTime;
priority =
sour
->priority;
remainTime =
sour
->remainTime;
runTime =
sour
->runTime;
beginTime =
sour
->beginTime;
state =
sour
->state;
endTime =
sour
->endTime;
turnaroundTime =
sour
->turnaroundTime;
isFirstExe =
sour
->isFirstExe;
next =
NULL
;
}
//
无参构造
Process_Control_Block
::Process_Control_Block() {
needTime = 1 + rand() % 10;
state =
PCB_State
::
READY
;
//
状态设为就绪
runTime = 0;
//
已运行时间设为0
beginTime = 0;
//
开始时间设为0
endTime = 0;
//
结束时间设为0
remainTime = needTime;
//
时间等于所需时间
isFirstExe =
true
;
//
是第一次指行
arriveTime = 0;
//
到达时间设为0
priority = 0;
//
优先级设为0
turnaroundTime = 0;
//
轮转时间设为0
next =
NULL
;
//
初始的下一个事件为空
}
//
带参构造
Process_Control_Block
::Process_Control_Block(
string
pcb_name
,
int
pcb_atime
,
int
pcb_priority
) {
name
=
pcb_name
;
arriveTime =
pcb_atime
;
priority =
pcb_priority
;
needTime = 1 + rand() % 10;
//
随机生成所需时间
state =
PCB_State
::
READY
;
//
状态设为就绪
runTime = 0;
//
已运行时间设为0
beginTime = 0;
//
发生时间设为0
endTime = 0;
//
结束时间设为0
turnaroundTime = 0;
//
轮转时间设为0
isFirstExe =
true
;
//
是第一次指行
remainTime = needTime;
//
时间等于所需时间
next =
NULL
;
//
初始的下一个事件为空
}
2
、
PCB_LIST
类：
//
获得平均响应时间
double
PCB_LIST
::getResponseTime() {
PCB
* p = head->next;
double
sum = 0;
double
n = getSize();
if
(p->next == head)
return
-1;
while
(p != head) {
sum = sum + (p->beginTime – p->arriveTime);
p = p->next;
}
return
sum / n;
}
void
PCB_LIST
::clear_list() {
PCB
* p = head->next;
while
(p != head) {
head->next = p->next;
delete
p;
p = head->next;
}
}
//
获得吞吐量
double
PCB_LIST
::getThroughput() {
if
(!isEmpty()) {
double
sum_time = getTail()->endTime;
double
n = getSize();
return
n / sum_time;
}
return
0;
}
//
计算平均等待时间
double
PCB_LIST
::getAverWaitTime() {
PCB
* p = head->next;
double
sum = 0;
double
n = getSize();
if
(p->next == head)
return
-1;
while
(p != head) {
sum = sum + (p->endTime – p->arriveTime – p->runTime);
p = p->next;
}
return
sum / n;
}
//
获得平均轮转时间
double
PCB_LIST
::getAverTurnTime() {
PCB
* p = head->next;
double
sum = 0;
double
n = getSize();
if
(p->next == head)
return
-1;
while
(p != head) {
sum += p->turnaroundTime;
p = p->next;
}
return
sum / n;
}
//
获得尾部结点
PCB
*
PCB_LIST
::getTail() {
PCB
* p = head;
if
(p->next == head)
return
NULL
;
while
(p->next != head) {
p = p->next;
}
return
p;
}
//
获得队列长度
int
PCB_LIST
::getSize() {
int
cont = 0;
PCB
* p = head->next;
while
(p != head) {
p = p->next;
cont++;
}
return
cont;
}
//
插入到队列最后
void
PCB_LIST
::InsertAtTail(
PCB
*
pcb
) {
PCB
* p = head;
PCB
* new_pcb =
new
PCB
(
pcb
);
while
(p->next != head) {
p = p->next;
}
p->next = new_pcb;
new_pcb->next = head;
}
//
更新某进程的状态
bool
PCB_LIST
::updata(
PCB
*
pcb
) {
PCB
* p = head->next;
if
(p == head) {
//
如为空返回
return
false
;
}
while
(p != head && p->name
!=
pcb
->name) {
//
找到要删除结点的前一个
p = p->next;
}
if
(p == head) {
//
如没找到，返回false
return
false
;
}
CopyPCB(p,
pcb
);
return
true
;
}
//
按进程剩余时间插入
void
PCB_LIST
::InsertByRemainTime(
PCB
*
pcb
) {
PCB
* p = head;
PCB
* new_pcb =
new
PCB
(
pcb
);
while
(p->next != head && p->next->remainTime <
pcb
->remainTime) {
p = p->next;
}
if
(p == head && head->next == head) {
//
如链表中只有头结点
head->next = new_pcb;
new_pcb->next = head;
}
else
if
(p->next == head) {
//
如果要插在最后
p->next = new_pcb;
new_pcb->next = head;
}
else
{
//
在中间插入
PCB
* q = p->next;
p->next = new_pcb;
new_pcb->next = q;
}
}
//
按进程优先级插入
void
PCB_LIST
::InsertByPriority(
PCB
*
pcb
) {
PCB
* p = head;
PCB
* new_pcb =
new
PCB
(
pcb
);
while
(p->next != head && p->next->priority <
pcb
->priority) {
p = p->next;
}
if
(p == head && head->next == head) {
//
如链表中只有头结点
head->next = new_pcb;
new_pcb->next = head;
}
else
if
(p->next == head) {
//
如果要插在最后
p->next = new_pcb;
new_pcb->next = head;
}
else
{
//
在中间插入
PCB
* q = p->next;
p->next = new_pcb;
new_pcb->next = q;
}
}
//
按到达时间插入
void
PCB_LIST
::InsertByArriveTime(
PCB
*
pcb
) {
PCB
* p = head;
PCB
* new_pcb =
new
PCB
(
pcb
);
while
(p->next != head && p->next->arriveTime <
pcb
->arriveTime) {
p = p->next;
}
if
(p == head && head->next == head) {
//
如链表中只有头结点
head->next = new_pcb;
new_pcb->next = head;
}
else
if
(p->next == head) {
//
如果要插在最后
p->next = new_pcb;
new_pcb->next = head;
}
else
{
//
在中间插入
PCB
* q = p->next;
p->next = new_pcb;
new_pcb->next = q;
}
}
//
按进程所需时间插入
void
PCB_LIST
::InsertByNeedTime(
PCB
*
pcb
) {
PCB
* p = head;
PCB
* new_pcb =
new
PCB
(
pcb
);
while
(p->next != head && p->next->needTime <
pcb
->needTime) {
p = p->next;
}
if
(p == head && head->next == head) {
//
如链表中只有头结点
head->next = new_pcb;
new_pcb->next = head;
}
else
if
(p->next == head) {
//
如果要插在最后
p->next = new_pcb;
new_pcb->next = head;
}
else
{
//
在中间插入
PCB
* q = p->next;
p->next = new_pcb;
new_pcb->next = q;
}
}
//
按进程结束时间插入
void
PCB_LIST
::InsertByEndTime(
PCB
*
pcb
) {
PCB
* p = head->next;
PCB
* new_pcb =
new
PCB
(
pcb
);
while
(p->next != head && p->next->endTime <
pcb
->endTime) {
p = p->next;
}
if
(p == head && head->next == head) {
//
如链表中只有头结点
head->next = new_pcb;
new_pcb->next = head;
}
else
if
(p->next == head) {
//
如果要插在最后
p->next = new_pcb;
new_pcb->next = head;
}
else
{
//
在中间插入
PCB
* q = p->next;
p->next = new_pcb;
new_pcb->next = q;
}
}
//
根据进程名删除进程
bool
PCB_LIST
::deleteByName(
string
pcb_name
) {
PCB
* p = head;
if
(p->next == head) {
//
如链表为空返回
return
false
;
}
while
(p->next != head && p->next->name
!=
pcb_name
) {
//
找到要删除结点的前一个
p = p->next;
}
if
(p->next == head) {
//
如没找到，返回false
return
false
;
}
else
{
PCB
* q = p->next;
//q
为要删除结点
p->next = q->next;
delete
q;
}
return
true
;
}
//
打印全部进程状态
void
PCB_LIST
::showAll() {
PCB
* p = head->next;
while
(p != head) {
p->showPCB();
p = p->next;
}
}
//
判断是否为空表
bool
PCB_LIST
::isEmpty() {
if
(head->next == head)
return
true
;
return
false
;
}
//
获取队列中第一个PCB
PCB
*
PCB_LIST
::FetchFirstPCB() {
if
(head->next == head)
return
NULL
;
return
head->next;
}
运行截图：
1
、测试数据：
2
、运行结果
①
SRTF
：
②SJF：
③
FCFS
：
④
Priority
：
⑤
Round_Robin
