#단편화와 그 해결 기법

아래 강의 정리 내용입니다. 강의 제공해주신 'Young Hyun Bae'님 감사합니다.

09-1 메모리의 기본 구조와 동작 (https://www.youtube.com/watch?v=IB1Klmq4UPc)

09-2 메모리 관리 기법 (1) (스와핑, 연속 메모리 할당) (https://www.youtube.com/watch?v=9uygOl-uyhA)

09-3 메모리 관리 기법 (2) (페이징, 세그먼테이션) (https://www.youtube.com/watch?v=2gW9pTFEW0U)

(정리 및 학습 중)

※ 단편화 (Fragmentation)

■ 외부 단편화 (external fragmentation)

● 메모리 할당이 반복됨으로써 사용할 수 없는 작은 크기의 가용 공간이 분산되어 생기는 현상

■ 내부 단편화 (internal fragmentation)

■ 외부 단편화 문제의 해결

● 메모리 압축 (compaction)

- 분산된 자유 공간을 모아 큰 블록 생성

- 프로세스 주소 공간이 동적으로 재배치 가능해야 함

: 재배치/기준 레지스터 값 변경

- 운영체제의 비용이 많이 드는 작업

● 페이징(paging)과 세그먼테이션(segmentation)

- 한 프로세스의 논리 주소 공간을 여러 개로 분할하여 비연속적인 물리 메모리 공간에 할당

※ 스와핑 (Swapping)

■ CPU에서 실행 중이지 않은 프로세스의 메모리 이미지를 저장장치로 이동

● 메모리 사용의 효율성 증가

■ 스케줄러의 동작에 따라 작동

■ 입출력을 요청한 프로세스의 스왑 처리 방법

● 스왑 불가 혹은 커널 버퍼를 이용한 입출력 수행

■ 스왑되어 들어오는 주소

● 컴파일/적재 시간 바인딩 : 이전과 동일한 주소

● 실행 시간 바인딩: 임의의 빈 공간

■ 스와핑과 문맥 교환(Context Switch)

● 디스패처(dispatcher)의 동작

- Ready queue의 다음 프로세스가 메모리에 없다면 swap in

- 메모리 공간이 부족하다면, 다른 프로세스를 swap out 후 swap in

● 문맥 교환 시간 증가

- 메모리 스왑 시간은 저장장치 전송시간에 의존

: 예) 100MB 프로세스가 50MB/s인 HDD에 스왑 → 2초

- 평범한 스왑 방식은 실제 시스템에 적용하기 어려움

: 디스크 내에 별도 스왑 공간 사용 (일반 파일 시스템과 분리)

: 실제로 사용하는 부분만 스왑하도록 최적화 필요

: 유닉스에서는 시스템 부하가 클 때만 스와핑 작동

※ 페이징

■ 페이지 단위의 논리-물리 주소 관리 기법

■ 논리 주소 공간이 하나의 연속적인 물리 메모리 공간에 들어가야 하는 제약 해결

● 스와핑을 하는 경우에도 디스크에 연속적으로 저장될 필요없음

■ 필요 조건

● 논리 주소 물리 주소 공간 분리 : 주소의 동적 재배치 허용

● 전용 하드웨어(MMU) : 논리 주소와 물리 주소 변환

■ 프레임 : 물리 메모리의 고정 크기 블록

■ 페이지 : 논리 메모리의 고정 크기 블록, 프레임과 같은 크기

■ 프로세스 실행 시 각 페이지는 임의의 메모리 프레임에 적재될 수 있다.

■ 논리 주소

● 페이지 번호(p)와 페이지 오프셋(d, offset, 프레임 번호)

● 논리 주소 공간의 크기가 이고, 페이지의 크기가 일 때

● 상위 (m –n)비트는 페이지 번호, 하위 n비트는 오프셋

● 페이지 테이블(Page Table)

● 각 페이지 번호에 할당된 메모리의 프레임 번호 제공

- 각 페이지에 대한 기준 (base) 주소 역할

● 개의 항목(entry) 포함

● MMU(Memery Management Unit)가 논리주소를 물리주소로 변환

● 사용자/프로세스의 편의성

- 연속된 논리 주소 공간을 독립적으로 사용

- 주소 변환은 하드웨어와 운영체제에 의해 처리

● 프레임 단위의 비연속적 메모리 할당 (allocation)

- 동적 메모리 할당에 따른 문제거 없음 (외부 단편화 없음)

● 내부 단편화 (internal fragmentation)

- 페이지 크기보다 작은 메모리를 요청하는 경우에 발생

- 페이지 크기가 작으면 내부 단편화 감소 (테이블 크기 증가)

● 프레임 테이블 (frame table)

- 운영체제가 관리하는 메모리 프레임(물리 메모리)의 사용 정보

● 페이징과 문맥 교환

- 페이지 테이블을 재설정하기 위해 문맥 교환 시간 증가

● 공유 페이지(shared page)

- 비교적 간단하게 메모리 공유 지원

■ 페이지 테이블의 구현

● 페이지 테이블도 메모리 저장

- 기준 레지스터 (Page_table Base Register, PTBR)

: 메모리에 저장된 페이지 테이블의 시작 주소 저장

- 문맥 교환 시에 페이지 테이블 교체 비용이 적음

: PTBR 값만 변경

● 메모리 접근 시간 문제

● 매번 메모리의 페이지 테이블을 먼저 읽어야 하므로 메모리 접근시간이 두배가 됨 ☞ 심각한 문제

: 해결책 : 페이지 테이블의 캐싱(caching)

: TLB(Translation Look-aside Buffer)

■ TLB(Translation Look-aside Buffer)

● 페이지 테이블을 위한 소형의 하드웨어 캐시

- 접근 속도가 매우 빠른 연관 메모리(associative memory)

- TLB 내의 항목(entry)은 키(key)와 값(value)으로 구성

: key = 페이지 번호

: value = 페이지 번호에 해당하는 프레임 번호

- 요청된 페이지 번호로 모든 항목을 동시에 비교

- 비싼 메모리로서 보통 64 ~ 1024 항목 저장

- 메모리 참조 시간은 주소 변환을 하지 않는 경우보다 10% 이하의 시간만 더 소요

● TLB 항목(entry) 교체(replacement)

- TLB miss 시 페이지 테이블에서 새로 가져온 것으로 교체

- LRU, FIFO, Random 등의 알고리즘

- 일반적으로 커널 코드에 대한 항목은 TLB에 고정시킴

● Address-psace Identifier (ASID)

- 각 TLB 항목이 속한 프로세스 정보

- 한 TLB에 여러 프로세스를 위한 페이지 테이즐 항목을 저장

: 페이지 번호가 같더라도 ASID가 다르면 참조 실패

- 문맥 교환 시에 TLB를 모두 방출(flush)하는 비용 줄임

■ 페이지 테이블의 구조

● 실제 컴퓨터 시스템에서의 페이지 테이블

- 페이지 테이블의 크기가 매우 크다

- 실제 컴퓨터의 시스템의 논리 주소 공간 :  혹은 

: 페이지 크기 : 4KB ()

: 페이지 테이블 항목(entry) 크기: 4bytes

: 페이지 테이블의 크기: 4MB( 4 x )

- 페이지 테이블을 연속된 메모리 공간에 배치하기 어렵다

● 크기가 큰 페이지 테이블의 처리

- 계층적 페이징 (Hierarchical Paging)

- 해시 페이지 테이블 (Hashed Page Table)

- 역 페이지 테이블 (Inverted page Table)

■ 계층적 페이징 (Hierarchical Paging)

● 2단계 페이지 테이블 기법

- 페이지 테이블 자체를 다시 페이징

: 외부 페이지 테이블

- 여러 개이 작은 크기 페이지 테이블로 구성

● 32비트 논리 주소 공간의 2단계 페이징 주소 구조

- 20비트의 페이지 번호

: 10비트_ 외부 페이지 테이블의 인덱스 (페이지 번호)

: 10비트_ 페이지 테이블을 위한 페이지의 오프셋

: 

● 2단계 페이징에서 주소 변환

- 성능 문제 → 유효한 페이지들만 테이블에 포함(해싱)

■ 해시 페이지 테이블 (Hashed Page Table)

● 논리 주소의 페이지 번호를 해시 값으로 사용

- 32비트 이상의 논리 주소 공간을 위한 페이지 테이블 구성 방법

- 해시 페이지 테이블의 항목은 연결 리스트(linked list) 구성

: 패이지 번호, 프레임 번호, 다음 원소 포인터

■ 역 페이지 테이블 (Inverted Page Table)

● 물리 메모리의 프레임 번호로 인덱스되는 테이블

- 각 항목(entry)은 페이지 번호와 프로세스 ID로 구성

: 한 시스템에 한 개의 페이지 테이블만 존재

: 프로세스 ID = 주소 공간 ID (ASID)

● 주소 변환

- 논리 주소: <프로세스 ID, 페이지 번호, 오프셋>

- 프로세스 ID와 페이지 번호로 페이지 테이블을 검색

- 발견된 항목의 인덱스가 프레임 번호

● 역 페이지 테이블의 특징

- 작은 메모리 공간 필요

- 주소 변환 시간 길어짐 (검색 비용)

: 해시 테이블 사용

- 메모리 공유가 어려움

※ 세그먼테이션

■ 사용자/프로그래머 관점의 메모리 관리 기법

- 논리 주소 공간을 세그먼트(segment) 집합으로 정의

: 세그먼트마다 별도의 독립된 주소 공간 제공

■ 세그먼트

● 프로그램의 논리적 단위

- method, procedure, function, object, variable, stack 등

● C 컴파일러 관점

- 코드, 전역 변수, 힙, 스택, 표준 C 라이브러리

- 각각의 이름과 서로 다른 길이 가짐

● 세그먼트의 논리 주소

- 세그먼트 이름(번호)과 오프셋

■ 세그먼트 테이블(segment table)

● 세그먼트가 사상되는 물리 메모리의 위치(주소) 제공

● 각 항목은 세그먼트의 기준(base) 주소와 한계(limit) 주소로 구성