文档介绍：进程调度算法
实验目的
调度的实质是操作系统按照某种预定的策略来分配资源。进程调度的目的是分配CPU资源。由于进程调度程序执行的频率很高,因此调度算法的好坏直接影响到操作系统的性能。本实验的目的是编程模拟实现几种常用的进程调度算法,通过对几组进程分别使用不同的调度算法,计算进程的平均周转时间和平均带权周转时间,比较各种算法的性能优劣。
实验原理
进程调度算法描述
进程调度算法包括先来先服务调度算法、优先数调度算法、时间片轮转算法和分级调度算法4种。
先来先服务(FCFS)调度算法
本算法在进行调度时,总是把处理机分配给最先进入就绪队列的进程,一个进程一旦分得处理机,便一直执行下去,直到该进程完成或阻塞时,才释放处理机。
优先数调度算法
基于优先级的调度算法给每个进程分配一个优先级,在每次进程调度时,调度器总是调度那个具有最高优先级的任务来执行。如果就绪队列中出现优先数相同的进程,则对这些有相同优先数的进程采用FCFS算法调度。
对于占有处理机的进程,系统可以使用“抢占式”或“非抢占式”的策略。“非抢占式”指进程一旦占用处理机,除非自己愿意,否则操作系统不能将处理机强行夺走,即使该进程的优先数已经小于就绪队列中的某个进程。“抢占式”则相反,一旦就绪队列中的某个进程优先数大于正在执行的进程,立刻进行进程切换。
基于优先级的调度算法可以分为如下两种类型:静态优先级调度算法,这种调度算法给那些系统中得到运行的所有进程都静态地分配一个优先级;动态优先级调度算法,这种调度算法根据任务的资源需求来动态地分配任务的优先级,其目的就是在资源分配和调度时有更大的灵活性。本实验的基本要求是实现固定优先数的调度算法,实验者可以在这个基础上添加动态优先数功能。
时间片轮转(RR)调度算法
前几种算法主要用于批处理系统中,不能作为分时系统中的主调度算法,在分时系统中,都采用时间片轮转法。简单轮转法:系统将所有就绪进程按FIFO规则排队,按一定的时间间隔把处理机分配给队列中的进程。这样,就绪队列中所有进程均可获得一个时间片的处理机而运行。时间片用完,调度程序自动停止该进程的执行,将它放到进程就绪队列的末尾,等待下一次执行,然后将处理机分配给就绪队列中新的队首进程,也让它执行一个时间片。重复这个过程,直到所有的进程执行完毕。
衡量算法性能的参数
下面引入两个衡量调度算法性能的参数。设作业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
平均带权周转时间:
实验内容
(1)编程实现本实验的程序,要求:
建立进程的进程控制块,进程控制块至少包括:
进程名称;
进程需要执行时间;
进入就绪队列时间;
进程执行开始时间
进程执行结束时间
进程的优先数
编程实现FCFS算法、优先数调度算法和RR算法。
进程及相关信息的输入。这些信息可以直接从键盘上输入,也可以从文件读取。
时间片与时间流逝的模拟。本实验需要对算法的执行计时,程序应该提供计算时间的方法。一种最简单的方法是使用键盘,比如每敲一次空格代表一个时间片的流逝。另一种方法是使用系统时钟,对于VC++的MFC型程序,可响应窗口的WM_TIMER消息,对于Borland C/C++程序,可截获INT 1CH或INT 08H时钟中断。
一组进程序列执行完毕,打印出结果信息。程序需要计算出每个进程的开始执行时间、结束时间、周转时间和带权周转时间,并为整个进程序列计算平均周转时间和平均带权周转时间。程序将计算结果按一定的格式显示在计算机屏幕上或输出到文件中。
实现数据在磁盘文件上的存取功能。
(2)对下列就绪进程序列分别使用上面的几种算法进行调度,计算每种算法下的平均周转时间和平均带权周转时间。
进程号
到达时间
要求执行时间
0
0
1
1
1
35
2
2
10
3
3
5
4
6
9
5
7
21
6
9
35
7
11
23
8
12
42
9
13
1
10
14
7
11
20
5
12
23
3
13
24
22
14
25
31
15
26
1
实验步骤
下面是本实验程序的一个简单实现,请把它输入到计算机里。(已输入,)
调试、运行此程序。
注意此程序没有最后完成,只有程序的主体结构,有些重要的函数还没有实现,以空函数的形式出现。请实现这些空函数。
调试这些新实现的函数。
运行整个程序,使用实验内容(2)中数据作为测试,记录测试结果。