【操作系统】先来先服务和短作业优先算法（C语言实现）
介绍:
1.先来先服务 (FCFS: first come first service)
如果早就绪的进程排在就绪队列的前面，迟就绪的进程排在就绪队列的后面，那么先来先服务(FCFS: first come first service)总是把当前处于就绪队列之首的那个进程调度到运行状态。也就说，它只考虑进程进入就绪队列的先后，而不考虑它的下一个CPU周期的长短及其他因素。FCFS算法简单易行，是一种非抢占式策略，但性能却不大好。
简单来说，先来先服务就是那个进程到达时间最早，那么CPU就先处理哪个进程。
2.短作业优先（SJF, Shortest Job First）
对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业。
也就是说，不但要考虑进程的到达时间，还要考虑进程需要运行的时间。
当一个进程正在运行时，假如有其他的进程到达，那么这些到达的进程就需要按照其需要运行的时间长短排序，运行时间短的在前，运行时间长的在后。
3.例子：
4.运行截图
1.先来先服务
2.短作业优先
5.话不多说，直接上代码。第一次写，有很多不足的地方。希望大家看到可以帮忙纠正一下，谢谢大家。
#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)->arrive_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+new_quene.front+i)->arrive_time; (new_quene.base+new_quene.front+i)->start_time = (new_quene.base+new_quene.front+i)->arrive_time; (new_quene.base+new_quene.front+i)->finish_time = (new_quene.base+new_quene.front+i)->arrive_time + (new_quene.base+new_quene.front+i)->service_time; } else { start = (new_quene.base+new_quene.front+i-1)->finish_time; (new_quene.base+new_quene.front+i)->finish_time = (new_quene.base+new_quene.front+i)->start_time + (new_quene.base+new_quene.front+i)->service_time; } service = (new_quene.base+new_quene.front+i)->service_time; arrive = (new_quene.base+new_quene.front+i)->arrive_time; finish = start + (new_quene.base+new_quene.front+i)->service_time; for(int j = 0;j <= q.length;j ++){ //假如一个进程运行结束前，有新的进程到达，那么就加入一个临时队列。 if ((q.base+q.front+j)->arrive_time <= finish && (q.base+q.front+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+q.front+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+q.front+j)->arrive_time == min_arrive_time && (q.base+q.front+j)->status == 0){ (q.base+q.front+j)->status = 1; rudui(&new_quene,*(q.base+q.front+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+q.front+j)->service_time == min_service_time && (q.base+q.front+j)->status == 0){ (q.base+q.front+j)->status = 1; rudui(&new_quene,*(q.base+q.front+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");}
希望大家看到不足的地方可以纠正一下。谢谢大家！
完美撒花！
赞 (0)