SETHU INSTITUTE OF TECHNOLOGY

(An Autonomous Institution | Accredited by NAAC with ‘A’ Grade)

PULLOOR, KARIAPATTI – 626 115.
DEPATMENT OF COMPUTER SCIENCE & ENGINEERING
Operating Systems

Multiple Choice Questions (1 mark):

1.Which one of the following is TRUE for any simple connected undirected graph with
more than 2 vertices?
A. No two vertices have the same degree
B. At least two vertices have the same degree
C. At least three vertices have the same degree
D. All vertices have the same degree

2. A CPU generally handles an interrupt by executing an interrupt service routine

A. as soon as an interrupt is raised
B. by checking the interrupt register at the end of fetch cycle
C. by checking the interrupt register after finishing the execution of the current
instruction
D. by checking the interrupt register at fixed time intervals

3. 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

4. Match all items in Group I with correct options from those given in Group 2
Group 1 Group 2
P. Regular expression 1. Syntax analysis
Q. Pushdown automata 2. Code generation
R. Dataflow analysis 3. Lexical analysis
S. Register allocation 4. Code Optimization
Codes:
A. P-4, Q-1, R-2, S-3
B. P-3, Q-1, R-4, S-2
C. P-3, Q-4, R-1, S-2
D. P-2, Q-1, R-4, S-3

5. Which of the following statements are CORRECT?

1) Static allocation of all data areas by a compiler makes it impossible to implement
recursion.
2) Automatic garbage collection is essential to implement recursion.
3) Dynamic allocation of activation records is essential to implement recursion.
4) Both heap and stack are essential to implement recursion.
A. 1 and 2 only
B. 2 and 3 only
C. 3 and 4 only
D. 1 and 3 only

6. In the context of modular software design, which one of the following combinations is
desirable?
A. High cohesion and high coupling
B. High cohesion and low coupling
C. Low cohesion and high coupling
D. Low cohesion and low coupling
7. Consider a 4-way set associative cache (initially empty) with total 16 cache blocks.
The main memory consists of 256 blocks and the request for memory blocks is in the
following order: 0,255,1,4,3,8,133,159,216,129,63,8,48,32, 73, 92,155 Which one of the
following memory block will not be in cache if LRU replacement policy is used?
A.3
B. 8
C. 129
D. 216

8. 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.

Which one of the following statements is TRUE if all three processes run concurrently
starting at time t = 0?
A. All processes will finish without any deadlock
B. Only P1 and P2 will be in a deadlock
C. Only P1 and P3 will be in deadlock
D. All three processes will be in deadlock

9. 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
an immediately
II. A process P2 in blocked state can take 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

10. The enter CS ( ) and leave CS( ) functions to implement critical section of a process
are realized using test-and-set instruction as follows:
Voidenter_CS(X)
{
While (test-and-set (X))
}
Voidleave_CS (X)
{
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 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 are TRUE?
A. I only
B. I and II
C. II and III
D. IV only
11. A main memory unit with a capacity of 4 megabytes is built using 1M×1-bit DRAM
chips. Each DRAM chip has 1K rows of cells with 1K cells in each row. The time taken
for a single refresh operation is 100 nanoseconds. The time required to perform one
refresh operation on all the cells in the memory unit is
A. 100 nanoseconds
B. 100*210 nanoseconds
C. 100*220 nanoseconds
D. 3200*220 nanoseconds

12. Identify the correct order in which a server process must invoke the function calls
accept, bind, listen, and recv according to UNIX socket APL
A. listen, accept, bind recv
B. bind, listen, accept, recv
C. bind, accept, listen, recv
D. accept, listen, bindrecv

13. Which one of the following statements is NOT correct about HTTP cookies?
A. A cookie is a piece of code that has the potential to compromise the security of an
internet user
B. A cookie gains entry to the user‟s work area through an HTTP header
C. A cookie has an expiry date and time
D. Cookies can be used to track the browsing pattern of a user at a particular site

14. 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 followings 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 per-thread basis, the OS does not maintain virtual memory state
D. On per thread basis, the OS maintains only scheduling and accounting information

15. Let the page fault service time be 10ms in a computer with average memory access
time being 20ns. If one page fault is generated for every 106 memory accesses, what is
the effective access time for the memory?
A. 21ns
B. 30ns
C. 23ns
D. 35ns

16. Consider six memory partitions of sizes 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, 210KB, 468 KB and 491 KB in that order. If the best fit
algorithm is used, which partitions are NOT allotted to any process?
A. 200KB and 300 KB
B. 200KB and 250 KB
C. 250KB and 300 KB
D. 300KB and 400 KB
17. 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
18. A computer handles several interrupt sources of which the following are relevant for
this question. Interrupt from CPU temperature sensor Interrupt from Mouse Interrupt
from Keyboard Interrupt from Hard Disk
A. Interrupt from Hard Disk
B. Interrupt from Mouse
C. Interrupt from Keyboard
D. Interrupt from CPU temp sensor

19. 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

20. 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 4ms
P2 2 ms 9ms
The pre-emptive shortest job first scheduling algorithm is used. Scheduling is carried
out only at arrival or completion of processes. What is the average waiting time for the
three processes?
A. 5.0 ms
B. 4.33 ms
C. 6.33 ms
D. 7.33 ms
21. Which of the following is NOT a valid deadlock prevention scheme?
(a) Release all resources before requesting a new resource
(b) Number the resources uniquely and never request a lower numbered resource
than the last one requested.
(c) Never request a resource after releasing any resource
(d) Request and all required resources be allocated before execution.

22. Consider a virtual memory system with FIFO page replacement policy. For an
arbitrary page access pattern, increasing the number of page frames in main memory
will
a) Always decrease the number of page faults
b) Always increase the number of page faults
c) Sometimes increase the number of page faults
d) Never affect the number of page faults

23. Which of the following requires a device driver?

a) Register
b) Cache
c) Main memory
d) Disk
24. In the index allocation scheme of blocks to a file, the maximum possible size of
the file depends on:
A. the size of the blocks, and the size of the address of the blocks
B. the number of blocks used for the index, and the size of the blocks
C. the size of the blocks, the number of blocks used for the index, and the size of the
address of the blocks
d. None of these
25. 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

26. Thrashing occurs when

a. When a page fault occurs
b. Processes on system frequently access pages not memory
c. Processes on system are in running state
d. Processes on system are in waiting state

27. 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 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

28. Which of the following operating system write through catches?

a. XEVIX
b. ULTRIX
c. DOS
d. UNIX

29. Which one is the example of hard real time system?

a. Robotics
b. Industrial control
c. Both (a) and (b)
d. None of these

30. The kernel of the operating system remains in primary memory (and other
part of the operating system remains in secondary storage) because
a. It is mostly called (used)
b. It manages all interrupt calls
c. It controls all operations in a process
d. It is low level
31. A CPU generally handles an interrupt by executing an interrupt service routine
A. as soon as an interrupt is raised
B. by checking the interrupt register at the end of fetch cycle
C. by checking the interrupt register after finishing the execution of the current
instruction
D. by checking the interrupt register at fixed time intervals

32. 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

33. 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 followings 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 per-thread basis, the OS does not maintain virtual memory state
D. On per thread basis, the OS maintains only scheduling and accounting information

34. A process executes the code fork (); fork (); fork (); The total number of child
processes created is
A. 3
B. 4
C. 7
D. 8

35.In the following Query, which of the following can be placed in the Query's blank
portion to display the salary from highest to lowest amount, and sorting the employs
name alphabetically?
SELECT *
FROM instructor
ORDER BY salary ____, name ___;

(A) Ascending, Descending

(B) Asc, Desc
(C) Desc, Asc
(D) All of the above

36. A Database Management System is a type of _________software.

(A) It is a type of system software

(B) It is a kind of application software
(C) It is a kind of general software
(D) Both A and C

37. The term "FAT" is stands for_____

(A) File Allocation Tree

(B) File Allocation Table
(C) File Allocation Graph
(D) All of the above

38. Which of the following can be considered as the maximum size that is supported by
FAT?

(A) 8GB
(B) 4GB
(C) 4TB
(D) None of the above

39. The term "NTFS" refers to which one of the following?

(A) New Technology File System

(B) New Tree File System
(C) New Table type File System
(D) Both A and C
40. A huge collection of the information or data accumulated form several different
sources is known as ________:

(A) Data Management

(B) Data Mining
(C) Data Warehouse
(D) Both B and C

41.Which scheduling policy is most suitable for a time shared operating system?
(a) Shortest Job First
(b) Round Robin
(c) First Come First Serve
(d) Elevator

42.A processor needs software interrupt to

(a) test the interrupt system of the processor.
(b) implement co-routines.
(c) obtain system services which need execution of privileged instructions.
(d) return from subroutine.

43.A CPU has two modes-privileged and non-privileged. In order to change the mode
from privileged to non-privileged
(a) a hardware interrupt is needed.
(b) a software interrupt is needed.
(c) a privileged instruction (which does not generate an interrupt) is needed.
(d) a non-privileged instruction (which does not generate an interrupt) is needed.

44.Which of the following scheduling algorithms is non-preemptive?

(a) Round Robin.
(b) First-In First-Out.
(c) Multilevel Queue Scheduling.
(d) Multilevel Queue Scheduling with Feedback.

45.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 scheduling algorithm? Do
not count the context switches at time zero and at the end.
(a) 1
(b) 2
(c) 3
(d) 4

46.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.

47.A CPU generally handles an interrupt by executing an interrupt service routine

(A) As soon as an interrupt is raised.
(B) By checking the interrupt register at the end of fetch cycle.
(C) By checking the interrupt register after finishing the execution of the current
instruction.
(D) By checking the interrupt register at fixed time intervals.

48.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.
49.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?

50.Which of the following statements is false?

(a) Virtual memory implements the translation of a program’s address space into
physical memory address space
(b) Virtual memory allows each program to exceed the size of the primary memory
(c) Virtual memory increases the degree of multiprogramming
(d) Virtual memory reduces the context switching overhead

51.The process of assigning load addresses to the various parts of the program and
adjusting the code and date in the program to reflect the assigned addresses is called
(a) Assembly
(b) Parsing
(c) Relocation
(d) Symbol resolution

52.Which of the following is not a form of memory?

(a) instruction cache
(b) instruction register
(c) instruction opcode
(d) translation look-a-side buffer

53.In a system with 32 bit virtual addresses and 1KB page size, use of one-level page
tables for virtual to physical address translation is not practical because of
(A) the large amount of internal fragmentation
(B) the large amount of external fragmentation
(C) the large memory overhead in maintaining page tables
(D) the large computation overhead in the translation process

54.A computer has six tape drives, with n processes competing for them. Each process
may need two drives. What is the maximum value of n for the system to be deadlock
free?
(a) 6
(b) 5
(c) 4
(d) 3.

55.Which of the following is NOT a valid deadlock prevention scheme?

(a) Release all resources before requesting a new resource
(b) Number the resources uniquely and never request a lower numbered resource
than the last one requested.
(c) Never request a resource after releasing any resource
(d) Request and all required resources be allocated before execution.

56.Consider a virtual memory system with FIFO page replacement policy. For an
arbitrary page access pattern, increasing the number of page frames in main memory
will
a) Always decrease the number of page faults
b) Always increase the number of page faults
c) Some times increase the number of page faults
d) Never affect the number of page faults
57.Which of the following requires a device driver?
a) Register
b) Cache
c) Main memory
d) Disk
58.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
59.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 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.
60.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

Multiple Choice Questions (2 mark):

1. Consider the virtual page reference string 1, 2, 3, 2, 4, 1, 3, 2, 4, 1 On a demand

paged virtual memory system running on a computer system that main memory size of
3 pages frames which are initially empty. Let LRU, FIFO and OPTIMAL denote the
number of page faults under the corresponding page replacements policy. Then
a. OPTIMAL < LRU < FIFO
b. OPTIMAL < FIFO < LRU
c. OPTIMAL = LRU
d. OPTIMAL = FIFO

2. A processor uses 36 bit physical addresses and 32 bit virtual addresses, with a
page frame size of 4 Kbytes. Each page table entry is of size 4 bytes. A three level
page table is used for virtual to physical address translation, where the virtual address
is used as follows • Bits 30-31 are used to index into the first level page table • Bits 21-
29 are used to index into the second level page table • Bits 12-20 are used to index
into the third level page table, and • Bits 0-11 are used as offset within the page The
number of bits required for addressing the next level page table (or page frame) in the
page table entry of the first, second and third level page tables are respectively.
a. 20, 20 and 20
b. 24, 24 and 24
c. 24, 24 and 20
d. 25, 25 and 24

3. 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

4. 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.
Which one of the following statements is TRUE if all three processes run concurrently
starting at time t = 0?
A. All processes will finish without any deadlock
B. Only P1 and P2 will be in a deadlock
C. Only P1 and P3 will be in deadlock
D. All three processes will be in deadlock

5. 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 blocked state can take 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

6. A main memory unit with a capacity of 4 megabytes is built using 1M×1-bit DRAM
chips. Each DRAM chip has 1K rows of cells with 1K cells in each row. The time taken
for a single refresh operation is 100 nanoseconds. The time required to perform one
refresh operation on all the cells in the memory unit is
A. 100 nanoseconds
B. 100*210 nanoseconds
C. 100*220 nanoseconds
D. 3200*220 nanoseconds

7. Identify the correct order in which a server process must invoke the function calls
accept, bind, listen, and recv according to UNIX socket APL
A. listen, accept, bind recv
B. bind, listen, accept, recv
C. bind, accept, listen, recv
D. accept, listen, bind recv

8. Consider six memory partitions of sizes 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, 210KB, 468 KB and 491 KB in that order. If the best fit
algorithm is used, which partitions are NOT allotted to any process?
A. 200KB and 300 KB
B. 200KB and 250 KB
C. 250KB and 300 KB
D. 300KB and 400 KB

9. 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 4ms
P2 2 ms 9ms
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.0ms
B. 4.33ms
C. 6.33ms
D. 7.33ms

10. The amount of ROM needed to implement a 4 bit multiplier is

A. 64 bits
B. 128 bits
C. 1kbits
D. 2kbits

11. A multithreaded program P executes with x number of threads and uses 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

12. Consider the 3 process, P1, P2 and P3 shown in the table

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

13. Consider the following schedule for transactions T1, T2 and T3:
T1 T2 T3
Read(X)
Read(Y)
Read(Y)
Write(Y)
Write(X)
Write(X)
Read(X)
Write(X)
Which one of the schedules below is the correct serialization of the above?
A. T1 → T3 → T2
B. T2 → T1 → T3
C. T2 → T3 → T1
D. T3 → T1 → T2

14. The following program consists of 3 concurrent processes and 3 binary

semaphores. The semaphores are initialized as S0=1, S1=0, S2=0.
How many times will process P0 print ‘0’?
A. At least twice
B. Exactly twice
C. Exactly thrice
D. Exactly once

15. The following code segment is executed on a processor which allows only register
operands in its instructions. Each instruction can have almost two source operands and
one destination operand.
Assume that all variables are dead after this code segment
c = a + b;
d = c * a;
e = c + a;
x = c *c;
if (x > a) {
y = a * a;
}
else {
d = d * d;
e = e * e;
}
Suppose the instruction set architecture of the processor has only two registers. The
only allowed compiler optimization is code motion, which moves statements from one
place to another while preserving correctness. What is the minimum number of spills to
memory in the compiled code?
A. 0
B. 1
C. 2
D. 3

16. Let m[0]…m[4] be mutexes (binary semaphores) and P[0] …. P[4] be processes.
Suppose each process P[i] executes the following:
wait (m[i]); wait(m[(i+1) mode 4]);

------
release (m[i]); release (m[(i+1)mod 4]);
This could cause (GATE CS 2000)
(a) Thrashing
(b) Deadlock
(c) Starvation, but not deadlock
(d) None of the above

17. Consider the following table of arrival time and burst time for three
processes P0,P1P0,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 a arrival or completion of processes. What is the average waiting time for the
three processes?
a)5.0ms
b)6.2ms
c)4.5ms
d)6.4ms

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

Process Arrival Time Processing Time

A 0 3

B 1 6

D 4 4

E 6 2
a)First Come First Serve
b)Shortest Job First
c)Shortest Remaining Time
d)Round Robin

19. A process executes the following code

for (i = 0; i< n; i++) fork();
The total number of child processes created is
(A) n
(B) 2^n - 1
(C) 2^n
(D) 2^(n+1) - 1;
20. 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 with different priorities for the two processes.
(D) Round robin scheduling with a time quantum of 5 ms.

21. At a particular time of computation the value of a counting semaphore is 7. Then 20

P operations and 15 V operations were completed on this semaphore. The resulting
value of the semaphore is:
(a) 42
(b) 2
(c) 7
(d) 12

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

23. The following program consists of 3 concurrent processes and 3 binary semaphores.
The semaphores are initialized as S0=1, S1=0, S2=0.
24. An operating system contains 3 user processes each requiring 2 units of resource
R.The minimum number of units of R such that no deadlocks will ever arise is
(a) 3
(b) 5
(c) 4
(d) 6

25. In the index allocation scheme of blocks to a file, the maximum possible size of the
file depends on
(a) the size of the blocks, and the size of the address of the blocks.
(b) the number of blocks used for the index, and the size of the blocks.
(c) the size of the blocks, the number of blocks used for the index, and the size of the
address of the blocks.
(d) None of the above

26. 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 1ms to move from one cylinder to adjacent one and shortest seek
time first policy is used?
(A) 95ms
(B) 119ms
(C) 233ms
(D) 276ms
27.A system shares 9 tape drives. The current allocation and maximum requirment of
tape drives for three processes are shown below:

Process Current Allocation Maximum Requirment

P1 3 7
P2 1 6
P3 3 5
which of the following best describes current state of the system?
(A) Safe, Deadlocked

(B) Safe, Not Deadlocked

(C) Not Safe, Deadlocked

(D) Not safe, Not Deadlocked

28. 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.

Process 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 preemptive priority
scheduling algorithm is _____________.
29.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 progress requirement.

(D) This solution violates bounded wait requirement.

30.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.
31. Consider the following processes, with the arrival time and the length of the CPU
burst given in milliseconds. The scheduling algorithm used is preemptive shortest
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 ________.

32.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 __________.

33.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

34.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.
35.Recall that Belady's anomaly is that the page-fault rate may increase as the number
of allocated frames increases. Now, consider the folliowingstatments:

S1: Random page replacement algorithm (where a page chosen at random is replaced)
suffers from Belady's anomaly
S2: LUR page replacement algorithm sufferes 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
36. 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{
wait(P);
wait(mutex);
//Add item to buffer
signal(mutex);
signal(Q);
}while(1);
do{
wait(R);
wait(mutex);
//Consume item from buffer
signal(mutex);
signal(S);
}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

37.A process executes the following code
for (i = 0; i< n; i++) fork();
The total number of child processes created is
(A) n
(B) 2^n - 1
(C) 2^n
(D) 2^(n+1) - 1;

38.At a particular time of computation the value of a counting semaphore is 7. Then 20

P operations and 15 V operations were completed on this semaphore. The resulting
value of the semaphore is:
________________________________________
(a) 42
(b) 2
(c) 7
(d) 12
39.An operating system contains 3 user processes each requiring 2 units of resource
R.The minimum number of units of R such that no deadlocks will ever arise is
(a) 3
(b) 5
(c) 4
(d) 6
40.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 __________.

Multiple Choice Questions (2 mark):

1. Consider the virtual page reference string 1, 2, 3, 2, 4, 1, 3, 2, 4, 1 On a demand

paged virtual memory system running on a computer system that main memory size of
3 pages frames which are initially empty. Let LRU, FIFO and OPTIMAL denote the
number of page faults under the corresponding page replacements policy. Then
a. OPTIMAL < LRU < FIFO
b. OPTIMAL < FIFO < LRU
c. OPTIMAL = LRU
d. OPTIMAL = FIFO
2. A processor uses 36 bit physical addresses and 32 bit virtual addresses, with a
page frame size of 4 Kbytes. Each page table entry is of size 4 bytes. A three level
page table is used for virtual to physical address translation, where the virtual address
is used as follows • Bits 30-31 are used to index into the first level page table • Bits 21-
29 are used to index into the second level page table • Bits 12-20 are used to index
into the third level page table, and • Bits 0-11 are used as offset within the page The
number of bits required for addressing the next level page table (or page frame) in the
page table entry of the first, second and third level page tables are respectively.
a. 20, 20 and 20
b. 24, 24 and 24
c. 24, 24 and 20
d. 25, 25 and 24

3. 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

4. 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.

Which one of the following statements is TRUE if all three processes run concurrently
starting at time t = 0?
A. All processes will finish without any deadlock
B. Only P1 and P2 will be in a deadlock
C. Only P1 and P3 will be in deadlock
D. All three processes will be in deadlock

5. 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 blocked state can take 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

6. A main memory unit with a capacity of 4 megabytes is built using 1M×1-bit DRAM
chips. Each DRAM chip has 1K rows of cells with 1K cells in each row. The time taken
for a single refresh operation is 100 nanoseconds. The time required to perform one
refresh operation on all the cells in the memory unit is
A. 100 nanoseconds
B. 100*210 nanoseconds
C. 100*220 nanoseconds
D. 3200*220 nanoseconds

7. Identify the correct order in which a server process must invoke the function calls
accept, bind, listen, and recv according to UNIX socket APL
A. listen, accept, bind recv
B. bind, listen, accept, recv
C. bind, accept, listen, recv
D. accept, listen, bind recv
8. Consider six memory partitions of sizes 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, 210KB, 468 KB and 491 KB in that order. If the best fit
algorithm is used, which partitions are NOT allotted to any process?
A. 200KB and 300 KB
B. 200KB and 250 KB
C. 250KB and 300 KB
D. 300KB and 400 KB

9. 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 4ms
P2 2 ms 9ms
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.0ms
B. 4.33ms
C. 6.33ms
D. 7.33ms

10. The amount of ROM needed to implement a 4 bit multiplier is

A. 64 bits
B. 128 bits
C. 1kbits
D. 2kbits

11. A multithreaded program P executes with x number of threads and uses 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

12. Consider the 3 process, P1, P2 and P3 shown in the table

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
13. Consider the following schedule for transactions T1, T2 and T3:
T1 T2 T3
Read(X)
Read(Y)
Read(Y)
Write(Y)
Write(X)
Write(X)
Read(X)
Write(X)
Which one of the schedules below is the correct serialization of the above?
A. T1 → T3 → T2
B. T2 → T1 → T3
C. T2 → T3 → T1
D. T3 → T1 → T2

14. The following program consists of 3 concurrent processes and 3 binary

semaphores. The semaphores are initialized as S0=1, S1=0, S2=0.

How many times will process P0 print ‘0’?

A. At least twice
B. Exactly twice
C. Exactly thrice
D. Exactly once

15. The following code segment is executed on a processor which allows only register
operands in its instructions. Each instruction can have almost two source operands and
one destination operand.
Assume that all variables are dead after this code segment
c = a + b;
d = c * a;
e = c + a;
x = c *c;
if (x > a) {
y = a * a;
}
else {
d = d * d;
e = e * e;
}
Suppose the instruction set architecture of the processor has only two registers. The
only allowed compiler optimization is code motion, which moves statements from one
place to another while preserving correctness. What is the minimum number of spills to
memory in the compiled code?
A. 0
B. 1
C. 2
D. 3

16. Let m[0]…m[4] be mutexes (binary semaphores) and P[0] …. P[4] be processes.
Suppose each process P[i] executes the following:
wait (m[i]); wait(m[(i+1) mode 4]);

------

release (m[i]); release (m[(i+1)mod 4]);

This could cause (GATE CS 2000)
(a) Thrashing
(b) Deadlock
(c) Starvation, but not deadlock
(d) None of the above
17. Consider the following table of arrival time and burst time for three
processes P0,P1P0,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 a arrival or completion of processes. What is the average waiting time for the
three processes?
a)5.0ms
b)6.2ms
c)4.5ms
d)6.4ms

18. For the processes listed in the following table, which of the following scheduling schemes will give
the lowest average turnaround time?
Process Arrival Time Processing Time

A 0 3

B 1 6

D 4 4

E 6 2
a)First Come First Serve
b)Shortest Job First
c)Shortest Remaining Time
d)Round Robin

19. A process executes the following code

for (i = 0; i< n; i++) fork();
The total number of child processes created is
(A) n
(B) 2^n - 1
(C) 2^n
(D) 2^(n+1) - 1;

20. 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 with different priorities for the two processes.
(D) Round robin scheduling with a time quantum of 5 ms.

21. At a particular time of computation the value of a counting semaphore is 7. Then 20

P operations and 15 V operations were completed on this semaphore. The resulting
value of the semaphore is:
(a) 42
(b) 2
(c) 7
(d) 12

22. Two processes, P1 and P2, need to access a critical section of code. Consider the
following synchronization construct used by the processes:
23. The following program consists of 3 concurrent processes and 3 binary semaphores.
The semaphores are initialized as S0=1, S1=0, S2=0.

24. An operating system contains 3 user processes each requiring 2 units of resource
R.The minimum number of units of R such that no deadlocks will ever arise is
(a) 3
(b) 5
(c) 4
(d) 6

25. In the index allocation scheme of blocks to a file, the maximum possible size of the
file depends on
(a) the size of the blocks, and the size of the address of the blocks.
(b) the number of blocks used for the index, and the size of the blocks.
(c) the size of the blocks, the number of blocks used for the index, and the size of the
address of the blocks.
(d) None of the above
26. 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 1ms to move from one cylinder to adjacent one and shortest seek
time first policy is used?
(A) 95ms
(B) 119ms
(C) 233ms
(D) 276ms
27.A system shares 9 tape drives. The current allocation and maximum requirment of
tape drives for three processes are shown below:

Process Current Allocation Maximum Requirment

P1 3 7
P2 1 6
P3 3 5
which of the following best describes current state of the system?

(A) Safe, Deadlocked

(B) Safe, Not Deadlocked

(C) Not Safe, Deadlocked

(D) Not safe, Not Deadlocked

28. 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.

Process 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 preemptive priority
scheduling algorithm is _____________.
29.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 progress requirement.

(D) This solution violates bounded wait requirement.

30.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.
31. Consider the following processes, with the arrival time and the length of the CPU
burst given in milliseconds. The scheduling algorithm used is preemptive shortest
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 ________.

32.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 __________.

33.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

34.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.
35.Recall that Belady's anomaly is that the page-fault rate may increase as the number
of allocated frames increases. Now, consider the folliowingstatments:

S1: Random page replacement algorithm (where a page chosen at random is replaced)
suffers from Belady's anomaly
S2: LUR page replacement algorithm sufferes 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

36. 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{
wait(P);
wait(mutex);
//Add item to buffer
signal(mutex);
signal(Q);
}while(1);
do{
wait(R);
wait(mutex);
//Consume item from buffer
signal(mutex);
signal(S);
}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

37.A process executes the following code

for (i = 0; i< n; i++) fork();
The total number of child processes created is
(A) n
(B) 2^n - 1
(C) 2^n
(D) 2^(n+1) - 1;
38.At a particular time of computation the value of a counting semaphore is 7. Then 20
P operations and 15 V operations were completed on this semaphore. The resulting
value of the semaphore is:
________________________________________
(a) 42
(b) 2
(c) 7
(d) 12
39.An operating system contains 3 user processes each requiring 2 units of resource
R.The minimum number of units of R such that no deadlocks will ever arise is
(a) 3
(b) 5
(c) 4
(d) 6
40.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 __________.

NUMERIC ANSWER TYPE QUESTION: (2 Marks)

1. Consider three concurrent processes P1, P2 and P3 as shown below, which
access a shared variable D that has been initialized to 100.

The process are executed on a uniprocessor system running a 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

2. A process executes the following code

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

The total number of child processes created is
3. A system has 32 bit Virtual adress and 8KB page size.main memory is 128 MB..the size of
page table, when page table ,when pt entry has 1 valid bit 1 modified bit and frame bits
is_____(MB)p.s what is frame bits..is it the frame entry size?
4. Consider a virtual memory system with FIFO page replacement policy. For an arbitrary page
access pattern, increasing the number of page frames in main memory will
5. 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?
6.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 will --------------

7. A multithreaded program P executes with x number of threads and uses 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 avilable. The minimum
value of x and the minimum value of y together for which execution of P can result in a deadlock
are ____

8. 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 memory. Semaphore S is initialized to two. What is
the maximum possible value of x after all processes complete execution?

9. Consider the resource allocation graph given in the figure.

.

10. Consider a machine with 64 MB physical memory and a 32-bit virtual address space. If the
page size is 4KB, what is the approximate size of the page table

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

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

13. 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.

14. 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 corressponding memory page
is available in memory, and D units if the memory access causes a page fault. It has been
experimental 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?
15. The following program consists of 3 concurrent processes and 3 binary semaphores. The
semaphores are initialized as S0=1, S1=0, S2=0.

How many times will process P0 print ‘0’?

D. Exactly once

16. 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
sources 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?
17. Consider a storage disk with 4 platters (numbered as 0, 1, 2 and 3), 200 cylinders
(numbered as 0, 1, … , 199), and 256 sectors per track (numbered as 0, 1, … 255). The
following 6 disk requests of the form [sector number, cylinder number, platter number] are
received by the disk controller at the same time: [120, 72, 2], [180, 134, 1], [60, 20, 0], [212, 86,
3], [56, 116, 2], [118, 16, 1] Currently head is positioned at sector number 100 of cylinder 80,
and is moving towards higher cylinder numbers. The average power dissipation in moving the
head over 100 cylinders is 20 milliwatts and for reversing the direction of the head movement
once is 15 milliwatts. Power dissipation associated with rotational latency and switching of head
between different platters is negligible. The total power consumption in milliwatts to satisfy all of
the above disk requests using the Shortest Seek Time First disk scheduling algorithm is ______
.\
18. Consider two processors P1 and P2 executing the same instruction set. Assume that under
identical conditions, for the same input, a program running on P2 takes 25% less time but incurs
20% more CPI (clock cycles per instruction) as compared to the program running on P1. If the
clock frequency of P1 is 1GHz, then the clock frequency of P2 (in GHz) is ________

19. 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

20. A hard disk system has the following parameters : o Number of tracks = 500 o Number of
sectors/track = 100 o Number of bytes /sector = 500 o Time taken by the head to move from
one track to adjacent track = 1 ms o Rotation speed = 600 rpm. What is the average time taken
for transferring 250 bytes from the disk ?

Multiple Select Questions(2Marks)

1. Which of the following are true about ZOMBIE process.

a. OS does not clear the information of a ZOMBIE unless wait () is called
b. The init process is the new parent of the ZOMBIE process
c. When a child process exit before parent process then the child process is called
ZOMBIE process
d. When a parent process exit before child process then the child process is called
ZOMBIE process
2. Signal handling : A signal handler is specified as a function, eg.,
Void sigint_handler(intsignum);
When a signal is “delivered” to a process, this function gets executed, as an
“asynchronous function call”.
Which of the following are true.
a. All the registers need to be saved before transferring control to the signal handler
function
b. Only program counter register need to be saved before transferring control to the
signal handler function
c. After the signal handler has finished executing, all the saved registres need to be
restored before resuming execution at the interrupted user instruction.
d. If any register’s value is to be stored before transferring control to the signal handler
function, one convenient location to store them is through pusig them to the process
stack.
3. Firefox uses a thread per tab, but Chrome uses a process per tab. Which of the
following are true:
a. Context switch is much faster in firefox over chrome
b. Firefox will have shared address space for its tabs. For chrome, address space is
different.
c. Firefox will require a specific interprocess communication interface whereas Chrome
does not require it.
d. If 1 tab in Firefox does some malicious activity, all threads are affected.
4. Which of the following are true,
a. Lidt is a privileged instruction.
b. IDT lives in the kernel address space
c. IGDT is a privileged instruction
d. Every process has its own GDT
5. What are the advantages of page table over segmentation?
a. Solves external fragmentation
b. Easy process memory growth
c. Smaller page table size over segmentation table
d. Bigger virtual memory size
6. Which of the following Is true about demand paging?
a. It requires hardware support to implement demand paging
b. It can be completely implemented in software
c. sum total of the number of valid pages in all page tables still cannot exceed total
number of memory frames
d. sum total of the number of valid pages in all page tables still can now exceed
total number of memory frames
7. If the memory access time is denoted by ‘ma’ and ‘p’ is the probability of page fault
(0<=p<=1) caused by the swapped out pages. Then the access time in expectation for a
demand paging enabled memory is?
a. p x ma + (1-p) x page fault time
b. ma + page fault time
c. (1-p) x ma + p x Page fault time
d. ma + p x page fault overhead time
8. Select all the correct statements true for the page replacement policy?
a. 2nd chance algorithm in a approximation for LRU algorithm
b. Nth chance algorithm is a better approximation for LRU algorithm, where N>2
c. LRU is itself a heuristic for the optimal page replacement algorithm
9. Which of the following synchronization abstractions (or their equivalent) are used in
xv6?
a. Mutex lock
b. Conditional variables
c. Semaphores
d. monitors
10. Which of the following is typically a part of the operating system but not the kernel?
a. Graphical User Interface
b.Network Management
c. Device Driver Management
d.Compiler
e. Utilities such as ls, chmod and chown
11. The "seek" system call allows the application program to change the value of the file's
offset
so that subsequent read/write is performed from a new position in the file. Which of the
following task will
a. require the use of seek operation:
b. Copying the contents of file A to B
c. Reversing the contents of a file
d. Insert/update/delete at a particular point
12. Which of the following can have an operating system?
a. Microprocessor
b. Car
c. Phone
d. Watches
13. Which of the following are valid differences between CreateProcess() and fork():
A. fork() by default creates a child process with same file descriptors while
CreateProcess() does not.
B.CreateProcess() by default creates a child process with same file descriptors while
fork() does not.
C.fork() duplicates the program for different process. CreateProcess() creates different
process withnew program.
D.CreateProcess() does not return the pid of the child process to the parent process
while fork()returns the child process pid to parent process.
E.CreateProcess() is more efficient than fork() then exec() without copy-on-write.
14. Consider two implementations of 2 >& 1 (i.e redirecting ERR to OUTPUT file
location):
// Implementation A:
close(1);
open(“output_file_A”);
close(2);
open(“output_file_A”);
write(1, “operating”,9);
write(2,”system”,6);
// Implementation B:
close(1);
open(“output_file_B);
close(2);
dup(1);
write(1, “operating”,9);
write(2,”system”,6);
Which of the following options are correct for above implementations?
a.Output_file_A content: “operatingsystem” and Output_file_A content: “system”
b. The offset for output_file_A is 6 and offset for output_file_B is 15
c.Output_file_A content: “system” and Output_file_A content: “operatingsystem”
d. The offset for output_file_A is 15 and offset for output_file_B is 6

15.Which of the following is typically a part of the operating system but not the kernel?
a.Graphical User Interface
b.Network Management
c.Device Driver Management
d.Compiler
16. The “Seek “ System call allows the application program to change the value of the file’s
offset so that subsequent read/write is performed from a new position in the file.Which of the
following task will require the use of seek operation:
a.Copying the contents of file A to B
b.Reversing the contents of a file
c.Insert/update/delete at a particular point
d.Finding a particular character in a file

17.Which of the following can have an operating system?

a.Microprocessor
b.Car
c.Phone
d.Microcontroller
18.What of the following are functions of MMU?
a.Fetch the data from the memory those address is given to MMU as input
b.Use Segment registers to create a mapping from program’s address space to physical
address space
c.It prevents the user programs from accessing the data belonging to other processes
or OS
19.Page fault occurs when
a.the page is corrupted by application Software
b.the page is in main memory
c.the page is not in main memory
d.the process requesting the page does not have privilege to access the page
20. In case of disk cache write policy is better than write through policy. which of the following
statements are true for write back policy?
a.The better performance can be attributed to the better amortised performance of disk
when it has multiple outstanding I/O requests
b.It saves all but last write from taking place,in case of disk when it has multiple
outstanding I/O requests
c.It is always efficient to use write back policy even in case of multiple systems
connected to the disk.