[OS 기초] Demand paging 3 - Trashing, Working Set

# Trashing 

> Trashing이 발생하는 과정

1. 시스템에 충분히 많은 Process가 동작 중

2. 동작중인 프로세스가 요구하는 메모리가 가용한 물리 메모리보다 많아서 Page Fault 발생

3. page fault를 처리하는 동안 프로세스는 block 당하고 CPU Utilization이 낮아짐

4. CPU Scheduler는 시스템이 한가한 것으로 판단하고 더 많은 프로세스를 실행하려고 함

5. Memory는 점점 부족하게 됨

=> Trashing은 모든 프로세스가 하나의 physical memory pool을 공유(global page replacement)하기 떄문에 발생하게 됨 

=> Local Allocation(per-process, per-job)을 통해 Thrashing을 해결할 수 있는가?

: 해결할 수 없음. 특정 프로세스가 과도하게 메모리를 사용하여 다른 프로세스가 영향을 받는 현상은 막을 수 없음.

하지만, 시스템의 메모리가 부족한 상황인 경우 어떤 프로세스가 충분한 메모리를 확보하고 있더라도 메모리가 부족한 다른 프로세스에 의해 페이지 폴트 처리가 지연됨에 따라라 성능이 급격히 나빠지는 현상이 발생

> Trashing이 발생하는 본질적인 이유?

현재 active하게 사용되는 메모리보다, physical memory가 부족하기 때문에 발생

* 결국 해결법은, 불필요한 프로세스를 suspend(swapping)나 terminate시키기. (degree of multiprogramming을 낮추기)

* Smartphone 처럼 Swap Device가 없는 경우 많은 프로세스로 인해 메모리가 부족하게된다면?

: suspend(swapping)을 할 수 없으므로, Android의 Low Memory Killer등을 사용하여 프로세스를 Terminate.

* Trashing을 체계적으로 극복하는 방법은?!

# Working Set

: 어느 시점에 특정 프로세스가 Access하는 page들의 집합(프로세스의 locality)

- 1960년대, Peter Demming이라는 사람이 생각해낸 아이디어

- 특정 프로세스이 수행되는 전체 life time동안 working set은 변함 (sub-routin call, jump)

=> locality도 변하게 됨

* Prepaging(Prefetching) : 실제 page 요청이 있기 전에 향후 Access 될 것으로 예상되는 페이지를 미리 메모리에 로드하는 것

> Working Set을 이용한 Prepaging

* Longterm Scheduler : degree of multiprogramming을 낮추기 위해 프로세스를 계속 모니터링하여 메모리의 사용이 없는 프로세스를 선정하는 스케줄러

  Shorterm Scheduler : 다음에 돌아야하는 프로세스를 선정하는 스케줄러

- How ?? Working Set Parameter - 현재부터 과거동안 access된 page 들

- working set param들의 갯수가 너무 적으면 충분한 working set을 확보하기 어렵고,

working set의 windows 사이즈가 너무 크면 불필요한 page들도 포함하게 됨

=> 적합한 working set을 찾아내야 하는 필요가 있음

> Working Set의 단위

- 시간? 어떤 프로세스가 항상 동작하는 것이 아니므로 시간으로 단위를 잡기는 어려움

-  Page Reference 패턴? Page Reference 횟수?  어떤 페이지는 여러 프로세스에서 엑세스 되므로 불필요하게 Working Set으로 잡힐 수 있음

=> working set을 잡는건 어려운 일임

# Working Set의 approximation

- 가정 : 현재 수행중인 프로세스에서 Trashing이 일어나지 않고 잘 수행중이면, 현재 할당된 page들은 그 프로세스의 working set일 가능성이 높음

-  OS는 프로세스의 Page fault를 가지고 현재 프로세스의 수행 상태를 알 수 있음

=> key point !!

> Resident Set

: 어떤 프로세스가 어느 시점에 메인메모리에 가지고있는 페이지 들

* Resident Set이 의미를 가지려면!?

- 프로세스가 fork되는 시점에 프로세스에서 일정한 양의 page frame을 allocation 

- system wide하게 upper bound를 설정.  page fault가 upper bound를 넘어서 발생된다면 해당 프로세스에게 좀 더 많은 frame을 할당(high watermark)

- low bound를 설정. page fault가 low bound보다 낮게 발생된다면 working set windows가 불필요하게 많이 할당되었다는 의미. (low watermark)

<Page Fault 발생 횟수에 따른 운영체제의 Memory 할당 정책>

- Threshold 보다 많이 발생하는 경우 : 해당 프로세스에게 더 많은 메모리를 할당

- Threshold 보다 적게 발생하는 경우 : 해당 프로세스에게 할당된 메모리를 회수

# Memory Management의 Trends

<이슈>

1. Physical Memory의 크기가 커짐

- Page Frame이 넉넉해짐

- Page replacement의 중요도가 줄어들고

- 하드웨어적 서포트가 줄고, 소프트웨어적으로 처리하게 됨

- page의 크기가 커지며,  커버하는 instruction의 크기도 늘어나며 hit rate이 높아지게 됨

2. Virtual Memory의 크기가 커짐

- 64bits with 4K page

-  Large Virtual Memory Management의 중요도가 높아짐

3. Memory Management가 OS의 다른 요소들과 결합

- 과거에 없던 색다른 서비스를 제공 : File System과 접목...

4. Large Page Table의 Handling

- 문제 :

1. page table을 유지하기위해 필요한 공간이 너무 큼

2. page table의 물리 메모리에 연속적인 공간에 존재해야 함 

=> 조각의 단위로 쪼개어 관리하는 기술이 필요

<해결방법>

1. Hierarchical page table ; table space를 줄이진 못하지만 , physical memory상에 조각으로 나누어 적재될 수 있도록

<Two-Level Page Table>

- 32bit 환경에서,

Page Number(22bits), offset(10bits)

=> Page Number = First Level Index(14bits) + Second Level Index(8bits)

* First Level Index == Outer Level Index

- Page Table Entry : 1 word size, 4bytes

- Page Table Size : 2^22 X 4 bytes = 16MB

- 한 page에 존재하는 Page Table Entry의 수 : 256 entries (8 bit)

- 한 Page Table에 존재하는 Page들의 수 : 16K (14 bit)

- First Level Page Table의 크기 : 16K x 4bytes = 64KB

- 공간상의 문제에서 장점을 보이나, 속도면에서의 단점이 있음

2. Hashed page table : page table space의 사이즈를 엄청나게 줄일수 있도록

: hashing기법을 사용하여 page table을 구성

page number를 hash table에서 얻어오기.

3. Inverted page table : page table space의 사이즈를 엄청나게 줄일수 있도록

: 모든 user Process는 독립적인 공간을 같기 떄문에 관리를 위해 별도로 큰 page table을 갖음

- address space 만큼 page table을 갖는게아니라 physical memory만큼 page table을 갖자.

* virtual address space사이즈가 아닌, 실제 시스템에 존재하는 page frame의 갯수만큼 page table을 갖는다.