10. 가상 메모리

강의 목표

• 가상 메모리 기법의 개념을 이해한다.
• 가상 메모리 기법에 대한 여러 의문점들과 해결에 대해 이해한다.
  스레싱, 페이지 테이블 구성, 페이지 폴트, 페이지 할당, 스왑 영역
  프레임 할당, 작업 집합, 페이지 교체, 쓰기 시 복사
• 요구 페이징의 개념과 페이지 폴트에 대해 안다.
• 요구 페이징 시스템에서 프로세스의 실행 과정을 이해한다.
• 프로세스의 생성에 사용되는 쓰기 시 복사에 대해 이해한다.
• 연속된 페이지 폴트로 인해 심각한 디스크 입출력이 발생하는
  스래싱 현상에 대해 이해한다.
• 참조의 지역성, 작업 집합, 페이지 폴트 사이의 관계에 대해 안다.
• 페이지 교체의 개념과 다양한 페이지 교체 알고리즘을 이해한다.
  최적 교체, FIFO, LRU, Clock

01. 물리 메모리의 한계

1.1 주소 공간과 물리 메모리

물리 메모리

• 컴퓨터에 장착된 실제 메모리
• 최대 크기는 CPU에 의해 제한됨
• 물리 메모리의 크기는 설치하기에 달림
  대부분 비용 문제로 인해 프로세스의 주소 공간보다 작게 설치됨

프로세스 주소 공간

• 프로세스가 실행 중에 닿을 수 있는 최대 주소 범위
• 주소 공간의 크기는 고정 크기

1.2 물리 메모리의 크기 한계

"1. 운영체제는 물리 메모리보다 큰 프로세스를 실행할 수 있는가?"

"2. 운영체제는 여러 프로세스를 합쳐 물리 메모리보다 클 때,
이들을 동시에 실행시킬 수 있는가?"

질문에 숨어있는 전제

• 프로세스가 실행되려면 반드시 프로세스 전체가 물리 메모리에 적재돼야 함

→ 프로세스가 완전히 메모리에 적재돼야 실행이 가능한 것일까?

02. 가상 메모리 개념

2-1. 가상 메모리 개요

가상 메모리(virtual memory)

• 물리 메모리보다 큰 프로세스나 여러 개의 작은 프로세스를 동시에 실행시켜,
  무한대의 메모리가 있다고 느끼도록 하는 메모리 관리 기법

가상 메모리 기법의 핵심

1) 물리 메모리를 디스크 공간으로 확장

• 프로세스를 물리 메모리와 하드 디스크(보조기억장치)에 나누어 저장
• 프로세스나 사용자가 프로세스를 실행하기에
  충분히 큰 물리 메모리가 있다고 착각하게 만드는 메모리 관리 기술

2) 스와핑(swapping)

• 물리 메모리가 부족할 때, 실행에 필요하지 않은 부분을 하드 디스크로 이동
• 실행에 필요할 때, 하드 디스크에서 물리 메모리로 이동

가상 메모리 개념

1. 운영체제는 물리 메모리 영역을 하드 디스크로 확장

• 프로세스를 물리 메모리와 하드 디스크에 나누어 저장

2. 프로세스 실행 시 프로세스 전체가 물리 메모리에 적재되어 있을 필요 없음

• 현재 실행에 필요한 코드나 데이터의 일부분만 있으면 실행 가능
• 나머지는 하드 디스크에 있다가 필요할 때 적재해도 됨
  실행 속도의 저하는 발생 가능

3. 운영체제는 물리 메모리의 빈 영역이 부족하게 되면,
물리 메모리의 일부분을 하드 디스크로 옮겨 물리 메모리의 빈 영역 확보

• 이 방식으로 많은 프로세스를 메모리에 적재 가능
• 다중프로그래밍 정도(DOM)를 높임, CPU 활용률과 처리율 높임

4. 물리 메모리를 확장해 사용하는 디스크 영역을 스왑 영역(swap area)이라고 함

• 스왑-아웃: 물리 메모리의 일부를 스왑 영역으로 옮기는 작업
• 스왑-인: 스왑 영역에서 물리 메모리로 가지고 오는 작업
• 프로세스는 물리 메모리 + 스왑 영역 + 실행 파일에 분산되어 있음

5. 사용자는 컴퓨터 시스템에 무한대의 메모리가 있는 것으로 착각

• 사용자는 큰 프로그램을 작성하는 데 부담 없음
• 사용자는 여러 프로그램을 동시에 실행시키는 데 부담 없음

6. 가상 메모리는 운영체제마다 구현 방식 다름

2.2 가상 메모리 구현

요구 페이징(demand paging)

• 페이징 기법을 토대로 프로세스의 일부 페이지들만 물리 메모리에 할당하고,
  페이지가 필요할 때 물리 메모리를 할당 및 적재시키는 메모리 관리 기법

• 페이징 + 스와핑

요구 세그먼테이션(demand segmentation)

• 세그먼테이션 + 세그먼트 스와핑

2.3 가상 메모리 기법에 대한 의문들

(스래싱 문제)
물리 메모리와 디스크의 스왑 영역 사이에 입출력이 너무 빈번히 발생하지 않는지?

(페이지 테이블)
페이지 테이블은 어떻게 구성할지?

(페이지 폴트)
가상 주소를 물리 주소로 변환할 때
페이지가 프레임에 없는 경우 어떻게 처리할지?

(페이지 할당)
프로세스의 어떤 페이지를 물리 메모리에 두고
어떤 페이지를 하드 디스크에 둘 지?

(스왑 영역)
디스크의 스왑 영역 크기는 얼마가 적당한지?

(프레임 할당)
프로세스별로 할당할 프레임의 개수를 몇 개로 정할지?

(작업 집합)
프로세스는 일정 시간 범위에서 실행 중에
몇 개의 프레임을 실제로 사용하고 있는가?

(페이지 교체 알고리즘)
필요한 페이지를 디스크로부터 읽어 오기 위해 프레임 중 하나를 비워야 하는데 어떤 프레임을 비워야 하는지? 비워야 하는 프레임이 결정되면
그 프레임에 저장된 페이지는 어떻게 처리할 것인지?

(쓰기 시 복사)
프로세스가 자식 프로세스를 생성하면
자식 프로세스의 메모리 공간은 어떻게 되는지?

03. 요구 페이징

3.1 요구 페이징 개념

요구 페이징(demanding paging)

• 현재 실행에 필요한 일부 페이지만 메모리에 적재하며
  나머지는 하드디스크에 두고, 페이지가 필요할 때 메모리에 적재하는 방식

• 프로세스의 페이지가 있는 디스크 영역 = 스왑 영역 + 실행 파일
  스왑 영역: 올라왔다가 쫓겨난 페이지
  실행 파일: 미처 올라오지 않은 페이지

• 요구(demand): 페이지가 실행에 필요할(참조될) 때

• 프로세스를 실행시킬 때 실행에 필요한 첫 페이지만 메모리에 적재하여 실행,
  실행 중 다음 페이지가 필요하면 그 때 적재시킴

3.2 요구 페이징 구성

디스크의 스왑 영역

스왑 영역(swap area)

• 메모리가 부족할 때, 메모리를 비우고 페이지를 저장해두는 하드 디스크 영역
  리눅스: 디스크 내 특별한 위치 혹은 스왑 파티션에 위치
  Windows: C:/pagefile.sys 파일을 스왑 영역으로 사용

• 운영체제 설치 시 시스템 관리자에 의해 위치와 크기가 결정됨

• golden rule: 스왑 영역의 크기는 컴퓨터에 설치된 물리 메모리의 2배
  최근에는 메모리 량이 커짐으로써 물리 메모리의 1/2 정도로 추천
  레드햇 운영체제의 경우 물리 메모리의 20% 정도를 추천
  현대는 2GB ~ 32GB정도로 설정

페이지 테이블

테이블 항목(Page Table Entry, PTE)

• present/valid 비트: 페이지가 메모리에 적재되어 있는지
  1: 물리 메모리에 적재
  0: 디스크에 적재

• modified/dirty 비트: 페이지가 메모리에 적재된 후 수정되었는지
  1: 해당 페이지가 프레임에 적재된 이후 수정되었음
  비트가 1인 경우엔 물리 메모리에서 쫓겨날 때, 스왑 영역에 저장
  0: 수정된 적이 없으며 스왑 영역에 있는 상태와 동일함
  물리 메모리에서 쫓겨날 때, 디스크의 데이터와 동일하므로 버림

• 코드가 담긴 페이지는 수정될 일이 없지만,
  데이터, 힙, 스택의 페이지들은 물리 메모리에 적재된 후 수정될 수 있음

• physical address 필드
  present == 1
  이 필드에 물리 프레임의 번호가 기록됨
  present == 0
  이 필드에 디스크 주소(디스크 블록 번호, disk block number)가 기록됨
  이 주소는 스왑 영역의 주소이거나 실행 파일에 대한 주소이다.

페이지 폴트(page fault) 또는 페이지 부재

• CPU가 액세스하려는 페이지가 물리 메모리에 없을 때 발생

• CPU가 가상 주소를 출력했을 때,
  present == 0이면 MMU에 의해 페이지 폴트 발생

• 페이지 폴트 발생 시
  운영체제의 페이지 폴트 핸들러(page fault handler) 코드 실행

• 물리 메모리에서 빈 프레임을 할당받고 요청된 페이지 적재

• 희생 프레임(victim frame)
  물리 메모리에 빈 프레임이 없는 경우 희생되는 프레임
  이 때 modified == 1이면, 스왑 영역에 저장
  희생 프레임은 현재 실행 중인 프로세스의 페이지 중 하나일 수 있고,
  다른 프로세스의 페이지일 수 있음

• 스왑-인(swap-in) 또는 페이지-인(page-in)
  페이지를 스왑 영역으로부터 프레임에 적재하는 것

• 스왑-아웃(swap-out) 또는 페이지-아웃(page-out)
  프레임에 적재된 페이지를 스왑 영역에 저장하는 것

• 페이지 히트(page hit)
  페이지 폴트와 반대로
  CPU가 발생한 가상 주소의 페이지가 메모리 프레임에 있을 때

TIP

Windows 운영체제의 스왑 영역, pagefile.sys

• 컴퓨터의 RAM의 크기가 큰 경우에도 필요함
• 페이지의 파일은 로그아웃 시 사라짐

3.3 페이지 폴트 자세히 알기

mov eax, 10
mov [11111234], eax

3.4 요구 페이징 시스템에서 프로세스 실행

1. 프로세스의 시작 페이지 적재

2. 여러 번의 페이지 폴트를 통해 실행 파일로부터 페이지들 적재

• 프로세스의 실행 초기에는 전역 변수나 스택이 담긴 페이지가 메모리에 없음
  따라서 페이지 폴트가 연이어 발생한다.
  폴트가 발생한 페이지는 실행 파일이나 스왑 영역에 존재한다.

• 처음 액세스하는 코드나 데이터 페이지는 실행 파일에서 찾아 적재
  코드가 들어있는 페이지는 스왑-아웃시키지 않으므로
  항상 실행 파일로부터 적재한다.

• 한번 적재된 페이지는 스왑 영역에서 적재

• 초기에는 실행 파일에서, 시간이 지나고 나면 스왑 영역으로부터 주로 적재됨
  이러한 과정은 운영체제에 따라 다르게 구현됨
  
  

3. 메모리가 부족하면 스왑-아웃/스왑-인

4. 스왑-아웃된 페이지 100을 다시 스왑-인

5. 코드가 적재된 페이지(읽기 전용)의 스왑-아웃/스왑-인

• 페이지 30은 코드가 들어 있는 읽기 전용 페이지(modified == 0)이므로
  스왑 영역에 적재할 필요 없음
• 다음에 함수 f()를 호출하기 위해선 실행 파일에서 적재

6. 수정되지 않은 페이지가 희생 페이지로 선택될 때

• modified == 0인 페이지가 희생 페이지로 선택되면,
  해당 페이지는 프레임에서 버려짐
  다시 적재할 경우 실행 파일이나 스왑 영역에서 다시 적재하면 됨

요구 페이징에서의 스왑 정리

• 프로세스가 적재될 때 최소 한 페이지가 적재되고 프로세스가 실행됨

• 프로세스의 실행 중에 다른 페이지가 필요하면 그 때 페이지가 프레임에 적재

• 희생 페이지의 modified == 1
  스왑 영역에 저장되고 프레임에서 비워짐

• 희생 페이지의 modified == 0
  스왑 영역에 저장하지 않고 프레임에서

• 스왑 아웃된 페이지가 다시 필요해지면 그 때 스왑 영역에서 프레임에 적재

• 코드가 적재된 페이지는 항상 modified == 0이기 때문에
  항상 실행 파일로부터 적재됨

순수 요구 페이징(pure demand paging)
아무 페이지도 물리 메모리에 적재하지 않고 프로세스를 실행시키고,
첫 페이지를 실행할 때 적재

스왑 영역은 반드시 필요한가?

• 스왑 영역을 디스크에 정해진 영역에 만듦으로써
  스왑 영역에서 단 번에 페이지를 읽거나 쓸 수 있음

TIP 요구 페이징에서 프로세스의 각 영역에 대한 적재 및 스왑 정리

코드가 액세스될 때

• 코드 페이지는 읽기 전용이므로 항상 modified == 0이다.
  따라서 항상 실행 파일로부터 적재한다.

데이터가 액세스될 때

• 초기화된 데이터 영역(initialized data)과
  초기화되지 않은 데이터 영역(uninitialized data, BSS)으로 나뉨

int n[1000];  // 초기화하지 않음
              // 아직 물리 프레임 할당 안 됨

x = n[0];     // 처음으로 액세스
              // → 물리 프레임 할당
              // → 프레임 전체를 0으로 채움 (쓰기 발생)
              // → m비트 = 1
              // → 그 다음 n[0]의 값(0)을 읽어옴

데이터 영역에서 초기화되지 않은 데이터는 적재 후에 modified == 1

힙을 액세스할 때

• 프로세스가 힙으로부터 동적 메모리를 요청하면
  빈 프레임을 할당받고 초기화하지 않기 때문에 modified == 0

• 동적 메모리에 대한 액세스 발생 시 modified == 1
  이후부터는 스왑 영역에서 적재

스택을 액세스할 때

• 함수가 호출되어 스택이 필요하게 되면
  빈 프레임을 할당받고 초기화하지 않기 때문에 modified == 0

• 스택 페이지에 대한 액세스 발생 시 modified == 1

3.5 쓰기 시 복사(COW, copy on write)

• 프로세스의 생성과 시작은 메모리 할당과 페이지의 메모리 적재에서 시작됨

완전 복사

• 부모 프로세스의 모든 페이지를 완전히 복사

• 프로세스는 부모 프로세스에 의해 생성되며, 시스템 호출을 통해서만 이루어짐
  시스템 호출 함수는 운영체제에 따라 다름

완전 복사의 비효율성

• 많은 응용프로그램들은 fork()로 자식 프로세스 생성 후
  execlp()을 이용하여 곧바로 다른 프로그램을 실행시키도록 작성되기 때문

• execlp()를 호출하여 할당받은 메모리를 모두 반환하고
  실행 파일로부터 다시 페이지를 적재
  fork() 메모리 복사 작업이 허사가 됨

int childPid = fork(); // 쉘을 복제한 자식 프로세스 생성
if (childPid == 0) { // 자식 프로세스 코드
	execlp("/bin/ls", "ls", NULL); // /bin/ls 파일을 적재하여 실행
}

그림 (b)에서 곧바로 다른 프로세스가 실행됨

쓰기 시 복사(copy on write, COW)로 완전 복사 문제 해결

• 완전 복사의 비효율을 해결하는 방법

• 부모 프로세스의 메모리를 복사하지 않고,
  자식 프로세스가 부모의 메모리를 완전히 공유하고 둘 다 실행되도록 함

• 메모리 쓰기 발생 시, 운영체제에 의해 부모든 자식이든
  쓰기가 발생한 페이지에 대해서만 새 프레임을 할당받아 복사함
  읽는 경우엔 복사하지 않음

• 쓰기 시 복사 기법을 위해 페이지 테이블 항목에
  보호 필드(protection 비트)가 추가됨
  R: 읽기만 가능
  RW: 읽고 쓰기 가능

• 자식 프로세스가 페이지 1에 쓰기 실행 시, protection == R이므로
  MMU에 의해 오류(protection fault)가 발생함

• 커널의 오류 처리 핸들러가 실행됨 핸들러는 물리 메모리에 새 프레임을 할당받고 오류가 발생한 페이지를 새 프레임에 복사
  이후 부모 자식 모두 페이지 테이블의 protection == RW로 수정

페이지 테이블의 항목

-present, modified, protection, physical address

-reference: 1이면 페이지가 최근에 참조되었음

쓰기 시 복사의 장점

• 프로세스 생성 시간 절약

• 메모리 절약

탐구 10-1. 요구페이징에 대해 생각해 볼 이슈

• 오늘날 대부분의 운영체제에서
  커널 코드와 커널 데이터가 적재된 프레임은 스왑-아웃되지 않음

3.6 페이지 폴트와 스래싱(thrashing)

페이지 폴트와 디스크 I/O

• 페이지 폴트 발생 시 필연적으로 디스크 입출력이 동반됨
  디스크 입출력을 줄이기 위해 페이지 폴트의 횟수를 줄여야 함

스레싱(thrashing)

• 페이지 폴트가 계속 발생하여, 메모리 프레임의 페이지가 반복적으로 교체되고
  디스크 입출력이 심각하게 증가하고, CPU 활용률이 대폭 감소하는 현상
  빈번한 페이지 폴트로 인한 디스크 입출력 증가 현상
  디스크 스래싱(disk thrashing) 이라고도 함

스래싱의 원인

1) 다중 프로그래밍 정도(DOM)가 과도한 경우

• 실행되는 프로세스의 개수가 많아지면
  각 프로세스에게 할당되는 메모리 프레임의 개수가 작아짐
  프로세스가 필요한 페이지들을 충분히 적재하지 못해 페이지 폴트 발생

2) 메모리 할당 정책이나 페이지 교체 알고리즘이 잘못된 경우

• 프로세스가 실행에 필요한 페이지 수보다 작은 수의 프레임이 할당된 경우

• 곧 사용될 페이지를 교체하는 잘못된 페이지 교체 알고리즘

3) 컴퓨터 시스템에 설치된 메모리가 절대적으로 작은 경우

4) 특정 시간대에 너무 많은 프로세스를 실행한 경우

스레싱 현상 관찰

• 동시에 실행되는 프로세스의 개수가 늘어날수록(DOM이 커질수록)
  CPU의 유휴 시간이 줄어 CPU 활용률 증가

• 다중프로그래밍 정도가 임계점을 넘어가면 스래싱 발생

(a) 메모리가 작은 경우

• CPU 활용률이 100%에 못 미친 상태에서
  메모리 포화가 먼저 일어나고 스레싱이 발생함

(b) 메모리가 많은 경우

• CPU의 활용률이 100%에 달해도
  메모리에 여유가 있기 때문에 스레싱이 발생하지 않음
  동시에 실행되는 프로세스의 수가 증가하면 결국 스레싱이 발생함

CPU의 활용률과 디스크 I/O율의 변화를 조사하면 스래싱 발생 여부 판단 가능
스레싱 감지 기법은 운영체제마다 다름

스레싱 해결 및 예방

• 다중프로그래밍 정도의 시스템 허용치 낮추기
• 컴퓨터의 메모리(RAM) 용량을 늘리기
• 하드 디스크 대신 SSD 사용하기

04. 참조의 지역성과 작업 집합

4.1 프로그램의 실행 특성

• 참조의 지역성
• 작업 집합

위의 두가지 특성으로 인해 페이지 폴트를 동반함에도 불구하고
요구 페이징을 사용함

4.2 참조의 지역성 (locality of reference)

• CPU가 프로그램을 실행하는 동안
  짧은 시간 범위 내에 일정 구간의 메모리 영역을 반복 참조하는 경향

참조의 지역성의 특징

• 모든 프로그램에서 나타나는 기본적인 실행 특성

• 프로세스의 실행 중 메모리가 균일하게 참조되지 않고
  특정 부분이 집중 참조됨

• 지역성(locality) 또는 지역성의 원리(principle of locality)라고도 부름

• 프로세스는 최근에 참조한 데이터와 코드를 다시 참조(사용)하는 경향이 있음

• 프로세스가 실행되는 동안 메모리 영역을 옮겨 다니며 나타남

• 90/10 규칙
  프로그램 코드의 10%가 전체 실행 시간의 90%를 소비

• 실행 초기에는 페이지 적재로 인한 페이지 폴트가 자주 발생하지만,
  참조의 지역성으로 인해 일정 시간 후 페이지 폴트는 드물게 발생

• 운영체제는 가까운 미래 어떤 페이지를 액세스할 것인지
  합리적인 예측이 가능하며, 이를 통해 페이지 교체 정책을 폄
  미래에 사용될 페이지가 스왑-아웃되지 않는 등

참조의 지역성의 2가지 형태

시간 지역성 (temporal locality)

• 지금 참조되는 주소(또는 페이지)가 가까운 미래에 다시 참조될 가능성이 있음
  코드나 데이터, 자원 등이 다시 사용되는 특성
  반복문이 대표적

공간 지역성 (spatial locality)

• 지금 참조되는 주소의 주변 번지들(동일한 페이지)이
  가까운 미래에 다시 참조되는 특성
  배열이나 프로그램의 코드가 그 예

4.3 작업 집합과 페이지 폴트

작업 집합 (working set)

• 프로세스가 일정 시간 범위 내에 참조한 페이지들의 집합

• 작업 집합은 현재 프로세스의 실행에 필요한 페이지들의 집합
  작업 집합에 포함된 페이지들이 모두 메모리에 적재되어 있다면,
  프로세스는 한동안 페이지 폴트 없이 높은 성능을 가짐

• 참조의 지역성으로 인해 작업 집합은 뚜렷이 형성되며,
  작업 집합에 포함된 페이지의 개수도 크지 않음
  운영체제는 작업 집합을 적재할 수 있는 정도의 메모리를 할당하고,
  해당 페이지가 스왑-아웃되지 않도록 관리함

• 프로세스의 실행 중 계속되는 페이지 폴트는
  프로세스의 집합 페이지 형성 과정이라고 생각해도 됨

작업 집합 형성 사례

• 페이지 2, 100, 5, 20의 작업 집합이 형성됨

작업 집합과 시간 범위

• 작업 집합은 특정 시간 범위 내의 프로세스가 실행에 필요한 페이지들의 집합

• 어떤 페이지는 몇 번 액세스되지 않을 수 있음에도 해당 시간의 작업 집합임

• 시간 범위가 클수록
  작업 집합의 크기(작업 집합에 포함된 페이지 수)도 늘어남

작업 집합 이동 (working set shift)

• 프로세스의 실행 과정에서 시간에 따라 참조의 지역성이
  다른 메모리 영역에서 나타나며 작업 집합이 변해감

다중프로그래밍 시스템에서 스래싱 발생 관측과 예방

• 여러 프로세스들에게서 작업 집합에 포함된 페이지들이
  충분히 메모리에 올라와 있지 않은 경우 스레싱 발생

• 각 프로세스에게 작업 집합 페이지를 수용할
  메모리를 할당하는 알고리즘을 통해 스래싱이 예방 가능함

4.4 요구 페이징의 필수 알고리즘

• 요구 페이징의 성능은 운영체제가 작업 집합에 속한 페이지들을
  메모리에 적재한 상태로 프로세스를 실행시킬 수 있는가에 달림
  이를 위해 운영체제는 다음 2개의 알고리즘이 필요함

프레임 할당(frame allocation)

• 프로세스에게 할당할 메모리 프레임의 개수를 결정하는 문제

• 프로세스의 작업 집합에 포함된 페이지들을 충분히 수용할만한 개수의
  메모리 프레임을 할당하여 페이지 폴트를 줄이는 것이 목표

페이지 교체(page replacement)

• 페이지 폴트 발생 시, 빈 메모리 프레임이 없는 경우
  스왑-아웃 시킬 페이지를 선택하는 문제
  작업 집합에 속한 페이지 스왑-아웃 시, 곧바로 페이지 폴트가 발생

• 작업 집합에 속하지 않은 페이지를 교체 페이지로 선택하는 것이 목표

05. 프레임 할당

5.1 프레임 할당의 목표

• 프로세스의 작업 집합에 포함된 페이지들을 충분히 수용할만한 개수의 메모리 프레임을 할당하여 페이지 폴트를 줄이고 스레싱이 발생하지 않도록 하는 것

5.2 균등 할당과 비례 할당

균등 할당(eqaul allocation)

• 프로세스의 크기와 관계없이 모든 프로세스에게 동일한 개수의 프레임 할당

• 단순하다는 장점이 있지만
  작은 프로세스에게는 필요 이상의 많은 프레임을 할당하고,
  큰 프로세스는 프레임이 부족하여 페이지 폴트가 자주 발생할 수 있음

비례 할당(proprotional allocation)

• 프로세스의 크기에 비례하여 프레임을 할당

• 프로세스의 페이지 폴트를 줄일 수 있지만,
  프로세스 크기를 명확히 알기 여러움
  코드와 데이터의 크기는 알 수 있지만, 힙이나 스택은 알 수 없음

프로세스에게 할당해야 할 최소 프레임 개수

• 프로세스 당 10개 미만의 프레임을 할당하는 컴퓨터 시스템은 거의 없음
  최소 50개에서 몇백개 몇 만개까지도 가능

5.3 프로세스에게 할당할 적정 프레임 수

• 프로세스에게 할당해줄 프레임의 적정 개수는
  작업 집합을 약간 넘나드는 수준이 적합함

TIP. Windows의 프레임 할당(작업 집합 관리) 사례

• Windows에서는 프레임의 최소, 최대 수를 정해 놓고 프로세스를 시작함
  이를 working set 이라고 함

• 프로세스를 생성할 때 할당할 프레임의 최소 수를 예약해놓고
  프로세스가 프레임을 요구하면 예약된 최소 프레임까지 계속 할당함

• 그 후에도 할당이 일어나지만, 정해진 최대 개수를 넘어 할당해주지 않음
  가용 메모리가 충분한 경우엔 프레임을 최대로 사용하고 있는 프로세스에게
  프레임의 할당 최대치를 증가

• working set trimming 알고리즘
  시스템의 전체 메모리 사용량을 관측하다가 일정 수준 이상의 메모리가 사용되고 있으면, 프로세스들에게 할당된 프레임의 개수를 줄임
  정해놓은 가용 메모리가 확보될 때 까지 페이지들을 계속해서 스왑-아웃시킴
  SetProcessWorkingSetSize(), SetProcessWorkingSetSizeEx()

• 현재 메모리 사용량은 프로세스의 크기가 아닌,
  프로세스가 현재 할당받아 사용하고 있는 프레임의 크기
  프로세스의 모든 페이지가 적재된 것도 아님

06. 페이지 교체

6.1 페이지 교체의 정의(page replacement)

• 요청된 페이지가 메모리 프레임에 없고,
  페이지를 적재할 빈 프레임도 없는 경우,
  메모리 프레임 중 하나를 선택하여 비우고 요청된 페이지를 적재하는 과정

• 희생 프레임(victim frame)
  비우기로 선택된 프레임

• 희생 페이지(victim page)
  비우기로 선택된 프레임에 저장되어 있던 페이지
  modified/dirty == 1 이라면 하드 디스크의 스왑 영역에 스왑-아웃

6.2 페이지 교체의 목표

• 희생 프레임 혹은 희생 페이지를 선택하는 문제

• 현재 메모리는 어떤 프로세스의 작업 집합에 속했지만 지금은 아닌 페이지들,
  그리고 현재 어떤 프로세스의 작업 집합에 포함된 페이지들이 혼재된 상태

• 현재 작업 집합에 포함되지 않거나, 미래에 참조되지 않을 페이지를
  희생 페이지로 선택하여 페이지 폴트의 횟수를 줄이는 것

6.3 희생 프레임의 선택 범위

지역 교체(local replacement)

• 페이지 적재를 요청한 프로세스에게 할당된 프레임들 중
  희생 프레임을 선택하는 방법
  per-process replacement

• 다른 프로세스에게 할당된 프레임을 건들지 않기 때문에
  페이지 교체가 일어나는 프로세스에서 스래싱이 발생하더라도
  다른 프로세스로 전파되지 않음

전역 교체(global replacement)

• 프로세스에 상관없이 전체 메모리 프레임 중 희생 프레임을 선택하는 방법

• 일반적으로 지역 교체보다 페이지 폴트를 덜 유발시켜 더 효과적
  여러 운영체제들이 전역 교체를 사용하며, window는 혼합 사용

페이지 교체 알고리즘에 대한 시각 변화

• 페이지 교체 알고리즘은
  1960~1970년대의 다중프로그래밍 초기 시대에 뜨거운 주제였음

• RAM 용량이 커지며,
  전역 교체 방법은 희생 프레임을 찾는 데에 시간 소모가 너무 많아 비현실적

• 메모리 활용보다 CPU 캐시 활용이 더 중요해짐

• 참조의 지역성 약화

이러한 이유로 인해 페이지 교체 알고리즘에 대한 중요도가 과거보다 떨어짐

6.4 페이지 교체 알고리즘 종류

• 최적 교체 (Optimal Page Replacement, OPT)
• FIFO (First in First out)
• LRU (Least Recently Used)
• Clock

페이지들의 참조 순서: 0 1 2 0 3 0 1 2 0 3 0 2 1 0
희생 페이지는 지역 교체

6.5 최적 교체 알고리즘(OPT)

알고리즘 개요

• 가까운 미래에 사용될 가능성이 가장 낮은 페이지를 희생 페이지로 선택
  가장 먼 미래에 사용될 페이지를 선택

구현

• 최적 교체는 페이지 폴트 횟수가 가장 적은 최고의 이상적인 방법이지만
  미래의 페이지 액세스에 대해 알지 못하므로 구현 불가능
  다른 알고리즘을 평가하는 기준으로
  최적 교체의 성능에 가까울수록 좋은 알고리즘이 됨

6.6 FIFO(First In First Out) 알고리즘

알고리즘 개요

• 메모리 프레임에 적재된 페이지들 중
  가장 오래된 페이지를 희생 페이지로 선택
  오래 전에 적재된 페이지들은
  작업 집합에서 벗어나 참조 가능성이 낮을 것이라는 판단

구현

• 각 페이지마다 적재된 시간 정보를 저장
  페이지를 교체할 때마다 페이지들의 적재 시간을 검색하는 것은 부담이 큼

• 따라서 프레임들을 페이지가 적재된 순서로 큐를 만들고,
  새 페이지가 적재될 때 해당 프레임을 큐 끝으로 이동

• 개념이 단순하고 구현이 쉽지만,
  작업 집합을 고려하지 않아 성능이 낮음

• Belady anomaly
  FIFO 알고리즘의 경우 더 많은 메모리 프레임을 할당할수록,
  페이지 폴트가 더 많이 발생하는 현상

6.7 LRU(Least Recently Used) 알고리즘

알고리즘 개요

프레임에 적재된 페이지들 중 가장 오래전에 참조된 페이지를 희생 페이지로 선택

구현

타임스탬프 이용

• 모든 프레임에 참조 시간을 기록할 수 있는 비트들을 추가
• CPU가 페이지를 참조할 때마다 프레임에 현재 시간을 기록
• 페이지 교체 요청 시 참조된 시간이 가장 오래된 것을 희생 페이지로 선택
• 시간 기록 및 참조 시간 검사에 많은 오버헤드

하드웨어 이용, 참조 비트 사용

• 페이지 테이블 항목에 1개의 참조 비트(reference bit)와
  참조 비트에 값을 기록하는 하드웨어 추가

• CPU 주소가 발생할 때 마다 하드웨어를 이용하여 참조 비트를 1로 세팅

• 페이지 교체 요청 발생 시, 참조 비트가 0인 페이지 중 하나를 선택

• 하드웨어를 이용함으로써, 참조 비트를 1로 바꾸는 지연 시간은 없지만,
  참조 비트가 0인 페이지 검색, 참조 비트를 주기적으로 0으로 초기화하는 데 많은 시간이 걸림

LRU 알고리즘의 장단점

• 구현의 복잡도가 높음
• 하드웨어에 대한 지원과 커널 코드의 주기적이 실행이 필요함

6.8 Clock 알고리즘

• LRU + FIFO
• LRU 근사 알고리즘(LRU approximation)
• FIFO 근사 알고리즘
• 2차 기회 알고리즘(second chance algorithm)

구성

• 메모리 프레임 당 1비트의 참조 비트를 사용

• 프레임들을 원형 큐로 만들어 관리

• CPU가 페이지를 참조할 때마다 특별한 하드웨어를 이용하여
  해당 페이지가 담긴 프레임의 참조 비트를 1로 수정

• 포인터(pointer, frame pointer)
  희생 페이지를 결정하기 위해 검색을 시작하는 원형 큐의 프레임 위치

알고리즘

• 원형 큐를 돌며 현재 포인터에서 참조 비트가 0인 프레임을 만날 때 까지
  참조 비트가 1이면 0으로 바꾸면서 시계 방향으로 이동
  참조 비트가 0인 프레임을 발견하지 못했다면,
  시작 페이지가 희생 페이지가 됨

• 희생 페이지를 찾는 과정에서 참조 비트를 0으로 초기화하기 때문에
  LRU에서 커널이 주기적으로 바꾸던 과정을 제거