Saturday, August 29, 2009

Block The Emergency Exit for Faster Evacuations

NewScientist reports that Japanese physicists timed a crowd of 50 women(?) as they exited as fast as possible through a door. They then repeated the experiment with a 20 cm (10 inch) wide pillar placed 65 cm (2 feet) in front of the exit to the left-hand side. The obstacle increased the exit throughput by an extra seven people per minute.
"Usually, the exit becomes clogged by people competing for the small space, and the crowd is slowed. The pillar blocks pedestrians arriving at the exit from the left so effectively that the number of people attempting to occupy the space just in front of the exit is reduced, says Yanagisawa. With reduced crowding there are fewer conflicts and the outflow rate increases."

How does this apply to computer performance? Think polling systems, where there are multiple waiting lines or buffers but only one service facility, like a grocery store with the usual checkout lanes but only one cashier running between them! Would you want to shop in that store? In the physics experiment, the exit is the single server and the lines are the streams of people (women?) approaching the exit from all angles. The asymmetric placement of the pillar effectively reduces the number of exit streams that can form (I'm guessing).

We already know from queueing theory that better performance is achieved with multiple servers processing a single waiting line. It follows that having less than one server—as is the case with polling systems—must be less efficient. But given that there is a necessity to adopt a polling system approach (e.g., an exit door), the fewer waiting lines or exit streams, the better. Knowing the potential performance impact, why would anyone ever implement polled queues in computer systems? Somewhat surprisingly, not only are polling systems used, they're used all over the place. Here are a few disparate examples:
In a nutshell, there are many situations in computer architectures where it is necessary to multiplex more streams of requests than there are resources to service them. It may not be optimal, but it may be necessary. Achieving best performance under the constraint of polling involves many subtle issues, which I discuss in my Perl PDQ book. Foremost among them is keeping the request sizes small (for some value of small). Returning to the physics experiments, there's a bit more to it.
"... the positioning of the pillar is crucial, says Yanagisawa. When the researchers moved the pillar so that it stood directly in front of the exit's centre, rather than to the left, the outflow rate dropped" (by approx. 5%)

Presumably, placing the pillar to one side (left) forces everybody to move in the same lateral direction (toward the right). Placing it in the middle means people will try to move either left or right (jostling), thus tending to impede the forward flow.


Chen Shapira said...

I found out that something similar is done on certain US highways:
There is a short-burst traffic light at the entrances to the highway. This seems to improve highway throughput by placing a bottleneck at a location that is easier to manage.

Neil Gunther said...

So, this is different from regular freeway metering in that it allows a group of cars ("burst") to enter?

Someone once told me that Len Kleinrock ( invented the concept of freeway metering, but a quick check of the web seems to indicate that may be an urban myth: "Ramp metering was first implemented in 1963 on the Eisenhower Expressway (Interstate 290) in Chicago by Adolf D. May."

If he had invented freeway metering, it would certainly address the question, "What use is queueing theory?"

But Kleinrock did publish the first paper on packet switching theory in July 1961, which led to the development of the ARPAnet/Internet.

I guess The Internet is just as good an answer. :D

Improbable said...

Forgive me, for I have sinned: in my unix programming years I've used the select() system call a lot.

Now my try for a shameless excuse: in a limited resource environmente, when you know for sure (well, sort of) that there will be a low arrival rate, would be acceptable to use a poll?. What do you think?

Neil Gunther said...

Any selected sins should be taken up with the Pope or Linus, as improbable as that may sound.

re: "excuses" It's always a matter of what queue lengths (or concomitant response times) you are prepared to tolerate. Referring back to the single-cashier grocery store, "low arrivals" could be one way to help ensure shortish queues. There's also the order of servicing queues, and many other subtleties.

Tim Cook said...

Not sure that pointing the finger at epoll(4) is completely fair. While it can be used for polling, it is primarily designed to be used to efficiently wait for events. The "poll" in the name, and the design of the API is there to ease the developer's transition from poll/select.

Windows I/O Completion Ports and Solaris' event ports are similar (and better named) API's, BTW. The Solaris implementation is also designed for transition from poll/select.