[쉽게 배우는 운영체제] 9장 가상 메모리 관리

요구 페이징

가져오기 정책 중 프로세스가 요청할 때 메모리로 가져오는 방법

 

프로세스의 일부만 메모리로 가져오는 이유

• 적은 메모리를 유지하여 메모리를 관리하기 쉬워짐
• 메모리 적재하는 시간 감소, 캐시 지역성 활용, 스왑 감소 등으로 응답 속도를 향상

 

페이지 테이블 엔트리(PTE) 구조

• 페이지 번호 : 직접 매핑에는 필요없지만 연관 매핑에는 필요
• 프레임 번호 : 가상 주소의 페이지가 어느 프레임에 있는지 알려줌
• 접근(참조) 비트 : 페이지가 메모리에 올라온 후 사용한 적이 있는지 알려주는 비트
• 유효 비트 : 페이지가 메모리에 있는지 나타내는 비트
  페이지가 스왑 영역에 있는 경우는 요구 페이징으로 처음부터 메모리에 적재되지 않는 경우와 메모리가 꽉 차서 스왑 아웃된 경우
• 읽기, 쓰기, 실행 비트 : 페이지에 대한 읽기, 쓰기, 실행 권한을 나타내는 비트
  세그먼테이션-페이징 혼용 기법에서 테이블의 크기를 줄이기 위해 접근 권한 비트를 세그먼테이션 테이블로 옮김

페이지 폴트

프로세스가 페이지를 요청했을 때 페이지가 메모리에 없는 상황

페이지 폴트가 발생하면 스왑 영역에서 물리 메모리로 옮기고 페이지 테이블을 업데이트

메모리에 빈 프레임이 없을 때는 페이지 교체 알고리즘을 통해 메모리에 있는 프레임 중 하나를 스왑 아웃해야 함

 

페이지 폴트 이후 처리 과정

1. MMU가 페이지 폴트 인터럽트를 발생시켜 현재 실행 중인 명령어의 상태가 저장됨
2. 페이지 폴트 처리 루틴 실행
3. 페이지 테이블을 검사하고 페이지 찾기
4. 메모리가 꽉 찼다면 페이지 교체 알고리즘을 사용하여 페이지를 스왑 아웃하고 페이지 테이블 업데이트
5. 필요한 페이지를 스왑 인하고 페이지 테이블 업데이트
6. 페이지 폴트 발생 시킨 명령어부터 프로세스 실행 재개

세그먼테이션 오류는 프로세스가 주어진 메모리 공간을 벗어나거나 접근 권한이 없는 곳에 접근할 때 발생하고, 해당 프로세스를 강제 종료하여 해결

페이지 교체 알고리즘

페이지 교체 알고리즘에 의해 스왑 아웃하는 페이지를 대상(victim) 페이지라고 함

 

지역성

메모리가 꽉 차서 페이지를 스왑 아웃할 때는 되도록 앞으로 사용하지 않을 페이지를 스왑 아웃하는 것이 좋음

• 자주 사용될 페이지를 스왑 아웃하면 다시 스왑 인해야 하기 때문에 시스템의 성능이 떨어짐

지역성은 기억장치에 접근하는 패턴이 특정 영역에 집중되는 성질

• 공간의 지역성 : 현재 위치에서 가까운 페이지에 접근할 확률이 먼 페이지에 접근할 확률보다 높음
• 시간의 지역성 : 현재를 기준으로 가까운 시간에 접근한 데이터가 먼 시간에 접근한 데이터보다 사용할 확률이 높음
• 순차적 지역성 : 작업이 순서대로 진행되는 경향, 공간의 지역성의 특별한 경우로도 보기도 함

 

무작위 페이지 알고리즘

가장 간단한 알고리즘

대상 페이지를 무작위로 선정

지역성을 전혀 고려하지 않기 때문에 자주 사용하는 페이지가 대상 페이지로 선정

알고리즘의 성능이 좋지 않아 거의 사용되지 않음

FIFO(First In First Out) 페이지 교체 알고리즘

시간상으로 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정

큐로 구현하여, 가장 오래된 페이지인 메모리의 맨 위에 있는 페이지를 스왑 아웃하고, 새로운 페이지는 항상 맨 아래에 삽입되어 스왑 인

큐로 간단하게 구현 가능

시간의 지역성을 고려하면 가장 오래된 페이지를 선정하는 것이 맞지만, 오래되었더라도 자주 사용되는 페이지일 수 있기 때문에 성능이 떨어짐
Belady의 역설 : 페이지의 프레임 수가 커질수록(사용 가능한 메모리의 크기가 클수록) Page Fault가 늘어나는 역설

 

최적 페이지 교체 알고리즘

앞으로 사용하지 않을 페이지를 선정

미래의 접근 패턴을 보고 대상 페이지를 결정하기 때문에 성능이 좋음

미래의 접근 패턴을 안다는 것이 불가능하여 실제로 구현할 수 없음

 

LRU(Least Recently Used) 페이지 교체 알고리즘

가장 오랫동안 사용되지 않은 페이지를 선정

시간, 카운터, 참조 비트 등을 사용하기 때문에 추가적인 메모리 사용

• 접근 시간에 기반한 구현은 접근한 시간을 기록하여 접근한 지 가장 오래된 페이지를 선정
  LRU 방법 중 가장 간단
• 카운터에 기반한 구현은 시간 대신 카운터를 사용
• 참조 비트 시프트 방식은 일정 크기의 참조 비트를 만들어 참조 비트가 가장 작은 값인 페이지를 선정
  참조 비트의 초기값은 0이고, 접근할 때마다 모든 참조 비트가 오른쪽으로 이동한 뒤 1로 변경됨

LFU(Least Frequently Used) 페이지 교체 알고리즘

사용된 횟수가 가장 적은 페이지를 선정

횟수를 표시하는데 필요한 메모리 낭비

 

NUR(Not Used Recently) 페이지 교체 알고리즘

LRU, LFU와 성능이 가장 비슷하고 메모리 낭비 문제를 해결

95번 접근한 페이지와 91번 접근한 페이지가 있다면 미래를 추정할 때 두 페이지의 접근 확률은 비슷

따라서 정확한 값을 유지하는 것은 메모리만 차지하기 때문에 추가 비트 2개만 사용

• PTE의 접근 비트와 PTE의 변경 비트

우선 고려 대상은 접근 비트이므로 (0, 0) (0, 1) (1, 0) (1, 1) 순서대로 페이지를 선정

모든 페이지가 (1, 1)이 되면 모든 페이지 비트를 (0, 0)으로 초기화

 

FIFO 변형 알고리즘

FIFO 페이지 교체 알고리즘을 기본으로 하되 페이지에 접근할 때마다 순서의 변화를 주어 성능을 향상

• 2차 기회 페이지 교체 알고리즘 : 특정 페이지에 접근하여 페이지 폴트 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동
  성능은 LRU, LFU, NUR보다 낮고 FIFO보다 높음
  큐를 유지하는 비용이 높고, 큐의 중간 값을 뒤로 이동하는 작업이 추가되는 단점
• 시계 알고리즘 : 원형 큐를 사용
  대상 페이지를 가리키는 포인터가 시계처럼 한 방향으로 돌기 때문에 시계 알고리즘이라고 부름
  참조 비트를 사용하여 페이지 참조에 성공하면 참조 비트가 1이 됨
  참조 비트가 1인 페이지는 건너뛰고 참조 비트를 0으로 초기화
  NUR보다 메모리 공간이 적게 들지만 알고리즘이 복잡하고 계산량이 많다는 단점
  

  

  출처 : https://rob-coding.tistory.com/37

스레싱과 프레임 할당

스레싱

잦은 페이지 폴트로 CPU 작업 시간보다 스왑 인/스왑 아웃 작업 시간이 더 많은 상태

동시에 실행할 수 있는 프로그램의 수를 멀티프로그래밍 정도라고 하는데, 멀티프로그래밍 정도가 높으면 스레싱 발생 확률이 높아짐

 

스레싱은 프로세스에 프레임을 할당하는 정책과 연관이 있는데, 적은 프레임을 할당하면 스레싱이 발생할 확률이 높아지고, 많은 프레임을 할당하면 메모리 낭비

 

정적 할당

프로세스 실행 초기에 프레임을 할당한 후 크기를 고정

• 균등 할당 : 프로세스의 크기와 상관없이 모든 프로세스에 균등하게 할당
  크기가 큰 프로세스는 페이지 폴트가 빈번하게 발생하고, 크기가 작은 프로세스는 메모리 낭비
• 비례 할당 : 프로세스의 크기에 비례하여 할당
  프로세스가 런타임에 필요한 프레임을 유동적으로 반영하지 못함
  사용하지 않을 프레임을 미리 할당하여 낭비

동적 할당

런타임에 필요한 프레임만 할당

• 작업집합 모델 : 지역성 이론을 바탕으로, 최근 일정 시간 동안 참조된 페이지들을 집합으로 만들고 집합에 있는 페이지들을 물리 메모리에 유지
  작업집합 크기는 작업집합에 들어갈 최대 페이지 수를 의미하고, 작업집합을 갱신하는 주기를 의미
  작업집합 크기를 크게 잡으면 필요 없는 페이지가 메모리에 남아 메모리 낭비하고, 작게 잡으면 필요한 페이지가 스왑 아웃되어 페이지 폴트 증가
• 페이지 폴트 빈도 : 페이지 폴트 횟수를 기록하여 비율을 계산하고, 상한을 초과하면 프레임을 추가로 할당하고, 하한 아래로 내려가면 프레임을 회수
  실행하면서 추가적으로 페이지를 할당하거나 회수하여 적정 페이지 할당량을 조절

 

프레임 관련 이슈

전역 교체 : 전체 프레임을 대상으로 페이지 교체 알고리즘을 적용

지역 교체 : 현재 실행 중인 프로세스의 프레임를 대상으로 교체 알고리즘을 적용
프로세스의 할당된 프레임의 전체 개수에 변화가 없기 때문에 다른 프로세스의 스레싱에 영향을 미치지 않음

자주 사용하는 페이지가 스왑 아웃되어 현재 프로세스의 스레싱이 발생할 수 있음

 

페이지 테이블의 크기를 줄이기 위해 페이지의 크기를 높일 수 있음

그러나 페이지의 크기를 무작정 늘리면 내부 단편화로 인한 메모리 낭비 증가

 

여러 프로세스가 동시에 같은 프레임을 메모리에 올리면 메모리가 낭비되므로 메모리에 프레임을 하나만 올리고 페이지가 공유하여 해결