LRU LFU FIFO 페이지 교체 알고리즘

Recent Posts

Today

Total

Recent Comments

관리 메뉴

develop

LRU LFU FIFO 페이지 교체 알고리즘 본문

Algorithm

LRU LFU FIFO 페이지 교체 알고리즘

pikachu987 2021. 1. 22. 20:09

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

1. LRU(Least Recently Used)

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

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

class LRU<K: Hashable, V: NSObject> {
    
    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<String, NSData>(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<K: Hashable, V: NSObject> {
    
    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<String, NSData>(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<K: Hashable, V: NSObject> {
    
    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<String, NSData>(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 }
]

Comments

develop

LRU LFU FIFO 페이지 교체 알고리즘 본문

LRU LFU FIFO 페이지 교체 알고리즘

1. LRU(Least Recently Used)

2. LFU(Least Frequently Used)

3. FIFO(First In First Out)

티스토리툴바