操作系统之进程调度算法-FCFS，RR，SJF

本次重要模拟三种进程调度算法即

• 先来先服务（FCFS）
• 时间片轮转（RR）
• 短进程优先（SJF）

并分别计算他们的作业周转时间和带权周转时间以及平均作业周转时间和平均带权周转时间。

首先定义 进程控制块(PCB)结构体

mypcb.h

#ifndef _MY_PCB_H
#define _MY_PCB_H

#include <stddef.h>

#define PROCESS_RUNNING  1
#define PROCESS_READY    2
#define PROCESS_CREATE	 3
#define PROCESS_BLOCKING 4
#define PROCESS_DEAD     5

typedef struct PCB{
    int pid;    // 进程号
    int status; // 进程状态
    int jid;     // 作业号

}PCB;


// 进程初始化
void pcb_init(PCB *pcb, int pid, int status, int jid);

// 判断进程是否全部死亡
int is_all_dead(PCB *pcb);

#endif

mypcb.c

#include "mypcb.h"

void pcb_init(PCB *pcb, int pid, int status, int jid)
{
    pcb[pid].pid = pid;
    pcb[pid].status = status;
    pcb[pid].jid = jid;
}

int is_all_dead(PCB *pcb)
{
    for(size_t i = 0; i < 10; i++){
        if(pcb[i].status != PROCESS_DEAD){
            return 0;
        }
    }
    return 1;
}

接下来是FCFS

FCFS.h

#ifndef _FCFS_H
#define _FCFS_H


#include "mypcb.h"
#include <stdio.h>

void FCFS(PCB *pcb, int *job);

#endif

FCFS.c

/**
 * 进程调度之先来先服务算法
 * M.J
 * Fri Oct 18 21:56:21 DST 2019
 */

#include "FCFS.h"

int fcfs_clock = 0; //时钟

double fcfs_r_turn_time_total = 0;
double fcfs_turn_time_total = 0;
// CPU执行
void fcfs_call_cpu(PCB *pcb, int *job){
    pcb->status = PROCESS_RUNNING;

    int each_time = job[pcb->jid];
    printf("pid =%d jid=%d call_cpu[%d-",pcb->pid,pcb->jid,fcfs_clock);
    fcfs_clock += job[pcb->jid];
    job[pcb->jid] = 0;
    printf("%d]\n",fcfs_clock);
    printf("pid=%d jid=%d finshed turn_time=%d r_turn_time=%lf\n",\
            pcb->pid,pcb->jid,fcfs_clock,fcfs_clock/(each_time * 1.0));
    fcfs_r_turn_time_total += fcfs_clock/(each_time * 1.0);
    fcfs_turn_time_total += fcfs_clock;
    pcb->status = PROCESS_DEAD;
}

void FCFS(PCB *pcb, int *job)
{

    // 假设作业进入顺序为job[0]~job[9]
    //执行
    while(1){
        for(size_t i = 0; i < 10; i++){
            if(pcb[i].status == PROCESS_READY){
                fcfs_call_cpu(&pcb[i],job);
            }
        }

        if(is_all_dead(pcb)){
            printf("ave_turn_time=%lf ave_r_turn_time=%lf\n",fcfs_turn_time_total / 10.0 ,fcfs_r_turn_time_total / 10);
            break;
        }
    }

}

对于短进程优先算法我们还需要一个排序算法将作业排序

quicksort.h

#ifndef _QUICK_SORT_H
#define	_QUICK_SORT_H

void quick_sort(int a[], int size,int *work_order);
void array_copy(int *src,int src_size, int *dst, int dst_size);

#endif

quicksort.c

/**
 *快速排序
 *M.J
 *Sat Oct 19 08:35:25 UTC 2019
 */
      
#include <stdlib.h>     

#include "quicksort.h"

// 设置排序规则
int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}


// 
void quick_sort(int a[], int size,int *work_order)
{
	int b[size];
	array_copy(a,10,b,10);
	qsort(b, size, sizeof(int), compare);

	for(size_t i = 0; i < size; i++){
		for(size_t j = 0; j < size; j++){
			if(a[j] == b[i]){
				work_order[i] = j;
			}
		}
	}
	
	return ;
	
}

void array_copy(int *src,int src_size, int *dst, int dst_size)
{
	if (dst_size < src_size){
		return;
	}
	for(size_t i = 0; i < src_size; i++){
		dst[i] = src[i];
	}
}

SJF.h

#ifndef _SJF_H
#define _SJF_H

#include "mypcb.h"
#include <stdio.h>

void SJF(PCB *pcb, int *job);

#endif

SJF.c

/**
 *进程调度之短作业优先算法
 *M.J
 *Sat Oct 19 08:31:25 UTC 2019
 */
#include "mypcb.h"
#include "quicksort.h"
#include "SJF.h"
#include <stdio.h>

int sjf_clock = 0; //时钟

double sjf_r_turn_time_total = 0;
double sjf_turn_time_total = 0;
// CPU执行
void sjf_call_cpu(PCB *pcb, int *job){
    pcb->status = PROCESS_RUNNING;

    int each_time = job[pcb->jid];

    printf("pid =%d jid=%d call_cpu[%d-",pcb->pid,pcb->jid,sjf_clock);
    sjf_clock += job[pcb->jid];
    job[pcb->jid] = 0;
    printf("%d]\n",sjf_clock);
    printf("pid=%d jid=%d finshed turn_time=%d r_turn_time=%lf\n",\
            pcb->pid,pcb->jid,sjf_clock,sjf_clock/(each_time * 1.0));
    sjf_r_turn_time_total += sjf_clock/(each_time * 1.0);
    sjf_turn_time_total += sjf_clock;
    pcb->status = PROCESS_DEAD;
}

void SJF(PCB *pcb, int *job)
{
	// 作业序列
	int work_order[10];
	
	quick_sort(job,10,work_order);
	
	//执行
    while(1){
        for(size_t i = 0; i < 10; i++){
            if(pcb[work_order[i]].status == PROCESS_READY){
                sjf_call_cpu(&pcb[work_order[i]],job);
            }
        }

        if(is_all_dead(pcb)){
            printf("ave_turn_time=%lf ave_r_turn_time=%lf\n",sjf_turn_time_total / 10.0 ,sjf_r_turn_time_total / 10);
            break;
        }
    }
}

RR.h

#ifndef _RR_H
#define _RR_H


#include "mypcb.h"
#include <stdio.h>

void RR(PCB *pcb, int *job);

#endif

RR.c

/**
 * 进程调度之时间片轮转法
 * M.J
 * Fri Oct 18 22:16:11 DST 2019
 */

#define RR_TIME_SLICE 5 // 时间片大小

#include "RR.h"

int rr_clock = 0; //时钟

double rr_r_turn_time_total = 0;
double rr_turn_time_total = 0;

int rr_each_time[10] = {0};
// CPU执行
void rr_call_cpu(PCB *pcb, int *job){
    int each_time = 0;
    rr_each_time[pcb->jid] = job[pcb->jid];
    pcb->status = PROCESS_RUNNING;
    printf("pid =%d jid=%d call_cpu[%d-",pcb->pid,pcb->jid,rr_clock);
    if(job[pcb->jid] > RR_TIME_SLICE){
        job[pcb->jid] -= RR_TIME_SLICE;
        rr_clock += 5;
        printf("%d]\n",rr_clock);
    }else{
        each_time = rr_clock;
        rr_clock += job[pcb->jid];
        job[pcb->jid] = 0;
        pcb->status = PROCESS_DEAD;
        printf("%d]\n",rr_clock);
        printf("pid=%d jid=%d finshed turn_time=%d r_turn_time=%lf\n",\
            pcb->pid,pcb->jid,rr_clock,rr_clock/(rr_each_time[pcb->jid] * 1.0));
        rr_r_turn_time_total += rr_clock/(rr_each_time[pcb->jid] * 1.0);
        rr_turn_time_total += rr_clock;
        return ;
    }
    pcb->status = PROCESS_READY;
}


void RR(PCB *pcb, int *job)
{
    //执行
    while(1){
        for(size_t i = 0; i < 10; i++){
            if(pcb[i].status == PROCESS_READY){
                rr_call_cpu(&pcb[i],job);
            }
        }

        if(is_all_dead(pcb)){
            printf("ave_turn_time=%lf ave_r_turn_time=%lf\n",rr_turn_time_total / 10.0 ,rr_r_turn_time_total / 10.0);
            break;
        }
    }

}

最后就是我们的main函数了哈哈！

main.c

#include "mypcb.h"
#include "RR.h"
#include "FCFS.h"
#include "SJF.h"

#include <stdio.h>


#define MAX_JOB_SIZE 10 // 最大作业数


//每个作业的周转时间
//平均周转时间
//带权周转时间
int main()
{
    // 定义JOB数组 存放时长
    int job[MAX_JOB_SIZE] = {
        10, 12, 24,  5, 19,
        11, 22, 33, 44, 55
    };

    // 定义PCB块
    PCB pcb[10];

    // 初始化进程并分配作业
    for(size_t i = 0; i < 10; i++){
        pcb_init(pcb,i,PROCESS_READY,i);
    }

    printf("+---[Process Schedule Demo]--+\n");
    printf("|1.FCFS                      |\n");
    printf("|2.RR                        |\n");
    printf("|3.SJF                       |\n");
    printf("|4.Exit                      |\n");
    printf("+----------------------------+\n>");

    int op = 3;
    scanf("%d",&op);
    switch (op)
    {
    case 1:
        FCFS(pcb,job);
        break;
    case 2:
        RR(pcb,job);
        break;
	case 3:
		SJF(pcb,job);
		break;
    default:
        break;
    }
    return 0;
}

编译和运行：

这里我为什么要放一张图片？

当然是展示一下我的Desktop PC终于升级到win10 1903了！（虽然丢失了很多东西）

选1执行结果：

>1
pid =0 jid=0 call_cpu[0-10]
pid=0 jid=0 finshed turn_time=10 r_turn_time=1.000000
pid =1 jid=1 call_cpu[10-22]
pid=1 jid=1 finshed turn_time=22 r_turn_time=1.833333
pid =2 jid=2 call_cpu[22-46]
pid=2 jid=2 finshed turn_time=46 r_turn_time=1.916667
pid =3 jid=3 call_cpu[46-51]
pid=3 jid=3 finshed turn_time=51 r_turn_time=10.200000
pid =4 jid=4 call_cpu[51-70]
pid=4 jid=4 finshed turn_time=70 r_turn_time=3.684211
pid =5 jid=5 call_cpu[70-81]
pid=5 jid=5 finshed turn_time=81 r_turn_time=7.363636
pid =6 jid=6 call_cpu[81-103]
pid=6 jid=6 finshed turn_time=103 r_turn_time=4.681818
pid =7 jid=7 call_cpu[103-136]
pid=7 jid=7 finshed turn_time=136 r_turn_time=4.121212
pid =8 jid=8 call_cpu[136-180]
pid=8 jid=8 finshed turn_time=180 r_turn_time=4.090909
pid =9 jid=9 call_cpu[180-235]
pid=9 jid=9 finshed turn_time=235 r_turn_time=4.272727
ave_turn_time=93.400000 ave_r_turn_time=4.316451

C:\Users\Michael Jiang\Desktop\OS\Process_Schedule_Algorithms>

选2执行结果：

>2
pid =0 jid=0 call_cpu[0-5]
pid =1 jid=1 call_cpu[5-10]
pid =2 jid=2 call_cpu[10-15]
pid =3 jid=3 call_cpu[15-20]
pid=3 jid=3 finshed turn_time=20 r_turn_time=4.000000
pid =4 jid=4 call_cpu[20-25]
pid =5 jid=5 call_cpu[25-30]
pid =6 jid=6 call_cpu[30-35]
pid =7 jid=7 call_cpu[35-40]
pid =8 jid=8 call_cpu[40-45]
pid =9 jid=9 call_cpu[45-50]
pid =0 jid=0 call_cpu[50-55]
pid=0 jid=0 finshed turn_time=55 r_turn_time=11.000000
pid =1 jid=1 call_cpu[55-60]
pid =2 jid=2 call_cpu[60-65]
pid =4 jid=4 call_cpu[65-70]
pid =5 jid=5 call_cpu[70-75]
pid =6 jid=6 call_cpu[75-80]
pid =7 jid=7 call_cpu[80-85]
pid =8 jid=8 call_cpu[85-90]
pid =9 jid=9 call_cpu[90-95]
pid =1 jid=1 call_cpu[95-97]
pid=1 jid=1 finshed turn_time=97 r_turn_time=48.500000
pid =2 jid=2 call_cpu[97-102]
pid =4 jid=4 call_cpu[102-107]
pid =5 jid=5 call_cpu[107-108]
pid=5 jid=5 finshed turn_time=108 r_turn_time=108.000000
pid =6 jid=6 call_cpu[108-113]
pid =7 jid=7 call_cpu[113-118]
pid =8 jid=8 call_cpu[118-123]
pid =9 jid=9 call_cpu[123-128]
pid =2 jid=2 call_cpu[128-133]
pid =4 jid=4 call_cpu[133-137]
pid=4 jid=4 finshed turn_time=137 r_turn_time=34.250000
pid =6 jid=6 call_cpu[137-142]
pid =7 jid=7 call_cpu[142-147]
pid =8 jid=8 call_cpu[147-152]
pid =9 jid=9 call_cpu[152-157]
pid =2 jid=2 call_cpu[157-161]
pid=2 jid=2 finshed turn_time=161 r_turn_time=40.250000
pid =6 jid=6 call_cpu[161-163]
pid=6 jid=6 finshed turn_time=163 r_turn_time=81.500000
pid =7 jid=7 call_cpu[163-168]
pid =8 jid=8 call_cpu[168-173]
pid =9 jid=9 call_cpu[173-178]
pid =7 jid=7 call_cpu[178-183]
pid =8 jid=8 call_cpu[183-188]
pid =9 jid=9 call_cpu[188-193]
pid =7 jid=7 call_cpu[193-196]
pid=7 jid=7 finshed turn_time=196 r_turn_time=65.333333
pid =8 jid=8 call_cpu[196-201]
pid =9 jid=9 call_cpu[201-206]
pid =8 jid=8 call_cpu[206-211]
pid =9 jid=9 call_cpu[211-216]
pid =8 jid=8 call_cpu[216-220]
pid=8 jid=8 finshed turn_time=220 r_turn_time=55.000000
pid =9 jid=9 call_cpu[220-225]
pid =9 jid=9 call_cpu[225-230]
pid =9 jid=9 call_cpu[230-235]
pid=9 jid=9 finshed turn_time=235 r_turn_time=47.000000
ave_turn_time=139.200000 ave_r_turn_time=49.483333

C:\Users\Michael Jiang\Desktop\OS\Process_Schedule_Algorithms>

选3执行结果：

>3
pid =3 jid=3 call_cpu[0-5]
pid=3 jid=3 finshed turn_time=5 r_turn_time=1.000000
pid =0 jid=0 call_cpu[5-15]
pid=0 jid=0 finshed turn_time=15 r_turn_time=1.500000
pid =5 jid=5 call_cpu[15-26]
pid=5 jid=5 finshed turn_time=26 r_turn_time=2.363636
pid =1 jid=1 call_cpu[26-38]
pid=1 jid=1 finshed turn_time=38 r_turn_time=3.166667
pid =4 jid=4 call_cpu[38-57]
pid=4 jid=4 finshed turn_time=57 r_turn_time=3.000000
pid =6 jid=6 call_cpu[57-79]
pid=6 jid=6 finshed turn_time=79 r_turn_time=3.590909
pid =2 jid=2 call_cpu[79-103]
pid=2 jid=2 finshed turn_time=103 r_turn_time=4.291667
pid =7 jid=7 call_cpu[103-136]
pid=7 jid=7 finshed turn_time=136 r_turn_time=4.121212
pid =8 jid=8 call_cpu[136-180]
pid=8 jid=8 finshed turn_time=180 r_turn_time=4.090909
pid =9 jid=9 call_cpu[180-235]
pid=9 jid=9 finshed turn_time=235 r_turn_time=4.272727
ave_turn_time=87.400000 ave_r_turn_time=3.139773

选4是退出。