《Linux原理與結(jié)構(gòu)》課件第7章

第七章進(jìn)程管理7.1進(jìn)程管理結(jié)構(gòu) 7.2進(jìn)程創(chuàng)建 7.3進(jìn)程調(diào)度7.4進(jìn)程終止在操作系統(tǒng)所營造的虛擬時(shí)空中，活動的主角是進(jìn)程。進(jìn)程(Process)是執(zhí)行中的計(jì)算機(jī)程序、是用戶在操作系統(tǒng)中的代理(替用戶工作)、是操作系統(tǒng)中一切活動的發(fā)起者、是內(nèi)核的主要服務(wù)對象。

操作系統(tǒng)內(nèi)核的主要任務(wù)是保證進(jìn)程更好地運(yùn)行，毫無疑問，進(jìn)程管理是操作系統(tǒng)工作的核心。進(jìn)程管理部分所管理的對象是進(jìn)程，所管理的資源是處理器，要達(dá)到的主要目標(biāo)是提高處理器的利用率，盡可能減少處理器資源的浪費(fèi)；平衡進(jìn)程之間的關(guān)系，盡可能公平、合理地分配處理器資源；提高進(jìn)程的運(yùn)行速度，盡可能縮短進(jìn)程的周轉(zhuǎn)周期；提高系統(tǒng)的反應(yīng)能力，盡可能縮短進(jìn)程的響應(yīng)時(shí)間；提高進(jìn)程的抗干擾性，實(shí)現(xiàn)進(jìn)程間的隔離與保護(hù)；提供進(jìn)程之間的同步、互斥和通信手段，維護(hù)資源的一致性，協(xié)調(diào)進(jìn)程的前進(jìn)步伐并允許進(jìn)程間相互通信等等。

作為操作系統(tǒng)中的主體，進(jìn)程有自己的生命周期。除第0號進(jìn)程之外，系統(tǒng)中的其它進(jìn)程都是動態(tài)創(chuàng)建的。新進(jìn)程可以與父進(jìn)程執(zhí)行同樣的程序，也可在運(yùn)行過程中加載并執(zhí)行新的程序。進(jìn)程在運(yùn)行過程中訪問到的所有地址構(gòu)成了它的虛擬地址空間，進(jìn)程的程序、數(shù)據(jù)等都存儲在虛擬地址空間中。為進(jìn)程管理虛擬地址空間的是虛擬內(nèi)存管理器，為進(jìn)程提供處理器的是調(diào)度器。運(yùn)行中的進(jìn)程需與其它進(jìn)程互斥、同步和通信。完成任務(wù)的進(jìn)程需要終止。因而進(jìn)程管理子系統(tǒng)又被分割成進(jìn)程創(chuàng)建、進(jìn)程調(diào)度、進(jìn)程終止、進(jìn)程虛擬內(nèi)存管理、進(jìn)程互斥與同步、進(jìn)程間通信等部分。

在早期的Linux系統(tǒng)中，進(jìn)程扮演著兩個(gè)角色，一是資源分配的實(shí)體，二是調(diào)度運(yùn)行的實(shí)體。Linux以進(jìn)程為單位分配資源，包括內(nèi)存、設(shè)備等，又以進(jìn)程為單位調(diào)度運(yùn)行(處理器僅分配給進(jìn)程)。獲得了足夠資源又獲得了處理器的進(jìn)程可以執(zhí)行它的程序，等待資源尤其是等待處理器資源的進(jìn)程無法執(zhí)行程序，只能暫停等待。7.1進(jìn)程管理結(jié)構(gòu)新版本的Linux借鑒了其它操作系統(tǒng)的成功經(jīng)驗(yàn)，允許將進(jìn)程的上述兩個(gè)角色分開，資源分配的實(shí)體仍被稱為進(jìn)程，但調(diào)度執(zhí)行的實(shí)體被改稱為線程(Thread)或輕量級進(jìn)程(LightweightProcess)。Linux以進(jìn)程為單位分配資源，以線程為單位調(diào)度運(yùn)行。屬于一個(gè)進(jìn)程的所有線程稱為一個(gè)線程組，一個(gè)線程組中的所有線程共享進(jìn)程的資源，如內(nèi)存、文件、信號處理、設(shè)備等。然而Linux又沒有嚴(yán)格區(qū)分它的進(jìn)程和線程。缺省情況下，Linux創(chuàng)建的都是進(jìn)程，只有在特別聲明時(shí)，新創(chuàng)建的進(jìn)程才被作為創(chuàng)建者的同組線程。一個(gè)線程組中的第一個(gè)線程通常被作為進(jìn)程創(chuàng)建，稱為領(lǐng)頭進(jìn)程，也就是該線程組的進(jìn)程，擁有資源。線程組中的其它線程通常是被領(lǐng)頭進(jìn)程特別創(chuàng)建的進(jìn)程，與領(lǐng)頭進(jìn)程共享資源，但它們是領(lǐng)頭進(jìn)程的兄弟而不是兒子，與領(lǐng)頭進(jìn)程擁有同一個(gè)父進(jìn)程。在表示上，進(jìn)程與線程完全一致，調(diào)度器同等對待進(jìn)程與線程。傳統(tǒng)意義上的Linux進(jìn)程既是進(jìn)程又是線程，它的線程組中僅有自己一個(gè)成員。在以下的討論中，除非特殊需要，不再專門區(qū)分進(jìn)程和線程。進(jìn)程的行為取決于它執(zhí)行的程序，但進(jìn)程又不等同于程序，用程序的代碼和數(shù)據(jù)均無法刻畫進(jìn)程，必須為進(jìn)程定義專門的管理結(jié)構(gòu)。操作系統(tǒng)通常用進(jìn)程控制塊(ProcessControlBlock，PCB)描述進(jìn)程，也通過進(jìn)程控制塊管理進(jìn)程。進(jìn)程控制塊是進(jìn)程存在的唯一標(biāo)識，其中含有進(jìn)程的描述信息和控制信息，是進(jìn)程動態(tài)性的集中體現(xiàn)。不同操作系統(tǒng)對進(jìn)程控制塊的叫法也不相同，Linux將自己的進(jìn)程控制塊稱為task_struct。

除task_struct結(jié)構(gòu)之外，Linux還為每個(gè)進(jìn)程定義了一個(gè)系統(tǒng)堆棧。當(dāng)進(jìn)程運(yùn)行在用戶態(tài)時(shí)，它使用用戶堆棧，當(dāng)進(jìn)程運(yùn)行在核心態(tài)時(shí)，它使用系統(tǒng)堆棧。由于每個(gè)進(jìn)程都會在核心態(tài)運(yùn)行，因而每個(gè)進(jìn)程都必須有系統(tǒng)堆棧。在早期的版本中，進(jìn)程的系統(tǒng)堆棧與它的task_struct結(jié)構(gòu)共用8KB的物理內(nèi)存，task_struct結(jié)構(gòu)位于首部，系統(tǒng)堆棧位于尾部。當(dāng)處理器在核心態(tài)運(yùn)行時(shí)，它的ESP總是位于當(dāng)前進(jìn)程的系統(tǒng)堆棧中，因而將ESP的低13位清0就可得到當(dāng)前進(jìn)程的task_struct結(jié)構(gòu)。

在隨后的發(fā)展中，task_struct結(jié)構(gòu)越來越大，已不適合再駐留在系統(tǒng)堆棧中，因而Linux為每個(gè)進(jìn)程另外準(zhǔn)備了一個(gè)thread_info結(jié)構(gòu)，用于替代task_struct駐留在進(jìn)程的系統(tǒng)堆棧中。結(jié)構(gòu)thread_info中的task指針指向進(jìn)程的task_struct結(jié)構(gòu)，而結(jié)構(gòu)task_struct中的stack指針指向進(jìn)程的thread_info結(jié)構(gòu)，如圖7.1所示。圖7.1進(jìn)程的系統(tǒng)堆棧與管理結(jié)構(gòu)結(jié)構(gòu)thread_info中還包含如下信息：

(1)標(biāo)志flags，記錄需要引起特別注意的信息，如有待處理信號、需再調(diào)度等。

(2)處理器號cpu，記錄運(yùn)行該進(jìn)程的當(dāng)前處理器號。

(3)搶占計(jì)數(shù)preempt_count，表示當(dāng)前進(jìn)程是否在處理中斷、是否允許搶占等，如圖4.8所示。

(4)虛擬地址上限addr_limit，規(guī)定了進(jìn)程可用的最大虛擬地址。

(5)執(zhí)行域exec_domain，如進(jìn)程執(zhí)行的是在其它操作系統(tǒng)中編譯的程序，該域記錄一些特殊的轉(zhuǎn)換關(guān)系，如系統(tǒng)調(diào)用號、信號編號等。

宏current是當(dāng)前進(jìn)程的task_struct結(jié)構(gòu)，其定義如下：

registerunsignedlong current_stack_pointer asm("esp")_used;

staticinlinestructthread_info *current_thread_info(void){

return(structthread_info*)(current_stack_pointer&~(8192-1));

}

#definecurrent (current_thread_info()->task)

當(dāng)然可以為每個(gè)處理器定義一個(gè)指針變量用于指向它的當(dāng)前進(jìn)程的task_struct結(jié)構(gòu)，但根據(jù)ESP寄存器直接計(jì)算要更加便捷，尤其是在多處理器環(huán)境中。

在進(jìn)程的管理結(jié)構(gòu)中，最重要的是task_struct結(jié)構(gòu)，其中的內(nèi)容可大致分為進(jìn)程標(biāo)識、認(rèn)證信息、調(diào)度信息、進(jìn)程狀態(tài)、進(jìn)程上下文、虛擬地址空間、文件目錄、文件描述符表、信號處理方式、名字空間等。

1.進(jìn)程標(biāo)識

雖然用task_struct結(jié)構(gòu)或指向task_struct結(jié)構(gòu)的指針都可唯一地標(biāo)識一個(gè)進(jìn)程，但這兩種方法都僅能在內(nèi)核中使用。用戶使用的進(jìn)程標(biāo)識應(yīng)該是簡潔、穩(wěn)定的，Linux將其稱之為進(jìn)程標(biāo)識號(ProcessIdentification，PID)。系統(tǒng)中的每個(gè)進(jìn)程都有一個(gè)PID。初始進(jìn)程init_task的PID是0，其它進(jìn)程的PID是在創(chuàng)建時(shí)臨時(shí)分配的。在早期的版本中，PID是一個(gè)小整數(shù)(16位)，目前的PID是一個(gè)整數(shù)(32位)。Linux用一個(gè)位圖記錄PID的使用情況，位圖的大小決定了PID號的最大值，在目前的版本中，PID號可達(dá)4194303個(gè)。如果系統(tǒng)中僅有一個(gè)名字空間，那么進(jìn)程與PID是一一對應(yīng)的。如果系統(tǒng)中有多個(gè)名字空間，一個(gè)進(jìn)程可以有多個(gè)PID，多個(gè)進(jìn)程也可以有同樣的PID，但在同一個(gè)名字空間中，進(jìn)程與PID仍然是一一對應(yīng)的。為了解決多名字空間帶來的問題，Linux專門定義了pid結(jié)構(gòu)來記錄一個(gè)進(jìn)程的不同PID，并定義了Hash表pid_hash來加速PID到task_struct結(jié)構(gòu)的轉(zhuǎn)換。為了區(qū)分不同的線程組，Linux又定義了線程組標(biāo)識號TGID(ThreadGroupID)。一個(gè)線程組的TGID就是它的領(lǐng)頭進(jìn)程的PID。一個(gè)線程組中的所有進(jìn)程擁有同樣的TGID，但卻有不同的PID。如果一個(gè)線程組中僅有一個(gè)進(jìn)程，那么它的TGID就等于PID。事實(shí)上，TGID等價(jià)于POSIX標(biāo)準(zhǔn)中的進(jìn)程ID，而PID則等價(jià)于POSIX標(biāo)準(zhǔn)中的線程ID。一個(gè)線程組中的所有進(jìn)程通過task_struct結(jié)構(gòu)中的thread_group域排成一個(gè)隊(duì)列，其中各進(jìn)程的group_leader都指向線程組的領(lǐng)頭進(jìn)程，如圖7.2所示。圖7.2進(jìn)程、線程與線程組另外，為了方便對進(jìn)程的管理，Linux還定義了進(jìn)程組(processgroup)和會話(session)。系統(tǒng)中的每個(gè)進(jìn)程都屬于一個(gè)進(jìn)程組，每個(gè)進(jìn)程組又屬于一個(gè)會話。進(jìn)程組和會話分別由領(lǐng)頭進(jìn)程標(biāo)識，同一進(jìn)程組的所有進(jìn)程擁有同樣的組標(biāo)識PGID，同一會話中的所有進(jìn)程擁有同樣的會話標(biāo)識SID。同一會話中的進(jìn)程通過該會話的領(lǐng)頭進(jìn)程和一個(gè)終端相連，該終端即是這個(gè)會話的控制終端。

2.認(rèn)證信息

認(rèn)證信息就是進(jìn)程的證書，其中包含有關(guān)進(jìn)程安全的各種標(biāo)識。在早期的Linux中，進(jìn)程的認(rèn)證信息直接記錄在task_struct結(jié)構(gòu)中，包括用戶標(biāo)識(UID)、用戶組標(biāo)識(GID)和進(jìn)程的權(quán)能(capability)等。新版本的Linux將認(rèn)證信息包裝在證書結(jié)構(gòu)cred中，其中包含多組信息，如：

(1)

4組UID和GID，其中uid和gid標(biāo)識創(chuàng)建進(jìn)程的用戶，euid和egid標(biāo)識當(dāng)前有效的用戶，fsuid和fsgid標(biāo)識文件系統(tǒng)用戶，suid和sgid用于備份。

(2)

4組權(quán)能，標(biāo)識進(jìn)程的能力，包括繼承、許可、有效的權(quán)能及權(quán)能的邊界集。

(3)密鑰和密鑰環(huán)，用于加解密處理。

(4)

Linux安全模塊(LSM)，如SELinux，其中包含多種特定的安全檢查操作。

(5)結(jié)構(gòu)user_struct，記錄用戶的統(tǒng)計(jì)信息，如擁有的進(jìn)程數(shù)、打開的文件數(shù)、掛起的信號數(shù)、鎖定的內(nèi)存量等。

在進(jìn)程進(jìn)行某些可能影響系統(tǒng)安全的操作之前，Linux會根據(jù)它的認(rèn)證信息檢查操作的合法性，并拒絕非法的操作。

3.調(diào)度策略

Linux的進(jìn)程分成兩大類，普通進(jìn)程和實(shí)時(shí)進(jìn)程。Linux的實(shí)時(shí)屬于軟實(shí)時(shí)(Softreal-time)，實(shí)時(shí)進(jìn)程的優(yōu)先級總是高于普通進(jìn)程，會比普通進(jìn)程得到更好的服務(wù)，但沒有嚴(yán)格的死線(Deadline)限制。

進(jìn)程的調(diào)度策略標(biāo)識了進(jìn)程的類型和調(diào)度方式。在Linux中，每個(gè)進(jìn)程都有一個(gè)調(diào)度策略，記錄在struct_struct結(jié)構(gòu)的policy域中。Linux定義了五種調(diào)度策略，分別是：

(1)

SCHED_NORMAL用于標(biāo)識普通進(jìn)程，采用CFS調(diào)度算法。

(2)

SCHED_BATCH用于標(biāo)識普通的批處理進(jìn)程，采用CFS調(diào)度算法。批處理進(jìn)程運(yùn)行在后臺，完成處理器密集型任務(wù)，很少交互，不需要被太多關(guān)注。

(3)

SCHED_IDLE用于標(biāo)識最低優(yōu)先級的普通進(jìn)程，采用CFS調(diào)度算法。

(4)

SCHED_FIFO用于標(biāo)識實(shí)時(shí)進(jìn)程，采用先進(jìn)先出調(diào)度算法，不記時(shí)間片。

(5)

SCHED_RR用于標(biāo)識實(shí)時(shí)進(jìn)程，采用RoundRobin調(diào)度算法，按時(shí)間片輪轉(zhuǎn)。4.優(yōu)先級和權(quán)重

優(yōu)先級用于標(biāo)識進(jìn)程的重要程度。調(diào)度器在選擇下一個(gè)投入運(yùn)行的進(jìn)程時(shí)要參考它的優(yōu)先級。進(jìn)程一次可運(yùn)行的時(shí)間長度(時(shí)間片)通常也取決于它的優(yōu)先級。

Linux為進(jìn)程定義了140個(gè)優(yōu)先級，其中0～99用于實(shí)時(shí)進(jìn)程，100～139用于普通進(jìn)程。值越小表示優(yōu)先級越高。普通進(jìn)程的缺省優(yōu)先級是120。每個(gè)進(jìn)程都有多個(gè)優(yōu)先級，記錄在它的task_struct結(jié)構(gòu)中，如下：

(1)

rt_priority是進(jìn)程的實(shí)時(shí)優(yōu)先級。與常規(guī)定義不同，值越大表示優(yōu)先級越高。

(2)

static_prio是進(jìn)程的靜態(tài)優(yōu)先級，其初值繼承自創(chuàng)建者進(jìn)程，并可被系統(tǒng)調(diào)用修改，但不會被調(diào)度器自動調(diào)整。

(3)

normal_prio是進(jìn)程的常規(guī)優(yōu)先級，其初值繼承自創(chuàng)建者進(jìn)程。通常情況下，普通進(jìn)程的normal_prio=static_prio，實(shí)時(shí)進(jìn)程的normal_prio=99-rt_priority。

(4)

prio是進(jìn)程的動態(tài)優(yōu)先級，其初值繼承自創(chuàng)建者進(jìn)程的常規(guī)優(yōu)先級，但可被調(diào)度器自動調(diào)整，普通進(jìn)程的優(yōu)先級甚至可以被提升到99以內(nèi)。

由于歷史的原因，用戶通常把進(jìn)程的靜態(tài)優(yōu)先級稱為nice，其值在-20～+19之間，對應(yīng)內(nèi)核優(yōu)先級的100～139，如圖7.3所示。

圖7.3進(jìn)程優(yōu)先級的取值范圍優(yōu)先級雖然重要，但內(nèi)核在調(diào)度時(shí)經(jīng)常使用的卻是進(jìn)程的權(quán)重(weight)。權(quán)重是根據(jù)優(yōu)先級計(jì)算出來的，優(yōu)先級越高，權(quán)重越大。權(quán)重的計(jì)算原則是：進(jìn)程的優(yōu)先級每提升一級，它的權(quán)重(得到的處理能力)應(yīng)提高10%。為了方便權(quán)重的計(jì)算，Linux預(yù)先定義了數(shù)組prio_to_weight，如下：

staticconstintprio_to_weight[40]={

/*100*/ 88761, 71755, 56483, 46273, 36291,

/*105*/ 29154, 23254, 18705, 14949, 11916,

/*110*/ 9548,

7620,

6100,

4904,

3906,

/*115*/ 3121,

2501,

1991,

1586,

1277,

/*120*/ 1024,

820, 655, 526, 423,

/*125*/ 335, 272, 215, 172, 137,

/*130*/ 110, 87, 70, 56, 45,

/*135*/ 36, 29, 23, 18, 15,

};

(1)實(shí)時(shí)進(jìn)程的權(quán)重=prio_to_weight[0]*2=88761*2；

(2)普通進(jìn)程的權(quán)重=prio_to_weight[static_prio-100]；

(3)調(diào)度策略為SCHED_IDLE的進(jìn)程的權(quán)重=3。

5.進(jìn)程狀態(tài)

早期的Linux定義了5種進(jìn)程狀態(tài)，分別是運(yùn)行狀態(tài)、可中斷等待狀態(tài)、不可中斷等待狀態(tài)、停止?fàn)顟B(tài)和僵死狀態(tài)。新版本的Linux定義了8種進(jìn)程狀態(tài)，如下：

(1)

TASK_RUNNING(運(yùn)行狀態(tài))表示進(jìn)程正在運(yùn)行或已準(zhǔn)備好運(yùn)行(就緒)。

(2)

TASK_INTERRUPTIBLE(可中斷等待狀態(tài))表示進(jìn)程在等待隊(duì)列中，正等待某個(gè)事件或資源。在此狀態(tài)下的進(jìn)程可以被信號自動喚醒。

(3)

TASK_UNINTERRUPTIBLE(不可中斷等待狀態(tài))表示進(jìn)程在等待隊(duì)列中，正等待被喚醒。處于這種狀態(tài)的進(jìn)程不會被信號自動喚醒。

(4)

_

_TASK_STOPPED(停止?fàn)顟B(tài))表示進(jìn)程被暫停，一般是被其它進(jìn)程暫停。處于停止?fàn)顟B(tài)的進(jìn)程還可以被恢復(fù)。

(5)

_

_TASK_TRACED(追蹤狀態(tài))表示進(jìn)程因被追蹤而暫停，是一種特殊的停止?fàn)顟B(tài)。

(6)

TASK_DEAD(死亡狀態(tài))表示進(jìn)程所執(zhí)行的程序已經(jīng)結(jié)束，它的資源已經(jīng)釋放，只剩余task_struct結(jié)構(gòu)等待被撤銷。

(7)

TASK_WAKEKILL(醒后終止?fàn)顟B(tài))表示進(jìn)程不管處于何種等待或停止?fàn)顟B(tài)，都可以被SIGKILL信號喚醒，而后終止。

(8)

TASK_WAKING(喚醒狀態(tài))表示進(jìn)程剛剛被喚醒，還未正常運(yùn)行。新版本的Linux還定義了2種退出狀態(tài)，分別是：

(1)

EXIT_ZOMBIE(僵死狀態(tài))表示進(jìn)程已進(jìn)入死亡狀態(tài)，且已向父進(jìn)程發(fā)送信號，正在等待父進(jìn)程響應(yīng)。

(2)

EXIT_DEAD(死亡狀態(tài))表示進(jìn)程已進(jìn)入死亡狀態(tài)，父進(jìn)程也已響應(yīng)它發(fā)送的信號，它的task_struct結(jié)構(gòu)正在被撤銷但還未撤銷完畢。

另外，在task_struct中還為進(jìn)程定義了一個(gè)位圖flags，用于進(jìn)一步標(biāo)志進(jìn)程的特性和狀態(tài)，如進(jìn)程是什么(VCPU、kswapd、內(nèi)核線程等)，進(jìn)程當(dāng)前在干什么(正在被創(chuàng)建、正在終止、創(chuàng)建后還未加載新程序、正在寫出核心內(nèi)存參數(shù)、被信號殺死、正在分配內(nèi)存、正在刷新磁盤、正在被凍結(jié)、已被凍結(jié)、正在文件系統(tǒng)事務(wù)內(nèi)部、正在清理內(nèi)存)，進(jìn)程有什么特殊能力(使用超級用戶特權(quán)、必須在使用前初始化FPU、不能被凍結(jié)、使用隨機(jī)的虛擬地址空間、可被換出)等。

在進(jìn)程生命周期中，它的狀態(tài)和標(biāo)志都會不斷變化。

6.進(jìn)程上下文

進(jìn)程的執(zhí)行是時(shí)斷時(shí)續(xù)的。當(dāng)進(jìn)程因?yàn)槟撤N原因必須讓出處理器時(shí)，它的上下文(處理現(xiàn)場)必須被暫存起來，以便當(dāng)再次被調(diào)度時(shí)能夠從暫停的位置恢復(fù)運(yùn)行。Linux在進(jìn)程task_struct結(jié)構(gòu)中嵌入了一個(gè)thread_struct結(jié)構(gòu)，用于記錄進(jìn)程的上下文。

在早期的版本中，thread_struct結(jié)構(gòu)大致相當(dāng)于一個(gè)任務(wù)狀態(tài)段(TSS)，其中包含進(jìn)程可能使用到的各種寄存器的值。新版本的Linux對thread_struct結(jié)構(gòu)進(jìn)行了調(diào)整，刪掉了不必要的通用寄存器，僅保存一些最必要的信息，如系統(tǒng)堆棧的棧底和棧頂、GS、EIP、CR2、Debug寄存器、error_code、IOPL、I/O許可位圖、浮點(diǎn)處理狀態(tài)等。7.虛擬地址空間

每個(gè)用戶態(tài)進(jìn)程都有自己的虛擬地址空間。進(jìn)程在用戶態(tài)運(yùn)行需要的所有信息，包括程序、數(shù)據(jù)、堆棧等，都保存在自己的虛擬地址空間中。進(jìn)程的虛擬地址空間被自然地劃分成了多個(gè)區(qū)域(區(qū)間)，每個(gè)區(qū)域都有著不同的屬性，如程序區(qū)可以執(zhí)行但不能修改、數(shù)據(jù)區(qū)可以讀寫但不能執(zhí)行、堆棧區(qū)可以動態(tài)增長等。為了管理的方便，Linux為每個(gè)虛擬內(nèi)存區(qū)域定義了一個(gè)vm_area_struct結(jié)構(gòu)，一個(gè)進(jìn)程的所有vm_area_struct結(jié)構(gòu)被組織成一個(gè)隊(duì)列和一棵紅黑樹，隊(duì)頭和樹根分別記錄在mm_struct結(jié)構(gòu)中。另外，mm_struct結(jié)構(gòu)中還記錄著與進(jìn)程虛擬內(nèi)存管理相關(guān)的其它信息，如頁目錄的位置，代碼、數(shù)據(jù)、堆棧、堆、環(huán)境變量、初始參數(shù)的存儲位置等。

Linux在task_struct結(jié)構(gòu)中定義了兩個(gè)指針mm和active_mm。普通用戶進(jìn)程的這兩個(gè)指針指向同一個(gè)mm_struct結(jié)構(gòu)，內(nèi)核線程的mm為空(沒有用戶態(tài)虛擬地址空間)，active_mm可指向任意一個(gè)進(jìn)程的mm_struct結(jié)構(gòu)(借用的虛擬地址空間)。

8.工作目錄

進(jìn)程在運(yùn)行過程中可能需要訪問文件系統(tǒng)，在訪問文件系統(tǒng)時(shí)需要解析文件的路徑名，而要解析路徑名則需要知道進(jìn)程的主目錄和當(dāng)前工作目錄。不同進(jìn)程可能有不同的主目錄和當(dāng)前工作目錄，因而Linux為每個(gè)進(jìn)程定義了一個(gè)fs_struct結(jié)構(gòu)，專門記錄它的目錄信息，其中root是進(jìn)程的主目錄，pwd是進(jìn)程的當(dāng)前工作目錄。

9.文件描述符

進(jìn)程在運(yùn)行過程中可能需要讀寫文件。按照Linux的約定，在讀寫文件之前需要先將其打開。進(jìn)程每打開一個(gè)文件，Linux都會為其創(chuàng)建一個(gè)打開文件對象(file結(jié)構(gòu))。為進(jìn)程創(chuàng)建的所有file結(jié)構(gòu)被組織在進(jìn)程的文件描述符表中，file結(jié)構(gòu)在文件描述符表中的索引就是文件的描述符。文件描述符是文件讀寫操作中必須提供的參數(shù)。

由于無法預(yù)估進(jìn)程打開文件的數(shù)量，因而進(jìn)程的文件描述符表不應(yīng)是一個(gè)靜態(tài)的數(shù)組，而應(yīng)能根據(jù)需要動態(tài)擴(kuò)展。Linux為每個(gè)進(jìn)程定義了一個(gè)files_struct結(jié)構(gòu)，專門用于管理進(jìn)程的文件描述符表。

10.信號處理方式

在Linux系統(tǒng)中，信號(Signal)是一種十分重要的通知手段。操作系統(tǒng)內(nèi)核和進(jìn)程可以向一個(gè)或一組進(jìn)程發(fā)送信號，以通報(bào)某些事件的發(fā)生。

為了處理信號，Linux在進(jìn)程的task_struct結(jié)構(gòu)中定義了多個(gè)管理結(jié)構(gòu)，包括blocked位圖(記錄進(jìn)程要阻塞的信號)，sigpending結(jié)構(gòu)(記錄進(jìn)程已收到的信號及其附加信息)，sighand_struct結(jié)構(gòu)記錄(進(jìn)程對各信號的處理程序及處理時(shí)的特殊要求)，signal_struct結(jié)構(gòu)(記錄各類時(shí)間間隔定時(shí)器的管理信息，如定時(shí)間隔、定時(shí)器的當(dāng)前值、進(jìn)程消耗的各類時(shí)間等)等。另外，線程組能夠使用的各類資源的上界記錄在signal_struct結(jié)構(gòu)的rlim數(shù)組中。規(guī)定了上界的資源包括處理器時(shí)間、優(yōu)先級、文件大小、數(shù)據(jù)大小、堆棧大小、可駐留內(nèi)存的頁數(shù)、可創(chuàng)建的進(jìn)程數(shù)、可打開的文件數(shù)等。

同一線程組中的進(jìn)程必須共享信號處理結(jié)構(gòu)，包括sighand_struct、signal_struct等。

11.名字空間

傳統(tǒng)操作系統(tǒng)所管理的信息大都是全局的，這些信息可以被每個(gè)進(jìn)程看到，且內(nèi)容都一樣，如系統(tǒng)名稱、版本號、進(jìn)程的PID號、文件系統(tǒng)目錄、網(wǎng)絡(luò)設(shè)置、活動用戶等。當(dāng)然，操作系統(tǒng)對進(jìn)程的能力進(jìn)行了限制，如一個(gè)用戶的進(jìn)程不能殺死另一個(gè)用戶的進(jìn)程，也不能訪問另一個(gè)用戶的文件等等。這種管理方法工作得很好，可以被一般用戶接受。但近年來，出于安全和虛擬化的考慮，人們提出了限制進(jìn)程可見信息的要求，即希望能為不同的進(jìn)程提供不同的全局信息。為此，Linux引入了名字空間(namespace)。一個(gè)名字空間實(shí)際上是系統(tǒng)的一種視圖(view)。兩個(gè)名字空間可以完全不同，也可以有部分重疊。每個(gè)進(jìn)程都必須與一個(gè)名字空間關(guān)聯(lián)，或者說屬于一個(gè)名字空間，多個(gè)進(jìn)程可以共用一個(gè)名字空間。共用一個(gè)名字空間的進(jìn)程能看到完全相同的系統(tǒng)信息，使用不同名字空間的進(jìn)程會看到不同的系統(tǒng)信息。

Linux用結(jié)構(gòu)nsproxy描述名字空間，其中包含5個(gè)名字空間結(jié)構(gòu)，如圖7.4所示。

圖7.4進(jìn)程名字空間

(1)

uts_namespace中定義了系統(tǒng)名、節(jié)點(diǎn)名、域名、版本號、機(jī)器名等。

(2)

ipc_namespace中定義了有關(guān)信號量、共享內(nèi)存、消息隊(duì)列等IPC機(jī)制的參數(shù)。

(3)

mnt_namespace中定義了有關(guān)文件系統(tǒng)安裝點(diǎn)的信息。

(4)

pid_namespace中定義了有關(guān)PID管理的信息，如PID位圖、回收進(jìn)程等。PID名字空間按層次結(jié)構(gòu)組織。一個(gè)進(jìn)程在它所屬的名字空間中有一個(gè)PID號，同時(shí)在所有的祖先名字空間中也都有一個(gè)PID號。

(5)

net中定義了與網(wǎng)絡(luò)配置相關(guān)的所有信息。

在圖7.4中，進(jìn)程2和3共享所有的名字空間，但與進(jìn)程1僅共享uts_namespace。

12.親緣關(guān)系

Linux的進(jìn)程之間有親緣關(guān)系。一般情況下，若進(jìn)程A創(chuàng)建了進(jìn)程B和C，那么A是B和C的父進(jìn)程，B和C是A的子進(jìn)程，B與C是兄弟進(jìn)程。按照親緣關(guān)系可將系統(tǒng)中所有的進(jìn)程組織成一棵家族樹。第0號進(jìn)程是所有進(jìn)程的祖先，是家族樹的根。

task_struct結(jié)構(gòu)中的real_parent指向進(jìn)程的父進(jìn)程。由于進(jìn)程的父進(jìn)程可能被改變，因而Linux又增加了指針parent，用于指示進(jìn)程的當(dāng)前父進(jìn)程。一個(gè)進(jìn)程的所有子進(jìn)程都被掛在它的children隊(duì)列中，越靠近隊(duì)頭的進(jìn)程越年輕，越靠近隊(duì)尾的進(jìn)程越年老。children隊(duì)列中的進(jìn)程互為兄弟，節(jié)點(diǎn)sibling用于連接兄弟進(jìn)程。如圖7.5所示。

圖7.5進(jìn)程的親緣關(guān)系

進(jìn)程是被動態(tài)創(chuàng)建出來的，創(chuàng)建的目的是為了執(zhí)行程序。進(jìn)程的創(chuàng)建過程大致可分為兩步，一是創(chuàng)建進(jìn)程的管理結(jié)構(gòu)，即以task_struct為核心的進(jìn)程控制塊；二是為進(jìn)程加載應(yīng)用程序，即為進(jìn)程創(chuàng)建虛擬地址空間并設(shè)置初始參數(shù)和環(huán)境變量，做好運(yùn)行前的準(zhǔn)備。當(dāng)進(jìn)程被調(diào)度運(yùn)行(獲得處理器)時(shí)，進(jìn)程即會從入口地址開始執(zhí)行程序。7.2進(jìn)程創(chuàng)建有些操作系統(tǒng)用一個(gè)系統(tǒng)調(diào)用完成上述兩步進(jìn)程創(chuàng)建工作，另一些操作系統(tǒng)用兩個(gè)系統(tǒng)調(diào)用分別完成。兩種實(shí)現(xiàn)方法各有優(yōu)劣，但兩階段創(chuàng)建方法繼承了傳統(tǒng)Unix一貫的優(yōu)雅作風(fēng)，將復(fù)雜的工作分解成相互關(guān)聯(lián)又相互獨(dú)立的兩部分，輕松地解除了進(jìn)程與程序的綁定關(guān)系。Linux采用兩階段創(chuàng)建方法，其中的進(jìn)程可以根據(jù)需要隨時(shí)、隨地更換自己的程序，因而進(jìn)程更加獨(dú)立，也更加靈活。

Linux用fork類的系統(tǒng)調(diào)用實(shí)現(xiàn)進(jìn)程的創(chuàng)建，用execve類的系統(tǒng)調(diào)用實(shí)現(xiàn)程序的加載。進(jìn)程的管理結(jié)構(gòu)比較容易創(chuàng)建。事實(shí)上，新進(jìn)程的很多管理信息是從創(chuàng)建者進(jìn)程中繼承來的，如優(yōu)先級等，雖然也有一些信息是自己特有的，如PID等。進(jìn)程創(chuàng)建的主要問題是如何為新進(jìn)程加載應(yīng)用程序。

Linux的解決辦法是讓新進(jìn)程與創(chuàng)建者進(jìn)程運(yùn)行同樣的程序但又不從頭開始。具體的做法是將創(chuàng)建者進(jìn)程的虛擬地址空間完整地復(fù)制到新進(jìn)程中，使新老進(jìn)程擁有完全相同的程序、數(shù)據(jù)、堆棧，因而當(dāng)新進(jìn)程首次開始運(yùn)行時(shí)，它具有與創(chuàng)建者進(jìn)程完全相同的行為，所不同的僅僅是fork()函數(shù)的返回值。根據(jù)fork()的返回值，進(jìn)程可以區(qū)分出自己是創(chuàng)建者還是新生命，從而決定自己下一步的工作，如加載應(yīng)用程序等。這種方法將程序加載的決定權(quán)交給了進(jìn)程(或者說應(yīng)用程序)，非常靈活。

復(fù)制進(jìn)程虛擬地址空間的問題是工作量過大。如果新進(jìn)程運(yùn)行后會立刻加載自己的應(yīng)用程序，復(fù)制工作就純粹是一種浪費(fèi)。為此Linux提供了兩種改進(jìn)：

(1)完全共享，讓新老進(jìn)程共用同一個(gè)虛擬地址空間。

(2)寫時(shí)復(fù)制(CopyonWrite)，僅復(fù)制管理信息，使新老進(jìn)程共享同樣的虛擬地址空間但都不許修改，將空間復(fù)制工作推遲到寫操作發(fā)生時(shí)(一種典型的Lazy做法)。

Linux提供了三種進(jìn)程創(chuàng)建方式，其中fork()用于普通進(jìn)程的創(chuàng)建，采用CopyonWrite方式復(fù)制虛擬地址空間；vfork()用于特殊進(jìn)程的創(chuàng)建，創(chuàng)建者進(jìn)程將自己的虛擬地址空間借給新進(jìn)程，并等待新進(jìn)程終止或加載程序；clone()用于線程的創(chuàng)建，由創(chuàng)建者指定新老雙方共享的信息。三個(gè)系統(tǒng)調(diào)用由同一個(gè)函數(shù)do_fork()實(shí)現(xiàn)。函數(shù)do_fork()的參數(shù)中有三個(gè)重要參數(shù)，其中位圖clone_flags界定了新老進(jìn)程可以共享的資源及新進(jìn)程的退出信號，regs是指向結(jié)構(gòu)pt_regs的指針，表示創(chuàng)建者進(jìn)程系統(tǒng)堆棧的棧底布局，stack_start是新進(jìn)程用戶堆棧的棧頂位置(一般情況下就是regs.sp)。進(jìn)程創(chuàng)建的主要工作流程如下：

(1)向?qū)ο髢?nèi)存管理器申請一個(gè)task_struct結(jié)構(gòu)，將當(dāng)前進(jìn)程(即創(chuàng)建者進(jìn)程)的task_struct結(jié)構(gòu)的內(nèi)容全部復(fù)制到其中。將新進(jìn)程的引用計(jì)數(shù)設(shè)為2。

(2)向伙伴內(nèi)存管理器申請2頁的物理內(nèi)存用于新進(jìn)程的系統(tǒng)堆棧。將當(dāng)前進(jìn)程的thread_info結(jié)構(gòu)復(fù)制到新堆棧的開始位置，作為新進(jìn)程的thread_info，并在新進(jìn)程的thread_info與task_struct之間建立關(guān)聯(lián)(如圖7.1)。如果創(chuàng)建者特別聲明，新進(jìn)程的系統(tǒng)堆棧可以僅用1頁。

(3)為新進(jìn)程建立認(rèn)證信息，即cred結(jié)構(gòu)。如果新老進(jìn)程屬于同一個(gè)線程組，則讓它們共用一個(gè)cred結(jié)構(gòu)，否則為新進(jìn)程建立單獨(dú)的cred結(jié)構(gòu)。

(4)調(diào)整新進(jìn)程的某些管理信息，如標(biāo)志flags、時(shí)間消耗量(utime、stime等)、創(chuàng)建時(shí)間start_time等。

(5)設(shè)置新進(jìn)程的調(diào)度信息，包括調(diào)度實(shí)體se、將要運(yùn)行該進(jìn)程的處理器、優(yōu)先級、調(diào)度類等，將新進(jìn)程的狀態(tài)設(shè)為TASK_RUNNING。

(6)為新進(jìn)程建立undo隊(duì)列。如果創(chuàng)建者請求共享，則讓新老進(jìn)程共用同一個(gè)undo隊(duì)列，否則將新進(jìn)程的undo隊(duì)列設(shè)為空。

(7)為新進(jìn)程建立files_struct結(jié)構(gòu)。如果創(chuàng)建者請求共享，則讓新老進(jìn)程共用同一個(gè)files_struct結(jié)構(gòu)，否則從創(chuàng)建者進(jìn)程中復(fù)制一個(gè)files_struct結(jié)構(gòu)。

(8)為新進(jìn)程建立fs_struct結(jié)構(gòu)。如果創(chuàng)建者請求共享，則讓新老進(jìn)程共用同一個(gè)fs_struct結(jié)構(gòu)，否則從創(chuàng)建者進(jìn)程中復(fù)制一個(gè)fs_struct結(jié)構(gòu)。

(9)為新進(jìn)程建立sighand_struct結(jié)構(gòu)。如果創(chuàng)建者請求共享，則讓新老進(jìn)程共用同一個(gè)sighand_struct結(jié)構(gòu)，否則從創(chuàng)建者進(jìn)程中復(fù)制一個(gè)sighand_struct結(jié)構(gòu)。

(10)為新進(jìn)程建立signal_struct結(jié)構(gòu)。如果新老進(jìn)程屬于同一個(gè)線程組，則讓它們共用同一個(gè)signal_struct結(jié)構(gòu)，否則為新進(jìn)程新建一個(gè)signal_struct結(jié)構(gòu)，并從創(chuàng)建者進(jìn)程中復(fù)制資源上界(數(shù)組rlim)等信息。結(jié)構(gòu)signal_struct中的內(nèi)容基本都是新建的，如各類間隔定時(shí)器及統(tǒng)計(jì)信息等，新老進(jìn)程重復(fù)的內(nèi)容不多。

(11)為新進(jìn)程建立mm_struct結(jié)構(gòu)。如果創(chuàng)建者請求共享，則讓新老進(jìn)程共用同一個(gè)mm_struct結(jié)構(gòu)，否則為新進(jìn)程新建一個(gè)mm_struct結(jié)構(gòu)，包括：①創(chuàng)建頁目錄。新頁目錄的內(nèi)核部分是從swapper_pg_dir中拷貝過來的。

②創(chuàng)建LDT。如果創(chuàng)建者進(jìn)程定義了LDT，則為新進(jìn)程復(fù)制一個(gè)。

③復(fù)制創(chuàng)建者進(jìn)程的所有虛擬內(nèi)存區(qū)域(新老vm_area_struct結(jié)構(gòu)位于同樣的逆向映射隊(duì)列中)和區(qū)域內(nèi)的各個(gè)頁表項(xiàng)，但不復(fù)制內(nèi)存頁。新進(jìn)程的頁表是在復(fù)制過程中逐個(gè)建立的。新老進(jìn)程中的頁都是只讀的。

不管共享與否，新進(jìn)程的虛擬地址空間都與創(chuàng)建者進(jìn)程完全一致。圖7.6是復(fù)制后新老進(jìn)程的虛擬地址空間，兩者的管理結(jié)構(gòu)獨(dú)立但內(nèi)容完全相同。

(12)為新進(jìn)程建立名字空間。如果創(chuàng)建者請求共享，則讓新老進(jìn)程共用同一個(gè)nsproxy結(jié)構(gòu)，否則為新進(jìn)程新建一個(gè)nsproxy結(jié)構(gòu)，并根據(jù)創(chuàng)建者的請求共享或新建各子名字空間結(jié)構(gòu)。

(13)為新進(jìn)程建立io_context結(jié)構(gòu)。結(jié)構(gòu)io_context用于記錄與進(jìn)程相關(guān)的I/O子系統(tǒng)的狀態(tài)。如果創(chuàng)建者請求共享，則讓新老進(jìn)程共用同一個(gè)io_context結(jié)構(gòu)，否則為新進(jìn)程新建一個(gè)io_context結(jié)構(gòu)。

圖7.6復(fù)制后子進(jìn)程的虛擬地址空間

(14)為新進(jìn)程建立執(zhí)行環(huán)境，包括：

①將創(chuàng)建者進(jìn)程系統(tǒng)堆棧的棧底(參數(shù)regs)復(fù)制到新進(jìn)程的系統(tǒng)堆棧中(棧底留8字節(jié))，將其中的ax改為0。如果創(chuàng)建者為新進(jìn)程指定了新的用戶堆棧，則將新進(jìn)程堆底的sp改為新堆棧的棧頂(參數(shù)stack_start)。

②修改新進(jìn)程的thread_struct結(jié)構(gòu)。讓新進(jìn)程thread_struct結(jié)構(gòu)中的sp指向自己系統(tǒng)堆棧的棧頂、sp0指向系統(tǒng)堆棧的棧底(間隔一個(gè)pt_regs結(jié)構(gòu))、ip指向ret_from_fork(系統(tǒng)調(diào)用的出口程序)。如圖7.7所示。

③如果創(chuàng)建者進(jìn)程定義了I/O許可位圖，則將其復(fù)制到新進(jìn)程中。結(jié)構(gòu)thread_struct中的io_bitmap_ptr指向I/O許可位圖。

圖7.7新老進(jìn)程的管理結(jié)構(gòu)與系統(tǒng)堆棧

(15)為新進(jìn)程分配PID。根據(jù)新進(jìn)程名字空間的定義為其新建一個(gè)pid結(jié)構(gòu)，在各相關(guān)名字空間中分別為新進(jìn)程分配PID號，建立新進(jìn)程與pid結(jié)構(gòu)的關(guān)聯(lián)，將pid的各子結(jié)構(gòu)(upid)插入到Hash表pid_hash中，并確定新進(jìn)程的PID和TGID號。

(16)確定新進(jìn)程的退出信號。如果新老進(jìn)程屬于同一個(gè)線程組，則將新進(jìn)程的退出信號設(shè)為-1，否則根據(jù)參數(shù)clone_flags設(shè)置它的退出信號，一般是SIGCHLD。

(17)為新進(jìn)程建立親緣關(guān)系。在早期的版本中，新進(jìn)程肯定是創(chuàng)建者進(jìn)程的子進(jìn)程。但在新版本中，如果新老進(jìn)程屬于同一個(gè)線程組，那么新進(jìn)程就是自己的兄弟。在確定新進(jìn)程的父進(jìn)程之后，將新進(jìn)程的task_struct結(jié)構(gòu)插入到父進(jìn)程的children隊(duì)列中。如果新老進(jìn)程屬于一個(gè)線程組，還要將新進(jìn)程的task_struct結(jié)構(gòu)插入到領(lǐng)頭進(jìn)程的thread_group隊(duì)列中。

(18)喚醒新進(jìn)程。將新進(jìn)程插入到所選處理器的就緒隊(duì)列中，等待調(diào)度。

(19)如果新進(jìn)程是由vfork()創(chuàng)建的，則將創(chuàng)建者進(jìn)程插入到新進(jìn)程的等待隊(duì)列vfork_done中，而后讓創(chuàng)建者進(jìn)程放棄處理器(請求調(diào)度)，停止運(yùn)行。當(dāng)新進(jìn)程終止或加載應(yīng)用程序時(shí)，它會喚醒在vfork_done中等待的進(jìn)程。

上述過程所創(chuàng)建的新進(jìn)程擁有完全獨(dú)立的task_struct結(jié)構(gòu)和系統(tǒng)堆棧，但其內(nèi)容大都來源于創(chuàng)建者進(jìn)程。不管共享與否，新進(jìn)程所打開的文件及各文件的描述符、根和當(dāng)前工作目錄、信號處理方式等都與創(chuàng)建者進(jìn)程完全一致。尤其是新進(jìn)程擁有與創(chuàng)建者進(jìn)程完全一致的虛擬地址空間。因而，進(jìn)程創(chuàng)建的本質(zhì)實(shí)際上是復(fù)制或者說是克隆，創(chuàng)建者通過進(jìn)程創(chuàng)建操作創(chuàng)造了一個(gè)自己的克隆體。

當(dāng)進(jìn)程創(chuàng)建工作完成之后，創(chuàng)建者進(jìn)程完成了一次正常的系統(tǒng)調(diào)用，函數(shù)fork()、vfork()或clone()正常返回，其返回值是新進(jìn)程的PID號。當(dāng)然新進(jìn)程可能有多個(gè)PID號，但此處返回的僅是新進(jìn)程在創(chuàng)建者名字空間中的PID號。當(dāng)新進(jìn)程被首次調(diào)度運(yùn)行時(shí)，調(diào)度程序根據(jù)新進(jìn)程的thread_struct結(jié)構(gòu)設(shè)置處理器的寄存器，將ESP設(shè)為新進(jìn)程系統(tǒng)堆棧的棧頂，將EIP設(shè)為ret_from_fork。因而，新進(jìn)程從程序ret_from_fork開始執(zhí)行。正常情況下，程序ret_from_fork逐個(gè)彈出系統(tǒng)堆棧的棧頂，用其中的值設(shè)置處理器的寄存器，包括EBX、ECX、EDX、ESI、EDI、EBP、EAX、DS、ES、FS、GS、EIP、CS、EFLAGS、ESP、SS等。由于新進(jìn)程的系統(tǒng)堆棧與創(chuàng)建者進(jìn)程完全一致(除EAX之外)，因而新進(jìn)程的返回地址及返回后的處理器環(huán)境都與創(chuàng)建者進(jìn)程相同，新進(jìn)程仿佛從函數(shù)fork()、vfork()或clone()中正常返回一樣，只是其返回值是0。返回到用戶態(tài)之后，由于新進(jìn)程的程序、數(shù)據(jù)、堆棧都與創(chuàng)建者進(jìn)程一致，因而新進(jìn)程與創(chuàng)建者進(jìn)程擁有完全相同的行為，唯一的區(qū)別是返回值。

隨著不斷地創(chuàng)建，系統(tǒng)中肯定會出現(xiàn)多個(gè)進(jìn)程，甚至?xí)瑫r(shí)出現(xiàn)多個(gè)就緒態(tài)進(jìn)程。處于就緒狀態(tài)的進(jìn)程所缺少的資源僅有處理器，一旦獲得處理器，就緒態(tài)進(jìn)程即可立即投入運(yùn)行。由于系統(tǒng)中的處理器數(shù)通常遠(yuǎn)少于進(jìn)程數(shù)，因而進(jìn)程對處理器資源的競爭是不可避免的。7.3進(jìn)程調(diào)度為了使競爭更加有序，使處理器的分配更加合理，使進(jìn)程的運(yùn)行更加公平，需要一個(gè)仲裁者來管理處理器的分配或者說協(xié)調(diào)進(jìn)程的運(yùn)行，Linux稱這一仲裁者為調(diào)度器(Scheduler)。毫無疑問，調(diào)度器是操作系統(tǒng)的核心。7.3.1Linux調(diào)度器的演變

早期的Linux采用一種極為簡潔的調(diào)度器，它將系統(tǒng)中所有就緒態(tài)進(jìn)程的task_struct結(jié)構(gòu)組織在一個(gè)隊(duì)列中，稱為單就緒隊(duì)列，第0號進(jìn)程的PCB結(jié)構(gòu)init_task充當(dāng)隊(duì)頭。當(dāng)時(shí)間片耗盡、程序執(zhí)行完畢、需要等待資源或事件時(shí)，當(dāng)前進(jìn)程主動執(zhí)行調(diào)度程序，將處理器讓給下一個(gè)進(jìn)程。進(jìn)程調(diào)度的過程如下：

(1)調(diào)整就緒隊(duì)列，如將非就緒態(tài)的進(jìn)程從隊(duì)列中摘除。

(2)順序搜索就緒隊(duì)列，取出各進(jìn)程的調(diào)度策略policy、普通優(yōu)先級priority、實(shí)時(shí)優(yōu)先級rt_priority、剩余時(shí)間片counter等調(diào)度信息，據(jù)此計(jì)算出各進(jìn)程的權(quán)重(weight)，選擇權(quán)重最大的進(jìn)程為下一個(gè)投入運(yùn)行進(jìn)程。權(quán)重的計(jì)算規(guī)則是：

①如果當(dāng)前進(jìn)程明確聲明要放棄處理器，則權(quán)重weight=0；

②實(shí)時(shí)進(jìn)程的權(quán)重weight=rt_priority+1000；

③無剩余時(shí)間片的普通進(jìn)程的權(quán)重weight=0；

④有剩余時(shí)間片的普通進(jìn)程的權(quán)重weight=counter+priority；⑤如果算出的最大weight值是0，則將所有進(jìn)程的時(shí)間片重設(shè)為counter=(counter>>1)+priority，而后重算各就緒進(jìn)程的weight值。

(3)如果選出的下一個(gè)進(jìn)程不是當(dāng)前進(jìn)程，則將處理器的現(xiàn)場保存在當(dāng)前進(jìn)程的任務(wù)狀態(tài)段中，而后用下一個(gè)進(jìn)程的任務(wù)狀態(tài)段恢復(fù)處理器現(xiàn)場，從而將處理器切換給新選出的進(jìn)程。

對上述調(diào)度器來說，實(shí)時(shí)進(jìn)程優(yōu)于普通進(jìn)程；運(yùn)行時(shí)間短的普通進(jìn)程優(yōu)于運(yùn)行時(shí)間長的普通進(jìn)程；進(jìn)程優(yōu)先級越高，時(shí)間片就越長；進(jìn)程等待時(shí)間越長，剩余時(shí)間片就會越長，就緒后的權(quán)重就越大；時(shí)間片耗完的進(jìn)程不參與調(diào)度，給小優(yōu)先級進(jìn)程提供了運(yùn)行的機(jī)會；只有當(dāng)就緒隊(duì)列為空時(shí)才會選中init_task進(jìn)程。

基于單就緒隊(duì)列的調(diào)度器雖然簡單，但每次調(diào)度都需要遍歷整個(gè)就緒隊(duì)列，因而調(diào)度時(shí)間會隨就緒進(jìn)程數(shù)的變化而變化(算法的復(fù)雜度為O(n))，而且多處理器共用同一個(gè)就緒隊(duì)列也會引起不必要的競爭，因而不大適合多處理器環(huán)境。為解決上述問題，Linux走向了另一個(gè)極端，在Linux2.6中引入了一種稱為O(1)的全新調(diào)度器。O(1)調(diào)度器為每一個(gè)處理器定義了140個(gè)就緒隊(duì)列(稱為隊(duì)列組)，用于組織在各處理器上等待的、不同優(yōu)先級的就緒進(jìn)程。其中0～99隊(duì)列用于實(shí)時(shí)進(jìn)程，100～139隊(duì)列用于普通進(jìn)程。序號越小，優(yōu)先級越高。

由于不是每個(gè)隊(duì)列上都有就緒進(jìn)程，因而O(1)調(diào)度器為每個(gè)隊(duì)列組都另外定義了一個(gè)位圖，用于記錄各隊(duì)列的狀態(tài)(是否為空)。通過隊(duì)列組位圖可以方便地找到序號最小的非空隊(duì)列(可由一條指令完成)，進(jìn)而找到下一個(gè)應(yīng)該運(yùn)行的進(jìn)程(隊(duì)頭進(jìn)程)。進(jìn)程的選擇工作可在常量時(shí)間內(nèi)完成，選擇時(shí)間與就緒進(jìn)程的數(shù)量無關(guān)，調(diào)度算法的復(fù)雜度是O(1)。另外，由于每個(gè)處理器僅需要訪問自己的就緒隊(duì)列組，處理器之間不再需要競爭，因而O(1)調(diào)度器更加適合多處理器環(huán)境，雖然它帶來了負(fù)載平衡問題。

多就緒隊(duì)列的問題是如果系統(tǒng)中一直存在高優(yōu)先級的就緒進(jìn)程，低優(yōu)先級的進(jìn)程就永遠(yuǎn)得不到運(yùn)行機(jī)會，會被餓死。因而在采用多就緒隊(duì)列的系統(tǒng)中，進(jìn)程的優(yōu)先級必須是動態(tài)可調(diào)的，或者說進(jìn)程在就緒隊(duì)列組中的位置應(yīng)該是浮動的。一般情況下，進(jìn)程運(yùn)行時(shí)間越長，優(yōu)先級應(yīng)該越低，等待時(shí)間越長，優(yōu)先級應(yīng)該越高。然而在實(shí)際操作中，優(yōu)先級的調(diào)整是一件十分復(fù)雜的工作，目前還未找到一種普適的算法來確定優(yōu)先級調(diào)整的時(shí)機(jī)和調(diào)整的幅度。O(1)調(diào)度器根據(jù)一些經(jīng)驗(yàn)公式來調(diào)整進(jìn)程的優(yōu)先級，這些經(jīng)驗(yàn)公式增加了代碼的復(fù)雜性，使O(1)調(diào)度器變得難以理解、難以評估，且容易失效。新版本的Linux僅用O(1)調(diào)度器調(diào)度實(shí)時(shí)進(jìn)程，新引入了完全公平調(diào)度器(CompletelyFairScheduler，CFS)來調(diào)度普通進(jìn)程。事實(shí)上，在設(shè)計(jì)調(diào)度器時(shí)，有兩個(gè)核心問題是必須要解決的，其一是如何選擇下一個(gè)投入運(yùn)行的進(jìn)程，其二是如何確定它的最長運(yùn)行時(shí)間(時(shí)間片)。比較簡單的解決辦法是讓等待時(shí)間最長的進(jìn)程投入運(yùn)行，但僅讓它運(yùn)行一個(gè)時(shí)間單位(如一個(gè)滴答)，如圖7.8(a)所示。這種方法實(shí)際上就是簡單的輪轉(zhuǎn)(RoundRobin)調(diào)度法，雖然貌似公平，但由于忽略了進(jìn)程的優(yōu)先級，因而并不合理。對簡單輪轉(zhuǎn)法的一種改進(jìn)是根據(jù)優(yōu)先級選擇進(jìn)程和確定時(shí)間片，即讓高優(yōu)先級的進(jìn)程先投入運(yùn)行，并讓它運(yùn)行較長的時(shí)間。在圖7.8(b)中，進(jìn)程1的優(yōu)先級最高，因而最先運(yùn)行，且一次運(yùn)行的時(shí)間也最長。這種調(diào)度方法能使高優(yōu)先級的進(jìn)程得到更好的服務(wù)，但卻會使低優(yōu)先級的進(jìn)程等待更長的時(shí)間，因而也不夠公平。

圖7.8傳統(tǒng)的進(jìn)程調(diào)度方法

CFS調(diào)度器是對簡單輪轉(zhuǎn)法的又一種改進(jìn)。它給每個(gè)進(jìn)程定義了一個(gè)虛擬計(jì)時(shí)器，用于記錄該進(jìn)程已消耗的處理器時(shí)間。不同進(jìn)程的虛擬計(jì)時(shí)器按照不同的速率計(jì)時(shí)，高優(yōu)先級進(jìn)程的虛擬計(jì)時(shí)器走得慢，低優(yōu)先級進(jìn)程的虛擬計(jì)時(shí)器走得快。虛擬計(jì)時(shí)器走得最慢的進(jìn)程就是運(yùn)行時(shí)間最少或等待時(shí)間最長的進(jìn)程。在每次時(shí)鐘中斷發(fā)生時(shí)，CFS都累計(jì)當(dāng)前進(jìn)程的虛擬計(jì)時(shí)器，并檢查就緒隊(duì)列，總是讓虛擬計(jì)時(shí)器最慢的進(jìn)程投入下一次運(yùn)行。在圖7.9中，進(jìn)程1、2、3的優(yōu)先級分別是8、3、2，CFS的調(diào)度順序如(a)所示，純粹按優(yōu)先級的調(diào)度順序如(b)所示。顯然，CFS既照顧到了高優(yōu)先級進(jìn)程，又不至于使低優(yōu)先級進(jìn)程等待過長時(shí)間。隨著時(shí)間的推移，所有進(jìn)程的虛擬計(jì)時(shí)器都趨向于勻速前進(jìn)，進(jìn)程的運(yùn)行更加平穩(wěn)，調(diào)度器的表現(xiàn)也更加公平。圖7.9CFS與基于優(yōu)先級的調(diào)度雖然CFS的表現(xiàn)更加公平，但也難以滿足所有的調(diào)度需求。為了適應(yīng)不同的應(yīng)用環(huán)境，新版本的Linux引入了一個(gè)調(diào)度器框架，試圖通過組合多種不同的調(diào)度算法來滿足不同種類的調(diào)度需求。新的調(diào)度器框架將進(jìn)程分成三大類，即實(shí)時(shí)進(jìn)程、普通進(jìn)程和空閑進(jìn)程，并為每一類就緒進(jìn)程定義了不同的管理方法，如用就緒隊(duì)列組管理實(shí)時(shí)類進(jìn)程、用紅黑樹管理普通類進(jìn)程、用一個(gè)指針管理空閑進(jìn)程等，如圖7.10所示。

圖7.10通用調(diào)度器框架調(diào)度器框架定義了稱為調(diào)度類的標(biāo)準(zhǔn)接口操作集，用于將不同的管理方法組合在一起，使它們對外表現(xiàn)為一個(gè)統(tǒng)一的通用調(diào)度器。調(diào)度類由結(jié)構(gòu)sched_class定義，其中包含與就緒隊(duì)列管理和進(jìn)程調(diào)度相關(guān)的各種操作。

調(diào)度類中的主要操作有如下幾個(gè)：

(1)入隊(duì)操作enqueue_task用于將一個(gè)進(jìn)程加入就緒隊(duì)列。

(2)出隊(duì)操作dequeue_task用于將一個(gè)進(jìn)程從就緒隊(duì)列中摘下。

(3)讓出操作yield_task用于聲明當(dāng)前進(jìn)程自愿讓出處理器。

(4)搶占檢查操作check_preempt_curr用于確定當(dāng)前進(jìn)程是否可被新進(jìn)程搶占。

(5)選出操作pick_next_task用于選擇下一個(gè)最值得運(yùn)行的進(jìn)程。

(6)歸還操作put_prev_task用于將當(dāng)前進(jìn)程歸還給就緒隊(duì)列。

(7)重置操作set_curr_task用于把當(dāng)前進(jìn)程重置為隊(duì)列的當(dāng)前進(jìn)程。

(8)更新操作task_tick用于更新當(dāng)前進(jìn)程的時(shí)間信息。

(9)新醒操作task_fork用于喚醒一個(gè)新建的、還未運(yùn)行過的進(jìn)程。

(10)優(yōu)先級改變操作prio_changed用于聲明進(jìn)程的優(yōu)先級已被改變。

(11)調(diào)度類切換操作switched_to用于聲明進(jìn)程的調(diào)度類已改變。

Linux為每一類進(jìn)程都實(shí)現(xiàn)了一個(gè)調(diào)度類，如實(shí)時(shí)進(jìn)程調(diào)度類rt_sched_class、普通進(jìn)程調(diào)度類fair_sched_class、空閑進(jìn)程調(diào)度類idle_sched_class等。在任何一個(gè)時(shí)刻，一個(gè)進(jìn)程僅屬于一個(gè)調(diào)度類，但允許改變。當(dāng)用戶請求且條件許可時(shí)，一個(gè)普通進(jìn)程可轉(zhuǎn)化成實(shí)時(shí)進(jìn)程，一個(gè)實(shí)時(shí)進(jìn)程也可轉(zhuǎn)化成普通進(jìn)程。但普通進(jìn)程和實(shí)時(shí)進(jìn)程都不能轉(zhuǎn)化成空閑進(jìn)程，空閑進(jìn)程也不能轉(zhuǎn)化成普通進(jìn)程或?qū)崟r(shí)進(jìn)程。結(jié)構(gòu)task_struct中的域sched_class指向進(jìn)程所屬的調(diào)度類。系統(tǒng)中所有的調(diào)度類按實(shí)時(shí)、普通、空閑的順序組成一個(gè)隊(duì)列，隊(duì)頭為sched_class_highest。為了統(tǒng)一管理三種不同的調(diào)度類，Linux為每個(gè)處理器定義了一個(gè)rq結(jié)構(gòu)，其中包含三種就緒進(jìn)程隊(duì)列和一些管理信息，如隊(duì)列中的就緒進(jìn)程總數(shù)nr_running、隊(duì)列的當(dāng)前總負(fù)載load、隊(duì)列的當(dāng)前時(shí)間clock(最近一次更新的實(shí)際時(shí)間，單位為ns)、高精度定時(shí)器hrtick_timer、處理器負(fù)載統(tǒng)計(jì)cpu_load[]等。7.3.2普通進(jìn)程調(diào)度類

普通類進(jìn)程采用CFS調(diào)度算法，它所需要的是一個(gè)按虛擬計(jì)時(shí)器由小到大排序的就緒進(jìn)程隊(duì)列。隊(duì)頭進(jìn)程的虛擬計(jì)時(shí)器走得最慢，是下一個(gè)應(yīng)調(diào)度運(yùn)行的進(jìn)程。雖然用一個(gè)標(biāo)準(zhǔn)的通用鏈表即可實(shí)現(xiàn)就緒隊(duì)列，但為了加快插入、搜索的速度，CFS選用了紅黑樹來組織、管理普通的就緒態(tài)進(jìn)程。

普通進(jìn)程的就緒隊(duì)列由結(jié)構(gòu)cfs_rq定義，其中的主要內(nèi)容有以下幾個(gè)：

(1)紅黑樹的樹根tasks_timeline。

(2)紅黑樹中最左端的葉子節(jié)點(diǎn)rb_leftmost，即隊(duì)頭節(jié)點(diǎn)。

(3)隊(duì)列中當(dāng)前正在運(yùn)行的進(jìn)程curr。

(4)隊(duì)列中建議的下一個(gè)運(yùn)行進(jìn)程next。

(5)隊(duì)列中剛剛被搶占的進(jìn)程last。

(6)隊(duì)列中當(dāng)前的就緒進(jìn)程數(shù)nr_running。

(7)隊(duì)列的當(dāng)前總負(fù)載load。負(fù)載最重的處理器是最忙的處理器。

(8)隊(duì)列的當(dāng)前虛擬時(shí)間min_vruntime(隊(duì)列中虛擬計(jì)時(shí)器的基準(zhǔn)值，單調(diào)增長)。隊(duì)列中正在運(yùn)行的進(jìn)程由curr指示，不在紅黑樹中，因而curr與rb_leftmost所指示的不是同一個(gè)進(jìn)程。下一個(gè)應(yīng)運(yùn)行的進(jìn)程必是rb_leftmost、next、last中的一個(gè)。

在進(jìn)程的task_struct結(jié)構(gòu)中嵌有一個(gè)調(diào)度實(shí)體，該實(shí)體由結(jié)構(gòu)sched_entity定義，用于記錄進(jìn)程的調(diào)度信息，如進(jìn)程的權(quán)重load、進(jìn)程已運(yùn)行的虛擬總時(shí)間(虛擬計(jì)時(shí)器)vruntime、進(jìn)程已運(yùn)行的實(shí)際總時(shí)間sum_exec_runtime、進(jìn)程之前運(yùn)行的實(shí)際總時(shí)間(不含本次運(yùn)行時(shí)間)prev_sum_exec_runtime、進(jìn)程本次運(yùn)行的實(shí)際開始時(shí)間exec_start等。就緒態(tài)的普通進(jìn)程通過調(diào)度實(shí)體中的run_node域?qū)⒆约烘溄拥郊t黑樹中。上述所有的時(shí)間都以納秒(ns)為單位。

CFS調(diào)度器的核心是維護(hù)進(jìn)程的虛擬計(jì)時(shí)器vruntime。由于一個(gè)處理器在一個(gè)時(shí)刻只能運(yùn)行一個(gè)進(jìn)程(當(dāng)前進(jìn)程)，所以在一個(gè)處理器上只有當(dāng)前進(jìn)程的虛擬計(jì)時(shí)器是走動的，其余進(jìn)程的虛擬計(jì)時(shí)器都處于停止?fàn)顟B(tài)，不需要調(diào)整。為了使當(dāng)前進(jìn)程的虛擬計(jì)時(shí)器走得更加平穩(wěn)，只要有機(jī)會，如在周期性時(shí)鐘中斷處理時(shí)、在有進(jìn)程入隊(duì)或出隊(duì)時(shí)、在有進(jìn)程被喚醒時(shí)等，CFS都會更新當(dāng)前進(jìn)程的虛擬計(jì)時(shí)器。更新的依據(jù)是rq結(jié)構(gòu)中的clock、當(dāng)前進(jìn)程調(diào)度實(shí)體中的exec_start和load，更新的方法如下：

delta_exec=(unsignedlong)(clock-curr->exec_start);

curr->sum_exec_runtime+=delta_exec;

delta_exec_weighted=(delta_exec*NICE_0_LOAD)/(curr->load.weight);

curr->vruntime+=delta_exec_weighted;

curr->exec_start=clock;

其中curr是指向當(dāng)前進(jìn)程調(diào)度實(shí)體的指針，宏NICE_0_LOAD的值是1024，即優(yōu)先級為120的普通進(jìn)程的權(quán)重。顯然，對優(yōu)先級為120的普通進(jìn)程來說，它的虛擬計(jì)時(shí)器與物理計(jì)時(shí)器相同。進(jìn)程的優(yōu)先級越高，它的權(quán)重越大，vruntime就走得越慢。當(dāng)然，隊(duì)列的當(dāng)前虛擬時(shí)間min_vruntime也應(yīng)隨之更新，如更新為隊(duì)列中的最小虛擬時(shí)間，但必須保證該時(shí)間單調(diào)增長。

CFS的入隊(duì)操作用于將一個(gè)進(jìn)程插入到紅黑樹中。新入隊(duì)的進(jìn)程可能是新創(chuàng)建的進(jìn)程，也可能是剛被喚醒的進(jìn)程。入隊(duì)操作完成的工作如下：

(1)更新當(dāng)前處理器上當(dāng)前進(jìn)程的虛擬計(jì)時(shí)器(如上所述)，將新入隊(duì)進(jìn)程的權(quán)重累加到隊(duì)列的當(dāng)前負(fù)載load中。

(2)如果新入隊(duì)進(jìn)程此前睡眠了過長時(shí)間，它的虛擬計(jì)時(shí)器可能過慢，應(yīng)對其進(jìn)行適當(dāng)調(diào)整，否則在今后一段時(shí)間內(nèi)其它進(jìn)程將無法投入運(yùn)行。調(diào)整之后，新入隊(duì)進(jìn)程的vruntime不應(yīng)小于min_vruntime-6000000。6000000ns是一個(gè)調(diào)度周期的缺省時(shí)間長度，CFS保證在一個(gè)調(diào)度周期內(nèi)所有就緒進(jìn)程至少都會運(yùn)行一次。

(3)如果新進(jìn)程不是當(dāng)前進(jìn)程，則將其插入到紅黑樹中，將隊(duì)列的nr_running加1。進(jìn)程在紅黑樹中的位置由vruntime與min_vruntime的差值決定，是一個(gè)相對時(shí)間。如果入隊(duì)的進(jìn)程位于隊(duì)列的最左端，還要調(diào)整隊(duì)列的rb_leftmost指針。

CFS的出隊(duì)操作用于將一個(gè)進(jìn)程從紅黑樹中摘下。出隊(duì)的進(jìn)程不能是當(dāng)前進(jìn)程。在出隊(duì)操作中同樣需要更新當(dāng)前處理器上當(dāng)前進(jìn)程的虛擬計(jì)時(shí)器，并需要遞減隊(duì)列的當(dāng)前負(fù)載和nr_running計(jì)數(shù)、調(diào)整隊(duì)列的min_vruntime基值。如果出隊(duì)的進(jìn)程位于隊(duì)列的最左端，還需要調(diào)整隊(duì)列的rb_leftmost指針。

CFS的讓出操作用于聲明當(dāng)前進(jìn)程自愿讓出處理器。當(dāng)前進(jìn)程的狀態(tài)不變，但在隊(duì)列中的位置需要調(diào)整。在下一次調(diào)度之時(shí)，當(dāng)前進(jìn)程會被重新插入到紅黑樹中，因而只需調(diào)整當(dāng)前進(jìn)程的虛擬計(jì)時(shí)器，它在紅黑樹中的位置即會被自動調(diào)整。如果當(dāng)前進(jìn)程是批處理的，將它的虛擬計(jì)時(shí)器改為最右端進(jìn)程的vruntime+1(最大)；否則按正常方式更新隊(duì)列rq的計(jì)時(shí)器clock和當(dāng)前進(jìn)程的虛擬計(jì)時(shí)器vruntime即可。

CFS的搶占檢查操作用于確定當(dāng)前進(jìn)程是否可被新進(jìn)程搶占，當(dāng)然在檢查之前需要先更新當(dāng)前進(jìn)程的虛擬計(jì)時(shí)器。如果新進(jìn)程是批處理或空閑的，不應(yīng)搶占；如果新進(jìn)程的虛擬計(jì)時(shí)器比當(dāng)前進(jìn)程的大，不應(yīng)搶占；如果新進(jìn)程是實(shí)時(shí)的，應(yīng)搶占；如果當(dāng)前進(jìn)程是空閑的，應(yīng)搶占；如果新進(jìn)程的虛擬計(jì)時(shí)器比當(dāng)前進(jìn)程的小，應(yīng)搶占，但為了使搶占不至于太頻繁，應(yīng)讓當(dāng)前進(jìn)程運(yùn)行足夠的時(shí)間，即應(yīng)允許當(dāng)前進(jìn)程的虛擬計(jì)時(shí)器略大于新進(jìn)程的虛擬計(jì)時(shí)器，允許的差值由經(jīng)驗(yàn)公式算出，但不大于1ms的虛擬計(jì)時(shí)。如應(yīng)搶占，則讓隊(duì)列中的next指向新進(jìn)程、last指向當(dāng)前進(jìn)程，并在當(dāng)前進(jìn)程的thread_info中設(shè)置TIF_NEED_RESCHED標(biāo)志。

CFS的選出操作用于從紅黑樹中選擇下一個(gè)投入運(yùn)行的進(jìn)程。如果紅黑樹不空，選出的應(yīng)該是最左端的進(jìn)程。然而，如果next或last不空，則應(yīng)給它們一定的優(yōu)惠。若last進(jìn)程的虛擬計(jì)時(shí)器僅略大于最左端進(jìn)程的虛擬計(jì)時(shí)器(差值由經(jīng)驗(yàn)公式算出)，則選擇last進(jìn)程，并將last清空；若next進(jìn)程的虛擬計(jì)時(shí)器僅略大于最左端進(jìn)程的虛擬計(jì)時(shí)器，則選擇next進(jìn)程，并將next清空。由于新選出的進(jìn)程即將成為當(dāng)前進(jìn)程，因而將它的prev_sum_exec_runtime改為sum_exec_runtime、exec_start改為隊(duì)列rq的計(jì)時(shí)器clock，并讓隊(duì)列中的curr指向新選出的進(jìn)程。新選進(jìn)程要被從紅黑樹中摘下。

新進(jìn)程的運(yùn)行也有時(shí)間片的限制。設(shè)隊(duì)列中的進(jìn)程數(shù)為nr_running，隊(duì)列當(dāng)前的總負(fù)載為load，進(jìn)程的權(quán)重為weight，進(jìn)程時(shí)間片的計(jì)算方法如下：

if(nr_running>3)

slice=(nr_running*2000000*weight)/load;

else

slice=(6000000*weight)/load;由此可見，CFS的時(shí)間片長度會隨著隊(duì)列的當(dāng)前負(fù)載情況動態(tài)變化。為了實(shí)現(xiàn)精確調(diào)度，Linux為每個(gè)處理器都準(zhǔn)備了一個(gè)高精度定時(shí)器hrtick_timer(在隊(duì)列rq中)。在選出下一個(gè)投入運(yùn)行的進(jìn)程后，CFS會根據(jù)它的時(shí)間片長度啟動hrtick_timer，以預(yù)定下一次調(diào)度的精確時(shí)刻。當(dāng)hrtick_timer到期時(shí)，說明當(dāng)前進(jìn)程已耗盡了自己的時(shí)間片，應(yīng)該啟動新一輪的調(diào)度。當(dāng)然，當(dāng)有進(jìn)程入隊(duì)、出隊(duì)或當(dāng)當(dāng)前進(jìn)程請求調(diào)度或被搶占時(shí)，有可能需要重啟定時(shí)器hrtick_timer。

CFS的歸還操作用于將當(dāng)前進(jìn)程再插入到紅黑樹中，并將隊(duì)列的curr清空，以便進(jìn)行新一輪的調(diào)度。歸還之前當(dāng)然要更新當(dāng)前進(jìn)程的虛擬計(jì)時(shí)器。

CFS的重置操作用于將處理器上的當(dāng)前進(jìn)程重新設(shè)為隊(duì)列的當(dāng)前進(jìn)程curr，同時(shí)將它的prev_sum_exec_runtime改為sum_exec_runtime、exec_start改為隊(duì)列rq的計(jì)時(shí)器clock。如果當(dāng)前進(jìn)程在紅黑樹中，應(yīng)將其摘下。該操作通常在調(diào)整進(jìn)程策略和調(diào)度類后執(zhí)行。

CFS的更新操作在周期性時(shí)鐘中斷中執(zhí)行，用于更新當(dāng)前進(jìn)程的虛擬計(jì)時(shí)器。如果此次時(shí)鐘中斷是因?yàn)閔rtick_timer到期引起的，則應(yīng)該請求調(diào)度；否則，應(yīng)根據(jù)當(dāng)前進(jìn)程的時(shí)間片和虛擬計(jì)時(shí)器決定是否需要請求調(diào)度。

算出當(dāng)前進(jìn)程的時(shí)間片長度slice和此次運(yùn)行的實(shí)際時(shí)間長度delta_exec。

delta_exec=sum_exec_runtime-prev_sum_exec_runtime;如果delta_exec>slice，說明當(dāng)前進(jìn)程的時(shí)間片已用完，應(yīng)該請求調(diào)度。如果當(dāng)前進(jìn)程的虛擬計(jì)時(shí)器已超過隊(duì)列中最左端進(jìn)程的虛擬計(jì)時(shí)器，說明隊(duì)列中出現(xiàn)了更值得運(yùn)行的進(jìn)程，也應(yīng)該請求調(diào)度。但為了不至于使調(diào)度過于頻繁，CFS稍微照顧了一下當(dāng)前進(jìn)程，允許它的虛擬計(jì)時(shí)器稍大于最左端進(jìn)程的虛擬計(jì)時(shí)器，只要它的實(shí)際運(yùn)行時(shí)間不超過slice即可。

請求調(diào)度的方法是在當(dāng)前進(jìn)程的thread_info結(jié)構(gòu)上設(shè)置TIF_NEED_RESCHED標(biāo)志。當(dāng)中斷返回時(shí)，中斷善后處理程序會檢查當(dāng)前進(jìn)程上的TIF_NEED_RESCHED標(biāo)志，如果該標(biāo)志被設(shè)置，系統(tǒng)將試圖運(yùn)行調(diào)度程序，如圖4.3所示。

CFS的新醒操作用于喚醒首次運(yùn)行的進(jìn)程，所需完成的工作大致有三個(gè)，一是更新當(dāng)前進(jìn)程的虛擬計(jì)時(shí)器，二是設(shè)置新進(jìn)程的虛擬計(jì)時(shí)器，三是將新進(jìn)程插入紅黑樹。一般情況下，新進(jìn)程的虛擬計(jì)時(shí)器vruntime應(yīng)等于隊(duì)列的當(dāng)前虛擬時(shí)間min_vruntime，但考慮到當(dāng)前進(jìn)程還未耗完它的時(shí)間片，因而應(yīng)將vruntime后延一個(gè)時(shí)間片的虛擬長度。如果系統(tǒng)規(guī)定新進(jìn)程應(yīng)優(yōu)先運(yùn)行，而且當(dāng)前進(jìn)程的虛擬計(jì)時(shí)器又小于新進(jìn)程的vruntime，則交換兩者的虛擬計(jì)時(shí)器，并在當(dāng)前進(jìn)程上設(shè)置TIF_NEED_RESCHED標(biāo)志。

CFS的優(yōu)先級改變操作用于聲明有進(jìn)程的優(yōu)先級已被改變，需檢查當(dāng)前進(jìn)程是否應(yīng)被搶占。

CFS的調(diào)度類切換操作用于聲明一個(gè)進(jìn)程從別的調(diào)度類切換到了普通調(diào)度類，需檢查當(dāng)前進(jìn)程是否應(yīng)被搶占。7.3.3實(shí)時(shí)進(jìn)程調(diào)度類

一般的系統(tǒng)中通常不會有太多的實(shí)時(shí)進(jìn)程，然而一旦有實(shí)時(shí)進(jìn)程就緒，必須優(yōu)先調(diào)度實(shí)時(shí)進(jìn)程，直到它們自己無法再運(yùn)行為止。因而實(shí)時(shí)進(jìn)程的調(diào)度通常比較簡單，嚴(yán)格遵循優(yōu)先級即可，且不需要進(jìn)行過多的調(diào)整或浮動，所以可借用O(1)調(diào)度器的管理結(jié)構(gòu)，用多就緒隊(duì)列(隊(duì)列組)來組織、管理實(shí)時(shí)就緒進(jìn)程。目前的Linux用結(jié)構(gòu)rt_rq定義實(shí)時(shí)就緒進(jìn)程隊(duì)列，其中的主要內(nèi)容有以下幾個(gè)：

(1)由100個(gè)隊(duì)列構(gòu)成的隊(duì)列組queue，用于組織不同優(yōu)先級的實(shí)時(shí)就緒進(jìn)程。

(2)隊(duì)列狀態(tài)位圖bitmap，描述各隊(duì)列的狀態(tài)，0表示空，1表示隊(duì)列中有進(jìn)程。

(3)隊(duì)列組中當(dāng)前就緒的實(shí)時(shí)進(jìn)程總數(shù)rt_nr_running。

(4)實(shí)時(shí)進(jìn)程抑制標(biāo)志rt_throttled。

(5)實(shí)時(shí)進(jìn)程在處理器上已運(yùn)行的時(shí)間rt_time。

(6)實(shí)時(shí)進(jìn)程在處理器上可運(yùn)行的時(shí)間rt_runtime。

實(shí)時(shí)進(jìn)程也使用調(diào)度實(shí)體sched_entity來記錄運(yùn)行信息，如進(jìn)程已運(yùn)行的總時(shí)間sum_exec_runtime、進(jìn)程之前運(yùn)行的總時(shí)間prev_sum_exec_runtime、進(jìn)程本次運(yùn)行的開始時(shí)間exec_start、進(jìn)程的權(quán)重load等。除此之外，在進(jìn)程的task_struct結(jié)構(gòu)中還內(nèi)嵌著一個(gè)實(shí)時(shí)調(diào)度實(shí)體，由結(jié)構(gòu)sched_rt_entity定義，用于記錄進(jìn)程的實(shí)時(shí)調(diào)度信息，如進(jìn)程的剩余時(shí)間片time_slice、允許運(yùn)行該進(jìn)程的處理器數(shù)nr_cpus_allowed等。就緒態(tài)的實(shí)時(shí)進(jìn)程通過sched_rt_entity結(jié)構(gòu)中的run_list域?qū)⒆约烘溔氲綄?shí)時(shí)就緒隊(duì)列中。

由于Linux總是照顧實(shí)時(shí)進(jìn)程，有可能出現(xiàn)普通進(jìn)程被餓死的現(xiàn)象。若系統(tǒng)中總是有就緒狀態(tài)的實(shí)時(shí)進(jìn)程，普通進(jìn)程將永遠(yuǎn)無法運(yùn)行，這顯然是不合理的。為了解決這一問題，Linux為實(shí)時(shí)進(jìn)程預(yù)定了帶寬，限定了實(shí)時(shí)進(jìn)程在一個(gè)處理器上、一個(gè)檢查周期內(nèi)可運(yùn)行的最長時(shí)間rt_runtime。處理器在更新當(dāng)前實(shí)時(shí)進(jìn)程的運(yùn)行時(shí)間時(shí)會同時(shí)累計(jì)隊(duì)列組中的運(yùn)行時(shí)間rt_time。當(dāng)rt_time大于rt_runtime時(shí)，說明實(shí)時(shí)進(jìn)程在該處理器上所占帶寬超標(biāo)，應(yīng)對其進(jìn)行抑制，即設(shè)置隊(duì)列組中的rt_throttled標(biāo)志，宣布暫停調(diào)度實(shí)時(shí)進(jìn)程，從而給普通進(jìn)程以運(yùn)行的機(jī)會。但對實(shí)時(shí)進(jìn)程的抑制不能一直持續(xù)，必須周期性地將其解除，為此Linux啟動了一個(gè)周期性的高精度定時(shí)器rt_period_timer，其定時(shí)周期為一個(gè)檢查周期。當(dāng)定時(shí)器rt_period_timer到期時(shí)，它檢查所有處理器的實(shí)時(shí)就緒進(jìn)程隊(duì)列組，將它們的rt_time減到一個(gè)檢查周期之內(nèi)并清除其上的rt_throttled標(biāo)志，同時(shí)設(shè)置當(dāng)前進(jìn)程上的TIF_NEED_RESCHED標(biāo)志，請求新一輪的進(jìn)程調(diào)度。

缺省情況下，一個(gè)檢查周期的長度是1秒鐘，實(shí)時(shí)帶寬為0.95秒。與普通類進(jìn)程相似，實(shí)時(shí)類進(jìn)程也需要經(jīng)常更新當(dāng)前進(jìn)程的運(yùn)行時(shí)間，更新依據(jù)是隊(duì)列rq中的clock。設(shè)curr是指向當(dāng)前進(jìn)程調(diào)度實(shí)體的指針，運(yùn)行時(shí)間的更新方法如下：

delta_exec=clock-curr->se.exec_start;

curr->se.sum_exec_runtime+=delta_exec;

curr->se.exec_start=clock;

如果系統(tǒng)為實(shí)時(shí)就緒進(jìn)程隊(duì)列指定了帶寬(rt_runtime不是無窮大)且?guī)挷淮笥?00%，則應(yīng)檢查實(shí)時(shí)帶寬。設(shè)rt_rq是指向?qū)崟r(shí)就緒進(jìn)程隊(duì)列的指針，檢查方法如下：

rt_rq->rt_time+=delta_exec;

if(rt_rq->rt_time>rt_rq->rt_runtime)

rt_rq->rt_throttled=1;

如果rt_throttled被置1，說明實(shí)時(shí)進(jìn)程所用時(shí)間已超標(biāo)，設(shè)置當(dāng)前進(jìn)程thread_info結(jié)構(gòu)中的TIF_NEED_RESCHED標(biāo)志，請求進(jìn)程調(diào)度。

實(shí)時(shí)類的入隊(duì)操作用于將一個(gè)實(shí)時(shí)進(jìn)程插入到就緒隊(duì)列中。如果進(jìn)程已在就緒隊(duì)列中，應(yīng)先將其摘下。新入隊(duì)進(jìn)程在實(shí)時(shí)就緒隊(duì)列組中的位置由它的動態(tài)優(yōu)先級prio決定，可以插在隊(duì)頭，也可以插在隊(duì)尾。進(jìn)程入隊(duì)后，隊(duì)列組位圖bitmap中的第prio位應(yīng)置1，隊(duì)列組中的進(jìn)程數(shù)rt_nr_running應(yīng)加1。如果高精度定時(shí)器rt_period_timer未被啟動，則應(yīng)啟動它。

實(shí)時(shí)類的出隊(duì)操作用于將一個(gè)實(shí)時(shí)進(jìn)程從就緒隊(duì)列中摘下。摘下前要先更新當(dāng)前進(jìn)程的運(yùn)行時(shí)間。如果出隊(duì)操作使某隊(duì)列變空，則應(yīng)清除該隊(duì)列在位圖bitmap中的標(biāo)志位。進(jìn)程出隊(duì)后，隊(duì)列組中的進(jìn)程數(shù)rt_nr_running應(yīng)減1。

實(shí)時(shí)類的讓出操作用于將當(dāng)前實(shí)時(shí)進(jìn)程從隊(duì)頭移到隊(duì)尾。實(shí)時(shí)類的搶占檢查操作用于確定當(dāng)前進(jìn)程是否可被新進(jìn)程搶占。如果新進(jìn)程的動態(tài)優(yōu)先級prio比當(dāng)前進(jìn)程的小，應(yīng)該搶占當(dāng)前進(jìn)程。如果新進(jìn)程的動態(tài)優(yōu)先級prio與當(dāng)前進(jìn)程的相同，說明當(dāng)前處理器上已有較多的實(shí)時(shí)進(jìn)程，應(yīng)設(shè)法將當(dāng)前進(jìn)程遷移到其它允許的處理器上。如果能夠遷移當(dāng)前進(jìn)程，則將新進(jìn)程移到隊(duì)頭，并請求搶占當(dāng)前進(jìn)程。搶占當(dāng)前進(jìn)程的方法是在它的thread_info結(jié)構(gòu)上設(shè)置TIF_NEED_RESCHED標(biāo)志。

實(shí)時(shí)類的選出操作用于從實(shí)時(shí)就緒進(jìn)程隊(duì)列組中選出下一個(gè)投入運(yùn)行的進(jìn)程。如果隊(duì)列組不空且實(shí)時(shí)進(jìn)程未被抑制，則從隊(duì)列組位圖bitmap中找出序號最小的非空隊(duì)列，該隊(duì)列的隊(duì)頭進(jìn)程就是被選出的實(shí)時(shí)進(jìn)程。與普通進(jìn)程不同，被選出的實(shí)時(shí)進(jìn)程仍然在隊(duì)列中，不被摘下。由于被選出進(jìn)程即將投入運(yùn)行，所以應(yīng)將它的exec_start設(shè)為當(dāng)前時(shí)間(rq中的clock)。

實(shí)時(shí)類的歸還操作用于更新當(dāng)前進(jìn)程的運(yùn)行時(shí)間，并將其exec_start清0。

實(shí)時(shí)類的重置操作用于將當(dāng)前進(jìn)程的exec_start設(shè)為當(dāng)前時(shí)間(rq中的clock)。實(shí)時(shí)類的更新操作在周期性時(shí)鐘中斷中調(diào)用，用于更新當(dāng)前進(jìn)程的運(yùn)行時(shí)間和時(shí)間片。根據(jù)當(dāng)前實(shí)時(shí)進(jìn)程的調(diào)度策略，可將更新操作分成兩類：

(1)如果當(dāng)前實(shí)時(shí)進(jìn)程的調(diào)度策略是SCHED_FIFO，則不需要更新時(shí)間片，讓它一直運(yùn)行下去即可。

(2)如果當(dāng)前實(shí)時(shí)進(jìn)程的調(diào)度策略是SCHED_RR，則將它的時(shí)間片time_slice減1。如果減后的time_slice仍然大于0，則讓它繼續(xù)運(yùn)行；否則將time_slice重置為(100

×

Hz/1000)，即100ms，而后將當(dāng)前進(jìn)程移到隊(duì)尾，并請求新一輪調(diào)度。實(shí)時(shí)類的優(yōu)先級改變操作用于聲明有進(jìn)程的優(yōu)先級被改變，需檢查當(dāng)前進(jìn)程是否應(yīng)被搶占。只要改變后的動態(tài)優(yōu)先級prio比當(dāng)前進(jìn)程的小，則應(yīng)搶占當(dāng)前進(jìn)程。

實(shí)時(shí)