운영체제 - 9

 

1. 요구 페이징

1.1 요구 페이징

프로세스가 필요로 하는 데이터를 언제 메모리로 가져올지 결정하는 것이 가져오기 정책이다. 일반적으로 프로세스가 요청할 때 메모리로 가져오는데, 일르 요구 페이징(Demang Paging)이라고 한다. 컴퓨터를 오래 켜둔 상태로 사용하다보면 느려진다. 그 이유는 작업을 하지 않고 쉬는 프로세스나 좀비 프로세스가 메모리를 차지하여 메모리 관리가 복잡해지기 때문이다.

덩치가 큰 프로세스는 모든 모듈이 메모리에 올라오지 않는다. 필요한 모듈만 올려두고 나머지 모듈은 필요시에만 메모리에 올려서 사용한다. 이러한 방식을 통하여 메모리를 효율적으로 관리 가능하며, 사용자에 대한 응답 속도를 향상시킬 수 있다. 포토샵을 예로 들어보자. 포토샵을 실행하면 기본적인 모듈이 메모리에 올라온다. 그리고 피부 보정 필터나 노이즈 제거 필터는 사용자가 요청할 경우에만 메모리에 올려서 사용한다.

'미리 가져오기'는 요구 페이징과 달리 앞으로 필요할 것으로 예상되는 페이지를 미리 가져오는 방식이다. 대표적으로 캐시가 이에 해당된다.

 

1.2 페이지 테이블 엔트리

가상 메모리는 물리 메모리와 스왑 영역으로 구성된다. 페이지 테이블 엔트리는 페이지 번호와 프레임 번호 외에도 플래그 비트가 있는데, 이 중 페이지 테이블이 물리 메모리에 있는지 혹은 스왑 영역이 있는지를 나타내는 비트가 유효 비트이다. 플래그 비트는 유효 비트 외에도 접근 비트(access bit), 변경 비트(modified bit), 권한 비트(read/write/execute bit)로 구성된다.

- 접근 비트: 해당 페이지가 메모리에 올라온 후 사용되었는지 여부를 나타냄. 해당 메모리를 읽거나 실행하였다면 1이 된다.

- 변경 비트: 해당 페이지가 메모리에 올라온 후 변경되었는지 나타냄.

- 유효 비트: 해당 페이지가 물리 메모리에 있는지 혹은 스왑영역에 있는지 여부를 나타냄.

- 읽그, 쓰기, 실행 비트: 접근 권한 비트로 세그먼테이션-페이징 혼용 기법으로 관리됨.

 

1.3 페이지 부재

특정 프로세스가 페이지를 요청했을 때 물리 메모리에 해당 페이지가 없는 상황을 페이지 부재(Page Fault)라고 한다. 페이지 부재가 발생하면 해당 페이지를 스왑 영역에서 읽어서 물리 메모리로 올려야 한다.

페이지 부재가 발생하면 위 그림과 같은 과정을 거쳐 스왑 영역에 있는 페이지를 메모리의 빈 영역에 올리고 페이지 테이블을 갱신한다. 문제는 빈 프레임이 없는 경우이다. 이 경우에, 물리 메모리에 있는 페이지 중 하나를 스왑 영역으로 스왑 아웃해야하는데, 이를 결정하는 알고리즘을 '페이지 교체 알고리즘(Page Replacement Algorithm)'이라고 한다. 이 때 스왑 영역으로 보내지는 페이지를 '대상 페이지(Victim Page)'라고 한다.

 

1.4 지역성

메모리가 가득 차서 특정 페이지를 스왑 아웃해야할 때는, 사용 가능성이 낮은 페이지를 보내는 것이 성능면에서 유리하다. 페이지 교체 알고리즘이 쫓아낼 페이지를 찾을 때는 지역성(Locality)를 바탕으로 한다.

- 공간의 지역성

- 시간의 지역성

 

2. 페이지 교체 알고리즘

2.1 페이지 교체 알고리즘

페이지 교체 알고리즘에서 핵심은 메모리에서 앞으로 사용 가능성이 적은 페이지를 스왑 아웃시키는 것이다.

 

2.2 무작위 페이지 교체 알고리즘(Random Page Replacement Algorithm)

말 그대로 무작위로 스왑 아웃할 페이지를 정한다. 오버헤드는 거의 없지만 전체 시스템에 매우 비효율적이므로 사용하지 않는다.

 

2.3 FIFO 페이지 교체 알고리즘(First In First Out Page Replacement Algorithm)

이 역시 이름 그대로 큐를 이용한 교체 방식이다. 문제는 먼저 들어온 페이지가 항상 덜 사용되는 것은 아니라는 점이다.

 

2.4 최적 페이지 교체 알고리즘(Optimal Page Replacement Algorithm)

최적 페이지 교체 알고리즘은 이론적으로만 가능한 것으로, 앞으로 사용하지 않는 페이지를 스왑 아웃한다. 앞으로 사용하지 않는 페이지를 찾는 것은 거의 불가능하므로, 이 알고리즘은 사실상 구현 불가하다. 뒤에 나오는 알고리즘들은 '최적 근접 알고리즘(Optimal Approximation Algorithm)'에 해당되는데, 이는 과거 데이터를 바탕으로 미래의 접근 패턴을 추정하는 알고리즘들이기 때문이다.

 

2.5 LRU 페이지 교체 알고리즘(Least Recently Used Page Replacement Algorithm)

LRU 페이지 교체 알고리즘은 '최근 최소 사용 페이지 교체 알고리즘'으로도 불리운다. 이 알고리즘은 메모리에 올라온 후 가장 오랫동안 사용하지 않은 페이지를 스왑아웃한다. LRU 페이지 알고리즘은 카운터나 시간 혹은 비트 시프트를 통해 구현하는데, 일반적으로 최적에 가까운 성능을 낸다고 알려져 있다. 다만 접근 시간이나 참조 비트를 유지하기 위한 추가 메모리가 필요하다는 것이 큰 단점이다.

 

2.6 LFU 페이지 교체 알고리즘(Least Frequently Used Page Replacement Algorithm)

LFU 페이지 교체 알고리즘은 '최소 빈도 사용 알고리즘'라고도 불리운다. 이는 페이지가 메모리에 올라온 후 몇 번 사용되었는지를 기준으로 삼는다. 이 역시 최적에 가까운 성능을 내지만, 추가 메모리가 필요하다는 단점이 있다.

 

2.7 NUR 페이지 교체 알고리즘(Not Used Recently Page Replacement Algorithm)

NUR 페이지 교체 알고리즘은 LRU / LFU의 메모리 사용을 줄이고자 고안된 알고리즘이다. NUR 알고리즘은 페이지마다 추가 비트 2개만 사용하는데, 이는 참조 비트와 변경 비트이다.

- 참조 비트: 페이지에 접근하면 1.

- 변경 비트: 페이지를 변경하면 1.

모든 페이지의 초기 상태는 (0, 0)이며, 접근 및 변경에 따라 두 비트의 값이 변화한다. NUR 알고리즘은 (0, 0), (0, 1), (1, 0), (1, 1) 순으로 교체 우선순위를 부여한다. 아래 그림에서 보듯 NUR 알고리즘에서 우선 고려 대상은 참조 비트이다. 만약 같은 비트의 페이지가 여러 개라면 무작위로 대상 페이지를 선정한다.

NUR 알고리즘은 LRU, LFU와 거의 유사한 성능을 내면서도 메모리면에서 효율적이므로 가장 많이 사용되고 있다.

 

2.8 2차 기회 페이지 알고리즘(Second Chance Page Replacement Algorithm)

2차 기회 페이지 알고리즘은 FIFO 방식을 변형한 것으로, 특정 페이지가 사용되면 해당 페이지를 큐의 말미로 보내는 방식이다. LRU, LFU, NUR에 비해 성능은 조금 떨어지는 것으로 알려져 있으며, 큐 운용이 복잡하다는 단점이 있다.

 

2.9 시계 알고리즘(Clock Algorithm)

시계 알고리즘 역시 FIFO의 변형으로, 원형 큐를 사용한다. 그리고 페이지 마다 참조 비트가 부여되어 있는 방식이다. 메모리 측면에서는 유리하지만 원형 큐에서 순회를 많이 하므로 계산량이 많다.

 

3. 스레싱과 프레임 할당

3.1 스레싱

프로세스를 1~3개 정도 실행할 때에는 별 문제가 없으나, 30개 이상 실행하면 물리 메모리가 부족하여 스왑인 및 스왑 아웃 작업이 빈번히 일어난다. 즉, 하드디스크와 메인 메모리 사이의 입출력 작업이 계속되어 프로그램이 마치 정지한 것 같은 현상이 발생할 수 있다. 이러한 상태를 스레싱(Threshing)이라고 한다. 멀티 프로그래밍 정도가 높을수록 스레싱이 발생한다.

스레싱은 각 프로세스에 프레임을 할당하는 문제와도 연결된다. 어떤 프로세스에 너무 적은 프레임이 할당된다면, 스왑인/아웃 작업이 빈번히 일어날 것이다.

 

3.2 정적 할당(Static Allocation)

정적 할당은 말 그대로 프로세스 실행 초기에 프레임을 나누는 방식이다. 대표적으로 비례 할당(Proportional Allocation)이 이에 해당된다. 비례 할당은 말 그대로 프로세스의 크기에 따라 프레임을 나누어 주는 방식이다. 언뜻 보면 합리적이지만 문제가 있다.

- 프로세스가 실행 중에 필요로 하는 프레임은 유동적이다. 프로세스 자체는 작으나 실행 중 많은 메모리를 필요로 할 수 있다. 예컨대 동영상 플레이어 자체는 작은 프로세스지만, 재생되는 동영상의 크기가 크기 때문에 프로세스 자체보다 훨씬 큰 데이터를 메모리에 올려야 한다.

- 프로세스가 크다고 해서 할당받은 모든 프레임을 다 사용하는 것은 아니다. 때문에 미리 할당해 두는 것은 메모리 공간 낭비로 이어진다.

 

3.3 동적 할당(Dynamic Allocation)

동적 할당은 크게 두 가지 방법으로 구현된다. 첫 번째는 메모리에 유지해야 하는 프레임을 결정하는 것이며, 두 번째는 프로세스에 할당하는 프레임의 수를 유동적으로 변화시키는 것이다.

여기서 각 프로세스에 할당하는 프레임의 수는 '부재 빈도(Page Fault Frequency)'를 이용할 수 있다. 이는 각 프로세스마다 페이지 부재 비율을 계산하여, 페이지 부재 비율이 상한선을 초과하면 해당 프로세스에 프레임 할당량을 늘리는 방식이다.

메모리에 유지해야 하는 프레임은 '작업 집합 모델(Working Set Model)'이라는 지역성 이론을 바탕으로 한다. 간단히 말하자면, 최근에 사용한 프레임을 기억해두고 스왑아웃되지 않도록 하는 방식이다.

 

4. 프레임 관련 이슈

4.1 전역 교체와 지역 교체

지역 교체 방식은 앞의 페이지 교체 알고리즘을 사용하되, 하나의 프로세스에 속하는 프레임들을 대상으로만 적용하는 방식이다. 반대로 전역 교체는 모든 프레임들을 대상으로 적용한다. 지역 교체 방식을 사용할 경우, 하나의 프로세스에 할당된 프레임 수가 변하지 않는다. 아무래도 전역 교체 방식이 전체 시스템 측면에서는 유리하다.

 

4.2 페이지 테이블 크기

페이지 테이블은 메인 메모리의 OS 영역 중 일부를 차지하기 때문에, 그 크기를 줄이는 것이 중요하다. 페이지의 크기 자체를 키우면 페이지 테이블 크기는 줄일 수 있는데, 무작정 그 크기를 늘릴 수 없다. 그 이유는 내부 단편화 때문이다. 다만 현대 컴퓨터 시스템은 물리 메모리가 커지고 응용 프로그램도 커짐에 따라 페이지의 크기 또한 커지는 추세이다.

 

4.3 쓰기 시점 복사

하나의 프로세스를 여러 user가 사용하는데, 각 user가 사용하는 프로세스 마다 프레임을 할당한다면 매우 비효율적일 것이다. 이는 메모리 운영 측면에서나, 실행 시간 측면에서 모두 비효율적이다. 예컨대 여러 user가 동시에 크롬 브라우저를 사용한다면, 메모리에 크롬 브라우저 하나만 올려서 같이 사용하면 효율적이다. 다만 모든 프레임이 다 공유가능한 것은 아니다. 코드 부분이 올라가는 프레임은 공유 가능할 것이나, 데이터 부분이 올라가는 프레임은 공유해서는 안될 것이다. 그렇다면 공유 불가능한 프레임에 대한 메모리 확보는 언제 일어날까? 이는 데이터에 변화가 필요한 시점이다. 이와 같이 데이터에 변화가 있을 때까지 복사를 미루는 방식을 '쓰기 시점 복사(Copy on Write)'라고 한다.