INTRO 페이지 교체 알고리즘에는 다양한 알고리즘이 있다. FIFO, LFU, Count-Base ... 이 중 LRU 알고리즘에 대해 소개한다. ◆ 가장 오랜 시간 사용되지 않은 페이지를 교체하는 운영체제의 페이지 교체 정책 알고리즘이다. ◆ 주로 캐시에서 메모리를 다루기 위해 사용된다. ◆ 캐시는 크게 보면 웹 서비스부터, 작게는 CPU가 RAM이나 Disk에 접근할 때.. 등 광범위하게 사용됨. ◆ 이러한 캐시들은 자원이 한정되어있으며, 한정된 자원 내에서 빠르게 데이터 접근이 가능해야 한다. ◆ 따라서 어떤 데이터를 남기고, 어떤 데이터를 지울지에 대한 알고리즘이 필요. ◆ 여기서 오래 참조되지 않은 데이터는 내보내는 '시간(temporal) 지역성'의 성질을 가지는 알고리즘이다. ◆ LRU는 아래와 같은 장/단점을 가진다. 장점 - 빠른 액세스 가장 최근에 사용한 아이템부터 가장 적게 사용한 아이템까지 정렬된다. 따라서 두 아이템에 접근할 경우, O(n)의 시간 복잡도를 가진다. - 빠른 Update 하나의 아이템에 엑세스 할때마다 업데이트 되며, O(n)의 시간 복잡도를 가진다. 단점 - 많은 공간 차지 n개의 아이템을 저장하는 LRU는 n의 크기를 가지는 1개의 Linked-list와(혹은 Queue) 이를 추적하기 위한 n의 크기를 가지는 1개의 hash-map이 필요하다. 이는 O(n)의 복잡도를 가지지만, 2개의 데이터구조를 사용해야 한다는 단점이 있다. ◆ 아래와 같은 3개의 공간을 가진 Queue가 있다. ◆ 1 -> 2 -> 3을 차례로 삽입(put)했을 경우 ◆ 2를 참조(get)한 경우 ◆ 4를 put 한 경우 ◆ 예제 소스는 아래 링크에서 참조하였다. ◆ 주석 부분을 참고하면 좋을 듯 하다. https://www.geeksforgeeks.org/lru-cache-implementation/ LRU Cache Implementation - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions. www.geeksforgeeks.org 마무리 캐싱이 필요한 다양한 곳에서 사용되는 알고리즘이므로 한번 쯤 알아두는것이 좋을 것 같다. 추가적으로 다른 캐시 알고리즘들에 대해서도 다룰 예정 -퍼가실 때는 출처를 꼭 같이 적어서 올려주세요! - 컴퓨터의 자원은 한정적이며, 한도내에서 최고의 효율을 얻기 위해 여러 알고리즘이 존재, 그 중에 하나. 두번째 : 페이지에 데이터를 큐 형식으로 저장하는 방식. 존재하지 않는다면, 바로 입력하여 맨 아래에 있는 데이터를 삭제하는 과정을 진행. 나머지 상황들이 존재하지 않을때 새로 교체 됨으로 Cache Miss 라고한다. 코딩테스트 연습 - [1차] 캐시 3 ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"] 50 3 ["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"] 21 2 ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Ro programmers.co.kr 운영체제 페이지 교체 알고리즘 FIFO, LFU, LRU처음에 참조 스트링에 1이 있고 페이지 프레임도 4개가 존재한다. 모든 프레임에 1이 없고 비어있기 때문에 첫 번째 프레임에 1을 넣어주고 F를 표시한다. 그 다음 2와 6도 1(첫번 째)과 마찬가지로 두 번째 세 번째 프레임에 각각 2와 6을 넣어준다. 이 또한 프레임에 data가 존재하지 않았으므로 F를 표시해준다 다시 1을 참조할 때 첫 번째 프레임에 1이 존재하므로 다음으로 넘어간다. 4도 마찬가지로 프레임에 4가 없고 네 번째 프레임이 비었으므로 4를 넣어주고 F를 표시한다. 다음으로 5가 왔을 때 프레임이 모두 꽉 차있으므로 프레임을 지우고 5를 넣어주어야 한다. 여기에서는 FIFO(선입 선출)를 사용하기 때문에 1대신에 5를 넣어준다.(1이 가장 먼저 들어왔기 때문에 1대신 5를 넣어준다) 그리고 5가 프레임에 존재하지 않았으므로 다시 F를 체크해준다. 이러한 방식으로 계속해서 프레임을 체크해주고 위와 같은 결과가 나타나게 된다. *참고) LRU , LFU 표 수정하고싶은데 게시글이 오래되서 원본이 사라지고 없어요ㅜㅜ 아래 제가 설명 써놓은거 보고 다시 표 그리면서 확인하시는게 더 빠를 것 같아요!! LFU는 가장 적은 참조횟수를 갖는 페이지를 교체 LRU는 가장 오랫동안 참조되지 않은 페이지를 교체 처음에 참조 스트링에 1이 있고 페이지 프레임도 4개가 존재한다. 모든 프레임에 1이 없고 비어있기 때문에 첫 번째 프레임에 1을 넣어주고 F를 표시한다. 그 다음 2와 6도 마찬가지로 두 번째 세 번째 프레임에 각각 2와 6을 넣어준다. 이 또한 프레임에 data가 존재하지 않았으므로 F를 표시해준다 다시 1을 참조할 때 첫 번째 프레임에 1이 존재하므로 다음으로 넘어간다. 4도 마찬가지로 프레임에 4가 없고 네 번째 프레임이 비었으므로 4를 넣어주고 F를 표시한다. 그 다음 5가 오는데 LFU는 가장 적은 참조횟수를 갖는 페이지를 교체하기 때문에 두 번째 프레임에 5가 들어간다. (첫 번째 프레임은 4초에 한번 더 참조되었다.) 2,3,4 프레임 모두 한번씩 참조되었기 때문에 2프레임부터 순서대로 들어가게 된다. 따라서 2프레임에 5가 들어간다. 위와 같은 방법으로 가장 적은 참조가 된 순서대로 페이지를 교체한다. 처음에 참조 스트링에 1이 있고 페이지 프레임도 4개가 존재한다. 모든 프레임에 1이 없고 비어있기 때문에 첫 번째 프레임에 1을 넣어주고 F를 표시한다. 그 다음 2와 6도 마찬가지로 두 번째 세 번째 프레임에 각각 2와 6을 넣어준다. 이 또한 프레임에 data가 존재하지 않았으므로 F를 표시해준다 다시 1을 참조할 때 첫 번째 프레임에 1이 존재하므로 다음으로 넘어간다. 4도 마찬가지로 프레임에 4가 없고 네 번째 프레임이 비었으므로 4를 넣어주고 F를 표시한다. 그 다음 5가 오는데 LRU는 오랫동안 참조되지 않은 페이지를 교체하기 때문에 두 번째 프레임에 5를 대입한다. (첫 번째 프레임은 4초에 참조되어있기 때문에 두 번째 프레임(가장 오래됨)이 바뀌게 된다) 이 다음도 이와 같은 방법으로 가장 오래된 프레임을 바꾸어 준다. |
LRU 알고리즘 예시 - LRU algolijeum yesi
저작권 © 2024 toptenid.com Inc.
