第八章進(jìn)程調(diào)度和時(shí)間8.1進(jìn)程調(diào)度在分時(shí)系統(tǒng)中，內(nèi)核給每個(gè)進(jìn)程分配一段CPU時(shí)間，這個(gè)時(shí)間稱為時(shí)間片。一個(gè)進(jìn)程的時(shí)間片用完時(shí)，內(nèi)核搶先該進(jìn)程并調(diào)度另一個(gè)進(jìn)程。每個(gè)進(jìn)程都有一個(gè)調(diào)度優(yōu)先權(quán)。在用戶態(tài)的進(jìn)程的優(yōu)先權(quán)是它最近使用CPU時(shí)間的函數(shù)，最近使用過較多的CPU時(shí)間的進(jìn)程得到較低的優(yōu)先權(quán)。當(dāng)內(nèi)核做上下文切換時(shí)，它選取有最高優(yōu)先權(quán)的進(jìn)程，切換到該進(jìn)程的上下文。當(dāng)進(jìn)程從核心態(tài)切換到用戶態(tài)時(shí)，內(nèi)核重新計(jì)算它的優(yōu)先權(quán)，并定期調(diào)整在用戶態(tài)“就緒”的每個(gè)進(jìn)程的優(yōu)先權(quán)。系統(tǒng)通過一個(gè)硬件時(shí)鐘計(jì)時(shí)。此硬件時(shí)鐘以一個(gè)固定的，依賴于硬件的頻率中斷CPU，此頻率一般在每秒鐘50到100次之間。每次時(shí)鐘中斷稱為時(shí)鐘滴答。unix系統(tǒng)上的調(diào)度程序叫做多級反饋循環(huán)調(diào)度。內(nèi)核給進(jìn)程分一個(gè)CPU時(shí)間片，內(nèi)核在剝奪一個(gè)時(shí)間片超時(shí)的進(jìn)程時(shí)，把它反饋到若干優(yōu)先級隊(duì)列中的某一隊(duì)列。一個(gè)進(jìn)程在它結(jié)束之前，可能要多次通過反饋循環(huán)。8.1.1算法

上下文切換結(jié)束時(shí)，內(nèi)核執(zhí)行此算法來調(diào)度一個(gè)進(jìn)程，從處于“在內(nèi)存中就緒”和“被搶先”狀態(tài)的進(jìn)程中選取優(yōu)先權(quán)最高的進(jìn)程。選取一個(gè)尚未裝入內(nèi)存的進(jìn)程是沒有意義的，因?yàn)樵撨M(jìn)程不能運(yùn)行。

如果若干進(jìn)程都具有最高優(yōu)先權(quán)，內(nèi)核按循環(huán)調(diào)度策略選擇在“就緒”狀態(tài)時(shí)間最長的進(jìn)程。若無合格的進(jìn)程，內(nèi)核則休閑，直到下次中斷，下次中斷最遲發(fā)生在下一個(gè)時(shí)鐘滴答時(shí)（時(shí)鐘中斷）。

處理完中斷后，內(nèi)核再次調(diào)度一個(gè)進(jìn)程去運(yùn)行。8.1.2調(diào)度參數(shù)進(jìn)程優(yōu)先權(quán)分為：用戶優(yōu)先權(quán)和核心優(yōu)先權(quán)。每種優(yōu)先權(quán)有若干優(yōu)先權(quán)值（優(yōu)先數(shù)），每個(gè)優(yōu)先權(quán)有一個(gè)邏輯上與它相關(guān)聯(lián)的進(jìn)程隊(duì)列。具有用戶級優(yōu)先權(quán)的進(jìn)程在它們從核心態(tài)返回到用戶態(tài)時(shí)被搶先，而得到它們的用戶級優(yōu)先權(quán)。具有核心級優(yōu)先權(quán)的進(jìn)程是在算法sleep中得到核心級優(yōu)先權(quán)的。

用戶級優(yōu)先權(quán)低于一個(gè)閾值，核心級優(yōu)先權(quán)高于該閾值。收到軟中斷信號時(shí)，具有低核心優(yōu)先權(quán)的進(jìn)程被喚醒；具有高核心優(yōu)先權(quán)的進(jìn)程繼續(xù)睡眠。

內(nèi)核在特定的進(jìn)程狀態(tài)下計(jì)算一個(gè)進(jìn)程的優(yōu)先權(quán)：1.內(nèi)核將優(yōu)先權(quán)賦給一個(gè)即將進(jìn)入睡眠的進(jìn)程。

在低層算法中睡眠的進(jìn)程的不活動的時(shí)間越長，就越容易引起系統(tǒng)瓶頸問題，因此，它們比可能引起較少系統(tǒng)瓶頸的進(jìn)程得到較高的優(yōu)先權(quán)。例：一個(gè)睡眠等待磁盤I/O的進(jìn)程比等待一個(gè)自由緩沖區(qū)的進(jìn)程具有較高優(yōu)先權(quán)。這是因?yàn)榈却疟PI/O的進(jìn)程已經(jīng)有了緩沖區(qū)，當(dāng)它醒來時(shí)就有機(jī)會做足夠的處理，從而釋放該緩沖區(qū)以及可能的其他資源。它釋放的資源越多，其他進(jìn)程的運(yùn)氣就會越好，不用擠在那里等待資源。

其次，一個(gè)等待自由緩沖區(qū)的進(jìn)程，可能正在等待由一個(gè)等待I/O完成的進(jìn)程所占用的緩沖區(qū)。2.內(nèi)核調(diào)整從核心態(tài)返回到用戶態(tài)的進(jìn)程的優(yōu)先權(quán)。3.時(shí)鐘處理程序以1秒鐘的間隔調(diào)整用戶態(tài)下的所有進(jìn)程的優(yōu)先權(quán)，并使內(nèi)核運(yùn)行調(diào)度算法防止某個(gè)進(jìn)程壟斷CPU的使用。

在一個(gè)進(jìn)程的時(shí)間片中，時(shí)鐘可能使它中斷若干次，每次時(shí)鐘中斷時(shí)，時(shí)鐘處理程序都要使該進(jìn)程表中的一個(gè)字段增值。該字段記錄了該進(jìn)程的最近CPU使用時(shí)間。時(shí)鐘處理程序每秒一次地根據(jù)一個(gè)衰減函數(shù)來調(diào)整每個(gè)進(jìn)程的最近CPU使用時(shí)間：

decay(CPU)=CPU/2當(dāng)時(shí)鐘處理程序重新計(jì)算最近CPU使用時(shí)間時(shí)會重新計(jì)算在“被搶先”和“就緒”狀態(tài)下的每個(gè)進(jìn)程的優(yōu)先權(quán)。

priority=(“recentCPUusage”/2)+(baseleveluserpriority)

優(yōu)先權(quán)值最近CPU使用時(shí)間基級用戶優(yōu)先權(quán)值優(yōu)先級數(shù)越低，優(yōu)先權(quán)越高。

內(nèi)核試圖每秒一次計(jì)算所有活動進(jìn)程的優(yōu)先權(quán)，這個(gè)時(shí)間間隔可以稍有變化：當(dāng)內(nèi)核正在執(zhí)行一段臨界區(qū)代碼時(shí)，如果時(shí)鐘中斷已經(jīng)到來，內(nèi)核并不重新計(jì)算優(yōu)先權(quán)，因?yàn)槟菚箖?nèi)核在臨界區(qū)呆的時(shí)間過長。每個(gè)進(jìn)程中訪問臨界資源的那段代碼稱為臨界區(qū)（臨界資源是一次僅允許一個(gè)進(jìn)程使用的共享資源）。8.1.3進(jìn)程調(diào)度的例子初始優(yōu)先數(shù)是60，時(shí)鐘每秒中斷系統(tǒng)60次CPU使用時(shí)間衰減值：

CPU=decay(CPU)=CPU/2進(jìn)程的優(yōu)先數(shù)：

priority=（CPU/2）+60

內(nèi)核可能會先于進(jìn)程B而調(diào)度進(jìn)程A，因?yàn)檫M(jìn)程A在“就緒”狀態(tài)的時(shí)間較長。這是對具有相同優(yōu)先權(quán)的進(jìn)程進(jìn)行調(diào)度的原則。8.1.4進(jìn)程優(yōu)先權(quán)的控制利用系統(tǒng)調(diào)用nice，進(jìn)程可以自然地實(shí)行對它們的調(diào)度優(yōu)先權(quán)的控制：

nice（value）value被加到進(jìn)程優(yōu)先權(quán)值的計(jì)算公式中：priority=（“recentCPUusage”/constant）+(basepriority)+(value)系統(tǒng)調(diào)用fork，進(jìn)程繼承父進(jìn)程的nice值。nice僅作用于正在運(yùn)行的進(jìn)程，一個(gè)進(jìn)程不能設(shè)置另一個(gè)進(jìn)程的nice值。

只有超級用戶才能提供提高進(jìn)程優(yōu)先權(quán)的nice值。普通用戶調(diào)用nice來降低他們進(jìn)程優(yōu)先權(quán)，對其他用戶友好，故名nice。

nice值范圍是[-20,19]，默認(rèn)值是0。8.1.5公平共享調(diào)度上述調(diào)度算法對不同類型的用戶不做區(qū)分，不可能將CPU時(shí)間分一半給一組特殊的進(jìn)程。公平共享調(diào)度的原則是將用戶團(tuán)體分為一些公平共享組。每組成員相對于組中其他進(jìn)程而言，受到常規(guī)進(jìn)程調(diào)度的限制。公平共享組優(yōu)先權(quán)計(jì)算進(jìn)程優(yōu)先權(quán)值時(shí)加入“公平共享組優(yōu)先權(quán)”。每個(gè)進(jìn)程在其u區(qū)有一個(gè)新字段，指向一個(gè)公平共享cpu使用字段，由該公平共享組中所有進(jìn)程共享。時(shí)鐘中斷處理程序就像它增加運(yùn)行進(jìn)程的cpu使用字段一樣，增加運(yùn)行進(jìn)程的公平共享cpu使用字段，并每秒一次地衰減所有公平共享組cpu使用字段的值。進(jìn)程A在一個(gè)組，進(jìn)程B和C在另一個(gè)組。內(nèi)核按A,B,A,C,A,B這樣的次序進(jìn)行調(diào)度。在第一組中的進(jìn)程所得到的cpu時(shí)間是第二組中的進(jìn)程的兩倍。8.1.6實(shí)時(shí)處理實(shí)時(shí)處理指的是對外部事件進(jìn)行立即響應(yīng)，在該事件發(fā)生后的一個(gè)指定時(shí)間內(nèi)，調(diào)度指定的進(jìn)程去運(yùn)行。目前還沒有標(biāo)準(zhǔn)的UNIX系統(tǒng)具有“提供一種機(jī)制來通知內(nèi)核處理進(jìn)程的實(shí)時(shí)要求”這種能力。8.2有關(guān)時(shí)間的系統(tǒng)調(diào)用stime設(shè)置系統(tǒng)日期和時(shí)間

stime（pvalue）pvalue：以秒為單位的長整數(shù)時(shí)間（從1970年1月1日零點(diǎn)開始），時(shí)鐘中斷程序每秒一次地使該變量加1。time查詢系統(tǒng)時(shí)間

time（tloc）tloc：返回的時(shí)間times給出調(diào)用進(jìn)程在用戶態(tài)和核心態(tài)執(zhí)行時(shí)所花費(fèi)的累積時(shí)間，及它的所有僵死子進(jìn)程在在用戶態(tài)和核心態(tài)執(zhí)行時(shí)曾花費(fèi)的累積時(shí)間。times（tbuffer）structtms*tbuffertms含有查詢到的時(shí)間。times返回“從過去的一個(gè)任意時(shí)刻”開始所經(jīng)歷的時(shí)間，通常是系統(tǒng)初啟的時(shí)間。使用系統(tǒng)調(diào)用times的程序一個(gè)進(jìn)程創(chuàng)建了10個(gè)子進(jìn)程，每個(gè)子進(jìn)程循環(huán)10000次。如果一個(gè)子進(jìn)程已經(jīng)終止，并且是一個(gè)僵死進(jìn)程，則wait立即返回并取得該子進(jìn)程的狀態(tài)，否則wait使其調(diào)用者阻塞直到一個(gè)子進(jìn)程終止。如調(diào)用者阻塞而且它有多個(gè)子進(jìn)程，則在其一個(gè)子進(jìn)程終止時(shí)，wait就立即返回。因?yàn)閣ait返回終止子進(jìn)程的進(jìn)程ID，所以它總能了解是哪個(gè)子進(jìn)程終止了。系統(tǒng)調(diào)用alarm來設(shè)置鬧鐘軟中斷信號。stat通過文件名fliename獲取文件信息，保存在buf所指的結(jié)構(gòu)體中。structstat{time_tst_atime}

最后一次使用時(shí)間GIGALRM在用alarm函數(shù)設(shè)置的計(jì)時(shí)器超時(shí)時(shí)會產(chǎn)生此信號。利用系統(tǒng)調(diào)用alarm來設(shè)置鬧鐘軟中斷信號。程序每分鐘檢查一次一個(gè)文件的存取時(shí)間，如果文件被訪問過，則打印出一條信息。調(diào)用stat函數(shù)報(bào)告該文件上次被訪問的時(shí)間，如果在上一分鐘內(nèi)文件被訪問過，則打印出一條信息。調(diào)用signal捕獲鬧鐘信號，調(diào)用alarm來安排每60秒一次的鬧鐘信號，調(diào)用puase掛起它的活動，直到收到一個(gè)信號。60秒后，鬧鐘信號響起，內(nèi)核設(shè)置該進(jìn)程的用戶棧來調(diào)用信號捕獲函數(shù)wakeup，該函數(shù)返回到pause之后的代碼，從而，進(jìn)程再次循環(huán)。8.3時(shí)鐘8.3.2系統(tǒng)的內(nèi)部定時(shí)callout表：用戶不能直接控制callout表的表項(xiàng)，其由各種內(nèi)核算法創(chuàng)建。表項(xiàng)按照各自的“啟動時(shí)間”進(jìn)行排序。各表項(xiàng)的時(shí)間字段記錄的是前一表項(xiàng)啟動后，到該表項(xiàng)被啟動時(shí)的時(shí)間量。對表中某一給定表項(xiàng)，其總的啟動時(shí)間是從啟動表中的第一項(xiàng)直到該表項(xiàng)的時(shí)間的總和。函數(shù)a的表項(xiàng)的時(shí)間字段為-2，意味著a在有資格被調(diào)用之后，系統(tǒng)已經(jīng)過去了2個(gè)時(shí)鐘中斷的時(shí)間。時(shí)鐘中斷處理程序在每次時(shí)鐘中斷時(shí)，檢查callout表中是否有表項(xiàng)。如果有，使第一個(gè)表項(xiàng)的字段減1.，相應(yīng)的其他表項(xiàng)的時(shí)間字段也會減1.如果表中第一項(xiàng)的時(shí)間字段小于或等于0，就調(diào)用對應(yīng)函數(shù)。如果該函數(shù)的運(yùn)行時(shí)間超過一個(gè)時(shí)鐘滴答，下次的時(shí)鐘中斷（以及所有其他發(fā)生的中斷）就會被屏蔽掉。時(shí)鐘中斷處理程序通過引起一個(gè)“軟件中斷”來調(diào)度該函數(shù)。軟件中斷的優(yōu)先級比其他中斷的優(yōu)先級低。在內(nèi)核準(zhǔn)備好調(diào)callout表中的某個(gè)函數(shù)時(shí)刻和軟件中斷發(fā)生的時(shí)刻之間，許多中斷，包括時(shí)鐘中斷都可能發(fā)生。因此，callout表中第一項(xiàng)的時(shí)間字段可能被減為負(fù)值。當(dāng)軟件中斷發(fā)生時(shí)，中斷處理程序清除時(shí)間字段已經(jīng)過時(shí)的callout表項(xiàng)，并調(diào)用相應(yīng)函數(shù)。8.3.3直方圖分析內(nèi)核直方圖分析給出了一種確定系統(tǒng)在用戶態(tài)的執(zhí)行時(shí)間與核心態(tài)執(zhí)行時(shí)間之比，以及內(nèi)核執(zhí)行內(nèi)核中各個(gè)子程序所花費(fèi)的時(shí)間的度量方法。直方圖分析程序有一個(gè)用于采樣的內(nèi)核地址表，表中通常含有內(nèi)核函數(shù)的地址。進(jìn)程事先通過寫直方圖驅(qū)動程序來裝入這些地址。在允許內(nèi)核進(jìn)行直方圖發(fā)分析時(shí)，時(shí)鐘中斷處理程序調(diào)用直方圖驅(qū)動程序的中斷處理程序，首先確定處理機(jī)是處于核心態(tài)還是用戶態(tài)：核心態(tài)：對應(yīng)于程序計(jì)數(shù)器的一個(gè)內(nèi)部計(jì)數(shù)器加1用戶態(tài)：用戶執(zhí)行計(jì)時(shí)器加1圖中給出的是幾個(gè)假象的內(nèi)核子程序的地址，內(nèi)核在用戶態(tài)花費(fèi)20%時(shí)間，在bread算法花費(fèi)50%時(shí)間。由于內(nèi)核不能中斷臨界區(qū)代碼，不能在那里調(diào)用直方圖中斷處理程序。必須有保留地對待內(nèi)核直方圖分析結(jié)果。用戶可以在用戶級使用系統(tǒng)調(diào)用profil來對進(jìn)程的執(zhí)行做統(tǒng)計(jì)。profil（buff，bufsize，offset，scale）buff是用戶空間中的一個(gè)數(shù)組的地址，bufsize是該數(shù)組的大小，offset是一個(gè)用戶子程序（通常是第一個(gè)）的虛地址，scale