Posted on by

Lecture 7: Deadlock

30 September, 2011 This week we will look at deadlock in more details, as well as other nuisances caused by buggy synchronization code, including livelock, starvation, and priority inversion. Having a hardcopy of slides during lecture would be helpful. Be prepare to take notes during lecture.

Download Slides: PDF

Reading:

  • Chapter 6 (exclude 6.5, 6.7.1, 6.7.2, 6.8)

Related Wikipedia entries are listed below. These are for students who are keen to go beyond what is covered in CS2106. Read the articles with a critical mind since Wikipedia is editable by anyone.

12 thoughts on “Lecture 7: Deadlock”

  5. Hi Prof

    I saw in slide 54 that you have mentioned that the dining philosophers problem can be avoid if we number (label) the chopsticks. Sticking to the “pick up left chopstick first” rule, at first the 1st philosopher has chopstick 1 & 2, so he pick up 1. Then the 2nd one pick up chopstick 2, and …. (Picking up continue…) Then when it’s it is the last philosopher turn to pick up a chopstick, he can just pick up chopstick 6 as it is available, resulting in a deadlock. Why will he pick up chopstick 1?

    And how does assign a “pick up right chopstick first” philosopher similar in term of the “ordering resource numerically and acquire in order” approach?

    • To avoid circular waiting, we can label resources with numbers and make processes acquire the resource in strictly increasing order of the labels.

      Thus, if we apply this solution to the dining philosophers problem, one of the philosopher must acquire the right chopstick first before the left (the one between Chopstick 1 and Chopstick 6). We cannot stick to the “pick left first” rule since it will violate the order of the labels (and lead to circular waiting).

      • Hence this is the solution approach that we will adopt to solve the circular waiting problem?

        ‘Label’ resources, ensure process to acquire resources in a order way, then make the last process to behave the opposite way, so that the circular waiting problem can be avoid?


        • Francis Pang:

          Hence this is the solution approach that we will adopt to solve the circular waiting problem?

          Yes.

          ‘Label’ resources, ensure process to acquire resources in a order way, then make the last process to behave the opposite way, so that the circular waiting problem can be avoid?

          The bit on ‘last process behave opposite” is specific to the dining philosophers problem only. Also, there is really no “last” process here.

          To understand this, it’s useful to spend a moment thinking about why there is no circular waiting when processes acquire resources in increasing order of labels.

Comments are closed.