SIR SYED UNIVERSITY OF ENGINEERING AND

TECHNOLOGY
INTRODUCTION TO OPERATING SYSTEM
(SWE 204)

ASSIGNMENT # 3

Submitted by :
Muhammad Fahad Siddiqui (2019-SE-206)
Muhammad Ali Hamza (2019-SE-219)
Muhammad Moiz Bakaseer (2019-SE-221)
Shahzaib Ansari (2019-SE-249)

Submitted to :
Miss Falak Saleem
 ASSIGNMENT # 3
Question 1 (Solved by 2019-SE-249)

Suppose we have 64bit logical address with 8KB of page size and size of each entry in the page is 4 Bytes.
Calculate the following:
(i) Inner page size.
(ii) Outer page size.
(iii) Page offset

Answer.
 Question 2 (Solved by 2019-SE-249)

Given the following stream of page references by an application, calculate the number of page faults the
application would incur with the FIFO, LRU and Optimal page replacement algorithms. Assume that there
are 3 frames, and all are initially empty. Reference Stream: E D H B D E D A E B E D E B G.

Answer.
 Question 3 (Solved by 2019-SE-249)

(a) Consider the following data of a system has five processes (P0, P1, P2, P3 and P4) and four types
of resources (A, B, C and D). There are multiple resources of each type. Is the following state safe
or not? If it is, show how the processes can complete. If not, show how they can deadlock.

(b) Draw the resource-allocation graph when the sets Process, Resource, and Edges are:
P = {T1, T2, T3, T4} R = {A, B, C, D} E = {T1B, AT1, AT2, BT2, T3B, CT3, T2C, T4C, DT3
and DT4}
Assume there exists two instances of resource A and D one instance of resource B and C. As well,
assume resources A, B, C and D are non-preemptive and cannot be shared.
(i) Draw wait-for-graph with the help of resource allocation graph.
(ii) Could a deadlock exist in the system? Briefly explain.
Answer.

.
 Question 4 (Solved by 2019-SE-206)

The following pair of processes share a common set of variables: “counter”, “temp A” and “temp B”
Process A Process B
A1: tempA = counter+1; B1: tempB = counter+2;
A2: counter = tempA; B2: counter = tempB;

The variable “counter” initially has the value 10 before either process begins to execute.

(i) What difference values of “counter” are possible when both processes finished executing? Give
an order of execution of statements from process A and B that would yield each of the values you
give. For example, execution order A1, A2, B1, and B2 would yield the value 13.
(ii) Modify the above programs for processes A and B by adding appropriate signal and wait
operations on the binary semaphore “sync” such that the only possible final value of “counter” is
13. Indicate what should be the initial value of the semaphore “sync”.

Answer.
 Question 5 (Solved by 2019-SE-206)

This problem was originally based on the Senate bus at Wellesley College. Riders come to a bus stop and
wait for a bus. When the bus arrives, all the waiting riders invoke board Bus, but anyone who arrives while
the bus is boarding must wait for the next bus. The capacity of the bus is 50 people; if there are more than
50 people waiting, some will have to wait for the next bus. When all the waiting riders have boarded, the
bus can invoke depart. If the bus arrives when there are no riders, it should depart immediately. Write
synchronization code using Semaphore.

Answer.

Here are the variables I used in my solution: Bus problem hint

riders = 0
mutex = Semaphore (1)
multiplex = Semaphore (50)
bus = Semaphore (0)
allAboard = Semaphore (0)
mutex protects riders, which keeps track of how many riders are waiting; multiplex makes sure there
are no more than 50 riders in the boarding area. Riders wait on bus, which gets signaled when the bus
arrives. The bus waits on allAboard, which gets signaled by the last student to board.
Bus problem solution #1
Here is the code for the bus. Again, we are using the “Pass the baton” pattern. mutex .
wait ()
if riders > 0:
bus . signal () # and pass the mutex
allAboard . wait () # and get the mutex back
mutex . signal ()
depart ()
When the bus arrives, it gets mutex, which prevents late arrivals from entering the boarding area. If
there are no riders, it departs immediately. Otherwise, it signals bus and waits for the riders to board.
Here is the code for the riders:
multiplex . wait ()
mutex . wait ()
riders += 1
mutex . signal ()
bus . wait () # and get the mutex
multiplex . signal ()
boardBus () riders -= 1
if riders == 0:
allAboard . signal ()
else :
bus . signal () # and pass the mutex .
The multiplex controls the number of riders in the waiting area, although strictly speaking, a rider doesn’t
enter the waiting area until she increments riders. Riders wait on bus until the bus arrives. When a rider
wakes up, it is understood that she has the mutex. After boarding, each rider decrements riders. If there
are more riders waiting, the boarding rider signals bus and pass the mutex to the next rider. The last
rider signals al

Bus problem solution #2

Grant Hutchins came up with this solution, which uses fewer variables than the previous one, and
doesn’t involve passing around any mutexes. Here are the variables:
waiting = 0
mutex = new Semaphore (1)
bus = new Semaphore (0)
boarded = new Semaphore (0) .
waiting is the number of riders in the boarding area, which is protected by mutex. bus signals when
the bus has arrived; boarded signals that a rider has boarded. Here is the code for the bus
mutex . wait ()
n = min ( waiting , 50)
for i in range (n ):
bus . signal ()
boarded . wait ()
waiting = max ( waiting -50 , 0)
mutex . signal ()
depart ()

The bus gets the mutex and holds it throughout the boarding process. The loop signals each
rider in turn and waits for her to board. By controlling the number of signals, the bus prevents
more than 50 riders from boarding. When all the riders have boarded, the bus updates waiting,
which is an example of the “I’ll do it for you” pattern. The code for the riders uses two simple
patterns: a mutex and a rendezvous.
mutex . wait ()
waiting += 1
mutex . signal ()
bus . wait ()
board ()
boarded . signal ().

12
 Question 6 (Solved by 2019-SE-206)

A disk system has 250 cylinders, numbered 300 to 550. Assume that the read / write head is at
cylinder 400 and determine the order of head movement for each algorithm to satisfy the following
stream of requests. For comparison purposes, calculate the total head travel distance. They are
listed in the order received.
450, 510, 345, 410, 545, 330, 495, 395, 475, 380, 529, 251, 365
Discuss the following algorithms and briefly explain which algorithm is best. (i) LOOK, (ii) SSTF, (iii) C-
SCAN, (iv) FCFS.

Answer.

13
14
15
16
17
 Question 7 (Solved by 2019-SE-221)

Consider a file system that uses i-nodes to represent files. Disk blocks are 9-KB in size and a pointer
to a disk block requires 4 bytes. This file system has 12 direct disk blocks, plus single, double, and
triple indirect disk blocks. What is the maximum size of a file that can be stored in this file system?

Answer.

Given data:
Size of the disk block = 9 KB
Size required by the pointer to a disk block = 4 bytes
Now,
Size required by 12 direct disk blocks = 12 × 9
Size required by single disk block = 2048 × 9 KB
Size required by double disk block = 2048 × 2048 × 9 KB
size required by triple disk block = 2048 × 2048 × 2048 × 9 KB
Now,
the maximum size of the file that can be stored in this file system = 12 * 9 + 2048 *9 KB + 2048 * 2048
* 9 KB + 2048 * 2048* 2048 * 9 KB = 81 terabytes
Answer:
81 terabytes.

Question 8 (Solved by 2019-SE-219)

Please mark whether the following statements are true or false.

(i) One way of implementing semaphores on uni-processor machines is by using Peterson’s
algorithm.
(ii) A critical section is a segment of code that can be executed by more than one
process/thread at a time.
(iii) Hardware interrupts can be disabled both from user- and kernel-space.
(iv) Counting semaphores are the most primitive synchronization mechanisms.

Answer.

(i)
True

(ii)
False

(iii)
True

(iv)

18
 True

Question 9 (Solved by 2019-SE-219)

Briefly explain the following:

(i) Why rotational latency is usually not considered in disk scheduling? How would you modify
SSTF, SCAN, and C-SCAN to include latency optimization?
(ii) Why must the bit map for file allocation be kept on mass storage, rather than in main
memory?
(iii) Consider a system that supports the strategies of contiguous, linked, and indexed allocation.
What criteria should be used in deciding which strategy is best utilized for a particular file?
(iv) How file allocation table (FAT) works? Explain with the help of diagram.
(v) What is the difference between deadlock prevention and deadlock avoidance? What
category does Bankers algorithm fall in and why?

Answer.

(i)

Most disks don't export their motility position information to the host. even if they did, the time for
this information to achieve the scheduler would be subject to inexactness and also the time
consumed by the computer hardware is variable, that the motility position info would become
incorrect. Further, the disk requests are sometimes given in terms of logical block numbers, and also
the mapping between logical blocks and physical locations is incredibly complex.

(ii)

In case of system crash (memory failure) the free-space list wouldn't be lost because it would be if
the bit map had been stored in main memory.
(iii)

o Contiguous—if file is usually accessed sequentially, if file is relatively small.

o Linked—if file is large and usually accessed sequentially.
o Indexed—if file is large and usually accessed randomly.

(iv)

The file system uses associate index table keep on the device to identify chains of information
storage areas related to a file, the File Allocation Table (FAT). The FAT is statically allocated at the
time of information. The table could be a coupled list of entries for every cluster,a contiguous space
of disk storage.

19
 (v)

• Deadlock Prevention:
o Preventing deadlocks by constraining how requests for resources can be made in the
system and how they are handled (system design).
o The goal is to ensure that at least one of the necessary conditions for deadlock can
never hold.
• Deadlock Avoidance:

o The system dynamically considers every request and decides whether it is safe to
grant it at this point,
o The system requires additional apriori information regarding the overall potential use
of each resource for each process.
o Allows more concurrency.
Similar to the difference between a traffic light.

Banker's algorithm is a deadlock avoidance algorithm. it's named therefore as a result of

this algorithmic program is employed in banking systems to see whether or not a loan will
be granted or not. Consider there are n account holders in a bank and the sum of the
money in all of their accounts is S.

20