完成,便可获得与终端型作业一样的响应时间:对于稍长的作业,通常也只需在第二队列和第 三队列各执行一个时间片即可完成,其周转时间仍然很短。对长批处理作业用户而言,他们的 作业将依次在第1,2,…,n个队列中运行,然后再按轮转方式邑行,用户不必担心其作业长期 得不到处理;而且每往下降一个队列,其得到的时间片将随着增加,故可进一步缩短长作业 的等待时间。 2.假设一个系统中有5个进程,它们的到达 表4.1进程到达和需服务时间 时间和服务时间如表4.1所示,忽略I/0以及 其他开销时间,若分别按先来先服务(FCFS)、非抢 匚进程『到达时间服务时间 占及抢占的短进程优先(SPF)、高响应比优先 HRN)、时间片轮转(RR,时间片=1)、多级反馈 队列(FB,第i级队列的时间片=2^i-1)以及立即 枪占的多级反馈队列(FB,第i级队列的时间片=2^i-1) BCDE 2468 3645 调度算法进行CPU调度,请给出各进程的完成时间、 周转时间、带权周转时间、平均周转时间和平均带 权周转时间。 分析:进程调度的关键是理解和掌握调度所采用的算法。FCFS算法选择最早进入就绪队 列的进程投入执行;SPF算法选择估计运行时间最短的进程投入执行,采用抢占方式时,若新 就绪的进程运行时间比正在执行的进程的剩余运行时间短,则运行时间+等待时间新进程将抢 占CPU;HRRN算法选择响应比(响应比=最高的运行时间+等待时间/运行时间)最高的进程投入 执行;R算法中,就绪进程按FIFO方式排队,CPU总是分配给队首的进程,并只能执行一个时间 片;FB算法将就绪进程排成多个不同优先权及时间片的队列,新就绪进程总是按FIFO方式先 进入优先权最高的队列,CPU也总是分配给较高优先权队列上的队首进程,若执行一个时间片 仍未完成,则转入下一级队列的末尾,最后一级队列则采用时间片轮转方式进行调度 答:各进程的完成时间、周转时间和带权周转时间(如表4.2所示) 表4.2进程的完成时间和周转时间 进程 完成时间 131820 周转时间 B97 FCFS 带权周转时间1.001.172.256.006.002.56 完成时间 15|11|11 SPF(非抢占)周转时间 7.6 带权周转时间.001.172.7511.51.511.84 完成时间31581010 SPF(抢占)周转时间3134227.2 带权周转时间1.002.161.001.001.001.59 完成时间 131515 HRRN 周转时间 带权周转时间1.001.172.253.53.52.14 完成时间 17 17 15 RR(g=1) 周转时间 4 1313|14|710.8 带权周转时间1.333.253.252.83.52.71 完成时间 10.4 FB(q=2-1)周转时间 2.56 带权周转时间12.503.502.83.00完成,便可获得与终端型作业一样的响应时间:对于稍长的作业,通常也只需在第二队列和第 三队列各执行一个时间片即可完成,其周转时间仍然很短。对长批处理作业用户而言,他们的 作业将依次在第 1,2,…,n 个队列中运行,然后再按轮转方式邑行,用户不必担心其作业长期 得不到处理； 而且每往下降一个队列，其得到的时间片将随着增加,故可进一步缩短长作业 的等待时间。 2.假设一个系统中有 5 个进程,它们的到达 表 4.1 进程到达和需服务时间 时间和服务时间如表 4.1 所示,忽略 I/0 以及 其他开销时间,若分别按先来先服务(FCFS)、非抢 占及抢占的短进程优先（SPF）、高响应比优先 (HRRN)、时间片轮转(RR,时间片=1)、多级反馈 队列(FB,第 i 级队列的时间片=2^i-1)以及立即 枪占的多级反馈队列(FB,第 i 级队列的时间片=2^i-1) 调度算法进行 CPU 调度,请给出各进程的完成时间、 周转时间、带权周转时间、平均周转时间和平均带 权周转时间。 分析：进程调度的关键是理解和掌握调度所采用的算法。FCFS 算法选择最早进入就绪队 列的进程投入执行;SPF 算法选择估计运行时间最短的进程投入执行,采用抢占方式时,若新 就绪的进程运行时间比正在执行的进程的剩余运行时间短,则运行时间+等待时间新进程将抢 占 CPU;HRRN 算法选择响应比(响应比=最高的运行时间+等待时间/运行时间)最高的进程投入 执行;RR算法中,就绪进程按FIFO方式排队,CPU总是分配给队首的进程,并只能执行一个时间 片;FB 算法将就绪进程排成多个不同优先权及时间片的队列,新就绪进程总是按 FIFO 方式先 进入优先权最高的队列,CPU 也总是分配给较高优先权队列上的队首进程,若执行一个时间片 仍未完成,则转入下一级队列的末尾,最后一级队列则采用时间片轮转方式进行调度。 答：各进程的完成时间、周转时间和带权周转时间(如表 4.2 所示) 表 4.2 进程的完成时间和周转时间 进程 A B C D E 平 均 FCFS 完成时间 周转时间 带权周转时间 3 3 1.00 9 7 1.17 13 9 2.25 18 12 6.00 20 12 6.00 8.6 2.56 SPF(非抢占) 完成时间 周转时间 带权周转时间 3 3 1.00 9 7 1.17 15 11 2.75 11 3 1.5 11 3 1.5 7.6 1.84 SPF(抢占) 完成时间 周转时间 带权周转时间 3 3 1.00 15 13 2.16 8 4 1.00 10 2 1.00 10 2 1.00 7.2 1.59 HRRN 完成时间 周转时间 带权周转时间 3 3 1.00 9 7 1.17 13 9 2.25 15 7 3.5 15 7 3.5 8 2.14 RR(q=1) 完成时间 周转时间 带权周转时间 4 4 1.33 17 13 3．25 17 13 3.25 20 14 2.8 15 7 3.5 10.8 2.71 FB(q=2^i-1) 完成时间 周转时间 带权周转时间 3 3 1 17 15 2.50 18 14 3.50 20 14 2.8 14 6 3.00 10.4 2.56 进程 到达时间 服务时间 A 0 3 B 2 6 C 4 4 D 6 5 E 8 2