8장, 가상메모리
프로그램이 CPU에서 실행되려면, 실행에 필요한 부분이 메모리에 올라와 있어야 한다. 이때 운영체제는 어떤 프로그램에 얼마만큼의 메모리 공간을 할당할지를 결정해야 한다. 프로세스의 빠른 수행을 위해 프로세스마다 최소한으로 확보해야 하는 메모리의 크기가 존재하기 때문에, 균등하게 할당하기보다는 특정 프로그램에 집중적으로 할당하는 방식을 사용한다.
프로그램이 실행되기 위해서 프로세스의 주소 공간 전체가 메모리에 올라와야 하는 것은 아니다. 당장 수행해야 할 부분만 메모리에 올려놓고, 나머지는 디스크의 스왑(swap) 영역에 두었다가 필요할 때 가져와 사용할 수 있다. 이를 통해 프로그램은 물리적 메모리 크기를 고려하지 않아도 된다. 프로세스는 자신만이 메모리를 사용한다고 가정하고 0번지부터 시작하는 자기 자신만의 메모리 주소 공간을 사용하는데, 이를 가상메모리라고 부른다.
가상메모리 기법
가상메모리 기법에는 요구 페이징 방식(demand paging)과 요구 세그먼테이션 방식(demand segmentation)이 있다. 대부분 요구 페이징 방식을 사용하며 페이지드 세그먼테이션 기법을 사용하는 경우 요구 세그먼테이션방식을 사용하기도 한다.
요구 페이징 방식(demand paging)
프로그램 실행 시 당장 사용될 페이지만을 메모리에 올리는 방식
요청이 들어온 다음에야 해당 페이지를 메모리에 적재한다
메모리 사용량 감소, 입출력 오버헤드 감소, 응답 시간 단축, 더 많은 프로세스 수용 가능
메모리 용량 제약에서 벗어남
유효-무효 비트(valid-invalid bit) - 모든 페이지에 대해 존재
※ 페이지 부재(page fault) : 참조하려는 페이지가 메모리에 올라와 있지 않아 유효-무효 비트가 무효로 세팅된 경우
페이지 부재 발생 시 처리 과정
페이지 부재가 발생 -> MMU가 페이지 부재 트랩(page fault trap) 발생시킴 -> CPU 커널 모드로 전환 -> 운영체제의 페이지 부재 처리 루틴(page fault handler) 호출
페이지 부재 처리 루틴
요구 페이징의 성능을 측정할 때에는 페이지 부재의 발생 빈도가 가장 중요하다. 페이지 부재가 일어나면, 막대한 오버헤드가 발생하기 때문이다. 요구 페이징의 성능은 요청한 페이지를 참조하는 데 걸리는 유효 접근시간으로 측정한다.
유효 접근시간(effective access time)
페이지 교체(Page Replacement) ? 페이지 부재 발생 시, 빈 프레임이 없을 때 메모리에 올라와 있는 페이지 중 하나를 스왑 아웃하여 빈 공간을 확보하는 것
페이지 교체 알고리즘(replacement algorithm)
페이지 교체 시, 어떤 프레임에 있는 페이지를 스왑 아웃할지 결정하는 알고리즘. 페이지 부재율의 최소화가 목적
- 최적 페이지 교체 - 빌레디의 최적 알고리즘(Belady's optimal algorithm), MIN, OPT
가장 먼 미래에 참조될 페이지를 스왑 아웃한다.
미래에 어떤 페이지가 어떤 순서로 참조될지 알고 있어야 하므로 온라인에서는 사용할 수 없다. 오프라인 알고리즘.
가장 적은 페이지 부재율 보장
성능의 상한선 - 선입선출 알고리즘(First In First Out : FIFO)
가장 먼저 올라온 페이지를 우선적으로 스왑 아웃한다.
비효율적
FIFO의 이상현상 - 선입선출 알고리즘에서 메모리를 증가시켰음에도 페이지 부재가 오히려 증가하는 상황 - LRU 알고리즘(Least Recently Used)
가장 오래전에 참조가 이루어진 페이지를 스왑 아웃한다.
※ 시간 지역성(temporal locality) : 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질 - LFU 알고리즘(Least Frequently Used)
메모리 내 존재하는 페이지 중에서 과거에 참조 횟수(reference count)가 가장 적었던 페이지를 스왑 아웃한다.
동일한 참조 횟수를 가진 경우에는 상대적으로 더 오래전에 참조된 페이지를 스왑 아웃하도록 구현하는 것이 좋다.- Incache-LFU : 메모리에 올라온 후부터의 참조 횟수 카운트
- Perfect-LFU : 페이지의 과거 총 참조 횟수 카운트, 모든 기록을 보관하고 있어야 해서 오버헤드가 큼
- 클럭 알고리즘(clock alogrithm) ★
오랫동안 참조되지 않은 페이지 중 하나를 스왑 아웃한다. 페이지 프레임에 참조 비트를 두고, 시계방향으로 돌면서 참조 비트가 0인 페이지를 찾아 교체한다. 참조 비트는 처음 참조될 때 1로 세팅되고, 시곗바늘이 돌면서 1은 0으로 변경, 0인 경우는 페이지 교체를 수행한다.
가장 오래되었다는 것을 보장하지는 않기 때문에 LRU를 근사(approximation)시킨 알고리즘으로 NUR(Not Used Recently)또는 NRU(Not Recently Used) 알고리즘이라고도 불린다.
하드웨어적인 지원으로 동작하기 때문에 빠르고 효율적이다.
페이지 프레임의 할당
각 프로세스에 얼마만큼의 메모리 공간을 할당할지 결정하는 알고리즘
- 균등 할당(equal allocation) 방식
모든 프로세스에게 페이지 프레임을 균일하게 할당한다. - 비례할당(proportional allocation) 방식
프로세스의 크기에 비례해 페이지 프레임을 할당한다. - 우선순위 할당(priority allocation) 방식
당장 실행될 프로세스와 그렇지 않은 프로세스를 구분하여, 실행될 프로세스에 더 많은 페이지 프레임을 할당한다.
최소한으로 필요한 프레임의 개수가 다를 수 있기 때문에 종합적인 상황을 고려하여 프로세스에 할당되는 페이지 프레임의 수를 결정함으로써 최소한의 메모리 요구량을 충족시켜야 한다.
교체 방법은 교체 대상이 될 프레임의 범위에 따라 전역 교체와 지역 교체로 나뉜다.
- 전역 교체(global replacement)
모든 프레임이 교체 대상이 된다.
전체 메모리를 각 프로세스가 공유해서 사용한다.
할당되는 메모리의 양이 가변적
다른 프로세스의 프레임을 빼앗아 올 수 있어 할당량을 조절하는 또 다른 방법이 될 수 있다.
ex) 워킹 셋 알고리즘, PFF 알고리즘 - 지역 교체(local replacement)
현재 수행 중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정할 수 있다.
프로세스마다 페이지 프레임을 미리 할당하는 것을 전제로 함
ex) 프로세스별로 독자적으로 LRU, LFU 등의 알고리즘을 운영하는 것
스레싱?
집중적으로 참조되는 페이지들의 집합을 메모리에 한꺼번에 적재하지 못할 때, 페이지 부재율(page fault rate)이 크게 상승해 CPU 이용률(CPU utilization)이 급격히 떨어지는 현상
CPU 이용률이 낮으면, 준비 큐가 비는 경우가 발생한다는 의미이므로 운영체제는 MPD(Multi-Programming Degree, 다중 프로그래밍의 정도, 메모리에 동시에 올라가 있는 프로세스의 수)를 높인다. 그런데 MPD가 지나치게 높으면, 각 프로세스에게 할당되는 메모리의 양이 지나치게 감소하게 되고, 결국 페이지 부재가 빈번하게 발생하게 된다. => 스레싱
스레싱이 발생하지 않도록 하면서, CPU이용률을 최대한 높일 수 있도록 MPD를 조절해야 한다. 이를 위한 알고리즘으로, 워킹셋 알고리즘(working-set algorithm)과 페이지 부재 빈도 알고리즘(Page-Fault Frequency scheme : PFF 알고리즘)이 있다.
- 워킹셋 알고리즘
집중적으로 참조되는 페이지들의 집합(지역성 집합)이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘
워킹셋(working-set)? 한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합
시각 t1에 대한 워킹셋(t1)은 't1-윈도우 크기' 시간부터 't1'시간까지 참조된 서로 다른 페이지들의 집합이다.
윈도우 크기가 너무 작으면 지역성 집합을 모두 수용하지 못하고,
윈도우 크기가 너무 크면 MPD가 감소하여 CPU이용률이 낮아질 수 있다. - 페이지 부재 빈도 알고리즘
프로세스의 페이지 부재율을 주기적으로 조사하여 각 프로세스에 할당할 메모리 양을 동적으로 조절하는 알고리즘
페이지 부재율에 상한값(upper bound), 하한값(lower bound)을 두고 상한값을 넘을때엔 프레임을 추가 할당하고, 하한값 아래로 떨어질 땐 할당된 프레임의 수를 줄인다.
참고자료
반효경, 『운영체제와 정보기술의 원리』, 이화여자대학교출판문화원(2020), p215-p240
'IT Basic > Operating System' 카테고리의 다른 글
| [OS] OS 캐시와 분산 (0) | 2023.01.16 |
|---|---|
| [OS] 9장 디스크 관리 (0) | 2022.01.05 |
| 데드락(Deadlock, 교착상태)에 대해 (0) | 2021.12.30 |
| [OS] 7장 메모리 관리 (0) | 2021.12.28 |
| [OS] 6장 CPU 스케줄링 (0) | 2021.12.28 |
댓글