?????? 又來(lái)到了一個(gè)老生常談的問(wèn)題，應(yīng)用層軟件開發(fā)的程序員要不要了解和深入學(xué)習(xí)操作系統(tǒng)呢？ 今天就這個(gè)問(wèn)題開始，來(lái)談?wù)劜僮飨到y(tǒng)中可以說(shuō)是最重要的一個(gè)概念--進(jìn)程。

????? 操作系統(tǒng)最主要的兩個(gè)職能是管理各種資源和為應(yīng)用程序提供系統(tǒng)調(diào)用接口。這其中關(guān)鍵的部分是，cpu到進(jìn)程的抽象，物理內(nèi)存到地址空間（虛擬內(nèi)存）的抽象，磁盤到文件的抽象，而其中后兩部分以進(jìn)程為基礎(chǔ)，所以嘛，咱重點(diǎn)來(lái)討論進(jìn)程，以及與進(jìn)程密切相關(guān)的線程。

一 .先說(shuō)說(shuō)概念

進(jìn)程(process)

狹義的定義：進(jìn)程就是一段程序的執(zhí)行過(guò)程。

廣義定義：進(jìn)程是一個(gè)具有一定獨(dú)立功能的程序關(guān)于某次數(shù)據(jù)集合的一次運(yùn)行活動(dòng)，它是操作系統(tǒng)分配資源的基本單元。

簡(jiǎn)單來(lái)講進(jìn)程的概念主要有兩點(diǎn)：第一，進(jìn)程是一個(gè)實(shí)體。每一個(gè)進(jìn)程都有它自己的地址空間，一般情況下，包括文本區(qū)域（text region）、數(shù)據(jù)區(qū)域（data region）和堆棧（stack region）。文本區(qū)域存儲(chǔ)處理器執(zhí)行的代碼；數(shù)據(jù)區(qū)域存儲(chǔ)變量和進(jìn)程執(zhí)行期間使用的動(dòng)態(tài)分配的內(nèi)存；堆棧區(qū)域存儲(chǔ)著活動(dòng)過(guò)程中調(diào)用的指令和本地變量。第二，進(jìn)程是一個(gè)“執(zhí)行中的程序”。程序是一個(gè)沒(méi)有生命的實(shí)體，只有處理器賦予程序生命時(shí)，它才能成為一個(gè)活動(dòng)的實(shí)體，我們稱其為進(jìn)程。

進(jìn)程狀態(tài)：進(jìn)程有三個(gè)狀態(tài)，就緒，運(yùn)行和阻塞。就緒狀態(tài)其實(shí)就是獲取了除cpu外的所有資源，只要處理器分配資源馬上就可以運(yùn)行。運(yùn)行態(tài)就是獲取了處理器分配的資源，程序開始執(zhí)行，阻塞態(tài)，當(dāng)程序條件不夠時(shí)，需要等待條件滿足時(shí)候才能執(zhí)行，如等待I/O操作的時(shí)候，此刻的狀態(tài)就叫阻塞態(tài)。

說(shuō)說(shuō)程序，程序是指令和數(shù)據(jù)的有序集合，其本身沒(méi)有任何運(yùn)動(dòng)的含義，是一個(gè)靜態(tài)的概念，而進(jìn)程則是在處理機(jī)上的一次執(zhí)行過(guò)程，它是一個(gè)動(dòng)態(tài)的概念。進(jìn)程是包含程序的，進(jìn)程的執(zhí)行離不開程序，進(jìn)程中的文本區(qū)域就是代碼區(qū)，也就是程序。

線程(thread)

通常在一個(gè)進(jìn)程中可以包含若干個(gè)線程，當(dāng)然一個(gè)進(jìn)程中至少有一個(gè)線程，不然沒(méi)有存在的意義。線程可以利用進(jìn)程所擁有的資源，在引入線程的操作系統(tǒng)中，通常都是把進(jìn)程作為分配資源的基本單位，而把線程作為獨(dú)立運(yùn)行和獨(dú)立調(diào)度的基本單位，由于線程比進(jìn)程更小，基本上不擁有系統(tǒng)資源，故對(duì)它的調(diào)度所付出的開銷就會(huì)小得多，能更高效的提高系統(tǒng)多個(gè)程序間并發(fā)執(zhí)行的程度。

多線程(multiThread)

在一個(gè)程序中，這些獨(dú)立運(yùn)行的程序片段叫作“線程”（Thread），利用它編程的概念就叫作“多線程處理”。多線程是為了同步完成多項(xiàng)任務(wù)，不是為了提高運(yùn)行效率，而是為了提高資源使用效率來(lái)提高系統(tǒng)的效率。線程是在同一時(shí)間需要完成多項(xiàng)任務(wù)的時(shí)候?qū)崿F(xiàn)的。

最簡(jiǎn)單的比喻多線程就像火車的每一節(jié)車廂，而進(jìn)程則是火車。車廂離開火車是無(wú)法跑動(dòng)的，同理火車也不可能只有一節(jié)車廂。多線程的出現(xiàn)就是為了提高效率。

二、說(shuō)說(shuō)區(qū)別

1、進(jìn)程與線程的區(qū)別：

進(jìn)程和線程的主要差別在于它們是不同的操作系統(tǒng)資源管理方式。進(jìn)程有獨(dú)立的地址空間，一個(gè)進(jìn)程崩潰后，在保護(hù)模式下不會(huì)對(duì)其它進(jìn)程產(chǎn)生影響，而線程只是一個(gè)進(jìn)程中的不同執(zhí)行路徑。線程有自己的堆棧和局部變量，但線程之間沒(méi)有單獨(dú)的地址空間，一個(gè)線程死掉就等于整個(gè)進(jìn)程死掉，所以多進(jìn)程的程序要比多線程的程序健壯，但在進(jìn)程切換時(shí)，耗費(fèi)資源較大，效率要差一些。但對(duì)于一些要求同時(shí)進(jìn)行并且又要共享某些變量的并發(fā)操作，只能用線程，不能用進(jìn)程。

1) 簡(jiǎn)而言之,一個(gè)程序至少有一個(gè)進(jìn)程,一個(gè)進(jìn)程至少有一個(gè)線程.

2) 線程的劃分尺度小于進(jìn)程，使得多線程程序的并發(fā)性高。

3) 另外，進(jìn)程在執(zhí)行過(guò)程中擁有獨(dú)立的內(nèi)存單元，而多個(gè)線程共享內(nèi)存，從而極大地提高了程序的運(yùn)行效率。

4) 線程在執(zhí)行過(guò)程中與進(jìn)程還是有區(qū)別的。每個(gè)獨(dú)立的線程有一個(gè)程序運(yùn)行的入口、順序執(zhí)行序列和程序的出口。但是線程不能夠獨(dú)立執(zhí)行，必須依存在應(yīng)用程序中，由應(yīng)用程序提供多個(gè)線程執(zhí)行控制。

5) 從邏輯角度來(lái)看，多線程的意義在于一個(gè)應(yīng)用程序中，有多個(gè)執(zhí)行部分可以同時(shí)執(zhí)行。但操作系統(tǒng)并沒(méi)有將多個(gè)線程看做多個(gè)獨(dú)立的應(yīng)用，來(lái)實(shí)現(xiàn)進(jìn)程的調(diào)度和管理以及資源分配。這就是進(jìn)程和線程的重要區(qū)別。

三、說(shuō)說(shuō)優(yōu)缺點(diǎn)

線程和進(jìn)程在使用上各有優(yōu)缺點(diǎn)：線程執(zhí)行開銷小，但不利于資源的管理和保護(hù)；而進(jìn)程正相反。同時(shí)，線程適合于在SMP(多核處理機(jī))機(jī)器上運(yùn)行，而進(jìn)程則可以跨機(jī)器遷移。

四、說(shuō)說(shuō)進(jìn)程和線程的細(xì)節(jié)，底層構(gòu)成 和 調(diào)度

（一）進(jìn)程相關(guān)的數(shù)據(jù)結(jié)構(gòu)

為了管理進(jìn)程，內(nèi)核必須對(duì)每個(gè)進(jìn)程所做的事情進(jìn)行清楚的描述，例如，內(nèi)核必須知道進(jìn)程的優(yōu)先級(jí)，它是在CPU上運(yùn)行還是因?yàn)槟承┦露蛔枞?，給它分配了什么樣的地址空間，允許它訪問(wèn)哪個(gè)文件等。

這些正是進(jìn)程描述符的作用---進(jìn)程描述符都是task_struct 數(shù)據(jù)結(jié)構(gòu)，它的字段包含了與一個(gè)進(jìn)程相關(guān)的所有信息。下圖顯示了Linux進(jìn)程描述符

談?wù)勥M(jìn)程的基本信息。

1）標(biāo)識(shí)一個(gè)進(jìn)程--PID

每個(gè)進(jìn)程都必須擁有它自己的進(jìn)程描述符；進(jìn)程和進(jìn)程描述符之間有非常嚴(yán)格的一一對(duì)應(yīng)關(guān)系，所以我們可以方便地使用32位進(jìn)程描述符地址標(biāo)識(shí)進(jìn)程。

進(jìn)程描述符指針（task_struct*）指向這些地址。內(nèi)核對(duì)進(jìn)程的大部份引用都是通過(guò)進(jìn)程描述符指針進(jìn)行的。

另一方面，類Unix橾作系統(tǒng)允許用戶使用一個(gè)叫做進(jìn)程標(biāo)識(shí)符processID(PID)的數(shù)來(lái)標(biāo)識(shí)進(jìn)程，PID存放在task_struct的pid字段中。PID被順序編號(hào)，新創(chuàng)建進(jìn)程的PID通常是前一個(gè)進(jìn)程的PID加1。不過(guò)，PID的值有一個(gè)上限，當(dāng)內(nèi)核使用的PID達(dá)到這個(gè)峰值的時(shí)候，就必須開始循環(huán)使用已閑置的小PID號(hào)。在缺省情況下，最大的PID號(hào)是32767。

系統(tǒng)管理員可以通過(guò)往/proc/sys/kernel/pid_max 這個(gè)文件中寫入一個(gè)更小的值來(lái)減小PID的上限值，使PID的上限小于32767。在64位體系結(jié)構(gòu)中，系統(tǒng)管理員可以把PID的上限擴(kuò)大到4194304。

Linux只支持輕量級(jí)進(jìn)程，不支持線程，但為了彌補(bǔ)這樣的缺陷，Linux引入線程組的概念。一個(gè)線程組中的所有線程使用和該線程組的領(lǐng)頭線程相同的PID，也就是該組中第一個(gè)輕量級(jí)進(jìn)程的PID，它被存入進(jìn)程描述符的tgid字段中。getpid()系統(tǒng)調(diào)用返回當(dāng)前進(jìn)程的tgid值而不是pid值，因此，一個(gè)多線程應(yīng)用的所有線程共享相同的PID。絕大多數(shù)進(jìn)程都屬于一個(gè)線程組；而線程組的領(lǐng)頭線程其tgid與pid的值相同，因而getpid()系統(tǒng)調(diào)用對(duì)這類進(jìn)程所起的作用和一般進(jìn)程是一樣的。

所以，我們得出一個(gè)重要的結(jié)論，Linux雖不支持線程，但是它有具備支持線程的操作系統(tǒng)的所有特性，后面講解輕量級(jí)進(jìn)程的概念中還會(huì)詳細(xì)討論。

2）進(jìn)程描述符定位

進(jìn)程是動(dòng)態(tài)實(shí)體，其生命周期范圍從幾毫秒到幾個(gè)月，因此內(nèi)核必須同時(shí)處理很多進(jìn)程，并把對(duì)應(yīng)的進(jìn)程描述符放在動(dòng)態(tài)內(nèi)存中，而不是放在永久分配給內(nèi)核的內(nèi)存區(qū)（3G之上的線性地址）。

那么，怎么找到被動(dòng)態(tài)分配的進(jìn)程描述符呢？我們需要在3G之上線性地址的內(nèi)存區(qū)為每個(gè)進(jìn)程設(shè)計(jì)一個(gè)塊—thread_union。

對(duì)每個(gè)進(jìn)程來(lái)說(shuō)，我們需要給其分配兩個(gè)頁(yè)面，即8192個(gè)字節(jié)的塊，Linux把兩個(gè)不同數(shù)據(jù)結(jié)構(gòu)緊湊地存放在一個(gè)單獨(dú)為進(jìn)程分配的存儲(chǔ)區(qū)域內(nèi)：一個(gè)是內(nèi)核態(tài)的進(jìn)程堆棧，另一個(gè)是緊挨著進(jìn)程描述符的小數(shù)據(jù)結(jié)構(gòu)thread_info，叫做線程描述符。

考慮到效率問(wèn)題，內(nèi)核讓這8k的空間占據(jù)連續(xù)兩個(gè)頁(yè)框并讓第一個(gè)頁(yè)框的起始地址是2^13的倍數(shù)。當(dāng)幾乎沒(méi)有可用的動(dòng)態(tài)內(nèi)存空間時(shí)，就會(huì)很難找到這樣的兩個(gè)連續(xù)頁(yè)框，因?yàn)榭臻e空間可能存在大量的碎片（注意，這里是物理空間，見“伙伴系統(tǒng)算法”博文）。因此，在80x86體系結(jié)構(gòu)中，在編譯時(shí)可以進(jìn)行設(shè)置，以使內(nèi)核棧和線程描述符跨越一個(gè)單獨(dú)的頁(yè)框（因?yàn)橹饕嬖诘膯雾?yè)的碎片）。在“Linux中的分段”的博文中我們已經(jīng)知道，內(nèi)核態(tài)的進(jìn)程訪問(wèn)處于內(nèi)核數(shù)據(jù)段的棧，也就是我們Linux在3G以上內(nèi)存空間為每個(gè)進(jìn)程設(shè)計(jì)這么一個(gè)棧的目的，這個(gè)棧不同于用戶態(tài)的進(jìn)程所用的棧。因?yàn)閮?nèi)核控制路徑使用很少的棧，因此只需要幾千個(gè)字節(jié)的內(nèi)核態(tài)堆棧。所以，對(duì)棧和thread_info來(lái)說(shuō)，8KB足夠了。不過(guò)，如果只使用一個(gè)頁(yè)框存放這兩個(gè)結(jié)構(gòu)的話，內(nèi)核要采用一些額外的棧以防止中斷和異常的深度嵌套而引起的溢出。

下圖顯示了在2頁(yè)（8KB）內(nèi)存區(qū)中存放兩種數(shù)據(jù)結(jié)構(gòu)的方式。線程描述符駐留于這個(gè)內(nèi)存區(qū)的開始位置，而棧從末端向下增長(zhǎng)。該圖還顯示了如何通過(guò)task字段與task_struct結(jié)構(gòu)相互關(guān)聯(lián)。

struct thread_info {

struct task_struct??? *task;??? ??? /* main task structure */

struct exec_domain??? *exec_domain;??? /* execution domain */

unsigned long??? ??? flags;??? ??? /* low level flags */

unsigned long??? ??? status;??? ??? /* thread-synchronous flags */

__u32??? ??? ??? cpu;??? ??? /* current CPU */

__s32??? ??? ??? preempt_count; /* 0 => preemptable, <0 => BUG */

mm_segment_t??? ??? addr_limit;??? /* thread address space:0-0xBFFFFFFF for user-thead? 0-0xFFFFFFFF for kernel-thread*/

struct restart_block??? restart_block;

unsigned long?????????? previous_esp;?? /* ESP of the previous stack in caseof nested (IRQ) stacks*/

__u8??? ??? ??? supervisor_stack[0];

};

esp為CPU棧指針寄存器，用來(lái)存放棧頂單元的地址。在80x86系統(tǒng)中，棧起始于末端，并朝這個(gè)內(nèi)存區(qū)的起始方向增長(zhǎng)。從用戶態(tài)切換到內(nèi)核態(tài)以后，進(jìn)程的內(nèi)核?？偸强盏模虼?，esp寄存器指向這個(gè)棧的頂端。

一旦數(shù)據(jù)寫入堆棧，esp的值就遞減。特別要注意，這里的數(shù)據(jù)是指內(nèi)核數(shù)據(jù)，其實(shí)用得很少，所以大多數(shù)時(shí)候這個(gè)內(nèi)核棧是空的。因?yàn)閠hread_info

結(jié)構(gòu)是52個(gè)字節(jié)的長(zhǎng)度，所以內(nèi)核棧能擴(kuò)展到8140個(gè)字節(jié)。C語(yǔ)言使用下列聯(lián)合結(jié)構(gòu)，方便地表示一個(gè)進(jìn)程的線程描述符和內(nèi)核棧：

union thread_union {

struct thread_info thread_info;

unsigned long stack[2048]; /* 1024 for 4KB stacks */

};

內(nèi)核使用alloc_thread_info 和 free_thread_info宏分配和釋放存儲(chǔ)thread_info結(jié)構(gòu)和內(nèi)核棧的內(nèi)存區(qū)。

3）標(biāo)識(shí)當(dāng)前進(jìn)程

我們?cè)購(gòu)男实挠^點(diǎn)來(lái)看，剛才所講的thread_info結(jié)構(gòu)與內(nèi)核態(tài)堆棧之間的緊密結(jié)合提供的主要好處還在：內(nèi)核很容易從esp寄存器的值獲得當(dāng)前在CPU上正在運(yùn)行進(jìn)程的thread_info結(jié)構(gòu)的地址。事實(shí)上，如果thread_union的長(zhǎng)度是8K（213字節(jié)），則內(nèi)核屏蔽掉esp的低13位有效位就可以獲得thread_info結(jié)構(gòu)的基地址；而如果thread_union的長(zhǎng)度是4K，內(nèi)核需要蔽掉esp的低12位有效位。這項(xiàng)工作由current_thread_info()函數(shù)來(lái)完成，它產(chǎn)生如下一些匯編指令：

movl $0xffffe000,%ecx /* or 0xfffff000 for 4KB stacks */

andl %esp,%ecx

movl %ecx,p

這三條指令執(zhí)行后，p就是在執(zhí)行指令的CPU上運(yùn)行的當(dāng)前進(jìn)程的thread_info結(jié)構(gòu)的指針。不過(guò)，進(jìn)程最常用的是進(jìn)程描述符的地址，而不是thread_info結(jié)構(gòu)的地址。為了獲得當(dāng)前在CPU上運(yùn)行進(jìn)程的描述符指針，內(nèi)核要調(diào)用current宏，該宏本質(zhì)上等價(jià)于current_thread_info( )->task，它產(chǎn)生如下匯編指令：

movl $0xffffe000,%ecx /* or 0xfffff000 for 4KB stacks */

andl %esp,%ecx

movl (%ecx),p

因?yàn)閠ask字段在thread_info結(jié)構(gòu)中的偏移量為0，所以執(zhí)行完這三條指令之后，p就是CPU上運(yùn)行進(jìn)程的描述符指針。

current宏經(jīng)常作為進(jìn)程描述符字段的前綴出現(xiàn)在內(nèi)核代碼中，例如，current->pid返回在CPU上正在執(zhí)行CPU的進(jìn)程的PID。

4）進(jìn)程鏈表

Linux內(nèi)核把進(jìn)程鏈表把所有進(jìn)程的描述符鏈接起來(lái)。每個(gè)task_struct結(jié)構(gòu)都包含一個(gè)list_head類型的tasks字段，這個(gè)類型的prev和next字段分別指向前面和后面的的task_struct元素。

進(jìn)程鏈表的頭是init_task描述符，它是所謂的0進(jìn)程或swapper進(jìn)程的進(jìn)程描述符。init_task的tasks.prev字段指向鏈表中最后插入的進(jìn)程描述符的tasks字段。

SET_LINKS 和 REMOVE_LINKS 宏分別用于從進(jìn)程鏈表中插入和刪除一個(gè)進(jìn)程描述符。這些宏考慮了進(jìn)程間的父子關(guān)系。

另外，還有一個(gè)很有用的宏就是for_each_process，它的功能是掃描整個(gè)進(jìn)程鏈表，其定義如下：

#define for_each_process(p) /

for (p=&init_task; (p=list_entry((p)->tasks.next, /

struct task_struct, tasks) /

) != &init_task; )

5）state字段

進(jìn)程描述符task_struct結(jié)構(gòu)的state字段描述了進(jìn)程當(dāng)前所處的狀態(tài)。它由一組標(biāo)志組成，其中每個(gè)標(biāo)志描述一種可能的進(jìn)程狀態(tài)。在當(dāng)前的Linux版本中，這些狀態(tài)是互斥的，因此，嚴(yán)格意義上來(lái)說(shuō)，只能設(shè)置一種狀態(tài)，其余的標(biāo)志位將被清除。下面是可能的狀態(tài)：

可運(yùn)行狀態(tài)（TASK_RUNNING）

進(jìn)程要么在CPU上執(zhí)行，要么準(zhǔn)備執(zhí)行。

可中斷的等待狀態(tài)（TASK_INTERRUPTIBLE）

進(jìn)程被掛起（睡眠），直到某個(gè)條件變?yōu)檎妗．a(chǎn)生一個(gè)硬件中斷、釋放進(jìn)程正在等待的系統(tǒng)資源、或傳遞一個(gè)信號(hào)都是可以喚醒進(jìn)程的條件（把進(jìn)程狀態(tài)放回到TASK_RUNNING）。

不可中斷的等待狀態(tài)（TASK_UNINTERRUPTIBLE）

與可中斷的等待狀態(tài)類似，但有一個(gè)例外，把信號(hào)傳遞到該睡眠進(jìn)程時(shí)，不能改變它的狀態(tài)。這種狀態(tài)很少用到，但在一些特定條件下（進(jìn)程必須等待，直到一個(gè)不能被中斷的時(shí)事件發(fā)生），這種狀態(tài)是很有用的。例如，當(dāng)進(jìn)程打開一個(gè)設(shè)備文件，其相應(yīng)的設(shè)備驅(qū)動(dòng)程序開始探測(cè)相應(yīng)的硬件設(shè)備時(shí)會(huì)用到這種狀態(tài)。探測(cè)完成以前，設(shè)備驅(qū)動(dòng)程序不能被中斷，否則，硬件設(shè)備會(huì)處于不可預(yù)知的狀態(tài)。

暫停狀態(tài)（TASK_STOPPED）

進(jìn)程的執(zhí)行被暫停。當(dāng)進(jìn)程接收到SIGSTOP、SIGTSTP、SIGTTIN或SIGTTOU信號(hào)后，進(jìn)人暫停狀態(tài)。

跟蹤狀態(tài)（TASK_TRACED）

進(jìn)程的執(zhí)行已由debugger程序暫停。當(dāng)一個(gè)進(jìn)程被另一個(gè)進(jìn)程監(jiān)控時(shí)（例如debugger執(zhí)行ptrace()系統(tǒng)調(diào)用監(jiān)控一個(gè)測(cè)試程序）任何信號(hào)都可以把這個(gè)進(jìn)程置于TASK_TRACED狀態(tài)。

還有兩個(gè)進(jìn)程狀態(tài)既可以存放在進(jìn)程描述符的state字段啊中，也可以存放在exit_state中字段中。從這兩個(gè)字段的名稱可以看出，只有當(dāng)進(jìn)程的執(zhí)行被終止時(shí)，進(jìn)程的狀態(tài)才會(huì)變成此兩種中的一種：

僵死狀態(tài)（EXIT_ZOMBIE）

進(jìn)程的執(zhí)行被終止，但是父進(jìn)程還沒(méi)發(fā)布wait4()或waitpid()系統(tǒng)調(diào)用來(lái)返回有關(guān)死亡進(jìn)程的信息。發(fā)布wait()類系統(tǒng)調(diào)用前，內(nèi)核不能丟棄包含在死進(jìn)程描述符中的數(shù)據(jù)，因?yàn)楦高M(jìn)程可能還需要它。

僵死撤銷狀態(tài)（EXIT_DEAD）

終狀態(tài)：由于父進(jìn)程剛發(fā)出wait4()或waitpid()系統(tǒng)調(diào)用，因而進(jìn)程由系統(tǒng)刪除。為了防止其他執(zhí)行線程在同一個(gè)進(jìn)程上也執(zhí)行wait()類系統(tǒng)調(diào)用（這也是一種競(jìng)爭(zhēng)條件），而把進(jìn)程的狀態(tài)由僵死（EXIT_ZOMBIE）狀態(tài)改為僵死撤銷狀態(tài)（EXIT_DEAD）

state字段的值通常用一個(gè)簡(jiǎn)單的賦值語(yǔ)句設(shè)置，例如：

p->state = TASK_RUNNING;

內(nèi)核也使用set_task_state和set_current_state宏：它們分別設(shè)置指定進(jìn)程的狀態(tài)和當(dāng)前執(zhí)行進(jìn)程的狀態(tài)。此外，這些宏確保編譯程序或CPU控制單元不把賦值操作和其他指令混合。混合指令的順序有時(shí)會(huì)導(dǎo)致災(zāi)難性的后果。

6）TASK_RUNNING狀態(tài)的進(jìn)程鏈表

當(dāng)內(nèi)核尋找到一個(gè)新進(jìn)程在CPU上運(yùn)行時(shí)，必須只考慮可運(yùn)行進(jìn)程（即處在TASK_RUNNING狀態(tài)的進(jìn)程）。

早先的Linux版本把所有的可運(yùn)行進(jìn)程都放在同一個(gè)叫做運(yùn)行隊(duì)列（runqueue）的鏈表中，由于維持鏈表中的進(jìn)程優(yōu)先級(jí)排序的開銷過(guò)大，因此，早期的調(diào)度程序不得不為選擇“最佳”可運(yùn)行進(jìn)程而掃描整個(gè)隊(duì)列。

Linux 2.6實(shí)現(xiàn)的運(yùn)行隊(duì)列有所不同。其目的是讓調(diào)度程序能在固定的時(shí)間內(nèi)選出“最佳”可運(yùn)行隊(duì)列，與進(jìn)程中可運(yùn)行的進(jìn)程數(shù)無(wú)關(guān)。

提高調(diào)度程序運(yùn)行速度的訣竅是建立多個(gè)可運(yùn)行進(jìn)程鏈表，每種進(jìn)程優(yōu)先級(jí)對(duì)應(yīng)一個(gè)不同的鏈表。每個(gè)task_struct描述符包含一個(gè)list_head類型的字段run_list。如果進(jìn)程的優(yōu)先權(quán)等于k（其取值范圍從0到139），run_list字段就把該進(jìn)程的優(yōu)先級(jí)鏈入優(yōu)先級(jí)為k的可運(yùn)行進(jìn)程的鏈表中。此外，在多處理器系統(tǒng)中，每個(gè)CPU都有它自己的運(yùn)行隊(duì)列，即它自己的進(jìn)程鏈表集。這是一個(gè)通過(guò)使數(shù)據(jù)結(jié)構(gòu)更復(fù)雜來(lái)改善性能的典型例子：調(diào)度程序的操作效率的確更高了，但運(yùn)行隊(duì)列的鏈表卻為此被拆分成140個(gè)不同的隊(duì)列！

內(nèi)核必須為系統(tǒng)中每個(gè)運(yùn)行隊(duì)列保存大量的數(shù)據(jù)，不過(guò)運(yùn)行隊(duì)列的主要數(shù)據(jù)結(jié)構(gòu)還是組成運(yùn)行隊(duì)列的進(jìn)程描述符鏈表，所有這些鏈表都由一個(gè)單獨(dú)的prio_array_t數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。

enqueue_task(p,array)函數(shù)把進(jìn)程描述符（p參數(shù)）插入到某個(gè)運(yùn)行隊(duì)列的鏈表（基于prio_array_t結(jié)構(gòu)的array參數(shù)），其代碼本質(zhì)上等同于如下代碼：

list_add_tail(&p->run_list, &array->queue[p->prio]);

__set_bit(p->prio, array->bitmap);

array->nr_active++;

p->array = array;

進(jìn)程描述符的prio字段存放進(jìn)程的動(dòng)態(tài)優(yōu)先權(quán)，而array字段是一個(gè)指針，指向當(dāng)前運(yùn)行隊(duì)列的proo_array_t數(shù)據(jù)結(jié)構(gòu)。類似地，dequeue_task(p,array)函數(shù)從運(yùn)行隊(duì)列的鏈表中刪除一個(gè)進(jìn)程的描述符。

7）進(jìn)程間關(guān)系

父子兄弟關(guān)系：

程序創(chuàng)建的進(jìn)程具有父/子關(guān)系。如果一個(gè)進(jìn)程創(chuàng)建多個(gè)子進(jìn)程時(shí)，則子進(jìn)程之間具有兄弟關(guān)系。進(jìn)程0和進(jìn)程1是由內(nèi)核創(chuàng)建的；進(jìn)程1（init）是所有進(jìn)程的祖先。

在進(jìn)程描述符中引入幾個(gè)字段來(lái)表示這些關(guān)系，我們假設(shè)擁有該task_struct結(jié)構(gòu)的這個(gè)進(jìn)程叫P：

real_parent——指向創(chuàng)建了P進(jìn)程的描述符，如果進(jìn)程P的父進(jìn)程不存在，就指向進(jìn)程1的描述符（因此，如果用戶運(yùn)行了一個(gè)后臺(tái)進(jìn)程而且退出了shell，后臺(tái)進(jìn)程就會(huì)變成init的子進(jìn)程）。

parent——指向P的當(dāng)前父進(jìn)程（這種進(jìn)程的子進(jìn)程終止時(shí)，必須向父進(jìn)程發(fā)信號(hào)）。它的值通常與reak_parent一致，但偶爾也可以不同，例如，當(dāng)另一個(gè)進(jìn)程發(fā)出監(jiān)控P的ptrace系統(tǒng)調(diào)用請(qǐng)求時(shí)。

children——鏈表的頭部，鏈表中所有的元素都是P創(chuàng)建的子進(jìn)程。

sibling——指向兄弟進(jìn)程鏈表中的下一個(gè)元素或前一個(gè)元素的指針，這些兄弟進(jìn)程的父進(jìn)程跟P是一樣的。

下圖顯示了一組進(jìn)程間的親屬關(guān)系，進(jìn)程P0創(chuàng)建了P1，P2，P3，進(jìn)程P3又創(chuàng)建了P4。

其他關(guān)系：此外，進(jìn)程之間還存在其他關(guān)系：一個(gè)進(jìn)程可能是一個(gè)進(jìn)程組或登錄會(huì)話的領(lǐng)頭進(jìn)程，也可能是一個(gè)線程組的領(lǐng)頭進(jìn)程，他還可能跟蹤其他進(jìn)程的執(zhí)行，下面就列出進(jìn)程描述符中的一些字段，這些字段建立起了進(jìn)程P和其他進(jìn)程之間的關(guān)系：

group_leader——P所在進(jìn)程組的領(lǐng)頭進(jìn)程的描述符指針

signal->pgrp——P所在進(jìn)程組的領(lǐng)頭進(jìn)程的PID

tgid——P所在線程組的領(lǐng)頭進(jìn)程的PID

signal->session——P的登錄會(huì)話領(lǐng)頭進(jìn)程的PID

ptrace_children——鏈表的頭，該鏈表包含所有被debugger程序跟蹤的P的子進(jìn)程

ptrace_list——指向所跟蹤進(jìn)程其實(shí)際父進(jìn)程鏈表的前一個(gè)和下一個(gè)元素（用于P被跟蹤的時(shí)候）

8）PID定位task_struct

再來(lái)，內(nèi)核必須能從進(jìn)程的PID導(dǎo)出對(duì)應(yīng)的進(jìn)程描述符指針。例如，為kill()系統(tǒng)調(diào)用提供服務(wù)時(shí)就會(huì)發(fā)生這種情況：當(dāng)進(jìn)程P1希望向另一個(gè)進(jìn)程P2發(fā)送一個(gè)信號(hào)時(shí)，P1調(diào)用kill()系統(tǒng)調(diào)用，其參數(shù)為P2的PID，內(nèi)核從這個(gè)PID導(dǎo)出其對(duì)應(yīng)的進(jìn)程描述符，然后從該task_struct中取出記錄掛起信號(hào)的數(shù)據(jù)結(jié)構(gòu)指針。

那么如何得到這個(gè)task_struct呢？首先想到for_each_process(p)。不行，雖然順序掃描進(jìn)程鏈表并檢查進(jìn)程描述符的pid字段是可行的，但相當(dāng)?shù)托?。為了加速查找，Linux內(nèi)核引入了4個(gè)散列表。需要4個(gè)散列表是因?yàn)檫M(jìn)程描述符包含了表示不同類型PID的字段，而且每種類型的PID需要它自己的散列表：

PIDTYPE_PID??? pid??? 進(jìn)程的PID

PIDTYPE_TGID??? tgid??? 線程組領(lǐng)頭進(jìn)程的PID

PIDTYPE_PGID??? pgrp??? 進(jìn)程組領(lǐng)頭進(jìn)程的PID

PIDTYPE_SID??? session??? 會(huì)話領(lǐng)頭的PID

內(nèi)核初始化期間動(dòng)態(tài)地為4個(gè)散列表分配空間，并把它們的地址存入pid_hash數(shù)組。一個(gè)散列表的長(zhǎng)度依賴于可用的RAM的容量，例如：一個(gè)系統(tǒng)擁有512MB的RAM，那么每個(gè)散列表就被存在4個(gè)頁(yè)框中，可擁有2048個(gè)表項(xiàng)。

用pid_hashfn宏把PID轉(zhuǎn)化為表索引：

#define pid_hashfn(x) hash_long((unsigned long) x, pidhash_shift)

變量pidhash_shift用來(lái)存放表索引的長(zhǎng)度（以位為單位的長(zhǎng)度，在我們這里是11位）。很多散列函數(shù)都使用hash_long()，在32位體系結(jié)構(gòu)中它基本等價(jià)于：

unsigned long hash_long(unsigned long val, unsigned int bits)

{

unsigned long hash = val * 0x9e370001UL;

return hash >> (32 - bits);

}

因?yàn)槲覀冞@里的pidhash_shift等于11，所以pid_hashfn的取值范圍是0到2^11 - 1=2047。

正如計(jì)算機(jī)科學(xué)的基礎(chǔ)課程所闡述的那樣，散列函數(shù)并不總能確保PID與表的索引一一對(duì)應(yīng)。兩個(gè)不同的PID散列到相同的表索引稱為沖突（colliding）。Linux利用鏈表來(lái)處理沖突的PID：每個(gè)表項(xiàng)是由沖突的進(jìn)程描述符組成的雙向循環(huán)鏈表

（二）進(jìn)程調(diào)度

1）進(jìn)程調(diào)度的目標(biāo)

1.高效性：高效意味著在相同的時(shí)間下要完成更多的任務(wù)，調(diào)度程序會(huì)被頻繁的執(zhí)行，所以調(diào)度程序要盡可能高效。

2.加強(qiáng)交互性能：在系統(tǒng)相當(dāng)?shù)呢?fù)載下，也要保證系統(tǒng)的響應(yīng)時(shí)間

3.保證公平和避免饑渴

4.SMP調(diào)度：調(diào)度程序必須支持多處理系統(tǒng)

5.軟實(shí)時(shí)調(diào)度：系統(tǒng)必須有效的調(diào)用實(shí)時(shí)進(jìn)程，但不保證一定滿足其要求。

2）進(jìn)程優(yōu)先級(jí)

進(jìn)程提供了兩種優(yōu)先級(jí)，一種是普通的進(jìn)程優(yōu)先級(jí)，一種是實(shí)時(shí)進(jìn)程優(yōu)先級(jí)。

前者適用SCHED_NORMAL調(diào)度策略，后者可選SCHED_FIFO或SCHED_RR調(diào)度策略，任何時(shí)候，實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)都高于普通進(jìn)程，實(shí)時(shí)進(jìn)程只會(huì)被更高級(jí)的實(shí)時(shí)進(jìn)程搶占，同級(jí)實(shí)時(shí)進(jìn)程之間是按照FIFO（一次機(jī)會(huì)做完）或者RR（多次輪轉(zhuǎn)）規(guī)則調(diào)度的。

實(shí)時(shí)進(jìn)程，只有靜態(tài)優(yōu)先級(jí)，因?yàn)閮?nèi)核不會(huì)再根據(jù)休眠等因素對(duì)其靜態(tài)優(yōu)先級(jí)做調(diào)整，其范圍在0~MAX_RT_PRIO-1間。默認(rèn)MAX_RT_PRIO配置為100，也即，默認(rèn)的實(shí)時(shí)優(yōu)先級(jí)范圍是0~99。而nice值，影響的是優(yōu)先級(jí)在MAX_RT_PRIO~MAX_RT_PRIO+40范圍內(nèi)的進(jìn)程。

不同與普通進(jìn)程，系統(tǒng)調(diào)度時(shí)，實(shí)時(shí)優(yōu)先級(jí)高的進(jìn)程總是先于優(yōu)先級(jí)低的進(jìn)程執(zhí)行，直到實(shí)時(shí)優(yōu)先級(jí)高的實(shí)時(shí)進(jìn)程無(wú)法執(zhí)行。實(shí)時(shí)進(jìn)程總是被認(rèn)為處于活動(dòng)狀態(tài)。如果有數(shù)個(gè) 優(yōu)先級(jí)相同的實(shí)時(shí)進(jìn)程，那么系統(tǒng)就會(huì)按照進(jìn)程出現(xiàn)在隊(duì)列上的順序選擇進(jìn)程，假設(shè)當(dāng)前CPU運(yùn)行的實(shí)時(shí)進(jìn)程A的優(yōu)先級(jí)為a，而此時(shí)有個(gè)優(yōu)先級(jí)為b的實(shí)時(shí)進(jìn)程B進(jìn)入可運(yùn)行狀態(tài)，那么只要b<a,系統(tǒng)將中斷A的執(zhí)行，而優(yōu)先執(zhí)行B，直到B無(wú)法執(zhí)行（無(wú)論A，B為何種實(shí)時(shí)進(jìn)程）。

不同調(diào)度策略的實(shí)時(shí)進(jìn)程只有在相同優(yōu)先級(jí)時(shí)才有可比性：

1. 對(duì)于FIFO的進(jìn)程，意味著只有當(dāng)前進(jìn)程執(zhí)行完畢才會(huì)輪到其他進(jìn)程執(zhí)行。由此可見相當(dāng)霸道。

2. 對(duì)于RR的進(jìn)程。一旦時(shí)間片消耗完畢，則會(huì)將該進(jìn)程置于隊(duì)列的末尾，然后運(yùn)行其他相同優(yōu)先級(jí)的進(jìn)程，如果沒(méi)有其他相同優(yōu)先級(jí)的進(jìn)程，則該進(jìn)程會(huì)繼續(xù)執(zhí)行。

總而言之，對(duì)于實(shí)時(shí)進(jìn)程，高優(yōu)先級(jí)的進(jìn)程就是大爺。它執(zhí)行到?jīng)]法執(zhí)行了，才輪到低優(yōu)先級(jí)的進(jìn)程執(zhí)行。

普通進(jìn)程的調(diào)度

Linux對(duì)于普通的進(jìn)程，根據(jù)動(dòng)態(tài)優(yōu)先級(jí)進(jìn)行調(diào)度，而動(dòng)態(tài)優(yōu)先級(jí)是由靜態(tài)優(yōu)先級(jí)調(diào)整而來(lái)，Linux下，靜態(tài)優(yōu)先級(jí)是用戶不可見的，隱藏在內(nèi)核中，而內(nèi)核提供給用戶一個(gè)可以影響靜態(tài)優(yōu)先級(jí)的接口，那就是nice值。

關(guān)系如下：

static_prio =MAX_RT_PRIO+nice+20

nice值的范圍是-20~19，因而靜態(tài)優(yōu)先級(jí)范圍在100~139之間,nice數(shù)值越大就使得static_prio越大，最終進(jìn)程優(yōu)先級(jí)就越低。

我們前面也說(shuō)了，系統(tǒng)調(diào)度時(shí)，還會(huì)考慮其他因素，因而會(huì)計(jì)算出一個(gè)叫進(jìn)程動(dòng)態(tài)優(yōu)先級(jí)的東西，根據(jù)此來(lái)實(shí)施調(diào)度。因?yàn)?，不僅要考慮靜態(tài)優(yōu)先級(jí)，也要考慮進(jìn)程

的屬性。例如如果進(jìn)程屬于交互式進(jìn)程，那么可以適當(dāng)?shù)恼{(diào)高它的優(yōu)先級(jí)，使得界面反應(yīng)地更加迅速，從而使用戶得到更好的體驗(yàn)。Linux2.6

在這方面有了較大的提高。Linux2.6認(rèn)為，交互式進(jìn)程可以從平均睡眠時(shí)間這樣一個(gè)measurement進(jìn)行判斷。進(jìn)程過(guò)去的睡眠時(shí)間越多，則越有

可能屬于交互式進(jìn)程。則系統(tǒng)調(diào)度時(shí)，會(huì)給該進(jìn)程更多的獎(jiǎng)勵(lì)（bonus），以便該進(jìn)程有更多的機(jī)會(huì)能夠執(zhí)行。獎(jiǎng)勵(lì)（bonus）從0到10不等。

系統(tǒng)會(huì)嚴(yán)格按照動(dòng)態(tài)優(yōu)先級(jí)高低的順序安排進(jìn)程執(zhí)行。動(dòng)態(tài)優(yōu)先級(jí)高的進(jìn)程進(jìn)入非運(yùn)行狀態(tài)，或者時(shí)間片消耗完畢才會(huì)輪到動(dòng)態(tài)優(yōu)先級(jí)較低的進(jìn)程執(zhí)行。動(dòng)態(tài)優(yōu)先級(jí)的計(jì)算主要考慮兩個(gè)因素：靜態(tài)優(yōu)先級(jí)，進(jìn)程的平均睡眠時(shí)間也即bonus。計(jì)算公式如下，

dynamic_prio?= max (100, min (static_prio - bonus?+ 5, 139))

為什么根據(jù)睡眠和運(yùn)行時(shí)間確定獎(jiǎng)懲分?jǐn)?shù)是合理的

睡眠和CPU耗時(shí)反應(yīng)了進(jìn)程IO密集和CPU密集兩大瞬時(shí)特點(diǎn)，不同時(shí)期，一個(gè)進(jìn)程可能即是CPU密集型也是IO密集型進(jìn)程。對(duì)于表現(xiàn)為IO密集的進(jìn)程，應(yīng)該經(jīng)常運(yùn)行，但每次時(shí)間片不要太長(zhǎng)。對(duì)于表現(xiàn)為CPU密集的進(jìn)程，CPU不應(yīng)該讓其經(jīng)常運(yùn)行，但每次運(yùn)行時(shí)間片要長(zhǎng)。交互進(jìn)程為例，假如之前其其大部分時(shí)間在于等待CPU，這時(shí)為了調(diào)高相應(yīng)速度，就需要增加獎(jiǎng)勵(lì)分。另一方面，如果此進(jìn)程總是耗盡每次分配給它的時(shí)間片，為了對(duì)其他進(jìn)程公平，就要增加這個(gè)進(jìn)程的懲罰分?jǐn)?shù)。可以參考CFS的virtutime機(jī)制.

3）現(xiàn)代方法CFS

不再單純依靠進(jìn)程優(yōu)先級(jí)絕對(duì)值，而是參考其絕對(duì)值，綜合考慮所有進(jìn)程的時(shí)間，給出當(dāng)前調(diào)度時(shí)間單位內(nèi)其應(yīng)有的權(quán)重，也就是，每個(gè)進(jìn)程的權(quán)重X單位時(shí)間=應(yīng)獲cpu時(shí)間，但是這個(gè)應(yīng)得的cpu時(shí)間不應(yīng)太小（假設(shè)閾值為1ms），否則會(huì)因?yàn)榍袚Q得不償失。但是，當(dāng)進(jìn)程足夠多時(shí)候，肯定有很多不同權(quán)重的進(jìn)程獲得相

同的時(shí)間——最低閾值1ms，所以，CFS只是近似完全公平。

4）Linux進(jìn)程狀態(tài)機(jī)

進(jìn)程是通過(guò)fork系列的系統(tǒng)調(diào)用（fork clone，vfork）來(lái)創(chuàng)建的，內(nèi)核，內(nèi)核模塊也可以通過(guò)kernel_thread函數(shù)創(chuàng)建內(nèi)核進(jìn)程，這些創(chuàng)建子進(jìn)程的函數(shù)本質(zhì)上都完成了相同的功能——將調(diào)用進(jìn)程復(fù)制一份，得到子進(jìn)程。（可以通過(guò)選項(xiàng)參數(shù)來(lái)決定各種資源是共享、還是私有。）那么既然調(diào)用進(jìn)程處于TASK_RUNNING狀態(tài)（否則，它若不是正在運(yùn)行，又怎么進(jìn)行調(diào)用？），則子進(jìn)程默認(rèn)也處于TASK_RUNNING狀態(tài)。

另外，在系統(tǒng)調(diào)用clone和內(nèi)核函數(shù)kernel_thread也接受CLONE_STOPPED選項(xiàng)，從而將子進(jìn)程的初始狀態(tài)置為 TASK_STOPPED。

進(jìn)程創(chuàng)建后，狀態(tài)可能發(fā)生一系列的變化，直到進(jìn)程退出。而盡管進(jìn)程狀態(tài)有好幾種，但是進(jìn)程狀態(tài)的變遷卻只有兩個(gè)方向——從TASK_RUNNING狀態(tài)變?yōu)榉荰ASK_RUNNING狀態(tài)、或者從非TASK_RUNNING狀態(tài)變?yōu)門ASK_RUNNING狀態(tài)?？傊?，TASK_RUNNING是必經(jīng)之路，不可能兩個(gè)非RUN狀態(tài)直接轉(zhuǎn)換。

也就是說(shuō)，如果給一個(gè)TASK_INTERRUPTIBLE狀態(tài)的進(jìn)程發(fā)送SIGKILL信號(hào)，這個(gè)進(jìn)程將先被喚醒（進(jìn)入TASK_RUNNING狀態(tài)），然后再響應(yīng)SIGKILL信號(hào)而退出（變?yōu)門ASK_DEAD狀態(tài)）。并不會(huì)從TASK_INTERRUPTIBLE狀態(tài)直接退出。

進(jìn)程從非TASK_RUNNING狀態(tài)變?yōu)門ASK_RUNNING狀態(tài)，是由別的進(jìn)程（也可能是中斷處理程序）執(zhí)行喚醒操作來(lái)實(shí)現(xiàn)的。執(zhí)行喚醒的

進(jìn)程設(shè)置被喚醒進(jìn)程的狀態(tài)為TASK_RUNNING，然后將其task_struct結(jié)構(gòu)加入到某個(gè)CPU的可執(zhí)行隊(duì)列中。于是被喚醒的進(jìn)程將有機(jī)會(huì)被

調(diào)度執(zhí)行。

而進(jìn)程從TASK_RUNNING狀態(tài)變?yōu)榉荰ASK_RUNNING狀態(tài)，則有兩種途徑：

1、響應(yīng)信號(hào)而進(jìn)入TASK_STOPED狀態(tài)、或TASK_DEAD狀態(tài)；

2、執(zhí)行系統(tǒng)調(diào)用主動(dòng)進(jìn)入TASK_INTERRUPTIBLE狀態(tài)（如nanosleep系統(tǒng)調(diào)用）、或TASK_DEAD狀態(tài)（如exit系統(tǒng)調(diào)用）；或由于執(zhí)行系統(tǒng)調(diào)用需要的資源得不到滿　　　　?足，而進(jìn)入TASK_INTERRUPTIBLE狀態(tài)或TASK_UNINTERRUPTIBLE狀態(tài)（如select系統(tǒng)調(diào)用）。

顯然，這兩種情況都只能發(fā)生在進(jìn)程正在CPU上執(zhí)行的情況下。

通過(guò)ps命令我們能夠查看到系統(tǒng)中存在的進(jìn)程，以及它們的狀態(tài)：R(TASK_RUNNING)，可執(zhí)行狀態(tài)。

只有在該狀態(tài)的進(jìn)程才可能在CPU上運(yùn)行。而同一時(shí)刻可能有多個(gè)進(jìn)程處于可執(zhí)行狀態(tài)，這些進(jìn)程的task_struct結(jié)構(gòu)（進(jìn)程控制塊）被放入對(duì)應(yīng)CPU的可執(zhí)行隊(duì)列中（一個(gè)進(jìn)程最多只能出現(xiàn)在一個(gè)CPU的可執(zhí)行隊(duì)列中）。進(jìn)程調(diào)度器的任務(wù)就是從各個(gè)CPU的可執(zhí)行隊(duì)列中分別選擇一個(gè)進(jìn)程在該CPU上運(yùn)行。

只要可執(zhí)行隊(duì)列不為空，其對(duì)應(yīng)的CPU就不能偷懶，就要執(zhí)行其中某個(gè)進(jìn)程。一般稱此時(shí)的CPU“忙碌”。對(duì)應(yīng)的，CPU“空閑”就是指其對(duì)應(yīng)的可執(zhí)行隊(duì)列為空，以致于CPU無(wú)事可做。

有人問(wèn)，為什么死循環(huán)程序會(huì)導(dǎo)致CPU占用高呢？因?yàn)樗姥h(huán)程序基本上總是處于TASK_RUNNING狀態(tài)（進(jìn)程處于可執(zhí)行隊(duì)列中）。除非一些非常極端情況（比如系統(tǒng)內(nèi)存嚴(yán)重緊缺，導(dǎo)致進(jìn)程的某些需要使用的頁(yè)面被換出，并且在頁(yè)面需要換入時(shí)又無(wú)法分配到內(nèi)存……），否則這個(gè)進(jìn)程不會(huì)睡眠。所以CPU的可執(zhí)行隊(duì)列總是不為空（至少有這么個(gè)進(jìn)程存在），CPU也就不會(huì)“空閑”。

很多操作系統(tǒng)教科書將正在CPU上執(zhí)行的進(jìn)程定義為RUNNING狀態(tài)、而將可執(zhí)行但是尚未被調(diào)度執(zhí)行的進(jìn)程定義為READY狀態(tài)，這兩種狀態(tài)在linux下統(tǒng)一為 TASK_RUNNING狀態(tài)。

S(TASK_INTERRUPTIBLE)，可中斷的睡眠狀態(tài)。

處于這個(gè)狀態(tài)的進(jìn)程因?yàn)榈却衬呈录陌l(fā)生（比如等待socket連接、等待信號(hào)量），而被掛起。這些進(jìn)程的task_struct結(jié)構(gòu)被放入對(duì)應(yīng)事件的等待隊(duì)列中。當(dāng)這些事件發(fā)生時(shí)（由外部中斷觸發(fā)、或由其他進(jìn)程觸發(fā)），對(duì)應(yīng)的等待隊(duì)列中的一個(gè)或多個(gè)進(jìn)程將被喚醒。

通過(guò)ps命令我們會(huì)看到，一般情況下，進(jìn)程列表中的絕大多數(shù)進(jìn)程都處于TASK_INTERRUPTIBLE狀態(tài)（除非機(jī)器的負(fù)載很高）。畢竟CPU就這么一兩個(gè)，進(jìn)程動(dòng)輒幾十上百個(gè)，如果不是絕大多數(shù)進(jìn)程都在睡眠，CPU又怎么響應(yīng)得過(guò)來(lái)。

D(TASK_UNINTERRUPTIBLE)，不可中斷的睡眠狀態(tài)。

與TASK_INTERRUPTIBLE狀態(tài)類似，進(jìn)程處于睡眠狀態(tài)，但是此刻進(jìn)程是不可中斷的。不可中斷，指的并不是CPU不響應(yīng)外部硬件的中斷，而是指進(jìn)程不響應(yīng)異步信號(hào)。

絕大多數(shù)情況下，進(jìn)程處在睡眠狀態(tài)時(shí)，總是應(yīng)該能夠響應(yīng)異步信號(hào)的。否則你將驚奇的發(fā)現(xiàn)，kill -9竟然殺不死一個(gè)正在睡眠的進(jìn)程了！于是我們也很好理解，為什么ps命令看到的進(jìn)程幾乎不會(huì)出現(xiàn)TASK_UNINTERRUPTIBLE狀態(tài)，而總是TASK_INTERRUPTIBLE狀態(tài)。

而TASK_UNINTERRUPTIBLE狀態(tài)存在的意義就在于，內(nèi)核的某些處理流程是不能被打斷的。如果響應(yīng)異步信號(hào)，程序的執(zhí)行流程中就會(huì)被插入一段用于處理異步信號(hào)的流程（這個(gè)插入的流程可能只存在于內(nèi)核態(tài)，也可能延伸到用戶態(tài)），于是原有的流程就被中斷了（參見《linux異步信號(hào)handle淺析》）。

在進(jìn)程對(duì)某些硬件進(jìn)行操作時(shí)（比如進(jìn)程調(diào)用read系統(tǒng)調(diào)用對(duì)某個(gè)設(shè)備文件進(jìn)行讀操作，而read系統(tǒng)調(diào)用最終執(zhí)行到對(duì)應(yīng)設(shè)備驅(qū)動(dòng)的代碼，并與對(duì)應(yīng)的物理設(shè)備進(jìn)行交互），可能需要使用TASK_UNINTERRUPTIBLE狀態(tài)對(duì)進(jìn)程進(jìn)行保護(hù)，以避免進(jìn)程與設(shè)備交互的過(guò)程被打斷，造成設(shè)備陷入不可控的狀態(tài)。（比如read系統(tǒng)調(diào)用觸發(fā)了一次磁盤到用戶空間的內(nèi)存的DMA，如果DMA進(jìn)行過(guò)程中，進(jìn)程由于響應(yīng)信號(hào)而退出了，那么DMA正在訪問(wèn)的內(nèi)存可能就要被釋放了。）這種情況下的TASK_UNINTERRUPTIBLE狀態(tài)總是非常短暫的，通過(guò)ps命令基本上不可能捕捉到。

linux系統(tǒng)中也存在容易捕捉的TASK_UNINTERRUPTIBLE狀態(tài)。執(zhí)行vfork系統(tǒng)調(diào)用后，父進(jìn)程將進(jìn)入TASK_UNINTERRUPTIBLE狀態(tài)，直到子進(jìn)程調(diào)用exit或exec。

通過(guò)下面的代碼就能得到處于TASK_UNINTERRUPTIBLE狀態(tài)的進(jìn)程：

#include

void main() {

if (!vfork()) sleep(100);

}

向進(jìn)程發(fā)送一個(gè)SIGSTOP信號(hào)，它就會(huì)因響應(yīng)該信號(hào)而進(jìn)入TASK_STOPPED狀態(tài)（除非該進(jìn)程本身處于TASK_UNINTERRUPTIBLE狀態(tài)而不響應(yīng)信號(hào)）。（SIGSTOP與SIGKILL信號(hào)一樣，是非常強(qiáng)制的。不允許用戶進(jìn)程通過(guò)signal系列的系統(tǒng)調(diào)用重新設(shè)置對(duì)應(yīng)的信號(hào)處理函數(shù)。）

向進(jìn)程發(fā)送一個(gè)SIGCONT信號(hào)，可以讓其從TASK_STOPPED狀態(tài)恢復(fù)到TASK_RUNNING狀態(tài)。

當(dāng)進(jìn)程正在被跟蹤時(shí)，它處于TASK_TRACED這個(gè)特殊的狀態(tài)?！罢诒桓櫋敝傅氖沁M(jìn)程暫停下來(lái)，等待跟蹤它的進(jìn)程對(duì)它進(jìn)行操作。比如在gdb中對(duì)被跟蹤的進(jìn)程下一個(gè)斷點(diǎn)，進(jìn)程在斷點(diǎn)處停下來(lái)的時(shí)候就處于TASK_TRACED狀態(tài)。而在其他時(shí)候，被跟蹤的進(jìn)程還是處于前面提到的那些狀態(tài)。

對(duì)于進(jìn)程本身來(lái)說(shuō)，TASK_STOPPED和TASK_TRACED狀態(tài)很類似，都是表示進(jìn)程暫停下來(lái)。

而TASK_TRACED狀態(tài)相當(dāng)于在TASK_STOPPED之上多了一層保護(hù)，處于TASK_TRACED狀態(tài)的進(jìn)程不能響應(yīng)SIGCONT信號(hào)而被喚醒。只能等到調(diào)試進(jìn)程通過(guò)ptrace系統(tǒng)調(diào)用執(zhí)行PTRACE_CONT、PTRACE_DETACH等操作（通過(guò)ptrace系統(tǒng)調(diào)用的參數(shù)指定操作），或調(diào)試進(jìn)程退出，被調(diào)試的進(jìn)程才能恢復(fù)TASK_RUNNING狀態(tài)。

Z(TASK_DEAD - EXIT_ZOMBIE)，退出狀態(tài)，進(jìn)程成為僵尸進(jìn)程。

進(jìn)程在退出的過(guò)程中，處于TASK_DEAD狀態(tài)。

在這個(gè)退出過(guò)程中，進(jìn)程占有的所有資源將被回收，除了task_struct結(jié)構(gòu)（以及少數(shù)資源）以外。于是進(jìn)程就只剩下task_struct這么個(gè)空殼，故稱為僵尸。

之所以保留task_struct，是因?yàn)閠ask_struct里面保存了進(jìn)程的退出碼、以及一些統(tǒng)計(jì)信息。而其父進(jìn)程很可能會(huì)關(guān)心這些信息。比如在shell中，$?變量就保存了最后一個(gè)退出的前臺(tái)進(jìn)程的退出碼，而這個(gè)退出碼往往被作為if語(yǔ)句的判斷條件。

當(dāng)然，內(nèi)核也可以將這些信息保存在別的地方，而將task_struct結(jié)構(gòu)釋放掉，以節(jié)省一些空間。但是使用task_struct結(jié)構(gòu)更為方便，因?yàn)樵趦?nèi)核中已經(jīng)建立了從pid到task_struct查找關(guān)系，還有進(jìn)程間的父子關(guān)系。釋放掉task_struct，則需要建立一些新的數(shù)據(jù)結(jié)構(gòu)，以便讓父進(jìn)程找到它的子進(jìn)程的退出信息。

父進(jìn)程可以通過(guò)wait系列的系統(tǒng)調(diào)用（如wait4、waitid）來(lái)等待某個(gè)或某些子進(jìn)程的退出，并獲取它的退出信息。然后wait系列的系統(tǒng)調(diào)用會(huì)順便將子進(jìn)程的尸體（task_struct）也釋放掉。

子進(jìn)程在退出的過(guò)程中，內(nèi)核會(huì)給其父進(jìn)程發(fā)送一個(gè)信號(hào)，通知父進(jìn)程來(lái)“收尸”。這個(gè)信號(hào)默認(rèn)是SIGCHLD，但是在通過(guò)clone系統(tǒng)調(diào)用創(chuàng)建子進(jìn)程時(shí)，可以設(shè)置這個(gè)信號(hào)。

通過(guò)下面的代碼能夠制造一個(gè)EXIT_ZOMBIE狀態(tài)的進(jìn)程：

#include

void main() {

if (fork())

while(1) sleep(100);

}

編譯運(yùn)行，然后ps一下：

kouu@kouu-one:~/test$ ps -ax | grep a\.out

10410 pts/0? ? ? S+? ? ? 0:00 ./a.out

10411 pts/0? ? ? Z+? ? ? 0:00 [a.out]

10413 pts/1? ? ? S+? ? ? 0:00 grep a.out

只要父進(jìn)程不退出，這個(gè)僵尸狀態(tài)的子進(jìn)程就一直存在。那么如果父進(jìn)程退出了呢，誰(shuí)又來(lái)給子進(jìn)程“收尸”？

當(dāng)進(jìn)程退出的時(shí)候，會(huì)將它的所有子進(jìn)程都托管給別的進(jìn)程（使之成為別的進(jìn)程的子進(jìn)程）。托管給誰(shuí)呢？可能是退出進(jìn)程所在進(jìn)程組的下一個(gè)進(jìn)程（如果存在的話），或者是1號(hào)進(jìn)程。所以每個(gè)進(jìn)程、每時(shí)每刻都有父進(jìn)程存在。除非它是1號(hào)進(jìn)程。

1號(hào)進(jìn)程，pid為1的進(jìn)程，又稱init進(jìn)程。

linux系統(tǒng)啟動(dòng)后，第一個(gè)被創(chuàng)建的用戶態(tài)進(jìn)程就是init進(jìn)程。它有兩項(xiàng)使命：

1、執(zhí)行系統(tǒng)初始化腳本，創(chuàng)建一系列的進(jìn)程（它們都是init進(jìn)程的子孫）；

2、在一個(gè)死循環(huán)中等待其子進(jìn)程的退出事件，并調(diào)用waitid系統(tǒng)調(diào)用來(lái)完成“收尸”工作；

init進(jìn)程不會(huì)被暫停、也不會(huì)被殺死（這是由內(nèi)核來(lái)保證的）。它在等待子進(jìn)程退出的過(guò)程中處于TASK_INTERRUPTIBLE狀態(tài)，“收尸”過(guò)程中則處于TASK_RUNNING狀態(tài)。

X(TASK_DEAD - EXIT_DEAD)，退出狀態(tài)，進(jìn)程即將被銷毀。

而進(jìn)程在退出過(guò)程中也可能不會(huì)保留它的task_struct。比如這個(gè)進(jìn)程是多線程程序中被detach過(guò)的進(jìn)程（進(jìn)程？線程？參見《linux線程淺析》）?；蛘吒高M(jìn)程通過(guò)設(shè)置SIGCHLD信號(hào)的handler為SIG_IGN，顯式的忽略了SIGCHLD信號(hào)。（這是posix的規(guī)定，盡管子進(jìn)程的退出信號(hào)可以被設(shè)置為SIGCHLD以外的其他信號(hào)。）

此時(shí)，進(jìn)程將被置于EXIT_DEAD退出狀態(tài)，這意味著接下來(lái)的代碼立即就會(huì)將該進(jìn)程徹底釋放。所以EXIT_DEAD狀態(tài)是非常短暫的，幾乎不可能通過(guò)ps命令捕捉到。

5）調(diào)度觸發(fā)的時(shí)機(jī)

調(diào)度的觸發(fā)主要有如下幾種情況：

1、當(dāng)前進(jìn)程（正在CPU上運(yùn)行的進(jìn)程）狀態(tài)變?yōu)榉强蓤?zhí)行狀態(tài)。

進(jìn)程執(zhí)行系統(tǒng)調(diào)用主動(dòng)變?yōu)榉强蓤?zhí)行狀態(tài)。比如執(zhí)行nanosleep進(jìn)入睡眠、執(zhí)行exit退出、等等；

進(jìn)程請(qǐng)求的資源得不到滿足而被迫進(jìn)入睡眠狀態(tài)。比如執(zhí)行read系統(tǒng)調(diào)用時(shí)，磁盤高速緩存里沒(méi)有所需要的數(shù)據(jù)，從而睡眠等待磁盤IO；

進(jìn)程響應(yīng)信號(hào)而變?yōu)榉强蓤?zhí)行狀態(tài)。比如響應(yīng)SIGSTOP進(jìn)入暫停狀態(tài)、響應(yīng)SIGKILL退出、等等；

2、搶占。進(jìn)程運(yùn)行時(shí)，非預(yù)期地被剝奪CPU的使用權(quán)。這又分兩種情況：進(jìn)程用完了時(shí)間片、或出現(xiàn)了優(yōu)先級(jí)更高的進(jìn)程。

優(yōu)先級(jí)更高的進(jìn)程受正在CPU上運(yùn)行的進(jìn)程的影響而被喚醒。如發(fā)送信號(hào)主動(dòng)喚醒，或因?yàn)獒尫呕コ鈱?duì)象（如釋放鎖）而被喚醒；

內(nèi)核在響應(yīng)時(shí)鐘中斷的過(guò)程中，發(fā)現(xiàn)當(dāng)前進(jìn)程的時(shí)間片用完；

內(nèi)核在響應(yīng)中斷的過(guò)程中，發(fā)現(xiàn)優(yōu)先級(jí)更高的進(jìn)程所等待的外部資源的變?yōu)榭捎?，從而將其喚醒。比如CPU收到網(wǎng)卡中斷，內(nèi)核處理該中斷，發(fā)現(xiàn)某個(gè)socket可讀，于是喚醒正在等待讀這個(gè)socket的進(jìn)程；再比如內(nèi)核在處理時(shí)鐘中斷的過(guò)程中，觸發(fā)了定時(shí)器，從而喚醒對(duì)應(yīng)的正在nanosleep系統(tǒng)調(diào)用中睡眠的進(jìn)程；

6）內(nèi)核搶占

理想情況下，只要滿足“出現(xiàn)了優(yōu)先級(jí)更高的進(jìn)程”這個(gè)條件，當(dāng)前進(jìn)程就應(yīng)該被立刻搶占。但是，就像多線程程序需要用鎖來(lái)保護(hù)臨界區(qū)資源一樣，內(nèi)核中也存在很多這樣的臨界區(qū)，不大可能隨時(shí)隨地都能接收搶占。

linux 2.4時(shí)的設(shè)計(jì)就非常簡(jiǎn)單，內(nèi)核不支持搶占。進(jìn)程運(yùn)行在內(nèi)核態(tài)時(shí)（比如正在執(zhí)行系統(tǒng)調(diào)用、正處于異常處理函數(shù)中），是不允許搶占的。必須等到返回用戶態(tài)時(shí)才會(huì)觸發(fā)調(diào)度（確切的說(shuō)，是在返回用戶態(tài)之前，內(nèi)核會(huì)專門檢查一下是否需要調(diào)度）；

linux 2.6則實(shí)現(xiàn)了內(nèi)核搶占，但是在很多地方還是為了保護(hù)臨界區(qū)資源而需要臨時(shí)性的禁用內(nèi)核搶占。

也有一些地方是出于效率考慮而禁用搶占，比較典型的是spin_lock。spin_lock是這樣一種鎖，如果請(qǐng)求加鎖得不到滿足（鎖已被別的進(jìn)程占有），則當(dāng)前進(jìn)程在一個(gè)死循環(huán)中不斷檢測(cè)鎖的狀態(tài)，直到鎖被釋放。

為什么要這樣忙等待呢？因?yàn)榕R界區(qū)很小，比如只保護(hù)“i+=j++;”這么一句。如果因?yàn)榧渔i失敗而形成“睡眠-喚醒”這么個(gè)過(guò)程，就有些得不償失了。

那么既然當(dāng)前進(jìn)程忙等待（不睡眠），誰(shuí)又來(lái)釋放鎖呢？其實(shí)已得到鎖的進(jìn)程是運(yùn)行在另一個(gè)CPU上的，并且是禁用了內(nèi)核搶占的。這個(gè)進(jìn)程不會(huì)被其他進(jìn)程搶占，所以等待鎖的進(jìn)程只有可能運(yùn)行在別的CPU上。（如果只有一個(gè)CPU呢？那么就不可能存在等待鎖的進(jìn)程了。）

而如果不禁用內(nèi)核搶占呢？那么得到鎖的進(jìn)程將可能被搶占，于是可能很久都不會(huì)釋放鎖。于是，等待鎖的進(jìn)程可能就不知何年何月得償所望了。

對(duì)于一些實(shí)時(shí)性要求更高的系統(tǒng)，則不能容忍spin_lock這樣的東西。寧可改用更費(fèi)勁的“睡眠-喚醒”過(guò)程，也不能因?yàn)榻脫屨级尭邇?yōu)先級(jí)的進(jìn)程等待。比如，嵌入式實(shí)時(shí)linux montavista就是這么干的。

由此可見，實(shí)時(shí)并不代表高效。很多時(shí)候?yàn)榱藢?shí)現(xiàn)“實(shí)時(shí)”，還是需要對(duì)性能做一定讓步的。

7）多處理器下的負(fù)載均衡

前面我們并沒(méi)有專門討論多處理器對(duì)調(diào)度程序的影響，其實(shí)也沒(méi)有什么特別的，就是在同一時(shí)刻能有多個(gè)進(jìn)程并行地運(yùn)行而已。那么，為什么會(huì)有“多處理器負(fù)載均衡”這個(gè)事情呢？

如果系統(tǒng)中只有一個(gè)可執(zhí)行隊(duì)列，哪個(gè)CPU空閑了就去隊(duì)列中找一個(gè)最合適的進(jìn)程來(lái)執(zhí)行。這樣不是很好很均衡嗎？

的確如此，但是多處理器共用一個(gè)可執(zhí)行隊(duì)列會(huì)有一些問(wèn)題。顯然，每個(gè)CPU在執(zhí)行調(diào)度程序時(shí)都需要把隊(duì)列鎖起來(lái)，這會(huì)使得調(diào)度程序難以并行，可能導(dǎo)致系統(tǒng)性能下降。而如果每個(gè)CPU對(duì)應(yīng)一個(gè)可執(zhí)行隊(duì)列則不存在這樣的問(wèn)題。

另外，多個(gè)可執(zhí)行隊(duì)列還有一個(gè)好處。這使得一個(gè)進(jìn)程在一段時(shí)間內(nèi)總是在同一個(gè)CPU上執(zhí)行，那么很可能這個(gè)CPU的各級(jí)cache中都緩存著這個(gè)進(jìn)程的數(shù)據(jù)，很有利于系統(tǒng)性能的提升。

所以，在linux下，每個(gè)CPU都有著對(duì)應(yīng)的可執(zhí)行隊(duì)列，而一個(gè)可執(zhí)行狀態(tài)的進(jìn)程在同一時(shí)刻只能處于一個(gè)可執(zhí)行隊(duì)列中。

于是，“多處理器負(fù)載均衡”這個(gè)麻煩事情就來(lái)了。內(nèi)核需要關(guān)注各個(gè)CPU可執(zhí)行隊(duì)列中的進(jìn)程數(shù)目，在數(shù)目不均衡時(shí)做出適當(dāng)調(diào)整。什么時(shí)候需要調(diào)整，以多大力度進(jìn)程調(diào)整，這些都是內(nèi)核需要關(guān)心的。當(dāng)然，盡量不要調(diào)整最好，畢竟調(diào)整起來(lái)又要耗CPU、又要鎖可執(zhí)行隊(duì)列，代價(jià)還是不小的。

另外，內(nèi)核還得關(guān)心各個(gè)CPU的關(guān)系。兩個(gè)CPU之間，可能是相互獨(dú)立的、可能是共享cache的、甚至可能是由同一個(gè)物理CPU通過(guò)超線程技術(shù)虛擬出來(lái)的……CPU之間的關(guān)系也是實(shí)現(xiàn)負(fù)載均衡的重要依據(jù)。關(guān)系越緊密，進(jìn)程在它們之間遷移的代價(jià)就越小。參見《linux內(nèi)核SMP負(fù)載均衡淺析》。

優(yōu)先級(jí)繼承

由于互斥，一個(gè)進(jìn)程（設(shè)為A）可能因?yàn)榈却M(jìn)入臨界區(qū)而睡眠。直到正在占有相應(yīng)資源的進(jìn)程（設(shè)為B）退出臨界區(qū)，進(jìn)程A才被喚醒。

可能存在這樣的情況：A的優(yōu)先級(jí)非常高，B的優(yōu)先級(jí)非常低。B進(jìn)入了臨界區(qū)，但是卻被其他優(yōu)先級(jí)較高的進(jìn)程（設(shè)為C）搶占了，而得不到運(yùn)行，也就無(wú)法退出臨界區(qū)。于是A也就無(wú)法被喚醒。

A有著很高的優(yōu)先級(jí)，但是現(xiàn)在卻淪落到跟B一起，被優(yōu)先級(jí)并不太高的C搶占，導(dǎo)致執(zhí)行被推遲。這種現(xiàn)象就叫做優(yōu)先級(jí)反轉(zhuǎn)。

出現(xiàn)這種現(xiàn)象是很不合理的。較好的應(yīng)對(duì)措施是：當(dāng)A開始等待B退出臨界區(qū)時(shí)，B臨時(shí)得到A的優(yōu)先級(jí)（還是假設(shè)A的優(yōu)先級(jí)高于B），以便順利完成處理過(guò)程，退出臨界區(qū)。之后B的優(yōu)先級(jí)恢復(fù)。這就是優(yōu)先級(jí)繼承的方法。

中斷處理線程化

在linux下，中斷處理程序運(yùn)行于一個(gè)不可調(diào)度的上下文中。從CPU響應(yīng)硬件中斷自動(dòng)跳轉(zhuǎn)到內(nèi)核設(shè)定的中斷處理程序去執(zhí)行，到中斷處理程序退出，整個(gè)過(guò)程是不能被搶占的。

一個(gè)進(jìn)程如果被搶占了，可以通過(guò)保存在它的進(jìn)程控制塊（task_struct）中的信息，在之后的某個(gè)時(shí)間恢復(fù)它的運(yùn)行。而中斷上下文則沒(méi)有task_struct，被搶占了就沒(méi)法恢復(fù)了。

中斷處理程序不能被搶占，也就意味著中斷處理程序的“優(yōu)先級(jí)”比任何進(jìn)程都高（必須等中斷處理程序完成了，進(jìn)程才能被執(zhí)行）。但是在實(shí)際的應(yīng)用場(chǎng)景中，可能某些實(shí)時(shí)進(jìn)程應(yīng)該得到比中斷處理程序更高的優(yōu)先級(jí)。

于是，一些實(shí)時(shí)性要求更高的系統(tǒng)就給中斷處理程序賦予了task_struct以及優(yōu)先級(jí)，使得它們?cè)诒匾臅r(shí)候能夠被高優(yōu)先級(jí)的進(jìn)程搶占。但是顯然，做這些工作是會(huì)給系統(tǒng)造成一定開銷的，這也是為了實(shí)現(xiàn)“實(shí)時(shí)”而對(duì)性能做出的一種讓步。

（三）進(jìn)程同步與互斥

多進(jìn)程系統(tǒng)中避免不了進(jìn)程之間的相互關(guān)系，最主要是兩種關(guān)系--同步和互斥。

進(jìn)程同步 是進(jìn)程間直接的相互作用，是合作進(jìn)程間的有意識(shí)的行為。我們也要有一定的同步機(jī)制保證它們的執(zhí)行次序。

進(jìn)程互斥是進(jìn)程之間發(fā)生的一種間接性作用，一般是程序不希望的。通常的情況是兩個(gè)或兩個(gè)以上的進(jìn)程需要同時(shí)訪問(wèn)某個(gè)共享變量。我們一般將發(fā)生能夠問(wèn)共享變量的程序段稱為臨界區(qū)。兩個(gè)進(jìn)程不能同時(shí)進(jìn)入臨界區(qū)，否則就會(huì)導(dǎo)致數(shù)據(jù)的不一致，產(chǎn)生與時(shí)間有關(guān)的錯(cuò)誤。解決互斥問(wèn)題應(yīng)該滿足互斥和公平兩個(gè)原則，即任意時(shí)刻只能允許一個(gè)進(jìn)程處于同一共享變量的臨界區(qū)，而且不能讓任一進(jìn)程無(wú)限期地等待?；コ鈫?wèn)題可以用硬件方法解決，也可以用軟件方法。

同步是說(shuō)進(jìn)程的合作關(guān)系，互斥是說(shuō)進(jìn)程對(duì)資源的競(jìng)爭(zhēng)關(guān)系。

信號(hào)量、管程

二，管程：參考自http://hi.baidu.com/zucenaa/blog/item/e63d22277c9d9c09918f9de2.html

信號(hào)量機(jī)制功能強(qiáng)大，但使用時(shí)對(duì)信號(hào)量的操作分散，而且難以控制，讀寫和維護(hù)都很困難。因此后

來(lái)又提出了一種集中式同步進(jìn)程——管程。其基本思想是將共享變量和對(duì)它們的操作集中在一個(gè)模塊中，操作系統(tǒng)或并發(fā)程序就由這樣的模塊構(gòu)成。這樣模塊之間聯(lián)

系清晰，便于維護(hù)和修改，易于保證正確性。

管程作為一個(gè)模塊，它的類型定義如下：

monitor_name = MoNITOR;

共享變量說(shuō)明;

define 本管程內(nèi)部定義、外部可調(diào)用的函數(shù)名表;

use 本管程外部定義、內(nèi)部可調(diào)用的函數(shù)名表;

內(nèi)部定義的函數(shù)說(shuō)明和函數(shù)體

{

共享變量初始化語(yǔ)句;

}

從語(yǔ)言的角度看，管程主要有以下特性：

（1）模塊化。管程是一個(gè)基本程序單位，可以單獨(dú)編譯;

（2）抽象數(shù)據(jù)類型。管程是中不僅有數(shù)據(jù)，而且有對(duì)數(shù)據(jù)的操作;

（3）信息掩蔽。管程外可以調(diào)用管程內(nèi)部定義的一些函數(shù)，但函數(shù)的具體實(shí)現(xiàn)外部不可見;

對(duì)于管程中定義的共享變量的所有操作都局限在管程中，外部只能通過(guò)調(diào)用管程的某些函數(shù)來(lái)間接訪問(wèn)這些變量。因此管程有很好的封裝性。

為了保證共享變量的數(shù)據(jù)一致性，管程應(yīng)互斥使用。 管程通常是用于管理資源的，因此管程中有進(jìn)程等待隊(duì)列和相應(yīng)的等待和喚醒操作。在管程入口有一個(gè)等待隊(duì)列，稱為入口等待隊(duì)列。當(dāng)一個(gè)已進(jìn)入管程的進(jìn)程等待時(shí)，就釋放管程的互斥使用權(quán)；當(dāng)已進(jìn)入管程的一個(gè)進(jìn)程喚醒另一個(gè)進(jìn)程時(shí)，兩者必須有一個(gè)退出或停止使用管程。在管程內(nèi)部，由于執(zhí)行喚醒操作，可能存在多個(gè)等待進(jìn)程（等待使用管程），稱為緊急等待隊(duì)列，它的優(yōu)先級(jí)高于入口等待隊(duì)列。

因此，一個(gè)進(jìn)程進(jìn)入管程之前要先申請(qǐng)，一般由管程提供一個(gè)enter過(guò)程；離開時(shí)釋放使用權(quán)，如果緊急等待隊(duì)列不空，則喚醒第一個(gè)等待者，一般也由管程提供外部過(guò)程leave。

管程內(nèi)部有自己的等待機(jī)制。管程可以說(shuō)明一種特殊的條件型變量：var c:condition；實(shí)際上是一個(gè)指針，指向一個(gè)等待該條件的PCB隊(duì)列。對(duì)條件型變量可執(zhí)行wait和signal操作：（聯(lián)系P和V； take和give）

wait(c):若緊急等待隊(duì)列不空，喚醒第一個(gè)等待者，否則釋放管程使用權(quán)。執(zhí)行本操作的進(jìn)程進(jìn)入C隊(duì)列尾部；

signal(c):若C隊(duì)列為空，繼續(xù)原進(jìn)程，否則喚醒隊(duì)列第一個(gè)等待者，自己進(jìn)入緊急等待隊(duì)列尾部。

（四）進(jìn)程間通信（IPC）

進(jìn)程間通信主要包括 管道，系統(tǒng)IPC(包括消息隊(duì)列,信號(hào)量,共享內(nèi)存), SOCKET.

管道分為有名管道和無(wú)名管道，無(wú)名管道只能用于親屬進(jìn)程之間的通信，而有名管道則可用于無(wú)親屬關(guān)系的進(jìn)程之間。

消息隊(duì)列用于運(yùn)行于同一臺(tái)機(jī)器上的進(jìn)程間通信，與管道相似；

消息隊(duì)列用于運(yùn)行于同一臺(tái)機(jī)器上的進(jìn)程間通信，與管道相似；

共享內(nèi)存通常由一個(gè)進(jìn)程創(chuàng)建，其余進(jìn)程對(duì)這塊內(nèi)存區(qū)進(jìn)行讀寫。得到共享內(nèi)存有兩種方式：映射/dev/mem設(shè)備和內(nèi)存映像文件。前一種方式不給系統(tǒng)帶來(lái)額外的開銷，但在現(xiàn)實(shí)中并不常用，因?yàn)樗刂拼嫒〉氖菍?shí)際的物理內(nèi)存；

本質(zhì)上，信號(hào)量是一個(gè)計(jì)數(shù)器，它用來(lái)記錄對(duì)某個(gè)資源（如共享內(nèi)存）的存取狀況。一般說(shuō)來(lái)，為了獲得共享資源，進(jìn)程需要執(zhí)行下列操作：

（1）測(cè)試控制該資源的信號(hào)量；

（2）若此信號(hào)量的值為正，則允許進(jìn)行使用該資源，進(jìn)程將進(jìn)號(hào)量減1；

（3）若此信號(hào)量為0，則該資源目前不可用，進(jìn)程進(jìn)入睡眠狀態(tài)，直至信號(hào)量值大于0，進(jìn)程被喚醒，轉(zhuǎn)入步驟（1）；

（4）當(dāng)進(jìn)程不再使用一個(gè)信號(hào)量控制的資源時(shí)，信號(hào)量值加1，如果此時(shí)有進(jìn)程正在睡眠等待此信號(hào)量，則喚醒此進(jìn)程。

套接字通信并不為L(zhǎng)inux所專有，在所有提供了TCP/IP協(xié)議棧的操作系統(tǒng)中幾乎都提供了socket，而所有這樣操作系統(tǒng)，對(duì)套接字的編程方法幾乎是完全一樣的。

管道：速度慢，容量有限，只有父子進(jìn)程能通訊

FIFO（命名管道）：任何進(jìn)程間都能通訊，但速度慢，命名管道可用于非父子進(jìn)程，命名管道就是FIFO，管道是先進(jìn)先出的通訊方式

消息隊(duì)列：容量受到系統(tǒng)限制，且要注意第一次讀的時(shí)候，要考慮上一次沒(méi)有讀完數(shù)據(jù)的問(wèn)題

信號(hào)量：不能傳遞復(fù)雜消息，只能用來(lái)同步

共享內(nèi)存區(qū)：能夠很容易控制容量，速度快，但要保持同步，比如一個(gè)進(jìn)程在寫的時(shí)候，另一個(gè)進(jìn)程要注意讀寫的問(wèn)題，相當(dāng)于線程中的線程安全，當(dāng)然，共享內(nèi)存區(qū)同樣可以用作線程間通訊，不過(guò)沒(méi)這個(gè)必要，線程間本來(lái)就已經(jīng)共享了同一進(jìn)程內(nèi)的一塊內(nèi)存。

線程

線程是CPU調(diào)度的最小單位，多個(gè)線程共享一個(gè)進(jìn)程的地址空間。

線程包含線程ID，程序計(jì)數(shù)器，寄存器和棧。

（一）線程調(diào)度

（二）線程同步