EuDs

オペレーティングシステム：設計と実装 (2022 春学期)の学習ノート

p3 マルチプロセッサプログラミング：入門から放棄まで (スレッドライブラリ；現代プロセッサと緩やかなメモリモデル)#

• 同時プログラムの三つの問題

  • 原子性
  • 順序
  • 可視性

• gcc コンパイル

  • 最適化しない、アセンブリコードを確認する
    gcc -c -O1 sum.c && objdump -d sum.o
  • asm volatile("" : : "memory"); // コンパイラバリア

• 統計回数
  ./a.out | head -n 1000 | sort | uniq -c

• 現代プロセッサ

  • 動的コンパイラでもある：アセンブリ命令は複数の uop で構成される。
  • uop の「プール」を維持する 指令の有向無環グラフ
  • 乱序実行、順序提出

p4 同時プログラムの実行を理解する (ペテルソンアルゴリズム、モデル検査とソフトウェア自動化ツール)#

• C 言語の形式的意味
  • グローバル変数と複数のスタックフレーム；各スタックフレームにはその局所変数と pc がある
• ペテルソンアルゴリズム
  • 一見すると譲歩しているようだが、実際には自己中心的である
  • 正しさの証明：状態機械を描く
    • Dilemma：描かないことができず、無闇に描くこともできない
    • 解決： model-checker
    • プログラムの問題をグラフ理論の問題に変える
      • safety 赤い状態に到達できない
      • liveness : 任意の状態から緑 / 青の状態に到達できる 強連結成分
  • 多くの重要なアイデアが、凝縮されると概念になる
• 同時プログラム = 状態機械
• Python generator
  • 例：
    Copy

    def numbers(init=0,step=1):
        n = init
        while True:
        n += step
        yield n
    g = numbers()
    g.__next__()
    

p5 同時制御：排他 (スピンロック、ミューテックスと futex)#

• 問題を解決できないときは、依存している仮定を見つけて大胆に破ることができる
• spin スレッドは直接 locked を共有する
• mutex システムコールを通じて locked にアクセスする
• futex(Fast Userspace muTexes)
  • Fast path: 一つの原子命令、ロック成功で即座に戻る
  • Slow path: ロック失敗、システムコールを実行してスリープ

p6 同時制御：同期 (条件変数、セマフォ、プロデューサ - コンシューマと哲♂学者の食事問題)#

• 考える：タスクの束があり、平均して n 束に分けられる。x 個のスレッドがそのタスクを完了する責任がある (x < n) 一つのスレッドは一度に一つのタスクしか完了できず、完了後は自動的に次のタスクに移る。どう実現するか？
• 万能の方法があるなら、万能の方法を使うべきである。
  • 彼はこう解釈した。プロジェクトのコード量が少ない（千行以内）の場合、プロジェクトは比較的維持しやすい。この時、賢い書き方を使うのは問題ない。しかし、プロジェクトが数万行、さらには数百万行に達すると、複数の人が協力する必要がある。そして、人と人の間の最大の障害は、完全にコミュニケーションを取れず、相手の意図を理解できないことである。
  • 同時問題を賢い方法で解決しようとしないこと
  • 個人的な考え：このような言い方を初めて聞いたが、一定の理にかなっている。
• 万能の同期方法 —— 条件変数 (Conditional Variables)
  • API
    • wait(cv, mutex) 💤
      呼び出す時は必ず mutex を取得していることを保証する
      mutex を解放し、スリープ状態に入る
    • signal/notify (cv) 💬 プライベートメッセージ：行こう
      待機しているスレッドがいる場合、その中の一つを起こす
    • broadcast/notifyAll (cv) 📣 みんな：行こう
      待機している全てのスレッドを起こす
  • Copy

    // 条件が満たされるのを待つ必要がある時
    mutex_lock(&mutex);
    while (!cond) {
      wait(&cv, &mutex);
    }
    assert(cond);
    // ...
    // ミューテックスはこの期間中条件 cond が常に成立することを保証する
    // ...
    mutex_unlock(&mutex);
    
    // 他のスレッドの条件が満たされる可能性がある時
    broadcast(&cv);
    

  • debug -> バグを引き起こす最小条件を隔離する

p7 現実世界の並行プログラミング (高性能計算 / データセンター / 人間とコンピュータのインタラクションにおける並行プログラミング)#

• ブロックチェーンについて話す > とても良い技術だ。しかし、あまり正しくないと感じる。かなりのリソースの無駄を引き起こしているから。
• マンデルブロ集合の何が特別なのか？ - Numberphile
• atanunq/viu
• 検索は知識の取得コストを下げ、ChatGPT などが再びコストを下げた。
• Go 言語、プログラミングに優しい、パフォーマンス最適化
• ブログは web2.0 の第一歩
• Ajax (非同期 JavaScript + XML)
• この授業では三つの並行プログラミングの方法が講義され、異なるニーズに応じて並行性を実現する方法も異なる。

p8 並行バグと対処 (デッドロック / データ競合 / 原子性違反；防御的プログラミングと動的分析)#

• ソフトウェアはコンピュータのデジタル世界における要求の投影である。
• assert の使用
• ツールがなければシステムを作らない
• premature optimization is root of all evil
• プログラミング言語の欠陥 —— プログラマへの完全な信頼：計算資源の貴重さのため
• 動的分析ツール -fsanitize
• Canary msvc のデバッグモードの canary (b'\xcc' * 80).decode('gb2312')

p9 オペレーティングシステムの状態機械モデル (オペレーティングシステムのロード；thread-os コード解説)#

• 大学の真の意味：既存の知識と方法を再消化し、皆のために「階段」を築き、限られた時間内に数十年にわたって築かれた学問体系に迅速に追いつくこと。

p10 状態機械モデルの応用 (セルオートマトン；gdb/rr/perf; コード検証ツール)#

• 分散システムも一種の並行プログラムであるが、より複雑である。なぜなら、並行プログラムは各スレッドが正常に動作することを仮定しているが、分散システムはノードの喪失を考慮しなければならない。

p11 オペレーティングシステム上のプロセス (最小 Linux; fork, execve と exit)#

• Linux オペレーティングシステムの起動プロセス
  CPU リセット → ファームウェア → ローダー → カーネル _start () → 最初のプログラム /bin/init → プログラム (状態機械) 実行 + システムコール
• Fork Bomb:
  :(){:|:&};:
  Copy

  :() {         # フォーマットを整える
  : | : &
  }; :
  

• stdout:
  ターミナル: line buffer
  pipe , file buffer (明示的に fflush を呼び出さない限り)
  Copy
• fork
  • プログラムは状態機械であり、実行中のプログラムも状態機械であり、fork は状態機械のコピーを作成する；
  • 作成されたプロセスは + 1 を返し、子プロセスは 0 を返す
  • すべてのレジスタとメモリをコピーする
• execve
  • 現在実行中の状態機械を別のプログラムの初期状態にリセットする
• _exit

p12 プロセスのアドレス空間 (pmap; vdso; mmap; ゲーム改造ツール / 外部ツール)#

• エンディアン
  • ビッグエンディアン (big endian): 低アドレスに高有効バイトを格納
  • リトルエンディアン (little endian): 低バイトに低有効バイトを格納
• ツールの使用
  • gdb
  • readelf
  • pmap
• コンピュータの世界には魔法はない。なぜなら、プログラムは状態機械だからである。
• vdso: オペレーティングシステムカーネルに入らず、システムコールを実現する
• mmap：
• ファイル = バイト列；メモリ = バイト列；すべてはファイルである

p13 システムコールとシェル (freestanding shell, ターミナルとジョブ制御)#

• cd は内部コマンド：現在のディレクトリを変更するのはシステムコールで実現される
• strace -f gcc a.c 2>&1 | vim - これは stdout と stderr の両方を vim にパイプします。-引数は vim に stdin から読み込むよう指示します。
• strace pmap 152 |& vim -
|& : これは bash と zsh での2>&1 |の省略形です。一つのコマンドの標準出力と標準エラーの両方を別のコマンドの入力として渡します。
• fish, zsh と bash は一般的なコマンドラインシェルであり；sh は比較的原始的である
• clear 画面をクリア
• ,./a.out & バックグラウンドで./a.out を実行

p14 C 標準ライブラリの実装 (システムコールのラッピング；メモリ空間管理)#

• ファイルディスクリプタはまだ理解できていない。印象としては、"everything is a file" が二度目に言及された。
  • os のオブジェクトとオブジェクトへのアクセス
• gdn の使用
  • No symbol table is loaded. Use the "file" command。これはコンパイルオプションにデバッグ情報が含まれていない可能性がある、例えば gcc が - g オプションを追加していない場合。
• premature optimization is the root of all evil.
• workload を離れて最適化を語るのは無駄である
• クラシックな設計：
  • fast path
  • slow path

p15 fork の応用 (ファイルディスクリプタのコピー；コピー時書き込み；平行宇宙を作る魔法)#

• fork 状態機械のコピーには保持しているすべてのオペレーティングシステムオブジェクトが含まれる
• 保持しているすべてのオペレーティングシステムオブジェクトを含む
• ファイルディスクリプタ（file discriptor）
  • オペレーティングシステム内のオブジェクトへの「ポインタ」
  • dup () の二つのファイルディスクリプタはオフセットを共有する
• 空のポインタにアクセスするとページフォルトが発生することもある
• “Copy-on-write” は書き込まれるページのみがコピーされる
  • コピー後、全体のアドレス空間は「読み取り専用」としてマークされる
  • オペレーティングシステムはページフォルトを捕捉した後、必要に応じてページをコピーする
  • fork-execve の効率が向上する
• オペレーティングシステムは各ページの参照カウントを維持する
• プロセスが占有するメモリを定義する
• ページは os のものであり、プロセスのものではない
• fork を使用して探索し並行化する。

p16 実行可能ファイルとは (デバッグ情報；スタックアンワインディング；静的リンクにおける再配置)#

• 実行可能ファイルは状態機械を記述しており、状態機械の初期状態 + 遷移のデータ構造を記述している
• os には魔法はなく、すべてのものには説明がある
• She-bang #! interpreter [optional-arg]
• GNU binutils
  • 実行可能ファイルを生成する
    • ld (リンカー), as (アセンブラ)
    • ar, ranlib
  • 実行可能ファイルを分析する
    • objcopy/objdump/readelf
    • addr2line, size, nm
• objdump -d a.out | less disasm
• addr2line 401122 a.out
• elf: 小精霊；dwarf：小人
• アセンブリ (機械) 状態を「C の世界」状態にマッピングするのは難しい
• gcc などにはまだ多くの不完全さが存在する
• コンパイラ、アセンブラ、リンカー

p17 動的リンクとロード (静的 ELF ローダーの実装；Linux カーネルのデバッグ；動的リンクとロード)#

• カスタムのバイナリフォーマットファイルを作成した
• GOT ： グローバルオフセットテーブル
• PLT : プロシージャリンクテーブル

p23 1 ビットデータの保存 (遅延線 / 磁気コア / DRAM/SRAM/ テープ / ディスク / 光ディスク / フラッシュ SSD)#

• volatile: この変数の実際の値がメモリ内の値と一致することを保証し、毎回の読み取りが最新の値であり、コンパイラによる最適化を禁止する。
• core dumped 磁気メモリ時代からの概念。
• 局所性原理 -> 大きなブロックで読み書きできる

p24 入出力デバイスモデル (シリアルポート / キーボード / ディスク / プリンター / バス / 割り込みコントローラー / DMA と GPU)#

• DMA: ダイレクトメモリアクセス : "memcpy" プログラムを実行する専用の CPU
• IPC: Instruction per second
• GPU:
  • 一般的な計算デバイス
  • 大量の並行した類似のタスク
• 異種計算：すべてが可能だが、最も適したものを選ぶ。（jjy は 22 年にこの関連のトレンドを感じ始めたと言っていた。しかし、挙げられた例のマイニングではなく、llm モデルのことだ。）

p25 デバイスドライバ (Linux デバイスドライバ；GPU と CUDA; ストレージデバイスの抽象)#

• デバイスは各種操作をサポートするオブジェクト (ファイル) に抽象化される
  • read - デバイスの特定の位置からデータを読み出す
  • write - デバイスの特定の位置にデータを書き込む
  • ioctl - デバイスの状態を読み取る / 設定する
• stty -a
• GPU
  • Single Instruction, Multiple Thread
• 読み優先の正しさ

p26 ファイルシステム API (デバイスのアプリケーション間の共有；ディレクトリとファイル API)#

• 情報の局所性
• Windows が c ドライブから始まったのは、その前身である Dos システムの影響を受けている。あの時代には a、b があった。
• mount disk.img /mnt
• umount /mnt
• ハード（hard）リンク
  • ln /usr/local/python3 python
  • ディレクトリにはファイルデータへのポインタのみが保存される
  • 一つのファイルが複数のディレクトリから参照されることを許可する。
  • ディレクトリをリンクすることはできず、ファイルシステムを越えることもできない
  • ls -iでハードリンクかどうかを確認する
• ソフト (symbolic) リンク
  • “ショートカット”
  • ln -s ../p24 p24
  • ディレクトリは「木」から「グラフ」に変わり、環状グラフが存在する
• cdの特異性
  • 各プロセスには対応する作業ディレクトリ（pwd）があり、このディレクトリはシステムコールでのみ変更できる

p27 FAT と UNIX ファイルシステム (データ構造の視点からのファイルシステム；FAT マニュアルの導入とディレクトリツリーの遍歴)#

• データ構造の仮定：データはバイトとして保存される。
• RAM とブロックの違い
• FAT(File Allocation Table)
  • ポインタをファイルシステムの特定の領域に集中して保存する
  • 小さなファイルに適している
  • フラグメンテーションを引き起こす
  • 基本的な仮定
    • リンクリストは環がなく、長さはファイルサイズと一致する
    • FREE のクラスターには入辺がない
• クラスター
• セクター
• ext2
  • 大ファイルのランダム読み書き性能が向上する (O (1))
  • リンクをサポート (ある程度スペースの無駄を減少させる)
  • inode はディスク上に連続して保存され、キャッシュ / プリフェッチが容易
  • フラグメンテーション

p28 永続データの信頼性 (RAID; クラッシュ整合性；FSCK とログ)#

• 仮想化
  • CPU の仮想化：分時などの技術を通じて複数のプロセスを並行して実行し、複数の CPU を仮想化する
  • メモリの仮想化：一つのメモリが mmu を通じて各プロセスのアドレス空間に仮想化される
  • RAID：逆の仮想化：複数のディスクを一つのディスクに仮想化する
• RAID
  • RAID0 : ストライピング： 容量と帯域幅を向上させる
  • RAID1 : フォールトトレランスと読み取り帯域幅を向上させる
  • RAID4 : 追加のパリティディスク
    • 致命的な欠陥：ランダム書き込みの性能はパリティディスクの性能の半分しかない
  • RAID5 : ローテイングパリティ
• RAID がもたらす連想：
  複数のディスクを一つの大きくて速くて信頼性の高いディスクに仮想化し、複数のコンピュータを一つの大きくて速くて信頼性の高いコンピュータに仮想化する
  それなら、複数の神経ネットワークを一つのより良い神経ネットワークに仮想化できるか？
• クラッシュ整合性 (Crash Consistency)
  • シナリオ：書き込み中に突然電源が切れたらどうする？
  • 方法 1：一定の順序で書き込み、「all or nothing」
    • 難しさ：ディスクは複数のブロックの読み書きに「all or nothing」のサポートを提供せず、性能のために順序保証もない。
  • 方法 2：ファイルシステムチェック (FSCK)
    • ディスク上の既存情報に基づいて「最も可能性の高い」データ構造を復元する
    • 難しさ：難しい；修復中に再度電源が切れたら？
  • 方法 3：ログ
  • 具体的には：
    • データ構造操作が発生した時、(2) append-only でログを記録する
    • ログがディスクに落ちた後、(1) データ構造を更新する
    • クラッシュ後、ログを再生しクリアする（これを redo log と呼び、相応に undo log も可能）
  • 最適化: journaling (jdb2)

p30 現代ストレージシステム (リレーショナルデータベースと分散ストレージシステム)#

• データベース
  • 重要な要素
    • インデックス
    • クエリ最適化
  • magic：あなたはただ sql 文を書くことに集中し、相応の検索最適化を行う
  • 要求：acid
    • 原子性
    • 一貫性
    • 隔離性
    • 耐久性
• チューリング賞
  • この授業を受けて、多くの知識の背後にはチューリング賞を受賞した研究があり、さらには一つの産業を創出したことを聞いた。
• リレーショナルデータベースはソーシャルネットワークの需要に追いつけない
• cap 定理
  • 一貫性
  • 可用性
  • 分割耐性
• 分散ストレージシステム

感想#

蒋炎炎のこの授業は他の人からの推薦だった。初めて見たときはあまり気にしなかったが、出現する回数が多くなると、見てみる必要があると感じた。大きな驚きを発見した。

収穫#

1. 原版の本を読むことができた。大段の英語を以前は少し怖がっていたが、今は読めるようになり、速度も良い。

課外資料#

• コンテキストスイッチのコスト
• CPU の製造と概念