[C Programming]

I had posted this question many times before, but got no answer. Please help me.

We just need to edit the code currently given below in the 'random_cache.c' to use the least recently used (LRU) replacement policy instead of the random replacement policy that is currently being used. The least recently used replacement policy is when the page that is used least recently is replaced. Please post screenshots of your code along with your code as it is easier to see the format that way. Thank You!

These are the instructions:

The code also has to meet these requirements:

1. lookup should give negative value on non-cached elements

2. insert should correctly cache elements

3. clearing an element should remove it from the cache

4. replacement policy should be LRU

To run the code we did:

gcc -o replacement cache_sim.c random_cache.c

-----------------------------------------------------------------------------------------

These are the files to be edited:

random_cache.c:

#include  #include "random_cache.h" // // A simple cache for positive float values, with a random replacement policy // CACHE *cache_new(int size) { CACHE *cache = malloc(sizeof(CACHE)); cache->size = size; cache->addr = malloc(size * sizeof(int)); cache->data = malloc(size * sizeof(float)); // initialize cache int i; for (i = 0; i size; i++) { cache->addr[i] = -1; cache->data[i] = 0.0; } return cache; } // return data element i if it is cached; else return -1 float cache_lookup(CACHE *cache, int i) { // is data element i in cache? int j; for (j = 0; j size; j++) { if (cache->addr[j] == i) { // yes, cache hit return cache->data[j]; } } // cache miss return -1.0; } // record in the cache that the ith data element has value x // random replacement policy is used void cache_insert(CACHE *cache, int i, float x) { int j = rand() % cache->size; cache->addr[j] = i; cache->data[j] = x; } // clear the ith element of the cache void cache_clear(CACHE *cache, int i) { int j; for (j = 0; j size; j++) { if (cache->addr[j] == i) { cache->addr[j] = -1; break; } } } 

random_cache.h:

typedef struct cache { int size; // number of cache elements int *addr; // index of element float *data; // value of element } CACHE; CACHE *cache_new(int size); float cache_lookup(CACHE *cache, int i); void cache_insert(CACHE *cache, int i, float x); void cache_clear(CACHE *cache, int i); 

-------------------------------------------------------------------------------------------------------

This is the file that models the cache storage and it is NOT to be edited/modifed. Leave the file as it is.

cache_sim.c:

#include  #include  #include "cache.h" // // A simple data store with cache // #define DATA_SIZE 1000 #define CACHE_SIZE 10 // // Data is stored in array data[] // float data[DATA_SIZE]; int nhits = 0; int nmisses = 0; CACHE *cache; // initialize the data array void init() { int i; // initialize data for (i = 0; i = DATA_SIZE) { fprintf(stderr, "get: no data element %d ", i); exit(EXIT_FAILURE); } float x = cache_lookup(cache, i); if (x >= 0) { // cache hit nhits++; return x; } else { // cache miss nmisses++; x = data[i]; // insert x into the cache cache_insert(cache, i, x); return data[i]; } } // set the ith data value to x void set(int i, float x) { if (i = DATA_SIZE) { fprintf(stderr, "set: no data element %d ", i); exit(EXIT_FAILURE); } // clear cache entry cache_clear(cache, i); data[i] = x; } // simulate a lot of data accesses int main(int argc, char *argv[]) { // simulation parameters int num_accesses = 100000; int dist_size = 10; int move_size1[] = {-3,-2,-1,0,0,0,0,1,2,3}; int move_size2[] = {-5,-4,-3,-2,-1,1,2,3,4,5}; init(); int i,j,delta; j = 0; for (i = 0; i = DATA_SIZE) { j = DATA_SIZE - 1; } get(j); } printf("hits: %d; misses: %d ", nhits, nmisses); exit(0); }

The program models storage with cache through the cache_sim.c file. It uses the random replacement policy. The code that implements cache with a random replacement policy is in random_cache.h and random_cache.c Your job is to edit the random_cache.c and random_cache.h files given that use the random replacement policy, to use the least recently used policy instead. DO NOT MODIFY cache sim.c ONLY MODIFY random cache.c and random cache.h If you run the current code using the random replacement policy, you get: hits: 73548; misses: 26452 After you modify it to use the least recently used replacement policy, you should get: hits: 78399; misses: 21601 The program models storage with cache through the cache_sim.c file. It uses the random replacement policy. The code that implements cache with a random replacement policy is in random_cache.h and random_cache.c Your job is to edit the random_cache.c and random_cache.h files given that use the random replacement policy, to use the least recently used policy instead. DO NOT MODIFY cache sim.c ONLY MODIFY random cache.c and random cache.h If you run the current code using the random replacement policy, you get: hits: 73548; misses: 26452 After you modify it to use the least recently used replacement policy, you should get: hits: 78399; misses: 21601