Disk Scheduling Algorithms

Let us assume a simple disk model:

The cost of a reading the data at track b is |b - h|, ignoring latency, waiting for the disk to rotate to the data, and acceleration of the disk head.

---

1) First-Come, First-Serve

Handles requests in a simple queue.

Assuming that the data is uniformly distributed, the average cost of random access for each h can be graphed as such:

Integrating the graph gives us the average cost of random access:

This is pretty expensive!

---

2) Shortest Seek Time First

Always schedules closest request to disk head.

• +Better thoroughput by minimal seeks.
• –May cause starvation of farther jobs if close requests keep getting scheduled.

---

Now we seek inspiration from elevators. After all, elevator operators have handled the same problem long before OS programmers...

3) Elevator Algorithm

Tries to keep going in the same direction until we run out of jobs in that direction.

• +More fair...
• –...However, requests for data on the ends may have to wait for the disk head to go to the other end then come back.

---

4) Circular Elevator Algorithm

Like the Elevator Algorithm, but it keeps going in the positive direction and immediately goes back to the lowest job when it reaches the end.

• +Completely fair and consistent — good for real-time applications.
• –Overhead of going to highest job, then back to lowest job.

---

Example

Assume that the disk head is currently at cylinder 100, and cylinders 101, 98, 200, 96 requested in that order.
Here's what the algorithms above will do, and why:

Step	FCFS	SSTF	Elevator	Circular Elevator
1	101 1st job	101 closest job	101 closest job	101 closest job
2	98 2nd job	98 closest job	200 same direction	200 positive direction
3	200 3rd job	96 closest job	98 closest job in other direction	96 lowest job
4	96 4th job	200 closest job	96 same direction	98 positive direction
Total Cost	210	110	204	206

---

Problem With The Above Algorithms

They can't see the future! Suppose we have two processes that read files starting at cylinders 100 and 200, respectively:

OS	Process 1	Process 2
Waiting for request	Request cylinder 100	Request cylinder 200
Go to cylinder 100, queued request for cylinder 200	Request cylinder 101	Waiting for OS
Go to cylinder 200, queued request for cylinder 101	Waiting for OS	Request cylinder 201
Go to cylinder 101, queued request for cylinder 201	Request cylinder 102	Waiting for OS
Go to cylinder 201, queued request for cylinder 102	Waiting for OS	Request cylinder 202

And so on...All of the algorithms above will go back and forth because they don't know that the processes will request more cylinders close by.

---

5) Anticipatory Scheduling

After fulfulling a request, wait (for ~0.1 ms) in case the process wants to request more accesses close by.

• +Solves the problem described above.
• –Like SSTF, this may cause starvation if one process keeps requesting accesses close by. For example, a media player continuously reads music/movie data.

We can easily solve the starvation problem by limiting the number of times we wait for a process.

---

Other File Systems

File systems don't have to be made from disks. They can be made from flash or from the network (LAN and cloud). However, they face similar problems of scheduling limited resources, whether it be seek time, IOPS, latency, bandwidth, etc.

File System Design

A file system is a data structure that lives on disk and provides and abstraction of a set of organized files.

---

1) Simple File System Created by Eggert in 1974 before he know any better.

Features:

• Fixed-length file table (directory) at the start of disk (and cached in RAM).
• Each entry held the name, sector-aligned offset, and size of the file.
• Files are contiguous on disk.
• Files are aligned to sectors so the file table entry only needs the sector offset rather than the byte offset.

• +Simple.
• +Fast sequential access, because the files are contiguous.
• –Must specify maximum numbers of files when creating the file system.
• –Must specify file size when creating file.
• –External fragmentation — free space gets scattered.
• –Internal fragmentation — free space not starting on sector boundary get overlooked.

---

2) FAT (File Allocation Table)

Features:

• Keeps track of file blocks.
• Files no longer need to be contiguous.

Super Block:

• Contains metadata of the file system.
• Fixed size.
• Version number of the file system.
• Size of the file system.
• Blocks in use.
• The block number of the root directory.

File Allocation Table:

• The File Allocation Table is a giant array of block numbers.
• Each entry in the FAT acts as a pointer.
• If the entry in FAT is "-1" then that block is free.
• If the entry in FAT is "0" then that block marks the blast block of the current file (EOF).
• If the entry in FAT is "N" any positive number, then we are in the middle of a file and the next block is N.
• Files are essentially represented as a linked list, except the pointer to the next block is stored in the FAT
• By placing the next field in the FAT, then file blocks can remain powers of two.

Directories in FAT:

• A directory in FAT is just a file that contains zero or more "directory entries"
• Each directory file resides on the data section of disk, and can be grown in the same way regular files are grown.

Pros and Cons:

• +Easy to grow files.
• +No external fragmentation.
• +No artificial limitation on the number of files.
• –Sequential reads are slow, due to the amount of seeking (seek in FAT for next block, then seek for block)
• This problem is partially solved by caching the FAT, and defragmenting (put the blocks in order) the disk.
• –lseek turns into an O(n) operation, this causes random access into a file to be slower.

---

3) UFS (Unix File System)

Features:

• UFS is based on "inodes", this is the biggest difference between UFS and FAT

inodes:

• The size of the inode table is set at filesystem creation.
• An inode table is an array of inode entries.
• Each inode entry is a fixed size.
• An inode entry contains metadata and an array of block numbers which point to the block for that file on disk.
• The last two blocks an an inode entry can be an indirect block and a double indirect block. This is for files that are larger than 10 blocks.
• An indirect block is a block that points to an array of block numbers, an indirect block points to two thousand block numbers (each block num is 4 bytes).
• A double indirect block is essentially a block that points to an array of indirect blocks
• The max size of a file in UFS can be: 80 KiB (only direct data blocks), 80Kib+16MiB (direct blocks + indirect block), or 80KiB+16MiB+32GiB (direct blocks + indirect block + double indirect block).
• The blocks in an inode entry are allowed to be "null", that is a file in UFS can have holes, writing to a hole allocates space.

Directories in UFS:

• Directories in UFS are extremely similar to their FAT counterpart.
• They are also arrays of directory entries.

Compared to FAT:

• External fragmentation ~ around the same as FAT.
• Internal fragmentation ~ similar to FAT, except for cases of files with holes, the worse case would be a file with an indirect block and double indirect block all pointing to holes except for 1 block pointing to data.

• +lseek is now O(1), no longer need to follow a chain of nexts, but may require up to 4 seeks due to indirect and double indirect blocks.

---

Made by Jeff Chien and Ze (Albert) Yuan.