[운영체제] 가상 메모리 관리(페이지 교체 알고리즘 / 캐싱 기법 / Clock Algorithm / Thrashing)

Demand Paging 기법

요청이 있을 때(실제로 필요할 때) 그 페이지를 메모리에 올리는 방법이다.

실제로 대부분의 시스템은 Paging 기법을 사용한다. 프로그램이 실행될 때 그 프로세스를 구성하는 주소 공간의 페이지를 한꺼번에 메모리에 올리는 것이 아니라, Demand Paging 기법을 사용하여 어떠한 페이지가 요청이 되었을 때만 메모리에 올린다.

 

장점

• I/O 양 감소
• 메모리 사용량 감소
• 빠른 응답시간
• 더 많은 사용자 수용

 

Valid/Invalid 사용

프로그램을 구성하는 페이지들 중에서 당장 필요한 부분은 Demand Paging에 의해서 물리적인 메모리에 올라간다. 그렇지 않은 부분은 Backing Store(Swap area)에 내려가 있게 된다.

따라서 Invalid의 의미는 페이지가 물리적인 메모리에 없는 경우, 프로그램이 사용하지 않는 주소 영역의 경우를 의미하게 된다.

 

Page fault

주소 변환 시 프로그램이 요청한 페이지가 메모리에 없는 경우에 page fault가 발생할 수 있다. 이는 주소 변환 시에 Invalid bit가 set되어 있는 경우를 말한다.

page fault는 대부분의 경우 발생하지 않지만, 발생할 경우에 운영체제와 하드웨어적으로 메모리 접근 시간이 매우 오래 걸리므로 오버헤드가 발생한다.

 

page fault 처리 루틴

1. invalid page를 접근하면 주소 변환을 해주는 하드웨어 MMU가 trap을 발생시킨다. (page fault trap)
2. CPU가 자동적으로 운영체제에 넘어와 커널 모드로 들어가서 page fault handler가 실행된다.
3. page fault를 처리한다.
   1. 주소나 접근 권한이 잘못되어 있지 않은지 확인한다. 정상이라면 취소한다. (abort)
   2. 메모리에서 빈 페이지 프레임을 찾아 가져온다. 만약 빈 페이지가 없다면 어느 한 페이지를 뺏어온다. (replace)
   3. 해당 페이지를 디스크에서 메모리로 읽어온다. (느린 작업이다.)
      • 디스크 I/O가 끝나기 전에 이 프로세스는 CPU를 선점당한다. (block)
      • 디스크 read가 끝나면 page table entry에 valid와 페이지 프레임 번호를 기록한다.
      • Ready Queue에 프로세스를 줄 세우며 Job Queue로 돌려보낸다.
   4. 이 프로세스가 CPU를 잡고 다시 재개된다. (running)
   5. trap 전 중단되었던 instruction이 재개된다.

 

Replacement Alogrithm

페이지 교체 작업을 해주는 알고리즘을 말하며, 가능한 page fault rate을 최소화하는 것이 목표이다.

주어진 page reference string에 대해 page fault를 얼마나 내는지 조사하여 알고리즘을 평가한다.

 

Page replacement

빈 페이지가 없는 경우 어떤 페이지를 빼앗아올지 결정해야 한다. 곧바로 사용되지 않을 페이지를 쫓아내는 것이 좋다.

page reference string

시간 순서에 따라서 페이지들에 서로 다른 번호를 붙여 페이지들이 참조된 순서를 나열해 둔 것

 

1️⃣ Optimal(OPT, MIN)

Opimal 알고리즘은 가장 먼 미래에 참조되는 페이지를 교체하는 알고리즘이다. page fault를 가장 최소화하며, 교체 알고리즘 중에서 가장 효율적인 알고리즘이다.

 

미래의 참조 페이지를 알 수 없지만 이 알고리즘에서는 page reference string을 다 안다고 가정한다. 실제 시스템의 온라인 환경에서 사용할 수 없고, 오프라인 환경에서 이 알고리즘을 운영한다.

따라서 Opimal 알고리즘은 다른 알고리즘의 성능에 대한 upper bound를 제공하는 역할을 한다.

 

2️⃣ FIFO(First In First Out)

가장 먼저 들어온 페이지를 교체하는 알고리즘이다.

특이하게도 FIFO 알고리즘은 페이지 프레임이 늘어나면 page fault가 늘어나는 FIFO Anomaly 현상이 발생할 수 있다.

 

3️⃣ LRU(Least Recently Used)

가장 오래 전에 참조된 페이지를 교체하는 알고리즘이다.

 

LRU 알고리즘의 구현

페이지들을 참조된 시간 순서에 따라서 Linked List로 줄 세운다.

새로운 페이지가 메모리에 진입하거나 이미 존재하는 페이지 중에서 다시 사용이 되면 맨 뒤로 이동시킨다.

시간 복잡도는 O(1)이 된다.

 

4️⃣ LFU(Least Frequently Used)

참조 횟수가 가장 적은 페이지를 교체하는 알고리즘으로, 가장 덜 빈번하게 사용된 페이지를 교체한다.

참조 횟수가 가장 적은 페이지가 여러 개 있을 경우에는 교체할 페이지를 알고리즘 자체에서 임의로 선정하기도 하지만, 실제 활용할 때에는 성능 향상을 위해 가장 오래 전에 참조된 페이지를 지우게 구현할 수 있다.

 

LFU 알고리즘의 구현

Heap의 완전 트리 구조를 사용하며, 페이지를 비교할 때에는 트리 경로를 순회하며 비교하고 교체한다.

시간 복잡도는 O(logN)이 된다.

 

캐싱 기법

한정된 빠른 공간(캐시)에 요청된 데이터를 저장해 두었다가 후속 요청 시 캐시로부터 직접 서비스하는 방법이다. 페이징 시스템 이외에도 cache memory, buffer caching, web caching 등 다양한 분야에서 사용된다.

 

Paging System에서 LRU, LFU 사용이 불가능한 이유

운영체제는 페이징 시스템에서의 페이지 사용 시간 등의 정보를 전부 다 알 수 없다.

운영체제는 page fault가 발생했을 때, 즉 디스크에 접근할 때에만 정보를 알 수 있지만 이미 메모리에 올라가 있는 페이지들에 대해서는 운영체제의 개입이 없기 때문에 알 수 없다.

 

Clock Algorithm

페이징 시스템은 LRU를 근사시킨 알고리즘인 클락 알고리즘을 사용한다.

클락 알고리즘은 Circular Linked List로 구성되어 있으며 최근 사용된 페이지는 reference bit가 1로 표시되어 있고, 최근 사용되지 않은 페이지는 0으로 표시되어 있다.

 

클락 알고리즘은 reference bit를 사용해서 교체 대상 페이지를 선정한다. 주소 변환 시 해당 페이지가 사용(참조) 되었다면 하드웨어가 reference bit를 1로 변경한다. 하드웨어가 해당 페이지를 주소 변환해서 CPU가 가져갔을 때를 말한다.

또한, 운영체제가 페이지를 교체하려고 할 경우에 포인터가 가리키고 있는 페이지의 reference bit가 1일 때 0으로 변경하고, 포인터를 다음으로 이동시킨다. 한 바퀴 돌아와서도 bit가 0이면 그때 그 페이지를 교체한다. (second chance)

 

클락 알고리즘 개선

클락 알고리즘은 reference bit과 modified bit을 함께 사용한다.

• reference bit: 최근에 참조된 페이지
• modified bit: 최근에 변경된 페이지(I/O를 동반하는 페이지)

 

메모리 페이지가 사용되는 것은 CPU가 메모리 위치를 읽어오고, 쓰는 두 가지 상황이 존재한다.

• Read: 페이지가 메모리에 올라온 다음 CPU가 해당 페이지를 접근하면 reference bit을 1로 만들어준다.
• Write: CPU가 해당 페이지를 읽으면 해당 페이지에 대한 reference bit와 modified bit 모두 1로 만들어준다.

 

클락 알고리즘에서 modified bit을 사용하는 이유는 페이지가 메모리에 올라온 이후 Write가 발생했을 때 메모리에서 쫓겨나고 수정 내용을 디스크에서도 Write해주어야 한다. 따라서 Write 발생 여부를 위해서 사용된다.

페이지가 메모리에 올라온 이후에 Write가 적어도 한 번 발생했을 때는 modified bit는 계속 1로 세팅되어 있을 것이다.

 

Page frame의 Allocation

각각의 프로세스에 최소한의 page frame을 할당하는 것을 말한다.

 

Allocation의 필요성

메모리 참조 명령어 수행 시 명령어, 데이터 등을 여러 페이지를 동시에 참조하는데 명령어 수행 시 최소한 할당되어야 하는 frame의 수가 있다.

또한 Loop를 구성하는 페이지들은 한꺼번에 할당되는 것이 유리하다. 최소한의 할당이 없으면 매 Loop마다 page fault가 발생할 수도 있기 때문이다.

 

Allocation Scheme

• Equal Allocation: 모든 프로세스에 똑같은 개수 할당
• Proportional Allocation: 프로세스 크기에 비례하는 할당
• Priority Allocation: 프로세스의 우선순위(자주 사용되는 빈도)에 따라 다르게 할당

 

Global replacement와 Local replacement

Global replacement

각 프로세스에 메모리 할당을 하지 않고, 사용되고 있는 알고리즘에 맞게 사용되게끔 하는 교체 방식으로, 각 프로세스별 할당량이 자동으로 조절된다.

FIFO, LRU, LFU 등의 알고리즘을 global로 사용 시 해당된다.

 

Local replacement

프로세스마다 할당한 다음 자신에게 할당된 frame 내에서만 교체하는 방법이다.

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

 

Thrashing

프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우에 발생하며 page fault가 빈번하게 발생하는 현상이다.

스레싱이 발생하면 CPU 이용률이 낮아진다.

 

Thrashing 방지

프로그램에 필요한 최소한의 메모리를 보장해주는 것이 핵심이다.

• Working-set Model
• PFF(Page-Fault Frequency)

 

Working-set Model

프로세스는 특정 시간 동안 특정 메모리를 집중적으로 참조하는 경향이 있다. 이러한 현상을 Locality of reference라고 하며, 집중적으로 참조되는 page들의 집합을 Locality set이라고 하는데 Working set과 동일한 개념이다.

Working set Model에서는 이러한 Locality 특징을 기반으로 하여 프로세스가 일정시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합을 Working set이라고 정의한다.

 

Working-set Algorithm

특정 window 크기 이내에 있는 page만을 Working set이라고 간주해서 메모리에 유지하고, 그렇지 않은 것은 버린다.

시간에 따라서 필요한 Working set이 변하는 것을 반영하며, 매시점 원활하게 실행되기 위해서 필요한 메모리 크기를 보장해줌으로써 스레싱을 방지할 수 있다.

 

PFF

각 프로세스의 page fault rate를 체크하면서 메모리를 더 할당할지 결정한다.

page fault rate의 상한값과 하한값을 두어 상한값이 넘으면 frame을 더 할당하고, 하한값 이하이면 할당 frame수를 줄인다.

빈 frame이 없으면 일부 프로세스를 swap out한다.

 

Page size의 결정

Page size를 감소시킬 때 장점

• 메모리를 더 잘게 쪼개므로 페이지 수가 증가한다.
• 내부 조각 발생률이 감소한다.
• 필요한 정보만 메모리에 올라와 메모리 이용이 효율적이다.

 

단점

• 페이지 테이블의 크기가 증가한다.
• 디스크 transfer의 효율성이 감소한다.
• Locality의 활용 측면에서 비효율적이다.

 

트렌드는 페이지 크기를 크게 가진다.(4Kb)