首页 > 代码库 > 第四章 進程調度

第四章 進程調度

可以參考《深入Linux內核架構》第二章閱讀筆記

1. 調度程序的職責

  • 負責決定那個進程投入運行,何時運行以及運行多長時間

  • 在一組處於可運行狀態的進程中選擇一個來執行,這是調度程序的基本工作

2. 多任務操作系統就是能同時併發地交互執行多個進程的操作系統

3. 多任務系統分類

  • 非搶佔式多任務:除非進程自己主動停止運行,否則它會一直執行。進程主動掛起自己的操作稱爲讓步(yielding)。

  • 搶佔式多任務:Linux採用了這種。搶佔的含義:由調度程序來決定什麼時候停止一個進程運行,以便其他進程能夠得到執行機會,這個強制的掛起動作就叫做搶佔。進程在被搶佔之前能夠運行的時間是預先設置好的,稱爲進程的時間片(timeslice)。

4. I/O消耗型和处理器消耗型的进程

  • I/O消耗型:经常处于可运行狀態,但通常運行時間很短,因爲它在等待更多的IO請求時最後都會阻塞。比如多數用戶圖形界面程序都屬IO密集型。

  • 處理器消耗型:把時間大多用在執行代碼上。除非被搶佔,否則它們通常都一直不停執行,因爲它們沒有太多的IO需求。

注:有的進程既屬於IO消耗型,也是處理器消耗型。如字處理器。

5. Linux系統爲了保證交互式應用和桌面系統的性能,更傾向於優先調度IO消耗型進程。

6. 調度程序總是選擇時間片未用盡而且優先級最高的進程運行。

7. Linux採用的兩種優先級:

  • nice值:範圍是從-20到19,值越大,優先級越低。在Linux系統中,nice值代表了時間片的比例,使用命令ps -el可以查看標記NI的那列。

  • 實時優先級:範偉是從0到99,值越大,優先級越高。任何實時進程的優先級都高於普通進程。使用命令

    1. ps -eo pid,tid,class,rtprio,ni,pri,psr,pcpu,stat,wchan:14,comm

    可以查看實時優先級,在RTPRIO列下,如果爲“-”,表示該進程不是實時進程。

  • 注:實時優先級和nice優先級是兩個互不相交的範疇。從剛纔的命令也可以看出,實時進程沒有nice值,而有nice值的進程一定不是實時進程。

    1.  PID   TID CLS RTPRIO  NI PRI PSR %CPU STAT WCHAN          COMMAND
    2.    1     1 TS       -   0  19   0  0.0 Ss   -              init
    3.    2     2 TS       -   0  19   5  0.0 S    -              kthreadd
    4.    3     3 TS       -   0  19   0  0.0 S    -              ksoftirqd/0
    5.    5     5 TS       - -20  39   0  0.0 S<   -              kworker/0:0H
    6.    7     7 TS       -   0  19   2  0.2 S    -              rcu_sched
    7.    8     8 TS       -   0  19   0  0.0 S    -              rcu_bh
    8.    9     9 TS       -   0  19   1  0.0 S    -              rcuos/0
    9.   10    10 TS       -   0  19   0  0.0 S    -              rcuob/0
    10.   11    11 FF      99   - 139   0  0.0 S    -              migration/0
    11.   12    12 FF      99   - 139   0  0.0 S    -              watchdog/0
    12.   13    13 FF      99   - 139   1  0.0 S    -              watchdog/1
    13.   14    14 FF      99   - 139   1  0.0 S    -              migration/1
    14.   15    15 TS       -   0  19   1  0.0 S    -              ksoftirqd/1
    15.   17    17 TS       - -20  39   1  0.0 S<   -              kworker/1:0H

8. 時間片是一個數值,它表明進程在被搶佔前所能持續運行的時間。

時間片過長會導致系統對交互的響應表現欠佳,太短的話會明顯增大進程切換帶來的處理器耗時。

9. 在Linux系統中,當一個進程進入可執行態,它就被准許投入運行。在多數OS中,是否要將一個進程立刻投入運行(即搶佔當前進程),是完全由進程優先級和是否有時間片決定的。而對於Linux所使用的新的CFS調度器,其搶佔時機取決於新的可執行進程消耗了多少處理器使用比(nice的比值)。如消耗的使用比比當前進程小,則新進程立刻投入運行,搶佔當前進程。否則,將推遲運行。

10. CFS 完全公平調度類

  • 完全摒棄時間片而是分配給進程一個處理器使用比重。通過這種方式,CFS確保了進程調度中能有恆定的公平性,而將切換頻率置於不斷變動中。

  • 任何進程所獲得的處理器時間是由它自己和其他所有可運行進程nice值的相對比值決定的

  • 任何nice值對應的絕對時間不在是一個絕對值,而是處理器的使用比。

  • 確保給每個進程公平的處理器使用比

11.  可運行隊列

  • CFS使用紅黑樹來組織可運行進程隊列,並利用其迅速找到最小vruntime的進程。

  • 在進程變爲可運行狀態(被喚醒)或者通過fork()調用第一次創建進程時會被加到所屬的調度類的可運行隊列中

  • 從可運行隊列中刪除進程的動作發生在進程阻塞或者終止時

12. 調度器的入口

進程調度器的主要入口是函數schedule(),schedule()會調用pick_next_task函數,按照優先級的大小,從高到低遍歷每一個調度類,每一個調度類都有自己的可運行隊列,然後獲得該調度類下的優先級最高的進程,如果爲空,那麼繼續處理下一個優先級的調度類。

schedule會調用下面的pick_next_task函數:

  1. /*
  2. * Pick up the highest-prio task:
  3. */
  4. static inline struct task_struct *
  5. pick_next_task(struct rq *rq, struct task_struct *prev)
  6. {
  7. const struct sched_class *class = &fair_sched_class;
  8. struct task_struct *p;
  9. /*
  10. * Optimization: we know that if all tasks are in
  11. * the fair class we can call that function directly:
  12. */
  13. if (likely(prev->sched_class == class &&
  14.   rq->nr_running == rq->cfs.h_nr_running)) {
  15. p = fair_sched_class.pick_next_task(rq, prev);
  16. if (unlikely(p == RETRY_TASK))
  17. goto again;
  18. /* assumes fair_sched_class->next == idle_sched_class */
  19. if (unlikely(!p))
  20. p = idle_sched_class.pick_next_task(rq, prev);
  21. return p;
  22. }
  23. again:
  24. for_each_class(class) {
  25. p = class->pick_next_task(rq, prev);
  26. if (p) {
  27. if (unlikely(p == RETRY_TASK))
  28. goto again;
  29. return p;
  30. }
  31. }
  32. BUG(); /* the idle class will always have a runnable task */
  33. }

在Linux如下以及調度類:

  1. struct sched_class stop_sched_class;
  2. struct sched_class dl_sched_class;
  3. struct sched_class rt_sched_class;
  4. struct sched_class fair_sched_class;
  5. struct sched_class idle_sched_class;

其中優先級的順序是: stop > dl > rt > fair > idle。高優先級的調度類利用其next字段指向相鄰的低優先級的調度類。如:

  1. const struct sched_class stop_sched_class = {
  2. .next = &dl_sched_class,
  3. ......
  4. }
  5. const struct sched_class dl_sched_class = {
  6. .next = &rt_sched_class,
  7. .....
  8. }
  9. const struct sched_class rt_sched_class = {
  10. .next = &fair_sched_class,
  11. ......
  12. }
  13. const struct sched_class fair_sched_class = {
  14. .next = &idle_sched_class,
  15. ......
  16. }

idle進程的調度類是idle_sched_class, 這個是在start_kernel ---> rest_init ---> init_idle_bootup_task(current) 設置的。所以不管怎麼樣,一定會找都一個可供CPU執行的進程。

12. 睡眠和喚醒

  • 睡眠的過程:進程把自己標記成休眠狀態,放入等待隊列,然後調用schedule(),他會將當前進程從所屬的可執行紅黑樹中移出,然後選擇和執行一個其他進程。睡眠通過等待隊列進行處理,等待隊列是由等待某些事件發生的進程組成的鏈表,內核用wake_queue_head_t表示等待隊列。

  • 喚醒過程:進程被設置爲可執行狀態,然後再從等待隊列中移到可執行紅黑樹中。喚醒通過wake_up()實現,它會喚醒指定的等待隊列上的所有進程,它將進程設置爲TASK_RUNNING狀態,然後調用enqueue_task()將其放入紅黑樹,被喚醒的進程優先級如果比當前進程高,還要設置need_resched標誌。

13.  上下文切換

即從一個可執行進程切換到另一個科執行進程,通過context_switch()實現,schedule會調用該函數。它完成的兩項基本工作:

  • 調用switch_mm(),完成把虛擬內存從上一個進程映射到新進程中

  • 調用switch_to(),完成將上一個進程的處理器狀態切換到新進程的處理器狀態,如保存、恢復棧信息和寄存器信息,還有其他任何與體繫結構相關的狀態信息,都必須以每個進程爲對象進行管理和保存。

14. 進程切換的時機 (除了進程主動調用schedule()之外)

  • need_resched標誌:內核提供的標誌用來表明是否需要重新執行一次調度。每一個進程都包含一個need_resched標誌,存放在thread_info結構體裏,用一個特別的標識變量中的一位來表示。對於ARM架構的CPU,定義如下:

    1. struct thread_info {
    2. unsignedlong flags;/* low level flags */
    3. int preempt_count;/* 0 => preemptable, <0 => bug */
    4. ......
    5. }

    其中,flags的第1位就是用來表示need_resched的。如下:

    1. /*
    2. * thread information flags:
    3. *  TIF_SYSCALL_TRACE - syscall trace active
    4. *  TIF_SYSCAL_AUDIT - syscall auditing active
    5. *  TIF_SIGPENDING - signal pending
    6. *  TIF_NEED_RESCHED - rescheduling necessary
    7. *  TIF_NOTIFY_RESUME - callback before returning to user
    8. *  TIF_USEDFPU - FPU was used by this task this quantum (SMP)
    9. *  TIF_POLLING_NRFLAG - true if poll_idle() is polling TIF_NEED_RESCHED
    10. */
    11. #define TIF_SIGPENDING 0
    12. #define TIF_NEED_RESCHED 1
    13. #define TIF_NOTIFY_RESUME 2/* callback before returning to user */
    14. #define TIF_UPROBE 7
    15. #define TIF_SYSCALL_TRACE 8
    16. #define TIF_SYSCALL_AUDIT 9
    17. #define TIF_SYSCALL_TRACEPOINT 10
    18. #define TIF_SECCOMP 11/* seccomp syscall filtering active */
    19. #define TIF_NOHZ 12/* in adaptive nohz mode */
    20. #define TIF_USING_IWMMXT 17
    21. #define TIF_MEMDIE 18/* is terminating due to OOM killer */
    22. #define TIF_RESTORE_SIGMASK 20
    23. #define TIF_MM_RELEASED 21/* task MM has been released */
  • 設置need_resched的時機:

    • 當某個進程應該被搶佔時,scheduler_tick()就會設置這個標誌

    • 當某個優先級高的進程進入可執行狀態的時候,try_to_wake_up()會設置該標誌

    • 設置方法:set_tsk_need_resched()、clear_tsk_need_resched()

    • 檢查方法:need_resched()

  • 檢查need_resched的時機(即:發生進程切換的時機)

    • 返回用戶空間的時候,這個屬於用戶搶佔

    • 從中斷返回的時候(注:這裏從中斷可以返回到內核空間(屬於內核搶佔)或者用戶空間(屬於用戶搶佔),具體要看中斷發生時被打斷的進程正處於什麼空間)

15. 用戶搶佔發生的時機

  • 從系統調用返回用戶空間的時候

  • 從中斷處理返回用戶空間的時候

16. 內核搶佔發生的時機

  • 前提:Linux完整地支持內核搶佔,但是前提是被搶佔的進程沒有持有鎖,即preempt_count是0.

  • preempt_count也是每一個進程一個,存放在thread_info中

  • 當從中斷返回內核空間的時候,內核會檢查need_resched和preempt_count,如果need_resched爲被設置,並且preempt_count爲0,調度程序就會被調用。否則,就直接從中斷返回當前執行進程。

  • 此外,如果當前進程持有的所有的鎖都釋放了,preempt_count就會重新爲0,此時,釋放鎖的代碼會檢查need_resched是否被設置,如果是的話,就會調用調度程序。

  • 綜上,發生的時機:

    • 中斷處理程序正在執行,且返回內核空間前

    • 內核代碼再一次具有可搶佔性的時候(即preemp_count爲0,如釋放鎖)

    • 內核中的任務顯式地調用schedule()

    • 內核中的任務阻塞(這同樣也會導致調用schedule(),如調用kmalloc可能導致睡眠)

17. 實時調度策略

  • Linux提供了兩種實時調度策略:SCHED_FIFO和SCHED_RR,而對於普通的、非實時的調度策略是SCHED_NORMAL。

  • 只要有實時進程處於科執行狀態,就會一直執行,直到它自己受阻塞或顯式地釋放CPU爲止。

  • SCHED_RR是帶有時間片的SCHED_FIFO。當SCHED_RR任務的時間片耗盡時,同一優先級的其他實時進程被輪流調度,即這裏的時間片只是用來重新調度同一優先級的進程。

  • 實時調度策略都是靜態優先級,內核不爲實時進程計算動態優先級。

18. 處理器綁定 processor affinity

Linux調度程序提供強制的處理器綁定機制。task_struct的cpu_allowed位掩碼標誌的每一位對應一個系統可用的處理器,爲一的位表示進程可以在對應的處理器上執行。使用sched_setaffinity()和sched_getaffinity()可以修改和獲得這個值。

 

 

完。



来自为知笔记(Wiz)



第四章 進程調度