Microsoft PowerPoint - os_4.ppt

行 程 資 科 系 林 偉 川 行 程 概 念 行 程 與 程 式 主 要 的 不 同 點 : 程 式 是 被 放 在 外 部 的 儲 存 裝 置 如 磁 碟 上, 而 行 程 則 被 放 在 記 憶 體 中 程 式 在 儲 存 裝 置 中 是 靜 態 的, 而 行 程 在 記 憶 體 中 是 動 態 的, 它 會 隨 著 一 些 事 件 的 發 生 而 產 生 相 對 的 改 變 行 程, 就 是 一 個 執 行 中 的 程 式 對 只 有 一 顆 CPU 的 系 統 而 言, 同 一 個 時 間 只 會 有 一 個 行 程 真 正 被 執 行 該 由 哪 個 行 程 執 行? 行 程 間 要 如 何 交 換 資 料 才 能 有 效 率 地 利 用 系 統 資 源? 行 程 管 理 2 1

行 程 簡 介 一 個 行 程 包 括 了 相 對 應 的 程 式 碼 程 式 計 數 器 (PC) 記 錄 下 一 個 要 被 執 行 的 指 令 CPU 中 各 暫 存 器 的 值 行 程 堆 疊 暫 時 儲 存 子 程 式 的 參 數 返 回 位 址 資 料 區 段 紀 錄 全 域 變 數 一 個 程 式 很 可 能 被 重 複 執 行 多 次 而 產 生 多 個 行 程, 但 是 這 些 行 程 是 彼 此 獨 立 的 3 行 程 的 狀 態 一 個 行 程 在 執 行 過 程 中, 會 改 變 很 多 狀 態, 狀 態 為 目 前 行 程 所 處 的 執 行 情 況 一 個 行 程 的 狀 態 通 常 有 下 列 幾 種 : 新 建 行 程 剛 被 產 生 的 狀 態 執 行 行 程 中 指 令 正 被 執 行 的 狀 態, 佔 有 CPU 資 源 等 待 行 程 目 前 正 在 等 待 事 件 發 生 的 狀 態 就 緒 行 程 準 備 好 被 執 行 的 狀 態 終 結 行 程 已 執 行 結 束 的 狀 態 單 CPU 中 同 一 時 間 內, 只 會 存 在 一 個 狀 態 為 執 行 的 行 程, 在 同 一 時 間 內 可 以 存 在 很 多 個 狀 態 為 等 待 或 就 緒 的 行 程 4 2

行 程 狀 態 圖 (91tku 93ncu 96,92nttu 97tku) 新 建 允 許 進 入 中 斷 離 開 結 束 就 緒 執 行 排 程 器 分 派 I/O 或 事 件 結 束 等 待 I/O 或 等 待 事 件 5 行 程 控 制 區 塊 行 程 控 制 區 塊 (PCB), 儲 存 行 程 在 執 行 時 相 關 的 資 訊 ( 開 哪 些 檔 行 程 所 處 狀 態 ) PCB 中 通 常 包 括 了 (94tku) 行 程 狀 態, 如 上 所 述 CPU 暫 存 器 行 程 在 執 行 時 發 生 中 斷, 作 業 系 統 需 要 將 暫 存 器 的 值 儲 存 起 來, 當 返 回 時 行 程 才 能 正 確 地 繼 續 執 行 排 程 資 訊 包 含 行 程 的 優 先 權 和 其 他 排 程 的 相 關 資 訊 I/O 狀 態 包 含 行 程 在 執 行 時 使 用 到 I/O 裝 置 開 啟 檔 案 6 3

行 程 控 制 區 塊 CPU 暫 存 器 種 類, 分 別 為 一 般 用 途 算 術 索 引 堆 疊 程 式 計 數 器 及 狀 況 暫 存 器 在 80386 CPU 以 下 的 規 劃 節 段 或 區 段 暫 存 器 分 別 有 CS SS DS ES 四 個 16 位 元 的 暫 存 器, 386 以 後 加 入 FS GS 兩 個,CS 就 是 規 劃 來 指 定 給 指 令 碼 存 放 的 區 段, 所 以 稱 為 指 令 段 (code segment) 暫 存 器, 而 SS 為 堆 疊 段 (stack segment) 暫 存 器,DS ES 分 別 為 資 料 段 (data segment) 及 額 外 段 (extra segment) 暫 存 器, FS GS 分 別 為 旗 號 段 (flag segment) 及 總 體 段 (global segment) 暫 存 器 7 行 程 控 制 區 塊 一 般 用 途 暫 存 器 :AX( 算 術 ) BX CX DX AX: 累 積 暫 存 器,BX: 基 底 暫 存 器,CX: 計 數 暫 存 器,DX: 資 料 暫 存 器 索 引 暫 存 器 :SI DI SI: 來 源 索 引 暫 存 器,DI: 目 的 索 引 暫 存 器 堆 疊 基 底 暫 存 器 :SP BP SP: 堆 疊 指 標 暫 存 器,BP: 基 底 指 標 暫 存 器 指 位 / 指 標 暫 存 器 ( 指 位 器 ):IP 程 式 計 數 器 稱 為 LC 或 稱 IC 作 為 存 放 下 一 個 電 腦 要 執 行 指 令 位 址 8 4

行 程 控 制 區 塊 旗 標 暫 存 器 :FLAG OF DF IF TF SF ZF AF PF CF AF: 輔 助 進 位 旗 標 CF: 進 位 旗 標 OF: 溢 位 旗 標 SF: 符 號 ( 負 號 ) 旗 標 PF: 奇 偶 旗 標 ZF: 零 值 旗 標 DF: 方 向 旗 標 IF: 中 斷 旗 標 TF: 單 步 旗 標 9 行 程 控 制 區 塊 行 程 其 他 資 訊 包 括 所 使 用 CPU 時 間 記 憶 體 大 小 行 程 代 號 等 都 可 放 於 PCB 中 當 行 程 進 行 切 換 時, 需 要 將 目 前 行 程 的 相 關 資 訊 記 錄 在 該 行 程 的 PCB 中, 並 將 另 一 個 行 程 的 PCB 載 入 至 系 統 中, 這 個 動 作 稱 為 內 文 切 換 (context switch) (96nttu) 當 CPU 的 使 用 權 由 一 個 行 程 轉 到 另 一 個 行 程 時 需 將 上 一 個 行 程 的 PCB 儲 存 起 來, 並 把 要 使 用 CPU 的 行 程 之 PCB 載 入 系 統, 稱 為 內 文 切 換 10 5

內 文 切 換 內 文 切 換 動 作 所 花 的 時 間 對 系 統 而 言 是 額 外 的 負 擔, 因 為 此 過 程 所 做 的 事 並 不 是 真 正 有 生 產 力 的 工 作, 此 時 間 是 由 要 儲 存 CPU 暫 存 器 個 數, 記 憶 體 的 速 度 CPU 是 否 提 供 特 別 的 指 令 來 決 定 執 行 緒 降 低 內 文 切 換 所 花 的 時 間 11 行 程 控 制 區 塊 (PCB) 行 程 指 的 是 正 在 執 行 的 程 式 行 程 不 只 是 程 式 碼 ( 有 時 也 稱 為 本 文 區,text section), 它 還 包 含 代 表 目 前 運 作 的 程 式 計 數 器 (Program counter) 數 值 和 處 理 器 的 暫 存 器 內 容 行 程 還 包 括 存 放 暫 用 資 料 ( 譬 如 : 副 程 式 的 參 數 返 回 位 址, 以 及 暫 時 性 變 數 ) 的 行 程 堆 疊 (stack), 以 及 包 含 整 體 變 數 的 資 料 區 間 (data section) 行 程 也 包 含 堆 積 (heap), 所 謂 堆 積 就 是 在 行 程 執 行 期 間 動 態 配 置 的 記 憶 體 12 6

行 程 控 制 區 塊 (PCB) 行 程 狀 態 行 程 代 號 程 式 計 數 器 暫 存 器 記 憶 體 限 制 己 開 啟 的 檔 案 串 列 13 行 程 的 切 換 行 程 P 0 作 業 系 統 行 程 P 1 中 斷 或 系 統 呼 叫 執 行 中 閒 置 將 狀 態 儲 存 至 PCB 0 由 PCB 1 載 入 狀 態 中 斷 或 系 統 呼 叫 閒 置 執 行 中 執 行 中 將 狀 態 儲 存 至 PCB 1 由 PCB 0 載 入 狀 態 閒 置 14 7

行 程 排 程 為 了 增 加 CPU 的 使 用 效 率 而 提 出 多 個 行 程 的 觀 念 一 個 單 CPU 的 系 統 來 說, 隨 時 只 能 有 一 個 行 程 在 執 行 其 他 行 程 則 必 須 等 待 CPU 空 閒 下 來, 然 後 再 經 由 排 程 器 選 出, 才 能 取 得 CPU 的 使 用 權 如 何 排 程 是 影 響 作 業 系 統 效 能 最 重 要 的 因 素 15 考 題 List the information stored in PCB. Describe the action taken by a kernel to context switching. Draw the process state transition diagram. Explain why a context switch may happen. 16 8

排 程 佇 列 一 個 行 程 在 執 行 期 間 會 在 各 種 不 同 的 佇 列 中 進 出 一 個 系 統 中 通 常 有 工 作 佇 列 紀 錄 系 統 中 所 有 的 行 程 就 緒 佇 列 一 個 行 程 (PCB) 準 備 要 執 行 時, 會 被 移 至 此, 形 成 一 個 PCB 串 列, 有 時 還 加 上 雜 湊 表 來 加 快 PCB 的 搜 尋 等 待 佇 列 行 程 在 執 行 期 間 要 等 待 某 些 事 件 完 成 才 能 執 行 時, 此 行 程 就 會 被 移 至 此 裝 置 佇 列 為 了 等 待 I/O 裝 置 動 作 完 成 而 產 生 的 佇 列, 每 個 裝 置 都 有 自 己 的 裝 置 佇 列 17 行 程 狀 態 圖 新 建 允 許 進 入 中 斷 離 開 結 束 就 緒 執 行 排 程 器 分 派 I/O 或 事 件 結 束 等 待 I/O 或 等 待 事 件 18 9

就 緒 佇 列 與 裝 置 佇 列 head tail 就 緒 佇 列 磁 碟 1 佇 列 編 輯 軟 體 head tail head tail 磁 碟 2 佇 列 PCB7 暫 存 器 PCB5 暫 存 器 PCB9 暫 存 器 PCB2 暫 存 器 PCB1 暫 存 器 19 排 程 器 一 個 行 程 從 開 始 執 行 到 最 後 離 開 系 統, 會 在 前 述 的 各 種 佇 列 進 出, 作 業 系 統 必 須 針 對 不 同 目 的 在 各 種 佇 列 中 採 取 不 同 的 選 取 行 程 的 方 法, 為 了 實 現 不 同 的 選 取 方 法, 必 須 使 用 不 同 的 排 程 器 作 業 系 統 中 主 要 的 排 程 器 有 : 長 程 排 程 器 (Job Scheduler) 從 磁 碟 中 選 取 合 適 的 行 程, 將 行 程 放 置 於 記 憶 體 中 準 備 執 行 短 程 排 程 器 (CPU Scheduler) 在 就 緒 佇 列 中 選 出 一 個 行 程, 然 後 將 CPU 的 使 用 權 交 給 該 行 程 20 10

排 程 器 一 個 新 的 行 程 最 初 是 置 於 就 緒 佇 列 它 就 一 直 在 就 緒 佇 列 中 等 待, 直 到 選 來 執 行 或 被 分 派 一 旦 這 個 行 程 配 置 CPU 並 且 進 行 執 行, 則 會 有 若 干 事 件 之 一 可 能 發 生 :. 行 程 可 發 出 I/O 要 求, 然 後 置 於 一 個 I/O 佇 列 中. 行 程 可 產 生 出 一 個 新 的 子 行 程 並 等 待 後 者 的 結 束 (fork 指 令 ). 行 程 可 強 行 地 移 離 CPU( 如 用 中 斷 的 結 果 一 樣 ), 然 後 放 回 就 緒 佇 列 中 21 排 程 器 22 11

排 程 器 長 程 排 程 器 和 短 程 排 程 器 最 大 的 不 同 點 執 行 的 頻 率 一 個 行 程 在 執 行 幾 毫 秒 後 就 會 產 生 I/O 中 斷, 這 時 短 程 排 程 器 就 必 須 執 行, 找 出 下 一 個 可 以 取 得 CPU 資 源 的 行 程 若 短 程 排 程 器 每 90 毫 秒 會 被 執 行 一 次, 每 次 花 10 毫 秒 才 選 出 下 一 個 行 程, 如 此 約 有 10%CPU 資 源 (10/(10+90)) 沒 有 真 正 用 來 執 行 使 用 者 工 作 而 浪 費 排 程 工 作 23 排 程 器 長 程 排 程 器 就 可 能 幾 分 鐘 才 執 行 一 次, 有 足 夠 時 間 選 出 一 組 對 系 統 最 好 的 行 程, 以 系 統 資 源 使 用 程 度 來 看, 可 將 行 程 分 成 以 I/O 為 主 及 CPU 為 主 長 程 排 程 器 控 制 整 個 系 統 多 工 的 程 度 同 時 有 幾 個 行 程 被 放 於 記 憶 體 I/O 為 主 的 行 程 是 指 執 行 期 間 花 在 I/O 上 的 時 間 比 花 在 計 算 上 的 時 間 長 CPU 為 主 的 行 程 則 相 反 如 果 系 統 如 果 都 存 在 某 一 類 型 的 行 程, 其 效 能 都 比 較 差 24 12

排 程 器 如 果 系 統 都 是 I/O 為 主 的 行 程, 則 大 部 分 的 行 程 都 停 留 在 I/O 的 等 待 佇 列 等 待 I/O 完 成, 而 就 緒 佇 列 卻 經 常 是 空 的, 造 成 CPU 的 利 用 率 很 低 如 果 系 統 都 是 CPU 為 主 的 行 程, I/O 的 等 待 佇 列 大 部 分 是 空 的, 所 以 I/O 裝 置 閒 置 不 用 25 排 程 器 這 兩 種 狀 況 都 造 成 系 統 資 源 分 配 不 平 均, 並 降 低 整 體 效 能, 如 何 挑 出 兩 者 比 例 合 適 的 工 作, 就 是 長 程 排 程 器 最 重 要 的 課 題, 但 是 很 難, 因 為 行 程 未 執 行 前, 系 統 很 難 預 測 它 到 底 是 屬 於 哪 一 類 型 的 行 程, 若 對 系 統 所 有 行 程 的 執 行 行 為 做 分 析 而 進 行 長 程 排 程, 這 對 系 統 整 體 效 能 會 有 相 當 正 面 的 影 響 26 13

排 程 器 一 般 作 業 系 統 已 無 長 程 排 程 器, 分 時 系 統 上 至 少 每 個 行 程 有 一 部 分 放 在 記 憶 體 中, 然 後 用 短 程 排 程 器 來 排 程, 這 樣 的 系 統 受 限 於 記 憶 體 大 小 及 終 端 機 數 目 上 限 等, 使 用 者 可 憑 感 覺 來 推 判 效 能 的 高 低, 當 系 統 反 應 時 間 超 出 使 用 者 可 容 忍 範 圍, 使 用 者 可 選 擇 離 開 系 統 或 是 移 除 一 些 不 必 要 的 行 程 27 排 程 器 中 程 排 程 器 最 主 要 的 用 途 在 於 降 低 系 統 多 工 的 程 度, 以 增 加 系 統 可 用 記 憶 體 的 大 小 中 程 排 程 器 將 依 些 行 程 從 記 憶 體 暫 時 移 除, 在 一 段 時 間 後 某 些 行 程 會 再 度 被 載 回 記 憶 體 ( 就 緒 佇 列 ) 中 準 備 執 行, 這 種 動 作 稱 為 置 換 (swapping in/out) 28 14

行 程 的 建 立 與 結 束 不 同 行 程 在 系 統 中 可 以 同 時 執 行, 而 且 必 須 能 動 態 地 被 建 立 與 刪 除, 如 此 才 能 有 效 地 運 用 或 共 享 系 統 資 源 來 完 成 系 統 的 目 標 如 何 有 效 地 建 立 和 刪 除 行 程 也 是 影 響 作 業 系 統 效 能 的 重 要 因 素 29 行 程 的 建 立 一 個 行 程 能 在 執 行 的 期 間 透 過 系 統 呼 叫 建 立 很 多 新 的 行 程 建 立 新 行 程 的 行 程 稱 為 父 行 程, 而 新 建 立 的 行 程 稱 為 子 行 程, 可 將 行 程 間 的 關 係 看 為 行 程 樹 父 行 程 建 立 了 子 行 程 後, 子 行 程 可 以 直 接 取 得 父 行 程 的 資 源 來 使 用, 也 可 能 只 取 用 其 中 一 部 份, 就 父 行 程 而 言, 需 將 部 分 資 源 ( 記 憶 體 或 檔 案 ) 與 子 行 程 分 享 30 15

行 程 的 建 立 UNIX 系 統 中, 使 用 行 程 代 號 (PID) 來 分 辦 不 同 的 行 程,PID 是 獨 一 無 二 的 行 程 身 分 證 明 系 統 呼 叫 fork(): 新 行 程 會 複 製 父 行 程 的 位 址 空 間, 子 行 程 中 fork() 傳 回 值 為 0, 父 行 程 的 回 傳 值 則 為 子 行 程 的 PID execlp(): 將 程 式 的 執 行 檔 載 入 記 憶 體, 並 用 程 式 的 內 容 覆 蓋 舊 程 式 的 記 憶 體 空 間, 然 後 開 始 執 行 wait(): 父 行 程 若 沒 有 其 他 工 作 要 做, 則 將 自 己 從 準 備 佇 列 移 到 等 待 佇 列, 等 待 下 一 次 被 排 程 器 選 出 來 執 行 或 是 子 行 程 執 行 結 束 31 if ((pid = fork()) == 0) { // child process execlp( execfile ); } else { // father process } 行 程 的 建 立 32 16

行 程 的 產 生 在 一 個 行 程 的 執 行 期 間, 它 可 以 利 用 產 生 行 程 的 系 統 呼 叫 來 產 生 數 個 新 的 行 程 原 先 的 行 程 就 叫 做 父 行 程, 而 新 的 行 程 則 叫 做 子 行 程 每 一 個 新 產 生 的 行 程 可 以 再 產 生 其 它 的 行 程, 這 可 以 形 成 一 幅 行 程 樹 33 行 程 的 產 生 34 17

行 程 樹 root keventd kswapd init_task ypbind bash crond 35 行 程 的 結 束 一 個 行 程 在 結 束 最 後 一 個 指 令 會 利 用 exit() 請 求 作 業 系 統 將 自 己 從 系 統 中 移 除, 執 行 期 間 用 到 的 資 源 如 實 體 記 憶 體 虛 擬 記 憶 體 開 啟 的 檔 案 和 使 用 的 I/O 裝 置 等, 都 會 交 還 給 作 業 系 統 除 自 己 正 常 結 束 外, 行 程 也 可 以 透 過 abort() 強 迫 另 一 個 行 程 結 束 執 行 通 常 只 有 父 行 程 才 能 使 用 此 系 統 呼 叫 去 中 斷 子 行 程 36 18

行 程 的 結 束 父 行 程 使 用 wait() 等 待 子 行 程 結 束, 而 子 行 程 用 exit() 結 束 執 行, 子 行 程 結 束 後, 作 業 系 統 則 呼 叫 wait() 傳 回 結 束 執 行 的 子 行 程 PID, 如 此 父 行 程 就 可 知 道 是 哪 個 子 行 程 結 束 了 如 果 父 行 程 結 束, 則 它 所 有 的 子 行 程 都 會 被 作 業 系 統 結 束 或 是 交 由 另 一 特 定 行 程 (init) 代 管, 在 UNIX 系 統 中 若 沒 有 父 行 程, 作 業 系 統 根 本 不 知 道 要 向 誰 回 報 子 行 程 的 結 束 狀 態 fork(95tpu 95ncu), wait, join(thread), exit?? ps top kill(97nttu) 37 #include <sys/types.h> #include <stdio.h> #include <unistd.h> int main() { pid_t pid; pid=fork(); if (pid == 0) execlp( /bin/ls, ls, NULL); } else { // father process wait(null); execlp( /bin/date, date, NULL); fprintf(stderr, Child Complete ); exit(0); } 38 19

39 #include <stdio.h> #include <windows.h> int main(void) { // dev-c++ STARTUPINFO si; PROCESS_INFORMATION pi; ZeroMemory(&si, sizeof(si)); si.cb=sizeof(si); ZeroMemory(&pi, sizeof(pi)); if (!CreateProcess(NULL,"c:\\WINDOWS\\system32\\mspaint.exe", NULL,NULL,FALSE,0,NULL,NULL, &si, &pi)) { fprintf(stderr,"create fail"); return -1; } if (!CreateProcess(NULL,"c:\\WINDOWS\\system32\\notepad.exe", NULL,NULL,FALSE,0,NULL,NULL, &si, &pi)) { fprintf(stderr,"create fail"); return -1; } WaitForSingleObject(pi.hProcess, INFINITE); printf("child complete"); CloseHandle(pi.hProcess); CloseHandle(pi.hThread); } 40 20

執 行 緒 系 統 呼 叫 fork() 的 缺 點 系 統 呼 叫 fork(), 會 複 製 父 行 程 的 位 址 空 間, 需 要 做 大 量 記 憶 體 的 複 製 進 行 內 文 切 換 時 需 付 出 相 當 的 代 價 兩 個 行 程 因 各 自 擁 有 自 己 的 位 址 空 間, 無 法 直 接 進 行 溝 通 (IPC), 需 透 過 資 源 共 享 機 制 如 共 享 記 憶 體 或 是 訊 息 傳 遞 若 行 程 間 可 以 共 用 一 部 分 的 記 憶 體 空 間, 那 麼 額 外 的 負 擔 就 能 減 少, 這 也 就 是 建 立 執 行 緒 的 基 本 理 由 41 執 行 緒 觀 念 執 行 緒 輕 量 級 行 程 (LWP) 使 用 CPU 資 源 的 基 本 單 元 包 含 了 一 個 程 式 計 數 器 一 組 暫 存 器 和 一 個 堆 疊 空 間 與 其 他 的 執 行 緒 共 用 同 一 個 位 址 空 間, 共 享 程 式 區 段 資 料 區 段 和 從 作 業 系 統 取 得 的 資 源 ( 開 啟 檔 案 及 信 號 ) 傳 統 的 行 程 重 量 級 行 程 (HWP) 可 看 成 是 只 有 一 個 執 行 緒 在 執 行 的 行 程 42 21

傳 統 行 程 與 執 行 緒 行 程 程 式 資 料 檔 案 程 式 資 料 檔 案 暫 存 器 堆 疊 暫 存 器 暫 存 器 堆 疊 堆 疊 執 行 緒 執 行 緒 單 執 行 緒 ( 傳 統 行 程 ) 多 執 行 緒 43 執 行 緒 的 優 點 大 部 份 應 用 程 式 都 是 多 執 行 緒 的 架 構 使 用 執 行 緒 來 取 代 傳 統 行 程 有 幾 項 優 點 : 資 源 共 享 容 易 : 不 需 透 過 行 程 溝 通 機 制 ( 共 享 記 憶 體 或 是 訊 息 傳 遞 ) 就 能 直 接 交 換 資 料, 節 省 溝 通 的 額 外 負 擔 節 省 記 憶 體 空 間 : 系 統 呼 叫 fork() 會 複 製 一 份 與 父 行 程 內 容 相 同 的 位 址 空 間 給 子 行 程, 造 成 浪 費, 執 行 緒 不 需 要 複 製 所 有 的 位 址 空 間 44 22

執 行 緒 的 優 點 (94ncu) 使 用 執 行 緒 來 取 代 傳 統 行 程 有 幾 項 優 點 : 快 速 的 內 文 切 換 : 執 行 緒 只 需 存 一 個 程 式 計 數 器 一 組 暫 存 器 和 一 個 堆 疊 空 間, 而 行 程 還 需 加 上 如 位 址 空 間 的 儲 存 平 行 處 理 : 若 有 多 個 CPU, 執 行 緒 可 以 提 升 整 個 系 統 的 效 能, 若 兩 個 執 行 緒 沒 有 相 依 性, 此 二 執 行 緒 可 同 時 在 不 同 的 CPU 上 執 行 ( 格 網 運 算 ) 45 使 用 者 和 核 心 執 行 緒 (92tku 97tku 96ncu 93tpu 94tpu 94nttu) 在 作 業 系 統 中, 有 兩 種 方 式 來 支 援 執 行 緒 使 用 者 執 行 緒 利 用 執 行 緒 函 式 庫 來 提 供 的, 建 構 在 核 心 之 上, 但 不 經 由 核 心 直 接 支 援 建 立 結 束 與 排 程 都 在 使 用 者 空 間 完 成, 系 統 核 心 並 不 知 道 使 用 者 執 行 緒 的 存 在, 如 此 使 得 使 用 者 執 行 緒 在 建 立 與 管 理 時 比 較 有 效 率 若 行 程 中 的 執 行 緒 因 系 統 呼 叫 而 暫 停, 則 同 行 程 中 其 他 所 有 執 行 緒 也 都 會 暫 停 執 行 常 見 的 使 用 者 執 行 緒 函 式 庫 包 括 :POSIX Pthreads(94tpu) Mach C-threads Solaris threads 46 23

使 用 者 和 核 心 執 行 緒 在 作 業 系 統 中, 有 兩 種 方 式 來 支 援 執 行 緒 核 心 執 行 緒 由 作 業 系 統 直 接 支 援 建 立 結 束 排 程 等 都 在 核 心 空 間 完 成, 需 要 從 使 用 者 空 間 轉 換 至 核 心 空 間, 所 以 建 立 與 管 理 執 行 緒 時 比 使 用 者 執 行 緒 來 得 慢 由 於 直 接 由 核 心 管 理, 若 行 程 中 的 執 行 緒 暫 停, 核 心 可 以 安 排 其 他 在 同 行 程 中 的 執 行 緒 繼 續 執 行, 在 多 CPU 的 執 行 環 境 下, 核 心 可 以 安 排 不 同 的 執 行 緒 在 不 同 的 CPU 上 執 行, 以 充 分 利 用 系 統 資 源 47 多 執 行 緒 的 模 型 實 作 執 行 緒 時 通 常 有 三 種 模 型 (96tpu) 多 對 一 模 型 : 將 許 多 個 使 用 者 執 行 緒 對 應 到 同 一 個 核 心 執 行 緒, 執 行 緒 在 使 用 者 空 間 執 行, 所 以 執 行 緒 的 建 立 和 管 理 速 度 都 很 快, 如 果 行 程 中 某 執 行 緒 暫 停 執 行, 那 麼 整 個 行 程 的 所 有 執 行 緒 都 會 暫 停, 同 一 時 間 內 只 有 一 個 執 行 緒 可 以 存 取 核 心, 所 以 在 多 個 CPU 環 境 下, 這 類 模 型 的 執 行 緒 不 能 並 行 地 執 行 若 作 業 系 統 不 支 援 核 心 執 行 緒 但 想 要 實 作 使 用 者 執 行 緒, 也 可 以 使 用 多 對 一 的 模 型 48 24

多 對 一 模 型 使 用 者 執 行 緒 核 心 執 行 緒 49 多 執 行 緒 的 模 型 實 作 執 行 緒 時 通 常 有 三 種 模 型 一 對 一 模 型 : 將 一 個 使 用 者 執 行 緒 對 應 到 一 個 核 心 執 行 緒, 比 多 對 一 模 型 提 供 更 多 並 行 處 理 的 能 力, 當 行 程 中 的 執 行 緒 暫 停 執 行, 其 他 執 行 緒 還 能 繼 續 執 行, 而 且 此 模 型 允 許 多 個 執 行 緒 同 時 在 多 個 CPU 上 並 行 執 行, 此 模 型 缺 點 是 每 當 產 生 一 個 新 的 使 用 者 執 行 緒 時, 必 須 產 生 相 對 的 核 心 執 行 緒, 如 此 造 成 系 統 額 外 的 負 擔, 使 用 此 模 型 時, 大 都 會 限 制 系 統 最 大 執 行 緒 數 目 50 25

一 對 一 模 型 使 用 者 執 行 緒 核 心 執 行 緒 核 心 執 行 緒 核 心 執 行 緒 51 多 執 行 緒 的 模 型 實 作 執 行 緒 時 通 常 有 三 種 模 型 多 對 多 模 型 : 將 使 用 者 執 行 緒 對 應 到 相 同 或 是 較 少 數 目 的 核 心 執 行 緒, 有 些 應 用 程 式 會 需 要 一 定 數 量 的 執 行 緒, 雖 然 多 對 一 模 型 可 以 滿 足, 但 在 同 一 時 間 內 各 個 執 行 緒 無 法 並 行 地 執 行, 若 使 用 一 對 一 模 型, 程 式 設 計 師 必 須 小 心 地 設 計 程 式, 不 能 在 程 式 中 產 生 過 多 核 心 執 行 緒 而 增 加 太 多 額 外 負 擔, 若 利 用 多 對 多 模 型, 程 式 設 計 師 可 以 產 生 自 己 所 需 數 目 的 使 用 者 執 行 緒, 相 對 的 核 心 執 行 緒 也 可 以 在 多 CPU 的 環 境 下 並 行 地 執 行 52 26

多 對 多 模 型 使 用 者 執 行 緒 核 心 執 行 緒 核 心 執 行 緒 核 心 執 行 緒 53 行 程 合 作 (IPC)(96nttu 92nttu) 當 多 個 行 程 同 時 在 一 個 系 統 中 執 行 時, 可 能 會 形 成 : 多 個 獨 立 的 行 程 - 指 行 程 之 間 沒 有 任 何 共 享 的 資 料 一 些 合 作 的 行 程 - 指 行 程 之 間 有 共 享 的 資 料, 為 達 此 目 的 作 業 系 統 提 供 一 些 方 法, 來 支 援 行 程 間 的 溝 通 或 進 行 行 程 間 的 同 步 54 27

合 作 行 程 間 通 訊 合 作 行 程 (cooperating process) 資 訊 共 享 : 因 為 數 個 使 用 者 可 能 對 相 同 的 資 訊 ( 例 如 : 公 用 檔 案 ) 有 興 趣, 因 此 必 須 提 供 一 個 環 境 允 許 使 用 者 能 同 時 使 用 這 些 資 源 加 速 運 算 : 如 果 希 望 某 一 特 定 工 作 執 行 快 一 點, 則 可 以 分 成 一 些 子 工 作, 每 一 個 子 工 作 都 可 以 和 其 它 子 工 作 平 行 地 執 行 ( 多 CPU) 模 組 化 : 希 望 以 模 組 的 方 式 來 建 立 系 統, 把 系 統 功 能 分 配 到 數 個 行 程 方 便 性 : 即 使 是 單 一 使 用 者 也 可 能 同 時 執 行 數 項 工 作 55 合 作 行 程 間 通 訊 56 28

合 作 行 程 間 通 訊 - Mach 在 訊 息 式 (94nttu) 的 作 業 系 統 例 子 中, 考 慮 由 Carnegie Mellon 大 學 所 發 展 出 的 Mach 作 業 系 統 Mach 核 心 支 援 多 元 任 務 的 產 生 和 刪 除, 這 些 任 務 類 似 於 行 程, 但 具 有 多 重 的 控 制 執 行 緒 Mach 中 大 部 份 的 通 訊 ( 包 括 大 部 份 系 統 呼 叫 和 所 有 任 務 之 間 的 資 訊 ) 都 是 由 訊 息 完 成 訊 息 都 是 由 信 箱 ( 在 Mach 中 乃 稱 為 埠,port) 來 傳 送 及 接 收 57 合 作 行 程 間 通 訊 - Windows XP Windows XP 作 業 系 統 是 現 代 設 計 的 一 個 例 子, 它 採 用 模 組 化 設 計 以 便 增 進 功 能 和 降 低 製 作 新 特 性 所 需 的 時 間 Windows Xp 提 供 多 元 操 作 環 境 的 支 援, 或 是 經 由 一 個 訊 息 傳 遞 的 功 能 完 成 應 用 程 式 之 連 結 的 子 系 統 這 些 應 用 程 式 可 以 視 為 WindowsXP 系 統 伺 服 器 的 委 託 人 58 29

遠 程 程 序 呼 叫 (RPC) 59 遠 端 方 法 呼 叫 (RMI) 60 30

遠 端 方 法 呼 叫 (RMI) 61 共 享 緩 衝 區 典 型 行 程 合 作 的 問 題 : 生 產 者 - 產 生 資 訊 給 消 費 者 消 費 者 - 消 耗 生 產 者 所 產 生 的 資 訊 當 生 產 者 和 消 費 者 同 時 執 行 時, 需 要 有 一 個 共 享 緩 衝 區 給 生 產 者 存 放 產 品, 以 提 供 給 消 費 者 使 用, 此 二 行 程 的 動 作 必 須 同 步, 才 不 會 造 成 當 緩 衝 區 滿 了, 生 產 者 還 繼 續 生 產, 緩 衝 區 空 了, 消 費 者 還 繼 續 消 費 62 31

緩 衝 區 緩 衝 區 可 分 為 : 無 限 緩 衝 區 緩 衝 區 大 小 沒 有 限 制, 生 產 者 不 用 擔 心 緩 衝 區 會 不 夠 用, 但 消 費 者 在 緩 衝 區 空 了 的 時 候 要 等 待 新 產 生 的 資 料 到 達 才 能 開 始 動 作 有 限 緩 衝 區 緩 衝 區 大 小 有 限 制, 緩 衝 區 滿 了 生 產 者 必 須 暫 停 生 產, 當 緩 衝 區 空 了 消 費 者 必 須 等 待 直 到 緩 衝 區 有 資 料, 才 能 進 行 資 料 取 得 的 動 作 緩 衝 區 由 作 業 系 統 提 供 的 IPC 機 制 來 產 生, 或 是 直 接 經 由 程 式 設 計 師 在 程 式 中 使 用 共 享 記 憶 體 的 機 制 來 進 行 63 生 產 者 與 消 費 者 的 例 子 使 用 共 享 記 憶 體 機 制 生 產 者 及 消 費 者 的 行 程 共 享 了 下 列 的 變 數 : #define BUF_SIZE n int iin = 0, iout = 0 user_def_type buffer[buf_size] 這 個 例 子 中 同 時 最 多 只 能 使 用 到 n-1 個 緩 衝 區 的 空 間 why? 64 32

生 產 者 與 消 費 者 的 例 子 iin 代 表 緩 衝 區 內 下 一 個 可 放 資 料 的 位 置, 及 生 產 者 下 一 個 可 存 放 資 料 的 位 置 iout 代 表 緩 衝 區 內 最 先 可 用 位 置 若 iin=iout 代 表 緩 衝 區 是 空 的,(iIn+1)%BUF_SIZE=iOut 代 表 緩 衝 區 已 滿 why? 65 生 產 者 do { 產 生 一 個 型 別 為 user_def_type 的 資 料 並 存 放 於 nextp, nextp 為 生 產 行 程 內 的 區 域 變 數 /* 若 緩 衝 區 己 滿 則 等 待 */ while ((iin + 1) % BUF_SIZE == iout) ; ; buffer[iin] = nextp; iin = (iin + 1) % BUF_SIZE; } while (True); 66 33

消 費 者 do { while (iin = iout) ; /* 若 緩 衝 區 為 空 則 等 待 */ ; nextc = buffer[iout]; iout = (iout + 1) % BUF_SIZE; 將 存 於 nextc 的 資 料 消 耗 掉, nextc 為 消 費 行 程 內 的 區 域 變 數 } while (True); 67 行 程 間 溝 通 共 享 記 憶 體 利 用 一 塊 行 程 間 共 享 的 緩 衝 區 來 進 行 合 作 的 溝 通, 而 溝 通 的 方 式 完 全 由 程 式 設 計 師 自 行 設 計 行 程 間 溝 通 (IPC) 由 作 業 系 統 提 供 IPC 包 含 了 一 些 機 制, 讓 行 程 與 行 程 間 能 夠 進 行 溝 通 與 同 步 訊 息 傳 遞 系 統 是 相 當 基 本 的 IPC 機 制, 行 程 間 可 建 立 溝 通 管 道 來 進 行 同 步 或 資 料 共 享, 不 必 使 用 相 同 的 位 址 空 間 共 享 記 憶 體 或 是 IPC 機 制 是 可 以 同 時 使 用 68 34

基 本 架 構 行 程 間 溝 通 (IPC) 為 作 業 系 統 所 提 供 用 來 達 到 行 程 間 資 料 交 換 與 共 享 的 機 制 IPC 通 常 會 提 供 兩 個 函 式 : send() - 傳 送 訊 息 receive() - 接 收 訊 息 行 程 在 傳 送 訊 息 時 可 有 兩 種 選 擇 : 固 定 大 小 的 訊 息 可 變 大 小 的 訊 息 固 定 大 小 訊 息 在 系 統 實 作 時 比 較 簡 單, 但 這 限 制 會 讓 程 式 設 計 較 為 複 雜, 因 程 式 設 計 者 需 自 行 處 理 超 過 固 定 大 小 的 訊 息 69 基 本 架 構 可 變 大 小 訊 息 在 系 統 實 作 時 比 較 複 雜, 但 會 使 程 式 設 計 較 為 簡 單 且 有 彈 性 行 程 間 在 溝 通 時 會 建 立 一 條 通 訊 鏈 結 透 過 鏈 結 send() 和 receive() 就 可 以 傳 送 和 接 收 訊 息 實 作 上 要 考 慮 的 問 題 包 括 : 鏈 結 是 否 可 以 共 享 給 2 個 以 上 的 行 程 使 用? 訊 息 大 小 應 是 固 定 大 小 還 是 可 變 大 小? 鏈 結 是 單 向 ( 只 能 傳 送 或 是 接 收 ) 的 還 是 雙 向 的? 70 35

基 本 架 構 實 作 傳 送 與 接 收 功 能 時 有 幾 種 方 法 : 直 接 或 間 接 的 溝 通 對 稱 或 非 對 稱 溝 通 傳 送 複 製 或 只 傳 送 參 考 71 直 接 溝 通 每 個 行 程 要 與 其 他 行 程 進 行 溝 通 時, 必 須 要 明 確 地 指 出 訊 息 傳 送 的 目 的 地 或 接 收 訊 息 的 來 源 send(a, message) /* 傳 送 訊 息 給 A 行 程 */ receive(b, message) /* 從 B 行 程 接 收 訊 息 */ 鏈 結 的 特 性 是 兩 個 行 程 在 進 行 溝 通 時 雙 方 必 須 要 知 道 對 方 的 身 分, 一 個 鏈 結 只 會 有 兩 個 行 程 參 與, 且 鏈 結 通 常 是 雙 向 的 生 產 者 產 生 一 新 的 資 料 後 會 呼 叫 send(), 消 費 者 要 消 耗 一 份 資 料 時 會 呼 叫 receive() 72 36

直 接 溝 通 ( 續 ) 使 用 IPC 機 制 程 式 較 容 易 撰 寫 ( 比 對 Slice 66) do {. /* 生 產 者 產 生 新 的 資 料 p_product */ send( 消 費 者, p_product); } while (True); 生 產 者 行 程 do { receive( 生 產 者, c_product); /* 消 費 者 消 耗 c_product */ } while (True); 消 費 者 行 程 73 直 接 溝 通 可 分 為 對 稱 與 非 對 稱, 而 send() 和 receive() 分 別 被 定 義 成 對 稱 發 送 端 與 接 收 端 必 須 互 相 指 定 對 方 的 名 字 send(a, message) /* 傳 送 訊 息 給 A 行 程 */ receive(b, message) /* 從 B 行 程 接 收 訊 息 */ 非 對 稱 只 有 發 送 端 需 指 定 對 方 的 名 字 而 接 收 端 則 不 需 要 send(a, message) /* 傳 送 訊 息 給 A 行 程 */ receive(id, message) /* 從 任 何 一 個 行 程 接 收 一 個 訊 息 其 中 id 這 個 變 數 代 表 正 在 與 接 收 端 進 行 溝 通 的 行 程 */ 74 37

直 接 溝 通 兩 者 皆 有 相 同 的 缺 點, 行 程 的 名 稱 若 改 變 了, 則 必 須 把 所 有 參 考 到 這 的 行 程 的 參 照 一 一 更 新, 此 舉 會 造 成 維 護 程 式 的 額 外 負 擔 75 間 接 溝 通 訊 息 的 傳 送 與 接 收 是 透 過 信 箱 來 完 成 每 個 信 箱 都 有 一 個 獨 一 無 二 的 編 號, 行 程 可 透 過 不 同 信 箱 編 號 與 其 他 數 個 行 程 進 行 溝 通 send() 與 receive() 可 定 義 為 send(a, message) /* 傳 送 一 個 訊 息 到 A 信 箱 */ receive(a, message) /* 從 A 信 箱 接 收 一 個 訊 息 */ 兩 個 行 程 溝 通 時, 他 們 一 定 共 用 相 同 的 信 箱, 鏈 結 可 以 同 時 給 數 個 行 程 使 用, 而 且 可 以 是 單 向 或 是 雙 向 76 38

間 接 溝 通 行 程 A 呼 叫 send(x, message), 行 程 B C 又 呼 叫 receive(x, message)? 多 個 行 程 同 時 共 用 相 同 的 信 箱, 若 多 個 行 程 同 時 接 收 訊 息, 那 個 行 程 會 收 到 訊 息? 同 時 只 允 許 兩 個 行 程 共 享 信 箱 同 時 只 允 許 一 個 行 程 呼 叫 receive() 交 給 作 業 系 統, 讓 作 業 系 統 決 定 由 誰 得 到 訊 息 77 間 接 溝 通 信 箱 擁 有 者 可 以 是 一 個 行 程 或 是 作 業 系 統, 每 個 信 箱 都 有 唯 一 的 擁 有 者, 當 一 個 擁 有 者 行 程 結 束 時, 信 箱 也 跟 著 被 銷 毀, 若 被 銷 毀 的 信 箱 還 有 其 他 行 程 傳 送 訊 息 給 這 個 信 箱, 則 這 些 傳 送 訊 息 的 行 程 必 須 被 告 之 此 信 箱 已 經 不 存 在 78 39

間 接 溝 通 行 程 宣 告 一 個 型 別 為 mailbox 的 變 數, 即 表 示 擁 有 此 信 箱, 其 他 知 道 此 信 箱 名 稱 的 行 程 就 是 信 箱 的 使 用 者 若 信 箱 數 於 作 業 系 統, 則 作 業 系 統 必 須 提 供 一 些 方 法 給 行 程, 允 許 行 程 去 : 建 立 一 個 新 的 信 箱 透 過 信 箱 去 傳 送 和 接 收 訊 息 銷 毀 一 個 信 箱 79 間 接 溝 通 透 過 作 業 系 統 建 立 信 箱 的 行 程 即 信 箱 的 擁 有 者, 一 開 始 只 有 信 箱 的 擁 有 者, 可 以 透 過 該 信 箱 接 收 訊 息 行 程 A 建 立 信 箱 M, 行 程 A 呼 叫 fork() 建 立 一 個 新 的 行 程 B, 行 程 A 與 B 即 共 享 信 箱 M 信 箱 銷 毀 後, 所 有 對 此 信 箱 存 取 的 行 程 就 不 能 再 用, 且 作 業 系 統 必 須 回 收 信 箱 所 使 用 的 資 源, 並 作 後 續 處 理 如 轉 信 到 新 信 箱 等 80 40

同 步 行 程 間 可 透 過 send() 與 receive() 來 進 行 同 步 實 作 send() 與 receive() 時, 可 為 阻 隔 式 發 送 : 發 送 訊 息 的 行 程 將 會 被 阻 隔, 直 到 訊 息 被 接 收 端 或 信 箱 收 到 為 止, 才 可 執 行 下 一 個 動 作 非 阻 隔 式 發 送 : 發 送 訊 息 的 行 程 於 送 出 訊 息 後, 馬 上 可 繼 續 執 行 下 一 個 動 作 (UDP) 阻 隔 式 接 收 : 接 收 端 的 行 程 將 會 被 阻 隔, 直 到 收 到 訊 息 才 可 執 行 下 一 個 動 作 非 阻 隔 式 接 收 : 接 收 端 的 行 程 不 論 收 到 訊 息 與 否, 都 可 以 執 行 下 一 個 動 作 當 send() 與 receive() 皆 為 阻 隔 式 時, 發 送 端 與 接 收 端 之 間 就 會 是 同 步 的 81 緩 衝 一 個 鏈 結 中, 可 能 設 置 緩 衝 區 來 暫 時 儲 存 正 在 鏈 結 中 傳 遞 的 訊 息, 一 般 是 用 訊 息 佇 列 來 實 作 實 作 訊 息 佇 列 時 可 使 用 下 列 幾 種 方 法 : 無 緩 衝 : 正 在 傳 遞 的 訊 息 會 停 留 在 鏈 結 中, 發 送 端 必 須 等 待 接 收 端 接 收 到 資 料, 才 能 繼 續 傳 送 下 一 個 訊 息, 發 送 端 與 接 收 端 是 同 步 有 限 緩 衝 : 鏈 結 中 緩 衝 區 最 多 只 有 n 個 訊 息, 發 送 端 若 緩 衝 區 沒 滿, 可 以 繼 續 傳 送 訊 息, 不 需 等 待 接 收 端 迴 應 接 收 到 資 料, 但 若 緩 衝 區 已 滿, 則 必 須 等 待 緩 衝 區 有 空 的 位 置 才 能 發 送 訊 息 無 限 緩 衝 : 鏈 結 中 緩 衝 區 沒 有 大 小 限 制, 無 論 訊 息 多 少 都 可 以 存 在 緩 衝 區, 發 送 端 不 需 等 待 緩 衝 區, 隨 時 可 以 傳 送 82 41

緩 衝 使 用 有 緩 衝 的 訊 息 佇 列 時, 若 行 程 間 需 要 同 步 則 需 另 外 處 理 行 程 A 送 訊 息 給 行 程 B, 行 程 A 必 須 等 待 行 程 B 收 到 訊 息 才 能 繼 續 執 行 同 步 行 程 A:send(B,msg); receive(b, msg); 行 程 B:receive(A, msg); send(a, ACK ); 83 例 外 狀 況 在 分 散 式 系 統 中, 行 程 在 進 行 溝 通 出 現 錯 誤 的 機 率 會 比 在 單 一 機 器 上 來 得 高, 因 為 分 散 式 系 統 相 對 較 為 複 雜 在 單 一 機 器 環 境 下, 訊 息 傳 遞 會 用 共 享 記 憶 體 來 實 作, 若 有 一 錯 誤 產 生, 整 個 系 統 皆 會 受 到 影 響 在 分 散 式 的 環 境 下, 若 一 個 訊 息 在 傳 遞 過 程 發 生 錯 誤, 這 個 錯 誤 不 一 定 會 影 響 整 個 系 統 的 運 作 84 42

例 外 狀 況 無 論 在 單 一 機 器 或 是 分 散 式 的 環 境 都 需 要 有 錯 誤 回 覆 的 機 制 將 系 統 回 復 正 常 運 作, 例 外 處 理 就 是 用 來 處 理 各 種 例 外 狀 況 的 一 種 錯 誤 回 復 機 制 85 例 外 狀 況 當 下 列 狀 況 發 生 時, 系 統 可 能 需 要 進 行 錯 誤 的 回 復 : 行 程 結 束 : 無 論 是 傳 送 端 或 是 接 收 端, 都 有 可 能 在 未 完 成 前 不 正 常 地 結 束, 這 產 生 訊 息 遺 失 或 是 行 程 在 等 待 永 遠 不 會 被 發 送 的 訊 息 如 此 會 有 兩 種 問 題 : 行 程 A 在 等 待 行 程 B 送 來 的 訊 息, 但 行 程 B 已 經 結 束 OS 應 將 行 程 A 結 束, 或 通 知 行 程 A 行 程 B 已 經 結 束 行 程 A 傳 送 訊 息 給 已 經 結 束 的 行 程 B, 若 行 程 A 需 要 知 道 行 程 B 是 否 已 經 收 到 訊 息, 那 麼 行 程 A 必 須 要 等 待 行 程 B 的 回 覆 有 緩 衝 則 沒 問 題, 否 則 若 以 阻 隔 式 發 送 的 行 程 將 會 被 永 遠 隔 絕 86 43

例 外 狀 況 訊 息 遺 失 : 訊 息 被 傳 送 過 程 很 有 可 能 會 遺 失, 造 成 遺 失 的 可 能 原 因 有 很 多, 通 常 是 硬 體 或 網 路 壅 塞, 此 時 有 些 基 本 的 處 理 方 法 : 由 OS 來 負 責 偵 測 此 類 問 題, 當 遺 失 訊 息 時 由 OS 自 動 重 送, 但 是 此 法 會 造 成 系 統 負 擔, 且 系 統 不 知 如 何 對 個 別 的 行 程 特 別 處 理 由 發 送 訊 息 的 行 程 來 負 責 偵 測, 若 有 遺 失 訊 息 則 此 行 程 會 自 動 重 送, 但 此 法 會 增 加 行 程 負 擔 與 應 用 程 式 設 計 的 困 難, 且 行 程 也 無 系 統 全 局 的 資 訊 做 特 別 的 處 理 由 OS 來 負 責 偵 測 此 類 問 題, 當 遺 失 訊 息 時 由 OS 不 直 接 重 送, 而 是 通 知 行 程 訊 息 遺 失, 由 行 程 決 定 是 否 該 重 送 87 例 外 狀 況 訊 息 遺 失 的 偵 測 並 不 是 必 要 的 動 作 在 網 路 通 訊 協 定 中 UDP 不 會 做 遺 失 偵 測,TCP 則 會 偵 測 並 保 證 訊 息 的 到 達, 若 訊 息 遺 失 則 會 重 送 遺 失 封 包 可 用 逾 時 的 機 制 (TCP/IP 連 接 網 站 逾 時 內 定 是 多 久? TCP/IP 傳 送 封 包 若 遺 失 最 多 會 重 傳 幾 次 才 宣 告 失 敗?) 88 44

例 外 狀 況 訊 息 的 錯 誤 : 訊 息 被 傳 送 至 目 的 地 時, 訊 息 資 料 有 錯 誤, 這 錯 誤 來 自 外 界 的 干 擾 所 造 成, 例 如 電 磁 波, 這 種 狀 況 與 訊 息 遺 失 類 似, 通 常 OS 會 重 送 訊 息, 檢 查 碼 (CRC? checksum? parity) 通 常 被 用 來 偵 測 這 類 的 錯 誤 (chap. 15 CRC16 CRC32 ECC) 89 同 位 元 偵 錯 法 (Parity) 無 論 什 麼 碼, 在 傳 送 時 都 可 能 產 生 邏 輯 上 的 辨 認 錯 誤, 同 位 元 偵 錯 法 就 是 一 種 能 夠 分 辨 傳 送 碼 有 無 錯 的 方 法, 分 為 偶 同 位 元 (even parity bit) 及 奇 同 位 元 (odd parity bit) 兩 種 編 碼 檢 查 方 式, 做 法 上 是 將 一 個 尚 未 傳 送 的 編 碼, 附 加 上 一 個 額 外 的 位 元, 若 要 整 個 編 碼 內 保 持 偶 數 個 1, 這 個 位 元 就 叫 做 偶 同 位 元, 若 要 整 個 編 碼 內 保 持 奇 數 個 1, 這 個 位 元 就 叫 做 奇 同 位 元 90 45

同 位 元 偵 錯 法 (Parity) 例 如 某 二 進 碼 尚 未 加 入 同 位 元 之 前 為 0100101, 此 碼 內 有 奇 數 個 1, 若 採 用 偶 同 位 元 編 碼, 編 碼 後 為 10100101, 使 其 變 為 偶 數 個 1, 若 採 用 奇 同 位 元 編 碼, 編 碼 後 為 00100101, 使 其 保 持 奇 數 個 1 加 了 同 位 元 的 編 碼 在 傳 送 後, 若 已 與 接 收 端 取 得 偶 同 位 元 或 是 奇 同 位 元 約 定, 接 收 端 可 以 經 由 同 位 元 檢 查 電 路 偵 察 出 目 前 的 傳 送 碼 是 偶 數 個 1 還 是 奇 數 個 1, 進 而 知 道 傳 送 過 程 有 無 產 生 錯 誤 91 摘 要 行 程 簡 介 行 程 就 是 一 個 執 行 中 的 程 式 行 程 的 狀 態 新 建 執 行 等 待 就 緒 終 結 作 業 系 統 中 的 佇 列 就 緒 佇 列 I/O 佇 列 等 待 佇 列 92 46

摘 要 作 業 系 統 中 主 要 的 排 程 器 長 程 排 程 器 短 程 排 程 器 內 文 切 換 將 上 一 個 行 程 的 相 關 資 訊 先 保 存 起 來, 並 且 把 即 將 要 使 用 CPU 的 行 程 的 相 關 資 訊 載 入 系 統 中 執 行 緒 的 概 念 減 少 行 程 間 切 換 所 造 成 的 額 外 負 擔 93 摘 要 同 一 個 行 程 中 的 執 行 緒 共 用 程 式 區 段 資 料 區 段 一 些 從 作 業 系 統 取 得 的 資 源 行 程 同 時 存 在 系 統 中 執 行 時, 可 能 會 是 獨 立 的 行 程 合 作 的 行 程 作 業 系 統 提 供 一 些 方 法 讓 行 程 之 間 能 夠 溝 通 共 享 記 憶 體 訊 息 傳 遞 系 統 94 47