作為一個程序員，至少對操作系統(tǒng)是要有些了解的巍实，最近被問了幾次嚎货，主要是內(nèi)存分配算法的實現(xiàn)思路，其實這次過來復習不過是為了熟悉專業(yè)名詞蔫浆。正如上次被問到LRU,主要是不知道這東西是什么？
也發(fā)現(xiàn)其實關(guān)于線程的實現(xiàn)姐叁，其實當年學過...

連續(xù)內(nèi)存分配

最先匹配：First Fit Allocation

• 原理與實現(xiàn)：

  • 空閑分區(qū)列表按地址順序排序
  • 分配過程時瓦盛，搜索一個合適的分區(qū)
  • 釋放分區(qū)時，檢查是否可與臨近的空閑分區(qū)合并

• 優(yōu)點：

  • 簡單
  • 在高地址空間有大塊的空閑分區(qū)

• 缺點：

  • 外部碎片
  • 分配大塊時較慢

image.png

最佳匹配：Best Fit Allocation

思路：分配n字節(jié)分區(qū)時外潜， 查找并使用不小于n的最小空閑分區(qū)

• 原理與實現(xiàn)
  • 空閑分區(qū)列表按照大小排序
  • 分配時原环，查找一個合適的分區(qū)
  • 釋放時，查找并且合并臨近的空閑分區(qū)（如果找到）
• 優(yōu)點
  • 大部分分配的尺寸較小時处窥，效果很好
  • 可避免大的空閑分區(qū)被拆分
  • 可減小外部碎片的大小
  • 相對簡單
• 缺點
  • 外部碎片
  • 釋放分區(qū)較慢,合并相鄰分區(qū)的工作并不容易處理
  • 容易產(chǎn)生很多無用的小碎片

最差匹配: Worst Fit Allocation

思路：分配n字節(jié)嘱吗，使用尺寸不小于n的最大空閑分區(qū)

image.png

• 原理與實現(xiàn)

  • 空閑分區(qū)列表按由大到小排序
  • 分配時，選最大的分區(qū)
  • 釋放時，檢查是否可與臨近的空閑分區(qū)合并谒麦，進行可能的合并俄讹，并調(diào)整空閑分區(qū)列表順序

• 優(yōu)點

  • 中等大小的分配較多時，效果最好
  • 避免出現(xiàn)太多的小碎片

• 缺點

  • 釋放分區(qū)較慢
  • 外部碎片
  • 容易破壞大的空閑分區(qū)绕德，因此后續(xù)難以分配大的分區(qū)

連續(xù)內(nèi)存分配的缺點：

• 分配給程序的物理內(nèi)存必須連續(xù)
• 存在外部碎片和內(nèi)部碎片
• 內(nèi)存分配的動態(tài)修改困難
• 內(nèi)存利用率較低

非連續(xù)內(nèi)存

段地址空間

更細粒度和靈活的分離與共享

進程的段地址空間由多個段組成：

• 主代碼段
• 子模塊代碼段
• 公用庫代碼段
• 堆棧段(stack)
• 堆數(shù)據(jù)(heap)
• 初始化數(shù)據(jù)段
• 符號表等

• 段的概念
  • 段表示訪問方式和存儲數(shù)據(jù)等屬性相同 的一段地址空間
  • 對應(yīng)一個連續(xù)的內(nèi)存“塊”
  • 若干個段組成進程邏輯地址空間
• 段訪問：邏輯地址由二元組（s, addr）表示
  • s：段號
  • addr：段內(nèi)偏移

頁式存儲管理

• 頁幀（幀患膛、物理頁面, Frame, Page Frame）
  • 把物理地址空間劃分為大小相同的基本分配單位 ,$2^n$，如512, 4096, 8192
• 頁面（頁耻蛇、邏輯頁面, Page）
  • 把邏輯地址空間也劃分為相同大小的基本分配單位
• 頁面到頁幀
  • 邏輯地址到物理地址的轉(zhuǎn)換
  • 頁表
  • MMU/TLB

幀 (Frame):

物理內(nèi)存被劃分成大小相等的幀

內(nèi)存物理地址的表示：二元組 (f, o)

• f ：幀號 (F 位, 共有$2^F$ 個幀)
• o：幀內(nèi)偏移 (S 位, 每幀有$2^S$ 字節(jié))
• 物理地址：$f * 2^S + o$

頁(Page)

進程邏輯地址空間被劃分為大小相等的頁

頁內(nèi)偏移 = 幀內(nèi)偏移
通常：頁號大小 ≠ 幀號大小

進程邏輯地址的表示：二元組 (p, o)

• p：頁號 (P 位, $2^P$ 個頁)
• o：頁內(nèi)偏移 (S 位, 每頁有$2^S$ 字節(jié))
• 虛擬地址 $= p * 2^S + o $

頁式存儲中的地址映射

頁到幀的映射：邏輯地址中的頁號是連續(xù)的,映射到物理地址中的物理幀號就變成是不連續(xù)的

頁表

• 頁表保存了邏輯地址到物理地址之間的映射關(guān)系
• 每個進程擁有一個頁表踪蹬，隨著進程的變化而變化

頁式存儲管理機制的性能問題

• 訪問一個內(nèi)存單元需要2次內(nèi)存訪問
  • 第一次訪問：獲取頁表項
  • 第二次訪問：訪問數(shù)據(jù)
• 頁表大小問題：
  • 頁表可能非常大
  • 64位機器如果每頁1024字節(jié)，那么一個頁表的大小會是多少臣咖？
• 如何處理?
  • 緩存（Caching）
  • 間接（Indirection）訪問

段頁式存儲管理

在段式存儲管理基礎(chǔ)上跃捣，給每個段加一級頁表

頁置換

場景：內(nèi)存里所有幀都被分配了，無法將虛擬內(nèi)存中的頁映射到新的幀上

使用修改位夺蛇，只有修改過的才被回寫到硬盤

頁置換的基本方法

1. 查找所需頁在磁盤上的位置（假設(shè)頁已經(jīng)被寫到磁盤）
2. 查找一空閑幀
   • 如果有空閑幀疚漆，那么就使用它
   • 如果沒有空閑幀，那么就使用頁置換算法以選擇一個“犧牲”幀（victim frame）蚊惯。
   • 將“犧牲”幀的內(nèi)容寫到磁盤上（如果是臟頁）愿卸；改變頁表和幀表。
3. 將所需頁讀入（新）空閑幀截型；改變頁表和幀表
4. 重啟用戶進程趴荸。

頁面置換算法

• 局部頁面置換算法--------->當前進程占用的物理頁面內(nèi)

  • 最優(yōu)算法、先進先出算法宦焦、最近最久未使用算法
  • 時鐘算法发钝、最不常用算法

• 全局頁面置換算法-------->所有可換出的物理頁面

  • 工作集算法、缺頁率算法

最優(yōu)頁面置換算法(OPT, Optimal)

• 基本思路: 置換在未來最長時間不訪問的頁面

• 算法實現(xiàn):

  1. 缺頁時波闹，計算內(nèi)存中每個邏輯頁面的下一次訪問時間（無法計算）
  2. 選擇未來最長時間不訪問的頁面

• 算法特征

  • 缺頁最少酝豪，是理想情況
  • 實際系統(tǒng)中無法實現(xiàn)， 無法預知每個頁面在下次訪問前的等待時間
  • 作為置換算法的性能評價依據(jù)

先進先出算法（FIFO）

• 思路： 選擇在內(nèi)存駐留時間最長的頁面進行置換

• 實現(xiàn): 優(yōu)先隊列精堕。堆排序孵淘，鏈表實現(xiàn)

  1. 維護一個記錄所有位于內(nèi)存中的邏輯頁面鏈表：
  2. 鏈表元素按駐留內(nèi)存的時間排序，鏈首最長歹篓，鏈尾最短
  3. 出現(xiàn)缺頁時瘫证，選擇鏈首頁面進行置換，新頁面加到鏈尾

• 特征

  • 實現(xiàn)簡單
  • 性能較差庄撮，調(diào)出的頁面可能是經(jīng)常訪問的
  • 進程分配物理頁面數(shù)增加時背捌，缺頁并不一定減少Belady^[1]現(xiàn)象
  • 很少單獨使用

最近最久未使用算法（LRU）

LRU: Least Recently Used

• 思路

  • 選擇最長時間沒有被引用的頁面進行置換
  • 如某些頁面長時間未被訪問，則它們在將來還可能會長時間不會訪問洞斯。

• 實現(xiàn)

  • 缺頁時毡庆，計算內(nèi)存中每個邏輯頁面的上一次訪問時間
  • 選擇上一次使用到當前時間最長的頁面

• 特征

  • 最優(yōu)置換算法的一種近似，最優(yōu)置換是基于未來可知的。
  • 這里認為未來是過去的一種延續(xù)么抗，是基于過去的毅否。

• 每次使用完就把這個頁放到堆頂，把其他的頁往后挪乖坠。這里應(yīng)該是鏈表實現(xiàn)搀突。
• 缺頁就置換最后那個頁。
• 開銷比較大熊泵，很少計算機系統(tǒng)支持真正的LRU算法

時鐘置換算法（Clock）

• 思路

  • 僅對頁面的訪問情況進行大致統(tǒng)計

• 數(shù)據(jù)結(jié)構(gòu)

  • 在頁表項中增加訪問位(reference bit)仰迁，描述頁面在過去一段時間的內(nèi)訪問情況
  • 各頁面組織成環(huán)形鏈表（循環(huán)隊列）
  • 指針指向最先調(diào)入的頁面

• 算法

  • 訪問頁面時，在頁表項記錄頁面訪問情況
  • 缺頁時顽分，從指針處開始順序查找未被訪問的頁面進行置換

• 特征

  • 時鐘算法是LRU和FIFO的折中

• 時鐘置換算法的實現(xiàn)

  1. 頁面裝入內(nèi)存時徐许，訪問位初始化為0
  2. 訪問頁面（讀 寫 時，訪問位 置1
  3. 缺頁時卒蘸，從指針當前位置順序檢查環(huán)形鏈表
     • 訪問位為0 雌隅，則置換該頁
     • 訪問位為 1，則訪問位 置1 （相當于給該頁第二次機會）缸沃，并指針移動到下一個頁面恰起，直到找到可置換的頁面
  4. 所以也叫二次機會算法（Second chance Algorithm）

最不常用算法（LFU）

LFU： Least Frequently Used

• 思路
  • 缺頁時，置換訪問次數(shù)最少的頁面
• 實現(xiàn)
  • 每個頁面設(shè)置一個訪問計數(shù)
  • 訪問頁面時趾牧，訪問計數(shù)加
  • 缺頁時检盼，置換計數(shù)最小的頁面
• 特征
  • 算法開銷大
  • 開始時頻繁使用，但以后不使用的頁面很難置換
• 解決方法：計數(shù)定期右移（即計數(shù)減半）
  • LRU和LFU的區(qū)別
  • LRU關(guān)注多久未訪問翘单，LFU關(guān)注訪問次數(shù)

LRU吨枉、FIFO的比較

• LRU依據(jù)頁面的最近訪問時間排序

• LRU需要動態(tài)地調(diào)整順序

• FIFO依據(jù)頁面進入內(nèi)存的時間排序

• FIFO的頁面進入時間是固定不變的

• LRU可退化成FIFO

LRU、FIFO和Clock的比較

• LRU算法性能較好哄芜，但系統(tǒng)開銷較大貌亭。(需要維護優(yōu)先隊列)
• FIFO算法系統(tǒng)開銷較小，會發(fā)生Belady現(xiàn)象
• Clock算法是它們的折衷
  • 對于未被訪問的頁面认臊，Clock和LRU算法的表現(xiàn)一樣好
  • 對于被訪問過的頁面圃庭，Clock算法不能記錄準確訪問順序，而LRU算法可以

進程

組成

• 程序代碼（文本段text )
• 當前活動（PC和CPU寄存器）
• 堆棧段（stack）（包含臨時數(shù)據(jù)失晴，如函數(shù)參數(shù)冤议、返回地址和局部變量）
• 數(shù)據(jù)段（data）（包含全局變量）
• 堆（heap）（包含運行期間內(nèi)存的動態(tài)分配）

特點：

• 動態(tài)性
  可動態(tài)地創(chuàng)建、結(jié)束進程
• 并發(fā)性
  進程可以被獨立調(diào)度并占用處理機運行
• 獨立性
  不同進程的工作不相互影響
• 制約性
  因訪問共享數(shù)據(jù)/資源或進程間同步而產(chǎn)生制約

進程 = 執(zhí)行中的程序 = 程序 + 執(zhí)行狀態(tài)
進程 = CPU + 內(nèi)存

image.png

• 掛起(Suspend)：把一個進程從內(nèi)存轉(zhuǎn)到外存

線程：
優(yōu)點：

• 實體之間可以并發(fā)執(zhí)行
• 各個線程之間可以共享地址空間和文件等資源
  缺點：
• 一個線程崩潰师坎，會導致其所屬進程的所有線程崩潰

• 進程： 資源分配單位
  地址空間（代碼段、數(shù)據(jù)段）堪滨、打開的文件等各種資源

• 線程：處理機調(diào)度角色：指令流執(zhí)行狀態(tài)

  
  
  image.png

• 進程是資源分配單位胯陋，線程是CPU調(diào)度單位
• 進程擁有一個完整的資源平臺，而線程只獨享指令流執(zhí)行的必要資源，如寄存器和棧
• 線程具有就緒遏乔、等待和運行三種基本狀態(tài)和狀態(tài)間的轉(zhuǎn)換關(guān)系
• 線程能減少并發(fā)執(zhí)行的時間和空間開銷

線程的三種實現(xiàn)方式

• 用戶線程：在用戶空間實現(xiàn)
• 內(nèi)核線程：在內(nèi)核中實現(xiàn)
• 輕量級進程：在內(nèi)核中實現(xiàn)义矛，支持用戶線程

用戶線程

• 對操作系統(tǒng)內(nèi)核透明
• 不需要變態(tài)，速度快
• 實現(xiàn)靈活盟萨，每個線程都可以有自己的線程調(diào)度策略

• 實現(xiàn)復雜凉翻，容易一崩全崩，不支持搶占
• 按CPU分配給進程的時間再做分配捻激，時間少

內(nèi)核線程

• 由內(nèi)核維護PCB ^[2]和TCB^[3]
• 線程執(zhí)行系統(tǒng)調(diào)用而被阻塞不影響其他線程
• 占用內(nèi)核資源制轰，無法支持大量內(nèi)核線程
• 能做到按照CPU分配

輕量級進程

image.png

??內(nèi)核支持的用戶線程。一個進程可有一個或多個輕量級進程胞谭，每個輕量級進程由一個單獨的內(nèi)核線程來支持垃杖。

• 能夠做到由操作系統(tǒng)內(nèi)核通過輕量級線程來調(diào)度線程，防止一個線程阻塞導致進程癱瘓丈屹。
• 用戶線程通過LWP訪問內(nèi)核调俘，內(nèi)核通過LWP控制用戶線程。節(jié)省資源
• 支持大規(guī)模的UT（對于服務(wù)器這個至關(guān)重要）

1. Belady: 對有的頁置換算法旺垒，頁錯誤率可能會隨著所分配的
   幀數(shù)的增加而增加 ?

2. PCB: process Controller Block ?

3. TCB: Thread Controller Block ?