操作系統(tǒng)2016

1、計(jì)算機(jī)操作系統(tǒng)計(jì)算機(jī)操作系統(tǒng)第三章第三章 進(jìn)程與線程進(jìn)程與線程目目 錄錄3.1 進(jìn)程概念進(jìn)程概念3.2 進(jìn)程控制進(jìn)程控制3.3 線程線程3.4 互斥和同步互斥和同步23.1 進(jìn)程概念進(jìn)程概念3.1.1 程序的順序執(zhí)行及其特征1. 程序的順序執(zhí)行 通?？梢园岩粋€(gè)應(yīng)用程序分成若干個(gè)程序段，各程序段之間必須按照某種先后次序順序執(zhí)行，僅當(dāng)前一程序段（操作）執(zhí)行完后，才能執(zhí)行后繼程序段（操作）。 33.1.1 程序的順序執(zhí)行及其特征程序的順序執(zhí)行及其特征 1. 程序的順序執(zhí)行 63.1.1 程序的順序執(zhí)行及其特征程序的順序執(zhí)行及其特征2. 程序順序執(zhí)行的特征 （1）順序性：處理機(jī)的操作嚴(yán)格按照程序所規(guī)定

2、的順序執(zhí)行，即每一操作必須在上一操作結(jié)束之后開始。 （2）封閉性：程序是在封閉的環(huán)境下執(zhí)行的，即程序運(yùn)行時(shí)獨(dú)占整個(gè)系統(tǒng)資源，資源的狀態(tài)（除初始狀態(tài)外）只有本程序可以改變。 （3）可再現(xiàn)性：只要程序執(zhí)行時(shí)的環(huán)境和初始條件相同，當(dāng)程序重復(fù)執(zhí)行時(shí)，不論它的執(zhí)行方式如何，是連續(xù)執(zhí)行或“走走停?！钡膱?zhí)行，其結(jié)果都是相同的。73.1.2 程序的并發(fā)執(zhí)行及其特征程序的并發(fā)執(zhí)行及其特征1. 程序的并發(fā)執(zhí)行 為了提高計(jì)算機(jī)的利用率、處理速度和系統(tǒng)的吞吐量，并行處理技術(shù)和并發(fā)程序設(shè)計(jì)技術(shù)在計(jì)算機(jī)中已經(jīng)得到了廣泛應(yīng)用，成為了現(xiàn)代操作系統(tǒng)的基本特征之一。 93.1.2 程序的并發(fā)執(zhí)行及其特征程序的并發(fā)執(zhí)行及其特征 具

3、有以下四條語句的一個(gè)程序段： S1: a:=x+2; S2: b:=y+4; S3: c:=a+b; S4: d:=c+b;11圖 3.3 四條語句的前趨圖 程序兩兩并發(fā)必須滿足（P37）3.1.2 程序的并發(fā)執(zhí)行及其特征程序的并發(fā)執(zhí)行及其特征2. 程序并發(fā)執(zhí)行的特征 （1）間斷（異步）性：程序在并發(fā)執(zhí)行時(shí), 由于它們共享系統(tǒng)資源，以及為了完成同一任務(wù)而相互合作，致使這些并發(fā)程序之間形成了相互制約的關(guān)系。 （2）失去封閉性：程序在并發(fā)執(zhí)行時(shí)，多程序共享系統(tǒng)中的各種資源，因此系統(tǒng)資源的狀態(tài)將由多個(gè)程序來改變，致使程序失去了封閉性。 （3）不可再現(xiàn)性：程序在并發(fā)執(zhí)行時(shí)，由于失去了封閉性，也將導(dǎo)致其

4、失去執(zhí)行的可再現(xiàn)性。 13已有的一些定義充分反映了進(jìn)程的實(shí)質(zhì)：l進(jìn)程是程序的一次執(zhí)行；l進(jìn)程是可以和別的計(jì)算并發(fā)執(zhí)行的計(jì)算；l進(jìn)程是定義在一個(gè)數(shù)據(jù)結(jié)構(gòu)上，并能夠在其上進(jìn)行操作的一個(gè)程序；l進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。3.1.3 進(jìn)程的概念及其特征進(jìn)程的概念及其特征15 綜上，將進(jìn)程定義為： 進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。3.1.3 進(jìn)程的概念及其特征進(jìn)程的概念及其特征16 程序和進(jìn)程之間的區(qū)別與聯(lián)系：程序是完成特定任務(wù)的一組指令的集合，可以永久保存，具有靜態(tài)性；進(jìn)程有生命周期，是程序在某一數(shù)據(jù)結(jié)構(gòu)上的一次執(zhí)

5、行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位，具有動(dòng)態(tài)性；一個(gè)進(jìn)程可以包含多個(gè)程序，一個(gè)程序也可以被多個(gè)進(jìn)程執(zhí)行。3.1.3 進(jìn)程的概念及其特征進(jìn)程的概念及其特征181. 兩狀態(tài)模型包含運(yùn)行態(tài)（Running）和非運(yùn)行態(tài)（Not running）兩種進(jìn)程狀態(tài)l創(chuàng)建了一個(gè)新進(jìn)程之后，它會(huì)以非運(yùn)行態(tài)加入到系統(tǒng)中，等待操作系統(tǒng)為其分派處理器l當(dāng)前處于運(yùn)行態(tài)的進(jìn)程會(huì)不時(shí)地中斷，由系統(tǒng)中的分派器選擇處于非運(yùn)行狀中的某一個(gè)進(jìn)程運(yùn)行3.1.4 進(jìn)程狀態(tài)進(jìn)程狀態(tài)19（a） 狀態(tài)變遷圖3.1.4 進(jìn)程狀態(tài)進(jìn)程狀態(tài)20（b） 排隊(duì)圖3.1.4 進(jìn)程狀態(tài)進(jìn)程狀態(tài)212.五狀態(tài)模型包括就緒態(tài)（Ready）、運(yùn)行態(tài)（Ru

6、nning）、阻塞態(tài)（Blocked）、新建態(tài)（New）和終止態(tài)（Terminate） 進(jìn)程狀態(tài)描述： （1）新建態(tài)：剛剛創(chuàng)建的新進(jìn)程，通常是指進(jìn)程控制塊已經(jīng)創(chuàng)建，但還沒有加載到系統(tǒng)內(nèi)存中的進(jìn)程 （2）就緒態(tài)：進(jìn)程等待系統(tǒng)為其分派處理器，而此時(shí)處理器被其它進(jìn)程占據(jù)，所以該狀態(tài)進(jìn)程不能執(zhí)行但已經(jīng)具備了除處理器之外的進(jìn)程執(zhí)行所需要的所有條件。3.1.4 進(jìn)程狀態(tài)進(jìn)程狀態(tài)22 （3）運(yùn)行態(tài)：進(jìn)程已獲得所需資源并占據(jù)處理器，處理器正在執(zhí)行該進(jìn)程 （4）阻塞態(tài)：也稱為等待態(tài)、掛起態(tài)或睡眠態(tài)，進(jìn)程在等待某個(gè)事情的發(fā)生而暫時(shí)不能運(yùn)行，例如等待某個(gè)I/O操作的完成 （5）終止態(tài)：進(jìn)程或者因?yàn)閳?zhí)行結(jié)束或者因?yàn)楸?/p>

7、撤銷而從可執(zhí)行進(jìn)程組中退出3.1.4 進(jìn)程狀態(tài)進(jìn)程狀態(tài)23圖圖3.5 五狀態(tài)模型（五狀態(tài)模型（P40）3.1.4 進(jìn)程狀態(tài)進(jìn)程狀態(tài)24 對(duì)于內(nèi)存中的多個(gè)進(jìn)程，處理器依次選中運(yùn)行，當(dāng)一個(gè)進(jìn)程正在等待 I/O 事件發(fā)生時(shí)，處理器轉(zhuǎn)移到另一個(gè)進(jìn)程。但是處理器的速度比 I/O 要快很多，有可能內(nèi)存中所有進(jìn)程都在等待 I/O 事件的完成，導(dǎo)致處理器處于空閑狀態(tài)。 一種可行的解決問題的辦法是引入掛起的概念。3.1.4 進(jìn)程狀態(tài)進(jìn)程狀態(tài)25圖圖3.6 引入掛起的進(jìn)程狀態(tài)轉(zhuǎn)換模型引入掛起的進(jìn)程狀態(tài)轉(zhuǎn)換模型3.1.4 進(jìn)程狀態(tài)進(jìn)程狀態(tài)27l進(jìn)程控制塊（Process control block, PCB）是操作

8、系統(tǒng)用來記錄進(jìn)程狀態(tài)和相關(guān)信息，控制進(jìn)程運(yùn)行的數(shù)據(jù)結(jié)構(gòu)，是進(jìn)程的唯一標(biāo)識(shí)符。l在PCB中，主要包含如下的信息：3.1.5 進(jìn)程控制塊進(jìn)程控制塊28進(jìn)程標(biāo)識(shí)符進(jìn)程狀態(tài)調(diào)度信息程序計(jì)數(shù)器上下文數(shù)據(jù)內(nèi)存指針I(yè)/O 狀態(tài)信息l進(jìn)程控制是進(jìn)程管理中最基本的功能進(jìn)程控制是進(jìn)程管理中最基本的功能l在操作系統(tǒng)中，不同功能都是通過執(zhí)行各種原語（Primitive）操作實(shí)現(xiàn)l原語是由若干條指令構(gòu)成、可完成特定功能的程序段；它是不可分割的操作單元，在執(zhí)行過是不可分割的操作單元，在執(zhí)行過程中不會(huì)被中斷程中不會(huì)被中斷！3.2 進(jìn)程控制進(jìn)程控制30l引起進(jìn)程創(chuàng)建的事件： （1）批處理作業(yè) （2）用戶登錄 （3）提供服務(wù)

9、（4）進(jìn)程派生3.2.1 進(jìn)程創(chuàng)建進(jìn)程創(chuàng)建31l創(chuàng)建一個(gè)新進(jìn)程的具體步驟： （1）系統(tǒng)為新建進(jìn)程申請(qǐng)一個(gè)空白的進(jìn)程控制塊，獲得一個(gè)唯一的進(jìn)程標(biāo)識(shí)符。 （2）系統(tǒng)為新建進(jìn)程分配運(yùn)行所需的資源，包括：內(nèi)存、處理器時(shí)間、I/O設(shè)備等。 （3）進(jìn)程控制塊（PCB）初始化。 （4）設(shè)置鏈接，如果就緒隊(duì)列允許新進(jìn)程插入，則將新進(jìn)程插入就緒隊(duì)列。3.2.1 進(jìn)程創(chuàng)建進(jìn)程創(chuàng)建32l引起進(jìn)程終止的事件： （1） 正常完成 （2） 運(yùn)行超時(shí) （3） 等待超時(shí) （4） 內(nèi)存不足 （5） 越界錯(cuò)誤 （6） 保護(hù)錯(cuò)誤 （7） 算術(shù)錯(cuò)誤3.2.2 進(jìn)程終止進(jìn)程終止33（8） I/O錯(cuò)誤（9） 無效指令（10）特權(quán)指令（1

10、1）操作員或操作系統(tǒng)干涉（12）父進(jìn)程請(qǐng)求（13）父進(jìn)程終止l終止原語的具體步驟： （1）根據(jù)需要終止進(jìn)程的進(jìn)程標(biāo)識(shí)符，從PCB集合中查找對(duì)應(yīng)進(jìn)程，從中讀出該進(jìn)程的狀態(tài)。 （2）若被終止進(jìn)程正處在執(zhí)行狀態(tài)，則應(yīng)立即終止該進(jìn)程的執(zhí)行，并設(shè)置相應(yīng)的調(diào)度信息，用于指示該進(jìn)程被終止后應(yīng)重新進(jìn)行調(diào)度。 （3）將被終止進(jìn)程所擁有的所有資源歸還給其父進(jìn)程，或者歸還給系統(tǒng)。 （4）若被終止進(jìn)程還擁有子孫進(jìn)程，則將其所有子孫進(jìn)程一并終止。 （5）歸還PCB所占據(jù)的空間。3.2.2 進(jìn)程終止進(jìn)程終止341. 進(jìn)程阻塞l進(jìn)程阻塞是指進(jìn)程在執(zhí)行過程中因等待某個(gè)事件的發(fā)生或等待某個(gè)操作的完成而不得不讓出處理機(jī)，是進(jìn)程主

11、動(dòng)、自愿的行為進(jìn)程主動(dòng)、自愿的行為。l引起進(jìn)程阻塞的主要事件有： （1）請(qǐng)求系統(tǒng)服務(wù) （2）啟動(dòng)某種操作 （3）新數(shù)據(jù)尚未到達(dá) （4）無新工作可做3.2.3 進(jìn)程阻塞和喚醒進(jìn)程阻塞和喚醒35l阻塞原語（Block primitive）的具體步驟： （1）正在執(zhí)行的進(jìn)程立即終止執(zhí)行，把PCB中的進(jìn)程狀態(tài)由執(zhí)行改為阻塞，并將處理機(jī)狀態(tài)寫入PCB中。 （2）將PCB插入阻塞隊(duì)列中，等到事件的發(fā)生或操作的完成。 （3）系統(tǒng)將處理機(jī)重新分派給另一就緒進(jìn)程，按照新進(jìn)程的處理機(jī)狀態(tài)更新處理機(jī)環(huán)境，就緒進(jìn)程開始執(zhí)行。 （4）當(dāng)被阻塞進(jìn)程等待的事件發(fā)生或者等待的操作完成時(shí)，則操作系統(tǒng)會(huì)通過喚醒原語將等待該事件的

12、進(jìn)程喚醒。3.2.3 進(jìn)程阻塞和喚醒進(jìn)程阻塞和喚醒362. 進(jìn)程喚醒l當(dāng)被阻塞進(jìn)程等待的事件發(fā)生（如等待的 I/O 操作已完成、或等待的操作完成時(shí)），則操作系統(tǒng)會(huì)通過喚醒原語將等待該事件的進(jìn)程喚醒。l喚醒原語（Wakeup primitive）的具體步驟： （1）根據(jù)進(jìn)程標(biāo)識(shí)符從等待該事件的阻塞隊(duì)列中找到需要喚醒的進(jìn)程PCB。 （2）將PCB中的進(jìn)程狀態(tài)阻塞改成就緒，并將該進(jìn)程插入到就緒隊(duì)列中。3.2.3 進(jìn)程阻塞和喚醒進(jìn)程阻塞和喚醒371. 進(jìn)程掛起l當(dāng)系統(tǒng)中出現(xiàn)了引起掛起的事件，如內(nèi)存資源不足時(shí)，操作系統(tǒng)將利用掛起原語將處于阻塞狀態(tài)的進(jìn)程掛起。l掛起原語（Suspend primitive

13、）的具體步驟： （1）根據(jù)進(jìn)程標(biāo)示符，在PCB集合中找到需要掛起的進(jìn)程。 （2）檢查掛起進(jìn)程的狀態(tài)。3.2.4 進(jìn)程掛起和激活進(jìn)程掛起和激活382. 進(jìn)程激活l激活，對(duì)應(yīng)于掛起，是讓被掛起的進(jìn)程重新活躍起來，也就是把進(jìn)程從外存調(diào)入到內(nèi)存中。當(dāng)系統(tǒng)中出現(xiàn)了引起激活的事件時(shí)，操作系統(tǒng)會(huì)利用激活原語將掛起進(jìn)程激活。l激活原語（Active primitive）的具體步驟： （1）根據(jù)進(jìn)程標(biāo)示符，在PCB集合中找到需要激活的進(jìn)程。 （2）檢查激活進(jìn)程的狀態(tài)。3.2.4 進(jìn)程掛起和激活進(jìn)程掛起和激活39l早期的計(jì)算機(jī)操作系統(tǒng)中，進(jìn)程既是資源分配的基本單位，又是調(diào)度的基本單位l操作系統(tǒng)發(fā)展至今，進(jìn)程在調(diào)度

14、中會(huì)存在許多問題，增加了調(diào)度的難度和開銷l現(xiàn)代操作系統(tǒng)很重要的一方面是進(jìn)程的并發(fā)執(zhí)行，然而進(jìn)程的并發(fā)執(zhí)行使得進(jìn)程調(diào)度的開銷日益增大，系統(tǒng)效率明顯降低3.3 線線 程程40l進(jìn)程包含兩方面特點(diǎn)： （1）資源所有權(quán)：進(jìn)程是一個(gè)可擁有資源的獨(dú)立單位。 （2）調(diào)度：進(jìn)程同時(shí)又是一個(gè)可獨(dú)立調(diào)度和分派的基本單位。一個(gè)進(jìn)程通過一個(gè)或多個(gè)程序的一條執(zhí)行路徑執(zhí)行。執(zhí)行中可能與其它進(jìn)程的執(zhí)行過程交替進(jìn)行，所以，一個(gè)進(jìn)程具有一個(gè)執(zhí)行狀態(tài)和一個(gè)分派的優(yōu)先級(jí)，同時(shí)又是一個(gè)能被操作系統(tǒng)調(diào)度和分派的實(shí)體。3.3.1 線程簡介線程簡介41l在操作系統(tǒng)中引入進(jìn)程，是為了使多個(gè)程序能并發(fā)執(zhí)行，以提高資源利用率和系統(tǒng)吞吐量。l在操

15、作系統(tǒng)中再引入線程，則是為了減少程序在并發(fā)執(zhí)行時(shí)所付出的時(shí)空開銷，使操作系統(tǒng)具有更好的并發(fā)性。l通常把調(diào)度和分派的基本單位稱做線程線程或輕量級(jí)輕量級(jí)進(jìn)程進(jìn)程（Light weight process, LWP），而把資源分配的基本單位稱做進(jìn)程進(jìn)程或者任務(wù)任務(wù)。3.3.1 線程簡介線程簡介42l進(jìn)程在任一時(shí)刻只有一個(gè)執(zhí)行控制流，通常將這種結(jié)構(gòu)的進(jìn)程稱為單線程進(jìn)程（Single threaded process）l多線程進(jìn)程（Multiple threaded process）同一進(jìn)程中設(shè)計(jì)出多條控制流，并且滿足： （1）多控制流之間可以并行執(zhí)行； （2）多控制流切換不需通過進(jìn)程調(diào)度； （3）多控

16、制流之間可以通過內(nèi)存直接通信聯(lián)系，從而降低通信開銷。3.3.2 多線程多線程43圖3.7 進(jìn)程和線程3.3.2 多線程多線程442.多線程環(huán)境下的進(jìn)程和線程 （1）多線程環(huán)境下的進(jìn)程 在多線程環(huán)境中，進(jìn)程被定義為資源分配的基本單位，與進(jìn)程相關(guān)的有：存放進(jìn)程映象的虛擬地址空間受保護(hù)地對(duì)處理器、其他進(jìn)程、文件和I/O資源的訪問3.3.2 多線程多線程45（2）多線程環(huán)境下的線程 一個(gè)進(jìn)程內(nèi)包含一個(gè)或者多個(gè)線程，每個(gè)線程都包含：線程執(zhí)行狀態(tài)當(dāng)線程處于非運(yùn)行狀態(tài)時(shí)，有一個(gè)受保護(hù)的線程上下文，用于存儲(chǔ)現(xiàn)場信息一個(gè)執(zhí)行堆棧容納每個(gè)線程的局部變量的存儲(chǔ)空間與進(jìn)程內(nèi)其它線程共享訪問進(jìn)程的內(nèi)存空間和資源3.3.

17、2 多線程多線程46圖3.8 單線程和多線程環(huán)境下的進(jìn)程模型3.3.2 多線程多線程47l線程的主要特性： （1）并發(fā)性 （2）共享性 （3）動(dòng)態(tài)性 （4）結(jié)構(gòu)性3.線程狀態(tài)l線程的關(guān)鍵狀態(tài)有：運(yùn)行態(tài)、就緒態(tài)、阻塞態(tài)l與線程狀態(tài)轉(zhuǎn)換相關(guān)的操作：派生、阻塞、解除阻塞、結(jié)束3.3.2 多線程多線程481.線程實(shí)現(xiàn)（1）用戶級(jí)線程（User level thread, ULT） 線程管理的所有工作都由應(yīng)用程序完成，內(nèi)核意識(shí)不到線程的存在。3.3.3 線程實(shí)現(xiàn)與線程模型線程實(shí)現(xiàn)與線程模型49 用戶級(jí)線程方式優(yōu)點(diǎn)：因?yàn)樗芯€程的管理數(shù)據(jù)結(jié)構(gòu)都在該進(jìn)程的用戶空間中，因此線程切換不需要轉(zhuǎn)換到內(nèi)核空間，從而節(jié)

18、省了模式切換的開銷。調(diào)度算法可以是基于不同進(jìn)程量身定做。不同進(jìn)程可以根據(jù)自身需要，為自己量身定做適合自身的調(diào)度算法完成對(duì)線程進(jìn)行管理和調(diào)度。用戶級(jí)線程的實(shí)現(xiàn)與操作系統(tǒng)平臺(tái)無關(guān)，即可以在任何操作系統(tǒng)中運(yùn)行。3.3.3 線程實(shí)現(xiàn)與線程模型線程實(shí)現(xiàn)與線程模型50 用戶級(jí)線程方式缺點(diǎn)：許多系統(tǒng)調(diào)用會(huì)引起阻塞，當(dāng)用戶級(jí)線程執(zhí)行一個(gè)系統(tǒng)調(diào)用時(shí)，不僅該線程會(huì)被阻塞，而且該線程所在進(jìn)程內(nèi)的所有線程都會(huì)被阻塞。在純粹的用戶級(jí)線程實(shí)現(xiàn)方式中，多線程應(yīng)用不能利用多處理機(jī)技術(shù)。內(nèi)核一次只為每個(gè)進(jìn)程分配一個(gè)處理器，即進(jìn)程每次只有一個(gè)線程處于運(yùn)行狀態(tài)，其它線程此時(shí)只能等待。3.3.3 線程實(shí)現(xiàn)與線程模型線程實(shí)現(xiàn)與線程模型

19、51（2）內(nèi)核級(jí)線程（Kernel level thread, KLT） 線程管理的所有工作都是由內(nèi)核完成，應(yīng)用程序并沒有參與其中。即：無論是用戶進(jìn)程中的線程，還是系統(tǒng)進(jìn)程中的線程，他們的創(chuàng)建、終止和切換等也是依靠內(nèi)核，在內(nèi)核空間實(shí)現(xiàn)的。3.3.3 線程實(shí)現(xiàn)與線程模型線程實(shí)現(xiàn)與線程模型52內(nèi)核級(jí)線程方式優(yōu)點(diǎn)：內(nèi)核能夠同時(shí)為同一進(jìn)程中的多個(gè)線程分配多個(gè)處理器，即能讓多個(gè)線程并行執(zhí)行。如果進(jìn)程中的一個(gè)線程被阻塞了，內(nèi)核可以為該進(jìn)程中的其它線程分派處理器資源使其運(yùn)行，當(dāng)然也可以調(diào)度其它進(jìn)程中的線程運(yùn)行。內(nèi)核本身也可以采用多線程技術(shù)，從而提高系統(tǒng)的執(zhí)行速度和效率。3.3.3 線程實(shí)現(xiàn)與線程模型線程實(shí)現(xiàn)

20、與線程模型53 內(nèi)核級(jí)線程方式缺點(diǎn)： 因?yàn)榫€程調(diào)度和管理是在內(nèi)核實(shí)現(xiàn)，而用戶進(jìn)程的線程卻是在用戶態(tài)下運(yùn)行。因此在進(jìn)行線程與同一進(jìn)程內(nèi)其它線程切換時(shí)，需要從用戶態(tài)轉(zhuǎn)到內(nèi)核態(tài)進(jìn)行，從而導(dǎo)致較大的系統(tǒng)開銷。3.3.3 線程實(shí)現(xiàn)與線程模型線程實(shí)現(xiàn)與線程模型54（3）組合方式 同一個(gè)進(jìn)程內(nèi)的多個(gè)線程可以同時(shí)在多處理器上并行執(zhí)行，而且一個(gè)線程被阻塞時(shí)，同一進(jìn)程內(nèi)的其它線程可以調(diào)度運(yùn)行，并不需要阻塞整個(gè)進(jìn)程。組合方式多線程機(jī)制能夠結(jié)合 KLT 和 ULT 兩者的優(yōu)點(diǎn)，并克服了各自的不足。3.3.3 線程實(shí)現(xiàn)與線程模型線程實(shí)現(xiàn)與線程模型55圖3.9 線程實(shí)現(xiàn)方式3.3.3 線程實(shí)現(xiàn)與線程模型線程實(shí)現(xiàn)與線程模型

21、562.線程模型（1）多對(duì)一模型3.3.3 線程實(shí)現(xiàn)與線程模型線程實(shí)現(xiàn)與線程模型57圖3.10 多對(duì)一模型（2）一對(duì)一模型3.3.3 線程實(shí)現(xiàn)與線程模型線程實(shí)現(xiàn)與線程模型58圖3.11 一對(duì)一模型（3）多對(duì)多模型3.3.3 線程實(shí)現(xiàn)與線程模型線程實(shí)現(xiàn)與線程模型59圖3.12 多對(duì)多模型l操作系統(tǒng)設(shè)計(jì)中的核心問題是關(guān)于進(jìn)程和線程的管理，例如：采用多道程序設(shè)計(jì)技術(shù)管理單處理器系統(tǒng)中的多個(gè)進(jìn)程采用多處理技術(shù)管理多處理器系統(tǒng)中的多個(gè)進(jìn)程采用分布式處理技術(shù)管理多臺(tái)分布式計(jì)算機(jī)系統(tǒng)中的多個(gè)進(jìn)程l并發(fā)是上述管理問題實(shí)現(xiàn)的基礎(chǔ)，也是操作系統(tǒng)設(shè)計(jì)的核心3.4 互斥和同步互斥和同步60l并發(fā)涉及的術(shù)語：（1）臨界

22、區(qū)臨界區(qū)（Critical section）（2）競爭（Competition）（3）同步同步（Synchronization）（4）互斥（Mutual exclusion）（5）死鎖死鎖（Deadlock）（6）饑餓（Starvation）3.4.1 并發(fā)原理并發(fā)原理613.4.1 并發(fā)原理并發(fā)原理62l2.臨界區(qū)和臨界資源l臨界資源臨界資源（Critical resource），多個(gè)進(jìn)程間采取互斥的方式實(shí)現(xiàn)對(duì)臨界資源的共享訪問l使用臨界資源的程序代碼稱為臨界區(qū)臨界區(qū)l進(jìn)程間競爭資源產(chǎn)生如下的幾個(gè)控制問題 （1）互斥 （2）死鎖 （3）饑餓3.4.1 并發(fā)原理并發(fā)原理63多個(gè)進(jìn)程共享臨界區(qū)，

23、需遵循如下的調(diào)度原則：3.4.1 并發(fā)原理并發(fā)原理651.關(guān)中斷關(guān)中斷：使進(jìn)程在臨界區(qū)時(shí)不響應(yīng)中斷2.TestAndSet指令：指令：指令描述如下：boolean TestAndSet(boolean *lock) boolean temp = *lock; *lock = TRUE; return temp;3.4.2 硬件同步硬件同步66lTestAndSet指令實(shí)現(xiàn)互斥的示例如下：do while(TestAndSet(&lock) ;/ do nothing / critical section lock = FALSE; / remainder sectionwhile(TR

24、UE);3.4.2 硬件同步硬件同步673.Swap指令：指令：為對(duì)換指令，定義如下：void Swap(boolean *a, boolean *b) Boolean temp = *a; *a = *b; *b = temp;3.4.2 硬件同步硬件同步68l使用Swap指令實(shí)現(xiàn)互斥的示例如下：do data = TRUE; while(data = TRUE) Swap(&lock, &data); / critical section lock = FALSE; / reminder section while(TRUE);3.4.2 硬件同步硬件同步693.4.3 信

25、號(hào)量機(jī)制信號(hào)量機(jī)制1.整型信號(hào)量 Dijkstra把整型信號(hào)量 s 定義成一個(gè)用于表示資源數(shù)目的整型變量。進(jìn)程通過信號(hào)量傳送信號(hào)，利用兩個(gè)特殊的操作發(fā)送和接收信號(hào)。 signal(s)：通過信號(hào)量：通過信號(hào)量 s 傳送信號(hào)傳送信號(hào) wait(s)：通過信號(hào)量：通過信號(hào)量 s 接收信號(hào)接收信號(hào) 如果相應(yīng)的信號(hào)仍然沒有發(fā)送則進(jìn)程被掛起，直到發(fā)送完為止。3.4.3 信號(hào)量機(jī)制信號(hào)量機(jī)制71void wait(s)void wait(s) while(s=0) while(s=0)； /do nothing /do nothing s-; s-; 3.4.3 信號(hào)量機(jī)制信號(hào)量機(jī)制72void sign

26、al(s)void signal(s) s+; s+; 2.記錄型信號(hào)量l整型信號(hào)量機(jī)制沒有滿足讓權(quán)等待的原則，可能使進(jìn)程處于饑餓的忙等狀態(tài)。l假設(shè) s 為一個(gè)記錄型數(shù)據(jù)結(jié)構(gòu)，其中一個(gè)分量為整形數(shù)整形數(shù)value，另一個(gè)為信號(hào)量隊(duì)列信號(hào)量隊(duì)列queue。lvalue通常是一個(gè)具有非負(fù)初值的整型變量，queue 表示一個(gè)初始時(shí)為空的進(jìn)程隊(duì)列，當(dāng)某進(jìn)程必須等待信號(hào)量時(shí)，就加入到該隊(duì)列中。3.4.3 信號(hào)量機(jī)制信號(hào)量機(jī)制73lwait 和 signal 操作定義相應(yīng)為： wait(s)：信號(hào)量 s 減 l，若結(jié)果小于0，則調(diào)用wait(s)的進(jìn)程被設(shè)置成等待信號(hào)量 s 的狀態(tài)。 signal(s)：

27、將信號(hào)量 s 加 1，若結(jié)果不大于0，則釋放一個(gè)等待信號(hào)量s的進(jìn)程。3.4.3 信號(hào)量機(jī)制信號(hào)量機(jī)制74（1）若 s.value 值為正，則該值表示在對(duì)進(jìn)程進(jìn)行阻塞之前對(duì)信號(hào)量 s 可以實(shí)施的wait( )操作個(gè)數(shù)，即：系統(tǒng)中某類資源實(shí)際可用數(shù)目系統(tǒng)中某類資源實(shí)際可用數(shù)目；（2）若 s.value 值為負(fù)，則它的絕對(duì)值表示阻塞隊(duì)列阻塞隊(duì)列s.queue 中等待的進(jìn)程個(gè)數(shù)中等待的進(jìn)程個(gè)數(shù)；（3）每次wait()操作，表示進(jìn)程請(qǐng)求一個(gè)單位的該類請(qǐng)求一個(gè)單位的該類資源資源，使系統(tǒng)中可供分配的該類資源數(shù)減少一；每次signal()操作，表示執(zhí)行進(jìn)程釋放一個(gè)單位該資源釋放一個(gè)單位該資源，使系統(tǒng)中可供分配

28、的該類資源數(shù)增加一。3.4.3 信號(hào)量機(jī)制信號(hào)量機(jī)制753.二元信號(hào)量（P56）l假設(shè) s 為一個(gè)記錄型數(shù)據(jù)結(jié)構(gòu)，其中一個(gè)分量為 value，它僅能取值 0 和 1，另一個(gè)分量為信號(hào)量隊(duì)列 queue。l一個(gè)二元信號(hào)量的值只能是 0 或者 13.4.3 信號(hào)量機(jī)制信號(hào)量機(jī)制761.1.生產(chǎn)者生產(chǎn)者- -消費(fèi)者問題消費(fèi)者問題（1）問題描述 假設(shè)有n個(gè)生產(chǎn)者和m個(gè)消費(fèi)者，連接在一個(gè)有 k 個(gè)公用緩沖區(qū)的有界緩沖上，pi 表示生產(chǎn)者進(jìn)程，cj 表示消費(fèi)者進(jìn)程。應(yīng)滿足應(yīng)滿足：只要緩沖區(qū)未滿，生產(chǎn)者pi 即可將生產(chǎn)的產(chǎn)品放 入空閑緩沖區(qū)中；否則pi 阻塞只要緩沖區(qū)不空，消費(fèi)者cj 就可從緩沖區(qū)從取走并消

29、耗產(chǎn)品；否則cj 阻塞3.4.5 經(jīng)典同步問題經(jīng)典同步問題80u注意：單一過程中控制對(duì)資源的互斥訪問的wait(mutex)和signal(mutex)的操作必須成對(duì)出現(xiàn)。對(duì)記錄資源的信號(hào)量empty和full的wait和signal操作也必須成對(duì)出現(xiàn)，但允許它們根據(jù)邏輯需要出現(xiàn)在不同的過程中。為避免死鎖，控制互斥訪問和記錄資源的信號(hào)量的wait操作順序不能亂，必須先執(zhí)行wait(empty)，再執(zhí)行wait(mutex)。3.4.5 經(jīng)典同步問題經(jīng)典同步問題872.2.讀者讀者- -寫者問題寫者問題（1）問題描述 有一個(gè)多進(jìn)程共享的數(shù)據(jù)區(qū)，把只要讀該數(shù)據(jù)區(qū)的記為Reader進(jìn)程（讀者），把只

30、要往數(shù)據(jù)區(qū)內(nèi)寫數(shù)據(jù)的記為Writer進(jìn)程（寫者）。滿足滿足：允許多個(gè)讀者同時(shí)執(zhí)行讀操作一次只能有一個(gè)寫者執(zhí)行寫操作如果一個(gè)寫者在執(zhí)行寫操作，則其它任何讀者都如果一個(gè)寫者在執(zhí)行寫操作，則其它任何讀者都不能執(zhí)行讀操作不能執(zhí)行讀操作883.3.哲學(xué)家就餐問題哲學(xué)家就餐問題3.4.5 經(jīng)典同步問題經(jīng)典同步問題93（1）問題描述 有五位哲學(xué)家，用一生來思考和吃飯。他們圍坐在一張圓桌旁，桌子中央有一大碗米飯，桌上還有五個(gè)碗和五只筷子，他們的生活方式是交替地進(jìn)行思考和進(jìn)餐。當(dāng)某位哲學(xué)家進(jìn)行思考時(shí)，他不與其它哲學(xué)家交互。當(dāng)他感覺到饑餓時(shí)，便試圖拿起與其左右最靠近的筷子。一個(gè)哲學(xué)家每次只能拿起一只筷子，且他不能

31、從其他哲學(xué)家手里拿筷子只有在他拿到兩只筷子時(shí)才能進(jìn)餐3.4.5 經(jīng)典同步問題經(jīng)典同步問題94 （2）用信號(hào)量解決哲學(xué)家就餐問題u每一只筷子的使用都必須是互斥的，在某一時(shí)刻只允許一個(gè)哲學(xué)家使用，它是臨界資源u利用一個(gè)信號(hào)量表示一只筷子，五只筷子的信號(hào)量數(shù)組定義為：u利用變量 i 區(qū)分不同的哲學(xué)家及筷子：3.4.5 經(jīng)典同步問題經(jīng)典同步問題951. 管程的定義 管程是由一個(gè)或多個(gè)過程、一個(gè)初始化序管程是由一個(gè)或多個(gè)過程、一個(gè)初始化序列和數(shù)據(jù)組成的軟件模塊列和數(shù)據(jù)組成的軟件模塊，是一種程序設(shè)計(jì)語言結(jié)構(gòu)成分，具有和信號(hào)量同等的表達(dá)能力。 進(jìn)程可以通過調(diào)用管程實(shí)現(xiàn)對(duì)資源的請(qǐng)求和釋放。3.4.4 管程管程

32、100 管程對(duì)分散在各進(jìn)程中的臨界區(qū)集中進(jìn)臨界區(qū)集中進(jìn)行管理行管理，并將系統(tǒng)中的共享資源用數(shù)據(jù)結(jié)構(gòu)抽象地表示出來。 管程中的共享變量每次只能被一個(gè)進(jìn)程訪問，從而可以提供互斥機(jī)制。l管程的主要特點(diǎn)：共享性共享性：一個(gè)進(jìn)程通過調(diào)用管程的一個(gè)過程進(jìn)入管程，管程中的過程可被所有要調(diào)用它的進(jìn)程所共享。安全性安全性：管程的局部數(shù)據(jù)變量只能被管程的過程訪問，任何其它外部過程都不能訪問；一個(gè)管程的過程也不能訪問任何非局部于它的變量?；コ庑曰コ庑裕涸谌我粫r(shí)刻，只能有一個(gè)進(jìn)程進(jìn)入管程執(zhí)行，調(diào)用管程的其它任何進(jìn)程都將被阻塞，只能等待直到當(dāng)前訪問進(jìn)程退出管程。3.4.4 管程管程1022.管程的條件變量l在管程的調(diào)用

33、過程中可能存在如下現(xiàn)象：一個(gè)進(jìn)程調(diào)用了管程，之后在管程中處于阻塞或掛起狀態(tài)，只有當(dāng)進(jìn)程解除阻塞或掛起的條件滿足后才能恢復(fù)執(zhí)行。l引入條件變量條件變量（Condition variables）的同步機(jī)制，及其對(duì)應(yīng)的原語操作cwait 和 csignal。3.4.4 管程管程103 條件變量也是一種信號(hào)量，但它不同于信號(hào)量機(jī)制中的計(jì)數(shù)信號(hào)量。 由于一個(gè)進(jìn)程被阻塞或掛起的條件或原因一般存在多個(gè)，因此也在管程中設(shè)置多個(gè)條件變量以便完成對(duì)進(jìn)程的描述控制。 條件變量的訪問只在管程中進(jìn)行，因此條件變量的訪問只在管程中進(jìn)行，因此對(duì)其的同步原語操作可以用來控制進(jìn)入管程對(duì)其的同步原語操作可以用來控制進(jìn)入管程的進(jìn)程的進(jìn)程。lcwait 和和 csignal 操作的意義：操作的意義： （1）cwait(c) 操作操作：正在調(diào)用管程的進(jìn)程因條件 c