操作系統(tǒng)簡明教程PPT第2章.ppt

,1,2.5 線程 2.5.1 線程的引入 進(jìn)程作為一個獨立運(yùn)行的基本單位只有進(jìn)程可以被調(diào)度運(yùn)行，只有進(jìn)程才能擁有資源。 分配、回收、切換時空開銷 為使進(jìn)程的程序充分并發(fā)執(zhí)行，同時能盡量減少系統(tǒng)的開銷，新想法 進(jìn)程調(diào)度運(yùn)行和擁有資源這兩個基本運(yùn)行單位的屬性分開，讓進(jìn)程擁有資源，而讓一個新的實體作為調(diào)度運(yùn)行的基本單位。,2,隨著并行技術(shù)、網(wǎng)絡(luò)技術(shù)和軟件設(shè)計技術(shù)的發(fā)展，給并發(fā)程序設(shè)計效率帶來了一系列新的問題，主要表現(xiàn)在： 進(jìn)程時空的開銷大，頻繁的進(jìn)程調(diào)度將耗費大量處理器時間，要為每個進(jìn)程分配存儲空間限制了操作系統(tǒng)中進(jìn)程的總數(shù)。 進(jìn)程通信的代價大，每次通信均要涉及通信進(jìn)程之間或通信進(jìn)程與操作系統(tǒng)之間的信息傳遞。 進(jìn)程之間的并發(fā)性粒度較粗，并發(fā)度不高，過多的進(jìn)程切換和通信延遲使得細(xì)粒度的并發(fā)得不償失。 不適合并行計算和分布并行計算的要求，對于多處理器和分布式的計算環(huán)境來說，進(jìn)程之間大量頻繁的通信和切換，會大大降低并行度。 不適合客戶/服務(wù)器計算的要求。對于C/S 結(jié)構(gòu)來說，那些需要頻繁輸入輸出并同時大量計算的服務(wù)器進(jìn)程（如數(shù)據(jù)庫服務(wù)器、事務(wù)監(jiān)督程序）很難體現(xiàn)效率。,3,在引入線程的操作系統(tǒng)中，將進(jìn)程看作資源集合與線程集合的復(fù)合體。 進(jìn)程擁有資源，屬于同一個進(jìn)程的所有線程可以共享這些資源。此外，每個線程僅有較少的私用資源，如程序計數(shù)器、寄存器和棧等。 每一個線程是一個動態(tài)對象，它表示進(jìn)程中的一條控制線索，執(zhí)行一系列指令操作，是一個相對獨立的、可被調(diào)度運(yùn)行的基本單位。,4,在進(jìn)程的地址空間中可以有多個線程，它們可以并發(fā)執(zhí)行， 這就需要一張單獨的表來記錄線程控制與管理等信息，這張表稱為線程控制表TCB。 其中，每個線程占一項，以記錄線程的程序計數(shù)器、寄存器的值及狀態(tài)等信息。 程序計數(shù)器可以使線程像進(jìn)程一樣被暫停執(zhí)行和恢復(fù)執(zhí)行，寄存器的值等可以保存線程暫停執(zhí)行時的CPU狀態(tài)。,5,線程由創(chuàng)建而產(chǎn)生，由撤消而消亡，在生命期間，線程可以處于就緒狀態(tài)、執(zhí)行狀態(tài)和阻塞狀態(tài)三個基本狀態(tài)中。 這三個基本狀態(tài)也像進(jìn)程一樣，會發(fā)生變遷，如就緒狀態(tài)執(zhí)行狀態(tài)，執(zhí)行狀態(tài)阻塞狀態(tài)，阻塞狀態(tài)就緒狀態(tài)等。,6,2.5.2 線程的類型 系統(tǒng)如何感知線程的存在？ 線程在用戶空間還是在系統(tǒng)空間。 不同類型的線程有著不同的屬性和使用方法，三種主要的線程類型： 1內(nèi)核線程 2輕量級進(jìn)程LWP 3用戶線程,7,1內(nèi)核線程 一個內(nèi)核線程可以獨立工作，不需要與一個用戶進(jìn)程聯(lián)系起來。 創(chuàng)建與回收 負(fù)責(zé) 共享什么，具有什么？ 調(diào)度與同步？ 開銷與使用資源？ 運(yùn)行在系統(tǒng)空間線程表,8,2輕量級進(jìn)程LWP 一個輕量級進(jìn)程LWP是一個內(nèi)核支持的用戶線程，運(yùn)行在用戶空間。 內(nèi)核線程基礎(chǔ)上的高層抽象，因此 每個進(jìn)程可以有一個或多個輕量級進(jìn)程LWP，用戶進(jìn)程通過輕量級進(jìn)程LWP與內(nèi)核通信，每一個輕量級進(jìn)程LWP都由一個單獨的內(nèi)核線程支持 可以被調(diào)度并且共享所屬進(jìn)程的地址空間和其它資源,9,它們可以對I/O設(shè)備或其它資源進(jìn)行系統(tǒng)調(diào)用，同時也能在I/O操作或資源訪問時被阻塞。 除了內(nèi)核堆棧和寄存器外，輕量級進(jìn)程LWP也需要維護(hù)一些用戶狀態(tài)，主要包括用戶寄存器上下文，當(dāng)輕量級進(jìn)程LWP被搶占CPU時這些內(nèi)容必須保存下來，以便保證下次調(diào)度運(yùn)行的正確進(jìn)行。 為了節(jié)省系統(tǒng)開銷，多個用戶進(jìn)程可以多路復(fù)用一個輕量級進(jìn)程LWP，但是只有連接到輕量級進(jìn)程LWP的進(jìn)程，才能與內(nèi)核通信。,10,進(jìn)程、輕量級進(jìn)程LWP及內(nèi)核線程關(guān)系圖,11,3用戶線程 用戶線程運(yùn)行在用戶空間，內(nèi)核無需也無法感知它。每個用戶線程僅需一個棧和程序計數(shù)器PC, 切換速度快。當(dāng)一個用戶線程被阻塞時, 它在停止之前選擇并啟動它的后繼線程。 用戶線程的實現(xiàn)是可能的，因為用戶線程的上下文可以在沒有內(nèi)核干預(yù)的情況下被保存和恢復(fù)。每一個用戶線程有自己的用戶堆棧，一塊用來保存用戶級寄存器上下文以及如信號屏蔽等狀態(tài)信息的內(nèi)存區(qū)域。通過保存當(dāng)前線程的堆棧和寄存器內(nèi)容，以及裝入新調(diào)度線程的那些堆棧和寄存器內(nèi)容，可實現(xiàn)用戶線程間的調(diào)度和上下文的切換。,12,內(nèi)核仍然負(fù)責(zé)進(jìn)程的切換，因為只有內(nèi)核具有修改內(nèi)存管理寄存器的權(quán)力。用戶線程不是真正地可以調(diào)度的實體，內(nèi)核沒有保留它們的一點信息，內(nèi)核只是簡單地調(diào)度它們下面的進(jìn)程，這些進(jìn)程再使用庫函數(shù)來調(diào)度它們的線程。當(dāng)進(jìn)程被搶占時，它們的線程也被搶占。,13,普通進(jìn)程上的用戶線程,14,2.5.3 線程與進(jìn)程的比較 在引入了線程的操作系統(tǒng)中，一個進(jìn)程除擁有資源外，還包括一個或多個線程。下面將進(jìn)程與線程做一比較： 1調(diào)度 擁有資源的基本單位和獨立調(diào)度運(yùn)行的基本單位的變化？ 線程的調(diào)度？,15,2并發(fā) 在引入線程的操作系統(tǒng)中，不僅進(jìn)程之間可以并發(fā)執(zhí)行，而且屬于同一個進(jìn)程的多個線程之間也可以并發(fā)執(zhí)行，因而使系統(tǒng)具有更好的并發(fā)性，可以更有效地使用系統(tǒng)資源和提高系統(tǒng)的吞吐量。 3擁有資源 無論是傳統(tǒng)的操作系統(tǒng)，還是引入線程的操作系統(tǒng)，進(jìn)程都是擁有資源的一個獨立單位，而線程僅擁有很少的一些私有資源（如程序計數(shù)器、寄存器和棧、線程表項等），但是它可以訪問所屬進(jìn)程的所有資源。,16,4開銷 在進(jìn)程創(chuàng)建和進(jìn)程撤消時，系統(tǒng)所付出的開銷大于創(chuàng)建線程和撤消線程的開銷。 進(jìn)程切換的開銷遠(yuǎn)遠(yuǎn)大于線程切換的開銷。此外，由于同一進(jìn)程的多個線程具有相同的地址空間，使得它們之間的同步和通信也變得比較容易實現(xiàn)。,17,注意：將線程引入操作系統(tǒng)后，設(shè)計人員必須選擇正確的內(nèi)核線程和用戶線程設(shè)計方法，而無論選擇哪種方法都有一些必須解決的問題，例如： (1) 父、子進(jìn)程是否有同樣的線程？ 如果父、子進(jìn)程具有相同的線程，父、子進(jìn)程兩者中有一個的線程阻塞時，另一個的相應(yīng)線程是否也應(yīng)該阻塞？,18,(2) 共享數(shù)據(jù)結(jié)構(gòu)。 當(dāng)一個線程關(guān)閉一個文件時，另一個線程在讀該文件，后果如何？ 若一個線程內(nèi)存不夠申請時，切換發(fā)生，新運(yùn)行線程內(nèi)存不夠也要申請，那么是申請一次還是兩次？,19,(3) 堆棧等問題。 當(dāng)一個進(jìn)程有多個線程時，它必須有多個堆棧。如果核心無法感知這些堆棧，則發(fā)生堆棧故障時它不能自動擴(kuò)展，實際上它甚至可能意識不到內(nèi)存故障與堆棧增長有關(guān)。 結(jié)論：引入線程的操作系統(tǒng)是需要重新設(shè)計的，但要注意兼容性，以保證現(xiàn)存的只有一個線程的進(jìn)程的可用性。,20,多線程技術(shù)在現(xiàn)代計算機(jī)軟件中得到了廣泛的應(yīng)用，取得了較好的效果。下面舉 例說明多線程技術(shù)的一些主要應(yīng)用： 前臺和后臺工作。如在一個電子表格軟件中，一個線程執(zhí)行顯示菜單和讀入用戶輸入，同時，另一個線程執(zhí)行用戶命令和修改電子表格。 C/S 應(yīng)用模式。局域網(wǎng)上文件（網(wǎng)絡(luò)）服務(wù)器處理多個用戶文件（任務(wù)）請求時，創(chuàng)建多個線程，若該服務(wù)器是多CPU 的，則同一進(jìn)程中的多線程可以同時運(yùn)行在不同CPU 上。,21,加快執(zhí)行速度。一個多線程進(jìn)程在計算一批數(shù)據(jù)的同時，讀入設(shè)備（網(wǎng)絡(luò)、硬盤）上的下一批數(shù)據(jù)，而這分別由兩個線程實現(xiàn)。 異步處理。程序中的異步成分可用線程實現(xiàn)，例如，為避免掉電帶來損失，可把文字編輯器設(shè)計成周期性把內(nèi)存緩沖內(nèi)容寫入到磁盤中?？梢詣?chuàng)建一個線程完成周期性寫盤任務(wù)，該線程由操作系統(tǒng)調(diào)度，并不需要應(yīng)用進(jìn)程提供代碼來做檢查或輸入輸出。 設(shè)計用戶接口。每當(dāng)用戶要求執(zhí)行一個動作時，就建立一個獨立線程來完成這項動作。當(dāng)用戶要求有多個動作時，就由多個線程來實現(xiàn)，窗口系統(tǒng)應(yīng)有一個線程專門處理鼠標(biāo)的動作。例如，GUI 中，后臺進(jìn)行屏幕輸出或真正計算；同時，要求對用戶輸入（鼠標(biāo)）做出反映。有了多線程，可同時運(yùn)行GUI輸入線程和后臺計算線程，便能實現(xiàn)這一功能。,22,2.6 死 鎖 混亂一個操作系統(tǒng)應(yīng)該保證一個進(jìn)程具有獨立訪問某個資源的能力。 但需獨占的資源不只一種 兩進(jìn)程 IO設(shè)備 記錄加鎖 相互申請對方尚未產(chǎn)生的消息 系統(tǒng)中存在各種進(jìn)程被阻塞而且不能解除的情況，通稱為死鎖，軟、硬件資源的申請都可能導(dǎo)致死鎖。,23,死鎖是指一種僵局：在系統(tǒng)運(yùn)行的某一時刻，當(dāng)一組進(jìn)程中的某個進(jìn)程提出資源請求或者彼此通信時，使得此組進(jìn)程在無外力作用下永遠(yuǎn)不能再向前推進(jìn)，此時稱這組進(jìn)程處于死鎖狀態(tài)。 死鎖的多數(shù)情況? 若這種情況只存在于部分進(jìn)程中，稱系統(tǒng)發(fā)生了局部死鎖；若系統(tǒng)中所有進(jìn)程都出現(xiàn)了這種情況，則稱系統(tǒng)發(fā)生了全局死鎖。,24,2.6.2 死鎖的類型 在計算機(jī)系統(tǒng)中發(fā)生死鎖，與資源有關(guān)的情況居多，下面進(jìn)行具體分析。 1資源 兩大類： 可剝奪資源 CPU、內(nèi)存等 不可剝奪資源 打印機(jī)、磁帶機(jī)等。 死鎖與不可剝奪資源有關(guān)。涉及可剝奪資源的死鎖通過在進(jìn)程間重新分配資源，通常能夠化解。所以，我們將重點放在對不可剝奪資源的處理上。,25,在系統(tǒng)中，對于一個資源的使用過程通常有以下幾步： (1) 申請資源； (2) 獲得資源； (3) 使用資源； (4) 釋放資源。 通常，當(dāng)進(jìn)程申請資源失敗時，將申請資源的進(jìn)程阻塞，在資源可用時再將其喚醒，這種方法使用得較多。也可以返回一個錯誤碼，由申請進(jìn)程等候一段時間后再重新申請。,26,2競爭資源引起死鎖,27,o、q、r、s、t o、q、r、s、n、u o、q、r、v、w、m、u,28,3進(jìn)程通信引起死鎖,P1：請求S3，產(chǎn)生S1； P2：請求S1，產(chǎn)生S2； P3：請求S2，產(chǎn)生S3；,P1：產(chǎn)生S1，請求S3； P2：產(chǎn)生S2，請求S1； P3：產(chǎn)生S3，請求S2,29,2.6.3 死鎖發(fā)生的條件 Coffman等人（1971）總結(jié)死鎖產(chǎn)生的必要條件如下： (1) 互斥條件：一個資源在某一時刻只能分配給一個進(jìn)程。若一個進(jìn)程申請某資源時，該資源被另一進(jìn)程占用，則申請者等待，直到占有者釋放該資源時才可能獲得。 (2) 請求與保持條件：進(jìn)程在占用部分資源后，運(yùn)行時還可以申請其余的資源，而且在申請其余資源時并不釋放已占用的資源。,30,(3) 非剝奪條件：已分配給進(jìn)程的資源不可被剝奪，只能被占有者自行釋放。 (4) 循環(huán)等待條件：系統(tǒng)中存在著一條由兩個或兩個以上的進(jìn)程組成的循環(huán)鏈，鏈中的每個進(jìn)程都在等待相鄰進(jìn)程已占用的資源。 以上是死鎖產(chǎn)生的必要條件，要想預(yù)防死鎖發(fā)生，只需設(shè)法破壞其中的任何一條或幾條即可。,31,2.6.4 解決死鎖的方法 解決死鎖的方法通常有以下幾種： 忽略死鎖：對于死鎖不作任何處理； 假如系統(tǒng)中不允許死鎖發(fā)生，通常有兩種解決辦法： 靜態(tài)解決辦法: 系統(tǒng)事先采取措施，對進(jìn)程申請資源的要求加以限制，即預(yù)防死鎖，使得死鎖沒有條件發(fā)生。 動態(tài)解決辦法:在進(jìn)程運(yùn)行過程中提出資源申請時，系統(tǒng)加以檢測，決定是否分配資源，即避免死鎖。 假如系統(tǒng)中允許發(fā)生死鎖，則需檢測死鎖是否發(fā)生，并在死鎖發(fā)生時加以解除。,32,1鴕鳥算法 鴕鳥算法比喻對死鎖視而不見，像鴕鳥一樣。 解決死鎖問題往往代價很大，還常常會給用戶帶來許多限制。大多數(shù)用戶寧可在很偶然的情況下發(fā)生死鎖，也不愿在工作時處處受到限制，因此多數(shù)用戶會選擇方便性而忽視系統(tǒng)對極少發(fā)生的死鎖問題的解決。,33,2預(yù)防死鎖 1) 限制“互斥條件” 不易有解決方案。 2) 限制“請求與保持條件” 只要禁止已擁有資源的進(jìn)程再申請其它資源，就可以消除死鎖。 一種實現(xiàn)方法是:當(dāng)所需資源全部可以使用時方可進(jìn)行分配 另一種方案是:當(dāng)新的資源申請成功時，才收回其原先占用的資源。,34,3) 限制“非剝奪條件” 只能對系統(tǒng)中的一部分資源采用這種方法。 4) 限制“循環(huán)等待條件” 一個方案是:如果要申請第二個資源，它必須先釋放第一個資源。 另一個方案是:把資源分類按順序排列,使進(jìn)程在申請、保持資源時不形成環(huán)路。如有m種資源，則列出R1R2Rm。若進(jìn)程Pi保持了資源Ri，則它只能申請比Ri級別更高的資源Rj(RiRj).釋放資源時必須是Rj先于Ri被釋放，從而避免環(huán)路的產(chǎn)生。,35,3避免死鎖 安全狀態(tài)及不安全狀態(tài)？ 如果能夠找到某種順序，按照這種順序為進(jìn)程分配資源時，進(jìn)程都能夠完成，則稱該狀態(tài)為安全狀態(tài)，否則為不安全狀態(tài)。 關(guān)鍵問題是找到為進(jìn)程分配資源的順序，即安全序列，系統(tǒng)按這個序列為進(jìn)程分配資源，將不會引起死鎖，否則就可能引起死鎖。,36,Dijkstra于1965年提出一種能夠避免死鎖的調(diào)度算法，稱為銀行家算法。該算法基于銀行家能否向客戶貸款及收回貸款的考慮。一個銀行家可以向多個客戶承諾貸款，客戶提出自己最大的貸款額后，銀行家只需準(zhǔn)備一定的貸款額，因為客戶們不太可能同時需要最大的貸款額。當(dāng)一個客戶提出貸款時，銀行家需要檢查： (1) 當(dāng)前銀行是否有這么多金額？ (2) 該客戶的請求是否超出其最大貸款額？ (3) 假如滿足這個客戶的要求，將貸款給他，對剩余貸款額設(shè)法找到一個序列，依次滿足各個客戶貸款請求，各個客戶完成所做事情并歸還貸款，銀行資金才能周轉(zhuǎn)。關(guān)鍵問題是能否找出一個滿足所有客戶要求貸款的序列。,37,上述條件都具備時，銀行家就可以滿足這個客戶提出的貸款請求，否則不予滿足。 這就是銀行家算法。對于(3)中：找出一個滿足所有客戶要求貸款的序列，這個序列稱為安全序列。檢查是否存在安全序列的過程稱為安全性算法，這是銀行家算法的核心。 需要注意的是安全序列并不惟一，這與所有采用的查找順序算法有關(guān)。,38,1) 單資源的銀行家算法 進(jìn)程申請系統(tǒng)的某種資源時，一次可以申請多個，為了避免死鎖，可以采用單資源的銀行家算法。執(zhí)行前，各進(jìn)程給出最大的資源需求，執(zhí)行中，進(jìn)程已分配資源與尚需資源之和就是最大的資源需求。 例：假設(shè)系統(tǒng)有某種設(shè)備12臺，在T0時刻，進(jìn)程需求與分配情況如下：,39,P2、P1、P3序列,40,在T0狀態(tài)下，P3申請分配1臺設(shè)備？,死鎖！,41,2) 多資源的銀行家算法 進(jìn)程申請系統(tǒng)的多種資源，并且每種資源可以申請多個時，為了避免死鎖，可以采用多資源的銀行家算法。每個進(jìn)程在執(zhí)行前給出對各種資源的最大需求。,42,算法中的數(shù)據(jù)結(jié)構(gòu)： 進(jìn)程尚需資源矩陣Sm，n：矩陣S中每一行表示某進(jìn)程對系統(tǒng)中各種資源的需求，初值為進(jìn)程在執(zhí)行前給出的對各種資源的最大需求。 進(jìn)程已分配資源矩陣Fm,n：矩陣F中每一行表示某進(jìn)程已分配的每種資源的個數(shù)。 系統(tǒng)可用資源向量A：其中每個元素表示某種資源當(dāng)前可以使用的個數(shù)。 進(jìn)程Pi用資源請求向量Ri提出資源請求，其中Ri的每個元素表示進(jìn)程在當(dāng)前時刻請求某種資源的個數(shù)。,43,多資源銀行家算法,44,圖2-54 安全性算法,45,4死鎖的檢測 在允許發(fā)生死鎖的系統(tǒng)中，必須有對死鎖進(jìn)行檢測的方法。死鎖的檢測通常是定時進(jìn)行的，時間間隔的選擇很重要。 1) 資源分配圖 資源分配圖中有圓形及方框兩類節(jié)點，圓形表示進(jìn)程，方框表示資源。 2) 死鎖定理 資源分配圖的簡化過程: 不孤立、不阻塞、孤立點 完全簡化、不可完全簡化,46,圖2-55 一個資源分配圖的簡化過程,47,圖2-56 一個資源分配圖,48,49,死鎖定理： 一種資源分配狀態(tài)為死鎖狀態(tài)的充要條件是：當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖是不可完全簡化的。 用死鎖定理來檢測圖2-50，顯然該圖是不可完全簡化的，會發(fā)生死鎖。 資源分配圖的簡化過程本質(zhì)上與銀行家算法中的安全性算法是一致的。在銀行家算法中，安全序列有可能不是惟一的，類似地，資源分配圖的簡化過程也可能不是惟一的。,50,5死鎖的解除 在允許發(fā)生死鎖的系統(tǒng)中，當(dāng)檢測到死鎖時，應(yīng)設(shè)法解除死鎖。 解除死鎖的一種方案是從其它進(jìn)程剝奪資源給死鎖進(jìn)程，直至死鎖解除。當(dāng)然，系統(tǒng)必須付出一定代價。 另一種方案是撤消進(jìn)程。撤消部分進(jìn)程，可使死鎖得以解除。撤消進(jìn)程時，可選擇代價最小的方案，也可以將全部死鎖進(jìn)程撤消，這種方案會使系統(tǒng)付出很大代價。,51,2.8操作系統(tǒng)接口 用戶接口操作系統(tǒng)中實現(xiàn)用戶與計算機(jī)系統(tǒng)之間進(jìn)行交互作用和通信的部分 分類： 命令接口 程序接口 圖形接口,52,2.8.1 命令接口 2.8.2 程序接口 程序接口是操作系統(tǒng)專門為用戶程序設(shè)置的，是用戶程序取得操作系統(tǒng)服務(wù)的惟一途徑。程序接口通常由各種各樣的系統(tǒng)調(diào)用組成。,53,1.基本概念 通常在操作系統(tǒng)的核心中都設(shè)置了一組用于實現(xiàn)各種系統(tǒng)功能的子程序（過程），并將它們提供給用戶程序調(diào)用。 每當(dāng)用戶在程序中需要操作系統(tǒng)提供某種服務(wù)時，便可利用一條系統(tǒng)調(diào)用命令去調(diào)用相應(yīng)的系統(tǒng)過程。 系統(tǒng)調(diào)用本質(zhì)上是一種過程調(diào)用，但它是一種特殊的過程調(diào)用，與一般的過程調(diào)用有明顯差別。,54,1) 運(yùn)行在不同的系統(tǒng)狀態(tài) 一般的過程調(diào)用，其調(diào)用和被調(diào)用的過程或者都是子程序，或者都是系統(tǒng)程序，故都運(yùn)行在同一系統(tǒng)狀態(tài)下。系