Demand Paging - (3) Thrashing and Working set

Demand Paging - (3) Thrashing and  Working set

Thrashing은 resource를 최대한 사용하고 있으나 아무런 유용한 일을 하지 못하는 현상을 일컬음.

예를 들어, CPU Scheduler는 cpu utilization을 최대한 높이는 것이 목적이다. 그러므로 cpu utilization이 낮으면 degree of programming을 늘려 cpu utilization을 활용하고자 한다. 그와 동시에 Memory management는 process이 수가 많아지면 page fault의 수가 증가하여 process들이 waiting 큐에서 대기하게 된다. 이에 따라 cpu utilization이 낮아지는 악순환이 반복된다.

Thrashing이 발생하는 과정
1. 시스템에 충분히 많은 process가 동작 중
2. 동작 중인 process가 요구하는 memory가 가용한 physical memory보다 많아서 page fault 발생
3. page fault를 처리하는 동안 process는 블록당하게 되므로 CPU utilization이 낮아진다.
4. CPU Scheduler는 시스템이 한가한 것으로 판단하고 더 많은 process들을 동작시킨다.
5. memory가 더욱 부족해짐으로써 악순환이 반복된다.

Q. Page replacement style를 global이 아닌 local allocation을 채택함으로써 thrashing을 해결할 수 있을까?
- 해결할 수 없다. 특정 process가 과도하게 memory를 사용하여 다른 process가 영향을 받는 현상은 막을 수 있다. 하지만, 시스템의 memory가 부족한 상황인 경우 어떤 process가 충분한 memory를 확보하고 있더라도 memory가 부족한 다른 process에 의해 page fault 처리가 지연되게 됨으로써 성능이 급격히 나빠지는 현상이 발생한다.

thrashing이 발생하는 본질적인 이유는 물리 메모리의 크기가 process들이 요구하는 크기에 비해 작기 때문.(virtual address space를 활용한 메모리 사이즈 극복에 따른 문제)

Q. 컴퓨터 시스템이 하드 디스크가 아닌 ssd를 사용하여 swap device가 없는 경우 많은 process로 인해 memory가 부족하면 어떻게 처리하는가?
- 안드로이드의 low memory killer와 같이 동작 중인 프로세스를 강제로 종료시켜 해당 프로세스를 완전히 memory에서 제거하는 수 밖에 없다.

따라서, thrashing을 줄이려면 page fault의 발생빈도를 줄여야 한다. 이를 해결하기 위해 고안된 것이 working set이다.
* working set
- 어느 시점에 특정 프로세스가 access하는 page들의 집합
- working set을 알고 있으면 운영체제는 필요한 page를 pre-paging함으로써 page fault 빈도를 낮출 수 있다.
- working set은 과거 임의의 시간(t)동안 access한 page의 집합을 말한다.

그러나, 이러한 방법은 컴퓨터 시스템에서 구현하기 힘들기 때문에 working set 개념을 approximation한 것이 Residence set이다.
Residence set은 현재 상황에서 가지고 있는 page정보에서 page fault가 발생하지 않는다면 이 페이지 집합을 Residence set이라 한다.(= 적합한 페이지 집합 구성이라고 판단한 것)

Page fault 발생 횟수에 따른 운영체제의 메모리 할당 정책
1) Threshold 보다 많이 발생하는 경우
- 해당 프로세스에게 더 많은 메모리를 할당
2) Threshold 보다 적게 발생하는 경우
_ 해당 프로세스에게 할당된 메모리를 회수