memory

Oak_Cassia·2022년 2월 22일

Stall

메모리 접근 지연으로 인한 파이프라인 정지 현상
Cache 등을 활용하여 메모리 지연 시간을 단축

메모리 바인딩과 주소

메모리 보호

합법적(legal) 메모리 주소 영역을 설정하여, 해당 프로세스가 허용된 주소 범위만 접근하도록 제한
프로세스마다 별도의 메모리 공간 보장

바인딩 시점
Compile time binding

파일 시점에 프로세스의 물리적 적재 위치를 이미 알고 있다면, 컴파일러가 절대 주소 생성
논리 주소와 물리 주소가 동일하게 구성

Load time binding

컴파일 시점에 물리적 위치를 모르면, 컴파일러는 재배치 가능(relocatable) 코드를 생성.
실제 물리 주소는 프로그램이 메모리에 적재될 때 결정.

Execution time binding

실행 중 프로세스의 메모리 위치가 바뀔 수 있음(페이징, 세그멘테이션).
이를 위해 MMU(Memory Management Unit)를 사용.

논리주소(Logical Address)와 물리주소(Physical Address)

논리(가상) 주소: CPU가 생성하는 주소, 각 프로세스마다 0번지부터 시작.\
물리 주소: 실제 메모리 상의 주소.
실행 시점 바인딩 시, MMU가 논리 주소를 동적으로 물리 주소로 변환

Memory management unit(MMU)

가상(논리) 주소를 물리 주소로 변환하는 하드웨어.
Relocation(Base) register: 모든 주소에 오프셋(기준값)을 더해 최종 물리 주소 생성
Limit register: 주어진 영역의 상한(유효 주소 범위)
CPU 스케줄러가 프로세스를 선택하면, 디스패처는 문맥 교환 시 Relocation Register와 Limit Register를 적재하여 메모리 보호

동적 로딩, 동적 링크

Dynamic Loading

실제로 필요한 루틴만 호출 시점에 메모리에 가져오는 기법
각 루틴은 재배치 가능한 상태로 디스크에 대기하며, 필요 시에만 적재되어 메모리 사용량 절약
메모리에 루틴이 없으면 relocatable linking loader가 루틴을 가져오고 테이블에 기록

Dynamic Linking & Libraries

여러 프로세스가 라이브러리 코드를 동시에 공유 가능
OS가 실제 링크(결합) 과정을 지원해야 하며, 공통 라이브러리 코드를 메모리에 한 번만 적재해 효율적으로 사용

연속 메모리 할당, 단편화

Contiguous Memory Allocation

각 프로세스가 하나의 연속된 메모리 영역을 차지
가변 파티션 기법 사용 시, OS는 “가용 블록(hole)”과 “사용 중인 블록” 정보를 유지

First Fit(첫 가용 크기), Best Fit(가장 작은 크기), Worst Fit(가장 큰 크기)

Fragmentation

External
- 프로세스가 메모리에 적재·해제되는 과정에서 생기는 자잘한 유휴 공간
- 압축으로 해결 가능하지만 오버헤드가 큼(GC)
Internal
- 정해진 블록(프레임)이 프로세스 요구 크기보다 커서 남는 부분이 생김

페이징

프로세스를 연속되지 않은 물리 메모리에 배치할 수 있도록 하는 기법
물리 메모리를 일정 크기의 프레임(frame)으로 나누고, 프로세스도 동일 크기의 페이지(page)로 분할
페이지 <-> 프레임 단위로 매핑

주소 변환(MMU)

논리 주소 = (페이지 번호 p, 페이지 오프셋 d)
페이지 테이블에서 p에 해당하는 프레임 번호 f를 찾음
최종 물리 주소 = (f, d)
장점: 외부 단편화가 없음(프레임 단위로 분산 배치 가능)
단점: 페이지 단위로 내부 단편화 발생 가능

논리주소 공간의 크기가 $2^m$ 이고 페이지의 크기가 $2^n$ 바이트인 경우 논리주소 상위 m-n비트는 페이지 번호이고 하위 n비트는 오프셋이다.

페이지 테이블

각 프로세스마다 페이지 테이블을 갖고, 페이지 번호 ↔ 프레임 번호 대응 정보를 저장
PTBR(Page Table Base Register): 페이지 테이블의 시작 주소
- 문맥 교환 시 프로세스별 PTBR 세팅
PTLR(Page Table Length Register): 페이지 테이블 크기)
- 주소가 유효 범위인지 확인

페이지 테이블 엔트리 정보

페이지/프레임 번호
유효 비트: 해당 페이지가 메모리에 존재하는지 (메모리: 1, 보조기억장치: 0)
- 0에 접근 시 페이지 폴트
보호 비트: r, w, x(실행) 접근 권한
참조 비트: CPU가 해당 페이지를 참조했는지
수정/더티 비트: 페이지에 쓰기가 발생했는지
- 수정한 적이 없으면 보조 기억장치 반영 안해도 됨

메모리의 페이지 테이블에 한 번 접근, 실제 프레임에 한 번 접근

두 번 접근해야하는 결과가 생김

TLB(Translation Look-aside Buffer)

페이지 테이블 조회를 캐싱하여 주소 변환 속도를 높임
최근에 참조된 페이지 번호↔프레임 번호 매핑을 저장
- 참조 지역성에 따라 선정
MMU가 TLB Miss 시 페이지 테이블 접근
커널 코드 같은 특정 항목을 TLB에 고정
ASID(Address Space Identifier): TLB 엔트리가 어느 프로세스 것인지 식별
- ASID가 없으면 문맥 교환 시마다 TLB Flush해야 함

대형 페이지 테이블 문제

페이지 테이블이 너무 크면 전부 메모리에 둘 수 없음
Hierarchical Paging(다단계/계층적 페이지 테이블)
- Outter Page Table(바깥 테이블) → 실제 페이지 테이블
- CPU와 가장 가까이 위치한 Outer 페이지 테이블만 메모리에 유지하면 됨
Hashed Page Table
- 주소공간이 큰(64비트 이상) 시스템에서 해시를 통해 매핑
Inverted Page Table
- “프레임” 단위로 어느 프로세스의 어떤 페이지인지 저장
- 테이블 크기를 물리 메모리 기준으로 유지

Shared pages

여러 프로세스가 공통 코드를 공유하여 메모리 절약 (읽기 전용)
Copy-On-Write: 부모 자식은 페이지를 공유하다가, 쓰기가 발생하면 그 시점에 복사

Swapping

프로세스를 메모리에서 보조저자장치로 내보낸 뒤 다시 가져오는 기법
전통적: 전체 프로세스
페이징 결합 방식: 필요한 페이지 단위로 스왑

가상 메모리

프로그램 전체가 메모리에 올라오지 않아도 실행 가능하도록 하는 기법
물리 메모리와 논리 메모리를 분리하여, 메모리를 큰 가상 주소 공간처럼 다룸
파일, 라이브러리 공유 및 공유 메모리 구현이 용이

가상 주소 공간

일반적으로 코드/데이터/힙과 스택이 분리된 형태로 배치
힙(heap): 동적 할당 메모리를 위로 확장
스택(stack): 함수 호출을 거듭하며 아래로 확장
힙과 스택 사이에 공백이 존재하므로, 가상 메모리는 공간을 효율적으로 관리하면서도 공유 영역을 만드는 데 도움
요구 페이징: 당장 필요한 페이지만 적재
- 페이지가 없으면 페이지 폴트 -> 디스크에서 가져온 뒤 재시도
- 순수 요구 페이징: 최초 시작 시 어떤 페이지도 올리지 않고, 필요한 순간에만 적재

요구 페이징 Demand Paging

현재 필요한 페이지만 메모리에 적재
존재하지 않는 페이지에 접근 시 페이지 폴트 발생 → 디스크에서 해당 페이지 로드 후 재시도
Pure Demand Paging: 프로그램 시작 시 어떠한 페이지도 미리 적재하지 않고, 요청 순간에만 적재

Page-fault trap

프로세스가 메모리에 적재되어 있지 않은 페이지에 접근하려 할 때 발생

접근하려는 페이지가 유효한지 내부 테이블(PCB 등)로 확인
유효하나 “메모리에 없는 경우”라면, 빈 프레임을 찾는다(free frame list)
보조저장장치에서 해당 페이지를 읽어, 빈 프레임에 적재
페이지 테이블 갱신
중단됐던 명령어 재실행

Free-Frame List

시스템 시작 시 모든 가용 메모리는 “가용 프레임 리스트”에 들어 있음
dy청이 발생하면 프레임 하나를 리스트에서 꺼내 할당
다 사용되고 리스트가 임계값 이하로 떨어지면 OS가 다시 확보
zero-fill-on-demand: 프레임 할당 전 0으로 채우는 기법, 연결리스트로 구성

요구 페이징 성능

페이지 폴트 확률(p)에 따라 실질 접근 시간 상승
메모리 접근 시간(ma)대비, 디스크 접근은 수백~수천 배 느리므로 p가 낮아야 효율적

요구 페이징의 특성 중 하나는 스왑 공간의 관리이다. 스왑 공간에서의 디스크 I/O는 파일 시스템의 입출력 보다 일반적으로 빠르다.
시스템은 더 나은 페이징 처리량을 갖기 위해 전체 파일 이미지를 스왑 공간에 복사할 수 있다. (좋은 방법은 아니다.)
또는 페이지 들이 교체될 때 스왑 공간에 기록하는 방법도 있다. (실질적으로 이 방법 사용)
Binary file(실행 파일)을 스왑 공간에 넣지 않기. 페이지 교체 당할 때 그대로 덮어쓸 수 있다.
Anonymous memory: 스택 및 힙. 스왑 공간이 필요한 메모리 혹은 페이지

Page Replacement

빈 프레임이 없다면 사용되지 않는 프레임을 찾아 비운다.

보조저장 장치에서 필요한 페이지의 위치를 알아낸다.
빈 페이지 프레임을 찾는다.
A. 빈 페이지가 없다면 victim frame을 선정하기위해 페이지 교체알고리즘 가동
B. 희생될 페이지를 보조저장장치에 기록하고, 관련 테이블을 수정한다.
빼앗은 프레임에 새 페이지를 읽어와 테이블을 수정한다.
페이지 폴트가 발생한 지점에서 프로세스를 계속한다.

빈 프레임이 없는 경우에 디스크를 두 번 접근해야 한다. 페이지 폴트 처리시간 2배

Reference string

알고리즘을 적용해 페이지 폴트 발생 횟수를 계산하여 평가한다.

FIFO 페이지 교체

first in first out
Belady’s anomaly: 프레임의 개수가 늘었는데 오히려 페이지 폴트 횟수가 늘어나는 현상.

Optimal Page Replacement(최적 페이지 교체)

가장 오래 사용되지 않을 페이지를 찾아서 교체
- 실제 구현이 어려움

LRU page replacement (Least-recently-used)

오랫동안 사용되지 않은 페이지를 교체
페이지 마다 마지막 사용시간을 유지한다. 하드웨어 지원이 필요하다.
Counters: 각 페이지 항목마다 사용시간 필드를 넣고 CPU에 논리적인 타이머와 counter를 추가한다. 메모리가 접근될 때 마다 시간은 증가한다. 페이지에 참조할 때 시간 레지스터의 내용이 페이지의 사용시간 필드에 복사된다.
Stacks: 페이지 번호의 스택을 유지하는 방법. 페이지가 참조되면 스택 중간에서 제거되어 꼭대기로 간다.

LRU Approximation Page Replacement

하드웨어의 한계로 LRU도 쉽지 않다.
Reference bit: 처음에 OS에의해 0으로 채워지고 프로세스 실행 중 참조되면 1
Additional-Reference Bits Algorithm: 각 페이지에 8비트의 참조 비트를 할당한다. 일정시간마다 타이머 인터럽트를 걸어서 OS가 참조비트를 최상위 비트로 이동시키고 나머지 비트는 오른쪽으로 이동시킨다.
Second-chance Algorithm: FIFO에서 참조 비트가 0이면 교체. 1이면 0
Enhanced Second-chance Algorithm:

(0,0) 최근사용 X, 변경 X
(0,1) 최근 사용 X, 변경 O
(1,0) 최근 사용 O , 변경 X
(1,1) 최근 사용 O, 변경 O

스레싱 Thrashing

과도한 페이징으로 인해 CPU가 실제 작업보다 페이지 교체에 시간을 더 많이 소비하는 현상
프로세스 간 프레임을 빼앗는 방식과 프레임 부족이 결합하면 발생 가능
CPU 이용률 하락 → CPU 스케줄러가 새 프로세스를 추가 → 더 심한 프레임 부족 → 계속 스래싱… (악순환)
해결 방안
- 다중프로그래밍 정도(메모리에 동시에 올라온 프로세스 수)를 줄여 충분한 프레임을 확보
- Local Replacement(프로세스 내부에서만 교체) 사용
- Working Set Model: 최근 \Delta번 메모리 참조에 등장한 페이지 집합(Working Set)을 기준으로, 프로세스가 실제 필요로 하는 최소 프레임 수 추정
- Page-Fault Frequency(PFF): 페이지 폴트율이 상한을 넘으면 프레임을 더 주고, 하한 아래면 회수