Following questions have been asked in GATE 2009 CS exam.

1) In the following process state transition diagram for a uniprocessor system, assume that there are always some processes in the ready state: Now consider the following statements:

I. If a process makes a transition D, it would result in another process making transition A immediately.
II. A process P2 in blocked state can make transition E while another process P1 is in running state.
III. The OS uses preemptive scheduling.
IV. The OS uses non-preemptive scheduling.
Which of the above statements are TRUE?

(A) I and II
(B) I and III
(C) II and III
(D) II and IV

Answer (C)
I is false. If a process makes a transition D, it would result in another process making transition B, not A.
II is true. A process can move to ready state when I/O completes irrespective of other process being in running state or not.
III is true because there is a transition from running to ready state.
IV is false as the OS uses preemptive scheduling.

2) The enter_CS() and leave_CS() functions to implement critical section of a process are realized using test-and-set instruction as follows:

void enter_CS(X)
    while test-and-set(X) ;
void leave_CS(X)
   X = 0;

In the above solution, X is a memory location associated with the CS and is initialized to 0. Now consider the following statements:
I. The above solution to CS problem is deadlock-free
II. The solution is starvation free.
III. The processes enter CS in FIFO order.
IV More than one process can enter CS at the same time.

Which of the above statements is TRUE?
(A) I only
(B) I and II
(C) II and III
(D) IV only

Answer (A)
The above solution is a simple test-and-set solution that makes sure that deadlock doesn’t occur, but it doesn’t use any queue to avoid starvation or to have FIFO order.

3) A multilevel page table is preferred in comparison to a single level page table for translating virtual address to physical address because
(A) It reduces the memory access time to read or write a memory location.
(B) It helps to reduce the size of page table needed to implement the virtual address space of a process.
(C) It is required by the translation lookaside buffer.
(D) It helps to reduce the number of page faults in page replacement algorithms.

Answer (B)
The size of page table may become too big (See this) to fit in contiguous space. That is why page tables are typically divided in levels.


Following questions have been asked in GATE 2009 CS exam.

1) In which one of the following page replacement policies, Belady’s anomaly may occur?
(B) Optimal

Answer (A)
Belady’s anomaly proves that it is possible to have more page faults when increasing the number of page frames while using the First in First Out (FIFO) page replacement algorithm.
See the wiki page for an example of increasing page faults with number of page frames.

2) The essential content(s) in each entry of a page table is / are
(A) Virtual page number
(B) Page frame number
(C) Both virtual page number and page frame number
(D) Access right information

Answer (B)
A page table entry must contain Page frame number. Virtual page number is typically used as index in page table to get the corresponding page frame number. See this for details.

3) Consider a system with 4 types of resources R1 (3 units), R2 (2 units), R3 (3 units), R4 (2 units). A non-preemptive resource allocation policy is used. At any given instance, a request is not entertained if it cannot be completely satisfied. Three processes P1, P2, P3 request the sources as follows if executed independently.

Process P1: 
t=0: requests 2 units of R2 
t=1: requests 1 unit of R3 
t=3: requests 2 units of R1 
t=5: releases 1 unit of R2    
        and 1 unit of R1. 
t=7: releases 1 unit of R3 
t=8: requests 2 units of R4 
t=10: Finishes

Process P2: 
t=0: requests 2 units of R3 
t=2: requests 1 unit of R4 
t=4: requests 1 unit of R1 
t=6: releases 1 unit of R3 
t=8: Finishes

Process P3: 
t=0: requests 1 unit of R4 
t=2: requests 2 units of R1 
t=5: releases 2 units of R1 
t=7: requests 1 unit of R2 
t=8: requests 1 unit of R3 
t=9: Finishes

Which one of the following statements is TRUE if all three processes run concurrently starting at time t=0?
(A) All processes will finish without any deadlock
(B) Only P1 and P2 will be in deadlock.
(C) Only P1 and P3 will be in a deadlock.
(D) All three processes will be in deadlock

Answer (A)
We can apply the following Deadlock Detection algorithm and see that there is no process waiting indefinitely for a resource. See this for deadlock detection algorithm.

4) Consider a disk system with 100 cylinders. The requests to access the cylinders occur in following sequence:
4, 34, 10, 7, 19, 73, 2, 15, 6, 20
Assuming that the head is currently at cylinder 50, what is the time taken to satisfy all requests if it takes 1ms to move from one cylinder to adjacent one and shortest seek time first policy is used?

(A) 95ms
(B) 119ms
(C) 233ms
(D) 276ms

Answer (B)
4, 34, 10, 7, 19, 73, 2, 15, 6, 20
Since shortest seek time first policy is used, head will first move to 34. This move will cause 16*1 ms. After 34, head will move to 20 which will cause 14*1 ms. And so on. So cylinders are accessed in following order 34, 20, 19, 15, 10, 7, 6, 4, 2, 73 and total time will be (16 + 14 + 1 + 4 + 5 + 3 + 1 + 2 + 2 + 71)*1 = 119 ms.


Following questions have been asked in GATE CS exam.

1) Let the time taken to switch between user and kernel modes of execution be t1 while the time taken to switch between two processes be t2. Which of the following is TRUE? (GATE CS 2011)

(A) t1 > t2
(B) t1 = t2
(C) t1 < t2 (D) Nothing can be said about the relation between t1 and t2 Answer: – (C) Process switching involves mode switch. Context switching can occur only in kernel mode.

2) A system uses FIFO policy for page replacement. It has 4 page frames with no pages loaded to begin with. The system first accesses 100 distinct pages in some order and then accesses the same 100 pages but now in the reverse order. How many page faults will occur? (GATE CS 2010)

(A) 196
(B) 192
(C) 197
(D) 195

Answer (A)
Access to 100 pages will cause 100 page faults. When these pages are accessed in reverse order, the first four accesses will not cause page fault. All other access to pages will cause page faults. So total number of page faults will be 100 + 96.

3) Which of the following statements are true? (GATE CS 2010)
I. Shortest remaining time first scheduling may cause starvation
II. Preemptive scheduling may cause starvation
III. Round robin is better than FCFS in terms of response time

(A) I only
(B) I and III only
(C) II and III only
(D) I, II and III

Answer (D)

I) Shortest remaining time first scheduling is a preemptive version of shortest job scheduling. It may cause starvation as shorter processes may keep coming and a long CPU burst process never gets CPU.
II) Preemption may cause starvation. If priority based scheduling with preemption is used, then a low priority process may never get CPU.
III) Round Robin Scheduling improves response time as all processes get CPU after a specified time.

4) Consider the methods used by processes P1 and P2 for accessing their critical sections whenever needed, as given below. The initial values of shared boolean variables S1 and S2 are randomly assigned.

Method Used by P1
while (S1 == S2) ;
Critica1 Section
S1 = S2;

Method Used by P2
while (S1 != S2) ;
Critica1 Section
S2 = not (S1);

Which one of the following statements describes the properties achieved? (GATE CS 2010)
(A) Mutual exclusion but not progress
(B) Progress but not mutual exclusion
(C) Neither mutual exclusion nor progress
(D) Both mutual exclusion and progress

Answer (A)
It can be easily observed that the Mutual Exclusion requirement is satisfied by the above solution, P1 can enter critical section only if S1 is not equal to S2, and P2 can enter critical section only if S1 is equal to S2.
Progress Requirement is not satisfied. Let us first see definition of Progress Requirement.
Progress Requirement: If no process is executing in its critical section and there exist some processes that wishes to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely.
If P1 or P2 want to re-enter the critical section, then they cannot even if there is other process running in critical section.


Following questions have been asked in GATE 2011 CS exam.

1) A thread is usually defined as a ‘light weight process’ because an operating system (OS) maintains smaller data structures for a thread than for a process. In relation to this, which of the followings is TRUE?
(A) On per-thread basis, the OS maintains only CPU register state
(B) The OS does not maintain a separate stack for each thread
(C) On per-thread basis, the OS does not maintain virtual memory state
(D) On per thread basis, the OS maintains only scheduling and accounting information.

Answer (C)
Threads share address space of Process. Virtually memory is concerned with processes not with Threads.

2) Let the page fault service time be 10ms in a computer with average memory access time being 20ns. If one page fault is generated for every 10^6 memory accesses, what is the effective access time for the memory?
(A) 21ns
(B) 30ns
(C) 23ns
(D) 35ns

Answer (B)

Let P be the page fault rate
Effective Memory Access Time = p * (page fault service time) + 
                               (1 - p) * (Memory access time)
                             = ( 1/(10^6) )* 10 * (10^6) ns +
                               (1 - 1/(10^6)) * 20 ns
                             = 30 ns (approx)    

3) An application loads 100 libraries at startup. Loading each library requires exactly one disk access. The seek time of the disk to a random location is given as 10ms. Rotational speed of disk is 6000rpm. If all 100 libraries are loaded from random locations on the disk, how long does it take to load all libraries? (The time to transfer data from the disk block once the head has been positioned at the start of the block may be neglected)
(A) 0.50s
(B) 1.50s
(C) 1.25s
(D) 1.00s

Answer (B)
Since transfer time can be neglected, the average access time is sum of average seek time and average rotational latency. Average seek time for a random location time is given as 10 ms. The average rotational latency is half of the time needed for complete rotation. It is given that 6000 rotations need 1 minute. So one rotation will take 60/6000 seconds which is 10 ms. Therefore average rotational latency is half of 10 ms, which is 5ms.

Average disk access time = seek time + rotational latency 
                         = 10 ms + 5 ms 
                         = 15 ms
For 100 libraries, the average disk access time will be 15*100 ms

4. Consider the following table of arrival time and burst time for three processes P0, P1 and P2.

Process   Arrival time   Burst Time
P0            0 ms          9 ms
P1            1 ms          4 ms
P2            2 ms          9 ms

The pre-emptive shortest job first scheduling algorithm is used. Scheduling is carried out only at arrival or completion of processes. What is the average waiting time for the three processes?
(A) 5.0 ms
(B) 4.33 ms
(C) 6.33 ms
(D) 7.33 ms

Answer: – (A)
Process P0 is allocated processor at 0 ms as there is no other process in ready queue. P0 is preempted after 1 ms as P1 arrives at 1 ms and burst time for P1 is less than remaining time of P0. P1 runs for 4ms. P2 arrived at 2 ms but P1 continued as burst time of P2 is longer than P1. After P1 completes, P0 is scheduled again as the remaining time for P0 is less than the burst time of P2.
P0 waits for 4 ms, P1 waits for 0 ms amd P2 waits for 11 ms. So average waiting time is (0+4+11)/3 = 5.


Following questions have been asked in GATE 2012 exam.

1. A process executes the code

  fork ();
  fork ();
  fork ();

The total number of child processes created is
(A) 3
(B) 4
(C) 7
(D) 8

Answer (C)

Let us put some label names for the three lines

  fork ();    // Line 1
  fork ();   // Line 2
  fork ();   // Line 3

       L1       // There will be 1 child process created by line 1
    /     \
  L2      L2    // There will be 2 child processes created by line 2
 /  \    /  \
L3  L3  L3  L3  // There will be 4 child processes created by line 3

We can also use direct formula to get the number of child processes. With n fork statements, there are always 2^n – 1 child processes. Also see this post for more details.

2. consider the 3 processes, P1, P2 and P3 shown in the table

Process     Arrival time    Time unit required
  P1                0                    5
  P2                1                    7
  P3                3                    4

The completion order of the 3 processes under the policies FCFS and RRS (round robin scheduling with CPU quantum of 2 time units) are
(A) FCFS: P1, P2, P3 RR2: P1, P2, P3
(B) FCFS: P1, P3, P2 RR2: P1, P3, P2
(C) FCFS: P1, P2, P3 RR2: P1, P3, P2
(D) FCFS: P1, P3, P2 RR2: P1, P2, P3

Answer (C)

3. 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 main memory size of 3 pages frames which are initially empty. Let LRU, FIFO and OPTIMAL denote the number of page faults under the corresponding page replacements policy. Then


4. A file system with 300 GByte uses a file descriptor with 8 direct block address. 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
(A) 3 Kbytes
(B) 35 Kbytes
(C) 280 Bytes
(D) Dependent on the size of the disk

Answer (B)

Total number of possible addresses stored in a disk block = 128/8 = 16

Maximum number of addressable bytes due to direct address block = 8*128
Maximum number of addressable bytes due to 1 single indirect address block = 16*128
Maximum number of addressable bytes due to 1 double indirect address block = 16*16*128

The maximum possible file size = 8*128 + 16*128 + 16*16*128 = 35KB


Following questions have been asked in GATE CS exam.

1. Using a larger block size in a fixed block size file system leads to (GATE CS 2003)
a) better disk throughput but poorer disk space utilization
b) better disk throughput and better disk space utilization
c) poorer disk throughput but better disk space utilization
d) poorer disk throughput and poorer disk space utilization

Answer (a)
If block size is large then seek time is less (fewer blocks to seek) and disk performance is improved, but remember larger block size also causes waste of disk space.

2. Consider the following statements with respect to user-level threads and kernel supported threads
i. context switch is faster with kernel-supported threads
ii. for user-level threads, a system call can block the entire process
iii. Kernel supported threads can be scheduled independently
iv. User level threads are transparent to the kernel

Which of the above statements are true? (GATE CS 2004)
a) (ii), (iii) and (iv) only
b) (ii) and (iii) only
c) (i) and (iii) only
d) (i) and (ii) only



3. The minimum number of page frames that must be allocated to a running process in a virtual memory environment is determined by (GATE CS 2004)

a) the instruction set architecture
b) page size
c) physical memory size
d) number of processes in memory

Answer (a)
Each process needs minimum number of pages based on instruction set architecture. Example IBM 370: 6 pages to handle MVC (storage to storage move) instruction
Instruction is 6 bytes, might span 2 pages.
2 pages to handle from.
2 pages to handle to.

4. In a system with 32 bit virtual addresses and 1 KB page size, use of one-level page tables for virtual to physical address translation is not practical because of (GATE CS 2003)
a) the large amount of internal fragmentation
b) the large amount of external fragmentation
c) the large memory overhead in maintaining page tables
d) the large computation overhead in the translation process

Answer (c)
Since page size is too small it will make size of page tables huge.

Size of page table =
  (total number of page table entries) *(size of a page table entry)

Let us see how many entries are there in page table

Number of entries in page table =
                    (virtual address space size)/(page size)
                    = (2^32)/(2^10) 
                    = 2^22

Now, let us see how big each entry is.

If size of physical memory is 512 MB then number of bits required to address a byte in 512 MB is 29. So, there will be (512MB)/(1KB) = (2^29)/(2^10) page frames in physical memory. To address a page frame 19 bits are required. Therefore, each entry in page table is required to have 19 bits.

Note that page table entry also holds auxiliary information about the page such 
as a present bit, a dirty or modified bit, address space or process ID information, 
amongst others. So size of page table 
    > (total number of page table entries) *(size of a page table entry)
    > (2^22 *19) bytes
    > 9.5 MB

And this much memory is required for each process because each process maintains its own page table. Also, size of page table will be more for physical memory more than 512MB. Therefore, it is advised to use multilevel page table for such scenarios.



Following questions have been asked in GATE CS exam.

1. Suppose the time to service a page fault is on the average 10 milliseconds, while a memory access takes 1 microsecond. Then a 99.99% hit ratio results in average memory access time of (GATE CS 2000)
(a) 1.9999 milliseconds
(b) 1 millisecond
(c) 9.999 microseconds
(d) 1.9999 microseconds

Answer: (d)

Average memory access time =
      [(% of page miss)*(time to service a page fault) +
                  (% of page hit)*(memory access time)]/100

So, average memory access time in microseconds is.
(99.99*1 + 0.01*10*1000)/100 = (99.99+100)/1000 = 199.99/1000 =1.9999 µs

2. Which of the following need not necessarily be saved on a context switch between processes? (GATE CS 2000)

(a) General purpose registers
(b) Translation look-aside buffer
(c) Program counter
(d) All of the above

Answer: (b)
In a process context switch, the state of the first process must be saved somehow, so that, when the scheduler gets back to the execution of the first process, it can restore this state and continue.

The state of the process includes all the registers that the process may be using, especially the program counter, plus any other operating system specific data that may be necessary.

A Translation lookaside buffer (TLB) is a CPU cache that memory management hardware uses to improve virtual address translation speed. A TLB has a fixed number of slots that contain page table entries, which map virtual addresses to physical addresses. On a context switch, some TLB entries can become invalid, since the virtual-to-physical mapping is different. The simplest strategy to deal with this is to completely flush the TLB.

3. Where does the swap space reside ? (GATE 2001)

(a) RAM
(b) Disk
(c) ROM
(d) On-chip cache
Answer: (b)
Swap space is an area on disk that temporarily holds a process memory image. When physical memory demand is sufficiently low, process memory images are brought back into physical memory from the swap area. Having sufficient swap space enables the system to keep some physical memory free at all times.

4. Which of the following does not interrupt a running process?
(GATE CS 2001)
(a) A device
(b) Timer
(c) Scheduler process
(d) Power failure

Answer: (c)
Scheduler process doesn’t interrupt any process, it’s Job is to select the processes for following three purposes.
Long-term scheduler(or job scheduler) –selects which processes should be brought into the ready queue
Short-term scheduler(or CPU scheduler) –selects which process should be executed next and allocates CPU.
Mid-term Scheduler (Swapper)- present in all systems with virtual memory, temporarily removes processes from main memory and places them on secondary memory (such as a disk drive) or vice versa. The mid-term scheduler may decide to swap out a process which has not been active for some time, or a process which has a low priority, or a process which is page faulting frequently, or a process which is taking up a large amount of memory in order to free up main memory for other processes, swapping the process back in later when more memory is available, or when the process has been unblocked and is no longer waiting for a resource.

5. Which of the following scheduling algorithms is non-preemptive? (GATE CS 2002)

a) Round Robin
b) First-In First-Out
c) Multilevel Queue Scheduling
d) Multilevel Queue Scheduling with Feedback

Answer: (b)



Following questions have been asked in GATE CS exam.

1. Consider a machine with 64 MB physical memory and a 32-bit virtual address space. If the page size is 4KB, what is the approximate size of the page table? (GATE 2001)
(a) 16 MB
(b) 8 MB
(c) 2 MB
(d) 24 MB

Answer: (c)
A page entry is used to get address of physical memory. Here we assume that single level of Paging is happening. So the resulting page table will contain entries for all the pages of the Virtual address space.

Number of entries in page table = 
                    (virtual address space size)/(page size)  

Using above formula we can say that there will be 2^(32-12) = 2^20 entries in page table.
No. of bits required to address the 64MB Physical memory = 26.
So there will be 2^(26-12) = 2^14 page frames in the physical memory. And page table needs to store the address of all these 2^14 page frames. Therefore, each page table entry will contain 14 bits address of the page frame and 1 bit for valid-invalid bit.
Since memory is byte addressable. So we take that each page table entry is 16 bits i.e. 2 bytes long.

Size of page table = 
  (total number of page table entries) *(size of a page table entry) 
   = (2^20 *2) = 2MB

For the clarity of the concept, please see the following figure. As per our question, here p = 20, d = 12 and f = 14.


2. Consider Peterson’s algorithm for mutual exclusion between two concurrent processes i and j. The program executed by process is shown below.

      flag [i] = true; 
      turn = j; 
      while ( P ) do no-op; 
      Enter critical section, perform actions, then exit critical 
      flag [ i ] = false; 
      Perform other non-critical section actions. 
   until false; 

For the program to guarantee mutual exclusion, the predicate P in the while loop should be (GATE 2001)
a) flag [j] = true and turn = i
b) flag [j] = true and turn = j
c) flag [i] = true and turn = j
d) flag [i] = true and turn = i

Answer: (b)
Basically, Peterson’s algorithm provides guaranteed mutual exclusion by using the two following constructs –flag[] and turn. flag[] controls that the willingness of a process to be entered in critical section. While turn controls the process that is allowed to be entered in critical section. So by replacing P with the following,

flag [j] = true and turn = j

process i will not enter critical section if process j wants to enter critical section and it is process j’s turn to enter critical section. The same concept can be extended for more than two processes. For details, refer the following.

3 More than one word are put in one cache block to (GATE 2001)

(a) exploit the temporal locality of reference in a program
(b) exploit the spatial locality of reference in a program
(c) reduce the miss penalty
(d) none of the above

Answer: (b)
Temporal locality refers to the reuse of specific data and/or resources within relatively small time durations. Spatial locality refers to the use of data elements within relatively close storage locations.
To exploit the spatial locality, more than one word are put into cache block.

4. Which of the following statements is false? (GATE 2001)

a) Virtual memory implements the translation of a program’s address space into physical memory address space
b) Virtual memory allows each program to exceed the size of the primary memory
c) Virtual memory increases the degree of multiprogramming
d) Virtual memory reduces the context switching overhead

Answer: (d)
In a system with virtual memory context switch includes extra overhead in switching of address spaces.

5. Consider a set of n tasks with known runtimes r1, r2, … rn to be run on a uniprocessor machine. Which of the following processor scheduling algorithms will result in the maximum throughput? (GATE 2001)

(a) Round-Robin
(b) Shortest-Job-First
(c) Highest-Response-Ratio-Next
(d) First-Come-First-Served

Answer: (b)



Following questions have been asked in GATE CS exam.

1. Which of the following is NOT a valid deadlock prevention scheme? (GATE CS 2000)
(a) Release all resources before requesting a new resource
(b) Number the resources uniquely and never request a lower numbered resource than the last one requested.
(c) Never request a resource after releasing any resource
(d) Request and all required resources be allocated before execution.

Answer: (c)

2. Let m[0]…m[4] be mutexes (binary semaphores) and P[0] …. P[4] be processes.
Suppose each process P[i] executes the following:

  wait (m[i]); wait(m[(i+1) mode 4]);


  release (m[i]); release (m[(i+1)mod 4]);

This could cause (GATE CS 2000)
(a) Thrashing
(b) Deadlock
(c) Starvation, but not deadlock
(d) None of the above

Answer: (b)

You can easily see a deadlock in a situation where..
P[0] has acquired m[0] and waiting for m[1]
P[1] has acquired m[1] and waiting for m[2]
P[2] has acquired m[2] and waiting for m[3]
P[3] has acquired m[3] and waiting for m[0]

3. A graphics card has on board memory of 1 MB. Which of the following modes can the
card not support? (GATE CS 2000)

(a) 1600 x 400 resolution with 256 colours on a 17 inch monitor
(b) 1600 x 400 resolution with 16 million colours on a 14 inch monitor
(c) 800 x 400 resolution with 16 million colours on a 17 inch monitor
(d) 800 x 800 resolution with 256 colours on a 14 inch monitor

Monitor size doesn’t matter here. So, we can easily deduct that answer should be (b) as this has the highest memory requirements. Let us verify it.
Number of bits required to store a 16M colors pixel = ceil(log2(16*1000000)) = 24
Number of bytes required for 1600 x 400 resolution with 16M colors = (1600 * 400 * 24)/8 which is 192000000 (greater than 1MB).

4 Consider a virtual memory system with FIFO page replacement policy. For an arbitrary page access pattern, increasing the number of page frames in main memory will (GATE CS 2001)

a) Always decrease the number of page faults
b) Always increase the number of page faults
c) Some times increase the number of page faults
d) Never affect the number of page faults

Answer: (c)
Incrementing the number of page frames doesn’t always decrease the page faults (Belady’s Anomaly). For details see http://en.wikipedia.org/wiki/Belady%27s_anomaly

5. Which of the following requires a device driver? (GATE CS 2001)

a) Register
b) Cache
c) Main memory
d) Disk

Answer: (d)