Computer programmers like to use real-world analogies to simplify the task of explaining how a given idea works or to champion the notion that their theory is the most practical for modeling the real world.
This is a trend perhaps most famous in the Object Oriented paradigm, where you can't open a text-book without being told that an Employee IS A Person, and a SalariedEmployee IS AN Employee, as is an HourlyEmployee. These canonical examples aren't always perfect (I'd argue that a sub-class relationship between and Employee and a Person is inappropriate), but they get the point across clearly in describing the basics of inheritance.
Another paradigm that tends to champion its own set of metaphors is Concurrency Oriented Programming, perhaps most visibly represented by Joe Armstrong and his Erlang programming language. Armstrong is quite fond of the analogy of a program as a sort of highway, with individual cars autonomously sending messages to and responding to messages from other cars based on localized rules. It only makes sense, then, that those of us looking to improve the usability of constructs for shared memory concurrency would also like to have our own metaphors.
Consider, for instance, our initial plan to use trains as an analogy for shared memory concurrency. The obvious relationships are that trains are threads of execution and tracks are code space. We also have switches and signals that can provide direction the way simple synchronization constructs like locks do. Two trains can run on parallel tracks (executing the same, non-critical block of code simultaneously) or can be running in completely different regions of the track space (executing different regions of code). If two trains are running on parallel tracks that suddenly cut down to a single lane, then that would obviously seem to be a critical section governed by a switch/signal...but this is where the problems start to come in. Why does this section of track need to be only a single lane? What is being modified that would break if there were two trains continuing to run side by side?
"Perhaps", you say, "there's a bridge that can only support the weight of a single train." This works here, when the trains are executing the same chunk of code, but what about the example of, say, a mutator and an accessor for a single state variable being called at the same time? How do we explain the notion that Train A has to stop and wait for Train B, miles and miles away on a completely distinct length of track, to finish crossing some seemingly arbitrary boundary before Train A can continue along its route?
The problem is that, unlike distributed memory forms of parallelism such as actor models, where each process has its own unique hunk of memory that only it can touch and where explicit communication is required to share data with other processes, shared memory requires us to be sure that our analogy contains some explicit way of representing memory. Otherwise, we run into problems like those above. This forces us to separate the address space utilized by all threads in a given process and the "code space" they traverse over time as distinct (though adjacent) spaces. If we try to limit ourselves to the code space and the agents moving through it, then we run into a situation where we need our limited set of representatives must exhibit either multilocation -- that is to say, the ability for something to be in multiple "places" simultaneously -- or co-location -- the potential for two "different" things to occupy the same space -- depending on how we want to represent the sorts of simultaneous memory accesses we want to avoid. Any metaphysician worth their salt will tell you that this is absurd if you're looking to represent anything resembling reality.
There are certainly some metaphors for which this doesn't cause a problem, they just aren't as immediately attention grabbing as those that have already been suggested. I've long been fond of this example I came up with on 2 hours of sleep in the middle of a presentation years ago:
Assume you live with another person, and, being kind of stupid (like computers), you refuse to freely stock your fridge with whatever you buy at the store. Instead, you need to place your groceries in containers that always sit in your fridge and are marked for specific purposes, but not based on their current contents. Now, suppose you come home one day with a nice carton of orange juice. You take one of the containers marked "drinks" and you dump out its current contents, fill it with the orange juice you just bought, and wander off happily thinking of all the enjoyment you'll get from consuming it later.
Now, before you get back to your orange juice-y revelry, your roommate shows up with a nice bottle of freshly stilled moonshine. Unaware of your intentions, he dumps out your orange juice and fills up the container it once inhabited. You walk into the kitchen, take out the container now filled with potent, put-hair-on-your-chest booze, chug the whole container, and wind up in the hospital getting your stomach pumped.
Boom, race conditions.
Perhaps, then, a fitting analogy for shared memory concurrency is a busy kitchen with a multitude of chefs trying to all get their meals out on time and their ingredients in place. We have threads (the chefs themselves) executing code (going about various kitchen-y tasks) and accessing shared memory (refrigerators, counter tops, ovens, and whatever else) containing multiple possible values (the food items therein).
This analogy, unfortunately, doesn't lend itself as well to traditional, low level abstractions for thread scheduling, as there is nothing external to the actors that governs them with set policies. What use is it, then? Perhaps my biases are skewing my judgement, but, for one thing, it seems to have potential for describing the sorts of shared memory "message passing" in Object Oriented Programming that I've discussed implementing in the past.
No comments:
Post a Comment