02158 Concurrent Programming        Fall 2024
Mandatory Assignment 4: Go Studies

Home

Plan

Material

Purpose

Preparations

As for CP Lab 4.

Program setup

In this assignment, you will have use the package/module notion of Go.

• In the first two problems only a single main Go program is made. This can be run stand-alone with the command go run <program>.go .

  Alternatively you may compile the programs using go build <program>.go and run the resulting binary program <program>[.exe] afterwards.

• In the remaining problems you will have to use one package from another one (a main program). This calls for encapsulating both packages into modules which are collections of packets.
• Modules may be placed locally or on the net. Here we just put the modules in separate directories referring to each other.
• For Problem 3, you should download and unzip the queue.zip file. This creates two directories: queue and demo. Each of these has a go.mod file turning the directory into a Go module. From the demo module, there is a reference to the queue directory (replace ...). This makes it possible to use the queue package from the main program.

Problem 1: Sieve of Eratosthenes

This problem was already given as Exercise B in CP Lab4 to which you are referred.

Problem 2: A Go Monitor (extra)

Download and run the barrier.go program (known from the lectures). Inspect the program code, run it, and make sure you understand all parts.

Now the barrier sync() method should be extended with an integer parameter and an integer result: sync(contrib int) int. The sync() operation should still make the workers meet, but return the sum of the workers' contribution parameter to all workers.

In the main program, each worker should use its number as its contribution. Hence the resulting sum is expected to be 45 (right?), which should be checked by each worker.

Beware that the solution should take fast reentry at the barrier into account and block for reentrance (on another condition queue) while the sum is being distributed. Luckily, you may safely assume that spurious wakeups do not occur in Go.

Hand in the revised program as sum_barrier.go and describe your solution.

Aside: The extended operation mimics the essential workings of the MPI_AllReduce() collective communication operation in MPI (Message Passing Interface).

Problem 3: Analyzing a Queue LIbrary (extra)

You are given a professional implementaion of a producer/consumer queue queue.go.

The queue is supposed to work as a work queue on which tasks (here called items) are submitted for execution by a pool of consumer goroutines.

Too avoid flooding, the queue is lossy. It has a limited capacity which, when reached, causes items to be lost when adding items to the queue.

Consider the following questions:

1. As stated above you are given the queue.go package and a skeleton demo program as separate modules in the queue.zip file.

   Unzip the file and enter the demo directory. Here execute the command go build queue_demo.go, run the resulting queue_demo[.exe] program a couple of times and explain the resuls.

2. The comments for the BoundedQueue structure state that the earliest items are dropped first. However, this is not what is implemented. Modify the queue_demo.go program such that it shows that the latest item is dropped first (actually never inserted, when the queue is full). Explain how the program demonstrates this.
3. There is a Size() operations which is supposed to return the current size of the queue for monitoring purposes. Explain how the Size() function may return a negative value or a value exceeding the capacity of the queue.

4. Enhance the given queue implementation by adding locks and lock operations such that the Size() operation never reports a negative value. It may still return a value exceeding the capacity bound. The resulting implementation should be called safe_queue.go.
5. Explain how a call of Produce() may fail (return a Go run-time panic [= exception]) if the queue is simultanesly stopped by a call of Stop(). [You need not try to remedy this unfortunate fact.]

Aside: The bounded queue studied above is actually a component in the Jaeger distributed tracing system, developed by the Uber company as part of their services.

The actual version provided is a (slightly simplified) commit of of this component as of August 2019.

Since this version, the component has been further developed (and corrected). Especially an operation Resize() to change the capacity of the queue has been added in the latest version.

Problem 4: An Overwriting Ring Buffer (extra)

As seen in Problem 3, the claim that the earliest items are dropped first when the queue capacity is reached is not what is implemented.

In certain contexts, it is desirable to have a queue in which the oldest elements are discarded in case of capacity problems. One example would be a buffer where program trace events are held before being stored in persistent storage. In case of a crash, hopefully the most recent events are intact in the store.

In this problem you should implement a queue with the same operations as in the queue.go, but where the oldest elements are discarded when the queue has reached its capacity. Such a queue is often called an overwriting ring buffer. The ring buffer should be implemented in a file ring_buffer.go defining a package ring_buffer.

The implementation may be based on the given queue.go still internally using a channel for the queue but discarding items from the other end. This could be achieved by letting the Produce() operation "make room for itself" by removing an old item if it finds the the queue to be full.

(Alternatively the ring buffer may be reimplemented by a server using an array to hold elements. For this, you may get inspiration from the blocking bounded buffer shown at the lectures: buffer.go.)

Device a program ring_buffer_demo.go which demontrates that the oldest elements are in fact discarded first.

Group Work

The assignment should be made in groups of 1-3 students. These may be the (subsets of) the provious groups, new groups or indivituals.

If you want to hand in, you must apply to get registered for a Mandatory 4 group. Please inform the teacher about this, no later than Wednesday November 27.

All groups should do Problem 1. Groups of 2 students are expected to do one of the extra Problems 2, 3, and 4 as well while groups of 3 students must do two of the extra problems.

Of course, each group must work on its own. In particular you must not exchange any form of code or texts with other groups. Any repositories you use, must be private.

Use of generative AI is not recommended, but if you do anyhow, it must be declared (for what and how).

Hand-in

The asssignment must be handed in on DTU Learn no later than

The hand-in should comprise the following:

• A pdf report.
• The eratosthenes1.go and eratosthenes2.go programs for Problem 1.
• Possibly the sum_barrier.go program for Problem 2.
• Possibly the modified queue_demo.go and safe_queue.go programs developed for Problem 3.
• Possibly the ring_buffer.go package and ring_buffer_demo.go demo program developed for Problem 4.

Reporting

The report should include

• A front page with all information about what, who and where.
• A section for each problem. This should describe your deliberations on the problem, provide answers to the questions raised, describe what you have done and present your results in the form requested.

• A conclusion with reflections on the use of message passing in general and on production library qualities.

Feedback

Feedback before the exam will be given only to groups who need approval in order to be admitted to the exam. Feedback to others will be given later.

Help

Assistance for the assignment will be available on November 23, during the lab session as indicated on the course plan.

Updates

In case of amendments or updates, these will appear here. Major updates will be announced on DTU Learn.

Hans Henrik Løvengreen, Nov 22, 2024