9)가상 메모리 관리

1. 요구 페이징

사용자가 요청할 때 해당 페이지를 메모리로 가져오는 것을 말합니다.

 

프로세스의 일부만 메모리로 가져오는 이유는 크게 두가지가 있습니다.

• 메모리를 효율적으로 관리하기 위해서입니다. 메모리가 꽉 차면 관리하기 어려우므로 가급적 적은 양의 프로세스만 유지합니다.
• 응답 속도를 향상하기 위해서입니다. 용량이 큰 프로세스를 전부 메모리로 가져와 실행하면 응답이 늦어질 수 있으므로 필요한 모듈만 올려 실행합니다.

예를들어 포토샵 같은 경우 피부 보정, 노이즈 제거 같은 외부 필터는 포토샵 실행시에는 메모리에 가져오지 않지만

사용자가 외부 필터를 요구하면 해당 모듈을 메모리에 올립니다.

 

요구 페이징을 사용하면 다음과 같은 장정이 있습니다.

• 메모리의 절약
• 메모리의 효율적 관리
• 프로세스의 응답 속도 향상
• 등등

미리 가져오기

요구 페이징과 반대로 앞으로 필요할 것이라고 예상되는 페이지를 미리 가져오는 방식입니다.
미리 가져오기의 대표적인 예로 캐시가 있습니다. 캐시는 앞으로 필요할 것이라고 예상되는 부분을 고속의 캐시 메모리에 가져다놓음으로써 시스템의 성능을 향상시킵니다. 그러나 미리 가져온 데이터가 쓸모없을 경우 피해가 매우 큽니다.

따라서 현대의 운영체제는 요구 페이징을 기본으로 사용하고 있습니다.

 

순수한 스와핑과 게으른 스와퍼

순수한 스와핑 : 프로세스를 구성하는 모든 페이지를 메모리에 올리는것
게으른 스와퍼 : 사용자가 요구 할 때 메모리에 올리는 것

 

2. 페이지 테이블 엔트리의 플래그 비트

 

페이지 테이블 엔트리는 페이지 테이블의 한 행을 말합니다.

페이지 번호

a

m

v

r

w

x

프레임 번호

 

• 접근 비트 : 페이지가 메모리에 올라온 후 사용한 적이 있는지 알려주는 비트 입니다.
  해당 메모리에 읽기나 실행 작업을 했다면 접근 비트가 1이 됩니다.
• 변경 비트 : 페이지가 메모리에 올라온 후 데이터의 변경이 있었는지 알려주는 비트입니다.
  해당 메모리에 쓰기나 추가 작업을 했다면 변경 비트가 1이 됩니다.
• 유효 비트 : 페이지가 실제 메모리에 있는지를 나타내는 비트입니다.
• 읽기, 쓰기, 실행 비트 : 페이지에 대한 읽기, 쓰기, 실행 권한을 나타내는 비트입니다.
  읽기 권한이 없는 프로세스가 읽으려고 하거나 쓰기 권한이 없는 프로세스가 쓰려고 할 때 접근을 차단하는데 사용합니다. 3가지를 합쳐서 접근 권한 비트(rights bit) 라고 합니다.

접근 비트와 변경 비트는 페이지가 메모리에 올라온 후 어떤 작업이 있었는지 알려주는 역할을 합니다.

두 비트는 메모리가 꽉 차서 어떤 페이지를 스왑 영역으로 옮겨야 할지 선택할 때 사용합니다.(NUR 방식)

 

3. 페이지 부재

프로세스가 페이지를 요청했을 때 그 페이지가 메모리에 없는 상황을 말합니다.

 

페이지 부재가 발생했을 때 빈 프레임이 없다면 메모리에 있는 프레임 중 하나를 스왑영역으로 보내야 합니다.

이때 어떤 페이지를 스왑 영역으로 보내야 할지 결정하는 알고리즘을 페이지 교체 알고리즘 이라고 합니다.

페이지 교체 알고리즘에 의해 스왑 영역으로 보낼 페이지를 대상 페이지 라고 합니다.

 

4. 지역성

기억장치에 접근하는 패턴이 메모리 전체에 고루 분포되는 것이 아니라 특정 영역에 집중되는 성질을 말합니다.

페이지 교체 알고리즘이 쫓아낼 페이지를 찾을 때는 지역성을 바탕으로 합니다.
지역성은 크게 공간의 지역성, 시간의 지역성, 순차적 지역성으로 나뉩니다.

 

• 공간의 지역성 : 현재 위치에서 가까운 데이터에 접근할 확률이 먼 거리에 있는 데이터에 접근할 확률보다 높다는것을 의미합니다.
• 시간의 지역성 : 현재를 기준으로 가장 가까운 시간에 접근한 데이터가 더 먼 시간에 접근한 데이터보다 사용될 확률이 높다는 것입니다.
• 순차적 지역성 : 여러 작업이 순서대로 진행되는 경향이 있다는 것을 의미합니다.

5. 페이지 교체 알고리즘

스왑 영역으로 보낼 페이지를 결정하는 알고리즘으로, 메모리에서 앞으로 사용할 가능성이 적은 페이지를 대상 페이지로 선정하여 페이지 부재를 줄이고 시스템의 성능을 향상시킵니다.

 

종류	알고리즘	특징
간단한 알고리즘	무작위	무작위로 대상 페이지를 선정하여 스왑 영역으로 보냅니다.
	FIFO	먼저 올라온 페이지를 스왑영역으로 보냅니다.(선입선출)
이론적 알고리즘	최적	미래의 접근 패턴을 보고 대상 페이지를 선정하여 스왑영역으로 보냅니다.
최적 근접 알고리즘	LRU	시간적으로 멀티 떨어진 페이지를 스왑 영역으로 보냅니다.
	LFU	사용 빈도가 적은 페이지를 스왑 영역으로 보냅니다.
	NUR	최근에 사용한 적이 없는 페이지를 스왑 영역으로 보냅니다.
	FIFO 변형	FIFO 알고리즘을 변형하여 성능을 높입니다.

 

최적 페이지 교체 알고리즘은 미래의 메모리 접근 패턴을 살펴보고 대상 페이지를 선정하므로 성능이 가장 좋지만 사실상 구현이 불가능 합니다.

 

페이지 교체 알고리즘의 성능 평가 기준

• 페이지 부재 횟수(작을수록 좋음)
• 페이지 성공 횟수(요청한 페이지가 물리메모리에 있음)
• 페이지 요청 후 실제로 작업에 들어갈 때까지의 평균 대기시간
• 전체 작업에 걸리는 시간

 

1. 무작위 페이지 교체 알고리즘 (성능이 좋지 않아 거의 사용하지 않습니다.)
   
   스왑 영역으로 쫓아낼 대상 페이지를 특별한 로직 없이 무작위로 선정합니다. 가장 간단하게 구현할 수 있는 방식이고 지역성을 고려하지 않아 자주 사용하는 페이지가 대상으로 성정 되기도 합니다. 
   
   
2. FIFO 페이지 교체 알고리즘
   
   선입 선출을 의미하며 큐를 이용해 구현합니다. 페이지 부재가 일어난 경우 가장 먼저 들어온 페이지를 스왑 영역으로 보냅니다.무조건 오래된 페이지를 대상 페이지로 선정하기 때문에 성능이 떨어지는데 이러한 문제점을 개선한 것이 2차 기회 페이지 교체 알고리즘 입니다.
   
   
3. 최적 페이지 교체 알고리즘
   
   앞으로 사용하지 않을 페이지를 스왑 영역으로 옮깁니다. 메모리가 앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정시점부터 사용 시점까지 가장 멀리 있는 페이지를 대상 페이지로 선정합니다.
   
   미래의 메모리 접근 패턴을 보고 대상 페이지를 결정하기 때문에 성능이 좋지만
   미래의 접근 패턴을 안다는 것이 불가능 하여 실제로는 구현할 수 없습니다.
   
   
4. LRU 페이지 교체 알고리즘
   
   페이지에 접근한 시간을 기준으로 대상 페이지를 선정합니다.
   현재와 메모리에 접근한 시간차가 가장 큰 페이지를 스왑영역으로 옮깁니다.
   
   LRU 페이지 교체 알고리즘에는 다음과 같은 구현방법이 있습니다.
   - 페이지 접근 시간에 기반한 구현
   - 카운터에 기반한 구현
   - 참조 비트 시프트 방식
   
   LRU 페이지 교체 알고리즘의 단점은 접근 시간이나 참조 비트를 유지하기 위한 메모리가 추가로 필요하기 때문에 낭비되는 메모리 공간이 많습니다.
   
   
5. LFU 페이지 교체 알고리즘
   
   페이지가 몇번 사용 되었는지를 기준으로 대상 페이지를 선정합니다. 다시 말해 현재 프레임에 있는 페이지마다 그 동안 사용된 횟수를 세어 횟수가 가장 적은 페이지를 스왑 영역으로 옮깁니다.
   
   LRU 페이지 교체 알고리즘의 단점은 LRU 페이지 교체 알고리즘과 마찬가지로 낭비되는 메모리 공간이 많다는 것입니다. 페이지 접근 횟수(빈도)를 표시하는 데 추가 공간이 필요하므로 그만큼 메모리가 낭비됩니다.
6. NUR 페이지 교체 알고리즘
   
   LRU, LFU 페이지 교체 알고리즘과 비슷한 성능이지만 공간 낭비 문제를 해결한 알고리즘 입니다.
   추가 비트 2개 참조 비트 / 변경 비트 를 사용하여 미래를 추정합니다.
   
   참조 비트 : 페이지에 접근(read / execute)하면 1이 됩니다.
   변경 비트 : 페이지가 변경(write / append)되면 1이 됩니다.
   
   모든 페이지의 초기 상태는 (0, 0) 입니다.
   이 상태에서 페이지에 읽기 또는 실행 같은 '접근'이 발생하면 (1, 0)으로 바뀝니다.
   만약 쓰기 또는 추가 같은 '변경'이 일어나면 (0, 1)이 됩니다.
   접근과 변경 두가지 연산이 다 발생하면 (1, 1) 이 됩니다.
   
   교체 대상 페이지 선정하는 우선 순위는
   (0, 0) -> (0, 1) -> (1, 0) -> (1, 1) 순서 입니다.
   
   만약 모든 페이지의 비트가 (1, 1) 이 되면 모든 페이지 비트를 (0, 0,)으로 초기화 합니다.
   
   NUR 페이지 교체 알고리즘은 2bit만 추가하여 다른 알고리즘과 유사한 성능을 낼 뿐만 아니라 쉽게 구현할 수 있다는 장점 때문에 가장 많이 사용되고 있습니다.
   
   
7. FIFO 변형 알고리즘
   
   FIFO 알고리즘을 개선한 알고리즘으로 2차 기회 페이지 교체 알고리즘과 시계 알고리즘이 있습니다.
   
   - 2차 기회 페이지 교체 알고리즘
   큐를 사용하고 특정 페이지에 접근하여 페이지 부재 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동하여 대상 페이지에서 제외한다는 것입니다. 다시 말해 성공한 페이지를 큐의 맨 뒤로 옮김으로써 기회를 한 번 더 줍니다.
   
   LRU, LFU, NUR 페이지 교체 알고리즘보다 성능이 약간 낮고 FIFO 페이지 교체 알고리즘보다는 약간 높습니다.
   
   단점
       - 큐를 유지하는 비용이 높습니다.
       - 페이지가 성공하면 큐의 중간에 있는 값을 뒤로 이동하는 작업이 추가됩니다.
   
   - 시계 알고리즘
   원형 큐를 사용합니다. 포인터가 큐의 바닥으로 내려가면 다시 큐의 처음을 가리키게 됩니다.
   각 페이지에 참조 비트가 하나씩 추가됩니다. 참조 비트의 초깃값은 0이며, 메모리에 있는 페이지를 성공적으로 참조하면 0에서 1로 변경됩니다.
   만약 포인터가 가리키는 페이지의 참조 비트가 0이라면 스왑영역으로 쫓아내고 1이라면 건너뛰고 건너 뛴 참조비트를 0으로 바꿔놓습니다.
   
   시계 알고리즘은 대상 포인터와 각 페이지당 참조 비트 하나만 추가하면 되기 때문에 NUR페이지 교체 알고리즘보다 추가 공간이 적게 들지만 알고리즘이 복잡하고 계산량이 많다는 것이 단점입니다.

6. 스레싱

하드 디스크의 입출력이 너무 많아져서 잦은 페이지 부재로 작업이 멈춘 것 같은 상태를 말합니다.

 

멀티 프로그래밍 정도 -> 동시에 실행하는 프로그램의 수

 

멀티 프로그래밍 정도가 너무 높으면 스레싱이 발생합니다.

 

스레싱 발생 지점 (threshing point)

메모리가 꽉차면 CPU가 작업하는 시간보다 스왑영역으로 페이지를 보내고 새로운 페이지를 메모리에 가져오는 작업이 많아져 CPU가 작업할 수 없는 상태에 이르는 지점을 뜻합니다.

 

7. 프레임 할당 방식

• 정적 할당 : 프로세스 실행 초기에 프레임을 나누어준 후 그 크기를 고정하는 방식입니다.
  
      - 균등 할당 : 프로세스의 크기와 상관없이 사용 가능한 프레임을 모든 프로세스에 동일하게 할당합니다.
      - 비례 할당 : 프로세스의 크기에 비례하여 프레임을 할당하는 방식입니다.
      
      - 문제점 : 프로세스가 실행 중에 필요로 하는 프레임을 유동적으로 반영하지 못합니다. 사용하지 않을 메모리를 처음부터 미리 확보하여 공간을 낭비한다는 문제가 있습니다.
  
  
• 동적 할당 : 프로세스를 싱행하는 중에 프레임을 나누어주기도 하고 회수하기도 하는 방식입니다.
  
  - 작업집합 모델 : 가장 최근에 접근한 프레임이 이후에도 또 참조될 가능성이 높다고 가정합니다. 작업 집합과  작업 집합 윈도우를 사용해서 작업 집합 윈도우가 끝나는 시점에서 가장 가까운 페이지를 작업 집합에 넣습니다.
  
      - 페이지 부재 빈도 활용 : 페이지 부재 횟수를 기록하여 페이지 부재 비율을 계산하는 방식입니다. 상한선과 하한선을 설정하여 상한선을 초과하면 프레임을 추가로 늘리고 하한선 밑으로 내려가면 할당한 프레임을 회수합니다.