《操作系统》实验二 进程调度.doc

实验二、多任务操作系统下的进程调度 （综合性实验） 一、实验目的 进程是操作系统中最重要的概念之一,进程调度又是操作系统核心的主要内容。通过编写和调试进程调度程序,加深对进程调度工作和各种调度算法的了解。 二、实验要求 用C语言实现进程调度控制过程中的有关工作：现场保护与恢复，处理运行指针和进程调度。 三、实验内容 1、实验准备 首先进行系统初始化 , 在创建了系统进程、各用户进程之后转进程调度控制程序 , 即进入多进程并发执行的状态。 进程调度控制程序负责将 CPU 控制以从一个进程转向另一个进程。当进行控制权转接 时必须做以下几件事 : ①保护当前运行进程的现场； ②处理当前运行进程 , 将该进程插入就绪队列或其它队列； ③选一优先级最高的进程作为运行进程； ④恢复被选中进程的现场。 现场的保护与恢复是经过两个步骤完成的。其中,在保护现场时,首先将CPU现场信息送内存r区,然后再将r区内容保存到该进程pcb的reg区；恢复现场则相反,首先从被选中进程的 pcb的reg区中恢复现场信息到内存r区,然后用r区内容设置CPU各寄存器。 2、数据结构 struct pcb { int id; /*进程标识*/ int priority; /*优先数或轮转时间片数*/ int cputime; /*已占用CPU的时间片数*/ int alltime; /*进程所需的时间片数*/ char status; /*进程状态指针*/ *next; /*进程当前队列链接字*/ *all_q_next; /*总链队列链接字*/ }pcba[num]; 3、算法 （1）优先数法 进程就绪链按优先数大小从高到低排列，链首进程首先投入运行。每过一个时间片,运行进程所需运行的时间片数减1,说明它运行了一个时间片；优先数减3,因为一个进程运行时如果在一个片中完成不了， 其优先级应降低一级。（注意,在本程序中通过对进程的PCB执行”优先数-3“和“进程所需时间片数-1”以及“进程已占用CPU的时间片数+1”来模拟进程的一次运行。而在实际的系统中，当一个进程被选中运行时, 必须恢复进程的现场,让它占有CPU运行,直到出现等待事件或运行结束）。然后比较现行程序和就绪链链首进程的优先数,如果仍是现行进程高或者相同,就让现行进程继续运行,否则,将现行运行进程按其优先数大小插入就绪链,将其状态改为“就绪态”，并调度就绪链链首进程投入运行。直到所有的进程都运行完其各自的时间片数。 （2）简单轮转法 进程就绪链按进程进入的先后排列,进程每次占用CPU的轮转时间按其重要程度登入PCB中的“优先数/轮转时间片数”记录顶。每过一个时间片,运行进程占用CPU的时间片数加1,进程所需的时间片数减1（和优先数法类似，程序只是简单地通过PCB中的cputime+1,alltime-1来模拟进程的一次运行）。然后比较占用CPU的时间片数（即cputime）是否与该进程的轮转时间片数（即priority）相等,若相等则说明已到达轮转时间,应将现行运行进程排到就绪链链尾，调度链首进程占用CPU,并改变它们的进程状态,直到所有的进程完成各自的时间片（alltime=0）。 4.程序构成 由六个子程序构成，各子程序及其完成的工作为： （1）init子程序 按照给定的进程调度算法（优先数法或简单轮转法）随机地产生5个进程控制块的内容,并形成进程控制块链。置链首进程为初始运行进程。 （2）print子程序 按格式打出调度信息及各进程控制块的内容，print子程序在每次进程调度的时候都要执行一次。 （3）prisch子程序 将优先数算法调度进程使之模拟运行。 （4）insert子程序 将落选的进程按优先数大小插入到就绪队到。 （5）timesch子程序 按简单轮转算法调度进程使之模拟运行。 （6）insert1子程序 将落选的进程链到就绪队队列末尾。 各子程序之间的调度关系如下图2.1: main main timesch init prisch timesch init prisch Insert1printinsert Insert1 print insert 图2.1程序之间调度关系 5、程序框图 开始 开始 输入调度算法 输入调度算法 轮转优先数 轮转 优先数 优先数或轮转？ 优先数或轮转？ 生成按进入次序排列的PCB生成按优先数大小排列的PCB 生成按进入次序排列的PCB 生成按优先数大小排列的PCB 链首进程投入运行链首进程投入运行 链首进程投入运行 链首进程投入运行 时间片到，进程时间片数-1,占用CPU时间+1 时间片