CS372: Homework 8

Problem 1:

Consider the following program fragment:

P(s1);
a++;
P(s2);
v++;
V(s2);
V(s1);

(s1, s2 are semaphores). All variables are automatic. Now, consider two threads running this fragment of code simultaneously, can there be a deadlock? Why, or why not?

Problem 2:

Consider the following program fragment:

if(a > 0)
    P(s1);
else
    P(s2);
b++;
P(s3);
if(b < 0 && a <= 0)
    P(s1);
else if(b >= 0 && a > 0)
    P(s2);
else
    P(s4);
a++;
V(s4);
V(s3);
V(s2);
V(s1);

s1, s2, s3 and s4 are semaphores. All variables are automatic. Now, consider two threads running this fragment of code simultaneously, can there be a deadlock? Why, or why not?

Problem 3

An angry mob goes after the five dining philosophers, who escape into a dark alley in an unfrequented part of the town. They found an old soup kitchen, 5 bowls, and a coin. They decide to adapt to a new lifestyle. A philosopher now goes through the sequence:

while(1)
{
    flip the coin
       if(head) Table.Work()
       else Table.Eat()
   Think()
}

where Table is a shared object that encapsulates the system's shared state. As a result of the function Table::Work(), the philosopher makes enough soup to fill a bowl. Similarly, the result of the function Table::Eat() is that a philosopher picks a bowl and consumes all the soup in it. Note that there is no correspondence between bowls and philosophers, i.e., a philosopher will eat from any available bowl that contains soup, and will fill any available empty bowl.

Using locks and condition variables, create a Table object to organize the philosophers' working and eating. Specifically, write the Table constructor and the methods Table::Work(), Table::Eat.
If the coin guarantees that no more than four heads or four tails can appear in a row, is it possible to have starvation in the system? Explain your answer.

Problem 4

True/False Starvation implies deadlock.

Problem 5

In the context of deadlock prevention, how does a safe state differ from an unsafe state?

Problem 6

Define the term priority inversion.