List of top Operating System Questions asked in GATE CS

Processes $ P_1, P_2, P_3, P_4 $ arrive in that order at times 0, 1, 2, and 8 milliseconds respectively, and have execution times of 10, 13, 6, and 9 milliseconds respectively. Shortest Remaining Time First (SRTF) algorithm is used as the CPU scheduling policy. Ignore context switching times. Which ONE of the following correctly gives the average turnaround time of the four processes in milliseconds?

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.

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

Which one of the following statements is FALSE?

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 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?

Consider two file 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 the 50th and 51st 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

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, 1, 5, 6, 1 \] The page fault rate, defined as the ratio of the number of page faults to the number of memory accesses (rounded off to one decimal place) is $\underline{\hspace{1cm}}$.

Which of the following statement(s) is/are correct in the context of CPU scheduling?

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() { 
	create a thread to execute foo(); // Thread T1 
	create a thread to execute foo(); // Thread T2 
	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?

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?

Consider a three-level page table to translate a 39-bit virtual address to a physical address as shown. The page size is 4KB and page table entry size at every level is 8 bytes. A process $ P $ is currently using 2GB virtual memory mapped to 2GB physical memory. The minimum amount of memory required for the page table of $ P $ across all levels is $\underline{\hspace{2cm}}$ KB.

In the context of operating systems, which of the following statements is/are correct with respect to paging?

Which of the following standard C library functions will always invoke a system call when executed from a single-threaded process in a UNIX/Linux operating system?

Consider a linear list based directory implementation in a file system. Each directory is a list of nodes, where each node contains the file name along with the file metadata, such as the list of pointers to the data blocks. Consider a given directory \texttt{foo. Which of the following operations will necessarily require a full scan of \texttt{foo} for successful completion?}

Three processes arrive at time zero with CPU bursts of 16, 20, and 10 milliseconds. If the scheduler has prior knowledge about the length of the CPU bursts, the minimum achievable average waiting time for these three processes in a non-preemptive scheduler (rounded to nearest integer) is $\underline{\hspace{2cm}}$ milliseconds.

Consider the following pseudocode, where S is a semaphore initialized to 5 in line#2 and counter is a shared variable initialized to 0 in line #1. Assume that the increment operation in line#7 is not atomic.

1. int counter = 0; 
2. Semaphore S = init(5); 
3. void parop(void) 
4. { 
5.     wait(S); 
6.     wait(S); 
7.     counter++; 
8.     signal(S); 
9.     signal(S); 
10. }

If five threads execute the function parop concurrently, which of the following program behavior(s) is/are possible?