情報学

香川県の金刀比羅宮は、表参道から御本宮まで 785 段の石段が続きます。1 段ずつか 2 段ずつ上るとき、上り方は何通りあるでしょうか。小さい数で考えると、1 段なら 1 通り、2 段なら 2 通り、3 段なら 3 通りです。

n 段目には、n − 1 段目から 1 段か、n − 2 段目から 2 段で着きます。だから、n 段の上り方は、n − 1 段と n − 2 段の上り方の和です。情報 I で学ぶ関数を使うと、この決まりをそのまま数行のプログラムに書けます。関数の中で自分自身を呼ぶこの書き方を、再帰と呼びます。

ところが、このプログラムは 30 段で 269 万回以上も関数を呼び出します。同じ段数の答えを、何度も計算し直しているからです。呼び出しの回数は、段数が 1 増えるごとに約 1.6 倍になります。785 段では 165 けたの回数になり、今のコンピュータでも終わりません。

そこで、1 段目から順に答えをリストに書きためていきます。前の 2 つを足すだけなので、785 段でも足し算は 784 回で済み、答えは 164 けたの数になります。大学の「アルゴリズムとデータ構造」の授業では、この方法を動的計画法と呼びます。手間がデータの大きさに応じてどう増えるか(計算量)を見積もる方法も学びます。

スマートフォンでは、音楽を聴きながら地図を見て、メッセージも受け取れます。けれども、CPU の 1 つのコアが一度に進められるプログラムは、基本的に 1 つです。OS がそれぞれのアプリに少しずつ順番に時間を割り当て、すばやく切り替えているのです。

この方法の始まりの 1 つが、1961 年にマサチューセッツ工科大学(MIT)で公開された CTSS です。それまでは、プログラムを書いたカードを係の人に預け、何時間も結果を待つのが普通でした。CTSS では答えが数秒で返り、利用者ごとのパスワードを初めて使ったコンピュータとしても知られています。

切り替えの間隔には、ちょうどよい長さがあります。例えば、1 回の切り替えに 0.1 ミリ秒かかるとします。10 ミリ秒ごとに切り替えれば、むだになる時間は約 1% です。1 ミリ秒ごとにすると反応は速くなりますが、むだは約 9% に増えます。

大学の OS の授業では、こうした切り替えの順番の決め方(スケジューリング)や、メモリの分け方を学びます。参照基準も、メモリ管理やプロセス管理を OS の基本機能に挙げています。情報 I で学ぶ CPU とメモリのしくみが、その土台です。