[OS] 가상 메모리 (페이지 부재/페이지 교체/스레싱/워킹셋)

create the illustion to users of a very large (main) memory

가상 메모리는 실제 물리적인 메모리보다 큰 용량의 메모리 공간을 제공하는 기술이다. 프로그램이 필요로 하는 데이터를 일부만 물리적 메모리에 로드하고, 나머지는 디스크 공간에 저장한다. 그리고 프로그램이 해당 데이터에 접근할 때만 필요한 부분을 메모리로 옮겨 사용한다. 이를 통해 더 많은 프로그램을 실행할 수 있고, 메모리를 보다 효율적으로 사용할 수 있다. 
 
가상 메모리는 주로 페이징 기법을 사용하여 메모리 용량을 초과하는 프로그램의 데이터를 디스크에 저장하고, 필요할 때마다 가져온다. 그러나 모든 페이지를 메모리에 동시에 유지할 수 없기 때문에 페이지 교체 알고리즘이 필요하다. 페이지 교체 알고리즘은 어떤 페이지를 메모리에서 내릴지 결정하며, 다양한 방식으로 동작할 수 있다. 지금부터 페이지 교체 알고리즘에 대해 알아보자.
 

페이지 교체

demand paging

pages should only be brought into memory if the executing process demands them

디맨드 페이징은 가상 메모리의 관리 방법으로, 실제로 필요한 페이지만 메모리에 적재하는 방식이다. 대부분의 프로그램은 일부만 필요하고 그 외의 데이터는 거의 사용하지 않는다. 따라서 모든 데이터를 메모리에 로드하는 것은 자원의 낭비를 초래한다.

demand paging의 효과

• 필요한 데이터만 로드하기 때문에 디스크 I/O양과 메모리 사용량이 감소한다.
• 필요한 데이터만 로드하므로 프로그램을 빠르게 시작할 수 있다.
• 메모리 자원의 효율적으로 사용하고, 빠른 응답 속도를 통해 더 많은 어플리케이션을 실행할 수 있다.

 

페이지 부재

페이지 부재는 프로그램이 실행되는 동안 필요한 페이지가 메모리에 없어 발생하는 현상이다. 즉, 프로세스가 메모리에 적재된 페이지를 참조하려고 할 대, 해당 페이지가 메모리에 없는 상태일 때 발생한다.
가상 메모리는 디맨드 페이징을 사용하는데, 이는 실제로 필요할 때만 페이지를 메모리에 로드하는 방식이므로 필요한 페이지가 메모리에 없는 경우 페이지 부재가 발생한다.

1. 프로세스가 특정 페이지에 접근하고자 한다.
2. 페이지 테이블을 사용하여 논리적 주소에 해당하는 물리적 주소를 찾는다.
3. 페이지 테이블에서 해당 페이지의 엔트리를 찾을 수 없거나 엔트리에 해당하는 데이터가 메모리에 없는 경우, 페이지 부재가 발생한다.
4. 페이지 부재가 발생하면 디스크에서 해당 페이지를 로드한다.

 

페이지 교체 알고리즘

물리적 메모리에 공간이 없는 경우 곧바로 사용되지 않을 페이지를 메모리에서 쫓아내야 한다. 페이지 교체 알고리즘은 물리적 메모리에 존재하는 페이지 중 어떤 페이지를 디스크로 내보내야 할지 결정한다. 일반적으로 사용되는 페이지 교체 알고리즘에는 다음과 같은 것들이 있다.

• LRU (least recently used) - 가장 오랫동안 참조되지 않은 페이지를 교체
• FIFO (first in first out) - 가장 먼저 메모리에 적재된 페이지를 교체
• LFU (least frequently used) - 참조 횟수가 가장 적은 페이지를 교체

🚨 부적절한 페이지 교체 알고리즘은 페이지 부재가 자주 발생하여 성능을 저하시킬 수 있다. 페이지 부재가 발생하면 해당 페이지를 디스크에서 메모리로 가져오기 위해 디스크 I/O가 발생하여 시간이 낭비된다.

 
클락 알고리즘*은 LRU 알고리즘을 구현하기 위한 방법이다. 페이지의 참조 상태를 관리하여 오랫동안 참조되지 않은 페이지를 교체하고, 최근에 사용된 페이지를 메모리에 유지한다.

*클락 알고리즘 == NUR (not recently used)

클락 알고리즘은 페이지의 참조 및 수정 상태를 추적하여 페이지를 교체한다. 페이지들은 원형 큐 형태로 관리되고, 메모리에 적재된 순서대로 배치된다.

• 참조 비트 (reference bit) - 페이지에 읽기 작업이 발생하면, 해당 페이지의 참조 비트가 1로 설정되어 최근에 사용되었음을 나타낸다.
• 수정 비트* (modified bit) - 페이지에 쓰기 작업이 발생하면, 해당 페이지의 수정 비트가 1로 설정되어 최근에 변경되었음을 나타낸다.

*페이지가 수정되면 해당 페이지는 디스크에 기록되어야 한다. 수정 비트는 페이지의 변경 여부를 나타내고 디스크I/O가 필요한 페이지로 간주한다.

클락 알고리즘은 페이지들을 가리키는 클락 포인터를 설정한다. 클락 포인터는 페이지 폴트가 발생했을 때 페이지들을 순회하며 교체할 페이지를 선정한다.
참조 비트가 1인 페이지를 만나면, 해당 페이지는 최근 참조된 것이므로 참조 비트를 0으로 수정하고 다음 페이지로 넘어간다. 만약 참조 비트가 0인 페이지를 만나면, 최근에 참조된 페이지가 아니므로 교체 대상이 된다. 해당 페이지를 메모리에서 삭제하고 새로운 페이지를 메모리에 올린 후, 새로운 페이지의 참조 비트를 1로 설정한다.
 

스레싱

프로세스가 원활하게 수행되기 위해서는 최소한의 페이지 프레임을 할당받아야 한다. 만약 프로세스에 충분한 페이지 프레임이 할당되지 않으면 스레싱이 발생할 수 있다.

스레싱은 프로세스가 필요한 페이지 프레임을 충분히 할당 받지 못하여 페이지 부재가 지나치게 빈번하게 발생할 때 일어나는 현상이다. 페이지 교체 작업이 빈번하게 일어나여 대부분의 시스템 자원이 페이지 교체에 소모되게 된다. 스레싱은 시스템의 성능을 급격하게 저하시킬 수 있으므로, 이를 방지하기 위해서는 프로세스에 충분한 페이지 프레임 수를 할당해야 한다.
 

워킹셋

위킹셋은 프로세스가 실행 중에 필요로 하는 페이지의 집합을 말한다. 즉, 프로세스가 일정 시간동안 원활하게 수행되기 위해서는 이 워킹셋에 속한 페이지들이 한꺼번에 메모리에 적재되어 있어야 한다. 이를 통해 페이지 부재가 빈번하게 발생하여 스레싱이 일어나는 것을 방지한다.

---

참고자료

• https://en.wikipedia.org/wiki/Virtual_memory
• https://en.wikipedia.org/wiki/Demand_paging