Operating

Systems
Lecture 45
Syed Mansoor Sarwar
 Agenda for Today
 Review of the previous lecture
 Space Allocation Techniques
 Free Space Management
 Disk Structure and Scheduling
 Access time and disk bandwidth
 Disk scheduling algorithms (FCFS, SSTF,
Scan, C-Scan, Look, C-Look)
 Course Recap
 Future Directions
May 28, 2024 © Copyright Virtual University of P
akistan
Review of Lecture 44
 File Sharing and Protection
 Read, write, and execute permissions
 User, group, and others
 chmod, ls –l, ls –ld, umask, ls –i
 Per Process File Descriptor Table
 Space Allocation Techniques
 Contiguous, Linked, Index

May 28, 2024 © Copyright Virtual University of P

akistan
 Index Allocation
 Need index table
 Random access
 Linked scheme – Linked list of
index blocks

Directory
Entry … …
May 28, 2024 © Copyright Virtual University of P
akistan
…
 Index Allocation
 Two-level index table

File
Directory … Data
Entry Blocks

First
Level …
May 28, 2024 Index Virtual University of P
© Copyright
akistan
 UNIX Allocation

May 28, 2024 © Copyright Virtual University of P

akistan
 UNIX Allocation
 4 KB block
 4-byte disk pointers
 10 direct pointers to file blocks
 Maximum file size?
 Amount of space needed to
store pointers?
May 28, 2024 © Copyright Virtual University of P
akistan
File Allocation Table
(FAT)

May 28, 2024 © Copyright Virtual University of P

akistan
 Free-Space
Management
 Bit vector
0 1 2 n-1
…

0  block[i] is free

bit[i] =
1  block[i] is occupied

 Block number calculation

(number of bits per word) * (number of 0-
value words) +
offset
May 28, 2024 of first ©1Copyright
bit Virtual University of P
akistan
 Free-Space
Management
 Example for overhead of bit map
Block size = 4 KB = 212 bytes
Disk size = 40 GB = 40 * 230 bytes
Overhead = 40 * 230/212 = 40 * 218 bits
= 40 * 32 KB = 1280 KB
 Easy to get contiguous files
May 28, 2024 © Copyright Virtual University of P
akistan
 Free-Space
Management
 Linked list (free list)
 Cannot get contiguous space
easily
 Overhead (number of pointers
used to maintain free space)

May 28, 2024 © Copyright Virtual University of P

akistan
 Free-Space
Management

May 28, 2024 © Copyright Virtual University of P

akistan
 Free-Space
Management
 Grouping
 First (n-1) pointers to free blocks and
last pointer to another such block
 Counting
 An entry contain address of the first
free block and number of free
contiguous blocks that follow the first
block—good for contiguous allocation
May 28, 2024 © Copyright Virtual University of P
akistan
 I/O Operations
 Number of I/O operations
(inserting, deleting, and reading
a file block) needed for the
various allocation schemes
 Assumptions
 Directory, Bit-map, and index blocks
are in the main memory
 Worst-case and best-case scenarios
May 28, 2024 © Copyright Virtual University of P
akistan
 I/O Operations
 File size of 100 blocks
 Insert a block after the 50th block
 Read 50th block
 Insert 101st block
 Delete 50th block
 Assumptions
 Directory, Bit-map, and index blocks are in
the main memory
 Worst-case©akistan
May 28, 2024
and best-case scenarios
Copyright Virtual University of P
 Secondary Storage
Management
 Maintains the file system,
File Management System its directories, and keeps
track of free secondary
storage space

 Provides device drivers to

I/O System control transfer of data
between memory and
secondary storage devices

 Optimizes the completion

Secondary Storage of I/O tasks by employing
Management
May 28, 2024 System algorithms to facilitate
© Copyright Virtual University of P
akistan efficient disk usage
 Disk Structure
 Disk drives are addressed as large 1-
dimensional arrays of logical blocks,
blocks the
smallest units of transfer (usually 512 bytes).
 The 1-dimensional array of logical blocks is
mapped into the sectors of the disk
sequentially.
 Block 0 is the first sector of the first track on the
outermost cylinder.
 Mapping proceeds in order through that track,
then through the rest of the tracks in that
cylinder, and then through the rest of the
May 28, cylinders
2024 from outermost
© Copyright to ofinnermost.
Virtual University P
akistan
 Disk Scheduling
 Disk Access Time has two major
components
 Seek time is the time for the disk
heads to the desired cylinder (track)
 Rotational latency is the time
waiting for the disk to rotate the
desired sector under the disk head
 Want to minimize seek time
May 28, 2024 © Copyright Virtual University of P
akistan
 Disk Scheduling
 Disk bandwidth is the total
number of bytes transferred,
divided by the total time between
the first request for service and
the completion of the last
transfer
 We can improve access time and
bandwidth by scheduling the
servicing of disk I/O request in a
good order.
May 28, 2024 © Copyright Virtual University of P
akistan
 Disk Scheduling
 Several algorithms exist to
schedule the servicing of disk I/O
requests. These include:
 First-Come-First-Serve (FCFS)
 Shortest Seek Time First (SSTF)
 Scan
 Circular Scan (C-Scan)
 Look
 C-Look
May 28, 2024 © Copyright Virtual University of P
akistan
 FCFS

Illustration shows total head

May 28, 2024 © Copyright Virtual University of P
movement of 640 cylinders.
akistan
 Shortest Seek Time
First (SSTF)
 Selects the request with the minimum
seek time from the current head
position.
 SSTF scheduling is a form of SJF
scheduling; may cause starvation of
some requests.
 Illustration shows total head movement
of 236 cylinders.
May 28, 2024 © Copyright Virtual University of P
akistan
 SSTF

May 28, 2024 © Copyright Virtual University of P

akistan
 SCAN
 The disk arm starts at one end of
the disk, and moves toward the
other end, servicing requests until it
gets to the other end of the disk,
where the head movement is
reversed and servicing continues.
Also known as the elevator
algorithm
 Total head movement is 208
cylinders
May 28, 2024 © Copyright Virtual University of P
akistan
 SCAN

May 28, 2024 © Copyright Virtual University of P

akistan
 LOOK
 Version of SCAN
 Arm only goes as far as the last
request in each direction, then
reverses direction immediately,
serving requests while going in the
other direction.
 That is, it looks for a request
before continuing to move in a
given direction.
May 28, 2024 © Copyright Virtual University of P
akistan
 LOOK

May 28, 2024 © Copyright Virtual University of P

akistan
 Recap of Lecture
 Space Allocation Techniques
 Free Space Management
 Disk Structure and Scheduling
 Access time and disk bandwidth
 Disk scheduling algorithms
(FCFS, SSTF, Scan, C-Scan,
Look, C-Look)
May 28, 2024 © Copyright Virtual University of P
akistan
 Recap of Course
 OS services and structures
 Processes and threads
 Process scheduling
 Concurrent processes
 Deadlocks in computer systems
 Memory management
 Virtual memory
 File system interface
 File system implementation
 Secondary
May 28, 2024 storage management
© Copyright Virtual
akistan
University of P
 Future Directions
 Advanced Operating Systems
 System Programming
 Linux Kernel Programming

May 28, 2024 © Copyright Virtual University of P

akistan
 Operating
Systems
Lecture 45
Syed Mansoor Sarwar

May 28, 2024 © Copyright Virtual University of P

akistan