程序和執行緒基礎知識
程序：程序是系統進行資源分配和排程的一個獨立單位，是系統中的並行執行的單位。
執行緒：執行緒是程序的一個實體，也是 CPU 排程和分派的基本單位，它是比程序更小的能獨立執行的基本單位，有時又被稱為輕權程序或輕量級程序。
程序
執行中的程式，就被稱為「程序」（Process）。
在一個程序的活動期間至少具備三種基本狀態，即執行狀態、就緒狀態、阻塞狀態。
當然，程序還有另外兩個基本狀態：
掛起狀態可以分為兩種：
PCB 過程控制塊 是程序存在的唯一標識
PCB 具體包含什麼資訊呢？
程序描述資訊：
程序控制和管理資訊：
資源分配清單：
CPU 相關資訊：
執行緒
執行緒是程序當中的一條執行流程。
同一個程序內多個執行緒之間可以共用程式碼段、資料段、開啟的檔案等資源，但每個執行緒各自都有一套獨立的暫存器和棧，這樣可以確保執行緒的控制流是相對獨立的。
執行緒的實現
主要有三種執行緒的實現方式：
第一種關係是多對一的關係，也就是多個使用者執行緒對應同一個核心執行緒
第二種是一對一的關係，也就是一個使用者執行緒對應一個核心執行緒
第三種是多對多的關係，也就是多個使用者執行緒對應到多個核心執行緒
使用者執行緒的整個執行緒管理和排程，作業系統是不直接參與的，而是由使用者級執行緒庫函數來完成執行緒的管理，包括執行緒的建立、終止、同步和排程等。
執行緒的優點：
執行緒的缺點：
核心執行緒是由作業系統管理的，執行緒對應的 TCB 自然是放在作業系統裡的，這樣執行緒的建立、終止和管理都是由作業系統負責。
程序/執行緒上下文切換
程序
一個程序切換到另一個程序執行，稱為程序的上下文切換。
程序的上下文切換到底是切換什麼呢？
程序是由核心管理和排程的，所以程序的切換隻能發生在核心態。
所以，程序的上下文切換不僅包含了虛擬記憶體、棧、全域性變數等使用者空間的資源，還包括了核心堆疊、暫存器等核心空間的資源。
通常，會把交換的資訊儲存在程序的 PCB，當要執行另外一個程序的時候，我們需要從這個程序的 PCB 取出上下文，然後恢復到 CPU 中，這使得這個程序可以繼續執行
發生程序上下文切換有哪些場景？
執行緒
執行緒上下文切換的是什麼？
這還得看執行緒是不是屬於同一個程序：
所以，執行緒的上下文切換相比程序，開銷要小很多。
程序/執行緒間通訊方式
程序間通訊（IPC，InterProcess Communication）是指在不同程序之間傳播或交換資訊。IPC 的方式通常有管道（包括無名管道和命名管道）、訊息佇列、號誌、共用儲存、Socket、Streams 等。其中 Socket 和 Streams 支援不同主機上的兩個程序 IPC。
管道
命名管道
訊息佇列
號誌
共用記憶體
Socket通訊
前面說到的通訊機制，都是工作於同一臺主機，如果要與不同主機的程序間通訊，那麼就需要 Socket 通訊了。Socket 實際上不僅用於不同的主機程序間通訊，還可以用於本地主機程序間通訊，可根據建立 Socket 的型別不同，分為三種常見的通訊方式，一個是基於 TCP 協定的通訊方式，一個是基於 UDP 協定的通訊方式，一個是本地程序間通訊方式。
以上，就是程序間通訊的主要機制了。你可能會問了，那執行緒通訊間的方式呢？
同個程序下的執行緒之間都是共用程序的資源，只要是共用變數都可以做到執行緒間通訊，比如全域性變數，所以對於執行緒間關注的不是通訊方式，而是關注多執行緒競爭共用資源的問題，號誌也同樣可以線上程間實現互斥與同步：
執行緒、程序崩潰發生什麼
一般來說如果執行緒是因為非法存取記憶體引起的崩潰，那麼程序肯定會崩潰，為什麼系統要讓程序崩潰呢，這主要是因為在程序中，各個執行緒的地址空間是共用的，既然是共用，那麼某個執行緒對地址的非法存取就會導致記憶體的不確定性，進而可能會影響到其他執行緒，這種操作是危險的，作業系統會認為這很可能導致一系列嚴重的後果，於是乾脆讓整個程序崩潰
崩潰機制
注意上面的第五步，如果程序沒有註冊自己的訊號處理常式，那麼作業系統會執行預設的訊號處理程式（一般最後會讓程序退出），但如果註冊了，則會執行自己的訊號處理常式，這樣的話就給了程序一個垂死掙扎的機會，它收到 kill 訊號後，可以呼叫 exit() 來退出，但也可以使用 sigsetjmp，siglongjmp 這兩個函數來恢復程序的執行
守護行程、殭屍程序和孤兒程序
守護行程
指在後臺執行的，沒有控制終端與之相連的程序。它獨立於控制終端，週期性地執行某種任務。Linux的大多數伺服器就是用守護行程的方式實現的，如web伺服器程序http等
建立守護行程要點：
（1）讓程式在後臺執行。方法是呼叫fork（）產生一個子程序，然後使父程序退出。
（2）呼叫setsid（）建立一個新對話期。控制終端、登入對談和行程群組通常是從父程序繼承下來的，守護行程要擺脫它們，不受它們的影響，方法是呼叫setsid（）使程序成為一個對談組長。setsid（）呼叫成功後，程序成為新的對談組長和行程群組長，並與原來的登入對談、行程群組和控制終端脫離。
（3）禁止程序重新開啟控制終端。經過以上步驟，程序已經成為一個無終端的對談組長，但是它可以重新申請開啟一個終端。為了避免這種情況發生，可以通過使程序不再是對談組長來實現。再一次通過fork（）建立新的子程序，使呼叫fork的程序退出。
（4）關閉不再需要的檔案描述符。子程序從父程序繼承開啟的檔案描述符。如不關閉，將會浪費系統資源，造成程序所在的檔案系統無法卸下以及引起無法預料的錯誤。首先獲得最高檔案描述符值，然後用一個迴圈程式，關閉0到最高檔案描述符值的所有檔案描述符。
（5）將當前目錄更改為根目錄。
（6）子程序從父程序繼承的檔案建立遮蔽字可能會拒絕某些許可權。為防止這一點，使用unmask（0）將遮蔽字清零。
（7）處理SIGCHLD訊號。對於伺服器程序，在請求到來時往往生成子程序處理請求。如果子程序等待父程序捕獲狀態，則子程序將成為殭屍程序（zombie），從而佔用系統資源。如果父程序等待子程序結束，將增加父程序的負擔，影響伺服器程序的並行效能。在Linux下可以簡單地將SIGCHLD訊號的操作設為SIG_IGN。這樣，子程序結束時不會產生殭屍程序。
孤兒程序
如果父程序先退出，子程序還沒退出，那麼子程序的父程序將變為init程序。（注：任何一個程序都必須有父程序）。
一個父程序退出，而它的一個或多個子程序還在執行，那麼那些子程序將成為孤兒程序。孤兒程序將被init程序(程序號為1)所收養，並由init程序對它們完成狀態收集工作。
殭屍程序
如果子程序先退出，父程序還沒退出，那麼子程序必須等到父程序捕獲到了子程序的退出狀態才真正結束，否則這個時候子程序就成為殭屍程序。
設定殭屍程序的目的是維護子程序的資訊，以便父程序在以後某個時候獲取。這些資訊至少包括程序ID，程序的終止狀態，以及該程序使用的CPU時間，所以當終止子程序的父程序呼叫wait或waitpid時就可以得到這些資訊。如果一個程序終止，而該程序有子程序處於殭屍狀態，那麼它的所有殭屍子程序的父程序ID將被重置為1（init程序）。繼承這些子程序的init程序將清理它們（也就是說init程序將wait它們，從而去除它們的殭屍狀態）。
如何避免殭屍程序
第一種方法忽略SIGCHLD訊號，這常用於並行伺服器的效能的一個技巧因為並行伺服器常常fork很多子程序，子程序終結之後需要伺服器程序去wait清理資源。如果將此訊號的處理方式設為忽略，可讓核心把殭屍子程序轉交給init程序去處理，省去了大量殭屍程序佔用系統資源。
程序和執行緒的比較
執行緒是排程的基本單位，而程序則是資源擁有的基本單位。
執行緒與程序的比較如下：
對於，執行緒相比程序能減少開銷，體現在：
所以，不管是時間效率，還是空間效率執行緒比程序都要高。
1、執行緒啟動速度快，輕量級
2、執行緒的系統開銷小
3、執行緒使用有一定難度，需要處理資料一致性問題
4、同一執行緒共用的有堆、全域性變數、靜態變數、指標，參照、檔案等，而獨自佔有棧
實體地址、邏輯地址、虛擬記憶體的概念
虛擬記憶體有什麼好處
記憶體管理
記憶體管理的概念就是作業系統對記憶體的劃分和動態分配。
記憶體管理功能：
記憶體空間的分配與回收：由作業系統完成主記憶體儲器空間的分配和管理，是程式設計師擺脫儲存分配的麻煩，提高程式設計效率。
地址轉換：將邏輯地址轉換成相應的實體地址。
記憶體空間的擴充：利用虛擬儲存技術或自動覆蓋技術，從邏輯上擴充主記憶體。
儲存保護：保證各道作業在各自的儲存空間內執行，互不干擾。
建立程序首先要將程式和資料裝入記憶體。將使用者源程式變為可在記憶體中執行的程式，通常需要以下幾個步驟：
編譯：由編譯程式將使用者原始碼編譯成若干目標模組（把高階語言翻譯成機器語言）
連結：由連結程式將編譯後形成的一組目標模組及所需的庫函數連線在一起，形成一個完整的裝入模組（由目標模組生成裝入模組，連結後形成完整的邏輯地址）
裝入：由裝入程式將裝入模組裝入記憶體執行，裝入後形成實體地址
程式的連結有以下三種方式：
靜態連結：在程式執行之前，先將各目標模組及它們所需的庫函數連線成一個完整的可執行檔案（裝入模組），之後不再拆開。
裝入時動態連結：將各目標模組裝入記憶體時，邊裝入邊連結的連結方式。
執行時動態連結：在程式執行中需要該目標模組時，才對它進行連結。其優點是便於修改和更新，便於實現對目標模組的共用。
記憶體的裝入模組在裝入記憶體時，有以下三種方式：
重定位：根據記憶體的當前情況，將裝入模組裝入記憶體的適當位置，裝入時對目標程式中的指令和資料的修改過程稱為重定位。
靜態重定位：地址的變換通常是在裝入時一次完成的。一個作業裝入記憶體時，必須給它分配要求的全部記憶體空間，若沒有足夠的記憶體，則不能裝入該作業。此外，作業一旦裝入記憶體，整個執行期間就不能在記憶體中移動，也不能再申請記憶體空間。
動態重定位：需要重定位暫存器的支援。可以將程式分配到不連續的儲存區中；在程式執行之前可以只裝入它的部分程式碼即可投入執行，然後在程式執行期間，根據需要動態申請分配記憶體。
記憶體分配前，需要保護作業系統不受使用者程序的影響，同時保護使用者程序不受其他使用者程序的影響。記憶體保護可採取如下兩種方法：
在CPU中設定一對上、下限暫存器，存放使用者作業在主記憶體中的上限和下限地址，每當CPU要存取一個地址時，分別和兩個暫存器的值相比，判斷有無越界。
採用重定位暫存器（或基址暫存器）和界地址暫存器（又稱限長記憶體）來實現這種保護。重定位暫存器包含最小的實體地址值，界地址暫存器含邏輯地址的最大值。每個邏輯地址值必須小於界地址暫存器；記憶體管理機構動態得將邏輯地址與界地址暫存器進行比較，若未發生地址越界，則加上重定位暫存器的值後對映成實體地址，再送交記憶體單元。
常見的記憶體分配方式
（1） 從靜態儲存區域分配。記憶體在程式編譯的時候就已經分配好，這塊記憶體在程式的整個執行期間都存在。例如全域性變數，static變數。
（2） 在棧上建立。在執行函數時，函數內區域性變數的儲存單元都可以在棧上建立，函數執行結束時這些儲存單元自動被釋放。棧記憶體分配運算內建於處理器的指令集中，效率很高，但是分配的記憶體容量有限。
（3） 從堆上分配，亦稱動態記憶體分配。程式在執行的時候用malloc或new申請任意多少的記憶體，程式設計師自己負責在何時用free或delete釋放記憶體。動態記憶體的生存期由我們決定，使用非常靈活，但問題也最多。
常見記憶體分配記憶體錯誤
（1）記憶體分配未成功，卻使用了它。
（2）記憶體分配雖然成功，但是尚未初始化就參照它。
（3）記憶體分配成功並且已經初始化，但操作越過了記憶體的邊界。
（4）忘記了釋放記憶體，造成記憶體洩露。
（5）釋放了記憶體卻繼續使用它。常見於以下有三種情況：
malloc如何分配記憶體
從作業系統層面上看，malloc是通過兩個系統呼叫來實現的： brk和mmap
通常，分配的記憶體小於128k時，使用brk呼叫來獲得虛擬記憶體，大於128k時就使用mmap來獲得虛擬記憶體。
程序先通過這兩個系統呼叫獲取或者擴大程序的虛擬記憶體，獲得相應的虛擬地址，在存取這些虛擬地址的時候，通過缺頁中斷，讓核心分配相應的實體記憶體，這樣記憶體分配才算完成。
如何避免預讀失效和快取汙染
預讀失效
這些被提前載入進來的頁，並沒有被存取，相當於這個預讀工作是白做了，這個就是預讀失效。
傳統的 LRU 演演算法法無法避免下面這兩個問題：
為了避免「預讀失效」造成的影響，Linux 和 MySQL 對傳統的 LRU 連結串列做了改進：
快取汙染
如果這些大量的資料在很長一段時間都不會被存取的話，那麼整個活躍 LRU 連結串列（或者 young 區域）就被汙染了。
為了避免「快取汙染」造成的影響，Linux 作業系統和 MySQL Innodb 儲存引擎分別提高了升級為熱點資料的門檻：
Linux 作業系統：在記憶體頁被存取第二次的時候，才將頁從 inactive list 升級到 active list 裡。
MySQL Innodb：在記憶體頁被存取
第二次
的時候，並不會馬上將該頁從 old 區域升級到 young 區域，因為還要進行
停留在 old 區域的時間判斷：
通過提高了進入 active list （或者 young 區域）的門檻後，就很好了避免快取汙染帶來的影響。
實體記憶體管理
作業系統實體記憶體管理主要包括程式裝入、交換技術、連續分配管理方式和非連續分配管理方式（分頁、分段、段分頁）。
連續分配管理方式
連續記憶體分配
記憶體碎片
當給程式分配空間時，可能會出現一些無法被利用的空閒碎片空間。
1.外部碎片：分配單元之間無法被利用的記憶體碎片
2.內部碎片：分配給任務記憶體大小大於任務所需記憶體大小時，多出來的記憶體碎片。
分割區的動態分配
連續記憶體分配情況：將應用程式從硬碟載入到記憶體中，給記憶體分配一塊記憶體。應用程式執行存取資料，資料的連續記憶體空間。
記憶體分配演演算法：
具體問題具體分析適配演演算法。
首次適配：
定義：使用第一塊記憶體大小大於需求大小的可用空閒塊
實現方法：需要有一個按地址排序的空閒塊列表。尋找第一個滿足記憶體需求的空閒塊。對於回收，要考慮空閒塊與相鄰空閒塊合併問題。
優點：簡單，易於產生更大的空閒塊，想著地址空間結尾分配
缺點：產生外部碎片，具有不確定性
最優適配：
定義：尋找整個空閒塊中，最滿足分配請求的空閒塊，記憶體差值最小。
實現方法：需要有一個按尺寸排序的空閒塊列表，尋找最滿足分配的記憶體塊。對於回收，要考慮空閒塊與相鄰空閒塊合併問題。
優點：避免分割大空閒塊，最小化外部碎片的產生，簡單
缺點：外部碎片很細，有很多微小碎片，不利於後續分配管理。
最差適配：
定義：找到差距最大的記憶體空閒塊。
實現：需要有一個按尺寸排序的空閒塊列表，尋找差距最大的記憶體塊。對於回收，要考慮空閒塊與相鄰空閒塊合併問題。
優點：避免產生微小外部碎片，分配效率高，適用於分配中大快
缺點：對於大塊請求帶來一定影響
減少記憶體碎片方法
緊緻：壓縮式碎片整理
調整執行程式的位置。
1.重定位的時機。不能在程式執行時進行，可以在程式等待時拷貝。
2.記憶體拷貝開銷很大。
swaping：交換式碎片整理
把硬碟作為一個備份。把等待的程式包括資料（主記憶體）挪到硬碟上。當硬碟上程式需要執行時再拷貝到主記憶體上。
1.交換那個程式，減小開銷
2.交換的時機
非連續記憶體分配
連續記憶體分配和非連續記憶體分配
連續記憶體分配缺點：1.分配給一個程式的實體記憶體是連續的，記憶體利用率較低，由外碎片內碎片的問題。
非連續記憶體分配優點：1.程式實體地址是非連續的 2.更好的記憶體利用和管理 3.允許共用程式碼與資料 4.支援動態載入和動態連結
非連續記憶體分配缺點：建立虛擬地址到實體地址的對映，軟體開銷太大，可以用硬體支援
-》硬體兩種管理方案：分段和分頁
分段
分段地址空間
對於一段程式記憶體可以分為：程式（主程式+子程式+共用庫）+變數（棧、堆、共用資料段）
分段：更好的分離與共用，將邏輯地址空間分散到多個實體地址空間
邏輯地址是連續的，將具有不同功能的對映到物理空間中，這些段大小不一，位置不一
硬體實現分段定址機制
一維邏輯地址有不同段組成，首先將邏輯地址分為兩段：段定址（段號）+段偏移定址（addr）
通過段號在段表找到邏輯記憶體的段起始地址，看段起始地址是否滿足段大小限制，不滿足返回記憶體異常，滿足將邏輯地址加偏移量是實體地址。
段表：
1.儲存邏輯地址段段號到實體地址段號之間的對映關係
2.儲存段大小，起始地址
段表的建立：作業系統在定址前建立。
分頁
分頁地址空間
需要頁號和頁地址偏移。相比分段，分頁頁幀大小固定不變。
可以劃分實體記憶體至固定大小的幀，將邏輯地址的頁也劃分至相同記憶體大小。大小是2的冪。
建立方案
頁幀（Frame）：實體記憶體被分割為大小相等的幀
一個記憶體實體地址是一個二元組（f,o）
實體地址 = 2^S*f+o
f是幀號（F位，2F個幀），o是幀內偏移（S位，每幀2S位元組）,
頁（Page）：邏輯地址空間分割為大小相等的頁
頁內偏移大小 = 幀內偏移大小（頁幀大小和頁大小一致）
頁號大小和幀號大小可能不一致
一個邏輯地址是一個二元組（p,o）
邏輯地址 = 2^S*p+o
p:頁號（P位，2P個頁），o：頁內偏移（S位，每頁2S個位元組）
頁定址機制
CPU定址（邏輯地址），邏輯地址包含兩部分（p，o），首先把p（頁號）作為索引，再加上頁表基址查頁表（pagetable）中對應幀號（實體地址中f），知道幀號加上頁內偏移就是實體地址（f，o）。
頁表：以頁號為索引的對應的幀號（實體地址），為此需要知道頁表的基址位置（頁號從哪個地址開始查）。
頁表的建立：作業系統初始化時，enable分頁機制前就需要建立好
分頁與分段：
分頁：相比分段，分頁頁記憶體固定，導致頁內偏移大小範圍是固定的。不需要想分段一樣考慮分頁大小不一致的問題。
邏輯地址和實體地址空間
1.總邏輯頁大小和總物理幀大小不一致，一般邏輯地址空間大於實體地址空間。
2.邏輯地址空間連續，實體地址空間不連續。減少內外碎片。
頁表
頁表結構
頁表是個陣列，索引是頁號，對應的陣列項內容裡有幀號。
分頁機制效能問題
1.時間開銷：存取一個記憶體單元需要兩次記憶體存取
頁表不能放在CPU裡，只能放在記憶體裡，CPU先做記憶體定址找頁表基址，再進行頁表存取，進行兩次記憶體存取，存取速度很慢
2空間代價：頁表佔用空間
1.64位元計算機，每頁1KB，頁表大小？2^54個數的頁表，很大
2.多個程式有多個頁表
解決方法
時間上：快取 ——快表，TLB，Translation Look-aside Buffer
TLB：
位於CPU中的一塊快取區域，存放常用的頁號-幀號對，採用關聯記憶體的方式實現，具有快速存取功能。
-CPU定址時會先通過頁號在TLB查詢，看是否存在頁號的Key，對應得到幀號，進而得到實體地址（減少對實體地址的存取）。TLB未命中，把該項更新到TLB中（x86CPU這個過程是硬體完成，對於mps是作業系統完成）。
編寫程式時，把存取的地址寫在一個頁號裡。
空間上：間接存取（多級頁表機制），以時間換空間
二級頁表：
對於邏輯地址（p1,p2,o）
CPU定址時先通過p1查詢一級頁表，一級頁表中存放的是二級頁表的p2的起始地址，再在二級頁表對應起始地址查詢偏移p2，對應存放的就是幀號。提高時間開銷，但一級頁表中不存在頁表項就不需要佔用二級頁表項的記憶體，節省空間。
多級頁表
頁號分為K個部分，建立頁表「樹」
快表
快表，又稱聯想暫存器(TLB) ，是一種存取速度比記憶體快很多的高速緩衝記憶體，用來存放當前存取的若干頁表項，以加速地址變換的過程。與此對應，記憶體中的頁表常稱為慢表。
| 地址變換過程 | 存取一個邏輯地址的訪存次數 | |
|---|---|---|
| 基本地址變換機構 | ①算頁號、頁內偏移量 ②檢查頁號合法性 ③查頁表，找到頁面存放的記憶體塊號 ④根據記憶體塊號與頁內偏移量得到實體地址 ⑤存取目標記憶體單元 | 兩次訪存 |
| 具有快表的地址變換機構 | ①算頁號、頁內偏移量 ②檢查頁號合法性 ③查快表。若命中，即可知道頁面存放的記憶體塊號，可直接進行⑤;若未命中則進行④ ④查頁表，找到頁面存放的記憶體塊號，並且將頁表項複製到快表中 ⑤根據記憶體塊號與頁內偏移量得到實體地址 ⑥存取目標記憶體單元 | 快表命中，只需一次訪存 快表未命中，需要兩次訪存 |
記憶體交換技術
交換(對換)技術的設計思想：記憶體空間緊張時，系統將記憶體中某些程序暫時換出外存，把外存中某些已具備執行條件的程序換入記憶體(程序在記憶體與磁碟間動態排程)
換入：把準備好競爭CPU執行的程式從輔存移到記憶體。 換出：把處於等待狀態（或CPU排程原則下被剝奪執行權力）的程式從記憶體移到輔存，把記憶體空間騰出來。
交換時機：記憶體交換通常在許多程序執行且記憶體吃緊時進行，而系統負荷降低就暫停。例如:在發現許多程序執行時經常發生缺頁，就說明記憶體緊張，此時可以換出一些程序;如果缺頁率明顯下降，就可以暫停換出。
關鍵點
分頁與分段的區別
程序排程演演算法詳細介紹
選擇一個程序執行這一功能是在作業系統中完成的，通常稱為排程程式（scheduler）。
排程時機
在程序的生命週期中，當程序從一個執行狀態到另外一狀態變化的時候，其實會觸發一次排程。
比如，以下狀態的變化都會觸發作業系統的排程：
因為，這些狀態變化的時候，作業系統需要考慮是否要讓新的程序給 CPU 執行，或者是否讓當前程序從 CPU 上退出來而換另一個程序執行。
另外，如果硬體時鐘提供某個頻率的週期性中斷，那麼可以根據如何處理時鐘中斷 ，把排程演演算法分為兩類：
排程原則
排程演演算法
排程演演算法是指：根據系統的資源分配策略所規定的資源分配演演算法。常用的排程演演算法有：先來先服務排程演演算法、時間片輪轉排程法、短作業優先排程演演算法、最短剩餘時間優先、高響應比優先排程演演算法、優先順序排程演演算法等等。
先來先服務排程演演算法是一種最簡單的排程演演算法，也稱為先進先出或嚴格排隊方案。當每個程序就緒後，它加入就緒佇列。當前正執行的程序停止執行，選擇在就緒佇列中存在時間最長的程序執行。該演演算法既可以用於作業排程，也可以用於程序排程。先來先服務比較適合於常作業（程序），而不利於段作業（程序）。
時間片輪轉排程演演算法主要適用於分時系統。在這種演演算法中，系統將所有就緒程序按到達時間的先後次序排成一個佇列，程序排程程式總是選擇就緒佇列中第一個程序執行，即先來先服務的原則，但僅能執行一個時間片。
短作業優先排程演演算法是指對短作業優先排程的演演算法，從後備佇列中選擇一個或若干個估計執行時間最短的作業，將它們調入記憶體執行。 短作業優先排程演演算法是一個非搶佔策略，他的原則是下一次選擇預計處理時間最短的程序，因此短程序將會越過長作業，跳至佇列頭。
最短剩餘時間是針對最短程序優先增加了搶佔機制的版本。在這種情況下，程序排程總是選擇預期剩餘時間最短的程序。當一個程序加入到就緒佇列時，他可能比當前執行的程序具有更短的剩餘時間，因此只要新程序就緒，排程程式就能可能搶佔當前正在執行的程序。像最短程序優先一樣，排程程式正在執行選擇函數是必須有關於處理時間的估計，並且存在長程序飢餓的危險。
高響應比優先排程演演算法主要用於作業排程，該演演算法是對 先來先服務排程演演算法和短作業優先排程演演算法的一種綜合平衡，同時考慮每個作業的等待時間和估計的執行時間。在每次進行作業排程時，先計算後備作業佇列中每個作業的響應比，從中選出響應比最高的作業投入執行。
優先順序排程演演算法每次從後備作業佇列中選擇優先順序最髙的一個或幾個作業，將它們調入記憶體，分配必要的資源，建立程序並放入就緒佇列。在程序排程中，優先順序排程演演算法每次從就緒佇列中選擇優先順序最高的程序，將處理機分配給它，使之投入執行。
磁碟排程演演算法詳細介紹
常見的磁碟排程演演算法有：
先來先服務
先來先服務（First-Come，First-Served，FCFS），顧名思義，先到來的請求，先被服務。
最短尋道時間優先
最短尋道時間優先（Shortest Seek First，SSF）演演算法的工作方式是，優先選擇從當前磁頭位置所需尋道時間最短的請求
掃描演演算法
最短尋道時間優先演演算法會產生飢餓的原因在於：磁頭有可能再一個小區域內來回得移動。
為了防止這個問題，可以規定：磁頭在一個方向上移動，存取所有未完成的請求，直到磁頭到達該方向上的最後的磁軌，才調換方向，這就是掃描（*Scan*）演演算法。
這種演演算法也叫做電梯演演算法，比如電梯保持按一個方向移動，直到在那個方向上沒有請求為止，然後改變方向。
迴圈掃描演演算法
掃描演演算法使得每個磁軌響應的頻率存在差異，那麼要優化這個問題的話，可以總是按相同的方向進行掃描，使得每個磁軌的響應頻率基本一致。
迴圈掃描（Circular Scan, CSCAN ）規定：只有磁頭朝某個特定方向移動時，才處理磁軌存取請求，而返回時直接快速移動至最靠邊緣的磁軌，也就是復位磁頭，這個過程是很快的，並且返回中途不處理任何請求，該演演算法的特點，就是磁軌只響應一個方向上的請求。
LOOK 與 C-LOOK演演算法
掃描演演算法和迴圈掃描演演算法，都是磁頭移動到磁碟「最始端或最末端」才開始調換方向。
那這其實是可以優化的，優化的思路就是磁頭在移動到「最遠的請求」位置，然後立即反向移動。
針對 SCAN 演演算法的優化叫 LOOK 演演算法，它的工作方式，磁頭在每個方向上僅僅移動到最遠的請求位置，然後立即反向移動，而不需要移動到磁碟的最始端或最末端，反向移動的途中會響應請求。
針對C-SCAN 演演算法的優化叫 C-LOOK，它的工作方式，磁頭在每個方向上僅僅移動到最遠的請求位置，然後立即反向移動，而不需要移動到磁碟的最始端或最末端，反向移動的途中不會響應請求。
頁面置換演演算法詳細介紹
請求調頁，也稱按需調頁，即對不在記憶體中的「頁」，當程序執行時要用時才調入，否則有可能到程式結束時也不會調入。而記憶體中給頁面留的位置是有限的，在記憶體中以幀為單位放置頁面。為了防止請求調頁的過程出現過多的記憶體頁面錯誤（即需要的頁面當前不在記憶體中，需要從硬碟中讀資料，也即需要做頁面的替換）而使得程式執行效率下降，我們需要設計一些頁面置換演演算法，頁面按照這些演演算法進行相互替換時，可以儘量達到較低的錯誤率。常用的頁面置換演演算法如下：
先進先出，即淘汰最早調入的頁面。
選未來最遠將使用的頁淘汰，是一種最優的方案，可以證明缺頁數最小。
即選擇最近最久未使用的頁面予以淘汰
時鐘置換演演算法也叫最近未用演演算法 NRU（Not RecentlyUsed）。該演演算法為每個頁面設定一位存取位，將記憶體中的所有頁面都通過連結指標鏈成一個迴圈佇列。
什麼是零拷貝
為了提高檔案傳輸的效能，於是就出現了零拷貝技術，它通過一次系統呼叫（sendfile 方法）合併了磁碟讀取與網路傳送兩個操作，降低了上下文切換次數。另外，拷貝資料都是發生在核心中的，天然就降低了資料拷貝的次數。
Kafka 和 Nginx 都有實現零拷貝技術，這將大大提高檔案傳輸的效能。
零拷貝技術是基於 PageCache 的，PageCache 會快取最近存取的資料，提升了存取快取資料的效能，同時，為了解決機械硬碟定址慢的問題，它還協助 I/O 排程演演算法實現了 IO 合併與預讀，這也是順序讀比隨機讀效能好的原因。這些優勢，進一步提升了零拷貝的效能。
I/O多路複用
既然為每個請求分配一個程序/執行緒的方式不合適，那有沒有可能只使用一個程序來維護多個 Socket 呢？答案是有的，那就是 I/O 多路複用技術。
一個程序雖然任一時刻只能處理一個請求，但是處理每個請求的事件時，耗時控制在 1 毫秒以內，這樣 1 秒內就可以處理上千個請求，把時間拉長來看，多個請求複用了一個程序，這就是多路複用，這種思想很類似一個 CPU 並行多個程序，所以也叫做時分多路複用。
我們熟悉的 select/poll/epoll 核心提供給使用者態的多路複用系統呼叫，程序可以通過一個系統呼叫函數從核心中獲取多個事件。
select/poll/epoll 是如何獲取網路事件的呢？在獲取事件時，先把所有連線（檔案描述符）傳給核心，再由核心返回產生了事件的連線，然後在使用者態中再處理這些連線對應的請求即可。
select/poll/epoll
select 和 poll 並沒有本質區別，它們內部都是使用「線性結構」來儲存程序關注的 Socket 集合。
在使用的時候，首先需要把關注的 Socket 集合通過 select/poll 系統呼叫從使用者態拷貝到核心態，然後由核心檢測事件，當有網路事件產生時，核心需要遍歷程序關注 Socket 集合，找到對應的 Socket，並設定其狀態為可讀/可寫，然後把整個 Socket 集合從核心態拷貝到使用者態，使用者態還要繼續遍歷整個 Socket 集合找到可讀/可寫的 Socket，然後對其處理。
很明顯發現，select 和 poll 的缺陷在於，當用戶端越多，也就是 Socket 集合越大，Socket 集合的遍歷和拷貝會帶來很大的開銷，因此也很難應對 C10K。
epoll 是解決 C10K 問題的利器，通過兩個方面解決了 select/poll 的問題。
而且，epoll 支援邊緣觸發和水平觸發的方式，而 select/poll 只支援水平觸發，一般而言，邊緣觸發的方式會比水平觸發的效率高。
高效能網路模式：Reactor和Proactor
常見的 Reactor 實現方案有三種。
第一種方案單 Reactor 單程序 / 執行緒，不用考慮程序間通訊以及資料同步的問題，因此實現起來比較簡單，這種方案的缺陷在於無法充分利用多核 CPU，而且處理業務邏輯的時間不能太長，否則會延遲響應，所以不適用於計算機密集型的場景，適用於業務處理快速的場景，比如 Redis（6.0之前 ） 採用的是單 Reactor 單程序的方案。
第二種方案單 Reactor 多執行緒，通過多執行緒的方式解決了方案一的缺陷，但它離高並行還差一點距離，差在只有一個 Reactor 物件來承擔所有事件的監聽和響應，而且只在主執行緒中執行，在面對瞬間高並行的場景時，容易成為效能的瓶頸的地方。
第三種方案多 Reactor 多程序 / 執行緒，通過多個 Reactor 來解決了方案二的缺陷，主 Reactor 只負責監聽事件，響應事件的工作交給了從 Reactor，Netty 和 Memcache 都採用了「多 Reactor 多執行緒」的方案，Nginx 則採用了類似於 「多 Reactor 多程序」的方案。
Reactor 可以理解為「來了事件作業系統通知應用程序，讓應用程序來處理」，而 Proactor 可以理解為「來了事件作業系統來處理，處理完再通知應用程序」。
因此，真正的大殺器還是 Proactor，它是採用非同步 I/O 實現的非同步網路模型，感知的是已完成的讀寫事件，而不需要像 Reactor 感知到事件後，還需要呼叫 read 來從核心中獲取資料。
不過，無論是 Reactor，還是 Proactor，都是一種基於「事件分發」的網路程式設計模式，區別在於 Reactor 模式是基於「待完成」的 I/O 事件，而 Proactor 模式則是基於「已完成」的 I/O 事件。
一致性雜湊介紹
一致性雜湊是指將「儲存節點」和「資料」都對映到一個首尾相連的雜湊環上，如果增加或者移除一個節點，僅影響該節點在雜湊環上順時針相鄰的後繼節點，其它資料也不會受到影響。
但是一致性雜湊演演算法不能夠均勻的分佈節點，會出現大量請求都集中在一個節點的情況，在這種情況下進行容災與擴容時，容易出現雪崩的連鎖反應。
為了解決一致性雜湊演演算法不能夠均勻的分佈節點的問題，就需要引入虛擬節點，對一個真實節點做多個副本。不再將真實節點對映到雜湊環上，而是將虛擬節點對映到雜湊環上，並將虛擬節點對映到實際節點，所以這裡有「兩層」對映關係。
引入虛擬節點後，可以會提高節點的均衡度，還會提高系統的穩定性。所以，帶虛擬節點的一致性雜湊方法不僅適合硬體設定不同的節點的場景，而且適合節點規模會發生變化的場景。
什麼是死鎖和產生死鎖原因
死鎖，是指多個程序在執行過程中因爭奪資源而造成的一種僵局，當程序處於這種僵持狀態時，若無外力作用，它們都將無法再向前推進。 如下圖所示：如果此時有一個執行緒 A，已經持有了鎖 A，但是試圖獲取鎖 B，執行緒 B 持有鎖 B，而試圖獲取鎖 A，這種情況下就會產生死鎖。
產生死鎖原因
由於系統中存在一些不可剝奪資源，而當兩個或兩個以上程序佔有自身資源，並請求對方資源時，會導致每個程序都無法向前推進，這就是死鎖。
例如：系統中只有一臺印表機，可供程序 A 使用，假定 A 已佔用了印表機，若 B 繼續要求印表機列印將被阻塞。
系統中的資源可以分為兩類：
例如：程序 A 和 程序 B 互相等待對方的資料。
死鎖產生的必要條件？
如何避免死鎖
預防死鎖、避免死鎖、檢測死鎖、解除死鎖
預防死鎖
解除死鎖
什麼是悲觀鎖、樂觀鎖
悲觀鎖做事比較悲觀，它認為多執行緒同時修改共用資源的概率比較高，於是很容易出現衝突，所以存取共用資源前，先要上鎖。
樂觀鎖做事比較樂觀，它假定衝突的概率很低，它的工作方式是：先修改完共用資源，再驗證這段時間內有沒有發生衝突，如果沒有其他執行緒在修改資源，那麼操作完成，如果發現有其他執行緒已經修改過這個資源，就放棄本次操作。
可見，樂觀鎖的心態是，不管三七二十一，先改了資源再說。另外，你會發現樂觀鎖全程並沒有加鎖，所以它也叫無鎖程式設計。
互斥鎖、自旋鎖、讀寫鎖，都是屬於悲觀鎖。
哲學家進餐問題
生產者-消費者問題描述：
我們對問題分析可以得出：
那麼我們需要三個號誌，分別是：
mutex：用於互斥存取緩衝區，初始化值為 1；fullBuffers：用於消費者詢問緩衝區是否有資料，有資料則讀取資料，初始化值為 0（表明緩衝區一開始為空）；emptyBuffers：用於生產者詢問緩衝區是否有空位，有空位則生成資料，初始化值為 n （緩衝區大小）；如果消費者執行緒一開始執行 P(fullBuffers)，由於號誌 fullBuffers 初始值為 0，則此時 fullBuffers 的值從 0 變為 -1，說明緩衝區裡沒有資料，消費者只能等待。
接著，輪到生產者執行 P(emptyBuffers)，表示減少 1 個空槽，如果當前沒有其他生產者執行緒在臨界區執行程式碼，那麼該生產者執行緒就可以把資料放到緩衝區，放完後，執行 V(fullBuffers) ，號誌 fullBuffers 從 -1 變成 0，表明有「消費者」執行緒正在阻塞等待資料，於是阻塞等待的消費者執行緒會被喚醒。
消費者執行緒被喚醒後，如果此時沒有其他消費者執行緒在讀資料，那麼就可以直接進入臨界區，從緩衝區讀取資料。最後，離開臨界區後，把空槽的個數 + 1。
生產者、消費者問題
哲學家就餐的問題描述：
5 個老大哥哲學家，閒著沒事做，圍繞著一張圓桌吃麵；5 支叉子，每兩個哲學家之間放一支叉子；一、讓偶數編號的哲學家「先拿左邊的叉子後拿右邊的叉子」，奇數編號的哲學家「先拿右邊的叉子後拿左邊的叉子」。
在 P 操作時，根據哲學家的編號不同，拿起左右兩邊叉子的順序不同。另外，V 操作是不需要分支的，因為 V 操作是不會阻塞的。
二、用一個陣列 state 來記錄每一位哲學家的三個狀態，分別是在進餐狀態、思考狀態、飢餓狀態（正在試圖拿叉子）。
那麼，一個哲學家只有在兩個鄰居都沒有進餐時，才可以進入進餐狀態。
上面的程式使用了一個號誌陣列，每個號誌對應一位哲學家，這樣在所需的叉子被佔用時，想進餐的哲學家就被阻塞。
讀者寫者問題
讀者只會讀取資料，不會修改資料，而寫者即可以讀也可以修改資料。
讀者-寫者的問題描述：
使用號誌的方式來嘗試解決：
wMutex：控制寫操作的互斥號誌，初始值為 1 ；rCount：正在進行讀操作的讀者個數，初始化為 0；rCountMutex：控制對 rCount 讀者計數器的互斥修改，初始值為 1；這種實現，是讀者優先的策略，因為只要有讀者正在讀的狀態，後來的讀者都可以直接進入，如果讀者持續不斷進入，則寫者會處於飢餓狀態。
那既然有讀者優先策略，自然也有寫者優先策略：
在方案一的基礎上新增如下變數：
rMutex：控制讀者進入的互斥號誌，初始值為 1；wDataMutex：控制寫者寫操作的互斥號誌，初始值為 1；wCount：記錄寫者數量，初始值為 0；wCountMutex：控制 wCount 互斥修改，初始值為 1；注意，這裡 rMutex 的作用，開始有多個讀者讀資料，它們全部進入讀者佇列，此時來了一個寫者，執行了 P(rMutex) 之後，後續的讀者由於阻塞在 rMutex 上，都不能再進入讀者佇列，而寫者到來，則可以全部進入寫者佇列，因此保證了寫者優先。
同時，第一個寫者執行了 P(rMutex) 之後，也不能馬上開始寫，必須等到所有進入讀者佇列的讀者都執行完讀操作，通過 V(wDataMutex) 喚醒寫者的寫操作。
既然讀者優先策略和寫者優先策略都會造成飢餓的現象，那麼我們就來實現一下公平策略。
公平策略：
對並行和並行的理解
什麼是使用者態和核心態
使用者態和核心態是作業系統的兩種執行狀態。
核心態：處於核心態的 CPU 可以存取任意的資料，包括外圍裝置，比如網路卡、硬碟等，處於核心態的 CPU 可以從一個程式切換到另外一個程式，並且佔用 CPU 不會發生搶佔情況，一般處於特權級 0 的狀態我們稱之為核心態。使用者態：處於使用者態的 CPU 只能受限的存取記憶體，並且不允許存取外圍裝置，使用者態下的 CPU 不允許獨佔，也就是說 CPU 能夠被其他程式獲取。兩大區域性性原理是什麼
主要分為時間區域性性和空間區域性性。
時間區域性性:如果執行了程式中的某條指令，那麼不久後這條指令很有可能再次執行;如果某個資料被存取過，不久之後該資料很可能再次被存取。(因為程式中存在大量的迴圈)
空間區域性性:一旦程式存取了某個儲存單元，在不久之後，其附近的儲存單元也很有可能被存取。(因為很多資料在記憶體中都是連續存放的，並且程式的指令也是順序地在記憶體中存放的)
異常和中斷是什麼，有什麼區別
中斷
當我們在敲擊鍵盤的同時就會產生中斷，當硬碟讀寫完資料之後也會產生中斷，所以，我們需要知道，中斷是由硬體裝置產生的，而它們從物理上說就是電訊號，之後，它們通過中斷控制器傳送給CPU，接著CPU判斷收到的中斷來自於哪個硬體裝置（這定義在核心中），最後，由CPU傳送給核心，有核心處理中斷。
異常
CPU處理程式的時候一旦程式不在記憶體中，會產生缺頁異常；當執行除法程式時，當除數為0時，又會產生除0異常。所以，大家也需要記住的是，異常是由CPU產生的，同時，它會傳送給核心，要求核心處理這些異常。
相同點
不同點
原子操作
處理器使用基於對快取加鎖或匯流排加鎖的方式來實現多處理器之間的原子操作。首先處理器會自動保證基本的記憶體操作的原子性。處理器保證從系統記憶體中讀取或者寫入一個位元組是原子的，意思是當一個處理器讀取一個位元組時，其他處理器不能存取這個位元組的記憶體地址。Pentium 6和最新的處理器能自動保證單處理器對同一個快取行裡進行16/32/64位元的操作是原子的，但是複雜的記憶體操作處理器是不能自動保證其原子性的，比如跨匯流排寬度、跨多個快取行和跨頁表的存取。但是，處理器提供匯流排鎖定和快取鎖定兩個機制來保證複雜記憶體操作的原子性。
（1）使用匯流排鎖保證原子性 第一個機制是通過匯流排鎖保證原子性。
所謂匯流排鎖就是使用處理器提供的一個LOCK＃訊號，當一個處理器在匯流排上輸出此訊號時，其他處理器的請求將被阻塞住，那麼該處理器可以獨佔共用記憶體。
（2）使用快取鎖保證原子性 第二個機制是通過快取鎖定來保證原子性。
伺服器高並行解決方案
抖動你知道是什麼嗎？它也叫顛簸現象
剛剛換出的頁面馬上又要換入記憶體，剛剛換入的頁面馬上又要換出外存，這種頻繁的頁面排程行為稱為抖動，或顛簸。產生抖動的主要原因是程序頻繁存取的頁面數目高於可用的物理塊數(分配給程序的物理塊不夠)
為程序分配的物理塊太少，會使程序發生抖動現象。為程序分配的物理塊太多，又會降低系統整體的並行度，降低某些資源的利用率 為了研究為應該為每個程序分配多少個物理塊，Denning 提出了程序工作集」 的概念