메모리 할당

라마·2023년 7월 31일

운영체제

목록 보기

28/32

※ 전남대학교 박태준 교수님의 운영체제 강의를 듣고, 정리한 내용입니다.

Memory Allocation

운영체제가 새 프로세스를 실행시키거나 실행 중인 프로세스가 메모리를 필요로 할 때, 물리 메모리를 할당해주어야 합니다.

여기서 고민해보아야 할 점은, 메모리를 할당해주는 건 좋지만, 메모리 어디에, 어떻게 올려할지 고민해봐야한다는 점입니다.

메모리 할당 기법

연속 vs 불연속 : Process Partitioning
- 연속 : 프로세스가 메모리 내 인접되어 연속되게 하나의 블록을 차지하도록 배치
  - 프로세스가 쪼개지지 않고 메모리에 올라감
- 불연속 ( 분산 ) : 프로세스가 페이지나 세그먼트 단위로 나뉘어 분산 배치되는 방법
가변 vs 고정 : Memory Partitioning
- 가변 : 프로세스의 크기에 맞게 메모리가 분할
- 고정 : 프로세스의 크기에 상관없이 메모리가 같은 크기로 나뉨
  - 큰 프로세스가 메모리에 올라오면 여러 조각으로 나누어 배치

연속 메모리 할당 ( Contiguous Allocation )

각 프로세스의 영역 ( 코드와 데이터 ) 을 연속된 메모리 공간에 배치하는 기법을 연속 메모리 할당 이라고 합니다.

고정 크기 : 메모리를 고정 크기의 파티션으로 나눔
- 각 프로세스를 하나의 파티션에 배치
가변 크기 : 각 프로세스에게 자신의 크기만한 크기의 파티션 할당

연속 메모리 할당 구현

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

연속 할당에서의 메모리 배치 기법

메모리의 빈 공간 중 어디에 프로세스를 넣을 것인지 결정하는 알고리즘이 홀 선택 알고리즘입니다.

홀 선택 알고리즘 / 동적 메모리 할당 : 운영체제는 할당 리스트 ( Allocation List ) 유지
- 할당된 파티션에 관한 정보를 리스트로 유지 관리
- 할당된 위치, 크기, 비어있는지 유무 확인
할당 요청이 발생했을 때 홀 선택 전략 3가지
- first - fit ( 최초 적합 )
  - 비어있는 파티션 중 맨 앞에 요청 크기보다 큰 파티션 선택
  - 순차 탐색하며 들어갈 수 있는 공간을 발견하면 거기로 들어감
  - 할당 속도가 빠르지만, 단편화 발생 가능성 존재
- best - fit ( 최적 적합 )
  - 비어있는 파티션 중 요청을 수용하는 가장 작은 파티션 선택
  - 순차 탐색하며 가장 단편화가 적게 발생하는 공간에 들어감
  - 가장 프로세스와 딱 맞는 공간을 찾는 방법!
  - 가장 작은 홀이 생성됨
- worst - fit ( 최악 적합 )
  - 비어있는 파티션 중 요청을 수용하는 가장 큰 파티션 선택
  - 순차 탐색하며 가장 단편화가 크게 발생하는 공간에 들어감
  - 가장 프로세스와 공간 차이가 큰 공간을 찾는 방법!
  - 가장 큰 홀이 생성됨

여러 방법이 존재하지만, 대개 큰 차이가 없기에 상황에 따라 어떤 방법을 선택할지는 얼마든지 달라질 수 있습니다.

연속 할당에서 입출력이 반복되다보면..

메모리에 프로세스의 입출력이 발생하다 보면, 단편화가 발생하게 됩니다.

단편화란 쉽게 생각하면 조각난 공간들이라고 볼 수 있습니다.

파티션 안에 프로세스가 들어가면서 파티션의 공간보다 프로세스의 크기가 작을 경우 비어있는 공간이 나오게 되는데, 이 비어있는 공간을 단편화 라고 부릅니다.

→ 정확히는 내부 단편화 라고 부릅니다.

🖥️ 파티션 공간 > 프로세스 크기 : ( 파티션 공간 - 프로세스 크기 ) 만큼 단편화 발생!

아래 그림의 경우 비어있는 공간보다 큰 프로세스가 들어갈 수 없으니, 이 경우도 단편화라고 볼 수 있습니다.

→ 정확히는 외부 단편화 라고 부릅니다.

단편화 ( Fragmentation )

프로세스에게 할당할 수 없는 조각 메모리 ( Hole ) 들이 생기는 현상을 단편화 라고 합니다.

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

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

단편화 해결방법

조각 모음 ( De-fragmentation ) / 압축 ( Compaction )
- 이미 배치된 프로세스를 옆으로 옮겨 빈 공간들을 하나의 큰 덩어리로 만드는 작업
굉장히 비싼 작업 중 하나..!!
- 프로세스의 위치를 옮긴다는 건, 데이터를 복사하며 프로세스를 옮기는 것이기 때문!

Buddy System

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

Buddy System 특징

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

분할 메모리 할당 ( Noncontiguous Allocation )

세그먼테이션 ( Segmentation ) : 프로세스를 가변 크기의 세그먼트들로 분할
페이징 ( Paging ) : 프로세스를 고정 크기의 페이지들로 분할

가볍게 보면, 프로세스를 쪼개서 메모리에 할당하는 방식을 분할 메모리 할당이라고 볼 수 있습니다.

세그먼테이션 ( Segmentation )

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