가상 메모리덕분에 프로세스 전체가 메모리 내에 올라가지 않아도 되고, 메모리보다 전체 프로그램이 더 커도 된다는 장점이 있음
또한, 파일과 라이브러리의 공유를 쉽게 해주고, 공유 메모리 구현을 가능케함
10.1 Background
기존의 전체 프로세스를 메모리에 올리고, dynamic loading을 사용해 좀 더 메모리 사용량을 낮출 순 있었다.
- 오류코드 처리
- 배열, 리스트, 테이블은 실제보다 더 큰 메모리를 잡아먹음
- 사용되지 않는 옵션
이것들은 굳이 메모리에 올릴 필요가 없다.
- 프로그램이 물리 메모리 크기에 제약없음
- 더 작은 메모리를 차지하므로 동시에 더 많은 프로그램 간으
- 프로그램을 메모리에 올리고 스왑하는데 필요한 I/O 회수가 줄어든다.
가상 메모리는 실제의 물리 메모리 개념과 논리 메모리 개념을 분리한 것
프로세스의 virtual address space는 프로세스가 메모리에 저장되는 논리적(가상의) 모습이다.
특정 logical address는 0번지부터 연속적인 공간을 차지한다.
물리 메모리는 프레임들로 구성되며, 프로세스에 할당된 페이지 프레임들은 연속적이진 않다.
(MMU에 달린 것)
프로그램에서 동적 메모리 할당을 할때마다 힙이 위로 증가하고, 스택은 연속적인 함수호출로 메모리 아래로 내려간다. 그리고 빈 구멍은 실제 물리 페이지가 없는 경우이고, 이런 구멍을 동적으로 링킹할때 구멍을 채워줄 수 있다.
표준 C 라이브러리같은 시스템 라이브러리들은 여러 프로세스에 공유될 수 있다.
공유 페이지란 것이 실제 라이브러리가 존재하는 물리 메모리 페이지이고, 각 프로세스는 공유가 가능하다.
또한, 프로세스들끼리 가상메모리를 통해 공유 메모리 기법을 통해 통신이 가능하다.
10.2 Demand Paging
필요한 페이지만 적재하는 것이 요구 페이징 기법이다.
요구 페이징 가상 메모리를 사용하면, 프로그램 실행 중 필요할 때만 페이지가 적재된다.
10.2.1 Basic Concepts
요구 페이징 기법은 필요할 때만 페이지를 메모리에 적재하는 것
결과적으론 일부 페이지만 메모리에 있고, 나머지는 디스크에 있다.
이런것들을 구분하기 위해 하드웨어가 필요하다.
일부 페이지가 메모리에 없고 디스크에 있는 상황이고, 페이지 테이블 항목이 무효로 설정되어 있는 상황이다.
그래서 페이지 폴트가 발생함
- 프로세스에 대한 내부 테이블을 검사해서 그 메모리 참조가 유효, 무효인지 알아냄
- 무효한 페이지에 대한 참조라면, 그 프로세스는 중단되고, 유효한 참조라면, 그것을 디스크로부터 가져와야함
- 빈 공간을 찾음
- 디스크에 새로 할당된 프레임으로 해당 페이지를 읽도록 요청함
- 디스크 읽기가 끝나면, 페이지 테이블을 갱신하며, 내부 테이블을 수정
- 중단되었던 명령어를 다시 수행
pure demand paging이란 어떤 페이지가 필요하기전까지는 결코 그 페이지를 메모리에 올리지 않는 방법
10.2.2 Free-Frame List
페이지 폴트가 발생하면, 디스크로부터 페이지를 가져와야함.
가용 프레임 풀인 가용 프레임 리스트를 유지해야함
zero-fill-on-demand 필요시 0으로 채우는 것이다.
할당되기전 0으로 다 채워져서 초기화되는 것
시스템이 시작되면 모든 가용 메모리가 가용 프레임 리스트에 넣어진다.
가용 프레임이 요청되면 가용 프레임 리스트의 크기가 줄어든다.
10.2.3 Performance of Demand Paging
10.3 Copy and Write
fork를 통해 요구 페이징을 생략가능하다.
부모의 페이지를 다 복사하는 대신 copy on write 방식을 사용
자식 프로세스가 시작할 때, 부모의 페이지를 당분간 함께 사용하도록 함
이때 공유되는 페이지를 쓰기 시 복사 페이지라고 표시한다.
둘 중 한 프로세스가 공유중인 페이지를 쓸때, 그 페이지의 복사본이 만들어진다.
10.4 Page Replacement
Basic Page Replacement
- 만약 빈 프레임이 없다면, 현재 사용되고 있지 않는 프레임을 찾아서 비운다.
- 희생될 프레임을 선정하기 위해 페이지 교체 알고리즘을 가동
- 페이지 테이블 수정
- 페이지 폴트가 발생한 지점에서부터 프로세스를 계속한다.
빈 프레임이 없는 경우에는 디스크를 2번 접근해야한다. 그러므로 페이지 폴트 처리 시간이 2배가 된다.
이러한 오버헤드는 modify bit, dirty bit를 사용해서 감소시킬 수 있다.
프레임 할당 알고리즘, 페이지 교체 알고리즘
각 프로세스에게 얼마나 많은 프레임을 할당해야 하는지, 어떤 페이지를 교체해야 하는지
페이지 폴트 비율이 낮은 페이지를 선정하여 교체
10.4.2 FIFO Page Replacement
메모리에 올라온지 가장 오래된 페이지를 바꾸는 법
프레임을 더 많이 썻는데도 페이지 폴트가 더 많이 일어나는 현상이 belady의 모순
10.4.3 Optimal Page Replacement
앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아서 교체해라
가장 낮은 페이지 폴트 비율이지만, 구현하기 어렵다
10.4.4 LRU Page Replacement
각 페이지마다 마지막 사용시간을 유지하고, 페이지 교체시에 가장 오랫동안 사용되지 않은 페이지를 교체함
하드웨어 지원 필요
10.4.5 LRU Approximation Page Replacement
처음에 모든 참조 비트는 0으로 초기화하고, 프로세스가 실행되면 참조되는 페이지의 비트는 1로 바뀐다.
-
부가적 참조 비트 알고리즘 : 일정한 간격마다 참조비트를 기록
-
2차 기회 알고리즘 : 참조 비트가 0이면 페이지를 교체, 1이면 다시 한번 기회를 준뒤 FIFO로 넘어간다.
-
개선된 2차 알고리즘
10.4.6 Counting Based Page Replacement
LFU : 알고리즘 참조 횟수가 가장 작은 페이지를 교체하는 방법
MFU : 참조 횟수가 가장 큰 페이지를 교체하는 알고리즘
10.4.7 Page Buffering Algorithm
시스템이 사용가능한 프레임을 여러 개 가지고 있다가, 페이지 폴트가 발생하면, 교체될 페이지를 기다리지 않고 새로운 페이지에 먼저 읽어 들이게 하는 방법
사용가능한 프레임 풀을 유지하지만, 그 풀 속 각 프레임의 원래 임자 페이지가 누구였었는지를 기억하는 방법
10.5 Allocation of Frames
여러 개의 프로세스들에 제한된 가용 메모리를 어떻게 할당할 것인가?
10.5.1 Minimum Number of Frames
페이지 공유가 없다면, 사용 가능한 프레임 수보다 더 많이 할당할 순 없지만, 너무 작게 할당해서는 안된다.
각 프로세스에 할당되는 프레임수가 줄면 페이지 폴트 비율이 올라가면서, 프로세스의 실행이 늦어진다
10.5.2 Allocation Algorithms
모든 프로세스에게 똑같이 할당해주는 방법
이런 방법을 equal Allocation이라고 하고 ㄴ남은것은 가용 프레임 버퍼 저장소로 사용한다.
하지만 두 프로세스의 크기가 차이가 많이 날 경우, 비례 할당 방식을 사용
10.5.3 Global Vs Local Allocation
페이지 교체 알고리즘은 전연 교체와 지역 교체가 있다.
전역 교체는 프로세스가 교체할 프레임을 다른 프로세스에 속한 프레임을 포함한 모든 프레임을 대상으로 찾는 경우
지역 교체는 각 프로세스가 자기에게 할당된 프레임들중 교체될 희생을 선택하는 경우
지역교체에서는 프로세스에 할당된 프레임 수는 변하지 않고, 전역 교체 아래에서는 프레임의 수가 바뀔 수 있다.
10.5.4 NUMA
메모리 접근 시간이 현저하게 차이가 나는 시스템
