第八章進程調(diào)度和時間

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

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

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

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

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

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

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

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

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

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

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

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

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

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

priority=（CPU/2）+60

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

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

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

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

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

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

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