가상 메모리(Virtual Memory) - 프레임 할당(Allocation of Frames)

아래의 글에서 요구 페이징에 대한 전반적인 설명을 다루고 있습니다.

https://create-new-worlds.tistory.com/128

가상 메모리(Virtual Memory) - 요구 페이징(Demand Paging)

 

 

* 프레임 할당

 

여러 개의 프로세스들에 제한된 가용 메모리를 어떻게 할당할 것인지 결정해야한다. 여러 가지 전략이 있을 수 있다.

 

예를 들어 운영체제가 모든 버퍼나 테이블 공간을 가용 프레임 리스트에서 할당받게 함으로써 운영체제에 의해 사용되지 않을 때 사용자 페이징을 위해 사용될 수 있다. 또한 언제나 가용 프레임 리스트에 3개의 프레임을 예비로 남겨두어 페이지 부재 발생 시에 가용 프레임이 존재하게 되어 페이지 스왑를 기다리지 않을 수 있다.

 

위와 같은 전략 외에도 다양한 전략이 존재하지만 기본적인 목적은 사용자 프로세스가 어떤 가용 프레임이든 할당받도록 하는 것이다.

 

 

- 최소 할당 프레임 수

 

메모리 할당에는 다음과 같은 제한이 존재한다.

1. (페이지 공유를 하지 않으면) 가용 프레임 수보다 더 많이 할당할 수 없다.
2. 최소한 몇 페이지는 할당해야만 한다.

여기서 두번째 조건의 이유는 각 프로세스에 할당되는 프레임 수가 줄어들면 페이지 부재율이 증가되기 때문이다. 페이지 부재는 프로세스 실행을 늦어지게 만들고, 명령어 수행 중 발생한다면 그 명령어를 재실행되어야 한다.(명령어에서 사용되는 모든 페이지가 올라와 있어야 한다.) 이와 같이 페이지 부재은 성능 저하로 이어진다.

 

최소 프레임 수는 컴퓨터 아키텍처에 의해 정의된다. 예를 들어 아키텍처에서의 이동 명령이 일부 주소지정 모드에서 하나 이상의 워드를 포함하는 경우 명령 자체는 두 프레임에 걸쳐있을 수 있고, 여기서 두 피연산자가 간접 참조일 수 있는 경우(간접 참조는 3개의 프레임이 필요) 6개의 프레임이 필요하다.

 

최대 프레임 수는 물리 메모리의 크기에 따라 결정된다.

 

 

- 프레임 할당 알고리즘

 

@ 균등 할당(equal allocation)

프로세스 모두에 같은 프레임을 할당하는 방식이다.

n개의 프로세스에 m개의 프레임을 분할한다고 하였을 때 (m/n 개)을 할당한다. 

 

 

@ 비례 할당(proportional allocation)

가용 메모리를 프로세스의 크기의 비율에 맞추어 할당하는 방식이다.

 

구하는 공식은 다음과 같다.

각 프로세스 pi의 크기를 si라고 했을 때 모든 프로세스의 크기의 합을 S라고 한다. (S = Σsi)
가용 프레임 개수를 m 각 프로세스 pi에 할당할 ai는 다음과 같이 정의된다.

ai = si / S * m

총합은 m을 넘지 않도록 해야하기 때문에 ai는 위의 식보다 조금 더 작게 나온다.

 

 

위의 두 방식은 다중 프로그래밍 정도가 높다면 더 적게 할당받고 다중 프로그래밍 정도가 낮다면 더 할당받게 된다. 

두 방식 외에도 우선순위에 따라 프레임을 할당할 수도 있다.

 

 

- 전역 할당과 지역 할당(global allocation and local allocation)

 

여러 프로세스가 프레임 할당을 위해 경쟁하는 환경에서 페이지 교체 알고리즘은 두 범주에서 수행된다.

전역 교체(global replacement)	지역 교체(local replacement)
@ 다른 프로세스에 속한 프레임을 포함한 모든 프레임에서 교체할 프레임을 찾는 방식이다.	@ 본인에게 할당된 프레임 중에서만 교체할 프레임을 찾는 방식이다.
@ 프로세스에 할당된 프레임 수는 바뀔 수 있다. @ 프로세스 우선순위에 따라 프레임을 할당 받을 수 있는 환경에서는 우선순위가 높은 프로세스는 우선순위가 낮은 프로세스를 희생시켜서 더 많은 프레임을 할당받을 수 있게 해준다. @ 프로세스의 페이지 집합은 여러 프로세스의 페이징과 연관된다. @ 동일한 프로세스도 외부적 환경에 따라 전혀 다르게 실행될 수 있다. @ 일반적으로 지역 교체보다 성능이 좋다.	@ 프로세스에 할당된 프레임 수는 변하지 않는다. @ 프로세스의 페이지 집합은 유일하게 해당 프로세스의 페이징과 연관된다. @ 동일한 프로세스라면 일관적으로 실행된다. @ 잘 안쓰는 페이지 프레임이 있더라도 낭비할 수 있다. @ 일반적으로 전역 교체보다 성능이 좋지 않다.

 

전역 교체의 페이지 교체 정책을 구현하는 데 사용할 수 있는 전략 중 하나로 가용 프레임 리스트의 크기를 최소 임계값 이상으로 유지하기 위해 최소 임계값 아래로 떨어지면 페이지 교체를 해주는 전략이 있다. 최소 임계값 아래로 떨어지면 시스템의 모든 프로세스에서 페이지를 회수하기 시작하는 커널 루틴이 촉발된다. 이러한 커널 루틴을 커널 리퍼(reaper) 루틴이라고 한다.

 

 

 

 

- 비균등 메모리 접근(non-uniform memory access)

 

여러 개의 CPU를 가진 비균등 메모리(NUMA) 시스템에서는 특정 CPU는 메인 메모리의 일정 영역을 다른 영역보다 빠르게 접근할 수 있다. CPU는 공유 시세틈 상호 연결을 사용하여 구성되며 자신의 로컬 메모리에 더 빠르게 접근할 수 있다.

 

이러한 시스템에서는 어느 페이지를 어느 프레임에 할당하는 지에 따라서 성능차이가 나기 때문에 CPU에 가능한 가장 가까운(최소 지연시간을 가진) 메모리 프레임이 할당되도록 한다.