軟件設(shè)計師之操作系統(tǒng)知識

1、操作系統(tǒng)知識 操作系統(tǒng)內(nèi)核的功能和基本組成功能：中斷處理、時鐘管理、存儲管理、設(shè)備管理還有與進程控制和管理有關(guān)的其他支撐功能。組成：與硬件緊密相關(guān)的功能模塊、運行頻率高的功能模塊以及公用的一些基本操作，這些常駐內(nèi)存部分即組成了操作系統(tǒng)內(nèi)核（Kernel）。 內(nèi)核與用戶程序的運行方式差別內(nèi)核操作段作為原語，不允許并發(fā)執(zhí)行； 內(nèi)核運行、中斷控制的基本知識 中斷控制是最基本的支撐功能，是操作系統(tǒng)運行的基礎(chǔ) 進程、線程等基本概念程序順序執(zhí)行和并發(fā)執(zhí)行的基本特征進程：是一個具有獨立功能的程序關(guān)于某個數(shù)據(jù)集合的一次運行活動，是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。線程：是進程內(nèi)一個相對獨立、可調(diào)度的執(zhí)行單

2、位，是進程中一個單一的控制線索。順序執(zhí)行：順序性、封閉性、可再現(xiàn)性。并發(fā)執(zhí)行：間斷性、失去封閉性、失去可再現(xiàn)性、程序與程序的執(zhí)行不再一一對應(yīng)。 進程的基本組成進程的基本狀態(tài)及狀態(tài)間的切換三態(tài)模型與五態(tài)模型從結(jié)構(gòu)上看：進程實體由程序、數(shù)據(jù)及進程控制塊3部分組成。進程的基本狀態(tài)：就緒態(tài)(Ready)、執(zhí)行態(tài)(Running)、阻塞態(tài)（Blocked）。狀態(tài)間轉(zhuǎn)換：就緒態(tài)執(zhí)行態(tài)：當(dāng)進程調(diào)度程序為之分配了處理器后。執(zhí)行態(tài)-就緒態(tài)：在進程的執(zhí)行過程中，因分配給它的一個時間片已經(jīng)用完或被更高優(yōu)先級的進程搶占，而不得不讓出處理器時。這是，原來占有處理器的進程將被中斷。執(zhí)行態(tài)-阻塞態(tài)：正在執(zhí)行的進程因等待某種

3、時間發(fā)生但尚未發(fā)生，或等待某個I/O完成單尚未完成而無法繼續(xù)執(zhí)行時。這個轉(zhuǎn)換時進程自行啟動的。阻塞態(tài)-就緒態(tài)：處于阻塞態(tài)的進程，若其等待的時間已經(jīng)發(fā)生或I/O已經(jīng)完成時。這個過程稱為“喚醒”是由其它進程啟動的。三態(tài)模型：五態(tài)模型： 進程間的通信同步與互斥、臨界資源、臨界區(qū)、信號量、PV操作II進程通信是指進程之間的信息交換。包括低級通信方式和高級通信方式：信號量機制為進程的低級通信機制；高級通信方式可歸結(jié)為：共享存儲區(qū)系統(tǒng)、管道通信系統(tǒng)和消息傳遞系統(tǒng)。共享存儲區(qū)方式：在內(nèi)存中開辟一塊共享存儲區(qū)域作為進程通信區(qū)。分為建立、附接、讀寫、斷接幾個步驟。常用于對通信速度有較高要求的場合。管道通信系統(tǒng)：

4、這是在文件系統(tǒng)上形成的，利用共享文件實現(xiàn)進程通信的一種方式。所謂管道是指用于連接多個讀寫進程，以實現(xiàn)它們之間通信的共享文件。首創(chuàng)于UNIX系統(tǒng)。此通信開銷小、交換信息量大且信息保存期長。但在通信過程中I/O操作的次數(shù)較多，同步和控制也較為復(fù)雜。消息傳遞系統(tǒng)：在單機系統(tǒng)、多機系統(tǒng)和網(wǎng)絡(luò)環(huán)境下，進程的高級通信廣泛采用消息傳遞方式。這種通信方式中，進程間的數(shù)據(jù)交換以消息為單位，在計算機網(wǎng)絡(luò)中，消息也成為報文。可分為直接通信和間接通信。1：直接通信：發(fā)送和接收進程都必須以顯示方式提供目標(biāo)進程標(biāo)識符，以表明向發(fā)送或從誰那里接收消息。通常，系統(tǒng)提供兩條通信原語：Send:將消息message發(fā)送個進程Re

5、ceiverReceive:接收由進程Sender發(fā)來的消息message.2:間接通信：進程之間需要通過某種中間實體來暫存消息。這一中間實體被形象地稱為信箱。當(dāng)兩個進程有一個共享信箱事，它們就能進行通信。一個進程可以分別與多個進程共享多個不同的信箱，這樣，一個進程可以同時和多個進程進行通信。操作系統(tǒng)提供了若干原語：用于創(chuàng)建和撤銷信箱、發(fā)送和接收消息等。臨界資源（CR）：一次僅允許一個進程使用的資源叫臨界資源。臨界區(qū)（CS）：每個進程中訪問臨界資源的那段程序代碼稱作臨界區(qū)。同步機制：空閑讓進、忙則等待、有限等待、讓權(quán)等待?；コ猓寒?dāng)一個進程進入臨界區(qū)使用臨界資源時，另外的進程必須等待；當(dāng)其退出后

6、，另一個進程才被允許進入其臨界區(qū)。這就是進程間的互斥關(guān)系。信號量：它是聯(lián)系某類臨界資源的數(shù)據(jù)結(jié)構(gòu)，不同取值表示臨界資源的不同狀態(tài)。按信號量 的用途的不同，可把信號量分為兩類：1：公用信號量，其初值僅允許取值為0或1，主要用于控制進程互斥地進入臨界區(qū)，也成為互斥信號量。2：私有信號量，其初值為初始資源數(shù)，主要用于控制進程間的同步運行，也成為同步信號量。PV操作：P即等待，V即發(fā)信號。 管程的概念I(lǐng) 進程調(diào)度方式及常用的進程調(diào)度算法II方式：非剝奪調(diào)度和剝奪調(diào)度1：非剝奪調(diào)度（非搶占方式）優(yōu)點：簡單、系統(tǒng)開銷小缺點：可能導(dǎo)致系統(tǒng)性能的惡化，表現(xiàn)為：（1）：當(dāng)一個緊急任務(wù)到達時，不恩能夠立即投入運行

7、，從而延誤時機。（2）：若干個后到的短進程，需要等待先到的長進程運行完畢后才能運行，致使短進程的周轉(zhuǎn)時間較長。它通常不適用于具有多個競爭的通用系統(tǒng)，但對于專用系統(tǒng)是很合理的。2：剝奪調(diào)度（搶占方式）剝奪原則：優(yōu)先權(quán)原則、短進程優(yōu)先原則、時間片原則進程調(diào)度算法：FCFS、短作業(yè)（進程）優(yōu)先調(diào)度算法（SJF）、時間片輪轉(zhuǎn)調(diào)度算法（RR）、高優(yōu)先權(quán)優(yōu)先調(diào)度算法（FPF）、最高響應(yīng)比優(yōu)先調(diào)度算法（HRN）、多級隊列調(diào)度算法（MQ）、多級反饋隊列調(diào)度算法（RRMF）。1、 FCFS很少作為進程調(diào)度的主調(diào)度算法，而常作為一種輔助調(diào)度算法。2、 SJF缺點：該算法對長作業(yè)（進程）不利。未考慮作業(yè)（進程）的緊

8、迫度。用戶可能有意或無意地縮短其作業(yè)（進程）的估計執(zhí)行時間，致使該算法不一定能真正做到短作業(yè)（進程）優(yōu)先調(diào)度。3、 RR的基本思想是讓每個進程在就緒隊列中等待的時間與享受服務(wù)的時間成正比。采用剝奪調(diào)度方式。系統(tǒng)將所有就緒進程按先進先出規(guī)則排成一個環(huán)形隊列，把CPU分配給隊首進程，并規(guī)定它執(zhí)行一個時間片。當(dāng)時間片用完，系統(tǒng)剝奪該進程的運行并將它送到就緒隊列末尾，重新把處理器分配給就緒隊列中新的隊首進程，同樣也讓它運行一個時間片。如果時間片太大，則時間片輪轉(zhuǎn)算法便退化為FCFS算法，如果太小，用戶輸入的常用命令都要花費幾個時間片才能處理完畢。時間片的大小選擇應(yīng)考慮：1、系統(tǒng)對響應(yīng)時間的要求（響應(yīng)時

9、間T直接與用戶（進程）數(shù)目n和時間片q的關(guān)系：T=nq）2、就緒隊列中進程的數(shù)目3、系統(tǒng)的處理能力。4、 FPF:通常允許剝奪調(diào)度。該算法的關(guān)鍵在如何確定進程的優(yōu)先權(quán)，常有2種方法：靜態(tài)優(yōu)先權(quán)：影響進程靜態(tài)優(yōu)先權(quán)的主要因素：進程類型（系統(tǒng)進程優(yōu)先權(quán)高于用戶進程）、進程對資源的要求（如估計的運行時間、內(nèi)存需要量等）、用戶要求的優(yōu)先級等。動態(tài)優(yōu)先權(quán)：基于某種原則，使進程的優(yōu)先權(quán)隨時間而改變。優(yōu)先數(shù)通常為04095間的整數(shù)，UNIX和許多其他系統(tǒng)中，優(yōu)先級數(shù)值越大，表示的進程優(yōu)先權(quán)越低；而在Windows中，大數(shù)值表示高優(yōu)先級。5、HRN：是FCFS和SJF的一種折衷。響應(yīng)比：Rp=R為響應(yīng)比，W為

10、等待時間，T為該作業(yè)估計要執(zhí)行的時間MQ：引入多個就緒隊列，通過對各隊列區(qū)別對待，達到一個綜合調(diào)度目標(biāo)。RRMF：是時間片輪轉(zhuǎn)換算法和優(yōu)先級調(diào)度算法的綜合和發(fā)展。 死鎖的定義、產(chǎn)生死鎖的原因、產(chǎn)生死鎖的必要條件II定義：兩個或兩個以上的進程無限期地等待永遠不可能發(fā)生的事件。產(chǎn)生原因：1、系統(tǒng)資源不足。2、進程推進順序不合理。系統(tǒng)中有m（m=1）個進程，各需要使用同類資源k個，則保證系統(tǒng)不發(fā)生思索的最少資源數(shù)位（k-1）m+1。必要條件：互斥條件、請求和保持條件、不剝奪條件、環(huán)路條件要防止死鎖的發(fā)生，其根本方法是破壞上述必要條件之一（或多個條件）。處理死鎖的策略：預(yù)防：如果能夠保證4個必要條件中

11、至少一個不成立，則死鎖將不會發(fā)生。避免策略、死鎖檢測、接觸策略。 虛擬地址、地址空間、存儲空間、地址重定位的基本概念I(lǐng)虛擬地址（邏輯地址或相對地址）：以0為基址連續(xù)順序進行編制的，稱為相對地址。地址空間（邏輯地址空間或相對地址空間）：相對地址（虛擬地址）的集合。存儲空間（物理地址空間或絕對地址空間）：相對地址空間通過地址重定位機構(gòu)轉(zhuǎn)換到絕對地址空間。 地址重定位：一個邏輯地址空間的程序裝入到物理地址空間時，由于兩個空間不一致，需要進行地址變換，或稱地址映射，即地址重定位。 分頁存儲管理II 頁：用戶程序的地址空間被劃分成若干固定大小的區(qū)域，稱為頁。物理塊：將存儲空間也劃分為與頁大小相等的區(qū)域，

12、稱為物理塊。內(nèi)碎片：進程的最后一頁經(jīng)常裝不滿一塊，形成不可利用的碎片，稱為內(nèi)碎片。將用戶程序的任一頁放入存儲空間的任一物理塊中，從而實現(xiàn)了離散存儲。計算邏輯地址：分頁系統(tǒng)中，每個邏輯地址用一個數(shù)對（p,d）來表示，其中P是頁號，d是頁內(nèi)地址。若給定一個邏輯地址A，頁面大小為L，則：P=INTA/L d=AMOD L其中，INT是向下取整的函數(shù)。 程序的局部性特點虛擬存儲器的實現(xiàn)方法I時間局限性：產(chǎn)生時間局限性的主要原因是程序中存在著大量的循環(huán)操作?？臻g局限性：產(chǎn)生空間局限性的原因是程序的順序執(zhí)行。局部性原理是實現(xiàn)虛擬存儲管理的理論基礎(chǔ)。實現(xiàn)方法：僅把進程的一部分裝入內(nèi)存，其余部分則存放在磁盤上

13、。如果需要的頁（段）已經(jīng)掉入內(nèi)存，便可以繼續(xù)執(zhí)行下去。如果不在內(nèi)存，則利用操作系統(tǒng)所提供的請求調(diào)頁（段）功能，將該頁（段）調(diào)入內(nèi)存，。如果此時分配給該程序的內(nèi)存已經(jīng)全部占用，不能裝入新的頁（段），則需要利用系統(tǒng)的置換功能，把內(nèi)存中暫時不用的頁（段）調(diào)出至磁盤上，留出足夠的內(nèi)存空間，再將要裝入的頁（段）調(diào)入內(nèi)存。這樣便能從邏輯上對內(nèi)存容量進行擴充了。虛擬存儲器的邏輯容量由系統(tǒng)的尋址能力和外存容量之和所決定 頁面置換算法最佳置換算法、先進先出置換算法、最近最久未使用置換算法、最近未用置換算法II 最佳置換算法（OPT）：置換掉那些以后永不再使用或在最長的時間以后才會用到的頁面。 這種算法實際上是不

14、能實現(xiàn)的，但可以把它作為衡量其它算法優(yōu)劣的一個標(biāo)準(zhǔn)。先進先出算法（FIFO）：置換掉那些最先進入內(nèi)存的頁面。一般，分配給進程的物理塊越多，缺頁次數(shù)越少。但分配給進程4個物理塊時的缺頁次數(shù)比3個是的多，這種反常現(xiàn)象稱為Belady異常。最近最久未使用置換算法（LRU）：其基本思想是，如果某一頁面被訪問，那么它很可能馬上又被訪問；反之，如果，很久未被訪問，那么最近也不會再次被訪問。該算法為每一個頁面設(shè)置一個訪問字段，用來記錄一個頁面自上次被訪問以來所經(jīng)歷的時間t，當(dāng)需要淘汰一個頁面時，選擇現(xiàn)有頁面中t值最大的。它普遍地使用于各種類型的程序。但系統(tǒng)要時時對各頁的訪問歷史情況加以記錄和更新，如果全由軟

15、件來做，則系統(tǒng)的“非生產(chǎn)性”開銷太大，從而會導(dǎo)致系統(tǒng)速度大大降低（至少會降低10倍）所以，LRU算法必須有硬件的支持。兩種實現(xiàn)方法：計時法、堆棧法。注這里的“?！辈皇峭ǔＲ饬x的堆棧，這里應(yīng)該使用雙向鏈來構(gòu)造棧，其鏈頭鏈尾各需要一個指針。LRU的實現(xiàn)代價太高，需要在內(nèi)存維持一個包含所有頁的鏈表，最近使用的頁面在表頭，最久未使用的在表尾。及時使用硬件實現(xiàn)也非常費時。最近未使用置換算法（NRU）：此算法被廣泛應(yīng)用，它近似LRU算法，為每個頁面設(shè)置一位訪問位，將內(nèi)存中的所有頁面通過鏈接指針鏈成一個循環(huán)隊列。當(dāng)某頁被訪問時，其訪問位置1.在選擇一頁淘汰時，檢查其訪問位，如果是0，則淘汰，若為1，則把它置

16、為0，暫不換出該頁，再按照FIFO算法檢查下一個頁面。當(dāng)檢查到最后一個頁面時，若其訪問位仍為1，則再返回隊首去檢查第一個頁面。為每頁增設(shè)兩個硬件位:訪問位和修改位。訪問位：A=0：該頁尚未被訪問過 A=1：該頁已經(jīng)被訪問過修改位：M=0：該頁尚未被修改過 M=1：該頁已經(jīng)被修改過4種組合：1類（A=0，M=0） ： 最佳淘汰頁2類（A=0，M=1）： 并不是很好的淘汰頁3類（A=1，M=0）：有可能再次被訪問4類（A=1，M=1）：可能再次被訪問 設(shè)備管理 設(shè)備分類方法I除CPU和內(nèi)存外，其它大部分硬件設(shè)備稱為外圍設(shè)備。大體可分為：人可讀的、機可讀的、通信。分類方法：1、 按傳輸速率分：低速設(shè)

17、備（如語音輸入、鍵盤、鼠標(biāo)器和輸出設(shè)備幾十至幾百字節(jié)每秒）、中速設(shè)備（如激光打印機、行式打印機幾千字節(jié)至十千個字節(jié)每秒）、高速設(shè)備（如磁帶機、磁盤機、光盤機數(shù)百千至數(shù)兆個字節(jié)每秒）2、 按信息交換的單位分類：塊設(shè)備（用于存儲信息，屬于有結(jié)構(gòu)設(shè)備I/O采用DMA方式。如磁盤，每個盤塊大小通常512B4KB）、字符設(shè)備（用于數(shù)據(jù)的輸入輸出，其基本單位是字符屬于無結(jié)構(gòu)設(shè)備，如交互式終端、打印機等）3、 從資源分配角度分類：獨占設(shè)備、共享設(shè)備、虛擬設(shè)備。 通道、DMA的概念及特點I 增設(shè)通道的主要目的是為了建立獨立的I/O操作，不僅使數(shù)據(jù)的傳送能獨立于CPU，而且希望有關(guān)I/O操作的組織、管理及結(jié)束也

18、盡量獨立，以保證CPU有更多的時間去進行數(shù)據(jù)處理通道特點：I/O通道時一種特殊的處理器，專門負責(zé)輸入/輸出。具有自己的指令系統(tǒng)，但該指令系統(tǒng)比較簡單。一方面，該指令系統(tǒng)一般只有數(shù)據(jù)傳送指令、設(shè)備控制指令等；另，通道沒有自己的內(nèi)存，其所執(zhí)行的程序（即通道程序）是放在主機內(nèi)存中的，與CPU共享內(nèi)存。DMA概念：直接存儲器訪問特點：1、 作為高速的外圍設(shè)備與內(nèi)存之間進行成批的數(shù)據(jù)交換，但不對數(shù)據(jù)做加工處理，數(shù)據(jù)傳輸?shù)幕締挝皇菙?shù)據(jù)塊，2、 需要使用一個專門的DMA控制器（DMAC）、內(nèi)存地址寄存器和數(shù)據(jù)緩沖寄存器。3、 采用盜竊總線控制權(quán)的方法，由DMAC送出內(nèi)存地址和發(fā)出內(nèi)存讀、設(shè)備寫或設(shè)備讀、內(nèi)

19、存寫的控制信號來完成內(nèi)存與設(shè)備之間的直接數(shù)據(jù)傳送，而不用CPU的干預(yù)，有的甚至不競購DMAC的數(shù)據(jù)緩沖寄存器的再吞吐，傳輸速率非常高。4、 僅在傳送一個或多個數(shù)據(jù)塊的開始和結(jié)束時，才需CPU干預(yù)，整塊數(shù)據(jù)的傳送石在控制器的控制下完成的 SpoolingSimultaneous Peripheral Operations On Line定義、組成和結(jié)構(gòu)I Spooling（假脫機技術(shù)）是多道程序設(shè)計系統(tǒng)中處理獨占I/O設(shè)備的一種技術(shù)。Spooling系統(tǒng)主要由3部分組成：1、輸入井和輸出井2、輸入緩沖區(qū)和輸出緩沖區(qū)3、輸入進程SPi和輸出進程SP0.它是對脫機輸入/輸出工作的模擬，必須有高速隨機

20、外存的支持，通常利用磁盤。 磁盤調(diào)度算法先來先服務(wù)First-Come First-ServedFCFS、 最短尋道時間優(yōu)先SSTFShortest Seek Time First、 掃描算法SCAN、單向掃描調(diào)度算法CSCAN磁盤調(diào)度算法的基本思想II FCFSSSTF比FCFS有更好的尋道性能，但可能導(dǎo)致某些進程發(fā)生“饑餓”現(xiàn)象。SCAN（電梯調(diào)度算法）：可防止“饑餓”現(xiàn)象的出現(xiàn)，它考慮到欲訪問磁道與當(dāng)前磁道間的距離，更優(yōu)先考慮的是刺頭當(dāng)前移動的方向。CSCAN：（循環(huán)掃描）最小磁道號緊接著最大磁道號構(gòu)成循環(huán)。 文件、文件系統(tǒng)、文件類型、文件組織結(jié)構(gòu)的基本概念I(lǐng)文件：指具有符號名的數(shù)據(jù)項的

21、集合。文件系統(tǒng)：負責(zé)管理和存取文件信息的軟件機構(gòu)文件類型：1、 按文件的性質(zhì)和用途分類：系統(tǒng)文件、庫文件、用戶文件（臨時文件、檔案文件、永久文件）。2、 按文件的保護方式分類：只讀文件、讀寫文件、不保護文件3、 按文件中的數(shù)據(jù)形式分類：源文件、目標(biāo)文件、可執(zhí)行文件4、 按文件的信息流向分類：輸入文件、輸出文件、輸入/輸出文件5、 UNIX操作系統(tǒng)文件的分類：普通文件、目錄文件、特別文件文件組織結(jié)構(gòu)：堆文件、順序文件、索引文件、索引順序文件、直接文件和哈希文件 文件的物理結(jié)構(gòu)連續(xù)結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)、多個物理塊的索引表結(jié)構(gòu)的基本概念I(lǐng)連續(xù)結(jié)構(gòu)：每個文件有一組相鄰接的盤塊鏈接結(jié)構(gòu)：通過每個物理

22、塊上的指針，將屬于一個文件的多個離散的盤塊鏈接成一個鏈表索引結(jié)構(gòu)：每一個文件建立一張索引表。適用于數(shù)據(jù)記錄保存在隨機存取存儲設(shè)備上的文件。 目錄一級目錄、二級目錄、多級目錄的基本概念I(lǐng)一級目錄：最簡單的目錄結(jié)構(gòu)，整個系統(tǒng)中只建立一張目錄表，為每個文件分配一個目錄項（包含文件名、文件的起始塊號、其他屬性，如文件長度、文件類型等，另外，再設(shè)置一個狀態(tài)位，表明是否空閑）二級目錄：為每個用戶建立一個單獨的用戶文件目錄UFD，這些文件目錄具有相似的結(jié)構(gòu)，由用戶所有文件控制塊組成。多級目錄：（樹形目錄結(jié)構(gòu)）：被廣泛采用，主目錄在樹形目錄結(jié)構(gòu)中，作為樹的根節(jié)點，稱為根目錄，數(shù)據(jù)文件作為輸液，其它所有文件均作為樹的節(jié)點。 文件的存取方法順序存取法、直接存取法、按鍵存取法的基本概念I(lǐng) 文件存儲空間的管理位示圖、空閑區(qū)表、空閑塊鏈、成組鏈接法基本思想I 位示圖：這種方法得到了多種操作系統(tǒng)的普遍采用，其基本思想是：用若干個字節(jié)組成一張圖，每個字節(jié)中的每一位對應(yīng)存儲空間中的一個物理塊。若某位為1表示對應(yīng)的物理塊已經(jīng)分配，若為0，則表示未分配，處于空閑態(tài)空閑區(qū)表：磁盤空間上一個連續(xù)的未分配區(qū)域稱為空閑區(qū)，僅當(dāng)有少量的