Paging

paging이 등장한 배경 : External Fragmentation

Untitled

Untitled

process 를 contiguous 하게 메인 메모리에 넣어서 실행시키고, 다 실행시킨 프로세스는 메모리에서 제거하는 방식을 사용하면 나타나는 주요 문제가 external fragmentation 입니다.

즉, 수많은 hole 들이 발생하는데 총 빈 부분은 추가적인 process 을 담을 만큼 충분하지만, 막상 들어갈 곳은 없게 되는 것입니다.

이를 해결하기 위해 process 를 일정 크기인 page로 쪼개어 메인메모리에 넣는 방법을 고안하였고, 이를 paging 이라고 합니다.

Paging

Basic Concept

  • paging이란?

    프로세스를 메인 메모리에 담을 때 non-contiguous 하게 담도록 일정한 크기의 page 로 잘라 메모리의 프로세스를 관리하는 기법을 paging 이라고 말합니다.

Untitled

이런식으로 process 를 page 로 나누어 메인 메모리에 연속되지 않은 공간에 mapping 하여 넣어주면 메인 메모리의 들어갈 수 없는 hole 이 발생하지 않아 external fragmentation 을 해결할 수 있습니다.

Untitled

하지만 이런 식으로 page 들을 나눴을 때 process 가 정확히 맞아 떨어지지 않는 경우들도 있겠지만, 그렇다고 page 의 크기는 그에 특정하여 줄어들지 않습니다.

이렇게 page 내부에서도 빈 공간이 일어나는 현상을 internal fragmentation 이라고 정의합니다.

이 내부 단편화 문제를 해결하기 위해 현대 컴퓨팅 시스템에서는 segmentation 을 활용하여 해결하곤 합니다.

Segmentation

Paging과 달리 물리적인 크기의 단위가 아닌 논리적 내용의 단위(의미가 같은) 로 잘라 나눠서 메모리에 보관하는 방법입니다.

8_09_Segmentation.jpg

Segment는 크기가 고정되어 있지 않고 가변적이기 때문에 외부단편화가 발생할 가능성이 있어 이런 메모리 낭비가 심한 외부 단편화를 막기 위해 paging, segmentation 두 방식을 모두 사용한 segment 를 paging 하는 방법을 취합니다.

page & segmentation 혼용 기법

22255E42590C1D9607.jpg

  • 프로세스를 segment(의미단위) 로 자릅니다.

    의미있는 단위로 나누게 되면 보호와 공유를 하는 측면에 이점을 가질 수 있게됩니다.

  • 잘라진 segment 를 다시 일정 간격인 page 단위로 자릅니다.

하지만 이와 같은 경우는 메모리 조회 시에 테이블을 2가지 모두 거쳐야 하므로 속도가 오래 걸릴 수 있다는 단점이 존재합니다.

Page Table

CPU 에 의해서 생성된 모든 주소값은 아래 그림과 같이 page number 와 page offset 으로 나뉩니다.

Untitled

  • page number : page 들 중 어떤 page 를 참조하였는지
  • page offset : 참조한 page 안에서 어디를 참조하였는지

시스템마다 주어지는 p 의 길이와 d 의 길이가 달라져, page 의 size 나 존재할 수 있는 page 의 개수를 달리할 수 있습니다. 페이지의 크기는 시스템마다 다르지만 일반적으로 4096bytes, 즉 4KB 로 존재합니다.

앞서 contiguous memory 에서 설명했던 것 처럼 CPU 가 인식하는 주소값(logical address) 하고 실제 주소값(physical address) 은 차이가 있습니다. 여기서 page table 은 CPU 가 보는 logical address 를 page number , page offset 으로 나누어 page number로 page table 을 조회하여 해당 page 가 들어있는 frame 을 찾아냅니다. (참고로 frame 은 메인 메모리를 나눈 단위로 page 와 크기가 같음).

그래서 physical address 로 변환된 주소값을 이용하여 해당 frame 의 특정 부분에 접근하게 해 주는 중간다리 역할을 page table 이 합니다.

Untitled

TLB (Translation Lookaside Buffer)

프로세스는 프로세스마다 page table 을 가집니다. 만약 프로세서로 32bit CPU 를 사용한다면 하나의 page 를 4KB ($2^{12}$) 의 크기를 가진다고 할 때 page table 은 $2^{20}$ 개의 page 들을 mapping 할 수 있는 테이블이어야 합니다. 그럼 대략 페이지 테이블의 용량은 $2^{20} * 4$ (int 크기) 정도가 됩니다.

이 page table 은 4MB 로 CPU 안에 있는 특별한 연산장치인 MMU 에는 들어가지 않는 크기입니다. 그래서 CPU 안에는 못 두고 메인 메모리에 둘 수 밖에 없는데, 이는 메모리를 1번 접근한다는 명령어가 있을 때 페이지 테이블 1번, 실제 주소값 한번해서 메인 메모리 접근을 2번 해야된다는 비효율이 발생합니다.

이를 해결하기 위해서 우리는 cache 를 사용하여 자주 쓰는 page 들을 저장하는 접근 속도가 빠른 저장소를 활용하게 됩니다.

Untitled

TLB 기본 동작

  1. page number → frame number translation 요청이 들어오면 요청된 주소값에서 page number 을 뽑아냅니다.
  2. 해당하는 translation 이 TLB 에 있는지 확인합니다.
  3. (TLB Hit) TLB 에 있으면 해당 버퍼를 확인하여 frame number 로 변환하여 반환해줍니다
  4. (TLB Miss) TLB에 없으면 page table 에 접근하여 frame number 로 변환하여 반환해줍니다.
    1. 그 후 해당 page table entry 값을 TLB 에 update 시켜줍니다.

실제 아래와 같은 코드가 있다고 하고, 이 코드가 오른쪽과 같은 page table 을 가지고 있다고 할 때

int sum = 0;
for(int i=0; i<10; i++)
{
		sum+=a[i];
}

img1.daumcdn.png

TLB 가 비어있다고 가정할 때 a[0], a[3], a[7] 을 조회할 때는 page table 을 직접 참조해야겠지만 나머지는 TLB 안에 존재하여 TLB hit 이 발생해 70% 의 변환 작업에서는 이득을 볼 수 있습니다.

이를 우리는 spacial locality 를 사용했다 하고, 이는 cache 를 사용하는 이유 중 하나입니다.

ASID (Address Space Identifier)

TLB entry 에 저장하는 값은 virtual address, physical address 말고도 해당 entry 가 차있는지 확인하는 valid bit, protection bit 와 ASID 라는 값이 있습니다.

img1.daumcdn.png

이 값은 TLB 용량이 작기 때문에 여러 프로세스가 나눠 써야하는데, context switching 될 때마다 TLB 값을 비워주는건 비효율적인 방법이기 때문에 ASID 값을 추가하여 어떤 프로세스가 사용하는 버퍼값인지 알려줘 다른 프로세스가 내 address space 를 침범하지 않도록 하는 역할을 합니다.

TLB 관리 정책

img1.daumcdn.png

TLB 는 용량이 제한되어 있어 해당 메모리가 꽉 차면 replacement 가 일어나야 합니다.

이 때 많은 종류의 cache 가 자주 사용하는 replacement policy 인 LRU(least recently used) 방식을 태책하여 entry 를 삭제하게 됩니다.

질문

  • fragmentation 에 대해 설명해보세요

    1. external fragmentation

      → contiguous 한 메모리 구성에서 발생 가능

      → paging 을 활용하여 해결

    b. internal fragmentation

    → segmentation 활용하여 해결

    → paging 과 혼용하여 사용 가능.

  • paging 에 대해 설명해보세요

    특정 프로세스를 메인 메모리에 적재시킬 때 일정한 크기로 나눠서 관리하는 기법

    external fragmentation 을 방지하여 메모리를 효율적으로 사용할 수 있게 함

    internal fragmentation 이 일어날 가능성이 있음

  • TLB 가 뭔가요?

    translation lookaside buffer 로 page table 의 cache 임

    main memory 에 있는 page table 과는 달리 MMU 안에 들어있어 접근이 빠르다.

  • Context switching 이 일어날 때 특정 프로세스의 cache 인 TLB 에서 일어나는 일은?

    flush 하는 동작 대신에 ASID 를 통해 프로세스마다 접근할 수 있는 entry 를 다르게 한다.

참조문헌

운영체제(OS) 목차 &책 추천

Translation Lookaside Buffers - TLB란?