가상 메모리 관리 (1)

이번 단원은 '메모리가 꽉 차있을 때 프로그램을 올려야 할 때에 어떤 페이지를 스왑영역으로 옮겨야 할까' 에 대한 여러 알고리즘을 배웠다.

 

처음에는 '어떠한 조건이 있으면 조건을 만족하기 어려운 페이지가 아사현상에 빠지지않을까?' 하고 생각했었는데 다시 생각해보니 서로 완전히 다른 영역이였다.

 

그리고 LRU 페이지 교체 알고리즘과 2차 기회 페이지 교체 알고리즘이 되게 유사하다고 생각이 든다. 둘 다 시간의 흐름을 기반으로 하고 있지만 다시 사용한 페이지라면 시간의 흐름을 초기화 한다는 성질 때문인데 이건 다시 공부하며 확실히 알고 넘어가야겠다.

 

마지막으로 페이지 교체 알고리즘과 캐시메모리가 사용하는 알고리즘이 같지않을까 하는 궁금증도 생겼다. 사용자가 쓰지 않을것 같은 데이터와 사용할것 같은 데이터를 구하는 알고리즘인데 서로 반대되는 성질을 가져 같은 알고리즘을 사용할 것 같다는 생각을 했다.

---

1. 요구 페이징

 

1-1 요구 페이징의 개요

 

프로세스를 실행할 때에 나누어 메모리에 올리는 이유

→ 메모리를 충분히 비워놓음으로서 컴퓨터 속도의 저하를 막고 메모리의 관리도 편하다.

• 메모리를 효율적으로 관리하기 위함
• 응답 속도를 향상하기 위함

→ 프로세스 전체를 메모리에 올리는 것 : 순수한 스와핑

사용자가 요구할 때 필요한 부분을 메모리에 올리는 것 : 게으른 스와핑 

 

1-2 페이지 테이블 엔트리의 구조

 

1. 프레임 번호 : 해당 페이지가 어느 프레임에 있는지 알려주는 자료구조

 

2. 플래그 비트 

• 접근비트(access bit) : 페이지가 메모리에 올라온 후 사용한적이 있는지 알려주는 비트
• 변경비트(modified bit) : 페이지가 메모리에 올라온 후 데이터의 변경이 있었는지 알려주는 비트
• 유효비트 (valid bit) : 페이지가 물리/가상 메모리중에 어디에 있는지 알려주는 비트
• 읽기/쓰기/실행비트 : 읽기/쓰기/실행 권한을 나타내는 비트

 

1-3 페이지 부재

 

원하는 페이지가 물리 메모리에 없다면 (유효비트가 1이라면) 페이지 부재라고 한다. 

 

페이지 부재가 발생했을 때에 해당 페이지를 물리메모리로 가져와야하고 이때엔 메모리 관리자가 주소변환을 통해 원하는 페이지를 물리페이지로 가져온다.

 

 

이 때에 빈 메모리가 없다면 물리메모리에 있는 메모리를 스왑영역으로 자리를 바꿔줘야 하는데 어떤 페이지를 바꿀지 정하는 방법을 페이지 교체 알고리즘이라고 하며 스왑영역으로 보내지는 페이지를 대상페이지라 한다.

 

1-4 지역성

 

페이지 교체 알고리즘은 지역성을 바탕으로 어떤 페이지를 스왑영역으로 내보낼지 정한다.

 

당연히 스왑영역으로 나가는 페이지는 앞으로 사용하지 않을 테이블이면 더 좋을 것이다. 그 방법을 지역성을 바탕으로 정한다.

 

지역성의 종류

• 공간의 지역성 : 현재 위치에서 가까운 데이터를 사용할 확률이 높다. 

→ 가장 멀리있는 페이지를 스왑영역으로 내쫒는다.

→ goto문을 사용하면 공간 지역성의 쓸모가 없어짐

• 시간의 지역성 : 현재 기준으로 가장 가까운 시간에 접근한 메모리를 사용할 확률이 높다.
• 순차적 지역성 : 여러 작업이 순차적으로 진행되는 것이 일반적이니 순서를 우선시한다.

 

2. 페이지 교체 알고리즘

 

2-1 페이지 교체 알고리즘의 개요

 

페이지 교체 알고리즘 : 물리 메모리가 가득 찬 상태에 또다른 메모리가 필요하다면 물리 메모리에 있는 어떤 데이터를 스왑영역으로 보낼지 결정하는 알고리즘

→ 앞으로 사용할 가능성이 적은 데이터 우선

 

1. 페이지 교체 알고리즘의 종류

종류	알고리즘	특징
간단한 알고리즘	무작위	무작위로 대상 페이지를 선정
	FIFO	메모리에 올라온 순서대로 선정
이론적 알고리즘 (사실상 불가능)	최적	미래의 접근 패턴을 보고 대상페이지를 선정
최적 근접 알고리즘	LRU	시간적으로 멀리 떨어진 페이지를 선정
	LFU	사용 빈도에 따라 대상 페이지를 선정
	NUR	최근에 사용한적이 없는 페이지를 선정
	FIFO 변형	FIFO 알고리즘을 변형하여 정확도를 높힘

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

 

당연히 사용하지 않을 페이지를 내보내 페이지 부재가 가장 일어나지 않는 알고리즘이 좋겠지만 유지비용도 고려해야 한다.

 

따라서 가장 적은 비용(적은 용량소모)이 들면서 가장 높은 효율을 내는 알고리즘이다.

 

2-2 무작위 페이지 교체 알고리즘

 

페이지 교체 알고리즘중 가장 간단한 알고리즘이다. 알고리즘이라고 하기도 못할 정도로 아무 연관관계가 없다. 말그대로 무작위로 아무 페이지나 스왑영역으로 보내버리기 때문에 거의 사용되지 않는다.

 

2-3 FIFO 페이지 교체 알고리즘

 

이전에 배웠던 큐를 사용하는 알고리즘이다. 가장 먼저 들어온 데이터가 가장 먼저 스왑영역으로 나간다. 이 알고리즘도 성능이 매우 떨어지기 때문에 자주 사용되지는 않는다.

 

2-4 최적 페이지 교체 알고리즘

 

앞으로 사용되지 않을 페이지 또는 가장 늦게 사용될 페이지를 스왑영역으로 보낸다. 하지만 이 방법은 미래의 접근패턴을 안다는 것이 불가능하여 실제로 구현이 불가능하다.

 

2-5 LRU 페이지 교체 알고리즘 (최적 근접 알고리즘)

 

이제부터는 현실성도 있으며 알고리즘이라는 표현을 할 수 있을만한 내용이 나온다.

 

LRU 알고리즘은 시간, 카운터, 참조비트 이 3가지의 종류를 가지고 있다.

 

1. 시간에 기반한 구현

: 프로세스가 페이지에 접근한 시간을 기록하여 구현하는 것 까지는 FIFO 알고리즘과 같지만, 다시 한번 메모리 내에 있는 프로세스가 선택되었을 때 시간을 초기화한다. 

2. 카운터에 기반한 구현

: 시간 대신 카운터를 이용한 방법

추가적인 메모리(시간측정, 카운터 측정)이 필요하기 때문에 메모리의 낭비가 단점이다.

 

3. 참조 비트 시프트 방식

: 각 페이지에 일정 크기의 참조비트를 만들어 사용한다.

참조 비트의 초깃값은 0이며 페이지에 접근할 때마다 1씩 증가한다. 

참조한 횟수가 아닌 참조한 시간을 기준을 잡아서 가장 오래전에 참조된 프로세스를 대상 프로세스로 선정

→ 1B이기는 하지만 메모리의 낭비가 생긴다. 

 

2-6 LFU 페이지 교체 알고리즘 (접근빈도)

 

'최소 빈도 사용 알고리즘' 이라고도 하며 페이지를 몇 번 사용하였나 를 기준으로 대상 페이지를 선정한다.

 

LRU 페이지 교체 알고리즘과 마찬가지로 페이지 접근 횟수를 표시하는데 추가 공간이 필요하므로 메모리의 낭비가 있다.

2-7 NUR 페이지 교체 알고리즘

 

'최근 미사용 페이지 교체 알고리즘'이라고도 하며 불필요한 공간 낭비 문제를 해결한 알고리즘

→ 기존의 PTE에 포함되어있는 참조/변경비트를 검사하기 때문에 메모리의 낭비가 없음

 

대상 페이지 선정 기준

(0,0) → (0,1) → (1,0) → (1,1)

→ 모든 페이지가 (1,1)이라면 모두 (0,0)으로 초기화

 

2-8 FIFO 변형 알고리즘

 

FIFO 알고리즘의 성능을 개선한 알고리즘으로 2차기회 페이제 교체/시계 알고리즘이 있다.

FIFO 알고리즘을 기본으로 하지만 페이지에 접근할 때마다 순서의 변화를 준다.

 

1. 2차 기회 페이지 교체 알고리즘

: FIFO와 마찬가지로 큐를 사용하지만 특정 페이지에 접근하여 페이지 부재 없이 성공하는 경우 해당 페이지를 큐의 맨 뒤로 이동하여 대상페이지에서 제외

 

2. 시계 알고리즘

: 2차 기회 페이지 교체 알고리즘과 유사하나 실제 구현은 시계 알고리즘이 원형 큐를 사용한다는 점에서 서로 다르다.