페이징(Paging)
무엇인가?
프로세스의 주소 공간을 동일한 크기의 페이지 단위로 나누어 물리적 메모리의 서로 다른 위치에 페이지들을 저장하는 방식이다.
왜 쓰는가?
연속 할당에서 발생하는 동적 메모리 할당 문제가 발생하지 않는다. 빈 공간 활용이 쉬우므로 외부조각 문제 발생 가능성이 작다.
동적 메모리 할당 문제: 주소 공간의 크기가 n인 프로세스를 메모리에 올릴 때 물리적 메모리 내 가용 공간 중 어떤 위치에 올릴 것인지 결정하는 문제
주소 변환 기법
페이징 기법에서는 CPU가 사용하는 논리적 주소를 페이지 번호(p)와 페이지 오프셋(d)로 나누어 주소 변환에 사용한다.
페이지 번호(p)
각 페이지 별 주소 변환 정보를 담고 있는 테이지 테이블 접근시 인덱스로 사용
페이지 오프셋(d)
하나의 페이지 내에서의 변위를 알려준다.
- 기준 주소값 + 변위 = 논리적 주소에 대응하는 물리적 주소
페이지 테이블 구현
무엇인가?
페이징 기법에서 주소 변환을 하기 위한 자료구조로, 물리적 메모리에 위치한다. CPU에서 실행 중인 프로세스의 페이지 테이블에 접근하기 위해 운영체제는 2개의 레지스터를 사용한다.
페이지 테이블 기준 레지스터(page-table base register)
메모리 내에서의 페이지 테이블의 시작 위치를 가르킨다.
페이지 테이블 길이 레지스터(page-table length register)
페이지 테이블의 크기를 보관한다.
계층적 페이징
무엇인가?
사용되지 않는 주소 공간에 대해 페이지 테이블의 항목을 설정하지 않아 메모리 공간을 절약하는 방법.
왜 쓰는가?
프로세스 수가 증가함에 따라 전체 메모리의 상당 부분이 주소 변환을 위한 페이지 테이블에 할애되어 메모리를 낭비하는 것을 방지하기 위해.
구성
외부 페이지 테이블(outer page table)
사용되지 않는 주소 공간에 대해 외부 페이지의 테이블 항목을 Null로 설정한다.
내부 페이지 테이블(inner page table)
테이블 항목이 Null이 아닌 경우 대응하는 페이지 테이블을 생성한다.
특징
메모리 공간 효율을 높일 수 있지만 주소 변환을 위해 접근하는 페이지 테이블 수가 증가하여 시간적인 손해가 뒤따른다.
역페이지 테이블
무엇인가?
물리적 메모리의 페이지 프레임 하나당 페이지 테이블에 하나씩의 항목을 둔다. 즉, 각 프로세스마다 페이지 테이블을 두지 않고, 시스템 전체에 페이지 테이블을 하나만 둔다.
왜 쓰는가?
페이지 테이블로 인한 메모리 공간 낭비가 심한 이유는 모든 프로세스의 모든 페이지에 대해 페이지 항목을 구성해야 하기 때문이다. 모든 프로세스가 아니라 시스템에 하나의 페이지 테이블을 만든다면 메모리 공간 낭비를 줄일 수 있다.
특징
역페이지 테이블은 논리적 주소 -> 물리적 주소가 아니라 물리적 주소 -> 논리적 주소를 얻기에 수월한 구조이다. 따라서 시간면에서 상대적으로 비효율적이다.
과정
- 역페이지 테이블에 주소 변환 요청이 들어온다.
- 그 주소를 담은 페이지가 물리적 메모리에 존재하는지 여부를 판단하기 위해 페이지 테이블 전체를 탐색한다.
이 과정에 시간이 많이 소요되므로 역페이지 테이블은 일반적으로 메모리에 유지하는 대신에 연관 레지스터(associative register)에 보관해 테이블 전체 항목에 대한 병렬 탐색을 가능하게 하여 시간적 효율성을 높힌다.
공유 페이지
무엇인가?
메모리 공간의 효율적인 사용을 위해 여러 프로세스에 의해 공통으로 사용될 수 있도록 작성된 코드(공유 코드: shared code)를 담고 있는 페이지
왜 쓰는가?
여러 프로세스에 공유되므로 물리적 메모리에 하나만 적재되어 메모리를 효율적으로 사용할 수 있다.
특징
공유 코드는 읽기 전용이어야 하며 모든 프로세스의 논리적 주소 공간에서 동일한 위치에 존재해야 한다.
메모리 보호
페이지 테이블의 각 항목에는 주소 변환 정보 뿐만 아니라 메모리 보호를 위한 보호비트(protection bit)와 유효-무효 비트(valid-invalid bit)를 두고 있다.
보호비트(protection bit)
각 페이지에 대한 접근 권한의 내용을 담고 있다.
유효-무효 비트(valid-invalid bit)
해당 페이지의 내용이 유효한지에 대한 내용을 담고 있다.
세그멘테이션(Segmentation)
무엇인가?
프로세스의 주소 공간을 의미 단위의 세그먼트(Segment)로 나누어 물리적 메모리에 올리는 기법이다.
특징은?
프로세스의 주소 공간이 통째로 메모리에 적재되는 것이 아니라 나뉘어져 적재된다는 면에서 페이징과 유사하다. 그러나 페이징과 달리 의미 단위의 세그먼트로 나누어 관리하므로 크기가 균일하지 않은 세그먼트들을 메모리에 적재하는 관리 오버헤드가 뒤따른다.
구현
세그먼트 테이블
주소 변환을 위해 세그먼트 테이블을 사용한다. 세그먼트 테이블의 각 항목은 기준점(base)와 한계점(limit)을 가지고 있다.
기준점(base): 물리적 메모리에서 그 세그먼트의 시작 위치를 나타낸다.한계점(limit): 세그먼트의 길이를 나타낸다.
세그먼트 테이블 기준 레지스터(STBR: Segment-Table Base Register)
현재 CPU에서 실행 중인 프로세스의 세그멘트 테이블이 메모리의 어느 위치에 있는지 시작 주소를 저장한다.
세그먼트 테이블 길이 레지스터(STLR: Segment-Table Length Register)
그 프로세스의 주소 공간이 몇 개의 세그먼트로 구성되는지 개수를 저장한다.
메모리 보호
페이징 기법과 마찬가지로 세그멘테이션 기법도 메모리 보호를 위한 보호비트(protection bit)와 유효-무효 비트(valid-invalid bit)를 두고 있다.
장점
의미 단위로 나뉘어져 공유와 보안 측면에서 페이징 기법에 비해 효과적이다.
- 접근 권한 제어를 할 경우 의미 단위로 이뤄지기 때문이다.
단점
세그먼트의 길이가 균일하지 않기 때문에 물리적 메모리 관리에서 외부 조각이 발생한다.
페이지드 세그멘테이션(Paged Segmentation)
무엇인가?
페이징과 세그멘테이션의 장점을 취하기 위한 기법이다. 세그멘테이션과 마찬가지로 프로그램을 의미 단위의 세그먼트로 나누되 이를 동일한 크기 페이지들의 집합으로 구성한다. 그리고 물리적 메모리에 적재하는 단위는 페이지 단위로 한다.
페이지 교체 알고리즘
무엇인가?
메모리에 적재된 페이지 중 하나를 디스크로 내보내 메모리에 빈 공간을 확보하는 작업
왜 쓰는가?
페이지 부재가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어오는데, 물리적 메모리가 가득 차면 빈 프레임이 존재하지 않을 수 있기 때문에. 페이지 부재율을 최소화하는 것이 목표이다.
최적 페이지 교체
페이지 부재율을 최소화하기 위해서는 페이지 교체시 물리적 메모리에 존재하는 페이지 중 가장 먼 미래에 참조될 페이지를 쫓아내면 된다. 이는 이상적인 최적의 알고리즘이며, 모든 알고리즘은 최적 페이지 알고리즘보다 비효율적이다.
FIFO(First In First Out)
페이지 교체시 물리적 메모리에 가장 먼저 올라온 페이지를 우선 내쫓는다. 페이지의 향후 참조 가능성을 고려하지 않으므로 이상 현상(FIFO anomaly)가 발생한다.
LRU(Least Recently Used)
메모리 페이지의 시간지역성(temporal locality) 관점으로 페이지 교체시 가장 오래전에 참조된 페이지를 내보낸다.
LFU(Least Frequently Used)
과거 참조 횟수가 가장 적었던 페이지를 쫓아내고 그 자리에 새로 참조될 페이지를 적재한다. LRU보다 오랜 참조 기록을 반영할 수 있지만 시간에 따른 페이지 참조 변화를 반영하지 못하고 LRU보다 구현이 복잡하다.
클럭 알고리즘(Clock algorithm)
하드웨어적인 지원을 통해 알고리즘 운영 오버헤드를 줄인 방식이다. 오랫동안 참조되지 않은 페이지 중 하나를 교체한다. LRU와 유사하지만 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 않는다. 하드웨어적 지원으로 빠르고 효율적으로 이뤄지므로 대부분의 시스템에서 페이지 교체 알고리즘으로 채택한다.
과정
- 교체할 페이지를 선정하기 위해 페이지 프레임들의 참조비트(reference bit)를 순차적으로 조사한다.
- 참조비트가 1인 페이지는 0으로 바꾸고 0인 페이지는 교체한다.
즉, 시곗바늘이 한 바퀴 도는 동안 다시 참조되지 않은 페이지를 교체한다.
참고
