进程调度模拟实验报告

一、实验目的

本实验旨在通过模拟实现多种进程调度算法，掌握进程调度的基本概念和操作方法，加深对操作系统的理解。

二、实验内容

1. 实现进程调度程序，并模拟 FCFS、SJF、RR、优先级调度等算法；
2. 分别用不同的实际应用场景，比如 CPU 密集型和 I/O 密集型任务，测试不同调度算法的效率和公平性；
3. 统计每种算法的平均等待时间、平均周转时间和平均响应时间，比较它们的优缺点。

三、实验步骤

1. 设计进程控制块 PCB 的数据结构，包括进程标识符 PID、进程状态 status、进程优先级 priority、进程所需 CPU 时间 need_time、进程已占用 CPU 时间 used_time、进程到达时间 arrival_time、进程等待时间 wait_time、进程周转时间 turnover_time、进程响应时间 response_time 等字段。
2. 实现进程调度程序，包括 FCFS、SJF、RR、优先级调度等算法。其中，FCFS 算法按照进程到达时间的先后顺序依次执行，SJF 算法按照进程所需 CPU 时间的短长顺序执行，RR 算法按照时间片大小分配 CPU 时间，并循环执行所有进程，优先级调度算法按照进程优先级的高低顺序执行。
3. 编写测试程序，模拟不同的实际应用场景，比如 CPU 密集型和 I/O 密集型任务。对于 CPU 密集型任务，需要让进程的 need_time 大于 arrival_time，以便测试 SJF 和优先级调度算法的效果；对于 I/O 密集型任务，需要设置进程的 I/O 操作，以便测试 RR 算法的效果。
4. 运行测试程序，记录每个进程的到达时间、需要 CPU 时间、优先级等信息，并根据不同的调度算法进行模拟，计算出每个进程的等待时间、周转时间和响应时间。
5. 对不同的调度算法进行比较，分析其优缺点，并统计平均等待时间、平均周转时间和平均响应时间。

四、实验结果

1. 设计进程控制块 PCB 的数据结构如下：

typedef struct PCB {
    int pid;                // 进程标识符
    int status;             // 进程状态
    int priority;           // 进程优先级
    int need_time;          // 进程所需 CPU 时间
    int used_time;          // 进程已占用 CPU 时间
    int arrival_time;       // 进程到达时间
    int wait_time;          // 进程等待时间
    int turnover_time;      // 进程周转时间
    int response_time;      // 进程响应时间
    struct PCB *next;       // 链表指针
} PCB;

2. 实现进程调度程序，包括 FCFS、SJF、RR、优先级调度等算法。具体代码如下：

// FCFS 调度算法
void fcfs(PCB *head) {
    PCB *p = head->next;
    int time = p->arrival_time;  // 当前时间
    while (p != NULL) {
        // 计算等待时间、周转时间和响应时间
        p->wait_time = time - p->arrival_time;
        p->turnover_time = p->wait_time + p->need_time;
        p->response_time = p->wait_time;
        // 更新当前时间
        time += p->need_time;
        // 处理下一个进程
        p = p->next;
    }
}

// SJF 调度算法
void sjf(PCB *head) {
    PCB *p = head->next;
    int time = p->arrival_time;  // 当前时间
    while (p != NULL) {
        // 查找需要执行的进程
        PCB *q = p->next;
        while (q != NULL) {
            if (q->arrival_time > time) {
                break;
            }
            if (q->need_time < p->need_time) {
                PCB tmp = *p;
                *p = *q;
                *q = tmp;
            }
            q = q->next;
        }
        // 计算等待时间、周转时间和响应时间
        p->wait_time = time - p->arrival_time;
        p->turnover_time = p->wait_time + p->need_time;
        p->response_time = p->wait_time;
        // 更新当前时间
        time += p->need_time;
        // 处理下一个进程
        p = p->next;
    }
}

// RR 调度算法
void rr(PCB *head, int quantum) {
    PCB *p = head->next;
    int time = p->arrival_time;  // 当前时间
    while (p != NULL) {
        // 计算等待时间、周转时间和响应时间
        p->wait_time = time - p->arrival_time;
        p->response_time = p->wait_time;
        // 分配时间片
        int remain_time = p->need_time;
        while (remain_time > 0) {
            if (remain_time <= quantum) {
                // 进程执行完毕
                time += remain_time;
                p->used_time += remain_time;
                remain_time = 0;
            } else {
                // 时间片用完了
                time += quantum;
                p->used_time += quantum;
                remain_time -= quantum;
                // 将进程移到队列尾部
                PCB *q = p->next;
                while (q != NULL) {
                    if (q->arrival_time > time) {
                        break;
                    }
                    q = q->next;
                }
                PCB tmp = *p;
                tmp.next = q;
                *p = *p->next;
                p->next = tmp.next;
            }
        }
        // 计算周转时间
        p->turnover_time = p->wait_time + p->used_time;
        // 处理下一个进程
        p = p->next;
    }
}

// 优先级调度算法
void priority(PCB *head) {
    PCB *p = head->next;
    int time = p->arrival_time;  // 当前时间
    while (p != NULL) {
        // 查找需要执行的进程
        PCB *q = p->next;
        while (q != NULL) {
            if (q->arrival_time > time) {
                break;
            }
            if (q->priority < p->priority) {
                PCB tmp = *p;
                *p = *q;
                *q = tmp;
            }
            q = q->next;
        }
        // 计算等待时间、周转时间和响应时间
        p->wait_time = time - p->arrival_time;
        p->turnover_time = p->wait_time + p->need_time;
        p->response_time = p->wait_time;
        // 更新当前时间
        time += p->need_time;
        // 处理下一个进程
        p = p->next;
    }
}

3. 编写测试程序，模拟不同的实际应用场景。对于 CPU 密集型任务，设置进程的 need_time 大于 arrival_time；对于 I/O 密集型任务，设置进程的 I/O 操作。具体代码如下：

// 生成测试数据
void gen_data(PCB *head, int type) {
    srand(time(NULL));
    int pid = 1;
    PCB *p = head;
    while (p->next != NULL) {
        p = p->next;
    }
    for (int i = 0; i < MAX_NUM; i++) {
        pid++;
        PCB *q = (PCB*)malloc(sizeof(PCB));
        q->pid = pid;
        q->status = READY;
        q->priority = rand() % 5 + 1;
        q->need_time = rand() % 10 + 1;
        if (type == CPU_INTENSIVE) {
            q->arrival_time = rand() % MAX_NUM;
            while (q->need_time <= q->arrival_time) {
                q->need_time = rand() % 10 + 1;
            }
        } else if (type == IO_INTENSIVE) {
            q->arrival_time = rand() % MAX_NUM;
            q->need_time = rand() % 5 + 1;
            if (rand() % 2 == 0) {
                q->io_time = rand() % q->need_time + 1;
            } else {
                q->io_time = 0;
            }
        }
        q->used_time = 0;
        q->wait_time = 0;
        q->turnover_time = 0;
        q->response_time = 0;
        q->next = NULL;
        p->next = q;
        p = p->next;
    }
}

// 显示测试数据
void show_data(PCB *head) {
    PCB *p = head->next;
    printf("PID\tStatus\tPriority\tNeed Time\tArrival Time\tIO Time\n");
    while (p != NULL) {
        printf("%d\t%d\t%d\t\t%d\t\t%d\t\t%d\n", p->pid, p->status, p->priority, p->need_time, p->arrival_time, p->io_time);
        p = p->next;
    }
}

// 模拟 I/O 操作
int do_io(PCB *head, PCB *p) {
    if (p->io_time > 0) {
        p->io_time--;
        if (p->io_time == 0) {
            // I/O 完成，将进程移到队列尾部
            PCB *q = p->next;
            while (q != NULL) {
                if (q->arrival_time > p->arrival_time) {
                    break;
                }
                q = q->next;
            }
            PCB tmp = *p;
            tmp.next = q;
            *p = *p->next;
            p->next = tmp.next;
            return 1;
        }
    }
    return 0;
}

// 测试 FCFS 调度算法
void test_fcfs(PCB *head) {
    printf("FCFS 调度算法：\n");
    fcfs(head);
    show_result(head);
}

// 测试 SJF 调度算法
void test_sjf(PCB *head) {
    printf("SJF 调度算法：\n");
    sjf(head);
    show_result(head);
}

// 测试 RR 调度算法
void test_rr(PCB *head, int quantum) {
    printf("RR 调度算法（quantum=%d）：\n", quantum);
    PCB *p = head->next;
    int time = p->arrival_time;  // 当前时间
    while (p != NULL) {
        // 计算等待时间、响应时间和周转时间
        p->wait_time = time - p->arrival_time;
        p->response_time = p->wait_time;
        // 分配时间片
        int remain_time = p->need_time;
        while (remain_time > 0) {
            if (remain_time <= quantum) {
                // 进程执行完毕
                time += remain_time;
                p->used_time += remain_time;
                remain_time = 0;
            } else {
                // 时间片用完了，进行 I/O 操作
                time += quantum;
                p->used_time += quantum;
                remain_time -= quantum;
                if (do_io(head, p)) {
                    break;
                }
            }
        }
        // 计算周转时间
        p->turnover_time = p->wait_time + p->used_time;
        // 处理下一个进程
        p = p->next;
    }
    show_result(head);
}

// 测试优先级调度算法
void test_priority(PCB *head) {
    printf("优先级调度算法：\n");
    priority(head);
    show_result(head);
}

// 显示测试结果
void show_result(PCB *head) {
    PCB *p = head->next;
    double total_wait_time = 0, total_turnover_time = 0, total_response_time = 0;
    printf("PID\tStatus\tPriority\tNeed Time\tArrival Time\tIO Time\tWait Time\tTurnover Time\tResponse Time\n");
    while (p != NULL) {
        printf("%d\t%d\t%d\t\t%d\t\t%d\t\t%d\t\t%d\t\t%d\t\t%d\n", p->pid, p->status, p->priority, p->need_time, p->arrival_time, p->io_time, p->wait_time, p->turnover_time, p->response_time);
        total_wait_time += p->wait_time;
        total_turnover_time += p->turnover_time;
        total_response_time += p->response_time;
        p = p->next;
    }
    double avg_wait_time = total_wait_time / MAX_NUM;
    double avg_turnover_time = total_turnover_time / MAX_NUM;
    double avg_response_time = total_response_time / MAX_NUM;
    printf("平均等待时间：%lf，平均周转时间：%lf，平均响应时间：%lf\n", avg_wait_time, avg_turnover_time, avg_response_time);
}

4. 运行测试程序，记录每个进程的到达时间、需要 CPU 时间、优先级等信息，并根据不同的调度算法进行模拟，计算出每个进程的等待时间、周转时间和响应时间。具体代码如下：

int main() {
    // 初始化进程链表
    PCB *head = (PCB*)malloc(sizeof(PCB));
    head->next = NULL;
    // 生成测试数据
    gen_data(head, CPU_INTENSIVE);
    // 显示测试数据
    show_data(head);
    // 测试 FCFS 调度算法
    test_fcfs(head);
    // 测试 SJF 调度算法
    test_sjf(head);
    // 测试 RR 调度算法
    test_rr(head, 2);
    // 测试优先级调度算法
    test_priority(head);
    // 释放内存
    PCB *p = head;
    while (p != NULL) {
        PCB *q = p->next;
        free(p);
        p = q;
    }
    return 0;
}

五、实验分析

本实验模拟了 FCFS、SJF、RR、优先级调度等四种进程调度算法，并通过测试程序模拟了不同的实际应用场景，比如 CPU 密集型和 I/O 密集型任务。根据测试结果，可以分析出每种算法的优缺点。

1. FCFS 调度算法

FCFS 调度算法按照进程到达时间的先后顺序依次执行，适用于 CPU 密集型任务。优点是实现简单，没有额外的开销，但缺点是可能导致长作业等待时间过长，无法满足实时性要求。

2. SJF 调度算法

SJF 调度算法按照进程所需 CPU 时间的短长顺序执行，适用于 CPU 密集型任务。优点是平均等待时间最短，但缺点是难以预测每个进程的需要时间，可能导致长作业饥饿。

3. RR 调度算法

RR 调度算法按照时间片大小分配 CPU 时间，并循环执行所有进程，适用于 CPU 密集型和 I/O 密集型任务。优点是公平性好，长作业不会饥饿，但缺点是时间片过小会增加上下文切换的开销，时间片过大会使得响应时间变长。

4. 优先级调度算法

优先级调度算法按照进程优先级的高低顺序执行，适用于 I/O 密集型任务。优点是可以满足实时性要求，但缺点是可能导致低优先级进程饥饿，需要设置合理的优先级和调整策略。

六、实验总结

本实验通过模拟实现多种进程调度算法，深入理解了操作系统的基本概念和操作方法，加深了对操作系统的理解。实验中还通过测试程序模拟了不同的实际应用场景，比较