[운영체제] 가상 메모리 관리 / 페이지 교체 알고리즘 / 스레싱 / 프레임

요구 페이징의 개요

• 메모리에는 꼭 필요한 프로세스만 유지하는 게 중요하다.
• 그러기 위해서 프로세스의 일부만 메모리에 가져오는 방법을 사용한다.
• 이 방법의 장점은 메모리를 효율적으로 관리할 수 있고, 응답 속도를 향상할 수 있다는 것이다.

 

• 요구 페이징
  • 사용자가 요구할 때 해당 페이지를 메모리로 가져오는 것
• 미리 가져오기 
  • 필요할 것이라고 예상되는 페이지를 미리 가져오는 방식

 

페이지 테이블 엔트리의 구조

• 페이지 테이블 엔트리의 구성
  • 페이지 번호 / a, m, v, r, w, x비트 / 프레임 번호
• 접근 비트 = 참조 비트
  • 페이지가 메모리에 올라온 후 사용한 적이 있는지 알려주는 비트
• 변경 비트 = 더티 비트
  • 페이지에서 데이터의 변경이 있었는지 알려주는 비트
• 유효 비트
  • 실제 메모리에 있는지를 나타내는 비트
  • 1이라면 스왑 영역에 있다.
• 읽기, 쓰기, 실행 비트
  • 각 권한에 대한 비트

 

페이지 부재

• 프로세스가 페이지를 요청했을 때 그 페이지가 메모리에 없는 상황
• 사용자 프로세스와 무관
• 페이지 부재가 발생하면 스왑 영역에서 물리 메모리로 페이지를 옮겨야 한다.

 

• 페이지 교체 알고리즘
  • 어떤 페이지를 스왑 영역으로 내보낼지 결정하는 알고리즘
• 대상 페이지
  • 페이지 교체 알고리즘에 의해 스왑 영역으로 보낼 페이지
• 세그먼테이션 오류
  • 사용자의 프로세스가 주어진 메모리 공간을 벗어나거나 접근 권한이 없는 곳에 접근할 때 발생

 

지역성

• 페이지 교체 알고리즘이 쫓아낼 페이지를 찾을 때 지역성을 바탕으로 한다.
• 지역성은 기억장치에 접근하는 패턴이 특정 영역에 집중되는 성질을 말한다.

 

• 공간의 지역성
  • 현재 위치에서 가까운 데이터에 접근할 확률이 높다.
• 시간의 지역성
  • 가장 가까운 시간에 접근한 데이터가 확률이 높다.
• 순차적 지역성
  • 작업이 순서대로 진행되는 경향이 있다.

 

페이지 교체 알고리즘

• 페이지 교체 알고리즘은 메모리가 꽉 찼을 때 스왑 영역으로 보낼 페이지를 결정하는 알고리즘이다.

 

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

• 특별한 로직 없이 무작위로 선정한 페이지를 스왑 영역으로 보내는 방식
• 지역성을 전혀 고려하지 않았기 때문에 성능이 안 좋다.

 

FIFO

• 선입선출 알고리즘으로 가장 먼저 들어온 페이지를 스왑 영역으로 쫓아낸다.

 

최적 페이지 교체 알고리즘

• 앞으로 사용하지 않을 페이지를 스왑 영역으로 보낸다.
• 미래의 메모리 접근 패턴을 알아야 하기 때문에 구현이 불가능하다.

 

LRU 페이지 교체 알고리즘

• 가장 오랫동안 사용하지 않은 페이지를 옮긴다.
• 시간에 기반한 구현과, 카운터에 기반한 구현, 참조 비트 시프트 방식을 이용한 구현 방법이 있다.

 

LFU 페이지 교체 알고리즘

• 페이지가 몇 번 사용되었는지를 기준으로 대상 페이지를 선정한다.

 

NUR 페이지 교체 알고리즘

• 최근 미사용 페이지 교체 알고리즘으로 추가 비트 2개를 이용해 미래를 추정한다.
• 참조 비트 : 페이지에 접근하면 1이 된다.
• 변경 비트 : 페이지가 변경되면 1이 된다.
• 교체 기준은 참조 비트가 0인 페이지를 먼저 찾고, 없으면 변경 비트가 0인 페이지를 찾는다.
• 만약 모든 페이지가 (1,1)이 되면 모든 페이지 비트를 (0,0)으로 초기화한다.

 

FIFO 변형 알고리즘

• 2차 기회 페이지 교체 알고리즘
  • FIFO에서 특정 페이지를 부재 없이 성공한 경우 다시 큐의 맨뒤로 옮겨서 기회를 한 번 더 주는 방식이다.
• 시계 알고리즘
  • 원형 큐를 이용하는 방식이다.
  • 포인터가 시계처럼 한 방향으로 돈다.

 

스레싱

• 메모리가 꽉 찬 후 스왑 영역과의 입출력이 너무 많아져서 잦은 페이지 부재로 작업이 멈춘 것 같은 상태
• 멀티프로그래밍 정도가 너무 높으면 스레싱이 발생한다.
• 스레싱 발생 시점
  • 메모리가 꽉 차서 CPU가 작업하는 시간보다 입출력 작업이 빈번해져서 CPU가 작업할 수 없는 상태에 이르게 되는 시점

 

정적 할당

• 균등 할당
  • 프로세스의 크기와 상관없이 프레임을 모두 동일하게 할당
• 비례 할당
  • 프로세스의 크기에 비례하여 프레임을 할당하는 방식

 

동적 할당

• 작업집합 모델(working set model)
  • 가장 최근에 접근한 프레임이 이후에도 또 참조될 가능성이 높다는 가정에서 출발
  • 최근 일정 시간동안 참조된 페이지를 집합으로 만들고 이 집합에 있는 페이지들을 물리 메모리에 유지하여 실행을 돕는다.
• 페이지 부재 빈도
  • 페이지 부재 횟수를 기록해 비율을 계산한다.
  • 부재 비율의 상한선과 하한선을 설정해서 상한선을 초과하면 프레임을 추가하고, 하한선 밑으로 내려가면 프레임을 회수한다.