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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　OS的主要功能：

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

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

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

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

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

　　第二章進(jìn)程管理

　　進(jìn)程與線程的基本概念

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

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

　　進(jìn)程和線程的區(qū)別

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

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

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

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

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

　　進(jìn)程的特征：

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

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

　　3) 并發(fā)性;

　　4) 獨(dú)立性;因?yàn)橛蠵CB，可以獨(dú)立運(yùn)行、獨(dú)立分配資源、獨(dú)立接受調(diào)度等功能

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

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

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

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

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

　　信號(hào)量機(jī)制是一種卓有成效的進(jìn)程同步工具。包括整形信號(hào)量、記錄型信號(hào)量、AND型信號(hào)量、信號(hào)量集。

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

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

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

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

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

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

　　死鎖：多個(gè)進(jìn)程在運(yùn)行過程中因爭(zhēng)奪資源而造成的一種僵局。

　　活鎖：多個(gè)進(jìn)程在運(yùn)行工程中因相互謙讓而造成的一種僵局。

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

　　1) 競(jìng)爭(zhēng)資源

　　2) 進(jìn)程間推進(jìn)順序非法

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

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

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

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

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

　　處理死鎖的基本方法

　　1) 預(yù)防死鎖

　　2) 避免死鎖

　　3) 檢測(cè)和解除死鎖

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

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

　　死鎖的解除

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

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

　　第四章存儲(chǔ)器管理

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

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

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

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

　　4) 動(dòng)態(tài)重定位分區(qū)分配：通過重定位寄存器把相對(duì)地址轉(zhuǎn)化成物理地址，此轉(zhuǎn)化過程是在程序執(zhí)行期間，隨著每條指令或數(shù)據(jù)的訪問自動(dòng)進(jìn)行的，故稱為動(dòng)態(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)算法(對(duì)空閑分區(qū)進(jìn)行分類，并建立索引表，選最適合的控件分配給請(qǐng)求的進(jìn)程)

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

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

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

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

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

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

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

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

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

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

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

　　第五章設(shè)備管理

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

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

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

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

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

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

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

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

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

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

　　設(shè)備控制器

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

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

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

　　1) 接受和識(shí)別命令

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

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

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

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

　　6) 差錯(cuò)控制

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

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

　　I/O控制方式

　　1) 程序I/O方式

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

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

　　4) I/O通道控制方式

　　SPOOLing技術(shù)

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

　　Spooling系統(tǒng)的組成

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

　　SPOOLing系統(tǒng)的特點(diǎn)

　　1) 提高了I/O的速度

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

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

　　磁盤調(diào)度

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

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

　　1) 先來先服務(wù)(適合進(jìn)程較少的場(chǎng)合)

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

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

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

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

　　第六章文件管理

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

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

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

　　記錄式文件的長(zhǎng)度分為定長(zhǎng)記錄和變長(zhǎng)記錄。

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

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

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

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

　　1) 適合進(jìn)行批量存取

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

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

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

　　5) 增加或刪除一個(gè)記錄時(shí)比較困難

　　索引文件的缺點(diǎn)：除了有主文件外，還須配置一張索引表，而且每個(gè)記錄都要有一個(gè)索引表，因此提高了存儲(chǔ)費(fèi)用。

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

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

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

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

　　1) 順序訪問容易

　　2) 順序訪問速度快

　　缺點(diǎn)：

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

　　2) 必須實(shí)現(xiàn)知道文件的長(zhǎng)度

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

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

　　文件存儲(chǔ)空間管理的方法

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

　　2) 位示圖法

　　3) 成組鏈接法

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

　　常見面試題：

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

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

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

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

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

　　6，P.V操作是一種低級(jí)進(jìn)程通信原語

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　2.存儲(chǔ)管理。存儲(chǔ)管理的主要工作是對(duì)內(nèi)部存儲(chǔ)器進(jìn)行分配、保護(hù)和擴(kuò)充和管理。

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

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

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

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

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

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

　　(3) 進(jìn)程調(diào)度

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

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

　　(1)進(jìn)程是一個(gè)動(dòng)態(tài)概念，而程序是一個(gè)靜態(tài)概念。

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

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

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

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

　　(1)進(jìn)程的虛擬空間被劃分成長(zhǎng)度相等的頁。

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

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

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

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

　　(2)選擇占有處理機(jī)的進(jìn)程

　　(3)進(jìn)行進(jìn)程上下文切換

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

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

　　(2)分時(shí)操作系統(tǒng)的特點(diǎn)：多路性、獨(dú)立性、及時(shí)性、交互性。

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

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

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

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

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

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

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

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

　　解析：

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

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

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

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

　　13、中斷和輪詢的特點(diǎn)

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

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

　　輪詢——效率低，等待時(shí)間很長(zhǎng)，CPU利用率不高。

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

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

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

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

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

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

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

　　15、說說分段和分頁

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

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

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

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

　　16、說出你所知道的保持進(jìn)程同步的方法?

　　進(jìn)程間同步的主要方法有原子操作、信號(hào)量機(jī)制、自旋鎖、管程、會(huì)合、分布式系統(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--那個(gè)是權(quán)限符號(hào)，總共是- --- --- ---這幾個(gè)位。

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

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

　　一個(gè)文件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、簡(jiǎn)術(shù)OSI的物理層Layer1，鏈路層Layer2，網(wǎng)絡(luò)層Layer3的任務(wù)。

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

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

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

　　20、什么是中斷?中斷時(shí)CPU做什么工作?

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

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

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

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

　　每個(gè)線程有自己的堆棧。

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

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

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

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

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

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

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

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

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

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

　　(2) 進(jìn)程推進(jìn)順序非法。

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

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

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

　　(3)占有并等待(hold andwait)，一個(gè)進(jìn)程因請(qǐng)求資源而阻塞時(shí)，對(duì)已獲得的資源保持不放;

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

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

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

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

　　附錄：

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

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

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

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

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

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

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

　　答案：C

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

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

　　5、中斷和輪詢的特點(diǎn)

　　輪詢——效率低，等待時(shí)間很長(zhǎng)，CPU利用率不高。

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

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

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

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

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

　　7、說說分段和分頁

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

　　8、說出你所知道的保持進(jìn)程同步的方法?

　　進(jìn)程間同步的主要方法有原子操作、信號(hào)量機(jī)制、自旋鎖、管程、會(huì)合、分布式系統(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--那個(gè)是權(quán)限符號(hào)，總共是- --- --- ---這幾個(gè)位。

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

　　一個(gè)文件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文件的作用是什么?

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

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

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

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

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

　　13、什么是中斷?中斷時(shí)CPU做什么工作?

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

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

　　每個(gè)線程有自己的堆棧。

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

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

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

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

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

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

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

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

　　(3)占有并等待(hold andwait)，一個(gè)進(jìn)程因請(qǐng)求資源而阻塞時(shí)，對(duì)已獲得的資源保持不放;

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

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

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

　　1、程序和進(jìn)程

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

定義

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

程序

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

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

進(jìn)程

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

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

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

　　2、進(jìn)程與線程

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

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

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

　　進(jìn)程與線程的比較如下：

比較

進(jìn)程

線程

活潑性

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

活潑

地址空間

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

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

調(diào)度

僅是資源分配的基本單位

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

并發(fā)性

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

進(jìn)程間、線程間并發(fā)

擁有資源

資源擁有的基本單位

基本上不擁有資源

系統(tǒng)開銷

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

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

　　3、進(jìn)程同步

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

　　同步機(jī)制遵循的原則：

　　(1)空閑讓進(jìn);

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

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

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

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

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

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

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

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

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

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

同一機(jī)器兩個(gè)進(jìn)程間通信

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

剪貼板Clipboard

可以

不可以

匿名管道Pipe

可以

不可以

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

可以

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

可以

　　5、線程同步

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

內(nèi)核對(duì)象/

非內(nèi)核對(duì)象

含義

缺點(diǎn)

適用

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

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

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

1.因?yàn)樵诘却M(jìn)入關(guān)鍵代碼段時(shí)無法設(shè)定超時(shí)值，所以其很容易進(jìn)入死鎖狀態(tài)。2.不能跨進(jìn)程使用。

單個(gè)進(jìn)程中線程間的同步（同步速度快）

事件對(duì)象Event

內(nèi)核對(duì)象

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

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

多個(gè)進(jìn)程間的各個(gè)線程間實(shí)現(xiàn)同步

互斥對(duì)象Mutex

內(nèi)核對(duì)象

代表對(duì)一個(gè)資源的獨(dú)占式訪問

信號(hào)量

Semaphore

內(nèi)核對(duì)象

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

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

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

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

　　【FAT】：

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

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

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

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

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

　　【NTFS】：

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

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

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

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

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

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

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

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

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

　　【Ext2】：

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

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

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

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

　　【Ext3】：

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

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

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

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

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

　　【Ext4】：

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

　　1、與 Ext3 兼容。執(zhí)行若干條命令，就能從 Ext3 在線遷移到 Ext4，而無須重新格式化磁盤或重新安裝系統(tǒng)。原有 Ext3 數(shù)據(jù)結(jié)構(gòu)照樣保留，Ext4 作用于新數(shù)據(jù)，當(dāng)然，整個(gè)文件系統(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 個(gè)子目錄，而 Ext4 支持無限數(shù)量的子目錄。

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

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

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

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

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

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

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

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

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

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

　　【ZFS】：

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

　　【HFS】：

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

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

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

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

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

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

　　3、構(gòu)成方式

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

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

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

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

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

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

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

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

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

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

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

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

　　計(jì)算機(jī)組成

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

　　硬件層

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

　　CPU：

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

　　總線：

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

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

　　速度：

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

　　局部性：

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

　　指令周期(取指周期)：

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

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

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

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

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

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

　　操作系統(tǒng)

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

　　操作系統(tǒng)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　Process table：管理進(jìn)程。

　　進(jìn)程和線程

　　進(jìn)程

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

　　進(jìn)程的組成：

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

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

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

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

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

　　進(jìn)程狀態(tài)切換

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

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

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

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

　　進(jìn)程切換(Swapping)：

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

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

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

　　進(jìn)程執(zhí)行模式：

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

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

　　多線程定義

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

　　與進(jìn)程的關(guān)系

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

　　創(chuàng)建方式

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

　　線程優(yōu)勢(shì)

　　l 創(chuàng)建時(shí)間開銷遠(yuǎn)小于進(jìn)程的創(chuàng)建。因?yàn)椴恍枰峙溆脩艨臻g和那么多初始化動(dòng)作。

　　l 銷毀線程的成本也遠(yuǎn)低于進(jìn)程。

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

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

　　線程同步

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

　　線程類型

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

用戶級(jí)

內(nèi)核級(jí)

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

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

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

在線程切換時(shí)需要模式切換（因?yàn)槭钦{(diào)用系統(tǒng)級(jí)的指令）

進(jìn)程中同時(shí)只能有一個(gè)線程在運(yùn)行，還是多段程序的思路

線程可以并發(fā)運(yùn)行，特別指多核計(jì)算機(jī)

一旦被阻塞整個(gè)進(jìn)程就被阻塞，也就是所有的線程都完蛋了

只會(huì)阻塞引起阻塞的線程

　　線程的四個(gè)應(yīng)用場(chǎng)景

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

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

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

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

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

　　并發(fā)性

　　競(jìng)爭(zhēng)條件

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

　　臨界區(qū)

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

　　互斥(multual exclusion)

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

　　互斥的要求：

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

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

　　l 請(qǐng)求臨界資源的進(jìn)程不能被無限期的延遲，即不能有死鎖。

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

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

　　l 一個(gè)進(jìn)程在臨界區(qū)的時(shí)間應(yīng)該是有限的。

　　進(jìn)程交互

　　進(jìn)程交互分三種情況：

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

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

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

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

　　Interrupt disable

　　進(jìn)程聲明自己的某一段程序是不可被中斷的，這招只在單個(gè)處理器的情況下有用，因?yàn)槎鄠€(gè)處理器則存在進(jìn)程并行運(yùn)行。

　　Compare & swap instruction

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

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

　　Exchange Instruction

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

　　硬件支持存在的弊端：

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

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

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

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

　　信號(hào)量(semaphore)

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

　　生產(chǎn)者與消費(fèi)者

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

　　const int bufferSize = n1;

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

　　producer

　　{

　　while(true)

　　{

　　produce();

　　semwait(e);

　　semwait(s);//s信號(hào)量用于控制每次只有一個(gè)進(jìn)入critical section

　　append();

　　semsignal(s);

　　semsignal(n);

　　}

　　consumer

　　{

　　while(true)

　　{

　　semwait(n);

　　semwait(s);

　　taken();

　　semsignal(s);

　　semsignal(e);

　　consume();

　　}

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

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

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

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

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

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

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

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

　　生產(chǎn)者/消費(fèi)者問題中Monitor的實(shí)現(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);

　　}

　　消息傳遞

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

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

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

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

　　生產(chǎn)者消費(fèi)者的消息實(shí)現(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)者消費(fèi)者，一個(gè)資源可以同時(shí)有多個(gè)讀者但是同一時(shí)間只能有一個(gè)寫者。寫者和讀者不能同時(shí)獲取資源。

　　可以存在兩種類型的鎖

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

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

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

　　死鎖和饑餓

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

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

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

　　資源類型

　　可重用資源：比如I/O設(shè)備、文件等等，它們?cè)谕粫r(shí)間只可以被一個(gè)進(jìn)程使用，但是使用之后并不會(huì)因此而銷毀。

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

　　死鎖形成的條件

　　1.互斥

　　2.不存在搶占

　　3.持有和等待

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

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

　　死鎖預(yù)防(protection)

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

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

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

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

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

　　死鎖避免(avoidance)

　　死鎖的避免是運(yùn)行時(shí)發(fā)現(xiàn)進(jìn)程的啟動(dòng)或者請(qǐng)求會(huì)導(dǎo)致死鎖，從而采取不啟動(dòng)或阻塞的措施。

　　1，如果進(jìn)程的請(qǐng)求導(dǎo)致死鎖，則不啟動(dòng)進(jìn)程。這個(gè)比較難做到，因?yàn)樗筮M(jìn)程提前預(yù)知自己要用到的所有資源。

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

　　方法2的運(yùn)算如下：

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

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

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

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

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

　　1，C - A得到矩陣P描述每個(gè)進(jìn)程順利完成時(shí)要得到的剩余資源。

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

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

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

　　矩陣C

　　矩陣A

　　矩陣C - A

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

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

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

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

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

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

　　2，初始化臨時(shí)的向量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é)束時(shí)如果存在為標(biāo)記的行則已經(jīng)發(fā)生死鎖。

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

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

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

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

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

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

　　l 目前消耗處理器時(shí)間最少。

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

　　l 預(yù)計(jì)剩下的時(shí)間最長(zhǎng)。

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

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

　　哲學(xué)家就餐問題

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

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

　　哲學(xué)家吃飯問題可以通過信號(hào)量或者M(jìn)onitor來處理。

　　內(nèi)存管理

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

　　l 重定位

　　l 保護(hù)

　　l 共享

　　l 邏輯組織

　　l 物理組織

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

　　固定分區(qū)

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

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

　　動(dòng)態(tài)分區(qū)

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

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

　　伙伴系統(tǒng)

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

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

　　重定位

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

　　分頁

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

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

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

　　頁表

　　操作系統(tǒng)為每個(gè)進(jìn)程維護(hù)一個(gè)頁表描述進(jìn)程中頁與幀的對(duì)應(yīng)，邏輯地址分為了頁號(hào)和偏移量?jī)刹糠?。一般情況下頁表的大小位頁的大小，頁表中每條記錄稱為頁表實(shí)體(PTE，page table entry)。

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

　　根據(jù)頁表尋址

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

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

　　l 幀號(hào)+偏移量獲得實(shí)地址。

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

　　反向頁表(Inverter Page Table)

　　這是另一個(gè)可行的從虛地址獲取實(shí)地址的方案。

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

　　反響的含義是指使用幀號(hào)而不是頁號(hào)來索引頁表項(xiàng)。

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

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

　　分段

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

　　分段存在外部碎片。

　　段頁結(jié)合

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

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

　　虛擬內(nèi)存

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

　　系統(tǒng)抖動(dòng)

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

　　讀取策略

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

　　放置策略

　　替換策略

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

　　最佳(OPT，Optimal)

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

　　最近最少使用

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

　　先進(jìn)先出

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

　　時(shí)鐘

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

　　一個(gè)改進(jìn)是增加修改位——這也是必須的因?yàn)楸恍薷牡膬?nèi)存必然要寫入輔存。現(xiàn)在有兩個(gè)指示位(訪問u，修改m)，算法如下：

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

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

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

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

　　頁緩沖

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

　　駐留集管理(Resident Set)

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

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

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

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

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

　　駐留集的替換策略

　　工作集策略(Working Set)

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

　　工作集如下工作：

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

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

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

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

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

　　2，開銷太大，實(shí)現(xiàn)監(jiān)視每個(gè)進(jìn)程不現(xiàn)實(shí)。

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

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

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

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

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

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

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

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

　　1，如果采樣時(shí)間超過了最長(zhǎng)時(shí)間L，掛起進(jìn)程并掃描使用位。

　　2，未達(dá)到最長(zhǎng)時(shí)間，但是頁錯(cuò)誤數(shù)超過了Q：

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

　　2.2，如果采樣間隔沒有超過M，則一直等待采樣時(shí)間到達(dá)M進(jìn)行掃描。

　　清除策略

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

　　請(qǐng)求式清除采取動(dòng)作的時(shí)間比較慢，影響性能。

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

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

　　加載控制

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

　　一個(gè)方案稱為L(zhǎng)=S，L是頁錯(cuò)誤間隔的平均時(shí)間，S是頁錯(cuò)誤的平均處理時(shí)間，實(shí)驗(yàn)表明當(dāng)兩者接近時(shí)處理器使用率達(dá)到最大。

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

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

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

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

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

　　l 最低優(yōu)先級(jí)

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

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

　　l 擁有最小駐留集的進(jìn)程：重新裝入的代價(jià)最小，但是不利于駐留集較小的程序。

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

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

　　處理器調(diào)度

　　單處理器調(diào)度

　　調(diào)度類型

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

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

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

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

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

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

　　面向用戶

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

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

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

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

　　面向系統(tǒng)

　　吞吐量：?jiǎn)挝粫r(shí)間內(nèi)完成的進(jìn)程數(shù)。

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

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

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

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

　　調(diào)度算法

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

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

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

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

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

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

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

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

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

　　多處理器調(diào)度

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

　　粒度

　　無約束并行性：進(jìn)程之間沒有顯示的同步，每個(gè)進(jìn)程都是一個(gè)單獨(dú)的程序。無約束并行可能達(dá)到每個(gè)用戶都像是使用單獨(dú)的計(jì)算機(jī)或工作站。

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

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

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

　　進(jìn)程調(diào)度

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

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

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

　　與單處理器性能的不同：

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

　　線程調(diào)度

　　負(fù)載分配：

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

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

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

　　組調(diào)度：

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

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

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

　　專用處理器分配：

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

　　采用這個(gè)策略的原因：

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

　　2，一個(gè)程序的生命周期里避免進(jìn)程切換會(huì)加快程序運(yùn)行。

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

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

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

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

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

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

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

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

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

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

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

　　調(diào)度和控制：關(guān)于I/O操作的排隊(duì)、調(diào)度和控制發(fā)生在這一層，可以在這一次處理中斷，收集和報(bào)告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)傳輸完成時(shí)立即嘗試讀取下一塊。根據(jù)局部性原理有理由期望下一塊被讀取，這種機(jī)制稱為超前讀。

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

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

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

　　磁盤調(diào)度

　　磁盤性能參數(shù)

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

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

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

　　磁盤調(diào)度策略

　　先進(jìn)先出

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

　　優(yōu)先級(jí)

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

　　后進(jìn)先出(LIFO)

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

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

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

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

　　SCAN：

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

　　C-SCAN

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

　　N-step-SCAN和FSCAN

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

　　RAID

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

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

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

　　磁盤高速緩沖

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

　　替換算法

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

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

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

　　文件管理

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

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

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

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

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

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

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

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

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

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

　　文件組織和訪問

　　堆：

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

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

　　順序文件：

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

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

　　索引順序文件

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

　　索引文件

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

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

　　直接文件或散列文件

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

　　記錄組塊

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

　　固定組塊

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

　　可變長(zhǎng)度跨越式組塊

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

　　可變長(zhǎng)度非跨越式組塊

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

　　二級(jí)存儲(chǔ)管理

　　文件分配

　　預(yù)分配：文件請(qǐng)求時(shí)聲明需要的空間，一次性分配。

　　動(dòng)態(tài)分配：根據(jù)文件的增長(zhǎng)每次分配一定的空間，或者一塊。

　　分配方法：

　　連續(xù)分配：始終給文件分配連續(xù)的空間。這種分配方式對(duì)于順序文件非常高效，并且可以簡(jiǎn)單的檢索到需要的文件塊。但是會(huì)產(chǎn)生外部碎片，并且需要實(shí)時(shí)運(yùn)行壓縮程序以消除外部碎片。

　　鏈?zhǔn)椒峙洌何募恍枰樞虮４?，每塊尾部通過指針指向下一塊數(shù)據(jù)，文件分配表中同樣只要保存一個(gè)表項(xiàng)。

　　鏈?zhǔn)椒峙涞囊粋€(gè)后果是局部性不再被利用，如果要順序的讀取一個(gè)文件時(shí)需要一連串訪問磁盤的不同部分，這對(duì)系統(tǒng)的影響很嚴(yán)重。一些系統(tǒng)周期性的的對(duì)文件進(jìn)行合并。

　　索引分配：每個(gè)文件在文件分配表中有一個(gè)一級(jí)索引，分配給文件的每個(gè)分區(qū)在索引中都有一個(gè)表項(xiàng)，典型的文件索引在物理上并不保存在文件分配表上，而是保存在獨(dú)立的一個(gè)塊上，文件分配表中該文件索引指向這個(gè)塊。

　　可以消除外部碎片，按大小可變的分區(qū)分配可以提高局部性，任何情況下(大小可變分區(qū)、按塊保存)都需要不時(shí)的對(duì)文件進(jìn)行合并。使用大小可變的分區(qū)情況下合并可以減少文件索引。索引分配支持順序和直接讀取數(shù)據(jù)，是最普遍的一種文件分配形式。

　　空閑空間管理

　　位表：使用一個(gè)向量，向量的每一位代表一塊磁盤，0表示空閑，1表示使用。優(yōu)點(diǎn)是容易找到一塊或一組連續(xù)的空間，問題是需要窮舉來找到合適大小的區(qū)域，當(dāng)磁盤剩余很少空間時(shí)這個(gè)問題尤為嚴(yán)重，因此需要設(shè)置特殊的數(shù)據(jù)結(jié)構(gòu)輔助查找。如位表可以在邏輯上劃分為不同的區(qū)域，建立區(qū)域匯總表統(tǒng)計(jì)每個(gè)區(qū)域的使用情況，查找空閑位時(shí)可以先找到合適的區(qū)域在查找位表中這部分區(qū)域的使用情況。

　　位表需要加載在主存中，一個(gè)位表所需要的存儲(chǔ)總量為【(磁盤大小)/(8_件系統(tǒng)塊大小)】(計(jì)算的是占用的字節(jié)數(shù))，因此一個(gè)16GB的磁盤，塊大小位512字節(jié)時(shí)位表占用4MB，如果每次去數(shù)據(jù)都從硬盤加載4MB的位表的話這個(gè)速度是難以忍受的。

　　鏈?zhǔn)娇臻e區(qū)

　　空閑表可以使用指向每個(gè)空閑區(qū)的指針和他們的長(zhǎng)度值被連接在一起，因?yàn)榭臻e表只需要一個(gè)指向第一個(gè)空閑區(qū)的指針，因此這種情況下空閑表的大小是可以忽略的。

　　這種分配法適合所有的文件分配方法，如果按塊分配可以移動(dòng)位于頭部的指針，如果是按區(qū)域分配則可以順序的找到合適的區(qū)域并更新指針。

　　存在的問題：1，使用一段時(shí)間磁盤會(huì)出現(xiàn)很多碎片，許多區(qū)變成只有一塊大小。2，寫時(shí)需要先讀取該塊以發(fā)現(xiàn)下一塊的指針，如果進(jìn)程請(qǐng)求大量的單個(gè)塊這個(gè)效率是很差的，同意刪除的時(shí)候也會(huì)導(dǎo)致很慢。

　　索引

　　索引是把空閑空間看做文件，使用之前介紹的索引表的方式記錄。基于效率的原因，索引適合使用在大小可變的分區(qū)分配的情況下。

　　空閑塊列表

　　每個(gè)空閑塊都有一個(gè)順序號(hào)，把順序號(hào)保存在磁盤的一個(gè)保留區(qū)中。根據(jù)磁盤的大小，存儲(chǔ)一個(gè)塊號(hào)需要24位或32位。這是一種令人滿意的方法，空閑塊列表部分保存在主存里：

　　1，磁盤空閑塊列表占用空間小于磁盤空間的1%。

　　2，盡管空閑塊太大了，不能保存在主存。但是兩種有效技術(shù)把該表的一小部分保存在主存里：

　　a，這個(gè)表可以是一個(gè)下推棧，棧中靠前的數(shù)千元素保存在內(nèi)存中，當(dāng)分配一個(gè)新塊時(shí)它從棧頂彈出，同樣當(dāng)一個(gè)塊被接觸時(shí)把它壓入棧中。只有棧中部分滿了或者空了時(shí)候才需要從磁盤傳輸數(shù)據(jù)，通常情況下它是零訪問時(shí)間的。

　　b，這個(gè)表可以看所FIFO的隊(duì)列，分配時(shí)從頭部取走，取消分配時(shí)從隊(duì)尾入隊(duì)，只有隊(duì)空了或者滿了時(shí)才需要與磁盤傳輸。

看了“操作系統(tǒng)總結(jié)知識(shí)”還想看：

1.操作系統(tǒng)主要知識(shí)點(diǎn)

2.操作系統(tǒng)知識(shí)大全

3.操作系統(tǒng)基本知識(shí) 操作系統(tǒng)知識(shí)點(diǎn)

4.linux操作系統(tǒng)基礎(chǔ)知識(shí)總結(jié)

5.系統(tǒng)與設(shè)計(jì)知識(shí)點(diǎn)歸納

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

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

相關(guān)文章

熱門文章