Wonny

Cache Memory

 Cache 메모리는 매우 빠른 메모리를 가리킨다. Cache memory는 속도를 빠르게 하기 위해 사용되고, 빠른 속도의 CPU와 동기화하기 위해 사용된다. 컴퓨터에도 캐시 메모리가 있는데, 컴퓨터에서 캐시 메모리는 RAM과 CPU의 버퍼 용도로 사용된다. 캐시 메모리는 CPU가 필요할 때 즉각적으로 처리해주기 위해 자주 사용되는 데이터와 명령어들을 들고 있는다. 

 참고로 컴퓨터에는 아래와 같이 Cache 메모리 말고도 다른 메모리들도 있다. 

 피라미드의 위로 갈 수록 비용이 비싸고 공간이 작으며 속도가 빠르고, 피라미드의 아래로 갈 수록 비용이 저렴하고 공간이 크며 속도가 느리다.

Cache Memory Paging 원리

 이 Cache Memory라는 친구는 앞으로 또 접근할 것 같은 데이터를 예측하여 가지고 있어야 한다. 다시 말해서 캐시 메모리에서는 자주 사용되는 메모리를 가지고 있어야 한다.

 그런데 지금까지 접근한 데이터로 앞으로 사용할 데이터를 예측할 수 있을까? 

 -> 할 수 있다. 그 이유는 Memory의 Locality라는 특성 때문인데, 이 Locality는 지금까지 방문했던 메모리 공간을 또 방문할 확률이 높다는 것이다. 

 그래서 이 Locality라는 특성 때문에 지금까지 방문했던 메모리를 또 방문할 확률이 높다고 예측할 수 있고, 방문했던 메모리를 캐시에 담아두어서 또 접근할 때 빠르게 접근할 수 있도록 해주는 것이다. 

LRU Cache

 LRU는 Least Recenty Used의 약자로, 여러 페이징 알고리즘 중 하나다. LRU는 캐시 메모리를 다루는 알고리즘 중 많이 사용되는 알고리즘이다. 원리는 간단한데, 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘이다. 즉 LRU 또한 과거에 자주 쓰이지 않은 페이지들을 앞으로도 잘 쓰이지 않을 것이니 빼도 된다는 개념이다. 

 아래 사진을 보면 쉽게 이해가 된다.

 초기 큐에는 1, 2, 3이 있다. 그리고 여기서 새로운 값인 4가 들어왔을 때 큐의 top이 pop되고, 새로운 값 4가 push된다. 그 다음에 1이 들어오면 top에 있는 2가 pop되고, 1이 push된다.

 Hit가 나는 경우를 확인해보자. 큐에 1, 2, 5가 있을 때, 1이 들어오면 top에 있던 1이 맨 아래로 내려간다. 필기에도 적어두었지만 새로 값이 들어온 것처럼 순서를 바꿔주는 것이다. 이런식으로 Queue를 이용한 LRU Cache의 페이징 알고리즘이 작동한다. 

C언어 코드

#include <string.h>
#include <stdlib.h>
#define FALSE 0
#define TRUE 1

void move(int newVal);
int chkHit(int n);
void setNum(int n);

int* frameList;
int frameSize= 0;
int curNum = -1;
int curPos = -1; // 새로 들어온 값이 list에 어느 위치에 있는지 position

int temp = 0;
int main() {
	char buffer[128];
	int readCnt = 0;
	int writeCnt = 0;
	int fCnt = 0; // frame cnt
	int hitCnt = 0;
	int faultCnt = 0;
	FILE *fp = NULL;
	fp = fopen("access.list", "r");
	
	scanf("%d", &frameSize);

	frameList = (int*)malloc(sizeof(int)* frameSize);//frame

	if (fp != NULL) {
		while (!feof(fp)) { // 파일 읽기 시작
			fgets(buffer, sizeof(buffer), fp);
			char* ptr = strtok(buffer, " ");
			
			while (ptr != NULL) {
				//printf("%s \n", ptr);

				if (ptr[0] >= '0'&& ptr[0] <= '9') {//숫자라면
					fCnt++;
					curNum = atoi(ptr); // 현재 숫자
					temp++;
				}
				else if (ptr[0] == 'r') { // read라면
					readCnt++;
					if (chkHit(curNum)) {
						move(curNum); 
						hitCnt++;
					}
					else {
						move(curNum);
						faultCnt++;
					}
				}
				else if (ptr[0] == 'w') { // write라면
					writeCnt++;
					if (chkHit(curNum)) {
						move(curNum);
						hitCnt++;
					}
					else {
						move(curNum);
						faultCnt++;
					}
				}

				ptr = strtok(NULL, " ");
			}
		}
	}
	else {
		printf("null");
	}

	printf("Total number of access: %d\n", readCnt+writeCnt);
	printf("Total number of read: %d\n", readCnt);
	printf("Total number of write: %d\n", writeCnt);
	printf("Number of page hits: %d\n", hitCnt);
	printf("Number of page faults: %d\n", faultCnt);
	printf("Page fault rate: %d/%d = %.3f %%", faultCnt, readCnt+writeCnt, (double)faultCnt / ((double)readCnt + (double)writeCnt) * 100);

	fclose(fp);
	return 0;
}

int chkHit(int n) {
	int i = 0;
	for (i = 0; i < frameSize; i++) {
		if (frameList[i] == n) {
			curPos = i; // 현재 위치 저장
			//printf("%d %d %d\n",temp, i, n);
			return TRUE;
		}
	}
	curPos = 0;
	return FALSE;
}

void move(int newVal) {
	int i = 0;
	for (i = curPos; i < frameSize - 1; i++) {
		frameList[i] = frameList[i + 1];
	}
	frameList[frameSize - 1] = newVal;
}