進程

進程模型

計算機上的所有可運行的軟件,通常包括操作系統,被組織成若干順序進程(squential process),簡稱進程(process).一個進程就是一個正在運行的實例,包括程序計數器、寄存器和變量的當前值。從概念上說,每個程序擁有它自己的CPU.然而實際上是CPU在多個進程間切換.
在UNIX系統中,可以使用fork()系統調用創建系統調用.
進程的兩個基本屬性：

進程是一個擁有資源的獨立單元； 進程同時又是一個可以被處理器獨立調度和分配的單元。

進程狀態

狀態圖：

進程狀態切換的原因:

就緒狀態→執行狀態：一個進程被進程調度程序選中。 執行狀態→阻塞狀態：請求並等待某個事件發生。 執行狀態→就緒狀態：時間片用完或在搶占式調度中有更高優先級的進程變為就緒狀態。 阻塞狀態→就緒狀態：進程因為等待的某個條件發生而被喚醒。

進程的實現

為了實現進程模型,操作系統維護著一張表格(一個結構數組),即進程表(process table),每個進程占用一個進程表項.進程表項也叫PCB(process control block),該表項包含了進程狀態的重要信息,包括程序計數器,堆棧指針,內存分配狀況,所打開的文件狀態,賬號和調度信息,以及其他在進程由運行態轉換到就緒態或阻塞態時必須保存的信息,從而保證該進程一會能夠再次啟動,就好像從來沒有被切換過一樣.

線程

線程的使用

線程是進程內一個相對獨立的、可調度的執行單元。線程自己基本上不擁有資源，只擁有一點在運行時必不可少的資源（如程序計數器、一組寄存器和棧），但它可以與同屬一個進程的其他線程共享進程擁有的全部資源。多線程是指一個進程中有多個線程，這些線程共享該進程資源。但是各線程自己堆棧數據不對其他線程共享。

經典的線程模型

多對一模型：多對一模型將多個用戶級線程映射到一個內核級線程上。只要一個用戶級線程阻塞，就會導致整個進程阻塞 一對一模型：一對一模型將內核級線程與用戶級線程一一對應。這樣做的好處是當一個線程阻塞時，不影響其他線程的運行。 多對多模型：多對多模型將多個用戶級線程映射到多個內核級線程，采用這樣的模型可以打破前兩種模型對用戶級線程的限制，不僅可以使多個用戶級線程真正意義上並行執行，而且不會限制用戶級線程的數量。

線程的實現

內核級線程：指依賴於內核，由操作系統內核完成創建和撤銷工作的線程。 用戶級線程：指不依賴於操作系統核心，由應用進程利用線程庫提供創建、同步、調度和管理線程的函數來控制的線程 混合實現 : 多對多模型實現,多個用戶線程被分配到多個內核線程上.

用戶級線程的優點:

切換代價小.具體體現為 ：切換都是在本地進行,不需要進入內核,只有一套棧,而內核有兩套棧.所以速度會快很多；不需要trap,不需要上下文切換,也不需要對內存高速緩存進行刷新. 允許每個進程都有自己的調度算法(進程主動使用yield()放棄)

用戶級線程的缺點:
- 如何實現阻塞系統調用,因為這會停止所有的用戶態指令.
- 如果發生缺頁中斷,由於操作系統不知道有其他線程存在,會阻塞到這個線程完成缺頁中斷,而不是去調度其他用戶級線程

線程與進程的比較

調度：在傳統的操作系統中，擁有資源和獨立調度的基本單位都是進程。而在引入線程的操作系統中，線程是獨立調度的基本單位，進程是擁有資源的基本單位。在同一進程中，線程的切換不會引起進程切換。在不同進程中進行線程切換，如從一個進程內的線程切換到另一個進程中的線程中，將會引起進程切換。 擁有資源：進程是擁有資源的基本單位，而線程不擁有系統資源（也有一點必不可少的資源，並非什麼資源都沒有），但線程可以訪問其隸屬進程的系統資源。 並發性：在引入線程的操作系統中，不僅進程之間可以並發執行，而且同一進程內的多個線程之間也可以並發執行。 系統開銷：由於創建進程或撤銷進程時，系統都要為之分配或回收資源，系統開銷較大；而線程切換時，只需保存和設置少量寄存器內容，因此開銷很小。

進程間通信

臨界區

臨界資源：同時僅允許一個進程使用的資源稱為臨界資源。許多物理設備都屬於臨界資源，如打印機、繪圖機等。 臨界區：每個進程中訪問臨界資源的一段代碼。

互斥的概念與要求

為了禁止兩個進程同時進入臨界區，軟件算法或同步機構都應遵循以下准則：

空閒讓進：當沒有進程處於臨界區時，可以允許一個請求進入臨界區的進程立即進入自己的臨界區。 忙則等待：當已有進程進入其臨界區時，其他試圖進入臨界區的進程必須等待。 有限等待：對要求訪問臨界資源的進程，應保證能在有限的時間內進入自己的臨界區。 讓權等待：當一個進程因為某些原因不能進入自己的臨界區時，應釋放處理器給其他進程。

忙等待的互斥

幾種互斥的方案

屏蔽中斷 ：在單處理器的系統中,最簡單的方法是在每個線程剛剛進入臨界區的時候將中斷屏蔽,並在離開臨界區的時候將中斷重新開啟. 這個方案並不好,把屏蔽中斷的權利交給用戶進程是不明智的.如果一個惡意的進程屏蔽中斷之後不再打開中斷,那就歇逼了. 而且,如果系統是多處理器系統,屏蔽中斷只能對執行的那個cpu有效 鎖變量 ：鎖變量是一種軟件方法.設想有一個共享變量,其初始值為0.當一個進程想進入其臨界區時,它首先測試這把鎖.如果鎖的值為0,則該進程將其設置為1並進入臨界區.如果是1,就等到變成0再進入. 這種方案還是有問題,原因在於對鎖變量的訪問不是原子的. 嚴格輪換法 Peterson解法 最常用的方法-TSL和XCHG指令：TSL指令的功能是這樣的:將一個內存字lock讀取到寄存器RX中,然後在該內存地址上存一個非零值.讀字和寫字操作保證是不可分割的,即該指令結束之前其他處理器均不允許訪問改內存字.執行TSL將總線鎖住,防止其他CPU在本指令結束前訪問內存.
這個方法和鎖變量法的思維基本一致,但是借助了硬件實現了原子操作.
XCHG的功能是原子性的交換兩個位置的內容.

睡眠與喚醒

Peterson解法和TSL或XCHG解法都是正確的,但他們都有忙等待的缺點.
另外一種進程間通信原語,他們無法進入臨界區時將被阻塞,而不是忙等待.最簡單的是sleep和weakup.sleep是一個將引起調用進程阻塞的系統調用,即被掛起,直到另一個進程將其喚醒.weakup調用有一個參數是weakup調用將要喚醒的進程的地址.

生產者消費者問題

代碼如下:

#define N 100 /* number of slots in the buffer */
int count = 0; /* number of items in the buffer */
void producer(void)
{
    int item;
    while (TRUE) { /* repeat forever */
    item = produce item( ); /* generate next item */
    if (count == N) sleep( ); /* if buffer is full, go to sleep */
    inser t item(item); /* put item in buffer */
    count = count + 1; /* increment count of items in buffer */
    if (count == 1) wakeup(consumer); /* was buffer empty? */
    }
}
void consumer(void)
{
    int item;
    while (TRUE) { /* repeat forever */
    if (count == 0) sleep( ); /* if buffer is empty, got to sleep */
    item = remove item( ); /* take item out of buffer */
    count = count ? 1; /* decrement count of items in buffer */
    if (count == N ? 1) wakeup(producer); /* was buffer full? */
    consume item(item); /* print item */
}

上面這段代碼由於對count的操作不是原子操作,所以會導致多線程問題.這種方法並沒有很好的解決這個問題.

信號量

信號量是一種新的變量類型,它使用一個整形變量來累計喚醒次數,供以後使用.
Dijkstra建議設立兩種操作:down和up.對一個信號量進行down操作,則實際檢查其值是否大於0,如果大於0就減一.如果為0,就睡眠.此時down操作暫未結束,只有另一個進程up時,操作系統才會選擇一個進程進行up操作.
檢查數值,修改變量值以及可能發生的睡眠操作都是用原子操作完成的.對信號量原子性的保護可以用之前提到的TSL和XCHG實現.
up操作對信號量的值增加1.如果一個或多個進程在該信號量上睡眠,無法完成一個先前的down操作,則系統選擇一個完成down操作.於是,這種情況下,執行了一個up操作,但是信號量的值仍然是0,但是在其上睡眠的進程卻少了一個.不會有進程因為執行up操作而阻塞.

信號量實現生產者消費者的代碼:

#define N 100 /* number of slots in the buffer */
typedef int semaphore; /* semaphores are a special kind of int
semaphore mutex = 1; /* controls access to critical region */
semaphore empty = N; /* counts empty buffer slots */
semaphore full = 0; /* counts full buffer slots */
void producer(void)
{
        int item;
        while (TRUE) { /* TRUE is the constant 1 */
        item = produce item( ); /* generate something to put in buffer *
        down(&empty); /* decrement empty count */
        down(&mutex); /* enter critical region */
        inser t item(item); /* put new item in buffer */
        up(&mutex); /* leave critical region */
        up(&full); /* increment count of full slots */
    }
}
void consumer(void)
{
    int item;
    while (TRUE) { /* infinite loop */
        down(&full); /* decrement full count */
        down(&mutex); /* enter critical region */
        item = remove item( ); /* take item from buffer */
        up(&mutex); /* leave critical region */
        up(&empty); /* increment count of empty slots */
        consume item(item); /* do something with the item */
    }
}

互斥量

信號量的一個簡化版本稱為互斥量
互斥量只有兩個狀態:解鎖和加鎖.常常使用一個整形量,0表示解鎖,其他所有值表示加鎖.當進程需要訪問臨界區時,它調用mutex_lock().當他出來時,它調用mutex_unlock().互斥量TSL實現代碼如下:

mutex lock:
    TSL REGISTER,MUTEX | copy mutex to register and set mutex to
    CMP REGISTER,#0 | was mutex zero?
    JZE ok | if it was zero, mutex was unlocked, so r
    CALL thread yield | mutex is busy; schedule another thread
    JMP mutex lock | tr y again
    ok: RET | return to caller; critical region entered
mutex unlock:
    MOVE MUTEX,#0 | store a 0 in mutex
    RET | return to caller

mutex和enter_region的區別很明顯:
enter_region()當測試不成功時就一直循環測試.而mutex會直接放棄時間片,讓另一個進程得到調度,這樣就避免了忙等待浪費資源.

Pthread中的互斥

Pthread提供許多可以用來同步線程的函數.其基本機制是使用一個可以被鎖定和解鎖的互斥量倆保護每個臨界區.一個線程想進入臨界區,它會先測試臨界區有沒有加鎖,如果沒有,就立即進入.如果加鎖了,就阻塞直到解鎖.如果多個互斥量等待同一個互斥量,就只允許一個線程復活.

線程調用 描述 pthread_mutex_init 創建一個互斥量 pthread_mutex_destroy 撤銷一個已存在的互斥量 pthread_mutex_lock 獲得一個鎖或阻塞 pthread_mutex_trylock 獲得一個鎖或失敗 pthread_mutex_unlock 釋放一個鎖

管程

使用mutex和信號量可能會引發死鎖問題.為了更易於編寫正確的程序,Brinch Hansen 和 Hoare 提出了管程.管程中是一個由過程,變量及數據結構等組成的一個集合,它們組成一個特殊模塊.
管程的一個很重要的特性就是任意時刻管程內只有一個活躍進程.
進入管程時的互斥由編譯器進行負責,但通常的做法是用一個互斥量或二元信號量.因為編譯器安排互斥是的出錯的可能小的多.
java中使用管程解決生產者消費者的代碼:

public class ProducerConsumer {
    static final int N = 100; // constant giving the buffer size
    static producer p = new producer( ); // instantiate a new producer thread
    static consumer c = new consumer( ); // instantiate a new consumer thread
    static our monitor mon = new our monitor( ); // instantiate a new monitor
    public static void main(String args[ ]) {
        p.star t( ); // star t the producer thread
        c.star t( ); // star t the consumer thread
    }
    static class producer extends Thread {
    public void run( ) { // run method contains the thread code
        int item;
        while (true) { // producer loop
        item = produce item( );
        mon.inser t(item);
        }
    }
    private int produce item( ) { ... } // actually produce
    }
    static class consumer extends Thread {
    public void run( ) { run method contains the thread code
    int item;
    while (true) { // consumer loop
        item = mon.remove( );
        consume item (item);
    }
    }
    private void consume item(int item) { ... }// actually consume
    }
    static class our monitor { // this is a monitor
    private int buffer[ ] = new int[N];
    private int count = 0, lo = 0, hi = 0; // counters and indices
    public synchronized void insert(int val) {
    if (count == N) go to sleep( ); // if the buffer is full, go to sleep
        buffer [hi] = val; // inser t an item into the buffer
        hi = (hi + 1) % N; // slot to place next item in
        count = count + 1; // one more item in the buffer now
    if (count == 1) notify( ); // if consumer was sleeping, wake it up
    }
    public synchronized int remove( ) {
        int val;
        if (count == 0) go to sleep( ); // if the buffer is empty, go to sleep
        val = buffer [lo]; // fetch an item from the buffer
        lo = (lo + 1) % N; // slot to fetch next item from
        count = count ? 1; // one few items in the buffer
        if (count == N ? 1) notify( ); // if producer was sleeping, wake it up
        return val;
    }
    private void go to sleep( ) { try{wait( );} catch(InterruptedException exc) {};}
    }
}

調度

調度介紹

進程行為

幾乎所有的進程I/O請求或計算都是交替突發的.
進程有IO密集型和計算密集型兩種.

何時調度

有關調度處理的一個關鍵問題是何時進行調度決策.

創建一個新進程之後,需要決定是運行父進程還是運行子進程 在一個進程退出時必須要做出調度決策 當一個進程阻塞在I/O和信號量上或由於其他原因阻塞時,必須選擇另一個進程運行. 當一個I/O中斷發生時,必須做出調度決策.

如果硬件時鐘提供50HZ,60HZ或其他頻率的周期性中斷,可以在每個時鐘中斷或者在每k個中斷時做出調度決策.
根據如何處理時鐘中斷,可以把調度算法分為兩類.

調度算法的目標

不同調度算法有不同的調度策略，這也決定了調度算法對不同類型的作業影響不同。在選擇調度算法時，必須考慮不同算法的特性。為了衡量調度算法的性能，人們提出了一些評價標准。

CPU利用率：CPU是系統最重要、也是最昂貴的資源，其利用率是評價調度算法的重要指標。 系統吞吐量 ：系統吞吐量表示單位時間內CPU完成作業的數量。對長作業來說，由於它要占用較長的CPU處理時間，因此會導致系統吞吐量下降，而對短作業來說則相反。 響應時間 ：在交互系統中，尤其在多用戶系統中，多個用戶同時對系統進行操作，都要求在一定時間內得到響應，不能使某些用戶的進程長期得不到調用。 周轉時間 ：從每個作業的角度來看，完成該作業的時間是至關重要的，通常用周轉時間或者帶權周轉時間來衡量。

批處理系統中的調度

先來先服務 ：適用范圍：可用於作業調度和進程調度。
基本思想是按照進程進入就緒隊列的先後次序來分配處理器。先來先服務調度算法采用非搶占的調度方式 短作業優先調度算法 ：基本思想是把處理器分配給最快完成的作業。

交互式系統中的調度

輪轉調度：每個進程被分配一個時間片,即允許該進程在該時間片結束前阻塞或結束,即CPU立即進行切換 優先級調度算法：輪轉調度假設所有的進程都一樣重要,事實上進程分為前台和後台進程,前台和後台進程對於調度的要求都不一樣.
基本思想是把處理器分配給優先級最高的進程。進程優先級通常分為兩種：a.靜態優先級：是指優先級在創建進程時就已經確定了，在整個進程運行期間不再改變；b.動態優先級：是指在創建進程時，根據進程的特點及相關情況確定一個優先級，在進程運行過程中再根據情況的變化調整優先級。 多級隊列調度算法： 適用范圍：主要用於進程調度。
基本思想是根據進程的性質或類型，將就緒隊列劃分為若干個獨立的隊列，每個進程固定地分屬於一個隊列。每個隊列采用一種調度算法，不同的隊列可以采用不同的調度算法。 彩票調度 ：其基本思想是向進程提供各種系統資源的彩票.一旦需要作出一項調度決策時,就隨機抽出一張彩票,擁有該彩票的進程獲得該進程獲得該資源.在應用時,系統可以掌握每秒鐘的一種彩票,作為獎勵每個進程可以獲得20ms的CPU時間

線程調度

用戶級線程

由於內核並不知道用戶級線程的存在,所以內核會調度進程,在每個進程執行的時間片內,進程自由調度它的用戶線程.

內核級線程

內核選擇一個特定的線程運行.它不用考慮該線程屬於哪個進程,不過如果有必要的話,它可以這麼做.對被選擇的線程賦予一個時間片,如果超過了時間片,就強制掛起該線程.

用戶級線程和內核級線程的差距在於性能.用戶級線程的線程切換需要少量的機器指令,而內核級線程需要完整的上下文切換,修改內存映像,是告訴緩存失效,這導致了若干數量級的延遲.

切換同一個進程的線程開銷小於切換進程.切換進程之間的進程需要比切換同一個進程的線程多做一些工作.比如:修改內存映像,清除高速緩存

經典的IPC問題

哲學家就餐問題

錯誤的解法:

#define N 5 /* number of philosophers */
void philosopher(int i) /* i: philosopher number, from 0 to 4 */
{
    while (TRUE) {
        think( ); /* philosopher is thinking */
        take fork(i); /* take left fork */
        take fork((i+1) % N); /* take right fork; % is modulo operator */
        eat( ); /* yum-yum, spaghetti */
        put fork(i); /* put left fork back on the table */
        put fork((i+1) % N); /* put right fork back on the table */
    }
}

當出現這樣一種極端情況:每個哲學家都拿到了左邊的叉子,嘗試去拿右邊的叉子.
這種情況下就出現了死鎖
為了解決這個問題,可以讓其中一位哲學家不先拿左邊的,而是先拿右邊的叉子.這樣就不會出現死鎖了.
下面這種解法,不僅沒有死鎖,而且獲得了最大的並行度.

#define N 5 /* number of philosophers */
#define LEFT (i+N?1)%N /* number of i’s left neighbor */
#define RIGHT (i+1)%N /* number of i’s right neighbor */
#define THINKING 0 /* philosopher is thinking */
#define HUNGRY 1 /* philosopher is trying to get forks */
#define EATING 2 /* philosopher is eating */
typedef int semaphore; /* semaphores are a special kind of int */
int state[N]; /* array to keep track of everyone’s state */
semaphore mutex = 1; /* mutual exclusion for critical regions */
semaphore s[N]; /* one semaphore per philosopher */
void philosopher(int i) /* i: philosopher number, from 0 to N?1 */
{
    while (TRUE) { /* repeat forever */
        think( ); /* philosopher is thinking */
        take forks(i); /* acquire two forks or block */
        eat( ); /* yum-yum, spaghetti */
        put forks(i); /* put both forks back on table */
    }
}
void take forks(int i) /* i: philosopher number, from 0 to N?1 */
{
    down(&mutex); /* enter critical region */
    state[i] = HUNGRY; /* record fact that philosopher i is hungry */
    test(i); /* tr y to acquire 2 forks */
    up(&mutex); /* exit critical region */
    down(&s[i]); /* block if forks were not acquired */
}
void put forks(i) /* i: philosopher number, from 0 to N?1 */
{
    down(&mutex); /* enter critical region */
    state[i] = THINKING; /* philosopher has finished eating */
    test(LEFT); /* see if left neighbor can now eat */
    test(RIGHT); /* see if right neighbor can now eat */
    up(&mutex); /* exit critical region */
}
void test(i) /* i: philosopher number, from 0 to N?1 */
{
    if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
        state[i] = EATING;
        up(&s[i]);
    }
}

算法使用一個state數組跟蹤每個哲學家是在進餐、思考還是饑餓(正在試圖拿叉子).一個哲學家只有在兩個鄰居都沒有進餐時才允許進入到進餐狀態.第i個哲學家的鄰居則由宏LEFT和RIGHT定義.
該程序使用了一個信號量數組,每個信號量對應一個哲學家,這樣在所需的叉子被占用時,想進餐的哲學家就被阻塞.

讀者寫者問題

讀者-寫者問題為數據庫建立了一個模型.考慮一個飛機訂票系統,其中有許多競爭進程試圖讀寫其中的數據.多個進程同時讀數據庫是可以接收的.但是只要有一個寫者在寫,那麼其他進程都不能訪問,即使讀操作也不可以.
在該解法中,隱含著一個需要注解的條件.假設一個讀者正在使用數據庫,另一個讀者來了.同時兩個讀者並不存在問題.第二個讀者也允許進入.如果有第三個和更多的讀者來了也同樣允許.
現在假設一個寫者到來.由於寫者的訪問時排他的,不能允許寫者進入數據庫,只能被掛起.只要還有一個讀者在活動,就允許後續的讀者進來.這種策略的結果是,如果有一個穩定的讀者流,那麼寫者將永遠得不到訪問.
為了避免這種情況,可以稍微改變一下程序的寫法:在一個讀者到達,且一個寫者在等待時,讀者在寫者之後被掛起,而不是立即允許進入.

typedef int semaphore; /* use your imagination */
semaphore mutex = 1; /* controls access to rc */
semaphore db = 1; /* controls access to the database */
int rc = 0; /* # of processes reading or wanting to */
void reader(void)
{
    while (TRUE) { /* repeat forever */
        down(&mutex); /* get exclusive access to rc */
        rc = rc + 1; /* one reader more now */
        if (rc == 1) down(&db); /* if this is the first reader ... */
        up(&mutex); /* release exclusive access to rc */
        read data base( ); /* access the data */
        down(&mutex); /* get exclusive access to rc */
        rc = rc ? 1; /* one reader fewer now */
        if (rc == 0) up(&db); /* if this is the last reader ... */
        up(&mutex); /* release exclusive access to rc */
        use data read( ); /* noncritical region */
    }
}
void writer(void)
{
    while (TRUE) { /* repeat forever */
        think up data( ); /* noncritical region */
        down(&db); /* get exclusive access */
        write data base( ); /* update the data */
        up(&db); /* release exclusive access */
    }
}