[운영체제] 연결리스트를 이용한 LRU 알고리즘 만들기

https://julian5383.tistory.com/75?category=926879 

[운영체제] 연결리스트를 이용한 FIFO 알고리즘 만들기

위의 게시물에서 이어집니다.

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

typedef struct node
{
	int num;
	struct node* next;
	clock_t time;
}NODE;

NODE* head;
NODE* tail;

void init()
{
	head = (NODE*)malloc(sizeof(NODE));
	tail = (NODE*)malloc(sizeof(NODE));

	head->next = tail;
	tail->next = tail;
}

NODE* c_time() {
	NODE* p = head->next;
	NODE* s = p->next;
	NODE* tmp = s;
	clock_t start = clock();

	double time1, time2;
	while (s != tail)
	{
		time1 = (double)(start - tmp->time);
		time2 = (double)(start - s->time);

		if (time1 < time2)
		{
			tmp = s;
		}
		p = p->next;
		s = p->next;
	}
	return tmp;
}

void insert(int num)
{
	NODE* p = malloc(sizeof(NODE));
	NODE* in_head = head;
	NODE* in_node = in_head->next;
	p->num = num;

	if (head->next == tail)
	{
		p->next = tail;
		head->next = p;
	}
	else
	{
		while (in_node != tail)
		{
			in_head = in_head->next;
			in_node = in_head->next;
		}
		in_head->next = p;
		p->next = in_node;
	}
}

void delete(int num)
{
	NODE* in_head = head;
	NODE* in_node = in_head->next;
	NODE* tmp;
	NODE* new = (NODE*)malloc(sizeof(NODE));
	new->num = num;

	tmp = c_time(head, tail);

	if (in_node != tmp)
	{
		in_head = in_head->next;
		in_node = in_head->next;
	}
	in_head->next = new;
	new->next = in_node->next;
	new->time = clock();
	free(in_node);
}

int search(int num)
{
	NODE* p = head->next;
	while (p != tail)
	{
		if (p->num == num)
		{
			return 1;
		}
		p = p->next;
	}
	return 0;
}

int length_list()
{
	int length = 0;
	NODE* p = head->next;
	while (p != tail)
	{
		p = p->next;
		length++;
	}
	return length;
}

int main()
{
	FILE* fp = NULL;
	int i, num, nc = 0;
	int arr[100000];
	int hit = 0;
	int node;

	init();

	printf("1: tr.2c39.txt\n");
	printf("2: tr.db2.txt\n");
	printf("3: tr.sort.txt\n");
	printf("4: r.zipf_20_80.txt\n");
	printf("Input file name's(1,2,3,4 only): ");
	scanf("%d", &i);

	printf("Input Node Number(100, 500, 1000 only) : ");
	scanf("%d", &node);

	switch (i)
	{
	case 1:
		fp = fopen("tr.2c39.txt", "r");
		break;
	case 2:
		fp = fopen("tr.db2.txt", "r");
		break;
	case 3:
		fp = fopen("tr.sort.txt", "r");
		break;
	case 4:
		fp = fopen("tr.zipf_20_80.txt", "r");
		break;
	default:
		printf("Error\n");
		break;
	}

	while (fscanf(fp, "%d", &num) > 0) {
		nc++;

		if (search(num)) {
			hit++;
		}

		else
		{
			while (1)
			{
				if (length_list() < node)
				{
					insert(num);
					break;
				}
				else
				{
					delete(num);
					break;
				}
			}
		}

	}

	fclose(fp);
	printf("Hit rate: %.2f\n", ((double)hit / (double)nc) * (double)100);
	return 0;
}

구현한 FiFO 페이지 교체 알고리즘의 성능(hit rate)을 주어진 트레이스 파일을 이용하여 측정하시오.

1. trace: tr.2c39

노드 수	replacement algorithms
	FIFO	LRU
100	15.81	9.02
500	24.41	16.44
1,000	25.69	17.46

2. trace: tr.db2

노드 수	replacement algorithms
	FIFO	LRU
100	38.82	13.72
500	57.32	28.77
1,000	62.49	34.89

3. trace: tr.sort

노드 수	replacement algorithms
	FIFO	LRU
100	34.55	35.57
500	36.71	41.65
1,000	44.62	48.75

4. trace: tr.zipf_20_80

노드 수	replacement algorithms
	FIFO	LRU
100	27.81	28.13
500	36.82	39.52
1,000	41.61	44.26