Confusing OPT Page Replacement

Confusing OPT Page Replacement

This is from my paper:
A cache is a high speed memory that aims to minimize the access to the
low-speed memory. An effective cache can help to improve the performance
of your computer. In this project, we study a simplified version of memory
cache.
Processor -- Cache -- Memory
Assume that your computer has a cache memory of size S. Assume that your
memory has a set of entries 1, ..., n. When you use your computer, a list
of entry accesses is generated one by one. At any particular time, suppose
you need to access entry f. The computer first checks if it is in the
cache. If yes, we can access the entry f from cache. Otherwise, there is a
cache miss and you will need to request the entry f from the memory. Then,
you can decide if you want to replace one entry in the cache by f. Our aim
is to minimize the number of cache miss.
OPT: This strategy replaces the entry that minimizes the number of cache
miss.



Given the input reference string: 1 2 3 1 4 1 2 3, this is what I work out
http://i.imgur.com/dk0xg9q.jpg The cache miss/page fault is 5
However the answer given was 4 http://i.imgur.com/UtK8eaI.jpg It
apparently shows that the entry "4" was not put into the cache but still
counted as cache miss.
Also, with another example 4 7 1 3 3 2 1 6 2 1 6 2 1 5 1 8 8 8 3 1 7 6 5 1
5 4 1, using the same method, I got the cache miss of 24 but the answer
given was 19.
I do not understand why. I thought Optimal strategy was to replace the
frame page that will not be used for the longest period of time. I hope
someone could explain in detail why.