프레임 할당 (Allocation of Frames)

* 들어가기 전에

• 컴퓨터 시스템의 성능 향상을 위해서는 동시에 동작하는 여러 개의 프로세스에 제한된 가용 메모리를 효과적으로 할당할 수 있는 방법을 고려해야 한다.
  • 각 프로세스에게 할당되는 메모리 프레임 수를 정해야 한다.
• 최소로 할당해야 할 프레임 수
  • 프로세스에 할당되는 프레임 수가 줄어들면 Page fault 발생 확률이 늘어나 성능이 떨어진다.
  • 명령어 실행이 끝나기 전에 Page fault가 발생하면 그 명령어를 재실행해야 한다.
  • 프로세서의 명령어 집합 구조 (instruction set architecture)에 의해 결정된다.
    • 즉, 아키텍처에 의해 정의된다.
• 최대로 할당해야 할 프레임
  • 물리 메모리에 의해 결정된다.

 

1. 할당 알고리즘 (Allocation Algorithm)

(1) 균등 할당 (Equal allocation)

• n개의 프로세스에 m개의 프레임씩 분할한다.

(2) 비례 할당 (Proportional allocation)

• 프로세스의 크기 비율에 맞추어 프레임을 할당한다.

(3) 우선순위 할당 (Priority allocation)

• 비례 할당 방법을 사용하면서 프레임 비율을 프로세스의 크기가 아닌 우선순위를 사용하여 할당한다.

 

2. 전역 대 지역 할당 (Global vs Local Allocation)

(1) 전역 교체 (Global Allocation)

• 프로세스가 교체할 프레임 (victim frame)을 다른 프로세스에 속한 프레임을 포함한 모든 프레임을 대상으로 찾는다.

(2) 지역 교체 (Local Allocation)

• 각 프로세스가 자기에게 할당된 프레임 중에서만 교체될 희생자를 선택할 수 있다.

 

3. 비균등 메모리 접근 (Non-uniform Memory Access)

• 여러 개의 CPU를 가진 비균등 메모리 접근(NUMA) 시스템
  • CPU 마다 local memory를 가지고 있다. 
  • 특정 CPU는 메인 메모리의 일정 영역을 다른 영역보다 빠르게 접근할 수 있다.
• process 할당 시 OS가 CPU에 가까운 meemory에 free frame을 할당한다.

 

4. 스래싱 (Trashing)

과도한 페이지 교체 작업

• 프로레스가 실제 실행보다 더 많은 시간을 페이지 교체에 사용하고 있으면 스래싱이 발생했다고 한다.

(1) 스래싱의 원인 

• 운영체제는 CPU 이용률이 너무 낮아지면 새로운 프로세스를 시스템에 더 추가해서 다중 프로그래밍의 정도를 높인다.
• 페이지 폴트가 자주 발생하면 프로세스들은 페이지를 기다리는 동안 CPU 이용률은 떨어진다.
• CPU 스케줄러는 이용률이 떨어지는 것을 보고, 이용률을 높이기 위해 새로운 프로세스를 추가한다.
• 결과적으로 CPU 이용률은 더욱 떨어지고 페이지 폴트는 상당히 늘어난다.

• 다중 프로그래밍의 정도가 그 이상으로 더 커지면 스래싱 발생

* 지역성(Locality)
 : 프로세스가 실행될 때에는 항상 어떤 특정한 지역에서만 메모리를 집중적으로 참조한다.

(2) 작업 집합 모델 (Working-Set Model)

• 작업 집합 창 (working-set window)을 가지고 있다.
  • 최근 창만큼의 페이지 참조를 관찰한다.
• 작업 집합의 정확도는 창의 크기에 좌우된다.
  • 너무 작은 창 : 전체 지역을 포함하지 못한다.
  • 너무 큰 창 : 여러 지역성을 과도하게 수용할 것이다.

• 각 프로세스가 요구하는 작업 집합 크기 : WSSi
• 전체 프로세스에게 요구되는 작업 집합 크기 : D = WSS1 + WSS2 + WSS3 .....
• 총 보유 메모리 m
• 만약 D > m 이 되면 trashing 발생한다.
  • 프로세스 하나를 선택해서 그 프로세스의 페이지들을 빼앗고, 연기시키고 그 프레임들을 다른 프로세스에게 주는 기법으로 해결 가능

(3) 페이지 폴트 빈도 (Page-Fault Frequency, PFF) 방법

페이지 폴트 빈도를 이용해서 프레임 할당 개수를 정한다.

• 페이지 폴트율의 상한과 하한을 정한다.
  • 페이지 폴트율이 상한을 넘으면 그 프로세스에 프레임을 더 할당해 준다.
  • 하한보다 낮아지면 그 프로세스의 프레임 수를 줄인다.

 

5. 커널 메모리의 할당 (Allocating Kernel Memory)

• 사용자 모드에서 수행 중인 프로세스가 추가적인 메모리를 요구하면 커널이 관리하는 페이지 프레임 중에서 할당
  • 이런 경우는 거의 발생하지 않는다.
• 커널 메모리는 보통 사용자 모드 프로세스와 달리 별도의 메모리 풀에서 할당하는 정책을 사용한다.
  • 커널 코드나 데이터는 페이징 하지 않는다.
  • 커널 메모리는 물리적으로 연속적으로 할당이 필요하다.