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

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

最先匹配：First Fit Allocation

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

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

• 優(yōu)點(diǎn)：

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

• 缺點(diǎn)：

  • 外部碎片
  • 分配大塊時(shí)較慢

image.png

最佳匹配：Best Fit Allocation

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

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

最差匹配: Worst Fit Allocation

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

image.png

• 原理與實(shí)現(xiàn)

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

• 優(yōu)點(diǎn)

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

• 缺點(diǎn)

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

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

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

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

段地址空間

更細(xì)粒度和靈活的分離與共享

進(jìn)程的段地址空間由多個(gè)段組成：

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

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

頁(yè)式存儲(chǔ)管理

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

幀 (Frame):

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

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

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

頁(yè)(Page)

進(jìn)程邏輯地址空間被劃分為大小相等的頁(yè)

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

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

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

頁(yè)式存儲(chǔ)中的地址映射

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

頁(yè)表

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

頁(yè)式存儲(chǔ)管理機(jī)制的性能問(wèn)題

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

段頁(yè)式存儲(chǔ)管理

在段式存儲(chǔ)管理基礎(chǔ)上，給每個(gè)段加一級(jí)頁(yè)表

頁(yè)置換

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

使用修改位，只有修改過(guò)的才被回寫到硬盤

頁(yè)置換的基本方法

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

頁(yè)面置換算法

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

  • 最優(yōu)算法、先進(jìn)先出算法、最近最久未使用算法
  • 時(shí)鐘算法、最不常用算法

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

  • 工作集算法、缺頁(yè)率算法

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

• 基本思路: 置換在未來(lái)最長(zhǎng)時(shí)間不訪問(wèn)的頁(yè)面

• 算法實(shí)現(xiàn):

  1. 缺頁(yè)時(shí)，計(jì)算內(nèi)存中每個(gè)邏輯頁(yè)面的下一次訪問(wèn)時(shí)間（無(wú)法計(jì)算）
  2. 選擇未來(lái)最長(zhǎng)時(shí)間不訪問(wèn)的頁(yè)面

• 算法特征

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

先進(jìn)先出算法（FIFO）

• 思路： 選擇在內(nèi)存駐留時(shí)間最長(zhǎng)的頁(yè)面進(jìn)行置換

• 實(shí)現(xiàn): 優(yōu)先隊(duì)列。堆排序，鏈表實(shí)現(xiàn)

  1. 維護(hù)一個(gè)記錄所有位于內(nèi)存中的邏輯頁(yè)面鏈表：
  2. 鏈表元素按駐留內(nèi)存的時(shí)間排序，鏈?zhǔn)鬃铋L(zhǎng)，鏈尾最短
  3. 出現(xiàn)缺頁(yè)時(shí)，選擇鏈?zhǔn)醉?yè)面進(jìn)行置換，新頁(yè)面加到鏈尾

• 特征

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

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

LRU: Least Recently Used

• 思路

  • 選擇最長(zhǎng)時(shí)間沒(méi)有被引用的頁(yè)面進(jìn)行置換
  • 如某些頁(yè)面長(zhǎng)時(shí)間未被訪問(wèn)，則它們?cè)趯?lái)還可能會(huì)長(zhǎng)時(shí)間不會(huì)訪問(wèn)。

• 實(shí)現(xiàn)

  • 缺頁(yè)時(shí)，計(jì)算內(nèi)存中每個(gè)邏輯頁(yè)面的上一次訪問(wèn)時(shí)間
  • 選擇上一次使用到當(dāng)前時(shí)間最長(zhǎng)的頁(yè)面

• 特征

  • 最優(yōu)置換算法的一種近似，最優(yōu)置換是基于未來(lái)可知的。
  • 這里認(rèn)為未來(lái)是過(guò)去的一種延續(xù)，是基于過(guò)去的。

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

時(shí)鐘置換算法（Clock）

• 思路

  • 僅對(duì)頁(yè)面的訪問(wèn)情況進(jìn)行大致統(tǒng)計(jì)

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

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

• 算法

  • 訪問(wèn)頁(yè)面時(shí)，在頁(yè)表項(xiàng)記錄頁(yè)面訪問(wèn)情況
  • 缺頁(yè)時(shí)，從指針處開(kāi)始順序查找未被訪問(wèn)的頁(yè)面進(jìn)行置換

• 特征

  • 時(shí)鐘算法是LRU和FIFO的折中

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

  1. 頁(yè)面裝入內(nèi)存時(shí)，訪問(wèn)位初始化為0
  2. 訪問(wèn)頁(yè)面（讀 寫 時(shí)，訪問(wèn)位 置1
  3. 缺頁(yè)時(shí)，從指針當(dāng)前位置順序檢查環(huán)形鏈表
     • 訪問(wèn)位為0 ，則置換該頁(yè)
     • 訪問(wèn)位為 1，則訪問(wèn)位 置1 （相當(dāng)于給該頁(yè)第二次機(jī)會(huì)），并指針移動(dòng)到下一個(gè)頁(yè)面，直到找到可置換的頁(yè)面
  4. 所以也叫二次機(jī)會(huì)算法（Second chance Algorithm）

最不常用算法（LFU）

LFU： Least Frequently Used

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

LRU、FIFO的比較

• LRU依據(jù)頁(yè)面的最近訪問(wèn)時(shí)間排序

• LRU需要?jiǎng)討B(tài)地調(diào)整順序

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

• FIFO的頁(yè)面進(jìn)入時(shí)間是固定不變的

• LRU可退化成FIFO

LRU、FIFO和Clock的比較

• LRU算法性能較好，但系統(tǒng)開(kāi)銷較大。(需要維護(hù)優(yōu)先隊(duì)列)
• FIFO算法系統(tǒng)開(kāi)銷較小，會(huì)發(fā)生Belady現(xiàn)象
• Clock算法是它們的折衷
  • 對(duì)于未被訪問(wèn)的頁(yè)面，Clock和LRU算法的表現(xiàn)一樣好
  • 對(duì)于被訪問(wèn)過(guò)的頁(yè)面，Clock算法不能記錄準(zhǔn)確訪問(wèn)順序，而LRU算法可以

進(jìn)程

組成

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

特點(diǎn)：

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

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

image.png

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

線程：
優(yōu)點(diǎn)：

• 實(shí)體之間可以并發(fā)執(zhí)行
• 各個(gè)線程之間可以共享地址空間和文件等資源
  缺點(diǎn)：
• 一個(gè)線程崩潰，會(huì)導(dǎo)致其所屬進(jìn)程的所有線程崩潰

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

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

  
  
  image.png

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

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

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

用戶線程

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

• 實(shí)現(xiàn)復(fù)雜，容易一崩全崩，不支持搶占
• 按CPU分配給進(jìn)程的時(shí)間再做分配，時(shí)間少

內(nèi)核線程

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

輕量級(jí)進(jìn)程

image.png

??內(nèi)核支持的用戶線程。一個(gè)進(jìn)程可有一個(gè)或多個(gè)輕量級(jí)進(jìn)程，每個(gè)輕量級(jí)進(jìn)程由一個(gè)單獨(dú)的內(nèi)核線程來(lái)支持。

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

1. Belady: 對(duì)有的頁(yè)置換算法，頁(yè)錯(cuò)誤率可能會(huì)隨著所分配的
   幀數(shù)的增加而增加 ?

2. PCB: process Controller Block ?

3. TCB: Thread Controller Block ?