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 ジェネレーター
  • 例：
    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) 💬 プライベートメッセージ：行こう
      もしスレッドが cv を待っている場合、その中の一つを起こす
    • broadcast/notifyAll (cv) 📣 みんな：行こう
      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 → プログラム (状態機械) 実行 + システムコール
• フォークボム:
  :(){:|:&};:
  Copy

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

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

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

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

p13 システムコールとシェル (フリースタンディングシェル、ターミナルとジョブ制御)#

• 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 標準ライブラリの実装 (システムコールのラッピング；メモリ空間管理)#

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

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

• fork 状態機械のコピーには保持しているすべてのオペレーティングシステムオブジェクトが含まれる
• 保持しているすべてのオペレーティングシステムオブジェクトを含む
• ファイルディスクリプタ（file descriptor）
  • オペレーティングシステム内のオブジェクトへの「ポインタ」
  • dup () の二つのファイルディスクリプタはオフセットを共有する
• 空のポインタにアクセスするとページフォルトが発生することもある
• 「コピーオンライト」では、書き込まれるページのみがコピーされる
  • コピーされた後、全体のアドレス空間は「読み取り専用」としてマークされる
  • オペレーティングシステムはページフォルトを捕捉した後、必要に応じてページをコピーする
  • 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: 秒あたりの命令
• GPU:
  • 一般的な計算デバイス
  • 大量の並行した類似のタスク
• 異種計算：すべてが可能だが、最も適したものを選ぶ。（jjy は 22 年にこの関連のトレンドを感じ始めたと言っていた。しかし、挙げられた例のマイニングではなく、llm モデルのことだ。）

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

• デバイスは各種操作をサポートするオブジェクト（ファイル）として抽象化される
  • read - デバイスの特定の位置からデータを読み出す
  • write - デバイスの特定の位置にデータを書き込む
  • ioctl - デバイスの状態を読み取り / 設定する
• stty -a
• GPU
  • 単一命令、複数スレッド
• 読み優先の正しさ

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

• 情報の局所性
• Windows が C ドライブから始まるのは、その前身である Dos システムの影響を受けているためで、あの時代には a、b があった。
• mount disk.img /mnt
• umount /mnt
• ハードリンク
  • ln /usr/local/python3 python
  • ディレクトリにはファイルデータへのポインタのみが保存される
  • 一つのファイルが複数のディレクトリから参照されることを許可する。
  • ディレクトリをリンクすることはできず、ファイルシステムを越えることもできない
  • ls -iでハードリンクかどうかを確認する
• ソフト（シンボリック）リンク
  • 「ショートカット」
  • 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：一定の順序で書き込み、「すべてか無か」
    • 難しさ：ディスクは複数のブロックの読み書きに「すべてか無か」のサポートを提供せず、性能のために順序保証もない。
  • 方法 2：ファイルシステムチェック (FSCK)
    • ディスク上の既存の情報に基づいて「最も可能性の高い」データ構造を復元する
    • 難しさ：難しい；修復中に再度電源が切れたら？
  • 方法 3：ログ
  • 具体的には：
    • データ構造操作が発生したとき、(2) append-only でログを記録する
    • ログがディスクに落ちた後、(1) データ構造を更新する
    • クラッシュ後、ログを再生しクリアする（これを redo log と呼ぶ；相応に undo log も可能）
  • 最適化：ジャーナリング (jdb2)

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

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

感想#

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

収穫#

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

課外資料#

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