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

实验目的

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

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

实验内容与基本要求

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

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

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

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

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

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

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

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

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

实现思路

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

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

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

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

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

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

算法流程图

全部代码

工程图

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;
}

结果截图