B.Tech.

/CSE/4th Sem-E/2024/CSC401
Indian Institute of Information Technology Kalyani
End Semester Examination, Spring 2023 - 2024
Subject: Operating Systems Time: 03 Hrs.
Paper Code: CSC401 Full Marks: 50

Instructions:
[1]. Answer all questions and each answer should be in your own words, otherwise, you will be awarded
zero mark. [2] All parts of a question should be answered consecutively. [3]. Answer the questions to the
points. [4]. Answer script should be neat and clean. [5]. Do not write anything on the question paper.
[6]. Number of pages in the question paper: 03.

Q1. Answer the following questions. [2 + 2 + 6 = 10]

(a) Consider the exponential average formula used to predict the length of the next CPU burst. What
is the implications of assigning the following values to the parameters used by the algorithm?

α = 0 τ0 = 100 milliseconds

(b) Consider the exponential average formula used to predict the next CPU burst. If α = 0.99 and
τ0 = 20 milliseconds, previous runs are as follows 6, 2. Find the values of τ1 , and τ2 .

(c) Consider the following set of processes, with the length of the CPU burst given in milliseconds:

Process Arrival time CPU Brust-time Priority

P1 0 10 3
P2 0 1 1
P3 0 2 3
P4 0 1 4
P5 0 5 2

The processes are assumed to have arrived in the order P1 , P2 , P3 , P4 , P5 . Draw the Gantt charts
that illustrate the execution of these processes using the following scheduling algorithms: SJF,
nonpreemptive priority (a smaller priority number implies a higher priority), and RR (quantum =
2 ms).

Q2. Given the following statement for the Banker’s Algorithm. There are five processes P0 , P1 , P2 , P3 ,
P4 and four resource types A, B, C and D. Consider the following snapshot of a system:

[2 + 4 + 4 = 10]

Process Current Allocation Maximum Demand Available

A B C D A B C D A B C D
P0 0 0 1 2 0 0 1 2 1 5 2 0
P1 1 0 0 0 1 7 5 0
P2 1 3 5 4 2 3 5 6
P3 0 6 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 6

(a) What is the content of the Need matrix?

1
Page faults
Miss ratio
Hit ratio
(b) Is the system in a safe state? Justify your answer.
(b) [5 points] LRU algorithm:
(c) If a request from process P1 arrives for (0 4 2 0), can the request be granted immediately and show
Page
all the calculations? 3 1 2 4 3 2 5 2 1 3 2 4

Q3. Answer the following questions.

Memory [4 + 6 = 10]

(a) A computer system has three processes P1 , P2 , and P3 . These processes belong to two groups named
GP1 and GP2 . ThePage faults
group weightage is 0.5 for both groups. The process P1 and P2 belongs to GP1 ,
Miss ratio
and P3 belong to GP2 . The base priority for P1 , P2 , and P3 is 30, 40, and 50, respectively. Assume
Hit ratio
that all the processes are processor bound and are ready to run. The priorities are calculated after
every second, and between two priority calculations, 60 clock ticks (interrupt) are generated. For
this[5system,
(c) points] using
The MINtheOptimal algorithm:
Fair share scheduling algorithm shows the tabular representation of the
process execution sequence for four seconds of time.
Page 3 1 2 4 3 2 5 2 1 3 2 4
(b) In a system there are three processes named P , Q and R. When the system starts, the process P
executes once thenMemory
process Q executes twice and after this process R executes twice. The process
R cannot execute until process Q has executed twice and process Q can not execute until process
P has executed once. PageOnce
faultsprocess P has executed it cannot execute again until the process Q and
Miss ratio
R have executed twice. The restriction mentioned above allows the process P , Q, and R to execute
in following manner Hit ratio
P QQRR P QQRR P QQRR
(d) [5 points] Working set of window size θ = 3:
Write the pseudo code for process P , Q and R using counting semaphore. Apart from semaphore
do not use any otherPageshared variable
3 1 for 2process
4 synchronization.
3 2 5 2 All1the three
3 2processes
4 access the
critical section in mutually exclusive manner.
Memory
Q4. Answer the following questions. [3 + 3 + 4 = 10]

(a) Suppose the CLOCK page-replacement algorithm is used to approximate the LRU algorithm. Cur-
(e) [5 points]
rently a systemSuppose thepage
has six CLOCK page-replacement
frames algorithm is used tobits
with RM (Reference/Modified) approximate
as shownthe LRU (i.e.,
below algorithm.
the
firstCurrently a system
and second has the
bits are six page framesand
reference with RM (Reference/Modified)
modified bits, respectively).bits as shown below (i.e., the first
and second bits are the reference and modified bits, respectively):

If the clock pointer is at the page frame as shown and a page fault occurs, after running the CLOCK
algorithm,
If the what are
clock pointer is atthe new
the RM
page bits?asWhich
frame shownpage
and frame
a pagewill
faultbeoccurs,
selectedafter
as arunning
victim? the
Is aCLOCK
page-out
required in this case? Why? Which page frame will be selected if a new page fault
algorithm, what are the new RM bits? Which page frame will be selected as a victim? Is a page-occurs immediately?
out required in this case? Why? Which page frame will be selected if a new page fault occurs
Answer: In the following, pages that cause a page fault are shown in boldface with ∗ . Note that pages in memory
immediately?
for LRU, MIN and Working Set must be shown in the stack algorithm convention.
(b) Consider a computer system executing a process of size 28KB in the main memory with the following
page reference strings 1, 4, 3, 0, 3, 6, 1, 0, 5, 2. The size of each page is 4KB. Compute the number
of page faults for the Optimal Page Replacement (OPT) algorithm for three frames.

2
(c) Suppose that a disk drive has 200 cylinders numbered 0 to 199. Consider a disk queue with requests for
I/O to blocks on cylinders 120, 65, 90, 35, 40, 150, 85, 19, 195, and 114, in that order. Assume that
the head is moving toward increasing the order of the cylinder numbers. Initially, the disk head is at
cylinder 44. Starting from the current head position, what is the total distance (in cylinders) that
the disk arm moves to satisfy all the pending requests for the C-SCAN disk-scheduling algorithm?

Q5. Answer the following questions. [3 + 3 + 4 = 10]

(a) Suppose a computer system with a 256 bytes main memory runs a process with four unequal size
segments. The process is loaded in the main memory using the following segment table.

Segment number Base Address (in decimal) Length (in bytes)

0 31 32
1 79 16
2 95 32
3 127 128

If the computer system uses the 9-bit addresses, what is the physical address corresponding to the
logical address 110011001?

(b) Assume that a computer system uses an inverted page table for memory management. The system
uses a 16-bit virtual address, and each virtual address is of the form ⟨process id, virtual page
number, offset⟩. The size of process id, virtual page number, and offset are 4 bits, 6 bits, and 6
bits, respectively. Assume that system uses the physical address of 9 bits. The page table of the
system s given as follows.

Index (3 bits) Process id (4 bits) Virtual page number (6 bits)

000 0000 000000
001 1001 000001
010 0010 000010
011 1011 000011
100 0100 000100
101 1101 000101
110 0110 000110
111 1111 000111

If the CPU generates the virtual address 1101000101111111, what is the corresponding physical
address?

(c) Suppose a two-level paging scheme with 64-bit logical address space is used by the OS to access the
memory. Assume that the page size is 4KB, and each entry in the page table consists of 4 bytes.
The outer page table size is 4GB, and the inner page table size is 4MB. How many bits are required
for the outer page table, inner page table, and page offset?