[운영체제] 페이징

페이징

• 단편화 문제를 압축방식으로 해결하려 했지만, 이 또한 비용이 발생한다. 좀 더 근본적인 해결책을 찾다가 발견한 것이 '페이징'이다.
• 단편화가 문제가 되는 이유는 프로그램을 연속된 메모리공간에 탑재해야만 하기 때문이다. 이러한 '연속적'이라는 조건을 없어지도록 하는 것이 페이징 기법이다.
• 즉, 페이징 기법은 연속된 물리공간을 필요로 하지 않으면서도, 실행시간 및 주소결속 등 프로그램 수행에는 문제가 없도록 하는 방식이다.
• 프레임, 페이지, 페이지테이블 3개로 이루어진다.
• 전체 물리적 공간을 같은 '프레임' 단위로 나누어놓고, 논리적 공간도 프레임과 같은 크기의 '페이지' 단위로 나눈다. 그리고 '페이지 테이블'을 통해 페이지를 프레임에 매핑시킨다. 즉 페이지 테이블은 일종의 주소 변환 테이블의 역할을 하여 각 페이지에 해당하는 프레임 번호를 보유한다.
• 이를 통해 만들어지는 각 페이지에 해당하는 프레임은 연속적인 공간에 존재하지 않고, 그럴 필요가 없다. 페이지단위로 메모리를 할당하여 페이지 테이블을 통해 가상적으로 연속된 공간인 것처럼 보여지도록 만들어주기 때문이다.

페이지테이블과 주소결속

• 논리주소를 'p부분'과 'd부분'으로 나눈다. p는 페이지 번호를 의미하여 페이지테이블에 대한 인덱스로 활용되고, d는 페이지 내의 오프셋을 의미한다.
• 예를 들어 p부분을 위해 4비트, d부분을 위해 12비트를 사용한다고 하자. p부분 4비트 값은 바로 페이지 번호로 활용된다. 즉, 페이지테이블의 p번째 셀에 가면 물리적 공간의 프레임에 대한 번호가 적혀있는 것이다. 페이지테이블의 p번째 셀에 'f'라는 값이 적혀있다고 하자. 그럼 4비트의 p부분을 f값이 대체하게 된다. 이렇게 만들어진 것이 최종적인 물리 메모리에 대한 주소가 된다. f번째 프레임에서 오프셋 d번째 주소, 즉 물리주소 0xf000 + d 가 최종적인 물리 메모리에 대한 주소이다.
• 논리공간 상의 페이지 번호가 페이지테이블에 의해 물리공간 상 번호로 대체되면서 논리주소가 물리주소로 결속되는 것이다.
• 위의 예제에서 페이지의 개수와 페이지의 크기를 구해보자. p부분이 4비트이므로 페이지의 개수는 2의 4승, 16개이다. d부분은 12비트이므로 d의 최댓값은 2의 12승, 4096이 된다. 따라서 페이지의 크기는 4096이다.
• 페이지 테이블은 메인 메모리 상에 존재한다. 그리고 페이지 테이블의 시작 주소는 이를 위한 레지스터인 PTBR(Page-Table Base Register)에 기록되어 있다

페이징 기법의 주소표현

• 페이징 기법의 논리주소는 p와 d로 이루어져 있고, p는 페이지 번호 f를 찾는 페이지테이블의 번호이며 d는 페이지 내의 상대주소(오프셋)이다.
• 결과적 물리주소는 'f*S + d'라고 할 수 있다. 여기서 S는 페이지의 크기이자 프레임의 크기이다.
• d를 위해서 사용해야 하는 비트 수는 log2S일 것이다. (S가 페이지의 크기이자 프레임의 크기이기 때문이다.)
• 일반적으로 페이지의 크기는 하드웨어에 의해 결정되며, 4KB 혹은 8KB 정도이다.
• 리눅스 시스템에서 $getconf PAGESIZE 명령어를 사용하면 페이지 크기를 알 수 있다.

페이징 기법의 단편화

• 페이징 기법에서는 외부단편화는 발생하지 않지만, 약간의 '내부 단편화'가 발생한다.
• 모든 프로그램의 크기가 페이지의 크기(프레임의 크기)의 정수배로 구성되어 있지는 않기 때문에, 0 ~ S-1바이트 만큼의 내부 단편이 생길 수 있다. 즉, 각 프로세스마다 마지막 페이지에 대해 평균적으로 페이지크기(프레임크기)의 절반 정도의 내부 단편이 발생하게 된다.
• 예제) 한 페이지당 512바이트의 크기를 가진 시스템에서 오프셋을 표현하는 비트의 크기는?
• 예제) 해당 시스템에서 829바이트인 프로그램을 적재했을 때 발생하는 내부 단편화의 크기는?

Free frame list

• 가용 프레임을 관리하고 페이지테이블에 기록되는 프레임 번호를 결정하는 것이 Free frame list이다.
• 각 프레임별 할당 상황 (할당여부 및 할당중인 프로세스의 정보)를 테이블에 담아 관리한다.

페이지 테이블의 문제점

• 페이징 테이블의 문제점은 주소결속까지 걸리는 속도 / 페이지테이블의 용량이다.
• 페이징 기법의 핵심은 페이지 테이블에 있고, 주소결속을 위해서는 반드시 페이지 테이블에 들려야 한다. 페이지테이블은 원래 별도의 레지스터 집합을 구성하여 활용하였으나, 페이지테이블의 요구용량이 커짐에 따라 메인메모리 상에 들어있게 되었다. 따라서 '페이지 테이블 접근', '최종 물리주소 접근'. 논리주소 하나에 대해 합쳐서 2번의 메인메모리 접근이 요구되는 것이다.
• 또한 페이지테이블의 시작주소를 알아내기 위해 PTBR(Page-Table Base Register)에도 매번 접근해야 한다.
• 즉, 페이징 기법을 사용하면 레지스터나 메모리를 접근하는 횟수가 증가될 수밖에 없고 이 때문에 필연적으로 속도가 저하되게 되어 있다.

페이지 테이블의 속도 개선

• TLB(Translation Lookaside Buffers) : 16개 혹은 32개의 연관 레지스터를 사용한다. 연관레지스터는 key값과 value값을 저장하여 key값을 활용해 해당 value값을 빠르게 검색해낸다. 이 속도는 메인메모리의 탐색 속도보다 빠르다. 페이지 번호 p와 프레임번호 f의 맵핑 정보쌍을 기록해두고 메모리 접근이 필요하면 먼저 TLB에서 p값을 key값으로 활용해 f값을 빠르게 검색해낸다. 그리고 TLB에 들어있지 않을 경우에만 페이지 테이블에서 찾게 된다. 페이지 테이블에 가서 찾게 되었을 경우엔 해당 내용을 TLB에 추가해놓는다.
• TLB는 FIFO 형태로 업데이트된다. 이는 메모리 접근의 지역성을 이용한 것이다.
• TLB가 일종의 캐시와 같은 역할이라고 생각할 수 있지만 조금 다르다. 캐시는 메모리의 접근 속도를 높이기 위해 활용하는 것으로 물리적으로 가까운 곳에 둔다. CPU에서 물리적 메모리를 계속 접근하려면 메모리 버스 등 거쳐야 하는 회로가 많기 때문이다. TLB는 캐시와 독립적으로 구성되어 운영된다.

페이지 공유

• 사용자 문맥 중 'TEXT' 부분(코드)은 변경되어선 안된다. 이러한 것은 reenterent 코드라고 한다. 따라서 이 부분은 만약 한 프로세스에 의해 먼저 메인메모리에 탑재 되었다면 다른 여러 프로세스가 공유해도 된다.
• 이러한 공유는 페이지 테이블을 활용해 더 효과적으로 해결할 수 있다. 해당 프레임에 대해 페이지 테이블이 동일한 번호를 기록하면 된다.

메모리 보호

• 페이지 테이블에 보호비트를 마련함으로서 메모리 보호 기능을 구현할 수 있다.
• 페이지 테이블에 valid-invalid를 표시하는 bit를 두고 이를 활용해 구분하는 것이다.
• 특정 이유로 해당 페이지를 접근하려는 시도가 있으면 트랩을 걸어 오류로 처리, 메모리의 보호된 영역을 접근하는 것을 방지한다.
• 이 외에도 read-only와 같이 쓰기 권한을 방지하거나, dirty-bit로 해당 프레임의 내용변경여부를 판단하는 비트들도 있다.
• 페이지테이블은 메모리 접근을 위해 반드시 거쳐가야만 하는 곳이기 때문에 이처럼 메모리 보호나 기타 유용한 용도로도 활용할 수 있다.

페이징의 장단점

• 단점 : 페이지 테이블 사용으로 분할방식 대비 주소결속에서 오버헤드 발생 (속도 저하) / 페이지 테이블의 메인메모리 저장으로 공간 낭비
• cf. TLB 사용 및 페이지 테이블의 다단계 구성(구조 개선)으로 단점 완화 가능
• 장점 : 외부 단편화 문제 해결 / 페이지 공유 가능 (메모리 공간의 효과적 활용) / 페이지 보호 가능