網(wǎng)絡程序設計3

1、基礎知識第三章1本章教學目標了解線程的基本概念熟悉進程描述、進程通信和進程死鎖掌握進程控制、進程同步與互斥、進程調度 2本章主要內(nèi)容處理器管理概述進程描述進程控制線程的基本概念進程同步與互斥進程通信進程調度進程死鎖3處理器管理概述處理器管理的功能程序的執(zhí)行4處理器管理的功能處理器管理的主要任務是對處理器進行分配，并對其運行進行有效地控制和管理。 處理器管理的主要功能進程控制 原語進程同步 互斥，同步進程通信 進程調度 5程序的執(zhí)行程序的順序執(zhí)行程序的并發(fā)執(zhí)行6程序的順序執(zhí)行概念：程序在執(zhí)行時，必須按某種先后次序逐個執(zhí)行操作，只有當前一個操作執(zhí)行完后，才能執(zhí)行后一個操作。 特征：順序性封閉性可再

2、現(xiàn)性7示意圖用圓結點表示各程序段的操作，其中I表示輸入，C表示計算，P表示打印，用箭頭指明操作間的先后次序。計算機處理完一道程序后再處理下一道程序。描述了二道程序在單CPU系統(tǒng)中先后被順序執(zhí)行。 8程序的并發(fā)執(zhí)行概念：是指在一個時間段內(nèi)執(zhí)行多個程序。 特征： 間斷性 失去封閉性不可再現(xiàn)性程序并發(fā)執(zhí)行的判斷方法：Bernstein條件利用前趨圖9程序并發(fā)執(zhí)行示例下圖描述了多道程序均包括輸入、計算、打印三部分操作時并發(fā)處理的過程。10進程描述進程的概念進程的狀態(tài)進程的掛起狀態(tài) 11進程的概念進程的定義有許多人從不同角度對“進程”下過各式各樣的定義。我國對進程概念的定義，多數(shù)人認為“進程是一個具有一

3、定獨立功能的程序關于某個數(shù)據(jù)集合的一次運行活動”(1978年全國操作系統(tǒng)會議)。所以一個程序在不同數(shù)據(jù)集合上運行，乃至一個程序在同樣數(shù)據(jù)集合上的多次運行都是不同的進程。 進程的特征動態(tài)性 并發(fā)性 獨立性 異步性 結構性 12進程的狀態(tài)進程的三種基本狀態(tài) 進程的其它兩種狀態(tài) 進程狀態(tài)間的轉換 13進程的三種基本狀態(tài) 就緒狀態(tài) 當進程以分配到除處理器（CPU）以外的所有必要資源后，只要再獲得處理器就可以立即執(zhí)行，這時進程的狀態(tài)稱為就緒狀態(tài)。 執(zhí)行狀態(tài) 處于就緒狀態(tài)的進程一旦獲得了處理器，就可以運行，進程狀態(tài)也就處于執(zhí)行狀態(tài)。 阻塞狀態(tài) 正在執(zhí)行的進程因為發(fā)生某些事件（如請求輸入/輸出、申請額外空間

4、等）而暫停運行，這種受阻暫停的狀態(tài)稱為阻塞狀態(tài)，也可以稱為等待狀態(tài)。 14進程的其它兩種狀態(tài) 新狀態(tài) 當一個新進程剛剛建立，還未將其放入就緒隊列時的狀態(tài)，稱為新狀態(tài)。 終止狀態(tài)當一個進程已經(jīng)正常結束或異常結束，操作系統(tǒng)已將其從系統(tǒng)隊列中移出，但尚未撤消，這時稱為終止狀態(tài)。 15進程狀態(tài)間的轉換等待的事件已發(fā)生等待某事件發(fā)生時間片用完進程被調度程序選中就緒狀態(tài)等待狀態(tài)運行狀態(tài)16進程控制進程控制塊PCB 進程的創(chuàng)建與撤消 進程的阻塞與喚醒 17進程控制塊PCB 進程控制塊的作用進程控制塊的內(nèi)容進程控制塊的組織方式進程控制原語18進程控制塊的作用概念進程控制塊是進程實體的重要組成部分，是操作系統(tǒng)中

5、最重要的記錄型數(shù)據(jù)，在進程控制塊PCB（Program Control Block）中記錄了操作系統(tǒng)所需要的、用于描述進程情況及控制進程運行所需要的全部信息 作用通過PCB，使得原來不能獨立運行的程序（數(shù)據(jù)），成為一個可以獨立運行的基本單位，一個能夠并發(fā)執(zhí)行的進程。進程控制塊是進程存在的唯一標志。 19進程控制塊的內(nèi)容進程標識信息 進程標識符用于標識一個進程，一個進程通有外部標識符和內(nèi)部標識符兩種 說明信息 說明信息是有關進程狀態(tài)等一些與進程調度有關的信息。 現(xiàn)場信息 現(xiàn)場信息是用于保留進程存放在處理器中的各種信息，主要由處理器內(nèi)的各個寄存器的內(nèi)容組成。 管理信息 管理信息包括進程資源、控制機

6、制等一些進程執(zhí)行所需要的信息。 20進程控制塊的組織方式鏈接方式把具有相同狀態(tài)的PCB，用其中的鏈接指針鏈接成隊列。如圖所示。 21索引方式 系統(tǒng)根據(jù)所有進程的狀態(tài)，建立幾張索引表。在每個索引表的表目中，記錄著具有相同狀態(tài)的各個PCB在表中的地址。如圖2-8所示。22進程控制原語原語的概念原語是指具有特定功能的不可被中斷的過程。它主要用于實現(xiàn)操作系統(tǒng)的一些專門控制操作。原語的分類創(chuàng)建原語：用于為一個進程分配工作區(qū)和建立PCB，置該進程為就緒狀態(tài)。 撤消原語：用于一個進程工作完后，收回它的工作區(qū)和PCB。 阻塞原語：用于進程在運行過程中發(fā)生等待事件時，把進程的狀態(tài)改為等待態(tài)。 喚醒原語 ：用于當

7、進程等待的事件結束時，把進程的狀態(tài)改為就緒態(tài)。 23進程的創(chuàng)建 引起進程創(chuàng)建的事件 用戶登錄 作業(yè)調度 提供服務 應用請求 進程創(chuàng)建的過程 為新進程分配唯一的進程標識符，并從PCB隊列中申請一個空閑PCB。為新進程的程序和數(shù)據(jù)，以及用戶棧分配相應的主存空間及其它必要分配資源。初始化PCB中的相應信息，如標識信息、處理器信息、進程控制信息等。如果就緒隊列可以接納新進程，便將新進程加入到就緒隊列中。 24進程的撤消引起進程撤消的事件 進程正常結束 在進程運行期間，由于出現(xiàn)某些錯誤和故障而使得進程被迫中止 進程應外界的請求而中止運行 進程撤消的過程 根據(jù)被終止進程的標識符，從PCB集合中檢索該進程的

8、PCB，讀出進程狀態(tài)。若該進程處于執(zhí)行狀態(tài)，則立即終止該進程的執(zhí)行。若該進程有子孫進程，還要將其子孫進程終止。將該進程所占用的資源回收，歸還給其父進程或操作系統(tǒng)。將被終止進程的PCB從所在隊列中移出，并撤消該進程的PCB。 25進程的阻塞引起進程阻塞的事件 請求系統(tǒng)服務 啟動某種操作 新數(shù)據(jù)尚未到達 無新工作可做 進程阻塞的過程 立即停止執(zhí)行該進程。修改進程控制塊中的相關信息。把進程控制塊中的運行狀態(tài)由“執(zhí)行”狀態(tài)改為“阻塞”狀態(tài)，并填入等待的原因，以及進程的各種狀態(tài)信息。把進程控制塊插入到阻塞隊列。根據(jù)阻塞隊列的組織方式，把阻塞進程的進程控制塊插入到阻塞隊列中。轉調度程序重新調度，運行就緒隊

9、列中的其他進程。 26進程的喚醒引起進程喚醒的事件 請求系統(tǒng)服務得到滿足 啟動某種操作完成 新數(shù)據(jù)已經(jīng)到達 有新工作可做 進程喚醒的過程 從阻塞隊列中找到該進程。修改該進程控制塊的相關內(nèi)容。把阻塞狀態(tài)改為就緒狀態(tài)，刪除等待原因等等。把進程控制塊插入到就緒隊列。按照就緒隊列的組織方式，把被喚醒的進程的進程控制塊插入到就緒隊列中。 27線程的基本概念1線程的概念線程是進程中的一個實體，是被系統(tǒng)獨立調度和執(zhí)行的基本單位。 線程與進程的比較 調度單位不同 并發(fā)形式不同擁有資源 不同28使用線程的例子使用線程的例子是WWW瀏覽器，許多Web頁面都包含有多幅很小的圖像。對于Web頁面上的每一幅小圖像，瀏覽

10、器都必須與頁面的連接點建立一條單獨的連接以索取圖像。這樣就有大量的時間花費在建立和釋放這些連接上。通過在瀏覽器內(nèi)設立多個線程，便可以同時請求傳輸多幅圖像。29線程的基本概念2線程的類型 系統(tǒng)級線程：是依賴于系統(tǒng)控制的，即無論是用戶進程中的線程，還是系統(tǒng)進程中的線程，它們的創(chuàng)建、撤消、切換都是由系統(tǒng)控制實現(xiàn)的。 用戶級線程 ：是由用戶控制，對于用戶級線程的創(chuàng)建、撤消、切換，都與系統(tǒng)控制無關，完全由用戶自己管理。30超線程 超線程的概念 超線程技術就是利用特殊的硬件指令，在一顆實體處理器中放入兩個邏輯處理單元，從而模擬成兩個工作環(huán)境，讓單個處理器都能使用線程級并行計算，同時處理多項任務，提升處理器

11、資源的使用率。 超線程的工作 超線程處理器被視為兩個分離的邏輯處理器，應用程序不須修正就可使用這兩個邏輯處理器。每個邏輯處理器都可獨立響應中斷。第一個邏輯處理器可追蹤一個軟件線程，而第二個邏輯處理器則可同時追蹤另一個軟件線程。由于兩個線程共同使用同樣的執(zhí)行資源，因此不會產(chǎn)生一個線程執(zhí)行的同時，另一個線程閑置的狀況。 31進程同步與互斥進程的并發(fā)性 進程的同步與互斥 利用PV操作實現(xiàn)互斥與同步 管程的基本概念 32進程的并發(fā)性概念在并發(fā)執(zhí)行的系統(tǒng)中，若干個作業(yè)可以同時執(zhí)行，而每個作業(yè)又需要有多個進程協(xié)作完成。在這些同時存在的進程間具有并發(fā)性 并發(fā)進程之間的關系無關關系 ：這些進程間彼此毫無關系，

12、互不影響 相關關系 ：這些進程間彼此往往相關，互相影響，要進行合理的控制和協(xié)調才能正確執(zhí)行 資源共享關系 相互合作關系 33進程的同步與互斥 進程同步與互斥的概念進程同步機制應遵循的原則 利用鎖機制實現(xiàn)同步 34進程同步與互斥的概念臨界資源 在系統(tǒng)中有許多硬件或軟件資源，在一段時間內(nèi)只允許一個進程訪問或使用，這種資源稱為臨界資源。 臨界區(qū) 每個進程中訪問臨界資源的那段代碼稱為臨界區(qū) 進程同步進程同步是指多個相關進程在執(zhí)行次序上的協(xié)調，這些進程相互合作，在一些關鍵點上需要相互等待或相互通信。 進程互斥進程互斥是指當一個進程進入臨界區(qū)使用臨界資源時，另一個進程必須等待，當占用臨界資源的進程退出臨界

13、區(qū)后，另一個進程才被允許使用臨界資源。 35進程同步與進程互斥間的關系（1）相同點進程的同步與進程的互斥都涉及到并發(fā)進程共享資源的問題，進程的互斥實際上是進程同步的一種特殊情況。（2）不同點進程互斥是進程間競爭共享資源的使用權，這種競爭沒有固定的必然關系，哪個進程競爭到使用權就歸哪個進程使用，直到不需要使用時再歸還使用權。進程同步涉及共享資源的并發(fā)進程間有一種必然的依賴關系，當進程必須同步時，即使無進程在使用共享資源，那么尚未得到同步消息的進程也不能去使用這個資源。 36進程同步機制應遵循的原則 空閑讓進 忙則等待 有限等待 讓權等待 37利用鎖機制實現(xiàn)同步鎖的概念 在同步機構中，常用一個變量

14、來代表臨界資源的狀態(tài)，并稱它為鎖。通常用“0”表示資源可用，用“1”表示資源已被占用。 鎖的操作 關鎖操作 解鎖操作 38利用PV操作實現(xiàn)互斥與同步 整型信號量的概念 信號量的操作 利用PV操作實現(xiàn)互斥利用PV操作實現(xiàn)同步利用PV操作實現(xiàn)進程的同步加互斥 39整型信號量的概念概念信號量就是一種特殊變量，它用來表示系統(tǒng)中資源的使用情況。而整型信號量就是一個整型變量。說明：當其值大于“0”時，表示系統(tǒng)中對應可用資源的數(shù)目；當其值小于“0”時，其絕對值表示因該類資源而被阻塞的進程的數(shù)目；當其值等于“0”時，表示系統(tǒng)中對應資源已經(jīng)都被占用，并且沒有因該類資源而被阻塞的進程。 40信號量的操作（1）P操

15、作：記為P（S），描述為： P（S） S=S-1； if （S0） W（S）； （2）V操作：記為V（S），描述為： V（S） S=S+1； if （S=0） R（S）； 41.記錄型信號量機制 信號量類型定義記錄型信號量是一個記錄型的數(shù)據(jù)結構，包含兩個數(shù)據(jù)項，一個是計數(shù)值域，另一個是等待該信號量的進程隊列首指針域。記錄型信號量結構可以描述如下：typedef struct semaphore int value； PCB *P； ；42（）、（）操作原語定義除了給信號量S初始化外，僅能通過P(S)和V(S)原語操作訪問。信號量相應的P(S)和V(S)操作原語描述如下：void p(S)str

16、uct semaphore S；S.value=S.value -1；信號量計數(shù)值減，表示申請資源一個單位if (S.value0 ) block(S.P)；若信號量計數(shù)值，表示無資源， 則阻塞等待。否則調用進程繼續(xù)void v(S)struct semaphore S；S.value=S.value+1； ；信號量計數(shù)值加，表示釋放資源一個單位if (S.value=0) wakeup(S.P)；若信號量計數(shù)值，表示進程在等待該資源，喚醒一個等待者43進程通信概念進程通信是指進程間的信息交換。 類型共享存儲器系統(tǒng)消息傳遞系統(tǒng)管道通信系統(tǒng) 44共享存儲器系統(tǒng)概念在共享存儲器系統(tǒng)中，相互通信的進

17、程共享某些數(shù)據(jù)結構或共享存儲區(qū)，進程之間能夠通過它們進行通信。 方式共享數(shù)據(jù)結構方式 相互通信的諸進程公用某些數(shù)據(jù)結構，并通過這些數(shù)據(jù)交換信息。 共享存儲區(qū)方式 是在存儲器中劃出一塊共享存儲區(qū)，相互通信的諸進程可以通過對共享存儲區(qū)中的數(shù)據(jù)進行讀或寫來實現(xiàn)通信。 45消息傳遞系統(tǒng)概念進程間的數(shù)據(jù)交換以消息為單位，用戶直接利用系統(tǒng)中提供的一組通信命令（原語）進行通信。 方式直接通信方式發(fā)送進程使用發(fā)送原語直接將消息發(fā)送給接收進程，并將它掛在接收進程的消息緩沖隊列上，接收進程使用接收原語從消息緩沖隊列中取出消息。 間接通信方式 發(fā)送進程使用發(fā)送原語直接將消息發(fā)送到某種中間實體中，接收進程使用接收原語

18、從該中間實體中取出消息。 46管道通信系統(tǒng)管道管道是指連接讀進程和寫進程，以實現(xiàn)它們之間通信的共享文件。 管道通信系統(tǒng)向管道提供輸入的發(fā)送進程（寫進程），以字符流形式將大量的數(shù)據(jù)送入管道，而接受管道輸出的接收進程（讀進程），可以從管道中接收數(shù)據(jù)。 47進程調度進程調度的類型選擇進程調度算法的原則 常用的進程調度算法 48進程調度的類型高級調度 低級調度 中級調度 49高級調度基本原理高級調度又稱為作業(yè)調度或長程調度，用于決定把外存上處于后備隊列中的哪些作業(yè)調入主存，并為它們創(chuàng)建進程、分配必要的資源，然后將新創(chuàng)建的進程排入就緒隊列，準備執(zhí)行。 需要解決的問題 一是接納多少個作業(yè)。 二是接納哪些作

19、業(yè)。 50低級調度基本原理低級調度通常又稱為進程調度或短程調度。它決定主存中的就緒隊列上的哪個進程（單處理器系統(tǒng)）將獲得處理器，然后把處理器分配給該進程，使其執(zhí)行。 方式非搶占方式 在某個進程正在占用處理器執(zhí)行時，不允許其它任何進程搶占處理器。 搶占方式 把處理器分配給某個進程后，在該進程尚未終止或阻塞時，允許系統(tǒng)調度程序根據(jù)某種原則，暫停正在執(zhí)行的進程，回收已經(jīng)分配的處理器，并將處理器重新分配給其它更為緊急的進程。 51中級調度基本原理系統(tǒng)將那些暫時不能運行的進程從主存調到外存（仍然保持進程狀態(tài)）上的特定區(qū)域，這些在外存存放的進程所處的狀態(tài)稱為就緒駐外狀態(tài)或掛起狀態(tài)。當這些進程的運行條件具備

20、，且主存又有空閑時，在中級調度的控制下，再將處于外存上的那些重新具備運行條件的就緒駐外進程調入主存，并將其狀態(tài)修改為就緒狀態(tài)，放入就緒隊列，等待進程調度。 目的是為了進一步提高主存的利用率和系統(tǒng)的吞吐量。52選擇進程調度算法的原則 面向用戶的原則 周轉時間短 響應時間快 截止時間有保證 優(yōu)先權原則 面向系統(tǒng)的原則 系統(tǒng)吞吐量高 處理器利用率好 各類資源的平衡利用 53常用的進程調度算法先來先服務調度算法 短進程優(yōu)先調度算法 時間片輪轉調度算法 優(yōu)先數(shù)調度算法 響應比高者優(yōu)先調度算法 多級隊列調度算法 54先來先服務調度算法 原理每次調度是從就緒隊列中，選擇一個最先進入就緒隊列的進程，把處理器分

21、配給該進程，使之得到執(zhí)行。該進程一旦占有了處理器，它就一直運行下去，直到該進程完成或因發(fā)生事件而阻塞，才退出處理器。 特點利于長進程，而不利于短進程。 55短進程優(yōu)先調度算法 原理它是從就緒隊列中選擇一個估計運行時間最短的進程，將處理器分配給該進程，使之占有處理器并執(zhí)行，直到該進程完成或因發(fā)生事件而阻塞，然后退出處理器，再重新調度。 特點照顧到了系統(tǒng)中占大部分的短進程，有效地降低了進程的平均等待時間，提高了系統(tǒng)的吞吐量，但對長進程不利。 56時間片輪轉調度算法 原理系統(tǒng)將所有的就緒進程按進入就緒隊列的先后次序排列。每次調度時把CPU分配給隊首進程，讓其執(zhí)行一個時間片，當時間片用完，由計時器發(fā)出

22、時鐘中斷，調度程序則暫停該進程的執(zhí)行，使其退出處理器，并將它送到就緒隊列的末尾，等待下一輪調度執(zhí)行。 特點為了保證人機交互的及時性，系統(tǒng)使每個進程依次按時間片方式輪流地執(zhí)行 。57優(yōu)先數(shù)調度算法 原理它是從就緒隊列中選擇一個優(yōu)先權最高的進程，讓其獲得處理器并執(zhí)行。 方式非搶占式優(yōu)先數(shù)調度算法 系統(tǒng)一旦把處理器分配給就緒隊列中優(yōu)先權最高的進程后，該進程就占有處理器一直運行下去，直到該進程完成或因發(fā)生事件而阻塞，才退出處理器。 搶占式優(yōu)先數(shù)調度算法 系統(tǒng)同樣把處理器分配給當前就緒隊列中優(yōu)先權最高的進程，使之執(zhí)行。但在其執(zhí)行期間，仍然會不斷的有新的就緒進程進入就緒隊列，如果出現(xiàn)某個進程，其優(yōu)先權比當

23、前正在執(zhí)行的進程的優(yōu)先權還高時，進程調度程序就會立即暫停當前進程的執(zhí)行，而將處理器收回，并將處理器分配給新出現(xiàn)的優(yōu)先權更高的進程，讓其執(zhí)行。 58響應比高者優(yōu)先調度算法 原理它是從就緒隊列中選擇一個響應比最高的進程，讓其獲得處理器執(zhí)行，直到該進程完成或因等待事件而退出處理器為止。 特點既照顧了短進程，又考慮了進程到達的先后次序，也不會使長進程長期得不到服務，因此是一個比較全面考慮的算法，但每次進行調度時，都需要對各個進程計算響應比。所以系統(tǒng)開銷很大，比較復雜。 59多級隊列調度算法 原理是根據(jù)進程的類型或性質的不同，將就緒進程分為若干個獨立隊列，不同類型或性質的進程固定地分屬于一個隊列，每個隊列可以采用適合的調度算法，不同的隊列可使用不同的調度算法。 特點同時具有多種操作方式 的進程調度60進程死鎖死鎖的基本概念 死鎖的預防