[운영체제] 가상 메모리

가상 메모리란 어떤 프로세스를 실행할 때 프로세스 전체가 메모리에 적재되지 않고도 실행이 가능하도록 하는 기법이다.

• 어떤 프로세스가 차지하는 메모리가 전체 메모리 용량보다 크더라도, 지금 현재 필요한 부분만 메모리에 적재하여 메모리에 올라가는 프로세스의 크기를 줄일 수 있기 때문에 물리 메모리 용량을 초과하는 프로그램도 동작시킬 수 있다.
• 파일이나 메모리가 둘 이상의 프로세스들에 의해 공유되는 것을 가능하게 한다.
  • 어떤 프로세스나 파일이 메모리 주소를 참조할 때 특정 물리주소가 아닌 가상 주소를 참조하기 때문.

 

요구 페이징(Demand Paging)

가상 메모리는 프로세스를 실행할 때, 실행에 필요한 부분만 메모리에 올리는 것이라고 했다. 이때 프로세스의 일부분은 페이지 단위일 수도 있고, 세그먼트 단위일 수도 있지만 현재 대부분은 페이지 단위를 사용한다. 이처럼 현재 필요한(요구되어지는) 페이지만 메모리에 올리는 것을 Demanding Paging(요구 페이징) 이라고 한다.

• Page Table : 특정 프로세스 내에서 어떤 페이지가 실제 메모리에 적재되었는지 여부를 구별하기 위한 테이블. CPU 입장에서 프호세스가 하나의 연속된 메모리 공간처럼 보일 수 있도록 한다.
• Page No : 프로세스 내 페이지 번호
• Frame No : 해당 페이지가 할당된 물리 메모리 주소
• Valid bit : 현재 메모리에 페이지가 있는지 없는지를 나타내는 비트. 현재 페이지가 메모리에 있다면 1, 없다면 0.
• Disk(backing store) : 프로세스의 이미지를 임시 보관하는 공간

페이지 부재(Page Fault)

페이지 부재는 CPU가 접근하려는 페이지가 메모리에 없는 경우를 말한다.

• 페이지 부재 발생시 처리 과정
  1. 해당 페이지가 메모리에 있는지 valid bit를 확인한다.
  2. valid bit가 0이라면 CPU에 인터럽트 신호를 보내어 운영체제 내부 해당 ISR로 점프한다.
  3. 해당 ISR에서 backing store(디스크)를 탐색하여 해당 프로세스의 페이지를 찾는다.
  4. 해당 페이지를 비어있는 프레임에 할당한다.
  5. 페이지 테이블을 갱신한다.(프레임 번호 설정, valid bit 1로 변경)
  6. 다시 명령어로 돌아가서 실행한다.

순수 요구 페이징(Pure Demaning Paging)

프로세스가 최초로 실행될 때는 어떤 페이지가 필요한지 알 수 없으므로, 아무 페이지도 올리지 않는다.

• 장점 - 메모리 절약을 최대화 할 수 있다.
• 단점 - 시작하자 마자 페이지 부재가 일어난다. 속도가 느려진다.

프리페이징(Prepaging)

필요할 것이라 판단되는 페이지를 미리 올리는 것

• 장점 - 미리 적재되어져 있기 때문에 속도가 빠르다.
• 단점 - 페이지 부재가 적다. 만약 사용되지 않으면 메모리 낭비가 된다.

스와핑 기법과 요구 페이징의 차이? - 스와퍼는 전체 프로세스를 관리하지만 요구 페이징은 프로세스 내의 개별 페이지들을 관리한다.

지역성의 원리(Locality of reference) - 메모리 접근은 시간적 지역성과 공간적 지역성을 가진다. (요구 페이징이 만족할만한 성능을 보이는 이유)

• 시간적 지역성: CPU는 어느 메모리 공간을 읽은 후, 시간이 지나도 그 공간을 다시 읽을 확률이 매우 높음.
  • 대표적인 예로 반복문이 있다. 반복문은 하나의 코드 공간을 여러 번 읽는다.
• 공간적 지역성: CPU가 메모리 공간을 읽을 때는 인접한 범위 내에서 읽음.
  • 프로그램은 대부분 절차적인 순서로 구현되어 있어 순서대로 읽는 경우가 빈번하다.

 

페이지 교체(Page Replacement)

Demanding Paging으로 인해 메모리를 절약하지만, 언젠가는 메모리가 가득 차게 될 것이다. 여기서 다른 프로그램이 새로 실행되거나 실행중인 프로세스가 다른 페이지를 요구한다면 이미 메모리에 있는 페이지 중 하나를 다시 backing store에 보내고(page-out), 새로운 페이지를 메모리에 올려야한다.(page-in) 이를 페이지 교체라고 한다.

페이지 교체 알고리즘(Page Replacement Algorithm)

페이지 교체로 인해 메모리에서 backing store로 page-out이 된 페이지를 victim page(희생양 페이지) 라고 한다. 페이지 교체 알고리즘은 이러한 victim page로 어떠한 페이지를 선택하느냐에 따라 나뉜다.

동작 순서

1. 디스크에서 필요한 페이지의 위치를 알아낸다.
2. 빈 페이지 프레임을 찾는다. (빈 프레임이 없다면 victim page를 찾아 비운다.)
3. 새롭게 비워진 프레임에 새 페이지를 읽어오고 프레임 테이블을 수정한다.
4. 사용자 프로세스를 재시작한다.

1. FIFO(First-In-First-Out) 페이지 교체

• 메모리에 먼저 올라온 페이지를 먼저 내보내는 알고리즘.
• 쉽고, 설계가 간단하지만, Belady's Anomaly 발생
  • Belady’s Anomaly : 기존 페이지 프레임의 개수를 늘리면 Page Fault 발생이 감소해야하나, 오히려 늘어나는 현상.
• 중요한 페이지가 차후에 계속 사용될 가능성이 있음에도 오랫동안 있었다는 이유만으로 교체되는 것은 불합리.

2. OPT(Optimal) 페이지 교체

• 가장 사용하지 않을 페이지를 가장 우선적으로 내려 보내는 알고리즘.
• 미래를 알 수 없기 때문에 실질적으로 수행하기 어려움

3. LRU(Least-Recently-Used) 페이지 교체

• 최근에 사용하지 않은 페이지를 가장 먼저 내려 보내는 알고리즘.
• OPT가 미래에 대한 예측이지만, LRU는 과거를 보고 판단.
• 최근에 사용하지 않은 페이지는 앞으로도 사용하지 않을 확률이 높다. => 실질적으로 사용 가능한 알고리즘.

4. LFU(Least Frequently Used) 페이지 교체

• 사용빈도가 가장 적은 페이지를 교체하는 기법
• 프로그램 실행 초기에 많이 사용된 페이지가 그 후로 사용되지 않을 경우에도 프레임을 계속 차지하는 단점이 존재

5. NUR(Not Used Recently) 페이지 교체

• 최근에 사용하지 않은 페이지를 교체하는 기법
• LRU와 유사하며, LRU에서 나타나는 시간적인 오버헤드를 줄일 수 있다.
• 사용 여부를 확인하기 위하여 각 페이지마다 참조비트와 변형비트가 사용됨
  • 참조 비트 : 페이지가 호출되지 않았을 때는 0, 호출되었을 때는 1로 저장된다.
  • 변형 비트 : 페이지 내용이 변경되지 않았을 때는 0, 변경되었을 때는 1로 지정된다.참조 비트변형 비트교체 순서

    0	0	1
    0	1	2
    1	0	3
    1	1	4

6. SCR(Second Chance Replacement) 페이지 교체

• 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 기법
• FIFO 알고리즘 기법의 단점을 보완하는 기법
• 참조 비트가 0일 경우에는 교체하고, 참조비트가 1일 경우에는 참조 비트를 0으로 지정한 후 FIFO 리스트의 맨 마지막으로 피드백시켜 다음 순서를 기다리게 한다.

 

[참고]

• https://jinhyy.tistory.com/35
• https://velog.io/@codemcd/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9COS-15.-%EA%B0%80%EC%83%81%EB%A9%94%EB%AA%A8%EB%A6%AC
• https://m.blog.naver.com/PostView.nhn?blogId=yeop9657&logNo=220729107141&proxyReferer=https:%2F%2Fwww.google.com%2F
• https://frontalnh.github.io/2018/04/04/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EA%B0%80%EC%83%81-%EB%A9%94%EB%AA%A8%EB%A6%AC%EB%9E%80-%EB%AC%B4%EC%97%87%EC%9D%B8%EA%B0%80/
• http://truemind5.blogspot.com/2017/05/15-1.html
• https://seungahyoo.tistory.com/70
• https://goodmilktea.tistory.com/36
• https://server-engineer.tistory.com/126
• https://jhpop.tistory.com/34