Friday, January 4, 2008

Dining Philosophers and Quarreling Kids

Concurrency in general and in particular making concurrent processes smoothly share resources are hard programming problems. The classic problem illustrating concurrency is the dining philosophers problem where the shared resources are forks. The problems the philosophers can get include resource starvation, deadlock and livelock. (Note: dining philosophers has a slight resemblence of the game of musical chairs)

The quarreling kids problem
A much less classic but way more realistic concurrency problem is the quarreling kids problem, i.e. when providing N resources (e.g. food or toys) to M kids (who might be either spoiled, tired or hungry) several situations can occur:
  1. N < M
    • Typical result: Quarreling kids since some kids doesn't get any resources
  2. N ≥ M and N mod M != 0
    • Typical result: Quarreling kids since resources are unevenly distributed
  3. N &ge M and N mod M == 0
    • Can go smoothly, but can lead to quarreling kids if:
      • the resources differ, e.g. in type, size, shape or color
      • the order/speed resources are distributed in
      • the resources doesn't match the recipient's expectations (stereotypical: the girl doesn't get the pink colored and the boy doesn't get the blue colored)
Solutions to the quarreling kids problem?
An obvious solution approach could be to let the kids select resources themselves, but that will typically make the kids that selects first happy and the rest less happy and start quarreling, and if the kids select resources at the same time that also typically leads to quarreling during selection process.
A second approach is to provide non-discrete resources that are of infinite divisible nature, but that has unfortunately practical lower boundaries.
A third approach is to provide personalized (heterogeneous) resources, so every kids gets what they anticipate, but this requires both detailed knowledge of each kids preference and is impractical due to either limited resource budget, limited resource availability or possibly other reasons (e.g. nutrition?).

So what might work?

A) Provide homogeneous resources (where N ≥ M and N mod M == 0) could work, this way the kids are likely to feel that they are fairly treated.

But what if there are fewer resources than kids (N < M)

B) Provide resources that supports and encourages communication and interaction, i.e. where sharing pays off (e.g. in a more or less continuous sport like soccer or a turn-based board game)

This sounds awfully politically correct, what is the point?

The point is that solving the quarreling kids problem most likely requires solutions that:
  1. Avoids resource sharing by having dedicated resources to each kid (e.g. a pair of skates each), like in A above, or
  2. Provides resources that are being competed for under a set of communicated and agreed-upon cooperative rules as in soccer, or waited for under as set of cooperative rules in a turn-based board game, like in B above. (Without cooperation quarreling about resources will occur)
From a programming perspective, the quarreling kids (processes) problem with dedicated resources don't have any sharing problems, and can entirely avoid complex synchronization mechanisms (e.g. locks and mutexes), communication between the kids (processes) are done using speech (messages). This approach is similar to message-based parallelism such as using (asyncronous) messages in MPI and Erlang or channels in Stackless Python.

But what is the computational analogy for solution 2?

No comments: