GSoC2009 Liu Journal

From Syslinux Wiki

Well, life starts early; my job starts. Here is the journal sorts in what I did but not when I did it.

LRU algorithm(2009-05-06)

With one night, I rewrote the cache code in C and made it work well.

Well, the LRU(Least Recently Used) algorithm isn't that complicated. And in my implementation, there are only two functions; they are:

• cache_init: initialize the cache in a double list structure.
• get_cache_sector:

1. find the corresponding cache structure in a list way; if hit, go 3.
2. if missed, add it to the LRU head replace the most least cache, as well as the leftmost cache structure.
3. In there, no mater missed or not, we find a cache to store or stored the sector. So remove it from the list.
4. add it to the rightmost cache make it be the most recent cache, means add it to the preview of head cache.
5. return it's address.

And here is the model of LRU algorithm:

         least cache
---------------------------------------------------------------------
| head |  leftmost cache ｜.....................｜rightmost cache  ｜     
---------------------------------------------------------------------
                                                recently cache