作业调度算法

时间片轮转

多道作业的操作系统中，时间片轮转调度算法，时间片为 1。

完成表格，计算平均周转时间和平均带权周转时间。

规则

新来的进程排在刚执行完的进程前。

周转时间 = 完成时间 - 到达时间

带权周转时间 = $\frac{\mathrm{周}\mathrm{转}\mathrm{时}\mathrm{间}}{\mathrm{估}\mathrm{计}\mathrm{运}\mathrm{行}\mathrm{时}\mathrm{间}(\mathrm{服}\mathrm{务}\mathrm{时}\mathrm{间})}$

响应比=$\frac{\mathrm{等}\mathrm{待}\mathrm{时}\mathrm{间}+\mathrm{服}\mathrm{务}\mathrm{时}\mathrm{间}}{\mathrm{服}\mathrm{务}\mathrm{时}\mathrm{间}}$

画出草稿表格

第一时间片，A 进入，执行

开始时刻	就绪队列	执行的进程	进程执行完时间
t=0-1	A	A

第二时间片，B 进入，排 A 前

此时 A 执行完，放到队尾。

B 新来，放到 A 的前面。

开始时刻	就绪队列	执行的进程	进程执行完时间
t=1-2	BA	B

第三时间片，C 进入，排 B 前

此时 B 执行完，放到队尾，队伍是 AB。

C 新来，放到 B 的前面。

最前面的是 A，所以 A 执行。

开始时刻	就绪队列	执行的进程	进程执行完时间
t=2-3	ACB	A

第四时间片，D 进入，排 A 前

此时 A 执行完，放到队尾，队伍是 CBA。

D 新来，放到 A 的前面。

最前面的是 C，所以 C 执行。

开始时刻	就绪队列	执行的进程	进程执行完时间
t=3-4	CBDA	C

第五时间片，E 进入，排 C 前

此时 C 执行完，放到队尾，队伍是 BDAC。

E 新来，放到 C 的前面。

最前面的是 B，所以 B 执行。

开始时刻	就绪队列	执行的进程	进程执行完时间
t=4-5	BDAEC	B

第六时间片，轮转

此时已经全部进入，按照队列顺序开始执行。

开始时刻	就绪队列	执行的进程	进程执行完时间
t=5-6	DAECB	D

运行完后退出队列

完成顺序是：

B$\to$D$\to$A$\to$C$\to$E

周转时间=结束执行时间-进入磁盘时间

带权周转时间= $\frac{\mathrm{周}\mathrm{转}\mathrm{时}\mathrm{间}}{\mathrm{服}\mathrm{务}\mathrm{时}\mathrm{间}}$

先来先服务（FCFS）

短作业优先

优先级高者优先

高响应比优先

响应比=$\frac{\mathrm{等}\mathrm{待}\mathrm{时}\mathrm{间}+\mathrm{服}\mathrm{务}\mathrm{时}\mathrm{间}}{\mathrm{服}\mathrm{务}\mathrm{时}\mathrm{间}}$