Linux CPU的排程 邱姸婕

Outline Process Control Block (PCB) Process State Scheduling Policy Completely Fair Scheduler (CFS) Multi-thread Linux Kernel

Process Control Block (1/2) 每個Process在OS中都有一個對應的PCB PCB記載Process的相關資訊包含: Process ID : 唯一的(Unique) Process State : Ready, Running, Wait Programming Counter : 放Process下一個要執行的指令位置 CPU Registers : Process所需的暫存器 CPU Scheduling Info : Process的優先權 Memory Management Info : Base, limit registers Accounting Info : 使用了多少CPU的時間、時間限制 I/O State : 未完成的I/O請求、分配給Process的Devices編號

Process Control Block (2/2)

Outline Process Control Block (PCB) Process State Scheduling Policy Completely Fair Scheduler (CFS) Multi-thread Linux Kernel

Process State Process : 執行中的程式

Outline Process Control Block (PCB) Process State Scheduling Policy Completely Fair Scheduler (CFS) Multi-thread Linux Kernel

Scheduling Policy (1/2) 在Ready Queue中的process會互相爭奪CPU,所以利用Scheduling Policy 來決定下一個被CPU執行的Process 在Linux中的scheduling policy又可分為兩大類 Real-time Policy Normal Policy

Scheduling Policy (2/2) Real-time Policy Normal Policy Real-time Policy的Process會優先被排程 優先權範圍為1到99 Real-time Policy中分為兩種Policy SCHED_FIFO SCHED_RR Normal Policy 優先權範圍為100到139 Normal Policy中分為三種Policy SCHED_OTHER SCHED_BATCH SCHED_IDLE

Real-time Policy(1/2) SCHED_FIFO (First In First Out ) 擁有最高優先權的Process優先執行 持續執行此Process直到它自行釋出或遇到更高優先權的Process Process Priority Burst time P1 2 3 P2 1 15 P3

Real-time Policy(2/2) SCHED_RR (Round Robin) 擁有最高優先權的先執行  若有兩個優先權相同的Process，Kernel 會分配一個 time slice 去限制執行 時間 Process Priority Burst time P1 1 15 P2 10 Time slice = 5 ms

Normal Policy SCHED_OTHER SCHED_BATCH SCHED_IDLE 每個Process都有time slice 使用Completely Fair Scheduler (CFS)機制運行 SCHED_BATCH 比 SCHED_OTHER 的優先權低 適合Batch Process，非急迫且與User互動性低的process SCHED_IDLE 最低優先權 在System Idle時此process才會被執行

Scheduling Policy Short Job First (SJF) 最短作業優先排班法 優先選擇具有最小CPU Burst Time的Process 若遇到兩個Burst Time一樣的Process，則在使用FIFO Process Burst time P1 6 P2 8 P3 7 P4 3

Outline Process Control Block (PCB) Process State Scheduling Policy Completely Fair Scheduler (CFS) Multi-thread Linux Kernel

Completely Fair Scheduler (1/3) 由Ingo Molnar提出 在Linux 2.6.23 (2007.10) 之後，Linux Kernel採用了CFS機制 解決某些Process因為優先權較低而始終沒被CPU處理到的問題 導入了“Virtual Runtime”

Completely Fair Scheduler (2/2) Virtual Runtime (vruntime) 每個Process都有自己的vruntime與Nice值 假設一process的執行時間為 t ns,則每一輪排程時 vrntime越小表示此process距離上一次被執行時間間隔最久 選擇vrntime最小的process為下一個CPU執行的Process Nice 用來調整Process的執行優先順序 Nice範圍為 -20到19，越小優先權越高 Vruntime += t * nice

Completely Fair Scheduler (3/3) Round1: 例子 Process Nice t P1 -2 5 P2 -1 P3 10 P1: Vruntime = 5*(-2)=-10 P2: Vruntime = 5*(-1)=-5 P3: Vruntime = 10*(-2)=-20 Round2: Process Nice t P1 -2 5 P2 -1 P1: Vruntime = -10+5*(-2)=-20 P2: Vruntime = -5+5*(-1)=-10 Round3: Process Nice t P2 -1 5 P4 10 P2: Vruntime = -10+5*(-1)=-15 P4: Vruntime = 10*(-1)=-10

Outline Process Control Block (PCB) Process State Scheduling Policy Completely Fair Scheduler (CFS) Multi-thread Linux Kernel

Thread Thread 又稱Light Weight Process (LWP) CPU執行時的一個基本單位 由一個Thread ID、程式計數器、一組暫存器及一個Stack組成 一個Process可能包含多個Thread 同一個Process中的Thread彼此共享 Code section Data section OS Resources (Open Files, signals)

Multi-thread (1/4) Thread又可分為User Level的User Thread與Kernel的Kernel Thread User Thread 由 User Level 的 Thread Library 來產生、排班、管理Thread Kernel Thread 由 OS來產生、排班、管理Thread

Multi-thread (2/4) Many to One 多個User Thread對應到一個Kernel Thread 由Thread Library管理 如果有一個Thread呼叫系統暫停,則整個Process就會被暫停 一次只有一個Thread可以存取Kernel

Multi-thread (3/4) One to One 一個User Thread對應到一個Kernel Thread 如果有一個Thread呼叫系統暫停時,其它Thread可以繼續被執行 產生一個新的User Thread就連帶要產生一個新的Kernel Thread 成本高,因此限制Thread產生的個數

Multi-thread (4/4) Many to Many 多個User Thread對應到較少或相等的Kernel Thread 如果有一個Thread呼叫系統暫停時,其它Thread可以繼續被執行 成本比一對一對的模式低

Outline Process Control Block (PCB) Process State Scheduling Policy Completely Fair Scheduler (CFS) Multi-thread Linux Kernel

Linux Kernel kernel_init( ) init_post( ) start_kernel( ) rest_init( ) kthreadd

Linux Kernel - kthreadd 負責所有Kernel Thread的創建、調度及管理 去查看kthread_create_list中是否有kernel thread 需要創建, 若有則使用create_kthread()創建, 接著用wake_up_process()喚醒這個task讓他運行 使用kthread_stop()來刪除kernel thread Linux/kernel/kthred.c kthreadd( ) Check kthread_create_list create_kthread( ) wake_up_process( )

Linux Kernel - khelper 透過khelper來使Kernel Thread帶起User Mode的應用程式執行 首先去查看WorkQueue裡是否有user thread需要執行, 若有則透過call_usermodehelper_setup()設定這個user thread相關路徑及參數, 最後使用call_usermodehelper_exec()來達到執行user thread的目的 Linux/kernel/kmod.c __init usermodehelper_init() Check khelper_wq call_usermodehelper_setup( ) call_usermodehelper_exec( )

Linux Kernel - Code(1/2) call_usermodehelper_setup( ) 設定預被執行的user thread其相關路徑及參數 Linux/kernel/kmod.c

Linux Kernel - Code(2/2) call_usermodehelper_exec( ) 達到執行user thread的目的 Linux/kernel/kmod.c