【操作系统】先来先服务和短作业优先算法（C语言实现）
- 2020 年 11 月 27 日
- 筆記
- C语言, 先来先服务和短作业优先进程调度算法, 操作系统
【操作系统】 先来先服务算法和短作业优先算法实现
介绍:
1.先来先服务 (FCFS: first come first service)
如果早就绪的进程排在就绪队列的前面，迟就绪的进程排在就绪队列的后面，那么先来先服务(FCFS: first come first service)总是把当前处于就绪队列之首的那个进程调度到运行状态。也就说，它只考虑进程进入就绪队列的先后，而不考虑它的下一个CPU周期的长短及其他因素。FCFS算法简单易行，是一种非抢占式策略，但性能却不大好。
简单来说，先来先服务就是那个进程到达时间最早，那么CPU就先处理哪个进程。
2.短作业优先（SJF, Shortest Job First）
对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业。
也就是说，不但要考虑进程的到达时间，还要考虑进程需要运行的时间。
当一个进程正在运行时，假如有其他的进程到达，那么这些到达的进程就需要按照其需要运行的时间长短排序，运行时间短的在前，运行时间长的在后。
例子：
话不多说，直接上代码。第一次写，有很多不足的地方。希望大家看到可以帮忙纠正一下，谢谢大家。
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
typedef struct PCB {
int id,arrive_time,service_time,start_time,finish_time; //进程id、到达时间、服务时间、开始时间、完成时间
float zhouzhuan_time,daiquanzhouzhuan_time; //周转时间、带权周转时间。。。只能说我的拼英。。。emm，。。尴尬。。
int status;
}PCB;
typedef enum {
OK,ERROR
}Status;
typedef enum {
FALSE,TRUE
}Bool;
typedef PCB datatype;
typedef struct LinkQueue {
int front;
int rear;
int length;
datatype* base;
}quene;
int arrive[MAX]; // 记录每个作业的到达时间
int service[MAX]; //记录每个作业的服务时间
int num; //输入的进程个数
quene init(){
quene q_pcb;
q_pcb.base = (datatype *)malloc(sizeof(datatype)*MAX);
q_pcb.front = q_pcb.rear = 0;
q_pcb.length = 0;
return q_pcb;
}
Bool isFull(quene *q) {
if ((q->rear + 1) % MAX == q->front) {
return TRUE;
}
return FALSE;
}
Bool isEmpty(quene *q) {
if (q->rear == q->front) {
return TRUE;
}
return FALSE;
}
Status rudui(quene *q,datatype p){ //入队。。。emmmm。。。尴尬。。。当时脑子抽了。。写成了拼英。 后来写完了。。。用的地方太多了。。就没修改了。。
if (isFull(q))
{
return ERROR;
}
*(q->base + q->rear) = p;
q->rear=(q->rear + 1) % MAX;
q->length ++;
return OK;
}
Status chudui(quene *q){ //出队。。。emmmm。。。尴尬。。。当时脑子抽了。。写成了拼英。 后来写完了。。。用的地方太多了。。就没修改了。。
if (isEmpty(q) == TRUE) {
return ERROR;
}
q->length --;
q->front = (q->front+1)%MAX;
return OK;
}
void input(quene *q) /* 建立进程控制块队列 */
{
printf("请输入进程的个数:\n");
scanf("%d",&num);
printf("请输入各进程的服务时间:\n");
int count = num;
int count2 = num;
int i = 0;
while(i < count2)
{
datatype temp;
temp.id = i;
temp.status = 0; //将所有的访问状态都置为0 表示未加入队列
scanf("%d",&temp.service_time);
service[i] = temp.service_time;
rudui(q,temp);
i ++;
}
i = 0;
printf("length=%4d\n",q->length);
printf("请输入各进程的到达时间:\n");
while (i < count)
{
scanf("%d",&(q->base+i)->arrive_time);
arrive[i] = (q->base+i)->arrive_time;
i ++;
}
}
void print_pcb(quene *q){ //格式化打印 ， 并计算相关的信息
float ave_zhouzhuan = 0;
float ave_daiquan = 0;
for (int i = 0; i < q->length; i++)
{
if(i == 0){
(q->base+i)->start_time = (q->base+i)->start_time; //第一个的开始时间
}
else
{
(q->base+i)->start_time = (q->base+i-1)->finish_time;
}
(q->base+i)->finish_time = (q->base+i)->start_time + (q->base+i)->service_time; //结束时间
(q->base+i)->zhouzhuan_time = (float)((q->base+i)->finish_time - (q->base+i)->arrive_time); //周转时间
if((q->base+i)->service_time == 0){
(q->base+i)->daiquanzhouzhuan_time = (q->base+i)->zhouzhuan_time;
}
else
{
(q->base+i)->daiquanzhouzhuan_time = (q->base+i)->zhouzhuan_time/(q->base+i)->service_time; //带权周转时间
}
ave_zhouzhuan += (q->base+i)->zhouzhuan_time;
ave_daiquan += (q->base+i)->daiquanzhouzhuan_time;
}
printf("进程ID\t到达时间\t服务时间\t开始时间\t结束时间\t周转时间\t带权周转时间\n");
for (int i = 0; i < q->length; i++)
{
printf("%4d\t%8d\t%8d\t%8d\t%8d\t%8f\t%8f\n",(q->base+i)->id,(q->base+i)->arrive_time,(q->base+i)->service_time,(q->base+i)->start_time,(q->base+i)->finish_time,(q->base+i)->zhouzhuan_time,(q->base+i)->daiquanzhouzhuan_time);
}
printf("平均周转时间=%f\n",ave_zhouzhuan/q->length);
printf("平均带权周转时间=%f\n",ave_daiquan/q->length);
}
void sort(int array[]){ //排序。 从大到小的顺序。
int temp;
for(int i = 0;i < num -1;i ++){
for(int j = i + 1;j < num;j ++){
if(array[i] > array[j]){
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
}
int select__min_arrive(quene *q){ //从到达的进程队列中挑选出到达时间最早的
int min = (q->base+q->front)->arrive_time;
for(int i = 1;i < q->length; i ++){
if (min > (q->base+q->front+i)->arrive_time && (q->base+q->front+i)->status == 0)
{
min = (q->base+q->front+i)->arrive_time;
}
}
return min;
}
int select__min_service(quene *qu){ //从到达的进程队列中挑选出所有进程中最短一个进程的服务时间
int min = (qu->base+qu->front)->service_time;
for(int i = 0;i < qu->length; i ++){
if (min > (qu->base+qu->front+i)->service_time && (qu->base+qu->front+i)->status == 0)
{
min = (qu->base+qu->front+i)->service_time;
}
}
return min;
}
int main(){
quene q = init();
input(&q);
int select;
sort(arrive); //按照到达时间排序
sort(service); // 按照服务时间长短排序
printf("\n");
printf("1.先来先服务\t2.短作业优先\t请输入你的选择：\n");
scanf("%d",&select);
quene new_q,new_quene; //两个队列。第一个表示先来先服务队列。第二个是短作业优先队列。
switch (select)
{
case 1:
new_q = init();
for(int i = 0;i < q.length; i ++){ //先来先服务 ： 按照到达时间排序然后依次查找入队列
for(int j = 0;j < q.length;j ++){
if((q.base+q.front+j)->arrive_time == arrive[i] && (q.base+q.front+j)->status == 0){
rudui(&new_q,*(q.base+j));
(q.base+j)->status = 1;
}
}
}
print_pcb(&new_q);
break;
case 2:
int flag = 0;
new_quene = init();
quene min_arrive = init(); //用来存放当一个进程正在运行时，新到达的队列
int count = 0;
for(int i = 0;i < q.length; i ++){ //先让第一个到达的入队列
for(int j = 0;j < q.length;j ++){
if(i == 0 && flag == 0){ //保证第一个到达作业装入系统
if((q.base+j)->arrive_time == arrive[0] && (q.base+j)->status == 0){
rudui(&new_quene,*(q.base+j));
(q.base+j)->status = 1; //防止重复访问
break;
}
}
else{ //后面的按照服务时间长短入队列
// if((q.base+j)->service_time == service[i] && (q.base+j)->status == 0){
// // sjf[index] = (q.base+j)->id;
// // index ++;
// rudui(&new_quene,*(q.base+j));
// (q.base+j)->status = 1;
// }
}
}
break;
}
int service,arrive,start,finish; //用于存放正在运行的进程的服务时间、到达时间、开始时间、完成时间。
for(int i = 0; i < q.length;i ++){ //按照sjf算法确定后续入队的顺序
if (i == 0)
{
start = (new_quene.base+i)->arrive_time;
(new_quene.base+i)->start_time = (new_quene.base+i)->arrive_time;
(new_quene.base+i)->finish_time = (new_quene.base+i)->arrive_time + (new_quene.base+i)->service_time;
}
else
{
start = (new_quene.base+i-1)->finish_time;
(new_quene.base+i)->finish_time = (new_quene.base+i)->start_time + (new_quene.base+i)->service_time;
}
service = (new_quene.base+i)->service_time;
arrive = (new_quene.base+i)->arrive_time;
finish = start + (new_quene.base+i)->service_time;
for(int j = 0;j < q.length;j ++){ //假如一个进程运行结束前，有新的进程到达，那么就加入一个临时队列。
if ((q.base+j)->arrive_time <= finish && (q.base+j)->status == 0)
{
// printf("进程ID\t到达时间\t服务时间\n"); //调试的时候用的
// printf("%8d\t%8d\t%8d\n",(q.base+j)->id,(q.base+j)->arrive_time,(q.base+j)->service_time);
rudui(&min_arrive,*(q.base+j));
count ++;
flag = 1;
}
}
if(flag == 0){ //在一个进程执行时，如果没有其他的进程到达，那就直接挑选出最早到达的加入到sjf作业调度队列
int min_arrive_time = select__min_arrive(&q);
for (int j = 0; j < q.length; j++)
{
if((q.base+j)->arrive_time == min_arrive_time && (q.base+j)->status == 0){
(q.base+j)->status = 1;
rudui(&new_quene,*(q.base+j));
break;
}
}
}
if (flag == 1) //在一个进程执行时，如果有其他的进程到达，那么就要从已经到达的队列中挑选出服务时间最短的加入sjf队列
{
// printf("进入待队列的进程ID\t到达时间\t服务时间\n"); //主要时调试的时候用的
// for (int j = 0; j < min_arrive.length; j++)
// {
// printf("%8d\t%8d\t%8d\n",(min_arrive.base+min_arrive.front+j)->id,(min_arrive.base+min_arrive.front+j)->arrive_time,(min_arrive.base+min_arrive.front+j)->service_time);
// }
int min_service_time = select__min_service(&min_arrive);
for (int j = 0; j < q.length; j++)
{
// printf("%d\t | \t", (q.base+j)->status);
if((q.base+j)->service_time == min_service_time && (q.base+j)->status == 0){
(q.base+j)->status = 1;
rudui(&new_quene,*(q.base+j));
flag = 0;
break;
}
}
}
for (int j = 0; j < count; j++) //因为每一个作业运行时，都可能会有新到达的进程，所以需要先把上一个进程运行时到达的进程队列给清空
{
chudui(&min_arrive);
}
count = 0;
}
for(int i = 0;i < new_quene.length; i ++){ //因为计算周转时间等的都放在print_PCB函数中了，所以为了后面直接用那个函数所以就又初始化了一遍
(new_quene.base + i)->start_time = 0;
(new_quene.base + i)->finish_time = 0;
}
print_pcb(&new_quene); //格式化打印并计算开始时间。完成时间，等的一些数据
break;
}
system("pause");
}
希望大家看到不足的地方可以纠正一下。谢谢大家！
完美撒花！
