LFU 알고리즘 구현 - LFU algolijeum guhyeon

Question

가상 메모리 기법을 구현하는 방식 중 하나인 요구 페이징 방식은 페이지 부재가 발생하게 됩니다. 페이지를 교체하는 작업은 오버헤드를 동반하므로 가능하면 페이지 교체가 적게 일어나도록 하는 것이 좋습니다. 페이지 교체가 무엇인지,

목차 Show

페이지 교체
페이지 교체 알고리즘
1. LRU(Least Recently Used)
2. LFU(Least Frequently Used)
3. FIFO(First In First Out)

페이지 교체

페이지 부재(page fault)가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야 합니다. 이때 물리적 메모리에 빈 프레임이 존재하지 않을 수 있습니다. 이 경우 물리적 메모리에 올라와 있는 페이지 중 하나를 선택해서 디스크의 스왑 영역으로 보내야 합니다. 이와 같은 과정을 페이지 교체라고 합니다.

페이지 교체 알고리즘

어떠한 프레임에 있는 페이지를 디스크의 스왑 영역으로 보낼 것인지를 결정하는 알고리즘을 교체 알고리즘이라고 합니다. 이 알고리즘의 목표는 페이지 부재율을 최소화 하는 것입니다. 그러므로 가까운 미래에 참조될 가능성이 가장 적은 페이지를 선택해서 내보내는 것이 성능을 향상 시킬 수 있는 방안이 될 것입니다.

선입선출 알고리즘(FIrst In First Out: FIFO)

페이지 교체 시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내보내는 알고리즘입니다. 페이지의 향후 참조 가능성을 고려하지 않기 때문에 비효율적인 상황이 발생할 수 있습니다.

아래 그림은 3개의 페이지 프레임을 가질 경우 9번의 페이지 부재와 3번의 페이지 히트가 발생했습니다.

이번엔 페이지 프레임을 4개로 증가 시켰을 때의 과정입니다.

10번의 페이지 부재와 2번의 페이지 히트가 발생했습니다.

분명 페이지 프레임을 더 많이 사용하는데 오히려 페이지 부재 횟수가 증가하는 이상현상이 나타났습니다.

선입선출 알고리즘에서 메모리를 증가해도 페이지 부재가 더 증가하는 FIFO의 이상 현상(FIFO abnomaly)이 발생할 수 있습니다.

LRU 알고리즘 (Least Recently Used Algorithm)

페이지 교체 알고리즘의 성능 향상을 위해선 앞으로 사용 가능성이 낮은 페이지를 우선적으로 내보내는 것이 좋다. 이와 관련해서 시간 지역성이라는 성질이 있다. 시간 지역성은 최근에 참조된 페이지가 미래에 다시 참조될 가능성이 높은 성질을 말한다. LRU 알고리즘은 이와 같은 성질을 활용해서 페이지 교체 시 가장 오래전에 참조가 이루어진 페이지를 내보낸다.

LRU 알고리즘을 사용하니 8번의 페이지 부재와 4번의 페이지 히트가 발생했습니다. FIFO 알고리즘에 비해 페이지 부재 횟수가 감소 했음을 알 수 있습니다.

LFU 알고리즘 (Least Frequently Used Algorithm)

물리적 메모리 내에 존재하는 페이지 중에서 과거에 참조 횟수가 가장 적은 페이지를 교체 시킬 페이지로 결정하는 알고리즘입니다. LFU 알고리즘은 크게 2가지로 나뉘어집니다.

Incache-LFU: 메모리에 적재될 때부터 페이지의 횟수를 카운트 하는 방식
Perfect-LFU: 메모리 적재 여부와 상관 없이 페이지의 과거 총 참조 횟수를 카운트 하는 방식

(Perfect-LFU의 경우 정확하게 참조 횟수를 참조할 수 있지만 시간에 따른 참조의 변화를 반영하지 못하고, 구현이 복잡하다는 단점이 있습니다.)

11번째로 5번을 참조 하려고 하면 페이지 폴트가 발생합니다. 이 때 LRU 알고리즘은 1번 페이지 프레임을 교체하게 됩니다. 이에 반해 LFU 알고리즘은 참조 횟수가 가장 적은 4번 페이지 프레임을 교체하게 됩니다.

1번 페이지가 오랫동안 쓰이지 않았지만 LFU 알고리즘은 참조 횟수가 가장 적은 4번 페이지를 교체 했습니다. 그러나 앞으로 4번 페이지가 계속 사용되는 페이지 일 수도 있습니다. 이처럼, LFU는 최신 흐름을 잘 반영하지 못할 수도 있습니다.

클럭 알고리즘 (NRU or NUR)

클럭 알고리즘은 하드웨어적인 자원을 통해 기존(LRU, LFU)알고리즘의 소프트웨어적인 운영 오버헤드를 줄인 방식입니다. NRU(Not Used Recently) 또는 NUR(Not Recently Used) 알고리즘이라고도 부르기도 합니다.

클럭 알고리즘은 LRU처럼 가장 최근에 참조되지 않은 페이지를 대상으로 선정한다는 점에서 LRU와 근사하지만 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 않는다.

클럭 알고리즘은 그림처럼 참조 비트(reference bit)를 순차적으로 조사하며 동작합니다.

1. 프레임 내의 페이지가 참조될 때 하드웨어에 의해 1로 자동 세팅됩니다.

2. 클럭 알고리즘은 한 바퀴 돌며 참조되지 않은 페이지의 참조 비트 값을 0으로 바꾼 후 지나갑니다.

3. 참조 비트가 0인 페이지를 방문하면 해당 페이지를 교체합니다.

즉, 페이지가 참조되어 1이 되고, 한 바퀴 도는 동안 사용되지 않으면 0이 되고 다시 한 바퀴를 도는 동안 사용되지 않는 페이지는 참조되지 않았으므로 교체 대상 페이지로 선정하는 알고리즘입니다.

클럭 알고리즘은 시계 바늘이 한 바퀴 도는 동안 걸리는 시간만큼 페이지를 메모리에 유지시켜 페이지 부재율을 줄이도록 설계 되었다. 때문에 클럭 알고리즘을 2차 기회 알고리즘이라 부르기도 한다.

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

You can’t perform that action at this time.

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.

페이지 교체 알고리즘은 메모리를 관리하는 운영체제에서 새로운 페이지를 할당하기 위해 현재 할당된 페이지중 어느 것과 교체할지를 결정하는 방법

1. LRU(Least Recently Used)

가장 오랫동안 참조되지 않은 페이지를 교체한다.

많은 운영체제가 사용하고 있는 알고리즘이고 좋은 알고리즘이라고 평가되고 있다.

class LRU {
    
    struct Node {
        let key: K
        var value: V?
        
        init(key: K, value: V?) {
            self.key = key
            self.value = value
        }
    }
    
    var description: String {
        if self.queue.isEmpty { return "[]" }
        var desc = self.queue.map({ " { key: \($0.key) },\n" }).reduce("", +)
        desc.removeLast(2)
        return "[\n\(desc)\n]"
    }
    
    let capacity: Int
    
    private var queue: [Node]
    
    init(capacity: Int) {
        self.capacity = capacity
        
        self.queue = [Node]()
    }
    
    subscript (key: K) -> V? {
        get {
            if let index = self.queue.firstIndex(where: { $0.key == key }) {
                let node = self.queue[index]
                self.queue.remove(at: index)
                self.queue.insert(node, at: 0)
                return node.value
            } else {
                return nil
            }
        }
        set {
            if let index = self.queue.firstIndex(where: { $0.key == key }) {
                var node = self.queue[index]
                node.value = newValue
                self.queue.remove(at: index)
                self.queue.insert(node, at: 0)
            } else {
                let node = Node(key: key, value: newValue)
                
                if self.queue.count < self.capacity {
                    self.queue.insert(node, at: 0)
                } else {
                    self.queue.removeLast()
                    self.queue.insert(node, at: 0)
                }
            }
        }
    }
}

let cache = LRU(capacity: 3)

class API {
    static func request(_ urlPath: String) -> NSData? {
        guard let url = URL(string: urlPath) else { return nil }
        return try? NSData(contentsOf: url)
    }
}

func load(_ urlPath: String) {
    cache[urlPath] = API.request(urlPath)
    print(cache.description)
}

@discardableResult
func get(_ urlPath: String) -> NSData? {
    let data = cache[urlPath]
    print(cache.description)
    return data
}

load("https://www.naver.com")
load("https://www.google.com")
load("https://www.youtube.com")
get("https://www.naver.com")
load("https://www.instagram.com")
load("https://www.facebook.com")
get("https://www.youtube.com")
load("https://www.google.com")

[
 { key: https://www.naver.com }
]
[
 { key: https://www.google.com },
 { key: https://www.naver.com }
]
[
 { key: https://www.youtube.com },
 { key: https://www.google.com },
 { key: https://www.naver.com }
]
[
 { key: https://www.naver.com },
 { key: https://www.youtube.com },
 { key: https://www.google.com }
]
[
 { key: https://www.instagram.com },
 { key: https://www.naver.com },
 { key: https://www.youtube.com }
]
[
 { key: https://www.facebook.com },
 { key: https://www.instagram.com },
 { key: https://www.naver.com }
]
[
 { key: https://www.facebook.com },
 { key: https://www.instagram.com },
 { key: https://www.naver.com }
]
[
 { key: https://www.google.com },
 { key: https://www.facebook.com },
 { key: https://www.instagram.com }
]

2. LFU(Least Frequently Used)

가장 적은 횟수를 참조하는 페이지를 교체한다.

초기에 한 페이지를 계속 참조하다가 이후에 참조하지 않으면 초기에 사용된 참조횟수가 많아 메모리에 남아 있어 문제가 될 수 있다.

class LFU {
    
    struct Node {
        let key: K
        var value: V?
        var count: Int
        
        init(key: K, value: V?) {
            self.key = key
            self.value = value
            self.count = 0
        }
    }
    
    var description: String {
        if self.queue.isEmpty { return "[]" }
        var desc = self.queue.map({ " { key: \($0.key), count: \($0.count) },\n" }).reduce("", +)
        desc.removeLast(2)
        return "[\n\(desc)\n]"
    }
    
    let capacity: Int
    
    private var queue: [Node]
    
    init(capacity: Int) {
        self.capacity = capacity
        
        self.queue = [Node]()
    }
    
    subscript (key: K) -> V? {
        get {
            if let index = self.queue.firstIndex(where: { $0.key == key }) {
                self.queue[index].count += 1
                return self.queue[index].value
            } else {
                return nil
            }
        }
        set {
            if let index = self.queue.firstIndex(where: { $0.key == key }) {
                self.queue[index].count += 1
                self.queue[index].value = newValue
            } else {
                let node = Node(key: key, value: newValue)
                if self.queue.count < self.capacity {
                    self.queue.append(node)
                } else {
                    if let minimum = self.queue.min(by: { $0.count < $1.count })?.count,
                        let index = self.queue.firstIndex(where: { $0.count == minimum }) {
                        self.queue.remove(at: index)
                        self.queue.append(node)
                    }
                }
            }
        }
    }
}

let cache = LFU(capacity: 3)

class API {
    static func request(_ urlPath: String) -> NSData? {
        guard let url = URL(string: urlPath) else { return nil }
        return try? NSData(contentsOf: url)
    }
}

func load(_ urlPath: String) {
    cache[urlPath] = API.request(urlPath)
    print(cache.description)
}

@discardableResult
func get(_ urlPath: String) -> NSData? {
    let data = cache[urlPath]
    print(cache.description)
    return data
}

load("https://www.naver.com")
load("https://www.google.com")
load("https://www.youtube.com")
get("https://www.naver.com")
get("https://www.google.com")
load("https://www.google.com")
load("https://www.instagram.com")
load("https://www.facebook.com")
get("https://www.youtube.com")
load("https://www.google.com")

[
 { key: https://www.naver.com, count: 0 }
]
[
 { key: https://www.naver.com, count: 0 },
 { key: https://www.google.com, count: 0 }
]
[
 { key: https://www.naver.com, count: 0 },
 { key: https://www.google.com, count: 0 },
 { key: https://www.youtube.com, count: 0 }
]
[
 { key: https://www.naver.com, count: 1 },
 { key: https://www.google.com, count: 0 },
 { key: https://www.youtube.com, count: 0 }
]
[
 { key: https://www.naver.com, count: 1 },
 { key: https://www.google.com, count: 1 },
 { key: https://www.youtube.com, count: 0 }
]
[
 { key: https://www.naver.com, count: 1 },
 { key: https://www.google.com, count: 2 },
 { key: https://www.youtube.com, count: 0 }
]
[
 { key: https://www.naver.com, count: 1 },
 { key: https://www.google.com, count: 2 },
 { key: https://www.instagram.com, count: 0 }
]
[
 { key: https://www.naver.com, count: 1 },
 { key: https://www.google.com, count: 2 },
 { key: https://www.facebook.com, count: 0 }
]
[
 { key: https://www.naver.com, count: 1 },
 { key: https://www.google.com, count: 2 },
 { key: https://www.facebook.com, count: 0 }
]
[
 { key: https://www.naver.com, count: 1 },
 { key: https://www.google.com, count: 3 },
 { key: https://www.facebook.com, count: 0 }
]

3. FIFO(First In First Out)

페이지가 저장된지 가장 오래된 순으로 페이지를 교체한다.

페이지가 올라온 시간을 기록하거나 Queue에 저장하는 방식을 사용한다.

구현이 쉽지만 성능이 좋다고 할 수 없다.

활발하게 사용중인 페이지를 계속 교체한다면 실행속도가 느려질 위험이 있다.

class FIFO {
    
    struct Node {
        let key: K
        var value: V?
        
        init(key: K, value: V?) {
            self.key = key
            self.value = value
        }
    }
    
    var description: String {
        if self.queue.isEmpty { return "[]" }
        var desc = self.queue.map({ " { key: \($0.key) },\n" }).reduce("", +)
        desc.removeLast(2)
        return "[\n\(desc)\n]"
    }
    
    let capacity: Int
    
    private var queue: [Node]
    
    init(capacity: Int) {
        self.capacity = capacity
        
        self.queue = [Node]()
    }
    
    subscript (key: K) -> V? {
        get {
            if let index = self.queue.firstIndex(where: { $0.key == key }) {
                return self.queue[index].value
            } else {
                return nil
            }
        }
        set {
            if let index = self.queue.firstIndex(where: { $0.key == key }) {
                self.queue[index].value = newValue
            } else {
                let node = Node(key: key, value: newValue)
                if self.queue.count < self.capacity {
                    self.queue.append(node)
                } else {
                    self.queue.removeFirst()
                    self.queue.append(node)
                }
            }
        }
    }
}

let cache = FIFO(capacity: 3)

class API {
    static func request(_ urlPath: String) -> NSData? {
        guard let url = URL(string: urlPath) else { return nil }
        return try? NSData(contentsOf: url)
    }
}

func load(_ urlPath: String) {
    cache[urlPath] = API.request(urlPath)
    print(cache.description)
}

@discardableResult
func get(_ urlPath: String) -> NSData? {
    let data = cache[urlPath]
    print(cache.description)
    return data
}

load("https://www.naver.com")
load("https://www.google.com")
load("https://www.youtube.com")
get("https://www.naver.com")
get("https://www.google.com")
load("https://www.google.com")
load("https://www.instagram.com")
load("https://www.facebook.com")
get("https://www.youtube.com")
load("https://www.google.com")

[
 { key: https://www.naver.com }
]
[
 { key: https://www.naver.com },
 { key: https://www.google.com }
]
[
 { key: https://www.naver.com },
 { key: https://www.google.com },
 { key: https://www.youtube.com }
]
[
 { key: https://www.naver.com },
 { key: https://www.google.com },
 { key: https://www.youtube.com }
]
[
 { key: https://www.naver.com },
 { key: https://www.google.com },
 { key: https://www.youtube.com }
]
[
 { key: https://www.naver.com },
 { key: https://www.google.com },
 { key: https://www.youtube.com }
]
[
 { key: https://www.google.com },
 { key: https://www.youtube.com },
 { key: https://www.instagram.com }
]
[
 { key: https://www.youtube.com },
 { key: https://www.instagram.com },
 { key: https://www.facebook.com }
]
[
 { key: https://www.youtube.com },
 { key: https://www.instagram.com },
 { key: https://www.facebook.com }
]
[
 { key: https://www.instagram.com },
 { key: https://www.facebook.com },
 { key: https://www.google.com }
]

LFU 알고리즘 예제 LFU 알고리즘 OPT 알고리즘 구현 FIFO 알고리즘 구현