Accessing memory: want from are here
cost of accessing block b is |b-h| |--------b---------h---------|
only taking track into account: seek is longer than latency (sector pos)
ignores acceleration (overestimates)
First Come First Serve Algorithm (FCFS)
services requests in order occur
If accesses are random (h and b are random)
then avg cost = (integral picture) (int pic 2)
FCFS is fair, but it can be very costly
for example:
process 1: read blocks: 1000, 1001, 1002, 1003
process 2: read blocks: 91631,28193,1512,69317
(zig zag pic)
Shortest Seek Time First (SSTF)
will increase performance over FCFS
Algorithm: always schedule the request closest to h
+ better throughput by choosing minimal seek time
+ guaranteed better performance
- starvation is possible
Elevator Metaphor
This type of scheduling problem is like elevators
With this SSTF, the top or bottom floor could be skipped.
Elevator algorithm:
Schedule the request that is closest to h “in the direction you are currently moving.”
Ie either increasing or decreasing.
- this is a bit ufair to the edges (top and bottom wait longer on average)
Circular Elevator algorithm:
Always go in positive direction (with the top looping back to the bottom).
(when at top, seek to lowest request, not absolute bottom)
+ has more fairness than regular elevator algorithm
- losses a bit of performance
- if only 2 processes, only 2 reads are scheduled, which is very inefficient
Anticipatory Scheduling
Fixes the inefficiency of Circular Elevator algorithm
Uses an oracle to speculate a process' next moves.
It speculates what a process will do, and then delays (DALLY).
For example, it might wait for 0.1 ms after each process finishes
Starvation is still an issue, but it can be easily overcome with a timer or a counter.
Modern Metrics
Everything previously mentioned primarily applies to single HD drives
(where seek time matters most).
Nowadays, file systems can be built from one of any combination of the following:
disks
flash memory
network drives (local and cloud).
Similar scheduling issues still apply, but the metrics used are different:
disk: seek time
flash (seek = 0): IOs per second
network: latency or throughput
File System Design and Organization:
A File System is a data structure that lives on a disk
It provides the abstraction of a set of organized files.
Example simple file system: (1974 Eggert's design before he knew any better)
|
Directory |
File1 |
File2 |
Unused |
File3 |
Unused |
File4 |
File5 |
Unused |
The directory was a file table in a fixed size region.
It was cached in RAM while the system was active.
Directory:
|
File entry 1 |
File entry 2 |
File entry 3 |
File entry4 |
Example File Entry:
|
Name |
Command.c |
|
Byte offset |
1096320 |
|
Size (in bytes) |
3369 |
Each file started at a sector boundary, so they had sector offsets (2916) instead of byte offsets.
This design is approximately equal to the RT-11 file system
-when you create a file, you must specify its size (very very bad)
-external fragmentation: free space is known, but may be scattered
-internal fragmentation: on average (- size ) % 512 bytes are wasted in each file.
(for example, a 1 byte file would waste an entire sector).
+ very simple
+ sequential access is very fast (this is a big deal for some program types, ie real time apps)
To find free space, anything not in the directory is fair game.
- You can't make a big file if there isn't enough continuous space.
- You must know the maximum number of files to be contained when you create the system (to specify the directory size)
The FAT (File Allocation Table) filesystem attempts to solve the problem of fragmentation
|
Boot Sector |
Super Block |
FAT |
Data |
|
Boot Sector
|
Super Block
|
Data
|
The FAT conatains an array of entries that each correspond to a data block
Each entry points to the next entry in the file or a marker for end of file cluster
0 denotes free space
The FAT is essentially a linked list with the pointers stored in a different location
Example:
FAT
|
4 |
0 |
7 |
0 |
2 |
0 |
0 |
EOC |
0 |
0 |
Corresponding Data Blocks
|
F |
b |
L |
l |
I |
h |
bl |
E |
a |
h |
Reading the file starting at block 0 would yield “FILE”
A FAT directory is a file with directory entries
These entries contain:
metadata about the Size, Name, etc. of the file
A pointer to the first entry for the file in the FAT
|
Advantages
|
Disadvantages
|
Attempts to maintain benefits of FAT while solving the random access problem
The structure is very similar to FAT, but uses relies on index-nodes (inodes) rather that a FAT
|
Boot Sector |
Super Block |
Node Table |
Data |
|
Boot Sector
|
Super Block
|
Data
|
Fixed size → limits the size of the filesystem
Each entry contains
Metadata (size, name, etc.)
An array of block #'s
80kB file size - First few blocks point to data
16Mb file size - next entry points to an array of block #'s
32 GB file size - next entry points to an array of pointers to arrays of block #'s
Files can contain holes
The entry is 0
Writing to the hole allocates space
A UFS directory is a file containing an array of directory entries, just as in a FAT filesystem
|
Advantages
|
Disadvantages
|