수다닷컴

이거 LRU LFU알고리즘짜는코딩이에요!힙을이용해서..

LRFU알고리즘함수를 코딩해야하는데ㅠㅠ
어떻게시작해야할지잘모르게써요ㅠㅠ
CRF값이 동률인 경우 last reference time이 더 오래된 것을 쫓아내도록 구현해야 합니다.
(첨부 LRFU.c 파일의 힙 부분에 이미 반영돼 있음)

LRFU함수에는밑의내용이 들어가야해요ㅠㅠfor문을 돌려 i=0부터 i값이 string_length에 도달할 때까지 i를 1씩 증가시키며 아래 사항을 수행.1.해당 block이 이미 cache에 존재하는 경우 CRF값을 변경한 후 HeapDown을 호출해서 위치 찾기2. 해당 block이 cache에 없는 경우 우선 cache_miss 증가시킨 후
cache가 꽉 찬 경우 root를 쫓아내고 그 자리에 새로 들어온 block을 넣고 HeapDown
cache가 꽉 차지 않은 경우 현재 힙에들어있는block 갯수를 1 증가시키고 그 위치에 새 block을 놓은 후 HeapUp------HeapUp(), HeapDown() 함수의 사용과제 설명 파일과 약간 다르게 heap의 root가 index 0번을 가지도록 작성되었습니다.

HeapUp 함수는 HeapUp(int현재까지 제일 큰index 번호, int 현재의논리시각)

HeapDown 함수는 HeapDown(int 비교해서 밑으로 내려가려는 노드의 index번호, int 제일 큰 index 번호, int 현재의 논리시각)

으로 사용하면 됩니다.

(예1) 인덱스 i 인 위치의 block이 시각 t에 재참조된 경우 (현재 cache 내에 n개의 block이 있는 경우)
HeapDown(i, n-1, t) /* n-1인 이유는 n개의 block의 index가 0, 1, 2, 3, ..., n-1 */

고수님들
ㅜㅜ꼭좀 알려주세요ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ
fill in 부분 채우면되거든요..ㅠ.ㅠ.ㅠ.ㅠㅠㅠㅠ.ㅠ.ㅠ.ㅠㅠㅠㅠㅠㅠㅠㅠㅠ

#include stdio.h
#include stdlib.h
#include math.h
#define F(x) pow(0.5, lambda*(x))
struct BLOCK{
int valid; /* valid=1, invalid=0 */
int block_location;
};
struct BLOCK *block;
struct CACHE{
int block_num;
float CRF;
int last_ref_time;
int heap_i; /* heap index */
};
struct CACHE *cache;
int max = 0; /* maximum block number */
int cache_size, string_length, *ref_string;
float lambda;
int cache_miss = 0; /* number of cache misses */
int *heap;
FILE *input_file;
void init();
void LRFU();
void heapDown(int, int, int);
void heapUp(int, int);

int main(int argc, char *argv[]){
int i;
input_file = fopen(argv[4], r);
cache_size = atoi(argv[2]);
string_length = atoi(argv[3]);
lambda = atof(argv[1]);
ref_string = (int *)malloc(string_length * sizeof(int));
for(i=0; istring_length; i++){
fscanf(input_file, %d, &ref_string[i]);
if(ref_string[i] max) max = ref_string[i];
}
fclose(input_file);
block = (struct BLOCK *)malloc((max+1) * sizeof(struct BLOCK));
cache = (struct CACHE *)malloc(cache_size * sizeof(struct CACHE));
heap = (int *)malloc((cache_size) * sizeof(int));
init();
LRFU();
printf(\n LRFU cache miss count : %d \n, cache_miss);
free(ref_string);
free(block);
free(cache);
free(heap);
}

void init(){
int i;
for(i=0; imax+1; i++) block[i].valid=0;
for(i=0; icache_size; i++){
cache[i].block_num = -1;
cache[i].CRF = 0.;
cache[i].last_ref_time = 0;
}
}
void LRFU()
{
/* fill in */
}
void heapDown(int newNode, int n, int current_time){
int child;
int tmp1, tmp2, rootkey;
rootkey = heap[newNode];
child = 2 * newNode + 1;
while(child=n){
if((childn) && (cache[heap[child]].CRF*F(current_time-cache[heap[child]].last_ref_time) =
&nbsbsp; cache[heap[child+1]].CRF*F(current_time-cache[heap[child+1]].last_ref_time)))
if(cache[heap[child]].CRF*F(current_time-cache[heap[child]].last_ref_time)
cache[heap[child+1]].CRF*F(current_time-cache[heap[child+1]].last_ref_time) ||
cache[heap[child]].last_ref_time cache[heap[child+1]].last_ref_time)
child++;
if(cache[rootkey].CRF*F(current_time-cache[rootkey].last_ref_time)
cache[heap[child]].CRF*F(current_time-cache[heap[child]].last_ref_time)) break;
else {
if((cache[rootkey].CRF*F(current_time-cache[rootkey].last_ref_time)
cache[heap[child]].CRF*F(current_time-cache[heap[child]].last_ref_time) ||
cache[rootkey].last_ref_time cache[heap[child]].last_ref_time)) {
tmp1 = heap[(child-1)/2];
tmp2 = cache[tmp1].heap_i;
cache[heap[(child-1)/2]].heap_i = cache[heap[child]].heap_i;
heap[(child-1)/2] = heap[child];
child = 2*child+1;
cache[heap[(child-1)/2]].heap_i = tmp2;
heap[(child-1)/2] = tmp1;
}
else break;
}
}
}
void heapUp(int n, int current_time){
int child;
int tmp1, tmp2, rootkey;
child = n;
for(rootkey = (child-1)/2 ; rootkey = 1; rootkey /= 2){
if(cache[heap[rootkey]].CRF*F(current_time-cache[heap[rootkey]].last_ref_time) =
cache[heap[child]].CRF*F(current_time- cache[heap[child]].last_ref_time)){
if(cache[heap[rootkey]].CRF*F(current_time-cache[heap[rootkey]].last_ref_time)
cache[heap[child]].CRF*F(current_time- cache[heap[child]].last_ref_time) ||
cache[heap[rootkey]].last_ref_time cache[heap[child]].last_ref_time) {
tmp1 = heap[rootkey];
tmp2 = cache[tmp1].heap_i;
cache[tmp1].heap_i = cache[heap[child]].heap_i;
heap[rootkey] = heap[child];
cache[heap[child]].heap_i = tmp2;
heap[child] = tmp1;
}
child = rootkey;
}
else break;
}
}

7. 실행 예제는 다음과 같습니다.

$ ./a.out 1.0 3000 19999 input.txt
LRFU cache miss count : 15297$ ./a.out 0.0 3000 19999 input.txt
LRFU cache miss count : 15144
form style=MARGIN: 0px name=tagForm onsubmit=javascript:oCafeTagRead.updateArticleTag() method=postinput type=hidden value=10026632 name=clubid / input type=hidden value=218651 name=articleid / input type=hidden value=15 name=menuid / /form

신청하기