m21.md

Use the following commands to make a fresh clone of your repository:

git clone -b m21 git@gitlab.epfl.ch:lamp/student-repositories-s21/cs206-GASPAR.git m21

Useful links

• A guide to the Scala parallel collections
• The API documentation of the Scala parallel collections
• The API documentation of the Scala standard library
• The API documentation of the Java standard library

If you have issues with the IDE, try reimporting the build, if you still have problems, use compile in sbt instead.

Exercise

In this question, you will complete the definition of two concurrent data structures without using synchronized: SeqCount and MultiWriterSeqCount.

Part 1: SeqCount (defined in SeqCount.scala)

An instance of this class stores two integers (initially set to 1), the stored values can be updated using write and retrieved using copy. Only one thread at a time is allowed to call write but multiple threads can call copy at once.

Your task in this part is to implement copy such that this method never returns partially updated values, for example given two threads operating concurrently on a SeqCount sc:

// Thread 1
sc.write(1, 2)

// Thread 2
val result = sc.copy()

result must either be (0, 0) (since the initial values are 0) or (1, 2), but it must not be (1, 0), (0, 2) or any other value.

To successfully implement this method you will need to use generation: this method returns the current value of a volatile variable which is initially set to 1, gets incremented by one at the beginning of write, and incremented by one again at the end of write.

You are not allowed to use synchronized or directly call any of myGeneration, myX or myY (use the pre-defined getters and setters instead).

Hints:

• Remember that a write to a volatile field happens-before every subsequent read of that field.
• generation will always be odd when a write has completed and always even when a write is in progress.
• copy can be implemented as a tail-recursive method.

Part 2: MultiWriterSeqCount (defined in MultiWriterSeqCount.scala)

Like SeqCount, this class stores two integers updated using write and retrieved using copy, but unlike SeqCount multiple threads are allowed to call write at the same time: these writes will all succeed but they are allowed to complete in any order, for example given three threads operating concurrently on a MultiWriterSeqCount msc:

// Thread 1
msc.write(1, 2)

// Thread 2
msc.write(10, 20)

// Thread 3
val result = msc.copy()

result must either be (0, 0), (1, 2) or (10, 20).

In this class, the generation is stored in an atomic variable instead of a volatible field therefore it's important to note that:

• a set on an atomic variable happens-before every subsequent get of that variable.
• A call to compareAndSet both gets and set an atomic variable.

Your task in this part is to implement both copy and write.

You are not allowed to use synchronized or directly call any of myGeneration, myX or myY (use the pre-defined getters and setters instead).

Hints:

• you should be able to just copy-paste the implementation of copy you implemented in Part 1
• you will need to make use of compareAndSetGeneration in write
• write can be implemented as a tail-recursive method.