オペレーティングシステム・ネットワーク・分散システム

プロセス・並行処理・仮想記憶、TCP・DNS・HTTP・TLS、分散合意・トランザクション・キャッシュという大学レベルの32概念を復習します。プログラミングとコンピュータネットワークの基礎知識を前提とします。必要に応じて、プロトコルのバージョンや障害に関する前提条件を説明します。

Category
Computer Science
Level
intermediate
Languages
ja → ja
Cards
32
Markdown
オペレーティングシステム・ネットワーク・分散システム (.md)

Flashcards (32)

#Front (Term / Question)Back (Definition / Answer)ExampleMultiple-Choice Options
1結果整合性は何を約束し、競合処理の仕組みはどの役割を果たすか?更新が止まり、更新や修復が最終的にレプリカへ到達できるなら、システムの調停規則に従って状態が収束するべきである。ベクトル時計は因果順序と並行するバージョンを検出するが、それだけで競合を解決するわけではない。適合するCRDTマージや最終書き込み優先などの決定的な方針で調停できるが、後者では更新が失われることがある。
2キャッシュされていない通常のDNS名前検索はどう進むか?クライアントが再帰リゾルバーに問い合わせる。必要に応じてリゾルバーはルートサーバーからトップレベルドメインのサーバー、次に権威サーバーへの参照をたどり、AやAAAAなどのレコードを得る。回答を返し、TTLの間キャッシュできる。参照や回答のキャッシュがあれば、一部の手順を省ける。
3ページングとTLB(アドレス変換キャッシュ)とは何か?ページングは、ページテーブルを用いて仮想メモリのページを物理ページフレームへ対応づける。TLBは最近のアドレス変換とアクセス情報をキャッシュし、ページテーブル参照を減らす。複数のページサイズを持つシステムもある。TLBが保持するのは変換情報であり、ページのデータではない。
4Beladyの異常とは何か。また、LRUではなぜ起こらないか?同じページ参照列でも、FIFOなどの置換方式ではフレームを増やすとページフォールトが増えることがある。LRUにはスタック性があり、Nフレームで保持するページ集合はN+1フレームで保持する集合の部分集合になる。そのため、フレームを増やしても、その参照列でのフォールト数は増えない。
5一般的なOSでは、プロセスとスレッドはどう違うか?プロセスは資源と保護の単位で、独自の仮想アドレス空間を持つ。内部のスレッドはその空間や開いているファイルなどの資源を共有するが、レジスタ、プログラムカウンタ、スタックなどの実行状態はそれぞれが持つ。別々のプロセスも、明示的にメモリを共有できる。
6キャッシュスタンピードとは何か。また、どう緩和できるか?多数の要求が同じ期限切れ・不在の項目でミスし、同時に再計算や取得を行って背後のサービスを過負荷にする現象。キー単位での要求のまとめ、適切なロック管理、早期・確率的な更新などで集中を減らせる。効果はタイミングと障害処理に依存する。
7資源のデッドロックに必要なコフマンの4条件は何か?相互排他、保持と待機、資源の非横取り、循環待ち。再利用可能な資源の古典的モデルでは、どれか1条件を破ればこの種のデッドロックを防げる。これらの条件を許すことは、すべての実行が必ずデッドロックするという意味ではない。
8ミューテックスと計数セマフォはどう違うか?ミューテックスは所有権に基づく相互排他を提供し、所有するスレッドが解放する必要がある。計数セマフォに同じ所有権規則はなく、成功した待機操作が許可を1つ消費し、post操作が1つ追加する。初期許可数がNで取得と返却が対応していれば、資源の同時利用者数をNに制限できる。
9ライトスルーとライトビハインドのキャッシュはどう違うか?ライトスルーは、書き込み処理の一部として元のストアへの書き込みを完了してから成功を通知する。ライトビハインドはキャッシュ更新を先に確認し、後でストアへ書くことで、その場の書き込み遅延を減らす。未反映の書き込みは永続的に保護しなければ障害時に失われ得る。耐久性は方式名だけでなくシステム次第である。
10競合状態とは何か。また、クリティカルセクションにはなぜ同期が必要か?正しさが並行処理のタイミングや実行の入り交じり方に依存すると、競合状態が生じる。クリティカルセクションは、不変条件を守る必要のある共有状態にアクセスする。相互排他は、該当部分を同時に実行するスレッドを1つに制限する一般的な方法である。
11証明書認証を使う典型的なTLS 1.3接続は、どの仕組みで保護されるか?証明書の検証とハンドシェイク署名が相手を認証し、一時的な(EC)DHEが共有鍵素材を確立し、AEADがアプリケーションデータの機密性と完全性を守る。TLS 1.3には事前共有鍵のモードもあるため、すべてのモードや0-RTTデータで証明書と前方秘匿性が得られるとは限らない。
12データを伴わない通常のTCPの3ウェイハンドシェイクでは、何を送るか?クライアントが初期シーケンス番号xのSYNを送る。サーバーはシーケンス番号y、確認応答番号x+1のSYN+ACKを返す。クライアントはy+1を確認するACKを送る。SYNはそれぞれシーケンス番号を1つ消費するが、ACKのみのセグメントは消費しない。
13TCPの受信ウィンドウrwndと輻輳ウィンドウcwndは、送信をどう制限するか?受信側は受け入れ可能なデータ量をrwndで通知し、送信側はネットワーク負荷を抑えるcwndを管理する。通常、送信済みで未確認のデータ量はmin(rwnd, cwnd)に制限される。それぞれ受信側の容量とネットワーク輻輳に対応する。
14Raftのログ一致特性とは何か。また、フォロワーの矛盾するログはどう修復するか?2つのログに同じインデックスと任期のエントリがあれば、そのインデックスまでの接頭部分は一致する。AppendEntriesは直前のインデックスと任期を確認する。リーダーは一致する接頭部分が見つかるまで再試行し、その後フォロワーの矛盾するエントリを自身のエントリで置き換える。正しいRaftはコミット済みエントリを決して破棄しない。
15CPUのコンテキストスイッチでは、どの状態を保存・復元するか?OSは実行を離れるタスクのレジスタ、プログラムカウンタ、スタックポインタなどを保存し、次のタスクの状態を復元する。アドレス空間の状態は必要な場合に切り替える。同じプロセス内のスレッド間の切り替えでは、ページテーブルのルートを変える必要がないこともある。具体的な保存対象はアーキテクチャと実装に依存する。
16Raftはリーダーをどう選び、選挙タイムアウトのランダム化は何を実現するか?選挙タイムアウト後、フォロワーは候補者となり、任期番号を増やし、自分に投票して他の票を求める。当選には過半数が必要で、各サーバーは任期ごとに最大1票を与え、ログの新しさを確認する。ランダム化は票の分裂の繰り返しを減らすが、毎回の選挙成功を保証しない。
17QUIC上のHTTP/3は、トランスポートの先頭待ちブロッキングをどう減らすか?QUICはUDP上で独立した信頼性のあるストリームを運ぶため、1つのストリームの欠落が他のストリームの受信を必ずしも妨げない。損失回復と輻輳制御は接続全体で引き続き働く。QUICは1往復のハンドシェイクに対応し、条件を満たす再開接続では、リプレイの危険がある0-RTTデータも任意で利用できる。
18RFC 5681の古典的なTCPモデルでは、スロースタートと輻輳回避でcwndはどう増えるか?スロースタートしきい値より下では、ACKによる増加はおおむね指数的で、1往復時間ごとにcwndが約2倍になり得る。輻輳回避では、1往復時間あたり最大サイズのセグメント約1個分だけ増える。ACKの挙動で増え方は変わり、他のTCP輻輳制御方式が同じパターンに従うとは限らない。
19OSIの7層と一般的なTCP/IPの4層を、下位から順に挙げると?OSIは物理層、データリンク層、ネットワーク層、トランスポート層、セッション層、プレゼンテーション層、アプリケーション層。一般的なTCP/IPの4層はリンク層、インターネット層、トランスポート層、アプリケーション層。異なる構造モデルなので、層は厳密に1対1対応しない。
20ページフォールトはなぜ発生し、OSはどう処理できるか?必要なアドレス変換が存在しない、または権限が許さないメモリアクセスで発生する。正当なアクセスなら、遅延割り当て、コピーオンライト、ファイルやスワップからのページ読み込みなどを行い、対応づけを更新して命令を再試行する。不正なアクセスならエラーとなり、プロセスへのシグナルなどで通知する。すべてのフォールトがディスクI/Oを必要とするわけではない。
21HTTP/2はリクエストをどう多重化し、どの先頭待ちブロッキングが残り得るか?HTTP/2は1つのTCP接続上で異なるストリームのバイナリフレームを交互に送り、フィールドセクションをHPACKで圧縮する。これによりHTTP/1.1パイプラインの応答順序制約を避けられる。ただしTCPはバイトを順序どおりに渡すため、TCPセグメントの欠落で複数ストリームのデータが遅れることがある。
22キャッシュアサイドは読み取りをどう処理するか?アプリケーションがキャッシュを調べ、ヒットなら値を返す。ミスなら元のストアを読み、キャッシュへ格納して値を返す。キャッシュの値は古くなり得るため、有効期限と無効化の方針も必要である。
232相コミットはなぜブロックすることがあるか?YESを返した参加者は決定を知るまで準備状態を維持する必要がある。調整役が故障し、到達可能な参加者の誰も決定を確定できなければ、ロックなどの資源を保持したまま回復を待つ場合がある。ブロックは起こり得るが、調整役が故障するたびに必ず起こるわけではない。
24ラウンドロビン方式はタイムクォンタムをどう使い、どのようなトレードオフがあるか?実行可能な各タスクは最大1クォンタム実行した後、実行待ちキューの末尾へ移る。それ以前にブロック、CPUの自発的な譲渡、終了が起きることもある。短いクォンタムは応答性を高めるが、切り替えの負荷を増やす。クォンタムがCPUバーストより長ければ、先着順方式に近づく。
25TCPを能動的に閉じる側は、通常なぜ最大セグメント生存時間の2倍だけTIME-WAITに留まるのか?最後のACKが失われた場合に再送FINへ確認応答できるようにし、同じ接続識別子を再利用する前に古いセグメントが消滅する時間を確保するためである。通常の時間は2×MSL。安全な終了に役立つが、ACKが絶対に失われない保証ではない。
26PACELCはCAPに何を加えるか?分断がある場合(P)は可用性と整合性(A/C)の取捨選択を、ない場合(E)は遅延と整合性(L/C)の取捨選択を考える。後者は特にレプリカ間で調整が必要なときに重要になる。PACELCは設計判断を議論する枠組みであり、全操作に固定的で普遍的な1つのトレードオフがあるという主張ではない。
27ネットワーク分断中、CAPは複製データサービスにどのトレードオフを要求するか?読み書きの線形化可能性と、故障していないノードへのすべての要求の成功を同時に保証することはできない。線形化可能性を守るには一部の要求を待たせたり失敗させたりする必要がある。分断の両側でサービスを続けるには、何らかの整合性保証を弱める必要がある。CAPは正常時に無条件で「任意の2つを選ぶ」という規則ではない。
282相コミット(2PC)の準備段階と決定段階では何をするか?各参加者は準備状態を永続化して初めてYESを返し、コミットできなければNOを返す。調整役は全員がYESの場合にのみCOMMITを永続記録し、それ以外ではコミット決定前にABORTを決められる。その後、決定を通知する。準備済み参加者のタイムアウトは、一方的な中止を許可するものではない。
29TCPとUDPが提供するサービスはどう違うか?TCPはコネクション型の信頼性のある順序付きバイトストリームを提供し、再送、フロー制御、輻輳制御を行う。ただし接続自体が失敗することはある。UDPはデータグラムの境界を保つが、配送、順序、再送を内蔵の仕組みで保証しない。UDPを使うアプリケーションが独自にこれらを追加することはできる。
30サーキットブレーカーのclosed、open、half-open状態は何をするか?Closedは呼び出しを許可し、失敗を追跡する。設定した失敗のしきい値に達するとopenになり、呼び出しを素早く拒否する。一定時間後、half-openは限られた試行呼び出しを許可し、回復すればclosed、再び失敗すればopenへ戻る。この方式は不調なサービスへの反復呼び出しを抑えるが、サービス自体を修復はしない。
31ロックの大域的な取得順序は、循環待ちによるデッドロックをどう防ぐか?ロックに一貫した厳密な順序を定め、他のロックを保持する各スレッドには、順序が増える方向でのみ追加取得させる。循環には順序を増やし続けて出発点へ戻る必要があり、不可能である。関連するすべての取得経路がこの規則に従う必要がある。
32リング型コンシステントハッシュは、ノード変更時のキー再割り当てをどう減らすか?キーとノードをリング上へハッシュし、各キーを時計回りで次のノードに割り当てる。ノード追加で区間を分割し、削除では区間を後続ノードへ渡す。十分に均等な配置なら、Nノードのうち1つの変更で全K個のキーのうち再割り当てされる個数の期待値はO(K/N)であり、最悪時の保証ではない。仮想ノードは偏りを減らす。