배경
배경
프로그램은 프로세스 형태로 메모리에 적재되어서 동작하는데, 대부분 전체 프로그램 코드가 한번에 필요하지 않는다.
예를 들어, 예외 처리를 하는 코드들은 잘 사용하지 않는다.
자주 사용하는 것들만 메모리에 있으면 충분하므로 프로그램의 일부만 메모리에 적재되어 실행된다.
이로 인해 프로그램은 물리 메모리 크기의 제약을 받지 않게 되고, 각 프로그램은 실행되는 동안 더 적은 메모리를 사용하게 된다.
따라서 동시에 더 많은 프로그램을 실행할 수 있고 응답시간이 늘어나지 않으면서도 CPU 이용률과 처리율을 높일 수 있다.
가상 메모리
가상 메모리 : 사용자 논리 메모리와 물리 메모리를 분리함.
프로그램의 실행을 위해 프로그램 전체가 아닌, 일부만 메모리에 적재하여 실행한다.
따라서 논리 주소 공간은 실제 물리 주소 공간보다 훨씬 클 수 있고,
더 많은 프로그램을 동시에 실행할 수 있고 효율적이게 프로세스를 생성할 수 있다.
전체 프로그램이 올라가는 것이 아닌, 부분이 올라가기 때문에 적재 또는 스왑을 하는 데 더 적은 I/O 작업을 요구한다.
여러 프로세스에서 주소 공간을 공유할 수도 있다.
가상 메모리는 일반적으로 주소 0에서 시작하여 주소 공간이 끝날 때까지 연속된 주소를 가진다.
반면, 물리 메모리는 페이지 프레임들로 구성된다.
MMU는 반드시 논리 주소를 물리 주소로 바꾸어야 한다.
가상 메모리는
1) 요구 페이징 (Demand paging)
2) 요구 세그멘테이션 (Demand segmentation)
의 방식으로 구현이 가능하다.
가상 주소 공간
- 스택이 논리 주소의 가장 큰 부분에서부터 시작하여 아래로 확장된다.
- 힙은 스택과 반대로 위로 확장된다.
- 이 둘 사이의 사용되지 않는 주소를 hole이라 부른다.
시스템 라이브러리는 가상 주소 공간으로의 매핑을 통해 공유된다.
요구 페이징
앞서 가상 메모리를 구현하기 위해 요구 페이징 기법을 사용할 수 있다고 했다.
적재 시 전체 프로세스를 메모리에 가져울 수도 있지만, 필요할 때에만 페이지를 메모리로 가져올 수 있다.
필요할 때만 페이지를 가져오면
- 보다 적은 I/O 작업을 수행
- 더 적은 메모리가 필요
- 더 빠른 반응
- 더 많은 사용자
의 장점을 가질 수 있다.
페이지가 필요하면 그 페이지를 참조하는데, 잘못된 참조라면 중단하고, 메모리에 없다면 메모리로 가져온다.
게으른 스와퍼 (Lazy swapper) : 페이지가 필요할 때까지 페이지를 메모리로 절대 스왑하지 않는다.
페이지를 다루는 스와퍼는 호출기(페이저, pager)라고 부른다.
기본 개념
swap out 이전에 어떤 페이지들이 쓰일지를 추측하고, 필요한 페이지들만 메모리로 가져올 수 있다.
스와핑을 통해 호출기(pager)는 어떤 페이지들이 스왑아웃 되기 전에 다시 사용될 것인지 추측한다.
그리고 호출기는 이러한 페이지들만 메모리로 가져온다.
- 페이지가 필요하며 이미 메모리에 있는 경우 : 요구 페이징을 쓰지 않을 때와 차이가 없다.
- 페이지가 필요한데 메모리에 없는 경우 : 저장소에서 페이지를 탐지하고 메모리에 페이지를 적재해야 한다. (프로그램의 동작을 변경하지 않고, 프로그래머가 코드를 변경할 필요가 없다.)
유효-무효 비트
어떻게 요구하는 페이지가 메모리에 있는지 확인할까?? -> 각 페이지 테이블 항목과 유효-무효 비트를 연결
- valid : 메모리에 있음. 메모리 상주 (memory resident)
- invalid : 메모리에 없음
초기에는 모든 항목이 invalid 상태이다.
MMU 주소 변환 중에 페이지 테이블 항목의 validation bit가 invalid인 경우 = 페이지 폴트 (page fault)
페이지 폴트 처리 과정
- 페이지 참조 시작
- 페이지 테이블에서 페이지를 못찾음 -> trap
2-1. 운영체제가 다른 테이블을 보고 잘못된 참조라면 프로그램 중단
2-2. 단지 메모리에 없는 경우라면 3으로 - 페이지는 저장 장치에 있으므로
- 해당 페이지를 가용 프레임으로 가져오고
- 페이지 테이블을 재설정한 후 (유효 비트를 valid로 설정)
- 페이지 폴트를 발생시킨 명령어를 다시 실행한다.
요구 페이징의 측면
극단적인 경우를 생각해보자.
메모리에 페이지가 없는 상태로 프로세스가 시작되었고, 운영체제가 명령 포인터를 프로세스의 첫번째 명령어로 지정한다.
그리고 해당 프로세스의 다른 모든 페이지들도 처음으로 접근을 하는 것이다. (순수 요구 페이징, pure demand paging : 제일 처음 접근하는 것)
메모리에서 2개의 숫자를 더하고 결과를 다시 저장하는 명령어와 같이
어떤 명령어가 여러 개의 페이지에 접근할 수도 있다. -> 다중 페이지 폴트
이 경우 참조의 지역성 (locality of reference) 에 의해 이러한 부담이 적어진다.
요구 페이징에 대한 하드웨어 지원이 필요하다.
- validation 비트를 가지는 페이지 테이블
- 보조 저장 장치 : 스왑 공간을 가지는 스왑 장치
- 명령어 재시작 : page fault가 났을 때 해당 부분에서 멈췄다가 다시 재시작할 수 있어야 함.
가용 프레임 리스트
만약 page fault가 발생하였고, 잘못된 참조가 아니라면 운영체제는 반드시 요청된 페이지를 보조 저장장치에서 메인 메모리로 가져와야 한다.
이 때 메인 메모리의 어디로 가져올 수 있는지 알 수 있게, 대부분의 운영체제는 가용 프레임 리스트를 가지고 이를 관리한다.
운영체제는 일반적으로 프레임 내의 모든 항목들이 할당되기 전에 0으로 초기화되는 zero-fill-on-demand 라고 알려진 기법을 사용하여 가용 프레임을 할당한다.
시스템이 시작되면 모든 가용 메모리가 가용 프레임 리스트에 추가된다.
요구 페이징의 절차
- 운영체제에 trap을 요청
- 레지스터들과 프로세스 상태를 저장
- 인터럽트 원인이 페이지 폴트임을 확인
- 페이지 참조가 유효한 것인지 확인하고, 유효하다면 보조 저장장치에 있는 페이지의 위치를 확인
- 디스크에서 가용 프레임으로의 읽기 요구를 발행
5-1. 읽기 차례가 돌아오기까지 대기열에서 대기
5-2. 차례가 오면, 디스크의 검색(seek) 시간과 지연 시간동안 대기
5-3. 페이지를 가용 프레임으로 전송 시작 - 이를 기다리는 동안 CPU를 다른 사용자에게 할당
- 저장장치 I/O 서브 시스템으로부터 I/O 완료 인터럽트를 수신 (5번에서 전송이 끝나면)
- 다른 사용자에게 할당하여 돌아가던 프로세스의 레지스터와 프로세스 상태 저장
- 인터럽트가 디스크로부터 발생된 것을 확인
- 새 페이지가 메모리에 있다는 것을 보이기 위해 페이지 테이블과 다른 페이지를 수정
- CPU에 이 프로세스가 할당되기를 기다림
- 사용자 레지스터, 프로세스 상태, 새 페이지 테이블을 복원시키고 인터럽트 되었던 명령어를 다시 실행
요구 페이징의 성능 (Effective access time)
페이지 폴트 비율 p, 메모리 접근 시간 t에 대해
실질 접근 시간 (EAT) = ((1-p) t) + (p (page fault overhead + swap page out + swap page in))
예를 들어, t = 200nanoseconds, 평균 page fault 서비스 시간 = 8milliseconds이라 할 때
EAT = (1-p) 200 + p 8,000,000 = 200 + 7,999,800 * p nanoseconds
page fault의 비율이 클수록 성능이 어마어마하게 안좋아지므로
page fault를 최대한 줄여야한다.
요구 페이징 최적화 기법들
-
일반 파일 시스템보다 관리가 조금 더 필요하지만, 일반 파일 시스템보다 큰 블록을 사용하는 스왑 공간을 만들어 활용하면 스왑 공간에서의 디스크 I/O는 일반 파일 시스템의 I/O보다 빠르기 때문에 최적화할 수 있다.
-
프로세스 시작 시 전체 프로세스 이미지를 스왑 공간에 복사하고, 이후 스왑 공간에서 요구 페이징을 수행한다. (오래된 BSD 유닉스에서 사용)
-
요구 페이지를 요청할 때에 디스크에서 불러오고, 페이지의 교체가 필요하면 page out을 하지 않고 그대로 덮어쓴다. (Solaris와 현재의 BSD에서 사용) 하지만 여전히 스왑 공간에 써야한다.
-
모바일 시스템에서는 일반적으로 스와핑을 지원하지 않고, 대신 파일 시스템으로부터 요구 페이징을 하고 읽기 전용 페이지들을 방출한다.
Copy on write
쓰기 시 복사
Copy on write는 말 그대로, 쓰기 시작하는 시점에 복사하는 것이다.
부모와 자식 프로세스가 처음에는 메모리 상 같은 페이지를 공유하다가, 둘 중 한 프로세스가 공유중인 페이지를 쓸 때 그 페이지가 복사된다.
쓰기 시 복사는 단지 변경된 페이지만 복사하게 함으로써, 프로세스 생성을 보다 효율적으로 할 수 있다.
일반적으로 가용 페이지들은 풀에 있는 zero fill on demand 페이지로부터 할당된다.
빠른 요구 페이지 실행을 위해 풀에는 항상 가용 프레임들이 있어야 한다.
페이지 교체
가용 프레임이 없다면?
page fault가 일어나면 저장장치에서 해당 page를 찾은 후 메모리의 가용 프레임으로 가져온 후 페이지 테이블을 update한다고 하였다.
이 때, 다음 상황과 같이 만약 가용 프레임이 없다면 어떻게 해야할까? -> 메모리 안에서 실제로 사용되지 않는 페이지들을 찾아서 page out 해야한다.
- 변경 비트(modify bit)를 사용하여 변경된 페이지들만 디스크에 쓸 수 있게 하여 페이지 전송의 오버헤드를 줄인다.
- 페이지 폴트 서비스 루틴을 페이지 교체를 포함하도록 수정하여 메모리 과할당(over allocation)을 방지
기초적인 페이지 교체
- 보조저장장치에서 필요한 페이지의 위치를 찾음
- 가용 프레임을 찾음
1-1. 가용 프레임이 있는 경우 그것을 사용
1-2. 가용 프레임이 없는 경우 페이지 교체 알고리즘을 사용하여 victim frame을 선택 - page table에서 victim frame의 valid bit를 invalid로 설정 (victim frame을 선택하고 새로 요구한 page를 가져올 때 까지도 시간이 거리기 때문에 valid bit를 먼저 update해준다.)
- 요구한 페이지를 물리 메모리의 가용 프레임으로 가져옴
- page table을 update함
- 트랩을 발생시킨 명령어를 재시작
페이지와 프레임 교체 알고리즘
-
프레임 할당 알고리즘 (Frame allocation algorithm)
각 프로세스들마다 얼마나 많은 프레임을 할당해야할지, 어떤 프레임을 교체할지를 결정한다. -
페이지 교체 알고리즘 (Page replacement algorithm)
첫번째 접근과 재접근시 모두에 대해 가장 낮은 페이지 폴트율을 가질 수 있도록 하는 것을 선호한다.
page fault와 프레임의 개수는 다음과 같이 반비례 관계이다.
FIFO 페이지 교체
가장 간단한 알고리즘인 FIFO를 통해 페이지 교체 정책을 설정할 수 있다.
가용 프레임이 없다면 가장 오래된 page를 교체하면 된다.
그러나 FIFO를 통해 구현을 했을 때 Belady의 모순이 있을 수 있다.
page fault와 프레임의 개수는 앞의 그림처럼 반비례 관계이지만 프레임을 추가하는 것이 더 많은 page fault를 발생시키도 한다.
위 그림은 Belady의 모순을 보여준다.
최적 페이지 교체
최적 페이지 교체는 가장 오랫동안 사용되지 않을 페이지를 찾아서 교체하는 방식이다.
그러나 미래를 알 수 없기 때문에 가장 오랫동안 사용되지 않을 페이지를 현 시점에서 알기란 불가능하다.
따라서 이는 모든 input을 아는 상황에서 우리가 적용한 알고리즘이 얼마나 잘 동작하는지 판단하기 위한 척도로 사용된다.
LRU 페이지 교체
Least recently used 방식은 가장 오랫동안 사용되지 않았던 페이지를 교체한다.
해당 페이지를 찾기 위해서는 2가지 방법을 사용할 수 있다.
1) 계수기 구현 (Counter implementation)
각 페이지 항목들에 계수기를 추가하여 해당 페이지 항목을 참조할 때 계수기에 현재 시간을 복사한다.
그리고 페이지 교환이 필요한 경우 페이지 테이블을 탐색하여 계수기의 시간이 가장 오래된 페이지를 선택한다.
2) 스택 구현 (Stack implementation)
양방향 연결리스트 형식을 가지는 스택을 활용한다.
페이지가 참조될 경우 해당 페이지를 스택에서 빼내어 top으로 올린다.
따라서 가장 최근에 사용한 페이지는 stack의 top에, 사용한지 가장 오래된 페이지는 stack의 bottom에 위치한다. (이 과정에서 최대 6개의 포인터를 수정해야 할 수도 있다.)
스택을 이용하여 LRU를 구현하면 교환을 위해 탐색을 할 필요 없이 stack의 bottom에 있는 페이지를 교체하면 된다. 그러나 매 갱신 시 오버헤드가 비교적 큰 단점이 있다.
LRU 근사 페이지 교체
앞서 살펴본 LRU는 특별한 하드웨어를 필요로 하며 느린 단점이 있다.
따라서 정확히 LRU 페이지를 찾아 교체를 하는 것이 아닌,
어느정도 LRU와 근사한 페이지를 찾아 교체를 할 수도 있다.
이를 위해 참조 비트 (Reference bit)를 두고,
각 페이지가 참조될 경우 1로 설정하고 페이지를 교체한다면 0으로 설정을 하여
페이지를 교체할 때 1인 페이지를 교체하는 방법을 사용할 수도 있다.
(그러나 정확히 사용된 순서는 알 수 없다.)
2차 기회 알고리즘 (Second chance algorithm)
2차 기회 알고리즘은 victim이 선정되었을 때 한번 더 기회를 주는 방법이다.
FIFO와 하드웨어에서 지원하는 참조 비트를 사용하여
페이지 교체 시 참조 비트가 1이라면 0으로 설정하고 기회를 한번 더 준다. (메모리에 그대로 남김)
참조 비트가 0이라면 교체를 하게 된다.
개선된 2차 기회 알고리즘
참조 비트에 변경 비트를 추가하여 2차 기회 알고리즘을 개선할 수 있다.
(참조, 변경) 비트의 조합을 확인하여
- (0, 0) : 최근 사용 X, 변경 X -> 교체하기 가장 좋은 페이지
- (0, 1) : 최근 사용 X, 변경 O -> 이 페이지는 교체하려면 디스크에 내용을 기록하야한다.
- (1, 0) : 최근 사용 O, 변경 X -> 이 페이지는 다시 사용될 가능성이 높다.
- (1, 1) : 최근 사용 O, 변경 O -> 이 페이지는 다시 사용될 가능성도 높고 교체하기 위해서는 디스크에 내용을 먼저 기록해야 한다.
계수 기반 페이지 교체
각 페이지마다 페이지의 참조 횟수를 계산하는 수를 유지할 수 있긴 하지만 일반적인 방법은 아니다.
페이지의 참조 횟수를 가지고 판단하는 방법도 아래와 같이 다르게 해석할 수 있다.
-
LFU 알고리즘 (Least frequently used) : 가장 적은 참조 횟수를 가지는 페이지는 사용될 일이 없을거라 판단하여 교체함
-
MFU 알고리즘 (Most frequently used) : 가장 적은 참조 횟수를 가지는 페이지는 아마 메모리에 들어온지 얼마 되지 않았고, 앞으로 사용될 것이라는 판단하여 교체하지 않음
페이지 버퍼링 알고리즘
가용 프레임을 담아놓는 풀을 구성할 수 있다.
page fault가 일어나면 기존처럼 victim frame을 선택한다.
그러나 victim이 out되기 전에 요구한 page가 가용 프레임으로 먼저 들어온다.
가용 프레임을 담아놓는 풀을 구성하여 page fault 후 프레임이 필요할 때 바로바로 가져다 쓸 수 있게함.
가능하면 변경된 페이지의 목록을 유지
만약 백업 저장장치가 유후 상태일 때에 페이지를 그곳에 쓰고
더럽지 않다고 표시
프레임의 할당
각 프로세스에는 반드시 필요한 최소 프레임의 수가 있다. (물론 최대 프레임의 수는 시스템의 총 프레임의 수)
고정 할당
-
균등 할당 (equal allocation) : 각 프로세스에 프레임을 균등하게 나누어 할당하는 것. (100개의 프레임과 5개의 프로세스가 있다면 각 프로세스에게 20개의 프레임을 할당)
-
비례 할당 (proportional allocation) : 프로세스의 크기에 비례하여 할당. 다중 프로그래밍의 정도와 프로세스의 크기가 변함에 따라 변화한다.
전역 vs 지역 할당
-
전역 교체 (global replacement) : 프로세스가 모든 프레임들로부터 재배치 프레임을 선택할 수 있고, 심지어 다른 프로세스의 프레임도 가져갈 수 있다. (프로세스의 실행 시간이 크게 달라질 수 있음, 일반적으로 처리량이 많을수록 전역 교체 방법을 채택)
-
지역 교체 (local replacement) : 각 프로세스는 자신에게 할당된 프레임에서만 선택이 가능하다. (프로세스별 성능을 보다 일관되게 유지할 수 있지만, 메모리 활용도가 떨어질 수 있다.)
페이지 회수
전역 페이지 교체 정책을 구현하기 위한 전략으로, 모든 메모리 요청은 가용 프레임 리스트에서 충족된다.
페이지 교체는 특정 임계값 아래로 떨어지면 발생하고, 리스트 항목의 개수가 0으로 떨어지고 나서야 페이지 교체를 시작하지 않는다.
이 전략은 새 요청을 충족할 수 있는 충분한 여유 메모리가 항상 있는지에 대해 확인하려고 시도한다.
비균등 메모리 접근
지금까지는 모든 메모리가 동등하게 접근된다고 가정했다.
하지만 많은 시스템들이 다음과 같은 비균등 메모리 접근(NUMA)로 구성되어 있다.
NUMA 구조에서 최적의 성능을 내기 위해서는 프로세스가 실행중인 CPU와 가장 가까운 메모리를 할당할 수 있도록 해야한다.
또한, 가능한 동일한 시스템 보드에서 스레드를 예약하도록 스케줄러를 수정해야한다.
Thrashing
스레싱
Thrash : (채찍 등으로) 갈기다, 때리다
Thrashing : 프로세스가 페이지를 swap-in / swap-out 하느라 바빠지는 현상
만약 프로세스가 충분한 수의 페이지를 가지지 못한다면 page fault는 자주 일어나게 된다.
Page fault가 자주 일어나게 되면 CPU 활용률이 떨어지게 된다.
동시에 돌아가는 프로세스의 개수를 증가하여 다중 프로그래밍의 정도를 높이면 CPU의 활용률이 증가하므로,
운영체제는 다중 프로그래밍의 정도를 높여야 한다고 판단하여 다른 프로세스를 시스템에 추가한다.
위 그림에서 알 수 있듯이 프로세스의 수가 많아지면 다중 프로그래밍의 정도가 높아져 CPU의 사용량이 증가한다.
그러나, 어느 임계값 이상으로 프로세스의 수가 많아지면 한 프로세스가 가지는 page의 수가 부족하게 되고,
그로 인해 page fault가 빈번히 일어나게 되면서 CPU 활용도가 떨어지게 된다.
요구 페이징과 스레싱
요구 페이징이 작동하는 이유는 지역성 모델 (Locality model) 때문이다.
즉, 실행중인 프로세스는 서로 겹쳐질 수 있는 여러 개의 지역으로 구성되며, 프로세스는 한 지역으로부터 다른 곳으로 이동한다.
아래 그림과 같이 메모리 참조 패턴은 지역성을 가진다.
그렇다면 스레싱이 발생하는 이유는 뭘까?
바로 프로세스의 모든 지역의 크기가 총 메모리의 크기보다 클 때 스레싱이 발생하게 된다.
쉽게 말해, 메모리의 어느 지역 단위로 프로세스가 실행되고 있는데, 프로세스가 사용하는 전체 지역의 크기가 총 메모리의 크기보다 크다면 page fault가 자주 일어나게 되어 스레싱이 발생하게 된다.
따라서 지역 혹은 우선순위 페이지 교체를 사용하여 효과를 제한해야한다.
작업 집합 모델 (Working set)
작업 집합 창 = 고정된 수의 페이지 참조
WSS : 한 프로세스의 작업 집합 = 가장 최근의 작업 집합 창에서 참조된 총 페이지 수
작업 집합 창이 너무 작을 경우 전체 지역을 포함하지 못함
작업 집합 창이 너무 클 경우 여러 지역성을 과도하게 수용한다.
작업 집합 창이 무한대의 크기라면 프로세스가 실행 중에 만난 모든 페이지의 집합을 뜻한다.
Memory compression
페이징의 대안으로 메모리 압축이 있다.
수정된 프레임들을 스왑 공간으로 페이지 아웃 하는 것 대신, 여러 프레임들을 하나의 프레임으로 압축하여 시스템이 스와핑 페이지들을 재정렬할 필요 없이 메모리의 사용을 줄일 수 있도록 할 수 있다.
가용 프레임 리스트에 6개의 프레임이 있는 상황을 생각해보자.
가용 프레임 리스트의 가용 프레임 개수가 페이지 교체의 기준이 되는 프레임 개수 임계치보다 떨어진다면,
LRU와 같은 페이지 교체 알고리즘이 4개의 프레임을 선택하여 가용 프레임 리스트로 위치시키게 된다.
(15, 3, 35, 26)
처음에는 이 프레임들이 수정된 프레임 리스트에 위치하게 된다.
통상적으로, 수정된 프레임 리스트는 다음에 스왑 공간으로 쓰여지며, 가용 프레임 리스트에게 사용가능하게끔 만든다.
다른 방법으로는 프레임의 개수를 압축시켜 한 페이지 프레임에 압축된 것을 저장할 수도 있다.
수정된 프레임들을 하나의 프레임으로 압축하여 시스템이 페이지 스와핑에 의존하지 않고도 메모리 사용량을 줄일 수 있다.
수정된 프레임을 스왑 공간으로 페이징 아웃하지 않는다.
위 그림에서는 프레임 15, 3, 35가 압축되어 프레임 7에 저장되고, 15, 3, 35 프레임들이 가용 프레임 리스트로 이동된다.
그리고 나중에 15, 3, 35 프레임 중 하나가 참조되면 page fault가 일어나고 압축된 프레임이 해제되어 다시 3개의 프레임들이 메모리에 restore된다.
커널 메모리의 할당
커널 메모리의 할당
커널 메모리는 사용자 메모리와는 다르게 처리된다.
보통 페이지 리스트와는 별도의 메모리 풀에서 할당 받는다. (가끔 가용 메모리 풀에서 할당 받음)
이렇게 커널 메모리가 별도로 관리되는 이유는
1) 커널은 다양한 크기의 자료구조를 위해 메모리를 할당 받음
2) 장치 I/O용 메모리와 같이 일부 커널 메모리는 연속적이어야 함
커널 프로세스에 할당되는 메모리를 관리하는 방법으로는 버디 시스템, 슬랩 할당이 있다.
버디 시스템
물리적으로 연속된 페이지로 구성된 고정된 크기의 세그먼트에서 메모리를 할당한다.
메모리는 이 세그먼트로부터 power of 2 allocator에 의해 2의 제곱 단위로 할당된다.
2의 제곱의 크기면 요청이 받아들여진다.
요청 값이 다음으로 큰 2의 제곱수로 반올림된다.
사용 가능한 것보다 작은 크기로 할당이 필요한 경우, 현재 청크가 다음으로 낮은 2의 제곱수의 크기의 버디들(buddies)로 분리되어 적절한 크기의 청크를 사용할 수 있을 때 까지 계속해서 분리된다.
예를 들어, 256KB 청크가 사용 가능할 때, 커널에서 21KB를 요청한 경우는 아래와 같다.
버디 시스템의 장단점은 아래와 같다.
- 장점 : 사용하지 않는 청크들을 더 큰 청크로 병합(coalesce)한다.
- 단점 : 단편화 (fragmentation)
슬랩 할당
슬랩 할당은 버디 시스템의 대체 전략이다.
슬랩(slab)은 물리적으로 인접한 하나 이상의 페이지를 말하고,
캐시(cache)는 하나 이상의 슬랩들로 구성된다.
각 커널 자료구조마다 하나의 캐시가 존재하고, 각 캐시는 객체들로 채워진다.
- 캐시가 생성될 때 free로 표시된 객체들로 채워짐
- 구조가 저장될 때 객체들은 used로 표시된다.
만약 슬랩이 사용된 객체로 꽉 찰 경우, 다음 객체는 빈 슬랩에 할당되고, 빈 슬랩이 없다면 새로운 슬랩이 할당된다.
장점은 단편화가 없으며2, 메모리 요청을 빠르게 처리한다.
기타 고려 사항
Pre-paging
프로세스를 시작할 때 많은 수의 page fault를 줄이기 위해 미리 올려놓는 것.
프로세스가 필요로 할 페이지들의 일부 혹은 전부를 참조되기 전에 미리 메모리로 가져온다
그러나 프리페이징 된 페이지가 사용되지 않으면 I/O와 메모리는 낭비된다.
s개의 페이지가 프리페이징 되고 그 중 a개의 페이지가 사용된다면
s a 개의 페이지 폴트를 줄인 비용이 s (1-a) 개의 불필요한 페이지를 프리페이징 한 비용보다 큰지 확인해야 한다.
페이지 크기
페이지 크기를 선택할 때에는
단편화, 페이지 테이블 크기, 정밀도, I/O 오버헤드, 페이지 폴트 횟수, 지역성, TLB 크기 및 효과 등을 고려하여야 한다.
항상 2의 제곱수여야 하며, 일반적으로 4096B ~ 4,194,304B의 범위를 가진다.
평균적으로 시간이 지남에 따라 크기가 커진다.
TLB Reach
TLB Reach : TLB에서 접근할 수 있는 메모리 공간의 크기 = TLB 크기 * 페이지 크기
이상적으로 각 프로세스의 작ㄷ업 집합은 TLB에 저장된다.
그렇지 않은 경우에는 페이지 폴트의 빈도가 높아진다.
여러 페이지 크기를 제공
더 큰 페이지 크기가 필요한 응용 프로그램들이 파편화를 증가시키지 않고 페이지들을 사용할 수 있다.
프로그램 구조
2차원 배열에서 각 행은 한 페이지에 저장되므로 프로그램 구조에 따라 페이지 폴트의 빈도가 달라질 수 있다.
// 페이지 폴트가 128번 발생
for (i = 0; i < 128; i++)
for (j = 0; j < 128; j++)
data[i][j] = 0;
// 페이지 폴트가 128*128 = 16384번 발생
for (i = 0; i < 128; i++)
for (j = 0; j < 128; j++)
data[j][i] = 0;I/O 상호 잠금
페이지가 메모리에 고정(pinning)되는 것이 필요할 때가 있다.
예를 들어, 장치에서 파일을 복사하는 데 사용되는 페이지는 페이지 교체 알고리즘에 의해 교체되지 않도록 잠겨야 한다.
