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 () {
    ...
  }
}
```
Surfing. Torrey Pines would like your help synchronizing surfers and the ocean. Using pseudocode, implement the class Surfing using locks and condition variables to synchronize multiple surfer threads with one ocean thread.
The Surfing class can be in one of two states, either breaking or calm. Surfer threads invoke the paddle method to indicate the direction, left or right, they would like to surf the break. When calm, surfer threads block until the next wave arrives. When breaking, surfer threads block if the wave is not breaking in their direction, and otherwise return immediately.
The ocean thread invokes the wave method indicating the direction the next wake is breaking (left, right, or both ways). It changes the state to breaking and wakes up all surfer threads waiting to catch waves in that direction, or wakes up all threads if the wave is breaking in both directions. It invokes the done method to indicate that the wave is finished breaking, changing the state back to calm. The ocean thread alternates invoking wave and done, and the state is initially calm.
```
class Surfing {
  enum State { calm, breaking; }
  enum Direction { LEFT, RIGHT, BOTH; }

  ...private variables...

  Surfing () {
    ...
  }
  void paddle (Direction dir) { // invoked by surfer threads
    ...
  }
  void wave (Direction dir) {   // invoked by the ocean thread
    ...
  }
  void done () {                // invoked by the ocean thread
    ...
  }
}
```
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.