进程调度算法.doc

进程调度算法 1. 实验目的调度的实质是操作系统按照某种预定的策略来分配资源。进程调度的目的是分配 CPU 资源。由于进程调度程序执行的频率很高,因此调度算法的好坏直接影响到操作系统的性能。本实验的目的是编程模拟实现几种常用的进程调度算法,通过对几组进程分别使用不同的调度算法,计算进程的平均周转时间和平均带权周转时间,比较各种算法的性能优劣。 2. 实验原理 、优先数调度算法、时间片轮转算法和分级调度算法 4种。?先来先服务( FCFS )调度算法本算法在进行调度时,总是把处理机分配给最先进入就绪队列的进程,一个进程一旦分得处理机,便一直执行下去,直到该进程完成或阻塞时,才释放处理机。?优先数调度算法基于优先级的调度算法给每个进程分配一个优先级,在每次进程调度时,调度器总是调度那个具有最高优先级的任务来执行。如果就绪队列中出现优先数相同的进程,则对这些有相同优先数的进程采用 FCFS 算法调度。对于占有处理机的进程,系统可以使用“抢占式”或“非抢占式”的策略。“非抢占式”指进程一旦占用处理机,除非自己愿意,否则操作系统不能将处理机强行夺走,即使该进程的优先数已经小于就绪队列中的某个进程。“抢占式”则相反,一旦就绪队列中的某个进程优先数大于正在执行的进程,立刻进行进程切换。基于优先级的调度算法可以分为如下两种类型: 静态优先级调度算法, 这种调度算法给那些系统中得到运行的所有进程都静态地分配一个优先级; 动态优先级调度算法, 这种调度算法根据任务的资源需求来动态地分配任务的优先级,其目的就是在资源分配和调度时有更大的灵活性。本实验的基本要求是实现固定优先数的调度算法,实验者可以在这个基础上添加动态优先数功能。?时间片轮转( RR )调度算法前几种算法主要用于批处理系统中,不能作为分时系统中的主调度算法, 在分时系统中,都采用时间片轮转法。简单轮转法:系统将所有就绪进程按 FIF O 规则排队,按一定的时间间隔把处理机分配给队列中的进程。这样,就绪队列中所有进程均可获得一个时间片的处理机而运行。时间片用完,调度程序自动停止该进程的执行,将它放到进程就绪队列的末尾,等待下一次执行,然后将处理机分配给就绪队列中新的队首进程,也让它执行一个时间片。重复这个过程,直到所有的进程执行完毕。 。设作业 Ji(i=1,2, …,n) 的提交时间为 tsi, 执行时间为 tri, 作业完成时间为 toi ,则作业 Ji的周转时间 Ti和周转系数 Wi 可定义为 Ti=toi-tsi, i=1,2, …,n Wi=Ti/tri, i=1,2, …,n 平均带权周转时间: 3. 实验内容( 1)编程实现本实验的程序,要求: ,进程控制块至少包括: ; ; ; ??? n1i iTn 1T??? n1i iW n 1W FCFS 算法、优先数调度算法和 RR 算法。 。这些信息可以直接从键盘上输入,也可以从文件读取。 。本实验需要对算法的执行计时,程序应该提供计算时间的方法。一种最简单的方法是使用键盘,比如每敲一次空格代表一个时间片的流逝。另一种方法是使用系统时钟,对于 VC++ 的 MFC 型程序,可响应窗口的 WM_TIMER 消息,对于 Borland C/C++ 程序,可截获 INT 1C H 或 INT 08H 时钟中断。 ,打印出结果信息。程序需要计算出每个进程的开始执行时间、结束时间、周转时间和带权周转时间,并为整个进程序列计算平均周转时间和平均带权周转时间。程序将计算结果按一定的格式显示在计算机屏幕上或输出到文件中。 。( 2 )对下列就绪进程序列分别使用上面的几种算法进行调度,计算每种算法下的平均周转时间和平均带权周转时间。进程号到达时间要求执行时间 001 1135 2210 335 469 5721 6935 7 1123 81242 9131 10147 11205 12233 132422 142531 15261 4. 实验步骤 ,请把它输入到计算机里。(已输入,见程序文件 ) 、运行此程序。 iii. 注意此程序没有最后完成,只有程序的主体结构,有些重要的函数还没有实现,以空函数的形式出现。请实现这些空函数。 。 ,使用实验内容(2)中数据作为测试,记