메모리는 주소데이터로 구성되어 있다. CPU가 원하는 데이터의 주소를 메모리에 보내면, 메모리는 CPU에게 해당되는 데이터를 보내준다. 또한, CPU에서 계산된 결과를 메모리의 특정 주소에 저장하라고 명령을 보낼 수도 있다.

하나의 프로그램이 실행되기 위해서는 코드, 데이터 그리고 스택을 가지고 있어야 한다. 개발자가 작성한 코드 파일이 컴파일되어 실행파일로 만들어지면, 로더에 의해 메모리에 올라가게 된다. 운영체제는 이 실행 파일을 메모리의 어느 부분에 올릴지를 결정한다. 따라서 메모리 적재시 적절한 메모리 위치에 프로그램을 넣지 않으면 문제가 발생 할 수 있다. 이런 문제를 해결하기 위해 MMU를 사용한다.


메모리 관련 용어


논리주소와 물리주소

CPU가 취급하는 주소를 논리주소, 해당 논리주소에 연관된 실제 메모리의 주소를 물리주소라고 한다. 프로그램이 논리주소를 통해 데이터를 요청하면, 운영체제는 해당 논리주소를 물리주소로 변환해야 하며, 이러한 역할을 MMU(Memory Management Unit)가 수행하고 있다.


동적 적재

개발가자 개발한 코드가 실행되려면 메인 메모리에 적재되어 있어야 하지만, 가끔은 매우 큰 코드를 처음부터 적재하는 것은 비효율 적일 수 있다. 따라서, 일부 코드는 메인 메모리에 미리 적재되지 않도록 설정할 수 있다.
이런 코드들은 실제로 프로그램에 의해 호출되기 전까지는 메모리에 적재되지 않으며, 메모리에는 stub이라 불리는 재배치 가능 요소로 대체된다. 이후 스텁을 만나면 진행을 잠깐 멈췄다가 해당 스텁이 가르키는 경로의 코드를 적재한 뒤 실행한다. 이런 방식으로 실제 실행될 때 반드시 필요한 루틴/데이터만 적재할 수 있도록 한다.


동적 연결

목적 파일과 라이브러리 파일 사이의 연결을 프로그램의 실행 지점까지 지연시키는 방법.


스와핑

현대 시스템에는 선점(우선순위를 가진 프로세스가 실행중인 프로세스를 가로채 실행하는 방식)이 허용되어 있어, 진행하던 작업을 멈추고 다른 작업을 수행해야 하는 경우가 생길 수 있다. 하지만, 멈춘 작업들을 메모리에 계속 내버려둔다면 새로운 프로세스를 더 받아들일 수 없어, 프로세스를 디스크로 빼냈다가 다시 적재하는 기능이 요구되었는데, 이것을 스와핑이라고 한다.

Backing Store는 하드디스크의 일부분이다. 현재 사용되지 않는 프로세스를 Backing store로 몰아내는 작업을 swap out이라고 하며, 반대로 필요한 부분이 생기면 그 부분에 대해 메모리로 적재하여 올려주는 작업을 swap in이라고 한다.


디스패처

스와핑에 의해 작업이 메모리에 적재되지 않을 가능성이 생겼다. 이를 위해 실행할 작업이 메모리에 적재되어 있는지 검사하는 프로그램을 디스패처라고 한다. 디느패처는 프로세스가 메모리에 적재되어 있는지 검사하고, 없다면 이미지를 재적재시킨다.


물리적 메모리의 할당 방식

물리적 메모리는 OS영역과 user process영역으로 나뉘어 사용된다. 여기서는 사용자 영역의 할당방식에 대해서 알아본다.

사용자 프로세스 영역에서의 관리 방법

  • 연속 할당 방식 : 물리적 메모리의 연속적인 공간에 프로세스를 적재하는 방식
    • 고정 분할 방식 : 물리적 메모리를 고정 크기의 분할로 나누는 방식
    • 가변 분할 방식 : 프로그램 실행, 종료 순서에 따라 분할을 관리하는 방식
  • 비연속 할당 방식 :하나의 프로세스를 물리적 메모리의 여러 영역에 분할하여 적재하는 방식
    • 페이징 기법 :
    • 세그멘테이션 기법 :
    • 페이지의 세그멘테이션 기법

연속 할당 방식

고정 크기 할당

메모리를 동일한 크기로 자른 뒤, 각 프로세스마다 블록 하나만 주는 방식입니다. 전체 메모리가 N분할 되었다면 적재될 수 있는 프로세스도 최대 N개이므로, 다중 프로그래밍 실행 가능 프로세스 개수는 블럭의 개수와 같다고 볼 수 있다. 모든 프로세스의 할당된 메모리 크기는 동일하다. 현재는 거의 사용하지 않는 방식이다. 이런 방식은 외부 단편화 / 내부 단편화가 발생 할 수 있기 때문이다.

외부 단편화 : 프로그램의 크기보다 파티션의 크기가 작은 경우 적재하지 못하여 발생하는 메모리 공간. 각각의 단편화된 공간의 크기는 작지만, 모으면 새로운 프로세스를 하나 적재 할 수 있을만큼 커진다. 내부 단편화 : 프로그램의 크기보다 파티션의 크기가 큰 경우 파티션에 적재하고 남는 메모리 공간

  • 내부 단편화보다 작은 크기의 프로세스를 수행하려고 해도 적재되지 못해 메모리 낭비를 야기한다.

동적 크기 할당

고정 할당과 돨리, 각 프로세스에게 할당된 메모리 크기가 다를 수 있다. 이 경우 내부 단편화는 발생하지 않지만, 외부 단편화가 발생할 수 있다. 동적 크기 할당 방식은 아래 세가지가 존재한다.

최초 적합(First-fit)

메모리를 순차적으로 탐색하여 제일 먼저 발견한 적절한 공간에 프로세스를 적재한다. 다른 두 방식에 비해 시간복잡도가 낮다.

최적 적합(Best-fit)

남은 슬롯 중 가장 작은 공간에 프로세스를 적재한다. 모든 빈 공간을 탐색해야 하기 때문에 시간복잡도가 높으며, 매우 작은 크기의 빈 공간을 생성한다.

최악 적합(Worst-fit)

최악적합은, 가용 공간중 가장 큰 공간에 프로세스를 적재한다. 모든 빈 공간을 탐색해야 하며, 매우 큰 크기의 빈 공간을 생성한다.



압축(Compaction)

동적으로 메모리를 할당하여도, 외부 단편화로 인한 메모리 낭비가 발생하는 것은 막을 수 없다. 이를 해결하기 위해서 Compaction이라는 방식을 차용했다.(GC에서 Mark-and-Sweep-and-Compaction에서 사용되는 Compaction 개념과 거의 동일하다!)
Compaction은 말 그대로, 뜨문뜨문 비어있는 프로세스 메모리 영역을 모아준다. 메모리를 이동시키는 작업은 크기에 비례해 비싸지기 때문에, 어떻게 메모리를 몰아 넣을지에 따라 시간복잡도가 달라지며, Runtime-Binding이 허용되지 않으면 애초에 해결 할 수 없다. 달라지는 방식은 아래 그림을 참고하기 바란다.


이렇듯 외부 단편화는 연속적 할당에서는 발생할 수 밖에 없다는 것을 알게 되었다. 이를 해결하기 위해 비연속적 할당방식, 페이징이 등장한다.

페이징

프로세스의 주소 공간을 동일한 사이즈의 페이지 단위로 나누어 물리적 메모리에 불연속적으로 저장하는 방식이다.

프레임과 페이지

페이징은 고정크기 할당과 비슷하지만, 나눠진 물리적 블럭을 프레임(Frame)이라고 하며, 하나의 프로세스가 여러개의 프레임을 할당받는 방식으로 동작한다. 이 때, 운영체제는 프로세스의 메모리 접근을 관리하기 위해 프레임을 직접적으로 관리하지 않고 페이지라는 논리적인 블럭을 사용한다. 둘은 1:1 대응되는 관계이므로, 프레임과 페이지의 단위 크기는 같다.

페이지 테이블

페이지는 페이지 테이블을 통해 자신이 어느 프레임을 가르키고 있는지 알 수 있다. 이 페이지 테이블은 앞서 말한 MMU의 실 예시라고 볼 수 있다.

위 그림에서, P1의 3번째 페이지는 페이징 테이블에서 4번째 프레임을 가르키는 것을 볼 수 있다. 이렇게 CPU는 페이지 테이블을 통해서 프로세스의 물리적 메모리 주소에 접근할 수 있다.

논리적 주소 변환

한 페이지에는 여러개의 데이터가 담길 수 있다, 그렇기 때문에 어떤 데이터의 시작지점, 즉 주소를 명확하게 표현하기 위해서는 2개의 정보가 필요하다.

  • 페이지 번호
  • 페이지 내에서의 시작지점과 변위(offset)

위 예제를 통해 논리적 주소를 물리적 주소로 변환하는 방법을 알아보자. 논리적 주소 0b1110은 두가지 정보를 표현한다.

  • 페이지 번호 : 0b11 -> 3
  • 변위 : 0b10 -> 2

페이지 테이블을 통해 프레임으로 바꿔보자.

  • 프레임 번호 : 0b11 -> 1 == 0b01
  • 프레임 변위 : 변동사항 없음

결과적으로, 논리적 주소 0b1110은 물리적주소0b0110과 같으며, 해당 주소가 가르키는 데이터는 0b01번째 프레임에서 0b10번째에 위치해있는 c를 말한다.



주소의 크기

램의 용량이 커지며 표현해야 할 영역의 크기도 증가되었다. 실제 32비트 운영체제에서는 최대 4GB만 인식할 수 있기 때문에 4바이트로도 모든 영역을 표현할 수 있지만, 64비트 운영체제에서는 8바이트는 되어야 인식된 메모리의 모든 영역을 표현할 수 있다.
메모리의 크기가 2^m바이트이고, 페이지의 크기가 2^p바이트라면, 다음 규칙에 따라 가용 가능한 최소 크기의 주소사이즈를 산출할 수 있다.

  • 변위 부분의 크기 : p비트
  • 번호 부분의 크기 : m-p비트


변위 부분의 크기 :

변위 부분은 페이지 어느 부분이라도 가르킬 수 있어야 하기 때문에, 페이지의 크기가 2^p바이트라면 최소 p비트가 필요하다. 예를 들어, 페이지의 사이즈가 4바이트라면 최소 2개 비트는 있어야 모든 바이트를 표현할 수 있다.

번호 부분의 크기 :

메모리의 크기가 2^m바이트이고, 페이지의 크기가 2^p바이트라면, 전채 램은 2^m/2^p개의 페이지로 분할된다. 이걸 정리해보자면 2^(m-p)개의 페이지와 같고, 변위 부분에서와 같이 최소 m-p개의 비트가 있어야 모든 페이지를 가르킬 수 있다.


내부 단편화 :

사용하지 못하는 페이지는 존재하지 않으므로 외부 단편화는 없어졌지만, 페이지를 할당하고 남는 공간이 발생하여 내부 단편화가 발생할 수 있다. 즉, 프로세스의 크기가 페이지 크기의 배수가 아니라면 마지막 프로세스의 페이지는 한 프레임을 다 채울 수 없다. 예를 들어, 프로세스가 15바이트인데 페이지를 4바이트 단위로 나눈다고 생각해보자. 그러면 3개의 바이트 페이지는 완전하게 다 사용할 수 있지만, 마지만 페이지는 3바이트의 크기가 만들어진다. 프레임은 4바이트의 크기인데 3바이트 크기의 페이지가 들어오면 1바이트의 메모리 낭비가 생기는 것이다.


세그멘테이션

앞서 말한 페이징은 프로세스를 물리적인 단위로 일정크기 균등하게 잘라서 사용하는 방식이다. 하지만 세그멘테이션은 주소 공간을 의미 단위로 나누어 물리적 메모리에 적재하는 방식이다.. 예를 들어, 하나의 프로세스를 실행할 때 기본적으로 코드, 데이터, 스택이 필요하다. 여기서 물리적으로 메모리를 할당할 때, 코드를 쪼개서 관리한다면?비효율 적이지 않을까 하여 같은 역할을 가진 데이터는 하나의 세그먼트에 저장시키도록 한다.

프로세스를 어떻게 자르는가에 대한 방법을 제외하고, 메모리에 할당하는 방법은 페이징과 동일하다. MMU의 재배치 레지스터를 통해 논리주소를 물리주소로 바꾸어주는 방식을 취한다.



이렇게 세그먼테이션만 사용하면 될 것 같지만, 세그먼트는 크기가 고정되어있지 않고 가변적이다. 크기가 다른 각 세그먼트를 메모리에 두려면 동적으로 메모리를 할당해야 하고, 이 경우 외부 단편화가 발생할 수 있다. 그래서 내부적으로는 세그먼테이션과 페이징의 기법을 모두사용한다.


페이징과 세그먼테이션을 동시에 사용하는 기법

우선 프로세스를 세그먼트 단위로 자른다. 이렇게 의미있는 단위로 나누면 보호와 공유를 하는 측면에서 이점을 갖는다. 하지만 외부 단편화가 발생할 수있기에, 잘라진 세그먼트를 다시 일정 간격인 페이지 단위로 자르는 페이징 방법을 취한다. 이를 통해 내부단편화와 외부단편화를 모두 막을 수 있지만, 두가지 테이블을 모두 거쳐야 하기 때문에 속도 면에서 조금 떨어진다.


참고 자료

  1. 8. 운영체제 메모리 관리
  2. 8-2. 페이징, 세그멘테이션
  3. 운영체제 정리 🦖 ch08. 메모리 관리 전략

oksusutea's blog

꾸준히 기록하려고 만든 블로그