实验三 进程调度算法模拟实验

Linux

一、 实验目的

通过模拟单处理器进程调度算法，加深对进程调度的概念理解。

二、实验内容

设计一个按时间片轮转法实现进程调度的模拟程序。

三、实验要求

1.假设系统有10个进程，每个进程用一个进程控制块（PCB）来代表。进程控制块的格式如图1所示。

图中的参数意义如下：

进程名：即进程标识。
链接指针：按照进程到达系统的时间将处于就绪状态的进程连接成一个就绪队列。指针指出下一个到达的进程控制块地址。最后一个进程的链接指针为NULL。
到达时间：进程创建时的系统时间或由用户指定，调度时，总是选择到达时间最早的进程。
估计运行时间：可由设计者任意指定一个时间值。
进程状态：为简单起见，这里假定进程有两种状态：就绪态和完成态。就绪状态用“R”表示，完成状态用“C”表示。假定进程一创建就处于就绪状态，运行结束时，就被置成完成状态。

// 代码参考
enum State {R,C};
typedef struct PCB{
    char name; // 进程名:以单个字符简化
    int startTime; // 到达时间
    int runTime; // 估计运行时间
    enum State processState; // 进程状态
    struct PCB* next; // 链接指针
}PCB;

2.按照进程到达的先后顺序排成一个循环队列，设一个队首指针指向第一个到达进程的首址。另外再设一个当前运行的进程指针，指向当前正运行的进程。

注：循环队列在本题中不能使用queue，只能使用链表。

3.执行进程调度时，首先选择队首的第一个进程运行。

4.由于本实验是模拟实验，所以对被选中的进程并不实际启动运行，而只是执行：估计运行时间减1，rumTime -= 1，输出当前运行进程的名字。用这个操作来模拟进程的一次运行。

5.进程运行一次后，以后的调度则将当前指针依次下移一个位置，指向下一个进程，即调整当前运行指针指向该进程的链接指针所指进程，以指示应运行进程，同时还应判断该进程的剩余运行时间是否为0。若不为0，则等待下一轮的运行；若该进程的剩余运行时间为0，则将该进程的状态置为完成状态“C”，并退出循环队列。

6.若就绪队列不空，则重复上述步骤4和5直到所有进程都运行完为止。

7.在所设计的调度程序中，应包含显示或打印语句，以便显示或打印每次选中进程的名称及运行一次后队列的变化情况。

8.在完成1-7后，请添加一个函数add(PCB* ptr)向队列尾新添加一个新的进程，让其加入执行，并观察打印输出。

9.请重构add函数，保证加入的新进程立刻在下一个时间片轮转时优先执行进行。请思考2种解决方案并加以实现。

10.在完成1-9后，请添加三个函数wait(PCB* ptr)，notify_one(PCB* ptr)和notify_all(PCB* ptr)。wait函数指定某一个进程进入等待，时间片轮转跳过该进程继续执行；notify_one为唤醒某一个指定进程，在下次时间片轮转时执行；notify_all为唤醒全部的wait进程，均在下次时间片轮转时执行。

注：提示：可以修改State进程状态，加入等待状态。可以为等待进程创建单独的记录表方便更改。

操作系统实验手册与实验报告模板：
本实验部分框架代码已经书写并放在仓库ex3/中并配有说明，请查阅在线文档后开始代码编写。
github仓库地址：https://github.com/zhangyuanes/OperatingSystemExperiments
gitee码云仓库地https://gitee.com/yanbo01haomiao/OperatingSystemExperiments
详情请查看仓库中readme.md.实验手册与实验报告模板已经更新至ex3。