84 real GATE CSE questions from 2012 to 2025, with the official answer key and a worked solution for each. Filter by year, topic, type, marks or keyword.
Questions belong to the GATE organising institutes; this copy is for personal study. Coverage varies by year: questions that need a figure I could not read, or whose answer I could not verify, were left out.
Showing 84 of 84 questions · 0 correct of 0 attempted · marks 0 / 132
GATE 2025 CS1 · Q11MCQ1 markProcesses, Threads & System Calls
Suppose a program is running on a non-pipelined single processor computer system. The computer is connected to an external device that can interrupt the processor asynchronously. The processor needs to execute the interrupt service routine (ISR) to serve this interrupt. The following steps (not necessarily in order) are taken by the processor when the interrupt arrives: (i) The processor saves the content of the program counter. (ii) The program counter is loaded with the start address of the ISR. (iii) The processor finishes the present instruction. Which ONE of the following is the CORRECT sequence of steps?
GATE 2025 CS1 · Q14MCQ1 markMemory Management
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?
GATE 2025 CS2 · Q26MCQ1 markCPU Scheduling
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?
GATE 2025 CS1 · Q29NAT1 markProcesses, Threads & System Calls
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 ______.
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;
}
GATE 2025 CS1 · Q38MCQ2 marksCPU Scheduling
A computer has two processors, M1 and M2. Four processes P1, P2, P3, P4 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: M1 uses priority of execution for the processes as P1 > P3 > P2 > P4, i.e., P1 and P4 have highest and lowest priorities, respectively. M2 uses priority of execution for the processes as P2 > P3 > P4 > P1, i.e., P2 and P1 have highest and lowest priorities, respectively. A process Pi is scheduled to a processor Mk, if the processor is free and no other process Pj 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?
GATE 2025 CS2 · Q47MSQ2 marksVirtual Memory
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 three frames after each reference are: after 1*: (1, -, -); 2*: (1, 2, -); 3*: (1, 2, 3); 4*: (1, 4, 3); 5*: (1, 4, 5); 4: (1, 4, 5); 1: (1, 4, 5); 6*: (6, 4, 5); 4: (6, 4, 5); 5: (6, 4, 5); 1*: (6, 1, 5); 3*: (6, 1, 3); 2*: (2, 1, 3). The *-marked references cause page replacements. Which one or more of the following could be the page replacement policy/policies in use?
One or more options may be correct. Select all that apply, then submit.
GATE 2025 CS2 · Q48MSQ2 marksDeadlock
P = {P1, P2, P3, P4} consists of all active processes in an operating system. R = {R1, R2, R3, R4} 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: R1 → P1, R2 → P2, R3 → P3, R4 → P4 (the assignment edge R1 → P1 means resource R1 is assigned to process P1, and so on for others). Claim edges: P1 → R2, P2 → R3, P3 → R1, P2 → R4, P4 → R2 (the claim edge P1 → R2 means process P1 is waiting for resource R2, and so on for others). Which of the following statement(s) is/are CORRECT?
One or more options may be correct. Select all that apply, then submit.
GATE 2025 CS1 · Q51NAT2 marksFile Systems
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, 1K = 210 and 1M = 220. The amount of space in bytes that will be wasted due to internal fragmentation is ______.
GATE 2025 CS1 · Q54NAT2 marksVirtual Memory
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 ______.
GATE 2025 CS2 · Q58NAT2 marksMemory Management
A computer system supports a logical address space of 232 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 ______.
GATE 2024 CS2 · Q11MCQ1 markDisk Scheduling & I/O
Consider a computer with a 4 MHz processor. Its DMA controller can transfer 8 bytes in 1 cycle from a device to main memory through cycle stealing at regular intervals. Which one of the following is the data transfer rate (in bits per second) of the DMA controller if 1% of the processor cycles are used for DMA?
GATE 2024 CS1 · Q15MCQ1 markDisk Scheduling & I/O
Which one of the following statements is FALSE?
GATE 2024 CS1 · Q24MSQ1 markProcesses, Threads & System Calls
Which of the following statements about threads is/are TRUE?
One or more options may be correct. Select all that apply, then submit.
GATE 2024 CS2 · Q24MSQ1 markMemory Management
Which of the following tasks is/are the responsibility/responsibilities of the memory management unit (MMU) in a system with paging-based memory management?
One or more options may be correct. Select all that apply, then submit.
GATE 2024 CS1 · Q25MSQ1 markProcesses, Threads & System Calls
Which of the following process state transitions is/are NOT possible?
One or more options may be correct. Select all that apply, then submit.
GATE 2024 CS2 · Q25MSQ1 markProcesses, Threads & System Calls
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)?
One or more options may be correct. Select all that apply, then submit.
GATE 2024 CS2 · Q37MCQ2 marksCPU Scheduling
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?
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:
a = a + 1;
b = b + 1;
T2:
b = 2 * b;
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?
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). T1:
wait(s1);
x = x + 1;
print(x);
wait(s2);
signal(s1)
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?
One or more options may be correct. Select all that apply, then submit.
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 ______.
Consider a 512 GB hard disk with 32 storage surfaces. There are 4096 sectors per track and each sector holds 1024 bytes of data. The number of cylinders in the hard disk is ______.
GATE 2024 CS1 · Q57NAT2 marksProcesses, Threads & System Calls
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 ______.
GATE 2024 CS1 · Q62NAT2 marksMemory Management
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 ______.
GATE 2024 CS2 · Q64NAT2 marksMemory Management
Consider a 32-bit system with 4 KB page size and page table entries of size 4 bytes each. Assume 1 KB = 210 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 ______.
GATE 2023 · Q22MSQ1 markProcesses, Threads & System Calls
Which one or more of the following need to be saved on a context switch from one thread (T1) of a process to another thread (T2) of the same process?
One or more options may be correct. Select all that apply, then submit.
GATE 2023 · Q23MSQ1 markProcesses, Threads & System Calls
Which one or more of the following options guarantee that a computer system will transition from user mode to kernel mode?
One or more options may be correct. Select all that apply, then submit.
GATE 2023 · Q27MSQ1 markCPU Scheduling
Which one or more of the following CPU scheduling algorithms can potentially cause starvation?
One or more options may be correct. Select all that apply, then submit.
GATE 2023 · Q34NAT1 markDisk Scheduling & I/O
A keyboard connected to a computer is used at a rate of 1 keystroke per second. The computer system polls the keyboard every 10 ms (milli seconds) to check for a keystroke and consumes 100 μs (micro seconds) for each poll. If it is determined after polling that a key has been pressed, the system consumes an additional 200 μs to process the keystroke. Let T1 denote the fraction of a second spent in polling and processing a keystroke. In an alternative implementation, the system uses interrupts instead of polling. An interrupt is raised for every keystroke. It takes a total of 1 ms for servicing an interrupt and processing a keystroke. Let T2 denote the fraction of a second spent in servicing the interrupt and processing a keystroke. The ratio T1 / T2 is ______. (Rounded off to one decimal place)
Consider the two functions incr and decr shown below.
incr() {
wait(s);
X = X + 1;
signal(s);
}
decr() {
wait(s);
X = X - 1;
signal(s);
}
There are 5 threads each invoking incr once, and 3 threads each invoking decr once, on the same shared variable X. The initial value of X is 10. Suppose there are two implementations of the semaphore s, as follows: I-1: s is a binary semaphore initialized to 1. I-2: s is a counting semaphore initialized to 2. Let V1, V2 be the values of X at the end of execution of all the threads with implementations I-1, I-2, respectively. Which one of the following choices corresponds to the minimum possible values of V1, V2, respectively?
GATE 2023 · Q58NAT2 marksMemory Management
Consider a computer system with 57-bit virtual addressing using multi-level tree-structured page tables with L levels for virtual to physical address translation. The page size is 4 KB (1 KB = 1024 B) and a page table entry at any of the levels occupies 8 bytes. The value of L is ______.
GATE 2022 · Q17MCQ1 markDisk Scheduling & I/O
Which one of the following facilitates transfer of bulk data from hard disk to main memory with the highest throughput?
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. T1:
while (true) {
wait(S3);
print("C");
signal(S2);
}
T2:
while (true) {
wait(S1);
print("B");
signal(S3);
}
T3:
while (true) {
wait(S2);
print("A");
signal(S1);
}
Which initialization of the semaphores would print the sequence BCABCABCA....?
GATE 2022 · Q26MSQ1 markDeadlock
Which of the following statements is/are TRUE with respect to deadlocks?
One or more options may be correct. Select all that apply, then submit.
GATE 2022 · Q38MCQ2 marksMemory Management
Which one of the following statements is FALSE?
GATE 2022 · Q42MCQ2 marksCPU Scheduling
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 · Q63NAT2 marksFile Systems
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 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 nA and nB, respectively, then the value of nA + nB is ______.
GATE 2022 · Q64NAT2 marksVirtual Memory
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 ______.
GATE 2021 Set 1 · Q11MSQ1 markMemory Management
In the context of operating systems, which of the following statements is/are correct with respect to paging?
One or more options may be correct. Select all that apply, then submit.
GATE 2021 Set 1 · Q14MSQ1 markProcesses, Threads & System Calls
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?
One or more options may be correct. Select all that apply, then submit.
GATE 2021 Set 1 · Q15MSQ1 markFile Systems
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 foo. Which of the following operations will necessarily require a full scan of foo for successful completion?
One or more options may be correct. Select all that apply, then submit.
GATE 2021 Set 1 · Q25NAT1 markCPU Scheduling
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 ______ milliseconds.
GATE 2021 Set 1 · Q46MSQ2 marksSynchronization & Concurrency
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.
If five threads execute the function parop concurrently, which of the following program behavior(s) is/are possible?
One or more options may be correct. Select all that apply, then submit.
GATE 2020 · Q11MCQ1 markMemory Management
Consider allocation of memory to a new process. Assume that none of the existing holes in the memory will exactly fit the process's memory requirement. Hence, a new hole of smaller size will be created if allocation is made in any of the existing holes. Which one of the following statements is TRUE?
GATE 2020 · Q12MCQ1 markProcesses, Threads & System Calls
Consider the following statements about process state transitions for a system using preemptive scheduling. I. A running process can move to ready state. II. A ready process can move to running state. III. A blocked process can move to running state. IV. A blocked process can move to ready state. Which of the above statements are TRUE?
Each of a set of n processes executes the following code using two semaphores a and b initialized to 1 and 0, respectively. Assume that count is a shared variable initialized to 0 and not used in CODE SECTION P. CODE SECTION P;
Consider the following five disk access requests of the form (request id, cylinder number) that are present in the disk scheduler queue at a given time. (P, 155), (Q, 85), (R, 110), (S, 30), (T, 115). Assume the head is positioned at cylinder 100. The scheduler follows Shortest Seek Time First scheduling to service the requests. Which one of the following statements is FALSE?
GATE 2020 · Q50NAT2 marksCPU Scheduling
Consider the following set of processes, assumed to have arrived at time 0. Consider the CPU scheduling algorithms Shortest Job First (SJF) and Round Robin (RR). For RR, assume that the processes are scheduled in the order P1, P2, P3, P4. Processes P1, P2, P3, P4 with burst times (in ms) 8, 7, 2, 4. If the time quantum for RR is 4 ms, then the absolute value of the difference between the average turnaround times (in ms) of SJF and RR (round off to 2 decimal places) is ______.
GATE 2020 · Q53NAT2 marksVirtual Memory
Consider a paging system that uses a 1-level page table residing in main memory and a TLB for address translation. Each main memory access takes 100 ns and TLB lookup takes 20 ns. Each page transfer to/from the disk takes 5000 ns. Assume that the TLB hit ratio is 95%, page fault rate is 10%. Assume that for 20% of the total page faults, a dirty page has to be written back to disk before the required page is read in from disk. TLB update time is negligible. The average memory access time in ns (round off to 1 decimal place) is ______.
GATE 2019 Set 2 · Q17NAT1 markProcesses, Threads & System Calls
The following C program is executed on a Unix/Linux system:
#include <unistd.h>
int main() {
int i;
for (i = 0; i < 10; i++) if (i % 2 == 0) fork();
return 0;
}
The total number of child processes created is ______.
GATE 2019 Set 2 · Q23NAT1 markSynchronization & Concurrency
Consider three concurrent processes P1, P2 and P3 as shown below, which access a shared variable D that has been initialized to 100. P1: D = D + 20; P2: D = D − 50; P3: D = D + 10. The processes are executed on a uniprocessor system running a time-shared operating system. If the minimum and maximum possible values of D after the three processes have completed execution are X and Y respectively, then the value of Y − X is ______.
GATE 2019 Set 2 · Q33MCQ2 marksMemory Management
Assume that in a certain computer, the virtual addresses are 64 bits long and the physical addresses are 48 bits long. The memory is word addressable. The page size is 8 kB and the word size is 4 bytes. The Translation Look-aside Buffer (TLB) in the address translation path has 128 valid entries. At most how many distinct virtual addresses can be translated without any TLB miss?
GATE 2019 Set 2 · Q39MCQ2 marksDeadlock
Consider the following snapshot of a system running n concurrent processes. Process i is holding Xi instances of a resource R, 1 ≤ i ≤ n. Assume that all instances of R are currently in use. Further, for all i, process i can place a request for at most Yi additional instances of R while holding the Xi instances it already has. Of the n processes, there are exactly two processes p and q such that Yp = Yq = 0. Which one of the following conditions guarantees that no other process apart from p and q can complete execution?
GATE 2019 Set 2 · Q41NAT2 marksCPU Scheduling
Consider the following four processes with arrival times (in milliseconds) and their length of CPU bursts (in milliseconds) as shown below: P1 (arrival 0, burst 3), P2 (arrival 1, burst 1), P3 (arrival 3, burst 3), P4 (arrival 4, burst Z). These processes are run on a single processor using preemptive Shortest Remaining Time First scheduling algorithm. If the average waiting time of the processes is 1 millisecond, then the value of Z is ______.
GATE 2019 Set 2 · Q42NAT2 marksFile Systems
The index node (inode) of a Unix-like file system has 12 direct, one single-indirect and one double-indirect pointers. The disk block size is 4 kB, and the disk block address is 32-bits long. The maximum possible file size is (rounded off to 1 decimal place) ______ GB.
GATE 2018 · Q9MCQ1 markProcesses, Threads & System Calls
The following are some events that occur after a device controller issues an interrupt while process L is under execution. (P) The processor pushes the process status of L onto the control stack. (Q) The processor finishes the execution of the current instruction. (R) The processor executes the interrupt service routine. (S) The processor pops the process status of L from the control stack. (T) The processor loads the new PC value based on the interrupt. Which one of the following is the correct order in which the events above occur?
GATE 2018 · Q10MCQ1 markVirtual Memory
Consider a process executing on an operating system that uses demand paging. The average time for a memory access in the system is M units if the corresponding memory page is available in memory, and D units if the memory access causes a page fault. It has been experimentally measured that the average time taken for a memory access in the process is X units. Which one of the following is the correct expression for the page fault rate experienced by the process?
GATE 2018 · Q24NAT1 markDeadlock
Consider a system with 3 processes that share 4 instances of the same resource type. Each process can request a maximum of K instances. Resource instances can be requested and released only one at a time. The largest value of K that will always avoid deadlock is ______.
GATE 2018 · Q39MCQ2 marksDeadlock
In a system, there are three types of resources: E, F and G. Four processes P0, P1, P2 and P3 execute concurrently. At the outset, the processes have declared their maximum resource requirements using a matrix named Max. The number of instances of the resources allocated to the various processes is given by a matrix named Allocation. Allocation (E F G): P0 1 0 1, P1 1 1 2, P2 1 0 3, P3 2 0 0. Max (E F G): P0 4 3 1, P1 2 1 4, P2 1 3 3, P3 5 4 1. Consider the state with the Allocation matrix above in which 3 instances of E and 3 instances of F are the only resources available (no G is available). From the perspective of deadlock avoidance, which one of the following is true?
Consider the following solution to the producer-consumer synchronization problem. The shared buffer size is N. Three semaphores empty, full and mutex are defined with respective initial values of 0, N and 1. Semaphore empty denotes the number of available slots in the buffer, for the consumer to read from. Semaphore full denotes the number of available slots in the buffer, for the producer to write to. The placeholder variables, denoted by P, Q, R, and S, in the code below can be assigned either empty or full. The valid semaphore operations are: wait() and signal(). Producer:
do {
wait(P);
wait(mutex);
/* add item to buffer */ signal(mutex);
signal(Q);
} while (1);
Consumer:
do {
wait(R);
wait(mutex);
/* consume item from buffer */ signal(mutex);
signal(S);
} while (1);
Which one of the following assignments to P, Q, R and S will yield the correct solution?
GATE 2018 · Q53NAT2 marksDisk Scheduling & I/O
Consider a storage disk with 4 platters (numbered as 0, 1, 2 and 3), 200 cylinders (numbered as 0, 1, ..., 199), and 256 sectors per track (numbered as 0, 1, ..., 255). The following 6 disk requests of the form [sector number, cylinder number, platter number] are received by the disk controller at the same time: [120, 72, 2], [180, 134, 1], [60, 20, 0], [212, 86, 3], [56, 116, 2], [118, 16, 1]. Currently the head is positioned at sector number 100 of cylinder 80, and is moving towards higher cylinder numbers. The average power dissipation in moving the head over 100 cylinders is 20 milliwatts and for reversing the direction of the head movement once is 15 milliwatts. Power dissipation associated with rotational latency and switching of head between different platters is negligible. The total power consumption in milliwatts to satisfy all of the above disk requests using the Shortest Seek Time First disk scheduling algorithm is ______.
GATE 2017 Set 1 · Q18MCQ1 markProcesses, Threads & System Calls
Threads of a process share
GATE 2017 Set 1 · Q24NAT1 markCPU Scheduling
Consider the following CPU processes with arrival times (in milliseconds) and length of CPU bursts (in milliseconds) as given below: P1 (arrival 0, burst 7), P2 (3, 3), P3 (5, 5), P4 (6, 2). If the pre-emptive shortest remaining time first scheduling algorithm is used to schedule the processes, then the average waiting time across all processes is ______ milliseconds.
GATE 2017 Set 1 · Q27MCQ2 marksDeadlock
A multithreaded program P executes with x number of threads and uses y number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are non-reentrant, i.e., if a thread holds a lock l, then it cannot re-acquire lock l without releasing it. If a thread is unable to acquire a lock, it blocks until the lock becomes available. The minimum value of x and the minimum value of y together for which execution of P can result in a deadlock are:
GATE 2017 Set 1 · Q40MCQ2 marksVirtual Memory
Recall that Belady's anomaly is that the page-fault rate may increase as the number of allocated frames increases. Now, consider the following statements: S1: Random page replacement algorithm (where a page chosen at random is replaced) suffers from Belady's anomaly. S2: LRU page replacement algorithm suffers from Belady's anomaly. Which of the following is CORRECT?
GATE 2016 Set 1 · Q20MCQ1 markCPU Scheduling
Consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time to a computer system. Which one of the following process scheduling algorithms would minimize the average waiting time in the ready queue?
GATE 2016 Set 1 · Q31NAT2 marksDisk Scheduling & I/O
The size of the data count register of a DMA controller is 16 bits. The processor needs to transfer a file of 29,154 kilobytes from disk to main memory. The memory is byte addressable. The minimum number of times the DMA controller needs to get the control of the system bus from the processor to transfer the file from the disk to main memory is ______.
GATE 2016 Set 1 · Q47NAT2 marksMemory Management
Consider a computer system with 40-bit virtual addressing and page size of sixteen kilobytes. If the computer system has a one-level page table per process and each page table entry requires 48 bits, then the size of the per-process page table is ______ megabytes.
GATE 2016 Set 1 · Q48NAT2 marksDisk Scheduling & I/O
Consider a disk queue with requests for I/O to blocks on cylinders 47, 38, 121, 191, 87, 11, 92, 10. The C-LOOK scheduling algorithm is used. The head is initially at cylinder number 63, moving towards larger cylinder numbers on its servicing pass. The cylinders are numbered from 0 to 199. The total head movement (in number of cylinders) incurred while servicing these requests is ______.
GATE 2016 Set 1 · Q49NAT2 marksVirtual Memory
Consider a computer system with ten physical page frames. The system is provided with an access sequence (a1, a2, ..., a20, a1, a2, ..., a20), where each ai is a distinct virtual page number. The difference in the number of page faults between the last-in-first-out page replacement policy and the optimal page replacement policy is ______.
GATE 2016 Set 1 · Q50MCQ2 marksDeadlock
Consider the following proposed solution for the critical section problem. There are n processes: P0 ... Pn−1. In the code, function pmax returns an integer not smaller than any of its arguments. For all i, t[i] is initialized to zero. Code for Pi:
do {
c[i] = 1;
t[i] = pmax(t[0], ..., t[n−1]) + 1;
c[i] = 0;
for every j ≠ i in {0, ..., n−1} {
while (c[j]);
while (t[j] != 0 && t[j] <= t[i]);
}
Critical Section;
t[i] = 0;
Remainder Section;
} while (true);
Which one of the following is TRUE about the above solution?
GATE 2014 Set 1 · Q19NAT1 markDisk Scheduling & I/O
Suppose a disk has 201 cylinders, numbered from 0 to 200. At some time the disk arm is at cylinder 100, and there is a queue of disk access requests for cylinders 30, 85, 90, 100, 105, 110, 135 and 145. If Shortest-Seek Time First (SSTF) is being used for scheduling the disk access, the request for cylinder 90 is serviced after servicing ______ number of requests.
GATE 2014 Set 1 · Q20MCQ1 markProcesses, Threads & System Calls
Which one of the following is FALSE?
GATE 2014 Set 1 · Q31MCQ2 marksDeadlock
An operating system uses the Banker's algorithm for deadlock avoidance when managing the allocation of three resource types X, Y, and Z to three processes P0, P1, and P2. The table given below presents the current system state. Allocation (X Y Z): P0 0 0 1, P1 3 2 0, P2 2 1 1. Max (X Y Z): P0 8 4 3, P1 6 2 0, P2 3 3 3. There are 3 units of type X, 2 units of type Y and 2 units of type Z still available. The system is currently in a safe state. Consider the following independent requests for additional resources in the current state: REQ1: P0 requests 0 units of X, 0 units of Y and 2 units of Z. REQ2: P1 requests 2 units of X, 0 units of Y and 0 units of Z. Which one of the following is TRUE?
GATE 2014 Set 1 · Q32NAT2 marksCPU Scheduling
Consider the following set of processes that need to be scheduled on a single CPU. All the times are given in milliseconds. A (arrival 0, execution 6), B (3, 2), C (5, 4), D (7, 6), E (10, 3). Using the shortest remaining time first scheduling algorithm, the average process turnaround time (in msec) is ______.
GATE 2014 Set 1 · Q33NAT2 marksVirtual Memory
Assume that there are 3 page frames which are initially empty. If the page reference string is 1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6, the number of page faults using the optimal replacement policy is ______.
GATE 2013 Code A · Q10MCQ1 markCPU Scheduling
A scheduling algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero (the lowest priority). The scheduler re-evaluates the process priorities every T time units and decides the next process to schedule. Which one of the following is TRUE if the processes have no I/O operations and all arrive at time zero?
GATE 2013 Code A · Q16MCQ1 markDeadlock
Three concurrent processes X, Y, and Z execute three different code segments that access and update certain shared variables. Process X executes the P operation (i.e., wait) on semaphores a, b and c; process Y executes the P operation on semaphores b, c and d; process Z executes the P operation on semaphores c, d, and a before entering the respective code segments. After completing the execution of its code segment, each process invokes the V operation (i.e., signal) on its three semaphores. All semaphores are binary semaphores initialized to one. Which one of the following represents a deadlock-free order of invoking the P operations by the processes?
GATE 2013 Code A · Q29MCQ2 marksDisk Scheduling & I/O
Consider a hard disk with 16 recording surfaces (0-15) having 16384 cylinders (0-16383) and each cylinder contains 64 sectors (0-63). Data storage capacity in each sector is 512 bytes. Data are organized cylinder-wise and the addressing format is <cylinder no., surface no., sector no.>. A file of size 42797 KB is stored in the disk and the starting disk location of the file is <1200, 9, 40>. What is the cylinder number of the last sector of the file, if it is stored in a contiguous manner?
GATE 2013 Code A · Q34MCQ2 marksSynchronization & Concurrency
A shared variable x, initialized to zero, is operated on by four concurrent processes W, X, Y, Z as follows. Each of the processes W and X reads x from memory, increments by one, stores it to memory, and then terminates. Each of the processes Y and Z reads x from memory, decrements by two, stores it to memory, and then terminates. Each process before reading x invokes the P operation (i.e., wait) on a counting semaphore S and invokes the V operation (i.e., signal) on the semaphore S after storing x to memory. Semaphore S is initialized to two. What is the maximum possible value of x after all processes complete execution?
GATE 2012 Code A · Q8MCQ1 markProcesses, Threads & System Calls
A process executes the code
fork();
fork();
fork();
The total number of child processes created is
GATE 2012 Code A · Q31MCQ2 marksCPU Scheduling
Consider the 3 processes, P1, P2 and P3 shown in the table: P1 (arrival 0, 5 time units), P2 (arrival 1, 7 units), P3 (arrival 3, 4 units). The completion order of the 3 processes under the policies FCFS and RR2 (round robin scheduling with CPU quantum of 2 time units) are
GATE 2012 Code A · Q32MCQ2 marksSynchronization & Concurrency
Fetch_And_Add(X, i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.
AcquireLock(L) {
while (Fetch_And_Add(L, 1)) L = 1;
}
ReleaseLock(L) {
L = 0;
}
This implementation
GATE 2012 Code A · Q41MCQ2 marksFile Systems
A file system with 300 GByte disk uses a file descriptor with 8 direct block addresses, 1 indirect block address and 1 doubly indirect block address. The size of each disk block is 128 Bytes and the size of each disk block address is 8 Bytes. The maximum possible file size in this file system is
GATE 2012 Code A · Q42MCQ2 marksVirtual Memory
Consider the virtual page reference string 1, 2, 3, 2, 4, 1, 3, 2, 4, 1 on a demand paged virtual memory system running on a computer system that has main memory size of 3 page frames which are initially empty. Let LRU, FIFO and OPTIMAL denote the number of page faults under the corresponding page replacement policy. Then