메모리 할당 알고리즘, 페이지 폴트, 단편화

5. 메모리 할당 알고리즘 (First fit, Next fit, Best fit) 결과에 대해 설명해보세요

메모리의 처음부터 탐색하기 시작해서, 크기가 충분한 첫 번째 메모리에 할당하는 First fit,
마지막으로 참조한 메모리 공간부터 탐색을 시작해서 메모리를 할당하는 Next fit,
모든 메모리 공간을 검사해서 내부 단편화를 최소화 하는 공간에 할당하는 Best fit이 있습니다.

5-1. 메모리 할당 알고리즘의 필요성 (가변 배치 전략)

OS가 제공하는 다중 프로그래밍 환경 내에서 / 다양한 프로그램들이 메모리 공간을 불규칙적으로 사용, 반환합니다.
이러한 불규칙적인 공간 중 프로세스에게 할당해 줄 메모리 공간을 선택하기 위해 메모리 할당 알고리즘이 필요합니다.

5-2. 각 알고리즘의 장단점이 있다면?

First-fit : 가장 간단하고 빠르지만, 공간 활용률이 떨어질 수 있습니다.
Next-fit : first-fit에 보다는 느리지만, 빠른 속도가 장점이다, 일반적으로 메모리 공간의 끝에 있는 가장 큰 크기의 메모리를 짧은 시간내에 작은 크기로 조각내서 메모리 집약작업이 추가적으로 필요하다.
Best-fit : 공간 활용률이 높아진다는 장점이지만, 가용 메모리가 크기 순으로 정렬되어있지 않으면 메모리 검색 시간이 늘어난다.

---

6. 페이지 폴트에 따른 페이지 교체 알고리즘에 대해 설명해주세요

OPT(Optimization) : 가장 오랫동안 사용하지 않을 페이지를 예측하여 교체하는, 최적화 방식
FIFO(First In First Out) : 메모리가 할당된 순서대로 페이지를 교체하는 방식
LRU(Least Recently Used) : 최근에 가장 오랫동안 사용하지 않은 페이지를 교체
LFU(Least Frequently Used) : 사용 빈도가 가장 적은 페이지를 교체
NUR(Not Used Recently) : 최근에 가장 사용하지 않은 페이지를 교체

6-1. 페이지 폴트란 무엇인가?

운영체제의 스와퍼(Swapper)는 메모리에 동작하고 있는 프로세스 중에서 실제로 필요한 프로세스만 로드하고, 페이저(Pager)는 프로세스의 필요한 페이지만 로드합니다.
따라서 필요한 페이지가 물리 메모리에 부재할 수 있는 시점이 있는 데, 이 때를 페이지 폴트라 합니다.

6-2. 페이지 폴트의 해결과정

필요한 페이지가 없는 것을 해결하기위해 요구를 합니다. 이를 Demand Paging이라하는데,
페이지 폴트가 발생하면 CPU에서 trap을 발생시켜 OS에 알립니다.
OS에서는 interrupt를 발생시키고 주소 값과 Valid bit가 있는 Page Table을 통해
필요한 페이지가 있는 지 확인합니다. 없으면 프로세스를 종료하고, 있으면 물리 메모리에 비어있는 프레임을 찾습니다.

이 때 비어있는 프레임이 없으면 페이지 교체 알고리즘을 통해 페이지를 교체하고,
페이지가 있으면 그 공간에 로드합니다.

---

7. 단편화란 무엇인가?

• RAM에서 메모리의 공간이 조각으로 나뉘어져, 사용 가능한 메모리가 충분히 존재하지만 할당할 수 없는 상태

7-1. 내부 단편화

• 프로세스가 필요한 양보다 더 큰 메모리가 할당되어, 할당된 메모리 내의 공간이 낭비되는 상황

7-2. 외부 단편화

• 총 사용 가능 메모리 공간은 충분하지만, 비연속적으로 존재하여 프로세스에 대한 할당이 불가능한 상황