Question

Assume you are given a graph that represents the relationship between four threads (T T2, T3, T4). An arrow from one thread (Tx) to another (Ty) means that thread Tx must finish its computation before Ty starts. Assume that the threads can arrive in any order. Use semaphores to enforce this relationship specified by the graph. Be sure to show the initial values and the locations of the semaphore operations ті T2 T3 T4 // Semaphores definitions and their initial values

Operating systems - synchronization/Concurrency control

Answer 1

Let there be two operations possible on a binary Semaphore s:

1. Down(s)
2. Up(s)

Here s is a binary semaphore,so it can take two possible values: 0 or 1

The shared area (critical section) will be available to use if s=1 else if its is s=0, it is considered to be busy and the process has to wait.

The function performed by each of the two functions is described as following pseudo code:

Down(s)

{

if (s.value == 1 )

{

s.value=0;

Enter Critical section

}

else

{

wait in suspend list

}

Up(s)

{

if (s.value == 0 )

{

wait in suspend list till Critical Section is free

s.value=1;

}

else

{

down(s);

}

}

Let the initial value of semaphore be 1. The given thread will be executed in the following order:

1. Execution of T1:

void T1(void)

{

Down(s);

Up(s);

}

2. Execution of either T2 or T3 can take place before as they are shown parallel in graph:

void T2(void)

{

Down(s);

Up(s);

}

3. void T3(void)

{

Down(s);

Up(s);

}

4. T4 will execute only after T2 and T3 have completed their execution.

void T4(void)

{

Down(s);

Up(s);

}