페이징
한 프로세스의 논리 주소 공간을 연속적인 하나의 긴 메모리가 아닌, 메모리를 여러개의 포스트잇과 같이 작은 동떨어진 공간들에 배정할수 있도록 하는 방법이다. 이를 통해 외부단편화를 해결할 수 있다.
모든 논리 주소는 페이징 하드웨어에 의해서 물리주소로 매핑된다.
Frame : 물리메모리를 고정된 크기로 분할한 것.
Page : 논리주소를 물리메모리 처럼 분할한 것
논리주소를 물리주소로 변환하기 위해서 페이지 테이블을 이용하게 된다.
페이징 특징
- 구현이 고정크기로 분할하기 때문에 쉽다.
- Cpu에 의존하는게 없다. 이식성이 높다.
- 시스템에 따라 page크기를 다르게 설정도 가능하다. 융통성이 높다.
- 시간 오버헤드 적에서 우수하다. 외부단편화가 생기지 않고, 홀 선택 알고리즘을 실행할 필요가 없다.
- 페이징 또한, 내부 단편화가 생길수 있다. 메모리는 항상 frame에 정수배로 할당되기 때문에 (프레임이 고정으로 나눠지기 때문에 메모리또한 그러하다. ) 이러한 내부 단편화를 줄이기 위해서는 페이지 크기를 줄여야 한다. 하지만 이러한 경우 페이지 테이블이 커진다.
페이지 크기와 페이지 테이블의 데이터량에 대한 계산 문제
1byte = 8bit
1kb = 2^10 byte
1mb = 2^20 byte
1gb = 2^30 byte
32비트 cpu의 메모리 크기는 = 2^32 = 4gb,
64비트 cpu의 메모리 크기는 = 2^64 = 18gb
물리 메모리의 최대 크기는 cpu비트에 정해지고 32비트라면 4gb
페이지 크기가 4kb로 한다면 물리메모리/페이지크기 = 페이지 수
2^32/2^12 = 2^20 = 약 100만개
테이블의 크기는 하나의 번호를 저장해야 하니까 필요한 byte는 4byte이다. 0000 이기때문.
그렇기 때문에 페이지수 * 1개당 필요한 크기(4byte) = 2^20* 4= 2^22=4mb
페이지 테이블
페이지 테이블 저장 위치는 어디에 저장이 되어있을까?
페이지 테이블은 PTBR(page table base register) 이 가르키는 메인 메모리에 저장되어 있다.
혹은 페이지 테이블 사이즈 레지스터 (page table length register PTLR)에 저장되는데 이것의 단점은 두번이나 메모리에 접근해야한다는 점이다.
논리주소를 통해서 페이지테이블에 접근하고, 페이지테이블을 통해서 다시 한번 물리주소로 접근해야한다.
이를 해결하기 위해서 TBL이 생긴것이다.
페이징 시스템에서 논리주소는 다음과 같이 나눠진다.
- 페이지 번호(p) : 페이지 테이블에 인덱스 번호
- 페이지 offset(d) : 특정 페이지 내에서의 offset으로 생각한다.
페이지 내부의 번호, 우리가 지금 읽어야 하는 줄의 번호를 의미한다.
32비트 cpu라고 하면 32비트의 주소값을 가진다는것이고 총 주소 수는 2^32가된다, 페이지 크기가 4kb이면 2^12이니까 페이지 넘버는 총 2^20개가 되는것이고, 그렇다면 주소 번호는 앞에 페이지 넘버링 2^20과 오프셋 2^12가 되는것이다.
TLB
이러한 방법은 효율적이지만, 매우 비효율적이다. (즉 한번은 페이지테이블 접근 한번은 오프셋 접근)
이를 보완하기 위해서 TLB라는 캐시 메모리를 이용한다.
TLB (translation look aside buffer) : 이전에 한번 접근했던 메모리라면 그 값을 TLB에 저장을 하고, 물리적인 메모리 번호에 접근하는것이 아닌 그냥 바로 프레임 번호를 가져올수 있다. 또한 TLB는 한번에 여러 물리주소를 동시에 확인하는 고도의 버퍼다
이러한 검색 타임은 아래와 같은 공식이 적용되는데
TLB의 hit ration 이 관련된다.
페이지 번호가 TLB에 있으면 프레임 번호를 바로 알려주고
없으면 메모리에 있는 페이지 테이블 번호를 가져와 TLB에 추가하고 교체 해준다. \
TLB를 쓰는 방법은 참조의 지역성으로 인해 효과적인 전략이다.
순차 접근시 실행 속도가 매우 빠르다.
하지만 TLB를 사용하는 경우 임의접근이나 반복이 없는 경우에는 느리게 된다.
TLB의 성능을 향상시키기 위해서는
- 히트율을 높이기 위해서 TLB항목수를 늘린다.
- Page가 크면 된다. 하지만 내부 단편화가 늘어난다.
- TLB도달범위(TLB reach) : 모든항목이 체워졌을때 miss없이 접근할수 있는 메모리 접근 범위를 의미한다.
TLB항목수 * page크기
향상된 페이징 방법들
페이징은 효율적이지만, 페이지테이블을 만들어야하는 불편함이 생긴다.
바로 페이지 테이블을 이용하지 않을때도 페이지 테이블을 생성해야하고, 페이지 테이블생성을 위한 메모리가 낭비된다. 이를 해결하기 위해서 아래와 같은 방법을 사용하게 된다.
페이지 테이블 메모리 낭비 해결방법
- 역 페이지 테이블
- 멀티 레벨 페이지 테이블
역페이지 테이블 (inverted Page table, IPT)
원래 페이징의 경우에는 논리주소를 물리적메모리에 대응하는데,
역페이지 테이블에서는 물리메모리를 N개의 프레임으로 나누게 되고, 그렇게 n개의 프레임으로 나눈것을 페이지 테이블로 대응하게 하여, 원래는 페이지 수만큼 존재하던 페이지 테이블이, 프레임 개수만큼 생기게 된다. 그렇게 해서 0번의 프레임테이블(그냥 내가 만든말임) 에서는 0번의 프레임을 가르키게 된다.
여기에서 pid와 page를 가진, 프레임테이블에서 대응하여 물리주소를 가지게 된다.
원래의 페이지 테이블은 이러한 페이지와 프레임 대응 맵을 가지고 있지만.
역 페이지 테이블은 pid와 페이지가 대응되어서, 페이지 순서에 맞춘 테이블에 존재하게 된다.
동일한 순서를 가지고 있기 때문에 다음과 같은 방법이 가능해지는것이다.
그래서 Pid와 페이지를 매칭해서 동일하게 되면 프레임 주소를 알수 잇게 되는것이다.
장점은 실행 프로세스당 페이지테이블이 생성된다.
시스템에 하나의 페이지가 존재하기 때문임.
하지만 특정 페이지 프레임을 검색하기 위해서 운이 안좋으면 전체를 검색해야 하기 때문에 문제가 발생한다.
그래서 이를 해결하기 위해서 TLB와 같은 것을 사용하는 것으로 줄일수 있다.
멀티 레벨 페이지 테이블(two level page table, multi level page table.)
페이지 테이블을 다시 페이지 해주는 방법으로, 현재 프로세스가 사용하고 있는 페이지에만 대응해서 페이지테이블을 형성하기 때문에, 낭비가 없다.
논리주소를
페이지 디렉터리 인덱스
페이지 테이블 인덱스
오프셋
페이지 디렉터리 인덱스를 통해서 현재 실행중인 프로세스 개수만큼만 페이지 개수를 나누고, 거기에서 페이지 테이블로 접근해 해당 페이지 테이블이 프레임을 알려주는것으로 물리주소를 가지고 오게 된다.
Uploaded by N2T
