가상메모리
다양한 캐시 환경
앞선 살펴본 가상 메모리의 페이지교체 알고리즘은 메모리에만 적용되는 것이 아닌 컴퓨터 시스템에서 다양하게 사용되어진다. 그 중 캐쉬환경에서 페이지교체 알고리즘이 적용된다.
캐시메모리란 한정된 빠른 공간(캐시)에 데이터를 저장했다가 후속에 동일한 요청이 올때 캐시메모리에서 서비스를 제공하는 방식이다.
cpu에서 메모리에 접근하는 것은 바로 직접 접근하는 것이 아니다. cpu와 메모리 사이에 존재 하는 좀 더 빠른 접근이 가능한 캐시메모리 계층에 먼저 접근하게 된다.
그리고 캐시메모리에 해당 데이터가 있는지 확인 하고 없는 경우에만 메모리에 접근하게 된다.
buffer caching 파일시스템에 대한 read/write요청을 메모리에서 빠르게 서비스하는 방법이다.
web caching 웹페이지에 대한 요청을 하면 웹서버에서 가지고 와서 웹브라우저에 표시를 하는데, 동일한 url에 대해서 다시 요청을 하게 되서 웹서버로 부터 다시 읽어 들여오면 느리기 때문에, 내 컴퓨터에 읽어온 웹페이지를 저장해두고서 요청이 올때 이 저장된 것을 보여주는 것이다.
캐시에서는 교체 알고리즘에서 어떤 것을 교체할지에 대해서 시간 제약이 있다. 너무 많은 시간을 고려해서 교체 알고리즘을 사용한다면 이는 오버헤드가 발생한다. 그렇기 때문에 O(1)이나 O(longN)까지가 적당한 수준이다.
LRU와 LFU를 이용한 페이지교체 알고리즘
LRU는 연결리스트 처럼 구현해서 제일 앞에 있는 것을 쫒아낸다. 그리고 다시 참조되는 경우는 빼서 아래로 이동시킨다. 새롭게 참조되는 것은 맨 뒤에 이어준다. 시간복잡도는 O(1)이 된다. 비교가 필요없다. 단순히 상수시간안에 가능하다.
LFU의 경우는 heap을 이용해서 구현한다. 최소힙을 이용해서 루트에 제일 적게 참조되는 것을 두고 교체될때는 루트를 제거하면 된다. 힙안에서 페이지가 다시 참조되는 경우라면 직계 자식과 비교만 해서 힙을 재 조정하면 된다.
LRU와 LFU는 사용가능?
운영체제가 가장오랜된 참조페이지를 알 수 있을까? 모른다.
운영체제가 가장적게 참조되는 페이지를 알 수 있을까? 모른다.
그러므로 실제로 LRU나 LFU를 사용하기는 어렵다.
페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 운영체제가 알수 없다.
다만, 페이지폴트가 발생했을 경우만 운영체제에 트랩이 걸려서 cpu제어권이 넘어오기 때문에 이에 대한 정보를 알수 있다.
그렇기 때문에 운영체제한테 주어지는 정보가 "반쪽" 만 주어지게 된다.
LRU나 LFU와 같은 알고리즘을 페이징시스템, 가상메모리시스템에서는 사용할 수 없다.
그럼 어떤 알고리즘을 사용해야 할까? Clock?
clock 알고리즘
LRU의 근사 알고리즘이다.
reference bit 주소변환을 해주는 하드웨어가 세팅을 해주는 것이다.
이미 메모리에 존재하는 페이지에 대해서 그 페이지가 참조되면 cpu가 읽어 들이면서 레퍼런스를 1로 한다.
modified bit은 메모리 참조가 read로 참조될 수도 있지만 write로 참조될 수도 있다.
write로 참조가 되면 modeified bit을 1로 세팅을 한다.
원에 있는 사각형들이 물리적메모리의 페이지프레임이다.
하드웨어가 설정한 reference를 보고서 1이면 0으로 바꾸고 다음을 본다. 0으로 바꾸면서 움직인다. 하드웨어가 참조할 때 reference를 1로 만드는 역할을 하고 운영체제는 하드웨어가 설정한 reference bit을 보면서 어떤 것을 쫒아낼지를 결정할때 1인거는 0으로 바꾸고, 0을 쫒아낸다.
시계바늘이 한바뀌 도는 동안에 참조가 안되는 것을 쫒아내기 때문에 LRU와 근사한 기법이라고 할 수 있다.
일정 페이지프레임 할당은 페이지 폴트를 막는다?
프로세스마다 일정량의 페이지프레임을 주어야지 페이지폴트가 빈번히 발생하지 않을 것이다.
프로세스마다 page allocate를 해주지 않으면, 특정 프로세스가 많은 페이지 프레임을 차지하는 경우가 발생할 수도 있다.
각각의 프로세스에 어느정도의 페이지 프레임을 나누어 주자는 것이다.
allocation 방법
equal allocation
동일한 갯수를 할당
proportional allocation
프로세스 크기에 비례해서 할당
priority allocation
프로세스의 cpu priority(cpu 우선순위)에 따라 다르게 할당
할당을 하지 않아도 배분이된다?
Global replacement
다른 프로세스의 페이지도 쫒아낼 수 있다.
할당을 하지 않더라도,페이지교체 알고리즘을 사용하다보면 일정량의 페이지프레임이 할당되는 효과가 발생할 수 있다.
working set, PFF알고리즘은 할당의 효과가 있는 알고리즘이다.
미리 할당을 하지 않아도 알고리즘에 의해서 할당이 된것 같은 효과를 발생시키면서 운영되는 것이다.
Local replacement
앞서 본 allocation방법을 통해서 할당을 하고 프로세스 내에서 자신에게 할당되 메모리에 대해서 자기의 페이지를 교체하는 교체알고리즘이 필요할 것이다.
페이지폴트가 계속 난다...
Thrashing
프로그램에 최소 메모리도 할당이 되지 않으면 페이지폴트가 자주난다.
프로그램에 너무 적은 메모리가 할당되어서 페이지폴트가 지나치게 많이 발생하는 경우를 thrashing 이라고 한다.
페이지폴트가 빈번히 발생하면 cpu utilization이 낮아진다.
페이지폴트가 발생해서 계속해서 I/O작업을 하러 가야한다.
위의 그림에서 너무 많은 프로그램이 올라가게되면, 프로그램 별로 할당받는 메모리 영역이 작아지고, 그러다보니 많은 페이지폴트가 발생해서 페이지를 가지고 오기 위해서 I/O작업을 하다보니까 cpu utilization이 낮아지게 된다.
운영체제는 cpu utilization이 낮으니까 cpu가 놀고있다고 생각해서 프로그램을 더 메모리에 올리게 되고, 또 다른 프로그램이 올라가서 다시 각 프로세스가 가지는 메모리가 작아지고, 그러면 또 페이지폴트가 발생하는 악순환이 반복한다.
멀티프로그래밍 정도가 높아지면 cpu 이용률이 떨어져서 시스템이 비효율적으로 되는 현상을 의미한다.
해결하기 위해서는 멀티프로그래밍 정도를 조절해주어야 한다.
그래서 프로그램들이 적어도 일정량 이상의 메모리를 할당 받게 해주는 것이 필요하다. 그것이 work set과 ppf이다.
집중참조 집합 Working-set
working-set을 이용한 페이지디폴트 방지
적어도 프로그램이 원할이 수행을 위해서는 일정량의 메모리를 할당받아야 한다.
locality of reference
프로세스는 특정시간 동안 일정 장소만을 집중적으로 참조한다.
for loop를 수행되는 동안은 loop만 집중적으로 참조한다.
함수를 수행하는 동안은 함수를 구성하는 페이지만 집중적으로 참조한다.
특정시간에 집중적으로 참조되는 페이지들의 집합을 locality set이라고 한다.
working-set Model에서 locality set을 working set이라고 부른다.
어떤 프로그램이 실행되면서 그 순간에 메모리에 꼭 올라와 있어야 하는 빈번히 참조되는 페이지들의 집합을 working set이라고 부른다.
working set은 메모리에 올라와 있는 것을 보장해주어야지만, 페이지폴트가 잘 발생하지 않을 것이다.
멀티프로그램 정도가 너무 높으면 working set을 보장할 수 없는 사태가 발생한다.
working set은 5개가 필요한데, 멀티프로그램정도가 높아서 3개만 할당되었다. 이런 경우는 모든 페이지(3개)를 반납하고 디스크로 swap out된다.
working set 모델은 멀티프로그램 정도를 조절해서 working set이 한꺼번에 올라가는 것이 아니라면 프로세스의 메모리를 빼았아서 Thrashing을 방지한다.
페이지디폴트 빈도수 PFF
프로세스별 페이지디폴트 빈도수를 확인해서 판단
멀티프로그램 정도를 조절하면서 Thrashing을 방지한다.
페이지폴트 정도를 보고서 페이지폴트를 많이 발생시키는 프로세스에 대해서는 좀 더 많은 메모리 할당
