Design a Ringbuffer for Thread Communication

[Svein]

TL;DR Summary

My eldest grandchild is taking IT at the low-level high school. To check on what level he understands programming I wrote a design document for him and asked if he could turn it into a program. He could not. What about you guys?

Design dokument for ”Ringbuffer”

The basic design object is

Ringbuffer: Object {
private
char buf[];
int buf_size, put_on, take_off;
bool empty, full;
int init(int size);
int next(int ix);

public
int put(char ch);
int get(void);
}

Additional design info
The design goal for this object is a "pipe" between two threads. One thread puts characters into the buffer and the other removes characters from the buffer. There is no synchronization between the threads, assume that put can be interrupted by get at any time and vice versa.

Design
init

• (Allocate space for buf[])
• Set buf_size to size
• Set put_on and take_off to 0
• Set empty to TRUE and full to FALSE

next
return (ix+1) if ix<buf_size, else 0

put
If full is FALSE

• Copy ch to buf[put_on]
• Update put_on
• Set empty to FALSE
• If put_on equals take_off, set full to TRUE
• Return 0

Else

• Return -1

get
If empty is FALSE

• Copy buf[take_off] to local temp
• Update take_off
• Set full to FALSE
• If put_on equals take_off set empty to TRUE
• Return temp

Else

• Return -2

 

[phinds]

First, this does not at all seem to me to be a high school level programming problem and second, if you are going to do a "design" document you should do it in generic pseudo code, not language-specific code.

 

[jedishrfu]

or use a python-like pseudo code

 

[jedishrfu]

i would start with a get_ptr, put_ptr, and a buffer of some length N.

N=1000
buffer = [0 for i in range(N)]

get_ptr=0
put_ptr=0

def get():
    c=buffer[get_ptr]
    get_ptr = (get_ptr + 1) % N
    return c

def put(c):
    buffer[put_ptr]=c
    put_ptr = (put_ptr + 1) % N

From here, you have to consider what to do when the buffer is empty or full, how to determine when the buffer is empty (get_ptr = put_ptr) or full.

Then write some simple testcases like:
- write one char / read one char / do they equal? / repeat many times or make N small so you check when the buffer loops around
- write 2 chars / read 1 char / repeat / wait for buffer full error
- write 10 chars / read 5 / write 1 / read 5 / write 1 / read 5 expect a buffer empty error
- write several chars / read a few chars / write a few chars / read several chars ... using random number
generator to decide how many to read and write (may see empty buffer condition)

You may have to introduce an additional variable to keep track of how chars are in the buffer so you can decide whether its empty or full.

 

[Svein]

First, this does not at all seem to me to be a high school level programming problem and second, if you are going to do a "design" document you should do it in generic pseudo code, not language-specific code.

The reason the design document ended up like this is because he stated that he had programmed in javascript - and I did the design document close to javascript idioms.

From here, you have to consider what to do when the buffer is empty or full, how to determine when the buffer is empty (get_ptr = put_ptr) or full.

Look at the design document. The design is based on some decades of experience.

 

[PeterDonis]

i would start with a get_ptr, put_ptr, and a buffer of some length N

If you're using Python, the obvious data structure to use is a collections.deque; "put" is then just "append" and "get" is then just "popleft", with appropriate locking to prevent calls from colliding with each other. Then you don't need to worry about pointers or indexes at all.

You may have to introduce an additional variable to keep track of how chars are in the buffer so you can decide whether its empty or full.

For the Python scheme above, testing whether the deque is empty is simple (as for any Python container), and testing whether it is full is just a matter of passing the maxlen parameter in the constructor and then testing whether the container's length is equal to it.

 

[Svein]

with appropriate locking to prevent calls from colliding with each other.

If you doing a high-level implementation, yes, you can introduce a semaphore to avoid collisions. But - think of it as an exercise in low-level programming where you do not have access to anything except your own structures and statements (that is why I put "Allocate space" in parentheses - it should be done higher up).

The "object" in the design should not be read as an "object" in a high-level sense, it is used as a convenient metaphor for describing the elements involved. You can think "objective" in most languages, you do not need to invoke a large library to handle it.

 

[jedishrfu]

If you're using Python, the obvious data structure to use is a collections.deque; "put" is then just "append" and "get" is then just "popleft", with appropriate locking to prevent calls from colliding with each other. Then you don't need to worry about pointers or indexes at all.
For the Python scheme above, testing whether the deque is empty is simple (as for any Python container), and testing whether it is full is just a matter of passing the maxlen parameter in the constructor and then testing whether the container's length is equal to it.

While I agree with many of your suggestions, I thought this was a learning exercise in lowlevel programming so I used python to illustrate how it might be done and what edge cases to consider and test for.

 

[PeterDonis]

think of it as an exercise in low-level programming where you do not have access to anything except your own structures and statements

Unless you're designing the whole operating system of the computer from scratch, synchronization primitives like semaphores should already be available in whatever language you are programming in.

 

[PeroK]

Summary:: My eldest grandchild is taking IT at the low-level high school. To check on what level he understands programming I wrote a design document for him and asked if he could turn it into a program. He could not. What about you guys?

1) Your "design" looks to me like largely undocumented code.

2) You've essentially done the "programming" and the programmer is only being asked to translate your code into something that passes a syntax checker or compiler.

3) A "specification" is really what you want, surely? You want to ask someone to write a program to do something. Not tell them how to do it in a language barely discernible from the code itself.

 

[pbuk]

The reason the design document ended up like this is because he stated that he had programmed in javascript - and I did the design document close to javascript idioms.

But your code for the "basic design object" appears to be C++ - a language which is probably not encountered at "low-level high school" (whatever this means - examination at age 16? 18?). Unlike C++, javascript does not have typed variables or private members.

Multi-threaded programming is not something I would expect to have been taught in a high school course - and a low-level in-memory pipe cannot be implemented in javascript anyway.

I respect your decades of experience, but design documents tend to be written differently now - you would not normally specify private members of a class, nor (as others have said) write coding hints in the specification; the return values you have written within the coding hints should be in the "basic design object" - this would have highlighted the ambiguous return value of -2 from get(). Note also that the term "character" is not normally used to describe 8 bit unsigned integer values any more as characters can be encoded in many ways other than ASCII. Language-agnostic pseudocode might look like this:

CLASS RingBuffer
    A buffer for passing byte values between two independent threads.

    METHOD get()
        Get a byte from the buffer.
        Note that a return value of -2 is used to indicate that the buffer is empty and
        so this cannot be distiguished from a byte value of -2.
        RETURN the byte if successful.
        RETURN -2 if the buffer is empty.

    METHOD put(value)
        Put a byte into the buffer.
        PARAM value - the byte to put into the buffer.
        RETURN 0 if successful.
        RETURN -1 if the buffer is full.

Edit: minor corrections to code to match OP.

 

[Svein]

1) Your "design" looks to me like largely undocumented code.

2) You've essentially done the "programming" and the programmer is only being asked to translate your code into something that passes a syntax checker or compiler.

3) A "specification" is really what you want, surely? You want to ask someone to write a program to do something. Not tell them how to do it in a language barely discernible from the code itself.

Agree. I have done most of the programming for him. But there remains a few tricky parts that none of you have addressed...

But your code for the "basic design object" appears to be C++

As I said above, using the "object" term is not meant to imply C++ (or Java or Delphi or whatever). It is a way to indicate what should be available to the "outside" (i. e. the users of the ring buffer) and what should be kept private (i.e. not visible to anyone outside the module).

Just to be clear: I have written several software design documents which would give the programmer much more leeway in the implementation. But such a design document mus be accompanied by a test design document with stringent requirement as to how to test the interfaces (for each parameter try with one well inside the spec, one at the spec border and one outside the spec, program crashes not allowed).

 

[PeroK]

As I said above, using the "object" term is not meant to imply C++ (or Java or Delphi or whatever). It is a way to indicate what should be available to the "outside" (i. e. the users of the ring buffer) and what should be kept private (i.e. not visible to anyone outside the module).

Just to be clear: I have written several software design documents which would give the programmer much more leeway in the implementation. But such a design document mus be accompanied by a test design document with stringent requirement as to how to test the interfaces (for each parameter try with one well inside the spec, one at the spec border and one outside the spec, program crashes not allowed).

This is way beyond high-school IT.

 

[anorlunda]

My eldest grandchild is taking IT at the low-level high school.

I agree with others. That does not sound appropriate at all for low level high school students.

I interpret "low level" not to mean low level programming, but introductory level students. The first thing an introductory student needs is "Is this a field that I want to study more?" not skills.

A game like Pong, or something that the students think is fun and which gives the thrill of creation, and which could be shared with non-programming peers would be appropriate.

 

[Svein]

I agree with others. That does not sound appropriate at all for low level high school students.

OK. I cannot help but agree. The reason I did such a test at all and such a detailed design document is that I know that the resulting interface programs should be very simple (about 6 lines of code) and the only thing to worry about would be the interaction between put() and get() not using any semaphores (yes, it is possible. I wrote the thing once for PC keyboard processor because the software guy kept losing input and did not know why).

 

[PeterDonis]

the only thing to worry about would be the interaction between put() and get() not using any semaphores (yes, it is possible

Semaphores are not the only possible mechanism for avoiding contention between different threads accessing the same data structure. But you need some mechanism. If you are claiming you can write a program that allows multiple threads to access the same data structure without worrying at all about avoiding contention, that's obviously false.

I wrote the thing once for PC keyboard processor

The keyboard processor is an operating system service driven by hardware interrupts, so the OS is already doing the avoidance of contention for you.

 

[Svein]

Semaphores are not the only possible mechanism for avoiding contention between different threads accessing the same data structure. But you need some mechanism.

I may have said it indirectly, but this ring buffer is meant to work as a "pipe", which means that one thread connects to the input and one thread connects to the output.

 

[PeterDonis]

this ring buffer is meant to work as a "pipe", which means that one thread connects to the input and one thread connects to the output

That still means a put from one thread can collide with a get from the other, so you still have to manage contention between threads.

 

[Svein]

That still means a put from one thread can collide with a get from the other, so you still have to manage contention between threads.

Yes - and that was one of the points of the exercise. Identifying the critical points where a collision could do some harm and think about how to program around it. Worst-case - insert the assembler code meant for such scenarios: In 8086 assembler it is "LOCK XCHG (reg, mem)" and in 68000 it was "TST (mem)". Both statements were guaranteed to be indivisible.

 

[PeterDonis]

Worst-case - insert the assembler code meant for such scenarios: In 8086 assembler it is "LOCK XCHG (reg, mem)" and in 68000 it was "TST (mem)". Both statements were guaranteed to be indivisible.

Those operations are atomic, yes, but can you do the required update to the data structure with just one of them? If you need two or more, a thread collision could occur in between them.

 

[Svein]

Those operations are atomic, yes, but can you do the required update to the data structure with just one of them? If you need two or more, a thread collision could occur in between them.

If get sets the full flag immediately and restores it when exiting and vice versa?

Otherwise, see Dekker's algorithm.

 

[willem2]

That still means a put from one thread can collide with a get from the other, so you still have to manage contention between threads.

This will actually work without synchronization primitives, as long as only 1 process can use put and 1 process can use get. The pointer to the start of the buffer can only be modified by put() and the pointer to the end can only be modified by get. the field empty will have to be replaced by a function (start == end)
if put sees that there is empty space, it knows that it can write a byte at the end of the buffer, and there's no way get() can make that disappear. You only need to make sure that updating the pointer to the buffer is the last thing put() and get() do.

 

[Svein]

You got it!

Now I am going to add some interface functions (methods) to the design. Think about these (sorry, the specs have to be in C, because outside of assembly I do not know how to define a couple of them in other languages):

int is_empty(void) //Returns the state of empty

int is-full(void) //Returns the state of full

typedef *callback(void)

int when_added(callback info) /*info is a pointer to a function to be called when a character is inserted in the buffer */
int when_removed(callback info) /*info is a pointer to a function to be called when a character is removed from the buffer */

 

[pbuk]

I'm not sure what the purpose of this thread is now - is it a code competition to implement a re-entrant ring buffer, or does it have anything to do with javascript or high school level IT?

 

[Svein]

I'm not sure what the purpose of this thread is now - is it a code competition to implement a re-entrant ring buffer, or does it have anything to do with javascript or high school level IT?

You are right - the original thread "closed" at #15. But the melody lingers on...

 

[sysprog]

Yes - and that was one of the points of the exercise. Identifying the critical points where a collision could do some harm and think about how to program around it. Worst-case - insert the assembler code meant for such scenarios: In 8086 assembler it is "LOCK XCHG (reg, mem)" and in 68000 it was "TST (mem)". Both statements were guaranteed to be indivisible.

When XCHG is coded, LOCK is automatically asserted, so you don't need LOCK for the XCHG instruction, and the LOCK mechanism wasn't available with the 8086; it arrived with the 80386, so perhaps it would be better to say x86.

Those operations are atomic, yes, but can you do the required update to the data structure with just one of them? If you need two or more, a thread collision could occur in between them.

If get sets the full flag immediately and restores it when exiting and vice versa?

Otherwise, see Dekker's algorithm.

You can't operate on the payload data and the flag in a single instruction unless the flag is part of the data, and you can't check the flag in the same instruction, and using the flag as a semaphore violates your no-semaphores design constraint. Regarding Dekker's algorithm, which is inherently co-operative, if you want to allow use of it, you can't also allow the 2 processes to be mutually interruptible, as you in your design document said they should be:

Additional design info
The design goal for this object is a "pipe" between two threads. One thread puts characters into the buffer and the other removes characters from the buffer. There is no synchronization between the threads, assume that put can be interrupted by get at any time and vice versa.

It appears to me that your design is for a proof-of-concept program with insufficiently precise specifications, not all of which are inter-consistent. I think that by the time you have a solid design, it would be enough to form a foundation for at least a rudimentary one-way messaging system, but reliably implementing that would probably be more complicated than what you seem want to require for the exercise. Some of the relevant considerations are discussed in Intel® 64 Architecture Memory Ordering White Paper.

 

[Svein]

When XCHG is coded, LOCK is automatically asserted, so you don't need LOCK for the XCHG instruction, and the LOCK mechanism wasn't available with the 8086; it arrived with the 80386, so perhaps it would be better to say x86.

Sorry, but this is not correct - but in some sense it highlights something I should have mentioned. The XCHG instruction is indivisible by itself, but the LOCK prefix tells any bus manager that no other processor or coprocessor should be able to access the bus between the read and the write cycle. And the LOCK prefix was available from the very beginning (see https://en.wikipedia.org/wiki/X86_instruction_listings#Original_8086/8088_instructions )

You can't operate on the payload data and the flag in a single instruction unless the flag is part of the data, and you can't check the flag in the same instruction, and using the flag as a semaphore violates your no-semaphores design constraint.

You have lost me there - where did I say something in that direction? My comment about setting the full/empty flag at once is just meant as a comment: It would block the other process, but it could possibly lead to a deadlock.

It appears to me that your design is for a proof-of-concept program with insufficiently precise specifications, not all of which are inter-consistent.

Guilty as charged. A detailed design document would cover at least 5 pages, and no teenager would bother read such a document. What about people here on PF - should I dig up some design document from my archive and see how many would bother reading it through?

 

[sysprog]

When XCHG is coded, LOCK is automatically asserted, so you don't need LOCK for the XCHG instruction, and the LOCK mechanism wasn't available with the 8086; it arrived with the 80386, so perhaps it would be better to say x86.

Sorry, but this is not correct - but in some sense it highlights something I should have mentioned. The XCHG instruction is indivisible by itself, but the LOCK prefix tells any bus manager that no other processor or coprocessor should be able to access the bus between the read and the write cycle. And the LOCK prefix was available from the very beginning (see https://en.wikipedia.org/wiki/X86_instruction_listings#Original_8086/8088_instructions )

I didn't know that the LOCK mechanism was present in the 8086. I found this in the (1985) ASM86 Langauge Reference Manual

​

​

My mistake came from misinterpreting the following:

From Intel® 64 and IA-32 Architectures Developer's Manual: Vol. 3A:

​

8.1.2​

​

Bus Locking​

​

Intel 64 and IA-32 processors provide a LOCK# signal that is asserted automatically during certain critical memory operations to lock the system bus or equivalent link.​

​

[. . .]​

​

8.1.2.1 Automatic Locking​

​

The operations on which the processor automatically follows the LOCK semantics are as follows:​

​

• When executing an XCHG instruction that references memory.​

​

The 8086 was a 16-bit processor, not one of the IA-32 processors, as the 80386 was, so I supposed that meant it didn't have the LOCK mechanism. I think that the later manual was a bit misleading in that matter, but I shouldn't have assumed that the references to 32 and 64 bit architectures meant that the mechanism wasn't present in 16-bit processors. Regarding the automatic locking for XCHG, the same page says that's true, so, given the fact that the 8086 shows LOCK XCHG, I think it's safe to assume that the automatic assertion of the bus lock is true in the more recent processors, and presumably wasn't true for the 8086.

You have lost me there - where did I say something in that direction? My comment about setting the full/empty flag at once is just meant as a comment: It would block the other process, but it could possibly lead to a deadlock.

That comment was made in response to the concern raised by @PeterDonis to the effect that despite the atomicity of the referenced instructions, if more than one instruction was required for the PUT or GET, there could still be contention problems. My response was intended to indicate that your response did not adequately address that concern, and that the use of a full/empty flag to implement turn-taking was functionally equivalent to a semaphore, wherefore it appeared to me to be inconsistent with what you said here:

I know that the resulting interface programs should be very simple (about 6 lines of code) and the only thing to worry about would be the interaction between put() and get() not using any semaphores

I interpreted "not using any semaphores" to mean that you were ruling them out, presumably in favor of something more like Dekkers algorithm, which doesn't use them.

A detailed design document would cover at least 5 pages, and no teenager would bother read such a document. What about people here on PF - should I dig up some design document from my archive and see how many would bother reading it through?

I would read it through.

 

[Svein]

OK. Here goes...

Be aware that I have removed a lot of formality from the document mostly regarding the customer at the time. I have released the document because it is old (from 2003) and the IEEE1588 standard has gone through at least one revision since this document was created.

 

[sysprog]

OK. Here goes...

Be aware that I have removed a lot of formality from the document mostly regarding the customer at the time. I have released the document because it is old (from 2003) and the IEEE1588 standard has gone through at least one revision since this document was created.

That's one of the more terse, yet also reasonably fully explanatory, RFC documents I've encountered. Maybe that's partly due to the formality redaction. I have some familiarity with the topic area due to having worked on IBM Sysplex (System Complex) implementations with a locally-attached ETR (External Time Reference) machine to keep sync between the processors and multi-processor systems in the complex. Mostly radio time is used to get sub-millisecond accuracy; if more precision is needed typically it's GPS connected via non-USB RS-232; if sub-10-microsecond accuracy, or (rarely) even sub microsecond accuracy is required, it's likely that multi-source systems with complicated inter-corrections will be employed.