Mesa (idea)

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);
}