Requirements for Locks and Condition Variables in OS/161

In Assignment 3, you'll be implementing locks and condition variables inside OS/161, which you'll then be able to use both in later kernel code and to solve some synchronization problems that come with that assignment.

The code for both locks and condition variables is in kern/include/synch.h and kern/thread/synch.c (currently just stubs), and kernel code that wants to use them should use

#include <synch.h>

Locks

Although C is not an object-oriented language like Java or Python, the flavor of the lock API in OS/161 is similar to what you might see in an object-oriented language. You can make a new lock, store it in a variable, and then call functions on that variable to acquire and release the lock. When you're done with the lock, destroy it.

The type of the variable that holds a lock is struct lock *.

Functions

• struct lock *lock_create(const char *name)
  • Creates and initializes a lock “object”.
    • The memory for a struct lock is created on the kernel heap with kmalloc.
  • Returns a pointer to the new lock, or NULL on failure.
• void lock_destroy(struct lock *lock)
  • Precondition: The lock is not held by any thread.
  • Destroys the lock and frees all associated memory.
• void lock_acquire(struct lock *lock)
  • Precondition: The lock is not held by the current thread.
  • Acquires the lock, blocking the calling thread if the lock is already held.
• void lock_release(struct lock *lock)
  • Precondition: The lock is held by the current thread.
  • Releases the lock, allowing another thread to acquire it.
• bool lock_do_i_hold(struct lock *lock)
  • Returns true if the current thread holds the lock; false otherwise.

Behavior Requirements

• The lock implementation must meet all the requirements of a solution to the critical section problem—mutual exclusion, progress, and bounded waiting.
• If a thread needs to wait for a lock to become available, it should sleep until the lock is released.
• Releasing a lock should wake up one waiting thread, if any threads are waiting.
• Violations of the preconditions for lock_acquire, lock_release, and lock_destroy should result in a kernel panic.

Condition Variables

Condition variables also have an object-like API in OS/161. You can create a new condition variable, store it in another variable, and then call functions on that variable to wait, signal, or broadcast.

Functions

• struct cv *cv_create(const char *name)
  • Creates and initializes a condition variable.
    • The memory for a struct cv is created on the kernel heap with kmalloc.
  • Returns a pointer to the new CV, or NULL on failure.
• void cv_destroy(struct cv *cv)
  • Precondition: No threads are waiting on the CV.
  • Destroys the condition variable and frees all associated memory.
• void cv_wait(struct cv *cv, struct lock *lock)
  • Precondition: The calling thread holds the associated lock.
  • Releases the lock and blocks the current thread on the CV.
  • When the thread wakes up, cv_wait reacquires the lock before returning.
• void cv_signal(struct cv *cv, struct lock *lock)
  • Precondition: The calling thread holds the associated lock.
  • Wakes up one thread waiting on the CV, if any are waiting.
• void cv_broadcast(struct cv *cv, struct lock *lock)
  • Precondition: The calling thread holds the associated lock.
  • Wakes up all threads waiting on the CV.

Behavior Requirements

• cv_wait must atomically release the lock and block the thread.
• The associated lock is held on entry to and exit from cv_wait, but released while the thread is waiting.
• cv_signal should wake up only one thread, whereas cv_broadcast should wake up all waiting threads.
• Violations of the preconditions for cv_wait, cv_signal, cv_broadcast, and cv_destroy should result in a kernel panic.

Relation to POSIX mutex/cv API

The OS/161 lock and CV API is similar to the POSIX pthread API:

The main differences are in creation/destruction, where OS/161 uses separate create and destroy functions, and in error handling, where OS/161 uses panic instead of returning error codes.

Usage Patterns

Typical usage of locks and CVs in a monitor-style solution:

struct pancake *
pancake_hot_pancake(struct fryingpan *fryingpan)
{
    struct pancake *food = pancake_create();

    // Wait for the frying pan to be available
    lock_acquire(fryingpan->pan_lock);
    while (fryingpan->in_use) {
        cv_wait(fryingpan->pan_ready, fryingpan->pan_lock);
    }
    pan->in_use = true;
    pan->resident_food = food;
    lock_release(fryingpan->pan_lock);

    // Cook the pancake
    pancake_cook(food);

    // Let anyone wanting the frying pan know it's available
    lock_acquire(fryingpan->pan_lock);
    fryingpan->in_use = false;
    fryingpan->resident_food = NULL;
    cv_signal(fryingpan->pan_ready, fryingpan->pan_lock);
    lock_release(fryingpan->pan_lock);

    return food;
}

In this example, the lock fryingpan->pan_lock protects access to the shared resource (the frying pan), and the condition variable fryingpan->pan_ready is used to signal when the pan is available for use.

(When logged in, completion status appears here.)