With experience and correct observation, one can analyze the paper pattern of GATE. After qualifying this exam 6 times, I can enlist the most frequently asked questions here:
1. Questions on Process-State Diagram
In this type of questions, they give you the process state diagram such as:
Now, they can ask you whether this diagram represents a pre-emptive scheduling policy or a non-preemptive one. Or some questions can be asked about the transitions. All you need to know about this state diagram is:
- Whenever you see a transition from Running state to Ready state, you can say that this scheduling is pre-emptive. (As simple as that)
- There can be multiple processes residing in Ready and Blocked state.
- There can be only one process in Running state at a time.
- Long term scheduler is responsible for bringing the processes from Start to ready state.
- Short term scheduler is responsible for selecting one process from Ready state to assign it the processor, i.e. Running state.
- Mid term scheduler is used for taking the processes from Ready state to Suspended Ready state and from Blocked state to Suspended Blocked state.
2. Questions on fork() system call
This is the simplest type of questions asked in GATE. In this they give you the number of fork() system calls, and you have to tell the number of child processes created.
Que.
for( i=0; i<n; i++)
fork();
The total number of child processes created is:
(a) n (b) 2n-1
(c) 2n (d) 2n+1-1
As we know, for every fork() system call, there are 2 processes created (1 parent and 1 child). So, for n fork() system calls, there will be 2n-1 child processes and remaining 1 will be the parent process.
The only thing to take care of is to see whether they are asking the total number of processes (2n) or the total number of child processes (2n-1).
3. Questions on CPU scheduling:
This is the most frequent type of questions. In this you are given a set of processes with their arrival times, burst times and priority (may be), and you need to calculate the average waiting time according to the given scheduling policy.
Que: 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?
All you need to know about scheduling algorithms:
4. Questions on context-switch
Let the time taken by context switch in case of threads is t1 and time taken by context switch in case of processes is t2. Which of the following is true?
(a) t1<t2
(b) t2>t1
(c) t1=t2
(d) None of these
The only thing you need to know here is that the processes will have more context than threads. So it will take longer to switch context in case of processes. So, option (a) is correct.
5. Questions on Semaphores
Semaphores have only two operations: P (Wait) operation and V (Signal) operation.
For every P operation, 1 is deducted from the semaphore value.
For every V operation, 1 is added in the semaphore value.
Que: Initial value of a counting semaphore is 10. After 6 P operations and 4 V operations, what will be the value of the semaphore?
(a) 0 (b) 8
(c) 10 (d) 12
As the initial value is 10, after 6 P operations it will be 10-6=4, after 4 V operations it will be 4+4=8.
6. Questions on Process Synchronization
Que: 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
|
Method Used by P2
|
while (S1 == S2) ;
Critica1 Section
S1 = S2;
|
while (S1 != S2) ;
Critica1 Section
S2 = not (S1);
|
Which one of the following statements describes the properties achieved?
(a) Mutual exclusion but not progress
(b) Progress but not mutual exclusion
(c) Neither mutual exclusion nor progress
(d) Both mutual exclusion and progress
Principle of Mutual Exclusion: No two processes may be simultaneously present in the critical section at the same time. That is, if one process is present in the critical section other should not be allowed.
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. Therefore Mutual Exclusion is satisfied.
Progress: no process running outside the critical section should block the other interested process from entering critical section whenever critical section is free.
Suppose P1 after executing critical section again want to execute the critical section and P2 don’t want to enter the critical section, then in that case P1 has to unnecessarily wait for P2. Hence progress is not satisfied.
7. Questions on Deadlock Prevention
In this type of questions, you are given a number of resources and a number of processes and resource requirements of these processes. You are asked the maximum number of processes or minimum number of resources for which no deadlock occurs in the system.
Que: A system contains three programs and each requires three tape units for its operation. The minimum number of tape units which the system must have such that deadlocks never arise is _________.
(a) 6 (b) 7
(c) 8 (d) 9
If 6 resources are there then it may be possible that all three process have 2 resources and waiting for 1 more resource. Therefore, all of them will have to wait indefinitely. If 7 resources are there, then at least one must have 3 resources so deadlock can never occur.
8. Questions on Deadlock Avoidance (Banker’s Algorithm)
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. Here, the Allocation matrix shows the current number of resources of each type allocated to each process and the Max matrix shows the maximum number of resources of each type required by each process during its execution. 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?
(a) Only REQ1 can be permitted
(b) Only REQ2 can be permitted.
(c) Both REQ1 and REQ2 can be permitted.
(d) Neither REQ1 nor REQ2 can be permitted
9. Questions on Deadlock Prevention VS Deadlock Avoidance
Which of the following is NOT true of deadlock prevention and deadlock avoidance schemes?
(a) In deadlock prevention, the request for resources is always granted if the resulting state is safe
(b) In deadlock avoidance, the request for resources is always granted if the result state is safe
(c) Deadlock avoidance is less restrictive than deadlock prevention
(d) Deadlock avoidance requires knowledge of resource requirements a priori
The only thing to remember is: Deadlock Prevention is less restrictive than Deadlock Avoidance.
10. Questions on Locality of Reference
Que: Locality of reference implies that the page reference being made by a process
(a) will always be to the page used in the previous page reference
(b) is likely to be to one of the pages used in the last few page references
(c) will always be to one of the pages existing in memory
(d) will always lead to a page fault
11. Questions on Thrashing
Thrashing occurs when
(A) When a page fault occurs
(B) Processes on system frequently access pages not memory
(C) Processes on system are in running state
(D) Processes on system are in waiting state
12. Questions on Page Table Size
Que: Consider a machine with 64 MB physical memory and a 32 bit virtual address space. If the page size is 4 KB, what is the approximate size of page table?
(a) 16 MB (b) 8 MB
(c) 2 MB (d) 24 MB
You may have seen various methods to solve this kind of questions. Here is the simplest one I follow:
Physical Memory = 64 MB = 2^28 B
Page Size = 4 KB = 2^12 B
#Page Frames = Physical memory/ page size = 2^16
So 16 bits are required to store an entry in a page table.
Number of entries = number of pages = 2^32/2^12 = 2^20
Page Table size= 2^20 * 16 bits = 2 MB
13. Questions on Paging
The level of these questions is somewhat higher than the rest of the operating system. But with good preparation this level can be surpassed.
A computer uses 46-bit virtual address, 32-bit physical address, and a three-level paged page table organization. The page table base register stores the base address of the first-level table (T1), which occupies exactly one page. Each entry of T1 stores the base address of a page of the second-level table (T2). Each entry of T2 stores the base address of a page of the third-level table (T3). Each entry of T3 stores a page table entry (PTE). The PTE is 32 bits in size. The processor used in the computer has a 1 MB 16-way set associative virtually indexed physically tagged cache. The cache block size is 64 bytes.
What is the size of a page in KB in this computer?
(A) 2
(B) 4
(C) 8
(D) 16
(B) 4
(C) 8
(D) 16
14. Questions on Page Faults
These are the easy questions, which can be solved even if you don’t have prior knowledge of OS.
Que: 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
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)
15. Questions on Page Replacement Policies
FIFO, LRU and Optimal are three page replacement policies which are asked in GATE. Questions on these policies are relatively easy. They give you a reference string and ask you the number of page faults according to the given page replacement policy.
Que: 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
(a) OPTIMAL < LRU < FIFO
(b) OPTIMAL < FIFO < LRU
(c) OPTIMAL = LRU
(d) OPTIMAL = FIFO
16. Questions on Disk Scheduling
In this type of questions, they give a reference string of block requests and ask you the total seek time following a disk scheduling policy.
Disk requests come to a disk driver for cylinders in the order 10, 22, 20, 2, 40, 6 and 38 at a given time when the given disk drive is reading from cylinder 20. The seek time is 6ms per cylinder.
1.What is the total seek time, if the disk arm scheduling algorithm FCFS is used?
A)360 ms B)850 ms C)900 ms D)None
2.What is the total seek time, if the closest cylinder next scheduling is used?
A)360 ms B)876 ms C)850 ms D)900 ms
17. Questions on Transfer Rate
They give you the rotation speed of the disk, total capacity, number of sectors, tapes etc and ask you the transfer rate or time to transfer a file.
Consider a typical disk that rotates at 15000 rotations per minute (RPM) and has a transfer rate of 50 × 106 bytes/sec. If the average seek time of the disk is twice the average rotational delay and the controller’s transfer time is 10 times the disk transfer time, the average time (in milliseconds) to read or write a 512 byte sector of the disk is _____________
(A) 6.1
Explanation: Disk latency = Seek Time + Rotation Time + Transfer Time + Controller Overhead
Seek Time? Depends no. tracks the arm moves and seek speed of disk
Rotation Time? depends on rotational speed and how far the sector is from the head
Transfer Time? depends on data rate (bandwidth) of disk (bit density) and the size of request
Disk latency = Seek Time + Rotation Time +
Transfer Time + Controller Overhead
Average Rotational Time = (0.5)/(15000 / 60) = 2 miliseconds
[On average half rotation is made]
It is given that the average seek time is twice the average rotational delay
So Avg. Seek Time = 2 * 2 = 4 miliseconds.
Transfer Time = 512 / (50 × 106 bytes/sec)
= 10.24 microseconds
Given that controller time is 10 times the average transfer time
Controller Overhead = 10 * 10.24 microseconds
= 0.1 miliseconds
Disk latency = Seek Time + Rotation Time +
Transfer Time + Controller Overhead
= 4 + 2 + 10.24 * 10-3 + 0.1 miliseconds
= 6.1 miliseconds
18. Questions on Interrupts
This is the most frequent question on interrupts.
Que: When an interrupt occurs, an operating system
(a) ignores the interrupt
(b) always changes state of interrupted process after processing the interrupt
(c) always resumes execution of interrupted process after processing the interrupt
(d) may change state of interrupted process to ‘blocked’ and schedule another process.
19. Questions on File Systems
Que: 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
(A) 3 Kbytes
(B) 35 Kbytes
(C) 280 Bytes
(D) Dependent on the size of the disk
(A) 3 Kbytes
(B) 35 Kbytes
(C) 280 Bytes
(D) Dependent on the size of the disk
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
20. Questions on Address Space
Que: In a virtual memory system, the address space specified by the address lines of the CPU must be ___ than the physical memory size and ____ than the secondary storage size.
(a) smaller, smaller
(b) smaller, larger
(c) larger, smaller
(d) larger, larger
Ans: (c)
You need to remember this order:(a) smaller, smaller
(b) smaller, larger
(c) larger, smaller
(d) larger, larger
Ans: (c)
Primary Memory < Virtual Memory < Secondary Memory
No comments:
Post a Comment