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