A simple programming exercise

  • Thread starter Svein
  • Start date
  • #1
Svein
Science Advisor
Insights Author
2,014
643

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?

Main Question or Discussion Point

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
 

Answers and Replies

  • #2
phinds
Science Advisor
Insights Author
Gold Member
2019 Award
15,739
5,383
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.
 
  • #3
11,269
4,732
or use a python-like pseudo code
 
  • #4
11,269
4,732
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:
  • #5
Svein
Science Advisor
Insights Author
2,014
643
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.
 
  • #6
PeterDonis
Mentor
Insights Author
2019 Award
27,520
7,522
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.
 
  • #7
Svein
Science Advisor
Insights Author
2,014
643
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.
 
  • #8
11,269
4,732
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.
 
  • #9
PeterDonis
Mentor
Insights Author
2019 Award
27,520
7,522
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.
 
  • #10
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
11,266
4,448
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.
 
  • #11
pbuk
Science Advisor
Gold Member
1,235
262
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:
  • #12
Svein
Science Advisor
Insights Author
2,014
643
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).
 
  • #13
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
11,266
4,448
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.
 
  • #14
7,969
4,651
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.
 
  • #15
Svein
Science Advisor
Insights Author
2,014
643
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).
 
  • #16
PeterDonis
Mentor
Insights Author
2019 Award
27,520
7,522
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.
 
  • #17
Svein
Science Advisor
Insights Author
2,014
643
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.
 
  • #18
PeterDonis
Mentor
Insights Author
2019 Award
27,520
7,522
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.
 
  • #19
Svein
Science Advisor
Insights Author
2,014
643
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.
 
  • #20
PeterDonis
Mentor
Insights Author
2019 Award
27,520
7,522
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.
 
  • #21
Svein
Science Advisor
Insights Author
2,014
643
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.
 
  • #22
1,924
223
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.
 
  • #23
Svein
Science Advisor
Insights Author
2,014
643
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 */
 
  • #24
pbuk
Science Advisor
Gold Member
1,235
262
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?
 
  • #25
Svein
Science Advisor
Insights Author
2,014
643
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....
 

Related Threads for: A simple programming exercise

  • Last Post
Replies
2
Views
2K
Replies
1
Views
558
Replies
4
Views
450
  • Last Post
Replies
7
Views
3K
Replies
2
Views
963
Replies
8
Views
846
Replies
0
Views
1K
Top