CS111 Lecture 11
By: Kenny Chow
Table of Contents:
1) Utilization (we want 100%): What percent of system is doing useful work
2) Throughput: requests/second
3) Latency: delay between request and response
These are the specifications for the router:
What we are trying to do:
We are trying to efficiently use CPU time while waiting for data.
The following is the simplest way to get information:
Goal: keep asking whether or not data is available
-Latency (microseconds): 100
-Throughput (KB/s): 10
-CPU utilization: 5%
Goal: reducing overhead of sending command to device
-Latency (microseconds): 1000
-Throughput (KB/s): 21
-CPU utilization: 10.5%
Note: From this point on, assume CPU has a lot of useful work elsewhere (multiple tasks, jumps back to task when data ready).
Goal: let CPU do other things when waiting for data
-Latency (microseconds): 106
-Throughput (KB/s): 18
-CPU utilization: 8.9%
Goal: talk directly to RAM, not to CPU, give signal when done
(access memory directly)
-Latency (microseconds): 61
-Throughput (KB/s): 91
-CPU utilization: 45%
Goal: event driven approach, don't do threading
-Latency (microseconds): 56
-Throughput (KB/s): 167
-CPU utilization: 84%
Here are some assumptions that are made for the Eggert File System:
There is a linear array of sectors (ignore that disk is actually in tracks). We start each file on a sector boundary (sector size is 512bytes). In order to keep track of where files are, there is a table of files at the beginning of the array.
Array of sectors
-------------------------------------------------------------------------
| |///////////| | | | |========|////////////////| |
-------------------------------------------------------------------------
Table File1 Junk Empty File2
-Size = number of bytes
-Location = sector # (don't need file size, since each file starts at sector boundary)
-Can cheat a little, since sector #'s are smaller than sector boundaries
-Sector # was chose to be 2 bytes in Egger File System
# bytes |------10 bytes ------|
---------------------------------------------------------
| | | foo bar |
---------------------------------------------------------
Sector
#
-8 sectors, 32 entries * 8 = 256 files
How was this similar to file systems at the time?
The Eggert File System ended up being similar to RT 11 file system (by Digital Equipment Corp). The RT 11 (RT = real time) file system was built to be predictable behavior, which is why it was used by real time systems. The Eggert File System ended up having many of the same advantages that would be useful for real time systems.
- Simple
- Low index overhead
- Sequential access is fast
- Relatively fast random access
- Internal fragmentation (small files wastes a lot of space in this file system)
- External fragmentation: free space exists, but not contiguous
- Poor performance if directory order, was not equal to data order
- Files can't easily grow
-One way to address this problem is to require size estimate on creation of file
- # of files is limited
We focus on attacking the following problems:
1) Files can't easily grow
2) External fragmentation: free space exists, but not contiguous
(File Allocation Table)
Superblock
------------------------------------------------------------------------------
| | | FAT | DATA
------------------------------------------------------------------------------
Boot
Sector
Superblock (had information about: version of FAT, size, # used sectors, root directory)
The super block contained information about file system as a whole
Sector numbers labeled:
FAT (basically a linked list table)
Each sector in table is labeled with next sector number
0 => EOF
-1=> free block
1 | |
2 | 200 |
3 | |
4 | 2 |
5 | |
- Directory: a file that maps file names to other files
-nested directories OKAY
|foo.dat sector# size filetype |
|subdir sector# size filetype |
| |
| |
| |
| |
| |
| |
| |
-FAT 16: 16 bit numbers
- Held up to 32 megabytes of data
- It was designed for floppy
RT11: Easy
FAT: Easy, if file stays in same directory
Harder if you move from one directory to another and rename it
(example: "mv d/f e/g")
- "mv d/f e/g"
- write "e/g"
- Say that there is a loss of power…
- Both "d/f" and "e/g" exists
- Now the file is both allocated and freed
-add a level of indirection
-8 KiB blocks
-2^32*2^13 bytes/file system
boot sector |-------------data------------->
-------------------------------------------------------------------------------------
| | | | | | |
--------------------------------------------------------------------------------------
superblock block inode table
bitmap
(1 bit/block)