Swap / Replacement Policies / Thrashing

프로세스의 어떤 데이터는 디램에, 어떤 데이터는 디스크 상에 존재할 수도 있음

자주 접근하는 데이터는 메모리에 두고,

잘 안쓰는 데이터는 디스크에 둘 수 있음 => 디맨드 로딩

 

스왑 공간

디스크 상의 공간

파일 시스템에서 첫번째에 루트 파일 시스템, 두번째 파티션에 스왑 공간을 둘 수 있음

메모리에 있는 데이터를 디스크로 이동할 때 스왑 공간을 사용

메모리 스페이스가 부족할 때 스왑함

 

어떤 단위로 옮기느냐

-> 페이지나 프로세스 단위

언제: light(페이지) VS heavy(프로세스) 메모리 헝그리 컨디션

어떻게: replacement policy (LRU pages, low-priority processes)

 

Benefit

- 프로세스를 위한 버추얼 메모리가 엄청 큰 것처럼 

- 프로그래머한테 투명함 (vs memory overlay)

 

Present bit int PTE

- 페이지가 메모리에 있는지 스왑 아웃되었는지 식별용

- 프레젠트 비트가 1 -> 페이지에 접근

- 프레진트 비트가 0 -> Page Fault

 

Page Fault

- 일종의 트랩 (소프트웨어 인터럽트)

- Page Fault 핸들러 트리거 => 디스크에서 메모리로 페이지를 가져옴

- 스왑 아웃 -> 스왑 스페이스로 내림

 

페이징의 특징

- 디맨드 로딩 지원하기 편함

- 하드웨어 프렌들리

- 고정 크기 ...

버추얼 메모리에서 페이지를 로딩한다

-> 파일 시스템 입장에선 inode를 읽는 것임

=> 버추얼 메모리와 파일 시스템이 협동을 하면서 작동

 

HW cotrol flow

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if(Success == True)
    if(CanAccess(TlbEntry.ProtectBits) == True)
        Offset = VirtualAddress & OFFSER_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)
    else
        RaiseException(PROTECTION_FAULT)
else
    PTEAddr = PTBR + (VPN * sizeof(PTE))
    PTE = AccessMemory(PTEAddr)
    if(PTE.Valid == False)
        RaiseException(SEGMENTATION_FAULT)
    else if(PTE.Present == True)
        TLB_INSERT(VPN, PTE.PFN, PTE.ProtectBits)
        RetryInstruction()
    else if(PTE.Present == False)
        RaiseException(PAGE_FAULT)

 

SW control flow

PFN = FindFreePhysicalPage()
if(PFN == -1)
    PFN = EvictPage()
DiskRead(PTE.DiskAddr, pfn)
PTE.Present = True
PTE.PFN = PFN
RetryInstruction()

 

세그멘테이션 파울트와 페이지 파울트의 차이

세그멘테이션 파울트: 인밸리드한 주소에 접근해서 발생. 프로세스를 죽여야 함

페이지 파울트: 합법적인 페이지 접근인데, 물리 메모리에 없을 뿐임. 특정 프레임을 메모리에 올리고 다시 수행, 어떤 프로세스를 중단시키지 않고 허용함

 

Evict

가용 프레임이 없는 경우 기존 프레임 중 하나를 쫓아내야 함

-> 페이지 교체 .. 어떤 페이지를 교체할 것이냐가 이슈

 

디맨드 페이징 (= 디맨드 로딩)

어떤 프로세스를 수행시킬 때 로딩없이 일단 매핑 정보만 만듦

수행 중 매핑만 있으면(페이지 번호는 있는데 프레임이 없음) 페이지 파울트 발생

-> 레이지 매너로 로딩 (실제 사용될 때 되서야 로딩함)

 

가용 공간이 충분하면 별로 문제는 없음

만약 프리 프레임이 부족하다 -> OS한테 일부 페이지를 빼달라 요청 가능

=> 교체 정책(Replacement Policy): 어떤 페이지를 Evict할지 결정

 

교체 시 목표

캐시 히트 최대로 하기 (= 캐시 미스 최소화)

* 물리 메모리는 스왑 공간의 일종의 캐시라 볼 수 있음

 

모델: AMAT (Average memory access time)

[  AMAT = (Phit * Tm) + (Pmiss * Td)  ]

 

Tm: 메모리 액세스 레이턴시

Td: 디스크 액세스 레이턴시

Phit: 캐시 히트 확률 (Pmiss = 1 - Phit)

 

예시

가정: Tm = 100ns, Td = 10ms (10,000,000ns)

Phit = 50% => AMAT = 0.5 * 100 + 0.5*10000000 = 5000050 = 5ms

Phit = 90% => AMAT = 0.9 * 100 + 0.1*10000000 = 1000090 = 1ms

Phit = 99% => AMAT = 0.99 * 100 + 0.01*10000000 = 100099 = 0.1ms

 

이때, 히트율은 정책을 어떻게 짜느냐에 따라 달라짐

 

 

Optimal replacement policy(= MIN)

페이지 교체 시 가정 먼 미래에 참조될 페이지를 교체함

구현은 불가능하고 최고 성능 비교 목적으로 존재, 연구하는 입장에서 유용함

Reference string: 0 1 2 0 1 3 0 3 1 2 1

캐시 사이즈: 3프레임

Access	Hit/Miss	Evict	Resulting Cache State
0	Miss		0
1	Miss		0, 1
2	Miss		0, 1, 2
0	Hit		0, 1, 2
1	Hit		0, 1, 2
3	Miss	2	0, 1, 3
0	Hit		0, 1, 3
3	Hit		0, 1, 3
1	Hit		0, 1, 3
2	Miss	3	0, 1, 2
1	Hit		0, 1, 2

히트율 = 6/11 = 54.5%

Compulsory miss (Cold-start miss)

Capacity miss

Confict miss (direct, set-associate case)

 

FIFO (First In First Out)

Access	Hit/Miss	Evict		Resulting Cache State
0	Miss		First-in->	0
1	Miss		First-in->	0, 1
2	Miss		First-in->	0, 1, 2
0	Hit		First-in->	0, 1, 2
1	Hit		First-in->	0, 1, 2
3	Miss	0	First-in->	1, 2, 3
0	Miss	1	First-in->	2, 3, 0
3	Hit		First-in->	2, 3, 0
1	Miss	2	First-in->	3, 0, 1
2	Miss	3	First-in->	0, 1, 2
1	Hit		First-in->	0, 1, 2

먼저 메모리에 들어왔었던 페이지를 뺌

히트율 = 4/11 = 36.4%

장점: 심플

단점: 로컬리티 고려 안함, Belady's anomaly (캐시가 커졌는데도 캐시 히트율이 떨어질 수 있음)

 

Random

랜덤으로 골라서 쫓아냄

Access	Hit/Miss	Evict	Resulting Cache State
0	Miss		0
1	Miss		0, 1
2	Miss		0, 1, 2
0	Hit		0, 1, 2
1	Hit		0, 1, 2
3	Miss	0	2, 1, 3
0	Miss	1	2, 0, 3
3	Hit		2, 0, 3
1	Miss	3	2, 0, 1
2	Miss		2, 0, 1
1	Hit		2, 0, 1

히트율 = 5/11 = 45.4%

장점: 심플

단점: 로컬리티 고려안함, 예측 안됨

 

LRU (Least Recently Used)

Access	Hit/Miss	Evict		Resulting Cache State
0	Miss		LRU->	0
1	Miss		LRU->	0, 1
2	Miss		LRU->	0, 1, 2
0	Hit		LRU->	1, 2, 0
1	Hit		LRU->	2, 0, 1
3	Miss	2	LRU->	0, 1, 3
0	Hit		LRU->	1, 3, 0
3	Hit		LRU->	1, 0, 3
1	Hit		LRU->	0, 3, 1
2	Miss	0	LRU->	3, 1, 2
1	Hit		LRU->	3, 2, 1

제일 오래 전에 쓰였던 페이지를 내림

히트율 = 6/11 = 54.4%

장점: 로컬리티 고려

단점: 반복문에서 안좋음

 

역사 기반 정책

과거에 참조되는 것들을 고려해서 정책을 결정

* 가장 최근에 쓰인 것: MRU

 

워크로드 예시

No-locality: LRU == FIFO == RAND

로컬리티 있음: LRU > FIFO == RAND

루프: LRU == FIFO < RAND

 

어떻게 LRU를 구현하나?

보통 링크드 리스트로 구현됨

페이지 액세스

- 리스트의 헤드에 삽입 (MRU 포지션)

- 모든 페이지는 다음 포지션으로 이동

- 제거 시 LRU 위치에서 제거

 

그런데 구현이 쉽지 않음

데이터베이스에서는 이 방식이 괜찮음

하지만 메모리에서는, 모든 메모리 액세스를 모니터링 해야하는데

메모리 참조는 하드웨어에 의해 가속되기에 OS가 모니터링하기 쉽지 않음

=> LRU를 근사해야 함

 

 

Clock Algorithm

레퍼런스 비트를 사용하는 FIFO

교체하려고 하면 FIFO 순으로 쭉 봄

HW: 페이지가 액세스되면 레퍼런스 비트를 1로 세팅

OS:

- 레퍼런스 비트가 1: 0으로 만들고 한 번 봐줌

- 레퍼런스 비트가 0: 스왑 아웃

 

Advanced version

- Periodic clearing

- 더티 비트까지 사용

---

Thrashing

시스템이 자기가 해야할 일을 하지 못하고 페이지 인, 페이지 아웃만 계속 하게 되는 경우

가용 물리 메모리가 충분하지 않아서 발생함

 

프로세스가 많을 수록 CPU 이용률이 높아지는데, 어느 순간 뚝 떨어지는 경우가 있음

주로 IO, 페이지 파울트가 계속 발생하기 때문

 

Working Set

WS(t): t 시점에서 델타 만큼의 이전 시간 구간에서 참조된 페이지들의 셋

 

워킹 셋의 응용

스레싱 감지 혹은 새 프로세스를 시작할 기회 찾기 가능

D는 현재 프로세스'들'이 요구하는 메모리 양 (프로세스들의 워킹 셋의 사이즈를 다 더한 것)

m은 실제 가용한 프레임 수

D > m

- 요구하는 양이 사용 가능한 양보다 크다 : 스레싱

-> 프로세스 중 하나를 서스펜드 (프로세스나 몇몇 페이지를 스왑 공간으로 내려야 함)

 

D < m

새 프로세스가 시작 가능

 

=> 멀티 프로그래밍을 할 수 있는 최대한 하면서 스레싱을 예방