PROCESS MANAGEMENT

Q1. Which one of the following statements is false?

(a) If a user process needs to perform I/O operation, it has to make a system call to ask
the OS kernel to perform it in its behalf.
(b) I/O hardware can be directly accessed only by a process running in the kernel
mode.
(c) If a privileged instruction is executed while the CPU is in the user mode, an
interrupt is raised.
(d) Any process can change from user mode to kernel (privileged) mode and continue
executing its own code, but when its kernel mode work is done, the control is given to
the OS kernel to check for any unauthorized access.

Q2. Multiple threads used in multi threading share:

1. Program counter
2. Heap
3. File descriptors
4. Call stack
(a) 2 only (b) 1, 3, and 4 only
(c) 2 and 3 only (d) 1 and 4 only

Q3. Which of the followings are true about threads?

1. Different threads share the same address space
2. Different threads share the same heap
3. Different threads share the same stack
4. Different threads share the same PC
(a) 1 and 2 only (b) 1 and 4 only
(c) 3 and 4 only (d) 1 and 4 only

Q4. Which of the following is/are true?

(a) A process may contain multiple threads, but each thread belongs to only one
process
(b) The process ID of a zombie process can be reused by another process
(c) If the memory usage of process A is twice the size as process B, then the latency of
fork() in process A is roughly twice as the latency of fork() in process B.
(d) Kernel-level threads of the same process do not share the same memory address
space.

OS Gate-2020 Page 1
Q5. Which of the followings are true about the relationship between kernel- and user- level
threads?
(a) Both of them are faster to create than creating a process
(b) When a kernel- level thread execute an I/O system call, the other kernel- threads
within the same process are blocked as well
(c) Lock/unlock synchronizations for kernel -level threads are system calls (assume the
lock/unlock are implemented using test- and- set)
(d) None of the above

Q6. Which one of the following statements is false about processes and threads?
(a) Context switching for threads requires less overhead that for processes.
(b) When a process invokes an I/O system call, its state may be changed from executing
to waiting.
(c) With the many to one model, user threads are managed by the kernel.
(d) One task of context switching is to store the CPU state in the PCB.

Q7. Which one of the following statements is true about processes and threads?
(a) Threads share the same address space, including code segment, data segment, stack
pointer and program counter
(b) Thread library implementing many-to-one model can make use of at most 4 CPUs.
(c) When one thread of a process makes exec() call, all threads are terminated.
(d) The thread library is responsible for thread scheduling, regardless of which model
(many to-one, one-to-one, many-to-many) is used.

Q8. Which of the following statements is/are false about process states and state
transitions:
1. A process state changes from NEW to READY when it is admitted to the system by
the long term scheduler
2. Process state changes from RUNNING to WAITING when its time slice expires
3. Only processes in the READY state can change into RUNNING state.
4. If a process is preempted, its state changes to READY.
5. There can be several processes in the WAITING state, but only one in the READY
state
(a) 1, 2, and 4 only
(b) 1, 3 and 4 only
(c) 2 and 5 only
(d) 2, 4 and 5 only

OS Gate-2020 Page 2
For next three questions select the valid state transition for process A in each of the following
cases.
Q9. A context switch is performed because process A was “picked” by the OS scheduler for
execution.
(a) Blocked → Ready
(b) Blocked → Running
(c) Ready → Running
(d) Running → Ready

Q10. Process A performs the exit () system call.

(a) Running → Blocked
(b) Running → Ready
(c) Blocked → Running
(d) Running → Stop

Q11. Process A performs the write() system call to write the data on I/O device
(a) Blocked → Ready
(b) Blocked → Running
(c) Ready → Running
(d) Running → Blocked

Q12. Processes exist in a number of different states like Running, Ready, Blocked, and New.
Which of the following state transition is not a valid for a process?
(a) Running, Running, Running, Ready, Running, Running, Running, Ready
(b) New, Ready, Ready, Running, Ready, Ready
(c) Running, Running, Blocked, Blocked, Blocked, Running
(d) Running, Running, Blocked, Blocked, Blocked, Ready, Running

Q13. Which of the following statements are true when the kernel switches execution from
the currently running process to another runnable process?
1. The kernel must save the register values of the current process to memory.
2. The kernel must close all the files opened by the current process.
3. The kernel must restore the register values of the next process to be executed.
4. The kernel must save the content of the current process‟s memory on disk.
(a) 1 and 3 only
(b) 1, 2 and 3 only
(c) 2 and 4 only
(d) All the above
OS Gate-2020 Page 3
Q14. Two of the following statements about scheduling are false:
1. Preemptive scheduler lets the process finish its CPU burst, but preempts the process
when it starts blocking I/O operation
2. Round Robin is a preemptive scheduler and does not suffer from starvation
3. Non-preemptive schedulers suffer from the convoy effect.
4. Shortest-Job-First scheduler is only of theoretical interest, as we cannot know the
future CPU burst lengths
5. Multilevel Feedback Queue scheduler gives priority to I/O intensive processes
(a) 1, 2, and 4 only (b) 1, 3 and 4 only
(c) 1 and 3 only (d) 2, 4 and 5 only

Q15. A process control block is:

(a) A structure that stores information about a single process.
(b) The kernel's structure for keeping track of all the processes in the system.
(c) A linked list of blocked processes (those waiting on some event).
(d) A kernel interface for controlling processes (creating, deleting, suspending)

Q16. For a workload consisting of ten CPU-bound jobs of all the same length (each would
run for 10 seconds in a dedicated environment), which policy would result in the
lowest average response time?
(a) Round-robin with a 100 millisecond quantum
(b) Shortest Job First
(c) Shortest Remaining Time First
(d) Round-robin with a 1000 nanosecond quantum

For the next two questions consider the five processes with their arrival time and CPU burst
as shown in below table:
Processes Arrival time(in units) Burst time(in units)
P1 5 6
P2 4 3
P3 3 4
P4 2 3
P5 0 2
Q17. If the scheduler user FCFS policy then, what is the average waiting time (in units) of all
processes? _____________

Q18. If the scheduler user SJF policy then, what is the average turnaround time (in units) of
all processes? _______________

OS Gate-2020 Page 4
Q19. Consider the following processes arrived at the same time in the given order with the
following CPU burst time
Process CPU burst time (in units)
P1 5
P2 3
P3 2
P4 7
P5 4
If the scheduler user Round Robin policy with 2 units of time quantum, then what is
the average waiting time (in units) of all processes?____________

For the next two questions consider the following set of processes with the arrival and CPU
burst time:
Processes Arrival time (in units) Burst time (in units)
P1 2 5
P2 3 2
P3 0 1
P4 6 3
Q20. What is the average waiting time (in units), if the scheduler uses SRTF scheduling
policy?____

Q21. What is the throughput and CPU utilization respectively, if the scheduler uses SRTF
scheduling policy?
(a) 0.33, 0.92 (b) 0.26, 0.93
(c) 1, 2 (d) 1, 1
Q22. Consider the following processes arrived at the same time in the given order with the
following CPU burst times and priorities:
Processes CPU Burst time (in units) Priority
P1 6 1
P2 5 2
P3 4 2
P4 2 3
P5 4 4
Assume that the lower no represent higher priority, and if the multiple processes comes
with same priorities then scheduler breaks the ties by using the SJF policy. What is the
average waiting time (in units), if the scheduler uses non-preemptive priority based
scheduling policy? _____

OS Gate-2020 Page 5
For the next two questions consider the following set of processes with the arrival, CPU
burst time and priorities:
Processes Arrival time (in units) CPU time (in units) Priority
P1 5 20 4
P2 4 5 2
P3 2 7 3
P4 0 10 1
Assume that the higher no represent higher priority, and the scheduler breaks the all ties by
using the FCFS policy.
Q23. What is the average waiting time (in units), if the scheduler uses SRTF scheduling
policy?_____
Q24. What is the response time (in units) of process P1, if the scheduler uses SJF scheduling
policy?___ ___

For next two questions, consider the Longest Job First (LJF) scheduling. In LJF scheduling,
Out of all the available processes, CPU is assigned to the process having largest burst time. In
case of a tie, it is broken by FCFS Scheduling. LJF Scheduling can be used in both preemptive
and non-preemptive mode. Preemptive mode of Longest Job First is called as Longest
Remaining Time First (LRTF). Assume that minimum allocation of CPU is 1 unit of time.
Q25. Consider the set of 5 processes whose arrival time and burst time are given below-
Process Id Arrival time (in units) Burst time (in units)
P1 0 3
P2 1 2
P3 2 4
P4 3 5
P5 4 6
If the CPU scheduling policy is LJF non-preemptive, what is the average waiting time
(in units) of all processes?__________
Q26. Consider the set of 4 processes whose arrival time and burst time are given below-
Process Id Arrival time(in units) Burst time (in units)
P1 1 2
P2 2 4
P3 3 6
P4 4 8
If the CPU scheduling policy is LJF preemptive, what is the average waiting time (in
units) of all processes? ________________

OS Gate-2020 Page 6
Q27. Consider the following four processes with arrival times (in milliseconds) and their
length of CPU bursts (in milliseconds) as shown below:
Process Id Arrival time CPU Burst time
P1 0 2
P2 1 3
P3 3 x
P4 2 1
These processes are run on a single processor using SRTF scheduling algorithm. If the
average waiting time of the processes is 1 millisecond, then the value of x is _______

For the next two questions, consider the following four processes with arrival times (in
milliseconds) and their length of CPU bursts (in milliseconds) as shown below:
Process Arrival time Burst time
C 2 3
D 0 6
B 4 3
A 6 4
Q28. Which of the following is the execution order of processes under the SJF?
(a) D D C C C B A A A A B D D D D B

(b) D D D D D D C C C B B B A A A A

(c) D D C C C B A A A A B B D D D D

(d) None of the above

Q29. Which of the following is the execution order of processes under the SRTF?
(a) D D C C C B B B D D D D A A A A

(b) D D D D D D C C C A A A A B B B

(c) D D C C C B A A A A B B D D D D

(d) None of the above

OS Gate-2020 Page 7
Q30. Consider the following set of processes, with the length of the CPU burst time given in
milliseconds:
Process Execution Time Priority
P1 45 2
P2 30 1
P3 15 3
P4 30 5
P5 40 4
The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0.
Which of the schedules produced by each algorithm results in the minimal average
waiting time?
(a) FCFS,
(b) SJF,
(c) a non-preemptive priority (a smaller priority number implies a higher priority),
(d) RR (with quantum = 5).

Q31. Assume, for the following jobs, a FIFO scheduler and only one CPU. Each job has a
“required” runtime, which means the job needs that many time units on the CPU to
complete.
 Job A arrives at time=0, required runtime=X time units
 Job B arrives at time=5, required runtime=Y time units
 Job C arrives at time=10, required runtime=Z time units
Assuming an average turnaround time between 10 and 20 time units (inclusive), which
of the following run times for A, B, and C is not possible?
(a) A=10, B=10, C=10 (b) A=20, B=20, C=20
(c) A=5, B=10, C=15 (d) A=20, B=30, C=40
Q32. Assume the following schedule for a set of three jobs, A, B, and C:
 A runs first (for 10 time units) but is not yet done
 B runs next (for 10 time units) but is not yet done
 C runs next (for 10 time units) and runs to completion
 A runs to completion (for 10 time units)
 B runs to completion (for 5 time units)
Which scheduling disciplines could allow this schedule to occur?
1. FIFO 2. Round Robin
3. SRTF 4. Multi-level Feedback Queue
(a) 2 and 4 only (b) 1, 2 and 3 only
(c) 2, 3 and 4 only (d) 1, 3 and 4 only

OS Gate-2020 Page 8
Q33. Consider a system with 3 processes A, B and C with following specification.
Process Id Arrival time I/O burst time CPU burst time I/O burst time CPU burst time
A 0 2 4 6 6
B 2 3 3 4 4
C 4 7 4 1 8
What is the average waiting time with SJF scheduling assuming I/O can be
overlapped? __

For the next eight questions, consider a priority scheduling algorithm with preemption using
the following scenario:
 Suppose we have five processes: P0 - priority 0; P10 and P11 - priority 1; P20 and P21 -
priority 2.
 Assume lower priority number represent higher priority process and higher priority
processes should run before lower priority processes.
 Assume that processes with the same priority should run FCFS basis.
 Assume that when a process is placed into its Running state, it is given a time quantum of
5 time units.
 A process may run for its allotted 5 time units, or it may block itself for I/O before its time
expires.
 A low priority process is not preempted by a newly-ready high priority process until the
quantum of the Running process expires.
 The scheduler does not apply "aging".
 Assume that the I/O operation of process can be overlapped.
 At time t = 0, the scheduler resched() is called, and the Ready list looks like:

 Each entry means:

 The desire CPU burst / I/O burst patterns of each process are:

 Assume that the process runs in the iteration of CPU then followed by I/O.
Q34. What is the completion time of process P10?___________
Q35. What is the completion time of process P11?___________
Q36. What is the completion time of process P20?___________
Q37. What is the completion time of process P21?___________

OS Gate-2020 Page 9
Q38. The percentage of time when the CPU remains idle is____________
Q39. The average turnaround time of all processes is___________
Q40. The average waiting time of all processes is__________
Q41. The average response time of all processes is__________

Q42. The diagram below depicts a typical multilevel feedback queue with three priority
levels: high, medium, and low. Assume that the high priority level queue employs RR
with quantum = 8 msec, the medium priority level queue employs RR with quantum =
16 msec, and the low priority level queue employs FCFS. In MLFQ running the jobs in
highest priority queue first. Once those finish, run jobs at the next highest priority
queue, etc. Job starts in their priority queue. If job's time slices expires, drop its priority
one level. If job's time slices does not expire (the context switch comes from an I/O
request instead), then increase its priority one level, up to the top priority level. CPU
bound jobs drop like a rock in priority and I/O bound jobs stay at a high priority.
Processes arrive as indicated in the table below and compete for a single CPU. All times
are in msec.

What is the Average Turnaround Time for the all process? _____________
Q43. An OS uses a MLFQ scheduler with 3 round-robin levels. The quantum for the highest
priority queue 1 that of second highest priority queue is 2 and that of third queue is 4
time units respectively. Assume that we have 6 jobs that arrive at time 0 with burst
lengths 8, 2, 1, 3, 10 and 4 in the order of arrival. All the jobs first kept in the highest
priority queue after completing their time quantum the jobs are move to the second
highest priority queue after completing their time quantum the jobs are moved to the
third queue and from third to first and so on till the processes is completed. What is the
average waiting time of processes?_____________

OS Gate-2020 Page 10
Q44. Consider the following table of arrival time and burst time for three
processes P1, P2 and P3.

Suppose that a fourth process P4 enters the system at time 7.6 sec and needs 6 sec of
CPU time. Also assume that P2, P3 are interactive and P1, P4 are batch. A multilevel
queue is in effect. The first queue is for interactive processes only whose processes get 1
sec each time they are in CPU. The second queue is for batch processes, which get up to
4 units each time they are in CPU. Processes are dispatched as follows: two processes (if
available) are dispatched from the interactive queue followed by one process (if
available) from the batch queue etc. What will be the average turnaround time (in
sec)?__________

Q45. Which of the following statement is FALSE?

(a) Round robin (RR) scheduler behaves like first-come first-serve (FCFS) scheduler for
infinitely large time quantum.
(b) Multi-level feedback queue (MLFQ) scheduler behaves like round robin (RR)
scheduler if there is only one priority level.
(c) Shortest remaining time first (SRTF) scheduler behaves like shortest job first (SJF)
algorithm if the set of processes are fixed (no new process is created) and the processes
are completely CPU bound.
(d) Multi-level feedback queue (MLFQ) scheduler behaves like round robin (RR)
scheduler if the set of processes are fixed (i.e., no new process is created) and the
processes are completely CPU bound.

For the next two questions, consider a new scheduling discipline Highest Response Ratio
Next (HRRN), HRRN scheduling is a non-preemptive discipline, similar to Shortest Job First
(SJF) in which the priority of each job is dependent on its estimated run time, and also the
amount of time it has spent waiting. In HRRN each time new priority of process is calculated
when the current process releases the CPU or blocked, and the scheduler select the next
highest priority process for the execution.
𝑤𝑎𝑖𝑡𝑖𝑛𝑔 𝑡𝑖𝑚𝑒
𝑃𝑟𝑖𝑜𝑟𝑖𝑡𝑦 = 1 +
𝑒𝑠𝑡𝑖𝑚𝑎𝑡𝑒𝑑 𝑟𝑢𝑛 𝑡𝑖𝑚𝑒
Minimum value of priority is 1.0, which occurs when a process first enters the system. In case
of a tie, it is broken by FCFS Scheduling. Consider a table of processes and their associated
arrival and service times. All times are in msec.

OS Gate-2020 Page 11
 Process Id Arrival time Burst time
P0 0 3
P1 2 6
P2 4 4
P3 6 5
P4 8 2
Q46. If the CPU scheduling policy is HRRN, what is the average waiting time (in msec) of all
processes?__________
Q47. A soft real-time system has four periodic events with periods of 50, 100, 200, and 250
msec each. Suppose that the four events require 35, 20, 10, and x msec of CPU time,
respectively. What is the largest integer value of x for which the system is
schedulable?________

Q48. Consider the following three periodic real-time tasks to be scheduled using Earliest
Deadline First (EDF) on a uni-processor: T1 = (e1=10, p1=20), T2 = (e2=5, p2=50), T3 =
(e3=10, p3=35). Assume initially all arrive at the time = 0. At which time fifth instance
of T2 will be finish._____

Q49. Consider the following three periodic real-time tasks to be scheduled using Rate
Monotonic Algorithm (RMA) on a uni-processor: T1 = (e1=20, p1=100), T2 = (e2=30,
p2=150), T3 = (e3=90, p3=200). Assume initially all arrive at the time = 0. At which time
second instance of T2 will be finish._____

For the next two questions consider the scheduler and system specification:
 There are two priority levels: low and high
 Time quantum for both priority levels is 10 time units
 If a process is preempted because a higher priority process arrives, it remains at the top of
its ready queue – it is placed at the end only when its time quantum expires or when its
CPU burst is finished.
 Each CPU burst is followed by an I/O operation taking 16 time units
 The I/O operations of different processes overlap and do not interfere, i.e. if P1 starts to
wait at time 10 and P2 starts to wait at time 20, P1 will become ready at time 10+16 = 26
and P2 will become ready at time 20+16=36. Process specification:
 There are four processes P0, P1, P2 and P3
 Processes P0 and P2 arrive at time 0, processes P1 and P3 arrive at time 10
 P0 and P1 are of high priority, P2 and P3 are of low priority
 The CPU burst time of processes are as follows:
P0: 2, 3, 2, 3 P1: 5, 14, 7, 9 P2: 12, 3, 18, 4 P3: 15, 25, 32, 2

OS Gate-2020 Page 12
Q50. How many processes finishes its All CPU burst up to 110 time step
(a)0 (b)1 (c)2 (d)3

Q51. What is the Average Turnaround Time under the Round Robin Scheduler?
(a) 131 (b) 130.5 (c) 132 (d) 133.75

For the next two questions, consider a system running ten I/O-bound tasks and one CPU-
bound task. Assume that the I/O-bound tasks issue an I/O operation once for every
millisecond of CPU computing and that each I/O operation takes 10 milliseconds to
complete. Also assume that the context switching overhead is 0.1millisecond and that all
processes are long-running tasks.
Q52. What is the CPU utilization (in %) for a round-robin scheduler when the time quantum
is 1 millisecond__________

Q53. What is the CPU utilization (in %) for a round-robin scheduler when the time quantum
is 10 millisecond__________

For next two questions, there are three independent jobs. They need 10 sec, 15 sec and 20 sec
CPU time, respectively, and during their executions each of them spends half a minute
waiting for I/O. Compute
Q54. The minimal overall runtime (in sec) of these jobs when they are processed in a
uniprogrammed system___________
Q55. The minimal overall runtime (in sec) of these jobs when they are processed in a multi
programmed system___________
Q56. Consider the following code
int main() {
printf("a");
fork();
printf("b");
return 0;
}
How many output(s) is (are) possible of the above code?____________
Q57. Consider the following code
int main(){
fork();
printf("a");
fork();
printf("b");
return 0;
}
How many output(s) is (are) possible of the above code?_______________
OS Gate-2020 Page 13
Q58. Consider the following code
int main(){
if(fork() == 0){
printf("a");
}
else {
fork();
printf("b");
}
return 0;
}
How many output(s) is (are) possible of the above code?_____________

Q59. Consider the following code

void main(){
fork();
int pid=fork();
if(pid==0){
fork();
}
exit();
}
How many processes are created upon the execution of this program?_____________

Short notes

OS Gate-2020 Page 14
OS Gate-2020 Page 15
 PROCESS SYNCHRONIZATION

Q1. Consider a process that uses a user level threading library to spawn 10 user level
threads. The library maps these 10 threads on to 2 kernel threads. The process is
executing on a 8-core system. What is the maximum number of threads of a process
that can be executing in parallel? _____________

Q2. Consider a user level threading library that multiplexes N > 1 user level threads over
M ≥ 1 kernel threads. The library manages the concurrent scheduling of the multiple
user threads that map to the same kernel thread internally, and the programmer using
the library has no visibility or control on this scheduling or on the mapping between
user threads and kernel threads. The N user level threads all access and update a
shared data structure. When (or, under what conditions) should the user level threads
use mutexes to guarantee the consistency of the shared data structure?
(a) Only if M > 1.
(b) Only if N ≥ M.
(c) Only if the M kernel threads can run in parallel on a multi-core machine.
(d) User level threads should always use mutexes to protect shared data.
Q3. Consider two concurrent processes, modifying a shared variable :
shared integer total = 0;
Process A Process B
for(i = 1; i<=3; i++) for (j = 1; j<=3; j++)
total = total + 1; total = total + 1;
Assume that total must be loaded into a register before being incremented, and then is
written back afterwards. What are all the possible values that total can have when both
processes complete?
(a) 3 and 6 only (b) 3 and 4 only (b) 4, 5 and 6 only (d) 3, 4, 5 and 6 only
Q4. Assume that following code is executed by the three processes P1, P2and P3 running
simultaneously on a uni-processor system.
int z = 0; // global variable, shared among processes
void update (int x, int y) {
z = x + y;
}
The following assembly code that implements the function update().
load R1, x;
load R2, y;
add R3, R1, R2;
store R3, z;

OS Gate-2020 Page 16
 If P1 calls update (1, 2), P2 calls update (2, 3) and P3 call update (3, 4), How many
values of z is possible after all three processes completes the execution of
update?__________

Q5. Consider the following two concurrent processes running on a uni-processor system
modifying a shared variable:
shared integer x=10;
P1: P2:
x = 10; x = 10;
while (1) { while (1) {
x = x – 1; x = x - 1;
x = x + 1; x = x + 1;
if (x != 10) if (x != 10)
printf(“x is %d”,x); printf(“x is %d”,x);
} }
Consider the following statements:
1. x is 10 2. x is 9 3. x is 8
Which of the above statements is/are possible in the output of the above processes?
(a) 2 and 3 only
(b) 1 and 2 only
(c) 1 and 3 only
(d) All the above

Q6. Consider the following concurrent process P1 and P2 have two semaphores, „mutex‟
and „signal‟:
Process 1 Process 2
P(mutex); P(mutex);
if (x > 0) x++;
V(signal); V(signal);
V(mutex); V(mutex);
P(signal);
We want „mutex‟ to provide mutual exclusion among the two processes, and for
„signal‟ to provide a way for process 2 to activate process 1 when „x‟ is greater than 0.
What should the initial values of „mutex‟ and „signal‟ semaphore respectively?
(Assume that „x‟ is always positive or zero, and that there are only these two processes
in the system).
(a) 0, 0
(b) 0, 1
(c) 1, 0
(d) 1, 1

OS Gate-2020 Page 17
Q7. Consider the two processes P1 and P2 start concurrently:
P1: P2:
P(s1); print("1");
print("a"); V(s1);
V(s2); P(s2);
print("b"); print("2");
Assume that all semaphores initialized to 0 then which of the following is/are the
possible outputs of above two processes?
i) 1ab2 ii) 1a2b
iii) 12 iv) ab12
(a) i and ii only (b) ii only
(c) iii and iv only (d) none of the above

Q8. Consider the two processes P1 and P2 start concurrently:

P1: P2:
p(s1); v(s1);
print("a"); p(s1);
print("b”); print("1");
v(s2); print("2");
v(s1); p(s2);
Assume that all semaphores initialized to 0 then which of the following is/are the
possible outputs of above two processes?
i) 1ab2 ii) 1a2b
iii) 12 iv) ab12
(a) i and ii only (b) ii only
(c) iii and iv only (d) none of the above

Q9. Consider the two processes P1 and P2 start concurrently:

P1: P2:
p(s1); print("1");
print("a"); p(s2);
v(s2); v(s1);
print("b"); print("2");
Assume that all semaphores initialized to 0 then which of the following is/are the
possible outputs of above two processes?
i) 1ab2 ii) 1a2b
iii) 12 iv) ab12
(a) i and ii only (b) ii only
(c) iii and iv only (d) none of the above

OS Gate-2020 Page 18
Q10. Suppose there are three processes P, Q and R. Each has some sequential code sections
represented as function calls and then updates a shared variable count, as shown in the
below table.
P Q R
while(1){ while(1){ while(1){
PS1( ); QS1( ); RS1( );
PS2( ); QS2( ); RS2( );
Count = count + 3; Count = count - 2; Count = count + 5;
} } }
Assume that there is the following dependency exists between function calls:
 RS1() is executed after QS1()which is executed after PS1(),
 QS2() is executed after RS1()
 PS2() and RS2() are executed after QS2()
 PS1() is executed after PS2() and RS2()
Minimum how many counting and binary semaphores are required to solve the
coordination and the critical section problem.
(a)3,4 (b)4,3 (c)4,5 (d)4,6

For next three questions, The following three concurrent processes share two semaphores
initialized as follows:
Semaphore S1 = 3;
Semaphore S2 = 0;
P1: P2: P3:
While(true){ While(true){ While(true){
Wait(S1); Wait(S2); Wait(S2);
Print(„C‟); Print(„A‟); Print(„D‟);
Signal(S2); Print(„B‟); }
} Signal(S2);
}
Q11. Assuming execution is eventually halted, how many C‟s are printed when the set of
processes runs?___________

Q12. What is the smallest number of A‟s that might be printed when this set of processes
runs?________

Q13. Which one is not possible output sequence when this set of processes runs?
(a) CABABDCABABDCD (b) CABDCABDCDAB
(c) CDCABDCABABD (d) CABABDCABCABDD

OS Gate-2020 Page 19
Q14. Suppose a program has three threads Thread1, Thread2, and Thread3, and a shared
counter, count, as shown below:
int count = 10;
semaphore Lock = 1;
Thread 1( ) Thread 2( ) Thread 3( )
{ { {
Wait(Lock); Wait(Lock); Wait(Lock);
Count ++; Count --; Printf(“%d”, Count);
Signal(Lock); Signal(Lock); Signal(Lock);
} } }
Which one of the following is not possible output of this program?
(a) 11 (b) 10 (c) 9 (d) 8

Q15. Consider two threads A and B that perform two operations each. Let the operations of
thread A be A1 and A2; let the operations of thread B be B1 and B2. We require that
threads A and B each perform their first operation before either can proceed to the
second operation. That is, we require that A1 be run before B2 and B1 before A2.
Consider the following solutions based on semaphores for this problem (the code run
by threads A and B is shown in two columns next to each other). Which of the
following solution is/are correct?
(a)

(b)

(c)

(d) Both (b) and (c)

OS Gate-2020 Page 20
Q16. Consider the following code for critical section problem:
shared boolean flag[2];
flag[0] = flag[1] = FALSE;
Process Pi:
do{
flag[i] = TRUE;
turn = i;
while (flag[j] && turn == j);
<critical section>
flag[i] = FALSE;
<remainder section>
}while (TRUE);
Consider the following statements:
1. It ensures mutual exclusion between the processes.
2. It is free from starvation.
3. It is free from deadlock.
Which of the above is/are true regarding to above code?
(a) 1 only (b) 2 and 3 only (c) 3 only (d) All the above

Q17. Consider the following code for critical section problem:

shared boolean flag[2];
flag[0] = flag[1] = FALSE;
process(int i){
while (TRUE) {
while (flag[(i+1) mod 2] == TRUE);
flag[i] = TRUE;
critical_section;
flag[i] = FALSE;
}
}
Consider the following statements:
1. It ensures mutual exclusion between the processes.
2. It ensures bounded wait between the processes.
3. It ensures progress between the processes.
Which of the above is/are true regarding to above code?
(a) 1 only (b) 2 and 3 only
(c) 3 only (d) All the above

OS Gate-2020 Page 21
Q18. Consider the following code for critical section problem:
int turn = 0;
bool flag[0] = false;
bool flag[1] = false;
enter(int id) {
flag[id] = true;
turn = id;
while(turn == id && flag[1 - id] == true);
}
Critical section;
exit(int id) {
flag[id] = false;
}
Consider the following statements:
1. It ensures mutual exclusion between the processes.
2. It ensures bounded wait between the processes.
3. It ensures progress between the processes.
Which of the above is/are true regarding to above code?
(a) 1 only (b) 2 and 3 only (c) 3 only (d) All the above

Q19. Consider the following code critical section problem:

boolean flag[2]; /* initially false */
int turn;
Process Pi:
do {
flag[i] = true;
while (flag[j]) {
if (turn == j) {
flag[i] = false;
while (turn == j);
flag[i] = true;
}
}
/* critical section */
turn = j;
flag[i] = false;
/* remainder section */
} while (true);
Consider the following statements:

OS Gate-2020 Page 22
 1. It ensures mutual exclusion between the processes.
2. It ensures bounded wait between the processes.
3. It ensures progress between the processes.
Which of the above is/are true regarding to above code?
(a) 1 only (b) 2 and 3 only (c) 3 only (d) All the above

Q20. Shared Boolean choosing [N]=false;

shared int number [N]=0;
int mypid =0;
int jj;
Choosing [mypid]=true;
number [mypid]= MAX(number)+1;
Choosing [mypid]=false;
for (jj=0;jj<N; jj=jj+1)
{
while (choosing [jj])
Donothing( );
While (number [jj]!=0 &&((number[jj]<number[mypid])
||(number [jj] = = number [mypid]&&gg<mypid))
Donothing( );
}
//critical section
number[mypid]=0;
_________________________________
Q21. Consider the following code for n-process critical section problem:
enum pstate {idle, want_in, in_cs};
pstate flag[n];
int turn;
/* All the elements of flag are initially idle.
The initial value of turn is immaterial (between 0 and n-1)*/
Process Pi:
do {
while (true) {
flag[i] = want_in;
j = turn;
while (j != i) {
if (flag[j] != idle) j = turn;
else j = (j + 1) % n;
}
flag[i] = in_cs;
j = 0;
while ((j < n) && (j == i || flag[j] != in_cs)) j++;
if ((j >= n) && (turn == i || flag[turn] == idle)) break;

OS Gate-2020 Page 23
 }
/* critical section */
j = (turn + 1) % n;
while (flag[j] == idle)
j = (j + 1) % n;
turn = j;
flag[i] = idle;
/* remainder section */
} while (true);
Consider the following statements:
1. It ensures mutual exclusion between the processes.
2. It ensures bounded wait between the processes.
3. It ensures progress between the processes.
Which of the above is/are true regarding to above code?
(a) 1 only (b) 2 and 3 only (c) 3 only (d) All the above
Q22. Consider the following implementation of a general (counting) semaphore. This
implementation assumes the existence of binary semaphore operations waitb and
signalb implemented with a test-and-set instruction.
void wait(S : semaphore){ void signal(S : semaphore){
waitb(mutex) waitb(mutex)
S = S - 1 S = S + 1
if(S < 0) { if(S ≤ 0)
signalb(mutex) signalb(delay)
waitb(delay) else
} signalb(mutex)
signalb(mutex) }
}
For which of the following scheduling policies, will the above code yield a correct
implementation of a semaphore?
(i) First-Come-First-Served (ii) Pre-emptive Shortest-Job-First
(iii) Pre-emptive Priority (iv) Round-Robin
(a) i only (b) ii and iii only
(c) iii and iv only (d) ii, iii and iv only
Q23. Assume this attempted non-atomic implementation of a lock:
void init(lock_t *mutex) { mutex->flag = 0;}
void lock(lock_t *mutex) {
while (mutex->flag == 1) ;
mutex->flag = 1;
}
void unlock(lock_t *mutex) {
mutex->flag = 0;
}

OS Gate-2020 Page 24
 Assume 5 processes are competing for this lock. How many processes can possibly
acquire the lock?
(a) 1 (b) 2 (c) 4 (d) 5

Q24. Assume this attempted implementation of a lock:

typedef struct __lock_t{
int ticket, turn;
} lock_t;

void lock_init(lock_t *lock){

lock->ticket = 0;
lock->turn = 0;
}
void lock(lock_t *lock){
int myturn = FetchAndAdd(&lock->ticket);
while (lock->turn != myturn);
}
void unlock(lock_t *lock) {
lock->turn = lock->turn + 1;
}
FetchAndAdd(X) is an atomic Read-Modify-Write instruction that reads the value of
memory location X, increments it by the value 1, and returns the old value
of X. Assuming a maximum of 5 processes in the system, what values of lock->ticket
and lock->turn are possible?
1. ticket=0 and turn=0
2. ticket=0 and turn=1
3. ticket=1 and turn=0
4. ticket=5 and turn=5
(a) 1 and 3 only (b) 2 and 3 only
(c) 1, 3 and 4 only (d) 3 and 4 only

Q25. A lock_ acquire() usually implemented with a test-and-set instruction as follows:

void lock_ acquire(){
while (test-and-set(&lock->held)==1);
}
The test-and-set() returns the old value at the address while atomically setting it to 1.
Now a new lock_acquire() is implemented as follows:

OS Gate-2020 Page 25
 void lock_ acquire(){
while (1) {
while (lock->held > 0) ;
if (test-and-set(&lock->held) == 0)
break;
}

Which of the following is true about given lock implementation?

(a) fails as lock can overflow
(b) fails as lock 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

Q26. Consider the following lock implementation:

int lock=0;
void acquire (lock) {
while (test­and­set(&lock));
}
void release (lock){
lock = 0;
}
The test-and-set() returns the old value at the address while atomically setting it to 1.
Which of the following is true about given lock implementation?
(a) It works on single-core machines because it disables context switches within critical
region
(b) It works on single-core machines even when there are context switches within
critical region
(c) It does not work on single core CPU
(d) It does not work on multi-core CPU

Q27. Consider the following lock implementation:

void acquire (lock) {
disable interrupts;
}
void release (lock) {
enable interrupts;
}
Which of the following is true about given lock implementation?
1. It works on single-core machines because it disables context switches within critical
region
OS Gate-2020 Page 26
 2. It works on single-core machines even when there are context switches within
critical region
3. It does not work on single core CPU
4. It does not work on multi-core CPU
(a) 1 only (b) 2 and 3 only
(c) 1 and 4 only (d) 2 and 4 only

Q28. Consider the following code for reader/writer problem. (Recall the problem is that
there can be multiple threads executing reader/writer functions, and you should allow
multiple readers to read concurrently, but when a writer executes, no other reader or
writer threads should execute.)
int readcount = 0;
Semaphore mutex = 1;
Semaphore w_or_r = 1;
Reader() Writer()
1. { 1. {
2. P(mutex); 2. P(w_or_r);
3. readcount++; 3. Write;
4. ________________ 4. V(w_or_r);
5. ________________ 5. }
6. ________________

7. /*Perform Reading*/

8. P(mutex);
9. readcount--;
10. if(readcount == 0)
11. V(w_or_r);
12. V(mutex);
13. }
There are some set of statements are missing from the code. Which of the following is
the correct set of statements for which the above code works correctly?
(a) if(readcount == 0) (b) if(readcount == 1)
P(w_or_r); V(mutex);
V(mutex); P(w_or_r);

(c) if(readcount == 0) (d) if(readcount == 1)

V(mutex); P(w_or_r);
P(w_or_r); V(mutex);

OS Gate-2020 Page 27
Q29. Several processes wish to read and write data shared between them. Some processes
only want to read, while others want to update the shared data. Multiple readers may
concurrently access the data. However, a writer must not access the data concurrently
with anyone else, either a reader or a writer. Consider the solution that use functions
readLock(), readUnlock(), writeLock(), and writeUnlock(), which are invoked by the
readers and writers to realize read/write locks
Ininilazation:
Semaphore mutex = 1;
Boolean variable writer_present;
Two condition variables reader_can_enter, writer_can_enter;
Reader: Writer:
readLock(){ writeLock(){
lock(mutex) lock(mutex)
while(writer_present) while(read_count > 0 || writer_present)
wait(reader_can_enter) wait(writer_can_enter)
read_count++ writer_present = true
unlock(mutex) unlock(mutex)
} }

//perform reading //perform writing

readUnlock(){ writeUnlock():
lock(mutex) lock(mutex)
read_count-- writer_present = false
if(read_count==0) signal(writer_can_enter)
signal(writer_can_enter) signal(reader_can_enter)
unlock(mutex) unlock(mutex)
} }
Which of the below statement is true, regarding synchronizing the classical readers and
writers?
(a) The above solution is correct, and it is properly synchronizing the readers and
writers.
(b) Both reader and writers will enter into data base at the same time.
(c) It is possible for deadlock.
(d) Both (b) and (c) are true

Q30. Consider the famous dining philosophers‟ problem. N philosophers are sitting around
a table with N forks between them. Each philosopher must pick up both forks on her
left and right before she can start eating. If each philosopher first picks the fork on her
left (or right), then all will deadlock while waiting for the other fork. The goal is to

OS Gate-2020 Page 28
 come up with an algorithm that lets all philosophers eat, without deadlock or
starvation. Consider a solution to this problem using condition variables. In this
solution a variable state is associated with each philosopher, and can be one of EATING
(holding both forks) or THINKING (when not eating). Further, a condition variable
condvar is associated with each philosopher to make them sleep and wake them up
when needed. Each philosopher must call the pickup() function before eating, and
putdown() function when done. Both these functions use a mutex to change states only
when both forks are available.
bothForksFree(i):
return (state[leftNbr(i)] != EATING &&
state[rightNbr(i)] != EATING)
pickup(i):
lock(mutex)
while(!bothForksFree(i))
wait(condvar[i])
state[i] = EATING
unlock(mutex)
putdown(i):
lock(mutex)
state[i] = THINKING
if(bothForksFree(leftNbr(i)))
signal(leftNbr(i))
if(bothForksFree(rightNbr(i)))
signal(rightNbr(i))
unlock(mutex)
Which of the below statement is true, regarding synchronizing the classical
philosophers problem?
(a) The above solution is correct, and it is properly synchronizing the philosophers.
(b) It is possible for starvation.
(c) It is possible for deadlock.
(d) Both (b) and (c) are true.
Q31. Consider a clinic with one doctor and a very large waiting room (of infinite capacity).
Any patient entering the clinic will wait in the waiting room until the doctor is free to
see her. Similarly, the doctor also waits for a patient to arrive to treat. All
communication between the patients and the doctor happens via a shared memory
buffer. Any of the several patient processes, or the doctor process can write to it. Once
the patient “enters the doctors office”, she conveys her symptoms to the doctor using a
call to consultDoctor(), which updates the shared memory with the patient‟s symptoms.
The doctor then calls treatPatient() to access the buffer and update it with details of the

OS Gate-2020 Page 29
 treatment. Finally, the patient process must call noteTreatment() to see the updated
treatment details in the shared buffer, before leaving the doctor‟s office. Your code
should ensure that no race conditions occur due to several patients overwriting the
shared buffer concurrently. Similarly, you must ensure that the doctor accesses the
buffer only when there is valid new patient information in it, and the patient sees the
treatment only after the doctor has written it to the buffer. Consider a code to correctly
synchronize between the patient and the doctor processes.
Initial Semaphores variables:
pt_waiting = 0
treatment_done = 0
doc_avlbl = 1
Patient process: Doctor:
down(doc_avlbl) while(1) {
consultDoctor() down(pt_waiting)
up(pt_waiting) treatPatient()
down(treatment_done) up(treatment_done)
noteTreatment() }
up(doc_avlbl)

Which of the below statement is true, regarding synchronizing the patient and the
doctor processes?
(a) The above solution is correct, and it is properly synchronizing the patient and the
doctor processes.
(b) The above solution is incorrect, because race conditions occur due to several
patients overwriting the shared buffer concurrently
(c) The above solution is incorrect, because doctor accesses the buffer when there is no
valid new patient information in it.
(d) The above solution is incorrect, because patient sees the treatment before the doctor
has written it to the buffer

Q32. Consider a producer-consumer situation, where a process P produces an integer using

the function produceNext() and sends it to process C. Process C receives the integer
from P and consumes it in the function consumeNext(). After consuming this integer, C
must let P know, and P must produce the next integer only after learning that C has
consumed the earlier one. Assume that P and C get a pointer to a shared memory
segment of 8 bytes, that can store any two 4-byte integer-sized fields, as shown below.
Both fields in the shared memory structure are zeroed out initially. P and C can read or

OS Gate-2020 Page 30
 write from it, just as they would with any other data object. Consider a code to
correctly synchronize between the producer and the consumer processes.
struct shmem_structure {
int field1;
int field2;
};
Producer: Consumer:
struct shmem_structure *shptr = struct shmem_structure *shptr =
get_shared_memory_structure(); get_shared_memory_structure();
while(1) { while(1) {
int produced = produceNext(); int consumed;
shptr->field1=produced; while(shptr->field2 == 0);
shptr->field2 = 1; consumed=shptr->field1;
while(shptr->field2 == 1); consumeNext(consumed);
} shptr->field2 = 0;
}
Which of the below statement is true, regarding synchronizing between producer and
the consumer processes?
(a) The above solution is correct, and it is properly synchronizing the producer and the
consumer processes.
(b) The above solution is incorrect, because the producer can produce the second
integer before consumer consumes the first integer.
(c) The above solution is incorrect, because the consumer tries to consume integer
before producer produce the integer.
(d) None of the above.

Q33. Three processes P1, P2, and P3 have priorities P1=1, P2=5, P3=10. (“10” is higher
priority than “1”.) The processes execute the following code:

OS Gate-2020 Page 31
 The X and Y locks are initialized to “unlocked”, i.e., they are free. <code sequence A>
takes 2 time units to execute, <code sequence B> takes 3 time units to execute, and
<critical section CS> takes 4 time units to execute. Assume lock() and unlock() are
instantaneous, and that context switching is also instantaneous. P1 begins executing at
time 0, P2 at time 3, and P3 at time 10. There is only one CPU shared by all processes.
Assume that the scheduler uses a priority scheduling policy: at any time, the highest
priority process that is ready (runnable and not waiting for a lock) will run. If a process
with a higher priority than the currently running process becomes ready, preemption
will occur and the higher priority process will start running. What is the Average
turnaround time of all three process?_____

Short notes

OS Gate-2020 Page 32
OS Gate-2020 Page 33
 DEADLOCK

Q1. There are four conditions that are necessary for deadlock to occur: mutual exclusion,
hold and wait, no preemption, and circular wait. With deadlock prevention, the system
ensures that deadlock does not occur by preventing one of these conditions from
holding. Match each of the following techniques with the one deadlock condition that
it prevents.
Techniques Deadlock Condition
1. Impose a total ordering (or ranking) on how resources a. Mutual exclusion
are acquired
2. When a process requests a resource that is already held, b. Hold and wait
force the process holding the resource to release it
3. Only allow a process to request a resource when the c. No preemption
process has none
4. Allow all processes to access the resource d. Circular wait
simultaneously
5. Require each process to grab all desired resources at
once
Codes:
1 2 3 4 5
(a) d c b a b
(b) d b c a b
(c) c a d a b
(d) d c b b a
Q2. Which of the following code segments lead to deadlock of process 0 and process 1?
(1) Process 0: Process 1:
[Link](); [Link]();
[Link](); [Link]();
[Link](); [Link]();
[Link](); [Link]();

(2) Process 0: Process 1:

[Link](); [Link]();
[Link](); [Link]();
[Link](); [Link]();
[Link](); [Link]();

(3) Process 0: Process 1:

[Link](); [Link]();
[Link](); [Link]();
[Link](); [Link]();
[Link](); [Link]();
(a) 1 only (b) 2 and 3 only (c) 2 only (d) 1 and 3 only

OS Gate-2020 Page 34
Q3. 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.
Q4. Which of the following will NOT guarantee that deadlock is avoided?
(a) Acquire all resources (locks) all at once, atomically
(b) Use locks sparingly
(c) Acquire resources (locks) in a fixed order
(d) Be willing to release a held lock if another lock you want is held, and then try the
whole thing over again
Q5. Consider the following resource allocation policy:
Requests for and releases of resources are allowed at any time. If a request for resources
cannot be satisfied because the resources are not available, then we check any processes
that are blocked, waiting for resources. If they have the desired resources, then these
resources are taken away from them and are given to the requesting process. The
vector of resources for which the waiting process is waiting is increased to include the
resources that were taken away. If the resources needed by a blocked process become
available, the process is put back on the ready queue. For example, consider a system
with three resource types and the vector Available initialized to (4, 2, 2).
 If process P0 asks for (2,2,1), it gets them.
 If P1 asks for (1,0,1), it gets them.
 Then, if P0 asks for (0,0,1), it is blocked (resource not available).
 If P2 now asks for (2,0,0), it gets the available one (1,0,0) and one that was allocated
to P0 (since P0 is blocked). P0‟s Allocation vector goes down to (1,2,1), and its Need
vector goes up to (1,0,1).
With this resource allocation policy, can deadlock occur?
(a) No, because hold and wait is violated.
(b) No, because circular wait is violated.
(c) No, because no pre-emption is violated.
(d) There can be deadlock
Q6. Suppose here are n processes in the system and each one needs k instances of a
resources to complete. What would be the minimum number of resources that you
should keep in the system to ensure no deadlock in the system?
(a) n*k (b)n*k-n+1 (c)n*k+1 (d)n*k*k

OS Gate-2020 Page 35
Q7. A system has eight tape drives {a, b, c, d, e, f, g, h}, with n processes competing for
them. Each process may need three of the drives. For what maximum values of n is the
system deadlock free? __________

Q8. Consider a system having m resources of the same type. These resources are shared by
3 processes A, B and C which have peak demands of 3, 4 and 6 respectively. For what
minimum value of m deadlock will not occur? _________
Q9. Consider a system with m resources of same type being shared by n processes.
Resources can be requested and released by processes only one at a time. The system is
deadlock free if and only if
(a) The sum of all max needs is < m + n (b) The sum of all max needs is > m + n
(c) Both of above (d) None of the mention

Q10. Which of the following resource allocation graph represents deadlock?

(a) i and ii only (b) iii and iv only

(c) i and iv only (d) ii, iii and iv only

Q11. A system has four processes P1 through P4 and two resource types R1 and R2. It has 2
units of R1 and 3 units of R2. Given that:
• P1 requests 2 units of R2 and 1 unit of R1,
• P2 holds 2 units of R1 and 1 unit of R2,
• P3 holds 1 unit of R2,
• P4 requests 1 unit of R1
Which of the following statement is correct?
(a) System is in unsafe state both processes P1 and P2 are involved in deadlock.
(b) System is in unsafe state both processes P3 and P4 are involved in deadlock.
(c) System is in safe state with the safe sequence P1, P4, P2, P3.
(d) System is in safe state with the safe sequence P2, P4, P3, P1.

OS Gate-2020 Page 36
Q12. A system has five processes P1 through P5 and four resource types R1 through R4.
There are 2 units of each resource type. Given that:
• P1 holds 1 unit of R1 and requests 1 unit of R4
• P2 holds 1 unit of R3 and requests 1 unit of R2
• P3 holds one unit of R2 and requests 1 unit of R3
• P4 requests 1 unit of R4
• P5 holds one unit of R3 and 1 unit of R2, and requests 1 unit of R3
Which of the following statement is correct?
(a) System is in unsafe state both processes P2, P3 and P5 are involved in deadlock.
(b) System is in unsafe state both processes P3 and P5 are involved in deadlock.
(c) System is in safe state with the safe sequence P1, P4, P2, P3, P5.
(d) System is in safe state with the safe sequence P2, P4, P5, P3, P1.

Q13. Consider the following three scenario of process execution:

(I) System has more than two processes which access three resources R1, R2, and R3 in
any order and process can hold any number of resources. Each of the resources R1, R2
and R3 has an associated semaphore S1, S2, and S3respectively. To access a resource
Ri, each process first calls P(Si); the process calls V(Si) when finished.
(II) System has more than two processes which access three resources R1, R2, and R3 in
any order and process can hold only one of the resources. Each of the resources R1, R2
and R3 has an associated semaphore S1, S2, and S3respectively. To access a resource
Ri, each process first calls P(Si); the process calls V(Si) when finished.
(III) System has more than two processes which access three resources R1, R2, and R3
in ascending order and process can hold any number of resources. Each of the
resources R1, R2 and R3 has an associated semaphore S1, S2, and S3respectively. To
access a resource Ri, each process first calls P(Si); the process calls V(Si) when finished.
In which of the above scenario deadlock is possible?
(a) I only (b) I and II only (c) II and III only (d) All the above

For the next two questions, consider a system that has 5 process and 3 resources (A, B, C).
The maximum counts of resources are (10, 5, 7). Consider the following table of resource
allocation.

OS Gate-2020 Page 37
Q14. Which one these is a safe sequence?
(a) P2, P4, P3, P1, P0 only (b) P1, P3, P4, P0, P2 only
(c) Both a and b (d) None are safe sequences

Q15. How many safe sequences are possible? ____________

For the next two questions, consider a system that has 5 process and 3 resources (A, B, C).
The maximum counts of resources are (11, 7, 7). Consider the following table of resource
allocation.

Q16. The system is currently in unsafe state. But some processes may finish their execution.
How many processes can complete their execution?____________

Q17. How could the state be made safe again?

(a) Process 2 could finish without using more than its current allocation.
(b) Process 3 could finish without using more than its current allocation.
(c) Process 0 could request (1, 1, 1), be granted this request, and the resulting state
would be safe.
(d) Process 3 could request (1, 0, 0), be granted this request, and the resulting state
would be safe.

Q18. Consider a system with three processes and three resource types. The following table
gives, for each process, how many of each resource is currently allocated to it and what
its maximum total need is for each resources type.
Processes Allocated Maximum
A B C A B C
P0 1 1 1 2 1 2
P1 1 1 0 3 3 3
P2 1 2 1 4 3 3
Suppose that the number of available (unallocated) resources for each type is 1 1 x.
What is the minimum value of x for which this is a safe state?________

For the next two questions, consider a system that has 5 process and 4 resources (A, B, C, D).
The maximum counts of resources are (6, 7, 14, 12). Consider the following table of resource
allocation.

OS Gate-2020 Page 38
Processes Allocated Maximum
A B C D A B C D
P1 0 0 1 2 0 0 3 2
P2 2 0 0 0 2 7 5 0
P3 0 0 3 4 6 6 5 6
P4 2 3 5 4 4 3 5 6
P5 0 3 3 2 0 6 5 2
Q19. Which one these is a safe sequence?
(a) P1, P4, P5, P2, P3. (b) P1, P4, P2, P5, P3
(c) P1, P4, P2, P3, P5 (d) system is not in safe sequence

Q20. Consider the two independent request form process P2 and P3

R1: Request from a process P3 arrives for (0, 4, 2, 0)
R2: Request from a process P2 arrives for (0, 1, 2, 0)
Which of the two requests is granted by the OS?
(a) R1 (b) R2 (c) both R1 and R2 (d) neither R1 and nor R2
Q21. Consider a system containing with two types of resources R and S. Total available
instance of R and S are 12 and 24 units respectively. The current allocation and Max
requirement of the resources are as follows
Process Current Allocation Max Requirement
R S R S
P1 0 4 0 12
P2 8 0 8 15
P3 0 8 8 20
What is the largest number of instances of S that P1 can request at this point that the
banker algorithm will grant? ___________

Short notes

OS Gate-2020 Page 39
OS Gate-2020 Page 40
 MEMORY MANAGEMENT

For next four questions, consider a swapping system in which memory consists of the
following holes size in order: 15K, 5K, 20K, 4K, 17K and 7K.
Q1. Which hole is taken for successive segment requests of 12K, 7K, 15K and 5K (in order)
for first fit?
(a) 15K, 20K, 17K, 5K (b) 15K, 7K, 17K, 5K
(c) 20K, 17K, 15K, 7K (d) 15K, 20K, 17K, 7K

Q2. Which hole is taken for successive segment requests of 12K, 7K, 15K and 5K (in order)
for best fit?
(a) 15K, 20K, 17K, 5K (b) 15K, 7K, 17K, 5K
(c) 20K, 17K, 15K, 7K (d) 15K, 20K, 17K, 7K

Q3. Which hole is taken for successive segment requests of 12K, 7K, 15K and 5K (in order)
for worst fit?
(a) 15K, 20K, 17K, 5K (b) 15K, 7K, 17K, 5K
(c) 20K, 17K, 15K, 7K (d) 15K, 20K, 17K, 7K

Q4. Which hole is taken for successive segment requests of 12K, 7K, 15K and 5K (in order)
for next fit?
(a) 15K, 20K, 17K, 5K (b) 15K, 7K, 17K, 5K
(c) 20K, 17K, 15K, 7K (d) 15K, 20K, 17K, 7K

Q5. One advantage of multiple fixed partitions (MFP) over variable partitions is:
(a) MFP never leads to unusably small holes due to external fragmentation.
(b) There is no need to pre-allocate partitions.
(c) Sharing memory is much easier.
(d) MFP will usually result in much more efficient use of system memory.

Q6. Assume that an OS uses a linked list to keep track of the memory usage in the system,
and each item in the list indicates whether the corresponding region of the memory is
occupied. Which one of the following dynamic memory allocation methods will quickly
lead to many small holes in memory?
(a) Best fit (b) First fit (c) Worst fit (d) Next fit

Q7. In a conventional paging system, a page table entry (PTE) will not contain:
(a) A logical page number.
(b) A physical page frame number.
(c) A page residence bit.
(d) Page permissions.

OS Gate-2020 Page 41
Q8. A system with 32-bit addresses, 1 GB main memory, and a 1 megabyte (20-bit) page size
will have a page table that contains:
(a) 4,096 entries. (b) 4,294,967,296 entries.
(c) 1,048,576 entries. (d) 1,024 entries.

Q9. Large page sizes increase:

(a) Internal fragmentation. (b) External fragmentation.
(c) The page table size. (d) The working set size.

Q10. Some systems try to eliminate external fragmentation by compaction. Suppose a

computer with 2MB of user memory compacts once every second. If it takes 0.1
microseconds to copy one byte, and the average size of hole is 30 percent of the average
size of process, what fraction of the total CPU time (in %) is used up on compaction?
You may also assume that there are half as many holes as processes in memory, and that
all process images must be moved. __Round off to two decimal places)

For next five questions, suppose that the virtual address space is 16 Mbytes, the physical
memory is 128 Kbytes, and the page/frame size is 2 Kbytes. The number of bit for:
Q11. Virtual address is ___________

Q12. Physical address is __________

Q13. Offset is __________
Q14. Page number is___________
Q15. Frame number is_________

For the next ten questions, consider a non-contiguous memory allocation scheme in which a
logical memory address is represented using 32 bits. Of these bits, the high-order 12 bits
represent the page number; the remaining bits represent the page offset.
Q16. What is the total logical memory space i.e., how many bytes are addressed?________

Q17. How many pages are there?_________

Q18. What is the page size in bytes?_______
Q19. What is the frame size in bytes?_____
Q20. If a process requires 78,901,234 bytes of memory, how many pages will it require?___
Q21. How many bytes are unused due to external fragmentation?________
Q22. How many bytes are unused due to internal fragmentation?_______
Q23. Given that the page table is stored entirely in memory and a memory reference takes
100 nanoseconds, how long does a paged memory reference take?____ nanoseconds.
OS Gate-2020 Page 42
Q24. Adding a translation look-aside buffer (TLB) with a TLB access time of 15 nanoseconds,
how long does a paged memory reference take if a TLB hit occurs?______ nanoseconds.

Q25. Given a TLB hit ratio of 84%, what is the effective memory access time
(EMAT)?____nanoseconds.

For next two questions, A system implements a paged virtual address space for each process
using a one-level page table. The maximum size of virtual address space is 16MB. The page
table for the running process includes the following valid entries (the → notation indicates that
a virtual page maps to the given page frame, that is, it is located in that frame):
Virtual page 2 → page frame 4
Virtual page 4 → page frame 9
Virtual page 1 → page frame 2
Virtual page 3 → page frame 16
Virtual page 0 → page frame 1
The page size is 1024 bytes and the maximum physical memory size of the machine is

Q26. To which physical address wills the virtual address (1524)10 translate? (_____)10

Q27. Which virtual address will translate to physical address 102410? (_____)10

For the next four questions, consider a system with 64K virtual pages. The OS operating
system uses two-level pages tables to support 2GB virtual address spaces by dividing the
virtual address into a 64K offset and two 8-bit first- and second-level page table indices. Given
the virtual address 0x7f001000,
Q28. The virtual page number is (________)10

Q29. The offset is (_______)10

Q30. The first level page table indices is (_______)10

Q31. The second level page table indices is (________)10
Q32. Consider a 32-bit computer with 2-level address translation; page directory, page tables,
and pages are all 4KB in size. How much total memory (in KB) will be used by the page
directory and page table(s) of a process that has the minimum amount of address space
mapped for the following addresses to be valid: 0x01234000, 0x01235678, 0x01234567,
0xDEADBEEF?
(a) 8KB (b) 12KB (c) 16KB (d) 20KB

Q33. Consider the theoretical computer architecture with 50-bit virtual addresses and 16KB
pages. What is the maximum number of levels of page tables that could be used in the
virtual memory system if PTE size is 4 bytes and all page tables fits into single
page._____________

OS Gate-2020 Page 43
Q34. Consider a 32-bit system with 4K pages uses multi-level page tables :
10 bits for the first-level index, 10 bits for the second-level index, 12-bit offset.
(Assume that page table entries (PTEs) are 32-bits) If a process has 10 contiguous code
pages (including global variables), 4 contiguous heap pages, and a single 1 page stack.
What are the minimum number and maximum number of pages required for the
process‟s page table respectively?
(a) 2, 4 (b) 2, 6 (c) 4, 4 (d) 4, 6

For the next two questions, consider page table design is called inverted page table (IPT). In
an IPT, the number of entries equals to the number of physical frames in memory. Each entry
in IPT contains the physical frame number, virtual page number, and 2-other bits such as
Valid and Modify. Assume a system with virtual address space being 4GB, and the physical
memory space is 4MB, and each page is of size 4KB.
Q35. How many entries does an IPT have?__________

Q36. What is the size in bytes of IPT?_________

Q37. Assuming a page size of 4 Kbytes and that a page table entry takes 4 bytes, how many
levels of page tables would be required to map a 62-bit address space if all the page
table fits to one page?_________

Q38. Consider the four processes of size of 212 KB, 417 KB, 112 KB, and 426 KB running on a
system with a page size of 4KB. If working set sizes are 50 percent of total size, how
many frames are needed for these processes if thrashing is to be prevented?_______

For next three questions, in a 32-bit machine the virtual address is divided into 4 parts as
follows:
10-bit 8-bit 6-bit 8-bit
Assume that, PTE size at each level is 4 bytes.
Q39. What is the size of a page table (in KB) for a process of size 256KB?_______

Q40. What is the size of a page table (in KB) for a process of size 64MB?____

Q41. How much memory (in KB) is wasted by internal fragmentation to store page table for a
process of size 64K?________(Round of too nearest greatest integer)

Q42. Consider a system with a 2-KB frame size. Program A needs 50KB and an interactive
database program B needs 150KB of memory. There are 60 free frames. How many
frames will be allocated to program A by proportion allocation?_________

Q43. Suppose you had a computer that supported virtual memory and had 32-bit virtual
addresses and 4KB pages. If a process actually uses 2048 pages of its virtual address
space, how much space (in KB) would be occupied by the page table for that process if a
two-level page table was used and first 10-bit represent the first level page table?
Assume each page table entry occupies 4 bytes.______

OS Gate-2020 Page 44
Q44. Suppose you have a computer system with a 50-bit logical address divided into four
parts: | 12 bits | 12 bits| 12 bits | 14 bits |.
Assume that size of the page table entry is 4 bytes. If we have a 64MB program such that
the entire program and all necessary page tables are in memory. Assume that each page
table at different level fits in a single page. How much memory is used by program,
including its page tables? ________ KB

For the next two questions, consider a virtual memory system with the following properties:
 12-bit virtual address
 256-byte pages
 64KB of physical memory
The system uses a single level page table. The contents of the page table are partially shown
below (where VPN: Virtual page number and PPN: Physical page number)

Q45. What is the total size of the page table (in byte) for a process on this machine, assuming
that the valid, protection, dirty, and use bits take a total of 4 bits and that all the virtual
pages are in use?________

Q46. The physical address corresponding to the virtual addresses 0xae2 is:________
(a) 0xfce2 (b)0xf2e2 (c)0xfee2 (d)0xfde2

Q47. Assume that for a given system, virtual addresses are 40 bits long and physical
addresses are 30 bits long. There are 8 Kbytes of addressable entries per page. The TLB
in the address translation path has 128 entries. How many virtual addresses can be
quickly translated by the TLB?____________

For the next two questions, A CPU generates 44-bit virtual addresses. And Physical address
size is 32 bit. The page size is 8 KB. The processor has a translation look-aside buffer (TLB)
which can hold a total of 64 page table entries and is 16-way set associative.
Q48. The minimum size of the TLB tag is:____________

Q49. What is the entry size of TLB (in bytes)?_____________

Q50. In computing system, virtual memory is a memory management technique developed

for multitasking kernels. A virtual memory system often implements a TLB to speed up
the virtual-to-physical address translation. A TLB has the following characteristics:
 Assume each TLB entry has a valid bit, a dirty bit, a tag, and the page number.
 It is direct-mapped.
 It has 16 entries.
 The page size is 4K bytes.

OS Gate-2020 Page 45
  The virtual address space is 8Gbytes.
 The physical memory is 2Gbytes.
What is the exact total number of bits to implement this TLB?_________
For next two questions, suppose the TLB has an access time of 2 ns and the main memory
access time is 30 ns. Page size is 256 bytes, the virtual address space is 32 bits, and the physical
memory address space is 24 bits. The entire TLB and the beginning of the page table are given
below.

For each of the logical addresses given in binary below, let the corresponding page number is
x in decimal, the time to access the memory location is y(in ns), and the corresponding
physical memory address is z in decimal.
Q51. For logical address 01110100010 the sum x + y + z is ______
Q52. For logical address 10110110100 the sum x + y+ z is _______
For the next two questions, Imagine a system has the following parameters:
• Virtual addresses are 18 bits wide.
• Physical addresses are 16 bits wide.
• The page size is 1024 bytes.
• The TLB is 2-way set associative with 16 total entries.
The contents of the TLB and the first 32 entries of the page table are shown as follows. All numbers are
given in hexadecimal.

Q53. What is physical address corresponding to the virtual address: 0x078E6?

(a) 0x106A4 (b) 0x15CE6 (c) 0x2A2A4 (d) page fault

OS Gate-2020 Page 46
Q54. What is physical address corresponding to the virtual address: 0x02AA4?
(a) 0x106A4 (b) 0x15CE6 (c) 0x2A2A4 (d) page fault
For the next three questions, consider the memory system shown in Figure. Assume that
PTEs and PDEs are 32 bits long.

Assume there is a single task running on the system. The task‟s heap area is allocated in the
physical range 0x660000 - 0x666600. The task‟s stack area is allocated in the physical range
0x7999400 - 0x8000000. The task‟s text area is allocated in the physical range 0x1000 - 0x1400.
The task has no other sections
Q55. How many entries can the level-1 page table hold?_________

Q56. How many valid PTEs are there?________

Q57. How many valid PDEs are there?________

Q58. How much memory (in KB) is in use strictly by the Page Directory and Page
Tables?__________
Q59. Consider the following segment table:
Segment Id Base Length
0 219 600
1 2300 14
2 90 100
3 1327 580
4 1952 96
Assume that the first digit represents the segment number, which reference is illegal?
(a) 0, 430 (b) 1, 10 (c) 2, 500 (d) 3, 400
OS Gate-2020 Page 47
For the next five questions, consider an architecture using segmentation with paging. In this
architecture, the 32-bit virtual address is divided into fields as follows:
4 bit segment number 12 bit page number 16 bit offset
Q60. Number of segments is__________

Q61. What is the maximum size of each segment (in MB)?__________

Q62. What is the size of page (in KB)?_______

Q63. What is the maximum number of pages per segment?________

Q64. Assume PTE requires 4 bytes. What is the maximum size (in KB) of page table per
segment?_______

For the next four questions, the following tables contain information about a segmented,
paged virtual memory system and certain select memory locations. Total physical memory
size is 2Kbytes. All numbers in this table are in Hex unless otherwise noted. The processor is
byte-addressable, and uses little-endian storage. Assuming that size of page is 512-bytes.

Q65. What is physical address corresponding to the virtual address: 0xFA4?

(a) 0x03A4 (b) 0xEA4 (c) Segment fault (d) Page fault
Q66. What is physical address corresponding to the virtual address: 0x3A4?
(a) 0x03A4 (b) 0xEA4 (c) Segment fault (d) Page fault

Q67. What is physical address corresponding to the virtual address: 0xBA4?

(a) 0x03A4 (b) 0xEA4 (c) Segment fault (d) Page fault

Q68. What is the value in memory stored at the physical address corresponding to the virtual
address 0xEA4?
(a) 0x86a9 (b) 0x2373 (c) 0x3205 (d) 0x3423

OS Gate-2020 Page 48
For next two questions, consider a single level paging system with the entire page table stored
in memory.
Q69. If a memory reference takes 200 nanoseconds, how long (in nanoseconds) does a paged
memory reference take? ______

Q70. If we add associative memory, and 80% of all page-table references are found in the
associative registers, and the time to access the associative memory is 20 nanoseconds
then what is the effective memory access time (in nanoseconds)_________
Q71. If the cost of accessing main memory is 100 ns and the TLB hit rate is 90%, what is the
cost of accessing the TLB (in ns) if the effective memory access time is 119 ns? Assume a
single-level page table and a parallel algorithm is used for searching in TLB and
memory.____________
Q72. If a memory access takes 100 ns and reading a page from disk takes 10 ms, what is the
average memory access time including page fault overhead (in s) if page faults occur in
0.1% of the memory references? Assume that single level paging is used.___

Q73. Consider architecture with a one-level page table, without support of associative
memory. Accessing a memory location takes 50ns. Accessing a disk block takes an
average of 10s. What percentage of accesses can result in page faults if the average
access time needs to be less than equal to 150ns?_____(Round off to two decimal place)

Q74. Consider a virtual machine system with the TLB, a TLB can hold 512 entries and can be
accessed in 20 ns. A page table entry can be found in 50 ns and the average page
replacement time is 5ms. If page references are handled by the TLB 90% of the time and
only 0.01% lead to a page fault, what is the effective address-translation time (in
ns)?___________
Q75. Consider a demand-paging system where the page fault time (including the times for
looking up page, reading a page from the disk, and updating page table) is on average
30 milliseconds (ms) while the physical memory access time is 10 microsecond.
Addresses are translated through a page table in main memory. So, each memory
reference takes two memory accesses. Assume that 90% of the pages are in the page
table while the 10% of the pages cause page fault. What is the effective Access Time (in
ms) for the above system?__________ (Round of to two decimal places)

Q76. Assume that following parameters:

 Accessing and searching the TLB takes 5 ns,
 Transferring the data from the TLB into a address register takes 10 ns,
 Updating a record in the TLB takes 15 ns,
 Accessing and searching the PT takes 50 ns,
 Transferring the data from the PT into a address register takes 70 ns,
 Transferring the data from the memory into a data register takes 70 ns,
 The TLB hit ratio is 0.6.

OS Gate-2020 Page 49
 How many nanoseconds are needed in average to perform all the TLB and PT
operations needed to compute the physical address for a given virtual address
(assuming that all referenced pages are in main memory)._______

Q77. It has been observed that the number of instructions executed between page faults is
directly proportional to the number of page frames allocated to a program. If the
available memory is doubled, the mean interval between page faults is also doubled.
Suppose that a normal instructions takes 1 microsecond, but if a page fault occurs, it
takes 2001 microseconds (i.e, 2 ms to handle the fault). If a program takes 60 seconds to
run, during which time it has 15,000 page faults, how long (in seconds) would it take to
run if twice as much memory were available? ________Round of to two decimal places)
Q78. Consider a paged segmentation memory system consists of a physically address cache
with an access time of 20ns and a hit rate of 0.90, and a main memory with an access
time of 50ns. To improve this time, we have added TLB that reduces access time; The
TLB takes 5ns to do a translation on a TLB hit. The TLB hit ratio is 95%, the segment
table hit ratio is 100% and the page table hit ratio is 50%. What is the effective memory
access time (in ns) of the system with virtual memory?________
Q79. Consider a memory system with the following specifications:
 TLB access time = 20 ns
 TLB hit ratio = 99%
 Memory access time = 100 ns
 Page fault rate = 0.05%
 page swap (in or out) time = 5000,000 ns
 Single level paging is used
What is the effective access time (in ns) if we assume that single level paging is used and
50 percent pages currently in memory are dirty?__________
Q80. For next questions, consider the two-dimensional array A[1…100][1…100] of integer.
The array is stored in row major order in memory; where A[1][1] is a location 200, in a
paged memory system with pages of size 200 integer. A small process is in page 0
(location 0 to 199) for manipulating the matrix; thus, every instruction fetch will be from
page 0. For three page frames, how many page faults are generated by the following
array-initialization loops, using LRU replacement for code i and code ii, and
assuming page frame 1 has the process in it, and the other two are initially empty.
i. for(j = 1; j<= 100; j++)
for(i = 1; i<=100; i++)
A[i][j] = 0;

ii. for(j = 1; j<= 100; j++)

for(i = 1; i <= 100; i++)
A[j][i] = 0;

(a) 5000, 50 (b) 50, 5000 (c) 5000, 5000 (d) 50, 50
OS Gate-2020 Page 50
For the next two questions, Assume that you have a page-reference string for a process with
four frames (initially all empty). The page-reference string has length 15; 10 distinct page
numbers occur in it. Answer these questions for any page-replacement algorithms:
Q81. What is a lower bound on the number of page faults? _________
Q82. What is an upper bound on the number of page faults? _________

For next six questions, consider a computer that has a page size of 1,024 bytes. Consider the
following address reference string for this computer:
220, 1054, 2320, 4441, 1220, 2321, 5764, 5944, 3200, 10, 11, 2090
What is the number of page faults generated for this string when:
Q83. The page replacement policy is optimal and there are three page frames. ___________

Q84. The page replacement policy is optimal and there are four page frames. ___________

Q85. The page replacement policy is LRU and there are three page frames. ____________

Q86. The page replacement policy is LRU and there are four page frames. _____________

Q87. The page replacement policy is FIFO and there are three page frames. ____________

Q88. The page replacement policy is FIFO and there are four page frames. ____________

Q89. Consider the following virtual page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3,

2, 1, 2, 3, 6. Given a window size of 4 and assuming the primary memory is initially
unloaded, how many page faults will the given reference stream incur using the
working set model?_______
Q90. Consider the following virtual page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3,
2, 1, 2, 3, 6. How many page faults would occur if MRU replacement was used with four
frames in memory?__________

Q91. Consider the following virtual page reference string: 0, 1, 3, 6, 2, 4, 5, 2, 5, 0, 3, 1, 2, 5, 4,

1, 0. How many page faults would occur if Second chance page replacement was used
with four frames in memory?__________

Q92. Consider a demand-paging system in which a process is allocated three frames. Let the
Least Recently Used (LRU) page-replacement algorithm be used in the system. Let the
sequence of page references for the process be as follows: 1, 3, 4, 1, 5, 2, 3, 1, 6, 2, 4, 3, 2,
4, 1, 6, 5, 6, 1, 5, 3, 1, 2, 4, 1, 2. When processing each of the above page references,
determine the set of pages resident in memory. Now, identify a triple from the
following that represents a set of pages of the process that do NOT reside together in
memory at the same time?
(a) {1, 4, 5} (b) {1, 2, 3}
(c) {2, 3, 6} (d){1, 2, 6}

OS Gate-2020 Page 51
Q93. Consider the following page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3,
6. At how many minimum allocation of frames (x) greater than one, the LRU, FIFO and
Optimal replacement policy gives the same number of page fault?_____________

For the next three questions, a computer has four page frames. The time of loading, time of
last access, and the R and M bits for each page is as shown below:
frame loaded Last ref. R M
0 126 280 1 0
1 230 265 0 1
2 140 270 0 0
3 110 285 1 1

Q94. Which page will be replaced if the Most recently used (MRU) algorithm is used?_____

Q95. Which page will be replaced if the First In First Out (FIFO) algorithm is used?_____

Q96. Which page will be replaced if the Least Recently Used (LRU) algorithm is used?_____

Short Notes

OS Gate-2020 Page 52
OS Gate-2020 Page 53
 FILE SYSTEM

Q1. An important difference between a hard link and a symbolic link in a file system is
(a) Reference counts are kept for hard links but not for symbolic links.
(b) Reference counts are kept for symbolic links but not for hard links.
(c) Hard links are allowed to create cycles, but symbolic links are not.
(d) Symbolic links require much less disk space than hard links.
Q2. An advantage of a file allocation table (FAT) file structure over a simple linked file
structure is
(a) The file allocation table uses much less disk space than the linked structure.
(b) The simple linked structure uses much less disk space than the file allocation table
method.
(c) The file allocation table method allows faster seeks in files.
(d) The simple linked allocation method allows faster seeks in files.
Q3. A Unix inode stores
(a) Only the name of a file.
(b) Only file allocation information about a file.
(c) Only access permission information about a file.
(d) Access permissions and file allocation information for a file, as well as some other
information.
Q4. Contiguous allocation of files has some advantages and some disadvantages. Which of
the following is NOT a disadvantage of contiguous allocation?
(a) Fragmentation of the disk free blocks.
(d) Slow seek time.
(c) Difficulty of adding new blocks to the end of a file.
(d) Difficulty of adding new blocks to the beginning of a file.
Q5. For contiguous disk space allocation, a directory entry for a file contains.
(a) file name and the starting location
(b) file name and the index block
(c) file name and a pointer to the corresponding entry in the FAT table
(d) file name, the starting location, and the number of blocks used by this file

Q6. Consider a file system with 1KB file blocks and 32-bit block address. Assume that we
have a 1GB disk. If the free block numbers are managed in a linked listed of file blocks,
how many file blocks we will need for the 1GB empty disk?_______
Q7. Consider a file system with 1KB file blocks and 32-bit block numbers. Assume that we
have a 1GB disk. If we use a bitmap to represent the disk block usage of this disk, how
many file blocks do we need to store the bitmap?_______
Q8. Consider an OS uses bitmap technique for free space management. The beginning of the
free space bitmap looks like this after the disk partition is first formatted:

OS Gate-2020 Page 54
 1000000000000000 (the first block is used by the root directory and remaining is free).
The system always searches for free blocks starting at the lowest numbered block, if the
lowest numbered block is free then it allocate to file. So, after writing a file A which uses
6 blocks, the bitmap looks like this: 1111111000000000. Consider the following sequence
of operations:
(1) File B is written, using 5 blocks. (2) File A is deleted.
(3) File C is written, using 8 blocks. (4) File B is deleted.
What will be the bitmap at the end of above sequence of operations?
(a) 1111111000001100 (b) 1111111110000000
(c) 1111111000000011 (d) 1111110000011100
Q9. Assume within an inode there are 12 direct pointers, a single indirect pointer, and a
double indirect pointer. Assume a 4KB block size, and disk addresses that are 32 bits.
What is the maximum file size (measured in number of blocks) on this system? _______
Q10. Consider a UNIX-style i-node with 10 direct pointers, one single-indirect pointer, one
double-indirect pointer, and one triple-indirect pointer. Assume that the block size is 4K
bytes, and that the size of a pointer is 4 bytes. Assume that the OS has already read the i-
node for a file into main memory. How many disk reads are required to read data block
number 1049700 into memory?___________
Q11. Consider a UNIX file system with the following components:
 Disk blocks are 4096 bytes. Sectors are 512 bytes long.
 All metadata pointers are 32-bits long.
 An inode has 12 direct block pointers,
 One indirect block pointer and,
 One double-indirect block pointer.
 The total inode size is 256 bytes.
 Both indirect and double indirect blocks take up an entire disk block.
How much disk space (in bytes) for metadata is needed to store a 4 GB file?______
Q12. Consider a FAT-like File system that uses 24 bits for each entry. For a 32-GB disk, what
is the minimum size (in bytes) of a file allocation table in this system?____
For the next six questions, suppose that a disk drive has 5000 cylinders, numbered 0 to 4999.
The drive is currently serving a request at cylinder 143, and the previous request was at
cylinder 125. The queue of pending requests, in FIFO order; is 86, 1470, 913, 1774, 948, 1509,
1022, 1750, 130. Starting from the current head position, what is the total distance (in cylinders)
that the disk arm moves to satisfy all the pending requests, for
Q13. FCFS disk-scheduling algorithms?_________
Q14. SSTF disk-scheduling algorithms?_________
Q15. SCAN disk-scheduling algorithms?____ ______
Q16. LOOK disk-scheduling algorithms?_____
Q17. CSCAN disk-scheduling algorithms?_____ _____
OS Gate-2020 Page 55
Q18. CLOOK disk-scheduling algorithms?__________
Q19. Free disk space can be managed using a linked list of address of free block or a bit map.
Suppose that disk addresses require D bits. For a disk with a total of B blocks, F of
which are free, state the condition under which the free list uses less space than the bit
map.
(a) (D + B) < F (b) (D * B) < F (c) (D * F) < B (d) none of these
For next three questions suppose that a disk drive has 200 cylinders, numbered 0 to 199. A
hard disk spins at 6000 rpm (revolution per minute), and it takes 100 microseconds (on
average) for the head to traverse one track. Consider the following sequence of disk track
requests: 27, 129, 110, 186, 147, 41, 10, 64, 120. Assume that initially the head is at track 30 and
is moving in the direction of decreasing track number. Compute the time it takes to serve the
requests using
Q20. FIFO algorithm_________________

Q21. SSTF (shortest seek time first) algorithm _______________

Q22. SCAN algorithm ___________________
Q23. A disk drive using the Circular LOOK (C-LOOK) algorithm just wrote block 1203 and
then read block 1204. The following blocks are queued for I/O: 900, 1200, 1800, and
2500. In what order will they be scheduled?
(a) 1200, 900, 1800, 2500 (b) 1200, 900, 2500, 1800
(c) 1800, 2500, 1200, 900 (d) 1800, 2500, 900, 1200

Q24. Which disk scheduling algorithm is most vulnerable to starvation?

(a) SCAN. (b) Shortest Seek Time First (SSTF).
(c) LOOK. (d) First Come, First Served (FCFS).

Q25. 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 85 is serviced after servicing ____________ number
of requests.
Q26. Suppose the following disk request sequence (track numbers) for a disk with 100 tracks
is given: 45, 20, 90, 10, 50, 60, 80, 25, and 70. Assume that the initial position of the head
is on track 50. The additional distance that will be traversed by the head when the First
Come First Served (FCFS) algorithm is used compared to the SCAN (Elevator)
algorithm (assuming that SCAN algorithm moves towards 100 when it starts execution)
is _________ tracks

OS Gate-2020 Page 56
 Short Notes

OS Gate-2020 Page 57
 OPERATING SYSTEMS TEST -1
Q1. The principle objective of batch system is to maximize CPU utilization. What is the principle
objective of time-sharing operating systems?
(a) Minimize memory use (b) Maximize CPU utilization
(c) Minimize response time (d)All of the above

Q2. 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 algorithm(s) will result in the
maximum throughput?
(i) Round-Robin (ii) Shortest-Job-First
(iii) Highest-Response-Ratio-Next (iv)First-Come-First-Served
(a) All of the above (b) (ii) and (iv) (c) (ii) and (iii) (d) (ii) only

Q3. Which of the following instruction should be privileged instruction(s)?

i. Load base register ii. Read timer
iii. Print a string on the printer directly iv. Change mode bit
(a) All of the above (b) (i), (ii), and (iii)
(c) (i), (iii), and (iv) (d (ii), (iii), and (iv)

Q4. Which statements are correct?

1. Real time systems tend to use pre-emptive schedulers
2. Timesharing systems tend to use pre-emptive schedulers
3. Assume a priority based pre-emptive scheduler where some jobs may need exclusive
access to a resource. Assume lower priority jobs relinquish any resource they happen to
share with a higher priority job if the high priority job asks them for the resource. Sucha
scheduler will never witness a priority inversion, i.e., a situation whereby a higher priority
job waits, directly or in directly, for lower priority jobs
(a) 1 and 2 only (b) 1, 2 and 3 only
(c) 1 and 3 only (d) 2 and 3 only

Q5. Which of the following is an advantage of system-level threads?

(a) A thread blocking in the kernel doesn’t stop all other threads in the same process.
(b) Different threads can be scheduled on different processors in a multicourse machine.
(c) Each thread can be scheduled separately, rather than using the time slice of one process
over many threads.
(d) All of the above.

Q6. Two computer systems, A and B, are exactly identical (including scheduling algorithms and
set of processes) except that the CPU of A is faster than the CPU of B. Which of the following
statement is FALSE?
(a) Throughput for processes in A will be lowers than B.
(b) CPU utilization of A will be lower or equal than B.
(c) Average turnaround time for processes in A will be lower than B.
(d) Average response time for processes in A will be lower than B.

OS Gate-2020 Page 58
Q7. Threads of the same task....
I. Share the same address space
II. Reduce context switching overhead
III. Are protected from each other the same way as heavy weight processes.
Which of the following options are correct?
(a) Only Statement I about threads is true
(b) Statements I and II about threads are both true
(c) Statements I, II and III about threads are all true
(d) Statements II and III about threads are all true

Q8. The aging algorithm with  = 1/2 is being used to predict run times. The previous four
runs, from oldest to most recent, are 40, 20, 40, and 15 msec. What is the prediction of the
next time?_____ ms

Q9. Which of the following statements about the process state transitions are FALSE?
(a) When a running process receives interrupt, it goes to ready state.
(b) Upon finishing, the running process exits and goes to terminated state.
(c) A ready state goes to running state when the scheduler schedules it.
(d) An I/O process on completion of I/O request goes back to running state.

Q10. Consider a pre-emptive priority scheduler with N priority queues. If the highest non-empty
priority queue contains multiple jobs, the scheduler runs them round robin with a time-
slice of 200ms. The priorities of jobs are dynamically adjusted as follows:
Rule 1: When a job enters the system, it is placed on the highest priority queue.
Rule 2: Once a job accumulates 100ms of CPU time at a given level, its priority is reduced by 1.
Rule 3: After 1 second, all the jobs in the system are moved to the highest priority queue.
Which of the following conclusion is/are correct about this approach?
(1) It favours CPU bound program
(2)It favours I/O bound program
(3)This approach may cause starvation for some jobs
(a) 1 only (b) 2 only (c) 1 and 3 only (d) 2 and 3 only

Q11. The primary difference between user-level threads and kernel-level threads is:
(a) User level threads do not use OS services via system calls, where kernel-level threads
require system calls.
(b) User level threads are independent of each other, whereas kernel-level threads can
write into each other’s memory space.
(c) User threads are supported above the kernel and are implemented by a thread library at
the user level. Whereas, kernel threads are supported directly by the operating system.
(d) None of above.

Q12. Consider five processes (process id 0, 1, 2, 3 and 4 respectively) with compute time bursts
2, 4, 8, 6 and 4 time units. All processes arrive at time zero. Consider the longest remaining
time first (LRTF) scheduling algorithm. In LRTF ties are broken by giving priority to the
process with the lowest process id. The average turnaround time is:____________

OS Gate-2020 Page 59
Q13. Suppose 10 processes arrive in a system at time 0. Each process takes 15 seconds to run.
The time quantum assigned to each process is 5 seconds. None of the process requires I/O,
and no new process is created. Suppose the Round Robin algorithm is used for scheduling.
What is the maximum response time experienced by a process in ms?______

Q14. If the waiting time for a process is p and there are n processes in the main-memory then the
CPU utilization is given by:
(a) p/n (b) p^n (c) 1-p^n (d) n-(p^n)
Q15. Consider the following set of processes to be executed on a system that uses shortest
remaining time first.
Process Arrival time CPU burst (in ms)
P1 0 20
P2 6 12
P3 21 8
P4 28 2
P5 30 15

What is the waiting time for process P1?_____ms

Q16. Measurements of a certain system have shown that the average process runs for time T
seconds before blocking on I/O. A process switch requires time S seconds, which is
effectively wasted (overhead). For round robin scheduling with quantum Q seconds, give a
formula for the CPU-efficiency(E) for Q = Infinity?
(a)E=T/(S+T) (b) E=Q/(Q+S)
(c) E=T/(Q+S) (d)E=Q/(S+T)

Q17. Consider the following 6 processes to be executed on a system that uses FCFS scheduling
Process Arrival time CPU burst (in ms)

P1 0 7
P2 5 9
P3 15 18
P4 20 21
P5 25 16
P6 30 9
Assume the above table shows the first CPU burst for process P4. If P4 spends 5 ms in the
I/O queue after first CPU burst, spends 15 ms for doing output operation, and then waits in
the ready queue for another 12 ms and has a final CPU burst of 9 ms and then terminates.
What will be the turnaround time for P4?____ms
Q18. Consider a ready queue with four processes and their corresponding information as below:
Process Arrival Time Burst Time (ms)
P1 0 25
P2 0 14
P3 4 12
P4 5 18
Assume that each context switching takes 1 ms. What is the average waiting time per
process (including context switching times) for a round robin system with time quantum
values of4ms?_____ms

OS Gate-2020 Page 60
Q19. Consider a system with following 5 processes
Process Arrival CPU
time Burst
P1 1 20
P2 6 15
P3 9 9
P4 19 3
P5 21 1
Assume a multi-level scheduler combining Round Robin with time quantum 5 and first-in-
first-out (FIFO). Round Robin has higher priority and each job is initially inserted at the end
of this queue. After executing for 5 time units, a process is pre-empted and inserted at the
ready queue of FIFO. What is average turnaround time?
(a)25.5 (b)23.4 (c)27.5 (d)23.6

Q20. Consider the following set of processes

Process Arrival Time Burst Time

F 0 6
G 2 3
H 3 2
I 7 5
The Gantt chart for Shortest-Job-First (SJF) scheduling algorithm is
(a)
F F G H H G G F F F F I I I I I
(b)
F F G G G H H F F F F I I I I I
(c)
F F F F F F H H G G G I I I I I
(d)
F F F F F F G G G H H I I I I I
Q21. Consider a system where there are 3 processes, A, B, and C. Their details are as follows
A: Arrival time = 0, I/O cycle-CPU = < 2, 4, 6, 6>
B: Arrival time = 1, I/O cycle-CPU = < 3, 3, 4, 4>
C: Arrival time = 4, I/O cycle-CPU =< 7, 4, 1, 8>
What is the average waiting time with SJF scheduling assuming I/O can be overlapped?
(a) 16 (b)6.67 (c)24 (d)None

Q22. A uni-processor computer system only has two processes, both of which alternate 10 ms
CPU bursts with 90 ms I/O bursts. Both the processes were created at nearly the same time.
The I/O of both processes can proceed in parallel. Which of the following scheduling
strategies will result in the least CPU utilization (over a long period of time) for this system?
(a) First come first served scheduling
(b) Shortest remaining time first scheduling
(c) Static priority scheduling
(d) Round robin scheduling with a time quantum of 5 ms
OS Gate-2020 Page 61
Q23. Consider the following pseudo code:
main()
{
int t1 = 0, t2 = 0, t3 = 0;
t1 = fork();
t2 = fork();
if (t1! = 0)
{
t3 = fork();
printf(“Gate@zeal”);
}
}
How many times the “Gateatzeal” will be printed by the given code________
Q24. Consider the following three periodic real-time processes to be scheduled using Earliest
Deadline First (EDF) on a uniprocessor:

At which time third instance of process P3 will be finish__________

Q25. Consider the Earliest Deadline First (EDF) Scheduling; a task set is schedulable under EDF,
if and only if it satisfies the condition that the total processor utilization due to the task set
is less than 1. For a set of periodic real-time tasks {T1, T2… Tn}, EDF schedulability
criterion can be expressed as: . Where ui is average utilization due to
the task Ti and n is the total number of tasks in the task set. This condition is both a
necessary and a sufficient condition for a set of tasks to be EDF schedulable. Which of the
following task set is schedulable under EDF?
T1 = {t1 = (e1=10, p1=20), t2 = (e2=5, p2=50), t3 = (e3=10, p3=35)}
T2 = {t1 = (e1=20, p1=100), t2 = (e2=30, p2=150), t3 = (e3=60, p3=200)}
T3 = {t1 = (e1=40, p1=100), t2 = (e2=30, p2=200), t3 = (e3=80, p3=150)}
(a) T1 only (b) T2 and T3 only (c) T3 only (d) T1 and T2 only

OS Gate-2020 Page 62
 OPERATING SYSTEMS TEST -2
Q1. A computer system has enough room to hold four programs in its main memory. These
programs are idle waiting to do I/O, half of the time. What fraction of the CPU time is
wasted, when main memory is completely utilized? __________

Q2. Consider the following solution to the synchronization problem for process Pi=0 and Pj=1:
int turn = i; //can take either i or j
boolean flag[2] = {false , false};
do
{
flag[i] = true;
turn = (i+1) % 2;
while(flag[(i+1)%2] && (turn == (i+1) %2));
Critical section
flag[i] = false;
Remainder section
}while(true);
Which of the following are satisfied?
(a) Only progress (b) Both mutual exclusion and bounded waiting
(c) Only mutual exclusion (d) All are satisfied

Q3. Consider the concurrently running processes A and B given below.

semaphore s1=0, s2=0;
Process A: Process B:
do{ do{
wait(s1); instruction d;
instruction a; signal(s1);
instruction b; wait(s2);
instruction c; instruction e;
signal(s2); }while(true);
}while(true);
Which of the following order of executions is possible?
(a) abcde (b) daebc (c) deabc (d) dabce

Q4. Consider the following solution to the producer/consumer problem.

Semaphore mutex =1 , buffer_size = 0
shared_buffer = 0

What could possibly go wrong with the above semaphore solution to the
producer/consumer problem?
(i) The consumer could grab the mutex semaphore and stop the producer from being able
to store its data in the shared_buffer.
(ii) A fast producer could overwrite the shared_buffer variable with another result before
OS Gate-2020 Page 63
 the previous result was retrieved by the consumer.
(iii) If the consumer is not running, the producer continues to produce all of its data.
(a)i&ii (b)ii&iii (c)i&iii (d)i,ii,&iii
Q5. Which of the following statements about the readers-writers problem is FALSE?
(a) A readers preferred solution is appropriate when the most recent data is not required.
(b) Multiple readers may be executing in the critical section at a time.
(c) A writers preferred solution is always appropriate when there are many writers and
hardly any readers.
(d) Only one writer may be executing in the critical section at a time.
Q6. Consider the following code
i=0
while( i < 2)
{
print(i)
fork()
i++
}
How many times does the print function get executed by the code above? __________
Q7. Consider the following code for to process mutual exclusion
boolean flag[2]; /* initialized to false */
int turn;
The structure of process Pi (i == 0) , with Pj (j == 1 ) being the other process is given by:
Process Pi
while(1) {
flag[i] = true;
while (flag[j]) {
if (turn == j) {
flag[i] = false;
while (turn == j);
flag[i] = true;
}}
/* Critical Section */
turn = j;
flag[i] = false;
/* Non-critical Section */
}
Which of the following are satisfied?
(a) Only progress (b) Only mutual exclusion
(c) Both mutual exclusion and progress (d)all are satisfied
Q8. We want to use semaphores to implement a shared critical section (CS) among three
threads T1, T2, . and T3. We want to enforce the execution in the CS in this order: First
T2 must execute in the CS. .When it finishes, T1 will then be allowed to enter the CS; and
when it finishes T3 will then be . allowed to enter the CS; when T3 finishes then T2 will be
allowed to enter the CS, and so on, (T2, T1, .T3, T2, T1, T3, …) What is the minimal number
of semaphores we need in order to implement this?_____________
OS Gate-2020 Page 64
Q9. Which of the following is true about race condition?
(a)A race condition occurs when correctness of the program depends on one thread
reaching point a before another thread reaches point.
(b) Exclusive access to all shared resources eliminates race conditions.
(c) Race conditions are the same as deadlocks.
(d)All race conditions occur inside loops, since that is the only way we can interleave
processes.
Q10. Consider the following code to ensure mutual exclusion between processes , when process
wants to enterinto CS it must execute the function CSEnter and after the CS it must execute
function
CSExit.
boolean inside[2]= {false, false} , turn;
CSEnter(int i)
{
inside[i] = true;
while(inside[j])
{
inside[i] = false;
while(turn == j) continue;
inside[i] = true;
}}
CSExit(int i)
{
turn = j;
inside[i] = false;
}
Which of the following is not satisfied by above code?
(a) Progress (b) Mutual exclusion
(c) Bounded waiting (d) All are satisfied
Q11. Consider the following resource status of a system:

Currently system is in safe state. Now consider the following independent requests
I. a request from process P1 arrives for (0, 0, 1, 0)
II. a request from process P2 arrives for (0, 0, 1, 0)
Which of the two requests is/are granted by OS?
(a) I only (b) II only (c) I and II (d)None
Q12. There are some proposed solutions to the mutual exclusion problem that utilize a lock
variable. This variable is set to 0 if the shared resource is not being used, and set to 1 when
the resource is in use. So if we want to use the resource, we have but to check the lock
variable. If it is 1, we continually repeat the test until the lock variable becomes 0. Then
weset it to 1, access the shared resource, and set the lock variable back to 0. What can go

OS Gate-2020 Page 65
 wrong with this solution?
(S2) There is a race condition present. Multiple processes (or threads) could check the lock
variable, find it 0, and then set it to 1 and enter their critical sections.
(S1) The solution, as presented, will not work if there are more than two processes.
(a) S1 only (b)S2 only (c)S1 and S2 only (d)None
Q13. In which of the following four necessary condition conditions for deadlock, processes claim
exclusive control of the resources they require?
(a)No preemption (b)Mutual Exclusion (c) Circular Wait (d) Hold & Wait

Q14. A scheduler uses multi-level feedback queues with the following characteristics:
Level Time-slice When dispatched
1 10 msec
2 40 msec Only when level 1 is empty
3 Unlimited Only when levels 1 and 2 are empty
Initially processes enter through scheduler in the level 1 queue and move down a level if
they completely use their time-slices. Processes do not move up levels. Preemption only
occurs when the time-slice is completed. The list of processes shows CPU burst times. The
processes start in this order in the level 1 queue.
Process CPU burst
A 8
B 300
C 60
D 12
E 5
F 20
What is the completion time for process B?_____________
Q15. Consider the following resource allocation graph?

The system is in safe state. Which of the following is/are possible safe sequence?
1. p0, p2, p1, p3, p4 2.p2, p0, p3, p1, p4
3. p2, p1, p4, p3, p0 4.p2, p4, p1, p3, p0
(a)1 and 2 (b) 2 and 3 (c) 3 and 4 (d) 1,2,3 and 4

Q16. What are the possible outputs when the processes A and B run concurrently and only once?
Assume .that the shared variables X and Y are initialized to 0.
Process A Process B
while (X == 0); printf(“b”);
printf(“a”); X = 1;
Y = 1; while (Y == 0);

OS Gate-2020 Page 66
 Y = 0; printf(“c”);
printf(“d”);
Y = 1;
(a) bacd (b) badc (c)bcad (d) a and b both

Q17. Consider that before execution of following code the value of variable X is 5.
Semaphore S = 0 , T = 0 ;
A1: Y = X*2; B1: Z = X+1;
wait(S); signal(S); wait(T);
A2: X = Y; B2: X = Z;
signal(T);
What is the value of X after following code get executed?
(a) 10 (b) 6 (c) 5 (d) 11

Q18. What is the output generated by following concurrent processes?

Semaphore: S1=0, S2=1, S3=0;
int a=1;
P1 P2 P3
while(1){ while(1){ while(1){
P(S1) P(S2); P(S3);
a=2*a; a=a+1; P(S3);
V(S3); } V(S1); printf("%d\n",a);
V(S3); } V(S2);
(a) for(int i = 1; i <= n ; i++) { a=(a+1)*2; printf("%d\n", a); }
(b) for(int i = n; i <= 1 ; i--) { a=(a*2) + 1; printf("%d\n", a); }
(c) for(int i = n; i <= 1 ; i--) { a=(a+1)*2; printf("%d\n", a); }
(d)both a and c

Q19. What are the possible output sequences from the following program:
int main() {
if (fork() == 0) {
printf("a");
exit(0);
}
else {
printf("b");
wait(); //wait for the termination of child
}
printf("c");
exit(0);
}
Which of the following are the possible output sequences?
(i)abc (ii) bacc (iii)bac (iv)bca (v)cab
(vi)cba (vii) abcc (viii) acb
(a) viii and i (b) ii ans vii (c) i and iii (d)iv, vi and v

OS Gate-2020 Page 67
Q20. Consider that two global data structures that will be shared among the Processes. The data
structures are not necessarily accessed at the same time. Which of the following is/are
true?
(1) If the program has only one semaphore, and Process call P on that single semaphore
before using either of the data structures, the code will not work correctly.
(2) Having one semaphore will work, but having two, one per shared data structure, may
allow for increased performance.
(3) If the machine has only one processor, only one of the processes can run at a time, so
semaphores are not necessary in that case.
(a) 1 only (b) 2 only (c) 1 and 2 (d)1, 3
Q21. For next questions consider the following critical-section problem with n processes can be
solved using "test_and_set()". The algorithm for a process Pi (for 0<=i<n) is listed below.
int lock_value = 0, waiting[n]={0};
int *lock = &lock_value;
Process Pi :
int j;
int key; //Boolean variable 1 or 0
do {
waiting [i]= 1;
key = 1;
while (waiting[i] && key) key=test_and_set (&lock);
waiting[i]=0;................................................................……………………… /* line 5 */
/* critical section; */
j=(i+1) % n;
while ((j != i) && (! waiting[ j])) j=(j+1) % n;
if (j==i) lock= 0;
else waiting[ j]= 0; …………………………………………………………. /* line 10 */
/* remainder section */
} while (true)
If line 5 ( waiting[i]=0; ) is deleted, then
(a) After process Pi leaves critical section, it will not be able to run critical section again the
next time it tries.
(b) Later on, when another process Pj leaves critical section, it may give the right of
accessing critical section to process Pi even if Pi does not want to at that time.
(c) It may happen that shortly after process Pi leaves critical section, another process trying
to get into critical section cannot do so.
(d) Some processes currently waiting to get into critical section will not be able to forever

Q22. For next questions consider the following critical-section problem with n processes can be
solved using "test_and_set()". The algorithm for a process Pi (for 0<=i<n) is listed below.
int lock_value = 0, waiting[n]={0};
int *lock = &lock_value;
Process Pi :
int j;
int key; //Boolean variable 1 or 0
do {
waiting [i]= 1;
key = 1;

OS Gate-2020 Page 68
 while (waiting[i] && key) key=test_and_set (&lock);
waiting[i]=0;................................................................……………………… /* line 5 */
/* critical section; */
j=(i+1) % n;
while ((j != i) && (! waiting[ j])) j=(j+1) % n;
if (j==i) lock= 0;
else waiting[ j]= 0; …………………………………………………………. /* line 10 */
/* remainder section */
} while (true)
In above code ifline 10 is removed, then which of the following is wrong?
(A) After process Pi leaves critical section, it may not be able to run critical section again the
next time it tries.
(B)Later on, when another process Pj leaves critical section, it may give the right of
accessing critical section to process Pi even if process Pi does not want to at that time.
(C)It may happen that shortly after process Pi leaves critical section, another process trying
to get into critical section cannot do so.
(D)Some processes currently waiting to get into critical section may not be able to do so for
ever.

Q23. Consider the following three processes and four semaphores:

Semaphore s1 , s2 , s3 , s4 // Counting semaphore int x=1;
Process1() { Process2() { Process3() {
while (x!=360){ while (x!=360){ while (x!=360){
P(s1); P(s2); P(s3);
P(s4); P(s4); P(s4);
x = x * 2; x = x * 3; x = x * 5;
V(s4);} V(s4);} V(s4);}
What should be initial values for the four semaphores that all the three process is
guaranteed to terminate?
(a) s1 = 3, s2 = 1, s3 = 1, s4 = 2 (b) s1 = 2, s2 = 3, s3 = 1, s4 = 1
(c) s1 = 3, s2 = 2, s3 = 1, s4 = 1 (d) s1 = 2, s2 = 2, s3 = 1, s4 = 2
Q24. Each thread has its own
(a)Heap (b)Stack (c)Global values (d)Text data
Q25. Consider the following process and resource requirement of each process:

Predict the state of this system, assuming that there are a total of 5 instances of resource
type 1 and 4 instances of resource type 2.
(a)Can go to safe state or unsafe state based on the sequence (b) Always go to safe state
(c) Always go to unsafe state (d) None of the above

OS Gate-2020 Page 69
 OPERATING SYSTEM TEST-3
Q1. For contiguous allocation of disk space to files which of the following algorithms leaves the
smallest amount of external fragmentation when a single file allocation is made?
(a) Best fit (b) Next fit (c) First fit (d) Worst fit

Q2. Suppose we have the following page accesses: 1 2 3 4 2 3 4 1 2 1 1 3 1 4 and that there are
three frames within our system. Using the FIFO replacement algorithm, what will be the
final configuration of the three frames following the execution of the given reference string?
(a) 4, 1, 3 (b) 3, 1, 4 (c) 4,1,3 (d) 3,4,2

Q3. Suppose we have the following page accesses: 1 2 3 4 2 3 4 1 2 1 1 3 1 4 and that there are
three frames within our system. Using the LRU replacement algorithm, what is the number
of page faults for the given reference string?
(a) 6 (b) 7 (c) 8 (d) 9

Q4. Consider a system with virtual memory of size 232 bits and the page size is 1Kbyte, the size
of the physical memory is 64Kbyte, the size of a page table entry is two bytes. What is the
size of the page table if single level paging is used? __________MB.

Q5. Consider a system with virtual memory of size 232 bits and the page size is 1Kbyte, the size
of the physical memory is 64Kbyte, the size of a page table entry is four bytes. What is the
size of the inverted page table?_______KB

Q6. Consider a memory system consists of the following hole sizes in the given order: 10 KB,4
KB, 20 KB, 18 KB, 7 KB, 9 KB, 12 KB, and 15 KB. Which hole is taken for successive segment
requests of12 KB, 10 KB and 8 KB by First Fit, Best Fit Worst Fit and Next Fit
respectively?(Assume fixed partition scheme)
(a) First fit: 20 KB, 10 KB, 18 KB. (b) First fit: 20 KB, 10 KB, 18 KB.
Best fit: 12 KB, 10 KB, 9 KB. Best fit: 12 KB, 10 KB, 9 KB.
Worst fit: 20 KB, 18 KB, 15 KB. Worst fit: 20 KB, 18 KB, 15 KB.
Next fit: 20 KB, 18 KB, 12 KB Next fit: 20 KB, 12 KB, 9 KB
(c) First fit: 20 KB, 10 KB, 18 KB. (d) First fit: 20 KB, 10 KB, 18 KB.
Best fit: 12 KB, 10 KB, 9 KB. Best fit: 12 KB, 10 KB, 9 KB.
Worst fit: 20 KB, 18 KB, 12 KB. Worst fit: 20 KB, 18 KB, 15 KB.
Next fit: 20 KB, 18 KB, 9 KB Next fit: 20 KB, 18 KB, 9 KB
Q7. Consider a virtual machine system with the TLB, a TLB can hold 1024 entries and can be
accessed in 1 nsec. A page table entry can be found in 100 nsec and the average page
replacement time is 10ms. If page references are handled by the TLB 99% of the time and
only 0.01% lead to a page fault, what is the effective address-translation time in ns if the
single level paging is used?____________
Q8. Suppose we have a demand-paged memory. The page table is held in registers. It takes 8
milliseconds to service a page fault if an empty frame is available or the replaced page is not
modified and 20 milliseconds if the replaced page is modified. Memory access time is 100
microseconds. Assume that the page to replace is modified 70 percent of the time. What is
the maximum acceptable page-fault percentage for an effective access time of no more than
200 microseconds?___________

OS Gate-2020 Page 70
Q9. Which of the following statements is/are true about file systems?
S1: Reading a random location in big files is usually faster in inode-based file systems than
the FAT file systems.
S2: For better sequential read/write performance, the file system should try to allocate
consecutive blocksto a file.
(a) S1 only (b) S2 only (c) S1 and S2 only (d) None of these

Q10. Consider a system using segmentation for memory management. There are 64 segments in
a program and largest segment size is 1024 bytes the length of logical address is:
(a) 12 bits (b) 14 bits (c) 16 bits (d) 18 bits

Q11. Consider a virtual memory system with following specification

 Size of virtual addresses: 40 bits
 Size of physical addresses : 30 bits
 Page size : 8 Kbytes
 The TLB can store 128 entries.
How many virtual addresses can be translated by the TLB without any miss?
(a) 27 (b) 213 (c) 220 (d) 230

Q12. Consider a virtual memory system with following specification

 Size of virtual addresses: 32 bits
 Size of physical addresses : 18 bits
 Page size : 64Kbytes
If the virtual address is 0x23456111 then page number would be:
(a) 0x23456 (b)0x2345 (c)0x56111 (d)0x6111

Q13. Consider the following graph which represents the number of page faults by a process over
time.

Which of the following can be inferred from the graph given above?
1. The peak point indicates a time when the process is changing its working set.
2. The process has three different working sets.
3. A small number of page faults after the peak shows that pages for thecurrent working set
have been allocated to the process.
(a) 2 and 3 (b) 1 and 2 only (c) 1 only (d) All the above

Q14. Which of the following is true?

(a) If all jobs have identical run lengths, a RR scheduler provides better average turnaround
time than FIFO.
(b) A RR scheduler is guaranteed to provide the optimal average turnaround time for a
OS Gate-2020 Page 71
 workload.
(c) The shorter the time slice, the more a RR scheduler gives similar results to a FIFO
scheduler
(d) An RR scheduler tends to decrease average response time as the time-slice is decreased.

Q15. Consider a file system with block size 4KB and 4-byte disk block addresses. The inode entry
for the file ‘[Link]’ has 8 direct block address and an indirect block which is half full. What is
the file size in KB?__________
Q16. Suppose that a disk drive has 300 cylinders, numbered 0 to 299. The drive is currently
serving a request at cylinder 143, and the previous request was at cylinder 15. The queue of
pending requests, in FIFO order, is: 86, 147, 291, 18, 95, 151, 12, 175, 30, 151, 12 and 43.
Starting from the current head position, what is the total distance (in cylinders) that the
disk arm moves to satisfy all the pending requests if elevator disk-scheduling algorithm is
used?_____________
Q17. Consider a file system make use of file allocation table. Each entry in the file allocation table
is 4 bytes in size. Given a 100 MB disk on which the file system is stored and data blocks of
size 1024 bytes, what is the maximum sized file that can be stored on this disk?
___________MB( Up to two decimal place)

Q18. In a virtual memory system, 1 in 600 references on average causes a page fault. When the
page fault is to be serviced, 1 in 40 pages have their dirty bit set. Let the average seek time
for the disk is 12ms, the average latency is 1ms, and the average wait time in the device
queue is 10ms. In addition, the transfer time per page is 1ms. Let the memory access be 40
s when there is no page fault. Compute the effective memory access time in s?____________(
Up to two decimal place).

Q19. Consider a file system with 2048 byte blocks and 32-bit block pointers. Each file has 12
direct pointers; a singly-indirect pointer, a doubly-indirect pointer, and a triply-indirect
pointer. Approximately how large of a disk can this file system support?
(a) 256 GB (b) 0.25 TB (c) 128 GB (d) 8 TB
Q20. Consider a virtual memory system that uses multi-level paging for address translation.
Virtual addresses and physical addresses are 64 bits long. The page size is 1 MB (2 20 bytes).
The size of a page table entry is 16 (24) bytes. Each individual page table, at each level, must
fit in a single frame. Suppose that a particular process uses only 128 GB (237 bytes) of
virtual memory, with a virtual address range from 0 to 237 − 1. How many individual page
tables, at each level, will be required to translate this process’ address space? Let the Level
1 required X page tables, Level 2 required Y page tables, Level 3 required Z page tables:
Level 1 Level 2 Level 3 Offset
Then the value of X + Y + Z is:_____________
Q21. Consider a system with a virtual address size of 64MB (2^26), a physical memory of size
2GB (2^31), and a page size of 1K (2^10). Under the target workload, 32 processes (2^5)
are running; half of the processes are smaller than 8K (2^13) and half use the full 64MB
virtual address space. What is the minimum number of levels of page tables that will be
required for virtual-to-physical translation in this system? Assume the page table fits into
single page________
OS Gate-2020 Page 72
Q22. On average, each job leaves half of its last page unused, and there are a maximum of 20 jobs
in memory at any given time. Jobs have 40 pages in their working set. Pages are 2Kbytes
long and virtual addresses are 24 bits long. What percentage of the memory is wasted due
to internal fragmentation?________

Q23. Given a byte-addressable system with 32 bit words, a virtual address space of 4 gigabytes, a
physical address space of 1 gigabyte, and a page size of 4 kilobytes. Now assume that a 4-
way set-associative translation look aside buffer is implemented, with a total of 1048576
virtual address translations. What is the size of translation look aside buffer in
bytes?__________

Q24. For questions, consider a NRU (Not Recently Used) Page Replacement Algorithm. This
algorithm requires that each page have two additional status bits 'R' and 'M' called
reference bit and change bit respectively. The reference bit(R) is automatically set to 1
whenever the page is referenced. The change bit (M) is set to 1 whenever the page is
modified. These bits are stored in the PMT and are updated on every memory reference.
When a page fault occurs, the memory manager inspects all the pages and divides them into
4 classes based on R and M bits.
Class 1: (0,0) − neither recently used nor modified - the best page to replace.
Class 2: (0,1) − not recently used but modified - the page will need to be written out before
replacement.
Class 3: (1,0) − recently used but clean - probably will be used again soon.
Class 4: (1,1) − recently used and modified - probably will be used again, and write out will
be needed before replacing [Link] algorithm removes a page at random from the lowest
numbered non-empty class.A computer has four page frames. The time of loading,time of
last access and the Rand M bits for eachpage are as shown below (the times are in clock
ticks):

Which page will be replaced in this page replacement algorithm?

(a) 0 (b) 1 (c) 2 (d) 3

Q25. Which page will be replaced if the page replacement algorithm is replaced by Least
Recently Used?
(a) 0 (b) 1 (c) 2 (d) 3

OS Gate-2020 Page 73
 OPERATING SYSTEM FULL TEST

Q1. How many of the possible outputs printed when the processes A and B run
Concurrently?____________
Assume that the shared variables X and Y are initialized to 0.
Process A Process B
printf(“a”) printf(“b”)
while(x == 0); while(y == 1);
y = 0; x= 1;
printf(“c”); printf(“d”);
y = 1; x = 0;
while(x == 0); while(y == 1);
printf(“e”); printf(“f”);
Q2. For questions consider a virtual memory system with 2-level paging and every page table
fits in a single page. The page size 28 bytes and the page table entry (PTE) size is 8 bytes.
What is the size (in Kbytes) of a virtual address space in this system?
(a)64 (b) 128 (c) 256 (d) 512

Q3. For questions consider a virtual memory system with 2-level paging and every page table
fits in a single page. The page size 28 bytes and the page table entry (PTE) size is 8 bytes.
Consider a process of the largest size possible on this system. How many Kbytes of memory
are occupied by the page tables for this process?__________

Q4. For contiguous disk space allocation, a directory entry for a file contains.
(a) File name and the starting location
(b) File name and the index block
(c) File name and a pointer to the corresponding entry in the FAT table
(d) File name, the starting location, and the number of blocks used by this file

Q5. Consider a file system with following specification

 Block size: 1KB
 Disk size: 1GB
If bit vector technique is used for free space management how many blocks do we need to
store the bitmap?
(a) 64 (b) 128 (c) 256 (d) 512

Q6. Consider the following scenario of resource allocation in a system

What is the smallest value of x for which the system is in safe state?
(a) 0 (b) 1 (c) 2 (d) 3

OS Gate-2020 Page 74
Q7. Suppose that a hard disk has 100 tracks (0 — 99) on every surface. The following tracks are
requested 10, 22, 20, 1, 98, 35, 78, 48, 82 and 69, in that order. Track to track seek time is
10 msec. The read-write head is currently at track 50 and is moving towards track 100.
How much seek time (in msec) is needed for the C-LOOK disk scheduling
algorithms?___________

Q8. Consider a system with 34-bit virtual address and three level of paging. Each page table
entry takes 4 bytes. If every page table fits into a single page then what is page size in
Kbyte? __________

Q9. Consider a system with MLFQ scheduler and a process P1 which requires 10231 seconds
for execution. The highest priority queue uses a time quantum of 10seconds and on each
lower priority level the time quantum doubles, and processes switches to lower priority
level after completing its time quantum in higher priority queue. On what queue number
will process P1 terminates?_____________ (Assume the queue number start from 0)
Q10. Consider a multilevel feedback queue with three queue of different priority levels:
q1: highest priority queue and employs RR with quantum= 8 msec,
q2: medium priority queue and employs RR with quantum = 16 msec,
q3: low priority queue employs FCFS.
New process initially enters into a queue according to its priority. Once a process completes
its time quantum in higher priority queue it is shifted to lower priority queue. The system
will executes the process of lower priority queuesonly when higher priority queues are
empty.
Process Arrival Time Priority Burst Time
P1 0 high 30
P2 3 high 28
P3 10 medium 20
P4 20 low 9
P5 35 low 2
P6 50 medium 10
What is the completion time for process P6?_____________
Q11. Following code is use to ensure mutual exclusion between two processes
boolean flag[2];
flag[0] = flag[1] = false;
Process P0: Process P1:
while(true){ while(true){
Compute; Compute;
while(flag[1]); while(flag[0]);
flag[0] = true; flag[1] = true;
<critical section> <critical section>
flag[0] = false; flag[1] = false; }
}
The above code satisfies
i) Mutual exclusion ii) Progress iii) Bounded wait
(a) ii only (b) ii and iii only (c) i and iii only (d) All the above
OS Gate-2020 Page 75
Q12. A computer has six tape drives, with n processes competing for them. Each process may
need up to two drives. For which maximum values of n is the system guaranteed to be
deadlock free?
(A)4 (b) 5 (c) 6 (c) 7
Q13. Which of the following statements about threads is/are false?
1. Multi-threading is only useful on a multi-processor.
2. Multi-threading is only useful when a task can be parallelized.
3. There are performance benefits to running threads of the same process one after the
other on the same processor.
4. Multi-threading requires operating system support for managing multiple PCBs.
(a) 2 and 3 only (b) 1 and 4 only (c) 2 and 4 only (d) 1, 4 and 3 only

Q14. Consider a system in which currently no processes in Ready queue. The three processes P1,
P2 and P3 are in waiting state from the beginning when they arrived. Process P1 is waiting
for input from keyboard and next CPU burst is expected to be 2 time unit. Process P2 is
waiting for disk data and its next CPU burst is expected to be 5 time unit. Process P3 is
waiting for network data and its next CPU burst is expected to be 2 time unit. The CPU
burst for any new processes are expected to be 3 time unit. A list of events that will take
place starting at this time:
Time Event
0 Disk data is delivered.
1 Process P4 is created.
2 Network data is delivered.
3 Executing process asks to sleep until tick 6.
5 Process P5 is created.
6 Process from tick 3 wake up from sleep.
7 Keyboard input is delivered.
8 Executing process asks for keyboard input.
10 Keyboard input is delivered.
What is the average waiting time of system with SRTF scheduling? _______________

Q15. Consider a system uses semaphore to protect a critical section. Some execution patterns on
timelines are given below for two processes. The convention used to represent execution
pattern is as follows: "c" indicates process is doing some computation, "S" means process
is waiting on the semaphore, "A" indicates a process has acquired a lock on semaphore; "R"
means processes has released the lock. Which of the following timelines is/are valid?
(I) Process 1: ccccAccccRccccc
Process 2: ccccccAcccccRcccc
(II) Process 1: ccccAccccccccccccRccccc
Process 2: cccccSSSSSSSSSSSSSSSSS
(III) Process 1: ccccAcccccccR
Process 2:cccccAccccR
(IV) Process 1: ccccSSSSSSSS SSSSSSSSSS ... (forever)
Process 2: cccccSSSSSSS SSSSSSSSSS ... (forever)
(a) I, II and IV only (b) II, III and IV only (c) I and II only (d) I only

OS Gate-2020 Page 76
Q16. Consider the following solution to the reader writer problem
Semaphore W=1 mutex-r=1
Shared int r=0;
Reader: Writer:
P(Mutex-r) P(Mutex-r)
r=r+1 P(W)
if (r==1) P(W) V(Mutex-r)
V(Mutex-r) write
read V(W)
P(Mutex-r)
r=r-1
if (r=0) V(W)
V(Mutex-r)
Which of the following is/ are correct?
(I) Reader Processes may starve
(II) Writer process may starve
(III) There can be deadlock
(a) II & III only (b) I and II only (c) I and III only (d) All the above

Q17. Consider the following parameters of a FAT based file system:

• Blocks are 8KB large
• FAT entries are 32 bits wide, of which 24 bits are used to store a block address
How large does the FAT structure need to be accommodate a 1GB disk?
(a)512 KB (b) 1 MB (c) 64 MB (d) 128 MB

Q18. Consider an OS with round-robin scheduling and time quantum of 500 ms, there is a
hardware device in the system which generates interrupts once every millisecond. Consider
that a process P1 is currently under running state. During its quantum P1 makes no system
calls. But there are TLB misses once in every 10 milliseconds while P is running. How many
times during its quantum does CPU enter into kernel mode?
(a)50 (b) 500 (c) 550 (d) 1000

Q19. Which of the following implementation of binary lock ensure mutual exclusion? Assuming
there are only two processes.
1. struct lock { int held = 0; } 2. struct lock { int turn = 0; }

void acquire(lock) { void acquire(lock) {

while (lock->held); while (lock->turn != this_process); }
lock->held = 1; }
void release(lock) {
void release(lock) lock->turn = other_process }
{ lock->held = 0; }
(a) Only 1 ensure mutual exclusion (b) Only 2 ensure mutual exclusion
(c) Both ensure mutual exclusion (d) Both not ensure mutual exclusion.

OS Gate-2020 Page 77
Q20. Consider an OS which uses paged segmentation with the following characteristics:
• 232 byte of physical memory
• 213 byte frame size
• at most 16 segments per process
• Maximum segment size:226 byte
What is size of a virtual address in this system (in bits)?
(a)39 bits (b) 36 bits (c) 30 bits (d) 26 bits

Q21. A system has three processes (P1, P2, P3) and three resources (R1,R2, R3). This is one
instance of R1 and R2. There are three instances of R3. P1 holds an R1 and is requesting an
R3. P2 holds an R3 and is requesting an R1. P3 holds two instancesof R3 and an R2.) Which
of the following statement is false.
1. There is no cycle in a resource allocation graph, there for no deadlock in the system.
2. There is a cycle in a resource allocation graph, there for deadlock in the system.
3. There is a cycle in a resource allocation graph, but there is no deadlock.
(a) 1 and 2 only (b) 2 and 3 only (c) 1 and 3 only (d) All are false

Q22. Consider the following three concurrent processesP1, P2, and p3, as shown below:
int count = 10;
Semaphore Lock = 1; // initial value is 1
P1{ P2 { P3{
wait(lock); wait(lock); wait(lock);
count++; count−−; printf(‘‘%d’’, count);
signal(lock); signal(lock); signal(lock);
} } }
Which of the following is not the possible output of this program?
(a) 9 (b) 10 (c) 11 (d) 12
Q23. Consider a memory management system that translates 16 bit virtual addresses to 24 bit
physical addresses. These addresses are byte addresses; the memory consists of 16 bit
words. The system uses a two-level page table, with a 4-bit first level page number, a 4- bit
second level page number, and an 8-bit offset within the page. What is the maximum
number of physical memory frames that can be addressed by this memory management
system?_______________
Q24. Consider the following 3-process concurrent program which uses semaphores S1, S2, and
S3.
Process 1 Process 2 Process 3
L1: P(S2); L2: P(S1); L3: P(S3);
print("Y"); print("D"); print("A");
V(S1); V(S3); V(S2);
goto L1; gotoL2; goto L3;
What are the minimum initial values that can be given to the semaphores so that the
processes cooperate toprint the string DAYDAYDAY?
(a) S1 = 0, S2 = 1, S3 = 0 (b) S1 = 1, S2 = 1, S3 = 0
(c) S1 = 1, S2 = 0, S3 = 1 (d) S1 = 1, S2 = 0, S3 = 0

OS Gate-2020 Page 78
Q25. Consider the following table of block requests and arrival times:
Block # Arrival time (ms)
6 0
15 5
30 8
10 18
45 21
5 23
60 25
The disk head is currently positioned over block #13 and moving toward lower number
block. Seeking across N blocks requires (N)ms and additionally change in direction
required 2ms extra. How long it will take to read all the blocks if SSTF scheduling algorithm
is used? __________ms

Q26. Consider the following parameters of an i-node based file system:

• Blocks size 1KB
• Block pointers are 8 bytes wide
• Each i-node contains 32 direct pointers, 8 single indirect pointers, 4 double indirect
pointers, and 1 triple indirect pointer.
How many entries of i-node is useful to store a file of size 64MB? _________

Q27. Consider the following two processes:

• P1, arriving at time t = 0, completing after two CPU bursts of 10ms each separated by a
single I/O burst of 15ms.
• P2, arriving at time t = 2, completing after three CPU bursts of 5ms each separated by two
I/O bursts of 10ms each.
Assume that processes enter into waiting queue after the context switch has been
performed and the context switch overhead is 1ms, do not count the context switches at
time zero and at the end. What is average turnaround time using the pre-emptive SJF
scheduling algorithm? ________ms

Q28. Consider a system with 32-bit virtual address and two-level paging with page size 4KB.
Assume that the majority of processes run on the system are exactly 4MB in size. How
many bits should be used for first level page table to minimize the total size of the page
tables?
(a) 9 (b) 10 (c) 11 (d) 12

Q29. A computer with 32-bit virtual addresses uses a two-level page table. Virtual addresses are
split into an 11-bit top-level page table field, a 9-bit second-level page table field, and an
offset. What is the minimal amount of physical memory that must be occupied by resident
page table data (assume each entry takes 4 bytes) during the execution of a process with
such an address space?
(a) 213 + 211 bytes (b) 213 bytes (c) 213 + 222 bytes (d) 211 + 29 bytes

OS Gate-2020 Page 79
Q30. Given the following:
Number of cylinders on the disk = 10,000
Number of platters = 3
Number of surfaces per platter = 2
Number of sectors per track = 1024
Number of bytes per sector = 512
Disk allocation policy = contiguous cylinders
How many cylinders should be allocated for a file of 7 Mbytes?___________

Q31. How many times Hello will be printed by the following code:_________
voiddoit() {
if (fork() == 0) {
fork();
print f("hello\n");}
return;}
int main() {
do it();
print f("hello\n");
}
Q32. Suppose a system has a disk with 2 KB disk blocks and the average access time on a block is
20 milliseconds. A process holding 40 KB of memory transitions from running to blocked
due to a resource request. How long must the process remain blocked to justify swapping
out the process?
(a) 100ms (b) 200 ms (c) 400 ms (d) 800 ms

Q33. How many page faults will the above reference string incur under the optimal page
replacement algorithm, assuming that the primary memory is initially empty?
(a)6 (b) 7 (c) 8 (d) 9

Q34. What is the working-set size after the entire string has been processed, if the initial window
size is 6?______

Q35. 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. What is the size of a page in KB in this computer?______

Q36. The address sequence generated by tracing a particular program executing in a pure
demand paging system with 200 bytes per page is 0100, 0200, 0430, 0499, 0510, 0530,
0560, 0120, 0220, 0240, 0260, 0320, and 0410. Suppose that the memory can store only
one page and if x is the address which causes a page fault then the bytes from addresses x
to x + 199 are loaded on to the memory. How many page faults will occur?__________

OS Gate-2020 Page 80
Q37. 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. How many number of page fault occurred if the optimal page
replacement policy is used?
(a) 258 (b) 259 (c) 260 (d) 261

Q38. Consider a system with the following specifications:

 System support single level page table,
 A 4-way set associative TLB with 256 entries and,
 A 4-way set associative Cache with 1024 entries.
 TLB hit rate is 90% with access time 1 cycle.
 Cache hit ratio is 80% with access time 1 cycle.
 The page fault rate when there is a miss in cache is 2%.
 Main memory access time is 20 cycles.
 Hard drive access time is 500 cycles.
 The page tables are always kept in Memory.
 The TLB accesses and cache accesses are sequential.
What is the effective access time in cycles when the cache is virtually addressed?__________

Q39. Consider a virtual memory system with 2^72 bytes virtual memory and 2^64 bytes
physical memory and, with a frame size of 4 Kbytes. Each page table entry consists of 4
status bits. A three level page table is used where the virtual address is divided into four
parts as follows:| 12 bits | 20 bits | 28 bits | 12 bits | where the first 12-bit (MSB) are used
to index into first level page table, next 20-bit are used to index into second level page table,
next 28-bit are used to index into the third level page table and last 12- bits are used as
offset within the page. What is the page table entry size in bytes of the first, second and
third level page tables respectively
(a) 7, 7, 7 (b) 5, 6, 7 (c) 6, 5, 7 (d) 5, 5, 7

Q40. Consider the implementation of the readers-writers locks. Suppose the implementation
uses a queue to manage requests. We say a request ARRIVES at the queue when the process
is trying to lock the resources. Consider the following three implementations:
1. Implementation (A) grants access to readers and writers in a strict first-in-first-out
order.
2. Implementation (B) may grant access to later readers even if a writer that arrived earlier
is blocked, when there are already some readers accessing the resource.
3. Implementation (C) will not grant access to readers as long as there is a writer in the
queue. In other words, it moves writers ahead of all readers and first honors writers.
Which of the three implementations is/are deadlock-free?
(a) 1 only (b) 1 and 2 only (d) 1 and 3 only (d) 1, 2 and 3 only

OS Gate-2020 Page 81