SEM Exam IIT Kanpur

Question

1. Consider the following function. The semaphores a, b, c, d are all initialized to one.

sem_t a, b, c, d;

void f (sem_t *s1, sem_t *s2, sem_t *s3, sem_t *s4)

{

          sem_wait(s1); sem_wait(s2); sem_wait(s3); sem_wait(s4);

         Critical section

         sem_post(s1); sem_post(s2); sem_post(s3); sem_post(s4);

 }

Two threads call the function f concurrently. One of these threads invokes f as f(&c, &b, &a, &d). Write down all possible correct invocations of function f by the other thread.

Answer 1

Let us call the two threads as thread1 and thread2.

Let thread1 has called f(&c, &b, &a, &d).

Now, we see that sem_wait(c); sem_wait(b); sem_wait(a); sem_wait(d); will be called in thread1. So, now if thread2 calls them in another order without first as c - like - sem_wait(b); sem_wait(c); sem_wait(a); sem_wait(d);, then we can see that we might get a deadlock if thread1 executes sem_wait(c) and thread2 executes sem_wait(b);.

So we would need the condition that first semaphore should be c itself.

Thus, now thread2 can call f by 6 different ways - 

1. f(&c, &b, &a, &d)
2. f(&c, &b, &d, &a)
3. f(&c, &d, &a, &b)
4. f(&c, &d, &b, &a)
5. f(&c, &a, &b, &d)
6. f(&c, &a, &d, &b)