CS 134

OS/161 Hangman: Your Kernel Debugging Companion

What is Hangman?

Hangman is a built-in tool in OS/161 designed specifically to help you debug your kernel code.

  • Dog speaking

    Does it, like, let you make up to seven mistakes before it finished drawing an ASCII-art stick figure and then panics the kernel?

  • PinkRobot speaking

    No. While the name might evoke the word-guessing game, in this context, Hangman is here to catch a particularly tricky bug: deadlocks.

What is a Deadlock?

A deadlock is a situation where two or more processes are stuck, unable to make progress because they're all waiting for each other. This state can happen when multiple threads are trying to acquire locks in a way that creates a cycle of dependencies (e.g., A is waiting for B, B is waiting for C, and C is waiting for A). When a deadlock occurs, the kernel freezes, and you're left wondering what went wrong.

Why is Hangman Important for You?

As you work on your OS/161 assignments, you'll be implementing various synchronization primitives and concurrent systems. This work is challenging, and it's easy to accidentally create deadlocks. Hangman is here to help you

  1. Catch Deadlocks: Hangman will alert you when a deadlock occurs, saving you from the frustration of a mysteriously frozen kernel.
  2. Understand the Problem: It will show you exactly which threads and locks are involved in the deadlock, making it easier to debug.

Understanding Hangman Macros

You'll encounter several Hangman-related macros in the OS/161 codebase. Don't let these intimidate you! They're simply hooks that allow Hangman to do its job. Let's break down what each macro does and what its parameters mean.

  1. HANGMAN_LOCKABLE(lockname)

    • Used in lock structure definitions
    • lockname: A unique identifier for the lockable object
    • Example: HANGMAN_LOCKABLE(lk_hangman);

  2. HANGMAN_LOCKABLEINIT(lock, name)

    • Initializes a lockable object
    • lock: Pointer to the Hangman-specific part of the lock (usually &lock->lk_hangman)
    • name: String name of the lock (for debugging output)
    • Example: HANGMAN_LOCKABLEINIT(&lock->lk_hangman, lock->lk_name);

  3. HANGMAN_WAIT(thread, lock)

    • Should be called before a thread waits for a lock
    • thread: Pointer to the thread's Hangman-specific data (usually &curthread->t_hangman)
    • lock: Pointer to the lock's Hangman-specific data (usually &lock->lk_hangman)
    • Example: HANGMAN_WAIT(&curthread->t_hangman, &lock->lk_hangman);
    • Generally, this function is called from inside the spinlock-protected critical section of a lock acquisition function.

  4. HANGMAN_ACQUIRE(thread, lock)

    • Should be called after a thread successfully acquires a lock
    • Parameters are the same as HANGMAN_WAIT
    • Example: HANGMAN_ACQUIRE(&curthread->t_hangman, &lock->lk_hangman);
    • Generally, this function is called from inside the spinlock-protected critical section of a lock acquisition function.

  5. HANGMAN_RELEASE(thread, lock)

    • Should be called when a thread releases a lock
    • Parameters are the same as HANGMAN_WAIT
    • Example: HANGMAN_RELEASE(&curthread->t_hangman, &lock->lk_hangman);
    • Generally, this function is called from inside the spinlock-protected critical section of a lock release function.

How to Use Hangman in Your Code

Now that you understand what these macros do, here's how to use them in your code:

  1. In your lock structure, include

    HANGMAN_LOCKABLE(lk_hangman);

  2. When initializing a lock,

    HANGMAN_LOCKABLEINIT(&lock->lk_hangman, lock->lk_name);

  3. In your lock implementation, in the lock-acquire function,

    // When you are about to wait on the lock
HANGMAN_WAIT(&curthread->t_hangman, &lock->lk_hangman);
// ... your code for waiting on the lock ...

// Once you're ready to say you've acquired the lock
HANGMAN_ACQUIRE(&curthread->t_hangman, &lock->lk_hangman);
// ... your code for acquiring the lock ...

    and in the lock-release function,

    // Tell Hangman you're about to release the lock
HANGMAN_RELEASE(&curthread->t_hangman, &lock->lk_hangman);
// ... your code for releasing the lock ...

Just make sure these macros are in the right places in your code, and Hangman will take care of the rest!

What Hangman Does Behind the Scenes

While you don't need to worry about the details right now, Hangman works by maintaining a “waits-for” graph of threads and locks. If it detects a cycle in this graph, it knows a deadlock has occurred and will alert you.

You'll learn more about wait-for graphs later in the course. For now, just think of Hangman as an alarm system, watching your kernel's lock usage and letting you know if something goes wrong.

Remember

Hangman is here to help you learn and debug. If you see a Hangman warning, don't panic! It's just doing its job to help you understand and fix concurrency issues in your kernel. Happy coding, and may Hangman catch your deadlocks before they catch you off guard!

(When logged in, completion status appears here.)