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.
Submit:
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.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.)