This puzzle does not actually appear in The Little Book of Semaphores but it is based on one of the puzzles there - the cigarette smoker's problem from section 4.5. Personally, I think cigarettes are gross so we're going to reword things a touch. The idea is the same.
We have four threads in total. One thread, the producer, randomly publishes one of fuel, oxidizer, or astronauts. The remaining three threads are the consumers, or rockets, which must take their resources in the order listed previously. If a rocket doesn't get its resources in that order, it's not safe to prepare the rocket, and if it doesn't have all three, the rocket can't lift-off. Moreover, once all the rockets are prepped, we want to start a 10 second count-down, only after which may the rockets lift-off.
The preamble to our solution is a little longer than usual, in the interest of keeping the solution as a standalone:
use std::{thread, time};
use std::sync::{Arc, Barrier, Condvar, Mutex};
// NOTE if this were a crate, rather than a stand-alone
// program, we could and _should_ use the XorShiftRng
// from the 'rand' crate.
pub struct XorShiftRng {
state: u32,
}
impl XorShiftRng {
fn with_seed(seed: u32) -> XorShiftRng {
XorShiftRng { state: seed }
}
fn next_u32(&mut self) -> u32 {
self.state ^= self.state << 13;
self.state ^= self.state >> 17;
self.state ^= self.state << 5;
return self.state;
}
}
We don't really need excellent randomness for this solution—the OS scheduler injects enough already—but just something small-ish. XorShift fits the bill. Now, for our resources:
struct Resources {
lock: Mutex<(bool, bool, bool)>,
fuel: Condvar,
oxidizer: Condvar,
astronauts: Condvar,
}
The struct is protected by a single Mutex<(bool, bool, bool)>, the Boolean being a flag to indicate that there's a resource available. We hold the first flag to mean fuel, the second oxidizer, and the third astronauts. The remainder of the struct are condvars to match each of these resource concerns. The producer is a straightforward infinite loop:
fn producer(resources: Arc<Resources>) {
let mut rng = XorShiftRng::with_seed(2005);
loop {
let mut guard = resources.lock.lock().unwrap();
(*guard).0 = false;
(*guard).1 = false;
(*guard).2 = false;
match rng.next_u32() % 3 {
0 => {
(*guard).0 = true;
resources.fuel.notify_all()
}
1 => {
(*guard).1 = true;
resources.oxidizer.notify_all()
}
2 => {
(*guard).2 = true;
resources.astronauts.notify_all()
}
_ => unreachable!(),
}
}
}
On each iteration, the producer chooses a new resource—rng.next_u32() % 3—and sets the Boolean flag for that resource before notifying all threads waiting on the fuel condvar. Meanwhile, the compiler and CPU are free to re-order instructions and the memory notify_all acts like a causality gate; everything before in the code is before in causality, and likewise, afterwards. If the resource bool flip was after the notification, the wake-up would be spurious from the point of view of the waiting threads and lost from the point of view of the producer. The rocket is straightforward:
fn rocket(name: String, resources: Arc<Resources>,
all_go: Arc<Barrier>, lift_off: Arc<Barrier>) { { let mut guard = resources.lock.lock().unwrap(); while !(*guard).0 { guard = resources.fuel.wait(guard).unwrap(); } (*guard).0 = false; println!("{:<6} ACQUIRE FUEL", name); } { let mut guard = resources.lock.lock().unwrap(); while !(*guard).1 { guard = resources.oxidizer.wait(guard).unwrap(); } (*guard).1 = false; println!("{:<6} ACQUIRE OXIDIZER", name); } { let mut guard = resources.lock.lock().unwrap(); while !(*guard).2 { guard = resources.astronauts.wait(guard).unwrap(); } (*guard).2 = false; println!("{:<6} ACQUIRE ASTRONAUTS", name); } all_go.wait(); lift_off.wait(); println!("{:<6} LIFT OFF", name); }
Each thread, regarding the resource requirements, waits on the condvar for the producer to make it available. A race occurs to re-acquire the mutex, as discussed, and only a single thread gets the resource. Finally, once all the resources are acquired, the all_go barrier is hit to delay any threads ahead of the count-down. Here we need the main function:
fn main() {
let all_go = Arc::new(Barrier::new(4));
let lift_off = Arc::new(Barrier::new(4));
let resources = Arc::new(Resources {
lock: Mutex::new((false, false, false)),
fuel: Condvar::new(),
oxidizer: Condvar::new(),
astronauts: Condvar::new(),
});
let mut rockets = Vec::new();
for name in &["KSC", "VAB", "WSMR"] {
let all_go = Arc::clone(&all_go);
let lift_off = Arc::clone(&lift_off);
let resources = Arc::clone(&resources);
rockets.push(thread::spawn(move || {
rocket(name.to_string(), resources,
all_go, lift_off)
}));
}
thread::spawn(move || {
producer(resources);
});
all_go.wait();
let one_second = time::Duration::from_millis(1_000);
println!("T-11");
for i in 0..10 {
println!("{:>4}", 10 - i);
thread::sleep(one_second);
}
lift_off.wait();
for jh in rockets {
jh.join().unwrap();
}
}
Note that, roughly, the first half of the function is made up of the barriers and resources or rocket threads. all_go.wait() is where it gets interesting. This main thread has spawned all the children and is now blocked on the all-go signal from the rocket threads, meaning they've collected their resources and are also blocked on the same barrier. That done, the count-down happens, to add a little panache to the solution; meanwhile, the rocket threads have started to wait on the lift_off barrier. It is, incidentally, worth noting that the producer is still producing, drawing CPU and power. Once the count-down is complete, the rocket threads are released, the main thread joins on them to allow them to print their goodbyes, and the program is finished. Outputs will vary, but here's one representative example:
KSC ACQUIRE FUEL WSMR ACQUIRE FUEL WSMR ACQUIRE OXIDIZER VAB ACQUIRE FUEL WSMR ACQUIRE ASTRONAUTS KSC ACQUIRE OXIDIZER KSC ACQUIRE ASTRONAUTS VAB ACQUIRE OXIDIZER VAB ACQUIRE ASTRONAUTS T-11 10 9 8 7 6 5 4 3 2 1 VAB LIFT OFF WSMR LIFT OFF KSC LIFT OFF