Assignment 1
This assignment is based around memory management.
Paging/Caching
Two level virtual memory system
Slow memory contains more pages than fast memory called cache.
Requesting a page:
- If a page is already in cache.
- Hit
- If page not in cache.
- Miss.
In case of a miss, need to evict a page from cache to make room: eviction algorithms
Eviction Algorithms
No Eviction
Nothing is evicted with the cache containing exactly what it contains initially.
Example
- Cache: 20, 30, 10
- Sequence of Requests: 20, 30, 5, 30, 5, 20
- Output: hhmhmh (4h 2m)
Evict FIFO
In the case of a miss the first element in the cache will be evicted first. This is similar to a queue.
Example
- Cache: 20, 30, 10
- Sequence of Requests: 20, 30, 5, 30, 5, 20
- Output: hhmhhm (4h 2m)
| 20 | 30 | 10 |
|---|---|---|
| 5 | 20 | 10 |
Second row is after the request sequence.
Evict LFU (Least Frequently Used)
If there is more than one page with lowest frequency, evict the leftmost one.
Example
- Cache: 20, 30, 10
- Sequence of Requests: 20, 30, 5, 30, 5, 20
- Output: hhmhhh (5h 1m)
| Cache | Frequency | Explanation |
|---|---|---|
| 20 30 10 | 1 1 1 | Initial cache. |
| 20 30 10 | 2 1 1 | Frequency of 20 increased. |
| 20 30 10 | 2 2 1 | Frequency of 30 increased. |
| 20 30 5 | 2 2 1 | 5 is a miss, evict 10 (freq of 1). |
| 20 30 5 | 2 3 1 | Frequency of 30 increased. |
| 20 30 5 | 2 3 2 | Frequency of 5 increased. |
| 20 30 5 | 3 3 2 | Frequency of 20 increased. |
Evict LFD (Longest Forward Distance)
We look forward in the request queue and replace the item in the cache that is furthest forward. If there is more than one page with same position of next request $\infty$ evict, leftmost one.
Example
- Cache: 20, 30, 10
- Sequence of Requests: 20, 30, 5, 30, 5, 20
- Output: hhmhhh (5h 1m)
| Cache Before | Cache After | Position of Next Request |
|---|---|---|
| 20 30 10 | 1 2 $\infty$ | |
| 20 30 10 | No change. | 6 2 $\infty$ |
| 20 30 10 | No change. | 6 4 $\infty$ |
| 20 30 10 | 20 30 5 | 6 4 5 |
| 20 30 5 | No change. | 6 $\infty$ 5 |
| 20 30 5 | No change. | 6 $\infty$ $\infty$ |
| 20 30 5 | No change. | $\infty$ $\infty$ $\infty$ |