Operating Systems

GATE CS previous year questions · 20 questions

Topics

GATE CS 2025 Set 1 | Question 14

MCQ · 1 mark · −0.33

Consider a demand paging memory management system with 32-bit logical address, 20-bit physical address, and page size of 2048 bytes. Assuming that the memory is byte addressable, what is the maximum number of entries in the page table?

Options for GATE CS 2025 Set 1 | Question 14

Explanation

Answer: (A)

A page table has one entry for each page of the logical address space. The page size is \(2048 = 2^{11}\) bytes, so the number of pages is \(\frac{2^{32}}{2^{11}} = 2^{21}\). The 20-bit physical address affects only the size of each entry (a frame number of \(20 - 11 = 9\) bits), not the number of entries.

Answer: A

GATE CS 2025 Set 1 | Question 29

NAT · 1 mark

Suppose in a multiprogramming environment, the following C program segment is executed. A process goes into I/O queue whenever an I/O related operation is performed. Assume that there will always be a context switch whenever a process requests for an I/O, and also whenever the process returns from an I/O. The number of times the process will enter the ready queue during its lifetime (not counting the time the process enters the ready queue when it is run initially) is _______. (Answer in integer)

int main()
{
    int x=0,i=0;
    scanf("%d",&x);
    for(i=0; i<20; i++)
    {
        x = x+20;
        printf("%d\n",x);
    }
    return 0;
}

Explanation

Answer: 21

Every I/O call moves the process from the CPU to the I/O queue, and when that I/O completes the process re-enters the ready queue. So we only need to count the I/O operations.

The program performs one scanf and 20 printf calls (one in each iteration, \(i = 0\) to \(19\)); the addition and return 0 need no I/O.

Entries into the ready queue \(= 1 + 20 = 21\).

Answer: 21

GATE CS 2025 Set 1 | Question 38

MCQ · 2 marks · −0.66

A computer has two processors, \(M_1\) and \(M_2\). Four processes \(P_1, P_2, P_3, P_4\) with CPU bursts of 20, 16, 25, and 10 milliseconds, respectively, arrive at the same time and these are the only processes in the system. The scheduler uses non-preemptive priority scheduling, with priorities decided as follows:

  • \(M_1\) uses priority of execution for the processes as, \(P_1 \gt P_3 \gt P_2 \gt P_4\), i.e., \(P_1\) and \(P_4\) have highest and lowest priorities, respectively.
  • \(M_2\) uses priority of execution for the processes as, \(P_2 \gt P_3 \gt P_4 \gt P_1\), i.e., \(P_2\) and \(P_1\) have highest and lowest priorities, respectively.

A process \(P_i\) is scheduled to a processor \(M_k\), if the processor is free and no other process \(P_j\) is waiting with higher priority. At any given point of time, a process can be allocated to any one of the free processors without violating the execution priority rules. Ignore the context switch time. What will be the average waiting time of the processes in milliseconds?

Options for GATE CS 2025 Set 1 | Question 38

Explanation

Answer: (A)

Simulate both processors. Whenever a processor becomes free, it takes the waiting process that ranks highest in its own priority list.

  • \(t = 0\): \(M_1\) takes \(P_1\) (runs 0 to 20) and \(M_2\) takes \(P_2\) (runs 0 to 16).
  • \(t = 16\): \(M_2\) is free; \(P_3\) and \(P_4\) are waiting, and \(M_2\) prefers \(P_3\) (runs 16 to 41).
  • \(t = 20\): \(M_1\) is free and only \(P_4\) is left (runs 20 to 30).

All processes arrive at time 0, so each waiting time equals its start time: \(0 + 0 + 16 + 20 = 36\), and the average is \(36 / 4 = 9.00\) ms.

Answer: A

GATE CS 2025 Set 1 | Question 51

NAT · 2 marks

A disk of size 512M bytes is divided into blocks of 64K bytes. A file is stored in the disk using linked allocation. In linked allocation, each data block reserves 4 bytes to store the pointer to the next data block. The link part of the last data block contains a NULL pointer (also of 4 bytes). Suppose a file of 1M bytes needs to be stored in the disk. Assume, \(1\text{K} = 2^{10}\) and \(1\text{M} = 2^{20}\). The amount of space in bytes that will be wasted due to internal fragmentation is ______. (Answer in integer)

Explanation

Answer: 65468

Each block is \(64\text{K} = 65536\) bytes and 4 of them hold the link, so a block carries \(65536 - 4 = 65532\) bytes of file data.

The file has \(2^{20} = 1048576\) bytes. Sixteen blocks carry \(16 \times 65532 = 1048512\) bytes, which leaves \(1048576 - 1048512 = 64\) bytes for a 17th block.

The last block holds those 64 bytes and the 4-byte NULL link, so the unused space is \(65536 - 4 - 64 = 65468\) bytes.

Answer: 65468

GATE CS 2025 Set 1 | Question 54

NAT · 2 marks

In optimal page replacement algorithm, information about all future page references is available to the operating system (OS). A modification of the optimal page replacement algorithm is as follows:

The OS correctly predicts only up to next 4 page references (including the current page) at the time of allocating a frame to a page.

A process accesses the pages in the following order of page numbers:

1, 3, 2, 4, 2, 3, 1, 2, 4, 3, 1, 4.

If the system has three memory frames that are initially empty, the number of page faults that will occur during execution of the process is ________ . (Answer in integer)

Explanation

Answer: 6

On a fault with all frames full, look at the current reference and the next three. Replace a resident page that is not in this window; if all of them are in it, replace the one needed last.

  • 1, 3, 2: three faults fill the frames: {1, 3, 2}.
  • 4: fault. Window 4, 2, 3, 1, so page 1 is needed last; replace it: {4, 3, 2}. The next 2 and 3 are hits.
  • 1: fault. Window 1, 2, 4, 3, so page 3 is needed last; replace it: {4, 1, 2}. The next 2 and 4 are hits.
  • 3: fault. Window 3, 1, 4 does not contain page 2; replace it: {4, 1, 3}. The last 1 and 4 are hits.

Total page faults \(= 3 + 1 + 1 + 1 = 6\).

Answer: 6

GATE CS 2025 Set 2 | Question 26

MCQ · 1 mark · −0.33

Processes \(P1\), \(P2\), \(P3\), \(P4\) 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?

Options for GATE CS 2025 Set 2 | Question 26

Explanation

Answer: (D)

SRTF always runs the ready process with the least remaining time, re-checking whenever a process arrives.

  • 0–2: \(P1\) runs. At time 1, \(P2\) needs 13 but \(P1\) only 9 more.
  • 2–8: \(P3\) (6) preempts \(P1\) (8 left) and finishes at 8.
  • 8–16: \(P4\) arrives needing 9, but \(P1\) needs only 8, so \(P1\) finishes at 16.
  • 16–25: \(P4\) (9) runs before \(P2\) (13).
  • 25–38: \(P2\) runs.

Turnaround time = completion − arrival: \(P1 = 16\), \(P2 = 37\), \(P3 = 6\), \(P4 = 17\). The average is \((16 + 37 + 6 + 17)/4 = 76/4 = 19\) ms; 37 is only \(P2\)'s turnaround time.

Answer: D

GATE CS 2025 Set 2 | Question 47

MSQ · 2 marks

Consider a demand paging system with three frames, and the following page reference string: 1 2 3 4 5 4 1 6 4 5 1 3 2. The contents of the frames are as follows initially and after each reference (from left to right):

initiallyafter
-1*2*3*4*5*416*451*3*2*
-1111111666662
--224444444111
---33555555533

The *-marked references cause page replacements.

Which one or more of the following could be the page replacement policy/policies in use?

Options for GATE CS 2025 Set 2 | Question 47

Explanation

Answer: (D)

The table replaces page 2 at the 4th reference, 3 at the 5th, 1 at the 8th, and then 4, 5 and 6 at the last three.

  • Optimal fits. At the 4th reference the frames hold 1, 2, 3, next used at references 7, 13 and 12, so 2, needed farthest ahead, goes. Likewise 3 goes at the 5th reference and 1 at the 8th. At the last three faults no page in memory is used again, so any victim is optimal.
  • LRU fails: at the 4th reference it would evict 1, the least recently used page.
  • LFU fails: at the 8th reference page 5 has one use and pages 1 and 4 have two, so it would evict 5.
  • MFU fails: at the 4th reference pages 1, 2 and 3 have one use each, and a first-in or least-recently-used tie-break evicts 1, not 2.

Answer: D

GATE CS 2025 Set 2 | Question 48

MSQ · 2 marks

\(P = \{P_1, P_2, P_3, P_4\}\) consists of all active processes in an operating system.
\(R = \{R_1, R_2, R_3, R_4\}\) consists of single instances of distinct types of resources in the system.

The resource allocation graph has the following assignment and claim edges.

Assignment edges: \(R_1 \to P_1,\ R_2 \to P_2,\ R_3 \to P_3,\ R_4 \to P_4\) (the assignment edge \(R_1 \to P_1\) means resource \(R_1\) is assigned to process \(P_1\), and so on for others)

Claim edges: \(P_1 \to R_2,\ P_2 \to R_3,\ P_3 \to R_1,\ P_2 \to R_4,\ P_4 \to R_2\) (the claim edge \(P_1 \to R_2\) means process \(P_1\) is waiting for resource \(R_2\), and so on for others)

Which of the following statement(s) is/are CORRECT?

Options for GATE CS 2025 Set 2 | Question 48

Explanation

Answer: (C), (D)

Every resource has a single instance, so a cycle means deadlock. Turn each edge pair into a waits-for edge between processes: \(P_1 \to P_2\) (for \(R_2\)), \(P_2 \to P_3\) (for \(R_3\)), \(P_2 \to P_4\) (for \(R_4\)), \(P_3 \to P_1\) (for \(R_1\)) and \(P_4 \to P_2\) (for \(R_2\)). That gives two cycles, \(P_1 \to P_2 \to P_3 \to P_1\) and \(P_2 \to P_4 \to P_2\), and both pass through \(P_2\).

  • Aborting \(P_1\) leaves the cycle \(P_2 \to P_4 \to P_2\) (A false).
  • Aborting \(P_3\) leaves the same cycle (B false).
  • Aborting \(P_2\) breaks both cycles (C true).
  • Aborting \(P_1\) and \(P_4\) removes a process from each cycle; only \(P_2 \to P_3\) remains (D true).

Answer: C, D

GATE CS 2025 Set 2 | Question 58

NAT · 2 marks

A computer system supports a logical address space of \(2^{32}\) bytes. It uses two-level hierarchical paging with a page size of 4096 bytes. A logical address is divided into a \(b\)-bit index to the outer page table, an offset within the page of the inner page table, and an offset within the desired page. Each entry of the inner page table uses eight bytes. All the pages in the system have the same size.

The value of \(b\) is ___________ . (Answer in integer)

Explanation

Answer: 11

Split the 32-bit logical address from the right:

  • Offset within the desired page: \(4096 = 2^{12}\) bytes, so 12 bits.
  • Offset within a page of the inner page table: one page holds \(4096 / 8 = 512 = 2^{9}\) eight-byte entries, so 9 bits.
  • Outer page table index: whatever is left, \(b = 32 - 12 - 9 = 11\).

So the outer page table has \(2^{11} = 2048\) entries, each pointing to one page of the inner page table.

Answer: 11

GATE CS 2024 Set 1 | Question 24

MSQ · 1 mark

Which of the following statements about threads is/are TRUE?

Options for GATE CS 2024 Set 1 | Question 24

Explanation

Answer: (D)

  • A: false. Threads can also be implemented in user space by a thread library, with the kernel seeing only one process (the many-to-one model).
  • B: false. Open files belong to the process, so all its threads share one file descriptor table; a file opened by one thread can be used by the others.
  • C: false. Each thread runs its own chain of function calls, so it needs its own stack, along with its own registers and program counter.
  • D: true. The threads of a process share one address space, so any of them can read or overwrite the data of the others. The operating system puts no protection boundary between them; that is the price of cheap sharing.

Answer: D