[OS] Memory Management - 2

본 글은 반효경 교수님의 운영체제 강의를 들으며 정리하는 글 입니다.

 

1. Paging

logical memory는 페이지 단위로 분할이 되고, 물리적 메모리는 프레임 단위로 분할이 되어 서로 매칭된다.

이때 논리적 주소를 물리적 주소로 변환하기 위해 페이지 테이블을 활용한다.

 

1 - 1) 주소 변환 기법

페이징 기법에서는 CPU가 사용하는 논리적 주소를 페이지 번호(p)와 페이지 오프셋(d)으로 나누어 주소 변환에 사용한다.

 

페이지 번호는 각 페이지별 주소 변환 정보를 담고 있는 페이지 테이블 접근 시 인덱스로 사용되고, 해당 인덱스의 항목에는 그 페이지의 물리적 메모리 상의 기준 주소, 즉 시작 위치가 저장된다.

 

따라서 특정 프로세스의 p번째 페이지가 위치한 물리적 메모리의 시작 위치를 알고 싶다면 해당 프로세스의 페이지 테이블에서 p번째 항목을 찾아보면 된다. 위 그림에서는 f를 찾게된다.

 

page offset은 하나의 페이지 시작지점에서 얼마나 떨어저 있는지를 알려준다.

따라서 기준 주소 값에 offset을 더함으로써 요청된 논리적 주소에 대응하는 물리적 주소를 얻을 수 있다.

 

위 그림에서 f (물리적 주소의 시작 위치) + d를 취하면 처음에 CPU가 요청한 논리적 주소에 대응하는 물리적 주소가 된다.

 

1 - 2) 페이지 테이블의 구현

• 페이지 테이블은 페이징 기법에서 주소 변환을 하기 위한 자료 구조로, 물리적 메모리인 Main Memory에 상주한다.
• 현재 CPU에서 실행 중인 프로세스의 페이지 테이블에 접근하기 위해 운영체제는 2개의 레지스터를 사용한다.
  • 페이지 테이블 기준 레지스터(page-table base register) : 메모리 내에서 페이지 테이블의 시작 위치를 가리킴
  • 페이지 테이블 길이 레지스터(page-table length register) : 페이지 테이블의 크기를 보관함
•  페이징 기법에서 모든 메모리 접근 연산은 총 2번씩 필요하다. 이는 주소 변환을 위한 페이지 테이블이 메모리에 저장되기 때문이다.
  • 주소 변환을 위해 페이지 테이블에 접근
  • 변환된 주소를 통해서 실제 데이터에 접근
  • 이러한 오버헤드를 줄이고 메모리의 접근 속도를 향상하기 위해 TLB(Translation Lock-aside Buffer)라고 불리는 고속의 주소 변환용 하드웨어 캐시를 사용한다.

 

1 - 3) TLB (Translation Lock-aside Buffer)

TLB는 가격이 비싸기 때문에 빈번히 참조되는 페이지에 대한 주소 변환 정보만 담게 된다.

 

요청된 페이지 번호가 TLB에 존재한다면 곧바로 대응하는 물리적 메모리의 프레임 번호를 얻을 수 있지만, TLB에 존재하지 않는 경우에는 메인 메모리에 있는 페이지 테이블로부터 프레임 번호를 알아내야 한다.

 

페이지 테이블에는 페이지 번호가 주어지면 해당 페이지에 대응하는 프레임 번호를 얻을 수 있지만, TLB에는 페이지 번호와 프레임 번호 쌍을 가지고 있으므로 특정 페이지 번호가 있는지 TLB 전체를 찾아봐야 한다.

이때 TLB 풀 스캔 시간이 오래 걸리므로 병렬적으로 탐색이 가능한 연관 레지스터를 사용한다.

 

TLB는 context switch시, 이전 프로세스의 주소 변환 정보를 담고 있는 내용이 전부 flush되어 지워진다.

 

1 - 4) 연관 레지스터를 사용한 평균 메모리 접근 시간 (Effective Access Time)

• 메모리에 접근하는 시간을 1이라 하고, 연관 레지스터에 접근하는 시간을 ε이라고 하자. (이때, ε은 1보다 충분히 작은 값이다.)
• 요청된 페이지에 대한 주소 변환 정보가 연관 레지스터에 존재할 확률을 a라고 하자.
• 평균적인 메모리 접근 시간 EAT는 다음과 같다.
  • EAT = (1 + ε)a + (2 + ε)(1 - a) = 2 + ε - a
  • (1 + ε)a 항은 요청된 페이지의 주소 변환 정보가 TLB에 존재하는 경우이다.
    • TLB로부터 직접 물리적인 메모리에 얻는 데 ε시간이 소요되고, 실제 원하는 데이터에 접근하기 위해 한 번에 메모리 접근이 필요하므로 (1 + ε)이 된다. 여기에 TLB에서 존재하는 확률인 a를 곱하면, (1 + ε)a가 된다.
  • (2 + ε)(1 - a) 항은 요청된 페이지에 대한 주소 변환 정보가 TLB에 존재하지 않는 경우이다.
    • 요청된 페이지에 대한 주소 변환 정보가 TLB에 있는지 확인하는 시간 ε이 소요되고, 페이지 테이블에 접근하는 시간 ε과 실제 원하는 데이터에 접근 시간 a, 두 번의 메모리 접근이 필요하게 된다. 따라서 (2 + ε)의 시간이 소요되며, 여기에 TLB에서 찾지 못하는 비율인 (1 - a)를 곱하여 (2 + ε)(1 - a)가 된다.

 

1 - 5) 계층적 페이징

• 현대의 컴퓨터는 주소 공간이 매우 큰 프로그램을 지원한다.
  • 예를 들어 32비트 주소 체계를 사용하는 컴퓨터에서는 4GB의 주소 공간을 갖는 프로그램을 지원한다.
    • page size가 4K라면, 한 프로세스(4G)당 페이지 테이블을 위해 1M 개의 page가 생성된다.
    • 각 프로그렘마다 page table이 따로 있기에, 이러한 page table을 전부 메모리에 올리면 공간 낭비가 심하다.
    • page table의 entry 하나의 크기가 4byte 이니, process당 4M의 page table이 필요하다
    • 그러나 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하므로 페이지 테이블 공간이 심하게 낭비된다.
• 위 문제로 인하여 페이지 테이블 자체를 페이지로 구성하는 2단계 페이징 기법을 사용한다.

 

1 - 5 - 1) 2단계 페이징 기법

• 주소 변환을 위해 외부 페이지 테이블과 내부 페이지 테이블의 두 단계에 걸친 페이지 테이블을 사용한다.
• 사용하지 않는 주소 공간에 대해서는 외부 페이지 테이블의 항목을 NULL로 설정하며, 여기에 대응하는 내부 페이지 테이블을 생성하지 않는다.
• 페이지 테이블을 위해 사용되는 메모리 공간을 줄이지만, 페이지 테이블의 수가 증가하므로 접근시 시간적인 손해가 뒤따른다.
• 안쪽 page table의 크기는 page 크기(4KB)와 똑같다. 즉 안쪽 page table은 page화 되어 memory어딘가에 들어가 있다.

 

1 - 5 - 2) 2단계 페이징 기법의 주소 변환

• 프로세스의 논리적 주소를 두 종류의 페이지 번호(P1, P2)와 페이지 오프셋(d)으로 구분한다.
  • P1은 외부 페이지 테이블의 인덱스이고, P2는 내부 페이지 테이블의 인덱스이다.
  • 논리적 주소를 <P1, P2, d> 형태로 표시할 수 있게 된다.

 

외부 페이지 테이블로부터 P1만큼 떨어진 위치에서 내부 페이지 테이블의 주소를 얻게 되고, 내부 페이지 테이블로부터 P2만큼 떨어진 위치에서 요청된 페이지가 존재하는 페이지 프레임의 위치를 얻은 후, 해당 프레임으로부터 d만큼 떨어진 곳이 바로 찾으려는 물리적 주소이다.

 

32비트 주소 체계를 갖는 시스템에서 페이지 하나의 크기를 4KB라 하고 페이지 테이블 항목의 크기를 4byte라고 할 때, 32비트의 논리적 주소 중 페이지 번호와 페이지 오프셋을 위해 각각 몇 비트씩 할당해야 하는가?

• 먼저 페이지 하나의 크기가 4KB(2^12 Byte)이므로 하나의 페이지 내에서의 byte 오프셋을 결정하기 위해 12비트가 필요하다.
• 2단계 페이징 기법에서는 내부 페이지 테이블 자체를 하나의 프레임에 보관하게 되므로 내부 페이지 테이블의 크기 역시 4KB가 된다. 페이지 테이블 항목의 크기가 4byte이므로 내부 페이지 테이블은 4KB/4byte, 즉 1K개의 항목을 가지게 된다.
• 1K(2^10 Byte) 항목을 구분하기 위해서는 10비트가 필요하다.
• P1은 (32 - 12- 10)을 취하여 10비트가 할당된다.

 

1 - 5 - 3) 다단계 페이징 기법

• 프로세스의 주소 공간이 커질수록 페이지 테이블의 크기도 커지므로 주소 변환을 위한 메모리 공간 낭비가 심해진다.
• 다단계 페이지 테이블을 사용하면 페이지 테이블을 위해 사용되는 메모리 공간의 소모를 줄일 수 있지만, 메모리 접근 시간이 늘어난다.
• TLB를 통해 메모리 접근 시간을 줄일 수 있다.
• 4단계 페이지 테이블을 사용하는 경우
  • 메모리 접근 시간이 100ns, TLB 접근 시간이 20ns
  • 요청된 페이지에 대한 주소 변환 정보가 TLB에 존재할 확률 98%
  • 평균 메모리 접근 시간 (EAT) = 0.98 x 120 + 0.02 x 520 = 128ns
    • TLB hit이 성공할 때는 TLB 접근 시간과 메모리 접근 시간의 합인 120ns가 된다.
    • TLB hit이 실패할 때는 TLB 접근 시간과 메모리 접근 시간 x 5의 합인 520ns이 된다.
  • 결과적으로 주소 변환을 위해서만 28ns가 소요된다.

 

1 - 6) Memory Protection

Page table의 각 entry마다 다음 2종류의 bit가 추가적으로 있다.

1 - 6 - 1) Protection bit

page에 대한 접근 권한을 나타내는 bit이다. read, write, read-only 

 

1 - 6 - 2) Valid-invalid bit

"valid"의 의미는 해당 주소의 farame에 그 process를 구성하는 유효한 내용이 있다는 것 이다.

"invalid"의 의미는 해당 주소의 frame에 유효한 내용이 없음을 뜻한다.

 

1 - 7) 역페이지 기법

페이지 테이블로 인한 메모리 공간의 낭비가 심한 이유가 뭘까?

바로, 모든 프로세스마다 자신의 페이지에 대한 페이지 테이블을 구성해야 하기 때문이다.

 

이러한 문제를 해결하기 위해 역페이지 기법을 사용할 수 있다. (Page Table을 하나만 사용하는 방식!)

• 물리적 메모리의 페이지 프레임 하나당 페이지 테이블에 하나씩의 항목을 두는 방식이다.
• 논리적 주소에 대해 페이지 테이블을 만드는 것이 아니라, 물리적 주소에 대해 페이지 테이블을 만드는 것이다.
• 시스템 전체에 페이지 테이블을 하나만 둔다.
• 페이지 테이블의 각 항목은 어느 프로세스의 어느 페이지가 이 프레임에 저장되었는 지의 정보를 보관하고 있다.
  • 페이지 테이블의 각 항목은 프로세스 번호(pid)와 그 프로세스 내의 논리적 페이지 번호(p)를 담고 있다.
• 이 방식은 기존의 page table처럼 index로 접근할 수 있는 방식이 아니라, 페이지 전체를 탐색해야 하는 단점이 있다.
  • 따라서 일반적으로 associative register를 사용하여 병렬 탐색을 수행한다.

 

1 - 8) Shared Page

Shared code는 메모리 공간의 효율적인 사용을 위해 여러 프로세스에 의해 공통적으로 될 수 있도록 작성된 코드를 말한다.

Re-entrant Code, Pure Code라고도 불리며, Read-Only의 특성을 가지고 있다.

 

공유 페이지는 공유 코드를 담고 있는 페이지를 말한다.

공유 페이지는 여러 프로세스에 의해 공유되는 페이지이므로 물리적 메모리에 하나만 적재되어 메모리를 효율적으로 사용할 수 있다.

 

예를 들어 문서 편집기 프로그램을 공유 페이지를 사용해서 작성한 경우, 이 프로세스를 여러 개 수행하더라도 공유 코드를 담은 페이지는 메모리에 하나만 올라간다.

공유 코드는 읽기 전용의 성질을 가져야 하고 모든 프로세스의 논리적 주소 공간에서 동일한 위치에 존재해야 한다.

 

private code and data는 프로세스들이 공유하지 않고 독자적으로 메모리에 올린다.

private data는 해당 프로세스의 논리적 주소 공간 중 어떠한 위치에 있어도 무방하다.

ed 1, ed 2, ed 3는 shared page이고, data 1, data 2, data 3는 private code이다.