注意: 最新版のドキュメントをご覧ください。この第1版ドキュメントは古くなっており、最新情報が反映されていません。リンク先のドキュメントが現在の Rust の最新のドキュメントです。
私たちの2番目のプロジェクトとして、古典的な並行処理問題を考えていきましょう。「食事する哲学者(the dining philosophers)」とよばれる問題です。 オリジナルは1965年にダイクストラ(Dijkstra)により考案されましたが、ここではトニー・ホーア(Tony Hoare)による1985年の この論文 を少しばかり脚色したバージョンを用います。
昔々、裕福な慈善家が、5人の高名な哲学者が宿泊できるカレッジを寄付しました。それぞれの哲学者には思索活動にふさわしい部屋が与えられました; また共用のダイニングルームもあり、そこには丸いテーブルが置かれ、5人それぞれが専用で使うイス5脚で取り囲まれていました。 彼らはテーブルを反時計回りに座ります。哲学者の左側にはそれぞれ金のフォークが配され、 中央には大きなボウルに入ったスパゲッティが常に補充されていました。哲学者は大半の時間を思慮に費やすのですが; 空腹になった時は、ダイニングルームに出向き、自分専用のイスに座り、左側のフォークを取上げ、スパゲッティに突き刺します。 しかし、絡まり合ったスパゲッティを口元まで運ぶには2本目のフォークが必要でした。なので哲学者は自分の右側にあるフォークも使う必要がありました。 食べ終わったら両側のフォークを元に戻し、席から立ちあがって、思索活動を続けます。 もちろん、1本のフォークは同時に1人の哲学者しか使えません。他の哲学者が食事したければ、 フォークが再び戻されるまで待たねばなりません。
この古典問題は並行処理特有の要因を際立たせます。その実装にあたっては少し注意が必要となるからです: 単純な実装ではデッドロックの可能性があるのです。例えば、この問題を解く単純なアルゴリズムを考えてみましょう:
さて、このような一連の出来事を想像してみましょう:
この問題を解決する方法はいくつかあります。チュートリアルでは独自の解法をとります。
さっそく、 cargo を使って新規プロジェクトを作り始めましょう:
$ cd ~/projects
$ cargo new dining_philosophers --bin
$ cd dining_philosophers
それでは、問題をモデル化するところから始めましょう。 src/main.rs にて、哲学者から手を付けていきます:
struct Philosopher { name: String, } impl Philosopher { fn new(name: &str) -> Philosopher { Philosopher { name: name.to_string(), } } } fn main() { let p1 = Philosopher::new("Judith Butler"); let p2 = Philosopher::new("Gilles Deleuze"); let p3 = Philosopher::new("Karl Marx"); let p4 = Philosopher::new("Emma Goldman"); let p5 = Philosopher::new("Michel Foucault"); }
訳注: ソースコード中に登場する哲学者は、ジュディス・バトラー(Judith Butler)、ジル・ドゥルーズ(Gilles Deleuze)、 カール・マルクス(Karl Marx)、エマ・ゴールドマン(Emma Goldman)、ミシェル・フーコー(Michel Foucault)の5人。
ここでは、哲学者を表す struct (構造体) を作ります。まずは名前だけで十分でしょう。
名前には &str 型ではなく String 型を選びました。一般的に、データを所有する型を用いた方が、
データを参照する型の利用よりも簡単になります。
では続けましょう:
fn main() { struct Philosopher { name: String, } impl Philosopher { fn new(name: &str) -> Philosopher { Philosopher { name: name.to_string(), } } } }impl Philosopher { fn new(name: &str) -> Philosopher { Philosopher { name: name.to_string(), } } }
この impl ブロックは Philosopher 構造体に関する定義を与えます。ここでは、 new という「関連関数(associated function)」を定義します。
最初の行は次の通りです:
fn new(name: &str) -> Philosopher {
関数は &str 型の引数1つ、 name をとります。これは他の文字列への参照です。そして Philosopher 構造体のインスタンスを返します。
Philosopher { name: name.to_string(), }
関数は新しい Philosopher インスタンスを作成し、その name フィールドに引数 name を設定します。
ここでは引数を直接設定するのではなく、 .to_string() を呼び出しています。これにより &str が指す文字列のコピーが作られ、
Philosopher の name フィールド型に合わせた新しい String が得られます。
なぜ引数に直接 String を受付けないのかって?いい質問です。仮に String をとるとしたら、呼出し元は &str 値をもっていますから、
呼び出し元でメソッドを呼ぶ必要がでてしまいます。この利便性の代償として、 常に コピーが作られてしまいます。
今回のプログラムでは、短い文字列しか与えないことが分かっているため、これは大して重要な問題ではありません。
最後の注意点として: ここは Philosopher を定義しただけで、何もしていないように見えます。Rust言語は「式ベース(expression based)」なので、
Rustではほとんどが値を返す式となります。関数についても同じことが言え―最後の式が自動的に戻り値となります。
ここでは関数内の最後の式で新しい Philosopher を生成し、それを戻り値としているのです。
この new() という名前、Rustにとって特別な意味を持ちませんが、構造体の新しいインスタンスを生成する関数としてよく用いられます。
その理由について話す前に、再び main() を見ていきましょう:
fn main() { let p1 = Philosopher::new("Judith Butler"); let p2 = Philosopher::new("Gilles Deleuze"); let p3 = Philosopher::new("Karl Marx"); let p4 = Philosopher::new("Emma Goldman"); let p5 = Philosopher::new("Michel Foucault"); }
ここでは、5つの新しい哲学者に対して5つの変数束縛を作ります。仮に new 関数を定義 しない なら、次のように書く必要があります:
fn main() { let p1 = Philosopher { name: "Judith Butler".to_string() }; let p2 = Philosopher { name: "Gilles Deleuze".to_string() }; let p3 = Philosopher { name: "Karl Marx".to_string() }; let p4 = Philosopher { name: "Emma Goldman".to_string() }; let p5 = Philosopher { name: "Michel Foucault".to_string() }; }
これでは面倒ですよね。 new の利用には他の利点もありますが、今回のような単純なケースでも、
利用側コードをシンプルにできるのです。
下準備が終ったので、ここでの残る問題、哲学者の問題に取り組める多くの方法があります。 まずは逆順に: 哲学者が食事を終わらせる部分から始めていきましょう。この小さなステップでは、 メソッドを1つ作り、全ての哲学者に対して呼び出します:
struct Philosopher { name: String, } impl Philosopher { fn new(name: &str) -> Philosopher { Philosopher { name: name.to_string(), } } fn eat(&self) { println!("{} is done eating.", self.name); } } fn main() { let philosophers = vec![ Philosopher::new("Judith Butler"), Philosopher::new("Gilles Deleuze"), Philosopher::new("Karl Marx"), Philosopher::new("Emma Goldman"), Philosopher::new("Michel Foucault"), ]; for p in &philosophers { p.eat(); } }struct Philosopher { name: String, } impl Philosopher { fn new(name: &str) -> Philosopher { Philosopher { name: name.to_string(), } } fn eat(&self) { println!("{} is done eating.", self.name); } } fn main() { let philosophers = vec![ Philosopher::new("Judith Butler"), Philosopher::new("Gilles Deleuze"), Philosopher::new("Karl Marx"), Philosopher::new("Emma Goldman"), Philosopher::new("Michel Foucault"), ]; for p in &philosophers { p.eat(); } }
最初は main() から見ていきます。哲学者たちに5つの変数束縛を個別に行うのではなく、代わりに Vec<T> を用いました。
Vec<T> は「ベクタ(vector)」とも呼ばれる、可変長の配列型です。ベクタの走査には for ループを使っているため、
それぞれの哲学者への参照が順番に得られれます。
ループ本体の中では、上記で定義した p.eat() を呼び出します:
fn eat(&self) { println!("{} is done eating.", self.name); }
Rustでは、メソッドは明示的な self パラメータを取ります。なので eat() はメソッドとなり、
new() は self を取らないため関連関数となります。最初の eat() バージョンでは、哲学者の名前と、
食事が終わったことを表示するだけです。このプログラムを実行すると次の出力がえられるはずです:
Judith Butler is done eating.
Gilles Deleuze is done eating.
Karl Marx is done eating.
Emma Goldman is done eating.
Michel Foucault is done eating.
これだけなら簡単ですね、出来ました!私たちはまだ真の問題を実装していませんから、実際のところは出来ていませんけど!
続いて、哲学者たちが一瞬で食事を終えるのではなく、本当に食事するようにしたいです。これが次のバージョンです:
use std::thread; use std::time::Duration; struct Philosopher { name: String, } impl Philosopher { fn new(name: &str) -> Philosopher { Philosopher { name: name.to_string(), } } fn eat(&self) { println!("{} is eating.", self.name); thread::sleep(Duration::from_millis(1000)); println!("{} is done eating.", self.name); } } fn main() { let philosophers = vec![ Philosopher::new("Judith Butler"), Philosopher::new("Gilles Deleuze"), Philosopher::new("Karl Marx"), Philosopher::new("Emma Goldman"), Philosopher::new("Michel Foucault"), ]; for p in &philosophers { p.eat(); } }use std::thread; use std::time::Duration; struct Philosopher { name: String, } impl Philosopher { fn new(name: &str) -> Philosopher { Philosopher { name: name.to_string(), } } fn eat(&self) { println!("{} is eating.", self.name); thread::sleep(Duration::from_millis(1000)); println!("{} is done eating.", self.name); } } fn main() { let philosophers = vec![ Philosopher::new("Judith Butler"), Philosopher::new("Gilles Deleuze"), Philosopher::new("Karl Marx"), Philosopher::new("Emma Goldman"), Philosopher::new("Michel Foucault"), ]; for p in &philosophers { p.eat(); } }
大した変更はありません。順に見ていきましょう。
fn main() { use std::thread; }use std::thread;
use は名前をスコープに持ち込みます。標準ライブラリから thread モジュールを使いたいので、 use が必要になります。
fn eat(&self) {
println!("{} is eating.", self.name);
thread::sleep(Duration::from_millis(1000));
println!("{} is done eating.", self.name);
}
今回は間に sleep を挟んで、2つのメッセージを出力します。これで哲学者が食事をする時間をシミュレートしましょう。
このプログラムを実行すると、哲学者たちが順番に食事する様子がわかります:
Judith Butler is eating.
Judith Butler is done eating.
Gilles Deleuze is eating.
Gilles Deleuze is done eating.
Karl Marx is eating.
Karl Marx is done eating.
Emma Goldman is eating.
Emma Goldman is done eating.
Michel Foucault is eating.
Michel Foucault is done eating.
素晴らしい!ここまで来ました。残る問題はたった1つ: この問題の核心である並行性に関して、実際には手を付けていませんね!
哲学者たちを並行に食事させるには、小さな変更を加える必要があります。これが次のイテレーションです:
use std::thread; use std::time::Duration; struct Philosopher { name: String, } impl Philosopher { fn new(name: &str) -> Philosopher { Philosopher { name: name.to_string(), } } fn eat(&self) { println!("{} is eating.", self.name); thread::sleep(Duration::from_millis(1000)); println!("{} is done eating.", self.name); } } fn main() { let philosophers = vec![ Philosopher::new("Judith Butler"), Philosopher::new("Gilles Deleuze"), Philosopher::new("Karl Marx"), Philosopher::new("Emma Goldman"), Philosopher::new("Michel Foucault"), ]; let handles: Vec<_> = philosophers.into_iter().map(|p| { thread::spawn(move || { p.eat(); }) }).collect(); for h in handles { h.join().unwrap(); } }use std::thread; use std::time::Duration; struct Philosopher { name: String, } impl Philosopher { fn new(name: &str) -> Philosopher { Philosopher { name: name.to_string(), } } fn eat(&self) { println!("{} is eating.", self.name); thread::sleep(Duration::from_millis(1000)); println!("{} is done eating.", self.name); } } fn main() { let philosophers = vec![ Philosopher::new("Judith Butler"), Philosopher::new("Gilles Deleuze"), Philosopher::new("Karl Marx"), Philosopher::new("Emma Goldman"), Philosopher::new("Michel Foucault"), ]; let handles: Vec<_> = philosophers.into_iter().map(|p| { thread::spawn(move || { p.eat(); }) }).collect(); for h in handles { h.join().unwrap(); } }
main() 内のループ変更と、1ヵ所の追加で全部です!まずは前半の変更から:
let handles: Vec<_> = philosophers.into_iter().map(|p| { thread::spawn(move || { p.eat(); }) }).collect();
たった5行ですが、内容の濃い5行になっています。では見ていきましょう。
fn main() { let handles: Vec<_> = }let handles: Vec<_> =
ここでは新しい束縛、 handles を導入します。今から新しいスレッドを作成していきますが、
スレッドはそのスレッドを制御するハンドルを返すのでこの名前としました。後ほど議論する問題があるため、
ここでは明示的な型アノテーションが必要となります。 _ は型プレースホルダです。
つまり「 handles は何らかの型のベクトルとするが、その型が何であるかはRustが解決せよ。」と言っています。
philosophers.into_iter().map(|p| {
哲学者のリストに対して into_iter() を呼び出します。このメソッドは、哲学者の所有権を持つイテレータを生成します。
スレッドに各要素を渡すため、このようにしました。イテレータに対して map を呼び出し、その引数として要素毎に順番に呼ばれるクロージャを渡します。
thread::spawn(move || {
p.eat();
})
ここが並行実行される部分です。 thread::spawn 関数はクロージャを1つ引数にとり、新しいスレッド上でそのクロージャを実行します。
このクロージャは特別なアノテーション、 move を必要とします。これによりキャプチャする値の所有権がクロージャ内へと移動されます。
今回のケースでは、 map 関数の変数 p が該当します。
スレッド内では、 p に対して eat() を呼び出しておしまいです。 thread::spawn 呼び出しの末尾にセミコロンを置かないことで、
式としている点に注意してください。正しい戻り値を返すために、この区別は重要です。詳細については、
式 vs. 文 を参照ください。
}).collect();
最後に、 map 呼び出しの結果をまとめ上げます。 collect() は何らかのコレクション型を生成しますが、要求する戻り値型アノテーションを必要とします:
ここでは Vec<T> です。またその要素は thread::spawn 呼び出しの戻り値、つまり各スレッドへのハンドルとなっています。
フゥー!
for h in handles { h.join().unwrap(); }
main() の最後に、ハンドルへの join() 呼び出しをループし、各スレッド実行が完了するまで実行をブロックします。
これにより、プログラム終了前にスレッド処理が完了すると保証します。
このプログラムを実行すると、哲学者たちが順不同に食事するさまが見られるでしょう! マルチスレッド処理だ!
Judith Butler is eating.
Gilles Deleuze is eating.
Karl Marx is eating.
Emma Goldman is eating.
Michel Foucault is eating.
Judith Butler is done eating.
Gilles Deleuze is done eating.
Karl Marx is done eating.
Emma Goldman is done eating.
Michel Foucault is done eating.
あれ、フォークはどこ行ったの?まだモデル化していませんでしたね。
という訳で、新しい struct を作っていきましょう:
use std::sync::Mutex; struct Table { forks: Vec<Mutex<()>>, }
この Table は Mutex のベクトルを保持します。ミューテックスは並行処理を制御するための機構です:
その内容へ同時アクセスできるのは1スレッドに限定されます。これは正に今回のフォークに求められる性質です。
単に保持するだけで、実際に値を使うあても無いため、ミューテックスの中身は空タプル () とします。
プログラムで Table を使うよう変更しましょう:
use std::thread; use std::time::Duration; use std::sync::{Mutex, Arc}; struct Philosopher { name: String, left: usize, right: usize, } impl Philosopher { fn new(name: &str, left: usize, right: usize) -> Philosopher { Philosopher { name: name.to_string(), left: left, right: right, } } fn eat(&self, table: &Table) { let _left = table.forks[self.left].lock().unwrap(); thread::sleep(Duration::from_millis(150)); let _right = table.forks[self.right].lock().unwrap(); println!("{} is eating.", self.name); thread::sleep(Duration::from_millis(1000)); println!("{} is done eating.", self.name); } } struct Table { forks: Vec<Mutex<()>>, } fn main() { let table = Arc::new(Table { forks: vec![ Mutex::new(()), Mutex::new(()), Mutex::new(()), Mutex::new(()), Mutex::new(()), ]}); let philosophers = vec![ Philosopher::new("Judith Butler", 0, 1), Philosopher::new("Gilles Deleuze", 1, 2), Philosopher::new("Karl Marx", 2, 3), Philosopher::new("Emma Goldman", 3, 4), Philosopher::new("Michel Foucault", 0, 4), ]; let handles: Vec<_> = philosophers.into_iter().map(|p| { let table = table.clone(); thread::spawn(move || { p.eat(&table); }) }).collect(); for h in handles { h.join().unwrap(); } }
変更がたくさん!とはいえ、このイテレーションで、動作するプログラムが出来ました。細かく見ていきましょう:
fn main() { use std::sync::{Mutex, Arc}; }use std::sync::{Mutex, Arc};
ここでは std::sync パッケージからもう一つの構造体: Arc<T> を利用します。その詳細は使うときに説明します。
struct Philosopher { name: String, left: usize, right: usize, }
Philosopher に2つのフィールドを追加する必要があります。哲学者はそれぞれ2本のフォークを使います:
1本は左手に、もう1本は右手に。フォークの表現はベクトルのインデックスに対応するため、ここでは usize 型を使います。
2つの値は Table が保持する forks のインデクス値を表しています。
fn new(name: &str, left: usize, right: usize) -> Philosopher { Philosopher { name: name.to_string(), left: left, right: right, } }
インスタンス生成時に left と right の値が必要になりますから、 new() を拡張しました。
fn eat(&self, table: &Table) { let _left = table.forks[self.left].lock().unwrap(); thread::sleep(Duration::from_millis(150)); let _right = table.forks[self.right].lock().unwrap(); println!("{} is eating.", self.name); thread::sleep(Duration::from_millis(1000)); println!("{} is done eating.", self.name); }
新しい行が3つあります。新しい引数 table も追加しました。 Table が保持するフォークのリストにアクセスし、
フォークにアクセスするため self.left と self.right をインデクス値に用います。そのインデクスから Mutex が得られたら、
lock() を呼び出します。ミューテックスが別スレッドから並行アクセスされていた場合は、有効になるまでブロックされるでしょう。
またフォークを取上げる操作が一瞬で終わらないよう、最初のフォークを取上げてから2つ目のフォークを取上げるまでの間に thread::sleep を呼び出します。
lock() 呼び出しは失敗する可能性があり、その場合は、プログラムをクラッシュさせます。この状況は、ミューテックスが 「poisoned」 状態、
つまりロック保持中のスレッドがパニックした場合にしか発生しません。つまり今は起こりえないため、単に unwrap() を使っています。
もう一つの変わった点として: 結果を _left と _right と名づけました。このアンダースコアはなにもの?
ええと、ロック内ではこれらの値を 使う 予定がありません。単にロックを獲得したいだけです。
そうなると、Rustは値が未使用だと警告してくるでしょう。アンダースコアを使えば、Rustにこちらの意図を伝えることができ、
警告されなくなるのです。
ロックの解放はどうしましょう?はい、 _left と _right がスコープから抜けるとき、自動的に解放されます。
let table = Arc::new(Table { forks: vec![
Mutex::new(()),
Mutex::new(()),
Mutex::new(()),
Mutex::new(()),
Mutex::new(()),
]});
続いて、 main() では、新しい Table を作って Arc<T> に包んでいます。「arc」は「アトミック参照カウント(atomic reference count)」を意味し、
複数スレッドから Table を共有するために必要となります。共有するときは参照カウントを増やし、
各スレッドの終了時にはカウントを減らします。
let philosophers = vec![ Philosopher::new("Judith Butler", 0, 1), Philosopher::new("Gilles Deleuze", 1, 2), Philosopher::new("Karl Marx", 2, 3), Philosopher::new("Emma Goldman", 3, 4), Philosopher::new("Michel Foucault", 0, 4), ];
Philosopher のコンストラクタには left と right の値を渡す必要があります。ここではもう1つ細かい話がありますが、
これは_非常に_重要な部分です。規則性という点では、最後以外は特に問題ありません。ムッシュ・フーコー(Foucault)は 4, 0 を引数にとるべきですが、
代わりに、 0, 4 としています。これはデッドロックを防ぐためのものです。実は: 哲学者の一人は左利きだったのです!
これは問題解決の一つのやり方ですが、私の見立てでは、最も単純な方法です。実引数の順番を変更すれば、デッドロックが生じるのを観測できるでしょう。
let handles: Vec<_> = philosophers.into_iter().map(|p| { let table = table.clone(); thread::spawn(move || { p.eat(&table); }) }).collect();
最後に、 map() / collect() ループの中で、 table.clone() を呼び出します。 Arc<T> の clone() メソッドにより参照カウントが増加し、
スコープ外に出たときは、参照カウントが減算されます。これは、スレッドを跨いで table への参照が何個あるかを知るのに必要です。
参照カウントを行わないと、いつ解放すればよいかが分からなくなってしまいます。
ここでは新しい束縛 table を導入して、古い方を覆い隠していることに気付くでしょう。
これは2つの異なる名前を必要としないため、よく用いられる方法です。
これで、プログラムが動くようになりました!2人の哲学者だけが同時に食事できるようになり、次のような出力がえられるでしょう:
Gilles Deleuze is eating.
Emma Goldman is eating.
Emma Goldman is done eating.
Gilles Deleuze is done eating.
Judith Butler is eating.
Karl Marx is eating.
Judith Butler is done eating.
Michel Foucault is eating.
Karl Marx is done eating.
Michel Foucault is done eating.
おめでとう!古典並行処理問題をRustを使って実装できましたね。