[운영체제] 메모리 관리 (2)

HONG·2023년 8월 26일

기술면접 운영체제 이론

기술면접

목록 보기

6/6

메모리 관리

부족한 메모리 공간을 좀 더 효율적으로 관리하려는 메모리 관리 기법

(1) 주소 할당 Address Binding

Address Binding
어떤 프로그램이 메모리의 어느 위치에,
즉 어떤 물리적 주소에 load 될지를 결정하는 과정

프로세스의 주소 종류

논리적 주소

Logical address, Virtual address (가상 주소)

CPU가 생성하는 주소

프로세스마다 독립적으로 갖는 주소 공간

프로세스의 내부에서 사용

각 프로세스마다 0부터 시작

물리적 주소

Physical address

프로세스가 실행되기 위해 실제로 메모리(RAM)에 올라가는 위치

주소 할당(Address binding)의 종류

binding하는 시점에 따라 분류된다

Compile Time
- 프로세스의 물리적 주소가 컴파일 때 정해진다
- 프로세스가 메모리의 어느 위치에 들어갈지 미리 알고 있다면
  ⇒ 컴파일러가 절대(=고정) 주소를 생성
  → 위치가 변경된다면 재컴파일 필요
- 논리적 주소와 물리적 주소가 동일하다
- 단점 : 고정 주소
  - 메모리 상에 빈 공간 발생 → 비효율적
  - 로드하려는 위치에 다른 프로세스가 존재할 수 있다
Load Time
- 프로세스가 메모리의 어느 위치에 들어갈지 미리 알 수 없다면
  ⇒ 컴파일러는 Relocatable code 생성
  ⇒ 그리고 Loader가 프로세스를 메모리에 load하는 시점에 물리적 주소 결정
- 따라서 논리적 주소와 물리적 주소가 다르다
- 단점
  - 프로세스 내에 메모리를 참조하는 명령어 多 → 주소를 다 바꿔주어야 함 → 로딩 시간이 매우 커질 수 있다
⇒ 따라서 컴파일 타임과 로드 타임 주소 할당은 실제로 잘 쓰이지 않는다!
Execution Time (Run time)
- 프로세스가 수행이 시작된 이후에 프로세스가 실행될 때 메모리 주소를 바꾸는 방법
- 즉 Runtime때 물리적 주소가 결정되며 실행 도중에 주소가 바뀔 수 있다
- CPU가 주소를 참조할 때마다 address mapping table을 이용하여 binding 점검
- MMU(Memory Management Unit)
  - 런타임 주소 할당에서, 논리적 주소를 물리적 주소로 바꿔주는 하드웨어 장치
  - 프로세스가 CPU에서 수행되면서 생성해 내는 모든 주소값에 대해서 base register의 값을 더해 물리적 주소를 생성
    - base register는 하나라서 프로세스끼리 공유함

런타임 주소 할당에서 MMU가 주소를 변환하는 과정
Limit register : 논리적 주소의 범위, 잘못된 메모리를 참조하지 않도록 막는 역할
Base register(Relocation register) : 접근할 수 있는 물리적 주소의 최솟값

[주의] 커널 모드인 경우에는 MMU가 물리적인 주소로 변환하지 않고 논리적 주소를 그대로 사용함
→ 커널 모드인지 체크하는 과정도 포함되어 있다

(2) 스왑 Swapping

Swapping
프로세스를 메모리에서 임시로 디스크에 보냈다가 (Swap out)
다시 메모리에 load하는 행위 (Swap in)

CPU에서 시행되지 않는 프로세스 (ready, waiting) 중 일부를 메모리 안에 보관하지 않고 하드디스크 등의 저장장치에 보관하는 것
swap 하는데 걸리는 시간의 대부분은 디스크 전송 시간이다.
기준
- 중기 스케줄러에 의해 swap out할 프로세스 선정
- 우선순위가 낮은 프로세스를 swap out
- 우선순위가 높은 프로세스를 swap in
주소 할당
- Compile time, Load time binding인 경우 → 원래 메모리 위치로 load
- Execution time binding인 경우 → 빈 메모리 영역 아무 곳에나 load

(3) 연속적 할당 Contiguous Allocation

연속적 할당 시스템
각 프로세스들이 연속적인 메모리 공간을 차지하게 되는 것

메모리는 일반적으로 커널 영역과 사용자 프로세스 영역으로 나뉘어 사용된다.

그 중 사용자 프로세스 영역의 할당 방법은

Contiguous Allocation (연속적 할당)
Noncontiguous Allocation (비연속적 할당)

으로 나뉜다.

연속적 할당

각 프로세스를 메모리에 담기 위해, 메모리는 미리 공간을 분할한다

고정 분할 (고정 파티션 할당)
- Fixed partition
- 공간을 고정된 크기로 분할
- 분할의 크기가 모두 동일하거나 혹은 서로 다를 수 있음
- 분할 당 하나의 프로세스가 적재
  - 동시에 메모리에 load 되는 프로세스의 수가 고정
  - 수행 가능한 프로세스의 최대 크기가 제한 (= 분할의 크기)
- 외부, 내부 단편화 발생 가능
가변 분할 (가변 파티션 할당)
- Variable partition
- 공간을 프로세스의 크기를 고려해 분할
- 분할의 크기나 개수가 동적으로 변함 → 기술적인 관리 기법이 요구됨
- 외부 단편화 발생 가능

Block

연속적 할당에서 메모리를 분할하는 각 단위
Hole
- 프로세스가 사용할 수 있는 Block
- 다양한 크기의 Hole들이 메모리 여러 곳에 흩어져 있고, 프로세스가 도착하면 수용 가능한 Hole을 할당시킴

Dynamic Storage-Allocation Proble

연속적 할당 - 가변 분할 방식에서 크기가 n인 프로세스가 들어갈 가장 적절한 Hole을 찾는 문제
해결법
1. First-fit : 크기가 n 이상인 Hole 중 최초로 발견한 Hole에 할당.
2. Best-fit
  1. 크기가 n 이상인 가장 작은 Hole을 찾아 할당
  2. Hole들이 크기순으로 정렬되지 않은 경우 모든 Hole을 탐색, 항상 거의 딱 맞는 크기를 할당하기 때문에 할당 후에 아주 작은 Hole들이 다량 생성됨
3. Worst-fit
  1. 가장 큰 Hole에 할당
  2. 모든 Hole을 탐색해야 하고, 상대적으로 아주 큰 Hole들이 새로 생성

(4) 단편화 Fragmentation

단편화
프로세스들이 메모리에 적재되고 제거되는 일이 반복되면
프로세스들이 차지하는 메모리 틈 사이에 사용하지 못할 만큼의 작은 공간들이 늘어나게 되는 현상

외부 단편화
- External Fragmentation
- 총공간을 계산했을 때 프로세스가 들어갈 수 있는 메모리가 있음에도 불구하고 공간들이 연속하지 않아 사용할 수 없는 경우
- 고정 분할, 가변 분할에서 발생 가능
- 해결책
  - 압축 Compaction
    - 프로세스가 사용하는 공간들을 한쪽으로 몰아서 공간을 확보
    - 비용이 매우 많이 드는 작업 → 효율 좋지 X
  - 페이징 Paging
내부 단편화
- Internal Fragmentation
- 프로세스가 사용하는 메모리 공간보다 분할된 공간이 더 커서 메모리가 남는 경우
- 고정 분할에서 발생 가능

(5) 페이징 Paging

페이징
한 프로세스가 사용하는 공간은 여러 page로 나뉘어 관리되고,
각각의 page는 순서와 관계없이 메모리의 frame에 mapping 되어 저장

비연속적 할당(Noncontiguous Allocation) 방식
외부 단편화의 압축 작업의 비효율성을 해결하기 위한 방법
메모리와 프로세스를 → 고정 크기의 블록(Block)으로 분할
- 메모리 → 프레임 (Frame)
- 프로세스 → 페이지 (Page)

작동 원리

프로세스가 순서대로 메모리에 저장되지 않음

프로세스 실행을 위해서는 page가 포함된 frame이 어디인지 알아야 함

Page table에 위 정보(page가 포함된 frame이 어디인지)가 포함됨

Page table을 사용해 논리적 주소를 물리적 주소로 변환.

Paging 장점
- page들이 연속할 필요 X → 외부 단편화 해결
- 빠른 할당과 해제
- 간단한 swap out
- 코드의 쉬운 공유 가능 (참고: shared pages)
Paging 단점
- 내부 단편화 해결 불가
- page table을 저장하기 위한 추가적인 메모리 필요
- page table은 메모리에 상주 → 메모리에 접근하는 연산은 2번의 메모리 접근이 요구됨 (page table에 접근 + 실제 연산) → 속도 저하
  - [참고] 따라서 속도 향상을 위해 Associative register 혹은 TLB(Translation Look-aside Buffer)라 불리는 고속의 하드웨어 캐시를 사용함

Logical address의 구성

page number

page table의 인덱스

page table에 접근 시 사용

page offset

물리적 주소를 얻을 때 사용

page table의 base address + page offset = 물리적 주소

Page table

Page table은 프로세스마다 존재하며 메인 메모리에 상주한다

PTBR(Page-Table Base Register)라는 레지스터가 page table을 가리킴

Context Switch가 발생하는 경우 PTBR의 내용만 변경

Page table의 각 엔트리(Entry)에는 정보를 담고 있는 bit가 포함된다

Protection bit : page에 대한 접근 권한 (read / write / read-only)

Valid-invalid bit : valid는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음. invalid는 없음(접근 불허)

Page의 크기가 작아질수록

내부 단편화 감소, 필요한 정보만 메모리에 있음
→ 효율적으로 메모리 이용

page table의 크기가 증가하고 디스크 이동의 효율성이 감소
⇒ 따라서 요즘은 page의 크기를 키워주는 추세

(6) TLB

Translation Look-aside Buffer
메모리 주소 변환을 위한 별도의 캐시 메모리로
Page table에서 빈번히 참조되는 일부 엔트리를 caching함

key-value 쌍으로 데이터를 관리하는 associative memory
- key에 page number, value에 frame number 대응

CPU는 page table보다 TLB를 우선적으로 참조한다

만약 원하는 page가 TLB에 있다면 → 곧바로 frame number 획득
그렇지 않은 경우 → 메인 메모리에 있는 page table로부터 frame number를 획득

원하는 엔트리가 TLB에 존재하는지 알기 위해선 TLB 전체를 다 찾아봐야 하는 단점이 있다.

→ 단, parallel search가 가능하므로 탐색 시간은 짧다

(7) Structure of the Pabe Table

Page table을 효율적으로 구성하는 방법

문제 상황

현대 컴퓨터는 주소 공간이 매우 큰 프로그램을 지원한다. 32 bit 주소를 사용하는 경우 2^32 = 4GB의 주소 공간을 사용한다. 이때 page의 크기가 4KB이면 약 100만 개의 page table entry가 필요하다. 그러나 대부분의 프로그램은 4GB 중 매우 일부분만 사용하므로 page table 공간이 심하게 낭비된다.

(a) Multi-level paging

논리적 주소 공간을 여러 단계의 page table로 분할
→ 오직 사용되는 page의 page table만 할당하는 기법

선형 페이지 테이블을 트리 구조로 표현한다
- 매우 효율적 → 현대 시스템에서 사용 중
이를 통해 각각의 page table이 Noncontiguously 하게 할당되도록 하는 것이 목표이다.

멀티 레벨 페이지 작동 원리

페이지 테이블을 페이지 크기의 단위로 나눈다

페이지 테이블의 페이지가 유효하지 않은 항목만 있다면

해당 페이지를 할당하지 않는다
= Page Table Entry (PTE)를 생성하지 않는다

Page directory라는 자료구조를 사용해 페이지 각 테이블의 할당 여부와 위치를 파악한다

(b) Hashed Page Table

hash table을 이용하여 page table을 관리하는 기법

주소 공간이 32 bit보다 커지면 → 계층적 paging이 비효율적
⇒ Hashed Page Table 사용
virtual page number를 해싱하여 page table을 참조하는 데 사용
연결 리스트를 따라가면서 page number를 비교 & 일치하면 대응되는 frame number 획득
구현하기가 어렵지만 속도는 매우 빠르다.

(c) Inverted Page Table

메모리의 frame마다 한 항목씩 할당함으로써
physical frame에 대응하는 항목만 저장 → 메모리를 훨씬 적게 사용

지금까지의 page table은 각 page마다 하나의 항목을 가짐
각 page table entry는 각각의 메모리의 frame이 담고 있는 내용(PID, logical address)을 표시
테이블 전체를 탐색해야 하므로 시간이 오래 걸림
⇒ 대부분의 메모리는 Hashed page table과 Inverted page table의 결합으로 이루어져 있다

(8) 세그멘테이션 Segmentation

세그멘테이션
의미 단위로 하나의 프로세스를 나누는 것

정의
- 작게는 프로그램을 구성하는 함수 하나, 크게는 프로그램 전체
- 일반적으로는 code, data, stack 부분이 하나의 세그먼트로 정의된다.
논리적 주소
- <segment number, offset>
- 각각의 segment는 base, limit, protection bit을 갖는다
장점 (= paging과 유사)
- segment들이 연속적으로 할당될 필요 X
- stack과 heap이 독립적으로 커질 수 O
- segment마다 protection을 따로 수행할 수 있음
단점
- 각각의 segment는 반드시 연속적으로 할당해야 함

HONG