GATE questions

1) 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
 A fails as L can overflow
 B fails as L can take on a non-zero value when the lock is actually available
 C works correctly but may starve some processes
 D works correctly without starvation
2) certain computation generates two arrays a and b such that a[i]=f(i) for 0 ≤ i < n and
b[i]=g(a[i]) for 0 ≤ i < n. Suppose this computation is decomposed into two concurrent processes
X and Y such that X computes the array a and Y computes the array b. The processes employ
two binary semaphores R and S, both initialized to zero. The array a is shared by the two
processes. The structures of the processes are shown below.
Process X: Process Y:
private i; private i;
for (i=0; i < n; i++) { for (i=0; i < n; i++) {
a[i] = f(i); EntryY(R, S);
ExitX(R, S); b[i]=g(a[i]);
} }
Which one of the following represents the CORRECT implementations of ExitX and
EntryY? (A)
ExitX(R, S) {
P(R);
 V(S);
}

EntryY (R, S) {
P(S);
V(R);
}
(B)
ExitX(R, S) {
V(R);
V(S);
}

EntryY(R, S) {
P(R);
P(S);
}
(C)
ExitX(R, S) {
P(S);
V(R);
}
EntryY(R, S) {
V(S);
P(R);
}
(D)
ExitX(R, S) {
 V(R);
P(S);
}
EntryY(R, S) {
V(S);
P(R);
}
 A
 B
 C
 D
3) The following program consists of 3 concurrent processes and 3 binary [Link]
semaphores are initialized as S0 = 1, S1 = 0, S2 = 0.

How many times will process P0 print '0'?

 A At least twice
 B Exactly twice
 C Exactly thrice
 D Exactly once
4) Consider the 3 processes, P1, P2 and P3 shown in the table.
Process Arrival time Time Units Required
P1 0 5
P2 1 7
P3 3 4
The completion order of the 3 processes under the policies FCFS and RR2 (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
5) 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
 D 7.33
6) 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 500
 B 1000
  C 2000
 D 10000
7) A system has n resources R0,...,Rn-1,and k processes P0,....Pk-1 .The implementation of the
resource request logic of each process Pi is as follows:
if (i % 2 == 0) {
if (i < n) request Ri
if (i+2 < n) request Ri+2
}
else {
if (i < n) request Rn-i
if (i+2 < n) request Rn-i-2
}
In which one of the following situations is a deadlock possible?
 A n=40, k=26
 B n=21, k=12
 C n=20, k=10
 D n=41, k=19
8) Consider the following snapshot of a system running n processes. Process i is holding Xi
instances of a resource R, 1 <= i <= n. currently, all instances of R are occupied. Further, for all
i, process i has placed a request for an additional Yi instances while holding the Xi instances it
already has. There are exactly two processes p and q such that Yp = Yq = 0. Which one of the
following can serve as a necessary condition to guarantee that the system is not approaching a
deadlock?
 A min (Xp, Xq) < max (Yk) where k != p and k != q
 B Xp + Xq >= min (Yk) where k != p and k != q
 C max (Xp, Xq) > 1
 D min (Xp, Xq) > 1
9) 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 [Link]
 C Both REQ1 and REQ2 can be permitted.
 D Neither REQ1 nor REQ2 can be permitted
10) P={P1,P2,P3,P4} consists of all active processes in an operating
system. R={R1,R2,R3,R4}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→P4Assignment edges: R1→P1,R2→P2,R3

→P3,R4→P4 (the assignment edge R1→P1R1→P1 means resource R1R1 is assigned to
process P1P1, and so on for others)
Claim edges: P1→R2,P2→R3,P3→R1,P2→R4,P4→R2Claim edges: P1→R2,P2→R3,P3→R1
,P2→R4,P4→R2 (the claim edge P1→R2P1→R2 means process P1P1 is waiting for
resource R2R2, and so on for others)

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

A Aborting P1P1 makes the system deadlock free.
B Aborting P3P3 makes the system deadlock free.
C Aborting P2P2 makes the system deadlock free.
Aborting P1P1 and P4P4 makes the system deadlock free.

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

The *-marked references cause page replacements.

Which one or more of the following could be the page replacement policy/policies in use?
A Least Recently Used page replacement policy
B Least Frequently Used page replacement policy
C Most Frequently Used page replacement policy
D Optimal page replacement
12) “In round-robin scheduling, there are n processes in the ready queue, and the time-slice is q
units. In the worst case, the interrupted process will get the CPU again after...?”
a) (n − 1) × q
b) (n + 1) × q
c) n × q
d) (n²) × q
13) Given processes: P1 (AT = 0, BT = 8), P2 (AT = 1, BT = 4), P3 (AT = 2, BT = 2). Using
Shortest Remaining Time First (SRTF), what is the average turnaround time?
a) 6.33
b) 7.00
c) 8.00
d) 9.00
14) Reference string: 7, 0, 1, 2, 0, 3, 0, 4; number of frames = 3. How many page faults occur
using the Optimal replacement algorithm?
a) 5
b) 6
c) 7
d) 8
15) Disk=1GB, block size=1KB. Max file size in contiguous allocation?
a) 512 MB
b) 1 GB
c) 2 GB
d) 4 GB