处理机调度（实验）

参考先来先服务算法，尝试实现其他四种调度算法：短作业优先、高响应比、时间片轮转、多级反馈队列。要求实现短作业优先、高响应比以及时间片轮转算法; 多级反馈队列为选做。
a)除了多级反馈队列，其他算法采用非抢占调度
b)短作业优先算法使用例题一数据或程序内置数据，要求运行结果给出调度顺序、完成时间、周转时间、带权周转时间
c)高响应比算法使用例题二的数据，要求运行结果给出调度顺序、完成时间、周转时间、带权周转时间
d)时间片轮转算法可以使用程序内置数据，要求运行结果给出每个时间片是被哪个进程使用，每个进程完成时，要修改状态并输出提示。
e)多级反馈队列算法使用例题三的数据，要求运行结果给出正确的进程调度顺序和过程描述。

实验步骤：

分析算法，给出算法流程图
实现代码
结合运行结果分析解释

例题一：在单处理机环境下，对4个作业Job1、Job2、Job3、Job4进行非抢占式调度，它们的到达时间均为1，所需运行时间分别为9、16、3、11。
例题二：在单处理机环境下，对4个进程P1、P2、P3、P 4进行非抢占式调度，它们的到达时间分别为10、12、14、16，运行时间分别为8、12、4、6。
例题三：在某一操作系统中对进程调度采用多级反馈队列调度算法。现设定采用三级反馈队列调度算法，三个队列分别为I、II、III，对应时间片为2、4、8。现有四个进程A、B、C、D，到达时刻分别为0、5、7、12，执行时间分别为7、4、13、9。请写出整个进程调度过程。

PS: 例程eg1.c

//模拟实现各种CPU调度算法

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <time.h>

//#define NULL 0
#define getpch(type) (type*)malloc(sizeof(type))
typedef struct pcb PCB;
struct pcb {
    //定义进程控制块PCB
    int id; //标识符
    char name[10]; //名称
    int time_start; //到达时间
    int time_need; //服务时间
    int time_left; //剩余运行时间
    int used; //已使用的CPU时间
    // 在时间片机制中，time_need = time_left + time_used
    char state; //进程状态
};

//*********************系统函数**********************//
//停顿n秒
void _sleep(int n) {
    clock_t goal;
    goal = (clock_t)n * CLOCK_PER_SEC + clock();
    while(goal > clock());
}

//程序暂停，按任意键继续
char _keygo() {
    char c;
    printf("按任意键继续......\n");
    c = getch();

    return c;
}

//*********************用户函数**********************//

//--------------------数据设置区域-------------------//

int time_unit = 2; //时间片长度
const maxmun = 10; //最大进程数量
int num = 5; //实际进程数量
//在程序内设置进程数据，不必手工输入，数据来自课本P76图3-4
PCB pcbdata[maxmun] = {
    {1000, "A", 0, 4, 4, 0, 'R'},
    {1001, "B", 1, 3, 3, 0, 'R'},
    {1002, "C", 2, 5, 5, 0, 'R'},
    {1003, "D", 3, 2, 2, 0, 'R'},
    {1004, "E", 4, 4, 4, 0, 'R'},
};
int ready[maxmun];//就绪队列，存放进程在pcbdata中的位置
/**
 * 例如上面pcbdata中的数据经过某种调度算法排序为CBADE
 * 就绪队列第一个进程为C
 * 存放在ready数组的第一个数值为2，因为pcbdata[2]是进程C的PCB
 * 就绪队列第一个进程为B
 * 存放在ready数组的第一个数值为1，因为pcbdata[1]是进程B的PCB
**/
int order[maxmun]; //记录排序使用哪个数值作为排序对象
//手工输入数据
void input() {
    int i;
    printf("进程总数为：");
    scanf("%d", &num);
    for(i = 0; i < num; i++) {
        pcbdata[i].id = 1000 + i; //系统自动分配标识符
        printf("输入第%d个进程名：", i+1);
        scanf("%s", &pcbdata[i].name);
        printf("输入第%d个进程到达时间：", i+1);
        scanf("%s", &pcbdata[i].time_start);
        printf("输入第%d个进程服务时间：", i+1);
        scanf("%s", &pcbdata[i].time_need);
    //剩余运行时间，初始值和服务时间相同
        pcbdata[i].time_left = pcbdata[i].time_need;
        printf("\n");
        pcbdata[i].time_used = 0; //已使用CPU时间，初始值为0
        pcbdata[i].satate = 'R'; //进程初始状态为就绪R
    }
}

//----------------------调度函数---------------------//
// 先来先服务算法
// 已到达时间为排序对象，从小到大排序，静态排序
void FCFS() {
    int i, j, temp;
    double k;
    for(i = 0; i < num; i++) {
        order[i] = pcbdata[i].time_start;
        ready[i] = i;
    }
    //冒泡排序
    for(i = 0; i < num; i++) {
        for(j = i+1; j < num; j++) {
            if(order[i] > order[j]) {
                temp = order[i];
                order[i] = order[j];
                order[j] = temp;
                temp = ready[i];
                ready[i] = ready[j];
                ready[j] = temp;
            }
        }
    }
    printf("---先来先服务算法调度：非抢占，无时间片---\n");
    temp = pcbdata[ready[0]].time_start;
    for(i = 0; i < num; i++) {
        printf("第%d个进程-- %s, ", i+1, pcbdata[ready[i]].name);
        printf("到达时间 -- %d，服务时间 -- %d\n", pcbdata[ready[i]].time_start, pcbdata[ready[i]].time_need);
        printf("本进程正在运行......");
        _sleep(1);
        printf("运行完毕\n");
        temp += pcbdata[ready[i]].time_need; //进程完成时间
        j = temp - pcbdata[ready[i]].time_start; //周转时间
        k = (float)j/pcbdata[ready[i]].time_need; //带权周转时间
        printf("完成时间 -- %d, 周转时间-- %d, 带权周转时间 -- %.lf\n", temp, j, k);
    }
    printf("-------所有进程调度完毕-------\n");
}

//短作业优先算法
//以服务时间为排序对象，从小到大排序，可能有多次排序
void SJF() {
    printf("---本算法未实现---\n");
}

//高响应比算法
//以响应比为排序对象，从小到大排序，可能有多次排序
void HRF() {
    printf("---本算法未实现---\n");
}

//按照先来先服务并使用时间片轮转
void Timelice() {
    printf("---本算法未实现---\n");
}

//多级反馈调度队列，抢占式调度
void MRLA() {
    printf("---本算法未实现---\n");
}

//主函数
void main() {
    int i = 0, sch = 99;
    //input();
    while(sch != 0) {
        printf("\n请选择其中一种调度算法：\n");
        printf("(1)先来先服务FCFS\n");
        printf("(2)短作业优先SJF\n");
        printf("(3)高响应比HRF\n");
        printf("(4)时间片轮转Timelice\n");
        printf("(5)多级反馈调度队列MRLA\n");
        printf("(0)退出：\n");
        printf("请输入上述一个数字：");
        scanf("%d", &sch);
        switch(sch) {
            case 1: FCFS(); break;
            case 2: SJF(); break;
            case 3: HRF(); break;
            case 4: Timelice(); break;
            case 5: MRLA(); break;
            case 0: printf("退出程序\n"); break;
        }
    }
    _keygo();
}

//-------------------------以下函数主要用于程序调试跟踪----------------------------//
//显示一个PCB的具体参数内容
void dis_pcb(PCB * pr) {
    printf("%s的PCB：\n", pr->name);
    printf("标识符--%d , 状态--%c , 到达时间--%d\n", pr->id, pr->state, pr->time_start);
    printf("服务时间--%d , 生于运行时间--%d , 已用时间--%d\n", pr->time_need, pr->time_left, pr->time_used);
    printf("--------------------------------------------\n");
}

//显示所有进程PCB
void dis_pcb_all() {
    int i;
    printf("****当前所有进程状态****\n");
    for(i = 0; i < num; i++) {
        dis_pcb(&pcbdata[i]);
    }
}

//显示就绪队列
void dis_ready() {
    int i;
    printf("当前就绪队列为：");
    for(i = 0; i < num-1; i++) {
        printf("%s--", pcbdata[order[i]].name);
    }
    printf("%s\n", pcbdata[order[i]].name);
}