进程调度：介绍
1、两个指标：
- 周转时间：任务完成时间减去任务到达系统的时间。
T（周转时间）= T（完成时间） − T（到达时间） - 响应时间：从任务到达系统到首次运行的时间。
T（响应时间）= T（首次运行） − T（到达时间）
2、先进先出（FIFO）：
先进先出（First In First Out 或FIFO）调度，有时候也称为先到先服务（First Come First Served 或FCFS）。
护航效应（convoy effect）:一些耗时较少的潜在资源消费者被排在重量级的资源消费者之后。
3、最短任务优先（SJF）:
具体：先运行最短的任务，然后是次短的任务，如此下去。
4、最短完成时间优先（STCF）：
具体：每当新工作进入系统时，它就会确定剩余工作和新工作中，谁的剩余时间最少，然后调度该工作。
5、轮转调度（RR）：
具体：RR 在一个时间片（time slice，有时称为调度量子，scheduling quantum）内运行一个工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直到结束。它反复执行，直到所有任务完成。因此，RR 有时被称为时间切片（time-slicing）。
关于时间片：
时间片长度必须是时钟中断周期的倍数。
时间片长度对于RR 是至关重要的。越短，RR 在响应时间上表现越好。
时间片太短是有问题的：突然上下文切换的成本将影响整体性能。
6、周期时间在STCF中表现良好，在RR中表现差。响应时间则相反。
调度：多级反馈队列（MLFQ）
1、多级反馈队列需要解决两方面的问题：
- 要优化周转时间。
- 要降低响应时间。
2、前提：
MLFQ 中有许多独立的队列（queue），每个队列有不同的优先级（priority level）。任何时刻，一个工作只能存在于一个队列中。MLFQ 总是优先执行较高优先级的工作（即在较高级队列中的工作）。
3、MLFQ 基本规则：
- 规则1：如果A 的优先级 > B 的优先级，运行A（不运行B）。
- 规则2：如果A 的优先级 = B 的优先级，轮转运行A和B。
4、优化一：
- 规则3：工作进入系统时，放在最高优先级（最上层队列）。
-
- 规则4a：工作用完整个时间片后，降低其优先级（移入下一个队列）。
- 规则4b：如果工作在其时间片以内主动释放CPU，则优先级不变。
5、优化二：
- 规则5：经过一段时间S，就将系统中所有工作重新加入最高优先级队列。
6、优化三：
- 改写规则4：一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），就降低其优先级（移入低一级队列）。
调度：比例份额
1、基于一个简单的想法：调度程序的最终目标，是确保每个工作获得一定比例的CPU 时间，而不是优化周转时间和响应时间。
2、彩票调度：
基本概念：彩票数（ticket）代表了进程（或用户或其他）占 有某个资源的份额。一个进程拥有的彩票数占总彩票数的百分比，就是它占有资源的份额。
3、彩票调度的一些基本机制：
- 彩票货币：这种方式允许拥有一组彩票的用户以他们喜欢的某种货币，将彩票分给自己的不同工作。
- 彩票转让：一个进程可以临时将自己的彩票交给另一个进程。
- 彩票通胀：利用通胀，一个进程可以临时提升或降低自己拥有的彩票数量。
4、步长方式实现：
基本思路很简单：当需要进行调度时，选择目前拥有最小行程值的进程，并且在运行之后将该进程的行程值增加一个步长。
注：
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处。