[Operating System] Swapping : Mechanisms

Virtual Memory : Demand Paging

---

하드디스크의 일부를 마치 메인 메모리처럼 사용할 수 있도록 하는 기술이다. 이는 물리적 메모리(Physical Memory)의 한계를 극복하기 위한 기술이다. 이 기법은 하나의 프로그램을 실행할 때 프로그램 전체가 메모리로 올라와 실행되는 것이 아닌, 필요한 부분만을 불러와 실행하는 것을 기본으로 한다.

 

즉, 커널은 실제 메모리(RAM)에 올라와 있는 블록들 중에, 쓰이지 않는 것을 디스크에 저장한다. 이를 통해서 사용 가능한 메모리 영역을 늘린다. 만일 디스크에 저장되었던 메모리 블록이 다시 필요하게 되면 실제 메모리 안으로 올려지며 대신에 다른 블록이 메모리로 내려간다. 이런 과정이 일어나고 있다는 것은 사용자가 알 수 없고, 그저 많은 양의 메모리가 있는 것처럼 보일 뿐이어서 점유하고 있는 메모리가 디스크에 있는 실제 메모리에 있는 지는 신경쓰지 않아도 된다.

 

다만, 디스크를 읽고 쓰는 시간은 메모리를 읽고 쓰는 시간보다 훨씬 느리기 때문에 프로그램의 실행은 그만큼 느려지게 된다. 이렇게 가상메모리로 쓰이는 하드디스크 영역을 스왑 영역(Swap Space)이라고 한다.

 

 

출처 : attiadmin.guyweb.co.kr/linux/swap.html

 

 

 

 

Swap Space

---

먼저, 페이지를 이동할 수 있도록 디스크의 공간을 확보해야 한다. 운영체제에서는 이를 위해 스왑 공간(Swap Space)를 참조하는데, 이는 메모리에서 페이지를 스왑 공간(디스크)으로 옮기고 스왑 공간으로부터 페이지를 메모리로 옮기기 위해서다. 따라서, 운영체제가 스왑 공간에서 페이지 크기의 단위로 읽고 쓴다고 가정했을 때, 운영체제는 지정된 페이지의 디스크 주소를 기억해야 한다.

 

스왑 공간의 크기는 궁극적으로 특정 시간에 시스템에서 사용할 수 있는 최대 메모리 페이지의 수를 결정하기 때문에 중요하다.

 

 

 

 

The Present Bit

---

이처럼 디스크에 공간을 확보했으니, 디스크와 페이지를 스왑(swap)하는 것을 지원하기 위해 시스템위에 기계(machinery)를 추가해야 한다.

 

Without Swap Space

먼저, 하드웨어 기반으로 관리되는 TLB가 있다고 가정했을 때, 메모리를 참조할 때 어떠한 일이 벌어지는지 떠올려보자. 실행 중인 프로세스는 가상 메모리 참조(Virtual Memory References)를 생성하며, 하드웨어는 원하는 데이터를 메모리에서 가져오기 전에 해당 참조를 물리적 주소로 변환한다.

 

하드웨어는 먼저 가상 주소에서 VPN을 추출하고 TLB에서 일치(TLB Hit)를 확인하고, 적중 시 해당하는 물리적 주소를 가져와 메모리로부터 데이터를 가져온다. 이 경우에는 추가적인 메모리 액세스가 필요하지 않으므로 속도가 빠르며 일반적인 경우다.

 

TLB에서 메모리를 찾을 수 없을 때 (TLB Miss), 하드웨어는 메모리에 있는 페이지 테이블로부터 VPN을 인덱스로 사용하여 해당 페이지에 대한 페이지 테이블 항목(PTE)을 조회한다. 페이지가 유효하고 물리적 메모리에 있는 경우 하드웨어는 PTE에서 PFN(Page Frame Number)을 추출하여 TLB에 설치한 후 해당 명령을 다시 시도한다. 이번에는 TLB Hit가 발생한다.

 

 

With Swap Space

만약 페이지(pages)가 disk와 스왑(swap) 되기를 원한다면, 즉 가상 메모리를 사용한다면 더 많은 기계를 추가해야 한다. 특히, 하드웨어 및 운영체제가 PTE를 확인할 때 페이지가 물리적 메모리에 존재하지 않는다는 것을 발견할 수 있다. 이처럼 하드웨어 및 운영체제가 페이지의 물리적 메모리 상의 존재 여부를 판단하기 위해 사용하는 새로운 정보는 각각의 PTE 항목에 존재하는 present bit이다.

 

Present bit이 1이라면, 페이지가 물리적 메모리에 존재한다는 것을 의미하고, 위와 같이 진행하면 된다.

Present bit이 0이라면, 페이지는 메모리가 아닌 디스크에 존재한다는 것을 의미한다. 물리적 메모리(physical memory)에 존재하지 않는 페이지에 접근하는 상황을 page fault라고 한다. 

 

페이지 폴트가 발생하면 OS가 호출되어 페이지 폴트를 처리한다. Page fault Handler가 실행되고 페이지 폴트를 해결한다.

 

 

 

The Page Fault

---

페이지가 메모리에 존재하지 않고 디스크로 스왑되어 있을 경우 운영체제는 page fault를 해결하기 위해 해당 페이지를 메모리로 스왑해야 한다. 그렇다면, 운영체제는 어떻게 해당 페이지의 위치를 디스크로부터 찾을까? 보통, 이러한 정보는 페이지 테이블에 저장되어 있다. 따라서, 운영체제는 PTE의 일부 비트에 해당하는 데이터를 해당 페이지 disk address의 PFN처럼 사용한다. 운영체제는 페이지에 대한 page fault를 수신하면 PTE를 조회하여 disk address를 찾고 디스크에 해당 페이지를 메모리에 불러오도록 요청을 전송한다.

 

Disk I/O(디스크 입출력)가 완료되면, 운영체제는 페이지 테이블을 업데이트하여 해당 페이지의 present bit을 1로 변경하고 PTE의 PFN에 새롭게 가져온 페이지의 in-memoroy location을 기록한다. 그리고 해당 명령을 재시도한다.

 

이번 재시도에서는 TLB miss가 발생할 수 있다. 발생 시 위의 변환된 정보로 TLB를 업데이트하고, 서비스할 것이다. 이와 같은 단계를 피하기 위해서 page fault를 해결할 때 TLB를 업데이트할 수도 있다.

 

최종적으로, 변환 정보를 TLB에서 찾아 변환된 물리적 주소(physical address)에 존재하는 원하는 데이터 또는 명령을 메모리로부터 가져온다(fetch). 

 

I/O가 발생한 동안에 해당 프로세스는 block상태가 된다. 따라서 운영체제는 page fault를 처리하는 동안에 다른 ready상태의 프로세스를 실행할 수 있다. I/O는 고비용 작업이기 때문에 다른 프로세스와 실행을 overlap(겹침)하는 것은 멀티프로그래밍 시스템이 하드웨어를 가장 효과적으로 사용할 수 있는 방법 중 하나이다.

 

 

 

What if Memory is Full?

---

위에서 설명한 절차는 페이지를 Swap Space(스왑 공간)으로부터 메모리로 가져오기에 충분한 사용 가능 메모리 용량이 확보되었다는 것을 가정한다. 물론 그렇지 않은 경우도 있다. 메모리가 꽉 찬(full) 상태 또는 거의 꽉 찬 상태일 때이다. 이 때, 운영체제는 가져오려는 새 페이지의 공간을 확보하기 위해 하나 이상의 페이지를 내보낼 수 있다. 내보내거나 교체할 페이지를 선정하는 절차를 Page-Replacement Policy라고 한다.

 

메모리에 존재하는 페이지를 잘못 내보낼 경우 프로그램 성능에 있어 엄청난 비용이 발생하기 때문에 좋은 페이지 교체 정책을 만드는 것이 중요하다. 잘못된 결정을 내린다면 프로그램이 메모리 기반 실행 속도가 아닌 디스크 기반 실행 속도로 실행하게 되며 이는 프로그램이 10,000배 또는 100,000배 느려질 수 있다는 것을 의미한다.

 

 

 

 

 

Page Fault Control Flow

---

지금까지 배운 지식들을 총집합하여 메모리 액세스의 전체 제어 흐름(comple control flow of memory access)을 스케치할 수 있다. 누군가가 메모리에서 어떠한 데이터를 가져오고자 할 때 무슨 일이 발생하는가?라는 질문을 한다면 발생할 수 있는 모든 다른 가능성들에 대해서 숙지하고 있어야 한다.

 

출처 : https://pages.cs.wisc.edu/~remzi/OSTEP/

 

위 Hardware Control Flow Algorithm을 통해서 알아둬야 할 대표적인 세 가지 사례가 있다.

 

첫 번째는, 페이지가 존재하고 유효한 경우다(valid and present, 18-21). 이 경우 TLB Miss Handler는 PTE로부터 PFN을 획득하여 명령을 다시 시도하면 TLB hit가 발생하고 여러번 계속할 수 있다.

 

두 번째는,  Page fault handler를 실행해야 하는 경우다(Valid but not present, 22-23). 페이지가 프로세스가 접근할 수 있는 유효한 상태이지만 물리적 메모리에 존재하지 않는 상황이다. Page fault handling(스왑공간에서 페이지 읽도록 I/O요청 및 페이지 테이블 업데이트) -> 재시도(TLB Miss) -> 재시도(TLB Hit) 순서다.

 

세 번째는 프로그램의 버그로 인해 유효하지 않은 페이지에 접근한 경우다(not valid, 22-23). 이 경우 PTE의 나머지 비트들은 관여하지 않고, 하드웨어가 invalid access를 trap하고 운영체제는 trap handler를 실행하여 해당 프로세스가 종료될 수 있다.

 

 

 

 

 

When Replacements Really Occur

---

지금까지 설명한 대체 방법은 운영체제가 메모리가 완전히 가득 찰 때까지 기다렸다가 다른 페이지를 위한 공간을 확보하기 위해 페이지를 교체하는 것으로 가정했다. 이는 다소 비현실적이며, 이보다는 운영체제가 메모리의 일정 작은 부분을 능동적으로 사용가능한 상태로 유지하는 것이 여러 측면에서 유리하다.

 

메모리의 일부 작은 공간을 확보(free)하기 위해서 대부분의 운영체제는 일종의 high watermark(HW)와 low watermark(LW)를 가지고 있다. 사용가능한 페이지 수가 LW보다 적어질 때 메모리 확보를 담당하는 백그라운드 스레드가 실행된다. 해당 스레드는 사용가능한 페이지 수가 HW에 다다를 때 까지 페이지를 제거한다. Swap daemon 또는 page daemon1이라고 불리는 해당 스레드는 운영체제가 프로세스를 실행하는동안 사용할 여유 메모리를 확보한 후 sleep상태가 된다.

 

여러 교체 작업을 한번에 수행하여 성능 최적화를 할 수 있다. 예를 들어, 많은 시스템은 여러 페이지를 클러스터링하거나 그룹화하여 한 번에 스왑 파티션에 기록하므로 디스크의 효율성이 향상된다. 이러한 클러스터링은 disk의 검색 및 회전 오버헤드를 줄여 성능을 현저하게 향상시킨다.

 

백그라운드 페이징 스레드를 이용하면 직접 교체를 수행하는 대신 사용 가능한 여유 페이지 공간이 있는지 확인할 수 있다. 여유 페이지 공간이 존재하지 않을 경우 백그라운드 페이징 스레드에 페이지가 필요함을 알린다. 사용 가능한 페이지가 존재하게 되면 백그라운드 페이징 스레드는 원래 스레드를 깨워 원하는 페이지로 이동할 수 있다.

 

해야할 일이 있을 때, 작업의 그룹화를 허용하고 효율성을 높이기 위해서 백그라운드에서 수행하는 것이 종종 좋다. 운영체제는 때때로 백그라운드에서 일을 수행한다. 예를 들어, 실제로 디스크에 데이터를 쓸 때(write), 많은 시스템 버퍼 파일이 메모리에 쓰인다(write). 이렇게 하면 디스크에 한 번에 많은 쓰기(write)를 수행할 수 있어 디스크 효율 향상, 쓰기 지연 시간 단축(improved latency of writes)이 가능하다. 또한 백그라운드 작업은 시스템이 idle 상태일 때도 수행될 수 있어 하드웨어를 더 효과적으로 사용할 수 있다.

 

 

 

---

 

 

출처 : pages.cs.wisc.edu/~remzi/OSTEP/ 

Operating Systems: Three Easy Pieces