Read: proc.c (sleep(), wakeup(), exit(), kill() and wait()), sys_wait(), sys_exit(), sys_kill(). Introduction
Consider a linked list implementation. The insert code is:
struct list *l; l = list_alloc(); l->next = list_head; list_head = l;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
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.)
xv6
,
briefly describe how you did it. Did it work?