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

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

1、1 l 操 作 系 統(tǒng) 概 述l 進(jìn) 程 管 理l 存 儲 管 理l 文 件 系 統(tǒng) 與 I/O 2操 作 系 統(tǒng) 給 計 算 機(jī) 一 個 靈 活 的 大 腦 、一 個 強(qiáng) 健 的 心 臟 和 突 出 的 個 性 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) 級 (privileged mode） ， 擁 有 相 同 的 地 址 空 間 ， 通信 采 用 常 規(guī) C函 數(shù) 調(diào) 用 的 形 式 。 6 7 系 統(tǒng) 調(diào) 用 是 一 個 復(fù) 雜 的過 程系 統(tǒng) 調(diào) 用 往 往 通 過 軟 中斷 的 方 式 實(shí) 現(xiàn)系 統(tǒng) 調(diào) 用 在 為 應(yīng) 用 程 序提 供 操 作 系 統(tǒng) 服 務(wù) 的 同時 ， 也 實(shí) 現(xiàn) 了 對 計 算 機(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、 存 儲 空 間 ， 及 其 他 資 源 （ 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) 程 中 的 線 程 共 享 進(jìn) 程 資 源 ， 但 擁 有 私 有 堆 棧 及 線 程 控 制塊 (TCB， 存 儲 寄 存 器 值 、 優(yōu) 先 級 及 其 他 線 程 狀 態(tài) 信 息 )q 核 心 級 線 程 （ KLT： kernel-level thread） 應(yīng) 用 程 序 通 過 API調(diào) 用 核 心 線 程 管 理 例 程 (kernel thread facility)來 管 理 ： 需 要 進(jìn) 行 模 式 切 換 是 OS調(diào) 度 的 基 本 單 位 線 程 阻 塞 不 會 導(dǎo) 致 整 個 進(jìn) 程 的 阻 塞 在 多 處 理 器 環(huán) 境 下 ， 內(nèi) 核 可 使 線 程

5、在 不 同 的 處 理 器 上運(yùn) 行 E.g. windows thread 10 q 用 戶 級 線 程 （ ULT： user-level thread） 由 應(yīng) 用 程 序 自 己 通 過 線 程 庫 (thread library)來 管理 ： 線 程 創(chuàng) 建 、 終 止 、 線 程 間 通 信 ， 線 程 調(diào) 度 與切 換 OS感 知 不 到 ULT的 存 在 線 程 阻 塞 會 導(dǎo) 致 整 個 進(jìn) 程 的 阻 塞 理 論 上 講 ， 在 任 何 OS下 都 可 以 實(shí) 現(xiàn) 無 法 利 用 多 處 理 器 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( /初 始 化 線 程 屬 性 為 缺 省 屬 性 pthread_create( /創(chuàng) 建 線 程 pthread_join(tid,NULL); /等 待 線 程 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) 一 次 只 能 由 一 個 進(jìn) 程 訪 問 的 資 源q 臨 界 區(qū) (critical section) 訪 問 臨 界 資 源 的 代 碼 段 稱 為 臨 界 區(qū) （ CS） 14 q 互 斥 (mutual exclusion)在 一 個 時 刻 最 多 只 有 一 個 進(jìn) 程 在 臨 界 區(qū)q 同 步 (synchro

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

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

10、進(jìn) 程 不 會 無 止境 的 等 待 （ 即 不 會 有 饑 餓 現(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算 法 ： 算 法 直 觀 ， 只

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

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

13、兩 個 操 作 原 語 訪 問 信 號 量 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 信 號 量 full， 初 始 化 為 0,表

14、示 緩 沖 區(qū) 中 可 消 費(fèi) 的 資 源 數(shù) mutex， 初 始 化 為 1,用 于 對 緩 沖 區(qū) 的 互 斥 操 作 empty, 初 始 化 為 緩 沖 區(qū) 的 長 度 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個 進(jìn) 程 （ P1， P2， ， Pn） 向 容 量 為 M的 緩 沖 區(qū) 寫 數(shù) 據(jù) ， 每 個 進(jìn) 程一 次 寫 1個 數(shù) 據(jù) ， 當(dāng) 緩 沖 區(qū) 寫 滿 時 ， 另 一 個 讀 進(jìn) 程 Pr一 次 將 M個 數(shù) 據(jù) 全 部 讀 完， 如 此 反 復(fù) 。 請 用 信 號 量 解 決 這 些 進(jìn) 程 的 同 步 互 斥 問 題 。答 ： 本 題 中 需 要 定 義 下 述 變 量 和 信 號 量 ：data_type bufferM; /* data_type對 應(yīng) 于 所 需 要 的 數(shù) 據(jù) 類 型 ， 如 int、 float等 */ int in=0； /* 用

16、 來 指 示 下 一 個 可 存 放 數(shù) 據(jù) 的 緩 沖 區(qū) */semaphore empty=M; /* 對 應(yīng) 空 閑 的 緩 沖 區(qū) */semaphore full=0; /* 對 應(yīng) 緩 沖 區(qū) 中 的 數(shù) 據(jù) */semaphore mutex=1; /* 用 來 實(shí) 現(xiàn) Pi進(jìn) 程 對 變 量 in的 互 斥 訪 問 */進(jìn) 程 Pi可 描 述 為 ：Pi() while(1) wait(empty); wait(mutex); 向 緩 沖 區(qū) bufferin中 寫 數(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 例 ： 有 一 個 倉 庫 ， 可 以 存 放 A和 B兩 種 產(chǎn) 品 ， 但 要 求 ：（ 1） 每 次 只 能 存 入 一 種 產(chǎn) 品 （ A或 B） ；（ 2） -NA產(chǎn) 品 數(shù) 量 -B產(chǎn) 品 數(shù) 量 M。其 中 ， N和 M是 正 整 數(shù) 。 試 用 信 號 量 來 同 步 產(chǎn) 品

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

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

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

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

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

23、鎖 ； 不 安 全 狀 態(tài) 不 一 定 就 死 鎖 。 27 狀 態(tài) （ a） 是 安 全 的(a) (b) (c) (d) (e)(a) (b) (c) (d) 狀 態(tài) （ b） 是 不 安 全 的 28n P4 沒 有 獲 得 資 源 ， 打 上 標(biāo) 記n 置 W = (0,0,0,0,1)n P3請 求 的 資 源 = W. 給 P3打 標(biāo) 記 ， 并 置 W = W + (0,0,0,1,0) = (0,0,0,1,1)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ā) 生 死 鎖 時 ， 如 何 恢 復(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交 替 的 過程 CPU約 束 進(jìn) 程 ： 大 量 時 間 作 計 算 ， 少 量 I/O I/O 約 束 進(jìn) 程 ： 大 量 的 I/O， 少 量 時 間 作

27、計 算 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) 一 個 新 的 進(jìn) 程 到 達(dá) 時當(dāng) 有 進(jìn) 程 從 阻 塞 變 為 就 緒 時進(jìn) 程 從 核 心 態(tài) 返 回 到 用 戶 態(tài) 時 （ 如 中 斷 、 系統(tǒng) 調(diào) 用 返 回 時 ）注 ： 此 搶 占 非 指 內(nèi) 核 搶 占 33 4. 常 用 調(diào) 度 算 法

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

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

30、進(jìn) 程 訪 問 的 地 址 ， 即 虛 地址 q Physical address(物 理 地 址 )： 物 理 存 儲 器 的 地 址 35 36 n 分 區(qū) ： 將 內(nèi) 存 劃 分 為 若 干 個 分 區(qū) ， 每 個 分 區(qū) 存 放 一 個 進(jìn) 程 ， 以 支持 多 道 程 序 (multi-programming)， Fixed partitioning:固 定 大 小 的 分 區(qū) ， 分 區(qū) 內(nèi) 部 會 出 現(xiàn) 碎 塊(internal fragment) Dynamic partitioning:動 態(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訪 問 時 間 為 ,一 次 存 儲 器 訪 問

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

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

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

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

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

37、 高 交 換 設(shè) 備 的 存 取 效 率 48 1.文 件 系 統(tǒng)n 文 件 控 制 塊 （ FCB）n 目 錄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目 錄 ： 存 儲 目 錄 下 文 件 名 字 及 屬 性 （ 如 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) 空 閑 磁 盤 空 間 管 理(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è) 備 分 類 ： 獨(dú) 占 、 共 享n I/O設(shè) 備 的 工 作 方 式 及 特 點(diǎn) :n 程 序 查 詢 （ Programmed I/O）n 中 斷 （ Interrupt）n 直 接 存 儲 器 訪 問 （ DMA）n I/O子 系 統(tǒng) 分 層 n Buffer與 cachen 磁 盤 調(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) 存 中 開 辟 的 一 個 區(qū) 域 ， 用 于 設(shè) 備 I/O時 緩 存n 解 決 CPU與 I/O設(shè) 備 的 速 度 匹 配 問 題n 解 決 數(shù) 據(jù) 傳 輸 大 小 匹 配 問 題n 提 高 I/O的 存 取 效 率n 直 接 由 OS管 理 （ 數(shù) 據(jù) 結(jié) 構(gòu) ） n Buffer 與 Cache的 區(qū) 別cache： 高 速 緩 存 ， 是 一 個 低 速 存 儲 介 質(zhì) 中 信 息 的 部 分 拷貝 ， 目 的 是 為 了 實(shí) 現(xiàn) 快 速 存 取 ， 如 TLB 61 n Disk scheduling（ 磁 盤 請 求 的 調(diào) 度 ）n 影

41、 響 磁 盤 存 取 速 度 的 主 要 因 素 ：n Seek time（ 尋 道 時 間 ）n Rotational latency（ 旋 轉(zhuǎn) 延 遲 ）n Data Transfer Rate（ 數(shù) 據(jù) 傳 輸 速 率 ）n 教 材 中 磁 盤 調(diào) 度 的 目 的 ： 降 低 磁 盤 平 均 尋 道 時 間n FCFS n SSTFn SCAN,C-SCANn LOOK,C-LOOKn 訪 問 時 間 優(yōu) 化 算 法 ： 綜 合 考 慮 尋 道 時 間 和 旋 轉(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（ 磁 盤 陣 列 ， redundant array of independent disks）n 提 高 存 取 帶 寬 ： 各 磁 盤 可 以 獨(dú) 立 進(jìn) 行 I/On 提 高 冗 余 度 ： 數(shù) 據(jù) 鏡 像 或 校 驗(yàn)n 常 用 ：n RAID 1 n RAID 5n RAID 6n RAID 1+0