[OS] 연속 메모리 할당, 단편화, 그리고 페이징

메모리 할당

• 초기에는 메모리를 연속적인 공간에 할당했다.
• 일반적으로 메모리는 운영체제를 위한 공간과 사용자 프로세스를 위한 공간으로 나뉜다.
• 연속적인 메모리의 할당에서, 여러개의 사용자 프로세스의 메모리는 어떻게 할당될까?

메모리 보호(memory protection)

• 프로세스가 자신이 소유하지 않은 메모리를 접근할 수 없게 강제할 수 있다.
• 상한 레지스터(limit register)와 재배치 레지스터(기준 레지스터, relocation register)로 메모리 보호를 할 수 있다.
• 
  1. CPU 스케쥴러가 context switch를 할때, 디스패처가 상한 레지스터와 재배치 레지스터에 해당 프로세스에 맞는 값을 적재한다.
  2. 상한레지스터로 CPU가 생성한 논리주소가 범위 내에 있는지 확인한다.
  3. MMU가 재배치 레지스터의 값을 더해 물리주소로 변환한다.

메모리 할당

• 가변 파티션 : 프로세스를 크기 변경이 가능한 파티션에 할당
• 처음에는 하나의 큰 hole이 있으나, 프로세스가 종료되고 메모리가 운영체제에 반납되면서 여러개의 hole이 생길 수 밖에 없다.

• 이때 발생하는 문제가 동적 메모리 할당 문제이다.

• 동적 메모리 할당 문제
  1. 최초 적합 : 첫 번째 사용 가능한 가용 공간 할당
  2. 최적 적합 : 사용 가능한 공간 중에서 가장 작은 것 택한다.
  3. 최악 적합 : 가장 큰 가용 공간 선택

단편화 (Fragmentation)

• 외부 단편화(external fragmentation) : 프로세스가 메모리에 적재되고 제거되는 일이 반복되다보면 가용 공간이 작은 조각으로 분산되어있다.
• 내부 단편화(internal fragmentation) : 일반적으로는 메모리를 아주 작은 공간으로 분할한 후에 프로세스의 요청에 따라 분할 크기의 정수배로 할당한다. 프로세스가 요구하는 메모리와 실제 할당된 메모리의 차이를 의미한다.

외부 단편화를 해결하기위해 압축(compaction)이라는 기법으로 메모리의 모든 내용을 한쪽으로 몰아주는 기법이 있는데, 비용이 너무 많이 사용된다.
이를 해결하기 위해 나온게 페이징이다.

페이징(Paging)

• 프로세스의 물리 메모리를 non-contiguous(비 연속적)으로 쪼개어
  • 외부 단편화를 회피하고
  • 압축(compaction)의 필요성을 회피한다.

방법

• 프레임(frame) : 물리적 메모리를 고정된 크기로 자른 블럭
• 페이지(page) : 논리적 메모리를 같은 크기로 자른 블럭
• 물리적 주소공간과 논리적 주소공간을 완전히 분리한다.

• CPU에서 나오는 모든 주소는 페이지 번호p와 페이지 오프셋d로 나뉘어진다.
  • 
  • 페이지 번호는 프로세스별 페이지 테이블에 접근할때 사용된다.
    • 
  • 페이지 오프셋은 페이지 번호로 얻은 물리 메모리의 frame의 시작주소로부터 떨어진 위치이다.
  • 0xffff와 같은 주소가 아니라는 말이다.

• CPU가 생성한 논리주소를 물리주소로 변환하기 위해선
  1. 페이지 번호 p를 페이지 테이블의 인덱스로 사용한다.
  2. 페이지 테이블에서 해당 프레임 번호 f를 찾는다.
  3. 논리주소의 p를 프레임번호 f로 변환한다.
     • 
     • 의 예시에서, 논리주소가 만약 (0, 5)라면, 페이지테이블에서 프레임 1을 찾을 것이고, 프레임 1의 시작주소로부터 5만큼 떨어진 부분이 물리주소가 될 것이다.

• 페이징 기법의 단편화
  • 외부단편화는 발생하지 않는다. : 모든 물리 메모리가 같은 크기로 나뉘어지므로, 해당 프로세스에서 사용되지 않는 프레임은 다른 프로세스에서 동일하게 사용될 수 있다.
  • 내부단편화는 발생할 수 있다. : 페이지가 모두 같은 크기로 잘리기때문에, 페이지 크기의 정수배가 프로세스가 요구하는 크기와 정확하게 일치하지 않는경우, 프레임은 내부 단편화가 발생한다.

• 페이지크기(프레임크기) 결정
  • 하드웨어가 결정한다.
  • 단, 4KB와 1GB사이의 2의 제곱으로만 페이지 크기를 할당한다.
  • 만약 논리적 주소공간의 크기가 2^m이고, 페이지 크기가 2^n이라면,
    • 논리주소의 상위 m-n 비트는 페이지 번호를 지정하고
    • n 하위 비트는 페이지 오프셋을 지정한다.
  • 페이지 크기가 2^n이라는 의미는, 각 페이지별로 최대 셀의 갯수가 2^n개라는 의미이므로,
  • 페이지 크기를 전체 주소공간의 크기에서 빼면 m-n bit가 페이지 번호를 지정함을 알 수 있다.

프레임 테이블(frame table)

• 운영체제는 프레임 테이블에 어떤 프레임이 사용중이고, 어떤 프레임이 할당되어있고, 총 프레임이 몇개인지에 대한 정보를 저장한다.
• 

하드웨어 지원

• CPU 스케쥴러가 context switch를 하면서 실행할 프로세스를 선택하면, 사용자 레지스터를 다시 로드하고, 사용자 페이지 테이블에서 해당 프로세스에 적절한 하드웨어 페이지 테이블을 다시 로드해야한다.
• 오늘날, 프로그램은 굉장히 크기에 페이지 테이블이 매우 큰데, 이를 위해 하드웨어적으로만(레지스터로만) 구현하는 것은 context switch 시 레지스터를 교체해야하므로, 비효율적이다.
• 따라서, 오늘날에는 페이지 테이블을 메인 메모리에 저장하고, 페이지 테이블 기준 레지스터(Page Table Base Register)가 페이지 테이블의 주소를 가리키고 있게한다.
• 다른 페이지 테이블을 사용할때는 이 레지스터의 값만 변화시키면 되므로, context switch 시간을 줄일 수 있다.
• 단, 메모리 엑세스를 ①페이지 테이블에 접근하고, ⓶페이지테이블을 사용해 실제 데이터에 접근으로 2번 해야하므로, 메모리 접근 시간이 오래걸린다.
• 이런 메모리 접근 시간을 해결해주는게 TLB(translation look-aside buffer)이다.

TLB(translation look-aside buffer)

• 작고, 빠른 특수한 하드웨어 캐시 메모리
• TLB에서 페이지를 찾을 수 있으면(TLB hit) 그에 상응하는 프레임 번호를 알려주는데, 하드웨어적인 접근으로 검색 속도가 매우 빠르다.
• 페이지 번호가 TLB에 없으면(TLB miss) 페이지 테이블에 의한 메모리 참조가 이루어진다.(느림)

• 실질 메모리 접근 시간(effective memory access time)
  • TLB hit: TLB에 페이지 번호가 존재한다.
  • TLB miss: TLB에 페이지 번호가 없다.
  • hit ratio: TLB hit이 얼마나 발생하는가에 따라 메모리 접근 시간이 달라진다.
    • 메인 메모리 접근시간이 10ns, 페이지 번호가 TLB에서 발견되면 원하는 데이터에 접근하는 시간이 10ns일때,
    • 80% hit ratio : 0.80 * 10(TLB가 반환한 프레임 번호로 데이터 접근) + 0.20 * 20(페이지 테이블 접근 + 실제 데이터 접근) = 12ns
    • 99% hit ratio : 0.99 * 10 + 0.01 * 20 = 10.1 ns

메모리 보호

• 연속적인 메모리 할당에서는 기준레지스터와 재배치 레지스터로 메모리 보호를 했지만, 페이징환경에서는 이게 불가능.
• 따라서, 페이징 환경에서는 page 별 protection bit로 메모리 보호를 한다.
• 각 페이지 테이블의 엔트리에 valid-invalid bit을 추가한다.
  • valid bit이면 이 페이지가 해당 프로세스의 합법적인 페이지를 나타내고,
  • invalid bit이면 이 페이지가 프로세스의 논리 주소 공간에 속하지 않는다는 것을 나타낸다.
• 

공유페이지 (shared page)

• 페이징의 장점은 공통적인 코드를 공유할 수 있다는 것이다.
  • 멀티 프로그래밍 환경에서 중요한 요소
• 표준 C라이브러리 libc 예시
  • 각각의 프로세스가 libc의 사본을 주소공간에 비효율적으로 적재할 수도 있지만,
  • 만약 코드가 재진입 코드(reentrant code)인 경우, libc에 대한 페이지를 공유할 수 있다.
  • 재진입 코드 : 실행중에 자기 자신의 코드를 바꿀 일이 없는 코드

• 3개의 프로세스의 libc의 페이지 테이블 엔트리가 동일하고, 각 엔트리는 동일한 물리적 공간을 참조하게된다.
• 재진입 코드일때, 모든 프로세스가 읽기 전용인 메모리를 사용하므로, 동기화문제는 발생하지 않는다.

페이지 테이블의 구조

• 현대 컴퓨터는 2^32, 2^64의 큰 주소 공간을 가지는데, 이 시스템에선 페이지 테이블이 상당히 커진다.
• 64bit 컴퓨터에서 4KB 페이지 크기를 가진 시스템의 페이지 테이블은 2^20의 100만개 이상의 4MB크기의 페이지 테이블을 가질 것이다.
• 이런 크기의 페이지 테이블도 연속적으로 메모리를 할당하지 않고, 여러 조각으로 나누어 페이지 테이블을 구성할 수 있다.

계층적 페이징

• 페이지 테이블 자체가 다시 페이징되게 하는 방법
• 32bit CPU, 페이지 크기 4KB(4048bit) 시스템에서 페이지 번호는 20bit, offset은 12bit인데, 페이지 번호 20bit를 다시 10 bit 페이지 번호와 10bit offset으로 나눈다.
  • 
  • 주소 변환이 outer page table에서부터 들어오므로 forward-mapped페이지 테이블이라고도 한다.
• 64bit CPU에서는 이런 2단계 페이징 기법을 사용하면
  • 
  • 이렇게 나타나므로, 바깥 페이지를 더 잘게 나눠야한다.
  • 

결국 메모리 접근을 위해선 아래와 같은 그림이 될 것이다.

• 64bit 구조에서는 계층적 페이징 기법을 사용하면 너무 많은 메모리 접근을 필요로하므로, 적합하지 않다.

해시 페이지 테이블

• 주소공간이 32bit보다 커지면 가상 주소를 해시로 사용하는 해시 페이지 테이블을 사용한다.

• 해시테이블의 각 엔트리는
  1. 가상 페이지 번호
  2. 사상되는 페이지 프레임 번호
  3. 연결리스트상의 다음 원소 포인터 를 가지고 있다.
• 알고리즘
  1. 가장 주소 공간으로부터 페이지 번호가 오면 그것을 해싱 2 해시 페이지 테이블에서 연결 리스트를 따라가며 첫 번째 원소와 가상 페이지 번호 비교
  2. 일치되면 페이지의 프레임 번호를 가져와서 물리 주소를 얻지만 일치되지 않는다면 연결리스트의 다음 원소로 같은일을 한다.
• 64bit 시스템에서 유용하게 변형된 클러스터 페이지 테이블이 있는데, 각 테이블의 각 엔트리가 여러 페이지를 가리킨다.

역 페이지 테이블

• 메모리 프레임마다 해당 프레임에 올라와있는 페이지 주소, 페이지를 소유한 PID를 표시하는 한 개의 항목을 할당한다.
• 시스템에 페이지 테이블이 1개만 존재하고, 테이블 내 각 항목은 메모리 한 프레임씩을 가리킨다.

스와핑(Swapping)

• 실제 물리적 메모리의 크기를 초과하는 프로세스를 실행하게끔해준다.
• 프로세스의 일부분이 실행중에 임시로 백업 장치(HDD)로 내보내어졌다가 다시 메모리로 되돌아 올 수 있다.
• 다중 프로그래밍에서 중요한 요소이다.

표준 스와핑

• 메인 메모리와 백업 저장장치 간에 전체 프로세스를 이동
• 실제 물리 메모리보다 많은 프로세스를 수용할 수 있다.
• 유휴시간이 많은 프로세스가 스와핑에 적합하다.

페이징에서 스와핑

• 표준 스와핑은 프로세스 전체를 이동해야하므로 시간이 오래걸려서 현대에는 사용되지 않는다.
• 대신, 프로세스의 페이지를 스왑할 수 있는 변형 스와핑을 사용한다.
• 프로세스 전체를 스왑하는 비용이 발생하지 않는다.
• 오늘날의 페이징은 페이징에서의 스와핑을 의미한다.
• 페이징은 가상 메모리와 함께 잘 작동한다.

• page-out : 페이지를 메모리에서 백업 저장장치로 이동
• page-in : 페이지를 백업 저장장치에서 메모리로 이동