实验一
课程名称：操作系统
课程类型：必修
实验项目名称：进程管理
实验题目：短作业优先算法、动态可剥夺优先数算法和基本循环轮转算法。

一、实验目的
进程是操作系统最重要的概念之一，进程调度又是操作系统核心的主要内容。

本实验要求学生独立的用高级语言编写和调试一个简单的模拟进程调度的程序。

通过本实验，加深学生理解有关进程控制块、进程队列的概念，并体会和了解短作业优先、优先数和时间片轮转调度算法的具体实施办法。

二、实验要求及实验环境
（1）设计一个有n 个进程的进程调度程序（具体个数可由键盘输入）。

每一个进程用一个进程控制块PCB 来代表。

PCB 中应包含下列信息：进程名、进程优先数、进程的状态、进程需要运行的时间及利用CPU运行的时间等。

进程的个数、各进程的优先数、轮转时间片数以及进程运行需要地时间可由
键盘输入。

（2）调度程序应包含2~3 种不同的调度算法，运行时可任选一种。

（3）每个进程处于运行Run、就绪ready 和完成Finish 三种状态之一，假定初始状态都为就绪状态ready。

（也可没有Finish状态，可以在设计程序时实现处以Finish状态的进程删掉）。

（4）系统能显示各进程状态和参数的变化情况。

（5）动态可剥夺优先数算法是：在创建进程时给定一个初始的优先数，当进程获得一次cpu后其优先数就减少1，如果就绪队列中有优先级更高的将剥夺运行中的进程。

三、设计思想
（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）
1．程序流程图
（见下图）
2．逻辑设计
使用链表表示就绪队列，每个元素包括进程名、进程优先数、进程的状态、进程需要运行的时间及利用CPU运行的时间等信息。

该结构需支持以下操作：取头节点，在表尾插入节
点，删除头节点，判断表空。

为此，至少引入3 个指针变量：头指针HEAD 和活动指针p、q。

3、物理设计
struct pcb
{ char name[10];
int priority;
int state;
int needtime;
int runtime;
struct pcb *next;
}; /*用此结构体来模拟一个进程*/
开始 选择菜单的选项choice
创建 进程 链表
输出菜单
1 短作业 优先 调度
动态 优先 级调度 循环 轮转 调度
退 出
2 3 4 0 结束
图1-1主程序的流程图
开始
就绪队列 是否为空？
取出执行时间最短的进程 修改该进程的状态为“RUN ” 输出运行进程的信息 输出若干就绪进程的信息 从链表中删除运行完的进程
否
是
结束
图1-2短作业优先算法的流程图
开始
就绪队列 是否为空？
是
否
Flag=1?
是
取出优先级最高的进程； 并修改进程的状态为“RUN ” 运行时间加1；
优先级减1。

输出运行进程的信息； 输出若干就绪进程的信息
运行结
束否？
是 从链表中删除运行完的进程
否 否
该进程优先级是
就绪进程中优先级最大的么？ 是
Flag=0 否 FLAG=1; 进程运行状态为“ready ”
结束
图1-3动态可剥夺优先数算法的流程图
指针r 指向就绪队列的最后一个进程 选中就绪队列的第一个进程； 将该进程的状态改为“RUN ”； 输出该运行进程的信息。

是
输入时间片
就绪队列 是否为空？
否
时间片内，进程运行结束否
否 运行时间=运行时间+时间片；并输出
输出就绪进程的信息
运行时间=需要时间； 并输出
进程运行
结束否
是 删除该进程 否
将该进程移到表尾
是
结束
开始
图1-4循环轮转算法的流程图。