가상 메모리
논리 메모리와 실제 물리 메모리를 분리한 개념에서 논리 메모리 부분을 가상 메모리라고 한다.
가상 메모리의 탄생
오류 처리 코드는 실제로 거의 사용되지 않으며, 프로그램 전체의 코드가 한 번에 모두 메모리에 올라와 있을 필요가 없다. 또한, 프로그램 전체 코드를 메모리에 올리지 않고도 실행하는 것은 큰 이득으로 다가오기 때문에 가상 메모리가 탄생하게 되었다.
- 매핑: 가상 주소를 물리 주소로 변환하는 과정을 의미한다.
- 동적 주소 변환 방법(DAT): 인위적으로 연속적으로 변환되는게 큰 특징인 매핑 방법 중 한 가지.
- 가상 메모리 추가 기능으로 페이지 공유를 지원해 여러 프로세스가 메모리를 공유할 수 있다.
- 시스템 라이브러리 공유
- 프로세스 간 공유 메모리
- fork() 시 페이지 복사 대신 공유
수요(요구) 페이징
프로그램 실행 중 접근 시 페이지를 메모리에 올리는 기법이다.
- 보조기억장치 <-> 물리 메모리 사이의 페이지 이동을 반복한다.
- 프로그램 A의 일부 모듈 실행 시 다른 실행중인 프로그램의 모듈을 내린다.
- 실제 프로그램은 시간·공간 지역성을 띄어 수요 페이징 성능이 우수하다.
- 페이지 테이블 엔트리(로우)에 유효 여부 표시 비트를 두어 위치를 확인한다.
- 타당(1) 비트: 메인 메모리에 있는 페이지 중 하나
- 비타당(0) 비트: 디스크에 있는 페이지 중 하나
페이지 부재(Page fault)
메모리에 저장되지 않은 페이지에 접근하려고 할 때 하드웨어가 발생시키는 S/W 트랩
페이지 부재 처리 과정
- 프로세스 실행을 위해 가장 주소 1번 접근
- 비타당 유효 비트(0) 확인으로 트랩 발생
- OS가 제어권을 넘겨받아 메모리에서 빈 프레임 탐색 및 선택
- 이후 디스크에서 해당 페이지를 가져와 선택한 빈 프레임에 페이지 적재
- 페이지 테이블에 해당 페이지 엔트리 수정(비타당 유효 비트 -> 타당 유효 비트 변경) 및 재시작
여유 프레임 리스트(Free-Frame List)
페이지 부재가 발생하면 보조기억장치에서 원하는 페이지를 메인 메모리로 불러와야 하는데, 이를 효율적으로 처리하기 위해 빈 물리 프레임들의 풀(여유 프레임 리스트)를 사용한다.
복사 시 쓰기 방식(COW)
fork() 시스템 콜을 통해 자식 프로세스 생성 시 수요 페이징을 건너뛰고 복사 시 쓰기 방식으로 더 빠르게 생성할 수 있다.
- 같은 물리 페이지 공유시키고, 공유 페이지에 '복사 시 쓰기'를 마킹한다.
- 부모 또는 자식에서 해당 페이지에 쓰기 시도 시 여유 프레임 리스트에서 빈 프레임을 꺼내 페이지를 복사한다.
- 시도 주체의 페이지 테이블에만 매핑시켜 다른 프로세스 페이지를 변경하지 않는다.
페이지 교체 알고리즘
물리 메모리의 프레임이 부족한 상황이 발생하면 페이지 부재 시 여유 프레임 리스트에 빈 프레임이 없음을 알게 되는데 이때 두 선택지가 존재한다.
- 해당 프로세스를 즉시 종료 시킨다.
- 표준 스와핑 기법으로 사용하지 않는 프로세스 전체를 디스크로 밀어내 메모리를 확보한다.
- 오버헤드가 커서 잘 사용하지 않는다.
두 선택지 모두 극단적이기 때문에, 페이지 교체 알고리즘을 통해 부족한 프레임을 확보한다.
선입선출 교체 알고리즘
페이지를 큐 구조로 유지하고 각 페이지가 메모리 안으로 들어간 시간을 체크한다.
프레임 부족 시 시간이 가장 긴 페이지를 우선적으로 교체하는 알고리즘이다.
- 교체 과정
1) Queue.Head 선택
2) 제거 페이지 스왑 아웃
3) 페이지 테이블 유효 비트 변경
4) 새로운 페이지 스왑 인
5) 페이지 테이블 유효 비트 변경
6) Q.insert(새로운 페이지) - 장점: 이해 및 구현이 쉽다
- 단점: 성능이 항상 좋음을 보장하지 못하고, 프레임이 많으면 페이지 부재가 증가한다.(벨래디의 변이 현상)
최적 페이지 교체 알고리즘(OPT, OPTimal Replacement Algorithm)
앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 알고리즘이다.
- 장점: 모든 페이지 교체 알고리즘 중 가장 페이지 부재 비율이 낮다.
- 단점: 언제 사용할건지의 정보가 필요한데 이를 알기 어려워 구현의 어려움이 크다.
최근 최소 사용 교체 알고리즘(LRU, Least Recently Used)
가장 최근 접근한 페이지는 곧 다시 사용할 페이지라는 예측을 통해 교체하는 알고리즘이다.
즉, 오랫동안 사용하지 않은 페이지를 교체하는데 이는 시간적 지역성 원리를 기반으로 한다.
- 알고리즘을 구현하는 H/W의 지원이 필요하다.
- 카운터(계수기)를 이용한 순서 결정 방법
- 페이지 테이블 항목에 사용시간 레지스터를 연관시키고, 프로세서에 논리 클록을 추가해 카운터 필드를 덧붙여 프레임 순서를 결정한다.
- 스택을 이용한 순서 결정 방법
- 페이지 번호를 스택에 넣어 관리하고 페이지 참조 시 해당 페이지 번호를 Stack.Top에 두어 순서를 결정한다.
- Stack.Top == 가장 최근 사용 / Stack.Bottom == 가장 과거에 사용
- 스택의 중간에서 항목을 가져와야 해 추가 오버헤드가 발생할 수 있지만 이중 연결 리스트로 해결할 수 있다.
- 카운터(계수기)를 이용한 순서 결정 방법
최근 최소 사용 근접 알고리즘
최근 최소 사용 교체 알고리즘보다 저렴한 가격으로 사용할 수 있느 알고리즘이다.
- 참조 비트 형태를 지원해 처음 모든 참조 비트를 0으로 초기화시킨 후 참조될 때 해당 페이지의 비트를 1로 변환한다.
- 이 다음 어느 페이지를 사용했는지 부분 순서 정보로 확인할 수 있는
참조 비트 알고리즘또는시계 알고리즘을 만들어야 한다.
NUR 알고리즘
최근 사용하지 않은 페이지를 교체해 낮은 오버헤드로 LRU와 동일하게 사용 가능한 알고리즘이다.
- 최근 사용하지 않은 페이지는 곧 다시 사용하지 않을꺼라는 전략을 가지낟.
- 참조 비트(R)과 수정 비트(M) 두 비트를 추가해 페이지 사용과 수정 여부를 확인한다.
0 == 수행되지 않음, 1 == 수행되었음뜻을 가지며 맨 좌측부터 우측 순으로 교체된다.- (0,0), (0,1), (1,0), (1,1)
최소 사용 빈도수 알고리즘(LFU, Least Frequently Used)
각 페이지마다 참조 횟수 카운터를 두고 횟수가 가장 작은 페이지를 교체하는 알고리즘이다.
- 초기에 많이 사용되었다가 이후 다시 사용되지 않는 페이지가 존재할 때 문제가 발생한다.
- 일정 시간 간격으로 하나씩 오른쪽으로 이동시켜 지수적으로 감소하는 평균 사용 수를 형성해 문제를 해결할 수 있다.
최대 사용 빈도수 알고리즘(MFU, Most Frequently Used)
계수가 가장 작은 페이지를 방금 들어와 아직 사용되지 않아 곧 사용할 확률이 높다고 판단해 교체 페이지 후보에서 제외하는 알고리즘이다. 즉, 가장 계수가 가장 큰 페이지(=가장 많이 사용한 페이지)를 교체한다.
- LFU, MFU 두 알고리즘 모두 비용이 많이 들고 성능이 떨어진다.
페이지 버퍼링
LRU와 시계 알고리즘은 선입선출보다 성능이 좋지만, 복잡성과 페이지 교체로 오버헤드가 크다.
선입선출처럼 성능이 떨어지는걸 막고자 교체 대상으로 선택한 페이지를 바로 교체하지 않은 채 잠시 메인 메모리에 유지하는 방식이다.
스래싱
메인 메모리에 상주할 프로세스 수를 효율적으로 관리해야한다.
- 너무 적은 프로세스 수 -> 대기 상태가 빈번해진다.
- 너무 많은 프로세스 수 -> 페이지 부재로 인해 교체 작업이 증가한다.
어떤 상황이던간에 페이지 교환이 계속 일어나는 현상을 스래싱이라고 한다.
다시말해 프로세스가 수행 시간보다 페이지 교환 시간이 더 길면 스래싱 상태라고 한다.
발생 원인
- 프레임 부족 -> 페이지 부재 급증 -> CPU 이용률 감소 -> CPU 이용률 회복 시도(다중 프로그래밍 정도 증가) -> 프레임 부족 악화 및 페이지 부재 급증 -> 페이지 교체만 반복
예방
- 다중 프로그래밍 정도와 CPU 이용률을 이용해 스래싱을 조기 발견할 수 있다.
- 지역 교환 알고리즘 또는 우선순위 교환 이용해 예방할 수 있다.
- 지역 교환 알고리즘: 프로세스 하나에 스래싱이 발생해도 다른 프로세스에서 프레임을 가져올 수 없어 스래싱 전파가 일어나지 않는다.
- 데닝의 50% 수준의 다중 프로그래밍 정도 제안
- 프로세스에 필요한만큼 프레임 수 제공 -> 가장 확실한 예방이지만 프레임 수는 한계가 있다.
생각 정리
페이지 크기에 대한 Trade-Off
- 작은 페이지
- 장점: 내부 단편화 감소
- 단점: 페이지 테이블 엔트리 수 증가
- 큰 페이지
- 장점: 페이지 부재 횟수 감소
- 단점: 내부 단편화 증가
페이지 크기가 커지면 페이지 부재가 더 많이 발생할까?
발생하지 않는다. 큰 페이지는 한 부재시 더 많은 데이터를 가져오기 때문에 페이지 부재 횟수는 줄어들지만 대신 페이지 부재 한번 당 비용이 커진다.
세그멘테이션 방식을 사용한다면 가상 메모리를 사용할 수 있을까?
세그멘티이션 방식으로도 수요 페이지 기법과 스와핑으로 구현할 수 있어서 가상 메모리를 사용할 수는 있다. 현대 OS에서는 페이징+세그멘테이션을 하이브리드로 주로 쓰고 있다.
학습하며 정리한 글이기 때문에 혼용된 표현 또는 잘못된 내용이 있을 수 있습니다.
만약, 발견하신 경우 댓글을 통해 알려주신다면 진심으로 감사드립니다.
