欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

第四章 进程的调度

程序员文章站 2022-03-07 13:21:48
...

1. 什么是调度

现在的操作系统都是多任务的，为了能让更多的任务能同时在系统上更好的运行，需要一个管理程序来管理计算机上同时运行的各个任务（也就是进程）。

这个管理程序就是调度程序，它的功能说起来很简单：

  • 决定哪些进程运行，哪些进程等待
  • 决定每个进程运行多长时间
  • 此外，为了获得更好的用户体验，运行中的进程还可以立即被其他更紧急的进程打断。

总之，调度是一个平衡的过程。一方面，它要保证各个运行的进程能够最大限度的使用CPU(即尽量少的切换进程，进程切换过多，CPU的时间会浪费在切换上)；另一方面，保证各个进程能公平的使用CPU(即防止一个进程长时间独占CPU的情况)。

2.进程优先级

进程的优先级有2种度量方法，一种是nice值，一种是实时优先级。

  • nice值的范围是-20～+19，值越大优先级越低，也就是说nice值为-20的进程优先级最大。
  • 实时优先级的范围是0～99，与nice值的定义相反，实时优先级是值越大优先级越高。 
    实时进程都是一些对响应时间要求比较高的进程，因此系统中有实时优先级高的进程处于运行队列的话，它们会抢占一般的进程的运行时间。

进程的2种优先级会让人不好理解，到底哪个优先级更优先？一个进程同时有2种优先级怎么办？

对于第一个问题，到底哪个优先级更优先？ 
　　答案是实时优先级高于nice值，在内核中，实时优先级的范围是 0～MAX_RT_PRIO-1 MAX_RT_PRIO的定义参见 include/linux/sched.h

1611 #define MAX_USER_RT_PRIO        100
1612 #define MAX_RT_PRIO             MAX_USER_RT_PRIO
  • 1
  • 2

nice值在内核中的范围是 MAX_RT_PRIO～MAX_RT_PRIO+40 即 MAX_RT_PRIO～MAX_PRIO

1614 #define MAX_PRIO                (MAX_RT_PRIO + 40)
  • 1

第二个问题，一个进程同时有2种优先级怎么办？ 
　　答案很简单，就是一个进程不可能有2个优先级。一个进程有了实时优先级就没有Nice值，有了Nice值就没有实时优先级。

我们可以通过以下命令查看进程的实时优先级和Nice值：(其中RTPRIO是实时优先级，NI是Nice值)

$ ps -eo state,uid,pid,ppid,rtprio,ni,time,comm
S   UID   PID  PPID RTPRIO  NI     TIME COMMAND
S     0     1     0      -   0 00:00:00 systemd
S     0     2     0      -   0 00:00:00 kthreadd
S     0     3     2      -   0 00:00:00 ksoftirqd/0
S     0     6     2     99   - 00:00:00 migration/0
S     0     7     2     99   - 00:00:00 watchdog/0
S     0     8     2     99   - 00:00:00 migration/1
S     0    10     2      -   0 00:00:00 ksoftirqd/1
S     0    12     2     99   - 00:00:00 watchdog/1
S     0    13     2     99   - 00:00:00 migration/2
S     0    15     2      -   0 00:00:00 ksoftirqd/2
S     0    16     2     99   - 00:00:00 watchdog/2
S     0    17     2     99   - 00:00:00 migration/3
S     0    19     2      -   0 00:00:00 ksoftirqd/3
S     0    20     2     99   - 00:00:00 watchdog/3
S     0    21     2      - -20 00:00:00 cpuset
S     0    22     2      - -20 00:00:00 khelper
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

３. Linux下的用户态抢占

抢占：高优先级进程抢占低优先级进程占有CPU 
在kernel返回用户态(user-space)时，并且need_resched标志为1时，scheduler被调用，这就是用户态抢占。当kernel返回用户态时，系统可以安全的执行当前的任务，或者切换到另外一个任务。当中断处理例程或者系统调用完成后，kernel返回用户态时，need_resched标志的值会被检查，假如它为1，调度器会选择一个新的任务并执行。中断和系统调用的返回路径(return path)的实现在entry.S中(entry.S不仅包括kernel entry code，也包括kernel exit code)。

4.Linux下的内核态抢占的设计

在2.6 kernel以前，kernel code(中断和系统调用属于kernel code)会一直运行，直到code被完成或者被阻塞(系统调用可以被阻塞)。在 2.6 kernel里，Linux kernel变成可抢占式。当从中断处理例程返回到内核态(kernel-space)时，kernel会检查是否可以抢占和是否需要重新调度。kernel可以在任何时间点上抢占一个任务(因为中断可以发生在任何时间点上，中断返回是抢占时机之一)，只要在这个时间点上kernel的状态是安全的、可重新调度的。

4.1 内核态需要抢占的触发条件（标记）

内核提供了一个need_resched标志(这个标志在任务结构thread_info中)来表明是否需要重新执行调度。

4.2 何时设置调度标记

  • 时钟中断处理例程检查当前任务的时间片，当任务的时间片消耗完时，scheduler_tick()函数就会设置need_resched标志；
  • 信号量、等到队列、completion等机制唤醒时都是基于waitqueue的，而waitqueue的唤醒函数为default_wake_function，其调用try_to_wake_up将被唤醒的任务更改为就绪状态并设置need_resched标志。
  • 设置用户进程的nice值时，可能会使高优先级的任务进入就绪状态；
  • 改变任务的优先级时，可能会使高优先级的任务进入就绪状态；
  • 新建一个任务时，可能会使高优先级的任务进入就绪状态；
  • 对CPU(SMP)进行负载均衡时，当前任务可能需要放到另外一个CPU上运行；

set_tsk_need_resched()：设置指定进程中的need_resched标志 
clear_tsk need_resched()：清除指定进程中的need_resched标志 
need_resched()：检查need_ resched标志的值;如果被设置就返回真，否则返回假

4.3 抢占发生的时机(何时检查可抢占条件)

  • 当一个中断处理例程退出，在返回到内核态时(kernel-space)。这是隐式的调用schedule()函数，当前任务没有主动放弃CPU使用权，而是被剥夺了CPU使用权。
  • 当kernel code从不可抢占状态变为可抢占状态时(preemptible again)。也就是preempt_count从正整数变为0时。这也是隐式的调用schedule()函数。
  • 一个任务在内核态中显式的调用schedule()函数。任务主动放弃CPU使用权。
  • 一个任务在内核态中被阻塞，导致需要调用schedule()函数。任务主动放弃CPU使用权。

4.4 什么时候不会抢占

有几种情况Linux内核不应该被抢占，除此之外，Linux内核在任意一点都可被抢占。这几种情况是：

  • 处于中断上下文 
    • 内核正进行中断处理。在Linux内核中进程不会抢*断(中断只能被其他中断中止、抢占，进程不能中止、抢*断)，在中断例程中不允许进行进程调度。进程调度函数schedule()会对此作出判断，如果是在中断中调用，会打印出错信息。
    • 内核正在进行中断上下文的Bottom Half(中断的下半部)处理。硬件中断返回前会执行软中断，此时仍然处于中断上下文中。
  • 持有锁： 
    内核的代码段正持有spinlock自旋锁、writelock/readlock读写锁等锁，处干这些锁的保护状态中。内核中的这些锁是为了在SMP系统中短时间内保证不同CPU上运行的进程并发执行的正确性。当持有这些锁时，内核不应该被抢占，否则由于抢占将导致其他CPU长期不能获得锁而死等。Linux在每个每个任务的thread_info结构中增加了preempt_count变量作为preemption的计数器。这个变量初始为0，当加锁时计数器增一，当解锁时计数器减一。抢占时机到来时会检查preemption是否为0而决定是否发生抢占。
  • 正在执行调度 
    内核正在执行调度程序scheduler。抢占的原因就是为了进行新的调度，没有理由将调度程序抢占掉再运行调度程序。

4.5 禁用/使能可抢占条件的操作

　对preempt_count操作的函数有add_preempt_count()、sub_preempt_count()、inc_preempt_count()、dec_preempt_count()。 
　　使能可抢占条件的操作是preempt_enable()，它调用dec_preempt_count()函数，然后再调用preempt_check_resched()函数去检查是否需要重新调度。 
　　禁用可抢占条件的操作是preempt_disable()，它调用inc_preempt_count()函数。 
　　在内核中有很多函数调用了preempt_enable()和preempt_disable()。比如spin_lock()函数调用了preempt_disable()函数，spin_unlock()函数调用了preempt_enable()函数。

5如何选择下一个要执行的程序

Linux上的调度算法是不断发展的，在2.6.23内核以后，采用了“完全公平调度算法”，简称CFS。 
CFS算法在分配每个进程的CPU时间时，不是分配给它们一个绝对的CPU时间，而是根据进程的优先级分配给它们一个占用CPU时间的百分比。 
比如ProcessA(NI=1)，ProcessB(NI=3)，ProcessC(NI=6)，在CFS算法中，分别占用CPU的百分比为：ProcessA(10%)，ProcessB(30%)，ProcessC(60%) 
因为总共是100%，ProcessB的优先级是ProcessA的3倍，ProcessC的优先级是ProcessA的6倍。

Linux上的CFS算法主要有以下步骤：(还是以ProcessA(10%)，ProcessB(30%)，ProcessC(60%)为例)

  • 计算每个进程的vruntime(注1)，通过update_curr()函数更新进程的vruntime。
  • 选择具有最小vruntime的进程投入运行。（注2）
  • 进程运行完后，更新进程的vruntime，转入步骤2) （注3）

注1. 这里的vruntime是进程虚拟运行的时间的总和。vruntime定义在：kernel/sched_fair.c 文件的 struct sched_entity 中。 
注2. 这里有点不好理解，根据vruntime来选择要运行的进程，似乎和每个进程所占的CPU时间百分比没有关系了。

  1. 比如先运行ProcessC，(vr是vruntime的缩写)，则10ms后：ProcessA(vr=0)，ProcessB(vr=0)，ProcessC(vr=10)
  2. 那么下次调度只能运行ProcessA或者ProcessB。(因为会选择具有最小vruntime的进程)

长时间来看的话，ProcessA、ProcessB、ProcessC是公平的交替运行的，和优先级没有关系。而实际上vruntime并不是实际的运行时间，它是实际运行时间进行加权运算后的结果。

比如上面3个进程中ProcessA(10%)只分配了CPU总的处理时间的10%，那么ProcessA运行10ms的话，它的vruntime会增加100ms。 
以此类推，ProcessB运行10ms的话，它的vruntime会增加(100/3)ms,ProcessC运行10ms的话，它的vruntime会增加(100/6)ms。

实际的运行时，由于ProcessC的vruntime增加的最慢，所以它会获得最多的CPU处理时间。上面的加权算法是我自己为了理解方便简化的，Linux对vruntime的加权方法还得去看源码^-^

注3.Linux为了能快速的找到具有最小vruntime，将所有的进程的存储在一个红黑树中。这样树的最左边的叶子节点就是具有最小vruntime的进程，新的进程加入或有旧的进程退出时都会更新这棵树。 
其实Linux上的调度器是以模块方式提供的，每个调度器有不同的优先级，所以可以同时存在多种调度算法。 
每个进程可以选择自己的调度器，Linux调度时，首先按调度器的优先级选择一个调度器，再选择这个调度器下的进程。

6.调度相关的系统调用

调度相关的系统调用主要有2类：

  • 与调度策略和进程优先级相关 (就是上面的提到的各种参数，优先级，时间片等等) - 下中的前8个
  • 与处理器相关 - 下中的最后3个
系统调用 描述
nice() 设置进程的nice值
sched_setscheduler() 设置进程的调度策略，即设置进程采取何种调度算法
sched_getscheduler() 获取进程的调度算法
sched_setparam() 设置进程的实时优先级
sched_getparam() 获取进程的实时优先级
sched_get_priority_max() 获取实时优先级的最大值，由于用户权限的问题，非root用户并不能设置实时优先级为99
sched_get_priority_min() 获取实时优先级的最小值，理由与上面类似
sched_rr_get_interval() 获取进程的时间片
sched_setaffinity() 设置进程的处理亲和力，其实就是保存在task_struct中的cpu_allowed这个掩码标志。该掩码的每一位对应一个系统中可用的处理器，默认所有位都被设置，即该进程可以再系统中所有处理器上执行。用户可以通过此函数设置不同的掩码，使得进程只能在系统中某一个或某几个处理器上运行。
sched_getaffinity() 获取进程的处理亲和力
sched_yield() 暂时让出处理器

本文主要整合自： 
http://www.cnblogs.com/wang_yb/archive/2012/09/04/2670564.html 
http://blog.sina.com.cn/s/blog_502c8cc401012pxj.html

相关标签： 内核

上一篇： php中MySQL、MySQLi、PDO的区别有哪些？

下一篇： PHP如何使用Ds\Queue pop()函数？

推荐阅读