가상 메모리

가상 메모리

• 메모리 크기보다 더 큰 기억공간이 필요한 프로세스도 실행할 수 있게 하는 방법
• 실행 중인 프로세스에 의해 참조되는 주소를 메모리에서 사용하는 주소와 분리
• 현재 필요한 일부만 메모리에 적재한다.
• 가상주소 : 실행 프로세스가 참조하는 주소
• 실주소 : 실제 메모리에서 사용하는 주소

사상(mapping)

• 프로세스 실행을 위해 가상주소를 실주소로 변환하는 과정
• 동적 주소변환(DAT) : 프로세스가 실행되는 동안 가상주소를 실주소로 바꾸는 절차
• 가상주소 공간에서 연속적인 주소가 실주소 공간에서도 연속적일 필요는 없음

블록 단위 주소변환

주소변환

• 주소변환 사상표 : 동적 주소변환을 위한 정보를 가진 표
• 바이트(byte)나 워드(word) 단위로 주소변환을 하면 사상표의 메모리 공간이 커지므로 블록 단위로 주소변환을 하는 블록 사상 시스템을 이용한다.

블록 사상 시스템

• 가상 메모리의 각 블록이 메모리의 어디에 위치하는지 관리
• 블록 사상 시스템의 주소는 블록과 그 블록의 시작점으로부터의 변위로 구성된다.
• 가상주소 v = (b,d), b:블록 번호, d:블록의 시작점으로부터의 변위
• 블록의 크기가 크면 사상표의 크기는 감소하지만, 블록 전송시간이 증가하고 적재할 수 있는 프로세스 수가 감소한다.
• 블록의 크기가 작으면 블록 전송시간이 감소하고 적재할 수 있는 프로세스 수가 증가하지만, 사상표의 크기가 증가한다.

블록 구성 방식

• 페이징 기법 : 가상 메모리를 고정된 크기의 블록(페이지) 단위로 나눈다.
• 세그먼테이션 기법 : 가상 메모리를 다양한 크기의 블록(세그먼트) 단위로 나눈다.

페이징 기법

• 가상 메모리를 논리적 의미와 무관한 동일 크기의 페이지로 나누어 관리하는 기법
• 고정된 크기로 나누므로 외부 단편화는 발생하지 않지만, 내부 단편화는 발생할 수 있다.
• 페이지 사상표에 페이지 존재 비트, 보조기억장치 주소, 페이지 프레임 번호를 저장한다.
• 페이지 사상표를 직접 사용하는 직접사상 방법과 연관사상표를 이용하는 연관사상 방법이 있으며, 일반적으로는 직접사상과 연관사상을 같이 사용하는 연관/직접 사상을 이용한다.

직접사상에 의한 동적 주소변환

• 가상주소 v=(3,8) 이라면, 페이지 번호가 3이므로 페이지 사상표에서 3에 대한 위치를 찾는다.
• 페이지 존재 비트를 확인하니 현재 메모리에 적재되어 있으므로, 페이지 프레임 번호 5로 메모리의 페이지 프레임을 찾는다.
• 메모리의 페이지 프레임에서 가상주소에 있는 변위 8byte만큼 더한 곳이 바로 실주소가 된다.
• 페이지 프레임의 크기가 M이라면 실주소는 5M+8이며, M=1024byte 이면 5128이다.

연관사상에 의한 동적 주소변환

• 페이지 변환 정보를 고속 메모리 장치인 연관 메모리에 저장한 연관사상표를 이용하는 방법이다.
• 페이지 프레임의 크기가 M이라면 마찬가지로 실주소는 5M+8이다.

연관/직접 사상에 의한 동적 주소변환

• 연관사상표에는 가장 최근에 참조한 페이지만 보관하고 나머지는 사상표에 수록한다.
• 먼저 연관사상표에서 페이지를 찾고, 없으면 사상표에서 시작주소 b와 페이지 번호를 더해서 찾는다.
• 실주소를 찾으면 페이지 번호와 페이지 프레임 번호를 연관사상표에 포함시킨다.

세그먼테이션 기법

• 가상 메모리를 논리적 의미에 부합하는 다양한 크기의 세그먼트로 나누어 관리하는 기법
• 세그먼트 사상표에 세그먼트 존재 비트, 보조기억장치 주소, 세그먼트 길이, 세그먼트 번호에 대한 실주소에서의 시작 위치를 저장한다. 세그먼트 길이는 세그먼트 오버플로를 확인할 때 사용된다.

동적 주소변환

• 가상주소 v=(3,8) 이라면, 세그먼트 번호가 3이므로 페이지 세그먼트 사상표에서 3에 대한 위치를 찾는다.
• 세그먼트 존재 비트를 확인하니 현재 메모리에 적재되어 있고, 세그먼트 크기가 1500으로 변위 8보다 크므로 문제가 없다.
• 메모리에서의 시작 주소 1200에 변위 8을 더한 1208이 바로 실주소가 된다.

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

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

연관/직접 사상에 의한 동적 주소변환

• 먼저 연관사상표에서 세그먼트 번호와 페이지 번호로 페이지를 찾는다. 발견되면 해당 페이지 프레임 번호와 변위로 실주소를 찾는다.
• 연관사상표에서 발견하지 못하면 세그먼트 사상표에서 세그먼트 사상표 시작주소와 세그먼트 번호를 더해서 세그먼트를 찾는다. 여기에 페이지 사상표의 시작주소가 포함되어 있다.
• 페이지 사상표에서 페이지 사상표의 시작주소와 페이지 번호를 더해서 페이지를 찾는다. 여기에 메모리의 페이지 프레임 번호가 포함되어 있다.
• 페이지 프레임 번호와 변위로 실주소를 찾으면 세그먼트 번호와 페이지 번호와 페이지 프레임 번호를 연관사상표에 포함시킨다.

페이지 교체 알고리즘

FIFO (First-In First-Out)

• 큐 자료구조 사용
• 메모리 내에 가장 오래 있었던 페이지를 선택하여 교체
• 단점
  • 가장 많이 쓰이는 페이지를 교체시킬 수도 있음
  • Belady의 이상 현상
    • 프로세스에 더 많은 수의 페이지 프레임을 할당하면 오히려 페이지 부재가 더 많이 발생할 수 있는 현상

LRU (Least Recently Used)

• 메모리 내에서 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체
• 국부성(locality) 휴리스틱에 기반
• 장점
  • Belady의 이상 현상이 발생하지 않음
  • 많은 경우 최적화 원칙에 근사한 선택 가능
• 단점
  • 국부성이 맞지 않는 상황도 존재
  • 막대한 오버헤드

LFU (Least Frequently Used)

• 메모리 내에서 참조된 횟수가 가장 적은 페이지를 선택하여 교체
• 단점
  • 가장 최근에 메모리로 옮겨진 페이지가 교체될 가능성이 높음
  • 초기에 매우 많이 사용되고 더 이상 사용되지 않는 페이지는 교체 가능성이 낮음
  • 막대한 오버헤드

2차 기회 페이지 교체

• 참조 비트가 0이면서 메모리 내에 가장 오래 있었던 페이지를 선택하여 교체
• FIFO 큐와 참조 비트를 이용하여 구현
• 각 페이지가 메모리에 적재될 때는 참조 비트 값이 0이다.
• 적재된 상태에서 추가로 참조되면 참조 비트 값을 1로 바꾼다.
• 교체할 페이지를 선택할 때는 큐 순서대로 조사하여 참조 비트가 0인 페이지가 나오면 선택하여 교체한다. 페이지의 참조 비트가 1이면 0으로 바꿔 큐의 뒤에 추가한다.

변형된 원형 큐를 이용한 구현 (클럭 페이지 교체 알고리즘)

• 포인터는 마지막에 추가된 페이지의 다음 위치를 가리킴
• 빈 페이지 프레임이 있는 경우 포인터는 빈칸을 가리킴
• 페이지 프레임이 꽉 찬 경우 포인터는 큐의 선두(12시 방향)를 가리킴