08. 가상메모리 - 2

캐싱 기법

한정된 빠른 공간(=캐쉬)에 요청된 데이터를 저장해두었다가 후속 요청 시 캐시로부터 직접 서비스하는 방식

paging system, cache memory, buffer caching, web caching 등에서 사용

buffer caching이나 web caching의 경우 O(1)에서 O(logN)까지 허용

클럭 알고리즘(Clock Algorithm) - 대부분의 시스템에서 사용

일반 페이지 참조 과정에서 OS는 전혀 관여하지 않는다. page fault인 경우에만 OS가 관여함.
따라서 페이지가 이미 메모리에 존재하는 경우에는 참조 시각 등의 정보를 OS가 알 수 없다.
LRU와 LFU의 조작 자체가 불가능하다.

그리고 두 알고리즘은 페이지의 참조 시각, 참조 횟수를 보관하고 있다가 비교해야하므로 오버헤드가 발생해 실제 시스템에서 쓰기 힘들다.

클럭 알고리즘: 하드웨어적인 지원을 통해 이와 같은 알고리즘의 오버헤드를 줄인 방식

LRU를 근사시킨 알고리즘
Second chance algorithm, NUR(Not Used Recently) 혹은 NRU(Not Recently Used) 알고리즘으로 불린다
오랫동안 참조되지 않은 페이지들 중 하나를 골라 교체한다
하드웨어의 지원으로 동작하기 때문에 LRU에 비해 페이지 관리가 훨씬 빠르고 효율적이다

 

동작 방식

• 페이지 프레임의 참조 비트(reference bit)를 순차적으로 조사
  • 참조 비트는 0 또는 1로 표시되는데, 최근에 참조된 페이지는 1로 표시된다 (하드웨어의 작업)
• 한 바퀴 돌면서 참조 비트가 1인 페이지는 0으로 바꾸고 다음 참조 비트로 넘어가 0이면 그 페이지를 쫓아낸다
  시곗바늘이 한 바퀴 도는 동안 다시 참조되지 않은 페이지를 교체한다

개선
reference bit과 modified bit(dirty bit)을 함께 사용

• reference bit = 1: 최근에 참조된 페이지
• modified bit = 1: 최근에 수정된 페이지 (backing store에 수정된 내용 반영 후 쫓아냄)

페이지 프레임의 할당

> 각 프로세스에 얼마만큼의 메모리 공간을 할당할 것인가?

메모리 참조 명령어 수행 시 명렁어, 데이터 등 여러 페이지를 동시에 참조한다

 

한 명령어 수행을 위해 최소한 할당되어야하는 프레임의 수가 있다
loop을 구성하는 page들은 한꺼번에 allocate되는 것이 유리하다
최소한의 allocation이 없으면 매 loop마다 page fault가 발생한다

 

⬇️할당 방식의 분류

균등할당(equal allocation)

모든 프로세스에 똑같은 갯수 할당

비례할당(proportional allocation)

프로세스 크기에 비례하여 할당

우선순위 할당(priority allocation)

프로세스의 priority에 따라 다르게 할당

전역교체와 지역교체

교체할 페이지를 선정할 때 교체 대상이 될 프레임의 범위를 정하는 방식

전역교체(global replacement)

교체 시 다른 프로세스에 할당된 프레임을 빼앗아 올 수 있다
process별 할당량을 조절하는 또 다른 방법
FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용 시에 해당

지역교체(local replacement)

자신에게 할당된 frame 내에서만 교체
FIFO, LRU, LFU 등의 알고리즘을 process별로 운영 시에 해당된다

스레싱(thrashing)

프로세스가 원활하게 수행되기 위해서는 일정 수준 이상의 페이지 프레임을 할당받아야 함

thrashing: 집중적으로 참조되는 페이지들의 집합을 메모리에 한꺼번에 적재하지 못하면 페이지 부재율이 크게 상승해 cpu 이용률이 떨어지는 현상

가로축 = degree of multiprogramming(MPD) 실행 중인 프로세스의 수
세로축 = CPU utilization CPU 이용률
thrashing이 발생한 순간 CPU 이용률이 뚝 떨어지고 있다

 

OS는 MPD를 더 높여야한다고 판단해 또 다른 프로세스가 시스템에 추가되어 프로세스 당 할당된 프레임의 수가 감소하게 된다.

프로세스는 page의 swap in, swap out 작업으로 매우 바쁜 반면에 cpu는 한가한 상황이 된다.
동시에 올라가는 프로그램의 개수를 조절해 프로그램이 어느 정도는 메모리를 확보할 수 있게 해줘야 한다.

워킹셋 알고리즘(working-set algorithm)

프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조하는 특징이 있다
집중적으로 참조되는 page들의 집합을 locality set이라고 한다

working set: locality에 기반해 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와있어야 하는 page들의 집합
프로세스의 working set 전체가 메모리에 올라와있어야 수행되고 그렇지 않다면 모든 프레임을 반납하고 swap out 시킨다

이런 식으로 MPD를 조절하여 thrashing을 방지한다

 

working set의 예

working set의 크기는 그때그때 바뀐다

페이지 부재 빈도 알고리즘(page-fault frequency scheme)

page fault rate의 상한값과 하한값을 둔다

• 상한값을 넘으면 frame을 더 할당한다
• 하한값 이하이면 할당된 frame 수를 줄인다
  빈 frame이 없으면 일부 프로세스를 swap out한다

Page Size의 결정

보통은 4KB

 

Page size를 감소시켰을 때 나오는 현상

• 페이지 수 증가
• 페이지 테이블의 크기 증가
• 내부 조각 감소
• disk transfer의 효율성 감소
  • seek/rotation vs. transfer
  • seek하는데에는 굉장히 오래 걸리기 때문에 이왕이면 한 번에 많은 뭉치를 데려오는 것이 효율적임
• 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
  • locality 활용 측면에서는 좋지 않다

트렌드는 페이지 사이즈를 더 키우는 것이다