操作系統(tǒng)基本概念

操作系統(tǒng)是計(jì)算機(jī)科學(xué)研究基石之一。

功能

• 管理硬件（如設(shè)備驅(qū)動(dòng)：實(shí)現(xiàn)用戶提出的I/O操作請求蛀醉，完成數(shù)據(jù)的輸入輸出）
• 管理內(nèi)存：物理內(nèi)存/虛擬內(nèi)存
• 處理中斷

內(nèi)核特征

• 并發(fā)：一段時(shí)間內(nèi)多個(gè)程序執(zhí)行
• 共享(資源)：“同時(shí)”訪問宴抚，互斥共享
• 虛擬：將硬件虛擬化(CPU->進(jìn)程绊序，磁盤->文件乱投，內(nèi)存->地址)
• 異步：程序走走停停衅檀，但保證程序結(jié)果一致

操作系統(tǒng)啟動(dòng)過程

• OS存放在硬盤上

BIOS：基本I/O處理系統(tǒng)

• 早期的 BIOS 存儲(chǔ)在 ROM 中选调，并且其大小不會(huì)超過 64KB夹供；而目前的 BIOS 大多有1MB 到 2MB，所以會(huì)被存儲(chǔ)在閃存（Flash Memory）中

ROM是只讀存儲(chǔ)器仁堪，存在里面的東西不能刪除和修改哮洽，只能讀取、復(fù)制等弦聂；
閃存是在斷電以后不丟失數(shù)據(jù)的存儲(chǔ)器鸟辅，不能以字節(jié)的方式擦除信息氛什，只能以區(qū)域/塊的方式擦除(如U盤)

• PSOT(Power-On Self-Test)：加電自檢，主要是對 CPU匪凉、內(nèi)存等硬件設(shè)備進(jìn)行檢測和初始化枪眉，執(zhí)行BIOS；
• 啟動(dòng)順序：硬件自檢完成后再层，BIOS需要知道"下一階段的啟動(dòng)程序"具體存放在哪一個(gè)設(shè)備贸铜。也就是說，BIOS需要有一個(gè)外部儲(chǔ)存設(shè)備的排序聂受，排在前面的設(shè)備就是優(yōu)先轉(zhuǎn)交控制權(quán)的設(shè)備蒿秦；
• 主引導(dǎo)記錄：BIOS按照"啟動(dòng)順序"，把控制權(quán)轉(zhuǎn)交給排在第一位的儲(chǔ)存設(shè)備蛋济，將BootLoader從磁盤的引導(dǎo)扇區(qū)加載到內(nèi)存的0x7c00處棍鳖；跳轉(zhuǎn)到CS：IP = 0000:7c00處開始執(zhí)行BootLoader

CS為代碼段寄存器，IP為指令指針寄存器瘫俊，任意時(shí)刻鹊杖，CPU將CS:IP指向的內(nèi)容當(dāng)作指令執(zhí)行。
在8086系統(tǒng)中扛芽，訪問存儲(chǔ)器的地址碼由段地址(CS)和段內(nèi)偏移地址(IP)兩部分組成段寄存器用來存放各分段的邏輯基值骂蓖。

BootLoader：加載OS

• 存放在硬盤第一個(gè)引導(dǎo)扇區(qū)，512個(gè)字節(jié)
• 將操作系統(tǒng)的代碼和數(shù)據(jù)從硬盤加載到內(nèi)存
• 跳轉(zhuǎn)到操作系統(tǒng)的起始地址

總結(jié)上述流程如下圖所示：

操作系統(tǒng)啟動(dòng)示意圖

中斷川尖、異常登下、系統(tǒng)調(diào)用

操作系統(tǒng)的交互

• 面向外設(shè)：中斷和I/O
• 面向應(yīng)用程序：異常和系統(tǒng)調(diào)用

中斷(來源于外設(shè))：來自不同的硬件設(shè)備的計(jì)時(shí)器和網(wǎng)絡(luò)的中斷

• 引入中斷技術(shù)的初衷是提高多道程序運(yùn)行環(huán)境中CPU的利用率，而且主要是針對外部設(shè)備的叮喳。后來逐步得到發(fā)展被芳，形成了多種類型，成為操作系統(tǒng)各項(xiàng)操作的基礎(chǔ)馍悟。例如畔濒，鍵盤或鼠標(biāo)信息的輸入、進(jìn)程的管理和調(diào)度锣咒、系統(tǒng)功能的調(diào)用塑顺、設(shè)備驅(qū)動(dòng)捞慌、文件訪問等，無不依賴于中斷機(jī)制择示∧垢埃可以說屯断，現(xiàn)代操作系統(tǒng)是靠中斷驅(qū)動(dòng)的軟件解孙。

特點(diǎn)

• 異步
• 持續(xù)的回还，對用戶應(yīng)用程序是透明的，用戶感知不到中斷
• 常見中斷類型：程序中斷，時(shí)鐘中斷蹋凝，I/O中斷鲁纠，硬件中斷

相關(guān)術(shù)語

• 中斷源 ：引起中斷發(fā)生的事件
• 中斷請求：中斷源向CPU發(fā)出的請求中斷處理信號(hào)
• 中斷響應(yīng)：CPU收到中斷請求后轉(zhuǎn)去執(zhí)行相應(yīng)的事件處理程序
• 中斷屏蔽：在中斷請求產(chǎn)生后，系統(tǒng)用軟件方式有選擇的封鎖中斷仙粱，而允許其他中斷仍能得到響應(yīng)
• 關(guān)中斷：又稱禁止中斷房交，CPU內(nèi)部處理機(jī)狀態(tài)字（PSW）中斷允許位被清除彻舰，不允許CPU響應(yīng)中斷
• 開中斷：與關(guān)中斷相反伐割，CPU內(nèi)部處理機(jī)狀態(tài)字（PSW）中斷允許位被恢復(fù)，允許CPU響應(yīng)中斷

中斷分類

• 硬中斷

1. 外中斷：來自CPU外部和內(nèi)存外部的中斷（如I/O中斷和外部信號(hào)中斷刃唤，其實(shí)就是我們一般上說的隔心，狹義上的中斷）
2. 內(nèi)中斷：來自CPU內(nèi)部和內(nèi)存內(nèi)部產(chǎn)生的中斷，也稱為陷入（trap）或者異常尚胞，（比如常見的算術(shù)溢出硬霍，除數(shù)為0，地址非法笼裳，缺頁等等）

• 軟中斷：是一條CPU指令唯卖，主要用于執(zhí)行系統(tǒng)調(diào)用（int 0x80匯編指令）以及給調(diào)試程序通報(bào)一個(gè)特定的事件，屬于同步中斷

所有的硬中斷的優(yōu)先級都高于軟中斷躬柬，各中斷的優(yōu)先級在系統(tǒng)設(shè)計(jì)初期給出拜轨，在運(yùn)行過程中是不變的。

中斷優(yōu)先級

• 說明：在實(shí)際系統(tǒng)中橄碾，常常遇到多個(gè)中斷源同時(shí)請求中斷的情況，這時(shí)CPU必須確定首先為哪一個(gè)中斷源服務(wù)颠锉，以及服務(wù)的次序
• 優(yōu)先級：解決的方法是中斷優(yōu)先排隊(duì)法牲，即根據(jù)中斷源請求的輕重緩急，排好中斷處理的優(yōu)先次序即優(yōu)先級琼掠，先響應(yīng)優(yōu)先級最高的中斷請求
• 中斷嵌套：當(dāng)CPU正在處理某一中斷時(shí)拒垃，要能響應(yīng)另一個(gè)優(yōu)先級更高的中斷請求，而屏蔽掉同級或較低級的中斷請求瓷蛙，形成中斷嵌套

中斷處理過程

• 硬件：設(shè)置中斷標(biāo)記[CPU初始化]

1. 將內(nèi)部悼瓮、外部事件設(shè)置中斷標(biāo)記
2. 生成中斷事件的ID

• 軟件

1. 保存當(dāng)前處理狀態(tài) [保護(hù)現(xiàn)場]
2. 中斷服務(wù)程序處理(中斷向量表) [中斷服務(wù)]
3. 清除中斷標(biāo)記 [恢復(fù)現(xiàn)場]
4. 恢復(fù)之前保存的狀態(tài) [中斷返回]

中斷向量與中斷向量表

• 中斷向量：Intel x86系列微機(jī)共支持256種向量中斷，為使處理器較容易地識(shí)別每種中斷源速挑，將它們從0～255 編號(hào)谤牡，即賦予一個(gè)中斷類型碼n，這個(gè)8位的無符號(hào)整數(shù)叫做一個(gè)向量姥宝，也叫中斷向量翅萤。

• 中斷向量表：在實(shí)地址模式中，CPU 把內(nèi)存中從0 開始的1K 字節(jié)作為一個(gè)中斷向量表；表中的每個(gè)表項(xiàng)占4個(gè)字節(jié)套么，由兩個(gè)字節(jié)的段基址和兩個(gè)字節(jié)的偏移量組成培己，這樣構(gòu)成的地址便是相應(yīng)中斷處理程序的入口地址。

Linux 對256 個(gè)中斷向量的分配如下：

• 從 0~31 的向量對應(yīng)于異常（不能被屏蔽）和非屏蔽中斷胚泌；
• 從 32~47 的向量分配給屏蔽中斷（即由I/O 設(shè)備引起的中斷）省咨；
• 從 48~255 的向量用來標(biāo)識(shí)軟中斷。Linux 只用了其中的一個(gè)（即128 或0x80向量）用來實(shí)現(xiàn)系統(tǒng)調(diào)用玷室。當(dāng)用戶態(tài)下的進(jìn)程執(zhí)行一條int 0x80匯編指令時(shí)零蓉，CPU 就切換到內(nèi)核態(tài)，并開始執(zhí)行 system_call() 內(nèi)核函數(shù)穷缤。

參考中斷向量表 中斷描述符

異常：非法指令或其他壞的處理狀態(tài)(如內(nèi)存出錯(cuò))

特點(diǎn)

• 同步
• 殺死或重新執(zhí)行意想不到的的程序指令（此時(shí)操作系統(tǒng)可能支持此指令了）

異常分類

• 故障（Fault）：如缺頁中斷
• 陷阱（Trap）：調(diào)用某些系統(tǒng)函數(shù)敌蜂，如打開文件的時(shí)候，觸發(fā)陷阱津肛，進(jìn)行系統(tǒng)調(diào)用
• 夭折（Abort）：發(fā)生嚴(yán)重錯(cuò)誤章喉，無法恢復(fù)運(yùn)行

異常處理過程

• 保存現(xiàn)場
• 異常處理

1. 殺死異常程序
2. 重新執(zhí)行異常指令

• 恢復(fù)現(xiàn)場

系統(tǒng)調(diào)用：應(yīng)用程序主動(dòng)向操作系統(tǒng)發(fā)出服務(wù)請求

特點(diǎn)

• 同步或異步
• 等待和持續(xù)（系統(tǒng)返回?cái)?shù)據(jù)后繼續(xù)執(zhí)行）

系統(tǒng)調(diào)用處理過程

• 應(yīng)用程序訪問高層次API接口而實(shí)現(xiàn)

1. Win32 API
2. POSIX API（通用可移植系統(tǒng)調(diào)用接口，UNIX Linux）
3. Java API（非系統(tǒng)調(diào)用接口）

• 觸發(fā)用戶態(tài)到內(nèi)核態(tài)的轉(zhuǎn)換

內(nèi)核態(tài)：CPU可以訪問內(nèi)存的所有數(shù)據(jù)身坐，包括外圍設(shè)備秸脱，例如硬盤、網(wǎng)卡部蛇，CPU也可以將自己從一個(gè)程序切換到另一個(gè)程序摊唇。
用戶態(tài)：只能受限的訪問內(nèi)存，且不允許訪問外圍設(shè)備搪花，占用CPU的能力被剝奪遏片，CPU資源可以被其他程序獲取。
參考內(nèi)核態(tài)與用戶態(tài)

• 函數(shù)調(diào)用/系統(tǒng)調(diào)用區(qū)別

1. 函數(shù)調(diào)用在同一個(gè)堆棧內(nèi)完成
2. 系統(tǒng)調(diào)用存在用戶態(tài)棧和內(nèi)核態(tài)棧的切換

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

跨越操作系統(tǒng)邊界的開銷

1. 建立中斷/異常/系統(tǒng)調(diào)用號(hào)與對應(yīng)服務(wù)例程映射關(guān)系的初始化開銷
2. 建立內(nèi)核堆棧
3. 參數(shù)傳遞：把一些參數(shù)從用戶空間傳給內(nèi)核撮竿，再進(jìn)行驗(yàn)證參數(shù)（安全性）：檢查所有的參數(shù)是否合法有效
4. 內(nèi)核態(tài)映射到用戶態(tài)的地址空間吮便，更新頁面映射權(quán)限
5. 內(nèi)核態(tài)獨(dú)立地址空間

內(nèi)存管理

內(nèi)存是一個(gè)計(jì)算機(jī)最重要的部分之一，程序只有被加載到內(nèi)存中才可以運(yùn)行幢踏，CPU所需要的指令和數(shù)據(jù)也都是來自于內(nèi)存髓需。

計(jì)算機(jī)體系結(jié)構(gòu)/內(nèi)存分層結(jié)構(gòu)

• 計(jì)算機(jī)基本硬件結(jié)構(gòu)：CPU(寄存器，運(yùn)算器房蝉，控制器僚匆，緩存，存儲(chǔ)管理單元)搭幻；內(nèi)存咧擂；設(shè)備(I/O)

計(jì)算機(jī)體系結(jié)構(gòu)

• 內(nèi)存分層結(jié)構(gòu)：金字塔結(jié)構(gòu)

1. CPU寄存器
2. cache(L1緩存 L2緩存...)
3. 主存
4. 硬盤(虛擬內(nèi)存)

主存與硬盤之間存在交換/分頁

內(nèi)存金字塔

操作系統(tǒng)內(nèi)存管理目標(biāo)

• 抽象：邏輯地址空間（應(yīng)用程序不用考慮底層）
• 保護(hù)：獨(dú)立地址空間（同時(shí)運(yùn)行多個(gè)程序，進(jìn)程進(jìn)程間隔離）
• 共享：訪問相同內(nèi)存（進(jìn)程間通信）
• 虛擬化：更多的內(nèi)存空間

內(nèi)存抽象

沒有內(nèi)存抽象的年代

早期的操作系統(tǒng)中檀蹋，并沒有引入內(nèi)存抽象的概念松申。程序直接訪問和操作的都是物理內(nèi)存，內(nèi)存的管理也非常簡單，除去操作系統(tǒng)所用的內(nèi)存之外贸桶，其余全部給用戶程序使用舅逸。

但是這種無內(nèi)存抽象存在一些問題：

比如當(dāng)執(zhí)行如下指令時(shí)：mov reg1，1000

這條指令會(huì)將物理地址1000中的內(nèi)容賦值給寄存器皇筛。這種內(nèi)存操作方式使得操作系統(tǒng)中存在多進(jìn)程變得完全不可能琉历，必須執(zhí)行完一條指令后才能接著執(zhí)行下一條。如果是多進(jìn)程的話水醋，由于直接操作物理內(nèi)存地址旗笔，當(dāng)一個(gè)進(jìn)程給內(nèi)存地址1000賦值后，另一個(gè)進(jìn)程也同樣給內(nèi)存地址賦值离例，那么第二個(gè)進(jìn)程對內(nèi)存的賦值會(huì)覆蓋第一個(gè)進(jìn)程所賦的值换团，這回造成兩條進(jìn)程同時(shí)崩潰。

因此無內(nèi)存抽象存在以下問題：

1. 用戶程序可以訪問任意內(nèi)存宫蛆，容易破壞操作系統(tǒng)，造成崩潰
2. 同時(shí)運(yùn)行多個(gè)程序特別困難

參考操作系統(tǒng)內(nèi)存管理

內(nèi)存抽象：地址空間

如何做到進(jìn)程的地址受保護(hù)
操作系統(tǒng)對物理內(nèi)存做了一層抽象的猛，也就是地址空間(AddressSpace)耀盗，一個(gè)進(jìn)程的地址空間包含了該進(jìn)程所有相關(guān)內(nèi)存，如下圖所示：

AddressSpace

從低地址到高地址分別內(nèi)存區(qū)分別為：代碼段卦尊，數(shù)據(jù)段（初始化）叛拷，數(shù)據(jù)段（未初始化）（BSS），堆岂却，棧忿薇，命令行參數(shù)和環(huán)境變量。（堆向高內(nèi)存地址生長躏哩，棧向低內(nèi)存地址生長）

• 代碼段：存放全局常量（const）署浩、字符串常量、程序代碼
• 數(shù)據(jù)段（初始化）：存放初始化的全局變量扫尺、初始化的靜態(tài)變量（全局的和局部的）
• 數(shù)據(jù)段（未初始化）（BSS）：存放未初始化的全局變量筋栋、未初始化的靜態(tài)變量（全局的和局部的）
• 堆：存放動(dòng)態(tài)分配的區(qū)域（malloc、new等）
• 棧：存放局部變量（初始化以及未初始化的正驻，但不包含靜態(tài)變量）弊攘、局部常量（const）
• 命令行參數(shù)和環(huán)境變量：存放命令行參數(shù)和環(huán)境變量

參考進(jìn)程實(shí)體 內(nèi)存劃分

真實(shí)地址生成過程

地址空間分為以下兩種：

• 物理地址空間：硬件支持的地址空間(內(nèi)存條/硬盤)，從0開始姑曙，如一個(gè)內(nèi)存條的大小4GB
• 邏輯地址空間：一個(gè)運(yùn)行程序所擁有的內(nèi)存范圍襟交，如一個(gè)進(jìn)程占用的內(nèi)存范圍16KB

從進(jìn)程的角度看待內(nèi)存其范圍是0-X，但是其對應(yīng)的真實(shí)物理內(nèi)存地址應(yīng)該是base——base+X伤靠，數(shù)值base稱為進(jìn)程的基址捣域，存放在基址寄存器中。每個(gè)內(nèi)存地址送到內(nèi)存之前，都會(huì)自動(dòng)加上基址寄存器的內(nèi)容竟宋。

CPU 上用來做內(nèi)存地址轉(zhuǎn)換的叫做內(nèi)存管理單元（MMU）提完，其完成邏輯地址到物理地址的映射。

邏輯地址生成過程

邏輯地址生成的過程就是將一行行代碼轉(zhuǎn)變成內(nèi)存中具體的邏輯地址丘侠，使得CPU運(yùn)行程序時(shí)能"按圖索驥"徒欣。
高級語言編寫出來的程序邏輯地址生成一般步驟為：編譯->匯編->鏈接->載入

1. 編譯：對源代碼進(jìn)行編譯，成為匯編源代碼蜗字，此時(shí)仍然用符號(hào)來指代函數(shù)
2. 匯編：匯編成二進(jìn)制代碼打肝，用具體地址來代替符號(hào)了，但是有一些函數(shù)還沒有找到（此函數(shù)在別的程序文件中）
3. 鏈接：加入函數(shù)庫挪捕，找到庫函數(shù)的地址粗梭，把多個(gè)小程序組裝成一個(gè)可執(zhí)行文件
4. 載入：程序加載時(shí)進(jìn)行，視程序?qū)嶋H位置改變符號(hào)地址

鏈接分為兩種方式：

• 靜態(tài)鏈接：在程序執(zhí)行之前完成所有的組裝工作级零，生成一個(gè)可執(zhí)行的目標(biāo)文件（EXE文件）断医。
• 動(dòng)態(tài)鏈接：在程序已經(jīng)為了執(zhí)行被裝入內(nèi)存之后完成鏈接工作，并且在內(nèi)存中一般只保留該編譯單元的一份拷貝奏纪。

延伸知識(shí)：靜態(tài)鏈接庫與動(dòng)態(tài)鏈接庫都是共享代碼的方式鉴嗤，如果采用靜態(tài)鏈接庫，lib文件(靜態(tài)鏈接的函數(shù)庫)中的指令都被直接包含在最終生成的EXE文件中了序调。但是若使用DLL文件（動(dòng)態(tài)鏈接的函數(shù)庫）醉锅，該DLL不必被包含在最終的EXE文件中，EXE文件執(zhí)行時(shí)可以“動(dòng)態(tài)”地引用和卸載這個(gè)與EXE獨(dú)立的DLL文件发绢。

• 參考動(dòng)態(tài)鏈接和靜態(tài)鏈接的區(qū)別

邏輯地址生成過程

地址安全檢查

• 程序邏輯地址空間的范圍硬耍，基址與界限
• CPU檢查邏輯地址是否合理

CPU 生成的地址通常稱為邏輯地址，而內(nèi)存單元看到的地址（即加載到內(nèi)存地址寄存器的地址）通常稱為物理地址边酒。
參考邏輯地址空間和物理地址空間

總結(jié)一下经柴，物理地址生成過程如下圖所示：

物理地址生成過程

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

連續(xù)分配是指為一個(gè)用戶程序分配連續(xù)的內(nèi)存空間。連續(xù)分配有單一連續(xù)存儲(chǔ)管理和分區(qū)式儲(chǔ)管理兩種方式甚纲。

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

內(nèi)存被分為兩個(gè)區(qū)域：系統(tǒng)區(qū)和用戶區(qū)口锭。應(yīng)用程序裝入到用戶區(qū)，可使用用戶區(qū)全部空間介杆。其特點(diǎn)是鹃操，最簡單，適用于單用戶春哨、單任務(wù)的操作系統(tǒng)荆隘。

分區(qū)式內(nèi)存分配

內(nèi)存碎片

• 定義：內(nèi)存的空閑空間不能被利用
• 外部碎片：在分配單元間的未使用內(nèi)存
• 內(nèi)部碎片：在分配單元內(nèi)的未使用內(nèi)存

固定分區(qū)

• 特點(diǎn)：把內(nèi)存劃分為若干個(gè)固定大小的連續(xù)分區(qū)，分區(qū)大小可以相等也可以不等
• 優(yōu)點(diǎn)：易于實(shí)現(xiàn)赴背，開銷小
• 缺點(diǎn)：分區(qū)總數(shù)固定椰拒，限制了并發(fā)執(zhí)行的程序數(shù)目晶渠；內(nèi)部碎片造成浪費(fèi)

動(dòng)態(tài)分區(qū)

• 特點(diǎn)：分區(qū)大小最初并未聲明上沐，它在進(jìn)程加載時(shí)聲明首昔。分區(qū)大小根據(jù)進(jìn)程的需要而變化，以避免內(nèi)部碎片坟募。
• 優(yōu)點(diǎn)：

1. 沒有內(nèi)部碎片
2. 進(jìn)程大小無限制
3. 多程序的程度是動(dòng)態(tài)的缆毁，可以同時(shí)將更多的進(jìn)程加載到內(nèi)存中

• 缺點(diǎn)：

1. 存在外部碎片
2. 復(fù)雜的內(nèi)存分配番川，動(dòng)態(tài)分區(qū)中，分配和釋放非常復(fù)雜脊框，分配和取消分配的操作非常頻繁颁督，因?yàn)槊看畏峙浣o新進(jìn)程時(shí)分區(qū)大小都會(huì)發(fā)生變化，操作系統(tǒng)必須跟蹤所有的分區(qū)

• 分配策略

1. 首次適配：找到第一個(gè)可用空閑塊(空閑塊空間大于應(yīng)用程序所需大小)[優(yōu)勢：簡單浇雹，易產(chǎn)生更大空閑塊][缺點(diǎn)：易產(chǎn)生外碎片]

按地址排序的空閑塊列表
分配需要尋找一個(gè)合適的分區(qū)
重分需要檢查相鄰空閑分區(qū)是否可以合并

2. 最優(yōu)適配：按分區(qū)在內(nèi)存的先后次序從頭查找沉御，找到其大小與要求相差最小的空閑分區(qū)進(jìn)行分配 [優(yōu)勢：避免分割大空間][缺點(diǎn)：外部碎片，重分配慢昭灵，易產(chǎn)生微小碎片]

按尺寸排序的空閑塊列表
分配需要尋找一個(gè)合適的分區(qū)
重分需要檢查相鄰空閑分區(qū)是否可以合并

3. 最差適配：按分區(qū)在內(nèi)存的先后次序從頭查找吠裆，找到最大的空閑分區(qū)進(jìn)行分配 [優(yōu)勢：中等尺寸分配效果最好][缺點(diǎn)：重分配慢，大分區(qū)可能無法被分配]

按地址排序的空閑塊列表
分配很快
重分需要檢查相鄰空閑分區(qū)是否可以合并

壓縮式與交換式碎片整理

• 壓縮式：

1. 重置程序合并孔洞虎锚，壓縮后硫痰，所有的空閑分區(qū)都是連續(xù)的，所有已被使用的分區(qū)也都集中在一起
2. 要求所有程序是動(dòng)態(tài)可重置的
3. 開銷大窜护，系統(tǒng)的效率會(huì)降低

• 交換式：

1. 情形描述：運(yùn)行程序需要更多的內(nèi)存
2. 搶占等待的程序的內(nèi)存，回收它們的內(nèi)存非春，將其數(shù)據(jù)存放到硬盤上

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

在前面的幾種存儲(chǔ)管理方法中柱徙，為進(jìn)程分配的空間是連續(xù)的，使用的地址都是物理地址奇昙。如果允許將一個(gè)進(jìn)程分散到許多不連續(xù)的空間护侮，就可以避免內(nèi)存緊縮，減少碎片储耐。

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

1. 分配給一個(gè)程序的物理內(nèi)存是連續(xù)的
2. 內(nèi)存利用率低
3. 有外羊初、內(nèi)碎片問題

• 非連續(xù)內(nèi)存非配優(yōu)點(diǎn)：

1. 一個(gè)程序的物理內(nèi)存是非連續(xù)的
2. 更好的內(nèi)存利用和管理
3. 允許共享代碼和數(shù)據(jù)(共享庫等...)
4. 支持動(dòng)態(tài)加載和動(dòng)態(tài)鏈接

• 非連續(xù)內(nèi)存非配缺點(diǎn)：如何建立虛擬地址和物理地址之間的關(guān)系？

1. 軟件：開銷大
2. 硬件：分段/分頁

分段式存儲(chǔ)管理

• 進(jìn)程的段地址空間由多個(gè)段組成：代碼段什湘；數(shù)據(jù)段长赞；堆；棧闽撤；命令行數(shù)據(jù)段
• 目標(biāo)：更好的分離和共享

image.png

• 分段的概念：

1. 段表示訪問方式和存儲(chǔ)數(shù)據(jù)等屬性相同的一段地址空間
2. 上圖可以看出段對應(yīng)一個(gè)連續(xù)的內(nèi)存“塊”
3. 若干個(gè)段組成進(jìn)程邏輯地址空間

• 段訪問機(jī)制：

1. 邏輯地址由二元組(s得哆，addr)表示
2. s：段號(hào)；addr：段內(nèi)偏移
3. 實(shí)現(xiàn)方案：段寄存器+地址寄存器方案哟旗；單地址實(shí)現(xiàn)方案
4. 硬件實(shí)現(xiàn)機(jī)制：操作系統(tǒng)需要設(shè)置段表

段訪問硬件實(shí)現(xiàn)機(jī)制

• 首先從邏輯地址中得到段號(hào)和偏移量
• 在段表中查找段號(hào)贩据，得到段基址和段長度范圍
• 由MMU來判斷偏移量是否合法（偏移量是否大于段長度）
• 得到物理地址栋操，在物理內(nèi)存中查找相應(yīng)內(nèi)容

分頁式存儲(chǔ)管理

• 基本原理：將程序的邏輯地址空間劃分為固定大小的頁(page)，而物理內(nèi)存劃分為同樣大小的幀(page frame)饱亮。程序加載時(shí)矾芙，可將任意一頁放入內(nèi)存中任意一個(gè)幀，這些幀不必連續(xù)近上，從而實(shí)現(xiàn)了離散內(nèi)存分配剔宪。再建立邏輯地址到物理地址映射關(guān)系。[頁表/MMU(內(nèi)存管理單元)/TLB(快表)]

劃分物理內(nèi)存至固定大小的幀(Frame)戈锻，大小是2的冪歼跟；劃分邏輯地址空間至相同大小的頁(Page)，大小是2的冪

幀（物理地址）

• 物理內(nèi)存被分割為大小相等的幀
• 一個(gè)內(nèi)存物理地址是一個(gè)二元數(shù)組(f, o)

f：幀號(hào)(F位格遭，共有2^F個(gè)幀)
o：幀內(nèi)偏移(S位哈街，每幀有2^S個(gè)字節(jié))
物理地址 = [2^Sxf + o]

幀

物理地址計(jì)算例子

頁（邏輯地址）

• 一個(gè)程序的邏輯地址空間被劃分為大小相等的頁

頁內(nèi)偏移的大小 = 幀內(nèi)偏移的大小; 頁號(hào)大小 ≠ 幀號(hào)大小

• 一個(gè)邏輯地址是一個(gè)二元數(shù)組(p, o)

p：頁號(hào)(P位，共有2^P個(gè)幀)
o：頁內(nèi)偏移(S位拒迅，每頁有2^S個(gè)字節(jié))
邏輯地址 = [2^Sxp + o]

頁尋址機(jī)制

頁尋址機(jī)制.jpg

• 首先從邏輯地址中得到頁號(hào)和頁內(nèi)偏移
• 在頁表中由頁號(hào)查找?guī)?hào)骚秦，頁表保存了邏輯地址->物理地址的映射關(guān)系
• 由幀號(hào)和幀內(nèi)偏移(頁內(nèi)偏移)得到物理地址，在物理內(nèi)存中查找相應(yīng)內(nèi)容

• 本質(zhì)是頁映射到幀的過程
• 頁表由操作系統(tǒng)初始化時(shí)建立
• 頁是連續(xù)的虛擬內(nèi)存
• 幀是非連續(xù)的物理內(nèi)存
• 不是所有的頁都有對應(yīng)的幀ｈ滴ⅰＷ鞴俊！

頁表

• 頁表保存了邏輯地址（頁號(hào)）——物理地址（幀號(hào)）之間的映射關(guān)系
• 本質(zhì)是個(gè)大數(shù)組
• 邏輯地址頁號(hào)+PTBR（頁表基址寄存器）得到頁號(hào)
• 頁表項(xiàng)標(biāo)志：

1. 修改位（dirty bit）：對應(yīng)的頁面中的內(nèi)容是否被修改了
2. 存在位（resident bit）：邏輯頁面是否存在與之對應(yīng)的物理幀前硫，有些邏輯頁沒有對應(yīng)的物理幀
3. 引用位（clock/reference bit）：在過去一段時(shí)間內(nèi)是否訪問過頁中的某一個(gè)存儲(chǔ)單元

頁表結(jié)構(gòu)

• 地址轉(zhuǎn)換實(shí)例：

地址轉(zhuǎn)換實(shí)例

• 分頁機(jī)制性能問題：

1. 時(shí)間性能問題：訪問一個(gè)內(nèi)存單元需要兩次內(nèi)存訪問(一次用于獲取頁表項(xiàng)胞得，一次用于訪問數(shù)據(jù))
2. 空間性能問題：頁表可能非常大
3. 解決方法(緩存，間接訪問方式)

快表（TLB）

• 功能：用來解決分頁機(jī)制時(shí)間性能問題
• 目標(biāo)：緩存近期訪問的頁表項(xiàng)
• 實(shí)現(xiàn)：TLB使用關(guān)聯(lián)存儲(chǔ)器實(shí)現(xiàn)屹电，具備快速訪問性能

關(guān)聯(lián)存儲(chǔ)器：有一組key阶剑，可以并行地查找所有表項(xiàng)，得到匹配項(xiàng)

• 參考計(jì)算機(jī)關(guān)聯(lián)內(nèi)存

• 特點(diǎn)：快表位于CPU中危号，所以它的速度快牧愁、成本高、功耗大

• 如果TLB命中外莲，物理頁號(hào)可以很快被獲取
• 如果TLB未命中猪半，對應(yīng)的表項(xiàng)被更新到TLB中

快表

多級頁表

• 快表從速度上解決問題，但空間上還存在缺點(diǎn)
• 多級頁表：解決分頁機(jī)制空間性能問題
• 實(shí)現(xiàn)：把頁號(hào)分為k個(gè)部分偷线，建立頁表“樹”
• 優(yōu)點(diǎn)：可以有效減少每級頁表的長度磨确，但是如果所有的頁表項(xiàng)都存在，則多級頁表并沒有減少存儲(chǔ)量淋昭，不過大部分進(jìn)程并不會(huì)用到所有的邏輯地址空間

在x86架構(gòu)中俐填，CR3寄存器用于存儲(chǔ)PTBR（頁表基址）

多級頁表

反向頁表

• 定義：用來解決頁表占用的空間的一種方案。
• 普通頁表問題：

1. 大地址空間問題翔忽，對于大地址空間（64-bits）系統(tǒng)英融，多級頁表變得繁瑣盏檐；比如：5級頁表
2. 不讓頁表與邏輯地址空間的大小相對應(yīng)，讓頁表與物理地址空間的大小相對應(yīng)驶悟，邏輯（虛擬）地址空間增長速度快于物理地址空間

• 基于頁寄存器的方案：

基于頁寄存器方案

1. 頁寄存器思路：不讓頁表與邏輯地址空間的大小相對應(yīng)胡野，讓頁表與物理地址空間的大小相對應(yīng)，以幀號(hào)為索引去尋找頁號(hào)痕鳍，這樣反向頁表大小最大就為物理地址的容量
2. 頁寄存器（Page Registers）：每個(gè)幀與一個(gè)頁寄存器（Page Register）關(guān)聯(lián)硫豆，寄存器內(nèi)容包括：

• 使用位（Residence bit）：此幀是否被進(jìn)程占用
• 占用頁號(hào)（Occupier）：對應(yīng)的頁號(hào)p
• 保護(hù)位（Protection bits）：約定這一頁的訪問方式，可讀 or 可寫

3. 頁寄存器方案資源消耗舉例：

頁寄存器方案舉例

4. 頁寄存器方案優(yōu)點(diǎn)

• 頁表大小相對于物理內(nèi)存而言很小
• 頁表大小與邏輯地址空間大小無關(guān)

5. 頁寄存器方案缺點(diǎn)

• 頁表信息對調(diào)后笼呆，需要根據(jù)幀號(hào)可找頁號(hào)
• 在頁寄存器中搜索邏輯地址中的頁號(hào)

• 基于關(guān)聯(lián)內(nèi)存的方案：

基于關(guān)聯(lián)內(nèi)存方案

1. 如果幀數(shù)較少熊响， 頁寄存器可以被放置在關(guān)聯(lián)內(nèi)存中
2. 在關(guān)聯(lián)內(nèi)存中查找邏輯頁號(hào)

• 成功： 幀號(hào)被提取
• 失敗： 頁錯(cuò)誤異常(pagefault)

3. 限制因素：

• 大量的關(guān)聯(lián)內(nèi)存非常昂貴
• 到難以在單個(gè)時(shí)鐘周期內(nèi)完成
• 耗電

• 基于hash查找的方案

基于hash方案

1. 在反向頁表中通過哈希算法查找對應(yīng)頁表項(xiàng)中的幀號(hào)
2. 查找過程：

• 從邏輯地址中得到頁號(hào)
• 根據(jù)頁號(hào)和PID計(jì)算出Hash值
• 在反向頁表中查找對應(yīng)的頁表項(xiàng)，核對頁號(hào)是否一致诗赌，從中找出相應(yīng)的物理幀號(hào)

虛擬內(nèi)存

簡單介紹

• 虛擬內(nèi)存是一種存儲(chǔ)方案汗茄，為用戶提供了一個(gè)擁有非常大的主內(nèi)存的幻覺
• 用戶可以加載比可用主存更大的進(jìn)程，用磁盤空間來擴(kuò)展物理內(nèi)存
• 操作系統(tǒng)不是在主內(nèi)存中加載一個(gè)大進(jìn)程铭若，而是在主內(nèi)存中加載多個(gè)進(jìn)程的不同部分

虛擬內(nèi)存

• 思考一個(gè)問題：在計(jì)算機(jī)系統(tǒng)中洪碳， 尤其是在多道程序運(yùn)行的環(huán)境下，可能會(huì)出現(xiàn)內(nèi)存不夠用的情況叼屠， 怎么辦瞳腌？

• 如果是程序太大， 超過了內(nèi)存的容量镜雨， 可以采用手動(dòng)的覆蓋(overlay)技術(shù)嫂侍， 只把需要的指令和數(shù)據(jù)保存在內(nèi)存當(dāng)中：
• 如果是程序太多， 超過了內(nèi)存的容量荚坞， 可以采用自動(dòng)的交換(swapping)技術(shù)吵冒， 把暫時(shí)不能執(zhí)行的程序送到外存中：
• 如果想要在有限容量的內(nèi)存中， 以更小的頁粒度為單位裝入更多更大的程序西剥， 可以采用自動(dòng)的虛擬存儲(chǔ)技術(shù)。

覆蓋技術(shù)

• 目標(biāo)：用較小的內(nèi)存運(yùn)行較大的程序亿汞，與分區(qū)存儲(chǔ)管理配合使用
• 原理：把程序按照自身邏輯結(jié)構(gòu)劃分為若干個(gè)功能上相對獨(dú)立的程序模塊瞭空，不會(huì)同時(shí)執(zhí)行的模塊共享同一塊內(nèi)存區(qū)域，按時(shí)間先后運(yùn)行

1. 必要部分（常用功能）的代碼和數(shù)據(jù)常駐內(nèi)存疗我；
2. 可選部分（不常用功能）在其他程序模塊中實(shí)現(xiàn)咆畏，平時(shí)存放在外存中，在需要用到時(shí)才裝入內(nèi)存吴裤；
3. 不存在調(diào)用關(guān)系的模塊不必同時(shí)裝入到內(nèi)存旧找，從而可以相互覆蓋，即這些模塊共用一個(gè)分區(qū)麦牺。

覆蓋技術(shù)舉例

• 缺點(diǎn)：

1. 由程序員來把一個(gè)大的程序劃分為若干個(gè)小的能模塊钮蛛；并確定各個(gè)模塊之間的覆蓋關(guān)系鞭缭，增加了程序復(fù)雜度，費(fèi)時(shí)費(fèi)力魏颓；
2. 覆蓋模塊從外存裝入內(nèi)存岭辣， 實(shí)際上是以時(shí)間延長換取空間。

交換技術(shù)

• 目標(biāo)：多道程序在內(nèi)存中甸饱，讓正在運(yùn)行或需要運(yùn)行的程序獲取更多的內(nèi)存資源
• 原理：將暫時(shí)不能運(yùn)行的程序送到外存沦童，操作系統(tǒng)將一個(gè)進(jìn)程的整個(gè)地址空間的內(nèi)容保存到外存，將外存的某個(gè)進(jìn)程的地址空間讀入到內(nèi)存中

交換技術(shù)

• 幾個(gè)問題：

1. 交換時(shí)機(jī)的確定（何時(shí)發(fā)生交換叹话？只有當(dāng)內(nèi)存空間不夠時(shí)交換）偷遗；
2. 交換區(qū)的大小（必須足夠大以存放所有用戶進(jìn)程的所有內(nèi)存映像的拷貝；必須能對這些內(nèi)存映像直接存韧蘸）氏豌；
3. 程序換入時(shí)的重定位（換出后再換入的內(nèi)存位置一定要在原來的位置上嗎？最好采用動(dòng)態(tài)地址映射的方式）辅柴。

• 覆蓋與交換的比較：

1. 覆蓋只能發(fā)生在那些相互之間沒有調(diào)用關(guān)系的程序模塊之間箩溃，因此程序員必須給出程序內(nèi)的各個(gè)模塊之間的邏輯覆蓋結(jié)構(gòu)。
2. 交換技術(shù)是以在內(nèi)存中的程序大小為單位來進(jìn)行的碌嘀， 它不需要程序員給出各個(gè)模塊之間的邏輯覆蓋結(jié)構(gòu);
3. 交換發(fā)生在內(nèi)存中程序與管理程序或操作系統(tǒng)之間涣旨， 而覆蓋則發(fā)生在運(yùn)行程序的內(nèi)部。

• 缺點(diǎn)：增加了處理器的負(fù)擔(dān)

虛存技術(shù)

• 目標(biāo)：像覆蓋技術(shù)那樣股冗，但由操作系統(tǒng)自動(dòng)來完成霹陡，無需增加程序員負(fù)擔(dān)；像交換技術(shù)那樣止状，但只對進(jìn)程的部分內(nèi)容進(jìn)行交換烹棉；綜合了兩者的優(yōu)點(diǎn)。

image

• 程序局部性原理：指程序在執(zhí)行過程中的一個(gè)較短時(shí)期怯疤， 所執(zhí)行的指令地址和指令的操作數(shù)地址浆洗， 分別局限于一定區(qū)域。局部性通常有兩種形式：時(shí)間局部性和空間局部性集峦。

1. 時(shí)間局部性：一條指令的一次執(zhí)行和下次執(zhí)行伏社， 一個(gè)數(shù)據(jù)的一次訪問和下次訪問都集中在一個(gè)較短時(shí)期內(nèi)；
2. 空間局部性：當(dāng)前指令和鄰近的幾條指令塔淤， 當(dāng)前訪問的數(shù)據(jù)和鄰近的幾個(gè)數(shù)據(jù)都集中在一個(gè)較小區(qū)域內(nèi)摘昌。

• 基本概念：可以在頁式或段式內(nèi)存管理的基礎(chǔ)上實(shí)現(xiàn)

1. 在裝入程序時(shí)，不必將其全部裝入內(nèi)存中高蜂，只需裝入部分執(zhí)行的頁或段聪黎；
2. 程序執(zhí)行過程中，如果需執(zhí)行的指令或訪問的數(shù)據(jù)尚未在內(nèi)存中（稱為缺頁或缺段）备恤，則由處理器通知操作系統(tǒng)將相應(yīng)頁面或段調(diào)入到內(nèi)存中稿饰，再繼續(xù)執(zhí)行程序锦秒；
3. 操作系統(tǒng)將內(nèi)存中暫時(shí)不使用的頁面或段調(diào)出保存在外存中，從而騰出更多空閑空間湘纵。

• 基本特征：

1. 大的用戶空間：虛擬地址可以遠(yuǎn)遠(yuǎn)大于物理地址脂崔，32位系統(tǒng)虛擬地址理論上可以訪問4GB
2. 部分交換：與交換技術(shù)相比，虛擬存儲(chǔ)的調(diào)入調(diào)出是對部分虛擬地址空間進(jìn)行的
3. 不連續(xù)性：物理內(nèi)存分配的不連續(xù)性梧喷，虛擬地址空間使用的不連續(xù)性

虛擬頁式內(nèi)存管理

虛擬頁式內(nèi)存管理

• 基本思想：在頁式存儲(chǔ)管理的基礎(chǔ)上砌左，增加請求調(diào)頁和頁面置換功能
• 基本思路：

1. 當(dāng)一個(gè)用戶程序要調(diào)入內(nèi)存運(yùn)行時(shí)，不是將該程序的所有頁面都裝入內(nèi)存铺敌，而是只裝入部分的頁面汇歹，就可啟動(dòng)程序運(yùn)行；
2. 在運(yùn)行的過程中偿凭，如果發(fā)現(xiàn)要運(yùn)行的程序或要訪問數(shù)據(jù)不在內(nèi)存产弹，則向系統(tǒng)發(fā)出缺頁中斷請求，系統(tǒng)在處理這個(gè)中斷時(shí)弯囊，將外存中相應(yīng)的頁面調(diào)入內(nèi)存痰哨，使得該程序能繼續(xù)運(yùn)行。

• 頁表表項(xiàng)：

頁表表項(xiàng)

1. 頁號(hào)：虛擬地址空間中的頁號(hào)
2. 訪問位：如果該頁面被訪問過（ 包括讀操作或?qū)懖僮鳎┴抑觯瑒t設(shè)置此位斤斧。用于頁面換算法。
3. 修改位：表示此頁在內(nèi)存中是否被修改過霎烙。當(dāng)系統(tǒng)回收該物理頁面時(shí)粱甫，根據(jù)此位來決定是否把它的內(nèi)容寫回外存智绸；0 表示頁面在內(nèi)存時(shí)數(shù)據(jù)未被修改深滚，1 表示被修改過占卧。
4. 保護(hù)位：表示允許對該頁做何種類型的訪問，如只讀尝蠕、可讀寫烘豌、可執(zhí)行等.
5. 駐留位：表示該頁是在內(nèi)存還是在外存。1 表示在內(nèi)存中看彼，0 表示不在內(nèi)存中扇谣，為 0 時(shí)會(huì)發(fā)生“缺頁”中斷信號(hào)，請求系統(tǒng)處理
6. 幀號(hào)：物理地址空間的幀號(hào)

• 缺頁中斷

缺頁中斷

后備存儲(chǔ)：

后備存儲(chǔ)

頁面置換算法

• 功能：當(dāng)缺頁中斷發(fā)生時(shí)闲昭，需要調(diào)入新的頁面而內(nèi)存已滿，則選取物理內(nèi)存中相關(guān)頁面進(jìn)行置換
• 目標(biāo)：盡可能減少頁面的換進(jìn)換出次數(shù)（即缺頁中斷的次數(shù)）
• 頁面鎖定：用于描述必須常駐內(nèi)存的操作系統(tǒng)的關(guān)鍵部分或時(shí)間關(guān)鍵的應(yīng)用進(jìn)程靡挥，在頁表中添加鎖定標(biāo)志位序矩。

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

• 設(shè)計(jì)思想：置換以后不再需要的或最遠(yuǎn)的將來才會(huì)用到的頁面。
• 實(shí)現(xiàn)：這種算法要基于程序的走向和未來實(shí)現(xiàn)跋破，實(shí)際操作系統(tǒng)中無法實(shí)現(xiàn)簸淀，更多的是作為一種標(biāo)準(zhǔn)來衡量其他算法的性能瓶蝴。

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

• 設(shè)計(jì)思想：選擇在內(nèi)存中駐留時(shí)間最長的頁并置換它
• 實(shí)現(xiàn)：系統(tǒng)維護(hù)著一個(gè)鏈表，記錄了所有位于內(nèi)存當(dāng)中的邏輯頁面租幕。從鏈表的排列順序來看舷手，鏈?zhǔn)醉撁娴鸟v留時(shí)間最長， 鏈尾頁面的駐留時(shí)間最短劲绪。當(dāng)發(fā)生一個(gè)缺頁中斷時(shí)男窟， 把鏈?zhǔn)醉撁嫣蕴鼍郑?并把新的頁面添加到鏈表的未尾。
• 性能：性能較差贾富，調(diào)出的頁面可能是經(jīng)常要訪問的頁面歉眷，并且有Belady現(xiàn)象，很少單獨(dú)使用

最近最少使用算法（LRU）

• 設(shè)計(jì)思想：置換最久未被使用的頁
• 實(shí)現(xiàn)：需要記錄各個(gè)頁面使用時(shí)間先后順序颤枪，兩種方案汗捡，鏈表實(shí)現(xiàn)（首節(jié)點(diǎn)是最近使用），或堆棧實(shí)現(xiàn)（棧頂是最近使用）

鏈表實(shí)現(xiàn)：系統(tǒng)維護(hù)一個(gè)頁面鏈表畏纲， 最近剛剛使用過的頁面作為首結(jié)點(diǎn)扇住， 最久未使用的頁面作為尾結(jié)點(diǎn)。每一次訪問內(nèi)存時(shí)盗胀， 找到相應(yīng)的頁面． 把它從鏈表中摘下來艘蹋， 再移動(dòng)到鏈表之首。每次缺頁中斷發(fā)生時(shí)读整， 淘汰鏈表末尾的頁面簿训。

堆棧實(shí)現(xiàn)：設(shè)置一個(gè)活動(dòng)頁面棧． 當(dāng)訪問某頁肘， 將此頁號(hào)壓入棧頂米间， 然后强品， 考察棧內(nèi)是否有與此頁面相同頁號(hào)， 若有則抽出屈糊。當(dāng)需要淘汰一個(gè)頁面時(shí)的榛，總是選擇棧底的頁面， 它就是最久未使用的逻锐。

• 性能：最佳頁面置換算法的近似

時(shí)鐘算法（CLOCK）

• 設(shè)計(jì)思想：

1. 需要用到頁表項(xiàng)當(dāng)中的訪問位夫晌，當(dāng)一個(gè)頁面被裝入內(nèi)存時(shí)，把該位初始化為0昧诱。然后如果這個(gè)頁面被訪問（讀/寫）晓淀，把該位置為1
2. 把各個(gè)頁面組織成環(huán)形鏈表（類似鐘表面），把指針指向最老頁面（最先進(jìn)來）
3. 當(dāng)發(fā)生缺頁中斷時(shí)盏档，考察指針是否指向最老頁面凶掰，若它的訪問位為0，則立即淘汰；若訪問位為1懦窘，則把該位置0前翎，然后指針指向下一個(gè)，直到找到淘汰頁面畅涂，然后把指針移動(dòng)到它的下一格港华。

• 性能：LRU的近似，F(xiàn)IFO的改進(jìn)算法

第二次機(jī)會(huì)算法（SCR）

• 設(shè)計(jì)思想：修改CLOCK算法午衰，同時(shí)使用臟位和訪問位來指導(dǎo)置換立宜，使它允許臟頁再第一次時(shí)鐘頭掃描中保存下來

第二次機(jī)會(huì)算法

最不常用算法（LFU）

• 設(shè)計(jì)思想：當(dāng)一個(gè)缺頁中斷發(fā)生時(shí)，選擇訪問次數(shù)最少的那個(gè)頁面淘汰
• 實(shí)現(xiàn)方法：對每個(gè)頁面設(shè)置一個(gè)訪問計(jì)數(shù)器苇经，每當(dāng)一個(gè)頁面被訪問時(shí)赘理，該頁的訪問計(jì)數(shù)器加1。在發(fā)生缺頁中斷時(shí)扇单， 淘汰計(jì)數(shù)值最小的那個(gè)頁面商模。

進(jìn)程及線程

進(jìn)程基本概念

進(jìn)程定義

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

進(jìn)程示意圖

進(jìn)程組成

• 程序的代碼；
• 程序處理的數(shù)據(jù)蜘澜；
• 程序計(jì)數(shù)器中的值施流，指示下一條將運(yùn)行的指今；
• 一組通用寄存器的當(dāng)前值鄙信，堆瞪醋、棧；
• 一組系統(tǒng)資源（如打開的文件）装诡。

總之银受，進(jìn)程包含正在運(yùn)行的一個(gè)程序的所有狀態(tài)信息

進(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)行；并發(fā)運(yùn)行
• 獨(dú)立性：頁表保證進(jìn)程獨(dú)立豆挽，不同進(jìn)程不同頁表箩帚，不同進(jìn)程不同地址空間
• 制約性：因訪問相同數(shù)據(jù)/資源或進(jìn)程間同步而產(chǎn)生制約

進(jìn)程管理

進(jìn)程控制結(jié)構(gòu)（PCB）

• 進(jìn)程控制塊：描述進(jìn)程的數(shù)據(jù)結(jié)構(gòu)，操作系統(tǒng)為每個(gè)進(jìn)程都維護(hù)一個(gè)PCB，用來保存與該進(jìn)程有關(guān)信息吸重，PCB是進(jìn)程存在的唯一標(biāo)識(shí)嚎幸。
• PCB與進(jìn)程關(guān)系：

1. 進(jìn)程的創(chuàng)建：為該進(jìn)程生成一個(gè)PCB；
2. 進(jìn)程的終止：回收它的PCB寄猩；
3. 進(jìn)程的組織管理：通過對PCB的組織管理來實(shí)現(xiàn)嫉晶。

• 包含信息：

pcb進(jìn)程標(biāo)識(shí)和狀態(tài)信息

• pcb組織方式：

1. 鏈表：同一狀態(tài)的進(jìn)程其PCB成一鏈表，多個(gè)狀態(tài)對應(yīng)多個(gè)不同的鏈表

各狀態(tài)的進(jìn)程形成不同的鏈表：就緒鏈表田篇，阻塞鏈表

2. 索引表：同一狀態(tài)的進(jìn)程歸入一個(gè)index表(由index指向PCB)替废，多個(gè)狀態(tài)對應(yīng)多個(gè)不同的index表

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

pcb組織方式

進(jìn)程生命周期

• 進(jìn)程生命周期：創(chuàng)建泊柬，就緒椎镣，運(yùn)行，等待（進(jìn)程只能自己阻塞自己）兽赁，喚醒（進(jìn)程只能被其他進(jìn)程或操作系統(tǒng)喚醒）状答，結(jié)束

進(jìn)程等待（阻塞）情況：

1. 請求并等待系統(tǒng)服務(wù)冷守，無法馬上完成
2. 啟動(dòng)某種操作，無法馬上完成
3. 需要的數(shù)據(jù)沒有到達(dá)

• 進(jìn)程狀態(tài)變化模型：
  進(jìn)程的三種基本狀態(tài)：就緒狀態(tài)惊科，等待狀態(tài)拍摇，阻塞狀態(tài)。

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

• 進(jìn)程掛起：此時(shí)進(jìn)程沒有占用內(nèi)存空間馆截，進(jìn)程映像在磁盤中授翻，不同于進(jìn)程阻塞

進(jìn)程掛起

1. 阻塞掛起狀態(tài)：進(jìn)程在外存并等待某事件出現(xiàn)
2. 就緒掛起狀態(tài)：進(jìn)程在外存，但只要進(jìn)入內(nèi)存便可運(yùn)行
3. 掛起狀態(tài)變化：

掛起狀態(tài)變化

OS進(jìn)程調(diào)度

OS進(jìn)程調(diào)度

• 狀態(tài)隊(duì)列：

1. 由操作系統(tǒng)來維護(hù)一組隊(duì)列孙咪，用來表示系統(tǒng)當(dāng)中所有進(jìn)程的當(dāng)前狀態(tài)；
2. 不同的狀態(tài)分別用不同的隊(duì)列來表示（就緒隊(duì)列巡语、各種類型的阻塞隊(duì)列）翎蹈；
3. 每個(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ì)中脫離出來荤堪，加入到另外一個(gè)隊(duì)列。

狀態(tài)隊(duì)列

線程基本概念

線程定義

• 進(jìn)程當(dāng)中的一條執(zhí)行流程
• 進(jìn)程與線程的理解：

1. 從資源組合角度：進(jìn)程是把一組相關(guān)的資源組合起來枢赔，構(gòu)成了一個(gè)資源平臺(tái)澄阳，包括地址空間、打開的文件等各種資源
2. 從運(yùn)行的角度：線程是代碼在這個(gè)資源平臺(tái)上的一條執(zhí)行流程
3. 線程 = 進(jìn)程 - 共享資源

進(jìn)程中的線程

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

1. 一個(gè)進(jìn)程中可以同時(shí)存在多個(gè)線程踏拜；
2. 各個(gè)線程之間可以并發(fā)地執(zhí)行碎赢；
3. 各個(gè)線程之間可以共享地址空間和文件等資源。

• 線程缺點(diǎn)：

1. 一個(gè)線程崩潰速梗， 會(huì)導(dǎo)致其所屬進(jìn)程的所有線程崩潰肮塞。

線程與進(jìn)程區(qū)別

1. 進(jìn)程是資源分配單位，線程是CPU調(diào)度單位姻锁；
2. 進(jìn)程擁有一個(gè)完整的資源平臺(tái)枕赵，而線程只獨(dú)享必不可少的資源，如寄存器和棧位隶；
3. 線程同樣具有就緒拷窜、阻塞和執(zhí)行三種基本狀態(tài)，同樣具有狀態(tài)之間的轉(zhuǎn)換關(guān)系涧黄；
4. 線程能減少并發(fā)執(zhí)行的間和空間開銷：

• 線程的創(chuàng)建時(shí)間比進(jìn)程短篮昧；
• 線程的終止時(shí)間比進(jìn)程短；
• 同一進(jìn)程內(nèi)的線程切換時(shí)間比進(jìn)程短弓熏；
• 由于同一進(jìn)程的各線程間只享內(nèi)存和文件資源恋谭，可直接進(jìn)行不通過內(nèi)核的通信。

進(jìn)程線程區(qū)別

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

用戶線程

• 基本概念：
  
  用戶線程

1. 在用戶空間實(shí)現(xiàn)挽鞠，它不依賴于操作系統(tǒng)的內(nèi)核疚颊，由一組用戶級的線程庫函數(shù)來完成線程的管理狈孔，包括進(jìn)程的創(chuàng)建、終止材义、同步和調(diào)度等
2. 由于用戶線程的維護(hù)由相應(yīng)進(jìn)程來完成（通過線程庫函數(shù)）均抽，不需要操作系統(tǒng)內(nèi)核了解用戶線程的存在，可用于不支持線程技術(shù)的多進(jìn)程操作系統(tǒng)其掂；
3. 每個(gè)進(jìn)程都需要它自己私有的線程控制塊(TCB)列表油挥，用來跟蹤記錄它的各個(gè)線程的狀態(tài)信息（PC、棧指針款熬、寄存器）深寥，TCB 由線程庫函數(shù)來維護(hù)；
4. 用戶線程的切換也是由線程庫函來完成贤牛，無需用戶態(tài)/核心態(tài)切換惋鹅，所以速度特別快；
5. 允許每個(gè)進(jìn)程擁有自定義的線程調(diào)度算法殉簸。

• 用戶線程缺點(diǎn)：

用戶線程缺點(diǎn)

內(nèi)核線程

內(nèi)核線程示意圖

1. 在操作系統(tǒng)的內(nèi)核當(dāng)中實(shí)現(xiàn)的一種線程機(jī)制闰集，由操作系統(tǒng)的內(nèi)核來完成線程的創(chuàng)建、終止和管理般卑。
2. 內(nèi)核來維護(hù)進(jìn)程和線程的上下文信息(PCB 和TCB)武鲁；
3. 線程的創(chuàng)建、終止和切換都是通過系統(tǒng)調(diào)用/內(nèi)核函數(shù)的方式來進(jìn)行蝠检，由內(nèi)核來完成沐鼠，因此系統(tǒng)開銷較大；
4. 在一個(gè)進(jìn)程當(dāng)中蝇率，如果某個(gè)內(nèi)核線程發(fā)起系統(tǒng)調(diào)用而被阻塞迟杂，并不會(huì)影響其他內(nèi)核線程的運(yùn)行；
5. 時(shí)間片分配給線程本慕，多線程的進(jìn)程獲得更多CPU時(shí)間排拷。

輕量級線程

內(nèi)核支持的用戶線程，一個(gè)進(jìn)程可以有多個(gè)輕量級進(jìn)程锅尘，每個(gè)輕量級進(jìn)程由一個(gè)單獨(dú)的內(nèi)核線程來支持监氢。

輕量級進(jìn)程

上下文切換

• 定義：停止當(dāng)前運(yùn)行進(jìn)程，并且調(diào)度其他進(jìn)程

1. 在切換之前藤违，存儲(chǔ)許多部分的進(jìn)程上下文
2. 能夠在之后恢復(fù)他們
3. 必須快速浪腐，因?yàn)樯舷挛那袚Q十分頻繁

• 需要存儲(chǔ)信息：

1. 寄存器(PC、SP...)顿乒，CPU狀態(tài)议街，...

上下文切換

進(jìn)程控制

• 創(chuàng)建：系統(tǒng)調(diào)用fork()父進(jìn)程創(chuàng)建子進(jìn)程

1. 調(diào)用fork創(chuàng)建一個(gè)繼承的子進(jìn)程
2. 復(fù)制父進(jìn)程的所有變量和內(nèi)存
3. 復(fù)制父程的所有CPU寄存器（有一個(gè)寄存器例外）

fork

• 加載：系統(tǒng)調(diào)用exec()加載程序取代當(dāng)前運(yùn)行進(jìn)程

exec示意圖

• 等待：系統(tǒng)調(diào)用wait()父進(jìn)程用來等待子進(jìn)程結(jié)束

1. 一個(gè)子進(jìn)程向父進(jìn)程返回一個(gè)值，所以父進(jìn)程須接受這個(gè)值并處理
2. 它使父進(jìn)程去睡眠來等待子進(jìn)程的結(jié)果
3. 當(dāng)一個(gè)子進(jìn)程調(diào)用exit()的時(shí)候璧榄，操作系統(tǒng)解鎖父進(jìn)程特漩，并且通過exit()傳遞得到的返回值作為wait()調(diào)用的一個(gè)結(jié)果吧雹，如果這里沒有子進(jìn)程存活，wait()立引返回
4. 當(dāng)然涂身，如果這里有父進(jìn)程的僵尸等待雄卷，wait()立即返回其中一個(gè)值（并解除僵尸狀態(tài)）
5. 父進(jìn)程可以幫助子進(jìn)程清除所有資源

• 結(jié)束：進(jìn)程結(jié)束后調(diào)用exit()

1. 將這程序“ 結(jié)果” 作為一個(gè)參數(shù)
2. 關(guān)閉所有打開的文件，連接等等
3. 釋放內(nèi)存
4. 釋放大部分支持進(jìn)程的操作系統(tǒng)結(jié)構(gòu)
5. 檢查父進(jìn)程是否存活：

• 如果是活蛤售，它保留的結(jié)果直到父進(jìn)程需要它丁鹉；進(jìn)程沒有真正死亡，但是它進(jìn)入了僵尸狀態(tài)
• 如果是死悴能，它釋放所有數(shù)據(jù)結(jié)構(gòu)揣钦，這個(gè)進(jìn)程死亡

6. 清理所有等待的僵尸進(jìn)程

CPU調(diào)度

調(diào)度背景

• 定義：從就緒隊(duì)列中挑選一個(gè)進(jìn)程/線程作為CPU將要運(yùn)行的下一個(gè)進(jìn)程/線程
• 內(nèi)核運(yùn)行調(diào)度程序的條件：

1. 一個(gè)進(jìn)程從運(yùn)行狀態(tài)切換到等待狀態(tài)
2. 一個(gè)進(jìn)程被終結(jié)

• 調(diào)度策略

1. 非搶占式：調(diào)度程序必須等待事件結(jié)束
2. 搶占式：

• 調(diào)度程序在中斷被響應(yīng)后執(zhí)行；
• 當(dāng)前進(jìn)程從運(yùn)行切換到就緒漠酿，或一個(gè)進(jìn)程從等待切換到就緒拂盯；
• 當(dāng)前運(yùn)行的進(jìn)程可以被換出。

調(diào)度原則

• 一些基本概念：

基本概念

• CPU調(diào)度目標(biāo)：

CPU調(diào)度目標(biāo)

調(diào)度算法

先來先服務(wù)（FCFS）

1. 根據(jù)就緒隊(duì)列的到達(dá)時(shí)間來排序记靡，此時(shí)就緒隊(duì)列是一個(gè)FIFO隊(duì)列，先到先服務(wù)团驱，算法簡單
2. 缺點(diǎn)：

• CPU進(jìn)程區(qū)間變化很大時(shí)朽们，平均等待時(shí)間會(huì)變化很大朦蕴；
• 可能導(dǎo)致I/O和CPU之間的重疊處理，CPU密集型進(jìn)程會(huì)導(dǎo)致I/O設(shè)備閑置時(shí)，I/O密集型進(jìn)程也在等待鸿染。

最短作業(yè)優(yōu)先調(diào)度（SJF）

1. 按照預(yù)測的完成時(shí)間來將任務(wù)入隊(duì)
2. 可以是可搶占的或不可搶占的
3. 可能導(dǎo)致饑餓

• 連續(xù)的短任務(wù)流會(huì)使長任務(wù)饑餓
• 短任務(wù)可用時(shí)的任何長任務(wù)的CPU時(shí)間都會(huì)增加平均等待時(shí)間

最高響應(yīng)比優(yōu)先（HRRN）

1. 在SPN調(diào)度的基礎(chǔ)上改進(jìn)
2. 不可搶占
3. 關(guān)注進(jìn)程等待了多長時(shí)間
4. 防止無限期推遲

響應(yīng)比：R = (w + s)/s ，選擇R值最高的進(jìn)程

• w: waiting time 等待時(shí)間
• s：service time 執(zhí)行時(shí)間

輪轉(zhuǎn)法調(diào)度（RR）

1. 選擇固定時(shí)間片亥宿，時(shí)間片到了則切換進(jìn)程運(yùn)行
2. 時(shí)間片太大：

• 等待時(shí)間過長
• 極限情況退化成FCFS

3. 時(shí)間片太小：

• 反應(yīng)迅速姥敛，但是切換上下文頻繁
• 吞吐量由于大量的上下文切換開銷受到影響

4. 目標(biāo)：

• 選擇一個(gè)合適的時(shí)間片
• 經(jīng)驗(yàn)規(guī)則： 維持上下文切換開銷處于1%以內(nèi)

多級反饋隊(duì)列調(diào)度

1. 實(shí)現(xiàn)思路：

• 就緒隊(duì)列被劃分成獨(dú)立的隊(duì)列：如前臺(tái)（交互），后臺(tái)（批處理）
• 每個(gè)隊(duì)列擁有自己的調(diào)度策略：如前臺(tái)一RR兵罢，后臺(tái)——FCFS
• 調(diào)度必須在隊(duì)列間進(jìn)行：固定優(yōu)先級或時(shí)間片輪轉(zhuǎn)

2. 具體方案舉例：

• 一個(gè)進(jìn)程可以在不同的隊(duì)列中移動(dòng)
• 例如：有n 級優(yōu)先級（優(yōu)先級調(diào)度在所有級別中献烦，RR在每個(gè)級別中），時(shí)間片大小隨優(yōu)先級級別增加而增加卖词，如果任務(wù)在當(dāng)前的時(shí)間片中沒有完成巩那， 則降到下一個(gè)優(yōu)先級

多級調(diào)度

公平共享調(diào)度（FFS）

1. 一些用戶組比其他用戶組更重要
2. 保證不重要的組無法壟斷資源
3. 未使用的資源按照每個(gè)組所分配的資源的比例來分配
4. 沒有達(dá)到資源用率目標(biāo)的組獲得更高的優(yōu)先級

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

實(shí)時(shí)系統(tǒng)

• 定義：正確性依賴于其時(shí)間和功能兩方面的一種操作系統(tǒng)
• 性能指標(biāo)：

1. 時(shí)間約束的及時(shí)性
2. 速度和平均性能相對不重要

• 主要特性：

1. 時(shí)間約束的可預(yù)測性

• 分類：強(qiáng)實(shí)時(shí)系統(tǒng)；軟實(shí)時(shí)系統(tǒng)

多處理器調(diào)度

1. 多處理器的CPU調(diào)度更加復(fù)雜

• 多個(gè)相同的單處理器組成一個(gè)另處理器
• 優(yōu)點(diǎn)：負(fù)載共享

2. 多對稱處理器(SMP)

• 每個(gè)處理器運(yùn)行自己的調(diào)度程序
• 需要在調(diào)度程序中同步

多處理器

優(yōu)先級反轉(zhuǎn)

1. 可以發(fā)生在任何基于優(yōu)先級的可搶占的調(diào)度機(jī)制中
2. 當(dāng)系統(tǒng)內(nèi)的環(huán)境強(qiáng)制使高優(yōu)先級任務(wù)等待低優(yōu)先級任務(wù)時(shí)發(fā)生

進(jìn)程/線程同步

背景知識(shí)

• 獨(dú)立線程：不和其他線程共享資源和狀態(tài)此蜈，確定性即横，可重現(xiàn)性
• 合作線程：在多個(gè)線程中共享狀態(tài)，不確定性裆赵，不可重現(xiàn)性

1. 資源共享
2. 加速：CPU計(jì)算和I/O操作可以重疊
3. 模塊化：將大程序拆分為小程序东囚，使系統(tǒng)易于擴(kuò)展

• 競態(tài)條件：結(jié)果依賴于并發(fā)執(zhí)行或者事件的順序/時(shí)間（讓指令不被打斷可避免競態(tài)條件）；當(dāng)兩個(gè)或多個(gè)線程競爭同一資源時(shí)战授，如果對資源的訪問順序敏感页藻，即存在競態(tài)條件桨嫁。

• 原子操作：指一次不存在任何中斷或失敗的執(zhí)行

1. 該執(zhí)行成功結(jié)束
2. 或者根不沒有執(zhí)行
3. 并且不應(yīng)該發(fā)現(xiàn)任何部分執(zhí)行的狀態(tài)
4. i++，java new一個(gè)對象都不是原子操作

臨界區(qū)

• 定義：導(dǎo)致競態(tài)條件發(fā)生的代碼區(qū)稱作臨界區(qū)
• 互斥：當(dāng)一個(gè)進(jìn)程處于臨界區(qū)并訪問共享資源時(shí)惕橙，沒有其他講程會(huì)處于臨界區(qū)并且訪問任何相同的共享資源
• 有限等待：如果一個(gè)線程i處于入囗區(qū)瞧甩，那么在i的請求被接受之前，其他線程進(jìn)入臨界區(qū)的時(shí)間是有限制的
• 無忙等待（可選）：如果一個(gè)進(jìn)程在等待進(jìn)入臨界區(qū)弥鹦，那么在它可以進(jìn)入之前會(huì)被掛起

實(shí)現(xiàn)方案

• 基于硬件中斷

1. 沒有中斷肚逸，沒有上下文切換，因此沒有并發(fā)

• 硬件將中斷處理延遲到中斷被啟用之后
• 大多數(shù)現(xiàn)代計(jì)算機(jī)結(jié)構(gòu)體系都提供指令來完成

2. 進(jìn)入臨界區(qū)：禁止中斷
3. 離開臨界區(qū)：開啟中斷
4. 缺點(diǎn)：

• 一旦中斷停用彬坏，線程無法停止朦促，整個(gè)系統(tǒng)停止，其他線程可能處于饑餓狀態(tài)
• 如果臨界區(qū)任意長栓始，無法限制響應(yīng)中斷所需時(shí)間
• 要小心使用

基于軟件解決方案

• 線程可能共享一些共有的變量來同步他們的行為
• 使用一些標(biāo)志位來解決線程間同步
• 滿足進(jìn)程Pi和Pj之間互斥的經(jīng)典的基于軟件的解決方法（1981年）：

• 使用兩個(gè)共享數(shù)據(jù)項(xiàng)：

基于軟件互斥方法

• 一些著名算法：

• Dekker算法（1965）：第一個(gè)針對雙線程例子的正確解決萬案
• Bakery算法（Lamport 1979）：針對n線程的臨界區(qū)問題解決方案

• 缺點(diǎn)：

1. 復(fù)雜：需要兩個(gè)進(jìn)程間的共享數(shù)據(jù)頃
2. 需要忙等待：浪費(fèi)CPU 時(shí)間
3. 沒有硬件保證的情況下無真正的軟件解決方案：原子操作都需要硬件支持

更高級的抽象

1. 硬件提供了一些原語（中斷禁用务冕，原子操作指令），大多數(shù)現(xiàn)代體系結(jié)構(gòu)都這樣
2. 操作系統(tǒng)提供更高級的編程抽象來簡化并行編程（鎖幻赚，信號(hào)量）禀忆，從硬件原語中構(gòu)建

鎖

1. 定義：鎖是一個(gè)抽象的數(shù)據(jù)結(jié)構(gòu)

• 一個(gè)二進(jìn)制狀態(tài)（鎖定/ 解鎖），兩種方法
• Lock::Acquire() 一 鎖被釋放前一直等待落恼，然后得到鎖
• Lock::Release() 一 釋放鎖箩退，喚醒任何等待的進(jìn)程

2. 應(yīng)用：編寫臨界區(qū)

• lock_next_pid->Acquire();
• new_pid = next_pid++;
• lock_next_pid->Release();

3. 原子操作指令

• 大多現(xiàn)代體系結(jié)構(gòu)都提供特殊原子操作指令，通過特殊的內(nèi)存訪問電路佳谦，針對單處理器和多處理器
• Test-And-Set：從內(nèi)存中讀值戴涝，測試該值是否為1并返回真或假，內(nèi)存值設(shè)置為1
• 交換：交換兩個(gè)內(nèi)存中值

原子操作指令

• 用TestAndSet實(shí)現(xiàn)Lock:

TestAndSet

忙等和無忙等待對比：

忙等和無忙等待對比

• 用Exchange實(shí)現(xiàn)Lock：

Exchange

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

• 適用于單處理器或者共享主存的多處理器中任意數(shù)量的進(jìn)程
• 筒單并且容易證明
• 可以用于支持多臨界區(qū)

缺點(diǎn)：

• 忙等待消耗處理器時(shí)間
• 當(dāng)進(jìn)程離開臨界區(qū)并且多個(gè)進(jìn)程在等待的時(shí)候能導(dǎo)致饑哦

信號(hào)量

1. 定義：一個(gè)抽象數(shù)據(jù)類型钻蔑，在早期的操作系統(tǒng)是主要的同步原語

• 一個(gè)整型（sem）啥刻，兩個(gè)原子操作
• P()：sem減1，如果sem<0咪笑，等待可帽，否則繼續(xù)
• V()：sem加1，如果sem<=0窗怒，喚醒一個(gè)等待的P

2. 一些基本概念：

• 信號(hào)量是整數(shù)蘑拯，信號(hào)量是被保護(hù)的變量，初始化完成后兜粘，唯一改變信號(hào)量的是P和V操作
• P能夠阻塞申窘，V不會(huì)阻塞
• 兩種類型：二進(jìn)制信號(hào)量，一般/計(jì)數(shù)信號(hào)量

3. 用途：可以用在互斥孔轴，同步

信號(hào)量實(shí)現(xiàn)互斥

信號(hào)量實(shí)現(xiàn)同步

4. 信號(hào)量實(shí)現(xiàn)：

• 使用硬件原語：禁用中斷剃法，原子指令（TestAndSet）

信號(hào)量的實(shí)現(xiàn)

5. 信號(hào)量實(shí)現(xiàn)生產(chǎn)者消費(fèi)者模型：

• 生產(chǎn)者消費(fèi)者模型：一個(gè)線程等待另一個(gè)線程處理事情，比如生產(chǎn)東西或消費(fèi)東西

生產(chǎn)者消費(fèi)者模型

• 正確性要求：

• 在任何一個(gè)時(shí)間只能有一個(gè)線程操作緩沖區(qū)（互斥）
• 當(dāng)緩沖區(qū)為空路鹰，消費(fèi)者必須等待生產(chǎn)者（調(diào)度/同步約束）
• 當(dāng)緩存區(qū)滿贷洲，生產(chǎn)者必須等待消費(fèi)者（調(diào)度/同步約束）

信號(hào)量實(shí)現(xiàn)生產(chǎn)者消費(fèi)者模型

6. 缺點(diǎn)：

• 讀/開發(fā)代碼十分困難收厨，程序員必須精通信號(hào)量
• 容易出錯(cuò)：忘記釋放信號(hào)量
• 不能處理死鎖問題

管程

1. 目的：分離互斥和條件同步的關(guān)注，封裝了同步操作优构，對進(jìn)程隱蔽了同步細(xì)節(jié)诵叁，簡化了同步功能的調(diào)用
2. 定義：包含若干共享變量及其說明和所有訪問這些共享變量的函數(shù)所組成的軟件模塊

管程

3. 實(shí)現(xiàn)：

• Condition Variable

• Wait() operation：釋放鎖，睡眠钦椭，重新獲得鎖返回后
• Signal() operation：喚醒等待者（或者所有等待者）

管程實(shí)現(xiàn)

4. 管程實(shí)現(xiàn)生產(chǎn)者消費(fèi)者模型：

image

IPC

• 概述：兩個(gè)進(jìn)程或線程間傳送數(shù)據(jù)或信號(hào)的一些技術(shù)或方法

1. 如果P和Q想通信拧额，需要在他們之間建立通信鏈路（共享內(nèi)存，硬件總線彪腔，邏輯屬性等）侥锦，通過send/receive交換消息
2. 存在直接通信，間接通信兩種方式

進(jìn)程間通信

3. 直接通信：

進(jìn)程必須正確的命名對方：

• send(P, message)：發(fā)送信息到進(jìn)程P
• receive(Q德挣，message)：從進(jìn)程Q接受消息

通啟鏈路的屬性:

• 自動(dòng)建立鏈路
• 每一條鏈路恰好對應(yīng)一對通信進(jìn)程
• 每對進(jìn)程之間只有一個(gè)鏈接存在
• 鏈接可以是單向的恭垦，但通常為雙向的

4. 間接通信：

定向從消息隊(duì)列接收消息:

• 每個(gè)消息隊(duì)列都有一個(gè)唯一的ID
• 只有它們共享了一個(gè)消息隊(duì)列，進(jìn)程才能夠通信

通信鏈路的屬性:

• 只有進(jìn)程共享一個(gè)相同的消息隊(duì)列格嗅，才建立鏈路
• 鏈接可以與許多進(jìn)程相關(guān)聯(lián)
• 每對進(jìn)程可以共享多個(gè)通信鏈路
• 鏈接可以是單向或雙向

5. 消息傳遞分為阻塞和非阻塞兩種

• 阻塞：同步
• 非阻塞：異步

6. 通信鏈路緩沖：

• 0容量：發(fā)送方必須等待接收方
• 有限容量(n)：如果隊(duì)列滿番挺，發(fā)送方必須等待
• 無限容量：發(fā)送方不需要等待

信號(hào)(Signal)

1. 定義：軟件中斷通知事件處理（如SIGFPE, SIGKILL...）
2. 接收到信號(hào)時(shí)會(huì)發(fā)生什么：

• Catch: 指定信號(hào)處理函數(shù)被調(diào)用
• Ignore: 依靠操作系統(tǒng)默認(rèn)操作（如: Abort, memory dump, suspend or resume process）
• Mask：閉塞信號(hào)因此不會(huì)傳送（可能是暫時(shí)的）

3. 不足：

• 不能傳輸要交換的任何數(shù)據(jù)

信號(hào)實(shí)現(xiàn)機(jī)制

管道（Pipe）

1. 定義：是一系列將標(biāo)準(zhǔn)輸入輸出鏈接起來的進(jìn)程，其中每一個(gè)進(jìn)程的輸出被直接作為下一個(gè)進(jìn)程的輸入
2. 原理：每創(chuàng)建一個(gè)管道屯掖，就有兩個(gè)文件描述符建芙，一個(gè)是負(fù)責(zé)讀管道的，一個(gè)是負(fù)責(zé)寫管道的懂扼。所以，使用管道通信時(shí)右蒲，可以看作是兩個(gè)文件描述符加一段內(nèi)核空間中的內(nèi)存阀湿。
3. 管道只能協(xié)調(diào)有親緣關(guān)系的進(jìn)程間通信，所謂親緣瑰妄，比如父子進(jìn)程陷嘴、兄弟進(jìn)程。當(dāng)某進(jìn)程創(chuàng)建一個(gè)管道后间坐，它就擁有了這個(gè)管道的兩個(gè)文件描述符灾挨，它的子進(jìn)程會(huì)繼承這兩個(gè)文件描述符，所以子進(jìn)程也能讀寫這個(gè)管道竹宋。
4. 示意圖：

管道示意圖

消息隊(duì)列

1. 定義：一個(gè)消息的鏈表劳澄，是一系列保存在內(nèi)核中消息的列表，由消息隊(duì)列標(biāo)識(shí)符標(biāo)識(shí)
2. 優(yōu)點(diǎn)：

• 傳遞消息多蜈七，克服了信號(hào)傳遞信息少缺點(diǎn)
• 克服了管道只能承載無格式字節(jié)流以及緩沖區(qū)大小受限的缺點(diǎn)

消息隊(duì)列

共享內(nèi)存

1. 定義：映射一段能被其他進(jìn)程所訪問的內(nèi)存秒拔，這段共享內(nèi)存由一個(gè)進(jìn)程創(chuàng)建，但多個(gè)進(jìn)程都可以訪問
2. 優(yōu)點(diǎn)：

• 通信速度最快的 IPC 方式飒硅，針對其他進(jìn)程間通信方式運(yùn)行效率低而專門設(shè)計(jì)的
• 進(jìn)程可以直接讀寫內(nèi)存砂缩，而不需要任何數(shù)據(jù)的拷貝

3. 缺點(diǎn)：必須同步數(shù)據(jù)訪問
4. 實(shí)現(xiàn)方式：內(nèi)存映射和共享內(nèi)存機(jī)制兩種方式

• 內(nèi)存映射：==內(nèi)存映射 memory map機(jī)制使進(jìn)程之間通過映射同一個(gè)普通文件實(shí)現(xiàn)共享內(nèi)存作谚，通過mmap()系統(tǒng)調(diào)用實(shí)現(xiàn)。普通文件被映射到進(jìn)程地址空間后庵芭，進(jìn)程可以像訪問普通內(nèi)存一樣對文件進(jìn)行訪問妹懒，不必再調(diào)用read/write等文件操作函數(shù)== ；
• 共享內(nèi)存機(jī)制：==把所有的共享數(shù)據(jù)放在共享內(nèi)存區(qū)域（IPC shared memory region）双吆，任何想要訪問該數(shù)據(jù)的進(jìn)程都必須在本進(jìn)程的地址空間新增一塊內(nèi)存區(qū)域眨唬，用來映射存放共享數(shù)據(jù)的物理內(nèi)存頁面==。

5. 原理：

共享內(nèi)存示意圖

死鎖

1. 定義：一個(gè)進(jìn)程集合中的多個(gè)進(jìn)程因?yàn)楦偁庂Y源伊诵，而造成的互相等待現(xiàn)象
2. 死鎖原因：

• 因?yàn)?strong>系統(tǒng)資源不足单绑；
• 進(jìn)程運(yùn)行推進(jìn)的順序不合適；
• 資源分配不當(dāng)?shù)取?/li>

3. 死鎖的必要條件：

• 互斥條件（Mutual exclusion）：資源不能被共享曹宴，只能由一個(gè)進(jìn)程使用搂橙。
• 請求與保持條件（Hold and wait）：已經(jīng)得到資源的進(jìn)程可以再次申請新的資源。
• 非剝奪條件（No pre-emption）：已經(jīng)分配的資源不能從相應(yīng)的進(jìn)程中被強(qiáng)制地剝奪笛坦。
• 循環(huán)等待條件（Circular wait）：系統(tǒng)中若干進(jìn)程組成環(huán)路区转，該環(huán)路中每個(gè)進(jìn)程都在等待相鄰進(jìn)程正占用的資源。

4. 死鎖預(yù)防：保證系統(tǒng)不進(jìn)入死鎖狀態(tài)的一種策略版扩。基本思想是要求進(jìn)程申請資源時(shí)遵循某種協(xié)議废离，從而打破產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)，保證系統(tǒng)不會(huì)進(jìn)入死鎖狀態(tài)礁芦。

• 破壞互斥條件蜻韭。即允許進(jìn)程同時(shí)訪問某些資源。但是柿扣，有的資源是不允許被同時(shí)訪問的肖方，像打印機(jī)。
• 破壞不可剝奪條件未状。即允許進(jìn)程強(qiáng)行從占有者那里奪取某些資源俯画。
• 破壞請求與保持條件∷静荩可以實(shí)行資源預(yù)先分配策略艰垂。即進(jìn)程在運(yùn)行前一次性地向系統(tǒng)申請它所需要的全部資源埋虹。但是此方法有缺點(diǎn)：

a. 一個(gè)進(jìn)程在執(zhí)行之前不可能知道它所需要的全部資源拉宗。這是由于進(jìn)程在執(zhí)行時(shí)是動(dòng)態(tài)的谷遂，不可預(yù)測的

b. 資源利用率低。無論所分資源何時(shí)用到卖鲤，一個(gè)進(jìn)程只有在占有所需的全部資源后才能執(zhí)行

c. 降低了進(jìn)程的并發(fā)性肾扰。因?yàn)橘Y源有限，又加上存在浪費(fèi)蛋逾，能分配到所需全部資源的進(jìn)程個(gè)數(shù)就必然少了

• 破壞循環(huán)等待條件集晚，實(shí)行資源有序分配策略。把資源事先分類編號(hào)区匣，按號(hào)分配偷拔，使進(jìn)程在申請，占用資源時(shí)不會(huì)形成環(huán)路亏钩。此方法也有如下缺點(diǎn)：

a. 限制了進(jìn)程對資源的請求莲绰，同時(shí)給系統(tǒng)中所有資源合理編號(hào)也是件困難事，并增加了系統(tǒng)開銷

b. 為了遵循按編號(hào)申請的次序姑丑，暫不使用的資源也需要提前申請蛤签，從而增加了進(jìn)程對資源的占用時(shí)間

5. 死鎖避免：

• 安全序列：系統(tǒng)中的所有進(jìn)程能夠按照某一種次序分配資源，并且依次地運(yùn)行完畢栅哀，這種進(jìn)程序列{P1震肮，P2，...留拾，Pn}就是安全序列戳晌。如果存在這樣一個(gè)安全序列，則系統(tǒng)是安全的间驮；如果系統(tǒng)不存在這樣一個(gè)安全序列，則系統(tǒng)是不安全的马昨。

安全序列{P1竞帽，P2，...鸿捧，Pn}是這樣組成的：若對于每一個(gè)進(jìn)程Pi屹篓，它需要的附加資源可以被系統(tǒng)中當(dāng)前可用資源加上所有進(jìn)程Pj當(dāng)前占有資源之和所滿足（其中j<i），則{P1匙奴，P2堆巧，...，Pn}為一個(gè)安全序列，這時(shí)系統(tǒng)處于安全狀態(tài)谍肤，不會(huì)進(jìn)入死鎖狀態(tài)啦租。

• 銀行家算法：通過先試探分配給該進(jìn)程資源，然后通過安全性算法判斷分配后的系統(tǒng)是否處于安全狀態(tài)荒揣，若不安全則試探分配作廢篷角，讓該進(jìn)程繼續(xù)等待。

6. 死鎖的檢測與恢復(fù):

• 由于操作系統(tǒng)有并發(fā)系任，共享以及隨機(jī)性等特點(diǎn)恳蹲，通過預(yù)防和避免的手段達(dá)到排除死鎖的目的是很困難的。這需要較大的系統(tǒng)開銷俩滥，而且不能充分利用資源嘉蕾。為此，一種簡便的方法是系統(tǒng)為進(jìn)程分配資源時(shí)霜旧，不采取任何限制性措施错忱，但是提供了檢測和解脫死鎖的手段：能發(fā)現(xiàn)死鎖并從死鎖狀態(tài)中恢復(fù)出來
• 死鎖檢測與恢復(fù)是指系統(tǒng)設(shè)有專門的機(jī)構(gòu)，當(dāng)死鎖發(fā)生時(shí)颁糟，該機(jī)構(gòu)能夠檢測到死鎖發(fā)生的位置和原因航背，并能通過外力破壞死鎖發(fā)生的必要條件，從而使得并發(fā)進(jìn)程從死鎖狀態(tài)中恢復(fù)出來

a. 最常用的方法就是進(jìn)行系統(tǒng)的重新啟動(dòng)棱貌，不過這種方法代價(jià)很大

b. 撤消進(jìn)程玖媚，剝奪資源。終止參與死鎖的進(jìn)程婚脱，收回它們占有的資源今魔，從而解除死鎖

文件系統(tǒng)

基本概念

• 文件：文件系統(tǒng)中一個(gè)單元的相關(guān)數(shù)據(jù)在操作系統(tǒng)中的抽象，一個(gè)存儲(chǔ)記錄序列的數(shù)據(jù)結(jié)構(gòu)

• 文件屬性：名稱障贸、類型错森、位置、大小篮洁、保滬涩维、創(chuàng)建者、創(chuàng)建時(shí)間袁波、最近修改時(shí)間瓦阐、....
• 文件頭：在存儲(chǔ)元數(shù)據(jù)中保存了每個(gè)文件的信息，保存文件屬性篷牌，跟蹤哪一塊存儲(chǔ)塊屬于邏輯上文件結(jié)構(gòu)的哪個(gè)偏移睡蟋。

• 文件系統(tǒng)：一種用于持久性存儲(chǔ)的系統(tǒng)抽象
• 文件系統(tǒng)功能：

1. 分配文件磁盤空間（管理文件塊，管理空閑空間枷颊，分配算法）
2. 管理文件集合（定位文件及其內(nèi)容戳杀，命名该面，最常見：分層文件系統(tǒng)）
3. 提供的便利及特征（保護(hù)作用：分層來保證安全，可靠性信卡，持久性）

• 文件系統(tǒng)種類：

1. 磁盤文件系統(tǒng)：文件存儲(chǔ)在數(shù)據(jù)存儲(chǔ)設(shè)備上隔缀，如FAT、NTFS坐求、ext2/3
2. 數(shù)據(jù)庫文件系統(tǒng)：文件根據(jù)其特征是可被尋址的蚕泽，如WinFS
3. 日志文件系統(tǒng)：記錄文件系統(tǒng)的修改/事件
4. 分布式文件系統(tǒng)：如NFS、SMB桥嗤、AFS

文件描述符

• 定義：操作系統(tǒng)為每個(gè)進(jìn)程維護(hù)一個(gè)打開文件表须妻，一個(gè)打開文件描述符是這個(gè)表中的索引
• 元數(shù)據(jù)管理打開文件：

1. 文件指針：指向最近的一次讀寫位置，每個(gè)打開了這個(gè)文件的進(jìn)程都這個(gè)指計(jì)
2. 文件打開計(jì)數(shù)：記錄文件打開次數(shù)一當(dāng)最后一個(gè)進(jìn)程關(guān)閉了文件時(shí)泛领，允許將其從打開文件表中移除
3. 文件磁盤位置：緩存數(shù)據(jù)訪問信息
4. 訪問權(quán)限：每個(gè)程序訪問模式信息

• 在文件系統(tǒng)中的所有操作都是在整個(gè)塊空間上進(jìn)行的

• 塊是邏輯轉(zhuǎn)換單元荒吏，unix中塊大小是4KB
• 即使每次只訪問1字節(jié)數(shù)據(jù)，也會(huì)緩存目標(biāo)數(shù)據(jù)4096字節(jié)

文件目錄

• 定義：磁盤上相關(guān)文件的列表渊鞋，文件以目錄方式組織起來的
• 典型操作：文件創(chuàng)建绰更，搜索文件，文件刪除锡宋，重命名文件驼鹅，遍歷文件逸爵，文件列表
• 操作系統(tǒng)只允許內(nèi)核模式修改文件目錄：確保映射完整性
• 目錄中文件存儲(chǔ)方式：

1. 文件名的線性列表庄撮，包含了指向數(shù)據(jù)塊的指針

• 編程簡單
• 執(zhí)行耗時(shí)

2. Hash數(shù)據(jù)結(jié)構(gòu)的線性表

• 減少目錄搜索時(shí)間
• 碰撞篱竭，兩個(gè)文件名的hash值相同
• 固定大小

• 目錄解析過程，以/bin/ls為例：

解析目錄

• 掛載點(diǎn)：實(shí)際上就是linux中的磁盤文件系統(tǒng)的入口目錄役首，類似于windows中的用來訪問不同分區(qū)的C:尝丐、D:、E:等盤符

掛載點(diǎn)

虛擬文件系統(tǒng)

1. 文件系統(tǒng)分層結(jié)構(gòu)：

文件系統(tǒng)分層結(jié)構(gòu)

2. 目的：對所有不同文件系統(tǒng)的抽象
3. 功能：

• 提供相同的文件和文件系統(tǒng)接口
• 管理所有文件和文件系統(tǒng)關(guān)聯(lián)的數(shù)據(jù)結(jié)構(gòu)
• 高效查詢例程衡奥，遍歷文件系統(tǒng)
• 與特定文件系統(tǒng)模塊的交互

4. 文件系統(tǒng)數(shù)據(jù)：

• 卷控制塊（每個(gè)文件系統(tǒng)一個(gè)）：文件系統(tǒng)詳細(xì)信息爹袁，塊、塊人小矮固、空余塊失息、計(jì)數(shù)/指針等
• 文件控制塊（每個(gè)文件一個(gè)）：文件詳細(xì)信息，許可档址、擁有者盹兢、大小、數(shù)據(jù)庫位置
• 目錄節(jié)點(diǎn)（每個(gè)目錄一個(gè)）：將目錄項(xiàng)數(shù)據(jù)結(jié)構(gòu)及樹型布局編碼成樹型數(shù)據(jù)結(jié)構(gòu)辰晕，指向文件控制塊蛤迎、父節(jié)點(diǎn)确虱、項(xiàng)目列表等

文件系統(tǒng)數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)塊緩存

• 數(shù)據(jù)塊按需讀入內(nèi)存
• 數(shù)據(jù)塊使用后被緩存含友，寫操作可能被緩存和延遲寫入(假設(shè)數(shù)據(jù)將會(huì)被再次使用)

磁盤緩存

• 兩種緩沖方式：

1. 普通緩沖區(qū)緩存
2. 頁緩存：統(tǒng)一數(shù)據(jù)塊和內(nèi)存項(xiàng)

一個(gè)頁可以映射到一個(gè)本地文件中
數(shù)據(jù)塊被映射成頁
文件的讀/寫轉(zhuǎn)換成對內(nèi)存的操作
可能導(dǎo)致缺頁

頁緩存

打開文件數(shù)據(jù)結(jié)構(gòu)

• 打開文件描述符：

1. 每個(gè)被打開的文件一個(gè)
2. 文件狀態(tài)信息
3. 目錄頂、當(dāng)前文件指針、文件操作設(shè)置等

• 打開文件表

1. 一個(gè)進(jìn)程一個(gè)
2. 一個(gè)系統(tǒng)級的
3. 每個(gè)卷控制塊也會(huì)保存一個(gè)列表
4. 所以如果有文件被打開將不能被卸載

打開文件表

文件分配(數(shù)據(jù)塊)

• 大數(shù)文件都很小

1. 需要對小文件提供強(qiáng)力的支持
2. 塊空間不能太大

• 一些文件非常大

1. 必須支持大文件(64-bit 文件偏移）
2. 大文件訪問需要相當(dāng)高效

• 分配方式：

1. 連續(xù)分配

文件頭指定起始塊和長度窘问，優(yōu)勢：文件讀取表現(xiàn)好辆童，高效的順序和隨機(jī)訪問，缺點(diǎn)：碎片惠赫，文件增長問題（對文件擴(kuò)容麻煩）

連續(xù)分配

2. 鏈?zhǔn)椒峙?/strong>

文件以數(shù)據(jù)塊鏈表方式存儲(chǔ)把鉴，文件頭包含了第一塊和最后一塊的指針，優(yōu)點(diǎn)：創(chuàng)建儿咱，增大庭砍，縮小很容易，沒有碎片混埠；缺點(diǎn)：不可能真正的隨機(jī)訪問怠缸，可靠性差

鏈?zhǔn)椒峙?/div>

3. 索引分配

為每個(gè)文件創(chuàng)建索引數(shù)據(jù)塊，文件頭包含了數(shù)據(jù)索引塊钳宪，優(yōu)點(diǎn)：創(chuàng)建揭北，增大，縮小很容易吏颖，沒有碎片搔体，可隨機(jī)訪問；缺點(diǎn)：文件小時(shí)存儲(chǔ)索引冗余半醉，文件大時(shí)索引數(shù)據(jù)塊有容量限制(采用分級索引解決大文件問題疚俱，鏈?zhǔn)剿饕?多級索引)

索引分配

4. 多級索引

多級索引

• 多級索引存儲(chǔ)文件示意圖(對大小文件都適用):

多級索引

文件頭包含13個(gè)指針

• 10個(gè)指針指向數(shù)據(jù)塊；
• 第11個(gè)指針指向間接接據(jù)塊奉呛；
• 第12個(gè)指針指向二級間接接據(jù)塊计螺；
• 第13個(gè)指針指向三級間接接據(jù)塊。

• 優(yōu)勢/缺點(diǎn)

• 提高了文件大小限制閾值
• 動(dòng)態(tài)分配數(shù)據(jù)塊瞧壮，文件擴(kuò)展很容易
• 小文件開銷小
• 只為大文件分配間接數(shù)據(jù)塊登馒，大文件在訪問間接數(shù)據(jù)塊是需要大量的查詢

• 指標(biāo)：

1. 高效：存儲(chǔ)利用（外部碎片）
2. 表現(xiàn)：訪問速度

空閑空間列表

• 跟蹤在存儲(chǔ)中的所有未分配的數(shù)據(jù)塊
• 用位圖代表空閑數(shù)據(jù)塊列表：如果該塊為空，則該位為1咆槽，否則為0

1. 使用簡單陈轿，但位圖會(huì)是個(gè)大向量，160GB硬盤需要5M位圖數(shù)據(jù)量
2. 需要保證其一致性

• 鏈?zhǔn)搅斜?分組列表：

鏈?zhǔn)?分組列表

多磁盤管理-RAID

• 通常磁盤通過分區(qū)來最大限度減小尋道時(shí)間

1. 一個(gè)分區(qū)是一個(gè)柱面集合
2. 每個(gè)分區(qū)都是邏輯上獨(dú)立的磁盤

磁盤示意圖

• 分區(qū)：硬件磁盤的一種適合操作系統(tǒng)指定格式的劃分
• 卷：一個(gè)擁有一個(gè)文件系統(tǒng)實(shí)例的可訪問的存儲(chǔ)空間
• 使用多個(gè)并行磁盤來增加：吞吐量（通過并行）秦忿；可靠性和可用性（通過冗余）
• RAID技術(shù)：獨(dú)立磁盤的冗余陣列

1. 它是一種用于連接多個(gè)輔助存儲(chǔ)設(shè)備以提高性能麦射，數(shù)據(jù)冗余或兩者兼?zhèn)涞募夹g(shù)
2. RAID技術(shù)有7個(gè)級別的RAID方案。這些模式為：RAID 0灯谣，RAID 1潜秋，....，RAID 6

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

1. 在操作系統(tǒng)內(nèi)核：存儲(chǔ)/卷管理
2. RAID硬件控制器（I/O）

多磁盤

磁盤調(diào)度

• 一個(gè)進(jìn)程需要兩種類型的時(shí)間胎许，CPU時(shí)間和I/O時(shí)間峻呛；對于I/O罗售，它請求操作系統(tǒng)訪問磁盤
• 磁盤訪問時(shí)間 = 尋道時(shí)間 + 旋轉(zhuǎn)延遲 + 傳輸時(shí)間

1. 尋道時(shí)間：是將磁盤臂定位到滿足讀/寫請求的指定磁道所用的時(shí)間，尋道時(shí)間是性能上的區(qū)別本質(zhì)
2. 旋轉(zhuǎn)延遲：期望的扇區(qū)將自己倒換到可以訪問R / W磁頭的位置
3. 傳輸時(shí)間: 傳輸數(shù)據(jù)所需的時(shí)間

I/O訪問時(shí)間

• 調(diào)度目的：從I/O請求隊(duì)列中選擇一個(gè)磁盤請求钩述，并決定處理該請求的時(shí)間表寨躁，以優(yōu)化I/O訪問時(shí)間
• 調(diào)度算法：

1. FCFS調(diào)度算法（先來先服務(wù)）
2. SSTF算法(最短尋找時(shí)間優(yōu)先)
3. SCAN調(diào)度

磁臂在一個(gè)方向上移動(dòng)，滿足所有未完成的請求牙勘，直到磁臂達(dá)到該方向上最后的磁道

4. C-SCAN調(diào)度：

限制在一個(gè)方向上移動(dòng)职恳，磁臂在一個(gè)方向上移動(dòng)，滿足所有未完成的請求方面，直到磁臂達(dá)到該方向上最后的磁道

5. C-LOOK調(diào)度：

C-SCAN的改進(jìn)版放钦，達(dá)到該方向最后一個(gè)請求處立即停止

6. N-Step-Scan算法：

• 在SSTF、SCAN 及C-SCAN這幾種調(diào)度算法中恭金，都可能出現(xiàn)磁臂停留在某處不動(dòng)的情況最筒，例如進(jìn)程反復(fù)請求對某一磁道的I/O操作。我們把這一現(xiàn)象稱為“磁臂粘著”蔚叨。
• N-Step-Scan算法是將磁盤請求隊(duì)列分成若干個(gè)長度為N的子隊(duì)列床蜘，磁盤調(diào)度將按FCFS算法依次處理這些子隊(duì)列。而處理每一個(gè)隊(duì)列又是SCAN算法蔑水，對一個(gè)隊(duì)處理完后邢锯，再處理其他隊(duì)列。

6. FSCASN算法:

• 實(shí)質(zhì)上是N 步SCAN 算法的筒化搀别，只將磁盤請求隊(duì)列分成兩個(gè)子隊(duì)列丹擎。