Project for algorithms assignment implementing cache policies: LRU FIFO OPTFF UF Name / ID: Evan Harden - 27541192
Make sure python is installed From the main project directory, enter the command specifying the input file:
python src/main.py <relative file path>
Example: python src/main.py data/1
Files may be placed in the data folder, but isn't strictly required. The program accepts any valid relative file path. Input file content is not validated, and it is assumed to contain valid data. Input file must be specified with extension if applicable.
Example files can be found in data directory. Expected outputs for each case:
data/1: FIFO : 33 LRU : 30 OPTFF: 19
data/2: FIFO : 23 LRU : 29 OPTFF: 15
data/3: FIFO : 19 LRU : 16 OPTFF: 12
data/4: FIFO : 27 LRU : 24 OPTFF: 18
| Input File | k | m | FIFO | LRU | OPTFF |
|---|---|---|---|---|---|
| data/1 | 4 | 56 | 33 | 30 | 19 |
| data/2 | 5 | 55 | 23 | 29 | 15 |
| data/3 | 6 | 58 | 19 | 16 | 12 |
| data/4 | 4 | 54 | 27 | 24 | 18 |
OPFF consistently has the fewest misses with these data. FIFO performed better than LRU for data/2 , but LRU had less misses for the rest of the tests. This suggests LRU generally performs better than FIFO
Consider the sequence with k=3: 1 2 3 4 1 2 3 4
Using the program to calculate misses: LRU - 8 FIFO - 8 OPTFF - 5
From the sequence, at index 4 when the cache is full, LRU and FIFO evict 1 when the very next id needed was 1. In both LRU and FIFO for the cyclic sequence of length k + 1, both will always run into misses. With OPTFF, the next item with access time furthest away, this doesn't happen
Assume there exists an optimal schedule S that makes the same eviction decisions as OPTFF through the first j steps of a sequence.
At j = 0, the caches of both S and OPTFF are empty, upholding the invariant. Assume there is an optimal schedule S that matches OPTFF for j steps. We show we can create an optimal schedule S' that matches OPTFF for j+1 steps.
Let d be the request at j+1. If d is a hit, or if S and OPTFF evict the same item on a miss, the invariant holds.
If d is a miss and S evicts item x while OPTFF evicts item y, we know by the definition of OPTFF that "y is the item in the cache whose next request occurs farthest in the future.
the next request for x happens before the next request for y. We construct S' by modifying S to evict y instead of x at step j+1. After this swap, the cache of S' has x and the cache of S has y. Since x is needed sooner than y, S will eventually get a miss to bring x back into the cache. S' can evict x and bring in whatever S needs, syncing the two cache states. Because y was the furthest in the future, S' is guaranteed not to miss on y before S is forced to miss on x.
S' matches OPTFF at step j+1 and incurs no more misses than the optimal schedule S. Therefore, S' is also optimal. OPTFF is optimal for the entire sequence.