深入Linux內核架構——行程管理和調度（一）-有解無憂

如果系統只有一個處理器，那么給定時刻只有一個程式可以運行，在多處理器系統中，真正并行運行的行程數目取決于物理CPU的數目，內核和處理器建立了多任務的錯覺，是通過以很短的間隔在系統運行的應用程式之間不停切換做到的，由此，以下兩個問題必須由內核解決：除非明確要求，否則應用程式不能彼此干擾；CPU時間必須在各種應用程式之間盡可能公平共享（一些程式可能比其他程式更重要），本文主要涉及內核共享CPU時間的方法以及如何在行程之間切換（內核為各行程分配時間，保證切換之后從上次撤銷其資源時執行環境完全相同），

一、行程優先級

并非所有行程的重要程度都相同，對于行程，首先比較粗糙的劃分，行程可以分為實時行程和非實時行程，

硬實時行程：有嚴格的時間限制，某些任務必須在指定時限內完成，比如汽車的安全氣囊，一旦發生碰撞，必須保證在一定時間內觸發，超過時限則產生災難性的后果，主流的Linux內核不支持實時處理，但有一些修改版本如RTLinux、Xenomai、RATI提供了這些特性，這些方案中，將Linux內核作為獨立的“行程”運行處理次要軟體，實時作業在Linux內核外部完成，
軟實時行程：軟實時行程是硬實時行程的一種榷訓形式，優先于其他普通行程，稍微晚一點不會造成巨大影響，比如對CD的寫入操作，
普通行程：沒有特定時間約束的行程，可以根據重要性對其進行分配優先級，

圖是CPU分配時間的一個簡圖，行程運行按時間片調度，分配行程的時間片額與其相對重要性相當，系統中時間的流動對應于圓盤的轉動，重要的行程會比次要的行程得到更多CPU時間，行程被切換時，所有的CPU暫存器內容和頁表都會被保存，下次該行程恢復執行時，其執行環境可以完全恢復，這種簡化模型忽略了一些行程狀態相關的資訊，不能使CPU時間利益回報盡可能最大化，但是為調度器的質量確立一種定量標準非常困難，自Linux內核誕生以來，調度器的代碼已經重寫了好幾次，按時間先后順序，主要有O(n)調度器，O(1)調度器和CFS(completely fair scheduler)調度器，

二、行程生命周期

行程并不總是可以立即運行，有時候它需要等待來自外部信號源、不受其控制的事件（如文本編輯等待輸入），在調度器進行行程切換時，必須知道每個行程的狀態，因為將CPU事件分配給無事可做的行程沒有意義，行程在各個狀態之間的轉換也同樣重要，

行程狀態之間的切換示意圖

行程可能存在的狀態有：運行、等待和睡眠，圖描述了行程的幾種狀態及其轉換，除了圖中所示的幾種狀態以外，還有一種狀態被稱為僵尸態，

運行：該行程正在運行，
等待（就緒）：行程能夠運行，但沒有得到許可，因為CPU分配給了另一個行程，調度器可能在下一次任務切換時選擇該行程，
睡眠：行程正在睡眠無法運行（“睡眠”狀態有兩種），因為它在等待一個外部事件，調度器無法在任務切換時選擇該行程，
僵尸：行程已經死亡，但是它的資料還沒有從行程表中洗掉，（在UNIX作業系統下銷毀行程需要兩步，第一步由另一個行程或一個用戶殺死（通過信號完成）；第二步是行程的父行程在子行程終止時必須呼叫或已經呼叫wait4系統呼叫，使內核釋放為子行程保留的資源，當條件一發生，第二個條件不成立的情況，便會出現“僵尸”狀態）

為了維持系統中現存的各個行程，防止它們與系統其他部分相互干擾，Linux行程管理結構中還需要兩種行程狀態選項：用戶狀態和核心態，行程通常處于用戶狀態，只能訪問自身的資料，無法干擾系統中其他行程，如果行程想要訪問系統資料，則必須切換到核心態，這種訪問必須經由明確定義的路徑（系統呼叫），從用戶狀態進入核心態的第二種方法是通過中斷，此時切換是自動觸發的，處理中斷操作，通常與中斷發生時執行的程式無關，（系統呼叫是由用戶應用程式有意呼叫的，中斷則是不可預測的）

內核的搶占調度模型是優先讓優先級高的行程占用CPU，它建立了一個層次結構，用于判斷哪些行程狀態可由其他狀態搶占，

普通行程總是可能被搶占，甚至由其他行程搶占，
如果系統處于核心態并正在處理系統呼叫，那么其他行程是無法奪取CPU時間的，
中斷可以暫停處于用戶態和和心態的行程，具有最高優先級，

在內核2.5開發期間，內核搶占（kernel preemption）選項被添加到內核，它支持緊急情況下切換到另一個行程，甚至當前行程處于系統呼叫也行，內核搶占可以減少等待時間，但代價是增加了內核的復雜度，因為搶占時有許多資料結構需要針對并發訪問進行保護，

小編推薦自己的Linux、C/C++技術交流群:【960994558】整理了一些個人覺得比較好的學習書籍、視頻資料共享在里面（包括C/C++，Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協程，DPDK等等.），有需要的可以自行添加哦！~
在這里插入圖片描述

三、行程表示

Linux內核涉及行程和程式的所有演算法都圍繞資料結構task_struct建立，該結構定義在include/sched.h中，task_struct包含很多成員，將行程與各內核子系統聯系起來，task_struct定義的簡化版本如下：

1 struct task_struct {
  2     volatile long state; /* -1表示不可運行，0表示可運行，>0表示停止 */
  3     void *stack;
  4     atomic_t usage;
  5     unsigned long flags; /* 每行程標志，下文定義 */
  6     unsigned long ptrace;
  7     int lock_depth; /* 大內核鎖深度 */
  8     int prio, static_prio, normal_prio;
  9     struct list_head run_list;
 10     const struct sched_class *sched_class;
 11     struct sched_entity se;
 12     unsigned short ioprio;
 13     unsigned long policy;
 14     cpumask_t cpus_allowed;
 15     unsigned int time_slice;
 16 #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
 17     struct sched_info sched_info;
 18 #endif
 19     struct list_head tasks;
 20 /*
 21 * ptrace_list/ptrace_children鏈表是ptrace能夠看到的當前行程的子行程串列，
 22 */
 23     struct list_head ptrace_children;
 24     struct list_head ptrace_list;
 25     struct mm_struct *mm, *active_mm;
 26 /* 行程狀態 */
 27     struct linux_binfmt *binfmt;
 28     long exit_state;
 29     int exit_code, exit_signal;
 30     int pdeath_signal; /* 在父行程終止時發送的信號 */
 31     unsigned int personality;
 32     unsigned did_exec:1;
 33     pid_t pid;
 34     pid_t tgid;
 35 /*
 36 * 分別是指向（原）父行程、最年輕的子行程、年幼的兄弟行程、年長的兄弟行程的指標，
 37 *（p->father可以替換為p->parent->pid）
 38 */
 39     struct task_struct *real_parent; /* 真正的父行程（在被除錯的情況下） */
 40     struct task_struct *parent; /* 父行程 */
 41 /*
 42 * children/sibling鏈表外加當前除錯的行程，構成了當前行程的所有子行程
 43 */
 44     struct list_head children; /* 子行程鏈表 */
 45     struct list_head sibling; /* 連接到父行程的子行程鏈表 */
 46     struct task_struct *group_leader; /* 執行緒組組長 */
 47 /* PID與PID散串列的聯系， */
 48     struct pid_link pids[PIDTYPE_MAX];
 49     struct list_head thread_group;
 50     struct completion *vfork_done; /* 用于vfork() */
 51     int __user *set_child_tid; /* CLONE_CHILD_SETTID */
 52     int __user *clear_child_tid; /* CLONE_CHILD_CLEARTID */
 53     unsigned long rt_priority;
 54     cputime_t utime, stime, utimescaled, stimescaled;
 55     unsigned long nvcsw, nivcsw; /* 背景關系切換計數 */
 56     struct timespec start_time; /* 單調時間 */
 57     struct timespec real_start_time; /* 啟動以來的時間 */
 58 /* 記憶體管理器失效和頁交換資訊，這個有一點爭論，它既可以看作是特定于記憶體管理器的，
 59 也可以看作是特定于執行緒的 */
 60     unsigned long min_flt, maj_flt;
 61     cputime_t it_prof_expires, it_virt_expires;
 62     unsigned long long it_sched_expires;
 63     struct list_head cpu_timers[3];
 64 /* 行程身份憑據 */
 65     uid_t uid,euid,suid,fsuid;
 66     gid_t gid,egid,sgid,fsgid;
 67     struct group_info *group_info;
 68     kernel_cap_t cap_effective, cap_inheritable, cap_permitted;
 69     unsigned keep_capabilities:1;
 70     struct user_struct *user;
 71     char comm[TASK_COMM_LEN]; /* 除去路徑后的可執行檔案名稱-用[gs]et_task_comm訪問（其中用task_lock()鎖定它）-通常由flush_old_exec初始化 */
 72 /* 檔案系統資訊 */
 73     int link_count, total_link_count;
 74 /* ipc相關 */
 75     struct sysv_sem sysvsem;
 76 /* 當前行程特定于CPU的狀態資訊 */
 77     struct thread_struct thread;
 78 /* 檔案系統資訊 */
 79     struct fs_struct *fs;
 80 /* 打開檔案資訊 */
 81     struct files_struct *files;
 82 /* 命名空間 */
 83     struct nsproxy *nsproxy;
 84 /* 信號處理程式 */
 85     struct signal_struct *signal;
 86     struct sighand_struct *sighand;
 87     sigset_t blocked, real_blocked;
 88     sigset_t saved_sigmask; /* 用TIF_RESTORE_SIGMASK恢復 */
 89     struct sigpending pending;
 90     unsigned long sas_ss_sp;
 91     size_t sas_ss_size;
 92     int (*notifier)(void *priv);
 93     void *notifier_data;
 94     sigset_t *notifier_mask;
 95 #ifdef CONFIG_SECURITY
 96     void *security;
 97 #endif
 98 /* 執行緒組跟蹤 */
 99     u32 parent_exec_id;
100     u32 self_exec_id;
101 /* 日志檔案系統資訊 */
102     void *journal_info;
103 /* 虛擬記憶體狀態 */
104     struct reclaim_state *reclaim_state;
105     struct backing_dev_info *backing_dev_info;
106     struct io_context *io_context;
107     unsigned long ptrace_message;
108     siginfo_t *last_siginfo; /* 由ptrace使用，*/
109 ...
110 };

每個命名空間都提供了相應的標志用于fork建立一個新的命名空間，因為在每個行程關聯到自身命名空間時，使用了指標，所以多個行程可以共享一組子命名空間，修改給定的命名空間，對所有屬于該命名空間的行程都是可見的，

UTS（UNIX Timesharing System）命名空間
它存盤了系統的名稱（Linux…）、內核發布版本、機器名等，使用uname工具可以取得這些屬性的當前值，它幾乎不需要特別處理，因為它只需要簡單量，沒有層次組織，所有相關資訊都匯集到結構uts_namespace中，

1 struct uts_namespace {
2     struct kref kref;        //嵌入的參考計數器，用于跟蹤內核有多少的地方使用了該命名空間實體
3     struct new_utsname name;        //命名空間所提供的屬性資訊
4 };

內核通過copy_utsname函式創建UTS命名空間，在讀取或設定UTS屬性值時，內核會保證總是操作特定于當前行程的uts_namespace實體，在當前行程修改UTS屬性不會反映到父行程，而父行程的修改也不會傳播到子行程，

用戶命名空間
用戶命名空間維護了一些統計資料（如行程和打開檔案數目），它在資料結構管理方面類似于UTS，在要求創建新的用戶命名空間時，生成當前用戶命名空間的一份副本，并關聯到當前行程nsproxy實體，

1 struct user_namespace {
2     struct kref kref;        //嵌入的計數器
3     struct hlist_head uidhash_table[UIDHASH_SZ];        //訪問各個實體串列
4     struct user_struct *root_user;        //負責記錄其資源消耗
5 };

每個用戶命名空間對其用戶資源使用的統計，與其他命名空間完全無關，對root用戶的統計也是如此，這是因為在克隆一個用戶命名空間時，為當前用戶和root都創建了新的user_struct實體，

3、行程ID號

UNIX行程會分配一個ID號（簡稱PID）作為其命名空間中唯一的標識，ID有的多型別：

行程處于某個執行緒組時，擁有執行緒組ID（TGID）（若行程沒有使用執行緒，則PID與TGID相同）；
獨立行程可以合并成行程組，行程組成員的task_struct的pgrp屬性值相同（為行程組組長PID）（用管道連接的行程便包含在同一個行程組中）；
幾個行程組可以合并成一個會話，會話中所有行程都有會話ID（SID），保存在task_struct的session中，命名空間增加了PID管理的復雜性，PID命名空間按層次組織，因此必須區磁區域ID和全域ID，
全域ID是在內核本身和初始命名空間中唯一的ID號，對每個ID型別，都有一個全域ID，保證在整個系統中唯一；
區域ID屬于某特定命名空間，不具備全域有效性，在所屬的命名空間內部有效，因此型別相同、值也相同的ID可能出現在不同的命名空間中，

PID分配器（pid allocator）用于加速新ID的分配（此處ID是廣義的包括TGID，SID等），內核提供輔助函式，實作通過ID及其型別查找行程的task_struct的功能，以及將ID的內核表示形式和用戶空間可見的數值進行轉換的功能，

PID命名空間的表示方式以及含義：

1 struct pid_namespace {
2 ...
3     struct task_struct *child_reaper;    //每個PID命名空間都具有一個行程，其發揮的作用相當于全域的init行程，child_reaper保存了指向該行程的task_struct的指標，
4 ...
5     int level;        //表示當前命名空間在命名空間層次結構中的深度，初始命名空間的level為0，
6     struct pid_namespace *parent;        //指向父命名空間的指標
7 };

PID的管理圍繞struct_pid和struct_upid展開，struct pid是內核對PID的內部表示，而struct upid則表示特定的命名空間中可見的資訊，

1 struct upid {
2     int nr;        //ID的數值
3     struct pid_namespace *ns;        //指向該ID所屬的命名空間的指標
4     struct hlist_node pid_chain;        //將所有的upid鏈接在一起的散鏈表
5 };

1 truct pid
2 {
3     atomic_t count;            //參考計數器
4 /* 使用該pid的行程的串列 */
5     struct hlist_head tasks[PIDTYPE_MAX];     //每一項對應一個id型別，作為散串列頭，對于其中的每項，因為一個ID可能用于幾個行程，所有共享同一給定ID的task_struct實體都通過該串列連接
6     int level;     //表示可以看到該行程的命名空間的數目
7     struct upid numbers[1];        //upid實體陣列，每個陣列項都對應于一個命名空間
8 };

1 enum pid_type
2 {
3     PIDTYPE_PID,
4     PIDTYPE_PGID,
5     PIDTYPE_SID,
6     PIDTYPE_MAX        //ID型別的數目
7 };

列舉型別中定義的ID型別不包括執行緒組ID，因為執行緒組ID無非是執行緒組組長的PID，圖5對pid和upid兩個結構的關系進行了概述，對于members陣列，形式上只有一個陣列項，如果一個行程只包含在全域命名空間中，那么確實如此，由于該陣列位于結構的末尾，因此只要分配更多的記憶體空間，即可向陣列添加附加的項，
在這里插入圖片描述
內核提供了若干輔助函式，用于操作和掃描上述復雜結構，完成以下兩個任務：

給出區域數字id和對應的命名空間，查找此二元組的task_struct；
給出task_struct、id型別、命名空間，取得命名空間區域的數字ID，

此外，內核還負責提供機制來生成唯一PID，具體方法：為跟蹤已經分配和仍然可用的PID，內核使用一個大的位圖，其中每個PID由一個位元標識，PID的值可通過對應位元在位圖中的位置計算而來，所有其他的ID都可以派生自PID，

4、行程關系

完成了ID連接關系之后，內核還負責管理建立在UNIX行程創建模型之上的“家族關系”（如果由行程A形成了行程B，則A是父行程，B是子行程；若行程A形成了若干個子行程，則這些子行程之間成為兄弟關系），圖說明了行程家族中的父子關系和兄弟關系，以及task_struct中children和sibling兩個鏈表表頭實作這些關系的方式，
在這里插入圖片描述

四、行程管理相關的系統呼叫

1、行程復制
Linux的行程復制有三種方式：

fork，重量級呼叫，它建立了父行程的完整副本，然后作為子行程執行，（為了減少作業量，提高效率，使用了寫時復制技術）
vfork，類似于fork，不創建父行程副本，相反，父子行程之間共享資料，（節省了大量CPU時間）vfork設計用于子行程形成后立即執行execve系統呼叫加載新程式的情形，在子行程退出或開始
新程式之前，內核保證父行程處于堵塞狀態，
clone，產生執行緒，可以對父子行程之間的共享、復制進行精確控制，

（1）寫時復制（COW）

寫時復制技術（copy-on-write），用來防止在fork執行時將父行程的所有資料復制到子行程，為了解決很多情況下不需要復制父行程資訊時，復制父行程副本使用大量記憶體，耗費很長時間的問題，

fork之后，父子行程的地址空間指向同樣的物理記憶體頁，此時，物理記憶體頁處于只讀狀態，如果確實要對記憶體進行寫入操作，會產生缺頁例外，然后由內核分配記憶體空間，

（2）執行系統呼叫

fork、vfork和clone系統呼叫的入口點分別是sys_fork、sys_vfork和sys_clone函式，這些入口函式都呼叫體系結構無關的do_fork函式，通過clone_flags這個標志集合區分不同入口，

1 long do_fork(
2     unsigned long clone_flags,    //標志集合，指定控制復制程序的屬性
3     unsigned long stack_start,    //用戶狀態下堆疊的起始地址
4     struct pt_regs *regs,        //指向暫存器集合的指標，以原始形式保存了呼叫引數
5     unsigned long stack_size,    //用戶狀態下堆疊的大小，通常設為0
6     int __user *parent_tidptr,    //指向用戶空間中父行程的PID
7     int __user *child_tidptr         //指向用戶空間中子行程的PID
8 ）

（3）do_fork的實作

do_fork的代碼流程圖如圖所示，
在這里插入圖片描述
子行程生產成功后，內核必須執行收尾操作：

如果設定了CLONE_PID標志，fork操作可能會創建新的pid命名空間，如果創建了新的命名空間，則需要在新命名空間獲取pid，否則直接獲取區域pid，
如果用了ptrace監控，創建行程后，就向它發送SIGSTOP信號，讓除錯器檢查資料，
子行程使用wake_up_new_task喚醒（將它的task_struct添加到調度器佇列，讓它有機會執行），
如果使用vfork機制，必須啟用子行程的完成機制，子行程的task_struct的vfork_done成員即用于該目的，父行程用wait_for_completion函式在該變數中進入睡眠，直至子行程退出，子行程終止時，內核呼叫complete(vfork_done)喚醒因該變數睡眠的行程，
（4）復制行程

在do_fork中大多數作業是由copy_process函式完成的，該函式根據標志的控制，處理了3個系統呼叫（fork、vfork和clone）的主要作業，copy_process流程圖如圖所示，
在這里插入圖片描述
（5）創建執行緒特別問題

用戶空間執行緒庫使用clone系統呼叫來生成新執行緒，該呼叫支持（上文討論之外的）標志，對copy_process（及其呼叫的函式）具有某些特殊影響，

CLONE_PARENT_SETTID將生成執行緒的PID復制到clone呼叫指定的用戶空間中的某個地址
CLONE_CHILD_SETTID首先會將另一個傳遞到clone的用戶空間指標（child_tidptr）保存在新行程的task_struct中，
CLONE_CHILD_CLEARTID首先會在copy_process中將用戶空間指標child_tidptr保存在task_struct中，這次是另一個不同的成員，

上述標志可用于從用戶空間檢測內核中執行緒的產生和銷毀，CLONE_CHILD_SETTID和CLONE_PARENT_SETTID用于檢測執行緒的生成，CLONE_CHILD_CLEARTID用于在執行緒結束時從內核向用戶空間傳遞資訊，在多處理器系統上這些檢測可以真正地并行執行，

2、內核執行緒

內核執行緒是直接由內核本身啟動的行程，內核執行緒實際上是將內核函式委托給獨立的行程，與系統中其他行程“并行”執行（實際上，也并行于內核自身的執行），內核執行緒經常稱之為（內核）守護行程，它們用于執行下列任務：

周期性地將修改的記憶體頁與頁來源塊設備同步（例如，使用mmap的檔案映射），
如果記憶體頁很少使用，則寫入交換區，
管理延時動作（deferred action），
實作檔案系統的事務日志，

基本上，內核執行緒有兩種：

執行緒啟動后一直等待，直至內核請求執行緒執行某一特定操作，
執行緒啟動后按周期性間隔運行，檢測特定資源的使用，在用量超出或低于預置的限制值時采取行動，內核使用這類執行緒用于連續監測任務，

因為內核執行緒是由內核自身生成的，它有兩個特別之處：

它們在CPU的管態（supervisor mode）執行，而不是用戶狀態，
它們只可以訪問虛擬地址空間的內核部分（高于TASK_SIZE的所有地址），但不能訪問用戶空間，

內核執行緒可以用兩種方法實作：

古老的方法：

將一個函式傳遞給kernel_thread，內核呼叫daemonize以轉換為守護行程，從內核釋放父行程的所有資源，
daemonize阻塞信號的接收，
將init作為守護行程的父行程，

備選方案：使用宏kthread_run（引數與kthread_create相同），它會呼叫kthread_create創建新執行緒，立即喚醒它，還可以使用kthread_create_cpu代替kthread_create創建內核執行緒，使之系結到特定的CPU，

3、啟動新程式

（1）execve的實作

該系統呼叫的入口點是體系結構相關的sys_execve函式，該函式很快將其作業委托給系統無關的do_execve例程，do_execve的代碼流程圖如圖所示，
在這里插入圖片描述
do_execve的主要作業：

打開要執行的檔案；
bprm_init，申請行程空間并初始化，處理若干管理性任務；
prepare_binprm，提供父行程相關的值（特別是有效UID和GID），也是用于初始化；
search_binary_handler，查找一種適當的二進制格式，用于所要執行的特定檔案，
通常，二進制格式處理程式執行下列操作：

釋放原行程的所有資源；
將應用程式映射到虛擬地址空間，引數和環境也映射到虛擬地址空間；
設定行程的指令指標和其他特定于體系結構的暫存器，
（2）解釋二進制格式

Linux內核中，每種二進制格式都表示為結構體linux_binfmt，都需要用register_binfmt向內核注冊，linux_binfmt結構為：

1 struct linux_binfmt {
2     struct linux_binfmt * next;
3     struct module *module;
4     int (*load_binary)(struct linux_binprm *, struct pt_regs * regs);
5     int (*load_shlib)(struct file *);
6     int (*core_dump)(long signr, struct pt_regs * regs, struct file * file);
7     unsigned long min_coredump; /* minimal dump size */
8 };

二進制格式主要介面函式

load_binary用于加載普通程式，
load_shlib用于加載共享庫，即動態庫，
core_dump用于在程式錯誤的情況下輸出記憶體轉儲，用于除錯分析，以解決問題，

4、退出行程

行程必須用exit系統呼叫終止，使得內核有機會將該行程使用的資源釋放回系統，該呼叫的入口點是sys_exit函式，該函式的實作就是將各個參考計數器減1，如果參考計數器歸0而沒有行程再使用對應的結構，那么將相應的記憶體區域返還給記憶體管理模塊，

小編推薦自己的Linux、C/C++技術交流群:【960994558】整理了一些個人覺得比較好的學習書籍、視頻資料共享在里面（包括C/C++，Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協程，DPDK等等.），有需要的可以自行添加哦！~

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/233537.html

標籤：其他

上一篇：一文讓你徹底了解Redis(進階)，史上最全,不看后悔！！！【建議收藏】

下一篇：單例模式之列舉實作