它的基本思想很明确,每个进程都被赋予一个优先级,优先级高的进程优先运行。
多级队列最早使用优先级调度的系统是 CTSS(Compatible TimeSharing System)。CTSS 在每次切换前都需要将当前进程换出到磁盘,并从磁盘上读入一个新进程。为 CPU 密集型进程设置较长的时间片比频繁地分给他们很短的时间要更有效(减少交换次数)。另一方面,如前所述,长时间片的进程又会影响到响应时间,解决办法是设置优先级类。属于最高优先级的进程运行一个时间片,次高优先级进程运行 2 个时间片,再下面一级运行 4 个时间片,以此类推。当一个进程用完分配的时间片后,它被移到下一类。
最短进程优先最短进程优先是根据进程过去的行为进行推测,并执行估计运行时间最短的那一个。假设每个终端上每条命令的预估运行时间为 T0,现在假设测量到其下一次运行时间为 T1,可以用两个值的加权来改进估计时间,即aT0+ (1- 1)T1。通过选择 a 的值,可以决定是尽快忘掉老的运行时间,还是在一段长时间内始终记住它们。当 a = 1/2 时,可以得到下面这个序列
![image-20200220120452410](/Users/mr.l/Library/Application Support/typora-user-images/image-20200220120452410.png)
可以看到,在三轮过后,T0 在新的估计值中所占比重下降至 1/8。
保证调度一种完全不同的调度方法是对用户做出明确的性能保证。一种实际而且容易实现的保证是:若用户工作时有 n 个用户登录,则每个用户将获得 CPU 处理能力的 1/n。类似地,在一个有 n 个进程运行的单用户系统中,若所有的进程都等价,则每个进程将获得 1/n 的 CPU 时间。
彩票调度对用户进行承诺并在随后兑现承诺是一件好事,不过很难实现。但是存在着一种简单的方式,有一种既可以给出预测结果而又有一种比较简单的实现方式的算法,就是 彩票调度(lottery scheduling)算法。
其基本思想是为进程提供各种系统资源(例如 CPU 时间)的彩票。当做出一个调度决策的时候,就随机抽出一张彩票,拥有彩票的进程将获得该资源。在应用到 CPU 调度时,系统可以每秒持有 50 次抽奖,每个中奖者将获得比如 20 毫秒的 CPU 时间作为奖励。
公平分享调度到目前为止,我们假设被调度的都是各个进程自身,而不用考虑该进程的拥有者是谁。结果是,如果用户 1 启动了 9 个进程,而用户 2 启动了一个进程,使用轮转或相同优先级调度算法,那么用户 1 将得到 90 % 的 CPU 时间,而用户 2 将之得到 10 % 的 CPU 时间。
为了阻止这种情况的出现,一些系统在调度前会把进程的拥有者考虑在内。在这种模型下,每个用户都会分配一些CPU 时间,而调度程序会选择进程并强制执行。因此如果两个用户每个都会有 50% 的 CPU 时间片保证,那么无论一个用户有多少个进程,都将获得相同的 CPU 份额。
实时系统中的调度实时系统(real-time) 是一个时间扮演了重要作用的系统。实时系统可以分为两类,硬实时(hard real time) 和 软实时(soft real time) 系统,前者意味着必须要满足绝对的截止时间;后者的含义是虽然不希望偶尔错失截止时间,但是可以容忍。
实时系统中的事件可以按照响应方式进一步分类为周期性(以规则的时间间隔发生)事件或 非周期性(发生时间不可预知)事件。一个系统可能要响应多个周期性事件流,根据每个事件处理所需的时间,可能甚至无法处理所有事件。例如,如果有 m 个周期事件,事件 i 以周期 Pi 发生,并需要 Ci 秒 CPU 时间处理一个事件,那么可以处理负载的条件是
只有满足这个条件的实时系统称为可调度的,这意味着它实际上能够被实现。一个不满足此检验标准的进程不能被调度,因为这些进程共同需要的 CPU 时间总和大于 CPU 能提供的时间。
下面我们来了解一下内存管理,你需要知道的知识点如下