Menu

Class 18: Homework

You must print this sheet out and write/type answers on it!

  1. Suppose we have a semaphore sem initialized to 0, and threads A and B executing the following: 
    Thread A           Thread B
----------         ---------
print("A");        print("C");
post(sem);         wait(sem);
wait(sem);         post(sem);
print("B");        print("D");
    We can show that it's possible for this system to print out ACDB by "serializing" the statements, i.e. by giving an order that results in ACDB being printed: 
                 Thread A        Thread B        value of sem (after statement)
             ----------      ---------       ------------
                                                   0
             print("A");                           0
             post(sem);                            1
                             print("C");           1
            _                wait(sem);            0
suspended__/ wait(sem);                            0
           \_                post(sem);            1
                                                   0
                             print("D");           0
             print("B");                           0
    Give a serialization like the one above that results in one of the threads being frozen, i.e. waiting forever. Be sure to show where the thread gets stuck!
  2. Consider the following system of three threads: 
          semaphore sem initialized to 0

Thread A           Thread B          Thread C
----------         ---------         ---------
print("A");        print("C");       print("E");
post(sem);         post(sem);        wait(sem);
print("B");        print("D");       print("F");