Untitled

 avatar
user_0616194
plain_text
a year ago
3.1 kB
17
Indexable
Never
package os_algorithm;


import java.util.LinkedHashMap;
import java.util.Map;

public class lru_algorithm {
    private final int capacity;		// declares the maximum capacity of the cache
    private final LinkedHashMap<Integer, Integer> cache;		// declares the cache as a LinkedHashMap with the page number as the key

    public lru_algorithm(int capacity) {
        this.capacity = capacity;		// assigns the given capacity to the LRU cache 
        this.cache = new LinkedHashMap<>(capacity, 0.75f, true) {		// initializes the LRU cache with the given capacity and sets the access order flag to true
            /**
			 * 
			 */
			private static final long serialVersionUID = 1L;

			@Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > capacity;		// returns true if the cache has more than the maximum allowed entries, which causes the eldest entry to be removed
            }
        };
    }

    public int getPage(int pageNumber) {
        Integer value = cache.get(pageNumber);		// gets the value associated with the given page number from the cache
        if (value == null) {
            value = -1; 		 // sets the value to -1 if the page number is not in the cache, indicating a page fault  
        }
        return value;		// returns the value associated with the given page number
    }

    public void setPage(int pageNumber, int value) {
        cache.put(pageNumber, value);		// puts the given value into the cache associated with the given page number
    }

    public static void main(String[] args) {
        int[] pageRequests = {1, 2, 3, 4, 1, 5, 1, 2, 6, 7, 2, 1, 5, 3, 4, 6};
        int capacity = 3;
        lru_algorithm cache = new lru_algorithm(capacity);
        int pageFaults = 0;

        System.out.printf("%-10s %-10s %-15s\n", "Page", "Cache", "Page Faults");
        for (int pageRequest : pageRequests) {
            int value = cache.getPage(pageRequest);
            if (value == -1) {
                pageFaults++;
                value = pageRequest; // assign a value to the new page
                cache.setPage(pageRequest, value);
            }
            System.out.printf("%-10d %-10s %-15d\n", pageRequest, cache.cache.keySet(), pageFaults);
        }
        System.out.println("Total page faults: " + pageFaults);
    }

	public int getCapacity() {
		return capacity;
	}
}

/*
    1. Set the capacity of the cache and the page requests.
    2. Create a new LRU cache with the given capacity.
    3. Initialize a counter for the number of page faults.
    4. Print a table header with the column names "Page", "Cache", and "Page Faults".
    5. For each page request in the list:
        a. Get the value associated with the page number from the cache.
        b. If the value is -1, increment the page faults counter and add the new page to the cache.
        c. Print the current page request, the contents of the cache, and the page faults count.
    6. Print the total number of page faults.
*/