调度策略
“调度策略” 为什么会发生调度? 因为cpu是有限的,而操作系统上的进程很多,所以操作系统需要平衡各个进程的运行时间 比如说有的进程运行时间已经很长了,已经占用了cpu很长时间了,这个时候操作系统要公平 就会换下一个需要运行的进程。 调度策略 抢占 vs 协作 从调度机制上来讲,调度可以分为抢占式和协作式。 非抢占, 协作 非抢占方式是指一旦将调度资源 (如 CPU) 分配给某任务后,便让该任务一直执行,直到该任务完成或阻塞或主动让出CPU控制权,非抢占调度又称为协作式调度,它实现简单,并且对共享资源的访问也更安全(如允许使用不可重入函数)。非抢占算法常见的如 FIFO,STCF(Short time to complete first)等。 抢占 抢占方式则允许调度程序根据某种规则,剥夺当前进程的调度资源,将其分配给其它进程。常见的抢占策略有: 基于时间片 基于时间片: 给每个进程分配时间片,当时间片用完后,则停止该进程重新调度下一个进程,这种均分CPU 的算法,又叫轮转调度算法 基于优先级 基于优先级: 给每个进程分配一个优先级,一旦出现一个优先级更高的进程,则停止当前进程并切换到该高优先级进程,这种调度算法又叫优先级抢占 轮转调度和优先级抢占结合: 即相同优先级的进程使用轮转调度,如果遇到更高优先级的进程,则可抢占CPU。现代 OS 如 Linux 通常都使用这种混合调度策略。 PS: 基于优先级抢占容易出现优先级反转的问题: 优先级低的任务持有一个被优先级高的任务所需要的共享资源,这种情况下,优先级低的任务有资源而得不到CPU,优先级高的资源有CPU而得不到资源,从而阻塞(导致其它中优先级的任务获得执行)或者忙等(可能永远无法获得资源)。 解决优先级反转的方案: 给临界区一个高优先级,所有进入该临界区的任务将获得该高优先级,避免其被随意抢占 当高优先级任务在等待低优先级进程持有资源时,低优先级进程将暂时获得高优先级进程的优先级,VxWorks采用的方式。 禁止中断,也就是在临界区不可被抢占,Linux 采用的就是这种方式,在 thread_info.preeempt_count 记录每个进程当前持锁计数。 另外,调度器是不能在进程指令流的任意一点执行打断的,因为进程可能此时正在做任何事情,如系统调用,死循环,锁操作等,要实现任意状态的可抢占性代价是很大的,需要 OS 和 App 的通力配合,特别是在涉及在内核态的时候,目前所有OS都不能在进程执行的任意点进行抢占。只是说不断让抢占区更大,抢占点尽可能地密集。 实时 vs 非实时 从系统需求或用户角度而言,调度系统可以分为实习系统和非实时系统。 在实时操作系统中,系统必须在特定的时间内完成指定的应用。实时通常分为软实时(soft real-time)和硬实时(hard real-time),硬实时是指系统要有确定的最坏情况下的服务时间,即对于事件的响应时间截止期限无论如何都必须得到满足,通常应用在军工航天领域。而软实时只提供统计意义上的实时,比如应用要求在95%的情况下都会确保在规定的时间内执行某个任务,而不一定要求100%。实时系统通常采用抢占调度,实现一个硬实时系统的代价是很高的,要做到进程可以在任意时刻被抢占,在现代OS上来讲,基本是不可能的,因为OS的很多系统调用都是不可被打断的,并且很多操作具备时间的随机性,比如 CPU Cache Miss,Page Fault,CPU Branch Predictor 等等。 BTW, 为什么现代OS不尽可能地去掉这些不稳定性(如虚拟内存,CPU多级Cache,分支预测等),从而为成为实时系统打好基础呢?对桌面操作系统而言,对实时性的要求没有那么高,应用切换偶尔卡一卡并无大碍,桌面系统更关注的一方面是对内核的统一抽象,屏蔽硬件差异化,接口丰富易用,让上层应用易于开发,比如虚拟内存,文件描述符等。另一方面,桌面系统在选择牺牲部分的实时性来提高吞吐量,比如多级Cache,分支预测。因此尽管如 Linux 这类桌面系统支持实时优先级和多种调度机制,但仍然最多只能实现软实时,这是设计目标决定的。 而非实时系统,则没有对最低任务处理时延的要求,比如简单的非抢占调度模型。 ...