[페이지교체알고리즘] 자리를 양보해가며!

문제

라이캣과 자바독이 배에 타고 보니 좌석이 3개밖에 없었습니다.

가장 먼저 탄 사람이 당연히 앉아야지!

아니, 가장 키가 큰 사람이 앉아야지!

아니, 가장 덩치가 큰 사람이 앉아야지!

사람들이 수근 거릴 때, 개리가 말했습니다.

모두 알고리즘 보물을 찾으러 가는 것이 아닌가!? 개굴! 그러니 모두 알고리즘 문제로 승부를 봅시다. 개굴!

그때 라이캣이 손을 들었습니다.

주목해주냥! 내게 좋은 아이디어가 있다냥!

 

1. 다리가 아픈 동물들이 순서대로 들어온다.
2. 동물들의 종류는 다음과 같다.  : 무척추동물, 척추동물, 어류, 양서류, 파충류, 조류, 포유류
3. 동물들의 '종'이 같을 경우 무릎에 앉을 수 있다. 다 회복된 동물들은 언제든지 빠질 수 있다. 무릎에 앉을 경우 1초로 카운트 한다!
4. 아무도 없거나, 자리가 꽉 차 있을 때 '이 종'이 들어올 경우 가장 오래 앉아있던 동물이 아닌, 가장 최근에 같은 종이 한 번도 들어오지 않은 '종'이 나가게 된다. 이때 자리를 깨끗하게 청소해야 해서 1분이 걸린다.
5. 동물(페이지)들이 아래와 같이 차례대로 들어왔을 때 전체 수행 시간(실행 시간)을 구해야 한다.

여기서는 LRU(Least Resently Used) 알고리즘을 사용하겠다냥! LRU 알고리즘은 자리(페이지) 부재가 발생했을 경우 가장 오랫동안 사용되지 않은 자리(페이지)를 제거하는 알고리즘이다냥!

한마디로! 교체가 자주 이뤄지는 동물의 자리를 보존해주겠다는 것이다냥!

입력 :  페이지 = ['척추동물', '어류', '척추동물', '무척추동물', '파충류', '척추동물', '어류', '파충류'] 출력 : 5분 3초

개리가 말했어요

개굴! 이 알고리즘은 효율적이지 않다 개굴! 더 효율적인 알고리즘이 A, B, C가 있다 개굴!

라이캣이 말했습니다.

약자를 먼저 배려하는 것, 그러한 알고리즘이라면, 언제든지 받아들이겠다냥!

• 페이지 교체 알고리즘 : 페이지 교체 알고리즘은 메모리를 관리하는 운영체제에서, 페이지 부재가 발생하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것을 교체할지를 결정하는 방법입니다. 이 알고리즘이 사용되는 시기는 페이지 부재(Page Fault)가 발생해 새로운 페이지를 적재해야 하지만 페이지를 적재할 공간이 없어 이미 적재되어 있는 페이지 중 교체할 페이지를 정할 때 사용됩니다. 빈 페이지가 없는 상황에서 메모리에 적재된 페이지와 적재할 페이지를 교체함으로 페이지 부재 문제를 해결할 수 있습니다. (wikipedia)
• 가장 오랫동안 사용되지 않은 페이지를 제거하는 방법 말고도, FIFO 방법도 있습니다. 가장 오랫동안 있었던 페이지를 제거하는 방법입니다.