Finding initial values of counting semaphore

Question

Below are four concurrent processes and three counting semaphores.

What must be the initial values of the three semaphores, so that output “TGE” is obtained?

Answer 1

This question is awesome :

I read all the answers all answer seems to be correct but as per my opinion when they say TGE output must be obtained then it must be TGE only not any other output  

Now my answer

As we want TGE as output so what process we must execute first, it  must be Process 3 which requires down on C therefore C must be some positive value (note they are not talking about mutex or binary semaphore) let us consider the minimum value i.e C equals to 1 now rest all semaphores need to be 0 or negative else there may be chance some other process other than P3 may execute first.

So P3 execute down on C and print T then it performs two up on A which makes A as 2 suppose A was initially 0.

Now p1 can execute and p4 can execute but p4 cant print E as it further needs down on B and B is already 0 so only p1 gets executed. and it prints "G "

Now it signals b i.e up on B so b becomes 1 and up on C but we dont want p2 to execute as it will print A so C must be some negative no in order to restrict the execution of P2 even after up on C .

now p4 can execute and can print "E"

So my answer is the a=0 b=1 and c can be any negative no .

Answer 2

To enter PROCESS 3 (as we need to print TGE)

we have wait(b) ~ A down operation ~ b should be atleast 1 initially ~b=1

 ( b value goes from 1  ~>0 )    b=0

PRINT "T"

Followed by two signal(a) operations  ~ a could  0 initially ~ a=0

( a value goes 0~> 1~>2 after two signal operations)

a= 2   , b= 0

To enter PROCESS 1 (as we need to print TGE)

we have wait(a).. ~ A down operation ~ a would be  1 ( a goes from  2~>1 )

a=1 , b=0

PRINT "G"

Followed by two operations

1. signal(b)  ~ b goes from 0~>1 &
2. signal(c) ~ c could be  0 initially ~c=0    ; c values goes from 0~>1

a=1 , b=1 , c= 1

To enter PROCESS 4 (as we need to print TGE)

we have wait(a).. ~ a values goes from 1~>0

we have wait(b).. ~ b value goes from 1~>0

a=0,b=0,c=1

PRINT"E"

Followed by two operations

1. signal(b)  ~ b value goes from 0~>1 &  
2. signal(c) ~ c value goes from 1~>2 

a=0,b=1,c=2 (final values)

Therefore , minimum values could be a=0 , b=1 , c=0 (intially values) {ANSWER}

Correct me if I am wrong!!

Comments

This is the definition of signal from galvin:

signal(semaphore *S) 
{
    S->value++;
    if (S->value <= 0) {
        remove a process P fron< S->list;
        wakeup(P);
    }
}

Point to note is <= 0. Stallings code too uses <= 0. Even if process 2 makes wait(c) calls $n$ number of times, it will be allowed to run at least once by process 1 when it does signal(c). Or in other words, every signal() always wakes up at least one process waiting on the corresponding semaphore. So I feel A will always be printed once irrespective of initial value of c. Isnt it?

---

If c=0 initially then Process 2 can also enter in cs so A is also printed

I think c should be  <0

---

don't you think if you start c with 0 then after G gets printed, it will signal(b) so E gets printed and then it signals c, so process 2 gets executed and A gets printed and we get output, "TGEA", instead of "TGE".

Answer 3

Take a=0,b=1,c=0

• Execute process 3 at first   i) then wait(b) =0 , ii) print T, signal(a)  makes a=1, next signal (a) makes a=2.
• Execute process 1 after that i) wait (a) makes a=1, ii)print G, iii) signal(b) makes b=1, signal(c) makes c=1.
• Execute process 4 i) wait(a) makes a=0, ii) wait(b) makes b=0, iii)print E.

Thus answer is  a=0,b=1,c=0 .

Comments

This is the definition of signal from galvin:

signal(semaphore *S) 
{
    S->value++;
    if (S->value <= 0) {
        remove a process P fron< S->list;
        wakeup(P);
    }
}

Point to note is <= 0. Stallings code too uses <= 0. Even if process 2 makes wait(c) calls $n$ number of times, it will be allowed to run at least once by process 1 when it does signal(c). Or in other words, every signal() always wakes up at least one process waiting on the corresponding semaphore. So I feel A will always be printed once irrespective of initial value of c. Isnt it?