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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
# Exercise 1
Use the following commands to make a fresh clone of your repository:
```
git clone -b exercise-1 git@gitlab.epfl.ch:lamp/student-repositories-s21/cs206-GASPAR.git exercise-1
```
Update the README.md file with your solutions. Don't forget to list the group members' SCIPER numbers.
# Problem 1: Introduction to Concurrency
Freshly graduated from EPFL, you all have been hired as contractors for a successful and rapidly growing bank. The bank has recently been experiencing problems with their money management system, coded in Scala, and so they hired the best and brightest young engineers they could find: you! The system has been working perfectly fine so far, they tell you. In the past days, due to an increased number of customers, they had to switch from a single threaded sequential execution environment to a multithreaded concurrent environment, in which multiple threads may perform transactions concurrently. That's when problems started, your manager says…
Below is the code responsible to withdraw money from the account from and transfer it to the account to, within the same bank.
```scala
def transfer(from: Account, to: Account, amount: BigInt) {
require(amount >= 0)
val balanceFrom = from.balance
if (balanceFrom >= amount) {
from.balance = balanceFrom - amount
val balanceTo = to.balance
to.balance = balanceTo + amount
}
}
```
For the bank, it is very important that the following two properties hold after any sequence of completed transfer transactions:
1. The balance of an account never goes below 0.
2. The total sum of money held by the bank is constant.
## Question 1
Does the above transfer method respect the two properties in a *sequential* execution environment, that is, when there is only one thread in the program?
## Question 2
What can go wrong in a setting where multiple threads can execute the `transfer` method concurrently? For each of the two desired properties of the system, check if its holds in this concurrent environment. If not, come up with an example execution which exhibits a violation of the property.
# Question 3
For each of the proposed implementations of `transfer` below, check which of the properties hold. Additionally, check if the system is vulnerable to *deadlocks*.
Variant 1
```scala
def transfer(from: Account, to: Account, amount: Long): Unit = {
require(amount >= 0)
val balanceFrom = from.balance
if (balanceFrom >= amount) {
from.synchronized {
from.balance = balanceFrom - amount
}
to.synchronized {
val balanceTo = to.balance
to.balance = balanceTo + amount
}
}
}
```
Variant 2
```scala
def transfer(from: Account, to: Account, amount: Long): Unit = {
require(amount >= 0)
from.synchronized {
val balanceFrom = from.balance
if (balanceFrom >= amount) {
from.balance = balanceFrom - amount
to.synchronized {
val balanceTo = to.balance
to.balance = balanceTo + amount
}
}
}
}
```
Variant 3
```scala
object lock // Global object
def transfer(from: Account, to: Account, amount: Long): Unit = {
require(amount >= 0)
lock.synchronized {
val balanceFrom = from.balance
if (balanceFrom >= amount) {
from.balance = balanceFrom - amount
val balanceTo = to.balance
to.balance = balanceTo + amount
}
}
}
```
# Problem 2: Parallel Reductions
## Question 1
As a group, write a function called `minMax`, which should take a non-empty array as input and return a pair containing the smallest and the largest element of the array.
```scala
def minMax(a: Array[Int]): (Int, Int) = ???
```
Now write a parallel version of the function. You may use the constructs `task` and/or `parallel`, as seen in the lectures.
## Question 2
Imagine that the data structure you are given, instead of an `Array[A]`, is one called `ParSeq[A]`. This class offers the two following methods, which work in parallel:
```scala
def map[B](f: A => B): ParSeq[B]
def reduce(f: (A, A) => A): A
```
Can you write the following `minMax` function in terms of `map` and/or `reduce` operations ?
```scala
def minMax(data: ParSeq[Int]): (Int, Int) = ???
```
## Question 3
What property does the function `f` passed to reduce need to satisfy in order to have the same result regardless on how reduce groups the applications of the operation f to the elements of the data structure? Prove that your function `f` indeed satisfies that property.