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

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

進(jìn)程p1進(jìn)程p2進(jìn)程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í)行時(shí)能否產(chǎn)生死鎖？如可能死鎖，請(qǐng)說(shuō)明在什么情況下會(huì)產(chǎn)生死鎖？并給出一個(gè)防止死鎖產(chǎn)生的修改方法。其中