# Operating System

 Question 1
Consider a demand paging system with four page frames (initially empty) and LRU page replacement policy. For the following page reference string

7, 2, 7, 3, 2, 5, 3, 4, 6, 7, 7,1, 5, 6,1

the page fault rate, defined as the ratio of number of page faults to the number of memory accesses (rounded off to one decimal place) is
 A 0.4 B 0.5 C 0.6 D 0.7
GATE CSE 2022      Memory Management
Question 1 Explanation:
 Question 2
Consider two files systems A and B , that use contiguous allocation and linked allocation, respectively. A file of size 100 blocks is already stored in A and also in B. Now, consider inserting a new block in the middle of the file (between $50^{th} \text{ and }51^{st}$ block), whose data is already available in the memory. Assume that there are enough free blocks at the end of the file and that the file control blocks are already in memory. Let the number of disk accesses required to insert a block in the middle of the file in A and B are $n_A$ and $n_B$, respectively, then the value of $n_A+n_B$ is
 A 50 B 51 C 101 D 153
GATE CSE 2022      File System
Question 2 Explanation:
 Question 3
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?
 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
GATE CSE 2022      CPU Scheduling
Question 3 Explanation:
 Question 4
Which one of the following statements is FALSE?
 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.
GATE CSE 2022      Memory Management
Question 4 Explanation:
 Question 5
Which of the following statements is/are TRUE with respect to deadlocks?
MSQ
 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.
Question 5 Explanation:
 Question 6
Consider the following threads, $T_1, T_2, \text{ and }T_3$ executing on a single processor, synchronized using three binary semaphore variables, $S_1, S_2, \text{ and }S_3$, operated upon using standard $wait()$ and $signal()$. The threads can be context switched in any order and at any time. Which initialization of the semaphores would print the sequence BCABCABCA ...?
 A $S_1 = 1; S_2 = 1; S_3 = 1$ B $S_1 = 1; S_2 = 1; S_3 = 0$ C $S_1 = 1; S_2 = 0; S_3 = 0$ D $S_1 = 0; S_2 = 1; S_3 = 1$
GATE CSE 2022      Process Synchronization
Question 6 Explanation:
 Question 7
Consider a three-level page table to translate a 39-bit virtual address to a physical address as shown below: The page size is 4 KB = (1KB =$2^{10}$ bytes) and page table entry size at every level is 8 bytes. A process P is currently using 2 GB (1 GB =$2^{30}$ bytes) virtual memory which os mapped to 2 GB of physical memory. The minimum amount of memory required for the page table of P across all levels is _________ KB
 A 1024 B 4096 C 4108 D 1864
GATE CSE 2021 SET-2      Memory Management
Question 7 Explanation:
 Question 8
Consider a computer system with multiple shared resource types, with one instance per resource type. Each instance can be owned by only one process at a time. Owning and freeing of resources are done by holding a global lock (L). The following scheme is used to own a resource instance:
 function OWNRESOURCE(Resource R)
Acquire lock L // a global lock
if R is available then
Acquire R
Release lock L
else
if R is owned by another process P then
Terminate P, after releasing all resources owned by P
Acquire R
Restart P
Release lock L
end if
end if
end function
Which of the following choice(s) about the above scheme is/are correct?
[MSQ]
 A The scheme ensures that deadlocks will not occur B The scheme may lead to live-lock C The scheme may lead to starvation D The scheme violates the mutual exclusion property
GATE CSE 2021 SET-2      Process Synchronization
Question 8 Explanation:
 Question 9
Consider the following multi-threaded code segment (in a mix of C and pseudo-code), invoked by two processes P1 and P2, and each of the processes spawns two threads T1 and T2:
int x = 0;  // global
Lock L1;    // global
main () {
wait for the two threads to finish execution;
print(x);}

foo() {
int y = 0;
Acquire L1;
x = x + 1;
y = y + 1;
Release L1;
print (y);} 
Which of the following statement(s) is/are correct?
[MSQ]
 A Both P1 and P2 will print the value of x as 2. B At least of P1 and P2 will print the value of x as 4. C At least one of the threads will print the value of y as 2. D Both T1 and T2, in both the processes, will print the value of y as 1.