操作系統(tǒng)總結知識
操作系統(tǒng)總結知識
你還在為不知道操作系統(tǒng)總結知識而不知所措么?下面來是學習啦小編為大家收集的操作系統(tǒng)總結知識，歡迎大家閱讀：
操作系統(tǒng)總結知識
第一章 操作系統(tǒng)引論
系統(tǒng)的目標：有效性(提高資源利用率和系統(tǒng)吞吐量)、方便性、可擴充性、開放性。
有效性和方便性是操作系統(tǒng)最重要兩個目標。
操作系統(tǒng)的作用：
(1) OS作為用戶與計算機硬件系統(tǒng)之間的接口
(2) OS作為計算機系統(tǒng)資源的管理者(處理器、存儲器、I/O設備、數(shù)據(jù)程序)
(3) OS實現(xiàn)了對計算機資源的抽象(在硬件上覆蓋I/O設備、文件和窗口管理軟件，即虛擬機)
OS的發(fā)展過程：無操作系統(tǒng)的計算機系統(tǒng)→單道批處理系統(tǒng)→多道批處理系統(tǒng)→分時系統(tǒng)→實時系統(tǒng)→微機操作系統(tǒng)
操作系統(tǒng)的基本特征：
(1) 并發(fā)性(兩個或多個事件在同一時間間隔內發(fā)生;進入進程和線程)
(2) 共享性(系統(tǒng)中資源可供內存中多個并發(fā)執(zhí)行的進程(線程)共同使用，方式為互斥共享方式和同時訪問方式)
(3) 虛擬性(通過某種技術把一個物理實體變?yōu)槿舾蓚€邏輯上的對應物。方式：時分復用技術和空分復用技術)
(4) 異步性(進程以不可預知的速度向前推進，多道程序設計固有的特點)
OS的主要功能：
(1) 處理機管理(進程管理)功能;(主要包括創(chuàng)建和撤銷進程、協(xié)調諸進程的運行、實現(xiàn)進程間信息交換、把處理機分配給進程。進程同步機制功能是協(xié)調多個進程的運行，分為競爭和協(xié)作兩種方式，實現(xiàn)進程同步常用的及時是信號量機制。調度包括作業(yè)調度和進程調度兩步。)
(2) 存儲器管理功能;(內存分配、內存保護、地址映射和內存擴充等功能。內存分配有動態(tài)和靜態(tài)兩方式。內容擴充的功能是請求調入和置換)
(3) 設備管理功能(緩沖管理、設備分配、設備處理和虛擬設備。緩沖管理包括單、雙、公用緩沖機制。設備處理的人物是實現(xiàn)CPU和設備控制器之間的通信)
(4) 文件管理功能;(文件存儲空間管理、目錄管理、文件讀寫管理、共享保護功能)
(5) 操作系統(tǒng)與用戶之間的接口;(用戶接口和程序接口)
第二章 進程管理
進程與線程的基本概念
1) 進程是為了使多個程序能并發(fā)執(zhí)行，以提高資源利用率和系統(tǒng)吞吐量。
2) 線程是為了減少程序在并發(fā)執(zhí)行時所付出的空間開銷，是OS具有更好的并發(fā)性。
進程和線程的區(qū)別
1) 調度：線程作為調度和分派的基本單位;進程作為資源擁有的基本單位。
2) 并發(fā)性：進程之間可以并發(fā)執(zhí)行，進程中的諸線程之間也可并發(fā)執(zhí)行。
3) 擁有資源：進程擁有資源，線程無資源，但可以訪問所屬進程的資源
4) 系統(tǒng)開銷：創(chuàng)建可撤銷進程的代價比創(chuàng)建和撤銷線程的代價大的多。
前趨圖是描述進程之間執(zhí)行的前后關系的。
進程的特征：
1) 結構特征;由程序段、相關的數(shù)據(jù)項和PCB三部分構成了進程實體。
2) 動態(tài)性;指從創(chuàng)建、調度執(zhí)行到撤銷的過程是動態(tài)的。
3) 并發(fā)性;
4) 獨立性;因為有PCB，可以獨立運行、獨立分配資源、獨立接受調度等功能
5) 異步性;各進程按各自獨立、不可預知的速度向前推進。
進程的三種基本狀態(tài)：
1) 就緒狀態(tài);處CPU外，已占有其他必要的資源的進程
2) 執(zhí)行狀態(tài);
3) 阻塞狀態(tài);因事故是正在執(zhí)行的進程停止，并讓出CPU。
信號量機制是一種卓有成效的進程同步工具。包括整形信號量、記錄型信號量、AND型信號量、信號量集。
第三章 處理機調度與死鎖
批量型作業(yè)通常需要經歷作業(yè)調度(高級調度或長程調度)和進程調度(低級調度和短程調度)兩個過程后方能獲得處理機。
處理機調度層次
1) 高級調度：把外存上處于后備隊列中的那些作業(yè)調入內存。
2) 低級調度：它決定就緒隊列中的哪個進程將獲得處理機，然后由分派程序執(zhí)行把處理機分配給該進程的操作。對象是進程。功能是：保存處理機現(xiàn)場信息(PCB);按某種算法選取進程;把處理器分配給進程。方式分為非搶占方式和搶占方式。
3) 中級調度：內存中不能有太多的進程，把進程從內存移到外存，當內存有足夠空間時，再將合適的進程換入內存，等待進程調度。目的是提高內存利用率和系統(tǒng)吞吐量。
死鎖：多個進程在運行過程中因爭奪資源而造成的一種僵局。
活鎖：多個進程在運行工程中因相互謙讓而造成的一種僵局。
產生死鎖的原因
1) 競爭資源
2) 進程間推進順序非法
產生死鎖的必要條件
1) 互斥條件：臨界資源的互斥訪問
2) 請求和保持條件：占著自己的資源不放，又去請求別人的
3) 不剝奪條件：進程沒有完成則不是放占有的資源
4) 環(huán)路等待條件：發(fā)生死鎖指必然存在一個資源環(huán)形鏈。
處理死鎖的基本方法
1) 預防死鎖
2) 避免死鎖
3) 檢測和解除死鎖
安全序列：是指系統(tǒng)能夠找到一個進程順序(P1、P2……Pn)，來為每個進程Pi分配所需資源，知道滿足每個進程的最大需求，是每個進程能夠順利完成，則P1、P2……Pn即為安全狀態(tài)。
用資源分配圖對死鎖進行檢測，消去途中的所有邊，若節(jié)點為孤立節(jié)點，則為可完全簡化。
死鎖的解除
1) 剝奪資源：從其他進程剝奪足夠數(shù)量的資源給死鎖進程，以解除死鎖狀態(tài)
2) 撤銷進程：一種方法是夭折全部進程;另一種方法是按某個順序逐個撤銷進程，知道死鎖狀態(tài)被解除。
第四章 存儲器管理
連續(xù)分配方式：一個用戶程序分配一個連續(xù)的內存空間
1) 單一連續(xù)分配：一個程序裝入其他程序就不允許被裝入。只是用于單用戶單任務的OS中。
2) 固定分區(qū)分配：把內存分為若干個固定大小的區(qū)域，每個分區(qū)裝入一個作業(yè)，允許并發(fā)執(zhí)行。
3) 動態(tài)分區(qū)分配：根據(jù)實際需要，動態(tài)地為之分配內存空間。
4) 動態(tài)重定位分區(qū)分配：通過重定位寄存器把相對地址轉化成物理地址，此轉化過程是在程序執(zhí)行期間，隨著每條指令或數(shù)據(jù)的訪問自動進行的，故稱為動態(tài)重定位。
分區(qū)分配算法
1) 首次適應算法(以地址遞增次序訪問)
2) 循環(huán)首次適應算法(從上一次分配處開始查找)
3) 最佳適應算法(小內存到大內存依次查找)
4) 最壞適應算法(每次分配從大內存開始割讓)
5) 快速適應算法(對空閑分區(qū)進行分類，并建立索引表，選最適合的控件分配給請求的進程)
對換：把暫時不運行的程序調到外存，需要時再調到內存。
地址變換機制：將用戶地址空間中的邏輯地址變換為內存空間中的物理地址。
引入分段存儲管理方式的目的，則主要是為了滿足用戶在編程和使用上多方面的要求。
段表是用于實現(xiàn)從邏輯段到物理內存區(qū)的映射。
分頁和分段的主要區(qū)別
1) 兩者都采用離散分配方式，且都要通過地址應設機構來實現(xiàn)地址變換。
2) 頁是信息的物理單位，分頁是為了有效的管理內存;段是邏輯單位，分段是為了維護信息完整性和獨立性。
3) 頁的大小固定且由系統(tǒng)決定，段的長度不固定，決定于用戶編寫的程序。
4) 分頁的作業(yè)地址空間是一維的，而分段的作業(yè)地址空間是二維的。
段頁式存儲管理方式的原理：分段和分頁相結合，先將用戶程序分成若干個段，再把每個段分成若干個頁，并為每個段賦予一個段名。其地質結構由段號、段內頁號和頁內地址組成。
頁面置換算法有：最佳置換算法、先進先出置換算法、最近最久未使用置換算法、Clock置換算法。
第五章 設備管理
I/O系統(tǒng)是用于實現(xiàn)數(shù)據(jù)輸入、輸出及數(shù)據(jù)存儲的系統(tǒng)。
I/O設備類型：
1) 特性：存儲設備;輸入/輸出設備。
2) 傳輸速率：低速設備;中速設備;高速設備。
3) 信息交換的單位分類：塊設備;字符設備。
4) 共享屬性：獨占設備;共享設備;虛擬設備。
設備與控制器之間的接口：
1) 數(shù)據(jù)信號線：設備和設備控制器之間傳送數(shù)據(jù)信號
2) 控制信號線：設備控制器向I/O設備發(fā)送控制信號的通路
3) 狀態(tài)信號線：傳送指示設備當前狀態(tài)的信號。
設備控制器
主要職責是控制一個或多個I/O設備，以實現(xiàn)I/O設備和計算機之間的數(shù)據(jù)交換。是CPU和I/O設備的接口，他接受CPU指令去控制I/O設備工作，使減輕處理機的工作量。
設備控制器包括控制字符設備控制器和控制塊設備的控制器。
設備控制器的基本功能
1) 接受和識別命令
2) 數(shù)據(jù)交換
3) 標識和報告設備的狀態(tài)
4) 地址識別(CPU通過地質控制設備)
5) 數(shù)據(jù)緩沖
6) 差錯控制
I/O通道是一種特殊的處理機，它具有執(zhí)行I/O指令的能力，可以控制I/O操作。類型分為：字節(jié)多路通道、數(shù)組選擇通道、數(shù)組多路通道。
解決“瓶頸”問題的最有效的方法是增加設備到主機間的通路而不增加通道。
I/O控制方式
1) 程序I/O方式
2) 中斷驅動I/O控制方式
3) 直接存儲器訪問(DMA)I/O控制方式
4) I/O通道控制方式
SPOOLing技術
通過SPOOLing技術便可將一臺物理I/O設備虛擬為多臺邏輯I/O設備，同樣允許多個用戶共享一臺物理I/O設備。
Spooling系統(tǒng)的組成
輸入井和輸入井;輸入緩沖區(qū)和輸出緩沖區(qū);輸入進程和輸出進程。
SPOOLing系統(tǒng)的特點
1) 提高了I/O的速度
2) 將獨占設備改造為共享設備
3) 實現(xiàn)了虛擬設備功能
磁盤調度
磁盤調度的主要目標是使磁盤的平均尋道時間最少。
常用的磁盤調度算法
1) 先來先服務(適合進程較少的場合)
2) 最短尋道時間優(yōu)先(要訪問的磁道與當前磁頭所在磁道距離最近。會導致進程“饑餓”現(xiàn)象)
3) 掃描算法(考慮訪問的磁道與當前磁頭所在磁道距離最近和磁頭當前移動的方向)
4) 循環(huán)掃描算法(規(guī)定磁頭單向移動)
5) NSPetpSCAN和FSCAN調度算法
第六章 文件管理
文件邏輯結構的類型
1) 有結構文件(由一個以上的記錄構成的文件，又稱記錄式文件)
2) 無結構文件(由字符流構成的文件，又稱流式文件)
記錄式文件的長度分為定長記錄和變長記錄。
記錄文件又分為順序文件、索引文件、索引順序文件。
大量的數(shù)據(jù)結構而后數(shù)據(jù)庫是采用有結構的文件形式
而大量的源代碼、可執(zhí)行文件、庫函數(shù)等采用無結構文件。
順序文件的優(yōu)缺點
1) 適合進行批量存取
2) 存取效率是所有邏輯文件中最高的
3) 也只有順序文件才能存儲在磁帶上，并能有效的工作
4) 不適合查找或修改單個記錄
5) 增加或刪除一個記錄時比較困難
索引文件的缺點：除了有主文件外，還須配置一張索引表，而且每個記錄都要有一個索引表，因此提高了存儲費用。
對已直接文件，檢索時可以根據(jù)記錄鍵值直接獲得指定記錄的物理地址。
哈希文件是鍵值通過Hash函數(shù)指向目錄表，該表目的內容指向記錄所在的物理塊。
外存分配方式：連續(xù)分配、連接分配和索引分配三種。
連續(xù)分配的優(yōu)缺點
1) 順序訪問容易
2) 順序訪問速度快
缺點：
1) 要求有連續(xù)的存儲空間
2) 必須實現(xiàn)知道文件的長度
鏈接分配中的鏈接方式分為隱式鏈接和顯式鏈接。
為新建文件分配存儲空間的方式分為連續(xù)和離散的分配方式。前置具有較高的文件訪問速度，但可能產生較多的外存零頭。后者能有效的利用外存空間，但訪問速度較慢。無論哪種方式，存儲空間的基本分配單位都是磁盤塊而非字節(jié)。
文件存儲空間管理的方法
1) 空閑表法和空閑鏈表法
2) 位示圖法
3) 成組鏈接法
空閑表法和空閑鏈表法都不適用于大型文件系統(tǒng)可使用成組鏈接法。
常見面試題：
1、進程是并發(fā)過程中程序的執(zhí)行過程
2、進程的特征：結構特征動態(tài)性并發(fā)性獨立性異步性
3、臨界區(qū)指在每個進程中訪問臨界資源的那段代碼
4，現(xiàn)在操作系統(tǒng)中申請資源的基本單位是進程，在CPU得到執(zhí)行的基本單位是線程，進程是由程序段、數(shù)據(jù)段、PCB組成的
5，對臨界資源應采取互斥訪問方式來實現(xiàn)共享
6，P.V操作是一種低級進程通信原語
7，對于記錄性信號量，在執(zhí)行一次P操作時，信號量的值應當減1，當其值為小于0時進程應阻塞;在執(zhí)行V操作時，信號量的值應當加1;當其值小于等于0時，應喚醒阻塞隊列中的進程。
8，N個進程共享某一臨界資源，(n-1)~1
9，短作業(yè)優(yōu)先算法，T1<T2<T3平均周轉時間為：T1+2XT2/3+T3/3
10，響應比Rp=(等待時間+要求服務時間)/要求服務器時間=響應時間/要求服務時間
11死鎖是指多個進程在運行過程中因爭奪資源，而造成的一種僵局，當進程處于這種僵局狀態(tài)時，若無外力作用，他們都將無法再向前推進。
死鎖的避免是根據(jù)防止系統(tǒng)進入不安全狀態(tài)。
產生死鎖的根本原因是資源分配不當和資源數(shù)量不足，發(fā)生死鎖的四個必要條件是：互斥條件，請求和保持條件，不剝奪條件和環(huán)路等待條件，銀行家算法用于避免死鎖
12，如果系統(tǒng)中有N個進程，最多為(N-1)個
13，若系統(tǒng)采用輪轉法調度進程系統(tǒng)采用的是剝奪式調度
14，既考慮作業(yè)等待時間，又考慮作業(yè)執(zhí)行時間，的調度算法是響應比優(yōu)先調度算法
15，資源的有序分配策略可以破壞死鎖的“循環(huán)等待”
16，并非所有的不安全狀態(tài)都必然會轉為死鎖狀態(tài)，但當系統(tǒng)進圖不安全按狀態(tài)后變有可能進入死鎖狀態(tài)，
17，重定位：在作業(yè)地址空間中使用的邏輯地址變?yōu)閮却嫖锢淼刂?/p>
18，支持程序放在不連續(xù)內存中儲存管理方法有分取式分配，分段式分配，段頁式分配頁式存儲主要特點是不要將作業(yè)同時全部裝入到主存的的連續(xù)區(qū)域
19，適合多道程序運行的存儲管理中，存儲保護是為了防止各道作業(yè)的相互干擾
20，采用頁式存儲管理時，重定位的工作由地址轉換機
21，段頁式存儲管理中的地址映像表是每個作業(yè)或進程一張段表，每個段一張頁表
22，在虛擬頁式存儲管理方案中，完成將頁面調入內存的工作的是缺頁中斷處理
23，分段管理和分頁管理的主要區(qū)別是分頁管理有存儲保護，分段管理沒有
24，在股低估分區(qū)分配中，可以不同但預先固定的
25，不使用中斷機構的I/O控制方式是程序I/O方式
26，spooling技術能獨占設備改造成可以共享的虛擬設備
27，磁盤防偽中把數(shù)據(jù)從磁盤讀出，叫做傳輸時間
28，共享設備指同一時間內運行多個進程同時訪問的設備
29，通過軟件的功能擴充，把原來獨占的設備愛造成若干個可共享的設備，虛擬設備
30，DMA方式如果I/O設備不通過CPU來完成
31，設備獨立性用戶程序獨立于具體物理設備的一種特性
32，虛擬設備一個物理設備變換成多個對應的邏輯設備
33，通道是一種特殊的處理機，通道按傳遞數(shù)據(jù)的方式分為：字節(jié)多路通道，數(shù)組選擇通道，數(shù)組多路通道
通道涉及的數(shù)據(jù)結構是設備控制器，控制器控制塊，通道控制塊，系統(tǒng)設備表
34，磁盤高速緩沖設在內存中，目的是提高I/O磁盤速度
35，磁盤空間的地址有盤面號，柱面號，扇區(qū)號組成。訪問磁盤的時間有 尋道時間，旋轉等待時間，讀寫時間
36，將系統(tǒng)段用參數(shù)翻譯成設備操作命令的工作由設備無關的操作系統(tǒng)完成
37，向設備寄存器寫入控制命令由設備驅動程序完成
38，尋找設備驅動程序由設備無關的操作系統(tǒng)軟件完成
39，設備管理的功能是設備分配，緩沖區(qū)管理和實現(xiàn)物理I/O設備的操作
40，根據(jù)設備的固有屬性特點，設備可分為獨占設備，共享設備和虛擬設備
41，引入緩沖區(qū)技術可提高處理器執(zhí)行程序和設備的輸入輸出操作的并行程序文件管理
42，物理文件的組織方式是由操作系統(tǒng)確定的，文件的順序存取是按文件的邏輯號逐一存取
43，系統(tǒng)通過樹形目錄結構來解決重名問題
44，在UNIX操作系統(tǒng)中，把輸入輸出設備看做特殊文件
45，打開文件操作的主要工作是把指定的目錄復制到內存指定區(qū)域
46，文件路徑名是指從根目錄到該文件所經歷的路徑中各符號名的集合
47，按邏輯結構劃分，文件主要有兩類：記錄是文件，流式文件，文件系統(tǒng)的主要目的是實現(xiàn)對文件的按名存取
48連續(xù)結構文件必須采用連續(xù)分配方式，而鏈接結構文件和索引結構文件都可采取離散分配方式
49，文件系統(tǒng)中，若文件的物理結構采用連續(xù)結構有關文件的物理位置的信息包括首塊地址和文件長度
50，位示圖可用于磁盤空間管理，在文件系統(tǒng)中，為實現(xiàn)文件保護，一般采用口令，密碼和訪問控制
1、進程是具有獨立功能程序在某個數(shù)據(jù)集合上的一次執(zhí)行過程。線程是進程內的一個執(zhí)行實體或執(zhí)行單元。
進程和線程的區(qū)別：
(a)不同進程的地址空間是獨立的，而同一進程內的線程共享同一地址空間。一個進程的線程在另一個進程內是不可見的。
(b) 在引入線程的操作系統(tǒng)中，進程是資源分配和調度的單位，線程是處理機調度和分配的單位，資源是分配給進程的，線程只擁有很少資源，因而切換代價比進程切換低。
2、死鎖在多道程序系統(tǒng)中，當一組進程中的每個進程均無限期地等待被改組進程中的另一進程所占有且永遠不會釋放的資源，此時的系統(tǒng)處于死鎖狀態(tài)。
死鎖產生的原因：
(a)系統(tǒng)提供的資源有限;
(b)進程推進順序不當。
產生死鎖的必要條件：互斥條件、不可剝奪條件、請求和保持條件、循環(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è)同時運行，就要解決對處理機分配調度策略、分配實施和資源回收等問題。
2.存儲管理。存儲管理的主要工作是對內部存儲器進行分配、保護和擴充和管理。
3.設備管理。涉及到通道、控制器、輸入輸出設備的分配和管理以及設備獨立性。
4.信息管理(文件系統(tǒng)管理) 是對系統(tǒng)的軟件資源的管理。
5.用戶接口。操作系統(tǒng)還為用戶提供一個友好的用戶接口。一般來說，操作系統(tǒng)提供兩種方式的接口來為用戶服務。
5、分級調度分為4級：
(1) 作業(yè)調度
(2) 交換調度
(3) 進程調度
(4) 線程調度。
6、試寫出程序與進程的區(qū)別
(1)進程是一個動態(tài)概念，而程序是一個靜態(tài)概念。
(2)進程具有并行特征，而程序不反映執(zhí)行所以沒有并行特征
(3)進程是競爭計算機系統(tǒng)資源的基本單位，而程序不反映執(zhí)行也就不會競爭計算機系統(tǒng)資源
(4)不同的進程可以包含同一程序，只要該程序所對應的數(shù)據(jù)集不同。
7、頁式管理的基本原理是什么?
(1)進程的虛擬空間被劃分成長度相等的頁。
(2)內存空間也按頁的大小劃分成長度相等的頁面。
(3)采用請求調頁或預調技術實現(xiàn)內外存儲器的統(tǒng)一管理。
8、進程調度有哪些功能?
(1)記錄系統(tǒng)中所有進程的執(zhí)行情況。
(2)選擇占有處理機的進程
(3)進行進程上下文切換
9、批處理操作系統(tǒng)、分時操作系統(tǒng)和實時操作系統(tǒng)的特點各是什么?
(1) 批處理操作系統(tǒng)的特點：成批處理，系統(tǒng)吞吐量高，資源利用率高，用戶不能直接干預作業(yè)的執(zhí)行。
(2)分時操作系統(tǒng)的特點：多路性、獨立性、及時性、交互性。
(3)實時操作系統(tǒng)的特點：及時響應、快速處理;高可靠性和安全性;不要求系統(tǒng)資源利用率。
10、Windows下的內存是如何管理的?
Windows提供了3種方法來進行內存管理：虛擬內存，最適合用來管理大型對象或者結構數(shù)組;內存映射文件，最適合用來管理大型數(shù)據(jù)流(通常來自文件)以及在單個計算機上運行多個進程之間共享數(shù)據(jù);內存堆棧，最適合用來管理大量的小對象。
Windows操縱內存可以分兩個層面：物理內存和虛擬內存。
其中物理內存由系統(tǒng)管理，不允許應用程序直接訪問，應用程序可見的只有一個2G地址空間，而內存分配是通過堆進行的。對于每個進程都有自己的默認堆，當一個堆創(chuàng)建后，就通過虛擬內存操作保留了相應大小的地址塊(不占有實際的內存，系統(tǒng)消耗很小)。當在堆上分配一塊內存時，系統(tǒng)在堆的地址表里找到一個空閑塊(如果找不到，且堆創(chuàng)建屬性是可擴充的，則擴充堆大小)，為這個空閑塊所包含的所有內存頁提交物理對象(在物理內存上或硬盤的交換文件上)，這時就可以訪問這部分地址。提交時，系統(tǒng)將對所有進程的內存統(tǒng)一調配，如果物理內存不夠，系統(tǒng)試圖把一部分進程暫時不訪問的頁放入交換文件，以騰出部分物理內存。釋放內存時，只在堆中將所在的頁解除提交(相應的物理對象被解除)，繼續(xù)保留地址空間。
如果要知道某個地址是否被占用/可不可以訪問，只要查詢此地址的虛擬內存狀態(tài)即可。如果是提交，則可以訪問。如果僅僅保留，或沒保留，則產生一個軟件異常。此外，有些內存頁可以設置各種屬性。如果是只讀，向內存寫也會產生軟件異常。
11、Windows消息調度機制是(C)
A)指令隊列;B)指令堆棧;C)消息隊列;D)消息堆棧
解析：
處理消息隊列的順序。首先Windows絕對不是按隊列先進先出的次序來處理的，而是有一定優(yōu)先級的。優(yōu)先級通過消息隊列的狀態(tài)標志來實現(xiàn)的。首先，最高優(yōu)先級的是別的線程發(fā)過來的消息(通過sendmessage);其次，處理登記消息隊列消息;再次處理QS_QUIT標志，處理虛擬輸入隊列，處理wm_paint;最后是wm_timer。
12、描述實時系統(tǒng)的基本特性
在特定時間內完成特定的任務，實時性與可靠性。
所謂“實時操作系統(tǒng)”，實際上是指操作系統(tǒng)工作時，其各種資源可以根據(jù)需要隨時進行動態(tài)分配。由于各種資源可以進行動態(tài)分配，因此，其處理事務的能力較強、速度較快。
13、中斷和輪詢的特點
對I/O設備的程序輪詢的方式，是早期的計算機系統(tǒng)對I/O設備的一種管理方式。它定時對各種設備輪流詢問一遍有無處理要求。輪流詢問之后，有要求的，則加以處理。在處理I/O設備的要求之后，處理機返回繼續(xù)工作。盡管輪詢需要時間，但輪詢要比I/O設備的速度要快得多，所以一般不會發(fā)生不能及時處理的問題。當然，再快的處理機，能處理的輸入輸出設備的數(shù)量也是有一定限度的。而且，程序輪詢畢竟占據(jù)了CPU相當一部分處理時間，因此，程序輪詢是一種效率較低的方式，在現(xiàn)代計算機系統(tǒng)中已很少應用。
程序中斷通常簡稱中斷，是指CPU在正常運行程序的過程中，由于預先安排或發(fā)生了各種隨機的內部或外部事件，使CPU中斷正在運行的程序，而轉到為響應的服務程序去處理。
輪詢——效率低，等待時間很長，CPU利用率不高。
中斷——容易遺漏一些問題，CPU利用率高。
14、什么是臨界區(qū)?如何解決沖突?
每個進程中訪問臨界資源的那段程序稱為臨界區(qū)，每次只準許一個進程進入臨界區(qū)，進入后不允許其他進程進入。
(1)如果有若干進程要求進入空閑的臨界區(qū)，一次僅允許一個進程進入;
(2)任何時候，處于臨界區(qū)內的進程不可多于一個。如已有進程進入自己的臨界區(qū)，則其它所有試圖進入臨界區(qū)的進程必須等待;
(3)進入臨界區(qū)的進程要在有限時間內退出，以便其它進程能及時進入自己的臨界區(qū);
(4)如果進程不能進入自己的臨界區(qū)，則應讓出CPU，避免進程出現(xiàn)“忙等”現(xiàn)象。
15、說說分段和分頁
頁是信息的物理單位，分頁是為實現(xiàn)離散分配方式，以消減內存的外零頭，提高內存的利用率;或者說，分頁僅僅是由于系統(tǒng)管理的需要，而不是用戶的需要。
段是信息的邏輯單位，它含有一組其意義相對完整的信息。分段的目的是為了能更好的滿足用戶的需要。
頁的大小固定且由系統(tǒng)確定，把邏輯地址劃分為頁號和頁內地址兩部分，是由機器硬件實現(xiàn)的，因而一個系統(tǒng)只能有一種大小的頁面。段的長度卻不固定，決定于用戶所編寫的程序，通常由編輯程序在對源程序進行編輯時，根據(jù)信息的性質來劃分。
分頁的作業(yè)地址空間是一維的，即單一的線性空間，程序員只須利用一個記憶符，即可表示一地址。分段的作業(yè)地址空間是二維的，程序員在標識一個地址時，既需給出段名，又需給出段內地址。
16、說出你所知道的保持進程同步的方法?
進程間同步的主要方法有原子操作、信號量機制、自旋鎖、管程、會合、分布式系統(tǒng)等。
17、Linux中常用到的命令
顯示文件目錄命令ls 如ls
改變當前目錄命令cd 如cd /home
建立子目錄mkdir 如mkdir xiong
刪除子目錄命令rmdir 如rmdir /mnt/cdrom
刪除文件命令rm 如rm /ucdos.bat
文件復制命令cp 如cp /ucdos /fox
獲取幫助信息命令man 如man ls
顯示文件的內容less 如less mwm.lx
重定向與管道type 如type readme>>direct，將文件readme的內容追加到文direct中
18、Linux文件屬性有哪些?(共十位)
-rw-r--r--那個是權限符號，總共是- --- --- ---這幾個位。
第一個短橫處是文件類型識別符：-表示普通文件;c表示字符設備(character);b表示塊設備(block);d表示目錄(directory);l表示鏈接文件(link);后面第一個三個連續(xù)的短橫是用戶權限位(User)，第二個三個連續(xù)短橫是組權限位(Group)，第三個三個連續(xù)短橫是其他權限位(Other)。每個權限位有三個權限，r(讀權限)，w(寫權限)，x(執(zhí)行權限)。如果每個權限位都有權限存在，那么滿權限的情況就是：-rwxrwxrwx;權限為空的情況就是- --- --- ---。
權限的設定可以用chmod命令，其格式位：chmod ugoa+/-/=rwx filename/directory。例如：
一個文件aaa具有完全空的權限- --- --- ---。
chmod u+rw aaa(給用戶權限位設置讀寫權限，其權限表示為：- rw- --- ---)
chmod g+r aaa(給組設置權限為可讀，其權限表示為：- --- r-- ---)
chmod ugo+rw aaa(給用戶，組，其它用戶或組設置權限為讀寫，權限表示為：- rw- rw- rw-)
如果aaa具有滿權限- rwx rwx rwx。
chmod u-x aaa(去掉用戶可執(zhí)行權限，權限表示為：- rw- rwx rwx)
如果要給aaa賦予制定權限- rwx r-x r-x，命令為：
chmod u=rwx，Go=rx aaa
19、簡術OSI的物理層Layer1，鏈路層Layer2，網(wǎng)絡層Layer3的任務。
網(wǎng)絡層：通過路由選擇算法，為報文或分組通過通信子網(wǎng)選擇最適當?shù)穆窂健?/p>
鏈路層：通過各種控制協(xié)議，將有差錯的物理信道變?yōu)闊o差錯的、能可靠傳輸數(shù)據(jù)幀的數(shù)據(jù)鏈路。
物理層：利用傳輸介質為數(shù)據(jù)鏈路層提供物理連接，實現(xiàn)比特流的透明傳輸。
20、什么是中斷?中斷時CPU做什么工作?
中斷是指在計算機執(zhí)行期間，系統(tǒng)內發(fā)生任何非尋常的或非預期的急需處理事件，使得CPU暫時中斷當前正在執(zhí)行的程序而轉去執(zhí)行相應的事件處理程序。待處理完畢后又返回原來被中斷處繼續(xù)執(zhí)行或調度新的進程執(zhí)行的過程。
21、你知道操作系統(tǒng)的內容分為幾塊嗎?什么叫做虛擬內存?他和主存的關系如何?內存管理屬于操作系統(tǒng)的內容嗎?
操作系統(tǒng)的主要組成部分：進程和線程的管理，存儲管理，設備管理，文件管理。虛擬內存是一些系統(tǒng)頁文件，存放在磁盤上，每個系統(tǒng)頁文件大小為4K，物理內存也被分頁，每個頁大小也為4K，這樣虛擬頁文件和物理內存頁就可以對應，實際上虛擬內存就是用于物理內存的臨時存放的磁盤空間。頁文件就是內存頁，物理內存中每頁叫物理頁，磁盤上的頁文件叫虛擬頁，物理頁+虛擬頁就是系統(tǒng)所有使用的頁文件的總和。
22、線程是否具有相同的堆棧?dll是否有獨立的堆棧?
每個線程有自己的堆棧。
dll是否有獨立的堆棧?這個問題不好回答，或者說這個問題本身是否有問題。因為dll中的代碼是被某些線程所執(zhí)行，只有線程擁有堆棧。如果dll中的代碼是exe中的線程所調用，那么這個時候是不是說這個dll沒有獨立的堆棧?如果dll中的代碼是由dll自己創(chuàng)建的線程所執(zhí)行，那么是不是說dll有獨立的堆棧?
以上講的是堆棧，如果對于堆來說，每個dll有自己的堆，所以如果是從dll中動態(tài)分配的內存，最好是從dll中刪除;如果你從dll中分配內存，然后在exe中，或者另外一個dll中刪除，很有可能導致程序崩潰。
23、什么是緩沖區(qū)溢出?有什么危害?其原因是什么?
緩沖區(qū)溢出是指當計算機向緩沖區(qū)內填充數(shù)據(jù)時超過了緩沖區(qū)本身的容量，溢出的數(shù)據(jù)覆蓋在合法數(shù)據(jù)上。
危害：在當前網(wǎng)絡與分布式系統(tǒng)安全中，被廣泛利用的50%以上都是緩沖區(qū)溢出，其中最著名的例子是1988年利用fingerd漏洞的蠕蟲。而緩沖區(qū)溢出中，最為危險的是堆棧溢出，因為入侵者可以利用堆棧溢出，在函數(shù)返回時改變返回程序的地址，讓其跳轉到任意地址，帶來的危害一種是程序崩潰導致拒絕服務，另外一種就是跳轉并且執(zhí)行一段惡意代碼，比如得到shell，然后為所欲為。通過往程序的緩沖區(qū)寫超出其長度的內容，造成緩沖區(qū)的溢出，從而破壞程序的堆棧，使程序轉而執(zhí)行其它指令，以達到攻擊的目的。
造成緩沖區(qū)溢出的主原因是程序中沒有仔細檢查用戶輸入的參數(shù)。
24、什么是死鎖?其條件是什么?怎樣避免死鎖?
死鎖的概念：在兩個或多個并發(fā)進程中，如果每個進程持有某種資源而又都等待別的進程釋放它或它們現(xiàn)在保持著的資源，在未改變這種狀態(tài)之前都不能向前推進，稱這一組進程產生了死鎖。通俗地講，就是兩個或多個進程被無限期地阻塞、相互等待的一種狀態(tài)。
死鎖產生的原因主要是：
(1)系統(tǒng)資源不足;
(2) 進程推進順序非法。
產生死鎖的必要條件：
(1)互斥(mutualexclusion)，一個資源每次只能被一個進程使用;
(2)不可搶占(nopreemption)，進程已獲得的資源，在未使用完之前，不能強行剝奪;
(3)占有并等待(hold andwait)，一個進程因請求資源而阻塞時，對已獲得的資源保持不放;
(4)環(huán)形等待(circularwait)，若干進程之間形成一種首尾相接的循環(huán)等待資源關系。
這四個條件是死鎖的必要條件，只要系統(tǒng)發(fā)生死鎖，這些條件必然成立，而只要上述條件之一不滿足，就不會發(fā)生死鎖。
死鎖的解除與預防：理解了死鎖的原因，尤其是產生死鎖的四個必要條件，就可以最大可能地避免、預防和解除死鎖。所以，在系統(tǒng)設計、進程調度等方面注意如何不讓這四個必要條件成立，如何確定資源的合理分配算法，避免進程永久占據(jù)系統(tǒng)資源。此外，也要防止進程在處于等待狀態(tài)的情況下占用資源。因此，對資源的分配要給予合理的規(guī)劃。
死鎖的處理策略：鴕鳥策略、預防策略、避免策略、檢測與恢復策略。
附錄：
1、什么是進程(Process)和線程(Thread)?有何區(qū)別?
進程是具有一定獨立功能的程序關于某個數(shù)據(jù)集合上的一次運行活動，進程是系統(tǒng)進行資源分配和調度的一個獨立單位。線程是進程的一個實體，是CPU調度和分派的基本單位，它是比進程更小的能獨立運行的基本單位。線程自己基本上不擁有系統(tǒng)資源，只擁有一點在運行中必不可少的資源(如程序計數(shù)器，一組寄存器和棧)，但是它可與同屬一個進程的其他的線程共享進程所擁有的全部資源。一個線程可以創(chuàng)建和撤銷另一個線程，同一個進程中的多個線程之間可以并發(fā)執(zhí)行。
進程與應用程序的區(qū)別在于應用程序作為一個靜態(tài)文件存儲在計算機系統(tǒng)的硬盤等存儲空間中，而進程則是處于動態(tài)條件下由操作系統(tǒng)維護的系統(tǒng)資源管理實體。
2、Windows下的內存是如何管理的?
Windows提供了3種方法來進行內存管理：虛擬內存，最適合用來管理大型對象或者結構數(shù)組;內存映射文件，最適合用來管理大型數(shù)據(jù)流(通常來自文件)以及在單個計算機上運行多個進程之間共享數(shù)據(jù);內存堆棧，最適合用來管理大量的小對象。
Windows操縱內存可以分兩個層面：物理內存和虛擬內存。
其中物理內存由系統(tǒng)管理，不允許應用程序直接訪問，應用程序可見的只有一個2G地址空間，而內存分配是通過堆進行的。對于每個進程都有自己的默認堆，當一個堆創(chuàng)建后，就通過虛擬內存操作保留了相應大小的地址塊(不占有實際的內存，系統(tǒng)消耗很小)。當在堆上分配一塊內存時，系統(tǒng)在堆的地址表里找到一個空閑塊(如果找不到，且堆創(chuàng)建屬性是可擴充的，則擴充堆大小)，為這個空閑塊所包含的所有內存頁提交物理對象(在物理內存上或硬盤的交換文件上)，這時就可以訪問這部分地址。提交時，系統(tǒng)將對所有進程的內存統(tǒng)一調配，如果物理內存不夠，系統(tǒng)試圖把一部分進程暫時不訪問的頁放入交換文件，以騰出部分物理內存。釋放內存時，只在堆中將所在的頁解除提交(相應的物理對象被解除)，繼續(xù)保留地址空間。
如果要知道某個地址是否被占用/可不可以訪問，只要查詢此地址的虛擬內存狀態(tài)即可。如果是提交，則可以訪問。如果僅僅保留，或沒保留，則產生一個軟件異常。此外，有些內存頁可以設置各種屬性。如果是只讀，向內存寫也會產生軟件異常。
3、Windows消息調度機制是?
A)指令隊列;B)指令堆棧;C)消息隊列;D)消息堆棧
答案：C
處理消息隊列的順序。首先Windows絕對不是按隊列先進先出的次序來處理的，而是有一定優(yōu)先級的。優(yōu)先級通過消息隊列的狀態(tài)標志來實現(xiàn)的。首先，最高優(yōu)先級的是別的線程發(fā)過來的消息(通過sendmessage);其次，處理登記消息隊列消息;再次處理QS_QUIT標志，處理虛擬輸入隊列，處理wm_paint;最后是wm_timer。
4、描述實時系統(tǒng)的基本特性
在特定時間內完成特定的任務，實時性與可靠性。
所謂“實時操作系統(tǒng)”，實際上是指操作系統(tǒng)工作時，其各種資源可以根據(jù)需要隨時進行動態(tài)分配。由于各種資源可以進行動態(tài)分配，因此，其處理事務的能力較強、速度較快。
5、中斷和輪詢的特點
對I/O設備的程序輪詢的方式，是早期的計算機系統(tǒng)對I/O設備的一種管理方式。它定時對各種設備輪流詢問一遍有無處理要求。輪流詢問之后，有要求的，則加以處理。在處理I/O設備的要求之后，處理機返回繼續(xù)工作。盡管輪詢需要時間，但輪詢要比I/O設備的速度要快得多，所以一般不會發(fā)生不能及時處理的問題。當然，再快的處理機，能處理的輸入輸出設備的數(shù)量也是有一定限度的。而且，程序輪詢畢竟占據(jù)了CPU相當一部分處理時間，因此，程序輪詢是一種效率較低的方式，在現(xiàn)代計算機系統(tǒng)中已很少應用。
程序中斷通常簡稱中斷，是指CPU在正常運行程序的過程中，由于預先安排或發(fā)生了各種隨機的內部或外部事件，使CPU中斷正在運行的程序，而轉到為響應的服務程序去處理。
輪詢——效率低，等待時間很長，CPU利用率不高。
中斷——容易遺漏一些問題，CPU利用率高。
6、什么是臨界區(qū)?如何解決沖突?
每個進程中訪問臨界資源的那段程序稱為臨界區(qū)，每次只準許一個進程進入臨界區(qū)，進入后不允許其他進程進入。
(1)如果有若干進程要求進入空閑的臨界區(qū)，一次僅允許一個進程進入;
(2)任何時候，處于臨界區(qū)內的進程不可多于一個。如已有進程進入自己的臨界區(qū)，則其它所有試圖進入臨界區(qū)的進程必須等待;
(3)進入臨界區(qū)的進程要在有限時間內退出，以便其它進程能及時進入自己的臨界區(qū);
(4)如果進程不能進入自己的臨界區(qū)，則應讓出CPU，避免進程出現(xiàn)“忙等”現(xiàn)象。
7、說說分段和分頁
頁是信息的物理單位，分頁是為實現(xiàn)離散分配方式，以消減內存的外零頭，提高內存的利用率;或者說，分頁僅僅是由于系統(tǒng)管理的需要，而不是用戶的需要。
段是信息的邏輯單位，它含有一組其意義相對完整的信息。分段的目的是為了能更好的滿足用戶的需要。
頁的大小固定且由系統(tǒng)確定，把邏輯地址劃分為頁號和頁內地址兩部分，是由機器硬件實現(xiàn)的，因而一個系統(tǒng)只能有一種大小的頁面。段的長度卻不固定，決定于用戶所編寫的程序，通常由編輯程序在對源程序進行編輯時，根據(jù)信息的性質來劃分。
分頁的作業(yè)地址空間是一維的，即單一的線性空間，程序員只須利用一個記憶符，即可表示一地址。分段的作業(yè)地址空間是二維的，程序員在標識一個地址時，既需給出段名，又需給出段內地址。
8、說出你所知道的保持進程同步的方法?
進程間同步的主要方法有原子操作、信號量機制、自旋鎖、管程、會合、分布式系統(tǒng)等。
9、Linux中常用到的命令
顯示文件目錄命令ls 如ls
改變當前目錄命令cd 如cd /home
建立子目錄mkdir 如mkdir xiong
刪除子目錄命令rmdir 如rmdir /mnt/cdrom
刪除文件命令rm 如rm /ucdos.bat
文件復制命令cp 如cp /ucdos /fox
獲取幫助信息命令man 如man ls
顯示文件的內容less 如less mwm.lx
重定向與管道type 如type readme>>direct，將文件readme的內容追加到文direct中
10、Linux文件屬性有哪些?(共十位)
-rw-r--r--那個是權限符號，總共是- --- --- ---這幾個位。
第一個短橫處是文件類型識別符：-表示普通文件;c表示字符設備(character);b表示塊設備(block);d表示目錄(directory);l表示鏈接文件(link);后面第一個三個連續(xù)的短橫是用戶權限位(User)，第二個三個連續(xù)短橫是組權限位(Group)，第三個三個連續(xù)短橫是其他權限位(Other)。每個權限位有三個權限，r(讀權限)，w(寫權限)，x(執(zhí)行權限)。如果每個權限位都有權限存在，那么滿權限的情況就是：-rwxrwxrwx;權限為空的情況就是- --- --- ---。
權限的設定可以用chmod命令，其格式位：chmod ugoa+/-/=rwx filename/directory。例如：
一個文件aaa具有完全空的權限- --- --- ---。
chmod u+rw aaa(給用戶權限位設置讀寫權限，其權限表示為：- rw- --- ---)
chmod g+r aaa(給組設置權限為可讀，其權限表示為：- --- r-- ---)
chmod ugo+rw aaa(給用戶，組，其它用戶或組設置權限為讀寫，權限表示為：- rw- rw- rw-)
如果aaa具有滿權限- rwx rwx rwx。
chmod u-x aaa(去掉用戶可執(zhí)行權限，權限表示為：- rw- rwx rwx)
如果要給aaa賦予制定權限- rwx r-x r-x，命令為：
chmod u=rwx，go=rx aaa
11、makefile文件的作用是什么?
一個工程中的源文件不計其數(shù)，其按類型、功能、模塊分別放在若干個目錄中。makefile定義了一系列的規(guī)則來指定哪些文件需要先編譯，哪些文件需要后編譯，哪些文件需要重新編譯，甚至于進行更復雜的功能操作。因為makefile就像一個Shell腳本一樣，其中也可以執(zhí)行操作系統(tǒng)的命令。makefile帶來的好處就是——“自動化編譯”。一旦寫好，只需要一個make命令，整個工程完全自動編譯，極大地提高了軟件開發(fā)的效率。make是一個命令工具，是一個解釋makefile中指令的命令工具。一般來說，大多數(shù)的IDE都有這個命令，比如：Delphi的make，Visual C++的nmake，Linux下GNU的make?？梢?，makefile都成為了一種在工程方面的編譯方法。
12、簡術OSI的物理層Layer1，鏈路層Layer2，網(wǎng)絡層Layer3的任務。
網(wǎng)絡層：通過路由選擇算法，為報文或分組通過通信子網(wǎng)選擇最適當?shù)穆窂健?/p>
鏈路層：通過各種控制協(xié)議，將有差錯的物理信道變?yōu)闊o差錯的、能可靠傳輸數(shù)據(jù)幀的數(shù)據(jù)鏈路。
物理層：利用傳輸介質為數(shù)據(jù)鏈路層提供物理連接，實現(xiàn)比特流的透明傳輸。
13、什么是中斷?中斷時CPU做什么工作?
中斷是指在計算機執(zhí)行期間，系統(tǒng)內發(fā)生任何非尋常的或非預期的急需處理事件，使得CPU暫時中斷當前正在執(zhí)行的程序而轉去執(zhí)行相應的事件處理程序。待處理完畢后又返回原來被中斷處繼續(xù)執(zhí)行或調度新的進程執(zhí)行的過程。
14、你知道操作系統(tǒng)的內容分為幾塊嗎?什么叫做虛擬內存?他和主存的關系如何?內存管理屬于操作系統(tǒng)的內容嗎?
操作系統(tǒng)的主要組成部分：進程和線程的管理，存儲管理，設備管理，文件管理。虛擬內存是一些系統(tǒng)頁文件，存放在磁盤上，每個系統(tǒng)頁文件大小為4K，物理內存也被分頁，每個頁大小也為4K，這樣虛擬頁文件和物理內存頁就可以對應，實際上虛擬內存就是用于物理內存的臨時存放的磁盤空間。頁文件就是內存頁，物理內存中每頁叫物理頁，磁盤上的頁文件叫虛擬頁，物理頁+虛擬頁就是系統(tǒng)所有使用的頁文件的總和。
15、線程是否具有相同的堆棧?dll是否有獨立的堆棧?
每個線程有自己的堆棧。
dll是否有獨立的堆棧?這個問題不好回答，或者說這個問題本身是否有問題。因為dll中的代碼是被某些線程所執(zhí)行，只有線程擁有堆棧。如果dll中的代碼是exe中的線程所調用，那么這個時候是不是說這個dll沒有獨立的堆棧?如果dll中的代碼是由dll自己創(chuàng)建的線程所執(zhí)行，那么是不是說dll有獨立的堆棧?
以上講的是堆棧，如果對于堆來說，每個dll有自己的堆，所以如果是從dll中動態(tài)分配的內存，最好是從dll中刪除;如果你從dll中分配內存，然后在exe中，或者另外一個dll中刪除，很有可能導致程序崩潰。
16、什么是緩沖區(qū)溢出?有什么危害?其原因是什么?
緩沖區(qū)溢出是指當計算機向緩沖區(qū)內填充數(shù)據(jù)時超過了緩沖區(qū)本身的容量，溢出的數(shù)據(jù)覆蓋在合法數(shù)據(jù)上。
危害：在當前網(wǎng)絡與分布式系統(tǒng)安全中，被廣泛利用的50%以上都是緩沖區(qū)溢出，其中最著名的例子是1988年利用fingerd漏洞的蠕蟲。而緩沖區(qū)溢出中，最為危險的是堆棧溢出，因為入侵者可以利用堆棧溢出，在函數(shù)返回時改變返回程序的地址，讓其跳轉到任意地址，帶來的危害一種是程序崩潰導致拒絕服務，另外一種就是跳轉并且執(zhí)行一段惡意代碼，比如得到shell，然后為所欲為。通過往程序的緩沖區(qū)寫超出其長度的內容，造成緩沖區(qū)的溢出，從而破壞程序的堆棧，使程序轉而執(zhí)行其它指令，以達到攻擊的目的。
造成緩沖區(qū)溢出的主原因是程序中沒有仔細檢查用戶輸入的參數(shù)。
17、什么是死鎖?其條件是什么?怎樣避免死鎖?
死鎖的概念：在兩個或多個并發(fā)進程中，如果每個進程持有某種資源而又都等待別的進程釋放它或它們現(xiàn)在保持著的資源，在未改變這種狀態(tài)之前都不能向前推進，稱這一組進程產生了死鎖。通俗地講，就是兩個或多個進程被無限期地阻塞、相互等待的一種狀態(tài)。
死鎖產生的原因主要是：? 系統(tǒng)資源不足;? 進程推進順序非法。
產生死鎖的必要條件：
(1)互斥(mutualexclusion)，一個資源每次只能被一個進程使用;
(2)不可搶占(nopreemption)，進程已獲得的資源，在未使用完之前，不能強行剝奪;
(3)占有并等待(hold andwait)，一個進程因請求資源而阻塞時，對已獲得的資源保持不放;
(4)環(huán)形等待(circularwait)，若干進程之間形成一種首尾相接的循環(huán)等待資源關系。
這四個條件是死鎖的必要條件，只要系統(tǒng)發(fā)生死鎖，這些條件必然成立，而只要上述條件之一不滿足，就不會發(fā)生死鎖。
死鎖的解除與預防：理解了死鎖的原因，尤其是產生死鎖的四個必要條件，就可以最大可能地避免、預防和解除死鎖。所以，在系統(tǒng)設計、進程調度等方面注意如何不讓這四個必要條件成立，如何確定資源的合理分配算法，避免進程永久占據(jù)系統(tǒng)資源。此外，也要防止進程在處于等待狀態(tài)的情況下占用資源。因此，對資源的分配要給予合理的規(guī)劃。
死鎖的處理策略：鴕鳥策略、預防策略、避免策略、檢測與恢復策略。
1、程序和進程
進程由兩個部分組成：1)操作系統(tǒng)用來管理進程的內核對象。內核對象也是系統(tǒng)用來存放關于進程的統(tǒng)計信息的地方。2)地址空間。它包含所有可執(zhí)行模塊或DLL模塊的代碼和數(shù)據(jù)。它還包含動態(tài)內存分配的空間。如線程堆棧和堆分配空間。
定義
使用系統(tǒng)運行資源情況
程序
計算機指令的集合，它以文件的形式存儲在磁盤上。程序是靜態(tài)實體（passive Entity），在多道程序系統(tǒng)中，它是不能獨立運行的，更不能與其他程序并發(fā)執(zhí)行。
不使用【程序不能申請系統(tǒng)資源，不能被系統(tǒng)調度，也不能作為獨立運行的單位，因此，它不占用系統(tǒng)的運行資源】。
進程
通常被定義為一個正在運行的程序的實例，是一個程序在其自身的地址空間中的一次執(zhí)行活動。
定義：進程是進程實體（包括：程序段、相關的數(shù)據(jù)段、進程控制塊PCB）的運行過程，是系統(tǒng)進行資源分配和調度的一個獨立單位。
使用【進程是資源申請、調度和獨立運行的單位，因此，它使用系統(tǒng)中的運行資源?！?/p>
2、進程與線程
如果說操作系統(tǒng)引入進程的目的是為了提高程序并發(fā)執(zhí)行，以提高資源利用率和系統(tǒng)吞吐量。那么操作系統(tǒng)中引入線程的目的，則是為了減少進程并發(fā)執(zhí)行過程中所付出的時空開銷，使操作系統(tǒng)能很好的并發(fā)執(zhí)行。
進程process定義了一個執(zhí)行環(huán)境，包括它自己私有的地址空間、一個句柄表，以及一個安全環(huán)境;線程則是一個控制流，有他自己的調用棧call stack，記錄了它的執(zhí)行歷史。
線程由兩個部分組成：1)線程的內核對象，操作系統(tǒng)用它來對線程實施管理。內核對象也是系統(tǒng)用來存放線程統(tǒng)計信息的地方。2)線程堆棧，它用于維護線程在執(zhí)行代碼時需要的所有參數(shù)和局部變量。當創(chuàng)建線程時，系統(tǒng)創(chuàng)建一個線程內核對象。該線程內核對象不是線程本身，而是操作系統(tǒng)用來管理線程的較小的數(shù)據(jù)結構?？梢詫⒕€程內核對象視為由關于線程的統(tǒng)計信息組成的一個小型數(shù)據(jù)結構。
進程與線程的比較如下：
比較
進程
線程
活潑性
不活潑（只是線程的容器）
活潑
地址空間
系統(tǒng)賦予的獨立的虛擬地址空間（對于32位進程來說，這個地址空間是4GB）
在進程的地址空間執(zhí)行代碼。線程只有一個內核對象和一個堆棧，保留的記錄很少，因此所需要的內存也很少。因為線程需要的開銷比進程少
調度
僅是資源分配的基本單位
獨立調度、分派的基本單位
并發(fā)性
僅進程間并發(fā)（傳統(tǒng)OS）
進程間、線程間并發(fā)
擁有資源
資源擁有的基本單位
基本上不擁有資源
系統(tǒng)開銷
創(chuàng)建、撤銷、切換開銷大
僅保存少量寄存器內容，開銷小。
3、進程同步
進程同步的主要任務：是對多個相關進程在執(zhí)行次序上進行協(xié)調，以使并發(fā)執(zhí)行的諸進程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。
同步機制遵循的原則：
(1)空閑讓進;
(2)忙則等待(保證對臨界區(qū)的互斥訪問);
(3)有限等待(有限代表有限的時間，避免死等);
(4)讓權等待，(當進程不能進入自己的臨界區(qū)時，應該釋放處理機，以免陷入忙等狀態(tài))。
4、進程間的通信是如何實現(xiàn)的?
進程通信，是指進程之間的信息交換(信息量少則一個狀態(tài)或數(shù)值，多者則是成千上萬個字節(jié))。因此，對于用信號量進行的進程間的互斥和同步，由于其所交換的信息量少而被歸結為低級通信。
所謂高級進程通信指：用戶可以利用操作系統(tǒng)所提供的一組通信命令傳送大量數(shù)據(jù)的一種通信方式。操作系統(tǒng)隱藏了進程通信的實現(xiàn)細節(jié)?；蛘哒f，通信過程對用戶是透明的。
高級通信機制可歸結為三大類：
(1)共享存儲器系統(tǒng)(存儲器中劃分的共享存儲區(qū));實際操作中對應的是“剪貼板”(剪貼板實際上是系統(tǒng)維護管理的一塊內存區(qū)域)的通信方式，比如舉例如下：word進程按下ctrl+c，在ppt進程按下ctrl+v，即完成了word進程和ppt進程之間的通信，復制時將數(shù)據(jù)放入到剪貼板，粘貼時從剪貼板中取出數(shù)據(jù)，然后顯示在ppt窗口上。
(2)消息傳遞系統(tǒng)(進程間的數(shù)據(jù)交換以消息(message)為單位，當今最流行的微內核操作系統(tǒng)中，微內核與服務器之間的通信，無一例外地都采用了消息傳遞機制。應用舉例：郵槽(MailSlot)是基于廣播通信體系設計出來的，它采用無連接的不可靠的數(shù)據(jù)傳輸。郵槽是一種單向通信機制，創(chuàng)建郵槽的服務器進程讀取數(shù)據(jù)，打開郵槽的客戶機進程寫入數(shù)據(jù)。
(3)管道通信系統(tǒng)(管道即：連接讀寫進程以實現(xiàn)他們之間通信的共享文件(pipe文件，類似先進先出的隊列，由一個進程寫，另一進程讀))。實際操作中，管道分為：匿名管道、命名管道。匿名管道是一個未命名的、單向管道，通過父進程和一個子進程之間傳輸數(shù)據(jù)。匿名管道只能實現(xiàn)本地機器上兩個進程之間的通信，而不能實現(xiàn)跨網(wǎng)絡的通信。命名管道不僅可以在本機上實現(xiàn)兩個進程間的通信，還可以跨網(wǎng)絡實現(xiàn)兩個進程間的通信。
同一機器兩個進程間通信
跨網(wǎng)絡通信
剪貼板Clipboard
可以
不可以
匿名管道Pipe
可以
不可以
命名管道（點對點單一通信，數(shù)據(jù)量可較大）Namedpipe
可以
可以
郵槽（一對多，數(shù)據(jù)量較小，424字節(jié)以下）Mailslot
可以
可以
5、線程同步
根據(jù)用戶模式及內核模式下的同步方式的不同，分類及對比如下：
內核對象/
非內核對象
含義
缺點
適用
關鍵代碼段（臨界區(qū)）CriticalSection
非內核對象，工作在用戶方式下，為用戶模式對象
從程序代碼的角度來控制線程的并發(fā)性
1.因為在等待進入關鍵代碼段時無法設定超時值，所以其很容易進入死鎖狀態(tài)。2.不能跨進程使用。
單個進程中線程間的同步（同步速度快）
事件對象Event
內核對象
所有內核對象中最基本的。
速度較慢（相比用戶模式實現(xiàn)線程同步）
多個進程間的各個線程間實現(xiàn)同步
互斥對象Mutex
內核對象
代表對一個資源的獨占式訪問
信號量
Semaphore
內核對象
使用計數(shù)器來控制程序對一個共享資源的訪問
由于進程同步產生了一系列經典的同步問題“生產者-消費者”問題，“哲學家進餐”問題，“讀者-寫者”問題。
常見的操作系統(tǒng)使用的文件系統(tǒng)整理
文件系統(tǒng)是操作系統(tǒng)用于明確磁盤或分區(qū)上的文件的方法和數(shù)據(jù)結構;即在磁盤上組織文件的方法。也指用于存儲文件的磁盤或分區(qū)，或文件系統(tǒng)種類。操作系統(tǒng)中負責管理和存儲文件信息的軟件機構稱為文件管理系統(tǒng)，簡稱文件系統(tǒng)。文件系統(tǒng)由三部分組成：與文件管理有關軟件、被管理文件以及實施文件管理所需數(shù)據(jù)結構。從系統(tǒng)角度來看，文件系統(tǒng)是對文件存儲器空間進行組織和分配，負責文件存儲并對存入的文件進行保護和檢索的系統(tǒng)。具體地說，它負責為用戶建立文件，存入、讀出、修改、轉儲文件，控制文件的存取，當用戶不再使用時撤銷文件等。
【FAT】：
常PC機使用的文件系統(tǒng)是FAT16。像基于MS-DOS，Win 95等系統(tǒng)都采用了FAT16文件系統(tǒng)。在Win 9X下，F(xiàn)AT16支持的分區(qū)最大為2GB。我們知道計算機將信息保存在硬盤上稱為“簇”的區(qū)域內。使用的簇越小，保存信息的效率就越高。在FAT16的情況下，分區(qū)越大簇就相應的要大，存儲效率就越低，勢必造成存儲空間的浪費。并且隨著計算機硬件和應用的不斷提高，F(xiàn)AT16文件系統(tǒ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ū)的啟動記錄被包含在一個含有關鍵數(shù)據(jù)的結構中，減少了計算機系統(tǒng)崩潰的可能性。
【NTFS】：
NTFS文件系統(tǒng)是一個基于安全性的文件系統(tǒng)，是Windows NT所采用的獨特的文件系統(tǒng)結構，它是建立在保護文件和目錄數(shù)據(jù)基礎上，同時照顧節(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是一個可恢復的文件系統(tǒng)。在NTFS分區(qū)上用戶很少需要運行磁盤修復程序。NTFS通過使用標準的事物處理日志和恢復技術來保證分區(qū)的一致性。發(fā)生系統(tǒng)失敗事件時，NTFS使用日志文件和檢查點信息自動恢復文件系統(tǒng)的一致性。
3、NTFS支持對分區(qū)、文件夾和文件的壓縮。任何基于Windows的應用程序對NTFS分區(qū)上的壓縮文件進行讀寫時不需要事先由其他程序進行解壓縮，當對文件進行讀取時，文件將自動進行解壓縮;文件關閉或保存時會自動對文件進行壓縮。
4、NTFS采用了更小的簇，可以更有效率地管理磁盤空間。在Win 2000的FAT32文件系統(tǒng)的情況下，分區(qū)大小在2GB～8GB時簇的大小為4KB;分區(qū)大小在8GB～16GB時簇的大小為8KB;分區(qū)大小在16GB～32GB時，簇的大小則達到了16KB。而Win 2000的NTFS文件系統(tǒng)，當分區(qū)的大小在2GB以下時，簇的大小都比相應的FAT32簇小;當分區(qū)的大小在2GB以上時(2GB～2TB)，簇的大小都為4KB。相比之下，NTFS可以比FAT32更有效地管理磁盤空間，最大限度地避免了磁盤空間的浪費。
5、在NTFS分區(qū)上，可以為共享資源、文件夾以及文件設置訪問許可權限。許可的設置包括兩方面的內容：一是允許哪些組或用戶對文件夾、文件和共享資源進行訪問;二是獲得訪問許可的組或用戶可以進行什么級別的訪問。訪問許可權限的設置不但適用于本地計算機的用戶，同樣也應用于通過網(wǎng)絡的共享文件夾對文件進行訪問的網(wǎng)絡用戶。與FAT32文件系統(tǒng)下對文件夾或文件進行訪問相比，安全性要高得多。另外，在采用NTFS格式的Win 2000中，應用審核策略可以對文件夾、文件以及活動目錄對象進行審核，審核結果記錄在安全日志中，通過安全日志就可以查看哪些組或用戶對文件夾、文件或活動目錄對象進行了什么級別的操作，從而發(fā)現(xiàn)系統(tǒng)可能面臨的非法訪問，通過采取相應的措施，將這種安全隱患減到最低。這些在FAT32文件系統(tǒng)下，是不能實現(xiàn)的。
6、在Win 2000的NTFS文件系統(tǒng)下可以進行磁盤配額管理。磁盤配額就是管理員可以為用戶所能使用的磁盤空間進行配額限制，每一用戶只能使用最大配額范圍內的磁盤空間。設置磁盤配額后，可以對每一個用戶的磁盤使用情況進行跟蹤和控制，通過監(jiān)測可以標識出超過配額報警閾值和配額限制的用戶，從而采取相應的措施。磁盤配額管理功能的提供，使得管理員可以方便合理地為用戶分配存儲資源，避免由于磁盤空間使用的失控可能造成的系統(tǒng)崩潰，提高了系統(tǒng)的安全性。
7、NTFS使用一個“變更”日志來跟蹤記錄文件所發(fā)生的變更。
【Ext2】：
Ext2是 GNU/Linux 系統(tǒng)中標準的文件系統(tǒng)，其特點為存取文件的性能極好，對于中小型的文件更顯示出優(yōu)勢，這主要得利于其簇快取層的優(yōu)良設計。
其單一文件大小與文件系統(tǒng)本身的容量上限與文件系統(tǒng)本身的簇大小有關，在一般常見的 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轉換成ext3并不復雜。
【Ext3】：
Ext3是一種日志式文件系統(tǒng)，是對ext2系統(tǒng)的擴展，它兼容ext2。日志式文件系統(tǒng)的優(yōu)越性在于：由于文件系統(tǒng)都有快取層參與運作，如不使用時必須將文件系統(tǒng)卸下，以便將快取層的資料寫回磁盤中。因此每當系統(tǒng)要關機時，必須將其所有的文件系統(tǒng)全部shutdown后才能進行關機。
如果在文件系統(tǒng)尚未shutdown前就關機 (如停電) 時，下次重開機后會造成文件系統(tǒng)的資料不一致，故這時必須做文件系統(tǒng)的重整工作，將不一致與錯誤的地方修復。然而，此一重整的工作是相當耗時的，特別是容量大的文件系統(tǒng)，而且也不能百分之百保證所有的資料都不會流失。
為了克服此問題，使用所謂‘日志式文件系統(tǒng) (Journal File System) ’。此類文件系統(tǒng)最大的特色是，它會將整個磁盤的寫入動作完整記錄在磁盤的某個區(qū)域上，以便有需要時可以回溯追蹤。
由于資料的寫入動作包含許多的細節(jié)，像是改變文件標頭資料、搜尋磁盤可寫入空間、一個個寫入資料區(qū)段等等，每一個細節(jié)進行到一半若被中斷，就會造成文件系統(tǒng)的不一致，因而需要重整。
然而，在日志式文件系統(tǒng)中，由于詳細紀錄了每個細節(jié)，故當在某個過程中被中斷時，系統(tǒng)可以根據(jù)這些記錄直接回溯并重整被中斷的部分，而不必花時間去檢查其他的部分，故重整的工作速度相當快，幾乎不需要花時間。
【Ext4】：
Linux kernel 自 2.6.28 開始正式支持新的文件系統(tǒng) Ext4。Ext4 是 Ext3 的改進版，修改了 Ext3 中部分重要的數(shù)據(jù)結構，而不僅僅像 Ext3 對 Ext2 那樣，只是增加了一個日志功能而已。Ext4 可以提供更佳的性能和可靠性，還有更為豐富的功能：
1、與 Ext3 兼容。執(zhí)行若干條命令，就能從 Ext3 在線遷移到 Ext4，而無須重新格式化磁盤或重新安裝系統(tǒng)。原有 Ext3 數(shù)據(jù)結構照樣保留，Ext4 作用于新數(shù)據(jù)，當然，整個文件系統(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 采用間接塊映射，當操作大文件時，效率極其低下。比如一個 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、多塊分配。當寫入數(shù)據(jù)到 Ext3 文件系統(tǒng)中時，Ext3 的數(shù)據(jù)塊分配器每次只能分配一個 4KB 的塊，寫一個 100MB 文件就要調用 25，600 次數(shù)據(jù)塊分配器，而 Ext4 的多塊分配器“multiblock allocator”(mballoc) 支持一次調用分配多個數(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、日志校驗。日志是最常用的部分，也極易導致磁盤硬件故障，而從損壞的日志中恢復數(shù)據(jù)會導致更多的數(shù)據(jù)損壞。Ext4 的日志校驗功能可以很方便地判斷日志數(shù)據(jù)是否損壞，而且它將 Ext3 的兩階段日志機制合并成一個階段，在增加安全性的同時提高了性能。
9、“無日志”(No Journaling)模式。日志總歸有一些開銷，Ext4 允許關閉日志，以便某些有特殊需求的用戶可以借此提升性能。
10、在線碎片整理。盡管延遲分配、多塊分配和 extents 能有效減少文件系統(tǒng)碎片，但碎片還是不可避免會產生。Ext4 支持在線碎片整理，并將提供 e4defrag 工具進行個別文件或整個文件系統(tǒng)的碎片整理。
11、inode 相關特性。Ext4 支持更大的 inode，較之 Ext3 默認的 inode 大小 128 字節(jié)，Ext4 為了在 inode 中容納更多的擴展屬性(如納秒時間戳或 inode 版本)，默認 inode 大小為 256 字節(jié)。Ext4 還支持快速擴展屬性(fast extended attributes)和 inode 保留(inodes reservation)。
12、持久預分配(Persistent preallocation)。P2P 軟件為了保證下載文件有足夠的空間存放，常常會預先創(chuàng)建一個與所下載文件大小相同的空文件，以免未來的數(shù)小時或數(shù)天之內磁盤空間不足導致下載失敗。Ext4 在文件系統(tǒng)層面實現(xiàn)了持久預分配并提供相應的 API(libc 中的 posix_fallocate())，比應用軟件自己實現(xiàn)更有效率。
13、默認啟用 barrier。磁盤上配有內部緩存，以便重新調整批量數(shù)據(jù)的寫操作順序，優(yōu)化寫入性能，因此文件系統(tǒng)必須在日志數(shù)據(jù)寫入磁盤之后才能寫 commit 記錄，若 commit 記錄寫入在先，而日志有可能損壞，那么就會影響數(shù)據(jù)完整性。Ext4 默認啟用 barrier，只有當 barrier 之前的數(shù)據(jù)全部寫入磁盤，才能寫 barrier 之后的數(shù)據(jù)。(可通過 “mount -o barrier=0” 命令禁用該特性。)
【ZFS】：
ZFS源自于Sun Microsystems為Solaris操作系統(tǒng)開發(fā)的文件系統(tǒng)。ZFS是一個具有高存儲容量、文件系統(tǒng)與卷管理概念整合、嶄新的磁盤邏輯結構的輕量級文件系統(tǒng)，同時也是一個便捷的存儲池管理系統(tǒng)。ZFS是一個使用CDDL協(xié)議條款授權的開源項目。
【HFS】：
1、HFS文件系統(tǒng)概念
分層文件系統(tǒng)(Hierarchical File System，HFS)是一種由蘋果電腦開發(fā)，并使用在Mac OS上的文件系統(tǒng)。最初被設計用于軟盤和硬盤，同時也可以在在只讀媒體如CD-ROM上見到。
2、HFS文件系統(tǒng)開發(fā)過程
HFS首次出現(xiàn)在1985年9月17日，作為Macintosh電腦上新的文件系統(tǒng)。它取代只用于早期Mac型號所使用的平面文件系統(tǒng)Macintosh File System(MFS)。因為Macintosh電腦所產生的數(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對磁盤空間的地址定位效率低下，并加入了其它的改進。當前版本的Mac OS仍舊支持HFS，但從Mac OS X開始HFS卷不能作為啟動用。
3、構成方式
分層文件系統(tǒng)把一個卷分為許多512字節(jié)的“邏輯塊”。這些邏輯塊被編組為“分配塊”，這些分配塊可以根據(jù)卷的尺寸包含一個或多個邏輯塊。HFS對地址分配塊使用16位數(shù)值，分配塊的最高限制數(shù)量是65536。
組成一個HFS卷需要下面的五個結構：
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)是當最初總目錄文件中三個擴展占用后，另外一個包含額外擴展記錄的分配塊對應信息的B_tree。
內核怎樣管理你的內存
在分析了進程的虛擬地址布局，我們轉向內核以及他管理用戶內存的機制。下圖是gonzo的例子：
Linux的進程在內核中是由task_struct進程描述符實現(xiàn)的，task_struct的mm字段指向內存描述符mm_struct，他是進程的一個內存執(zhí)行摘要。如上圖所示，mm_struct存儲了內存各個段的開始和結束地址、進程所使用的內存頁面數(shù)(rss代表常駐集合大小)、使用的虛擬地址空間總數(shù)等等。在內存描述符中我們也可以找到兩個用于管理進程內層的字段：虛擬內存集合和頁表。Gonzo的內存區(qū)域如下圖：
每個虛擬內存區(qū)域(VMA)是一個虛擬地址空間上連續(xù)的區(qū)域;這些區(qū)域不會彼此覆蓋。Vm_area_struct結構描述了一個內存區(qū)域，包括他的開始和技術地址、flags字段指定了他的行為和訪問權限，vm_file字段指定了該區(qū)域映射的實際文件。一個沒有映射文件的VMA成為匿名的。除了內存映射段以外，上面的每個內存段(堆、棧等等)相當于一個單獨的VMA。這不是必須的，盡管在x86機器上通常是這樣。VMA不會關心他在哪個段里面。
一個進程的所有VMA以兩種方式存儲在他的內存描述符中，一種是以鏈表的方式存放在mmap字段，以開始虛擬地址進行了排序，另一種是以紅黑樹的方式存放，mm_rb字段為這顆紅黑樹的根。紅黑樹可以讓內核根據(jù)給定的虛擬地址快速地找到內存區(qū)域。當我們讀取文件/proc/pid_of_process/maps，內核僅僅是通過進程VMA的鏈接同時打印出每一個。
計算機組成
計算機的運行簡單理解為這三層：硬件即組成計算機的所有摸得見看得著的東西是計算機運行的基礎;應用程序即完成特定功能、目的的用戶程序是計算機的價值體現(xiàn);中間就是操作系統(tǒng)，連接了硬件和應用程序負責硬件調度、資源管理和分配(內存、文件、CPU等等)、安全等一系列功能。
硬件層
主要硬件包括CPU(算術、邏輯單元)、主存、輔助存儲、系統(tǒng)總線、I/O設備(即輸入輸出)。
CPU：
CPU本身(Processor)可以是單核、多核、多CPU架構，主要目的就是滿足日益增長的運算需求。單核比較簡單，多核(包括一CPU多核心和多CPU)立即涉及到核心之間高速緩存的共享，此處是CPU內置高速緩存非主存，進程之間寄存器數(shù)據(jù)的共享和進程處理器調度問題。
總線：
總線連接了所有的設備提供通訊的能力，注意設備之間同一時間的通信是會沖突的，這就要涉及到總線的決策，負責決策的可能是CPU或專有芯片。所有設備需要通信時要提交通信請求有CPU決定下一個通信的設備。
另外一個問題顯然連接到總線上的設備越多，沖突的幾率就越大效率越差。所以總線可以有多層總線設計，比如設置I/O總線所有的I/O設備都通過I/O總線和I/O控制器連接，I/O控制器則連接在系統(tǒng)總線上代理I/O的通信請求。
速度：
CPU飛快，其中CPU內置的一級高速緩存保持了和CPU同樣的速度但是容量極小，接下來可能存在二級、三級高速緩存;主存(內存)其次和CPU存在數(shù)量級上的差距;輔寸(多硬盤)的速度就不是一般的慢了，因為有機械運動，但是容量大很多;I/O設備多數(shù)慢的要死，但不是沒有快的(比如圖形、千兆以太網(wǎng)的速度是超過硬盤的)?？偠灾褪强斓奶F，賤的太慢，訪問快的斷電數(shù)據(jù)即失效，不失效的訪問慢，所以就有了多級存儲的設計。程序的運行必然是加載到主存的(內存)!
局部性：
多級存儲的設計得益于局限性能夠大幅提升性能。局限性本身分為時間局限性和空間局限性。時間局限性是說現(xiàn)在用到的指令很可能短時間內還會多次調用，空間局限性是現(xiàn)在調用的數(shù)據(jù)在輔寸上鄰接的塊很可能即將被用到。就是因為局限性的存在預讀取才有了市場(所以有了磁盤整理)，當然局限性是必然的——程序肯定趨向于統(tǒng)一存取、循環(huán)、分支邏輯肯定是指令的循環(huán)調用。——好的命中率決定了計算機的性能。
指令周期(取指周期)：
計算機中CPU始終是取指-》執(zhí)行的動作循環(huán)運行的，計算機從取指到完成指令的周期稱為取指周期。因此針對CPU的性能優(yōu)化有流水線和超標量體系結構，前者目的在于合理分割指令使取指和執(zhí)行能夠并行進行(預取指)，后者則通過相同的運算結構重復設置實現(xiàn)多條指令同時執(zhí)行(得益于指令的亂序執(zhí)行)。
I/O設備進化：
I/O設備一般較慢，極端點的比如鍵盤這貨簡直慢的沒法說。那么當程序需要讀取I/O數(shù)據(jù)時(如讀取一塊數(shù)據(jù)、監(jiān)聽鍵盤輸入)就會被I/O設備阻塞，這是最差的情況整個系統(tǒng)空轉直到I/O設備讀取數(shù)據(jù)完成。
于是有了可編程I/O設備——你可以定期問我準備好數(shù)據(jù)了沒，好了你就取沒好你就干別的去，也就是輪詢這法子還是非常慢因為CPU要定期過來問而且多數(shù)情況都是沒準備好空耗系統(tǒng)資源(進程切換)。
再后來有了中斷，前提是指令的運行是可被中斷和恢復的(現(xiàn)在當然都可以，把寄存器數(shù)據(jù)保存到緩存，完了再恢復嘛)，需要讀取的時候CPU發(fā)給I/O指令然后不理它了，需要讀取的進程(或線程)進入阻塞狀態(tài)換下一個進程來執(zhí)行，當I/O準備好數(shù)據(jù)后發(fā)送一個中斷信號給CPU，這時現(xiàn)在執(zhí)行的進程被中斷CPU會執(zhí)行一段中斷處理程序(通常很短)把之前阻塞的進程標記為Ready(可執(zhí)行)狀態(tài)，處理完中斷后恢復之前中斷的進程(或線程)繼續(xù)執(zhí)行。在當前進程執(zhí)行完或者超時中斷后(分時多道程序處理，超時也是一種中斷)，之前從阻塞中恢復的進程可能會被執(zhí)行(取決于進程調度，不一定是下一個時間片里也可能是下幾個時間片后或者干脆餓死了)。
再后來又有了DMA(直接存儲器訪問)，主要原因就是CPU很忙，你一個拷貝/傳輸整塊數(shù)據(jù)的動作就不要每塊數(shù)據(jù)都讓我來處理了，系統(tǒng)中多了一個專門的輔助芯片干這個事情。CPU下達指令后輔助芯片負責設備之間的數(shù)據(jù)直接傳輸。DMA模塊可以是總線中的一個模塊也可以是I/O模塊，但是仍然要占用總線(傳輸數(shù)據(jù))所以并不是不會對系統(tǒng)性能產生影響，至少DMA沖突時CPU要等待一個總線周期。
操作系統(tǒng)
看完硬件層(簡單看看，后面可能還要回頭)，再來看看操作系統(tǒng)層。最基本的元素肯定要包括進程、線程等等用于程序的執(zhí)行。
操作系統(tǒng)
操作系統(tǒng)目的：
方便：簡化了計算機的使用，無論是用戶還是開發(fā)者角度都極大的簡化了對計算機的使用。用戶角度提供了交互的能力，開發(fā)者角度提供了底層設備的接口、公共庫等等。
有效：提高計算機的利用效率。對于操作系統(tǒng)CPU運算、內存、輔存、I/O等等都是資源，如何能最大的利用資源是計算機要考慮的事情。(沒有操作系統(tǒng)的年代顯然效率非常低，同一時間只運行一個程序計算資源多數(shù)時間都在等待I/O設備、人等)。
擴展的能力：在不阻礙服務前提下開發(fā)、測試、加入新的計算機能力。比如安裝個程序、加個設備。
操作系統(tǒng)發(fā)展
串行處理：這是個久遠的年代(上世紀50年代也不算太遠哈),計算機一次只能運行一個程序，要通過輸入設備讀入程序(讀卡器吧)運行結束后再將結果輸出到打印機。這個年代是沒有操作系統(tǒng)的。
簡單批處理：這個算是操作系統(tǒng)的鼻祖吧?就是常駐內存的一個監(jiān)控程序，要運行的程序被管理員組織成一批，監(jiān)控程序從存儲器(卡片或磁帶)讀取要執(zhí)行的Job將處理器控制權轉交給程序運行結束后(成功或失敗)控制權返回監(jiān)控程序繼續(xù)讀入下一個任務。
簡單批處理節(jié)約了計算機調度和準備的時間——任務不再是一個一個的處理了，變成一批了。
多道程序批處理：現(xiàn)代操作系統(tǒng)進程切換之父?哈哈。由于內存的加大除了容納操作系統(tǒng)、一個程序以外還有足夠的空間容納第二、第三個程序，所以就有了同時運行多個程序的能力。在第一個程序被阻塞后(I/O等)，可以轉交控制權個第二、第三個程序。
多道程序批處理節(jié)約了CPU等待I/O等慢速設備的時間，這個效率的提升非?？陀^。
分時操作系統(tǒng)：注意關注在人的交互上。人肯定是比I/O還慢的設備了，由于早年計算機資源的稀缺當然要達到多人共用一臺機器的目的。分時操作系統(tǒng)把計算機資源做時間切片，用戶通過終端連接到計算機，每個中斷都獲取到時間切片內的計算資源，由于人是反應很鈍的，所以就像沒人都有一臺計算機服務一樣。
操作系統(tǒng)的幾張表
Memory table：記錄內存的使用情況，回收和分配內存時這里都會被更新。
I/O table：記錄I/O設備和通道的情況。
File table：文件系統(tǒng)的占用情況，文件是否存在，文件狀態(tài)。
Process table：管理進程。
進程和線程
進程
進程包括程序代碼和一組(set)數(shù)據(jù)，是程序運行的實體(應該能算作最小單元吧，線程能執(zhí)行的是一段邏輯，一個程序的啟動至少是一個或多個進程)。
進程的組成：
進程所有屬性的集合被稱為進程映像(Process Image)，這之中一共包括四部分：用戶程序(User Program)、數(shù)據(jù)(User Data)、棧(Stack)和進程控制塊(Process Control Block)。
用戶程序：要執(zhí)行的程序。
數(shù)據(jù)：用戶空間中可以被用戶修改的部分。比如進程數(shù)據(jù)、可修改程序。
Stack：每個進程都有一個或者多個棧用于保存參數(shù)、過程調用地址、系統(tǒng)調用地址。
進程控制塊：操作系統(tǒng)控制進程需要的數(shù)據(jù)。包含了進程的屬性，最基本的每個進程總要有個Id吧，還有進程狀態(tài)、當前寄存器的值、程序計數(shù)器、Stack的指針等等。
進程狀態(tài)切換
最起碼的兩個狀態(tài)：Ready、Running，進程自創(chuàng)建后進入Ready狀態(tài)也就是可以執(zhí)行的，這時的進程進入等待隊列知道進程調度輪到自己執(zhí)行時才能夠被分配資源進入執(zhí)行狀體Running。
進程的基本狀態(tài)一共五個，包括上面兩個以外還會有被阻塞的情況(I/O、等待生產者生產、信號量等等)所以存在Blocked狀態(tài)，進程創(chuàng)建過程中存在New狀態(tài)、進程運行終結后處于Exit狀態(tài)等待操作系統(tǒng)做進一步處理并銷毀進程。
進程狀態(tài)之間的切換可以參考圖中進程狀態(tài)部分，大體過程：進程被允許創(chuàng)建進入New狀態(tài)，這個過程中要分配進程Id、劃分內存區(qū)域、初始化PCB(Process control block)、連接和創(chuàng)建或擴展其它的數(shù)據(jù);上述過程完成以后進程可以運行了所以進入Ready狀態(tài)等待系統(tǒng)調度;終于等到自己運行了，進程為Running狀態(tài)這時候可能出現(xiàn)幾種情況。1，進程運行結束進入Exit狀態(tài)等待銷毀。2，進程運行超時重新進入Ready狀態(tài)等待下一次調度。3，進程被阻塞了進入Block狀態(tài)等待所需要的數(shù)據(jù)或信號準備好，重新喚醒進入Ready狀態(tài)。除此以外還有兩個掛起狀態(tài)，見下面的切換。
調度的示意圖參考進程調度示意子圖，其中一個改進是操作系統(tǒng)很可能為不同的中斷事件設立不同的阻塞隊列，以便提高效率。
進程切換(Swapping)：
說白了還是CPU計算資源寶貴和內存有限(內存在漲吃內存的程序也在漲)。為了能讓更多的進程可以同時執(zhí)行(實際上不是同時是調度)，程序運行中有很大一部分會被I/O阻塞——原因是I/O太慢了，所以即便你要的數(shù)據(jù)不多那這個取數(shù)的過程CPU也夠跑很多其它程序的了。所以導致的問題就是在內存中的進程都阻塞了，內存沒地方了，CPU依然閑的蛋疼，怎么辦?把硬盤上畫出一塊地兒(個人理解就是windows下的虛擬內存、Linux中的swap)，塞得比較久的那些進程你們先出去待會，換些后面排著的進來。
看到進程切換的子圖中除了五個狀態(tài)以外還有兩個掛起態(tài)(就緒/掛起、阻塞/掛起)就是這個情況。雖然把進程從硬盤換入換出這個開銷非常高，但是硬盤比起I/O設備還是快了很多，所以這一步是有價值的。
當然還有一個路子是虛擬內存的時候，這個稍晚的時候再扯進來。
進程執(zhí)行模式：
用戶模式和內核模式，這兩個模式還有多個別名不記錄了。這是出于操作系統(tǒng)安全考慮的，有些重要的指令就只有內核模式下才能被CPU執(zhí)行(硬件支持)，總不能任意來個程序什么事情都給他干吧。
有了執(zhí)行模式就算有模式的切換，比如進程要調用系統(tǒng)操作時(system call)就有可能從用戶模式切換到內核模式，system call執(zhí)行后也會在切換回去。
多線程定義
多線程是指進程內支持并發(fā)路徑執(zhí)行的能力。
與進程的關系
一個進程至少包含一個線程，當進程中存在多個線程的時各個線程可以共享進程內的資源。進程內的線程共享進程的用戶空間，操作系統(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 線程之間的切換消耗低于進程，特別是同一進程內的線程切換消耗更低。
l 線程間通信的效率比進程間通信要高，因為進城之間安全性問題需要隔離和互斥，同一進程內的線程可以共享進程資源而不需要提前獲取鎖。
線程同步
進程也涉及到同步，但是線程的同步更需要開發(fā)者注意。上面提到了線程共享進程的資源并且不需要獲取鎖，所以線程之間是沒有操作系統(tǒng)來保證隔離的。
線程類型
類型分為用戶級線程和內核級線程。用戶級線程即通過Lib創(chuàng)建的對操作系統(tǒng)是透明的，內核級線程是由操作系統(tǒng)創(chuàng)建的。
用戶級
內核級
通過線程庫創(chuàng)建，對操作系統(tǒng)不可見
由操作系統(tǒng)來管理
比內核級的線程更高效，不涉及模式切換
在線程切換時需要模式切換（因為是調用系統(tǒng)級的指令）
進程中同時只能有一個線程在運行，還是多段程序的思路
線程可以并發(fā)運行，特別指多核計算機
一旦被阻塞整個進程就被阻塞，也就是所有的線程都完蛋了
只會阻塞引起阻塞的線程
線程的四個應用場景
l 前后臺運算：即有UI和后臺運算的程序，你總不希望后臺數(shù)據(jù)運算時前面的UI界面就對用戶沒響應了吧?所以這里應該分開線程，后臺啟動單獨的線程運算，界面在不同的線程了所有能時時相應用戶的操作(哪怕只是提示計算中)。
l 異步計算：比如應對電路故障的實時備份功能，通過線程無論是在代碼量上還是開銷上都要比你編寫定時調度的功能要高效。
l 速度敏感的運算：多線程的計算機可以在計算一組數(shù)據(jù)的同時讀入下一組數(shù)據(jù)(當然弄幾個進程干這事兒也可以，但是開銷明顯更大)。
l 模塊化的程序架構：對于包含多個活動或者多個源頭和目標的輸入輸出程序，也許更容易使用多線程來設計和實現(xiàn)(就是每個線程干一攤子事兒，大家數(shù)據(jù)在一起自己取誰也別干涉誰)。
l 另外的比如Java程序，每個程序就是一個JVM的進程，至于這里面你起多少線程操作系統(tǒng)是不關心的。
并發(fā)性
競爭條件
競爭條件發(fā)生在多進程或者多線程同時修改同一個數(shù)據(jù)項的情況下，這時數(shù)據(jù)的最終結果依賴于各個進程(線程)執(zhí)行的順序(也就是結果不是唯一確定的了，比如同時修改變量b，P1執(zhí)行b = 1， P2執(zhí)行b = 2結果有競爭失敗者決定)。
臨界區(qū)
類似于b的這種資源稱為臨界資源(critical resource)，程序中操作臨界資源的程序段稱為臨界區(qū)(critical section)。就是說事兒肯定是出在臨界區(qū)里的。
互斥(multual exclusion)
多個進程嘗試進入同一個不可共享的資源的時候進程間需要是互斥的。這個不可共享的資源就是上面說的臨界資源，進入的程序段即臨界區(qū)。
互斥的要求：
l 互斥是系統(tǒng)強制的。
l 在臨界區(qū)外掛起的進程不能夠干涉其他進程。
l 請求臨界資源的進程不能被無限期的延遲，即不能有死鎖。
l 當沒有進程處于臨界區(qū)時，對臨界資源的請求必須立即分配。
l 互斥不能建立在任何關于進程相對速度或執(zhí)行順序的假設上。
l 一個進程在臨界區(qū)的時間應該是有限的。
進程交互
進程交互分三種情況：
l 進程間互不相認：比如多道程序設計，這些進程間存在共享資源但是彼此不知道，操作系統(tǒng)需要保證進程間的安全。
l 進程間簡介知道彼此：進程不知道彼此的ID，但是知道存在共享資源，進程間表現(xiàn)為合作。
l 進程間直接知道彼此：進程知道彼此的ID，存在共享資源，進程間表現(xiàn)為合作。
并發(fā)性的硬件支持
Interrupt disable
進程聲明自己的某一段程序是不可被中斷的，這招只在單個處理器的情況下有用，因為多個處理器則存在進程并行運行。
Compare & swap instruction
由CPU提供的原子指令，用測試值(test value)檢查內存單元(_ord)，如果相等就用給定的值設置內存單元(newvalue)，最終返回替換前的內存單元值。
使用：內存單元的初始值是0，多個進程執(zhí)行用0去測試并替換為1的指令，只有獲取到0的返回值的進程獲得了進入臨界區(qū)的資格，在離開臨界區(qū)前進程要重置內存單元值為0。
Exchange Instruction
有CPU提供的原子指令，用內存區(qū)域的值和一個寄存器的值交換。也就是只有換到寄存器初始值(換完以后檢查內存區(qū)域的值)的那個進程可以進入臨界區(qū)并在離開時重置寄存器。
硬件支持存在的弊端：
1，采用的是忙等待(busy waiting)的方式，CPU一直在進程間切換，效率低。
2，可能發(fā)生饑餓：總有一個二活人品差，搶不到而又沒有任何辦法干預。
3，可能存在死鎖：P1獲得了臨界資源但是同時P1被P2中斷了(P2優(yōu)先級高)，P2卻無法獲得被P1占有的臨界資源，P1同時得不到CPU的計算周期。
并發(fā)性的軟件支持
信號量(semaphore)
用于進程間傳遞信號的一個整數(shù)值。提供了三種操作初始化、信號加和信號減。只有0和1的信號量稱為二元信號量。減操作semwait用于阻塞一個進程(當信號量為0的時候阻塞)，加操作semsignal用于激活被阻塞的進程。、
生產者與消費者
生產者負責生產資源并加入到指定的緩存中，加入過程如果緩存已滿要阻塞生產者;消費者負責消費資源，如果緩存已空要避免消費者消費不存在的資源。
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)聽者(管程)
信號量的麻煩在于分布在程序的各個地方，一處錯誤就可能導致并發(fā)同步的錯誤。監(jiān)聽者提供了更完善的機制用于并發(fā)同步。參考監(jiān)聽者子圖。
監(jiān)聽者包括局部數(shù)據(jù)、條件變量和若干過程和等待隊列等，局部變量是被監(jiān)聽者機制保存的處于外部進程不能訪問或影響局部變量。
進程可以通過調用監(jiān)聽者的某一過程來進入監(jiān)聽者，但是同一時間只有一個進程處于監(jiān)聽者中(其它的在外面排隊，也就是進入隊列)。
監(jiān)聽者包含若干個條件變量，可以視條件變量為指向某一等待隊列的指針。
監(jiān)聽者提供了cwait和csignal方法，調用cwait(c)將在條件變量c上阻塞當前進程并使監(jiān)聽者可用，當前進程加入到條件變量c的等待隊列，調用csignal(c)將激活條件變量c的等待隊列上的進程并重新嘗試獲得監(jiān)聽者(一般是激活一個，也有可能是signalAll<對于條件變量不明確的情況激活所有的進程，使正確的進程運行其它的進程則因為未獲得條件變量再次阻塞>)。
除此監(jiān)聽者還提供了緊急隊列(也可能沒有)，對于進入到過程中的但最后沒有調用csignal的進程(它可能是在過程中阻塞了或者怎么完蛋了)有兩種處理方式：1，踢出去重新回到進入隊列和大家競爭。2，考慮到這個進程已經執(zhí)行了過程的部分邏輯有必要把它加入到緊急隊列中，監(jiān)聽者會在空閑后重新激活緊急隊列中的進程。
注意與信號量不同的是，在調用csignal(c)的時候如果條件變量c的等待隊列上沒有任何進程，那這個動作將不產生任何效果也不會累計下去。
生產者/消費者問題中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)點是除了進程間還可以適應分布式、共享的系統(tǒng)。消息傳遞最典型的兩個原語：send(source, message)和receive(destination, message)，其中可以是阻塞send、阻塞receive的也可以是不阻塞send阻塞receive的或者兩者都不阻塞。
消息的組成包括消息頭和消息體，消息頭包括目的地Id、消息格式、源Id、消息長度等信息，消息體則是消息內容。
尋址：消息可以是一對一的也可以是一對多、多對一或者多對多。
消息的排隊原則：默認情況下消息的接收應該是先進先出的對了，除此還要考慮緊急程度的優(yōu)先級設置。
生產者消費者的消息實現(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);
}
讀者和寫者問題
讀者/寫者問題不同于生產者消費者，一個資源可以同時有多個讀者但是同一時間只能有一個寫者。寫者和讀者不能同時獲取資源。
可以存在兩種類型的鎖
1，讀者優(yōu)先：文件未被占用或存在讀者時可以繼續(xù)加入讀者。
2，寫者優(yōu)先：文件被讀者占用后一旦出現(xiàn)寫者后續(xù)不能加入讀者。
可以基于信號量或者消息發(fā)送來解決，個人覺得能通過信號量的一定能通過Monitor解決。
死鎖和饑餓
死鎖：兩個或多個進程間都需要幾個臨界資源，但是各個進程持有其中一個臨界資源而嘗試獲取另外的臨界資源。
饑餓：可能是優(yōu)先級或者調度算法本身的原因導致某個進程始終無法獲取到臨界資源(競爭激烈)，雖然不存在死鎖但是這個進程做不了任何事情。
聯(lián)合進程圖(Join Process Diagram)
資源類型
可重用資源：比如I/O設備、文件等等，它們在同一時間只可以被一個進程使用，但是使用之后并不會因此而銷毀。
可消耗資源：比如存在I/O中的一段流數(shù)據(jù)，一旦被使用就不在存在了，但是可以被制造出來。除此以外還有信號、中斷、消息等等。
死鎖形成的條件
1.互斥
2.不存在搶占
3.持有和等待
4.形成了等待的環(huán)路
1~3：有可能產生死鎖但是并沒死鎖。只有4發(fā)生的時候死鎖才是真的產生了。
死鎖預防(protection)
死鎖的預防不同于死鎖避免，死鎖預防的目的在于干涉死鎖形成的條件1~4使得死鎖無法形成，往往導致的成本很高并且不很實用。
1.互斥：無法消除，有并發(fā)就有互斥。
2.搶占：這個可以做到有幾種途徑：a，當進程資源請求被拒絕時強制其釋放已占有的資源，在后續(xù)需要時可以重新申請。b，當進程申請已被其它進程占有的資源時系統(tǒng)允許其搶占。這兩種方法都有一個大前提就是資源狀態(tài)必須是容易保存和恢復的，否則就啥都沒了。
3.持有和等待：可以讓進程一次申請所有需要的資源，這將不會出現(xiàn)持有并等待的情況。但是這是在進程能夠預測它所使用的所有資源的前提下才成立的，并且效率很低。進程會在沒有用到資源前先占用資源。
4.形成環(huán)路：可以將各個資源類型定義成線性順序，只有占有了前面資源的進程才能進一步申請后續(xù)資源——同樣效率是硬傷。
死鎖避免(avoidance)
死鎖的避免是運行時發(fā)現(xiàn)進程的啟動或者請求會導致死鎖，從而采取不啟動或阻塞的措施。
1，如果進程的請求導致死鎖，則不啟動進程。這個比較難做到，因為它要求進程提前預知自己要用到的所有資源。
2，如果進程請求的資源可能導致死鎖，則不分配資源給進程(塞你一會兒)。這個是更可行的辦法。
方法2的運算如下：
OS中始終維護下列數(shù)據(jù)：
1，矩陣C(claim)為各個進程聲明的需要用到資源。
2，矩陣A(allocation)現(xiàn)在以分配給各個進程的情況。
3，向量R當前系統(tǒng)擁有的資源
當一個進程申請起源是，OS假設分配資源給它并更下上面的數(shù)據(jù)，之后查看是否會產生死鎖：
1，C - A得到矩陣P描述每個進程順利完成時要得到的剩余資源。
2，向量R - A中各個資源的合計值等到向量V當前可用的資源。
3，如果向量V中的資源不足以使P中任何一個進程得到滿足，那么即將發(fā)生死鎖，這時候拒絕進程的請求。
4，如果存在可完成的進程，把進程的資源加入到向量V中重復3步驟直到所有進程可完成或出現(xiàn)死鎖。
R1
R2
R3
P1
3
2
2
P2
6
1
3
P3
3
1
4
P4
4
2
2
矩陣C
R1
R2
R3
P1
1
0
0
P2
6
1
2
P3
2
1
1
P4
0
0
2
矩陣A
R1
R2
R3
P1
2
2
2
P2
0
0
1
P3
1
0
3
P4
4
2
0
矩陣C - A
R1
R2
R3
9
3
6
系統(tǒng)資源向量R
R1
R2
R3
0
1
1
當前可用資源向量V
由于當前可用資源可以滿足P2，所以可以加回P2的資源并重復步驟3。
死鎖的檢測和恢復
死鎖的檢測其實和上面的步驟是一樣的需要兩個矩陣：Q——進程請求資源(是排除已分配資源后)、A——進程已經分配的資源，一個向量V當前可用資源。
1，標記A中所有資源占用都為0的進程行。
2，初始化臨時的向量W是它等于V。
3，查找Q中為標記的i行，其中i行小于向量W。如果找不到i則種植算法。
4，如果找到i行，將i標記并把A中i行數(shù)據(jù)加回到W中。重復步驟3。
當算法結束時如果存在為標記的行則已經發(fā)生死鎖。
死鎖的恢復有點野蠻：
1，取消所有死鎖的進程。這是現(xiàn)代操作系統(tǒng)最常用的辦法。
2，回滾進程到之前一個檢查點(checkpoint)，重新啟動。操作系統(tǒng)需要具備回滾和恢復的能力，這樣仍然有死鎖的風險，但是并發(fā)的不確定性能保證死鎖最終不再發(fā)生。
3，連續(xù)取消死鎖進程直到最終不再出現(xiàn)死鎖。取消進程的順序依賴某種成本的原則，取消后重新調用死鎖檢測，如果仍然存在死鎖繼續(xù)取消。
4，連續(xù)搶占資源直到死鎖不再發(fā)生。同樣基于某些成本選擇的方法，資源搶占后重新調用死鎖檢測，一個被搶占資源的進程需要回滾到獲取該資源前的檢查點。
3、4步驟可以考慮一下原則：
l 目前消耗處理器時間最少。
l 目前為止產生的輸出最少
l 預計剩下的時間最長。
l 目前位置分配的資源總量最少。
l 優(yōu)先級最低。
哲學家就餐問題
一個屋子里有5個哲學家他們一天中除了睡覺只做思考和吃飯兩件事情，屋子里有一個桌子提供了哲學家喜歡的意大利粉，但是由于哲學家每天至思考導致身體退化他們需要用兩個叉子才能夠進食，他們坐下后會先拿起左手的叉子，然后拿起右手的叉子，之后進食吃飽以后放下兩把叉子。桌子周圍一共提供了五把椅子在每個椅子間提供了一把叉子，請為哲學家設計吃飯的算法。
如果5個哲學家同時餓了那么每個人都會拿到左手的叉子而死鎖。
哲學家吃飯問題可以通過信號量或者Monitor來處理。
內存管理
內存管理的目的：
l 重定位
l 保護
l 共享
l 邏輯組織
l 物理組織
內存分區(qū)
固定分區(qū)
分為大小相等和大小不等的固定分區(qū)策略。內存預先被劃分為固定大小的內存區(qū)域，進程可以安裝到大于等于自身的內存區(qū)域中。
存在內部碎片、大于最大內存區(qū)域的進程無法加載、內存利用不充分。
動態(tài)分區(qū)
動態(tài)的根據(jù)進程大小進行內存區(qū)域劃分，從而使得每個進程可以裝進和自己大小相等的內存區(qū)域。
存在外部碎片、需要定時壓縮外部碎片否則內存被割裂成很多小區(qū)域。
伙伴系統(tǒng)
采用二分法把內存等大小的兩塊區(qū)域(2^1)，再將其中一塊區(qū)域繼續(xù)二分為2^2層，逐次分配下去直到進程所需的大小M在2^(N+1) < M <2^(N)時保存進程。在進程釋放后再進行合并為較大的塊。
伙伴系統(tǒng)彌補了固定分區(qū)和動態(tài)分區(qū)的缺點，但是分頁和分段提供了更高級的分區(qū)方式。
重定位
因為進程換入換出后不一定仍加載到原來的內存位置，所以在程序中不可能確切的寫出實際的內存地址，而是通過偏移量來描述位置。
分頁
內存被劃分成許多等大小的幀，程序被劃分成與幀大小相等的若干頁。進程加載時需要將所有頁加載到內存中不一定連續(xù)的幀中。系統(tǒng)維護了頁表描述程序占用的頁和空閑頁表。
分頁沒有外部碎片，由于每個幀很小只有最后一幀是可能存在內部碎片的，所以只會出現(xiàn)很小的內部碎片。
頁的大小將直接影響性能。頁太小時：頁數(shù)多開始時頁面錯誤率很高，一段時間后由于頁面都已加入趨于平穩(wěn)，但是過小的頁將使每次讀寫的區(qū)塊很小。頁增大時：每一頁所包含的單元和相關單元越來越遠，局部性被削弱錯誤率增加，不斷增大時錯誤率又減小當頁大小等于進程P時不再有也錯誤，整個進程都在內存中。由此導致的問題是主存中能存入的進程越來越少。
頁表
操作系統(tǒng)為每個進程維護一個頁表描述進程中頁與幀的對應，邏輯地址分為了頁號和偏移量兩部分。一般情況下頁表的大小位頁的大小，頁表中每條記錄稱為頁表實體(PTE，page table entry)。
頁表可以是多級頁表，受制于頁大小的限制頁表的大小不能大于一頁(也不可能把巨大的頁表存放在主存中)，因此頁表做多級處理，根頁表始終在主存中，當次級頁表不在主存中時從輔存加載對應的頁表進主存。
根據(jù)頁表尋址
l 根據(jù)虛擬地址的頁號查找根頁表對應的幀號。
l 幀號+次級頁號合成次級頁表的地址找到對應的主存中幀號(如果存在的話)。
l 幀號+偏移量獲得實地址。
l 如果頁表中頁表實體的標志位標志當前頁沒有加載到主存中，發(fā)生頁錯誤中斷交給操作系統(tǒng)加載，進程被中斷處于Block狀態(tài)。
反向頁表(Inverter Page Table)
這是另一個可行的從虛地址獲取實地址的方案。
針對虛擬內存中頁表大小和虛擬地址范圍成比例的缺點(太大了)，反向頁表大小是固定的取決于主存中實際幀數(shù)。反響列表對虛擬地址的頁號做Hash運算取得Hash值，每一個Hash值對應一個數(shù)據(jù)項。數(shù)據(jù)項中記錄了進程ID和主存中幀號，通過幀號和偏移量就可以得到實地址了。由于多個虛擬地址可能映射到同一個Hash值，反向頁表需要維持鏈結構(當前項連接到同值的其它項)，所以進程ID和Hash值共同決定了虛擬地址對應的數(shù)據(jù)項。
反響的含義是指使用幀號而不是頁號來索引頁表項。
轉移后備緩沖器(TLB，Translation Lookside Buffer)
這是(虛擬內存地址轉換)硬件設備的一部分，相當于高速緩存。因為正常情況下虛擬地址的訪問要經過兩次主存——一次查找?guī)刂?，一次取?shù)據(jù)，轉移后備緩沖器緩存了頁號和幀地址的對應關系，只有在未命中的情況下采取訪問頁表查找?guī)枴?/p>
分段
簡單分段類似于簡單分頁，是將主存換分成大小不等的若干段，一個進程可以存儲在不連續(xù)的段中。分段的大小受限于分段最大長度。分段對程序員是可見的，它具有處理不斷增長的數(shù)據(jù)結構的能力以及支持共享和保護的能力。操作系統(tǒng)為每個進程維護一個段表。
分段存在外部碎片。
段頁結合
段頁結構是將程序劃分成段，每段保存在主存中對應的段里，在主存中段是由等大小的多個頁組成，當段最后不足一個頁時占用一個頁。
段頁結合的方式結合了分段和分頁的長處。在分段系統(tǒng)中由于每段有長度屬性，避免了程序不經意的越界訪問。進程間存在共享時多個進程可能持有同一個段的引用，頁結構也可以是實現(xiàn)類似的結構。
虛擬內存
當程序太大超過主存時就需要虛擬內存了，另外多道程序設計希望同時有盡可能多的進程加載到內存中，由于局部性的原理進程不需要全部加載進內存而是加載頻繁是用的區(qū)塊(稱為駐留集)，進程的其它部分保存著專門的輔存區(qū)域中。這個機制稱為虛擬內存。
系統(tǒng)抖動
當系統(tǒng)換出一塊內存區(qū)域后緊接著它有需要調用它，當這種情況頻繁發(fā)生的時候就導致了系統(tǒng)抖動。
讀取策略
分為請求式分頁和預約式分頁。請求式分頁是指當確實需要訪問到某頁時才把它加載進主存，預約式分頁是利用局部性原理將可能訪問到的當前請求的后續(xù)頁面加載到主存中。顯然預約式分頁更可取，但是會造成一定的浪費，在首次加載頁面和發(fā)生頁錯誤時適合采取預約式分頁。
放置策略
替換策略
替換策略是在加載新的頁時主存已滿需要替換出頁時決定那些頁將被替換的算法。
最佳(OPT，Optimal)
最少發(fā)生頁錯誤的算法，是優(yōu)先替換那些距離訪問最遠的頁面，需要預知頁的請求順序，本身是不可能實現(xiàn)的，但是可以作為參考比對其它策略。
最近最少使用
實際上是性能上最接近最佳的，但是仍難以實現(xiàn)。一種實現(xiàn)方式是給每個頁定義最近訪問的時間標簽，并在每次訪問后更新標簽，即使通過硬件支持成本和開銷仍然很高。
先進先出
依賴的理論是一個在很久以前加載的頁現(xiàn)在很可能已經不再訪問了，但是結果往往并非如此，這種策略很容易實現(xiàn)。
時鐘
環(huán)形的結構，通過指針指示當前所在位置，每個頁有一個使用為在訪問后標記其值為1。在需要替換時移動指針找到第一個標記位等于0的頁，指針每移動過一個頁就將這個頁的使用位清零。這樣如果沒有使用位為0的頁，當移動一圈以后最初的位置就會被清理。
一個改進是增加修改位——這也是必須的因為被修改的內存必然要寫入輔存?，F(xiàn)在有兩個指示位(訪問u，修改m)，算法如下：
1，查找u=0,m=0的頁，如果存在替換。這一步不清零訪問位。
2，如果1失敗，查找u=0，m=1的頁，并且這個過程中把訪問位清零。
3，如果2失敗，重復1，必要時重復2。
這樣好處是盡量不去替換發(fā)生數(shù)據(jù)修改的頁，少了寫回輔存的動作。
頁緩沖
也是避免系統(tǒng)抖動的一個策略，在主存中劃分出一定的緩存，用于保存那些被替換出的頁，根據(jù)局部性原理他們很可能近期會被訪問到。這個緩存是一個先入先出的隊列，一般頁面被訪問則直接從緩存中取回，如果一直沒有被訪問則最終會被擠出緩存。
駐留集管理(Resident Set)
虛擬內存中并非一個進程的所有部分都加載到主存中，程序運行過程中常駐內存的部分稱為駐留集。
駐留集的討論包括兩部分：駐留集分配(大小)和替換范圍。其中駐留集不可變的情況下替換算法已經在替換側路討論過了，駐留集可變的情況下將有所不同。
固定分配，局部范圍：每個進程的駐留集大小固定，每個進程一旦有一個頁換進來就要有一個頁換出去。需要根據(jù)程序的類型、優(yōu)先級等預先分配固定的大小，一旦過小則會保持較高的也錯誤率，如果較大則會占用資源，系統(tǒng)運行緩慢。
動態(tài)分配，全局范圍：根據(jù)進程運行的狀態(tài)調整駐留集的大小，如果頁錯誤率較高就適當加大駐留集，如果進程錯誤率一直保持較低水平說明程序的駐留集足夠大，可以適當削減一些也不會危及程序。全局范圍則可在所有進程間選擇要被替換出的頁，難點在于沒辦法確定該從哪里換出頁(即很可能換了不該換的)，解決辦法是頁緩沖。
動態(tài)分配，局部范圍：動態(tài)分配的效果同上，同時限制在進程自己的范圍內換出頁。在這個策略中要求對增加或減少駐留集大小進行評估并且要預估將來進程的情況，因此比簡單全局替換要復雜得多，但會提供更好的性能。
駐留集的替換策略
工作集策略(Working Set)
W(t，r)是關于t和r的函數(shù)，t是單位時間，r是窗口的寬度定義最近的r個單位時間中用到的頁的集合。即始終有W(t, r+1) 包含 W(t, r)。
工作集如下工作：
1，監(jiān)視每個進程的工作集。
2，周期性的從一個進程的駐留集中移除那些不在工作集中的頁，可以使用LRU策略。
3，只有當一個進程的工作集在主存時才可以執(zhí)行該進程(也就是駐留集包含了工作集)。
首先工作集是有效的，它利用率局部性原理，并未該原理設計了一個可以減少頁錯誤的內存管理策略。遺憾的是工作集存在很多問題：
1，現(xiàn)在不總是代表未來。
2，開銷太大，實現(xiàn)監(jiān)視每個進程不現(xiàn)實。
3，r最優(yōu)值未知。
但是工作集提供了參考，以下方案都是基于工作集思想的：
頁錯誤頻率(Page Fault Frequency，PFF)
主存中每個頁都有一個使用位(和時鐘的一樣作用)，操作系統(tǒng)記錄每個進程上一次頁錯誤的時間戳，如果發(fā)生了頁錯誤查看兩次頁錯誤的時間間隔如果小于閾值F，則加入新的頁(擴大駐留集)，否則清除所有使用位為0的頁，并把當前駐留集的頁使用位清零(縮小駐留集)。一個改進時加入使用兩個閾值——一個是駐留集增加的最高閾值，一個是駐留集減小的最低閾值(指頻率)。
頁面錯誤頻率是工作集的一個折衷，使用頁緩沖則可以達到相當好的效率。但是一個缺點是如果要轉移到新的局部性，會導致暫時的駐留集猛增。轉移到新的局部性是指，進程運行一段時間會切換到不同的邏輯指令部分，這時候局部性發(fā)生偏移，之前的駐留集不再需要。
采樣間隔可變工作集(Variable-interval Simple Working Set，VSWS)
針對PFF在內存高峰是來不及淘汰就得駐留集而導致進程頻繁換入換出等開銷(頻率不夠快)，采用動態(tài)的采樣率以期望盡快淘汰不需要的頁。
采用三個參數(shù)：L采樣區(qū)間最長寬度、M采樣區(qū)間最短快讀、Q采樣區(qū)間允許發(fā)生的頁錯誤數(shù)。VSWS和PFF一樣使用了頁的使用位，不同之處在于頻率的調整：
1，如果采樣時間超過了最長時間L，掛起進程并掃描使用位。
2，未達到最長時間，但是頁錯誤數(shù)超過了Q：
2.1，如果采樣間隔超過了M則掛起進程并掃描使用位。
2.2，如果采樣間隔沒有超過M，則一直等待采樣時間到達M進行掃描。
清除策略
清除策略目的在于確定何時講一個被修改的頁寫回輔存，分為請求式清除和預約式清除。
請求式清除采取動作的時間比較慢，影響性能。
預約式清除把需要修改的頁在需要用到它們的頁幀之前批量的寫回輔存。但是預約式清除寫回的頁在替換策略確定移除它之前仍有駐留在主存中，這期間可能再次發(fā)生修改導致清除無意義。
改進辦法是使用頁緩沖，分為兩個表存儲替換策略淘汰的頁。一個表寸修改的頁，一個表存未修改的頁，修改表中的頁被批量的寫回輔存，然后移動到未修改表中，未修改的表準備被擠出或者拿回。
加載控制
加載控制是關注多道程序設計的控制，系統(tǒng)中多道程序的數(shù)量稱為多道程序設計級。當多道程序數(shù)量過少時系統(tǒng)會比較空閑，過多時則會導致較高的頁錯誤率和抖動。
一個方案稱為L=S，L是頁錯誤間隔的平均時間，S是頁錯誤的平均處理時間，實驗表明當兩者接近時處理器使用率達到最大。
另一個方案是50%方案，即始終報紙分頁設備的使用率保持在50%左右，此時的處理器使用率也是最大。
另外策略是監(jiān)視時鐘(Clock)替換策略的環(huán)形緩存區(qū)指針移動速度，當移動速度低于某個閾值時可能是以下兩種情況之一：
1，很少發(fā)生頁錯誤，指針很少移動。
2，未被使用的駐留頁太多，指針不需要移動太多就可以找到可清除頁。
這兩種情況都表明進程的駐留集分配太大，可以增加多道程序設計級。另外還可以包括一個高閾值，如果指針移動速度超過這個閾值，則表明多道程序設計級太高，導致頻繁的頁錯誤，則要掛起進程以減少多道程序設計級。掛起進程的策略可以是：
l 最低優(yōu)先級
l 正在發(fā)生頁錯誤的進程(Faulting process)：原因是該進程很肯能駐留集還沒有形成，因此暫停它的代價很低。
l 最后被激活的進程：同樣很可能有最小的駐留集。
l 擁有最小駐留集的進程：重新裝入的代價最小，但是不利于駐留集較小的程序。
l 最大的進程：釋放較大的空間，不用很快又去取活其它的進程。
l 具有最大剩余執(zhí)行窗口的進程：類似于最少剩余時間策略，把已運行時間最短的掛起。
處理器調度
單處理器調度
調度類型
長程調度：決定是否將任務加入到待執(zhí)行的進程池中。
中程調度：決定進程的部分或全部加入到內存中(從Suspended到Ready)。
短程調度：決定哪一個就緒的進程將被執(zhí)行。
I/O調度：決定哪一個掛起的I/O請求將被可用的I/O設備執(zhí)行。
處理器調度關注的是短程調度。
調度準則
面向用戶
響應時間：從任務提交到開始有響應輸出的時間，一般的當處理器開始處理任務時即開始有輸出。
周轉時間：從任務提交到任務完成的時間。
最后期限：當可以指定最后期限時，操作系統(tǒng)降低其它目標，是滿足最后期限的作業(yè)數(shù)目的百分比達到最高。
可預測性：無論系統(tǒng)當前負載情況是繁重還是空閑，一個給定工作完成的總時間和總代價應該是相等的。
面向系統(tǒng)
吞吐量：單位時間內完成的進程數(shù)。
處理器利用率：處理器處于忙狀態(tài)的時間百分比。對于昂貴的共享系統(tǒng)來說這是一個重要的準則，對于個人系統(tǒng)則顯得不那么重要。
公平性：沒有來自用戶或其它系統(tǒng)的指導時操作系統(tǒng)應該公平的對待所有進程，沒有一個進程會處于饑餓狀態(tài)。
強制優(yōu)先級：當指定了優(yōu)先級后調度策略應優(yōu)先響應高優(yōu)先級的進程。
平衡資源：調度策略應是系統(tǒng)的所有資源保持忙碌的狀態(tài)，較少使用緊缺系統(tǒng)資源的進程應該得到照顧。
調度算法
歸一化周轉時間：它是指進程周轉時間與服務時間的比率，最小值是1.0.該值表示進程的相對延遲，典型的進程的執(zhí)行時間越長可容忍的延遲越長。
先來先服務(FCFS)：沒有優(yōu)先級和搶占，所有進程按照加入的順序執(zhí)行。這樣的調度偏向于執(zhí)行時間長的進程。FCFS策略本身對操作系統(tǒng)不是很有吸引力，但是它經常和優(yōu)先級系統(tǒng)配合使用產生有價值的調度策略。
輪轉(Round Robin)：對處理器資源進行時間分片，依次分配相同的時間資源給每個就緒的進程。輪轉的時間片最好略大于一次典型交互的時間，當時間片足夠大時退化為FCFS策略。
輪轉增加了處理時鐘中斷、進程切換和分配函數(shù)的開銷，因此時間片不應該過短。該策略對短執(zhí)行時間的進程有所改善，但是一個問題是進程分為I/O密集型和處理器密集型，由于I/O密集型進程經常被I/O中斷，所以輪轉策略傾向于處理器密集型。
一個改善的策略是虛擬輪轉法(Virtual Round Robin)，它增加了一個I/O隊列，當一個進程被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)中任務加入時程序員給出任務的估計時間，如果任務執(zhí)行時間遠遠超過給出的估計時間它將被廢棄。在生產環(huán)境中有大量的重復任務，系統(tǒng)將監(jiān)控每次任務執(zhí)行的時間以估計執(zhí)行時間，最簡單的公式是s=(各次時間和)/n，一個避免每次求和的優(yōu)化是s=S(n-1) + Tn/n，上述公式每次執(zhí)行的權值是相同的，典型情況下我們希望最近的執(zhí)行情況有更大的權值Sn+1 = aTn + (1-a)Sn。
最少剩余時間(SRT，shortest remain time)：是SPN的改進版本增加了搶占機制，在不斷有短進程加入的情況下長進程可能處于饑餓狀態(tài)。
最高相應比優(yōu)先(HRRN，Highest Response Rapid Next)：使用公式(w+s)/s，其中w是等待時間，s是服務時間。操作系統(tǒng)始終選擇具有最高相應比的進程，同樣需要估計和記錄進程的服務時間。該策略非常具有吸引力，當偏向短進程時，長進程由于得不到處理響應比不斷增加。
反饋：不想SPN、STR、HRRN策略那樣需要估計時間，反饋策略傾向于短進程，它具備多個隊列Q1~Qn，當進程加入時處于Q1隊列中，采用FCFS的順序服務隊列中的每個進程，當進程允許超過時間閾值時中斷并加入到下一級隊列中Q2，依次類推。Q1具有最高的優(yōu)先級，只有Q1中不存在進程是才執(zhí)行下一級的隊列。這樣可能導致的問題是過長的隊列可能加入到Qn隊列后處于饑餓狀態(tài)，因此要見識進程的等待時間，如果超過一定長度則重新調入到Q1中。
多處理器調度
多處理器調度關注的類型
粒度
無約束并行性：進程之間沒有顯示的同步，每個進程都是一個單獨的程序。無約束并行可能達到每個用戶都像是使用單獨的計算機或工作站。
粗粒度和非常粗粒度并行性：進程之間存在這同步，但是在一個非常粗淺的級別上，這種情況可以簡單的處理成一組運行在多道程序單處理器的并發(fā)進程，在多處理器系統(tǒng)是允許的軟件進行很少或者不進行改動就可以支持。
中等粒度并行性：應用程序可以被進程中一組線程有效的實現(xiàn)，這種情況下程序員需要顯示的指定潛在的同步性，應用程序之間需要高程度的合作與交互。
細粒度并行性：代表著比線程間更加復雜的同步情況，迄今為止仍是特殊的未被分割的領域。
進程調度
集中調度or對等調度：
集中調度即調度中存在主處理器，所有的任務分發(fā)由主處理器來完成，這種情況下主處理器可能成為系統(tǒng)的瓶頸。
單處理器使用多道程序設計：
與單處理器性能的不同：
多個處理器系統(tǒng)中由于一個長進程在單個處理器上執(zhí)行時，其它的進程可以分配到另外的處理器上因此復雜的調度策略不再顯得非常重要，調度策略的開銷可能成為性能損失。FCFS策略變得可接受。
線程調度
負載分配：
提供全局隊列，每個處理器只要空閑就從隊列中取任務執(zhí)行。
優(yōu)點是：負載均勻的分配給處理器，不存在空閑的處理器;不需要集中調度;可以使用單處理的任何一種調度方案進行分配。
缺點是：中心隊列占居了必須互斥訪問的存儲器區(qū)域，因此多處理器同時查找時會成為瓶頸，當只有幾十個處理器時不是大問題，但是上百個處理器時就會出現(xiàn)瓶頸。被搶占的線程可能在不同的處理器上執(zhí)行，如果每個處理器都配有高速緩存的話那么命中率將非常低。如果進程的所有線程都視為在公共線程池中那么進程的線程可能不會同時被處理，當線程間存在高度合作時則出現(xiàn)瓶頸。
組調度：
一組相關的線程基于一對一的原則，同時分配到一組處理器上去。
優(yōu)點：如果緊密相關的進程并行執(zhí)行那么同步阻塞可能減少，從進程推廣到線程組調度把一個進程所有的線程視為相關的;調度開銷可能減少，因為進程內線程間可能相關如果一個線程在高速允許，而它以來的線程沒有運行就會出現(xiàn)阻塞和調度。
缺點：組調度同一時間調度一個進程中相關線程，某些進程的特性可能至適應單線程允許將會出現(xiàn)其它處理器空閑的情況，解決辦法是把若干單線程的進程視為一組允許。
專用處理器分配：
每個程序執(zhí)行時被分配給一組處理器，處理器個數(shù)與進程的線程數(shù)相等，當進程執(zhí)行完后處理器返回到處理器池中等待處理其它任務。這個策略看似是極端浪費的，它會等到進程運行結束才將處理器分配給其它的進程使用，而一旦一個線程被I/O阻塞執(zhí)行它的處理器將空閑。
采用這個策略的原因：
1，高度并行的系統(tǒng)中有數(shù)十或者數(shù)百個處理，每個處理器只占系統(tǒng)總代價的一小部分，處理器利用率不再是衡量有效性或性能的重要因素。
2，一個程序的生命周期里避免進程切換會加快程序運行。
動態(tài)調度：
執(zhí)行期間進程的線程數(shù)可以改變。某些應用程序可能提供了語言和系統(tǒng)工具允許動態(tài)的改變進程中的線程數(shù)目。提供了一種操作系統(tǒng)和應用程序共同進行調度決策的方法。
當一個作業(yè)請求一個或多個處理器時：
1，如果有空閑處理器分配滿足它們需求。
2，否則如果作業(yè)新到達，從當前已分配多個處理器的作業(yè)中分出一個處理器給它。
3，如果都不滿足那么作業(yè)處于未完成狀態(tài)直到有空閑的處理器或者改作業(yè)廢除它的請求。
4，當釋放一個或多個處理器時為這些處理器掃描當前未滿足的請求隊列，給每個沒有分配處理器的作業(yè)分配一個處理器，如果還有空閑處理器再次掃描隊列，按照FCFS原則分配處理器。
I/O設備調度
I/O功能的邏輯結構
邏輯I/O：邏輯I/O層將I/O設備視為邏輯資源，不關心底層的細節(jié)。邏輯I/O代表用戶進程管理的一般I/O功能，允許它們根據(jù)設備標識符以及諸如打開、關閉、讀取等操作與設備打交道。
設備I/O：請求的操作和數(shù)據(jù)(緩沖的數(shù)據(jù)、記錄等)被轉換成適當?shù)腎/O指令序列、通道命令和控制器指令?？梢允褂镁彺婕夹g以提高使用率。
調度和控制：關于I/O操作的排隊、調度和控制發(fā)生在這一層，可以在這一次處理中斷，收集和報告I/O狀態(tài)。這一層是與I/O設備真正打交道的軟件層。
I/O緩沖
I/O設備劃分：
I/O設備分為面向塊(block oriented和面向流(stream oriented)的設備，面向塊的設備將信息保存在塊中，通常是固定大小的，傳輸過程中一次傳送一塊。面向流的設備以字節(jié)流的方式傳輸數(shù)據(jù)。
單緩沖：系統(tǒng)在發(fā)送I/O指令后給I/O設備分配一塊位于主存中的緩沖區(qū)，傳輸數(shù)據(jù)被放在緩沖區(qū)中，當傳輸完成時立即嘗試讀取下一塊。根據(jù)局部性原理有理由期望下一塊被讀取，這種機制稱為超前讀。
雙緩沖：單緩沖時I/O設備必須等待讀取緩沖區(qū)中數(shù)據(jù)被完全讀出才能再次寫入，雙緩沖設置兩塊緩存區(qū)域以平滑這種趨勢。設C為進程處理塊的時間，T位讀取塊的時間，我們可以粗略估計塊的執(zhí)行時間位max(C，T)，當C>=T是進程將不需要等待I/O，當C<T是則I/O設備可以全速運行。
循環(huán)緩沖：當爆發(fā)性的執(zhí)行大量的I/O操作時，則僅有雙緩沖就不夠了，這種情況下使用多于兩個緩沖的方案來緩解，這種緩沖區(qū)域自身被當成循環(huán)區(qū)域使用。
需要指出的是緩存是一種技術旨在平緩I/O請求峰值的，當進程需求的I/O平均值大于I/O傳輸速度是再多的緩沖也不能解決問題。
磁盤調度
磁盤性能參數(shù)
尋道時間：機械臂移動到數(shù)據(jù)所在軌道的時間，現(xiàn)在典型磁盤的尋道時間Ts=10ms。
旋轉延遲：磁盤旋轉到要讀取的數(shù)據(jù)位置的延遲，一般取平均時間即1/2r，其中r表示轉速。
傳送時間：磁頭讀取數(shù)據(jù)所花費的時間b/(Nr)，b表示要讀取的字節(jié)數(shù)，N表示磁道上總字節(jié)數(shù)，r表示轉速。
磁盤調度策略
先進先出
先來的請求先服務，由于數(shù)據(jù)的請求式隨機的，會導致較高的尋址時間，效率差。
優(yōu)先級
優(yōu)先級是高優(yōu)先級的請求先服務，一般是為了滿足操作系統(tǒng)的特定目的，并沒有改善磁盤性能的能力。
后進先出(LIFO)
令人驚訝的是這種選取最近請求的策略有許多優(yōu)點。把設備資源提供給最近(使用系統(tǒng))的用戶時會導致磁頭臂在一個順序文件中移動時移動的很少，甚至不移動。利用這種局部性原理可以提高吞吐量減少隊列長度，只要一個作業(yè)積極的使用磁盤它就能盡快得到處理。
當然如果有大量的請求就會導致最先的請求餓死。
最短服務時間優(yōu)先(SSTF)
總是選擇磁頭臂移動最少的請求響應，對于移動距離相等的請求可以隨機移動向一邊。同樣如果一個進程大量的請求臨近的數(shù)據(jù)會導致其它請求饑餓。
SCAN：
SCAN要求磁頭臂向一個方向移動，移動過程中響應在當前磁道的請求。當磁頭臂到達最外(內)層磁道時，再反向掃描。這種算法并沒有很好的利用局部性原理(對最近橫跨過的區(qū)域不公平，不如SSTF和LIFO好)，由于兩側的數(shù)據(jù)被快速的掃描了兩次因此它偏向于外圍數(shù)據(jù)(局部性原理)。
C-SCAN
限定在一個方向掃描，當達到最后一個磁道時，磁頭臂返回到相反方向的磁道末端重新開始掃描。
N-step-SCAN和FSCAN
為了克服進程的粘滯性，在SCAN和C-SCAN中一個或多個進程對一個磁道有較高的訪問速度時可能會壟斷這個磁道一段時間。N-step-SCAN設置若干個N個請求的隊列，每次掃描只響應一個隊列里的請求，當開始掃描時新的請求需要加入到下一個隊列中。
RAID
RAID是一組磁盤系統(tǒng)把它們看為一個單個的邏輯驅動器。
數(shù)據(jù)分布在物理驅動器陣列中
使用冗余的磁盤容量保存奇偶檢驗信息，保障一個磁盤失敗時，數(shù)據(jù)具有可恢復性。
磁盤高速緩沖
高速緩存是系統(tǒng)從主存中劃分的一塊區(qū)域，利用了局部性原理保存最近訪問的數(shù)據(jù)塊，用于提高更好的磁盤性能。
替換算法
LRU：最少訪問，將緩沖區(qū)設置為一個棧，當一個塊被訪問后加入到棧中，如果再次得當訪問則把該塊從當前位置移動到棧頂，隨著塊的加入那些不被訪問的將會擠出棧中。
LFU：最小頻率訪問，對緩存中的塊增加計數(shù)特性，每次被訪問到時計數(shù)加1。當訪問輔存時，把計數(shù)最小的塊移除，加入最近的塊。由于局部性的問題，一個塊可能短時間內多次訪問使得計次很高，但是這之后并不意味著還會再次訪問它，所以LFU并不是一個好的算法。
基于頻率的替換算法：克服LFU的確定，在LRU的棧模型中劃分出位于棧頂?shù)娜舾蓭瑸樾聟^(qū)，當塊位于新區(qū)是重復訪問不增加訪問次數(shù)。
文件管理
文件系統(tǒng)軟件結構
基本文件系統(tǒng)：計算機與外部環(huán)境的接口，該層處理磁盤、磁帶的交互數(shù)據(jù)。
基本I/O管理程序：負責所有文件I/O的初始和終止。
邏輯I/O：是用戶和應用程序能夠訪問到記錄。
訪問方法層(堆、順序文件、索引順序文件、索引、散列)：距離用戶和應用程序最近的層，在應用程序與保存數(shù)據(jù)的設備之間提供了標準接口。
文件結構：
域(Field)：基本的數(shù)據(jù)單元，一個域包含一個值，如雇員名字、日期等。
記錄(Record)：一組相關域的集合，可以看做應用程序的一個單元。
文件(File)：一組相關記錄的集合，它被用戶或應用程序看做一個實體，并可以通過名字訪問。
數(shù)據(jù)庫(DB)：一組相關數(shù)據(jù)的集合，它的本質特征是數(shù)據(jù)之間存在著明確的關系，可供不同的應用程序使用。
文件組織和訪問
堆：
最簡單的文件系統(tǒng)。數(shù)據(jù)按它們到達的順序被組織，通過特定的分隔符或特定的域指明。每個域應該是自描述的，數(shù)據(jù)之間不一定存在聯(lián)系或相同的格式。
當數(shù)據(jù)在處理器采集并存儲時或者當數(shù)據(jù)難以存儲時會用到堆。只能窮舉搜索，對大多數(shù)應用都不適用。
順序文件：
文件具有固定的格式，所有的記錄都有相同的格式，具有相同數(shù)目、長度固定的域按照順序組成。每條記錄第一個域稱為關鍵域，唯一標識了這條記錄。
交互的表現(xiàn)較差，需要順序的搜索。一種情況下順序文件按照順序存儲在磁盤上，在發(fā)生文件修改時需要移動數(shù)據(jù)，可能的處理方式是把數(shù)據(jù)存在臨時堆上，定期的將數(shù)據(jù)批量寫回順序文件。另一種情況文件可能采用鏈式存儲，該方法帶來一些方便，但是是以額外的處理和開銷為代價的。
索引順序文件
彌補了順序文件檢索的問題。檢索文件可以是簡單的順序文件，每條記錄包括兩個值一個關鍵域和指向文件的指針。簡單的檢索可以是一級的，也可以由多級檢索。查找文件時找到相等的域或者關鍵域值之前最大的域。
索引文件
順序文件和索引順序文件只能是順序檢索或對關鍵域檢索，索引文件對感興趣的域提供了索引，索引文件本身可以是順序的。索引文件分為完全索引和部分索引，差別在于被索引的域是全部域還僅僅是感興趣的域。
索引文件一般只提供索引訪問的方式，不再支持順序訪問，因此記錄的組織也不必是順序的，應用程序只能通過指針訪問。
直接文件或散列文件
直接文件或散列文件開發(fā)直接訪問磁盤中任何一個地址一致的塊的能力，要求每條記錄中都有一個關鍵域，但這里不存在順序的概念。
記錄組塊
磁盤中數(shù)據(jù)保存在塊中，塊越大每次傳輸?shù)臄?shù)據(jù)越多，效率越高。當時大的塊要求操作系統(tǒng)提供更大或者復雜的緩存，并且由于局部性的關系大塊中的數(shù)據(jù)可能是應用程序不需要的造成浪費。
固定組塊
使用固定長度的記錄，并且若干條完整記錄保存到一個塊中，每個塊末尾可能有未使用的空間稱為內部碎片。
可變長度跨越式組塊
塊的長度可變，記錄可以跨越塊保存，如果一個塊的末尾空間不足一條記錄時，剩下的數(shù)據(jù)可以保存在下一個塊中，通過后繼指針指明。造成了更復雜的處理，并且當讀取跨越塊的數(shù)據(jù)時需要讀取兩次，消除了內部碎片。
可變長度非跨越式組塊
和上面相同，但是記錄不可以跨越塊保存。
二級存儲管理
文件分配
預分配：文件請求時聲明需要的空間，一次性分配。
動態(tài)分配：根據(jù)文件的增長每次分配一定的空間，或者一塊。
分配方法：
連續(xù)分配：始終給文件分配連續(xù)的空間。這種分配方式對于順序文件非常高效，并且可以簡單的檢索到需要的文件塊。但是會產生外部碎片，并且需要實時運行壓縮程序以消除外部碎片。
鏈式分配：文件不需要順序保存，每塊尾部通過指針指向下一塊數(shù)據(jù)，文件分配表中同樣只要保存一個表項。
鏈式分配的一個后果是局部性不再被利用，如果要順序的讀取一個文件時需要一連串訪問磁盤的不同部分，這對系統(tǒng)的影響很嚴重。一些系統(tǒng)周期性的的對文件進行合并。
索引分配：每個文件在文件分配表中有一個一級索引，分配給文件的每個分區(qū)在索引中都有一個表項，典型的文件索引在物理上并不保存在文件分配表上，而是保存在獨立的一個塊上，文件分配表中該文件索引指向這個塊。
可以消除外部碎片，按大小可變的分區(qū)分配可以提高局部性，任何情況下(大小可變分區(qū)、按塊保存)都需要不時的對文件進行合并。使用大小可變的分區(qū)情況下合并可以減少文件索引。索引分配支持順序和直接讀取數(shù)據(jù)，是最普遍的一種文件分配形式。
空閑空間管理
位表：使用一個向量，向量的每一位代表一塊磁盤，0表示空閑，1表示使用。優(yōu)點是容易找到一塊或一組連續(xù)的空間，問題是需要窮舉來找到合適大小的區(qū)域，當磁盤剩余很少空間時這個問題尤為嚴重，因此需要設置特殊的數(shù)據(jù)結構輔助查找。如位表可以在邏輯上劃分為不同的區(qū)域，建立區(qū)域匯總表統(tǒng)計每個區(qū)域的使用情況，查找空閑位時可以先找到合適的區(qū)域在查找位表中這部分區(qū)域的使用情況。
位表需要加載在主存中，一個位表所需要的存儲總量為【(磁盤大小)/(8_件系統(tǒng)塊大小)】(計算的是占用的字節(jié)數(shù))，因此一個16GB的磁盤，塊大小位512字節(jié)時位表占用4MB，如果每次去數(shù)據(jù)都從硬盤加載4MB的位表的話這個速度是難以忍受的。
鏈式空閑區(qū)
空閑表可以使用指向每個空閑區(qū)的指針和他們的長度值被連接在一起，因為空閑表只需要一個指向第一個空閑區(qū)的指針，因此這種情況下空閑表的大小是可以忽略的。
這種分配法適合所有的文件分配方法，如果按塊分配可以移動位于頭部的指針，如果是按區(qū)域分配則可以順序的找到合適的區(qū)域并更新指針。
存在的問題：1，使用一段時間磁盤會出現(xiàn)很多碎片，許多區(qū)變成只有一塊大小。2，寫時需要先讀取該塊以發(fā)現(xiàn)下一塊的指針，如果進程請求大量的單個塊這個效率是很差的，同意刪除的時候也會導致很慢。
索引
索引是把空閑空間看做文件，使用之前介紹的索引表的方式記錄?；谛实脑颍饕m合使用在大小可變的分區(qū)分配的情況下。
空閑塊列表
每個空閑塊都有一個順序號，把順序號保存在磁盤的一個保留區(qū)中。根據(jù)磁盤的大小，存儲一個塊號需要24位或32位。這是一種令人滿意的方法，空閑塊列表部分保存在主存里：
1，磁盤空閑塊列表占用空間小于磁盤空間的1%。
2，盡管空閑塊太大了，不能保存在主存。但是兩種有效技術把該表的一小部分保存在主存里：
a，這個表可以是一個下推棧，棧中靠前的數(shù)千元素保存在內存中，當分配一個新塊時它從棧頂彈出，同樣當一個塊被接觸時把它壓入棧中。只有棧中部分滿了或者空了時候才需要從磁盤傳輸數(shù)據(jù)，通常情況下它是零訪問時間的。
b，這個表可以看所FIFO的隊列，分配時從頭部取走，取消分配時從隊尾入隊，只有隊空了或者滿了時才需要與磁盤傳輸。
看了“操作系統(tǒng)總結知識”還想看：
1.操作系統(tǒng)主要知識點
2.操作系統(tǒng)知識大全
3.操作系統(tǒng)基本知識 操作系統(tǒng)知識點
4.linux操作系統(tǒng)基礎知識總結
5.系統(tǒng)與設計知識點歸納