[공룡책] 가상메모리

앞서 작성한 글에서 다중 프로그래밍을 실현하기 위한 이야기가 많이 등장했습니다.

다중 프로그래밍을 실현하기 위해 많은 프로세스를 동시에 메모리에 올려둬야 합니다.

가상 메모리는 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록하는 기법입니다.

프로그램이 물리 메모리보다 커도 된다는 장점이 있는 이 가상 메모리에 대해 작성해볼까 합니다.

가상메모리

프로그램 전체가 늘 메모리에 올라와 있어야 하는 것은 아닙니다.

• 만일을 대비한 코드는 만일의 상황에만 실행됩니다.
• arrays, lists 등은 필요 이상으로 많은 공간을 점유하기도 합니다.

프로그램의 일부만 메모리에 올릴 수 있다면 많은 이점이 존재합니다.

• 물리 메모리 크기에 제약받지 않아도 됩니다.

• 더 많은 프로그램을 동시에 실행시킬 수 있습니다.

  • 응답시간은 유지되고 CPU 이용률과 처리율은 높아집니다.
• swap에 필요한 입출력이 줄어들기 때문에 속도 효율이 좋습니다.

가상 주소 공간

• 한 프로세스가 메모리에 저장되는 논리적인 모습을 가상메모리에 구현한 공간입니다.
• 현재 필요하지 않은 공간은 실제 물리 메모리에 올리지 않아서 메모리를 절약할 수 있습니다.

프로세스간 페이지 공유

• 시스템 라이브러리가 여러 프로세스들 사이에 공유될 수 있도록 합니다.
• 각 프로세스들은 공유 라이브러리를 자신의 가상 주소공간에 두고 사용하는 것처럼 인식하지만, 라이브러리가 올라가있는 물리 메모리 페이지들은 모든 프로세스에 공유되고 있습니다.
• 프로세스들이 메모리를 공유하는 것을 가능하게 하고 프로세스들은 공유메모리를 통해 통신할 수 있습니다.

Demand Paging

• 실행 프로그램 중 필요한 페이지만 메모리로 적재하는 기법을 요구 페이징이라고 합니다.
• 사용되지 않을 페이지를 가져오는 시간낭비와 메모리 낭비를 줄일 수 있다는 장점이 있습니다.

Page Fault Trap

1. internal table을 검사해 메모리 참조가 유효, 무효인지를 알아낸다.

   1. 무효한 페이지 참조라면 중단된다.
   2. 유효한 참조인데 페이지가 아직 메모리에 올라오지 않았다면 보조저장장치로부터 가져와야 한다.
2. free frame을 찾는다.
3. 보조저장장치에 새로 할당된 프레임으로 해당 페이지를 읽어 들이도록 요청한다.
4. 읽기가 끝나면 페이지 테이블을 갱신하며 프로세스가 유지하고 있는 내부 테이블을 수정한다.
5. 트랩에 의해 중단되었던 명령어를 다시 수행한다.

요구 페이징은 페이지 폴트 오류 처리 후에 명령어 처리를 다시 시작할 수 있어야 합니다.

Pure Demand Paging

극단적으로는 메모리에 페이지가 하나도 안올라와 있어도 프로세스를 실행시키는게 가능합니다.

명령 포인터의 값을 프로세스의 첫 명령으로 설정하는 순간, 메모리에 존재하지 않는 페이지에 있으므로 페이지 폴트를 발생시킵니다.

필요한 페이지가 모두 메모리에 올라올 때까지 필요할 때마다 페이지 폴트가 발생합니다.

필요에 의해서만 페이지를 적재시키는 기법을 순수요구 페이징이라 합니다.

Page Replacement

페이지를 요청할 때 page fault가 발생하면 보조저장장치에서 페이지를 가져오게 됩니다.

하지만 물리 메모리가 모두 사용중일 때 페이지 교체가 필요합니다.

Basic Page Replacement

1. 필요한 페이지의 위치를 찾는다.

2. 빈 페이지 프레임을 찾는다.

   1. 희생될 페이지를 고른다.
   2. 희생될 페이지를 디스크에 기록하고 관련 페이지 테이블을 수정한다.
3. 페이지 테이블 내 프레임에 새 페이지를 읽어오고 프레임 테이블을 수정한다.
4. 프로세스를 계속한다.

FIFO Page Replacement

• 장점

이해하기도 쉽고 프로그래밍하기도 쉬운 기법입니다.

• 단점

하지만 초기 변수처럼 오래됐지만 필요한 정보를 포함하는 경우가 존재합니다.

또한 처음부터 활발히 사용되는 페이지를 교체해서 page fault rate를 높일 수 있습니다.

Belady의 모순 - 페이지를 저장할 수 있는 페이지 프레임의 개수를 늘려도 페이지 폴트가 더 생기는 모순이 존재합니다.

Optimal Page Replacement

앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 기법입니다.

• 장점

Belady의 모순을 확인한 후 탐구되었고 가장 낮은 페이지 부재율을 보이며 Belady의 모순이 생기지 않는 장점이 존재합니다.

• 단점

메모리 참조 계획을 예측하기 힘듭니다. 때문에 구현이 어렵습니다.

LRU Page Replacement

Least-Recently-Used

가장 오래 사용되지 않은 페이지를 교체합니다.

LFU Page Replacement

Least-Frequently-Used

참조 횟수가 가장 적은 페이지를 교체합니다. 참조 횟수가 많다는 뜻을 활발히 사용된다는 뜻으로 받아들이는 알고리즘입니다.

프로세스가 특정 페이지를 집중적으로 사용하다가 다른 기능을 사용하게 되면, 더이상 사용하지 않아도 메모리에 상주해 초기 가정에 어긋나는 시점이 존재합니다.

최적 페이지 교체와 거리가 멀기 때문에 잘 쓰이지 않습니다.

MFU Page Replacement

참조 횟수가 가장 작은 페이지는 최근에 메모리에 올라왔으며 앞으로 계속 사용될 것이라는 알고리즘입니다.

최적 페이지 교체와 거리가 멀기 때문에 잘 쓰이지 않습니다.

References

• Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』
• https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/OS#가상-메모리