山东科技大学学生课程设计
1．进程调度算法
1.3时间片轮转调度算法
1.3.1需求分析
时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。调度程序所要做的就是维护一张就绪进程列表，当进程用完它的时间片后，它被移到队列的末尾。
- 18 -
山东科技大学学生课程设计
基本功能如下：
（1）将到达的进程按照到达顺序排成一个队列；
（2）程序在运行时，设定一个时间片，每个进程每次只运行一个时间片，直到进程运行结束。
以下是各功能模块的功能描述： 1．主函数模块
本模块的主要功能是输出算法的名字以及对算法的调用。 2．进程创建和排序模块
本模块的主要功能是将创建新的进程，获得进程的进程编号、进程名、运行状态、到达时间等，并按到达时间拍成一个队列 3．寻找进程模块
本模块的主要功能是根据队列指针和当前时间，找到当前到达且没有运行的作业，并在这些进程中找到到达时间最早的作业。 4．运行及输出模块
本模块的主要功能是运行当前运行时间最短的作业，并输出运行后的进程的调度顺序以及进程执行完后的运行状态、到达时间、开始时间、结束时间、运行时间、周转时间、带权周转时间。 测试数据：
进程的个数：2 时间片大小：2
进程编号：1 进程名：a 到达时间：2 进程运行时间：4 进程编号：2 进程名：b 到达时间：1 进程运行时间：5
1.3.2 概要设计
本次程序使用c语言的方法，在程序中定义了一个结构体来标示进程控制块，每个结构体包括进程编号、进程名、运行状态、到达时间、开始时间、结束时间、运行时间、周转时间、带权周转时间以及指向下个进程的指针。程序中定义了创建进程及排序函数、查找函数、运行和输出函数，首先要做的是输入进程的相关信息并创建进程、然后调用了排序函数将进程按到达时
- 19 -
山东科技大学学生课程设计
间排成一个队列，当进程运行时，通过查找当前队列中最早到达的进程后运行，每个进程运行一个时间片，运行结束后，如果没有运行完，则将该作业移到后备队列中，直至运行结束。
1.3.3 详细设计
1.主函数模块
首先调用list( )函数，再调用runrr()函数。
2．进程创建和排序模块
创建进程时，首先用malloc( )先申请内存，建一个空的后备队列，然后输入进程的相关信息，通过对比进程的arrivetime排成一个队列。 3．寻找进程模块
在实现查找最先到达进程功能时，通过循环，将每一个进程的arrivetime与当前的最早到达时间t进行比较，如果arrivetime小于t，则将该进程的arrivetime赋给t，并将指针指向下一个进程，直到找到到达时间最早的进程。
4．移动队列模块
每运行完一个进程，就调用move函数，将他移动到队列的后面。 5．运行及输出模块
调用runsjf（）程序进行运行，当运行时，把进程的开始时间begintime置为当前时间time，完成时间finishtime为开始时间begintime加上运行时间runtime，周转时间turntime为finishtime减arrivetime，带权周转时间wturntime为turntime/runtime。
- 20 -
山东科技大学学生课程设计
开始 输入进程信息和时间片 将进程排成队列 调用search（）函数 arrivetime< 是 否 mintime=arrivetime 指针指向下个进程 否 下一个进程是否为空 是 调用runrr()运行进程 输出运行后信息 是 进程是否运行完 否 结束 图2：SJF流程图
- 21 -
山东科技大学学生课程设计
程序源代码
#include
typedef struct process {
int num;//进程编号 char name[2];//进程名
char state;//运行状态 Y：完成 N：未完成 int arrivetime;//到达时间 int begintime;//开始时间 int finishtime;//结束时间 int runtime;//运行时间 int turntime;//周转时间
int wturntime;//带权周转时间
int needtime;//进程剩余还需要的时间 int rrtime;//进程被运行的次数
struct process *next;//指向下个作业
} process;
//全局变量定义
int totaltime;//记录总时间 int rr;//时间片的大小 int count;
struct process *p,*q,*s;
//函数声明
struct process* search(struct process *head,int atime);
- 22 -