1.計(jì)算機(jī)硬件簡單介紹

1.1 基本硬件組成

1. 處理器
   一般是CPU,計(jì)算機(jī)用來完成運(yùn)算的主要組成,其中一般還包含多級緩存和支持的指令集.

2. 存儲器
   RAM,運(yùn)行中的程序計(jì)數(shù)器(指向下一條CPU指令的指針)及其堆棧和變量等一切相關(guān)信息會放在緩存中,方便CPU調(diào)取,速度比起CPU的內(nèi)部緩存會慢,又快于磁盤等大容量存儲設(shè)備.

3. 磁盤
   計(jì)算機(jī)用于存儲數(shù)據(jù)的設(shè)備,速度很慢,但是掉電后非易失,存儲容量大,廉價(jià)等特性讓其成為現(xiàn)代計(jì)算機(jī)系統(tǒng)不可缺少的設(shè)備.

4. I/O設(shè)備
   輸入輸出設(shè)備.

5. 總線
   用于將上述的所有設(shè)備鏈接起來的抽象概念,現(xiàn)在計(jì)算機(jī)系統(tǒng)一般會有多種總線,用橋(bridge)再連接各級總線.

1.2 硬件間的通訊

以一個最普通的作業(yè)為例,假設(shè)它的運(yùn)行包括如下步驟

1. 運(yùn)算
2. 等待I/O設(shè)備輸入    
3. 從磁盤讀取數(shù)據(jù)
4. 運(yùn)算
5. 結(jié)束

1. 假設(shè)在沒有操作系統(tǒng),在最簡單的情況下.CPU會通過一個循環(huán)忙等待將會從步驟2中輸入的數(shù)據(jù),然后通過總線通知磁盤讀取數(shù)據(jù),然后又會以相同的方法等待步驟3返回的數(shù)據(jù).

細(xì)心的你可能會看到這個沒有操作系統(tǒng)的計(jì)算機(jī)存在巨大的資源浪費(fèi).

2. 在裝有操作系統(tǒng)的計(jì)算機(jī)上,在步驟2和步驟3中,CPU不會進(jìn)入一個忙等待過程,而是會將當(dāng)前作業(yè)的程序計(jì)數(shù)器,變量,堆棧等信息存儲在內(nèi)存中的一個特殊表中,然后調(diào)取下一個作業(yè)開始執(zhí)行.

   當(dāng)I/O設(shè)備完成輸入,或者磁盤完成讀取操作后,這些設(shè)備會通過總線,向中斷控制器發(fā)出中斷信號,再由中斷控制器通知CPU.

   CPU決定是將當(dāng)前任務(wù)暫存(掛起),代而執(zhí)行之前掛起的作業(yè),還是等待合適的時候再執(zhí)行先前程序,取決于操作系統(tǒng)調(diào)度算法,總之,這樣就通過操作系統(tǒng)完成了比較高效的作業(yè)執(zhí)行.

上述模型在交互較少的情況下有著良好的效率,但是在交互式系統(tǒng)中,多個用戶可能希望多個作業(yè)在感官上同時執(zhí)行,而不是等待上一個作業(yè)執(zhí)行完畢或等待I/O或讀寫磁盤時再執(zhí)行下一個作業(yè).這時就要求操作系統(tǒng)必須實(shí)現(xiàn)作業(yè)的并行,起碼是偽并行,因?yàn)檎嬲牟⑿性趩蜟PU計(jì)算機(jī)上是不可能的.

2.單CPU計(jì)算機(jī)實(shí)現(xiàn)偽并行

2.1 為什么需要并行

1. 現(xiàn)代計(jì)算機(jī)系統(tǒng)中,在一般情況下,同一個作業(yè)中,CPU的運(yùn)算時間遠(yuǎn)遠(yuǎn)低于I/O或讀寫磁盤存儲器這類耗時操作所需要的時間.
   在沒有并行的時候,CPU在完成運(yùn)算后就需要等待I/O,這是個巨大的資源浪費(fèi)

2. 在交互式系統(tǒng)中,一般要求多個用戶的進(jìn)程在感官上同時執(zhí)行,或者單個用戶的多個進(jìn)程間也要求感官上的同時運(yùn)行,如果做不到這一點(diǎn),該系統(tǒng)的用戶體驗(yàn)也是極其惡劣的.

   所以,尤其在交互式系統(tǒng)中,(偽)并行將是一個合格的操作系統(tǒng)不得不考慮的問題.

2.2 操作系統(tǒng)的作用

個人認(rèn)為操作系統(tǒng)有以下職責(zé):

1. 封裝硬件,提供簡單接口
2. 提供諸如進(jìn)程,線程,地址空間,文件等的抽象

2.3 操作系統(tǒng)如何實(shí)現(xiàn)偽并行

首先需要了解什么是進(jìn)程,什么是線程
1. 進(jìn)程:是操作系統(tǒng)對一個正在運(yùn)行的程序的抽象.其中包括該程序的程序計(jì)數(shù)器,寄存器,變量的當(dāng)前值等.
2. 線程:是一種輕量化的進(jìn)程,與進(jìn)程不同的是它與其他同屬一個進(jìn)程的線程間是共享寄存器的.

1. 一句話解釋系統(tǒng)實(shí)現(xiàn)(偽)并行的方法:
   CPU在所有進(jìn)程間快速切換.

2. 如何觸發(fā)切換
   這種切換的出發(fā)機(jī)制有兩種可能,一種是時鐘中斷,一種是I/O中斷.具體的實(shí)現(xiàn)細(xì)節(jié)在不同的操作系統(tǒng)中是不同的,但是大體上是類似的,CPU在經(jīng)歷了N個時鐘中斷后將當(dāng)前的進(jìn)程掛起,轉(zhuǎn)而運(yùn)行下一個進(jìn)程(具體運(yùn)行哪一個程序,這取決于操作系統(tǒng)的調(diào)度算法).或者當(dāng)進(jìn)程在等待I/O操作,或有耗時操作,需要CPU忙等待時,CPU就會運(yùn)行下一進(jìn)程.

3. 如何切換
   進(jìn)程切換過程如下:

   1. 時鐘中斷,或I/O中斷,或讀寫數(shù)據(jù)到達(dá),發(fā)生進(jìn)程切換
   2. 原有進(jìn)程的程序計(jì)數(shù)器,變量當(dāng)前值,堆棧等被保存在寄存器的一個特殊表中
   3. 調(diào)取下一個進(jìn)程的程序計(jì)數(shù)器,變量當(dāng)前值,堆棧等
   4. 運(yùn)行該進(jìn)程

對于用戶而言,相當(dāng)于操作系統(tǒng)為其進(jìn)程或線程提供了一個單獨(dú)的CPU和寄存器.

3.互斥問題

在實(shí)現(xiàn)了(偽)并行后,馬上就會有一個嚴(yán)重的問題擺在面前"競爭條件"

舉例說明:(假設(shè)有兩個進(jìn)程A,B)
1. A將變量a寫入共享寄存器,準(zhǔn)備使用顯示器顯示到屏幕上.
2. 就在A準(zhǔn)備但還沒有顯示a時,發(fā)生了中斷.
3. CPU將A掛起,轉(zhuǎn)而運(yùn)行B.
4. B將變量b寫入相同位置,準(zhǔn)備顯示.
5. 再次發(fā)生中斷,在b沒有顯示的時候,CPU切換回A進(jìn)程.
6. A錯誤的顯示了變量b.
這樣A的變量a在未被A察覺的情況下永遠(yuǎn)的丟失了.

這就是"競爭條件,"為了解決這一問題,A在訪問共享內(nèi)存時,B必須被阻止訪問到該寄存器.即該寄存器必須被"互斥"的訪問.

3.1 單CPU計(jì)算機(jī)如何解決互斥問題

由此可見,競爭條件問題形成的充分條件有兩個,一是要有共享資源,二是要在特定的時間發(fā)生中斷.只要打破了其中的一條,就能完成互斥.實(shí)現(xiàn)資源的不共享是不可能的,所以我們必須能夠讓CPU屏蔽中斷信號.

在實(shí)現(xiàn)互斥的問題上,我們必須引入一個概念"鎖變量".這個變量為0時,表示共享資源可以被訪問,為1時表示共享資源已被鎖,不能訪問.

為每個共享資源加入鎖變量后,在進(jìn)程想要訪問共享資源時直接讀取鎖變量就知道資源是否可用.

具體實(shí)現(xiàn)如下:
1. 進(jìn)程A想要訪問共享資源,通知CPU屏蔽所有中斷.
2. A判斷資源是否可用,可用則將鎖變量置1.不可用則伺機(jī)再從第一步重新執(zhí)行.
3. CPU開始接收中斷正常運(yùn)行.
4. A完成操作,將鎖變量置0.

這樣就實(shí)現(xiàn)了單CPU計(jì)算機(jī)系統(tǒng)上的互斥,同樣還有很多算法也可以實(shí)現(xiàn)互斥,如Peterson算法.但是包括上述方法,在具體使用場景中,用的很少.一般使用TSL指令來實(shí)現(xiàn)互斥.

3.2 多CPU(或多核)計(jì)算機(jī)解決互斥問題

在多CPU(多核心CPU)計(jì)算機(jī)系統(tǒng)中,通過屏蔽中斷,是無法實(shí)現(xiàn)互斥的.因?yàn)榫退阕屵M(jìn)程所在的CPU屏蔽了中斷,也不能保證運(yùn)行在其他CPU上的進(jìn)程不會訪問到共享資源.所以需要一種全新的互斥方法.

TSL(Test and Set Lock)指令.這是一種硬件級別的指令,其核心方法是直接鎖定內(nèi)存總線.

TSL的匯編代碼進(jìn)行了如下操作:
1. 將鎖變量復(fù)制到程序寄存器中,并將原來的鎖變量置1.
2. 將寄存器中的值與0做對比,等于則表示可以訪問共享資源,不等于則伺機(jī)再執(zhí)行TSL.
3. 操作結(jié)束后,講鎖變量置0.

有了TSL指令,就可以在多CPU計(jì)算機(jī)系統(tǒng)上實(shí)現(xiàn)互斥.

在Pthread中有關(guān)互斥量的操作,都是這個原理.

3.3 信號量和互斥量

用TSL可以原子的實(shí)現(xiàn)信號量和互斥量,也可以理解為信號量和互斥量是對TSL指令的封裝.

1. 信號量是記錄未被執(zhí)行的鎖和釋放的次數(shù),在解決界緩沖問題的時候,通過多個信號量來標(biāo)記每個進(jìn)程的狀態(tài),從而決定進(jìn)程的行為.過程較為復(fù)雜,再次不做詳述.

2. 互斥量是簡化的信號量,因?yàn)榛コ饬渴且粋€二元信號量,一般是0和其他.用于標(biāo)記兩種狀態(tài).

值得注意的是不管是在信號量還是互斥量操作中,未獲得鎖后是直接放棄CPU使用(thread_yeild調(diào)用),而不是忙等待.

4.哲學(xué)家就餐

現(xiàn)在嘗試用以上互斥方法解決哲學(xué)家就餐問題.

4.1 問題描述

1. 有N個哲學(xué)家,哲學(xué)家狀態(tài)有兩種,就餐和思考,并隨機(jī)發(fā)生.
2. 每個哲學(xué)家面前有一碗面,左右各一把叉子.共有N碗面,N個叉子(兩個相鄰的哲學(xué)家之間只有一把叉子).
3. 哲學(xué)家就餐需要有兩把叉子,并且只能在自己左右取.規(guī)定,哲學(xué)家先拿左叉后拿右叉.
4. 讓每個哲學(xué)家順利完成就餐和思考.

4.2 問題分析

1. 如果N位哲學(xué)家同時就餐,拿起身邊的左叉,等待右叉就會發(fā)生死鎖.
2. 如果在一位哲學(xué)家就餐時用互斥量鎖住所有的叉子,不讓其他哲學(xué)家就餐,這樣是可以的,但是會造成資源的浪費(fèi).
3. 所以為了最大化的使用資源,得想辦法鎖定與就餐的哲學(xué)家有關(guān)的叉子,而不是鎖定全部.

4.3 嘗試解決

該哲學(xué)家左右都是處于非就餐狀態(tài)的哲學(xué)家時,這個哲學(xué)家就可以就餐,這樣就解決了資源的最大化利用.

使用三個主要變量
1. 每個哲學(xué)家的狀態(tài)數(shù)組state[],狀態(tài)有THINKING,HUNGERY,EATING.
2. 互斥量mutex,用于獲取兩把叉子.
3. 數(shù)組s[],由于哲學(xué)家在想就餐的時候不一定能立即實(shí)現(xiàn)顺呕，所以需要信號量來記錄未實(shí)現(xiàn)的就餐需求.


步驟:
1. 原子性檢查左右哲學(xué)家的狀態(tài)
2. 如果左右的哲學(xué)家都不是處于EATING狀態(tài),則表示可以就餐.
3. 如果不是,則將自己掛起(對信號量s[i]執(zhí)行down操作,以記錄這次就餐請求),等待2中描述的狀態(tài).
4. 完成就餐放下所有叉子.

互斥:
1. 哲學(xué)家必須原子性的檢查自己左右的哲學(xué)家是否處于EATING狀態(tài).使用mutex.
2. 在未達(dá)到預(yù)期狀態(tài)(左右都是非EATING狀態(tài)的哲學(xué)家)的時候,用一個信號量s[i]記錄用餐請求,等待情況出現(xiàn).完成就餐后up這個信號量.

來自博客:http://newlooc.com