GATE CS Operating Systems Previous Year Questions

GATE CS 2024 Set 1 | Question 25

MSQ · 1 mark

Which of the following process state transitions is/are NOT possible?

Running to Ready Waiting to Running Ready to Waiting Running to Terminated

Explanation

Answer: (B), (C)

In the process state diagram the moves are: Ready to Running (dispatch), Running to Ready (preemption, for example when the time slice ends), Running to Waiting (an I/O request or a wait for an event), Waiting to Ready (the event completes) and Running to Terminated (exit).

Waiting to Running is not possible: when its event completes, a waiting process joins the ready queue, and only the scheduler can dispatch it from there.
Ready to Waiting is not possible: a process blocks only by doing something, such as requesting I/O, and a ready process is not executing.

Running to Ready and Running to Terminated are normal transitions, so A and D are possible.

Answer: B, C

GATE CS 2024 Set 1 | Question 40

MCQ · 2 marks · −0.66

Consider the following two threads T1 and T2 that update two shared variables a and b. Assume that initially a = b = 1. Though context switching between threads can happen at any time, each statement of T1 or T2 is executed atomically without interruption.

    T1                T2

a = a + 1;        b = 2 * b;
b = b + 1;        a = 2 * a;

Which one of the following options lists all the possible combinations of values of a and b after both T1 and T2 finish execution?

(a = 4, b = 4); (a = 3, b = 3); (a = 4, b = 3) (a = 3, b = 4); (a = 4, b = 3); (a = 3, b = 3) (a = 4, b = 4); (a = 4, b = 3); (a = 3, b = 4) (a = 2, b = 2); (a = 2, b = 3); (a = 3, b = 4)

Explanation

Answer: (A)

Each thread runs its two statements in order, so the four atomic statements interleave in \(\binom{4}{2} = 6\) ways. Writing the results as \((a, b)\):

T1 entirely first: \(a = 2\), \(b = 2\), then \(b = 4\), \(a = 4\): (4, 4).
T2 entirely first: \(b = 2\), \(a = 2\), then \(a = 3\), \(b = 3\): (3, 3).
Each of the other four orders runs a = a + 1 before a = 2 * a and b = 2 * b before b = b + 1, giving (4, 3).

(3, 4) is impossible: \(a = 3\) needs T2 to finish before T1 starts, while \(b = 4\) needs T1 to finish before T2 starts. Options B, C and D all contain it.

Answer: A

GATE CS 2024 Set 1 | Question 57

NAT · 2 marks

Consider the following code snippet using the fork() and wait() system calls. Assume that the code compiles and runs correctly, and that the system calls run successfully without any errors.

int x = 3;
while(x > 0) {
  fork();
  printf("hello");
  wait(NULL);
  x--;
}

The total number of times the printf statement is executed is _______

Your answer

Explanation

Answer: 14

After each fork(), the parent and the new child both call printf once and then continue the loop with the same value of x. So every pass doubles the number of processes, and each of them prints once:

\(x = 3\): 2 processes print.
\(x = 2\): 4 processes print.
\(x = 1\): 8 processes print.

The total is \(2 + 4 + 8 = 14\). wait(NULL) only makes a parent wait for its children; it changes the order of execution, not the count. (More than 14 copies of "hello" can finally appear, because fork() copies unflushed output; the question counts executions of the statement.)

Answer: 14

GATE CS 2024 Set 1 | Question 62

NAT · 2 marks

Consider a memory management system that uses a page size of 2 KB. Assume that both the physical and virtual addresses start from 0. Assume that the pages 0, 1, 2, and 3 are stored in the page frames 1, 3, 2, and 0, respectively. The physical address (in decimal format) corresponding to the virtual address 2500 (in decimal format) is _________

Your answer

Explanation

Answer: 6596

A page holds \(2\ \text{KB} = 2048\) bytes, so split the virtual address into a page number and an offset:

page number \(= \lfloor 2500 / 2048 \rfloor = 1\);
offset \(= 2500 - 2048 = 452\).

Page 1 is stored in frame 3 (the second pair in the list), and the offset carries over unchanged:

\[3 \times 2048 + 452 = 6144 + 452 = 6596\]

Answer: 6596

GATE CS 2024 Set 2 | Question 24

MSQ · 1 mark

Which of the following tasks is/are the responsibility/responsibilities of the memory management unit (MMU) in a system with paging-based memory management?

Allocate a new page table for a newly created process Translate a virtual address to a physical address using the page table Raise a trap when a virtual address is not found in the page table Raise a trap when a process tries to write to a page marked with read-only permission in the page table

Explanation

Answer: (B), (C), (D)

The MMU is the hardware between the CPU and memory that handles every memory reference. Its jobs are the ones done on each access:

B: it translates each virtual address to a physical address through the page table, with the TLB caching recent translations.
C: if the page table entry is invalid or not present, it cannot translate the address and raises a trap (a page fault) for the OS to handle.
D: it checks the protection bits on every access and traps when a process writes to a read-only page.

A is not an MMU task. Creating a process and allocating and filling its page table is done in software by the operating system kernel; the MMU only uses the table the OS has set up, for example through the page-table base register.

Answer: B, C, D

GATE CS 2024 Set 2 | Question 25

MSQ · 1 mark

Consider a process P running on a CPU. Which one or more of the following events will always trigger a context switch by the OS that results in process P moving to a non-running state (e.g., ready, blocked)?

P makes a blocking system call to read a block of data from the disk P tries to access a page that is in the swap space, triggering a page fault An interrupt is raised by the disk to deliver data requested by some other process A timer interrupt is raised by the hardware

Explanation

Answer: (A), (B)

The test is whether P could carry on running after the event.

A: a blocking read must wait for the disk, so P is moved to the blocked state and the OS switches to another process (or the idle task). Always.
B: the missing page has to be read in from swap space, which is slow disk I/O, so P blocks until the page arrives. Always.
C: the handler marks the other process ready, but P can simply resume afterwards; P is switched out only if the scheduler decides to preempt it. Not always.
D: the timer handler may find that P's time slice has not run out, or that no other process is ready, and return to P. Not always.

Answer: A, B

GATE CS 2024 Set 2 | Question 37

MCQ · 2 marks · −0.66

Consider a single processor system with four processes A, B, C, and D, represented as given below, where for each process the first value is its arrival time, and the second value is its CPU burst time.

A (0, 10), B (2, 6), C (4, 3), and D (6, 7).

Which one of the following options gives the average waiting times when preemptive Shortest Remaining Time First (SRTF) and Non-Preemptive Shortest Job First (NP-SJF) CPU scheduling algorithms are applied to the processes?

SRTF = 6, NP-SJF = 7 SRTF = 6, NP-SJF = 7.5 SRTF = 7, NP-SJF = 7.5 SRTF = 7, NP-SJF = 8.5

Explanation

Answer: (B)

SRTF: A runs 0–2. B (6) preempts A (8 left) and runs 2–4. C (3) preempts B (4 left) and runs 4–7; D arrives at 6 but needs 7, more than C’s last unit. Then B runs 7–11, D 11–18 and A 18–26.

Waiting time = completion − arrival − burst: A \(26 - 0 - 10 = 16\), B \(11 - 2 - 6 = 3\), C \(7 - 4 - 3 = 0\), D \(18 - 6 - 7 = 5\). Average \(= 24/4 = 6\).

NP-SJF: A, alone at time 0, runs 0–10 without interruption. Then the shortest waiting job goes first each time: C 10–13, B 13–19, D 19–26. Waiting times: A 0, C 6, B 11, D 13. Average \(= 30/4 = 7.5\).

Answer: B

GATE CS 2024 Set 2 | Question 46

MSQ · 2 marks

Consider a multi-threaded program with two threads T1 and T2. The threads share two semaphores: s1 (initialized to 1) and s2 (initialized to 0). The threads also share a global variable x (initialized to 0). The threads execute the code shown below.

// code of T1
wait(s1);
x = x+1;
print(x);
wait(s2);
signal(s1);

// code of T2
wait(s1);
x = x+1;
print(x);
signal(s2);
signal(s1);

Which of the following outcomes is/are possible when threads T1 and T2 execute concurrently?

T1 runs first and prints 1, T2 runs next and prints 2 T2 runs first and prints 1, T1 runs next and prints 2 T1 runs first and prints 1, T2 does not print anything (deadlock) T2 runs first and prints 1, T1 does not print anything (deadlock)

Explanation

Answer: (B), (C)

Only one thread at a time can be between wait(s1) and signal(s1), and s2 starts at 0.

If T2 gets s1 first, it prints 1, and its signal(s2) and signal(s1) never block. T1 then enters, prints 2, finds s2 at 1 and finishes. So (B) is possible, and (D) is not: T1 cannot stay blocked.
If T1 gets s1 first, it prints 1 and blocks on wait(s2) while still holding s1. Only T2 could signal s2, but it is stuck at wait(s1), so both wait forever and T2 prints nothing. So (C) is possible and (A) is not.

Answer: B, C

GATE CS 2024 Set 2 | Question 53

NAT · 2 marks

Consider a disk with the following specifications: rotation speed of 6000 RPM, average seek time of 5 milliseconds, 500 sectors/track, 512-byte sectors. A file has content stored in 3000 sectors located randomly on the disk. Assuming average rotational latency, the total time (in seconds, rounded off to 2 decimal places) to read the entire file from the disk is _________

Your answer

Explanation

Answer: 29.5 to 30.5

At 6000 RPM the disk makes 100 rotations per second, so one rotation takes 10 ms.

Seek time: 5 ms.
Average rotational latency: half a rotation, 5 ms.
Transfer time of one sector: \(10 / 500 = 0.02\) ms.

Because the sectors lie at random places, each one needs its own seek and rotational wait: \(5 + 5 + 0.02 = 10.02\) ms per sector. For 3000 sectors the total is \(3000 \times 10.02 = 30060\) ms, that is 30.06 s. The sector size (512 bytes) is not needed. Treating the file as stored on consecutive sectors would give a much smaller time.

Answer: 30.06

GATE CS 2024 Set 2 | Question 64

NAT · 2 marks

Consider a 32-bit system with 4 KB page size and page table entries of size 4 bytes each. Assume 1 KB = \(2^{10}\) bytes. The OS uses a 2-level page table for memory management, with the page table containing an outer page directory and an inner page table. The OS allocates a page for the outer page directory upon process creation. The OS uses demand paging when allocating memory for the inner page table, i.e., a page of the inner page table is allocated only if it contains at least one valid page table entry.

An active process in this system accesses 2000 unique pages during its execution, and none of the pages are swapped out to disk. After it completes the page accesses, let \(X\) denote the minimum and \(Y\) denote the maximum number of pages across the two levels of the page table of the process.

The value of \(X+Y\) is ________

Your answer

Explanation

Answer: 1028

A 4 KB page holds \(2^{12} / 4 = 1024\) entries. So one inner page-table page maps 1024 pages, and the outer directory (one page, 1024 entries) can point to at most 1024 inner pages. The directory page always exists.

Minimum: the 2000 pages fall into as few 1024-page regions as possible, \(\lceil 2000 / 1024 \rceil = 2\) inner pages, so \(X = 1 + 2 = 3\).
Maximum: the pages are spread out so that each inner page has few valid entries. With 2000 pages and only 1024 possible inner pages, all 1024 can be in use, so \(Y = 1 + 1024 = 1025\).

Hence \(X + Y = 3 + 1025 = 1028\).

Answer: 1028