Frame Allocation

page를 메모리에 할당하는 프레임 할당에 대해 알아본다.

1. Global VS Local Replacement

• Global Replacement
  • 메모리 상의 모든 프로세스 페이지에 대한 교체 작업을 수행한다.
  • 앞에서 배운 FIFO, OPT, LRU 등은 Victim을 정할 때, 모든 메모리에 올려져 있는 frame을 다 확인 후에 교체를 수행했다.
• Local Replacement
  • 메모리 상의 자기 자신의 프로세스 페이지에 대해서만 교체 작업을 수행한다.
  • 지금 요청이 들어온 page가 p1이라면, 메모리상에 올라가 있는 frame 중 p1 frame만 교체의 대상으로 간주한다.

메모리 사용 효율은 일반적으로 Global Replacement가 좋다.

2. 프레임 할당(Allocation of Frames)

어떻게 할당하는 것이 좋은지에 대한 고민을 해본다.

2.1. 쓰레싱(Thrashing)

일반적으로 메모리에 올라가는 프로세스 개수가 증가할수록 CPU의 이용률은 올라갈 것이라 예상한다. 왜냐하면 프로세스가 많을 수록 CPU의 할 일 역시 증가하기때문이다. 이는 일정 범위까지는 맞는 예상이지만, 그 범위를 넘어서면 오히려 CPU 이용률이 감소하는 현상이 나타난다.

위 그림은 이러한 현상을 그래프로 나타낸 것이다. 이와 같은 현상이 발생하는 이유는 프로세스가 증가할수록 메인 메모리의 비어있는 프레임 개수는 줄어들게 되고 결국 모든 프레임이 가득 차게 된다. 그 후에도 계속 프로세스가 증가한다면 메모리와 backing store 사이에 page in/out 작업이 발생하는데, 프로세스가 많아질수록 이 작업 역시 증가한다. page in/out은 디스크 I/O 작업으로 CPU를 사용하지 않는 작업이다. 그러므로 이 작업이 많아질수록 CPU는 그동안 아무것도 하지 않게 된다.

위 그래프에서도 나와있듯이, I/O 작업이 증가하여 CPU 이용률이 떨어지는 현상을 Thrashing 이라 한다.

2.1.1 해결 방법

쓰레싱을 해결하는 방법은 크게 두 가지가 있다.

1. Global Replacement보다 Local Replacement를 사용하는 것이다.
   • 하지만 이 경우에는 메모리 사용 효율이 떨어지는 단점이 있다.
2. 프로세스당 충분한/적절한 수의 프레임(메모리)을 할당한다.

그렇다면, 적절한 프레임의 수는 어떻게 정하는 것일까?

2.2 프레임 할당의 방법

프레임 할당은 크게 정적 할당과 동적 할당으로 나뉜다.

2.2.1 정적 할당(Static Allocation)

• 동일 할당(Equal Allocation)
  • 모든 프로세스에게 똑같은 수의 프레임을 할당한다. 이 방식은 프로세스의 크기에 따라 매우 비효율적이다.
• 비례 할당(Proportional Allocation)
  • 프로세스의 크기에 따라 프레임을 할당한다. 이 방식 역시 단점이 있다. 프로세스 크기가 크더라도 모든 기능을 사용하지 않기 때문에 이 방식 또한 비효율적이다.

이처럼 정적 할당은 한계가 뚜렷하다. 따라서 동적 할당의 방법을 사용하는 것이 좋다.

2.2.2 동적 할당(Dynamic Allocation)

2.2.2.1 Working Set Model

프로세스가 실행 중일 때 어느 페이지를 사용하는지 실험한 결과에서 Locality 성질이 성립한다는 것을 발견할 수 있었다. 즉, 특정 시간 대에 참고하는 부분은 일부분이다.

위 그래프는 프로세스가 실행 중에 어떤 프로세스를 사용하는지 표시한 것으로, 특정 시간에는 일정 범위의 페이지를 주로 참조하는 것을 알 수 있다. 이러한 성질은 캐시에서도 볼 수 있다. 이를 통해 특정 시간에 따라 사용하는 페이지의 개수만큼 프레임을 할당해줄 수 있다.

그런데 어떻게 locality를 조사할 수 있을까? 여기서 치명적인 단점이 있다. 바로 프로세스를 미리 수행해봐야 할 수 있다는 것이다. 그리고 프로세스를 수행할 때마다 사용하는 기능이 달라질 수 있으므로, Locality를 이용하는 방법은 비현실적이다.

이를 해결하기 위해 나온 것이 working set 이다. working set은 위의 locality의 방식과 유사한데, 미래가 아닌 과거를 보는 것이다.

위 그림은 working set을 사용하는 모습이다. working set은 현재 시간에서 일정 시간($\Delta$) 이전동안 사용되었던 페이지의 집합이다. $\Delta$(델타)는 운영체제 내부에서 정하는 기준에 따라 다르며, 이를 working set window 라 한다. 마지막으로 working set의 개수만큼 프레임을 할당한다.

만약 현재 시간이 t1이라면 working set = {1, 2, 5, 6, 7}이다. 이 때 working set의 개수는 총 5개이므로 프레임 역시 5개를 할당해주면 된다.

2.2.2.2 Page-Fault Frequency(PFF)

페이지 부재의 비율은 프로세스에 할당된 프레임의 수에 반비례한다. 즉, 할당된 프레임의 수가 적을수록 페이지 부재 비율은 늘어난다.

위 그림은 이와 같은 현상을 그래프로 나타낸 것이다. 세로축은 페이지 부재 비율이고, 가로축은 할당된 프레임의 수이다. 여기서 운영체제 내부에서 해당 프로세스의 페이지 부재 횟수를 계속 검사한다. 그러면 위와 같은 그래프처럼 나오는데, 여기서 **상한선(upper bound)과 하한선(lower bound)**를 설정한다.

만약 상한선보다 많은 페이지 부재가 발생하면 프레임을 더 많이 할당해주고, 하한선보다 적게 페이지 부재가 발생하면 할당된 프레임 개수를 줄여준다.

3. 페이지 크기(Page Size)

현재 페이지의 일반적인 크기는 4KB ~ 4MB 이다. 이는 과거에서부터 점점 커져왔고, 현재에도 메모리 크기가 증가하면서 커지고 있다.

페이지 크기에 따라 성능에는 어떤 영향을 미치는지 알아보자.

3.1 페이지 크기에 따른 성능

• 내부단편화
  • 내부단편화를 줄이려면 페이지 크기는 작은 것이 좋다.
• Page-in, page-out 시간
  • 페이지의 in/out 시간을 결정하는 가장 큰 요인은 하드디스크 기준으로 하드디스크의 헤더가 움직이는 시간이다.(seek time) 페이지 크기가 크면 클수록 한 번의 seek time마다 큰 페이지를 읽을 수 있으므로, 페이지 부재 빈도가 줄어든다.(데이터를 읽는 시간은 크기에 따라 차이가 매우 적다.)
• 페이지 테이블 크기
  • 페이지 크기가 클수록 페이지 개수가 줄어들기 때문에 그만큼 페이지 테이블 크기도 줄일 수 있다.
• Memory resolution(해상도)
  • Memory resolution은 해당 메모리에 필요한 데이터가 있는 확률이다. 이는 페이지 크기가 작을수록 resolution을 높일 수 있다. 만약 페이지 크기가 크면 다른 필요없는 부분이 있을 확률이 크기 때문이다.
• Page fault 발생 확률
  • Page fault 발생 확률을 줄이려면 페이지 크기가 큰 것이 좋다. 이는 locality 성질과도 관련이 있는데, 대부분 프로세스는 필요한 부분이 일정 범위 이내인 경우가 많으므로 페이지 크기가 클수록 필요한 부분이 있을 확률이 크다.

big	small
Page fault 발생 확률 ▼	내부 단편화 ▼
페이지 테이블 크기 ▼	Page-in, page-out 시간 ▼
	Memory resolution(해상도) ▲

3.2 페이지 테이블

반도체 기술의 발달로 TLB 역시 CPU의 내장 칩 형태로 만들어져있다.

Reference

• KOCW 양희재 교수님 - 운영체제
• 양희재 교수님 블로그(시험 기출 문제)
• codemcd 님의 정리글
• Operating System Concepts, 9th Edition - Abraham Silberschatz