作业调度算法(先来先服务算法,短作业算法).doc

《操作系统》实验报告

题目：作业调度算法
班级：网络工程
姓名：朱锦涛
学号：E31314037

一、实验目的
用代码实现页面调度算法，即先来先服务（FCFS）调度算法
、短作业优先算法、高响应比优先调度算法。通过代码的具体实现，加深对算法的核心的理解。
二、实验原理
1.先来先服务（FCFS）调度算法
FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行的时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。
2.短作业优先算法
SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存。
3、高响应比优先调度算法
高响应比优先调度算法则是既考虑了作业的等待时间，又考虑了作业的运行时间的算法，因此既照顾了短作业，又不致使长作业等待的时间过长，从而改善了处理机调度的性能。
如果我们引入一个动态优先级，即优先级是可以改变的令它随等待的时间的延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。该优先级的变化规律可以描述为：
优先权 = （等待时间 + 要求服务时间）/要求服务时间
三、实验内容
源程序：
#include
#include
#include

struct work
{
int id;
int arrive_time;
int work_time;
int wait;
float priority;
};

typedef struct sjf_work
{
struct work s_work; //数据域
struct sjf_work * pNext; //指针域
}NODE,*PNODE;

void FCFS();
void SJF();
void showmenu();
bool Is_empty(PNODE pHead);
int cnt_work(PNODE pHead);
PNODE do_work(PNODE pHead,int *w_finish_time,int i);
void show(int *w_finish_time,int i,PNODE q,int w_rel_time);
void HRRN();
PNODE priorit(PNODE pHead);
void do_work_1(PNODE pHead,int *w_finish_time,int i);

int main()
{
int choice; //设置选择数
showmenu(); //显示菜单
scanf("%d",&choice);
while(choice != 0) //选择算法
{
switch(choice)
{
case 1 :
printf("您选择的是先来先服务算法:\n");

FCFS();
break;
case 2 :
printf("您选择的是短作业优先算法:\n");
SJF();
break;
case 3 :
printf("您选择的是高响应比优先调度算法\n");
HRRN();
break;
default:
printf("请重新选择！");
break;
}
printf("\n");
printf("下面是菜单，请继续，或者按‘0’退出");
showmenu();
scanf("%d",&choice);
}
printf("感谢您使用本系统，再见！");

return 0;
}

void FCFS()
{
int j,k;
int w_rel_time[5];
int w_finish_time[5];
float rel_time = 0;
struct work temp;
int i;
struct work w[5];
srand(time(0));
for(i=0;i<5;i++)
{
w[i].id = rand()%10;
w[i].arrive_time = rand()%10;
w[i].work_time = rand()%10+1;
}
for(j=0;j<5;j++)
{
printf("第%d个作业的编号是：%d\t",j+1,w[j].id);
printf("第%d个作业到达时间：%d\t",j+1,w[j].arrive_time);
printf("第%d个作业服务时间：%d\t",j+1,w[j].work_time);
printf("\n");

}

for(j=1;j<5;j++)
for(k=0;k<5-j;k++)
{
if(w[k].arrive_time > w[k+1].arrive_time)
{
temp = w[k];
w[k] = w[k+1];
w[k+1] = temp;
}
}
printf("\n");

w_finish_time[0] = w[0].arrive_time + w[0].work_time;
for(j=0;j<5;j++)
{
if(w_finish_time[j] < w[j+1].arrive_time)
{
w_finish_time[j+1] = w[j+1].arrive_time + w[j+1].work_time;

}
else
w_finish_time[j+1] = w_finish_time[j] + w[j+1].work_time;

}
for(j=0;j<5;j++)
w_rel_time[j] = w_finish_time[j] - w[j].arrive_time;
for(j=0;j<5;j++)
{
rel_time += w_rel_time[j];
}

for(j=0;j<5;j++)
{
printf("第%d个系统执行的作业到达时间：%d ",j+1,w[j].arrive_time);
printf("编号是：%d ",w[j].id);
printf("服务时间是：%d ",w[j].work_time);
printf("完成时间是：%d ",w_finish_time[j]);
printf("周转时间是：%d ",w_rel_time[j]);

printf("\n");

}

printf("平均周转时间：%f\n",rel_time/5);
}

void SJF()
{
int w_rel_time[10];
int w_finish_time[10];
float rel_time = 0;
srand(time(0));
int i;
int j = 0;
PNODE pHead = (PNODE)malloc(sizeof(NODE));
if (NULL == pHead)
{
printf("分配失败, 程序终止!\n");
exit(-1);
}
PNODE pTail = pHead;
pTail->pNext = NULL; //定义该链表有头结点，且第一个节点初始化为空

for(i=0;i<10;i++)
{
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if (NULL == pNew)
{
printf("分配失败, 程序终止!\n");
exit(-1);
}
pNew->s_work.id = rand()%100;
pNew->s_work.arrive_time = rand()%10;
pNew->s_work.work_time = rand()%10+1;
pTail->pNext = pNew;
pNew->pNext = NULL;
pTail = pNew;
}

PNODE p = pHead->pNext; //p指向第一个节点

while (NULL != p)
{
printf("第%d个作业的编号是：%d\t",j+1,p->s_work.id);
printf("第%d个作业到达时间：%d\t",j+1,p->s_work.arrive_time);
printf("第%d个作业服务时间：%d\t",j+1,p->s_work.work_time);
printf("\n");
p = p->pNext;
printf("\n");
j++;

}
p = pHead->pNext;
PNODE q = p; //p,q都指向第一个节点
p = p->pNext;
while(p != NULL)
{
if(p->s_work.arrive_time < q->s_work.arrive_time)
q = p;
p = p->pNext;
}
PNODE r = pHead->pNext; //r也指向第一个节点
int cnt = 0; //记录所有节点数据域中到达时间最短且相等的个数
while(r!= NULL)

{
if( r->s_work.arrive_time == q->s_work.arrive_time )
cnt++;
r = r->pNext;
}
p = pHead->pNext;
while(p != NULL) //在相等到达时间的作业中找服务时间最短的作业
{
if(cnt > 1)
{
if( p->s_work.arrive_time == q->s_work.arrive_time )
if( p->s_work.work_time < q->s_work.work_time )
q = p
p = p->pNext;
}
else
p =NULL;
} //确定q所指作业最先到达且服务时间最短
w_finish_time[0] = q->s_work.arrive_time + q->s_work.work_time;
w_rel_time[0] = w_finish_time[0] - q->s_work.arrive_time;
printf("第1个系统执行的作业到达时间：%d ",q->s_work.arrive_time);
printf("编号是：%d ",q->s_work.id);
printf("服务时间是：%d \n",q->s_work.work_time);
printf("完成时间是：%d ",w_finish_time[0]);
printf("周转时间是：%d \n",w_rel_time[0]);

p = pHead; //寻找q的前一个节点，方便删掉q节点
while( p->pNext != q )
{
p = p->pNext;
}
p->pNext = q->pNext;
free(q);
q = NULL;

for(i=0;i<9&&!Is_empty(pHead);i++)
{
printf("现在系统还剩%d个作业！\n",cnt_work(pHead));
q = do_work(pHead,w_finish_time,i);
show(w_finish_time,i,q,w_rel_time);
p = pHead; //寻找q的前一个节点，方便删掉q节点
while( p->pNext != q )
{
p = p->pNext;
}
p->pNext = q->pNext;
free(q);
q = NULL;
}

for(j=0;j<10;j++)
{
rel_time += w_rel_time[j];
}
printf("平均周转时间：%f\n",rel_time/10);

}

bool Is_empty(PNODE pHead) //判断作业是否做完
{
PNODE p;
p = pHead->pNext;
int len = 0;
while(p != NULL)
{
len++;
p = p->pNext;
}
if(len == 0)
return true; //当没有作业时，返回为真
else
return false;
}

int cnt_work(PNODE pHead) //计算当前还剩多少作业
{
PNODE p;
p = pHead->pNext;
int len = 0;
while(p != NULL)
{
len++;
p = p->pNext;
}
return len;
}

PNODE do_work(PNODE pHead,int *w_finish_time,int i)
{
PNODE p,q;
int cnt = 0; //计数器清0，计算当前作业完成时，系统中有多少个作业已经到达
p = pHead->pNext
q = p;
while(p != NULL)
{
if( p->s_work.arrive_time <= w_finish_time[i] )
{
cnt ++;
q = p;
p = p->pNext;
}
else
{
p = p->pNext;
}
} //q指向当前到达时间小于刚刚完成的作业，但不一定是服务时间最短的(如果有的话)
printf("系统中有%d个作业在当前作业完成时已经到达！\n",cnt);
p = pHead->pNext;
while(p != NULL)
{
if(cnt>1) //执行此次判断后，q现在指向所有条件都满足的作业（如果有的话）
{
if( p->s_work.arrive_time <= w_finish_time[i] )
{
if( p->s_work.work_time < q->s_work.work_time )
{
q = p;
p = p->pNext;
}
else
p = p->pNext;
}
else
p = p->pNext;
}
else //当前作业完成时，没有作业到达的情况
{
p = p->pNext; //用q来接收最先到达的，用p来遍历
while( p != NULL )
{
if( p->s_work.arrive_time< q->s_work.arrive_time )
q = p;
p = p->pNext;

}
w_finish_time[i+1] = q->s_work.arrive_time + q->s_work.work_time;
}
}
w_finish_time[i+1] = wfinish_time[i] + q->s_work.work_time;
return q;
}

void show(int *w_finish_time,int i,PNODE q,int *w_rel_time)
{
w_finish_time[i+1] = w_finish_time[i] + q->s_work.work_time;
w_rel_time[i+1] = w_finish_time[i+1] - q->s_work.arrive_time;
printf("第%d个系统执行的作业到达时间：%d ",i+2,q->s_work.arrivetime);
printf("编号是：%d ",q->s_work.id);
printf("服务时间是：%d\n",q->s_work.work_time);
printf("完成时间是：%d ",w_finish_time[i+1]);
printf("周转时间是：%d \n",w_rel_time[i+1]);

}

void showmenu()
{
printf("**********************************\n");
printf("请选择你要执行的命令~: \n");
printf("1：先来先服务算法\n");
printf("2：短作业优先算法\n");
printf("3: 高响应比优先算法\n");
printf("0: 退出菜单\n");
printf("**********************************\n");
}

void HRRN()
{
int w_rel_time[10];
int w_finish_time[10];
float rel_time = 0;
float priority; //计算优先权
srand(time(0));
int i;
int j = 0;
PNODE pHead = (PNODE)malloc(sizeof(NODE));
if (NULL == pHead)
{
printf("分配失败, 程序终止!\n");
exit(-1);
}
PNODE pTail = pHead;
pTail->pNext = NULL; //定义该链表有头结点，且第一个节点初始化为空

for(i=0;i<10;i++) //定义了十个进程
{
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if (NULL == pNew)
{
printf("分配失败, 程序终止!\n");
exit(-1);
}
pNew->s_work.id = rand()%100;
pNew->s_work.arrive_time = rand()%10;
pNew->s_work.work_time = rand()%10+1;
pTail->pNext = pNew;
pNew->pNext = NULL;
pTail = pNew;
}

PNODE p = pHead->pNext; //p指向第一个节点

while (NULL != p)
{
printf("第%d个作业的编号是：%d\t",j+1,p->s_work.id);
printf("第%d个作业到达时间：%d\t",j+1,p->s_work.arrive_time);
printf("第%d个作业服务时间：%d\t",j+1,p->s_work.work_time);
printf("\n");
p = p->pNext;
printf("\n");
j++;

}
p = pHead->pNext;
PNODE q = p; //p,q都指向第一个节点
p = p->pNext;
while(p != NULL)
{
if(p->s_work.arrive_time < q->s_work.arrive_time)
q = p;
p = p->pNext;
}
PNODE r = pHead->pNext; //r也指向第一个节点
int cnt = 0; //记录所有节点数据域中到达时间最短且相等的个数
while(r!= NULL)
{
if( r->s_work.arrive_time == q->s_work.arrive_time )
cnt++;
r = r->pNext;
}
p = pHead->pNext;
while(p != NULL) //在相等到达时间的作业中找服务时间最短的作业
{
if(cnt > 1)
{
if( p->s_work.arrive_time == q->s_work.arrive_time )
if( p->s_work.work_time < q->s_work.work_time )
q = p;
p = p->pNext;
}
else
p =NULL;
} //确定q所指作业最先到达且服务时间最短
w_finish_time[0] = q->s_work.arrive_time + q->s_work.work_time;
w_rel_time[0] = w_finish_time[0] - q->s_work.arrive_time;
printf("第1个系统执行的作业到达时间：%d ",q->s_work.arrive_time);
printf("编号是：%d ",q->s_work.id);
printf("服务时间是：%d \n",q->s_work.work_time);
printf("完成时间是：%d ",w_finish_time[0]);
printf("周转时间是：%d \n",w_rel_time[0]);

p = pHead; //寻找q的前一个节点，方便删掉q节点
while( p->pNext != q )
{
p = p->pNext;
}
p->pNext = q->pNext;
free(q);
q = NULL; //已经找到并执行第一个进程，执行完之后又将其删除了

for(i=0;i<9&&!Is_empty(pHead);i++)
{
printf("现在系统还剩%d个作业！\n",cnt_work(pHead));
do_work_1(pHead,w_finish_time,i)
q = priorit(pHead);
show(w_finish_time,i,q,w_rel_time);
p = pHead; //寻找q的前一个节点，方便删掉q节点
while( p->pNext != q )
{
p = p->pNext;
}
p->pNext = q->pNext;
free(q);
q = NULL;
}

for(j=0;j<10;j++)
{
rel_time += w_rel_time[j];
}
printf("平均周转时间：%f\n",rel_time/10);

}

void do_work_1(PNODE pHead,int *w_finish_time,int i)
{
PNODE p,q;
int cnt = 0; //计数器清0，计算当前作业完成时，系统中有多少个作业已经到达
p = pHead->pNext;
q = p;
while(p != NULL)
{
if( p->s_work.arrive_time <= w_finish_time[i] )
{
cnt ++;
q = p;
p = p->pNext;
}
else
{
p = p->pNext;
}
} //q指向当前到达时间小于刚刚完成的作业，但有可能有另外几个进程也已经到达了，所以要进行下面的判断
printf("系统中有%d个作业在当前作业完成时已经到达！\n",cnt);
p = pHead->pNext;
while(p != NULL)
{
if(cnt>1) //说明此时有好几个都已经到达了
{
if(p->s_work.arrive_time <= w_finish_time[i])
{
p->s_work.wait = w_finish_time[i] - p->s_work.arrive_time;
p = p->pNext;
}
else
{
p->s_work.wait = 0;
p = p->pNext;
}

}
else //当前作业完成时，没有作业到达的情况
{
p = p->pNext; //此时p指向第一个节点，q指向第二个节点，还是找最先到达的
while( p != NULL )
{
if( p->s_work.arrive_time < q->s_work.arrive_time )
q = p;
p = p->pNext;
}
w_finish_time[i+1] = q->s_work.arrive_time + q->s_work.work_time;
return;
}
}
w_finish_time[i+1] = w_finish_time[i] + q->s_work.work_time;
}

PNODE priorit(PNODE pHead)
{
PNODE p = pHead->pNext;
while(p != NULL)
{
if(p->s_workwait > 0)
{
p->s_work.priority = (p->s_work.wait + p->s_work.work_time) / p->s_work.work_time; //计算每一个已经等待的进程的优先等级
p = p->pNext;
}
else
p = p->pNext;
}
p = pHead->pNext;
PNODE q;
q = p;
p = p->pNext; //p已经指向第二个节点
while(p != NULL)
{
if(p->s_work.wait > 0)
{
if(p->s_work.priority > q->s_work.priority)
{
q = p;
p = p->pNext;
}
else
p = p->pNext;
}
else
p = p->pNext;
}
printf("该进程优先级最高，为：%f\n",q->s_work.priority);
return q;

}
实验结果：
系统自动为每个算法模拟分配五个作业，同时随机生成作业的编号，作业的到达时间，作业估计运行的时间。
1.先来先服务算法

该算法严格按照各作业到达时间来为其分配进程和资源，实验的结果见截图，最后算出该算法五个作业的平均周转时间。
2.短作业优先
短作业优先算法考虑的比较多，系统先找出最先到达的作业，若有多个相同时间到达的作业，则按照其运行时间长短先为时间短的服务。

3.高响应比优先算法

代码中主要运用PNODE priorit(PNODE pHead)函数计算作业的优先权。
四.实验小结
通过的代码的实现，对三种作业调度算法有了更深的理解。短作业优先算法要考虑的是后备队列