포스트

[OS] 메모리 할당과 단편화

게시 업데이트
By Jangan Lee 읽는 시간  13분

1. Memory Allocation

  • 운영체제가 새 프로세스를 실행시키기거나 실행 중인 프로세스가 메모리를 필요로 할 때, 물리 메모리를 할당해주어야 함
    • 프로세스의 실행은 할당된 물리 메모리에서 이루어짐
    • 프로세스의 코드(함수), Data, Heap, stack등
  • 메모리는 어디에, 어떻게 할당해야 하는 것인가? 많은 방법이 있음

1. Memory Allocation

1.1. 메모리 할당 기법

1.1. 메모리 할당 기법

1.1.1. 연속 vs 불연속: Process partitioning

  • 연속
    • 프로세스가 메모리 내에 인접되어 연속되게 하나의 블록을 차지하도록 배치
  • 불연속(분산)
    • 프로세스가 페이지나 세그먼트 단위로 나뉘어 분산 배치되는 방법

1.1.2. 가변 vs 고정: Memory partitioning

  • 가변
    • 프로세스의 크기에 맞게 메모리가 분할
    • 메모리의 영역이 각각 다름
  • 고정
    • 프로세스의 크기에 상관없이 메모리가 같은 크기로 나뉨
    • 큰 프로세스가 메모리에 올라오면 여러 조각으로 나누어 배치

1.1.2. 가변 vs 고정

2. 연속 메모리 할당

  • 각 프로세스의 영역(코드와 데이터)을 연속된 메모리 공간에 배치
  • 메모리를 한 개 이상의 파티션으로 분할하고 파티션을 할당하는 기법
  • 한 프로세스는 한 파티션으로 할당

2.1. 고정 크기(fixed size partition) 할당

  • MFT(Multiple Programming with a Fixed Number of Tasks)
    • 메모리 전체를 고정 크기의 n개로 분할. 프로세스마다 하나씩 할당. 수용가능 프로세스의 수 n 고정

2.1. 고정 크기 할당 0

  • 내부 단편화 발생(외부 단편화일 수도 있음 밑에 내용으로 확실히 하자)

2.1. 고정 크기 할당

2.2. 가변 크기(variable size partition) 할당

  • MVT(Multiple Programming with a Variable Number of Tasks)
  • 프로세스마다 가변 크기로 연속된 메모리 할당. 수용가능 프로세스 수 가변
    • 메모리가 없을 때, 프로세스는 큐에서 대기연속 메모리 할당은 초기 운영체제에서 사용

2.1. 가변 크기 할당 0

  • 외부 단편화 발생(내부 단편화일 수도 있음 밑에 내용으로 확실히 하자)

2.2. 가변 크기 할당

2.3. 연속 메모리 할당 구현

  • 하드웨어 지원
    • base 레지스터, limit 레지스터, 주소 레지스터
    • 주소 변환 하드웨어(MMU)
  • 운영체제 지원
    • 모든 프로세스에 대해 프로세스별로 할당된 ‘물리메모리의 시작 주소와 크기 정보 저장’ 관리
    • 비어있는 메모리 영역 관리
    • 새 프로세스를 스케줄링하여 실행시킬 때마다, ‘물리 메모리의 시작 주소와 크기 정보’를 CPU 내부의 base 레지스터와 limit 레지스터에 적재
  • 연속 메모리 할당의 장단점
    • 장점
      • 논리 주소를 물리 주소로 바꾸는 과정 단순, CPU의 메모리 액세스 속도 빠름
      • 운영체제가 관리할 정보량이 적어서 부담이 덜함
    • 단점
      • 메모리 할당의 유연성이 떨어짐.
      • 외부 단편화

2.3. 연속 메모리 할당 구현

2.4. 메모리 배치 기법

2.4. 메모리 배치 기법

  • 홀 선택 알고리즘/동적 메모리 할당
    • 운영체제는 할당 리스트(allocation list) 유지
  • 할당된 파티션에 관한 정보를 리스트로 유지 관리
  • 할당된 위치, 크기, 비어 있는지 유무
  • 할당 요청이 발생하였을 때 홀 선택 전략 3가지

2.4.1. first-fit(최초 적합)

  • 비어 있는 파티션 중 맨 앞에 요청 크기보다 큰 파티션 선택
  • 할당 속도 빠름/단편화 발생 가능성

2.4.2. best-fit(최적 적합)

  • 비어 있는 파티션 중 요청을 수용하는 가장 작은 파티션 선택
  • 크기 별로 파티션이 정렬되어 있지 않으면 전부 검색
  • 가장 작은 홀 생성됨

2.4.3. worst-fit(최악 적합)

  • 비어 있는 파티션 중 요청을 수용하는 가장 큰 파티션 선택
  • 크기 별로 파티션이 정렬되어 있지 않으면 전부 검색
  • 가장 큰 홀 생성됨

2.4. 메모리 배치 기법 예

2.4.4. 어떤 배치 기법이 가장 좋은 것인가?

  • Simulations have shown that both first fit and best fit are better than worst fit in terms of decreasing time and storage utilization.
    • 시뮬레이션 해보면, first-fit과 best-fit이 속도나 메모리 사용률 측면에서 worst 보다 낫더라!
  • first-fit vs best-fit
    • Case by case!
    • 단, 알고리즘적으로는 first-fit이 유리하다!
    • 뭐 근데 보통 그렇다더라 하는거지, 대게 큰 차이는 없더라…!
    • 물론 상황마다 얼마든지 달라질 수 있음!

2.5. 단편화: 입출력이 반복되면 생기는 문제

  • 메모리에 프로세스의 입출력이 반복되다보면 단편화가 발생함
  • 단편화 예
    • 프로세스 A, B, C, D, E를 순서대로 배치했을 때 프로세스 B와 D가 종료되면 18KB와 17KB의 빈 공간이 생김
    • 이후 18KB보다 큰 프로세스가 들어오면 적당한 공간이 없어 메모리를 배정할 수 없음
      • 총 메모리 잔여 공간? 18+17 = 35KB.
    • 하지만, 20KB의 프로세스는 수용하지 못한다…!
  • 단편화 공간
    • 조각난 공간
    • 합치면 분명히 용량이 있지만, 조각나서 못쓰는 공간들

2.5. 단편화

2.5. 단편화 예

3. 단편화 Fragmentation

  • 프로세스에게 할당할 수 없는 조각 메모리 (Hole)들이 생기는 현상

  • 외부 단편화(externalfragmentation)

    • 할당된 메모리들 사이에 사용할 수 없는 홀이 생기는 현상
    • 가변 크기의 파티션이 생기고 반환되면서 여러 개의 작은 홀 생성
    • 홀이 프로세스의 크기(요구되는 메모리 량)보다 작으면 할당할 수 없음
    • MVT(Multiple Programming with a Variable Number of Tasks)의 경우

3. 외부 단편화

  • 내부 단편화(internal fragmentation)
    • 할당된 메모리 내부에 사용할 수 없는 홀이 생기는 현상
    • 파티션보다 작은 프로세스(요구되는 메모리)를 할당하는 경우 발생
    • MFT(Multiple Programming with a Fixed Number of Tasks)의 경우

3. 내부 단편화

3.1. 계산해보기

분할영역분할크기작업크기
15060
2150160
3200100
4250150

3.2. 단편화 해결방법

  • 조각 모음 (De-fragmentation) / Compaction(압축)
    • 이미 배치된 프로세스를 옆으로 옮겨 빈 공간들을 하나의 큰 덩어리로 만드는 작업
  • 동작
    • 조각 모음을 하기 위해 이동할 프로세스의 동작을 멈춤
    • 프로세스를 적당한 위치로 이동 (프로세스가 원래의 위치에서 이동하기 때문에 프로세스의 상대 주소값을 바꿈)
    • 작업을 다 마친 후 프로세스 다시 시작
    • 굉장히 비싼 작업…!

3.2. 조각모음

3.3. Buddy System

  • 메모리 할당의 Binary search
    1. 메인 메모리의 크기는 $2^N$
    2. 사용할 수 있는 가장 큰 메모리부터 시작해서 Binary로 절반씩 쪼개나가면서 아래 조건을 만족시키는 공간을 찾는다.
    3. 프로세스의 크기가 K일 때, $2^{U-1} < K \le 2^U$ 를 만족시키는 $U$를 찾고, $2^U$ 크기의 공간에 할당.
      • 예를 들어, 프로세스 크기가 100이면, 64 < 100 < 128이기 때문에 128 사이즈의 메모리에 할당
    4. 프로세스가 종료되고, 만약 같은 Parent를 갖는 Buddy 공간이 비어있다면 Merge.

3.3. Buddy System

3.3.1. Buddy System 특징

‣ 가변 분할 방식처럼 메모리가 프로세스 크기대로 나뉨 ‣ 고정 분할 방식처럼 하나의 구역에 다른 프로세스가 들어갈 수 없고, 메모리의 한 구역 내부에 조각이 생겨 내부 단편화 발생 ‣ 비슷한 크기의 조각이 서로 모여 작은 조각을 통합하여 큰 조각을 만들기 쉬움

4. 분할 메모리 할당

4. 분할 할당 - 세그먼테이션

4. 분할 할당 - 페이징

  • 분할된 크기는 20KB이므로 40KB인 프로세스 A는 프로세스 A1과 A2로 나뉘어 할당
  • 30KB인 프로세스 C는 프로세스 C1과 C2로 나뉘는데, 메모리에 남은 공간이 없으므로 프로세스 C2는 스왑 영역으로 옮겨짐
  • 정확히 우측 그림은
    • 불연속이면서 고정 분할이면서
    • 자세한건 다음시간, 페이징을 배울 때!

4. 고정 분할 방식 프로세스 배치

5. 세그먼테이션(Segmentation) 개요

  • 세그먼트(segment)
    • 세그먼트는 논리적 단위 – 개발자의 관점에서 보는 프로그램의 논리적 구성 단위
    • 프로그램을 구성하는 일반적인 세그먼트 종류
    • 코드 세그먼트, 데이터 세그먼트, 스택 세그먼트, 힙 세그먼트
    • 세그먼트마다 크기 다름
  • 세그먼테이션 기법
    • 프로세스를 논리 세그먼트 크기로 나누고, 각 논리 세그먼트를 한 덩어리의 물리 메모리에 할당하고 관리
  • 프로세스의 주소 공간
    • 프로세스의 주소 공간을 여러 개의 논리 세그먼트들로 나누고
    • 각 논리 세그먼트를 물리 세그먼트에 매핑
    • 프로세스를 논리 세그먼트로 나누는 과정은 컴파일러, 링커, 로더, 운영체제에 의해 이루어짐
  • 논리 세그먼트와 물리 세그먼트의 매핑
    • 시스템 전체 세그먼트 매핑 테이블을 두고 논리 주소를 물리 주소로 변환
  • 외부 단편화 발생

5.1. 논리 - 물리 세그먼트 매핑

5.1. 논리 - 물리 세그먼트 매핑 1

5.1. 논리 - 물리 세그먼트 매핑 2

Computer-Science, OS
OS 메모리
이 포스팅은 작성자의 CC BY-NC 4.0 라이선스를 준수합니다.