스레싱(Thrashing)
스레싱은 뭐지?
특정 프로그램을 실행하기 위해 CPU가 메모리 접근을 하는데, 페이지 부재(Page Fault)가 자주 발생하는 상황을 Thrashing이라고 한다.
왜 스레싱이 발생할까?
컴퓨터에는 여러 프로그램이 동시에 메모리에 올라와있기 마련이다. 즉, 메모리에 올라와 있는 프로그램의 개수(Degree Of Multiprogramming)에 맞게 한정된 메모리 자원을 사이좋게 나눠 가져야한다
하지만, 어느정도 빈부격차가 발생할 수 밖에 없다.(프로그램마다 용량이 다르니까...) 결국 운영체제가 특정 프로그램한태 메모리를 너무 적게 할당해줄때 발생한다.
일반적으로 Degree Of Multiprogramming이 증가함에 따라 CPU 이용률도 증가한다
메모리에 프로그램이 하나만 올라와 있으면, CPU 이용률은 낮아진다. CPU가 프로그램을 실행하다가 I/O 작업이 발생해서 Blocking 상태 등이 된다면 더이상 CPU가 실행할 프로그램이 없기 때문이다.
그러다가 메모리에 프로그램이 한개 더 올라오면? 프로세스가 Blocking 상태가 될때 다른 프로그램을 실행시키면 되기 때문에 CPU 이용률은 올라간다.
하지만, 프로그램을 메모리에 계속 올리다 보면 아래 그림처럼 CPU이용률이 뚝 떨어지는걸 볼 수 있다.
이때 스레싱이 발생한 것이다.
프로그램을 올릴 수록 CPU가 더 열심히 일하는거 아니였어?
프로그램이 충분한 메모리 공간을 가져간다면 페이지 교체가 적게 발생해서 페이지 적중(Page Hit) 비율이 증가하는데
프로그램이 너무 많이 올라오면 프로그램마다 할당되는 메모리 공간이 적어지고 페이지 부재(Page Fault) 비율이 증가해서 결국 스레싱이 발생하는 것이다.
악순환의 고리
운영체제는 cpu 이용률이 낮으면 프로그램을 더 올려야 한다고 판단한다. 그럼 각 프로세스가 갖고 있는 메모리 용량이 더 낮아지고, 낮아지면 페이지 부재(Page Fault)가 더 발생하고, 발생하면 cpu 이용률이 낮아지고, 낮아지면 프로그램을 더 올리려고 하고...
이게 반복된다.
그럼 스레싱은 어떻게 해결할까?
두 가지 방법이 있다
1. Working-set 알고리즘
2. PFF(Page Fault Frequency) 알고리즘
프로그램이 필요로 하는 최소한의 메모리는 보장해줘야 한다.
Working Set 알고리즘
결론부터 말하면, Working Set의 개수만큼 메모리 용량을 받지 못한다면 그 프로세스의 메모리를 빼앗아서 스레싱을 방지하는 알고리즘이라고 할 수 있다.
프로그램이 원활하게 실행되는 메모리 용량의 최소값이 있다.
프로그램에는 특정 시간에 특정 메모리 위치만 집중적으로 참조하는 참조 지역성의 특징을 갖고 있는데
특정시간에 집중적으로 참조되는 페이지의 집합은Locality Set이지만, Working Set 알고리즘에서는 Working Set이라고 한다.
즉, 어떤 프로그램이 실행될 때 메모리에 꼭 올라와 있어야 하는 페이지의 집합을 Working Set라고 하고. Working Set을 보장해주는 알고리즘이 Working Set 알고리즘이다.
만약 A 프로그램의 Working Set이 5개라고 가정할 때 운영체제가 A한태 페이지 3개 분량의 메모리 용량만 줄 수 있다면 A의 모든 페이지를 반납하고 Swap Out 상태가 된다.(메모리에서 퇴출된다)
어떻게 동작하는데?
그 프로그램의 Working Set은 미리 알 수는 없다. 즉, 과거의 데이터를 통해 추정한다.
과거 그 프로그램이 x시간동안 참조된 페이지들을 Working Set이라고 가정할 때(x는 윈도우 크기라고 생각하면 된다)
과거에 접근된 페이지 번호가 1, 2, 3, 4, 4이고 x가 5라면 Working Set은 중복을 제거한 1, 2, 3, 4으로 4개이다.(4는 중복이니 제거했다)
이 프로세스에게 4개만큼 메모리의 페이지 프레임을 제공할 수 있다면(페이지 프레임은 보통 4kb이니까 16kb만큼의 메모리 용량을 할당받는 것) 1, 2, 3, 4페이지를 메모리에 올려놓는다.
하지만, 4개 만큼의 페이지 프레임을 줄 수 있는 여력이 없다면, 이 프로세스를 메모리에서 제거한다. Swap Out해서 디스크로 보내버린다.(참고로 이 역할은 스와퍼가 한다)
다만, x는 어떤 기준으로 정하는 건지 모르겠다.
PFF(Page Fault Frequency) 알고리즘
Degree Of MultiProgramming을 조절하면서 스레싱을 방지한다는 건 동일하지만, Working Set을 추정하기 보단 페이지 부재율(Page Fault Rate)을 보면서 조절한다는 차이가 있다.
일반적으로 프로그램한태 할당되는 메모리의 크기가 커지면 페이지 부재율(Page Fault Rate)은 줄어든다. 그렇기에 특정 프로그램에서 페이지 부재(Page Fault)가 많이 발생한다면 메모리를 더 많이 줘서 스레싱을 해결한다.
반대로 페이지 부재율(Page Fault Rate)가 너무 발생하지 않으면, 메모리를 빼앗아서 일정 수준의 페이지 부재율(Page Fault Rate)로 만들어 버린다.
이것이 PFF 알고리즘의 동작 방식이다.
