【操作系统】先来先服务和短作业优先算法(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)

相关推荐