Double buffering

From Wikipedia, the free encyclopedia

This article does not cite any references or sources. (February 2008) Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

In computer science, double buffering (or ping-pong buffering) is a widely used technique for minimizing the delay (flicker) in input/output operations which use a buffer. Single buffering is affected by buffer underrun and buffer overflow. Double buffering is a better solution because it is possible to use two separate buffers in parallel, so that while B1 is read B2 can be written, and while B2 is read B1 can be written.

The easiest way to explain how double buffering works is to take a real world example. It is a nice sunny day and you have decided to get the paddling pool out, only you can't find your garden hose. You'll have to fill the pool with buckets. So you fill one bucket (or buffer) from the tap, turn the tap off, walk over to the pool, pour the water in, walk back to the tap to repeat the exercise. This is analogous to single buffering. The tap has to be turned off while you "process" the bucket of water.

Now consider how you would do it if you had two buckets. You would fill the first bucket and then swap the second in under the running tap. You then have the length of time it takes for the second bucket to fill in order to empty the first into the paddling pool. When you return you can simply swap the buckets so that the first is now filling again, during which time you can empty the second into the pool. This can be repeated until the pool is full. It is clear to see that this technique will fill the pool far faster as there is much less time spent waiting, doing nothing, whilst buckets fill. This is analogous to double buffering. The tap can be on all the time and does not have to wait whilst the processing is done.

In computer science the situation of having a running tap that cannot be, or should not be, turned off is common (such as a stream of audio). It is also usual that computers prefer to deal with chunks of data rather than a stream. In such situations double buffering is often employed.

In Microsoft Windows double buffering is also copying data between two buffers for direct memory access (DMA) transfers. This is not for enhancing performance, but to meet specific addressing requirements of a device (esp. 32-bit devices on systems with wider addressing provided via physical address extension).^[1]

Device drivers are particularly noteworthy as a place where double buffering is likely to be used.

Triple buffering is a variation of double buffering.

Contents 1 Double Buffering Petri Net 2 Double Buffering in Computer Graphics 3 Database management system 4 Interlacing 5 References

[edit] Double Buffering Petri Net

The following Petri net shows how double buffering works. Transitions W1 and W2 represent writing to buffer 1 and 2 respectively while R1 and R2 represent reading from buffer 1 and 2 respectively. At the beginning only the transition W1 is enabled. After W1 fires, R1 and W2 are both enabled and can proceed in parallel. When they finish, R2 and W1 proceed in parallel and so on.

So after the initial transient where W1 fires alone, this system is periodic and the transitions are enabled always in pair (R1 with W2 and R2 with W1 respectively).

This Petri net is live and safe.

[edit] Double Buffering in Computer Graphics

In computer graphics, double buffering (sometimes called ping-pong buffering) is a technique used to reduce or remove visible artifacts from the drawing process. It may be implemented in either software or hardware.

Computer monitors constantly redraw the visible video page (at around 60 times a second), and so it is difficult to make changes to the video page (such as creation or movement of complex objects onscreen) without the monitor showing the results before the graphics operation is complete. This results in ugly artifacts such as flickering, tearing and shearing.

A software implementation of double buffering uses a video page stored in system RAM that all drawing operations are written to. When a drawing operation is considered complete, the whole page, or a portion of it, is copied into the video RAM (VRAM) in one operation. This is generally synchronised so that copy operation is ahead of the monitor's raster beam so that ideally (if the copy is faster than the video beam) artifacts are avoided. This software method is not always flawless, and has a higher overhead than the hardware method. Most notably, double buffering necessarily requires more video memory and CPU time than single buffering because of the video memory allocated for the buffer itself and the syncronisation copy respectively.

The hardware method is also known as page flipping. In this method, two graphics pages in VRAM are used. At any one time, one page is actively being displayed by the monitor, while the other, background page is being drawn. When drawing is complete, the roles of the two pages are switched, so that the previously shown page is now being modified, and the previously drawn page is now being shown. The page-flip is typically accomplished by modifying the value of a pointer to the beginning of the display data in the video memory.

The hardware method guarantees artifacts will not be seen as long as the pages are switched over during the monitor's vertical blank period when no video data is being drawn. This method requires twice the amount of VRAM that is required for a single video page. The currently active and visible buffer is called the front buffer, while the background page is called the back buffer.

[edit] Database management system

In database management systems, double buffering is a technique used to exploit CPU resources during I/O operation (e.g. external sorting) by overlapping CPU and I/O processing. See Prefetching.

[edit] Interlacing

Double buffering is also used as a technique to facilitate interlacing on analog displays.

[edit] References