<Scribe Note 11/20/08>
By: Hyun Joon Lee, Santiago Mok
File System Continued..
Policy Question
- Page Replacement Policy (Figuring out which victim to throw out of memory)
Assume: random access memory, then any page replacement policy works
-
LOCALITY OF REFERENCE
1) Spatial – tend to access the similar location next time
2) Temporal – after accessing at time t, it tends to access at time t + a (a is very small) next time
·
Simple Page Replacement Policy
<1> FIFO (First In, First Out)
Victim: “Oldest page”
Ex) Reference String
- With 3 Ram -> 9 Page Fault
|
|
The page # in memory being requested |
|||||||||||
|
Page |
0 |
1 |
2 |
3 |
0 |
1 |
4 |
0 |
1 |
2 |
3 |
4 |
|
A |
Δ0 |
0 |
0 |
Δ3 |
3 |
3 |
Δ4 |
4 |
4 |
4 |
4 |
4 |
|
B |
- |
Δ1 |
1 |
1 |
Δ0 |
0 |
0 |
0 |
0 |
Δ2 |
2 |
2 |
|
C |
- |
- |
Δ2 |
2 |
2 |
Δ1 |
1 |
1 |
1 |
1 |
Δ3 |
2 |
- With 4 Ram -> 10 Page Fault
|
|
The page # in memory being requested |
|||||||||||
|
Page |
0 |
1 |
2 |
3 |
0 |
1 |
4 |
0 |
1 |
2 |
3 |
4 |
|
A |
Δ0 |
0 |
0 |
0 |
0 |
0 |
Δ4 |
4 |
4 |
4 |
Δ3 |
3 |
|
B |
- |
Δ1 |
1 |
1 |
1 |
1 |
1 |
Δ0 |
0 |
0 |
0 |
Δ4 |
|
C |
- |
- |
Δ2 |
2 |
2 |
2 |
2 |
2 |
Δ1 |
1 |
1 |
1 |
|
D |
- |
- |
- |
Δ3 |
3 |
3 |
3 |
3 |
3 |
Δ2 |
2 |
2 |
“Belady Anomaly” : Adding RAM actually increased the number of page faults
<2> Oracle of
It looks to the future then pick the least used one, however impossible to implement
Ex) from previous example, 7 page faults
|
|
The page # in memory being requested |
|||||||||||
|
Page |
0 |
1 |
2 |
3 |
0 |
1 |
4 |
0 |
1 |
2 |
3 |
4 |
|
A |
Δ0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Δ2 |
2 |
2 |
|
B |
- |
Δ1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Δ3 |
3 |
|
C |
- |
- |
Δ2 |
Δ3 |
3 |
3 |
Δ4 |
4 |
4 |
4 |
4 |
4 |
<3> Least Recently Used (LRU) algorithm
It looks at recent past instead.
Generally, LRU > FIFO.
Ex) total of 10 page faults occur
|
|
The page # in memory being requested |
|||||||||||
|
Page |
0 |
1 |
2 |
3 |
0 |
1 |
4 |
0 |
1 |
2 |
3 |
4 |
|
A |
Δ0 |
0 |
0 |
Δ3 |
3 |
3 |
Δ4 |
4 |
4 |
Δ2 |
2 |
2 |
|
B |
- |
Δ1 |
1 |
1 |
Δ0 |
0 |
0 |
0 |
0 |
0 |
Δ3 |
3 |
|
C |
- |
- |
Δ2 |
2 |
2 |
Δ1 |
1 |
1 |
1 |
1 |
1 |
Δ4 |
To implement LRU,
We approximate with clock interrupt code by having extra bit in the page table
·
Optimization
<1> Demand Paging
Don’t page from disk until program actually needs it!
Ex) N pages in program
U <= N pages actually needed
C : Cost to read a page(avg)
F : Faulting
|
|
Total Cost |
Latency (Time to start a program) |
|
No demand Paging |
NC |
NC |
|
With Demand Paging |
U(C + F) |
C + F |
Assuming plenty of RAM
<2> Dirty Bit
Don’t write victim page to disk
(done when victim is clean)
To implement, add dirty bit in the page table and set to all 0’s
When anything is written, flip to 1 (dirty page entry)
You can implement this in software by making pages “read only” at first.
<How to implement malloc
atop virtual Memory>
P = malloc(10,000,000); // Invoking mmap( system call with page table)
…..
Free(p); // Invoking Munmap(p, 10000000);
·
Fork vs. vFork
-
vFork is like Fork
except
1) Parent is frozen until child execlp() or exit
2) Child can modify only the local variable in its function
3) Child can’t return from function calling vfork
-
vFork is faster,
because they share RAM + page tables
-
You don’t
need vfork if you have copy-on-write
- Fork()
clones PTEs, not pages by marking both parents and
child as Read Only. It clones page only when needed.
Disk Scheduling
- algorithm to decide disk access (write and read) order
- disk read and write access impact overall system performance since disk speed is very slow
- common to file system and virtual memory
- similar to CPU scheduling, we want to achieve very high throughput
o i.e. very high I/O operations per second
- must avoid starvation (fairness)
For example:
Simple Model:
- N blocks on disks: 0,1,…,N-1
- Seek time between blocks ‘i’ is |i-j|
Given:
1) a set of m blocks to access (write) {b0, …, bm-1}
2) current disk head position (shown in figure 1)
0 ≤ h < N
|
0 |
|
h |
|
|
…. |
N-1 |
Figure 1
Scheduling Algorithm
FCFS (First Come First Serve):
Read and Write requests are served in the order they came in.
Advantage: no starvation
Disadvantage: potential for seek across disk that might cause long seek time.
Average seek time on different location of disk
Start
|
|
|
N/4 |
|
N/2 |
End
Average seek time (assuming random writes) ≈ N/3
SSTF (Shortest Seek
Time First)
Assuming disk head’s position is known, disk access are ordered in shortest seek
time relative to the disk head’s position
Assume the following disk track access
|
15 |
5 |
8 |
0 |
2 |
SSTF algorithm relative to track 0 position
|
0 |
2 |
5 |
8 |
15 |
Advantage:
o minimizes latency
o maximizes throughput
Disadvantage:
o starvation
Elevator Scheduling
As the name implies, the algorithm determine where on disk to stop and similar to SSTF except it don’t change seek direction until it is necessary.
|
|
Head |
|
|
|
Advantages:
- no starvation
- almost SSTF performance
Average seek time on disk location
|
|
|
N/2 |
|
N |
Disadvantage
- unfair!
Anticipatory
Scheduling
This algorithm wait a teensy bit to schedule next write, just in case a previous write to block ‘i’ will be succeeded by request to block i+1. This algorithm is unfair because it’s so often augmented by timeout.
Flash File System Issues
1) Flash wears out, ~ 100,000 write-erase cycles (NOR Flash)
2) Must erase before writing, writes are very slow
3) No seek
Performance Memes
- Locality of Reference
- Speculation: pretend you have an oracle that predict future accesses
- Prefetching: guess where the next page fault will be read page in
- Batching: getchar buffers (i.e. 8KB in RAM)
- Dallying: purchar() … anticipatory disk scheduling
- Multitasking: parallel processes can gain access to hardware that is not in use
Multitasking Example:
|
Task
1 |
CPU |
I/O |
CPU |
I/O |
|
Task
2 |
I/O |
CPU |
I/O |
CPU |