[OS] Memory Management

Segmentation

*Segment: 프로세스의 메모리를 논리적으로 나눈 단위

 

세그멘테이션은 프로세스를 여러 세그먼트 또는 파티션으로 나누는 메모리 관리 기법이다. 각 세그먼트는 Code(read only), Data, Bss, Stack과 같은 프로그램의 다른 부분을 나타내며, 크기가 다를 수 있다. 이 기법은 세그먼트를 비연속적으로 물리 메모리에 할당할 수 있어 연속적인 메모리 할당의 필요성을 줄인다. 다만, 각 세그먼트 내부는 연속적으로 할당되어야 한다.

 

세그멘테이션의 주요 장점 중 하나는 가변 크기 세그먼트를 사용하여 내부 단편화를 줄일 수 있다는 점이다. 이는 세그먼트가 동적으로 성장하거나 축소될 수 있어 내부 단편화를 최소화할 수 있음을 의미한다. 또한, 세그멘테이션은 각 세그먼트를 독립적으로 스와핑할 수 있어 유연한 메모리 관리가 가능하다. 이러한 특징 덕분에 세그멘테이션은 다양한 크기의 세그먼트를 효과적으로 관리할 수 있어 프로그램의 효율성을 높일 수 있다.

 

하지만 세그멘테이션에는 단점도 있다. 우선, 세그먼트 크기가 다양해지면 메모리 할당이 복잡해질 수 있다. 다양한 크기의 세그먼트를 관리하기 위해 메모리 할당 알고리즘이 복잡해지며, 이는 시스템 자원을 많이 소모할 수 있다. 또한, 세그멘테이션은 외부 단편화를 초래할 수 있다. 외부 단편화란 작은 비연속 블록으로 자유 메모리가 분산되는 현상으로, 이는 세그먼트 성장을 위한 연속적인 자유 메모리를 확보하기 어렵게 만든다.

 

세그먼트 확장을 할때, 해당 세그먼트 위 공간이 비어있으면, limit를 업데이트하여 확장한다. 하지만, 만일 빈 공간이 없다면, 해당 세그먼트를 swap out하고, 더 큰 빈 공간으로 swap in한다. 또한 연속적인 자유 메모리가 필요하기 때문에 빈번한 메모리 압축이 필요할 수 있으며, 이는 성능 오버헤드를 초래할 수 있다. 따라서 세그멘테이션을 효과적으로 사용하기 위해서는 이러한 단점들을 고려한 효율적인 메모리 관리 전략이 필요하다.

 

Segment Table

: 세그멘테이션 메모리 관리 기법에서 각 세그먼트의 정보를 저장하는 자료 구조이다.

Base Register를 통해 가상 주소가 물리 주소로 번역되며, Limit Register를 통해 프로그램이 세그먼트의 범위를 초과하는 메모리에 접근하지 않도록 하여 메모리 접근의 안전성을 높인다.

 

Virtual Address는 seg + offset 형태로, 세그먼트를 식별하고 세그먼트안에서의 특정 byte를 나타낸다.

 

---

Paging

*page: Virtual Address Space의 작은 고정 크기의 Partition

*frame: Physical Address Space의 작은 고정 크기의 Partition

 

페이징은 프로세스의 논리 메모리를 고정 크기의 페이지로 나누고, 물리 메모리를 동일한 크기의 프레임으로 나누는 기법이다. 페이지는 프레임에 매핑되며, 이를 통해 하나의 세그먼트를 구성하는 page들도 물리 메모리에 비연속적으로 할당할 수 있다. 페이지 테이블은 메모리 관리 유닛(MMU)에 의해 유지되며 page-frame 매핑을 추적한다.

 

페이징의 주요 장점 중 하나는 고정 크기 페이지를 사용하여 메모리 할당과 관리를 단순화할 수 있다는 점이다. 또한, 페이지 크기가 고정되어 있어 외부 단편화가 발생하지 않는다. 페이지를 독립적으로 스와핑할 수 있어 메모리 관리가 효율적이다.

 

하지만 페이징에는 단점도 있다. 고정 크기 페이지는 페이지가 완전히 사용되지 않을 경우, 내부 단편화를 초래할 수 있다. 또한, 큰 프로세스는 많은 페이지 테이블이 필요해 메모리 오버헤드를 증가시킬 수 있고, 특히 컨텍스트 스위칭 시 오버헤드가 발생할 수 있다. 페이지 테이블이 커서 일부 항목은 disk에, 일부는 main memory에, 일부를 TLB에 넣기도 한다.

 

Page Table

: 페이징(Paging) 메모리 관리 기법에서 각 페이지의 정보를 저장하는 자료구조로, 논리 주소를 물리 주소로 변환하는 데 사용된다.

 

Virtual Address는 page + offset 형태로, page를 식별하고, page에서의 특정 byte 위치를 나타낸다.

Virtual Address의 page는 page table을 통해 Physical Address의 frame으로 변환된다.

페이징에서는 페이지 테이블의 유효 비트(valid bit) 등을 통해 page의 유효성을 확인하기에 paging에서는 limit register가 필요가 없다. frame의 유효성은 bit map을 통해 확인할 수 있다.

---

Segmentation과 Paging

 

현대의 메모리 관리 시스템에서는 두 단계의 매핑을 사용하여 메모리를 보다 효율적으로 관리한다. 먼저, 프로세스를 가변 크기의 세그먼트로 나누고, 각 세그먼트를 다시 수많은 고정 크기의 페이지로 나눈다. 이러한 구조에서는 가상 주소(Virtual Address)가 세그먼트 번호(seg), 페이지 번호(page), 그리고 오프셋(offset)으로 구성된다.

 

가상 주소의 변환 과정은 다음과 같다. 우선, 가상 주소의 세그먼트 번호(seg)를 이용해 세그먼트 테이블(Segment Table)에서 해당 세그먼트의 시작 주소(Base Address)와 한계(Limit)를 찾는다. 이를 통해 해당 세그먼트가 메모리에 유효한지 확인한 후, 세그먼트 시작 주소와 페이지 번호(page)를 결합하여 해당 세그먼트 내의 페이지 테이블(Page Table)에 접근한다.

각 세그먼트는 고유한 페이지 테이블을 가지며, 페이지 테이블은 각 페이지 번호를 물리 메모리의 프레임 번호로 매핑하는 역할을 한다. 페이지 번호를 사용하여 페이지 테이블에서 해당 페이지의 프레임 번호를 찾아낸 후, 프레임 번호와 오프셋(offset)을 결합하여 최종 물리 주소(Physical Address)를 계산한다.

 

이 두 단계 매핑 기법의 주요 장점은 메모리 관리를 더욱 유연하고 효율적으로 할 수 있다는 점이다. 프로세스는 각기 다른 크기의 세그먼트로 나누어지며, 각 세그먼트는 동일한 크기의 페이지로 나뉘어 관리된다. 이러한 방식은 외부 단편화를 최소화하고, 메모리 할당과 해제를 보다 효율적으로 처리할 수 있게 한다. 또한, 세그먼트와 페이지를 독립적으로 스와핑하거나 교체할 수 있어 메모리 관리의 유연성을 높인다.

 

결과적으로, 프로세스는 하나의 세그먼트 테이블과 여러 개의 페이지 테이블을 가지고, 이를 통해 가상 주소를 물리 주소로 변환하는 복잡한 과정을 처리한다. 이 구조는 현대 컴퓨터 시스템에서 메모리 관리의 효율성과 성능을 향상시키는 데 중요한 역할을 한다.

---

TLB (Translation Lookaside Buffer)

TLB(Translation Lookaside Buffer)는 가상 주소를 물리 주소로 변환하는 과정에서 페이지 테이블에 접근하는 시간을 단축하기 위해 사용되는 고속 캐시 메모리이다. TLB는 자주 사용되는 페이지 테이블 항목(page number: frame number)을 저장하여, 가상 주소를 물리 주소로 변환할 때 페이지 테이블을 직접 조회하는 대신 TLB를 먼저 참조함으로써 주소 변환 시간을 크게 줄일 수 있다. TLB 미스가 발생하면 페이지 테이블에 접근하여 필요한 항목을 가져오고, TLB에 해당 항목을 저장한 후 주소 변환을 진행한다. 만일, 페이지 테이블이 메인 메모리가 아닌 디스크에 있었다면, 페이지 폴트가 발생할 것이다. 이 경우, 페이지 폴트 처리 단계를 따라 필요한 페이지를 메인 메모리로 가져와야 한다.

---

Demand Paging

 

실행되는 프로세스의 모든 페이지를 전부 물리 메모리(RAM)에 올리는 것은 매우 비효율적일 뿐만 아니라, RAM의 용량이 작거나 프로그램의 크기가 커서 불가능한 경우도 존재했다. 따라서, 메모리를 효율적으로 관리하기 위해 실행 중인 프로그램이 실제로 사용하는 부분만 메모리에 올리고, 사용되지 않는 부분은 디스크에 유지하는 방식이 필요했다.

 

Locality of reference(옆 사진)을 보면, 특정 시간에 특정 메모리 주소만 필요로 한다는 것을 알 수 있다. 따라서 각 페이지가 필요할 때마다 디스크에서 물리 메모리(RAM)로 적재하는 방식이 효과적이다. 이 방식은 초기 로딩 시 프로그램 전체를 메모리에 올리는 대신, 실제로 접근이 발생하는 페이지들만 메모리에 올리기 때문에 메모리 사용 효율을 높일 수 있다. 또한, 초기 로딩 시간을 단축하고, 자주 사용되는 페이지들만 메모리에 유지함으로써 멀티태스킹 환경에서 성능을 최적화할 수 있다.

 

동작 과정

초기에 Main Memory에는 해당 프로세스의 Page가 없다. 그래서 초반에는 많은 Page Fault를 발생시키게 되고, 이로 인해 잠시 느려질 수 있다.

Page Fault 발생, 처리 과정

: 필요한 데이터를 물리 메모리에 로드하고, 프로그램이 정상적으로 실행을 계속할 수 있도록 한다.

1. 참조(reference): 프로세스가 메모리 주소 M을 참조하려고 시도한다. 이 시점에서 페이지 테이블을 참조하여 vaild bit을 통해 해당 페이지가 물리 메모리(ram)에 있는지 확인한다.
2. 트랩(trap): 참조한 페이지가 현재 물리 메모리에 없으면 페이지 폴트가 발생하여 트랩이 걸리며 프로세스는 sleep한다. 운영 체제에 제어권이 넘어가고, page fault 처리를 시작하게 된다.
3. 백킹 스토어에서 페이지 검색: 운영 체제가 페이지 폴트를 처리하기 위해 필요한 페이지가 백킹 스토어(일반적으로 disk)에 있음을 확인한다. 이 단계에서는 디스크에서 해당 페이지를 찾는다.
4. 누락된 페이지를 가져옴: Loader(=pager. kernel proc2)는 백킹 스토어에서 누락된 페이지를 찾아 물리 메모리의 빈 프레임에 적재한다(loading). 이때, bit map을 통해 빈 frame을 찾아 시간을 절약한다. 이 과정은 디스크 I/O를 포함하며, 시간이 걸릴 수 있다.
5. 페이지 테이블 리셋: 페이지 테이블을 업데이트하여 새로 가져온 페이지의 위치를 반영한다. 즉, 해당 페이지의 프레임 번호를 페이지 테이블에 기록하고, vaild bit을 1로 갱신한다.
6. 명령 재시작(restart instruction): 마지막으로, 페이지 폴트를 유발한 명령을 재시작한다. 이제 해당 페이지가 물리 메모리에 존재하므로, 명령이 정상적으로 실행될 수 있다. ⇒ Transparency

이로써 프로세스는 Transparency로 인해 메모리가 무한한 것과 같은 환상을 느끼게 된다.

 

---

Prepaging (↔ Demand Paging)

Demand paging과 반대로, 시작할 때 필요한 만큼의 페이지를 미리 물리 메모리(Physical Memory)에 적재하는 방법이 있다. Locality of Reference(참조의 지역성) 개념을 통해 주로 사용되는 페이지들이 존재하며, 이들은 시간적/공간적 지역성이라는 특징을 갖기 때문에 필요한 페이지들을 어느 정도 예측할 수 있다. 그러나 예측하여 페이지를 적재했지만 실제로 사용되지 않으면, Memory Pollution이 발생할 수 있다.

---

Page Replacement

페이지 교체(Page Replacement)는 물리 메모리(Physical Memory)가 가득 차서 새로운 페이지를 메모리에 로드할 공간이 없을 때, 기존의 페이지 중 하나를 디스크로 스왑 아웃하고 새로운 페이지를 로드하는 메모리 관리 기법이다. 즉, main memory에 남는 frame이 없는데, page fault가 발생하면, swapping을 하는 page replacement가 실행된다.

page 교체 알고리즘

• Random: 무작위의 페이지를 교체한다.
• FIFO (First-In, First-Out): 가장 먼저 메모리에 들어온 페이지를 가장 먼저 교체한다. 단순하지만, 최신 참조 정보를 고려하지 않기 때문에 효율적이지 않을 수 있다.
• Optimal: 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체한다. 이론적으로 가장 효율적이지만, 실제로 구현하기 어려운 알고리즘이다.
• LRU (Least Recently Used): 가장 오랫동안 참조되지 않은 페이지를 교체한다. 최근에 사용된 페이지는 앞으로도 사용될 가능성이 높다는 가정을 바탕으로 한다.

효율적인 페이지 교체 알고리즘을 사용하면 메모리 사용 효율이 높아지고, 페이지 폴트 빈도가 줄어들어 시스템 전체 성능이 향상된다. 반대로 비효율적인 알고리즘은 자주 페이지 폴트를 발생시켜 디스크 I/O 오버헤드를 증가시키고, 시스템 성능을 저하시킬 수 있다.

*modified/dirty bit: 해당 페이지가 메모리에 적재된 이후에 수정되었는지를 나타내는 플래그이다. 수정이 되었다면, disk에 데이터를 저장해야 하지만, 수정되지 않은 page는 그대로 폐기해도 된다. 이를 통해 디스크 I/O 작업을 최소화할 수 있고, 페이지가 교체될 때 더러워진(수정된) 페이지는 반드시 디스크에 기록되어 데이터 일관성을 유지할 수 있다.

 

---

Thrashing

과도한 multi tasking으로 인해 free frame 이 부족해지면 페이지 폴트가 빈번하게 발생하고, 그로 인해 CPU가 프로세스를 처리하는 시간보다 page replacement하는 시간이 더 많아져 CPU 이용률이 급격히 떨어지는 현상이다. Thrashing은 시스템 성능을 심각하게 저하시킬 수 있으며, 이를 방지하기 위해 Working Set 개념을 사용한다.

Working Set

워킹 셋은 참조의 지역성(Locality of Reference)을 기반으로, 일정 시간 동안 실행되는 프로그램이 자주 참조하는 페이지의 집합을 말한다. 이 워킹 셋을 메모리에 적재해두면, 페이지 교체를 최소화하여 Thrashing을 방지하고 시스템의 전반적인 성능을 최적화 할 수 있다.