操作系统课程设计指导书-.doc

设计题目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时间短或内存容量少的进程以较高的优先数，