[운영체제 6] 스와핑(Swapping)과 페이징(Paging)
스와핑(Swapping)
메모리는 분명 규모적 한계가 존재한다. 따라서 현재 실행하지 않거나 오랫동안 사용되지 않은 프로세스를 쫓아낼 필요가 있다.
해당 프로세스들을 보조기억장치의 일부 영역(=스왑 영역)으로 쫓아내고, 그 공간에 다른 프로세스를 적재하는 과정을 스와핑(swapping)이라고 한다.
이때 프로세스들을 쫒아 내는 것을 스왑 아웃(swap-out), 쫒아보내진 공간을 스왑 영역(swap space), 그 자리에 다른 프로세스를 들여오는 과정을 스왑 인(swap-in)이라 한다. 스왑 공간의 크기와 관련해서는 유닉스 등의 free, top 명령어를 통해 확인할 수 있다.
외부 단편화와 배치 전략
최초로 메모리를 할당할 생각을 했을 때는 아마도 연속적인 할당을 떠올렸을 것이다. 그게 보기도 편하고 코딩하기도 편하니까.(이후의 내용은 일단 ‘연속 메모리 할당’을 가정으로 한다.)
그런데 이후 프로세스들을 스와핑하는 과정에서 문제가 발생한다.
다음과 같이 메모리 A~C에 각각 프로세스가 할당되어있다가 B의 프로세스가 스왑 아웃되었다고 생각해보자.
만약 그 다음 프로세스가 블록 4개 이상을 필요로하는 대형 프로세스라면, 아무리 해당 프로세스가 실행되고 싶어도 남은 연속된 공간이 없어서 실행될 수가 없어진다.
스와핑이 점점 반복되면서 이러한 사용할 수 없는 공간들은 계속 발생하게 되는데, 결국 남는 공간의 합은 프로세스보다 큼에도, 연속된 충분한 공간이 없어 프로세스가 실행되지 못하는 상황이 연출된다. 이를 외부 단편화(external fragmentation)라 한다. (물론 이 문제는 뒤에 나오는 가상 메모리로 말끔히 해소된다!)
이를 해결하기 위해 최대한 스왑 아웃된 빈공간에 이후의 프로세스들을 적소에 배치하기 위한 전략들이 등장했는데 이를 배치 전략(placement strategy)이라고 한다.
최초 적합(First Fit)
가장 기초적인 배치 전략으로 최초 적합(first fit)이 있다.
말 그대로 스왑 인하려는 프로세스가 들어갈 수 있는 최초의 공간을 발견하는 즉시 메모리를 할당하는 방법이다. 검색이 최소화돼 속도가 빠르고 구현이 쉬운 장점이 있다.
위의 상황에선 크기가 20짜리인 P1이 크기가 100인 Block1에 들어가고, (하나의 프로세스가 들어간 블록엔 다른 프로세스는 스왑 인이 불가하다고 하면) P2는 Block 2, 3에는 못들어가고 4에, P3는 아무 블록에도 할당이 되지 못한다.
교재에서는 이와 다르게 하나의 블록에 여러 프로세스가 들어갈 수 있다고 가정해놓고 있는데, 이 역시 최초 적합의 일종으로 볼 수 있다. 이와 관련한 두 코드의 구현 차이는 여기에서 확인
최적 적합(Best Fit)
다음으로 최적 적합(best fit)이다.
낭비되는 공간이 가장 적도록 할당하는 방식으로, 위의 그림에선 40짜리 프로세스가 50짜리 Block2에 들어간다.
단편화(fragmentation)가 최소화된다는 장점이 있지만, 최적의 장소를 찾는 데에 시간이 소요된다.
최악 적합(Worst Fit)
신기하게도 최악 적합(worst fit)도 존재한다.
최악 적합은 반대로 단편화를 최대로 하는 장소에 들어가는데, 이는 하나의 블록에 여러 프로세스가 들어갈 수 있다는 상황을 전제로 하는 방법이다.
큰 상자에 여러 물건을 한꺼번에 넣는 것이 좋듯이, 최대한 빈 공간에 많은 프로세스를 욱여넣음으로써 궁극적으로 단편화를 최소화하게 되는 것이다.
다음 적합(Next Fit)
다음 적합(next fit)은 최초 적합의 변형 버전이다. 차이점은 매번 첫번째 블록부터 탐색하는 최초 적합과 달리, 바로 직전에 할당된 블록부터 순차적으로 최초 적합을 시행해나간다는 것이다.
다음과 같이 16M 짜리 메모리는 앞선 위의 블록들에도 들어갈 수 있지만, 가장 최근에 삽입된 위치로부터 탐색하기에 상대적으로 뒷 블록에 할당된 것을 볼 수 있다.
이 다음 적합은 점점 뒤로 가면서 공간을 찾기에 최초/최적 적합에 비해 빠르기도, 사용하지 않던 뒷공간을 잘 사용하게 되기도 한다는 장점이 있다.
압축(Compaction)
이건 또다른 외부 단편화의 해결책인데, 기존의 프로세스들을 한데 모아 빈 공간들도 하나로 모으는 방식이다. 물론 적당한 재비치를 통해 잉여 공간을 남길 수도 있겠지만, 압축 과정에서 시스템은 하던 일을 중지해야 하고, 오버헤드가 크게 발생해 바람직한 해결책은 아니다. 그렇다면 더 나은 전략이 있을까?
가상 메모리와 페이징(Virtual Memory & Paging)
이번 운영체제 파트에서 정말 중요한 개념 중 하나가 드디어 등장했다. 페이징(paging)이다.
이제부터는 앞서 가정한 연속 메모리가 아닌, 일부만을 메모리에 적재함으로도 프로세스를 실행할 수 있는 ‘가상 메모리(virtual memory)’를 대상으로 진행한다.
이 가상 메모리 관리 방식으로는 세그멘테이션(segmentation)이라는 것도 있지만, 일단은 책에서 다루고 있는 페이징에 대해 살펴보자.
페이징의 가상 메모리는 두 가지 조건을 전제로 한다. 첫째, 모든 공간들과 프로세스들을 일정한 단위의 크기로 자를 수 있을 것. 둘째, 프로세스 조각들을 불연속적으로 적재할 수 있을 것.
다음과 같이 각 프로세스 A1~A4의 물리 주소 공간을 1KB 크기의 프레임(frame)으로 자르고, 각 프로세스의 논리 주소 공간을 같은 크기의 페이지(page)(플래시 메모리에서의, 셀들이 모인 페이지와 같은 철자이지만 다른 뜻임에 유의)로 나눈 뒤, 각 페이지를 프레임에 할당하는 기법이 페이징이다.
페이징은 프로세스 조각(즉, 페이지)을 불연속적으로 적재할 수 있기에, 마찬가지로 페이지 단위로 스와핑이 가능하다. 이 페이지들을 스왑 아웃/스왑 인하는 것을 각각 페이지 아웃(page out)/페이지 인(page in)이라고 부른다.
페이징의 장점은, 당장 실행에 필요하지 않은 페이지들을 보조기억장치에 그대로 둠으로써 메모리보다 더 큰 크기의 프로세스도 실행이 가능하다는 것이다.
다만 페이지의 크기(프레임의 크기와 동일하다)를 너무 크게 잡으면 프로세스가 할당되면서 일부 남는 공간이 발생하게 되는데, 이를 내부 단편화(internal fragmentation)라 부른다. 그렇다고 페이지의 크기를 줄이면 후술할 페이지 테이블이 커져서 또 다른 공간(PCB)을 낭비하게 되므로 적절한 크기 설정이 중요하다.
페이지 테이블(Page Table)
물리 주소가 불연속적이더라도 논리 주소는 연속적으로 배치되어야 프로세스의 실행이 쉬워진다. 이를 기록하기 위한 표가 페이지 테이블(page table)이다. 컴퓨터구조 파트에서 다룬 MMU와 기능적으로 유사하다.
각 프로세스 별로 페이지 테이블이 존재하며, 이 테이블들은 메모리 커널 영역의 PCB(프로세스 제어 블록)에 저장된다. 또한 페이지 테이블 베이스 레지스터(PTBR; Page Table Base Register)가 각 프로세스의 ‘페이지 테이블이 저장된 주소’를 가리킨다. 페이지의 주소가 아님에 유의하자.
문제는 각 페이지 테이블이 메모리에 저장되기에, 페이징을 위해 페이지 테이블에 한 번, 실제 프레임에 한 번, 총 두 번을 메모리에 접근해야한다는 것이다.
우리는 이와 같은 상황을 전에 한 번 보았다. RAM까지 다시 가기도 뭐한데, 참조는 해야할 상황. 무엇으로 해결했더라? 캐시다.
이 페이지 테이블 전용 캐시 메모리를 MMU 안에 두게 했으니 그것이 TLB(변환 색인 버퍼: Translation Lookaside Buffer)다. 캐시와 마찬가지로 히트와 미스도 있다.
이 TLB 안에는 각 페이지 테이블에 대한 정보(페이지 번호 및 변위)가 저장되며, 이 각각의 행들을 페이지 테이블 엔트리(PTE; Page Table Entry)라 부른다. 이 PTE들이 TLB 안에 저장된다.
위의 이미지를 정확히 이해하려면 너무 알아야 하는 것이 많다. 너무 깊게 들어가진 말자.
PTE를 구성하는 비트 중 하나인 유효 비트(valid bit)는 해당 페이지에 접근 가능한지, 즉 페이지 인 되어 있는지를 알려준다. 만약 페이지 아웃된 상태여서 유효 비트가 0인 메모리를 접근하려고 한다면, 페이지 폴트(page fault)라는 예외가 발생한다. 폴트이므로 예외를 처리하고 나면 다시 해당 페이지를 다시 읽는 것부터 시작한다.
다음으로 보호 비트(protection bit)는 rwx(읽기, 쓰기, 실행) 가능 여부를 나타내느 것으로 3비트로 나타낸다.
참조 비트(reference bit)는 해당 페이지에 접근한 적이 있는지의 여부를, 수정 비트(modified bit; dirty bit)는 해당 페이지에 추가 데이터가 작성된 것이 있는지 여부를 알려준다.
마지막 수정 비트는 해당 페이지가 메모리에서 페이지 아웃될 때 보조기억장치에 추가적인 작성 작업을 해야하는 지를 나타내는 지표로써, 후술할 페이지 교체 알고리즘에서 또 한 번 언급하겠다.
페이징의 이점
쓰기 시 복사(CoW; Copy on Write)
페이징은 이전에 한 프로세스의 스레드끼리는 PCB를 공유한다고 했듯이, 부모-자식간 프로세스끼리는 프레임(물리 주소 공간)을 공유한다. 다만 이중 한 프로세스에 수정이 발생한다면, 해당 페이지의 복사본에 수정 사항을 기입하고, 프레임 번호를 바꿈으로써 공간을 절약한다.
계층적 페이징(Hierarchical Paging)
페이지 테이블은 비교적 크기가 작지만, 프로세스가 커짐에 따라 테이블의 크기도 커지기에 테이블을 두 단계 이상으로 접어버리는 기술이 등장했다.
이를 다단계 페이지 테이블(multilevel page table) 기법이라고 부르는데, 예를 들어 two-level의 경우 바깥(outer) 페이지 번호와 안쪽 페이지 번호 및 변위를 적시함으로써, 페이지를 두 번 찾아 들어가 정보를 읽어오는 식으로 저장 공간을 절약할 수 있다.
페이지 교체 알고리즘(Page Replacement Algorithm)
앞서 최초 적합 등을 말하며 placement strategy에 대해 말했다면, 이번엔 replacement algorithm이다.
아무리 가상 메모리이고, 큰 프로세스도 실행할 수 있다고 해도 메모리는 메모리이다. 크기가 한정되어있다. 필요한 메모리만을 페이지 인하는 기법을 ‘요구 페이징(demand paging)’이라고 하는데, 앞서 말한 유효 비트가 0일 때 폴트를 발생시킨 후 페이지 인을 시도한다. 그런데 누굴 빼버릴 것인가? 누굴 페이지 아웃시키는 게 가장 현명할까?
이를 알기 위해선 페이지 참조열(page reference string)이라는 개념을 알아야하는데, 쉽게 말해 연속된 페이지를 생략한 수열이다. ‘2 2 2 3 5 5 5 3 7’이면 페이지 참조열은 ‘2 3 5 3 7’인 식
FIFO 페이지 교체 알고리즘
선입선출로 교체하는 가장 쉬운 방법이 있다. “오래 머물렀으면 나가라” 알고리즘
가장 쉽지만, 그만큼 페이지 폴트가 자주 발생한다.
2차 기회 페이지 교체 알고리즘
FIFO는 너무 매정하다. 이 알고리즘은 해당 페이지가 참조된 적이 있다면(참조 비트가 1이라면) 참조 비트를 0으로 바꾸고, 현재 시간을 적재 시간으로 설정한다.
이게 뭔 말이냐? CPU가 한 번 이상 더 접근한 적이 있는 페이지는 앞으로도 쓰일 가능성이 높으니 기회를 한 번 더 주겠다는 뜻이다.
0이 2번째로 접근될 때 frame2에 저장되어있는 참조 비트는 1로 바뀐다. 즉 0은 두 번 이상 참조가 된 것이다. 이후 3이 접근될 때 FIFO로는 ‘0 2 1’ 순이므로 0이 페이지 아웃되어야 하겠지만, 참조된 적이 있기에 참조 비트를 0으로 바꾸는 대신 페이지 인 된 시간순을 ‘0 2 1’에서 ‘2 1 0’으로 바꾸게 된다. 그렇게 되면 2가 가장 오래 머무른 셈이 되니 2가 엉겁결에 페이지 아웃되어버리는 것.
최적 페이지 교체 알고리즘
이건 좀 예측의 싸움이다. 가장 페이지 폴트가 적게 일어날 경우를 예측해서 알고리즘을 짜는 것인데 현실적으로 쉽지는 않을 것이다. 따라서 이 알고리즘은 현실에서 사용되기보다는, 다른 교체 알고리즘을 평가하기 위한 수단으로써 사용된다.
LRU 페이지 교체 알고리즘
앞선 최적 교체가 가장 오랫동안 사용되지 ‘않을’ 페이지를 빼는 거라면, LRU(Least Recently Used)는 가장 오랫동안 사용되지 ‘않은’ 페이지를 빼는 것이다.
페이지 2와 1이 히트를 했기에 페이지 5가 들어올 때 가장 늦게 들어온 3이 페이지 아웃된다. 확실히 페이지 폴트(회색 miss)가 주는 것이 보이는가?
스래싱(Thrashing)
페이지 교체를 적절히 하는 것도 좋지만, 페이지 교체 횟수가 잦아질 경우 그만큼 시행 시간이 오래 걸려 CPU의 효율이 떨어지게 된다. 이렇듯 프로세스의 실행 시간보다 페이징 시간이 더 커서 성능이 저해되는 상황을 스래싱(thrashing)이라고 한다.
스래싱을 줄이기 위해서는 각 프로세스별로 필요한 최소한의 프레임 수가 보장되어야 한다. 그런데 프레임도 역시 ‘자원’의 일종인데 수량이 넉넉할까? 아니다. 그렇다면 어떻게 이 프레임을 할당해야할까?
가장 편하게 모든 프로세스에 똑같이 프레임을 주는 균등 할당(equal allocation)이 있다. 또 프로세스의 크기 별로 할당해주는 비례 할당(proportional allocation)이 있다. 이 둘은 단순히 크기만을 보고 할당하므로 정적 할당 방식이라고 부르는데 둘 다 완벽히 할당을 시켜주진 못한다.
따라서 이와 반대로 프로세스의 실행을 직접 보고 할당하는 동적 할당 방식이 있는데,
일정 시간동안 참조한 페이지의 개수를 보고 할당하는 작업 집합 모델(working set model)과
페이지 폴트율 그래프 사이에서 상한선과 하한선을 그어 절충하는 페이지 폴트 빈도(PFF; Page-Fault Frequency) 방식이 있다.
출처: [혼자 공부하는 컴퓨터구조+운영체제 Chapter 14]