Memory - Paging

이유석·2022년 3월 11일

CS Operating System tech-interview

CS - Operating System

목록 보기

13/20

NonContiguous allocation
하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음
기법 : Paging, Segmentation

Paging

정의

프로세스의 virtual 메모리를 동일한 사이즈의 page로 나누어 physical 메모리에 불연속적으로 배치(저장)합니다.

용어

Frames : physical memory는 동일한 크기의 블록들로 나누어 집니다. 이때 해당 블록들을 의미합니다.
Pages : logical memory는 동일한 크기의 블록들로 나누어 집니다. 이때 해당 블록들을 의미합니다.
Page table : logical memory에서 physical memory로 쉽게 변환하기 위해 유지됩니다.
Backing store : physical memory에 저장되지 못한 블럭들이 저장됩니다.

특징

physical memory의 block들의 크기가 동일하므로, External Fragmentation이 발생하지 않습니다.
여전히, Internal Fragmentation은 발생 가능합니다.

Address 변환 구조

CPU에 의해서 생성된 주소는 2부분으로 나뉩니다.

p (Page number) : Physical memory에서의 해당 page의 Base Address(시작 지점)를 가리킵니다.
d (Page offset) : Base Address와 합쳐져서, physical memory 주소를 정의합니다.

Page Table 구현

Page Table 은 물리 메모리에 유지됩니다. 그리고 주소 매핑/ 데이터 접근 시 항상 2가지의 register에 대한 접근이 필요합니다.

Page-table base register (PTBR) : relocation register 역할을 하며, page table을 가리킴
Page-table length register (PTLR) : limit register 역할을 하명, page table 크기를 가리킴

Page Table에 의해 Logical Address를 Physical Address로 매핑을 하면, 실제 물리 메모리의 주소에 접근하여 연산을 합니다.
이런 경우, 2번의 물리 메모리 접근이 필요합니다.

실제 데이터 연산을 위한 Page Table 접근
물리 메모리의 실제 data/instruction 접근

2번의 물리 메모리 접근으로 인한 속도 저하 문제는 특별한 fast-lookup hardware cache를 사용하여 해결 가능합니다.

TLB (Translation look-aside buffers)

속도 향상을 위해, CPU와 물리 메모리 사이에 cache를 두어 Page Table에서 자주 참조되는 Page를 caching 합니다.

동작 방법

Logical Address를 Physical Address로 변환하기 전에 TLB를 확인 합니다.
P에 해당하는 Page Number가 TLB에 caching되어 있는지 확인합니다.
2-1. caching이 되어있으면(TLB hit) , 바로 주소 변환을 하여 물리 메모리에 접근합니다.
2-2. caching이 되어있지 않다면(TLB miss) , Page Table을 사용하여 주소변환 후, 물리 메모리에 접근합니다.

Associative Memory

TLB에서 caching되어 있는 정보를 확인하기 위해, 전체 리스트를 검색해야 하는 overhead가 발생 합니다.

이런 문제를 해결하기 위해, TLB는 Associative Memory를 사용하여 병렬 검색을 수행합니다.
즉, Page Number에 대한 검색의 시간복잡도는 O(1)입니다.

Memory Protection

Protection Bit

Page의 연산에 대한 접근 권한 (read/write/read-only)
code의 경우는 read-only이지만 data,stack은 연산이 가능하므로 read/write 권한을 부여

Valid or Invalid Bit in a Page Table

Page Table내에는 해당 페이지가 물리 메모리(프레임)에 올라가 있는지를 확인할 수 있는 Valid/Invalid bit가 존재합니다.

Valid (V) : 해당 주소의 Frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함
Invalid (I) : 해당 주소의 Frame에 유효한 내용이 없음을 뜻함
- 프로세스가 그 주소 부분을 사용하지 않는 경우
- 해당 페이지가 메모리에 올라와 있지 않는 경우

Shared Pages

정의

Page의 장점은 공통의 코드를 공유할 수 있다.

우리가 표준 C 라이브러리 libc가 필요하다고 하자.
페이지를 공유하지 않는 경우 시스템에 3개의 프로세스가 libc 라이브러리가 필요하다면 가각 2MB씩 6MB가 physical 메모리에 올라갈 필요가 있다.

만약, 해당 코드(libc)가 read-only(reentrant) code 라면 위 사진과 같이 공유할 수 있다.

reentrant code : 물리 메모리에 해당 코드가 올라가면, 자체 수정을 할 수 없는 코드이므로 실행 중 변경되지 않음을 보장한다.

Page Table 구조

32-bit Logical address space가 있다고 가정하자. 이때, Page 1개의 size는 4KB(212)이다.
Page Table은 1M(million)의 page를 갖게 될 것이다. (232 / 212)
만약 각 page를 위해 4bytes가 필요하다면, 전체 page table을 위해 4MB(4KB X 1M)가 필요하다.

Page Table의 크기가 너무 거대해 지는 상황을 위한 해결책

Hierarchical Paging
Hashed Page Tables
Inverted Page Tables

Hierarchical Paging

정의

Logical Address Space를 여러개의 Page Table들로 쪼갠다.
2단계 Page Table과 유사한 기법이다.

2단계 Page Table

4K 페이지 크기인 32 bit 명령어 기계가 있고, 각 페이지 entry 크기가 4 byte라 가정하겠습니다.
그렇다면 하나의 페이지의 크기가 4K이므로 212이며 명령어에서 offset은 12 bit로 표현이 가능합니다.
즉, 명령어 32 bit 중 12 bit는 offset을 표현하는데 사용이 됩니다.

그럼 20 bit가 남게 되는데, 만약 온전히 20 bit로만 테이블을 접근하게 된다면 각 페이지의 entry 크기가 4 byte이므로 22 X 220 = 222로 Page Table의 크기가 굉장히 커지게 됩니다.
이러한 큰 크기를 메모리에 연속으로 할당하는 것은 역시 부담일 수 있기 때문에, 20 bit를 다시 각각 10 bit로 나누어, 즉 두 계층의 테이블 구조를 사용하게 됩니다.

Hashed Page Tables

Hashed Page Tables 구조는 32 bit 이상의 명령어 기계에서 주로 사용하는 구조 입니다.

명령어 비트 중 Page 테이블의 인덱스의 해당하는 p를 hash function의 입력값으로 넣어 나온 결과값으로 hash table을 검사합니다.
그후, 검사한 결괏값으로 해당하는 Physical Memory를 찾아가게 됩니다.
같은 hash 결괏값에 대해서는 리스트를 이용하여 하나의 hash table위치에 연결해 놓습니다.

Inverted Page Table (역전 구조)

정의

Inverted Page Table은 말 그대로 역전 구조 테이블 입니다.

이전의 테이블들은 모두 Logical Address를 기준의 테이블 이었습니다.
프로세스 당 하나의 테이블을 갖고 있었으며, 나누어진 페이지의 순서대로 Page Table에 순서대로 대응되는 구조였습니다.
역전 구조는 Physical Address의 입장에서 만들어진 테이블 구조 입니다.