此文章为关于操作系统实验的讲解，在这一学期，我学习了操作系统，即然学习课程肯定有实验，第一个实验为进程的调度。进程调度有相当多的算法，比如最简单的先来先服务算法，时间片轮转算法，多级队列调度算法等。我将它们中的一部分写进了一个系统用于模拟进程调度，以帮助学习，在这里分享一下我的写法与思路。

        当前代码中包含三种算法：先来先服务，短作业优先，高响应比优先。剩余的时间片轮转算法与多级队列算法会在之后慢慢尝试并分享我的做法。之后的内容为我的实验内容和完成过程。

一.基本操作准备

       我希望这个小系统是一个可以进行很方便的扩展的系统，虽然相当简陋并且效率低。为了实现这个功能，我将各种进程调度写成了函数，这样可以减少各模块之间的关系并且可以提升复用程度。同时还应了解这几种调度之间的关系，据我分析，这三种调度有不小的联系，简单说，它们之间的关系是一层一层扩展的关系，短作业优先算法是在对先来先服务算法上加了服务时间的限制，高响应比优先则是又加上了等待时间的关系，这些联系我会在后面进行详细说明。

       为了可以比较好的实现我想要的功能，比较简单的完成各种队列操作，我写了一些队列函数。因为进程调度机制本身就是一个队列式的服务机制，用队列的数据结构存储是再自然不过的。

队列操作代码：

typedef struct {//进程类型的创建
    char progress_name[10];//进程名
    int priority;//进程的优先级
    int arrive_time;//到达时间
    int serve_time;//要求服务时间
    int progress_state;//进程状态
    
    int wait_time;//等待时间
    int leave_time;//离开时间
}PCB;//PCB为进程控制快，这里将进程控制块抽象成一个结构体

int time_clock;//时间轴，在每一次调度开始前都要置0

/*链式队列的创建与操作*/
typedef struct ele{
    PCB a_progress_pcb;
    struct ele* next;
}PCB_node;//队列中存储进程的节点的创建

typedef struct ele_quene{
    PCB_node* PCB_head;
    PCB_node* PCB_tail;
    int quene_long;
}PCB_quene;//链式队列的创建

void quene_init(PCB_quene **que){//链式队列的初始化
    *que = (PCB_quene*)malloc(sizeof(PCB_quene));
    (*que)->PCB_head = NULL;
    (*que)->PCB_tail = NULL;
    (*que)->quene_long = 0;
}

void PCB_enter(PCB_quene* que, PCB progress)//PCB入队操作
{
    if(que == NULL)
        return ;
    PCB_node* pTemp = (PCB_node*)malloc(sizeof(PCB_node));
    pTemp->a_progress_pcb = progress;
    pTemp->next = NULL;

    if(que->PCB_head==NULL){
        que->PCB_head = pTemp;
    }else{
        que->PCB_tail->next = pTemp;
    }
    que->PCB_tail = pTemp;
    que->quene_long++;
}


PCB PCB_leave(PCB_quene* que)//PCB出队操作
{
    PCB error;
    error.arrive_time=-1;
    error.leave_time=-1;
    error.priority=-1;
    strcpy(error.progress_name,"error");
    error.progress_state=-1;
    error.serve_time=-1;
    error.wait_time=-1;
    if(que == NULL || que->quene_long == 0)
        return error;
    PCB_node* pDel = NULL;
    PCB res;
    pDel = que->PCB_head;
    que->PCB_head = que->PCB_head->next;
    res = pDel->a_progress_pcb;
    free(pDel);
    que->quene_long--;
 
    if(que->quene_long == 0)
        que->PCB_tail = NULL;
    return res;
}

        注：由于进程的存在是靠进程控制块（PCB）标识的，因此我将它命名为PCB。

        由于这里的队列我都是创建的地址，同时队列排序很麻烦。为了防止队地址操作导致的指针错误和问题的简单化，我在main函数中输入这些进程信息时是用一个结构数组保存的，这样以来我可以随意改变数组的信息而不影响到队列，需要使用时只要将数组转化成队列即可。在这里，我的信息输入时每个进程来到的顺序并不是按时间顺序固定的，也就是说在输入这些作业时输入的到达时间并不有顺序。因此为了表达一个先来后到的关系，我们必须有一个按照时间排好序的数组或者队列，以表达基本的时序关系，因此我将两种功能结合起来，直接将数组转化为按照先来后到的顺序排好的链式队列，这个链式队列是直接当成参数传给各种调度函数的，表示时间上的先来后到顺序，我命名它为时间管道，其实怎么说都可以。

数组转化函数：

PCB_quene* time_paixu(PCB undolist[],int num){//需要进行重指针保存，时间排序，这里是返回一个时间x上的先后队列，用于表示先来后到
    PCB_quene *endquene;
    quene_init(&endquene);
    int i,j,minum;
    PCB min,chen;
    for(i=0;i<num;i++){
        min = undolist[i];
        minum=i;
        for(j=i+1;j<num;j++){
            if(min.arrive_time>undolist[j].arrive_time){
                min = undolist[j];
                minum = j;
            }
        }
        chen = undolist[i];
        undolist[i] = min;
        undolist[minum] = chen;
    }
    
    for(i=0;i<num;i++){
        PCB_enter(endquene, undolist[i]);
    }
    /*
    PCB_node *head = endquene->PCB_head;
    while(head!=NULL){
        PCB a = head->a_progress_pcb;
        printf("%d",a.arrive_time);
        head = head->next;
    } 用于进行测试，输出一个链表，这里已经将链表进行时间先来后到进行排序并会返回，用于进行先来先服务的操作*/
    
    return endquene;//返回排好序的链表，即进程按时序到达的先后关系，即先来后到的关系，由于出入队列的操作，实际上可以自由转化
}

        我们知道一个PCB不仅有时间上的先来后到顺序，还有优先级，在除先来先服务调度外的两种方法中优先级都起着不小的作用，因此我们在需要进行优先级判断时，如果想知道谁优先级高谁优先级低，我们必须要有一个优先级排序方法。

优先级排序：

void yxj_paixu(PCB_quene* npx){//大家一定不要学习这种低级的胡乱命名方法
    PCB undolist[20];
    int i,n = npx->quene_long,j,minum;
    for(i = 0;i<n;i++){
        undolist[i]=PCB_leave(npx);
    }
    
    PCB max,chen;
    for(i=0;i<n;i++){
        max = undolist[i];
        minum=i;
        for(j=i+1;j<n;j++){
            if(max.priority<undolist[j].priority){
                max = undolist[j];
                minum = j;
            }
        }
        chen = undolist[i];
        undolist[i] = max;
        undolist[minum] = chen;
    }
    /*for(i=0;i<n;i++){
        printf("%s ",undolist[i].progress_name);
        printf("%d\n",undolist[i].priority);
    }用于进行查错检验，目前查到问题，由于排序机制导致的*/
    for(i=0;i<n;i++){
        PCB_enter(npx, undolist[i]);
    }
    
}

        有了这些基本操作，就可以解决我们的问题了。

二.先来先服务

        我在写这个实验的时候对于每一个算法都进行了分析并记录了我的想法，随着分析的深入规定的实现方法也在不断变化，可以先看一下我当时写的问题分析：

    先来先服务即FCFS，是最简单的调度算法，其实也就是队列的基本处理，谁先来，谁先服务，后来的就得等，该算法既可用于作业调度，也可用于进程调度。
    当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行的时间长短，从后备队列中选择几个最先进入该队列的进程。将它们调入内存，为它们分配资源和创建进程。然后放进就绪队列。
    当在进程调度中采用FCFS算法时，每次调度是从就绪的进程队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后，进程调度程序才将处理机分配给其他进程。
    FCFS算法在单处理机系统中已经很少作为主调度算法，但经常把它与其他调度算法相结合使用，形成一种更为有效的调度算法。例如，可以在系统中按进程的优先级设置多个队列，每个优先级一个队列，其中每一个队列的调度都基于FCFS算法。
    对于先来先服务我打算用时间静态排序法，因为先来先服务中的进程不会发生运行到一半截止从而由回到等待序列中的情况，直接静态生成不会影响其队列顺序，也就是说，只要时间给定，这个序列就是固定的了。
    其他的需要用到模拟时钟，也就是循环自增的一个时钟，整个就绪队列在时循环里，但是其实仍然需要这个时间静态队列，但是它最好是动态的，也就是说我需要一个静态队列来进行先来后到的判断，我还需要一个运行队列也就是就绪队列进行紧跟当前时间的模拟调度。就绪队列需要考虑到优先级等东西，也就是说就绪队列的内容来自于静态时间队列和运行被迫终止的程序。方法是每秒检查一下系统有没有什么动作。

        这篇行文破碎的分析就是我当时一边进行问题思考，一边计划怎么解决时的思维过程，可以看出最终我确定的方法是递推方法。不要特别仔细的研究这个分析，因为当时脑子里想到什么写什么，主要是留一个思维上的印记，一步一步的找到思路。现在在这里我将规范的介绍我实现这个问题的方法，上面的分析仅起到一个辅助作用。

        先来先服务，顾名思义，我先来我就先服务，好比食堂排队，先来先打饭，天经地义，插队者天理难容。因此，我得到一个结论，先来先服务中的就绪队列，长度也许是动态的，但是顺序一定时静态的，当这个PCB进入系统后，到达时间已经确定，那么它第几个享受服务就已经定好了。同时这些PCB的到达时间都给定后，它们的就绪队列总体顺序也就确定好了。也就是说，先来先服务的就绪队列可以用一个静态的队列表示。这个队列确实会随着时间变化，但是只要到达时间一旦给出，它就定了。因此它的推导方法就很好确定了。

        首先，我们将输入的数组通过函数转化成排好序的队列，然后作为参数传入函数。函数中首先会出队一个元素，作为正在运行的函数。起始时间是0，表示系统从0时刻开始运行。现在我要计算这个进程的等待时间了，我必须有等待时间，才能通过到达时刻计算出离开时刻。因为存在：离开时刻=到达时刻+等待时间+服务时间。那么第一个的等待时间怎么计算呢？过程是这样的：系统时间由变量time_clock储存，它其实真实代表的是上一个的离开时间，第一个进入系统是没有上一个，那么它只能为0。实际上，它就是一个记录系统时间状态的坐标，作为这个系统上一次发生变化的时刻。一开始为0其实就是代表系统开始时间，而系统开始时间或者上一个的离开时间减去到达时间，含义就是等待时间。如图所示：

当然这里进程不会再系统开始前就到，这里只是举个例子，让这个含义更加明显。总的来说，我们用这个变量存储上一个进程的离开，然后当前进程到达后，我们就可以计算出当前进程的等待时间了。有了等待时间，当前的离开时间也能确定了，这样一来，重复这个过程，每个进程的等待时间就都能确定。

先来先服务函数：

void FCFS_method(PCB_quene* pcb_quene){
    time_clock=0;//时间轴必须置0,为当前时间，记录最初的系统时间和上一个的离开时间
    int wait;//等待时间
    int run_time;//周转时间
    int run_time_sum=0;//周转时间和
    double quan_run_time_sum=0;//带权周转时间
    PCB_node *head = pcb_quene->PCB_head;//准备进行遍历
    PCB per_node;
    while(head!=NULL){
        sleep(1);
        per_node = head->a_progress_pcb;
        wait = time_clock-per_node.arrive_time;//time_clock记录上一个离开
        if(wait<0){
            per_node.wait_time=0;
        }else{
            per_node.wait_time=wait;
        }
        time_clock=per_node.arrive_time+per_node.serve_time+per_node.wait_time;//离开时间为到达时间加上等待时间加上服务时间
        run_time=per_node.serve_time+per_node.wait_time;
        run_time_sum =run_time_sum+run_time;
        quan_run_time_sum =quan_run_time_sum+(run_time*1.0)/per_node.serve_time;
        per_node.leave_time=time_clock;
        printf("进程:%s\n",per_node.progress_name);
        printf("到达时间:%d\n",per_node.arrive_time);
        printf("服务时间:%d\n",per_node.serve_time);
        printf("离开时间:%d\n",per_node.leave_time);
        printf("等待时间:%d\n",per_node.wait_time);
        printf("周转时间:%d\n",run_time);
        printf("带权周转时间:%lf\n",(run_time*1.0)/per_node.serve_time);
        printf("\n\n");
        head = head->next;
    }
    printf("平均周转时间为:%.3lf\n",(run_time_sum*1.0)/pcb_quene->quene_long);
    printf("带权平均周转时间为:%.3lf\n",quan_run_time_sum/pcb_quene->quene_long);
    printf("\n\n");
}

三.短作业优先

        短作业优先其实相当于对于先来先服务加上了一个限制，在每次一个进程运行完后，不应该直接选择时间上的下一个，而是要检查一下目前都谁来了，然后从这些进程中选择一个服务时间短的。这样以来一个静态的队列就远远不够了，此时我需要一个动态的队列，这个队列用来存储“当前”到达的进程，为什么是“当前”而不是当前，这是因为这个算法仍然不是一秒一秒的模拟运行的方法，而仍与上一个算法一样，是一个推导的算法。接下来是算法描述。

        首先我创建了一个就绪队列，这个不是数组，是正儿八百的队列。一开始它是空的，因为一开始并不清楚有哪个进程会到来，也没有进程到来。然后我会检验它是否为空，如果为空，那么此时有两种情况，一种是还没来进程，一种是已经结束了，但是我还是尝试一下向总体的代表先来后到的时间管道中请求进程，如能请求到一个，那么就会往下运行，如果请求不到，那么就说嘛实在没有了，程序终止。话说回来，我现在请求到了一个进程并且时间管道内仍然有很多进程，那么程序就会向下执行，程序中仍然有一个时间钟表，不再赘述。通过同样的方式可以求的等待时间，并计算出离开时间，这一步完全相同。但是求出离开时间后，情况发生了变化，进程现在该离开了，下一个该来了，但是谁先来呢，这时，我遍历整个时间管道，来看一看谁在这个进程离开前到达了，然后加入到就绪队列中。这个操作是对就绪队列的更新，现在就明白了为什么刚才的“当前”要加引号了，因为这不见得是当前，确切的说是以前，我要将我离开以前到达的进程都加进来，表示他们已经进入就绪队列在等待了。而且每一个进程离开时都要对这个队列进行更新。更新队列完毕后，我写了一个排序，可以将时间短的排在前面。这里我耍了个小聪明，我并没有直接对服务时间排序，而是对优先级排序，在调用函数之前，我先用一个优先级刷新函数将函数的优先级通过服务时间映射成了优先级，这样以来，只要有对优先级的排序，只要写出映射关系，就可以实现对各种参数进行排序。这个排序函数仍然十分的low，大家将就着看，仅供参考。

优先级排序函数：

void yxj_paixu(PCB_quene* npx){//原理和刚才的到达时间排序一摸一样，命名方式也一样草
    PCB undolist[20];
    int i,n = npx->quene_long,j,minum;
    for(i = 0;i<n;i++){
        undolist[i]=PCB_leave(npx);
    }
    
    PCB max,chen;
    for(i=0;i<n;i++){
        max = undolist[i];
        minum=i;
        for(j=i+1;j<n;j++){
            if(max.priority<undolist[j].priority){
                max = undolist[j];
                minum = j;
            }
        }
        chen = undolist[i];
        undolist[i] = max;
        undolist[minum] = chen;
    }
    /*for(i=0;i<n;i++){
        printf("%s ",undolist[i].progress_name);
        printf("%d\n",undolist[i].priority);
    }用于进行查错检验，目前查到问题，由于排序机制导致的*/
    for(i=0;i<n;i++){
        PCB_enter(npx, undolist[i]);
    }
    
}//方法其实就是将队列拆解成数组，排序后在装回来，费时费力，但思路简单，不推荐使用，一些更好的链表排序方法更值得使用

优先级刷新函数：

void refresh_timeyxj(PCB_quene* pcb_quene){
    PCB_node* head = pcb_quene->PCB_head;
    while(head!=NULL){
        head->a_progress_pcb.priority = 100-head->a_progress_pcb.serve_time;
        head=head->next;
    }
}//使用了一个相当简单的映射

短作业优先函数：

void SJE_method(PCB_quene* pcb_quene){
    int n = pcb_quene->quene_long;
    int run_time;
    int run_time_sum=0;
    double quan_run_time_sum=0;
    time_clock=0;//时间z轴置0
    PCB_node *head;
    PCB_quene* ready_quene;//就绪队列
    quene_init(&ready_quene);
    PCB runing_pcb,lve;
    int wait;
    while(1){
        sleep(1);
        if(ready_quene->quene_long==0){
            PCB_enter(ready_quene, PCB_leave(pcb_quene));//如果就绪队列没有PCB，那么将从时间管道内请求一个
        }//否则的话要向就绪队列中请求一个来运行
        runing_pcb = PCB_leave(ready_quene);//向队头请求一个,获得其进程，将先求等待时间等一系例时间
        runing_pcb.progress_state=2;
        wait = time_clock-runing_pcb.arrive_time;//time_clock记录上一个离开
        if(wait<0){
            runing_pcb.wait_time=0;
        }else{
            runing_pcb.wait_time=wait;
        }
        time_clock=runing_pcb.arrive_time+runing_pcb.serve_time+runing_pcb.wait_time;//计算出当前进程的离开时间
        
        run_time=runing_pcb.serve_time+runing_pcb.wait_time;
        run_time_sum =run_time_sum+run_time;
        quan_run_time_sum =quan_run_time_sum+(run_time*1.0)/runing_pcb.serve_time;
        runing_pcb.leave_time=time_clock;
        //printf("%d",time_clock);
        head=pcb_quene->PCB_head;
        while(head!=NULL){
            if(head->a_progress_pcb.arrive_time<=time_clock){
                lve =head->a_progress_pcb;
                lve.progress_state=1;
                //printf("%s",lve.progress_name);
                PCB_enter(ready_quene, lve);
                PCB_leave(pcb_quene);
                head=pcb_quene->PCB_head;
            }else
                head = head->next;
        }printf("\n");
        //更新队列
        yxj_paixu(ready_quene);//按照优先级排序
        //printf("%s %d %d\n",runing_pcb.progress_name,runing_pcb.arrive_time,runing_pcb.priority);
        printf("进程:%s\n",runing_pcb.progress_name);
        printf("优先级:%d\n",runing_pcb.priority);
        printf("到达时间:%d\n",runing_pcb.arrive_time);
        printf("服务时间:%d\n",runing_pcb.serve_time);
        printf("离开时间:%d\n",runing_pcb.leave_time);
        printf("等待时间:%d\n",runing_pcb.wait_time);
        printf("周转时间:%d\n",run_time);
        printf("带权周转时间:%lf\n",(run_time*1.0)/runing_pcb.serve_time);
        printf("\n\n");
        runing_pcb.progress_state=3;
        if(ready_quene->quene_long==0&&pcb_quene->quene_long==0){
            break;
        }
    }
    printf("平均周转时间为:%.3lf\n",(run_time_sum*1.0)/n);
    printf("带权平均周转时间为:%.3lf\n",quan_run_time_sum/n);
    printf("\n\n");
}

四.高响应比优先

        高响应比优先算法其实大体上和短作业优先非常相似，我的这个函数也是直接拿短作业优先改的，但是它相比短作业优先算法又多了一个动态因素，那就是等待时间，等待时间一直在变，一个进程可能一直在就绪队列中等待，那么等待时间也就会一直在升高，等待时间升高后，根据响应比公式，优先级也会提高，那么它可能就会被先执行。下面是响应比公式：

                            优先级   =（服务时间+等待时间）/   服务时间

        可见，这里的优先级变得更加合理科学了，但也复杂了。与服务时间和等待时间都有关系，在这里我一度有些懵，考虑是不是应该一秒一秒的遍历推进，但是后来发现仍然不需要，只要结合短作业优先算法再进行一些添加就可以了。我发现，只要控制好当一个进程离开时，系统应该发生什么这个问题，所有的问题就迎刃而解了。这里，当一个进程离开时，首先我要向就绪队列里边加入新来的进程，也就是说当前进程正在运行时过来的进程，然后要为他们求出等待了多久，最后求出优先级。这样，问题就解决了。不过这只是求出了新来的进程，因为在上一个进程离开时，也会有一些进程加进来并也会进行这个更新操作，但是他们没有轮到执行，于是当目前正在运行的进程离开时，他们的优先级已经旧了，或说，他们的优先级更新是上一个进程离开时执行的，而非这一个进程离开时执行的，他们在系统中又等待了一些时间，因此这些等待时间要重新求解，然后再更新一次优先级即可。我在这里直接又遍历了一次就绪队列，可以完全更新一次所有进程的优先级和等待时间。注意，这里存在可以优化的成分，因为我在更新就绪队列时已经为新来的计算过一次新的优先级了，在这里又全面更新了一次，因此虽然数据不会出错但是操作出现了容余。在这里可以进行优化，将在更新就绪队列时的等待时间和优先级的更新删去。这个优化大家可以在看懂算法后自行操作，在此我附上优化前的代码。

高响应比函数：

void HRRN_method(PCB_quene* pcb_quene){
    int n = pcb_quene->quene_long;
    int run_time;
    int run_time_sum=0;
    double quan_run_time_sum=0;
    time_clock=0;//时间z轴置0
    PCB_node *head,*head1;
    PCB_quene* ready_quene;
    quene_init(&ready_quene);
    PCB runing_pcb,lve,ls;
    int wait;
    while(1){
        sleep(1);
        if(ready_quene->quene_long==0){
            ls=PCB_leave(pcb_quene);
            ls.priority=1;
            PCB_enter(ready_quene, ls);//如果就绪队列没有PCB，那么将从时间管道内请求一个
        }//否则的话要向就绪队列中请求一个来运行
        runing_pcb = PCB_leave(ready_quene);//向队头请求一个,获得其进程，将先求等待时间等一系例时间
        runing_pcb.progress_state=2;
        wait = time_clock-runing_pcb.arrive_time;//time_clock记录上一个离开
        if(wait<0){
            runing_pcb.wait_time=0;
        }else{
            runing_pcb.wait_time=wait;
        }//实际等待时间刷新
        time_clock=runing_pcb.arrive_time+runing_pcb.serve_time+runing_pcb.wait_time;//计算出当前进程的离开时间
        
        run_time=runing_pcb.serve_time+runing_pcb.wait_time;
        run_time_sum =run_time_sum+run_time;
        quan_run_time_sum =quan_run_time_sum+(run_time*1.0)/runing_pcb.serve_time;
        runing_pcb.leave_time=time_clock;
        //printf("%d",time_clock);
        head=pcb_quene->PCB_head;
        while(head!=NULL){
            if(head->a_progress_pcb.arrive_time<=time_clock){
                lve =head->a_progress_pcb;
                lve.progress_state=1;
                lve.wait_time=time_clock-lve.arrive_time;
                lve.priority=(lve.wait_time+lve.serve_time)/lve.serve_time;//等待时间和优先级在加入时就更新，这里与下面的全面更新形成冗余，可以删去
                //printf("%s",lve.progress_name);
                PCB_enter(ready_quene, lve);
                PCB_leave(pcb_quene);
                head=pcb_quene->PCB_head;
            }else
                head = head->next;
        }//更新就绪队列
        head1=ready_quene->PCB_head;
        while(head1!=NULL){
            
            head1->a_progress_pcb.wait_time=time_clock-head1->a_progress_pcb.arrive_time;
            head1->a_progress_pcb.priority=(head1->a_progress_pcb.wait_time+head1->a_progress_pcb.serve_time)/head1->a_progress_pcb.serve_time;
            head1=head1->next;
        }
        //全面数据更新
        yxj_paixu(ready_quene);//按照优先级排序
        //printf("%s %d %d\n",runing_pcb.progress_name,runing_pcb.arrive_time,runing_pcb.priority);
        printf("进程:%s\n",runing_pcb.progress_name);
        printf("优先级:%d\n",runing_pcb.priority);
        printf("到达时间:%d\n",runing_pcb.arrive_time);
        printf("服务时间:%d\n",runing_pcb.serve_time);
        printf("离开时间:%d\n",runing_pcb.leave_time);
        printf("等待时间:%d\n",runing_pcb.wait_time);
        printf("周转时间:%d\n",run_time);
        printf("带权周转时间:%lf\n",(run_time*1.0)/runing_pcb.serve_time);
        printf("\n\n");
        runing_pcb.progress_state=3;
        if(ready_quene->quene_long==0&&pcb_quene->quene_long==0){
            break;
        }
    }
    printf("平均周转时间为:%.3lf\n",(run_time_sum*1.0)/n);
    printf("带权平均周转时间为:%.3lf\n",quan_run_time_sum/n);
    printf("\n\n");
}

全部代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

typedef struct {
    char progress_name[10];//进程名
    int priority;//进程的优先级
    int arrive_time;//到达时间
    int serve_time;//要求服务时间
    int progress_state;//进程状态
    
    int wait_time;//等待时间
    int leave_time;//离开时间
}PCB;//PCB为进程控制快，这里将进程控制块抽象成一个结构体

int time_clock;//时间轴，在每一次调度开始前都要置0

/*链式队列的创建与操作*/
typedef struct ele{
    PCB a_progress_pcb;
    struct ele* next;
}PCB_node;

typedef struct ele_quene{
    PCB_node* PCB_head;
    PCB_node* PCB_tail;
    int quene_long;
}PCB_quene;

void quene_init(PCB_quene **que){
    *que = (PCB_quene*)malloc(sizeof(PCB_quene));
    (*que)->PCB_head = NULL;
    (*que)->PCB_tail = NULL;
    (*que)->quene_long = 0;
}//初始化链表，我发现我已经不知道怎么写了，网上找的，至于为何用二级指针，有可能为了操作统一，还需加深理解

void PCB_enter(PCB_quene* que, PCB progress)
{
    if(que == NULL)
        return ;
    PCB_node* pTemp = (PCB_node*)malloc(sizeof(PCB_node));
    pTemp->a_progress_pcb = progress;
    pTemp->next = NULL;

    if(que->PCB_head==NULL){
        que->PCB_head = pTemp;
    }else{
        que->PCB_tail->next = pTemp;
    }
    que->PCB_tail = pTemp;
    que->quene_long++;
}


PCB PCB_leave(PCB_quene* que)
{
    PCB error;
    error.arrive_time=-1;
    error.leave_time=-1;
    error.priority=-1;
    strcpy(error.progress_name,"error");
    error.progress_state=-1;
    error.serve_time=-1;
    error.wait_time=-1;
    if(que == NULL || que->quene_long == 0)
        return error;
    PCB_node* pDel = NULL;
    PCB res;
    pDel = que->PCB_head;
    que->PCB_head = que->PCB_head->next;
    res = pDel->a_progress_pcb;
    free(pDel);
    que->quene_long--;
 
    if(que->quene_long == 0)
        que->PCB_tail = NULL;
    return res;
}

int init_a_pcb(PCB static_list[]){
    strcpy(static_list[0].progress_name, "A");
    static_list[0].arrive_time=7;
    static_list[0].priority=-1;
    static_list[0].serve_time=7;
    static_list[0].leave_time=-1;
    static_list[0].wait_time=-1;
    static_list[0].progress_state=1;
    strcpy(static_list[1].progress_name, "B");
    static_list[1].arrive_time=2;
    static_list[1].priority=-1;
    static_list[1].serve_time=6;
    static_list[1].leave_time=-1;
    static_list[1].wait_time=-1;
    static_list[1].progress_state=1;
    
    strcpy(static_list[2].progress_name, "C");
    static_list[2].arrive_time=3;
    static_list[2].priority=-1;
    static_list[2].serve_time=5;
    static_list[2].leave_time=-1;
    static_list[2].wait_time=-1;
    static_list[2].progress_state=1;
    
    strcpy(static_list[3].progress_name, "D");
    static_list[3].arrive_time=4;
    static_list[3].priority=-1;
    static_list[3].serve_time=1;
    static_list[3].leave_time=-1;
    static_list[3].wait_time=-1;
    static_list[3].progress_state=1;
    return 4;
}

/*操作函数表*/
int menu(void);
void output(PCB pcblist[],int num);
PCB_quene* time_paixu(PCB undolist[],int num);
void time_output(PCB_quene* list);
void FCFS_method(PCB_quene* pcb_quene);
void SJE_method(PCB_quene* pcb_quene);
void yxj_paixu(PCB_quene* npx);
void refresh_timeyxj(PCB_quene* pcb_quene);
void HRRN_method(PCB_quene* pcb_quene);


int main(int argc, const char * argv[]) {
    PCB undolist[20],new_pcb;
    PCB_quene* pcb_quene;
    int flag=1,option,input_flag=0;//标志位f和操作位
    int pcb_num=0,pcb_num_count;//进程数量和进程计数器
    while(flag){
        option=menu();
        if(option==1){
            printf("请输入进程个数:");
            scanf("%d",&pcb_num);
            for(pcb_num_count=0;pcb_num_count<pcb_num;pcb_num_count++){
                printf("请输入[%d]号进程名:",pcb_num_count);scanf("%s",new_pcb.progress_name);
                printf("请输入[%d]号进程到达时间:",pcb_num_count);scanf("%d",&new_pcb.arrive_time);
                printf("请输入[%d]号进程服务时间:",pcb_num_count);scanf("%d",&new_pcb.serve_time);
                //printf("请输入[%d]号进程优先级:",pcb_num_count);scanf("%d",&new_pcb.priority);
                printf("\n\n");
                new_pcb.wait_time=-1;//当前的新pcb等待时间和离开时间都定为未知
                new_pcb.leave_time=-1;
                new_pcb.progress_state=0;
                //状态定为就绪状态，就绪为1，运行为2，完成为3，0为未到达，进入就绪队列后为1，在运行中为0，运行结束后为3
                new_pcb.priority=-1;//在此处优先级不考虑，为未知，具体是多少根据方法而改变
                undolist[pcb_num_count]=new_pcb;
                input_flag=1;
            }
        }
        else if(option==7){
            flag=0;
        }
        else if(option==2){
            if(input_flag==0)
                pcb_num=init_a_pcb(undolist);
            output(undolist, pcb_num);
        }
        else if(option==6){
            if(input_flag==0)
                pcb_num=init_a_pcb(undolist);
            pcb_quene=time_paixu(undolist, pcb_num);
            time_output(pcb_quene);
            //yxj_paixu(pcb_quene);
        }
        else if (option==3){
            if(input_flag==0)
                pcb_num=init_a_pcb(undolist);
            pcb_quene=time_paixu(undolist, pcb_num);
            FCFS_method(pcb_quene);
        }else if(option==4){
            if(input_flag==0)
                pcb_num=init_a_pcb(undolist);
            pcb_quene=time_paixu(undolist, pcb_num);
            refresh_timeyxj(pcb_quene);//进行优先级刷新，当然是根据服务时间
            SJE_method(pcb_quene);
        }else if(option==5){
            if(input_flag==0)
                pcb_num=init_a_pcb(undolist);
            pcb_quene=time_paixu(undolist, pcb_num);
            HRRN_method(pcb_quene);
        }
    }
    
    
    return 0;
}
int menu(void){//用于显示操作菜单与返回操作数
    printf("请选择进程操作:\n");
    printf("1.输入进程信息\n");
    printf("2.显示进程信息\n");
    printf("3.先来先服务调度\n");
    printf("4.短作业优先调度\n");
    printf("5.高响应比优先调度\n");
    printf("6.时间顺序输出进程\n");
    printf("7.退出\n");
    int flag;
    scanf("%d",&flag);
    printf("\n\n");
    return flag;
}
void output(PCB pcblist[],int num){//用于输出
    int i;
    if(num==0){
        printf("当前系统无进程");
        return;
    }
    for(i=0;i<num;i++){
        printf("第%d号进程的进程名为:%s。\n",i,pcblist[i].progress_name);
        printf("第%d号进程的到达时间为:%d。\n",i,pcblist[i].arrive_time);
        printf("第%d号进程的服务时间为:%d。\n",i,pcblist[i].serve_time);
        if(pcblist[i].priority!=-1)
            printf("第%d号进程的优先级为:%d。\n",i,pcblist[i].priority);
        else
            printf("暂时没有设定优先级。");
        printf("\n\n");
    }
}
PCB_quene* time_paixu(PCB undolist[],int num){//需要进行重指针保存，时间排序，这里是返回一个时间x上的先后队列，用于表示先来后到
    PCB_quene *endquene;
    quene_init(&endquene);
    int i,j,minum;
    PCB min,chen;
    for(i=0;i<num;i++){
        min = undolist[i];
        minum=i;
        for(j=i+1;j<num;j++){
            if(min.arrive_time>undolist[j].arrive_time){
                min = undolist[j];
                minum = j;
            }
        }
        chen = undolist[i];
        undolist[i] = min;
        undolist[minum] = chen;
    }
    
    for(i=0;i<num;i++){
        PCB_enter(endquene, undolist[i]);
    }
    /*
    PCB_node *head = endquene->PCB_head;
    while(head!=NULL){
        PCB a = head->a_progress_pcb;
        printf("%d",a.arrive_time);
        head = head->next;
    } 用于进行测试，输出一个链表，这里已经将链表进行时间先来后到进行排序并会返回，用于进行先来先服务的操作*/
    
    return endquene;//返回排好序的链表，即进程按时序到达的先后关系，即先来后到的关系，由于出入队列的操作，实际上可以自由转化
}
void yxj_paixu(PCB_quene* npx){
    PCB undolist[20];
    int i,n = npx->quene_long,j,minum;
    for(i = 0;i<n;i++){
        undolist[i]=PCB_leave(npx);
    }
    
    PCB max,chen;
    for(i=0;i<n;i++){
        max = undolist[i];
        minum=i;
        for(j=i+1;j<n;j++){
            if(max.priority<undolist[j].priority){
                max = undolist[j];
                minum = j;
            }
        }
        chen = undolist[i];
        undolist[i] = max;
        undolist[minum] = chen;
    }
    /*for(i=0;i<n;i++){
        printf("%s ",undolist[i].progress_name);
        printf("%d\n",undolist[i].priority);
    }用于进行查错检验，目前查到问题，由于排序机制导致的*/
    for(i=0;i<n;i++){
        PCB_enter(npx, undolist[i]);
    }
    
}



void time_output(PCB_quene* list){//好了，先不考虑链表的问题，先用
    PCB_node *head = list->PCB_head;
    int i=0;
    while(head!=NULL){
        PCB a = head->a_progress_pcb;
        printf("%d号",i);
        i++;
        printf("进程名为:%s。\n",a.progress_name);
        printf("到达时间为:%d。\n",a.arrive_time);
        printf("服务时间为:%d。\n",a.serve_time);
        if(a.priority!=-1)
            printf("优先级为:%d。\n",a.priority);
        else
            printf("暂时没有设定优先级");
        printf("\n\n");
        head = head->next;
    }
}
void FCFS_method(PCB_quene* pcb_quene){
    time_clock=0;//时间轴必须置0,为当前时间，上一个的离开减去当前的到达
    int wait;
    int run_time;
    int run_time_sum=0;
    double quan_run_time_sum=0;
    PCB_node *head = pcb_quene->PCB_head;
    PCB per_node;
    while(head!=NULL){
        sleep(1);
        per_node = head->a_progress_pcb;
        wait = time_clock-per_node.arrive_time;//time_clock记录上一个离开
        if(wait<0){
            per_node.wait_time=0;
        }else{
            per_node.wait_time=wait;
        }
        time_clock=per_node.arrive_time+per_node.serve_time+per_node.wait_time;//离开时间为到达时间加上等待时间加上服务时间
        run_time=per_node.serve_time+per_node.wait_time;
        run_time_sum =run_time_sum+run_time;
        quan_run_time_sum =quan_run_time_sum+(run_time*1.0)/per_node.serve_time;
        per_node.leave_time=time_clock;
        printf("进程:%s\n",per_node.progress_name);
        printf("到达时间:%d\n",per_node.arrive_time);
        printf("服务时间:%d\n",per_node.serve_time);
        printf("离开时间:%d\n",per_node.leave_time);
        printf("等待时间:%d\n",per_node.wait_time);
        printf("周转时间:%d\n",run_time);
        printf("带权周转时间:%lf\n",(run_time*1.0)/per_node.serve_time);
        printf("\n\n");
        head = head->next;
    }
    printf("平均周转时间为:%.3lf\n",(run_time_sum*1.0)/pcb_quene->quene_long);
    printf("带权平均周转时间为:%.3lf\n",quan_run_time_sum/pcb_quene->quene_long);
    printf("\n\n");
}

void SJE_method(PCB_quene* pcb_quene){
    int n = pcb_quene->quene_long;
    int run_time;
    int run_time_sum=0;
    double quan_run_time_sum=0;
    time_clock=0;//时间z轴置0
    PCB_node *head;
    PCB_quene* ready_quene;//就绪队列
    quene_init(&ready_quene);
    PCB runing_pcb,lve;
    int wait;
    while(1){
        sleep(1);
        if(ready_quene->quene_long==0){
            PCB_enter(ready_quene, PCB_leave(pcb_quene));//如果就绪队列没有PCB，那么将从时间管道内请求一个
        }//否则的话要向就绪队列中请求一个来运行
        runing_pcb = PCB_leave(ready_quene);//向队头请求一个,获得其进程，将先求等待时间等一系例时间
        runing_pcb.progress_state=2;
        wait = time_clock-runing_pcb.arrive_time;//time_clock记录上一个离开
        if(wait<0){
            runing_pcb.wait_time=0;
        }else{
            runing_pcb.wait_time=wait;
        }
        time_clock=runing_pcb.arrive_time+runing_pcb.serve_time+runing_pcb.wait_time;//计算出当前进程的离开时间
        
        run_time=runing_pcb.serve_time+runing_pcb.wait_time;
        run_time_sum =run_time_sum+run_time;
        quan_run_time_sum =quan_run_time_sum+(run_time*1.0)/runing_pcb.serve_time;
        runing_pcb.leave_time=time_clock;
        //printf("%d",time_clock);
        head=pcb_quene->PCB_head;
        while(head!=NULL){
            if(head->a_progress_pcb.arrive_time<=time_clock){
                lve =head->a_progress_pcb;
                lve.progress_state=1;
                //printf("%s",lve.progress_name);
                PCB_enter(ready_quene, lve);
                PCB_leave(pcb_quene);
                head=pcb_quene->PCB_head;
            }else
                head = head->next;
        }printf("\n");
        //更新队列
        yxj_paixu(ready_quene);//按照优先级排序
        //printf("%s %d %d\n",runing_pcb.progress_name,runing_pcb.arrive_time,runing_pcb.priority);
        printf("进程:%s\n",runing_pcb.progress_name);
        printf("优先级:%d\n",runing_pcb.priority);
        printf("到达时间:%d\n",runing_pcb.arrive_time);
        printf("服务时间:%d\n",runing_pcb.serve_time);
        printf("离开时间:%d\n",runing_pcb.leave_time);
        printf("等待时间:%d\n",runing_pcb.wait_time);
        printf("周转时间:%d\n",run_time);
        printf("带权周转时间:%lf\n",(run_time*1.0)/runing_pcb.serve_time);
        printf("\n\n");
        runing_pcb.progress_state=3;
        if(ready_quene->quene_long==0&&pcb_quene->quene_long==0){
            break;
        }
    }
    printf("平均周转时间为:%.3lf\n",(run_time_sum*1.0)/n);
    printf("带权平均周转时间为:%.3lf\n",quan_run_time_sum/n);
    printf("\n\n");
}

void refresh_timeyxj(PCB_quene* pcb_quene){
    PCB_node* head = pcb_quene->PCB_head;
    while(head!=NULL){
        head->a_progress_pcb.priority = 100-head->a_progress_pcb.serve_time;
        head=head->next;
    }
}
void HRRN_method(PCB_quene* pcb_quene){
    int n = pcb_quene->quene_long;
    int run_time;
    int run_time_sum=0;
    double quan_run_time_sum=0;
    time_clock=0;//时间z轴置0
    PCB_node *head,*head1;
    PCB_quene* ready_quene;
    quene_init(&ready_quene);
    PCB runing_pcb,lve,ls;
    int wait;
    while(1){
        sleep(1);
        if(ready_quene->quene_long==0){
            ls=PCB_leave(pcb_quene);
            ls.priority=1;
            PCB_enter(ready_quene, ls);//如果就绪队列没有PCB，那么将从时间管道内请求一个
        }//否则的话要向就绪队列中请求一个来运行
        runing_pcb = PCB_leave(ready_quene);//向队头请求一个,获得其进程，将先求等待时间等一系例时间
        runing_pcb.progress_state=2;
        wait = time_clock-runing_pcb.arrive_time;//time_clock记录上一个离开
        if(wait<0){
            runing_pcb.wait_time=0;
        }else{
            runing_pcb.wait_time=wait;
        }//实际等待时间刷新
        time_clock=runing_pcb.arrive_time+runing_pcb.serve_time+runing_pcb.wait_time;//计算出当前进程的离开时间
        
        run_time=runing_pcb.serve_time+runing_pcb.wait_time;
        run_time_sum =run_time_sum+run_time;
        quan_run_time_sum =quan_run_time_sum+(run_time*1.0)/runing_pcb.serve_time;
        runing_pcb.leave_time=time_clock;
        //printf("%d",time_clock);
        head=pcb_quene->PCB_head;
        while(head!=NULL){
            if(head->a_progress_pcb.arrive_time<=time_clock){
                lve =head->a_progress_pcb;
                lve.progress_state=1;
                lve.wait_time=time_clock-lve.arrive_time;
                lve.priority=(lve.wait_time+lve.serve_time)/lve.serve_time;
                //printf("%s",lve.progress_name);
                PCB_enter(ready_quene, lve);
                PCB_leave(pcb_quene);
                head=pcb_quene->PCB_head;
            }else
                head = head->next;
        }
        head1=ready_quene->PCB_head;
        while(head1!=NULL){
            
            head1->a_progress_pcb.wait_time=time_clock-head1->a_progress_pcb.arrive_time;
            head1->a_progress_pcb.priority=(head1->a_progress_pcb.wait_time+head1->a_progress_pcb.serve_time)/head1->a_progress_pcb.serve_time;
            head1=head1->next;
        }
        //更新队列
        yxj_paixu(ready_quene);//按照优先级排序
        //printf("%s %d %d\n",runing_pcb.progress_name,runing_pcb.arrive_time,runing_pcb.priority);
        printf("进程:%s\n",runing_pcb.progress_name);
        printf("优先级:%d\n",runing_pcb.priority);
        printf("到达时间:%d\n",runing_pcb.arrive_time);
        printf("服务时间:%d\n",runing_pcb.serve_time);
        printf("离开时间:%d\n",runing_pcb.leave_time);
        printf("等待时间:%d\n",runing_pcb.wait_time);
        printf("周转时间:%d\n",run_time);
        printf("带权周转时间:%lf\n",(run_time*1.0)/runing_pcb.serve_time);
        printf("\n\n");
        runing_pcb.progress_state=3;
        if(ready_quene->quene_long==0&&pcb_quene->quene_long==0){
            break;
        }
    }
    printf("平均周转时间为:%.3lf\n",(run_time_sum*1.0)/n);
    printf("带权平均周转时间为:%.3lf\n",quan_run_time_sum/n);
    printf("\n\n");
}

五.总结

        说白了这个实验很简单，比去年的编译原理简单很多，起码我知道怎么写。虽然原来很简单但是我仍然想给大家分享一下，讲一讲，因为这样不仅能帮助的一些和我一样在苦逼学习的同学，还能让我自己进行一次梳理与分析，比如这次我就分析出了很多内在的问题：码风不好，胡乱命名；思维不缜密，逻辑错误经常发生；代码不简洁，耗时长；基础不扎实，链表操作等基础知识忘得快，以及其他问题。这些问题都是相当严重的，一定要进行改正。并且我发现我相当长的时间没有写博客了，这也不太好。总之意识到应该及时改正，我发现很多东西都要学，越早越好，大家一起努力吧。联系信息在下面，欢迎指正我的错误并一起探讨。

邮箱：15830880315@163.com

QQ：1448610869

云杉木屋