A simple programming exercise

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);
}

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
Gold Member
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.

DEvens, Klystron, hmmm27 and 3 others
jedishrfu
Mentor
or use a python-like pseudo code

jedishrfu
Mentor
i would start with a get_ptr, put_ptr, and a buffer of some length N.
Python:
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.

Last edited:
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.

jedishrfu
PeterDonis
Mentor
2020 Award
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.

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
Mentor
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
Mentor
2020 Award
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
Homework Helper
Gold Member
2020 Award
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.

Klystron
pbuk
Gold Member
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:
Code:
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.

Last edited:
PeroK
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
Homework Helper
Gold Member
2020 Award
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.

Klystron and pbuk
anorlunda
Staff Emeritus
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.

pbuk
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
Mentor
2020 Award
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.

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
Mentor
2020 Award
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.

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
Mentor
2020 Award
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.

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.

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):
C:
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