메모리 관리 II & 메모리 관리 III

Paging

메모리 단편화를 방지하기 위해 메모리를 페이지 라는 작은 단위로 나누어 메모리를 관리하는 관리하는 방법

• 프로세스(Process) 의 가상 메모리(Virtual memory)를 동일한 크기의 페이지(page) 단위로 분할

• 가상 메모리(Virtual memory) 의 내용이 페이지(page) 단위로 불연속적으로 저장됨

• 일부는 백업 저장소(Backing storage) 에, 일부는 물리 메모리(Physical memory) 에 저장됨

• Paging 의 기본적인 기능

  • frame 과 page를 동일한 크기로 잘라서, frame 에 page 를 담습니다.
  • External fragmentation(외부 조각) 이 발생하지 않는다는 장점이 있습니다.
  • Internal fragmentation(내부 조각) 은 발생할 수 있음
    • 이는 프로세스를 일정 단위로 자르다가 나누어떨어지지 않는 경우에 해당하는데, 외부 조각에 비해서는 비용이 크지 않음

• Internal fragmentation(내부 조각)

  • 프로그램 크기 < 분할의 크기
  • 하나의 분할 내부에서 사용되지 않는 메모리 조각
  • 특정 프로그램에 배정되었으나, 사용되지 않는 조각

• External fragmentation(외부 조각)

  • 프로그램 크기 > 분할(page, fragment)의 크기
  • 메모리의 빈 공간인데도, 프로그램이 올라갈 수 없는 작은 분할
    

Implementation of Page Table

• Page table 은 주 기억장치(main memory) 에 상주함
• Register
  • PTBR(Page-table base register) : page table 시작 주소를 저장
  • PTLR(Page-table length register) : 테이블 크기를 저장
• 모든 메모리 접근 연산에는 2번의 memory access 필요
  • 1) page table 에서 실제 주소를 찾기
  • 2) 실제 주소로 물리 메모리의 데이터에 접근
• 속도 향상을 위해 사용하는 고속의 캐시 사용(lockup hardware cache)
  • TBL(Translation lock-aside buffer)

Paging Hardware with TLB

TBL 는 Page table 의 일부를 캐싱하여, 주소 변환 속도 향상을 위해 사용합니다.
하지만 인덱스로 접근이 가능한 Page table 과는 달리, TLB 는 일부만 저장했기 때문에 하나 하나 탐색해야합니다.
속도 향상을 위해 사용하는데, 탐색시간이 더 오래걸리면 의미가 없습니다.
그래서 Associative register 라고 하는 병렬 탐색이 가능한 레지스터로 TBL 를 구성하게 됩니다.

• VPN(Virtual Page Number) → PFN(Physical Frame Number) 변환 속도 향상을 위해 사용
• 기본 알고리즘
  • 1) 주소 변환 요청이 들어오면, 주소값에서 VPN 을 추출
  • 2) 해당 VPN 과 일치하는 정보가 TLB 에 있는지 확인
  • 3-1) TLB 에 있으면 PFN 으로 변환하여 반환(TLB Hit)
  • 3-2) TBL에 없으면 Page table 에 접근하여 PFN 으로 변환하여 반환 후 TLB 에 기록(TLB Miss)
• TBL 가 속도 향상에 도움이되는 이유?
  • 프로그램은 대부분 이미 참조한 곳을 다시 참조할 가능성이 높기 때문

Two-Level Page Table

현대의 컴퓨터는 address space 가 매우 큰 프로그램을 지원함

• 32 bit address : 2³²(4GB) 의 주소 공간 표현 가능
  • page size 가 4KB 일 경우, 1M 개의 page table entry 필요
  • 각 page table entry 가 4KB 일 경우, 프로세스당 4MB 의 page table 영역이 할당되어야함
  • 하지만, 대부분의 프로그램은 4GB 의 주소 공간 중 일부분만 사용하기 때문에 page table 공간이 낭비됨
    → 그래서 page table 자체를 page 로 구성
    → 사용되지 않는 주소 공간에 대한 outer page table 의 엔트리 값은 null

현재는 많은 시스템이 64 bit address 로 동작하기 때문에, 더 큰 주소 공간을 표현할 수 있다.

Multilevel Paging and Performance

• Address space 가 더 커지면 다단계 페이지 테이블이 필요
• 각 단계의 페이지 테이블이 메모리에 존재하므로, VPN→PFN 변환에 더 많은 메모리 접근 단계 거쳐야함
• TBL 를 통해 메모리 접근 시간을 줄일 수 있음
• 4 단계 페이지 테이블을 사용하는 경우
  • 메모리 접근 시간이 100ns, TLB 접근 시간이 20ns 이명 TLB hit ratio 가 98% 인 경우
  • effective memory access time = 0.98 x 120 + 0.02 x 520 = 128ns
    결과적으로 28ns 만 소요됨

Valid(v) / Invalid(i) Bit in a Page Table

각 page table 의 entry 는 다음과 같은 bit 을 가진다

• Protection bit : 접근 권한(read/write/read-only)
• Valid-invalid bit
  • valid : 해당 주소의 frame 을 사용하고 있음을 의미
  • invalid : 해당 주소의 frame 에 유효한 내용이 없음을 의미
    1) 프로세스가 그 주소 부분을 사용하지 않는 경우
    2) 해당 페이지가 메모리에 올라와 있지 않고, swap area에 있는 경우

Inverted Page Table Architecture

Page table 은 모든 프로세스별로 가상 메모리에 대응하는 모든 page 에 대해 page table entry 존재합니다.
그래서 크기가 크고, 실제 메모리에 없더라도 entry 에 존재하는 비효율적인 측면이 있습니다.

Inverted Page table 은 Page frame 하나당 page table 에 하나의 entry 를 두는 방식입니다.
실제로 사용하는 공간에 비례하여 entry 가 존재하기 때문에 효율적입니다.

그러나 가상 메모리 를 찾을 때 page table 에 인덱스로 접근할 수 없어서 전체를 탐색해야 하는 단점이 있습니다.
그래서 병렬 탐색을 위해 연상 레지스터(Associative register) 를 사용합니다.

• Page table
  • 가상 메모리 크기 : 가질 수 있는 만큼(사용 안해도 일단 갖고있는 것 처럼 동작)
  • page table 크기 : 가상 메모리 크기만큼 entry 를 갖고있음
• Inverted Page table
  • 가상 메모리 크기 : 가질 수 있는 만큼
  • page table 크기 : 실제 메모리 frame 에 할당된 만큼만 entry 가 존재함

Shared Page

Shared code

프로그램을 여러번 실행하면 각 실행마다 프로세스가 생기게 되는데, 프로그램 코드를 각 프로세스마다 갖고 있는건 비효율 적입니다.
그래서 프로세스들이 공용으로 사용하는 공간에 read-only 로 코드를 저장하여, 각 프로세스들이 하나의 코드만 참조하게 됩니다.
모든 프로세스가 함께 사용하기 때문에 약속된 위치(항상 동일한 위치)에 존재해야 한다는 제약조건이 있습니다.

• Shared code 제약조건
  • 공유 코드들은 read-only 로 저장되어야 함
  • 가상 메모리 에서도 항상 동일한 위치에 존재해야함

그 이유는 프로그램이 처음 실행되며 코드는 이미 메모리 특정 번지를 참조하는 Instruction 들로 컴파일되었기 때문입니다.
그래서 모든 프로세스들은 자신이 사용하는 가상 메모리의 동일한 위치에 Shared code 가 위치해야 합니다.

Private code and data

각 프로세스들은 독자적으로 사용하는 코드와 데이터입니다.
이 데이터들은 예약된 위치가 아니라면, 가상 메모리 어디든 저장할 수 있습니다.

Segmentation

Paging 기법은 가상 메모리를 동일한 크기의 page 라는 단위로 자르고, 물리 메모리의 frame 과 매치시키는 방법이었습니다.
하지만 Segmentation 은 이와 다르게, 가상 메모리 를 segment 라는 의미있는 단위로 잘라서 관리합니다.
(일반적으로 code, data, stack 이 하나의 segment로 정의됩니다)
그래서 Segment 는 각각 크기가 다를 수 있습니다.

그래서 segment 는 page 와는 다르게 크기가 달라서, base address 뿐만 아니라 크기(limit)도 segment table 에 저장합니다.

• Register

  • STBR(Segment-table base register) : 물리 메모리에서 segment table 시작 주소를 저장

  • STLR(Segment-table length register) : 프로그램이 사용하는 segment 의 수를 저장

    • 주소 변환시에 segment 의 번호와, STLR 을 비교하여 검증함
      • if (번호 > STLR ) then '잘못된 접근'

  • 장점

    • 공유, 보안 등의 관리가 편하다
      • ex) Stack Segment : read-write
        Code segment : read-only

  • 단점

    • External fragmentation(외부 조각) 이 발생할 수 있음

하지만 가변 크기 때문에 발생할 수 있는 외부 조각 문제로 인해 순수한 segmentation 은 사용되지 않는다고 합니다.
대신, paging 과 혼합하여 사용된다고 합니다.

Segmentation with Paging

Segment 가 여러개의 page로 구성되고, 실제 물리 메모리에는 page 형태로 저장하여 주소 변환시에는 paging 처럼 동작합니다.
그리고 의미있는 단위로 관리하기 위해서 Segment 가 사용됩니다.

• 주소 변환 방식
  • STBR 을 참조하여 segment table 로 이동
  • n 번째 entry 에서 해당 segment 의 page tabe base address 를 얻음
  • 해당 segment 의 page table 로 이동
  • 물리 주소로 변환

참고

• TBL 란?
• 테코톡 리눅스 메모리관리