[ OS 기초 ] 10. Virtual Memory Management (2)

0. 가상 메모리 관리란 무엇인지, 관련된 개념
1. 가상 메모리 관리 - 하드웨어 컴포넌트
2. 가상 메모리 관리 - 소프트웨어 컴포넌트
3. 가상 메모리 관리 - 소프트웨어 컴포넌트 중 교체 전략 - FA, VA based를 중심으로
4. 기타 가상 메모리 관리 시 고려해야 할 요소들

 

00 개요

가상 메모리 관리 방법으로 하드웨어와 소프트웨어 컴포넌트들을 살펴봤는데 이 중에서 소프트웨어 컴포넌트의 replacement strategies(교체 전략)을 구현하는 고정 할당 기반, 변동 할당 기반의 다양한 알고리즘을 살펴본 뒤 기타 가상 메모리 관리를 위한 고려 사항들에 대해 알아보는 것으로 가상 메모리 관리 부분을 마무리할 예정.

 

01 교체 전략과 지역성

교체 전략 : 어떤 프로세스에 할당된 메모리를 전부 사용하고있는 상황에서 추가적으로 다른 데이터를 메모리에 올려야 할 때, 현재 적재되어있는 메모리 중 어떤 것을 내릴 (가상 메모리로 돌려보낼) 것인지 결정하는 전략

지역성 : 교체 전략을 세울 때 고려해야 할 기준. 지역성을 잘 활용하면 성능을 높일 수 있음
- 개념 : 프로세스가 프로그램이나 데이터의 특정 영역을 집중적으로 참조하는 현상
- 종류 : 시간적 지역성(가까운 시간 이내에), 공간적 지역성(근처 데이터)
- 예시

• 페이징 시스템을 가정할 때
• 이중 for문을 돌면서 값을 비교해야 하는 코드를 작성했을 경우
  • 여러 메모리 중 특정 페이지를 반복적으로 접근하게 됨 = 지역성
  • 값을 읽어오는 페이지, 값을 비교하는 페이지, for문에 사용된 변수를 지정하는 페이지 등

 

(전제 : 페이징 시스템)

02 Fixed Allocation Based Schemas

FA based Schemas 는 페이지 고정 할당을 전제로, 프로세스에 고정된 페이지 프레임의 개수를 할당한다고 가정한 상태에서의 교체 전략에 대해 다루고 있다. 예를 들어 특정 프로세스가 4개의 페이지 프레임을 할당받은 상태에 이미 4개의 페이지 프레임을 사용하고 있다. 이때 만약 새로운 페이지가 필요해졌을 경우 어떤 페이지를 내보내고 새로운 페이지를 올릴지 교체할 대상을 결정해야 하는데, 이때 이 결정 방식을 FA based 교체 전략이라 한다. 아래와 같이 다양한 방법이 FA based schemas에 해당한다.

• MIN Algorithm : 최적의 알고리즘, page fault 가 최소인 알고리즘
• Random Algorithm : 랜덤으로 교체하는 알고리즘, 구현한 알고리즘이 랜덤보다 page fault가 많다면 랜덤 사용
• FIFO Algorithm : 선입선출(먼저 사용했던 순서대로 교체) 알고리즘
• LRU Algorithm : 최근에 가장 조금 사용한 (Least Recently Used) 페이지 교체 알고리즘
• LFU Algorithm : 가장 자주 쓰지 않는 페이지 교체 알고리즘(Least Frequently Used)
• NUR Algorithm : 최근에 사용 안한 페이지 교체 알고리즘(Not Used Recently)
• Clock Algorithm :포인터가 가리키는 페이지를 교체 후보로 고려, 참조 비트(reference bit)로 판단하는 알고리즘
• Second Chance Algorithm : clock algorithm + update bit
• other Algorithms...

 

02-1 MIN Algorithm
- Minimize Page Fault Frequency 알고리즘으로, 최적의 솔루션에 해당한다
- 최적이지만, 실현 불가능한(Unrealizable) 알고리즘으로, 다음에 어떤 페이지를 참조할지 모두 알고 있다고 전제
- 방법 : 앞으로 가장 오랫동안 참조되지 않을 페이지를 교체하는 방식
- 보통 다른 알고리즘의 성능 평가를 위한 비교 기준으로 쓰기 위해 활용

02-2 Random Algorithm
- 무작위로 교체할 페이지를 선택하는 알고리즘으로, 오버헤드가 적음
- 보통 다른 알고리즘의 성능 평가를 위한 비교 기준으로 쓸 수 있음(랜덤보다 안좋으면 차라리 랜덤을 쓰도록)

02-3 FIFO Algorithm
- First In First Out 알고리즘으로, 먼저 사용했던 페이지를 교체시키는 알고리즘
- 먼저 사용했다는 정보 = 시간, 즉 적재된 시간 정보를 알고 있어야 함
- 자주 사용하는 페이지가 교체될 경우 page fault가 급격히 증가하며 지역성를 고려하지 않는 알고리즘
- FIFO anomaly : 페이지 프레임을 더 할당하더라도 성능이 떨어지는(자원 증가에도 불구하고 성능은 낮아지는 현상)으로 원인은 지역성을 고려하지 않기 때문임

02-5 LRU Algorithm
- 사용한지 오래된, 가장 오랫동안 쓰지 않은 페이지를 교체하는 알고리즘
- 지역성을 고려한 알고리즘으로, 언제 사용했는지 참조한 시간 정보를 기록하고 있어야 함(오버헤드)
- 그나마 최적의 알고리즘(MIN)에 근접한 성능을 보여주고, 가장 많이 활용되고 있는 기법
- 단, 루프(for문)에 필요한 크기보다 적은 수의 페이지 프레임을 할당받았을 경우 페이지 폴트가 급격히 증가하는데, 이 경우에는 할당 기법과 협조해 해결해야 함

02-6 LFU Algorithm
- 가장 사용하는 빈도가 낮은 페이지를 교체하는 알고리즘으로 사용 빈도 정보를 저장해야 함
- 지역성을 고려한 알고리즘으로, LRU 알고리즘 대비 오버헤드는 적다(시간이 아닌 빈도만 저장하면 되기 때문)
- 빈도 수를 따지기 때문에 최근에 참조된 페이지가 교체되어버릴 위험이 있고, 참조 횟수 누적에 따른 오버헤드도 발생
- 역시 지역성을 고려했기 때문에 성능이 비교적 괜찮음

02-7 NUR Algorithm
- 최근에 사용되지 않은 페이지를 교체하는 알고리즘
- 비트 벡터를 활용해 구현. 최근 참조하지 않은 페이지부터 교체하되, 최근 업데이트된 페이지들은 후순위로 두고 참조하지 않았던 페이지들부터 교체시켜버리는 방식

02-8 Clock Algorithm
- 시계의 시침, 분침처럼 포인터가 돌면서 페이지 프레임을 가리키고, 그 페이지 프레임의 참조 비트를 확인한 뒤 조건을 만족하면 교체시키는 방식
- 만약 참조한 적이 있다면(참조비트 = 1)? 다음 포인터로 이동할 때 참조 비트를 초기화함(=다음에는 0이 될 것)
- FIFO처럼 먼저 들어온 페이지가 교체될 가능성이 높으면서 동시에 비트 벡터를 활용하기때문에 지역성도 어느 정도 고려한 알고리즘으로 LRU, NUR와 유사함

02-9 Second Chance Algorithm
- clock algorithm과 유사한데 업데이트 비트도 활용하는 알고리즘
- 방법 : 만약 참조비트가 1 이면 지나가면서 0으로 바꿔주고 만약 참조 비트가 0이라면 업데이트 비트를 살펴봄. 만약 업데이트 비트가 1이라면 swap device에 업데이트를 write back 한 뒤 0으로 초기화해주고 만약 업데이트 비트도 0이라면 교체 대상이 됨

02-10 Others...
- 다른 비트를 더 활용해 판단하는 알고리즘들 => 더 많은 정보를 활용한다 = 오버헤드 증가
- 다양한 방법들이 있지만 핵심은 지역성을 잘 고려해 페이지 폴트를 줄여 성능을 높일 수 있는 알고리즘이 좋다

 

03 Variable Allocation Based Schemas

Fixed Allocation Based Schemas와 달리 프로세스에 할당되는 페이지 프레임의 수가 가변적인 경우에 사용할 수 있는 다양한 교체 기법들에 대한 내용이다. 종류는 크게 다음과 같이 나눌 수 있다.

• WS Algorithm
• PFF (Page Fault Frequency) Algorithm
• VMIN (Variable MIN Algorithm)

 

03-1 WS Algorithm
- Working Set : 일하는 + 집합 = 현재 작업중인/사용중인 페이지들의 집합
- '현재' = 시점 => 로컬리티와 연관이 있고, 시간에 따라 working set은 변함
- 프로세스가 특정 시점에 자주 참조하는 페이지들의 집합을 의미하며, 이 특정 시점은 델타(Δ)를 의미
- 워킹셋에 있는 페이지들은 항상 메모리에 유지하고, 워킹 셋에 없다면 메모리 반납
- 최근 참조된 페이지를 고려한다는 점에서(지역성) 페이지 폴트를 줄일 수 있고, Δ 값에 따라 성능이 결정됨
- 적재되는 페이지가 없어도 메모리를 반납하는 경우가 있고, 새로 적재되는 페이지가 있어도 교체되는 페이지는 없을 수 있음. ( 워킹 셋을 보기 때문 )
- 지속적으로 윈도우를 움직여 가며 관찰하는데서 오버헤드가 생기고 residence set에 대한 관리에서 또 오버헤드.
- WS Algorithm이 variable allocation, fixed window 사이즈를 가정, 그렇다면 fixed allocation, variable window 방식의 기법은?
답 : LRU (최근에 사용된 애들만 담고 있는 알고리즘)

03-1-1 W(t,Δ) : t는 현재 시간, Δ는 델타(윈도 사이즈, 시스템 파라미터)로 [t-Δ, t] 동안 참조된 페이지들의 집합을 의미
- 윈도우 : 시간
- 윈도우에 참조할 수 있는 페이지들의 개수는 최소 1개 ~ 최대 Δ+1개

Window Size가 클수록 Working Set Size도 커진다? NO. 구간에 따라 다름

 

03-1-2 Working Set Transition
프로그램이 여러 개의 루프로 구성되어 있고 각 루프가 2,3,2개의 페이지를 참조한다고 할 때 루프를 도는 시점에서의 워킹 셋 사이즈는 유지되지만, 루프 전환이 발생할 때 워킹 셋 사이즈에는 변화가 생김. 이를 working set transition이라 함.
- 이 예시의 경우 2=>3 으로 처음엔 증가하는 경향을 보이는데 이렇게 일시적으로 메모리 할당 수가 중가 하는 상황

03-1-3 성능 평가
Fixed Allocation의 경우 페이지 폴트의 횟수로 성능을 판단했지만, Variable allocation은 기법에 따라 제공되는 자원의 수도 달라질 수 있기 때문에 다른 지표도 성능 평가에 고려해야 한다. 따라서 평균 페이지 프레임의 수와 페이지 폴트의 수를 보는데 이들 정보의 비용 정보로 성능을 비교할 수 있다.

• 페이지 프레임 유지비용
• 페이지 폴트 처리 비용

03-1-4 윈도우 사이즈, 페이지 라이프타임, 페이지 폴트의 관계

• 윈도 사이즈가 크면?
  • 페이지 라이프 타임은 길어짐
    • 페이지 유지 비용은 증가함
  • 페이지 폴트는 감소함

위와 같은 관계가 있기 때문에 적당히 잘 크기를 조절해야 한다는 특징이 있다.

 

03-2 PFF Algorithm
- WS Algorithm은 워킹 셋을 계속 관리해야 한다는 단점이 있는데, 이 문제를 해결하기 PFF Algorithm을 사용할 수 있음
- WS는 페이지 폴트가 없어도 관리를 해야 한다면, PFF는 페이지 폴트가 생겼을 때 관리하는 알고리즘(오버헤드 낮음)
- 얼마나 자주 페이지 폴트가 발생하는가에 따라 몇 개의 페이지 프레임을 할당할지 결정하는 알고리즘
- 자주 발생한다면, 메모리를 늘려주고 반대라면 메모리를 줄여주는 방식으로 구현(할당된 페이지 프레임 개수 조절)
- 자주의 기준 : 타우(t)라는 threshold value로 inter fault time을 의미함 
- 할당되는 메모리의 변화는 페이지 폴트 발생 시에만 생기기 때문에 비교적 오버헤드가 낮음

• inter fault time : 현재 페이지 폴트 발생 시간에서 이전 페이지 폴트 발생 시간을 빼준 시간
• inter fault time > 타우 : low fault rate
• inter fault time < 타우 : high fault rate => 메모리를 더 할당

 

03-3 WMIN Algorithm
- Fixed Allocation Schema의 MIN 알고리즘처럼 Variable Allocation Schema에서의 최적 알고리즘
- 마찬가지로 미래 상황을 예측할 수 있어야 만 구현할 수 있기 때문에 실현은 불가능하지만 성능 평가의 기준이 됨
- 방법 : 특정 페이지가 시점 (t,t+Δ] 사이에도 다시 참조되는지 확인해서 참조된다면 유지 안된다면 내리는 방식
(괄호 주의 : ()는 포함 안함, []는 포함)
- 특징 : Δ의 크기에 따라 페이지 폴트 횟수가 달라짐 => 마찬가지로 페이지 유지 비용과 페이지 폴트 처리 비용을 고려해서 종합적으로 평가해야 함

최적의 Δ 값은?
- R / U : R은 페이지 폴트 처리비용, U는 페이지 유지 비용
- R > ΔxU : 페이지 폴트 처리비용이 페이지 유지 비용보다 큼
- R < ΔxU : 페이지 폴트 처리비용이 페이지 유지 비용보다 작음

 

04 그 외 고려사항

이외 가상 메모리 관리를 위해 추가적으로 다음의 사항들을 고려할 수 있다.

• Page Size
  • 뭐든 적당한 게 좋다 (다만 최근에는 크기가 점점 커지는 경향은 있다 - 128byte => 4MB)
  • 페이지 사이즈가 작으면? 페이지 수 증가, 관리 테이블 크기 확대, 커널의 관리 오버헤드 증가, 내부 단편화 감소, I/O시간 증가, locality는 향상(계속 읽을 데이터만 들어감), 페이지 폴트 증가(페이지 교체 빈번)
  • 페이지 사이즈가 크면? 페이지 수 감소, 관리 테이블 크기 축소, 커널의 관리 오버헤드 감소, 내부 단편화 크기 확대, I/O시간 감소(메모리에 올려야 하는 페이지의 수가 적으니까), locality 감소(필요한 것 이외의 내용까지 메모리에 올라갈 수 있음), 페이지 폴트 감소
    
    참고로, 하드웨어 발전에 있어 cpu의 발전 속도는 빠른데 반해 메모리의 발전 속도가 느려 페이지 폴트 처리 비용이 증가했다. 따라서 이런 메모리 입출력 병목을 해소하기 위해서는 전체 퍼포먼스를 높일 필요가 있는데, 최근에는 전체 I/O시간을 줄이기 위해서 페이지 크기를 키우는 경향이 있다.
• Program Restructuring
  • 아주 쉽게 표현하면 프로그램의 구조를 바꿔 성능을 개선하는 작업을 의미하는데, 가상 메모리 관리 방법을 배우는 것도 이런 전체적인 구조를 파악한 뒤 성능을 높이기 위한 방법들을 파악함으로써 직접 짜는 프로그램의 성능도 효율적으로 짤 수 있기 때문임.
• TLB reach
  • TLB는 address mapping에서 direct mapping의 시간을 단축하기 위해 사용했던 특별한 하드웨어
  • Translation Lookaside Buffer : 변환할 때 옆을 잠시 쳐다보난(참고하는) 버퍼
  • 여기서 reach는 닿는 범위, 도달하는 정도와 양을 의미
  • TLB reach : TLB를 통해 도달할 수 있는 메모리의 양, entrySize * entryCount = TLB reach
  • TLB reach가 높으면 hit ratio가 증가하는데, 다만 TLB의 크기를 늘리는 것은 비쌈. 따라서 페이지 크기를 늘리거나 다양한 페이지 사이즈를 지원해주는 방식을 생각해볼 수 있음

 

 

**  KOREATECH 무료 OS강의(클릭) 학습 후 나름대로 이해한 뒤 정리한 내용입니다. **

[Course] Operating System (CPA310) - 운영체제 강의