용어 정리

LRU(Least Recently Used) : 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘

• 사용된 시간을 저장하여 가장 오랫동안 참조되지 않는 데이터를 제거
• 큐로 구현할 수 있음. 사용된 데이터를 큐에서 제거하여 맨 위로 보내고, 페이지를 교체해야 할 경우 맨 아래에 있는 페이지를 삭제하면 됨, O(1)이 걸림

LFU(Least Frequently Used) : 참조 횟수가 가장 작은 페이지를 교체하는 알고리즘

• 페이지의 참조 횟수로 교체 페이지 결정
• 참조 횟수를 통해 장기적 시간 규모에서의 참조 성향을 고려할 수 있지만 그만큼 tracking 해야 하는 범위가 넓기에 자료 구조에 따라 성능이 달라질 수 있음. 참조 횟수가 어디까지 내려갈 수 있는지 비교를 해야 하므로 O(N)이 걸릴 수 있음. 이를 heap을 이용하게 되면 O(logN)까지 최적화가 가능.

LRU, LFU 페이징 교체 알고리즘으로 사용 가능할까?

CPU에서 프로세스 A가 실행 중일 때, 프로세스 A의 논리적인 메모리에서 명령을 한 줄씩 읽어 와 실행하게 된다.

CPU가 프로세스 A에 대한 논리적인 주소를 주면 Page Table을 통해 즉시 물리적인 주소로 변환하여 이 주소를 CPU로 읽어들여야 한다.

변환 이후, 해당 페이지가 메모리에 올라와 있으면 즉시 참조가 가능하기 때문에 운영체제가 개입할 부분이 없다.

프로세스 A가 대기에서 실행 상태로 변경됐을 때 주소의 변환을 요청할 것이다. 하지만 Valid-invalid bit이 i(invalid) 라면 페이지가 Backing Store에 있기 때문에 *Page Fault`가 날 것이다.

이후 Trap(Software Interrupt)이 발생하고 CPU 제어권이 운영체제로 넘어가고 운영체제가 Backing Store에 있는 페이지를 메모리로 읽어올 것이다.

이 과정에서 Page Replacement를 하게 된다면 어떤 Page를 쫓아낼 것인지를 정해야 할 것이다.

어떤 것을 쫓아내야 할지 운영체제가 살펴보는데, LRU를 쓴다면 가장 오래전에 참조된 페이지를 쫓아내야 한다. 하지만 오래된 페이지가 어떤 페이지인지 알 수 있을까?

LFU 또한 각 페이지의 참조된 횟수를 알 수 있을까?

답은 알 수 없다 이다.

프로세스가 요청한 페이지가 이미 메모리로 올라와 있으면 CPU가 운영체제로 넘어가지 않는다.

하드웨어적으로 주소 변환을 해서 CPU로 읽어 들인다.

그러면 CPU는 프레임 접근 시간을 실질적으로 알지 못하게 되는 것이다.

Page Fault가 발생할 때는 Backing Store에 있는 페이지가 메모리로 올라온 시간을 알 수 있다.

따라서 LFU, LRU 알고리즘을 구현해야 할 때 사용되어야 하는 정보가 반쪽만 주어지는 것이라고 할 수 있다.

Caching

한정된 빠른 공간에 요청된 데이터를 저장해 두었다가 후속 요청 시 Cache에서 직접 서비스하는 방식

Paging system외에도 캐시 메모리, 버퍼 캐시, 웹 캐시에서도 많이 사용되는 기술

캐시 시간 제약

• 교체 알고리즘에서 삭제할 항목을 결정하는 일에 오랜 시간이 걸리는 경우 실제 시스템에 적용할 수 없음
• 버퍼 캐시나 웹 캐시의 경우 : O(1) ~ O(logN)까지 허용
• Paging System
  • Page Fault 인 경우에만 OS가 관여하기 때문에 이미 페이지가 메모리에 존재하는 경우에는 페이지에 대한 정보를 OS가 알 수 없음

Clock Algorithm

지금까지 봤듯이 Paging System에서는 LRU, LFU 알고리즘을 사용하지 못하기 때문에 Clock Algorithm을 사용하게 된다.

이는 가장 오래 전에 사용된 페이지를 쫓아내는 것 대신에 최근에 사용되지 않는 페이지를 쫓아내는 방식이다.

시계침처럼 지나가면서 Reference bit이 1일 때는 0으로 변경하고, Reference bit이 0인 페이지를 쫓아내는 기법이다.

여기서는 Modified Bit이라는 개념도 사용한다.

만약 쫓아내는 페이지가 수정되지 않았다면 Backing Store에 업데이트하여 저장할 필요가 없다. 이는 즉슨, Modified Bit이 0일 때 그냥 프레임을 메모리에서 쫓아내면 되는 것이다.

하지만 수정된 경우에는 Backing Store에 저장해야 하기 때문에 수정될 때에 Modified Bit을 1로 설정한다. 이후 Reference bit이 0이고 교체 대상 페이지가 된다면 Backing Store에 변경된 내용을 반영한다.

다음 시간에는 Page Allocation 및 Thrashing과 해결법에 대해 알아보겠다.