1.

Ques on 1: MCQ with JUSTIFICATION (40 Minutes and 40 Points]

1.1. Ques on 1.1: [4 Minutes and 2 Points] This solu on to the dining philosophers' problem
has (there may be more than one); and WHY?
philosopher():
wait (chopstick)
wait (chops ck{(i+1) mod N])
….
Eat
….
signal (chopstick (])
signal (chops ck|(¡+1) mod N)

A. Circular wait
B. Hold and wait
C. Mutual exclusion
D. No preemption
E. Deadlock

1.2. Ques on 1.2: (5 Minutes and 4 Points] Three CPU intensive processes enquire 10-, 20-
and 30- me units and arrive at mes 0, 2 and 6 respec vely. The opera ng system
implements a shortest remaining time first scheduling algorithm. Considering that the
context switches at time zero and at the end are not counted, the number of context
switches needed is and how with step-by-step declaration:
A. 4
B. 3
C. 2
D. 1
1.D.1. Justification: shortest remaining time, also known as shortest remaining time, first (SRTF), is a
scheduling method that is a pre-emptive version of shortest job next scheduling. In this scheduling
algorithm, the process with the smallest amount of time remaining until completion is selected to
execute. Since the currently executing process is the one with the shortest amount of time remaining
by definition, and since that time should only reduce as execution progresses, processes will always
run until they complete, or a new process is added that requires a smaller amount of time.

1.3. Ques on 1.3: [2 Minutes and 2 Points] The scheduling algorithm, which is non-pre-emptive,
is and WHY?
A. Multilevel queue scheduling with feedback
B. Multilevel queue scheduling
C. First-in-First-Out
D. Round Robin
a. Justification: Multi Level Queue Scheduling – Preemption takes place when a
process of higher priority arrives
 Multi-Level Queue Scheduling with Feedback – Preemption takes a place when
process of higher priority arrives or when the quantum of high priority queue
expires, and we need to move the process to low priority queue

1.4. Ques on 1.4: [4 Minutes and 4 Points] Let P1 and P2 be the two processes and S1 and
S2 be the two shared Boolean variables. The ini al values of S1 and S2 are randomly
assigned. For accessing the cri cal sec ons of P1 and P2 the methods sed by them are
given below:
Method used by P1 Method used by P2
While (S1==S2): While (S1! -S2);
Critical section Critical section
S1=S2: S2=not (S1);
The statement that describes the properties achieved is and WHY?
(A) Progress but not mutual exclusion
(B) Mutual exclusion but not progress
(C) Both mutual exclusion and progress
(D) Neither mutual exclusion nor progress
i. Justification: In this mutual exclusion is satisfied because at any point of time either
S1=S2 or S1! = S2, but not both. But here progress is not sa sfied because suppose
S1=1 and S2=0 and P1 is not interested to enter the cri cal sec on but P2 wants to
enter the cri cal sec on, and P2 will not be able to enter, because un l P1 will not
enter the cri cal sec on, S1 will not become equal to S2. So, if one process is not
interested in entering the critical section, it will not allow the other process to enter
the critical section which is interested. So, progress is not satisfied.
1.5. Ques on 1.5: [2 Minutes and 2 Points] Consider a computer system with 6 resources
and n processes competing for them. What is the maximum value of n for the system to
be deadlock free assuming each process may need 3 resources?
A. 3
B. 2
C. 4
D. 7
a. Justification: or a system to be deadlock free, Sum of max need of processes < No. of
processes + No. of resources
3n < n + 6
=> 2n < 6
=> n < 3
so the maximum value of n for which the system is guaranteed to be deadlock free is
2 [ n is less than 3 means max value for n is 2
1.6. Ques on 1.6: [4 Minutes and 4 Points] A system has m number of resources of same
type and 3 processes A, B and C. share these resources. A, B and C have the peak
demand of 3, 4 and 6 respec vely. Deadlock will not occur if and WHY?
A. m= 15
B. m=8
C. m= 13
 D. m= 9
 Justification: Consider a system having m of resources of the same type. These resources are
shared by 3 processes A, B and C, which have peak demands of 3, 4 and 6 respec vely. For 13
value of n deadlock will not occur. Consider the peak demand situation of resources (A, B, C)=
(3,4,6). Total of max needs < (no. of resource instances + no. of processes) (
3+4+6) < m+3.
m>10. Hence m should be eleven or above. Only 13 qualify the criteria. Deadlock refers to a
specific condition when two or more processes are each waiting for another to release a
resource, or more than two processes are waiting for resources in a circular chain

1.7. Ques on 1.7: [5 Minutes and 5 Points] in the table shown below P1, P2 and P3 are
three processes:
Process Arrival time Time units required
P1 0 5
P2 1 7
P3 3 4
What is the comple on order of the 3 processes under the scheduling policies FCFS and
Round Robin (RR) with CPU quantum me of 2 units? You need to demonstrate how.
A. FCFS: P1, P2, P3 RR: P1, P3, P2
B. FCFS: P1, P3, P2 RR: P1, P2, P3
C. FCFS: P1. P3. P2 RR: P1, P3, P2
D. FCFS: P1. P2. P3 RR: P1. P2. P3
a. Justification: FCFS is a scheduling algorithm in which the process that scheduled
first will execute first completely. And Round Robin is a scheduling algorithm in
which the process executes for a fixed CPU quantum time then the next
process gets executed then the next process and goes on.

1.8. Ques on 1.8: 2 Minutes and 2 Points] For me-shared operating systems the most
suitable scheduling policy is and WHY?
A. Shortest job first
B. Last come first served
C. First come first served
D. Round Robin
a. Justification: to schedule processes fairly, a round-robin scheduler generally employs
time-sharing, giving each job a time slot or quantum (its allowance of CPU time),
and interrupting the job if it is not completed by then. It is designed especially for
time-sharing systems.
1.9. Ques on 1.9: [5 Minutes and 5 Points] Consider the following I/O scenarios on a single-
user PC
A. A mouse used with a graphical user interface: When higher priority operations are taking place
buffering is needed to record mouse movements. In this case, spooling and caching are not appropriate.
Interrupt driven I/O is most appropriate
B. A hard drive on a multitasking operating system
 C. A disk drive containing user files. Caching is used to hold disk-resident data for better performance.
Buffering is used to hold data while in transit from the user and vice versa. Spooling is not necessary as disks
are shared-access devices. Interrupt driven I/O is likely to give the best performance for devices such as
disks that transfer data at slow rates
D. A graphics card with direct bus connection

For each of the above I/O scenarios, would you use polled I/O, or Interrupt-Driven 1/O or DMA? Give
reasons for your choices and how does DMA increase the concurrency

a) Buffering may be needed to record mouse movement during times when higher-priority
operations are taking place. Spooling, caching is inappropriate. Interrupt-driven I/O is
most appropriate.
b) Buffering may be needed to manage throughput difference between the tape drive and
the source or destination of the I/O. Caching can be used to hold copies of data that
resides on the tape, for faster access. Spooling could be used to stage data to the device
when multiple users desire to read from or write to it. Interrupt=driven I/O is likely to
allow the best performance.
c) Buffering can be used to hold data while in transit from user space to the disk, and vice
versa. Caching can be used to hold disk-resident data for improved performance.
Spooling is not necessary because disks are shared-access devices. Interrupt-driven I/O
is best for devices such as disks that transfer data at slow rates.
d) Buffering may be needed to control multiple access and for performance (double-
buffering can be used to hold the next screen image while displaying the current one).
Caching and spooling are not necessarily due to the fast and shared-access natures of
the device. Polling and interrupts are only useful for input and for I/O completion
detection, neither of which is needed for a memory-mapper device

1.10. Ques on 1.10: [3 Minutes and 3 Points] If t1 is the me taken to switch between
user and kernel modes of execu on and t2 is the me to switch between two processes
then the rela on between 11 and t2 is and why?
A. t1< t2
B. 11 > 12
C. 11 = 12
D. No rela on exists between 11 and t2
a. Justification: Process switches or Context switches can occur in only kernel mode. So, for
process switches first we must move from user to kernel mode. Then we must save the PCB
of the process from which we are taking off CPU and then we have to load PCB of the
required process. At switching from kernel to user mode is done. But switching from user to
kernel mode is a very fast operation (OS must just change single bit at hardware level)
1.11. Ques on 1.11: [4 Minutes and 4 Points] What do you think is the best CPU
scheduling method among these? Explain WHY?
A. First come first serve (FCFS) Simplest scheduling algorithm that schedules according to arrival
times of processes. First come first serve scheduling algorithm states that the process that
requests the CPU first is allocated the CPU first
B. Shortest job first (SJF): Process which have the shortest burst time are scheduled first. If two
processes have the same bust time then FCFS is used to break the tie. It is a non-preemptive
scheduling algorithm
C. Shortest remaining job first (SRTF): It is preemptive mode of SJF algorithm in which jobs are
schedule according to shortest remaining time.
D. Priority scheduling: In this scheduling, processes are scheduled according to their priorities, i.e.,
highest priority process is scheduled first. If priorities of two processes match, then schedule
according to arrival time. Here starvation of process is possible.
E. Round robin scheduling: Each process is assigned a fixed time (Time Quantum/Time Slice) in
cyclic way. It is designed especially for the time-sharing system. The ready queue is treated as a
circular queue.
F. Multi-Level Feedback Queues: It allows the process to move in between queues. The idea is to
separate processes according to the characteristics of their CPU bursts. If a process uses too much
CPU time, it is moved to a lower-priority queue.
a. Justification:

1.12. Ques on 1.12: [5 Minutes and 3 Points] The program given below consists of
three concurrent processes PO, P1, P2 and three binary semaphores with the values SO
=1. S1 = 0. S2 = 0.

Process P0 Process P1 Process P2

wait (s0),
Print '01 wait (S1), wait (s2);
release (S1) release (S1) release (s0);
release (S2);
How many times the process PO will print 'O'?
a) At least twice
b) Exactly twice
c) Exactly thrice
d) Exactly once
a. Justification:
i. ini ally only P0 can go inside the while loop as 𝑆0 = 1, 𝑆1 = 0, 𝑆2 = 0.
ii. Minimum no. of me 0 printed is twice when execute in this order (𝑝0 −> 𝑝1 −>
𝑝2 −> 𝑝0)
iii. Maximum no. of me 0 printed is thrice when execute in this order (𝑝0 −>
𝑝1 −> 𝑝0 −> 𝑝2 −> 𝑝0).
2. Question 2: [30 Minutes and 30 points]
2.1. Ques on 2.1: What is a cri cal sec on? (2 Minute and 2 Point)
It's a memory location, or part of the process code, or disk space which is shared by processes
where all processes may be able to change stored values

2.2. Ques on 2.2: Give an example of a cri cal sec on. (2 Minute and 2 Point)
1. Progress
Progress means that if one process doesn't need to execute into critical section then it
should not stop other processes to get into the critical section.
2. Bounded Waiting
We should be able to predict the waiting time for every process to get into the critical
section. The process must not be endlessly waiting for getting into the critical section.

2.3. Ques on 2.3: What are the three requirements that a solu on to the cri cal sec on
problem must sa sfy with your Explana on of the meaning of each. (4 Minutes and 5
Points)
1. Mutual Exclusion: At most, one process/thread is allowed to execute in a shared CS.
2. Progress: If a process/thread wishes to execute its CS (and no other processes/threads
are currently executing in it) then the processes which are allowed to decide if this
process/thread gains entrance are those not currently executing their remainder
section.
3. Bounded waiting: If a process/thread i is in entry section, then there is a bound on the
number of times that other processes/threads are allowed to enter the critical section
before process/thread i’s request is granted

2.4. Question 2.4: [5 Minutes and 5 Points] Consider the following algorithm for
synchronizing the entry of processes into the critical section.
do {
flag[i] = TRUE;
turn =i;
while (flagli] && turn==i);
CS // CRITICAL SECTION.
Flag[i] = false;
REMAINDER SECTION // other non-C$ code
} while (TRUE);
Does this algorithm satisfy all the requirements of synchronization? Explain in detail
which requirement has been satisfied and why or why not?
Yes So. that can be observed is, if 2 processes wants to enter the CS, the process which
executes " turn=j" statement first is always the first one to enter the CS (after the other process
executes turn=j"

2.5. Ques on 2.5: A system has four processes, P1 through P4, and three types of
resources, R1 (3 units), R2 (2 units) and R3 (2 units). Process P1 holds 1 unit of R1 and
requests 1 unit of R2. Process P2 holds 2 units of R2 and requests 1 unit of R1 and 1
 unit of R3. P3 holds 1 unit of R1 and requests 1 unit of R2. P4 holds 2 units of R3 and
requests 1 unit of R1.
A. Draw the resource alloca on graph for this system. (5 Minutes and 5 Points)

B. Is there a danger for deadlock? If yes, what are the deadlocked processes? If no,
what is the safe sequence? (6 Minutes and 5 Points)
YES. There is a cycle, with deadlock. And the resources not enough

2.6. Problem 2.6:

A. Discuss the effect of the Quantum Time on the performance of the RR
scheduling algorithm. (3 Minutes and 3 Points)
in Round Robin Scheduling, the time quantum is fixed and then processes are scheduled
such that no process gets CPU time more than one time quantum in one go. If time
quantum is too large, the response time of the processes is too much which may not be
tolerated in interactive environment.
B. Does swapping time of the process affect the setting of the Quantum Time?
Give your proposal of how to set the quantum time by considering the swapping
me. (3 Minutes and 3 Points)
3. Question 3: [30 Minutes and 30 points]
3.1. Ques on 3.1: [3 Minutes and 3 Points] In the following RAG diagram below, show with
a single request, you can deadlock all processes.

3.2. Problem 3.2: [6 Minutes and 6 Points] Consider a variant of the Round Robin (RR)
scheduling algorithm in which the entries in the ready queue are pointers to the PCBs.

a. What would be the effect of putting two pointers to the same process in the
ready queue? (2 Points)
The process would be run twice as many times.
b. What would be major advantages and disadvantages of this scheme? (2
Points)
a) Advantages
1. It would allow the user to prioritize more important processes.
2. It prevents starvation of lower priority processes.
3. We do not have to change the scheduling algorithm.
b) Disadvantage 1
1. Context switching will now have a larger effect than it did before.
2. Removing processes from the running queue is now significantly harder, as
you would have to search through the whole list.

c. How would you modify the basic RR algorithm to achieve the same effect
without the duplicate pointers? (2 Points)
Allow the quantum time each process gets to be changed on a per process
basis.
3.3. Problem 3.3: (5 Minutes and 5 Points] Given the following state transi on diagram for
processes, what are the correct labels for I, II, III and the causes of the transitions?

3.4. Problem 3.4: 3 Minutes and 3 Points] Explain what should be done by the OS to
improve the CPU utilization? and HOW?
Use Multiprogramming improves CPU utilization as it organizes a number of jobs where CPU
always has one to execute.
3.5. Problem 3.5 (5 Minutes and 5 Points) We discussed in the class we approaches used by
the OS for recovering from the deadlock. Discuss based on your understanding which
approach is more costly: And briefly explain your proposed ideas of how to optimize lie
Cost? Do you always favor one approach than the other? and why:
1. Process Termination:
a) Abort all the Deadlocked Processes: Aborting all the processes will certainly break the
deadlock, but with a great expense.
b) Abort one process at a time until deadlock is eliminated: Abort one deadlocked
process at a time, until deadlock cycle is eliminated from the system
2. Resource Preemption:
a) Selecting a victim: We must determine which resources and which processes are to
be preempted and the order to minimize the cost
b) Rollback: we must determine what should be done with the process from which
resources are preempted
c) Starvation: In a system, it may happen that same process is always picked as a
victim. As a result, that process will never complete its designated task.
3.6. Problem 3.6: 5 Minutes and 5 Points] Consider a uni-processor computer system that
has 2 processes and both of them alternate 1Oms CPU bursts with 90ms IN/OUT bursts.
Both the processes were created at nearly the same time and the IN/OUT of both the
processes can proceed in parallel. For this system, what is the scheduling strategies that
will result in the least CPU utilization (over a long period of time)?
First come first served scheduling
from 0−10: process 1
from 10−20: process 2
from 100−110: process 1
from 110−120: process 2
So, in every 100 ms, CPU is u lized for 20 ms, CPU u liza on =20%
3.7. Problem 3.7: [3 Minutes and 3 Points] What is meant by Direct and Indirect Process
Communication? List the required primitives the OS should provide to allow these
types of communications to occur?
 direct communication
o With direct communication each process that requires to communicate must explicitly
name the recipient or sender of the communication. The send and receive primitives are
o Send (P,message) - Send a message to process P.
o Receive (Q,message) - Receive a message from process Q
 Indirect communication
o With indirect communication, the messages are sent to and received from mailboxes or
ports. A mailbox can be viewed abstractly as an object into which messages can be
placed by processes and from which messages can be removed. Every mailbox has a
unique identification. Two processes can communicate only if they share a mailbox. The
primitives are
o Send (A, message) - Send a message to mailbox A.
o Receive (A, message) - Receive a message from mailbox A.