一、程序執行過程

• 編譯：由編譯程序將用戶源代碼編譯成若干個目標模塊
• 鏈接：由鏈接程序將編譯后形成的一組目標模塊及所需的庫函數鏈接在一起，形成一個完整的裝入模塊
• 裝入：由裝入程序將裝入模塊裝入內存運行

裝入的三種方式

• 絕對裝入：在編譯時，如果知道程序將放到內存中的哪個位置，編譯程序將產生絕對地址的目標代碼。裝入程序按照裝入模塊中的地址，將程序和數據裝入內存。
• 靜態重定位：又稱可重定位裝入。編譯、鏈接后的裝入模塊的地址都是從0開始的，指令中使用的地址、數據存放的地址都是相對于起始地址而言的邏輯地址。可根據內存的當前情況，將裝入模塊裝入到內存的適當位置。裝入時對地址進行“重定位”，將邏輯地址變換為物理地址（地址變換是在裝入時一次完成的）。
• 動態重定位：又稱動態運行時裝入。編譯、鏈接后的裝入模塊的地址都是從0開始的。裝入程序把裝入模塊裝入內存后，并不會立即把邏輯地址轉換為物理地址，而是把地址轉換推遲到程序真正要執行時才進行。因此裝入內存后所有的地址依然是邏輯地址。這種方式需要一個重定位寄存器的支持。

鏈接的三種方式

• 靜態鏈接：在程序運行之前，先將各目標模塊及它們所需的庫函數連接成一個完整的可執行文件（裝入模塊），之后不再拆開。
• 裝入時動態鏈接：將各目標模塊裝入內存時，邊裝入邊鏈接的鏈接方式
• 運行時動態鏈接：在程序執行中需要該目標模塊時，才對它進行鏈接。其優點是便于修改和更新，便于實現對目標模塊的共享

二、內存管理的概念

內存空間的分配與回收

連續分配管理方式

單一連續分配

在單一連續分配方式中，內存被分為系統區和用戶區。系統區通常位于內存的低地址部分，用于存放操作系統相關數據；用戶區用于存放用戶進程相關數據。內存中只能有一道用戶程序，用戶程序獨占整個用戶區空間。

優點：實現簡單；無外部碎片；可以采用覆蓋技術擴充內存；不一定需要采取內存保護（eg：早期的 PC 操作系統 MS-DOS）。
缺點：只能用于單用戶、單任務的操作系統中；有內部碎片；存儲器利用率極低。

固定分區分配

操作系統需要建立一個數據結構——分區說明表，來實現各個分區的分配與回收。每個表項對應一個分區，通常按分區大小排列。每個表項包括對應分區的大小、起始地址、狀態（是否已分配）。

當某用戶程序要裝入內存時，由操作系統內核程序根據用戶程序大小檢索該表，從中找到一個能滿足大小的、未分配的分區，將之分配給該程序，然后修改狀態為“已分配”。

優點：實現簡單，無外部碎片。
缺點：

• 當用戶程序太大時，可能所有的分區都不能滿足需求，此時不得不采用覆蓋技術來解決，但這又會降低性能；
• 會產生內部碎片，內存利用率低。

動態分區分配

動態分區分配又稱為可變分區分配。這種分配方式不會預先劃分內存分區，而是在進程裝入內存時，根據進程的大小動態地建立分區，并使分區的大小正好適合進程的需要。因此系統分區的大小和數目是可變的。

空閑分區表：每個空閑分區對應一個表項。表項中包含分區號、分區大小、分區起始地址等信息

空閑分區鏈：每個分區的起始部分和末尾部分分別設置前向指針和后向指針。起始部分處還可記錄分區大小等信息。

首次適應算法

算法思想：每次都從低地址開始查找，找到第一個能滿足大小的空閑分區。

如何實現：空閑分區以地址遞增的次序排列。每次分配內存時順序查找空閑分區鏈（或空閑分區表），找到大小能滿足要求的第一個空閑分區。

最佳適應算法

算法思想：由于動態分區分配是一種連續分配方式，為各進程分配的空間必須是連續的一整片區域。因此為了保證當“大進程”到來時能有連續的大片空間，可以盡可能多地留下大片的空閑區，即，優先使用更小的空閑區。

如何實現：空閑分區按容量遞增次序鏈接。每次分配內存時順序查找空閑分區鏈（或空閑分區表），找到大小能滿足要求的第一個空閑分區

缺點：每次都選最小的分區進行分配，會留下越來越多的、很小的、難以利用的內存塊。因此這種方法會產生很多的外部碎片。

最壞適應算法

算法思想：為了解決最佳適應算法的問題——即留下太多難以利用的小碎片，可以在每次分配時優先使用最大的連續空閑區，這樣分配后剩余的空閑區就不會太小，更方便使用。

如何實現：空閑分區按容量遞減次序鏈接。每次分配內存時順序查找空閑分區鏈（或空閑分區表），找到大小能滿足要求的第一個空閑分區

缺點：每次都選最大的分區進行分配，雖然可以讓分配后留下的空閑區更大，更可用，但是這種方式會導致較大的連續空閑區被迅速用完。如果之后有“大進程”到達，就沒有內存分區可用了

鄰近適應算法

算法思想：首次適應算法每次都從鏈頭開始查找的。這可能會導致低地址部分出現很多小的空閑分區，而每次分配查找時，都要經過這些分區，因此也增加了查找的開銷。如果每次都從上次查找結束的位置開始檢索，就能解決上述問題。

如何實現：空閑分區以地址遞增的順序排列（可排成一個循環鏈表）。每次分配內存時從上次查找結束的位置開始查找空閑分區鏈（或空閑分區表），找到大小能滿足要求的第一個空閑分區

非連續分配管理方式

基本分頁存儲管理

為了能知道進程的每個頁面在內存中存放的位置，操作系統要為每個進程建立一張頁表。頁表通常存在PCB（進程控制塊）中

基本地址變換機構可以借助進程的頁表將邏輯地址轉換為物理地址。通常會在系統中設置一個頁表寄存器（PTR），存放頁表在內存中的起始地址F 和頁表長度M。進程未執行時，頁表的始址 和 頁表長度 放在進程控制塊（PCB）中，當進程被調度時，操作系統內核會把它們放到頁表寄存器中。

具有快表的地址變換機構
快表，又稱聯想寄存器（TLB， translation lookaside buffer ），是一種訪問速度比內存快很多的高速緩存（TLB不是內存！），用來存放最近訪問的頁表項的副本，可以加速地址變換的速度。與此對應，內存中的頁表常稱為慢表。

兩級頁表

主要為了解決單頁表在內存中需要許多的頁框來存儲，而在實際中可能就只需要常用的頁框在使用。

基本分段存儲管理方式

分段：進程的地址空間：按照程序自身的邏輯關系劃分為若干個段，每個段都有一個段名（在低級語言中，程序員使用段名來編程），每段從0開始編址

內存分配規則：以段為單位進行分配，每個段在內存中占據連續空間，但各段之間可以不相鄰

段表：程序分多個段，各段離散地裝入內存，為了保證程序能正常運行，就必須能從物理內存中找到各個邏輯段的存放位置。為此，需為每個進程建立一張段映射表，簡稱“段表”。

分段、分頁管理的對比

1. 頁是信息的物理單位。分頁的主要目的是為了實現離散分配，提高內存利用率。分頁僅僅是系統管理上的需要，完全是系統行為，對用戶是不可見的。

   段是信息的邏輯單位。分頁的主要目的是更好地滿足用戶需求。一個段通常包含著一組屬于一個邏輯模塊的信息。分段對用戶是可見的，用戶編程時需要顯式地給出段名。

2. 頁的大小固定且由系統決定。段的長度卻不固定，決定于用戶編寫的程序。

3. 分頁的用戶進程地址空間是一維的，程序員只需給出一個記憶符即可表示一個地址。

   分段的用戶進程地址空間是二維的，程序員在標識一個地址時，既要給出段名，也要給出段內地址。

4. 分段比分頁更容易實現信息的共享和保護。不能被修改的代碼稱為純代碼或可重入代碼（不屬于臨界資源），這樣的代碼是可以共享的。可修改的代碼是不能共享的

訪問一個邏輯地址需要幾次訪存？
分頁（單級頁表）：第一次訪存——查內存中的頁表，第二次訪存——訪問目標內存單元。總共兩次訪存
分段：第一次訪存——查內存中的段表，第二次訪存——訪問目標內存單元。總共兩次訪存
與分頁系統類似，分段系統中也可以引入快表機構，將近期訪問過的段表項放到快表中，這樣可以少一次訪問，加快地址變換速度

段頁式管理

三、內存空間的擴充

覆蓋技術

覆蓋技術的思想：將程序分為多個段（多個模塊）。常用的段常駐內存，不常用的段在需要時調入內存。內存中分為一個“固定區”和若干個“覆蓋區”，需要常駐內存的段放在“固定區”中，調入后就不再調出（除非運行結束）不常用的段放在“覆蓋區”，需要用到時調入內存，
用不到時調出內存。這樣程序運行的大小就小了。

交換技術

交換（對換）技術的設計思想：內存空間緊張時，系統將內存中某些進程暫時換出外存，把外存中某些已具備運行條件的進程換入內存（進程在內存與磁盤間動態調度）

1. 具有對換功能的操作系統中，通常把磁盤空間分為文件區和對換區兩部分。文件區主要用于存放文件，主要追求存儲空間的利用率，因此對文件區空間的管理采用離散分配方式；對換區空間只占磁盤空間的小部分，被換出的進程數據就存放在對換區。由于對換的速度直接影響到系統的整體速度，因此對換區空間的管理主要追求換入換出速度，因此通常對換區采用連續分配方式。總之，對換區的I/O速度比文件區的更快。
2. 交換通常在許多進程運行且內存吃緊時進行，而系統負荷降低就暫停。例如：在發現許多進程運行時經常發生缺頁，就說明內存緊張，此時可以換出一些進程；如果缺頁率明顯下降，就可以暫停換出。
3. 可優先換出阻塞進程；可換出優先級低的進程；為了防止優先級低的進程在被調入內存后很快又被換出，有的系統還會考慮進程在內存的駐留時間

四、虛擬內存

為什么要引入虛擬內存？
傳統存儲管理方式局由一次性和駐留性的特點

• 一次性：作業必須一次性全部裝入內存后才能開始運行。這會造成兩個問題：①作業很大時，不能全部裝入內存，導致大作業無法運行；②當大量作業要求運行時，由于內存無法容納所有作業，因此只有少量作業能運行，導致多道程序并發度下降。
• 駐留性：旦作業被裝入內存，就會一直駐留在內存中，直至作業運行結束。事實上，在一個時間段內，只需要訪問作業的一小部分數據即可正常運行，這就導致了內存中會駐留大量的、暫時用不到的數據，浪費了寶貴的內存資源。

同時運行一個程序會有時間局部性和空間局部性的特點。

• 時間局部性：如果執行了程序中的某條指令，那么不久后這條指令很有可能再次執行；如果某個數據被訪問過，不久之后該數據很可能再次被訪問。（因為程序中存在大量的循環）
• 空間局部性：一旦程序訪問了某個存儲單元，在不久之后，其附近的存儲單元也很有可能被訪問。（因為很多數據在內存中都是連續存放的，并且程序的指令也是順序地在內存中存放的）

虛擬內存有一下三個主要特征：

• 多次性：無需在作業運行時一次性全部裝入內存，而是允許被分成多次調入內存。
• 對換性：在作業運行時無需一直常駐內存，而是允許在作業運行過程中，將作業換入、換出。
• 虛擬性：從邏輯上擴充了內存的容量，使用戶看到的內存容量，遠大于實際的容量

虛擬內存的實現

虛擬內存技術，允許一個作業分多次調入內存。如果采用連續分配方式，會不方便實現。因此，虛擬內存的實現需要建立在離散分配的內存管理方式基礎上。

請求分頁管理

請求分頁存儲管理與基本分頁存儲管理的主要區別：
在程序執行過程中，當所訪問的信息不在內存時，由操作系統負責將所需信息從外存調入內存，然后繼續執行程序。若內存空間不夠，由操作系統負責將內存中暫時用不到的信息換出到外存。

缺頁中斷機制

在請求分頁系統中，每當要訪問的頁面不在內存時，便產生一個缺頁中斷，然后由操作系統的缺頁中斷處理程序處理中斷。此時缺頁的進程阻塞，放入阻塞隊列，調頁完成后再將其喚醒，放回就緒隊列。如果內存中有空閑塊，則為進程分配一個空閑塊，將所缺頁面裝入該塊，并修改頁表中相應的頁表項。

頁面置換算法

最佳置換算法（OPT）

最佳置換算法（OPT，Optimal）：每次選擇淘汰的頁面將是以后永不使用，或者在最長時間內不再被訪問的頁面，這樣可以保證最低的缺頁率。

先進先出置換算法（FIFO）

先進先出置換算法（FIFO）：每次選擇淘汰的頁面是最早進入內存的頁面
實現方法：把調入內存的頁面根據調入的先后順序排成一個隊列，需要換出頁面時選擇隊頭頁面即可。隊列的最大長度取決于系統為進程分配了多少個內存塊。

最近最久未使用置換算法（LRU)

最近最久未使用置換算法（LRU，least recently used）：每次淘汰的頁面是最近最久未使用的頁面
實現方法：賦予每個頁面對應的頁表項中，用訪問字段記錄該頁面自上次被訪問以來所經歷的時間t。當需要淘汰一個頁面時，選擇現有頁面中 t 值最大的，即最近最久未使用的頁面

例：假設系統為某進程分配了四個內存塊，并考慮到有以下頁面號引用串：
1, 8, 1, 7, 8, 2, 7, 2, 1, 8, 3, 8, 2, 1, 3, 1, 7, 1, 3, 7

時鐘置換算法（CLOCK）

簡單的CLOCK 算法實現方法：為每個頁面設置一個訪問位，再將內存中的頁面都通過鏈接指針鏈接成一個循環隊列。當某頁被訪問時，其訪問位置為1。當需要淘汰一個頁面時，只需檢查頁的訪問位。如果是0，就選擇該頁換出；如果是1，則將它置為0，暫不換出，繼續檢查下一個頁面，若第一輪掃描中所有頁面都是1，則將這些頁面的訪問位依次置為0后，再進行第二輪掃描（第二輪掃描中一定會有訪問位為0的頁面，因此簡單的CLOCK 算法選擇一個淘汰頁面最多會經過兩輪掃描）

改進型的時鐘置換算法

簡單的時鐘置換算法僅考慮到一個頁面最近是否被訪問過。事實上，如果被淘汰的頁面沒有被修改過，就不需要執行I/O操作寫回外存。只有被淘汰的頁面被修改過時，才需要寫回外存。因此，除了考慮一個頁面最近有沒有被訪問過之外，操作系統還應考慮頁面有沒有被修改過。在其他條件都相同時，應優先淘汰沒有修改過的頁面，避免I/O操作。這就是改進型的時鐘置換算法的思想。修改位=0，表示頁面沒有被修改過；修改位=1，表示頁面被修改過。為方便討論，用（訪問位，修改位）的形式表示各頁面狀態。如（1，1）表示一個頁面近期被訪問過，且被修改過。
算法規則：將所有可能被置換的頁面排成一個循環隊列

• 第一輪：從當前位置開始掃描到第一個（0, 0）的幀用于替換。本輪掃描 不修改任何標志位**（第一優先級：最近沒訪問，且沒修改的頁面）**
• 第二輪：若第一輪掃描失敗，則重新掃描，查找第一個（0, 1）的幀用于 替換。本輪將所有掃描過的幀訪問位設為0。(第二優先級：最近沒訪問，但修改過的頁面)
• 第三輪：若第二輪掃描失敗，則重新掃描，查找第一個（0, 0）的幀用于 替換。本輪掃描不修改任何標志位.(第三優先級：最近訪問過，但沒修改的頁面)
• 第四輪：若第三輪掃描失敗，則重新掃描，查找第一個（0, 1）的幀用于 替換。(第四優先級：最近訪問過，且修改過的頁面)

由于第二輪已將所有幀的訪問位設為0，因此經過第三輪、第四輪掃描一定會有一個幀被選中，因此改進型CLOCK置換算法選擇一個淘汰頁面最多會進行四輪掃描

頁面分配策略

駐留集：指請求分頁存儲管理中給進程分配的物理塊的集合。在采用了虛擬存儲技術的系統中，駐留集大小一般小于進程的總大小。若駐留集太小，會導致缺頁頻繁，系統要花大量的時間來處理缺頁，實際用于進程推進的時間很少；駐留集太大，又會導致多道程序并發度下降，資源利用率降低。所以應該選擇一個合適的駐留集大小。

固定分配：操作系統為每個進程分配一組固定數目的物理塊，在進程運行期間不再改變。即，駐留集大小不變

可變分配：先為每個進程分配一定數目的物理塊，在進程運行期間，可根據情況做適當的增加或減少。即，駐留集大小可變

局部置換：發生缺頁時只能選進程自己的物理塊進行置換。
全局置換：可以將操作系統保留的空閑物理塊分配給缺頁進程，也可以將別的進程持有的物理塊置換到外存，再分配給缺頁進程

三種策略

固定分配局部置換：系統為每個進程分配一定數量的物理塊，在整個運行期間都不改變。若進程在運行中發生缺頁，則只能從該進程在內存中的頁面中選出一頁換出，然后再調入需要的頁面。這種策略的缺點是：很難在剛開始就確定應為每個進程分配多少個物理塊才算合理。（采用這種策略的系統可以根據進程大小、優先級、或是根據程序員給出的參數來確定為一個進程分配的內存塊數）

可變分配全局置換：剛開始會為每個進程分配一定數量的物理塊。操作系統會保持一個空閑物理塊隊列。當某進程發生缺頁時，從空閑物理塊中取出一塊分配給該進程；若已無空閑物理塊，則可選擇一個未鎖定的頁面換出外存，再將該物理塊分配給缺頁的進程。采用這種策略時，只要某進程發生缺頁，都將獲得新的物理塊，僅當空閑物理塊用完時，系統才選擇一個未鎖定的頁面調出。被選擇調出的頁可能是系統中任何一個進程中的頁，因此這個被選中的進程擁有的物理塊會減少，缺頁率會增加

可變分配局部置換：剛開始會為每個進程分配一定數量的物理塊。當某進程發生缺頁時，只允許從該進程自己的物理塊中選出一個進行換出外存。如果進程在運行中頻繁地缺頁，系統會為該進程多分配幾個物理塊，直至該進程缺頁率趨勢適當程度；反之，如果進程在運行中缺頁率特別低，則可適當減少分配給該進程的物理塊。

調入頁面時機

1. 預調頁策略：根據局部性原理，一次調入若干個相鄰的頁面可能比一次調入一個頁面更高效。但如果提前調入的頁面中大多數都沒被訪問過，則又是低效的。因此可以預測不久之后可能訪問到的頁面，將它們預先調入內存，但目前預測成功率只有50%左右。故這種策略主要用于進程的首次調入， 由程序員指出應該先調入哪些部分。
2. 請求調頁策略：進程在運行期間發現缺頁時才將所缺頁面調入內存。由這種策略調入的頁面一定會被訪問到，但由于每次只能調入一頁，而每次調頁都要磁盤I/O操作，因此I/O開銷較大

從何處調入頁面

1. 系統擁有足夠的對換區空間：頁面的調入、調出都是在內存與對換區之間進行，這樣可以保證頁面的調入、調出速度很快。在進程運行前，需將進程相關的數據從文件區復制到對換區
2. 系統缺少足夠的對換區空間：凡是不會被修改的數據都直接從文件區調入，由于這些頁面不會被修改，因此換出時不必寫回磁盤，下次需要時再從文件區調入即可。對于可能被修改的部分，換出時需寫回磁盤對換區，下次需要時再從對換區調入
3. UNIX 方式：運行之前進程有關的數據全部放在文件區，故未使用過的頁面，都可從文件區調入。若被使用過的頁面需要換出，則寫回對換區，下次需要時從對換區調入