메모리 할당 기법

• 연속할당
  • Uni Programming
  • Multi Programming (주기억장치 분할)
    • 고정분할(같은크기)
    • 가변분할(다른크기)
• 비연속할당
  • Multi Programming (가상메모리 분할)
    • 페이징
    • 세그먼테이션
    • 페이징/세그먼테이션 혼용

단편화

주기억장치 상에서 빈번하게 기억장소가 할당되고 반납됨에 따라 기억장소들이 조각들로 나누어져 사용하지 못하는 공간

내부 단편화

메모리를 할당하는 단위가 정해져 있는 경우(ex 고정분할, 페이징)에 할당된 단위보다 적은 용량의 프로그램이 적재되어 실행 될 때 낭비되는 공간이 발생하는 경우를 말한다. 예를 들어 빈 공간이 500MB일때 300MB메모리를 사용하는 프로그램을 실행한다고 하면 200MB의 낭비가 생긴다.

외부 단편화

주기억장치 상에서 빈번하게 기억장소가 할당되고 반납됨에 따라 여유 빈 공간이 여러 조각으로 나뉘게 되고 이 공간들을 합치면 요구되는 공간을 할당 할 수 있음에도 불구하고 연속적인 공간이 아니라서 할당하지 못하는 상황. 고정분할, 가변분할, 세그먼테이션 기법에서 발생한다.

해결방법

1. 인접한 빈 공간을 합쳐서 큰 빈 공간을 만든다. (304호, 305호, 306호가 비어있을 때 이 집들 사이의 벽을 허무는 것)
2. 빈 공간을 한곳으로 모은다. 일종의 Garbege collection. 부하가 클 수 있다. (304호, 308호가 비어있을 때 304호를 308호 근처로 교체해서 큰 빈 공간을 만드는 셈이다.)
3. 가상메모리를 이용하는 기법 (페이징, 세그먼테이션)

페이징

가상기억장치를 모두 같은 크기의 블록으로 편성하여 운용하는 기법

**<용어 정리="">**

1. 보조기억장치인 가상기억장치(=가상메모리)에 저장된 프로그램을 주기억장치에 올리고 cpu가 프로그램을 작동시킨다.
2. 가상메모리를 일정한 크기로 나눈 블록을 페이지라고 한다. 4K씩 나눌수도 있고 5K씩 나눌 수도 있다.
3. 주기억장치를 일정한 크기로 나눈 블록을 프레임이라고 한다. 이 또한 나누는 크기는 달라질 수 있다.
4. 가상메모리에 있는 페이지를 주기억장치에 올리는 것을 Page-In(Swap-In)이라 하고 주기억장치에 있던 것을 다시 가상메모리로 되돌리는 것을 Page-Out(Swap-Out)이라 한다.
5. Page-In, Page-Out과 같은 과정을 페이지 교체 알고리즘에 따라 수행되는데 이를 Swapping이라 한다.
6. 페이지 사상테이블(매핑) : 프로세스의 페이지 정보를 저장하고 있는 테이블이다. 하나의 프로세스는 하나의 페이지 테이블을 가진다. 페이지번호, 페이지가 주기억장치에 적재되었는지 여부, 주기억장치 상에서의 시작주소가 저장된다.
7. cpu가 프로그램을 실행하던 와중에 필요한 페이지가 주기억장치에 없는 상황을 Page Fault라고 하고 페이지 테이블을 확인하여 페이지 교체가 일어난다. 그리고 Page Fault를 해결하는 과정을 Demand Paging이라 한다.
8. 프레임 단위가 4K이고 페이지가 3K일 경우 1K의 내부단편화가 발생한다.
9. 스래싱 : Page Fault로 인한 성능다운을 의미
10. 페이지크기가 클수록 1개를 읽는 시간은 오래 걸릴지 몰라도 총 시간은 줄어들 수 있다.

쉬운 설명 : 보조기억장치에 저장된 ‘색깔’이란 이름의 프로그램은 주기억장치에 모두 올리기엔 공간이 부족하다. 그래서 보조기억장치 상에서 ‘색깔’이라는 이름의 프로그램을 ‘빨’,’주’,’노’,’초’,’파’,’남’,’보’로 쪼갠다. 그리고 커다란 강당과 같던 주기억장치 또한 101호, 102호, 103호,,,, 등의 공간으로 나눈다. 페이징이란 ‘빨’,’주’를 101호, 102호에 넣고 일단 프로그램을 실행한다. 그리고 실행되던 중 ‘노’가 필요하면 그때 ‘노’를 주기억장치 속 빈 방에 이동시키고 프로그램을 계속 실행한다. 대신에 누가 어느 방에 들어갔는지 확인해야 하기 때문에 페이지 사상테이블도 필요하다.

페이지 교체 알고리즘

1. FIFO(first in first out) : 메모리에 올라온 지 가장 오래된 페이지를 교체
2. Optimal : 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체
3. LRU(least-recently-used) : 가장 오래 사용되지 않은 페이지를 교체
4. Counting-Based : 페이지 참조 시마다 각 페이지가 현재까지 참조된 횟수를 카운팅하는 방법. 이를 이용해 2가지의 알고리즘을 만들 수 있다. ==> LFU와 MFU는 실제 사용에 잘 쓰이지 않음 (비용문제, LRU보다 못하다.)
   1. LFU(least-frequently-used) : 참조 횟수가 가장 작은 페이지를 교체. 만약 교체대상이 여러개일 경우, LRU에 따른다.
   2. MFU(most-frequently-used) : 참조 횟수가 가장 많은 페이지를 교체. 횟수가 적은 페이지가 최근에 사용된 것이기 때문에 앞으로 사용될 가능성이 높다는 판단.

세그먼테이션

가상기억장치를 가변적인 크기의 블록으로 편성하여 운용하는 기법. 가상기억장치의 블록의 크기가 제각각이므로 대신 주기억장치의 영역 구분을 없앤다. 그리고 각 블록에 Protection Key라는 이름표를 달아 준다.

• 프레임이 없기 때문에 내부단편화가 발생하지 않으나 외부단편화가 발생한다. 그래서 주기적으로 압축이 필요하다.
• 세그먼테이션 기법을 사용하는 가장 큰 이유는 메모리를 효율적으로 관리하기 위해서다. 예를 들어 실제로 필요한 기능이 300MB일때 페이지크기 단위가 400MB라면 필요 없는 100MB부분도 주기억장치에 올려야 하고, 이 때문에 시간, 공간적으로 비효율적이기 때문이다.
• 페이징 기법에 비해 물리적 개념보다는 논리적이란 장점이 있다.
• 세그먼트의 길이가 모두 달라서, 세그컨트 길이에 맞는 주기억장치의 영역을 할당하지 못하면 다른 프로그램 영역을 침범하게 되는 세그먼트 오버플로우 결함이 발생한다. (= 스택 세그먼트가 넘치거나 힙 세그먼트에 의해 침범 당하면 스택 오버플로우)

Paged Segmentation 기법

• Segmentation을 수행하고 각 Segment별로 paging을 수행한다
• 페이지-세그먼트 매핑 테이블이 필요
• 주소변환을 2번 해야 한다. 속도저하가 생길 수 있다.

참고

태양정복 스터디 발표자 한OO

https://codemcd.github.io/study/OperatingSystem-14%EC%9E%A5-%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%85%8C%EC%9D%B4%EC%85%98/ [운영체제] # 14 세그먼테이션(Segmentation)

https://devs-trashcan.tistory.com/24 Paged Segmentation

https://medium.com/pocs/%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-page-replacement-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-650d58ae266b 페이지 교체(page-replacement) 알고리즘