OS의 메모리관리

메모리 관리

단일 프로그램만 쓰는 것이 아니라 다수의 프로세스를 수용시켜야 하기 때문에

이를 어떻게 메모리에 적재할 것인지 따져야 한다.

 

메모리 할당

메모리는 일반적으로 두 영역으로 나뉜다.

1. OS 상주 영역(커널)
2. 사용자 프로세스 영역
   1. 연속 할당: 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
      • 고정 분할 방식(fixed partition allocation)
      • 가변 분할 방식(variable partition allocation)
   2. 불연속 할당: 프로세스를 구성하는 주소 공간을 쪼개서 메모리의 여러 영역에 분산시켜 올리는 기법
      • 페이징(paging)
      • 세그먼테이션(segemtation)

 

메모리 단편화

내부 단편화

프로세스가 사용하는 메모리 공간 중 남는 부분

프로세스가 요청한 양보다 더 많은 메모리를 할당할 때 발생함

 

외부 단편화

메모리 공간 중 사용하지 못하게 되는 부분

종료된 프로그램이 반환한 메모리 크기가 새로운 프로그램의 크기보다 작으면 그곳에서 새로운 프로그램을 실행하지 못한다. 이런 이유로 메모리 공간 내에 다양한 크기의 빈 공간이 생기고, 이를 hole이라고 한다.

 

연속 할당

고정 분할 방식

• 물리적 메모리를 미리 똑같은 크기, 개수로 분할하는 방식. 미리 분할해서 그 곳에 프로그램을 올린다.
• 외부 단편화, 내부 단편화 발생 가능

가변 분할 방식

• 프로그램의 크기를 고려하여 메모리에 할당. 분할의 크기, 개수가 동적으로 변할 수 있다.
• 외부 단편화 발생 가능

 

불연속 할당

페이징 - 외부 단편화 해결

1. 물리적 메모리를 동일한 크기의 프레임으로 나누고,
2. 논리적 메모리를 동일한 크기의 페이지(프레임과 크기가 같음)로 나눈다.
3. 각 페이지에 해당하는 프레임을 매핑 시켜주는 페이지 테이블 이라는 공간을 메인 메모리에 따로 둔다.
4. 이것을 이용하여 논리적 주소를 물리적 주소로 변환한다.

이 때, 페이지 테이블에서 빈번히 접근되는 엔트리를 캐싱하는 TLB를 통해 논리적 주소를 물리적 주소로 변환시키는 시간을 절약시킬 수 있다.

 

세그먼테이션

프로세스를 서로 크기가 다른 논리적 단위인 세그먼트로 분할하여 메모리에 적재하는 방식

 

Demand Paging

프로세스가 실제로 페이지를 필요로 할 때 물리 메모리에 올리는 것을 demand paging이라고 한다.

• I/O 양의감소
• 메모리 사용량 감소
• 빠른 응답시간
• 더 많은 수용자 수용

 

Page Fault

페이지 테이블에는 invalid bit가 존재한다.

• 프로세스에서 사용 되지 않는 주소 영역인 경우
• 페이지가 물리적 메모리에 없는 경우(디스크에 스왑된 경우)

주소 변환시에 엔트리에 invalid bit가 세팅되어있다면, 이것을 page fault라고 부른다.

1. 허용되지 않은 주소로 접근한다. (limit를 넘거나 하는 요청)
2. 프로세스를 종료시킨다.
3. 그렇지 않다면, 페이지가 디스크에 스왑 되어 있는 것으로 우선 빈 페이지 프레임을 하나 획득한다.
4. 빈 페이지 프레임이 없다면 다른 프로세스로부터 뺏어온다.
5. 해당 페이지를 디스크에서 메모리로 읽어온다.디스크 I/O가 끝나면 페이지 테이블의 엔트리의 valid-invalid bit를 valid로 바꿔준다.
6. 디스크 I/O가 끝나기까지 이 프로세스는 cpu를 다른 프로세스에게 선점당한다. (block)
7. 이 프로세스가 cpu를 잡고 다시 running한다.
8. 아까 중단되었던 instruction을 재개한다.

 

페이지 교체 알고리즘

page fault 발생 시, 만약 빈 페이지 프레임을 획득하지 못 하면 다른 프로세스로부터 뺏어온다.

이 때 어떤 프레임을 뺏어올지 결정하기 위한 알고리즘이 필요하다.

이 알고리즘은 page fault rate를 최소화하는 것을 목적으로 한다.

 

FIFO

먼저 들어온 페이지를 먼저 내쫓는 알고리즘

프레임 갯수를 늘렸는데 page fault가 오히려 더 늘어날 수 있다. 즉, 프레임을 늘린다고 page fault가 적어지는 것을 보장할 수 없다.

 

LRU & LFU

LRU는 가장 오래 전에 참조된 페이지를 지우는 알고리즘이다.

LFU는 참조 횟수가 가장 적은 페이지를 지우는 알고리즘이다.

 

LRU는 큐를 사용하면 된다. 이미 존재하는 페이지는 참조될 때마다 head로 보내고, 새로운 페이지가 들어오면 tail의 페이지를 삭제하고 head에 페이지를 넣는다.

LFU는 참조 횟수의 오름차순으로 페이지를 리스트에 넣은 다음에, page fault가 발생하면 head에 있는 페이지를 삭제한다. 그리고 만약 존재하는 페이지가 참조되면 그 페이지의 참조 횟수를 1 늘리고, 올바른 위치에 다시 정렬시킨다. 다만 이렇게 비교해야하기 때문에 O(n)이라는 시간이 걸린다.

따라서 힙을 이용한 알고리즘을 사용하기도 한다. 이렇게 구현하면 O(log n)의 시간이 걸린다.