Operating System GATE 2022 Solved Questions

Ques 1: Consider the following threads, T1,T2 and T3 executing on a single processor, synchronized using three binary semaphore variables, S1,S2 and S3, operated upon using standard wait() and signal(). The threads can be context switched in any order and at any time.

GATE 2022 Q no 19

T1	T2	T3
while(true){ wait(S3); print(“C”); signal(S2); }	while(true){ wait(S1); print(“B”); signal(S3); }	while(true){ wait(S2); print(“A”); signal(S1); }

Which initialization of the semaphores would print the sequence BCABCABCA…?

(A) S1 = 1; S2 = 1; S3 = 1

(B) S1 = 1; S2 = 1; S3 = 0

(C) S1 = 1; S2 = 0; S3 = 0

(D) S1 = 0; S2 = 1; S3 = 1

Ans: (C) S1 = 1; S2 = 0; S3 = 0

Solution:

• Thread T2 prints B. 
• Thread T1 prints C. 
• Thread T3 prints A.

These three threads are executing on a single processor.

We want these threads to be synchronized in such a way that we get the sequence BCABCABCA………. printed.

The threads can be context switched in any order and at any time.

But in whichever order they run, pre-empt, run again;

The sequence that should be printed is BCABCABCA…

Hence, Logically, we want the threads to execute in the following order : T2,T1,T3,T2,T1,T3,T2,T1,T3….

First T2 should be able to print. Hence, binary semaphore S1 must be 1 initially.

Clearly, first T1 Or T3 should not be able to print, So, S3=0,S2=0

Also, with S1=1,S3=0,S2=0 initially, we can verify that the sequence BCABCABCA…is printed, as following :

T2 prints B, then wakes up T1.

T1 prints C, then wakes up T3.

T3 prints A, then wakes up T2.

Same scenario repeats continuously.

Ques 2: Which of the following statements is/are TRUE with respect to deadlocks?

GATE 2022 Q no 26

(A) Circular wait is a necessary condition for the formation of deadlock.

(B) In a system where each resource has more than one instance, a cycle in its wait-for graph indicates the presence of a deadlock.

(C) If the current allocation of resources to processes leads the system to unsafe state, then deadlock will necessarily occur.

(D) In the resource-allocation graph of a system, if every edge is an assignment edge, then the system is not in deadlock state.

Ans: (A) & (D)

Solution:

• Circular Wait is one of the four necessary conditions for deadlock to happen. True
   
• Not necessarily, if every resource had only a single instance then, a cycle would’ve been necessary and sufficient for a deadlock to occur. A Cycle in a multi-instance resource is necessary but isn’t sufficient and in this case, each resource is made up of more than one instance, a simple contradiction. False
   
• An Unsafe state is where no method of allocation of resources can prevent deadlock from happening. Whereas in a safe state, there exists a method of allocation in which all processes are complete. False
   
• Resource Allocation graph accommodates future resource requirements in the form of request edges. If there are no request edges, then resource requirements for all the processes are satisfied. True

Ques 3: Which one of the following statements is FALSE?

GATE 2022 Q no 38

(A) The TLB performs an associative search in parallel on all its valid entries using page number of incoming virtual address.

(B) If the virtual address of a word given by CPU has a TLB hit, but the subsequent search for the word results in a cache miss, then the word will always be present in the main memory.

(C) The memory access time using a given inverted page table is always same for all incoming virtual addresses.

(D) In a system that uses hashed page tables, if two distinct virtual addresses V1 and V2 map to the same value while hashing, then the memory access time of these addresses will not be the same.

Ans: (C) The memory access time using a given inverted page table is always same for all incoming virtual addresses.

Solution:

1. “The TLB is associative, high-speed memory. Each entry in the TLB consists of two parts: a key (or tag) and a value. When the associative memory is presented with an item, the item is compared with all keys simultaneously. If the item is found, the corresponding value field is returned.” Hence option A is TRUE. 

2. The TLB contains only a few of the page-table entries. If the virtual address of a word given by CPU has a TLB hit it means the the page number is found, so its frame number is immediately available and is used to access memory. Therefore even if the subsequent search for the word results in a cache miss, it does not matter. Its just not in cache memory but the word will always be present in the main memory as we already know the frame number due to the TLB Hit. Hence option B is also TRUE. 

3. An Inverted Page Table has frame numbers as indexes unlike a Page Table where page number is used as index to it. Therefore for any given virtual address we need to search the exact <page no., process no.> in the frames of MM.This increases main memory access time. This is the reason why Inverted Page table uses less space but searching time is more. Therefore the memory access time using a given inverted page table is not always same for all incoming virtual addresses. Hence option C is FALSE and is the ans. 

4. In a system that uses hashed page tables, if two distinct virtual addresses V1 and V2 map to the same value while hashing, it means they will be present as a linked list of items having same hashed values. Then the memory access time of these addresses will not be the same as in a Linked List the best case T.C = Omega(1) for the first element and worst case T.C. = O(N) for the last element in chained LL. Hence option D is also TRUE. 

Ques 4: Consider four processes P, Q, R, and S scheduled on a CPU as per round robin algorithm with a time quantum of 4 units. The processes arrive in the order P, Q, R, S, all at time t = 0. There is exactly one context switch from S to Q, exactly one context switch from R to Q, and exactly two context switches from Q to R. There is no context switch from S to P. Switching to a ready process after the termination of another process is also considered a context switch. Which one of the following is NOT possible as CPU burst time (in time units) of these processes?

GATE 2022 Q no 42

(A) P = 4, Q = 10, R = 6, S = 2

(B) P = 2, Q = 9, R = 5, S = 1

(C) P = 4, Q = 12, R = 5, S = 4

(D) P = 3, Q = 7, R = 7, S = 3

Ans: (D) P = 3, Q = 7, R = 7, S = 3

Solution: Round Robin QUEUE :–  P,Q,R,S,P,Q,R,S,P,Q,R,S…..

Given that processes arrived in the order P,Q,R and S.

1. Switching to ready processes after termination of currently executing process also a context switch.
2. There is no context switch from S to P. ( Therefore P should be complete with in 1 TQ )
3. There are exactly two context switches from Q to R ( Therefore Q and R both should requires more than 1 TQ )
4. There is exactly one context switch from R to Q ( Therefore Q require more time than R )
5. Exactly one context switch from R to S. ( Therefore S should be complete with in 1 TQ otherwise another CS from R to S required.)
6. Exactly one context switch from S to Q

Accumulating all the above points

QUEUE :   P,Q,R,S,Q,R,Q

Given that time quantum = 4

• 0<P_BT≤4
• 0<S_BT≤4
• 8<Q_BT
• 4<R_BT≤8

In option D, Q’s BT=7, which is not possible.