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

時間：2020-06-02 17:04:00 志藝942由分享

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

　　你還在為不知道操作系統(tǒng)總結(jié)知識而不知所措么?下面來是學(xué)習(xí)啦小編為大家收集的操作系統(tǒng)總結(jié)知識，歡迎大家閱讀：

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

　　第一章操作系統(tǒng)引論

　　系統(tǒng)的目標(biāo)：有效性(提高資源利用率和系統(tǒng)吞吐量)、方便性、可擴充性、開放性。

　　有效性和方便性是操作系統(tǒng)最重要兩個目標(biāo)。

　　操作系統(tǒng)的作用：

　　(1) OS作為用戶與計算機硬件系統(tǒng)之間的接口

　　(2) OS作為計算機系統(tǒng)資源的管理者(處理器、存儲器、I/O設(shè)備、數(shù)據(jù)程序)

　　(3) OS實現(xiàn)了對計算機資源的抽象(在硬件上覆蓋I/O設(shè)備、文件和窗口管理軟件，即虛擬機)

　　OS的發(fā)展過程：無操作系統(tǒng)的計算機系統(tǒng)→單道批處理系統(tǒng)→多道批處理系統(tǒng)→分時系統(tǒng)→實時系統(tǒng)→微機操作系統(tǒng)

　　操作系統(tǒng)的基本特征：

　　(1) 并發(fā)性(兩個或多個事件在同一時間間隔內(nèi)發(fā)生;進入進程和線程)

　　(2) 共享性(系統(tǒng)中資源可供內(nèi)存中多個并發(fā)執(zhí)行的進程(線程)共同使用，方式為互斥共享方式和同時訪問方式)

　　(3) 虛擬性(通過某種技術(shù)把一個物理實體變?yōu)槿舾蓚€邏輯上的對應(yīng)物。方式：時分復(fù)用技術(shù)和空分復(fù)用技術(shù))

　　(4) 異步性(進程以不可預(yù)知的速度向前推進，多道程序設(shè)計固有的特點)

　　OS的主要功能：

　　(1) 處理機管理(進程管理)功能;(主要包括創(chuàng)建和撤銷進程、協(xié)調(diào)諸進程的運行、實現(xiàn)進程間信息交換、把處理機分配給進程。進程同步機制功能是協(xié)調(diào)多個進程的運行，分為競爭和協(xié)作兩種方式，實現(xiàn)進程同步常用的及時是信號量機制。調(diào)度包括作業(yè)調(diào)度和進程調(diào)度兩步。)

　　(2) 存儲器管理功能;(內(nèi)存分配、內(nèi)存保護、地址映射和內(nèi)存擴充等功能。內(nèi)存分配有動態(tài)和靜態(tài)兩方式。內(nèi)容擴充的功能是請求調(diào)入和置換)

　　(3) 設(shè)備管理功能(緩沖管理、設(shè)備分配、設(shè)備處理和虛擬設(shè)備。緩沖管理包括單、雙、公用緩沖機制。設(shè)備處理的人物是實現(xiàn)CPU和設(shè)備控制器之間的通信)

　　(4) 文件管理功能;(文件存儲空間管理、目錄管理、文件讀寫管理、共享保護功能)

　　(5) 操作系統(tǒng)與用戶之間的接口;(用戶接口和程序接口)

　　第二章進程管理

　　進程與線程的基本概念

　　1) 進程是為了使多個程序能并發(fā)執(zhí)行，以提高資源利用率和系統(tǒng)吞吐量。

　　2) 線程是為了減少程序在并發(fā)執(zhí)行時所付出的空間開銷，是OS具有更好的并發(fā)性。

　　進程和線程的區(qū)別

　　1) 調(diào)度：線程作為調(diào)度和分派的基本單位;進程作為資源擁有的基本單位。

　　2) 并發(fā)性：進程之間可以并發(fā)執(zhí)行，進程中的諸線程之間也可并發(fā)執(zhí)行。

　　3) 擁有資源：進程擁有資源，線程無資源，但可以訪問所屬進程的資源

　　4) 系統(tǒng)開銷：創(chuàng)建可撤銷進程的代價比創(chuàng)建和撤銷線程的代價大的多。

　　前趨圖是描述進程之間執(zhí)行的前后關(guān)系的。

　　進程的特征：

　　1) 結(jié)構(gòu)特征;由程序段、相關(guān)的數(shù)據(jù)項和PCB三部分構(gòu)成了進程實體。

　　2) 動態(tài)性;指從創(chuàng)建、調(diào)度執(zhí)行到撤銷的過程是動態(tài)的。

　　3) 并發(fā)性;

　　4) 獨立性;因為有PCB，可以獨立運行、獨立分配資源、獨立接受調(diào)度等功能

　　5) 異步性;各進程按各自獨立、不可預(yù)知的速度向前推進。

　　進程的三種基本狀態(tài)：

　　1) 就緒狀態(tài);處CPU外，已占有其他必要的資源的進程

　　2) 執(zhí)行狀態(tài);

　　3) 阻塞狀態(tài);因事故是正在執(zhí)行的進程停止，并讓出CPU。

　　信號量機制是一種卓有成效的進程同步工具。包括整形信號量、記錄型信號量、AND型信號量、信號量集。

　　第三章處理機調(diào)度與死鎖

　　批量型作業(yè)通常需要經(jīng)歷作業(yè)調(diào)度(高級調(diào)度或長程調(diào)度)和進程調(diào)度(低級調(diào)度和短程調(diào)度)兩個過程后方能獲得處理機。

　　處理機調(diào)度層次

　　1) 高級調(diào)度：把外存上處于后備隊列中的那些作業(yè)調(diào)入內(nèi)存。

　　2) 低級調(diào)度：它決定就緒隊列中的哪個進程將獲得處理機，然后由分派程序執(zhí)行把處理機分配給該進程的操作。對象是進程。功能是：保存處理機現(xiàn)場信息(PCB);按某種算法選取進程;把處理器分配給進程。方式分為非搶占方式和搶占方式。

　　3) 中級調(diào)度：內(nèi)存中不能有太多的進程，把進程從內(nèi)存移到外存，當(dāng)內(nèi)存有足夠空間時，再將合適的進程換入內(nèi)存，等待進程調(diào)度。目的是提高內(nèi)存利用率和系統(tǒng)吞吐量。

　　死鎖：多個進程在運行過程中因爭奪資源而造成的一種僵局。

　　活鎖：多個進程在運行工程中因相互謙讓而造成的一種僵局。

　　產(chǎn)生死鎖的原因

　　1) 競爭資源

　　2) 進程間推進順序非法

　　產(chǎn)生死鎖的必要條件

　　1) 互斥條件：臨界資源的互斥訪問

　　2) 請求和保持條件：占著自己的資源不放，又去請求別人的

　　3) 不剝奪條件：進程沒有完成則不是放占有的資源

　　4) 環(huán)路等待條件：發(fā)生死鎖指必然存在一個資源環(huán)形鏈。

　　處理死鎖的基本方法

　　1) 預(yù)防死鎖

　　2) 避免死鎖

　　3) 檢測和解除死鎖

　　安全序列：是指系統(tǒng)能夠找到一個進程順序(P1、P2……Pn)，來為每個進程Pi分配所需資源，知道滿足每個進程的最大需求，是每個進程能夠順利完成，則P1、P2……Pn即為安全狀態(tài)。

　　用資源分配圖對死鎖進行檢測，消去途中的所有邊，若節(jié)點為孤立節(jié)點，則為可完全簡化。

　　死鎖的解除

　　1) 剝奪資源：從其他進程剝奪足夠數(shù)量的資源給死鎖進程，以解除死鎖狀態(tài)

　　2) 撤銷進程：一種方法是夭折全部進程;另一種方法是按某個順序逐個撤銷進程，知道死鎖狀態(tài)被解除。

　　第四章存儲器管理

　　連續(xù)分配方式：一個用戶程序分配一個連續(xù)的內(nèi)存空間

　　1) 單一連續(xù)分配：一個程序裝入其他程序就不允許被裝入。只是用于單用戶單任務(wù)的OS中。

　　2) 固定分區(qū)分配：把內(nèi)存分為若干個固定大小的區(qū)域，每個分區(qū)裝入一個作業(yè)，允許并發(fā)執(zhí)行。

　　3) 動態(tài)分區(qū)分配：根據(jù)實際需要，動態(tài)地為之分配內(nèi)存空間。

　　4) 動態(tài)重定位分區(qū)分配：通過重定位寄存器把相對地址轉(zhuǎn)化成物理地址，此轉(zhuǎn)化過程是在程序執(zhí)行期間，隨著每條指令或數(shù)據(jù)的訪問自動進行的，故稱為動態(tài)重定位。

　　分區(qū)分配算法

　　1) 首次適應(yīng)算法(以地址遞增次序訪問)

　　2) 循環(huán)首次適應(yīng)算法(從上一次分配處開始查找)

　　3) 最佳適應(yīng)算法(小內(nèi)存到大內(nèi)存依次查找)

　　4) 最壞適應(yīng)算法(每次分配從大內(nèi)存開始割讓)

　　5) 快速適應(yīng)算法(對空閑分區(qū)進行分類，并建立索引表，選最適合的控件分配給請求的進程)

　　對換：把暫時不運行的程序調(diào)到外存，需要時再調(diào)到內(nèi)存。

　　地址變換機制：將用戶地址空間中的邏輯地址變換為內(nèi)存空間中的物理地址。

　　引入分段存儲管理方式的目的，則主要是為了滿足用戶在編程和使用上多方面的要求。

　　段表是用于實現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射。

　　分頁和分段的主要區(qū)別

　　1) 兩者都采用離散分配方式，且都要通過地址應(yīng)設(shè)機構(gòu)來實現(xiàn)地址變換。

　　2) 頁是信息的物理單位，分頁是為了有效的管理內(nèi)存;段是邏輯單位，分段是為了維護信息完整性和獨立性。

　　3) 頁的大小固定且由系統(tǒng)決定，段的長度不固定，決定于用戶編寫的程序。

　　4) 分頁的作業(yè)地址空間是一維的，而分段的作業(yè)地址空間是二維的。

　　段頁式存儲管理方式的原理：分段和分頁相結(jié)合，先將用戶程序分成若干個段，再把每個段分成若干個頁，并為每個段賦予一個段名。其地質(zhì)結(jié)構(gòu)由段號、段內(nèi)頁號和頁內(nèi)地址組成。

　　頁面置換算法有：最佳置換算法、先進先出置換算法、最近最久未使用置換算法、Clock置換算法。

　　第五章設(shè)備管理

　　I/O系統(tǒng)是用于實現(xiàn)數(shù)據(jù)輸入、輸出及數(shù)據(jù)存儲的系統(tǒng)。

　　I/O設(shè)備類型：

　　1) 特性：存儲設(shè)備;輸入/輸出設(shè)備。

　　2) 傳輸速率：低速設(shè)備;中速設(shè)備;高速設(shè)備。

　　3) 信息交換的單位分類：塊設(shè)備;字符設(shè)備。

　　4) 共享屬性：獨占設(shè)備;共享設(shè)備;虛擬設(shè)備。

　　設(shè)備與控制器之間的接口：

　　1) 數(shù)據(jù)信號線：設(shè)備和設(shè)備控制器之間傳送數(shù)據(jù)信號

　　2) 控制信號線：設(shè)備控制器向I/O設(shè)備發(fā)送控制信號的通路

　　3) 狀態(tài)信號線：傳送指示設(shè)備當(dāng)前狀態(tài)的信號。

　　設(shè)備控制器

　　主要職責(zé)是控制一個或多個I/O設(shè)備，以實現(xiàn)I/O設(shè)備和計算機之間的數(shù)據(jù)交換。是CPU和I/O設(shè)備的接口，他接受CPU指令去控制I/O設(shè)備工作，使減輕處理機的工作量。

　　設(shè)備控制器包括控制字符設(shè)備控制器和控制塊設(shè)備的控制器。

　　設(shè)備控制器的基本功能

　　1) 接受和識別命令

　　2) 數(shù)據(jù)交換

　　3) 標(biāo)識和報告設(shè)備的狀態(tài)

　　4) 地址識別(CPU通過地質(zhì)控制設(shè)備)

　　5) 數(shù)據(jù)緩沖

　　6) 差錯控制

　　I/O通道是一種特殊的處理機，它具有執(zhí)行I/O指令的能力，可以控制I/O操作。類型分為：字節(jié)多路通道、數(shù)組選擇通道、數(shù)組多路通道。

　　解決“瓶頸”問題的最有效的方法是增加設(shè)備到主機間的通路而不增加通道。

　　I/O控制方式

　　1) 程序I/O方式

　　2) 中斷驅(qū)動I/O控制方式

　　3) 直接存儲器訪問(DMA)I/O控制方式

　　4) I/O通道控制方式

　　SPOOLing技術(shù)

　　通過SPOOLing技術(shù)便可將一臺物理I/O設(shè)備虛擬為多臺邏輯I/O設(shè)備，同樣允許多個用戶共享一臺物理I/O設(shè)備。

　　Spooling系統(tǒng)的組成

　　輸入井和輸入井;輸入緩沖區(qū)和輸出緩沖區(qū);輸入進程和輸出進程。

　　SPOOLing系統(tǒng)的特點

　　1) 提高了I/O的速度

　　2) 將獨占設(shè)備改造為共享設(shè)備

　　3) 實現(xiàn)了虛擬設(shè)備功能

　　磁盤調(diào)度

　　磁盤調(diào)度的主要目標(biāo)是使磁盤的平均尋道時間最少。

　　常用的磁盤調(diào)度算法

　　1) 先來先服務(wù)(適合進程較少的場合)

　　2) 最短尋道時間優(yōu)先(要訪問的磁道與當(dāng)前磁頭所在磁道距離最近。會導(dǎo)致進程“饑餓”現(xiàn)象)

　　3) 掃描算法(考慮訪問的磁道與當(dāng)前磁頭所在磁道距離最近和磁頭當(dāng)前移動的方向)

　　4) 循環(huán)掃描算法(規(guī)定磁頭單向移動)

　　5) NSPetpSCAN和FSCAN調(diào)度算法

　　第六章文件管理

　　文件邏輯結(jié)構(gòu)的類型

　　1) 有結(jié)構(gòu)文件(由一個以上的記錄構(gòu)成的文件，又稱記錄式文件)

　　2) 無結(jié)構(gòu)文件(由字符流構(gòu)成的文件，又稱流式文件)

　　記錄式文件的長度分為定長記錄和變長記錄。

　　記錄文件又分為順序文件、索引文件、索引順序文件。

　　大量的數(shù)據(jù)結(jié)構(gòu)而后數(shù)據(jù)庫是采用有結(jié)構(gòu)的文件形式

　　而大量的源代碼、可執(zhí)行文件、庫函數(shù)等采用無結(jié)構(gòu)文件。

　　順序文件的優(yōu)缺點

　　1) 適合進行批量存取

　　2) 存取效率是所有邏輯文件中最高的

　　3) 也只有順序文件才能存儲在磁帶上，并能有效的工作

　　4) 不適合查找或修改單個記錄

　　5) 增加或刪除一個記錄時比較困難

　　索引文件的缺點：除了有主文件外，還須配置一張索引表，而且每個記錄都要有一個索引表，因此提高了存儲費用。

　　對已直接文件，檢索時可以根據(jù)記錄鍵值直接獲得指定記錄的物理地址。

　　哈希文件是鍵值通過Hash函數(shù)指向目錄表，該表目的內(nèi)容指向記錄所在的物理塊。

　　外存分配方式：連續(xù)分配、連接分配和索引分配三種。

　　連續(xù)分配的優(yōu)缺點

　　1) 順序訪問容易

　　2) 順序訪問速度快

　　缺點：

　　1) 要求有連續(xù)的存儲空間

　　2) 必須實現(xiàn)知道文件的長度

　　鏈接分配中的鏈接方式分為隱式鏈接和顯式鏈接。

　　為新建文件分配存儲空間的方式分為連續(xù)和離散的分配方式。前置具有較高的文件訪問速度，但可能產(chǎn)生較多的外存零頭。后者能有效的利用外存空間，但訪問速度較慢。無論哪種方式，存儲空間的基本分配單位都是磁盤塊而非字節(jié)。

　　文件存儲空間管理的方法

　　1) 空閑表法和空閑鏈表法

　　2) 位示圖法

　　3) 成組鏈接法

　　空閑表法和空閑鏈表法都不適用于大型文件系統(tǒng)可使用成組鏈接法。

　　常見面試題：

　　1、進程是并發(fā)過程中程序的執(zhí)行過程

　　2、進程的特征：結(jié)構(gòu)特征動態(tài)性并發(fā)性獨立性異步性

　　3、臨界區(qū)指在每個進程中訪問臨界資源的那段代碼

　　4，現(xiàn)在操作系統(tǒng)中申請資源的基本單位是進程，在CPU得到執(zhí)行的基本單位是線程，進程是由程序段、數(shù)據(jù)段、PCB組成的

　　5，對臨界資源應(yīng)采取互斥訪問方式來實現(xiàn)共享

　　6，P.V操作是一種低級進程通信原語

　　7，對于記錄性信號量，在執(zhí)行一次P操作時，信號量的值應(yīng)當(dāng)減1，當(dāng)其值為小于0時進程應(yīng)阻塞;在執(zhí)行V操作時，信號量的值應(yīng)當(dāng)加1;當(dāng)其值小于等于0時，應(yīng)喚醒阻塞隊列中的進程。

　　8，N個進程共享某一臨界資源，(n-1)~1

　　9，短作業(yè)優(yōu)先算法，T1<T2<T3平均周轉(zhuǎn)時間為：T1+2XT2/3+T3/3

　　10，響應(yīng)比Rp=(等待時間+要求服務(wù)時間)/要求服務(wù)器時間=響應(yīng)時間/要求服務(wù)時間

　　11死鎖是指多個進程在運行過程中因爭奪資源，而造成的一種僵局，當(dāng)進程處于這種僵局狀態(tài)時，若無外力作用，他們都將無法再向前推進。

　　死鎖的避免是根據(jù)防止系統(tǒng)進入不安全狀態(tài)。

　　產(chǎn)生死鎖的根本原因是資源分配不當(dāng)和資源數(shù)量不足，發(fā)生死鎖的四個必要條件是：互斥條件，請求和保持條件，不剝奪條件和環(huán)路等待條件，銀行家算法用于避免死鎖

　　12，如果系統(tǒng)中有N個進程，最多為(N-1)個

　　13，若系統(tǒng)采用輪轉(zhuǎn)法調(diào)度進程系統(tǒng)采用的是剝奪式調(diào)度

　　14，既考慮作業(yè)等待時間，又考慮作業(yè)執(zhí)行時間，的調(diào)度算法是響應(yīng)比優(yōu)先調(diào)度算法

　　15，資源的有序分配策略可以破壞死鎖的“循環(huán)等待”

　　16，并非所有的不安全狀態(tài)都必然會轉(zhuǎn)為死鎖狀態(tài)，但當(dāng)系統(tǒng)進圖不安全按狀態(tài)后變有可能進入死鎖狀態(tài)，

　　17，重定位：在作業(yè)地址空間中使用的邏輯地址變?yōu)閮?nèi)存物理地址

　　18，支持程序放在不連續(xù)內(nèi)存中儲存管理方法有分取式分配，分段式分配，段頁式分配頁式存儲主要特點是不要將作業(yè)同時全部裝入到主存的的連續(xù)區(qū)域

　　19，適合多道程序運行的存儲管理中，存儲保護是為了防止各道作業(yè)的相互干擾

　　20，采用頁式存儲管理時，重定位的工作由地址轉(zhuǎn)換機

　　21，段頁式存儲管理中的地址映像表是每個作業(yè)或進程一張段表，每個段一張頁表

　　22，在虛擬頁式存儲管理方案中，完成將頁面調(diào)入內(nèi)存的工作的是缺頁中斷處理

　　23，分段管理和分頁管理的主要區(qū)別是分頁管理有存儲保護，分段管理沒有

　　24，在股低估分區(qū)分配中，可以不同但預(yù)先固定的

　　25，不使用中斷機構(gòu)的I/O控制方式是程序I/O方式

　　26，spooling技術(shù)能獨占設(shè)備改造成可以共享的虛擬設(shè)備

　　27，磁盤防偽中把數(shù)據(jù)從磁盤讀出，叫做傳輸時間

　　28，共享設(shè)備指同一時間內(nèi)運行多個進程同時訪問的設(shè)備

　　29，通過軟件的功能擴充，把原來獨占的設(shè)備愛造成若干個可共享的設(shè)備，虛擬設(shè)備

　　30，DMA方式如果I/O設(shè)備不通過CPU來完成

　　31，設(shè)備獨立性用戶程序獨立于具體物理設(shè)備的一種特性

　　32，虛擬設(shè)備一個物理設(shè)備變換成多個對應(yīng)的邏輯設(shè)備

　　33，通道是一種特殊的處理機，通道按傳遞數(shù)據(jù)的方式分為：字節(jié)多路通道，數(shù)組選擇通道，數(shù)組多路通道

　　通道涉及的數(shù)據(jù)結(jié)構(gòu)是設(shè)備控制器，控制器控制塊，通道控制塊，系統(tǒng)設(shè)備表

　　34，磁盤高速緩沖設(shè)在內(nèi)存中，目的是提高I/O磁盤速度

　　35，磁盤空間的地址有盤面號，柱面號，扇區(qū)號組成。訪問磁盤的時間有尋道時間，旋轉(zhuǎn)等待時間，讀寫時間

　　36，將系統(tǒng)段用參數(shù)翻譯成設(shè)備操作命令的工作由設(shè)備無關(guān)的操作系統(tǒng)完成

　　37，向設(shè)備寄存器寫入控制命令由設(shè)備驅(qū)動程序完成

　　38，尋找設(shè)備驅(qū)動程序由設(shè)備無關(guān)的操作系統(tǒng)軟件完成

　　39，設(shè)備管理的功能是設(shè)備分配，緩沖區(qū)管理和實現(xiàn)物理I/O設(shè)備的操作

　　40，根據(jù)設(shè)備的固有屬性特點，設(shè)備可分為獨占設(shè)備，共享設(shè)備和虛擬設(shè)備

　　41，引入緩沖區(qū)技術(shù)可提高處理器執(zhí)行程序和設(shè)備的輸入輸出操作的并行程序文件管理

　　42，物理文件的組織方式是由操作系統(tǒng)確定的，文件的順序存取是按文件的邏輯號逐一存取

　　43，系統(tǒng)通過樹形目錄結(jié)構(gòu)來解決重名問題

　　44，在UNIX操作系統(tǒng)中，把輸入輸出設(shè)備看做特殊文件

　　45，打開文件操作的主要工作是把指定的目錄復(fù)制到內(nèi)存指定區(qū)域

　　46，文件路徑名是指從根目錄到該文件所經(jīng)歷的路徑中各符號名的集合

　　47，按邏輯結(jié)構(gòu)劃分，文件主要有兩類：記錄是文件，流式文件，文件系統(tǒng)的主要目的是實現(xiàn)對文件的按名存取

　　48連續(xù)結(jié)構(gòu)文件必須采用連續(xù)分配方式，而鏈接結(jié)構(gòu)文件和索引結(jié)構(gòu)文件都可采取離散分配方式

　　49，文件系統(tǒng)中，若文件的物理結(jié)構(gòu)采用連續(xù)結(jié)構(gòu)有關(guān)文件的物理位置的信息包括首塊地址和文件長度

　　50，位示圖可用于磁盤空間管理，在文件系統(tǒng)中，為實現(xiàn)文件保護，一般采用口令，密碼和訪問控制

　　1、進程是具有獨立功能程序在某個數(shù)據(jù)集合上的一次執(zhí)行過程。線程是進程內(nèi)的一個執(zhí)行實體或執(zhí)行單元。

　　進程和線程的區(qū)別：

　　(a)不同進程的地址空間是獨立的，而同一進程內(nèi)的線程共享同一地址空間。一個進程的線程在另一個進程內(nèi)是不可見的。

　　(b) 在引入線程的操作系統(tǒng)中，進程是資源分配和調(diào)度的單位，線程是處理機調(diào)度和分配的單位，資源是分配給進程的，線程只擁有很少資源，因而切換代價比進程切換低。

　　2、死鎖在多道程序系統(tǒng)中，當(dāng)一組進程中的每個進程均無限期地等待被改組進程中的另一進程所占有且永遠不會釋放的資源，此時的系統(tǒng)處于死鎖狀態(tài)。

　　死鎖產(chǎn)生的原因：

　　(a)系統(tǒng)提供的資源有限;

　　(b)進程推進順序不當(dāng)。

　　產(chǎn)生死鎖的必要條件：互斥條件、不可剝奪條件、請求和保持條件、循環(huán)等待條件

　　3、執(zhí)行如下訪問頁號序列： 1，2，3，4，1，2，5，1，2，3，4，5 試說明采用先進(1)FIFO: 9次(2)LRU：10次 (3)OPT：7次

　　4、什么是操作系統(tǒng)的基本功能?

　　1.處理機管理。在多道程序或多用戶的情況下，要組織多個作業(yè)同時運行，就要解決對處理機分配調(diào)度策略、分配實施和資源回收等問題。

　　2.存儲管理。存儲管理的主要工作是對內(nèi)部存儲器進行分配、保護和擴充和管理。

　　3.設(shè)備管理。涉及到通道、控制器、輸入輸出設(shè)備的分配和管理以及設(shè)備獨立性。

　　4.信息管理(文件系統(tǒng)管理) 是對系統(tǒng)的軟件資源的管理。

　　5.用戶接口。操作系統(tǒng)還為用戶提供一個友好的用戶接口。一般來說，操作系統(tǒng)提供兩種方式的接口來為用戶服務(wù)。

　　5、分級調(diào)度分為4級：

　　(1) 作業(yè)調(diào)度

　　(2) 交換調(diào)度

　　(3) 進程調(diào)度

　　(4) 線程調(diào)度。

　　6、試寫出程序與進程的區(qū)別

　　(1)進程是一個動態(tài)概念，而程序是一個靜態(tài)概念。

　　(2)進程具有并行特征，而程序不反映執(zhí)行所以沒有并行特征

　　(3)進程是競爭計算機系統(tǒng)資源的基本單位，而程序不反映執(zhí)行也就不會競爭計算機系統(tǒng)資源

　　(4)不同的進程可以包含同一程序，只要該程序所對應(yīng)的數(shù)據(jù)集不同。

　　7、頁式管理的基本原理是什么?

　　(1)進程的虛擬空間被劃分成長度相等的頁。

　　(2)內(nèi)存空間也按頁的大小劃分成長度相等的頁面。

　　(3)采用請求調(diào)頁或預(yù)調(diào)技術(shù)實現(xiàn)內(nèi)外存儲器的統(tǒng)一管理。

　　8、進程調(diào)度有哪些功能?

　　(1)記錄系統(tǒng)中所有進程的執(zhí)行情況。

　　(2)選擇占有處理機的進程

　　(3)進行進程上下文切換

　　9、批處理操作系統(tǒng)、分時操作系統(tǒng)和實時操作系統(tǒng)的特點各是什么?

　　(1) 批處理操作系統(tǒng)的特點：成批處理，系統(tǒng)吞吐量高，資源利用率高，用戶不能直接干預(yù)作業(yè)的執(zhí)行。

　　(2)分時操作系統(tǒng)的特點：多路性、獨立性、及時性、交互性。

　　(3)實時操作系統(tǒng)的特點：及時響應(yīng)、快速處理;高可靠性和安全性;不要求系統(tǒng)資源利用率。

　　10、Windows下的內(nèi)存是如何管理的?

　　Windows提供了3種方法來進行內(nèi)存管理：虛擬內(nèi)存，最適合用來管理大型對象或者結(jié)構(gòu)數(shù)組;內(nèi)存映射文件，最適合用來管理大型數(shù)據(jù)流(通常來自文件)以及在單個計算機上運行多個進程之間共享數(shù)據(jù);內(nèi)存堆棧，最適合用來管理大量的小對象。

　　Windows操縱內(nèi)存可以分兩個層面：物理內(nèi)存和虛擬內(nèi)存。

　　其中物理內(nèi)存由系統(tǒng)管理，不允許應(yīng)用程序直接訪問，應(yīng)用程序可見的只有一個2G地址空間，而內(nèi)存分配是通過堆進行的。對于每個進程都有自己的默認堆，當(dāng)一個堆創(chuàng)建后，就通過虛擬內(nèi)存操作保留了相應(yīng)大小的地址塊(不占有實際的內(nèi)存，系統(tǒng)消耗很小)。當(dāng)在堆上分配一塊內(nèi)存時，系統(tǒng)在堆的地址表里找到一個空閑塊(如果找不到，且堆創(chuàng)建屬性是可擴充的，則擴充堆大小)，為這個空閑塊所包含的所有內(nèi)存頁提交物理對象(在物理內(nèi)存上或硬盤的交換文件上)，這時就可以訪問這部分地址。提交時，系統(tǒng)將對所有進程的內(nèi)存統(tǒng)一調(diào)配，如果物理內(nèi)存不夠，系統(tǒng)試圖把一部分進程暫時不訪問的頁放入交換文件，以騰出部分物理內(nèi)存。釋放內(nèi)存時，只在堆中將所在的頁解除提交(相應(yīng)的物理對象被解除)，繼續(xù)保留地址空間。

　　如果要知道某個地址是否被占用/可不可以訪問，只要查詢此地址的虛擬內(nèi)存狀態(tài)即可。如果是提交，則可以訪問。如果僅僅保留，或沒保留，則產(chǎn)生一個軟件異常。此外，有些內(nèi)存頁可以設(shè)置各種屬性。如果是只讀，向內(nèi)存寫也會產(chǎn)生軟件異常。

　　11、Windows消息調(diào)度機制是(C)

　　A)指令隊列;B)指令堆棧;C)消息隊列;D)消息堆棧

　　解析：

　　處理消息隊列的順序。首先Windows絕對不是按隊列先進先出的次序來處理的，而是有一定優(yōu)先級的。優(yōu)先級通過消息隊列的狀態(tài)標(biāo)志來實現(xiàn)的。首先，最高優(yōu)先級的是別的線程發(fā)過來的消息(通過sendmessage);其次，處理登記消息隊列消息;再次處理QS_QUIT標(biāo)志，處理虛擬輸入隊列，處理wm_paint;最后是wm_timer。

　　12、描述實時系統(tǒng)的基本特性

　　在特定時間內(nèi)完成特定的任務(wù)，實時性與可靠性。

　　所謂“實時操作系統(tǒng)”，實際上是指操作系統(tǒng)工作時，其各種資源可以根據(jù)需要隨時進行動態(tài)分配。由于各種資源可以進行動態(tài)分配，因此，其處理事務(wù)的能力較強、速度較快。

　　13、中斷和輪詢的特點

　　對I/O設(shè)備的程序輪詢的方式，是早期的計算機系統(tǒng)對I/O設(shè)備的一種管理方式。它定時對各種設(shè)備輪流詢問一遍有無處理要求。輪流詢問之后，有要求的，則加以處理。在處理I/O設(shè)備的要求之后，處理機返回繼續(xù)工作。盡管輪詢需要時間，但輪詢要比I/O設(shè)備的速度要快得多，所以一般不會發(fā)生不能及時處理的問題。當(dāng)然，再快的處理機，能處理的輸入輸出設(shè)備的數(shù)量也是有一定限度的。而且，程序輪詢畢竟占據(jù)了CPU相當(dāng)一部分處理時間，因此，程序輪詢是一種效率較低的方式，在現(xiàn)代計算機系統(tǒng)中已很少應(yīng)用。

　　程序中斷通常簡稱中斷，是指CPU在正常運行程序的過程中，由于預(yù)先安排或發(fā)生了各種隨機的內(nèi)部或外部事件，使CPU中斷正在運行的程序，而轉(zhuǎn)到為響應(yīng)的服務(wù)程序去處理。

　　輪詢——效率低，等待時間很長，CPU利用率不高。

　　中斷——容易遺漏一些問題，CPU利用率高。

　　14、什么是臨界區(qū)?如何解決沖突?

　　每個進程中訪問臨界資源的那段程序稱為臨界區(qū)，每次只準(zhǔn)許一個進程進入臨界區(qū)，進入后不允許其他進程進入。

　　(1)如果有若干進程要求進入空閑的臨界區(qū)，一次僅允許一個進程進入;

　　(2)任何時候，處于臨界區(qū)內(nèi)的進程不可多于一個。如已有進程進入自己的臨界區(qū)，則其它所有試圖進入臨界區(qū)的進程必須等待;

　　(3)進入臨界區(qū)的進程要在有限時間內(nèi)退出，以便其它進程能及時進入自己的臨界區(qū);

　　(4)如果進程不能進入自己的臨界區(qū)，則應(yīng)讓出CPU，避免進程出現(xiàn)“忙等”現(xiàn)象。

　　15、說說分段和分頁

　　頁是信息的物理單位，分頁是為實現(xiàn)離散分配方式，以消減內(nèi)存的外零頭，提高內(nèi)存的利用率;或者說，分頁僅僅是由于系統(tǒng)管理的需要，而不是用戶的需要。

　　段是信息的邏輯單位，它含有一組其意義相對完整的信息。分段的目的是為了能更好的滿足用戶的需要。

　　頁的大小固定且由系統(tǒng)確定，把邏輯地址劃分為頁號和頁內(nèi)地址兩部分，是由機器硬件實現(xiàn)的，因而一個系統(tǒng)只能有一種大小的頁面。段的長度卻不固定，決定于用戶所編寫的程序，通常由編輯程序在對源程序進行編輯時，根據(jù)信息的性質(zhì)來劃分。

　　分頁的作業(yè)地址空間是一維的，即單一的線性空間，程序員只須利用一個記憶符，即可表示一地址。分段的作業(yè)地址空間是二維的，程序員在標(biāo)識一個地址時，既需給出段名，又需給出段內(nèi)地址。

　　16、說出你所知道的保持進程同步的方法?

　　進程間同步的主要方法有原子操作、信號量機制、自旋鎖、管程、會合、分布式系統(tǒng)等。

　　17、Linux中常用到的命令

　　顯示文件目錄命令ls 如ls

　　改變當(dāng)前目錄命令cd 如cd /home

　　建立子目錄mkdir 如mkdir xiong

　　刪除子目錄命令rmdir 如rmdir /mnt/cdrom

　　刪除文件命令rm 如rm /ucdos.bat

　　文件復(fù)制命令cp 如cp /ucdos /fox

　　獲取幫助信息命令man 如man ls

　　顯示文件的內(nèi)容less 如less mwm.lx

　　重定向與管道type 如type readme>>direct，將文件readme的內(nèi)容追加到文direct中

　　18、Linux文件屬性有哪些?(共十位)

　　-rw-r--r--那個是權(quán)限符號，總共是- --- --- ---這幾個位。

　　第一個短橫處是文件類型識別符：-表示普通文件;c表示字符設(shè)備(character);b表示塊設(shè)備(block);d表示目錄(directory);l表示鏈接文件(link);后面第一個三個連續(xù)的短橫是用戶權(quán)限位(User)，第二個三個連續(xù)短橫是組權(quán)限位(Group)，第三個三個連續(xù)短橫是其他權(quán)限位(Other)。每個權(quán)限位有三個權(quán)限，r(讀權(quán)限)，w(寫權(quán)限)，x(執(zhí)行權(quán)限)。如果每個權(quán)限位都有權(quán)限存在，那么滿權(quán)限的情況就是：-rwxrwxrwx;權(quán)限為空的情況就是- --- --- ---。

　　權(quán)限的設(shè)定可以用chmod命令，其格式位：chmod ugoa+/-/=rwx filename/directory。例如：

　　一個文件aaa具有完全空的權(quán)限- --- --- ---。

　　chmod u+rw aaa(給用戶權(quán)限位設(shè)置讀寫權(quán)限，其權(quán)限表示為：- rw- --- ---)

　　chmod g+r aaa(給組設(shè)置權(quán)限為可讀，其權(quán)限表示為：- --- r-- ---)

　　chmod ugo+rw aaa(給用戶，組，其它用戶或組設(shè)置權(quán)限為讀寫，權(quán)限表示為：- rw- rw- rw-)

　　如果aaa具有滿權(quán)限- rwx rwx rwx。

　　chmod u-x aaa(去掉用戶可執(zhí)行權(quán)限，權(quán)限表示為：- rw- rwx rwx)

　　如果要給aaa賦予制定權(quán)限- rwx r-x r-x，命令為：

　　chmod u=rwx，Go=rx aaa

　　19、簡術(shù)OSI的物理層Layer1，鏈路層Layer2，網(wǎng)絡(luò)層Layer3的任務(wù)。

　　網(wǎng)絡(luò)層：通過路由選擇算法，為報文或分組通過通信子網(wǎng)選擇最適當(dāng)?shù)穆窂健?/p>

　　鏈路層：通過各種控制協(xié)議，將有差錯的物理信道變?yōu)闊o差錯的、能可靠傳輸數(shù)據(jù)幀的數(shù)據(jù)鏈路。

　　物理層：利用傳輸介質(zhì)為數(shù)據(jù)鏈路層提供物理連接，實現(xiàn)比特流的透明傳輸。

　　20、什么是中斷?中斷時CPU做什么工作?

　　中斷是指在計算機執(zhí)行期間，系統(tǒng)內(nèi)發(fā)生任何非尋常的或非預(yù)期的急需處理事件，使得CPU暫時中斷當(dāng)前正在執(zhí)行的程序而轉(zhuǎn)去執(zhí)行相應(yīng)的事件處理程序。待處理完畢后又返回原來被中斷處繼續(xù)執(zhí)行或調(diào)度新的進程執(zhí)行的過程。

　　21、你知道操作系統(tǒng)的內(nèi)容分為幾塊嗎?什么叫做虛擬內(nèi)存?他和主存的關(guān)系如何?內(nèi)存管理屬于操作系統(tǒng)的內(nèi)容嗎?

　　操作系統(tǒng)的主要組成部分：進程和線程的管理，存儲管理，設(shè)備管理，文件管理。虛擬內(nèi)存是一些系統(tǒng)頁文件，存放在磁盤上，每個系統(tǒng)頁文件大小為4K，物理內(nèi)存也被分頁，每個頁大小也為4K，這樣虛擬頁文件和物理內(nèi)存頁就可以對應(yīng)，實際上虛擬內(nèi)存就是用于物理內(nèi)存的臨時存放的磁盤空間。頁文件就是內(nèi)存頁，物理內(nèi)存中每頁叫物理頁，磁盤上的頁文件叫虛擬頁，物理頁+虛擬頁就是系統(tǒng)所有使用的頁文件的總和。

　　22、線程是否具有相同的堆棧?dll是否有獨立的堆棧?

　　每個線程有自己的堆棧。

　　dll是否有獨立的堆棧?這個問題不好回答，或者說這個問題本身是否有問題。因為dll中的代碼是被某些線程所執(zhí)行，只有線程擁有堆棧。如果dll中的代碼是exe中的線程所調(diào)用，那么這個時候是不是說這個dll沒有獨立的堆棧?如果dll中的代碼是由dll自己創(chuàng)建的線程所執(zhí)行，那么是不是說dll有獨立的堆棧?

　　以上講的是堆棧，如果對于堆來說，每個dll有自己的堆，所以如果是從dll中動態(tài)分配的內(nèi)存，最好是從dll中刪除;如果你從dll中分配內(nèi)存，然后在exe中，或者另外一個dll中刪除，很有可能導(dǎo)致程序崩潰。

　　23、什么是緩沖區(qū)溢出?有什么危害?其原因是什么?

　　緩沖區(qū)溢出是指當(dāng)計算機向緩沖區(qū)內(nèi)填充數(shù)據(jù)時超過了緩沖區(qū)本身的容量，溢出的數(shù)據(jù)覆蓋在合法數(shù)據(jù)上。

　　危害：在當(dāng)前網(wǎng)絡(luò)與分布式系統(tǒng)安全中，被廣泛利用的50%以上都是緩沖區(qū)溢出，其中最著名的例子是1988年利用fingerd漏洞的蠕蟲。而緩沖區(qū)溢出中，最為危險的是堆棧溢出，因為入侵者可以利用堆棧溢出，在函數(shù)返回時改變返回程序的地址，讓其跳轉(zhuǎn)到任意地址，帶來的危害一種是程序崩潰導(dǎo)致拒絕服務(wù)，另外一種就是跳轉(zhuǎn)并且執(zhí)行一段惡意代碼，比如得到shell，然后為所欲為。通過往程序的緩沖區(qū)寫超出其長度的內(nèi)容，造成緩沖區(qū)的溢出，從而破壞程序的堆棧，使程序轉(zhuǎn)而執(zhí)行其它指令，以達到攻擊的目的。

　　造成緩沖區(qū)溢出的主原因是程序中沒有仔細檢查用戶輸入的參數(shù)。

　　24、什么是死鎖?其條件是什么?怎樣避免死鎖?

　　死鎖的概念：在兩個或多個并發(fā)進程中，如果每個進程持有某種資源而又都等待別的進程釋放它或它們現(xiàn)在保持著的資源，在未改變這種狀態(tài)之前都不能向前推進，稱這一組進程產(chǎn)生了死鎖。通俗地講，就是兩個或多個進程被無限期地阻塞、相互等待的一種狀態(tài)。

　　死鎖產(chǎn)生的原因主要是：

　　(1)系統(tǒng)資源不足;

　　(2) 進程推進順序非法。

　　產(chǎn)生死鎖的必要條件：

　　(1)互斥(mutualexclusion)，一個資源每次只能被一個進程使用;

　　(2)不可搶占(nopreemption)，進程已獲得的資源，在未使用完之前，不能強行剝奪;

　　(3)占有并等待(hold andwait)，一個進程因請求資源而阻塞時，對已獲得的資源保持不放;

　　(4)環(huán)形等待(circularwait)，若干進程之間形成一種首尾相接的循環(huán)等待資源關(guān)系。

　　這四個條件是死鎖的必要條件，只要系統(tǒng)發(fā)生死鎖，這些條件必然成立，而只要上述條件之一不滿足，就不會發(fā)生死鎖。

　　死鎖的解除與預(yù)防：理解了死鎖的原因，尤其是產(chǎn)生死鎖的四個必要條件，就可以最大可能地避免、預(yù)防和解除死鎖。所以，在系統(tǒng)設(shè)計、進程調(diào)度等方面注意如何不讓這四個必要條件成立，如何確定資源的合理分配算法，避免進程永久占據(jù)系統(tǒng)資源。此外，也要防止進程在處于等待狀態(tài)的情況下占用資源。因此，對資源的分配要給予合理的規(guī)劃。

　　死鎖的處理策略：鴕鳥策略、預(yù)防策略、避免策略、檢測與恢復(fù)策略。

　　附錄：

　　1、什么是進程(Process)和線程(Thread)?有何區(qū)別?

　　進程是具有一定獨立功能的程序關(guān)于某個數(shù)據(jù)集合上的一次運行活動，進程是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。線程是進程的一個實體，是CPU調(diào)度和分派的基本單位，它是比進程更小的能獨立運行的基本單位。線程自己基本上不擁有系統(tǒng)資源，只擁有一點在運行中必不可少的資源(如程序計數(shù)器，一組寄存器和棧)，但是它可與同屬一個進程的其他的線程共享進程所擁有的全部資源。一個線程可以創(chuàng)建和撤銷另一個線程，同一個進程中的多個線程之間可以并發(fā)執(zhí)行。

　　進程與應(yīng)用程序的區(qū)別在于應(yīng)用程序作為一個靜態(tài)文件存儲在計算機系統(tǒng)的硬盤等存儲空間中，而進程則是處于動態(tài)條件下由操作系統(tǒng)維護的系統(tǒng)資源管理實體。

　　2、Windows下的內(nèi)存是如何管理的?

　　Windows操縱內(nèi)存可以分兩個層面：物理內(nèi)存和虛擬內(nèi)存。

　　3、Windows消息調(diào)度機制是?

　　A)指令隊列;B)指令堆棧;C)消息隊列;D)消息堆棧

　　答案：C

　　4、描述實時系統(tǒng)的基本特性

　　在特定時間內(nèi)完成特定的任務(wù)，實時性與可靠性。

　　5、中斷和輪詢的特點

　　輪詢——效率低，等待時間很長，CPU利用率不高。

　　中斷——容易遺漏一些問題，CPU利用率高。

　　6、什么是臨界區(qū)?如何解決沖突?

　　每個進程中訪問臨界資源的那段程序稱為臨界區(qū)，每次只準(zhǔn)許一個進程進入臨界區(qū)，進入后不允許其他進程進入。

　　(1)如果有若干進程要求進入空閑的臨界區(qū)，一次僅允許一個進程進入;

　　(2)任何時候，處于臨界區(qū)內(nèi)的進程不可多于一個。如已有進程進入自己的臨界區(qū)，則其它所有試圖進入臨界區(qū)的進程必須等待;

　　(3)進入臨界區(qū)的進程要在有限時間內(nèi)退出，以便其它進程能及時進入自己的臨界區(qū);

　　(4)如果進程不能進入自己的臨界區(qū)，則應(yīng)讓出CPU，避免進程出現(xiàn)“忙等”現(xiàn)象。

　　7、說說分段和分頁

　　段是信息的邏輯單位，它含有一組其意義相對完整的信息。分段的目的是為了能更好的滿足用戶的需要。

　　8、說出你所知道的保持進程同步的方法?

　　進程間同步的主要方法有原子操作、信號量機制、自旋鎖、管程、會合、分布式系統(tǒng)等。

　　9、Linux中常用到的命令

　　顯示文件目錄命令ls 如ls

　　改變當(dāng)前目錄命令cd 如cd /home

　　建立子目錄mkdir 如mkdir xiong

　　刪除子目錄命令rmdir 如rmdir /mnt/cdrom

　　刪除文件命令rm 如rm /ucdos.bat

　　文件復(fù)制命令cp 如cp /ucdos /fox

　　獲取幫助信息命令man 如man ls

　　顯示文件的內(nèi)容less 如less mwm.lx

　　重定向與管道type 如type readme>>direct，將文件readme的內(nèi)容追加到文direct中

　　10、Linux文件屬性有哪些?(共十位)

　　-rw-r--r--那個是權(quán)限符號，總共是- --- --- ---這幾個位。

　　權(quán)限的設(shè)定可以用chmod命令，其格式位：chmod ugoa+/-/=rwx filename/directory。例如：

　　一個文件aaa具有完全空的權(quán)限- --- --- ---。

　　chmod u+rw aaa(給用戶權(quán)限位設(shè)置讀寫權(quán)限，其權(quán)限表示為：- rw- --- ---)

　　chmod g+r aaa(給組設(shè)置權(quán)限為可讀，其權(quán)限表示為：- --- r-- ---)

　　chmod ugo+rw aaa(給用戶，組，其它用戶或組設(shè)置權(quán)限為讀寫，權(quán)限表示為：- rw- rw- rw-)

　　如果aaa具有滿權(quán)限- rwx rwx rwx。

　　chmod u-x aaa(去掉用戶可執(zhí)行權(quán)限，權(quán)限表示為：- rw- rwx rwx)

　　如果要給aaa賦予制定權(quán)限- rwx r-x r-x，命令為：

　　chmod u=rwx，go=rx aaa

　　11、makefile文件的作用是什么?

　　一個工程中的源文件不計其數(shù)，其按類型、功能、模塊分別放在若干個目錄中。makefile定義了一系列的規(guī)則來指定哪些文件需要先編譯，哪些文件需要后編譯，哪些文件需要重新編譯，甚至于進行更復(fù)雜的功能操作。因為makefile就像一個Shell腳本一樣，其中也可以執(zhí)行操作系統(tǒng)的命令。makefile帶來的好處就是——“自動化編譯”。一旦寫好，只需要一個make命令，整個工程完全自動編譯，極大地提高了軟件開發(fā)的效率。make是一個命令工具，是一個解釋makefile中指令的命令工具。一般來說，大多數(shù)的IDE都有這個命令，比如：Delphi的make，Visual C++的nmake，Linux下GNU的make?？梢姡琺akefile都成為了一種在工程方面的編譯方法。

　　12、簡術(shù)OSI的物理層Layer1，鏈路層Layer2，網(wǎng)絡(luò)層Layer3的任務(wù)。

　　網(wǎng)絡(luò)層：通過路由選擇算法，為報文或分組通過通信子網(wǎng)選擇最適當(dāng)?shù)穆窂健?/p>

　　鏈路層：通過各種控制協(xié)議，將有差錯的物理信道變?yōu)闊o差錯的、能可靠傳輸數(shù)據(jù)幀的數(shù)據(jù)鏈路。

　　物理層：利用傳輸介質(zhì)為數(shù)據(jù)鏈路層提供物理連接，實現(xiàn)比特流的透明傳輸。

　　13、什么是中斷?中斷時CPU做什么工作?

　　14、你知道操作系統(tǒng)的內(nèi)容分為幾塊嗎?什么叫做虛擬內(nèi)存?他和主存的關(guān)系如何?內(nèi)存管理屬于操作系統(tǒng)的內(nèi)容嗎?

　　15、線程是否具有相同的堆棧?dll是否有獨立的堆棧?

　　每個線程有自己的堆棧。

　　16、什么是緩沖區(qū)溢出?有什么危害?其原因是什么?

　　造成緩沖區(qū)溢出的主原因是程序中沒有仔細檢查用戶輸入的參數(shù)。

　　17、什么是死鎖?其條件是什么?怎樣避免死鎖?

　　死鎖產(chǎn)生的原因主要是：? 系統(tǒng)資源不足;? 進程推進順序非法。

　　產(chǎn)生死鎖的必要條件：

　　(1)互斥(mutualexclusion)，一個資源每次只能被一個進程使用;

　　(2)不可搶占(nopreemption)，進程已獲得的資源，在未使用完之前，不能強行剝奪;

　　(3)占有并等待(hold andwait)，一個進程因請求資源而阻塞時，對已獲得的資源保持不放;

　　(4)環(huán)形等待(circularwait)，若干進程之間形成一種首尾相接的循環(huán)等待資源關(guān)系。

　　這四個條件是死鎖的必要條件，只要系統(tǒng)發(fā)生死鎖，這些條件必然成立，而只要上述條件之一不滿足，就不會發(fā)生死鎖。

　　死鎖的處理策略：鴕鳥策略、預(yù)防策略、避免策略、檢測與恢復(fù)策略。

　　1、程序和進程

　　進程由兩個部分組成：1)操作系統(tǒng)用來管理進程的內(nèi)核對象。內(nèi)核對象也是系統(tǒng)用來存放關(guān)于進程的統(tǒng)計信息的地方。2)地址空間。它包含所有可執(zhí)行模塊或DLL模塊的代碼和數(shù)據(jù)。它還包含動態(tài)內(nèi)存分配的空間。如線程堆棧和堆分配空間。

定義

使用系統(tǒng)運行資源情況

程序

計算機指令的集合，它以文件的形式存儲在磁盤上。程序是靜態(tài)實體（passive Entity），在多道程序系統(tǒng)中，它是不能獨立運行的，更不能與其他程序并發(fā)執(zhí)行。

不使用【程序不能申請系統(tǒng)資源，不能被系統(tǒng)調(diào)度，也不能作為獨立運行的單位，因此，它不占用系統(tǒng)的運行資源】。

進程

通常被定義為一個正在運行的程序的實例，是一個程序在其自身的地址空間中的一次執(zhí)行活動。

定義：進程是進程實體（包括：程序段、相關(guān)的數(shù)據(jù)段、進程控制塊PCB）的運行過程，是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。

使用【進程是資源申請、調(diào)度和獨立運行的單位，因此，它使用系統(tǒng)中的運行資源?！?/p>

　　2、進程與線程

　　如果說操作系統(tǒng)引入進程的目的是為了提高程序并發(fā)執(zhí)行，以提高資源利用率和系統(tǒng)吞吐量。那么操作系統(tǒng)中引入線程的目的，則是為了減少進程并發(fā)執(zhí)行過程中所付出的時空開銷，使操作系統(tǒng)能很好的并發(fā)執(zhí)行。

　　進程process定義了一個執(zhí)行環(huán)境，包括它自己私有的地址空間、一個句柄表，以及一個安全環(huán)境;線程則是一個控制流，有他自己的調(diào)用棧call stack，記錄了它的執(zhí)行歷史。

　　線程由兩個部分組成：1)線程的內(nèi)核對象，操作系統(tǒng)用它來對線程實施管理。內(nèi)核對象也是系統(tǒng)用來存放線程統(tǒng)計信息的地方。2)線程堆棧，它用于維護線程在執(zhí)行代碼時需要的所有參數(shù)和局部變量。當(dāng)創(chuàng)建線程時，系統(tǒng)創(chuàng)建一個線程內(nèi)核對象。該線程內(nèi)核對象不是線程本身，而是操作系統(tǒng)用來管理線程的較小的數(shù)據(jù)結(jié)構(gòu)?？梢詫⒕€程內(nèi)核對象視為由關(guān)于線程的統(tǒng)計信息組成的一個小型數(shù)據(jù)結(jié)構(gòu)。

　　進程與線程的比較如下：

比較

進程

線程

活潑性

不活潑（只是線程的容器）

活潑

地址空間

系統(tǒng)賦予的獨立的虛擬地址空間（對于32位進程來說，這個地址空間是4GB）

在進程的地址空間執(zhí)行代碼。線程只有一個內(nèi)核對象和一個堆棧，保留的記錄很少，因此所需要的內(nèi)存也很少。因為線程需要的開銷比進程少

調(diào)度

僅是資源分配的基本單位

獨立調(diào)度、分派的基本單位

并發(fā)性

僅進程間并發(fā)（傳統(tǒng)OS）

進程間、線程間并發(fā)

擁有資源

資源擁有的基本單位

基本上不擁有資源

系統(tǒng)開銷

創(chuàng)建、撤銷、切換開銷大

僅保存少量寄存器內(nèi)容，開銷小。

　　3、進程同步

　　進程同步的主要任務(wù)：是對多個相關(guān)進程在執(zhí)行次序上進行協(xié)調(diào)，以使并發(fā)執(zhí)行的諸進程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。

　　同步機制遵循的原則：

　　(1)空閑讓進;

　　(2)忙則等待(保證對臨界區(qū)的互斥訪問);

　　(3)有限等待(有限代表有限的時間，避免死等);

　　(4)讓權(quán)等待，(當(dāng)進程不能進入自己的臨界區(qū)時，應(yīng)該釋放處理機，以免陷入忙等狀態(tài))。

　　4、進程間的通信是如何實現(xiàn)的?

　　進程通信，是指進程之間的信息交換(信息量少則一個狀態(tài)或數(shù)值，多者則是成千上萬個字節(jié))。因此，對于用信號量進行的進程間的互斥和同步，由于其所交換的信息量少而被歸結(jié)為低級通信。

　　所謂高級進程通信指：用戶可以利用操作系統(tǒng)所提供的一組通信命令傳送大量數(shù)據(jù)的一種通信方式。操作系統(tǒng)隱藏了進程通信的實現(xiàn)細節(jié)?；蛘哒f，通信過程對用戶是透明的。

　　高級通信機制可歸結(jié)為三大類：

　　(1)共享存儲器系統(tǒng)(存儲器中劃分的共享存儲區(qū));實際操作中對應(yīng)的是“剪貼板”(剪貼板實際上是系統(tǒng)維護管理的一塊內(nèi)存區(qū)域)的通信方式，比如舉例如下：word進程按下ctrl+c，在ppt進程按下ctrl+v，即完成了word進程和ppt進程之間的通信，復(fù)制時將數(shù)據(jù)放入到剪貼板，粘貼時從剪貼板中取出數(shù)據(jù)，然后顯示在ppt窗口上。

　　(2)消息傳遞系統(tǒng)(進程間的數(shù)據(jù)交換以消息(message)為單位，當(dāng)今最流行的微內(nèi)核操作系統(tǒng)中，微內(nèi)核與服務(wù)器之間的通信，無一例外地都采用了消息傳遞機制。應(yīng)用舉例：郵槽(MailSlot)是基于廣播通信體系設(shè)計出來的，它采用無連接的不可靠的數(shù)據(jù)傳輸。郵槽是一種單向通信機制，創(chuàng)建郵槽的服務(wù)器進程讀取數(shù)據(jù)，打開郵槽的客戶機進程寫入數(shù)據(jù)。

　　(3)管道通信系統(tǒng)(管道即：連接讀寫進程以實現(xiàn)他們之間通信的共享文件(pipe文件，類似先進先出的隊列，由一個進程寫，另一進程讀))。實際操作中，管道分為：匿名管道、命名管道。匿名管道是一個未命名的、單向管道，通過父進程和一個子進程之間傳輸數(shù)據(jù)。匿名管道只能實現(xiàn)本地機器上兩個進程之間的通信，而不能實現(xiàn)跨網(wǎng)絡(luò)的通信。命名管道不僅可以在本機上實現(xiàn)兩個進程間的通信，還可以跨網(wǎng)絡(luò)實現(xiàn)兩個進程間的通信。

同一機器兩個進程間通信

跨網(wǎng)絡(luò)通信

剪貼板Clipboard

可以

不可以

匿名管道Pipe

可以

不可以

命名管道（點對點單一通信，數(shù)據(jù)量可較大）Namedpipe

可以

郵槽（一對多，數(shù)據(jù)量較小，424字節(jié)以下）Mailslot

可以

　　5、線程同步

　　根據(jù)用戶模式及內(nèi)核模式下的同步方式的不同，分類及對比如下：

內(nèi)核對象/

非內(nèi)核對象

含義

缺點

適用

關(guān)鍵代碼段（臨界區(qū)）CriticalSection

非內(nèi)核對象，工作在用戶方式下，為用戶模式對象

從程序代碼的角度來控制線程的并發(fā)性

1.因為在等待進入關(guān)鍵代碼段時無法設(shè)定超時值，所以其很容易進入死鎖狀態(tài)。2.不能跨進程使用。

單個進程中線程間的同步（同步速度快）

事件對象Event

內(nèi)核對象

所有內(nèi)核對象中最基本的。

速度較慢（相比用戶模式實現(xiàn)線程同步）

多個進程間的各個線程間實現(xiàn)同步

互斥對象Mutex

內(nèi)核對象

代表對一個資源的獨占式訪問

信號量

Semaphore

內(nèi)核對象

使用計數(shù)器來控制程序?qū)σ粋€共享資源的訪問

　　由于進程同步產(chǎn)生了一系列經(jīng)典的同步問題“生產(chǎn)者-消費者”問題，“哲學(xué)家進餐”問題，“讀者-寫者”問題。

　　常見的操作系統(tǒng)使用的文件系統(tǒng)整理

　　文件系統(tǒng)是操作系統(tǒng)用于明確磁盤或分區(qū)上的文件的方法和數(shù)據(jù)結(jié)構(gòu);即在磁盤上組織文件的方法。也指用于存儲文件的磁盤或分區(qū)，或文件系統(tǒng)種類。操作系統(tǒng)中負責(zé)管理和存儲文件信息的軟件機構(gòu)稱為文件管理系統(tǒng)，簡稱文件系統(tǒng)。文件系統(tǒng)由三部分組成：與文件管理有關(guān)軟件、被管理文件以及實施文件管理所需數(shù)據(jù)結(jié)構(gòu)。從系統(tǒng)角度來看，文件系統(tǒng)是對文件存儲器空間進行組織和分配，負責(zé)文件存儲并對存入的文件進行保護和檢索的系統(tǒng)。具體地說，它負責(zé)為用戶建立文件，存入、讀出、修改、轉(zhuǎn)儲文件，控制文件的存取，當(dāng)用戶不再使用時撤銷文件等。

　　【FAT】：

　　常PC機使用的文件系統(tǒng)是FAT16。像基于MS-DOS，Win 95等系統(tǒng)都采用了FAT16文件系統(tǒng)。在Win 9X下，F(xiàn)AT16支持的分區(qū)最大為2GB。我們知道計算機將信息保存在硬盤上稱為“簇”的區(qū)域內(nèi)。使用的簇越小，保存信息的效率就越高。在FAT16的情況下，分區(qū)越大簇就相應(yīng)的要大，存儲效率就越低，勢必造成存儲空間的浪費。并且隨著計算機硬件和應(yīng)用的不斷提高，F(xiàn)AT16文件系統(tǒng)已不能很好地適應(yīng)系統(tǒng)的要求。在這種情況下，推出了增強的文件系統(tǒng)FAT32。同F(xiàn)AT16相比，F(xiàn)AT32主要具有以下特點：

　　1、同F(xiàn)AT16相比FAT32最大的優(yōu)點是可以支持的磁盤大小達到32G，但是不能支持小于512MB的分區(qū)。

　　_于FAT32的Win 2000可以支持分區(qū)最大為32GB;而基于 FAT16的Win 2000支持的分區(qū)最大為4GB。

　　2、由于采用了更小的簇，F(xiàn)AT32文件系統(tǒng)可以更有效率地保存信息。如兩個分區(qū)大小都為2GB，一個分區(qū)采用了FAT16文件系統(tǒng)，另一個分區(qū)采用了FAT32文件系統(tǒng)。采用FAT16的分區(qū)的簇大小為32KB，而FAT32分區(qū)的簇只有4KB的大小。這樣FAT32就比FAT16的存儲效率要高很多，通常情況下可以提高15%。

　　3、FAT32文件系統(tǒng)可以重新定位根目錄和使用FAT的備份副本。另外FAT32分區(qū)的啟動記錄被包含在一個含有關(guān)鍵數(shù)據(jù)的結(jié)構(gòu)中，減少了計算機系統(tǒng)崩潰的可能性。

　　【NTFS】：

　　NTFS文件系統(tǒng)是一個基于安全性的文件系統(tǒng)，是Windows NT所采用的獨特的文件系統(tǒng)結(jié)構(gòu)，它是建立在保護文件和目錄數(shù)據(jù)基礎(chǔ)上，同時照顧節(jié)省存儲資源、減少磁盤占用量的一種先進的文件系統(tǒng)。使用非常廣泛的Windows NT 4.0采用的就是NTFS 4.0文件系統(tǒng)，相信它所帶來的強大的系統(tǒng)安全性一定給廣大用戶留下了深刻的印象。Win 2000采用了更新版本的NTFS文件系統(tǒng)??NTFS 5.0，它的推出使得用戶不但可以像Win 9X那樣方便快捷地操作和管理計算機，同時也可享受到NTFS所帶來的系統(tǒng)安全性。

　　NTFS 5.0的特點主要體現(xiàn)在以下幾個方面：

　　1、NTFS可以支持的分區(qū)(如果采用動態(tài)磁盤則稱為卷)大小可以達到2TB。而Win 2000中的FAT32支持分區(qū)的大小最大為32GB。

　　2、NTFS是一個可恢復(fù)的文件系統(tǒng)。在NTFS分區(qū)上用戶很少需要運行磁盤修復(fù)程序。NTFS通過使用標(biāo)準(zhǔn)的事物處理日志和恢復(fù)技術(shù)來保證分區(qū)的一致性。發(fā)生系統(tǒng)失敗事件時，NTFS使用日志文件和檢查點信息自動恢復(fù)文件系統(tǒng)的一致性。

　　3、NTFS支持對分區(qū)、文件夾和文件的壓縮。任何基于Windows的應(yīng)用程序?qū)TFS分區(qū)上的壓縮文件進行讀寫時不需要事先由其他程序進行解壓縮，當(dāng)對文件進行讀取時，文件將自動進行解壓縮;文件關(guān)閉或保存時會自動對文件進行壓縮。

　　4、NTFS采用了更小的簇，可以更有效率地管理磁盤空間。在Win 2000的FAT32文件系統(tǒng)的情況下，分區(qū)大小在2GB～8GB時簇的大小為4KB;分區(qū)大小在8GB～16GB時簇的大小為8KB;分區(qū)大小在16GB～32GB時，簇的大小則達到了16KB。而Win 2000的NTFS文件系統(tǒng)，當(dāng)分區(qū)的大小在2GB以下時，簇的大小都比相應(yīng)的FAT32簇小;當(dāng)分區(qū)的大小在2GB以上時(2GB～2TB)，簇的大小都為4KB。相比之下，NTFS可以比FAT32更有效地管理磁盤空間，最大限度地避免了磁盤空間的浪費。

　　5、在NTFS分區(qū)上，可以為共享資源、文件夾以及文件設(shè)置訪問許可權(quán)限。許可的設(shè)置包括兩方面的內(nèi)容：一是允許哪些組或用戶對文件夾、文件和共享資源進行訪問;二是獲得訪問許可的組或用戶可以進行什么級別的訪問。訪問許可權(quán)限的設(shè)置不但適用于本地計算機的用戶，同樣也應(yīng)用于通過網(wǎng)絡(luò)的共享文件夾對文件進行訪問的網(wǎng)絡(luò)用戶。與FAT32文件系統(tǒng)下對文件夾或文件進行訪問相比，安全性要高得多。另外，在采用NTFS格式的Win 2000中，應(yīng)用審核策略可以對文件夾、文件以及活動目錄對象進行審核，審核結(jié)果記錄在安全日志中，通過安全日志就可以查看哪些組或用戶對文件夾、文件或活動目錄對象進行了什么級別的操作，從而發(fā)現(xiàn)系統(tǒng)可能面臨的非法訪問，通過采取相應(yīng)的措施，將這種安全隱患減到最低。這些在FAT32文件系統(tǒng)下，是不能實現(xiàn)的。

　　6、在Win 2000的NTFS文件系統(tǒng)下可以進行磁盤配額管理。磁盤配額就是管理員可以為用戶所能使用的磁盤空間進行配額限制，每一用戶只能使用最大配額范圍內(nèi)的磁盤空間。設(shè)置磁盤配額后，可以對每一個用戶的磁盤使用情況進行跟蹤和控制，通過監(jiān)測可以標(biāo)識出超過配額報警閾值和配額限制的用戶，從而采取相應(yīng)的措施。磁盤配額管理功能的提供，使得管理員可以方便合理地為用戶分配存儲資源，避免由于磁盤空間使用的失控可能造成的系統(tǒng)崩潰，提高了系統(tǒng)的安全性。

　　7、NTFS使用一個“變更”日志來跟蹤記錄文件所發(fā)生的變更。

　　【Ext2】：

　　Ext2是 GNU/Linux 系統(tǒng)中標(biāo)準(zhǔn)的文件系統(tǒng)，其特點為存取文件的性能極好，對于中小型的文件更顯示出優(yōu)勢，這主要得利于其簇快取層的優(yōu)良設(shè)計。

　　其單一文件大小與文件系統(tǒng)本身的容量上限與文件系統(tǒng)本身的簇大小有關(guān)，在一般常見的 x86 電腦系統(tǒng)中，簇最大為 4KB，則單一文件大小上限為 2048GB，而文件系統(tǒng)的容量上限為 16384GB。

　　但由于目前核心 2.4 所能使用的單一分割區(qū)最大只有 2048GB，實際上能使用的文件系統(tǒng)容量最多也只有 2048GB。

　　至于Ext3文件系統(tǒng)，它屬于一種日志文件系統(tǒng)，是對ext2系統(tǒng)的擴展。它兼容ext2，并且從ext2轉(zhuǎn)換成ext3并不復(fù)雜。

　　【Ext3】：

　　Ext3是一種日志式文件系統(tǒng)，是對ext2系統(tǒng)的擴展，它兼容ext2。日志式文件系統(tǒng)的優(yōu)越性在于：由于文件系統(tǒng)都有快取層參與運作，如不使用時必須將文件系統(tǒng)卸下，以便將快取層的資料寫回磁盤中。因此每當(dāng)系統(tǒng)要關(guān)機時，必須將其所有的文件系統(tǒng)全部shutdown后才能進行關(guān)機。

　　如果在文件系統(tǒng)尚未shutdown前就關(guān)機 (如停電) 時，下次重開機后會造成文件系統(tǒng)的資料不一致，故這時必須做文件系統(tǒng)的重整工作，將不一致與錯誤的地方修復(fù)。然而，此一重整的工作是相當(dāng)耗時的，特別是容量大的文件系統(tǒng)，而且也不能百分之百保證所有的資料都不會流失。

　　為了克服此問題，使用所謂‘日志式文件系統(tǒng) (Journal File System) ’。此類文件系統(tǒng)最大的特色是，它會將整個磁盤的寫入動作完整記錄在磁盤的某個區(qū)域上，以便有需要時可以回溯追蹤。

　　由于資料的寫入動作包含許多的細節(jié)，像是改變文件標(biāo)頭資料、搜尋磁盤可寫入空間、一個個寫入資料區(qū)段等等，每一個細節(jié)進行到一半若被中斷，就會造成文件系統(tǒng)的不一致，因而需要重整。

　　然而，在日志式文件系統(tǒng)中，由于詳細紀(jì)錄了每個細節(jié)，故當(dāng)在某個過程中被中斷時，系統(tǒng)可以根據(jù)這些記錄直接回溯并重整被中斷的部分，而不必花時間去檢查其他的部分，故重整的工作速度相當(dāng)快，幾乎不需要花時間。

　　【Ext4】：

　　Linux kernel 自 2.6.28 開始正式支持新的文件系統(tǒng) Ext4。Ext4 是 Ext3 的改進版，修改了 Ext3 中部分重要的數(shù)據(jù)結(jié)構(gòu)，而不僅僅像 Ext3 對 Ext2 那樣，只是增加了一個日志功能而已。Ext4 可以提供更佳的性能和可靠性，還有更為豐富的功能：

　　1、與 Ext3 兼容。執(zhí)行若干條命令，就能從 Ext3 在線遷移到 Ext4，而無須重新格式化磁盤或重新安裝系統(tǒng)。原有 Ext3 數(shù)據(jù)結(jié)構(gòu)照樣保留，Ext4 作用于新數(shù)據(jù)，當(dāng)然，整個文件系統(tǒng)因此也就獲得了 Ext4 所支持的更大容量。

　　2、更大的文件系統(tǒng)和更大的文件。較之 Ext3 目前所支持的最大 16TB 文件系統(tǒng)和最大 2TB 文件，Ext4 分別支持 1EB(1，048，576TB， 1EB=1024PB， 1PB=1024TB)的文件系統(tǒng)，以及 16TB 的文件。

　　3、無限數(shù)量的子目錄。Ext3 目前只支持 32，000 個子目錄，而 Ext4 支持無限數(shù)量的子目錄。

　　4、Extents。Ext3 采用間接塊映射，當(dāng)操作大文件時，效率極其低下。比如一個 100MB 大小的文件，在 Ext3 中要建立 25，600 個數(shù)據(jù)塊(每個數(shù)據(jù)塊大小為 4KB)的映射表。而 Ext4 引入了現(xiàn)代文件系統(tǒng)中流行的 extents 概念，每個 extent 為一組連續(xù)的數(shù)據(jù)塊，上述文件則表示為“該文件數(shù)據(jù)保存在接下來的 25，600 個數(shù)據(jù)塊中”，提高了不少效率。

　　5、多塊分配。當(dāng)寫入數(shù)據(jù)到 Ext3 文件系統(tǒng)中時，Ext3 的數(shù)據(jù)塊分配器每次只能分配一個 4KB 的塊，寫一個 100MB 文件就要調(diào)用 25，600 次數(shù)據(jù)塊分配器，而 Ext4 的多塊分配器“multiblock allocator”(mballoc) 支持一次調(diào)用分配多個數(shù)據(jù)塊。

　　6、延遲分配。Ext3 的數(shù)據(jù)塊分配策略是盡快分配，而 Ext4 和其它現(xiàn)代文件操作系統(tǒng)的策略是盡可能地延遲分配，直到文件在 cache 中寫完才開始分配數(shù)據(jù)塊并寫入磁盤，這樣就能優(yōu)化整個文件的數(shù)據(jù)塊分配，與前兩種特性搭配起來可以顯著提升性能。

　　7、快速 fsck。以前執(zhí)行 fsck 第一步就會很慢，因為它要檢查所有的 inode，現(xiàn)在 Ext4 給每個組的 inode 表中都添加了一份未使用 inode 的列表，今后 fsck Ext4 文件系統(tǒng)就可以跳過它們而只去檢查那些在用的 inode 了。

　　8、日志校驗。日志是最常用的部分，也極易導(dǎo)致磁盤硬件故障，而從損壞的日志中恢復(fù)數(shù)據(jù)會導(dǎo)致更多的數(shù)據(jù)損壞。Ext4 的日志校驗功能可以很方便地判斷日志數(shù)據(jù)是否損壞，而且它將 Ext3 的兩階段日志機制合并成一個階段，在增加安全性的同時提高了性能。

　　9、“無日志”(No Journaling)模式。日志總歸有一些開銷，Ext4 允許關(guān)閉日志，以便某些有特殊需求的用戶可以借此提升性能。

　　10、在線碎片整理。盡管延遲分配、多塊分配和 extents 能有效減少文件系統(tǒng)碎片，但碎片還是不可避免會產(chǎn)生。Ext4 支持在線碎片整理，并將提供 e4defrag 工具進行個別文件或整個文件系統(tǒng)的碎片整理。

　　11、inode 相關(guān)特性。Ext4 支持更大的 inode，較之 Ext3 默認的 inode 大小 128 字節(jié)，Ext4 為了在 inode 中容納更多的擴展屬性(如納秒時間戳或 inode 版本)，默認 inode 大小為 256 字節(jié)。Ext4 還支持快速擴展屬性(fast extended attributes)和 inode 保留(inodes reservation)。

　　12、持久預(yù)分配(Persistent preallocation)。P2P 軟件為了保證下載文件有足夠的空間存放，常常會預(yù)先創(chuàng)建一個與所下載文件大小相同的空文件，以免未來的數(shù)小時或數(shù)天之內(nèi)磁盤空間不足導(dǎo)致下載失敗。Ext4 在文件系統(tǒng)層面實現(xiàn)了持久預(yù)分配并提供相應(yīng)的 API(libc 中的 posix_fallocate())，比應(yīng)用軟件自己實現(xiàn)更有效率。

　　13、默認啟用 barrier。磁盤上配有內(nèi)部緩存，以便重新調(diào)整批量數(shù)據(jù)的寫操作順序，優(yōu)化寫入性能，因此文件系統(tǒng)必須在日志數(shù)據(jù)寫入磁盤之后才能寫 commit 記錄，若 commit 記錄寫入在先，而日志有可能損壞，那么就會影響數(shù)據(jù)完整性。Ext4 默認啟用 barrier，只有當(dāng) barrier 之前的數(shù)據(jù)全部寫入磁盤，才能寫 barrier 之后的數(shù)據(jù)。(可通過 “mount -o barrier=0” 命令禁用該特性。)

　　【ZFS】：

　　ZFS源自于Sun Microsystems為Solaris操作系統(tǒng)開發(fā)的文件系統(tǒng)。ZFS是一個具有高存儲容量、文件系統(tǒng)與卷管理概念整合、嶄新的磁盤邏輯結(jié)構(gòu)的輕量級文件系統(tǒng)，同時也是一個便捷的存儲池管理系統(tǒng)。ZFS是一個使用CDDL協(xié)議條款授權(quán)的開源項目。

　　【HFS】：

　　1、HFS文件系統(tǒng)概念

　　分層文件系統(tǒng)(Hierarchical File System，HFS)是一種由蘋果電腦開發(fā)，并使用在Mac OS上的文件系統(tǒng)。最初被設(shè)計用于軟盤和硬盤，同時也可以在在只讀媒體如CD-ROM上見到。

　　2、HFS文件系統(tǒng)開發(fā)過程

　　HFS首次出現(xiàn)在1985年9月17日，作為Macintosh電腦上新的文件系統(tǒng)。它取代只用于早期Mac型號所使用的平面文件系統(tǒng)Macintosh File System(MFS)。因為Macintosh電腦所產(chǎn)生的數(shù)據(jù)，比其它通常的文件系統(tǒng)，如DOS使用的FAT或原始Unix文件系統(tǒng)所允許存儲的數(shù)據(jù)更多。蘋果電腦開發(fā)了一種新式更適用的文件系統(tǒng)，而不是采用現(xiàn)有的規(guī)格。例如，HFS允許文件名最多有31個字符的長度，支持metadata和雙分支(每個文件的數(shù)據(jù)和資源支分開存儲)文件。

　　盡管HFS象其它大多數(shù)文件系統(tǒng)一樣被視為專有的格式，因為只有它為大多數(shù)最新的操作系統(tǒng)提供了很好的通用解決方法以存取HFS格式磁盤。

　　在1998年，蘋果電腦發(fā)布了HFS Plus，其改善了HFS對磁盤空間的地址定位效率低下，并加入了其它的改進。當(dāng)前版本的Mac OS仍舊支持HFS，但從Mac OS X開始HFS卷不能作為啟動用。

　　3、構(gòu)成方式

　　分層文件系統(tǒng)把一個卷分為許多512字節(jié)的“邏輯塊”。這些邏輯塊被編組為“分配塊”，這些分配塊可以根據(jù)卷的尺寸包含一個或多個邏輯塊。HFS對地址分配塊使用16位數(shù)值，分配塊的最高限制數(shù)量是65536。

　　組成一個HFS卷需要下面的五個結(jié)構(gòu)：

　　1)卷的邏輯塊0和1是啟動塊，它包含了系統(tǒng)啟動信息。例如，啟動時載入的系統(tǒng)名稱和殼(通常是Finder)文件。

　　2)邏輯塊2包含主目錄塊(Master Directory Block，簡稱MDB)。

　　3)邏輯塊3是卷位圖(Volume Bitmap)的啟動塊，它追蹤分配塊使用狀態(tài)。

　　4)總目錄文件(Catalog File)是一個包含所有文件的記錄和儲存在卷中目錄的B_tree。

　　5)擴展溢出文件(Extent Overflow File)是當(dāng)最初總目錄文件中三個擴展占用后，另外一個包含額外擴展記錄的分配塊對應(yīng)信息的B_tree。

　　內(nèi)核怎樣管理你的內(nèi)存

　　在分析了進程的虛擬地址布局，我們轉(zhuǎn)向內(nèi)核以及他管理用戶內(nèi)存的機制。下圖是gonzo的例子：

　　Linux的進程在內(nèi)核中是由task_struct進程描述符實現(xiàn)的，task_struct的mm字段指向內(nèi)存描述符mm_struct，他是進程的一個內(nèi)存執(zhí)行摘要。如上圖所示，mm_struct存儲了內(nèi)存各個段的開始和結(jié)束地址、進程所使用的內(nèi)存頁面數(shù)(rss代表常駐集合大小)、使用的虛擬地址空間總數(shù)等等。在內(nèi)存描述符中我們也可以找到兩個用于管理進程內(nèi)層的字段：虛擬內(nèi)存集合和頁表。Gonzo的內(nèi)存區(qū)域如下圖：

　　每個虛擬內(nèi)存區(qū)域(VMA)是一個虛擬地址空間上連續(xù)的區(qū)域;這些區(qū)域不會彼此覆蓋。Vm_area_struct結(jié)構(gòu)描述了一個內(nèi)存區(qū)域，包括他的開始和技術(shù)地址、flags字段指定了他的行為和訪問權(quán)限，vm_file字段指定了該區(qū)域映射的實際文件。一個沒有映射文件的VMA成為匿名的。除了內(nèi)存映射段以外，上面的每個內(nèi)存段(堆、棧等等)相當(dāng)于一個單獨的VMA。這不是必須的，盡管在x86機器上通常是這樣。VMA不會關(guān)心他在哪個段里面。

　　一個進程的所有VMA以兩種方式存儲在他的內(nèi)存描述符中，一種是以鏈表的方式存放在mmap字段，以開始虛擬地址進行了排序，另一種是以紅黑樹的方式存放，mm_rb字段為這顆紅黑樹的根。紅黑樹可以讓內(nèi)核根據(jù)給定的虛擬地址快速地找到內(nèi)存區(qū)域。當(dāng)我們讀取文件/proc/pid_of_process/maps，內(nèi)核僅僅是通過進程VMA的鏈接同時打印出每一個。

　　計算機組成

　　計算機的運行簡單理解為這三層：硬件即組成計算機的所有摸得見看得著的東西是計算機運行的基礎(chǔ);應(yīng)用程序即完成特定功能、目的的用戶程序是計算機的價值體現(xiàn);中間就是操作系統(tǒng)，連接了硬件和應(yīng)用程序負責(zé)硬件調(diào)度、資源管理和分配(內(nèi)存、文件、CPU等等)、安全等一系列功能。

　　硬件層

　　主要硬件包括CPU(算術(shù)、邏輯單元)、主存、輔助存儲、系統(tǒng)總線、I/O設(shè)備(即輸入輸出)。

　　CPU：

　　CPU本身(Processor)可以是單核、多核、多CPU架構(gòu)，主要目的就是滿足日益增長的運算需求。單核比較簡單，多核(包括一CPU多核心和多CPU)立即涉及到核心之間高速緩存的共享，此處是CPU內(nèi)置高速緩存非主存，進程之間寄存器數(shù)據(jù)的共享和進程處理器調(diào)度問題。

　　總線：

　　總線連接了所有的設(shè)備提供通訊的能力，注意設(shè)備之間同一時間的通信是會沖突的，這就要涉及到總線的決策，負責(zé)決策的可能是CPU或?qū)Ｓ行酒Ｋ性O(shè)備需要通信時要提交通信請求有CPU決定下一個通信的設(shè)備。

　　另外一個問題顯然連接到總線上的設(shè)備越多，沖突的幾率就越大效率越差。所以總線可以有多層總線設(shè)計，比如設(shè)置I/O總線所有的I/O設(shè)備都通過I/O總線和I/O控制器連接，I/O控制器則連接在系統(tǒng)總線上代理I/O的通信請求。

　　速度：

　　CPU飛快，其中CPU內(nèi)置的一級高速緩存保持了和CPU同樣的速度但是容量極小，接下來可能存在二級、三級高速緩存;主存(內(nèi)存)其次和CPU存在數(shù)量級上的差距;輔寸(多硬盤)的速度就不是一般的慢了，因為有機械運動，但是容量大很多;I/O設(shè)備多數(shù)慢的要死，但不是沒有快的(比如圖形、千兆以太網(wǎng)的速度是超過硬盤的)。總而言之就是快的太貴，賤的太慢，訪問快的斷電數(shù)據(jù)即失效，不失效的訪問慢，所以就有了多級存儲的設(shè)計。程序的運行必然是加載到主存的(內(nèi)存)!

　　局部性：

　　多級存儲的設(shè)計得益于局限性能夠大幅提升性能。局限性本身分為時間局限性和空間局限性。時間局限性是說現(xiàn)在用到的指令很可能短時間內(nèi)還會多次調(diào)用，空間局限性是現(xiàn)在調(diào)用的數(shù)據(jù)在輔寸上鄰接的塊很可能即將被用到。就是因為局限性的存在預(yù)讀取才有了市場(所以有了磁盤整理)，當(dāng)然局限性是必然的——程序肯定趨向于統(tǒng)一存取、循環(huán)、分支邏輯肯定是指令的循環(huán)調(diào)用。——好的命中率決定了計算機的性能。

　　指令周期(取指周期)：

　　計算機中CPU始終是取指-》執(zhí)行的動作循環(huán)運行的，計算機從取指到完成指令的周期稱為取指周期。因此針對CPU的性能優(yōu)化有流水線和超標(biāo)量體系結(jié)構(gòu)，前者目的在于合理分割指令使取指和執(zhí)行能夠并行進行(預(yù)取指)，后者則通過相同的運算結(jié)構(gòu)重復(fù)設(shè)置實現(xiàn)多條指令同時執(zhí)行(得益于指令的亂序執(zhí)行)。

　　I/O設(shè)備進化：

　　I/O設(shè)備一般較慢，極端點的比如鍵盤這貨簡直慢的沒法說。那么當(dāng)程序需要讀取I/O數(shù)據(jù)時(如讀取一塊數(shù)據(jù)、監(jiān)聽鍵盤輸入)就會被I/O設(shè)備阻塞，這是最差的情況整個系統(tǒng)空轉(zhuǎn)直到I/O設(shè)備讀取數(shù)據(jù)完成。

　　于是有了可編程I/O設(shè)備——你可以定期問我準(zhǔn)備好數(shù)據(jù)了沒，好了你就取沒好你就干別的去，也就是輪詢這法子還是非常慢因為CPU要定期過來問而且多數(shù)情況都是沒準(zhǔn)備好空耗系統(tǒng)資源(進程切換)。

　　再后來有了中斷，前提是指令的運行是可被中斷和恢復(fù)的(現(xiàn)在當(dāng)然都可以，把寄存器數(shù)據(jù)保存到緩存，完了再恢復(fù)嘛)，需要讀取的時候CPU發(fā)給I/O指令然后不理它了，需要讀取的進程(或線程)進入阻塞狀態(tài)換下一個進程來執(zhí)行，當(dāng)I/O準(zhǔn)備好數(shù)據(jù)后發(fā)送一個中斷信號給CPU，這時現(xiàn)在執(zhí)行的進程被中斷CPU會執(zhí)行一段中斷處理程序(通常很短)把之前阻塞的進程標(biāo)記為Ready(可執(zhí)行)狀態(tài)，處理完中斷后恢復(fù)之前中斷的進程(或線程)繼續(xù)執(zhí)行。在當(dāng)前進程執(zhí)行完或者超時中斷后(分時多道程序處理，超時也是一種中斷)，之前從阻塞中恢復(fù)的進程可能會被執(zhí)行(取決于進程調(diào)度，不一定是下一個時間片里也可能是下幾個時間片后或者干脆餓死了)。

　　再后來又有了DMA(直接存儲器訪問)，主要原因就是CPU很忙，你一個拷貝/傳輸整塊數(shù)據(jù)的動作就不要每塊數(shù)據(jù)都讓我來處理了，系統(tǒng)中多了一個專門的輔助芯片干這個事情。CPU下達指令后輔助芯片負責(zé)設(shè)備之間的數(shù)據(jù)直接傳輸。DMA模塊可以是總線中的一個模塊也可以是I/O模塊，但是仍然要占用總線(傳輸數(shù)據(jù))所以并不是不會對系統(tǒng)性能產(chǎn)生影響，至少DMA沖突時CPU要等待一個總線周期。

　　操作系統(tǒng)

　　看完硬件層(簡單看看，后面可能還要回頭)，再來看看操作系統(tǒng)層。最基本的元素肯定要包括進程、線程等等用于程序的執(zhí)行。

　　操作系統(tǒng)

　　操作系統(tǒng)目的：

　　方便：簡化了計算機的使用，無論是用戶還是開發(fā)者角度都極大的簡化了對計算機的使用。用戶角度提供了交互的能力，開發(fā)者角度提供了底層設(shè)備的接口、公共庫等等。

　　有效：提高計算機的利用效率。對于操作系統(tǒng)CPU運算、內(nèi)存、輔存、I/O等等都是資源，如何能最大的利用資源是計算機要考慮的事情。(沒有操作系統(tǒng)的年代顯然效率非常低，同一時間只運行一個程序計算資源多數(shù)時間都在等待I/O設(shè)備、人等)。

　　擴展的能力：在不阻礙服務(wù)前提下開發(fā)、測試、加入新的計算機能力。比如安裝個程序、加個設(shè)備。

　　操作系統(tǒng)發(fā)展

　　串行處理：這是個久遠的年代(上世紀(jì)50年代也不算太遠哈),計算機一次只能運行一個程序，要通過輸入設(shè)備讀入程序(讀卡器吧)運行結(jié)束后再將結(jié)果輸出到打印機。這個年代是沒有操作系統(tǒng)的。

　　簡單批處理：這個算是操作系統(tǒng)的鼻祖吧?就是常駐內(nèi)存的一個監(jiān)控程序，要運行的程序被管理員組織成一批，監(jiān)控程序從存儲器(卡片或磁帶)讀取要執(zhí)行的Job將處理器控制權(quán)轉(zhuǎn)交給程序運行結(jié)束后(成功或失敗)控制權(quán)返回監(jiān)控程序繼續(xù)讀入下一個任務(wù)。

　　簡單批處理節(jié)約了計算機調(diào)度和準(zhǔn)備的時間——任務(wù)不再是一個一個的處理了，變成一批了。

　　多道程序批處理：現(xiàn)代操作系統(tǒng)進程切換之父?哈哈。由于內(nèi)存的加大除了容納操作系統(tǒng)、一個程序以外還有足夠的空間容納第二、第三個程序，所以就有了同時運行多個程序的能力。在第一個程序被阻塞后(I/O等)，可以轉(zhuǎn)交控制權(quán)個第二、第三個程序。

　　多道程序批處理節(jié)約了CPU等待I/O等慢速設(shè)備的時間，這個效率的提升非常客觀。

　　分時操作系統(tǒng)：注意關(guān)注在人的交互上。人肯定是比I/O還慢的設(shè)備了，由于早年計算機資源的稀缺當(dāng)然要達到多人共用一臺機器的目的。分時操作系統(tǒng)把計算機資源做時間切片，用戶通過終端連接到計算機，每個中斷都獲取到時間切片內(nèi)的計算資源，由于人是反應(yīng)很鈍的，所以就像沒人都有一臺計算機服務(wù)一樣。

　　操作系統(tǒng)的幾張表

　　Memory table：記錄內(nèi)存的使用情況，回收和分配內(nèi)存時這里都會被更新。

　　I/O table：記錄I/O設(shè)備和通道的情況。

　　File table：文件系統(tǒng)的占用情況，文件是否存在，文件狀態(tài)。

　　Process table：管理進程。

　　進程和線程

　　進程

　　進程包括程序代碼和一組(set)數(shù)據(jù)，是程序運行的實體(應(yīng)該能算作最小單元吧，線程能執(zhí)行的是一段邏輯，一個程序的啟動至少是一個或多個進程)。

　　進程的組成：

　　進程所有屬性的集合被稱為進程映像(Process Image)，這之中一共包括四部分：用戶程序(User Program)、數(shù)據(jù)(User Data)、棧(Stack)和進程控制塊(Process Control Block)。

　　用戶程序：要執(zhí)行的程序。

　　數(shù)據(jù)：用戶空間中可以被用戶修改的部分。比如進程數(shù)據(jù)、可修改程序。

　　Stack：每個進程都有一個或者多個棧用于保存參數(shù)、過程調(diào)用地址、系統(tǒng)調(diào)用地址。

　　進程控制塊：操作系統(tǒng)控制進程需要的數(shù)據(jù)。包含了進程的屬性，最基本的每個進程總要有個Id吧，還有進程狀態(tài)、當(dāng)前寄存器的值、程序計數(shù)器、Stack的指針等等。

　　進程狀態(tài)切換

　　最起碼的兩個狀態(tài)：Ready、Running，進程自創(chuàng)建后進入Ready狀態(tài)也就是可以執(zhí)行的，這時的進程進入等待隊列知道進程調(diào)度輪到自己執(zhí)行時才能夠被分配資源進入執(zhí)行狀體Running。

　　進程的基本狀態(tài)一共五個，包括上面兩個以外還會有被阻塞的情況(I/O、等待生產(chǎn)者生產(chǎn)、信號量等等)所以存在Blocked狀態(tài)，進程創(chuàng)建過程中存在New狀態(tài)、進程運行終結(jié)后處于Exit狀態(tài)等待操作系統(tǒng)做進一步處理并銷毀進程。

　　進程狀態(tài)之間的切換可以參考圖中進程狀態(tài)部分，大體過程：進程被允許創(chuàng)建進入New狀態(tài)，這個過程中要分配進程Id、劃分內(nèi)存區(qū)域、初始化PCB(Process control block)、連接和創(chuàng)建或擴展其它的數(shù)據(jù);上述過程完成以后進程可以運行了所以進入Ready狀態(tài)等待系統(tǒng)調(diào)度;終于等到自己運行了，進程為Running狀態(tài)這時候可能出現(xiàn)幾種情況。1，進程運行結(jié)束進入Exit狀態(tài)等待銷毀。2，進程運行超時重新進入Ready狀態(tài)等待下一次調(diào)度。3，進程被阻塞了進入Block狀態(tài)等待所需要的數(shù)據(jù)或信號準(zhǔn)備好，重新喚醒進入Ready狀態(tài)。除此以外還有兩個掛起狀態(tài)，見下面的切換。

　　調(diào)度的示意圖參考進程調(diào)度示意子圖，其中一個改進是操作系統(tǒng)很可能為不同的中斷事件設(shè)立不同的阻塞隊列，以便提高效率。

　　進程切換(Swapping)：

　　說白了還是CPU計算資源寶貴和內(nèi)存有限(內(nèi)存在漲吃內(nèi)存的程序也在漲)。為了能讓更多的進程可以同時執(zhí)行(實際上不是同時是調(diào)度)，程序運行中有很大一部分會被I/O阻塞——原因是I/O太慢了，所以即便你要的數(shù)據(jù)不多那這個取數(shù)的過程CPU也夠跑很多其它程序的了。所以導(dǎo)致的問題就是在內(nèi)存中的進程都阻塞了，內(nèi)存沒地方了，CPU依然閑的蛋疼，怎么辦?把硬盤上畫出一塊地兒(個人理解就是windows下的虛擬內(nèi)存、Linux中的swap)，塞得比較久的那些進程你們先出去待會，換些后面排著的進來。

　　看到進程切換的子圖中除了五個狀態(tài)以外還有兩個掛起態(tài)(就緒/掛起、阻塞/掛起)就是這個情況。雖然把進程從硬盤換入換出這個開銷非常高，但是硬盤比起I/O設(shè)備還是快了很多，所以這一步是有價值的。

　　當(dāng)然還有一個路子是虛擬內(nèi)存的時候，這個稍晚的時候再扯進來。

　　進程執(zhí)行模式：

　　用戶模式和內(nèi)核模式，這兩個模式還有多個別名不記錄了。這是出于操作系統(tǒng)安全考慮的，有些重要的指令就只有內(nèi)核模式下才能被CPU執(zhí)行(硬件支持)，總不能任意來個程序什么事情都給他干吧。

　　有了執(zhí)行模式就算有模式的切換，比如進程要調(diào)用系統(tǒng)操作時(system call)就有可能從用戶模式切換到內(nèi)核模式，system call執(zhí)行后也會在切換回去。

　　多線程定義

　　多線程是指進程內(nèi)支持并發(fā)路徑執(zhí)行的能力。

　　與進程的關(guān)系

　　一個進程至少包含一個線程，當(dāng)進程中存在多個線程的時各個線程可以共享進程內(nèi)的資源。進程內(nèi)的線程共享進程的用戶空間，操作系統(tǒng)仍然通過進程控制塊控制進程進而影響到線程。線程本事具備自己的線程控制塊、用戶棧和系統(tǒng)棧。

　　創(chuàng)建方式

　　由于線程類型的不同(下面介紹)線程可以是操作系統(tǒng)創(chuàng)建的也可以使通過線程庫(Lib)由進程自己創(chuàng)建的，對于進程創(chuàng)建的線程操作系統(tǒng)是不知道的。

　　線程優(yōu)勢

　　l 創(chuàng)建時間開銷遠小于進程的創(chuàng)建。因為不需要分配用戶空間和那么多初始化動作。

　　l 銷毀線程的成本也遠低于進程。

　　l 線程之間的切換消耗低于進程，特別是同一進程內(nèi)的線程切換消耗更低。

　　l 線程間通信的效率比進程間通信要高，因為進城之間安全性問題需要隔離和互斥，同一進程內(nèi)的線程可以共享進程資源而不需要提前獲取鎖。

　　線程同步

　　進程也涉及到同步，但是線程的同步更需要開發(fā)者注意。上面提到了線程共享進程的資源并且不需要獲取鎖，所以線程之間是沒有操作系統(tǒng)來保證隔離的。

　　線程類型

　　類型分為用戶級線程和內(nèi)核級線程。用戶級線程即通過Lib創(chuàng)建的對操作系統(tǒng)是透明的，內(nèi)核級線程是由操作系統(tǒng)創(chuàng)建的。

用戶級

內(nèi)核級

通過線程庫創(chuàng)建，對操作系統(tǒng)不可見

由操作系統(tǒng)來管理

比內(nèi)核級的線程更高效，不涉及模式切換

在線程切換時需要模式切換（因為是調(diào)用系統(tǒng)級的指令）

進程中同時只能有一個線程在運行，還是多段程序的思路

線程可以并發(fā)運行，特別指多核計算機

一旦被阻塞整個進程就被阻塞，也就是所有的線程都完蛋了

只會阻塞引起阻塞的線程

　　線程的四個應(yīng)用場景

　　l 前后臺運算：即有UI和后臺運算的程序，你總不希望后臺數(shù)據(jù)運算時前面的UI界面就對用戶沒響應(yīng)了吧?所以這里應(yīng)該分開線程，后臺啟動單獨的線程運算，界面在不同的線程了所有能時時相應(yīng)用戶的操作(哪怕只是提示計算中)。

　　l 異步計算：比如應(yīng)對電路故障的實時備份功能，通過線程無論是在代碼量上還是開銷上都要比你編寫定時調(diào)度的功能要高效。

　　l 速度敏感的運算：多線程的計算機可以在計算一組數(shù)據(jù)的同時讀入下一組數(shù)據(jù)(當(dāng)然弄幾個進程干這事兒也可以，但是開銷明顯更大)。

　　l 模塊化的程序架構(gòu)：對于包含多個活動或者多個源頭和目標(biāo)的輸入輸出程序，也許更容易使用多線程來設(shè)計和實現(xiàn)(就是每個線程干一攤子事兒，大家數(shù)據(jù)在一起自己取誰也別干涉誰)。

　　l 另外的比如Java程序，每個程序就是一個JVM的進程，至于這里面你起多少線程操作系統(tǒng)是不關(guān)心的。

　　并發(fā)性

　　競爭條件

　　競爭條件發(fā)生在多進程或者多線程同時修改同一個數(shù)據(jù)項的情況下，這時數(shù)據(jù)的最終結(jié)果依賴于各個進程(線程)執(zhí)行的順序(也就是結(jié)果不是唯一確定的了，比如同時修改變量b，P1執(zhí)行b = 1， P2執(zhí)行b = 2結(jié)果有競爭失敗者決定)。

　　臨界區(qū)

　　類似于b的這種資源稱為臨界資源(critical resource)，程序中操作臨界資源的程序段稱為臨界區(qū)(critical section)。就是說事兒肯定是出在臨界區(qū)里的。

　　互斥(multual exclusion)

　　多個進程嘗試進入同一個不可共享的資源的時候進程間需要是互斥的。這個不可共享的資源就是上面說的臨界資源，進入的程序段即臨界區(qū)。

　　互斥的要求：

　　l 互斥是系統(tǒng)強制的。

　　l 在臨界區(qū)外掛起的進程不能夠干涉其他進程。

　　l 請求臨界資源的進程不能被無限期的延遲，即不能有死鎖。

　　l 當(dāng)沒有進程處于臨界區(qū)時，對臨界資源的請求必須立即分配。

　　l 互斥不能建立在任何關(guān)于進程相對速度或執(zhí)行順序的假設(shè)上。

　　l 一個進程在臨界區(qū)的時間應(yīng)該是有限的。

　　進程交互

　　進程交互分三種情況：

　　l 進程間互不相認：比如多道程序設(shè)計，這些進程間存在共享資源但是彼此不知道，操作系統(tǒng)需要保證進程間的安全。

　　l 進程間簡介知道彼此：進程不知道彼此的ID，但是知道存在共享資源，進程間表現(xiàn)為合作。

　　l 進程間直接知道彼此：進程知道彼此的ID，存在共享資源，進程間表現(xiàn)為合作。

　　并發(fā)性的硬件支持

　　Interrupt disable

　　進程聲明自己的某一段程序是不可被中斷的，這招只在單個處理器的情況下有用，因為多個處理器則存在進程并行運行。

　　Compare & swap instruction

　　由CPU提供的原子指令，用測試值(test value)檢查內(nèi)存單元(_ord)，如果相等就用給定的值設(shè)置內(nèi)存單元(newvalue)，最終返回替換前的內(nèi)存單元值。

　　使用：內(nèi)存單元的初始值是0，多個進程執(zhí)行用0去測試并替換為1的指令，只有獲取到0的返回值的進程獲得了進入臨界區(qū)的資格，在離開臨界區(qū)前進程要重置內(nèi)存單元值為0。

　　Exchange Instruction

　　有CPU提供的原子指令，用內(nèi)存區(qū)域的值和一個寄存器的值交換。也就是只有換到寄存器初始值(換完以后檢查內(nèi)存區(qū)域的值)的那個進程可以進入臨界區(qū)并在離開時重置寄存器。

　　硬件支持存在的弊端：

　　1，采用的是忙等待(busy waiting)的方式，CPU一直在進程間切換，效率低。

　　2，可能發(fā)生饑餓：總有一個二活人品差，搶不到而又沒有任何辦法干預(yù)。

　　3，可能存在死鎖：P1獲得了臨界資源但是同時P1被P2中斷了(P2優(yōu)先級高)，P2卻無法獲得被P1占有的臨界資源，P1同時得不到CPU的計算周期。

　　并發(fā)性的軟件支持

　　信號量(semaphore)

　　用于進程間傳遞信號的一個整數(shù)值。提供了三種操作初始化、信號加和信號減。只有0和1的信號量稱為二元信號量。減操作semwait用于阻塞一個進程(當(dāng)信號量為0的時候阻塞)，加操作semsignal用于激活被阻塞的進程。、

　　生產(chǎn)者與消費者

　　生產(chǎn)者負責(zé)生產(chǎn)資源并加入到指定的緩存中，加入過程如果緩存已滿要阻塞生產(chǎn)者;消費者負責(zé)消費資源，如果緩存已空要避免消費者消費不存在的資源。

　　const int bufferSize = n1;

　　semaphore s = 1, n = 0, e = bufferSize;

　　producer

　　{

　　while(true)

　　{

　　produce();

　　semwait(e);

　　semwait(s);//s信號量用于控制每次只有一個進入critical section

　　append();

　　semsignal(s);

　　semsignal(n);

　　}

　　consumer

　　{

　　while(true)

　　{

　　semwait(n);

　　semwait(s);

　　taken();

　　semsignal(s);

　　semsignal(e);

　　consume();

　　}

　　監(jiān)聽者(管程)

　　信號量的麻煩在于分布在程序的各個地方，一處錯誤就可能導(dǎo)致并發(fā)同步的錯誤。監(jiān)聽者提供了更完善的機制用于并發(fā)同步。參考監(jiān)聽者子圖。

　　監(jiān)聽者包括局部數(shù)據(jù)、條件變量和若干過程和等待隊列等，局部變量是被監(jiān)聽者機制保存的處于外部進程不能訪問或影響局部變量。

　　進程可以通過調(diào)用監(jiān)聽者的某一過程來進入監(jiān)聽者，但是同一時間只有一個進程處于監(jiān)聽者中(其它的在外面排隊，也就是進入隊列)。

　　監(jiān)聽者包含若干個條件變量，可以視條件變量為指向某一等待隊列的指針。

　　監(jiān)聽者提供了cwait和csignal方法，調(diào)用cwait(c)將在條件變量c上阻塞當(dāng)前進程并使監(jiān)聽者可用，當(dāng)前進程加入到條件變量c的等待隊列，調(diào)用csignal(c)將激活條件變量c的等待隊列上的進程并重新嘗試獲得監(jiān)聽者(一般是激活一個，也有可能是signalAll<對于條件變量不明確的情況激活所有的進程，使正確的進程運行其它的進程則因為未獲得條件變量再次阻塞>)。

　　除此監(jiān)聽者還提供了緊急隊列(也可能沒有)，對于進入到過程中的但最后沒有調(diào)用csignal的進程(它可能是在過程中阻塞了或者怎么完蛋了)有兩種處理方式：1，踢出去重新回到進入隊列和大家競爭。2，考慮到這個進程已經(jīng)執(zhí)行了過程的部分邏輯有必要把它加入到緊急隊列中，監(jiān)聽者會在空閑后重新激活緊急隊列中的進程。

　　注意與信號量不同的是，在調(diào)用csignal(c)的時候如果條件變量c的等待隊列上沒有任何進程，那這個動作將不產(chǎn)生任何效果也不會累計下去。

　　生產(chǎn)者/消費者問題中Monitor的實現(xiàn)：

　　monitor

　　{

　　int size, nextin, nextout

　　appand(node)

　　{

　　if(nextin == size) cwait(notFull);

　　buffer[nextin] = node;

　　nextin = (nextin + 1) % size;

　　count++;

　　csignal(notEmpty);

　　}

　　take(char x)

　　{

　　if(count == 0)cwait(notEmpty);

　　x = buffer[nextout];

　　nextout = (next + 1) % size;

　　count--;

　　csignal(notFull);

　　}

　　消息傳遞

　　消息傳遞是進程間通信的另一個手段，其一個優(yōu)點是除了進程間還可以適應(yīng)分布式、共享的系統(tǒng)。消息傳遞最典型的兩個原語：send(source, message)和receive(destination, message)，其中可以是阻塞send、阻塞receive的也可以是不阻塞send阻塞receive的或者兩者都不阻塞。

　　消息的組成包括消息頭和消息體，消息頭包括目的地Id、消息格式、源Id、消息長度等信息，消息體則是消息內(nèi)容。

　　尋址：消息可以是一對一的也可以是一對多、多對一或者多對多。

　　消息的排隊原則：默認情況下消息的接收應(yīng)該是先進先出的對了，除此還要考慮緊急程度的優(yōu)先級設(shè)置。

　　生產(chǎn)者消費者的消息實現(xiàn)：

　　producer

　　{

　　while(true)

　　{

　　receive(mayproduce, pmsg);

　　pmsg = produce();

　　send(mayconsume, pmsg);

　　}

　　consumer

　　{

　　while(true)

　　{

　　receive(mayconsume, pmsg);

　　pmsg = consume();

　　send(mayproduce, pmsg);

　　}

　　main()

　　{

　　create_messagebox(mayconsume);

　　create_messagebox(mayproduce);

　　for(int i = 0; i < N; i++) send(mayproduce, null);

　　parbegin(producer, consumer);

　　}

　　讀者和寫者問題

　　讀者/寫者問題不同于生產(chǎn)者消費者，一個資源可以同時有多個讀者但是同一時間只能有一個寫者。寫者和讀者不能同時獲取資源。

　　可以存在兩種類型的鎖

　　1，讀者優(yōu)先：文件未被占用或存在讀者時可以繼續(xù)加入讀者。

　　2，寫者優(yōu)先：文件被讀者占用后一旦出現(xiàn)寫者后續(xù)不能加入讀者。

　　可以基于信號量或者消息發(fā)送來解決，個人覺得能通過信號量的一定能通過Monitor解決。

　　死鎖和饑餓

　　死鎖：兩個或多個進程間都需要幾個臨界資源，但是各個進程持有其中一個臨界資源而嘗試獲取另外的臨界資源。

　　饑餓：可能是優(yōu)先級或者調(diào)度算法本身的原因?qū)е履硞€進程始終無法獲取到臨界資源(競爭激烈)，雖然不存在死鎖但是這個進程做不了任何事情。

　　聯(lián)合進程圖(Join Process Diagram)

　　資源類型

　　可重用資源：比如I/O設(shè)備、文件等等，它們在同一時間只可以被一個進程使用，但是使用之后并不會因此而銷毀。

　　可消耗資源：比如存在I/O中的一段流數(shù)據(jù)，一旦被使用就不在存在了，但是可以被制造出來。除此以外還有信號、中斷、消息等等。

　　死鎖形成的條件

　　1.互斥

　　2.不存在搶占

　　3.持有和等待

　　4.形成了等待的環(huán)路

　　1~3：有可能產(chǎn)生死鎖但是并沒死鎖。只有4發(fā)生的時候死鎖才是真的產(chǎn)生了。

　　死鎖預(yù)防(protection)

　　死鎖的預(yù)防不同于死鎖避免，死鎖預(yù)防的目的在于干涉死鎖形成的條件1~4使得死鎖無法形成，往往導(dǎo)致的成本很高并且不很實用。

　　1.互斥：無法消除，有并發(fā)就有互斥。

　　2.搶占：這個可以做到有幾種途徑：a，當(dāng)進程資源請求被拒絕時強制其釋放已占有的資源，在后續(xù)需要時可以重新申請。b，當(dāng)進程申請已被其它進程占有的資源時系統(tǒng)允許其搶占。這兩種方法都有一個大前提就是資源狀態(tài)必須是容易保存和恢復(fù)的，否則就啥都沒了。

　　3.持有和等待：可以讓進程一次申請所有需要的資源，這將不會出現(xiàn)持有并等待的情況。但是這是在進程能夠預(yù)測它所使用的所有資源的前提下才成立的，并且效率很低。進程會在沒有用到資源前先占用資源。

　　4.形成環(huán)路：可以將各個資源類型定義成線性順序，只有占有了前面資源的進程才能進一步申請后續(xù)資源——同樣效率是硬傷。

　　死鎖避免(avoidance)

　　死鎖的避免是運行時發(fā)現(xiàn)進程的啟動或者請求會導(dǎo)致死鎖，從而采取不啟動或阻塞的措施。

　　1，如果進程的請求導(dǎo)致死鎖，則不啟動進程。這個比較難做到，因為它要求進程提前預(yù)知自己要用到的所有資源。

　　2，如果進程請求的資源可能導(dǎo)致死鎖，則不分配資源給進程(塞你一會兒)。這個是更可行的辦法。

　　方法2的運算如下：

　　OS中始終維護下列數(shù)據(jù)：

　　1，矩陣C(claim)為各個進程聲明的需要用到資源。

　　2，矩陣A(allocation)現(xiàn)在以分配給各個進程的情況。

　　3，向量R當(dāng)前系統(tǒng)擁有的資源

　　當(dāng)一個進程申請起源是，OS假設(shè)分配資源給它并更下上面的數(shù)據(jù)，之后查看是否會產(chǎn)生死鎖：

　　1，C - A得到矩陣P描述每個進程順利完成時要得到的剩余資源。

　　2，向量R - A中各個資源的合計值等到向量V當(dāng)前可用的資源。

　　3，如果向量V中的資源不足以使P中任何一個進程得到滿足，那么即將發(fā)生死鎖，這時候拒絕進程的請求。

　　4，如果存在可完成的進程，把進程的資源加入到向量V中重復(fù)3步驟直到所有進程可完成或出現(xiàn)死鎖。

　　矩陣C

　　矩陣A

　　矩陣C - A

　　系統(tǒng)資源向量R

　　當(dāng)前可用資源向量V

　　由于當(dāng)前可用資源可以滿足P2，所以可以加回P2的資源并重復(fù)步驟3。

　　死鎖的檢測和恢復(fù)

　　死鎖的檢測其實和上面的步驟是一樣的需要兩個矩陣：Q——進程請求資源(是排除已分配資源后)、A——進程已經(jīng)分配的資源，一個向量V當(dāng)前可用資源。

　　1，標(biāo)記A中所有資源占用都為0的進程行。

　　2，初始化臨時的向量W是它等于V。

　　3，查找Q中為標(biāo)記的i行，其中i行小于向量W。如果找不到i則種植算法。

　　4，如果找到i行，將i標(biāo)記并把A中i行數(shù)據(jù)加回到W中。重復(fù)步驟3。

　　當(dāng)算法結(jié)束時如果存在為標(biāo)記的行則已經(jīng)發(fā)生死鎖。

　　死鎖的恢復(fù)有點野蠻：

　　1，取消所有死鎖的進程。這是現(xiàn)代操作系統(tǒng)最常用的辦法。

　　2，回滾進程到之前一個檢查點(checkpoint)，重新啟動。操作系統(tǒng)需要具備回滾和恢復(fù)的能力，這樣仍然有死鎖的風(fēng)險，但是并發(fā)的不確定性能保證死鎖最終不再發(fā)生。

　　3，連續(xù)取消死鎖進程直到最終不再出現(xiàn)死鎖。取消進程的順序依賴某種成本的原則，取消后重新調(diào)用死鎖檢測，如果仍然存在死鎖繼續(xù)取消。

　　4，連續(xù)搶占資源直到死鎖不再發(fā)生。同樣基于某些成本選擇的方法，資源搶占后重新調(diào)用死鎖檢測，一個被搶占資源的進程需要回滾到獲取該資源前的檢查點。

　　3、4步驟可以考慮一下原則：

　　l 目前消耗處理器時間最少。

　　l 目前為止產(chǎn)生的輸出最少

　　l 預(yù)計剩下的時間最長。

　　l 目前位置分配的資源總量最少。

　　l 優(yōu)先級最低。

　　哲學(xué)家就餐問題

　　一個屋子里有5個哲學(xué)家他們一天中除了睡覺只做思考和吃飯兩件事情，屋子里有一個桌子提供了哲學(xué)家喜歡的意大利粉，但是由于哲學(xué)家每天至思考導(dǎo)致身體退化他們需要用兩個叉子才能夠進食，他們坐下后會先拿起左手的叉子，然后拿起右手的叉子，之后進食吃飽以后放下兩把叉子。桌子周圍一共提供了五把椅子在每個椅子間提供了一把叉子，請為哲學(xué)家設(shè)計吃飯的算法。

　　如果5個哲學(xué)家同時餓了那么每個人都會拿到左手的叉子而死鎖。

　　哲學(xué)家吃飯問題可以通過信號量或者Monitor來處理。

　　內(nèi)存管理

　　內(nèi)存管理的目的：

　　l 重定位

　　l 保護

　　l 共享

　　l 邏輯組織

　　l 物理組織

　　內(nèi)存分區(qū)

　　固定分區(qū)

　　分為大小相等和大小不等的固定分區(qū)策略。內(nèi)存預(yù)先被劃分為固定大小的內(nèi)存區(qū)域，進程可以安裝到大于等于自身的內(nèi)存區(qū)域中。

　　存在內(nèi)部碎片、大于最大內(nèi)存區(qū)域的進程無法加載、內(nèi)存利用不充分。

　　動態(tài)分區(qū)

　　動態(tài)的根據(jù)進程大小進行內(nèi)存區(qū)域劃分，從而使得每個進程可以裝進和自己大小相等的內(nèi)存區(qū)域。

　　存在外部碎片、需要定時壓縮外部碎片否則內(nèi)存被割裂成很多小區(qū)域。

　　伙伴系統(tǒng)

　　采用二分法把內(nèi)存等大小的兩塊區(qū)域(2^1)，再將其中一塊區(qū)域繼續(xù)二分為2^2層，逐次分配下去直到進程所需的大小M在2^(N+1) < M <2^(N)時保存進程。在進程釋放后再進行合并為較大的塊。

　　伙伴系統(tǒng)彌補了固定分區(qū)和動態(tài)分區(qū)的缺點，但是分頁和分段提供了更高級的分區(qū)方式。

　　重定位

　　因為進程換入換出后不一定仍加載到原來的內(nèi)存位置，所以在程序中不可能確切的寫出實際的內(nèi)存地址，而是通過偏移量來描述位置。

　　分頁

　　內(nèi)存被劃分成許多等大小的幀，程序被劃分成與幀大小相等的若干頁。進程加載時需要將所有頁加載到內(nèi)存中不一定連續(xù)的幀中。系統(tǒng)維護了頁表描述程序占用的頁和空閑頁表。

　　分頁沒有外部碎片，由于每個幀很小只有最后一幀是可能存在內(nèi)部碎片的，所以只會出現(xiàn)很小的內(nèi)部碎片。

　　頁的大小將直接影響性能。頁太小時：頁數(shù)多開始時頁面錯誤率很高，一段時間后由于頁面都已加入趨于平穩(wěn)，但是過小的頁將使每次讀寫的區(qū)塊很小。頁增大時：每一頁所包含的單元和相關(guān)單元越來越遠，局部性被削弱錯誤率增加，不斷增大時錯誤率又減小當(dāng)頁大小等于進程P時不再有也錯誤，整個進程都在內(nèi)存中。由此導(dǎo)致的問題是主存中能存入的進程越來越少。

　　頁表

　　操作系統(tǒng)為每個進程維護一個頁表描述進程中頁與幀的對應(yīng)，邏輯地址分為了頁號和偏移量兩部分。一般情況下頁表的大小位頁的大小，頁表中每條記錄稱為頁表實體(PTE，page table entry)。

　　頁表可以是多級頁表，受制于頁大小的限制頁表的大小不能大于一頁(也不可能把巨大的頁表存放在主存中)，因此頁表做多級處理，根頁表始終在主存中，當(dāng)次級頁表不在主存中時從輔存加載對應(yīng)的頁表進主存。

　　根據(jù)頁表尋址

　　l 根據(jù)虛擬地址的頁號查找根頁表對應(yīng)的幀號。

　　l 幀號+次級頁號合成次級頁表的地址找到對應(yīng)的主存中幀號(如果存在的話)。

　　l 幀號+偏移量獲得實地址。

　　l 如果頁表中頁表實體的標(biāo)志位標(biāo)志當(dāng)前頁沒有加載到主存中，發(fā)生頁錯誤中斷交給操作系統(tǒng)加載，進程被中斷處于Block狀態(tài)。

　　反向頁表(Inverter Page Table)

　　這是另一個可行的從虛地址獲取實地址的方案。

　　針對虛擬內(nèi)存中頁表大小和虛擬地址范圍成比例的缺點(太大了)，反向頁表大小是固定的取決于主存中實際幀數(shù)。反響列表對虛擬地址的頁號做Hash運算取得Hash值，每一個Hash值對應(yīng)一個數(shù)據(jù)項。數(shù)據(jù)項中記錄了進程ID和主存中幀號，通過幀號和偏移量就可以得到實地址了。由于多個虛擬地址可能映射到同一個Hash值，反向頁表需要維持鏈結(jié)構(gòu)(當(dāng)前項連接到同值的其它項)，所以進程ID和Hash值共同決定了虛擬地址對應(yīng)的數(shù)據(jù)項。

　　反響的含義是指使用幀號而不是頁號來索引頁表項。

　　轉(zhuǎn)移后備緩沖器(TLB，Translation Lookside Buffer)

　　這是(虛擬內(nèi)存地址轉(zhuǎn)換)硬件設(shè)備的一部分，相當(dāng)于高速緩存。因為正常情況下虛擬地址的訪問要經(jīng)過兩次主存——一次查找?guī)刂?，一次取?shù)據(jù)，轉(zhuǎn)移后備緩沖器緩存了頁號和幀地址的對應(yīng)關(guān)系，只有在未命中的情況下采取訪問頁表查找?guī)枴?/p>

　　分段

　　簡單分段類似于簡單分頁，是將主存換分成大小不等的若干段，一個進程可以存儲在不連續(xù)的段中。分段的大小受限于分段最大長度。分段對程序員是可見的，它具有處理不斷增長的數(shù)據(jù)結(jié)構(gòu)的能力以及支持共享和保護的能力。操作系統(tǒng)為每個進程維護一個段表。

　　分段存在外部碎片。

　　段頁結(jié)合

　　段頁結(jié)構(gòu)是將程序劃分成段，每段保存在主存中對應(yīng)的段里，在主存中段是由等大小的多個頁組成，當(dāng)段最后不足一個頁時占用一個頁。

　　段頁結(jié)合的方式結(jié)合了分段和分頁的長處。在分段系統(tǒng)中由于每段有長度屬性，避免了程序不經(jīng)意的越界訪問。進程間存在共享時多個進程可能持有同一個段的引用，頁結(jié)構(gòu)也可以是實現(xiàn)類似的結(jié)構(gòu)。

　　虛擬內(nèi)存

　　當(dāng)程序太大超過主存時就需要虛擬內(nèi)存了，另外多道程序設(shè)計希望同時有盡可能多的進程加載到內(nèi)存中，由于局部性的原理進程不需要全部加載進內(nèi)存而是加載頻繁是用的區(qū)塊(稱為駐留集)，進程的其它部分保存著專門的輔存區(qū)域中。這個機制稱為虛擬內(nèi)存。

　　系統(tǒng)抖動

　　當(dāng)系統(tǒng)換出一塊內(nèi)存區(qū)域后緊接著它有需要調(diào)用它，當(dāng)這種情況頻繁發(fā)生的時候就導(dǎo)致了系統(tǒng)抖動。

　　讀取策略

　　分為請求式分頁和預(yù)約式分頁。請求式分頁是指當(dāng)確實需要訪問到某頁時才把它加載進主存，預(yù)約式分頁是利用局部性原理將可能訪問到的當(dāng)前請求的后續(xù)頁面加載到主存中。顯然預(yù)約式分頁更可取，但是會造成一定的浪費，在首次加載頁面和發(fā)生頁錯誤時適合采取預(yù)約式分頁。

　　放置策略

　　替換策略

　　替換策略是在加載新的頁時主存已滿需要替換出頁時決定那些頁將被替換的算法。

　　最佳(OPT，Optimal)

　　最少發(fā)生頁錯誤的算法，是優(yōu)先替換那些距離訪問最遠的頁面，需要預(yù)知頁的請求順序，本身是不可能實現(xiàn)的，但是可以作為參考比對其它策略。

　　最近最少使用

　　實際上是性能上最接近最佳的，但是仍難以實現(xiàn)。一種實現(xiàn)方式是給每個頁定義最近訪問的時間標(biāo)簽，并在每次訪問后更新標(biāo)簽，即使通過硬件支持成本和開銷仍然很高。

　　先進先出

　　依賴的理論是一個在很久以前加載的頁現(xiàn)在很可能已經(jīng)不再訪問了，但是結(jié)果往往并非如此，這種策略很容易實現(xiàn)。

　　時鐘

　　環(huán)形的結(jié)構(gòu)，通過指針指示當(dāng)前所在位置，每個頁有一個使用為在訪問后標(biāo)記其值為1。在需要替換時移動指針找到第一個標(biāo)記位等于0的頁，指針每移動過一個頁就將這個頁的使用位清零。這樣如果沒有使用位為0的頁，當(dāng)移動一圈以后最初的位置就會被清理。

　　一個改進是增加修改位——這也是必須的因為被修改的內(nèi)存必然要寫入輔存?，F(xiàn)在有兩個指示位(訪問u，修改m)，算法如下：

　　1，查找u=0,m=0的頁，如果存在替換。這一步不清零訪問位。

　　2，如果1失敗，查找u=0，m=1的頁，并且這個過程中把訪問位清零。

　　3，如果2失敗，重復(fù)1，必要時重復(fù)2。

　　這樣好處是盡量不去替換發(fā)生數(shù)據(jù)修改的頁，少了寫回輔存的動作。

　　頁緩沖

　　也是避免系統(tǒng)抖動的一個策略，在主存中劃分出一定的緩存，用于保存那些被替換出的頁，根據(jù)局部性原理他們很可能近期會被訪問到。這個緩存是一個先入先出的隊列，一般頁面被訪問則直接從緩存中取回，如果一直沒有被訪問則最終會被擠出緩存。

　　駐留集管理(Resident Set)

　　虛擬內(nèi)存中并非一個進程的所有部分都加載到主存中，程序運行過程中常駐內(nèi)存的部分稱為駐留集。

　　駐留集的討論包括兩部分：駐留集分配(大小)和替換范圍。其中駐留集不可變的情況下替換算法已經(jīng)在替換側(cè)路討論過了，駐留集可變的情況下將有所不同。

　　固定分配，局部范圍：每個進程的駐留集大小固定，每個進程一旦有一個頁換進來就要有一個頁換出去。需要根據(jù)程序的類型、優(yōu)先級等預(yù)先分配固定的大小，一旦過小則會保持較高的也錯誤率，如果較大則會占用資源，系統(tǒng)運行緩慢。

　　動態(tài)分配，全局范圍：根據(jù)進程運行的狀態(tài)調(diào)整駐留集的大小，如果頁錯誤率較高就適當(dāng)加大駐留集，如果進程錯誤率一直保持較低水平說明程序的駐留集足夠大，可以適當(dāng)削減一些也不會危及程序。全局范圍則可在所有進程間選擇要被替換出的頁，難點在于沒辦法確定該從哪里換出頁(即很可能換了不該換的)，解決辦法是頁緩沖。

　　動態(tài)分配，局部范圍：動態(tài)分配的效果同上，同時限制在進程自己的范圍內(nèi)換出頁。在這個策略中要求對增加或減少駐留集大小進行評估并且要預(yù)估將來進程的情況，因此比簡單全局替換要復(fù)雜得多，但會提供更好的性能。

　　駐留集的替換策略

　　工作集策略(Working Set)

　　W(t，r)是關(guān)于t和r的函數(shù)，t是單位時間，r是窗口的寬度定義最近的r個單位時間中用到的頁的集合。即始終有W(t, r+1) 包含 W(t, r)。

　　工作集如下工作：

　　1，監(jiān)視每個進程的工作集。

　　2，周期性的從一個進程的駐留集中移除那些不在工作集中的頁，可以使用LRU策略。

　　3，只有當(dāng)一個進程的工作集在主存時才可以執(zhí)行該進程(也就是駐留集包含了工作集)。

　　首先工作集是有效的，它利用率局部性原理，并未該原理設(shè)計了一個可以減少頁錯誤的內(nèi)存管理策略。遺憾的是工作集存在很多問題：

　　1，現(xiàn)在不總是代表未來。

　　2，開銷太大，實現(xiàn)監(jiān)視每個進程不現(xiàn)實。

　　3，r最優(yōu)值未知。

　　但是工作集提供了參考，以下方案都是基于工作集思想的：

　　頁錯誤頻率(Page Fault Frequency，PFF)

　　主存中每個頁都有一個使用位(和時鐘的一樣作用)，操作系統(tǒng)記錄每個進程上一次頁錯誤的時間戳，如果發(fā)生了頁錯誤查看兩次頁錯誤的時間間隔如果小于閾值F，則加入新的頁(擴大駐留集)，否則清除所有使用位為0的頁，并把當(dāng)前駐留集的頁使用位清零(縮小駐留集)。一個改進時加入使用兩個閾值——一個是駐留集增加的最高閾值，一個是駐留集減小的最低閾值(指頻率)。

　　頁面錯誤頻率是工作集的一個折衷，使用頁緩沖則可以達到相當(dāng)好的效率。但是一個缺點是如果要轉(zhuǎn)移到新的局部性，會導(dǎo)致暫時的駐留集猛增。轉(zhuǎn)移到新的局部性是指，進程運行一段時間會切換到不同的邏輯指令部分，這時候局部性發(fā)生偏移，之前的駐留集不再需要。

　　采樣間隔可變工作集(Variable-interval Simple Working Set，VSWS)

　　針對PFF在內(nèi)存高峰是來不及淘汰就得駐留集而導(dǎo)致進程頻繁換入換出等開銷(頻率不夠快)，采用動態(tài)的采樣率以期望盡快淘汰不需要的頁。

　　采用三個參數(shù)：L采樣區(qū)間最長寬度、M采樣區(qū)間最短快讀、Q采樣區(qū)間允許發(fā)生的頁錯誤數(shù)。VSWS和PFF一樣使用了頁的使用位，不同之處在于頻率的調(diào)整：

　　1，如果采樣時間超過了最長時間L，掛起進程并掃描使用位。

　　2，未達到最長時間，但是頁錯誤數(shù)超過了Q：

　　2.1，如果采樣間隔超過了M則掛起進程并掃描使用位。

　　2.2，如果采樣間隔沒有超過M，則一直等待采樣時間到達M進行掃描。

　　清除策略

　　清除策略目的在于確定何時講一個被修改的頁寫回輔存，分為請求式清除和預(yù)約式清除。

　　請求式清除采取動作的時間比較慢，影響性能。

　　預(yù)約式清除把需要修改的頁在需要用到它們的頁幀之前批量的寫回輔存。但是預(yù)約式清除寫回的頁在替換策略確定移除它之前仍有駐留在主存中，這期間可能再次發(fā)生修改導(dǎo)致清除無意義。

　　改進辦法是使用頁緩沖，分為兩個表存儲替換策略淘汰的頁。一個表寸修改的頁，一個表存未修改的頁，修改表中的頁被批量的寫回輔存，然后移動到未修改表中，未修改的表準(zhǔn)備被擠出或者拿回。

　　加載控制

　　加載控制是關(guān)注多道程序設(shè)計的控制，系統(tǒng)中多道程序的數(shù)量稱為多道程序設(shè)計級。當(dāng)多道程序數(shù)量過少時系統(tǒng)會比較空閑，過多時則會導(dǎo)致較高的頁錯誤率和抖動。

　　一個方案稱為L=S，L是頁錯誤間隔的平均時間，S是頁錯誤的平均處理時間，實驗表明當(dāng)兩者接近時處理器使用率達到最大。

　　另一個方案是50%方案，即始終報紙分頁設(shè)備的使用率保持在50%左右，此時的處理器使用率也是最大。

　　另外策略是監(jiān)視時鐘(Clock)替換策略的環(huán)形緩存區(qū)指針移動速度，當(dāng)移動速度低于某個閾值時可能是以下兩種情況之一：

　　1，很少發(fā)生頁錯誤，指針很少移動。

　　2，未被使用的駐留頁太多，指針不需要移動太多就可以找到可清除頁。

　　這兩種情況都表明進程的駐留集分配太大，可以增加多道程序設(shè)計級。另外還可以包括一個高閾值，如果指針移動速度超過這個閾值，則表明多道程序設(shè)計級太高，導(dǎo)致頻繁的頁錯誤，則要掛起進程以減少多道程序設(shè)計級。掛起進程的策略可以是：

　　l 最低優(yōu)先級

　　l 正在發(fā)生頁錯誤的進程(Faulting process)：原因是該進程很肯能駐留集還沒有形成，因此暫停它的代價很低。

　　l 最后被激活的進程：同樣很可能有最小的駐留集。

　　l 擁有最小駐留集的進程：重新裝入的代價最小，但是不利于駐留集較小的程序。

　　l 最大的進程：釋放較大的空間，不用很快又去取活其它的進程。

　　l 具有最大剩余執(zhí)行窗口的進程：類似于最少剩余時間策略，把已運行時間最短的掛起。

　　處理器調(diào)度

　　單處理器調(diào)度

　　調(diào)度類型

　　長程調(diào)度：決定是否將任務(wù)加入到待執(zhí)行的進程池中。

　　中程調(diào)度：決定進程的部分或全部加入到內(nèi)存中(從Suspended到Ready)。

　　短程調(diào)度：決定哪一個就緒的進程將被執(zhí)行。

　　I/O調(diào)度：決定哪一個掛起的I/O請求將被可用的I/O設(shè)備執(zhí)行。

　　處理器調(diào)度關(guān)注的是短程調(diào)度。

　　調(diào)度準(zhǔn)則

　　面向用戶

　　響應(yīng)時間：從任務(wù)提交到開始有響應(yīng)輸出的時間，一般的當(dāng)處理器開始處理任務(wù)時即開始有輸出。

　　周轉(zhuǎn)時間：從任務(wù)提交到任務(wù)完成的時間。

　　最后期限：當(dāng)可以指定最后期限時，操作系統(tǒng)降低其它目標(biāo)，是滿足最后期限的作業(yè)數(shù)目的百分比達到最高。

　　可預(yù)測性：無論系統(tǒng)當(dāng)前負載情況是繁重還是空閑，一個給定工作完成的總時間和總代價應(yīng)該是相等的。

　　面向系統(tǒng)

　　吞吐量：單位時間內(nèi)完成的進程數(shù)。

　　處理器利用率：處理器處于忙狀態(tài)的時間百分比。對于昂貴的共享系統(tǒng)來說這是一個重要的準(zhǔn)則，對于個人系統(tǒng)則顯得不那么重要。

　　公平性：沒有來自用戶或其它系統(tǒng)的指導(dǎo)時操作系統(tǒng)應(yīng)該公平的對待所有進程，沒有一個進程會處于饑餓狀態(tài)。

　　強制優(yōu)先級：當(dāng)指定了優(yōu)先級后調(diào)度策略應(yīng)優(yōu)先響應(yīng)高優(yōu)先級的進程。

　　平衡資源：調(diào)度策略應(yīng)是系統(tǒng)的所有資源保持忙碌的狀態(tài)，較少使用緊缺系統(tǒng)資源的進程應(yīng)該得到照顧。

　　調(diào)度算法

　　歸一化周轉(zhuǎn)時間：它是指進程周轉(zhuǎn)時間與服務(wù)時間的比率，最小值是1.0.該值表示進程的相對延遲，典型的進程的執(zhí)行時間越長可容忍的延遲越長。

　　先來先服務(wù)(FCFS)：沒有優(yōu)先級和搶占，所有進程按照加入的順序執(zhí)行。這樣的調(diào)度偏向于執(zhí)行時間長的進程。FCFS策略本身對操作系統(tǒng)不是很有吸引力，但是它經(jīng)常和優(yōu)先級系統(tǒng)配合使用產(chǎn)生有價值的調(diào)度策略。

　　輪轉(zhuǎn)(Round Robin)：對處理器資源進行時間分片，依次分配相同的時間資源給每個就緒的進程。輪轉(zhuǎn)的時間片最好略大于一次典型交互的時間，當(dāng)時間片足夠大時退化為FCFS策略。

　　輪轉(zhuǎn)增加了處理時鐘中斷、進程切換和分配函數(shù)的開銷，因此時間片不應(yīng)該過短。該策略對短執(zhí)行時間的進程有所改善，但是一個問題是進程分為I/O密集型和處理器密集型，由于I/O密集型進程經(jīng)常被I/O中斷，所以輪轉(zhuǎn)策略傾向于處理器密集型。

　　一個改善的策略是虛擬輪轉(zhuǎn)法(Virtual Round Robin)，它增加了一個I/O隊列，當(dāng)一個進程被I/O阻塞后它加入到I/O隊列，在就緒后它I/O隊列有高于就緒隊列的優(yōu)先級，該進程后續(xù)的執(zhí)行時間與已執(zhí)行時間的和不會超過時間片。

　　最短進程優(yōu)先(SPN，shortest process Next)：具有最短執(zhí)行時間的進程有更高的優(yōu)先級，它依賴于系統(tǒng)估計進程的執(zhí)行時間，在批處理系統(tǒng)中任務(wù)加入時程序員給出任務(wù)的估計時間，如果任務(wù)執(zhí)行時間遠遠超過給出的估計時間它將被廢棄。在生產(chǎn)環(huán)境中有大量的重復(fù)任務(wù)，系統(tǒng)將監(jiān)控每次任務(wù)執(zhí)行的時間以估計執(zhí)行時間，最簡單的公式是s=(各次時間和)/n，一個避免每次求和的優(yōu)化是s=S(n-1) + Tn/n，上述公式每次執(zhí)行的權(quán)值是相同的，典型情況下我們希望最近的執(zhí)行情況有更大的權(quán)值Sn+1 = aTn + (1-a)Sn。

　　最少剩余時間(SRT，shortest remain time)：是SPN的改進版本增加了搶占機制，在不斷有短進程加入的情況下長進程可能處于饑餓狀態(tài)。

　　最高相應(yīng)比優(yōu)先(HRRN，Highest Response Rapid Next)：使用公式(w+s)/s，其中w是等待時間，s是服務(wù)時間。操作系統(tǒng)始終選擇具有最高相應(yīng)比的進程，同樣需要估計和記錄進程的服務(wù)時間。該策略非常具有吸引力，當(dāng)偏向短進程時，長進程由于得不到處理響應(yīng)比不斷增加。

　　反饋：不想SPN、STR、HRRN策略那樣需要估計時間，反饋策略傾向于短進程，它具備多個隊列Q1~Qn，當(dāng)進程加入時處于Q1隊列中，采用FCFS的順序服務(wù)隊列中的每個進程，當(dāng)進程允許超過時間閾值時中斷并加入到下一級隊列中Q2，依次類推。Q1具有最高的優(yōu)先級，只有Q1中不存在進程是才執(zhí)行下一級的隊列。這樣可能導(dǎo)致的問題是過長的隊列可能加入到Qn隊列后處于饑餓狀態(tài)，因此要見識進程的等待時間，如果超過一定長度則重新調(diào)入到Q1中。

　　多處理器調(diào)度

　　多處理器調(diào)度關(guān)注的類型

　　粒度

　　無約束并行性：進程之間沒有顯示的同步，每個進程都是一個單獨的程序。無約束并行可能達到每個用戶都像是使用單獨的計算機或工作站。

　　粗粒度和非常粗粒度并行性：進程之間存在這同步，但是在一個非常粗淺的級別上，這種情況可以簡單的處理成一組運行在多道程序單處理器的并發(fā)進程，在多處理器系統(tǒng)是允許的軟件進行很少或者不進行改動就可以支持。

　　中等粒度并行性：應(yīng)用程序可以被進程中一組線程有效的實現(xiàn)，這種情況下程序員需要顯示的指定潛在的同步性，應(yīng)用程序之間需要高程度的合作與交互。

　　細粒度并行性：代表著比線程間更加復(fù)雜的同步情況，迄今為止仍是特殊的未被分割的領(lǐng)域。

　　進程調(diào)度

　　集中調(diào)度or對等調(diào)度：

　　集中調(diào)度即調(diào)度中存在主處理器，所有的任務(wù)分發(fā)由主處理器來完成，這種情況下主處理器可能成為系統(tǒng)的瓶頸。

　　單處理器使用多道程序設(shè)計：

　　與單處理器性能的不同：

　　多個處理器系統(tǒng)中由于一個長進程在單個處理器上執(zhí)行時，其它的進程可以分配到另外的處理器上因此復(fù)雜的調(diào)度策略不再顯得非常重要，調(diào)度策略的開銷可能成為性能損失。FCFS策略變得可接受。

　　線程調(diào)度

　　負載分配：

　　提供全局隊列，每個處理器只要空閑就從隊列中取任務(wù)執(zhí)行。

　　優(yōu)點是：負載均勻的分配給處理器，不存在空閑的處理器;不需要集中調(diào)度;可以使用單處理的任何一種調(diào)度方案進行分配。

　　缺點是：中心隊列占居了必須互斥訪問的存儲器區(qū)域，因此多處理器同時查找時會成為瓶頸，當(dāng)只有幾十個處理器時不是大問題，但是上百個處理器時就會出現(xiàn)瓶頸。被搶占的線程可能在不同的處理器上執(zhí)行，如果每個處理器都配有高速緩存的話那么命中率將非常低。如果進程的所有線程都視為在公共線程池中那么進程的線程可能不會同時被處理，當(dāng)線程間存在高度合作時則出現(xiàn)瓶頸。

　　組調(diào)度：

　　一組相關(guān)的線程基于一對一的原則，同時分配到一組處理器上去。

　　優(yōu)點：如果緊密相關(guān)的進程并行執(zhí)行那么同步阻塞可能減少，從進程推廣到線程組調(diào)度把一個進程所有的線程視為相關(guān)的;調(diào)度開銷可能減少，因為進程內(nèi)線程間可能相關(guān)如果一個線程在高速允許，而它以來的線程沒有運行就會出現(xiàn)阻塞和調(diào)度。

　　缺點：組調(diào)度同一時間調(diào)度一個進程中相關(guān)線程，某些進程的特性可能至適應(yīng)單線程允許將會出現(xiàn)其它處理器空閑的情況，解決辦法是把若干單線程的進程視為一組允許。

　　專用處理器分配：

　　每個程序執(zhí)行時被分配給一組處理器，處理器個數(shù)與進程的線程數(shù)相等，當(dāng)進程執(zhí)行完后處理器返回到處理器池中等待處理其它任務(wù)。這個策略看似是極端浪費的，它會等到進程運行結(jié)束才將處理器分配給其它的進程使用，而一旦一個線程被I/O阻塞執(zhí)行它的處理器將空閑。

　　采用這個策略的原因：

　　1，高度并行的系統(tǒng)中有數(shù)十或者數(shù)百個處理，每個處理器只占系統(tǒng)總代價的一小部分，處理器利用率不再是衡量有效性或性能的重要因素。

　　2，一個程序的生命周期里避免進程切換會加快程序運行。

　　動態(tài)調(diào)度：

　　執(zhí)行期間進程的線程數(shù)可以改變。某些應(yīng)用程序可能提供了語言和系統(tǒng)工具允許動態(tài)的改變進程中的線程數(shù)目。提供了一種操作系統(tǒng)和應(yīng)用程序共同進行調(diào)度決策的方法。

　　當(dāng)一個作業(yè)請求一個或多個處理器時：

　　1，如果有空閑處理器分配滿足它們需求。

　　2，否則如果作業(yè)新到達，從當(dāng)前已分配多個處理器的作業(yè)中分出一個處理器給它。

　　3，如果都不滿足那么作業(yè)處于未完成狀態(tài)直到有空閑的處理器或者改作業(yè)廢除它的請求。

　　4，當(dāng)釋放一個或多個處理器時為這些處理器掃描當(dāng)前未滿足的請求隊列，給每個沒有分配處理器的作業(yè)分配一個處理器，如果還有空閑處理器再次掃描隊列，按照FCFS原則分配處理器。

　　I/O設(shè)備調(diào)度

　　I/O功能的邏輯結(jié)構(gòu)

　　邏輯I/O：邏輯I/O層將I/O設(shè)備視為邏輯資源，不關(guān)心底層的細節(jié)。邏輯I/O代表用戶進程管理的一般I/O功能，允許它們根據(jù)設(shè)備標(biāo)識符以及諸如打開、關(guān)閉、讀取等操作與設(shè)備打交道。

　　設(shè)備I/O：請求的操作和數(shù)據(jù)(緩沖的數(shù)據(jù)、記錄等)被轉(zhuǎn)換成適當(dāng)?shù)腎/O指令序列、通道命令和控制器指令?？梢允褂镁彺婕夹g(shù)以提高使用率。

　　調(diào)度和控制：關(guān)于I/O操作的排隊、調(diào)度和控制發(fā)生在這一層，可以在這一次處理中斷，收集和報告I/O狀態(tài)。這一層是與I/O設(shè)備真正打交道的軟件層。

　　I/O緩沖

　　I/O設(shè)備劃分：

　　I/O設(shè)備分為面向塊(block oriented和面向流(stream oriented)的設(shè)備，面向塊的設(shè)備將信息保存在塊中，通常是固定大小的，傳輸過程中一次傳送一塊。面向流的設(shè)備以字節(jié)流的方式傳輸數(shù)據(jù)。

　　單緩沖：系統(tǒng)在發(fā)送I/O指令后給I/O設(shè)備分配一塊位于主存中的緩沖區(qū)，傳輸數(shù)據(jù)被放在緩沖區(qū)中，當(dāng)傳輸完成時立即嘗試讀取下一塊。根據(jù)局部性原理有理由期望下一塊被讀取，這種機制稱為超前讀。

　　雙緩沖：單緩沖時I/O設(shè)備必須等待讀取緩沖區(qū)中數(shù)據(jù)被完全讀出才能再次寫入，雙緩沖設(shè)置兩塊緩存區(qū)域以平滑這種趨勢。設(shè)C為進程處理塊的時間，T位讀取塊的時間，我們可以粗略估計塊的執(zhí)行時間位max(C，T)，當(dāng)C>=T是進程將不需要等待I/O，當(dāng)C<T是則I/O設(shè)備可以全速運行。

　　循環(huán)緩沖：當(dāng)爆發(fā)性的執(zhí)行大量的I/O操作時，則僅有雙緩沖就不夠了，這種情況下使用多于兩個緩沖的方案來緩解，這種緩沖區(qū)域自身被當(dāng)成循環(huán)區(qū)域使用。

　　需要指出的是緩存是一種技術(shù)旨在平緩I/O請求峰值的，當(dāng)進程需求的I/O平均值大于I/O傳輸速度是再多的緩沖也不能解決問題。

　　磁盤調(diào)度

　　磁盤性能參數(shù)

　　尋道時間：機械臂移動到數(shù)據(jù)所在軌道的時間，現(xiàn)在典型磁盤的尋道時間Ts=10ms。

　　旋轉(zhuǎn)延遲：磁盤旋轉(zhuǎn)到要讀取的數(shù)據(jù)位置的延遲，一般取平均時間即1/2r，其中r表示轉(zhuǎn)速。

　　傳送時間：磁頭讀取數(shù)據(jù)所花費的時間b/(Nr)，b表示要讀取的字節(jié)數(shù)，N表示磁道上總字節(jié)數(shù)，r表示轉(zhuǎn)速。

　　磁盤調(diào)度策略

　　先進先出

　　先來的請求先服務(wù)，由于數(shù)據(jù)的請求式隨機的，會導(dǎo)致較高的尋址時間，效率差。

　　優(yōu)先級

　　優(yōu)先級是高優(yōu)先級的請求先服務(wù)，一般是為了滿足操作系統(tǒng)的特定目的，并沒有改善磁盤性能的能力。

　　后進先出(LIFO)

　　令人驚訝的是這種選取最近請求的策略有許多優(yōu)點。把設(shè)備資源提供給最近(使用系統(tǒng))的用戶時會導(dǎo)致磁頭臂在一個順序文件中移動時移動的很少，甚至不移動。利用這種局部性原理可以提高吞吐量減少隊列長度，只要一個作業(yè)積極的使用磁盤它就能盡快得到處理。

　　當(dāng)然如果有大量的請求就會導(dǎo)致最先的請求餓死。

　　最短服務(wù)時間優(yōu)先(SSTF)

　　總是選擇磁頭臂移動最少的請求響應(yīng)，對于移動距離相等的請求可以隨機移動向一邊。同樣如果一個進程大量的請求臨近的數(shù)據(jù)會導(dǎo)致其它請求饑餓。

　　SCAN：

　　SCAN要求磁頭臂向一個方向移動，移動過程中響應(yīng)在當(dāng)前磁道的請求。當(dāng)磁頭臂到達最外(內(nèi))層磁道時，再反向掃描。這種算法并沒有很好的利用局部性原理(對最近橫跨過的區(qū)域不公平，不如SSTF和LIFO好)，由于兩側(cè)的數(shù)據(jù)被快速的掃描了兩次因此它偏向于外圍數(shù)據(jù)(局部性原理)。

　　C-SCAN

　　限定在一個方向掃描，當(dāng)達到最后一個磁道時，磁頭臂返回到相反方向的磁道末端重新開始掃描。

　　N-step-SCAN和FSCAN

　　為了克服進程的粘滯性，在SCAN和C-SCAN中一個或多個進程對一個磁道有較高的訪問速度時可能會壟斷這個磁道一段時間。N-step-SCAN設(shè)置若干個N個請求的隊列，每次掃描只響應(yīng)一個隊列里的請求，當(dāng)開始掃描時新的請求需要加入到下一個隊列中。

　　RAID

　　RAID是一組磁盤系統(tǒng)把它們看為一個單個的邏輯驅(qū)動器。

　　數(shù)據(jù)分布在物理驅(qū)動器陣列中

　　使用冗余的磁盤容量保存奇偶檢驗信息，保障一個磁盤失敗時，數(shù)據(jù)具有可恢復(fù)性。

　　磁盤高速緩沖

　　高速緩存是系統(tǒng)從主存中劃分的一塊區(qū)域，利用了局部性原理保存最近訪問的數(shù)據(jù)塊，用于提高更好的磁盤性能。

　　替換算法

　　LRU：最少訪問，將緩沖區(qū)設(shè)置為一個棧，當(dāng)一個塊被訪問后加入到棧中，如果再次得當(dāng)訪問則把該塊從當(dāng)前位置移動到棧頂，隨著塊的加入那些不被訪問的將會擠出棧中。

　　LFU：最小頻率訪問，對緩存中的塊增加計數(shù)特性，每次被訪問到時計數(shù)加1。當(dāng)訪問輔存時，把計數(shù)最小的塊移除，加入最近的塊。由于局部性的問題，一個塊可能短時間內(nèi)多次訪問使得計次很高，但是這之后并不意味著還會再次訪問它，所以LFU并不是一個好的算法。

　　基于頻率的替換算法：克服LFU的確定，在LRU的棧模型中劃分出位于棧頂?shù)娜舾蓭瑸樾聟^(qū)，當(dāng)塊位于新區(qū)是重復(fù)訪問不增加訪問次數(shù)。

　　文件管理

　　文件系統(tǒng)軟件結(jié)構(gòu)

　　基本文件系統(tǒng)：計算機與外部環(huán)境的接口，該層處理磁盤、磁帶的交互數(shù)據(jù)。

　　基本I/O管理程序：負責(zé)所有文件I/O的初始和終止。

　　邏輯I/O：是用戶和應(yīng)用程序能夠訪問到記錄。

　　訪問方法層(堆、順序文件、索引順序文件、索引、散列)：距離用戶和應(yīng)用程序最近的層，在應(yīng)用程序與保存數(shù)據(jù)的設(shè)備之間提供了標(biāo)準(zhǔn)接口。

　　文件結(jié)構(gòu)：

　　域(Field)：基本的數(shù)據(jù)單元，一個域包含一個值，如雇員名字、日期等。

　　記錄(Record)：一組相關(guān)域的集合，可以看做應(yīng)用程序的一個單元。

　　文件(File)：一組相關(guān)記錄的集合，它被用戶或應(yīng)用程序看做一個實體，并可以通過名字訪問。

　　數(shù)據(jù)庫(DB)：一組相關(guān)數(shù)據(jù)的集合，它的本質(zhì)特征是數(shù)據(jù)之間存在著明確的關(guān)系，可供不同的應(yīng)用程序使用。

　　文件組織和訪問

　　堆：

　　最簡單的文件系統(tǒng)。數(shù)據(jù)按它們到達的順序被組織，通過特定的分隔符或特定的域指明。每個域應(yīng)該是自描述的，數(shù)據(jù)之間不一定存在聯(lián)系或相同的格式。

　　當(dāng)數(shù)據(jù)在處理器采集并存儲時或者當(dāng)數(shù)據(jù)難以存儲時會用到堆。只能窮舉搜索，對大多數(shù)應(yīng)用都不適用。

　　順序文件：

　　文件具有固定的格式，所有的記錄都有相同的格式，具有相同數(shù)目、長度固定的域按照順序組成。每條記錄第一個域稱為關(guān)鍵域，唯一標(biāo)識了這條記錄。

　　交互的表現(xiàn)較差，需要順序的搜索。一種情況下順序文件按照順序存儲在磁盤上，在發(fā)生文件修改時需要移動數(shù)據(jù)，可能的處理方式是把數(shù)據(jù)存在臨時堆上，定期的將數(shù)據(jù)批量寫回順序文件。另一種情況文件可能采用鏈?zhǔn)酱鎯?，該方法帶來一些方便，但是是以額外的處理和開銷為代價的。

　　索引順序文件

　　彌補了順序文件檢索的問題。檢索文件可以是簡單的順序文件，每條記錄包括兩個值一個關(guān)鍵域和指向文件的指針。簡單的檢索可以是一級的，也可以由多級檢索。查找文件時找到相等的域或者關(guān)鍵域值之前最大的域。

　　索引文件

　　順序文件和索引順序文件只能是順序檢索或?qū)﹃P(guān)鍵域檢索，索引文件對感興趣的域提供了索引，索引文件本身可以是順序的。索引文件分為完全索引和部分索引，差別在于被索引的域是全部域還僅僅是感興趣的域。

　　索引文件一般只提供索引訪問的方式，不再支持順序訪問，因此記錄的組織也不必是順序的，應(yīng)用程序只能通過指針訪問。

　　直接文件或散列文件

　　直接文件或散列文件開發(fā)直接訪問磁盤中任何一個地址一致的塊的能力，要求每條記錄中都有一個關(guān)鍵域，但這里不存在順序的概念。

　　記錄組塊

　　磁盤中數(shù)據(jù)保存在塊中，塊越大每次傳輸?shù)臄?shù)據(jù)越多，效率越高。當(dāng)時大的塊要求操作系統(tǒng)提供更大或者復(fù)雜的緩存，并且由于局部性的關(guān)系大塊中的數(shù)據(jù)可能是應(yīng)用程序不需要的造成浪費。

　　固定組塊

　　使用固定長度的記錄，并且若干條完整記錄保存到一個塊中，每個塊末尾可能有未使用的空間稱為內(nèi)部碎片。

　　可變長度跨越式組塊

　　塊的長度可變，記錄可以跨越塊保存，如果一個塊的末尾空間不足一條記錄時，剩下的數(shù)據(jù)可以保存在下一個塊中，通過后繼指針指明。造成了更復(fù)雜的處理，并且當(dāng)讀取跨越塊的數(shù)據(jù)時需要讀取兩次，消除了內(nèi)部碎片。

　　可變長度非跨越式組塊

　　和上面相同，但是記錄不可以跨越塊保存。

　　二級存儲管理

　　文件分配

　　預(yù)分配：文件請求時聲明需要的空間，一次性分配。

　　動態(tài)分配：根據(jù)文件的增長每次分配一定的空間，或者一塊。

　　分配方法：

　　連續(xù)分配：始終給文件分配連續(xù)的空間。這種分配方式對于順序文件非常高效，并且可以簡單的檢索到需要的文件塊。但是會產(chǎn)生外部碎片，并且需要實時運行壓縮程序以消除外部碎片。

　　鏈?zhǔn)椒峙洌何募恍枰樞虮４?，每塊尾部通過指針指向下一塊數(shù)據(jù)，文件分配表中同樣只要保存一個表項。

　　鏈?zhǔn)椒峙涞囊粋€后果是局部性不再被利用，如果要順序的讀取一個文件時需要一連串訪問磁盤的不同部分，這對系統(tǒng)的影響很嚴(yán)重。一些系統(tǒng)周期性的的對文件進行合并。

　　索引分配：每個文件在文件分配表中有一個一級索引，分配給文件的每個分區(qū)在索引中都有一個表項，典型的文件索引在物理上并不保存在文件分配表上，而是保存在獨立的一個塊上，文件分配表中該文件索引指向這個塊。

　　可以消除外部碎片，按大小可變的分區(qū)分配可以提高局部性，任何情況下(大小可變分區(qū)、按塊保存)都需要不時的對文件進行合并。使用大小可變的分區(qū)情況下合并可以減少文件索引。索引分配支持順序和直接讀取數(shù)據(jù)，是最普遍的一種文件分配形式。

　　空閑空間管理

　　位表：使用一個向量，向量的每一位代表一塊磁盤，0表示空閑，1表示使用。優(yōu)點是容易找到一塊或一組連續(xù)的空間，問題是需要窮舉來找到合適大小的區(qū)域，當(dāng)磁盤剩余很少空間時這個問題尤為嚴(yán)重，因此需要設(shè)置特殊的數(shù)據(jù)結(jié)構(gòu)輔助查找。如位表可以在邏輯上劃分為不同的區(qū)域，建立區(qū)域匯總表統(tǒng)計每個區(qū)域的使用情況，查找空閑位時可以先找到合適的區(qū)域在查找位表中這部分區(qū)域的使用情況。

　　位表需要加載在主存中，一個位表所需要的存儲總量為【(磁盤大小)/(8_件系統(tǒng)塊大小)】(計算的是占用的字節(jié)數(shù))，因此一個16GB的磁盤，塊大小位512字節(jié)時位表占用4MB，如果每次去數(shù)據(jù)都從硬盤加載4MB的位表的話這個速度是難以忍受的。

　　鏈?zhǔn)娇臻e區(qū)

　　空閑表可以使用指向每個空閑區(qū)的指針和他們的長度值被連接在一起，因為空閑表只需要一個指向第一個空閑區(qū)的指針，因此這種情況下空閑表的大小是可以忽略的。

　　這種分配法適合所有的文件分配方法，如果按塊分配可以移動位于頭部的指針，如果是按區(qū)域分配則可以順序的找到合適的區(qū)域并更新指針。

　　存在的問題：1，使用一段時間磁盤會出現(xiàn)很多碎片，許多區(qū)變成只有一塊大小。2，寫時需要先讀取該塊以發(fā)現(xiàn)下一塊的指針，如果進程請求大量的單個塊這個效率是很差的，同意刪除的時候也會導(dǎo)致很慢。

　　索引

　　索引是把空閑空間看做文件，使用之前介紹的索引表的方式記錄?；谛实脑?，索引適合使用在大小可變的分區(qū)分配的情況下。

　　空閑塊列表

　　每個空閑塊都有一個順序號，把順序號保存在磁盤的一個保留區(qū)中。根據(jù)磁盤的大小，存儲一個塊號需要24位或32位。這是一種令人滿意的方法，空閑塊列表部分保存在主存里：

　　1，磁盤空閑塊列表占用空間小于磁盤空間的1%。

　　2，盡管空閑塊太大了，不能保存在主存。但是兩種有效技術(shù)把該表的一小部分保存在主存里：

　　a，這個表可以是一個下推棧，棧中靠前的數(shù)千元素保存在內(nèi)存中，當(dāng)分配一個新塊時它從棧頂彈出，同樣當(dāng)一個塊被接觸時把它壓入棧中。只有棧中部分滿了或者空了時候才需要從磁盤傳輸數(shù)據(jù)，通常情況下它是零訪問時間的。

　　b，這個表可以看所FIFO的隊列，分配時從頭部取走，取消分配時從隊尾入隊，只有隊空了或者滿了時才需要與磁盤傳輸。

看了“操作系統(tǒng)總結(jié)知識”還想看：

1.操作系統(tǒng)主要知識點

2.操作系統(tǒng)知識大全

3.操作系統(tǒng)基本知識操作系統(tǒng)知識點

4.linux操作系統(tǒng)基礎(chǔ)知識總結(jié)

5.系統(tǒng)與設(shè)計知識點歸納

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

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

相關(guān)文章

熱門文章