CS111 Lecture 11 Scribe Notes (Fall 13)

By: Dongkeun Lee

Some I/O Performance Metrics

utilization: what % of the system is doing useful work
Throughput: request done per second
Latency: time taken from request to response

Hypothetical Router Hash

X86 Cycle: 1ns
Programmed I/O: 1000 cycles
Send a command to device: 5 Programmed I/O
Device latency: 50 microseconds
Computation: 5000 cycles

Simplest

Method	Latency (in microsecond)	Throughput (in KB/s)	CPU Utilization (%)
Polling: 1 Byte at a time	100	10	5
Batching	1000	21	10.5
Batching + Interrupt (Contect Switching)	106	18	8.9
DMA+Interrupt	61	91	45
DMA+Polling	56	162	84

**DMA: Direct Memory Access: Memory moves from Device Controller to RAM directly, not through CPU

File System Design

Eggert File System:

Table of Files

DATA

...

One sector is consisted of useful data and leftover waste data
This is because one sector cannot be divided into smaller pieces, so if file takes up only a part of sector, the file system considers as if the file took up entire sector.
This is called, "Internal Fragmentation" and this is unavoiable in most cases

Table of Files:

11 Bytes	4 Bytes	10 Bytes
Sector Number	Size	Name

Advantage

Simple - Only requires table to index and actual files
Low Index Overhead - Does not take up much index space.
Fast Sequential Access - File is stored sequentially, so there is no need for file system to look up where next sector is
Fast Random Access
Predictable Time - Time is predictable as file is stored sequentially

Disadvantage

Internal Fragmentation - A sector cannot be divided into multiple smaller pieces
External Fragmentation - File can only be stored sequentially, so there might be case where enough storage for file exists, but file system is not able to save the file, because there is not enough sequential sectors
Directory Not Sorted - File system does not have any concept of directory
File Growth Not Easy - File growth would mean that it has too find a set of sequential sectors that are bigger than current set. This means the entire file has to be moved into different location, instead of just adding few more sectors

File Allocation Table (FAT) File System

Developed in Late 1970s

Boot Sector

Super Block

FAT

DATA

...

Sector vs Block

Block is a batch of sector, which is around the size of 4KiB, when sector is 512 bytes.
Basically block is used at software level, while sector is used at hardware level.

Boot Sector:

It contains bootstrapping programs which the Master Boot Record transfers to CPU
This allows CPU to know which program to boot up, when the computer is turned on.

Super Block Contains:

File System Version
Size of the File System
Number of Sectors Used
Root Directory Sector Location
Other Metadata

File Allocation Table

Current Sector	Next Sector
#1	27
#2	67
...	...

Next Sector should have 0 if current sector is End of File or -1 if current sector is free
In FAT 16, sector number was 16 bits allowing 2^16 * 512 bytes = 2^25 bytes maximum
So basically file allocation table allows data to be stored in non-continuous sectors. This eliminates external fragmentation.
Also FAT size will be determined by disk size as different disk size consists of different sector number

Directory in FAT

Directory is a file that maps file names into files

Name (11 Bytes)

Size of File(4 Bytes)

Type (At least 1 bit)

Permission

Name section can have name of the file or another directory to allow nested directory.

How FAT works in basic

Super block has location of where root directory is stored in the disk
With root directory information, one can find file by searching through the directory
Directory knows which file is associated with which sector, so file system would direct CPU to the corresponding sector number
If newly read sector is directory, repeat above procedures and if it is a file, then read the sectors using FAT, since it stores the order in which sectors should be read

Problem of FAT System

FAT file would easily rename a file if it happens in a same directory.
However, moving a file to different directory will be burdensome as moving a file and deleting a file is two different system calls.
Therefore there is no gurantee that they will happen atomically.

Berkeley Fast File System (FFS) (~1975)

This file system is used by many Unix-based system
This file system adds another level of indirection in order to avoid the problem of FAT

Boot Sector

Super Block

Block Bitmap

Inode Table

DATA

...

Block Bitmap

Bitmap that tells the system which block is empty using 1 bit per block

Inode Table

Table has inodes ndexed by inode number

Each Inode consists of

Link Count

Owner

Group

Permission

...

Block Number

...

Block Number of List of Blocks

Each inode has fixed size
One of the differences between FAT and FFS is that inode doesn't contain file name, but FAT has a file name to every data.
Link count stores the number of links pointing to the inode
Unlike FAT system, FFS saves all the block numbers that file uses in a inode
If space to save block number runs out, it saves block number of the list that holds a set of blocks (Linked List)
This allows more efficient method of saving sparse data, which means faster lseek

CS111 Lecture 11 Scribe Notes (Fall 13)

By: Dongkeun Lee

Some I/O Performance Metrics

Hypothetical Router Hash

Simplest

File System Design

Eggert File System:

Table of Files:

Advantage

Disadvantage

File Allocation Table (FAT) File System

Sector vs Block

Boot Sector:

Super Block Contains:

File Allocation Table

Directory in FAT

How FAT works in basic

Problem of FAT System

Berkeley Fast File System (FFS) (~1975)

Block Bitmap

Inode Table

Each Inode consists of

Directory

End of Lecture 11