Chapter-02(進程與線程)

1、1主要內容第2章 進程與線程2.1 進程2.2 線程2.3 進程間通信2.4 調度2.5 經典的IPC問題22.1 進程（補充1） 程序 指令或語句序列，體現了某種算法所有程序是順序的 順序程序 計算機系統中只有一個程序在運行，該程序獨占系統中的所有資源，其執(zhí)行不受外界影響 特征：順序性、封閉性、可再現性32.1 進程（補充2） 多道程序執(zhí)行系統中程序的執(zhí)行：多道程序執(zhí)行系統中程序的執(zhí)行：同時處理多個具有獨立功能的程序，應具有以下特點：同時處理多個具有獨立功能的程序，應具有以下特點：獨立性：多個程序邏輯獨立，并可獨立運行獨立性：多個程序邏輯獨立，并可獨立運行隨機性：多用戶環(huán)境下程序的運行是隨機

2、的隨機性：多用戶環(huán)境下程序的運行是隨機的資源共享：資源共享： 并發(fā)執(zhí)行的程序：并發(fā)執(zhí)行的程序：并發(fā)：兩個或多個事件在并發(fā)：兩個或多個事件在同一個時間間隔同一個時間間隔之內同時發(fā)生之內同時發(fā)生并行：兩個或多個事件在并行：兩個或多個事件在同一個時刻同一個時刻同時發(fā)生同時發(fā)生特點：隨機性，失去了程序順序執(zhí)行所具有的封閉性和可再現性特點：隨機性，失去了程序順序執(zhí)行所具有的封閉性和可再現性4例：有棧例：有棧S, top為棧頂指針，為棧頂指針，getaddr(top)從棧中取內存數據塊從棧中取內存數據塊地址，地址，reladdr(bld)將內存數據塊地址將內存數據塊地址blk放入放入S中中Procedur

3、e getaddr(top) begin local r r - (top) top - top-1 return(r) endProcedure reladdr(blk) begin top - top+1 (top) - blk endabeftop r=?52.1.2 進程的定義：進程的定義： 定義：定義：A Procss is just an executing program (Include : PC, R ,variables etc.)或：可以與其他程序并發(fā)執(zhí)行的程序的一次執(zhí)行，是系統或：可以與其他程序并發(fā)執(zhí)行的程序的一次執(zhí)行，是系統資源分配的基本單位資源分配的基本單位 特征：

4、特征： 動態(tài)動態(tài)并發(fā)并發(fā)獨立獨立異步異步結構結構6 進程與程序的區(qū)別及聯系：進程與程序的區(qū)別及聯系：進程是動態(tài)的，而程序是靜態(tài)的進程是動態(tài)的，而程序是靜態(tài)的進程可以并發(fā)，而程序則沒有進程可以并發(fā)，而程序則沒有進程是資源競爭的基本單位進程是資源競爭的基本單位聯系：聯系：一個程序可以生成多個不同的進程一個程序可以生成多個不同的進程 進程的層次結構：（進程樹）進程的層次結構：（進程樹）系統中除根進程外，每個進程都有且只有一個父進程系統中除根進程外，每個進程都有且只有一個父進程每個子進程均由它的父進程創(chuàng)建每個子進程均由它的父進程創(chuàng)建一個父進程可以有多個子進程一個父進程可以有多個子進程72.1 進程2.

5、1.1 進程模型 含有4道程序的多道程序 4個獨立的順序進程的概念模型 在任意時刻僅有一個程序是活躍的82.1.2 創(chuàng)建進程4種主要事件導致進程的創(chuàng)建1. 系統初始化2. 執(zhí)行了正在運行的進程所調用的進程創(chuàng)建系統調用3. 用戶請求創(chuàng)建一個新進程4. 一個批處理作業(yè)的初始化92.1.3 進程的終止引起進程終止的條件：1. 正常退出 (自愿的)2. 錯誤退出 (自愿地)3. 嚴重錯誤 (非自愿地)4. 被其他進程殺死 (非自愿地)102.1.4 進程的層次結構 父進程創(chuàng)建一個子進程，子進程可以創(chuàng)建屬于自己的更多進程 Unix中所有子女和后裔共同組成一個進程組 UNIX 叫 “進程組 Windows

6、 沒有進程層次的概念 所有的進程都是地位相同的112.1.5 進程的狀態(tài) (1) 進程的狀態(tài) running（運行態(tài)） blocked(阻塞態(tài)) ready（就緒態(tài)） 上圖顯示出各狀態(tài)之間的轉換1.進程為等待輸入而阻塞進程為等待輸入而阻塞2.調度程序選擇另一個進程調度程序選擇另一個進程3.調度程序選擇這個進程調度程序選擇這個進程4.出現有效輸入出現有效輸入122.1.5 進程的狀態(tài) (2) 以進程構造的操作系統最底層 處理中斷, 調度 在該層之上是順序進程132.1.6 進程的實現（補充）進程控制塊（用來標識進程存在于系統中的唯進程控制塊（用來標識進程存在于系統中的唯一的實體，部分或全部常駐內

7、存）一的實體，部分或全部常駐內存）程序程序數據集數據集 ：系統用反映進程的動態(tài)特征，內容包括：系統用反映進程的動態(tài)特征，內容包括：描述信息：進程名（標識號），用戶名（標識號），家族鏈描述信息：進程名（標識號），用戶名（標識號），家族鏈控制信息：狀態(tài)，優(yōu)先級，內存始址，計時，通信信息控制信息：狀態(tài)，優(yōu)先級，內存始址，計時，通信信息資源管理信息：內存大小，設備等資源管理信息：內存大小，設備等現場保護機構：中設有現場保護機構：中設有142.1.6 進程的實現 (1)典型的進程表表項中的一些字段進程表表項進程表表項進程控制塊的主要字段進程控制塊的主要字段152.1.6 進程的實現(2)當中斷發(fā)生后操作

8、系統最底層的工作步驟1.硬件壓入堆棧程序計數器等。硬件壓入堆棧程序計數器等。2.硬件從中斷向量裝入新的程序計數器。硬件從中斷向量裝入新的程序計數器。3.匯編語言過程保存寄存器值。匯編語言過程保存寄存器值。4.匯編語言過程設置新的堆棧。匯編語言過程設置新的堆棧。5.C中斷服務例程運行（典型的讀和緩沖輸入）。中斷服務例程運行（典型的讀和緩沖輸入）。6.調度程序決定下一個將運行的進程。調度程序決定下一個將運行的進程。7.C過程返回至匯編代碼過程返回至匯編代碼8.匯編語言過程開始運行新的當前進程匯編語言過程開始運行新的當前進程中斷發(fā)生時，底層處理步驟中斷發(fā)生時，底層處理步驟16進程與程序的區(qū)別（補充）

9、 進程更能真實的描述并發(fā)（程序不能） 進程是由程序和數據兩部分組成的 程序是靜態(tài)的。進程是動態(tài)的 進程有生命周期，有誕生有消亡，短暫的；而程序是相對長久的 一個程序可以對應多個進程 進程具有創(chuàng)建其他進程的功能17 線程 線程是輕量級的進程，它是一個進程內的基本調度單位，有自己的程序計數器、寄存器及堆棧。 多線程與多進程-多線程系統允許多個線程共享一個進程的地址空間、打開文件、全局變量等資源。-多進程系統允許多個進程共享物理內存、磁盤、打印機等資源。 線程與進程 - 進程是資源管理的基本單位 -線程是調度的基本單位 2.2 線程線程2.2.1 線程的概念線程的概念182.2.2 線程模型線程模型

10、(a) 三個進程，每個進程有三個進程，每個進程有1個線程個線程(b) 一個進程有一個進程有3個線程個線程112319線程的實現（線程的實現（TCB） 一個進程中所有線程共享內容一個進程中所有線程共享內容 每個線程自己的內容每個線程自己的內容20每個線程有自己的堆棧(kernel&user stack,TCB)212.2.3 引入線程的原因引入線程的原因 偽并行，進一步提高并發(fā)度 更小的系統開銷 更高的性能 有利于在多CPU系統中實現真正的并行222.2.4 在用戶空間實現線程在用戶空間實現線程用戶級線程包用戶級線程包232.2.5 在內核中實現線程在內核中實現線程內核管理的線程包內核管

11、理的線程包242.2.6 混合實現混合實現 用戶級線程與內核線程復用用戶級線程與內核線程復用252.3 進程間通信進程間通信 并發(fā)進程間的相互制約：并發(fā)進程間的相互制約：間接制約：諸進程對共享資源的使用通過系統來協調，使得間接制約：諸進程對共享資源的使用通過系統來協調，使得進程間執(zhí)行速度相互影響進程間執(zhí)行速度相互影響直接制約：諸進程自行使用共享資源或由進程合作引起，某直接制約：諸進程自行使用共享資源或由進程合作引起，某一進程直接通過某機構發(fā)消息給其他進程，從而直接其他進程一進程直接通過某機構發(fā)消息給其他進程，從而直接其他進程的執(zhí)行的執(zhí)行 基本概念：基本概念：臨界資源：一次只允許一個進程使用的資

12、源臨界資源：一次只允許一個進程使用的資源臨界區(qū)：在每個進程中，訪問臨界資源的那部分代碼（那段程臨界區(qū)：在每個進程中，訪問臨界資源的那部分代碼（那段程序）序）2.3.1 進程通信進程通信262.3.2 互斥互斥 定義定義: 不允許兩個以上的共享該資源的并發(fā)進程同時進入臨界不允許兩個以上的共享該資源的并發(fā)進程同時進入臨界區(qū)，稱為互斥區(qū)，稱為互斥 并發(fā)進程互斥執(zhí)行準則：并發(fā)進程互斥執(zhí)行準則：不假設各并發(fā)進程的相對執(zhí)行速度不假設各并發(fā)進程的相對執(zhí)行速度出于臨界區(qū)外的進程不能阻止其他進程進入臨界區(qū)出于臨界區(qū)外的進程不能阻止其他進程進入臨界區(qū)任何時刻只允許一個進程處于臨界區(qū)中任何時刻只允許一個進程處于臨界

13、區(qū)中不能使進程在臨界區(qū)外永遠等待不能使進程在臨界區(qū)外永遠等待27 互斥的實現：互斥的實現：關中斷法：每個進程進入臨界區(qū)后先關中斷，離開前開中斷關中斷法：每個進程進入臨界區(qū)后先關中斷，離開前開中斷缺點：系統可能終止缺點：系統可能終止多多CPU時，無用時，無用加鎖法：用鎖變量來表示臨界區(qū)是否可用加鎖法：用鎖變量來表示臨界區(qū)是否可用加鎖后的臨界區(qū)描述如下：lock(keys) /s為臨界區(qū)類名 unlock(keys) /keys為鎖變量，為1表示臨界區(qū) /可用，為0表示臨界區(qū)不能使用28 lock(keys) L: if keys=0 then goto L else keys=0 unlock(

14、keys) keys= 1 PA() L1: lock(keys) unlock(keys) goto L1PB() L2: lock(keys) unlock(keys) goto L2缺點：不斷循環(huán)測試，缺點：不斷循環(huán)測試，CPU費時費時存在不公平現象存在不公平現象29嚴格的輪轉法：用標志嚴格控制輪流使用臨界區(qū)嚴格的輪轉法：用標志嚴格控制輪流使用臨界區(qū)PA()while(true) while(turn!=0); /wait critical_region(); turn=1; noncritical_region(); PB() while(true) while(turn!=1); /

15、wait critical_region(); turn=0; noncritical_region(); 缺點：當一個進程比另一進程慢很多時不好缺點：當一個進程比另一進程慢很多時不好30TSL指令指令用用TSL指令進入和離開臨界區(qū)指令進入和離開臨界區(qū)31 信號量法：信號量法：信號量：是中表示資源的物理實體，是一個與隊列相關的信號量：是中表示資源的物理實體，是一個與隊列相關的整型變量，其值僅由整型變量，其值僅由down，up原語改變原語改變信號量的表示意義：信號量的表示意義：設設sem為信號量，則：為信號量，則：當當sem=0時，表示可供并發(fā)進程使用的資源實體數時，表示可供并發(fā)進程使用的資源實

16、體數 當當sem =0調用進程入等待隊列轉進程調度返回入口 s=s+1 s=0喚醒等待隊列中的一個進程返回或轉進程調度返回down原語原語up原語原語YYNN33用用down，up原語實現互斥：原語實現互斥：A： down(sem) up(sem) B： down(sem) up(sem) 設一個互斥的信號量設一個互斥的信號量sem描述：描述：S為臨界區(qū)的類名為臨界區(qū)的類名34管程管程一種更為高級的同步原語，更便于使用，管程的互斥由編譯一種更為高級的同步原語，更便于使用，管程的互斥由編譯 器負責，使用者只需將所有臨界區(qū)轉換為管程即可。器負責，使用者只需將所有臨界區(qū)轉換為管程即可。一個管程是由過

17、程、條件變量及數據結構等組成的特殊模塊一個管程是由過程、條件變量及數據結構等組成的特殊模塊 或軟件包。進程僅能通過管程訪問其中的數據結構?；蜍浖?。進程僅能通過管程訪問其中的數據結構。 管程的特性：任一時刻管程中只能有一個活躍進程。管程的特性：任一時刻管程中只能有一個活躍進程。352.3.3 進程同步進程同步例：設有計算進程及打印進程通過共用一個例：設有計算進程及打印進程通過共用一個buf緩沖區(qū)進行工作，緩沖區(qū)進行工作，如兩進程獨立工作，則過程可描述如下：如兩進程獨立工作，則過程可描述如下：Pc: . A: local Buf repeat buf - Buf until Buf = null

18、 compute Buf - result goto A .Pp: . B: local Pri repeat Pri - buf until Pri = null print buf - null goto B .假定對假定對buf已采取的互斥措施已采取的互斥措施36 定義：定義：異步環(huán)境下，一組并發(fā)進程因直接制約而相互發(fā)送消息，異步環(huán)境下，一組并發(fā)進程因直接制約而相互發(fā)送消息，相互合作，相互等待，使各進程按一定速度執(zhí)行的過程相互合作，相互等待，使各進程按一定速度執(zhí)行的過程 同步的實現：同步的實現： 消息名法：消息名法：為同步進程間發(fā)送的事件或消息賦予一個唯一的消息名，用：為同步進程間發(fā)送的

19、事件或消息賦予一個唯一的消息名，用：wait(表示進程等待合作進程發(fā)來的消息表示進程等待合作進程發(fā)來的消息) signal(表示向合作進程發(fā)送消息表示向合作進程發(fā)送消息)則上例表示的同步關系如下：則上例表示的同步關系如下：設消息名設消息名Bufempty表示表示Buf為空，為空，Buffull表示表示Buf滿滿初始化：初始化：Bufempty=true, Buffull=false37描述：描述：Pc: A: wait(Bufempty) caculate Buf - result Bufempty - false signal(Buffull) Goto APp: B: wait(Buffu

20、ll) print Buf - null Buffull - false signal(Bufempty) Goto B38信號量法：信號量法：此處信號量只與制約及被制約進程有關，故為私有的信號量此處信號量只與制約及被制約進程有關，故為私有的信號量同例：同例：設設SA=0表示表示Buf中無可供打印的計算結果中無可供打印的計算結果SB=0表示表示Buf空，計算結果可放入空，計算結果可放入BufPcPp39Pc: A: caculate next number Buf - result count=count-1 V(SA) P(SB) if count=0 then destroy(Pc) el

21、se goto APp: B: P(SA) print 0) 對享受服務隊列：對享受服務隊列：b * t (ab0)新建就緒隊列進程轉入享受服務隊列的時機：新建就緒隊列進程轉入享受服務隊列的時機：就緒隊列的第一個進程的優(yōu)先級（就緒隊列的第一個進程的優(yōu)先級（a*(t-t1)）享受服務隊）享受服務隊列最后一個進程的優(yōu)先級（列最后一個進程的優(yōu)先級（b*t）時）時當享受服務隊列為空時，新建就緒隊列頭一進程可轉入享受服當享受服務隊列為空時，新建就緒隊列頭一進程可轉入享受服務隊列務隊列注：注：ab0 否則：否則：ba0，成為，成為 ab=0，成為，成為62例：有個進程，它們的周期時值及優(yōu)先級如下表：周期性

22、優(yōu)先數進入時刻）在非剝奪方式下，求它們的調度序列，平均等待時間，平均周轉時間，平均帶權周轉時間）在可剝奪方式下，設優(yōu)先級按如下規(guī)律變化：連續(xù)執(zhí)行10ms以上后優(yōu)先數加，就緒隊列中的進程每40ms優(yōu)先數減；則求它們的調度序列，平均等待時間，平均周轉時間，平均帶權周轉時間63 多隊列輪轉法：多隊列輪轉法：進程按不同的優(yōu)先級進入不同的隊列，每個隊列又采用不同的進程按不同的優(yōu)先級進入不同的隊列，每個隊列又采用不同的算法，如圖所示：算法，如圖所示：cpu1cpu2cpun完成完成完成完成完成完成（時間片）（時間片）（時間片）（時間片）RR（時間片（時間片n）時間片到（剝奪）時間片到（剝奪）時間片到（剝奪

23、）時間片到（剝奪） 注：注：n642.4.6 實時系統調度方法：實時系統調度方法： 實時系統處理的外部事件：實時系統處理的外部事件：硬實時任務：系統必須完全滿足任務的時限要求硬實時任務：系統必須完全滿足任務的時限要求軟實時任務：允許系統對任務的時限要求有一定的延遲軟實時任務：允許系統對任務的時限要求有一定的延遲 實時操作系統的功能實時操作系統的功能:快速的進程或線程切換快速的進程或線程切換快速的外部中斷響應快速的外部中斷響應基于優(yōu)先級的隨時強占式調度策略基于優(yōu)先級的隨時強占式調度策略 65 實時操作系統的調度算法：實時操作系統的調度算法：時限調度算法：時限調度算法：選擇時限要求最近的任務優(yōu)先占

24、有處理機，它是搶先式選擇時限要求最近的任務優(yōu)先占有處理機，它是搶先式的，即將新任務的時限與當前任務的時限進行比較，選擇時的，即將新任務的時限與當前任務的時限進行比較，選擇時限最近的執(zhí)行限最近的執(zhí)行（時限可以是處理開始時限或處理結束時限）（時限可以是處理開始時限或處理結束時限）頻率單調調度算法：頻率單調調度算法：周期長的任務優(yōu)先級越低周期長的任務優(yōu)先級越低（適用于多周期性實時任務）（適用于多周期性實時任務）1/n662.4.7 線程調度線程調度用戶級線程的可能調度用戶級線程的可能調度67內核級線程的可能調度內核級線程的可能調度682.5 經典的進程間通信問題經典的進程間通信問題2.5.1 生產者

25、生產者-消費者問題消費者問題P1P2Pm12nC1C2C3有界緩沖區(qū)生產者消費者之間滿足的條件：生產者消費者之間滿足的條件：消費者想接收數據時，有界緩沖區(qū)中至少有一個單元是滿的消費者想接收數據時，有界緩沖區(qū)中至少有一個單元是滿的生產者想發(fā)送數據時，有界緩沖區(qū)中至少有一個單元是空的生產者想發(fā)送數據時，有界緩沖區(qū)中至少有一個單元是空的有界緩沖區(qū)是臨界資源有界緩沖區(qū)是臨界資源69702.5.2 哲學家就餐問題哲學家就餐問題 哲學家的活動：吃飯/思考 吃飯需要2把叉子 一次只拿一把? 給出描述哲學家行為的、不會死鎖的程序結構* It is useful for modeling processes that are competing for exclusive acces