?個人博客：https://blog.csdn.net/Newin2020?type=blog
📣專欄地址：https://blog.csdn.net/newin2020/category_12820365.html
📚專欄簡介：在這個專欄中，我將會分享操作系統面試中常見的面試題給大家~
??如果有收獲的話，歡迎點贊👍收藏📁，您的支持就是我創作的最大動力💪
163. 擴展調度算法
- 彩票調度：其基本思想是為進程提供各種系統資源（如 CPU 時間）的彩票。一旦需要做出一項調度決策時，就隨機抽出一張彩票，擁有該彩票的進程獲得該資源。
- 公平分享調度：在這種模式中，每個用戶分配到 CPU 時間的一部分，而調度程序以一種強制的方式選擇進程。這樣，如果兩個用戶都得到獲得 50% CPU 時間的保證，那么無論一個用戶有多少進程存在，每個用戶都會得到應有的 CPU 份額。
- CFS 調度算法：顧名思義就是完全公平調度。比方說，調度延遲時間是 10ms，存在兩個進程 A 和 B，那么兩個進程分別占用 CPU 的時間是 5ms。然而，階級總是存在的，畢竟有些進程高貴些，需要消耗更多的時間，因此引入了 nice 值。
- 假如 A 進程 nice 值是 0，對應的權重 prio_to_weight 是 1024；B進程 nice 值是 1，對應的權重 prio_to_weight 是 820。因此，相對應的，A 進程占用 CPU 的時間就變成了 10 * 1024 / (1024 + 820) 約 5.6ms，B 進程占用 CPU 時間 10 * 820 / (1024 + 820) 約 4.4ms。人善被人欺，nice 越大，獲取 CPU 的時間就越少。
- 此時分配給每個進程的運行時間=sched_latency_ns * 進程權重值 / 運行隊列上所有進程權重之和
164. 最佳頁面置換算法
最佳頁面置換算法基本思路是，置換在「未來」最長時間不訪問的頁面。
所以，該算法實現需要計算內存中每個邏輯頁面的「下一次」訪問時間，然后比較，選擇未來最長時間不訪問的頁面。
我們舉個例子，假設一開始有 3 個空閑的物理頁，然后有請求的頁面序列，那它的置換過程如下圖：
在這個請求的頁面序列中，缺頁共發生了 7 次（空閑頁換入 3 次 + 最優頁面置換 4 次），頁面置換共發生了 4 次。
這很理想，但是實際系統中無法實現，因為程序訪問頁面時是動態的，我們是無法預知每個頁面在「下一次」訪問前的等待時間。
所以，最佳頁面置換算法作用是為了衡量你的算法的效率，你的算法效率越接近該算法的效率，那么說明你的算法是高效的。
165. 先進先出置換算法
既然我們無法預知頁面在下一次訪問前所需的等待時間，那我們可以選擇在內存駐留時間很長的頁面進行中置換，這個就是「先進先出置換」算法的思想。
還是以前面的請求的頁面序列作為例子，假設使用先進先出置換算法，則過程如下圖：
在這個請求的頁面序列中，缺頁共發生了 10 次，頁面置換共發生了 7 次，跟最佳頁面置換算法比較起來，性能明顯差了很多。
)
