요구 페이징(Demand Paging)
메모리 관리자는 프로세스가 필요로 하는 데이터를 언제 메모리로 가져올지 결정하는 '가져오기 정책', 가져온 프로세스를 메모리의 어느 위치에 올려놓을지 결정하는 '배치 정책', 메모리가 곽 찼을 때 메모리 내에 있는 어떤 프로세스를 내보낼지 결정하는 '재배치 정책'에 따라 메모리를 관리한다.
'가져오기 정책'은 프로세스가 요청할 때 메모리로 가져오는 방법이 일반적인데 이를 요구 페이징(Demand Paging)이라고 한다.
1. 요구 페이징의 개요
컴퓨터를 오래 쓰다보면 시스템이 느려진다. 이때 컴퓨터의 전원을 껐다가 다시 켜면 시스템이 빨라진다. 컴퓨터를 오래 켜두면 시스템이 느려지는 이유는 작업을 하지 않고 쉬는 프로세스나 좀비 프로세스가 메모리를 차지하여 메모리 관리가 복잡해지기 때문이다. 따라서 메모리에는 꼭 필요한 프로세스만 유지하는 것이 좋다.
용량이 큰 프로세스를 실행한다고 생각해보자. 운영체제는 프로세스를 구성하는 모듈을 전부 메모리에 올리지 않는다. 필요한 모듈만 메모리에 올려 실행하고 나머지 모듈은 필요하다고 판단될 때 메모리로 불러온다. 이렇게 프로세스의 일부만 메모리로 가져오는 이유는 다음과 같다.
- 메모리가 꽉차면 관리하기 어려우므로 가급적 적은 양의 프로세스만 유지한다. 즉 메모리를 효율적으로 관리하기 위해서 이다.
- 용량이 큰 프로세스를 전부 메모리로 가져와 실행하면 응답이 늦어질 수 있으므로 필요한 모듈만 올려 실행한다. 즉 응답 속도를 향상하기 위해서이다.
예를 들어, 포토샵과 같은 대형 프로그램을 실행하는 경우를 생각해보자. 포토샵에는 본 프로그램 외에도 피부 보정 필터, 노이즈 제거 필터 같은 외부 필터가 있다. 그런데 포토샵을 실행할 대 본 프로그램과 외부 필터를 메모리에 모두 올리면 메모리를 많이 차지할 뿐만 아니라 프로그램이 시작하는 시간도 오래 걸린다. 따라서 메모리에는 포토샵의 본 프로그램만 올리고 필터는 사용자가 필요로 할 때마다 메모리로 가져오는 것이 효율적이다.
포토샵과 같이 프로그램의 일부만 가져와 실행하고 사용자가 특정 기능을 요구할 때 해당 모듈을 메모리에 올리면 메모리의 절약, 메모리의 효율적 관리, 프로세스의 응답 속도 향상 등의 효과를 볼 수 있다. 이처럼 사용자가 요구할 때 해당 페이지를 메모리로 가져오는 것을 요구 페이징이라고 한다.
미리 가져오기는 *요구 페이징과는 반대로 앞으로 필요할 것이라고 예상되는 페이지를 미리 가져오는 방식이다. 미리 가져오기의 대표적인 경우가 바로 캐시이다. 캐시는 앞으로 필요할 것이라고 예상되는 부분을 고속의 캐시 메모리에 가져다 놓음으로써 시스템의 성능을 향상시킨다. 그러나 미리 가져온 데이터가 쓸모없을 경우 피해가 매우 크다. 따라서 현대 운영체제는 요구 페이징을 기본**으로 사용하고 있다.
프로세스 입장에서는 프로세스를 구성하는 모든 페이지가 한거번에 메모리로 올라오는 것이 좋다. 이렇게 프로세스를 구성하는 모든 페이지를 메모리에 올리는 것을 순수한 스와핑(swapping)이라고 한다. 이와 달리 사용자가 요구할 때 메모리에 올리는 것은 게으른 스와퍼(lazy swapper)라고 한다.
2. 페이지 테이블 엔트리의 구조
가상메모리의 크기는 물리 메모리와 스왑 영역을 합친 것이다. 스왑 영역은 하드디스크에 존재하나 메모리 관리자가 관리하는 영역으로 가상 메모리의 구성 요소 중 하나이다. 스왑 영영에서 물리 메모리로 데이터를 가져오는 것을 스왑인, 물리 메모리에서 스왑 영역으로 데이터를 보내는 것을 스왑아웃이라고 한다.
가상 메모리 시스템에서 사용자의 프로세스는 물리 메모리와 스왑 영역 중 한 곳에 있다. 이 때 페이지가 스왑 영역에 있는 경우는 크게 두 가지이다. 하나는 요구 페이징(Demand Paging)으로 인해 처음부터 물리 메모리에 올라가지 못한 경우이고, 또 하나는 메모리가 꽉 차서 스왑 영역으로 옮겨 온 경우이다. 어떤 경우든 페이지 테이블에는 페이지가 메모리에 있는지, 스왑 영역에 있는지 표시해야 하는데 이때 사용하는 비트가 바로 유효 비트이다.
위 그림은 페이지 테이블 엔트리(PTE)의 구성을 나타낸 것이다. PTE는 페이지 테이블의 한 행을 말한다. 페이지 테이블 엔트리는 페이지 번호, 플래그 비트, 프레임 번호로 구성된다. 몇몇 비트는 CPU에 따라 추가되거나 빠지기도 한다.
PTE의 맨 앞에 있는 페이지 번호는 이전에 설명한 주소 변환 방식 중 직접 매핑에서는 필요없다. 그러나 연관 매핑에서는 페이지 번호와 프레임 번호가 둘 다 필요하다. 페이지 번호는 매핑 방식에 따라 포함되기도 하고, 포함되지 않다.
PTE의 마지막에 있는 프레임 번호는 가상 주소의 해당 페이지가 어느 프레임에 있는지 알려주는 자료 구조로 페이지 테이블의 핵심이다. 메모리 관리자는 찾은 프레임 번호를 이용하여 가상 주소를 물리 주소로 변환한다. 프레임 번호는 주소 필드(address field)라고도 하므로 이후로는 주소 필드로 말해도 프레임 번호로 생각하면 된다. PTE의 가운데에는 접근 비트, 변경 비트, 유효 비트, 읽기 비트, 쓰기 비트, 실행 비트 등을 모아놓은 플래그 비트가 있다.
- 접근 비트: 접근 비트(access bit)는 페이지가 메모리에 올라온 후 사용한 적이 있는지 알려주는 비트이다. 즉 해당 메모리에 읽거나 실행 작업을 했다면 접근 비트가 1이 된다. 접근 비트는 참조 비트(reference bit)라고도 한다.
- 변경 비트: 변경 비트(modified bit)는 페이지가 메모리에 올라온 후 데이터의 변경이 있었는 지 알려주는 비트이다. 즉, 해당 메모리에 쓰기나 추가 작업을 했다면 변경 비트가 1이 된다. 변경 비트는 데이터가 새로운 값으로 오염되었다는 의미에서 더티 비트(dirty bit)라고도 불린다.
- 유효 비트: 유효 비트(valid bit)는 페이지가 실제 메모리에 있는 지를 나타내는 비트이다. 가상 메모리 시스템에서는 물리 메모리가 부족할 경우 일부 페이지가 스왑 영역으로 옮겨진다. 이는 프로세스가 물리 메모리에 접근했을 때 해당 데이터가 메모리에 있지 않고 저장장치에 있을 수 있다는 의미이다. 유효 비트는 해당 페이지가 메모리에 있는 지를 나타내므로 현재 비트(present bit)라고도 한다. 0이면 메모리에 있는 것이고, 1이면 스왑 영역에 있다는 것을 의미한다.
- 읽기, 쓰기, 실행 비트: 읽기 비트(read bit), 쓰기 비트(write bit), 실행 비트(execute bit)는 페이지에 대한 읽기 권한, 쓰기 권한, 실행 권한을 나타내는 비트이다. 읽기 권한이 없는 프로세스가 읽으려고 하거나 쓰기 권한이 없는 프로세스가 쓰려고 할 때 접근을 차단하는 데 사용한다. 읽기 비트, 쓰기 비트, 실행 비트를 합쳐서 접근 권한 비트(right bit)라고도 부른다. 세그먼테이션-페이징 혼용 기법에서 테이블의 크기를 줄이기 위해 접근 제한 비트를 세그먼테이션 테이블로 옮겼다.
접근 비트(access bit, reference bit)와 변경 비트(modified bit, dirty bit)는 페이지가 메모리에 올라온 후 어떤 작업이 있었는지 알려주는 역할을 한다. 두 비트는 메모리가 꽉 차서 어떤 페이지를 스왑 영역으로 옮겨야 할 지 선택할 때 사용하는데, 이는 뒤에서 자세히 알아보자.
3. 페이지 부재
가상 메모리의 페이지 테이블에는 페이지가 물리 메모리에 있는지, 스왑 영역에 있는지 표시하기 위해 유효 비트(valid bit)을 사용한다.
위 그림은 유효 비트에 따른 주소 필드의 내용을 보여준다. 유효 비트가 0일 때는 페이지가 메모리에 있으므로 주소 필드에 물리 메모리의 프레임 번호가 저장된다. 도한, 유효 비트가 1일 때는 페이지가 스왑 영역에 있으므로 주소 필드에 스왑 영역 내 페이지의 주소가 저장된다.
위 그림은 가상 메모리, 페이지 테이블, 물리 메모리, 스왑 영역을 모두 나타낸 것이다. 가상 메모리의 페이지 0은 물리 메모리의 프레임 3에 있기 때문에 PTE 0의 유효 비트는 0, 주소 필드 값은 프레임 번호 3이다. 그리고 가상 메모리의 페이지 4는 스왑 영역의 1번에 있기 때문에 PTE 4의 유효 비트는 1, 주소 필드 값은 스왑 주소 1이다.
위 그림에서 프로세스가 페이지 3을 요청했다고 가정해보자. PTE 3의 유효 비트가 1, 주소 필드 값이 0이므로 데이터(페이지) 3은 메모리에 없고, 스왑 영역의 0번째에 있다. 이렇게 프로세스가 페이지를 요청했을 때, 그 페이지가 메모리에 없는 상황을 페이지 부재(page fault)라고 한다. page fault가 발생하면 프로세스가 해당 페이지를 사용할 수 있도록 스왑 영역에서 물리 메모리로 옮겨야 한다.
참고로, 페이지라는 단어는 가상 메모리 상의 데이터를 의미하기도 하지만 물리 메모리나 스왑 영역에 있는 데이터를 페이지라고 부르기도 한다. 이에 따라 가상 메모리의 페이지와 구분하기 위해 가상 메모리 안에 있는 페이지는 '가상-페이지와 페이지(virtual page)', 메모리와 스왑 영역에 있는 데이터를 페이지(page)라고 구분하기도 한다.
위 그림은 page fault가 발생했을 때 메모리 관리자가 어떤 작업을 하는 지를 보여준다. 프로세스가 page 3을 요청하면 page table의 유효 비트가 1이기 때문에 page fault가 발생한다. 메모리 관리자는 스왑 영역의 0번에 있는 데이터 D를 메모리의 비어있는 프레임 5로 가져온다.(swap-in) 프레임 5에 데이터 D가 들어오면 PTE 3의 유효 비트는 1에서 0으로, 주소 필드 값은 0에서 5로 바뀐다. 그리고 프레임 5로 접근하여 해당 데이터 D를 프로세스에 넘긴다.
page fault가 발생하면 위와 같은 과정을 거쳐 스왑 영역에 있는 페이지를 메모리의 빈 영역에 올리고 페이지 테이블을 갱신(업데이트)한다. 위에서는 메모리에 빈 프레임이 있어서 작업이 수월하지만 빈 프레임이 없을 때는 메모리에 있는 프레임 중 하나를 스왑 영역으로 보낸 후에야 해당 페이지를 가져올 수 있다. 어떤 페이지를 스왑 영역으로 내보낼지 결정하는 알고리즘을 페이지 교체 알고리즘(page replacement algorithm)이라고 한다. 페이지 교체 알고리즘에 의해 스왑 영역으로 보낼 페이지를 대상 페이지, 희생 페이지(victim page)라고 한다.
위 그림은 메모리가 꽉 찬 상태에서 page fault가 발생했을 때 어떤 작업이 일어나는지를 보여준다. 프로세스가 페이지 4를 요청했다고 가정하자.
- 해당 페이지의 유효 비트(valid bit)가 1이다. 즉 페이지 부재(page fault)가 발생한다.
- 메모리가 꽉 차 있는 상태이기 때문에 스왑 영역에 있는 데이터 E를 가져오기 위해 메모리의 데이터(페이지) 중 하나를 스왑 영역으로 보내야 한다. 물리 메모리의 프레임 3에 저장된 페이지를 대상 페이지(victim page)로 임의 선정하였는데 이 페이지를 스왑 영역으로 옮긴다.(스왑아웃)
- 이에 따라 대상 페이지(victim page) PTE 1의 유효 비트가 0에서 1로, 주소 필드 값이 프레임 3에서 스왑 주소 6으로 바뀐다.
- 스왑 영역 1번에 있던 페이지 E가 프레임 3으로 올라간다.(스왑인)
- 이에 따라 PTE 4의 유효 비트가 1에서 0으로, 주소 필드 값이 스왑 주소 1에서 프레임 3으로 바뀐다.
세그먼테이션 오류와 페이지 부재(page fault)는 많은 차이가 있다. 세그먼테이션 오류는 사용자의 프로세스가 주어진 메모리 공간을 벗어나거나 접근 권한이 없는 곳에 접근할 때 발생한다. 즉, 사용자 프로세스에 의해 발생하며 해당 프로세스를 강제 종료하여 해결한다. 반면 페이지 부재(page fault)는 해당 페이지(데이터)가 물리 메모리에 없을 때 발생하는 오류로 사용자 프로세스와 무관하다. 페이지 부재(page fault)가 발생하면 메모리 관리자는 스왑 영역에서 해당 페이지를 물리 메모리로 옮긴 후 작업을 진행한다.
4. 지역성
메모리가 꽉 차서 어떤 페이지를 스왑 영역으로 보낼 때는 되도록 앞으로 사용하지 않을 페이지를 쫒아내는 것이 좋다. 자주 사용될 페이지를 쫒아내면 다시 물리 메모리로 불러와야 하기 때문에 시스템 성능이 떨어진다. 페이지 교체 알고리즘이 쫒아낼 페이지를 찾을 때는 지역성(locality)을 고려한다.
지역성(locality)은 기억장치에 접근하는 패턴이 메모리 전체 고루 분포되는 것이 아니라 특정 영역에 집중되는 성질을 말한다. 집약성은 크게 3가지로 공간 지역성, 시간 지역성, 순차적 지역성으로 나뉜다.
4-1. 공간 지역성(spacial-locality)
집 바로 옆의 편의점과 길 건너편의 편의점 중 가까이 있는 편의점에 갈 확률이 더 높다. 이와 마찬가지로 공간의 지역성(spacial locality)은 현재 위치에서 가까운 데이터에 접근할 확률이 먼 거리에 있는 데이터에 접근할 확률보다 높다는 것이다.
4-2. 시간 지역성(temporal locality)
1년 전에 산 라면보다 어제 산 라면을 먹을 확률이 더 높다. 이와 마찬가지로 시간 지역성(temporal locality)는 현재를 기준으로 가장 가까운 시간에 접근한 데이터가 더 먼 시간에 접근한 데이터보다 사용될 확률이 높다는 것이다.
4-3. 순차적 지연성(sequential locality)
순차적 지연성(sequential locality)은 여러 작업이 순서대로 진행되는 경향이 있다는 것을 의미한다. 일반적인 프로그래밍은 처음부터 마지막 순서로 진행되는 경향이 있다. 책에 따라서 순차적 지역성을 공간 지역성의 특별한 경우로 보고 지역성을 공간 지역성과 시간 지역성으로만 구분하기도 한다.
지역성 이론은 많은 곳에서 사용된다. 특히 캐시는 지역성 이론을 사용하는 대표적인 장치이다. 시간적으로나 지역적으로나 가까이 있는 데이터를 가져옴으로써 캐시 적중률을 높일 수 있다. 예를 들어 현재 5번 행을 실행하고 있다면 10~19번 행과 200~2019번 행 중에서 당연히 10~19번 행을 가져오는 것이 유리하다. 프로그램을 작성할 대 goto문을 사용하지 말라고 하는 것도 이러한 이유에서이다. 지역성에 근거하여 현재 실행하는 행과 가까운 행을 캐시 메모리로 가져오고 있는데 갑자기 goto문을 사용하여 엉뚱한 행으로 이동해버리면 이미 가져온 데이터가 쓸모 없어진다.
캐시 메모리의 동작과 마찬가지로 페이지 교체 알고리즘에서도 지역성을 고려하여 대상 페이지(victim page)를 선정한다. 자수 사용하는 페이지를 대상 페이지(victim page)로 선정하면 시스템의 성능이 저하될 것이므로, 페이지 교체 알고리즘에서는 앞으로 적게 사용될 페이지를 대상 페이지로 선정함으써 page fault를 줄이고 컴퓨터의 성능을 높인다.
