ULK3 学习笔记（七）

CHAPTER 7 PROCESS SCHEDULING

Erratic

adj.

无确定路线, 不稳定的, 奇怪的

n.

古怪的人, 漂泊无定的人

 

inhibit

抑制, 约束, [化][医]抑制

 

iterative

adj.

重复的, 反复的, [数]迭代的

n.

反复体

 

这一章主要讲的是进程调度，调度算法一类的。而进程切换时候CPU要做什么在3章已经讲了。

  调度策略里面，传统的unix操作系统必须处理一些互相之间可能有冲突的目标。

  1进程能快速的响应。2后台工作有高的吞吐量。3避免进程饥饿现象。(得不到CPU)。4协调高-低优先级的进程。等等。

  Linux的调度是基于时间分配time sharing技术。CPU时间被分成slices。

  时间分配是依靠定时器中断的。对进程来说是透明的。也就是不用在程序里面加上附加的功能来确保CPU的时间分配。

  在linux里面，进程的优先级是动态的。也就是进程长时间没有被激活了就可能增加优先级，而进程运行了很长的时间就有可能降低优先级。

  进程可以分为占用I/O的或者占用CPU的。I/O-bound和CPU-bound（不知道这样翻译对不对：））。

  进程可以分成三类：

  1 互动进程interactive processes：就是这些进程需要经常和用户交流，所以会花很多时间来等待按键或者鼠标动作。这种进程必须很快的被响应（很明显三）而且响应的间隔必须比较固定，不然的话可能erratic，就是系统对于用户来说可能会表现的不稳定。

  2 批处理进程 batch processes： 这些不需要跟用户互动，不需要快速反应，所以会被scheduler penalize。

  3 实时进程 real-time processes：这种进程永远不会被低优先级的进程block，而且需要很小的响应时间。比如视频和音频应用。

  实时进程可以很容易的被linux认出来，但是互动式和批处理的任务不是那么容易被分出来。2.6里面用一种复杂的启发式算法来分辨进程属于互动的行为还是批处理的行为。

  （这种分辨在进程里面是怎么体现出来的呢？在process descriptor里面有标识么？）

进程抢占

  Linux进程是可抢占的。就是如果一个进程处于TASK_RUNNING状态情况下，一旦发现它优先级比CURRENT高，那么就会抢占当前进程。当然，进程的时间权值quantum到了的话，那么thread_info里面的TIF_NEED_RESCHED就会set，这样的话timer interrupt handler完了之后就会执行调度。

Quantum 额度需要多长？

  答案是不能长了也不能短了。。。

  长了就会使多个进程运行起来不够连续，短了就会有大部分时间不是在处理进程，而是在进行切换。但是长的额度会减少互动进程的响应时间这个说法是错误的。（因为进程可以抢占，自己想为什么）

  Linux的设计原则是在满足好的系统响应时间的情况下，额度越长越好。

 调度算法

  老版本里面的调度算法非常的简单，  就是在每个进程切换的时候，内核检查运行队列里面的进程，计算他们的优先级，选出最好的来运行。这样的话，如果运行队列里面的进程很多，那么选择最好的进程的时间就会很大

  2.6里面就非常的复杂。进程的选择时间是固定的，不依赖于有多少个进程。这种新的算法也能更好的分辨出interactive processes和batch processes。

  Linux里面的每个进程都可能被分成以下几个scheduling classes：

  1 SCHED_FIFO 先进先出的real-time process。如果没有更高的优先级出现，那么这个进程就想运行多久就运行多久。

  2 SCHED_RR，round robin real-time process。如果这个进程被换出，那么它就会被加到队列的最后。

  3 SCHED_NORMAL 常规的，time-shared进程。

常规进程的调度

  内核给常规进程提供100-139的静态优先级。Nice()和setpriority()两个系统调用都可以改变静态优先级。

  基本时间额度。静态优先级决定进程的基本时间额度，具体的方程请参看p263

  动态优先级和average sleep time：动态优先级也是100-139。动态优先级是调度程序真正用来查看选择那个进程运行的。它与静态优先级有关。具体方程参看p264

  里面有一个bouns的参数，这个是跟sleeping time有关的，这个可以影响到优先级。

  Active 和expired processes

Active process是可运行进程里面时间额度还没有用完的，可以运行的进程

Expired process是可运行进程里面的时间额度已经用完的，直到所有active processes都expire以后才可以运行的。

但是schema还要复杂一些，因为interactive的进程每次额度到了都会自动补充，所以一直会在active里面，但是如果expire里面有进程已经等了很久了或者expire里面的进程有比这个interactive进程大的，那么interactive进程也会从active里面移到expire里面。所以最终这个active会变空，那么expired队列里面的进程就可以执行了。

实时进程的调度

  每个实时进程都有一个从1-99的实时优先级。实时进程会一直抑制实时优先级低的进程（都相对于实时的进程来说）与常规进程不同的是，实时进程没有expire的状态，都是active的。

  实时进程在一下情况下会被另一个进程取代：

  1这个进程被另一个优先级更高的进程抢占了  preempt

  2这个进程执行了block的操作。然后就被sleep，就是变成TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE状态了

  3这个进程被停止了 TASK_STOPPED或TASK_TRACED，或者被kill了TASK_ZOMBIE或TASK_DEAD

  4这个进程调用了sched_yield()系统调用，自动的选择换出了。

  5这个进程是round robin real-time（SCHED_RR），而且它的时间额度到了。（对于FIFO来说，永远没有时间额度这个概念，知道有个更高优先级的进程出现，它才会被换出）

  Nice（）和setpriority（）系统调用当用在round robin real-time进程下面的时候，只是改变基本的时间额度，而不改变优先级。

调度里面要用到的数据结构

  This_rq（）宏用来产生当前CPU的运行队列的地址。

  运行队列的数据结构是runqueue的数据结构  具体内容参看泡p267

  注意 expired_timestamp，timestamp_last_tick，curr ，prev_mm，active，expired，arrays

Best_expired_prio这几个域。

  Array里面有两个prio_array_t的数据结构，对应着一个active队列和一个expired队列，用active和expire表明哪个是哪个。

  Process descriptor 里面有些是关于调度的，具体的参看p269

  如果新进程fork出来了，那么就会把它parent的时间片/2给它，parent也只剩slice/2。

调度程序里面要用到的一些函数

  Scheduler_tick() 保持当前进程的time_slice更新

  Try_to_wake_up() 唤醒一个进程

  Recalc_task_prio() 更新一个进程的动态优先级

  Schedule（）选择一个新的进程来执行

  Load_balance() 用来保持多处理器的负载平衡

 

  分别介绍：

  Scheduler_tick()：在定时中断的时候调用。主要功能：减少时间片。然后检查是否时间额度已经到了，对于不同调度策略的进程来说，有不同的方法：

             1更新实时进程的时间片；FIFO没有必要更新，RR的话，--time_slice，如果额度到期的话，重置slice，set_tsk_need_resched(current)，从队列中删除这个进程，再重新添加到这个队列的队尾。

             2更新常规进程的时间片；1--time_slice，2.如果额度到期的话，那么从actvie队列里面移除这个进程。TIF_NEED_RESCHED置位。更新当前进程的动态优先级。重置time_slice，将这个队列放入active或者expire的队列里面。

  Try_to_wake_up()：将停止和睡眠的进程回复成TASK_RUNNING，然后加入到运行队列。

  Schedule（）func：在内核进程中，这个函数会被立刻的调用，或则被延时调用。

                   立即调用：调度程序在当前进程必须马上被block的时候立即调用。将当前进程插入到等待队列。把当前进程的state变了。调用schedule（），检查资源是否可用，不能就重复上面的步骤。

                   调度程序也会在许多执行重复任务的设备驱动上执行。？

                   延时调用：集中情况：1当用完时间额度，调用scheduler_tick（）的时候 2.当进程醒来以后，发现比当前进程优先级高的时候，在try_to_wake_up（）中。3.当sched_setscheduler（）系统调用的时候。

 

还有一些关于调度的系统调用system calls

  nice（），sched_getscheduler（），sched_setscheduler（），sched_yield()，sched_get_priority_min()，sched_get_priority_max()，sched_rr_get_interval()，sched_getparam()，shced_setparam()。

  具体的含义请参见p292