concurrency

So, I was stood in a queue in Boots this morning, and thinking about how using one queue for multiple checkouts guarantees fairness. If the checkouts are guaranteed to be able to deal with any customer eventually, and they always take their next customer from the front of the queue, you can guarantee in turn that every customer will get handled eventually, and that they will be handled in the order they arrived. The system exhibits safety properties, since only one person can leave the queue to go to any one checkout at once, and it exhibits liveness properties, in that the queue is guaranteed to empty eventually, and it exhibits fairness properties, in the ordering of people in the queue. It also shows some signs of being efficient, in that there's no time wasted in negotiating who goes next (as you'd see without a queue), nor do the checkout operators have to waste time finding people (as might occur with table service).

But alas! There is an inefficiency. The head of the queue is located several steps away from even the nearest of the checkouts. This means that after the checkout operator calls the next person over, that operator is sat idle for 2 or 3 seconds until the next person arrives. If each transaction takes a minute, then this latency between the queue and the checkout imposes a massive 3 to 5 percent penalty over optimal checkout operation. To fix this, the head of the queue needs to move closer to the point at where the work is done. In practical terms you can usually make this easier by dividing the queue up into several queues, but then you lose your fairness properties, and some safety properties (since a problem at one till stalls the whole thing). Dilemma.

I guess this means I spend too long thinking about computing problems.