TIL 정리_104(Virtual Memory 2)

http://www.kocw.net/home/m/search/kemView.do?kemId=1046323

운영체제 강의를 듣고 정리한 내용입니다.

 

LRU(Least Recently Used) Algorithm

제일 많이 사용되는 알고리즘이다.

제일 오래전에 사용된 것을 내쫒는다(지운다)

 

LFU(Least Frequently Used) Algorithm

참조 횟수가 가장 적은 페이지를 지운다

 

---

다양한 cashing 환경

cashing 기법

캐시 : 한정된 빠른 공간

• 한정된 빠른 공간에 요청된 데이터를 저장해 두었다가 후속 요청시 캐시로부터 직접 서비스하는 방식이다
• 페이징 시스템 외에도 캐시 메모리, 버퍼 캐싱, 웹 캐싱 등 다양한 분야에서 사용된다

 

캐시 메모리 : CPU에서 메모리를 접근 할 때 메인 메모리에 접근하기 전 캐시메모리를 먼저 확인한다.

웹 캐싱 : 동일한 URL에 대하여 읽어오는 페이지를 저장해두었다가 보여준다

 

캐시 운영의 시간 제약

교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없다

-> 어떤 것을 쫓아낼지

>> buffer caching이나 Web caching의 경우

시간 복잡도가 O(1)에서 O(log n)정도까지 허용된다

 

>> Paging system인 경우

페이지 폴트인 경우에만 OS가 관여한다

페이지가 이미 메모리에 존재하는 경우 참조시간 등의 정보를 OS가 알 수 없다

O(1)인 LRU의 리스트 조작조차 불가능하다

 

불가능한 이유

주소변환은 하드웨어적으로 발생한다

invalid라서 페이지 폴트가 발생한 경우 CPU의 제어권이 운영체제로 넘어가게 된다

->그 과정에서 replacement를 통해 하나를 쫓아내야 한다

이 경우 운영체제가 오래전에 사용된 페이지의 구분 여부를 알 수 없다

-> 프로세스가 사용하는 요청한 페이지가 이미 메모리에 올라간 경우 운영체제는 접근 시간을 알 수 없다

페이지 폴트가 발생하여 제어권이 넘어간 이후부터 알 수 있다

 

따라서, 운영체제가 오래전 사용된 페이지를 알 수 없기 때문에

Paging system에서는 LRU, LFU 알고리즘을 사용할 수 없다

 

 

페이징 시스템에서는 무슨 알고리즘을 써야하는가?

Clock Algorithm

LRU의 근사 알고리즘이다

*approximation

 

여러 명칭으로 불린다

• Second chance algorithm
• NUR(Not Used Recently) 또는 NRU(Not Recently Used)

-> 운영체제는 가장 오래전에 참조된 페이지를 알 수 없기 때문에 최근에 사용되지 않은 페이지를 쫒아내는 방법을 쓴다

 

수행 방법

1. Reference bit을 사용해서 교체 대상 페이지 선정한다 (circular list)
2. reference bit가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동한다
3. 포인터가 이동하는 중에 reference bit 1을 모두 0으로 바꾼다
4. Reference bit이 0인 것을 찾으면 그 페이지를 교체한다
5. 한 바퀴 되돌아와서도(==second chance) 0이면 그때에는 교체당한다
6. 자주 사용되는 페이지라면 second chance가 올 때 1이 된다

 

Clock algorithm의 개선

reference bit과 modified bit(dirty bit)을 함께 사용한다

reference bit = 1로 세팅 : 최근에 참조된 페이지임을 표시한다

운영체제가 아닌 하드웨어가 하는 일이다

modified bit = 1로 세팅 : 최근에 변경된 페이지(입출력을 동반하는 페이지)

메모리 참조가 write로 참조되는 경우 modified bit으로 세팅한다

modified bit이 0일 경우 write가 발생하지 않았다는 의미이다

 

 

Page Frame의 Allocation

Allocation 문제 : 각 프로세스에 얼마만큼의 페이지 프레임을 할당할 것인가?

Allocation의 필요성

• 메모리 참조 명령어 수행시 명령어, 데이터 등 여러 페이지를 동시에 참조한다
• 명령어 수행을 위해 최소한 할당되어야 하는 프레임 수가 있다
• Loop를 구성하는 페이지들은 한번에 allocate 되는 것이 유리하다
• 최소한의 allocation이 없으면 매 loop마다 페이지 폴트가 발생한다

 

Allocation scheme

Equal allocation : 모든 프로세스에 똑같은 개수를 할당한다

Proportional allocation : 프로세스 크기에 비례하여 할당한다

Priority allocation : 프로세스의 우선순위에 따라 다르게 할당한다.

 

 

Global vs Local Replacement

Global replacement

replace시 다른 프로세스에 할당된 프레임을 빼앗아올 수 있다

프로세스별 할당량을 조절하는 또 다른 방법이다

FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 해당한다

Working set, PFF 알고리즘을 사용한다

 

Local replacement

자신에게 할당된 프레임 내에서만 replacement된다

FIFO, LRU, LFU 등의 알고리즘을 프로세스 별로 운영시 replcement된다

 

 

Thrashing

• 프로세스의 원활한 수행에 필요한 최소한의 페이지 프레임 수를 할당받지 못한 경우 발생한다
• 페이지 폴트 속도가 매우 높아진다
• CPU utilization이 낮아진다
• OS는 MPD(Multiprogramming degree)를 높여야 한다고 판단한다
• -> 또 다른 프로세스가 시스템에 추가된다 (higher MPD)
• 프로세스는 페이지의 swap in / out으로 인하여 매우 바빠진다
• 대부분의 시간에 CPU는 한가해진다
• low throughput