OperatingSystems
Question 1 
Consider three concurrent processes P1, P2 and P3 as shown below, which access a shared variable D that has been initialized to 100.
The process are executed on a uniprocessor system running a timeshared 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 _______.
A  10 
B  40 
C  60 
D  80 
P2 reads D=100, preempted.
P1 executes D=D+20, D=120.
P3 executes D=D+10, D=130.
Now, P2 has D=100, executes
D = D50 = 10050 = 50
P2 writes D=50 final value. This is minimum.
Next,
P2 reads D=100, executes D = D50, before that assume P1 & P3 has read D=100.
P2 makes D=50 & writes it.
P1 executes (D=100), D=D+20 & P3 executes D=D+10 gives maximum value D=130.
So, Y – X = 130 – 50 =80.
Question 2 
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 _____.
A  26 
B  33 
C  31 
D  28 
#include
int main( )
{
int i;
fork( );
fork( );
fork( );
fork( );
fork( );
}
n – fork statements will have 2^{n}1 child.
Hence, n = 5 ⇒ We have 31 child processes.
Question 3 
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 Lookaside 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?
A  8×2^{20} 
B  4×2^{20} 
C  16×2^{10} 
D  256×2^{10} 
So, it can refer to 2^{7} pages.
Each page size is 8 kB & word is 4 bytes.
So, the total addresses of virtual address spaces that can be addressed
Question 4 
Consider the following four processes with arrival times (in milliseconds) and their length of CPU bursts (in milliseconds) as shown below:
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 _____.
A  2 
B  7 
C  1 
D  4 
At this point P4 arrives with burst ‘Z’ & P3 is in queue with burst 3.
P1 & P2 have executed with P1 incurred delay 1unit & P2 0units.
Hence, Avg = 0+1+x/4 =1
⇒ x=3, the next delay should be 3. It would happen if assume Z=2.
It executes and completes at 6.
P3 will wait totally for 3units.
Hence, Avg=1.
Z=2
Question 5 
The index node (inode) of a Unixlike file system has 12 direct, one singleindirect and one doubleindirect pointers. The disk block size is 4 kB, and the disk block address is 32bits long. The maximum possible file size is (rounded off to 1 decimal place) ______ GB.
A  7.0 
B  9.0 
C  2.0 
D  4.0 
Max. file size
= (12 × 1k + 1k × 1k) × 4kB
≈ (1024 × 12 + 1024 × 1024) × 4 × 1024 bytes
≈ 4GB
Question 6 
Consider the following snapshot of a system running n concurrent processes. Process i is holding X_{i} 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 Y_{i} additional instances of R while holding the X_{i} instances it already has. Of the n processes, there are exactly two processes p and q such that Y_{p} = Y_{q} = 0. Which one of the following conditions guarantees that no other process apart from p and q can complete execution?
A  Min (X_{p}, X_{q}) ≥ Min {Y_{k}  1 ≤ k ≤ n, k ≠ p, k ≠ q} 
B  X_{p} + X_{q} < Max {Y_{k}  1 ≤ k ≤ n, k ≠ p, k ≠ q} 
C  Min (X_{p}, X_{q}) ≤ Max {Y_{k}  1 ≤ k ≤ n, k ≠ p, k ≠ q} 
D  X_{p} + X_{q} < Min {Y_{k}  1 ≤ k ≤ n, k ≠ p, k ≠ q} 
P_{i} holds X_{i} instances.
P_{i} can request additional Y_{i} instances.
Given two process p & q such that their additional requests are zero.
Y_{p} = Y_{q} = 0
{Y_{k}  1 ≤ k ≤ n, k ≠ p, k ≠ q} means that out of ‘n’ processes, we are left with (n2) process (except p&q), i.e., Y_{k} indicates additional request of all the processes (n2) except p & q.
For p & q to complete first, accordingly
X_{p} + X_{q} < Min {Y_{k}}
Option D is correct.
There are exactly two process p and q which do not need any additional instances of resources.
So, p and q will complete their execution and will release X_{p} and X_{q} instances of resources.
Now to guarantee that no other process apart from p and q can complete execution, the no. of instances of resources available must be less than the minimum no. of instances of resources required by any other process, i.e.,
X_{p} + X_{q} < Min {Y_{k}  1 ≤ k ≤ n, k ≠ p, k ≠ q}.
Question 7 
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?
A  (DM)/(XM) 
B  (XM)/(DM) 
C  (DX)/(DM) 
D  (XM)/(DX) 
X = (1 – P)M + D × P
X = M ∙ PM + DP
(X – M) = P(D – M)
⇒ P = (X – M) / (D – M)
Question 8 
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 _________.
A  2 
B  3 
C  4 
D  5 
No. of resources = 4
Let’s distribute each process one less than maximum demands i.e., (k1) resources.
So, for three processes, 3(k – 1) resources.
For deadlock avoidance provide an additional resource to any one of the process.
∴ Total resources required to avoid deadlock in any case is 3(k – 1) + 1 = 3k – 2
Now this 3k – 2 should be less than equal to available no. of resources, i.e.,
3k – 2 ≤ 4
k ≤ 2
So maximum value of k = 2
Question 9 
Consider the following solution to the producerconsumer 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().
Which one of the following assignments to P, Q, R and S will yield the correct solution?
A  P: full, Q: full, R: empty, S: empty 
B  P: empty, Q: empty, R: full, S: full

C  P: full, Q: empty, R: empty, S: full 
D  P: empty, Q: full, R: full, S: empty 
Initial: mutex = 1
empty = 0
full = N
Question 10 
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 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 ______ .
A  85 
B  86 
C  87 
D  88 
→ A storage disk – 4 platters(0, 1, 2 & 3), Cylinder – 200 (0, 1, …, 199) , 256 sector per track.
In the above question the disk requests are given in the form of 〈sector no, cylinder no, platter no〉.
In SSTF (Shortest Seek Time First) Disk Scheduling algorithm, requests having shortest seek time are executed first.
So, the seek time of every request is calculated in advance in queue and then they are scheduled according to their calculated seek time. Head is positioned at 80 and moving towards higher cylinder no.
Head Movement in SSTF = (86 – 80) + (86 – 72) + (134 – 72) + (134 – 16) = 200
P_{1}: Power dissipated by 200 movements = 0.2 * 200 = 40 mW
Power dissipated in reversing Head direction once = 15 mW
No. of times Head changes its direction = 3 P_{2}: Power dissipated in reversing Head direction = 3 * 15 = 45 mW
Total power consumption is P_{1} + P_{2} = 85 mW
Question 11 
In a system, there are three types of resources: E, F and G. Four processes P_{0}, P_{1}, P_{2} and P_{3} execute concurrently. At the outset, the processes have declared their maximum resource requirements using a matrix named Max as given below. For example, Max[P_{2}, F] is the maximum number of instances of F that P_{2} would require. The number of instances of the resources allocated to the various processes at any given state is given by a matrix named Allocation.
Consider a state of the system with the Allocation matrix as shown below, and in which 3 instances of E and 3 instances of F are the only resources available.
From the perspective of deadlock avoidance, which one of the following is true?
A  The system is in safe state. 
B  The system is not in safe state, but would be safe if one more instance of E were available. 
C  The system is not in safe state, but would be safe if one more instance of F were available.

D  The system is not in safe state, but would be safe if one more instance of G were available. 
Safe sequence:
〈P_{0}, P_{2}, P_{1}, P_{3}〉
P_{0}: P_{0} can be allotted 〈3,3,0〉.
After completion Available = 〈4,3,1〉
P_{2}: P_{2} can be allotted 〈0,3,0〉.
After completion: Available = 〈5,3,4〉
P_{1}: P_{1} can be allotted 〈1,0,2〉.
After completion: Available = 〈6,4,6〉
P_{3}: P_{3} can be allotted 〈3,4,1〉.
After completion: Available = 〈8,4,6〉
Question 12 
Threads of a process share
A  global variables but not heap. 
B  heap but not global variables. 
C  neither global variables nor heap. 
D  both heap and global variables. 
Question 13 
Consider the following CPU processes with arrival times (in milliseconds) and length of CPU bursts (in milliseconds) as given below:
If the preemptive shortest remaining time first scheduling algorithm is used to schedule the processes, then the average waiting time across all processes is __________ milliseconds.
A  3 
B  4 
C  5 
D  6 
Question 14 
A multithreaded program P executes with x number of threads and used y number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are nonreentrant, i.e., if a thread holds a lock l, then it cannot reacquire 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:
A  x = 1, y = 2 
B  x = 2, y = 1 
C  x = 2, y = 2 
D  x = 1, y = 1 
Here a nonreentrant process can’t own the same lock multiple times, so if the process tries to acquire an already owned lock, it will get blocked, and deadlock will happen.
From the above options x=1 (a single thread) and y=1 (a single lock) deadlock is possible when we consider the given situations in question.
Question 15 
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?
A  S1 is true, S2 is true 
B  S1 is true, S2 is false 
C  S1 is false, S2 is true 
D  S1 is false, S2 is false 
Page replacement algorithm suffers from Belady’s anomaly when it is not a stack algorithm.
S1: Random page replacement algorithm is not a stack algorithm. So, S1 is true.
S2: LRU is a stack algorithm. Therefore, it doesn’t suffer from Belady’s anomaly. S2 is false.
Question 16 
Which of the following is/are shared by all the threads in a process?
I. Program counter
II. Stack
III. Address space
IV. Registers
A  I and II only 
B  III only 
C  IV only 
D  III and IV only 
A process, in the simplest terms, is an executing program.
One or more threads run in the context of the process.
A thread is the basic unit to which the operating system allocates processor time.
A thread can execute any part of the process code, including parts currently being executed by another thread.
Each thread has its own stack, register and PC.
So here address space that is shared by all thread for a single process.
Question 17 
In a file allocation system, which of the following allocation scheme(s) can be used if no external fragmentation is allowed?
I. Contiguous
II. Linked
III. Indexed
A  I and III only 
B  II only 
C  III only 
D  II and III only 
Advantage:
i) Both sequential and direct access is possible.
ii) Extremely fast.
Disadvantage:
i) Suffers from both internal and external fragmentation.
ii) Increasing file size is difficult, because it depends on the availability of contiguous memory at a particular instance.
→ Linked list allocation:
Advantage:
i) Flexible in terms of size.
ii) Does not suffers from external fragmentation.
Disadvantage:
i) Allocation is slower.
ii) Does not support random or direct access.
iii) Pointers require some extra overhead.
→ Indexed allocation:
Advantage:
i) Support direct access, so provides fast access to the file blocks.
ii) No external fragmentation.
Disadvantage:
i) The pointer overhead for indexed allocation is greater than linked allocation.
ii) Inefficient in terms of memory utilization.
Question 18 
A system shares 9 tape drives. The current allocation and maximum requirement of tape drives for three processes are shown below:
Which of the following best describe current state of the system?
A  Safe, Deadlocked 
B  Safe, Not Deadlocked 
C  Not Safe, Deadlocked 
D  Not Safe, Not Deadlocked 
Available: (9 – (3 + 1 + 3)) = 2, P3 can be satisfied.
New available = 3 + 2 = 5
Now, P2 can be satisfied.
New available: 5 + 1 = 6
Now, P1 can be satisfied. Thus safe sequence: P3 → P2 → P1
That is not deadlocked.
Question 19 
Consider the set of processes with arrival time (in milliseconds), CPU burst time (in milliseconds), and priority (0 is the highest priority) shown below. None of the processes have I/O burst time.
The average waiting time (in milliseconds) of all the processes using preemptive priority scheduling algorithm is __________.
A  29 
B  30 
C  31 
D  32 
Waiting Time = 0 + (33 – 5) + (40 – 2) + (49 – 12) + (51 – 9) = 145
Average waiting time: 145/5 = 29
Question 20 
Consider an arbitrary set of CPUbound 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?
A  Shortest remaining time ﬁrst 
B  Roundrobin with time quantum less than the shortest CPU burst 
C  Uniform random 
D  Highest priority ﬁrst with priority proportional to CPU burst length 
We can consider an arbitrary set of CPUbound processes with unequal CPU burst lengths submitted at the same time to a computer system.
We have to choose the appropriate process scheduling algorithms, which would minimize the average waiting time in the ready queue.
Waiting time is the time for which process is ready to run but not executed by CPU scheduler.
In all CPU Scheduling algorithms, shortest job first is optimal.
It gives minimum turnaround time, minimum average waiting time and high throughput and the most important thing is that shortest remaining time first is the preemptive version of shortest job first.
This scheduling algorithm may lead to starvation because if the short processes are added to the CPU scheduler continuously then the currently running process will never be able to execute as they will get preempted but here all the processes are arrived at same time so there will be no issue such as starvation.
SRTF would be same as SJF.
So, A is the answer. Shortest remaining time first.
Question 21 
Consider a computer system with 40bit virtual addressing and page size of sixteen kilobytes. If the computer system has a onelevel page table per process and each page table entry requires 48 bits, then the size of the perprocess page table is __________ megabytes.
A  384 MB 
B  385 MB 
C  386 MB 
D  387 MB 
Size of memory = 2^{40} and Page size = 16 KB = 2^{14}
No. of pages = size of Memory / page size = 2^{40}/ 2^{14} = 2^{26}
Size of page table = 2^{26} * 48 / 8 bytes = 2^{6} * 6 MB = 384 MB
Question 22 
Consider a disk queue with requests for I/O to blocks on cylinders 47, 38, 121, 191, 87, 11, 92, 10. The CLOOK 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 ___________.
A  346 
B  347 
C  348 
D  349 
I/O to blocks on cylinders 47, 38, 121, 191, 87, 11, 92, 10.
CLOOK scheduling algorithm is used.
Head is initially at cylinder number 63.
First start from 63
63 → 87 → 92 → 121 → 191 = 24 + 5 + 29 + 70 movements = 128
191 → 10 movements = 181
10 → 11 → 38 → 47 = 1 + 27 + 9 movements = 37
Total = 128 + 181 + 37 = 346
Question 23 
Consider a computer system with ten physical page frames. The system is provided with an access sequence (a_{1},a_{2},…,a_{20},a_{1},a_{2},…,a_{20}), where each a_{i} is a distinct virtual page number. The difference in the number of page faults between the lastinﬁrstout page replacement policy and the optimal page replacement policy is ___________.
A  1 
B  2 
C  3 
D  4 
First we can consider LIFO (Last In First Out) →
a_{1} to a_{10} will result in page faults = 10 page faults,
Then a_{11} will replace a_{10} (last in is a_{10}), a_{12} replace a_{11} and …till a_{20} = 10 page faults and a_{20} will be top of stack and a_{9}…a_{1} are remained as such.
Then a_{1} to a_{9} are already there.
So, 0 page faults from a_{1} to a_{9}.
a_{10} will replace a_{20}, a_{11} will replace a_{10} and so on = So 11 page faults.
So total faults will be 10+10+11 = 31.
Second Optimal Page Replacement Policy →
a_{1} to a_{10} = 10 page faults,
a_{11} will replace a_{10} because among a_{1} to a_{10}, a_{10} will be used later, a_{12} will replace a_{11} and so on = 10 page faults.
a_{20} will be top of stack and a_{9}…a_{1} are remained as such.
a_{1} to a_{9} = 0 page fault. a_{10} will replace a_{1} because it will not be used afterwards and so on, a_{10} to a_{19} will have 10 page faults.
So no page fault for a_{20}.
Total = 10+ 10 +10 = 30.
So the difference between LIFO – Optimal = 1
Question 24 
Consider the following proposed solution for the critical section problem. There are n processes: P_{0}…P_{(n1)}. 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 P_{i}: do { c[i]=1; t[i] = pmax(t[0],...,t[n1])+1; c[i]=0; for every j ≠ i in {0,...,n1} { 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?
A  At most one process can be in the critical section at any time 
B  The bounded wait condition is satisﬁed 
C  The progress condition is satisﬁed 
D  It cannot cause a deadlock 
Based on the above code option B, C and D are not satisfied.
We can see that while (t[j] != 0 && t[j] <= t[i]);
because of this condition deadlock is possible when t[j] = = t[i].
Because Progress == no deadlock as no one process is able to make progress by stopping other process.
Bounded waiting is also not satisfied.
In this case both deadlock and bounded waiting to be arising from the same reason as if t[j] = = t[i] is possible then starvation is possible means infinite waiting.
Mutual exclusion is satisfied.
All other processes j started before i must have a value of t[j]) < t[i] as function pMax() return an integer not smaller than any of its arguments.
So if anyone out of the processes j have positive value will be executing in its critical section as long as the condition t[j] > 0 && t[j] <= t[i] within while will persist.
And when this j process comes out of its critical section, it sets t[j] = 0; and next process will be selected in for loop.
So, when i process reaches to its critical section none of the processes j which started earlier before process i is in its critical section.
This ensures that only one process is executing its critical section at a time.
So, A is the answer.
Question 25 
In which one of the following page replacement algorithms it is possible for the page fault rate to increase even when the number of allocated frames increases?
A  LRU (Least Recently Used) 
B  OPT (Optimal Page Replacement) 
C  MRU (Most Recently Used) 
D  FIFO (First In First Out) 
In Belady’s anomaly is the phenomenon in which increasing the number of page frames results in an increase in the number of page faults for certain memory access patterns 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.
In some situations, FIFO page replacement gives more page faults when increasing the number of page frames.
Question 26 
Consider the following processes, with the arrival time and the length of the CPU burst given in milliseconds. The scheduling algorithm used is preemptive shortest remainingtime ﬁrst.
The average turn around time of these processes is _________ milliseconds.
A  8.25 
B  8.26 
C  8.27 
D  8.28 
To answer the question we need to design the gantt chart:
In this algorithm, the processes will be scheduled on the CPU which will be having least remaining burst time.
Turnaround Time (TAT) = Completion Time (CT) – Arrival Time (AT)
TAT for P_{1} = 20 – 0 = 20,
TAT for P_{2} = 10 – 3 = 7,
TAT for P_{3} = 8 – 7 = 1,
TAT for P_{4} = 13 – 8 = 5.
Total TAT = 20 + 7 + 1 + 5 = 33 / 4 = 8.25 (Avg. TAT)
Question 27 
Consider the following twoprocess synchronization solution.
Process 0 Process 1   Entry: loop while (turn == 1); Entry: loop while (turn == 0); (critical section) (critical section) Exit: turn = 1; Exit: turn = 0;
The shared variable turn is initialized to zero. Which one of the following is TRUE?
A  This is a correct twoprocess synchronization solution. 
B  This solution violates mutual exclusion requirement. 
C  This solution violates progress requirement. 
D  This solution violates bounded wait requirement. 
So False.
C) Progress means if one process does not want to enter the critical section then it should not stop other process to enter the critical section.
But we can see that if process 0 will not enter the critical section then value of turn will not become 1 and process 1 will not be able to enter critical section.
So progress not satisfied. True.
D) Bounded waiting solution as there is a strict alternation.
So, False.
Question 28 
Consider a nonnegative counting semaphore S. The operation P(S) decrements S, and V(S) increments S. During an execution, 20 P(S) operations and 12 V(S) operations are issued in some order. The largest initial value of S for which at least one P(S) operation will remain blocked is _________.
A  7 
B  8 
C  9 
D  10 
P(S) operation remain in blocked state therefore it will 1.
The negative value of the counting semaphore indicates the number of processes in suspended list (or blocked).
Take any sequence of 20P and 12V operations, at least one process will always remain blocked.
So, X – 20 + 12 = 1
Here P(S) = 20 and V(S) = 12
X = 7
Question 29 
The following two functions P1 and P2 that share a variable B with an initial value of 2 execute concurrently.
P1() { C = B – 1; B = 2*C; } P2() { D = 2 * B; B = D  1; }
The number of distinct values that B can possibly take after the execution is
A  3 
B  4 
C  5 
D  6 
If we execute P1 process after P2 process, then B = 4
If we did preemption between P1 & P2 processes, then B = 2 (Preemption have done from P1 to P2) or B = 3 (Preemption have done from P2 to P1). So, among 2 & 3 values, only one value will be saved in B. So, total no. of distinct values that B can possibly take after the execution is 3.
Question 30 
Consider a uniprocessor system executing three tasks T_{1}, T_{2} and T_{3}, each of which is composed of an infinite sequence of jobs (or instances) which arrive periodically at intervals of 3, 7 and 20 milliseconds, respectively. The priority of each task is the inverse of its period and the available tasks are scheduled in order of priority, with the highest priority task scheduled first. Each instance of T_{1}, T_{2} and T_{3} requires an execution time of 1, 2 and 4 milliseconds, respectively. Given that all tasks initially arrive at the beginning of the 1^{st} millisecond and task preemptions are allowed, the first instance of T_{3} completes its execution at the end of ______________ milliseconds.
A  13 
B  12 
C  15 
D  16 
∴ At the end of 12 milliseconds, 1st instance of T_{3} will complete its execution.
Question 31 
Suppose the following disk request sequence (track numbers) for a disk with 100 tracks is given: 45, 20, 90, 10, 50, 60, 80, 25, 70. Assume that the initial position of the R/W head is on track 50. The additional distance that will be traversed by the R/W head when the Shortest Seek Time First (SSTF) algorithm is used compared to the SCAN (Elevator) algorithm (assuming that SCAN algorithm moves towards 100 when it starts execution) is _________ tracks.
A  10 
B  11 
C  12 
D  13 
∴ Total head movements,
= 10 + 10 + 10 + 10 + 10 + 55 + 20 + 5 + 10
= 140
SSTF:
∴ Total head movements
= 5 + 15 + 10 + 10 + 65 + 5 + 10 + 10
= 130
∴ Additional distance that will be traversed by R/W head is
= 140 – 130
= 10
Question 32 
Consider a main memory with five page frames and the following sequence of page references: 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3. Which one of the following is true with respect to page replacement policies FirstInFirst Out (FIFO) and Least Recently Used (LRU)?
A  Both incur the same number of page faults

B  FIFO incurs 2 more page faults than LRU 
C  LRU incurs 2 more page faults than FIFO 
D  FIFO incurs 1 more page faults than LRU 
∴ Number of page faults = 9
∴ Number of page faults = 9
Question 33 
A system has 6 identical resources and N processes competing for them. Each process can request atmost 2 resources. Which one of the following values of N could lead to a deadlock?
A  1 
B  2 
C  3 
D  6 
Question 34 
A computer system implements a 40bit virtual address, page size of 8 kilobytes, and a 128entry translation lookaside buffer (TLB organized into 32 sets each having four ways. Assume that the TLB tag does not store any process id. The minimum length of the TLB tag in bits is _________.
A  22 
B  23 
C  24 
D  25 
Question 35 
A computer system implements 8 kilobyte pages and a 32bit physical address space. Each page table entry contains a valid bit, a dirty bit, three permission bits, and the translation. If the maximum size of the page table of a process is 24 megabytes, the length of the virtual address supported by the system is ________ bits.
A  36 
B  37 
C  38 
D  39 
PAS = 32 bit
∴ No. of frames =PA/Page size = 2^{32} / 2^{13} = 2^{19}
Also, it is given that each page table entry contains a valid bit, a dirty bit, 3 permission bits:
= 5 bits reserved
So one Page table entry size is
= 19+5 = 24 bits = 3 bytes
Now, Page table size = No. of entries × Entry size
24 × 2^{20} = No. of entries × 3
No. of entries = 8 × 2^{20} = 2 ^{23}
∴ Virtual Address size = No. of entries × Page size = 2^{23} × 2^{13} = 2^{36}
∴ Virtual Address Space = 36 bits
Question 36 
The maximum number of processes that can be in Ready state for a computer system with n CPUs is
A  n 
B  n^{2} 
C  2^{n} 
D  Independent of n 
Maximum number of processes that will be in ready state is independent of number of processors.
Question 37 
Consider the following policies for preventing deadlock in a system with mutually exclusive resources.
 I. Processes should acquire all their resources at the beginning of execution. If any resource is not available, all resources acquired so far are released.
II. The resources are numbered uniquely, and processes are allowed to request for resources only in increasing resource numbers.
III. The resources are numbered uniquely, and processes are allowed to request for resources only in decreasing resource numbers.
IV. The resources are numbered uniquely. A process is allowed to request only for a resource with resource number larger than its currently held resources.
Which of the above policies can be used for preventing deadlock?
A  Any one of I and III but not II or IV 
B  Any one of I, III, and IV but not II 
C  Any one of II and III but not I or IV 
D  Any one of I, II, III, and IV 
Question 38 
For the processes listed in the following table, which of the following scheduling schemes will give the lowest average turnaround time?
A  First Come First Serve 
B  Nonpreemptive Shortest Job First 
C  Shortest Remaining Time 
D  Round Robin with Quantum value two 
FCFS:
TAT for A = completion time(A) – AT(A) = 3 – 0 = 3
TAT of B = 9 – 1 = 8
TAT of C = 13 – 4 = 9
TAT of D = 15 – 6 = 9
∴ Avg. TAT = 29/4
SJF:
TAT of A = 3 – 0 = 3
TAT of B = 9 – 1 = 8
TAT of C = 15 – 4 = 11
TAT of D = 11 – 6 = 5
∴ Avg. TAT = 27/4
SRTF:
TAT of A = 3 – 0 = 3
TAT of B = 15 – 1 = 14
TAT of C = 8 – 4 = 4
TAT of D = 10 – 6 = 4
∴ Avg. TAT = 25/4
RR:
TAT of A = 5 – 0 = 5
TAT of B = 15 – 1 = 14
TAT of C = 13 – 4 = 9
TAT of D = 11 – 6 = 5
∴ Avg. TAT = 33/4
∴ SRTF has lowest Avg. TAT.
Question 39 
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 ShortestSeek Time First (SSTF) is being used for scheduling the disk access, the request for cylinder 90 is serviced after servicing ____________ number of requests.
A  3 
B  4 
C  5 
D  6 
90 is serviced after servicing three requests, i.e.,
100 → 105 → 110 → 90
Question 40 
Which one of the following is FALSE?
A  User level threads are not scheduled by the kernel. 
B  When a user level thread is blocked, all other threads of its process are blocked. 
C  Context switching between user level threads is faster than context switching between kernel level threads. 
D  Kernel level threads cannot share the code segment. 
Question 41 
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. 
After allowing Req 1,
Available: X=3, Y=2, Z=0
With this we can satisfy P1’s requirement. So available becomes: X=6, Y=4, Z=0.
Since Z is not available, neither P0’s nor P2’s requirement can be satisfied. So, it is an unsafe state.
Lets take 2nd case,
After allowing Req 2,
Available: X=1, Y=2, Z=2
With this we can satisfy any one of P1’s or P2’s requirement. Lets first satisfy P1’s requirement. So Available now becomes:
X=6, Y=4, Z=2
Now with the availability we can satisfy P2’s requirement. So Available now becomes,
X=8, Y=5, Z=3
With this availability P0 can also be satisfied. So, hence it is in safe state.
So from above two cases Req 1 cannot be permitted but Req 2 can be permitted.
Question 42 
Consider the following set of processes that need to be scheduled on a single CPU. All the times are given in milliseconds.
Using the shortest remaining time first scheduling algorithm, the average process turnaround time (in msec) is ________.
A  7.2 
B  7.3 
C  7.4 
D  7.5 
TAT(A) = 80 = 8, TAT(B)= 53=2, TAT(C)= 125=7, TAT(D)= 217= 14, TAT(E)=1510=5
Average turnaround time = 8+2+7+14+5/ 5 = 7.2ms
Question 43 
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__________.
A  7 
B  8 
C  9 
D  10 
Total 7 faults are there.
Question 44 
A FAT (file allocation table) based file system is being used and the total overhead of each entry in the FAT is 4 bytes in size. Given a 100 × 10^{6} bytes disk on which the file system is stored and data block size is 10^{3} bytes, the maximum size of a file that can be stored on this disk in units of 10^{6} bytes is ________.
A  99.60 
B  99.61 
C  99.62 
D  99.63 
= Total disk size/ disk block size
= 100 × 10^{6} / 10^{3}
= 100 × 10^{3}
∴ Total overhead = 100 × 10^{3} × 4B
= 400 × 10^{3} B
= 0.4 × 10^{6} B
So, Maximum size of file that can be stored in disk is,
Total disk size – Total overhead
= 100 × 10^{6} – 0.4 × 10^{6}
= 99.6 × 10^{6} B
Question 45 
Consider the procedure below for the ProducerConsumer problem which uses semaphores:
semaphore n=0; semaphore s=1; void producer() void consumer() { { while(true) while(true) { { produce(); semWait(s); semWait(s); semWait(n); addToBuffer(); removeFromBuffer(); semSignal(s); semSignal(); semSignal(n); consume(); } } } }
Which one of the following is TRUE?
A  The producer will be able to add an item to the buffer, but the consumer can never consume it. 
B  The consumer will remove no more than one item from the buffer. 
C  Deadlock occurs if the consumer succeeds in acquiring semaphore s when the buffer is empty. 
D  The starting value for the semaphore n must be 1 and not 0 for deadlockfree operation. 
Question 46 
Three processes A, B and C each execute a loop of 100 iterations. In each iteration of the loop, a process performs a single computation that requires tc CPU milliseconds and then initiates a single I/O operation that lasts for tio milliseconds. It is assumed that the computer where the processes execute has sufficient number of I/O devices and the OS of the computer assigns different I/O devices to each process. Also, the scheduling overhead of the OS is negligible. The processes have the following characteristics:
Process id tc tio A 100 ms 500 ms B 350 ms 500 ms C 200 ms 500 ms
The processes A, B, and C are started at times 0, 5 and 10 milliseconds respectively, in a pure time sharing system (round robin scheduling) that uses a time slice of 50 milliseconds. The time in milliseconds at which process C would complete its first I/O operation is ___________.
A  1000 
B  1001 
C  1002 
D  1003 
So ‘C’ completes its I/O at 1000 time units.
Question 47 
A computer has twenty physical page frames which contain pages numbered 101 through 120. Now a program accesses the pages numbered 1, 2, …, 100 in that order, and repeats the access sequence THRICE. Which one of the following page replacement policies experiences the same number of page faults as the optimal page replacement policy for this program?
A  Leastrecentlyused 
B  Firstinfirstout 
C  Lastinfirstout 
D  Mostrecentlyused 
So, there would be 300 page faults in total (each access 100 page faults). Also it is visible that every time a replacement is done for the page which is most recently referred as it will be least recently referred in future. So, for the given page reference string optimal page replacement policy is working same as most recently used policy and thus number of page faults will be same in both of them.
Question 48 
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  7 
B  8 
C  9 
D  10 
Question 49 
An operating system uses shortest remaining time first scheduling algorithm for preemptive scheduling of processes. Consider the following set of processes with their arrival times and CPU burst times (in milliseconds):
The average waiting time (in milliseconds) of the processes is
A  5.5 
B  5.6 
C  5.7 
D  5.8 
WT – Waiting Time
CT – Completion Time
TAT – Turn Around Time
TAT = CT – AT < br> WT = TAT – BT
Gantt chart using Shortest remaining time first,
Avg. WT = 15+0+3+4/4 = 22/4 = 5.5
Question 50 
Consider a paging hardware with a TLB. Assume that the entire page table and all the pages are in the physical memory. It takes 10 milliseconds to search the TLB and 80 milliseconds to access the physical memory. If the TLB hit ratio is 0.6, the effective memory access time (in milliseconds) is _________.
A  122 
B  123 
C  124 
D  125 
= 10 + 0.4 × 80 + 80
= 10 + 32 + 80
= 122 ms