(完整word版)操作系統(tǒng)計算題總結(jié)(word文檔良心出品).doc

1、應用類型知識要點一：進程同步問題整形信號量：wait(S): while S=0 do no-op;未遵循“讓權(quán)等待原則”S:=S-1;signal(S): S:=S+1記錄型信號量：type semaphore=record執(zhí)行 wait 操作時，信號量的值加1，信號量value:integer;的值小于 0 時阻塞；L:list of process;執(zhí)行 signal 操作時， 信號量的值減1，信號量end的值小于等于 0 時喚醒阻塞中的進程。procedure wait(S)var S:semaphore;beginS.value=S.value-1;if S.value0 then

2、block(S.L);endprocedure signal(S)var S:semaphore;beginS.value:=S.value+1;if S.valueSj ，專門設置一初值為0 的信號量，并在 Si 結(jié)束之后執(zhí)行對該信號量的signal 操作，而在 Sj 開始之前執(zhí)行對該信號量的 wait 操作，這樣便可保證程序段Si 執(zhí)行完后才執(zhí)行程序段Sj。2生產(chǎn)者 -消費者問題Var buffer:array0, ,n-1 of item;in, out: integer:=0,0;mutex,empty,full:semaphore:=1,n,0;begin主程序 (n 為常量 )pa

3、rbeginproducer1; ;produceri; ;producerM;consumer1; consumerj; ;consumerN;parendend生產(chǎn)者子程序消費者子程序producericonsumerjVar nextp:item;Var nextc:item;beginbeginrepeatrepeatProduce an item in nextp;wait(full);wait(mutex);wait(empty);wait(mutex);nextc:=bufferout;bufferin:=nextp;out:=(out+1) mod n;in=(in+1)mod

4、 n;signal(mutex); signal(empty);signal(mutex); signal(full);Consume the item in nextc;until falseuntil falseendend生產(chǎn)者子程序 (基于 AND 信號量 )消費者子程序 (基于 AND信號量 )producericonsumerjbeginbeginrepeatrepeatProduce an item in nextp;Swait(full,mutex);Swait(empty, mutex);nextc:=bufferout;bufferin=nextp;out:=(out+1)

5、 mod n;in:=(in+1) mod n;Ssignal(mutex, empty);Signal(mutex, full);Consume the item in nextc;until falseuntil falseendend3讀者 -寫者問題 (讀者優(yōu)先 )Var readercount:integer:=0;rcmutex,wmutex:semaphore:=1,1;begin主程序parbeginreader1;readeri;readerM;writer1;writerj;writerN;parend讀者endreaderibeginrepeatwait(rcmutex)

6、;if readercount=0 then wait(wmutex);readercount:=readercount+1;signal(rcmutex);Perform read operation;wait(rcmutex);readercount:=readercount-1;if readercount=0 then signal(wmutex);signal(rcmutex);until falseendwriterjbeginrepeat寫者wait(wmutex);Perform write operation;signal(wmutex);until false;endrea

7、dercount:讀者數(shù)rcmutex:讀者進程中用于readercount 變量的互斥訪問wmutex: 用于讀者與寫者、寫者與寫者之間的互斥訪問寫者與第一個讀者競爭 wmutex 。一旦讀者獲得 wmutex ，那么直到所有讀者執(zhí)行結(jié)束由最后一個讀者釋放，而每個寫者執(zhí)行結(jié)束都釋放，所以讀者優(yōu)先寫者執(zhí)行。4讀者 -寫者問題 (寫者優(yōu)先 )Var readercount,writercount:integer:=0,0;rcmutex,wcmutex,wmutex,S:semaphore:=1,1,1,1;begin主程序parbeginreader1; ;readeri; ;readerM;

8、writer1; ;writerj; ;writerN;parendendreaderibeginrepeatwait(S);wait(rcmutex);if readercount=0 then wait(wmutex);readercount:=readercount+1;讀者signal(rcmutex);signal(S);Perform read operation;wait(rcmutex);readercount:=readercount-1;if readercount=0 then signal(wmutex);signal(rcmutex);until false;endw

9、riterjbeginrepeatwait(wcmutex);if writercount=0 then wait(S);writercount:=writercount+1;signal(wcmutex);寫者wait(wmutex);Perform write operation;signal(wmutex);wait(wcmutex);writercount:=writercount-1;if writercount=0 then signal(S);signal(wcmutex);until falseendrcmutex:讀者進程中用于readercount 變量的互斥訪問wcmut

10、ex: 寫者進程中用于writercount 變量的互斥訪問5wmutex: 用于讀者與寫者、寫者與寫者之間的互斥訪問讀者與第一個寫者競爭S 信號量。一旦讀者獲得S 信號量，那么直到所有讀者執(zhí)行結(jié)束由最后一個寫者釋放，而每個讀者執(zhí)行結(jié)束都釋放，所以寫者優(yōu)先讀者執(zhí)行。讀者 -寫者問題 (限定讀者數(shù) )Var RN:integer:=10;rmax,wmutex:semaphore:=RN,1;begin主程序parbeginreader1; ;readeri; ;readerM;writer1; ;writerj; ;writerN;parendendreaderibeginrepeatSwai

11、t(rmax,1,1);讀者=Swait(rmax,1,1,wmutex,1,0);Swait(wmutex,1,0);Perform read operation;Ssignal(rmax,1);until false;endwriterjbeginrepeat寫者Swait(wmutex,1,1, rmax,RN,0);Perform write operationSignal(wmutex);until falseendRN: 限定最多同時讀的讀者數(shù)rmax:空位置的數(shù)目，即系統(tǒng)還允許執(zhí)行讀操作的讀者數(shù)，超過這個數(shù)目后讀者將等待wmutex: 用于讀者與寫者、寫者與寫者之間的互斥訪問讀者

12、執(zhí)行Swait(wmutex,1,0) 保證無寫者 (wmutex 值保持不改變)寫者執(zhí)行Swait(wmutex,1,1,rmax,RN,0) 保證既無寫者在寫又無讀者在讀(rmax 值保持不變 )6主程序哲學家進餐問題子程序基于 AND 信號量機制哲學家進餐問題子程序限制哲學家同時進餐人數(shù)哲學家進餐問題Var chopstick:array0,4 of semaphore:=1,1,1,1,1;beginparbeginphilosopher0;philosopheri; philosopher4;parendendphilosopheribeginrepeatThink;Swait(ch

13、opstick(i+1) mod 5,chopsticki);Eat;Ssignal(chopstick(i+1)mod 5,chopsticki); until falseendphilosopherivar pmax:semaphore:=4;beginrepeatwait(pmax);wait(chopsticki);wait(chopstick(i+1) mod 5);Eat;signal(chopstick(i+1) mod 5);signal(chopsticki);signal(pmax);Think;until falseend7理發(fā)師問題描述如下：理發(fā)店包含一間接待室和一間工

14、作室，接待室內(nèi)有n(n=1) 把椅子，而工作室只有一把椅子。如果沒有顧客，理發(fā)師就去睡覺，如果顧客來時所有的椅子都有人，那么顧客離去；如果理發(fā)師在忙且接待室有空閑的椅子，那么此顧客會坐在其中一把空閑的椅子上等待；如果理發(fā)師在睡覺，則顧客會喚醒他。請采用信號量機制解決該理發(fā)師問題 (可采用偽代碼描述)。解：要求描述理發(fā)師和顧客的行為，因為需要兩類進程Barber() 和 Customer()分別描述理發(fā)師和顧客的行為。理發(fā)師和顧客之間是同步的關(guān)系，理發(fā)師和椅子使臨界資源，所以顧客之間是互斥的關(guān)系。引入 3 個信號量和一個控制變量：控制變量waiting 也用于記錄等候的顧客數(shù)，實際上是custo

15、mers 的一份拷貝。之所以使用 waiting 是因為無法讀取信號量的當前值，初值均為0。信號量 customers 用來記錄等候理發(fā)的顧客數(shù) (不包括正在理發(fā)的顧客 ) ，并用作阻塞理發(fā)師進程，初值為 0。信號量 barbers 用來記錄正在等候顧客的理發(fā)師數(shù)（為0 或 1），并用作阻塞顧客進程，初值為 0。信號量 mutex 用于對 waiting 的訪問進行互斥，初值為1。進入理發(fā)店的顧客必須先看等候的顧客數(shù)，如果少于椅子數(shù)（n），他坐下來等，否則他就離開。PV 操作代碼如下 :int waiting=0;/ 等候理發(fā)的顧客數(shù)(還沒理發(fā)的 ), 0 nsemaphore custome

16、rs=0, barbers=0, mutex=1;barber() while(TRUE)/ 理完一人 ,還有顧客嗎 ?P(customers);/ 若無顧客 ,理發(fā)師睡眠P(mutex);/ 進程互斥waiting := waiting -1;/ 等候顧客數(shù)少一個V(barbers);/ 理發(fā)師去為一個顧客理發(fā)V(mutex);/ 開放臨界區(qū)cut-hair( );/ 正在理發(fā) (非臨界區(qū)操作 )customer() / 顧客進入理發(fā)店P(guān)(mutex);/ 進程互斥if (waiting n) / 還有空位waiting := waiting+1;/ 等候顧客數(shù)加1V(customers);

17、/ 有顧客了，如果理發(fā)師在睡則喚醒V(mutex);/ 開放臨界區(qū)P(barbers);/ 無理發(fā)師 , 顧客坐著養(yǎng)神get-haircut( );/ 一個顧客坐下等待理發(fā) elseV(mutex);/ 顧客已滿，離開8應用類型知識要點二：分頁存儲地址結(jié)構(gòu)及地址變換分頁存儲管理地址結(jié)構(gòu)(由硬件機制決定)3112110頁號頁內(nèi)地址邏輯地址與頁號及頁內(nèi)偏移地址之間的換算PageNo=INTAddr/PageLengthPageOffset=Addr mod PageLength舉例：對于1KB 頁面，若給定邏輯地址2170B ，則 PageNo=2， PageOffset=122地址變換任務關(guān)鍵在

18、于頁號到物理塊號之間的轉(zhuǎn)變地址映射某虛擬存儲器的用戶編程空間共32 個頁面， 每頁 1K ，主存為 16K。假定某時刻用戶頁表中已調(diào)入主存的頁面的虛頁號和物理頁號對照表如圖所示，則當虛地址為十六進制0A5C時，對應的物理地址是多少？虛頁號物理頁號041102437解：虛擬地址 (0A5C) 16 =(10*16 2 +5*16+12)10頁號 =INT2652/1K=2 ，其物理塊號為4頁內(nèi)偏移 =2652 mod 1K = 604物理地址為4*1K+604=(4700)10 =(125C) 16應用類型知識要點三：分頁存儲與數(shù)據(jù)訪問時間假定快表檢索時間為20ns，內(nèi)存訪問時間為100ns，則

19、若能在快表中找到CPU 給出的頁號， CPU 存取一個數(shù)據(jù)將需要(100+20)=120ns ，若不能在快表中找到CPU 給出的頁號，則為存取一個數(shù)據(jù)將需要(100+100+20)=220ns 。進一步說，若假定快表查找命中率為80%，則其有效訪問時間為120*80%+220*(1-80%)=140ns 。9應用類型知識要點四：頁面置換算法與缺頁次數(shù)最佳置換算法OPT( 向前看頁面引用序列)基本思想：選擇永不使用或是在最長時間內(nèi)不再被訪問( 即據(jù)現(xiàn)在最長時間才會被訪問)的頁面淘汰出內(nèi)存評價：理想化算法，具有最好性能( 對于固定分配方式，本法可保證獲得較低的缺頁率)，但實際上卻難于實現(xiàn)，故主要用

20、于算法評價參照70120304230321201701777222222222222227770000004440000000000111333333331111111某進程分配獲得三個物理塊采用預調(diào)頁策略 ( 區(qū)別預調(diào)頁策略與請求調(diào)頁策略)，前 3個頁面預先裝入第一行為頁面訪問(引用 ) 序列第二、三、四行為內(nèi)存頁面分布情況，前三列頁面預先裝入缺頁中斷次數(shù)為6 次，缺頁率30% 缺頁率 =(發(fā)生缺頁次數(shù) /頁面序列長度 )*100%先進先出置換算法FIFO( 向回看頁面分布情況)基本思想：選擇最先進入內(nèi)存即在內(nèi)存中駐留時間最久的頁面換出到外存。進程已調(diào)入內(nèi)存的頁面按進入先后次序鏈接成一個隊列

21、，并設置替換指針以指向最老頁面。評價：簡單直觀，但不符合進程實際運行規(guī)律，性能較差，故實際應用極少。70120304230321201701777222244400000007770000333222221111100111100033333222221某進程分配獲得三個物理塊采用預調(diào)頁策略 ( 區(qū)別預調(diào)頁策略與請求調(diào)頁策略)，前 3個頁面預先裝入第一行為頁面訪問(引用 ) 序列第二、三、四行為內(nèi)存頁面分布情況，前三列頁面預先裝入缺頁中斷次數(shù)為12 次，缺頁率68% 缺頁率 =(發(fā)生缺頁次數(shù) /頁面序列長度 )*100%最近最久未使用置換算法LRU( 向回看頁面引用序列)(硬件支持 )基本思想

22、：以“最近的過去”作為“最近的將來”的近似，選擇最近一段時間最長時間未被訪問的頁面淘汰出內(nèi)存。評價：適用于各種類型的程序，性能較好，但需要較多的硬件支持。70120304230321201701777222244400011111110000000033333300000111333222222222777某進程分配獲得三個物理塊10采用預調(diào)頁策略( 區(qū)別預調(diào)頁策略與請求調(diào)頁策略)，前 3 個頁面預先裝入第一行為頁面訪問(引用 ) 序列第二、三、四行為內(nèi)存頁面分布情況，前三列頁面預先裝入缺頁中斷次數(shù)為9 次，缺頁率45% 缺頁率 =(發(fā)生缺頁次數(shù) /頁面序列長度 )*100%簡單 CLOCK置

23、換算法 (NRU)( 硬件支持 )改進型 CLOCK置換算法 (硬件支持 )評價：與簡單CLOCK 算法相比，可減少磁盤的I/O 操作次數(shù)，但淘汰頁的選擇可能經(jīng)歷多次掃描(最多 3 輪加 1 次 )，故實現(xiàn)算法自身的開銷增大。最少使用置換算法(硬件支持 )基本思想：為內(nèi)存各頁設置一個以為寄存器用于記錄對應被訪問頻率。選擇在最近時期使用最少的頁面作為淘汰頁。評價：鑒于僅用一位寄存器有限各位來記錄頁面使用會導致訪問一次與訪問多次的等效性，本算法并不能真實全面地反映頁面適用情況。應用類型知識要點五：文件結(jié)構(gòu)與記錄檢索次數(shù)索引順序文件組織方式檢索開銷分組大小兩級索引順序文件組織方式主文件分組大小低級索

24、引表分組大小檢索開銷順序文件 (定長記錄順序文件/變長記錄順序文件)1 邏輯記錄的排序 (與關(guān)鍵字次序一致與否 ) 串結(jié)構(gòu)與順序結(jié)構(gòu)2 順序文件讀寫操作讀寫指針 RWptr 對應記錄邏輯地址定長記錄 RWptr+=recordLength變長紀錄 RWptr+=currentRecordLength( 無法實現(xiàn)隨機存取 )3 順序文件評析適于批量存取及磁帶介質(zhì)交互應用場合單個記錄操作低效索引文件組織及檢索機制(主要解決變長記錄文件無法實現(xiàn)隨機存取問題)記錄號本身的物理含義很弱，強調(diào)真正具有物理含義的關(guān)鍵字索引表本身是定長記錄順序文件索引順序文件檢索效率分析對于擁有N 條記錄的主數(shù)據(jù)文件，若基于

25、順序查找法來檢索具有指定關(guān)鍵字的記錄，11不同文件組織方式下的系統(tǒng)檢索開銷比較(假設不存在查找失敗的情況)1 順序文件組織方式 (N+1)/2 條 (順序查找 )2 索引文件組織方式 (N+1)/2 條 (順序查找 )3索引順序文件組織方式N +1(分組大小N 記錄，此時檢索效率最高)4 舉例說明 (N=10000)基于多級索引的索引順序文件 (分組大小 3 N )建立多級索引以進一步提高檢索效率6舉例說明 (N=10)1 索引順序文件組織方式檢索開銷 1001 條分組大小 1000 條記錄2 兩級索引順序文件組織方式主文件分組大小 100 條記錄低級索引表分組大小 100 條記錄檢索開銷 1

26、51.5 條應用類型知識要點六：文件分配表占用空間關(guān)鍵計算盤塊總數(shù)(實際操作系統(tǒng)按簇分配，這里按盤塊分配)磁盤有多少個盤塊，F(xiàn)AT 中就有多少個表項(前提是按盤塊分配 )FAT 表項應足以表示最大的盤塊號文件分配表空間開銷計算設定盤塊大小為 1KB對于 1.2M 的軟盤，共有盤塊 1.2M/1KB=1.2K(2 8 ,212 )(取 4 的倍數(shù)且較大的那個 )故文件分配表表項取12 位即 1.5B所以 FAT 共需空間 1.2K*1.5B=1.8KB對于 200M 的硬盤，共有盤塊 200M/1KB=200K(216,220 )故文件分配表表項取20 位即 2.5B所以 FAT 共需空間200

27、K*2.5B=500KB應用類型知識要點七：索引分配與文件最大長度兩級 /多級索引分配基本思想12對于太大的文件和索引塊太多時，直接用鏈接指針來鏈接索引塊的方法顯然是低效的，為此應引入多級索引分配方式允許文件最大長度兩級索引、盤塊大小1KB 、盤塊號占4B，則一個索引塊可含1KB/4B=256 個盤塊號，于是兩級索引最多可含256*256=64K 個盤塊號，允許文件最大長度為64MB混合分配方式 (UNIX系統(tǒng) 4KB 、 4MB 、 4GB 、4TB)直接尋址直接地址項存放對應文件數(shù)據(jù)的盤塊的盤塊號盤塊大小 4KB 、盤塊號占 4B ，則支持長度在 4KB*10=40KB 以內(nèi)的文件一次間接

28、尋址addr(10)指向?qū)募囊患壦饕龎K一級索引塊可含 4KB/4B=1K 個盤塊號，故支持長度在 (4KB*1K=4MB)+40KB 以內(nèi)的文件多次間接尋址addr(11)、 i.addr(12) 分別指向?qū)募膬杉壦饕腿壦饕龎K，所以支持的文件長度可達(4KB*1K*1K*1K=4TB)+(4KB*1K*1K=4GB)+4MB+40KB應用類型知識要點八文件查找與磁盤啟動次數(shù)假定每次啟動磁盤只裝入一個目錄盤塊盤塊大小1KB ，文件目錄共3200 個 FCB引入索引結(jié)點前FCB 占 64B，每盤塊包含 16 個 FCB ，文件目錄共需占用 200 個盤塊，故查找一個文件平均需啟動磁

29、盤 100.5 次 (順序查找 )引入索引結(jié)點后FCB 占 16B(文件名和索引結(jié)點指針分別占用14B 和 2B) ，每盤塊包含64 個目錄項， 文件目錄共需占用50 個盤塊，故查找一個文件平均需啟動磁盤25.5+1 次 (順序查找，讀索引結(jié)點取地址信息只需一次，因為索引結(jié)點在外存上是連續(xù)存放的)應用類型知識要點九：銀行家算法及資源分配管理產(chǎn)生死鎖的必要條件1 互斥條件2 請求和保持條件3 不剝奪條件4 環(huán)路等待條件死鎖預防 (要求進程的資源分配是靜態(tài)的)死鎖預防的方法是使四個必要條件中的第 2、3、4 個條件之一不能成立， 來避免發(fā)生死鎖。至于條件 1，因為它是設備的固有特性所決定的，不僅不

30、能改變，還應加以保證。死鎖避免允許進程動態(tài)地申請資源，但系統(tǒng)在進行資源分配之前，應首先就資源分配的安全性進13行檢查，且僅當確認此次分配不會導致系統(tǒng)進入不安全狀態(tài)時才可分配，否則予以拒絕。死鎖避免基本概念安全狀態(tài)系統(tǒng)可按某種進程序列 ( 稱之為安全分配序列 )來為每個進程 Pi 分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程均能順利完成。不安全狀態(tài)系統(tǒng)無法找到一個安全分配序列的系統(tǒng)狀態(tài)。死鎖與狀態(tài)安全性之間的關(guān)系1. 并非所有不安全狀態(tài)都是死鎖狀態(tài)2. 當系統(tǒng)進入不安全狀態(tài)后，便 可能陷入死鎖3. 只要保證系統(tǒng)處于安全狀態(tài)，便可避免死鎖安全狀態(tài)及向不安全狀態(tài)的轉(zhuǎn)換資源名稱資源總數(shù)

31、可用資源量可用資源量磁帶機1232進程最大需求已分配 (尚需 )已分配 (尚需 )P1105(5)5(5)P242(2)2(2)P392(7)3(6)T0 時刻存在安全分配序列若在 T0 時刻應進程請求將所剩磁帶機中的1 臺分配給 P3，則系統(tǒng)進入不安全狀態(tài)(如上圖 )銀行家算法之數(shù)據(jù)結(jié)構(gòu)(下標 i 對應進程，下標j 對應資源 )可用資源向量 / 請求向量 mAvailablej=k表示系統(tǒng)現(xiàn)有k 個 Rj 類資源Requesti j=k 表示進程 Pi 請求 k 個 Rj 類資源最大需求矩陣 / 分配矩陣 /需求矩陣 n,mMaxi,j=k表示進程Pi 最多需要k 個 Rj 類資源Alloc

32、ationi,j=k表示進程 Pi 已分配 k 個 Rj 類資源Needi,j=k 表示進程Pi 尚需 k 個 Rj 類資源工作向量 m/Finish 布爾向量 nWorkj=k表示系統(tǒng) ”可 ”提供 k 個 Rj 類資源Finishi 表示進程 Pi 可否擁有足夠資源完成運行銀行家算法之主體算法1. 進程 Pi 發(fā)出資源請求 Requesti2.若非 RequestiNeedi ，出錯返回3.若非 RequestiAvailable ，則應使 Pi 等待并返回4. 系統(tǒng)試探性地滿足 Pi 請求，并作以下修改：Available=Available-Request iAllocationi=A

33、llocationi+Requesti14Needi=Needi-Request i5. 系統(tǒng)調(diào)用 安全性算法 進行資源分配檢查， 若安全則執(zhí)行分配， 否則恢復試探分配前狀態(tài)，并使 Pi 等待銀行家算法之安全性子算法另 Work=Available ， Finish=FALSE從進程集合中查找一個滿足Finishi=FALSE且 NeediWork 的進程。若找到，則可假定Pi 能獲得所需資源并順利執(zhí)行，故有：Work=Work+AllocationiFinishi=TRUE然后重復執(zhí)行第2 步；否則轉(zhuǎn)至第3 步執(zhí)行如果 Finish=TRUE ，則表示系統(tǒng)處于安全狀態(tài)；否則系統(tǒng)處于不安全狀態(tài)

34、銀行家算法應用舉例之一(無任何進程發(fā)出資源申請)MAXAllocationNeedWorkAllocation進程+WorkFinishABCABCABCABCA B CP07530107437457554TRUEP13222001223325321TRUEP29023026007551057TRUE5P32222110115327432TRUEP44330024317437453TRUE系統(tǒng)資源總量 AvailableA,B,C=10,5,7T0 時刻 Available A,B,C=3,3,2安全分配序列？1.Work= Available=3,3,2可滿足 P1 或 P3，先滿足P1(如果 P1 走不通，再看P3)2.