Main Memory

k_bell·2024년 6월 15일

목록 보기

5/15

Background

현대 컴퓨터 시스템에서 메모리의 역할

현대 컴퓨터 시스템에서 매우 중심적인 역할을 수행하는 메모리는 각기 고유한 주소를 가진 바이트의 배열로 이루어져 있다. 프로그램은 디스크에서 메모리로 로딩되어서 프로세스 내에 위치해야 한다. CPU가 직접 접근할 수 있는 저장장치는 레지스터와 메인 메모리밖에 없다. Cache는 CPU와 메인 메모리 사이에 존재하는데 캐시는 오직 하드웨어에 의해서만 관리되며, OS는 어떠한 컨트롤도 하지 않는다.

CPU가 메인 메모리에 접근할 때 memory stall이 발생할 수 있다.

Logical vs Physical Address Space

Logical address를 실제 메모리의 physical address에 연결하는 것은 적절한 메모리 관리의 핵심이다. logical address는 cpu가 바라보는 메모리 주소, 프로그램 실행 중에 cpu가 생성하는 주소이다. cpu는 메모리의 실제 주소에 직접 접근하지 않는다. 이는 한정된 메모리 공간을 효율적으로 관리하기 위함도 있지만, 멀티 프로세싱을 위한 부분이 가장 크다고 생각한다. 각각의 프로세서가 직접 메모리 주소에 접근할 수 있다면 서로의 주소를 침범하여 충돌이 일어날 가능성이 높기 때문이다.

Logical address = Physical address
: in compile-time and load time address binding
Logical address != Physical address
: in execution-time address binding

Logical memory address의 중요성

: logical address는 프로그램이 실행될 때 격리된 환경에서 실행될 수 있도록 한다. 이를 통해 여러 프로그램이 동시에 실행될 때 각 프로그램이 다른 프로그램의 메모리에 접근하지 못하도록 보호할 수 있다.

Physical memory address의 중요성

: 실제 메모리 하드웨어에 직접 접근하므로, 정확한 메모리 관리가 필요하다. OS는 physical address를 효율적으로 관리하여 시스템 성능을 최적화한다.

Memory Management Unit

프로세스가 physical address에 접근하기 위해서는 logical address를 pysical address와 매핑 시키는 과정이 필요하다. 이러한 역할을 수행하는 것이 MMU이다. Logical address를 변환하여 매핑하는 과정은 매우 빈번하게 발생하므로, MMU는 하드웨어적으로 구현되어 있다.

지금부터는 logical address를 어떻게 physical address로 변환하는지 그 방법에 대해서 알아볼 것이다. 우선 base register와 limit register에 대해서 설명이 필요하다.

base register란 logical address가 실제 physical address에 매핑될 때 그 시작 주소를 의미한다. 즉 해당 프로세스가 매핑될 메모리의 시작 위치를 지정해 주는 것이다. 따라서 logical address의 메모리 시작 주소를 알고 싶다면, logical address + base register를 계산하면 된다.

앞에서 logical address는 실제 메모리에서 프로세스 간의 주소 침범을 막기 위해 매우 중요한 개념이라고 했다. 이제 logical address가 실제 메모리에서 어떤 위치에서 시작할지를 알았으니, 끝 주소만 안다면 우리는 각각의 프로세스가 실제 메모리에서 어디부터 어디까지 매핑되어 있는지 알 수 있다.

메모리에서 프로세스의 끝 주소를 알 수 있도록 해주는 것이 바로 limit register이다. limit register는 프로세스가 가질 수 있는 한계 범위를 알려준다. 따라서 [base register ~ base register + limit register]가 프로세스가 실제 메모리에 매핑되어 있는 주소인 것이다.

간단한 예제를 통해 정리해보겠다. 프로세스 P1의 logical address = 5, base register = 1100, limit register = 600일 때, P1의 physical address는?

매우 간단하다. 시작 주소 = 1105, 마지막 주소 = 1705이다.

지금부터는 base register = relocation register라고 정의한다.

Contiguous Allocation

지금까지 설명한 것처럼 logical address에 같은 relocation register(base register)를 더하여 physical address에 매핑하는 것을 contiguous allocation (연속 할당)이라고 한다.

메인 메모리는 크게 두 파티션으로 구분할 수 있다.
1. OS가 상주하는 low memory (with interrupt vector)
2. User processes가 존재하는 high memory

즉, 위 그림이 전형적인 연속 할당이다. 프로세스의 logical address에 relocation register를 더해 하나의 프로세스를 연속된 메모리 공간에 할당하는 것이다.

Contiguous Allocation 오해하지 말자!
contiguous allocation은 각기 다른 프로세스들이 연속적으로 할당되는 것이 아니다. 하나의 프로세스가 연속된 메모리 공간을 차지하는 것이 연속 할당이다. 즉, 하나의 프로세스는 연속된 메모리 공간에 있지만, 각기 다른 프로세스는 메모리 공간에서 서로 떨어져 있을 수 있다는 것이다.

Hole & Fragmentation

위 그림은 연속 할당이 가지는 문제점을 보여주는 그림이다. 하나의 프로세스는 메모리에서 연속된 공간을 차지하고 있다. 해당 프로세스가 종료되면 메모리에는 그만큼의 이용 가능한 블록이 생기게 되는데 이를 hole이라고 한다.

문제는 이 hole들이 fragmentation(파편화)가 된다는 것이다. 위의 그림을 보면 종료된 프로세들로 인해 여러 개의 hole이 생겨난 것을 알 수 있다. 그런데 이 hole들이 작은 사이즈의 블록으로 나누어 지면서 여러 개의 hole을 합치면 새로운 프로세스를 할당할 수 있음에도 그러지 못한다는 것이다. 맨 우측의 메모리 이미지를 보면 두 개의 hole을 합친다면 프로세스 8을 실행해도 할당할 수 있을 것이다. 하지만 저런 형태로 hole이 파편화되어 있다면 프로세스를 할당할 수 없게 된다.

Dynamic Storage Allocation Problem

메모리의 free hole에 어떻게 프로세스를 할당할 것인가?

지금부터 총 3가지 allocation 방법에 대해서 알아보도록 하자.

free hole들을 list의 형태로 관리하는 것이 필요하다.

First-Fit
: 프로세스를 할당할 때 size를 만족하는 첫 번째 free hole에 할당하는 방법이다. list를 순회하다가 프로세스를 할당할 수 있는 크기의 hole을 만나면 바로 해당 hole에 프로세스를 할당한다.
Best-Fit
: free hole들을 size대로 정렬한 뒤, 할당할 수 있을만큼의 크기를 가진 hole 중 가장 작은 hole에 할당하는 것이다.즉, 프로세스에 가장 적절한 크기의 hole을 할당하는 것이며, 이러한 알고리즘 수행을 위해서는 hole-list를 크기를 기준으로 오름차순으로 정렬할 필요가 있다.
Worst-Fit
: 할당할 수 있는 hole 중에 크기가 가장 큰 hole에 할당하는 방법이다.

당연하게도 first-fit과 best-fit이 속도와 저장공간 효율 측면에서 worst-fit보다 더 나은 성능을 보인다.

Fragmentation

Fragmentation(파편화)는 위에서 언급한 것처럼 메모리에 프로세스의 할당/해제 과정이 반복되면서 hole들이 작은 파편으로 나뉘어지는 것을 의미한다. 그러나 이것은 엄격히 말하면 External Fragmentation에 해당하며, 우리는 fragmentation을 두 가지로 정의할 수 있다.

External Fragmentation
: 외부 파편화의 가장 큰 문제점은 메모리의 전체 여유 공간에는 요청을 만족할 만큼의 공간이 존재하지만, hole들이 연속적으로 존재하지 않아 해당 요청을 수락할 수 없다는 것이다.
Internal Fragmentation
: 내부 파편화는 프로세스가 자신이 할당받은 연속적인 공간을 모두 다 이용하지 않는 것이다. 즉, limit register가 너무 크게 할당되어서 프로세스에게 불필요한 크기의 메모리 공간을 할당한 것이다.

Fragmentation을 어떻게 줄일 수 있을 것인가?

외부에 흩어져 있는 파편들을 재배치 하여 하나의 큰 hole로 만드는 compaction이 있다. 그렇다면 compaction을 어떻게 수행할 수 있을 것인가? 가장 간단한 방법으로는 모든 프로세스들을 재배치하는 것이다. 하지만 이 경우에는 당연하게도 매우 심각한 오버헤드가 발생할 것이다. 따라서 우리는 지금부터 non-contiguous한 방법의 paging에 대해서 알아볼 것이다.