操作系統(tǒng)總結(jié)2005

1、操作系統(tǒng)總結(jié)林樹寬第一章 緒論操作系統(tǒng)的概念定義從科普、功能、用戶、管理員、軟件的觀點(diǎn)理解操作系統(tǒng)操作系統(tǒng)發(fā)展歷史手工、批處理、多道程序、分時(shí)、實(shí)時(shí)操作系統(tǒng)的基本類型批處理、分時(shí)、實(shí)時(shí)、個(gè)人計(jì)算機(jī)、網(wǎng)絡(luò)、分布式、嵌入式第一章 緒論操作系統(tǒng)的功能處理機(jī)管理、存儲(chǔ)管理、設(shè)備管理、文件管理、用戶接口操作系統(tǒng)的特征并發(fā)、共享、虛擬、異步現(xiàn)代操作系統(tǒng)特征微內(nèi)核、多線程、對(duì)稱多處理、分布式、面向?qū)ο蟮诙?用戶接口與作業(yè)管理程序的啟動(dòng)和結(jié)束程序的啟動(dòng)（命令方式、批處理方式、EXEC方式、硬件裝入程序、自啟程序）程序的結(jié)束（正常結(jié)束、異常結(jié)束）作業(yè)的基本概念作業(yè)（用戶角度、系統(tǒng)角度）作業(yè)組織（作業(yè)、說明書、

2、控制語言）第二章 用戶接口與作業(yè)管理作業(yè)的建立包括：作業(yè)的輸入、作業(yè)控制塊的建立作業(yè)輸入方式聯(lián)機(jī)輸入、脫機(jī)輸入、直接耦合、Spooling、網(wǎng)絡(luò)作業(yè)控制塊的建立用戶接口程序級(jí)接口、操作級(jí)接口、圖形用戶接口系統(tǒng)調(diào)用（類、功能、實(shí)現(xiàn)過程）第三章 進(jìn)程管理進(jìn)程的概念程序的順序執(zhí)行和并發(fā)執(zhí)行定義、條件、特點(diǎn)進(jìn)程的定義、特性、與程序的區(qū)別進(jìn)程的描述進(jìn)程的組成（程序+數(shù)據(jù)+PCB）進(jìn)程控制塊PCB（作用、所包含信息）進(jìn)程上下文（用戶級(jí)、寄存器級(jí)、系統(tǒng)級(jí)）第三章 進(jìn)程管理進(jìn)程的描述PCB的組織方式（鏈表、索引表）進(jìn)程的狀態(tài)及轉(zhuǎn)換核心態(tài)和用戶態(tài)內(nèi)存中3種基本狀態(tài)（轉(zhuǎn)換、條件）擴(kuò)展：3狀態(tài)、5狀態(tài)、7狀態(tài)（狀態(tài)

3、、轉(zhuǎn)換、條件、數(shù)據(jù)結(jié)構(gòu)等）進(jìn)程控制功能、原語、UNIX進(jìn)程管理第三章 進(jìn)程管理線程進(jìn)程與線程的關(guān)系線程引入的作用線程的應(yīng)用線程的狀態(tài)及轉(zhuǎn)換操作系統(tǒng)對(duì)線程的實(shí)現(xiàn)方式進(jìn)程與線程的比較線程舉例第三章 進(jìn)程管理進(jìn)程的互斥與同步進(jìn)程間的關(guān)系（同步、互斥）互斥算法（臨界資源的使用）信號(hào)量（信號(hào)量和P、V原語）經(jīng)典進(jìn)程同步問題（特別復(fù)雜的互斥與同步）管程（定義、例子、實(shí)現(xiàn)、結(jié)構(gòu)、與進(jìn)程的異同）第三章 進(jìn)程管理進(jìn)程間通信進(jìn)程間通信類型消息緩沖共享存儲(chǔ)區(qū)管道消息套接字第三章 進(jìn)程管理死鎖死鎖的定義、現(xiàn)象、發(fā)生原因、發(fā)生條件死鎖的預(yù)防、避免、死鎖的檢測(cè)與恢復(fù)解決死鎖的綜合方法第四章 處理機(jī)調(diào)度分級(jí)調(diào)度調(diào)度層次（與

4、狀態(tài)轉(zhuǎn)換、與時(shí)間周期、操作系統(tǒng)類型聯(lián)系）作業(yè)與進(jìn)程的關(guān)系（從調(diào)度的角度）作業(yè)調(diào)度作業(yè)調(diào)度功能作頁調(diào)度中狀態(tài)的轉(zhuǎn)換目標(biāo)與性能第四章 處理機(jī)調(diào)度進(jìn)程調(diào)度進(jìn)程調(diào)度的功能、時(shí)機(jī)、上下文切換、性能評(píng)價(jià)調(diào)度算法先來先服務(wù)（FCFS）短作業(yè)優(yōu)先（SJF）最高響應(yīng)比優(yōu)先（HRR）時(shí)間片輪轉(zhuǎn)（RR）多級(jí)隊(duì)列第四章 處理機(jī)調(diào)度調(diào)度算法優(yōu)先級(jí)靜態(tài)、動(dòng)態(tài)優(yōu)先級(jí)線性優(yōu)先級(jí)（SRR）多級(jí)反饋隊(duì)列調(diào)度算法性能指標(biāo)調(diào)度算法應(yīng)用舉例第四章 處理機(jī)調(diào)度實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度任務(wù)分類實(shí)時(shí)調(diào)度特點(diǎn)實(shí)時(shí)調(diào)度算法靜態(tài)表驅(qū)動(dòng)靜態(tài)優(yōu)先級(jí)驅(qū)動(dòng)的可剝奪調(diào)度動(dòng)態(tài)分析調(diào)度無保障動(dòng)態(tài)調(diào)度第四章 處理機(jī)調(diào)度多處理機(jī)調(diào)度與單處理機(jī)調(diào)度的區(qū)別對(duì)稱式多處理系統(tǒng)的調(diào)

5、度非對(duì)稱式多處理系統(tǒng)的調(diào)度成組調(diào)度專用處理機(jī)的調(diào)度第五章 存儲(chǔ)管理存儲(chǔ)管理的功能和目標(biāo)虛擬存儲(chǔ)器存儲(chǔ)管理的功能地址變換內(nèi)外存數(shù)據(jù)傳輸?shù)目刂苾?nèi)存的分配與回收內(nèi)存信息的共享與保護(hù)第五章 存儲(chǔ)管理分區(qū)存儲(chǔ)管理原理固定分區(qū)動(dòng)態(tài)分區(qū)分配、釋放最先匹配下次匹配最佳匹配最壞匹配碎片及解決第五章 存儲(chǔ)管理覆蓋與交換原理、實(shí)現(xiàn)、特點(diǎn)頁式和段式存儲(chǔ)管理簡(jiǎn)單頁式（原理、數(shù)據(jù)結(jié)構(gòu)、地址變換、特點(diǎn)）簡(jiǎn)單段式（原理、數(shù)據(jù)結(jié)構(gòu)、地址變換、特點(diǎn)）簡(jiǎn)單頁式、段是管理的比較第五章 存儲(chǔ)管理虛擬存儲(chǔ)器原理虛擬頁式與簡(jiǎn)單頁式管理的關(guān)系缺頁中斷請(qǐng)求調(diào)入和預(yù)調(diào)入虛擬段式與簡(jiǎn)單段式的關(guān)系特點(diǎn)第五章 存儲(chǔ)管理虛擬存儲(chǔ)器段頁式地址變換高速聯(lián)想

6、寄存器調(diào)入、分配策略置換算法（最佳OPT、最近最久未使用LRU、先進(jìn)先出FIFO、輪轉(zhuǎn)、最不常用LFU）第六章 文件系統(tǒng)引言文件管理的目的基本概念（文件、目錄、文件分類）文件系統(tǒng)的結(jié)構(gòu)和功能元素文件的組織文件的組織邏輯結(jié)構(gòu)物理結(jié)構(gòu)第六章 文件系統(tǒng)文件目錄內(nèi)容結(jié)構(gòu)別名的實(shí)現(xiàn)（硬鏈接、符號(hào)鏈接）文件和目錄的使用文件的訪問文件的控制目錄管理偽文件第六章 文件系統(tǒng)文件共享和訪問控制存取控制共享訪問權(quán)限并發(fā)訪問安全、可靠性第六章 文件系統(tǒng)文件存儲(chǔ)空間管理存儲(chǔ)設(shè)備空間分配磁盤空閑空間管理文件卷文件系統(tǒng)層次模型文件系統(tǒng)舉例（DOS、Windows、UNIX）第七章 設(shè)備管理引言外設(shè)管理的重要性外設(shè)的類型和特

7、征外設(shè)管理的目的和功能外設(shè)管理結(jié)構(gòu)I/O控制技術(shù)程序控制方式（查詢、中斷）DMA方式（工作原理、與中斷的區(qū)別）通道方式（定義、原理、3種通道、）第七章 設(shè)備管理緩沖技術(shù)緩沖技術(shù)的作用和目的單方向緩沖I/OCPU （單緩沖、雙緩沖、環(huán)形緩沖）緩沖池（3種隊(duì)列、4種操作）設(shè)備分配數(shù)據(jù)結(jié)構(gòu)分配原則分配方式假脫機(jī)第七章 設(shè)備管理設(shè)備控制設(shè)備控制過程設(shè)備控制實(shí)現(xiàn)方式I/O軟件的組成磁盤設(shè)備管理訪問時(shí)間調(diào)度策略（先進(jìn)先出、優(yōu)先級(jí)、后進(jìn)先出、短查找時(shí)間優(yōu)先、各種掃描算法）置換算法 生產(chǎn)者/消費(fèi)者問題 (the producer/consumer problem)問題描述：若干進(jìn)程通過有限的共享緩沖區(qū)交換數(shù)據(jù)

8、。其中，生產(chǎn)者進(jìn)程不斷寫入，而消費(fèi)者進(jìn)程不斷讀出；共享緩沖區(qū)共有N個(gè)；任何時(shí)刻只能有一個(gè)進(jìn)程可對(duì)共享緩沖區(qū)進(jìn)行操作。共享緩沖區(qū)生產(chǎn)指針消費(fèi)指針Producer 1Producer 2.Producer MConsumer 1Consumer 2.Consumer N滿空指針移動(dòng)方向 設(shè)信號(hào)量： full是“滿”數(shù)目，初值為0， empty是“空”數(shù)目，初值為N。實(shí)際上，full和 empty是同一個(gè)含義：full + empty = N mutex用于訪問緩沖區(qū)時(shí)的互斥，初值是1 ProducerP(empty);P(mutex);/進(jìn)入?yún)^(qū) one unit - buffer;V(mutex)

9、;V(full);/退出區(qū)ConsumerP(full);P(mutex);/進(jìn)入?yún)^(qū) one unit n時(shí)因此，如果在設(shè)計(jì)系統(tǒng)時(shí)，能預(yù)測(cè)到進(jìn)程并發(fā)執(zhí)行和申請(qǐng)資源量的情況，只要每個(gè)進(jìn)程所需資源的最大量不超過x,則可不必受任何的資源分配策略的限制，只要有空閑資源就可分配給申請(qǐng)者，系統(tǒng)不會(huì)有死鎖現(xiàn)象。習(xí)題有一頁式存儲(chǔ)管理系統(tǒng)，向用戶提供的邏輯地址空間最大為16頁，每頁2048字節(jié)，內(nèi)存共有8個(gè)存儲(chǔ)塊，問：邏輯地址至少應(yīng)為多少位？?jī)?nèi)存空間多大？有8頁的邏輯空間，每頁有1024字節(jié)，它們被映射到32塊的物理存儲(chǔ)區(qū)中，則邏輯地址的有效位（ ）位，物理地址至少是（ ）位。習(xí)題一分頁存儲(chǔ)管理系統(tǒng)，邏輯地址長(zhǎng)

10、度為16位，頁面大小為2048字節(jié)，對(duì)應(yīng)的頁表如下，邏輯地址0A5CH和2F6AH經(jīng)地址變換后的物理地址各是多少？習(xí)題物理地址8頁表長(zhǎng)度頁表地址控制寄存器頁號(hào)頁面號(hào)021328有效地址21C41C4頁式地址變換舉例250010000111000100給出段號(hào)和段內(nèi)地址，完成段式管理中的地址變換過程對(duì)于段號(hào)，段內(nèi)地址形式，計(jì)算0,430 1,10 2,500 3,400的內(nèi)存地址存取主存中的一條指令或數(shù)據(jù)至少要訪問幾次主存？段號(hào)段長(zhǎng)度主存起始地址01234660142005809621933009012371952段表起始地址段表地址寄存器虛擬地址11C4段號(hào)段內(nèi)地址段表段號(hào)始址01500134

11、0035C4內(nèi)存第2段頁表段地址寄存器段表長(zhǎng)度 段表始址頁號(hào) 其它 頁面 1 12 2 19 3 21 4 8 5 10第0段頁表頁號(hào) 其它 頁面 1 29 2段號(hào) 其它 頁表長(zhǎng)度 頁表始址 0 5 1024 1 7 1029 2 9 1036段表某進(jìn)程在內(nèi)存中分配三個(gè)頁面，初始為空，頁面走向?yàn)?，3，2，1，4，3，5，4，3，2，1，5。堆棧第五章 存儲(chǔ)管理第五章 存儲(chǔ)管理某os采用可變分區(qū)分配方法管理，用戶區(qū)主存512KB(0-511KB),自由區(qū)由空閑分區(qū)表管理。假設(shè)分配時(shí)采用分配自由區(qū)的低地址部分的方案，假設(shè)初始時(shí)全為空。對(duì)于下述申請(qǐng)次序：req(300KB),req(100KB),

12、release(300KB),req(150KB),req(30KB),req(40KB),req(60KB),release(30KB)1.采用首次適應(yīng)法，用戶區(qū)狀態(tài)。寫出空閑分區(qū)表。2.采用最佳適應(yīng)法，用戶區(qū)狀態(tài)。寫出空閑分區(qū)表。3.如再申請(qǐng)100KB，各有什么結(jié)果？編程實(shí)現(xiàn) P203-8。設(shè)索引表數(shù)組為index, 每個(gè)物理塊的塊號(hào)用m個(gè)字節(jié)表示，物理塊長(zhǎng)為PBL, 文件結(jié)構(gòu)為流式文件。給定字節(jié)偏移OFF,計(jì)算其所在的物理塊地址。解：令 k = int(PBL/m)Int Off2PBN(Off) k = int(PBL/m);lbn = Off / PBL;if lbn10 then

13、return indexlbn;Else I = (lbn-10) div k; J = (lbn-10) mod k; 讀文件的第 Index10+I 號(hào)塊的內(nèi)容 buf; return bufj; 40962284542031111150101367142891568241011109954952331452.33003333083274104289156757601331假定盤塊的大小為1KB，每個(gè)盤塊號(hào)占4個(gè)字節(jié)，文件索引節(jié)點(diǎn)中的磁盤地址明細(xì)表如圖所示，如何將下列文件的字節(jié)偏移量轉(zhuǎn)換為物理地址？1 9000 2 14000 3 350000解：（1） 字節(jié)偏移量為9000，此時(shí)邏輯塊號(hào)

14、為：9000/10248塊內(nèi)偏移量為：900081024808因邏輯塊號(hào)小于10，因此該塊為直接塊。其物理盤塊號(hào)為367，該塊中的第808字節(jié)即為文件的第9000字節(jié)（2） 字節(jié)偏移量為14000，此時(shí)邏輯塊號(hào)為：14000/102413塊內(nèi)偏移量為：14000131024688因邏輯塊號(hào)1013266，因此該塊為一次間接塊。 由圖可知，一次間接的盤塊號(hào)為428，從一次間接塊中讀出盤塊號(hào)表，查得其物塊號(hào)為952，該塊中的第688字節(jié)即為文件的第14000字節(jié)。(3)字節(jié)偏移量為350000，此時(shí)邏輯塊號(hào)為：350000/1024341塊內(nèi)偏移量為：3500003411024816因邏輯塊號(hào)26

15、634165802，因此該塊為二次間接塊。由圖可知，二次間接塊的盤塊號(hào)為9156。由于一個(gè)一次間接塊中可容納256個(gè)塊號(hào)，341-10-25675 因此，字節(jié)偏移量350000在二次間接塊的第0個(gè)一次間接塊的第75個(gè)表項(xiàng)中，其盤塊號(hào)為333，該塊中的第816字節(jié)即為文件的第350000字節(jié)。某磁盤有40個(gè)磁道，磁頭從一個(gè)磁道移至另一個(gè)磁道需要6ms。文件在磁盤上非連續(xù)存放，邏輯上相鄰數(shù)據(jù)塊的平均距離為13道，每塊的旋轉(zhuǎn)延遲時(shí)間及傳輸時(shí)間分別為100ms、25ms,問讀取一個(gè)100塊的文件需多少時(shí)間？一個(gè)樹形結(jié)構(gòu)的文件系統(tǒng)如圖所示，框?yàn)槟夸洠瑘@為文件?？煞襁M(jìn)行下列操作在目錄D中建立一個(gè)文件，命名

16、為A；將目錄C改名為A若E和G分別為兩個(gè)用戶的目錄用戶E欲共享文件Q，應(yīng)有什么條件，如何操作？在一段時(shí)間內(nèi)，用戶G主要使用文件S和T。為簡(jiǎn)便操作和提高速度，應(yīng)如何處理？用戶E欲對(duì)文件I加以保護(hù)，不許別人使用，能否實(shí)現(xiàn)？如何實(shí)現(xiàn)？根目錄ABCDEFGHIJKLMNOPQRST作業(yè)P202 7.1, 7.2, 7.3, 7.7, 7.8, 7.10, 7.11, 7.12, 7.13一個(gè)存儲(chǔ)與磁盤上的文件系統(tǒng)，其中的文件由大小512B的塊組成。假定每一個(gè)文件有一個(gè)文件目錄項(xiàng)，該目錄項(xiàng)包含此文件的名字、文件長(zhǎng)度以及第一塊（或第一索引塊）和最后一塊的位置，而且該目錄項(xiàng)位于內(nèi)存。對(duì)于索引結(jié)構(gòu)文件，該目錄項(xiàng)指明第一索引塊、該索引塊又依次指向511個(gè)文件塊且有一個(gè)指向下一個(gè)索引塊的指針。針對(duì)連續(xù)、鏈接、索引結(jié)構(gòu)的每一種，如果當(dāng)前位于邏輯塊10（即最后一個(gè)訪問的塊是邏輯塊10）且希望訪問邏輯塊4，那么，必須分別從磁盤上讀多少個(gè)物理塊？ 若磁頭的當(dāng)前位置為100磁道，磁頭正向磁道號(hào)增加的方向移動(dòng)?，F(xiàn)有一磁盤讀寫請(qǐng)求隊(duì)列：23，376，205，132，19，61，190，398，29，4，18，40。分別采用先來先服務(wù)、最短尋道時(shí)間優(yōu)先和掃描算法，平均尋道長(zhǎng)度各是多少？ 下一磁道 移動(dòng)磁道數(shù) 最少尋道優(yōu)先 掃描 23