【文章內(nèi)容簡介】
phore)與PV操作信號量:A Semaphore is a special integer variable, it can be accessed only through two standard atomic operations。P操作( wait):request a resourceWait(S) {while S = 0 。 // noop S。}V操作( signal):release a resourcesignal (S) { S++。}//,有一個P操作就一定有一個V操作//當(dāng)為互斥操作時,它們處于同一進程//當(dāng)為同步操作時,則不在同一進程中出現(xiàn)//對于前后相連的兩個P(S1)和P(S2) ,順序是至關(guān)重要的:同步P操作應(yīng)該放在互斥P操作前,而兩個V操作順序則無關(guān)緊要信號量實現(xiàn)互斥為臨界資源設(shè)置一個互斥信號量mutex,其初值為1;在每個進程中將臨界區(qū)代碼置于P(mutex)和V(mutex)原語之間信號量實現(xiàn)同步,有一個P操作就一定有一個V操作三個經(jīng)典問題(1)生產(chǎn)者消費者(2)讀者寫者(3)哲學(xué)家吃米飯While (true) { wait ( chopstick[i] )。 wait ( chopStick[ (i + 1) % 5] )。 // eat signal ( chopstick[i] )。 signal (chopstick[ (i + 1) % 5] )。 // think}管程(Monitor)的定義:一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進程調(diào)用的在該數(shù)據(jù)結(jié)構(gòu)上的一組操作過程,這組互斥操作的過程,能同步進程和改變管程中的數(shù)據(jù)。 管程實現(xiàn)互斥:外部等待隊列。一個管程的程序在運行一個線程前會先獲取互斥鎖,直到完成線程或是線程等待某個條件被滿足才會放棄互斥鎖。管程實現(xiàn)同步:內(nèi)部設(shè)置條件變量。一個條件變量就是一個線程隊列(queue), 其中的線程正等待某個條件變?yōu)檎?。CHAPTER 7 DEADLOCK死鎖(deadlock)的概念計算機系統(tǒng)中多道程序并發(fā)執(zhí)行時,兩個或兩個以上的進程由于競爭資源而造成的一種互相等待的現(xiàn)象(僵局),如無外力作用,這些進程將永遠不能再向前推進。死鎖產(chǎn)生原因眾多進程競爭有限資源;進程推進順序不合適。死鎖產(chǎn)生的必要條件互斥使用(Mutual exclusion)不可剝奪(No preemption)請求保持(Hold and wait) 環(huán)路等待(Circular wait)解決死鎖的方案(1)設(shè)計無死鎖的系統(tǒng):預(yù)防、避免(2)允許出現(xiàn)死鎖然后排除:檢測并解除(3)置之不理資源分配圖(resourceallocation graph)中的概念辨析沒有環(huán)路,則沒有死鎖有環(huán)路,可能有死鎖也可能沒有若每種資源只有一個實例,有環(huán)路就有死鎖死鎖的預(yù)防破壞四個必要條件之一,通常是破壞第三、四個條件。(1)資源的靜態(tài)分配方法:進程運行前一次性申請全部資源,破壞請求和保持條件.(2)資源的順序分配法:系統(tǒng)的全部資源進行編號,只允許按編號順序遞增地申請,破除環(huán)路待。(3)一個已占有資源的進程,若要申請新的資源,必須先放棄已占有的資源,破壞請求保持條件。死鎖的避免每當(dāng)進程申請資源時,都根據(jù)一定的算法判斷是否安全安全狀態(tài):當(dāng)多個進程動態(tài)申請資源時,系統(tǒng)按某一順序逐次地為每個進程分配所需資源,使每個進程都可以在最終得到最大需求量后依次順利完成。不安全狀態(tài):可能死鎖避免死鎖的關(guān)鍵:讓系統(tǒng)在動態(tài)分配資源的過程中,不要進入不安全狀態(tài)銀行家算法死鎖的解除:刪除法:刪除死鎖進程,將其資源分給其他進程剝奪法:剝奪某些進程的資源CHAPTER 8 MAIN MEMORY一些概念l 邏輯地址:an address generated by cpul 物理地址:an address seen by the memory unitl 內(nèi)存管理單元(MMUmemory management unit): 包括一個基地址寄存器(relocation register)和一個加法器,在程序運行時map虛擬地址到物理地址。l Compiler bind symbolic address to reloacatable addressl Loader/linkage editor bind relocatable address to absolute address重定位動態(tài)重定位:在程序執(zhí)行期間每次訪問內(nèi)存之前進行重定位。這種變換是靠硬件地址變換機構(gòu)實現(xiàn)的。通常采用重定位寄存器,其中放有當(dāng)前正在執(zhí)行的程序在內(nèi)存空間中的起始地址,而地址空間中的代碼在裝入過程中不發(fā)生變化。靜態(tài)重定位:在目標(biāo)程序裝入內(nèi)存時,由裝入程序?qū)δ繕?biāo)程序中的指令和數(shù)據(jù)的邏輯地址改成物理地址。對每個程序來說,這種地址變換只是在裝入時一次完成,在程序運行期間不再進行重定位。內(nèi)存為程序分配空間的四種方式(1) 連續(xù)分配方式(contiguous memory allocation)單一連續(xù)分配固定分區(qū)分配:分區(qū)容量和數(shù)目固定不變,大小可不等,每個分區(qū)容納一道作業(yè)可變分區(qū)分配:動態(tài)分區(qū),作業(yè)裝入內(nèi)存時才建立分區(qū)(根據(jù)作業(yè)的大?。?/四種動態(tài)分區(qū)分配算法:l 首次適應(yīng)(first fit):allocate the first holel 最佳適應(yīng)(best fit):allocate the smallest holel 最差適應(yīng)(worst fit): allocate the largest holel Next fit: 從剛剛分配出的內(nèi)存開始查找合適的hole分配可重定位分區(qū)分配:重定位寄存器(relocation register)、緊湊技術(shù)(把進程統(tǒng)一移向一邊)(2) 基本分頁存儲管理方式(paging) 分頁引入:動態(tài)分區(qū)方式產(chǎn)生“外碎片”,采用緊湊技術(shù)要付出很大開銷,于是引入了頁式存儲管理。分頁定義A memorymanagement scheme that permits the physical address space of fitting memory to be noncontiguous.分頁原理:l 將物理內(nèi)存分割為等份,叫做物理塊(frame),大小一般為2的次方l 將邏輯地址分割為等份,叫做頁(page),大小與frame相等l 建立page與frame的關(guān)系映射,叫做頁表(page table),頁表在內(nèi)存里。l 地址轉(zhuǎn)換是在進程執(zhí)行過程中進行的。分頁的地址變換過程當(dāng)一個進程轉(zhuǎn)入執(zhí)行狀態(tài)時,其頁表的始址和長度從其PCB中裝入頁表寄存器。當(dāng)進程要訪問某個邏輯地址中的指令或數(shù)據(jù)時,地址變換機構(gòu)自動地將邏輯地址分為頁號和頁內(nèi)地址兩部分,并將頁號與頁表寄存器中的頁表長度比較,若頁號不小于頁表長度,便產(chǎn)生越界中斷,否則以頁號為索引,去檢索頁表,從中得到該頁的物理塊號,送入物理地址寄存器與頁內(nèi)地址拼接,形成物理地址??毂?TLBtranslation lookasi