[운영체제 OS] Virtual Memory

1. 가상메모리의 특성 및 개념

1.1 특성

• 논리 주소와 물리 주소의 분리: 프로세스는 논리 주소(logical address)를 참조하며, 실행 시점에 물리 주소(physical address)로 동적 변환된다.
• 비연속적 할당: 주소 공간이 블록(페이지/세그먼트)으로 분할되어 주기억장치의 인접하지 않은 위치에 배치될 수 있다.
• 부분 적재(Partial Loading): 프로세스의 일부 블록만 적재해도 실행 가능하다.
  • 적재집합(Resident Set): 현재 주기억장치에 적재된 블록들의 집합이다.
  • 메모리 접근 오류(Memory Access Fault): 적재되지 않은 블록 참조 시 발생하며, 이를 '페이지 폴트'라고 한다.

1.2 가상메모리와 물리메모리

• 가상메모리: 디스크의 방대한 공간을 활용한 프로세스 관점의 전체 주소 공간이다.
• 물리메모리: CPU가 실제로 참조하는 하드웨어 주기억장치이다.

 

2. 가상 메모리 시스템 구조 및 주소 지정

2.1 페이징(Paging) 기반 구조

• 페이지(Page): 보조기억장치(디스크)에 있는 고정된 크기의 블록이다.
• 프레임(Frame): 주기억장치에 있는 페이지와 동일한 크기의 블록이다.
• 페이지 테이블: 논리 주소(페이지)와 물리 주소(프레임) 간의 매핑 정보를 관리한다.

프로그램 실행 및 적재

• 프로그램이 수행되기 위해서는, 해당 프로그램을 구성하는 페이지들 중 일부 혹은 전부가 주기억장치에 적재되어 있어야 한다.
• 디스크의 가상 주소 공간에서는 연속적이던 페이지들이, 주기억장치의 프레임에는 비연속적으로 나뉘어 적재될 수 있다.
• 운영체제는 페이지 테이블을 사용하여 이처럼 분산된 페이지와 프레임 간의 매핑을 관리한다.

2.2 주소 변환 과정 (MMU)

• CPU: 논리적인 가상 주소를 생성한다.
• MMU(Memory Management Unit): 하드웨어 장치로, 가상주소를 실주소로 변환한다.
• Case 1 (페이지 히트): 성공적으로 변환하여 메모리에 접근한다.
• Case 2 (페이지 폴트): 데이터가 메모리에 없으면 OS가 디스크에서 해당 데이터를 가져온다.

 

3. 가상 메모리 관련 용어

 

4. 지역성의 원리 (Principle of Locality)

가상메모리가 효율적으로 작동하는 근본적인 이유이다.

• 시간 지역성(Temporal Locality): 최근 참조된 위치가 가까운 미래에 다시 참조될 가능성이 높다 (예: 반복문, 스택).
• 공간 지역성(Spatial Locality): 참조된 위치 근처의 주소들이 참조될 가능성이 높다.

 

5. 페이지테이블 항목 구성 및 주소 변환

5.1 페이지테이블 항목 구성

가상 주소의 구조

• 가상 주소는 페이지 번호와, 해당 페이지 내에서의 위치를 나타내는 오프셋으로 구성된다.

페이지테이블 항목(PTE)의 구성

• P (존재 비트 - Present bit): 해당 페이지가 현재 주기억장치에 적재되어 있는지 여부를 나타낸다. (적재 시 1, 미적재 시 0)
• M (변경 비트 - Modify bit): 페이지가 주기억장치에 적재된 이후, 그 내용이 변경되었는지 여부를 나타낸다.

5.2 주소 변환

1. 가상주소 생성
   • 프로그램은 논리적인 가상주소를 생성한다.
   • 페이지 번호와 해당 페이지 내의 상대적 위치인 오프셋으로 구성된다.
2. 페이지테이블 조회
   • 가상주소에서 페이지 번호 부분이 추출된다.
   • 이 페이지 번호는 페이지테이블을 조회하기 위한 인덱스로 사용된다.
   • 페이지테이블의 해당 항목에는 프레임 번호가 저장되어 있다.
3. 물리주소 생성
   • 페이지테이블에서 조회한 프레임 번호와 오프셋을 결합하여 물리주소를 생성한다.
4. 주기억장치 접근
   • 생성된 물리주소를 사용하여 주기억장치에 접근한다.
   • 물리주소의 프레임 번호 부분은 특정 페이지 프레임을 선택하고, 오프셋 부분은 그 프레임 내의 데이터 위치를 지정한다.

 

6. 페이지테이블 크기 문제 해결 방법

6.1 계층적 페이지 테이블 (Multi-level Page Table)

가상 주소 공간이 커짐에 따라 페이지 테이블 크기도 비대해지는 문제를 해결한다.

• 구조: 1단계(루트) 테이블과 2단계(사용자) 테이블로 나뉜다.
• 장점: 실제 사용 중인 영역에 대해서만 하위 테이블을 생성하여 메모리 공간을 절약한다.

2-단계 계층적 페이지테이블

1. 1단계 (루트 페이지 테이블):
   • 최상위에 '루트 페이지 테이블'이 존재한다.
   • 가상주소의 첫 번째 부분이 이 테이블의 인덱스로 사용된다.
   • 여기서 선택된 항목은 2단계 페이지테이블 중 하나의 시작 주소를 가리킨다.
2. 2단계 (사용자 페이지 테이블):
   • 가상주소의 두 번째 부분이 1단계에서 지정된 2단계 테이블의 인덱스로 사용된다.
   • 여기서 선택된 항목이 비로소 실제 데이터가 저장된 물리 메모리의 프레임 번호를 가리킨다.
3. 사용자 주소 공간:
   • 최종적으로 변환된 프레임 번호와 가상주소의 오프셋이 결합되어 4GB 사용자 주소 공간 내의 특정 물리 주소에 접근한다.

2-단계 페이징 시스템에서의 주소변환

1. 가상 주소의 구조 (32비트)

• 상위 10비트: '루트 페이지 테이블'(1단계)의 인덱스로 사용
• 중간 10비트: '4KB 페이지 테이블'(2단계)의 인덱스로 사용
• 하위 12비트: 페이지(프레임) 내의 오프셋(Offset)으로 사용

2. 주소 변환 과정

1. 1단계 조회 (루트 페이지 테이블):
   • '루트 페이지 테이블 포인터' 레지스터가 1단계 테이블의 시작 주소를 가리킨다.
   • 이 시작 주소에 가상주소의 상위 10비트 인덱스를 더하여, 1단계 테이블 내의 해당 항목을 찾는다.
   • 이 1단계 항목에는 사용할 2단계 페이지 테이블의 시작 주소가 저장되어 있다.
2. 2단계 조회 (페이지 테이블):
   • 1단계에서 찾은 2단계 테이블의 시작 주소에 가상주소의 중간 10비트 인덱스를 더한다.
   • 이를 통해 2단계 '4KB 페이지 테이블' 내의 해당 항목을 찾는다.
   • 이 2단계 항목에는 데이터가 실제 적재된 프레임 번호가 저장되어 있다.
3. 물리 주소 생성:
   • 2단계 조회에서 최종적으로 얻은 프레임 번호와, 가상주소의 원본 하위 12비트를 결합하여 물리 주소를 완성한다.
4. 주기억장치 접근:
   • 완성된 물리 주소를 사용하여 주기억장치의 해당 '페이지 프레임'에 접근하여 데이터를 읽거나 쓴다.

6.2 역페이지 테이블 (Inverted Page Table)

• 프로세스마다 테이블을 만드는 대신, 실제 물리 프레임당 하나의 항목만 가진다.
• 해싱(Hashing)을 사용하여 페이지 번호를 프레임 번호로 변환하며, 시스템 전체에 단 하나만 존재한다.

1. 페이지 번호 + 프로세스 ID n비트를 해시 함수를 돌려 인덱스 i를 찾아낸다. 해당 i는 해시값 즉 프레임 번호이다.

2. 이때 서로 다른 페이지 번호가 동일한 해시값으로 사상될 수 있는 충돌문제를 해결해야 한다. 이를 위해 체인 기법을 사용한다.

3. 동일한 해시값을 갖는 페이지들을 연결리스트 형태로 관리한다.

4. i번째 하옥에 접근해서 페이지 번호와 프로세스 ID를 가장주소의 원본값과 비교한다.

5. 일치하면 i가 프레임 번호이고 불일치하면 체인 필드가 가리키는 j로 이동하여 일치하는 항목을 찾을 때까지 계속 비교 반복한다. 6. 찾아낸 최종 인덱스와 오프셋을 결합하여 실주소를 생성한다.

 

6.3 TLB (Translation Lookaside Buffer)

• 주소 변환 속도를 높이기 위한 고속 하드웨어 캐시이다.
• 최근에 사용된 페이지 테이블 항목을 저장하여, 메모리에 있는 페이지 테이블에 접근하는 시간을 단축한다.

1. 가상주소 생성
   • CPU가 가상주소(페이지 번호 + 오프셋)를 생성한다.
2. TLB 조회:
   • MMU는 먼저 가상주소의 페이지 번호를 이용해 TLB를 검색한다.
3. TLB 적중 (Hit):
   • 만약 페이지 번호가 TLB에 존재할 경우 TLB로부터 즉시 대응되는 프레임 번호를 얻는다.
   • 이 프레임 번호와 가상주소의 원본 오프셋을 결합하여 실주소를 생성한다.
   • 생성된 실주소를 이용해 주기억장치에 바로 접근한다.
4. TLB 부재 (Miss):
   • 만약 페이지 번호가 TLB에 존재하지 않을 경우 시스템은 주기억장치에 있는 페이지 테이블에 접근하여 해당 페이지 번호에 대한 항목을 찾는다.
5. 페이지 폴트 처리:
   • 페이지 테이블 항목이 해당 페이지가 주기억장치에 없다고 표시하면 페이지 폴트가 발생한다.
     • 운영체제가 개입하여 보조기억장치에서 해당 페이지를 찾아 주기억장치로 적재한다.
     • 페이지 테이블을 갱신하고, TLB에도 새 항목을 적재한다.

 

7. 페이지 교체 알고리즘

메모리가 가득 찼을 때 어떤 페이지를 내보낼지 결정하는 전략이다.

7.1 Optimal

• 앞으로 가장 오랫동안 참조되지 않을페이지를 선택하여 교체하는 방식이다.
• 가장 낮은 페이지 폴트율을 보장한다.
• 구현 불가능: 프로세스가 앞으로 어떤 페이지를 참조할지 미래의 정보를 미리 정확하게 알고 있어야 한다.

7.2 FIFO (First-In First-Out)

• 가장 오래전에 적재된 페이지를 먼저 교체하는 방식이다.
• Belady's Anomaly: FIFO 알고리즘에서 프레임 수(메모리 용량)를 늘려주었는데 오히려 페이지 폴트가 더 많이 발생하는 기현상을 말한다.

 

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 순서로 페이지를 요청한다.

 

프레임이 3개일 때

• 메모리에 페이지를 담을 수 있는 공간(프레임)이 3개인 경우이다.
• 진행 과정:
  • 초기에 1, 2, 3이 순서대로 들어오며 자리를 채운다.
  • 4가 들어올 때 가장 먼저 들어온 1이 교체되어 나간다.
  • 이후 1이 다시 필요할 때 2가 교체되는 식으로, 가장 오래된 페이지가 계속해서 교체된다.
• 결과: 총 9번의 Page Faults가 발생한다.

프레임이 4개일 때

• 메모리 용량을 늘려서 프레임을 4개 할당한 경우이다.
• 진행 과정:
  • 초기에 1, 2, 3, 4까지는 페이지 부재를 일으키며 빈 공간에 들어간다.
  • 이후 1, 2는 이미 메모리에 있으므로 부재 없이 넘어간다.
  • 5가 들어올 때 가장 먼저 들어온 1이 쫓겨난다.
  • 바로 뒤에 1이 다시 필요한데 방금 쫓겨났으므로 또다시 페이지 부재가 발생하며 2를 내보낸다.
• 결과: 총 10번의 Page Faults가 발생한다.

7.3 LRU (Least Recently Used)

• 가장 오랫동안 참조되지 않은 페이지를 찾아서 교체하는 방식이다.

• 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 순서로 페이지를 요청한다.
• 메모리 프레임: 총 4개의 페이지를 담을 수 있는 환경이다.

교체 과정

• 초기 단계 (~1, 2, 3, 4):
  • 처음 1, 2, 3, 4까지는 빈 공간에 순서대로 채워진다.
• 첫 번째 교체 (5번 페이지 요청 시):
  • 메모리에 1, 2, 3, 4가 꽉 차 있고, 5가 들어와야 한다.
  • 바로 직전의 과거 기록을 역추적해본다. 2(방금 사용), 1(그 전), 4(그 전) 순으로 사용되었고, 3이 가장 오랫동안 호출되지 않았다.
  • 따라서 3번 페이지를 내보내고 그 자리에 5를 넣는다.
• 두 번째 교체 (3번 페이지 재요청 시):
  • 현재 메모리는 1, 2, 5, 4이다. 이때 아까 내보냈던 3이 다시 필요해졌다.
  • 과거를 보면 2, 1, 5는 최근에 쓰였지만, 4는 가장 오랫동안 참조되지 않았다.
  • 4번 페이지가 교체 대상이 되어 나가고 3이 들어온다.
• 이후 과정:
  • 동일한 논리로 4번 요청 시에는 가장 오래된 5가 교체되고, 마지막 5번 요청 시에는 가장 오래된 1이 교체되는 패턴이다.

7.4 Clock

• Use Bit (사용 비트): 각 프레임마다 해당 페이지가 최근에 사용되었는지를 표시하는 비트를 하나씩 둔다.
  • 1: 최근에 참조됨 (사용됨).
  • 0: 최근에 참조되지 않음.
• 포인터 (시계 바늘): 교체할 후보를 찾기 위해 프레임을 순차적으로 가리키는 화살표 역할.

작동 원리

• 비트 설정: 페이지가 처음 메모리에 적재되거나, 실행 도중 참조(Read/Write)되면 해당 프레임의 Use Bit를 1로 설정한다
• 교체 대상 탐색: 페이지 부재가 발생하여 새로운 페이지를 넣어야 할 때, 포인터가 가리키는 프레임의 Use Bit를 확인한다.
  1. Use Bit가 0인 경우: 오랫동안 사용되지 않았다고 판단하여 해당 페이지를 교체하고, 그 자리에 새 페이지를 넣는다.
  2. Use Bit가 1인 경우: 최근에 사용된 적이 있는 페이지이므로 당장 쫓아내지 않고 Use Bit를 0으로 변경한 뒤, 포인터를 다음 프레임으로 이동시켜 탐색을 계속한다.

7.5 LFU (Least Frequently Used), MFU (Most Frequently Used)

• LFU: 현재 프레임에 있는 페이지 중 참조 횟수가 가장 적은 페이지를 교체한다.
• MFU: 참조 횟수가 가장 많은 페이지를 교체한다.

 

8. 세그먼테이션 (Segmentation)

프로세스를 고정 크기가 아닌, 논리적 단위(함수, 데이터, 스택 등)인 가변 크기의 세그먼트로 분할하는 기법이다.

8.1 세그먼트 테이블

• 가상 주소는 세그먼트 번호와 해당 세그먼트 내의 상대적 위치인 오프셋으로 구성된다.

주소 변환 과정

• 시스템은 가상주소의 세그먼트 번호를 인덱스로 사용하여, 프로세스의 세그먼트 테이블에 접근한다.
• 해당 세그먼트 테이블 항목을 찾는다.
• 이 항목으로부터 해당 세그먼트가 적재된 물리메모리 블록의 시작 주소를 얻는다.

세그먼트 테이블 항목의 구성

• 세그먼트 시작 주소:
  • 해당 세그먼트가 적재된 물리 메모리의 시작 주소
• 길이:
  • 세그먼트의 경계를 벗어나는 접근을 방지하는 보호 기능을 수행
• 제어 비트:
  • P (존재 비트 - Present bit): 해당 세그먼트가 현재 주기억장치에 적재되어 있는지 여부
  • M (변경 비트 - Modify bit): 세그먼트가 주기억장치에 적재된 이후, 그 내용이 변경되었는지 여부
  • 기타 제어 비트: 접근 권한(읽기/쓰기/실행) 등 추가적인 정보를 포함

8.2 세그먼테이션 주소변환

1. 가상주소 생성
   • 프로그램은 세그먼트 번호와 해당 세그먼트 내의 상대적 위치인 오프셋으로 구성된 가상주소를 생성한다.
2. 세그먼트 테이블 조회
   • 세그먼트 테이블 포인터 레지스터 값과 가상주소의 세그먼트 번호를 더한다.
   • 이 결과값을 인덱스로 사용하여 세그먼트 테이블의 해당 항목에 접근한다.
   • 이 항목으로부터 해당 세그먼트가 적재된 물리 메모리의 시작 주소를 읽어온다.
3. 물리주소 생성
   • 세그먼트 테이블에서 읽어온 시작 주소, 가상주소의 원본 오프셋을 더한다.
4. 주기억장치 접근
   • 이 합산된 값이 최종 물리 주소가 된다.
   • 이 물리 주소를 사용하여 주기억장치에 접근한다. 이 주소는 해당 세그먼트의 시작 위치로부터 오프셋만큼 떨어진 실제 데이터 위치를 가리킨다.

8.3 세그먼테이션/페이징 결합

1. 가상 주소의 구조

• 가상 주소는 세그먼트 번호, 페이지 번호, 오프셋의 세 부분으로 구성

2. 주소 변환 과정

1. 세그먼트 테이블 조회:
   • 가상주소의 세그먼트 번호는 세그먼트 테이블 포인터 레지스터 값과 더해진다.
   • 이 결과값은 해당 프로세스의 세그먼트 테이블 내 특정 항목을 가리키는 인덱스로 사용
2. 페이지 테이블 주소 획득:
   • 1단계에서 찾은 세그먼트 테이블 항목에는, 해당 세그먼트에 대한 페이지 테이블의 시작 주소가 저장되어 있다.
3. 페이지 테이블 조회:
   • 2단계에서 획득한 페이지 테이블 시작 주소와 가상주소의 페이지 번호를 더한다.
   • 이 결과값은 페이지 테이블 내 특정 항목을 가리키는 인덱스로 사용된다.
4. 프레임 번호 획득:
   • 3단계에서 찾은 페이지 테이블 항목에는 데이터가 실제 적재된 물리 메모리의 프레임 번호가 저장되어 있다.
5. 물리 주소(실주소) 생성:
   • 4단계에서 획득한 프레임 번호와, 가상주소의 원본 오프셋을 결합하여 최종 물리 주소를 생성
6. 주기억장치 접근:
   • 생성된 물리 주소를 사용하여 주기억장치의 해당 페이지 프레임에 접근

8.4 세그먼테이션/페이징 결합 테이블 항목

1. 가상 주소의 구조

• 가상 주소는 세그먼트 번호 + 페이지 번호 + 오프셋의 세 부분으로 구성

2. 세그먼트 테이블 항목 (STE)

• '세그먼트 시작 주소' 필드:
  • 해당 세그먼트에 대한 페이지 테이블의 시작 주소
• 길이 필드:
  • 해당 세그먼트의 크기를 나타낸다.
• 제어 비트:
  • 세그먼트 테이블 항목에는 메모리 적재 여부(P 비트)나 변경 여부(M 비트)를 나타내는 비트가 없다.

3. 페이지 테이블 항목 (PTE)

• P (존재 비트) / M (변경 비트):
  • 메모리 적재 및 내용 변경 여부는 페이지 수준에서, 즉 페이지 테이블 항목에서 관리된다.
• 프레임 번호:
  • 해당 페이지가 적재된 물리 메모리의 프레임 번호를 저장한다.

8.5 특징 및 장점

• 보호와 공유: 논리적 단위로 나뉘어 있어 권한 설정(읽기 전용 등)과 공유가 용이하다.
• 외부 단편화: 가변 크기이므로 빈 공간이 조각나는 외부 단편화가 발생할 수 있다.
• 결합 기법: 최근 시스템은 세그먼테이션의 논리적 이점과 페이징의 관리 효율을 합친 세그먼테이션/페이징 결합 기법을 주로 사용한다.

 

출처

• William Stallings, 운영체제 내부구조 및 설계원리