12. 가상기억장치 구현 기법

가상기억장치 구현 기법

보조기억장치의 일부를 주기억장치처럼 사용하여, 용량이 작은 주기억장치를 마치 큰 용량을 가진 것처럼 사용하는 기법

프로그램을 여러 개의 작은 블록 단위로 나누어서 가상 기억장치에 보관해 놓고, 프로그램 실행 시 요구되는 블록만 주기억장치에 불연속적으로 할당하여 처리한다.

사용자에게는 프로세스 전체가 메모리에 로드된 것처럼 보이지만, 실제로는 전체가 로드된 것이 아니며, 가상 메모리라고도 한다.

---

• 가상기억장치 구현 기법
  • 페이징(paging) 기법
  • 세그먼테이션(segmentation) 기법
    • 논리 메모리와 물리 메모리
    • 메모리 관리 장치(MMU, Memory Management Unit)
  • 요구 페이징(demand paging)
  • 스래싱(thrashing)
    • Locality
    • 워킹 셋(Working set)

---

가상 메모리 사용 장점

• 프로그램이 메모리 크기에 대한 제약을 덜 받을 수 있다
• 동시에 많은 프로그램을 실행하므로 CPU 이용률과 처리율을 높일 수 있다.
• 필요한 영역만 메모리에 로드해 스와핑 횟수를 줄여서 프로그램 실행 속도를 높일 수 있다.

페이징(paging) 기법

가상기억장치에 보관되어 있는 프로그램과 주기억장치의 영역을 동일한 크기로 나눈 후 나눠진 프로그램을 동일하게 나눠진 주기억장치의 영역에 적재시켜 실행하는 기법

• 나눠진 물리 메모리 영역은 고정 크기의 프레임(Frame) 이라는 블럭 단위로 분리되며, 논리 메모리 영역(프로세스가 점유하는)은 페이지라 불리는 고정 크기의 블록으로 분리된다.

• 하나의 프로세스가 여러 개의 프레임을 할당받을 수 있다.

• 운영체제는 프로세스의 메모리 접근을 관리하기 위해 프레임을 직접적으로 사용하지 않고 페이지라는 논리적인 블럭을 사용

• 프레임과 페이지의 단위 크기는 같아야 함

• 페이지(Page) : 프로그램을 일정한 크기로 나눈 단위

• 페이지 프레임(Page Frame) : 페이지 크기로 일정하게 나눈 주기억장치의 단위

• 페이지와 프레임에는 각각 번호를 할당해 프로세스의 페이지와 메모리의 프레임을 매핑하고, 매핑 정보는 페이지 맵 테이블에 저장된다.

• 페이지 맵 테이블 : 논리 주소를 물리 주소로 변환하기 위한 페이지의 위치 정보를 저장

  • 프로세스의 페이지의 논리 주소, 그리고 페이지에 매핑된 프레임의 물리 주소 값을 저장
  • 각 프로세스의 PCB에 저장됨
  • 

작동 예시

위 그림과 같이 프로세스 P1은 5개의 페이지로 나눌 수 있다. 이를 메인 메모리의 프레임 5곳에 나눠서 할당하였다. 프로세스를 정상적으로 사용하기 위해 CPU는 논리 주소로 프로그램이 설정한대로 연속적인 주소값으로 명령을 내린다. 이때 각 페이지의 물리 주소가 저장되어 있는 페이지 테이블에서 MMU의 재배치 레지스터를 여러 개 사용해서 위의 그림과 같이 논리 주소가 각 페이지의 실제 물리 주소로 변경된다.

• 장점 :

  • 외부 단편화 해결 : 하나의 프로세스가 사용하는 공간은 여러개의 페이지로 나뉘어서 논리 메모리에서 관리되고 개별 페이지는 순서에 상관없이 물리 메모리에 있는 남는 프레임에 적절히 mapping 되어 저장된다.

• 단점 :

  • 내부 단편화 발생 : 프로세스의 크기가 페이지 수로 나누어 떨어지는 지는 보장하지 않는다. 따라서 프로세스의 마지막 페이지가 페이지 크기보다 작을 수 있다.

    • 예를 들어 페이지 크기가 1,024B 이고 프로세스 A 가 3,172B 의 메모리를 요구한다면 3 개의 페이지 프레임(1,024 * 3 = 3,072) 하고도 100B 가 남기때문에 총 4 개의 페이지 프레임이 필요한 것이다. 결론적으로 4 번째 페이지 프레임에는 924B(1,024 - 100)의 여유 공간이 남게 되는 내부 단편화 문제가 발생하는 것이다.

  • 페이지 맵 테이블 사용 -> 추가적인 메모리 공간 필요

종류

• 계층적 페이징(hierarchical paging) : 페이지 테이블을 다시 페이지로 나눠 페이지 테이블 자체를 페이징하는 방식으로, 멀티 레벨 페이징(multi-level paging)이라고도 한다.
• 해시 페이지 테이블(hashed page table) : 해시 테이블의 각 항목에 저장된 연결 리스트에 페이지 번호를 해싱한 뒤에 첫 번째 요소와 가상 페이지 번호를 비교하는 방식
• 역 페이지 테이블(inverted page table) : 프레임을 이용해 페이지를 찾는 방식. 페이지로 프레임을 찾는 기존 방식과 반대다.

세그먼테이션(segmentation) 기법

가상기억장치에 보관되어 있는 프로그램을 다양한 크기의 논리적 단위로 나눈 후 주기억장치에 적재시켜 실행하는 방법

• 세그먼트 : 프로그램을 배열이나 함수 등 논리적인 크기로 나눈 단위
• 각 세그먼트는 고유한 이름과 크기를 갖는다.
• 사용 목적 : 기억공간 절약
• 세그먼트 맵 테이블 : 논리 주소를 물리 주소로 변환하기 위해 세그먼트 위치 정보를 저장
  • 세그먼트 번호를 인덱스로 사용, 세그먼트별 시작 주소(base)와 세그먼트 길이(limit) 저장

작동 예시

세그먼트 테이블에는 각 세그먼트 번호와, 세그먼트의 기준(세그먼트의 시작 물리 주소 : base)과 한계(세그먼트의 길이 : limit)를 저장하여 엔트리로 갖는다.

• 장점
  • 데이터 보호 : 프로세스의 메모리 영역을 논리적 단위로 나눠 저장하므로 단위별로 데이터를 보호하기 쉽다
• 단점
  • 외부 단편화 발생 : 세그먼트의 크기가 균등하지 않아서 프로세스의 할당/해제를 반복하는 과정에서 외부 단편화 발생 가능
  • 메모리 영역 중복 : 메모리에 로드된 스택 세그먼트 영역에서 오버플로가 발생하면 다른 프로세스와 메모리 영역이 겹칠 수 있다. 그러면 다른 프로세스의 세그먼트나 스택 오버플로가 발생한 세그먼트를 디스크로 스왑 아웃해야 한다.

논리 메모리와 물리 메모리

CPU가 프로세스를 처리할 때 보는 주소 값과 실제 메모리의 주소 값은 다르다.

• 논리 메모리 영역(logical memory addrress space)(= 가상 메모리 영역 = virtual memory address space) : 프로세스가 보는 메모리 영역
• 물리 메모리 영역(physical memory address space) : 실제로 사용되는 메모리 영역(RAM)
• 논리 주소(logical address)(가상 주소 = virtual address) : CPU가 프로세스를 실행하며 보는 주소 값'
• 물리 주소(physical address) : 실제 메모리에서 사용되는 주소

메모리 관리 장치(MMU, Memory Management Unit)

• CPU가 프로세스를 실행할 때 사용하는 주소 값과 실제 주소 값이 다르므로, 논리 주소를 물리 주소로 변환
• CPU에 위치하며, CPU에서 메모리에 접근하기 전에 MMU를 거쳐 논리 주소에 해당하는 물리 주소를 얻는다.
• 보호해야 하는 메모리 영역에 대한 접근을 제한해 메모리를 보호하는 역할을 한다.

요구 페이징(demand paging)

프로세스에서 필요한 페이지만 메모리에 로드

페이지를 모두 디스크로부터 메모리에 로드하지 않고, 초기에 필요한 페이지만 로드 후 다른 페이지는 요청이 올 때 메모리에 로드한다.

프로그램을 실행하다가 물리 메모리에 필요한 페이지가 없을 때 이를 페이지 폴트(page fault)라고 한다. 페이지 폴트가 발생하면 디스크에서 필요한 페이지를 스왑 인 한다. 이때 페이지에 해당하는 메모리 영역이 물리 메모리에 있는지는 페이지 테이블로 파악할 수 있다. 페이지 테이블은 페이지에 해당하는 프레임이 존재하면 v(valid) 값을, 프레임이 존재하지 않거나 유효하지 않은 주소 값이면 i(invalid) 값을 반환한다.

페이지 폴트 발생 시 처리 과정

1. 필요한 페이지가 물리 메모리에 있는지 없는지를 페이지 테이블에서 확인한다. 페이지 폴트가 발생하면 i를 반환한다.
2. i를 반환하면 OS는 참조하려는 페이지의 주소 값이 유효하지 않은지 아니면 메모리에 로드되지 않은 영역인지 판단한다.
3. 필요한 페이지가 메모리에 로드되지 않은 영역이라면 디스크에서 해당 영역을 찾는다.
4. 디스크에서 해당 페이지 영역을 스왑 인한다. 이때 물리 메모리에 비어 있는 프레임(free frame)이 있으면 페이지를 해당 영역에 바로 로드한다. 만약 비어 있는 프레임이 없으면 페이지 교체 알고리즘(page replace algorithm)을 호출해 기존에 로드된 페이지를 디스크로 스왑 아웃한 후 새로운 페이지를 로드한다.
5. 페이지 테이블에서 새로 로드한 페이지의 값을 v로 변경한다.
6. 프로세스를 다시 실행한다.

• 장점
  • 메모리 절약
  • 메모리 효율적 관리
  • 프로그램 응답 속도 향상

스래싱(thrashing)

동시에 일정 수 이상의 프로그램을 실행했을 때 프로세스의 처리 시간보다 페이지 교체에 소요되는 시간이 더 많아져 오히려 CPU 이용률이 떨어지는 현상

다중 프로그래밍 시스템이나 가상기억장치를 사용하는 시스템에서 하나의 프로세스 수행 과정 중에 자주 페이지 부재가 발생함으로써 나타나며, 디스크 영역에서 필요한 페이지를 스왑 인 하고 불필요한 페이지를 스왑 아웃하는 페이지 교체 작업을 자주 하게 됨으로써 전체 시스템의 성능이 저하된다.

Locality

Locality(국부성, 지역성, 구역성, 국소성)는 프로세스가 실행되는 동안 주기억장치를 참조할 때 일부 페이지만 집중적으로 참조하는 성질이 있다는 이론

• 스레싱을 방지하기 위한 워킹 셋 이론의 기반
• 시간 구역성(Temporal Locality) : 프로세스가 실행되면서 하나의 페이지를 일정 시간 동안 집중적으로 액세스하는 현상
• 공간 구역성(Spatial Locality) : 프로세스 실행 시 일정 위치의 페이지를 집중적으로 액세스하는 현상

워킹 셋(Working set)

프로세스가 일정 시간 동안 자주 참조하는 페이지들의 집합

• 자주 참조되는 워킹 셋을 주기억장치에 상주시킴으로써 페이지 부재 및 페이지 교체 현상이 줄어들어 프로세스의 기억장치 사용이 안정된다.