[08]가상 메모리

연속 메모리 할당

• 프로세스에 연속적인 메모리 공간을 할당하는 방식

스와핑

• 실행되지 않는 프로세스들을 보조기억장치의 일부영역으로 쫓아내고 생긴 빈 공간에 또 다른 프로세스를 적재하여 실행하는 방식
• 이 때 보조 기억 장치의 일부 영역을 스왑 영역
• 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것을 스왑 아웃
• 프로세스가 다시 메모리로 옮겨오는 것을 스왑 인

• 프로세스가 요구하는 메모리 주소 공간의 크기가 실제 메모리 크기보다 큰 경우에도 프로세스 동시 실행 가능!

메모리 할당

• 최초 적합, 최적 적합, 최악 적합이 있음

최초 적합 First Fit

• 운영 체제가 메모리 내 빈공간을 순서대로 검색 후 적재할 수 있는 공간 발견 시 그 공간에 프로세스를 배치
• 검색을 최소화, 결과적으로 빠른 할당이 가능

최적 적합 Best Fit

• 빈 공간을 모두 검색한 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 곳에 배치

최악 적합 Worst Fit

• 빈 공간을 모두 검색한 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 곳에 배치

위 세 방법 모두 외부 단편화라는 문제를 내포하고 있음

외부 단편화

• 메모리 할당을 한 후, 전체적인 빈 공간은 여유로우나 각각의 빈공간이 할당하고자 하는 프로세스보다 메모리 주소 공간이 적어 할당할 수 없는 상황

  

  출처 : https://velog.io/@mm723/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EC%97%B0%EC%86%8D-%EB%A9%94%EB%AA%A8%EB%A6%AC-%ED%95%A0%EB%8B%B9

해결 방안

1. 메모리 압축
   • 메모리 조각 모음이라고도 함
   • 여기저기 흩어져 있는 메모리들을 한 공간으로 만드는 것
   • 시스템은 하던 일을 중지해야 하고 메모리에 있는 내용을 옮기면서 오버헤드를 야기함..
   • 현재는 페이징 기법을 사용

페이징을 통한 가상 메모리 관리

페이징

• 메모리 공간과 프로세스를 일정한 크기로 자르고, 이 곳에 불연속 적으로 프로세스 조각, 메모리 조각을 적재하는 방식
• 논리 주소를 페이지라는 단위로 자름
• 물리 주소공간은 프레임단위로 자름 
• 모두 일정한 크기로 자른 뒤, 페이지를 프레임에 할당하는 방식

• 이 때 페이징 시스템에서, 스왑 아웃은 페이지 아웃, 스왑 인은 페이지 인이라고 불림

페이징을 사용하면, 프로세스 전체를 메모리에 적재할 필요가 없음!

페이지 테이블

• 프로세스가 메모리에 불연속적으로 배치되어 있으면, CPU입장에서는 순차적인 수행이 불가
• 프로세스를 이루는 페이지가 어느 프레임에 적재되어 있는지 알아야 함
• 이를 해결하기 위해 논리주소에 연속적으로 배치될 수 있도록 하는 페이지 테이블을 사용

내부 단편화

• 페이징이 야기할 수 있는 문제
• 일정한 크기로 잘리지 못할 때 발생!
  • 예를 들어, 프로세스의 크기가 108KB인데 10KB로 자르면, 8KB가 비게 되어 메모리 낭비 발생
• 따라서 페이지 테이블을 크기를 적당히하고, 내부단편화가 일어나지 않을 정도로만 설정하는 것이 중요

페이지 테이블 베이스 레지스터 Page Table Base Register

• 프로세스의 페이지 테이블이 적재된 주소를 가리키는 레지스터

  

• 만약 페이지 테이블에 해당 프로세스가 존재한다면 더 빠르게 프로세스를 이용할 수 있음
• 그러나 이렇게 이용을 하게되면, 메모리에 있는 페이지 테이블로 한번, 프레임에 접근하는데 한번 총 두번의 메모리 접근이 필요하게 됨
• 그래서 CPU에는 TLB가 있음
  • 참조 지역성에 근거하여 사용된 페이지 위주로 가져와 저장
• 논리 주소에 대한 페이지 번호가 TLB에 있으면 TLB 히트
• 없으면 TBL미스로 페이지 테이블에 접근해야만 함

페이징에서의 주소 변환

• 특정 주소에 접근하기 위해서는 다음과 같은 정보가 필요
  • 어떤 페이지, 프레임에 접근하고 싶은지?
  • 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지?
• 이런 이유로 페이징 시스템에서는 모든 논리 주소가 기본적으로 페이지 번호와 변위로 이루어짐
  • 예로, 32비트라면 N비트는 페이지 번호, 32-N 비트는 변위
• 이때 논리 주소의 변위와 물리 주소의 변위 값은 같다!

페이지 테이블 엔트리

• 페이지 테이블의 각각의 행을 뜻함
• 페이지 번호, 프레임 뿐만 아니라 유효 비트, 보호 비트, 참조 비트, 수정 비트 등 여러 정보가 담김

유효 비트

• 현재 해당 페이지에 접근가능한지 알려주는 비트
• 프레임 번호 다음으로 중요한 정보
• 현재 페이지가 메모리에 적재되어 있는지, 보조기억장치에 있는지를 알려준다.(메모리 1, 보조기억장치 0)
• 만약 비트가 0인 곳에 접근하려고 하면

페이지 폴트(Page Fault) 발생
1. CPU가 기존 작업 내역을 백업
2. 페이지 폴트 처리 루틴 실행
3. 페이지 처리 루틴은 원하는 페이지를 메모리로 가져온 뒤 유효 비트를 1로 변경
4. 처리했다면 이제 CPU가 해당 페이지에 접근할 수 있음

보호 비트

• 페이지 보호 기능을 위해 존재하는 비트
• 해당 비트를 통해 읽고 쓰기만 가능인지, 읽기만 가능한지 알 수 있음
  • 1일 경우 둘다, 0일경우 읽기만 가능

참조 비트

• CPU가 이 페이지에 접근한 적이 있는지 알려주는 비트
• 접근한 적 없으면 0 나머지 1

수정 비트

• 페이지에 데이터를 쓴 적이 있는지 여부를 알려주는 비트
• 더티 비트라고도 함
• 0이면 변경된 적이 없는 페이지
• 존재하는 이유
  • 페이지가 메모리에서 사라질 때, 보조기억장치에 쓰기 작업을 해야하는지 판단하기 위함

    

• 해당 메모리는 값이 변경되어, 보조기억장치에 적재하기 전에 값을 기록하는 작업이 필요함

페이지 교체와 프레임 할당

요구 페이징

• 프로세스를 메모리에 적재 시 처음부터 모든 페이지를 적재하는 것이 아닌 필요한 페이지만을 메모리에 적재
• 기본 적인 양상은 다음과 같음

1. CPU가 특정 페이지에 접근하는 명령어 실행
2. 해당 페이지가 현재 메모리에 있을 경우, CPU는 페이지가 적재된 프레임에 접근
3. 없을 경우 페이지 폴트 발생
4. 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재, 유효 비트 1로 설정
5. 다시 1번 수행

• 아무런 페이지도 메모리에 적재하지 않고 실행하면, 페이지 폴트가 계속 되다가 어느정도 진행되면 페이지 폴트 발생 빈도가 떨어짐
  • 이를 순수 요구 페이징이라 함 ( Pure Demand Paging )
• 요구 페이징이 안정적으로 작동하려면
  • 페이지 교체
  • 프레임 할당
• 이 두가지를 해결해야 함
• 페이지를 적재하다보면 언젠간 메모리가 가득차고, 이 때 사용하지 않는 페이지를 제거해야하는데, 이때 사용하는 것이 페이지 교체 알고리즘이다.

페이지 교체 알고리즘

• 페이지 폴트를 가장 적게 일으키면 좋은 알고리즘!
• 제대로 이해하기 위해서는 페이지 폴트 횟수를 알아야하고, 이는 페이지 참조 열을 통해 알 수 있음

페이지 참조열

• 쉽게 말해서, CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열

2 2 2 3 5 5 5 3 3 7 => 2 3 5 3 7

• 중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않아서, 굳이 볼 필요가 없음

FIFO 페이지 교체 알고리즘

• 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식
• 오래 머물렀음 나가!
• 프레임에 적재된 페이지가 교체될 때마다 페이지 폴트 발생

  

2차 기회 페이지 교체 알고리즘

• 자주 참조되는 페이지가 먼저 적재되었다는 이유만으로 빠지는 문제를 방지하기 위함
• 만약 교체 대상 페이지의 참조비트가 1이면, 0으로 바꾼 뒤 적재시간을 현재 시간으로 수정
• 0일 경우, 오래된 페이지 이면서 사용하지 않을 페이지이므로 교체 진행

  

 

최적 페이지 교체 알고리즘

• CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘
• 사용 빈도가 가장 낮은 페이지를 교체하는 방식

  

• 가장 효율적인 알고리즘이긴 하나, 실제 구현이 어려움
• 가장 오래 사용되지 않을 페이지를 예측하기 힘듬

LRU 페이지 교체 알고리즘 Least Recently Used Page Replacement Algorithm

• 가장 오래 사용되지 않은 페이지를 교체하는 기법
• 최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것이라는 가정

  

스래싱과 프레임 할당 Thrashing & Frame Allocation

• 페이지 폴트가 자주 발생하는 이유에 나쁜 페이지 교체 알고리즘만이 있는 것은 아님
• 프레임 수가 적어도 페이지 폴트는 자주 발생!
• 이처럼 페이지가 실제 실행되는 시간보다, 페이지 교체(페이징)에 시간을 더 많이 소모한다면, 이를 스래싱이라고 함

참고 - 멀티 프로그래밍의 정도

• 메모리에서 동시 실행되는 프로세스의 수를 멀티프로그래밍의 정도라고 함

참고2 - 프레임 할당 방식

• 각 프로세스에 균등하게 프레임을 할당하는 것을 균등 할당
• 프로세스의 크기에 따라 각기 다르게 프레임을 할당하는 것을 비례 할당

참고3 - 작업 집합

• 실행중인 프로세스가 일정 시간 동안 참조한 페이지의 집합

  

참고4 - 페이지 폴트 기반 프레임 할당

• 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을,
• 페이지 폴트율이 너무 낮으면 그 프로세스는 너무 많은 프레임을 가지고 있다.