[운영체제] 스와핑 (swapping)

스와핑

메모리를 모두 사용했을 때 새로운 프로세스를 실행할 수 있을까? 스와핑을 이용하면 실행할 수 있다. 스와핑은 메모리에 있는 데이터를 디스크에 있는 데이터와 바꾸는 작업이다.

스왑 스페이스 : 하드디스크를 이용하는 것 얘기
초반에 피지컬 메모리만 있을 때 문제점 : 메모리 크기가 충분하지 않으면 모든 프로그램을 적재할 수 없다.

아이디어

페이징 시스템을 사용하고 있을 때 사용하지 않는 프레임이 있다면 그 부분을 디스크에 저장하고 디스크에 있는 페이지를 메모리로 올린다.

프로세스가 메모리 접근 -> (if 메모리에 없다) 스와핑이 일어난다. -> 디스크에서 가져온다. -> 메모리에 다시 엑세스

운영체제에서 어떤 페이지를 가져오라는 명령을 줄 수 있어야 한다. 스와핑은 cpu가 자동으로 할 순 없고 운체가 구현해줘야하는 부분이다.

메모리 덤프를 떠서 haddisk 에 file 로 저장한다.
swap out : 메모리에서 디스크로 내보내는 것
swap in : 디스크에서 메모리로 올리는 것

프로세스는 어떤 기준으로 쫓아낼까? 모든 프로세스가 실행중이면 불가능한가? 그건 아니다. 현대 운영체제들은 대부분 페이징과 스와핑 기능을 제공한다.

리눅스 : 디스크를 파티션으로 나눈다. 한 파티션을 스와핑 파티션으로 이용
윈도우 : 파티션 따로 안 나눈다. 지정할 수도 있지만 기본적으로 C에 저장 윈도우 7에서는 숨김파일로 볼 수 있었지만, 윈도우 10의 경우 숨김파일 보기로도 안 보인다.

스와핑 구현
1. 자료구조가 필요하다. 어떤 페이지 나갔는지, 들어왔는지, 페이지에 대한 메타 데이터, 페이지가 나간 시간 등을 저장한다.
2. 운영체제가 페이지 폴트 핸들러를 구현할 수 있어야 한다.

PTE
p(present) : 피지컬 메모리에 이 페이지가 있느냐? 0 이면 페이지가 없다는 뜻. 페이지 폴트 발생.
invalid 같은 경우 segmentation fault 발생
swap out 돼 있는 페이지 접근 : 
1. swap in
2. PTE update
3. TLB 에 PTE 넣고 CPU 가 다시 instruction 수행

segmentation fault : valid == false
page fault : PTE.Present == False
운영체제는 page fault handling 을 수행하고 다른 코드들은 cpu가 한다.

evict

언제 쫓아낼 것인가?

1. on-demand approach
메모리가 가득한 상태에서 바꾸면 계속해서 page fault 가 발생할 것이기 때문에 느리다. 디스크는 메모리보다 100배이상 느리다.
2. proactive approach
8~90%가 차면 스와핑을 시작한다. (high watermark)
high watermark 넘어가면 백그라운드 프로세스로 스와핑을 동작시킨다.
high watermark 보다 적게 사용하도록 유지한다.

어떤 페이지를 쫓아낼 것인가?

page-replacement policy

내가 앞으로 어떤 순서로 엑세스할 지 미리 알고 있다고 가정하면 가장 나중에 접근할 페이지를 쫓아낸다. 이 방법은 수학적으로 최적의 방법이지만 구현이 불가능하다. 하지만 이 방법과 비교하여 성능을 측정할 수 있다.

TLB와 같이 생각할 것
FIFO, Random 방법도 있지만 보통 LRU 방법을 사용한다.
LRU : Least Recently used (가장 최근에 사용되지 않은 것 : localiry 이용)
TLB 는 하드웨어적으로 구현되어 있지만, 페이지 폴트 핸들러는 운영체제에서 구현해야 한다.
LRU 방법을 사용하면 최악의 경우에도 optimal보다 두 배를 넘지 않는다. 어떤 것으로 구현할 지는 workload 에 따라 다르다.

LRU 는 어떻게 구현할까? 접근한 시간과 순서를 저장하는 것은 너무 복잡하다. 정렬하는 것은 성능상 안 좋다. 따라서 LRU 를 직접 구현하는 것은 오버헤드가 크다. 따라서 LRU approximation 을 한다.

x86 의 PTE
a : 페이지를 최근에 read를 했는가?
d(dirty) : 페이지에 최근에 write를 했는가?
mmu가 페이지가 접근될 때마다 pte에 이 비트들을 세팅하고, 운영체제는 이 비트들을 clear 할 수 있다. 이 비트들을 이용하여 LRU approximation 을 할 수 있다.

Approximating LRU
운영체제가 일정한 시간마다 a, d 비트를 체크한다. 일정 시간 안에는 이 페이지에 접근했다는 것을 알 수 있다. a == 0 인 페이지들을 쫓아낸다.

the clock algorithm
운영체제가 PTE 를 순차적으로 한 바퀴 돌면서 0으로 만든다. 다시 돌아왔을 때 0이면 쫓아내고 1이면 쫓아내지 않는다.
주기를 잘 조절하여 적절한 시간을 찾는다. 조금 더 발전된 알고리즘으로 two handed clock 이 있다. 시계축이 두 개이고 지우는 축과 쫓아내는 축으로 구성, 두 개의 시간을 다르게 설정한다.

dirty bit 를 고려하는 것의 성능적인 이점
dirty bit == 1이라면 메모리에 있는 페이지가 디스크에 있는 페이지와 다르다. 이 경우 쫓아낼 때 디스크에 써야한다. 만약 read 만 했다면 메모리에서 삭제하기만 하면 된다. 더티비트가 세팅되어 있다면 세팅되지 않은 페이지를 쫓아내야 한다. -> 디스크에 이미 적재한 페이지를 메모리로 불러온 뒤 다시 메모리에 적재하는 경우를 말하는 듯하다. read 만 했을 경우엔 디스크에 다시 적재할 필요가 없다는 뜻이다.