计算机操作系统实验之进程调度（二）优先级调度法（C语言）

怼烎@ 2023-06-18 08:00 28阅读 0赞

### 计算机操作系统实验之进程调度（二）优先级调度法（C语言） ###

*   *   *  实验目的
         *  实验内容与基本要求
         *  优先级调度算法的基本内容
         *  实现思路
         *  算法流程图
         *  全部代码
         *   *  工程图
             *  ProcessScheduling.h
             *  ProcessScheduling.c
             *  Main.c
         *  结果截图

### 实验目的 ###

1、理解进程调度的任务、机制和方式

2、了解优先级调度算法的基本原理

### 实验内容与基本要求 ###

用C，C++等语言编写程序，模拟使用静态优先级调度算法实现进程调度

### 优先级调度算法的基本内容 ###

在时间片轮转调度算法中，有一个隐含的假设：系统中所有进程的紧迫性是一致的。但是在实际中并不是如此，因此实际在进程调度算法中引入“优先级”这个概念，形成了优先级调度算法。

优先级调度算法，就是把处理机分配给就绪队列中优先级最高的进程。现在的问题是：处理机正在执行目前就绪队列中优先级最高的进程B，此时又出现了另一个优先级更高的进程A，系统该如何处理？针对这个问题的不同处理方式，形成了优先级调度算法的两个类型：一种是抢占式的优先级调度算法，一种是非抢占式的优先级调度算法。

*  抢占式优先级调度算法：在这种算法中，只要出现了一个优先级更高的进程A，就停止正在执行的进程B，让A立刻投入执行
 *  非抢占式优先级调度算法：在这种算法中，处理机已经分配给了进程B，就让B一直执行结束，或等B自动放弃处理机时，才将处理机分配给A

优先级调度算法的核心问题是：如何确定进程的优先级？

优先级根据性质的不同，也分为两种类型：静态优先级和动态优先级。

*  静态优先级：在进程创建时就决定，并且在进程的整个运行期间保持不变
 *  动态优先级：在进程创建时先赋予一个优先级，但是其值会随着进程的推进或等待时间的增加而改变。

静态优先级容易实现，但是可能会出现优先级低的进程始终无法被调度的情况。而动态优先级根据不同的规定来计算优先级，有利于促进进程调度的公平性。

### 实现思路 ###

用轮转调度法类似，进程PCB的结构和进程队列的设置方式不变，只是调度的方法有区别而已。

附：上篇轮转调度法 [计算机操作系统实验之进程调度（一）轮转调度法（C语言）][C]

PCB的属性包括：1.进程名字2.进程优先级3.进程的状态4.时间片5.总共需要的运行时间6.cpu时间（已运行时间）7.还需要运行的时间8.计数器9.下一个要执行的进程指针。

仍然使用带头结点的单链表来存储进程队列，已完成的进程不移出队列，而是沉到队列底部。

本次实验实现的是非抢占式的静态优先级调度方式，优先级在进程创建时就决定好（可以由随机数生成，也可以让用户自己输入）。由于是非抢占式的，因此每个进程只会获得一次处理机，无论它的执行时间是多长，都要执行完后才会调度下一个进程。

至于具体怎么实现调度，有两种思路：第一种是在每次调度时去查找队列中未完成的优先级最大的进程，将它的状态变为完成。第二种是：先将队列按优先级顺序排序，然后再依次执行。本次实验采用的是第二种，因此额外写了方法，用于按优先级排序。排序的方法是：将链表从头结点处断开，依次取出首元结点后的每个结点，对链表进行按值（优先级的值）插入，优先级从大到小排列。

### 算法流程图 ###

![img\_1][img_1]

### 全部代码 ###

#### 工程图 ####

![img\_5][img_5]

#### ProcessScheduling.h ####

//
    // ProcessScheduling.h
    // ProcessSchedulingTest
    //
    // Created by Apple on 2019/10/21.
    // Copyright © 2019 Yao YongXin. All rights reserved.
    //
    
    #ifndef ProcessScheduling_h
    #define ProcessScheduling_h
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <time.h>
    
    #define TIME_SLICE 2
    
    //线程状态：就绪 等待 完成
    enum process_type{ 
        process_type_waitting = 'W',
        process_type_ready = 'R',
        process_type_finish = 'F'
    };
    
    //进程控制块结构体
    typedef struct PCB_Type{ 
        //进程的名字
        char *name;
        //进程的优先级
        int priority;
        //仍需运行时间
        int need_time;
        //进程的状态 就绪 等待
        char state;
        //时间片
        int time_slice;
        //cpu时间 ->已运行时间
        int cpu_time;
        //计数器
        int time_count;
        //总共需要的运行时间
        int total_time;
    
        //下一个要执行的进程
        struct PCB_Type *next;
    }PCB;
    
    //创建新的进程
    void create_process(PCB *running_list,char *name,int need_time);
    void create_process1(PCB *running_list,char *name,int need_time,int priority);
    //展示当前就绪队列状态
    void show(PCB *running_list);
    
    //优先级调度法
    void priority_scheduling(PCB *running_list);
    //按优先级大小对队列进行排序
    void sort(PCB *running_list);
    //找到当前未执行的优先级最高的进程，将它状态变为就绪
    void set_ready(PCB *running_list);
    
    #endif /* ProcessScheduling_h */

#### ProcessScheduling.c ####

//
    // ProcessScheduling.c
    // ProcessSchedulingTest
    //
    // Created by Apple on 2019/10/21.
    // Copyright © 2019 Yao YongXin. All rights reserved.
    //
    
    #include "ProcessScheduling.h"
    
    //创建新的进程->优先级随机数生成
    void create_process(PCB *running_list,char *name,int need_time){ 
        //申请一个内存控制块的空间
        PCB *p = (PCB *)malloc(sizeof(PCB));
        assert(p != NULL);
        
        //设置该控制块的值
        p->name = name;
        p->need_time = need_time;
        
        //状态
        p->state = process_type_waitting;
        //时间片
        p->time_slice = 0;
        //cpu时间
        p->cpu_time = 0;
        //计数器
        p->time_count = 0;
        //总需用时
        p->total_time = need_time;
        
        //优先级->随机数生成
        srand((unsigned)time(NULL));
        int priority = rand() % 50 + 1;
        p->priority = priority;
        
        //下个进程
        p->next = NULL;
        
        //放入运行队列中
        PCB *s = running_list;
        while (s->next != NULL) { 
            s = s->next;
        }
        s->next = p;
        
    }
    
    void create_process1(PCB *running_list,char *name,int need_time,int priority){ 
        //申请一个内存控制块的空间
        PCB *p = (PCB *)malloc(sizeof(PCB));
        assert(p != NULL);
        
        //设置该控制块的值
        p->name = name;
        p->need_time = need_time;
        
        //状态
        p->state = process_type_waitting;
        //时间片
        p->time_slice = 0;
        //cpu时间
        p->cpu_time = 0;
        //计数器
        p->time_count = 0;
        //总需用时
        p->total_time = need_time;
        
        //优先级
        p->priority = priority;
        
        //下个进程
        p->next = NULL;
        
        //放入运行队列中
        PCB *s = running_list;
        while (s->next != NULL) { 
            s = s->next;
        }
        s->next = p;
    }
    
    //展示当前就绪队列状态
    void show(PCB *running_list){ 
        PCB *p = running_list->next;
        if (p == NULL) { 
            printf("当前队列中无进程\n");
            return;
        }
        
        printf("进程名 优先级 时间片 cpu时间 需要时间 进程状态 计数器\n");
        while (p != NULL) { 
            printf("%s %4d %4d %4d %4d %c %4d\n",p->name,p->priority,p->time_slice,p->cpu_time,p->need_time,p->state,p->time_count);
            
            p = p->next;
        }
        printf("\n");
    }
    
    //优先级调度算法
    void priority_scheduling(PCB *running_list){ 
        
        //将队列按优先级大小进行排序
        sort(running_list);
        
        //遍历整个链表依次执行进程
        PCB *s = running_list->next;
        while (s != NULL) { 
            s->cpu_time = 1;
            s->time_count = 1;
            s->state = process_type_finish;
            
            s = s->next;
            set_ready(running_list);
            //每执行完依次进程展示当前队列状况
            show(running_list);
        }
    }
    
    //按优先级大小对队列进行排序
    void sort(PCB *running_list){ 
        PCB *s = running_list->next;
        PCB *p = s->next;
        if (s == NULL || p == NULL) { 
            //此时链表中只有0或1个结点，无须排序
            return;
        }
        
        //将链表从第一个结点往后断开
        s->next = NULL;
        //头指针
        PCB *first = running_list;
        
        while (p != NULL) { 
            s = p;
            p = p->next;
            
            //将s插入断开的新链表中
            PCB *q = first;
            //遍历新链表，找到插入位置
            while (q->next !=NULL) { 
                //判断s结点的优先级是否比当前节点小
                if (s->priority < q->next->priority) { 
                    //是，往后继续寻找
                    q = q->next;
                }else{ 
                    //否，就在这里插入
                    s->next = q->next;
                    q->next = s;
                    break;
                }
            }
            
            if (q->next == NULL) { 
                //比之前的优先级都低，插入最后
                q->next = s;
                s->next = NULL;
            }
            
        }
        
    }
    
    //找到当前未执行的优先级最高的进程，将它状态变为就绪
    void set_ready(PCB *running_list){ 
        
        PCB *s = running_list->next;
        if (s == NULL) { 
            printf("当前队列已空\n");
            return;
        }
        
        /* 该方法只适用于排序之后 // while (s != NULL && s->state != process_type_waitting) { // s = s->next; // } // if (s != NULL) { // s->state = process_type_ready; // } */
        //记录当前优先级的最大值
        int max = 0;
        //记录该值对应的进程
        PCB *p = NULL;
        
        while (s != NULL) { 
            //当该进程不属于等待状态时，直接跳过
            if (s->state != process_type_waitting) { 
                s = s->next;
                continue;
            }
            //记录处于等待状态的进程优先级的最大值
            if (s->priority >= max) { 
                max = s->priority;
                p = s;
            }
            s = s->next;
        }
        //P为空说明当前已经没有等待中的进程了
        if (p != NULL) { 
            p->state = process_type_ready;
        }
    
    }

#### Main.c ####

//
    // main.c
    // ProcessSchedulingTest
    //
    // Created by Apple on 2019/10/21.
    // Copyright © 2019 Yao YongXin. All rights reserved.
    //
    
    #include "ProcessScheduling.h"
    
    int main(int argc, const char * argv[]) { 
        
        //运行(就绪)队列(头结点不储存信息)
        PCB *running_list = (PCB *)malloc(sizeof(PCB));
        running_list->next = NULL;
        
        int p_number;
        printf("请输入要创建的进程数目:\n");
        scanf("%d",&p_number);
        
    // 随机数生成优先级
    // printf("请输入进程名字和所需时间:\n");
    // for (int i = 0; i < p_number; i++) { 
    // //create(running_list);
    // char *name = (char *)malloc(sizeof(char));
    // int time;
    // scanf("%s %d",name,&time);
    // create_process(running_list, name, time);
    // }
        
        printf("请输入进程名字和所需时间、优先级:\n");
        for (int i = 0; i < p_number; i++) { 
            //create(running_list);
            char *name = (char *)malloc(sizeof(char));
            int time,priority;
            scanf("%s %d %d",name,&time,&priority);
            create_process1(running_list, name, time,priority);
        }
        
        //优先级调度法
        set_ready(running_list);
        printf("调度前:\n");
        show(running_list);
        printf("调度后:\n");
        priority_scheduling(running_list);
    
        return 0;
    }

### 结果截图 ###

![img\_1][img_1 1]  
![img\_2][img_2]

[C]: https://blog.csdn.net/weixin_42643216/article/details/102897159
[img_1]: https://img-blog.csdnimg.cn/20191201144540603.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_5]: https://img-blog.csdnimg.cn/20191104152215710.png
[img_1 1]: https://img-blog.csdnimg.cn/20191201165425853.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_2]: https://img-blog.csdnimg.cn/20191201165445840.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70