프레임 할당 (Allocation of Frames)

1. 쓰레싱(Thrashing)

1) CPU utilization vs Degree of multiprogramming

  CPU 이용률 vs 메인메모리에 올라와있는 프로세스의 개수

일반적으로 프로세스의 개수가 증가하면  CPU 이용률이 증가한다. CPU가 노는 시간이 줄어들기 때문이다.

그러나 프로세스가 일정 범위를 넘어서면 CPU 이용률이 감소하게 된다.

이러한 현상을 Thrashing이라 한다.

Thrashing 구간

 

2) 쓰레싱 극복

  Thrashing이 일어나는 이유는 빈번한 page in/out 때문이다. 프로세스가 늘어나면서 i/o 시간이 증가하기 때문에 CPU 이용률이 급격히 감소하는 Thrashing 이 발생하게 된다.

 

쓰레싱을 극복하기 위한 방법은 여러가지가 있다.

1) Global replacement 대신 local replacement를 사용한다.

2) 프로세스당 충분한/적절한 수의 메모리(프레임)을 할당한다.

=> 프로세스 당 얼마 만큼의 프레임을 할당하는게 좋을까.

　

2. 정적 프레임 할당과 동적 프레임 할당

  프레임 할당 문제에 있어서 정적 프레임 할당과 동적 프레임 할당이 있다.

 

1) 정적 프레임 할당

  a. Eqaul (동일 할당) : 각 프로세스에 동일한 프레임을 할당한다.

  b. Propotional (비례 할당) : 프로그램 크기에 따라 비례하여 프레임을 할당한다.

2) 동적 프레임 할당

  a. working set model

  b. page-fault Frequency(PFF)

 

그러나 정적 프레임 할당은 현실과 맞지 않는 방법이다. 왜냐하면 프로그램 내 안쓰는 기능도 많기 때문이다. (ex. 워드프로세서의 정렬기능, 도표그리기 기능 등)

　

3. 동적 프레임 할당

1) Working set model

  - Locality vs working set

Locality란 특정 시간에서 CPU가 내는 주소는 몰려있다는 개념이다.

그래서 Locality를 포함하는 프레임 수를 프로세스에 할당하는 것이 가장 이상적인 방법이다.

그러나 미래의 Locality는 실제로 프로세스를 돌려봐야 알 수 있기 때문에 현실적으로 불가능하다.

 

이에 대한 대안으로 나온 것이 working set 모델이다.

working set 모델은 프레임을 할당하려는 미래 시점에서 델타만큼의 과거동안 몇개의 프레임이 쓰였는지 확인하고 이를 할당하는 방법을 말한다. 과거 시간의 간격이 바로 working set window다.

Locality  vs  working set

2) Page-Fault Frequency(PFF)

 PFF는 Page fault 발생 비율의 상한/하한선을 파악해 page fault의 상한선을 초과하는 프로세스에는 더 많은 프레임을 할당하고, 하한선 이하의 page fault를 내는 프로세스에는 프레임을 회수하는 방식이다. 

 

O/S에서 page fault가 현재 몇번 일어나고 있는지 계속 계산한뒤 프레임 할당수를 조절한다.