Memory Allocation and Trashing

Demand Paging Issue

Demand paging을 할 때 memory allocation의 문제를 생각해야 한다.

Demand paging으로 인해 trashing 문제가 발생할 수 있다.

 

---

Memory Allocation

Demand paging은 프로세스가 필요로 하는 page만 그때그때 제공하는 것이다.

 

Demand paging을 구현할 때 프로세스가 최소로 필요로 하는 page의 수를 고려해야 한다.

최대로 필요한 page의 수는 제약은 없고, physical memory의 크기에 따라 결정하면 된다.

 

예를 들어 IBM 370에서 SS MOVE 라는 instructoin은 memory에서 memory로 data를 옮기는 instruction이다.

이 instruction를 처리하기 위해서는 최소 6개의 page가 필요하다.

• instruction : 2byte
  • 이 instruction은 6bytes인데, memory가 align 되어있지 않다면 2개의 page에 걸칠 수가 있다.
  • 따라서 최소 2개의 page가 필요 할 수 있다.
• 주소 표현 : 4개
  • 메모리에서 메모리로 데이터를 옮기기 때문에 2개의 메모리 주소가 필요하다.
  • 따라서 source address와 destination address의 표현에 각각 2개의 page가 필요하다.

 

Allocation Scheme

메모리를 배정하는 방법은 2가지가 있다.

• fixed allocation vs. priority allocation
  • 프로세스에게 배정할 frame의 개수를 정하고 그를 넘어서지 못하게 한다.
  • fixed allocation
    
    • equal allocation : 모든 프로세스의 최대치를 균등하게 결정한다.
    • proportional allocation : 프로세스의 크기에 비례해서 최대치를 결정한다.
  • priority allocation
    • 프로세스의 크기는 작지만 빠르게 수행되어야 하는 경우가 존재할 때 사용한다.
    • proportional allocation scheme와 유사하다.
    • 프로세스의 크기 대신 priority를 이용해서 최대치를 결정한다.
• global allocation vs. local allocation
  • global replacement
    • victim을 전체 프로세스의 page들 중에서 선택한다.
    • 다른 프로세스의 page를 victim으로 선택할 수 있다.
  • local replacement
    • victim을 해당 프로세스의 page들 중에서 선택한다.
    • 다른 프로세스의 page를 victim으로 선택할 수 없다.

 

---

Trashing

Demand paging의 부작용이다.

 

프로세스가 swap out/in을 하는데 바쁜 상황을 말한다.

정상적인 instruction의 실행보다는, page fault handling과 page replacement algorithm의 실행만 대부분의 작업을 차지하게 된다.

 

system이 가지고 있는 physical memory보다 현재 프로세스의 개수가 너무 많을 때 발생한다.

즉, 프로세스가 page의 수가 충분하지 않기 때문에 page fault rate가 높게 나타난다.

 

해결

Trashing을 detect하고 처리하는 2가지 방법이 있다.

• working-set model
• page fault frequency scheme

 

---

Working Set Model

• Working set window
  • page 참조가 몇번 발생하는지를 의미한다.
  • fixed number of page reference
  • $\Delta$로 표현한다.
• Working set
  • $\Delta$ 구간 동안 참조된 page number들의 집합
• Working set size
  • working set에서 요소들의 개수
• D (demand)
  • $\Sigma WSS_i$ 
  • 프로세스가 필요로 하는 전체 frame들의 집합
• S (supply)
  • 이용 가능한 frame의 수
  • D > S 이면 trashing이 발생한다.
• Policy
  • D > S 이면 프로세스를 중단시켜서 D가 S보다 작아지도록 한다.

 

Keeping Track

Working set을 이용하면 trashing을 detect하고 해결하는 것이 수월해진다.

단, working set을 파악하고 유지해야 한다.

 

이를 위해서 아래가 필요하다.

• interval timer
• reference bit
• memory에서 2개의 bit

 

방법

1. 어떤 page가 참조되면 reference bit을 1로 set 한다.
2. timer interrupt가 발생하면 reference bit을 in-memory로 copy하고 0으로 초기화한다.
3. 만약 in memory의 2 bit 중 하나라도 1이면, 그 page는 working set 안에 있다고 취급한다.

 

한계

정확하지는 않다.

timer interrupt가 발생하기 전에 access를 하더라도 in-memory에는 반영되지 않는다.

따라서 정확도를 위해서는 in-memory bit을 늘리거나 timer interrupt의 interval을 줄여야 한다.

 

---

Page Fault Frequency Scheme

프로세스마다 적절한 page fault 상한과 하한을 결정한다.

 

• 상한보다 위에 있는 경우
  • page fault rate이 상한보다 위에 있다면 physical frame이 부족한 경우이다.
  • 따라서 추가 할당을 한다.
  • 만약 free frame이 없다면 일부 프로세스를 중단시킨다.
• 하한보다 아래 있는 경우
  • physical frame이 너무 많은 경우이므로 회수한다.