06. 가상 메모리

연속 메모리 할당

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

스와핑

swapping. 메모리에 적재된 프로세스 중 현재 실행되지 않는 프로세스들을 임시로 보조기억장치 일부 영역으로 쫓아내고 생긴 메모리상의 빈 공간에 또 다른 프로세스를 적재하여 실행하는 방식

• 스왑 영역swap space : 프로세스들이 쫓겨나는 보조기억장치의 일부 영역
• 스왑 아웃swap-out : 현재 실행되지 않는 프로세스가 메모리에서 스왑영역으로 옮겨지는 것
• 스왑 인swap-in : 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것

💡 프로세스가 스왑 아웃→스왑인 될 때, 이전 물리 주소와 다른 주소에 적재될 수 있음
💡 스와핑을 이용하면 프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리 크기보다 클 때도 프로세스들을 동시 실행할 수 있음.
💡 스왑 영역은 free, top 명령어를 통해 크기를 확인할 수 있음. 크기와 사용 여부는 사용자가 임의로 정할 수 있음. ex)free -h

메모리 할당

아래는 모두 연속할당에 해당

• 최초 적합first fit
  운영체제가 메모리 내 빈 공간을 순서대로 검색하다 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치
  • 검색 최소화, 빠른 할당 가능
• 최적 적합best fit
  운영체제가 빈 공간을 모두 검색한 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 프로세스 배치
• 최악 적합worst fit
  운영체제가 빈 공간을 모두 검색한 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스 배치
  

외부 단편화

external fragentation. 연속 메모리 할당은 외부 단편화 문제를 내포하고 있음
프로세스가 실행이 끝나고 메모리를 떠나면 해당 프로세스가 있던 자리는 빈공간이 됨. 메모리 사이사이에 빈공간이 생기고, 그 공간보다 큰 프로세스는 적재하기 어려워지므로 메모리 낭비로 이어짐

• 메모리 압축compaction
  외부단편화의 해결 방안. 메모리 내 저장된 프로세스를 적당히 재배치하여 흩어진 빈 공간들을 하나로 모으는 방법
  • 작은 빈 공간들을 하나로 모으는 동안 시스템은 하던 일을 중지해야함. 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기. 어떤 프로세스를 어떻게 움직여야 오버헤드를 최소화하며 압출할 수 있는지 명확한 방법을 결정하기 어려움

이에 등장한 것이 가상 메모리 기법 중 페이징 기법.

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

가상 메모리virtual memory
실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술. 페이징과 세그멘테이션이 있음

페이징

paging. 프로세스의 논리 주소 공간을 페이지page라는 일정 단위로 자르고, 물리 주소 공간을 프레임frame이라는 페이지와 동일한 크기의 일정단 단위로 자른 뒤 페이지를 프레임에 할당하는 메모리 관리 기법

페이징에서 스와핑은 페이지 단위로 스왑 아웃/인. (= 페이지 아웃/인)

즉, 한 프로세스를 실행하기 위해 프로세스 전체가 메모리에 적재될 필요가 없음. 프로세스를 이루는 페이지 중 실행에 필요한 페이지만 메모리에 적재하고, 당장 필요하지 않은 페이지는 보조기억장치에 남겨두면 됨.

페이지 테이블

page table. 프로세스가 메모리에(물리주소) 불연속으로 배치되어 CPU가 다음에 실행할 명령어 위치를 찾는 것이 어려워지는 것을 해결하기 위해 논리 주소(CPU가 보는 주소)에는 연속적으로 배치되도록 페이지 테이블을 사용

🐥 내부 단편화internal fragmentation
프로세스의 크기가 페이지 크기의 배수가 아닐 때 낭비되는 공간이 생김으로써 발생하는 메모리 낭비
하나의 페이지 크기를 작게 만들면 페이지 테이블이 차지하는 공간이 낭비될 수 있음
💡 리눅스의 경우 get conf PAGESIZE 로 페이지 크기를 알아낼 수 있음
💡 일부 운영체제에서는 기본적으로 설정된 페이지보다 크기가 큰 페이지를 일부 허용하며 메모리에 유지하는데, 이를 대형 페이지huge page라고 부름

각 프로세스마다 페이지 테이블을 가지고 있으며, 각 페이지 테이블들은 메모리에 적재 상태.
CPU 내의 페이지 테이블 베이스 레지스터(PTBR)에서 각 프로세스의 페이지 테이블이 적재된 주소를 가르켜줌

페이지 테이블을 메모리에 두게 되는 경우 메모리 접근 시간이 두배가 되는 문제가 생김
(1. 테이블 페이지 보기 2. 프레임에 접근하기)

이를 해결하기 위해 CPU 곁에 TLB(Translation Lookaside Buffer)라는 페이지 테이블의 캐시 메모리를 둠(보통은 MMU 내 위치)

• TLB hit : 페이지 번호가 TLB에 있을 경우
• TLB miss : 페이지 번호가 TLB에 없을 경우

페이징에서의 주소 변환

페이징 시스템에서는 모든 논리 주소가 기본적으로 페이지 번호page number와 변위offset으로 이루어짐
ex) 32bit 주소 → N비트 : 페이지 번호, 32-N : 변위
🐥 변위 : 접근하려는 프레임 주소가 프레임 시작번지로부터 얼마나 떨어져 있는가

1. (CPU가 본) 논리 주소
2. 페이지 테이블에서 프레임 번호 확인
3. 프레임 번호 위치의 (메모리) 물리 주소 + 변위

페이지 테이블 엔트리

페이지 테이블 각각의 행들을 페이지 테이블 엔트리PTE; page table entry
페이지 번호, 프레임 번호 이외에도 유효 비트, 보호 비트, 참조 비트, 수정 비트가 존재

• 유효 비트valid bit
  현재 해당 페이지 접근 가능 여부 알려줌. 프로세스를 이루는 모든 페이지가 메모리에 있지 않기 때문
  • 메모리 적재 : 1, 보조기억장치 위치 : 0
  • 페이지 폴트page fault : 예외Exception. 유효 비트 0인 페이지에 접근 시도
    1. CPU가 기존의 작업 내역 백업
    2. 페이지 폴트 처리 루틴 실행
    3. 페이지 폴트 처리 루틴은 원하는 페이지 메모리로 가져오고 유효비트 1로 변경
    4. 페이지 폴트를 처리했다면 CPU는 해당 페이지에 접근할 수 있음
• 보호 비트protection bit
  페이지 보호 기능
  • 읽기만 가능 : 0, 쓰기 읽기 모두 가능 : 1

    프로세스를 이루는 요소 중 코드영역은 읽기전용 영역. 읽기 전용 페이지에 쓰기 시도하면 운영체제가 막아줌

  • r(read), w(write), x(execute)로 더 자세히도 구현
    111은 읽기/쓰기/실행 모두 가능
• 참조 비트reference bit
  CPU의 해당 페이지 접근 여부 알려줌
  • 적재 이후 CPU 읽거나 씀 : 1, 적재 이후 한 번도 읽거나 씀X : 0
• 수정 비트modified bit (= 더티 비트dirty bit)
  해당 페이지의 수정 여부 알려줌. 페이지가 메모리에서 사라질 때 보조기억장치에 쓰지 작업을 해야하는지 판단하기 위해 존재
  • 변경된 페이지 : 1, 변경되지 않은 페이지 : 0

💡 페이징 이점 - 쓰기 시 복사copy on write

• 부모 프로세스와 동일한 자식 프로세스가 생성되면, 자식 프로세스가 부모 프로세스와 동일한 프레임 가리킴. 읽기 작업만 한다면 이 상태 지속.
• 부모/자식 프로세스 중 하나가 페이지에 쓰기 작업을 하면 그 순간 해당 페이지가 별도의 공간으로 복제, 각 프로세스는 자신의 고유한 페이지가 할당된 프레임 가리킴(수정된 페이지만 다른 프레임)

💡 계층적 페이징hierarchical page(= 다단계multilevel 페이지 테이블)
프로세스를 이루는 모든 테이블 엔트리를 항상 메모리에 유지하지 않을 수 있는 방법. 페이지 테이블을 페이징하여 여러 단계의 페이지를 둠페이지 테이블을 쪼개고 페이지들을 가르키는 페이지 테이블을 둠
논리 주소 : 바깥 페이지 번호 | 안쪽 페이지 번호 | 변위
❗ 페이지 테이블의 계층이 늘어날 수록 페이지 폴트가 발생했을 때 메모리 참조 횟수가 많아짐

1. 바깥 페이지 번호를 통해 페이지 테이블의 페이지 찾기
2. 페이지 테이블의 페이지를 통해 프레임 번호찾고 변위 더하면 물리 주소

페이지 교체와 프레임 할당

요구 페이징

demand paging. 프로세스를 메모리에 적재할 때 필요한 페이지만 메모리에 적재하는 기법

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

💡 순수 요구 페이징pure demand paging
아무런 페이지도 메모리에 적재하지 않은 채 무작정 실행부터 함
프로세스의 첫 명령어를 실행할 때부터 페이지 폴트가 계속 발생. 실행에 필요한 페이지가 어느정도 적재된 후 페이지 폴트 발생 빈도↓

요구 페이징 시스템이 안정적으로 작동하기 위해 1. 페이지 교체, 2. 프레임 할당 이 해결되어야 함.

페이지 교체 알고리즘

메모리에서 쫓아낼 페이지를 결정하는 방법. 페이지 폴트를 가장 적게 일으키는 것이 좋음

페이지 폴트 횟수 : 페이지 참조열page reference string을 통해 알 수 있음

🐥 페이지 참조열page reference string
CPU가 참조하는 페이지 중 연속된 페이지를 새약한 페이지열
ex) 2 2 2 3 5 5 5 3 3 7페이지 접근 → 2 3 5 3 7 : 페이지 참조열
페이지 폴트 횟수는

• FIFO 페이지 교체 알고리즘First In First Out Page replacement Algorithm
  메모리에 가장 먼저 올라온 페이지부터 내쫓음. "오래 머물렀다면 나가라"
  • 프로그램 실행 내내 사용될 내용을 포함하고 있을 수도 있으므로 마냥 좋진 않음

💡 2차 기회 페이지 교체 알고리즘second chance page replacement algorithm
FIFO 페이지 교체 개선. 페이지의 참조비트가 1인 경우 당장 내쫓지 않고 참조비트를 0으로 만든 후 현재 시간을 적재 시간으로 설정

• 최적 페이지 교체 알고리즘optimal page replacement algorithm
  CPU에 의해 참조되는 횟수를 고려. 사용 빈도가 가장 낮은 페이지를 내쫓음
  앞으로 오랫동안 사용되지 않을 페이지를 내보냄
  • 페이지 폴트의 빈도가 가장 낮음. but 앞으로 오랫동안 사용되지 않을 페이지 예측 어려움. 운영체제에서는 안쓰임
• LRU 페이지 교체 알고리즘Least Recently Used Page Replacement Algorithm
  가장 오랫동안 '사용되지 않은' 페이지 교체.
  '최근 사용되지 않은 페이지는 앞으로도 사용되지 않을것'
  

스래싱과 프레임 할당

스래싱thrashing

프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요해 성능이 저해되는 문제. 지나치게 빈번한 페이지 교체로 CPU 이용률이 낮아짐

🐥 멀티프로그래밍의 정도degree of multiprogramming
메모리에서 동시 실행되는 프로세스의 수 동시 실행 프로세스의 수를 지나치게 늘이면 각 프로세스들이 사용할 수 있는 프레임 수가 적어져 페이지 폴트 빈번히 발생하여 CPU이용률도 낮아짐
→ 동시 실행 프로세스의 수가 증가한다고 CPU 이용률이 비례해서 증가하지X

각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문에 스래싱 발생

프레임 할당 - 정적 할당 방식

프로세스 실행과정 고려X, 단순히 프로세스 크기와 물리 메모리 크기만 고려

• 균등 할당equal allocation
  모든 프로세스에 프레임 균등하게 할당
  • 프로세스 크기는 제각각이라서 비효율적
• 비례 할당proportional allocation
  프로세스의 크기가 크면 프레임 많이 할당, 작으면 적게 할당
  

프레임 할당 - 동적 할당 방식

프로세스의 실행을 보고 할당할 프레임 수 결정

• 작업 집합 모델working set model
  프로세스가 일정 기간동안 참조한 페이지 집합(작업 집합working set)을 기억해 빈번한 페이지 교체 방지
  (참조 지역성의 원리!)
• 페이지 폴트 빈도PFF; Page-Fault Frequency
  페이지 폴트율에 상한선과 하한선을 정하여 이 범위 안에서만 프레임 할당