COMP2004
Programming Practice
2002 Summer School


Kevin Pulo
School of Information Technologies
University of Sydney


(page 1)


Assignment 3





(page 2)


Background




(page 3)


Addresses and pages




(page 4)


Pages diagram






(page 5)


Finding page numbers


= 91.045166...
= 91


(page 6)


Frames




(page 7)


Cache diagram





(page 8)


Accessing information




(page 9)


Loading pages




(page 10)


Cache misses




(page 11)


Writing to frames




(page 12)


Cache diagram revisited





(page 13)


Write-back




(page 14)


Types of cache miss




(page 15)


Your task




(page 16)


Your code




(page 17)


Classes




(page 18)


Creating Cache objects


CacheFactory::createCache(s);


(page 19)


Creation string format


lookahead check_frames



(page 20)


Main loop


char mode;
Cache::addr_t address;
while (cin >> mode >> address) {
if (mode == 'r') {
c->read(address);
} else if (mode == 'w') {
c->write(address);
}
outputStats(*c);
}


(page 21)


Cache typedefs




(page 22)


Output


void outputStats(const Cache &c) {
Cache::counter_t hits = c.getHits(),
misses = c.getMisses(),
missesWB = c.getMissesWB();

cout << hits << " " <<
misses << " " <<
missesWB << endl;
}


(page 23)


Paging algorithms





(page 24)


First In First Out (FIFO)




(page 25)


FIFO Example





(page 26)


Least Recently Used (LRU)






(page 27)


LRU Example





(page 28)


Pipelined LRU (PLRU)





(page 29)


Pipelining and lookahead list




(page 30)


Lookahead list example


w 2000
w 1492
r 456
w 24121
r 24120
r 34
r 4592
r 2000
w 2000
r 1492
r 24120

Contains 0 operations.
0 operations processed.
Initially empty.


(page 31)


Lookahead list example


* w 2000
w 1492
r 456
w 24121
r 24120
r 34
r 4592
r 2000
w 2000
r 1492
r 24120

Contains 1 operation.
0 operations processed.


(page 32)


Lookahead list example


w 2000
* w 1492
r 456
w 24121
r 24120
r 34
r 4592
r 2000
w 2000
r 1492
r 24120

Contains 2 operations.
0 operations processed.


(page 33)


Lookahead list example


w 2000
w 1492
* r 456
w 24121
r 24120
r 34
r 4592
r 2000
w 2000
r 1492
r 24120

Contains 3 operations.
0 operations processed.


(page 34)


Lookahead list example


w 2000
w 1492
r 456
* w 24121
r 24120
r 34
r 4592
r 2000
w 2000
r 1492
r 24120

Contains 4 operations.
0 operations processed.


(page 35)


Lookahead list example


+ w 2000
w 1492
r 456
w 24121
* r 24120
r 34
r 4592
r 2000
w 2000
r 1492
r 24120

Contains 4 operations.
1 operation processed.


(page 36)


Lookahead list example


w 2000
+ w 1492
r 456
w 24121
r 24120
* r 34
r 4592
r 2000
w 2000
r 1492
r 24120

Contains 4 operations.
2 operations processed.


(page 37)


Lookahead list example


w 2000
w 1492
+ r 456
w 24121
r 24120
r 34
* r 4592
r 2000
w 2000
r 1492
r 24120

Contains 4 operations.
3 operations processed.


(page 38)


Lookahead list example


w 2000
w 1492
r 456
+ w 24121
r 24120
r 34
r 4592
* r 2000
w 2000
r 1492
r 24120

Contains 4 operations.
4 operations processed.


(page 39)


Lookahead list example


w 2000
w 1492
r 456
w 24121
+ r 24120
r 34
r 4592
r 2000
* w 2000
r 1492
r 24120

Contains 4 operations.
5 operations processed.


(page 40)


Lookahead list example


w 2000
w 1492
r 456
w 24121
r 24120
+ r 34
r 4592
r 2000
w 2000
* r 1492
r 24120

Contains 4 operations.
6 operations processed.


(page 41)


Lookahead list example


w 2000
w 1492
r 456
w 24121
r 24120
r 34
+ r 4592
r 2000
w 2000
r 1492
* r 24120

Contains 4 operations.
7 operations processed.


(page 42)


Lookahead list example


w 2000
w 1492
r 456
w 24121
r 24120
r 34
+ r 4592
r 2000
w 2000
r 1492
* r 24120

Contains 4 operations.
7 operations processed.

No more input!
flush() is called, which indicates to process the
rest of the lookahead list.


(page 43)


Lookahead list example


w 2000
w 1492
r 456
w 24121
r 24120
r 34
r 4592
+ r 2000
w 2000
r 1492
r 24120

Contains 3 operations.
8 operations processed.


(page 44)


Lookahead list example


w 2000
w 1492
r 456
w 24121
r 24120
r 34
r 4592
r 2000
+ w 2000
r 1492
r 24120

Contains 2 operations.
9 operations processed.


(page 45)


Lookahead list example


w 2000
w 1492
r 456
w 24121
r 24120
r 34
r 4592
r 2000
w 2000
+ r 1492
r 24120

Contains 1 operation.
10 operations processed.


(page 46)


Lookahead list example


w 2000
w 1492
r 456
w 24121
r 24120
r 34
r 4592
r 2000
w 2000
r 1492
+ r 24120

Contains 0 operations.
All 11 operations
processed.


(page 47)


Finding frame to remove




(page 48)


PLRU example 1




(page 49)


PLRU example 1






(page 50)


PLRU example 1


v

^


(page 51)


PLRU example 1


v

^


(page 52)


PLRU example 1


v

^


(page 53)


PLRU example 1





(page 54)


All frames needed soon?




(page 55)


All frames needed example


w 1492 (page 2)
w 50 (page 0)
w 15400 (page 30)
w 15300 (page 30)
w 180 (page 0)
r 2200 (page 4)
w 1292 (page 2)




(page 56)


All frames needed example


w 1492 (page 2)
w 50 (page 0)
w 15400 (page 30)
w 15300 (page 30)
w 180 (page 0)
r 2200 (page 4)
w 1292 (page 2)


(page 57)


All frames needed example


w 1492 (page 2) First (page 2)w 50 (page 0)
w 15400 (page 30)
w 15300 (page 30)
w 180 (page 0)
r 2200 (page 4)
w 1292 (page 2)


(page 58)


All frames needed example


w 1492 (page 2) First (page 2)w 50 (page 0) First (page 0)w 15400 (page 30)
w 15300 (page 30)
w 180 (page 0)
r 2200 (page 4)
w 1292 (page 2)


(page 59)


All frames needed example


w 1492 (page 2) First (page 2)w 50 (page 0) First (page 0)w 15400 (page 30) First (page 30)w 15300 (page 30)
w 180 (page 0)
r 2200 (page 4)
w 1292 (page 2)


(page 60)


All frames needed example


w 1492 (page 2) First (page 2)w 50 (page 0) First (page 0)w 15400 (page 30) First (page 30)w 15300 (page 30)
w 180 (page 0)
r 2200 (page 4) First (page 4)w 1292 (page 2)


(page 61)


All frames needed example


w 1492 (page 2) First (page 2)w 50 (page 0) First (page 0)w 15400 (page 30) First (page 30)w 15300 (page 30)
w 180 (page 0)
r 2200 (page 4) First (page 4)w 1292 (page 2)




(page 62)


PLRU example 2





(page 63)


PLRU example 2






(page 64)


PLRU example 2


v

^


(page 65)


PLRU example 2


v

^


(page 66)


PLRU example 2


v v

^ ^


(page 67)


PLRU example 2




(page 68)


PLRU example 2





(page 69)


PLRU example 3


v v

^ ^


(page 70)


PLRU example 3






(page 71)