Mesa was a strongly typed multithreading high level programming
language developed at Xerox PARC in the '70s. Today its name is remembered
in the context of Monitors, a high level synchronization type.
Technical details:
C.A.R. Hoare introduced the monitor type in 1974. Major programming
languages today still do not implement it directly (Java comes close), so
programmers must explicitly implement it using locks and condition variables.
Consider this simplified example code for multiple Klaproths
running simultaneously:
Lock eat_death_lock;
Condition node_marked(eat_death_lock);
void klaproth() {
eat_death_lock.acquire();
if (nodes_to_be_killed == 0)
node_marked.wait();
--nodes_to_be_killed;
Node node = marked_nodes_list.pop_first();
eat_death_lock.release();
kill_node(node);
}
void mark_node(Node node) {
eat_death_lock.acquire();
++nodes_to_be_killed;
marked_nodes_list.push_back(node);
node_marked.signal();
eat_death_lock.release();
}
When a condition variable is signaled, a Hoare-style
monitor will transfer execution the next thread waiting on it, if there
is one. Thus the thread waiting on the condition variable will always be able
to run when when the condition returns, i.e. with the code given above, on return
from node_marked.wait(), it is guaranteed that there will be nodes
available to be killed.
This is inefficient to implement however, and the way condition variables
are implemented in most systems today, as introduced by Mesa, does
not transfer immediately execution to a waiting thread when it is signaled.
Instead, the target thread is put on the ready queue (queue of threads
waiting to run), and will run some short time in the future. The problem is
that if new klaproth() now enters the system in the split second
after nodes_to_be_killed is incremented but before
the already waiting klaproth() gets to run, the new klaproth()
will eat up that node. So we need to modify klaproth() to take
this (unlikely case) into account:
void klaproth() {
eat_death_lock.acquire();
while (nodes_to_be_killed == 0)
node_marked.wait();
--nodes_to_be_killed;
Node node = marked_nodes_list.pop_first();
eat_death_lock.release();
kill_node(node);
}