프레임 할당

Global Replacement vs Local Replacement

교체를 어떤 방식으로 하느냐의 차이가 있다.

Global Replacement

메모리 상의 모든 프로세스 페이지에 대해 교체를 진행한다.

Local Replacement

메모리 상의 자기 프로세스 페이지에 대해 교체를 진행한다.

성능 비교

Global Replacement가 메모리 사용 효율성에 대해서 더 효율적일 수 있다.

프레임 할당 (Allocation of Frames)

쓰레싱 (Thrashing)

일반적으로 프로세스가 증가하면 그 만큼 메모리의 빈 공간이 줄어든다. 끝내 가득차게 되면 Page In, Page Out이 빈번하게 발생하기 시작한다. 프로세스가 더더욱 많아지면 Page In과 Page Out이 그만큼 더더욱 빈번하게 발생하게 된다.

문제는 Page It, Page Out 작업이 진행되는 동안에는 CPU가 아무런 일을 하지 못한다. 페이지가 메모리 상에 올라와야 CPU가 일을 하는데 디스크 I/O 작업만 계속 반복되기 때문이다.

이처럼 디스크 I/O 작업이 증가하여 CPU의 이용률이 떨어지는 현상을 쓰레싱 (Thrashing)이라고 한다.

극복

쓰레싱은 Global Replacement 보다는 Local Replacement로 극복할 수 있다.

프로세스 당 충분한 또는 적절한 수의 메모리 (프레임)을 할당하는 식으로 극복할 수 있다.

그렇다면 이 충분한 또는 적절한 수의 메모리 (프레임) 은 어떤 기준으로 정할 수 있을까?

정적 할당 (Static Allocation)

균등 할당 (Equal Allocation)

모든 프로세스에게 똑같은 수의 프레임을 할당한다. 하지만 프로세스의 크기에 따라 비효율적일 수 있다.

비례 할당 (Proportional Allocation)

프로세스의 크기에 따라 프레임을 할당한다. 프로세스가 크더라도 그 안의 모든 내용을 사용하는 것이 아니기 때문에 비효율적이다.

이처럼 정적할당은 한계가 뚜렷한 비효율적인 방법이다.

동적 할당 (Dynamic Allocation)

Working Set Model

지역성 (Locality)

프로세스가 실행 중일 때, 특정 시간에는 특정 범위의 페이지를 주로 참조하는 현상이 발생한다. 이를 지역성 (Locality)이라고 한다.

지역성을 파악하면 특정 시간에 필요한 페이지의 개수만큼 프레임을 할당할 수 있다. 하지만 미래에 어느 부분에서 지역성이 발견될지는 아무도 알 수 없다. 따라서 이를 파악하기 위해 미리 전체적으로 돌려봐서, 어느 시점에 어느 정도의 프레임이 필요한지를 파악해야한다.

이는 매우 비효율적인 방법이다.

Working Set

Locality의 한계를 보완하기 위해 등장한 개념이다. Locality는 미래를 예측한다면 Working Set은 과거에 기반한다.

현재 시간에서부터 일정 시간 이전동안 사용되었던 페이지의 집합을 구한다. 이를 Working Set Window이라고 한다. 마치 하나의 창문을 옆으로 이동시키는 듯한 움직임을 보여서 Window라는 이름이 붙었다. 알고리즘 중 Sliding Window와 비슷한 개념이다.

Working Set은 이 Working Set Window 안의 페이지 개수만큼 프레임을 할당하는 방식이다.

Page-Fault Frequency (PFF)

Page Fault 발생 비율의 상한선 (Upper Bound) 또는 하한선(Lower Bound)을 구한다.

• Page Fault가 상한선보다 더 많이 발생하면 더 많은 프레임을 할당한다.
• Page Fault가 하한선보다 더 적게 발생하면 프레임 개수를 줄인다.

페이지 크기 (Page Size)

현대에서 페이지의 크기는 일반적으로 4kb ~ 4mb 정도를 갖고 있다. 시간이 지날 수록 페이지의 크기는 더 커져가는 경향을 보인다.

페이지 크기의 영향

페이지의 크기에 따라 성능에 다양한 영향을 미친다.

내부 단편화

페이지 크기가 작을수록 내부 단편화가 적게 발생한다.

Page In, Page Out 시간

페이지 크기가 크면 한번의 Seek Time 때 많은 양의 페이지를 읽을 수 있기 때문에 페이지 크기가 클 수록 Page Fault의 빈도수가 줄어즌다. (Seek Time : HDD가 Backing Store를 탐색하는 시간)

페이지 테이블 크기

페이지 크기가 클수록 페이지 테이블의 엔트리 개수가 줄어들기 때문에 페이지 테이블 크기가 줄어든다.

Memory Resolution

Memory Resolution이란 메모리에 필요한 데이터가 있을 확률이다.

페이지 크기가 작을 수록 Memory Resolution은 증가한다. 왜냐하면 페이지 크기가 크면 필요없는 데이터까지 같이 포함되어있을 확률이 높아지기 때문이다.

Page Fault 발생 확률

Page Fault 발생 확률은 페이지 크기가 클수록 줄어든다. 대부분 프로세스는 Locality의 특징 때문에 필요한 부분이 일정 범위 이내일 경우가 많다. 따라서 페이지의 크기가 클수록 필요한 부분이 범위 내에 있을 확률이 더 높아진다.