1. 实验目的

1. 掌握周转时间、等待时间、平均周转时间等概念及其计算方法。
2. 理解五种常用的进程调度算法（FCFS、SJF、HRRF、HPF、RR），区分算法之间的差异性，并用 C 语言模拟实现各算法。
3. 了解操作系统中高级调度、中级调度和低级调度的区别和联系。

2. 实验内容

2.1 实验说明

1. 基本概念

• 程序：
  程序是指静态的指令集合，它不占用系统的运行资源，可以长久地保存在磁盘中。

• 进程：
  进程是指进程实体（由程序、数据和进程控制块构成）的运行过程，是系统进行资源分配和调度的一个独立单位。进程执行程序，但进程与程序之间不是一一对应的。通过多次运行，一个程序可以包含多个进程；通过调用关系，同一进程可以被多个程序包含（如一个 DLL 文件可以被多个程序运用）。

• 作业：
  作业由一组统一管理和操作的进程集合构成，是用户要求计算机系统完成的一项相对独立的工作。作业可以是完成了编译、链接之后的一个用户程序，也可以是各种命令构成的一个脚本。

• 作业调度：
  作业调度是在资源满足的条件下，将处于后备状态的作业调入内存，同时生成与作业相对应的进程，并为这些进程提供所需要的资源。作业调度适用于多道批处理系统中的批处理作业。根据作业控制块中的信息，检查系统是否满足作业的资源要求，只有在满足作业调度的资源需求的情况下，系统才能进行作业调度。

2. 基本调度算法

• 先来先服务（First-Come First-Served，FCFS）调度算法
  先来先服务调度算法遵循按照进入后备队列的顺序进行调度的原则。该算法是一种非抢占式的算法，是到目前为止最简单的调度算法，其编码实现非常容易。该算法仅考虑了作业到达的先后顺序，而没有考虑作业的执行时间长短、作业的运行特性和作业对资源的要求。

• 短作业优先（Shortest-Job-First，SJF）调度算法
  短作业优先调度算法根据作业控制块中指出的执行时间，选取执行时间最短的作业优先调度。本实验中规定，该算法是非抢占式的，即不允许立即抢占正在执行中的长进程，而是等当前作业执行完毕再进行调度。

• 响应比高者优先（HRRF）调度算法
  FCFS 调度算法只片面地考虑了作业的进入时间，短作业优先调度算法考虑了作业的运行时间而忽略了作业的等待时间。响应比高者优先调度算法为这两种算法的折中。响应比为作业的响应时间与作业需要执行的时间之比。作业的响应时间为作业进入系统后的等待时间与作业要求处理器处理的时间之和。

• 优先权高者优先（Highest-Priority-First，HPF）调度算法
  优先权高者优先调度算法与响应比高者优先调度算法十分相似，根据作业的优先权进行作业调度，每次总是选取优先权高的作业优先调度。作业的优先权通常用一个整数表示，也叫优先数。优先数的大小与优先权的关系由系统或者用户规定。优先权高者优先调度算法综合考虑了作业执行时间和等待时间的长短、作业的缓急度，作业对外部设备的使用情况等因素，根据系统设计目标和运行环境而给定各个作业的优先权，决定作业调度的先后顺序。

2.2 程序清单

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

作业 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 job_s {
    bool done;        // 是否已经调度完成
    int  number;      // 作业号
    int  need_time;   // 需要的服务时间
    int  reach_time;  // 到达时刻
    int  start_time;  // 开始运行时刻
    int  wait_time;   // 等待时间 = 开始运行时刻 - 到达时刻
    int  turn_time;   // 周转时间 = 等待时间 + 服务时间
    int  privilege;   // 优先权, 数值越大优先级越高
} job_t;

实验代码：

▶

Code

/*
 * 作业调度模拟程序
 *
 * 从数据文件读入一批作业, 分别用四种非抢占式调度算法模拟调度:
 *   FCFS  先来先服务    : 在已到达的作业中按到达先后选择
 *   SJF   短作业优先    : 在已到达的作业中选择服务时间最短者
 *   HRRF  高响应比优先  : 在已到达的作业中选择响应比最高者
 *   HPF   高优先权优先  : 在已到达的作业中选择优先权最高者
 *
 * 数据文件每行描述一个作业: 作业号 到达时间 服务时间 优先权.
 * 数据只读取一次, 各算法在作业表的副本上运行, 互不影响.
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_JOB_NUM 50  // 作业序列的最大长度
#define INVALID -1      // 没有找到可运行作业时的返回值

/* 单个作业信息 */
typedef struct job_s {
    bool done;        // 是否已经调度完成
    int  number;      // 作业号
    int  need_time;   // 需要的服务时间
    int  reach_time;  // 到达时刻
    int  start_time;  // 开始运行时刻
    int  wait_time;   // 等待时间 = 开始运行时刻 - 到达时刻
    int  turn_time;   // 周转时间 = 等待时间 + 服务时间
    int  privilege;   // 优先权, 数值越大优先级越高
} job_t;

// 就绪作业的选择策略: 返回当前时刻应运行的作业下标;
// 若此刻没有"已到达且未完成"的作业, 返回 INVALID, 由调度框架推进时间
typedef int (*pick_policy)(const job_t jobs[], int count, int current_time);

// 从文件读入的作业表, 作为只读基准数据
job_t g_jobs[MAX_JOB_NUM];
int   g_job_count = 0;

/**
 * @brief 打印读入的原始作业数据
 *
 */
static void print_input_data()
{
    printf("原始作业数据\r\n");
    printf("---------------------------------------------------------------------\r\n");
    printf("\tjobID\treachtime\tneedtime\tprivilege\r\n");
    for (int i = 0; i < g_job_count; i++) {
        printf("\t%-8d\t%-8d\t%-8d\t%-8d\r\n", g_jobs[i].number, g_jobs[i].reach_time, g_jobs[i].need_time,
               g_jobs[i].privilege);
    }
}

/**
 * @brief 打印算法名称与作业流表头
 *
 * @param algo_name 算法名
 */
static void print_header(const char *algo_name)
{
    printf("\r\n%s 算法作业流\r\n", algo_name);
    printf("---------------------------------------------------------------------\r\n");
    printf("\tjobID\treachtime\tstarttime\twaittime\troundtime\r\n");
}

/**
 * @brief 打印单个作业的调度结果
 *
 * @param job 作业信息指针
 */
static void print_job_row(const job_t *job)
{
    printf("\t%-8d\t%-8d\t%-8d\t%-8d\t%-8d\n", job->number, job->reach_time, job->start_time, job->wait_time,
           job->turn_time);
}

/**
 * @brief 打印一次调度过程的统计结果
 *
 * @param count 作业数量
 * @param total_wait 总等待时间
 * @param total_turn 总轮转时间
 */
static void print_summary(int count, int total_wait, int total_turn)
{
    printf("总等待时间:%-8d 总周转时间:%-8d\r\n", total_wait, total_turn);
    printf("平均等待时间: %4.2f 平均周转时间: %4.2f\n\n", (float)total_wait / count, (float)total_turn / count);
}

/**
 * @brief 从文件读入全部作业
 *
 * @return true  读取成功
 * @return false 读取失败
 */
static bool read_job_data()
{
    char fname[128];
    int  number, reach, need, privilege;
    printf("请输入作业数据文件名: ");
    scanf("%s", fname);

    FILE *fp = fopen(fname, "r");
    if (fp == NULL) {
        printf("打开文件 %s 失败\r\n", fname);
        return false;
    }

    // 逐行读取直到文件结束或达到上限, 正确读取最后一个作业
    g_job_count = 0;
    while (g_job_count < MAX_JOB_NUM && fscanf(fp, "%d %d %d %d", &number, &reach, &need, &privilege) == 4) {
        g_jobs[g_job_count].number     = number;
        g_jobs[g_job_count].reach_time = reach;
        g_jobs[g_job_count].need_time  = need;
        g_jobs[g_job_count].privilege  = privilege;
        g_job_count++;
    }
    fclose(fp);

    if (g_job_count == 0) {
        printf("文件中没有有效的作业数据\r\n");
        return false;
    }
    return true;
}

/**
 * @brief FCFS 算法: 在已到达的作业中选择最早到达的一个
 *
 * @param jobs         作业列表
 * @param count        作业数量
 * @param current_time 当前时间
 * @return int 执行作业 ID
 */
static int pick_fcfs(const job_t jobs[], int count, int current_time)
{
    int best = INVALID;
    for (int i = 0; i < count; i++) {
        if (jobs[i].done || jobs[i].reach_time > current_time) {
            continue;
        }
        if (best == INVALID || jobs[i].reach_time < jobs[best].reach_time) {
            best = i;
        }
    }
    return best;
}

/**
 * @brief SJF 算法: 在已到达的作业中选择服务时间最短的一个
 *
 * @param jobs         作业列表
 * @param count        作业数量
 * @param current_time 当前时间
 * @return int 执行作业 ID
 */
static int pick_sjf(const job_t jobs[], int count, int current_time)
{
    int best = INVALID;
    for (int i = 0; i < count; i++) {
        if (jobs[i].done || jobs[i].reach_time > current_time) {
            continue;
        }
        if (best == INVALID || jobs[i].need_time < jobs[best].need_time) {
            best = i;
        }
    }
    return best;
}

/**
 * @brief HRRF 算法: 在已到达的作业中选择响应比最高的一个
 * 响应比 = 1 + 等待时间 / 服务时间, 只需比较 等待时间 / 服务时间
 *
 * @param jobs         作业列表
 * @param count        作业数量
 * @param current_time 当前时间
 * @return int 执行作业 ID
 */
static int pick_hrrf(const job_t jobs[], int count, int current_time)
{
    int   best       = INVALID;
    float best_ratio = -1.0f;
    for (int i = 0; i < count; i++) {
        if (jobs[i].done || jobs[i].reach_time > current_time) {
            continue;
        }
        float ratio = (float)(current_time - jobs[i].reach_time) / jobs[i].need_time;
        if (best == INVALID || ratio > best_ratio) {
            best       = i;
            best_ratio = ratio;
        }
    }
    return best;
}

/**
 * @brief HPF 算法: 在已到达的作业中选择优先权最高的一个
 *
 * @param jobs         作业列表
 * @param count        作业数量
 * @param current_time 当前时间
 * @return int 执行作业 ID
 */
static int pick_hpf(const job_t jobs[], int count, int current_time)
{
    int best = INVALID;
    for (int i = 0; i < count; i++) {
        if (jobs[i].done || jobs[i].reach_time > current_time) {
            continue;
        }
        if (best == INVALID || jobs[i].privilege > jobs[best].privilege) {
            best = i;
        }
    }
    return best;
}

/**
 * @brief 在所有未完成作业中寻找最早到达的一个, 用于 CPU 空闲时推进时间
 *
 * @param jobs  作业列表
 * @param count 作业数量
 * @return int 执行作业 ID
 */
static int pick_earliest_arrival(const job_t jobs[], int count)
{
    int best = INVALID;
    for (int i = 0; i < count; i++) {
        if (jobs[i].done) {
            continue;
        }
        if (best == INVALID || jobs[i].reach_time < jobs[best].reach_time) {
            best = i;
        }
    }
    return best;
}

/**
 * @brief 依据给定的选择策略逐个运行作业:
 * 选作业 -> 无作业可运行则推进时间 -> 运行 -> 推进时间 -> 统计
 *
 * @param master    作业列表
 * @param count     作业数量
 * @param algo_name 算法名称
 * @param pick      算法函数
 */
static void run_scheduler(const job_t master[], int count, const char *algo_name, pick_policy pick)
{
    // 在基准数据的副本上调度, 不破坏原始数据
    job_t work[MAX_JOB_NUM];
    for (int i = 0; i < count; i++) {
        work[i] = master[i];
    }

    int current    = 0;  // 当前时刻
    int scheduled  = 0;  // 已调度完成的作业数
    int total_wait = 0;  // 总等待时间
    int total_turn = 0;  // 总周转时间

    print_header(algo_name);
    while (scheduled < count) {
        int loc = pick(work, count, current);

        // 当前没有已到达的作业, CPU 空闲, 推进到下一个作业的到达时刻后重新选择
        if (loc == INVALID) {
            current = work[pick_earliest_arrival(work, count)].reach_time;
            loc     = pick(work, count, current);
        }

        // 运行选中的作业
        work[loc].start_time = current;
        work[loc].wait_time  = current - work[loc].reach_time;
        work[loc].turn_time  = work[loc].wait_time + work[loc].need_time;
        print_job_row(&work[loc]);

        total_wait += work[loc].wait_time;
        total_turn += work[loc].turn_time;
        current += work[loc].need_time;
        work[loc].done = true;
        scheduled++;
    }
    print_summary(count, total_wait, total_turn);
}

int main()
{
    // 读取一次作业数据, 供所有算法使用
    if (!read_job_data()) {
        return EXIT_FAILURE;
    }
    print_input_data();

    // 依次运行四种调度算法
    run_scheduler(g_jobs, g_job_count, "FCFS", pick_fcfs);
    run_scheduler(g_jobs, g_job_count, "SJF", pick_sjf);
    run_scheduler(g_jobs, g_job_count, "HRRF", pick_hrrf);
    run_scheduler(g_jobs, g_job_count, "HPF", pick_hpf);
    return EXIT_SUCCESS;
}

同目录下创建 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 5 0

3. 分析与思考

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

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

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

• HRRF 算法（最高响应比优先）：
  按照响应比进行调度，响应比=（等待时间+服务时间）/服务时间。优点是对 FCFS 和 SJF 进行了折中，既照顾了短作业，又不会使长作业无限等待；缺点是每次调度都需要重新计算各作业的响应比，增加了系统开销。

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

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