페이징

해당 게시글은 kocw에서 제공하는 금오공과대학교 최태영 교수님의 무료 강의를 공부하고 정리하기 위해서 만들어졌습니다.

Paging

• 세그먼트로 처리하기 위해 주소 변환을 하다보면 logical 에서 physical로 변환하는 비용이 발생하게 된다.
  • 결국 세그먼트를 사용한 이유는 결국 fragment 문제를 해결하기 위함이다.
• 이 것을 막기 위해 하드웨어 기능인 paging을 사용한다.
• fragment(빈 작은 공간)가 생기지 않게 아예 메모리 자체를 잘라서 관리한다.
• physical memory에서 잘라진 것 하나하나를 Frame이라고 한다.
• 사용자가 보는 logical memory에서 잘라낸 것을 Page라고 한다.
  • frame이 4kb 단위로 잘라졌다면 page도 마찬가지로 4kb 단위로 잘라진다.
• 10kb 짜리 프로세스가 들어온다면,
• 3개의 페이지가 사용된다.
  • 3 * 4kb = 12kb
• 이런식으로 10kb 프로세스가 들어가고 남는 공간 2kb는 internal fragmentation이다.
• logical memory는 필요한 페이지들만 만들어 지고, physicial memory 영역에서 빈 프레임을 찾게 된다.
  • 여기서는 빈 프레임 3개가 쓰인다.
• 이런 프레임은 bitmap으로 관리된다.
  • 각 프레임이 비어있는지 비트로 관리한다.
• bitmap에서 빈 프레임을 찾으면 페이지와 프레임을 매핑한다.
• 매핑된 프레임에 하드디스크에서 4kb씩 꺼내와 메모리에 올리게 된다.
• 이렇게 되면 이 매핑된 주소를 MMU에서 변환을 시켜주어야 한다.
• 매핑된 정보는 테이블로 관리되는데 이것을 Page Table이라고 한다.
  • 페이지가 0번이면 매핑된 프레임 정보를 0번째 위치에 넣어준다.
  • 0번 page: 3번 frame
• 페이지 테이블도 마찬가지로 메모리에 존재하게 되고,
• MMU에서는 페이지 테이블의 위치를 알기 위한 레지스터가 관리된다.
  • PTBR
• 페이지 테이블 또한 세그먼트와 마찬가지로 프로세스마다 존재한다.
• 세그먼트와 페이징이 다른 것은
  • 세그먼트는 각각의 세그먼트 마다 크기가 다 다르지만
  • 페이지는 각 페이지마다 일정한 크기를 가진다.
  • 이렇게 일정한 크기를 가지면서 MMU의 속도를 높일 수 있다.

Address Translation Scheme

• paging은 항상 2의 지수승으로 메모리를 자르게 된다.
• 어떤 주소를 페이지의 크기로 나누게 된다면
  • 메모리 주소 5000번을 4096으로 나누면
  • 몫은 1이 되고 나머지는 904가 된다.
• page의 logical address를 보면,
  • 32bit를 기준으로
    • 20bit는 페이지 순서
      • page
    • 12bit는 페이지 안의 메모리 주소 위치
      • offset
  • 5000번은 항상 1번 메모리의 904번 위치에 존재하게 된다.
  • 이렇게 항상 정해진 크기이기 때문에 나눗셈이 쉬워진다.
• 이렇게 가져온 logical address를 MMU에 전달한다.
• MMU는 Page table에서 페이지 번호에 매핑된 프레임 번호를 가져온다.
• 이런식으로 가져온 프레임 번호를 페이지 번호 위치에 설정한다.
• offset은 그대로 유지하며, 이렇게 되면 3번 프레임에 904번 메모리 위치에 존재한다는 것을 알 수 있다.

Paging의 문제

• 페이징을 쓰게 되면 Internal fragmentation이 필연적으로 생길 수 밖에 없다.
• 이러한 Internal fragmentation을 줄이려면 페이지의 크기를 줄여야 한다.
• 페이지의 크기를 줄이면, 하드디스크를 읽어오는 오버헤드가 증가하게 되기 때문에 마냥 크기를 줄일 수만은 없다.
  • 하드디스크에서 데이터를 읽어오려면 원판의 헤더부터 시작하여 읽어올 데이터로 이동해야 한다.
    • 이 과정을 seek라고 한다.
  • 그러고 나서 읽어올 데이터 위치가 올 때까지 원판이 돌길 기다려야 한다.
    • 이 과정을 rotate라고 한다.
  • 하드디스크를 읽어오는 과정은 반드시 위 두 과정을 거쳐야 하기 때문에 최대한 많은 데이터를 읽어오는 것이 성능면에서 유리하다.
  • 그러나 페이지의 크기를 줄이면 줄일수록 이러한 데이터를 가져오는 과정이 많이 지기 때문에 오버헤드가 증가한다.
• 따라서 페이지 크기를 결정하기 위해서는 서로 트레이드오프할 수 밖에 없다.
  • 크기를 줄이면 하드디스크를 읽어오는 오버헤드 증가
  • 크기를 늘리면 internal fragmentation 증가

Implementation of Page Table

• page table을 사용하는 MMU를 구현하기 위해서는,
• 페이지 테이블 위치를 저장할 PCBR 레지스터를 가져야 하고,
• 이 레지스터에 가져올 정보는 PCB의 한 필드로 존재한다.
• 따라서 프로세스를 읽어오면 해당 프로세스의 PCB에서 페이지 테이블 위치를 꺼내오게 된다.
• 그러나 이러한 과정을 거치면 메모리를 읽기위한 메모리 참조가 발생하기 때문에 Contiguous Allocation 방식보다 성능이 좋지 않아지게 된다.
  • page table은 메모리에 존재하기 때문
• 이 것을 해결하기 위해 페이지 테이블의 일부를 캐시에 담아 둔다.
  • 이 캐시를 TLB(Translation Look-aside Buffers)라고 한다.
• TLB는 Associative Memory로 만들어져 있다.
• Associative Memory는 일반적인 테이블이 아니며, 각 엔트리는 두 개의 값으로 이루어져 있다.
  • key: page 번호가 있다.
  • data: frame 번호가 있다.
• 이 테이블은 입력이 들어올 경우 입력을 복사하여 각 엔트리마다 key가 입력에 해당되는지 검사하고, 맞을 경우 data를 리턴해준다.
• 이런식으로 리턴된 값이 있는 것만 회로에서 판단하여 전달해준다.
• 이 Associative Memory를 사용하는 이유는 엔트리의 개수와 상관없이 항상 검색 시간이 O(1)만 걸린다는 점 때문이다.
  • 병렬적으로 검색하기 때문
• 단점은 크기가 커질수록 복잡해지기 때문에 가격이 올라간다.
• TLB는 빨라야 하기 때문에 레지스터 보단 느리지만 메모리 보단 (1000배 정도)빠른 하드웨어로 이루어져 있다.

Memory Protection

• 페이징을 사용하면 MMU에서 검새해야 할 것은 logical address에서 현재 페이지 번호의 유효성이다.
• 그것을 하기 위해 두가지 방법이 있는데,
• 1. 각 페이지 테이블의 엔트리마다 valid/invalid bit를 하나 두는 방식
  • invalid할 경우 해당 페이지는 트랩에 걸려 쫓겨나게 된다.
• 2. PTLR를 활용하여 현재 페이지 번호가 레지스터 값보다 큰지 확인하는 방식
  • 클 경우 트랩을 걸어 프로세스를 죽여버린다.