作業系統面試要點

程序與線程

主要掌握程序與線程的差別和聯系

程序是系統資源配置設定的最小機關,線程是程式執行的最小機關；

程序使用獨立的資料空間,線程共享程序的資料空間；

線程排程

簡單了解幾種線程排程算法以及這兩個衡量批處理系統的排程性能

• 周轉時間：作業結束完成時間-作業進入系統時間
• 帶權周轉時間：周轉時間/所需運作時間

先來先服務排程

• 政策：在到達系統的一批作業中，先來先服務算法（FCFS）按照作業進入系統的先後次序挑選作業，先進入系統優先被挑選，這是一種非剝奪式算法；
• 效果：有利于CPU繁忙型作業，不利于I/O繁忙型作業；

優先級排程

• 政策：優先級排程算法根據确定的優先級選取程序/線程，每次總是選擇就緒隊列中優先級最高者運作；優先級排程算法可以采用剝奪或者非剝奪方式，如果就緒隊列中出現優先級更高的程序/線程，剝奪式排程可立刻執行該程序/線程，非剝奪式等待目前運作程序結束或者出現等待時間主動讓出處理器後，才會排程另一程序投入運作。
• 優先級規定者有是使用者或系統；
• 優先級還可分為靜态優先級和動态優先級；

多級回報隊列排程

• 多級回報隊列排程算法建立兩個或多個就緒程序隊列，每個隊列賦予不同的優先級，較高優先級一般配置設定給較短的時間片。處理器每次從高優先級就緒隊列中選取可占用處理器的程序，隻有在無程序時，才會從較低優先級就緒隊列中選取程序，同一隊列中的程序按照先來先服務原則排隊。開始工作時，新錦成首先進入高優先級隊列等候排程，若能在該優先級的一個時間片内執行完成則程序撤離系統，否則進入低一級隊列等候排程，若處理器正在執行低優先級隊列程序時，若新的程序到達高優先級就緒隊列，則處理器暫停目前低優先級隊列程序的執行，轉而執行高優先級隊列中新到程序，是以，多級回報隊列排程是一種剝奪式排程。
• 不足：多級回報隊列排程存在饑餓問題，當新的程序不斷到來時，低優先級隊列中的程序将長時間得不到排程

時間片輪轉排程

• 排程程式每次将CPU配置設定給就緒隊列中的首程序使用一個時間片，就緒隊列中的每個程序輪流運作一個時間片，當這個時間片耗盡時，強迫目前線程讓出處理器，排到就緒隊列尾部，等候下一輪排程。是一種剝奪式排程，系統消耗在程序切換上的開銷比較大，那麼時間片大小的選取就顯得非常重要。

高響應比優先排程

• 響應比=1+已等待時間/作業處理時間
• 政策：每當排程一個作業的時，都要計算後背作業隊中每個作業的響應比，選擇響應比最高者投入運作。對于FCFS，隻考慮使用者等待時間，對于SJF，隻考慮計算時間，而高響應比優先排程（HRRF）采用的響應比既考慮了等待時間又考慮了作業處理時間，是以是二者折中的排程算法，是一種非剝奪式排程。

程序/線程切換的步驟

程序上下文

程序上下文包含了程序執行所需的所有資訊

• 使用者位址空間：包括程式代碼，資料，使用者堆棧等；
• 控制資訊：程序描述符，核心棧等；
• 硬體上下文：（注意中斷也要儲存硬體上下文隻是儲存的方法不同）。

程序切換的步驟

• .切換頁目錄以使用新的位址空間
• 切換核心棧
• 切換硬體上下文

線程切換與程序切換的對比

• 對于linux來說，線程和程序的最大差別就在于位址空間。對于線程切換，第1步是不需要做的，第2和3步是程序和線程切換都要做的。是以明顯是程序切換代價大

線程切換與程序切換的代價對比

• 線程上下文切換和程序上下文切換一個最主要的差別是線程的切換虛拟記憶體空間依然是相同的，但是程序切換是不同的。這兩種上下文切換的處理都是通過作業系統核心來完成的。核心的這種切換過程伴随的最顯著的性能損耗是将寄存器中的内容切換出。
• 外一個隐藏的損耗是上下文的切換會擾亂處理器的緩存機制。簡單的說，一旦去切換上下文，處理器中所有已經緩存的記憶體位址一瞬間都廢棄了。還有一個顯著的差別是當你改變虛拟記憶體空間的時候，處理的頁表緩沖（processor’s Translation Lookaside Buffer (TLB)）或者相當的神馬東西會被全部重新整理，這将導緻記憶體的通路在一段時間内相當的低效。但是線上程的切換中，不會出現這個問題。

程序間通信 IPC

共享存儲

在記憶體中建立一個共享空間，兩個程序對共享空間的通路必須是互斥的（互斥通路通過作業系統提供的工具實作），作業系統隻提供共享空間和同步操作工具（P V操作）。

共享存儲分為兩種

• 一種是基于資料結構的共享：比如共享空間隻能存放一個長度為10 的數組，這種共享方式速度慢、限制多，是一種低級通信方式。
• 另一種是基于存儲區的共享：在記憶體中劃出一塊共享存儲區，資料的形式、存放位置都由程序控制，而不是作業系統，是一種進階通信方式。

管道通信

• 管道：管道是指用于連接配接讀寫程序的一個共享檔案，又名pipe檔案。其實就是在記憶體中開辟一個大小固定的緩沖區。管道之恩那個采用半雙工通信，如果要實作雙向同時通信，則需要設定兩個管道。
• 各程序要互斥的通路管道
• 資料以字元流的形式寫入管道，當管道寫滿時，寫程序的write()系統調用将被阻塞，等待讀程序将資料取走。當讀程序将資料全部取走後，管道變空，此時程序的read()系統調用将會被阻塞。
• 如果沒寫滿，就不允許讀，如果沒讀空，就不允許寫。
• 資料一旦被讀出，就從管道中被抛棄，這就意味着讀程序最多隻能有一個，否則會有都錯資料的情況。

消息傳遞

• 程序間資料交換以格式化的資訊為機關。程序通過作業系統提供的“發送消息/接收消息”兩個原語進行資料交換
• 格式化的消息分為消息頭和消息體：消息頭包括：發送程序ID、接受程序ID、消息類型、消息長度等格式化的資訊（計算機網絡中發送的封包其實就是一種格式化的消息）

消息傳遞有兩種方式

• 直接通信方式：将消息直接挂到接受程序消息緩沖隊列上。
• 簡介通信方式：将消息發送到中間實體（信箱）中，是以也稱為信箱通信方式。

協程

簡單了解協程更輕量化，是在使用者态進行排程，切換的代價比線程上下文切換低很多

了解：極高的執行效率：因為子程式切換不是線程切換，而是由程式自身控制，是以，沒有線程切換的開銷，和多線程比，線程數量越多，協程的性能優勢就越明顯；不需要多線程的鎖機制：因為隻有一個線程，也不存在同時寫變量沖突，在協程中控制共享資源不加鎖，隻需要判斷狀态就好了，是以執行效率比多線程高很多。

了解一些Java的第三方協程架構，比如Kilim 、Fiber .

Linux常用指令

重點掌握awk top netstat grep less tail

記憶體分頁管理與Swap機制（了解）

記憶體分頁

分頁存儲管理将全部記憶體分成長度相等的若幹份，每一塊稱為一個實體塊或頁框，作業也自動被系統分為于每個實體塊相等的若幹份，每一份稱為一頁或者一個頁面。

Swap機制

當Linux記憶體不足時就會觸發swap(交換)機制, swap機制是什麼東西呢?

swap機制其實就是将外存(如硬碟)當記憶體使用, 怎麼可以把外存當記憶體使用呢? 原理就是當系統記憶體不夠用的時候, 核心會選擇某些程序, 把其使用較少的記憶體的内容交換(swap)到外存中,然後把記憶體讓給需要的程序使用.

那麼Linux核心會把哪些記憶體交換到外存去呢? 在新版的Linux核心會使用LRU算法計算出那些使用比較少的記憶體交換到外存中.

任務隊列與CPU Load（了解）

CPU使用率:顯示的是程式在運作期間實時占用的CPU百分比

CPU負載:顯示的是一段時間内正在使用和等待使用CPU的平均任務數。CPU使用率高，并不意味着負載就一定大。

上圖1個電話亭可以了解為一個CPU核心。從上圖的過程中可以看到load的概念，而使用率始終100%。

擴充知識點(了解)

記憶體屏障

記憶體屏障,也稱 記憶體栅欄， 記憶體栅障， 屏障指令等， 是一類 同步屏障指令，使得CPU或編譯器在對記憶體随機通路的操作中的一個同步點，使得此點之前的所有讀寫操作都執行後才可以開始執行此點之後的操作

指令亂序

隻要是熟悉計算機底層系統的同學就會知道，程式裡面的每行代碼的執行順序，有可能會被編譯器和cpu根據某種政策，給打亂掉，目的是為了性能的提升，讓指令的執行能夠盡可能的并行起來。知道指令的亂序政策很重要，原因是這樣我們就能夠通過barrier等指令，在正确的位置告訴cpu或者是編譯器，這裡我可以接受亂序，那裡我不能接受亂序等等。進而，能夠在保證代碼正确性的前提下，最大限度地發揮機器的性能。

亂序執行就是說把原來 有序執行的 指令清單，在保證執行結果一緻的情況下 根據 指令依賴關系及指令執行周期 重新安排執行順序。例如以下指令（a = 1;b=a;c=2;d=c）在CPU中就很可能被重排序成為以下的執行順序（a=1;c=2;b=a;d=c;），這樣的話，4條指令都可以高效的在流水線中運轉了。

分支預測

從P5時代開始的一種先進的資料處理方法，由CPU來判斷程式分支的進行方向，能夠更快運算速度。

CPU親和性（affinty）

分為軟親和性和硬親和性

軟親和性

硬親和性

Netfilter與iptables