[OS] Memory Management

1. 메모리 구조

 

메모리는 CPU 자원만큼 컴퓨터 사용에 중요한 자원 중 하나이다. 그렇기 때문에 메모리는 접근하는데 필요한 시간을 최소화 하는 방향으로 발전해왔다. 현재의 메모리 구조는 다음과 같다.

 

 

- Secondary Memory (External Memory): Magnetic Disk, Optical Disk, Magnetic Tape으로 구성되어 있으며 I/O 모듈에 의해 접근 가능한 저장 장치이다.

 

- Primary Memory (Internal Memory): Main Memory, Cache memory, CPU registers 로 구성되어 있으며 Processor에서 접근이 가능한 저장 장치이다.

 

 

2. Memory

 

메모리는 기본적으로 address 와 data 로 구성되어 있다.

 

 

CPU와 메모리는 위의 그림과 같이 양방향으로 데이터를 주고받는다. CPU는 주소를 가지고 메인 메모리에 요청을 하거나 해당 주소에 계산 결과를 저장하고, 메모리는 요구하는 주소에 저장되어 있는 데이터를 CPU 에게 전달한다.

 

 

3. 메모리 관리

 

각각의 프로세스는 독립된 메모리 공간을 가지고 OS 또는 다른 프로세스의 메모리 공간에 접근할 수 없는 제한이 걸려있다. OS만이 운영체제 메모리 영역과 사용자 메모리 영역의 접근에 제약을 받지 않는다.

 

- Swapping

 

메모리를 관리하는 기법 중 하나로 메모리에 적재되어 있는 프로세스 중에서 오랫동안 사용하지 않은 프로세스를 프로세스 이미지 형태로 만든 후 하드디스트, 보조 기억장치로 보내고 다른 프로세스의 메모리를 불러 들일 수 있다. 이때 메모리에서 보조 기억장치로 내보내지는 것을 swap-out, 주 기억장치로 불러오는 과정을 swap-in 이라고 한다.

 

swapping은 큰 사이즈의 프로세스를 속도가 느린 하드 디스크에 넣고, 빼는 과정을 수행하기 때문에 오버헤드가 크다. 그렇기 때문에 현재는 메모리가 부족한 경우에 swapping을 진행하거나 하드디스크보다 좀 더 빠른 저장 장치를 사용하기도 한다.

 

- Fragmentation

 

프로세스들이 메모리에 적재되고 제거되는 일이 반복되면서 프로세스들이 차지하는 메모리 틈 사이에 사용하지 못하는 작은 공간들이 생겨난다. 이러한 현상을 메모리 단편화 (Memory Fragmentation) 이라고 부른다.

 

물리 메모리 (RAM) 공간 중에서 프로세스들이 차지하는 틈 사이에 존재하여 사용하지 못하게 되는 부분을 외부 단편화라고 부른다. 반대로 프로세스 내부에서 할당된 메모리 공간 중 사용하지 않고 남아있는 부분을 내부 단편화라고 부른다.

 

외부 단편화를 해결하기 위해서 first-fit, best-fit, worst-fit 등 프로세스와 적합한 메모리 단편을 찾아서 할당하는 방식이나 hole 들을 하나로 모으는 compaction, 압축 등의 방법을 사용한다. 하지만 이러한 방법들은 작업을 진행할 때의 오버헤드가 크고 최적의 알고리즘이 존재하지 않는다는 단점이 있다.

 

 

4. Paging

 

하나의 프로세스가 사용하는 메모리 공간이 연속적이어야 하는 제약을 없애는 메모리 관리 방법. 외부 단편화와 압축 작업을 해소하기 위해 생긴 방법론으로 프로세스를 작은 크기로 나눠서 저장한다.

 

페이징은 프로세스를 일정한 작은 크기로 나누는데 이러한 작은 조각들을 크기에 맞춰 메모리에 할당한다. 하나의 프로세스는 연속적인 동작을 수행하는데, 이를 작은 조각으로 나누어 저장하게 되면 문제가 생기게 된다. 그렇기 떄문에 메모리 상에 흩어져 있는 주소를 연속적으로 가지고 있어서 CPU가 보기에는 프로세스가 연속적으로 저장되어 있는 것처럼 보이도록 해야한다.

 

프로세스를 나눈 조각을 page고 하고 이를 통해 메모리를 나눈 조각을 frame 이라고 한다. CPU 에서 논리 주소를 통해 프로세스의 메모리에 접근하려고 하는 경우 page table을 통해서 페이지의 실제 메모리 주소, 물리 주소로 변경하여 접근해야 한다.

 

페이징 기법을 사용함으로써 논리 메모리는 물리 메모리에 저장될 때 연속적으로 저장될 필요가 없고, 물리 메모리는 남는 프레임에 적절히 배치됨으로 외부 단편화를 해결할 수 있다.

 

 

5. Segmentation

 

페이징에서처럼 논리 메모리와 물리 메모리를 물리적으로 같은 크기의 블록으로 나누는 것이 아닌 서로 다른 크기의 논리적 단위인 segment 로 나누어 메모리에 배치한다. 세그멘테이션은 프로세스를 세그먼트의 집합으로 만들고 세그먼트 테이블에서 세그번흐 번호와 시작 주소 (base), 세그먼트 크기 (limit) 등을 저장한다.

 

세그먼트의 할당과 주소 변환은 페이징과 유사한데 다른 점은 세그먼트의 크기가 페이지의 프레임처럼 일정하지 않다는 것이다. 그렇기 때문에 테이블에 세그먼트의 limit 정보를 가지고 있다. 그리고 CPU 에서 해당 세그먼트 크기를 넘어서는 주소가 들어오면 인터럽트가 발생해서 해당 프로세스를 강제로 종료시킨다.

 

세그먼트의 단점은 외부 단편화가 발생할 수 있다는 것이다. 서로 다른 크기의 세그먼트들이 메모리에 적재되고 제거되는 과정이 반복되면 결과적으로 기존 메모리 관리와 동일하게 외부 단편화가 발생하게 된다.

 

 

6. Virtual Memory

 

가상 메모리는 물리 메모리 크기의 한계를 극복하기 위한 기술이다. 실제 물리 메모리의 크기보다 큰 프로세스가 수행되는 경우에 필요한 부분만 메모리에 적재하는 방식으로 프로세스 전체가 메모리에 적재된 것과 같이 작업을 수행한다. 이때 메모리에 적재되는 프로세스의 일부분은 페이지나 세그먼트 단위가 될 수 있는데, 현재 대부분은 페이지 단위를 사용한다. 이와같이 필요한 페이지만 메모리에 올리는 것을 Demanding Paging 이라고 한다.

 

- Demand Paging (요구 페이징)

 

요구 페이징에서 페이지 테이블은 valid bit 라는 속성을 가지게 된다. 이 값은 현재 메모리에 해당 페이지가 있는지 없는지를 나타내는 비트로 메모리에 존재하는 경우 1, 없는 경우 0을 가지게 된다.

 

만약에 현재 메모리에 적재되지 않은 페이지에 접근하는 경우 page fault 가 발생한다.

 

- Page Fault (페이지 부재)

 

CPU에서 접근할는 페이지가 메모리에 없는 경우 발생한다. 즉 페이지 테이블의 valid bit의 값이 0인 경우이다. 이때는 해당 페이지를 디스크에서 로드해야 하는데, 다음의 순서를 거친다.

 

1. page fault가 발생하면 CPU에 interrupt signal 을 보낸다.

2. OS는 해당 프로세스를 blocked state로 변경시킨다.

3. OS는 요청된 페이지를 논리 주소 영역에서 조회한다.

4. 논리 주소 영역에서 해당 페이지를 찾아서 해당 페이지의 물리 주소로 접근한다.

5. 해당 페이지를 비어있는 프레임에 할당한다. 이때 비어있는 프레임이 없는 경우 페이지 교체 알고리즘에 따라 페이지 교체를 수행한다.

6. 교체된 페이지대로 페이지 테이블이 업데이트 된다.

7. CPU에 신호를 보내어 해당 프로세스를 ready state로 변경시킨다.

 

- 페이지 교체 알고리즘

 

1) FIFO 페이지 교체

• 가장 간단한 페이지 교체 알고리즘으로 FIFO 라는 이름대로 물리 메모리에 먼저 들어온 페이지 순서대로 페이지 교체 시점에 나가게 된다.
• 이해하고 프로그래밍하기 쉬운 반면에 필요한 페이지를 교체할 수도 있다.
• 오래된 페이지가 필요한 정보만을 포함하고 있거나 처음부터 활발하게 사용중인 페이지가 교체되어 페이지 부재율을 높일 수도 있다.
• belady의 모순: 페이지를 저장할 수 있는 페이지 프레임의 개수를 늘려도 되려 페이지 부재가 많아지는 모순

 

2) 최적 페이지 교체 (optimal page replacement)

• belady의 모순을 해결하기 위한 알고리즘. 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아서 교체하는 것이 핵심이다.
• 다른 모든 프로세스의 메모리 참조 계획을 미리 파악할 방법이 없기 때문에 구현의 어려움이 있다.

 

3) LRU 페이지 교체

• Least-Recently-Used, 최적 알고리즘의 근사 알고리즘으로 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체하고 있다.

 

4) LFU 페이지 교체

• Least-Frequently-Used, 참조 횟수가 가장 적은 페이지를 교체하는 방법이다. 활발하게 사용되는 페이지는 참조 횟수가 많아질 거라는 가정에서 만들어진 알고리즘이다.
• 어떤 프로세스가 특정 페이지를 집중적으로 사용하다 다른 기능을 사용하게 되면 더 이상 사용하지 않아도 계속 메모리에 머물게 되어 초기 가정에 어긋나는 시점이 발생할 수 있다.
• 최적 페이지 교체를 제대로 근사하지 못하기 때문에 잘 쓰이지 않는다.

 

5) MFU 페이지 교체

• Most Frequently Used, 참조 횟수가 가장 작은 페이지가 최근에 메모리에 올라왔고, 앞으로 계속 사용될 것이라는 가정에 기반한다.
• 성능이 좋지 않기 때문에 잘 쓰이지 않는다.

 

[reference]

- https://www.geeksforgeeks.org/memory-hierarchy-design-and-its-characteristics/

Memory Hierarchy Design and its Characteristics - GeeksforGeeks