《操作系統(tǒng)原理》PPT課件.ppt

《《操作系統(tǒng)原理》PPT課件.ppt》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《《操作系統(tǒng)原理》PPT課件.ppt（66頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1 l 操 作 系 統(tǒng) 概 述l 進(jìn) 程 管 理l 存 儲(chǔ) 管 理l 文 件 系 統(tǒng) 與 I/O 2操 作 系 統(tǒng) 給 計(jì) 算 機(jī) 一 個(gè) 靈 活 的 大 腦 、一 個(gè) 強(qiáng) 健 的 心 臟 和 突 出 的 個(gè) 性 3 4 孰 優(yōu) ？ 5 q (quoting Linus Torvalds): . message passing as the fundamental operation of the OS is just an exercise in computer science masturbation. It may feel good, but you dont actually ge

2、t anything DONE.q Monolithic： 內(nèi) 核 中 所 有 的 子 系 統(tǒng) 運(yùn) 行 在 相 同 的 特權(quán) 級(jí) (privileged mode） ， 擁 有 相 同 的 地 址 空 間 ， 通信 采 用 常 規(guī) C函 數(shù) 調(diào) 用 的 形 式 。 6 7 系 統(tǒng) 調(diào) 用 是 一 個(gè) 復(fù) 雜 的過(guò) 程系 統(tǒng) 調(diào) 用 往 往 通 過(guò) 軟 中斷 的 方 式 實(shí) 現(xiàn)系 統(tǒng) 調(diào) 用 在 為 應(yīng) 用 程 序提 供 操 作 系 統(tǒng) 服 務(wù) 的 同時(shí) ， 也 實(shí) 現(xiàn) 了 對(duì) 計(jì) 算 機(jī)資 源 和 應(yīng) 用 程 序 的 保 護(hù) 8 n Process - a program in executi

3、on text section, data section, stack, current activity n 進(jìn) 程 是 資 源 擁 有 的 基 本 單 位 (unit of resource ownership)n CPU、 存 儲(chǔ) 空 間 ， 及 其 他 資 源 （ I/O設(shè) 備 、 文 件 等 ） 進(jìn) 程 控 制 塊 （ PCB） 及 其 管 理 進(jìn) 程 的 狀 態(tài) ： running,ready,blocked,stopped,zombie 9 q Thread an execution path in a processq Thread the unit of dispatchi

4、ng 進(jìn) 程 中 的 線(xiàn) 程 共 享 進(jìn) 程 資 源 ， 但 擁 有 私 有 堆 棧 及 線(xiàn) 程 控 制塊 (TCB， 存 儲(chǔ) 寄 存 器 值 、 優(yōu) 先 級(jí) 及 其 他 線(xiàn) 程 狀 態(tài) 信 息 )q 核 心 級(jí) 線(xiàn) 程 （ KLT： kernel-level thread） 應(yīng) 用 程 序 通 過(guò) API調(diào) 用 核 心 線(xiàn) 程 管 理 例 程 (kernel thread facility)來(lái) 管 理 ： 需 要 進(jìn) 行 模 式 切 換 是 OS調(diào) 度 的 基 本 單 位 線(xiàn) 程 阻 塞 不 會(huì) 導(dǎo) 致 整 個(gè) 進(jìn) 程 的 阻 塞 在 多 處 理 器 環(huán) 境 下 ， 內(nèi) 核 可 使 線(xiàn) 程

5、在 不 同 的 處 理 器 上運(yùn) 行 E.g. windows thread 10 q 用 戶(hù) 級(jí) 線(xiàn) 程 （ ULT： user-level thread） 由 應(yīng) 用 程 序 自 己 通 過(guò) 線(xiàn) 程 庫(kù) (thread library)來(lái) 管理 ： 線(xiàn) 程 創(chuàng) 建 、 終 止 、 線(xiàn) 程 間 通 信 ， 線(xiàn) 程 調(diào) 度 與切 換 OS感 知 不 到 ULT的 存 在 線(xiàn) 程 阻 塞 會(huì) 導(dǎo) 致 整 個(gè) 進(jìn) 程 的 阻 塞 理 論 上 講 ， 在 任 何 OS下 都 可 以 實(shí) 現(xiàn) 無(wú) 法 利 用 多 處 理 器 11 12 #include #include int sum;void *r

6、unner(void *param);main(int argc, char *argv) pthread_t tid; pthread_attr_t attr; pthread_attr_init( /初 始 化 線(xiàn) 程 屬 性 為 缺 省 屬 性 pthread_create( /創(chuàng) 建 線(xiàn) 程 pthread_join(tid,NULL); /等 待 線(xiàn) 程 tid結(jié) 束 printf(“sum=%dn”,sum);void *runner(void *param) int upper=atoi(param); int i; sum = 0; if (upper 0) for ( i =

7、 1; i =upper; i+) sum +=i; pthread_exit(0); 13 三 、 并 發(fā) 控 制 ： 互 斥 與 同 步并 發(fā) （ Concurrent） 與 并 行 （ Parallel） q 臨 界 資 源 (critical resource) 一 次 只 能 由 一 個(gè) 進(jìn) 程 訪(fǎng) 問(wèn) 的 資 源q 臨 界 區(qū) (critical section) 訪(fǎng) 問(wèn) 臨 界 資 源 的 代 碼 段 稱(chēng) 為 臨 界 區(qū) （ CS） 14 q 互 斥 (mutual exclusion)在 一 個(gè) 時(shí) 刻 最 多 只 有 一 個(gè) 進(jìn) 程 在 臨 界 區(qū)q 同 步 (synchro

8、nization)協(xié) 調(diào) 需 要 訪(fǎng) 問(wèn) 臨 界 資 源 的 進(jìn) 程 ， 否 則 會(huì) 導(dǎo) 致 race condition（ 競(jìng) 爭(zhēng) 條 件 ）如 ： 兩 進(jìn) 程 p0,p1， 都 通 過(guò) 下 面 的 代 碼 訪(fǎng) 問(wèn) 一 個(gè) 共 享 的 存 儲(chǔ) 單元 :Shared variable: int total : = 0 ;p0,p1: int count;for (count=1; count =50; count+) total = total + 1 ; total可 能 的 結(jié) 果 ？最 大 值 ？ 最 小 值 ？注 意 total是 兩 個(gè) 進(jìn) 程 都 可 以 訪(fǎng) 問(wèn) 的 共 享 存 儲(chǔ)

9、 單 元 ， 不 同 于 一 般程 序 中 的 全 局 變 量 15 q 兩 個(gè) 前 提 ： 對(duì) 處 理 器 數(shù) 及 各 進(jìn) 程 的 相 對(duì) 運(yùn) 行 速 度 （ 不 會(huì) 是 零 速 度 ） 不 應(yīng) 該有 任 何 假 設(shè) 進(jìn) 程 在 臨 界 區(qū) 停 留 的 時(shí) 間 是 有 限 的q 三 個(gè) 必 須 ： 互 斥 (mutual exclusion) 有 空 讓 進(jìn) (progress)， 若 沒(méi) 有 進(jìn) 程 在 臨 界 區(qū) ， 則 應(yīng) 該 讓 申 請(qǐng) 進(jìn) 入臨 界 區(qū) 的 進(jìn) 程 中 的 一 個(gè) 立 即 進(jìn) 入 有 限 等 待 (bounded waiting)， 申 請(qǐng) 進(jìn) 入 臨 界 區(qū) 的

10、進(jìn) 程 不 會(huì) 無(wú) 止境 的 等 待 （ 即 不 會(huì) 有 饑 餓 現(xiàn) 象 ） 16 1.軟 件 方 法 （ 忙 等 待 ）q Shared variablesboolean flag2; /initially flag 0 = flag 1 = false.int turn; /initially turn=i;q Process Pido flagi := true;while (turn i) while (flag j ) ; turn := i ;flag i = false; while (1);q 此 算 法 正 確 嗎 ？ 17 Peterson算 法 ： 算 法 直 觀(guān) ， 只

11、 能 解 決 二 個(gè) 進(jìn) 程 同步 P0: do flag0:=true; /希 望 進(jìn) 入 turn := 1; /給 對(duì) 方 一 次 機(jī) 會(huì) while flag1 and turn = 1 donothing; /如 果 對(duì) 方 先 申 請(qǐng) 則 等 待 flag0:= false; while (1) 18 2. 利 用 硬 件 支 持 中 斷 屏 蔽 (interrupt disable) 代 價(jià) 大 ， 無(wú) 法 做 到 程 序 的 交 叉 執(zhí) 行 （ interleave) 多 處 理 環(huán) 境 下 無(wú) 法 實(shí) 現(xiàn) 特 殊 機(jī) 器 指 令Test and Set Instruction

12、Exchange Instruction 優(yōu) 點(diǎn) ： 適 合 多 處 理 器 環(huán) 境 、 簡(jiǎn) 單 缺 點(diǎn) ： 必 須 忙 等 待 (busy waiting)、 可 能 導(dǎo) 致 饑 餓 19 q OS提 供 的 裝 置 ， 用 于 進(jìn) 行 進(jìn) 程 /線(xiàn) 程 的 同 步 與 互 斥q 數(shù) 據(jù) 結(jié) 構(gòu) (s) count:integer;=0表 示 可 用 資 源 數(shù) ， 0， 其 絕 對(duì) 值 表 示 掛 起 進(jìn)程 數(shù) ， 初 始 化 非 負(fù) queue:list of process； 正 在 等 待 該 類(lèi) 資 源 的 進(jìn) 程q 進(jìn) 程 只 能 通 過(guò) OS提 供 的 wait和 signal

13、兩 個(gè) 操 作 原 語(yǔ) 訪(fǎng) 問(wèn) 信 號(hào) 量 Wait(s):等 待 資 源 s.count = s.count 1; if s.count 0 then begin place this process in s.queue; block this process; end; Signal(s):釋 放 資 源 s.count = s.count +1; if s.count =0 then begin remove a process P from s.queue; place process P on ready list; end; 20 信 號(hào) 量 full， 初 始 化 為 0,表

14、示 緩 沖 區(qū) 中 可 消 費(fèi) 的 資 源 數(shù) mutex， 初 始 化 為 1,用 于 對(duì) 緩 沖 區(qū) 的 互 斥 操 作 empty, 初 始 化 為 緩 沖 區(qū) 的 長(zhǎng) 度 N， 表 示 緩 沖 區(qū) 中 空 閑 單 元 數(shù)Producer: repeat produce; wait(empty);wait(mutex); append; signal(mutex) ;signal(full); foreverConsumer: repeat wait(full); wait(mutex); take; signal(mutex);signal(empty);consume forever

15、 21 例 ： 有 n個(gè) 進(jìn) 程 （ P1， P2， ， Pn） 向 容 量 為 M的 緩 沖 區(qū) 寫(xiě) 數(shù) 據(jù) ， 每 個(gè) 進(jìn) 程一 次 寫(xiě) 1個(gè) 數(shù) 據(jù) ， 當(dāng) 緩 沖 區(qū) 寫(xiě) 滿(mǎn) 時(shí) ， 另 一 個(gè) 讀 進(jìn) 程 Pr一 次 將 M個(gè) 數(shù) 據(jù) 全 部 讀 完， 如 此 反 復(fù) 。 請(qǐng) 用 信 號(hào) 量 解 決 這 些 進(jìn) 程 的 同 步 互 斥 問(wèn) 題 。答 ： 本 題 中 需 要 定 義 下 述 變 量 和 信 號(hào) 量 ：data_type bufferM; /* data_type對(duì) 應(yīng) 于 所 需 要 的 數(shù) 據(jù) 類(lèi) 型 ， 如 int、 float等 */ int in=0； /* 用

16、 來(lái) 指 示 下 一 個(gè) 可 存 放 數(shù) 據(jù) 的 緩 沖 區(qū) */semaphore empty=M; /* 對(duì) 應(yīng) 空 閑 的 緩 沖 區(qū) */semaphore full=0; /* 對(duì) 應(yīng) 緩 沖 區(qū) 中 的 數(shù) 據(jù) */semaphore mutex=1; /* 用 來(lái) 實(shí) 現(xiàn) Pi進(jìn) 程 對(duì) 變 量 in的 互 斥 訪(fǎng) 問(wèn) */進(jìn) 程 Pi可 描 述 為 ：Pi() while(1) wait(empty); wait(mutex); 向 緩 沖 區(qū) bufferin中 寫(xiě) 數(shù) 據(jù) ； in=(in+1)%M; signal(mutex); signal(full); 進(jìn) 程 Pr可

17、 描 述 為 ： Pr() int i; while(1) for(i=0;iM;i+) wait(full); wait(mutex); 取 出 緩 沖 buffer0到 bufferM-1中 的 數(shù) 據(jù) ； signal(mutex); for(i=0;iM;i+) signal(empty); 22 例 ： 有 一 個(gè) 倉(cāng) 庫(kù) ， 可 以 存 放 A和 B兩 種 產(chǎn) 品 ， 但 要 求 ：（ 1） 每 次 只 能 存 入 一 種 產(chǎn) 品 （ A或 B） ；（ 2） -NA產(chǎn) 品 數(shù) 量 -B產(chǎn) 品 數(shù) 量 M。其 中 ， N和 M是 正 整 數(shù) 。 試 用 信 號(hào) 量 來(lái) 同 步 產(chǎn) 品

18、 A與 產(chǎn) 品 B的 入 庫(kù) 過(guò) 程 。答 ： 本 題 中 ， 首 先 需 要 設(shè) 置 一 個(gè) 初 值 為 1的 互 斥 信 號(hào) 量 mutex， 以 保 證 每 次 只存 入 一 種 產(chǎn) 品 。 另 外 ， 為 了 保 證 “ -NA產(chǎn) 品 數(shù) 量 -B產(chǎn) 品 數(shù) 量 M”， 還 需 設(shè) 置 信號(hào) 量 SA， 表 示 倉(cāng) 庫(kù) 中 目 前 可 再 存 放 的 A產(chǎn) 品 的 數(shù) 量 ， 其 初 值 為 M-1； SB， 表 示目 前 還 可 再 存 放 的 B產(chǎn) 品 的 數(shù) 量 ， 其 初 值 為 N-1。A產(chǎn) 品 入 庫(kù) 的 過(guò) 程 可 描 述 為 ： B產(chǎn) 品 入 庫(kù) 的 過(guò) 程 可 描 述

19、 為 ：while(1) while(1)wait(SA); /* 還 可 放 A產(chǎn) 品 ？ */ wait (SB); /* 還 可 放 B產(chǎn) 品 ？ */wait(mutex); wait(mutex);將 A產(chǎn) 品 放 入 倉(cāng) 庫(kù) ； 將 B產(chǎn) 品 放 入 倉(cāng) 庫(kù) ；signal(mutex); signal(mutex); signal(SB); /*可 放 B產(chǎn) 品 數(shù) 增 1*/ signal(SA); /*可 放 A產(chǎn) 品 數(shù) 增 1*/ 23 n 四 、1.死 鎖 （ deadlock）系 統(tǒng) 中 存 在 一 個(gè) 進(jìn) 程 集 合 ， 該 集 合 中 的 每 個(gè) 進(jìn) 程 都 占

20、用了 一 定 數(shù) 量 的 資 源 ， 并 且 在 等 待 被 集 合 中 的 其 他 進(jìn) 程 占用 的 資 源例 ： 某 系 統(tǒng) 由 相 同 類(lèi) 型 的 8個(gè) 資 源 組 成 ， 若 資 源 可 被 3個(gè) 進(jìn) 程共 享 ， 每 個(gè) 進(jìn) 程 最 多 可 申 請(qǐng) 3個(gè) 資 源 ， 問(wèn) 該 系 統(tǒng) 是 否 會(huì) 發(fā)生 死 鎖 ？ 24 n Mutual exclusion： 互 斥n Hold and wait： 保 持 等 待 ， 申 請(qǐng) 資 源 時(shí) 擁 有 其 他 資 源n No preemption： 非 剝 奪 ， 進(jìn) 程 占 有 的 資 源 只 能 由 進(jìn) 程 自己 釋 放 ， 不 會(huì) 被

21、別 的 進(jìn) 程 剝 奪n Circular wait： 循 環(huán) 等 待 (若 各 類(lèi) 資 源 的 資 源 數(shù) 為 1， 則 一定 死 鎖 ) 25 n 間 接 預(yù) 防 ： 阻 止 Mutual exclusion, Hold and wait及 No preemption都 滿(mǎn) 足n 直 接 預(yù) 防 ： 阻 止 circular wait的 發(fā) 生 。一 種 可 行 的 方 法 ： 有 序 申 請(qǐng) 法 （ 對(duì) 所 有 資 源 類(lèi) 別 編 號(hào) ， 進(jìn) 程 申 請(qǐng)資 源 按 序 進(jìn) 行 ） 。例 ： 哲 學(xué) 家 就 餐 問(wèn) 題 ， 筷 子 編 號(hào) ， 先 拿 編 號(hào) 小 的 、 再 拿 大 的 。

22、 26 n 進(jìn) 程 申 請(qǐng) 資 源 時(shí) ， 決 定 是 否 應(yīng) 該 滿(mǎn) 足n 必 須 預(yù) 先 知 道 每 個(gè) 進(jìn) 程 需 要 的 各 類(lèi) 資 源 數(shù)n Bankers algorithm， 銀 行 家 算 法n 基 本 思 想 ， 若 新 的 狀 態(tài) 是 安 全 的 （ safe） ， 則 滿(mǎn) 足 它n Safe state： 從 此 狀 態(tài) 出 發(fā) ， 存 在 某 種 執(zhí) 行 順 序 （ 安 全序 列 ,safe sequence） ， 可 以 使 所 有 進(jìn) 程 執(zhí) 行 完 畢 。n 安 全 狀 態(tài) 只 是 暫 時(shí) 安 全 ， 如 果 以 后 資 源 分 配 不 當(dāng) ， 也會(huì) 導(dǎo) 致 死

23、鎖 ； 不 安 全 狀 態(tài) 不 一 定 就 死 鎖 。 27 狀 態(tài) （ a） 是 安 全 的(a) (b) (c) (d) (e)(a) (b) (c) (d) 狀 態(tài) （ b） 是 不 安 全 的 28n P4 沒(méi) 有 獲 得 資 源 ， 打 上 標(biāo) 記n 置 W = (0,0,0,0,1)n P3請(qǐng) 求 的 資 源 = W. 給 P3打 標(biāo) 記 ， 并 置 W = W + (0,0,0,1,0) = (0,0,0,1,1)n 算 法 無(wú) 法 找 到 滿(mǎn) 足 條 件 的 進(jìn) 程 ， 終 止 。 所 以 系 統(tǒng) 發(fā) 生 死 鎖 ，P1和 P2 是 死 鎖 進(jìn) 程 R1 R2 R3 R4 R5

24、P1P2P3P4 Request Allocated AvailableR1 R2 R3 R4 R5 R1 R2 R3 R4 R50 1 0 0 10 0 1 0 10 0 0 0 11 0 1 0 1 1 0 1 1 01 1 0 0 00 0 0 1 00 0 0 0 0 0 0 0 0 1 29 n 當(dāng) 發(fā) 生 死 鎖 時(shí) ， 如 何 恢 復(fù) 死 鎖 Abort all deadlocked processes. Abort one process at a time until the deadlock cycle is eliminated. In which order shoul

25、d we choose to abort? Priority of the process. How long process has computed, and how much longer to completion.Resources the process has used.Resources process needs to complete.How many processes will need to be terminated. Is process interactive or batch? Selecting a victim minimize cost Rollback

26、 return to some safe state, restart process for that state.Starvation same process may always be picked as victim, include number of rollback in cost factor. 30 1. CPU約 束 進(jìn) 程 與 I/O約 束 進(jìn) 程進(jìn) 程 的 執(zhí) 行 是 CPU burst與 I/O burst交 替 的 過(guò)程 CPU約 束 進(jìn) 程 ： 大 量 時(shí) 間 作 計(jì) 算 ， 少 量 I/O I/O 約 束 進(jìn) 程 ： 大 量 的 I/O， 少 量 時(shí) 間 作

27、計(jì) 算 31 2. 調(diào) 度 準(zhǔn) 則 (criteria) 32 3. 調(diào) 度 模 式 (decision mode)Non-preemptive（ 非 搶 占 式 ）進(jìn) 程 一 旦 被 調(diào) 度 ， 則 執(zhí) 行 至 結(jié) 束 或 不 能 繼 續(xù) 執(zhí) 行 （ 如因 為 發(fā) 起 I/O操 作 而 等 待 ）Preemptive（ 搶 占 式 ）當(dāng) 一 個(gè) 新 的 進(jìn) 程 到 達(dá) 時(shí)當(dāng) 有 進(jìn) 程 從 阻 塞 變 為 就 緒 時(shí)進(jìn) 程 從 核 心 態(tài) 返 回 到 用 戶(hù) 態(tài) 時(shí) （ 如 中 斷 、 系統(tǒng) 調(diào) 用 返 回 時(shí) ）注 ： 此 搶 占 非 指 內(nèi) 核 搶 占 33 4. 常 用 調(diào) 度 算 法

28、n FCFS(first come first served) 先 來(lái) 先 服 務(wù) ， 直 至 結(jié) 束 (nonpreemptive)n RR:Round robin 時(shí) 間 片 輪 轉(zhuǎn) (time slice,preemptive) 時(shí) 間 片 到 時(shí) ， 將 進(jìn) 程 放 入 就 緒 隊(duì) 列 的 末 尾 ， 然 后 從 隊(duì) 列 頭 部取 出 一 個(gè) 進(jìn) 程 運(yùn) 行 公 平 的 調(diào) 度 策 略 ， 不 會(huì) 導(dǎo) 致 進(jìn) 程 饑 餓 n Priority scheduling： 基 于 優(yōu) 先 級(jí) 的 調(diào) 度存 在 問(wèn) 題 ： 饑 餓 低 優(yōu) 先 級(jí) 進(jìn) 程 可 能 永 遠(yuǎn) 得 不 到 執(zhí) 行解

29、決 辦 法 ： 老 化 （ Aging） 隨 著 時(shí) 間 的 推 移 ， 進(jìn) 程 的優(yōu) 先 級(jí) 可 以 提 升 (即 進(jìn) 程 的 優(yōu) 先 級(jí) 可 以 是 動(dòng) 態(tài) 的 ) 34 q Relocation(重 定 位 )： 程 序 只 有 在 執(zhí) 行 時(shí) 才 能 確 定 其 在 內(nèi) 存中 的 位 置q Protection(保 護(hù) )： 進(jìn) 程 在 未 被 允 許 時(shí) 不 能 訪(fǎng) 問(wèn) 其 他 進(jìn) 程 的地 址 空 間q Sharing(共 享 )： 應(yīng) 該 提 供 機(jī) 制 允 許 進(jìn) 程 訪(fǎng) 問(wèn) 共 享 地 址 空 間中 的 信 息q Logical address(邏 輯 地 址 )： 用 戶(hù)

30、進(jìn) 程 訪(fǎng) 問(wèn) 的 地 址 ， 即 虛 地址 q Physical address(物 理 地 址 )： 物 理 存 儲(chǔ) 器 的 地 址 35 36 n 分 區(qū) ： 將 內(nèi) 存 劃 分 為 若 干 個(gè) 分 區(qū) ， 每 個(gè) 分 區(qū) 存 放 一 個(gè) 進(jìn) 程 ， 以 支持 多 道 程 序 (multi-programming)， Fixed partitioning:固 定 大 小 的 分 區(qū) ， 分 區(qū) 內(nèi) 部 會(huì) 出 現(xiàn) 碎 塊(internal fragment) Dynamic partitioning:動(dòng) 態(tài) 分 區(qū) ， 按 照 進(jìn) 程 大 小 決 定 分 區(qū) 大 小， 不 存 在 內(nèi) 部

31、 碎 塊 ， 但 有 外 部 碎 塊 （ external fragment)， 涉 及放 置 算 法 (placement algorithm)： first fit,best fit, next fitOSprocess 5 process 8process 2 OSprocess 5process 2 OSprocess 5process 2 OSprocess 5process 9process 2process 9 process 10 37 Buddy system（ 常 用 于 空 閑 內(nèi) 存 管 理 ） 38n若 一 次 TLB訪(fǎng) 問(wèn) 時(shí) 間 為 ,一 次 存 儲(chǔ) 器 訪(fǎng) 問(wèn)

32、時(shí) 間 為 1n TLB命 中 率 為 ， 則 平 均 存 取 時(shí) 間 EAT為 ：EAT = (1 + ) + (2 + )(1 )= 2 + 頁(yè) 表 的 實(shí) 現(xiàn) 方 式 ：l 頁(yè) 表 分 級(jí)l Hash頁(yè) 表l 倒 置 頁(yè) 表 39 40 41 n 進(jìn) 程 的 虛 地 址 空 間 (virtual address space) 由 進(jìn) 程 的 邏 輯 地 址 組 成 的 地 址 空 間 。 虛 地 址 空 間 可 以 遠(yuǎn) 大 于 系 統(tǒng) 的 物 理 內(nèi) 存 。 虛 擬 存 儲(chǔ) 器 (virtual memory)： 邏 輯 地 址 訪(fǎng) 問(wèn)的 存 儲(chǔ) 器 42 43 n 決 定 何 時(shí) 將

33、進(jìn) 程 的 邏 輯 頁(yè) 面 裝 入 內(nèi) 存 Demand paging（ 按 需 調(diào) 頁(yè) ） ： 發(fā) 生 缺 頁(yè) 時(shí) ， 才 將頁(yè) 面 裝 入 。 Prepaging（ 預(yù) 取 ） ： 預(yù) 先 將 某 些 頁(yè) 面 裝 入 內(nèi) 存 。 44 n OS分 配 給 進(jìn) 程 的 物 理 內(nèi) 存 不 夠 用 時(shí) ， 需 要 頁(yè) 替 換n Optimal： 最 優(yōu) 化 方 法 ， 選 擇 將 來(lái) 最 久 不 會(huì) 被 訪(fǎng) 問(wèn) 的 頁(yè) 換 出 需 要 預(yù) 先 知 道 頁(yè) 訪(fǎng) 問(wèn) 序 列 不 可 能 實(shí) 現(xiàn) ， 只 是 作 為 一 個(gè) 評(píng) 判 標(biāo) 準(zhǔn)n FIFO： 最 先 裝 入 的 被 換 出n LRU:最

34、久 未 使 用 的 頁(yè) 被 換 出 (基 于 locality現(xiàn) 象 ， 很 有 效 )n Clock policy， 時(shí) 鐘 算 法 。 LRU算 法 不 易 實(shí) 現(xiàn) ， 用 時(shí) 鐘 算 法 近似 模 擬 每 頁(yè) 設(shè) 置 一 個(gè) reference bit， 為 1表 示 在 時(shí) 鐘 指 針 循 環(huán) 一 周內(nèi) 被 訪(fǎng) 問(wèn) 過(guò) ； 查 找 替 換 頁(yè) ： 指 針 掃 描 ， 若 reference bit =1,置 為 0,否 則 該 頁(yè) 就 是 替 換對(duì) 象 。 Belady s Anomaly(belady異 態(tài) ):內(nèi) 存 大 ， 反 而 缺 頁(yè) 率 高 45 46 n 進(jìn) 程 執(zhí) 行

35、時(shí) 缺 頁(yè) 率 過(guò) 高 ， 使 得 系 統(tǒng) 忙 于 頁(yè) 面 換 進(jìn) 換出 ， 因 此 執(zhí) 行 效 率 低 。 提 高 效 率 的 可 行 方 法 ： 優(yōu) 化 頁(yè) 調(diào) 入 與 替 換 算 法 ； 增 加 物 理 內(nèi) 存 ； 減 少 進(jìn) 程 數(shù) ； 提 供 更 快 速 的 交 換 設(shè) 備 。n 工 作 集 （ working set,進(jìn) 程 近 期 訪(fǎng) 問(wèn) 的 頁(yè) 面 的 集 合） 為 防 止 抖 動(dòng) ， 應(yīng) 該 使 得 進(jìn) 程 獲 得 足 夠 的 內(nèi) 存 以 使 進(jìn) 程的 工 作 集 在 內(nèi) 存 中 計(jì) 算 工 作 集 的 算 法七 、 抖 動(dòng) (thrashing) 47 八 、 交 換 區(qū)

36、管 理n 實(shí) 現(xiàn) 虛 擬 存 儲(chǔ) 的 重 要 手 段n 擴(kuò) 大 內(nèi) 存 ， 使 系 統(tǒng) 可 以 運(yùn) 行 比 物 理 內(nèi) 存 大 的 程 序 。n 交 換 空 間 （ swap space） 交 換 文 件 ， 文 件 系 統(tǒng) 下 的 一 個(gè) 文 件 （ 如 windows下 的頁(yè) 面 文 件 ） 交 換 設(shè) 備 （ 如 linux的 swap分 區(qū) ） 后 者 比 前 者 的 讀 寫(xiě) 效 率 高 交 換 設(shè) 備 的 管 理數(shù) 據(jù) 結(jié) 構(gòu) 交 換 設(shè) 備 上 的 空 間 信 息 ； 頁(yè) 表 項(xiàng) 上 標(biāo) 識(shí) 頁(yè) 面 在 交 換 區(qū) 中 的 信 息 。n Linux中 的 Swap cache： 提

37、 高 交 換 設(shè) 備 的 存 取 效 率 48 1.文 件 系 統(tǒng)n 文 件 控 制 塊 （ FCB）n 目 錄n 空 閑 磁 盤(pán) 空 間 管 理n 文 件 系 統(tǒng) 性 能 49 n文 件 控 制 塊 （ FCB)permissions, dates, ownershipsize, Data blocks indexes 50 UNIX/Linux 文 件 控 制 塊 i-node(index node:索 引 節(jié) 點(diǎn) ） 51 n目 錄 ： 存 儲(chǔ) 目 錄 下 文 件 名 字 及 屬 性 （ 如 FCB信 息 ） q Two ways of handling long file names

38、in directory (a) In-line (b) In a heap 52An example of how a long name is stored in Windows 98 53The steps in looking up /usr/ast/mbox 54 n 文 件 系 統(tǒng) 空 閑 磁 盤(pán) 空 間 管 理(a) Storing the free list on a linked list(b) A bit map 55 56 57q I-nodes placed at the start of the diskq Disk divided into cylinder gro

39、ups each with its own blocks and i-nodes 58 2. I/O子 系 統(tǒng)n I/O設(shè) 備 分 類(lèi) ： 獨(dú) 占 、 共 享n I/O設(shè) 備 的 工 作 方 式 及 特 點(diǎn) :n 程 序 查 詢(xún) （ Programmed I/O）n 中 斷 （ Interrupt）n 直 接 存 儲(chǔ) 器 訪(fǎng) 問(wèn) （ DMA）n I/O子 系 統(tǒng) 分 層 n Buffer與 cachen 磁 盤(pán) 調(diào) 度 算 法n RAID 59 Layers of the I/O system and the main functions of each layer 60 Buffern I/

40、O buffering(緩 沖 )n 內(nèi) 存 中 開(kāi) 辟 的 一 個(gè) 區(qū) 域 ， 用 于 設(shè) 備 I/O時(shí) 緩 存n 解 決 CPU與 I/O設(shè) 備 的 速 度 匹 配 問(wèn) 題n 解 決 數(shù) 據(jù) 傳 輸 大 小 匹 配 問(wèn) 題n 提 高 I/O的 存 取 效 率n 直 接 由 OS管 理 （ 數(shù) 據(jù) 結(jié) 構(gòu) ） n Buffer 與 Cache的 區(qū) 別cache： 高 速 緩 存 ， 是 一 個(gè) 低 速 存 儲(chǔ) 介 質(zhì) 中 信 息 的 部 分 拷貝 ， 目 的 是 為 了 實(shí) 現(xiàn) 快 速 存 取 ， 如 TLB 61 n Disk scheduling（ 磁 盤(pán) 請(qǐng) 求 的 調(diào) 度 ）n 影

41、 響 磁 盤(pán) 存 取 速 度 的 主 要 因 素 ：n Seek time（ 尋 道 時(shí) 間 ）n Rotational latency（ 旋 轉(zhuǎn) 延 遲 ）n Data Transfer Rate（ 數(shù) 據(jù) 傳 輸 速 率 ）n 教 材 中 磁 盤(pán) 調(diào) 度 的 目 的 ： 降 低 磁 盤(pán) 平 均 尋 道 時(shí) 間n FCFS n SSTFn SCAN,C-SCANn LOOK,C-LOOKn 訪(fǎng) 問(wèn) 時(shí) 間 優(yōu) 化 算 法 ： 綜 合 考 慮 尋 道 時(shí) 間 和 旋 轉(zhuǎn) 延 遲 62 63 D C B AD C B A AB C DI/O Requests I/O Processing Ord

42、erFront-End Controller CylindersWithout Optimization (FIFO) D B C AD C B A AB C DI/O Requests I/O Processing OrderFront-End Controller CylindersWith command queuing 64 65 66 n RAID（ 磁 盤(pán) 陣 列 ， redundant array of independent disks）n 提 高 存 取 帶 寬 ： 各 磁 盤(pán) 可 以 獨(dú) 立 進(jìn) 行 I/On 提 高 冗 余 度 ： 數(shù) 據(jù) 鏡 像 或 校 驗(yàn)n 常 用 ：n RAID 1 n RAID 5n RAID 6n RAID 1+0