[OS] 가상 메모리

배경

• 정의: 프로세스를 실행할 때 실행에 필요한 일부만 메모리에 로드하고 나머지는 디스크(backing store)에 두는 기술
  • 따라서, 프로세스 전체가 물리적 메모리에 있는 것'처럼' 수행되어, 물리적 메모리가 훨씬 많이 있는 것처럼 보이게 됨
  • 결과적으로 더 많은 프로그램을 동시에 실행 가능

 

 

Demand Paging

• 정의: 현재 필요한 Page만 메모리에 올리는 방법
• Page Fault Handling을 통해 구현 가능
  • Page Fault: 요청된 페이지가 MM에 없는 경우

 

Page Fault Handling(처리 방법)

valid-invalid 1bit를 이용해서 처리

• valid: page가 메모리에 존재 ( & 해당 프로세스에 맞는 페이지 legal )
• invalid page가 메모리에 존재 ( | 해당 프로세스에 맞는 페이지x not legal )

 

 

 

1. 요청된 페이지를 페이지 테이블에서 확인
2. page fault가 발생했다면(= invalid하다면) , page in 처리를 해줘야함 (  valid하다면 그냥 처리 )
3. 넣을 수 있는 프레임 영역(free frame)을 확인
4. HDD에 있는 페이지를 프레임에 배치
5. 페이지 테이블 수정
6. 다시 명령어 수행

 

 

 

 

 

페이지 교체(Page Replacement)

그러면 페이지를 MM에 넣어야하는데 실제 메모리 공간이 부족한 경우는 어떻게 처리하는가?

 

성능 측정

• 알고리즘 성능 척도: page fault가 적게 발생되는 것이 좋은 알고리즘! ( HDD 접근에 시간이 많이 소요되므로 )

 

 

 

교체 과정

1. 페이지 교체 알고리즘을 통해 선정된 희생자(victim) 페이지를 page out처리
2. 페이지 테이블에서 해당 테이블 invalid 처리
3. page request를 한 page in 처리
4. 페이지 테이블에서 새롭게 들어온 페이지 valid 처리

 

페이지 교체 알고리즘

• 3개의 프레임이 존재할 때, 다음과 같은 순서로 페이지 request가 들어오면 어떻게 처리되는가?

 

Optimal Page replacemenT(OPT)

• 정의: 앞으로 가장 참조가 덜 되는 페이지(will not be used)를 교체시키는 방법
• 전제 조건: 그러려먼 미래의 참조 정보를 모두 가지고 있어야 구현 가능한 방법
  • 그래서 얘는 실제 구현보다, 그냥 얘를 기준으로 성능이 이정도로 나온다! 이렇게 비교용도로만 사용되는 알고리즘

총 9번의 page fault가 발생

 

 

 

FIFO

• 정의: 가장 먼저온 페이지(oldest page)를 교체시키는 방법

총 15번의 page falut가 발생

 

 

 

Least Recently Used(LRU)

• 정의: 최근에 가장 오랫동안 사용되지 않은 페이지를 교체시키는 것
• 전제 조건:  해당 프레임이 언제 마지막으로 사용되었는지 정보가 필요

총 12번의 page fault가 발생

 

 

LRU 구현 방법

• 핵심: 카운터와 스택 자료구조 방법은 구현하기 어렵기에 근사치 방법(Clock Alogrotihm)을 사용한다.

카운터(Counter) 방법	스택(stack) 방법	근사치(Approximation) 방법
각 페이지에 매핑되는 카운터 배치 참조할때마다 카운터 증가 교체할때, 값이 가장 작은것을 선택	스택을 배치 참조할때마다 스택에 넣기 교체할때, 가장 안쪽에 있는 것을 선택	각 페이지에 매핑되는 reference 1 bit 배치 참조할때 값을 1로 세팅 교체 시기에, 값이 0인것을 선택 교체후 , 다시 모든 값을 0으로 세팅

 

Allocation of Frames

그럼 이번에는 N개의 프레임이 있고, M개의 프로세스가 있을때, 각 프로세스에 몇개의 프레임을 할당해줄거냐?

• Equal vs Proportional
  • Equal: 모든 프로세스에게 동일한 개수의 프레임 할당
  • proportional: 프로세스 크기나 우선순위에 비례하게 프레임을 할당
• Global vs Local
  • local: 페이지 교체시 오로지 자신이 할당받은 프레임내에서 교체가 발생하는 것
  • global: 다른 프로세스의 프레임도 페이지 교체 대상에 넣는 것

 

Thrashing

• 정의: 프로세스가 원할한 수행에 필요한 최소한의 page frame을 할당받지 못해, 실행보다 Swapping 하는데 더 많은 시간을 소모하는 현상
  • OS가 Multiprogramming Degree를 높이면, 프로세스당 할당되는 page frame이 감소하게 됨
  • 프로세스는 Swapping(I/O)으로 매우 바빠져서, 대부분의 시간에 CPU는 한가해짐
  • = Swapping(I/O) 작업 증가 + CPU 효율성(Utilization) 감소 

 

 

참고

https://rebro.kr/179?category=504670

[운영체제(OS)] 9. 가상 메모리(Virtual Memory)