10.1 Background
- 프로그램을 실행하려면 명령어가 물리 메모리에 있어야 하지만, 물리 메모리의 크기는 제한적이다.
- 프로그램 전체가 항상 필요하지는 않으며, 오류 처리 코드나 필요 이상으로 할당된 배열 등은 거의 사용되지 않는다.
- 프로그램의 일부만 메모리에 로드하여 실행할 수 있다면, 더 많은 프로그램을 동시에 실행할 수 있고, 성능도 향상될 것이다.
가상 메모리(Virtual memory) 개념
- 가상 메모리는 논리 메모리와 물리 메모리를 분리하여, 실제 물리 메모리보다 훨씬 큰 메모리 공간을 제공하는 방식이다.
- 개발자는 물리 메모리 크기를 신경 쓰지 않고 프로그램을 작성할 수 있다.
가상 주소 공간(virtual address space)
- 프로세스가 메모리에 저장되는 방식에 대한 논리적(또는 가상) 보기를 의미
- 가상 주소 공간은 연속적으로 보이지만, 실제 물리 메모리에서는 불연속적인 페이지 프레임으로 저장된다.
- 스택은 아래 방향으로, 힙은 위 방향으로 성장하며, 이들 사이의 빈 공간(홀)은 동적 할당 및 공유 라이브러리 로딩 등에 활용될 수 있다.
10.2 요구 페이징 (Demand Paging)
10.2.1 기본 개념
- 요구 페이징은 필요한 페이지만 메모리에 로드하는 방식으로, 실행 중 참조된 페이지만 로딩하므로 메모리를 효율적으로 사용할 수 있다.
- 실행 중 참조되지 않은 페이지는 보조 저장장치(HDD, NVM 등)에 남아 있으며, 접근 시 메모리로 가져온다.
요구 페이징의 작동 방식
- 페이지 접근 확인: 페이지 테이블에서 해당 페이지가 유효한지(valid) 확인한다.
- 페이지 폴트(Page Fault) 발생:
- 페이지가 유효하지 않다면, 운영체제(OS)가 트랩을 처리하여 해당 페이지를 메모리에 로드한다.
- 페이지 폴트 처리 과정
페이지 폴트 처리 단계 - 내부 테이블 확인
- 유효성 검사 및 프로세스 처리
- 잘못된 접근(Invalid Reference): 프로세스를 강제 종료(Terminate)
- 유효한 접근(Valid Reference): 아직 메모리에 로드되지 않은 페이지이므로, 해당 페이지를 메모리에 가져옴 (Page-in)
- 빈 프레임 할당
- 보조 저장장치에서 페이지 읽기 (Disk I/O 수행)
- 페이지 테이블 및 내부 테이블 수정
- 페이지가 메모리에 로드되었음을 페이지 테이블과 내부 테이블에 반영
- 페이지 테이블의 해당 페이지를 "유효(valid)" 상태로 변경
- 중단된 명령어 재시작
- 순수 요구 페이징(Pure Demand Paging)
- 프로세스를 실행할 때 처음에는 메모리에 아무 페이지도 로드하지 않음
- 첫 번째 명령어를 실행하려 하면 해당 페이지가 메모리에 없으므로 페이지 폴트(Page Fault) 발생
- 필요한 페이지가 하나씩 메모리에 로드되면서 프로그램이 실행됨
- 결국 필요한 모든 페이지가 메모리에 로드되면 더 이상 페이지 폴트 없이 실행됨
10.4 페이지 교체(Page Replacement)
페이지 교체의 필요성
- 프로세스가 실제 사용하는 페이지만 로드하면 메모리를 효율적으로 사용할 수 있음
- 하지만 예기치 않은 메모리 부족 문제 발생 가능
- 스와핑 대신 페이지 교체 알고리즘을 사용하여 문제 해결
- 효율적인 페이지 교체 기법이 운영체제 성능을 결정하는 중요한 요소
10.4.1 Basic Page Replacement
페이지 교체의 개념
- 운영체제에서 프로세스가 필요한 페이지가 메모리에 없는 경우(페이지 폴트 발생), 해당 페이지를 보조 저장장치에서 메모리로 불러와야 함
- 메모리에 빈 프레임이 없다면, 기존에 사용 중인 프레임을 해제하고 새 페이지를 로드하는 과정을 페이지 교체(Page Replacement)라고 함
페이지 교체 과정
- 보조 저장장치(디스크)에서 필요한 페이지의 위치를 찾음
- 메모리에서 빈 프레임을 찾음
- 빈 프레임이 있다면 그대로 사용
- 빈 프레임이 없다면, 페이지 교체 알고리즘을 사용하여 대체할 페이지(희생 페이지)를 선택
- 선택된 페이지가 수정된 상태라면, 해당 내용을 보조 저장장치에 저장
- 새로운 페이지를 메모리에 로드하고, 페이지 테이블을 업데이트
- 페이지 폴트가 발생했던 위치에서 프로세스를 재개
수정 비트(Modify Bit, Dirty Bit) 활용
- 수정 비트(Dirty Bit): 페이지가 메모리에 로드된 이후 수정되었는지 여부를 표시하는 비트
- 수정된 페이지 → 페이지 교체 시 반드시 보조 저장장치에 저장해야 함
- 수정되지 않은 페이지 → 단순히 메모리에서 제거하면 되므로 I/O 비용을 절반으로 줄일 수 있음
페이지 교체의 중요성
- 가상 메모리 시스템에서 필수적인 기능으로, 논리 메모리와 물리 메모리를 완전히 분리할 수 있음
- 메모리 크기에 구애받지 않고 더 큰 프로세스를 실행할 수 있도록 함
- 효율적인 페이지 교체 알고리즘이 시스템 성능에 큰 영향을 미침
10.4.2 FIFO 페이지 교체 (FIFO Page Replacement)
- 가장 단순한 페이지 교체 알고리즘
- 가장 먼저 메모리에 들어온 페이지를 가장 먼저 내보냄
- 구현 방법:
- 각 페이지가 메모리에 들어온 시간을 기록하거나 큐(Queue) 를 사용
- 새로운 페이지가 들어오면 큐의 맨 앞(오래된 페이지) 제거 → 맨 뒤에 새 페이지 추가
- 문제점:
- 최근에 자주 사용되는 페이지도 무조건 교체될 수 있음 → 페이지 폴트 증가
- 벨라디의 역설(Belady’s Anomaly) 발생 가능
- 메모리 프레임 수를 늘려도 페이지 폴트 수가 증가하는 현상
10.4.3 최적 페이지 교체 (Optimal Page Replacement)
- 가장 오랫동안 사용되지 않을 페이지를 교체하는 방식
- 이론적으로 가장 낮은 페이지 폴트율을 보장
- 구현 방법:
- 앞으로 올 페이지 참조 패턴을 미리 알고 있어야 함
- 가장 오랫동안 사용되지 않을 페이지를 선택하여 교체
- 문제점:
- 실제 구현이 불가능 (미래의 페이지 참조 순서를 알 수 없음)
- 연구 및 비교 분석을 위한 기준점으로 사용됨
10.4.4 LRU 페이지 교체 (LRU Page Replacement)
- 가장 오랫동안 사용되지 않은 페이지를 교체하는 방식
- 과거 데이터를 기반으로 미래를 예측 → OPT 알고리즘을 현실적으로 근사
- 구현 방법:
- 카운터 방식
- 모든 페이지에 마지막 사용 시간(time-stamp) 을 저장
- 페이지를 교체할 때 가장 오래 전에 사용된 페이지를 제거
- 문제점: 매번 시간 값을 업데이트하고 정렬해야 하므로 오버헤드 큼
LRU Page Replacement 알고리즘
- 스택 방식
- 페이지 번호를 스택(연결 리스트)로 관리
- 새로운 페이지가 참조될 때 스택의 맨 위로 이동
- 가장 오랫동안 사용되지 않은 페이지는 항상 스택의 맨 아래에 위치
- 문제점: 스택 조작을 위한 추가적인 하드웨어가 필요
- 카운터 방식
10.5 페이지 할당 (Allocation of Frames)
10.5.1 최소 프레임 수
- 모든 프로세스에 최소한의 프레임을 할당해야 함.
- 너무 적은 프레임을 할당하면 페이지 폴트가 증가하여 성능이 저하됨.
- 특정 명령어 실행을 위해 필요한 최소 프레임 수는 컴퓨터 아키텍처에 따라 결정됨.
- 예: 간접 주소 참조를 허용하는 경우 최소 3개 이상의 프레임이 필요함.
10.5.2 할당 알고리즘
- 균등 할당(Equal Allocation): 모든 프로세스에 동일한 수의 프레임을 배분.
- 예: 93개의 프레임을 5개의 프로세스에 배분하면 각 프로세스는 18개를 받음.
- 비례 할당(Proportional Allocation): 프로세스 크기에 따라 프레임을 배분.
- 예: 10KB 프로세스와 127KB 프로세스가 있는 경우 62개 프레임을 4:57로 나눔.
- 우선순위 기반 할당: 프로세스 크기뿐만 아니라 우선순위를 고려하여 프레임을 배분.
- 높은 우선순위의 프로세스가 더 많은 프레임을 받을 수 있음.
10.5.3 전역 vs 지역 할당
- 전역 할당(Global Replacement)
- 모든 프로세스가 시스템 전체에서 프레임을 교체할 수 있음.
- 한 프로세스가 다른 프로세스의 프레임을 가져갈 수 있음.
- 시스템 처리량이 증가하지만 개별 프로세스 성능이 예측 불가능해짐.
- 지역 할당(Local Replacement)
- 프로세스가 자신에게 할당된 프레임 내에서만 페이지 교체 가능.
- 개별 프로세스의 성능은 안정적이지만, 전체 시스템 효율성은 떨어질 수 있음.
전역 페이지 교체 전략
- 특정 임계값 이하로 여유 프레임이 줄어들면 커널이 페이지 교체를 시작.
- 프레임이 최대 임계값에 도달하면 페이지 회수가 중지됨.
- 리퍼(Reaper) 루틴이 페이지 교체를 수행하며, 보통 LRU(Least Recently Used) 방식 사용.
- 여유 메모리가 부족하면 더욱 적극적으로 페이지 회수를 수행할 수도 있음.
- 극단적인 경우, OOM(Out-Of-Memory) 킬러가 실행되어 메모리를 많이 사용하는 프로세스를 종료함.
10.5.4 비균일 메모리 접근(NUMA, Non-Uniform Memory Access)
- NUMA 시스템에서는 메모리 접근 시간이 동일하지 않다고 가정
- NUMA 시스템에서는 여러 개의 CPU가 각자의 로컬 메모리(Local Memory) 를 가지며, CPU는 자신의 로컬 메모리에 더 빠르게 접근할 수 있음.
- 다른 CPU의 로컬 메모리에 접근할 경우 지연(latency)이 증가하여 성능이 저하됨.
- 하지만 NUMA 시스템은 더 많은 CPU를 수용할 수 있어, 병렬 처리와 시스템 처리량을 증가 시킬 수 있음.
10.6 스래싱(Thrashing)
스래싱(Thrashing)은 프로세스가 실행보다 페이지 교체(Page Faulting)에 더 많은 시간을 소비하는 현상을 의미함.
이로 인해 성능이 심각하게 저하되며, 시스템이 거의 멈추는 상태가 됨.
10.6.1 스래싱의 원인 (Cause of Thrashing)
기본 개념
- 프로세스가 실행을 위해 필요한 최소한의 프레임(Frame, 페이지 저장 공간)을 확보하지 못할 경우 발생.
- 페이지 부재(Page Fault) 발생 → 페이지 교체가 필요 → 현재 사용 중인 페이지를 교체 → 교체된 페이지가 다시 필요해 반복적인 페이지 폴트 발생.
- 프로세스가 페이지를 계속 교체하느라 실행을 제대로 하지 못하는 상황이 됨.
스래싱 발생 과정
- 운영체제는 CPU 사용률을 모니터링하고, 사용률이 낮으면 다중 프로그래밍 정도(실행 프로세스 수)를 증가시킴.
- 새로운 프로세스가 실행되면서 더 많은 프레임이 필요하게 됨.
- 전역 페이지 교체(Global Page Replacement)가 적용되면, 운영체제가 특정 프로세스가 아닌 전체 프로세스에서 무작위로 페이지를 교체함.
- 한 프로세스가 더 많은 프레임을 차지하면, 다른 프로세스들이 부족한 프레임을 가지게 되어 추가적인 페이지 부재가 발생함.
- 결과적으로, 모든 프로세스가 서로 프레임을 빼앗으며 페이지 교체를 반복하는 스래싱 현상 발생.
스래싱 발생 시 결과
- 프로세스가 페이지 교체에만 집중 → CPU 사용률 급감.
- 운영체제가 이를 해결하려고 더 많은 프로세스를 실행 → 문제 악화.
- 시스템 전체의 처리량(Throughput) 급락.
- 메모리 접근 시간 증가 → 전체 성능 저하.
스래싱을 줄이는 방법
- 로컬 교체(Local Replacement) 또는 우선순위 교체(Priority Replacement) 사용
- 특정 프로세스가 자신에게 할당된 프레임 내에서만 페이지를 교체하도록 제한.
- 프로세스에 충분한 프레임 할당
- 프로세스가 정상적으로 실행되려면 현재 실행 중인 코드와 데이터를 저장할 충분한 프레임 필요.
- 프레임 수가 부족하면 스래싱 발생 가능성 높아짐.
- 지역성(Locality) 개념 활용
- 프로세스는 특정 시간 동안 특정한 페이지 집합(지역성, Locality)을 집중적으로 사용.
- 지역성이 유지되는 동안 필요한 페이지를 미리 로드하면 페이지 폴트를 줄일 수 있음.
- 지역성(Locality) 개념과 스래싱 방지
- 프로세스는 실행 중에 지역성을 변경하면서 새로운 페이지 집합을 사용.
- 운영체제가 현재 지역성을 유지할 수 있는 충분한 프레임을 할당하면 스래싱 방지 가능.
- 반대로, 현재 지역성 크기보다 적은 프레임을 할당하면 스래싱 발생.
- 지역성(Locality) 개념과 스래싱 방지
위 그림에서 '시간 a'의 지역성은 페이지 집합 {18, 19, 20, 21, 22, 23, 24, 29, 30, 33} 이다. '시간 b'의 지역성은 페이지 집합 {18, 19, 20, 24, 25, 26, 27, 28, 29, 31, 32, 33} 으로 변경
10.6.2 작업-집합 모델 (Working-Set Model)
변화량만큼 페이지 참조를 관찰하여 그 안에 들어있는 서로 다른 페이지들의 집합을 작업 집합(working set)이라 한다.
10.6.3 페이지 폴트 빈도(Page-Fault Frequency)
- 스래싱은 높은 페이지 폴트 비율을 동반하므로, 페이지 폴트 비율의 상한선과 하한선을 두어 조절함
- 상한선 및 하한선 설정: 실제 페이지 부재율이 상한선을 초과하면 해당 프로세스에 프레임을 추가로 할당하고, 반대로 하한선 아래로 떨어지면 프레임을 회수한다.
- 프로세스 스와핑: 만약 페이지 부재율이 증가하고 더 이상 사용 가능한 프레임이 없다면, 일부 프로세스를 백업 저장소로 스와핑하여 프레임을 해방시킨다. 이렇게 해방된 프레임은 높은 페이지 부재율을 보이는 다른 프로세스에 재분배.
10.7 메모리 압축(Memory Compression)
- 메모리 압축은 페이징(Paging)의 대안으로, 프레임을 압축하여 메모리에 저장하는 방식.
- 장점: 메모리 사용량을 줄이면서도 성능 저하를 최소화할 수 있음.
메모리 압축의 원리
- 운영체제는 일정 기준 이하로 사용 가능한 프레임 수가 줄어들면 페이지 교체를 수행.
- 기존 방식(페이징): 프레임을 스왑 공간으로 이동 → 이후 다시 로드할 때 페이지 폴트(Page Fault) 발생.
- 메모리 압축 방식:
- 여러 개의 프레임을 하나의 프레임에 압축하여 저장.
- 압축된 프레임은 ‘압축 프레임 리스트(Compressed Frame List)’에 저장.
- 필요할 경우 압축 해제하여 원래 프레임을 복원(페이지 폴트 발생 시).
예시> 압축전
- 사용 가능한 free-frame 리스트에 여유 공간이 6개 있음.
- 프레임 15, 3, 35, 26이 페이지 교체 대상으로 선택됨.
- 기존 방식이라면 이 프레임들이 스왑 공간으로 이동.
압축후
- 프레임 15, 3, 35를 하나의 프레임(프레임 7)에 압축 저장.
- 이제 15, 3, 35는 free-frame 리스트에서 제거되고, 대신 프레임 7이 압축 프레임 리스트에 추가됨.
- 필요하면 압축 해제 후 다시 메모리에 복구.
10.8 커널 메모리 할당 (Allocating Kernel Memory)
- 운영체제에서 커널(Kernel)은 자체적인 메모리 할당 방식이 필요함.
- 이유:
- 커널은 다양한 크기의 데이터 구조를 요청 → 조각화(Fragmentation) 방지 필요
- 물리 메모리에 직접 접근하는 특정 하드웨어 장치는 연속된(Contiguous) 메모리를 요구
이를 해결하기 위한 두 가지 커널 메모리 할당 전략
- 버디 시스템(Buddy System)
- 슬랩 할당(Slab Allocation)
10.8.1 버디 시스템 (Buddy System)
- 연속된(Contiguous) 페이지 단위의 메모리를 고정 크기로 분할하여 할당하는 방식.
- 2의 거듭제곱 단위(4KB, 8KB, 16KB...)로 메모리를 분할하여 관리.
- 요청된 크기보다 큰 가장 작은 2의 거듭제곱 크기 메모리를 할당.
- 예: 11KB 요청 → 16KB 할당
- 예: 21KB 요청 → 32KB 할당
버디 시스템 할당 예시
- 초기 메모리 크기: 256KB
- 21KB 요청 발생 → 32KB 할당 필요
- 256KB를 두 개의 128KB로 분할 → 128KB를 다시 64KB로 분할
- 64KB를 다시 32KB로 분할 → 32KB 중 21KB를 사용 (나머지는 내부 단편화)
- 할당된 32KB는 버디(짝) 시스템(CL, CR) 중 CL에 배정됨
10.8.2 슬랩 할당 (Slab Allocation)
- 슬랩(Slab): 하나 이상의 연속된(Contiguous) 페이지로 구성된 메모리 블록
- 캐시(Cache): 특정 커널 데이터 구조를 저장하는 공간
- 객체(Object): 특정 커널 데이터 구조의 인스턴스
슬랩 할당의 메모리 상태
- Full (모든 객체 사용 중)
- Empty (모든 객체 사용 가능)
- Partial (일부 사용 중, 일부 사용 가능)
슬랩 할당 예시
- 리눅스에서 프로세스 디스크립터(Process Descriptor) 할당 시
- struct task_struct 데이터 구조 사용 (약 1.7KB 필요)
- 슬랩 할당자는 이미 존재하는 객체 중 사용되지 않은 것을 할당
- 새로운 객체가 필요하면 슬랩을 확장하여 추가 할당
'운영체제 공룡책' 카테고리의 다른 글
| [운영체제 공룡책] 12장 I/O Systems (0) | 2025.03.22 |
|---|---|
| [운영체제 공룡책] 11장 Mass -Storage Structure (0) | 2025.03.19 |
| [운영체제 공룡책] 9장 메인 메모리 (0) | 2025.03.17 |
| [운영체제 공룡책] 8장 교착상태 (1) | 2025.01.25 |
| [운영체제 공룡책] 7장 동기화 예제 (0) | 2025.01.15 |