8. 가상 메모리

---

 

 

1. 가상 메모리 (Virtual Memory)

1.1) 가상 메모리의 개념

각 프로세스에게 물리적 메모리(메인 메모리)가 아닌 가상의 논리적 메모리를 제공하기 위해 사용된다.

이를 위해 가상 주소와 실제 주소를 분리해서 사용한다.

• 가상 주소(논리적 주소): 실행 중인 프로세스가 참조하는 주소
• 실제 주소(물리적 주소): 메인 메모리에서 사용하는 주소

 

1.2) 가상 메모리 제공 목적

메인 메모리보다 더 큰 가상 주소 공간을 사용하기 위함이다.

프로그램 전체를 동시에 실행하지 않으므로, 가상 주소 공간의 일부만 메모리에 적재해 실행할 수 있다.

각 프로세스는 연속적인 가상 주소 공간을 사용할 수 있다.

가상 주소 공간 상의 연속적인 주소가 꼭 메인 메모리에서도 연속적일 필요는 없다.

이를 인위적 연속성이라고 부른다.

 

1.3) 가상 메모리를 통해 얻을 수 있는 이익

공간의 제약이 없어지기 때문에 중첩을 작성할 필요도 없어 프로그래밍이 쉬워진다.

메모리 공간이 부족해도 부분 적재가 가능하기 때문에 보다 많은 작업을 실행할 수 있어 프로세서 이용률, 처리율이 향상된다.

 

1.4) 가상 메모리 시스템에서 해결해야 하는 문제점들

논리적 주소를 물리적 주소로 변환하는 동적 주소 변환이 빠르게 이루어져야 한다.

메모리와 디스크 사이의 이동량이 증가하여 디스크 스와핑 공간 확보가 필요하다.

어느 시기에 어느 페이지를 메인 메모리에 적재/복귀할 것인가에 대한 알고리즘을 결정해야 한다.

요구된 페이지가 메인 메모리에 없을 경우 페이지 부재(Page Fault)가 발생하므로, 이를 해결하기 위한 방안이 필요하다.

 

---

 

2. 페이징 (Paging)

페이징은 가상 메모리를 통해 논리적 주소 공간을 구축하고, 실제 메인 메모리에 적재할 데이터들을 관리하는 방법이다.

프로그램의 모든 부분이 동시에 실행되지는 않는다는 특징을 이용한다.

프로세스를 실행하는 데 꼭 필요한 부분만 메인 메모리에 적재하고, 나머지는 디스크에 분산 저장한다.

프로세스 실행 흐름에 따라 필요한 부분(현재 사용해야 하는 부분)만 메인 메모리에 적재한다.

가상 메모리 상에 올라가게 되는 데이터들도 일단은 실존하는 데이터이므로, 어딘가에 저장되어야 한다.

이를 위해 용량이 큰 2차 저장공간 활용한다.

 

---

 

3. 동적 주소 변환 (DAT: Dynamic Address Translation)

가상 메모리 상에서의 논리적 메모리 주소가 연속적일지라도, 메인 메모리 상의 물리적 메모리 주소는 불연속적일 수 있다.

실행 시간에 가상 주소를 실제 주소로 변환하는 매핑 작업이 필요하다. (주소 바인딩 종류 중, 실행 시간 바인딩에 해당함)

주소 매핑에 페이지 테이블 등을 이용한다.

매핑은 가능한 한 빨리 이루어져야 한다.

매핑 속도가 시스템 성능과 가상 메모리 사용 효과를 결정한다.

 

3.1) 페이지 테이블 항목(PTE: Page Table Entry) 구성

페이지 테이블을 구성하는 항목들은 제어 비트와 페이지 프레임 번호, 디스크 주소 등으로 이루어진다.

각 페이지 테이블 항목에는 페이지 프레임 번호를 기록하여, 페이지 번호를 프레임 번호로 변환할 수 있도록 만든다.

페이지 번호는 논리적 메모리 주소에서 사용되며, 프레임 번호는 물리적 메모리 주소에서 사용된다.

 

---

 

4. 요구 페이징 (Demand Paging)

프로세스 시작 시, 디스크에서 메인 메모리로 스와핑 하는 순수 스와핑과 달리, 요구 페이징 기법에서는 실행 중인 프로세스가 요구한 페이지만 메모리에 반입한다.

즉, 사용하지 않는 페이지는 메모리에 적재하지 않는 방법이다.

반입 시간 감소, 기억 공간 절약, 다중 프로그래밍 정도 증가 등의 효과를 기대할 수 있다.

각 페이지가 메인 메모리에 있는 유효한 페이지인지 여부를 표시해야 한다.

페이지 테이블 항목에는 타당/비타당 비트를 추가하여 유효한 페이지인지 구분한다.

• 타당/비타당 비트 값이 1일 경우: 유효 페이지로서 메인 메모리에 있는 페이지
• 타당/비타당 비트 값이 0일 경우: 유효하지 않는 페이지로서 메인 메모리에 없는 페이지
• 논리적 메모리 주소 인덱스: 페이지 테이블 주소 인덱스
• 페이지 테이블에 저장된 프레임 값: 메인 메모리 주소 값
• 타당/비타당 비트: 메인 메모리에 페이지가 적재되어 있는지 여부를 판단하는 비트 값 (1: 적재 || 0: 비적재)

 

Ex) 페이지 테이블 주소 인덱스 0

• 프레임 '4'가 페이지 테이블에 저장되어 있으므로, 메인 메모리 주소 '4'에 값이 존재한다.
• 페이지 테이블 주소 인덱스가 '0'이므로, 논리적 메모리 주소 인덱스 '0'에 해당하는 값인 'A'가 저장되어 있다.
• 페이지 테이블에 프레임 값이 저장되어 있으므로, 페이지 테이블 주소 인덱스 '0'의 타당/비타당 비트 값은 1이다.

 

4.1) 페이지 부재

가상 주소를 물리 주소로 변환하는 요구 페이징 과정에서 해당 페이지 테이블 항목의 타당/비타당 비트가 0일 경우, 페이지 부재가 발생한다.

페이지 부재가 발생하게 되면 페이징을 사용하지 않는 경우보다 유효 액세스 시간이 증가하기 때문에 프로세스 수행 속도가 떨어질 수밖에 없다.

즉, 페이지 부재율을 최대한 낮추는 것이 성능 향상을 결정하는 요인이다.

 

4.2) 페이지 부재 처리 과정

프로세스가 논리적 메모리 상에서 페이지 1에 접근을 시도한다.

해당 논리적 주소를 가지고 페이지 테이블에 접근해 적재 여부를 조사한다.

페이지 테이블 주소 인덱스 1의 타당/비타당 비트를 보면 비타당 상태임을 알 수 있다.

즉, 페이지 부재가 발생하는 상태이므로, 운영체제는 페이지 부재 트랩을 시작한다.

페이지 부재 트랩에 의해 운영체제는 메인 메모리의 빈 공간 1개를 탐색한다.

탐색에 성공하면 보조 기억 장치에 접근해 요구한 페이지를 메인 메모리에 적재한다.

이제 페이지가 메인 메모리 상에 적재되었으므로, 페이지 테이블 주소 인덱스 1의 값을 변경한다.

위 사진에서 메인 메모리 주소 7에 페이지를 적재하였으므로, 페이지 테이블의 프레임 값은 7이 되며, 타당/비타당 비트 값은 1이 된다.

모든 작업을 완료하였으므로, 프로세스를 재시작한다.

 

4.3) 요구 페이징의 성능

페이지 부재율을 최대한 낮추는 것이 가장 중요하다.

페이지 부재율이 높은 경우, 유효 액세스 시간(EAT: Effective Access Time)이 증가하므로, 프로세스 수행 속도가 느려진다.

요구된 페이지의 메모리 접근 시간, 즉, 메모리 액세스 시간을 MAT(Memory Access Time)이라고 부른다.

이때 페이지 부재율, p는 0 이상 1 이하이다.

유효 액세스 시간은 {(1 - p) * 메모리 액세스 시간} + {p * (페이지 부재 처리 시간)}로 계산한다.

• 페이지 부재가 발생하지 않을 경우: 유효 액세스 시간 == 메모리 액세스 시간 (페이지 부재 처리 시간 == 0)
• 페이지 부재가 발생할 경우: 유효 액세스 시간 == 페이지 부재 처리 시간 (메모리 액세스 시간 == 0)

Ex) 메모리 액세스 시간 == 200ns, 페이지 부재 처리 시간 == 8,000,000ns 조건인 경우

• p가 0.001이면, 유효 액세스 시간은 8199.8ns (메모리 액세스 시간의 약 40배)
  
  
• p가 0.0000025보다 작다면, 유효 액세스 시간은 220ns 미만

메모리 액세스 시간과 페이지 부채 처리 시간을 최적화하지 않더라도, 페이지 부재가 발생하는 확률 자체를 낮추면 보다 효과적인 결과를 얻을 수 있음을 보여준다.

 

---

 

5. 페이지 부재와 메모리 프레임 수의 관계

참조 문자열: [1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1]

참조 문자열은 메모리를 참조하는 페이지 번호를 순서대로 나열한 것이다.

프레임 수가 1일 경우, 페이지 부재는 11번 발생한다.

프레임 수가 3일 경우, 페이지 부재는 3번(1, 4, 6) 발생한다.

일반적으로 메모리 프레임 수가 증가하면, 페이지 부재 횟수는 감소한다.

 

---

 

6. 페이지 교체

페이지 부재 시, 해당 페이지를 메모리에 로드해야 한다.

이때 비어있는 프레임이 없는 경우, 메모리에 적재되어 있는 페이지를 교체해야 한다.

교체할 희생자 페이지를 선택할 때는 페이지 부재율을 낮출 수 있도록 적절히 선택해야 한다.

이는 페이지 교체 알고리즘을 통해 판별한다.

페이지 교체 알고리즘은 페이지 부재 횟수를 가능한 줄여야 하며, 구현 부담이 지나치게 크지 않아야 한다.

 

6.1) 선입 선출 페이지 교체 알고리즘 (FIFO: First-In First-Out)

가장 먼저 메모리에 로드된(가장 오래 메인 메모리에 적재되어 있었던) 페이지를 교체한다.

메모리에 있는 모든 페이지를 선입선출(FIFO) 방식인 큐로 관리한다.

큐의 크기는 사용 가능한 메모리 프레임 수를 의미한다. (메인 메모리에 올라가 있는 페이지들의 정보가 기록됨)

큐의 가장 앞(Front: 헤드)에 있는 페이지를 먼저 교체한다.

새로 로드된 페이지를 FIFO 큐의 맨 뒤에 삽입한다.

가장 구현하기 쉬운 알고리즘이다.

곧 참조될 페이지를 교체할 수 있으므로, 최적의 페이지 부재율을 얻기 어렵다.

아래와 같이 Belady's Anomaly(할당된 프레임의 수가 증가해도, 페이지 부재율이 상승하는 현상)가 발생할 수 있다.

선입 선출 알고리즘에서 참조 문자열이 다음과 같을 때, 프레임 수가 3인 경우보다 4인 경우에 페이지 부재가 더 많은 이상 현상이 나타난다.

 

6.2) 최적 알고리즘 (OPT: Optimal)

앞으로 가장 오랜 기간 동안 사용하지 않을 페이지를 교체한다.

페이지 부재율이 가장 낮은 이상적인 알고리즘이다.

미래를 예측해야 하므로 실제로 구현하기는 매우 어렵다.

알고리즘 비교 연구를 위해 주로 사용된다.

 

6.3) LRU(Least Recently Used) 알고리즘

가장 오랫동안 사용하지 않은 페이지를 교체한다.

과거의 데이터를 기반으로 미래를 예측함으로써, 최적 알고리즘에 근접하고자 하는 알고리즘이다.

시간적 지연성(Temporal Locality)을 기반으로 동작하는 알고리즘이다.

즉, 가장 오랫동안 사용하지 않은 페이지는 앞으로도 오랫동안 사용하지 않을 것이라는 가정 하에 동작한다.

가장 오랫동안 사용하지 않은 페이지를 정확히 알아내기 위해 페이지 참조 순서를 기록하는 알고리즘이 추가로 필요하다.

LRU 알고리즘을 구현하는 방법으로든 다음과 같이 2가지가 있다.

• 계수기(Counter)를 이용한 LRU 알고리즘
• 스택(Stack)을 이용한 LRU 알고리즘

LRU 알고리즘은 최적 알고리즘에 가까운 성능을 낼 수 있다.

정확한 참조 순서를 기록해야 하는 부담이 있다.

하드웨어 지원이 필요하다.

페이지를 참조할 때마다 참조 순서 관련 기록을 갱신해야 하므로, 실행 시간 부담이 발생한다.

과거 기록이 미래를 정확하게 반영하지는 않으므로, 과거 기록(참조 순서)에 의존하기보다는 대략적인 참조 순서를 반영해 교체 페이지를 선정하는 것이 바람직하다.

 

6.4) 계수기(counter)를 이용한 LRU 알고리즘

페이지 참조 시각을 기록해두고, 참조 시각이 가장 빠른 페이지를 교체한다.

페이지 교체가 필요할 때는 계수기(counter) 필드 값이 최소인 페이지를 희생자 페이지로 선택한다.

참조 시각을 기록하기 위해서는 다음 2가지가 필요하다.

• 프로세서에 논리 클록을 둔다.
• 페이지 테이블 각 항목에 계수기(counter) 필드를 둔다.

페이지에 대한 참조가 있을 때마다 다음 2가지 작업이 필요하다.

• 프로세서의 논리 클록 값을 증가시킨다.
• 해당 페이지의 계수기(counter) 필드 값을 논리 클록 값으로 업데이트한다.

페이지 참조 시마다 계수기의 값을 관리해야 하므로, 실행 시간 부담이 존재한다.

페이지 참조 시마다, 계수기(counter) 필드 값을 갱신해야 한다.

페이지 교체 시에는, 계수기(counter) 필드 값이 최소인 것을 검색해야 한다.

 

6.5) 스택을 이용한 LRU 알고리즘

참조 순서를 결정하기 위해 페이지 번호를 스택에 넣어 관리한다.

페이지가 참조될 때마다 페이지 번호를 스택의 top로 옮긴다.

페이지 교체가 필요할 때는 스택 bottom에 있는 페이지가 가장 오래전에 참조된 페이지이므로, 이를 희생자 페이지로 선택한다.

교체되는 페이지 번호는 스택에서 삭제된다.

페이지 참조 시마다 스택의 페이지 번호를 top으로 옮겨야 하므로, 스택 삭제/삽입 연산이 필요하다.

 

6.6) LRU 근사 페이지 교체 알고리즘

LRU 근사 페이지 교체 알고리즘은 참조 비트를 사용하여 LRU와 비슷한 효과를 얻는 알고리즘이다.

각 페이지마다 참조 비트(Reference Bit)를 두고, 이를 조사해 최근에 사용되었는가를 확인한다.

페이지 참조 시, 그 페이지의 참조 비트를 1로 변경한다.

정확한 참조 순서를 유지하는 대신, 대략적인 순서를 알 수 있게 만든다.

LRU 알고리즘에 비해 구현 부담은 크게 줄이지만, 이에 근접한 성능을 얻을 수 있다.

 

6.7) 부가된 참조 비트 알고리즘

각 페이지에 8bit(1byte) 정보를 두어 일정한 기간 내에 참조되었는지를 알 수 있게 한다.

8bit Shift Register를 사용하여 부분 순서 정보를 얻어온다.

각 페이지에 대한 참조 비트(0 or 1) 값을 최상위 bit에 넣고, 일정 시간마다 1bit씩 오른쪽으로 Shift

8bit Shift Register는 최근 8번의 기간 동안 페이지 사용의 기록 정보를 유지하므로, 이 값이 최소인 것을 고체 대상으로 한다.

위 사진에서 5단계가 기준이라면, 페이지 5 > 페이지 3 > 페이지 4 > 페이지 2 > 페이지 1 순으로 교체된다.

 

6.8) Clock 알고리즘 (Second Chance 알고리즘)

FIFO 알고리즘을 기반으로 하되, 각 프레임의 참조 여부를 나타내는 참조 비트를 추가한다.

참조 비트는 페이지가 메모리 프레임에 처음 로드될 때 1로 설정한 후, 참조될 때마다 다시 1로 설정한다.

페이지 교체가 필요할 때, FIFO 원칙에 따라 원형 큐에서 가장 오래전에 로드된 프레임을 검사한다.

참조 비트가 0이면 즉시 교체된다.

참조 비트가 1이면, 교체하는 대신 값을 0으로 바꾸고, 원형 큐의 다음 프레임을 검사한다.

1번 돌 때 참조 비트 1인 페이지는 참조 비트 값을 0으로 변경, 참조 비트가 0인 페이지는 희생된다.

즉, 2번째 기회(Second Chance)를 제공하고, 다음 검사까지 교체 대상이 되지 않는다.

메인 메모리의 페이지 프레임이 m개인 경우, 원형 큐의 원소 수는 m개다.

새로운 페이지 420을 프레임에 로드하기 위해 교체할 페이지를 찾는 과정은 위 그림과 같다.

 

6.9) NUR(Not Used Recently) 알고리즘

페이지마다 참조 비트 외에 수정 비트를 추가로 둔다.

• 참조 비트: 최근에 페이지를 참조했는지 여부를 나타낸다.
• 수정 비트: 페이지를 메모리에 로드한 후, 수정되었는지 여부를 나타낸다.

수정되지 않은 페이지를 교체할 경우, 교체되는 페이지를 디스크에 수록(Swap out)할 필요가 없다.

즉, 페이지의 변경 사항을 디스크 상에 반영할 필요가 없기 때문에 메인 메모리에서 삭제만 하면 된다.

페이지 부재(Page Fault) 처리 시간을 줄일 수 있다.

교체 대상 페이지 우선순위는 다음과 같이 판별한다.

• 1순위 = (0, 0): 최근에 참조하지 않았고, 수정하지 않음
• 2순위 = (0, 1): 최근에 참조하지 않았으나, 수정함
• 3순위 = (1, 0): 최근에 참조하였으나, 수정하지 않음
• 4순위 = (1, 1): 최근에 참조하였으며, 수정함

 

6.10) 계수 기반 페이지 교체 알고리즘

각 페이지에 참조 횟수를 세는 카운터를 두고, 참조 횟수를 기반으로 교체할 페이지를 선택한다.

LFU, MFU 알고리즘이 있으나, 일반적으로 사용하지 않는다.

구현 비용이 많이 들고, 최적 알고리즘에 비해 성능이 낮기 때문이다.

 

6.11) LFU 알고리즘

가장 적게 사용된 페이지를 교체한다.

각 페이지마다 참조 횟수를 나타내는 카운터를 두고, 카운터 값이 최소인 페이지를 교체한다.

초기에 많이 사용된 페이지는 큰 카운터 값을 가지므로, 더 이상 필요하지 않음에도 메모리에 남아 있는 문제점이 있다.

 

6.12) MFU 알고리즘

가장 많이 사용된 페이지를 교체한다.

각 페이지마다 참조 횟수를 나타내는 카운터를 두고, 카운터 값이 최대인 페이지를 교체한다.

카운터 값이 작은 페이지는 방금 로드되어 아직 사용되지 않아 앞으로 사용할 확률이 높다고 보고 교체하지 않는다.

거의 사용하지 않는 페이지가 메모리에 계속 남게 되는 문제점이 있다.

 

---

 

11. 페이지 교체 알고리즘 비교

분석에 사용된 페이지 크기는 256 word이며, 프레임 수를 6, 8, 10, 12, 14개로 변경하며 실행했다.

적은 수의 프레임을 사용할 경우, 페이지 부재 수 차이가 크게 나타났다.

 

---

 

12. 프레임 할당 알고리즘

12.1) 최소 프레임 수

한 프로세스 당 최소 프레임 수는 각 컴퓨터의 명령어 구조에 의해 정의된다.

1개의 명령어 실행을 위해 명령어가 참조하는 모든 페이지를 수용할 수 있는 충분한 프레임이 필요하다.

 

12.2) 다중 프로그래밍 환경의 프레임 할당

메인 메모리에 2개 이상의 프로세스가 존재하므로, 각 프로세스에 얼마만큼의 프레임을 할당할 것인지에 관한 문제가 발생한다.

프레임 할당 방법에는 균일 할당과 비례 할당이 있다.

 

12.3) 균일 할당

프레임 m개를 프로세스 n개에 할당할 때, 각 프로세스에 똑같이 m/n개씩 할당한다. 

각 프로세스의 메모리 요구량이 서로 다름에도 불구하고 같은 수의 프레임을 할당하므로 남으면 페이지 프레임 낭비, 모자라면 페이지 부재율 증가 문제를 일으킬 수 있다.

 

12.4) 비례 할당

사용 가능한 메모리를 각 프로세스가 필요로 하는 메모리 양 또는 프로세스의 크기에 비례하여 할당한다. 

운영체제가 프로세스 메모리 할당 관련 정보를 알아야 한다.

 

---

 

13. 메모리를 관리하는 프로세스 적재 정책

13.1) 스레싱 (Thrashing)

지나친 페이지 부재로 페이지 교환이 계속 일어나는 현상.

프로세서가 작업 수행에 보내는 시간보다, 페이지 교환에 보내는 시간이 더 길어지면, 프로세서 이용률이 급격히 감소한다.

운영체제는 프로세서 이용률이 떨어지면, 새로운 프로세스를 도입해 다중 프로그래밍 정도를 높인다.

다중 프로그래밍 정도가 어느 이상이 되면, 각 프로세스가 할당받을 수 있는 프레임이 부족해져 페이지 부재 빈도가 증가한다.

페이지 교환이 계속 일어나기 때문에 프로세서가 작업을 수행하지 못해 이용률이 급격히 감소한다.

이를 해결하기 위해서는 다중 프로그래밍 정도를 낮추어 각 프로세스가 충분한 프레임을 확보하도록 만들면 된다.

 

13.2) 지역성

프레임 할당은 지역성을 기반으로 이루어진다.

즉, 최근에 사용했던 메모리 근처는 다시 접근할 가능성이 높다는 것이다.

 

13.3) 시간 지역성

현재 참조하는 주소는 가까운 미래에 다시 참조될 가능성이 높다. 

반복문, 함수 호출, 스택 등이 이에 해당한다

 

13.4) 공간 지역성

프로세스가 어떤 주소를 참조하면 근처 주소도 참조될 가능성이 높다. 

배열 순차 검색, 순차적 코드 실행, 변수 선언 등이 이에 해당한다.

 

13.5) 프레임 할당 기준

가능한 높은 다중 프로그래밍 정도를 유지하면서 스레싱을 방지하려면 지역성을 바탕으로 하여 각 프로세스에게 적절한 개수의 페이지 프레임을 할당해야 한다.

프레임 할당 기법으로는 작업 집합 모델과 페이지 부재 빈도가 있다.

 

13.6) 작업 집합 모델 (Working Set model)

프로그램 수행 과정을 지역성 개념으로 설명하고자 데닝이 고안했다.

프로세스가 자주 참조하는 페이지들의 집합(작업 집합)을 메모리에 유지, 페이지 부재를 줄이는 방법이다.

프로세스의 작업 집합(w, t) == 시간 (t-w)부터 t까지의 프로세스 시간 간격에 참조한 페이지들의 집합

• t: 현재 프로세스 시간
• w: Working Set Window 크기

Working Set Window의 크기 선택에 따라 작업 집합 모델의 정확성이 달라진다.

• Working Set Window 값이 너무 작으면 작업 집합을 충족할 수 없다.
• Working Set Window 값이 너무 크면 전체 프로세스가 포함되므로, 의미가 사라진다.

프로세스가 수행되는 동안 작업 집합은 위와 같이 계속 변화한다.

작업 집합이 가장 커지는 시기를 과도기, 작업 집합 크기 변동이 완만한 시기를 안정기라고 부른다.

작업 집합 모델을 사용하면 다중 프로그래밍 정도를 최대화하면서 스레싱을 방지할 수 있다.

Working Set Model의 기본 개념은 많은 OS에서 사용 중이다.

Working Set이 나타내는 과거의 참조가 미래의 참조를 항상 보장하지는 않는다.

메모리를 참조할 때마다, Working Set을 조절해야 하므로, 실행 시간 부담이 크다.

각 프로세스에 대한 Working Set을 모두 측정한다는 것은 현실적으로 불가능하다.

작업 집합 크기가 10인 경우, 페이지 참조 문자열 10개 중에 작업 집합에 포함될 페이지가 결정된다.

t1동안 WS에 들어가는 페이지는 {2, 1, 5, 7}이다.

시스템 내의 프로세스 i에 대한 working set size를 Wss(i)라고 할 때, 이를 모두 더하면 전체 요구 프레임 수 D를 구할 수 있다.

전체 요구 프레임 수 D가 메인 메모리 전체 프레임 수 m보다 더 크면, 스레싱이 발생한다.

이 경우, 다중 프로그래밍 정도를 낮춰서 각 프로세스에 working set 크기만큼의 프레임을 할당해줄 수 있게 해줘야 한다.

 

13.7) 페이지 부재 빈도 (PFF: Page Fault Frequency)

페이지 부재 빈도를 측정해서 스레싱을 예방하는 방법이다.

페이지 부재율의 상한과 하한을 두고, 각 프로세스의 페이지 부재율이 범위 내에 들도록 프레임 수를 조절한다.

• 상한보다 높은 페이지 부재율이 발생하면, 프레임 수를 증가시켜 페이지 부재율을 상한 값 아래로 조절한다.
• 하한보다 낮은 페이지 부재율이 발생하면, 프레임 수를 감소시켜 페이지 부재율을 하한 값 위로 조절한다.

페이지 부재 빈도는 페이지 부재가 발생할 때마다 조절해야 하므로, 메모리에 참조할 때마다 실행해야 하는 작업 집합 모델(Working Set Model) 보다 실행 시간 부담이 적다.

각 프로세스에게 적절한 수의 프레임을 할당해주기 위해서는 다중 프로그래밍 정도 조절이 필요할 수 있다.

 

---

 

14. 메모리 관리와 관련된 이슈

14.1) 페이지 교체 범위

운영체제는 빈 프레임 리스트를 유지한다.

빈 프레임 리스트가 비었을 때, 프레임을 요청하면 운영체제는 페이지 교체 알고리즘으로 페이지 1개를 선택에 교체한다.

 

14.2) 전역 교체

페이지 교체 범위를 모든 프로세스로 확대하여 프로세스가 교체할 프레임을 다른 프로세스에서도 찾을 수 있다.

대기 프로세스가 점유한 메모리를 다른 프로세스가 사용할 수 있다.

프로세스당 필요한 할당(프로세스의 작업 집합)을 추측할 수 있다.

한 프로세스의 페이지 부재를 처리하려고 다른 프로세스의 페이지를 제거할 수 있어서 각 프로세스의 페이지 부재 비율 조절이 불가능하다.

한 프로세스의 실행 속도가 다른 프로세스의 영향으로 늦거나 빠를 수 있다.

개별 프로세스의 동작보다는 시스템 전반에 중점을 두므로, 대형 시스템에 사용된다.

 

14.3) 지역 교체

각 프로세스가 자신에게 할당된 프레임들 중에서만 교체할 페이지를 선택한다.

각 프로세스에 할당된 프레임 수가 페이지 교체로 인해 변하지 않는다.

프로세스의 상대적인 중요도에 따라 프레임 할당을 조정해 성능을 향상한다.

각 프로세스가 독립적으로 자신의 페이지 부재 비율을 제어할 수 있다.

다른 프로세스의 영향을 받지 않고, 일관된 성능을 얻을 수 있다.

 

14.4) 프리 페이징 (Prepaging)

참조할 것으로 예상되는 페이지들을 미리 한꺼번에 메모리에 로드한다.

연속된 페이지를 한 번에 로드하므로, 입출력을 여러 번 수행하는 요구 페이징보다 성능이 좋다.

미리 가져올 페이지와 개수를 결정하는 경험적 알고리즘이 중요하다.

프리 페이징에 의해 메모리로 로드된 페이지 중에서 상당수는 사용되지 않을 수 있다.

프로세스가 사용할 페이지를 잘못 예측할 경우, 요구 페이징보다 성능이 낮을 수 있다.

예측 페이징이라고도 한다.

 

14.5) 페이지 크기

페이징 기법에서 페이지 크기는 하드웨어 디자인에서 매우 중요한 요소이다.

프로세서 속도 증가, 메모리 용량 증가, 디스크 속도 증가로 인해 오늘날 페이지 크기는 증가했다.

많은 아키텍처에서 다중 페이지 크기를 지원한다.

페이지 크기가 작을 경우, 내부 단편화가 감소하고 프로세스들이 더 작고 타이트한 작업 집합 확립이 가능하므로 다른 프로세스들이 더 많은 메모리 공간을 활용할 수 있다.

페이지 크기가 큰 경우, 페이지 테이블 크기, 디스크 입출력 횟수, 페이지 부재율이 감소한다.

 

14.6) 역 페이지 테이블 (Inverted Page Table)

페이지 테이블 크기 증가 문제를 해결하기 위한 방법이다.

각 프로세스마다 1개의 페이지 테이블을 두는 대신, 시스템 전체에 1개의 페이지 테이블을 둔다.

메인 메모리의 각 페이지 프레임 당 1개의 페이지 테이블 항목(PTE: Page Table Entry)이 존재한다.

전통적인 페이지 테이블과 비교해 역으로 정보를 유지한다.

• 역 페이지 테이블의 인덱스: 페이지 프레임 번호
• 역 페이지 테이블의 각 항목에 저장된 내용: 페이지 번호

시스템 전체에 1개의 페이지 테이블을 두기 때문에 논리적 주소에는 프로세스 id 값을 배정해야 한다.

역 페이지 테이블에서 <프로세스 id, 페이지 번호>를 검색해서 찾은 인덱스가 프레임 번호에 해당한다.

<프로세스 id, 페이지 번호> 검색 시간문제를 해결해야 한다.

페이지 번호를 검색해서 프레임 번호를 얻는 시간을 줄이기 위해 해싱을 이용할 수 있다.

해싱이란, 해시 함수에 키값을 대입해 계산한 결과로 원하는 값에 바로 접근하는 방법을 말한다.

해싱을 이용하기 위해서는 해시 함수가 사용되므로, 아래 사진과 같이 구조가 일부 변경된다.

 

---

 

---

수고하셨습니다!

---