18.1信號(hào)量

回顧

■并發(fā)問(wèn)題

多線程并發(fā)導(dǎo)致資源競(jìng)爭(zhēng)

■同步概念

協(xié)調(diào)多線程對(duì)共享數(shù)據(jù)的訪問(wèn)

任何時(shí)刻只能有一個(gè)線程執(zhí)行臨界區(qū)代碼

■確保同步正確的方法

底層硬件支持

高層次的編程抽象

基本同步方法

信號(hào)量(semaphore)

■信號(hào)量是操作系統(tǒng)提供的一種協(xié)調(diào)共享資源訪問(wèn)的方法

軟件同步是平等線程間的一種同步協(xié)商機(jī)制（線程是平等的）

OS是管理者，地位高于進(jìn)程

用信號(hào)量表示系統(tǒng)資源的數(shù)量

■由Dijkstra在20世紀(jì)60年代提出

■早期的操作系統(tǒng)的主要同步機(jī)制

現(xiàn)在很少用（但還是非常重要在計(jì)算機(jī)科學(xué)研究）

■信號(hào)量是一種抽象數(shù)據(jù)類型

·由一個(gè)整形(sem)變量（共享資源數(shù)目）和兩個(gè)原子操作組成

·P()(Prolaag（荷蘭語(yǔ)嘗試減少）)

sem減1

如sem<0,進(jìn)入等待,否則繼續(xù)

·V()(Verhoog（荷蘭語(yǔ)增加）)

sem加1

如sem≤0,喚醒一個(gè)等待進(jìn)程

信號(hào)量的特性

■信號(hào)量是被保護(hù)的整數(shù)變量

初始化完成后，只能通過(guò)P()和V()操作修改

由操作系統(tǒng)保證，PV操作是原子操作

■P()可能阻塞，V()不會(huì)阻塞

■通常假定信號(hào)量是“公平的”

線程不會(huì)被無(wú)限期阻塞在P()操作

假定信號(hào)量等待按先進(jìn)先出排隊(duì)

自旋鎖能否實(shí)現(xiàn)先進(jìn)先出?

自旋鎖是需要占用CPU隨時(shí)隨地去查標(biāo)志，有可能臨界區(qū)的使用者退出的時(shí)候它剛改完標(biāo)志，下一個(gè)進(jìn)入者哪個(gè)線程去查，那它就能進(jìn)去，如果說(shuō)運(yùn)氣不好，正好是這個(gè)資源變成有效的時(shí)候，你去查的時(shí)候在你之前就有一個(gè)人已經(jīng)查過(guò)了，就沒(méi)有辦法按照你等待的這個(gè)順序來(lái)執(zhí)行。

信號(hào)量的實(shí)現(xiàn)

18.2信號(hào)量的使用

精髓：

基本原理:兩個(gè)或多個(gè)進(jìn)程可以通過(guò)簡(jiǎn)單的信號(hào)進(jìn)行合作，一個(gè)進(jìn)程可以被迫在某一位置停止，直到它接收到一個(gè)特定的信號(hào)。任何復(fù)雜的合作需求都可以通過(guò)適當(dāng)?shù)男盘?hào)結(jié)構(gòu)得到滿足。為了發(fā)信號(hào)，需要使用一個(gè)稱做信號(hào)量的特殊變量。信號(hào)量分類

■可分為兩種信號(hào)量

·二進(jìn)制信號(hào)量：資源數(shù)目為0或1（有些系統(tǒng)稱為互斥鎖）

·資源信號(hào)量:資源數(shù)目為任何非負(fù)值

·兩者等價(jià)

基于一個(gè)可以實(shí)現(xiàn)另一個(gè)

■信號(hào)量的使用

·互斥訪問(wèn)

■臨界區(qū)的互斥訪問(wèn)控制

·條件同步

線程間的事件等待

用信號(hào)量實(shí)現(xiàn)臨界區(qū)的互斥訪問(wèn)

用一個(gè)信號(hào)量來(lái)對(duì)應(yīng)一個(gè)臨界區(qū),,通過(guò)mutex的值來(lái)確定該資源的情況，P（）減一V（）加一，但mutex為負(fù)值的時(shí)候表示使用該資源的線程有在排隊(duì)的，這樣來(lái)實(shí)現(xiàn)互斥訪問(wèn)

用信號(hào)量實(shí)現(xiàn)條件同步

也是通過(guò)condition這個(gè)值來(lái)控制的，有一個(gè)資源B只在使用，只用通過(guò)V（）操作加一后，condition的值小于等于0就知道有另一個(gè)線程A在等他，然后喚醒A。

生產(chǎn)者-消費(fèi)者問(wèn)題

用信號(hào)量解決生產(chǎn)者-消費(fèi)者問(wèn)題

P、V操作的順序有影響嗎？

P、V顛倒會(huì)出現(xiàn)死鎖，原因是先檢查空、滿再去申請(qǐng)互斥訪問(wèn)，如果申請(qǐng)了互斥訪問(wèn)，申請(qǐng)的進(jìn)程已經(jīng)占用了臨界資源，其他進(jìn)程不能讀寫，但是里面發(fā)現(xiàn)又是滿的（寫者）或者是空的（讀者），寫也寫不下去，讀也讀不到，其他進(jìn)程也不能申請(qǐng)這個(gè)臨界區(qū)，所以形成死鎖。

使用信號(hào)量的困難

■讀/開發(fā)代碼比較困難

程序員需要能運(yùn)用信號(hào)量機(jī)制

■容易出錯(cuò)（忘了一個(gè)P/V操作或者操作順序顛倒）

使用的信號(hào)量已經(jīng)被另一個(gè)線程占用

忘記釋放信號(hào)量

■不能夠處理死鎖問(wèn)題

概念：信號(hào)量的關(guān)鍵之處是它們?cè)拥貓?zhí)行。

SMP系統(tǒng)必須提供其他加鎖技術(shù)（如自旋鎖），以確保wait（）和signal（）（即P（）Ｖ（））可原子地執(zhí)行。

18.3管程

基本同步方法

管程（Moniter）

■管程是一種用于多線程互斥訪問(wèn)共享資源的程序結(jié)構(gòu)

采用面向?qū)ο蠓椒?，?jiǎn)化了線程間的同步控制

任一時(shí)刻最多只有一個(gè)線程執(zhí)行管程代碼

正在管程中的線程可臨時(shí)放棄管程的互斥訪問(wèn)，等待事件出現(xiàn)時(shí)恢復(fù)

■管程的使用

在對(duì)象/模塊中，收集相關(guān)共享數(shù)據(jù)

定義訪問(wèn)共享數(shù)據(jù)的方法

概念：管程類型提供了一組由程序員定義的、在管程內(nèi)互斥的操作。

管程的組成

■一個(gè)鎖（入口）

控制管程代碼的互斥訪問(wèn)

■0或者多個(gè)條件變量

管理共享數(shù)據(jù)的并發(fā)訪問(wèn)

只允許一個(gè)線程在管程內(nèi)部執(zhí)行，如果說(shuō)在這個(gè)內(nèi)部，沒(méi)有其它共享數(shù)據(jù)的話這時(shí)候呢就和臨界區(qū)是完全一樣的

管程特有：用來(lái)管理共享數(shù)據(jù)的并發(fā)訪問(wèn)需要這些共享資源的時(shí)候，與相應(yīng)的條件變量對(duì)應(yīng)的互斥操作才能執(zhí)行

條件變量（Condition Variable）

■條件變量是管程內(nèi)的等待機(jī)制

進(jìn)入管程的線程因資源被占用而進(jìn)入等待狀態(tài)

每個(gè)條件變量表示一種等待原因，對(duì)應(yīng)一個(gè)等待隊(duì)列

條件變量?jī)H有的操作wait和signal

■Wait()操作

將自己阻塞在等待隊(duì)列中

被signal（）喚醒一個(gè)等待者或釋放管程的互斥訪問(wèn)

■Signal()操作

將等待隊(duì)列中的一個(gè)線程喚醒

如果等待隊(duì)列為空，則等同空操作

條件變量實(shí)現(xiàn)

用管程解決生產(chǎn)者-消費(fèi)者問(wèn)題

管程條件變量的釋放處理方式

Hansen管程與Hoare管程

18.4哲學(xué)家就餐問(wèn)題

方案1（信號(hào)量）

方案2（臨界區(qū)）

方案3（保證每個(gè)哲學(xué)家拿起不同方向的叉）

18.5讀者-寫者問(wèn)題

用信號(hào)量解決讀者-寫者問(wèn)題

用管程解決讀者-寫者問(wèn)題

精髓：

17、18小結(jié)

現(xiàn)代操作系統(tǒng)的核心是多道程序設(shè)計(jì)、多處理器和分布式處理器，這些方案的基礎(chǔ)以及操作系統(tǒng)設(shè)計(jì)技術(shù)的基礎(chǔ)是并發(fā)。當(dāng)多個(gè)進(jìn)程并發(fā)執(zhí)行時(shí)，不論是在多處理器系統(tǒng)的情況下，還是單處理器多道程序系統(tǒng)中，都會(huì)產(chǎn)生沖突和合作的問(wèn)題。

并發(fā)進(jìn)程可以按多種方式進(jìn)行交互?；ハ嘀g不知道對(duì)方的進(jìn)程可能需要競(jìng)爭(zhēng)使用資源，如處理器時(shí)間或?qū)/O設(shè)備的訪問(wèn)。進(jìn)程間由于共享訪問(wèn)一個(gè)公共對(duì)象，如一塊內(nèi)存空間或一個(gè)文件，可能間接知道對(duì)方，這類交互中產(chǎn)生的重要問(wèn)題是互斥和死鎖。

互斥指的是，對(duì)一組并發(fā)進(jìn)程，一次只有一個(gè)進(jìn)程能夠訪問(wèn)給定的資源或執(zhí)行給定的功能?；コ饧夹g(shù)可以用于解決諸如資源爭(zhēng)用之類的沖突，還可以用于進(jìn)程間的同步，使得它們可以合作。后一種情況的一個(gè)例子是生產(chǎn)者/消費(fèi)者模型，一個(gè)進(jìn)程向緩沖區(qū)中放數(shù)據(jù)，另一個(gè)或更多的進(jìn)程從緩沖區(qū)中取數(shù)據(jù)。

支持互斥的第二種方法涉及使用專門的機(jī)器指令，這種方法減少了開銷，但由于使用了忙等待，效率較低。

支持互斥的另一種方法是在操作系統(tǒng)中提供相應(yīng)的功能，其中最常見的兩種技術(shù)是信號(hào)量和消息機(jī)制。信號(hào)量用于在進(jìn)程間發(fā)信號(hào)，并可以很容易地實(shí)施一個(gè)互斥協(xié)議。消息對(duì)實(shí)施互斥是很有用的，它還為進(jìn)程間的通信提供了一種有效的方法。