REPLACEMENT 알고리즘 환경이 꼭 가상메모리 뿐만 아니고,다양한 곳에서 사용되고 있음.
paging system : 한정된 빠른 공간(물리적인 메모리)에 직접 service를 하는데 요청된 page가 없을 때 page fault가 났고, 느린 저장 장치 (backing store)에서 물리적인 메모리로 읽어오는 기법
cache memory: 일반적인 메모리 참조에서 사용됨. CPU에서 메모리에 접근할 때 CPU랑 메모리 사이에 캐시 메모리 좀 더 빠른 계층을 두고 있다. 혹시 요청된 내용이 캐시 메모리에 있는지 살펴보고, 없는 경우에만 메인 메모리에 요청
buffer caching: 파일 시스템에 대한 READ/WRITE 요청을 메모리에서 빠르게 서비스하는 방식. paging system과 매체는 동일함. 빠른공간이 물리적인 메모리를 뜻하고, 느린 곳이 디스크를 뜻함. 물론, paging system에서 디스크는 swap area에 해당하고, buffer caching에서 디스크는 file system으로 해당함.
힙 자료구조 사용
비교 횟수가 log 2의 n으로 줄어들음.
이 과정에서 운영체제가 하는 일이 없음.
이런 주소 변환은 하드웨어적으로 일어남.
cpu를 프로세스 A가 가지고 있으면서 주소변환을 해서 메모리 참조를 해가는 것.
반면에,
프로세스 A가 주소 변환을 시도했을 때 invalid라서 요청한 페이지가 물리적 메모리에 만약에 없어.
결론: 운영체제는 알 수 없다.
이유: page fault가 날 때만 os가 cpu를 얻는다. page fault가 나지 않을 때는 os는 해당 page가 얼마나 참조되고, 언제 참조됐는지의 정보를 전혀 알 수 없음.
따라서 virtual memeory에서 LRU, LFU 알고리즘은 사실 무용지물임.
그러나 buffer caching, Web caching에서는 쓰이는데, 나중에 알아보자 ~
paging 시스템에서는 쫓아낼 page를 결정하기 위한 LRU, LFU 알고리즘을 사용할 수 없고, Clock 알고리즘을 사용한다.
NUR``NRU
라고 불리기도 함.
각각의 사각형이 page frame다.
즉, 물리적 메모리 안에 들어가있는 page들임.
page에 대해서 어떤 page가 지금 참조가 돼서 cpu가 그 page를 사용하게 되면 그 page에 reference bit이 붙어있따. 주소변환을 해주는 하드웨어가 어떤 page에 대한 접근을 해서 valid라서 그 page를 cpu로 읽어갈 때 , reference bit을 1로 세팅해준다. 즉, 현재 참조가 되면 reference bit을 1로 세팅. 하드웨어가 하는 일.
=> 만약, page fault가 나서 운영체제게 어떤 page를 쫓아내야겠다 싶으면 하드웨어가 세팅해둔 reference bit을 참조하는 것. 만약 reference bit이 1이다. 하면 적어도 이 page가 한번은 참조가 됐구나~ 그런데 reference bit은 최근에 참조됐다는 것을 의미. 운영체제는 reference bit이 1이면 0으로 바꾸고 넘어감. 그러다가 0을 만나면 해당 page를 쫓아냄.
reference bit = 0의 의미
reference bit = 1의 의미
정리)
정리)
modified bit 하나를 더 두고 있음.
응용)
modifited bit이 0인걸 우선해서 쫓아낸다면?
두가지 bit을 같이 이용해서 clock 알고리즘을 개선할 수 있음 ~
LRU, LFU,CLOCK 알고리즘에서는
프로그램 여러개가 물리적 메모리에 같이 올라가 있음.
쫓아낼 때는 어떤 프로세스에 속한 PAGE인지 무관하게 쫓아냈음.
실제로는, 프로그램 원활하게 실행되기 위해서는 CPU에서 실행이 되면서 PAGE FAULT가 안나게 하려면 일련의 PAGE들이 메모리에 같이 올라가 있어가야지 효율적이 됨.
EX) instruction을 실행하는데 있어서 loop를 반복하고 있을경우.
: for 문으로 그 for문에 속한 page가 세개일 때, 이 프로그램한테 세개의 page를 주면, for문을 반복하는 동안에 page fault가 안남.
할당을 해주지 않더라도 우리가 LRU나 LFU 같은 replacement 알고리즘을 사용하다 보면 알아서 어느정도씩 할당이 되는 효과가 있을 수 있다.
어떤 프로그램이 메모리를 많이 필요로 하면, 그 프로그램의 메모리가 그 순간에 메모리에 많이 올라가게 되고 상대적으로 다른 프로그램 page들이 메모리에서 쫓겨나게 된다. 또 다른 프로그램이 메모리가 많이 필요한 순간이 되면은 또 다른 프로그램의 메모리 페이지를 쫓아내고,,,
이런식으로 미리 할당하지 않고 Global replacement
알아서 FIFO
, LRU
, LFU
알고리즘을 사용하면은 그때그때 프로세스별로 메모리 할당량이 자동으로 조절되기 때문에 미리 할당하지 않겠다 !
Global replacement
는 다른 프로그램의 page도 쫓아낼 수 있는 방법.
Local replacement
는 프로그램한테 할당을 해놓은 다음에 새로운 page를 올려놓기 위해서 쫓아내야 할때는 자신에게 할당된 page를 쫓아내는 방법.
Thrashing
이라고 부른다. 일반적으로 multiprogramming degree
를 올려주면 cpu utilization
이 올라간다.
그런데, 계속해서 multiprogramming degree
를 올리면 어느 지점에 이를때 cpu utilization
이 뚝 떨어진다.
=> Thrashing
이 발생한 순간임
각 프로그램마다 메모리 할당량이 너무 적어지게 되면,(degree of multiprogramming이 너무 올라가서 생기는 현상임) page fault가 빈번히 발생하고 => cpu utilization은 낮아진다. (프로그램이 cpu 안쓰고 i/o하러 가게 돼서임)
MPD, 동시에 메모리에 올라가있는 프로그램 개수를 조절해야된다. 프로그램이 어느정도는 메모리 확보를 할 수 있게 해줘야 한다.
=> Working-set
알고리즘, Page-Fault Frequency
알고리즘 이란 것 !
적어도 프로그램들이 메모리에서 원활하게 실행될라면 어느정도의 메모리 PAGE를 가지고 있어야 함.
프로그램이 특정 시간에는 특정 메모리 위치만 참조하는 특징을 가지고 있다. => Reference의 Locality
라고 함.
working set이란 것은 미리 알 수가 없음.
동시에 메모리에 올라가 있으면 좋은 page 집합을 알면, 메모리에 올리면 되는데 정확히 모르기 때문에 여기서도 과거를 통해서 working set을 추정한다. 과거에 d델타 시간동안 참조된 page들은 메모리에서 쫓아내지 않고 유지를 한다. 이 d시간을 window라고 부른다. window size 만큼 현재 시점부터 과거 10번째까지는 이 프로그램의 working set이기 때문에 메모리에 올라가 있어야함. 서로 다른page들을 나열하고, 1,6,7 페이지가 이 프로그램의 working set임.
이 방법도 Multi Programming Degree를 조절하면서 trashing을 방지하는 알고리즘임.이 방식은 working-set 알고리즘 처럼 추정하는게 아니라 현재 시스템에서 page fault가 얼마나 나는지 보고, 특정 프로그램이 page fault를 얼마나 내는지 본다. 만약 page fault가 많이 일으키는 프로그램이 있다면 page를 더준다. 기본적으로 할당되는 메모리 크기가 커지면, page fault가 나는 수가 줄어들어. 어떤 프로그램의 page fault rate이 일정수준 빈번하게 일어나면, page수를 늘려주고, page faultf를 내려준다.
또, 어떤 프로그램은 page fault가 너무 안나면, 메모리를 너무 가지고 있다고 생각.