Paging
- Paging에서의 내부 단편화
- page 크기가 2KB (2048 byte)
- 프로세스 크기는 72,766 bytes
- 35개의 page + 1086 bytes
→ 마지막 page는 962 bytes의 자투리 공간이 남음
- 내부 단편화가 가장 심한 경우 : 마지막 page에서 자투리 공간이 1byte가 남는 경우
- 평균적으로 page 크기 또는 page와 동일한 frame 크기의 1/2 정도의 내부 단편화가 있음
- 내부 단편화를 줄이기 위해 page 크기를 작게 설정하면 page table의 크기가 커짐
→ page table은 부가적인 정보이므로 이것이 커지는 것은 바람직하지 않음 - page 크기는 최신 컴퓨터일수록 크게 설정하는 추세
Free Frames
- paging을 하는 시스템에서 물리 메모리를 관리하는 방법
- kernel은 물리 메모리 상의 빈 frame 목록을 늘 유지하고 있음
Implementation of Page Table
- 메인 메모리 상에 존재하며 프로세스마다 하나씩 있음
- PCB에 해당 프로세스의 page table에 대한 포인터 존재
- Page-table base register (PTBR) : 현재 실행 중인 프로세스의 page table에 대한 포인터 값
- Page-table length register (PTLR) : 현재 실행 중인 프로세스의 page table 크기
- 프로세스 별로 page table의 크기가 다른 시스템에서 사용
- 현재 실행 중인 프로세스가 전환되면 PTBR, PTLR 값도 새로 실행되는 프로세스 것으로 변경됨
- page table 자체가 메모리에 있으므로 CPU가 메모리 상의 데이터나 명령을 접근할 때마다 본 접근 외에 page table을 추가로 접근해서 메모리 접근이 2번 발생함
→ paging을 하면 컴퓨터가 느려짐
Implementation of Page Table (Cont.) - Translation look aside Buffers (TLBs)
- 성능 저하를 최소화하기 위해 paging 시스템에서 사용하는 캐시
- associative memory를 사용해서 만들어짐
- 메모리에 저장된 값을 읽기 위해 주소로 접근하는 것이 아닌 key 값을 사용해서 접근
- 내부적으로 빠르게 key에 해당하는 값을 병렬로 검색
- 현재 접근한 page table entry가 TLB에 없는 내용이라면 추가함
- TLB가 꽉 찬 경우 기존의 entry 중 하나를 교체함
→ 프로세스가 자주 사용하는 entry는 교체 대상에서 제외되어 오랜 시간 TLB에 머무르는 것이 프로그램 실행 성능에 좋음 - (p, d)
- page 번호를 key 값으로 TLB에 제시하여 frame 번호를 얻음
- 보통 page table 전체 entry 중 64~1000개 정도만 TLB에 담을 수 있음
- TLB hit : 검색하는 page 번호 내용이 TLB에 존재
- TLB miss : 검색하는 page 번호 내용이 TLB에 없음
- 시스템마다 TLB는 하나이고 이를 여러 프로세스가 나누어 사용할 때 TLB 항목에 ASID (address-space identifiers)를 추가하기도 함
- 해당 TLB entry가 어느 프로세스 것인지를 나타내는 고유 ID
- ASID를 통해 protection 가능
- TLB가 ASID를 지원하지 않으면 현재 실행 중인 프로세스만 TLB를 독점하는 방식으로 동작
→ 문맥 교환이 일어나면 TLB의 내용도 바뀜 (TLB flush)
→ TLB flush는 컴퓨터 시스템 전체에 매우 나쁜 영향
Paging Hardware With TLB
- paging을 하는 시스템은 무조건 TLB를 사용함
- 전체 구성 요소는 3가지
- CPU : 논리주소를 만듦
- TLB
- page table과 물리 메모리
- page table은 실제 물리 메모리 어딘가에 있음
- CPU가 논리주소를 생성하면 무조건 TLB를 먼저 검색함
Effective Access Time
- 주소 변환에 걸리는 시간 (유효 접근 시간)
- TLB를 사용하는 경우 TLB hit이 매번 발생하는 것이 아니므로 메모리 접근 시간이 늘 일정하지 않음
→ hit ratio를 가정하고 전체 접근 시간을 유효 접근 시간으로 표현
- ε : TLB에 접근하는데 걸리는 시간
- 실제 컴퓨터에서는 TLB에 접근하는데 걸리는 시간이 메인 메모리 접근 시간의 10%도 안됨
- 전체 시간에 미치는 영향이 작으므로 생략 가능
- α : 전체 메모리 접근 횟수 중 TLB hit이 발생한 횟수의 비율
- (1+ε)α : (TLB hit 시의 전체 접근 시간(1) + TLB 접근 시간(ε)) * TLB hit 비율(α)
- (2+ε)(1-α) : (TLB miss 시의 전체 접근 시간(2) + TLB 접근 시간(ε)) * TLB miss 비율(α)
- α 값이 0에 가까우면 기존 메모리 접근 시간보다 2배에 가까운 시간이 걸리지만, 1에 가까우면 paging의 장점을 누리면서도 접근 시간이 얼마 늘어나지 않게 됨
Memory Protection
- 각 page frame마다 이 page frame에 올라와있는 page에 대해서 읽기, 쓰기, 실행 중 어느 것이 가능한지 표시하는 protection bit가 있음
- page table entry마다 valid bit을 가짐
- valid 하다 (1) : 해당 page가 프로세스의 주소 공간에 속하는 정당한 page이다
- valid bit를 사용할 수도 있고 PTLR을 사용할 수도 있음
- protection bit이나 valid bit의 정의에 어긋나는 메모리 접근이 있는 경우 trap(software interrupt)이 발생
- 보통 해당 프로세스는 강제 종료시킴
Shared Pages
- paging을 하게 되면 프로세스들 간의 메모리 공유도 page 단위로 함
- Shared code
- 프로그램의 코드처럼 읽기 전용인 부분들은 여러 프로세스들이 공유할 가능성이 높아짐
- 코드 부분에 해당하는 page는 메모리에 하나만 두고 page table 수준에서 한 copy 밖에 없는 page를 공유하는 형식으로 사용
- 여러 프로세스가 한 코드를 공유하거나 한 프로세스 내에서 thread가 여러 개일 경우 thread 간의 주소 공간을 page 단위로 공유하거나, 혹은 IPC를 통해서 특정 page를 다른 프로세스와 공유할 수도 있음
- Private code and data
- 각각의 데이터 page 같은 것들은 별도의 page를 가져야 함
Structure of the Page Table
- paging을 그대로 구현하는 경우 page table이 너무 커지는 문제가 생길 수 있음
- 32 bit 주소를 사용하는 CPU에서 4KB 크기의 page를 사용
- 전체 주소 공간 2^32를 page 크기 2^12로 나누면 최대 page의 개수는 2^20이므로 page table entry 개수도 2^20개
- page table entry 하나당 4byte라고 가정하면 전체 page table 크기는 4byte * 2^20(1MB) = 4MB
- 배열 형태의 page table을 그대로 사용하면 공간 면에서 문제가 있으므로 다양한 구조의 page table을 사용
- Hierarchical Paging
- Hashed Page Tables
- Inverted Page Tables
Hierarchical Paging
- 가장 기본적인 2단계 page table
- page table을 또 다시 page 단위로 쪼개서 paging을 하는 방법으로, 쪼갠 page table 중 일부만 메모리에 올라가게 함
- outer page table entry 하나가 특정한 inner page table page 한 조각을 가리키게 구성
Two-Level Paging Example
- forward-mapped page table이라고도 함
- 32 bit 주소를 가지고 page 하나의 크기가 1KB(2^10)인 시스템을 가정
- offset을 표현하는 것은 10bit, 나머지 22bit는 page 번호를 표시하는데 사용
- page 번호를 나타내는 22bit가 다시 12bit의 page 번호와 10bit의 page offset으로 나눠짐
- 맨 아래 고정된 10bit는 page 하나의 크기에서 옴 (1KB = 2^10)
- 주소 변환을 할 때 p1 부분에 해당하는 12bit 값은 outer page table에 대한 index로 사용하고 p2는 inner page table에서 index로 사용
Address-Translation Scheme
- (p1, p2, d)
- 논리주소에서 offset d에 해당하는 부분은 page 크기로 결정
- page 크기가 2^n인 경우 n bit는 d가 차지하는 비트 수
- p1은 outer page table의 index
- p2는 inner page table의 index
- 논리주소에서 offset d에 해당하는 부분은 page 크기로 결정
- outer page table에서 p1번째 entry를 찾으면 inner page table의 시작 주소가 있음
- innter page table에서 p2번째 entry를 찾으면 최종 frame의 시작 주소가 있음
64-bit Logical Address Space
- 64 bit 주소 공간의 경우 논리 주소 공간이 넓으므로 2단계 page table로도 사실 부족함
- 4KB 크기의 page를 사용한다고 가정
- page table은 2^(64-12) = 2^52개의 entry를 가지게 됨
- inner table은 2^10개의 4byte 크기의 entry를 가지게 됨
- 논리주소 42 bit는 다시 10 bit와 32 bit로 나눠짐
→ 2번째 outer page table을 사용하는 것
→ page table이 3단계가 되면서 메모리 접근 시 총 4번의 메모리 접근이 요구됨
Three-level Paging Scheme
Hashed Page Tables
- hasing 기법을 page table 구조에 적용
- 주로 주소 공간이 32 bit보다 큰 경우에 사용
- page 번호 p를 hash 함수에 적용해서 만들어진 hash 값을 갖고 page table에 접근
- 각 page table entry마다 여러 개의 frame들이 chain 형태로 연결되어 있음
- chain을 다시 한 번 선형 탐색해서 최종적인 물리 frame 번호를 알 수 있음
→ 일반적인 형태의 page table보다 검색 시간이 많이 걸림
- chain을 다시 한 번 선형 탐색해서 최종적인 물리 frame 번호를 알 수 있음
- page table 크기를 줄이는데 효과 있음
- clustered page table
- hashed page table의 변형 중 하나로 64 bit 시스템에서 주로 사용
- page table의 각 항목 entry가 여러 개의 page를 가리키게 함으로써 여러 page frame에 대한 변환 정보를 지니게 함
- 특히 sparse한 주소 공간(전체 주소 공간은 넓은데 프로세스가 듬성듬성 사용하는 경우)을 사용하는 프로세스가 많은 경우 유용함
Inverted Page Tables
- 시스템 전체에 page table이 하나만 있고 여러 프로세스들이 공유해서 사용
- 물리 메모리의 frame당 page table entry가 하나씩 있음
- 앞의 page table들은 프로세스의 논리 page당 entry가 하나씩 있었음
- page table에서 i번째 항목은 물리 frame i번에 대한 정보
- 어느 프로세스가 사용하는 frame인지와 그 프로세스의 몇 번 page 번호인지에 대한 정보가 있음
- 논리주소가 물리주소로 변환되는 과정도 달라짐
- 논리주소마다 프로세스를 나타내는 pid가 있어야 함
- 전체 page table을 검색해서 내가 찾는 pid와 p 값의 쌍이 i번째 entry에 있다면 frame 값을 알게 되는 것
- page table 상의 위치가 frame 번호가 됨
- 이 검색 과정은 프로세스 동작의 성능을 떨어뜨림
- 프로세스 간의 page 공유가 어려워짐
참고 자료 : Operating System Concepts Essentials
*이미지 자료는 교재 자료를 직접 다시 만든 것으로 무단 불펌 금지입니다
끗!!
