GATE Solved Paper 2020 - GATE 2020

32. Each of a set of Q.28 n processes executes the following code using two semaphores a and b initialized to 1 and 0, respectively. Assume that count is a shared variable initialized to 0 and not used in CODE SECTION P.

   CODE SECTION P
wait(a); count=count+1;
if (count==n) signal(b);
signal(a); wait(b); signal(b);
   CODE SECTION Q

What does the code achieve?

  • Option : C
  • Explanation :
    Subject Operating Systems
    a = 1 b = 0 count = 0
    Code section P: For process 1
    Wait (a) ⇒ a = 0
    Count ++ ⇒ count = 1
    If (count = = n) ⇒ false
    signal (a) ⇒ a = 0
    wait (b) process blocked
    As shown above, all processes execute wait (b) before, signal (b) in if condition.
    Because, ‘if’ condition becomes True only for process Pn(nth process) [∵ if (count = = n)]
    So, before Pn process finishes the code section, P, no other process executes code section Q.
    Hence, no process executes code section Q before every process has finished code section P.
Cancel reply
Cancel reply

34. Consider the following languages.
L1 = {wxyx | w,x,y(0+1)+}
L2 = {xy | x,y(a + b)*,|x| = |y|, x y}
Which one of the following is TRUE?

  • Option : A
  • Explanation :
    L1 is regular and L2 is CFL.
    L1: {ω xyx| ω, x, y ϵ (0 + 1)*}
    We can write the regular expression for this,
    Let, x = 0
    L11 = ω 0 Y 0 ⇒ ( 0 + 1)+ 0(0 + 1)+0
    x = 1
    L12 = ω 1 Y 1 ⇒ we can generate all the strings and since a regular expression can be written for 4, we can say 4 is regular.
    L2 is CFL:
    L2 = {xy| x,y ϵ (a + b)*, |x| = |y|, x ≠ y}
    L2 generates strings of even length, which can be done by PDA, therefore L2 is CFL.
Cancel reply
Cancel reply