处理机调度算法的模拟.doc

实验三：处理器调度算法的模拟 实验学时：3实验类型：（设计）一、实验目的1. 理解多道程序系统中处理机调度算法；2. 掌握单处理机情况下，常用处理机调度算法的模拟实现方法； 3. 培养学生分析和设计程序的能力。二、实验条件Windows 2000/Windows ME/Linux等操作系统，装有JAVA、C、C+等语言工具的环境。三、实验原理及相关知识在采用多道程序系统中，往往有若干个进程同时处于就绪状态。当就绪进程个数大于处理器数时，就必须依照某种策略来决定哪些进程优先占用处理器。本实验模拟在单处理器情况下的处理器调度，包括先来先服务算法、短作业优先算法、时间片轮转算法等，帮助学生加深了解处理器调度的相关知识。四、实验步骤本实验模拟单处理器系统的进程调度，加深对进程的概念及进程调度算法的理解。用某种语言编写和调试一个进程调度的算法程序，有一些简单的界面，能够运行，仿真操作系统中进程调度的原理和过程。1、先来先服务调度算法 假设系统有5个进程，每个进程由一个进程控制块标识。进程控制块内容如下：1）进程名即进程标识。2）链接指针：按照进程到达系统的时间将处于就绪状态的进程连接成一个就绪队列。指针指出下一个到达进程的进程控制块首地址。最后一个进程的链接指针为NULL。3）估计运行时间：可由设计者任意指定一个时间值。4）到达时间：进程创建时的系统时间或由用户指定。调度时，总是选择到达时间最早的进程。5）进程状态：为简单起见，这时假定进程有两种状态：就绪和完成。并假定进程一创建就处于就绪状态，用R表示。当一个进程运行结束时，就将其置成完成态，用C表示。 设置一个队首指针head ，用来指出最先进入系统的进程，各就绪进程通过链接指针连在一起。 处理机调度时总是选择队首指针指向的进程投入运行。由于本实验只是模拟实验，所以对被选中的进程并不实际启动运行，而只是执行：估计运行时间减一，用这个操作来模拟进程的一次运行，而且省去进程的现场保护和现场恢复工作。 在所设计的程序中应有显示或打印语句，能显示或打印正运行进程的进程名、已运行时间、还剩余时间、就绪队列中的进程等。所有进程运行完成时，给出各进程的周转时间和平均周转时间。2、设计一个按高响应比优先法实现处理器调度的程序动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。例如，我们可以规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高。若所有的进程都具有相同的优先权初值，则显然是最先进入就绪队列的进程，将因其动态优先权变得最高而优先获得处理机，此即FCFS算法。若所有的就绪进程具有各不相同的优先权初值，那么，对于优先权初值低的进程，在等待了足够的时间后，其优先权便可能升为最高，从而可以获得处理机。当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以速率b下降，则可防止一个长作业长期地垄断处理机。高响应比优先调度算法是一种动态优先权调度算法，其优先权的变化规律可描述为： 由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为高响应比优先(HRRN)调度算法计算举例：进程到达时间要求服务时间A04B13C25D32E44 T=0：只有作业A已到达，调度作业A运行。 T=4：作业A完成，作业B、C、D、E已到达，计算作业B、C、D、E响应比RP分别为： 1+3/3、1+2/5、1+1/2、1+0/4，作业B响应比最大调度运行。 T=7：作业B完成，作业C、D、E已到达，计算作业C、D、E响应比RP分别为： 1+5/5、1+4/2、1+3/4，作业D响应比最大调度运行。 T=9：作业D完成，作业C、E已到达，计算作业C、E响应比RP分别为： 1+7/5、1+5/4，作业C响应比最大调度运行。 T=14：作业C完成，只有作业E未完成，调度作业E运行。 3设计一个按时间片轮转法实现处理器调度的程序（选作）1)、 假定系统有五个进程，每一个进程用一个进程控制块PCB来代表。进程控制块的格式为：进程名指针要求运行时间已运行时间状态进程名作为进程的标识，假设五个进程的进程名分别为Q1，Q2，Q3，Q4，Q5。指针进程按顺序排成循环队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程的指针指出第一个进程的进程控制块首地址。要求运行时间假设进程需要运行的单位时间数。已运行时间假设进程已经运行的单位时间数，初始值为“0”。状态有两种状态，“就绪”和“结束”，初始状态都为“就绪”，用“R”表示。当一个进程运行结束后，它的状态为“结束”，用“E”表示。2)、 每次运行所设计的处理器调度程序前，为每个进程任意确定它的“要求运行时间”。3)、把五个进程按顺序排成循环队列，用指针指出队列连接情况。另用一标志单元记录轮到运行的进程。例如，当前轮到P2执行，则有：标志单元 K2 K1Q1 K2Q2 K3Q3 K4Q4 K5Q5K2K3K4K5K12312410000RRRRRPCB1PCB2PCB3PCB4PCB54)、 处理器调度总是选择标志单元指示的进程运行。由于本实验是模拟处理器调度的功能，所以，对被选中的进程并不实际的启动运行，而是执行：已运行时间+1来模拟进程的一次运行，表示进程已经运行过一个单位的时间。请同学注意：在实际的系统中，当一个进程被选中运行时，必须置上该进程可以运行的时间片值，以及恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行满一个时间片。在这时省去了这些工作，仅用“已运行时间+1”来表示进程已经运行满一个时间片。5)、 进程运行一次后，应把该进程的进程控制块中的指针值送到标志单元，以指示下一个轮到运行的进程。同时，应判断该进程的要求运行时间与已运行时间，若该进程的要求运行时间已运行时间，则表示它尚未执行结束，应待到下一轮时再运行。若该进程的要求运行时间=已运行时间，则表示它已经执行结束，应指导它的状态修改成“结束”（E）且退出队列。此时，应把该进程的进程控制块中的指针值送到前面一个进程的指针位置。6)、若“就绪”状态的进程队列不为空，则重复上面的4和5的步骤，直到所有的进程都成为“结束”状态。7)、在所设计的程序中应有显示或打印语句，能显示或打印每次选中进程的进程名以及运行一次后进程队列的变化。可以为五个进程任意确定一组“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中的进程名以及进程控制块的动态变化过程。五、实验报告要求(1) 程序中使用的数据结构及符号说明。/程序中使用的数据结构示例typedef struct _proc /*进程结构体*/ char name32;/*进程名*/ int run_time; /*要求运行总时间*/ int alloc_time; /*已经运行时间*/ int req_time;/*还需要的运行时间*/ int pri;/*优先级：时间片调度中未使用*/ PROC_STATE s