불연속할당 기법(Noncontiguous allocation)
불연속할당 기법은 하나의 프로세스가 물리적 메모리의 여러 위치에 분산되어 올라갈 수 있는 메모리 할당 기법을 말한다.
페이징 기법
페이징은 프로세스의 주소 공간을 동일한 크기의 페이지 단위로 나누어 물리적 메모리의 서로 다른 위치에 페이지들을 저장하는 방식을 말한다.
물리적 메모리를 페이지와 동일한 크기의 프레임으로 미리 나누어둔다. 왜냐하면 메모리에 올리는 단위가 동일한 크기의 페이지 단위이므로 메모리를 같은 크기로 미리 분할해두더라도 빈 프레임이 있다면 어떤 위치이든 사용될 수 있기 때문이다. 따라서 페이징 기법에서 동적 메모리 할당 문제가 발생하지 않는다.
페이징 기법은 외부 단편화 문제는 발생하지 않지만 내부 단편화 문제는 발생한다.
- 프로세스의 주소 공간과 물리적 메모리가 모두 같은 단위인 페이지로 나눠지므로 빈 공간은 어느 곳이든 활용 가능하므로 외부 단편화 문제는 발생하지 않음
- 프로그램의 크기가 항상 페이지 크기의 배수가 되지 않으므로 프로세스의 주소 공간 중 제일 마지막에 위치한 페이지에서는 내부 단편화 문제가 발생할 수 있음
페이징 기법의 주소 변환
물리적 메모리에 올리는 위치가 각각 다르므로 논리적 주소를 물리적 주소로 변환하는 작업이 페이지 단위로 이루어져야 한다. 즉, 특정 프로세스의 몇 번째 페이지가 물리적 메모리의 몇 번째 프레임에 들어 있다는 페이지별 주소 변환 정보를 유지하고 있어야 한다.
페이징 기법에서는 모든 프로세스가 각각의 주소 변환을 위한 페이지 테이블(page table)을 가지며 이 테이블은 프로세스가 가질 수 있는 페이지 개수만큼 주소 변환 엔트리를 가지고 있게 된다.
주소 변환 기법
논리적 주소는 페이지 번호(p)와 페이지 오프셋(d)로 나누어 주소 변환에 사용된다.
- 페이지 번호는 페이지 테이블 접근 인덱스로 사용되고 해당 인덱스의 entry에는 그 페이지의 물리적 메모리상의 기준 주소(시작 위치)가 저장된다.
- 페이지 오프셋: 하나의 페이지 내에서 변위(displacement)를 알려준다. 기준 주소값에 변위를 더해 요청된 논리적 주소에 대응하는 물리적 주소를 얻을 수 있다.
물리적 주소는 프레임 번호(f)와 프레임 오프셋(d)로 나눠져 있다.
페이지 테이블의 구현
페이지 테이블은 페이징 기법에서 주소 변환을 하기 위한 자료구조로 물리적 메모리에 위치해 있다.
- 페이지 테이블 기준 레지스터(PTBR): 메모리 내에서의 페이지 테이블의 시작 위치를 가리킴
- 페이지 테이블 길이 레지스터(PTLR): 페이지 테이블의 크기를 보관
메모리에 한 번 접근하기 위해서 매번 메모리에 두 번 접근해야되므로 오버헤드가 생기게 된다.
- 페이지 테이블 접근, 실제 데이터에 접근
따라서 오버헤드를 줄이고 메모리의 접근 속도를 향상시키기 위해 TLB(Translation Look-aside Buffer)라고 불리는 고속의 주소 변환용 하드웨어 캐시가 사용된다.
TLB에는 모든 정보를 담을 수 없어서 자주 참조되는 페이지에 대한 주소 변환 정보만 담는다. 따라서 요청되는 페이지에 대한 주소 변환 정보가 TLB에 있을 수도 있고 없을 수도 있다. 따라서 TLB에는 페이지 번호와 이에 대응하는 프레임 번호가 쌍으로 저장되어야 한다.
또한 TLB에 있는지 확인하기 위해 모든 항목들을 탐색하는데에 오버헤드가 생긴다. 이 오버헤드를 줄이기 위해 병렬탐색이 가능한 연관 레지스터(associative register)가 사용된다.
- EAT(Effective Access Time):
- : 연관 레지스터에 접근하는 시간
- : 요청된 페이지에 대한 주소 변환 정보가 연관 레지스터에 존재할 확률
