Principals of Computer System Design: Some comments (II)

While doing some more problems I noticed some more little issues that I want to get down before I forget:

  1. There is a misspell on page 282 in the before last paragraph, second line.  It says “flip-flip” when it’s supposed to be “flip-flop”.
  2. The code on page 456 (the read_input procedure) has strange indentation.  There is a while statement on line 32 that just does not make sense.  Note that this line was changed from the original implementation of read_input on page 454.   It appears that the change involved removing the “nothing” and adding a body to the while.  Unfortunately the body was added without any indentation.  IMO the body of the while in line 32 is made up of line 33 and 34.  Additionally from the strange indentation in lines 33 and 34, we have also strange indentation in lines 35 and 36.  These lines appear to be outside of the “do forever” loop.  Note that they were originally inside the “do forever” loop.  Based on the answers to problem 10 I think that these lines are also missing an indentation to the right.  In any case this part of the problem requires a review.
  3. Problem 10.10.C in page 458 asks about deadlocks in the code.  I agree with the answers given by the answer sheet, but I do not agree with the explanation.  Let me explain:  The answers states that “if the interrupt occurs between statements 35 and 36 of read_input, then the interrupt handler will set input available just before read_input resets it, and read_input will loop for ever waiting for input_available to become true.”  I don’t agree with the explanation because if the interrupt occurs between lines 35 and 36, the procedure DEVICE(n) is executed with input_available[n]=true.  And on the second line of the DEVICE(n) procedure, it would lock because the input_available[n] would never be false.  In other words it would lock in the DEVICE procedure, not in the read_input procedure.  Am I missing something?
  4. Similarly on problem 10.10.A the answer states that “If device 0 interrupts thread 0 after it checks input_available but before it gets to the statement in YIELD that changes its state to WAIT, the interrupt handler will run and call NOTIFY, then YIELD will set the thread’s state to WAIT, where it will remain forever, because it missed the NOTIFY”.  I agree that it misses the notify and there is a race condition, but I don’t agree with the word “forever”.  It will stay in this state until the next run of DEVICE(n).  Remember that DEVICE is an interrupt handler and that interrupts are only disabled inside DEVICE.  Am I missing something?

That is all I got for my second batch :)

Update 22-11-2010: My advisor made me realize that there is a deadlock for problem 10.10.A.  The deadlock occurs on a subsequent call to DEVICE.  It occurs when the thread is in wait state.  The thing to notice here is that the second call to DEVICE finds the input_available[n] variable set to true (because thread n missed the notify); this will cause the DEVICE interrupt handler to deadlock. :)

Advertisements

About joelgranados

I'm fascinated with how technology and science impact our reality and am drawn to leverage them in order to increase the potential of human activity.
This entry was posted in PhD. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s