1.1 課程概述

• 基本概念及原理
• 操作系統(tǒng)介紹
• 中斷及系統(tǒng)調(diào)用
• 內(nèi)存管理
• 進(jìn)程及線程
• 調(diào)度
• 同步
• 文件系統(tǒng)
• I/O子系統(tǒng)

1.2 什么是操作系統(tǒng)

• 用戶(hù)角度上，操作系統(tǒng)是一個(gè)控制軟件
  管理應(yīng)用程序
  為應(yīng)用程序提供服務(wù)
  殺死應(yīng)用程序
• 對(duì)內(nèi)部管理而言
  資源管理
  管理外設(shè)、分配資源
• 操作系統(tǒng)架層次結(jié)構(gòu)
  硬件之上，應(yīng)用程序之下

1.2.1 kernel－操作系統(tǒng)內(nèi)部組件

• CPU調(diào)度器
• 物理內(nèi)存管理
• 虛擬內(nèi)存管理
• 文件系統(tǒng)管理
• 中斷處理與設(shè)備驅(qū)動(dòng)
• OS kernel 的特征
  并發(fā)：一段時(shí)間內(nèi)，有多個(gè)程序可以同時(shí)運(yùn)行，需要OS管理和調(diào)度
  并行：一個(gè)時(shí)間點(diǎn)，（多個(gè)CPU）
  共享：分時(shí)訪問(wèn)，互斥共享
  虛擬：利用多道程序設(shè)計(jì)技術(shù)，讓每個(gè)用戶(hù)覺(jué)得有一個(gè)計(jì)算機(jī)為他服務(wù)
  異步： 程序的執(zhí)行不是一貫到底，而是走走停停，向前推進(jìn)的速度不可預(yù)知
  但是只要運(yùn)行環(huán)境相同，OS需要保證程序運(yùn)行的結(jié)果相同。

1.3 為什么要學(xué)習(xí)操作系統(tǒng)

頂級(jí)會(huì)議
SOSP
OSENIX
實(shí)際操作系統(tǒng)
Windows代碼量巨大，不可能完全掌握
目標(biāo)是要理解其核心內(nèi)容
操作系統(tǒng)管理并發(fā)
操作系統(tǒng)代碼管理原始硬件：時(shí)間依賴(lài)行為，非法行為，硬件故障。
操作系統(tǒng)代碼必須是高效的：低耗CPU，內(nèi)存，磁盤(pán)
操作系統(tǒng)出錯(cuò)，就意味著機(jī)器出錯(cuò)，OS必須比用戶(hù)程序擁有更高的穩(wěn)定性。
OS是系統(tǒng)安全的基礎(chǔ)
操作系統(tǒng)需要權(quán)衡：

空間和時(shí)間
性能和可預(yù)測(cè)性
公平和性能
硬件方面，OS需要：

良好的硬件管理
合理的資源分配

1.4 操作系統(tǒng)的歷史

早期計(jì)算機(jī)使用紙帶傳輸程序和數(shù)據(jù)，OS只起到加載作用
CPU等硬件快速發(fā)展，計(jì)算機(jī)速度得到提升，性能為得到充分利用，成批／離線處理
內(nèi)存的容量越來(lái)越大，CPU執(zhí)行多個(gè)程序，多道程序設(shè)計(jì)
為了更好的利用計(jì)算機(jī)資源，并且更好的和用戶(hù)交互，出現(xiàn)了分時(shí)系統(tǒng)。分時(shí)調(diào)度
網(wǎng)絡(luò)的快速發(fā)展，出現(xiàn)了分布式的OS。松、緊耦合系統(tǒng)

1.5 操作系統(tǒng)的分類(lèi)

• 批處理操作系統(tǒng)。

批處理是指用戶(hù)將一批作業(yè)提交給操作系統(tǒng)后就不再干預(yù)，由操作系統(tǒng)控制它們自動(dòng)運(yùn)行。這種采用批量處理作業(yè)技術(shù)的操作系統(tǒng)稱(chēng)為批處理操作系統(tǒng)。批處理操作系統(tǒng)分為單道批處理系統(tǒng)和多道批處理系統(tǒng)。批處理操作系統(tǒng)不具有交互性，它是為了提高CPU的利用率而提出的一種操作系統(tǒng)。

• 分時(shí)操作系統(tǒng)。

利用分時(shí)技術(shù)的一種聯(lián)機(jī)的多用戶(hù)交互式操作系統(tǒng)，每個(gè)用戶(hù)可以通過(guò)自己的終端向系統(tǒng)發(fā)出各種操作控制命令，完成作業(yè)的運(yùn)行。分時(shí)是指把處理機(jī)的運(yùn)行時(shí)間分成很短的時(shí)間片，按時(shí)間片輪流把處理機(jī)分配給各聯(lián)機(jī)作業(yè)使用。

• 實(shí)時(shí)操作系統(tǒng)。

一個(gè)能夠在指定或者確定的時(shí)間內(nèi)完成系統(tǒng)功能以及對(duì)外部或內(nèi)部事件在同步或異步時(shí)間內(nèi)做出響應(yīng)的系統(tǒng),實(shí)時(shí)意思就是對(duì)響應(yīng)時(shí)間有嚴(yán)格要求,要以足夠快的速度進(jìn)行處理.分為硬實(shí)時(shí)和軟實(shí)時(shí)兩種。

• 通用操作系統(tǒng)。

同時(shí)兼有多道批處理、分時(shí)、實(shí)時(shí)處理的功能，或者其中兩種以上功能的操作系統(tǒng)。

• 網(wǎng)絡(luò)操作系統(tǒng)。
  一種在通常操作系統(tǒng)功能的基礎(chǔ)上提供網(wǎng)絡(luò)通信和網(wǎng)絡(luò)服務(wù)功能的操作系統(tǒng)。
• 分布式操作系統(tǒng)。
  一種以計(jì)算機(jī)網(wǎng)絡(luò)為基礎(chǔ)的，將物理上分布的具有自治功能的數(shù)據(jù)處理系統(tǒng)或計(jì)算機(jī)系統(tǒng)互聯(lián)起來(lái)的操作系統(tǒng)。分布式系統(tǒng)中各臺(tái)計(jì)算機(jī)無(wú)主次之分，系統(tǒng)中若干臺(tái)計(jì)算機(jī)可以并行運(yùn)行同一個(gè)程序，分布式操作系統(tǒng)用于管理分布式系統(tǒng)資源。
• 嵌入式操作系統(tǒng)
  一種運(yùn)行在嵌入式智能芯片環(huán)境中，對(duì)整個(gè)智能芯片以及它所操作、控制的各種部件裝置等資源進(jìn)行統(tǒng)一協(xié)調(diào)、處理、指揮和控制的系統(tǒng)軟件

2 中斷 異常 系統(tǒng)調(diào)用

系統(tǒng)調(diào)用（來(lái)源于應(yīng)用程序）
應(yīng)用程序主動(dòng)向操作系統(tǒng)發(fā)出服務(wù)請(qǐng)求
異常（來(lái)源于應(yīng)用程序）
非法指令或其他壞的處理狀態(tài)（如內(nèi)存出錯(cuò)）
中斷（來(lái)源于外設(shè)）
來(lái)自不同的硬件設(shè)備的計(jì)時(shí)器和網(wǎng)絡(luò)的中斷

2.1區(qū)別和特點(diǎn)

類(lèi)型 源頭 處理時(shí)間 響應(yīng)
中斷 外設(shè) 異步 持續(xù)，對(duì)用戶(hù)應(yīng)用程序是透明的
異常 應(yīng)用程序意想不到的行為 同步 殺死或重新執(zhí)行意想不到的應(yīng)用程序指令
系統(tǒng)調(diào)用 應(yīng)用程序請(qǐng)求提供服務(wù) 同步或異步 等待和持續(xù)

2.2 中斷、異常和系統(tǒng)調(diào)用

（一）中斷

硬件
設(shè)置中斷標(biāo)記（CPU初始化）
將內(nèi)部、外部事件設(shè)置中斷標(biāo)記
中斷事件的ID
軟件（OS）
保存當(dāng)前處理狀態(tài)
中斷服務(wù)程序處理
清除中斷標(biāo)記
恢復(fù)之前保存的狀態(tài)
（二）異常：異常編號(hào)

保存現(xiàn)場(chǎng)
異常處理
殺死產(chǎn)生了異常的程序
重新執(zhí)行異常指令
恢復(fù)現(xiàn)場(chǎng)
（三）系統(tǒng)調(diào)用

程序訪問(wèn)主要是通過(guò)高層次的API接口而不是直接進(jìn)行系統(tǒng)調(diào)用
跨越操作系統(tǒng)邊界的開(kāi)銷(xiāo)
在執(zhí)行時(shí)間上的開(kāi)銷(xiāo)超過(guò)程序調(diào)用
開(kāi)銷(xiāo)：
建立中斷/異常/系統(tǒng)調(diào)用號(hào)與對(duì)應(yīng)服務(wù)例程映射關(guān)系的初始化開(kāi)銷(xiāo)
建立內(nèi)核堆棧
驗(yàn)證參數(shù)
內(nèi)核態(tài)映射到用戶(hù)態(tài)的地址空間，更新頁(yè)面映射權(quán)限
內(nèi)核態(tài)獨(dú)立地址空間，TLB（地址轉(zhuǎn)換與安全保護(hù)）

7 進(jìn)程和線程

• 進(jìn)程（Process）描述
  進(jìn)程定義
  進(jìn)程的特點(diǎn)和組成
  進(jìn)程控制結(jié)構(gòu)
  進(jìn)程狀態(tài)（State）
  進(jìn)程的生命周期管理
  進(jìn)程創(chuàng)建
  進(jìn)程運(yùn)行
  進(jìn)程等待
  進(jìn)程喚醒
  進(jìn)程結(jié)束
  進(jìn)程狀態(tài)變化模型
  進(jìn)程掛起模型
• 線程（Thread）
  為什么使用線程
  什么是線程
  線程的實(shí)現(xiàn)
  用戶(hù)線程
  內(nèi)核線程
  輕量級(jí)線程
  多線程編程接口舉例
  進(jìn)程控制
  進(jìn)程切換（上下文切換）
  進(jìn)程創(chuàng)建
  進(jìn)程加載
  進(jìn)程等待與退出
  進(jìn)程間通信（Inter-Process communication）
  進(jìn)程互斥與同步
  死鎖（Dead Lock）

7.1 進(jìn)程的定義

一個(gè)具有一定獨(dú)立功能的程序在一個(gè)數(shù)據(jù)集合上的一次動(dòng)態(tài)執(zhí)行過(guò)程。

7.2 進(jìn)程的組成

• 一個(gè)進(jìn)程一個(gè)包括：
  程序的代碼；
  程序處理的數(shù)據(jù)；
  程序計(jì)數(shù)器中的值，指示下一條將運(yùn)行的指令；
  一組通用的寄存器的當(dāng)前值，堆、棧；
  一組系統(tǒng)資源（如打開(kāi)的文件）；
• 總之，進(jìn)程包含了正在運(yùn)行的一個(gè)程序的所有狀態(tài)信息。
  進(jìn)程與程序的聯(lián)系
  程序是產(chǎn)生進(jìn)程的基礎(chǔ)
  程序的每次運(yùn)行構(gòu)成不同的進(jìn)程
  進(jìn)程是程序功能的體現(xiàn)
  通過(guò)多次執(zhí)行，一個(gè)程序可對(duì)應(yīng)多個(gè)進(jìn)程；通過(guò)調(diào)用關(guān)系，一個(gè)進(jìn)程可包括多個(gè)程序
  進(jìn)程和程序的區(qū)別
  進(jìn)程是動(dòng)態(tài)的，程序是靜態(tài)的
  程序是有序代碼的集合；進(jìn)程是程序的執(zhí)行，進(jìn)程有核心態(tài)/用戶(hù)態(tài)
  進(jìn)程是暫時(shí)的，程序是永久的
  進(jìn)程是一個(gè)狀態(tài)變化的過(guò)程，程序可長(zhǎng)久保存
  進(jìn)程與程序的組成不同
  進(jìn)程的組成包括程序、數(shù)據(jù)和進(jìn)程控制塊（即進(jìn)程狀態(tài)信息）

7.3 進(jìn)程的特點(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)生制約
程序 = 算法 + 數(shù)據(jù)結(jié)構(gòu)
描述進(jìn)程的數(shù)據(jù)結(jié)構(gòu)：進(jìn)程控制塊（Process Control Block，PCB）
操作系統(tǒng)為每個(gè)進(jìn)程都維護(hù)了一個(gè)PCB，用來(lái)保存與該進(jìn)程有關(guān)的各種狀態(tài)信息

7.4 進(jìn)程控制塊結(jié)構(gòu)

進(jìn)程控制塊：操作系統(tǒng)管理控制進(jìn)程運(yùn)行所用的信息集合
操作系統(tǒng)用PCB來(lái)描述進(jìn)程的基本情況以及運(yùn)行變化的過(guò)程，PCB是進(jìn)程存在的唯一標(biāo)志
使用進(jìn)程控制塊
進(jìn)程的創(chuàng)建：為該進(jìn)程生成一個(gè)PCB
進(jìn)程的終止：回收它的PCB
進(jìn)程的組織管理：通過(guò)PCB的組織管理來(lái)實(shí)現(xiàn)
PCB含有以下三大類(lèi)信息：
進(jìn)程標(biāo)識(shí)信息

如本進(jìn)程的標(biāo)識(shí)，本進(jìn)程的產(chǎn)生者標(biāo)識(shí)（父進(jìn)程標(biāo)識(shí)），用戶(hù)標(biāo)識(shí)
處理機(jī)狀態(tài)信息保存區(qū)。保存進(jìn)程的運(yùn)行現(xiàn)場(chǎng)信息

用戶(hù)可見(jiàn)寄存器，用戶(hù)程序可以使用的數(shù)據(jù)、地址等寄存器
控制和狀態(tài)寄存器，如程序計(jì)數(shù)器（PC）、程序狀態(tài)字（PSW）
棧指針，過(guò)程調(diào)用/系統(tǒng)調(diào)用/中斷處理/和返回時(shí)需要用它
PCB的組織方式
鏈表：同一狀態(tài)的進(jìn)程其PCB成一鏈表，多個(gè)狀態(tài)對(duì)應(yīng)多個(gè)不同的鏈表

各狀態(tài)的進(jìn)程形成不同的鏈表：就緒鏈表、阻塞鏈表
索引表：同一狀態(tài)的進(jìn)程歸入一個(gè)index表（有index指向PCB），多個(gè)狀態(tài)對(duì)應(yīng)多個(gè)不同的index表

各狀態(tài)的進(jìn)程形成不同的索引表：就緒索引表、阻塞索引表

7.5 進(jìn)程的生命周期管理

進(jìn)程創(chuàng)建
引起進(jìn)程創(chuàng)建的3個(gè)主要條件：
系統(tǒng)初始化時(shí)
用戶(hù)請(qǐng)求創(chuàng)建一個(gè)新進(jìn)程
正在運(yùn)行的進(jìn)程執(zhí)行了創(chuàng)建進(jìn)程的系統(tǒng)調(diào)用
進(jìn)程運(yùn)行
內(nèi)核選擇一個(gè)就緒的進(jìn)程，讓它占用處理機(jī)并執(zhí)行
如何選擇？
為何選擇？
進(jìn)程等待
在以下情況下，進(jìn)程等待（阻塞）：

請(qǐng)求并等待系統(tǒng)服務(wù)，無(wú)法馬上完成
啟動(dòng)某種操作，無(wú)法馬上完成
需要的數(shù)據(jù)未到達(dá)
進(jìn)程只能自己阻塞自己，因?yàn)橹挥羞M(jìn)程自身才能知道何時(shí)需要等待某種事件的發(fā)生

進(jìn)程喚醒
喚醒進(jìn)程的原因：
被阻塞進(jìn)程需要的資源可被滿足
被阻塞進(jìn)程等待的事件到達(dá)
將該進(jìn)程的PCB插入到就緒隊(duì)列
進(jìn)程只能被別的進(jìn)程或操作系統(tǒng)喚醒
進(jìn)程結(jié)束
在以下四種情況下，進(jìn)程結(jié)束：
正常退出（自愿的）
錯(cuò)誤退出（自愿的）
致命錯(cuò)誤（強(qiáng)制性的）
被其他進(jìn)程所殺（強(qiáng)制性的）

7.6 進(jìn)程狀態(tài)變化模型

進(jìn)程的三種基本狀態(tài)：
運(yùn)行狀態(tài)（Running）：當(dāng)一個(gè)進(jìn)程正在處理機(jī)上運(yùn)行時(shí)
就緒狀態(tài)（Ready）：一個(gè)進(jìn)程獲得了除處理機(jī)之外的一切所需資源，一旦得到處理機(jī)即可運(yùn)行
等待狀態(tài)（又稱(chēng)阻塞狀態(tài) Blocked）：一個(gè)進(jìn)程正在等待某一時(shí)間而暫停運(yùn)行時(shí)。如等待某資源，等待輸入/輸出完成
進(jìn)程在生命結(jié)束前處于且僅處于三種狀態(tài)之一
不同系統(tǒng)設(shè)置的進(jìn)程狀態(tài)數(shù)目不同
進(jìn)程的其它的基本狀態(tài)：
創(chuàng)建狀態(tài)（New）：一個(gè)進(jìn)程正在被創(chuàng)建，還沒(méi)被轉(zhuǎn)到就緒狀態(tài)之前的狀態(tài)
結(jié)束狀態(tài)（Exit）：一個(gè)進(jìn)程正在從系統(tǒng)中消失時(shí)的狀態(tài)，這是因?yàn)檫M(jìn)程結(jié)束或由于其他原因。
可能的狀態(tài)變化如下：
Null -> New：一個(gè)新進(jìn)程被產(chǎn)生出來(lái)執(zhí)行一個(gè)程序
New -> Ready：當(dāng)進(jìn)程被創(chuàng)建完成并初始化后，一切就緒準(zhǔn)備運(yùn)行時(shí)，變?yōu)榫途w狀態(tài)（時(shí)間很短）
Ready -> Running：處于就緒狀態(tài)的進(jìn)程被進(jìn)程調(diào)度程序選中后，就分配到處理機(jī)上來(lái)運(yùn)行
Running -> Ready：處于運(yùn)行狀態(tài)的進(jìn)程在其運(yùn)行過(guò)程中，由于分配給它的處理機(jī)時(shí)間片用完而讓出處理機(jī)（操作系統(tǒng)完成）
Running -> Blocked：當(dāng)進(jìn)程請(qǐng)求某樣?xùn)|西且必須等待時(shí)
Blocked -> Ready：當(dāng)進(jìn)程要等待某事件到來(lái)時(shí)，它從阻塞狀態(tài)變到就緒狀態(tài)

7.7 進(jìn)程掛起

Why？合理且充分地利用系統(tǒng)資源
進(jìn)程在掛起狀態(tài)時(shí)，意味著進(jìn)程沒(méi)有占用內(nèi)存空間。處在掛起狀態(tài)的進(jìn)程映像在外存中。
掛起狀態(tài)
阻塞掛起狀態(tài)（Blocked-suspend）：進(jìn)程在外存并等待某事件的出現(xiàn)
就緒掛起狀態(tài)（Ready-suspend）：進(jìn)程在外存，但只要進(jìn)入內(nèi)存，即可運(yùn)行；
與掛起狀態(tài)相關(guān)的狀態(tài)轉(zhuǎn)換
掛起（suspend）：把一個(gè)進(jìn)程從內(nèi)存轉(zhuǎn)到外存，可能有以下幾種情況：
阻塞到阻塞掛起： 沒(méi)有進(jìn)程處于就緒狀態(tài)或就緒狀態(tài)進(jìn)程要求更多內(nèi)存資源時(shí)，會(huì)進(jìn)行這種轉(zhuǎn)換，以提交新進(jìn)程或運(yùn)行就緒進(jìn)程。
就緒到就緒掛起：當(dāng)有高優(yōu)先級(jí)阻塞（系統(tǒng)認(rèn)為很快就緒的）進(jìn)程和低優(yōu)先級(jí)就緒進(jìn)程時(shí)，系統(tǒng)會(huì)選擇掛起低優(yōu)先級(jí)就緒進(jìn)程。
運(yùn)行到就緒掛起：對(duì)搶先式分時(shí)系統(tǒng)，當(dāng)有高優(yōu)先級(jí)阻塞掛起進(jìn)程因事件出現(xiàn)而進(jìn)入就緒掛起時(shí)，系統(tǒng)可能會(huì)把運(yùn)行進(jìn)程轉(zhuǎn)到就緒掛起狀態(tài)。
在外存時(shí)的狀態(tài)轉(zhuǎn)換：
阻塞掛起到就緒掛起：當(dāng)有阻塞掛起進(jìn)程因相關(guān)事件出現(xiàn)時(shí)，系統(tǒng)會(huì)把阻塞掛起進(jìn)程轉(zhuǎn)換為就緒掛起進(jìn)程。
解掛/激活（Activate）：把一個(gè)進(jìn)程從外存轉(zhuǎn)到內(nèi)存，可能會(huì)有以下幾種情況：
就緒掛起到就緒：沒(méi)有就緒進(jìn)程或掛起就緒進(jìn)程優(yōu)先級(jí)高于就緒進(jìn)程時(shí)，會(huì)進(jìn)行這種轉(zhuǎn)換。
阻塞掛起到阻塞：當(dāng)一個(gè)進(jìn)程釋放足夠多內(nèi)存時(shí)，系統(tǒng)會(huì)把一個(gè)高優(yōu)先級(jí)阻塞掛起（系統(tǒng)認(rèn)為會(huì)很快出現(xiàn)所等待的事件）進(jìn)程轉(zhuǎn)換為阻塞進(jìn)程。
狀態(tài)隊(duì)列
由操作系統(tǒng)來(lái)維護(hù)一組隊(duì)列，用來(lái)表示系統(tǒng)當(dāng)中所有進(jìn)程的當(dāng)前狀態(tài)；
不同的狀態(tài)分別用不同的隊(duì)列表示（就緒隊(duì)列、各種類(lèi)型的阻塞隊(duì)列）；
每個(gè)進(jìn)程的PCB都根據(jù)它的狀態(tài)加入到相應(yīng)的隊(duì)列當(dāng)中，當(dāng)一個(gè)進(jìn)程的狀態(tài)發(fā)生變化時(shí)，它的PCB從一個(gè)狀態(tài)隊(duì)列中脫離出來(lái)，加入到另外一個(gè)隊(duì)列。

7.8 為什么使用線程：

案例 編寫(xiě)一個(gè)MP3播放軟件

核心功能模塊有三個(gè)：
從MP3音頻文件當(dāng)中讀取數(shù)據(jù)；
對(duì)數(shù)據(jù)進(jìn)行解壓縮；
把壓縮后的音頻數(shù)據(jù)播放出來(lái)。
單進(jìn)程實(shí)現(xiàn)方法
問(wèn)題：
播出來(lái)的聲音是否連貫？
各個(gè)函數(shù)之間不是并發(fā)執(zhí)行，影響資源的使用效率
多進(jìn)程實(shí)現(xiàn)方法
問(wèn)題：
進(jìn)程之間如何通信、共享數(shù)據(jù)？
另外，維護(hù)進(jìn)程的系統(tǒng)開(kāi)銷(xiāo)較大：創(chuàng)建進(jìn)程時(shí)，分配資源、建立PCB；撤銷(xiāo)進(jìn)程時(shí)，回收資源、撤銷(xiāo)PCB
進(jìn)程切換時(shí)，保存當(dāng)前進(jìn)程的狀態(tài)信息
怎么來(lái)解決這些問(wèn)題？
需要提出一種新的實(shí)體，滿足以下特性：
實(shí)體之間可以并發(fā)地執(zhí)行；
實(shí)體之間共享相同的地址空間
這種實(shí)體就是線程。

7.9 什么是線程

Thread：進(jìn)程當(dāng)中的一條執(zhí)行流程
從兩個(gè)方面來(lái)重新理解進(jìn)程：
從資源組合的角度：
進(jìn)程把一組相關(guān)的資源組合起來(lái)，構(gòu)成了一個(gè)資源平臺(tái)（環(huán)境），包括地址空間（代碼段、數(shù)據(jù)段）、打開(kāi)的文件等各種資源；
從運(yùn)行的角度：
代碼在這個(gè)資源平臺(tái)上的一條執(zhí)行流程（線程）。
線程 = 進(jìn)程 - 共享資源
線程的優(yōu)點(diǎn)
一個(gè)進(jìn)程中可以同時(shí)存在多個(gè)線程
各個(gè)線程之間可以并發(fā)地執(zhí)行且共享地址空間和文件資源
線程的缺點(diǎn)
一個(gè)線程崩潰，會(huì)導(dǎo)致其所屬進(jìn)程所有線程崩潰
不同OS對(duì)線程的支持
MS-DOS：?jiǎn)芜M(jìn)程單線程
Unix：多進(jìn)程單線程
Windows NT：多進(jìn)程多線程（Linux）
線程與進(jìn)程的比較
進(jìn)程是資源分配單位，線程是CPU調(diào)度單位
進(jìn)程擁有一個(gè)完整的資源平臺(tái)，而線程只獨(dú)享必不可少的資源，如寄存器和棧
線程同樣具有就緒、阻塞和執(zhí)行三種基本狀態(tài)，同樣具有狀態(tài)之間的轉(zhuǎn)換關(guān)系
線程能減少并發(fā)執(zhí)行的時(shí)間和空間開(kāi)銷(xiāo)：
線程的創(chuàng)建時(shí)間比進(jìn)程短；
線程的終止時(shí)間比進(jìn)程短；
同一進(jìn)程內(nèi)線程切換時(shí)間比進(jìn)程短；
由于同一進(jìn)程的各線程間共享內(nèi)存和文件資源，可直接進(jìn)行不通過(guò)內(nèi)核的通信。

7.10 線程的實(shí)現(xiàn)

主要有三種線程實(shí)現(xiàn)方式：

• 用戶(hù)線程：在用戶(hù)空間實(shí)現(xiàn)；
  POSIX Pthreads,Math C-threads,Solaris threads

• 內(nèi)核線程：在內(nèi)核中實(shí)現(xiàn)；
  Windows，Solaris，Linux

• 輕量級(jí)線程：在內(nèi)核中實(shí)現(xiàn)，支持用戶(hù)線程；
  Solaris

• 用戶(hù)線程與內(nèi)核線程的對(duì)應(yīng)關(guān)系
  多對(duì)一
  一對(duì)一
  多對(duì)多

• 用戶(hù)線程
  在用戶(hù)空間實(shí)現(xiàn)的線程機(jī)制，它不依賴(lài)于操作系統(tǒng)的內(nèi)核，由一組用戶(hù)級(jí)的線程庫(kù)函數(shù)來(lái)完成線程的管理，包括進(jìn)程的創(chuàng)建、終止、同步和調(diào)度等。
  由于用戶(hù)線程的維護(hù)由相應(yīng)進(jìn)程來(lái)完成（通過(guò)線程庫(kù)函數(shù)），不需要操作系統(tǒng)內(nèi)核了解用戶(hù)線程的存在，可用于不支持線程技術(shù)的多進(jìn)程操作系統(tǒng)；
  每個(gè)進(jìn)程都需要它自己私有的線程控制塊（TCB）列表，用來(lái)跟蹤記錄它的各個(gè)線程的狀態(tài)信息（PC、棧指針、寄存器），TCB由線程庫(kù)函數(shù)來(lái)維護(hù)；
  用戶(hù)線程的切換也是由線程庫(kù)函數(shù)來(lái)完成，無(wú)需用戶(hù)態(tài)/核心態(tài)切換，所以速度特別快
  允許每個(gè)進(jìn)程擁有自定義的線程調(diào)度算法。
  用戶(hù)線程缺點(diǎn)
  阻塞性的系統(tǒng)調(diào)用如何實(shí)現(xiàn)？如果一個(gè)線程發(fā)起系統(tǒng)調(diào)用而阻塞，則整個(gè)進(jìn)程在等待；
  當(dāng)一個(gè)線程開(kāi)始運(yùn)行后，除非它主動(dòng)地交出CPU的使用權(quán)，否則它所在的過(guò)程當(dāng)中的其他線程都無(wú)法運(yùn)行；
  由于時(shí)間片分配給進(jìn)程，故與其他進(jìn)程比，在多線程執(zhí)行時(shí)，每個(gè)線程得到的時(shí)間片較少，執(zhí)行會(huì)較慢。

• 內(nèi)核線程
  是指在操作系統(tǒng)的內(nèi)核當(dāng)中實(shí)現(xiàn)的一種線程機(jī)制，由操作系統(tǒng)的內(nèi)核來(lái)完成線程的創(chuàng)建、終止和管理。
  在支持內(nèi)核線程的操作系統(tǒng)中，由內(nèi)核來(lái)維護(hù)進(jìn)程和線程的上下文信息（PCB和TCB）；
  線程的創(chuàng)建、終止和切換都是通過(guò)系統(tǒng)調(diào)用/內(nèi)核函數(shù)的方式來(lái)進(jìn)行，由內(nèi)核來(lái)完成，因此系統(tǒng)的開(kāi)銷(xiāo)較大；
  在一個(gè)進(jìn)程中，如果某個(gè)內(nèi)核線程發(fā)起系統(tǒng)調(diào)用而被阻塞，并不會(huì)影響其他內(nèi)核線程的運(yùn)行；
  時(shí)間片分配給線程，多線程的進(jìn)程獲得更多的CPU時(shí)間；
  Windows NT 和 Windows 2001/XP 支持內(nèi)核線程。

• 輕量級(jí)進(jìn)程（LightWeight Process）
  它是內(nèi)核支持的用戶(hù)線程。一個(gè)進(jìn)程可有一個(gè)或多個(gè)輕量級(jí)進(jìn)程，每個(gè)量級(jí)進(jìn)程由一個(gè)單獨(dú)的內(nèi)核線程來(lái)支持。（Solaris/Linux）

8 處理機(jī)調(diào)度

處理機(jī)調(diào)度概念
處理機(jī)調(diào)度
處理機(jī)調(diào)度時(shí)機(jī)
調(diào)度準(zhǔn)則
調(diào)度策略
比較調(diào)度算法的準(zhǔn)則
調(diào)度算法

先進(jìn)先服務(wù)算法（FCFS：First Come, First Served）
短進(jìn)程優(yōu)先算法
SPN: Shortest Process Next
SJF: Shortest Job First（短作業(yè)優(yōu)先算法）
SRT: Shortest Remaining Time（短剩余時(shí)間優(yōu)先算法）
最高響應(yīng)比優(yōu)先算法（HRRN: Highest Response Ratio Next）
時(shí)間片輪轉(zhuǎn)算法（RR: Round Robin）
多級(jí)隊(duì)列調(diào)度算法（MQ: Multilevel Queues）
多級(jí)反饋隊(duì)列算法（MFQ: Multilevel Feedback Queues）
公平共享調(diào)度算法（FSS: Fair Share Scheduling）
實(shí)時(shí)調(diào)度

實(shí)時(shí)操作系統(tǒng)
可調(diào)度性
實(shí)時(shí)調(diào)度算法
速度單調(diào)調(diào)度算法（RM，Rate Monotonic)
最早截止時(shí)間優(yōu)先算法（EPF，Earlist Deadline First）
多處理器調(diào)度
優(yōu)先級(jí)反轉(zhuǎn)

8.1 處理機(jī)調(diào)度

CPU資源的時(shí)分復(fù)用
進(jìn)程切換：CPU資源的當(dāng)前占用者切換

保存當(dāng)前進(jìn)程在PCB中的執(zhí)行上下文（CPU狀態(tài)）
恢復(fù)下一個(gè)進(jìn)程的執(zhí)行上下文
處理機(jī)調(diào)度

從就緒隊(duì)列中挑選下一個(gè)占用CPU運(yùn)行的進(jìn)程
從多個(gè)可用CPU中挑選就緒進(jìn)程可使用的CPU
調(diào)度程序：挑選就緒進(jìn)程的內(nèi)核函數(shù)
調(diào)度策略
調(diào)度時(shí)機(jī)
調(diào)度時(shí)機(jī)
內(nèi)核運(yùn)行調(diào)度程序的條件
進(jìn)程從運(yùn)行狀態(tài)切換到等待狀態(tài)
進(jìn)程被終結(jié)了
非搶占系統(tǒng)
當(dāng)前進(jìn)程主動(dòng)放棄CPU時(shí)
可搶占系統(tǒng)
中斷請(qǐng)求被服務(wù)例程響應(yīng)完成時(shí)
當(dāng)前進(jìn)程被搶占
進(jìn)程時(shí)間片用完
進(jìn)程從等待切換到就緒

8.2 調(diào)度準(zhǔn)則

（一）調(diào)度策略

調(diào)度策略
確定如何從就緒隊(duì)列中選擇下一個(gè)執(zhí)行進(jìn)程
調(diào)度策略要解決的問(wèn)題

挑選就緒隊(duì)列中的哪一個(gè)進(jìn)程？
通過(guò)什么樣的準(zhǔn)則來(lái)選擇？
調(diào)度算法

在調(diào)度程序中實(shí)現(xiàn)的調(diào)度策略
比較調(diào)度算法的準(zhǔn)則

哪一個(gè)策略/算法較好？
調(diào)度算法的考核指標(biāo)
處理機(jī)資源的使用模式
進(jìn)程在CPU計(jì)算和I/O操作間交替
在時(shí)間片機(jī)制下，進(jìn)程可能在結(jié)束當(dāng)前計(jì)算前被迫放棄CPU
（二）比較調(diào)度算法的準(zhǔn)則

系統(tǒng)利用效率角度：
CPU使用率
CPU處于忙狀態(tài)的時(shí)間百分比
吞吐量
單位時(shí)間內(nèi)完成的進(jìn)程數(shù)量
用戶(hù)角度：
周轉(zhuǎn)時(shí)間
進(jìn)程從初始化到結(jié)束（包括等待）的總時(shí)間
等待時(shí)間
進(jìn)程在就緒隊(duì)列的總時(shí)間
交互性應(yīng)用角度：
響應(yīng)時(shí)間
從提交請(qǐng)求到產(chǎn)生響應(yīng)所花費(fèi)的總時(shí)間
吞吐量與延遲
調(diào)度算法的要求
希望“更快”的服務(wù)
什么是更快？
傳輸文件時(shí)的高帶寬，調(diào)度算法的吞吐量
玩游戲時(shí)的低延遲，調(diào)度算法的低響應(yīng)延遲
這兩個(gè)因素是獨(dú)立的
處理機(jī)調(diào)度策略的響應(yīng)時(shí)間目標(biāo)
減少響應(yīng)時(shí)間
及時(shí)處理用戶(hù)的輸入請(qǐng)求，盡快將輸出反饋給用戶(hù)
減少平均響應(yīng)時(shí)間的波動(dòng)
在交互系統(tǒng)中，可預(yù)測(cè)性比高差異低平均更重要
低延遲調(diào)度改善了用戶(hù)的交互體驗(yàn)
響應(yīng)時(shí)間是操作系統(tǒng)的計(jì)算延遲
處理機(jī)調(diào)度策略的吞吐量目標(biāo)
增加吞吐量
減少開(kāi)銷(xiāo)（操作系統(tǒng)開(kāi)銷(xiāo)，上下文切換）
系統(tǒng)資源的高效利用（CPU，I/O設(shè)備）
減少等待時(shí)間

減少每個(gè)進(jìn)程的等待時(shí)間
操作系統(tǒng)需要保證吞吐量不受用戶(hù)交互的影響

操作系統(tǒng)必須不時(shí)進(jìn)行調(diào)度，即使存在許多交互任務(wù)
吞吐量是操作系統(tǒng)的計(jì)算帶寬

處理機(jī)調(diào)度策略的公平性目標(biāo)
公平的定義

保證每個(gè)進(jìn)程占用相同的CPU時(shí)間
保證每個(gè)進(jìn)程的等待時(shí)間相同
公平通常會(huì)增加平均響應(yīng)時(shí)間

8.3 調(diào)度算法

（一）先進(jìn)先服務(wù)算法（FCFS：First Come, First Served）

依據(jù)進(jìn)程進(jìn)入就緒狀態(tài)的先后順序排列
進(jìn)程進(jìn)入與等待或結(jié)束狀態(tài)時(shí)，就緒隊(duì)列中的下一個(gè)進(jìn)程占用CPU
先進(jìn)先服務(wù)算法的周轉(zhuǎn)時(shí)間
例

3個(gè)進(jìn)程，計(jì)算時(shí)間分別為12，3，3
任務(wù)到達(dá)順序：P1，P2，P3

執(zhí)行時(shí)間：| 0 | P1 | 12 | P2 | 15 | P3 | 18|
周轉(zhuǎn)時(shí)間：（12+15+18）/3 = 15
任務(wù)到達(dá)順序：P2，P3，P1

執(zhí)行時(shí)間：| 0 | P2 | 3 | P3 | 6 | P1 | 18|
周轉(zhuǎn)時(shí)間：（3+6+18）/3 = 9
先進(jìn)先服務(wù)算法特征
優(yōu)點(diǎn)

簡(jiǎn)單
缺點(diǎn)

平均等待時(shí)間波動(dòng)較大

短進(jìn)程可能排在長(zhǎng)進(jìn)程后面
I/O資源CPU資源的利用率較低

CPU密集型進(jìn)程會(huì)導(dǎo)致I/O設(shè)備閑置時(shí)，I/O密集型進(jìn)程也等待
（二）短進(jìn)程優(yōu)先算法（SPN: Shortest Process Next）

選擇就緒隊(duì)列中執(zhí)行時(shí)間最短進(jìn)程占用CPU進(jìn)入運(yùn)行狀態(tài)
就緒隊(duì)列按預(yù)期的執(zhí)行時(shí)間來(lái)排序
短進(jìn)程優(yōu)先算法特征
優(yōu)點(diǎn)

具有最優(yōu)的平均周轉(zhuǎn)時(shí)間
缺點(diǎn)

可能導(dǎo)致饑餓

連續(xù)的短進(jìn)程流會(huì)使長(zhǎng)進(jìn)程無(wú)法獲得CPU資源
需要預(yù)知未來(lái)

如何預(yù)知下一個(gè)CPU計(jì)算的持續(xù)時(shí)間？
簡(jiǎn)單的解決辦法：詢(xún)問(wèn)用戶(hù)
用戶(hù)欺騙就殺死相應(yīng)進(jìn)程
用戶(hù)不知道怎么辦？
短進(jìn)程優(yōu)先算法執(zhí)行時(shí)間預(yù)估
用歷史的執(zhí)行時(shí)間來(lái)預(yù)估未來(lái)的執(zhí)行時(shí)間

τn+1 = αtn + (1-α)τn，其中 0 <= α <= 1

tn：第n次的CPU計(jì)算時(shí)間
τn+1：第n+1次的CPU計(jì)算時(shí)間預(yù)估
短剩余時(shí)間優(yōu)先算法（SRT: Shortest Remaining Time）
短進(jìn)程優(yōu)先算法的可搶占改進(jìn)
（三）最高響應(yīng)比優(yōu)先算法（HRRN: Highest Response Ratio Next）

選擇就緒隊(duì)列中響應(yīng)比的R值最高的進(jìn)程
R = （w+s)/s

w：等待時(shí)間（waiting time）
s：執(zhí)行時(shí)間（Service time）

在短進(jìn)程優(yōu)先算法的基礎(chǔ)上改進(jìn)

不可搶占
關(guān)注進(jìn)程的等待時(shí)間
防止無(wú)限期推遲
（四）時(shí)間片輪轉(zhuǎn)算法（RR：Round Robin）

時(shí)間片

分配處理機(jī)資源的基本時(shí)間單元
算法思路

時(shí)間片結(jié)束時(shí)，按先進(jìn)先服務(wù)算法切換到下一個(gè)就緒進(jìn)程
每隔（n-1）個(gè)時(shí)間片進(jìn)程執(zhí)行一個(gè)時(shí)間片q
例

時(shí)間片為20的時(shí)間片輪轉(zhuǎn)算法示例
4個(gè)進(jìn)程的執(zhí)行時(shí)間如下：
P1：53，P2：8，P3：68，P4：24
甘特圖如下：
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
20 28 48 68 88 108 112 125 145 153
等待時(shí)間：

P1：（68-20）+（112-88） = 72
P2：（20-0）= 20
P3：（28-0）+（88-48）+（125-108）= 85
P4：（48-0）+（108-68）=88
平均等待時(shí)間：（72+20+85+88）/4 = 66.25

時(shí)間片長(zhǎng)度
時(shí)間片輪轉(zhuǎn)算法開(kāi)銷(xiāo)：

額外的上下文切換（靠時(shí)鐘中斷強(qiáng)行把正在執(zhí)行的進(jìn)程結(jié)束掉）
時(shí)間片太大（進(jìn)程響應(yīng)時(shí)間）

等待時(shí)間過(guò)長(zhǎng)
極限情況退化成先進(jìn)先服務(wù)算法
時(shí)間片太?。ㄏ到y(tǒng)開(kāi)銷(xiāo)）

反應(yīng)迅速，但產(chǎn)生大量的上下文切換
大量上下文切換開(kāi)銷(xiāo)影響到系統(tǒng)吞吐量
時(shí)間片長(zhǎng)度選擇目標(biāo)

選擇一個(gè)合適的時(shí)間片長(zhǎng)度
經(jīng)驗(yàn)規(guī)則：維持上下文切換開(kāi)銷(xiāo)在1%以?xún)?nèi)
（五）多級(jí)隊(duì)列調(diào)度算法（MQ: Multilevel Queues）

就緒隊(duì)列被劃分成多個(gè)獨(dú)立的子隊(duì)列

如：前臺(tái)（交互）、后臺(tái)（批處理）
每個(gè)隊(duì)列擁有自己的調(diào)度策略

如：前臺(tái)–RR，后臺(tái)：FCFS
隊(duì)列間的調(diào)度

固定優(yōu)先級(jí)

先處理前臺(tái)，然后處理后臺(tái)
可能導(dǎo)致饑餓
時(shí)間片輪轉(zhuǎn)

每個(gè)隊(duì)列都得到一個(gè)確定的能夠調(diào)度其進(jìn)程的CPU總時(shí)間
如：80% CPU時(shí)間用于前臺(tái)，20% CPU時(shí)間用于后臺(tái)
（六）多級(jí)反饋隊(duì)列算法（MFQ: Multilevel Feedback Queues）

進(jìn)程可在不同隊(duì)列間移動(dòng)的多級(jí)隊(duì)列算法
時(shí)間片大小隨優(yōu)先級(jí)增加而減小
如進(jìn)程在當(dāng)前時(shí)間片沒(méi)有完成，則降到下一個(gè)優(yōu)先級(jí)
多級(jí)反饋隊(duì)列算法特征
CPU密集型進(jìn)程的優(yōu)先級(jí)下降很快（時(shí)間片大）
I/O密集型進(jìn)程停留在高優(yōu)先級(jí)（時(shí)間片?。?br> （七）公平共享調(diào)度算法（FSS: Fair Share Scheduling）

公平共享調(diào)度算法控制用戶(hù)對(duì)系統(tǒng)資源的訪問(wèn)
一些用戶(hù)組比其他用戶(hù)組更重要
保證不重要的無(wú)法壟斷資源
未使用的資源按比例分配
沒(méi)有達(dá)到資源使用率目標(biāo)的組獲得更高的優(yōu)先級(jí)（時(shí)間片減?。?/p>

8.4 實(shí)時(shí)調(diào)度

（一）實(shí)時(shí)操作系統(tǒng)

defs：正確性依賴(lài)于其時(shí)間和功能兩方面的操作系統(tǒng)

性能指標(biāo)：

時(shí)間約束的及時(shí)性（deadlines）
速度和平均性能相對(duì)不重要
特征：

時(shí)間約束的可預(yù)測(cè)性
實(shí)時(shí)任務(wù)
任務(wù)（工作單元）

一次計(jì)算、一次文件讀取、一次信息傳遞等等
任務(wù)屬性

完成任務(wù)所需要的資源
定時(shí)參數(shù)
周期實(shí)時(shí)任務(wù)
defs：一系列相似的任務(wù)

任務(wù)有規(guī)律的重復(fù)
周期 p = 任務(wù)請(qǐng)求時(shí)間間隔（ocp）
執(zhí)行時(shí)間 e = 最大執(zhí)行時(shí)間（ocecp)
使用率 U = e/p
硬時(shí)限（Hard deadline）

錯(cuò)過(guò)任務(wù)時(shí)限會(huì)導(dǎo)致災(zāi)難性或非常嚴(yán)重的后果
必須驗(yàn)證，在最壞情況下能夠滿足時(shí)限
軟時(shí)限（Soft deadline）

通常能滿足任務(wù)時(shí)限

如有時(shí)不能滿足，則降低要求
盡力保證滿足任務(wù)時(shí)限

（二）可調(diào)度性

defs：可調(diào)度表示一個(gè)實(shí)時(shí)操作系統(tǒng)能夠滿足任務(wù)時(shí)限要求
需要確定實(shí)時(shí)任務(wù)的執(zhí)行順序
靜態(tài)優(yōu)先級(jí)調(diào)度
動(dòng)態(tài)優(yōu)先級(jí)調(diào)度
（三）實(shí)時(shí)調(diào)度算法

速度單調(diào)調(diào)度算法（RM，Rate Monotonic)
通過(guò)周期安排優(yōu)先級(jí)
周期越短優(yōu)先級(jí)越高
執(zhí)行周期最短的任務(wù)
最早截止時(shí)間優(yōu)先算法（EPF，Earlist Deadline First）
截止時(shí)間越早優(yōu)先級(jí)越高
執(zhí)行截止時(shí)間最早的任務(wù)

8.5 多處理器調(diào)度

多處理器調(diào)度特征
多個(gè)處理機(jī)組成一個(gè)多處理機(jī)系統(tǒng)
處理機(jī)間可負(fù)載共享
對(duì)稱(chēng)多處理器（SMP，Symmetric multiprocessing)調(diào)度
每個(gè)處理器運(yùn)行自己的調(diào)度程序
調(diào)度程序?qū)蚕碣Y源的訪問(wèn)需要進(jìn)行同步
對(duì)稱(chēng)多處理器的進(jìn)程分配
靜態(tài)進(jìn)程分配
進(jìn)程從開(kāi)始到結(jié)束都被分配到一個(gè)固定的處理上執(zhí)行
每個(gè)處理機(jī)有自己的就緒隊(duì)列
調(diào)度開(kāi)銷(xiāo)小
各處理機(jī)可能忙閑不均
動(dòng)態(tài)進(jìn)程分配
進(jìn)程在執(zhí)行中可分配到任意空閑處理機(jī)上執(zhí)行
所有處理機(jī)共享一個(gè)公共的就緒隊(duì)列
調(diào)度開(kāi)銷(xiāo)大
多處理機(jī)的負(fù)載是均衡的

8.6 優(yōu)先級(jí)反置（Priority Inversion）

操作系統(tǒng)中出現(xiàn)高優(yōu)先級(jí)進(jìn)程長(zhǎng)時(shí)間等待低優(yōu)先級(jí)進(jìn)程所應(yīng)用資源的現(xiàn)象
基于優(yōu)先級(jí)的可搶占調(diào)度算法存在優(yōu)先級(jí)反置
優(yōu)先級(jí)繼承（Priority Inheritance）
占用資源的低優(yōu)先級(jí)進(jìn)程繼承申請(qǐng)資源的高優(yōu)先級(jí)進(jìn)程的優(yōu)先級(jí)
只在占用資源的低優(yōu)先級(jí)進(jìn)程被阻塞時(shí)，才提高占用資源進(jìn)程的優(yōu)先級(jí)
優(yōu)先級(jí)天花板協(xié)議（Priority ceiling protocol）
占用資源進(jìn)程的優(yōu)先級(jí)和所有可能申請(qǐng)?jiān)撡Y源的進(jìn)程的最高優(yōu)先級(jí)相同
不管是否發(fā)生等待，都提升占用資源進(jìn)程的優(yōu)先級(jí)
優(yōu)先級(jí)高于子系統(tǒng)中所有被鎖定的資源的優(yōu)先級(jí)上限，任務(wù)執(zhí)行臨界區(qū)時(shí)就不會(huì)被阻塞

第3章：連續(xù)內(nèi)存分配

3.1 地址空間與地址生成

（一）地址空間

物理地址空間–硬件支持的地址空間
邏輯地址空間–一個(gè)運(yùn)行的程序所擁有的內(nèi)存范圍
（二）邏輯地址生成

.c file -> 編譯 -> .s file -> 匯編 -> .o file -> 鏈接 -> .exe file -> 載入（程序重定位） -> 程序在內(nèi)存中

（三）物理地址生成

CPU方面
運(yùn)算器需要在邏輯地址內(nèi)存內(nèi)容
內(nèi)存管理單元尋找在邏輯地址和物理地址之間的映射
控制器從總線發(fā)送在物理地址的內(nèi)存內(nèi)容的請(qǐng)求
內(nèi)存方面
內(nèi)存發(fā)送物理地址內(nèi)存的內(nèi)容給CPU
OS方面
建立邏輯地址和物理地址之間的映射

3.2 連續(xù)內(nèi)存分配：內(nèi)存碎片與分區(qū)的動(dòng)態(tài)分配

（一）內(nèi)存碎片問(wèn)題

空閑內(nèi)存不能被利用
外部碎片：在分配單元間的未使用內(nèi)存
內(nèi)部碎片：在分配單元中的未使用內(nèi)存
（二）分區(qū)的動(dòng)態(tài)分配

簡(jiǎn)單的內(nèi)存管理方法

當(dāng)一個(gè)程序準(zhǔn)許運(yùn)行在內(nèi)存中時(shí)，分配一個(gè)連續(xù)的區(qū)間
分配一個(gè)連續(xù)的區(qū)間給運(yùn)行的程序以訪問(wèn)數(shù)據(jù)
分配策略

首次適配
最優(yōu)適配
最差適配
第一匹配適配
defs

為了分配 n 字節(jié)，使用第一個(gè)可用空閑塊以致塊的尺寸比 n 大
基本原理&實(shí)現(xiàn)

簡(jiǎn)單實(shí)現(xiàn)
需求：
按地址排序的空閑塊列表
分配需要尋找一個(gè)合適的分區(qū)
重分配需要檢查，看是否自由分區(qū)能合并于相鄰的空閑分區(qū)（若有）
優(yōu)勢(shì)

簡(jiǎn)單
易于產(chǎn)生更大空閑塊，向著地址空間的結(jié)尾
劣勢(shì)

外部碎片
不確定性
最優(yōu)匹配
defs

為了分配 n 字節(jié)，使用最小的可用空閑塊，以致塊的尺寸比 n 大
基本原理&實(shí)現(xiàn)

為了避免分割大的空閑塊
為了最小化外部碎片產(chǎn)生的尺寸
需求：
按尺寸排序的空閑塊列表
分配需要尋找一個(gè)合適的分區(qū)
重分配需要搜索及合并于相鄰的空閑分區(qū)（若有）
優(yōu)勢(shì)

當(dāng)大部分分配是小尺寸時(shí)非常有效
比較簡(jiǎn)單
劣勢(shì)

外部碎片
重分配慢
易產(chǎn)生很多沒(méi)用的微小碎片（不怎么好）
最差匹配
defs

為了分配 n 字節(jié)，使用最大可用空閑塊，以致塊的尺寸比 n 大
基本原理&實(shí)現(xiàn)

為了避免太多微小的碎片
需求：
按尺寸排序的空閑塊列表
分配很快（獲得最大的分區(qū)）
重分配需要合并于相鄰的空閑分區(qū)（若有），然后調(diào)整空閑塊列表
優(yōu)勢(shì)

假如分配是中等尺寸效果最好
劣勢(shì)

重分配慢
外部碎片
易于破碎大的空閑塊以致大分區(qū)無(wú)法被分配

3.3 連續(xù)內(nèi)存分配：壓縮式與交換式碎片整理

（一）壓縮式碎片整理

重置程序以合并孔洞
要求所有程序是動(dòng)態(tài)可重置的
（二）交換式碎片整理

運(yùn)行程序需要更多的內(nèi)存
搶占等待的程序&回收它們的內(nèi)存

第4章：非連續(xù)內(nèi)存分配
標(biāo)簽（空格分隔）： 操作系統(tǒng)

4.1 非連續(xù)內(nèi)存分配：分段

（一）為什么需要非連續(xù)內(nèi)存分配

連續(xù)內(nèi)存分配的缺點(diǎn)
分配給一個(gè)程序的物理內(nèi)存是連續(xù)的
內(nèi)存利用率較低
有外碎片、內(nèi)碎片的問(wèn)題
非連續(xù)內(nèi)存分配的優(yōu)點(diǎn)
一個(gè)程序的物理地址空間是非連續(xù)的
更好的內(nèi)存利用和管理
允許共享代碼和數(shù)據(jù)（共享庫(kù)等）
支持動(dòng)態(tài)加載和動(dòng)態(tài)鏈接
非連續(xù)分配：缺點(diǎn)
如何建立虛擬地址和物理地址之間的轉(zhuǎn)換
硬件方案
軟件方案：開(kāi)銷(xiāo)大
兩種硬件方案
分段
分頁(yè)
分段
程序的分段地址空間
分段尋址方案

段訪問(wèn)機(jī)制：一個(gè)段，一個(gè)內(nèi)存“塊”，一個(gè)邏輯地址空間

程序訪問(wèn)需要：
一個(gè)二維的二元組（s, addr） s：段號(hào)，addr：段內(nèi)偏移
段寄存器+地址寄存器實(shí)現(xiàn)方案
單地址實(shí)現(xiàn)方案

4.2 非連續(xù)內(nèi)存分配：分頁(yè)

（一）分頁(yè)

分頁(yè)地址空間
頁(yè)尋址方案
劃分物理內(nèi)存至固定大小的幀（frames），大小是2的冪，512,4196……
劃分邏輯地址空間至相同大小的頁(yè)，大小是2的冪，512,4196……
建立方案，轉(zhuǎn)換邏輯地址為物理地址（page to frames）
頁(yè)表
MMU/TLB
幀（Frame）
物理內(nèi)存被分割為大小相等的幀
一個(gè)內(nèi)存物理地址是一個(gè)二元組（f, o）
f：幀號(hào)（F位，共有2^F個(gè)幀）
o：幀內(nèi)偏移（S位，每幀有2^S個(gè)字節(jié)）
物理地址：2^S * f + o
例

16bit 的地址空間，9bit（512bytes）大小的頁(yè)幀，物理地址=（3,6）
物理地址：2^93+6=5123+6=1536+6=1542
頁(yè)（page）
一個(gè)程序的邏輯地址空間被劃分為大小相等的頁(yè)
頁(yè)內(nèi)偏移大小 = 幀內(nèi)偏移的大小
頁(yè)號(hào)大小 幀號(hào)大小 （頁(yè)表）
一個(gè)邏輯地址是一個(gè)二元組（p,o）
p：頁(yè)號(hào)（P位，2^P個(gè)頁(yè)）
o：頁(yè)內(nèi)偏移（S位，每頁(yè)有2^S個(gè)字節(jié)）
虛擬地址：2^S * p + o
頁(yè)尋址機(jī)制
頁(yè)映射到幀
頁(yè)是連續(xù)的虛擬內(nèi)存
幀是非連續(xù)的物理內(nèi)存
不是所有的頁(yè)都有對(duì)應(yīng)的幀

4.3 非連續(xù)內(nèi)存分配：頁(yè)表 - 概述、TLB

頁(yè)表概述
轉(zhuǎn)換后備緩沖區(qū)（TLB）
二級(jí)/多級(jí) 頁(yè)表
反向頁(yè)表
（一）分頁(yè)機(jī)制的性能問(wèn)題

問(wèn)題：訪問(wèn)一個(gè)內(nèi)存單元需要2次內(nèi)存訪問(wèn)
一次用于獲取頁(yè)表項(xiàng)
一次用于訪問(wèn)數(shù)據(jù)
頁(yè)表可能非常大
（二）Translation Look-aside Buffer (TLB) 快表

緩存近期訪問(wèn)的頁(yè)幀轉(zhuǎn)換表項(xiàng)
TLB使用associate memory（關(guān)聯(lián)內(nèi)存）實(shí)現(xiàn)，具備快速訪問(wèn)性能
如果TLB命中，物理頁(yè)號(hào)可以很快被獲取
如果TLB未命中，對(duì)應(yīng)的表項(xiàng)被更新到TLB中

4.4 非連續(xù)內(nèi)存分配：頁(yè)表 - 二級(jí)/多級(jí) 頁(yè)表

多級(jí)頁(yè)表
通過(guò)把頁(yè)號(hào)分為k個(gè)部分，來(lái)實(shí)現(xiàn)多級(jí)間接頁(yè)表
建立頁(yè)表“樹(shù)”，以時(shí)間換空間

4.5 非連續(xù)內(nèi)存分配：頁(yè)表 - 反向頁(yè)表

（一）大地址空間

有大地址空間（64bits），前向映射表變得繁瑣
不是讓頁(yè)表與邏輯地址空間的大小相對(duì)應(yīng)，而是讓頁(yè)表與物理地址空間的大小相對(duì)應(yīng)
邏輯（虛擬）地址空間增長(zhǎng)速度快于物理地址空間
基于寄存器（Page Registers）的方案
每個(gè)幀和一個(gè)寄存器關(guān)聯(lián)，寄存器內(nèi)容包括：
Residence bit：此幀號(hào)是否已被占用
Occupier：對(duì)應(yīng)的頁(yè)號(hào)P
Protection bits：保護(hù)位
頁(yè)寄存器：一個(gè)例子
物理內(nèi)存大?。?0964096=4kB4kB=16MB
頁(yè)面大小：4096Bytes
頁(yè)幀數(shù)：4096=4k
頁(yè)寄存器使用的空間（假設(shè)8 Bytes/register）：8*4096=32kBytes
頁(yè)寄存器帶來(lái)的額外開(kāi)銷(xiāo)：32K/16M = 0.2%（大約）
虛擬內(nèi)存的大?。喝我?br> 頁(yè)寄存器方案的權(quán)衡
利：
轉(zhuǎn)換表的大小相對(duì)于物理內(nèi)存來(lái)說(shuō)很小
轉(zhuǎn)換表的大小跟邏輯地址空間的大小無(wú)關(guān)
弊：
需要的信息對(duì)調(diào)了，即根據(jù)幀號(hào)找到頁(yè)號(hào)
如何轉(zhuǎn)換回來(lái)？即根據(jù)頁(yè)號(hào)找到幀號(hào)
需要在反向頁(yè)表中搜索想要的頁(yè)號(hào)

第5章：虛擬內(nèi)存

起因
覆蓋技術(shù)
交換技術(shù)
虛存技術(shù)
目標(biāo)
程序局部性原理
基本概念
基本特征
虛擬頁(yè)式內(nèi)存管理

5.1 虛擬內(nèi)存的起因

理想中的存儲(chǔ)器
更大、更快、更便宜的非易失性存儲(chǔ)器
OS支持的存儲(chǔ)器
更大、更快、更便宜好用的易失性存儲(chǔ)器
內(nèi)存不夠用
程序太大，手動(dòng)的覆蓋（overlay）技術(shù)，只把需要的指令和數(shù)據(jù)保存在內(nèi)存當(dāng)中
程序太多，自動(dòng)的交換（swapping）技術(shù)，把暫時(shí)不能執(zhí)行的程序送到外存
想在有限的內(nèi)存中，以更小的頁(yè)粒度為單位裝入更多更大的程序，采用自動(dòng)的虛擬存儲(chǔ)技術(shù)

5.2 覆蓋技術(shù)

目標(biāo)：是在較小的可用內(nèi)存中運(yùn)行較大的程序。常用于多道程序系統(tǒng)，與分區(qū)存儲(chǔ)管理配合使用
原理：把程序按照自身邏輯結(jié)構(gòu)，劃分為若干個(gè)功能上相對(duì)獨(dú)立的程序模塊，那些不會(huì)同時(shí)執(zhí)行的模塊共享同一塊內(nèi)存區(qū)域，按時(shí)間先后來(lái)運(yùn)行
必要部分（常用功能）的代碼和數(shù)據(jù)常駐內(nèi)存
可選部分（不常用功能）在其他程序模塊中實(shí)現(xiàn)，平時(shí)存放在外存中，在需要用到時(shí)才裝入內(nèi)存
不存在調(diào)用關(guān)系的模塊不必同時(shí)裝入內(nèi)存，從而可以相互覆蓋，即這些模塊共用一個(gè)分區(qū)
缺點(diǎn)：
由程序員來(lái)把一個(gè)大的程序劃分為若干個(gè)小的功能模塊，并確定各個(gè)模塊之間的覆蓋關(guān)系，費(fèi)時(shí)費(fèi)力，增加了編程的復(fù)雜度
覆蓋模塊從外存裝入內(nèi)存，實(shí)際上是以時(shí)間延長(zhǎng)來(lái)?yè)Q取空間節(jié)省

5.3 交換技術(shù)

目標(biāo)：多道程序在內(nèi)存中時(shí)，讓正在運(yùn)行的程序或需要運(yùn)行的程序獲得更多的內(nèi)存資源
方法：
可將暫時(shí)不能運(yùn)行的程序送到外存，從而獲得空閑內(nèi)存空間
操作系統(tǒng)把一個(gè)進(jìn)程的整個(gè)地址空間的內(nèi)容保存到外存中（換出swap out），而將外存中的某個(gè)進(jìn)程的地址空間讀入到內(nèi)存中（換入swap in）。換入換出內(nèi)容 的大小為整個(gè)程序的地址空間
幾個(gè)問(wèn)題
交換時(shí)機(jī)的確定：只有當(dāng)內(nèi)存空間不夠或有不夠的危險(xiǎn)時(shí)換出
交換區(qū)的大?。罕仨氉銐虼笠源娣潘杏脩?hù)進(jìn)程的所有內(nèi)存映像的拷貝；必須能對(duì)這些內(nèi)存映像進(jìn)行直接存取
程序換入時(shí)的重定位：換出后再換入內(nèi)存位置一定要在原來(lái)的位置上嗎？最好采用動(dòng)態(tài)地址映射的方法
覆蓋與交換的比較
覆蓋只能發(fā)生在那些相互之間沒(méi)有調(diào)用關(guān)系的程序模塊之間，因此程序員必須給出程序內(nèi)各個(gè)模塊之間的邏輯覆蓋結(jié)構(gòu)
交換技術(shù)是以在內(nèi)存中的程序大小為單位進(jìn)行的，它不需要程序員給出各個(gè)模塊之間的邏輯覆蓋結(jié)構(gòu)。換言之，交換發(fā)生在內(nèi)存中程序與管理程序或操作系統(tǒng)之間，而覆蓋發(fā)生在運(yùn)行程序的內(nèi)部。

5.4.1 虛存技術(shù)（上）

目標(biāo)：在內(nèi)存不夠用的情形下，可以采用覆蓋技術(shù)和交換技術(shù)，但是

覆蓋技術(shù)：需要程序員自己把整個(gè)程序劃分為若干個(gè)小的功能模塊，并確定各個(gè)模塊之間的覆蓋關(guān)系，增加了程序員的負(fù)擔(dān)。
交換技術(shù)：以進(jìn)程為交換的單位，需要把進(jìn)程的整個(gè)地址空間都換進(jìn)換出，增加了處理器的開(kāi)銷(xiāo)。
像覆蓋技術(shù)一樣，不是把程序的所有內(nèi)容都放在內(nèi)存中，因而能夠運(yùn)行比當(dāng)前空閑內(nèi)存空間還要大的程序。但做得更好，由操作系統(tǒng)自動(dòng)來(lái)完成，無(wú)需程序員的干涉

像交換技術(shù)那樣，能夠?qū)崿F(xiàn)進(jìn)程在內(nèi)存與外存之間的交換，因而獲得更多的空閑內(nèi)存空間。但做得更好，只對(duì)進(jìn)程的部分內(nèi)容在內(nèi)存和外存之間進(jìn)行交換
程序的局部性原理
指程序在執(zhí)行的過(guò)程中的一個(gè)較短時(shí)期，所執(zhí)行的指令地址和指令的操作數(shù)地址，分別局限于一定區(qū)域，可以表現(xiàn)為：

時(shí)間局部性：一條指令的一次執(zhí)行和下次執(zhí)行，一個(gè)數(shù)據(jù)的一次訪問(wèn)和下次訪問(wèn)，都集中在一個(gè)較短時(shí)期內(nèi)
空間局部性：當(dāng)前指令和鄰近的幾條指令，當(dāng)前訪問(wèn)的數(shù)據(jù)和鄰近的幾個(gè)數(shù)據(jù)都集中在較小的區(qū)域內(nèi)。
基本概念：

可以在頁(yè)式或段式內(nèi)存管理的基礎(chǔ)上實(shí)現(xiàn)
在裝入程序時(shí)，不必將其全部裝入到內(nèi)存，而只需將當(dāng)前執(zhí)行的部分頁(yè)面或段裝入到內(nèi)存，就可以讓程序開(kāi)始執(zhí)行
在程序執(zhí)行過(guò)程中，如果需執(zhí)行的指令或訪問(wèn)的數(shù)據(jù)尚未在內(nèi)存中（稱(chēng)為缺頁(yè)或缺段），則由處理器通知操作系統(tǒng)將相應(yīng)的頁(yè)面或段調(diào)入到內(nèi)存，然后繼續(xù)執(zhí)行程序
另一方面，操作系統(tǒng)將內(nèi)存中暫時(shí)不使用的頁(yè)面或段調(diào)出保存在外存上，從而騰出更多的空閑空間存放將要裝入的程序以及將要調(diào)入的頁(yè)面或段
基本特征：
大的用戶(hù)空間：通過(guò)把物理內(nèi)存與外存相結(jié)合，提供給用戶(hù)的虛擬內(nèi)存空間通常大于實(shí)際的物理內(nèi)存，即實(shí)現(xiàn)了這兩者的分離
部分交換：與交換技術(shù)相比較，虛擬存儲(chǔ)的調(diào)入和調(diào)出是對(duì)部分虛擬地址空間進(jìn)行的
不連續(xù)性：物理內(nèi)存分配的不連續(xù)，虛擬地址空間使用的不連續(xù)

5.4.2 虛存技術(shù)（下）

虛存技術(shù) - 虛擬頁(yè)式內(nèi)存管理
大部分虛擬存儲(chǔ)系統(tǒng)都采用虛擬頁(yè)式存儲(chǔ)管理技術(shù)，即在頁(yè)式存儲(chǔ)管理的基礎(chǔ)上，增加請(qǐng)求調(diào)頁(yè)和頁(yè)面置換功能
基本思路：

當(dāng)一個(gè)用戶(hù)程序要調(diào)入內(nèi)存運(yùn)行時(shí)，不是將該程序的所有頁(yè)面都裝入內(nèi)存，而是只裝入部分的頁(yè)面，就可啟動(dòng)程序運(yùn)行
在運(yùn)行過(guò)程中，如果發(fā)現(xiàn)要運(yùn)行的程序或要訪問(wèn)數(shù)據(jù)不再內(nèi)存，則向系統(tǒng)發(fā)出缺頁(yè)中斷請(qǐng)求，系統(tǒng)在處理這個(gè)中斷時(shí)，將外存中相應(yīng)的頁(yè)面調(diào)入內(nèi)存，使得該程序能夠繼續(xù)運(yùn)行
頁(yè)表表項(xiàng)：

邏輯頁(yè)號(hào)i | 訪問(wèn)位 | 修改位 | 保護(hù)位 | 駐留位 | 物理頁(yè)幀號(hào) |
駐留位：表示該頁(yè)是在內(nèi)存還是在外存，如果該位為1，表示該頁(yè)位于內(nèi)存當(dāng)中，即該頁(yè)表項(xiàng)是有效的，可以使用；如果該位為0，表示該頁(yè)當(dāng)前還在外存當(dāng)中，如果訪問(wèn)該頁(yè)表項(xiàng)，將導(dǎo)致缺頁(yè)中斷
保護(hù)位：表示允許對(duì)該頁(yè)做何種類(lèi)型的訪問(wèn)，如只讀、可讀寫(xiě)、可執(zhí)行等
修改位：表明此頁(yè)在內(nèi)存中是否被修改過(guò)。當(dāng)系統(tǒng)回收該物理頁(yè)面時(shí)，根據(jù)此位來(lái)決定是否把它的內(nèi)容寫(xiě)回外存
訪問(wèn)位：如果該頁(yè)面被訪問(wèn)過(guò)（包括讀操作或?qū)懖僮鳎瑒t設(shè)置此位。用于頁(yè)面置換算法
缺頁(yè)中斷處理過(guò)程：
如果在內(nèi)存中有空閑的物理頁(yè)面，則分配一物理頁(yè)幀f，然后轉(zhuǎn)第4步；
采用某種頁(yè)面置換算法，選擇一個(gè)將被替換的物理頁(yè)幀f，它所對(duì)應(yīng)的邏輯頁(yè)為q。如果該頁(yè)在內(nèi)存期間被修改過(guò)，則需把它寫(xiě)回外存；
對(duì)q所對(duì)應(yīng)的頁(yè)表項(xiàng)進(jìn)行修改，把駐留位置為0；
將需要訪問(wèn)的頁(yè)p裝入到物理頁(yè)面f當(dāng)中；
修改p所對(duì)應(yīng)的頁(yè)表項(xiàng)的內(nèi)容，把駐留位置為1，把物理頁(yè)幀號(hào)置為f；
重新運(yùn)行被中斷的指令；
后備存儲(chǔ)（Backing store）
在何處保存未被映射的頁(yè)？
能夠簡(jiǎn)單的識(shí)別在二級(jí)存儲(chǔ)器中的頁(yè)
交換空間（磁盤(pán)或文件）：特殊格式，用于存儲(chǔ)未被映射的頁(yè)面
概念：
一個(gè)虛擬地址空間的頁(yè)面可以被映射到文件（在二級(jí)存儲(chǔ)中）中的某個(gè)位置
代碼段：映射到可執(zhí)行二進(jìn)制文件
動(dòng)態(tài)加載的共享庫(kù)程序段：映射到動(dòng)態(tài)調(diào)用的庫(kù)文件
其他段：可能被映射到交換文件（swap file）
虛擬內(nèi)存性能
為了便于理解分頁(yè)的開(kāi)銷(xiāo)，使用有效存儲(chǔ)器訪問(wèn)時(shí)間（EAT）
EAT = 訪存時(shí)間 * 頁(yè)表命中幾率 + page fault 處理時(shí)間 * page fault 幾率
例

• 訪存時(shí)間：10 ns
• 磁盤(pán)訪問(wèn)：5 ms
• 參數(shù)p = page fault 幾率
• 參數(shù)q = dirty page 幾率
• EAT = 10(1-p) + 5,000,000 p(1*q)

第6章：頁(yè)面置換算法

功能與目標(biāo)
實(shí)驗(yàn)設(shè)置與評(píng)價(jià)方法
局部頁(yè)面置換算法
最優(yōu)頁(yè)面置換算法（OPT，optional）
先進(jìn)先出算法（FIFO，F(xiàn)irst-In First-Out）
最近最久未使用算法（LRU，Least Recently Used）
時(shí)鐘頁(yè)面置換算法（Clock）
二次機(jī)會(huì)法
最不常用算法（LFU，Least Frequently Used）
Belady 現(xiàn)象
LRU、FIFO和Clock的比較
全局頁(yè)面置換算法
工作集模型
工作集置換算法
缺頁(yè)率置換算法

• （一）功能目標(biāo)

功能：
當(dāng)缺頁(yè)中斷發(fā)生，需要調(diào)入新的頁(yè)面而內(nèi)存已滿時(shí)，選擇內(nèi)存當(dāng)中哪個(gè)物理頁(yè)面被置頂
目標(biāo)：
盡可能地減少頁(yè)面的換入換出次數(shù)（即缺頁(yè)中斷的次數(shù)），具體來(lái)說(shuō)，把未來(lái)不再使用的或短期內(nèi)較少使用的頁(yè)面換出，通常只能在局部性原理指導(dǎo)下依據(jù)過(guò)去的統(tǒng)計(jì)數(shù)據(jù)來(lái)進(jìn)行預(yù)測(cè)
頁(yè)面鎖定（frame locking）：
用于描述必須常駐內(nèi)存的操作系統(tǒng)的關(guān)鍵部分或時(shí)間關(guān)鍵（time - critical）的應(yīng)用進(jìn)程。實(shí)現(xiàn)的方法是：在頁(yè)表中添加鎖定標(biāo)志位（lock bit）

6.1 最優(yōu)頁(yè)面置換算法（OPT，optional）

基本思路：
當(dāng)一個(gè)缺頁(yè)中斷發(fā)生時(shí)，對(duì)于保存在內(nèi)存中的每一個(gè)邏輯頁(yè)面，計(jì)算在它的下一次訪問(wèn)之前，還需等待多長(zhǎng)時(shí)間，從中選擇等待時(shí)間最長(zhǎng)的那個(gè)，作為被置換的頁(yè)面
這只是一種理想情況，在實(shí)際系統(tǒng)中是無(wú)法實(shí)現(xiàn)的，因?yàn)椴僮飨到y(tǒng)無(wú)從得知每一個(gè)頁(yè)面要等待多長(zhǎng)時(shí)間以后才會(huì)再次被訪問(wèn)
可用作其他算法的性能評(píng)價(jià)的依據(jù)（在一個(gè)模擬器上運(yùn)行某個(gè)程序，并記錄每一次頁(yè)面訪問(wèn)情況，在第二遍運(yùn)行時(shí)即可使用最優(yōu)置換算法）

6.2 先進(jìn)先出算法（FIFO，F(xiàn)irst-In First-Out）

基本思路：
選擇在內(nèi)存中駐留時(shí)間最長(zhǎng)的頁(yè)面并淘汰之。具體來(lái)說(shuō)，系統(tǒng)維護(hù)著一個(gè)鏈表，記錄了所有位于內(nèi)存當(dāng)中的邏輯頁(yè)面。從鏈表的排列順序來(lái)看，鏈?zhǔn)醉?yè)面的駐留時(shí)間最長(zhǎng)，鏈尾頁(yè)面的駐留時(shí)間最短。當(dāng)發(fā)生一個(gè)缺頁(yè)中斷時(shí)，把鏈?zhǔn)醉?yè)淘汰出局，并把新的頁(yè)面添加到鏈表的末尾。
性能較差，調(diào)出的頁(yè)面有可能是經(jīng)常要訪問(wèn)的頁(yè)面，并且有Belady現(xiàn)象，F(xiàn)IFO算法很少單獨(dú)使用。

6.3 最近最久未使用算法（LRU，Least Recently Used）

基本思路：

當(dāng)一個(gè)缺頁(yè)中斷發(fā)生時(shí)，選擇最久未使用的那個(gè)頁(yè)面，并淘汰之。
它是對(duì)最優(yōu)頁(yè)面置換算法的一個(gè)近似，其依據(jù)是程序的局部性原理，即在最近一小段時(shí)間（最近幾條指令）內(nèi)，如果某些頁(yè)面被頻繁地訪問(wèn)，那么在將來(lái)的一小段時(shí)間內(nèi)，它們還可能會(huì)再一次被頻繁地訪問(wèn)。反過(guò)來(lái)說(shuō)，如果在過(guò)去某些頁(yè)面長(zhǎng)時(shí)間未被訪問(wèn)，那么在將來(lái)它們還可能會(huì)長(zhǎng)時(shí)間地得不到訪問(wèn)。
LRU算法需要記錄各個(gè)頁(yè)面使用時(shí)間的先后順序，開(kāi)銷(xiāo)較大
兩種可能的實(shí)現(xiàn)方法是：

系統(tǒng)維護(hù)一個(gè)頁(yè)面鏈表，最近剛使用過(guò)的頁(yè)面作為首結(jié)點(diǎn)，最久未使用的頁(yè)面作為尾結(jié)點(diǎn)。每一次訪問(wèn)內(nèi)存時(shí)，找到相應(yīng)的頁(yè)面，把它從鏈表中摘下來(lái)，再移動(dòng)到鏈表之首，如果沒(méi)有，則直接插入到鏈表之首。每次缺頁(yè)中斷發(fā)生時(shí)，淘汰鏈表末尾的頁(yè)面。
設(shè)置一個(gè)活動(dòng)頁(yè)面棧，當(dāng)訪問(wèn)某頁(yè)時(shí)，將此頁(yè)號(hào)壓入棧頂，然后，考察棧內(nèi)是否有與此頁(yè)面相同的頁(yè)號(hào)，若有則抽出。當(dāng)需要淘汰一個(gè)頁(yè)面時(shí)，總是選擇棧底的頁(yè)面，它就是最久未使用的。

6.4 時(shí)鐘頁(yè)面置換算法（Clock）

LRU的近似，對(duì)FIFO的一種改進(jìn)
基本思路：
需要用到頁(yè)表項(xiàng)當(dāng)中的訪問(wèn)位，當(dāng)一個(gè)頁(yè)面被裝入內(nèi)存時(shí)，把該位初始化為0.然后如果這個(gè)頁(yè)面被訪問(wèn)（讀/寫(xiě)），則把該位置為1；
把各個(gè)頁(yè)面組織成環(huán)形鏈表（類(lèi)似時(shí)鐘表面），把指針指向最老的頁(yè)面（最先進(jìn)來(lái)）；
當(dāng)發(fā)生一個(gè)缺頁(yè)中斷時(shí)，考察指針?biāo)赶虻淖罾享?yè)面，若它的訪問(wèn)位為0，立即淘汰；若訪問(wèn)位為1，則把該位置為0，然后指針往下移動(dòng)一格。如此下去，直到找到被淘汰的頁(yè)面，然后把指針移動(dòng)到它的下一格。

6.5 二次機(jī)會(huì)法

這里有一個(gè)巨大的代價(jià)來(lái)替換“臟頁(yè)”
修改Clock算法，使它允許臟頁(yè)總是在時(shí)鐘頭掃描中保留出來(lái)
同時(shí)使用臟位和使用位來(lái)指導(dǎo)置換
used dirty used’ dirty’
0 0 replace page
0 1 0 0
1 0 0 0
1 1 0 1

6.6 最不常用算法（LFU，Least Frequently Used）

基本思路：
當(dāng)一個(gè)缺頁(yè)中斷發(fā)生時(shí)，選擇訪問(wèn)次數(shù)最少的那個(gè)頁(yè)面，并淘汰之。
實(shí)現(xiàn)方法：
對(duì)每個(gè)頁(yè)面設(shè)置一個(gè)訪問(wèn)計(jì)數(shù)器，每當(dāng)一個(gè)頁(yè)面被訪問(wèn)時(shí)，該頁(yè)面的訪問(wèn)計(jì)數(shù)器加1。在發(fā)生缺頁(yè)中斷時(shí)，淘汰計(jì)數(shù)值最小的那個(gè)頁(yè)面。
LRU 和 LFU的區(qū)別：

LRU考察的是多久未訪問(wèn)，時(shí)間越短越好；而LFU考察的是訪問(wèn)的次數(shù)或頻率，訪問(wèn)次數(shù)越多越好。
問(wèn)題：

一個(gè)頁(yè)面在進(jìn)程開(kāi)始時(shí)使用得多，但以后就不使用了。實(shí)現(xiàn)費(fèi)時(shí)費(fèi)力。
解決方法：

定期把次數(shù)寄存器右移一位

6.7 Belady現(xiàn)象

Belady現(xiàn)象：

在采用FIFO算法時(shí)，有時(shí)會(huì)出現(xiàn)分配的物理頁(yè)面數(shù)增加，缺頁(yè)率反而提高的異?，F(xiàn)象。
原因：

FIFO算法的置換特征與進(jìn)程訪問(wèn)內(nèi)存的動(dòng)態(tài)特征是矛盾的，與置換算法的目標(biāo)是不一致的（即替換較少使用的頁(yè)面），因?yàn)?，被它置換出去的頁(yè)面并不一定是進(jìn)程不會(huì)訪問(wèn)的。

6.8 LRU、FIFO和Clock的比較

LRU算法和FIFO本質(zhì)上都是先進(jìn)先出的思路，只不過(guò)LRU是針對(duì)頁(yè)面的最近訪問(wèn)時(shí)間來(lái)進(jìn)行排序，所以需要在每一次訪問(wèn)的時(shí)候動(dòng)態(tài)地調(diào)整各個(gè)頁(yè)面之間的先后順序（有一個(gè)頁(yè)面的最近訪問(wèn)時(shí)間變了）；而FIFO是針對(duì)頁(yè)面進(jìn)入內(nèi)存的時(shí)間來(lái)進(jìn)行排序，這個(gè)時(shí)間是固定不變的，所以各個(gè)頁(yè)面之間的先后順序是固定的。如果一個(gè)頁(yè)面在進(jìn)入內(nèi)存后沒(méi)有被訪問(wèn)，那么它的最近訪問(wèn)時(shí)間就是它進(jìn)入內(nèi)存的時(shí)間。換句話說(shuō)，如果內(nèi)存當(dāng)中的所有頁(yè)面都未曾訪問(wèn)過(guò)，那么LRU算法就退化為FIFO算法。
LRU算法性能較好，但系統(tǒng)開(kāi)銷(xiāo)大；FIFO算法系統(tǒng)開(kāi)銷(xiāo)較小，但可能會(huì)發(fā)生Belady現(xiàn)象。因此，折中的辦法是Clock算法，在每一次頁(yè)面訪問(wèn)時(shí)，它不必去動(dòng)態(tài)地調(diào)整該頁(yè)面在鏈表中的順序，而僅僅是做一個(gè)標(biāo)記，然后等到發(fā)生缺頁(yè)中斷時(shí)，再把它移動(dòng)到鏈表的末尾，對(duì)于內(nèi)存中那些被訪問(wèn)過(guò)的頁(yè)面，它不能像LRU算法一樣，記住它們的準(zhǔn)確位置。

6.9 工作集模型

（一）工作集

defs:
一個(gè)進(jìn)程當(dāng)前正在使用的邏輯頁(yè)面集合，可以用一個(gè)二元函數(shù) w(t,△）來(lái)表示
t 是當(dāng)前執(zhí)行時(shí)刻
△ 稱(chēng)為工作集窗口（working-set window），即一個(gè)定長(zhǎng)的頁(yè)面訪問(wèn)的時(shí)間窗口
w(t,△）= 在當(dāng)前時(shí)刻t之前的 △ 時(shí)間窗口當(dāng)中的所有頁(yè)面組成的集合（隨著t的變化，該集合也在不斷的變化）
|w(t,△）|指工作集的大小，即頁(yè)面數(shù)目|
（二）常駐集

defs:
是指在當(dāng)前時(shí)刻，進(jìn)程實(shí)際駐留在內(nèi)存當(dāng)中的頁(yè)面集合
工作集是進(jìn)程在運(yùn)行過(guò)程中固有的性質(zhì)，而常駐集取決于系統(tǒng)分配給進(jìn)程的物理頁(yè)面數(shù)目，以及所采用的頁(yè)面置換算法
如果一個(gè)進(jìn)程的整個(gè)工作集都在內(nèi)存當(dāng)中，即常駐集包含（=）工作集，那么進(jìn)程將很順利的運(yùn)行，而不會(huì)造成太多的缺頁(yè)中斷（直到工作集發(fā)生劇烈變動(dòng)，從而過(guò)渡到另一個(gè)狀態(tài)）
當(dāng)進(jìn)程常駐集的大小達(dá)到某個(gè)數(shù)目后，再給它分配更多的物理頁(yè)面，缺頁(yè)率也不會(huì)明顯下降

6.10 兩個(gè)全局頁(yè)面置換算法

（一）缺頁(yè)率頁(yè)面置換算法

可變分配策略：
常駐集大小可變。例如，每個(gè)進(jìn)程在剛開(kāi)始運(yùn)行的時(shí)候，先根據(jù)程序的大小給它分配一定數(shù)目的物理頁(yè)面，然后在運(yùn)行過(guò)程中，再動(dòng)態(tài)的調(diào)整常駐集的大小。
可采用全局頁(yè)面置換的方式，當(dāng)發(fā)生一個(gè)缺頁(yè)中斷時(shí)，被置換的頁(yè)面可以是在其他進(jìn)程當(dāng)中，各個(gè)并發(fā)進(jìn)程競(jìng)爭(zhēng)地使用物理頁(yè)面。
優(yōu)缺點(diǎn)：

性能較好，但增加了系統(tǒng)開(kāi)銷(xiāo)
具體實(shí)現(xiàn)：

可以使用缺頁(yè)率算法（PFF, Page fault frequency)來(lái)動(dòng)態(tài)調(diào)整常駐集的大小
缺頁(yè)率：

缺頁(yè)率表示“缺頁(yè)次數(shù)/內(nèi)存訪問(wèn)次數(shù)”（比率）或“缺頁(yè)的平均時(shí)間間隔的倒數(shù)”。
影響缺頁(yè)率的因素：

頁(yè)面置換算法
分配給進(jìn)程的物理頁(yè)面數(shù)目
頁(yè)面本身的大小
程序的編寫(xiě)方法
缺頁(yè)率算法
若運(yùn)行的程序的缺頁(yè)率過(guò)高，則通過(guò)增加工作集來(lái)分配更多的物理頁(yè)面
若運(yùn)行的程序缺頁(yè)率過(guò)低，則通過(guò)減少工作集來(lái)減少它的物理頁(yè)面數(shù)
力圖使運(yùn)行的每個(gè)程序的缺頁(yè)率保持在一個(gè)合理的范圍內(nèi)
一個(gè)交替的工作集計(jì)算明確的適于最小化頁(yè)缺失
當(dāng)缺頁(yè)率高的時(shí)候–增加工作集
當(dāng)缺頁(yè)率低的時(shí)候–減少工作集
算法：
保持追蹤缺失發(fā)生概率
當(dāng)缺失發(fā)生時(shí)，從上次頁(yè)缺失起計(jì)算這個(gè)時(shí)間記錄這個(gè)時(shí)間，t’last 是上次的頁(yè)缺失時(shí)間
如果發(fā)生頁(yè)缺失之間的時(shí)間是“大”的，之后減少工作集
如果 t’current - t’last > T，之后從內(nèi)存中移除所有在[t’last,t’current]時(shí)間內(nèi)沒(méi)有被引用的頁(yè)
如果發(fā)生頁(yè)缺失之間的時(shí)間是“小”的，之后增加工作集
如果 t’current - t’last <= T，之后增加缺失頁(yè)到工作集中

6.11 抖動(dòng)問(wèn)題(Trashing)

defs:
如果分配給一個(gè)進(jìn)程的物理頁(yè)面很少，不能包含整個(gè)的工作集，那常駐集含于工作集，那么進(jìn)程將會(huì)造成很多的缺頁(yè)中斷，需要頻繁地在內(nèi)存到外存之間替換頁(yè)面，從而使進(jìn)程的運(yùn)行速度變得很慢，我們把這種狀態(tài)稱(chēng)為“抖動(dòng)”。
產(chǎn)生抖動(dòng)的原因：

隨著駐留內(nèi)存的進(jìn)程數(shù)目增加，分配給每個(gè)進(jìn)程的物理頁(yè)面數(shù)不斷減小，缺頁(yè)率不斷上升。所以操作系統(tǒng)要選擇一個(gè)適當(dāng)?shù)倪M(jìn)程數(shù)目和進(jìn)程需要的幀數(shù)，以便在并發(fā)水平和缺頁(yè)率之間達(dá)到一個(gè)平衡。
抖動(dòng)問(wèn)題可能會(huì)被本地的頁(yè)面置換算法改善

更好的規(guī)則為加載控制：調(diào)整MPL
平均頁(yè)缺失時(shí)間（MTBF, mean time between page faults)
頁(yè)缺失服務(wù)時(shí)間（PFST，page fault service time）