操作系統(tǒng)復(fù)習(xí)

Chap.1概述操作系統(tǒng)的定義、功能、特征操作系統(tǒng)是一種系統(tǒng)軟件，是假設(shè)干程序模塊所的集合； 它負責(zé)管理和控制計算機系統(tǒng)的硬件、軟件資源的分配、調(diào)度和管理，使系統(tǒng)高效、平安地運行；為用戶提供簡單、直觀、靈活的用戶接口和使用環(huán)境，以方便用戶對計算機系統(tǒng)的使用。 操作系統(tǒng)的主要功能：處理機管理、進程管理、存儲管理、設(shè)備管理、文件管理、作業(yè)管理、用戶接口操作系統(tǒng)的類型及特點，操作系統(tǒng)的構(gòu)成及各模塊功能三種用戶接口處理機的2種工作狀態(tài)及設(shè)置原因，系統(tǒng)調(diào)用的機制處理機的工作狀態(tài)主要有內(nèi)核態(tài)和用戶態(tài)兩種。設(shè)置這兩種狀態(tài)主要是為了保護操作系統(tǒng)內(nèi)核不受用戶程序的干擾和影響，使計算機系統(tǒng)具有穩(wěn)定性、可靠性、平安性等特點。因為設(shè)置這兩種工作狀態(tài)后，用戶編寫的程序都運行在用戶態(tài)，只能執(zhí)行非特權(quán)指令，不能直接讀寫影響系統(tǒng)狀態(tài)的CPU存放器、外部設(shè)備存放器的指令、不能直接訪問和使用系統(tǒng)資源，而只能通過操作系統(tǒng)才能訪問這些資源；而操作系統(tǒng)程序運行在核心態(tài)，可以執(zhí)行CPU的任何指令，實施資源管理。術(shù)語：多道程序設(shè)計、并發(fā)、吞吐量、分時、實時硬件：構(gòu)成計算機的各種有形的物理裝置、部件或設(shè)備軟件：與計算機進行數(shù)據(jù)處理有關(guān)的計算機程序、數(shù)據(jù)、過程、規(guī)那么、文檔資料的總稱多道程序設(shè)計：可以支持多道程序同時在內(nèi)存中并發(fā)執(zhí)行的計算機系統(tǒng)并發(fā)：多個活動同時處于執(zhí)行狀態(tài)，每個活動都已開始執(zhí)行，卻都尚未完成，這種執(zhí)行方式稱為并發(fā)吞吐量：計算機系統(tǒng)在單位時間內(nèi)完成的作業(yè)數(shù)分時：操作系統(tǒng)將CPU執(zhí)行時間劃分成一個個時間片，輪流分配給各個進程使用，各個進程執(zhí)行完一個時間片，排到等待隊列，等待分配下一個時間片。時間片的大小使系統(tǒng)對每個進程的響應(yīng)保持在用戶能夠忍耐的限度內(nèi)實時：能夠在規(guī)定的時間內(nèi)對外部發(fā)生的事件給予響應(yīng)和處理的計算機系統(tǒng)稱為分時系統(tǒng)Chap.2進程管理術(shù)語：進程、程序、線程、進程互斥、進程同步、臨界區(qū)、臨界資源、原語進程組成，進程的三種根本狀態(tài)及其轉(zhuǎn)換〔習(xí)題第3題〕進程控制原語：創(chuàng)立、退出、等待、喚醒，這些原語完成的主要工作，進程控制塊的主要內(nèi)容〔列舉幾項〕線程的概念及與進程的關(guān)系，進程間通信的主要技術(shù)：管道、消息通信、共享內(nèi)存用P、V操作及信號量的方法解決同步互斥問題〔作業(yè)11、12、13題〕11.設(shè)系統(tǒng)中只有一臺打印機，有三個用戶的程序在執(zhí)行過程中都要使用打印機輸出計算結(jié)果。設(shè)每個用戶程序?qū)?yīng)一個進程。問：這三個進程間有什么樣的制約關(guān)系？試用P、V操作寫出這些進程使用打印機的算法。答：(1)三個進程間的關(guān)系是互斥關(guān)系。(2)進程間同步算法如下：設(shè)置一個互斥信號量mutex來協(xié)調(diào)各進程對打印機的使用，初值為1。用戶進程1：…P(mutex);打印計算結(jié)果1；V(mutex);…用戶進程2：…P(mutex);打印計算結(jié)果2；V(mutex);…用戶進程3：…P(mutex);打印計算結(jié)果3；V(mutex);…12.(1)有錯(2)有錯13.(1)可用3個進程完成：Pa：從卡片機讀信息，并逐一輸入到緩沖區(qū)B1中Pb：從緩沖區(qū)B1讀信息，加工處理后再搬到緩沖區(qū)B2中P3：從緩沖區(qū)B2讀信息，并在打印機上印出(2)這些進程間為同步關(guān)系(3)同步算法：初值：empty1=empty2=1;full1=full2=0;Pa：While(1){從卡片機讀數(shù)據(jù)；P(Empty1);將數(shù)據(jù)寫入緩沖區(qū)B1；V(Full1);}Pb：While(1){P(Full1);從緩沖區(qū)B1讀數(shù)據(jù)；V(Empty1)加工數(shù)據(jù)P(Empty2);將加工后的數(shù)據(jù)寫緩沖區(qū)B2；V(Full2);}Pc：While(1){P(Full2);從緩沖區(qū)2讀數(shù)據(jù)；V(Empty2);打印信息；}P、V原語的作用，信號量的含義C三級調(diào)度及功能、含義，作業(yè)調(diào)度與進程調(diào)度的關(guān)系，計算作業(yè)及進程周轉(zhuǎn)時間，常用調(diào)度算法：FCFS、短作業(yè)優(yōu)先、輪轉(zhuǎn)法、響應(yīng)比高優(yōu)先，算法的特點(習(xí)題2、3、7、10)10.〔1〕RRRR123420468101214165FCFS182012342046810121416518201234204681012141651820非搶占優(yōu)先級(2)作業(yè)名12345平均周轉(zhuǎn)時間FCFS1010111115RR1915110非搶占式優(yōu)先級101811814〔3〕作業(yè)名12345平均帶權(quán)周轉(zhuǎn)時間FCFS110115RR112非搶占式優(yōu)先級118872.高級調(diào)度與低級調(diào)度的主要功能是什么?為什么要引入中級調(diào)度?3.處理機調(diào)度一般可分為哪三級?其中哪一級調(diào)度必不可少?為什么?7.作業(yè)調(diào)度與進程調(diào)度之間有什么差異?二者間如何協(xié)調(diào)工作?C1、術(shù)語：程序地址、物理地址、地址重定位、快表、碎片、內(nèi)碎片、外碎片、存儲抖動與工作集2、分區(qū)式內(nèi)存管理的思想〔3種適應(yīng)算法〕3、分頁式內(nèi)存管理〔學(xué)會手工查頁表，計算物理地址〕，可從程序地址、物理地址中提取頁號、頁內(nèi)偏移量；地址位數(shù)確實定〔習(xí)題7，8，14，15，16，17，19，21〕7.設(shè)一個邏輯地址空間有8頁，每頁1024個字節(jié)，映像到有32塊的物理內(nèi)存上?！?〕邏輯地址需要用多少位表示？〔2〕物理地址需要用多少位表示？答：(1)log28+log21024=13位(2)log232+log21024=15位8.假設(shè)一個分頁系統(tǒng)的頁表存放在內(nèi)存中：〔1〕如果一次內(nèi)存訪問需要花費1.2μs，那么存取一次數(shù)據(jù)至少要多少時間？〔2〕如果我們增加8個聯(lián)想存儲器，其命中率可達75%，那么有效內(nèi)存訪問時間是多少〔假設(shè)在聯(lián)想存儲器中找到該頁表項，那么認(rèn)為在聯(lián)想存儲器中查找時間為0〕？答：2×1.2us=2.4us××1.2+1.2=1.6us14.假定分頁存儲系統(tǒng)中有快表，多數(shù)活動頁表項都可收在其中。如果頁表還是放在內(nèi)存中，內(nèi)存訪問時間是1μs，假設(shè)快表的命中率是85%，那么有效存取時間是多少？假設(shè)命中率降為50%，那么有效存取時間為多少？答：如果快表命中率為85%，那么有效存取時間為：(1-0.85)×1us+1us=1.15us(1-0.5)×1＋1＝1.5us17.什么時候會發(fā)生缺頁？說明缺頁出現(xiàn)時操作系統(tǒng)所做的事情。答：缺頁時機：CPU發(fā)現(xiàn)要訪問的內(nèi)存頁面不在內(nèi)存時缺頁時操作系統(tǒng)所作的工作：(1)轉(zhuǎn)缺頁中斷效勞程序(2)取得缺頁內(nèi)存地址和頁面所在輔存地址(3)在內(nèi)存中找到一個空閑物理塊(4)從輔存調(diào)入所需頁面(5)填修改引起缺頁指令內(nèi)存地址所在頁面在頁表：物理塊號為空閑物理塊號，頁面狀態(tài)位為存在21.一個操作系統(tǒng)支持分頁虛存，所用處理機的周期時間是1μs，頁面大小是1000字，分頁設(shè)備是磁鼓，它每分鐘轉(zhuǎn)3000圈，傳輸速率是每秒1000000字。由系統(tǒng)測得下述統(tǒng)計結(jié)果：〔1〕所執(zhí)行的全部指令中有0.1%存取的頁面不是當(dāng)前的頁面。〔2〕存取另外頁面的指令，它們所存取的頁面有80%已在內(nèi)存?！?〕當(dāng)請求一個新頁面時，所置換頁面有50%在此期間修改正。設(shè)系統(tǒng)中只運行這一個程序，當(dāng)磁鼓進行傳送時，處理機空轉(zhuǎn)等待。在上述條件下計算這個系統(tǒng)的有效指令時間〔執(zhí)行一條指令所需的平均時間〕答：1個頁面從外存?zhèn)鞯絻?nèi)存的時間：1000÷10-6＝10-3s＝1ms存取當(dāng)前頁面中內(nèi)存單元的時間：1us×99.9%≈10-6s存取不在當(dāng)前頁面中內(nèi)存單元〔但單元已在內(nèi)存〕的時間：1us×0.1%×80%≈10-9s存取不在當(dāng)前頁面中內(nèi)存單元〔但單元不在內(nèi)存，被置換頁面不需寫回〕的時間：1ms×0.1%×20%×50%=10-7s存取不在當(dāng)前頁面中內(nèi)存單元〔但單元不在內(nèi)存，被置換頁面需寫回〕的時間：2ms×0.1%×20%×50%=2×10-7s有效存取時間為:10-6s+10-9s+10-7s+2×10-7s=1.3us16.考慮下面存儲訪問序列，該程序有460字：10，11，104，170，73，309，185，245，246，434，458，364設(shè)頁面大小是100字，請給出訪問順序。又設(shè)該程序根本可用內(nèi)存是200字，采用FIFO置換算法，找出其缺頁率。如果我們采用LRU置換算法，缺頁率是多少？如果采用最優(yōu)置換算法，其缺頁率又是多少？19.考慮下述頁面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6當(dāng)內(nèi)存塊分別為1，2，3，4，5，6或7時，試問LRU、FIFO、OPT這三種置換算法的缺頁各出現(xiàn)多少次？注意，所有內(nèi)存塊最初都是空的，所以但凡第一次用到的頁面都產(chǎn)生一次缺頁4、分段式內(nèi)存管理〔習(xí)題24〕24.考慮如下段表：下述邏輯地址的物理地址是什么？〔1〕0，430；〔2〕1，10；〔3〕1，11；〔4〕2，500；〔5〕3，400；〔6〕4，112。答：219+430=6492300+10=23102300+11=2311∵500>100，∴發(fā)生地址越界1327＋400＝1727∵112>96，∴發(fā)生地址越界5頁面替換〔淘汰算法〕〔OPT、LRU、FIFO、NUR〕，缺頁中斷處理過程，計算內(nèi)存訪問時間；Chap.5文件系統(tǒng)1．文件系統(tǒng)的功能2.術(shù)語：文件邏輯結(jié)構(gòu)、文件的物理結(jié)構(gòu)文件的邏輯組織有幾種形式及特點，文件的物理組織形式主要有哪幾種及優(yōu)缺點3.什么是文件控制塊?有哪些內(nèi)容？它與文件有何關(guān)系？4．習(xí)題16、1716.有些文件系統(tǒng)中采用“文件控制塊分解法”，即文件目錄與其控制信息分開存放。假設(shè)目錄文件存放在磁盤上，每個盤塊為512字節(jié)。文件控制塊占64字節(jié)，其中文件名占8字節(jié)。通常將文件控制塊分解為兩個局部，第一局部占10字節(jié)〔包括文件名和文件內(nèi)部號〕，第二局部占56字節(jié)〔包括文件內(nèi)部號和文件其他描述信息〕?！?〕假設(shè)某一目錄文件共有254個文件控制塊，試分別給出采用分解法前和分解法后，查找該目錄文件的某個文件控制塊的平均訪問磁盤次數(shù)?！?〕一般情況，假設(shè)目錄文件分解前占用n個盤塊，分解后改用m個盤塊存放文件名和文件內(nèi)部號局部，請給出訪問磁盤次數(shù)減少的條件。答：〔1〕分解前：目錄大?。?4×254＝16256字節(jié)查找目錄文件的某個文件控制塊的平均訪問磁盤次數(shù)：分解后：目錄大小：10×254＝2540查找文件目錄的平均訪盤次數(shù)：根據(jù)文件目錄的文件控制塊號〔索引節(jié)點號〕訪存次數(shù)為1總共訪盤次數(shù)：3＋1＝4次〔2〕分解前訪盤次數(shù)：(1＋n)/2分解后訪盤次數(shù)：(1+m)/2+1訪問磁盤次數(shù)減少的條件：(1＋n)/2>(1+m)/2+1即：n>m+217.在UNIX系統(tǒng)中，試問：〔1〕有哪幾種常用類型的文件？〔2〕試描述“翻開文件”和“關(guān)閉文件”系統(tǒng)調(diào)用的作用及主要實現(xiàn)過程?！?〕假設(shè)盤塊為1KB，每塊可放256個地址，如何將以下文件的字節(jié)偏移量轉(zhuǎn)換為物理地址？〔要求寫出計算過程?！尝?000②18000③420000答：普通文件、目錄文件、設(shè)備文件翻開文件的作用：實現(xiàn)系統(tǒng)對文件的檢索、權(quán)限驗證、讀/寫指針共享等操作，改善文件系統(tǒng)的性能，翻開文件的過程：1〕查找文件目錄。如找到，那么把對應(yīng)的文件控制塊調(diào)入內(nèi)存的活動文件控制塊區(qū)。2〕檢查翻開文件的合法性。如果flags與文件使用屬性不符，那么不能翻開該文件，返回fd為-1，表示不成功；如果權(quán)限相符，那么建立內(nèi)部控制結(jié)構(gòu)〔如UNIX系統(tǒng)中的用戶翻開文件表、系統(tǒng)翻開文件表和活動Ⅰ節(jié)點表等〕之間的通路聯(lián)系，返回fd值關(guān)閉文件的作用：一個是防止對翻開文件的非法操作，起保護文件的作用；為了有效地使用系統(tǒng)資源。因為一個進程能夠同時翻開的文件數(shù)是受限制的，當(dāng)它不再使用某個翻開文件時，那么應(yīng)關(guān)閉它，騰出其內(nèi)部控制結(jié)構(gòu)所占用的內(nèi)存空間，關(guān)閉文件的過程：將尚存在于緩沖區(qū)的數(shù)據(jù)寫入文件更新將內(nèi)存文件控制塊的內(nèi)容寫入磁盤文件控制塊，更新文件的長度、修改日期等信息回收文件控制塊所占用的內(nèi)存(3)偏移量為9000的物理地址計算方法：物理塊號的計算方法是：計算邏輯塊號：因為9000/1024=8….808邏輯塊號為82〕計算在物理塊號由于8<10，所以可從直接塊8處查到物理塊號偏移量為1800的物理地址計算方法：1〕計算邏輯塊號：因為18000/1024=17….592邏輯塊號為172〕檢查在幾次間接指針下由于17－10<255，所以在一次間接指針的索引下3〕計算在一次間接索引塊中的指針號17－10＝7在一次間接索引塊的第7個指針元素中查到其物理塊號偏移量為420000的物理地址計算方法：1〕計算邏輯塊號：因為420000/1024=410….160邏輯塊號為4102〕檢查在幾次間接指針下由于410－10－256＝144<2562，所以在二次間接指針的索引下3〕計算在二次間接索引塊中的指針號144÷256＝0…144在二次間接索引塊的第0個指針指向的索引塊的第144個指針處查到物理塊號C設(shè)備I/O控制方式(3種:直接I/O，中斷控制、DMA控制)，術(shù)語：SPOOLING技術(shù)，通道、控制器、設(shè)備SPOOLing技術(shù)是在計算機控制下通過聯(lián)機的外圍設(shè)備同時操作，其實質(zhì)是用多個磁盤文件來代替獨占的輸入輸出設(shè)備，當(dāng)進程申請使用獨占設(shè)備時，就分配一個文件代替設(shè)備給其使用，可以防止因競爭獨占設(shè)備而引起死鎖或阻塞等待等問題。設(shè)備驅(qū)動程序的結(jié)構(gòu)框架與功能、接口，磁盤調(diào)度〔FCFS、電梯調(diào)度〕〔習(xí)題11，12〕SPOOLing系統(tǒng)是怎樣實現(xiàn)虛擬設(shè)備的？采用SPOOLing技術(shù)時，SPOOLing系統(tǒng)將進程需要處理的數(shù)據(jù)預(yù)先輸入到磁盤文件中，當(dāng)進程需要從輸入設(shè)備輸入信息時，就改從磁盤文件讀取數(shù)據(jù)；進程需要輸出信息時，先將輸出信息寫入一個磁盤文件，然后SPOOLing系統(tǒng)在后臺將各個進程的輸出信息從磁盤文件一一輸出到外部設(shè)備。在這里，SPOOLing系統(tǒng)用磁盤文件代替設(shè)備分配給進程使用，而進程卻感覺到自己分配到獨占的外部設(shè)備，而這種設(shè)備不是真實的獨占設(shè)備，而是一個磁盤文件，所以稱為虛擬設(shè)備。12.假定一個動頭盤有200道，編號從0～199。當(dāng)前磁頭正在143道上效勞，并且剛剛完成了125道的請求。如果請求隊列的先后順序是：86，147，91，177，94，150，102，175，130問：為完成上述請求，以下算法各自磁頭移動的總量是多少？〔1〕FCFS；〔3〕電梯法；答：(1)(143-86)+(147-86)+(147-91)+(177-91)+(177-94)+(150-94)+(150-102)+(175-102)+(175-130)=565(2)147-143+150-147+175-150+177-150+177-130+130-102+102-91+91-86=30+91=121C死鎖的四個必要條件，死鎖預(yù)防的方法：有序資源分配法、靜態(tài)資源分配法、虛擬設(shè)備法死鎖防止的根本思想：銀行家算法死鎖檢測與恢復(fù)方法，死鎖與饑餓，習(xí)題14、1514.設(shè)有三個進程p1、p2、p3，各按如下所示順序執(zhí)行程序代碼：

進程p1進程p2進程p3↓↓↓p(s1)p(s3)p(s2)p(s2)p(s1)p(s3)v(s1)v(s3)v(s2)v(s2)v(s1)v(s3)↓↓↓在執(zhí)行時能否產(chǎn)生死鎖？如可能死鎖，請說明在什么情況下會產(chǎn)生死鎖？并給出一個防止死鎖產(chǎn)生的修改方法。其中