가상 메모리

• 메모리 크기보다 더 큰 기억공간이 필요한 프로세스를 실행할 수 있게 하는 방법
• 해당 프로세스의 특정구간만 메모리에 담아서 당장 필요한 부분부터 처리한다.
• 프로세스에 의해 참조되는 가상주소를 메모리에서 사용하는 실주소와 분리하여 구분함
• 메모리에 실제로 적재될 때는 가상주소를 실주소로 매핑되어 사용함

선요약

• 페이지 교체기법은 메모리가 완전히 사용되고 있을 때 새로이 적재되어야 할 페이지를 위하여 어느 페이지가 교체되어야 하는지에 관계된다.
• 페이지 교체기법으로는 FIFO, LRU, LFU, NUR, 2차 기회, 클럭, 워킹세트, PFF 등이 있다.
• 최적의 페이지 교체기법은 앞으로 가장 오랫동안 사용되지 않을 페이지를 선택하는 방법이다.
• 프로세스는 기억장치 내의 정보를 균일하게 액세스하는 것이 아니라, 어느 한 순간에는 특정 부분을 집중적으로 참조하는 국부성을 보인다.
• 워킹세트는 어떠한 시점을 기준으로 정해진 크기의 과거 시간 구간 동안 참조된 페이지의 집합이다.
• 워킹세트 알고리즘은 프로그램의 효율적 실행을 위해 워킹세트가 메모리 내에 유지되도록 한다.
• PFF 알고리즘의 기본 아이디어는 페이지 부재 비율이 높으면 페이지 프레임을 더 배정하고, 낮으면 회수하는 것이다.

사상

프로세스 실행을 위해 가상주소를 실주소로 변환(매핑)하는 것

• 동적 주소 변환(DAT): 프로세스가 실행되는 동안 사상
• 인위적 연속성이 보장됨

인위적 연속성이란?

가상주소 공간에서는 연속이지만 실주소 공간에서는 연속일 필요가 없음

블록 단위 주소 변환

• 블록 단위로 분류하여 각 블록이 메모리의 어디에 위치하는지를 관리
• 블록이 작아지면 사상정보 커짐
• 블록이 커지면 블록 전송시간도 증가 및 적재할 프로세스 수 감소

블록 구성 방식에 따른 분류

• 페이징 기법: 블록의 크기가 동일한 페이지로 구성
• 세그먼테이션 기법: 블록의 크기가 서로 다른 세그먼트로 구성

페이징 기법

• 가상 메모리를 고정된 크기의 블록인 페이지 단위로 나누어 관리함

용어

• 페이지: 가상 메모리의 블록
• 페이지 프레임: 실제 메모리의 블록

페이지와 페이지 프레임의 블록의 크기는 동일하다.

페이징 기법의 특징

• 논리적 의미와 무관하게 동일 크기의 페이지로 가상 메모리를 나눔
• 프로세스 사이의 메모리 보호는 페이지 단위로 이루어짐
• 페이지 덕분에 외부 단편화는 발생하지 않으나, 페이지 크기보다 적재되는 메모리가 작을 경우 내부 단편화가 발생할 수 있음

페이지 사상표

가상주소를 실주소로 동적 변환하기 위해 필요함.
가상 주소의 페이지 번호에 대한 실주소의 페이지 프레임 번호를 저장함.
페이지 존재 비트, 보조기억장치 주소, 페이지 프레임 번호로 이루어져 있음.

페이지 번호	페이지 존재 비트	보조기억장치	페이지 프레임 번호
3	1	s	5
...	...	...	...

• 직접 사상 : 페이지 사상표를 직접 이용하는 방법
• 연관 사상 : 연관기억장치에 저장한 연관 사상표를 이용하는 방법.

용어

• 페이지 존재 비트: 1일 경우 메모리상에 적재되어 있는 상태. 0이면 적재가 안된 상태
• 연관기억장치: 저장된 값으로 데이터를 엑세스하는 고속 메모리 장치
• 연관 사상표: 가장 최근에 참조된 페이지들만 보관, 나머지는 페이지 사상표에 보관

연관 사상표

페이지 번호	페이지 프레임 번호
3	5
...	...

세그먼테이션 기법

• 세그먼트: 가상 메모리를 논리적 의미에 맞는 다양한 크기의 세그먼트 단위로 나누어 관리함

세그먼트 사상표

• 세그먼트 시작주소 : 메모리에서의 시작 위치
• 세그먼트 길이 : 오버플로우 확인용

세그먼트 번호	보조기억장치 주소	세그먼트 길이	세그먼트 시작주소
...	...	...	...
1	s	1500	1200
...	...	...	...

페이징, 세그먼테이션 혼용기법

• 세그먼테이션의 논리적 장점 + 페이징 기법의 메모리 관리 장점
• 가상 메모리를 세그먼트 단위로, 각 세그먼트를 다시 페이지 단위로 분할 (세그먼트 하나당 페이지 사상표 하나!)
• 메모리는 페이지 프레임으로 분할
• 가상주소는 v = (s, p, d) (s=세그먼트번호, p=페이지번호, d=페이지 내 변위)

동적 주소 변환 방법

1. 세그먼트 사상표의 시작주소에 가상주소의 세그먼트번호(s)를 더함
2. 위에서 구한 b+s의 위치에 들어있는 페이지 사상표의 시작위치를 가져옴
3. 페이지 사상표 시작위치 + 가상주소의 페이지번호(p)를 해서 페이지 사상표에 들어있는 페이지 프레임 번호를 가져옴
4. 해당 페이지 프레임에서 가상주소의 페이지 내 변위(d)를 조합하여 실주소를 찾을 수 있게 됨

메모리 호출기법

페이지를 어느 시점에 적재할 것인가를 결정

요구 페이지 호출기법

한 프로세스의 페이지 요구가 있을 때 요구된 페이지를 메모리로 이동시킴.
즉, 명령어나 데이터가 실제로 참조될 때(필요할 때) 해당 페이지를 메모리에 적재시킴.

• 옮길 페이지를 결정하는데 오버헤드를 최소화
• 페이지가 요구될 때 옮겨지기 때문에 메모리로 옮겨진 페이지는 모두 프로세스에 의해 무조건 참조된 것들임
• 프로세스 시작 시점에는 프로세스 진행에 따라 연속적으로 페이지 부재 발생 (성능 저하)

예상 페이지 호출기법

현재 요구되지는 않지만 곧 사용될 것으로 예상되는 페이지를 미리 메모리로 이동시킴.
실제 필요한 시점이 되었을 때 프로세스 실행이 단절되지 않음.

• 예상이 잘못된 경우 메모리 공간을 낭비하게 됨
• 프로세스 시작 시점에 적용하면 성능이 개선됨

페이지 교체기법

모든 페이지 프레임이 사용되고 있을 때 새로 적재되어야 할 페이지를 위하여 어느 페이지를 교체할 것인가를 결정하는 기법

• 교체 대상 선택 -> 보조기억장치에 보관 -> 새로운 페이지를 적재

최적화의 원칙

• 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체 대상으로 선택함
• 이론적으로는 최적이나 미래를 예측할 수 없어 실현 불가능
• 대체로 좋은 결론을 내리면서 시간 및 공간의 오버헤드가 적은 방법을 기본 정책으로 사용함

교체 제외 페이지

페이징을 위한 슈퍼바이저 코드 영억, 보조기억장치 드라이버 영역, 입출력장치를 위한 데이터 버퍼 영역 등

FIFO (First-in First-Out) 페이지 교체기법

메모리 내에 가장 먼저 들어온 페이지부터 교체하는 기법 (FIFO 큐 이용)

단점

• 반복적으로 계속 사용되는 페이지가 오래전에 적제되었다는 이유로 교체될 수도 있음
• Belady의 이상현산 발생
  • 프로세스에 더 많은 수의 페이지 프레임을 할당할 경우 오히려 페이지 부재가 더 많이 발생할 수 있는 현상

LRU (Least Recently Used) 페이지 교체기법

가장 오랫동안 사용되지 않은 페이지를 교체함

• 구현: 참조시간 또는 리스트 이용
• 페이지가 참조될 때마다 그때의 시간을 기록함
• 페이지가 참조되면 리스트의 선두로 옮김
• 페이지를 교체해야 한다면 리스트의 끝에 있는 페이지를 교체

장점

• Belady의 이상현상 발생하지 않음
• 많은 경우 최적화 원칙에 근사한 선택을 함
• 국부성(locality)에 기반함 (= 어느 한순간에 특정 부분을 집중적으로 참조함)
  (국부성 = 지역성)

단점

• 경험적 판단이 맞지 않는 상황도 존재함
• 막대한 오버헤드 발생

국부성(=지역성)

• 시간 국부성(=시간 지역성): 현재 참조된 기억장소는 가까운 미래에도 계속 참조될 가능성이 높음
• 공간 국부성(=공간 지역성): 하나의 기억장소가 참조되면 근처의 기억장소가 계속 참조될 가능성이 높음

LFU (Least Frequently Used) 페이지 교체기법

참조된 횟수가 가장 적은 페이지를 교체함

• 구현: 참조횟수 이용

단점

• 가장 최근에 메모리로 옮겨진 페이지가 교체될 가능성이 높음
• 초기에 매우 많이 사용된 후 더 이상 사용되지 않는 페이지는 교체가능성이 낮음
• 막대한 오버헤드

NUR (Not Used Recently) 페이지 교체기법

• 참조 여부와 수정 여부에 따른 우선순위에 따라 적합한 페이지를 교체
• 구현: 페이지마다 참조 비트 r과 수정 비트 m 이용

방법

• 페이지를 프레임에 적재: r=0, m=0
• 페이지를 참조: r=1
• 페이지를 수정: m=1
• 교체 우선 순위
  1. r=0, m=0
  2. r=0, m=1
  3. r=1, m=0
  4. r=1, m=1

특징

• 적은 오버헤드로 적절한 성능을 낼 수 있음
• LRU와 유사하면서도 실제로 자주 쓰임
• 동일 그룹 내에서의 선택은 무작위
• 모든 참조 비트 r을 주기적으로 0으로 변경

2차 기회 (second chance) 페이지 교체기법

FIFO 페이지 교체기법과 참조 여부에 따른 우선순위를 고려하여 적합한 페이지를 교체

• 구현: FIFO 큐와 참조비트 이용

참조비트

• 페이지 프레임에 적재: 참조 비트는 0
• 페이지 참조: 참조 비트는 1

교체 대상 선택 방법

1. 큐의 선두를 꺼내 참조 비트 조사
2. 참조 비트가 0이면 교체 대상으로 선택
3. 참조 비트가 1이면 0으로 바꿔 큐의 뒤에 넣음

클럭 (clock) 페이지 교체기법

• 2차 기회 페이지 교체를 원형 큐를 이용하여 구현한 것
• 교체가 필요한 경우 큐에서의 삭제 및 삽입 대신 포인터 이동으로 간단히 구현

프로세스별 페이지 집합 관리

• 프로세스별 페이지 집합: 프로세스마다 페이지 프레임에 적재된 페이지들의 집합
• 프로세스별 페이지 집합의 크기가 적은 경우
  • 메모리에 적재할 수 있는 프로세스의 수 많아짐 -> 시스템 처리량 증대
  • 각 프로세스별 페이지 부재 많아짐 -> 성능 저하
• 페이지 집합 관리 알고리즘
  • 워킹세트 알고리즘
  • PFF 알고리즘

워킹세트 알고리즘

• 하나의 프로세스가 자주 참조하는 페이지의 집합
• 워킹세트 W(t,w): 시간 t-w로부터 시간 t까지의 프로세스 시간 간격동안 참조된 페이지의 집합
• 데닝(Denning)이 제안함
• 페이지 부재 비율을 감소시킬 수 있는 방법임
• 원칙: 실행 중인 프로그램의 워킹세트를 메모리에 유지함(국부성)
• 프로세스가 실행됨에 따라 워킹세트의 크기는 변함
• 워킹세트가 메모리에 유지되지 못하는 경우 쓰레싱이 유발될 수 있음

용어

• 프로세스 시간: 해당 프로세스가 CPU를 점유하고 있는 시간
• t: 현재 시간
• w: 과거 시간
• W: 워킹세트 윈도 크기 (W = t - w)
• 쓰레싱(thrashing): 페이지 부재가 비정상적으로 많이 발생하여 페이지 교체에 많은 시간을 사용하여 시스템 처리량이 급감하는 현상

단점

• 과거를 통해 미래를 예측하는 것이 매번 정확할수는 없음
• 워킹세트를 정확히 알아내고 이를 계속적으로 업데이트하는 것이 현실적으로 어려움
• 워킹세트 윈도의 크기 w의 최적 값을 알기 어려우며 이 역시 변화할 수 있음

PFF (Page Fault Frequency) 알고리즘

• 프로세스의 상주 페이지 세트를 변경하며 관리
• 페이지 부재가 발생할 때 빈도를 계산하여 상한과 하한을 벗어나는 경우에만 변경
• 페이지 부재 빈도: 두 페이지 부재가 일어난 사이의 시간의 역수
• 운영체제는 프레임의 여분 상황에 따라 새로운 프로세스 추가 및 중지 결정

상주 페이지 세트

프로세스가 페이지 부재 떄문에 멈추게 되는 빈도에 기초한 페이지 세트