[OS(2)]Virtual Memory2

이유정·2024년 6월 18일

운영체제

목록 보기

47/49

다양한 캐슁 환경

01. 캐싱 기법

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으로 해당함.
- 컴퓨터 시스템에서 데이터 접근 속도를 높이기 위함

web caching: 웹 페이지를 볼 때 웹페이지에 대한 요청을 하면 , 멀리 있는 웹서버에서 가져와야 하는데, 만약 동일한 URL에 대해서 지금도 요청, 이따가도 요청 한다면 웹서버에서 가져오는건 시간이 오래거림. 이미 읽어온 웹 페이지를 저장했다가 화면에 보여주면 더 빠름.

02. 캐쉬 운영의 시간 제약

LRU와 LFU 알고리즘의 구현

힙 자료구조 사용

메모리 안 페이지들을 트리 형태로 구성
힙이라는 것은 항상 부모보다 자식이 참조 횟수가 많다.

비교 횟수가 log 2의 n으로 줄어들음.

Paging System에서 LRU, LFU 가능한가?

process A가 CPU에서 러닝중
프로세스 A의 논리적인 메모리에서 매순간마다 instruction을 하나씩 읽어와서 실행을 한다.
그런데, cpu에서 프로세스 A에 대한 논리주소를 주는데 page table을 통해서 물리적인 주소로 변환한다.
그리고 물리적인 메모리 주소에 있는 내용을 cpu에 읽어들인다.
그런데 만약에 주소변환을 했는데 해당하는 page가 이미 물리적인 메모리에 올라가 있다?
그러면, 물리적인 메모리에서 직접 그 내용을 읽어서 cpu로 가져감

이 과정에서 운영체제가 하는 일이 없음.
이런 주소 변환은 하드웨어적으로 일어남.
cpu를 프로세스 A가 가지고 있으면서 주소변환을 해서 메모리 참조를 해가는 것.

반면에,
프로세스 A가 주소 변환을 시도했을 때 invalid라서 요청한 페이지가 물리적 메모리에 만약에 없어.

백킹 스토어에 있으면, 이런 상황 page fault
page fault가 나면 디스크 접근을 필요로 하기 때문에 즉, i/o가 필요하기 때문에 프로세스 A가 디스크에 메모리 읽어오는 작업을 할 수 없다.
그러면 trap이 발생.
cpu 제어권이 프로세스 A => 운영체제로 넘어가.
운영체제가 디스크에 있는 페이지를 읽어서 물리적인 메모리로 올려둔다.
그 과정에서 필요하면 하나의 page를 쫓아내는 replacement를 해야한다.
그런데 어떤걸 쫓아낼지 운영체제가 쭉 살펴보는데
1) LRU 알고리즘을 쓴다면,
가장 오래전에 참조된 PAGE를 쫓아내야 하는데, 운영체제가 알 수 있는가?
2) LFU 알고리즘을 쓴다면,
가장 적게 참조된 PAGE를 쫒아내야 하는데, 운영체제가 알 수 있는가?

결론: 운영체제는 알 수 없다.

이유: page fault가 날 때만 os가 cpu를 얻는다. page fault가 나지 않을 때는 os는 해당 page가 얼마나 참조되고, 언제 참조됐는지의 정보를 전혀 알 수 없음.
따라서 virtual memeory에서 LRU, LFU 알고리즘은 사실 무용지물임.
그러나 buffer caching, Web caching에서는 쓰이는데, 나중에 알아보자 ~

Clock Algorithm

paging 시스템에서는 쫓아낼 page를 결정하기 위한 LRU, LFU 알고리즘을 사용할 수 없고, Clock 알고리즘을 사용한다.

LRU 알고리즘을 근사시킨 알고리즘이다.
최근에 사용되지 않은 페이지 알고리즘: 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의 의미

이 시계 바늘이 한바퀴 돌아오는 동안에 이 page에 대한 참조가 없었다는 것.

reference bit = 1의 의미

이 시계 바늘이 한바퀴 돌아오는 동안에 적어도 이 page에 대한 참조가 1번은 있었다는 것.

정리)

하드웨어가 이 page들을 참조할 때 reference bit을 1로 변경하는 역할을 함.
운영체제는 이 bit을 보면서 어떤것을 쫓아낼지 결정할 때 reference가 1인건 0으로 바꾸고, 0인건 쫓아낸다.
- 가장 오래전에 참조된 page를 쫓아내는 것은 아님.
- LRU와 정확히 일치하는 운영을 하는 것은 아님.
- 오랫동안 참조 안된 page를 쫓아내기 때문에 어느정도 LRU하고 비슷한 효과냄.

정리)

Virtual memory, paging system에서 일반적으로 사용하는 알고리즘이다.

modified bit 하나를 더 두고 있음.

어떤 page가 메모리 page가 참조되는 건 read로 참조 or write로 참조
어떤 page가 reference bit이 0이라서 쫓겨나야 할 때 , 만약 modified bit이 0이라면? 그러면 이 page는 backing store에서 물리적 메모리로 올라온 이후로, write가 발생하지 않은 것임. 그런 page는 그냥 쫓아냄.
만약 modified가 1인 page가 쫓겨난다면, write이 발생했다는 이유기 때문에 backing store에 수정된 내용을 반영한 다음에 지우면된다.

응용)
modifited bit이 0인걸 우선해서 쫓아낸다면?

disk에 쫓겨난 page를 써줄 필요가 없기 때문에 조금 더 빠를 수 있음.

두가지 bit을 같이 이용해서 clock 알고리즘을 개선할 수 있음 ~

Page Frame의 Allocation

LRU, LFU,CLOCK 알고리즘에서는
프로그램 여러개가 물리적 메모리에 같이 올라가 있음.
쫓아낼 때는 어떤 프로세스에 속한 PAGE인지 무관하게 쫓아냈음.
실제로는, 프로그램 원활하게 실행되기 위해서는 CPU에서 실행이 되면서 PAGE FAULT가 안나게 하려면 일련의 PAGE들이 메모리에 같이 올라가 있어가야지 효율적이 됨.

EX) instruction을 실행하는데 있어서 loop를 반복하고 있을경우.
: for 문으로 그 for문에 속한 page가 세개일 때, 이 프로그램한테 세개의 page를 주면, for문을 반복하는 동안에 page fault가 안남.

그런데, for문을 구성하는 page가 3개인데 이 프로그램한테 page를 두개만 줬다? 그럼 백만번 반복하는 동안에 계속 page fault가 난다. 프로그램마다 적어도 어느정도 몇개의 page를 줘야지만 page fault가 잘 안나는 일련의 page개수가 존재함.
프로그램이 실행되면서 필요에 따라서는 데이터에 접근하는 경우가 있음.
- 최소한 데이터에 해당하는 page도 메모리에 올라가 있어야만 page fault가 덜 남.

Global vs. Local Replacement

할당을 해주지 않더라도 우리가 LRU나 LFU 같은 replacement 알고리즘을 사용하다 보면 알아서 어느정도씩 할당이 되는 효과가 있을 수 있다.
어떤 프로그램이 메모리를 많이 필요로 하면, 그 프로그램의 메모리가 그 순간에 메모리에 많이 올라가게 되고 상대적으로 다른 프로그램 page들이 메모리에서 쫓겨나게 된다. 또 다른 프로그램이 메모리가 많이 필요한 순간이 되면은 또 다른 프로그램의 메모리 페이지를 쫓아내고,,,
이런식으로 미리 할당하지 않고 Global replacement
알아서 FIFO, LRU, LFU 알고리즘을 사용하면은 그때그때 프로세스별로 메모리 할당량이 자동으로 조절되기 때문에 미리 할당하지 않겠다 !

그런데 LRU나 LFU 같은 방법은 어느정도 프로그램한테 페이지를 할당하는 효과는 없다.
그런데 Working set, PFF 알고리즘 같은 경우에는 프로그램이 최소로 필요로 하는 그런 PAGE들을 동시에 메모리에 올려놓는, 즉, 할당 효과가 있는 알고리즘이다.

Global replacement는 다른 프로그램의 page도 쫓아낼 수 있는 방법.
Local replacement는 프로그램한테 할당을 해놓은 다음에 새로운 page를 올려놓기 위해서 쫓아내야 할때는 자신에게 할당된 page를 쫓아내는 방법.

Thrashing

어떤 프로그램한테 최소 메모리가 할당이 안되었을 때는 page fault가 자주난다.
=> 이러한 상황을 Thrashing이라고 부른다.

Thrashing Diagram

degree of multiprogramming : 지금 메모리에 올라가있는 프로그램 개수
메모리에 동시에 올라가있는 프로그램이 늘어남에 따라서 cpu 이용률은 어떻게 되는가?

일반적으로 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 알고리즘 이란 것 !

Working-Set Model

적어도 프로그램들이 메모리에서 원활하게 실행될라면 어느정도의 메모리 PAGE를 가지고 있어야 함.
프로그램이 특정 시간에는 특정 메모리 위치만 참조하는 특징을 가지고 있다. => Reference의 Locality라고 함.

Working-Set Algorithm

working set이란 것은 미리 알 수가 없음.
동시에 메모리에 올라가 있으면 좋은 page 집합을 알면, 메모리에 올리면 되는데 정확히 모르기 때문에 여기서도 과거를 통해서 working set을 추정한다. 과거에 d델타 시간동안 참조된 page들은 메모리에서 쫓아내지 않고 유지를 한다. 이 d시간을 window라고 부른다. window size 만큼 현재 시점부터 과거 10번째까지는 이 프로그램의 working set이기 때문에 메모리에 올라가 있어야함. 서로 다른page들을 나열하고, 1,6,7 페이지가 이 프로그램의 working set임.

PFF(Page-Fault Frequency) Scheme

이 방법도 Multi Programming Degree를 조절하면서 trashing을 방지하는 알고리즘임.이 방식은 working-set 알고리즘 처럼 추정하는게 아니라 현재 시스템에서 page fault가 얼마나 나는지 보고, 특정 프로그램이 page fault를 얼마나 내는지 본다. 만약 page fault가 많이 일으키는 프로그램이 있다면 page를 더준다. 기본적으로 할당되는 메모리 크기가 커지면, page fault가 나는 수가 줄어들어. 어떤 프로그램의 page fault rate이 일정수준 빈번하게 일어나면, page수를 늘려주고, page faultf를 내려준다.
또, 어떤 프로그램은 page fault가 너무 안나면, 메모리를 너무 가지고 있다고 생각.