메인메모리가 보통 자기 디스크로 구현되는 2차 저장장치(secondary memory)를 위한 캐시로 이용될 수 있다. 이런 기술을 가상 메모리(virtual memory)라고 부른다. 가상 메모리를 사용하는 두 가지 중요한 이유는
- 다수의 프로그램을 동시에 수행할 대 메모리를 효과적으로 공유할 수 있게 하고,
- 작고 제한된 크기의 메인 메뫼에서 프로그래밍해야 하는 제약을 제거하기 위해서이다
이 기법이 탄생한 지 50년이 지난 지금은 첫 번재이유로 널리 사용되고 있다.
다수의 가상 머신이 같은 메모리를 사용하는 경우를 살펴보자. 가상 머신이 각자 보호될 수 있도록 보장하고 각 프로그램은 자신에게 할당된 메인 메모리의 부분에만 읽고 쓸 수 있도록 보장해야 한다. 캐시가 한 프로그램의 활성화된 부분만을 담고 있는 것과 마찬가지로 메인 메모리도 많은 가상 머시의 활성화된 부분만을 담고 있어야 한다. 따라서 지역성의 원칙은 캐시뿐만 아니라 가상 메모리에도 적용된다. 가상 메모리는 메인 메모리뿐만 아니라 프로세서 까지도 효율적으로 공유하게 해준다.
가상 메모리 : 메인 메모리를 2차 저장 장치를 위한 캐시로 사용하는 기술
프로그램을 컴파일 할 때는 가상 머신이 다른 어던 가상 머신과 메모리를 공유할 지는 알 수 없다. 실제로 메모리를 공유하는 가상 머신은 가상 머신들이 수행되는 동안 동적으로 변하게 된다. 이러한 동적 상호 작용 때문에 각 프로그램들이 자신만의 주소공간(address space), 즉 이 프로그램에 의해서만 접근 가능한 분리된 메모리 영역에서 컴파일되어야 한다. 가상 메모리는 프로그램의 주소공간을 실제 주소(physical address) == 메인 메모리의 주소로 변환해준다. 이런 변환 과정이 한 프로그램의 주소 공간을 다른 가상 머신으로부터 보호(protection)하여 준다.
보호: 프로세서를 공유하는 여러 프로그램들이 프로세서, 메모리, 입출력 장치를 공유하면서도 의도적이든 비의도적이든 서로 간섭하지 않도록, 즉 다른 프로그램의 데이터를 읽거나 쓰지 않도록 하는 일련의 메커니즘. 운영체제를 사용자 프로그램으로부터 분리시킨다.
가상 메모리가 생겨나게된 두번재 동기는 사용자 프로그램을 메인 메모리의 크기보다 더 크게 작성할 수 있도록 해주는 것이다. 이전에는 프로그램이 메인 메모리보다 더 클 경우에는 프로그래머가 프로그램을 알맞게 조정해야만 한다. 즉 프로그래머는 프로그램들을 작은 조각으로 나누고, 이들이 서로 상관관계가 없도록 작성해야만 했다. 이와 같은 오버레이는 수행 도중 사용자 프로그램 제어 하에 적재되거나 제거되어야 한다. 프로그래머는 프로그램이 적재되지 않은 오버레이에 접근하지 않고 적재된 오버레이는 전체 메모리 크기보다 더 커지지 않도록 보장하여야 한다. 오버레이는 전통적으로 모듈로 구성되었으며 각 모듈은 코드와 데이터를 갖고 있다. 다른 모듈에 속한 프로시저 사이의 호출이 발생하면 한 모듈위에 다른 모듈이 겹쳐 써질 수 있다.
이와 같은 제약은 부담이다. 프로그래머를 해방시킨 가상 메모리는 자동으로 메인 메모리(physical memory)와 2차 기억장치로 구성되는 두 단계의 메모리 계층을 관리.
가상 메모리와 캐시에 사용되는 개념이 같을지라도 역사적 배경이 다르기 때문에 다른 용어를 사용하게 되었다. 가상 메모리 블록은 페이지(page)라고 불리고, 가상 메모리 실패는 페이지 부재(page fault)라고 불린다. 가상 메모리를 갖는 프로세서는 가상 주소(virtual address)를 만들어내고, 가상 주소는 하드웨어와 소프트웨어의 조합에 의해 메인 메모리 접근에 사용되는 실제주소(physical address)로 변환된다.
아래 그림은 메인 메모리에 사상된 페이지와 함게 가상 주소로 접근되는 메모리를 보여주고 있다. 이런 작업을 주소 사상(address mapping) 혹은 주소 변환(address translation)이라고 한다. 오늘날 가상 메모리에 의해 제어되는 2개의 메모리 계층은 일반적으로 개인용 휴대기기에서는 DRAM과 플래시 메모리 서버에서는 DRAM, 디스크이다.
가상 메모리는 재배치(relocation) 기능을 제공하여 수행될 프로그램의 적재를 단순화한다. 재배치는 프로그램에 의해 사용되는 가상 주소를 메모리에 접근하는 데 사용되기 이전에 다른 실제 주소로 사상시켜 준다. 오늘날 사용되는 가상 메모리 시스템은 프로그램을 고정된 크기로 이뤄진 블록(페이지)의 집합으로 재배치시킨다. 따라서 프로그램을 할당하기 위해 메모리에서 연속적인 블록을 찾아낼 필요가 업게 되었다. 대신에 운영체제는 메인 메모리 내에 충분한 페이지가 있는지만 확인하면 된다.
- 페이지 부재 : 접근하는 페이지가 메인 메모리 안에 존재하지 않을 때 발생하는 이벤트
- 가상 주소 : 가상 메모리에서의 위치를 나나태는 주소이며 메모리에 접근할 때 주소 사상에 의하여 실제 주소로 변환
- 주소 변환 : 주소 사상이라고도 부름. 가상 주소를 메모리 접근에 사용되는 주소로 사상시키는 과정
가상 메모리 시스템의 주소는 가상 페이지 번호(virtual page number) 및 페이지 변위(page offset)로 나눠진다. 아래 그림은 가상 페이지 번호가 실제 페이지 번호로 변환되느 것을 보여준다. 실제 페이지 번호는 실제 주소의 상위 부분으로 이뤄지는 반면에 변화되지 않은 페이지 변위는 하위 부분으로 구성된다. 페이지 변위 필드의 비트 수는 페이지의 크기를 결정한다. 가상 주소로 참조 가능한 페이지 수는 실제 주로소 참조 가능한 페이지 수와 같지 않아도 된다. 실제 페이보다 더 많은 가상 페이지 수를 갖는 것이 이점.
가상 메모리에서 전통적으로 페이지 부재(page fault)라고 부려온 실패에 처리되는 높은 비용을 줄이기 위해서 설계의 방법들이 제죄. 페이지 부재는 처리하는데 수백만 사이클이 소요됨. 보통 크기의 페이지의 경우 첫 번째 워드를 거내는 데 걸리는 시간이 거의 이러한 어머어마한 실패 손실 대문에, 가상 메모리를 설계 시 다음과 같이 중요한 결정들이 내려졌다.
- 페이지는 큰 접근 시간을 보상할만큼 충분히 커야 한다. 4KiB 내지 16KiB 크기가 오늘날 일반적. 새로운 데스크톱과 서버 시스템이 32KiB와 64KiB을 지원하도록 개발되고 있다. 그러나 새로운 임베디드 시스템들은 반대 방향으로 발전하고 있어 페이지의 크기가 1KiB
- 페이지 부재 발생률을 줄이는 구현이 바람직. 이를 위해 사용되는 주된 기법은 페이지를 완전 연관 방식으로 배치
- 페이지 부재는 소프트웨어 적으로 다러질 수도. 이 부담이 디스크에 접근하는 시간과 비교 시 작기 때문. 소프트웨어는 페이지를 어떻게 배치할 것인가를 위해 효율적인 알고리즘을 상용. 왜냐하면 실패율의 작은 감소로도 충분히 알고리즘의 비용을 보상할 수 있기 때문
- 가상 메모리에서 쓰기를 수행 시 즉시 쓰기 방식은 시간이 오래걸리기에 가상 메모리 시스템은 나중 쓰기 방식을 사용
세그멘테이션
가상 메모리에 관한 설명에서는 고정된 크기의 블록을 사용하는 페이징에 중점을 두고 있다. 이 방법 외에도 가변 크기의 블록을 사용하는 세그멘테이션(segmetation) 기법이 있다. 세그멘테이션 기법에서 주소는 세그멘트 번호와 세그먼트 변위의 두 부분으로 구성. 세그먼트 레지스터 값이 실제 주소로 사상되고 여기에 변위를 더하여 실질적인 실제 주소를 구한다. 세그먼튼느 그 크기가 다양하기 때문에 변위가 세그먼트 내에 있는가를 확인하는 것이 필요하다.
세그멘테이션의 주 용도는 보다 강혁한 보호 방법과 주소공간의 공유 방법을 제공하는 것이다. 대부분의 운영체제 교과서에서는 페이징 보다 세그멘테이션에 대해 훨씬 더 많은 설명. 또한 주소 공간을 논리적으로 공유하기 위한 세그먼트 사용에 대해서도.
세그멘테이션의 가장 큰 단점은 주소공간이 논리적으로 분리된 조각들로 분할되어, 세그먼트 번호와 변위 두 부분으로 된 주소를 사용해야 한다는 것이다. 이에 반해 페이징은 페이지 번호와 변위 사이의 경계가 프로그래머나 컴파일러에게는 보이지 않게 한다.
세그먼트는 컴퓨터 워드 크기를 변화시키지 않고 주소 공간을 확장하는 방법으로서도 사용되어 왔다. 이러한 시도는 프로그래머와 컴파일러가 꼭 알아야만 하는 두 개의 분리된 주소로 인해 생기는 성능 저하와 불편함으로 인해 성공적이지 못했다.
많은 시스템들은 주소 공간을 고정 크기의 큰 블록들로 나누는데, 이렇게 하면 운영체제와 사용자 프로그램 사이의 보호 기능이 단순화되고 페이징 구현의 효율성이 증대. 이런 블록도 세그먼트라고 부르는 경우가 있지만 이 방식은 가변 크기를 갖는 세그멘테이션 방식보다 훨씬 더 간단하고 사용자 프로그램에는 보이지 않는다.
페이지 배치와 다시 찾기
페이지 부재의 손실이 엄청나게 크기 때문에 시스템 설계자느 페이지 배치를 최적화함으로써 페이지 부재 발생 수를 줄이고자 한다. 가상 페이지가 어떤 실제 페이지로도 사상될 수 있게 하면 운영체제는 페이지 부재 발생 시 어떤 페이지든 마음대로 선택할 수 있다. 에를 들어 운영체제는 페이지 사용을 추적하는 정교한 알고리즘과 복잡한 자료구조를 사용해 앞으로 오랫동안 사용하지 않을 것 같은 페이지를 선택할 수 있다. 유연하고 효과적인 교체 방식을 사용함으로써 페이지 부재 방생률을 낮출 수 있고 완전 연관 페이지 배치 방식의 사용을 단순화할 수 있다.
완전 연관 방식을 사용하는ㄴ데 있어 가장 큰 어려움은 엔트리의 위치를 알아내는 것이다. 왜냐하면 상위 계층의 어디에도 있을 수 있기 때문이다. 완전 검색은 비실용적이다. 가상 메모리 시스템에서는 메모리를 인덱스하는 표를 사용한다. 이 구조는 페이지 테이블(page table)이라고 불리고 메모리 내부에 존재한다. 페이지 테이블은 가상 주소의 페이지 번호로 인덱스되어 있고 대응되는 실제 페이지 번호를 가지고 있다. 각 프로그램은 각자 자신의 페이지 테이블을 가지고 있으며 페이지 테이블은 그 프로그램의 가상 주소 공간을 메인 메모리로 사상한다. 메모리 내 페이지 테이블의 위치를 나타내기 위해 하드 웨어는 페이지 테이블의 시작 주소를 나타내는 레지스터를 포함하고 있다. 이 레지스터를 페이지 레지스터라고 부른다.
페이지 부재
가상 페이지의 유효 비트가 0이면 페이지 부재가 발생하며, 운영체제가 제어를 넘겨 받게 된다. 운영체제가 제어를 갖게 되면 계층의 다음 수준(자기 디스크)에서 그 페이지를 찾아야 하며, 요구된 페이지를 메인 메모리의 어디에 배치시킬 것인지를 결정해야 한다.
가상 주소 하나만으로 디스크 내에 그 페이지가 어디에 있는지를 바로 알 수 없다. 도서관 예로 되돌아가서 책의 이름만으로는 도서관 내 책의 위치를 알 수 없다. 대신 일람표를 뒤져 책을 찾아야만 서가 내의 책 위치를 알 수 있다. 이와 같이 가상 메모리 시스템에서는 가상 주소공간 내에 각 페이지의 디스크상 위치를 알고 있어야 한다.
메모리 내의 페이지가 언제 쫓겨날지를 미리 알 수 없기 때문에 운영체제는 대개 프로세스를 생성시킬 때 프로세스의 모든 페이지를 위한 공간을 플래시 메모리나 디스크 상에 마련한다. 이 디스크 상의 공간을 스왑 스페이스(swap space) 라고 부른다. 이때 가상 페이지가 디스크 어느 곳에 저장되는지를 기록하기 위한 자료구조를 만든다. 이 자료구조는 페이지 테이블의 일부일 수도. 아래 그림은 단일 테이블이 실제 페이지 번호나 디스크 주소를 담고 있을 때의 구조를 보여준다.
페이지 테이블을 가상 메모리의 각 페이지를 메인 메모리의 페이지나 디스크에 저장된 페이지로 사상한다
가상 페이지 번호는 페이지 테이블의 인덱스로 이용된다. 유효 비트가 1이면 페이지 테이블은 가상 페이지에 대응되는 실제 페이지 번호(즉 메모리상의 그 페이지의 시작주소)를 제공한다. 유효 비트가 0이면 페이지는 디스크상의 지정된 디스크 주소에 존재한다. 많은 시스템들에서 실제 페이지 주소와 디스크 페이지 주소 표는 논리적으로 한 개이지만 두 개의 분리된 자료구조에 저장. 현재 메인 메모리에 있는 페이지를 포함해 모든 페이지의 디스크 주소를 가지고 있어야 하므로 두 종류의 표를 사용하는 것이 좋다. 메인 메모리의 페이지와 디스크 페이지는 같은 크기를 갖는다는 점을 기억.
운영체제는 또한 어떤 프로세스와 어떤 가상 주소 각 실제 페이지를 사용하는지를 추적하는 자료구조를 만든다. 페이지 부재가 발생했을 때, 메인 메모리 내의 모든 페이지가 사용 중이면, 운영체제는 교체할 페이지를 선택해야만 한다. 페이지 부재의 수를 최소화해야 하기 때문에, 대부분의 운영체제는 가까운 시간 내에 사용되지 않을 페이지를 선정하려 한다. 미래를 예측하기 위해 과거를 사용하여, 운영체제는 이미 LRU 교체 방식을 따른다. 최근에 가장 덜 사용된 페이지가 더 자주 사용된 페이지보다 앞으로 이용될 가능성이 적다는 가정을 이용하여 가장 덜 사용된 페이지를 찾는다. 교체된 페이지는 디스크상의 스왑 스페이스에 쓰인다. 운영체제 또한 하나의 프로세스이며 메모리를 제어하는 테이블 또한 메모리에 위치한다. 얼핏 모순같이 보이는 이런 현상은 곧 다시 살펴보자.
하드웨어 스프트웨어 인터페이스
완벽하게 LRU 방식을 구현하는 것은 메모리를 참조할 때마다 자료구조를 갱신히야 하기 때문에 비용이 많이 든다. 대신에 많은 운영체제는 최근에 어떤 페이지가 참조되고 참조되지 않았는지를 추적하는 유식 LRU 방식을 사용한다. 운영체제가 LRU 페이지를 찾는 것을 돕기 위해, 어떤 시스템에선 페이지가 접근될 때마다 1값을 갖는 참조피트 또는 사용비트를 제공한다. 운영체제는 주기적으로 참조비트 0으로 만들고 후에 다시 기록한다. 이렇게 함으로써 특정 시간 동안 어떤 페이지들이 접근되었는지를 알 수 있다. 이 사용 정보를 이용해 운영체제는 최근에 가장 덜 참조된 것들(참조 비트가 0으로 된) 중 하나를 선택할 수 있다. 만약 이러한 비트들이 하드웨어적으로 제공되지 않는다면, 운영체제는 어떤 페이지가 접근되었는지를 예측하기 위한 다른 방법을 찾아야만 한다.
쓰기는 어떻게 처리되는가?
캐시의 접근 시간과 메인 메모리의 접근 시간 사이의 차이는 수십에서 수백 사이클 정도, 프로세서로부터 쓰기 지연 스간을 줄이기위해 쓰기 버퍼를 사용해서 즉시 쓰기를 이용할 수 있었다. 가상 메모리의 경우, 계층 구조의 다음 계층(디스크)에 쓰기는 수백만 사이클이 소요된다. 그러므로 디스크에 쓰기를 위해 시스템을 즉시 쓰기 방식으로 구현하고 쓰기 버퍼를 첨가하는 것은 매우 비실용적이다. 대신에 가상 메모리 시스템에서는 나중 쓰기 방식을 사용한다. 나중 쓰기 방식에서 각각의 쓰기 동작은 메인 메모리상의 페이지에만 수행된다. 그리고 페이지가 메모리에서 교체될 때 디스크로 복사가 된다.
하드웨어 스프트웨어 인터페이스
나중 쓰기 방식은 가상 메모리 시스템의 또 하나의 큰 장점 중 하나. 디스크의 전송 시간이 디스크 접근 시간보다 짧기 때문에 전체 페이지를 저장하는 것이 각각의 워드를 디스크로 저장하는 것보다 훨씬 더 능률적. 나중 쓰기 방식은 각각의 워드를 전송하는 것보다 능률적이지만 역시 추가되는 비용이 있다. 즉시 교체할 페이지가 결정되면 이 페이지가 디스크로 저장되어야 하는지를 알 필요가 있다. 메모리에 적재된 이후 페이지가 변화되었는지를 추적하기 위해, 페이지 테이블에 갱신 비트(dirty bit)를 추가한다. 페이지 내의 어떤 워드에 변화가 생길 때 이 갱신 비트가 1 값을 갖게 된다. 운영체제가 어떤 페이지를 바꾸기 위해 선택하면, 갱신 비트는 새로운 페이지에게 공간을 내주기 전에 그 페이지를 디스크에 써야 할지 여부를 알려준다. 그래서 수정된 페이지를 종종 갱신 페이지(dirty page) 라고 부른다.
주소 변환을 빠르게 하기: TLB
페이지 테이블은 메인 메모리에 저장되기 때문에, 프로그램에 의한 모든 메모리 접근은 최소한 두번 필요하게 된다. 실제 주소를 얻기 위한 메모리 접근 한 번과 데이터를 얻기 위한 또 한 번의 접근이 필요하다. 접근 성능을 높이기 위한 핵심은 페이지 테이블에 대한 참조의 지역성에 달려 있다. 어떤 가상 페이지 번호의 변환이 사용되면, 다시 참조될 가능성이 높다.
따라서 요즘의 컴퓨터들은 최근에 사용된 변환을 추적하는 특별한 캐시를 갖고 있다. 이 특별한 주소 변환 전용 캐시는 전통적으로 변환 참조용 버퍼(translation - lookaside -buffer)라고 불린다. 이 버퍼는 변환 캐시라고 부르는 게 더 정확한 표현, 페이지 테이블에 접근하는 것을 피하기 위해 최근에 사용된 사상을 보관하고 있는 캐시. 여러 책들의 위치를 종이에 기록하고 이 종이를 마치 캐시처럼 사용하는 것과 같다.
TLB는 실제 페이지로만 사상되는 엔트리를 위한 페이지 테이블의 캐시로 동작
TLB는 페이지 테이블에 있는 가상 주소-실제 주소 사상의 부분집합만을 포함. TLB 사상은 파란색으로 표시하였다. TLB는 캐시이기 때문에 태그 필드가 있어야 한다. 접근하려는 페이지와 일치하는 엔트리가 TLB 내에 없을 때 페이지 테이블을 조사해야 한다. 페이지 테이블은 페이지의 실제 페이지 번호를 제공하거나 (이 번호는 TLB의 엔트리로 저장됨), 페이지가 디스크상에 존재함(페이지 부재가 발생됨)을 표시. 페이지 테이블은 모든 가상 페이지 항목을 가지고 있기에 태그 필드가 필요하지 않다.
위 그림은 TLB의 각 태그 항목이 가상 페이지 번호의 일정 부분을 갖고 있고 TLB의 데이터 항목이 실제 페이지 번호를 갖고 있음을 보여준다. 이제는 각 참조마다 페이지 테이블에 접근하지 않고 TLB에 접근하기 때문에, TLB는 갱신(dirty) 비트와 참조(reference)비트 같은 다른 상태 비트들을 포함해야 한다.
참조 시마다 TLB의 가상 페이지 번호를 검사. 적중되면 실제 페이지 번호는 주소를 형성하는데 쓰이고, 대응되는 참조 비트는 1이 된다. 프로세서가 쓰기를 수행하면 갱신 비트도 1이 된다. TLB 내에서 실패가 발생하면, 이 실패가 페이지 부재인지 단순한 TLB 실패인지를 알아야 한다. 그 페이지가 메모리에 있으면, 그 변환이 TLB에 없을 뿐 페이지 부재는 아님을 의미. 이 경우에는 프로세서가 그 변환을 페이지 테이블로부터 TLB로 적재하고 참조를 다시 시도함으로써 TLB 실패를 처리할 수 있다. 그 페이지가 메모리에 존재하지 않으면 TLB 실패는 실제 페이지 부재가 된다. 이 경우에는 예외를 사용해 운영체제로 하여금 처리하게 한다. TLB는 메인 메모리 내의 페이지 개수보다 훨씬 더 적은 엔트리를 가지고 있기 때문에, TLB 실패는 실제 페이지 부재보다 더 빈번히 발생.
TLB 실패는 하드웨어로 처리할 수도, 소프트웨어로 처리할 수도 있다. 실제로 이 두 방법 모두가 수행해야 할 기본적인 동작이 길기에 두 가지 방법의 성능 차이는 없다.
TLB 실패가 발생되고 실패한 변환이 페이지 테이블로부터 인출되면 교체해야할 TLB 엔트리를 선정해야. TLB 엔트리 내에는 참조 비트와 갱신 비트가 포함되어 있기에 엔트리를 교체시킬 때 이 비트들도 페이지 테이블 엔트리에 저장해야 한다. 이 비트들만이 TLB 엔트리 중 변화될 수 있는 부분. TLB 실패율이 낮기에 나중 쓰기 방법을 사용하는 것이 효율적. 몇몇 시스템들은 참조 비트와 갱신 비트를 근사화 하는 다른 방법들을 사용. 이 방식들을 사용하면 실패 발생 시에 새로운 테이블 엔트리를 적재하기만 하면 되고 TLB에 쓰기는 하지 않아도 된다.
TLB의 일반적인 값들은 다음과 같다.
- TLB의 크기 : 16 - 512 엔트리
- 블록 크기: 1-2 페이지 테이블 엔트리(일반적으로 각각 4-8바이트)
- 적중 시간: 0.5 - 1 클럭 사이클
- 실패 시간: 10-100 클럭 사이클
- 실패율 : 0.01 - 1%
설계자들은 TLB 내에서 매우 다양한 연관 정도를 사용하였다. 어떤 시스템들은 완전 연관 사상 방식을 사용하는 작은 TLB를 사용한다. 왜냐하면 이 방법이 실패율이 작기 때문이다. 게다가 TLB의 크기가 작기 때문에 구현하는 비용도 많이 들지 않는다. 다른 시스템들은 때때로 작은 연관 정도를 갖는 큰 TLB를 사용한다. 완전 연관 사상 방법에서는 LRU 하드웨어를 구현하는 것이 비용이 많이 들기 때문에 교체할 엔트리의 선정이 쉽지 않다. 게다가 TLB 실패는 페이지 부재보다 더 빈번하고 값싸게 처리되어야만 하기 때문에 페이지 부재 시 사용했던 것과 같은 비싼 소프트웨어 알고리즘을 사용할 수 없다. 결론적으로 많은 시스템들은 교체할 엔트리를 임의로 선정하는 기능을 제공.
Intrinsity FastMATH의 TLB와 캐시가 가상 주소를 가지고 데이터를 인출하는 과정을 보여준다.
이 그림은 4KiB 페이지 크기로 가정했을 때 TLB와 데이터 캐시의 구성을 보여준다. 이 그림은 읽기 과정이고 아래 그림은 쓰기 처리 과정을 보여준다. 태그와 RAM 이 분리되어 있다. 블록 변위와 캐시 인덱스로 길고 좁은 데이터 RAM에 접근함으로써 16:1 멀티플렉서를 사용하지 않고도 원하는 워드를 선택할 수 있다. 캐시는 직접 사상 방식이지만 TLB는 완전 연관 방식. 완전 연관 TLB이므로 모든 TLB 태그가 가상 페이지 번호와 비교되어야만 한다. 관심 있는 엔트리가 TLB 내 어디든 위치할 수 있기 대문. 일치된 엔트리의 유효비트가 1이면 접근은 TLB적중. 이때 실제 페이지 번호와 페이지 변위 비트가 캐시에 접근하는데 사용되는 인덱스를 형성
Intrinsity FastMATH의 TLB와 캐시를 통한 읽기와 즉시 쓰기의 처리
TLB가 적중되면 캐시는 바로 실제 주소로 접근될 수 있다. 읽기 동작일 때 캐시가 적중되면 데이터를 공급. 실패이면 메모리에서 읽어오는 동안 지연되다. 즉시 쓰기 방식을 가정 시 그 작업이 쓰기라면 캐시 엔트리에 덮어 쓰고, 데이터는 쓰기 버퍼로 보내진다. 쓰기 실패는 메모리로부터 읽힌 후에 블록이 수정된다는 것만 제외하면 읽기 실패와 동일. 나중 쓰기 방식은 쓰기 발생 시 캐시 블록의 갱신 비트를 1로 만든다. 그리고 교체되어야할 블록이 변경되었을 경우 읽기 실패나 쓰기 실패가 발생할 때만 쓰기 버퍼에 전체 블록이 적재. TLB 적중과 캐시 적중은 독립적인 사건. 그러나 캐시 적중은 TLB 적중 이후에만 발생할 수 있다. 즉 데이터는 메모리에 있어야만 가능하다. TLB 실패와 캐시 실패의 관계는 다음 예제와 이 장 마지막에 있는 연습문제.
가상 메모리, TLB와 캐시의 통합
우리의 가상 메모리와 캐시 시스템은 계층 구조를 이루며 같이 동작한다. 따라서 데이터가 메인 메모리에 없다면 그 데이터는 캐시에 있을 수가 없다. 운영쳊는 페이지를 디스크로 옮기기로 결정하면 캐시에서 해당 페이지를 제고함으로써 이 계층구조를 유지하는 역할을 수행. 동시에 운영체제는 페이지 테이블과 TLB 수정함으로써 해당 페이지의 데이터에 접근하려고 시도하는 경우 페이지 부재를 일으키게 된다.
가장 좋은 경우는 가상 주소가 TLB에 의해 변환되고 캐시로 보내져서 원하는 데이터를 찾아내서 프로세서로 보내는 것이다. 가장 안 좋은 경우 참조가 메모리 계층구조의 모든 세 가지 요소, 즉 TLB, 페이지 테이블, 그리고 캐시에서 실패를 발생시키는 경우이다. 다음의 예는 이 관계를 더 자세히 설명
메모리 계층 구조의 전체적인 동작
TLB와 캐시로 이뤄진 위 그림과 같은 메모리 계층구조에서는 메모리 참조시 TLB 실패, 페이지 부재, 캐시 실패의 세 가지 다른 형태의 실패가 존재. 이 세 가지 종류의 조합(일곱 가지 가능성)을 살펴보자. 각 가능성에 대해 이 사건이 실제로 발생하는지 또는 어떤 환경에서 발생하는 지를 답하라.
위 그림에서는 모든 메모리 주소가 캐시에 접근되기 전에 실제 주소로 변환된다는 것을 가정. 이 구조에서는 캐시가 실제 주소로 인덱스되고(physically indexed) 실제 주소로 태그된다(physically tagged) (캐시 인덱스와 태그는 가상 주소가 아니고 실제 주소이다). 이러한 시스템에서 캐시 적중 시 메모리에 접근하는 시간은 TLB 접근 시간과 캐시 접근 시간을 포함해야 한다. 물론 이러한 접근 시간은 파이프라이닝 될 수 있다.
다른 방법으로는 프로세서가 완전히 또는 부분적으로 가상 주소를 이용해 캐시를 이덱스 할 수 있다. 이를 가상 주소 캐시(Virtually addressed cache)라고 부르며, 이는 가상 주소인 태그를 사용한다. 따라서 이 캐시는 가상 주소로 인덱스되고(virtually indexed) 가상 주소로 태그된다(virtually tagged) 이러한 캐시에서는 주소 변환 하드웨어 (TLB)가 정상 캐시 접근 시에는 사용되지 않는다. 캐시는 실제 주소로 변환되지 않은 가상 주소로 접근되기 때문이다. 이 방법은 TLB가 접근 경로에서 제외되기때문에 캐시 지연을 줄여준다. 그러나 캐시 실패가 발생하면 프로세서는 주소를 실제 주소로 변환하여 메인 메모리로부터 캐시 블록을 가져오도록 해야 한다.
캐시가 가상 주소로 접근되고, 페이지가 프로그램들 사이에 공유될 때(프로그램들은 다른 가상 주소로 접근할 수도 있음) 동의어 문제(aliasing)가 발생할 가능이 있다. 동의어 문제는 같은 객체가 두 개의 주소에 의해 접근되는 상황. 같은 실제 페이지가 두 개의 가상 주소가 존재하는 가상 메모리에서 발생할 수 있다. 이러한 모호함은 페이지 내의 워드가 각각 다른 가상 주소로 대응되는 두 개의 다른 캐시 블록에 들어갈 수 있기 때문에 문제를 발생시킨다. 이런 경우는 하나의 프로그램이 다른 프로그램은 데이터가 변화된 것을 모르는 상태에서 데이터를 바꿀 수 있게 한다. 완전히 가상 주소를 사용하는 캐시는 동의어 문제를 줄이기 위해 캐시나 TLB를 정교하게 설계하거나, 운영체제 또는 사용자가 동의어 문제를 줄이기 위해 캐시나 TLB를 정교하게 설계하거나, 운영체제 또는 사용자가 동의어 문제가 발생하지 않도록 조치를 취해야.
위의 두가지 설계 요소들 사이에 타협접으로서 다음과 같은 방법을 사용할 수 있다. 캐시는 가상 주소로 인덱스(때때로 주소의 페이지 변위 부분을 사용한다. 이는 번역되지 않았으므로 실제 주소) 실제 주소의 태그를 사용하는 방식이다. 가상 주소로 인덱스 되고 실제 주소로 태그되는 이 설계 방식은 실제 주소 캐시(physically addressed cache)의 단순한 구조에 힘입어 가상 주소 캐시보다 더 좋은 성능을 얻을 수 있다.
가상 메모리의 보호 구현
가상 메모리의 가장 중요한 기능 중의 하나는 여러 프로세스가 하나의 메인 메모리를 공유하도록 허용. 그러나 이 프로세스들과 운영체제 사이에 메모리 보호 기증을 제공하여야만 한다. 이 보호 기능은 다수의 프로세스가 같은 메모리를 공유한다 할지라도 아떤 악의를 품은 프로세스가 다른 사용자의 프로세스의 주소 공간에 쓰기를 수행하거나 고의적으로 또는 실수로 운영체제의 주소공간에 쓰기를 수앻할 수 없도록 보장해야만 한다. TLB의 쓰기 접근 비트가 페이지를 보호할 수 있다. 이 정도 수준의 보호조차 없다면 바이러스...!
또한 어떤 프로세스가 다른 프로세스의 데이터를 읽어오는 것도 막아야 한다. 예를 들어 성적이 프로세서의 메모리에 있는 동안 학생의 프로그램이 그 성적을 올 수 있게끔 만들지 말아야. 한 번 메인 메모리 공유가 허용되면, 다른 프로세스가 자신의 데이터를 읽거나 쓰지 못하게 하는 기능이 제공되어야 한다. 그렇지 않으면 메인 메모리는 뒤죽박죽될 것이다.
각 프로세스는 각각의 가상 주소공간을 가지고 있음을 기억하라. 그래서 만약 각각의 가상 페이지가 서로 분리된 실제 페이지로 사상되게끔 운영체제가 페이지 테이블을 구성하면, 어떤 프로세서스는 다른 프로세스 데이터에 접근할 수 없게 된다. 물론 이렇게 되기 위해서는 사용자 프로세스가 페이지 테이블 사상을 변화 시키지 못하게 해야 한다. 운영체제가 사용자 프로세스 스스로 자신의 페이지 테이블을 수정할 수 없게 하면 이런 것은 보장할 수 있다. 그러나 운영체제는 페이지 테이블을 수정할 수 있어야 한다. 페이지 테이블을 운영체제의 보호된 주소 공간에 배치함으로써 두 가지 요구를 만족시킬 수 있다.
페이지 부재
TLB 적중 시에는 TLB에서 가상 주소에서 실제 주소로의 변환이 곧바로 일어나지만 TLB 실패와 페이지 부재 시의 처리는 훨씬 복잡하다. TLB 실패는 TLB 내 엔트리가 가상 주소와 일치하는 거시 없을 때 발생한다. TLB 실패는 다음 두 가지 중의 하나이다.
- TLB 페이지가 메모리에 있는 경우 실패가 발생한 TLB 엔트리만 만들면 된다.
- 페이지가 메모리에 없는 경우 페이지 부재를 처리하기 위해 제어를 운영체제로 넘겨야 한다
MIPS는 전통적으로 TLB 실패를 소프트웨어로 처리. 메모리로부터 페이지 테이블 엔트리를 가져오고 TLB 실패를 발생시킨 명령어를 다시 수행한다. 다시 수행하면 TLB 성공이 될 것이다. 페이지 테이블 엔트리가 페이지가 메모리에 없다고 하면 페이지 부재 예외가 발생한다.
TLB 실패 혹은 페이지 부재 처리는 실행 중인 프로세스를 인터럽트 해, 운영체제로 제어를 넘기고, 중단된 프로세스를 나중에 계속 실행하는 예외 처리 방식을 이용한다. 페이지 부재는 메모리에 접근하는 클럭 사이클 도중에 인식된다. 페이지 부재를 처리하고 난 후 명령어를 다시 시작하기 위해서는 페이지 부재를 일으킨 명령어의 주소를 갖고 있는 프로그램 카운터 값이 저장되어야만 한다. EPC가 이 값을 저장하기 위해 사용된다.
TLB 실패 혹은 페이지 부재 예외는 메모리 접근이 발생하는 사이클의 끝 부분에서 처리되어야 한다. 다음 클럭 사이클이 정상적인 명령어 수행을 하는 대신에 예외 처리를 시작할 수 있도록 하기 위함. 페이지 부재가 이 클럭 사이클에서 인식되지 못하면, 적재 명령어는 레지스터의 내용을 바꺼버릴 수도 있고 혼란을 야기할 수도 있다. 예를 들어 명령어
lw $1, 0($1)이 수행될 때 시스템은 쓰기 파이프라인 단계가 동작하지 않도록 해야만 한다. 그렇지 않으면 $1의 내용이 지워져 버리기 때문에 그 명령어를 적절히 재수행시킬 수 없다. 저장 명령어의 경우도 마찬가지. 페이지 부재가 발생될 때는 메모리로 기록하는 것을 막아야 한다. 이런 것은 쓰기 제어 신호를 메모리에 인가하지 않음으로써 가능하다.
예외를 처리한 후 중단되었던 명령어 수행을 계속할 수 있게 다시 시작할 수 있는 명령어를 만드는 것은 MIPS 같은 구조에서는 비교적 쉽다. 각 명령어는 오직 하나의 데이터만을 쓸 수 있고 이 쓰기는 명령어 사이클의 맨 마지막 단계에서 수행되기 때문에, 명령어 수행이 완료되는 것을 막고(즉 쓰기를 못 하게 막고) 명령어를 처음부터 다시 수행시키기만 하면 된다.
MIPS를 좀 더 자세히 살펴보자. TLB 실패가 발생하면 MIPS 하드웨어는 BadVAddr이라고 불리는 특수 레지스터에 참조된 페이지 번호를 저장하고 예외를 발생시킨다. 예외는 소프트웨어로 실패를 처리한느 운영체제를 동작시킨다. 제어는 TLB 실패 핸들러(Handler)의 위치인 주소 8000 0000(hex)로 옮겨진다. 실패처리된 페이지의 실제 주소를 알기 위해 TLB 실패 처리 루틴은 가장 주소의 페이지 번호와 활성화된 프로세스 체이지 테이블의 시작 주소를 나타내는 페이지 테이블 레지스터를 사용하여 페이지 테이블을 인덱스한다.
이 인덱스 작업을 빠르게 하기 위해 MIPS 하드웨어는 필요한 모든 것을 Context 레지스터에 넣는다. 상위 12비트는 페이지 테이블의 시작 주소이고 다음 18비트는 실패가 발생한 페이지의 가상 주소이다. 각 페이지 테이블 엔트리의 크기는 한 워드이므로 마지막 2비트는 0이다. 따라서 처음 두 명령어는 Context 레지스터 값을 커널 임시 레지스터 $k1에 복사하고 그 주소의 페이지 테이블 항목을 여기에 적재시킨다. $k0와 $k1은 운영체제가 아무 때나 사용할 수 있게 예약되어 있음을 상기하라. 그 이유는 TLB 실패 핸들러가 빠르게 동작하도록 하기 위해서이다. 다음은 전형적인 TLB 실패 처리 기능 MIPS 코드의다.
TLBmiss:
mfc0 $k1, Context # copy address of PTE into temp $k1
lw $k1, 0($k1) # put PTE into temp $k1
mtc0 $k1, EntryLo # put PTE into special register EntryLo
tlbwr # put EntryLo into TLB entry at Random
eret # return from TLB miss exception위에 보인 것과 같이 MIPS는 TLB 갱신을 위한 특수 시스템 명령어 집합을 가지고 있다. 명령어 tlbwr은 제어 레지스터 EntryLo로부터 제어 레지스터 Random에 의해 선택되는 TLB 엔트리에 복사한다. Random은 무작위 교체를 수행하므로 기본적으로 규칙이 없는 카운터라고 보면 된다. TLB 실패는 12 클럭 사이클 정도가 소요된다.
TLB 실패 핸들러는 페이지 테이블 엔트리가 유효한지를 검사하지 않는다. TLB 엔트리 실패에 따른 예외는 페이지 부재보다 훨씬 더 자주 발생하므로 운영체제는 페이지 테이블 엔트리를 검사하지 않고 TLB에 넣은 후 명령어를 다시 수행시킨다. 만약 엔트리가 유효하지 않으면 또 다른 예외가 발생하고 운영체제는 페이지 부재로 인식하게 된다. 이와 같은 방법이 자주 발생하지 않는 페이지 부재에 대해서는 약간의 성능 저하를 초래하지만 자주 발생하는 TLB 실패를 빠르게 처리한다.
체이지 부재를 발생시킨 프로세스가 인터럽트를 당하게 되면 TLB 실패 핸들러와 다른 주소인 8000 0180(hex)로 제어를 옮기게 된다. 이것은 예외 처리를 하는 일반적인 주소이다. TLB 실패는 TLB 실패에 따른 손실을 줄이기 위해 특수한 시작 주소를 갖고 있다. 예외가 페이지 부재이기 때문에 운영체제는 많은 처리를 하여야 한다. 따라서 TLB 실패와는 다르게 활성화된 프로세스 모든 상태를 저장한다.
이 상태는 모든 범용 레지스터, 부동소수점 레지스터, 페이지 테이블 주소 레지스터, EPC와 예외 원인 레지스터를 모두 포함한다. 예외 핸들러는 일반적으로 부동소수점 레지스터를 사용하지 않으므로 이 레지스터를 사용하는 일부 핸들러들만 부동소수점 레지스터를 저장하고 일반 엔트리 포인트는 이를 저장하지 않는다.
아래 그림은 예외 핸들러의 MIPS 코드를 보여준다. 언제 예외 활성화할지 비활성화할지 고려하면 상태를 저장하고 또 복원하기 위해 어셈블리 코드를 사용하였다. 그러나 특정 예외를 처리하기 위해서는 C 코드를 사용한다.
페이지 부재를 일으킨 가상 주소를 찾는 방법은 페이지 부재가 명령어 부재인지 데이터 부재인지에 따라 달라진다. 부재를 일으킨 명령어의 주소는 EPC에 있다. 만약 명령어 페이지 부재인 경우 EPC가 부재된 페이지의 가상 주소를 가지고 있다. 데이터 부재의 경우 부재인 가상 주소는 명령어(주소는 EPC)에서 베이스 레지스터와 변위 값을 구해서 계산할 수 있다.
