《操作系統(tǒng)原理》算法-m

《《操作系統(tǒng)原理》算法-m》由會員分享，可在線閱讀，更多相關《《操作系統(tǒng)原理》算法-m（129頁珍藏版）》請在裝配圖網上搜索。

1、2021-5-31 進 程 同 步 互 斥 1 信 號 量 機 制 （ semaphore ） 1965年 ， 由 荷 蘭 學 者 Dijkstra提 出 （ P、V分 別 是 荷 蘭 語 的 test (proberen) 和increment (verhogen) ） 一 種 卓 有 成 效 的 進 程 同 步 機 制 最 初 提 出 的 是 二 元 信 號 量 （ 互 斥 ） 推 廣 到 一 般 信 號 量 （ 多 值 ） （ 同 步 ） P、 V操 作 是 原 語 2021-5-31 進 程 同 步 互 斥 2 整 型 信 號 量 定 義 一 個 整 數(shù) S， 僅 能 通 過 兩 個

2、原 子 操 作 來訪 問 ： wait(S): while S=0 then do no-op S := S 1; Signal(S): S := S + 1; 很 明 顯 ， 不 滿 足 讓 權 等 待 。 2021-5-31 進 程 同 步 互 斥 3 記 錄 型 信 號 量是 一 個 數(shù) 據(jù) 結 構定 義 如 下 ： struct semaphore int value; pointer_PCB queue; 信 號 量 說 明 ： semaphore s; 2021-5-31 進 程 同 步 互 斥 4 Wait（ P操 作 ）wait(s) s.value = s.value -1

3、; if (s.value 0) block(S.L);/ 該 進 程 狀 態(tài) 置 為 等 待 狀 態(tài)/ 將 PCB插 入 相 應 的 等 待 隊 列 s.queue; 2021-5-31 進 程 同 步 互 斥 5 Signal（ V操 作 ）signal(s) s.value = s.value +1; if (s.value 0表 示 有 S個 資 源 可 用S=0表 示 無 資 源 可 用S0則 | S |表 示 S等 待 隊 列 中 的 進 程 個 數(shù)P(S)： 表 示 申 請 一 個 資 源 V(S)： 表 示 釋 放 一 個 資 源 。信 號 量 的 初 值 應 該 大 于 等

4、于 0 2021-5-31 進 程 同 步 互 斥 10 2) P.V操 作 必 須 成 對 出 現(xiàn) ， 有 一 個 P操 作 就 一 定 有 一 個V操 作當 為 互 斥 操 作 時 ， 它 們 同 處 于 同 一 進 程當 為 同 步 操 作 時 ， 則 不 在 同 一 進 程 中 出 現(xiàn)如 果 P(S1)和 P(S2)兩 個 操 作 在 一 起 ， 那 么 P操 作 的 順 序至 關 重 要 。一 個 同 步 P操 作 與 一 個 互 斥 P操 作 在 一 起 時 同 步 P操 作在 互 斥 P操 作 前而 兩 個 V操 作 無 關 緊 要 2021-5-31 進 程 同 步 互 斥 1

5、1 進 程 互 斥用 信 號 量 實 現(xiàn) 臨 界 區(qū) 互 斥 :設 置 一 信 號 量 ， 信 號 量 初 值 唯 一 ，進 入 臨 界 區(qū) 以 前 對 信 號 量 執(zhí) 行 P操 作 ，退 出 臨 界 區(qū) 后 對 信 號 量 執(zhí) 行 V操 作 . 2021-5-31 進 程 同 步 互 斥 12 進 程 同 步 同 步 問 題 可 分 為 兩 類 ： 保 證 一 組 合 作 進 程 按 確 定 的 次 序 執(zhí) 行 保 證 共 享 緩 沖 區(qū) 的 合 作 進 程 的 同 步 。 2021-5-31 進 程 同 步 互 斥 13 合 作 進 程 的 執(zhí) 行 次 序 若 干 個 進 程 為 了 完

6、成 一 個 共 同 任 務 而 并 發(fā) 執(zhí) 行 ， 在 這 些 進 程中 ， 有 些 進 程 之 間 有 次 序 的 要 求 ， 有 些 進 程 之 間 沒 有 次 序 的要 求 ， 為 了 描 述 方 便 ， 可 以 用 一 個 圖 來 表 示 進 程 集 合 的 執(zhí) 行次 序 。 如 圖 2021-5-31 進 程 同 步 互 斥 14 例如 圖 ， 試 用 信 號 量 實 現(xiàn) 這 三 個 進 程 的同 步 。 設 有 兩 個 信 號 量 SB、 SC， 初 值 均 為 Pa： Pb： Pc： P(SB); P(SC) V(SB); V(SC); 2021-5-31 進 程 同 步 互 斥

7、 15 【 思 考 題 1】如 圖 ， 試 用 信 號 量 實 現(xiàn) 這 三 個 進程 的 同 步 。 2021-5-31 進 程 同 步 互 斥 16 解設 有 兩 個 信 號 量 S1、 S2， 初 值 均 為 P1： P2： P3： P(S1) V(S1); V(S2); P(S2) 2021-5-31 進 程 同 步 互 斥 17 【 思 考 題 2】如 圖 ， 試 用 信 號 量 實 現(xiàn) 這 6個 進 程 的 同 步 2021-5-31 進 程 同 步 互 斥 18 解設 有 5個 信 號 量 S2、 S3、 S4、 S5、 S6， 初 值 均 為 P1： P2： P3： P(S2);

8、 P(S3) V(S2); V(S3)；V(S4); V(S6); V(S5) P4： P5： P6： P(S4); P(S5); P(S6); P(S5); P(S6); V(S5)； V(S6); 2021-5-31 進 程 同 步 互 斥 19 共 享 緩 沖 區(qū) 的 進 程 的 同 步 設 某 計 算 進 程 CP和 打 印 進 程 IOP共 用 一 個 單緩 沖 區(qū) ， CP進 程 負 責 不 斷 地 計 算 數(shù) 據(jù) 并 送入 緩 沖 區(qū) T中 ， IOP進 程 負 責 不 斷 地 從 緩 沖區(qū) T中 取 出 數(shù) 據(jù) 去 打 印 。 2021-5-31 進 程 同 步 互 斥 20

9、分 析通 過 分 析 可 知 ， CP、 IOP必 須 遵 守 以 下同 步 規(guī) 則 ： 當 CP進 程 把 計 算 結 果 送 入 緩 沖 區(qū) 時 ，IOP進 程 才 能 從 緩 沖 區(qū) 中 取 出 結 果 去打 印 ; 當 IOP進 程 把 緩 沖 區(qū) 中 的 數(shù) 據(jù) 取 出 打 印后 ， CP進 程 才 能 把 下 一 個 計 算 結 果 送入 緩 沖 區(qū) 2021-5-31 進 程 同 步 互 斥 21 解 為 此 設 有 兩 個 信 號 量 Sa=0， Sb=1， Sa表 示 緩 沖 區(qū)中 有 無 數(shù) 據(jù) ， Sb表 示 緩 沖 區(qū) 中 有 無 空 位 置 。 兩 個 進 程 的 同

10、 步 可 以 描 述 如 下 ： 2021-5-31 進 程 同 步 互 斥 22 【 思 考 題 】1.用 P.V操 作 解 決 下 圖 之 同 步 問 題提 示 ： 分 別 考 慮 對 緩 沖 區(qū) S和 T的 同 步 ， 再合 并 考 慮 get copy puts t 2021-5-31 進 程 同 步 互 斥 23 解 設 置 四 個 信 號 量 Sin=1， Sout=0， Tin=1， Tout=0；get： while（ 1） P(Sin） ; 將 數(shù) 放 入 S; V(Sout); copy： while（ 1） P(Sout） ; P(Tin） ; 將 數(shù) 從 S放 入 T;

11、 V(Tout); V(Sin); put： while（ 1） P(Tout） ; 將 數(shù) 從 T取 走 ; V(Tin); 2021-5-31 進 程 同 步 互 斥 24 【 思 考 題 】 桌 上 有 一 空 盤 ， 最 多 允 許 存 放 一 只 水 果 。爸 爸 可 向 盤 中 放 一 個 蘋 果 或 放 一 個 桔 子 ，兒 子 專 等 吃 盤 中 的 桔 子 ， 女 兒 專 等 吃 蘋 果 。試 用 P、 V操 作 實 現(xiàn) 爸 爸 、 兒 子 、 女 兒 三 個并 發(fā) 進 程 的 同 步 。提 示 ： 設 置 一 個 信 號 量 表 示 可 否 向 盤 中 放 水果 ， 一 個

12、 信 號 量 表 示 可 否 取 桔 子 ， 一 個 信號 量 表 示 可 否 取 蘋 果 。 2021-5-31 進 程 同 步 互 斥 25 解設 置 三 個 信 號 量 S,So,Sa ， 初 值 分 別為 1， 0， 0。 分 別 表 示 可 否 向 盤 中 放 水果 ， 可 否 取 桔 子 ， 可 否 取 蘋 果 。 2021-5-31 進 程 同 步 互 斥 26 Father() while(1) p(S); 將 水 果 放 入 盤 中 ; if(是 桔 子 )v(So); else v(Sa); Son() while(1) p(So) 取 桔 子 v(S); 吃 桔 子 ;

13、Daughter() while(1) p(Sa) 取 蘋 果 v(S); 吃 蘋 果 ; 2021-5-31 進 程 同 步 互 斥 27 4 經 典 的 進 程 同 步 問 題 4.1 生 產 者 /消 費 者 問 題 4.2 讀 者 /寫 者 問 題 4.3 哲 學 家 進 餐 問 題 2021-5-31 進 程 同 步 互 斥 28 4.1 生 產 者 /消 費 者 問 題 生 產 者 消 費 者 問 題 是 一 種 同 步 問 題 的 抽 象描 述 。 計 算 機 系 統(tǒng) 中 的 每 個 進 程 都 可 以 消費 （ 使 用 ） 或 生 產 （ 釋 放 ） 某 類 資 源 。 這些

14、資 源 可 以 是 硬 件 資 源 ， 也 可 以 是 軟 件 資源 。 當 某 一 進 程 使 用 某 一 資 源 時 ， 可 以 看 作 是消 費 ， 稱 該 進 程 為 消 費 者 。 而 當 某 一 進 程釋 放 某 一 資 源 時 ， 它 就 相 當 于 生 產 者 。 2021-5-31 進 程 同 步 互 斥 29 問 題 描 述通 過 一 個 有 界 緩 沖 區(qū) 可 以 把 一 群 生 產 者P1,P2,Pm， 和 一 群 消 費 者 Q1,Q2, Qn聯(lián) 系 起 來 。 如 圖 只 要 緩 沖 區(qū) 未 滿 ， 生 產 者 就 可 以 把 產 品 送入 緩 沖 區(qū) ; 只 要

15、緩 沖 區(qū) 未 空 ， 消 費 者 就 可 以 從 緩 沖 區(qū)中 取 走 物 品 。 2021-5-31 進 程 同 步 互 斥 30 圖 . .P Q放 消 息 取 消 息nn個 緩 沖 區(qū)(Buffer)i j 2021-5-31 進 程 同 步 互 斥 31 問 題 分 析 為 解 決 生 產 者 消 費 者 問 題 ， 應 該 設 兩 個 同 步 信 號量 ， 一 個 說 明 空 緩 沖 區(qū) 的 數(shù) 目 ， 用 S1表 示 ， 初值 為 有 界 緩 沖 區(qū) 的 大 小 N， 另 一 個 說 明 已 用 緩 沖區(qū) 的 數(shù) 目 ， 用 S2表 示 ， 初 值 為 。 由 于 在 此 問 題

16、 中 有 M個 生 產 者 和 N個 消 費 者 ， 它們 在 執(zhí) 行 生 產 活 動 和 消 費 活 動 中 要 對 有 界 緩 沖 區(qū)進 行 操 作 。 由 于 有 界 緩 沖 區(qū) 是 一 個 臨 界 資 源 ， 必須 互 斥 使 用 ， 所 以 ， 另 外 還 需 要 設 置 一 個 互 斥 信號 量 mutex， 其 初 值 為 。 2021-5-31 進 程 同 步 互 斥 32 問 題 的 解Q： j = 0; while (1) P(S2); P(mutex); 從 Bufferj取 產 品 ; j = (j+1) % n; V(mutex); V(S1); 消 費 產 品 ;

17、;P： i = 0;while (1) 生 產 產 品 ; P(S1); P(mutex); 往 Buffer i放 產 品 ; i = (i+1) % n; V(mutex); V(S2); ; 2021-5-31 進 程 同 步 互 斥 33 采 用 AND信 號 量 集 解 決 生 產 者 -消 費 者問 題 Q： j = 0; while (1) Swait(s2, mutex); 從 Bufferj取 產 品 ; j = (j+1) % n; Ssignal(s1, mutex); 消 費 產 品 ; ;P： i = 0;while (1) 生 產 產 品 ; Swait(s1, m

18、utex); 往 Buffer i放 產 品 ; i = (i+1) % n; Ssignal(s2, mutex); ; 2021-5-31 進 程 同 步 互 斥 34 【 思 考 題 】有 一 個 倉 庫 ， 可 以 存 放 A和 B兩 種 產 品 ， 但 要求 ：（ 1） 每 次 只 能 存 入 一 種 產 品 （ A或 B）（ 2） N A產 品 數(shù) 量 B產 品 數(shù) 量 M。其 中 ， N和 M是 正 整 數(shù) 。 試 用 P、 V操 作 描 述 產品 A與 B的 入 庫 過 程 。提 示 ： 設 兩 個 信 號 量 Sa、 SbSa表 示 允 許 A產 品 比 B產 品 多 入 庫

19、 的 數(shù) 量Sb表 示 允 許 B產 品 比 A產 品 多 入 庫 的 數(shù) 量 2021-5-31 進 程 同 步 互 斥 35 解設 兩 個 信 號 量 Sa、 Sb， 初 值 分 別 為 M-1， N-1Sa表 示 允 許 A產 品 比 B產 品 多 入 庫 的 數(shù) 量Sb表 示 允 許 B產 品 比 A產 品 多 入 庫 的 數(shù) 量設 互 斥 信 號 量 mutex， 初 值 為 1。 2021-5-31 進 程 同 步 互 斥 36 B產 品 入 庫 進 程 ： j = 0; while (1) P(Sb); P(mutex); B產 品 入 庫 V(mutex); V(Sa); 消

20、費 產 品 ; ;A產 品 入 庫 進 程 ：i = 0;while (1) 生 產 產 品 ; P(Sa); P(mutex); A產 品 入 庫 V(mutex); V(Sb); ; 2021-5-31 進 程 同 步 互 斥 37 4.2 讀 者 /寫 者 問 題 有 兩 組 并 發(fā) 進 程 : 讀 者 和 寫 者 ,共 享 一 組 數(shù) 據(jù) 區(qū) 要 求 ： 允 許 多 個 讀 者 同 時 執(zhí) 行 讀 操 作 不 允 許 讀 者 、 寫 者 同 時 操 作 不 允 許 多 個 寫 者 同 時 操 作 2021-5-31 進 程 同 步 互 斥 38 第 一 類 ： 讀 者 優(yōu) 先如 果 讀

21、 者 來 ：1） 無 讀 者 、 寫 者 ， 新 讀 者 可 以 讀2） 有 寫 者 等 ， 但 有 其 它 讀 者 正 在 讀 ， 則 新 讀 者也 可 以 讀3） 有 寫 者 寫 ， 新 讀 者 等如 果 寫 者 來 ：1） 無 讀 者 ， 新 寫 者 可 以 寫2） 有 讀 者 ， 新 寫 者 等 待3） 有 其 它 寫 者 ， 新 寫 者 等 待 2021-5-31 進 程 同 步 互 斥 39 第 一 類 讀 者 寫 者 問 題 的 解 法 設 有 兩 個 信 號 量 w=1， mutex=1 另 設 一 個 全 局 變 量 readcount =0 w用 于 讀 者 和 寫 者 、

22、 寫 者 和 寫 者 之 間 的 互 斥 readcount表 示 正 在 讀 的 讀 者 數(shù) 目 mutex用 于 對 readcount 這 個 臨 界 資 源 的 互 斥訪 問 2021-5-31 進 程 同 步 互 斥 40 讀 者 ： while (1) P(mutex); readcount +; if (readcount=1) P (w); V(mutex); 讀 P(mutex); readcount -; if (readcount=0) V(w); V(mutex); ; 寫 者 ： while (1) P(w); 寫 V(w); ; 2021-5-31 進 程 同 步

23、互 斥 41 第 一 類 讀 者 寫 者 問 題 的 解 法 （ 一 般 信 號 量 集 ）寫 者 ：while(1) Swait(wmutex,1,1; rcount,R,0); 寫 ； Ssignal(wmutex,1);讀 者 ：while(1) Swait(rcount,1,1; wmutex,1,0); 讀 ； Ssignal(rcount,1); n 增 加 一 個 限 制 條 件 ： 同 時 讀 的 “ 讀 者 ” 最 多 R個u wmutex表 示 “ 允 許 寫 ” ， 初 值 是 1u rcount表 示 “ 允 許 讀 者 數(shù) 目 ” ， 初 值 為 R 2021-5-3

24、1 進 程 同 步 互 斥 42 【 思 考 題 】 寫 優(yōu) 先 修 改 以 上 讀 者 寫 者 問 題 的 算 法 ， 使 之對 寫 者 優(yōu) 先 ， 即 一 旦 有 寫 者 到 達 ， 后續(xù) 的 讀 者 必 須 必 須 等 待 ， 無 論 是 否 有讀 者 在 讀 。 提 示 ， 增 加 一 個 信 號 量 ， 用 于 在 寫 者到 達 后 封 鎖 后 續(xù) 的 讀 者 2021-5-31 進 程 同 步 互 斥 43 解 增 加 一 個 信 號 量 s， 初 值 為 1讀 者 ： while (1) P(s); P(mutex); readcount +; if (readcount=1)

25、P (w); V(mutex); V(s); 讀 P(mutex); readcount - -; if (readcount=0) V(w); V(mutex); ; 寫 者 ： while (1) P(s); P(w); 寫 V(w); V(s); ; 2021-5-31 進 程 同 步 互 斥 44 4.3 哲 學 家 就 餐 問 題 有 五 個 哲 學 家 圍 坐 在 一 圓 桌 旁 ， 桌 中 央 有 一盤 通 心 粉 ， 每 人 面 前 有 一 只 空 盤 子 ， 每 兩 人之 間 放 一 只 筷 子 每 個 哲 學 家 的 行 為 是 思 考 ， 感 到 饑 餓 ， 然 后吃 通

26、 心 粉 為 了 吃 通 心 粉 ， 每 個 哲 學 家 必 須 拿 到 兩 只 筷子 ， 并 且 每 個 人 只 能 直 接 從 自 己 的 左 邊 或 右邊 去 取 筷 子 2021-5-31 進 程 同 步 互 斥 45 設 fork5為 5 個 信 號 量 ， 初 值 為 均 1Philosopheri：while (1) 思 考 ； P(forki); P(fork(i+1) % 5)； 進 食 ； V(forki); V(fork(i+1) % 5)； 解 2021-5-31 進 程 同 步 互 斥 46 以 上 解 法 會 出 現(xiàn) 死 鎖為 防 止 死 鎖 發(fā) 生 可 采 取 的

27、 措 施 ： 最 多 允 許 4個 哲 學 家 同 時 坐 在 桌 子 周 圍 僅 當 一 個 哲 學 家 左 右 兩 邊 的 筷 子 都 可 用 時 ， 才 允許 他 拿 筷 子 （ ） 給 所 有 哲 學 家 編 號 ， 奇 數(shù) 號 的 哲 學 家 必 須 首 先 拿左 邊 的 筷 子 ， 偶 數(shù) 號 的 哲 學 家 則 反 之 分 析 2021-5-31 進 程 同 步 互 斥 47 采 用 AND信 號 量 集 解 決 哲 學 家 就 餐 問 題設 fork5為 5 個 信 號 量 ， 初 值 為 均 1Philosopheri：while (1) 思 考 ； Swait( forki

28、, fork(i+1) % 5 )； 進 食 ； Ssignal( forki, fork(i+1) % 5 )； 2021-5-31 進 程 調 度 48 3.2 調 度 算 法 先 來 先 服 務 算 法 （ FCFS： First Come First Serve）有 利 于 長 作 業(yè) ， 不 利 于 短 作 業(yè) 最 短 作 業(yè) 優(yōu) 先 算 法 （ SJF： Shortest Job First） -提 高 了 系 統(tǒng) 吞 吐 量對 長 作 業(yè) 不 利未 考 慮 作 業(yè) 的 緊 迫 程 度作 業(yè) 時 間 的 估 計 時 間 不 準 2021-5-31 進 程 調 度 49 高 優(yōu) 先

29、權 調 度 算 法 照 顧 緊 迫 作 業(yè) ， 常 用 于 批 處 理 靜 態(tài) 優(yōu) 先 權依 據(jù) 進 程 類 型 ： 系 統(tǒng) 進 程 高 于 一 般 用 戶 進 程依 據(jù) 對 資 源 的 要 求 ： 要 求 少 的 高 于 多 的依 據(jù) 用 戶 要 求 ： 緊 迫 程 度 和 付 費 情 況 動 態(tài) 優(yōu) 先 權創(chuàng) 建 進 程 時 賦 予 的 優(yōu) 先 權 ， 遂 進 程 的 推 進 或 隨 其 等 待時 間 的 增 加 而 改 變 ， 可 防 止 某 些 進 程 無 限 期 的 等 待 2021-5-31 進 程 調 度 50 最 高 響 應 比 優(yōu) 先 算 法 （ HRN： Highest R

30、esponse Ratio Next） 響 應 比 R = 作 業(yè) 周 轉 時 間 / 作 業(yè) 處 理 時 間 =（ 作 業(yè) 處 理 時 間 +作 業(yè) 等 待 時 間 ） / 作 業(yè) 處理 時 間 = 1 +（ 作 業(yè) 等 待 時 間 / 作 業(yè) 處 理 時 間 ） 2021-5-31 進 程 調 度 51 調 度 算 法 應 用 例 子 1 假 設 在 單 道 批 處 理 環(huán) 境 下 有 四 個 作 業(yè) ，已 知 它 們 進 入 系 統(tǒng) 的 時 間 、 估 計 運 行 時間 應 用 先 來 先 服 務 、 最 短 作 業(yè) 優(yōu) 先 和 最 高響 應 比 優(yōu) 先 作 業(yè) 調 度 算 法 ， 分

31、別 計 算 出作 業(yè) 的 平 均 周 轉 時 間 和 帶 權 的 平 均 周 轉時 間 2021-5-31 進 程 調 度 52 2021-5-31 進 程 調 度 53 先 來 先 服 務 調 度 算 法 計 算 結 果 作 業(yè) 進 入 時 間 估 計 運 行時 間（ 分 鐘 ） 開 始 時 間 結 束 時 間 周 轉 時 間（ 分 鐘 ） 帶 權 周 轉時 間 JOB1 8： 00 120 8： 00 10： 00 120 1JOB2 8： 50 50 10： 00 10： 50 120 2.4JOB3 9： 00 10 10： 50 11： 00 120 12 JOB4 9： 50 20

32、 11： 00 11： 20 90 4.5作 業(yè) 平 均 周 轉 時 間 T = 112.5作 業(yè) 帶 權 平 均 周 轉 時 間 W = 4.975 450 19.9 2021-5-31 進 程 調 度 54 最 短 作 業(yè) 優(yōu) 先 作 業(yè) 算 法 計 算 結 果 作 業(yè) 進 入 時 間 估 計 運 行時 間（ 分 鐘 ） 開 始 時 間 結 束 時 間 周 轉 時 間（ 分 鐘 ） 帶 權 周 轉時 間JOB1 8： 00 120 8： 00 10： 00 120 1 JOB2 8： 50 50 10： 30 11： 20 150 3JOB3 9： 00 10 10： 00 10： 10

33、70 7JOB4 9： 50 20 10： 10 10： 30 40 2 作 業(yè) 平 均 周 轉 時 間 T = 95作 業(yè) 帶 權 平 均 周 轉 時 間 W = 3.25 380 13 2021-5-31 進 程 調 度 55 最 高 響 應 比 優(yōu) 先 作 業(yè) 算 法 計 算 結 果 2021-5-31 進 程 調 度 56 多 隊 列 反 饋 調 度 算 法 將 就 緒 隊 列 分 為 N級 ， 每 個 就 緒 隊 列 分 配 給不 同 的 時 間 片 ， 隊 列 級 別 越 高 ， 時 間 片 越 長， 級 別 越 小 ， 時 間 片 越 短 ； 當 進 程 第 一 次 就 緒 時

34、， 進 入 第 一 級 隊 列 系 統(tǒng) 從 第 一 級 調 度 ， 當 第 一 級 為 空 時 ， 系 統(tǒng)轉 向 第 二 個 隊 列 ， .當 運 行 進 程 用 完 一 個 時間 片 ， 放 棄 CPU時 ， 進 入 下 一 級 隊 列 ； 等 待 進 程 被 喚 醒 時 ， 進 入 原 來 的 就 緒 隊 列 ； 2021-5-31 進 程 調 度 57 就 緒 隊 列 1就 緒 隊 列 2就 緒 隊 列 3就 緒 隊 列 4 至 CPU至 CPU至 CPU至 CPU 2021-5-31 進 程 調 度 58 3.6.3 利 用 銀 行 家 算 法 避 免 死 鎖最 有 代 表 性 的 避

35、 免 死 鎖 算 法 ， 由 Dijkstra提 出。1、 銀 行 家 算 法 中 的 數(shù) 據(jù) 結 構 可 利 用 資 源 向 量 Available。 它 是 一 個 含 有 m個 元 素 的 數(shù) 組 ， 其 中 每 個 元 素 代 表 一 類 可 利用 資 源 的 數(shù) 目 。 如 ： A B C5 2 3 2021-5-31 進 程 調 度 59 最 大 需 求 矩 陣 Max。 n*m矩 陣 ， 表 示 n個 進 程的 每 一 個 對 m類 資 源 的 最 大 需 求 。A B CP1 5 6 2P2 3 3 1P3 4 2 5P4 3 3 2 2021-5-31 進 程 調 度 60

36、分 配 矩 陣 Allocation 。 n*m矩 陣 ， 表 示 每 個進 程 分 配 的 資 源 數(shù) 。A B CP1 2 1 2P2 1 2 1P3 2 2 2P4 1 3 2 2021-5-31 進 程 調 度 61 需 求 矩 陣 Need 。 n*m矩 陣 ， 表 示 每 個 進 程還 需 要 各 類 資 源 數(shù) 。A B CP1 3 5 2P2 2 1 1P3 2 2 3P4 2 3 2 2021-5-31 進 程 調 度 62 例設 系 統(tǒng) 有 五 個 進 程 和 三 類 資 源 ， 每 類 資 源 分 別 有 10、5、 7。 在 T0時 刻 資 源 分 配 情 況 如 圖

37、2021-5-31 進 程 調 度 63 銀 行 家 算 法 描 述當 進 程 Pi提 出 資 源 申 請 時 ， 系 統(tǒng) 執(zhí) 行 下 列步 驟 ：（ 1） 若 RequestiNeedi,轉 （ 2） ； 否 則 錯 誤 返 回（ 2） 若 RequestiAvailable, 轉 （ 3） ； 否 則 進 程 等 待 2021-5-31 進 程 調 度 64 （ 3） 假 設 系 統(tǒng) 分 配 了 資 源 ， 則 有 ：Available:=Available-Requesti;Allocationi:=Allocationi+Requesti;Needi:=Needi-Requesti（

38、4） 執(zhí) 行 安 全 性 算 法 ， 若 系 統(tǒng) 新 狀 態(tài) 是 安 全的 ， 則 分 配 完 成 ， 若 系 統(tǒng) 新 狀 態(tài) 是 不 安 全 的， 則 恢 復 原 狀 態(tài) ， 進 程 等 待 2021-5-31 進 程 調 度 65 安 全 性 算 法為 進 行 安 全 性 檢 查 ， 定 義 數(shù) 據(jù) 結 構 ：Work:ARRAY0.m-1 of integer;Finish:ARRAY0.n-1 of Boolean;m代 表 資 源 的 數(shù) 量 ， n代 表 進 程 的 數(shù) 量 2021-5-31 進 程 調 度 66 安 全 性 算 法 步 驟(1) Work:=Available;

39、 Finish:=false;(2) 尋 找 滿 足 下 列 條 件 的 i： a). Finishi=false; b). NeediWork;如 果 不 存 在 ， 則 轉 (4) 2021-5-31 進 程 調 度 67 (3) Work:=Work+Allocationi; Finishi:=true; 轉 (2)(4) 若 對 所 有 i,Finishi=true,則 系 統(tǒng) 處 于安 全 狀 態(tài) ， 否 則 處 于 不 安 全 狀 態(tài) 2021-5-31 進 程 調 度 68 T0時 刻 的 安 全 性 檢 查 T0時 刻 可 以 找 到 一 個 安 全 序 列 p1,p3,p4,

40、p2,p0. 系 統(tǒng) 是 安 全的 。 2021-5-31 進 程 調 度 69 例 1： T0時 刻 P1請 求 資 源 P1發(fā) 出 請 求 Request(1,0,2)， 執(zhí) 行 銀 行 家 算 法 2021-5-31 進 程 調 度 70 執(zhí) 行 安 全 性 算 法 可 以 找 到 一 個 安 全 序 列 p1,p3,p4,p0,p2. 系 統(tǒng) 是 安 全 的 ， 可以 將 P1的 請 求 分 配 給 它 。 2021-5-31 進 程 調 度 71 P1請 求 資 源 P1發(fā) 出 請 求 Request(1,0,2), 執(zhí) 行 銀 行 家算 法 條 件 滿 足 ， 找 到 安 全 序

41、列p1,p3,p4,p2,p0 分 配 2021-5-31 進 程 調 度 72 P4請 求 資 源 P4發(fā) 出 請 求 Request(3,3,0), 執(zhí) 行 銀 行 家算 法 Available=2 3 0 不 能 通 過 算 法 第 2步 （ RequestiAvailable ） ， 所 以 P4等 待。 2021-5-31 進 程 調 度 73 P0請 求 資 源 Request（ 0， 2， 0） ， 執(zhí) 行 銀 行 家 算 法 2021-5-31 進 程 調 度 74 進 行 安 全 性 檢 查 Available2,1,0已 不 能 滿 足 任 何 進 程 需要 ， 所 以 系

42、 統(tǒng) 進 入 不 安 全 狀 態(tài) ， P0的請 求 不 能 分 配 2021-5-31 進 程 調 度 75 練 習 ： 有 三 類 資 源 A(17)、 B(5)、 C(20)。 有 5個 進 程P1P5。 T0時 刻 系 統(tǒng) 狀 態(tài) 如 下 ：問 (1)、 T0時 刻 是 否 為 安 全 狀 態(tài) ， 給 出 安 全 系 列 。(2)、 T0時 刻 ， P2: Request(0,3,4)， 能 否 分 配 ， 為 什 么 ？(3)、 在 (2)的 基 礎 上 P4： Request(2,0,1)， 能 否 分 配 ， 為 什 么 ？(4)、 在 (3)的 基 礎 上 P1： Request

43、(0,2,0)， 能 否 分 配 ， 為 什 么 ？ 最 大 需 求 已 分 配P1 5 5 9 2 1 2P2 5 3 6 4 0 2P3 4 0 11 4 0 5P4 4 2 5 2 0 4P5 4 2 4 3 1 4 2021-5-31 進 程 調 度 76 解 ： (1) T0時 刻 的 出 安 全 系 列最 大 需 求 已 分 配 NeedP1 5 5 9 2 1 2 3 4 7P2 5 3 6 4 0 2 1 3 4P3 4 0 11 4 0 5 0 0 6P4 4 2 5 2 0 4 2 2 1P5 4 2 4 3 1 4 1 1 0 A(17)、 B(5)、 C(20)Work

44、=2 3 3先 求 出 Need和 Work 2021-5-31 進 程 調 度 77 Work Allocation Need W+A FinishP5 2 3 3 3 1 4 1 1 0 5 4 7 TP4 5 4 7 2 0 4 2 2 1 7 4 11 TP3 7 4 11 4 0 5 0 0 6 11 4 16 TP2 11 4 16 4 0 2 1 3 4 15 4 18 TP1 15 4 18 2 1 2 3 4 7 17 5 20 TWork=2 3 3 2021-5-31 進 程 調 度 78 (2) P2: Request(0,3,4) 因 （ Available =2 3

45、 3） Request(0,3,4) 所 以 不 能 分 配 2021-5-31 進 程 調 度 79 (3) P4： Request(2,0,1)Work Allocation Need W+A FinishP4 0 3 2 4 0 5 0 2 0 4 3 7 TP5 4 3 7 3 1 4 1 1 0 7 4 11 TP3 7 4 11 4 0 5 0 0 6 11 4 16 TP2 11 4 16 4 0 2 1 3 4 15 4 18 T P1 15 4 18 2 1 2 3 4 7 17 5 20 T Available =2 3 3Allocation Need Available

46、P1 2 1 2 3 4 7 0 3 2P2 4 0 2 1 3 4P3 4 0 5 0 0 6P4 4 0 5 0 2 0P5 3 1 4 1 1 0 有 安 全 序 列P4 P5 P3 P2 P1 可 以分 配 2021-5-31 進 程 調 度 80 (4) P1： Request(0,2,0)Allocation Need AvailableP1 2 3 2 3 2 7 0 1 2P2 4 0 2 1 3 4P3 4 0 5 0 0 6P4 4 0 5 0 2 0P5 3 1 4 1 1 0 0 1 2 已 不 能 滿 足 任 何 進 程 的 需 要 ， 不 能 分 配 2021-5-

47、31 內 存 管 理 置 換 算 法 4.7 頁 面 淘 汰 算 法 先 進 先 出 頁 面 淘 汰 算 法 （ FIFO） 選 擇 在 內 存 中 駐 留 時 間 最 長 的 頁 并 淘 汰 之 第 二 次 機 會 淘 汰 算 法 (SCR) 按 照 先 進 先 出 算 法 選 擇 某 一 頁 面 ， 檢 查 其 訪問 位 ， 如 果 為 0， 則 淘 汰 該 頁 ， 如 果 為 1， 則給 第 二 次 機 會 ， 并 將 訪 問 位 置 0 理 想 淘 汰 算 法 最 佳 頁 面 算 法 （ OPT） 淘 汰 以 后 不 再 需 要 的 或 最 遠 的 將 來 才 會 用 到的 頁 面 2

48、021-5-31 內 存 管 理 置 換 算 法 1、 最 佳 置 換 算 法 最 佳 置 換 算 法 是 一 種 理 想 化 的 理 論 上算 法 ， 具 有 最 好 的 性 能 ， 但 在 實 際 上卻 難 于 實 現(xiàn) 。 它 選 擇 永 不 使 用 的 ， 或 者 是 在 最 長 時間 內 不 再 被 訪 問 的 頁 面 作 為 淘 汰 頁 面。 但 這 是 無 法 預 知 的 ， 因 而 該 算 法 無法 實 現(xiàn) 。 它 在 固 定 分 配 頁 面 方 式 中 可保 證 獲 得 最 低 的 缺 頁 率 。 2021-5-31 內 存 管 理 置 換 算 法 2、 先 進 先 出 頁 面

49、 置 換 算 法 該 算 法 總 是 淘 汰 最 先 調 入 內 存 的 頁 面， 即 選 擇 在 內 存 中 駐 留 時 間 最 久 的 頁面 予 以 淘 汰 。 該 算 法 實 現(xiàn) 時 把 一 個 進 程 已 調 入 內 存的 頁 面 按 先 后 次 序 鏈 接 成 一 個 隊 列 ，并 設 置 一 個 替 換 指 針 ， 指 向 最 老 頁 面。 2021-5-31 內 存 管 理 置 換 算 法 最 近 最 久 未 使 用 頁 面 淘 汰 算 法 （ LRU） 選 擇 最 后 一 次 訪 問 時 間 距 離 當 前 時 間 最長 的 一 頁 并 淘 汰 之 即 淘 汰 沒 有 使 用

50、的 時 間 最 長 的 頁 實 現(xiàn) 代 價 很 高 軟 件 方 法 或 硬 件 方 法 2021-5-31 內 存 管 理 置 換 算 法 LRU軟 件 解 法 ：設 置 一 個 頁 號 棧 ， 當 一 個 頁 面 被 訪 問 時 ， 就立 即 將 它 的 頁 號 壓 入 頁 號 棧 ， 并 檢 查 頁 號 棧中 是 否 有 與 剛 壓 入 棧 頂 的 相 同 的 頁 號 ， 若 有， 則 從 頁 號 棧 中 抽 出 ， 以 保 證 頁 號 棧 中 無 相同 的 頁 號 。 當 系 統(tǒng) 要 淘 汰 一 節(jié) 時 ， 總 是 從 頁號 棧 底 取 出 一 個 頁 號 淘 汰 ， 即 淘 汰 的 頁

51、 是 最久 未 使 用 的 。 2021-5-31 內 存 管 理 置 換 算 法 LRU近 似 算 法 ： Clock算 法在 頁 表 中 增 加 一 訪 問 位 ， 每 當 訪 問 一 頁 時 ，將 該 頁 的 訪 問 位 由 硬 件 置 1， 軟 件 周 期 （ T） 性地 將 所 有 訪 問 位 置 0。 在 時 間 T內 ， 訪 問 過 的 頁其 訪 問 位 為 1， 反 之 為 0， 淘 汰 為 0 的 頁 。缺 點 ： T難 定 。 太 小 ， 訪 問 位 為 0的 頁 相 當 多， 所 選 的 不 一 定 是 最 久 未 用 的 。 太 大 ， 所 有 頁的 引 用 位 可 能

52、 都 為 1， 找 不 到 合 適 的 淘 汰 頁 。 2021-5-31 內 存 管 理 置 換 算 法 最 不 經 常 使 用 （ LFU） 選 擇 訪 問 次 數(shù) 最 少 的 頁 面 淘 汰 之 與 LRU的 硬 件 解 法 類 似 。 2021-5-31 內 存 管 理 置 換 算 法 頁 面 緩 沖 算 法 (PBA: Page Buffering Algorithm ) 頁 面 緩 沖 算 法 采 用 了 可 變 分 配 和 局 部 置換 方 式 頁 面 緩 沖 算 法 中 ， 設 置 了 兩 個 鏈 表 （ 隊列 ） 存 放 被 淘 汰 的 頁 ：空 閑 頁 鏈 表 （ 實 際

53、上 就 是 空 閑 物 理 塊鏈 表 ： 頁 面 未 修 改 ）已 修 改 頁 面 鏈 表 。 2021-5-31 內 存 管 理 置 換 算 法 當 需 要 讀 入 一 個 頁 面 時 ， 便 利 用 空 閑 物 理 塊鏈 表 中 的 第 一 個 物 理 塊 來 裝 入 。 當 有 一 個 未 被 修 改 的 頁 要 換 出 時 ， 并 不 將它 換 出 內 存 ， 而 是 直 接 把 它 所 在 的 物 理 塊 掛在 空 閑 頁 鏈 表 的 末 尾 。 換 出 一 個 已 修 改 的 頁 面 時 ， 則 將 其 所 在 的物 理 塊 掛 在 修 改 頁 面 鏈 表 的 末 尾 。 注 ：

54、換 出 頁 面 時 ， 頁 面 在 內 存 并 不 做 物 理 上的 移 動 ， 只 是 將 頁 表 中 的 表 項 移 到 上 述 兩 個鏈 表 之 一 中 。 2021-5-31 內 存 管 理 置 換 算 法 優(yōu) 點 ： 可 使 已 被 修 改 的 頁 面 和 未 被 修 改的 頁 面 ， 都 仍 留 在 內 存 中 。 當 進 程 以 后再 次 訪 問 這 些 頁 面 時 ， 就 有 可 能 只 須 花費 較 小 的 開 銷 。只 有 當 被 修 改 頁 面 達 到 一 定 數(shù) 量 ， 例 如64個 頁 面 時 ， 再 將 它 們 一 起 寫 回 到 磁 盤， 從 而 顯 著 地 減

55、少 了 磁 盤 I O的 操 作 次數(shù) 。 2021-5-31 內 存 管 理 置 換 算 法 某 程 序 在 內 存 中 分 配 三 個 塊 ， 訪 問 頁 的順 序 為 4， 3， 2， 1， 4， 3， 5， 4， 3，2， 1， 5， 按 FIFO、 LRU、 OPT算 法 分別 計 算 缺 頁 次 數(shù)假 設 開 始 時 所 有 頁 均 不 在 內 存例 1 2021-5-31 內 存 管 理 置 換 算 法 FIFO 4 3 2 1 4 3 5 4 3 2 1 5頁 1 4 3 2 1 4 3 5 5 5 2 1 1頁 2 4 3 2 1 4 3 3 3 5 2 2頁 3 4 3 2

56、 1 4 4 4 3 5 5 x x x x x x x x x 共 缺 頁 中 斷 9次 FIFO 2021-5-31 內 存 管 理 置 換 算 法 LRU 4 3 2 1 4 3 5 4 3 2 1 5頁 1 4 3 2 1 4 3 5 4 3 2 1 5頁 2 4 3 2 1 4 3 5 4 3 2 1頁 3 4 3 2 1 4 3 5 4 3 2 x x x x x x x x x x共 缺 頁 中 斷 10次 LRU 2021-5-31 內 存 管 理 置 換 算 法 OPT 4 3 2 1 4 3 5 4 3 2 1 5頁 1 4 3 2 1 1 1 5 5 5 2 1 1頁 2

57、 4 3 3 3 3 3 3 3 5 5 5頁 3 4 4 4 4 4 4 4 4 4 4 x x x x x x x 共 缺 頁 中 斷 7次 OPT 2021-5-31 內 存 管 理 置 換 算 法 練 習某 程 序 在 內 存 中 分 配 四 個 塊 ， 訪 問 頁 的走 向 為 4， 3， 2， 1， 4， 3， 5， 4， 3， 2， 1， 5， 按 LRU、 OPT算 法 分 別 計算 缺 頁 次 數(shù)假 設 開 始 時 所 有 頁 均 不 在 內 存 2021-5-31 內 存 管 理 置 換 算 法 LRU 4 3 2 1 4 3 5 4 3 2 1 5頁 1 4 3 2 1

58、4 3 5 4 3 2 1 5頁 2 4 3 2 1 4 3 5 4 3 2 1頁 3 4 3 2 1 4 3 5 4 3 2頁 4 4 3 2 1 1 1 5 4 3 x x x x x x x x共 缺 頁 中 斷 8次 2021-5-31 內 存 管 理 置 換 算 法 OPT 4 3 2 1 4 3 5 4 3 2 1 5頁 1 4 3 2 1 1 1 5 5 5 5 1 1頁 2 4 3 2 2 2 2 2 2 2 5 5頁 3 4 3 3 3 3 3 3 3 3 3頁 4 4 4 4 4 4 4 4 4 4 x x x x x x 共 缺 頁 中 斷 6次 2021-5-31 內

59、存 管 理 置 換 算 法 有 一 虛 擬 存 儲 系 統(tǒng) ， 采 用 先 進 先 出 的 頁 面 淘 汰算 法 。 在 內 存 中 為 每 個 進 程 分 配 3塊 。 進 程執(zhí) 行 時 使 用 頁 號 的 順 序 為 4 3 2 1 4 3 5 4 3 2 1 5(1) 該 進 程 運 行 時 總 共 出 現(xiàn) 幾 次 缺 頁 。(2) 若 每 個 進 程 在 內 存 有 4塊 ， 又 將 產 生 幾 次缺 頁 。(3) 如 何 解 釋 所 出 現(xiàn) 的 現(xiàn) 象 。 例 2 2021-5-31 內 存 管 理 置 換 算 法 FIFO 4 3 2 1 4 3 5 4 3 2 1 5頁 1 4

60、3 2 1 4 3 5 5 5 2 1 1頁 2 4 3 2 1 4 3 3 3 5 2 2頁 3 4 3 2 1 4 4 4 3 5 5 x x x x x x x x x 共 缺 頁 中 斷 9次 m=3 2021-5-31 內 存 管 理 置 換 算 法 FIFO 4 3 2 1 4 3 5 4 3 2 1 5頁 1 4 3 2 1 1 1 5 4 3 2 1 5頁 2 4 3 2 2 2 1 5 4 3 2 1頁 3 4 3 3 3 2 1 5 4 3 2頁 4 4 4 4 3 2 1 5 4 3 x x x x x x x x x x共 缺 頁 中 斷 10次 m=4 2021-5-

61、31 內 存 管 理 置 換 算 法 m=3時 ， 缺 頁 中 斷 9次m=4時 ， 缺 頁 中 斷 10次FIFO頁 面 淘 汰 算 法 會 產 生 異 常 現(xiàn) 象 （Belady現(xiàn) 象 ） ， 即 ： 當 分 配 給 進 程 的物 理 頁 面 數(shù) 增 加 時 ， 缺 頁 次 數(shù) 反 而 增加 2021-5-31 內 存 管 理 置 換 算 法 (1) 分 配 給 進 程 的 物 理 塊 數(shù)(2) 頁 本 身 的 大 小(3) 程 序 的 編 制 方 法(4) 頁 淘 汰 算 法影 響 缺 頁 次 數(shù) 的 因 素 2021-5-31 內 存 管 理 置 換 算 法 練 習程 序 編 制 方

62、法 1：for j:=1 to 128 for i:=1 to 128 Ai,j:=0; 程 序 編 制 方 法 2：for i:=1 to 128 for j:=1 to 128 Ai,j:=0;內 存 分 配 一 頁 ， 初 始 時 矩 陣 數(shù) 據(jù) 均 不 在 內 存 ；頁 面 大 小 為 128個 整 數(shù) ； 矩 陣 A128X128按 行 存 放 。這 兩 個 程 序 執(zhí) 行 時 分 別 會 產 生 多 少 次 缺 頁 中 斷 ？ 2021-5-31 磁 盤 調 度 算 法 2 磁 盤 調 度 算 法 當 多 個 訪 盤 請 求 在 等 待 時 ， 采 用 一 定 的 策 略， 對 這

63、 些 請 求 的 服 務 順 序 調 整 安 排 ， 旨 在 降低 平 均 磁 盤 服 務 時 間 ， 達 到 公 平 、 高 效 公 平 ： 一 個 I/O請 求 在 有 限 時 間 內 滿 足 高 效 ： 減 少 設 備 機 械 運 動 所 帶 來 的 時 間 浪 費 1) 先 來 先 服 務 2)最 短 尋 道 時 間 優(yōu) 先 3)掃 描 算 法 4)單 向 掃 描 調 度 算 法 2021-5-31 磁 盤 調 度 算 法 按 訪 問 請 求 到 達 的 先 后 次 序 服 務 優(yōu) 點 ： 簡 單 ， 公 平 ； 缺 點 ： 效 率 不 高 ， 相 鄰 兩 次 請 求 可能 會 造 成

64、 最 內 到 最 外 的 柱 面 尋 道 ，使 磁 頭 反 復 移 動 ， 增 加 了 服 務 時 間， 對 機 械 也 不 利2.1 先 來 先 服 務 2021-5-31 磁 盤 調 度 算 法 假 設 磁 盤 訪 問 序 列 ： 98， 183， 37， 122，14， 124， 65， 67 讀 寫 頭 起 始 位 置 ： 53 安 排 磁 頭 服 務 序 列 計 算 磁 頭 移 動 總 距 離 （ 道 數(shù) ）例 2021-5-31 磁 盤 調 度 算 法 圖 解98， 183， 37， 122， 14， 124， 65， 67磁 頭 走 過 的 總 道 數(shù) ： 640 2021-5-

65、31 磁 盤 調 度 算 法 優(yōu) 先 選 擇 距 當 前 磁 頭 最 近 的 訪 問 請 求 進行 服 務 ， 主 要 考 慮 尋 道 優(yōu) 先 優(yōu) 點 ： 改 善 了 磁 盤 平 均 服 務 時 間 ； 缺 點 ： 造 成 某 些 訪 問 請 求 長 期 等 待 得不 到 服 務2.2 最 短 尋 道 時 間 優(yōu) 先 (SSF) 2021-5-31 磁 盤 調 度 算 法 圖 解65， 67 ， 37， 14， 98， 122， 124， 183磁 頭 走 過 的 總 道 數(shù) ： 23698， 183， 37， 122， 14， 124， 65，67 2021-5-31 磁 盤 調 度 算 法

66、 克 服 了 最 短 尋 道 優(yōu) 先 的 缺 點 ， 既 考 慮 了 距 離， 同 時 又 考 慮 了 方 向 具 體 做 法 ： 當 設 備 無 訪 問 請 求 時 ， 磁 頭 不 動； 當 有 訪 問 請 求 時 ， 磁 頭 按 一 個 方 向 移 動 ，在 移 動 過 程 中 對 遇 到 的 訪 問 請 求 進 行 服 務 ，然 后 判 斷 該 方 向 上 是 否 還 有 訪 問 請 求 ， 如 果有 則 繼 續(xù) 掃 描 ； 否 則 改 變 移 動 方 向 ， 并 為 經過 的 訪 問 請 求 服 務 ， 如 此 反 復2.3 掃 描 算 法 （ 電 梯 算 法 ） 2021-5-31 磁 盤 調 度 算 法 圖 2021-5-31 磁 盤 調 度 算 法 圖 解37， 14， 65， 67 ， 98， 122， 124， 183磁 頭 走 過 的 總 道 數(shù) ： 20898， 183， 37， 122， 14， 124， 65， 67 2021-5-31 磁 盤 調 度 算 法 也 稱 單 向 掃 描 算 法 。 電 梯 算 法 杜 絕 了 饑 餓 ， 但 當 請 求 對 磁