23.07.15 최초 작성
23.12.11 내용 추가 (Page Fault, Page를 활용한 가상 메모리 기술, Swapping)

OS가 가상 주소를 통해 메모리를 관리하는 방법.

1. Demand Paging

페이지 단위로 Swapping을 하는 방식이며 페이지를 사용하는 시스템에서 사용할 수 있다. 프로세스 전체를 외부 저장장치에 저장하지 않고 프로세스의 페이지 일부를 외부 저장장치에 저장한다.

1. 프로세스를 새로 생성하는데 메모리에 공간 부족
2. 기존 프로세스의 페이지의 일부를 외부 저장장치에 저장 & Page Table에 알림(V bit 비활성화)
3. 새로운 프로세스 메모리에 할당
4. 기존 프로세스의 옮겨진 페이지를 읽으려 하면 OS에 요청(Page Fault 익셉션 발생 & Page Fault Handler 실행)
5. Page Table을 참고해 다른 프로세스의 페이지를 외부 저장장치에 저장하고 빈 공간에 기존 프로세스의 페이지를 저장함

1.1 Page Fault

• V bit가 활성화되지 않은 상태에서 page를 접근하는 경우 발생
• major faults
  • 가상 페이지는 유효하나 해당 가상 페이지가 메모리에 적재되지 않은 경우
  • page fault handler는 해당 가상 페이지의 디스크 위치를 찾아 메모리에 적재
• minor fault
  • 가상 페이지는 유효하나 PTE의 V bit가 활성화되지 않은 경우
  • 지연 할당(가상 페이지에만 주소를 할당하고 나중에 실제로 접근할 때 물리 프레임 할당)에 사용
• invalid page fault
  • 유효하지 않은 가상페이지에 접근한 경우 (segmentation fault)

2. Page를 활용한 가상 메모리 기술

2.1 Shared Memory

• 가상 메모리를 활용해 프로세스가 같은 물리적 메모리 공간을 공유할 수 있도록 하는 방법
• 각 프로세스의 Page Table Entry에 동일한 물리 프레임 저장
• 공유 페이지가 퇴거되는 경우 연관된 Page Table Entry가 clear되어야 함

2.2 Memory Mapped Files

• 메모리 접근을 통해 디스크 파일 접근하는 방법
• mmap()을 통해 접근
  • mmap()을 통해 메모리를 할당하면 가상 메모리 영역에 V bit가 비활성화됨
  • 접근 시 Page Fault
• 장점
  • I/O가 적게 일어남
  • 여러 프로세스가 파일을 공유해 접근 가능

2.3 Copy-on-Write

프로세스를 복사(fork())할 때 Shared Memory 영역은 Virtual Memory Table에서 같은 공간을 가르키도록 함.
만약 해당 영역에 Write 할 수 있는 권한을 가진 상태라면 이 Write 권한을 임시로 없앤다. Write 요청이 들어오면 내용을 다른 영역에 복사하고 그 값을 수정한 뒤 Virtual Memory Table에서 가상 주소가 복사한 주소 값을 가리키게 한다. 이 때 Write 권한이 다시 활성화된다.
원본 프로세스 또한 위 과정을 거쳐 두 프로세스가 Write요청을 받으면 처음과는 다른 메모리를 할당받게 된다.
내용이 바뀌지 않으면 가상 주소가 공유 영역을 가리키되 내용이 바뀌면 다른 주소를 가리키게 된다.

해당 방법은 힙 영역에 데이터를 할당할 때에도 쓰인다. 만약 malloc()과 같은 함수로 메모리를 초기값 없이 할당하면 "Zero Page"라는 페이지에 매핑된다. 이 페이지는 Write 권한이 없는 Read 권한만 있는 영역이며 만약 이 영역에 데이터를 쓴다면 Copy-on-Write 방식으로 값이 입력된다.

2.4 TLB

• Page를 활용해 메모리를 참조 시 성능이 느려질 수 있음
  • Page Table접근, 물리 메모리 접근의 순서로 2번의 주소 공간 접근이 발생
  • Page Table의 단계가 많아질수록 성능 하락
  • TLB활용해 해결

3. VM Feature

3.1 운영체제와 프로세스의 주소공간

운영체제는 일반적으로 가상 주소공간을 2개로 나눠(User Address Space / Kernel Address Space) 관리한다. Kernel Address Space의 경우 Shared Page로 관리되며 프로세스끼리 공유한다.

3.2 Frame Allocation

한정된 페이지를 프로세스에 분배하는 방식.
1. Equal Allocaition
모든 프로세스가 동일한 페이지를 분배받음
2. Proportional Allocation
각 프로세스의 크기에 맞춰 페이지를 분배받음
3. Priority Allocation
프로세스의 중요도에 따라 페이지를 분배받음

3.3 Thrashing

물리 메모리가 모든 프로세스의 Working Set을 담을 수 없을 때 발생하는 성능 저하. Working Set이 메모리의 용량보다 훨씬 많을 때 Phasing이 자주 일어나게 되고 이는 성능 저하로 이어지게 된다.
Working Set : 프로세스가 사용하고 있는 페이지의 집합

4. Page Replacement

• Page Fault penalty가 크기 때문에 Page Fault Rate를 줄이기 위한 Page Replacement 원칙을 선정

• 프로세스는 할당된 가상 메모리 전체가 필요하지 않으므로 필요한 데이터만 적재하고 그렇지 않은 Page는 디스크로 적재

• Swapping

  • 페이지 단위로 필요 없어진 데이터를 디스크에 저장 (Swap-in)하고 필요한 페이지를 메모리로 옮기는 (Swap-out) 작업
  • 디스크 공간의 일부를 할당 해 시스템에서 제공하는 가상메모리의 크기 확장
  • 리눅스에는 메모리에 임계치를 두고 유휴 메모리가 이를 넘어서면 Swapping실행

4.1 OPT (Belady's Algorithm)

• 가장 나중에 쓰일 페이지를 제거하는 방법. 어떤 상황에서도 가장 낮은 Fault Rate를 보임.
  하지만 나중에 쓰일 페이지를 추측해야 하기 때문에 구현이 어렵다는 단점이 있다.

4.2 FIFO

• 가장 오래된 페이지를 제거하는 방법. 적용하기 쉽고 가장 오래된 페이지가 안쓰여 성능이 향상될 수도 있지만 단순 가정이기 때문에 그렇지 않을 수 있다.
• 프레임 갯수가 늘어나도 Page Fault가 많이 발생할 수도 있다(Belady's Anomaly).

4.3 LRU (Least Recently Used)

• 최근에 참조된 횟수가 적은 페이지를 제거하는 방법.
• 프레임이 늘어날수록 성능이 향상된다(Stack Algorithm).

4.3.1 Additional Reference Bits Algorithm

Reference Bit를 비교해 가장 작은 값을 가진 페이지를 제거한다. Reference Bit의 값은 참조되면 1이 입력되고 다음 작업에서 각 비트가 오른쪽으로 이동한다.

4.3.2 Second Chance Algorithm

clock 알고리즘으로 널리 알려진 방식.

5. Issue in Page Replacement

5.1 Global vs Local Page Replacement

1 Global Page Replacement

• 전체 Frame 중 교체할 페이지를 선택하는 방법.

• 구현이 쉽고 최적의 성능을 이끌어내지만 프로세스마다 실행 시간의 편차가 크다.

  2 Local Page Replacement

• 요청한 프로세스의 Frame 중 필요없는 영역을 교체할 페이지로 선택하는 방법.

• 성능이 일정하지만 구현이 어렵고 메모리의 활용성이 떨어진다.

5.2 Page Pining

Page Replacement에 의해 영향받지 않는 Page.

5.3 Paging Virtual Memory

Heap 과 Stack 영역은 R/W이 가능해 데이터가 변경될 경우 Zero Page에 저장되며 Page 정보를 저장해야 한다(CoW).
Data 영역의 경우 R/W이 가능하며 CoW 방식으로 수정된다.
두 영역 모두 CoW 이후 Swap File에 백업을 해야 한다.