一、進(jìn)程與線程

1. 進(jìn)程的概念、組成、特征

在多道程序環(huán)境下，允許多個(gè)程序并發(fā)執(zhí)行，此時(shí)他們將失去封閉性，并具有間斷性和不可再現(xiàn)性的特征。為此引入了進(jìn)程的概念，以便更好地描述和控制程序的并發(fā)執(zhí)行，實(shí)現(xiàn)操作系統(tǒng)的并發(fā)行和共享性。為此引入了進(jìn)程的概念，以便更好地描述和控制程序的并發(fā)執(zhí)行，實(shí)現(xiàn)操作系統(tǒng)的并發(fā)性和共享性。

為了是參與并發(fā)執(zhí)行的程序能獨(dú)立的運(yùn)行，必須為之配置一個(gè)專門的數(shù)據(jù)結(jié)構(gòu)，稱之為進(jìn)程控制塊（process control block），系統(tǒng)利用PCB來描述進(jìn)程的基本情況和運(yùn)行狀態(tài)，進(jìn)而控制和管理進(jìn)程。

相應(yīng)的，有程序段、相關(guān)數(shù)據(jù)段和PCB三部分構(gòu)成了進(jìn)程映像（進(jìn)程實(shí)體）。所謂創(chuàng)建進(jìn)程，實(shí)質(zhì)上是創(chuàng)建進(jìn)程映像中的PCB；而撤銷進(jìn)程，實(shí)質(zhì)上是撤銷進(jìn)程的PCB。指的注意的是，進(jìn)程影響是靜態(tài)的，進(jìn)程是動(dòng)態(tài)的。

從不同的角度，進(jìn)程可以有不同的定義，比較經(jīng)典的定義有：

1） 進(jìn)程是程序的一次執(zhí)行過程

2） 進(jìn)程是一個(gè)程序及其數(shù)據(jù)在處理器上順序執(zhí)行時(shí)所發(fā)生的活動(dòng)。

3） 進(jìn)程是具有獨(dú)立功能的程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過程，他是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。

在引入了進(jìn)程實(shí)體的概念后，我們可以吧傳統(tǒng)的操作系統(tǒng)中的進(jìn)程定義為：“進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位”。

進(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)過程調(diào)用的指令和本地變量。第二，進(jìn)程是一個(gè)“執(zhí)行中的程序”。程序是一個(gè)沒有生命的實(shí)體，只有處理器賦予程序生命時(shí)（操作系統(tǒng)執(zhí)行之），它才能成為一個(gè)活動(dòng)的實(shí)體，我們稱其為進(jìn)程。

描述進(jìn)程—–PCB

進(jìn)程信息被放在一個(gè)叫做進(jìn)程控制塊的數(shù)據(jù)結(jié)構(gòu)中，可以理解為進(jìn)程屬性的集合。

課本上稱之為PCB（process control block），Linux操作系統(tǒng)下的PCB是: task_struct 。

在Linux中描述進(jìn)程的結(jié)構(gòu)體叫做task_struct。

task_struct是Linux內(nèi)核的一種數(shù)據(jù)結(jié)構(gòu)，它會(huì)被裝載到RAM(內(nèi)存)?里并且包含著進(jìn)程的信息。

task_ struct內(nèi)容分類

進(jìn)程的特征：

進(jìn)程是由多程序的并發(fā)執(zhí)行而引出的，他和程序是兩個(gè)截然不同的概念。進(jìn)程的基本特征是對比單個(gè)程序的順序執(zhí)行提出的，也是對進(jìn)程管理提出的基本要求。

1） 動(dòng)態(tài)性：進(jìn)程是程序的一次執(zhí)行，他有著創(chuàng)建、活動(dòng)、暫停、終止等過程，具有一定的生命周期，是動(dòng)態(tài)的產(chǎn)生、變化和消亡的。動(dòng)態(tài)性是進(jìn)程最基本的特征。

2） 并發(fā)性：至多個(gè)進(jìn)程實(shí)體，同存于內(nèi)存中，能在一段時(shí)間內(nèi)同時(shí)運(yùn)行，并發(fā)性是進(jìn)程的重要特征，同時(shí)也是操作系統(tǒng)的重要特征，引入進(jìn)程的目的就是為了是程序能與去其他進(jìn)程的程序并發(fā)執(zhí)行，以提高資源利用率。

3） 獨(dú)立性：指進(jìn)程實(shí)體是一個(gè)能獨(dú)立運(yùn)行、獨(dú)立獲得資源和獨(dú)立接收調(diào)度的基本單位。范圍建立PCB的程序都不能作為一個(gè)獨(dú)立的單位參與運(yùn)行。

4） 異步性：由于進(jìn)程的相互制約，是進(jìn)程具有執(zhí)行的間斷性。也即進(jìn)程按各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)。異步性會(huì)導(dǎo)致執(zhí)行結(jié)果不可再現(xiàn)性，為此，在操作系統(tǒng)中必須配置相應(yīng)的進(jìn)程同步機(jī)制。

5） 結(jié)構(gòu)性：每個(gè)進(jìn)程都配置一個(gè)PCB對其進(jìn)行描述。從結(jié)構(gòu)上來看，進(jìn)程實(shí)體是由程序段、數(shù)據(jù)段和進(jìn)程控制端三部分組成的。

PCB

PCB的組織

PCB表的組織方式主要有:線性方式、鏈接方式和索引方式。

· 線性方式是把所有進(jìn)程的PCB都放在一個(gè)表中。

·?鏈接方式按照進(jìn)程的不同狀態(tài)把它們分別放在不同的隊(duì)列中。

·?索引方式是利用索引表記載相應(yīng)狀態(tài)進(jìn)程的PCB地址。

2.?進(jìn)程的狀態(tài)與轉(zhuǎn)換

進(jìn)程在其生命周期內(nèi)，由于系統(tǒng)中個(gè)進(jìn)程之間的相互制約關(guān)系以及系統(tǒng)的運(yùn)行環(huán)境的變化，使的進(jìn)程的狀態(tài)也在不斷地發(fā)生著變化。通常進(jìn)程有以下五種狀態(tài)。前三種是進(jìn)程的基本狀態(tài)。

1） 運(yùn)行狀態(tài)：進(jìn)程正在處理器上運(yùn)行。在單處理器的環(huán)境下，每一時(shí)刻最多只有一個(gè)進(jìn)程處于運(yùn)行狀態(tài)。

2） 就緒狀態(tài)：進(jìn)程已處于準(zhǔn)備運(yùn)行的狀態(tài)，即進(jìn)程獲得了除CPU之外的一切所需資源，一旦得到處理器即可運(yùn)行。

3） 阻塞狀態(tài)：又稱為等待狀態(tài)：進(jìn)程正在等待某一事件而暫停運(yùn)行，如等待某資源為可用（不包括處理器），或等待輸入輸出的完成。即使處理器空閑，該進(jìn)程也不能運(yùn)行。

4） 創(chuàng)建狀態(tài)：進(jìn)程正在被創(chuàng)建，尚未轉(zhuǎn)到就緒狀態(tài)。創(chuàng)建進(jìn)程通常需要多個(gè)步驟：首先申請一個(gè)空白的PCB，并向PCB中填寫一些控制和管理進(jìn)程的信息；然后由系統(tǒng)為該進(jìn)程分配運(yùn)行時(shí)所必須的資源；最后把該進(jìn)程轉(zhuǎn)入到就緒狀態(tài)。

5） 結(jié)束狀態(tài)：進(jìn)程正在從系統(tǒng)中消失，這可能是進(jìn)程正常結(jié)束或其他原因中斷退出運(yùn)行。當(dāng)進(jìn)程需要結(jié)束運(yùn)行時(shí)，系統(tǒng)首先必須置該進(jìn)程為結(jié)束狀態(tài)，然后再進(jìn)一步處理資源釋放和回收工作。

注意區(qū)別就緒狀態(tài)和等待狀態(tài)：就緒狀態(tài)是指進(jìn)程僅缺少處理器，只要活得處理器資源就立即執(zhí)行；而等待狀態(tài)是指進(jìn)程需要其他資源或等待某一事件，及時(shí)處理器空閑也不能運(yùn)行。

3. 進(jìn)程控制

進(jìn)程的創(chuàng)建和終止

進(jìn)程控制的主要功能是對系統(tǒng)中所有進(jìn)程實(shí)施有效地管理，它具有創(chuàng)建新進(jìn)程、撤銷已有進(jìn)程、實(shí)現(xiàn)進(jìn)程狀態(tài)轉(zhuǎn)換等功能。在操作系統(tǒng)中，一般把進(jìn)程控制用的程序段稱為原語，原語的特點(diǎn)是執(zhí)行期間不允許中斷，它是一個(gè)不可分割的基本單位。

允許一個(gè)進(jìn)程創(chuàng)建另一個(gè)進(jìn)程。

操作系統(tǒng)創(chuàng)建一個(gè)新進(jìn)程的過程如下（創(chuàng)建原語）：

1） 為新進(jìn)程分配一個(gè)唯一進(jìn)程標(biāo)示號，并申請一個(gè)空白的PCB。

2） 為進(jìn)程分配資源，為新進(jìn)程的程序和數(shù)據(jù)，以及用戶占分配必要的空間。

3） 初始化PCB，主要包括初始化標(biāo)識信息、初始化處理器狀態(tài)信息和初始化處理器控制信息，以及設(shè)置進(jìn)程的優(yōu)先級。

4） 如果進(jìn)程就緒隊(duì)列能夠接納新進(jìn)程，就將新進(jìn)程插入到就緒隊(duì)列，等待被調(diào)度運(yùn)行。

引起進(jìn)程終止的時(shí)間主要有：正常結(jié)束、表示進(jìn)程的任務(wù)已經(jīng)完成和準(zhǔn)備退出運(yùn)行。異常結(jié)束是指進(jìn)程在運(yùn)行時(shí)，發(fā)生了某種異常事件，是程序無法繼續(xù)運(yùn)行，如：存儲(chǔ)區(qū)越界、保護(hù)錯(cuò)誤、非法指令、特權(quán)指令錯(cuò)誤、IO故障等。外界干預(yù)是指進(jìn)程外界的請求而終止，如操作員或操作系統(tǒng)干預(yù)、父進(jìn)程請求和父進(jìn)程終止。

操作系統(tǒng)終止進(jìn)程的過程如下：（撤消原語）

1） 根據(jù)被終止進(jìn)程的標(biāo)示符，檢索PCB，從中讀出該進(jìn)程的狀態(tài)。

2） 若被終止進(jìn)程處于執(zhí)行狀態(tài)，立即終止該進(jìn)程的執(zhí)行，將處理器資源分配給其他進(jìn)程。

3） 若該進(jìn)程還有子進(jìn)程，則應(yīng)將其所有子進(jìn)程終止。

4） 將該進(jìn)程所擁有的資源、或歸還給父進(jìn)程或歸還給操作系統(tǒng)。

5） 將該P(yáng)CB從所在隊(duì)列（鏈表）中刪除。

進(jìn)程的阻塞和喚醒：

正在執(zhí)行的進(jìn)程，猶豫期待的某些時(shí)間為發(fā)生，如請求系統(tǒng)資源失敗、等待某種操作的完成、新數(shù)據(jù)尚未到達(dá)或無新工作可做等，則由系統(tǒng)自動(dòng)執(zhí)行阻塞原語，使自己由運(yùn)行狀態(tài)變?yōu)樽枞麪顟B(tài)?？梢姡M(jìn)程的阻塞是進(jìn)程自身的一種主動(dòng)行為。

阻塞原語的執(zhí)行過程為：找到將要被阻塞進(jìn)程的標(biāo)識號對應(yīng)的PCB，如果該進(jìn)程為運(yùn)行狀態(tài)，則保護(hù)其現(xiàn)場，將其狀態(tài)改為阻塞狀態(tài)，停止運(yùn)行，并把該P(yáng)CB插入響應(yīng)時(shí)間的等待隊(duì)列中去；若為就緒狀態(tài)，則將其狀態(tài)改為阻塞狀態(tài)，把它溢出就緒隊(duì)列，插入到等待隊(duì)列中去。

當(dāng)阻塞進(jìn)程所期待的時(shí)間出現(xiàn)時(shí)，如它所啟動(dòng)的IO操作已完成或其所期待的數(shù)據(jù)已到達(dá)，則有關(guān)進(jìn)程（比如，提供數(shù)據(jù)的進(jìn)程），調(diào)用喚醒原語，將等待該事件的進(jìn)程喚醒，喚醒原語的執(zhí)行過程是：在該事件的等待隊(duì)列中找到相應(yīng)進(jìn)程的PCB，然后把該P(yáng)CB插入到就緒隊(duì)列中，等待調(diào)度程序調(diào)度。

需要注意的是，Block原語和Wakeup原語是一對作用剛好相反的原語，必須成對使用。Block原語是由被阻塞進(jìn)程自我調(diào)用實(shí)現(xiàn)的，而Wakeup原語則是由一個(gè)與被喚醒進(jìn)程相合作或被其他相關(guān)進(jìn)程調(diào)用實(shí)現(xiàn)的。

無論什么樣的進(jìn)程操作，都是在內(nèi)核執(zhí)行的。

進(jìn)程的切換

進(jìn)程切換是指當(dāng)前正在運(yùn)行的進(jìn)程被轉(zhuǎn)換到其他狀態(tài)后，再回到運(yùn)行繼續(xù)執(zhí)行的過程，這個(gè)過程中，進(jìn)程的運(yùn)行環(huán)境產(chǎn)生了實(shí)質(zhì)性的變化。進(jìn)程切換的過程如下：

1） 保存處理器上下文，包括程序計(jì)數(shù)器和其他寄存器。

2） 更新PCB信息。

3） 把進(jìn)程的PCB移入相應(yīng)的隊(duì)列，如就緒、在某時(shí)間阻塞等隊(duì)列。

4） 選擇另一個(gè)進(jìn)程執(zhí)行，并更新其PCB。更新內(nèi)存管理的數(shù)據(jù)結(jié)構(gòu)。

5） 恢復(fù)處理器的上下文。

4. 線程

引入進(jìn)程的目的，是為了是多道程序能并發(fā)執(zhí)行，以提高資源利用率和系統(tǒng)吞吐量；而引入線程，則是為了減小程序在并發(fā)執(zhí)行時(shí)所付出的時(shí)空開銷，提高操作系統(tǒng)的并發(fā)性能。

線程最直接的理解就是“輕量級進(jìn)程”，它是一個(gè)基本的CPU執(zhí)行單元，也是程序執(zhí)行流的最小單元，由線程ID、程序計(jì)數(shù)器、寄存器集合和堆棧組成。線程是進(jìn)程中的一個(gè)實(shí)體，是被系統(tǒng)獨(dú)立調(diào)度和分派的基本單位。進(jìn)程只作為除CPU以外的系統(tǒng)資源的分配單元，線程則作為處理器的分配單元。線程也有就緒、阻塞和運(yùn)行三種基本狀態(tài)。

線程的特點(diǎn)

線程和進(jìn)程的比較

1） 調(diào)度：在引入線程的操作系統(tǒng)中，線程是獨(dú)立調(diào)度的基本單位，進(jìn)程是資源擁有的基本單位。

2） 擁有資源：進(jìn)程是擁有資源的基本單位，而線程不擁有系統(tǒng)資源，單線程可以訪問其隸屬進(jìn)程的系統(tǒng)資源。

3） 并發(fā)性：在引入線程的操作系統(tǒng)中，不僅進(jìn)程之間可以并發(fā)執(zhí)行，線程之間也可以并發(fā)執(zhí)行，從而是操作系統(tǒng)具有更好的并發(fā)性，大大提高了系統(tǒng)的吞吐量。

4） 系統(tǒng)開銷：線程開銷極小。

5） 地址空間和其他資源：進(jìn)程的地址空間之間相互獨(dú)立，同一進(jìn)程的各線程間共享進(jìn)程的資源，進(jìn)程內(nèi)的線程對進(jìn)程外的其他進(jìn)程不可見。

6） 通信方面：進(jìn)程間通信需要進(jìn)程同步和互斥手段的輔助，以保證數(shù)據(jù)的一致性，而線程間可以直接讀寫進(jìn)程數(shù)據(jù)段來進(jìn)行通信。

線程的屬性

線程的主要屬性如下：

1） 線程是一個(gè)輕型實(shí)體，它不擁有系統(tǒng)資源，但每個(gè)線程都應(yīng)有一個(gè)唯一的標(biāo)識符和一個(gè)線程控制塊，線程控制塊記錄了線程執(zhí)行的寄存器和棧等現(xiàn)場情況。

2） 不同的線程可以執(zhí)行相同的程序，即同一個(gè)服務(wù)程序被不同的用戶調(diào)用時(shí)，操作系統(tǒng)為他們創(chuàng)建不同的線程。

3） 統(tǒng)一進(jìn)程中的各個(gè)線程共享該進(jìn)程所擁有的系統(tǒng)資源。

4） 線程是處理器的獨(dú)立調(diào)度單位，多個(gè)線程是可以并發(fā)執(zhí)行的。

5） 一個(gè)線程被創(chuàng)建后便開始了它的生命周期，直至終止，線程在生命周期內(nèi)會(huì)經(jīng)歷等待態(tài)、就緒態(tài)和運(yùn)行態(tài)等各種狀態(tài)變化。

線程的實(shí)現(xiàn)可以分為兩類：用戶級線程和內(nèi)核級線程。

（操作系統(tǒng)對）線程的實(shí)現(xiàn)

多線程模型

有些系統(tǒng)同時(shí)支持用戶線程和內(nèi)核線程，由此產(chǎn)生了不同的多線程模型，即實(shí)現(xiàn)用戶級線程和內(nèi)核級線程的連接方式。

1） 多對一模型。多對一模型將多個(gè)用戶級線程映射到一個(gè)內(nèi)核級線程。線程管理在用戶空間完成。

2） 一對一模型。

3） 多對多模型。

特點(diǎn)：克服了多對一模型的并發(fā)度不高的缺點(diǎn)，又克服了一對一模型中一個(gè)用戶進(jìn)程占用太多內(nèi)核級線程，開銷太大的缺點(diǎn)。

線程的狀態(tài)與轉(zhuǎn)換

二、進(jìn)程調(diào)度和線程調(diào)度

1.調(diào)度的概念、層次

調(diào)度的概念

在多道程序系統(tǒng)中，進(jìn)程的數(shù)量往往多于處理器的個(gè)數(shù)，進(jìn)程爭用處理器的情況在所難免。處理器調(diào)度是對處理器進(jìn)行分配，就是從就緒隊(duì)列中，按照一定的算法，選擇一個(gè)進(jìn)程并將處理器分配給他運(yùn)行，以實(shí)現(xiàn)進(jìn)程的并發(fā)執(zhí)行。

處理器調(diào)度是多道程序操作系統(tǒng)的基礎(chǔ)，它是操作系統(tǒng)設(shè)計(jì)的核心問題。

一個(gè)作業(yè)從提交開始直到完成，往往要經(jīng)歷以下三級調(diào)度：

1）作業(yè)調(diào)度。作業(yè)調(diào)度又稱高級調(diào)度：其主要任務(wù)是按一定的原則從外存上處于后備狀態(tài)的作業(yè)中挑選一個(gè)或多個(gè)作業(yè)，給他們分配內(nèi)存、輸入輸出設(shè)備等必要的資源。并建立相應(yīng)的進(jìn)程，以使他們獲得競爭處理器的權(quán)利。

多道批處理系統(tǒng)中大多配有作業(yè)調(diào)度，而其它系統(tǒng)中通常不需要配置作業(yè)調(diào)度。作業(yè)調(diào)度的執(zhí)行頻率較低，通常為幾分鐘一次。

2）中級調(diào)度。中級調(diào)度又稱內(nèi)存調(diào)度。引入中級調(diào)度視為了提高內(nèi)存利用率和系統(tǒng)吞吐率，為此，應(yīng)使那些暫時(shí)不能運(yùn)行的進(jìn)程調(diào)至外存等待，把此時(shí)的進(jìn)程狀態(tài)稱為掛起狀態(tài)。當(dāng)他們已具備運(yùn)行條件且內(nèi)存有稍有空閑時(shí)，由中級調(diào)度來決定，吧外存上那些已具備運(yùn)行條件的就緒進(jìn)程，在重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上等待。

3）進(jìn)程調(diào)度。進(jìn)程調(diào)度又稱為低級調(diào)度，其主要任務(wù)是按照某種方法和策略從就緒隊(duì)列中選取一個(gè)進(jìn)程，將處理器分配給它。進(jìn)程調(diào)度是操作系統(tǒng)中最基本的一中調(diào)度，在一般操作系統(tǒng)中都不需配置進(jìn)程調(diào)度。進(jìn)程調(diào)度的頻率很高，一般幾十毫秒一次。

作業(yè)調(diào)度從外存的后備隊(duì)列中選擇一批作業(yè)進(jìn)入內(nèi)存，為他們建立進(jìn)程。這些進(jìn)程被送入就緒隊(duì)列。進(jìn)程調(diào)度從就緒隊(duì)列中選出一個(gè)進(jìn)程，并把其狀態(tài)改為運(yùn)行狀態(tài)，把CPU分配給它。中級調(diào)度是位于高級調(diào)度和低級調(diào)度之間的一種調(diào)度。為了提高內(nèi)存的利用率，系統(tǒng)將那些暫時(shí)不能運(yùn)行的進(jìn)程掛起來。當(dāng)內(nèi)存空間寬松時(shí)，通過中級調(diào)度選擇具備運(yùn)行條件的進(jìn)程，將其喚醒。

調(diào)度的層次

作業(yè)調(diào)度

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

實(shí)時(shí)調(diào)度

多處理機(jī)調(diào)度

2.調(diào)度的時(shí)機(jī)、切換與過程、 方式

調(diào)度的時(shí)機(jī)、切換與過程

進(jìn)程調(diào)度和切換程序是操作系統(tǒng)內(nèi)核程序。當(dāng)請求調(diào)度的事件發(fā)生后，才可能會(huì)運(yùn)行進(jìn)程調(diào)度程序，當(dāng)調(diào)度了新的就緒進(jìn)程后，才會(huì)去進(jìn)行進(jìn)程間的切換。

現(xiàn)在操作系統(tǒng)中，不能進(jìn)行進(jìn)程的調(diào)度與切換的情況有以下幾種：

1） 在處理中斷的過程中：中斷處理過程復(fù)雜，在實(shí)現(xiàn)上很難做到，而且中斷處理時(shí)系統(tǒng)工作的一部分，邏輯上不屬于某一進(jìn)程，不應(yīng)被剝奪處理器資源。

2） 進(jìn)程在操作系統(tǒng)內(nèi)核程序臨界區(qū)中：進(jìn)入臨界區(qū)后，需要獨(dú)占式的訪問共享數(shù)據(jù)，理論上必須加鎖，以防止其他并行程序的進(jìn)入，在解鎖前不應(yīng)該切換到其他進(jìn)程，以加快該共享數(shù)據(jù)的釋放。

3） 其他需要完全屏蔽中斷的原子操作過程中：如加鎖、解鎖、中斷現(xiàn)場保護(hù)、恢復(fù)等等源自操作。在原子過程中，連中斷都要屏蔽，更不應(yīng)該進(jìn)行進(jìn)程的切換。

如果在上述過程中發(fā)生了引起調(diào)度的條件，并不能馬上進(jìn)行調(diào)度和切換，應(yīng)置系統(tǒng)請求調(diào)度標(biāo)志，知道上述過程結(jié)束后才能進(jìn)行相應(yīng)的調(diào)度和切換。

應(yīng)該進(jìn)行進(jìn)程的調(diào)度與切換的情況有：

1） 當(dāng)發(fā)生引起調(diào)度條件且當(dāng)前進(jìn)程無法繼續(xù)運(yùn)行下去時(shí)，可以馬上進(jìn)行調(diào)度與切換。如果操作系統(tǒng)只在這種情況下進(jìn)行進(jìn)程調(diào)度，就是非剝奪調(diào)度。

2） 當(dāng)中斷處理結(jié)束后或自陷處理結(jié)束后，返回被中斷進(jìn)程的用戶態(tài)程序執(zhí)行現(xiàn)場前，若置上請求調(diào)度標(biāo)志，即可馬上進(jìn)行進(jìn)程調(diào)度與切換。如果操作系統(tǒng)支持這種情況下的運(yùn)行調(diào)度程序，就實(shí)現(xiàn)了剝奪方式的調(diào)度。

進(jìn)程切換往往在調(diào)度完成后立刻發(fā)生，它要求保存源進(jìn)程當(dāng)前切換點(diǎn)的進(jìn)程信息，恢復(fù)被調(diào)度進(jìn)程的現(xiàn)場信息。現(xiàn)場切換時(shí)，操作系統(tǒng)內(nèi)核將源近程的現(xiàn)場信息推入到當(dāng)前進(jìn)程的內(nèi)核堆棧來保存它們，并更新堆棧指針。內(nèi)核完成從新進(jìn)程的內(nèi)核棧中裝入新進(jìn)程的線程信息、更新當(dāng)前運(yùn)行進(jìn)程空間指針、重設(shè)PC寄存器等相關(guān)工作之后，開始運(yùn)行新的進(jìn)程。

調(diào)度的方式

所謂進(jìn)程調(diào)度方式是指當(dāng)某一個(gè)進(jìn)程正在處理器上執(zhí)行時(shí)，若有某個(gè)更為重要或緊迫的進(jìn)程需要處理，既有優(yōu)先權(quán)更高的進(jìn)程進(jìn)入就緒隊(duì)列，此時(shí)應(yīng)如何分配處理器。通常有一下兩種進(jìn)程調(diào)度方式：

（1） 非剝奪調(diào)度方式

非剝奪調(diào)度方式又稱為非搶占調(diào)度方式，是指當(dāng)一個(gè)進(jìn)程正在處理器上執(zhí)行時(shí)，即使有某個(gè)更為重要或緊迫的進(jìn)程進(jìn)入就緒狀態(tài)，仍然讓正在執(zhí)行的進(jìn)程繼續(xù)執(zhí)行，知道該進(jìn)程完成或發(fā)生某種時(shí)間而進(jìn)入阻塞狀態(tài)時(shí)，才把處理器分配給更為重要或緊迫的進(jìn)程。

（2） 剝奪調(diào)度方式

剝奪調(diào)度方式又稱為搶占方式，是指當(dāng)一個(gè)進(jìn)程正在處理器上執(zhí)行時(shí)，若有某個(gè)更為重要或緊迫的進(jìn)程需要使用處理器，則立即暫停正在執(zhí)行的進(jìn)程，將處理器分配給這個(gè)更為重要或緊迫的進(jìn)程。

“剝奪”不是一種任意性行為，必須遵循一定的原則：優(yōu)先權(quán)原則，短進(jìn)程優(yōu)先原則和時(shí)間片原則。

3.調(diào)度器（調(diào)度程序scheduler）和閑逛進(jìn)程

4.調(diào)度算法的評價(jià)指標(biāo)（準(zhǔn)則）

不同的調(diào)度算法具有不同的特性，在選擇調(diào)度算法時(shí)，必須考慮算法所具有的特性。為了比較處理器調(diào)度算法的性能，人們提出很多評價(jià)準(zhǔn)則，下面介紹主要的幾種準(zhǔn)則：

（1） CPU利用率

CPU是計(jì)算機(jī)系統(tǒng)中最重要的資源之一，所以應(yīng)盡可能使CPU保持在忙狀態(tài)，是這一資源利用率最高。

（2） 系統(tǒng)吞吐量

系統(tǒng)吞吐量表示單位時(shí)間內(nèi)CPU完成作業(yè)的數(shù)量。長作業(yè)需要消耗較長的處理器時(shí)間，因此會(huì)降低系統(tǒng)的吞吐量。而對于短作業(yè)，他們所需要消耗的處理器時(shí)間端，因此能提高系統(tǒng)的吞吐量。調(diào)度算法和方式的不同，也會(huì)對系統(tǒng)的吞吐量產(chǎn)生較大的影響。

（3） 周轉(zhuǎn)時(shí)間

周轉(zhuǎn)時(shí)間是指從作業(yè)提交到作業(yè)完成所經(jīng)歷的時(shí)間，包括作業(yè)等待、在就緒隊(duì)列中排隊(duì)、在處理器上運(yùn)行以及進(jìn)行輸入輸出操作所花費(fèi)的時(shí)間的總和。

作業(yè)的周轉(zhuǎn)時(shí)間=作業(yè)完成時(shí)間-作業(yè)提交時(shí)間

（4） 等待時(shí)間

等待時(shí)間是指進(jìn)程處于等處理器狀態(tài)時(shí)間之和，等待時(shí)間越長，用戶滿意度越低。處理器調(diào)度算法實(shí)際上并不影響作業(yè)執(zhí)行或輸入輸出操作時(shí)間，只影響作業(yè)在就緒隊(duì)列中等待所花的時(shí)間。因此，衡量一個(gè)調(diào)度算法優(yōu)劣常常只需簡單地考察等待時(shí)間。

（5） 響應(yīng)時(shí)間

響應(yīng)時(shí)間是指從用戶提交請求到系統(tǒng)首次產(chǎn)生響應(yīng)所有的時(shí)間。在交互式系統(tǒng)中，周轉(zhuǎn)時(shí)間不可能是最好的評測準(zhǔn)則，一般采用響應(yīng)時(shí)間作為衡量調(diào)度算法的重要準(zhǔn)則之一。從用戶的角度來看，調(diào)度策略應(yīng)盡量降低響應(yīng)時(shí)間，使響應(yīng)時(shí)間處在用戶能夠接受的范圍之內(nèi)。

5.調(diào)度算法

處理調(diào)度（CPU調(diào)度）

定義：其任務(wù)是控制、協(xié)調(diào)作業(yè)進(jìn)程對CPU的競爭，即按一定的調(diào)度算法，從輸入井（就緒隊(duì)列）中選擇一個(gè)作業(yè)（進(jìn)程），把CPU的使用權(quán)交給被選中的作業(yè)（進(jìn)程）

通常系統(tǒng)的設(shè)計(jì)目標(biāo)不同，所采用的調(diào)度算法也不同。在操作系統(tǒng)中存在多種調(diào)度算法，其中有的調(diào)度算法適用于作業(yè)調(diào)度，有的調(diào)度算法適用于進(jìn)程調(diào)度，有的調(diào)度算法兩者都適用。下面介紹幾種常用的調(diào)度算法：

（1） FIFS先來先服務(wù)調(diào)度算法

特點(diǎn)：算法簡單，但是效率低；有利于長作業(yè)，不利于短作業(yè)；有利于CPU繁忙型作業(yè)而不利于IO繁忙型作業(yè)。

（2） SJF短作業(yè)優(yōu)先調(diào)度算法

短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法是指對短作業(yè)和短進(jìn)程優(yōu)先調(diào)度的算法。短作業(yè)優(yōu)先調(diào)度算法是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)算時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。

SJF調(diào)度算法的缺點(diǎn)：

1） 該算法對長作業(yè)不理。

2） 該算法完全未考慮作業(yè)的緊迫程度。

3） 由于作業(yè)的長短只根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶又可能會(huì)有意或無意的縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間，致使該算法不一定能真正做到算作業(yè)優(yōu)先調(diào)度。

4） 注意：SJF調(diào)度算法的平均等待時(shí)間、平均周轉(zhuǎn)時(shí)間最少。

（3） 高響應(yīng)比優(yōu)先調(diào)度算法

高響應(yīng)比優(yōu)先調(diào)度算法主要用于作業(yè)調(diào)度。同時(shí)考慮從每個(gè)作業(yè)的等待時(shí)間和估計(jì)需要運(yùn)行的時(shí)間。

（4） 時(shí)間片輪轉(zhuǎn)調(diào)度算法

時(shí)間片輪轉(zhuǎn)調(diào)度算法主要適用于分時(shí)系統(tǒng)。

（5）?優(yōu)先級調(diào)度算法

（6）?多級反饋隊(duì)列調(diào)度算法

多級反饋隊(duì)列調(diào)度算法主要是時(shí)間片輪轉(zhuǎn)調(diào)度算法和優(yōu)先級調(diào)度算法的綜合和發(fā)展。通過動(dòng)態(tài)調(diào)整進(jìn)程優(yōu)先級和時(shí)間片大小，多級反饋隊(duì)列調(diào)度算法可以兼顧多方面的系統(tǒng)目標(biāo)。

三、進(jìn)程間通信（IPC, Inter-Process Communication）

進(jìn)程通信就是進(jìn)程之間的數(shù)據(jù)交換。PV操作是低級通信方式，高級通信方式是指以較高的效率傳輸大量數(shù)據(jù)的通信方式。高級通信方法可分為共享存儲(chǔ)、消息傳遞和管道通信三大通信方式。

消息緩沖

（1）?共享存儲(chǔ)

在通信的進(jìn)程之間存在著一塊可以直接訪問的共享空間，通過對這塊共享空間的讀寫操作時(shí)間進(jìn)程之間的信息交換。在共享存儲(chǔ)方法中，需要使用同步互斥工具。

需要注意的是：用戶進(jìn)程空間一般都是相互獨(dú)立的，要想讓兩個(gè)用戶進(jìn)程共享空間，必須通過特殊系統(tǒng)調(diào)用實(shí)現(xiàn)，而進(jìn)程內(nèi)的線程是自然共享進(jìn)程空間的。

（2） 消息傳遞

（3） 管道通信

管道通信是消息傳遞的一種特殊方式。所謂管道，就是用于連接一個(gè)讀進(jìn)程和一個(gè)寫進(jìn)程以實(shí)現(xiàn)他們之間通信的一個(gè)共享文件，又名為pipe文件。向管道或共享文件提供輸入的發(fā)送進(jìn)程，以字符流的形式將大量的數(shù)據(jù)送入寫管道；而接收管道輸出的接收進(jìn)程，則從管道中接受數(shù)據(jù)。為了協(xié)調(diào)雙方的通信，管道機(jī)制必須它提供以下三方面的協(xié)調(diào)能力：互斥、同步和確定對方存在。

*快速面經(jīng)

一、進(jìn)程和線程的區(qū)別？

Ⅰ 擁有資源

進(jìn)程是資源分配的基本單位，但是線程不擁有資源，線程可以訪問隸屬進(jìn)程的資源。

Ⅱ 調(diào)度

線程是獨(dú)立調(diào)度的基本單位，在同一進(jìn)程中，線程的切換不會(huì)引起進(jìn)程切換，從一個(gè)進(jìn)程中的線程切換到另一個(gè)進(jìn)程中的線程時(shí)，會(huì)引起進(jìn)程切換。

Ⅲ 系統(tǒng)開銷

由于創(chuàng)建或撤銷進(jìn)程時(shí)，系統(tǒng)都要為之分配或回收資源，如內(nèi)存空間、I/O 設(shè)備等，所付出的開銷遠(yuǎn)大于創(chuàng)建或撤銷線程時(shí)的開銷。類似地，在進(jìn)行進(jìn)程切換時(shí)，涉及當(dāng)前執(zhí)行進(jìn)程 CPU 環(huán)境的保存及新調(diào)度進(jìn)程 CPU 環(huán)境的設(shè)置，而線程切換時(shí)只需保存和設(shè)置少量寄存器內(nèi)容，開銷很小。

Ⅳ 通信方面

線程間可以通過直接讀寫同一進(jìn)程中的數(shù)據(jù)進(jìn)行通信，但是進(jìn)程通信需要借助 IPC。

二、進(jìn)程狀態(tài)的切換

• 就緒狀態(tài)（ready）：等待被調(diào)度

• 運(yùn)行狀態(tài)（running）

• 阻塞狀態(tài)（waiting）：等待資源

  只有就緒態(tài)和運(yùn)行態(tài)可以相互轉(zhuǎn)換，其它的都是單向轉(zhuǎn)換。就緒狀態(tài)的進(jìn)程通過調(diào)度算法從而獲得 CPU 時(shí)間，轉(zhuǎn)為運(yùn)行狀態(tài)；而運(yùn)行狀態(tài)的進(jìn)程，在分配給它的 CPU 時(shí)間片用完之后就會(huì)轉(zhuǎn)為就緒狀態(tài)，等待下一次調(diào)度。

  阻塞狀態(tài)是缺少需要的資源從而由運(yùn)行狀態(tài)轉(zhuǎn)換而來，但是該資源不包括 CPU 時(shí)間，缺少 CPU 時(shí)間會(huì)從運(yùn)行態(tài)轉(zhuǎn)換為就緒態(tài)。

三、進(jìn)程調(diào)度算法

不同環(huán)境的調(diào)度算法目標(biāo)不同

1. 批處理系統(tǒng)

批處理系統(tǒng)沒有太多的用戶操作，在該系統(tǒng)中，調(diào)度算法目標(biāo)是保證吞吐量和周轉(zhuǎn)時(shí)間（從提交到終止的時(shí)間）。

1.1 先來先服務(wù) first-come first-serverd（FCFS）

非搶占式的調(diào)度算法，按照請求的順序進(jìn)行調(diào)度。

有利于長作業(yè)，但不利于短作業(yè)，因?yàn)槎套鳂I(yè)必須一直等待前面的長作業(yè)執(zhí)行完畢才能執(zhí)行，而長作業(yè)又需要執(zhí)行很長時(shí)間，造成了短作業(yè)等待時(shí)間過長。

1.2 短作業(yè)優(yōu)先 shortest job first（SJF）

非搶占式的調(diào)度算法，按估計(jì)運(yùn)行時(shí)間最短的順序進(jìn)行調(diào)度。

長作業(yè)有可能會(huì)餓死，處于一直等待短作業(yè)執(zhí)行完畢的狀態(tài)。因?yàn)槿绻恢庇卸套鳂I(yè)到來，那么長作業(yè)永遠(yuǎn)得不到調(diào)度。

1.3 最短剩余時(shí)間優(yōu)先 shortest remaining time next（SRTN）

最短作業(yè)優(yōu)先的搶占式版本，按剩余運(yùn)行時(shí)間的順序進(jìn)行調(diào)度。 當(dāng)一個(gè)新的作業(yè)到達(dá)時(shí)，其整個(gè)運(yùn)行時(shí)間與當(dāng)前進(jìn)程的剩余時(shí)間作比較。如果新的進(jìn)程需要的時(shí)間更少，則掛起當(dāng)前進(jìn)程，運(yùn)行新的進(jìn)程。否則新的進(jìn)程等待。

2. 交互式系統(tǒng)

交互式系統(tǒng)有大量的用戶交互操作，在該系統(tǒng)中調(diào)度算法的目標(biāo)是快速地進(jìn)行響應(yīng)。

2.1 時(shí)間片輪轉(zhuǎn)

將所有就緒進(jìn)程按 FCFS 的原則排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把 CPU 時(shí)間分配給隊(duì)首進(jìn)程，該進(jìn)程可以執(zhí)行一個(gè)時(shí)間片。當(dāng)時(shí)間片用完時(shí)，由計(jì)時(shí)器發(fā)出時(shí)鐘中斷，調(diào)度程序便停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾，同時(shí)繼續(xù)把 CPU 時(shí)間分配給隊(duì)首的進(jìn)程。

時(shí)間片輪轉(zhuǎn)算法的效率和時(shí)間片的大小有很大關(guān)系：

• 因?yàn)檫M(jìn)程切換都要保存進(jìn)程的信息并且載入新進(jìn)程的信息，如果時(shí)間片太小，會(huì)導(dǎo)致進(jìn)程切換得太頻繁，在進(jìn)程切換上就會(huì)花過多時(shí)間。

• 而如果時(shí)間片過長，那么實(shí)時(shí)性就不能得到保證。

2.2 優(yōu)先級調(diào)度

為每個(gè)進(jìn)程分配一個(gè)優(yōu)先級，按優(yōu)先級進(jìn)行調(diào)度。

為了防止低優(yōu)先級的進(jìn)程永遠(yuǎn)等不到調(diào)度，可以隨著時(shí)間的推移增加等待進(jìn)程的優(yōu)先級。

2.3 多級反饋隊(duì)列

一個(gè)進(jìn)程需要執(zhí)行 100 個(gè)時(shí)間片，如果采用時(shí)間片輪轉(zhuǎn)調(diào)度算法，那么需要交換 100 次。

多級隊(duì)列是為這種需要連續(xù)執(zhí)行多個(gè)時(shí)間片的進(jìn)程考慮，它設(shè)置了多個(gè)隊(duì)列，每個(gè)隊(duì)列時(shí)間片大小都不同，例如 1,2,4,8,..。進(jìn)程在第一個(gè)隊(duì)列沒執(zhí)行完，就會(huì)被移到下一個(gè)隊(duì)列。這種方式下，之前的進(jìn)程只需要交換 7 次。

每個(gè)隊(duì)列優(yōu)先權(quán)也不同，最上面的優(yōu)先權(quán)最高。因此只有上一個(gè)隊(duì)列沒有進(jìn)程在排隊(duì)，才能調(diào)度當(dāng)前隊(duì)列上的進(jìn)程。

可以將這種調(diào)度算法看成是時(shí)間片輪轉(zhuǎn)調(diào)度算法和優(yōu)先級調(diào)度算法的結(jié)合。

3. 實(shí)時(shí)系統(tǒng)

實(shí)時(shí)系統(tǒng)要求一個(gè)請求在一個(gè)確定時(shí)間內(nèi)得到響應(yīng)。

分為硬實(shí)時(shí)和軟實(shí)時(shí)，前者必須滿足絕對的截止時(shí)間，后者可以容忍一定的超時(shí)。

四、進(jìn)程間通信

進(jìn)程同步與進(jìn)程通信很容易混淆，它們的區(qū)別在于：

• 進(jìn)程同步：控制多個(gè)進(jìn)程按一定順序執(zhí)行；

• 進(jìn)程通信：進(jìn)程間傳輸信息。

進(jìn)程通信是一種手段，而進(jìn)程同步是一種目的。也可以說，為了能夠達(dá)到進(jìn)程同步的目的，需要讓進(jìn)程進(jìn)行通信，傳輸一些進(jìn)程同步所需要的信息

管道：管道是通過調(diào)用 pipe 函數(shù)創(chuàng)建的，fd[0] 用于讀，fd[1] 用于寫。

它具有以下限制：

• 只支持半雙工通信（單向交替?zhèn)鬏敚?/p>

• 只能在父子進(jìn)程或者兄弟進(jìn)程中使用。

FIFO：也稱為命名管道，去除了管道只能在父子進(jìn)程中使用的限制。FIFO 常用于客戶-服務(wù)器應(yīng)用程序中，F(xiàn)IFO 用作匯聚點(diǎn)，在客戶進(jìn)程和服務(wù)器進(jìn)程之間傳遞數(shù)據(jù)。

消息隊(duì)列：相比于 FIFO，消息隊(duì)列具有以下優(yōu)點(diǎn)：

• 消息隊(duì)列可以獨(dú)立于讀寫進(jìn)程存在，從而避免了 FIFO 中同步管道的打開和關(guān)閉時(shí)可能產(chǎn)生的困難；

• 避免了 FIFO 的同步阻塞問題，不需要進(jìn)程自己提供同步方法；

• 讀進(jìn)程可以根據(jù)消息類型有選擇地接收消息，而不像 FIFO 那樣只能默認(rèn)地接收

信號量：它是一個(gè)計(jì)數(shù)器，用于為多個(gè)進(jìn)程提供對共享數(shù)據(jù)對象的訪問

共享存儲(chǔ)：允許多個(gè)進(jìn)程共享一個(gè)給定的存儲(chǔ)區(qū)。因?yàn)閿?shù)據(jù)不需要在進(jìn)程之間復(fù)制，所以這是最快的一種 IPC。

需要使用信號量用來同步對共享存儲(chǔ)的訪問。

多個(gè)進(jìn)程可以將同一個(gè)文件映射到它們的地址空間從而實(shí)現(xiàn)共享內(nèi)存。另外 XSI 共享內(nèi)存不是使用文件，而是使用內(nèi)存的匿名段。

套接字：與其它通信機(jī)制不同的是，它可用于不同機(jī)器間的進(jìn)程通信。

優(yōu)缺點(diǎn)：

• 管道：速度慢，容量有限；

• Socket：任何進(jìn)程間都能通訊，但速度慢；

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

• 信號量：不能傳遞復(fù)雜消息，只能用來同步；

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