📌 메모리 할당(Memory Allocation)

💡 사전 지식

메모리 영역

OS 상주 영역과 사용자 프로세스 영역으로 나뉜다.

내부 단편화 외부 단편화

내부 단편화(Internal Fragmentation)
- 프로그램의 크기가 분할의 크기보다 큰 경우
- 프로그램에 할당된 공간이지만 사용되지 않는 공간
외부 단편화(External Fragmentation)
- 프로그램의 크기보다 분할의 크기가 작은 경우
- 메모리의 빈 공간이지만 모든 프로그램의 크기보다 작아서 사용되지 못하는 공간
두 개념이 어느 정도 연관된 개념이다.
- 보는 시각의 차이에 따라 외부 단편화가 내부 단편화로 될 수 있음!

홀(hole)

가용 메모리 공간이다.
메모리는 프로세스에게 적당한 크기(프로세스가 적재될 수 있는)의 홀을 부여한다.

데이터 표현 단위

2^10 = K(킬로)
2^20 = M(메가)
2^30 = G(기가)

✔️ 사용자 프로세스에 메모리 할당 방법

사용자 프로세스에 메모리 할당 방법의 크게 두 가지 방법으로 나뉜다.
연속 할당 방법(Contiguous allocation)
- 각 프로세스를 연속적인 메모리 공간에 적재하는 방법
- 아래의 두 가지 방법이 존재한다.
  - 고정 분할 할당(Fixed partition allocation)
  - 가변 분할 할당(Variable partition allocation)
불연속 할당 방법(Noncontiguous allocation)
- 하나의 프로세스를 메모리의 여러 영역에 분산시켜 적재하는 방법
- 아래의 세 가지 방법이 존재한다.
  - 페이징(Paging)
  - 세그멘테이션(Segmentation)
  - 페이지드 세그멘테이션(Paged Segmentation)

✔️ 고정 분할 할당

- 사용자 프로그램이 들어갈 메모리 공간을 미리 분할하는 방법
    - 분할(Partition)의 크기는 각각 다를 수 있다.
    - 분할 당 하나의 프로그램의 적재
- 사용자 프로세스는 미리 분할된 공간 중 크기가 맞는 메모리 공간에 적재된다.
- 분할의 개수에 따라 동시에 메모리에 적재되는 프로그램의 수가 제한됨
- 최대 분할 크기에 따라 최대 프로그램의 크기가 제한됨
- 내부 단편화와 외부 단편화가 모두 발생

✔️ 가변 분할 할당

- 사용자 프로그램이 실행될 때마다 메모리 공간에 차례로 적재하는 방법
- 분할의 크기와 개수가 동적으로 변함
- 외부 단편화 발생
    - 메모리에 적재된 프로세스가 종료되면 `홀(hole)`이 생긴다.

❗️ 홀(hole)

가용 메모리 공간이다.
메모리는 프로세스에게 적당한 크기(프로세스가 적재될 수 있는)의 홀을 부여한다.
운영체제는 메모리를 할당 공간과 가용 공간(홀)의 정보를 가지고 있다.

동적 메모리 할당 문제(Dynamic Storage-Allocation Problem)

가변 분할 방식에서 프로세스가 크기가 n 바이트인 공간이 필요할 때, 가장 적절한 크기의 hole을 찾는 문제
일반적으로 세 가지의 방법이 있다.
- 최초 적합(First-fit)
  - 처음 발견한 크기가 n 바이트 이상의 공간(hole)에 할당
- 최적 적합(Best-fit)
  - 크기가 n 바이트 이상의 공간 중 가장 작은 공간에 할당
  - 보통 다른 방법에 비해 메모리를 할당한 후 작은 공간이 생긴다.
- 최작 적합(Worst-fit)
  - 가장 큰 공간에 할당
  - 보통 다른 방법에 비해 메모리를 할당한 후 큰 공간이 생긴다.
최초 적합과 최적 적합이 일반적으로 속도와 공간 이용률 측면에서 최악 적합보다 효과적인 것으로 알려졌다.
공간 효율성 면에서 최초 적합과 최적 적합은 경우에 따라서 효율적인 방법이 다르다.
속도 측면에서는 일반적으로 최초 적합이 최적 적합보다 더 빠르다.

외부 단편화를 해결하기 위한 방법

압축(Compaction) 방법
- 사용중인 메모리 공간을 한 곳으로 몰고, 다른 한 곳에는 가용 공간(홀)을 모아 큰 홀을 만드는 방법
- 비용이 많이 드는 작업이며, 메모리 주소를 실행 시간에 동적으로 배치할 수 있을 때 사용 가능한 방법

✔️ 페이징(Paging)

프로세스의 메모리 영역을 동일한 크기의 단위(페이지)로 나누고 각각의 단위를 불연속적인 물리적인 공간에 올리는 방법
페이지(page)와 프레임(frame)
- 페이지
  - 프로세스의 메모리 영역을 나누는 단위(=논리 메모리를 나누는 단위)
  - 각 페이지의 크기는 동일
  - 페이지의 크기는 컴퓨터 아키텍처에 따라 다르지만, 보통은 4KB라고 한다.
- 프레임
  - 물리적인 메모리 영역을 나누는 단위
  - 페이지와 같은 크기
  - 하나의 프레임에 하나의 페이지를 할당한다.
    - 하나의 물리적인 공간에 하나의 논리적인 메모리 영역을 할당하는 것!
내부 단편화가 발생할 수 있다.
- 프로그램의 크기가 페이지의 배수가 아닐 수 있다.
논리 주소를 물리 주소로 변환하기 위해 페이지 테이블(page table)을 이용한다.
- 페이지 테이블은 페이지 번호를 인덱스로 받으며, 해당 위치에는 논리 주소와 연결된 물리 주소의 프레임 번호가 저장되어 있다.
- 즉, 몇 번 페이지가 몇 번 프레임에 올라갔는지 확인하기위해 페이지 테이블을 이용한다.
MMU(Memory Management Unit)을 통한 주소 변환 과정이 연속 할당 방법에 비해 복잡하다.

페이지 테이블(Page Table)

페이지 테이블은 메인 메모리(물리 공간)에 존재한다.
PTBR과 PTLR
- PTBR(Page-table base register)
  - 페이지 테이블을 가리키는 포인터 값이 저장되는 레지스터
  - 메인 메모리에 저장된 페이지 테이블의 위치를 저장한다.
- PTLR(Page-table length register)
  - 페이지 테이블의 크기를 저장하는 레지스터
- 다른 페이지 테이블을 사용하려면 PTBR과 PTLR에 저장된 값만 변경하면 된다.
데이터에 접근하기 위해서 두 번의 메모리 접근이 필요
- PTBR에 저장된 값을 통해서 물리 공간에 저장된 페이지 테이블에 접근
- 페이지 테이블에서 변환된 프레임과 offset 값을 이용해서 데이터에 접근
- 때문에 속도 측면에서 손해를 본다.
페이지 테이블에는 두 가지 추가 bit가 있다.
- valid-invalid bit
  - 해당 페이지가 유효한(또는 사용되는) 페이지인지 확인해 주는 bit
  - valid 상태는 참조하려는 코드 부분(페이지)가 물리 메모리의 프레임에 적재된 상태를 의미한다.
  - invalid 상태는 두 가지 의미가 있다.
    - 프로세스가 주소 부분(페이지)를 사용하지 않는 경우
    - 프로세스가 주소 부분(페이지)를 사용하지만 현재 물리 메모리의 프레임이 아닌 아닌 swap-area에 존재하는 경우(swap-out된 상태)
- protection bit
  - 읽기/쓰기 등의 권한의 표현하는 bit
    - 코드 영역은 읽기 전용 권한이 부여돼야 한다.
    - 반면, 스택 영역은 읽기/쓰기 연산이 모두 가능하다.

TLB(Translation look-aside buffers)

주소 변환을 위한 캐시메모리
- 메모리와 CPU의 속도 차이로 인해 데이터 접근 시 발생되는 비효율적인 문제를 해결하기 위해 사용된다.
TLB는 페이지 테이블의 일부분을 저장한다.
- 페이지 테이블과 다르게 페이지 번호와 프레임 번호 정보를 같이 저장한다.
parallel search가 가능한 associative register이다.
TLB를 이용한 주소 참조 방식
1. CPU에 의해 생성된 논리 주소를 MMU에 전달
2. MMU는 TLB에 해당되는 페이지 번호가 존재하는지 확인
  - 만약 페이지 정보가 있다면(캐시 미스), 3번으로
  - 페이이지 정보가 없다면(캐시 히트), 4번으로
3. TLB에 저장된 프레임 번호를 이용해서 물리 주소를 반환
4. 페이지 테이블로 접근하여 프렘임 번호를 얻고, 물리 주소를 반환
  - 데이터에 접근 후, 페이지 번호와 프레임 번호를 TLB에 추가하여
  - 이를 통해 다음에 같은 데이터에 참조할 경우 더 빠르게 참조할 수 있도록 한다.
ASIDs(address-space identifiers)
- TLB의 각 항목이 어느 프로세스에 속해있는지 알려주는 정보로 TLB에 저장한다.
- ASIDs의 지원이 있으면 TLB에는 여러 프로세스의 페이지 테이블 정보가 저장될 수 있다.
- 반면, ASIDs의 지원이 없으면 TLB에 저장된 정보는 문맥 교환(Context Switch)가 발생할 때마다 초기화돼야 한다.(flush)

2단계 페이지 테이블(Two-Level Page Table)

1단계 페이지 테이블을 사용하면 공간 낭비가 심하다.
- 일반적으로 프로그램에서 자주 참조하는 영역(페이지 영역)은 전체 코드 영역에서 일부분이다.
- 모든 페이지 정보를 메모리에 저장하는 것은 낭비다.(페이지 테이블로 저장할 경우 모든 페이지 정보가 순차적으로 저장돼야 한다.)
2단계 페이지 테이블 시스템에서 논리 주소 비트를 구성하는 방법은 해당 강의의 38분부터 참조
다단계 페이지 테이블을 TLB와 함께 이용하면 속도 측면의 overhead가 크게 발생하지 않는다.

Inverted Page Table

모든 프로세스가 페이지 테이블을 공유하는 형태
- 따라서 페이지 테이블은 프로세스 id 정보(pid)를 저장하고 있어야 한다.
페이지 테이블의 entry 개수는 물리 메모리의 프레임 개수와 같다.
- 페이지 테이블의 0번째 entry는 프레임 0번을 의미한다.
논리 주소(페이지)에 해당되는 물리 주소(프레임)을 찾기 위해서 페이지 테이블의 모든 entry를 조회해야 한다.
- 페이지 테이블의 공간을 줄이기 위해 사용된다.
- 하지만 시간 측면에서 overhead가 발생한다.
- 속도의 문제를 해결하기 이해 associative register를 이용해서 병렬적으로 탐색하는 방법이 있다.

Shared Pages

여러 프로세스가 공유할 수 있는 코드 영역을 중복되지 않는 프레임 영역에 적재하고, 각 프로세스가 프레임(물리 공간)을 공유하는 방법
Shared Code
- Shared Code가 되기 위한 조건
  - ready-only 상태여야 한다.
  - 코드를 공유하려는 각 프로세스의 동일한 논리 주소를 가져야 한다.
Private Code and data
- 각 프로세스들은 해당 영역을 독립적인 물리 메모리 공간에 올린다.

✔️ 세그멘테이션(Segmentation)

프로그램의 메모리 영역을 의미 있는 단위로 나누어 물리적인 공간에 올리는 방법
- 의미 있는 단위의 예시) 프로세스 영역을 코드, 데이터, 스택 영역으로 나눈다.
- 의미 있는 단위를 더 작게 구성하면 함수 단위로 나눌 수 있다.
논리 주소는 두 가지로 구성
- segment-number
  - 해당 주소가 몇 번째 segment에 해당되는지에 대한 정보
- offset
  - segment-number의 시작 위치에서 몇 번째 떨어진 위치인지에 대한 정보
세그먼트 테이블
- 각 엔트리는 base 정보와 limit 정보를 갖는다.
- base
  - 해당 세그먼트의 시작 위치(물리 메모리 주소)
- limit
  - 해당 세그먼트의 길이
- 세그먼트 테이블의 결괏값으로는 byte 단위의 물리 주소를 반환한다.
기본적으로 각 프로세스는 독립적인 세그먼트 테이블을 갖는다.
- STBR(Segment-table base register)
  - 물리 메모리에서 세그먼트 테이블의 위치
- STLR(Segment-table length reegister)
  - 해당 프로세스의 세그먼트의 총 개수
  - 만약 참조하려는 세그먼트 번호가 STLR에 저장된 값보다 크면 잘못된 참조로 판단한다.
Protection과 Sharing 부분은 세그멘테이션 기법이 페이징 기법보다 장점을 가진다.
- 세그멘테이션 기법은 논리 메모리 영역을 의미 단위로 나누기 때문에
Allocation 측면에서는 세그멘테이션 기법이 페이징 기법에는 없는 단점을 가진다.
- 크기가 균일하지 않기 때문에 동적 메모리 할당 문제가 발생할 수 있다.
- 가변 분할 방식과 동일한 문제들이 발생한다.

✔️ Paged Segmentation

페이징 기법과 세그멘테이션 기법을 혼합한 주소 할당 방법
논리 메모리 영역을 의미 있는 단위(세그먼트)로 나누고, 각 세그먼트는 동일한 크기의 단위(페이지)로 나눠서 메모리를 할당하는 방법
- 논리적인 메모리 공간 의미 있는 단위로 나누기 때문에 Protection과 Sharing 부분에서 장점을 가진다.
- 물리적인 공간을 할당할 때는 동일한 크기의 영역을 할당하기 때문에 Allocation 부분에서 장점을 가진다.
보통 시스템에서는 세그멘테이션 기법과 페이징 기법을 혼합한 방법을 사용한다.
해당 기법에서는 세그멘테이션 테이블과 페이지 테이블이 모두 존재한다.
- 세그멘테이션 테이블에는 페이지 테이블의 시작 위치 정보를 저장
- 페이지 테이블에는 페이지의 위치를 저장한다.

📚 참고 자료

KOCW 운영체제 Ch.Memory Mnagement- 반효경 교수님
Operating System Concepts Ch.8 Main Memory - Abraham Silberschatz 외 2인

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

memoryAllocation.md

memoryAllocation.md

📌 메모리 할당(Memory Allocation)

💡 사전 지식

✔️ 사용자 프로세스에 메모리 할당 방법

✔️ 고정 분할 할당

✔️ 가변 분할 할당

❗️ 홀(hole)

동적 메모리 할당 문제(Dynamic Storage-Allocation Problem)

외부 단편화를 해결하기 위한 방법

✔️ 페이징(Paging)

페이지 테이블(Page Table)

TLB(Translation look-aside buffers)

2단계 페이지 테이블(Two-Level Page Table)

Inverted Page Table

Shared Pages

✔️ 세그멘테이션(Segmentation)

✔️ Paged Segmentation

📚 참고 자료

Files

memoryAllocation.md

Latest commit

History

memoryAllocation.md

File metadata and controls

📌 메모리 할당(Memory Allocation)

💡 사전 지식

✔️ 사용자 프로세스에 메모리 할당 방법

✔️ 고정 분할 할당

✔️ 가변 분할 할당

❗️ 홀(hole)

동적 메모리 할당 문제(Dynamic Storage-Allocation Problem)

외부 단편화를 해결하기 위한 방법

✔️ 페이징(Paging)

페이지 테이블(Page Table)

TLB(Translation look-aside buffers)

2단계 페이지 테이블(Two-Level Page Table)

Inverted Page Table

Shared Pages

✔️ 세그멘테이션(Segmentation)

✔️ Paged Segmentation

📚 참고 자료