CPSC 422/522: Operating Systems


Homework: sleep and wakeup

Read: proc.c (sleep(), wakeup(), exit(), kill() and wait()), sys_wait(), sys_exit(), sys_kill().

Hand-In Procedure

You are to turn in this homework at the beginning of lecture. Please write up your answers to the questions below and hand them in to a 6.828 staff member at the beginning of lecture.

Introduction

Remember in lecture 7 we discussed locking a linked list implementation. The insert code was:

        struct list *l;
        l = list_alloc();
        l->next = list_head;
        list_head = l;
and if we run the insert on multiple processors simultaneously with no locking, this ordering of lines can cause one of the inserts to be lost:
        CPU1                           CPU2
       
        struct list *l;
        l = list_alloc();
        l->next = list_head;
                                       struct list *l;
                                       l = list_alloc();
                                       l->next = list_head;
                                       list_head = l;
        list_head = l;

In this case, CPU2's new list element will be lost when CPU1 updates list_head. Adding a lock that protects the final two lines of insert() makes the read and write of list_head atomic, so that this ordering is impossible.

The reading for this lecture includes the implementation of sleep() and wakeup(), which processes running in the kernel use to coordinate with each other. Usually one process waits for something to happen by calling sleep(), and another process later indicates that the event has occured by calling wakeup(). For example, a read() on an empty pipe involves a sleep() to wait for input; a later write() to the pipe calls wakeup().

One problem that the sleep() and wakeup() implementations avoid is races in which process A has decided to sleep but has not quite gone to sleep, at which point process B calls wakeup() but doesn't see that A is sleeping and thus does not wake A up. If it were possible for this to occur, A would have missed the event it was sleep()ing for, and its sleep() might never terminate.

Read the code with this in mind.



Questions

(Answer and hand in.)

1. How does the ptable.lock help avoid this problem? Give an ordering of instructions (like the above example for linked list insertion) that could result in a wakeup being missed if the ptable.lock were not used. You need only include the relevant lines of code.

2. sleep is also protected by a second lock, its second argument, which need not be the ptable.lock. Look at the example in ide.c, which uses the idelock. Give an ordering of instructions that could result in a wakeup being missed if the idelock were not being used. (Hint: this should not be the same as your answer to question 2. The two locks serve different purposes.)



This completes the homework.


Bryan Ford, Department of Computer Science, Yale University
[an error occurred while processing this directive] Based on MIT 6.828 materials by Frans Kaashoek and others