Linux의 캐싱 메커니즘에 대한 심층적 논의: 대체 알고리즘 및 성능 최적화 전략에 대한 자세한 설명

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int key;
    int value;
    struct Node* prev;
    struct Node* next;
} Node;

typedef struct LRUCache {
    int capacity;
    int size;
    Node* head;
    Node* tail;
} LRUCache;

LRUCache* createCache(int capacity) {
    LRUCache* cache = (LRUCache*)malloc(sizeof(LRUCache));
    cache->capacity = capacity;
    cache->size = 0;
    cache->head = (Node*)malloc(sizeof(Node));
    cache->tail = (Node*)malloc(sizeof(Node));
    cache->head->prev = NULL;
    cache->head->next = cache->tail;
    cache->tail->prev = cache->head;
    cache->tail->next = NULL;
    return cache;
}

void deleteNode(LRUCache* cache, Node* node) {
    node->next->prev = node->prev;
    node->prev->next = node->next;
    free(node);
}

void addToHead(LRUCache* cache, Node* node) {
    node->next = cache->head->next;
    node->prev = cache->head;
    cache->head->next->prev = node;
    cache->head->next = node;
}

int get(LRUCache* cache, int key) {
    Node* node = cache->head->next;
    while (node != cache->tail) {
        if (node->key == key) {
            // hit, move to head
            node->prev->next = node->next;
            node->next->prev = node->prev;
            addToHead(cache, node);
            return node->value;
        }
        node = node->next;
    }
    return -1; // cache miss
}

void put(LRUCache* cache, int key, int value) {
    Node* node = cache->head->next;
    while (node != cache->tail) {
        if (node->key == key) {
            // hit, update value and move to head
            node->value = value;
            node->prev->next = node->next;
            node->next->prev = node->prev;
            addToHead(cache, node);
            return;
        }
        node = node->next;
    }
    if (cache->size >= cache->capacity) {
        // cache is full, remove least recently used item
        Node* tailNode = cache->tail->prev;
        tailNode->prev->next = cache->tail;
        cache->tail->prev = tailNode->prev;
        free(tailNode);
        cache->size--;
    }
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->value = value;
    addToHead(cache, newNode);
    cache->size++;
}

int main() {
    LRUCache* cache = createCache(3);
    put(cache, 1, 100);
    put(cache, 2, 200);
    put(cache, 3, 300);
    printf("%d
", get(cache, 2)); // Output: 200
    put(cache, 4, 400);
    printf("%d
", get(cache, 1)); // Output: -1
    printf("%d
", get(cache, 3)); // Output: 300
    printf("%d
", get(cache, 4)); // Output: 400
    return 0;
}