Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
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](https://docs.scala-lang.org/overviews/parallel-collections/overview.html)
* [The API documentation of the Scala parallel collections](https://www.javadoc.io/doc/org.scala-lang.modules/scala-parallel-collections_2.13/latest/scala/collection/index.html)
* [The API documentation of the Scala standard library](https://www.scala-lang.org/files/archive/api/2.13.4)
* [The API documentation of the Java standard library](https://docs.oracle.com/en/java/javase/15/docs/api/index.html)
**If you have issues with the IDE, try [reimporting the
build](https://gitlab.epfl.ch/lamp/cs206/-/blob/master/labs/example-lab.md#ide-features-like-type-on-hover-or-go-to-definition-do-not-work),
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`:
```scala
// Thread 1
sc.write(1, 2)
```
```scala
// 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`:
```scala
// Thread 1
msc.write(1, 2)
```
```scala
// Thread 2
msc.write(10, 20)
```
```scala
// 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.