Friday, June 5, 2009

Bin/Res process synch

Back in the 80's Graham Birtwistle developed Demos (ala Greek citizenry, not that canned thing the publisher is shown), a library extension to Simula. It is one of the earliest and most intuitive process-oriented simulation systems around. Here's one link:

There is a particular synchronization mechanism I have always liked about Demos. It is called bin/res. These are two queue-like objects that are most easily described as elements in an assembly line. A res is a resource that can be obtained and returned. (Yes, like a semaphore.) A bin is a collection into which items can be placed and removed. The items can contain arbitrary information.

What is interesting here is that when an entity pulls from a bin or a res when it is empty, the entity blocks until something becomes available. If an entity puts something into a bin or res that exceeds its configured maximum the producing entity blocks.

In process-oriented entity modeling, this is a great simple synchronization technique. In the middle of a complex bit of behavior logic, the Entity can block until something important happens.

Another cool thing about bin/res is that it has an event-oriented optimization. When an Entity is blocked, it inserts itself into an entity queue and blocks. When the other Entity changes the bin/res, it uses that queue to notify and wake up the blocked entity. This avoids all polling. It also works between processes using messages. That can be very important and useful in an online game.

Also note that bin/res can have a lot of other extensions. There can be multiple producers/consumers. The queues can be LIFO, FIFO or randomly serviced. And it is easy to put statistics like wait-times on them.

There are a million uses for bin/res. You can make your behavior scripts wait until some property reaches a desired value without polling. You can make two entities wait for each other before proceeding no matter what order they get to the staging area. You can deal with fairness and race conditions between multiple players. Any kind of queuing can be automatically flow controlled.

I've been a fan for almost 30 years. Ever since I came across Demos at University of Calgary. Hi Graham!

1 comment:

  1. been following ur blog for a while - would like to get ur views on this article