【处理器调度—时间片轮转算法和优先级调度算法】

一、实验目的

1.深刻理解处理器调度算法；理解可剥夺和不可剥夺算法的区别；
2.掌握时间片轮转算法和优先级调度算法，并能在可调度情况下给出具体调度结果。

二、实验内容与设计思想

实验内容

1.设计进程控制块PCB的结构，通常应包括如下信息：进程名、进程优先数（或轮转时间片数值）、进程已占用的CPU时间、进程到完成还需要的时间、进程的状态、当前队列指针等；
2.编写两种调度算法程序；
3.按算法确定的调度次序安排各个线程运行，运行时在终端上画出其Gantt图；撰写实验报告,给出实验小结，问题分析。

设计思路

实验定义的 PCB 结构体包含以下关键信息：

typedef struct PCB {char process_name[10];     // 进程名int priority;             // 优先级（数值越小优先级越高）int cpu_time_used;        // 已占用CPU时间（时间片轮转用）int remaining_time;       // 剩余执行时间bool is_completed;        // 完成状态
} PCB;

时间片轮转：通过remaining_time与时间片quantum的比较，判断进程是否需要抢占。
优先级调度：依赖priority字段确定执行顺序，优先级高的进程优先执行。

三、实验代码实现

1. 时间片轮转算法

时间片轮转是一种常用的可剥夺调度算法，特别适用于多任务操作系统。每个进程被分配固定的时间片（时间段），在时间片结束时，进程被挂起并轮到下一个进程执行。
基本步骤：
轮流安排进程执行。每个进程分配固定的时间片。如果进程在其时间片结束前完成，则释放CPU。如果未完成，则被挂起并重新排队。
代码：

#include <stdio.h>
#include <stdbool.h>typedef struct PCB {char process_name[10];int priority;int cpu_time_used;int remaining_time;bool is_completed;
} PCB;// 函数用于找到下一个要执行的进程
int find_next_process(PCB processes[], int n, int current_index, int quantum) {for (int i = 0; i < n; i++) {int index = (current_index + i) % n;if (!processes[index].is_completed && processes[index].remaining_time > 0) {return index;}}return -1;
}void print_gantt_chart(PCB processes[], int n, int quantum) {int time = 0;int current_index = 0;while (true) {int next_index = find_next_process(processes, n, current_index, quantum);if (next_index == -1) break; // 所有进程都已完成while (processes[next_index].remaining_time > 0) {if (processes[next_index].remaining_time > quantum) {printf("%d-%d: %s \t", time, time + quantum, processes[next_index].process_name);time += quantum;processes[next_index].remaining_time -= quantum;} else {printf("%d-%d: %s \t", time, time + processes[next_index].remaining_time, processes[next_index].process_name);time += processes[next_index].remaining_time;processes[next_index].remaining_time = 0;processes[next_index].is_completed = true;}}current_index = (next_index + 1) % n; // 移动到下一个进程}
}int main() {PCB processes[] = {{"P1", 1, 0, 5, false},{"P2", 1, 0, 3, false},{"P3", 1, 0, 2, false}};int n = sizeof(processes) / sizeof(processes[0]);int quantum = 2;printf("Round Robin Scheduling:\n");print_gantt_chart(processes, n, quantum);return 0;
}

结果：

2. 优先级调度算法
   优先级调度算法根据进程的优先级来安排执行顺序。每个进程都有一个优先级值，调度器始终选择优先级最高的进程执行。
   基本步骤：分配优先级给每个进程。每次调度时选择优先级最高的进程执行。可剥夺型的实现需要在当前执行进程的优先级低于新的就绪队列中的进程时进行抢占。
   代码：

#include <stdio.h>
#include <stdbool.h>typedef struct PCB {char process_name[10];int priority;int cpu_time_used;int remaining_time;bool is_completed;
} PCB;void print_gantt_chart(PCB processes[], int n) {int time = 0;while (true) {bool all_completed = true;for (int i = 0; i < n; i++) {if (!processes[i].is_completed && processes[i].remaining_time > 0) {all_completed = false;printf("%d-%d: %s \t", time, time + processes[i].remaining_time, processes[i].process_name);time += processes[i].remaining_time;processes[i].remaining_time = 0;processes[i].is_completed = true;}}if (all_completed) break;}
}int main() {PCB processes[] = {{"P1", 2, 0, 5, false},{"P2", 1, 0, 3, false},{"P3", 3, 0, 2, false}};int n = sizeof(processes) / sizeof(processes[0]);printf("Priority Scheduling:\n");print_gantt_chart(processes, n);return 0;
}

结果

四、总结

• 遇到的问题

1.文件权限问题：只读文件的困境

问题描述：在自建用户hyy202221336007下编辑代码时，vi提示 “只读文件”，无法保存。
排查过程：
使用ls -l检查文件权限，发现目录属于 root 用户，当前用户无写入权限。

尝试用sudo chmod修改权限失败（无 root 密码），最终通过cd ~在用户主目录新建文件夹，在专属目录下编写代码，避免权限冲突。
经验总结：Linux 文件权限遵循 “用户 - 组 - 其他” 三级模型，新建文件应确保在当前用户可读写的目录下，或通过mkdir创建专属工作空间。
2. 代码结构混乱：模块化拆分的必要性
初始问题：最开始我将时间片轮转算法以及优先调度算法写在一块，报错非常多。为了让代码更加简洁好修改，同时将复杂的代码简化，我重新建了两个文件分别进行时间片轮转算法以及优先调度算法，在运行过程中成功没有报错。

解决方法：
将两种算法拆分为独立文件（如round_robin.c和priority_sched.c），分别定义 PCB 结构体和调度逻辑。
提取公共函数（如 Gantt 图打印），避免代码冗余。
核心思考：复杂功能应遵循 “单一职责原则”，模块化设计不仅便于调试，更利于后续扩展（如添加可剥夺优先级调度）。

• 感悟

本次实验让我意识到，课本中的调度算法在实际操作系统（如 Linux 的 CFS 调度器）中会结合更多因素（如进程活跃度、IO 等待），但核心思想始终是资源利用率与公平性的平衡。未来计划深入研究 Linux 内核源码，观察时间片轮转与优先级调度的工程实现，理解理论与实践的差异与融合。
操作系统实验不仅是代码的编写，更是对计算机系统底层逻辑的逆向思考。当 Gantt 图按预期输出时，我真正感受到调度算法如何将 CPU 资源 “切割” 并分配给多个进程，这是理论落地的奇妙瞬间，也是继续探索系统内核的动力起点。