[OS] 페이징: 개요

장선규·2023년 7월 30일
OSOSTEPPaging가상화운영체제페이징
0

[OS] OSTEP Study

목록 보기
13/28

페이징: 개요

운영체제는 공간 관리 문제를 해결할 때 크게 두 가지 방법으로 세그멘테이션이나 페이징을 사용한다.

  • 세그멘테이션: 가상 메모리를 "가변 크기"의 조각들로 분할

    • 공간을 다양한 크기의 청크로 분할할 때 공간 자체가 단편화 되는 단점
    • 단편화로 인해 할당이 점점 어려워짐

  • 페이징: 공간을 "동일 크기"의 조각으로 분할

    • 프로세스의 주소 공간을 논리 세그멘트(힙, 스택, 코드)로 나누는 것이 아니라 고정 크기의 단위로 나누는 것
    • 이 각각의 고정 크기 단위를 페이지(page)라고 함
    • 페이징 시 물리 메모리도 페이지 프레임(page frame)이라고 불리는 고정 크기의 슬롯의 배열이라고 생각
    • 이 프레임 각각은 하나의 가상 메모리 페이지를 저장할 수 있음
      (쉽게 생각하면, 물리 메모리는 페이지를 저장하는 슬롯, 리스트)

    핵심 문제: 페이지를 사용하여 어떻게 메모리를 가상화 할 수 있을까?

1. 간단한 예제 및 개요

예제 프로세스 & 물리 메모리

  • 예제 프로세스
    • 총 크기: 64바이트
    • 페이지 수: 4개 (0~3)
    • 페이지 크기: 16바이트
  • 예제 물리 메모리
    • 총 크기: 128바이트
    • 수용 가능 페이지 수: 총 8 페이지
    • 운영체제를 위해 예약된 물리 메모리도 존재

세그멘테이션과 같은 이전 방식에 비해 유연하다.

  • 페이징을 사용하면 프로세스의 주소 공간 사용 방식과는 상관없이 효율적으로 주소 공간 개념을 지원할 수 있다.
  • 힙과 스택이 어느 방향으로 커지는지 상관 x
  • 힙과 스택이 어떻게 사용되는지 알 필요 없음

또 다른 장점은 빈 공간 관리의 단순함이다.

  • 위의 예에서 64바이트 주소공간을 물리 메모리에 배치하길 원한다면, 운영체제는 비어있는 네 개의 페이지만 찾으면 됨 (빈 공간 리스트)
  • 위의 예에서 운영체제는 가상 페이지 0,1,2,3을 각각 물리 페이지 프레임 3,7,5,2에 배치

페이지 테이블

  • 프로세스마다 주소 공간의 각 가상 페이지에 대한 물리 메모리 위치를 기록하는 테이블
    (가상페이지 대 물리프레임 매핑)
  • 역할: 주소 공간의 가상 페이지 주소 변환 정보를 저장
    • 위의 예에서는 VP0->PF3, VP1->PF7, VP2->PF5, VP3->PF2 항목을 가짐
  • 페이지 테이블은 프로세스마다 존재 (역 페이지 테이블이라는 예외적인 기법도 있긴함)

주소 변환

  • 가상주소 -> 물리주소 변환을 위해 가상 페이지 번호(Virtual page number, VPN)이 필요
  • 위의 예에서는 가상 주소 공간의 크기가 64바이트이므로, 가상 주소는 6비트가 필요
    • 총 크기는 64바이트, 한 페이지의 크기는 16바이트이므로 총 4페이지를 선택할 수 있어야 한다.
      따라서 상위 2비트가 가상 페이지 번호를 가지게 된다.
    • 나머지 비트는 한 페이지 내에서 우리가 원하는 바이트의 위치를 나타내고, 이를 오프셋이라고 부른다.
    • ex) 가상 주소 21
      • 21 -> 010101(2) -> 01(VPN) 0101(오프셋)
      • 따라서 가상주소 21은 가상페이지 1번의 5번째 바이트이다.
      • 아까 페이지 테이블에 VP1->PF7이 저장되어 있으므로, 가상주소 1을 넣으면 물리 프레임 번호(Physical frame number, PFN)은 7이 나온다.
        (이때 오프셋은 상대적인 위치이므로 변하지 않는다.)

2. 페이지 테이블은 어디에 저장되는가

페이지 테이블은 세그먼트 테이블이나 베이스-바운드 쌍에 비해 매우 커질 수 있다.

  • ex) 페이지의 크기가 4KB인 32비트 주소 공간
    • 페이지 크기 4KB = 4096 = 2122^{12}
    • 따라서 32비트 주소공간에서 오프셋은 12비트이고, 그에 따라 VPN은 20비트
    • 20비트 VPN의 의미는 "운영체제가 각 프로세스를 위해 관리해야 하는 변환의 수가 2202^{20}개" (약 백만)
    • 만약 물리 주소로의 변환 정보와 다른 필요한 정보를 저장하기 위해 페이지 테이블 항목(Page table entry, PTE)마다 4바이트가 필요로 한다면 4MB의 메모리가 필요, 프로세스가 100개 실행중이면 주소 변환을 위해 400MB 필요...
  • 페이지 테이블은 매우 크기 때문에, 현재 실행 중인 프로세스의 페이지 테이블을 저장할 수 있는 회로를 MMU 안에 유지하지 않을 것
  • 대신 각 프로세스의 페이지 테이블을 메모리에 저장한다.
    (당분간 페이지 테이블은 물리 메모리에 상주한다고 가정)
    • PFN 0번지에 페이지테이블 존재

3. 페이지 테이블에는 실제 무엇이 있는가

선형 페이지 테이블(linear page table)

  • 가상 페이지 번호(VPN)를 물리 주소(PFN)로 매핑하는데 사용되는 단순한 배열
    • 가상 페이지 번호(VPN)로 페이지 테이블에 접근
    • 페이지 테이블 항목(PTE) 검색
    • 물리 페이지 번호(PFN)
  • 페이지 테이블 항목(PTE)
    • Valid bit: 특정 변환의 유효 여부를 나타내는 비트, 할당되지 않은 주소 공간 표현
    • Protection bit: 페이지가 읽을 수 있는지, 쓸 수 있는지, 실행될 수 있는지를 나타내는 비트
    • Present bit: 페이지가 물리메모리 혹은 디스크에 있는지 (=스왑 아웃 되었는지) 여부를 나타내는 비트
    • Dirty bit: 메모리에 반입된 후 페이지의 변경 여부를 나타내는 비트
    • Reference bit(accessed bit): 페이지가 접근되었는지를 추적 (페이지 교체에 매우 중요)
      • x86 아키텍쳐의 PTE
      • Present bit(P), Read/Write bit(R/W), Accessed bit(A), Dirty bit(D) 등 다양한 비트, 그리고 PFN 자체로 구성됨

4. 페이징: 너무 느림

페이지 테이블의 크기가 메모리 상에서 매우 크게 증가할 수 있고, 그로 인해 처리 속도가 저하될 수 있다.

  • 예시) 주소 21에 대해 참조하는 명령어 실행 (movl 21, %eax)
    • 하드웨어가 주소 변환 담당한다고 가정
    • 과정: 가상주소(21) -> 페이지 테이블에서 적절한 PTE 가져오기 -> 변환 수행 후 물리 메모리에서 데이터 탑재
    • 이렇게 하기 위해서, 하드웨어는 현재 실행 중인 프로세스의 페이지 테이블의 위치를 알아야함
      그러므로 페이지 테이블 베이스 레지스터가 페이지 테이블의 시작 (물리)주소를 저장한다고 가정
    • 원하는 PTE 위치를 찾기 위해 하드웨어는 다음과 같은 연산 수행
       //가상 주소에서 VPN 추출
 VPN = (VirtualAddress & VPN_MASK) >> SHIFT
 // 페이지 테이블 항목(PTE)의 주소 형성
 PTEAddr = PageTableBaseRegister + (VPN * sizeof(PTE))
      • VPN_MASK는 110000(2)으로 VPN 비트만 골라낸다
      • 이후 SHIFT는 4로 설정되어(오프셋 비트 수) VPN 비트를 오른쪽으로 이동
      • 가상주소 21(010101)을 마스킹하면 010000, 이후 쉬프트 연산을 하면 01 (가상페이지 1로 변환)
      • 이 값을 페이지 테이블 베이스 레지스터가 가리키는 PTE 배열에 대한 인덱스로 사용
      // PTE 반입
PTE = AccessMemory(PTEAddr)
// 오프셋 추출
offset = VirtualAddress & OFFSET_MASK 
// PFN과 가상주소의 오프셋을 연결하여 물리 주소 만들기
PhysAddr = (PTE.PFN << PFN_SHIFT) | offset
      • 하드웨어는 메모리에서 PTE를 반입
      • OFFSET_MASK는 001111(2)로 오프셋 비트만 골라낸다
      • PFN_SHIFT는 4로 설정되고(오프셋 비트 수), 이를 오프셋과 연결하여 물리 주소를 만든다
      Register = AccessMemory(PhysAddr)
      • 마지막으로 하드웨어는 메모리에서 원하는 데이터를 가져와서 레지스터에 넣음
    • 메모리 참조 전체 과정
      //가상 주소에서 VPN 추출
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
// 페이지 테이블 항목(PTE)의 주소 형성
PTEAddr = PageTableBaseRegister + (VPN * sizeof(PTE))
// PTE 반입
PTE = AccessMemory(PTEAddr) // <- 메모리 참조 1
// 프로세스가 페이지를 접근할 수 있는지 확인
if (PTE. Valid == False) 
	RaiseException(SEGMENTATION_FAULT)
else if (CanAccess(PTE. ProtectBits) == False)
	RaiseException(PROTECTION_FAULT)
else {
	// 접근 가능하면 물리 주소 만들고 값 가져오기	
	offset = VirtualAddress & OFFSET_MASK 
    PhysAddr = (PTE.PFN << PFN_SHIFT) | offset
    
	Register = AccessMemory(PhysAddr) // <- 메모리 참조 2
}
      • PTE 반입 시 메모리 참조, 그리고 레지스터에 데이터 넣을 때 메모리 참조, 총 두 번의 메모리 참조가 일어남
      • 메모리 참조는 비용이 비싸고, 이 경우에 프로세스는 2배 이상 느려진다.

페이징 기법을 쓸 때 해결해야 할 문제점 2가지
1. 소프트웨어 및 하드웨어 설계 잘못하면 페이지 테이블로 인해 시스템이 매우 느려질 수 있음
2. 너무 많은 메모리를 차지함

5. 메모리 트레이스

페이징을 사용했을 때 발생하는 모든 메모리 접근을 살펴보자

int arrray[1000];
...
for(i=0; i<1000; i++)
	array[i] = 0;
  • 위의 코드가 어떤 메모리 접근을 생성하는지 이해하기 위해 어셈블리어로 바꿔줌
// 값 0을 가상 메모리 주소 %edi로 옮긴다. %eax는 인덱스(i), 정수 배열이라서 4 곱해줌
0x1024 movl $0x0, (%edi,%eax,4)	
// %eax에 저장된 배열 인덱스 증가
0x1028 incl %eax 
// %eax의 값과 0x03e8(=1000)을 비교
0x102c cmpl $0x03e8,%eax	
// 위의 값이 같지 않다면 루프 상단(0x1024)으로 분기
0x1030 jne 0x1024
  • 이 명령어 시퀀스가 가상 및 물리 수준 모드에서 어떤 메모리 접근을 생성하는지 이해하기 위해서 몇가지 가정이 필요
    • 이 예에서 크기가 64KB인 가상 주소 공간을 가정, 페이지의 크기는 1KB로 가정
    • 테이블은 선형 페이지 테이블이고, 물리주소 1KB(1024)에 위치
    • 코드가 상주하는 가상 페이지의 가상주소는 1KB(1024)이며, 이는 가상 주소 공간의 두번째 페이지(VPN=1)이다. 또한 이 가상 페이지는 물리 프레임 4에 매핑됨 (VPN1->PFN4).
    • 크기가 4000바이트인 (1000개의 정수) 배열이 가상주소 40000에서 44000까지 존재한다고 가정. 이 범위의 가상 페이지는 VPN=39~42이며(페이지 크기 1KB이므로 4페이지 필요) 가상-대-물리 주소 매핑은 (VPN39->PFN7) VPN40->PFN8 VPN41->PFN9 VPN42->PFN10이다.
  • 프로그램이 실행되면, 각 명령어 반입 시에 메모리가 두 번 참조한다
    • 명령어의 위치를 파악하기 위해 페이지 테이블 접근 한 번 참조
    • 명령어 자체에 한 번 참조
  • 추가적으로 mov명령어도 메모리 참조를 함
    • 배열의 가상 주소를 올바른 물리 메모리 주소로 변환하기 위한 페이지 테이블 접근 한 번 참조
    • 다음 배열 자체를 접근하기 위해 한 번 참조
  • 처음 다섯 번의 루프 반복에 대한 전체 과정
    • 가장 위쪽 그래프가 페이지 테이블 메모리 접근 (페이지 테이블은 물리 메모리만 존재)
    • 가운데 그래프가 배열에 대한 접근 (왼쪽이 가상주소, 오른쪽이 물리주소)
    • 가장 아래쪽 그래프가 명령어 메모리 참조 (왼쪽이 가상주소, 오른쪽이 물리주소)
    • 루프당 10번의 메모리 접근
      • 4번의 명령어 반입 (코드부)
      • 한 번의 메모리 갱신 (배열)
      • 4번의 반입(코드부에 대응)과 한 번의 "명시적인 갱신을 위한 주소 변환(배열 갱신)"을 위한 총 다섯번의 페이지 테이블 접근

6. 요약

  • 페이징은 메모리를 고정 크기의 단위로 나눈다
  • 가상 주소 공간이 드문드문 사용되는 것을 허용
  • 근데 페이징 제대로 설계 못하면
    • 매우 느림 (페이지 테이블 접근을 위한 많은 추가적 접근)
    • 메모리 낭비 심함 (페이지 테이블로 가득 찰 수도)
  • 제대로 동작하는 페이징 시스템을 고안해야 한다
profile
장선규
코딩연습
이전 포스트

[OS] 빈 공간 관리

다음 포스트

[OS] 페이징: 더 빠른 변환 (TLB)

0개의 댓글