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
Use the following commands to make a fresh clone of your repository:
```
git clone -b m14 git@gitlab.epfl.ch:lamp/student-repositories-s21/cs206-GASPAR.git m14
```
## 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 implement a simple thread pool executor.
Thread pool executors provide a way to execute tasks in parallel using one of several pooled threads.
Using a pool of threads provides improved performance compared to creating a new thread for every operation since threads in the pool are reused throughout the executor's lifetime.
Thread pool executors are one of the core primitive used to implement parallel programs. For example, they are the underlying mechanism used in the implementation of `Future`-s.
Your task is to complete the implementation of the `ThreadPoolExecutor` class. This class' constructor takes the number of threads of the pool as argument and exposes two life-cycle methods (`start` and `shutdown`), and an `execute` method to run tasks on the thread pool. The `execute` method takes as argument `Unit => Unit` functions. These functions can be constructed anonymously using the following syntax: `val func = (x: Unit) => println("hello")`. Furthermore, given a `func` function of type `Unit => Unit`, one can invoke that function using `func(())`.
For the purpose of this exercise, you can assume that the tasks submitted to the thread pool via the `execute` method do not throw exceptions.
The thread pool implementation uses two additional classes:
- `BlockingQueue`, used by the `ThreadPoolExecutor` to store pending tasks,
- `Worker`-s, which each run in a separate thread, consume tasks from the queue and execute those tasks.
The `BlockingQueue` implements two methods:
- `put` to insert an element in the queue
- `take` to retrieve and remove an element from the queue, in a last in first out order.
The `put` operation always succeeds and is non-blocking (the queue is unbounded).
The `take` operation is a potentially blocking operation that waits for new elements when called on an empty queue.
Given that `Worker`-s run on separate threads, the `take` operation must be thread-safe. Furthermore, since the thread pool executor could also be used from multiple threads, the `put` operation should also be thread-safe.
Your implementation should use a single lock to achieve this thread safety, specifically using the `[wait](http://docs.oracle.com/javase/7/docs/api/java/lang/Object.html#wait())`/`[notify](http://docs.oracle.com/javase/7/docs/api/java/lang/Object.html#notify())`/`[notifyAll](http://docs.oracle.com/javase/7/docs/api/java/lang/Object.html#notifyAll())`/`synchronized` primitives.
Remember that `wait`, `notify` and `notifyAll` should only be invoked inside a synchronized block.