[CS][OS] Paging Algorithm - Cache

오늘은 페이징 알고리즘에 대해 포스팅을 할 생각이다.

특히, 가장 많이 쓰이는 LRU는 어떤 자료 구조를 사용하고 구현은 어떠한식으로 되는지를
2018년도 카카오 블라인드 채용 코딩테스트 문제 를 보고 확인 해 볼 생각이다.

페이징 알고리즘

우선 페이징 알고리즘이 뭔지 알아볼 필요가 있다.
운영체제는 프로세스를 메모리에 적재할 때 프로세스를 프로세스 통째로 메모리에 올리지 않는다.
논리적인 주소에 최대한 연속적으로 할당하면서 외부 단편화같은 Critical 한 낭비를 막기 위해
Page라는 특정 크기로 프로세스를 나누어 적재하게 된다.

결국, 캐시나 레지스터 등등의 메모리는 영역을 전부 쓰여지거나 당장 빼서 영역을 활용 해야 할 때가 존재하는데 이럴 경우 적재된 프로세스의 페이지들을 정리하는 알고리즘을 페이징 알고리즘 라고 한다.

오늘 소개할 알고리즘은 크게 3개다.

1. FIFO(First In First Out)
2. OPT
3. LRU(Least-Recently-Used)

차례 대로 살펴보자.

FIFO

First In First Out 메모리에 먼저 올라온 페이지를 먼저 내보내는 알고리즘

가장 먼저 빠지게 되는 페이지는, 가장 먼저 메모리에 올라온 페이지가 된다.

가장 간단한 알고리즘으로, 특히 초기화 코드에서 적절한 방법이다.(딱히 언제 들어왔는지에 대해 신경 쓰지 않아도 되는 유일한 순간이기 때문이다.)

초기화 코드 : 처음 프로세스 실행될 때 최초 초기화를 시키는 역할만 진행하고 다른 역할은 수행하지 않으므로, 메인 메모리에서 빼도 괜찮음

하지만 처음 프로세스 실행시에는 무조건 필요한 코드이므로, FIFO 알고리즘을 사용하면 초기화를 시켜준 후 가장 먼저 내보내는 것이 가능함

OPT

앞으로 가장 사용하지 않을 페이지를 내보내는 방식

사실상 가장 이상적인 페이지 교체 알고리즘이다.
FIFO에 비해 다 동작시키지 못하는 해저드나, 페이지 결함의 횟수를 줄여주는데 좋다.

하지만 설명으로 써놨던 앞으로 가장 사용하지 않는 페이지라는 어떠한 특정한 기준치는,
명확한 증거로 작용하여 내놓을 페이지를 결정할수 없다는 점에 있다.

실제 구현한다면 가장 효율적이겠으나, 사실상 불가능에 가까운 알고리즘이다.

LRU

가장 최근에 사용하지 않은 페이지를 내보내는 방식이다.

현재 가장 많이 쓰이고 있는 페이지 교체 알고리즘이다.
전체적인 큰 틀은 Queue와 같지만 FIFO 구조 에서 가지고 있던 결함 횟수를 줄여주는데다, Cache에서 사용할 경우 Cache Hit을 통해 자원 절약 효과를 얻을수 있다.

OPT처럼 미래를 예측하여 어떠한 페이지를 교체할지 결정하지 않는다.
보유한 페이지의 과거 기록을 대조하여 cache hit을 시키거나 불필요한 데이터 버스의 동선낭비를 줄여주는 역할을 할수 있다.

실제로 카카오 2018 공채에서도 캐시 라는 문제로 출제가 되었었다.

실제 이를 위하여 필요한 자료구조는 세가지다.

1. Double Linked List
2. Hash Map
3. Queue

큐 자체를 DLL(Double Linked List)로 구현하고 실제 들어갈 위치를 Hash Map에 기록해둔뒤, 필요할 때마다 Map에서 값의 변화상태를 기록하며 큐를 확장해 나간다면,
모든 과정에서 시간복잡도 O(1) 의 결과를 얻을수 있게된다.

논리적인 플로우는 다음과 같다.

• Cache 크기만큼 채웠는지 확인한다.
• 만약 다 채웠다면 LRU규칙에 따라 가장 오랫동안 쓰이지 않은 페이지를 제거 하여 교체하거나, Cache Hit일 경우 해당 부분만 빼내어 큐에 다시 집어넣는다.
• Cache 사이즈를 다 채우지 못한경우, Cache Hit일때는 Hit된 부분만을 뒤로 보내고, 아닐 경우 LRU규칙에 따라 가장 오랫동안 쓰이지 않은 페이지를 버린다.

이것을 그대로 구현한 코드는 아래와 같다.

class Node {
    var str : String
    var next : Node?
    var prev : Node?
    init() {
        str = ""
        self.next = nil; self.prev = nil
    }
    init(_ str: String, _ prev : Node?, _ next: Node?) {
        self.str = str
        self.prev = prev
        self.next = next
    }
    func pop() {
        if prev != nil {
            prev?.next = next
        }
        if next != nil {
            next?.prev = prev
        }
    }
}

func solution(_ cacheSize:Int, _ cities:[String]) -> Int {
    var map : [String : Node] = [String: Node]()
    var head : Node = Node()
    var tail : Node = Node("", head, nil)
    
    if cacheSize == 0 {
        return cities.count * 5
    }
    
    var LRUQueueLen = 0
    var ans = 0
    for c in cities {
        let city = c.uppercased()
        var node : Node = Node(city, nil, nil)
        
        // 큐가 다 차기 전까진 일단 다 넣는다.
        if LRUQueueLen < cacheSize {
            if let v = map[city] {// 하지만 만약 캐시 큐에 존재한다면? HIT!
                v.pop()
                v.next = tail
                v.prev = tail.prev
                map[city] = v
                
                tail.prev?.next = v
                tail.prev = v
                ans += 1
            }else{//캐시 큐에 존재하지 않으면! MISS!
                node.next = tail
                node.prev = tail.prev
                map[city] = node
                
                tail.prev?.next = node
                tail.prev = node
                LRUQueueLen += 1
                ans += 5
            }
        }else{// 큐가 다 찼다면!!
            if let v = map[city] {// 만약 이미 나왔던 것일 경우, 1. 현재 큐에 있거나, 2. 큐에 없거나 <- pop하면 양 옆이 nil임..
                if v.next == nil, v.prev == nil {
                    let cit: String = head.next?.str ?? ""
                    head.next?.pop()
                    map[cit] = Node(cit, nil, nil)
                    
                    node.next = tail
                    node.prev = tail.prev
                    map[city] = node
                    
                    tail.prev?.next = node
                    tail.prev = node
                    ans += 5//캐시 미스
                }else{
                    // 이미 존재하는 경우에 대해!
                    v.pop()
                    v.next = tail
                    v.prev = tail.prev
                    map[city] = v
                    
                    tail.prev?.next = v
                    tail.prev = v
                    ans += 1
                }
            }else{
                let cit: String = head.next?.str ?? ""
                head.next?.pop()
                map[cit] = Node(cit, nil, nil)
                
                node.next = tail
                node.prev = tail.prev
                map[city] = node
                
                tail.prev?.next = node
                tail.prev = node
                ans += 5//캐시 미스
            }
        }
    }
    return ans
}

실제 문제에서 주어진 cacheSize의 크기가 굉장히 작아서 크게 속도적인 부분에서의 느끼는 체감상 크기는 달라지지 않았지만, 처음 큐 하나만으로 별다른 작업 없이 만든 코드에 비해 속도 개선이 된 것을 확인할수 있었다.