(AUTONOMOUS)

Affiliated to JNTUH, Approved by AICTE, Accredited by NAAC with A++ Grade, ISO 9001:2015 Certified
Kacharam, Shamshabad, Hyderabad – 501218, Telangana, India

A8510 – OPERATING SYSTEMS II [Link] I Sem

Problem Based Learning Questions
CO# BL#
[A] OPERATING SYSTEMS OVERVIEW:
[Link].
Explain the following Operating Systems CO1 BL2
a) Batch Processing Systems
1.
b) Distributed Systems
c) Special Purpose Systems.
2. Identify the requirements for distributed systems. CO1 BL3
Summarize the various characteristics to be considered in the design of Operating CO1 BL3
3.
systems.
4. List the differences between Multiprocessing and Multiprocessor systems. CO1 BL2
[B] PROCESS MANAGEMENT:
Assume that following jobs have arrived in the order 1,2,3,4 and 5: CO2 BL3
Job Arrival Time Burst Time Priority
1 0 15 2
2 2 3 1
3 5 5 5
5. 4 6 8 4
5 7 12 3
Give Gantt chart and calculate Avg. Turnaround Time and Waiting Time for:
i) FCFS
ii) SRTF and Preemptive priority algorithm

Consider the following processes with CO2 BL3

their burst times and arrival times given:
Process Arrival Time Burst Time
P1 0 8
6. P2 1 4
P3 2 9
P4 3 5
Write the Gantt chart. Using Pre-emptive Shortest job first algorithm, calculate the
Average waiting time and average turnaround time.
Summarize a Comparison table of Throughput, Response time and Waiting time CO2 BL2
7.
average for various scheduling algorithms.
Consider the following set of process with their arrival and burst times as shown. Draw CO2 BL3
the Gantt chart and compute the turn-around time and waiting time of each job using
the
8. following scheduling algorithms:
i. FCFS
ii. SJF
iii. Round Robin (time quantum = 2)
 Consider the following set of processes, with the length of the CPU burst given in CO2 BL3
milliseconds:

9.
The processes are assumed to have arrived in the order P1, P2, P3, P4, and P5 all at time
0.
i. Draw the Gantt Charts that illustrate the execution of these processes using the
following scheduling algorithms: Non preemptive Priority (a smaller priority
number implies a higher priority) and RR (Quantum = 1).
ii. Calculate the Average Waiting time and Average Turnaround Time in both the
algorithms.

Consider the following set of processes, with the length of the CPU burst given in CO2 BL4
milliseconds.

10.
The processes are assumed to have arrived in the order P1, P2, P3, P4, and P5 all at time
0.
i. Draw the Gantt charts that illustrate the execution of these processes using the
following scheduling algorithms, FCFS, SJF, non-preemptive priority. Note: A smaller
priority number implies a higher priority and RR (quantum=1).
ii. What is the turnaround time of each process for each of the scheduling algorithms?
iii. What is the waiting time of each process for each of the scheduling algorithms?

Say we have the process arrival time chart given below: CO2 BL4

11.
 Draw a Gantt chart to illustrate how these processes would be scheduled using Round
Robin (RR) and First-come First-Served (FCS) scheduling, and calculate the waiting time
for each process. If when choosing a process to schedule next you could legally choose
any of a number of processes, choose the one with the lowest-numbered name;
i.e.,choose p5 if i < j. Do not include context-switching time in your chart. Assume that
the quantum is set to 5 time units.
CO2 BL3

12.

Assume that following jobs have arrived in the order 1,2,3,4 and 5: CO2 BL3
Job Arrival Time Burst Time Priority
1 0 15 2
2 2 3 1
3 5 5 5
13. 4 6 8 4
5 7 12 3
Give Gantt chart and calculate Avg. Turnaround Time and Waiting Time for:
iii) FCFS
iv) SRTF and Preemptive priority algorithm

Consider the following processes CO2 BL3

Process Arrival Time Burst Time Priority
P1 0 5 4
P2 1 3 2
14. P3 2 3 1
P4 4 4 5
P5 5 5 3
What is Average Waiting time and Turnaround time using Preemptive SJF and
Priority Scheduling? (1 -> low Priority).
Compare Message passing and Shared memory systems for inter process CO2 BL4
15.
communication.
Consider a system running ten I/O-bound tasks and one CPU-bound task. Assume that CO2 BL4
the I/O-bound tasks issue an I/O operation once for every millisecond of CPU computing
and that each I/0 operation takes 10 milliseconds to complete. Also assume that the
context-switching overhead is 0.1 millisecond and that all processes are long-running
tasks.
16.
Describe the CPU utilization for a round-robin scheduler when:
a. The time quantum is 1 millisecond
b. The time quantum is 10 milliseconds
 [C] PROCESS SYNCHRONIZATION:
CO2 BL4

17.

The following program consists of 3 concurrent processes and 3 binary semaphores. CO2 BL4
The semaphores are initialized as S0 = 1, S1 = 0, S2 = 0.
Process P0
while(true)
{
wait(S0);
print '0';
release(S1);
release(S2);
}
18.
----------------------
Process P1
wait(S1);
release(S0);

Process P2
wait(S2);
release(S0);
How many times will P0 print ‘0’
?
Each process Pi, i = 0,1,2,3,……,9 is coded as follows : CO2 BL4
repeat
P(mutex)
{Critical Section}
V(mutex)
19.
Forever

The code for P10 is identical except that it uses V(mutex) instead of P(mutex). What
is the largest number of processes that can be inside the critical section at any
moment (the mutex being initialized to 1)
[D] MEMORY MANAGEMENT:
Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600 KB (in order), CO3 BL3
how would each of the first-fit, best-fit, and worst-fit algorithms place processes of 212
20.
KB, 417 KB, 112 KB, and 426 KB (in order)? Which algorithm makes the most efficient
use of memory?
Compare the memory organization schemes of contiguous memory allocation, pure CO3 BL2
segmentation, and pure paging with respect to the following issues:
21. a. External fragmentation
b. Internal fragmentation
c. Ability to share code across processes
 Consider a paging system with the page table stored in memory. CO3 BL3
a. If a memory reference takes 200 nanoseconds, how long does apaged memory
reference take?
22.
b. If we add TLBs, and 75 percent of all page-table references are found in the TLBs,
what is the effective memory reference time? (Assume that finding a page-table entry in
the TLBs takes zero time, if the entry is there.)
Consider a logical address space of eight pages of 1024 words each, mapped onto a CO3 BL3
physical memory of 32 frames.
23.
a) How many bits are there in the logical address?
b) How many bits are there in the physical address?
Assuming a 1-KB page size, what are the page numbers and offsets for the following CO3 BL3
address references (provided as decimal numbers):
a. 2375
24. b. 19366
c. 30000
d. 256
e. 16385
Consider a computer system with a 32-bit logical address and 4-KB page size. The CO3 BL3
system supports up to 512MB of physical memory. How many entries are there in each
25. of the following?
a. A conventional single-level page table
b. An inverted page table
Consider the page reference string 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1. How many CO3 BL3
page faults would occur for the following pages replace algorithms by considering 3 and
26.
4 frames?
i) FIFO ii) LRU iii) Optimal
Given reference to the following pages by a program, CO3 BL3
0,9,0,1,8,1,8,7,8,7,1,2,8,2,7,8,2,3,8,3. How many page faults will occur if the program
27. has
three page frames available to it and uses FIFO ,LRU and OPT page replacement
algorithms?
Consider the following page reference string CO3 BL3
1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6.
28.
Compare the page faults by applying FIFO, LRU and Optimal Page Replacement
algorithms.
Consider the following page reference string A, B, C, D, B, A, E, F, A, B, CO3 BL3
C, G, F, C, F. How many page faults would occur for the following page replacement
algorithm assuming three and four frames? Remember all frames are initially empty:
29.
FIFO
Optimal
LRU
Consider the following segment table: CO3 BL3

30.

What are the physical addresses for the following logical addresses?
 i. 0,430
ii. 1,10
iii. 2,50
iv. 3,400
v. 4,11
A certain computer provides its users with a virtual-memory space of 232 bytes. The CO3 BL3
computer has 218 bytes of physical memory. The virtual memory is implemented by
31. paging, and the page size is 4096 bytes. A user process generates the virtual address
11123456. Explain how the system establishes the corresponding physical location.
Distinguish between software and hardware operations.
Suppose we have a demand paged memory. The page table is held in registers. It takes CO3 BL3
8 milliseconds to service a page fault if an empty frame is available or the replaced page
is not modified and 20 milliseconds if the replaced page is modified. Memory access
32. time is 100 nanoseconds. Assume that the page to be replaced is modified 70 percent of
the time. What is the maximum acceptable page-fault rate for an effective access time
of no more than 200 nanoseconds?

[E] FILE SYSTEM:

CO4 BL3

33.

Demonstrate how Directory is implemented in Operating System. Explain Various CO4 BL2
34.
Directory structures.
[F] MASS-STORAGE STRUCTURE:
Suppose that a disk drive has 5000 cylinders, numbered 0 to 4999. The drive is currently CO4 BL3
serving a request at cylinder 143, and the previous request was at cylinder 125. The
queue of pending requests, in FIFO order is:
86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130
Starting from the current head position, what is the total distance that the disk arm
35. moves to satisfy all the pending requests for each of the following disk-scheduling
algorithms?
i. FCFS
ii. SSTF
iii. SCAN
iv. LOOK
Suppose the head of moving-head disk with 200 tracks, numbered 0 to 199 is currently CO4 BL3
serving a request at track 143 and has just finished a request at track 125. if the queue
of requests is kept in the FIFO order
86, 147, 91, 177, 94, 150, 100, 175, 130
What is total head movement to satisfy this request for the following disk scheduling
36.
algorithms?
i) FCFS
ii) SSTF
iii) C-SCAN
iv) LOOK
 Consider a disk queue with requests for I/O to blocks on cylinders: 98, 183, 37, 122,
14,124, 65, 67. If the disks head is initially at cylinder 53, the previous request was at
37.
cylinder number 75. Find out the total head movements by using various disk scheduling
algorithms.
Given a disk with 200 tracks, numbered from 0 to 199. It takes 1ms for the disk CO4 BL3
Read/Write head to travel from the current track to the next one, and that it is originally
positioned at track 89 and “moving towards” the lower tracks. These requests arrive at
the following times as shown in the table below:

38.

i. Draw diagrams showing the order in which the above 10 requests are processed,
under each of these disk scheduling algorithms? SCAN, LOOK.
ii. Compute the Total Service Time of all these requests for each disk scheduling
algorithms; ignore the transfer time and latency time?
CO4 BL3

39.

[G] DEADLOCKS:
Consider the following snapshot of a system CO5 BL3

Allocation Max. Available

A B C D A B C D A B C D
P1 0 0 1 3 0 0 1 2 1 5 2 0
P2 1 0 0 0 1 7 5 0
P3 1 3 5 4 2 3 5 6
P4 0 6 3 2 0 6 5 2
40.
Answer the following question using the banker’s algorithm:

a) What is the content of matrix “Need”?

b) Is the System in a safe state?
c) If a request from process P1 arrives for (0, 4, 2, 0) can the request be granted
immediately?

Choose the various methods to recover from deadlock. Justify with examples. CO5 BL2
41.

42. Consider the following snapshot of a system: CO5 BL3

 Using Banker’s algorithm, find:
What is the content of the need matrix?
Is the system in a safe state?
Is request from p1=(1,0,2) and then request from p4=(3,3,0) can be granted or not?
Demonstrate with a resource allocation graph for detecting single instance of a resource CO5 BL2
43.
type.
Consider the following snapshot of a system: CO5 BL3

44.

Using Banker’s algorithm, find:

i. What is the content of the need matrix
ii. Is the system in a safe state

45. Show with protocols how to prevent deadlock with examples. CO5 BL2
CO5 BL3

46.

Consider a system with five process P1 to P5 and three resource types P, Q and R. CO5 BL3
resource type P has 7 instances, resource type Q has 5 instances, and resource type R
47.
has 10 instances. Suppose that at time T0, the following snapshot of the system has
been taken:
Answer the following questions.
i. What is the content of need matrix?
ii. Is the system in safe state?
iii. If a request from process P1 arrives for (0,2,0), can this request be granted
immediately?
iv. If a request from process P4 arrives for (0,3,3), can this request be granted
immediately?