CPL - Channel-based Concurrency Module

Lab #2 – Mini-Project

To submit your answers, simply push your files onto the repository. The problem will be graded.

Concurrent Bounded Buffer

Your task is to implement a bounded buffer that obeys a FIFO discipline. The buffer has a very simple interface:

  • New(capacity int) BoundedBuffer
    • A function that returns a new empty buffer with the given capacity.
  • Add(elem BufferElem)
    • A (blocking) method which adds a new element to the buffer.
  • Remove() BufferElem
    • A (blocking) method which removes and returns the last inserted element.

You can define the type BufferElem as interface{} using go’s type definition mechanism (look it up!). This will allow the buffer to take elements of any type.

Your task is to implement a buffer that adheres to the API above, backed by an array slice (your code should not use any functionality from Go’s atomic or sync packages):

  1. When you create the buffer use persistent auxiliary workers to handle the insertions and removals (2 per operation). Submit this file asboundedbuffer/buffer.go.

  2. Regardless of how you implemented the buffer, the proposed API can easily give rise to deadlocks if consumers are not careful. Write a small test program (boundedbuffer/buffer_test.go) that uses a buffer with non-zero capacity and two clients that results in a global deadlock (i.e. both clients and the workers are stuck). Name this test TestGlobalDeadlock, following Go’s testing API. Also write a TestBuffer function that uses more than one client and exercises the buffer API in a reasonable way.

  3. The workers are reading and writing to a shared data structure concurrently. Are these concurrents reads and writes safe? If so, comment your code with an explanation of how this is achieved (don’t use any “weird” packages for this!). If not, give an example workload (put it in the buffer_test.go file, as TestRace) under which a “problem” can arise, exhibiting the appropriate output of the go race detector tool (see here).

  4. If your implementation was indeed racy, modify it to ensure that the two workers access the underlying array in mutual exclusion. Call it boundedbuffer/betterbuffer.go. Hint: Use channels linking the workers.

  5. If your implementation was not racy, congratulations. Now, break it! Place the broken implementation in boundedbuffer/buffer_racy.go and don’t forget to add the appropriate test as requested in point (3) above.

  6. Does the buffer ensure freedom from starvation to its clients? Explain (write your answer in a file boundedbuffer/starvation.txt).

  7. Since the buffer is backed by an array slice, there is still a lot of shared-memory concurrency in your code. Lets now try to write a bounded buffer in a way that is more aligned with Go’s concurrency philosophy: Write an implementation (boundedbuffer/idiomaticbuffer.go) for the bounded buffer API, with two writing and two reading workers, preserving the good properties of the previous implementation, that is not backed by an array or an array slice (but without using any imported concurrent data structure). Revisit question 6 for this buffer, leaving your answer as comments in the code.

That’s it! Don’t forget to push!