どうもこんにちは。最近とても刺激を受ける機会が多い生活を送っています、logicaです。

刺激を受けると新しいことを始めたくなることが多いのですが、そんな感じで新しいことを始めてしまうと、大学の課題など自分にとって苦痛・つまらないものが後回しになりがちです。良くないことですね...。

はじめに

1週間ほど前、セキュリティ・キャンプ全国大会2022 オンラインの選考結果が発表されました。
幸運なことに、自分は第一希望の [Y3] 故障を乗り越えて動くシステムのための分散合意ゼミで選考を通過させていただきました！
番号を確認した瞬間、嬉しさのあまり飛び上がってしまいました。本当にありがたい限りです。力の限り楽しんで来ようと思います。

折角頑張って課題の回答を書きましたので、少しでも来年以降のセキュリティ・キャンプに応募される方のお役に立てればと思い、今回の課題の回答を公開させていただきます。

なお、Y3はこの回答で通過させていただきましたが、Y1・Y2に関してはこの回答をしても通過できたかどうか不明だということをあらかじめご承知おき下さい。

申し込んだコース

開発コース第1希望
[Y3] 故障を乗り越えて動くシステムのための分散合意ゼミ
開発コース第2希望
[Y2] データベースゼミ
開発コース第3希望
[Y1] OS自作ゼミ

最終的に [Y3] 故障を乗り越えて動くシステムのための分散合意ゼミで参加権をいただきました！

回答作成時間

締め切り付近では他のタスクも積み重なっており、締め切り直前の2～3日でかなり集中して取り組んでいたので、所要時間は各3～4時間ほどでした。

回答

故障を乗り越えて動くシステムのための分散合意ゼミ

皆さんの多くは直接的に分散システムを意識した経験，あるいは実装した経験が少ないと思います．
したがって本応募課題では，分散システムそのものに密接に関連する技術よりは，むしろ皆さんのモチベーションや基礎的なプログラミング技術，わからないことを調べる力について教えていただこうと考えております．

各設問の回答について字数制限は特に設けませんが，要点が明確であることを期待します．

(1)

分散システムと聞いて，どういったものを想像しますか．特にメリットやデメリットについて，自分なりの考えを記述してください．

回答

分散システムは、1つのサービスの中で、複数の同等な性質とそれぞれ固有の状態をもったインスタンスが相互に連携・同期して動いているシステムのことだと認識しています。
今まで自分はマイクロサービスアーキテクチャ・クラスタリングによるロードバランシングに主に興味をもって勉強を進めていましたが、それらの概念と分散システムは同じものだと聞いたことが無かったので、違いを考察すると上記のようになりました。マイクロサービスアーキテクチャは、インスタンスがそれぞれ異なる性質を持つという点で分散システムと異なり、単一サービスのクラスタリングは複数のインスタンスが同等な状態を持つという点で異なっていると考えています。
また、Gitなどが実現する「分散バージョン管理」の「分散」も、上記の定義と合致しているかなと思われます。
分散システムのメリットとしては、全てのインスタンスが他のすべてのインスタンスのバックアップになれることによる、データの冗長性がまず第一に挙げられるのではないでしょうか。例えばGitのような分散バージョン管理システムでは、リモートが集中的にデータを持つのではなくリモートとローカルがそれぞれ固有にデータを持ち、それを任意のタイミングで同期することによる冗長性を実現することに焦点が当てられていました。ですから、おそらくインスタンス間の同期によって動いている分散システムにおいても同様のメリットが得られると考えられます。
また別視点のメリットとして、インスタンスが増えることによる負荷分散は見過ごせないでしょう。これはクラスタリングによるロードバランシングと全く同じですが、分散システムにおいても変わらずメリットとなり得ると考えます。
一方デメリットについては、ひとえに同期の難しさにあると思います。これはGit等の分散バージョン管理システムを例に挙げるとわかりやすく、マージの粒度・頻度が統一しづらいという問題や、マージ時のConflictに表れています。分散バージョン管理システムは基本的に人が使うツールで同期面の問題を人間が手を加えることによって解決しますが、分散システムにおいてはそれを全て自動化しなければいけないため、開発コストが飛躍的に上昇するというデメリットが発生すると考えられます。

(2)

身近なITサービスなどの中から分散システムで構築されているであろうものを一つ挙げ，どういった機能を分散システムで実現しているのか，なぜ分散システムである必要があるのかを説明してください．ここでの説明は自分なりに考察したものであっても，調べた結果わかったことをまとめたものでも構いません．

回答

Suica・PASMOに代表される交通ICカードは分散システムで運用されているという話を聞いたことがありますし、目的を考えると非常に納得できる例だと思います。
交通ICカードは日本の中でも電車を使う人の大部分が使用するシステムであり、その運用面の障害は電車という交通機関の大規模な麻痺を引き起こします。そのため交通ICカードは、どこか一部で故障などの障害が起こってもその影響が周りに伝播しないようにする、言い換えるとBlast Radiusを最小まで抑える必要があります。システム全体としての可用性を上げるだけにとどまらず、各ICカード・各改札一つ一つの可用性を上げる仕組みが必要であり、解決する手段として最良なのが分散システムだと考えられます。
以前テレビ番組でSuicaが特集されていた際、改札を通る際、Suicaにはいつ・どこで・中 / 外どちらに向かって改札を通ったかがすべて記録され、改札はそれを元に計算するという話が紹介されていました。Suicaを「きっぷの延長線上」と考えると、ひとまず各Suicaにデータを保存すれば、同期は必要ないと思われるかもしれません。
しかしSuicaは今や電車だけではなく様々な店・交通機関で使用することができ、チャージも様々な場所でできることを考えると、その利用履歴は中央のサーバーにも集めて各店舗などに分配されるときの目安にするべきだという事が容易に想像されます。いつどこが壊れてもそれ以外の部分は使えることと、中央システムで全ての履歴を記録・管理できるようにすることを同時に実現するためには、分散システムが不可欠だと考えられます。

(3)

これまでのプログラミング歴について，以下の問いに回答してください．

(3.1)

プログラミング経験のある方は好きなプログラミング言語を，経験のない方は興味のあるプログラミング言語を，理由とともに教えてください．

回答

Go言語がとても好きです。好きな理由は大きく「シンプルさ」と「並行処理のやりやすさ」にあります。
シンプルさは予約語の少なさに現れていると思います。その数30弱。宣言済み識別子と呼ばれる再定義が可能な名前まで合わせても、他の言語が自前で持つ機能よりも圧倒的に少ないです。これは、Goを書くときに最低限必要な知識が非常に少ないことを意味しています。JavaScriptのように無限に広がる仕様を理解する必要はないのです。また、Goが約束しているランタイムの高い後方互換性は、このシンプルさゆえに実現できているのではないかと考えられます。
また、シンプルさは同じ機能を実装するときの選択肢が少ないことも意味しており、これが無駄な選択やコードレビューの難化を防いでくれます。例えば、指定回数ループを実現する際、多くの言語ではfor、whileの2つの選択肢がありますし、JavaScriptに至ってはmap.foreachなどという選択肢もあります。一方Goでは必ずforです。forしかありません。forを使えばいいんです。本当にシンプルでわかりやすい。これは大きな魅力だと思われます。
また並行処理のやりやすさに関して、Goでは他のどの言語にもない、「Goroutine」というランタイム機能を用意しています。スレッドが立つたびにOSのプロセスが起動するような仕組みではなく、Goのランタイムがプロセスを管理し、前に使われたプロセスを再利用するような実装になっているため、Pythonのthreadingなどと比べると非常に軽く、速いです。
その記法も非常にシンプルで、「go」という予約語を関数実行時に前に付けるだけです。また、ライフサイクルもそれを呼び出した親関数のreturnまでという非常にわかりやすいものになっています。async、awaitなど、他の言語の面倒なライフサイクル管理と比べて、我々並行処理を酷使するプログラマーが一番使いやすい(カスタマイズ性と記法の簡単さのバランス)形でラップされている並行処理の記法だと思います。

(3.2)

なにか作ったものがあれば，作ったものの簡単な説明と実装時に苦労した点を教えてください．作ったものがない場合は，作ってみたいものの説明と，それを作るために必要な技術を調べてまとめてください．

回答

昨年の冬に友人と5人で、HiQidas(ヒキダス)というブレインストーミングの補助をするWebアプリを作りました。
「ヘヤ」と名付けた共同編集スペースに複数人で入り、「ヒキダシ」と名付けた四角形の枠にアイデアを次々に上げていきます。それぞれのヒキダシは必ず親となるヒキダシと親子関係で結ばれた形で追加されるため、アイデアの派生関係が木構造となって明確に整理され、またその構造に最も適した形でフォーマッティングされるのが、他のブレインストーミング補助アプリと異なる点かなと思います。
実装面で非常に苦労したのは、2つの未体験技術の導入を試みたところです。一つはWebSocketで、ヘヤ内での共同編集を同期的にするために導入を決定しました。もう一つは、REST APIとWebSocket上で送受信するデータのエンコード形式としてProtocol Buffersと呼ばれる構造化データのエンコーディング規格を試しました。
二つの実装に慣れるため、1週間ほど簡単なWebアプリケーションを作って試してみました。Protocol Buffersはスキーマ定義からデータエンコーディング用コードを自動生成できるのですが、そのツールがOSのデフォルトCライブラリの問題でAlpine Linux上で動かず、Dockerビルド時に自動生成をしたかった私はそこに約5時間を費やしました。この練習があったおかげで、Webアプリ自体の実装はスムーズに進んだのでとても良かったです。

(4)

以下の単語から (できれば知らないものを) 2つを選び，調査した結果わかったことをそれぞれ簡単にまとめてください．

単語集: メッセージパッシング, 非同期システム, ビザンチン将軍問題, FLP不可能性

回答

・メッセージパッシングについて
メッセージパッシングは、senderが一つまたは多くのreceiverに対してデータを配送できる通信方法である。遠隔メソッド呼び出し、シグナル、データパケットなどがある。
中でも同期メッセージパッシングと非同期メッセージパッシングがあり、前者はreceiverの受信を確認するまで相互で処理をブロッキングするものだが、後者はreceiverが受信するメッセージをバッファに保存し、任意のタイミングでそれを読み込むことで実現する。後者の例としては、最近マイクロサービスアーキテクチャのイベント駆動によく使われる、Pub / Subによるイベントハブなどがあげられるだろう。

・ビザンチン将軍問題について
ビザンチン軍の複数人の将軍が分隊に分かれて敵を包囲したとする。将軍の中には誠実なものと裏切者がおり、裏切者は発された伝令とは真逆の伝令を他の将軍に発する。ビザンチン将軍問題は、この条件のもと誠実な将軍たちの間で攻撃のタイミングを合わせることを目的とし、誠実な将軍たちの間で確信的な合意を得る方法を考える問題である。裏切者の将軍がN人の時、2N+1人以上の誠実な将軍がいれば誠実な将軍同士では正しい合意が得られることがわかっている。
ランポート博士がこのビザンチン将軍問題を分散システムの同意問題として考えた。システムの不具合で分散システムの中のあるインスタンスが間違った情報を出力したとき、システム内のインスタンスをそれぞれ将軍と置き換えると上記と同じシチュエーションで考えることができる。

(5)

その他，意気込みなどがあれば自由に記述してください

回答

元々大規模なシステムに非常に興味を持っており、そのためにK8sを使用したクラスタリングやマイクロサービスアーキテクチャに興味をもって学習を進めてきました。分散合意システムをここで学ぶことは、この先社会人になってからより大規模なシステムの設計・開発を目指す上でかけがえのない経験になるはずです。
分散合意が必要なほどの可用性・冗長性が必要な大規模プロジェクトに関わることを夢見ていますし、その1歩を踏み出していると思うと興奮が止まりません。
何卒よろしくお願いします。

データベースゼミ

以下の設問 (1)(2)(3)(4) に回答してください。

(1)

あなたの好きなプログラミング言語について、どういうところが好きなのか教えてください

回答

好きなプログラミング言語はGo言語です。好きな理由は大きく「シンプルさ」と「並行処理のやりやすさ」にあります。
シンプルさは予約語の少なさに現れていると思います。その数30弱。宣言済み識別子と呼ばれる再定義が可能な名前まで合わせても、他の言語が自前で持つ機能よりも圧倒的に少ないです。これは、Goを書くときに最低限必要な知識が非常に少ないことを意味しています。JavaScriptのように無限に広がる仕様を理解する必要はないのです。また、Goが約束しているランタイムの高い後方互換性は、このシンプルさゆえに実現できているのではないかと考えられます。
また、シンプルさは同じ機能を実装するときの選択肢が少ないことも意味しており、これが無駄な選択やコードレビューの難化を防いでくれます。例えば、指定回数ループを実現する際、多くの言語ではfor、whileの2つの選択肢がありますし、JavaScriptに至ってはmap.foreachなどという選択肢もあります。一方Goでは必ずforです。forしかありません。forを使えばいいんです。本当にシンプルでわかりやすい。これは大きな魅力だと思われます。
また並行処理のやりやすさに関して、Goでは他のどの言語にもない、「Goroutine」というランタイム機能を用意しています。スレッドが立つたびにOSのプロセスが起動するような仕組みではなく、Goのランタイムがプロセスを管理し、前に使われたプロセスを再利用するような実装になっているため、Pythonのthreadingなどと比べると非常に軽く、速いです。
その記法も非常にシンプルで、「go」という予約語を関数実行時に前に付けるだけです。また、ライフサイクルもそれを呼び出した親関数のreturnまでという非常にわかりやすいものになっています。async、awaitなど、他の言語の面倒なライフサイクル管理と比べて、我々並行処理を酷使するプログラマーが一番使いやすい(カスタマイズ性と記法の簡単さのバランス)形でラップされている並行処理の記法だと思います。

(2)

トランザクション処理やそれに関する技術のどんなところに興味を持ったのか教えてください

回答

トランザクションはWebアプリケーションの開発者 = データベースの利用者として、日々頭を悩まている部分です。どこからどこまでのクエリが同じ状態・セッションの中で実行されるべきなのか、その切り分けがとても難しいと感じています。ですが扱いが難しい分、正しく利用すれば強力な武器になることも確かです。不正なデータをDBに入れないための、大きな助けになってくれます。
そうしてトランザクションを多数用いてアプリケーションを構築していく中で、トランザクションがセッションとその状態を並列(並行？)かつ高い精度で操れるところに興味を持ちました。元々並行処理は大好きで、上記のようなGoの並行処理の仕組みも、わざわざGo Conferenceと呼ばれるアメリカで開かれているGoの勉強会のアーカイブを見て勉強しているくらいです。
データベースのトランザクションは、並行処理の面で見た時あり得ないくらい複雑なステートを持っていることが容易に想像できます。そもそもトランザクションを取ると、そのトランザクションごとにDBが違う状態を持つことになるはずです。何も知らない私は、状態を全てメモリに入れるとメモリが爆発するはずなので、スナップショットではなく差分を取るのかな…と想像したんですが、それだとトランザクション内でデータを取得するときに差分の適用時間が発生し、取得時間が遅くなってしまうと考えられます。もちろんスレッド間で同じデータにアクセスするときはスレッドセーフでなければいけず(これは私が普段散々やらかしているので…)、これがトランザクションの持つステートをさらに複雑にしていると思われます。
全てのトランザクションを並行に正しく処理するために、高速かつデータ容量を食わない、そしてスレッドセーフ状態の持ち方が必須のはずで、これを実現するデータ構造を掘り下げるのは非常に面白いだろうと想像しています。

(3)

トランザクション処理についてあなたが現時点で良く分からないなと思うことを少なくともひとつ選び、少し調べてみて分かったことを書いてください。時間をかけすぎる必要はありません。
参考にした書籍や Web ページの情報があれば全て書いてください

回答

この補足資料を読み、わからない単語はいくつかあったのですが、(2)で言ったようなステートの持ち方の参考になるであろうログ先行書き込み(Write-ahead logging, WAL)について調べてみました。

ログ先行書き込みは、データベースにおいて原子性 / 不可分性と永続性を実現するテクニックの一つです。WALを用いたシステムでは、データベースに対する変更は先立ってロギングされていなければいけないというルールに則って動きます。Wikipediaには変更を行っている最中にデータベースの電源が落ちてしまった場合、ログをチェックして現在のステートとの差分を取り、それを適用するか破棄するか、そのままにしておくかの選択ができるという例が書かれていましたが、これはデータベースの利用者がログの適用・破棄を任意に定められるトランザクションシステムにおいても同様に使えると考えられます。
PostgreSQLのドキュメントには、これをデータベースシステムに採用するメリットとして、溜めたログをディスクに書き出すのがトランザクションのコミット時だけで済む、と書いてありました。確かにログを基準にするということは差分保存に近いことをしているので、本流へのマージタイミングを自由に決めることができるのがメリットになること容易に想像できます。
上記の部分までは理解できました。WAL形式で保存されたデータ取得の高速化については未だに疑問が残りますが、そこはセキュリティキャンプまでに必要そうならまた深堀したいと考えています。

(4)

アピールしたいことがあれば自由に書いてください。この設問は未回答でも構いません

回答

今回のゼミを受けることで、最終的にはデータベースの上手で効率の良い使い方を考えるきっかけにしていきたいと考えています。
自分は大規模システムに強い興味があり、その中でTiDBなどNewSQLと呼ばれる横方向にスケーリングできるデータベースのことを勉強する機会がありました。それに関しては1つのインスタンス内でのトランザクション処理だけではなく、複数インスタンス間で全てのトランザクションの同期をしなければいけないため、さらに難しい処理になると思います。データベースシステムの仕組みに関する深い知識があることは。それらを最高効率で使用するための力強い手助けになってくれると考えています。
どうぞよろしくお願い致します。

OS自作ゼミ

「OS自作ゼミ」の応募課題は、3問の共通課題と、2問の選択課題、そして1問の任意課題から成ります。共通課題は当ゼミに応募する方は全員回答してください。選択課題は、後で示す通りに回答してください。回答は、ソースコードを除いて全体が4096字に収まるようにしてください。英数字や記号、改行文字も1文字とカウントします。複数の選択課題に回答する場合も字数制限は変わらないので、注意してください。

今年のOS自作ゼミは、2人の講師、hikaliumと内田が皆さんをサポートします。講師それぞれ、ちょっとずつ得意分野が違います。どの講師のもとで学びたいかを考えて、学びたい講師に対応する選択課題に回答してください。選考に通過した場合、回答した選択課題に対応する講師の班に配属されます。選択課題は複数回答可能です。複数回答した場合の講師選択は講師側で決めるため、応募者は選べません。

課題に回答する際は「選考のポイント」というページを読んで回答すると、より良い回答になるでしょう。回答作成にあたり文献やWebページを利用した場合は、適切に出典や引用元を明記してください。

A: 共通課題

OS自作ゼミで挑戦してみたいことを教えてください。また、それを実現するために必要となる実装や調査はどのようなものになるか、あなたの予想を教えてください。間違っていても大丈夫です。

トピック例: コンテキストスイッチやページング、ネットワーク通信の実装など。

もちろんこれ以外のトピックも歓迎します。講師によって得意分野が違いますので、それも踏まえて回答していただけると助かります。

回答

とにかくOSがどのようにハードウェアを駆使して動いているかを、1から実装して理解したいと思っています。ブートローダーの原理の理解から、特にメモリ管理やマルチスレッディングの実装に非常に興味があるので、もしそこの部分を集中してできると嬉しいです。
ブートローダーの実装のためには、バイナリデータとアセンブラの理解が必要だと認識しています。OS開発に使うことができるシステム言語の標準機能は基本的にOSの機能に頼ったものが多いので、挙げた二つでCやその他システム言語を動かせる土台を作ることが必要だと考えています。
また、メモリ管理の面ではCPUのアーキテクチャにおけるメモリ管理手法の理解が必須だと考えています。OSとして、その上に乗っかるアプリケーションに対して使いやすいメモリ管理インターフェースを提供するため、具体的にどのようにCPUがメモリを把握するのか、調査が必要だと考えます。
マルチスレッディングに関しては、特に並行処理に興味があり、これはタスクを処理を頻繁にスタート・ストップし、効率よく入れ替えていく必要があります。この入れ替えのタイミングや処理をできるだけ食わないプロセスのスタート・ストップを実装したいと思っております。

B: 共通課題

テキストエディタでコードを書いているとして、キーボードのキーを押してから画面に文字が表示される間の処理の流れを説明してください。また、そのなかで、あなたが大事だと思うOSの処理をいくつか取り上げて説明してください。

回答

キーボードのキーを押すと、キーボードケーブルを伝わってマザーボードに電気信号が届きますが、ここでOS上にてキーボード入力をトリガーとした割込み処理が発生します。割込み処理は、特定の条件が揃った時のみ発生する処理を効率よく処理するための仕組みで、OSは常に様々な割込み処理を監視し、トリガーがオンになったらそれまで順々に処理していたタスクの途中で割込み処理を発動します。
割込みに関係するデータのすべてを保持しておき、OSが割込み処理を実行する際に呼び出されるのが割込みハンドラです。キーボードの割込みハンドラの場合は押されたキーのデータをキューに保存し、OSが割込みを処理する際はそこからキーの履歴が出されて使われます。
割込み処理によって、テキストエディタが持つキーボードのファイルディスクリプタ(パイプ？)に対して値がプッシュされ、テキストエディタはread等のsyscallを使うことによって入力された値を読み取ることができます。
テキストエディタは読み取った値から次に描画されるべき画面を計算し、特定のsyscall(CLIならwriteなど)を用いてOSに割込み処理をかけます。OSはこの割込み処理も入力時度同様に処理し、最終的にモニターに向けて信号が送られ、画面に文字が描画されます。

C: 共通課題

C言語で整数を要素に持つ固定長のリングバッファを実装してください。
以下の関数が最低限必要です。

リングバッファを新規に作成する関数 ring_new(size)
要素を追加する関数 ring_push(ring, value)
要素を取得する関数 ring_pop(ring)

実装の制約：

C言語の標準ライブラリのみを利用して実装してください。
プログラムとテストケースのひな形ファイルring.cをダウンロードして使ってください。
関数やテストケースを追加するのは構いませんが、最初に定義してあるテストケースだけは変更せず、それらがパス（成功）するようにプログラムを作ってください。
応募課題を提出する際は、みなさんが実装を追加したring.cをフォームの添付ファイルとして追加して提出してください。
提出されたring.cの内容をそのままコンパイル＆実行すると、すべてのテストケースにパスする状態で提出してください。テストケースにパスすると、"PASSED: All tests finished successfully"と表示されます。初期状態では"FAILED: 2/2 tests failed" と表示されますので、これを修正するのが課題です。
提供したリングバッファのひな形の関数定義には、改善できる点がいくつかあります。余裕があればそれについても指摘し、修正して説明してください。

ひな形

ひな形

ring.c

/*

# セキュリティ・キャンプ 2022「OS 自作ゼミ」応募課題

このファイルには、作りかけのリングバッファの実装があります。
このままコンパイルして実行することはできますが、実装が不足しているため、テストに失敗するようです。
欠けている部分を実装して、テストに通るリングバッファを実装してください。

## コンパイル＆実行方法

初期状態のコードをコンパイルして実行すると、以下のような出力が得られます。

$ gcc -Wall -Wextra ring.c
$ ./a.out
NG: want 2, got 0
NG: want 3, got 0
FAILED: 2/2 tests failed

実装を追加してテストに通るようになると、出力は以下のようになります。

$ ./a.out
OK: want 2, got 2
OK: want 3, got 3
PASSED: All tests finished successfully

上記のように、テストにパスするプログラムを書くことが目標です。

## 注意事項

- 講師は GCC あるいは Clang で動作を確認します。
- 最低限、付属の 2 つのテストケースがパスするまで実装してから提出してください。
- 提出の際は本コメントブロックを取り除いてかまいません。

## 解答のヒント

- まずは付属のテストケースが動くようにしてみましょう。
- 付属のテストケースが動くようになったら、テストケースを追加してみましょう。
  - どのようなテストを追加すると、この実装の信頼性が向上するでしょうか？
- 適宜コメントを追加して処理を説明すると、コードがわかりやすくなります。
- 余裕があれば、正常系だけでなく、異常系も考えてみましょう。
  - 付属のテストケースが動作し、リングバッファとして正しく動作する範囲であれば、
    新たに関数を追加したり定義を変更してもかまいません。

みなさんの応募をお待ちしています！楽しんで！！

*/

# include <stdio.h>
# include <stdlib.h>

// リングバッファを表す構造体
struct RingBuffer {};

// リングバッファを生成して返す
struct RingBuffer *ring_new() {
  return NULL;
}

// リングバッファ ring の末尾に要素 value を追加
void ring_push(struct RingBuffer *ring, int value) {}

// リングバッファ ring の先頭要素を取り除いて返す
int ring_pop(struct RingBuffer *ring) { return 0; }

// テスト記述のための便利関数
int fail, success;
void assert_equal(int want, int got) {
  if (want == got) {
    printf("OK: want %d, got %d\n", want, got);
    success++;
  } else {
    printf("NG: want %d, got %d\n", want, got);
    fail++;
  }
}

// テストケース群
void test_push_pop() {
  struct RingBuffer *r = ring_new();
  ring_push(r, 2);
  ring_push(r, 3);

  assert_equal(2, ring_pop(r));
  assert_equal(3, ring_pop(r));
}

int main() {
  test_push_pop();
  // 他のテストケース呼び出しはここに追記

  if (fail != 0) {
    printf("FAILED: %d/%d tests failed\n", fail, fail + success);
    return EXIT_FAILURE;
  }
  printf("PASSED: All tests finished successfully\n");
  return EXIT_SUCCESS;
}

回答と添付コード

回答

ひな形の関数定義のうち、ring_pushに関して返り値がvoidになっていてエラーを起こさないことが前提になっていましたので、intにすることでまだpopされてない値を上書きしようとしたときエラーを吐くようにしました。

添付コード

ring.c

# include <stdio.h>
# include <stdlib.h>

// リングバッファを表す構造体
struct RingBuffer {
  int *buf;           // 本体となる配列
  int size;           // 配列のサイズ
  int push_offset;    // プッシュ位置
  int pop_offset;     // ポップ位置
  int pushed_element; // プッシュした要素数
};

// リングバッファを生成して返す
struct RingBuffer *ring_new(int size) {
  // サイズが不正ならNULLポインターを返す
  if (size <= 0) return NULL;

  // リングバッファの本体となる配列を初期化
  int *buf = malloc(size* sizeof(int));
  for (int i = 0; i < size; i++)
    buf[i] = 0;

  // リングバッファを生成、初期化
  struct RingBuffer *ring = malloc(sizeof(int*) + sizeof(int) * (4));
  ring->buf = buf;
  ring->size = size;
  ring->push_offset = 0;
  ring->pop_offset = 0;
  ring->pushed_element = 0;

  return ring;
}

// リングバッファ ring の末尾に要素 value を追加
int ring_push(struct RingBuffer *ring, int value) {
  // プッシュが一周回っていたらエラー
  if (ring->pushed_element >= ring->size) return -1;
  // これからプッシュする領域に値が入っていたらエラー
  if (ring->buf[ring->push_offset] != 0) return -1;

  // 値を代入
  ring->buf[ring->push_offset] = value;
  // オフセットとプッシュ数の更新
  ring->push_offset = (ring->push_offset + 1) % ring->size;
  ring->pushed_element++;

  return 0;
}

// リングバッファ ring の先頭要素を取り除いて返す
int ring_pop(struct RingBuffer *ring) {
  // 値がまだプッシュされていなければエラー
  if (ring->pushed_element <= 0) return -1;

  // 値を取得
  int value = ring->buf[ring->pop_offset];

  // 値のリセット
  ring->buf[ring->pop_offset] = 0;
  // オフセットとプッシュ数の更新
  ring->pop_offset = (ring->pop_offset + 1) % ring->size;
  ring->pushed_element--;

  return value;
}

// リングバッファ ring を削除(メモリを解放)
int ring_delete(struct RingBuffer *ring) {
  free(ring->buf);
  free(ring);
  return 0;
}

// テスト記述のための便利関数
int fail, success;
void assert_equal(int want, int got) {
  if (want == got) {
    printf("OK: want %d, got %d\n", want, got);
    success++;
  } else {
    printf("NG: want %d, got %d\n", want, got);
    fail++;
  }
}

// テストケース群
void test_push_pop() {
  struct RingBuffer *r = ring_new(5);
  assert_equal(0, ring_push(r, 2));
  assert_equal(0, ring_push(r, 3));

  assert_equal(2, ring_pop(r));
  assert_equal(3, ring_pop(r));

  assert_equal(0, ring_delete(r));
}
void test_immediate_pop() {
  struct RingBuffer *r = ring_new(5);
  assert_equal(-1, ring_pop(r));

  assert_equal(0, ring_delete(r));
}
void test_too_much_push() {
  struct RingBuffer *r = ring_new(1);
  assert_equal(0, ring_push(r, 2));
  assert_equal(-1, ring_push(r, 3));

  assert_equal(2, ring_pop(r));

  assert_equal(0, ring_delete(r));

  r = ring_new(2);
  assert_equal(0, ring_push(r, 2));
  assert_equal(0, ring_push(r, 3));
  assert_equal(-1, ring_push(r, 4));

  assert_equal(2, ring_pop(r));
  assert_equal(3, ring_pop(r));

  assert_equal(0, ring_delete(r));
}
void test_too_much_pop() {
  struct RingBuffer *r = ring_new(1);
  assert_equal(0, ring_push(r, 2));

  assert_equal(2, ring_pop(r));
  assert_equal(-1, ring_pop(r));

  // 正常に使えるかの確認
  assert_equal(0, ring_push(r, 2));

  assert_equal(2, ring_pop(r));

  assert_equal(0, ring_delete(r));

  r = ring_new(2);
  assert_equal(0, ring_push(r, 2));
  assert_equal(0, ring_push(r, 3));

  assert_equal(2, ring_pop(r));
  assert_equal(3, ring_pop(r));
  assert_equal(-1, ring_pop(r));

  // 正常に使えるかの確認
  assert_equal(0, ring_push(r, 2));

  assert_equal(2, ring_pop(r));

  assert_equal(0, ring_delete(r));
}

int main() {
  // 他のテストケース呼び出しはここに追記
  test_push_pop();
  test_immediate_pop();
  test_too_much_push();
  test_too_much_pop();

  if (fail != 0) {
    printf("FAILED: %d/%d tests failed\n", fail, fail + success);
    return EXIT_FAILURE;
  }
  printf("PASSED: All tests finished successfully\n");
  return EXIT_SUCCESS;
}

D: 選択課題(hikaliumに担当してもらいたい方は回答してください)

なぜコンピューターにはOSが必要とされていると思いますか？現代の、もしくは将来のOSが果たすべき役割はどのようなものだと考えますか？この設問には正解はありませんので、あなたの考えを自由に記述してください。

希望しなかったので回答無し

E: 選択課題(内田に担当してもらいたい方は回答してください)

x86系CPUのメモリ管理機構が持つ「ページング」と呼ばれる仕組みを用いて実現されるOSの機能を1つ挙げ、その機能の概要と詳しい仕組みを説明してください。取り上げるOSの機能は既存の機能でも、独創的な機能でも良いです。

回答

記憶領域の仮想化を使った、メモリスワッピングによる仮想メモリの無限化が挙げられると思います。メモリスワッピングはRAMがいっぱいになった時にストレージにデータを移し替えることで、RAMの容量に制限されないメモリ量を仮想的に獲得するものです。
ページングは、このRAMとストレージ、双方に存在するデータを仮想的なメモリアドレスとして一元的に管理するために使われます。ページングは、メモリ空間を「ページ」と呼ばれる一定サイズの単位で分割して管理する仕組みで、主に仮想的に付けられるメモリアドレスと物理的なメモリ内の領域の紐づけにこの仕組みが用いられています。
OS側はメモリスワッピングを行うとき、仮想的なメモリアドレスを書き換えるのではなく、このページングで紐づけられた物理メモリの場所をページ単位で書き換えます。このことによって、OS上で動いているプログラムから見たときに全く同じアドレスで、データの所在地だけを移し替えることができるのです。

F: 任意課題

その他、何かあれば自由に書いてください。これまでにあなたが行ってきた自作OSやシステムプログラミングに関連するリポジトリや、関連する活動へのリンク、OS自作へかける熱い想いなど、なんでもOKです。

回答

普段はWebアプリケーションを作っていて、OSの提供するインターフェースに幾度となく助けられてきました。自作OSに足を踏み入れることで、これまでお世話になってきたOSのことをもっと深く知れたら嬉しいです。
どうぞよろしくお願い致します。

終わりに

ここまで読んで下さった方、どうもありがとうございます。

回答の中の情報について、間違い等ありましたら申し訳ないです。もしお気づきになりましたらそっとコメント欄に書いて、僕や未来のセキュキャン応募者にお力添えいただけると幸いです。

未来のセキュキャン応募者の皆様へですが、これはあくまで僕の回答です。
講師の方々に対する距離感等は参考にしていただけるかと思いますが、内容に関しては参考にしない方が良いかなと考えています。
僕のチンケな回答を部分部分コピペするより、己の知識と直感に従って、講師陣をわくわくさせるような熱い心からの言葉を綴っていただく方が、よっぽど熱意が伝わるはずです。
来年以降のあなた方に、幸あらんことを。

それではこの辺で。
セキュキャン運営の皆様、講師の皆様、参加者の皆様、本夏は何卒よろしくお願い致します!!

Discussion