Delivery-Date: Wed Nov 19 13:59:52 2008
Message-Id: <200811192156.mAJLuwsU011608@bourbon.usc.edu>
To: cs551@merlot.usc.edu
Subject: Re: CS551: Final Project 2 : Queries
Date: Wed, 19 Nov 2008 13:56:58 -0800
From: Bill Cheng <william@bourbon.usc.edu>

Someone wrote:

  > I had the following queries about final project part 2:
  > 
  > 1. LRU - If the cache at a node is full, we need to replace the file using
  > LRU replacement policy.
  > 
  > Now, in the follwing scenario, what would be the expected solution.
  > The total cache size is 10K.
  > There are 3 files in the cache, with size and time stamp of last access of
  > that file as below:
  > file1 2k 2.5sec
  > file2 4k 3.5sec
  > file3 4k 4.5sec
  > 
  > Now, at this node, if we get a request to cache another file, file 4 (size
  > 3k) . But since there is no more free cache space we need to do an LRU
  > replacement of the existing files.
  > If we run the LRU on the cache mentioned above, the file1 will be removed
  > (because its the LRU file) and we will try to store the new file, file4 at
  > this place but the free space now is only 2k (after removing file1) and we
  > need 3k.
  > so what do we do in this case ?
  > a. drop the new file and give an error message that there is not enough
  > space in cache ?
  > b., run the lru again and replace the file which might not be the LRU file
  > but is of size greater than or equal to the new file size ?

Slide 17 of lecture 18 says:

    while (filesize + current usage > CacheSize)
        start deleting files from the head of the LRU list
        (this would decrease current usage)

So, in your example, you will delete both file1 and file2
so that you can add your new file.