가상 메모리 관리

가상 메모리 관리

요구 페이징

사용자가 요구 할 때 해당 페이지를 메모리로 가져 오는 것을 요구 페이징이라 칭한다.

요구 페이징은 가상 메모리 시스템에서 주로 사용하며 프로그램 실행 시에 당장 사용될 페이지만을 적재함으로써 메모리를 더 효율적으로 사용할 수 있도록 한다.

장점

1. 필요한 페이지만 메모리에 적재하기 때문에 메모리 사용량이 감소한다.
2. 프로세스 전체를 메모리에 올리는 데 소요되는 입출력 오버헤드가 감소한다.
3. 사용되지 않는 주소 영역에 대한 입출력이 줄어 응답시간이 줄어든다.
4. 시스템이 더 많은 프로세스를 수용할 수 있게 해준다.
5. 물리적 메모리의 제약을 벗어날 수 있다.

페이지 테이블 엔트리

PTE ( Page Table Entry ) : 페이지 테이블의 한 행을 의미하고 페이지 번호 / 프레임 번호 / 플래그 비트 로 구성

플래그 비트

• 접근 비트 ( Access bit ) : 페이지가 메모리에 올라 온 후 사용 한 적이 있는지를 알려주는 비트
• 변경 비트 & 더티 비트 ( dirty bit ) : 데이터의 변경이 있었는지 알려주는 비트
• 유효 비트 & 현재 비트 ( present bit ) : 페이지가 메모리에 있는지, 스왑 영역에 있는지 알려주는 비트
• 접근 권한 비트 (읽기 / 쓰기 / 실행 비트) : 페이지에 대한 읽기 / 쓰기 / 실행에 대한 권한이 적힌 비트

Page fault

프로세스가 페이지를 요청 했을 때, 그 페이지가 메모리에 없는 상황을 페이지 부재 ( page fault ) 라고 한다. (유효 비트가 1일 경우)

동작 방식

1. MMU(Memory Management Unit)가 페이지 부재 트랩을 발생
2. CPU의 제어권이 커널모드로 변경되고 운영체제의 페이지 부재 처리 루틴이 호출
3. 운영체제가 페이지에 대한 주소가 유효한지 확인
4. 물리 메모리에 빈 공간이 있는 경우, 스왑 영역에 있는 페이지를 메모리의 비어있는 프레임에 할당
5. 물리 메모리에 빈 공간이 없는 경우, 페이지 교체 알고리즘을 통해 대상 페이지를 스왑 영역으로 옮긴다. → 대상 페이지의 프레임에 옮길 페이지를 할당
6. 디스크로부터 메모리 적재는 오랜 시간이 걸기 때문에, 페이지 부재가 발생한 프로세스는 CPU를 반납하고 PCB에 현재 상태를 저장 후 blocked 된다.
7. 디스크 입출력이 완료되어 인터럽트가 발생하면, 해당 페이지의 유효-무효 비트를 유효로 수정
8. 봉쇄되었던 프로세스를 준비 큐로 이동시킨다.
9. CPU를 할당 받고 PCB로부터 저장한 값을 복원시켜 중단되었던 명령부터 실행을 이어간다.

지역성

데이터 접근이 메모리 전체에 고루 분포되는것이 아니라 특정 영역에 집중되는 성질.
물리 메모리가 꽉 차 페이지를 스왑 영역으로 보낼 때엔 되도록 사용하지 않을 페이지를 보내는 것이 좋기 때문에 지역성을 바탕으로 진행 하는 경우가 많다.

• 공간의 지역성 : 현재 위치에서 가까운 데이터에 접근 할 확률이 먼 거리에 있는 데이터에 접근할 확률보다 높다.

• 시간의 지역성 : 현재를 기준으로 가장 가까운 시간에 접근한 데이터가 더 먼 시간에 접근한 데이터보다 사용 될 확률이 높다.

• 순차적 지역성 : 기억장치에 저장된 순서대로 인출되어 실행 ( 프로그래밍은, 윗줄에서 아랫줄로 가는 경향이 있다.)

캐시의 지역성

+) 캐시 : CPU의 처리속도와 메모리의 속도 차이로 인한 병목현상을 완화하기 위해 사용하는 고속 버퍼 메모리

캐시의 성능은 작은 용량의 캐시 메모리에 CPU가 이후에 참조할 쓸모있는 데이터가 어느 정도 할당되어 있는 지에 따라 좌우된다. (Hit rate의 극대화)

따라서, 지역적으로 가까이 있는 데이터를 캐시에 가져 옴으로써 Hit rate를 높일 수 있다.

페이지 교체 알고리즘

페이지 부재(page fault)가 발생하였을 때, 어떠한 프레임에 있는 페이지를 디스크의 스왑 영역으로 보낼 것인지를 결정하는 알고리즘

이 알고리즘의 목표는 가까운 미래에 참조될 가능성이 가장 적은 페이지를 선택해서 내보내는 것으로 페이지 부재율을 최소화하여 오버헤드를 줄인다.

• 선입선출 알고리즘(FIrst In First Out: FIFO)
  페이지 교체 시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내보내는 알고리즘
  메모리에 올라온지 오래 되더라도 자주 사용되는 페이지를 고려하지 않기 때문에 (지역성을 고려하지 않는다) 비효율적인 상황이 발생할 수 있다.

+) FIFO anomaly(FIFO의 이상 현상) : 더 많은 page frame을 할당 받음에도 불구하고 page fault가 증가하는 경우

• LRU (Least Recently Used) Algorithm
  시간 지역성을 활용하여 페이지 교체 시 가장 오래전에 참조가 이루어진 페이지를 내보낸다.
  page 참조 시 마다 시간 또는 카운터를 기록해야하므로 추가적인 메모리 공간이나 검색 시간이 필요하지만 참조 비트, 순서 같은 간소화된 정보 수집으로 해결 가능하다.

OPT보다는 페이지 결함이 더 일어날 수 있지만, 실제로 가장 많이 활용되는 방법 중 하나

• 최적 알고리즘 (Min Algorithm & OPT algorithm)
  page fault를 최소화 시키는 알고리즘으로 메모리가 앞으로 사용할 페이지를 미리 살펴보고, 앞으로 사용하지 않을 페이지를 교체한다. 미래의 접근 패턴을 아는 것이 불가능 하여 실제로 구현 할 수 없는 방식이지만, 다른 교체 알고리즘의 성능 평가 도구로 사용 됩니다.

• LFU(Least Frequenctly Used) Algorithm
  과거에 참조 횟수가 가장 적은 페이지를 교체한다. page 참조 시 마다, 참조 횟수를 누적 시켜야한다.(추가적인 메모리 공간 필요) LRU처럼 Locality 활용하지만, 최근 적재된 참조될 가능성이 높은 page가 교체 될 가능성이 있다. (초기에 한 페이지를 집중적으로 참조하다가 이후 다시 참조하지 않는 경우, 메모리에 계속 남아있는 문제)

• NUR ( Not Used Recently page replacement algorithm )
  알고리즘에서 접근 시간이든, 접근 빈도든 정확한 값을 유지하는 것은 의미가 없고 순위만 알수 있으면 된다는 생각을 기반으로 구현되었다. LRU와 비슷하게 최근에 사용하지 않은 페이지를 교체한다. 최근의 사용여부를 확인 하기 위해 각페이지마다 두개의 비트 사용함으로 써 LRU의 오버헤드를 줄일 수 있다. 실제로 자주 사용되는 알고리즘이다.

  • 참조 비트: 페이지가 참조되지 않았을 때 0, 호출되었을 때 1 (모든 참조비트를 주기적으로 0으로 변경)
  • 변형 비트: 페이지 내용이 변경되지 않았을 때는 0, 변경되었을 때 1
  • 우선순위: 참조비트 > 변형비트

스레싱 (trashing)

잦은 페이지 부재로 CPU 이용율이 급격히 떨어지는 상태를 스레싱이라 한다. (메모리에 올라와 있는 프로세스의 수가 너무 적어 프로세스가 모두 I/O작업을 함으로써 준비 큐가 비는 경우)
물리 메모리 크기가 부족 할 때, 프로그램을 계속 실행 시키면 CPU 사용률이 증가 하다가 어느 구간부터 떨어지는 구간이 존재하는데 이 구간이 스레싱 발생 지점이다.

정적 할당과 동적 할당

정적 할당

프로세스 실행 초기에 프레임을 나누어 준 후 프레임 크기를 고정 하는 방식

• 균등 할당 방식
  프로세스의 크기와 상관 없이 사용 가능한 프레임을 모든 프로세스에 동일하게 할당한다.
• 비례 할당 방식
  프로세스의 크기에 비례하여 프레임을 할당하는 방식

동적 할당

프로세스를 실행할 때 Page의 사용을 고려하여 동적으로 프레임을 할당

• Working Set Model
  working set은 현재 시간에서 일정 시간 이전동안 사용되었던 페이지의 집합이다. 이 집합에 있는 페이지들을 물리 메모리에 남겨두어 Page Fault를 방지한다.

• Page Fault Frequency(PFF) algorithm
  page fault 발생 빈도에따라 page frame의 크기를 조절하는 알고리즘이다. 페이지 부재 비율이 상한선을 초과 하면 프레임을 추가적으로 할당하고 하한선을 초과 할 경우 할당된 프레임을 일부 회수한다.

전역 교체와 지역 교체

교체할 페이지를 선택할 때, 프레임 범위를 정하는 방법은 2가지가 있다.

• 전역 교체
  메모리 상의 모든 프로세스 페이지를 대상으로 교체 알고리즘을 적용
  - 한 프로세스에 할당된 프레임의 수는 바뀔 수 있다.
  - 프로세스 간 영향을 끼칠 수 있으므로 외부적 환경에 따라 다르게 실행된다.
  
• 지역 교체
  현재 실행중인 프로세스가 차지하고 있는 만큼의 물리 메모리 전체 만을 대상으로 교체 알고리즘 적용

지역보다 전역 교체 알고리즘이 더 좋은 성능을 나타내며 일반적으로 많이 사용하고 있다.

페이지 테이블 크기

페이지 한개의 크기를 늘림 → 가상 주소 하나당 행의 개수가 줄어듬 → 각 행을 표현할 주소공간의 크기가 줄어듬 → 페이지 테이블 하나가 차지하는 물리 공간이 줄어듬

하지만, 무작정 페이지 하나의 크기를 늘리면, 내부 단편화로 낭비되는 공간이 많아질 수 있다.
현대 컴퓨터 시스템은 물리 메모리도 커지고, 응용 프로그램도 커지고 있기 때문에, 페이지의 크기를 점점 늘리고 있는 추세이다.

쓰기 지점 복사

데이터의 변화가 있을 때까지 복사를 미뤄서 메모리 낭비를 방지한다.