TUTORIAL

1. Disk Scheduling
There are many Disk Scheduling Algorithms but before discussing them let’s have a
quick look at some of the important terms:

Seek Time: Seek time is the time taken to locate the disk arm to a specified track where
the data is to be read or write. So, the disk scheduling algorithm that gives minimum
average seek time is better.
Rotational Latency: Rotational Latency is the time taken by the desired sector of disk
to rotate into a position so that it can access the read/write heads. So the disk scheduling
algorithm that gives minimum rotational latency is better.
Transfer Time: Transfer time is the time to transfer the data. It depends on the rotating
speed of the disk and number of bytes to be transferred.
Disk Access Time:
Disk Access Time = Seek Time + Rotational Latency + Transfer Time
Total Seek Time = Total head Movement * Seek Time
Disk Response Time: Response Time is the average of time spent by a request waiting
to perform its I/O operation. Average Response time is the response time of all requests.
Variance Response Time is measure of how individual request are serviced with respect
to average response time. So, the disk scheduling algorithm that gives minimum
variance response time is better.

Example:
Consider an imaginary disk with 51 cylinders. A request comes in to read a block on
cylinder 11. While the seek to cylinder 11 is in progress, new requests come in for
cylinders 1, 36, 16, 34, 9, and 12, in that order. 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 each of the following disk scheduling Algorithms?
i. FCSC (First come first serve)
ii. SSTF(Shorted seek time first)
iii. SCAN
iv. C-SCAN
v. LOOK
vi. C-LOOK
Answers: i. FCFS
In FCFS, the requests are addressed in the order they arrive in the disk queue.
Disk movement will be 11, 1, 36, 16, 34, 9and 12 as first come first served.
Total cylinder movement:
(11-1)+ (36-1)+ (36-16) + (34-16)+(34-9)+(9-12) = 111

ii. SSTF (Shortest seek time first)

Requests having shortest seek time are executed first. So, the seek time of every
request is calculated in advance in the queue and then they are scheduled according
to their calculated seek time.
As a result, the request near the disk arm will get executed first. SSTF is certainly an
improvement over FCFS as it decreases the average response time and increases the
throughput of system.

Starting head position is 11, closest to 11 is12, closest to 12 is 9, and so on.

As per SSTF request will be satisfied in order 11, 12, 9, 16, 1,34, 36.
Total cylinder movement:
(12-11) + (12-9) + (16-9) + (16-1)+ (34-1) + (36-34) = 61

iii. SCAN
In SCAN algorithm the disk arm moves in a particular direction and services the
requests coming in its path and after reaching the end of the disk, it reverses its
direction and again services the request arriving in its path. So, this algorithm works
as an elevator and is hence also known as an elevator algorithm. As a result, the
requests at the midrange are serviced more and those arriving behind the disk arm
will have to wait.
From the current position disk arm starts in up direction and moves towards the end,
serving all the pending requests until end.
At that end arm direction is reversed (down) and moves towards the other end serving
the pending requests on the way.
As per SCAN request will be satisfied in order: 11, 12, 16, 34,36, 50, 9, 1
Total cylinder movement:
(12-11) + (16-12) + (34-16) +(36-34) +(50-36) + (50-9) + (9-1) = 88

iv. C-SCAN
In CSCAN algorithm in which the disk arm instead of reversing its direction goes to
the other end of the disk and starts servicing the requests from there. So, the disk arm
moves in a circular fashion and this algorithm is also similar to SCAN algorithm and
hence it is known as C-SCAN (Circular SCAN).

From the current position disk arm starts in up direction and moves towards the end,
serving request until end.
At the end the arm direction is reversed (down), and arm directly goes to other end and
again continues moving in upward direction.
As per SCAN request will be satisfied in order: 11, 12, 16, 34,36, 50, 0, 1,9
Total cylinder movement:
(12-11) + (16-12) + (34-16) +(36-34) +(50-36) + (50-0) + (1-0) +(9-1) = 98

v. LOOK
It is similar to the SCAN disk scheduling algorithm except for the difference that the
disk arm in spite of going to the end of the disk goes only to the last request to be
serviced in front of the head and then reverses its direction from there only. Thus, it
prevents the extra delay which occurred due to unnecessary traversal to the end of the
disk.
Keep moving in the same direction until there are no more outstanding requests pending
in that direction, then algorithm switches the direction.
As per LOOK request will be satisfied in order 11, 12, 16, 34,
36, 9, 1.
Total cylinder movement: (12-11) + (16-12) + (34-16) + (36-34) +
(36-9) + (9-1) = 60

vi. CLOOK

Total cylinder movement:

(12-11) + (16-12) + (34-16) + (36-34) +(36-1) +(9-1)=68

2. Page Replacement Algorithms

i. First In First Out (FIFO): This is the simplest page replacement algorithm. In
this algorithm, the operating system keeps track of all pages in the memory in a
queue, the oldest page is in the front of the queue. When a page needs to be
replaced page in the front of the queue is selected for removal.
Example: Consider page reference string 1, 3, 0, 3, 5, 6, 3 with 3 page frames.
Find the number of page faults.
Initially, all slots are empty, so when 1, 3, 0 came they are allocated to the empty slots
—> 3 Page Faults.
when 3 comes, it is already in memory so —> 0 Page Faults. Then 5 comes, it is not
available in memory, so it replaces the oldest page slot i.e 1. —>1 Page Fault. 6 comes,
it is also not available in memory, so it replaces the oldest page slot i.e 3 —>1 Page
Fault. Finally, when 3 come it is not available, so it replaces 0 1 page fault.

ii. Optimal Page replacement: In this algorithm, pages are replaced which would
not be used for the longest duration of time in the future.
Example-: Consider the page references 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with
4-page frame. Find number of page fault.

Initially, all slots are empty, so when 7 0 1 2 are allocated to the empty slots —> 4 Page
faults.
0 is already there so —> 0 Page fault. when 3 came it will take the place of 7 because
it is not used for the longest duration of time in the future.—>1 Page fault. 0 is already
there so —> 0 Page fault. 4 will takes place of 1 —> 1 Page Fault.

Now for the further page reference string —> 0 Page fault because they are already
available in the memory.

iii. Least Recently Used: In this algorithm, page will be replaced which is least
recently used.
Example-: Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2,
3 with 4 page frames. Find number of page faults.
Initially, all slots are empty, so when 7 0 1 2 are allocated to the empty slots —> 4 Page
faults
0 is already their so —> 0 Page fault. when 3 came it will take the place of 7 because it
is least recently used —>1 Page fault
0 is already in memory so —> 0 Page fault.
4 will takes place of 1 —> 1 Page Fault
Now for the further page reference string —> 0 Page fault because they are already
available in the memory.

3. A computer uses 46–bit virtual address, 32–bit physical address, and a three–level
paged page table organization. The page table base register stores the base address of
the first–level table (T1), which occupies exactly one page. Each entry of T1 stores
the base address of a page of the second–level table (T2). Each entry of T2 stores the
base address of a page of the third–level table (T3). Each entry of T3 stores a page
table entry (PTE). The PTE is 32 bits in size. The processor used in the computer has
a 1 MB 16 way set associative virtually indexed physically tagged cache. The cache
block size is 64 bytes. What is the size of a page in KB in this computer?
Answer: Let the page size is of \'x\' bits
Size of T1 = 2 ^ x bytes
(This is because T1 occupies exactly one page)
Now, number of entries in T1 = (2^x) / 4
(This is because each page table entry is 32 bits or 4 bytes in size)

Number of entries in T1 = Number of second level page tables

(Because each I-level page table entry stores the base address of page of II-level page
table)

Total size of second level page tables = ((2^x) / 4) * (2^x)

Similarly, number of entries in II-level page tables = Number of III level page tables
= ((2^x) / 4) * ((2^x) / 4)

Total size of third level page tables = ((2^x) / 4) * ((2^x) / 4) * (2^x)

Similarly, total number of entries (pages) in all III-level page tables = ((2^x) / 4) *
((2^x) / 4) * ((2^x) / 4)
= 2^(3x - 6)

Size of virtual memory = 2^46

Number of pages in virtual memory = (2^46) / (2^x) = 2^(46 - x)

Total number the pages in the III-level page tables = Number of pages in virtual
memory

2^(3x - 6) = 2^(46 - x)
3x - 6 = 46 - x
4x = 52
x = 13

That means, page size is of 13 bits

or Page size = 2^13 bytes = 8 KB

4. A bit-map can be used to keep track of which blocks are free in a file-system’s partition
on disk. Assuming, 1 KB block size and a disk size of 40 GB, what is the size of the bit
map
Answer:
Disk Size = 40 GB
Block Size: 1 KB
Number od blocks = 40*2^30/ 8*2^10 = 5 MB

5. A CPU generates 64 bits virtual address. Page size is of 8 KB. The processor has a
Translation Lookaside Buffer (TLB) which can hold a total of 256 page table entries
and is 4-way set associative. What is the minimum size of TLB tag?
Answer:
No. of sets = 256/4 = 64 = 2^6
No of bits used to represent sets: 6
Tag bits: 51-6= 45 bits

6. Consider a computer system with 34 bit logical address and 30 bit physical address. If
the page size is 4KB then the number of bits required to represent number of entries is
an inverted page table is
Answer:
Physical memory size = 1 GB
No. of entries in inverted page table = Physical Address/page size
2^30/2^12=2^18
No of bits required= 18

7. Consider the organization of a UNIX file as represented by the inode in which there are
12 direct block pointers, a singly, doubly, and triply indirect pointer in each inode.
Assume that the system block size and the disk sector size are both 8 KB. It is given
that the disk block pointer is 32 bits, if no information other than that the file inode is
already in main memory (file is present only in the single indirect), then the disk
accesses are required to access the byte in position 13,423,956 is
Answer:
Disk block address in a disk block = 8*1024 B/4 B
The 12 direct pointer cover= 12*8 KB=96KB, means it cannot fit into direct
The singly indirect pointer covers= 96 KB+ 2048*8 KB= 16 MB
So the address is in a block referenced by the singly indirect pointer.
So, this means we will need 2 disk access, 1 for the indirect block and second for the
block containing the data.

8. Consider the page reference string:

1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6 with number of frames be 4.The
number of page faults when using FIFO technique be x, Optimal technique be y, LRU
technique be z. Find the value of x, y and z.
Answer:
x= 14, y=10 and z=8

9. A translational look aside buffer is a hardware device used for speeding up the
conversation from virtual address to physical address. Consider a memory management
unit where a memory reference takes 500nanoseconds; TLB (Translation Look aside
Buffer) reference takes 40 nanoseconds; and the hit-rate achieved with the use of TLB
is 80%. The difference of Effective Access Time between TLB technique and pure
paging with no TLB is ?
Answer:
EAT with TLB = x(TLB+ Tm) + (1- x)(TLB+ 2 Tm)
= 0.8(40 +500) +0.2(40+2*500)
= 640ns
EAT using pure paging = 2* Tm =2*500 = 1000ns
Now their difference = 1000-640 =360ns

10. Consider a disk has 200 cylinders, numbered from 0 to 199. At some time the disk arm
is at cylinder 100, and moving towards right direction. There is a queue of disk access
requests for cylinders 30, 85, 110,100, 105, 126, 135, 55 and 195. What will be the
distance traversed by the R/W head when CSCAN algorithm is used _
Answer:
Total distance traversed by R/W head = (105-100) + (110-105) + (126-110) + (135-126)
+ (195-135) + (199-195) + (199-0) + (30-0) + (55-30) + (85-55)
=5+5+16+9+60+4+199+30+25+30
=383
11. Consider a computer system having 30 physical frames, numbered from 1 to 30 which
are initially empty. Now, a program accesses the page numbered (1, 2 ..... 80, 80, 79,
..... 2, 1). The number of page faults generated by least recently used page replacement
policy .
Answer:
Initially there is compulsory miss from page number 1 to 30, from 31 to till 80 all pages
are replaced . Total 80 page fault.
On second access of 80 there is hit from 80 to 51. After 50 to 1 there are total 50 page
fault again
So Total page fault = 80+ 50 =130

12. A system uses FIFO policy for page replacement. It has 5 page frames with no pages
loaded to begin with. The system first accesses 200 distinct pages in some order and
then accesses the same 200 pages but now in the reverse order. How many page faults
will occur?
Answer: - During the first pass, the system accesses 200 distinct pages. As each page
is accessed for the first time, it is loaded into a page frame. When all 5 page frames are
full, the system must evict one of the pages to make room for the next page. Since the
system uses the FIFO policy, the page that was loaded first is evicted. Thus, for the first
5 page accesses, there are no page faults. For each subsequent access, the system checks
if the requested page is already in a page frame. If it is, there is no page fault. Otherwise,
the page must be loaded into a page frame, replacing the page that was loaded first.
During the second pass, the system accesses the same 200 pages but in reverse order.
Since all the pages are already in memory, there are no page faults during the first 5
accesses. For each subsequent access, the system evicts the page that was loaded last
during the first pass and replaces it with the requested page.
Therefore, the total number of page faults is 200 + 195 = 395.

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

14. We have a disk drive with 3000 cylinders, which are numbered 0 to 2999. The drive is
currently serving a request at cylinder 93, and the previous request was at cylinder 125.
The queue of pending requests, in FIFO order, is: 45, 1950, 912, 1090, 130, 10, 2250,
130 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 each of the following disk
scheduling algorithms?
i. FCFS
ii. SSTF
iii. LOOK
iv. SCAN
Which algorithm causes the disk head to travel the smallest number of cylinders?
Answer:
i. FCFS (First-Come-First-Serve):
The total distance can be calculated by summing the absolute differences
between consecutive cylinder requests. Starting from cylinder 93:
93 → 45 = 48
45 → 1950 = 1905
1950 → 912 = 1038
912 → 1090 = 178
1090 → 130 = 960
130 → 10 = 120
10 → 2250 = 2240
2250 → 130 = 2120
Total distance for FCFS: 48 + 1905 + 1038 + 178 + 960 + 120 + 2240 + 2120 =
7,609 cylinders.

ii. SSTF (Shortest Seek Time First):

For SSTF, we choose the nearest cylinder from the current position at each step.
Starting from cylinder 93:
93 → 130 = 37
130 → 125 = 5
125 → 1090 = 965
1090 → 912 = 178
912 → 130 = 782
130 → 45 = 85
45 → 10 = 35
10 → 1950 = 1940
1950 → 2250 = 300
2250 → 130 = 2120
Total distance for SSTF: 37 + 5 + 965 + 178 + 782 + 85 + 35 + 1940 + 300 +
2120 = 6,457 cylinders

iii. SCAN:
SCAN moves the head from one end of the disk to the other and serves requests
along the way. In this case, we assume the head initially moves towards the
outermost cylinder.
Total distance for SCAN:
From 93 to 2999 (outermost cylinder) = 2906
2999 to 2250 = 749
2250 to 1950 = 300
1950 to 130 = 1820
130 to 125 = 5
125 to 10 = 115
10 to 45 = 35
Total distance for SCAN: 2906 + 749 + 300 + 1820 + 5 + 115 + 35 =
6,930cylinders

iv. LOOK:
LOOK is similar to SCAN, but it does not move the head to the opposite end of
the disk if there are no pending requests in that direction. In this case, we assume
the head initially moves towards the outermost cylinder.
Total distance for LOOK:
From 93 to 2999 (outermost cylinder) = 2906
2999 to 2250 = 749
2250 to 1950 = 300
1950 to 130 = 1820
130 to 125 = 5
125 to 10 = 115
10 to 45 = 35

Total distance for LOOK: 2906 + 749 + 300 + 1820 + 5 + 115 + 35 = 6,930
cylinders (same as SCAN)
After reviewing the results for problem 1, the algorithm that causes the disk
head to travel the smallest number of cylinders is SSTF (Shortest Seek Time
First) scheduling. SSTF has a total distance of 6,457 cylinders, which is the
lowest among the given disk scheduling algorithms.

15. Explore the underlying factors that contribute to the tendency of SSTF scheduling to
give preference to cylinders located in the middle, while comparatively neglecting those
positioned at the innermost and outermost regions.
Answer: The center of the disk is the location having the smallest average distance to
all other tracks. Thus, after servicing the first request, the algorithm would be more
likely to be closer to the center track than to any other particular track, and hence would
more often go there first. Once at a particular track, SSTF tends to keep the head near
this track; thus, this scheduling strategy would compound the initial tendency to go to
the center.

16. Consider a system with multiple concurrent processes operating under a modern OS
that employs virtual addresses and demand paging. Empirical observations have
revealed the following memory access times within the system: t1 when the logical
memory address is present in the TLB cache, t2 when the address is not found in the
TLB but does not result in a page fault, and t3 when the address triggers a page fault.
These access times include all associated overhead, such as page fault handling and
logical-to-physical address translation. On average, it has been determined that 10% of
logical address accesses lead to a page fault. Of the remaining virtual address accesses,
approximately two-thirds can be resolved using the TLB cache, while one-third
necessitates traversing the page tables. Utilizing the provided information, calculate the
average expected memory access time in terms of t1, t2, and t3.
Answer: 0.6*t1 + 0.3*t2 + 0.1*t3

17. A file system has a block size of 4KB and an inode size of 256 bytes. If each inode can
point to a maximum of 12 direct blocks, calculate the maximum file size that can be
supported by this file system.
Answer: Block size = 4KB = 4 * 1024 bytes
Number of direct blocks per inode = 12
Maximum file size = block size * number of direct blocks per inode
Maximum file size = 4 * 1024 bytes * 12 = 48,576 bytes

18. Consider a process with 4 physical pages numbered 0–3. The process accesses pages in
the following sequence: 0, 1, 0, 2, 3, 3, 0, 2. Assume that the RAM can hold only 3 out
of these 4 pages, is initially empty, and there is no other process executing on the
system. Assuming the demand paging system is using an LRU replacement policy, how
many page faults do the 8 page accesses above generate? Indicate the accesses which
cause the faults.
Answer: 0 (M), 1 (M), 0(H), 2 (M), 3 (M), 3(H), 0(H), 2(H) = 4 misses

19. A file system has a total disk space of 1TB and a block size of 8KB. If the file system
uses 4 bytes to store metadata per block, calculate the maximum number of blocks that
can be allocated for file data.
Answer: Disk space = 1TB = 1 * 1024 * 1024 * 1024 bytes
Block size = 8KB = 8 * 1024 bytes
Metadata size per block = 4 bytes
Maximum number of blocks for file data = (disk space / block size) - (disk space / block
size) * (metadata size per block / block size)
Maximum number of blocks for file data = (1 * 1024 * 1024 * 1024 bytes / 8 * 1024
bytes) - (1 * 1024 * 1024 * 1024 bytes / 8 * 1024 bytes) * (4 bytes / 8 * 1024 bytes)
Maximum number of blocks for file data = 128,000 blocks

20. A process requires 64KB of memory. The system uses a fixed-size partitioning memory
allocation scheme with partition sizes of 8KB. How many partitions are required to
accommodate the process?
Answer:

Process size is 64KB, which is equal to 2^16 bytes.

Partition size is 8KB, which is equal to 2^13 bytes.
Number of partitions = Process size / Partition size
Number of partitions = (2^16 bytes) / (2^13 bytes)
Number of partitions = 2^(16-13)
Number of partitions = 2^3
Number of partitions = 8 partitions

Therefore, 8 partitions are required to accommodate the process.

21. Examine the effectiveness of C-SCAN and SCAN scheduling algorithms under a
uniform distribution of requests, taking into account average response time (the
duration between request arrival and completion of service), response time variability,
and effective bandwidth. Assess how performance is influenced by the relative
magnitudes of seek time and rotational latency.
Answer: The main difference would be that C-SCAN loses time traveling from the
inside edge to the outside edge of the disk. Other, quite minor differences in throughput
could come from the fact that SCAN examines the edge tracks once for two
examinations of the inside tracks and the time intervals between successive visits of a
given track tend to have a greater variance for SCAN than for C-SCAN.