实验六、作业调度算法模拟

一、实验目的

1. 掌握周转时间、等待时间、平均周转时间等概念及其计算方法。

2. 理解五种常用的进程调度算法（FCFS、SJF、HRRF、HPF、RR），区分算法之间的差异性，并用C语言模拟实现各算法。
3. 了解操作系统中高级调度、中级调度和低级调度的区别和联系。

二、实验环境

• 硬件环境：计算机一台，局域网环境；
• 软件环境：Linux Ubuntu 操作系统，gcc 编译器；

三、实验内容和步骤

1. 实验说明

2. 基本概念
   * 程序：程序是指静态的指令集合，它不占用系统的运行资源，可以长久地保存在磁盘中。
   * 进程：
   进程是指进程实体（由程序、数据和进程控制块构成）的运行过程，是系统进行资源分配和调度的一个独立单位。进程执行程序，但进程与程序之间不是一一对应的。通过多次运行，一个程序可以包含多个进程；通过调用关系，同一进程可以被多个程序包含（如一个DLL文件可以被多个程序运用）。
   * 作业：
   作业由一组统一管理和操作的进程集合构成，是用户要求计算机系统完成的一项相对独立的工作。作业可以是完成了编译、链接之后的一个用户程序，也可以是各种命令构成的一个脚本。
   * 作业调度：
   作业调度是在资源满足的条件下，将处于后备状态的作业调入内存，同时生成与作业相对应的进程，并为这些进程提供所需要的资源。作业调度适用于多道批处理系统中的批处理作业。根据作业控制块中的信息，检查系统是否满足作业的资源要求，只有在满足作业调度的资源需求的情况下，系统才能进行作业调度。

3. 基本调度算法
   1. 先来先服务（First-Come First-Served，FCFS）调度算法
   先来先服务调度算法遵循按照进入后备队列的顺序进行调度的原则。该算法是一种非抢占式的算法，是到目前为止最简单的调度算法，其编码实现非常容易。该算法仅考虑了作业到达的先后顺序，而没有考虑作业的执行时间长短、作业的运行特性和作业对资源的要求。
   2. 短作业优先（Shortest-Job-First，SJF）调度算法
   短作业优先调度算法根据作业控制块中指出的执行时间，选取执行时间最短的作业优先调度。本实验中规定，该算法是非抢占式的，即不允许立即抢占正在执行中的长进程，而是等当前作业执行完毕再进行调度。
   3. 响应比高者优先（HRRF）调度算法
   FCFS调度算法只片面地考虑了作业的进入时间，短作业优先调度算法考虑了作业的运行时间而忽略了作业的等待时间。响应比高者优先调度算法为这两种算法的折中。响应比为作业的响应时间与作业需要执行的时间之比。作业的响应时间为作业进入系统后的等待时间与作业要求处理器处理的时间之和。
   4. 优先权高者优先（Highest-Priority-First，HPF）调度算法
   优先权高者优先调度算法与响应比高者优先调度算法十分相似，根据作业的优先权进行作业调度，每次总是选取优先权高的作业优先调度。作业的优先权通常用一个整数表示，也叫优先数。优先数的大小与优先权的关系由系统或者用户规定。优先权高者优先调度算法综合考虑了作业执行时间和等待时间的长短、作业的缓急度，作业对外部设备的使用情况等因素，根据系统设计目标和运行环境而给定各个作业的优先权，决定作业调度的先后顺序。

4. 本实验所选用的调度算法均默认为非抢占式调度，实验所用的测试数据如下表所示。

作业Id	到达时间	执行时间	优先权
1	800	50	0
2	815	30	1
3	830	25	2
4	835	20	2
5	845	15	2
6	700	10	1
7	820	5	0

作业的数据结构：

typedef struct node {
int number; // 作业号
int reach_time;// 作业抵达时间
int need_time;// 作业的执行时间
int privilege;// 作业优先权
float excellent;// 响应比
int start_time;// 作业开始时间
int wait_time;// 等待时间
int visited;// 作业是否被访问过
bool isreached;// 作业是否已经抵达
} job;

重要函数说明：

// 初始化所有作业信息
void initial_jobs()
// 重置所有作业信息
void reset_jinfo()
// 找到执行时间最短的作业。输入参数：所有的作业信息及待查找的作业总数，输出为执行时间最短的作业id
int findminjob(job jobs[],int count)
// 找到达到最早的作业 输入参数：所有的作业信息及待查找的作业总数，输出参数为最早达到的作业id
int findrearlyjob(job jobs[],int count)
// 读取作业的基本信息
void readJobdata()
// 先来先服务算法
void FCFS()
// 短作业优先算法 输入参数：所有的作业信息及待查找的作业总数
void SFJschdulejob(job jobs[],int count)

3. 实验代码

▶

Code

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

// 最大作业数量
#define MAXJOB 50
// 作业的数据结构
typedef struct node {
    int number;//作业号
    int reach_time;//作业抵达时间
    int need_time;//作业的执行时间
    int privilege;//作业优先权
    float excellent;//响应比
    int start_time;//作业开始时间
    int wait_time;//等待时间
    int visited;//作业是否被访问过
    bool isreached;//作业是否抵达
} job;
// 作业序列
job jobs[MAXJOB];
// 作业数量
int quantity;
// 初始化作业序列
void initial_jobs() {
    int i;
    for (i = 0; i < MAXJOB; i++) {
        jobs[i].number = 0;
        jobs[i].reach_time = 0;
        jobs[i].privilege = 0;
        jobs[i].excellent = 0;
        jobs[i].start_time = 0;
        jobs[i].wait_time = 0;
        jobs[i].visited = 0;
        jobs[i].isreached = false;
    }
    quantity = 0;
}

// 重置全部作业信息
void reset_jinfo() {
    int i;
    for (i = 0; i < MAXJOB; i++) {
        jobs[i].start_time = 0;
        jobs[i].wait_time = 0;
        jobs[i].visited = 0;
    }
}

// 查找当前 current_time 已到达未执行的最短作业,若无返回-1
int findminjob(job jobs[], int current_time) {
    int mincost = 1000;
    int minloc = -1;
    int i;
    for (i = 0; i < quantity; i++) {
        if (jobs[i].reach_time <= current_time && jobs[i].visited == 0) {
            if (jobs[i].need_time < mincost) {
                mincost = jobs[i].need_time;
                minloc = i;
            }
        }
    }
    if (minloc == -1) {
        int early_time = 10000;
        for (i = 0; i < quantity; i++) {
            if (jobs[i].reach_time < early_time && jobs[i].visited != 1) {
                early_time = jobs[i].reach_time;
                mincost = jobs[i].need_time;
                minloc = i;
            } else if (jobs[i].reach_time == early_time && jobs[i].need_time < mincost && jobs[i].visited != 1) {
                mincost = jobs[i].need_time;
                minloc = i;
            }
        }
    }
    return minloc;
}

// 查找最早到达作业，若全部到达返回-1.
int findrearlyjob(job jobs[], int count) {
    int rearlyloc = -1;
    int rearlyjob = -1;
    int i;
    for (i = 0; i < count; i++) {
        if (rearlyloc == -1) {
            if (jobs[i].visited == 0) {
                rearlyloc = i;
                rearlyjob = jobs[i].reach_time;
            }
        } else if (rearlyjob > jobs[i].reach_time && jobs[i].visited == 0) {
            rearlyjob = jobs[i].reach_time;
            rearlyloc = i;
        }
    }
    return rearlyloc;
}

// 读取作业数据
void readJobdata() {
    FILE *fp;
    char fname[20];
    int i;
    // 输入测试文件文件名
    printf("please input job data file name\n");
    scanf("%s", fname);
    if ((fp = fopen(fname, "r")) == NULL) {
        printf("error, open file failed, please check filename:\n");
    } else {
        // 依次读取作业信息
        while (!feof(fp)) {
            int num;
            if (fscanf(fp, "%d %d %d %d", &jobs[quantity].number, &jobs[quantity].reach_time, &jobs[quantity].need_time,
                       &jobs[quantity].privilege)) {
                quantity++;
            }

        }
        quantity--;
        // 打印作业信息
        printf("output the origin job data\n");
        printf("---------------------------------------------------------------------\n");
        printf("\tjobID\treachtime\tneedtime\tprivilege\n");
        for (i = 0; i < quantity; i++) {
            printf("\t%-8d\t%-8d\t%-8d\t%-8d\n", jobs[i].number, jobs[i].reach_time, jobs[i].need_time,
                   jobs[i].privilege);
        }
    }
}

// FCFS
void FCFS() {
    int i;
    int current_time = 0;
    int loc;
    int total_waitime = 0;
    int total_roundtime = 0;
    // 获取最近到达的作业
    loc = findrearlyjob(jobs, quantity);
    // 输出作业流
    printf("\n\nFCFS算法作业流\n");
    printf("------------------------------------------------------------------------\n");
    printf("\tjobID\treachtime\tstarttime\twaittime\troundtime\n");
    current_time = jobs[loc].reach_time;
    // 每次循环找出最先到达的作业并打印相关信息
    for (i = 0; i < quantity; i++) {
        if (jobs[loc].reach_time > current_time) {
            jobs[loc].start_time = jobs[loc].reach_time;
            current_time = jobs[loc].reach_time;
        } else {
            jobs[loc].start_time = current_time;
        }
        jobs[loc].wait_time = current_time - jobs[loc].reach_time;
        printf("\t%-8d\t%-8d\t%-8d\t%-8d\t%-8d\n", jobs[loc].number, jobs[loc].reach_time, jobs[loc].start_time,
               jobs[loc].wait_time,
               jobs[loc].wait_time + jobs[loc].need_time);
        jobs[loc].visited = 1;
        current_time += jobs[loc].need_time;
        total_waitime += jobs[loc].wait_time;
        total_roundtime = total_roundtime + jobs[loc].wait_time + jobs[loc].need_time;
        // 获取剩余作业中最近到达作业
        loc = findrearlyjob(jobs, quantity);
    }
    printf("总等待时间:%-8d 总周转时间:%-8d\n", total_waitime, total_roundtime);
    printf("平均等待时间: %4.2f 平均周转时间: %4.2f\n", (float) total_waitime / (quantity),
           (float) total_roundtime / (quantity));
}

// 短作业优先作业调度
void SFJschdulejob(job jobs[], int count) //6175432
{
    int i;
    int current_time = 0;
    int total_waitime = 0;
    int total_roundtime = 0;
    int loc;
    int earlyest = findrearlyjob(jobs, quantity);
    loc = findminjob(jobs, jobs[earlyest].reach_time);
    // 输出作业流
    printf("\n\nSFJ算法作业流\n");
    printf("------------------------------------------------------------------------\n");
    printf("\tjobID\treachtime\tstarttime\twaittime\troundtime\n");
    // 每次循环找出最短作业作业并打印相关信息e
    for (i = 0; i < quantity; i++) {
        if (jobs[loc].reach_time > current_time) {
            jobs[loc].start_time = jobs[loc].reach_time;
            current_time = jobs[loc].reach_time + jobs[loc].need_time;
            jobs[loc].wait_time = 0;
        } else {
            jobs[loc].start_time = current_time;
            jobs[loc].wait_time = current_time - jobs[loc].reach_time;
            current_time += jobs[loc].need_time;
        }

        printf("\t%-8d\t%-8d\t%-8d\t%-8d\t%-8d\n", jobs[loc].number, jobs[loc].reach_time, jobs[loc].start_time,
               jobs[loc].wait_time,
               jobs[loc].wait_time + jobs[loc].need_time);
        total_waitime += jobs[loc].wait_time;
        total_roundtime += jobs[loc].wait_time + jobs[loc].need_time;
        jobs[loc].visited = 1;
        loc = findminjob(jobs, current_time);
    }
    printf("总等待时间:%-8d 总周转时间:%-8d\n", total_waitime, total_roundtime);
    printf("平均等待时间: %4.2f 平均周转时间: %4.2f\n", (float) total_waitime / (quantity),
           (float) total_roundtime / (quantity));
}

int updatePrivilege(job jobs[], int current_time) {
    int next = -1;
    int max_privilege = -1;
    int i;
    while (max_privilege == -1) {

        for (i = 0; i < quantity && jobs[i].reach_time <= current_time; i++) {
            if (jobs[i].visited != 1) {
                jobs[i].wait_time = current_time - jobs[i].reach_time;
                jobs[i].excellent = (double) jobs[i].wait_time / (double) jobs[i].need_time;
                if (jobs[i].excellent > max_privilege) {
                    max_privilege = jobs[i].excellent;
                    next = i;
                }
            }
        }
        if (max_privilege == -1) {
            int early_time = 10000, i;
            for (i = 0; i < quantity; i++) {
                if (jobs[i].reach_time < early_time && jobs[i].reach_time > current_time && jobs[i].visited != 1) {
                    early_time = jobs[i].reach_time;
                    next = i;
                    jobs[i].excellent = (double) jobs[i].wait_time / (double) jobs[i].need_time;
                    max_privilege = jobs[i].excellent;
                }
            }
        }
    }

    return next;
}

// 高响应比调度算法
void HRRFschdulejob() {
    int i, j;
    for (i = 0; i < quantity - 1; i++) {// sort reach_time
        for (j = 0; j < quantity - 1 - i; j++) {
            if (jobs[j].reach_time > jobs[j + 1].reach_time) {
                job temp = jobs[j];
                jobs[j] = jobs[j + 1];
                jobs[j + 1] = temp;
            }
        }
    }
    int current_time = 0;
    int total_waitime = 0;
    int total_roundtime = 0;
    int loc = updatePrivilege(jobs, jobs[0].reach_time);
    printf("\n\nHRRF算法作业流\n");
    printf("------------------------------------------------------------------------\n");
    printf("\tjobID\treachtime\tstarttime\twaittime\troundtime\n");
    for (i = 0; i < quantity; i++) {
        if (jobs[loc].reach_time > current_time) {
            jobs[loc].start_time = jobs[loc].reach_time;
            jobs[loc].wait_time = 0;
            current_time = jobs[loc].start_time + jobs[loc].need_time;
        } else {
            jobs[loc].start_time = current_time;
            jobs[loc].wait_time = current_time - jobs[loc].reach_time;
            current_time += jobs[loc].need_time;
        }
        printf("\t%-8d\t%-8d\t%-8d\t%-8d\t%-8d\n", jobs[loc].number, jobs[loc].reach_time, jobs[loc].start_time,
               jobs[loc].wait_time,
               jobs[loc].wait_time + jobs[loc].need_time);
        total_waitime += jobs[loc].wait_time;
        total_roundtime += jobs[loc].wait_time + jobs[loc].need_time;
        jobs[loc].visited = 1;
        if (i != quantity - 1) {
            loc = updatePrivilege(jobs, current_time);
        }
    }
    printf("总等待时间:%-8d 总周转时间:%-8d\n", total_waitime, total_roundtime);
    printf("平均等待时间: %4.2f 平均周转时间: %4.2f\n", (float) total_waitime / (quantity),
           (float) total_roundtime / (quantity));
}

// 优先权高者优先调度算法
void HPF(job jobs[]) {
    int i, j;
    for (i = 0; i < quantity - 1; i++) {
        for (j = 0; j < quantity - 1 - i; j++) {
            if (jobs[j].reach_time >= jobs[j + 1].reach_time) {
                job temp = jobs[j];
                jobs[j] = jobs[j + 1];
                jobs[j + 1] = temp;
            }
        }
    }
    for (i = 0; i < quantity - 1; i++) {
        for (j = 0; j < quantity - 1 - i; j++) {
            if (jobs[j].reach_time == jobs[j + 1].reach_time && jobs[j].privilege <= jobs[j + 1].privilege) {
                job temp = jobs[j];
                jobs[j] = jobs[j + 1];
                jobs[j + 1] = temp;
            }
        }
    }
    int current_time = 0;
    int total_waitime = 0;
    int total_roundtime = 0;
    int loc = 0;
    printf("\n\nHRF算法作业流\n");
    printf("------------------------------------------------------------------------\n");
    printf("\tjobID\treachtime\tstarttime\twaittime\troundtime\n");
    for (i = 0; i < quantity; i++) {
        if (jobs[loc].reach_time > current_time) {
            jobs[loc].start_time = jobs[loc].reach_time;
            current_time = jobs[loc].start_time + jobs[loc].need_time;
        } else {
            jobs[loc].start_time = current_time;
            current_time += jobs[loc].need_time;
        }
        jobs[loc].wait_time = jobs[loc].start_time - jobs[loc].reach_time;
        printf("\t%-8d\t%-8d\t%-8d\t%-8d\t%-8d\n", jobs[loc].number, jobs[loc].reach_time, jobs[loc].start_time,
               jobs[loc].wait_time,
               jobs[loc].wait_time + jobs[loc].need_time);
        total_waitime += jobs[loc].wait_time;
        total_roundtime += jobs[loc].wait_time + jobs[loc].need_time;
        jobs[loc].visited = 1;
        int next = -1;
        int max_privilege = -1;
        for (j = 0; j < quantity && current_time >= jobs[j].reach_time; j++) {
            if (jobs[j].visited != 1 && jobs[j].privilege > max_privilege) {
                max_privilege = jobs[j].privilege;
                next = j;
            }
        }
        if (next == -1) {
            next = loc + 1;
        }
        loc = next;
    }
    printf("总等待时间:%-8d 总周转时间:%-8d\n", total_waitime, total_roundtime);
    printf("平均等待时间: %4.2f 平均周转时间: %4.2f\n", (float) total_waitime / (quantity),
           (float) total_roundtime / (quantity));
}

int main() {
    initial_jobs();
    readJobdata();
    FCFS();
    initial_jobs();
    readJobdata();
    SFJschdulejob(jobs, quantity);
    initial_jobs();
    readJobdata();
    HRRFschdulejob();
    initial_jobs();
    readJobdata();
    HPF(jobs);
    system("pause");
    return 0;
}

同目录下创建job.txt，用于储存作业数据，内容如下：

1 800 50 0
2 815 30 1
3 830 25 2
4 835 20 2
5 845 15 2
6 700 10 1
7 820 05 0

四、实验总结

请总结一下本次实验的收获、教训和感受，结合课本内容谈一下你对操作系统中各种作业调度算法优缺点的理解。

• FCFS 算法（先来先服务）：
  按照作业提交的先后顺序进行调度，是一种非抢占式调度算法。优点是公平，算法实现简单；缺点是排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即FCFS算法对长作业有利，对短作业不利。

• SJF 算法（最短作业优先）：
  按照作业的执行时间进行调度，是一种非抢占式调度算法。优点是平均等待时间最小，缺点是可能会导致长作业无限等待。

• HRRF 算法（最高响应比优先）：
  按照响应比进行调度，响应比=（等待时间+服务时间）/服务时间。优点是可以避免长作业无限等待，缺点是可能会导致短作业无限等待。

• HPF 算法（高优先级优先）：
  按照进程的优先级进行调度，是一种抢占式调度算法。优点是可以保证高优先级进程的执行，缺点是可能会导致低优先级进程无限等待。

事实上，并不存在最完美的算法，只存在最合适的算法，当一些进程中只有一个长进程且优先级很高，此刻的短进程优先算法便显得不太合理，但是同样 SJF 的算法却在照顾短进程方面有着优点，所以算法的使用终归要根据进程运行的需求来做。