设计题目1 进程调度算法1.1 设计目的进程管理是操作系统中的重要功能，用来创建进程、撤消进程、实现进程状态转换，它提供了在可运行的进程之间复用CPU的方法。

在进程管理中，进程调度是核心，因为在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态，当就绪进程个数大于处理器数目时，就必须依照某种策略决定哪些进程优先占用处理器。

本实验模拟在单处理器情况下的进程调度，目的是加深对进程调度工作的理解，掌握不同调度算法的优缺点。

下面回顾一下进程管理的相关内容。

1.1.1 进程控制块为了管理和控制进程，系统在创建每一个进程时，都为其开辟一个专用的存储区，用以随时记录它在系统中的动态特性。

而当一个进程被撤消时，系统就收回分配给它的存储区。

通常，把这一存储区称为该进程的“进程控制块”（Process Control Block）。

由于PCB是随着进程的创建而建立，随着进程的撤消而取消的，因此系统是通过PCB 来“感知”一个个进程的，PCB是进程存在的唯一标志。

随操作系统的不同，PCB的格式、大小以及内容也不尽相同。

一般地，在PCB中大致应包括如下4方面的信息。

·标识信息：进程名等。

·说明信息：进程状态、程序存放位置、数据存放位置等。

·现场信息：通用寄存器内容、控制寄存器内容、断点地址等。

·管理信息：进程优先数、队列指针等。

1.1.2 进程控制块队列在多道程序设计环境里，同时会创建多个进程。

当计算机系统只有一个CPU时，每次只能让一个进程运行，其他的进程或处于就绪状态，或处于阻塞状态。

为了对这些进程进行管理，操作系统要做三件事。

（1）把处于相同状态的进程的PCB，通过各自的队列指针链接在一起，形成一个个队列。

通常有运行队列、就绪队列、阻塞队列。

（2）为每一个队列设立一个队列头指针，它总是指向排在队列之首的进程的PCB。

（3）排在队尾的进程的PCB，它的“队列指针”项内容应该为“NULL”，或一个特殊的符号，以表示这是该队的队尾PCB。

在单CPU系统中，任何时刻都只有一个进程处于运行状态，因此运行队列中只能有一个PCB；系统中所有处于就绪状态的进程的PCB排成一队，称其为“就绪队列”。

一般地，就绪队列中会有多个进程的PCB排在里面，它们形成处理机分配的候选对象。

如果就绪队列里没有PCB存在，则称该队列为空；所有处于阻塞状态进程的PCB，应该根据阻塞的原因进行排队，每一个都称为一个“阻塞队列”。

比如等待磁盘输入/输出进程的PCB排成一个队列，等待打印机输出进程的PCB排成一个队列等。

所以，系统中可以有多个阻塞队列，每个阻塞队列中可以有多个进程的PCB，也可以为空。

1.1.3 进程调度算法进程调度算法用于确定就绪队列中的哪一个进程即将获得CPU。

常用的进程调度算法有先来先服务法、时间片轮转法、优先数法等。

1．先来先服务调度算法先来先服务调度算法的基本思想是：以到达就绪队列的先后次序为标准来选择占用处理机的进程。

一个进程一旦占有处理机，就一直使用下去，直至正常结束或因等待某事件的发生而让出处理机。

采用这种算法时，应该这样来管理就绪队列：到达的进程的PCB总是排在就绪队列末尾；调度程序总是把CPU分配给就绪队列中的第一个进程使用。

2．时间片轮转法时间片轮转调度算法的基本思想是：为就绪队列中的每一个进程分配一个称为“时间片”的时间段，它是允许该进程运行的时间长度。

在使用完一个时间片后，即使进程还没有运行完毕，也要强迫其释放处理机，让给另一个进程使用。

它自己则返回到就绪队列末尾，排队等待下一次调度的到来。

采用这种调度算法时，对就绪队列的管理与先来先服务完全相同。

主要区别是进程每次占用处理机的时间由时间片决定，而不是只要占用处理机就一直运行下去，直到运行完毕或为等待某一事件的发生而自动放弃。

3．优先数调度算法优先数调度算法的基本思想是：为每一个进程确定一个优先数，进程就绪队列按照优先数排序。

如何确定进程的优先数（也就是进程的优先级）？可以从如下几个方面考虑。

（1）根据进程的类型。

系统中既有系统进程，又有用户进程。

系统进程完成的任务是提供系统服务，分配系统资源，因此，给予系统进程较高的优先数能够提高系统的工作效率。

（2）根据进程执行任务的重要性。

重要性和紧迫性高的进程应当被赋予较高的优先级。

（3）根据进程程序的性质。

一个CPU繁忙的进程，由于需要占用较长的运行时间，影响系统整体效率的发挥，因此只能给予较低的优先数。

一个I/O繁忙的进程，给予它较高的优先数后，就能充分发挥CPU和外部设备之间的并行工作能力。

（4）根据对资源的要求。

系统资源有处理机、内存储器和外部设备等。

可以按照一个进程所需资源的类型和数量，确定它的优先数。

比如给予占用CPU时间短或内存容量少的进程以较高的优先数，这样可以提高系统的吞吐量。

（5）根据用户的请求。

系统可以根据用户的请求，给予它的进程很高的优先数，作“加急”处理。

4．多级队列调度算法多级队列调度算法也称多级反馈队列调度算法，它是时间片调度算法与优先数调度算法的结合。

实行这种调度算法时，系统中将维持多个就绪队列，每个就绪队列具有不同的调度级别，可以获得不同长度的时间片。

例如，系统维持N个就绪队列，第1级就绪队列中进程的调度级别最高，可获得的时间片最短，第N级就绪队列中进程的调度级别最低，可获得的时间片最长。

具体的调度方法是：创建一个新进程时，它的PCB将进入第1级就绪队列的末尾。

对于在第1级到第N-1级队列中的进程，如果在分配给它的时间片内完成了全部工作，那么就撤离系统；如果在时间片没有用完时提出了输入/输出请求或要等待某事件发生，那么就进入相应的阻塞队列里等待。

在所等待的事件出现时，仍回到原队列末尾，参与下一轮调度（也就是每个队列实行先来先服务调度算法）；如果用完了时间片还没有完成自己的工作，那么只能放弃对CPU的使用，降到低一级队列的末尾，参与那个队列的调度。

对位于最后一个队列里的进程，实行时间片轮转调度算法。

整个系统最先调度1级就绪队列；只有在上一级就绪队列为空时，才去下一级队列调度。

当比运行进程更高级别的队列中到达一个进程（可以肯定，在此之前比运行进程级别高的所有队列全为空）时，系统将立即停止当前运行进程的运行，让它回到自己队列的末尾，转去运行级别高的那个进程。

可以看出，多级队列调度算法优先照顾I/O繁忙的进程。

I/O繁忙的进程在获得一点CPU 时间后就会提出输入/输出请求，因此它们总是被保持在1、2级等较前面的队列中，总能获得较多的调度机会。

对于CPU繁忙的进程，它们需要较长的CPU时间，因此会逐渐地由级别高的队列往下降，以获得更多的CPU时间，它们“沉”得越深，被调度到的机会就越少。

但是，一旦被调度到，就会获得更多的CPU时间。

1.2 设计要求1.2.1 界面要求实验要求采用简单的控制台界面，包括一级功能菜单，如图1-1所示。

图1-1 界面要求1.2.2功能要求实验应该包括以下功能：1.运行先来先服务进程调度算法；2.运行时间片轮转进程调度算法；3.运行优先数进程调度算法；4.运行多级反馈队列进程调度算法；5.显示就绪进程队列；6.显示运行进程队列；7.显示阻塞进程队列；8.创建新进程；9.阻塞进程；10.唤醒进程；11.删除进程；12.退出程序。

1.3 设计步骤1.3.1 总体设计确定程序包含多少个模块，每个模块有哪些功能、包括哪些函数，模块之间的调用关系如何。

由于本实验并不复杂，所以只用一个模块实现。

要求宏、数据结构、全局变量和函数原型放在头文件中，而函数实现放在源文件中。

假设头文件名为process_schedule.h，源程序文件名为process_schedule.cpp。

实验中用到的主要数据结构是进程控制块，其结构如图1-2所示。

实验中用到1个宏和8个全局变量，如图1-3所示。

实验中用到的主要函数有10个，如图1-4所示。

图1-2 进程控制块图1-3 宏和全局变量图1-4 函数名称及作用1.3.2 详细设计及实现1. 头文件头文件中含有图1-2、图1-3和图1-4的内容。

#include <conio.h>#include <stdlib.h>#include <stdio.h>#include <io.h>#include <string.h>#define MAX_PROCESS 10int process_number=0; //下一个可用的进程编号typedef struct pcb{struct pcb *next; //下一个进程控制块指针char process_name[20]; //进程名int process_number; //进程编号int process_start_moment; //进程启动时刻int process_need_time; //要求运行时间int process_time_slice; //时间片int process_priority; //优先数}PCB; //自定义数据类型：进程控制块PCB pcb_table[MAX_PROCESS]; //进程控制块表PCB *pcb_run=NULL; //进程运行队列头指针PCB *pcb_free=NULL; //进程空闲队列头指针PCB *pcb_ready=NULL; //进程就绪队列头指针PCB *pcb_ready_rear=NULL; //进程就绪队列尾指针PCB *pcb_blocked=NULL; //阻塞队列头指针PCB *pcb_blocked_rear=NULL; //阻塞队列尾指针void init_pcb_table( ); //初始化进程控制块表void print_space(int num); //显示若干个空格void display_process_queue(PCB *queue); //显示进程队列PCB *create_process( ); //创建进程函数,成功时返回新创建进程的PCB,失败时返回NULL。

void block_process_by_name( ); //阻塞指定名称的进程。

void wakeup_process( ); //唤醒进程void FCFS( ); //先来先服务进程调度算法void RR( ); //时间片轮转进程调度算法void HPF( ); //优先数进程调度算法void MFBQ( ); //多级反馈队列进程调度算法2. 主函数main主函数用来初始化进程队列，显示菜单，接收用户输入的菜单选项，并根据用户的选项执行相应的功能。

其处理流程如下：main( ){初始化进程控制块表；while(1){显示菜单；输出提示信息；接收用户输入的选项，如果输入不是数字1~8或者字母a~d则重新输入；switch(选项){case …1‟：调用先来先服务进程调度算法；break；case …2‟：调用时间片轮转进程调度算法；break；case …3‟：调用优先数进程调度算法；break；case …4‟：调用多级反馈队列进程调度算法；break；case …5‟：显示就绪进程队列；break；case …6‟：显示阻塞进程队列；break；case …7‟：显示运行进程队列；break；case …a‟：调用创建进程函数；break；case …b‟：调用删除进程函数；break；case …c‟：调用阻塞进程函数；break；case …d‟：调用唤醒进程函数；break；case …8‟：返回；}}返回；}说明：通常用循环语句和多分支语句实现菜单。