가상 메모리

1. 가상 메모리 개요

컴퓨터마다 실제 메모리의 크기가 다르다. 만약 운영체제나 프로세스가 4GB 메모리에서 동작하도록 만들어졌다면 이보다 작은 메모리를 가진 컴퓨터에서는 실행되지 않을 것이다.

가상 메모리는 이 문제를 완벽하게 해결했다. 프로세스는 운영체제 영역이 어디 있는지, 물리 메모리가 얼마나 큰지 몰라도 된다. 즉, 프로그래머는 물리 메모리의 크기와 프로세스가 메모리 어느 위치에 올라가는지 신경쓰지 않고 0x0번지에서 시작된다고 생각하고 프로그래밍을 하면 된다.

프로세스는 메모리 관리자를 통해 메모리에 접근한다. 프로세스 입장에서는 물리 메모리에 직접 접근할 일이 없고, 메모리 관리자에게 요청만 하면 된다. 메모리 관리자는 프로세스의 요청이 있으면 그에 맞는 물리 메모리로 연결시켜준다.

가상 메모리의 크기는 이론적으로는 무한대이지만, 실제로는 물리 메모리 크기와 CPU의 비트 수로 결정된다. 만약 32bit CPU인 경우 표현할 수 있는 주소 값이 2^32로 대략 4GB 정도 되고, 가상 메모리 크기도 똑같이 4GB이다. 32bit CPU의 경우 최대 메모리 크기가 4GB라고 했는데 운영체제를 포함해서 수많은 프로세스들은 어떻게 실행시킬까?

4GB를 차지하는 프로세스 5개와 운영체제를 실행시킨다고 가정해보자. 그럼 운영체제를 제외하고도 적어도 20GB가 필요한데 4GB로는 턱없이 부족하다. 이럴때 가상 메모리 시스템은 물리 메모리 내용의 일부를 하드디스크에 있는 스왑 영역으로 옮기고, 처리가 필요할 때 물리 메모리로 가져와 실행시키기 때문에 운영체제와 프로세스 5개를 전부 실행시킬 수 있다.

메모리 관리자는 물리 메모리와 스왑 영역을 합쳐서 프로세스가 사용하는 가상 주소를 물리 주소로 변환하는데, 이것을 동적 주소 변환(Dynamic Address Translation)이라고 부른다. 동적 주소 변환을 거치면 프로세스는 마음대로 사용자 데이터를 물리 메모리에 배치시킬 수 있다. 메모리 관리자는 물리 메모리를 어떻게 나눌지, 프로세스를 어디다 배치할지, 부족한 물리 메모리는 어떻게 처리할지와 같은 문제를 처리해야 하기 때문에 복잡한 과정을 거친다.

실제 물리 주소 0x0번지는 운영체제 영역이므로 프로세스가 사용할 수 없다. 가상 메모리 시스템에서는 운영체제 영역을 제외한 나머지 영역을 일정한 크기로 나누어서 프로세스에게 할당하는데, 할당하는 방식은 메모리 분할 방식과 마찬가지로 가변 분할 방식과 고정 분할 방식으로 나뉜다.

가상 메모리 시스템에서는 가변 분할 방식을 이용한 세그멘테이션, 고정 분할 방식을 이용한 페이징이라는 것이 있다. 세그멘테이션에서는 외부 단편화와 같은 단점이 있고, 페이징에는 내부 단편화와 같은 단점이 있기 때문에 이 단점을 보완한 세그멘테이션-페이징 혼용기법을사용한다.

가상 메모리 시스템에서 가상 주소는 메모리나 스왑 영역 한 곳 중 위치한다. 메모리 관리자는 가상 주소와 물리 주소를 1대 1 매핑 테이블로 관리한다.

2. 세그멘테이션(배치정책)

가변 분할 방식을 이용하는 세그멘테이션을 알아보자. 세그멘테이션에서 프로그램은 함수나 모듈 등으로 세그먼트를 구성한다. 프로그램 입장에서 메모리를 살펴보면 메인 코드가 있는 세그먼트, 전역 데이터들이 있는 세그먼트, 힙 영역이 있는 세그먼트, 스택 영역이 있는 세그먼트 등이 있다. 각 세그먼트들은 서로 인접할 필요는 없다. 반면 프로세스 입장에서는 우리가 앞서 봤던 것처럼 코드 영역, 데이터 영역, 힙 영역, 스택 영역을 서로 인접한 것처럼 바라본다. 사용자와 프로세스, CPU가 바라보는 주소는 논리 주소라고 한다. 실제 물리 주소로 변환은 중간에서 메모리 관리자가 해준다.

그럼 메모리 관리자는 어떻게 논리 주소를 물리 주소로 변환해줄까?

메모리 관리자는 세그멘테이션 테이블이라는 것을 가지고 있다. 세그멘테이션 테이블에는 Base Address와 Bound Address 정보가 저장되고 이걸 이용해 물리 메모리 주소를 계산한다. CPU에서 논리 주소를 전달해주면 메모리 관리자는 이 논리 주소가 몇 번 세그먼트인지 알아낸다. 그러면 메모리 관리자 내에 Segment Table Base Register(STBR)를 이용해서 물리 메모리 내에 있는 세그멘테이션 테이블을 찾고 세그먼트 번호를 인덱스로 Base Address와 Bound Address를 찾는다. 참고로 운영체제는 컨텍스트 스위칭을 할 때마다 메모리 관리자 내의 Segment Table Base Register를 해당 프로세스의 것으로 값을 바꿔줘야 한다. 컨텍스트 스위칭은 이런 작업까지 하기 대문에 굉장히 무거운 동작이다.

Bound Address는 세그먼트의 크기를 나타낸다. 메모리 관리자는 CPU에서 받은 논리 주소와 이 Bound Address의 크기를 비교한다. 만약 논리 주소가 Bound Address보다 작다면 논리 주소와 Base Address를 더해 물리 주소를 구하고 논리 주소가 Bound Address보다 크다면 메모리를 침범했다고 생각하고 인터럽트를 발생시켜 프로세스를 종료시킨다.

세그멘테이션의 장점은 메모리를 가변적으로 분할할 수 있고 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 모듈로 처리할 수 있기 때문에 공유와 각 영역에 대한 메모리 접근 보호가 편리하다. 반면 단점으로는 가변 분할 방식의 단점인 외부 단편화가 발생한다.

3. 페이징(배치정책)

이번에는 고정 분할 방식을 이용한 페이징을 알아보자. 세그멘테이션 기법은 외부 단편화 문제가 있기 때문에 이를 해결하기 위해 고안되었다.

페이징은 메모리를 할당할 때 정해진 크기의 페이지로 나눈다. 모든 페이지는 크기가 같기 때문에 관리과 굉장히 쉬워진다. 또한 일정한 크기로 나눴기 때문에 외부 단편화 현상이 일어나지 않는다. 여기에 논리 주소 공간과 물리 주소 공간이 있다.

논리 주소 공간은 사용자와 프로세스가 바라보는 주소 공간이고, 물리 주소 공간은 실제 메모리에서 사용되는 주소 공간이다. 페이징에서 논리 주소 공간은 일정한 크기로 균일하게 나뉜다. 이것을 페이지라고 부른다. 물리 주소 공간도 페이지의 크기와 똑같이 나뉘는데 이걸 프레임이라고 부른다.

그럼 페이징의 주소 변환을 어떻게 하는지 알아보자. 세그멘테이션과 마찬가지로 메모리 관리자는 테이블을 가지고 있는데 이를 페이지 테이블이라고 부른다. CPU 테이블에서 논리 주소를 전달해주면 메모리 관리자는 이 논리 주소가 몇 번 페이지인지, 오프셋은 얼마인지 알아낸다. 그리고 메모리 관리자 내에 Page Table Base Register(PTBR)를 이용해서 물리 메모리에 있는 페이지 테이블을 찾고, 페이지 번호를 인덱스로 프레임 번호를 알아내고 오프셋을 이용해 물리 주소로 변환한다.

• 페이지 넘버 : 논리주소 / 페이지 크기
• 오프셋 : 논리주소 % 페이지 크기

오프셋은 계산을 통해 쉽게 구할 수 있다. 페이지 테이블에 Invalid로 표시되어 있으면 스왑 영역, 즉 하드웨어에 저장되어 있다는 의미이다. 세그멘테이션과 마찬가지로 Page Table Base Register는 컨텍스트 스위칭을 할 때마다 해당 프로세스의 것으로 업데이트 해준다.

여기까지보면 세그멘테이션과 페이징은 굉장히 비슷해보인다. 이 둘의 차이점은 무엇일까?

1. 첫번째는 페이지의 크기이다. 세그멘테이션은 프로세스마다 크기가 달라 Bound Address를 가지고 있지만 페이징은 모든 페이지의 크기가 동일해서 크기를 표현하는 Bound Address는 필요하지 않다. 페이징은 이러한 특징 때문에 외부 단편화는 발생하지 않지만 내부 단편화가 발생한다. 정해진 크기의 페이징보다 프로세스의 정보가 작으면 그만큼 공간이 낭비되는데 이를 내부 단편화라고 부른다. 하지만 세그멘테이션의 단점과 비교하면 많은 공간이 낭비되는 게 아니라서 심각하게 생각하지는 않는다.
2. 두번째는 이것도 페이지의 크기 때문에 생긴 차이인데 세그멘테이션은 논리적인 영역별로 세그먼트를 나눈다. 세그먼트마다 크기를 다르게 나눌 수 있으니 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 나눌 수 있다. 하지만 페이징은 페이지의 크기가 고정되어 있어 논리적인 영역별로 나누는 것이 아니라 페이지로 나누기 때문에 논리적인 영역을 나눌 수 없다. 그래서 특정 영역만 딱 떼어내서 공유하거나 권한을 부여하는 게 더 어렵다.

페이징에서 가장 신경써야 할 것은 페이지 테이블의 크기이다. 각 프로세스마다 페이지 테이블을 가지고 있는데, 프로세스가 많아질수록 페이지 테이블도 많아지기 때문에 프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어든다. 실제로 메모리 관리자가 참조하는 페이지 테이블도 물리 메모리의 운영체제 영역에 저장되기 때문에 페이지 테이블 크기가 너무 크면 사용자 영역이 부족하게 된다. 이 때문에 페이지 테이블의 크기를 적절하게 유지하는 것이 굉장히 중요하다.

3. 페이지드 세그멘테이션(배치정책)

페이지드 세그멘테이션은 세그멘테이션과 페이징을 혼합해 장점을 취한 방식이다. 세그멘테이션은 가변 분할 방식이라서 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 세그먼트로 나눠서 관리할 수 있다. 때문에 다른 프로세스와 공유하기도 편하고 각 영역에 대한 메모리 접근 보호를 하기가 쉽다. 페이징은 고정 분할 방식으로 메모리를 효율적으로 관리할 수 있다.

그럼 메모리 접근 권한에 대해 알아보자. 메모리 접근 권한은 메모리의 특정 번지에 부여된 권한으로 읽기, 쓰기, 실행 세 가지가 있다. 프로세스는 코드 영역, 데이터 영역, 스택 영역, 힙 영역이 있는데 각 영역마다 접근 권한이 있다. 코드 영역은 프로그램 그 자체이므로 수정되면 안 되기 때문에 읽기와 실행 권한만 있다. 데이터 영역은 일반 변수, 전역 변수, 상수로 선언한 변수가 저장되기 때문에 읽기 권한이 있고 쓰기 권한은 있거나 없거나이고 당연히 실행 권한은 없다. 스택 영역과 힙 영역은 읽기, 쓰기 권한이 있고 실행 권한은 없다. 메모리 접근 권한에 대한 검사는 가상 주소에서 물리 주소로 변환될 때마다 일어나는데 만약 권한을 위반한다면 에러를 발생시킨다.

세그멘테이션 기법에서 세그멘테이션 테이블은 Base Address와 Bound Address로 구성되어 있었다. 페이징 기법에서 페이지 테이블은 프레임 번호로 구성되어 있었다. 이제 이 둘을 혼합해 페이지드 세그멘테이션으로 만들어보자.

페이지드 세그멘테이션 기법에서는 세그멘테이션 테이블에 권한 비트를 추가한다. 그리고 Base Address는 페이지 넘버로 바뀌고, Bound Address는 페이지 개수로 바뀐다. 각각의 역할은 이름만 달라졌을 뿐 본질적으로는 달라진 건 없다.

만약 가상 주소가 들어오면 먼저 가상 주소를 이용해 몇번 세그먼트인지 알아낸다. 그리고 해당 세그먼트가 메모리 접근 권한을 위반하는지 검사한다. 접근 권한을 위배했으면 프로세스를 종료시키고 위반하지 않으면 페이지 넘버와 페이지 개수를 가져온다. 이제 페이지 넘버로 페이지 테이블에 접근해서 프레임 번호를 가져오고 물리 메모리 내에 해당 프레임에 접근해서 그 위치에서 페이징 개수를 더해 물리 주소를 더한다. 만약 물리 메모리에 해당 프레임이 없다면 스왑 영역에서 물리 영역으로 가져온다.

페이지드 세그멘테이션의 단점은 물리 메모리에 접근하기 위해서 메모리에 접근을 두 번 해야 된다는 것이다. 첫번째는 세그멘테이션을 참조할 때이고, 두번째는 페이지 테이블을 참조할 때 일어난다.

이런 단점 때문에 현대 운영체제는 페이징과 페이지드 세그멘테이션 기법을 적절히 섞어서 사용한다.

4. 디맨드 페이징(가져오기 정책)

우리는 프로세스가 실행될 때 프로세스를 이루고 있는 코드 영역, 데이터 영역, 힙 영역, 스택 영역과 같은 모듈이 모두 메모리에 올라와 실행된다고 알고 있다. 하지만 실제로는 모든 모듈이 메모리에 올라오는 것이 아니라 필요한 모듈만 올라와서 실행된다.

이게 어떻게 가능할까? 컴퓨터 과학자 도널드 커누스는 90대 10이라는 법칙을 발견했다. 프로그램이 실행될 때 90%의 시간이 10%의 코드에서 보내는 것을 의미한다.

이것을 지역성 이론이라고 하는데, 지역성은 두 가지가 있다.

• 첫번째는 공간의 지역성으로 현재 위치에서 가까운 데이터에 접근할 확률이 높다는 것이다.
• 두번째는 시간의 지역성으로 현재 기준에서 가까운 시간에 접근했던 데이터가 먼 시간에 접근했던 데이터보다 접근할 확률이 높다는 것이다.

지역성 이론은 조만간 쓰일 데이터만 메모리에 올리고 당분간 필요하지 않을 것 같은 데이터는 스왑 영역으로 보내 성능을 향상시킨다.

디맨드 페이징은 조만간 필요할 것 같은 데이터를 메모리로 가져오고, 쓰이지 않을 것 같은 데이터는 스왑 영역으로 이동시키는 정책이다.

포토샵을 예시로 들면, 포토샵은 본 프로그램 외에도 이미지에 효과를 주는 외부 필터들이 있다. 이 필터들을 포토샵과 같이 메모리에 모두 올리면 메모리를 많이 차지해서 프로그램이 더 무거워진다. 그래서 본 프로그램만 메모리에 올리고 외부 필터들은 사용자의 요청이 있을 때만 메모리로 가져오는 것이 메모리도 절약되고, 메모리를 효율적으로 관리할 수 있고 프로세스의 응답 속도도 빨라진다.

여기서 잠깐 메모리 계층 구조에 대해 알아보자. 메모리는 레지스터, 캐시, 메인 메모리, 보조 저장장치로 나눌 수 있다. 레지스터는 CPU 내에 존재하고 CPU의 한 사이클에 접근할 수 있어서 굉장히 빠르다. 캐시는 수 사이클에서 수십 사이클 내에 접근할 수 있고, 메인 메모리는 수백 사이클이 걸린다. 반면 보조 저장장치에는 수백만 사이클이 걸려 굉장히 오래 걸린다. 이처럼 메모리에 접근하는 시간이 보조 저장장치 쪽으로 갈수록 느려진다.

디맨드 페이징은 스왑 영역을 보조 저장 장치에 저장하는데, 성능 향상을 위해서는 스왑 영역으로 데이터를 이동시키는 것을 최소화시켜야 한다.

스왑 영역에서 물리 메모리로 데이터를 가져오는 것을 스왑 인이라고 부르고, 물리 메모리에서 스왑 영역으로 데이터를 보내는 것을 스왑 아웃이라고 부른다. 가상 주소가 주어지면 메모리 관리자는 페이지 테이블을 참조해서 물리 메모리가 있는 프레임을 알아내거나 스왑 영역이 있는 위치를 알아내야 하는데, 이를 위해 페이지 테이블에는 여러 가지 비트가 있습니다. 페이지 테이블을 이루고 있는 한 행을 페이지 테이블 엔트리(PTE)라고 부른다. 페이지 테이블 엔트리는 많은 비트들로 구성되어 있다.

접근 비트는 페이지가 메모리에 올라온 후 데이터의 접근이 있었는지 알려주는 비트이다. 메모리에 읽거나 실행 작업을 했다면 1로 바뀌게 된다. 변경 비트는 페이지가 메모리에 올라온 후 데이터의 변경이 있었는지 알려주는 비트이다. 메모리에 쓰기 작업을 했다면 1로 바뀌게 된다. 유효 비트는 페이지가 물리 메모리에 있는지 알려주는 비트이다. 만약 유효 비트가 1이라면 페이지가 스왑 영역에 있고, 0이라면 물리 메모리에 있다는 의미이다. 읽기, 쓰기, 실행 비트는 권한 비트로 해당 메모리에 접근 권한이 있는지 검사하는 비트이다.

프로세스가 가상 메모리에 접근 요청을 했을 때 메모리 관리자는 페이지 테이블을 보고 물리 메모리의 프레임을 찾아내는데 만약 물리 메모리에 없다면 Page Fault라는 인터럽트를 발생시킨다. Page Fault가 발생하면 보조 저장장치의 스왑 영역에 접근하게 되고 해당 프로세스는 대기 상태가 된다. 그럼 스왑 영역에 있는 데이터가 메모리에 올라가는 작업을 시작하고 메모리로 올라갔다면 대기 상태에 있던 프로세스는 다시 실행하게 된다.

스왑영역에서 물리 메모리로 가져오는 스왑 인과 물리 메모리에서 스왑 영역으로 보내는 스왑 아웃을 할 때 어떤 게 적절할지는 운영체제가 판단한다. 이 판단하는 것을 페이지 교체 알고리즘이라고 부른다.

5. 페이지 교체정책

위에서 세그멘테이션과 페이징, 페이지 세그멘테이션으로 메모리 배치 정책을 알아보았다. 또 디맨드 정책으로 메모리에서 가져오기 정책을 알아보았다. 여기서는 메모리가 꽉 찼을 때 어떤 페이지를 스왑 영역으로 보낼지 결정하는 페이지 교체 정책을 알아보자.

프로세스는 데이터 접근을 위해 메모리를 참조하는데, 해당 데이터가 메모리에 없으면 Page Fault가 발생한다. Page Fault가 발생하면 해당 페이지를 스왑 영역에서 메모리로 불러들여야 하는데, 메모리가 꽉 차서 공간이 없다면 메모리에 있는 페이지 중에 하나를 선택해서 스왑 영역으로 옮겨야 한다. 메모리에 있는 페이지를 스왑 영역으로 옮길 때 어떤 페이지를 선택할지 결정하는 정책을 페이지 교체 정책이라 부르고, 페이지 교체 정책에는 여러 가지가 있다.

• Random : 첫번째 방법은 무작위로 선택하는 방법이다. 이 방법은 지역성을 고려하지 않기 때문에 자주 사용되는 페이지가 선택될 때도 있어 성능이 별로 좋지 않다. 그래서 거의 사용되지 않는다.
• FIFO(First In First Out) : 두번째 방법은 메모리에 들어온지 가장 오래된 페이지를 선택하는 방법이다. 마트에서 계산하려고 줄을 기다릴 때는 FIFO와 같은 알고리즘이 공평하지만, 페이지 교체 정책에서는 자주 쓰이는 페이지가 먼저 들어왔다는 이유로 교체되면 공평하지 않을 것이다. 이런 단점이 있지만 구현이 간단하고 성능도 꽤 괜찮아서 조금 변형해서 많이 쓰인다.
• Optimum : 세번째 방법은 앞으로 가장 오랫동안 쓰이지 않을 것 같은 페이지를 선택하는 방법이다. 이 방법은 사실상 구현이 불가능한 이론적인 선택 방법이다. 구현이 불가능해서 필요 없을 것 같지만, 다른 알고리즘과 성능 비교를 위해 많이 쓰인다.
• LRU(Least Recently Used) : 네번째 방법은 최근에 가장 사용이 적은 페이지를 선택하는 방법이다. 지역성 이론의 시간의 지역성에 따르면 최근 사용한 데이터가 앞으로도 사용될 확률이 높기 때문에, 최근에 가장 사용을 적게 한 페이지가 앞으로도 사용될 확룔이 적다는 결론이 나온다. 실제로도 Optimum 알고리즘에 근접한 성능을 보인다. 하지만 프로그램이 지역성을 띄지 않을 땐 성능이 떨어지게 된다. 페이지 테이블 엔트리는 여러 개의 비트와 페이지 넘버가 저장된다고 했는데 이곳에 시간까지 기록하려면 비트가 많이 필요하게 된다. 하지만 많은 비트를 준비하기는 어려우니 실제 LRU를 구현할 때는 적은 비트를 이용해서 LRU를 구현한다.

FIFO의 가장 큰 문제는 빌레이디라는 사람이 제시한 빌레이디의 역설(Belady’s Anomaly)이다. 빌레이디의 역설이란 Page Fault를 줄이려고 메모리를 더 늘려서 프레임 수를 늘렸는데, 오히려 Page Fault가 더 많이 발생하는 역설을 말한다. 빌레이디의 역설은 FIFO에서만 발생하며 LRU에서는 발생하지 않는다.

그럼 LRU가 좋다는 것은 분명해졌으니 LRU를 구현해야 하는데, 시간을 기록해야 하는 LRU는 구현하기 힘들다. 왜냐하면 시간을 기록할 비트가 많이 필요할 뿐만 아니라 많은 비트가 있어도 시간이 아주 오래 지난다고 가정하면 어쩔 수 없이 오버플로우가 발생하게 된다. 그럼 아주 오랜 시간이 지났어도 오버플로우로 값이 초기화되면서 시간을 올바르게 표현할 수 없게 된다.

이때문에 LRU와 유사하게 구현하는 방법을 고안했는데, 이를 클락 알고리즘(Clock Algorithm)이라고 한다. 클락 알고리즘은 접근 비트 하나만 이용한다. 일정 시간 간격마다 모든 페이지의 접근 비트를 0으로 초기화한다. 접근 비트의 초기 값은 0으로 설정되어 있고 만약 페이지가 참조되었다면 1로 설정된다. 그럼 일정 시간 간격마다 페이지가 참조되었는지 아닌지 확인할 수 있다.

클락 알고리즘은 페이지를 원형으로 연결한다. 스왑 영역으로 옮길 페이지를 포인터로 가리키는데, 이를 클락 핸드라고 부른다. 클락 핸드는 시계 방향으로 돈다. 만약 Page Fault가 발생해서 스왑 영역으로 보내야 하는 상황이 나오면 클락 핸드는 현재 참조하고 있는 페이지의 접근 비트를 본다. 만약 접근 비트가 1이라면 해당 접근 비트를 0으로 바꾸고 클락 핸드가 다음 페이지를 가리킨다. 이렇게 반복하다가 접근 비트가 0인 페이지를 발견하면 해당 페이지를 스왑 영역으로 보낸다.

향상된 클락 알고리즘이라는 것도 있는데 이 알고리즘은 접근 비트만 이용하는 것이 아니라 변경 비트까지 본다. 스왑 영역으로 보내지는 가장 순위가 높은 것은 접근 비트가 0이고 변경 비트도 0인 페이지이다. 그 다음으로 접근 비트가 0, 변경 비트가 1인 페이지이고, 그 다음으로 접근 비트가 1, 변경 비트가 0인 페이지이고, 마지막으로 접근 비트가 1이고 변경 비트인 1인 페이지가 교체된다.

이렇게보면 LRU만 사용하고 FIFO는 사용될 일이 없어 보인다. 하지만 부득이하게 FIFO를 사용해야 하는 경우가 있다. LRU에서는 접근 비트를 이용하는데, 하드웨어적으로 접근 비트를 지원하지 않는 시스템에서는 FIFO를 이용할 수 밖에 없다. 어쩔 수 없이 FIFO를 이용하는 상황이 나오기 때문에 FIFO의 성능을 높이기 위한 방법을 고안했다.

FIFO의 장점은 구현이 간단하다는 것인데, 자주 사용되는 페이지가 교체될 수 있는 단점이 있다. 이를 위해 2차 기회 페이지 교체 알고리즘을 고안했는데, FIFO 방식에서 자주 사용되는 페이지에게는 또 한 번의 기회를 주는 것이다. FIFO 방식과 동일하게 동작하지만 Page Fault 없이 페이지 접근에 성공했다면 해당 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장시켜주는 방식이다. 이 알고리즘의 성능은 LRU보다는 안 좋고 FIFO보다는 좋다.

6. 스레싱과 워킹셋

CPU 스케줄링의 목표는 CPU의 사용률을 높이는 것이다. CPU 사용률을 높이는 것은 동시에 실행하는 프로세스의 수, 즉 멀티 프로그래밍 정도를 높이는 것이다. 동시에 실행하는 프로세스의 수가 늘어나면 어떤 프로세스가 I/O 작업으로 CPU를 사용할 수 없을 때 다른 프로세스로 컨텍스트 스위칭을 해서 CPU 사용률을 높일 수 있다.

CPU 사용률을 높이기 위해 멀티 프로그래밍 정도를 늘렸으면 당연히 이 프로세스들이 필요로 하는 공간이 있기 때문에 물리 메모리에 프레임을 할당해야 한다. 하지만 물리 메모리의 크기는 한계가 있기 때문에 모든 프로세스의 모든 프레임을 물리 메모리에 올릴 수 없고, 일부는 스왑 영역에 저장된다.

문제는 멀티 프로그래밍 정도가 늘어난다는 것이다. 멀티 프로그래밍 정도가 늘어나면 제한된 물리 메모리에 모든 프로세스를 올려야 하고, 당장 실행되는 프레임을 제외한 나머지 프레임들은 스왑 영역에 저장되고 Page Fault가 많이 발생하게 된다. 그러면 CPU가 작업하는 시간보다 스왑 작업의 시간이 더 길어지고 CPU 사용률은 떨어지게 된다.

CPU 스케줄러는 CPU 사융률이 낮아지면 더 많은 프로세스를 메모리에 올리게 되고, 이렇게 반복하다보면 어느새 CPU 사용률이 0에 가깝게 떨어지게 된다. CPU 사용률을 높이려 했지만 오히려 더 떨어지는 상황이 나오는데 이를 스레싱이라고 부른다. 스레싱의 근본적인 원인은 물리 메모리의 크기가 부족한 것이다.

이를 하드웨어적으로 해결하려면 메모리 크기를 늘리면 된다. 만약 2GB RAM을 사용하다가 스레싱이 발생한다면 4GB RAM으로 교체해주면 스레싱 발생 시점이 늦춰지기 때문에 컴퓨터 성능이 향상된다. 하지만 무작정 메모리의 크기를 늘린다고 성능은 좋아지지 않는다. 4GB RAM에서 16GB RAM으로 올려도 성능 향상을 느끼기 힘들다. 그 이유는 현재 메모리가 프로세스들이 작업을 하는데 충분한 크기라서 스레싱이 발생하지 않는다면 크기를 늘려도 별다른 점이 없기 때문이다.

운영체제가 스레싱을 소프트웨어적으로 해결하기 위한 방법은 무엇일까. 한 프로세스가 실행될 때 너무 많은 페이지를 할당하면 다른 프로세스가 사용할 페이지가 줄어들기 때문에 효율이 떨어지게 된다. 반대로 너무 적은 페이지를 할당하면 빈번한 Page Fault가 발생하고 스왑 요청이 많아 스레싱이 발생하게 된다. 이를 해결하기 위해 프로세스가 실행되면 일정량의 페이지를 할당하고, 만약 Page Fault가 발생하면 더 많은 페이지를 할당한다. 반대로 Page Fault가 너무 적게 발생하면 페이지를 과하게 할당해 메모리가 낭비되는 것이라고 판단하고 페이지를 회수한다. 이렇게 하면 프로세스가 실행되는 동안 해당 프로세스에게 맞는 적절한 페이지 수가 결정된다.

적절한 페이지 수를 결정했다면 어떤 페이지들을 유지할 것인가를 알아야 한다. 이는 지역성 이론을 따른다. 현재 메모리에 올라온 페이지는 다시 사용할 확률이 높기 때문에 하나의 세트로 묶어서 메모리에 올린다. 이를 워킹셋이라 부른다. 워킹셋은 프로세스가 준비 상태에서 실행 상태가 되는 컨텍스트 스위칭을 할 때 사용된다.

참고

• 그림으로 쉽게 배우는 운영체제