[운영체제] 가상 메모리

가상 메모리

• 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법이다.
• 사용자 프로그램이 물리 메모리보다 커져도 된다. 작은 메모리를 갖고도 얼마든지 큰 가상 주소 공간을 프로그래머에게 제공할 수 있다.
• 파일과 라이브러리의 공유를 쉽게 해주고, 공유 메모리 구현을 가능하게 한다.

요구 페이징(Demand Paging)

• 필요할 때만 페이지를 메모리에 적재한다.
• 프로세스가 실행되는 동안 일부 페이지는 메모리에 있고, 일부는 보조저장장치에 있다.
• 순수 요구 페이징(pure demand paging) : 어떤 페이지가 필요해지기 전에는 결코 그 페이지를 메모리로 적재하지 않는 방식

페이지 폴트

• 메모리에 올라와 있지 않은 페이지에 접근하려고 하면 페이지 폴트 트랩(page-fault trap)을 발생시킨다.
• 페이지 폴트를 처리하는 과정은 다음과 같다.

1. 프로세스 내부 테이블을 검사해서 메모리 참조가 유효, 무효인지를 알아낸다.
2. 무효한 페이지에 대한 참조라면 프로세스는 중단된다. 유효한 참조인 경우 메모리에 없으면 디스크로부터 가져와야 한다.
3. 빈 공간, 가용 프레임(free frame)을 찾는다.
4. 보조저장장치에 새로 할당된 프레임으로 해당 페이지를 읽어 들이도록 요청한다.
5. 보조저장장치 읽기가 끝나면, 이 페이지가 메모리에 있다는 걸 알리기 위해 페이지 테이블을 갱신하며, 프로세스가 유지하고 있는 내부 테이블을 수정한다.
6. 트랩에 의해 중단됐던 명령을 다시 수행하며, 이제 마치 그 페이지가 항상 메모리에 있었던 것처럼 해당 페이지에 접근할 수 있다.

참조의 지역성(locality of reference)

• 프로그램의 어느 한 특정 작은 부분만 한동안 집중적으로 액세스되는 특성으로 지역성의 원리라고도 불린다.
• 참조 지역성의 3가지
  1. 공간(spatial) 지역성
     • 특정 클러스터의 기억 장소들에 대해 참조가 집중적으로 이뤄지는 경향
     • 참조된 메모리 근처의 메모리를 참조
  2. 시간(temporal) 지역성
     • 최근 사용되었던 기억 장소들이 집중적으로 액세스되는 경향
     • 참조했던 메모리는 빠른 시간에 다시 참조될 확률이 높음
  3. 순차(sequential) 지역성
     • 데이터가 순차적으로 액세스되는 경향
     • 프로그램 내 명령어가 순차적 구성에 기인

페이지 교체

• 페이지 폴트가 발생하면 운영체제는 새로 진입할 페이지를 위한 공간을 만들기 위해 이미 존재하고 있는 페이지 중 하나를 내보내야 한다.
• 만약 내보낼 페이지가 변경되어 있다면, 그 페이지의 내용은 디스크로 보내져 기록되야 한다.
• 내보낼 페이지가 변경되지 않았다면, 디스크에 기록할 필요는 없다.

페이지 교체 알고리즘

기본적인 페이지 교체

1. 보조저장장치에서 필요한 페이지의 위치를 찾는다.
2. 빈 페이지 프레임을 찾는다.
   • 비어있는 프레임이 있다면 그걸 사용한다.
   • 없다면 victim 프레임을 선정하기 위해 페이지 교체 알고리즘을 수행한다.
   • 필요한 경우 내보낼 페이지를 보조저장장치에 기록하고, 관련 테이블을 수정한다.
3. 새로 비워진 프레임에 새 페이지를 읽어오고 테이블을 수정한다.
4. 페이지 폴트가 발생한 지점에서부터 프로세스를 계속한다.

FIFO 페이지 교체

• 메모리에 올라온 지 가장 오래된 페이지를 내쫓는다.
• 페이지가 메모리에 올라온 시간을 페이지마다 기록하거나, 올라온 순서를 큐에 저장한다.

장점

• 이해하기 쉽고, 프로그램하기 쉽다.

단점

• 성능이 항상 좋지는 않다.
• 활발하게 사용 중인 페이지를 계속해서 교체한다면 페이지 폴트가 높아진다.
• Belady의 모순 : 프로세스에 프레임을 더 주었는데 오히려 페이지 폴트율이 더 증가하는 현상

최적 페이지 교체(Optimal Page Replacement)

• 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체한다.

장점

• 할당된 프레임 수가 고정된 경우, 가장 낮은 페이지 폴트율을 보장한다.

단점

• 프로세스가 앞으로 메모리를 어떻게 참조할 것인지를 미리 알아야 하기 때문에 구현이 어렵다.
• 위 단점으로 주로 비교 연구 목적을 위해 사용된다.

LRU(Least-Recently-Used) 페이지 교체

• 위의 최적 페이지 교체 알고리즘은 실제 구현이 불가능하므로, 최적 페이지 교체 방식과 비슷한 효과를 낼 수 있는 방법을 사용한 것이 LRU 알고리즘이다.
• 페이지마다 마지막 사용 시간을 유지하여, 가장 오랫동안 사용되지 않은 페이지를 교체한다.

장점

• 최적 알고리즘보다 페이지 교체 횟수가 높지만, FIFO 알고리즘보다 효율적이다.

계수-기반 페이지 교체

• 페이지를 참조할 때마다 지금까지 참조된 횟수를 카운팅하는 방법이다.
• LFU와 MFU 방법이 있지만, 구현하는 데 비용이 많이 들고, 최적 페이지 교체 알고리즘에 근사하지 못해 일반적으로 잘 쓰이진 않는다.

LFU(Least Frequently Used)

• 활발하게 사용되는 페이지는 참조 횟수가 클 것을 기대하므로, 참조 횟수가 가장 적은 페이지를 교체하는 방법이다.
• 초기에 한 페이지를 집중적으로 많이 사용하지만, 그 후로 다시는 이 페이지를 사용하지 않는 경우와 같은 예외 상황은 참조 횟수를 일정 시간마다 하나씩 오른쪽으로 shift 해서 지속적으로 영향력을 감소시키는 방법으로 해결할 수 있다.

MFU(Most Frequently Used)

• LFU와는 반대로, 참조 횟수가 큰 페이지를 교체하는 방법이다.
• 참조 횟수가 작은 페이지가 가장 최근 참조된 것이고, 앞으로 더 사용될 것이라는 판단이다.

스래싱(Thrashing)

• 프로세스가 계속적으로 페이지 폴트가 발생하여 프로세스의 처리 시간보다 페이지 교체 시간이 더 많아지는 현상을 말한다.
• 스래싱의 원인 : 프로세스가 메인 메모리에 적재되어 수행되고자 할 때, 실제 사용하는 수만큼의 충분한 페이지 프레임을 갖지 못하는 경우에 발생한다.

• 다중 프로그래밍의 정도가 어느 점을 기준으로 더 커지면 스래싱이 일어나게 되고 CPU 이용률은 급격히 떨어진다.

  

• 완전히 스왑아웃 해버리거나 그래야 함