1. 说明
本文档用于自学之总结,资料来源见参见资料,另外有一些来源于网络和作者的理解,不能保证百分之百正确。
本文的目的主要是说明linux操作系统的任务调度方案,关于windows的调度形成独立一章。主要是为了让使用windows的大众有个基本的认识。
2. 进程
2.1 进程
进程:资源管理和调度对象的总体。进程是一个独立的实体,拥有完整的地址空间,包括文本区域(textregion)、数据区域(dataregion)和堆栈(stackregion)。
进程组:每个进程都属于一个进程组。每个进程组有一个领头进程。进程组是一个或多个进程的集合,通常它们与一组作业相关联,可以接受来自同一终端的各种信号。每个进程组都有唯一的进程组ID(整数,也可以存放在pid_t类型中)。进程组由进程组ID来唯一标识。除了进程号外(PID)之外,进程组ID也是一个进程的必备属性之一。进程组是用户空间的概念,和Linux内核无关。
2.2 进程状态
Figure1 linux进程状态图
准备执行(Ready):等待被挑选为执行的进程
实际执行(executing):正在执行的进程
可中断休眠(interruptible):可被事件或信号唤醒的进程
不可中断休眠(uninterruptible):只能被事件唤醒的进程
停止(stopped):挂起,只能被其他进程唤醒的进程。例如被调试程序中止的进程
僵死(Zombie):进程已终止运行,但父进程尚未查询其状态,因为还有些许资源未释放
3. 线程
线程:进程的执行单位。每个进程至少有一个线程。一个进程有多个线程时,线程之间共享进程的地址空间和资源。每个线程有独立的线程栈。
3.1 内核进程
Linux系统内核不明确区分进程和线程。本文中,将Linux内核中的进程称为内核进程。因此,有下述四个概念:
用户进程:用户层面的进程的概念,即传统意义上的进程
用户线程:用户层面的线程概念,即传统意义上的线程
内核进程:内核中的执行实体,作用相当于线程
内核进程组:内核中执行实体集合,用于标识内核进程是否归属于相同的用户进程。
3.2 映射关系
Figure2 linux用户进程内核进程映射
如图,用户空间有2个用户进程,第1个用户进程有3个用户线程,第2个用户进程有1个用户线程。内核空间有3个内核进程,第1和第2个内核进程映射到第1个用户进程,第3个内核进程映射到第4个用户线程。因此,内核进程1和内核进程2归属于同一个内核进程组,第3个内核进程独自组成一个内核进程组。
Linux系统使用Clone() 函数创建内核进程。
内核进程切换时,Linux检查源进程和目标进程的页目录地址(进程使用的内存地址)是否相同,如果相同,则认为是同一个内核进程组的不同进程。
相同内核进程组的进程共享资源,如文件、内存等,相互切换时,不进行上下文切换,只会更换栈空间。
结论:
内核进程相当于用户线程;内核进程组相当于用户进程。用户线程是通过映射获取内核进程提供服务的。
NOTES:
1) 从大到小的概念有:进程组à用户进程及内核进程组à线程(内核进程)
2) 内核进程经常被称作任务(TASK),本文后面使用“任务”来表述内核进程。
4 任务调度
4.1 任务的分类
4.1.1 实时任务
SCHED_FIFO: 先进先出。任务一直执行,除非:1)被更高优先级的任务抢占;2)自行出让CPU;3)阻塞。
SCHED_RR: 时间片轮转。和SCHED_FIFO相同,增加退出执行:时间片耗尽,重新分配时间片,并放到同优先级任务队列尾部。
4.1.2 普通任务
SCHED_OTHER: 分时调度。任务执行,除非:1)被抢占;2)自行出让CPU;3)阻塞;4)时间片耗尽。静态优先级决定时间片长度;动态优先级决定是否调度。
4.2 任务的优先级
Figure3 任务优先级
如上图所示,所有任务优先级范围是[1, 139],其中[1,99]为实时任务的优先级(实时优先级),[100,139]为普通任务的优先级(静态优先级;动态优先级)。优先级越高,其值越小。
4.3 重要概念
SCHED_RR实时任务的时间片长度是一个固定的值(2.6.36内核代码中使用DEF_TIMESLICE=100ms,《深入理解LINUX内核》中的说法是,由实时优先级计算而来。)
实时优先级:实时任务创建时的优先级(实际为创建时的优先级+1000,这里简单处理便于理解)。
静态优先级:普通任务创建时的优先级。
普通任务--基本时间片长度= (140 – 静态优先级)×M。静态优先级<120时,M=20,静态优先级>=120时,M=5。可见,静态优先级越高(值越小),基本时间片长度越大。
普通任务--动态优先级= max(100, min (静态优先级 – bonus + 5, 139))。其中,bonus<5表示惩罚,>5表示奖赏。任务的睡眠时间越长,静态优先级越高(值越小),动态优先级越高(越小)。动态优先级和静态优先级的范围都是[100,139] 。任务执行将降低bonus,从而降低任务的优先级。
活动任务队列和过期任务队列:处于就绪状态的任务分为两个队列:活动任务队列和过期任务队列。时间片耗光的任务将会被放到过期任务队列中。当活动队列中没有可执行任务时,活动任务和过期任务队列互换。
Note:
1) 实时任务没有过期任务队列,它们就绪后,一直处于活动任务中
2) 任务调度的设计原则是,执行少的任务优先调度;优先级高的任务优先调度
3) 每个优先级对应一个优先级队列,因此,一共有140个队列
4) 0号优先级为保留优先级4.4 调度策略
1) 活动任务队列中没有任务,才倒换过期任务队列
2) 没有实时任务,才执行普通任务
3) 永远执行高优先级任务[实时任务的实时优先级、普通任务的动态优先级]
NOTES:
1) 实际的调度可能更为复杂,例如,交互式任务可能会在时间片耗光之后,重新赋值,留在活动任务列表中。
4.5 任务切换策略
1) SCHED_FIFO:如果因为阻塞切换出去,则进入阻塞态,不再继续态列表中,因此不涉及到调度的问题;如果是因为出让CPU或被抢占切换出去,则直接回到队列头中,后面可继续执行。
2) SCHED_RR:阻塞和被抢占时的情形与SCHED_FIFO相同;如果是因为时间片耗尽造成的切换,则任务回到队列尾部。
3) SCHED_OTHER:阻塞和上述相同;被抢占后,其动态优先级会被重新计算,并安排到新的队列尾部;时间片耗尽后,任务不再存在于活动任务队列中,而是被放到过期任务队列中。必须等到过期任务队列切换为活动任务队列,才可能被重新调度。
5 多CPU负载均衡
每个CPU拥有独立的队列,存在专用的负载均衡算法,可实现多CPU之间的进程调配。本文从略。
6 实时性
实时操作系统一般使用类似Deadline Scheduling等方法保证实时任务能够按时间完成。但linux中并未见到类似处理。虽然Linux中的实时进程调度算法能够起到优先执行的目的,但是,并不能保证满足实时性要求。因此,一般认为Linux操作系统不是实时操作系统。
7 Windows的调度方法
一般不能详细描述windows系统的调度算法,因为MS认为这种算法对于程序而言越模糊越好。MS不保证未来的调度算法不发生重大变化,因而不希望任何应用利用该调度算法的特性。
Windows针对线程进行调度,进程仅是一个容器。
7.1 优先级
一般不能详细描述windows系统的调度算法,因为MS认为这种算法对于程序而言越模糊越好。MS不保证未来的调度算法不发生重大变化,因而不希望任何应用利用该调度算法的特性。
Windows针对线程进行调度,进程仅是一个容器。
Figure5 进程优先级的分类
Figure6 线程优先级的分类
优先级范围0~31。和linux相反,优先级越高,其值越大。
7.1.1 实时优先级
16~31为实时优先级。这里的实时优先级和普通意义上的实时是不同的,它并不能保证线程的执行时间,只是说它的优先级很高,执行时,可以忽略I/O设备、网络设备、UI界面的事件。
7.1.2 普通优先级
1~15为普通优先级。普通线程的优先级是动态的,但它有一个初始优先级。
进程基本优先级范围为1~15。进程内的线程,其优先级按上表,有表示最高、高于正常、正常、低于正常、最低,其线程基本优先级对应为2、1、0、-1、-2,可认为是对进程优先级的加权处理。
线程初始优先级 = 进程基本优先级 + 线程基本优先级。
线程执行过程中,其优先级会动态调整,但不会低于线程优先级,也不会高于15。如图:Figure7 线程优先级实例
7.1.3 保留优先级
0为保留优先级,用途为zero page thread,即Idle进程。它将系统所有的空闲RAM页面置0。
7.1.4 线程的实际优先级范围
实际中,进程/线程的优先级并非所有级别都可以使用。如下图表:
Figure8 进程-线程可能的优先级1
Figure9 进程-线程可能的优先级2
可见:
1)进程的基本优先级,只有4、6、8、10、13、24可用。
2)线程的优先级,可能的值的范围均在上述范围之内。
3)优先级1和优先级31是特殊的优先级。
4)17、18、19、20、21、27、28、29、30等优先级是用户不可用的,只有内核方式执行的设备驱动程序才可能使用这些优先级。
7.2 调度
抢占式:只要存在高优先级线程,低优先级线程就会被抢占。但不用担心饥饿的发生,因为windows中的绝大部分线程是不能调度的。
调度的触发:抢占、时间片用完。
动态优先级提升:
•I/O操作完成
•信号量或事件等待结束
•前台进程中的线程完成一个等待操作
•由于窗口活动而唤醒图形用户接口线程
•线程处于就绪状态超过一定时间,但没能进入运行状态(处理机饥饿)
8 参考资料
《深入理解LINUX内核》
《OperatingSystem – Internals and Design Principle》
《windows核心编程(windowsvia C/C++)》