聊一聊操作系統八股文背誦版
備受期待的操作系統八股文來啦!
八股文在線網址: http://interviewtop.top
求大家給我們的八股文項目github來個贊!https://github.com/autoencoder-github/interviewtop
什么是操作系統?請簡要概述一下
操作系統是管理計算機硬件和軟件資源的計算機程序，提供一個計算機用戶與計算機硬件系統之間的接口。
向上對用戶程序提供接口，向下接管硬件資源。
操作系統本質上也是一個軟件，作為最接近硬件的系統軟件，負責處理器管理、存儲器管理、設備管理、文件管理和提供用戶接口。
操作系統有哪些分類?
操作系統常規可分為批處理操作系統、分時操作系統、實時操作系統。
若一個操作系統兼顧批操作和分時的功能，則稱該系統為通用操作系統。
常見的通用操作系統有：Windows、Linux、MacOS等。
什么是內核態和用戶態?
為了避免操作系統和關鍵數據被用戶程序破壞，將處理器的執行狀態分為內核態和用戶態。
內核態是操作系統管理程序執行時所處的狀態，能夠執行包含特權指令在內的一切指令，能夠訪問系統內所有的存儲空間。
用戶態是用戶程序執行時處理器所處的狀態，不能執行特權指令，只能訪問用戶地址空間。
用戶程序運行在用戶態,操作系統內核運行在內核態。
如何實現內核態和用戶態的切換?
處理器從用戶態切換到內核態的方法有三種：系統調用、異常和外部中斷。
- 系統調用是操作系統的最小功能單位，是操作系統提供的用戶接口，系統調用本身是一種軟中斷。
- 異常，也叫做內中斷，是由錯誤引起的，如文件損壞、缺頁故障等。
- 外部中斷，是通過兩根信號線來通知處理器外設的狀態變化，是硬中斷。
并發和并行的區別
- 并發(concurrency)：指宏觀上看起來兩個程序在同時運行，比如說在單核cpu上的多任務。但是從微觀上看兩個程序的指令是交織著運行的，指令之間交錯執行，在單個周期內只運行了一個指令。這種并發并不能提高計算機的性能，只能提高效率(如降低某個進程的相應時間)。
- 并行(parallelism)：指嚴格物理意義上的同時運行，比如多核cpu，兩個程序分別運行在兩個核上，兩者之間互不影響，單個周期內每個程序都運行了自己的指令，也就是運行了兩條指令。這樣說來并行的確提高了計算機的效率。所以現在的cpu都是往多核方面發展。
什么是進程?
進程是操作系統中最重要的抽象概念之一，是資源分配的基本單位，是獨立運行的基本單位。
進程的經典定義就是一個執行中程序的實例。系統中的每個程序都運行在某個進程的上下文(context)中。
上下文是由程序正確運行所需的狀態組成的。這個狀態包括存放在內存中的程序的代碼和數據，它的棧、通用目的寄存器的內容、程序計數器、環境變量以及打開文件描述符的集合。
進程一般由以下的部分組成：
- 進程控制塊PCB，是進程存在的唯一標志，包含進程標識符PID，進程當前狀態，程序和數據地址，進程優先級、CPU現場保護區(用于進程切換)，占有的資源清單等。
- 程序段
- 數據段
進程的基本操作
以Unix系統舉例：
進程的創建：fork()。新創建的子進程幾乎但不完全與父進程相同。子進程得到與父進程用戶級虛擬地址空間相同的(但是獨立的)一份副本，包括代碼和數據段、堆、共享庫以及用戶棧。子進程還獲得與父進程任何打開文件描述符相同的副本，這就意味著當父進程調用 fork 時，子進程可以讀寫父進程中打開的任何文件。父進程和新創建的子進程之間最大的區別在于它們有不同的 PID。fork函數是有趣的(也常常令人迷惑)， 因為它只被調用一次，卻會返回兩次：一次是在調用進程(父進程)中，一次是在新創建的子進程中。在父進程中，fork 返回子進程的 PID。在子進程中，fork 返回 0。因為子進程的 PID 總是為非零，返回值就提供一個明 確的方法來分辨程序是在父進程還是在子進程中執行。
- pid_t fork(void);
回收子進程：當一個進程由于某種原因終止時，內核并不是立即把它從系統中清除。相反，進程被保持在一種已終止的狀態中，直到被它的父進程回收(reaped)。當父進程回收已終止的子進程時，內核將子進程的退出狀態傳遞給父進程，然后拋棄已終止的進程。一個進程可以通過調用 waitpid 函數來等待它的子進程終止或者停止。
- pid_t waitpid(pid_t pid, int *statusp, int options);
加載并運行程序：execve 函數在當前進程的上下文中加載并運行一個新程序。
- int execve(const char *filename, const char *argv[], const char *envp[]);
進程終止：
- void exit(int status);
簡述進程間通信方法
每個進程各自有不同的用戶地址空間,任何一個進程的全局變量在另一個進程中都看不到，所以進程之間要交換數據必須通過內核,在內核中開辟一塊緩沖區,進程A把數據從用戶空間拷到內核緩沖區,進程B再從內核緩沖區把數據讀走,內核提供的這種機制稱為進程間通信。
不同進程間的通信本質：進程之間可以看到一份公共資源;而提供這份資源的形式或者提供者不同，造成了通信方式不同。
進程間通信主要包括管道、系統IPC(包括消息隊列、信號量、信號、共享內存等)、以及套接字socket。
進程如何通過管道進行通信
管道是一種最基本的IPC機制，作用于有血緣關系的進程之間，完成數據傳遞。調用pipe系統函數即可創建一個管道。有如下特質：
- 其本質是一個偽文件(實為內核緩沖區)
- 由兩個文件描述符引用，一個表示讀端，一個表示寫端。
- 規定數據從管道的寫端流入管道，從讀端流出。
管道的原理: 管道實為內核使用環形隊列機制，借助內核緩沖區實現。
管道的局限性：
- 數據自己讀不能自己寫。
- 數據一旦被讀走，便不在管道中存在，不可反復讀取。
- 由于管道采用半雙工通信方式。因此，數據只能在一個方向上流動。
- 只能在有公共祖先的進程間使用管道。
進程如何通過共享內存通信?
它使得多個進程可以訪問同一塊內存空間，不同進程可以及時看到對方進程中對共享內存中數據得更新。這種方式需要依靠某種同步操作，如互斥鎖和信號量等。
特點：
- 共享內存是最快的一種IPC，因為進程是直接對內存進行操作來實現通信，避免了數據在用戶空間和內核空間來回拷貝。
- 因為多個進程可以同時操作，所以需要進行同步處理。
- 信號量和共享內存通常結合在一起使用，信號量用來同步對共享內存的訪問。
什么是信號
一個信號就是一條小消息，它通知進程系統中發生了一個某種類型的事件。Linux 系統上支持的30 種不同類型的信號。每種信號類型都對應于某種系統事件。低層的硬件異常是由內核異常處理程序處理的，正常情況下，對用戶進程而言是不可見的。信號提供了一種機制，通知用戶進程發生了這些異常。
發送信號：內核通過更新目的進程上下文中的某個狀態，發送(遞送)一個信號給目的進程。發送信號可以有如下兩種原因：
- 內核檢測到一個系統事件，比如除零錯誤或者子進程終止。
- —個進程調用了kill 函數， 顯式地要求內核發送一個信號給目的進程。一個進程可以發送信號給它自己。
接收信號：當目的進程被內核強迫以某種方式對信號的發送做出反應時，它就接收了信號。進程可以忽略這個信號，終止或者通過執行一個稱為信號處理程序(signal handler)的用戶層函數捕獲這個信號。
如何編寫正確且安全的信號處理函數
1.處理程序要盡可能簡單。避免麻煩的最好方法是保持處理程序盡可能小和簡單。例如，處理程序可能只是簡單地設置全局標志并立即返回;所有與接收信號相關的處理都由主程序執行，它周期性地檢查(并重置)這個標志。
2.在處理程序中只調用異步信號安全的函數。所謂異步信號安全的函數(或簡稱安全的函數)能夠被信號處理程序安全地調用，原因有二：要么它是可重入的(例如只訪問局部變量)，要么它不能被信號處理程序中斷。
3.保存和恢復errno。許多Linux 異步信號安全的函數都會在出錯返回時設置errno在處理程序中調用這樣的函數可能會干擾主程序中其他依賴于分。解決方法是在進人處理程序時把errno 保存在一個局部變量中，在處理程序返回前恢復它。注意，只有在處理程序要返回時才有此必要。如果處理程序調用_exit終止該進程，那么就不需要這樣做了。
4.阻塞所有的信號，保護對共享全局數據結構的訪問。如果處理程序和主程序或其他處理程序共享一個全局數據結構，那么在訪問(讀或者寫)該數據結構時，你的處理程序和主程序應該暫時阻塞所有的信號。這條規則的原因是從主程序訪問一個數據結構d 通常需要一系列的指令，如果指令序列被訪問d 的處理程序中斷，那么處理程序可能會發現d 的狀態不一致，得到不可預知的結果。在訪問d 時暫時阻塞信號保證了處理程序不會中斷該指令序列。
5.用volatile 聲明全局變量。考慮一個處理程序和一個main 函數，它們共享一個全局變量g 。處理程序更新g，main 周期性地讀g， 對于一個優化編譯器而言，main 中g的值看上去從來沒有變化過，因此使用緩存在寄存器中g 的副本來滿足對g 的每次引用是很安全的。如果這樣，main 函數可能永遠都無法看到處理程序更新過的值。可以用volatile 類型限定符來定義一個變量，告訴編譯器不要緩存這個變量。例如：volatile 限定符強迫編譯器毎次在代碼中引用g時，都要從內存中讀取g的值。一般來說，和其他所有共享數據結構一樣，應該暫時阻塞信號，保護每次對全局變量的訪問。
- volatile int g;
6.用sig_atomic_t聲明標志。在常見的處理程序設計中，處理程序會寫全局標志來記錄收到了信號。主程序周期性地讀這個標志，響應信號，再清除該標志。對于通過這種方式來共享的標志，C 提供一種整型數據類型sig_atomic_t對它的讀和寫保證會是原子的(不可中斷的)。
7.信號的一個與直覺不符的方面是未處理的信號是不排隊的。因為 pending 位向量中每種類型的信號只對應有一位，所以每種類型最多只能有一個未處理的信號。關鍵思想是如果存在一個未處理的信號就表明至少有一個信號到達了。
進程調度的時機
- 當前運行的進程運行結束。
- 當前運行的進程由于某種原因阻塞。
- 執行完系統調用等系統程序后返回用戶進程。
- 在使用搶占調度的系統中，具有更高優先級的進程就緒時。
- 分時系統中，分給當前進程的時間片用完。
不能進行進程調度的情況
- 在中斷處理程序執行時。
- 在操作系統的內核程序臨界區內。
- 其它需要完全屏蔽中斷的原子操作過程中。
進程的調度策略
- 先到先服務調度算法
- 短作業優先調度算法
- 優先級調度算法
- 時間片輪轉調度算法
- 高響應比優先調度算法
- 多級隊列調度算法
- 多級反饋隊列調度算法
進程調度策略的基本設計指標
- CPU利用率
- 系統吞吐率，即單位時間內CPU完成的作業的數量。
- 響應時間。
- 周轉時間。是指作業從提交到完成的時間間隔。從每個作業的角度看，完成每個作業的時間也是很關鍵
- 平均周轉時間
- 帶權周轉時間
- 平均帶權周轉時間
進程的狀態與狀態轉換
進程在運行時有三種基本狀態：就緒態、運行態和阻塞態。
1.運行(running)態：進程占有處理器正在運行的狀態。進程已獲得CPU，其程序正在執行。在單處理機系統中，只有一個進程處于執行狀態;在多處理機系統中，則有多個進程處于執行狀態。
2.就緒(ready)態：進程具備運行條件，等待系統分配處理器以便運行的狀態。 當進程已分配到除CPU以外的所有必要資源后，只要再獲得CPU，便可立即執行，進程這時的狀態稱為就緒狀態。在一個系統中處于就緒狀態的進程可能有多個，通常將它們排成一個隊列，稱為就緒隊列。
3.阻塞(wait)態：又稱等待態或睡眠態，指進程不具備運行條件，正在等待某個時間完成的狀態。
各狀態之間的轉換：
就緒→執行 處于就緒狀態的進程，當進程調度程序為之分配了處理機后，該進程便由就緒狀態轉變成執行狀態。
執行→就緒 處于執行狀態的進程在其執行過程中，因分配給它的一個時間片已用完而不得不讓出處理機，于是進程從執行狀態轉變成就緒狀態。
執行→阻塞 正在執行的進程因等待某種事件發生而無法繼續執行時，便從執行狀態變成阻塞狀態。
阻塞→就緒 處于阻塞狀態的進程，若其等待的事件已經發生，于是進程由阻塞狀態轉變為就緒狀態。
什么是孤兒進程?僵尸進程?
1.孤兒進程：父進程退出，子進程還在運行的這些子進程都是孤兒進程，孤兒進程將被init進程(1號進程)所收養，并由init進程對他們完成狀態收集工作。
2.僵尸進程：進程使用fork創建子進程，如果子進程退出，而父進程并沒有調用wait 獲waitpid 獲取子進程的狀態信息，那么子進程的進程描述符仍然保存在系統中的這些進程是僵尸進程。
什么是線程?
- 是進程劃分的任務，是一個進程內可調度的實體，是CPU調度的基本單位，用于保證程序的實時性，實現進程內部的并發。
- 線程是操作系統可識別的最小執行和調度單位。每個線程都獨自占用一個虛擬處理器：獨自的寄存器組，指令計數器和處理器狀態。
- 每個線程完成不同的任務，但是屬于同一個進程的不同線程之間共享同一地址空間(也就是同樣的動態內存，映射文件，目標代碼等等)，打開的文件隊列和其他內核資源。
為什么需要線程?
線程產生的原因：進程可以使多個程序能并發執行，以提高資源的利用率和系統的吞吐量;但是其具有一些缺點：
- 進程在同一時刻只能做一個任務，很多時候不能充分利用CPU資源。
- 進程在執行的過程中如果發生阻塞，整個進程就會掛起，即使進程中其它任務不依賴于等待的資源，進程仍會被阻塞。
引入線程就是為了解決以上進程的不足，線程具有以下的優點：
- 從資源上來講，開辟一個線程所需要的資源要遠小于一個進程。
- 從切換效率上來講，運行于一個進程中的多個線程，它們之間使用相同的地址空間，而且線程間彼此切換所需時間也遠遠小于進程間切換所需要的時間(這種時間的差異主要由于緩存的大量未命中導致)。
- 從通信機制上來講，線程間方便的通信機制。對不同進程來說，它們具有獨立的地址空間，要進行數據的傳遞只能通過進程間通信的方式進行。線程則不然，屬于同一個進程的不同線程之間共享同一地址空間，所以一個線程的數據可以被其它線程感知，線程間可以直接讀寫進程數據段(如全局變量)來進行通信(需要一些同步措施)。
簡述線程和進程的區別和聯系
- 一個線程只能屬于一個進程，而一個進程可以有多個線程，但至少有一個線程。線程依賴于進程而存在。
- 進程在執行過程中擁有獨立的地址空間，而多個線程共享進程的地址空間。(資源分配給進程，同一進程的所有線程共享該進程的所有資源。同一進程中的多個線程共享代碼段(代碼和常量)，數據段(全局變量和靜態變量)，擴展段(堆存儲)。但是每個線程擁有自己的棧段，棧段又叫運行時段，用來存放所有局部變量和臨時變量。)
- 進程是資源分配的最小單位，線程是CPU調度的最小單位。
- 通信：由于同一進程中的多個線程具有相同的地址空間，使它們之間的同步和通信的實現，也變得比較容易。進程間通信IPC，線程間可以直接讀寫進程數據段(如全局變量)來進行通信(需要一些同步方法，以保證數據的一致性)。
- 進程編程調試簡單可靠性高，但是創建銷毀開銷大;線程正相反，開銷小，切換速度快，但是編程調試相對復雜。
- 進程間不會相互影響;一個進程內某個線程掛掉將導致整個進程掛掉。
- 進程適應于多核、多機分布;線程適用于多核。
進程和線程的基本API
進程API以Unix系統為例，線程相關的API屬于Posix線程(Pthreads)標準接口。
| 進程原語 | 線程原語 | 描述 |
|---|---|---|
fork |
pthread_create |
創建新的控制流 |
exit |
pthread_exit |
從現有的控制流中退出 |
waitpid |
pthread_join |
從控制流中得到退出狀態 |
atexit |
pthread_cancel_push |
注冊在退出控制流時調用的函數 |
getpid |
pthread_self |
獲取控制流的ID |
abort |
pthread_cancel |
請求控制流的非正常退出 |
多線程模型
- 多對一模型。將多個用戶級線程映射到一個內核級線程上。該模型下，線程在用戶空間進行管理，效率較高。缺點就是一個線程阻塞，整個進程內的所有線程都會阻塞。幾乎沒有系統繼續使用這個模型。
- 一對一模型。將內核線程與用戶線程一一對應。優點是一個線程阻塞時，不會影響到其它線程的執行。該模型具有更好的并發性。缺點是內核線程數量一般有上限，會限制用戶線程的數量。更多的內核線程數目也給線程切換帶來額外的負擔。linux和Windows操作系統家族都是使用一對一模型。
- 多對多模型。將多個用戶級線程映射到多個內核級線程上。結合了多對一模型和一對一模型的特點。
進程同步的方法
操作系統中，進程是具有不同的地址空間的，兩個進程是不能感知到對方的存在的。有時候，需要多個進程來協同完成一些任務。當多個進程需要對同一個內核資源進行操作時，這些進程便是競爭的關系，操作系統必須協調各個進程對資源的占用，進程的互斥是解決進程間競爭關系的方法。進程互斥指若干個進程要使用同一共享資源時，任何時刻最多允許一個進程去使用，其他要使用該資源的進程必須等待，直到占有資源的進程釋放該資源。當多個進程協同完成一些任務時，不同進程的執行進度不一致，這便產生了進程的同步問題。需要操作系統干預，在特定的同步點對所有進程進行同步，這種協作進程之間相互等待對方消息或信號的協調關系稱為進程同步。進程互斥本質上也是一種進程同步。進程的同步方法：
- 互斥鎖
- 讀寫鎖
- 條件變量
- 記錄鎖(record locking)
- 信號量
- 屏障(barrier)
線程同步的方法
操作系統中，屬于同一進程的線程之間具有相同的地址空間，線程之間共享數據變得簡單高效。遇到競爭的線程同時修改同一數據或是協作的線程設置同步點的問題時，需要使用一些線程同步的方法來解決這些問題。
線程同步的方法：
- 互斥鎖
- 讀寫鎖
- 條件變量
- 信號量
- 自旋鎖
- 屏障(barrier)
進程同步與線程同步有什么區別
進程之間地址空間不同，不能感知對方的存在，同步時需要將鎖放在多進程共享的空間。而線程之間共享同一地址空間，同步時把鎖放在所屬的同一進程空間即可。
死鎖是怎樣產生的?
死鎖是指兩個或兩個以上進程在執行過程中，因爭奪資源而造成的下相互等待的現象。產生死鎖需要滿足下面四個條件：
- 互斥條件：進程對所分配到的資源不允許其他進程訪問，若其他進程訪問該資源，只能等待，直至占有該資源的進程使用完成后釋放該資源。
- 占有并等待條件：進程獲得一定的資源后，又對其他資源發出請求，但是該資源可能被其他進程占有，此時請求阻塞，但該進程不會釋放自己已經占有的資源。
- 非搶占條件：進程已獲得的資源，在未完成使用之前，不可被剝奪，只能在使用后自己釋放。
- 循環等待條件：進程發生死鎖后，必然存在一個進程-資源之間的環形鏈。
如何解決死鎖問題?
解決死鎖的方法即破壞產生死鎖的四個必要條件之一，主要方法如下:
- 資源一次性分配，這樣就不會再有請求了(破壞請求條件)。
- 只要有一個資源得不到分配，也不給這個進程分配其他的資源(破壞占有并等待條件)。
- 可搶占資源：即當進程新的資源未得到滿足時，釋放已占有的資源，從而破壞不可搶占的條件。
- 資源有序分配法：系統給每類資源賦予一個序號，每個進程按編號遞增的請求資源，釋放則相反，從而破壞環路等待的條件
什么是虛擬地址，什么是物理地址?
地址空間是一個非負整數地址的有序集合。
在一個帶虛擬內存的系統中，CPU 從一個有N=pow(2,n)個地址的地址空間中生成虛擬地址，這個地址空間稱為虛擬地址空間(virtual address space),現代系統通常支持 32 位或者 64 位虛擬地址空間。
一個系統還有一個物理地址空間(physical address space)，對應于系統中物理內存的M 個字節。
地址空間的概念是很重要的，因為它清楚地區分了數據對象(字節)和它們的屬性(地址)。
一旦認識到了這種區別，那么我們就可以將其推廣，允許每個數據對象有多個獨立的地址，其中每個地址都選自一個不同的地址空間。這就是虛擬內存的基本思想。
主存中的每字節都有一個選自虛擬地址空間的虛擬地址和一個選自物理地址空間的物理地址。
什么是虛擬內存?
為了更加有效地管理內存并且少出錯，現代系統提供了一種對主存的抽象概念，叫做虛擬內存(VM)。虛擬內存是硬件異常、硬件地址翻譯、主存、磁盤文件和內核軟件的完美交互，它為每個進程提供了一個大的、一致的和私有的地址空間。通過一個很清晰的機制，虛擬內存提供了三個重要的能力：
- 它將主存看成是一個存儲在磁盤上的地址空間的高速緩存，在主存中只保存活動區域，并根據需要在磁盤和主存之間來回傳送數據，通過這種方式，它高效地使用了主存。
- 它為每個進程提供了一致的地址空間，從而簡化了內存管理。
- 它保護了每個進程的地址空間不被其他進程破壞。
為什么要引入虛擬內存?
虛擬內存作為緩存的工具
- 虛擬內存被組織為一個由存放在磁盤上的N個連續的字節大小的單元組成的數組。
- 虛擬內存利用DRAM緩存來自通常更大的虛擬地址空間的頁面。
虛擬內存作為內存管理的工具。操作系統為每個進程提供了一個獨立的頁表，也就是獨立的虛擬地址空間。多個虛擬頁面可以映射到同一個物理頁面上。
- 一般：每個進程有各自私有的代碼，數據，堆棧，是不和其他進程共享的，這樣OS創建頁表，將虛擬頁映射到不連續的物理頁面。
- 某些情況下，需要進程來共享代碼和數據。例如每個進程調用相同的操作系統內核代碼，或者C標準庫函數。OS會把不同進程中適當的虛擬頁面映射到相同的物理頁面。
- 加載器從不在磁盤到內存實際復制任何數據，在每個頁初次被引用時，虛擬內存系統會按照需要自動的調入數據頁。
- 例如：一個給定的linux系統上的每個進程都是用類似的內存格式，對于64為地址空間，代碼段總是從虛擬地址)0x400000開始，數據段，代碼段，棧，堆等等。
- 簡化鏈接： 獨立的地址空間允許每個進程的內存映像使用相同的基本格式，而不管代碼和數據實際存放在物理內存的何處。
- 簡化加載： 虛擬內存還使得容易向內存中加載可執行文件和共享對象文件。要把目標文件中.text和.data節加載到一個新創建的進程中，Linux加載器為代碼和數據段分配虛擬頁VP，把他們標記為無效(未被緩存) ，將頁表條目指向目標文件的起始位置。
- 簡化共享： 獨立地址空間為OS提供了一個管理用戶進程和操作系統自身之間共享的一致機制。
- 簡化內存分配： 虛擬內存向用戶提供一個簡單的分配額外內存的機制。當一個運行在用戶進程中的程序要求額外的堆空間時(如malloc)，OS分配一個適當k大小個連續的虛擬內存頁面，并且將他們映射到物理內存中任意位置的k個任意物理頁面，因此操作系統沒有必要分配k個連續的物理內存頁面，頁面可以隨機的分散在物理內存中。
虛擬內存作為內存保護的工具。不應該允許一個用戶進程修改它的只讀段，也不允許它修改任何內核代碼和數據結構，不允許讀寫其他進程的私有內存，不允許修改任何與其他進程共享的虛擬頁面。每次CPU生成一個地址時，MMU會讀一個PTE，通過在PTE上添加一些額外的許可位來控制對一個虛擬頁面內容的訪問十分簡單。
常見的頁面置換算法
當訪問一個內存中不存在的頁，并且內存已滿，則需要從內存中調出一個頁或將數據送至磁盤對換區，替換一個頁，這種現象叫做缺頁置換。當前操作系統最常采用的缺頁置換算法如下：
- 先進先出(FIFO)算法：
- 思路：置換最先調入內存的頁面，即置換在內存中駐留時間最久的頁面。
- 實現：按照進入內存的先后次序排列成隊列，從隊尾進入，從隊首刪除。
- 特點：實現簡單;性能較差，調出的頁面可能是經常訪問的
- 最近最少使用(LRU)算法:
- 思路：置換最近一段時間以來最長時間未訪問過的頁面。根據程序局部性原理，剛被訪問的頁面，可能馬上又要被訪問;而較長時間內沒有被訪問的頁面，可能最近不會被訪問。
- 實現：缺頁時，計算內存中每個邏輯頁面的上一次訪問時間，選擇上一次使用到當前時間最長的頁面
- 特點：可能達到最優的效果，維護這樣的訪問鏈表開銷比較大
當前最常采用的就是LRU算法。
- 最不常用算法(Least Frequently Used, LFU)
- 思路：缺頁時，置換訪問次數最少的頁面
- 實現：每個頁面設置一個訪問計數，訪問頁面時，訪問計數加1，缺頁時，置換計數最小的頁面
- 特點：算法開銷大，開始時頻繁使用，但以后不使用的頁面很難置換
請說一下什么是寫時復制?
- 如果有多個進程要讀取它們自己的那部門資源的副本，那么復制是不必要的。每個進程只要保存一個指向這個資源的指針就可以了。只要沒有進程要去修改自己的“副本”，就存在著這樣的幻覺：每個進程好像獨占那個資源。從而就避免了復制帶來的負擔。如果一個進程要修改自己的那份資源“副本”，那么就會復制那份資源，并把復制的那份提供給進程。不過其中的復制對進程來說是透明的。這個進程就可以修改復制后的資源了，同時其他的進程仍然共享那份沒有修改過的資源。所以這就是名稱的由來：在寫入時進行復制。
- 寫時復制的主要好處在于：如果進程從來就不需要修改資源，則不需要進行復制。惰性算法的好處就在于它們盡量推遲代價高昂的操作，直到必要的時刻才會去執行。
- 在使用虛擬內存的情況下，寫時復制(Copy-On-Write)是以頁為基礎進行的。所以，只要進程不修改它全部的地址空間，那么就不必復制整個地址空間。在fork()調用結束后，父進程和子進程都相信它們有一個自己的地址空間，但實際上它們共享父進程的原始頁，接下來這些頁又可以被其他的父進程或子進程共享。
實時操作系統的概念
實時操作系統(Real-time operating system, RTOS)，又稱即時操作系統，它會按照排序運行、管理系統資源，并為開發應用程序提供一致的基礎。實時操作系統與一般的操作系統相比，最大的特色就是“實時性”，如果有一個任務需要執行，實時操作系統會馬上(在較短時間內)執行該任務，不會有較長的延時。這種特性保證了各個任務的及時執行。
優先級反轉是什么?如何解決
由于多進程共享資源，具有最高優先權的進程被低優先級進程阻塞，反而使具有中優先級的進程先于高優先級的進程執行，導致系統的崩潰。這就是所謂的優先級反轉(Priority Inversion)。其實,優先級反轉是在高優級(假設為A)的任務要訪問一個被低優先級任務(假設為C)占有的資源時,被阻塞.而此時又有優先級高于占有資源的任務(C)而低于被阻塞的任務(A)的優先級的任務(假設為B)時,于是,占有資源的任務就被掛起(占有的資源仍為它占有),因為占有資源的任務優先級很低,所以,它可能一直被另外的任務掛起.而它占有的資源也就一直不能釋放,這樣,引起任務A一直沒辦法執行.而比它優先低的任務卻可以執行。
目前解決優先級反轉有許多種方法。其中普遍使用的有2種方法：一種被稱作優先級繼承(priority inheritance);另一種被稱作優先級極限(priority ceilings)。
- 優先級繼承(priority inheritance) 優先級繼承是指將低優先級任務的優先級提升到等待它所占有的資源的最高優先級任務的優先級.當高優先級任務由于等待資源而被阻塞時,此時資源的擁有者的優先級將會自動被提升。
- 優先級天花板(priority ceilings)優先級天花板是指將申請某資源的任務的優先級提升到可能訪問該資源的所有任務中最高優先級任務的優先級.(這個優先級稱為該資源的優先級天花板)。
