目录
先来先服务调度算法:
先来先服务(FCFS)调度算法是一种最简单的调度算法,该算法既可用于作业调度,也可用于进程调度。当在作业调度中采用该算法时,每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业,将它们调入内存,为它们分配资源、创建进程,然后放入就绪队列。在进程调度中采用FCFS算法时,则每次调度是从就绪队列中选择一个最先进入该队列的进程,为之分配处理机,使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。
短进程优先调度算法:
短作业(进程)优先调度算法SJ(P)F,是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业,将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程,将处理机分配给它,使它立即执行并一直执行到完成,或发生某事件而被阻塞放弃处理机时再重新调度。
两种进程调度算法优缺点
|
优点 |
缺点 |
先来先服务调度算法 |
|
|
短进程优先调度算法 |
|
|
思维导图
程序代码:
/*
实验题目:先来先服务FCFS和短作业优先SJF进程调度算法
*******实验要求*********
1. 先来先服务调度算法FCFS:
1)是一种最简单的调度算法,适用于作业调度和进程调度
2)每次调度都是从后备队列中选择一个或者多个最先进入该队列的作业,将它们调入内存,分配资源,创建进程,然后放入就绪队列
3)FCFS算法比较有利于长作业(进程),不利于短作业(进程)
4)既可用于作业调度,也可用于进程调度
2. 周转时间 = 完成时间 - 到达时间
带权周转时间 = 周转时间/服务时间
*/
#include<stdio.h>
#include <stdlib.h> //malloc的头文件
#include <time.h>
#include <math.h>
struct node { //进程控制块
char name;
double arr; //到达时间
double ing; //服务时间
double finish;//结束时间
double round; //周转时间
double daiquan;//带权周转时间
double pingjunround; //平均周转时间
double pingjundaiquan; //平均带权周转时间
}ai[100];
node t;
void FCFS()
{
int n,i;
printf("请输入进程个数:\n");
scanf("%d", &n);
printf("请输入%d个进程的名字\n", n);
for (i = 0;i<n;i++)
{
getchar();
scanf("%s",&ai[i].name);
ai[i].arr = (double)(rand()%10 + 1); //随机
ai[i].ing = (double)(rand()%10 + 1); //随机
}
//排序
for (i = 1; i < n; i++)
{
for (int j = 0; j < n - i; j++)
{
if (ai[j].arr > ai[j + 1].arr)
{
t = ai[j];
ai[j] = ai[j + 1];
ai[j + 1] = t;
}
}
}
printf("进程名 \t到达时间\t服务时间\t结束时间\t周转时间\t平均周转时间\t带权周转时间\t平均带权周转时间\n");
ai[0].finish =ai[0].arr+ai[0].ing;
ai[0].round=ai[0].finish-ai[0].arr;
ai[0].daiquan=ai[0].round/ai[0].ing;
ai[0].pingjunround=ai[0].round;
ai[0].pingjundaiquan=ai[0].daiquan;
printf("%c \t%.2lf \t\t%.2lf \t\t%.2lf \t\t%.2lf \t\t%.2lf \t\t%.2lf \t\t%.2lf\n",ai[0].name,ai[0].arr,ai[0].ing,ai[0].finish,ai[0].round,ai[0].pingjunround,ai[0].daiquan,ai[0].pingjundaiquan);
for (i = 1;i<n;i++)
{
ai[i].finish = ai[i-1].finish + ai[i].ing;
ai[i].round = ai[i].finish - ai[i].arr;
ai[i].daiquan = ai[i].round / ai[i].ing;
ai[i].pingjunround=(ai[i].round+ai[i-1].round)/(double)(i+1);
ai[i].pingjundaiquan=(ai[i].daiquan+ai[i-1].daiquan)/(double)(i+1);
printf("%c \t%.2lf \t\t%.2lf \t\t%.2lf \t\t%.2lf \t\t%.2lf \t\t%.2lf \t\t%.2lf\n",ai[i].name,ai[i].arr,ai[i].ing,ai[i].finish,ai[i].round,ai[i].pingjunround,ai[i].daiquan,ai[i].pingjundaiquan);
}
}
void SPF()
{
int n,i,time=0;
printf("请输入进程个数:\n");
scanf("%d", &n);
printf("请输入%d个进程的名字\n", n);
for (i = 0;i<n;i++)
{
getchar();
scanf("%s",&ai[i].name);
ai[i].arr = (double)(rand()%10 + 1);
ai[i].ing = (double)(rand()%10 + 1);
}
for ( i = 1; i<n; i++)
{
for (int j = 0; j<n - i; j++)
{
if (ai[j].arr>ai[j + 1].arr)//将到达时间短的交换到前边
{
t = ai[j];
ai[j] = ai[j + 1];
ai[j + 1] = t;
}
}
for (int k = 0; k < n - i; k++)
{
if ((ai[k].ing > ai[k + 1].ing) && (ai[k].arr >= ai[k + 1].arr))//将服务时间短的交换到前边
{
t = ai[k];
ai[k] = ai[k + 1];
ai[k + 1] = t;
}
}
}
printf("进程名 \t到达时间\t服务时间\t结束时间\t周转时间\t平均周转时间\t带权周转时间\t平均带权周转时间\n");
ai[0].finish =ai[0].arr+ai[0].ing;
ai[0].round=ai[0].finish-ai[0].arr;
ai[0].daiquan=ai[0].round/ai[0].ing;
ai[0].pingjunround=ai[0].round;
ai[0].pingjundaiquan=ai[0].daiquan;
printf("%c \t%.2lf \t\t%.2lf \t\t%.2lf \t\t%.2lf \t\t%.2lf \t\t%.2lf \t\t%.2lf\n",ai[0].name,ai[0].arr,ai[0].ing,ai[0].finish,ai[0].round,ai[0].pingjunround,ai[0].daiquan,ai[0].pingjundaiquan);
for (i = 1; i < n; i++) //排序
{
for (int j = i; j < n - 1; j++)
{
for (int d = i + 1; d<n; d++)
if ((ai[i - 1].finish >= ai[j].arr) && (ai[i - 1].finish >= ai[d].arr) && (ai[j].ing > ai[d].ing))
{
t = ai[j];
ai[j] = ai[d];
ai[d] = t;
}
}
if (ai[i].arr<ai[i - 1].finish) //当前到达时间在上一个作业结束时间之前
{
ai[i].finish = ai[i - 1].finish + ai[i].ing;
ai[i].round = ai[i].finish - ai[i].arr;
ai[i].daiquan = ai[i].round / ai[i].ing;
ai[i].pingjunround=(ai[i].round+ai[i-1].round)/(double)(i+1);
ai[i].pingjundaiquan=(ai[i].daiquan+ai[i-1].daiquan)/(double)(i+1);
}
else //当前到达时间在上一个作业结束时间之后
{
ai[i].finish = ai[i].arr + ai[i].ing;
ai[i].round = ai[i].finish - ai[i].arr;
ai[i].daiquan = ai[i].round / ai[i].ing;
ai[i].pingjunround=(ai[i].round+ai[i-1].round)/(double)(i+1);
ai[i].pingjundaiquan=(ai[i].daiquan+ai[i-1].daiquan)/(double)(i+1);
}
}
for (i = 1;i<n;i++)
{
printf("%c \t%.2lf \t\t%.2lf \t\t%.2lf \t\t%.2lf \t\t%.2lf \t\t%.2lf \t\t%.2lf\n",ai[i].name,ai[i].arr,ai[i].ing,ai[i].finish,ai[i].round,ai[i].pingjunround,ai[i].daiquan,ai[i].pingjundaiquan);
}
}
int main()
{
srand( (unsigned)time( NULL ) ); //随机
printf("请选择算法“1-FCFS,2-SPF”\n");
int choose;
scanf("%d",&choose);
if(choose==1){ FCFS(); }
else if(choose==2) { SPF(); }
return 0;
}