Page Frame의 Allocation

process에 얼마 만큼의 page frame을 할당해줄 것인가

• 메모리 참조 명령어 수행 시 여러 페이지를 동시 참조가 필요한 경우 최소한 할당되어야 하는 frame 수가 존재
• 최소한의 allpcation이 아니면 매번 page fault가 발생할 수 있음
  ex) Loop를 구성하는 page들은 한꺼번에 allcation되는 것이 유리
  
  

1) Equal allocaiont

• 모든 프로세스에 같은 개수 할당
• 필요한 개수가 다른데 균등하게 할당하는 것은 비효율적

2) Proportional allocation

• 프로세스 크기에 비례하여 할당
• 같은 프로세스라도 특정 시간에는 많이 필요할 수도 있음
• 반드시 크기에 따라 필요한 frame이 많지 않을 수 있음

3) Prioritional allocaion

• 프로세스의 priority에 따라 다르게 할당
  
  

Replacement

1) Grobal Replacement

• LRU, LFU와 같은 Replacement 알고리즘을 사용하다 보면 프로세스에 할당된 frame을 빼앗을 수도 있음
• 따로 할당량을 정해주지 않아도 조절됨
• Working set, PFF 알고리즘 사용

2)Local Replacement

• 이미 정해진 할당 방식을 따름
• 자신에게 할당된 frame 내에서만 Replacement

---

Thrashing

프로세스의 원활한 수행에 필요한 최소한의 page frame을 할당받지 못한 경우 발생

• 빈번한 page fault 발생
• CPU utilization이 낮아짐
• 메모리에 너무 많은 프로그램(multiprogramming)이 동시에 올라간 상황
  --> page fault가 발생해서 메모리에 더 올림 --> 반복 악화
• multiprogramming을 줄여야 함 ➡️ Working-Set
  
  

Working-Set Model

Locality of reference

• 프로세스는 특정 시간에 일정 장소만 집중적으로 참조하는 경향이 있음
• Locality Set: 집중적으로 참조되는 해당 page들의 집합
  
  

Working-Set

Locality에 기반하여 한꺼번에 메모리에 올라와 있어야 하는 page 집합

• Working Set을 보장해줘야 page fault가 덜 발생
• Working Set을 보장할 수 없다고 하면 모든 frame을 반납한 후 swap out(= suspend)
• Thrashing을 방지
  
  

Working-Set Algorithm

Working-Set을 결정하는 방법

• 어떤 page들이 Working-Set이 되는지 미리 알 수 없음 ---> 과거를 통해 추정
• 특정 시간동안 참조된 page들을 Working-Set으로 묶음
• 특정 시간 = window
• 현재로부터 과거의 window size 만큼의 page들을 Working-Set으로 지정
  = 참조된 page들을 window size 만큼 메모리에 유지한 후 버린다
  
  

Page Fault Frequency (PFF)

• Thrashing을 방지하는 방법
• page fault rate의 상한값과 하한값을 둠

• 상한값을 넘으면 frame을 더 할당
• 하한값 이하면 할당 frame을 줄임
  (빈 frame이 없으면 일부 프로세스를 swap out)

---

참고 링크
반효경 교수님 강의