最高优先级算法——进程调度

原创

---

最近几周操作系统实习，要求完成几道题目，下面是自己敲出来的模拟在单处理器情况下的进程调度算法（说算法可能过于高大尚），

采用的是短作业优先调度算法、时间片轮转调度、最高优先级优先算法三种算法中的最高优先级算法。

题目阐述如下：

　　　　　　　　　　　　　　　　　　　　设计一：进程调度

  设计目的：    

  进程管理是操作系统中的重要功能，用来创建进程、撤消进程、实现进程状态转换，它提供了在可运行的进程之间复用CPU的方法。

在进程管理中，进程调度是核心，因为在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态，当就绪进程个数大于处

理器数目时，就必须依照某种策略决定哪些进程优先占用处理器。本设计模拟在单处理器情况下的进程调度，目的是加深对进程调度

工作的理解，掌握不同调度算法的优缺点。

  设计内容：

设计程序模拟单处理机系统中的进程调度算法，在短作业优先调度算法、时间片轮转调度、最高优先级优先算法三种算法中选择两种实现。

每个进程由一个进程控制块（PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进

程状态等。进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间。

进程的运行时间以时间片为单位进行计算。

每个进程的状态可以是就绪W（Wait）、运行R(Run)或完成F(Finish)3中状态之一。

以下是最高优先级优先算法思想：

就绪进程获得CPU后都只能运行一个时间片，用已占用CPU时间加1来表示。

如果运行一个时间片后，进程的已占用CPU时间已达到所需要的运行时间，则撤销该进程，如果运行一个时间片后进程的已占用CPU时间

还未达到所需要的运行时间，也即进程还需要继续运行，此时应将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU。

每进行一次调度程序都打印一次运行进程、就绪队列以及各个进程的PCB，以便进行检查。

重复以上过程，直到所有进程都完成为止。

 

每个PCB进程包括：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态；采用结构体类型来存储一个PCB。

采用的数据结构是队列，创建的进程形成一个双向队列（采用双向队列容易寻找前驱结点的地址），遍历队列，从中找出优先级

最高的PCB取出（相当于调入CPU），将其优先数降低，增加其已用CPU时间，改变其进程状态；然后判断其已用CPU时间是否

大于等于需要运行时间，大于将其进程状态置为完成状态，否则将此PCB插入队列尾部，再次在队列中寻找优先级最高的PCB......

/*
    最高优先级算法 
*/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define N 3
#define Time_film 2    //时间片

int count = 0;    //统计进程完成个数 

void print(struct PCB *head);

struct PCB{
    int process_name;    //进程名 
    int priority_number;    //优先数,随机产生 
    int arrive_time;    //到达时间,为进程的创建时间 
    int need_time;    //需要运行的时间,随机产生 
    int used_time;    //已用CPU的时间,初始值为0 
    int process_state;    //进程状态,1表示运行,0表示完成,-1表示就绪,初始值为-1 
    struct PCB *cre;    //前驱指针域
    struct PCB *next;    //后驱指针域
};

void Process_scheduling(struct PCB *head){
    /*
    扫描队列，寻找最高优先数的PCB，调入CPU运行；
    如果 use_CPU == need_time 撤销此PCB；
    否则用完一个时间片后放回队列尾部，继续扫描；
    */
    //****************************
    struct PCB *Move=head->next;
    struct PCB *Max_Pri=head->next;
    struct PCB *Tail;    //尾指针 
    //****************************
    while(Move!=NULL){
        if(Max_Pri->priority_number < Move->priority_number){
            Max_Pri = Move;
        }                        //寻找最高优先级进程 
        Move = Move->next;
    }
    //****************************
    Move = Max_Pri->cre;        //将最高优先级进程调出
    Move->next = Max_Pri->next;
    if(Move->next != NULL){
        Move = Max_Pri->next;
        Move->cre = Max_Pri->cre;    
    }
    //****************************
    printf("        进程 %d 被调度: \n",Max_Pri->process_name);
    Max_Pri->used_time += Time_film;    //增加CPU占用时间
    if(Max_Pri->used_time >= Max_Pri->need_time){
        Max_Pri->used_time = Max_Pri->need_time;    //进程状态改变
        Max_Pri->process_state = 0;
        count++;
    }
    else{
        Max_Pri->process_state = 1;
    }
    Max_Pri->priority_number-=1;    //优先数减1
    printf(" %d     %d     %d        %d         %d      %d \n\n",Max_Pri->process_name,Max_Pri->priority_number,Max_Pri->arrive_time,Max_Pri->need_time,Max_Pri->used_time,Max_Pri->process_state);
    if(count == N){    //所有进程执行完毕 
        printf("        所有进程执行完毕！");
        return;
    }
    printf("        就绪队列：\n");
    print(head);    //输出就绪队列
    printf("\n");
    //****************************
    if(Max_Pri->process_state !=0){
        Move = head;
        while( Move->next!=NULL ){    //当被调出进程未完成时将其插入就绪队列尾部 
            Move = Move->next; 
        }
        Tail = Move;
        Max_Pri->cre = Tail;
        Max_Pri->next = NULL;
        Tail->next = Max_Pri;
        Max_Pri->process_state = -1;
    }
    //****************************
    Process_scheduling(head);
}

void print(struct PCB *head){    //输出队列函数 
    if(head->next == NULL){
        printf("就绪队列已空\n");
        return;
    }
    printf("name priority arr_time need_time use_CPU pro_state\n");
    struct PCB *fry = head->next;
    while(fry != NULL){
        printf(" %d     ",fry->process_name);
        printf("%d     ",fry->priority_number);
        printf("%d        ",fry->arrive_time);
        printf("%d         ",fry->need_time);
        printf("%d      ",fry->used_time);
        printf("%d ",fry->process_state);
        printf("\n");
        fry = fry->next;    
    }
    printf("\n"); 
}

int main(){
    struct PCB *head;    //头指针
    struct PCB Pro[N+1];    //创建 N+1 个进程
    head = &Pro[0];
    srand(time(0));
    
    //****************************
    //设置进程参数
    Pro[0].process_name = 0;
    Pro[0].cre = NULL;
    Pro[0].next = &Pro[1];
    Pro[0].priority_number = 0;
    int i=0;
    for(i=1;i<=N;i++){
        Pro[i].process_name = i;
        Pro[i].priority_number = rand()%10;
        while(Pro[i].priority_number == 0){
            Pro[i].priority_number = rand()%10;
        }
        Pro[i].arrive_time = i;
        Pro[i].need_time = rand()%7;
        while(Pro[i].need_time == 0){
            Pro[i].need_time = rand()%7;
        }
        Pro[i].used_time = 0;
        Pro[i].process_state = -1;
    }
    for(i=1;i<=N;i++){    //形成双向队列
        if( i == N ){
            Pro[i].cre = &Pro[i-1];
            Pro[i].next = NULL;
            break;
        }
        Pro[i].cre = &Pro[i-1];
        Pro[i].next = &Pro[i+1];
    }
    //****************************
    
    printf("        进程初始状态: \n");
    print(head);    //输出初始队列状态
    
    Process_scheduling(head);    //调用进程调度函数(最高优先级)
    
    return 0;
}

（运行结果部分截图）

10:58:16

2018-05-12