Paging
Noncontiguous allocation
프로세스의 가상 메모리를 동일한 사이즈(page)로 나누어 저장하는 방식
특징
- 가상 메모리의 내용이
page단위로 불연속하게 저장 - 물리 메모리는
page가 들어올frame으로 나눔 (= page와 같은 크기) page중 일부는 물리 메모리에, 일부는backing storage에 저장- 논리 주소를 물리 주소로 변환된 결과를 page table을 사용해 관리
- 외부 조각은 발생하지 않지만 내부 조각은 가능성 있음 (page 단위로 나누면 마지막 크기는 작을 수도 있음)
- 외부 조각: 크기가 너무 작아서 넣을 수 없는 공간
- 내부 조각: 프로그램을 넣었는데 남는 공간
Page Table
- 페이지 테이블은 (물리) 메인 메모리에 저장
- 페이지 테이블은 프로세스 별로 존재
- 테이블 엔트리 수는 논리 메모리의 페이지 개수 만큼
Page Table을 위한 레지스터
- Page table base register(PTBR): 메모리에 있는 페이지 테이블의 시작 위치
- Page table length register(PTLR): 페이지 테이블의 길이
주소 변경 방법
p번 페이지 ➡️ f번 프레임
- p(page number)
- d(page offset)
CPU가 특정 page의 논리 주소를 읽음
| p | d |
---> page 번호 -> 페이지 테이블에서 p번째를 확인
---> 할당된 물리 주소(frame 번호)를 확인
---> frame에서 d 번째
page table 접근+코드 접근= 두 번의 메모리 접근이 필요
--> 속도 향상을 위해 별도의 하드웨어를 사용
associative register 또는 translation look-aside buffer(TLB)
translation look-aside buffer(TLB)
- 페이지 테이블의 일부를 담고 있는 캐시 메모리
- 페이지 번호와 프레임 번호 쌍을 가짐
- TLB에 있는지 쭉 읽어가며 확인을 해야하므로 보통 병렬 탐색이 가능한 associative register를 함께 사용
- 일부만 담고 있으므로 TLB에 없다면 페이지 테이블을 사용해야 함
- 프로세스 별로 페이지 테이블이 달라 TLB 역시 다르므로 문맥 교환이 발생하면 TLB를 flush 해야 함
메모리 접근 시간
- TLB 접근 시간 = a (a < 1)
- 메인 메모리 접근 시간 = 1
- TLB에서 원하는 주소를 찾는 비율(Hit ratio) = b
(1 + a)b + (2 + a)(1 - b) = 2 + a - b
➡️ 보통 Hit ratio가 1에 가까운 비율이라 무조건 페이지 테이블에 접근하는 2보단 작음
페이지 테이블 엔트리
1) Valid - Invalid Bit
- 모든 page가 frame으로 mapping 되진 않음
- 페이지 테이블에는 물리 주소 외에도
valid-invalid bit엔트리가 존재 - 지금 프로그램이 사용하지 않는 페이지라도 페이지 테이블은 모든 페이지에 대한 엔트리를 가져야하기 때문에 사용되지 않는 페이지는
invalid로 표시
valid: 해당 주소의 frame에 프로세스를 구성하는 유효한 내용이 있음
invalid: 해당 주소의 frame에 유효한 값이 없음
- 프로세스가 해당 주소를 사용하지 않을 경우
- 해당 페이지가 메모리에 올라와 있지 않고 swap out된 경우
2) Protect bit
- page에 대한 접근 권한 ➡️ read / write / read-only
대용량 페이지 테이블
1) 2단계 페이지 테이블
CPU가 논리 주소를 주면 두 단계의 페이지 테이블을 거쳐서 메모리에 접근하는 방식
outer page table+page table- page table의 공간이 줄어든다는 장점
- 현대 컴퓨터는 큰 단위의 주소체계를 가짐 = address space가 큼
- 프로그램은 4G의 주소 공간 중 극히 일부만 사용하는데 모든 페이지 테이블을 메모리에 저장하면 낭비
p1(첫 번째 번호) | p2(두 번째 번호) | d(page offset)-> | 10 | 10 | 12 |- 첫 번째 페이지 테이블의 엔트리 별로 두 번째 페이지 테이블이 존재
- 프로그램에서 사용되는 페이지는 극히 일부 -> outer page table에서 사용되지 않는 엔트리는 null
= 두 번째 페이지 테이블 중 상당수는 만들지 않아도 됨
2) 다단계 페이지 테이블
- 2단계를 넘어 여러 단계로도 구성 가능
- 테이블을 위한 주소 공간을 줄일 수 있지만 주소 변환 시 더 많은 메모리 접근이 필요
-> 접근 시간이 오래 걸릴 수 있음 - 하지만 보통 TLB에서 해결 되므로 시간이 오래 소요되는 영향이 크지 않음
3) Inverted Page Table
page가 아니라 frame을 기준으로 주소 변환을 하는 방법
p -> f ➡️ f -> p
- 각 프로세스 별로 페이지 테이블이 존재 -> 페이지 테이블이 많은 용량을 차지하는 문제
- 페이지 테이블을 이용한 주소 변환을 역으로 뒤집음
- 물리 주소를 보고 논리 주소를 알 수 있는 페이지 테이블
- 페이지 frame의 f번 째 엔트리에 가면 논리적인 번호(p)가 나오도록
- Inverted Page Table은 시스템에 단 하나만 존재
- 페이지 테이블에 어떤 프로세스의
p인지 프로세스 아이디(pid)도 같이 저장해야 함
- 논리 주소만 알고 있을 때 페이지 테이블은 순차적으로 확인해 주소
p를 찾음 -> p가 위치한 엔트리 번호가 곧 f (프레임 엔트리) - 페이지 테이블의 공간은 줄일 수 있지만 시간 상의 성능 저하가 있음
- 병렬 탐색을 위해 associate register를 같이 사용해 시간 오버헤드를 줄임
Shared Page
- 여러 프로세스에서 같은 코드를 사용할 때는 페이지를 공유할 수 있음 ex) text editor
- Shared Code(Re-entrant Code, Pure Code)
- read-only로 하나의 code만 메모리에 올림
- 동일한 logical address를 가져야 함
Page Size 결정
- 보통 4KB ➡️ 메모리 주소 체계가 32bits에서 64bits로 변화
- 최근에는 보다 큰 page size 사용하는 메모리 시스템도 나오고 있음
page size 작으면
- 페이지 수 증가
- 페이지 테이블 크기 증가
- 외부 조각 감소
- 디스크 transfer 효율성 감소
- 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
- Locality 측면에서는 좋지 않음
iOS Developer