프로세스가 요구한 페이지가 현재 메모리에 없으면 페이지 부재가 발생합니다. 페이지 부재가 발생하면 스왑 영역에서 페이지를 메모리로 가져오는데 만약 메모리가 꽉 찼다면 메모리에 있는 페이지를 스왑영역으로 보내야 합니다. 이때 페이지 교체 알고리즘은스왑 영역으로 보낼 페이지를 결정하는 알고리즘으로, 메모리에서 앞으로 사용할 가능성이 적은 페이지를 대상 페이지로 선정하여페이지 부재를 줄이고 시스템의 성능을 향상합니다.
-
NUR 페이지 교체 알고리즘은 최근 미사용 페이지 교체 알고리즘이라고 불리며 LRU, LFU 페이지 교체 알고리즘 성능이 비슷하면서도 불필요한 공간 낭비 문제를 해결한 알고리즘입니다.추가 비트 2개만 사용하여 예측한다는 특징이 있습니다. 따라서 페이지마다참조 비트와변경 비트를 가지므로 페이지마다 추가되는메모리 공간이 2비트뿐입니다. 여기서참조 비트는 PTE 접근 비트를 가리키고, 변경 비트는 PTE의 변경 비트를 가리킵니다. 참조 비트와 변경 비트는 초깃값이 0이며 다음과 같은 경우 1이 됩니다.- 참조 비트: 페이지에 접근(read/execute)하면 1이 된다.
- 변경 비트: 페이지가 변경(write/append)되면 1이 된다.
모든 페이지의 초기 상태는 (0,0)입니다. 이 상태에서 페이지에 읽기 또는 실행과 같은 '접근'이 발생하면 (1,0)으로 바뀐다. 만약 페이지에 쓰기 또는 추가 같은 '변경'이 일어나면 (0,1)이 된다. 또한 접근과 변경, 두 가지 연산이 다 발생하면 (1,1)이 됩니다.
NUR 페이지 교체 알고리즘에서 대상 페이지(victim page)를 선정할 때는 (0,0), (0,1), (1,0), (1,1) 중에서 하나를 고르는데, 가장 먼저 (0,0)인 페이지를 선정한다. 즉 접근한 적도 변경한 적도 없는 페이지를 스왑 영역으로 옮긴다. 만약 (0,0)인 페이지가 없다면 (0,1)인 페이지를, (0,1)인 페이지가 없다면 (1,0)인 페이지를 (1,0)인 페이지가 없다면 최종적으로 (1,1)인 페이지를 스왑 영역으로 옮깁니다.
위에서부터 아래로 대상 프레임(victim page) 우선순위가 낮아진다. 만약 모두 (1,1)이면 초기화를 하도록 한다.
최적 근접 알고리즘인 LRU, LFU, NUR 페이지 교체 알고리즘의 성능은 거의 비슷하며 FIFO 페이지 교체 알고리즘보다 우수하다. 이 중에서
NUR 페이지 교체 알고리즘은 2bit만 추가하여 다른 알고리즘과 유사한 성능을 낼 뿐만 아니라 쉽게 구현할 수 있다는 장점덕분에 가장 많이 사용되고 있다.
-
먼저 FIFO 페이지 교체 알고리즘은 시간상으로 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정하여 스왑 영역으로 쫒아냅니다.
FIFO 페이지 교체 알고리즘은 큐로 구현합니다. 메모리의 맨 위에 있는 페이지는 가장 오래된 페이지이고, 새로운 페이지는 항상 맨 아래에 삽입됩니다.
메모리에 먼저 올라왔어도 자수 사용되는 페이지가 있기도 하고, 나중에 올라왔어도 한 번만 사용되는 페이지가 있기도 하다.
FIFO 페이지 교체 알고리즘은 무조건 오래된 페이지를 대상 페이지(victim page)로 선정하기 때문에 성능이 떨어지는데이러한 문제점을 개선한 것이 2차 기회 페이지 교체 알고리즘(second chance replacement algorithm)입니다.
-
위의 표는 위키피디아에서 참조한 것으로, 실제 예시를 통하여 확인할 수 있습니다. 직관적으로 말이 전혀 되지 않아보이지만, 아래의 사례를 통하여 이런 사례가 존재한다는 것을 알 수 있습니다. 3개의 page frames을 사용하는 경우에 4개의 page frames 을 사용하는 것보다 더 적은 page fault가 발생합니다.
Belady의 역설은 일반적으로 FIFO (선입 선출) 페이지 교체 알고리즘을 사용할 때 발생하고, LRU (Least Recently Used) 와 같은 알고리즘에서는 페이지 프레임이 증가함에 따라 페이지 폴트가 감소한다고 합니다.
-
LRU 페이지 교체 알고리즘(Latest Recently Used page replacement algorithm)은 '
최근 최소 사용 페이지 교체 알고리즘'이라고도 합니다. 즉 최근에 사용된 페이지는 놔두고 오래전에 사용된 페이지를 대상 페이지(victim page)로 선정합니다.큐로 구현가능하며 사용한 데이터를 큐에서 제거하여 맨 위로다시 올리고, 프레임이 모자랄 경우 맨 아래에 있는 데이터를 삭제합니다.단점으로는 프로세스가 주기억장치에 접근할때마다 참조된 페이지 시간을 기록해야 하므로 막대한 오버헤드가 발생 카운터나 큐, 스택과 같은 별도의 하드웨어가 필요합니다.
Q-6) 그럼 큐를 어떻게 구현할까요 하드웨어 쪽으로 LRU 알고리즘으로 구현할 때 페이지 변경 여부를 알 수 있는 특정 비트를 둔다고 한다. 비트를 변경하고 변경여부를 확인가능, 참조여부
-
페이지 접근 시간에 기반한 구현, 가장 간단한 형태는 페이지에 접근한 시간을 기록하여 구현하는 것이다.
FIFO 페이지 교체 알고리즘이 메모리에 올라온 시간을 기준으로 가장 오래된 페이지를 교체한다면, LRU 페이지 교체 알고리즘은 페이지에 접근한 지 가장 오래된 페이지를 교체한다.
주의할 점은 메모리 접근 패턴을 변경하면 LRU 페이지 교체 알고리즘의 성능이 FIFO 페이지 교체 알고리즘만큼 느려지기도 하고 최적 페이지 교체 알고리즘만큼 좋아지기도 한다는 사실이다. 일반적으로 LRU 페이지 교체 알고리즘의 선능은 FIFO 페이지 교체 알고리즘보다 우수하고 최적 페이지 교체 알고리즘보다는 조금 떨어진 것으로 알려져 있다.
카운터에 기반한 구현, 페이지 접근 시간을 기록하여 구현할 수 도 있지만 카운터를 사용하여 구현할 수 있다. 그런데 접근 시간을 기록하든 카운트를 기록하든 두 방법은 모두 추가적인 메모리 공간을 필요로 하는 것이 단점이다. 가령, 0~1024초를 표시하려면 10bit가 필요하고 더 큰 숫자를 표시하려면 더 많은 비트를 사용해야한다는 것이다. 이러한 추가 공간으로 인해 사용자가 사용할 수 있는 공간이 낭비된다.참조 비트 쉬프트 방식, 각 페이지에 일정 크기의 참조 비트를 만들어 사용한다. 참조 비트의 초깃값은 0이며 페이지에 접근할 때마다 1로 바뀐다. 또한 참조 비트는 주기적으로 오른쪽으로 한 칸씩 이동한다.참조 비트 쉬프트 방식은 LFU 페이지 교체 알고리즘과 혼동되기도 한다. LFU 페이지 교체 알고리즘은 페이지의 접근 횟수를 측정하여 대상 페이지를 선정한다.
최적 페이지 교체 알고리즘(Optimal page replacement algorithm)은 앞으로 사용하지 않을 페이지를 스왑 영역으로 옮긴다. 메모리가 앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시점부터 사용 시점까지 가장 멀리 있는 페이지를 대상 페이지로 선정한다. 즉, 프레임에 있는 페이지가 가장 나중에 불리는 것을 대상 페이지로 선정하는 것이다.
최적 페이지 교체 알고리즘은 미래의 메모리 접근 패턴을 보고 대상 페이지를 결정하기 때문에 성능이 좋다. 하지만 미래의 접근 패턴을 안다는 것이 불가능하여 실제로 구현할 수 없다. 최적 페이지 교체 알고리즘에 근접하는 방법을 연구한 결과 최근 최소 사용 알고리즘인 LRU(Latest Recently Used)와 최소 빈도 사용 알고리즘인 LFU(Latest Frequently Used), 최근 미사용 알고리즘인 NUR(Not Used Recently) 등이 개발되었다. 이러한 알고리즘은 과거의 데이터를 바탕으로 미래의 접근 패턴을 추정하기 때문에 최적 근접 알고리즘(Optimal approximation algorithm)이라고 부른다.
#### Q-8) 최적 알고리즘
- 페이지 교체 알고리즘은
가상 메모리 관리에서 사용됩니다. 운영 체제는 일반적으로 사용자가 실행하는 프로그램에 할당된 가상 주소 공간을 물리적인 메모리 공간에 매핑합니다. 그러나 물리적인 메모리 공간은 제한적이므로 운영 체제는 가상 주소 공간 중 일부만을 메모리에 올려놓고, 나머지는 디스크에 저장합니다. 이때, 프로그램이 필요로 하는 페이지가 메모리에 없는 경우페이지 부재(page fault)가 발생합니다. 페이지 부재가 발생하면 운영 체제는 디스크에서 해당 페이지를 읽어와 메모리에 올리는데, 이때 페이지 교체 알고리즘이 사용됩니다. 페이지 교체 알고리즘은 어떤 페이지를 디스크로 쫓아낼 것인지 결정하여 새로운 페이지를 메모리에 올리는 역할을 수행합니다. 페이지 교체 알고리즘의 목표는페이지 부재가 최소화되도록 하는 것입니다.
페이지 교체 알고리즘은 페이지 부재(page fault)가 발생했을 때, 메모리에 적재된 페이지 중에서 어떤 페이지를 디스크로 쫓아낼지 결정합니다. 이때,메모리에 적재된 페이지가 디스크의 내용과 달라져서 디스크의 내용을 갱신해야 하는 경우가 있습니다. 이를 더티 페이지(dirty page)라고 합니다. 더티 비트는 이러한 더티 페이지를 추적하기 위해 사용됩니다. 더티 비트는 페이지 테이블에 존재하며, 각 페이지마다 해당 비트가 할당됩니다. 페이지가 갱신되면, 더티 비트가 설정되어 해당 페이지가 더티 페이지임을 표시합니다. 이를 통해 페이지 교체 알고리즘은 더티 페이지가 있는 페이지를 우선적으로 디스크로 쫓아내어 디스크의 내용을 갱신할 수 있습니다. 즉,더티 비트는 페이지 교체 알고리즘이 페이지 교체를 수행할 때 더티 페이지를 우선적으로 쫓아내어 디스크의 내용을 갱신하도록 돕는 기술입니다.