[OS] Memory #2

1. Fetch Policy

Demand Paging
페이지에 접근이 있을 때만 메모리에 적재하는 방식
처음엔 페이지 폴트가 많지만 지역성 원리에 따라 점차 줄어든다.

Prepaging: 필요한 페이지 외에 근처 페이지도 미리 적재하는 방식
적재된 페이지가 사용되지 않으면 비효율적

2. Placement Policy
세그먼테이션에서는 중요하지만(처음 어떻게 배치되느냐에 따라 컴팩션 달라질 수..)
페이징에서는 별로 중요하지 않다

3. Replacement Policy

Frame Locking: 교체를 방지하기 위해 프레임에 잠금을 설정하여 메모리에 유지되도록 하는 것

Optimal: 가장 나중에 참조될 페이지를 교체 대상으로 선정 (미래를 다 알아야 하기 때문에 현실적으로 불가능)
LRU(Least Recently Used): 가장 오래 전에 참조한 페이지를 교체 대상으로 선정
FIFO: 가장 오래 전에 들어온 페이지를 교체 대상으로 선정 (오래 전에 들어왔어도 사용 될 수 있다)
Clock: 처음 들어오거나 참조되면 use-bit 1이 되고, 원형 큐에서 0인 페이지를 찾아서 교체 대상으로 선정

(일단 프레임에 있는 페이지가 들어오면 그대로 진행)
(프레임에 없는 페이지가 들어오면)
(OPT는 뒤로 가면서 나오는 페이지 빼다가 가장 마지막에 빠지는 애 교체)
(LRU는 앞으로 가면서 나오는 페이지 빼다가 가장 마지막에 빠지는 애 교체)
(FIFO는 교체된 칸 기억해 뒀다가, 교체해야 하면 다음 칸 교체: 점 이동은 폴트 날 때에만)
(CLOCK는 새로 추가/이미 있는 프레임이면 * 넣고, 없으면 *떼면서 다음 칸으로: 점 이동 & 떼는 것은 폴트 날 때에만)

(FIFO랑 CLOCK에서 .은 반드시 순차적으로 진행)

Page Buffering (=Page Cache): 교체된 페이지를 메모리에 잠시 유지해 재참조 시 비용을 줄이는 기법

Free Frame List에 있는 프레임 최대한 먼저 쓰고
Modified Page List에 있는 애들의 프레임을 쓰려면 디스크로 가서 수정해 주고 와서 써야하기
때문에 시간이 걸린다
Modified Page List에 있는 애들 모아뒀다가 한 번에 팍 적고 FFL로 옮겨 주는 cluster하면 효율적으로 운용 가능

Fixed-allocation: 프로세스에 고정된 수의 프레임을 할당, 폴트 시 해당 프로세스 내에서 페이지를 교체
Variable-allocation: 페이지 폴트율에 따라 할당된 프레임 수를 동적으로 조절, 효율적이나 오버헤드가 발생

Local replacement policy: 폴트 시 프로세스의 페이지만 교체 후보로 고려
Global replacement policy: 폴트 시 언락인 모든 페이지를 교체 후보로 고려

fixed implies local
variable can be either local global
variable + local: 폴트율에 따라 동적으로 조절되되, 프로세스의 페이지만 가능
variable + global: 폴트율에 따라 동적으로 조절되되, 메모리의 모든 프레임 선택 가능 (레지던트 셋 크기 변경)

레지던트 셋 할당이 너무 적으면: 페이지 폴트 증가로 시스템이 느려짐
레지던트 셋 할당이 너무 많으면: 메모리 내 프로세스 수가 줄어 CPU Utilization이 떨어짐

Variable+gloabal
페이지 폴트 발생 시,
FFL에 free frame이 있으면 레지던트 셋에 추가하고,
FFL이 비어있으면, 다른 프로세스의 레지던트 셋에서 하나 뺏어서 자신의 레지던트 셋에 넣는다
=> 이런 식으로 작동하면 비효율 초래 가능
==> 해결: Page Buffering

4. Cleaning Policy
modified page는 반드시 디스크에 기록되어야 하는데.

Demand Cleaning
modified page를 페이지 교체 시 디스크에 기록하는 방법
페이지 폴트 시 두 번의 디스크 접근으로 CPU 활용도가 낮아질 수 있다.

Precleaning
modified page를 미리 미리 디스크에 기록해두고, 실제 교체 시 지연을 줄이는 방법
한 번 수정된 페이지들은 다시 수정될 가능성 높기 때문에 디스크 기록이 더 많이 필요할 수 있다

5. Load Contorol

메모리 내의
너무 적은 프로세스 수는 스와핑이 늘어난다
너무 많은 프로세수 수는 스레싱이 늘어난다

L = 페이지 폴트 간 시간
S = 페이지 폴트로 처리 시간

L > S: 폴트 발생 x, 너무 안정됨 => CPU 활용률이 너무 낮다
L < S: 처리하기도 전에 또 다른 폴트 발생 => 스레싱
L = S일 때 최적이다

Clock이 너무 천천히 돈다: CPU 활용률이 너무 낮다
Clock이 너무 빨리 돈다: 페이지 폴트가 너무 많이 발생, 스레싱 (멀티프로그래밍 레벨을 줄여야 한다)

멀티프로그래밍 레벨을 줄이기 위한 Process suspension 기준
우선순위가 가장 낮은 프로세스,
페이지 폴트를 일으킨 프로세스,
마지막으로 활성화된 프로세스(최근에 들어왔으니까 레지던트 셋 작을 것이므로),
레지던트 집합이 가장 작은 프로세스,
가장 큰 프로세스(한 방에 큰 공간 확보할 수 있으므로),
남은 실행 시간이 가장 긴 프로세스(짧게 남은 애들 빨리 빨리 처리하기 위해서).

I/O Buffering -> I/O 성능을 높일 수 있다

블록 지향 장치(Block-oriented device)
고정 크기 블록 단위로 데이터 전송 (예: 디스크, USB)

스트림 지향 장치(Stream-oriented device)
바이트 스트림 형태로 데이터 전송하며 (예: 터미널, 프린터, 포트, 마우스)

Disk Scheduling

PRI: 우선순위대로 처리
FIFO: 요구순서대로 처리
SSTF(Shortest Service Time First): 근처에 있는 요청 먼저 처리(멀리 있는 요청 기아 가능)
SCAN: 한번 주욱 갔다가 주욱 오면서 요청 처리 (최대 2*h 대기)
LOOK: SCAN과 유사하지만 끝까지 가지 않고, 더 이상 요청이 없을 때 방향을 바꿔 불필요한 이동을 줄인다.
C-SCAN: 한 방향으로만 스캔 (최대 h+c 대기)
N-step-SCAN: 큐를 길이 N의 하위 큐로 나누고 각 큐를 SCAN으로 처리
(N이 너무 작으면 C-SCAN이랑 동일, N이 너무 크면 FIFO랑 동일)
arm stickiness problem: 디스크 암이 특정 구간에 머물러 다른 요청이 오래 대기하는 현상
FSCAN: 두 개의 하위 큐를 사용해,
한 큐에만 요청을 모으고 다른 큐는 주욱 실행하고,
다른 큐의 실행이 끝나면 해당 큐에서 요청을 모으고 다른 큐에서 요청을 주욱 실행하는 방법

RAID
여러 독립 디스크를 하나의 논리 드라이브로 구성해
데이터를 스트라이핑하고, 패리티를 통해 고장 시 데이터 복구를 보장하는 것

RAID 0: 중복성 없이 데이터를 디스크에 스트라이핑해 성능을 높이나 데이터 보호 기능은 없다.