[운영체제] 운영체제(OS) 메모리 관리 - (1) 불연속 메모리 할당, 페이징

메모리 불연속 할당(Noncontiguous memory allocation)

메모리 불연속 할당은 하나의 프로세스가 메모리의 여러 위치에 분산되어 올라갈 수 있는 메모리 할당 기법을 말한다.

 

들어가며

이전 게시글에서 운영체제 메모리 할당 방식과 스와핑, 스레싱, 페이지폴트와 같은 개념을 알아보았다.

https://brightstarit.tistory.com/16

운영체제(OS) 메모리 관리 - (1) 연속 메모리 할당

 

이번 포스팅에서는 메모리 불연속 할당 중 페이징 방식에 대해 알아보도록 하자.

페이징(paging)

페이징 기법은 프로세스의 주소 공간을 동일한 크기의 페이지 단위로 나눠 물리적 메모리의 서로 다른 위치에 페이지들을 저장하는 방식을 말한다.

페이징 기법에서는 물리적 메모리를 페이지와 동일한 크기의 프레임으로 미리 나누어 둔다.

메모리에 올리는 단위가 동일한 크기의 페이지 단위이므로 , 메모리를 같은 크기로 미리 분할해 두더라도 빈 프레임이 있으면 어떤 위치든 사용될 수 있기 때문이다.

따라서 페이징 기법은 동적 메모리 할당 문제(메모리 주소 공간 결정 문제)가 발생하지 않는다는 강점을 가진다.

빈 페이지가 보이면 메모리를 올리기만 하면 된다.

페이징 기법에서는 프로세스의 주소 공간과 물리적 메모리가 모두 같은 크기의 페이지 단위로 나누어지기 때문에 빈 공간은 어느 곳이든 활용할 수 있다.

따라서 메모리상의 가용 공간의 크기가 작아서 빈 공간임에도 활용되지 못하는 외부 단편화가 발생하지 않는다.

그러나 프로그램의 크기가 항상 페이지 크기의 배수가 된다는 보장이 없기 때문에 프로세스의 주소 공간 중 제일 마지막에 위치한 페이지에서는 내부 단편화가 발생할 가능성이 있다.

주소 변환 기법

CPU에서 나오는 모든 주소는 아래와 같이 페이지 번호(p)와 페이지 오프셋(d) 두 개의 부분으로 나누어진다.

페이지 번호는 프로세스 페이지 테이블(page table)을 액세스 할 때 사용된다.

 

페이지 테이블은 물리 메모리의 각 프레임의 시작 주소를 저장하고 있으며 오프셋은 참조되는 프레임 안에서의 위치다. 따라서, 프레임의 시작주소와 페이지 오프셋이 결합하여 물리 메모리 주소가 된다. 

 

CPU에 의해 생성된 논리 주소를 물리 주소로 변환하기 위해 MMU가 취한 단계

1. 페이지 번호 p를 추출하여 페이지 테이블의 인덱스로 사용한다.
2. 페이티 테이블에서 해당 프레임 번호 f를 추출한다.
3. 논리 주소의 페이지 번호 p를 프레임 번호 f로 바꾼다.

프레임 크기와 마찬가지로 페이지 크기는 하드웨어에 의해 정해진다. 페이지 크기는 2의 거듭제곱으로, 일반적으로 컴퓨터 아키텍처에 따라 페이지당 4KB와 1GB 사이다. 페이지 크기로 2의 거듭제곱을 선택하면 논리 주소를 페이지 번호 및 페이지 오프셋으로 쉽게 변환 할 수 있다. 논리 주소 공간의 크기가 2^m이고 페이지 크기가 2^n바이트인 경우 논리 주소의 상위 m-n 비트는 페이지 번호를 지정하고 n 하위 비트는 페이지 오프셋을 지정한다.

 

메인 메모리에 페이지 테이블을 저장하면 문맥 교환 속도가 빨라지지만 페이지 테이블을 확인하기 위해 메모리 액세스를 함으로써 시간이 더 느려질 수도 있다. 따라서 TLB(translation look-aside buffers)라고 불리는 특수현 소형 하드웨어 캐시를 통해 이를 해결한다.

---

TLB(translation look-aside buffers)

메인 메모리에 페이지 테이블을 저장하면 문맥 교환 속도가 빨라지지만 페이지 테이블을 확인하기 위해 메모리 액세스를 함으로써 시간이 더 느려질 수도 있다. 메모리 i에 액세스 하려고 가정할 때, 먼저 페이지 번호를 기준으로 페이지 테이블 기준 레지스터(PTBR) 오프셋의 값을 사용하여 페이지 테이블의 항목을 찾습니다. 이 작업에는 한 번의 메모리 액세스가 필요하다. 이렇게 얻은 프레임 번호와 페이지 오프셋을 결합하여 실제 주소를 생성한다. 그런 다음 메모리에서 원하는 위치에 액세스 할 수 있다.

이 기법을 사용하면 데이터에 액세스 하려면 두 번의 메모리 액세스가 필요하다(한 번은 페이지 테이블 항목과 한 번은 실제 데이터). 따라서 메모리 접근 시간은 2배로 느려지고 이는 대부분의 상황에서 허용할 수 없는 지연시간이다.

 

이를 해결하기위해 TLB라는 특수형 소형 하드웨어 캐시를 사용한다.

 

TLB(translation look-aside buffers)는 매우 빠른 연관 메모리(associative memory)로 구성된다.

TLB 내 각 항목은 키(key)와 값(value)의 두 부분으로 구성된다.

TLB에 페이지를 찾아달라고 요청이 들어오면 이 찾고자 하는 페이지를 동시에 여러 개의 내부 키(페이지 번호)와 비교한다. 페이지 번호와 같은 것이 발견되면 그에 대응하는 프레임 번호를 알려준다. 검색의 속도는 빠르고 현대 하드웨어에서의 TLB 검색은 명령어 파이프라인의 일부로 동작하며 성능에 추가적인 손해를 끼치지 않는다. 그러나 파이프라인의 일부로 동작하며 성능에 추가적인 손해를 끼치지 않는다. 그러나 파이프라인 단계 동안 검색을 하기 위해서 TLB의 크기는 작게 유지할 수밖에 없으며 통상 32개에서 1024개의 항목을 유지한다.

 

TLB는 페이지 테이블과 함께 다음과 같이 사용된다.

TLB는 페이지 테이블의 일부분만을 저장한다. CPU가 논리 주소를 생성하면 MMU는 해당 페이지 번호가 TLB에 있는지 확인한 후, 페이지 번호가 발견되면 해당 프레임 번호를 즉시 알 수 있고, 메모리를 접근하는데 사용된다.

 

페이지 번호가 TLB에 없으면(TLB 미스라고 함) 주소 변환은 메인 메모리에 접근하는 단계에 따라 진행된다.

또한 페이지 번호와 프레임 번호를 TLB에 추가하여 다음 참조에서 빠르게 찾을 수 있도록 한다.

 

만약 TLB가 가득 차면, 기존 항목 중에서 교체될 항목을 선택해야 한다. 교체 정책은 LRU, 라운드 로빈, 무작위 등 다양한 정책이 사용된다.

 

접근하려는 메모리의 페이지 번호가 TLB에서 발견되는 비율은 적중률(hit ratio)라고 부른다. 

예를 들어 80% 적중률이란 TLB에서 원하는 페이지 번호를 발견할 확률이 80%라는 것을 의미한다.

---

참고 자료

https://zangzangs.tistory.com/134

[OS] 메모리 불연속할당 - (1) 페이징 기법

https://dkswnkk.tistory.com/443

[OS] 메인 메모리(2) - 페이징 기법

https://dkswnkk.tistory.com/456

[OS] 메인 메모리(3) - TLB(translation look-aside buffers)