Wednesday, October 22, 2008

Ring Buffer

During a recent interview, I was asked an algorithm question about buffering data with circularly linked lists. The problem wasn't especially difficult, just some pointer arithmetic so I won't relay the details here, but I remember wondering about useful applications for cyclic data structures. First-In-First-Out (FIFO) queues are an obvious application, but if a Windows kernel developer is taking the time to ask, there's got to be something behind the question.

So I was reading a design specification the other day for a virtual device driver and stumbled upon the following, written by another Windows developer:

"...the [virtual device provider] and [virtual device client] act as endpoints on a VMBus channel and communicate using upstream and downstream ring buffers."

All of a sudden, a light switched on. Here's what wikipedia has to say about Ring Buffers. Circular data structures are especially useful for streaming data between sockets. In my case, here is the most pertinent point:

"An example that could possibly use an overwriting circular buffer is with multimedia. If the buffer is used as the bounded buffer in the producer-consumer problem then it is probably desired for the producer (e.g., an audio generator) to overwrite old data if the consumer (e.g., the sound card) is unable to momentarily keep up."

The wikipedia article has a POSIX implementation of a ring buffer if you'd like to try it out.

No comments:

Post a Comment