Operating Systems

Which one of the following CPU scheduling
algorithms cannot be preemptive?

• (a)Shortest Remaining Time First (SRTF) Scheduling
• (b)First Come First Serve (FCFS) Scheduling
• (c)Round Robin Scheduling
• (d)Priority Scheduling

Consider a CPU that has to execute two types of
processes. The first type, Actuators (A), requires a
CPU burst of 6 seconds. The second type,
Controllers (C), requires a CPU burst of 8 seconds.

A new process of type A arrives at time t = 10, 20,
30, 40, and 50 seconds. Similarly, a new process of
type C arrives at time t = 11, 22, 33, 44, and 55 seconds.

The CPU scheduling policy is First Come First
Serve (FCFS). The first process of type A starts
running at t = 10 seconds.

The average waiting time (in seconds) for the 10
processes is ______. (rounded off to one decimal place).

Processes P1, P2, P3, P4 arrive in that order at
times 0, 1, 2, and 8 milliseconds respectively, and
have execution times of 10, 13, 6, and 9
milliseconds respectively. Shortest Remaining
Time First (SRTF) algorithm is used as the CPU
scheduling policy. Ignore context switching times.
Which ONE of the following correctly gives the
average turnaround time of the four processes in
milliseconds?

• (a)22
• (b)15
• (c)37
• (d)

A computer has two processors, M1 and M2. Four
processes P1, P2, P3, P4 with CPU bursts of 20, 16, 25,
and 10 milliseconds, respectively, arrive at the same
time and these are the only processes in the system.
The
scheduler
uses
non-preemptive
priority
scheduling, with priorities decided as follows:
• M1 uses priority of execution for the processes
as, P1 > P3 > P2 > P4, i.e., P1 and P4 have
highest and lowest priorities, respectively.
• M2 uses priority of execution for the processes
as, P2 > P3 > P4 > P1, i.e., P2 and P1 have
highest and lowest priorities, respectively.

A process Pi is scheduled to a processor Mk, if the
processor is free and no other process Pj is waiting
with higher priority. At any given point of time, a
process can be allocated to any one of the free
processors without violating the execution priority
rules. Ignore the context switch time. What will be the
average
waiting
time
of
the
processes
in
milliseconds?

• (a)9.00
• (b)8.75
• (c)6.50
• (d)7.50

Consider a process P running on a CPU. Which one
or more of the following events will always trigger a
context switch by the OS that results in process P
moving to a non-running state (e.g., ready, blocked)?

• (a)P makes a blocking system call to read a block of data from the disk
• (b)tries to access a page that is in the swap space, triggering a page fault
• (c)An interrupt is raised by the disk to deliver data requested by some other process
• (d)A timer interrupt is raised by the hardware OPERATING SYSTEMS

Consider the following code snippet using the
fork() and wait() system calls. Assume that the code
compiles and runs correctly, and that the system
calls run successfully without any errors.

int x = 3;

while (x > 0) {

  fork();

  printf("hello");

  wait(NULL);

  x--;

}

The total number of times the printf statement is

executed is ________.

Which of the following statements about threads
is/are TRUE?

• (a)Threads can only be implemented in kernel space
• (b)Each thread has its own file descriptor table for open files
• (c)All the threads belonging to a process share a common stack
• (d)Threads belonging to a process are by default not protected from each other

Which of the following process state transition(s)
is/are NOT possible?

• (a)Ready to Waiting
• (b)Running to Ready
• (c)Running to Terminated
• (d)Waiting to Running

Consider a single processor system with four
processes A, B, C, and D, represented as given below,
where for each process the first value is its arrival
time, and the second value is its CPU burst time.
A (0, 10), B (2, 6), C (4, 3), and D (6, 7).
Which one of the following options gives the average
waiting times when preemptive Shortest Remaining
Time First (SRTF) and Non-Preemptive Shortest Job
First (NP-SJF) CPU scheduling algorithms are
applied to the processes?

• (a)SRTF = 6, NP-SJF = 7
• (b)SRTF = 6, NP-SJF = 7.5
• (c)SRTF = 7, NP-SJF = 7.5
• (d)SRTF = 7, NP-SJF = 8.5

Consider the following two threads T1 and T2 that
update two shared variables a and b. Assume that
initially a = b = 1. Though context switching between
threads can happen at any time, each statement of T1
or T2 is executed atomically without interruption.

T1                            T2
          a = a + 1;                 b = 2 * b;
          b = b + 1;                 a = 2 * a;

Which one of the following options lists all the
possible combinations of values of a and b after both
T1 and T2 finish execution?

• (a)(a = 4, b = 4); (a = 3, b = 3); (a = 4, b = 3)
• (b)(a = 3, b = 4); (a = 4, b = 3); (a = 3, b = 3)
• (c)(a = 4, b = 4); (a = 4, b = 3); (a = 3, b = 4)
• (d)(a = 2, b = 2); (a = 2, b = 3); (a = 3, b = 4)

Which one or more of the following options
guarantees that a computer system will transition
from user mode to kernel mode?

• (a)function call
• (b)malloc call
• (c)page fault
• (d)system call OPERATING SYSTEMS

Which one or more of the following need to be
saved on a context switch from one thread (T1) of
a process to another thread (T2) of the same process
?

• (a)Page Table base register
• (b)Stack pointer
• (c)Program Counter
• (d)General purpose register

Which one or more of the following CPU
scheduling algorithms can potentially cause
starvation?

• (a)First-in First-Out
• (b)Round Robin
• (c)Priority Scheduling
• (d)Shortest Job First.

Consider four processes P, Q, R, and S scheduled
on a CPU as per round robin algorithm with a time
quantum of 4 units. The processes arrive in the
order P, Q, R, S, all at time t = 0. There is exactly
one context switch from S to Q, exactly one context
switch from R to Q, and exactly two context
switches from Q to R. There is no context switch
from S to P. Switching to a ready process after the
termination of another process is also considered a
context switch. Which one of the following is NOT
possible as CPU  burst time (in time units) of these
processes?

• (a)P = 4, Q = 10, R = 6, S = 2
• (b)P = 2, Q = 9, R = 5, S = 1
• (c)P = 4, Q = 12, R = 5, S = 4
• (d)P = 3, Q = 7, R = 7, S = 3

Which of the following standard C library functions
will always invoke a system call when executed
from  a single-threaded process in a UNIX/Linux
operating system?

• (a)exit
• (b)malloc
• (c)sleep
• (d)strlen

There are 6 jobs with distinct difficulty levels, and 3
computers with distinct processing speeds. Each job
is assigned to a computer such that:

- The fastest computer gets the toughest job and the
slowest computer gets the easiest job.

- Every computer gets at least one job

The number of ways in which this can be done is
_________

Which of the following statement(s) is/are correct in
the context of CPU scheduling?

• (a)Turnaround time includes waiting time.
• (b)Round-robin policy can be used even when the CPU time required by each of the processes is not known apriori.
• (c)Implementing pre-emptive scheduling needs hardware support.
• (d)The goal is to only maximize CPU utilization and minimize throughput. OPERATING SYSTEMS

Consider the following multi-threaded code
segment (in a mix of C and pseudocode), invoked
by two processes P1 and P2, and each of the
processes spawns two threads T1 and T2:

int x = 0;   // global

Lock L1;    // global

main() {

create a thread to execute foo();  // Thread T1

create a thread to execute foo();  // Thread T2

wait for the two threads to finish execution;

print (x);}

foo () {

 int y = 0;

Acquire L1;

x = x + 1;

 y = y + 1;

Release L1;

print (y);}

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

• (a)At least one of P1 and P2 will print the value of x as 4.
• (b)At least one of the threads will print the value of y as 2.
• (c)Both T1 and T2, in both the processes, will print the value of y as 1.
• (d)Both P1 and P2 will print the value of x as 2.

Three processes arrive at time zero with CPU bursts
of 16, 20 and 10 milliseconds. If the scheduler has
prior knowledge about the length of the CPU
bursts, the minimum achievable average waiting
time for these processes in a non-preemptive
scheduler
(rounded
to
nearest
integer)
is
_________milliseconds.

Consider the following set of processes assumed to
have arrived at time 0. Consider the CPU scheduling
algorithms Shortest Job First (SJF) and Round Robin
(RR). For RR, assume that the processes are
scheduled in the order P1, P2, P3, P4.

Processes
P1
P2
P3
P4
Burst time (in ms)
8
7
2
4

If the time quantum for RR is 4 ms, then the

absolute value of the difference between the

average turnaround times (in ms) of SJF and RR

(round off to 2 decimal places) is ______

Consider the following statements about process state
transitions for a system using preemptive scheduling.

I. A running process can move to ready state.

II. A ready process can move to running state.

III. A blocked process can move to running state.

IV. A blocked process can move to ready state.

Which of the above statements are TRUE?

• (a)I, II, and III only
• (b)II and III only
• (c)I, II, and IV only
• (d)I, II, III and IV only

Consider the following four processes with arrival
times (in milliseconds) and their length of CPU bursts
(in milliseconds) as shown below:

Process
P1 P2 P3 P4
Arrival time
0
1
3
4
CPU burst time
3
1
3
Z

OPERATING SYSTEMS
These processes are run on a single processor
using preemptive Shortest Remaining Time First
scheduling algorithm. If the average waiting time
of the processes is 1 millisecond, then the value of
Z is ______

Consider the following C program is executed on a
Unix/Linux system:

#include <unistd.h>

int main()

{

int i;

for(i = 0; i < 10; i++)

if(i % 2 == 0)

fork();

return 0;

}
The total number of child processes created is
__________.

Consider the following CPU processes with arrival
times (in milliseconds) and length of CPU bursts
(in milliseconds) as given below:

Process: P1, P2, P3, P4

Arrival Time: 0, 3, 5, 6

Burst Time: 7, 3, 5, 2
If the pre-emptive shortest remaining time first
scheduling algorithm is used to schedule the

processes, then the average waiting time across

all processes is ______ milliseconds.

Threads of a process share

• (a)global variables but not heap
• (b)heap but not global variables
• (c)neither global variables nor heap
• (d)both heap and global variables

Which of the following is/are shared by all the threads
in a process?

I. Program counter

II. Stack

III. Address space

IV. Registers

• (a)(I) and (II) only
• (b)(III) only
• (c)(IV) only
• (d)(III) and (IV) only

Consider the set of processes with arrival time (in
milliseconds), CPU burst time (in milliseconds), and
priority (0 is the highest priority) shown below. None
of the processes have I/O burst time.

Proces
Arrival
Time
Burst
Time
Priority
P1
0
11
2
P2
5
28
0
P3
12
2
3
P4
2
10
1
P5
9
16
4

The average waiting time (in milliseconds) of all the
processes using the pre-emptive priority scheduling
algorithm is __________.

Consider an arbitrary set of CPU-bound processes
with unequal CPU burst lengths submitted at the same
time to a computer system. Which one of the
following process scheduling algorithms would
minimize the average waiting time in the ready
queue?

• (a)Shortest remaining time first
• (b)Round-robin with time quantum less than the shortest CPU burst
• (c)Uniform random
• (d)Highest priority first with priority proportional to CPU burst length OPERATING SYSTEMS

Consider the following processes, with the arrival
time and the length of the CPU burst given in
milliseconds. The scheduling algorithm used is the
pre-emptive shortest remaining-time first.

Process
Arrival Time
Burst Time
P1
0
10
P2
3
6
P3
7
1
P4
8
3

The average turn-around time of these processes is
_________ milliseconds

The maximum number of processes that can be in
Ready state for a computer system with n CPUs is

• (a)n
• (b)n2
• (c)2N
• (d)Independent of n

Which of the following is FALSE about SJF
(Shortest Job First Scheduling)?
S1: It causes minimum average waiting time

S2: It can cause starvation

• (a)Only S1
• (b)Only S2
• (c)Both S1 and S2
• (d)Neither S1 or S2

For the processes listed in the following table, which
of the following scheduling schemes will give the
lowest average turnaround time?

Proces
Arrival Time
Processing
Time
A
0
3
B
1
6
C
4
4
D
6
2

• (a)First Come First Serve
• (b)Non-pre-emptive Shortest Job First
• (c)Shortest Remaining Time First
• (d)Round Robin with Quantum value two

Consider a uniprocessor system executing three tasks
T1, T2 and T3, each of which is composed of an
infinite sequence of jobs (or instances) which arrive
periodically at intervals of 3, 7 and 20 milliseconds,
respectively. The priority of each task is the inverse
of its period and the available tasks are scheduled in
order of priority, with the highest priority task
scheduled first. Each instance of T1, T2 and T3
requires an execution time of 1, 2 and 4 milliseconds,
respectively. Given that all tasks initially arrive at the
beginning of the 1st millisecond and task preemptions
are allowed, the first instance of T3 completes its
execution
at
the
end
of
______________
milliseconds.

Which one of the following is FALSE?

• (a)User level threads are not scheduled by the kernel.
• (b)When a user level thread is blocked, all other threads of its process are blocked.
• (c)Context switching between user level threads is faster than context switching between kernel level threads
• (d)Kernel level threads cannot share the code segment. OPERATING SYSTEMS

Three processes A, B and C each execute a loop of
100 iterations. In each iteration of the loop, a
process performs a single computation that requires
tc CPU milliseconds and then initiates a single I/O
operation that lasts for tio milliseconds. It is
assumed that the computer where the processes
execute has sufficient number of I/O devices and
the OS of the computer assigns different I/O
devices to each process. Also, the scheduling
overhead of the OS is negligible. The processes
have the following characteristics:

Process id
TC
Tio
A
100 ms
500 ms
B
350 ms
500 ms
C
200 ms
500 ms

The processes A, B, and C are started at times 0, 5
and 10 milliseconds respectively, in a pure time
sharing system (round robin scheduling) that uses a
time slice of 50 milliseconds. The time in
milliseconds at which process C would complete its
first
I/O
operation
is
___________.

An operating system uses the shortest remaining
time first scheduling algorithm for pre-emptive
scheduling of processes. Consider the following set
of processes with their arrival times and CPU burst
times (in milliseconds):
Process
Arrival Time
Burst Time
P1
0
12
P2
2
4
P3
3
6
P4
8
5

The average waiting time (in milliseconds) of the
processes is ______.

Consider the following set of processes that need to
be scheduled on a single CPU. All the times are given
in milliseconds.

Process
Name
Arrival Time
Execution
Time
A
0
6
B
3
2
C
5
4
D
7
6
E
10
3

Using the shortest remaining time first scheduling
algorithm, the average process turnaround time (in
msec) is

A scheduling algorithm assigns priority proportional
to the waiting time of a process. Every process starts
with priority zero (the lowest priority). The scheduler
re-evaluates the process priorities every T time unit
and decides the next process to schedule. Which one
of the following is TRUE if the processes have no I/O
operations and all arrive at time zero?

• (a)This algorithm is equivalent to the first-come- first-serve algorithm.
• (b)This scheduling algorithm behaves like Round-Robin scheduling.
• (c)This algorithm is equivalent to the shortest-job- first algorithm.
• (d)This algorithm is equivalent to the shortest- remaining-time-first algorithm.

A process executes the code

fork ();

fork ();

fork ();

The total number of child processes created is

• (a)3
• (b)4
• (c)7
• (d)8 OPERATING SYSTEMS

Consider the 3 processes, P1, P2 and P3 shown in
the table.
Process
Arrival Time  Time Units
Required
Time
P1
0
5
P2
1
7
P3
3
4

The completion order of the 3 processes under the
policies FCFS and RR2 (round robin scheduling
with CPU quantum of 2 time units) are

• (a)FCFS: P1, P2, P3 RR2: P1, P2, P3
• (b)FCFS: P1, P3, P2 RR2: P1, P3, P2
• (c)FCFS: P1, P2, P3 RR2: P1, P3, P2
• (d)FCFS: P1, P3, P2 RR2: P1, P2, P3

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

• (a)(t1) > (t2)
• (b)(t1) = (t2)
• (c)(t1) < (t2)
• (d)Nothing can be said about the relation between t1 and t2

A thread is usually defined as a "light weight
process" because an operating system (OS)
maintains smaller data structures for a thread than
for a process. In relation to this, which of the
following is TRUE?

• (a)On per-thread basis, the OS maintains only CPU register state.
• (b)The OS does not maintain a separate stack for each thread.
• (c)On a per-thread basis, the OS does not maintain virtual memory state.
• (d)On a per thread basis, the OS maintains only scheduling and accounting information.

Consider the following table of arrival time and burst
time for three processes P0, P1 and P2.
Process
Arrival Time
Burst Time
P0
0 ms
9 ms
P1
1 ms
4 ms
P2
2 ms
9 ms

The pre-emptive shortest job first scheduling
algorithm is used. Scheduling is carried out only at
arrival or completion of processes. What is the
average waiting time for the three processes?

• (a)5
• (b)4.33
• (c)6.33
• (d)7.33

Which of the following statements is/are true?

I. Shortest remaining time first scheduling may cause
starvation

II. Preemptive scheduling may cause starvation

III. Round robin is better than FCFS in terms of
response time

• (a)I only
• (b)I and II only
• (c)II and III only
• (d)I, II and III OPERATING SYSTEMS

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

Now consider the following statements :
I. If a process makes a transition D, it would result
in
another
process
making
transition
A
immediately.
II. A process P2 in a blocked state can make
transition E while another process P1 is in running
state.

III. The OS uses preemptive scheduling.

IV. The OS uses non-preemptive scheduling.

Which of the above statements are TRUE ?

• (a)I and II
• (b)I and III
• (c)II and III
• (d)II and IV

A process executes the following code:

for(i=0;i<n;i++)
    fork();

The total number of child processes created is

• (a)n
• (b)2n-1
• (c)2n
• (d)2n+1 - 1

An operating system uses the Shortest Remaining
Time First (SRT) process scheduling algorithm.
Consider the arrival times and execution times for the
following processes:

Process Execution Time Arrival Time
P1
20
0
P2
25
15
P3
10
30
P4
15
45

What is the total waiting time for process P2?

• (a)5
• (b)15
• (c)40
• (d)55

Consider the following statements about user level
threads and kernel level threads. Which one of the
following statements is FALSE?

• (a)Context switch time is longer for kernel level threads than for user level threads.
• (b)User level threads do not need any hardware support.
• (c)Related kernel level threads can be scheduled on different processors in a multi-processor system.
• (d)Blocking one kernel level thread blocks all related threads. OPERATING SYSTEMS

Group 1 contains some CPU scheduling algorithms
and Group 2 contains some applications. Match
entries in Group 1 to entries in Group 2.

Group 1
P. Gang Scheduling
Q. Rate Monotonic Scheduling
R. Fair Share Scheduling

Group 2
1.
Guaranteed Scheduling
2.
Real-time Scheduling
3.
Thread Scheduling

• (a)P-3; Q-2; R-1
• (b)P-1; Q-2; R-3
• (c)P-2; Q-3; R-1
• (d)P-1; Q-3; R-2

Consider three CPU-intensive processes, which
require 10, 20 and 30 time units and arrive at times
0, 2 and 6, respectively. How many context
switches are needed if the operating system
implements a Shortest Remaining Time First
(SRTF) scheduling algorithm?

Do not count the context switches at time zero and
at the end.

• (a)1
• (b)2
• (c)3
• (d)4

Consider three processes (process id 0, 1, 2,
respectively) with compute time bursts 2, 4, and 8
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

• (a)13 units
• (b)14 units
• (c)15 units
• (d)16 units

Consider three processes, all arriving at time zero,
with total execution time of 10, 20, and 30 units,
respectively. Each process spends the first 20% of
execution time doing I/O, the next 70% of time doing
computation, and the last 10% of time doing I/O
again.

The operating system uses a shortest remaining
compute time first scheduling algorithm and
schedules a new process either when the running
process gets blocked on I/O or when the running
process finishes its compute burst. Assume that all
I/O operations can be overlapped as much as possible.

For what percentage of time does the CPU remain
idle?

• (a)0%
• (b)10.6%
• (c)30.0%
• (d)89.4%

Consider the following code fragment:

if (fork() == 0)

{

  a = a + 5;

 printf("%d, %p\n", a, &a);

}

else

{

a = a - 5;

 printf("%d, %p\n", a, &a);

}

Let u, v be the values printed by the parent process

and x, y be the values printed by the child process.

Which one of the following is TRUE?

• (a)u = x + 10 and v = y
• (b)u = x + 10 and v ≠ y
• (c)u + 10 = x and v = y
• (d)u + 10 = x and v ≠ y OPERATING SYSTEMS

Consider three processes P1, P2, and P3 running
identical code, as shown in the pseudocode below.
A and B are two binary semaphores initialized to 1
and 0, respectively. X is a shared variable
initialized to 0. Each line in the pseudocode is
executed atomically.

Pseudocode of P1, P2, and P3:

wait(A);
print(*);
X=X+1;

if(X==2)
{
    print($);
    signal(B);
}

signal(A);

wait(B);
print(#);
signal(B);

Assume that any of the three processes can start to
execute first and context switching can happen
between these processes at any arbitrary time and
in any arbitrary order.

Which of the following patterns is/are possible to
be generated as an outcome of the execution of
these three processes?

• (a)**$*###
• (b)**$#*##
• (c)**$##*#
• (d)***$###

Consider a multi-threaded program with two threads
T1 and T2. The threads share two semaphores: s1
(initialized to 1) and s2 (initialized to 0). The threads
also share a global variable x (initialized to 0). The
threads execute the code shown below.

T1:

wait(s1);

x = x + 1;

 print(x);

 wait(s2);

 signal(s1);

T2:

wait(s1);

 x = x + 1;

 print(x);

 signal(s2);

 signal(s1);
Which of the following outcomes is/are possible
when threads T1 and T2 execute concurrently?

• (a)T1 runs first and prints 1, T2 runs next and prints 2
• (b)T2 runs first and prints 1, T1 runs next and prints 2
• (c)T1 runs first and prints 1, T2 does not print anything (deadlock)
• (d)T2 runs first and prints 1, T1 does not print anything (deadlock) OPERATING SYSTEMS

Consider the two functions incr and decr shown
below.

          incr(){
                     wait(s);

                     X = X+1;
                      signal(s);
         }
         decr(){
                     wait(s);

                     X = X-1;
                      signal(s);
         }

There are 5 threads each invoking incr once, and 3
threads each invoking decor once, on the same
shared variable X. The initial value of X is 10.

Suppose there are two implementations of the
semaphore s, as follows:

I-1: s is a binary semaphore initialized to 1.
I-2: s is a counting semaphore initialized to 2.

Let V1, and V2 be the values of X at the end of the
execution of all the threads with implementations I-
1, and I-2, respectively.

Which one of the following choices corresponds to
the minimum possible values of V1, V2,
respectively?

• (a)15,7
• (b)7,7
• (c)12,7
• (d)12,8

Consider the following threads T1, T2, and T3

executing on a single processor, synchronized using
three binary semaphore variables S1, S2, and
S3,operated upon using standard wait() and signal().
The  threads can be context switched in any order
and at any time.
T1:
 while(true) {
 wait(S3);
 print("C");
 signal(S2);
 }
T2:
 while(true) {
 wait(S1);
 print("B");
 signal(S3);
 }
T3:
 while(true) {
 wait(S2);
 print("A");
 signal(S1);
 }
Which initialization of the semaphores would print
the sequence BCABCABCA...?

• (a)S1 = 1; S2 = 1; S3 = 1
• (b)S1 = 1; S2 = 1; S3 = 0
• (c)S1 = 1; S2 = 0; S3 = 0
• (d)S1 = 0; S2 = 1; S3 = 1 OPERATING SYSTEMS

Consider the following pseudocode, where S is a
semaphore initialized to 5 in line #2 and counter is
a shared variable initialized to 0 in line#1. Assume
that the increment operation in line#7 is not atomic.

1. int counter = 0

2. Semaphore S = init(5);

3. void parop(void)

4. {

5.

wait(S);

6.

 wait(S);

7.

  counter++;

8.
        signal(S);

9.                signal(S);

10.}

If five threads execute the function parop
concurrently, which of the following program
behavior(s) is/are possible?

• (a)The value of counter is 5 after all the threads successfully complete the execution of parop.
• (b)The value of counter is 1 after all the threads successfully complete execution of parop.
• (c)The value of counter is 0 after all the threads successfully complete the execution of parop.
• (d)There is a deadlock involving all the threads.

Consider a computer system with multiple shared
resource types, with one instance per resource type.
Each instance can be owned by only one process at
a time. Owning and freeing of resources are done
by holding a global lock (L). The following scheme
is used to own a resource instance:

function OWNRESOURCE(Resource R)

Acquire lock L // a global lock

if R is available then

Acquire R

Release lock L

else

if R is owned by another process P then
           Terminate P, after releasing all resources
owned by P

Acquire R

Restart P

Release lock L

end if
         end if

end if

end function

Which of the following choice(s) about the above
scheme is/are correct?

• (a)The scheme violates the mutual exclusion property.
• (b)The scheme ensures that deadlocks will not occur.
• (c)The scheme may lead to starvation.
• (d)The scheme may lead to live-lock.

Each of a set of n processes executes the following
code using two semaphores a and b initialized to 1
and 0, respectively. Assume that count is a shared
variable initialized to 0 and not used in CODE
SECTION P.

CODE SECTION P

wait (a);
           count = count+1;

if (count==n) signal (b);

signal (a); wait (b); signal (b);

CODE SECTION Q

What does the code achieve?

• (a)It ensures that all processes execute CODE SECTION P mutually exclusively.
• (b)It ensures that at most two processes are in CODE SECTION Q at any time.
• (c)It ensures that no process executes CODE SECTION Q before every process has finished CODE SECTION P.
• (d)It ensures that at most n-1 processes are in CODE SECTION P at any time. OPERATING SYSTEMS

Consider three concurrent processes P1, P2 and P3
as shown below, which access a shared variable

D initialized to 100.
P1: D = D + 20
P2: D = D - 50
P3: D = D + 10
The processes are executed on a uniprocessor
system running a time-shared operating system. If
the minimum and maximum possible values of D
after the three processes have completed
execution are X and Y respectively, then the value
of Y - X is ______

Consider the following solution to the producer-
consumer synchronization problem. The shared
buffer size is N. Three semaphores empty,
full and mutex are defined with respective initial
values of 0, N and 1. Semaphore empty denotes the
number of available slots in the buffer, for the
consumer to read from. Semaphore full denotes the
number of available slots in the buffer, for the
producer to write to. The placeholder variables,
denoted by P, Q, R and S, in the code below can be
assigned either empty or full. The valid semaphore
operations are: wait () and signal ().
Producer
Consumer
do{
do {
wait (P);
wait (R);
wait (mutex);
wait mutex);
//Add item to buffer
//Consume item from
buffer
Signal (mutex);
Signal (mutex);
Signal (Q);
Signal (S);
} while (1);
} while (1);

Which one of the following assignments to P, Q, R
and S will yield the correct solution?

• (a)P: full, Q: full, R: empty, S: empty
• (b)P: empty, Q: empty, R: full, S: full
• (c)P: full, Q: empty, R: empty, S: full
• (d)P: empty, Q: full, R: full, S: empty

Consider the following proposed solution for the
critical section problem. There are n processes:
P0...Pn-1. In the code, function pmax returns an integer
not smaller than any of its arguments. For all i, t[i] is
initialized to zero.

Code for Pi:

do {

c[i]=1; t[i] = pmax (t[0],...,t[n-1]) +1; c[i]=0;

           for every j ≠ i in {0,...,n-1} {

  while (c[j]);

  while (t[j]! = 0 && t[j]<=t[i]);

 }

Critical Section;

t[i]=0;

Remainder Section;

} while (true);

Which one of the following is TRUE about the above
solution?

• (a)At most one process can be in the critical section at any time.
• (b)The bounded wait condition is satisfied
• (c)The progress condition is satisfied
• (d)It cannot cause a deadlock.

Consider the following two-process synchronization
solution.

Process 0
Process 1
Entry: loop while
(turn == 1);
Entry: loop while (turn == 0);

(critical section )
( Critical section)
Exit: turn = 1;
Exit: turn = 0;

The shared variable turn is initialized to zero. Which
one of the following is TRUE?

• (a)This is a correct two-process synchronization solution.
• (b)This solution violates mutual exclusion requirement.
• (c)This solution violates the progress requirement.
• (d)This solution violates the bounded wait requirement. OPERATING SYSTEMS

Consider a non-negative counting semaphore S.
The operation P(S) decrements S, and V(S)
increments S. During an execution, 20 P(S)
operations and 12 V(S) operations are issued in
some order. The largest initial value of S for which
at least one P(S) operation will remain blocked is
_________.

The following two functions P1 and P2 that share a
variable B with an initial value of 2 execute
concurrently.

P1()

{

   C = B – 1;

   B = 2*C;

}

P2()

{

  D = 2 * B;

 B = D - 1;

}

The number of distinct values that B can possibly
take after the execution is?

• (a)3
• (b)4
• (c)5
• (d)6

Two processes X and Y need to access a critical
section. Consider the following synchronization
construct used by both the processes.

Here, varP and varQ are shared variables and both
are initialized to false. Which one of the following
statements is true?

• (a)The proposed solution prevents deadlock but fails to guarantee mutual exclusion.
• (b)The proposed solution guarantees mutual exclusion but fails to prevent deadlock.
• (c)The proposed solution guarantees mutual exclusion and prevents deadlock.
• (d)The proposed solution fails to prevent deadlock and fails to guarantee mutual exclusion.

Consider the procedure below for the Producer-
Consumer problem which uses semaphores:

semaphore n = 0;
semaphore s = 1;
void producer() void consumer()
{
    while(true) while(true)
    {
        produce();
        semWait(s) ;
        addToBuffer();
        semSignal(s);
        semSignal(n);
    }
}
void consumer()
{
    while(true)
    {
        semWait(s);
        semWait(n);
        removeFromBuffer();
        semSignal(s);
        consume();
    }
}

OPERATING SYSTEMS

Which one of the following is TRUE?

• (a)The producer will be able to add an item to the buffer, but the consumer can never consume it.
• (b)The consumer will remove no more than one item from the buffer.
• (c)Deadlock occurs if the consumer succeeds in acquiring semaphore s when the buffer is empty.
• (d)The starting value for the semaphore n must be 1 and not 0 for deadlock-free operation.

A certain computation generates two arrays a and b
such that a[i]=f(i) for 0 ≤ i< n and b[i]=g(a[i]) for 0
≤ i< n. Suppose this computation is decomposed
into two concurrent processes X and Y such that X
computes the array a and Y computes the array b.
The processes employ two binary semaphores R
and S, both initialized to zero. The array a is shared
by the two processes. The structures of the
processes are shown below.

Process X:
Process Y:
private i;
private i;
for (i= 0; i< n; i + +){
for (i= 0; i< n; i + +){

a[i] = f(i);
EntryY (R, S);
ExitX (R, S);
b[i] = g(a[i]);
}
}

Which one of the following represents the
CORRECT implementations of Exit X and Entry
Y?

• (a)ExitX(R, S) { P(R); V(S); } EntryY(R, S) { P(S); V(R); }
• (b)ExitX(R, S) { V(R); V(S); } EntryY(R, S) { P(R); P(S); }
• (c)ExitX(R, S) { P(S); V(R); } EntryY(R, S) { V(S); P(R); }
• (d)ExitX(R, S) { V(R); P(S); } EntryY(R,S) { V(S); P(R); }

A shared variable x, initialized to zero, is operated on
by four concurrent processes W, X, Y, Z as follows.
Each of the processes W and X reads x from memory,
increments by one, stores it to memory, and then
terminates. Each of the processes Y and Z reads x
from memory, decrements by two, stores it to
memory, and then terminates. Each process before
reading x invokes the P operation (i.e. wait) on a
counting semaphore S and invokes the V operation
(i.e., signal) on the semaphore S after storing x to

OPERATING SYSTEMS
memory. Semaphore S is initialized to two. What is
the maximum possible value of x after all processes
complete execution?

• (a)-2
• (b)-1
• (c)1
• (d)2

Fetch_And_Add (X, i) is an atomic Read-Modify-
Write instruction that reads the value of memory
location X, increments it by the value i, and returns
the old value of X. It is used in the pseudocode
shown below to implement a busy-wait lock. L is
an unsigned integer shared variable initialized to 0.
The value of 0 corresponds to lock being available,
while any non-zero value corresponds to the lock
being not available.

AcquireLock(L) {

while (Fetch_And_Add(L,1))

  L = 1;

}

ReleaseLock(L) {

L = 0;

}

This implementation........

• (a)fails as L can overflow
• (b)fails as L can take on a non-zero value when the lock is actually available.
• (c)works correctly but may starve some ` processes.
• (d)works correctly without starvation

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

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

Which one of the following statements describes the
properties achieved?

• (a)Mutual exclusion but not progress
• (b)Progress but not mutual exclusion
• (c)Neither mutual exclusion nor progress
• (d)Both mutual exclusion and progress

The following program consists of 3 concurrent
processes and 3 binary semaphores. The semaphores
are initialized as S0 = 1, S1 = 0, S2=0.

Process P0
Process P1
Process P2
while (true) {
wait (S1);
wait (S2);
wait (S0);
Release (S0);
Release (S0);

print '0'

release (S1);

release (S2);

}

How many times will the process P0 print '0'?

• (a)At least twice
• (b)exactly twice
• (c)exactly thrice
• (d)exactly one

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

void enter_CS(X)
{
    while test-and-set(X) ;
}

void leave_CS(X)
{

OPERATING SYSTEMS
    X = 0;
}

In the above solution, X is a memory location
associated with the CS and is initialized to 0. Now
consider the following statements:

I. The above solution to the CS problem is
deadlock-free.
II.
The
solution
is
starvation
free.
III. The processes enter CS in FIFO order.
IV. More than one process can enter CS at the same
time.

Which of the above statements is TRUE?

• (a)I only
• (b)I and II
• (c)II and III
• (d)IV only

The P and V operations on counting semaphores,
where s is a counting semaphore, are defined as
follows:
P(s):
 s = s - 1;
 if s < 0 then wait;
V(s):
 s = s + 1;
 if s ≤ 0 then wake up process waiting on s;

Assume that Pb and Vb, the wait and signal
operations on binary semaphores, are provided.
Two binary semaphores xb and yb are used to
implement the semaphore operations P(s) and V(s)
as follows:
P(s):
 Pb(xb);
 s = s - 1;
 if (s < 0)
 {
  Vb(xb);
  Pb(yb);
 }
 else Vb(xb);
V(s):
 Pb(xb);
 s = s + 1;
 if (s ≤ 0) Vb(yb);
 Vb(xb);

The initial values of xb and yb are respectively

• (a)0 and 0
• (b)0 and 1
• (c)1 and 0
• (d)1 and 1

Two processes, P1 and P2, need to access a critical
section
of
code.
Consider
the
following
synchronization construct used by the processes:

/* P1 */
while (true) {
    wants1 = true;
    while (wants2 == true);
    /* Critical Section */
    wants1 = false;
}
/* Remainder section */

/* P2 */
while (true) {
    wants2 = true;
    while (wants1 == true);
    /* Critical Section */
    wants2 = false;
}
/* Remainder section */

Here, wants1 and wants2 are shared variables,
initialized to false.

Which one of the following statements is TRUE
about the above construct?

• (a)It does not ensure mutual exclusion.
• (b)It does not ensure bounded waiting.
• (c)It requires that processes enter the critical section in strict alternation.
• (d)It does not prevent deadlocks, but ensures mutual exclusion.

The
atomic
fetch-and-set
x,
y
instruction
unconditionally sets the memory location x to 1 and
fetches the old value of x in y without allowing any
intervening access to the memory location x.
Consider the following implementation of P and V
functions on a binary semaphore S.

void P (binary_semaphore *s) {

unsigned y;

OPERATING SYSTEMS

unsigned *x = &(s->value);

do {

fetch-and-set x, y;

}  while (y);

}

void V (binary_semaphore *s) {

S->value = 0;

}

Which one of the following is true?

• (a)The implementation may not work if Context switching is disabled in P
• (b)Instead of using fetch-and-set, a pair of normal load/store can be used
• (c)The implementation of V is wrong
• (d)The code does not implement a binary semaphore

Barrier is a synchronization construct where a set of
processes synchronize globally. Let the number of
processes be three and S be a binary semaphore.
Consider the following implementation:
void barrier(void) {
1:  P(S);
2:  process_arrived++;
3:  V(S);
4:  while (process_arrived != 3);
5:  P(S);
6:  process_left++;
7:  if (process_left == 3) {
8:      process_arrived = 0;
9:      process_left = 0;
10: }
11: V(S);
}
Variables process_arrived and process_left are
shared and initialized to 0.
Which one of the following is true?

• (a)The barrier implementation is wrong due to the use of binary semaphore S
• (b)The barrier implementation may lead to a deadlock if two barrier invocations are used in immediate succession
• (c)Lines 6 to 10 need not be inside a critical section
• (d)The barrier implementation is correct if there are only two processes instead of three

Barrier is a synchronization construct where a set of
processes synchronize globally. Let the number of
processes be three and S be a binary semaphore.
Consider the following implementation:

void barrier(void) {

1:  P(S);

2:  process_arrived++;

3:  V(S);

4:  while (process_arrived != 3);

5:  P(S);

6:  process_left++;

7:  if (process_left == 3) {

8:  process_arrived = 0;

9: process_left = 0;

10: }

11: V(S);

}

The variables process_arrived and process_left are
shared and initialized to zero.

Which one of the following rectifies the problem in
the implementation?

• (a)Lines 6 to 10 are simply replaced by process_arrived--
• (b)At the beginning of the barrier the first process to enter waits until process_arrived becomes zero before proceeding to execute P(S)
• (c)Context switch is disabled at the beginning of the barrier and re-enabled at the end
• (d)The variable process_left is made private instead of shared OPERATING SYSTEMS

With respect to deadlocks in an operating system,
which of the following statements is/are FALSE?

• (a)Banker's algorithm is used to prevent deadlocks
• (b)Deadlock formation can be prevented by ensuring that the hold and wait condition is not allowed
• (c)An assignment edge in a resource allocation graph is marked from a process to a resource
• (d)A safe state guarantees that all processes can finish without formation of a deadlock

Consider a system consisting of k instances of a
resource R, being shared by 5 processes.

Assume:
● Each process requires a maximum of two
instances of resource R.
● A process can request or release only one
instance at a time.
● A process can request the second instance only
after acquiring the first instance.

The minimum value of k for the system to be
deadlock-free is ______.

P = {P1, P2, P3, P4} consists of all active processes
in an operating system. R = {R1, R2, R3, R4} consists
of single instances of distinct types of resources in the
system.

The resource allocation graph has the following
assignment and claim edges.

Assignment edges: R1 → P1, R2 → P2, R3 → P3, R4
→ P4 (the assignment edge R1 → P1 means resource
R1 is assigned to process P1 , and so on for others)

Claim edges: P1 → R2, P2 → R3, P3 → R1, P2 →
R4, P4 → R2 (the claim edge P1 → R2 means process
P1 is waiting for resource R2 , and so on for others)

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

• (a)Aborting P1 makes the system deadlock free.
• (b)Aborting P3 makes the system deadlock free
• (c)Aborting P2 makes the system deadlock free
• (d)Aborting P1 and P4 makes the system deadlock free.

Which of the following statements is/are TRUE with
respect to deadlocks?

• (a)The circular wait is a necessary condition for the formation of deadlock
• (b)In a system where each resource has more than one instance, a cycle in its wait-for graph indicates the presence of a deadlock.
• (c)If the current allocation of resources to processes leads the system to an unsafe state, then deadlock will necessarily occur.
• (d)In the resource-allocation graph of a system, if every edge is an assignment edge, then the system is not in a deadlock state. OPERATING SYSTEMS

Consider the following snapshot of a system
running  n concurrent processes. Process i is
holding Xi instances of a resource R, 1 ≤ i ≤ n.
Assume that all instances of R are currently in use.
Further, for all i process i can place a request for at
most Yi additional instances of R while holding the
Xi instances it already has. Of the n processes, there
are exactly two processes p and q such that Yp = Yq
= 0. Which one of the following conditions
guarantees that no other process apart from p and q
can complete execution?

• (a)Min (Xp, Xq) ≥ Min {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q}
• (b)Xp + Xq< Max {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q
• (c)Min (Xp, Xq) ≤ Max {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q}
• (d)Xp + Xq< Min {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q}

In a system, there are three types of resources: E, F
and G. Four processes P0, P1, P2 and P3 execute
concurrently. At the outset, the processes have
declared their maximum resource requirements
using a matrix named Max as given below. For
example, Max [P2, F] is the maximum number of
instances of F that P2 would require. The number of
instances of the resources allocated to the various
processes at any given state is given by a matrix
named Allocation.

Consider a state of the system with the Allocation
matrix as shown below, and in which 3 instances of
E and 3 instances of F are the only resources
available.

Allocation

E
F
G
P0
1
0
1
P1
1
1
2
P2
1
0
3
P3
2
0
0

Max

E
F
G
P0
4
3
1
P1
2
1
4
P2
1
3
3
P3
5
4
1

From the perspective of deadlock avoidance, which
one of the following is true?

• (a)The system is in safe state.
• (b)The system is not in safe state, but would be safe if one more instance of E were available.
• (c)The system is not in safe state, but would be safe if one more instance of F were available.
• (d)The system is not in safe state, but would be safe if one more instance of G were available.

Consider a system with 3 processes that share 4
instances of the same resource type. Each process can
request a maximum of K instances. Resource
instances can be requested and released only one at a
time. The largest value of K that will always avoid
deadlock is _________.

A multithreaded program P executes with x number
of threads and used y number of locks for ensuring
mutual exclusion while operating on shared memory
locations. All locks in the program are non-reentrant,
i.e., if a thread holds a lock l, then it cannot re-acquire
lock l without releasing it. If a thread is unable to
acquire a lock, it blocks until the lock becomes
available. The minimum value of x and the minimum
value of y together for which execution of P can result
in a deadlock are:

• (a)x = 1, y = 2
• (b)x = 2, y = 1
• (c)x = 2, y = 2
• (d)x = 1, y = 1 OPERATING SYSTEMS

A system shares 9 tape drives. The current
allocation and maximum requirement of tape drives
for three processes are shown below:

Proces
s
Current
Allocation
Maximum
Requirement
P1
3
7
P2
1
6
P3
3
5

Which of the following best describes the current
state of the system?

• (a)Safe, Deadlocked
• (b)Safe, Not Deadlocked
• (c)Not Safe, Deadlocked
• (d)Not Safe,Not Deadlocked

A system has 6 identical resources and N processes
competing for them. Each process can request at
most 2 resources. Which one of the following
values of N could lead to a deadlock?

• (a)1
• (b)2
• (c)3
• (d)6

Consider the following policies for preventing
deadlock in a system with mutually exclusive
resources.

I. Processes should acquire all their resources at the
beginning of execution.  If any resource is not
available, all resources acquired so far are released.

II. The resources are numbered uniquely, and
processes are allowed to request for resources only
in increasing resource numbers.

III. The resources are numbered uniquely, and
processes are allowed to request for resources only in
decreasing resource numbers.

IV. The resources are numbered uniquely. A process
is allowed to request only for a resource with resource
number larger than its currently held resources.

Which of the above policies can be used for
preventing deadlock?

• (a)Any one of I and III but not II or IV
• (b)Any one of I, III, and IV but not II
• (c)Any one of II and III but not I or IV
• (d)Any one of I, II, III, and IV

A system contains three programs and each requires
three tape units for its operation. The minimum
number of tape units which the system must have
such that deadlocks never arise is _________.

An operating system uses the Banker's algorithm for
deadlock avoidance when managing the allocation
of three resource types X, Y, and Z to three
processes P0, P1, and P2. The table given below
presents the current system state. Here, the
Allocation matrix shows the current number of
resources of each type allocated to each process and
the Max matrix shows the maximum number of
resources of each type required by each process
during its execution.

Allocation
Max

X
Y
Z
X
Y
Z
P 0
0
0
1
8
4
3
P 1
3
2
0
6
2
0
P 2
2
1
1
3
3
3

There are 3 units of type X, 2 units of type Y and 2
units of type Z still available. The system is currently
in a safe state. Consider the following independent
requests for additional resources in the current state:

REQ1: P0 requests 0 units of X,

0 units of Y and 2 units of Z

OPERATING SYSTEMS

REQ2: P1 requests 2 units of X,

0 units of Y and 0 units of Z

Which one of the following is TRUE?

• (a)Only REQ1 can be permitted.
• (b)Only REQ2 can be permitted.
• (c)Both REQ1 and REQ2 can be permitted.
• (d)Neither REQ1 nor REQ2 can be permitted.

Three concurrent processes X, Y, and Z execute
three different code segments that access and
update certain shared variables. Process X executes
the P operation (i.e., wait) on semaphores a, b, and
c; process Y executes the P operation on
semaphores b, c, and d; process Z executes the P
operation on semaphores c, d, and a before entering
the respective code segments. After completing the
execution of its code segment, each process
invokes the V operation (i.e., signal) on its three
semaphores.
All
semaphores
are
binary
semaphores initialized to one. Which one of the
following represents a deadlock-free order of
invoking the P operations by the processes?

• (a)X: P(a) P(b) P(c)Y: P(b) P(c) P(d) Z: P(c) P(d) P(a)
• (b)X: P(b) P(a) P(c) Y: P(b) P(c) P(d) Z: P(a) P(c) P(d)
• (c)X: P(b) P(a) P(c) Y: P(c) P(b) P(d) Z: P(a) P(c) P(d)
• (d)X: P(a) P(b) P(c) Y: P(c) P(b) P(d) Z: P(c) P(d) P(a)

A system has n resources R0...,Rn-1, and k processes
P0....Pk-1. The implementation of the resource
request logic of each process Pi is as follows:

if (i % 2 == 0) {

if (i < n) request Ri

if (i+2 < n) request Ri+2

}

else {

if (i < n) request Rn-i

if (i+2 < n) request Rn-i-2

}
 In which one of the following situations is a deadlock
possible?

• (a)n = 40, k = 26
• (b)n = 21, k = 12
• (c)n = 20, k = 10
• (d)n = 41, k = 19

Consider a system with 4 types of resources R1 (3
units), R2 (2 units), R3 (3 units), R4 (2 units). A non-
preemptive resource allocation policy is used. At any
given instance, a request is not entertained if it cannot
be completely satisfied. Three processes P1, P2, P3
request the resources as follows if executed
independently.
Process P1:
t= 0 : requests
2 units of
R2
t= 1 : requests
1 unit of
R3
t= 3 : requests
2 units of
R1
t= 5 : releases
1 unit of
R2 and 1
unit
of
R1
t= 7 : releases
1 unit of
R3
t= 8 : requests
2 units of
R4
t= 10
:
Finishes
Process P2:
t= 0 : requests
2 units of
R3
t= 2 : requests
1 unit of
R4
t= 4 : requests
1 unit of
R1
t= 6 : releases
1 unit of
R3
t= 8 : Finishes
Process P3:
t= 0 : requests
1 unit of
R4
t= 2 : requests
2 units of
R1
t= 5 : releases
2 units of
R1
t= 7 : requests
1 unit of
R2
t= 8 : requests
1 unit of
R3
t= 9
:
Finishes

Which one of the following statements is TRUE if all
three processes run concurrently starting at time t = 0
?

OPERATING SYSTEMS

• (a)All processes will finish without any deadlock.
• (b)Only P1 and P2 will be in deadlock.
• (c)Only P1 and P3 will be in deadlock.
• (d)All three processes will be in deadlock.

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 resulting state is safe
• (c)Deadlock avoidance is less restrictive than deadlock prevention
• (d)Deadlock avoidance requires knowledge of resource requirements a priori

A single processor system has three resource types
X, Y, and Z, which are shared by three processes.
There are 5 units of each resource type.

The column alloc denotes the number of units of
each resource type allocated to each process, and
the column request denotes the number of units of
each resource type requested by a process in order
to complete execution.

Which of these processes will finish LAST?

alloc (X Y Z)
request (X Y Z)
P0
1 2 1
1 0 3
P1
2 0 1
0 1 2
P2
2 2 1
1 2 0

• (a)P0
• (b)P1
• (c)P2
• (d)None of the above, since the system is in a deadlock.

Consider the following snapshot of a system running
n processes. Process i is holding xi instances of a
resource R, for 1 ≤ i ≤ n. Currently, all instances of R
are occupied. Further, for all i, process i has placed a
request for an additional yi instances while holding
the xi instances it already has. There are exactly two
processes p and q such that yp = y_q = 0.

Which one of the following can serve as a necessary
condition to guarantee that the system is not
approaching a deadlock?

• (a)min(xp, xq) < maxk≠p,q yk
• (b)xp+ xq≥mink≠p,q yk
• (c)max(xp, xq) > 1
• (d)min(xp, xq) > 1

Suppose n processes, P1,...,Pn, share m identical
resource units, which can be reserved and released
one at a time. The maximum resource requirement of
process Pi is si, where si>0.

Which one of the following is a sufficient condition
for ensuring that deadlock does not occur?

• (a)∀i, si < m
• (b)∀i, si < n
• (c)∑ si < (m + n) n i=1
• (d)∑ si < (m × n) n i=1 OPERATING SYSTEMS

Consider contiguous allocation of physical memory
to processes using a variable partitioning scheme.
Suppose there are 8 holes in the memory of sizes:

20 KB, 4 KB, 25 KB, 18 KB, 7 KB, 9 KB, 15 KB,
and 12 KB.

Assume that no two holes are adjacent.

Two processes arrive in order:
●
P1 = 16 KB
●
P2 = 9 KB

They are allocated memory using the best-fit
technique.

After allocating space to P1 and P2, the number of
holes of size less than 8 KB is ______.

Note: 1K = 210.

A system has a Translation Lookaside Buffer
(TLB) that has a reach of 1 MB. TLB reach is
defined as the total amount of physical memory that
can be accessed through the TLB entries.

The paging system uses pages of size 4 KB. The
virtual address space is 64 GB and physical address
space is 1 GB.

If each TLB entry stores:
●
a 4-bit process id
●
page number
●
frame number
●
a 2-bit control field

then the size of the TLB (in bytes) is ______.

Note:
1K = 210, 1M = 220, 1G = 230.

Consider a system that has a cache memory unit and
a memory management unit (MMU). The address
input to the cache memory is a physical address. The
MMU has a Translation Lookaside Buffer (TLB).
Assume that when a page is evicted from main
memory, the corresponding blocks in the cache are
marked invalid.

For a given memory reference, which of the following
sequences of events can NEVER happen?

• (a)TLB miss, Page table hit, Cache hit
• (b)TLB hit, Page table miss, Cache hit
• (c)TLB miss, Page table miss, Cache hit
• (d)TLB miss, Page table miss, Cache miss

A computer system supports a logical address space
of 232bytes. It uses two-level hierarchical paging
with a page size of 4096 bytes. A logical address is
divided into a b-bit index to the outer page table, an
offset within the page of the inner page table, and an
offset within the desired page. Each entry of the inner
page table uses eight bytes. All the pages in the
system have the same size.The value of b is ______.

Consider a demand paging system with three frames, and the
following page reference string:1 2 3 4 5 4 1 6 4 5 1 3 2
          The contents of the frames are shown initially and after each
reference.

          The *-marked references cause page replacements.
          Which one or more of the following could be the page
replacement policy/policies in use?

• (a)Least Recently Used page replacement policy
• (b)Least Frequently Used page replacement policy
• (c)Most Frequently Used page replacement policy
• (d)Optimal page replacement policy OPERATING SYSTEMS

Consider a demand paging memory management
system with 32-bit logical address, 20-bit physical
address, and page size of 2048 bytes. Assuming that
the memory is byte addressable, what is the
maximum number of entries in the page table?

• (a)221
• (b)220
• (c)222
• (d)224

A disk of size 512M bytes is divided into blocks of
64K bytes. A file is stored in the disk using linked
allocation. In linked allocation, each data block
reserves 4 bytes to store the pointer to the next data
block. The link part of the last data block contains
a NULL pointer (also of 4 bytes). Suppose a file of
1M bytes needs to be stored in the disk. Assume,
1K = 210 and 1M = 220. The amount of space in
bytes that will be wasted due to internal
fragmentation is ______. (Answer in integer)

In
optimal
page
replacement
algorithm,
information about all future page references is
available to the operating system (OS). A
modification of the optimal page replacement
algorithm is as follows: The OS correctly predicts
only up to next 4 page references (including the
current page) at the time of allocating a frame to a
page. A process accesses the pages in the following
order of page numbers: 1, 3, 2, 4, 2, 3, 1, 2, 4, 3, 1,
4. If the system has three memory frames that are
initially empty, the number of page faults that will
occur during execution of the process is ________
. (Answer in integer)

Consider a 32-bit system with 4 KB page size and
page table entries of size 4 bytes each. Assume 1 KB
= 210 bytes. The OS uses a 2-level page table for
memory management, with the page table containing
an outer page directory and an inner page table. The
OS allocates a page for the outer page directory upon
process creation. The OS uses demand paging when
allocating memory for the inner page table, i.e., a
page of the inner page table is allocated only if it
contains at least one valid page table entry.

An active process in this system accesses 2000 unique
pages during its execution, and none of the pages are
swapped out to disk. After it completes the page
accesses, let X denote the minimum and Y denote the
maximum number of pages across the two levels of
the page table of the process.

The value of X + Y is _____

Which
of
the
following
tasks
is/are
the
responsibility/responsibilities
of
the
memory
management unit (MMU) in a system with paging-
based memory management?

• (a)Allocate a new page table for a newly created process
• (b)Translate a virtual address to a physical address using the page table
• (c)Raise a trap when a virtual address is not found in the page table
• (d)Raise a trap when a process tries to write to a page marked with read-only permission in the page table

Consider a memory management system that uses a
page size of 2 KB. Assume that both the physical and
virtual addresses start from 0. Assume that the pages
0, 1, 2, and 3 are stored in the page frames 1, 3, 2, and
0, respectively. The physical address (in decimal
format) corresponding to the virtual address 2500 (in
decimal format) is _________

OPERATING SYSTEMS

Consider the following two-dimensional array D in
the C programming language, which is stored in
row-major order:

int D[128][128];

Demand paging is used for allocating memory and
each physical page frame holds 512 elements of the
array D. The Least Recently Used (LRU) page-
replacement policy is used by the operating system.
A total of 30 physical page frames are allocated to
a process that executes the following code snippet:

for (int i = 0; i < 128; i++)

for (int j = 0; j < 128; j++)

D[j][i] *= 10;

The number of page faults generated during the
execution of this code snippet is

• (a)2048
• (b)512
• (c)4096
• (d)1032

Consider a computer system with 57-bit virtual
addressing using multi-level tree-structured page
tables with L levels for virtual to physical address
translation. The page size is 4 KB (1 KB = 1024 B)
and a page table entry at any of the levels occupies
8 bytes.The value of L is.........

Which one of the following statements is FALSE?

• (a)The TLB performs an associative search in parallel on all its valid entries using page number of incoming virtual address.
• (b)If the virtual address of a word given by CPU has a TLB hit, but the subsequent search for the word results in a cache miss, then the word will always be present in the main memory.
• (c)The memory access time using a given inverted page table is always same for all incoming virtual addresses.
• (d)In a system that uses hashed page tables, if two distinct virtual ddresses V1 and V2 map to the same value while hashing, then the memory access time of these addresses will not be the same.

Consider a demand paging system with four-page
frames (initially empty) and an LRU page
replacement policy. For the following page reference
string 7, 2,7,3, 2,5,3, 4,6,7,7,1,5,6,1 the page fault
rate, defined as the ratio of number of page faults to
the number of memory accesses (rounded off to one
decimal place) is_________.

In the context of the operating system, which of the
following statements is/are correct with respect to
paging?

• (a)Paging helps solve the issue of external fragmentation.
• (b)Page size has no impact on internal fragmentation.
• (c)Multi-level paging is necessary to support pages of different sizes.
• (d)Paging incurs memory overheads.

Consider a three-level page table to translate a 39-bit
virtual address to a physical address as shown below.

The page size is 4KB (1KB = 210 bytes) and page table
entry size at every level is 8 bytes. A process P is
currently using 2GB (1GB = 230 bytes) virtual
memory which is mapped to 2GB of physical
memory. The minimum amount of memory required
for the page table of P across all levels is
_______  KB

OPERATING SYSTEMS

Consider allocation of memory to a new process.
Assume that none of the existing holes in the
memory will exactly fit the process's memory
requirement. Hence, a new hole of smaller size will
be created if allocation is made in any of the
existing holes. Which one of the following
statements is TRUE?

• (a)The hole created by the worst fit is always larger than the hole created by the first fit.
• (b)The hole created by best fit is never larger than the hole created by first fit.
• (c)The hole created by the first fit is always larger than the hole created by the next fit.
• (d)The hole created by the next fit is never larger than the hole created by the best fit.

Consider a paging system that uses a 1-level page
table residing in main memory and a TLB for
address translation. Each main memory access
takes 100 ns and TLB lookup takes 20 ns. Each
page transfer to/from the disk takes 5000 ns.
Assume that the TLB hit ratio is 95%, page fault
rate is 10%. Assume that for 20% of the total page
faults, a dirty page has to be written back to disk
before the required page is read in from disk. TLB
update time is negligible. The average memory
access time in ns (round off to 1 decimal place) is
______.

Assume that in a certain computer, the virtual
addresses are 64 bits long and the physical
addresses are 48 bits long. The memory is word
addressable. The page size is 8 kB and the word
size is 4 bytes. The Translation Look-aside Buffer
(TLB) in the address translation path has 128 valid
entries. At most how many distinct virtual
addresses can be translated without any TLB miss?

• (a)8×220
• (b)4×220
• (c)16×210
• (d)256×210

Consider a process executing on an operating system
that uses demand paging. The average time for a
memory access in the system is M units if the
corresponding memory page is available in memory
and D units if the memory access causes a page fault.
It has been experimentally measured that the average
time taken for a memory access in the process is X
units.

Which one of the following is the correct expression
for the page fault rate experienced by the process?

• (a)(D-M)/(X-M)
• (b)(X-M)/(D-M)
• (c)(D-X)/(D-M)
• (d)(X-M)/(D-X)

Recall that Belady's anomaly is that the page-fault
rate may increase as the number of allocated frames
increases. Now, consider the following statements:

S1: Random page replacement algorithm (where a
page chosen at random is replaced) suffers from
Belady's anomaly

S2: LRU page replacement algorithm suffers from
Belady's anomaly

Which of the following is CORRECT?

• (a)S1 is true, S2 is true.
• (b)S1 is true, S2 is false.
• (c)S1 is false, S2 is true.
• (d)S1 is false, S2 is false.

In which one of the following page replacement
algorithms is it possible for the page fault rate to
increase even when the number of allocated frames
increases?

• (a)LRU (Least Recently Used)
• (b)OPT (Optimal Page Replacement)
• (c)MRU (Most Recently Used)
• (d)FIFO (First In First Out) OPERATING SYSTEMS

Consider a computer system with ten physical
page frames. The system is provided with an
access sequence (a1, a2,........., a20, a1, a2, ...... a20),
where each ai is a distinct virtual page number.
The difference in the number of page faults
between the last-in-first-out page replacement
policy and the optimal page replacement policy is
__.

Consider a computer system with 40-bit virtual
addressing and page size of sixteen kilobytes. If the
computer system has a one-level page table per
process and each page table entry requires 48 bits,
then the size of the per-process page table is
__________ megabytes.

Consider a main memory with five page frames and
the following sequence of page references: 3, 8, 2,
3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3. Which one of the
following is true with respect to page replacement
policies First-In-First Out (FIFO) and Least
Recently Used (LRU)?

• (a)Both incur the same number of page faults
• (b)FIFO incurs 2 more page faults than LRU
• (c)LRU incurs 2 more page faults than FIFO
• (d)FIFO incurs 1 more page faults than LRU

Consider six memory partitions of size 200 KB,
400 KB, 600 KB, 500 KB, 300 KB, and 250 KB,
where KB refers to kilobyte. These partitions need
to be allotted to four processes of sizes 357 KB, 210
KB, 468 KB and 491 KB in that order. If the best
fit algorithm is used, which partitions are NOT
allotted to any process?

• (a)200 KB and 300 KB
• (b)200 KB and 250 KB
• (c)250 KB and 300 KB
• (d)300 KB and 400 KB

A computer system implements a 40-bit virtual
address, page size of 8 kilobytes, and a 128-entry
translation look-aside buffer (TLB organized into 32
sets each having four ways. Assume that the TLB tag
does not store any process id. The minimum length of
the TLB tag in bits is _________.

Consider a system with byte-addressable memory, 32
bit logical addresses, 4 kilobyte page size and page
table entries of 4 bytes each. The size of the page table
in the system in megabytes is ___________

A computer system implements 8 kilobyte pages and
a 32-bit physical address space. Each page table entry
contains a valid bit, a dirty bit, three permission bits,
and the translation. If the maximum size of the page
table of a process is 24 megabytes, the length of the
virtual address supported by the system is ________
bits.

Consider the main memory system that consists of 8
memory modules attached to the system bus, which is
one word wide. When a write request is made, the bus
is occupied for 100 ns by the data, address, and
control signals. During the same 100 ns, and for 500
ns thereafter, the addressed memory module executes
one cycle accepting and storing the data. The internal
operation of different memory modules may overlap
in time, but only one request can be on the bus at any
time. The maximum number of stores (of one word
each) that can be initiated in 1 millisecond is ______

OPERATING SYSTEMS

A system uses 3 page frames for storing process
pages in main memory. It uses the Least Recently
Used (LRU) page replacement policy. Assume that
all the page frames are initially empty. What is the
total number of page faults that will occur while
processing the page reference string given below?
          4, 7, 6, 1, 7, 6, 1, 2, 7, 2

A computer has twenty physical page frames which
contain pages numbered 101 through 120. Now a
program accesses the pages numbered 1, 2, ..., 100
in that order, and repeats the access sequence thrice.
Which one of the following page replacement
policies experiences the same number of page
faults as the optimal page replacement policy for
this program?

• (a)Least-recently-used
• (b)First-in-first-out
• (c)Last-in-first-out
• (d)Most-recently-used

Assume that there are 3 page frames which are
initially empty. If the page reference string is
1,
2,
3,
4,
2,
1,
5,
3,
2,
4,
6
the number of page faults using the optimal
replacement policy is ______

Consider a paging hardware with a TLB. Assume
that the entire page table and all the pages are in the
physical memory. It takes 10 ms to search the TLB
and 80 ms to access the physical memory. If the
TLB hit ratio is 0.6, the effective memory access
time (in milliseconds) is ______

A computer uses 46-bit virtual address, 32-bit
physical address, and a three-level paged page table
organization. The page table base register stores the
base address of the first-level table (T1), which
occupies exactly one page. Each entry of T1 stores the
base address of a page of the second-level table (T2).
Each entry of T2 stores the base address of a page of
the third-level table (T3). Each entry of T3 stores a
page table entry (PTE). The PTE is 32 bits in size.
The processor used in the computer has a 1 MB 16-
way set associative virtually indexed physically
tagged cache. The cache block size is 64 bytes.

What is the minimum number of page colors needed
to guarantee that no two synonyms map to different
sets in the processor cache of this computer?

• (a)2
• (b)4
• (c)8
• (d)16

Consider the virtual page reference string 1, 2, 3, 2, 4,
1, 3, 2, 4, 1 On a demand paged virtual memory
system running on a computer system that has a main
memory size of 3 pages frames which are initially
empty. Let LRU, FIFO and OPTIMAL denote the
number of page faults under the corresponding page
replacements policy. Then

• (a)OPTIMAL < LRU < FIFO
• (b)OPTIMAL < FIFO < LRU
• (c)OPTIMAL = LRU
• (d)OPTIMAL = FIFO OPERATING SYSTEMS

Let the page fault service time to 10 ms in a
computer with average memory access time being
20 ns. If one page fault is generated for every 106
memory accesses, what is the effective access time
for the memory?

• (a)21 ns
• (b)30 ns
• (c)23 ns
• (d)25ns

A system uses FIFO policy for page replacement. It
has 4 page frames with no pages loaded to begin
with. The system first accesses 100 distinct pages
in some order and then accesses the same 100 pages
but now in the reverse order.

How many page faults will occur?

• (a)196
• (b)192
• (c)197
• (d)195

In which one of the following page replacement
policies, Belady's anomaly may occur?

• (a)FIFO
• (b)Optimal
• (c)LRU
• (d)MRU

The essential content(s) in each entry of a page
table is/are

• (a)virtual page number
• (b)page frame number
• (c)both virtual page number and page frame number
• (d)access right information

A multilevel page table is preferred in comparison to
a single level page table for translating virtual address
to physical address because

• (a)it reduces the memory access time to read or write a memory location.
• (b)It helps to reduce the size of the page table needed to implement the virtual address space of a process.
• (c)it is required by the translation lookaside buffer.
• (d)it helps to reduce the number of page faults in page replacement algorithms

A processor uses:
Physical address = 36 bits
Virtual address = 32 bits
Page size = 4 KB
PTE size = 4 bytes

Three-level page table with:
● bits 30–31 → 1st level index
● bits 21–29 → 2nd level index
● bits 12–20 → 3rd level index
● bits 0–11 → offset

Find number of bits required in PTE to address the
next level page table (or page frame) at first, second,
and third levels respectively.

• (a)20, 20 and 20
• (b)24, 24 and 24
• (c)24, 24 and 20
• (d)25, 25 and 24 OPERATING SYSTEMS

A virtual memory system uses First In First Out
(FIFO) page replacement policy and allocates a
fixed number of frames to a process. Consider the
following statements:

P: Increasing the number of page frames allocated
to a process sometimes increases the page fault rate.

Q: Some programs do not exhibit locality of reference.

Which one of the following is TRUE?

• (a)Both P and Q are true, and Q is the reason for P.
• (b)Both P and Q are true, but Q is not the reason for P.
• (c)P is false, but Q is true.
• (d)Both P and Q are false.

A process has been allocated 3 page frames.
Assume that none of the pages of the process are
available in memory initially.

The process makes the following sequence of page
references (reference string):

1, 2, 1, 3, 7, 4, 5, 6, 3, 1

If optimal page replacement policy is used, how
many page faults occur for the above reference string?

• (a)7
• (b)8
• (c)9
• (d)10

A process has been allocated 3 page frames.
Assume that none of the pages of the process are
available in memory initially.

The process makes the following sequence of page
references (reference string):

1, 2, 1, 3, 7, 4, 5, 6, 3, 1

Least Recently Used (LRU) page replacement policy is
a practical approximation to optimal page replacement.

For the above reference string, how many more
page faults occur with LRU than with the optimal
page replacement policy?

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

A CPU generates 32-bit virtual addresses. The page
size is 4 KB. The processor has a translation look-
aside buffer (TLB) which can hold a total of 128 page
table entries and is 4-way set associative. The
minimum size of the TLB tag is

• (a)11 bits
• (b)13 bits
• (c)15 bits
• (d)20 bits

A computer system supports 32-bit virtual addresses
as well as 32-bit physical addresses. Since the virtual
address space is of the same size as the physical
address space, the operating system designers decide
to get rid of the virtual memory entirely. Which one
of the following is true?

• (a)Efficient implementation of multi-user support is no longer possible
• (b)The processor cache organization can be made more efficient now
• (c)Hardware support for memory management is no longer needed
• (d)CPU scheduling can be made more efficient now

Increasing the RAM of a computer typically improves
performance because:

• (a)Virtual memory increases
• (b)Larger RAMs are faster
• (c)Fewer page faults occur
• (d)Fewer segmentation faults occur OPERATING SYSTEMS

Consider a hard disk with a rotational speed of
15000 rpm. The time to move the read/write head
from a track to its adjacent track is 1 millisecond.
Initially, the head is on track 0. The number of
sectors per track is 400, and the sector size is 1024
bytes.

It is necessary to transfer data from 10 randomly
located sectors in each of the following tracks in the
order: 5, 12, and 7.

The total time for the data transfer (in milliseconds)
from
the
hard
disk
is
______.
(rounded off to one decimal place)

To keep track of free blocks in a file system, one of
the two approaches is generally used – using
bitmaps (bit vectors) or using linked lists. Consider
that the linked list approach is used to keep track of
free blocks in a file system.

Assume that:
● Disk size = 16 GB
● Block size = 2 KB
● Block numbers used are 32-bit long
●
A single pointer of size 4 bytes is used in
each block of the list to point to the next block of
the list

The number of blocks required to hold the free disk
block numbers is ______.

Note:
1K = 210 and 1G = 230.

A disk of size 512 M bytes is divided into blocks of
64 K bytes. A file is stored in the disk using linked
allocation. In linked allocation, each data block
reserves 4 bytes to store the pointer to the next data
block. The link part of the last data block contains a
NULL pointer (also of 4 bytes). Suppose a file of 1 M
bytes needs to be stored in the disk. Assume, 1 K =
210and 1 M = 220. The amount of space in bytes that
will be wasted due to internal fragmentation is
______

Suppose in a multiprogramming environment, the
following C program segment is executed. A process
goes into I/O queue whenever an I/O related
operation is performed. Assume that there will always
be a context switch whenever a process requests for
an I/O, and also whenever the process returns from an
I/O. The number of times the process will enter the
ready queue during its lifetime (not counting the time
the process enters the ready queue when it is run
initially) is ______

Int main()
{

int x = 0, i = 0;

 scanf("%d", &x);

 for(i = 0; i < 20; i++)

 {

x = x + 20;

printf("%d\n", x);

 }

return 0;
}

OPERATING SYSTEMS

Consider a disk with the following specifications:
rotation speed of 6000 RPM, average seek time of
5 milliseconds, 500 sectors/track, 512-byte sectors.
A file has content stored in 3000 sectors located
randomly on the disk. Assuming average rotational
latency, the total time (in seconds, rounded off to 2
decimal places) to read the entire file from the disk is
______

Consider a 512 GB hard disk with 32 storage
surfaces. There are 4096 sectors per track and each
sector holds 1024 bytes of data. The number of
cylinders in the hard disk is ______

Consider two files systems A and B, that use
contiguous allocation and linked allocation,
respectively. A file of size 100 blocks is already
stored in A and also in B. Now, consider inserting
a new block in the middle of the file
(between 50th and 51st block), whose data is
already available in the memory. Assume that there
are enough free blocks at the end of the file and that
the file control blocks are already in memory. Let
the number of disk accesses required to insert a
block
in
the
middle
of
the
file
in A and B are  nA and nB, respectively, then the
value of nA+nB is__________________.

Consider
a
linear
list
based
directory
implementation in a file system. Each directory is a
list of nodes, where each node contains the file
name along with the file metadata, such as the list
of pointers to the data blocks. Consider a given
directory foo.
 Which of the following operations will necessarily
require a full scan of foo for successful completion?

• (a)Creation of a new file in foo
• (b)Deletion of an existing file from foo
• (c)Renaming of an existing file in foo
• (d)Opening of an existing file in foo

Consider the following five disk access requests of
the form (request id, cylinder number) that are present
in the disk scheduler queue at a given time:

(P, 155), (Q, 85), (R, 110), (S, 30), (T, 115)

Assume the head is positioned at cylinder 100. The
scheduler follows
Shortest
Seek Time
First
scheduling to service the requests.

Which one of the following statements is FALSE?

• (a)T is serviced before P.
• (b)Q is serviced after S, but before T.
• (c)The head reverses its direction of movement between servicing of Q and P.
• (d)R is serviced before P.

The index node (inode) of a Unix-like file system has
12 direct, one single-indirect and one double-indirect
pointers. The disk block size is 4 kB, and the disk
block address is 32-bits long. The maximum possible
file size is (rounded off to 1 decimal place) ______
GB.

The following are some events that occur after a
device controller issues an interrupt while process L
is under execution:

P. The processor pushes the process status of L onto
the control stack
Q. The processor finishes the execution of the
current instruction
R. The processor executes the interrupt service routine
S. The processor pops the process status of L from
the control stack
T. The processor loads the new PC value based on
the interrupt

Which of the following is the correct order in which
the events above occur?

• (a)QPTRS
• (b)PTRSQ
• (c)TRPQS
• (d)QTPRS OPERATING SYSTEMS

In a file allocation system, which of the following
allocation scheme(s) can be used if no external
fragmentation is allowed?
1. Contiguous
2. Linked
3. Indexed

• (a)1 and 3 only
• (b)2 only
• (c)3 only
• (d)2 and 3 only

Consider a storage disk with 4 platters (numbered
as 0, 1, 2 and 3), 200 cylinders (numbered as 0, 1,
..., 199), and 256 sectors per track (numbered as 0,
1, ... 255). The following 6 disk requests of the
form [sector number, cylinder number, platter
number] are received by the disk controller at the
same time:
[120, 72, 2], [180, 134, 1], [60, 20, 0], [212, 86, 3],
[56, 116, 2], [118, 16, 1]

Currently the head is positioned at sector number
100 of cylinder 80, and is moving towards higher
cylinder numbers. The average power dissipation in
moving the head over 100 cylinders is 20 milliwatts
and for reversing the direction of the head
movement once is 15 milliwatts. Power dissipation
associated with rotational latency and switching of
head between different platters is negligible.

The total power consumption in milliwatts to
satisfy all of the above disk requests using the
Shortest Seek Time First disk scheduling algorithm
is ______ .

Consider a disk queue with requests for I/O to
blocks on cylinders 47, 38, 121, 191, 87, 11, 92, 10.
The C-LOOK scheduling algorithm is used. The
head is initially at cylinder number 63, moving
towards larger cylinder numbers on its servicing
pass. The cylinders are numbered from 0 to 199.
The total head movement (in number of cylinders)
incurred while servicing these requests is
___________.

Suppose the following disk request sequence (track
numbers) for a disk with 100 tracks is given: 45, 20,
90, 10, 50, 60, 80, 25, 70. Assume that the initial
position of the R/W head is on track 50. The
additional distance that will be traversed by the R/W
head when the Shortest Seek Time First (SSTF)
algorithm is used compared to the SCAN (Elevator)
algorithm (assuming that SCAN algorithm moves
towards 100 when it starts execution) is _________
tracks.

Consider a typical disk that rotates at 15000 rotations
per minute (RPM) and has a transfer rate of 50 ×
106bytes/sec. If the average seek time of the disk is
twice the average rotational delay and the controller's
transfer time is 10 times the disk transfer time, the
average time (in milliseconds) to read or write a 512-
byte sector of the disk is ______

Consider a disk pack with a seek time of 4
milliseconds and rotational speed of 10000 rotations
per minute (RPM). It has 600 sectors per track and
each sector can store 512 bytes of data. Consider a file
stored in the disk. The file contains 2000 sectors.
Assume that every sector access necessitates a seek,
and the average rotational latency for accessing each
sector is half of the time for one complete rotation.
The total time (in milliseconds) needed to read the
entire file is ______

A FAT (file allocation table) based file system is
being used and the total overhead of each entry in the
FAT is 4 bytes in size. Given a 100 × 106 bytes disk
on which the file system is stored and data block size
is 103 bytes, the maximum size of a file that can be
stored on this disk in units of 106 bytes is
____________.

OPERATING SYSTEMS

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
90 is serviced after servicing ____________
number of requests.

Consider a hard disk with 16 recording surfaces (0–
15) having 16384 cylinders (0–16383) and each
cylinder contains 64 sectors (0–63). Each sector
stores 512 bytes. Data are organized cylinder-wise
and the addressing format is (cylinder no., surface
no., sector no.). A file of size 42797 KB is stored
starting at disk location (1200, 9, 40). What is the
cylinder number of the last sector of the file, if it is
stored contiguously?

A file system with 300 Gbyte disk uses a file
descriptor with 8 direct block addresses, 1 indirect
block address and 1 doubly indirect block address.
The size of each disk block is 128 Bytes and the
size of each disk block address is 8 Bytes. The
maximum possible file size in this file system is

• (a)3 KBytes
• (b)35 KBytes
• (c)280 Kbytes
• (d)dependent on the size of the disk

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

• (a)0.50s
• (b)1.50s
• (c)1.25s
• (d)1.00 s

Consider a disk system with 100 cylinders. The
requests to access the cylinders occur in following
sequence :

4, 34, 10, 7, 19, 73, 2, 15, 6, 20.

Assuming that the head is currently at cylinder 50,
what is the time taken to satisfy all requests if it takes
1 ms to move from one cylinder to adjacent one and
the shortest seek time first policy is used ?

• (a)95 ms
• (b)119 ms
• (c)233 ms
• (d)276 ms

A hard disk has 63 sectors per track, 10 platters each
with 2 recording surfaces and 1000 cylinders. The
address of a sector is given as a triple (c,h,s), where c
is the cylinder number, h is the surface number and s
is the sector number. Thus, the 0th sector is addressed
as ⟨0,0,0⟩, the 1st sector as ⟨0,0,1⟩, and so on.

The address ⟨400,16,29⟩ corresponds to sector
number:

• (a)505035
• (b)505036
• (c)505037
• (d)505038 OPERATING SYSTEMS

A hard disk has 63 sectors per track, 10 platters
each with 2 recording surfaces and 1000 cylinders.
The address of a sector is given as a triple (c,h,s),
where c is the cylinder number, h is the surface
number and s is the sector number. Thus, the 0th
sector is addressed as ⟨0,0,0⟩, the 1st sector as
⟨0,0,1⟩, and so on.

The address of 1039th sector is

• (a)⟨0,15,31⟩
• (b)⟨0,16,30⟩
• (c)⟨0,16,31⟩
• (d)⟨0,17,31⟩

The data blocks of a very large file in the Unix file
system are allocated using

• (a)contiguous allocation
• (b)linked allocation
• (c)indexed allocation
• (d)an extension of indexed allocation

For a magnetic disk with concentric circular tracks,
the seek latency is not linearly proportional to the
seek distance due to

• (a)non-uniform distribution of requests
• (b)arm starting and stopping inertia
• (c)higher capacity of tracks on the periphery of the platter
• (d)use of unfair arm scheduling policies

Consider a disk pack with 16 surfaces, 128 tracks per
surface and 256 sectors per track. 512 bytes of data
are stored in a bit serial manner in a sector. The
capacity of the disk pack and the number of bits
required to specify a particular sector in the disk pack
are respectively:

• (a)256 Mbyte, 19 bits
• (b)256 Mbyte, 28 bits
• (c)512 Mbyte, 20 bits
• (d)64 Gbyte, 28 bits

What is the swap space in the disk used for?

• (a)Saving temporary HTML pages
• (b)Saving process data
• (c)Storing the super-block
• (d)Storing device drivers

Normally user programs are prevented from
handling I/O directly by I/O instructions in them.
For CPUs having explicit I/O instructions, such I/O
protection is ensured by having the I/O instruction
privileged. In a CPU with memory mapped I/O,
there is no explicit I/O instruction. Which one of the
following is true for a CPU with memory mapped
I/O?

• (a)I/O protection is ensured by operating system routine(s)
• (b)I/O protection is ensured by a hardware trap
• (c)I/O protection is ensured during system configuration
• (d)I/O protection is not possible OPERATING SYSTEMS