[OS] 메모리 관리

반효경 교수님 운영체제 강의와 도서를 정리한 내용입니다.

주소 바인딩

CPU 는 소스 코드를 읽어낼 때 physical address 가 아닌 virtual address 를 읽고 있다. 이러한 상황에서 메모리를 접근해야 한다면 physical address 가 필요해진다. 이렇게 논리적 메모리 주소를 물리적 메모리 주소로 바꿔주는 것을 Address Binding 이라고 부른다.

 

주소 바인딩은 물리적 메모리 주소가 결정되는 시기에 따라 세가지로 분류된다.

• 컴파일 타임 바인딩
  • 코드를 컴파일할 때 물리적 메모리 주소가 정해진다. 만약에 다른 물리적 메모리 주소를 사용하고 싶다면 다시 컴파일해야 하므로 잘 사용하지 않는 기법이다.
• 로드 타임 바인딩
  • 프로그램의 실행이 시작될 때에 물리적 메모리 주소가 결정된다. 프로그램이 종료될 때까지 그 자리 그대로 유지된다.
• 실행 시간 바인딩
  • 프로그램이 실행을 시작한 후에도 물리적 메모리상의 주소가 변경될 수 있는 바인딩 방식이다. 따라서 CPU 는 메모리 접근을 할 때 항상 어디있는지 확인을 해주어야 하는데 이를 돕는게 주소 매핑 테이블이다. 그리고 MMU (Memory Management Unit) 를 통해 하드웨어적 도움을 받기도 한다.

MMU

MMU 가 어떻게 주소 바인딩을 하는지 살펴보자. MMU 는 기준 레지스터인 재배치 레지스터 (relocation register) 는 프로세스의 물리적 메모리 시작 주소를 가진다. 그렇기 때문에 논리적 메모리 주소에 그대로 더해주면 물리적 메모리 주소 값을 얻을 수 있다. 물론 이것은 프로세스의 주소 공간이 연속적으로 적대된다는 가정 하에 진행된다.
(그리고 MMU는 CPU 안에 하드웨어로 구현되어있다!)

Context Switching 이 되는 상황을 생각해보자. 프로세스가 바뀌면 가르키는 물리적 메모리 주소 공간 또한 바껴야한다. 즉 재배치 레지스터의 값이 바껴야하는 것이다. 정리하자면 문맥 교환이 될때에는 재배치 레지스터의 값이 바뀐다.

다중 프로세스 환경에서 프로세스 A 가 진행 중에 프로세스 B의 메모리 주소 공간을 가르킨다면 어떻게 될까? 이는 메모리 보안으로 이어지는 문제로 심각한 문제이다. 프로세스 간의 영역은 침범되어서는 안된다. 이를 방지하기 위해 한계 레지스터 (limit register) 를 사용한다.

한계 레지스터는 해당 프로세스의 크기를 담고 있다. 따라서 논리적 주소 값이 한계 레지스터의 값보다 크다면 이것은 프로세스의 영역을 벗어나는 일이다. 이는 OS 차원에서 트랩을 발생시켜 강제종료시켜버린다.

물리적 메모리 할당 방식

프로세스를 메모리에 올리는 방식에 따라 두가지가 있다.

• 연속 할당 : 하나의 프로세스를 물리적 메모리의 연속적인 공간에 적재하는 방식
  • 고정 분할 : 영구적으로 크기 고정
  • 가변 분할 : 분할의 크기, 개수가 동적으로 바뀜
• 불연속 할당 : 하나의 프로세스를 여러 영역에 분산해 적재하는 방식
  • 페이징
  • 세그먼테이션
  • 페이지드 세그먼테이션연속 할당
    분할을 하다보면 아쉽게 남는 공간들이 있는데 이에 대해 알아보도록 하자
• 내부 조각 : 프로세스가 분할보다 작아서 남는 공간
• 외부 조각 : 프로세스가 분할보다 커서 생기는 공간. 실제로는 분할2와 분할4를 합치면 프로세스3이 들어갈 공간이 충분하지만 둘은 분산되어 있기 때문에 프로세스3이 들어갈 수 없다. 이는 메모리가 찼다가 해제됨을 반복하면서 빈공간이 분산적으로 생기기 때문에 나타나는 문제이다.

사실 연속할당은 MMU를 사용하던 옛날에 사용하던 방법으로 현재는 불연속 할당 방식이 쓰인다.

연속할당 - 가변분할

가변분할 방식에서는 어떻게 프로세스를 효율적으로 올리느냐가 관건인데 이에 대한 세가지 솔루션이 있다.

• 최초적합 (first-fit) : 존재하는 가용 공간을 full scan 하다가 들어갈 수 있는 적합한 공간을 최초로 발견하면 그 공간에 프로그램을 올린다.
• 최적적합 (best-fit) : 존재하는 가용 공간 중 내부 조각이 제일 적을 (남는 공간이 최소가 되는) 공간을 찾아 넣는다. 탐색하는 시간이 오래걸리지만 공간 효율성 측면에서는 좋다.
• 최악적합 (worst-fit) : 가용 공간 중에서 가장 크기가 큰 곳에 프로그램을 할당한다. 최적적합과 마찬가지로 full scan를 해야하므로 시간 측면에서도 안 좋고 가용 공간을 빨리 소진하기 때문에 공간 측면에도 안좋다.
• 컴팩션 (compaction) : 물리적 메모리 영역 중에서 사용 중인 메모리 영역을 한쪽으로 몰고 가용 공간들을 다른 한쪽으로 모아서 가용 공간을 확보한다. 듣기만 해도 cost가 매우 높은 기법이다.불연속 할당 기법연속적으로 올리는 것 보다는 불연속적으로 분산하여 메모리에 올린다면 더 효율적으로 메모리 가용 공간을 이용해볼 수 있다.
• 페이징 기법
• 세그먼테이션 기법
• 페이지드 세그먼테이션페이징 기법

유혁 교수님 운영체제 슬라이드

프로세스의 주소공간을 동일한 크기의 페이지 단위로 나누어 물리적 메모리의 서로 다른 위치에 페이지들을 저장하는 방식이다. 물리적 메모리를 페이지와 동일한 크기의 프레임으로 미리 나눠둔다.
프로세스는 각자의 페이지 테이블을 가지며 이 테이블을 통해 물리적 메모리 주소 공간을 매핑한다. 페이지 테이블에서 인덱스 자체가 페이지의 넘버가 되고 엔트리의 값은 프레임 번호가 된다. 그리고 페이지 테이블은 보조 메모리에 구현되어 있다.

페이지 테이블에 대한 기본 변환 방식은 위의 그림을 참고하면 된다.

32 bit 주소 체계에서 page number 24 bit + offset 8 bit 로 가정하면 다음과 같다.

❗그림 수정
보조 메모리 접근이 아니라 메인 메모리 접근이다.
페이지 테이블과 프레임 모두 메인 메모리에 저장되어 있다.

 

우리는 결국에는 그림에서와 같이 2번의 보조 메모리 접근을 하게 된다. 이는 엄청난 오버헤드이므로 캐싱이 필요하다.

TLB

TLB (Translation Look-aside Buffer) 는 페이지 테이블을 보기 전에 조회되는 버퍼로 페이지 테이블과는 달리 모든 페이지에 대한 매핑 정보가 들어있진 않다. 그렇기 때문에 entry 하나에는 page number 에 대한 정보 또한 포함되어 있어야한다. TLB에서 물리적 프레임 넘버를 바로 알 수 있도록 캐싱 역할을 하는 것이다.
이때 주의할 점은 주소 변환 정보는 프로세스 별로 다르기 때문에 문맥교환 시 이전 프로세스의 주소 변환 정보를 담고 있던 TLB 내용은 모두 비워내야한다.

TLB 와 주소 변환을 해주는 MMU 모두 CPU 안에 구현되어있다.

Multi-level Paging

하나의 프로세스가 하나의 페이지 테이블을 갖는다면 보조 메모리에 그만큼의 테이블이 존재해야한다. 보조 메모리의 공간 절약을 위해 페이지 테이블을 덜 갖게 하는 방법을 생각해보자.
하나의 프로세스는 결국엔 전체 공간 중에서 지극히 일부분만 사용한다. 이 점을 이용해서 필요없는건 만들지 않도록 해보자.
2단계 페이징 기법에서는 외부 페이지 테이블과 내부 페이지 테이블 2개가 존재한다. 쓰이지 않는 주소 공간에 대해서는 외부 페이지 테이블의 엔트리를 null로 만들어 내부 페이지 테이블을 만들지않는다.
이렇게 해서 공간적인 이득을 볼 수 있지만, 주소 변환을 위해 접근해야하는 페이지 테이블의 수가 증가하므로 시간적 손해가 존재한다.

32 bit 주소 체계에서 페이지 하나의 크기를 4KB, 페이지 테이블 항목의 크기가 4B 라고 가정하자.
1B 는 데이터를 표현하는 최소 단위이다. 페이지 하나가 4KB (=2^12B) 이기 때문에 12 bit 로 1B 하나 하나로 이루어진 공간을 표현할 수 있다. 따라서 offset 은 12 bit 가 된다.
그리고 내부 페이지 테이블은 프레임의 크기와 같게 설계되어 있다. 따라서 4KB / 4B = 1K (=2^10) 로 2^10 개의 entry 를 구별해야 한다. 따라서 내부 페이지 테이블을 표현하는데 10 bit 가 쓰인다. 나머지 10bit는 외부 페이지 테이블을 표현하는데 쓰인다.

역페이지 테이블

물리적 메모리의 페이지 프레임 하나당 페이지 테이블에 하나씩의 항목을 두는 방식이다. 각 프로세스 마다 페이지 테이블을 만드는 것이 아니라, 물리적 주소에 대해 페이지 테이블을 만드는 것이다.

역페이지 테이블에 주소 변환 요청이 들어오면, 그 주소를 담은 페이지가 물리적 메모리에 존재하는지 여부를 판단하기 위해 페이지 테이블 전체를 다 탐색해야하는 어려움이 있다. 그렇기 때문에 일반적으로 메모리에 유지하는 대신 연관 레지스터에 보관해 전체 항목에 대한 병렬탐색을 가능하게 함으로써 시간적 효율성을 꾀한다.

공유 페이지

공유 코드는 메모리 공간의 효율적인 사용을 위해 여러 프로세스에 의해 공통으로 사용될 수 있도록 작성된 코드를 말한다. 공유 페이지란 공유코드를 담고 있는 페이지를 뜻한다. 공유된는 코드이기 때문에 read-only 속성을 가진다.

메모리 보호

• 보호비트 (protection bit) : 각 페이지에 대한 접근 권한의 내용을 담는다. 예를 들어 위의 공유 페이지의 경우 읽기 권한만 존재하도록 한다.
• 유효무효비트 (valid-invalid bit) : 페이지의 내용이 유효한지에 대한 내용을 담고있다. 유효하다면 메모리 프레임에 페이지가 존재함을 뜻하고 무효라면 물리적 메모리에 올라와 있지 않고 백킹 스토어에 존재함을 뜻한다.세그먼테이션 (Segmentation)
  페이징은 주소 공간을 동일한 크기 단위로 나누어 물리적 메모리에 올리는 방법이었다. 세그먼테이션은 의미 단위 (ex. 코드, 데이터, 스택) 의 세그먼트로 나누어 물리적 메모리에 올리는 방식이다. 이는 논리적인 단위로 나눈 것이기 때문에 크기가 균일하지 않다. 여기서 오는 오버헤드가 뒤따르게 된다.

세그먼트 테이블의 항목은 기준점, 한계점을 갖는다. (추가적으로 보호비트, 유효무효비트도 똑같이 존재한다.) 페이징 기법에서는 모든 페이지의 길이가 동일하므로 페이지 프레임 위치만 유지해도 벗어나는 일은 없었지만 세그먼테이션은 세그먼트의 길이가 동일하지 않기 때문에 한계점도 필요하다.
페이징 기법에서 주소 변환 시 필요한 테이블을 찾기 위해 테이블 기준 레지스터와 페이지 테이블 길이 레지스터의 도움을 받았듯이, 세그먼테이션 기법에서도 세그먼트 테이블 기준 레지스터와 세그먼트 테이블 길이 레지스터를 사용한다.

• 세그먼트 테이블 기준 레지스터 : 현재 CPU에서 실행중인 프로세스의 세그먼트 테이블이 메모리의 어느 위치에 있는지 그 시작 주소
• 세그먼트 테이블 길이 레지스터 : 프로세스의 주소 공간이 몇개의 세그먼트로 구성되는지
  
  두 가지 검사를 진행하게 된다.

1. 주어진 세그먼트 번호가 세그먼트 테이블 길이 레지스터의 값보다 작은지 확인한다. 그렇지 않다면 존재하지 않는 세그먼트에 대한 접근이기 때문에 트랩을 발생시킨다.
2. 주어진 offset (d) 가 세그먼트의 길이(limit) 보다 작은지 확인한다.

그리고 페이징과 동일하게 공유 세그먼트를 통해 공통되는 부분은 공유하기도 한다.

세그먼트는 의미단위로 나누어져 있어 페이징 기법보다 좋은 점이 존재한다. 주소 공간의 일부를 공유하거나 접근 권한 제어를 하고자 하는 경우 효과적이다. 왜냐하면 동일한 크기로 나누는 페이징의 경우 하나의 페이지에 공유 코드와 사유 데이터 영역이 같이 존재할 수도 있기 때문이다. 이에 반해 세그먼트는 의미 단위로 나누어져 있기 때문에 관리가 용이하다.

그러나 세그먼트의 길이가 균일하지 않아 외부 조각 문제가 발생할 수 있다. 세그먼트를 가용 공간에 할당하는 방식에는 최초적합, 최적적합 방식이 있따.

페이지드 세그먼테이션

프로그램을 의미 단위의 세그먼트로 나누되 세그먼트가 임의의 길이를 가질 수 있는 것이 아니라 반드시 동일한 크기 페이지들의 집합으로 구성되어 있다.

하나의 세그먼트 크기를 페이지 크기의 배수가 되도록 함으로써 외부 조각의 문제점을 해결하며, 세그먼트 단위로 프로세스 간의 공유와 접근 권한 보호가 되도록 하여 둘의 장점을 합친 방식이다.