【操作系统实验6】CPU调度程序模拟实现

一、实验目标

加深对操作系统CPU调度以及调度算法的理解

二、实验内容

1.思路

1）

• 单处理器环境下，针对最短作业优先算法(SJF)和优先级调度算法(Priority)，分别模拟实现抢占调度和非抢占调度的调度程序
• 设计使用三个队列，分别为就绪队列(readyQueue)、运行队列(runningQueue)、等待队列(waitingQueue)
• 进程状态三种，分别为就绪状态：0、运行状态：1、等待状态：2
• 输入：task.txt 文件和指定调度算法 - task.txt 文件为需要调度的进程集- 非抢占 SJF: sjf- 抢占 SJF: psjf- 非抢占 Priority: pprio- 抢占 Priority: prio
• 输出：按照所指定的调度算法，显示调度结果 - 比如：P2:2、P1:2、P3:1、P4:5

2）1数据结构
本次实验的数据结构参考了 pintos 中的线程调度：使⽤ PCB 结构体表示进程、使⽤双向链表管理进程。
PCB 结构体定义如下：

typedefstructPCB{int pid;// pidint time_release;// release timeint time_cpu;// total CPU execution timeint time_remaining;// remaining CPU execution tineint priority;// priorityenumProcessState state;// process statestructPCB* prev;// previous process pointerstructPCB* next;// next process pointer} PCB;

为何适配该实验，双向链表上实现了⼀些常⽤的操作函数。由于本实验中需要通过进程的优先级和剩余 CPU 时间进⾏排序，所以还参考 pintos 实现了有序插⼊的操作。

1/* Operations on list. */2 List*list_create();3voidlist_delete(List* list);45/* Iteration operations */6 ListElem*list_begin(List* list);7 ListElem*list_next(ListElem* elem);8 ListElem*list_end(List* list);910/* Removal operations. */11 ListElem*list_remove(ListElem* elem);12 ListElem*list_pop_front(List* list);1314/* Insertion operations. */15voidlist_insert(ListElem* before, ListElem* elem);16voidlist_insert_ordered(List* list, ListElem* elem,17 list_less_func* less_func);18voidlist_push_back(List* list, ListElem* elem);1920/* Get list properties. */21size_tlist_size(List* list);22intlist_empty(List* list);

3）算法
本实验中⾸先计算出运⾏完所有进程所需要的 CPU 区间⻓度 T，然后使⽤ for 循环，令 i 从0 遍历到 T-1 来模拟实际 CPU 调度中定时器产⽣的时间⽚到时中断：i 每增加 1，代表 CPU执⾏了⼀个时间⽚，此时应该重新进⾏调度。
下⾯以最短作业优先调度为例概述调度算法，优先级调度算法与此类似，代码也极其相似。
在⼀个新的时间⽚到来时，将 CPU 分配给哪⼀个进程有两个需要考虑的因素 — 进程的到达时间与进程的剩余 CPU 区间。假如当前到来的是第 i 个时间⽚，只有到达时间（release time）⼩于等于 i 的进程才有机会被分配 CPU；随后我们需要在些进程中选择剩余 CPU 区间最短的作为执⾏进程。
由此得到的结论就是，我们需要先对进程的到达时间作为第⼀优先级、剩余 CPU 区间作为第⼆优先级进⾏排序。本实验采⽤的⽅法是在进程创建的时候就将其按照上述两个优先级插⼊到ready queue 中，使 ready queue 成为⼀个优先级队列。在⾮抢占式调度中，⼀个进程执⾏完⽆需执⾏其他操作；⽽在抢占式调度中，⼀个进程在该时间⽚内执⾏完后，需要判断其剩余 CPU 区间是否为 0，如果为 0，则需要将其重新按照上述两个优先级插⼊到队列中。
同理，如果采⽤优先级调度，上述的排列规则变为到达时间使第⼀优先级，⽽进程优先级是第⼆优先级。

2.代码

#include<stdint.h>#include<stdio.h>#include<stdlib.h>enumProcessState{
    PROCESS_READY,
    PROCESS_RUNNING
};typedefstructPCB{int pid;int time_release;int time_cpu;int time_remaining;int priority;enumProcessState state;structPCB* prev;structPCB* next;} PCB;typedef PCB ListElem;typedefstructList{
    ListElem head;
    ListElem tail;} List;/* Compares the value of two list elements A and B, given
   auxiliary data AUX.  Returns true if A is less than B, or
   false if A is greater than or equal to B. */typedefintlist_less_func(const ListElem* a,const ListElem* b);

PCB* process_running;
List* ready_queue;
List* terminated_list;char file_name[]="sched.txt";
FILE* file;/* Operations on list. */
List*list_create();voidlist_delete(List* list);

ListElem*list_begin(List* list);
ListElem*list_next(ListElem* elem);
ListElem*list_end(List* list);

ListElem*list_remove(ListElem* elem);
ListElem*list_pop_front(List* list);voidlist_insert(ListElem* before, ListElem* elem);voidlist_insert_ordered(List* list, ListElem* elem,
                         list_less_func* less_func);voidlist_push_back(List* list, ListElem* elem);size_tlist_size(List* list);intlist_empty(List* list);/* Operations on process. */
PCB*process_create(int pid,int time_release,int priority,int time_exec);voidprocess_sched_sjf(int cpu_time);voidprocess_sched_psjf(int cpu_time);intprocess_cmp_sjf(const ListElem* a,const ListElem* b);voidprocess_sched_prio(int cpu_time);voidprocess_sched_pprio(int cpu_time);intprocess_cmp_prio(const ListElem* a,const ListElem* b);voidprocess_print(int cnt);voidprint_header(int cpu_time);intget_total_cpu_time();

PCB*load_process_from_file();intmain(){int cpu_time, mode;
    PCB* process;
    file =fopen(file_name,"r");

    ready_queue =list_create();
    terminated_list =list_create();printf("Input schedule mode.\n1: sjf, 2: psjf, 3: prio, 4:pprio.\n");scanf("%d",&mode);switch(mode){case1:{while((process =load_process_from_file())!=NULL){list_insert_ordered(ready_queue, process, process_cmp_sjf);}
        cpu_time =get_total_cpu_time();printf("\n\n");print_header(cpu_time);process_sched_sjf(cpu_time);printf("\n\n");}break;case2:{while((process =load_process_from_file())!=NULL){list_insert_ordered(ready_queue, process, process_cmp_sjf);}
        cpu_time =get_total_cpu_time();printf("\n\n");print_header(cpu_time);process_sched_psjf(cpu_time);printf("\n\n");}break;case3:{while((process =load_process_from_file())!=NULL){list_insert_ordered(ready_queue, process, process_cmp_prio);}
        cpu_time =get_total_cpu_time();printf("\n\n");print_header(cpu_time);process_sched_prio(cpu_time);printf("\n\n");}break;case4:{while((process =load_process_from_file())!=NULL){list_insert_ordered(ready_queue, process, process_cmp_prio);}
        cpu_time =get_total_cpu_time();printf("\n\n");print_header(cpu_time);process_sched_pprio(cpu_time);printf("\n\n");}break;default:break;}list_delete(ready_queue);list_delete(terminated_list);return0;}

List*list_create(){
    List* list =(List*)malloc(sizeof(List));if(!list){printf("list_create(): malloc failed.\n");exit(1);}

    list->head.prev =NULL;
    list->head.next =&list->tail;
    list->tail.prev =&list->head;
    list->tail.next =NULL;return list;}voidlist_delete(List* list){
    ListElem* elem;while(!list_empty(list)){
        elem =list_pop_front(list);free(elem);}free(list);}

ListElem*list_begin(List* list){return list->head.next;}

ListElem*list_next(ListElem* elem){return elem->next;}

ListElem*list_end(List* list){return&list->tail;}

ListElem*list_remove(ListElem* elem){
    elem->prev->next = elem->next;
    elem->next->prev = elem->prev;return elem->next;}

ListElem*list_pop_front(List* list){
    ListElem* front =list_begin(list);list_remove(front);return front;}voidlist_insert(ListElem* before, ListElem* elem){
    elem->prev = before->prev;
    elem->next = before;
    before->prev->next = elem;
    before->prev = elem;}voidlist_push_back(List* list, ListElem* elem){list_insert(list_end(list), elem);}voidlist_insert_ordered(List* list, ListElem* elem,
                         list_less_func* less_func){
    ListElem* e;for(e =list_begin(list); e !=list_end(list); e =list_next(e))if(less_func(elem, e))break;list_insert(e, elem);}size_tlist_size(List* list){
    ListElem* elem;size_t cnt =0;for(elem =list_begin(list); elem !=list_end(list); elem =list_next(elem))
        cnt++;return cnt;}intlist_empty(List* list){return(list_begin(list)==list_end(list));}

PCB*process_create(int pid,int time_release,int priority,int time_exec){
    PCB* process =(PCB*)malloc(sizeof(PCB));if(!process){printf("process_create(): malloc failed.\n");exit(1);}

    process->pid = pid;
    process->time_release = time_release;
    process->time_cpu = time_exec;
    process->time_remaining = time_exec;
    process->priority = priority;
    process->state = PROCESS_READY;return process;}voidprocess_sched_sjf(int cpu_time){int i =0;
    PCB* next;for(; i < cpu_time; i++){
        process_running =list_begin(ready_queue);for(next =list_next(process_running); next !=list_end(ready_queue); next =list_next(next)){if(next->time_release > i)break;if(next->time_remaining < process_running->time_remaining)
                process_running = next;}
        i += process_running->time_remaining -1;list_remove(process_running);list_push_back(terminated_list, process_running);process_print(process_running->time_remaining);}}voidprocess_sched_psjf(int cpu_time){int i =0;
    PCB* next;for(; i < cpu_time;++i){
        process_running =list_begin(ready_queue);for(next =list_next(process_running); next !=list_end(ready_queue); next =list_next(next)){if(next->time_release > i)break;if(next->time_remaining < process_running->time_remaining)
                process_running = next;}
        process_running->time_remaining--;process_print(1);if(process_running->time_remaining >0){list_remove(process_running);list_insert_ordered(ready_queue, process_running, process_cmp_sjf);}else{list_remove(process_running);list_push_back(terminated_list, process_running);}}}intprocess_cmp_sjf(const ListElem* a,const ListElem* b){if(a->time_release != b->time_release)return(a->time_release < b->time_release);elsereturn(a->time_remaining < b->time_remaining);}voidprocess_sched_prio(int cpu_time){int i =0;
    PCB* next;for(; i < cpu_time; i++){
        process_running =list_begin(ready_queue);for(next =list_next(process_running); next !=list_end(ready_queue); next =list_next(next)){if(next->time_release > i)break;if(next->priority < process_running->priority)
                process_running = next;}
        i += process_running->time_remaining -1;list_remove(process_running);list_push_back(terminated_list, process_running);process_print(process_running->time_remaining);}}voidprocess_sched_pprio(int cpu_time){int i =0;
    PCB* next;for(; i < cpu_time;++i){
        process_running =list_begin(ready_queue);for(next =list_next(process_running); next !=list_end(ready_queue); next =list_next(next)){if(next->time_release > i)break;if(next->priority < process_running->priority)
                process_running = next;}
        process_running->time_remaining--;process_print(1);if(process_running->time_remaining >0){list_remove(process_running);list_insert_ordered(ready_queue, process_running, process_cmp_prio);}else{list_remove(process_running);list_push_back(terminated_list, process_running);}}}intprocess_cmp_prio(const ListElem* a,const ListElem* b){if(a->time_release != b->time_release)return(a->time_release < b->time_release);elsereturn(a->priority < b->priority);}voidprocess_print(int cnt){int i =0;for(; i < cnt;++i)printf("  P%d  ", process_running->pid);}voidprint_header(int cpu_time){int i =0;for(; i < cpu_time;++i)printf("|_____");printf("|\n");for(i =0; i <= cpu_time;++i)printf("%-6d", i);printf("\n");}intget_total_cpu_time(){int total_cpu_time =0;
    ListElem* elem =list_begin(ready_queue);for(; elem !=list_end(ready_queue); elem =list_next(elem))
        total_cpu_time += elem->time_remaining;return total_cpu_time;}

PCB*load_process_from_file(){int pid, time_release, time_cpu, priority;
    PCB* process =NULL;if(fscanf(file,"%d%d%d%d",&pid,&time_release,&priority,&time_cpu)!=EOF){
        process =process_create(pid, time_release, priority, time_cpu);}return process;}

3.过程及运行结果展示

从文本文件中输入信息（格式：进程ID， 到达时间， 优先级， 运行时间）

非抢占式最短作业优先调度

抢占式最短作业优先调度

非抢占式优先级调度

抢占式优先级调度

三、实验结论

通过本实验对于调度算法有了更加深刻的理解。
-最短作业优先调度：
抢占式：当新进来的进程的CPU区间比当前执行的进程所剩的CPU区间短，则抢占。
非抢占：为下一个最短优先，因为在就绪队列中选择最短CPU区间的进程放在队头。
-优先级调度算法：SJF是特殊的优先级调度算法，以CPU区间长度的倒数为优先级。
抢占式为如果进来的进程优先级高于运行的进程，则替换。
非抢占式只是在就绪队列中按优先级排队。
缺点：无线阻塞或饥饿。前者为一个优先级高且运行时间长的进程一直阻塞，后者为优先级低的进程永远都得不到执行。