電腦考研複試面試常問問題 作業系統篇
- 2020 年 4 月 3 日
- 筆記
電腦考研複試面試常問問題 作業系統篇
在複習過程中，我用心查閱並整理了在考研複試面試中可能問到的大部分問題，並分點整理了答案，可以直接理解背誦並加上自己的語言潤色!極力推薦列印下來看，效率更高！
此系列一共有8篇：程式語言篇|數據結構篇|作業系統篇|組成原理篇|電腦網路篇|資料庫篇|軟體工程篇|電腦專業英語篇(還未全部完成,敬請期待,你們的支援和關注是我最大的動力!)
個人整理，不可用於商業用途，轉載請註明出處。
作者各個平台請搜索：程式設計師寶藏。快來探索屬於你的寶藏吧！
需要pdf直接列印版，可在公眾號”程式設計師寶藏”回複復試上岸獲取(會持續更新)
需要408電子書2021版，可在公眾號”程式設計師寶藏”回復408電子書獲取
需要408初試影片2021版，可在公眾號”程式設計師寶藏”回復408影片獲取
需要複試機試影片，可在公眾號”程式設計師寶藏”回復機試必過獲取
加油，大家都可以上岸！！！讓我們一起努力！！！
快速喚起記憶的知識框架
1.作業系統是電腦資源的管理者
處理機管理（進程式控制制、進程同步、進程通訊、死鎖處理、處理機調度）
存儲器管理（提高記憶體利用率，記憶體的分配與回收、地址映射、記憶體保護與共享、記憶體擴充）
文件管理（電腦中的資訊都是以文件的形式存在的）
設備管理（完成用戶的I/O請求，方便用戶使用設備、並提高設備的利用率**）**
2.作業系統為用戶提供使用電腦硬體系統的介面
命令介面（用戶通過控制台或終端輸入操作命令，向系統提供各種服務要求）
程式介面（由
系統調用組成，用戶在程式中使用這些系統調用來請求作業系統為其提供服務）圖形介面 最常見的
圖形用戶介面GUI（最終還是通過調用程式介面實現的）
3.作業系統用作擴充機器
沒有任何軟體支援的電腦稱為裸機，實際呈現在用戶面前的電腦系統是經過若干層軟體改造的電腦。作業系統將裸機改造成功能更強、使用更方便的機器。我們將覆蓋了軟體的機器稱為擴充機器或虛擬機。
1.內核程式和應用程式(內核態和用戶態)
在電腦系統中，通常CPU執行兩種不同性質的程式：一種是作業系統內核程式；另一種是用戶自編程式或系統外層的應用程式。內核程式是應用程式的”管理者”。“管理程式“可以執行一些特權指令，而”被管理程式“出於安全考慮不能執行這些指令。所謂特權指令，是指電腦中不允許用戶直接使用的指令，如：I/O指令、置中斷指令，存取用於記憶體保護的暫存器，送程式狀態字到程式狀態字暫存器等指令。
作業系統在具體實現上劃分了用戶態（目態）和核心態（管態），以嚴格區分兩類程式。
2.層次式結構
作業系統的各項功能分別被設置在不同的層次上。一些與硬體關聯較緊密的模組，諸如時鐘管理、中斷管理、設備驅動等處於最底層。其次是運行頻率較高的程式，諸如進程管理、存儲管理和設備管理等。 上面的這兩部分內容構成了作業系統的內核，這部分內容的指令操作工作在核心態。
3.內核
內核是電腦上配置的底層軟體，是電腦功能的延伸，包括以下4個方面的內容：
1）時鐘管理 時鐘的第一功能是計時，作業系統需要通過時鐘管理，向用戶提供標準的系統時間。其次，通過時鐘中斷的管理，可以實現進程的切換。在分時作業系統中，採用時間片輪轉調度的實現；在實時系統中，按截至時間控制運行的實現；在批處理系統中，通過時鐘管理來衡量一個作業的運行程度等。
2）中斷機制 引入中斷技術的初衷是提高多道程式運行環境中CPU的利用率，主要針對外部設備。後來逐步得到發展，形成了多種類型，成為作業系統各項操作的基礎。如，鍵盤或滑鼠資訊的輸入、進程的管理和調度、系統功能的調用、設備驅動、文件訪問等。都依賴於中斷機制。可以說，現代作業系統是靠中斷驅動的軟體。中斷機制中，只有一小部分功能屬於內核，負責保護和恢復中斷現場的資訊，轉移控制權到相關的處理程式。這樣可以減少中斷的處理時間，提高系統的並行處理能力。
3）原語 作業系統底層是一些可被調用的公用小程式，它們各自完成一個規定的操作，其特點是：
—— 它們處於作業系統的最底層，是最接近硬體的部分。
—— 這些程式的運行具有原子性，其操作只能一氣呵成
—— 這些程式的運行時間都較短，而且調用頻繁。
定義原語的直接方法是關閉中斷，讓它的所有動作不可分割地進行完再打開中斷。
4）系統控制的數據結構及處理 系統中用來登記狀態資訊的數據結構很多，比如：作業控制塊、進程式控制制塊、設備控制塊、各類鏈表等。為了實現有效的管理，系統需要一些基本的操作，常見的操作有以下三種：
—— 進程管理：進程狀態管理、進程調度和分配、創建和撤銷進程式控制制塊等。
—— 存儲器管理：存儲器的空間分配和回收、記憶體資訊保護程式、程式碼對換程式等。
—— 設備管理：緩衝區管理、設備分配和回收等。
1.中斷的引入——為了支援CPU和設備之間的並行操作
中斷也稱外中斷，指來自CPU執行指令以外的事件的發生，如設備發出的I/O結束中斷、時鐘中斷等。這一類中斷通常是與當前執行的指令無關的事件。
2.異常的引入——表示CPU執行指令本身時出現的問題
異常也稱內中斷、例外或陷入，指源自CPU執行指令內部的事件，如程式的非法操作碼、地址越界、算術溢出、缺頁異常等。對異常的處理一般要依賴與當前程式的運行現場，不能被屏蔽。
3.中斷和異常的聯繫與區別
4.中斷執行的流程
以上是多重中斷的流程，其中，1~3步是由硬體（中斷隱指令）完成的；4-9步是由中斷服務程式完成的。
電腦系統的各種硬體資源是有限，為了更好的管理這些資源，進程是不允許直接操作的，所有對這些資源的訪問都必須有作業系統控制。也就是說作業系統是使用這些資源的唯一入口，而這個入口就是作業系統提供的系統調用。一般地，系統調用都是通過中斷實現的，比如，linux下中斷號0x80就是進行系統調用的。
作業系統為用戶態進程與硬體設備進行交互提供了一組介面——系統調用:1.把用戶從底層的硬體編程中解放了出來;2.極大地提高了系統的安全性使用戶程式具有可移植性；用戶程式與具體硬體已經被抽象介面所替代。
系統調用流程圖如下：
1.大內核
大內核是將作業系統功能作為一個緊密結合的整體放到內核。由於各模組共享資訊，因此有很高的性能。
2.微內核
由於作業系統不斷複雜，因此將一部分作業系統功能移出內核，從而降低內核的複雜性。移出的部分根據分層的原則劃分成若干服務，相互獨立。
在微內核結構下，作業系統被劃分成小的、定義良好的模組，只有微內核這一個模組運行在內核態，其餘模組運行在用戶態。
因為需要頻繁地在用戶態和核心態之間進行切換，所以會有一定的性能損失。
快速喚起記憶的知識框架
1.進程的概念與定義
在多道程式環境下，允許多個進程並發執行，此時他們將失去封閉性，並具有間斷性及不可再現性的特徵。為此引入了進程的概念，以便更好地描述和控制程式的並發執行，實現作業系統的並發性和共享性。
進程是程式的運行過程，是系統進行資源分配和調度的一個獨立單位。
2.執行緒的概念和定義
早期，在OS中能擁有資源和獨立運行的基本單位是進程，然而隨著電腦技術的發展，進程出現了很多弊端，一是由於進程是資源擁有者，創建、撤消與切換存在較大的時空開銷，因此需要引入輕型進程；二是由於對稱多處理機（SMP）出現，可以滿足多個運行單位，而多個進程並行開銷過大。
執行緒是作業系統能夠進行運算調度的最小單位。它被包含在進程之中，是進程中的實際運作單位。一條執行緒指的是進程中一個單一順序的控制流，每條執行緒執行不同的任務。
3.進程和執行緒的區別
1.進程（Process）是系統進行資源分配和調度的基本單位，執行緒（Thread）是CPU調度和分派的基本單位；
2.執行緒依賴於進程而存在，一個進程至少有一個執行緒；
3.進程有自己的獨立地址空間，執行緒共享所屬進程的地址空間；
4.進程是擁有系統資源的一個獨立單位，而執行緒自己基本上不擁有系統資源，只擁有一點在運行中必不可少的資源(如程式計數器,一組暫存器和棧)，和其他執行緒共享本進程的相關資源如記憶體、I/O、cpu等；
5.在進程切換時，涉及到整個當前進程CPU環境的保存環境的設置以及新被調度運行的CPU環境的設置，而執行緒切換隻需保存和設置少量的暫存器的內容，並不涉及存儲器管理方面的操作，可見，進程切換的開銷遠大於執行緒切換的開銷；
6.執行緒之間的通訊更方便，同一進程下的執行緒共享全局變數等數據，而進程之間的通訊需要以進程間通訊(IPC)的方式進行；
7.多執行緒程式只要有一個執行緒崩潰，整個程式就崩潰了，但多進程程式中一個進程崩潰並不會對其它進程造成影響，因為進程有自己的獨立地址空間，因此多進程更加健壯
4.進程和程式的區別
（1） 程式是永存的；進程是暫時的，是程式在數據集上的一次執行，有創建有撤銷，存在是暫時的；
（2）程式是靜態的觀念，進程是動態的觀念；
（3）進程具有並發性，而程式沒有；
（4）進程是競爭電腦資源的基本單位，程式不是。
（5）進程和程式不是一一對應的： 一個程式可對應多個進程即多個進程可執行同一程式； 一個進程可以執行一個或幾個程式
1.共享記憶體
顧名思義，共享記憶體就是兩個進程同時共享一塊記憶體，然後在這塊記憶體上的數據可以共同修改和讀取，達到通訊的目的。
2.無名管道
無名管道是半雙工的通訊方式；並且只能在具有親緣關係的進程之間使用（親緣關係是指進程間的父子關係，兄弟關係等），具有親緣關係的進程在創建時同時擁有一個無名管道的句柄，可以進行讀寫；無名管道不存在磁碟節點，只存在與記憶體中用完即銷毀。
3.命名管道
命名管道也是半雙工的通訊方式；可以在不具有親緣關係的進程間通訊；有名管道存在磁碟節點，有對應的FIFO文件，凡是可以訪問該路徑的文件的進程均可以進行通訊。
4.消息隊列
消息隊列是由消息的鏈表，存放在內核中並由消息隊列標識符標識。消息隊列克服了訊號傳遞資訊少、管道只能承載無格式位元組流以及緩衝區大小受限等缺點。
5.套接字
套接字是網路編程的api，通過套接字可以不同的機器間的進程進行通訊，常用於客戶端進程和伺服器進程的通訊。
6.訊號
訊號是Unix系統中使用的最古老的進程間通訊的方法之一。作業系統通過訊號來通知進程系統中發生了某種預先規定好的事件（一組事件中的一個），它也是用戶進程之間通訊和同步的一種原始機制。一個鍵盤中斷或者一個錯誤條件（比如進程試圖訪問它的虛擬記憶體中不存在的位置等）都有可能產生一個訊號。Shell也使用訊號向它的子進程發送作業控制訊號。
1.先來先服務 first-come first-serverd（FCFS）
按照請求的順序進行調度。非搶佔式，開銷小，無飢餓問題，響應時間不確定（可能很慢）；
對短進程不利，對IO密集型進程不利。
2.最短作業優先 shortest job first（SJF）
按估計運行時間最短的順序進行調度。非搶佔式，吞吐量高，開銷可能較大，可能導致飢餓問題；
對短進程提供好的響應時間，對長進程不利
3.優先順序調度演算法
為每個進程分配一個優先順序，按優先順序進行調度。為了防止低優先順序的進程永遠等不到調度，可以隨著時間的推移增加等待進程的優先順序。
4.時間片輪轉
將所有就緒進程按 FCFS 的原則排成一個隊列，用完時間片的進程排到隊列最後。搶佔式（時間片用完時），開銷小，無飢餓問題，為短進程提供好的響應時間；
若時間片小，進程切換頻繁，吞吐量低；若時間片太長，實時性得不到保證。
5.最高響應比優先
響應比 = 1+ 等待時間/處理時間。同時考慮了等待時間的長短和估計需要的執行時間長短，很好的平衡了長短進程。非搶佔，吞吐量高，開銷可能較大，提供好的響應時間，無飢餓問題。
6.多級回饋隊列調度演算法
設置多個就緒隊列1、2、3…，優先順序遞減，時間片遞增。只有等到優先順序更高的隊列為空時才會調度當前隊列中的進程。如果進程用完了當前隊列的時間片還未執行完，則會被移到下一隊列。
搶佔式（時間片用完時），開銷可能較大，對IO型進程有利，可能會出現飢餓問題。
1.同步
多個進程因為合作而使得進程的執行有一定的先後順序。比如某個進程需要另一個進程提供的消息，獲得消息之前進入阻塞態；
2.互斥
多個進程在同一時刻只有一個進程能進入臨界區
3.同步機制的4個準則
1.空閑讓進
當無進程處於臨界區，可允許一個請求進入臨界區的進程立即進入自己的臨界區2.忙則等待
當已有進程進入自己的臨界區，所有企圖進入臨界區的進程必須等待3.有限等待
對要求訪問臨界資源的進程，應保證該進程能在有限時間內進入自己的臨界區4.讓權等待
當進程不能進入自己的臨界區，應釋放處理機
為什麼需要進程同步：進程有時候會和其他進程共享一些資源，比如記憶體、資料庫等。當多個進程同時讀寫同一份共享資源的時候，可能會發生衝突。因此需要進程的同步，多個進程按順序訪問資源。
互斥量 Mutex：互斥量是內核對象，只有擁有互斥對象的執行緒才有訪問互斥資源的許可權。因為互斥對象只有一個，所以可以保證互斥資源不會被多個執行緒同時訪問；當前擁有互斥對象的執行緒處理完任務後必須將互斥對象交出，以便其他執行緒訪問該資源；
訊號量 Semaphore：訊號量是內核對象，它允許同一時刻多個執行緒訪問同一資源，但是需要控制同一時刻訪問此資源的最大執行緒數量。訊號量對象保存了最大資源計數和當前可用資源計數，每增加一個執行緒對共享資源的訪問，當前可用資源計數就減1，只要當前可用資源計數大於0，就可以發出訊號量訊號，如果為0，則將執行緒放入一個隊列中等待。執行緒處理完共享資源後，應在離開的同時通過
ReleaseSemaphore函數將當前可用資源數加1。如果訊號量的取值只能為0或1，那麼訊號量就成為了互斥量；
事件 Event：允許一個執行緒在處理完一個任務後，主動喚醒另外一個執行緒執行任務。事件分為手動重置事件和自動重置事件。手動重置事件被設置為激髮狀態後，會喚醒所有等待的執行緒，而且一直保持為激髮狀態，直到程式重新把它設置為未激髮狀態。自動重置事件被設置為激髮狀態後，會喚醒一個等待中的執行緒，然後自動恢復為未激髮狀態。
臨界區 Critical Section：指的是訪問資源的那段程式碼，任意時刻只允許一個執行緒對臨界資源進行訪問。擁有臨界區對象的執行緒可以訪問該臨界資源，其它試圖訪問該資源的執行緒將被掛起，直到臨界區對象被釋放。
1.死鎖的定義
是指兩個或兩個以上的進程在執行過程中，因爭奪資源而造成的一種互相等待的現象，若無外力作用，它們都將無法推進下去。此時稱系統處於死鎖狀態或系統產生了死鎖，這些永遠在互相等待的進程稱為死鎖進程。
2.死鎖原因：
① 系統資源不足（對不可剝奪資源的競爭）
② 進程推進順序不當（P1擁有A申請B，P2擁有B申請A）
3.產生死鎖的必要條件：
① 互斥條件：指進程對所分配到的資源進行排它性使用，即在一段時間內某資源只由一個進程佔用。
② 請求和保持條件：指進程已經保持至少一個資源，但又提出了新的資源請求，而該資源已被其它進程佔有，此時請求進程阻塞，但又對自己已獲得的其它資源保持不放。
③ 不剝奪條件：指進程已獲得的資源，在未使用完之前，不能被剝奪，只能在使用完時由自己釋放
④ 環路等待條件：指在發生死鎖時，必然存在一個進程資源的環形鏈。
4.處理死鎖的基本方法：
① 預防死鎖：這是一種較簡單和直觀的事先預防的方法。方法是通過設置某些限制條件，去破壞產生死鎖的四個必要條件中的一個或者幾個，來預防發生死鎖。預防死鎖是一種較易實現的方法，已被廣泛使用。但是由於所施加的限制條件往往太嚴格，可能會導致系統資源利用率和系統吞吐量降低。
② 避免死鎖：該方法同樣是屬於事先預防的策略，但它並不須事先採取各種限制措施去破壞產生死鎖的的四個必要條件，而是在資源的動態分配過程中，用 某種方法去防止系統進入不安全狀態，從而避免發生死鎖。
③ 檢測死鎖：這種方法並不須事先採取任何限制性措施，也不必檢查系統是否已經進入不安全區，此方法允許系統在運行過程中發生死鎖。但可通過系統所設置的檢測機構，及時地檢測出死鎖的發生，並精確地確定與死鎖有關的進程和資源，然後採取適當措施，從系統中將已發生的死鎖清除掉。
④ 解除死鎖：這是與檢測死鎖相配套的一種措施。當檢測到系統中已發生死鎖時，須將進程從死鎖狀態中解脫出來。常用的實施方法是撤銷或掛起一些進程，以便回收一些資源，再將這些資源分配給已處於阻塞狀態的進程，使之轉為就緒狀態，以繼續運行。
等待時間給進程推進和響應帶來明顯影響時成為進程飢餓。
飢餓並不代表系統已經死鎖，但至少有一個程式的執行被無限期地推遲。
差別：
① 進入飢餓的進程可以只有一個，但是死鎖必須大於等於兩個；
② 出於飢餓狀態的進程可以是一個就緒進程，但是死鎖狀態的進程必定是阻塞進程。
主要思想是避免系統進入不安全狀態，在每次進行資源分配時，它首先檢查系統是否有足夠的資源滿足要
求，如果有，則先試行分配，並對分配後的新狀態進行安全性檢查。如果新狀態安全，則正式分配上述資
源，否則拒絕分配上述資源。這樣就保證系統始終處於安全狀態，從而避免死鎖現象的發生。
如果資源分配圖是可以完全簡化的（能消去所有的邊），則沒有死鎖。
快速喚起記憶的知識框架
存儲管理的主要任務是為多道程式的運行提供良好的環境，方便用戶使用存儲器，提高存儲器的利用率以
及從邏輯上擴充存儲器，故應具有以下功能：① 記憶體的分配和回收：實施記憶體的分配，回收系統或用戶釋放的記憶體空間。
② 地址變換：提供地址變換功能，將邏輯地址轉換成物理地址。
③ 擴充記憶體：藉助於虛擬存儲技術活其他自動覆蓋技術，為用戶提供比記憶體空間大的地址空間，從邏輯
上擴充記憶體。④ 存儲保護：保證進入記憶體的各道作業都在自己的存儲空間內運行，互不干擾。
1.編譯：由編譯程式將用戶源程式碼編譯成若干目標模組
2.鏈接：由鏈接程式將編譯後形成的一組目標模組及所需的庫函數鏈接在一起，形成一個完整的裝入模組。
3.裝入：由裝入程式將裝入模組裝入記憶體中運行。
① 靜態鏈接：在程式運行之前，先把各個目標模組及所需庫鏈接為一個完整的可執行程式，以後不再拆
開。② 裝入時動態鏈接：將應用程式編譯後所得到的一組目標模組在裝入記憶體時採用邊裝入邊鏈接的鏈接方
式。③ 運行時動態鏈接：知道程式運行過程中需要一些模組時，才對這些模組進行鏈接。
① 絕對裝入：在編譯時就知道程式將要駐留在記憶體的物理地址，編譯程式產生含有物理地址的目標程式碼，
不適合多道程式設計。② 可重定位裝入：根據記憶體當前情況，將裝入模組裝入到記憶體的適當位置，地址變換通常在裝入時一次
完成，之後不再改變，也稱靜態重定位。當作業系統為程式分配一個以某地址為起始地址的連續主存
區域後，重定位時將程式中指令或操作數的邏輯地址加上這個起始地址就得到了物理地址。③ 動態運行裝入：允許程式運行時在記憶體中移動位置，把裝入模組裝入到記憶體後的所有地址都是相對地
址，在程式執行過程中每當訪問到相應指令或數據時，才將要 訪問的程式或數據的相對地址轉換為物
理地址。動態重定位的實現要依靠硬體地址變換機構。
1.覆蓋技術：
把一個大的程式劃分為一系列覆蓋，每個覆蓋是一個相對獨立的程式單位，把程式執行時並不要求同時 裝入記憶體的覆蓋組成一組，成為覆蓋段，這個覆蓋段分配到同一個存儲區域，這個存儲區域成為覆蓋區，它與覆蓋段一一對應。覆蓋段的大小由覆蓋段中最大的覆蓋來確定。（為了解決記憶體容量太小的問題，打破了必須將一個程式全部資訊裝入記憶體後才能運行的限制）
2.交換技術：
把暫時不用的某個程式及數據部分從記憶體移到外存中去，以便騰出必要的記憶體空間；或者把指定的程式或數據從外存讀到相應的記憶體中，並將控制權交給他，讓其在系統上運行的一種記憶體擴充技術。處理器的中級調度就是採用交換技術。
3.區別：
① 與覆蓋技術相比，交換技術不要求程式設計師給出的 程式段之間的覆蓋結構；② 交換技術主要在進程和作業之間進行，覆蓋技術主要在同一個進程或作業中進行；交換技術主要在進程和作業之間進行，覆蓋技術主要在同一個進程或作業中進行；
③ 覆蓋技術只能覆蓋於覆蓋程式段無關的程式段，交換進程由換出和換入兩個過程組成。覆蓋技術只能覆蓋於覆蓋程式段無關的程式段，交換進程由換出和換入兩個過程組成。
1.單一連續分配
記憶體在此方式下分為系統區和用戶區，系統區僅提供給作業系統使用，通常在低地址部分；用戶區是為用戶提供的、除系統區之外的記憶體空間。這種方式無需進行記憶體保護。
這種方式的優點是簡單、無外部碎片，可以釆用覆蓋技術，不需要額外的技術支援。缺點是只能用於單用戶、單任務的作業系統中，有內部碎片，存儲器的利用率極低。
2.固定分區分配
固定分區分配是最簡單的一種多道程式存儲管理方式，它將用戶記憶體空間劃分為若干個固定大小的區域，每個分區只裝入一道作業。當有空閑分區時，便可以再從外存的後備作業隊列中,選擇適當大小的作業裝入該分區，如此循環。
固定分區分配在劃分分區時，有兩種不同的方法。
(1) 分區大小相等：用於利用一台電腦去控制多個相同對象的場合，缺乏靈活性。
(2) 分區大小不等：劃分為含有多個較小的分區、適量的中等分區及少量的大分區。
3.動態分區分配
動態分區分配又稱為可變分區分配，是一種動態劃分記憶體的分區方法。這種分區方法不預先將記憶體劃分，而是在進程裝入記憶體時，根據進程的大小動態地建立分區，並使分區的大小正好適合進程的需要。因此系統中分區的大小和數目是可變的。
4.動態分區分配演算法
在進程裝入或換入主存時，如果記憶體中有多個足夠大的空閑塊，作業系統必須確定分配哪個記憶體塊給進程使用，這就是動態分區的分配策略，考慮以下幾種演算法：
(1) 首次適應(First Fit)演算法：空閑分區以地址遞增的次序鏈接。分配記憶體時順序查找，找到大小能滿足要求的第一個空閑分區。
(2) 最佳適應(Best Fit)演算法：空閑分區按容量遞增形成分區鏈，找到第一個能滿足要求的空閑分區。
(3) 最壞適應(Worst Fit)演算法：又稱最大適應(Largest Fit)演算法，空閑分區以容量遞減的次序鏈接。找到第一個能滿足要求的空閑分區，也就是挑選出最大的分區。
(4) 鄰近適應(Next Fit)演算法：又稱循環首次適應演算法，由首次適應演算法演變而成。不同之處是分配記憶體時從上次查找結束的位置開始繼續查找。
本問內容比較多，適合系統複習，都整理過來不過全面，請自行查閱相關資料（狗頭保命）。
1.最佳（OPT）置換演算法
從主存中移出永遠不再需要的頁面；如無這樣的頁面存在，則選擇最長時間不需要訪問的頁面。於所選擇的被淘汰頁面將是以後永不使用的，或者是在最長時間內不再被訪問的頁面，這樣可以保證獲得最低的缺頁率。 即被淘汰頁面是以後永不使用或最長時間內不再訪問的頁面。（往後看）
2.先進先出（FIFO）置換演算法
是最簡單的頁面置換演算法。這種演算法的基本思想是：當需要淘汰一個頁面時，總是選擇駐留主存時間最長的頁面進行淘汰，即先進入主存的頁面先淘汰。其理由是：最早調入主存的頁面不再被使用的可能性最大。 即優先淘汰最早進入記憶體的頁面。（往前看）
3.最近最久未使用（LRU）演算法
這種演算法的基本思想是：利用局部性原理，根據一個作業在執行過程中過去的頁面訪問歷史來推測未來的行為。它認為過去一段時間裡不曾被訪問過的頁面，在最近的將來可能也不會再被訪問。所以，這種演算法的實質是：當需要淘汰一個頁面時，總是選擇在最近一段時間內最久不用的頁面予以淘汰。 即淘汰最近最長時間未訪問過的頁面。（往前看）
4.時鐘(CLOCK)置換演算法
LRU演算法的性能接近於OPT,但是實現起來比較困難，且開銷大；FIFO演算法實現簡單，但性能差。所以作業系統的設計者嘗試了很多演算法，試圖用比較小的開銷接近LRU的性能，這類演算法都是CLOCK演算法的變體。
簡單的CLOCK演算法是給每一幀關聯一個附加位，稱為使用位。當某一頁首次裝入主存時，該幀的使用位設置為1;當該頁隨後再被訪問到時，它的使用位也被置為1。對於頁替換演算法，用於替換的候選幀集合看做一個循環緩衝區，並且有一個指針與之相關聯。當某一頁被替換時，該指針被設置成指向緩衝區中的下一幀。當需要替換一頁時，作業系統掃描緩衝區，以查找使用位被置為0的一幀。每當遇到一個使用位為1的幀時，作業系統就將該位重新置為0；如果在這個過程開始時，緩衝區中所有幀的使用位均為0，則選擇遇到的第一個幀替換；如果所有幀的使用位均為1,則指針在緩衝區中完整地循環一周，把所有使用位都置為0，並且停留在最初的位置上，替換該幀中的頁。由於該演算法循環地檢查各頁面的情況，故稱為CLOCK演算法，又稱為最近未用(Not Recently Used, NRU)演算法。
頁表指出邏輯地址中的頁號與所佔主存塊號的對應關係。作用：頁式存儲管理在用動態重定位方式裝入作業時，要利用頁表做地址轉換工作。快表就是存放在高速緩衝存儲器的部分頁表。它起頁表相同的作用。由於採用頁表做地址轉換，讀寫記憶體數據時CPU要訪問兩次主存。有了快表，有時只要訪問一次高速緩衝存儲器，一次主存，這樣可加速查找並提高指令執行速度。
TLB->頁表（TLB不命中）->Cache->主存（Cache不命中）->外存
本章重要程度比較低
快速喚起記憶知識框架
文件屬於抽象數據類型。為了恰當地定義文件，就需要考慮有關文件的操作。作業系統提供系統調用，它對文件進行創建、寫、讀、定位和截斷。
①創建文件：創建文件有兩個必要步驟，一是在文件系統中為文件找到空間；二是在目錄中為新文件創建條目，該條目記錄文件名稱、在文件系統中的位置及其他可能資訊。
②寫文件：為了寫文件，執行一個系統調用，指明文件名稱和要寫入文件的內容。對於給定文件名稱，系統搜索目錄以查找文件位置。系統必須為該文件維護一個寫位置的指針。每當發生寫操作，便更新寫指針。
③讀文件：為了讀文件，執行一個系統調用，指明文件名稱和要讀入文件塊的記憶體位置。同樣，需要搜索目錄以找到相關目錄項，系統維護一個讀位置的指針。每當發生讀操作時，更新讀指針。一個進程通常只對一個文件讀或寫，所以當前操作位置可作為每個進程當前文件位置指針。由於讀和寫操作都使用同一指針，節省了空間也降低了系統複雜度。
④文件重定位（文件定址）：按某條件搜索目錄，將當前文件位置設為給定值，並且不會讀、寫文件。
⑤刪除文件：先從目錄中找到要刪除文件的目錄項，使之成為空項，然後回收該文件所佔用的存儲空間。
⑥截斷文件：允許文件所有屬性不變，並刪除文件內容，即將其長度設為0並釋放其空間。
這6個基本操作可以組合執行其他文件操作。例如，一個文件的複製，可以創建新文件、 從舊文件讀出並寫入到新文件。
1、先來先服務演算法（FCFS）First Come First Service
這是一種比較簡單的磁碟調度演算法。它根據進程請求訪問磁碟的先後次序進行調度。此演算法的優點是公平、簡單，且每個進程的請求都能依次得到處理，不會出現某一進程的請求長期得不到滿足的情況。此演算法由於未對尋道進行優化，在對磁碟的訪問請求比較多的情況下，此演算法將降低設備服務的吞吐量，致使平均尋道時間可能較長，但各進程得到服務的響應時間的變化幅度較小。
2、最短尋道時間優先演算法（SSTF） Shortest Seek Time First
該演算法選擇這樣的進程，其要求訪問的磁軌與當前磁頭所在的磁軌距離最近，以使每次的尋道時間最短，該演算法可以得到比較好的吞吐量，但卻不能保證平均尋道時間最短。其缺點是對用戶的服務請求的響應機會不是均等的，因而導致響應時間的變化幅度很大。在服務請求很多的情況下，對內外邊緣磁軌的請求將會無限期的被延遲，有些請求的響應時間將不可預期。
3、掃描演算法（SCAN）電梯調度
掃描演算法不僅考慮到欲訪問的磁軌與當前磁軌的距離，更優先考慮的是磁頭的當前移動方向。例如，當磁頭正在自里向外移動時，掃描演算法所選擇的下一個訪問對象應是其欲訪問的磁軌既在當前磁軌之外，又是距離最近的。這樣自里向外地訪問，直到再無更外的磁軌需要訪問才將磁臂換向，自外向里移動。這時，同樣也是每次選擇這樣的進程來調度，即其要訪問的磁軌，在當前磁軌之內，從而避免了飢餓現象的出現。由於這種演算法中磁頭移動的規律頗似電梯的運行，故又稱為電梯調度演算法。此演算法基本上克服了最短尋道時間優先演算法的服務集中於中間磁軌和響應時間變化比較大的缺點，而具有最短尋道時間優先演算法的優點即吞吐量較大，平均響應時間較小，但由於是擺動式的掃描方法，兩側磁軌被訪問的頻率仍低於中間磁軌。
4、循環掃描演算法（CSCAN）
循環掃描演算法是對掃描演算法的改進。如果對磁軌的訪問請求是均勻分布的，當磁頭到達磁碟的一端，並反向運動時落在磁頭之後的訪問請求相對較少。這是由於這些磁軌剛被處理，而磁碟另一端的請求密度相當高，且這些訪問請求等待的時間較長，為了解決這種情況，循環掃描演算法規定磁頭單向移動。例如，只自里向外移動，當磁頭移到最外的被訪問磁軌時，磁頭立即返回到最里的欲訪磁軌，即將最小磁軌號緊接著最大磁軌號構成循環，進行掃描。
快速喚起記憶知識框架
1.程式 I/O 方式
早期的電腦系統中， 沒有中斷系統，所以CPU和I/O設備進行通訊，傳輸數據時CPU速度遠快於I/O設備，於是CPU需要不斷測試I/O設備，看其是否完成了傳輸。
2.中斷驅動方式
當某進程要啟動某個 I/O 設備工作時，便由 CPU 向相應的設備控制器發出一條 I/O 命令，然後立即返回繼續執行原來的任務。僅當輸完一個數據時，才需 CPU 花費極短的時間去做些中斷處理。
3.DMA方式（直接存儲器訪問）
通過在I/O設備和記憶體之間開啟一個可以直接傳輸數據的通路，採用DMA控制器來控制一個數據塊的傳輸，CPU只需在一個數據塊傳輸開始階段設置好傳輸所需的控制資訊，並在傳輸結束階段做進一步處理。
4.I/O通道控制方式
雖然DMA方式比起中斷方式來已經顯著地減少了CPU的干預，即已由以字（節）為單位的干預減少到以數據塊為單位的干預。但CPU每發出一條I/O指令，也只能去讀/寫一個連續的數據塊。而當我們需要一次去讀多個數據塊且將它們分別傳送到不同的記憶體區域，或者相反時，則需由CPU分別發出多條I/O指令及進行多次中斷處理才能完成。
—- 通道控制方式與DMA控制方式類似，也是一種以記憶體為中心，實現設備與記憶體直接交換數據的控制方式。
—- 與DMA控制方式相比，通道方式所需要的CPU干預更少，而且可以做到一個通道控制多台設備，從而進一步減輕了CPU負擔。
—- 通道本質上是一個簡單的處理器，專門負責輸入、輸出控制，具有執行I/O指令的能力，並通過執行通道I/O程式來控制I/O操作。
—- 通道的指令系統比較簡單，一般只有數據傳送指令、設備控制指令等。
虛擬性是OS的四大特性之一。如果說可以通過多道程式技術將一台物理CPU虛擬為多台邏輯CPU，從而允許多個用戶共享一台主機，那麼，通過SPOOling技術便可將一台物理I/O設備虛擬為多台邏輯I/O設備，同樣允許多個用戶共享一台物理I/O設備。
SPOOLing技術是對離線輸入、輸出系統的模擬。相應地，SPOOLing系統必須建立在具有多道程式功能的作業系統上，而且還應有高速隨機外存的支援，這通常是採用磁碟存儲技術。
SPOOLing系統主要有以下三部分：
（1）輸入井和輸出井。這是在磁碟上開闢的兩個大存儲空間。輸入井是模擬離線輸入時的磁碟設備，用於暫存I/Q設備輸入的數據；輸出井是模擬離線輸出時的磁碟，用於暫存用戶程式的輸出數據。
（2）輸入緩衝區和輸出緩衝區。為了緩和和CPU和磁碟之間速度不匹配的矛盾，在記憶體中要開闢兩個緩衝區；輸入緩衝區和輸出緩衝區。輸入緩衝區用於暫存由輸入設備送來的數據，以後再傳送到輸入井。輸出緩衝區用與暫存從輸出井送來的數據，以後在傳送給輸出設備。
（3）輸入進程SPi 和輸入進程SP0。這裡利用兩個進程來模擬離線I/O時的外圍控制機。其中，進程SPi模擬離線輸入時的外圍控制機，將用戶要求的數據從輸入機通過輸入緩衝區再送到輸入井，當CPU需要輸入數據時，直接從輸入井讀入記憶體；進程SP0模擬離線輸出時的外圍控制機，把用戶要求輸出的數據從先記憶體送到輸出井，待輸出設備空閑時，在將輸出井中的數據經過輸出緩衝區送到輸出設備上。
SPOOLing技術的特點：
(1)提高了I/O速度。從對低速I/O設備進行的I/O操作變為對輸入井或輸出井的操作，如同離線操作一樣，提高了I/O速度，緩和了CPU與低速I/O設備速度不匹配的矛盾。
(2)將獨佔設備改造為共享設備。因為在SPOOLing系統的系統中，實際上並沒為任何進程分配設備，而知識在輸入井或輸出井中為進程分配一個存儲區和建立一張I/O請求表。這樣，便把獨佔設備改造為共享設備。
(3)實現了虛擬設備功能。多個進程同時使用一獨享設備，而對每一進程而言，都認為自己獨佔這一設備，從而實現了設備的虛擬分配。不過，該設備是邏輯上的設備
