オペレーティングシステム 第 8 回 講 義 内 容 並 行 プログラミング 相 互 排 除 (つづき) 哲 学 者 の 食 事 問 題 メモリ 管 理 と 仮 想 記 憶 主 記 憶 共 有 資 源 としてのメモリ 奈 良 先 端 科 学 技 術 大 学 院 大 学 宮 崎 純 miyazaki@is.naist.jp 1 デッドロック(1) 待 機 グラフ(wait for graph; WFG) ( 例 )t1がt2の 持 つリソースのロック 解 放 を 待 つ デッドロック(deadlock) t1 複 数 のスレッドが 互 いに 他 のスレッドが 持 つリソース のロックの 解 放 を 待 ち 続 ける 状 態 WFG 上 で 有 向 閉 路 (サイクル)が 存 在 する t1 t3 t2 t2 デッドロック(2) デッドロックの 回 避 非 効 率 な 場 合 が 多 い アトミック ロック: 全 てのロックを 同 時 に 取 得 ロックの 順 序 付 け: ロックを 取 る 資 源 に 優 先 順 位 を 付 ける デッドロックの 検 出 WFG 中 の 有 向 閉 路 を 発 見 する( 非 現 実 的 ) タイムアウト(timeout) 一 定 時 間 ロック 待 ちを 行 うと デッドロックが 発 生 したとみなす pthreadライブラリでは 標 準 でpthread_cond_timedwait()が 利 用 可 能 デッドロックの 解 消 デッドロックを 構 成 する1つ 以 上 のスレッドのロックを 解 放 食 事 する 哲 学 者 問 題 定 式 化 5 人 の 哲 学 者 が 食 事 をする 食 事 と 思 考 を 繰 り 返 す 食 事 をするには 以 下 の 手 順 を 行 う 席 の 両 側 にある2 本 のフォー クを 持 ち テーブル 中 央 のパ スタを 食 べる 哲 学 者 は 長 時 間 食 事 をしないと 死 んでしまう P4 F0 P0 F1 P1 条 件 フォークを2 本 とも 持 たないと 食 事 できない 哲 学 者 は 自 分 の 両 隣 のフォークしか 使 えない 2 人 の 哲 学 者 は 同 時 に 同 じフォークを 使 えない 目 標 問 題 :5 人 を 死 なせずに 食 事 を 続 けさせることはできるか? F4 P3 F3 P2 F2 誰 もが 食 事 できない 状 態 になってはいけない 誰 か1 人 が 長 い 間 食 事 できない 状 態 になってはいけな い 1
哲 学 者 をプロセスとして 表 す フォークをセマフォで 表 現 する 自 分 の 右 隣 のフォーク, 次 に 左 側 のフォークを 順 番 に 取 る 試 行 1 デッドロックの 発 生 試 行 1の 問 題 哲 学 者 全 員 が 同 時 に 右 のフォークを 取 る (Wait(Fork(l))を 実 行 する)と 次 の 左 のフォークを 取 る 操 作 (Wait(Fork((l+1)%5)))で 永 久 に 待 たされる 飢 餓 状 態 (Starvation)の 発 生 つまり 哲 学 者 が 全 て 餓 死 ライブロックの 発 生 右 のフォークをWait(Fork(l))で 取 得 後 左 のフォーク を(Fork((l+1)%5)))を 取 得 できなければ 右 のフォー クを 置 き 1 分 休 憩 してから 再 度 同 じ 順 序 でフォークを 取 るよう 変 更 しても 哲 学 者 全 員 が 同 じ 動 作 をすれば 永 久 に 食 事 ができない うまくいきそうな 試 行 哲 学 者 4だけ 別 行 動 を 取 る 0 番 から3 番 の 哲 学 者 は, 右 左 の 順 にフォークを 取 る 4 番 目 の 哲 学 者 だけ, 左 右 の 順 にフォークを 取 る 動 作 するが 4 番 目 の 哲 学 者 だけ 有 利 あるい は 不 利 になったりしないか? 講 義 内 容 並 行 プログラミング 相 互 排 除 哲 学 者 の 食 事 問 題 メモリ 管 理 と 仮 想 記 憶 主 記 憶 共 有 資 源 としてのメモリ 他 の 解 法? ウェイターを1 人 おいて フォークをとる 際 にウェイターに 聞 く 一 度 に 食 事 をするのを4 人 までに 限 定 主 記 憶 の 管 理 コンピュータの 性 能 はメモリ? プロセッサの 演 算 速 度 は? メモリは 安 価 に CPU ディスクは? 記 憶 装 置 の 効 率 利 用 は 極 めて 重 要 な 問 題 高 効 率 で 使 いやすい 主 記 憶 管 理 OSの 大 切 な 役 割 のひとつ いわゆる メインメモリ 一 次 記 憶 装 置 主 記 憶 半 導 体 素 子 (DRAM)を 使 用 高 速 電 気 的 に 読 み 書 き プロセッサに 極 めて 近 い 位 置 に 配 置 HDDやSDD DVDなどは 二 次 記 憶 装 置 外 部 記 憶 装 置 とも 呼 ばれる 低 速 バスなどで 他 のI/O 装 置 と 信 号 を 共 有 2
論 理 的 なメモリのしくみ 読 み 書 き 選 択 アドレス データの 信 号 線 を 持 つ 読 み 書 き 選 択 :データを 読 むのか 書 くのかを 指 示 アドレス:データが 格 納 される 位 置 を 示 す 番 地 データ:0/1で 表 現 されるディジタル 値 物 理 アドレス 主 記 憶 のメモリデバイス 上 のアドレス メモリ 参 照 のためのハードウェアが 使 用 プロセスはOSを 介 してメモリにアクセス プロセスが 使 うアドレス( 仮 想 アドレス)と 実 際 の 主 記 憶 のアドレス( 物 理 アドレス)は 異 なる メモリは 共 有 資 源 メモリ 内 に, 各 プロセスの 領 域 が 割 り 当 てられる ユーザAのプロセス:emacs, gcc ユーザBのプロセス:emacs, firefox 主 記 憶 の 問 題 点 マルチプログラミングが 難 しい メモリ 保 護 機 構 が 必 要 あるプロセスが 他 のプロセスのデータの 破 壊 を 防 止 擬 似 並 行 処 理 が 難 しい メモリ 監 視 機 構 が 必 要 迅 速 にプロセス 切 り 替 え フラグメンテーション 問 題 メモリの 管 理 機 構 が 必 要 メモリの 空 き 領 域 を 有 効 活 用 メモリサイズの 物 理 的 制 限 仮 想 記 憶 機 構 が 必 要 大 きなプログラム/データを 扱 えるようにする 工 夫 共 有 資 源 としてのメモリ(1) 起 動 中 のプロセスの 数 を 数 える 共 有 資 源 としてのメモリ(2) ps aux : 起 動 中 のプロセスを 表 示 : パイプ.パイプ 前 のコマンドの 結 果 を 後 ろのコマン ドの 入 力 に 使 う wc : ワードカウント 行 数 単 語 数 文 字 数 を 表 示 する grep : 引 数 を 含 む 行 を 取 り 出 す 3
共 有 資 源 としてのメモリ(3) プロセスが 使 うメモリもOSが 管 理 OSによるメモリの 割 り 当 て 管 理 メモリの 割 り 当 てや 解 放 はシステムコールで 実 現 brk() mmap()システムコール 使 いにくいので 普 通 はライブラリ 関 数 malloc() free()を 使 用 各 プロセスはメモリを 勝 手 に 使 用 できない 他 のプロセスが 使 用 中 のメモリ 空 間 にはアクセス 禁 止 OSが 各 プロセスの 使 用 メモリ 領 域 を 管 理 する 必 要 メモリの 仮 想 化 ( 抽 象 化 ) プロセスごとに それぞれの 仮 想 アドレス 空 間 を 提 供 各 プロセスがメモリを 占 有 しているように 見 える 各 プロセスは 自 分 の 仮 想 アドレス 空 間 内 を 自 由 に 使 える OSはプロセスがメモリを 使 用 するたびに 物 理 メモリを 少 しずつ 割 り 当 て メモリの 仮 想 化 OSがプロセスに 見 せるメモリ 空 間 を 仮 想 化 する 実 際 に 存 在 する 物 理 メモリ 量 よりも 大 きな 空 間 をプロセスに 見 せ ることが 可 能 ( 仮 想 記 憶 ) 32bit OSの 場 合 32bitのアドレス 空 間 (2 32 B = 4GB) メモリの 仮 想 化 ( 抽 象 化 ) プロセスごとに 専 用 の 仮 想 アドレス 空 間 自 分 のプロセスのメモリ 空 間 に 限 り 読 み 書 き 可 能 各 プロセスがメモリを 占 有 しているように 見 える プロセス1の0 番 地 とプロセス2の0 番 地 は 全 く 別 の 場 所 仮 想 ( 論 理 )アドレス 空 間 プログラムを 書 くときの 利 用 可 能 なメモリの 範 囲 物 理 メモリ 空 間 よりも 大 きなメモリサイズを 提 供 多 数 のプロセスを 動 作 させる 必 要 性 必 要 メモリ 量 は 物 理 メモリ 量 以 上 かもしれない 異 なる 計 算 機 でも 同 じプログラムを 動 作 させる 必 要 性 搭 載 メモリ 量 が 異 なるかもしれない 仮 想 アドレス ある 仮 想 アドレス 空 間 内 で 有 効 なアドレス プログラム/プロセス/スレッドが 使 用 するアドレス 通 常 アドレス( 番 地 ) と 言 うと 仮 想 アドレスのことを 指 す 4
仮 想 アドレスと 仮 想 アドレス 空 間 仮 想 アドレス 空 間 プロセスごとに 用 意 された 仮 想 的 なアドレス 空 間 仮 想 アドレス 空 間 物 理 アドレス 空 間 仮 想 アドレス 空 間 の 大 きさはハードウェアとOSで 決 まる 仮 想 アドレス 空 間 は 互 いに 分 離 プロセスAの9000 番 地 とプロセスBの9000 番 地 は 別 物 他 のプロセス 内 の 仮 想 アドレスを 指 定 することはない プロセスAが 参 照 できるメモリはプロセスAの 仮 想 アドレスのみ プロセス 間 のメモリ 保 護 が 実 現 されている 論 理 アドレスと 物 理 アドレスの 関 係 論 理 アドレス 空 間 全 部 を 物 理 メモリに 割 り 当 てることは 不 可 能 論 理 アドレス 空 間 の 物 理 アドレス 空 間 へのマッピング 各 プロセスの 論 理 アドレスを 物 理 アドレスに 対 応 付 け ある 論 理 アドレスを 参 照 すると 対 応 する 物 理 メモリを 参 照 する 実 際 に 使 っている 部 分 だけが 物 理 メモリに 対 応 付 けられる アドレスマッピングの 実 現 あるプロセスの 論 理 アドレスを 物 理 アドレスに 変 換 する 仕 組 み [プロセスID, 論 理 アドレス 値 ] [ 物 理 アドレス]への 変 換 機 構 アドレス 変 換 のためのハードウェア Memory Management Unit (MMU) メモリ 管 理 ユニット 論 理 アドレスから 物 理 アドレスへの 変 換 OSはプロセスごとにアドレス 変 換 表 ( 対 応 表 )を 管 理 MMUをソフトウェアで 実 現 できるが: メモリ 参 照 ごとにソフトウェアで 変 換 を 行 うので 遅 い メモリ 参 照 のためにメモリ 参 照 をする という 状 態 が 発 生 1アドレス1エントリで 表 を 作 るとサイズが 巨 大 になる 一 定 サイズを1ブロックにまとめる( 通 常 4KBや8KB) このブロックは ページと 呼 ばれる ページテーブル 論 理 - 物 理 アドレスをページ 単 位 で 変 換 ページテーブルでアドレス 変 換 仮 想 ページ 番 号 とページ 内 のオフセット( 相 対 位 置 )で 物 理 アドレスを 計 算 論 理 アドレスと 仮 想 ページの 関 係 論 理 アドレスは 仮 想 ページ 番 号 とページ 内 のオ フセットから 構 成 5
ページテーブルのエントリ 最 下 位 ビットが0( 有 効 )または1( 無 効 )で 2 種 類 に 分 けら れる20ビットのデータ その 他 の 属 性 = 保 護 属 性 読 み 書 き 実 行 の 可 否 許 可 されていない 処 理 はページ 保 護 例 外 で 割 込 み 発 生 アドレス 変 換 のまとめ CPUが 仮 想 アドレスVAのデータを 参 照 する 場 合 : VAの 上 位 20ビットVPNを 取 り 出 し 同 時 に 最 下 位 ビットを 確 認 有 効 だった(0) 場 合 : VPNを 使 ってページテーブルから 物 理 ページ 番 号 PPNを 読 み 出 す PPNとページ 内 アドレスを 使 って 物 理 アドレスを 確 定 アクセスする 無 効 だった(1) 場 合 : ページフォルトを 発 生 させて 割 込 みハンドラへ 飛 ぶ TLB: Translation Lookaside Buffer 各 プロセスのページテーブルは 主 記 憶 上 アドレス 変 換 ごとにページテーブルにアクセスするのは 非 効 率 TLB ページテーブルのエントリの 一 部 ( 数 十 ~ 数 百 程 度 )をMMU 内 の TLBにキャッシュ アドレスの 変 換 を 高 速 化 プログラムの 参 照 の 局 所 性 を 利 用 時 間 的 局 所 性 : 近 い 将 来 再 び 参 照 される 可 能 性 が 高 い 空 間 的 局 所 性 : 近 傍 のリソースが 参 照 される 可 能 性 が 高 い 逐 次 的 局 所 性 : 逐 次 アクセスされる 可 能 性 が 高 い 多 階 層 ページテーブル 多 くの 場 合 仮 想 アドレス 空 間 は 疎 4Gバイト(32ビット)のページテーブルは100 万 エントリ しかし 実 際 は 数 Mバイト( 数 千 エントリ)のみを 使 用 多 階 層 の 表 で 実 現 ( 省 メモリ 化 技 術 ) 2 階 層 のページテーブル 6