linux是以线程为单位进行CPU调度的。所以下面的描述中所说的线程和进程从CPU调度角度来说是等效。
Linux进程优先级:
Priority。进程的优先级是操作系统自己给定并且动态调整的。用户可以通过nice值来调整实际优先级。
CentOS6.2(kernel 2.6.32)进程的默认优先级是80。
Nice value:-20到+19。Real priority = priority + nice,top中的PRI这一列是Real priority。
Real-time priority:0到99。非实时线程优先级为100到139。所以linux进程 总共140个优先级。
整体调度原始思路可以近似理解为根据优先级分配时间量,线程轮转(round robin)使用CPU分配到的时间量。
Linux内核2.6中流行的调度器是O(1)调度器。它维护两个数组。一个存放活动进程,另一个存放过期进程,每个数组有140个链表头。当活动数组中的进程都执行了之后,活动数组变成过期数组,过期数组变成活动数组。然后继续执行。另外,会给等到了输入的I/O和交互式进程提高优先级,以及时执行。并且降低占用CPU时间长的进程的优先级。但是因为是通过启发式的方法来确定一个任务是交互式任务,所以在处理交互式任务时效果并不好。
Linux内核2.6.23中引入CFS (Completely Fair Scheduler)算法。每个进程有一个vruntime,优先级越高的进程vruntime增加的就越慢,总是调用vruntime小的进程。这样即可以保证高优先级进程得到更多调度,同时低优先级进程也不会饿死。
CFS使用红黑树作为调度队列的数据结构。根据任务在CPU上的运行时间长短将其有序地排列在树中,这个时间是vruntime。左侧的节点对应迄今为止CPU上运行时间少的任务,所以左侧的任务会更早被调度。根据实际运行时间,按需调整节点在树中的位置。查找和插入的时间复杂度为O(logn)。但是其实除了查找最左侧节点外,很少执行其他查找,而最左侧的节点指针始终被缓存,所以查找效率非常高。
CFS算法并没有尝试去识别交互式任务,因为交互式任务使用CPU时间少,即vruntime小,所以一旦有了输入,就会被优先执行。这样就保证了响应速度。
多核平台每个core一个调度队列。调度器保证各个core的负载是均衡的。
调度器只考虑ready的线程。其它线程在sleep队列中。
 

Logo

更多推荐