Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 36 ยท Projects and Practice

Project: Bounded Ring Buffer

Build a bounded ring buffer in Ada with a protected type, barriers, contracts and a producer/consumer pair, plus a runnable C model with threads to test the design.

In this project you combine four ideas from the chapter: protected objects, entries with barriers, contracts and tasks. The result is a bounded ring buffer that lets a producer and a consumer pass values safely at different speeds, blocking when it is full or empty.

The Ada listings are read-only on this site (no Ada compiler). The C program is a runnable model with threads, used to test the same design.

Requirements

  1. Capacity fixed when the buffer is created.
  2. Put blocks while the buffer is full; Get blocks while it is empty.
  3. Values come out in the order they went in (FIFO).
  4. A producer and a consumer can run concurrently with no data races.
  5. The count never leaves 0 .. Capacity.

Step 1: the ring layout

A ring buffer uses an array and two positions. Instead of shifting elements, First marks the oldest item and Count the number stored; the next free slot is (First + Count) wrapped around.

Ring buffer idea

Wrap around index mod capacity
First oldest item
Count items stored
Next free First + Count

No shifting, O(1) put and get.

1 / 2

Step 2: the protected type

ADA
package Ring_Buffers is

   type Item_Array is array (Positive range <>) of Integer;

   protected type Buffer (Capacity : Positive) is
      entry Put (Item : in  Integer);
      entry Get (Item : out Integer);
      function Length return Natural;
   private
      Data  : Item_Array (1 .. Capacity) := (others => 0);
      First : Positive := 1;
      Count : Natural  := 0;
   end Buffer;

end Ring_Buffers;

package body Ring_Buffers is

   protected body Buffer is

      entry Put (Item : in Integer) when Count < Capacity is
         Last : constant Positive := (First + Count - 1) mod Capacity + 1;
      begin
         Data (Last) := Item;
         Count := Count + 1;
      end Put;

      entry Get (Item : out Integer) when Count > 0 is
      begin
         Item  := Data (First);
         First := First mod Capacity + 1;
         Count := Count - 1;
      end Get;

      function Length return Natural is (Count);

   end Buffer;

end Ring_Buffers;

The barriers Count < Capacity and Count > 0 express requirements 2 and 5, and the protected type's mutual exclusion gives requirement 4. Index arithmetic: with Capacity = 4, First = 3 and Count = 2, the next free slot is (3 + 2 - 1) mod 4 + 1 = 1, wrapping to the start.

Step 3: a producer and a consumer

ADA
with Ada.Text_IO; use Ada.Text_IO;
with Ring_Buffers;

procedure Run_Pipeline is
   B : Ring_Buffers.Buffer (Capacity => 4);

   task Producer;
   task Consumer;

   task body Producer is
   begin
      for I in 1 .. 10 loop
         B.Put (I * I);
      end loop;
   end Producer;

   task body Consumer is
      V     : Integer;
      Total : Integer := 0;
   begin
      for I in 1 .. 10 loop
         B.Get (V);
         Total := Total + V;
      end loop;
      Put_Line ("sum of squares:" & Total'Image);   --  385
   end Consumer;
begin
   null;
end Run_Pipeline;

Both tasks run for exactly ten items, so they finish, and the master Run_Pipeline waits for them. The sum of the squares from 1 to 10 is 385 whatever the interleaving, because the buffer never loses or reorders items.

Step 4: add contracts

For a state-based object you can state invariants with a ghost function. In SPARK, for example:

ADA
function Length return Natural
  with Post => Length'Result <= Capacity;

and, to show the capacity bound is never exceeded, the proof tool needs the invariant Count <= Capacity on the private part, which the barriers maintain. Writing such a statement reveals subtle errors: if Put forgot to check the barrier, the contract would fail at the first overflow.

Step 5: test the design with the C model

The C program uses a mutex and two condition variables (not_full, not_empty), the standard implementation of the same barriers. A producer writes the squares of 1 to 10 and a consumer sums them and also checks FIFO order. The capacity of 4 forces both sides to block at times.

C C model: bounded buffer with producer and consumer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The output is sum of squares: 385, FIFO order kept: yes on every run, even though the interleaving differs.

Step 6: single-threaded unit test of the wrap-around

Concurrency is not needed to test the index arithmetic. This second program tests the ring logic alone: fill, drain two, add two more (forcing wrap-around), and drain all, checking the order. In Ada this would be an AUnit test or a series of assertions.

C C model: testing wrap-around without threads

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The output is put 5 on full buffer: refused and drain: 3 4 5 6.

Extensions

  • Make Buffer generic over the element type (a generic package with a formal type Element is private;).
  • Add a Close procedure that lets the consumer finish when the producer is done, and have Get raise an exception on a closed, empty buffer.
  • Add several producers and consumers and check the total.
  • Try SPARK-friendly versions and see which checks the prover can discharge.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which barrier should the Put entry of a bounded buffer have?

    Put must block while the buffer is full.
  2. 2. Why does a ring buffer use modular arithmetic on its indexes?

    Wrapping gives constant-time put and get.
  3. 3. Why is the sum of squares the same on every run, even though the tasks interleave differently?

    Mutual exclusion and FIFO order make the result independent of scheduling.
  4. 4. What is the role of the master subprogram in this program?

    A master cannot complete before its tasks terminate.

Summary

  • A ring buffer keeps First and Count and wraps positions with mod.
  • A protected type with two barriered entries implements a safe bounded buffer.
  • Producer and consumer tasks need no explicit locks.
  • Contracts and invariants document and (with SPARK) prove the bounds.
  • A threaded C model and a single-threaded test check the design.

Next: Project: Traffic Light State Machine