Browse Prior Art Database

Circular Buffer Management Using Cycle Counter

IP.com Disclosure Number: IPCOM000125928D
Original Publication Date: 2005-Jun-22
Included in the Prior Art Database: 2005-Jun-22
Document File: 3 page(s) / 23K

Publishing Venue

IBM

Abstract

This article describes a method of managing circular buffers using cycle counters. The method simplifies program logic, enabling complex buffer management to be implemented with clear and reliable logic.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 3

Circular Buffer Management Using Cycle Counter

A program is disclosed that manages curricular buffers using cycle counters.

Circular buffer is commonly used to support FIFO (first in first out) data streams. When the producer writes to the end of the buffer, it wraps around to the beginning of the buffer, provided that data written at beginning of the buffer has been consumed by a consumer. As the write (head of the buffer) proceeds, it will catch-up to the end of consumed data (tail of the buffer). When the producer is slow, the tail can catch-up to the head. When head and tail are at the same location, additional info is needed to determine whether the buffer is full (head caught up with tail) or empty (tail caught up with head). Typically, this additional info is a Boolean flag indicating if the buffer is full or not. It starts as "not full", when head catches up to tail, it is set to full. When tail moves, it is reset to "not full".

Variations of the full flag include flags to indicate if head is ahead of tail or tail is ahead of head, and if head and/or tail positions have wrapped around. Example:

US Patent 5584038: Entry allocation in a circular buffer using wrap bits indicating whether a queue of the circular buffer has been traversed

All these Boolean flag solutions are error prone. If the state of the flag is corrupted (for example, it is not updated when it should be), unconsumed data will be overwritten. It is hard to debug too. When buffer corruption is suspected, it is virtually impossible to tell if the cause is the corrupted flag.

Additionally, when multiple producers and multiple consumers are involved, the logic to keep track of the positions of all the producers and consumers is very complex and error prone. It only gets worse if rules of production/consumption such as data has to be consumed by consumer 1 before it can be consumed (as a second pass) by consumer 2. It is difficult to figure out who is ahead of who among all these buffer positions using Boolean flags.

The new solution is to represent a logical position in the circular buffer using a cycle-counter / buffer-address pair. Buffer address points to a physical location in the circular buffer. Cycle counter is incremented each time the buffer address wraps around. Comparing any two counter/address pairs is then trivial and reliable. The counter is treated as higher order bits and compared first. The address is compared only if the counters are the same. Implementing complex producer/consumer logic becomes easy. The program is more robust. It is also easier to debug because the cycle counter is always available to indicate the logical position of a buffer address in a (nearly) infinite logical FIFO buffer.

The counter/address pair can be viewed as the two parts of a number. The counter can be viewed as the higher order bits and the address as the lower order bits. Arithmetic operations such as greater than, equal, addition, subtraction can then be defined...