2020-04-06
以下是源代码
#include
#include
#include
#define TRUE 1
#define FALSE 0
//作业数组大小
#define LEN 5
/*
**
** 各种调度算法模拟仿真(链式存储的队列实现版):
** 短作业优先调度算法 (SJF)、先来先服务调度算法 (FCFS)
** 时间片轮转调度算法 (RR) 、最高响应比调度算法(HRRN)
** Author:贾志洋
** version:1.0
** Create Time: 2020/4/05 22:09
** Modified Time:
*/
/*进程PCB结点结构体*/
typedef struct job
{
int PID;
//进程的PID
int arrival_time;
//进程到达系统时间
int require_time_slice;
//要求服务时间
【2020-04-06】 int used_time_slice;
//已经使用的时间片(短作业优先用不到该值)
int ended_time;
//进程完成时间 ,初始值为-1,表示进程未完成,如果该进程已经完成则>=0
int waited_time;
//等待时间,等待时间=周转时间-要求服务时间
int cycle_time;
//周转时间,周转时间=结束时间-到达时间
float weight_cycle_time;
//带权周转时间,带权周转时间=周转时间/要求服务时间
struct job * next;
//所在队列的下一个作业
}job;
/*作业队列的结构体*/
typedef struct linked_queue
{
job * front;
//队头指向结点的指针
job * rear;
//队尾指向结点的指针
int count;
//队列当前长度
}linked_queue;
//作业数组全局变量
struct job job_array[LEN];
//后备队列
linked_queue * created_queue;
//就绪队列
linked_queue * ready_queue;
//完成队列
linked_queue * ended_queue;
//初始化作业数组的每个作业信息
void init_jobs();
//初始化各个队列
void init_queues();
//打印菜单
void print_menu();
//短作业优先调度算法 (SJF)
void sjf_jobs();
//先来先服务调度算法 (FCFS)
void fcfs_jobs();
//时间片轮转调度算法 (RR)
void rr_jobs(int q);
//最高响应比调度算法(HRRN)
void hrrn_jobs();
//打印输出所有作业的各种时间平均值
void print_average_value();
//作业出队列函数
job * de_queue(linked_queue * queue);
//返回队头作业(不出队)
job * peek_queue(linked_queue * queue);
//计算该作业的各种时间
void record_job_time(job * record_job);
//作业结点入队
void en_queue_node(linked_queue * queue,job * en_queue_pcb_node);
/*程序入口*/
int main()
{
//记录用户键盘输入的选择键
char user_opt;
while(1)
{
//初始化作业数组中每个作业
init_jobs();
//初始化各个队列
init_queues();
//打印菜单
print_menu();
scanf("%c", &user_opt);
getchar();
switch(user_opt)
{
case '1' :
sjf_jobs();
break;
case '2':
fcfs_jobs();
break;
case '3':
rr_jobs(1);
break;
case '4':
rr_jobs(4);
break;
case '5':
hrrn_jobs();
break;
case 'q':
exit(0);
break;
}
}
return 0;
}
void print_menu()
{
printf("\n======================\n");
printf("按1键SJF \n");
printf("按2键FCFS\n");
printf("按3键RR时间片轮转(q=1)\n");
printf("按3键RR时间片轮转(q=4)\n");
printf("按3键HRRN\n");
printf("按q键退出 \n");
printf("您的选择: \n");
printf("\n======================\n");
}
void init_jobs()
{
//根据题目要求的表格初始化每个进程的信息(也可以通过控制台输入)
job_array[0].PID = 0;
job_array[0].require_time_slice = 3;
job_array[0].arrival_time = 0;
job_array[0].ended_time =-1;
job_array[0].used_time_slice = 0;
job_array[1].PID = 1;
job_array[1].require_time_slice = 6;
job_array[1].arrival_time = 2;
job_array[1].ended_time =-1;
job_array[1].used_time_slice = 0;
job_array[2].PID = 2;
job_array[2].require_time_slice = 4;
job_array[2].arrival_time = 4;
job_array[2].ended_time =-1;
job_array[2].used_time_slice = 0;
job_array[3].PID = 3;
job_array[3].require_time_slice = 5;
job_array[3].arrival_time = 6;
job_array[3].ended_time =-1;
job_array[3].used_time_slice = 0;
job_array[4].PID = 4;
job_array[4].require_time_slice = 2;
job_array[4].arrival_time = 8;
job_array[4].ended_time =-1;
job_array[4].used_time_slice = 0;
}
void init_queues()
{
//释放原来的
free(created_queue);
free(ready_queue);
free(ended_queue);
//后备队列
created_queue = (linked_queue*)malloc(sizeof(linked_queue));
//初始化队列
created_queue->front = created_queue->rear = NULL;
//就绪队列
ready_queue = (linked_queue*)malloc(sizeof(linked_queue));
//初始化队列
ready_queue->front = ready_queue->rear = NULL;
//完成队列
ended_queue = (linked_queue*)malloc(sizeof(linked_queue));
//初始化队列
ended_queue->front = ended_queue->rear = NULL;
//将作业数组中所有作业放入后备队列
int i;
for(i=0;
i
}
void record_job_time(job * record_job)
{
//计算该作业的各种时间
record_job->cycle_time = record_job->ended_time - record_job->arrival_time;
record_job->waited_time = record_job->cycle_time - record_job->require_time_slice;
record_job->weight_cycle_time = (float)record_job->cycle_time / (float)record_job->require_time_slice;
}
void print_average_value()
{
//平均周转时间
float avg_cycle_time = 0;
//平均等待时间
float avg_waited_time = 0;
//平均带权周转时间
float avg_weight_cycle_time = 0;
//遍历作业数组,求和值
int i;
for(i=0;
i
avg_cycle_time += (float) job_array[i].cycle_time;
avg_waited_time += (float) job_array[i].waited_time;
avg_weight_cycle_time += job_array[i].weight_cycle_time;
}
//计算均值
avg_cycle_time = avg_cycle_time / (float) LEN;
avg_waited_time = avg_waited_time / (float) LEN;
avg_weight_cycle_time = avg_weight_cycle_time / (float) LEN;
printf("平均周转时间:%05.2f平均等待时间:%05.2f平均带权周转时间:%05.2f\n",avg_cycle_time,avg_waited_time,avg_weight_cycle_time);
}
void fcfs_jobs()
{
//先来先服务调度算法
int current_time = 0;
//当前运行的作业
job * running_job = NULL;
//后备队列不为空 或 就绪队列不为空 或 正在有作业运行则进行调度
while (!is_queue_empty(created_queue)||!is_queue_empty(ready_queue)||running_job!=NULL)
{
//把后备队列中,到达时间为当前系统时间的作业挂入就绪队列
while (!is_queue_empty(created_queue))
{
job * front_job = peek_queue(created_queue);
if (front_job->arrival_time==current_time)
{
//后备队列出队一个作业并挂入就绪队列
en_queue_node(ready_queue,de_queue(created_queue) );
}
else
{
//一定要有else,表示后备队列中的当前队头作业的到达系统时间大于系统当前时间,需要退出while循环
break;
}
}
//判断当前是否有进程使用CPU
if (running_job == NULL)
{
//无作业使用CPU,将就绪队列队头出队,去使用CPU
if (!is_queue_empty(ready_queue))
running_job = de_queue(ready_queue);
else
{
//为了增加程序的健壮性,可以用某些其它数据测试(本题目要求没有出现这种情况)
//需要考虑,当前就绪队列为空,但后备队列仍旧有未到达系统的作业,系统时间空转1个时间片
printf("系统%d时刻就绪队列空\n", current_time);
current_time++;
continue;
}
//printf("调度新的作业使用CPU:%d\n",running_job->PID);
}
else
{
//如果有作业正在使用CPU,判断其使用CPU时间是否已经满足其要求服务时间
if (running_job->used_time_slice==running_job->require_time_slice)
{
//该作业要求服务时间已满足
//记录作业完成时间
running_job->ended_time = current_time;
//将该作业挂入完成队列
en_queue_node(ended_queue,running_job);
//计算并存储各种时间
record_job_time(running_job);
printf("调作业%d已完成,完成时间:%d\n",running_job->PID,running_job->ended_time);
//从就绪队列调度新的作业使用CPU
if (!is_queue_empty(ready_queue))
running_job = de_queue(ready_queue);
else
running_job = NULL;
}
else
{
//空实现
}
}
//系统时间步进
current_time++;
//当前正在运行的作业的使用的时间片++
if (running_job!=NULL)
running_job->used_time_slice++;
}
printf("SJF的调度信息:\n");
//打印该调度算法的各种时间的平均值
print_average_value();
}
void sjf_jobs()
{
//请实现,SJF算法
}
void rr_jobs(int q)
{
//请实现,时间片轮转RR算法,传入参数为时间片q的大小
}
void hrrn_jobs()
{
//请实现 ,最高响应比优先算法HRRN(非抢占),
}
//作业结点入队
void en_queue_node(linked_queue * queue,job * en_queue_pcb_node)
{
//将传入的Job作业结点入队
if (is_queue_empty(queue)){
queue->front = en_queue_pcb_node;
queue->rear = en_queue_pcb_node;
}else{
//队列非空,
queue->rear->next = en_queue_pcb_node;
queue->rear =en_queue_pcb_node;
}
}
//判断队列是否为空
int is_queue_empty(linked_queue * queue)
{
if ((queue->front==NULL)&&(queue->rear==NULL))
return TRUE;
else
return FALSE;
}
/*遍历队列,按顺序将队列中每个元素的值打印输出*/
void show_queue_all_job(linked_queue * queue){
if (is_queue_empty(queue)){
printf("队列为空,遍历结束\n");
return;
}
//游标指针
job * cursor_pcb_pointer;
cursor_pcb_pointer = queue->front;
printf("---------------\n");
printf("队列为:\n");
/*顺序遍历队列每个结点*/
while (cursor_pcb_pointer!=NULL){
//打印当前结点信息,
printf("结点PID:%d,时间片需求为:%d\n",cursor_pcb_pointer->PID,cursor_pcb_pointer->require_time_slice);
//后移游标指针
cursor_pcb_pointer=cursor_pcb_pointer->next;
}
printf("---------------\n");
}
job * de_queue(linked_queue * queue)
{
job * return_job;
if (is_queue_empty(queue)){
printf("队列为空,无法出队\n");
return NULL;
}
return_job = queue->front;
if (queue->front==queue->rear){
//只有一个结点时候
queue->front=queue->rear=NULL;
}else{
//多于一个结点时
queue->front = queue->front->next;
}
return_job->next = NULL;
return return_job;
}
//返回队头作业,但不出队
job * peek_queue(linked_queue * queue)
{
return queue->front;
}
推荐阅读
- 热闹中的孤独
- 我要做大厨
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量
- 爱就是希望你好好活着
- 太平之莲
- 知识
- 叙述作文
- 时间老了
- 清明,是追思、是传承、是感恩。
- 我错了,余生不再打扰