[운영체제 8주차] - 메모리 관리 II & 메모리 관리 III

반효경 교수님의 운영체제 강의와 Operating System Concepts 10th ed. 를 참고하였습니다.

Paging

페이징이란 연속적으로 할당하는 메모리 관리 기법의 한계를 극복하고자, 물리적인 메모리를 일정한 단위로 나누어 관리하는 불연속 할당 기법을 말한다.

Paging

• 프로세스의 virtual memory를 동일한 size의 page 단위로 나눔
• 이 page들 중 일부를 메모리에 불연속적으로 올리고 일부는 backing store에 보관함
• 보편적인 방법
  • 물리 메모리를 동일한 크기의 page frame으로 나눔
  • logical memory를 동일 크기의 page로 나눔(frame과 같은 크기)
  • 모든 가용 frame들을 관리
  • page table을 사용하여 logical address를 physical address로 변환
  • 외부 조각은 생기지 않고, 내부 조각은 발생 가능하다.
    - 외부 조각은 당연히 생기지 않는다. 왜냐하면 빈 칸이 있으면 연속적이지 않더라도 불연속적으로 할당해줄 수 있기 때문이다. 하지만 내부 조각은 왜 생길까? 균일한 간격으로 주소공간을 자르다 보면, 딱 나눠 떨어지지 않는 페이지가 있을 수 있기 때문이다.

예시 그림을 보면 한 프로세스의 주소공간을 4페이지로 잘라놓고, 물리 메모리 상에 불연속적으로 페이지를 로딩해놓았다. page table는 이 프로세스의 어떤 페이지가 실제 메모리 주소의 어디에 있는 지 알려주고 있다. page table은 페이지 넘버(entry)를 인덱스로 하는 배열 형태로 페이지 넘버를 통해 직접 접근이 가능해진다.

위 예시에서는 모든 페이지가 메모리에 로딩되어 있다. 그러나 그렇지 않은 경우에는? 애매한 숫자를 담기 보다는 페이지 테이블에서는 valid/invalid bit를 통해 관리한다. CPU는 valid bit를 메모리 상에 이 페이지가 로딩된 경우에는 valid, 메모리 상에 없거나 사용되지 않는 경우에 invalid로 바꾼다.
페이지 테이블에는 그런 경우를 포함하여 다양한 정보를 담고 있다.
더 알아볼 것:페이지 테이블에 담긴 정보들 알아보기

그러면 CPU는 어떻게 실제 페이지의 위치를 찾는가? 연속 할당 기법과 마찬가지로 register의 도움을 받는다. PTBR(Page-table Base Regiseter)은 page table의 시작점을 가리킨다. PTLR(Page-Table length register(PTLR)은 테이블 크기를 보관한다. 즉, 연속할당과 유사하게 페이지 테이블의 시작점과 범위를 담고 있는 것이다.
CPU는 논리 주소 상 페이지 넘버와 페이지 내에서의 위치를 가르킨다. 그러면 페이지 테이블 상에 해당 페이지가 어디에 있는지 찾는다. 그리고 실제 메모리의 프레임 위치를 찾고 나서 페이지 내 위치를 합산하여 실제 메모리 주소를 찾는다.

즉 절대 위치 + 상대 위치의 조합으로 페이지가 올라간 실제 메모리 주소를 찾는다. 그런데 여기서 알아야할 점은 페이지 테이블 또한 메모리에 적재되어있다는 것이다. 일반적으로 메인 메모리에 접근하는 것은 매우 비용이 많이 드는 연산이다. CPU 대비 메인 메모리는 속도가 매우 느린 저장장치이기 때문이다. 그런데 페이지 테이블을 참조하기 위해 1번, 실제 실행을 위해 1번 총 2번의 메모리 접근을 해야 한다.

이런 시간을 줄여보고자, 캐싱을 위해 TLB(Translation Lookaside buffer)라는 버퍼를 하나 둔다. 최근 참조된 페이지의 프레임 정보를 저장해두었다가, 메모리에 찾으러 가기전에 먼저 살펴본다. 만약 TLB에 찾는 page가 있다면 cache hit가 발생하고, 곧바로 메모리상의 주소를 찾아갈 수 있다. 즉, 메모리 접근이 1번 줄어드는 효과가 있다.

cache hit ratio = alpha, 메모리 접근 시간 = 1, TLB 접근 시간 = e라면, effecitve access time은 다음과 같이 계산된다.
EAT = (1+e)*alpha + (2+e)*(1-alpha)

그런데 TLB는 table 구조가 아니라 page number, frame number 값을 갖는 구조로 되어 있다. 즉 page number로 바로 접근할 수 없고 TLB의 모든 엔트리를 다 뒤져야 한다. 이런 탐색은 O(N)이 소모되는만큼, TLB에서는 associative memory처럼 병렬 탐색이 가능하도록 만들어 사용한다.

그리고 당연하게도, 각 프로세스마다 독자적인 페이지 테이블을 가지므로 TLB 또한 프로세스마다 달라져야 한다. context switch가 발생하면 TLB 또한 모두 flush된다.

운영체제의 주소 체계

여기서 짚고 넘어가야할 점이 하나 더 있다. 운영체제의 주소 체계이다.
보통 32비트 운영체제, 64비트 운영체제라고 한다. 여기서 말하는 이 비트가 주소체계의 비트 수이다.

32비트가 표현할 수 있는 정보의 개수는 당연하게도 2^32가지이다. 이는 대략 4G개이다. (4x10^9개) 그리고 메모리는 byte 단위로 관리된다. 즉, 32비트 주소체계를 가지는 운영체제가 인식할 수 있는 메모리의 최대 용량은 4G byte가 되는 것이다.

페이지의 개수

그럼 4기가의 메모리 크기를 4kb인 페이지 단위로 쪼개면 총 몇개일 까? 1M개이다. 즉 10^6 = 1,000,000개이다. 즉, 각 이 페이지들을 관리하려면 페이지 테이블 상에 백 만개의 엔트리가 필요한 셈이다.

그럼 페이지 테이블의 크기는?

그럼 100만개의 엔트리가 필요하다면, 페이지 테이블의 전체 크기는 어떻게 될까?
각 엔트리의 크기가 4 byte라면 4M의 메모리가 필요한 셈이다.
그러나 대부분의 프로그램은 가상 주소 공간 4G중 지극히 일부분만 사용하므로 page table로 메모리가 심각하게 낭비되고 있는 것이다.

페이지 테이블도 페이지로 관리해보자!

그래서 페이지 테이블 자체도 페이지라는 단위로 쪼개는 방법이 있다. 페이지 테이블이 2단계라고 하여 Two-Level Page Table이라고 부른다.

바깥쪽 페이지 테이블에는 안쪽 페이지 테이블의 엔트리가 들어있고, 안쪽 페이지 테이블에는 실제 메모리 프레임이 들어있다.

그런데 이렇게 되면 메모리 주소 변환을 위해 메모리 테이블을 2번 접근해야 한다. 총 3회의 메모리 접근이 발생하는 셈이다. 게다가 어차피 페이지의 개수도 동일하므로 페이지 테이블의 크기가 변할까도 의문이다. 시간에서도 손해, 공간적으로도 큰 이득이 없어 보이는데 왜 이 방법을 사용할까?

낭비되는 페이지 테이블이 줄어든다

페이지 테이블은 배열이기 때문에 사용되지 않는 페이지라고 하더라도 모든 엔트리를 유지해야 한다. 하지만 대부분의 프로세스는 자신의 주소공간 중 극히 일부만 사용할 것이기 때문에 페이지 테이블의 대부분은 필요가 없음에도 모든 엔트리를 만들어 낭비가 된다.

그래서 two-level page에서 안쪽 페이지 테이블은 페이지 테이블이 4kb로 쪼개진 페이지들을 가르키고 있다. 4kb로 쪼개진 페이지 테이블은 총 4 byte 짜리 entry를 1K개 가지고 있을 것이다. (기존에 페이지 테이블 크기가 4M이었으므로)

그리고 위 그림과 같이 바깥쪽 테이블은 사용하지 않는 페이지 테이블은 null로 두어 안쪽 페이지 테이블을 만들지 않아서 공간을 절약한다.

logical address의 구성

그럼 위의 32bit 주소체계에서의 two-level page의 논리 주소 구성을 살펴보자.
기존의 단일 페이지에서는 page number, page offset만 필요했지만, 이제는 두 계층의 page가 있기 때문에 page number가 2개로 늘어난다.
그럼 먼저 page offset은 몇 bit일까? 페이지 하나가 4kb 이므로, 1 byte 단위의 주소를 구분하기 위해서는 4k개의 bit가 필요하다. 즉, 4k = 2^12이므로, page offset에서는 12비트가 필요하다.

다음으로 안쪽 페이지 테이블을 보자. 안쪽 페이지 테이블 또한 4kb 단위로 쪼개진 페이지 형태이고, 각 엔트리는 4 byte를 가진다. 그럼 4kb 크기의 페이지에서 각 엔트리의 위치를 구별하기 위해서는 2^10이 필요하다. 즉, p2는 10 비트가 필요하다.

마지막으로 바깥쪽 페이지 테이블의 위치 p1은 32비트 중에서 12비트, 10비트를 뺀 10비트를 사용하는 것이다.

Multilevel Paging and Performance

• 주소 공간이 더 커지면 다단계 페이지 테이블이 필요하다.
• 각 단계의 페이지 테이블이. 메모리에 존재하므로 레벨이 커질수록 메모리 접근이 더 많이 필요하다.
• 어차피 주소공간 중 일부만 쓰이기 때문에 TLB를 통해 hit ratio를 높여 메모리 접근횟수를 많이 줄일 수 있다. 공간은 절약하면서 시간이 늘어나는 부작용은 최소화할 수 있는 것이다.

entry에 담긴 정보들

• Protection bit
  원래 각 프로세스는 자기 자신의 페이지 테이블만 접근할 수 있게 되어있다. 그래서 접근 보호라기보다는 연산에 대한 권한을 표시해주는 비트이다. read-only/read-write/execute-only 등의 보호를 설정해줄 수 있다.

• Valid-invalid bit
  위에서 설명한 것으로, valid하다는 것은 현재 frame 상에 페이지가 올라와있다는 것을 의미하고(접근 허용), invalid하다는 것은 현재 frame 상에 페이지가 올라와있지 않거나, 프로세스가 그 주소를 사용하지 않는다는 것을 의미한다.(접근 불허)

Inverted Page Table

Inverted Page table은 프로세스 당 페이지 테이블이 존재하는 것이 아니라, 물리적 메모리의 frame에 대한 페이지 테이블이 존재한다. 즉, 해당 물리적 메모리의 프레임에 어떤 프로세스의 몇 번째 페이지가 있는지 확인할 수 있는 것이다. 이렇게 하면 모든 프로세스의 페이지를 페이지 테이블 하나로 관리할 수 있는 장점이 있다.

다만, 주소 변환은 논리적 주소를 통해 페이지 테이블을 직접 접근하여 물리적 주소를 얻는 과정이다. 그런데 이렇게 되면 페이지 테이블에 직접 접근할 수 없으므로 페이지 상의 엔트리를 모두 탐색해보아야 한다.

그래서 가능하다면, TLB처럼 associative register를 사용해 parallel search가 가능한 식으로 구현을 해야 시간/공간 효율을 모두 챙길 수 있다. 하지만 TLB와 같은 메모리는 매우 비싸므로 비용이 많이 들게 된다.

Shared Page

알다시피 모든 프로세스는 독자적인 주소공간을 가진다. 하지만 프로세스들의 주소공간의 내용은 모두 다를까? 널리 사용되는 라이브러리를 쓴다든가 하면 그 내용은 중복될 것이다. 극단적으로 프로세스들이 모두 같은 프로그램이라면? code 영역은 모두 동일할 것이다.

그런데 이것들을 모두 메모리상에 올린다면? 당연히 메모리가 낭비된다. 그래서 페이징 기법에서도 이것들을 공유 페이지(Shared Page)로 관리한다. 공유되는 영역에 해당하는 페이지를 프레임 상에 올려놓고 이를 사용하는 모든 프로세스들은 이 페이지를 쓸 때 동일한 프레임 상에 접근하는 것이다.

여러 프로세스가 동일한 메모리 공간에 접근하므로 일종의 Shared memory 방식이다. 하지만 프로세스 간 통신에서 사용하는 Shared memory에서는 통신이 목적이므로 read-write가 모두 가능했지만, 여기서는 반복되는 코드의 재사용이 목적이므로 항상 내용이 일정하도록 read-only가 필수적이어야 한다.

또한, 각 프로세스의 주소공간 상에서 동일한 논리주소를 가져야 한다. 왜냐하면 페이지 테이블 상에서 그 논리주소로 조회했을 때 공유되는 페이지가 있는 프레임이 나와야 하기 때문이다. 즉, 페이지 번호가 같아야 된다는 소리이다.

Segmentation

세그멘테이션 기법은 동일 크기로 자르는 페이지와 달리, 메모리가 갖는 의미 단위로 자르는 방법이다. 프로세스의 주소 공간은 code, data, heap, stack과 같이 각 영역이 의미를 가지고 있다.

이런 것들을 하나의 segment로 보고 쪼개는 것이다. 작게 보면 메소드도 하나의 세그먼트로 볼 수 있다. 그리고 의미 단위로 자르기 때문에 당연히 나눠진 segment 간의 크기는 일정하지 않다.

위 그림을 보면 페이지 테이블과 유사한 구조의 세그먼트 테이블로 세그먼트를 관리하고 있다. s번째 entry를 통해 세그먼트 테이블에서의 위치를 찾고, d만큼의 offset을 통해 실제 위치를 찾는다.

단, 페이지와는 달리 각 엔트리는 limit이라는 정보를 가지고 있는데 base로부터 그 세그먼트의 크기를 나타내는 것이다. 페이지와 달리 세그먼트는 그 크기가 일정하지 않기 때문이다. 만약 d가 세그먼트의 크기를 초과한다면, trap을 발생시킨다.

그리고 base 또한 페이지 프레임의 주소가 아닌 실제 메모리 주소가 나와있다.

Segmentation Architecture

• STBR, STLR
  PTBR, PTLR과 같은 기능을 수행한다. STBR(Segment-table base register)는 메모리 상의 세그먼트 테이블의 시작점을 가르키고, STLR(Segment-table length register)는 세그먼트 테이블의 길이, 즉 세그먼트 개수를 가르킨다.

• Protection
  페이징과 마찬가지로 Protection bit, valid/invalid bit가 있다.

• Sharing: Shared Segment, same segment number
  segment는 의미 단위이기 때문에 공유와 보안에 있어 페이징보다 훨씬 효과적이다. 예를 들어, code segment는 공유하고 stack segment는 독자적으로 관리하는 등 공유를 구현하기 매우 편리하다. 페이징 기법에서는 공유 영역이 페이지 크기로 나누어떨어진다는 보장이 없기 때문에 같은 페이지에서 일부는 공유 영역, 일부는 아닌 경우가 발생할 수 있지만 세그멘테이션은 그럴 일이 없다.

• Allocation: 페이징 기법에서는 모두 같은 크기의 페이지로 나누었기 때문에 프레임 아무데나 페이지를 올릴 수 있었지만, 세그먼트는 크기가 각각 다르기 때문에 어디서 할당할 지에 대한 문제가 추가된다. (first fit/best fit 등을 활용해야 한다)
  이렇게 되면 페이징에서는 발생하지 않던 외부 조각이 발생하게 된다.

• 세그먼트는 아무래도 페이지보다 쪼개는 단위가 크기 때문에 세그먼트 테이블 자체의 크기는 더 작을 것이다. 그래서 프로세스마다 세그먼트 테이블이 존재해도 메모리 낭비를 줄일 수 있다는 장점이 있다.

Segmentation with Paging

하지만 실제로 순수하게 세그멘테이션만을 사용하는 경우는 거의 없다. 적용한다면 보통 세그먼트를 다시 페이지로 쪼개서 메모리에 올리는 방법을 사용한다.

즉, 페이지 테이블이 같은 의미를 갖는 세그먼트 단위로 관리되는 것이다.

그림과 같이, s/d가 주어지면 s는 segment table의 엔트리를 가리키고, 엔트리에는 segment 길이와 page table의 시작점이 있다. segment 길이는 page table의 크기를 나타내는 것과 같다. 그 다음 세그먼트 테이블에서의 offset인 d를 통해 몇번째 페이지 엔트리의 offset d'인지로 쪼갠다. d를 페이지 크기로 나눈 다음 나머지가 d'이 될 것이다. 그럼 페이지 테이블의 엔트리에서 실제 메모리의 몇번 프레임에 해당하는 지 찾아서 d'를 적용하면, 실제 메모리 접근이 가능해진다.