Q6) Memory Fragmentation and its solutions: Paging and Segmentation (Interview Question in OS)

[joey-ful]

메모리의 단편화(Memory Fragmentation) 란 RAM에서 메모리의 빈 공간 또는 자료가 여러 개의 조각으로 나뉘어 수치상으로는 사용 가능한 메모리가 충분함에도 할당이 불가능한 상태를 말합니다.

여기서 질문 😈

👉 👉🏻 👉🏼 👉🏽 👉🏾 👉🏿 메모리의 단편화 중 내부 단편화 (Internal Fragmentation) 와 외부 단편화 (External Fragmentation) 는 무엇인가요?

👉 👉🏻 👉🏼 👉🏽 👉🏾 👉🏿 또한, 단편화를 해결하기 위한 방법으로 페이징(Paging) 과 세그먼테이션(Segmentation) 에 대해 설명해 주세요.

[terry-yes]

즉석)
내부외부 조각: 고정된 사이즈로 메모리를 할당했을때 고정된 사이즈보다 적은 메모리를 필요로하는 프로세스를 할당하면 사용하지 못하는 메모리가 생긱는데 이를 내부외부조각이라고 합니다.
외부내부 조각: 가변식 할당 방식에서 한번 할당되었던 프로세스가 종료되고 다시 그자리에 더 적은 메모리의 프로세스가 할당되면 남는 메모리가 생기는데 이 남은 용량보다 큰 사이즈의 프로세스는 할당되지 않습니다.

페이징: 물리적 메모리를 프레임 단위로 나누고 같은 사이즈만큼 논리적 메모리를 페이지로 나누어서 페이지를 프레임의 올리는 방식을 말합니다. 페이지를 아주 작은 단위로 나누기 때문에 위의 문제점들이 나타나지 않습니다.
마지막 페이지를 적재할 때 외부조각이 나타날 수 있지만 너무 작은 용량이라 크게 문제가 되지 않습니다.

세그먼테이션: 페이징처럼 메모리를 물리적 단위로 나누는 것이 아니라 논리적 단위(아마도 코드, 데이터, 스택영역과 같은)로 나누는 방식을 의미합니다.

[joey-ful]

😈 메모리 단편화 (Memory Fragmentation)

내부 단편화는 내부 조각을 뜻합니다. 하지만 내부 조각이 발생하는 현상을 지칭하는데 사용되기도 하는 것 같습니다. (same with 외부 단편화)

내부 단편화 (Internal Fragmentation)

내부 단편화란 프로세스에게 할당된 메모리에서 사용되지 않고 남는 공간을 뜻합니다.
메모리의 고정 분할 방식에서 분할의 크기보다 작은 프로그램이 적재되는 경우 해당 분할 내에 남는 영역이 발생합니다. 이 때 생기는 빈 공간을 내부 단편화 혹은 내부 조각이라 하며 이는 해당 분할에 올라온 프로그램에 의해서도 사용되지 않고, 다른 프로그램에도 할당될 수 없어 낭비되는 공간입니다.

외부 단편화 (External Fragmentation)

외부 단편화란 메모리가 할당되고 해제되는 반복된 작업으로 프로세스 사이 사이에 남는 공간을 뜻합니다.
메모리의 가변분할 방식은 매 시점 프로그램의 크기에 맞게 메모리를 분할해서 사용하는 방식으로 외부 단편화가 생길 가능성이 있습니다. 새롭게 시작되는 프로그램의 크기가 직전에 종료된 프로그램보다 작을 때, 할당되지는 않았지만 너무 작아 프로그램을 올리지 못하는 빈 공간이 생기는데 이를 외부 단편화 혹은 외부 조각이라고 합니다.

---

😈 메모리 단편화 해결방법

페이징 (Paging)

페이징은 물리 메모리와 논리 메모리를 각각 프레임(Frame)과 페이지(Page)라는 동일한 크기로 나눈 후 페이지를 프레임에 매핑하는 기법입니다.

• 프로세스는 여러 페이지에 나뉘어 저장됩니다
• 프레임과 페이지 크기가 같기 때문에 빈 프레임이 있으면 어떤 위치든 페이지를 적재할 수 있습니다. 이는 메모리 공간이 연속적이어야 한다는 제약을 없앤 것으로, 논리 메모리를 물리 메모리의 남는 프레임에 적절히 배치할 수 있어 외부 단편화를 해결할 수 있습니다.
• 하지만 페이지의 크기는 고정되어 있기 때문에 내부 단편화가 발생할 수 있습니다.
• 또한, 논리 메모리를 물리 메모리에 대응시키기 위해 특정 프로세스의 몇 번 째 페이지가 물리적 메모리의 몇 번째 프레임에 들어 있다는 페이지별 주소 변환 정보를 유지하고 있어야 하며 이를 위해 페이징 테이블이 필요합니다. 페이지 크기를 작게하면 내부 단편화 문제도 해결할 수 있지만 대신 페이지 매핑 과정이 많아져 효율이 떨어집니다.

세그먼테이션 (Segmentation)

세그먼테이션은 프로세스를 서로 다른 크기의 논리적 내용의 단위인 세그먼트(segment), 즉 프로세스의 코드, 데이터, 스택 등의 기능 단위 또는 의미 단위로 나눈 후 물리 메모리에 할당하는 기법입니다.

• 물리 메모리를 세그먼트라는 논리적 단위, 프로세스가 딱 필요로 하는 크기로 할당하기 때문에 내부 단편화를 해결할 수 있습니다.
• 세그먼트들의 크기가 달라 미리 분할해둘 수 없으므로 물리 메모리에 연속적으로 적재되며, 적재될 때마다 빈 공간을 찾아 할당합니다. 따라서 외부 단편화가 발생할 수 있습니다.
• 논리 메모리를 물리 메모리에 대응시키기 위해 세그먼트 번호, 물리적 메모리에서 세그먼트의 시작 주소와 세그먼트 길이 정보를 유지하고 있어야 하며 이를 위해 세그먼트 테이블이 필요합니다.

---

보너스

👉 👉🏻 👉🏼 👉🏽 👉🏾 👉🏿 가상 메모리와 요구 페이징은 무엇인가요?

[joey-ful]

가상 메모리

프로그램 실행에 필요한 메모리 용량 전체를 물리 메모리인 RAM에서 할당받는 것이 아니라 최소한의 메모리만 RAM에서 할당받고 나머지는 논리 메모리인 HDD에 저장하는 것을 가상 메모리라 합니다. 가상 메모리는 프로그램이 물리 메모리보다 커져도 되며 더 많은 프로그램을 동시에 수행할 수 있다는 장점이 있습니다.

요구 페이징

프로그램이 필요로 하는 페이지가 물리 메모리에 없을 경우를 페이지 폴트라 하는데, 페이지 폴트가 발생하면 운영 체제는 가상 메모리에서 해당 페이지를 찾아 물리 메모리의 불필요한 페이지와의 교체를 요구합니다. 요구 페이징이 발생할 때 교체할 물리 페이지를 선정하는 페이지 교체 알고리즘은 다음과 같습니다.

1. FIFO (First In First Out): 물리 메모리에 적재된지 가장 오래된 페이지를 교체합니다. 페이지의 사용 빈도를 무시하기 때문에 활발하게 사용하는 페이지가 교체될 수 있다는 문제점이 있습니다. 페이지가 적재된 순서를 Queue에 저장하는 방식을 사용합니다.
2. LRU (Least Recently Used): 가장 오랜 기간 사용되지 않은 페이지를 교체합니다. 많은 운영체제가 사용하는 알고리즘이라고 합니다.
3. LFU (Least Frequently Used): 참조 횟수가 가장 적은 페이지를 교체합니다. 교체 대상이 여러 개일 경우에 사용됩니다. LFU는 한 페이지가 초기에만 집중적으로 참조되다가 이후에 참조되지 않는 경우, 메모리에 계속 남을 가능성이 크다는 문제점이 있습니다.
4. MFU (Most Frequently Used): LFU와 반대로 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘입니다.