CSE 120: Synchronization Practice

The problems on this page provide more practice with synchronization. They are not required, not graded, and for your own curiosity. This page has the problem descriptions, and a separate page provides solutions for you to check your answers. Keep in mind that there can be multiple ways to implement the same problem.

For the problems below, use only locks and condition variables to synchronize (do not manipulate interrupts). Your solutions also cannot change the lock, condition variable, or thread classes, and they cannot use data structures other than locks and condition variables to store references to threads.

You need only use pseudocode in your answers. Your pseudocode does not have to compile, and you can use whatever syntax you are most comfortable with (the solutions use the Nachos syntax). But it does have to look like code.

Event. An Event synchronization object has two methods, wait and signal, and an internal state that can have one of two values, unsignaled and signaled. When created, an Event is in the unsignaled state. When a thread calls wait, it blocks if the Event is unsignaled and otherwise returns immediately. When a thread calls signal, it sets the Event to signaled and wakes up all blocked threads. Once an Event is signaled, it remains signaled until deleted.
Use pseudocode to implement Event:
```
class Event {
  ...private variables...
  void Event () {
    ...
  }
  void wait () {
    ...
  }
  void signal () {
    ...
  }
}
```
CountdownEvent. Microsoft .NET provides a synchronization primitive called a CountdownEvent. Programs use CountdownEvent to synchronize on the completion of many threads (similar to CountDownLatch in Java). A CountdownEvent is initialized with a count, and a CountdownEvent can be in two states, nonsignalled and signalled. Threads use a CountdownEvent in the nonsignalled state to Wait (block) until the internal count reaches zero. When the internal count of a CountdownEvent reaches zero, the CountdownEvent transitions to the signalled state and wakes up (unblocks) all waiting threads. Once a CountdownEvent has transitioned from nonsignalled to signalled, the CountdownEvent remains in the signalled state. In the nonsignalled state, at any time a thread may call the Decrement operation to decrease the count and Increment to increase the count. In the signalled state, Wait, Decrement, and Increment have no effect and return immediately.
Use pseudocode to implement a thread-safe CountdownEvent using locks and condition variables by implementing the following methods:
```
class CountdownEvent {
  ...private variables...
  CountdownEvent (int count) { ... }
  void Increment () { ... }
  void Decrement () { ... }
  void Wait () { ... }
}
```
Notes:
- The CountdownEvent constructor takes an integer count as input and initializes the CountdownEvent counter with count. Positive values of count cause the CountdownEvent to be constructed in the nonsignalled state. Other values of count will construct it in the signalled state.
- Increment increments the internal counter.
- Decrement decrements the internal counter. If the counter reaches zero, the CountdownEvent transitions to the signalled state and unblocks any waiting threads.
- Wait blocks the calling thread if the CountdownEvent is in the nonsignalled state, and otherwise returns.
- Each of these methods is relatively short.
sleepUntil. Some languages like C++ and Rust support an additional method for condition variables that we will call sleepUntil. A thread invokes the sleepUntil method with a predicate function as an argument. The predicate function takes no arguments and returns a boolean value. For a thread to return from sleepUntil, it must not only be woken up, but then evaluating the predicate must also return true. If a thread is woken up and evaluating the predicate function returns false, then the thread will block again inside of sleepUntil. (Hint: The goal is to formalize the typical condition variable wait loop.)
Use pseudocode to implement the sleepUntil method:
```
public void sleepUntil (Callable<boolean> predicate);
```
The predicate is provided by the caller and invoked using "predicate.call()". When implementing sleepUntil, you do not need to worry about the details of the predicate. You can invoke it when needed, and it will return either true or false depending on the caller's implementation and the state of the program at that time.