페이징(Paging)
Paging
- Process의 virtual memory를 동일한 사이즈의 page단위로 나눔
- Virtual memory의 내용이 page 단위로 noncontiguous하게 저장됨
- 일부는 backing storage에, 일부는 physical memory에 저장
Basic Method
- physical memory를 동일한 크기의 frame으로 나눔
- logical memory를 동일 크기의 page로 나눔(frame과 같은 크기)
- 모든 가용 frame들을 관리
- page table을 사용하여 logical address를 physical address로 변환
- External fragmentation 발생 안함
- Internal fragmentation 발생 가능
물리적인 공간에 페이지를 넣기 위해
page table이라는 것을 사용!
주소 변환 아키텍처
페이지 테이블 구현
- 페이지 테이블은 main memory에 상주
Page-table base register (PTBR)가 page table을 가리킴Page-table length register (PTLR)가 테이블 크기를 보관- 모든 메모리 접근 연산에는 2번의 memory access 필요
- page table 접근 1번, 실제 data/instruction 접근 2번
- 속도 향상을 위해
associative register혹은transition look-aside buffer (TLB)라 불리는 고속의 lookup hardware cache 사용
기존에 페이지 테이블을 접근하려면 CPU가 메인 메모리에 접근해야하는데 이 과정의 속도를 높이기 위해서 TLB라는 캐시를 사용해서 주소변환을 함
이곳에 없으면 page table로 가서 확인함
Associative register
Associative registers(TLB): parallel search가 가능
- TLB에는 page table 중 일부만 존재
page table은 일반적인 인덱싱으로 검색이 가능함
Address translation
- page table 중 일부가
associative register에 보관되어 있음 - 만약 해당 page #가
associative register에 있는 경우 곧바로 frame #를 얻음 - 그렇지 않은 경우 main memory에 있는 page table로부터 frame #를 얻음
- TLB는 context switch 때 flush (remove old entries)
Effective Access Time
Two-Level Page Table(2단계 페이지 테이블)
목적: 페이지 테이블의 공간을 줄이기 위해 사용
그러나 사실 공간적으로 outer-page table이 생기기 때문에 손해이지만 사용되지 않은 주소 공간에 대한 포인터 값이 null로 설정되기 때문에 page table의 공간을 줄일 수 있음
현대의 컴퓨터는 address space가 매우 큰 프로그램 지원
- 32bit address 사용시:
2^10 = K, 2^20 = M, 2^30 = G(4G)의 주소 공간- page size가 4K시 1M개의 page table entry 필요
- 각 page entry가 4B시 프로세스당 4M의 page table필요
- 그러나 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비됨
→ page table 자체를 page로 구성
→ 사용되지 않는 주소 공간에 대한 outer page table의 엔트리 값은 NULL (대응하는 inner page table이 없음)
Multilevel Paging and Performance
- Address space가 더 커지면 다단계 페이지 테이블 필요
- 각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 physical address 변환에 더 많은 메모리 접근 필요
- TLB를 통해 메모리 접근 시간을 줄일 수 있음
- 4단계 페이지 테이블을 사용하는 경우
- 메모리 접근 시간이 100ns, TLB 접근 시간이 20ns이고
- TLB hit ration가 98%인 경우
effective memory access time =0.98 x 120 + 0.02 x 520 = 128 nanoseconds.
결과적으로 주소변환을 위해 28ns만 소요
Memory Protection
Page table의 각 entry 마다 아래의 bit를 둔다.
-
Protection bit
- page에 대한 접근 권한 (read/write/read-only)
-
Valid-invalid bit
valid는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함(접근 허용)invalid는 해당 주소의 frame에 유효한 내용이 없음을 뜻함(접근 불허)
유효한 내용이 없다는 것은 프로세스가 그 주소 부분을 사용하지 않는 경우와 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우를 말한다.
Inverted Page table
page table이 매우 큰 이유
- 모든 process 별로 그 logical address에 대응하는 모든 page에 대해 page table entry가 존재
- 대응하는 page가 메모리에 있든 아니든 간에 page table에는 entry로 존재
Inverted page table
- Page frame 하나당 page table에 하나의 entry를 둔 것(system-wide)
- 각 page table entry는 각각의 물리적 메모리의 page frame이 담고 있는 내용 표시(process-id, process의 logical address)
- 단점
- 테이블 전체를 탐색해야 함
- 조치
- associative register 사용(expensive)
Inverted Page Table Architecture
physical memory의 frame 개수 만큼 page table의 entry가 존재하며, page table은 1개만 존재
Shared Page
Shared Code
- Re-entrant Code(=Pure code)
- read-only로 하여 프로세스 간에 하나의 code만 메모리에 올림
(eg, text editors, compilers, window systems). - Shared code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 함
Private code and data
- 각 프로세스들은 독자적으로 메모리에 올림
- Private data는 logical address space의 아무 곳에 와도 무방
Segmentation
프로그램은 의미 단위인 여러 개의 segment로 구성
- 작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의
- 크게는 프로그램 전체를 하나의 세그먼트로 정의 가능
- 일반적으로 code, data, stack 부분이 하나씩의 세그먼트로 정의됨
Segment는 다음과 같은 logical unit들임
- main(),
- function
- global variables,
- stack
- symbol table, arrays
Segmentation Architecture
Logical address는 다음의 두 가지로 구성
< segment-number, offset >Segment table
- each table entry has
- base - starting physical address of the segment
- limit - length of the segment
Segment-table base register(STBR)
- 물리적 메모리에서의 segment table의 위치
Segment-table length register(STLR)
- 프로그램이 사용하는 segment의 수
segment number s is legal if s < STLR.
세그먼트가 어디서 시작이 되는지 바이트 단위 주소로 정해준다는면에서 페이징 기법과 차이가 있음
Protection
- 각 세그먼트 별로 protection bit가 있음
- Each entry:
- Valid bit = 0 => illegal segment
- Read/Write/Execution 권한 bit
Sharing
- shared segment
- save segment number
segment는 의미 단위이기 때문에 공유(sharing)와 보안(protection)에 있어 paging보다 훨씬 효과적이다.
Allocation
- first fit / best fit
- external fragmentation 발생
segment의 길이가 동일하지 않으므로 가변분할 방식에서와 동일한 문제점들이 발생
세그멘테이션 예시
페이징 기법에 비해 테이블에 의한 메모리 낭비가 훨씬 적다. (소수의 몇개만 들어가기 때문에)
세그먼트 공유
code에 대한 데이터를 공유하고
private segment는 따로 분류하여 물리 메모리에 올려둠
Segmentation with Paging
pure segmentation과의 차이점
- segment-table entry가 segment의 base address를 가지고 있는 것이아니라 segment를 구성하는 page table의 base address를 가지고 있음
기존 segmentation에서 발생하는
allocation문제가 발생하지 않음
- 세그먼트당 페이지테이블이 존재함
- 세그먼트 오프셋을 또 쪼개어서 페이지 번호, 오프셋으로 나누어서 사용함
참고사이트
