운영체제의 기초 - 19. Demand Paging 3

Thrashing and Working Set

Thrashing: 하기는 굉장히 열심히 일하는데 유용한 일을 못 만드는 것

Q. Local Allocation을 통해 Thrashing을 해결할 수 있는가?

A. 해결할 수 없다. 특정 Process가 과도하게 Memory를 사용하여 다른 Process가 영향을 받는 현상은 막을 수 있다.

    하지만 시스템의 Memory가 부족한 상황인 경우 어떤 Process가 충분한 Memory를 확보하고 있더라도 Memory가

    부족한 다른 Process에 의해 Page Fault 처리가 지연되게 됨으로써 성능이 급격히 나빠지는 현상이 발생한다.

이 문제가 생기는 본질적이 이유(원인)는 무엇인가?

현재 active한 Process들이 요구하는 메모리보다 physical memory가 작기 때문에 생긴다.

이런 상황이 발생되면 thrashing은 피할 수 없게된다.

불필요한 프로세스를 중지시키거나 가능하다면 종료 시키는 것이 thrashing을 해결하기 위한 좋은 방법이다.

개인 PC일 경우 쉽가 할 수도 있지만 서버PC일 경우 OS에서 그럴 수 있도록 무언가가 필요.

이것은 swap device가 존재할 때 발생하는 문제이다.

그런데 swap device가 없으면서도 굉장히 복잡한 모던 OS을 사용하는 기기들이 등장하고 있음 ex) 스마트폰, 디지털TV

Q. Smartphone 처럼 Swap Device가 없는 경우 많은 Process로 인해 Memory가 부족하면 어떻게 처리하는가?

A. Android의 Low Memory Killer와 같이 동작 중인 Process를 강제로 종료시켜 완전히 Memory에서 제거할 수 밖에 없음

Thrashing은 메모리가 over permit되어있기 때문에 발생하게 된다.

p: Page가 Memory에 로드되어 있을 확률

1-p: Page Fault가 발생할 확률

 thrashing을 어떻게 체계적으로 극복할까? Working Set

Working Set: 어느 시점에 특정 Process가 Access하는 Page들의 집합 / 그 프로세스의 그 시점의 locality

Prepaging (Prefetching)

실제 Page 요청이 있기 전에 향후 Access될 것으로 예상되는 Page를 미리 Memory에 로드하는 것

앞에서 배웠던 스케쥴러는 다음에 돌아야될 프로세스를 선정하는 것이었음 (short term scheduler)

long term scheduler: degree of multiprogramming을 낮추는 것이 목적임 (Thrashing이 발생하지 않도록)

working set parameter: 현재부터 과거 t (time unit) 동안 access된 page들을 working set이라고 한다.

단위를 시간으로 하면 어떤 프로세스가 multi tasking kernel이니 항상 도는 것은 아님

다른 프로세스와 CPU를 multiplexing하니까 시간으로 하기는 어려움

page reference의 패턴을 가지고 page table 몇 회를 윈도우 사이즈로 갖는다.  (이렇게 할 수도 있음 but 정답은 아님)

working set을 구현하기 위한 방법

1. reference bit을 사용한다.

Ex) 1000회의 reference동안 page들이 몇회 access됐는가 이런 것을 count하기 위해서 사용

but 오버헤드가 많이 필요함

working set 문제를 비교적 쉽게 구현하기 위해서 사람들이 Approximation한 다른 기법들을 생각하기 시작함

Thrashing은 Active한 working set들의 합이 현재 메모리보다 클 경우 생긴다.

운영체제가 어떻게 현재 특정 Process가 잘 돌고 있는지를 판단하는가?

Page Fault가 얼마나 발생하는지를 확인하여 판단할 수 있다.

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

Threshold 보다 많이 발생하는 경우: 해당 Process에게 더 많은 Memory를 할당

Threshold 보다 적게 발생하는 경우: 해당 Process에게 할당된 Memory를 회수

Resident Set: 프로세스가 어느 시점에 Main Memory에 가지고 있는 page들

이걸 어디에 쓰면 될까?  프로세스들이 idle해 졌을 때 

long term scheduler에 의해서 swap out 당했다가 다시 Main Memory로 불러들일 때(prepaging할 때) 사용함

Trends in Memory Management

기타 등등...

1. physical memory size가 점점 커지고 있다.

 - 페이지 frame이 넉넉하기 때문에 page replacement 알고리즘이 덜 중요해졌다.

 - H/W 적 서포트도 줄어들게 되고 S/W가 emulation(대행, 대리실행)하는 것이 하나의 특징이 되었음

 - page 사이즈도 커지기 시작

Large Page Table의 문제

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

2. Page Table이 Physical Memory의 연속적인 공간에 존재해야 함

해결책은 PPT에 적혀있는 3가지임

1. Hierarchical page table

Table Space를 줄이지는 못하지만 page table들이 physical memory 상에 조각으로 나뉘어져서 scatter(흩어지다) 될 수 있게 허용하는 방법

2. Hashed page table

3. Inverted page table: Table Space를 매우 줄이는 방법

page단위로 다 조각 나있고 각각의 page안에 256개의 entry가 있다. 

8bit이 각 page table 조각에 index로 사용하게 됨

나머지 14bit는 2^14개의 First-level PT(continuous)을 갖고 있음

Large page table의 문제를 어느정도 해소 할 수 있음

문제점: 오버헤드 (내가 원하는 page table fragment가 swap device에 있으면 읽어들여야 하는 오버헤드도 발생 할 수 있음)

page table size를 획기적으로 줄일 수 있는 방법임

address space만큼 page table을 갖는 것이 아닌 physical memory 만큼 page table을 갖음

page table이 한개만 존재

page table의 사이즈가 virtual address space의 사이즈가 아니라 실제로 시스템에 존재하는 page frame의 개수 만큼임

거대한 TLB라고 생각하면 됨 (물론 이 메커니즘이 잘 동작하려면 hash function 성능이 굉장히 좋아야 함)

hash function 성능이 좋지 않다면 동일하게 매핑된 entry에 collision(충돌)이 일어나 performance penalty가 생김

요즘 virtual address space 가 커지니까 점점 많이 사용되는 기법임

---

출처 - http://snui.snu.ac.kr/ocw/index.php?mode=view&id=677

출처 - http://snui.snu.ac.kr/ocw/index.php?mode=view&id=678