Search
Duplicate

컴퓨터 구조 및 설계/ 메모리 계층구조

서론

여러분이 도서관에서 책을 찾는 방법과 프로그램이 동작하는 방법에는 지역성의 원칙(principle of locality)이 똑같이 적용된다. 어떤 순간에 사용하는 책은 도서관의 모든 책 중에서 극히 일부이듯이, 프로그램은 어떤 특정 시간에는 주소공간 내의 비교적 작은 부분에만 접근한다는 것이 지역성의 원칙이다. 지역성에는 다음과 같이 두 종류가 있다.
시간적 지역성(temporal locality)
만약 어떤 항목이 참조되면 곧바로 다시 참조되기가 쉽다. 즉 여러분이 어떤 정보를 찾기 위해 책을 책상으로 가지고 왔다면 곧바로 그 책을 다시 찾아보게 될 가능성이 매우 크다.
공간적 지역성(spatial locality)
어떤 항목이 참조되면 그 근처에 있는 다른 항목들이 곧바로 참조될 가능성이 높다. 예컨대 EDSAC에 대한 내용을 찾기 위해 초창기 영국 컴퓨터에 대한 책들을 찾아왔다면 서가의 그 책 주위에 초창기 기계식 컴퓨터에 대한 다른 책들이 있을 것이다. 같은 주제에 대한 책들은 공간적으로 지역성을 높이기 위해 서가에 함께 정리되어 있다.
프로그램에서의 지역성은 단순하고도 자연스러운 프로그램 구조에서 나온다.
예컨대 대부분의 프로그램들이 순환문 구문을 갖고 있고 순환문은 명령어와 데이터에 반복적으로 접근하므로 상당히 큰 시간적 지역성을 보여준다.
또 명령어들은 대개 순차적으로 접근되기 때문에 큰 공간적 지역성을 보여준다. 데이터 접근에도 자연스럽게 공간적 지역성이 나타난다. 예컨대 배열이나 레코드들의 요소에 접근할 때는 대개 큰 공간적 지역성을 갖는다.
컴퓨터의 메모리를 메모리 계층구조(memory hierarchy)로 구현함으로써 지역성의 원칙을 이용할 수 있다.
메모리 계층구조는 서로 다른 속도와 크기를 갖는 여러 계층의 메모리로 구성되어 있다. 가장 빠른 메모리는 더 느린 메모리보다 비트당 가격이 비싸기 때문에 대개 그 크기가 작다.
그림 5.1에서 빠른 메모리는 프로세서에 가깝게 두고, 느리고 싼 메모리를 그 아래에 두었다. 메모리 계층구조의 목적은 사용자에게 가장 빠른 메모리가 갖고 있는 접근 속도를 제공하면서 동시에 가장 싼 기술로 최대한 큰 메모리 용량을 제공하는 것이다.
데이터도 이와 유사한 계층구조를 갖는다. 프로세서에 가까운 계층은 먼 계층의 부분집합이고, 가장 낮은 계층에는 모든 데이터가 다 저장되어 있다.
책장의 예와 같이 책상 위의 책들은 그 책을 찾아온 단과 대학 도서관의 부분 집합이며, 또 캠퍼스 내 모든 도서관의 부분집합이다. 게다가 캠퍼스 내 도서관의 계층구조와 같이, 프로세서에서 멀어지면 멀어질수록 그 계층에 접근하는데 시간이 오래 걸린다.
메모리 계층구조는 여러 계층으로 구성되지만 데이터는 인접한 두 계층 사이에서만 한 번에 복사가 된다. 따라서 여기에서는 계층을 두 개로 한정해서 설명한다.
상위 계층(즉 프로세서에서 가까운 계층)은 더 비싼 기술을 사용하므로 하위 계층보다 작으며 빠르다.
그림 5.2에 보인 바와 같이 이 두 계층 간 정보의 최소 단위를 블록(block) 또는 라인(line)이라 한다. 예컨대 도서관의 경우에는 블록을 책 한 권에 비유할 수 있다.
프로세서가 요구한 데이터가 상위 계층의 어떤 블록에 있을 때 이를 적중(hit)이라 부른다. (즉 책상 위의 책 중에서 정보를 찾아낸 것과 같다)
그리고 상위 계층에서 찾을 수 없다면 이를 실패(miss)라고 부른다. 이때는 필요한 데이터를 포함하는 블록을 찾기 위해 하위 계층 메모리에 접근하게 된다. (즉 책상에서 일어나 필요한 정보를 찾기 위해 서가를 찾는 것과 같다)
적중률(hit rate 또는 hit ratio)은 메모리 접근 중 상위 계층에서 찾을 수 있는 것의 비율로서 메모리 계층의 성능을 평가하는 척도로 이용된다.
실패율(miss rate, 1- 적중률)은 메모리 접근 중 상위 계층에서 찾을 수 없는 것의 비율을 말한다.
메모리 계층구조를 만든 가장 큰 이유는 성능 향상이기 때문에 적중과 실패의 처리 속도가 매우 중요하다.
적중 시간(hit time)은 메모리 계층구조의 상위 계층에 접근하는 시간이며 이 시간에는 접근이 적중인지 실패인지를 결정하는데 필요한 시간이 포함된다. (즉 책상의 책들으 찾아보는데 걸리는 시간과 유사함)
실패 손실(miss penalty)은 하위 계층에서 해당 블록을 가져와서 상위 계층 블록과 교체하는 시간에다 그 블록을 프로세서에 보내는데 걸리는 시간을 더한 값이다. (즉 서가에서 다른 책을 찾는 시간과 책상에 가져오는데 걸리는 시간)
상위 계층은 작고 빠른 메모리를 사용하여 만들어졌기 때문에 적중 시간은 실패 손실의 주요한 부분을 차지하는 다음 계층에 접근하는 시간보다 훨씬 적게 걸린다. (즉 책상 위의 책을 찾는 시간이 자리에서 일어나 서가의 다른 책을 찾는 시간 보다 적게 걸린다)
메모리 시스템을 구축하는데 쓰인 개념은 어떻게 운영체제가 메모리와 입출력을 관리하는지, 어떻게 컴파일러가 코드를 생성하는지, 심지어는 응용 프로그램이 어떻게 컴퓨터를 이용하느지 등등 컴퓨터의 많은 다른 분야에까지 영향을 미친다.
물론 모든 프로그램이 메모리 접근에 많은 시간을 쓰기 때문에 메모리 시스템은 성능을 결정하는 중요한 요소이다.
메모리 계층구조는 성능에 큰 영향을 미치므로 지금까지 단일 계층의 메모리만 생각했던 프로그래머들도 이제는 메모리 계층구조가 어떻게 성능을 향상시키는지에 대하여 이해할 필요가 있다.
그림 5.18과 5.14절의 예에서 이에 대한 이해가 얼마나 중요한지를 보여주겠다. 이 예에서 행렬 곱셈의 성능을 어떻게 두 배로 향상시키는지를 보여줄 것이다.
프로그램은 최근에 접근했던 데이터들을 다시 사용하려는 경향, 즉 시간적 지역성과 최근에 접근했던 데이터에 인접해 있는 데이터들에 접근하려는 경향, 즉 공간적 지역성을 보인다.
메모리 계층구조는 최근에 접했던 데이터들을 프로세서 가까이 적재함으로써 시간적 지역성을 이용한다. 또한 메모리의 상위 계층으로 필요한 데이터뿐만 아니라 이와 인접한 다량의 데이터들로 이루어진 블록들을 옮김으로써 공간적 지역성을 이용한다.
메모리 계층은 그림 5.3과 같이 작고 빠른 메모리를 프로세서 가까이에 둔다. 따라서 최상위 계층에서 적중되는 접근은 매우 빠르게 처리할 수 있다. 실패가 발생한 접근은 느린 하위 계층으로 내려가서 수행된다.
적중률이 충분히 크면 메모리 계층의 접근 속도는 최상위(가장 빠른)과 비슷하고 크기는 최하위 계층(가장 큰) 메모리와 같아진다.
대부분의 컴퓨터에서 메모리는 정말로 계층적이다. 즉 계층 i+1에 존재하지 않는 데이터는 계층 i에 존재할 수 없다.

메모리 기술

오늘날 메모리 계층구조에서는 네 가지 주요 기술이 사용된다. 메인 메모리(main memory)는 DRAM(dynamic random access memory)으로 구현된다. 프로세서에 더 가까운 계층인 캐시(cache)에는 SRAM(static random access memory)이 사용된다.
DRAM은 SRAM보다 훨씬 느리지만 비트당 가격이 덜 비싸다. DRAM은 메모리 비트당 면적이 작기 떄문에 가격 차이가 생기게 되고, 따라서 같은 양의 실리콘으로 더 큰 용량을 만들 수 있다. 속도 차이는 여러 가지 이유로 생긴다.
세 번째 기술은 플래시 메모리이다. 이 비휘발성 메모리는 개인용 휴대기기에서 2차 메모리로 사용된다.
네 번째 기술은 서버의 가장 크고 가장 느린 계층으로 자기 디스크이다.
비트당 접근 시간과 가격은 기술에 따라 매우 다양하다. 아래 표는 2012년 현재의 전형적인 값들을 보여준다.
Search
Memory technology
Typical access time
$ per GiB in 2012
DRAM semiconductor memory
Open
50 ~ 70 ns
$10 ~ $20
Flash semiconductor memory
Open
5,000 ~ 50,000 ns
$0.75 ~ $1.00
Magnetic disk
Open
5,000,000 ~ 20,000,000 ns
$0.04 ~ $0.10

SRAM 기술

SRAM은 단순한 집적회로로서 읽기나 쓰기를 제공하는 접근 포트가(일반적으로) 하나 있는 메모리 배열이다. SRAM은 읽기 접근 시간과 쓰기 접근 시간이 다를 수는 있지만 어떤 데이터든지 접근 시간은 같다.
SRAM은 리프레시가 필요 없으므로 접근 시간은 사이클 시간과 거의 같다. SRAM은 읽을 때 정보가 바뀌지 않게 하기 위하여 비트당 6개 내지 8개의 트랜지스터를 사용한다. SRAM은 대기 모드에서 데이터 값을 유지하기 위해 최소한의 전력만을 사용한다.
과거 대부분의 PC와 서버 시스템은 1차, 2차 심지어 3차 캐시에도 별도의 SRAM 칩을 사용하였다. 그러나 오늘날에는 Moore의 법칙 덕택에 모든 계층의 캐시가 프로세서 칩에 집적되므로 분리된 SRAM 칩 시장은 거의 사라졌다.

DRAM 기술

SRAM에서는 전력이 공급되는 한 그 값이 무한히 유지된다. DRAM에서는 셀이 기억되는 값이 전하로 커패시터에 저장된다. 저장된 값을 읽거나 새로 쓰기 위하여 저장된 전하에 접근하는데 트랜지스터를 하나 사용한다.
DRAM은 저장된 비트 하나당 트랜지스터 하나만 사용하므로 SRAM에 비하여 훨씬 더 집적도가 높고 값도 싸다.
DRAM은 커패시터에 전하를 저장하기 떄문에 무한히 저장될 수 없으므로 주기적으로 리프레시가 필요하다. 그러므로 SRAM 셀에서 정적 저장이라고 하는 것에 반해 이런 메모리 구조를 동적이라고 부른다.
셀을 리프레시 하기 위해서는 단순히 저장된 값을 읽고 다시 쓴다. 전하는 수 밀리초 동안 유지될 수 있다. 모든 비트를 하나씩 DRAM에서 읽어서 다시 쓴다면, 계속 DRAM을 리프레시해야 하므로 기억된 값에 접근할 시간이 없게 된다.
다행히도 DRAM은 두 단계 디코딩 구조를 갖는다. 이 구조는 읽기 사이클에서 전체 행(워드라인을 공유하는)을 한꺼번에 읽은 후 바로 쓰기를 하여 한 행을 통째로 리프레시 할 수 있도록 해 준다.
그림 5.4는 DRAM의 내부 구조를 보여 준다. 그림 5.5는 DRAM의 집적도, 비용, 접근 시간이 수년 동안 어떻게 변화되었는지를 보여준다.
리프레시에 도움이 되는 행 구조는 성능 향상에도 도움이 된다. 성능을 향상시키기 위하여 DRAM은 행을 버퍼링해서 반복적으로 접근한다.
버퍼는 SRAM처럼 동작한다. 다음 행에 접근할 때까지 주소 값만 바꾸면 버퍼 내의 아무 비트에나 접근할 수 있다. 이 기능은 같은 행 내의 비트 접근 시간을 훨씬 줄여 주므로 접근 시간을 크게 개선한다.
칩을 더 크게 만들면 칩의 메모리 대역폭 또한 커지게 된다. 어떤 행이 버퍼에 있으면 DRAM의 대역폭(일반적으로 4, 8, 또는 16비트)이 얼마든지 간에 연속된 주소를 사용해서 또는 버퍼 내 시작 주소와 블록 전송을 이용해서 전송할 수 있다.
프로세서와의 인터페이스를 더욱 향상시키기 위해 DRAM은 클럭을 추가할 수 있는데 이것을 동기화 DRAM 또는 SDRAM이라 부른다. SDRAM의 장점은 클럭을 사용하므로 메모리와 프로세서를 동기화하는 시간이 필요 없다는 것이다.
동기화 DRAM의 속도가 빠른 이유는 추가 주소지정 대신 클럭이 연속적인 비트들을 버스트 모드로 전송할 수 있게 하기 떄문이다.
가장 빠른 버전은 DDR(Double Data Rate) SDRAM이라 불린다. 이 이름은 클럭의 상승 에지와 하강 에지 각각에서 데이터가 전송되는 것을 의미한다.
클럭과 데이터 전송 폭으로부터 기대할 수 있듯이 2배의 대역폭을 가능하게 한다. 이 중 최신 버전은 DDR4라고 불린다. DDR4-3200 DRAM은 초당 32억번의 전송이 가능하며, 1600 MHz 클럭을 사용한다.
이와 같이 큰 대역폭을 유지하기 위해서는 DRAM 내부에 좋은 구조가 필요하다. 단순하게 더 빠른 행 버퍼를 사용하는 대신에 DRAM은 내부적으로 여러 뱅크에서 읽기와 쓰기가 가능하도록 구성되었다.
각각의 뱅크는 자신의 행 버퍼를 가지고 있다. 여러 뱅크에 주소를 보낼 수 있게 하여 동시에 읽고 쓰기가 가능하게 하였다.
예컨대 뱅크가 4개일 때 한 번의 접근 시간으로 4배의 대역폭을 제공하기 위해 4개의 뱅크에 돌아가면서 접근한다. 이 순환 접근 방식은 주소 인터리빙(address interleaving)이라고 한다.

플래시 메모리

플래시 메모리는 전기적으로 지울 수 있고 프로그래밍이 간으한 ROM(EEPROM)의 한 종류이다.
디스크나 DRAM과 달리 플래시 메모리의 쓰기는 비트를 마모시킨다. 이 단점을 극복하기 위하여 대부분의 플래시 제품은 여러 번 쓰기가 수행된 블록을 덜 사용된 블록에 재사상(remapping)해서 쓰기를 분산시키는 제어기를 사용한다.
이 기법을 마모 균등화(wear leveling)라고 부른다. 마모 균등화를 사용하기 때문에 개인용 이동 단말기의 플래시가 잠재적 쓰기 한계를 넘는 경우는 거의 없다.
마모 균등화가 플래시의 잠재적 성능을 떨어뜨리지만, 상위 계층 소프트웨어가 각 블록의 마모를 관리하지 않는 한 사용할 수 밖에 없다. 마모 균등화를 수행하는 플래시 제어기는 제조 과정에서 잘못된 메모리 셀을 사용하지 않게 함으로써 수율을 향상시킬 수도 있다.

디스크 메모리

그림 5.6에서 볼 수 있듯이, 하드디스크는 원판의 집합으로 구성되어 있고 원판은 분당 5,400~15,000번의 속도로 회전한다. 금속 원판의 양측 면은 카세트나 비디오테이프와 같이 자성체로 코딩되어 있다.
하드디스크상의 정보를 읽거나 쓰기 위해선느 읽기/쓰기 헤드라고 불리는 작은 전자기 코일을 갖고 있는 움직이는 암(arm)이 필요하다. 전체 드라이브는 드라이브 내부를 보호하기 위하여 일체형으로 포장되어 있으며 따라서 디스크 헤드는 드라이브의 표면에 더욱 가깝게 위치할 수 있다.
각 디스크 표면은 트랙(track)이라고 불리는 동심원으로 나누어진다. 일반적으로 표면당 수만 개의 트랙이 존재한다. 각 트랙은 다시 정보를 담는 섹터(sector)로 나누어진다.
한 트랙은 수천 개의 섹터로 구성된다. 섹터는 일반적으로 512바이트에서 4096바이트까지의 크기를 갖는다.
자성 매체에는 섹터 번호, 공백, 에러 정정 코드를 포함하는 섹터의 정보, 공백, 다음 번 섹터의 번호와 같은 순서로 기록된다.
각 면의 디스크 헤드는 서로 연결되어 있어서 함꼐 움직인다. 그러므로 모든 헤드는 각 면의 같은 트랙에 위치하게 된다. 모든 면의 한 점에 위치한 헤드 아래에 놓인 모든 트랙은 실린더(cylinder)라고 부른다.
데이터에 접근하려면 운영체제가 세 단계에 걸친 명령어를 디스크에 내려야 한다. 첫 단계는 적절한 트랙 위에 디스크 암을 갖다 놓는 일이다. 이 작업은 보통 탐색(seek)이라 부르며 디스크 헤드를 원하는 트랙까지 이동시키는데 걸리는 시간은 탐색 시간(seek time)이라고 한다.
헤드가 원하는 트랙에 도달하면 읽기/쓰기 헤드의 아래에 원하는 섹터가 위치할 때까지 기다려야 한다. 이 시간을 회전 지연 시간(rational latency 또는 rorational delay)이라고 부른다.
원하는 정보에 도달하는 평균 회전 지연 시간은 디스크가 1/2 회전하는 정도의 시간이다. 디스크는 5,400~15,000 RPM으로 회전한다. 5,400 RPM에서 평균 회전 지연 시간은 다음과 같다.
평균 회전 지연 시간 = 0.5 rotation / 5,400 RPM = 0.0056 seconds = 5.6 ms
디스크 접근의 마지막 요소는 블록 하나를 전송하는 시간, 즉 전송 시간(transfer time)이다. 전송 시간은 섹터의 크기, 회전 속도 트랙의 저장 밀도의 함수이다. 2012년 기준 전송률은 100 MB/sec와 200 MB/sec 사이 값이다.
대부분의 디스크 제어기는 섹터들을 저장하는 내장 캐시를 갖고 있어서 전송률이 더 높아져서 2012년 기준으로 750 MB/sec (6 Gbit/sec) 정도이다.
이제는 블록 번호를 붙이는 방법이 단순하지 않다. 앞서 설명한 섹터-트랙-실린더 모델에서는 가까운 블록이 같은 트랙에 있는 것으로 가정한다. 같은 실린더에 위치한 블록은 탐색 시간이 필요 없으므로 빨리 접근할 수 있다.
블록 번호를 붙이는 방법이 달라진 것은 디스크 인터페이스의 계층을 더 높였기 때문이다. 순차적 전송을 더 빠르게 하기 위하여 이 상위 계층 인터페이스는 디스크를 무작위 접근 장치보다는 테이프 같은 형태로 구성하여 논리적 블록들을 디스크 표면에 구불구불한 순서로 배치한다.
최고의 성능을 얻기 위하여 같은 비트 밀도로 저장된 모든 섹터를 사용하기 위함이다. 따라서 연속된 블록도 다른 트랙에 위치할 수 있다.
자기 디스크와 반도체 메모리 기술 사이의 두 가지 큰 차이점은 디스크는 기계 장치이므로 접근 시간이 길고(플래시는 1,000배 정도 빠르고 DRAM은 100,000배 정도 빠르다), 디스크는 적당한 가격에 아주 높은 저장 용량을 갖기 때문에 훨씬 싸다는 점(디스크는 10~100배 정도 싸다)이다.
자기 디스크는 플래시와 같이 비휘발성이지만 플래시와 다르게 마모 문제가 없다. 그러나 플래시는 훨씬 튼튼해서 거친 환경에서 사용되는 개인용 휴대기기에 더 잘 맞는다.

캐시의 기본

도서관의 예에서 책상은 캐시의 기능을 수행하였다. 캐시(cache)는 이 계층을 갖춘 최초의 상용 컴퓨터에서 메인 메모리와 프로세서 사이에 있는 메모리 계층을 나타내기 위해 선택된 이름이다.
4장 데이터패스의 메모리들은 간단히 캐시로 대체될 수 있다.
이 절에서는 프로세서가 한 순간에 필요로 하는 데이터는 한 워드이고 블록 또한 한 워드로만 이루어진 아주 단순한 캐시를 먼저 살펴본다.
그림 5.7은 캐시에 없는 데이터를 요청하기 전과 후의 캐시 상태를 보여준다. 요청하기 전의 캐시에는 최근에 접근한 X1,X2,...,Xn1X_{1}, X_{2}, ... , X_{n-1}이 존재하고, 프로세서는 캐시에 없는 워드 XnX_{n}을 요청하였다. 이 요구는 실패를 발생시키고 워드 XnX_{n}을 메모리로부터 캐시로 가져오게 된다.
그림 5.7의 시나리오를 살펴보면 우리가 해결해야 할 두 가지 의문이 생기게 된다. 즉 데이터가 캐시 내에 있는지 어떻게 알 수 있는가? 그리고 알 수 있다면 어떻게 찾을 수 있는가?
이 질문들에 대한 답은 서로 연관되어 있다. 각 워드가 캐시 내의 딱 한 장소에만 있을 수 있다면 워드가 캐시 내에 있는지 없는지를 바로 알 수 있다.
메모리의 각 워드에 캐시 내의 위치를 할당하는 가장 간단한 방법은 메모리 주소에 기반을 두고 할당하는 것이다.
이 캐시 구조를 직접 사상(direct mapped)이라 한다. 왜냐하면 각 메모리 위치는 캐시 내의 딱 한 장소에 직접 사상되기 때문이다.
직접 사상 캐시가 사용하는 방식은 비교적 단순하다. 예컨대 거의 모든 직접 사상 캐시는 블록을 찾기 위하여 다음의 사상 방식을 사용한다.
(블록 주소) modulo (캐시 내에 존재하는 전체 캐시 블록 수)
만약 캐시 내부의 전체 블록 수가 2의 지수승이면 modulo 연산은 간단히 주소의 하위 log2\log_{2}(캐시 내의 전체 블록 수) 비트만을 취하는 것으로 쉽게 계산할 수 있다. 따라서 8-블록 캐시는 블록 주소로 하위 3비트(8=238 = 2^{3})를 사용한다.
예컨대 그림 5.8은 8개의 워드로 된 직접 사상 캐시와 캐시 내의 위치 1(001)과 5(101)로 사상되는 메모리 주소 1(00001)과 29(11101) 사이의 메모리 주소들을 보여준다.
각 캐시 엔트리는 여러 주소의 메모리 내용을 적재할 수 있다. 이때 캐시 내의 워드가 프로세서가 요구하는 것과 일치하는지를 어떻게 알 수 있을까? 즉 요구하는 워드가 캐시 내에 있는지 없는지를 어떻게 알 수 있을까?
캐시에 태그(tag)를 추가함으로써 이 문제를 해결할 수 있다. 태그는 캐시 내의 워드가 요청한 것인지 아닌지를 식별하는데 필요한 주소 정보를 포함한다.
예컨대 그림 5.8에서는 주소 비트의 하위 3비트 인덱스 필드가 블록을 선택하는데 사용되었으므로 태그는 5비트의 주소 비트 중 상위 2비트가 된다. 태그 구조는 중복되는 인덱스 비트를 생략한다. 왜냐하면 캐시 블록 주소의 인덱스 필드는 그 블록의 번호이기 때문이다.
또한 캐시 블록이 유효한 정보를 가지고 있는지를 알아내는 방법이 필요하다.
예컨대 프로세서가 맨 처음 작업을 시작하면 캐시는 비어 있을 것이며, 태그 필드는 의미가 없을 것이다. 많은 명령어를 수행한 이후에도 캐시 엔트리의 일부는 그림 5.7에서와 같이 비어있을 수 있다.
따라서 이들 엔트리들을 위한 태그들은 무시되어야 한다는 것을 알 수 있다. 가장 많이 쓰이는 방법은 엔트리가 타당한 주소를 포함하는지를 표시하기 위해 유효 비트(valid bit)를 캐시에 첨가하는 것이다. 이 비트가 1로 설정되어 있지 않으면 이 엔트리에는 유효한 블록이 없는 것으로 간주한다.
캐시는 예측기법을 사용하는 가장 중요한 예라고 할 수 있다. 지역성의 원칙을 이용해서 메모리 상위 계층에서 필요한 데이터를 찾는다. 상위 계층에서 예측이 틀렸을 경우에는 하위 계층에서 적합한 데이터를 찾을 수 있는 기법을 제공한다. 현대 컴퓨터의 캐시 예측 적중률은 95% 이상이다.

캐시 접근

아래 표는 캐시가 8개의 블록을 가지고 있고 모두 비어 있을 떄, 아홉 번의 메모리 참조에 따른 동작을 보여주고 있다. 그림 5.9는 캐시의 내용이 각 캐시 실패에 따라 어떻게 변경되는지를 보여준다. 캐시 내에 8개의 블록이 있기 떄문에 주소의 하위 3비트가 블록의 번호를 나타낸다.
Search
Decimal address of reference
Binary address of reference
Hit or miss in cache
Assigned cache block (where found or placed)
10110
miss(5.9b)
(10110 mod 8) = 110
11010
miss(5.9c)
(10010 mod 8) = 010
10110
hit
(10110 mod 8) = 110
11010
hit
(10010 mod 8) = 010
10000
miss(5.9d)
(10000 mod 8) = 000
00011
miss(5.9e)
(10011 mod 8) = 011
10000
hit
(10000 mod 8) = 000
10010
miss(5.9f)
(10010 mod 8) = 010
10000
hit
(10000 mod 8) = 000
캐시가 비어 있기 때문에 몇 개의 첫 번째 참조는 캐시 실패이다 (그림 5.9는 각 메모리 참조의 동작을 설명하고 있다)
여덟 번째 참조에서 블록에 대한 충돌이 생긴다. 주소 18(10010)의 워드가 캐시 블록 2(010)로 옮겨져야 한다. 따라서 이미 캐시 블록 2(010)에 있는 주소 26(11010)의 워드는 교체되어야만 한다.
이러한 상황은 캐시가 시간적 지역성을 활용할 수 있도록 해준다. 즉 최근에 접근된 워드는 더 이전에 접근된 워드를 교체한다.
이는 서가로부터 새로운 책이 필요하고 책상에 더는 빈 공간이 없을 때와 동일하다. 이미 책상에 있는 어떤 책을 서가로 되돌려 놓아야만 한다.
직접 사상 캐시에서는 새로 요청된 데이터가 들어갈 장소가 한 곳밖에 없기 때문에 교체시킬 선택안이 오직 하나밖에 없다.
우리는 모든 주소에 대해 캐시 내의 어느 곳을 찾아야 할지 알 수 있다. 주소의 하위 비트들은 주소가 사상되는 유일한 캐시 엔트리를 찾는데 사용할 수 있다. 그림 5.10은 참조된 주소가 어떻게 다음과 같이 나누어지는 지를 보여준다.
캐시의 태그 필드 값과 비교하는데 사용하는 태그 필드
블록을 고르는데 쓰이는 캐시 인덱스
캐시 블록의 인덱스는 그 블록의 태그 값과 함께 캐시 블록에 있는 워드의 실제 메모리 주소를 유일하게 표시할 수 있다.
인덱스 필드가 캐시에 접근하는 주소로 이용되고 nn비트 필드는 2n2^{n}개의 값을 갖게 되므로, 직접 사상 캐시 전체 엔트로피의 수는 2의 지수승이 되어야 한다.
MIPS 구조에서는 모든 주소가 4바이트로 정렬되어 4의 배수이기 때문에 모든 주소의 맨 오른쪽 2비트는 워드 내부의 바이트를 나타낸다. 따라서 최하위 두 비트는 블록 내의 워드를 선택할 때 이용되지 않는다.
캐시 구현에 필요한 총 비트 수는 캐시의 크기와 주소의 크기에 따라 결정된다. 왜냐하면 캐시는 데이터 뿐만 아니라 태그를 위한 장소를 필요로 하기 때문이다. 위에서 블록의 크기는 한 워드였지만 일반적으로는 여러 개의 워드가 된다. 아래와 같은 가정에서
32비트의 주소
직접 사상 캐시
캐시는 2n2^{n}개 블록을 가지고 있고 nn개 비트는 인덱스를 위하여 사용된다.
캐시 블록의 크기는 2m2^{m}개 워드(2m+22^{m+2}개 바이드)이다. mm개 비트는 블록 내부에서 워드 구별에 쓰이며, 두 비트는 주소 중 바이트 구별용으로 쓰인다.
태그 필드의 크기는
32(n+m+2)32 - (n + m + 2)
이다. 그리고 직접 사상 캐시의 전체 비트 수는
2m×(블록 크기+태그 크기+유효 비트 크기)2^{m} \times (\text{블록 크기} + \text{태그 크기} + \text{유효 비트 크기})
이다. 블록의 크기는 2m2^{m}개 워드 (2m+52^{m+5}개 비트)이고, 유효 필드를 위한 한 비트가 필요하므로 이 캐시의 전체 비트 수는
2n×(2m×32+(32nm2)+1)=2n×(2m×32+31nm)2^{n} \times (2^{m} \times 32 + (32 - n - m - 2) + 1) = 2^{n} \times (2^{m} \times 32 + 31 - n - m)
이다. 하지만 일반적으로 캐시 크기는 유효 비트와 태그 필드의 크기를 제외하고 데이터 크기만 따진다. 따라서 그림 5.10의 캐시는 4 KiB 캐시라고 부른다.

예제) 캐시 내의 비트

16 KiB의 데이터와 4워드 블록을 갖는 직접 사상 캐시의 구현에 필요한 전체 비트 수는 얼마인가? 단 32비트 주소를 가정하라
16 KiB는 4K(2122^{12})개 워드이다. 각 블록은 4(22)4(2^{2})개의 워드로 구성되고 1024(210)1024(2^{10})개의 블록을 갖는다. 각 블록은 4×32=1284 \times 32 = 128비트의 데이터와 (321022)(32-10-2-2)개 비트의 태그, 그리고 한 비트의 유효비트를 갖는다. 따라서 전체 캐시의 크기는
210×(4×32+(321022)+1)=210×147=147KiBibits2^{10} \times (4 \times 32 + (32 - 10 - 2- 2) + 1) = 2^{10} \times 147 = 147 \text{KiBibits}
다시 말해서 16 KiB 데이터를 저장하기 위해 18.4 KiB 캐시가 필요하다. 이 캐시에서 캐시의 전체 비트 수는 데이터에 필요한 저장 공간에 비해 약 1.15배 더 크다.

예제) 다수의 워드를 갖는 캐시 블록에의 주소 사상

16바이트의 블록 크기와 64개 블록으로 구성된 캐시를 고려하자. 바이트 주소 1200이 사상되는 블록 번호는 무엇인가?
블록은 다음과 같이 구할 수 있다.
(블록 주소) modulo (캐시 내 블록 수)
여기에서 블록 주소는 다음과 같이 구할 수 있다.
바이트 주소 / 블록당 바이트 수
이 블록 주소는 다음 두 주소 사이의 모든 주소를 포함하는 블록임을 주목하라
[바이트 주소 / 블록당 바이트 수] x 블록당 바이트 수
[바이트 주소 / 블록당 바이트 수] x 블록당 바이트 + (블록당 바이트 수 - 1)
블록당 바이트 수는 16이므로 바이트 주소 1200은 다음의 블록 주소를 갖는다.
1200 / 6 = 75
이는 캐시 블록 번호 75 modulo 64 = 11에 사상된다. 실제로 이 블록은 1200번지와 1215번지 사이의 모든 바이트를 갖게 된다.
크기가 큰 블록의 공간적 지역성은 실패율을 감소시킨다. 그림 5.11에 보인 것처럼 블록 크기를 늘리면 대개 실패율은 줄어든다.
블록 하나가 캐시 크기의 상당 부분을 차지하도록 블록을 크게 만들면 실패율이 올라갈 수도 있다. 왜냐하면 캐시 내에 존재할 수 있는 전체 블록의 수가 작아져서 블록들 간에 상호 충돌이 생길 수 있기 때문이다.
결과적으로 블록 내의 많은 워드들이 접근되기도 전에 그 블록이 캐시로부터 방출될 수도 있기 때문이다. 블록 크기가 매우 클 경우엔느 블록 내 워드 간의 공간적 지역성이 감소하게 된다. 결과적으로 실패율의 향상은 둔화된다.
블록 크기를 늘리는 것과 연관되어 발생되는 더 심각한 문제는 실패에 따르는 비용이 증가하는 것이다. 실패 손실은 메모리 계층구조의 다음 하위 계층에서 블록을 가져오고 캐시에 적재하는데 걸리는 시간에 의해 결정된다.
블록을 가져오는데 걸리는 시간은 두부분으로 나누어진다. 첫 번째 워드를 찾는데 걸리는 접근 지연(latency)과 블록을 이동시키는데 필요한 전송 시간이다.
메모리 시스템을 변경시키지 않는 한 블록 크기가 늘어날수록 전송시간 —따라서 실패 손실— 이 증가할 것은 자명하다. 게다가 실패율의 향상도 블록의 크기가 증가함에 따라 감소하기 시작한다.
결과적으로 실패 손실의 증가가 실패율의 감소를 압도하게 되고 캐시의 성능 또한 감소하게 된다.
물론 큰 블록을 보다 효율적으로 전송할 수 있게 메모리를 설계한다면 블록의 크기를 크게 할 수 있고 캐시의 성능 또한 더 개선할 수 있다. 이에 관해서는 다음 절에서 논의하도록 하자.

캐시 실패의 처리

실제 시스템에서 사용되는 캐시를 살펴보기 전에 제어 유닛이 어떻게 캐시 실패(cache miss)를 처리하는지 알아보자.
제어 유닛은 실패를 탐지해야 하며, 메모리로부터 데이터를 가져와서 실패를 처리해야 한다.
만약 캐시 내에 원하는 데이터가 존재하면 컴퓨터는 아무 일도 없는 것처럼 데이터를 사용할 수 있다.
캐시 적중을 처리할 수 있게 프로세서의 제어 유닛을 수정하는 것은 쉬운 일이지만 실패의 경우에는 몇 가지 조작이 더 필요하다.
캐시 실패 처리는 프로세서의 제어 유닛과 별도 제어기의 공동작업으로 처리된다. 이 제어기는 메모리 접근을 시작하고 캐시를 채우는 일을 한다. 캐시 실패의 처리는 모든 레지스터의 상태를 저장하는 인터럽트와는 다른 파이프라인 지연을 발생시킨다.
캐시 실패 발생 시에는 임시 레지스터와 프로그래머에게 보이는 레지스터의 내용을 그대로 유지한 채 메모리로부터 데이터가 오기를 기다리면서 전체 시스템을 지연시킨다.
더 정교한 비순서 실행 프로세서는 캐시 실패 처리를 기다리면서 명령어를 실행시킬 수 있지만 이 장에서는 캐시 실패가 발생하면 지연시키는 순차적 실행 프로세서를 가정한다.
명령어 실패가 어떻게 처리되는지 조금 더 자세히 살펴보자.
데이터 실패를 처리할 수 있게 이 방법을 확장하는 것은 어렵지 않다. 명령어 접근에 실패하면 명령어 레지스터의 내용이 유효하지 않게 된다.
적합한 명령어를 캐시로 가져오기 위해서는 메모리 계층구조의 낮은 계층에게 읽기 수행을 시켜야 한다. PC는 맨 처음 클럭 사이클 동안에 증가되기 때문에 명령어 캐시 실패를 발생시킨 명령어의 주소는 현재의 PC에서 4를 뺀 값과 같다.
주소가 얻어지면 메인 메모리에서 읽기를 수행하도록 요구해야 한다.
메모리가 응답하기를 기다려서 (접근에 여러 클럭이 걸리므로) 읽어 온 워드를 캐시에 쓴다.
명령어 캐시 실패의 처리 단계는 다음과 같이 정의할 수 있다.
1.
원래의 PC 값(현재 PC 값 - 4)을 메모리로 보낸다.
2.
메인 메모리에 읽기 동작을 지시하고 메모리가 접근을 끝낼 때까지 기다린다.
3.
메모리에서 인출한 데이터를 데이터 부분에 쓰고, 태그 필드에 주소(ALU로부터 계산된)의 상위 비트를 쓰고 유효 비트를 1로 만듦으로써 캐시 엔트리에 쓰기를 수행한다.
4.
명령어 수행을 첫 단계부터 다시 시작하여 캐시에 명령어를 가져온다. 이제는 필요한 명령어를 캐시에서 찾을 수 있다.
데이터 접근을 위한 캐시의 제어는 근본적으로 똑같다. 실패 발생 시에는 메모리가 데이터를 보내 줄 때까지 프로세서를 지연시키기만 하면 된다.

쓰기의 처리

쓰기는 약간 다르게 작동한다. 저장 명령을 가정해 보자.
데이터를 데이터 캐시에만 쓰고 메인 메모리에는 쓰지 않을 경우, 메인 메모리는 캐시와는 다른 값을 갖게 된다. 이 경우 캐시와 메모리는 불일치(inconsistent) 한다고 말한다.
메인 메모리와 캐시를 일치시키는 가장 쉬운 방법은 항상 데이터를 메모리와 캐시에 같이 쓰는 것이다. 이 방법을 즉시 쓰기(write-through)라고 부른다.
쓰기의 다른 중요한 측면은 쓰기 실패 시 어떤 일이 발생하는가이다. 먼저 메모리에서 해당 워드가 포함된 블록을 가져와서 캐시에 넣은 뒤 이 워드에 쓰기를 수행한다. 또한 전체 주소를 사용하여 이 워드를 메인 메모리에도 쓴다.
이 방식은 설계를 잘 한다고 하더라도 좋은 성능을 제공하기 어렵다. 즉시 쓰기 방식에서는 모든 쓰기가 메인 메모리에 데이터를 써야만 한다.
이 쓰기가 시간이 오래 걸려서 최소한 100개의 프로세서 클럭 사이클이 필요하고 따라서 프로세서의 성능을 심하게 저하시킨다.
예컨대 명령어의 10%가 저장 명령어라고 가정하자. 캐시 실패가 없는 경우 CPI가 1.0이고 모든 쓰기에 100개의 추가 사이클이 필요하게 되면, CPI 값은 1.0 + 100 x 10% = 11, 즉 약 10배 정도의 성능 저하가 생기게 된다.
이 문제를 해결하기 위한 한 가지 방법은 쓰기 버퍼(write buffer)를 이용하는 것이다. 쓰기 버퍼는 메모리에 쓰이기 위해 기다리는 동안 데이터를 저장한다.
데이터를 캐시와 쓰기 버퍼에 쓰고 난 후에, 프로세서는 수행을 계속할 수 있다. 메인 메모리에 쓰기를 완료하고 나면, 쓰기 버퍼에 있는 엔트리는 다시 비게 된다.
프로세서가 쓰기 처리를 하려고 할 때, 쓰기 버퍼가 모두 차 있으면 쓰기 버퍼에 빈 공간이 생길 때까지 멈춰 있어야만 한다.
물론 메모리가 쓰기를 완료할 수 있는 속도가 프로세서의 쓰기 동작 발생 속도보다 느리면, 아무리 큰 버퍼를 사용해도 도움이 되지 않는다. 왜냐하면 메모리 시스템이 쓰기를 받아들이는 것보다도 쓰기가 더 빨리 발생되기 때문이다.
쓰기 신호가 발생되는 속도가 메모리가 받아들이는 속도보다 느리다고 하더라도 지연이 발생할 수 있다. 이 같은 현상은 쓰기 신호가 폭주할 때 발생한다. 이러한 지연이 일어나는 것을 줄이기 위해서는 컴퓨터의 쓰기 버퍼 크기를 두 배 이상으로 늘려야 한다.
즉시 쓰기 방식의 대안은 나중 쓰기(write-back)라고 불리는 방식이다. 이 나중 쓰기 방식에서는 쓰기가 발생했을 때 새로운 값은 캐시 내의 블록에만 쓴다.
그러다가 나중에 캐시에서 쫓겨날 때 쓰기에 의해 내용이 바뀐 블록이면 메모리 계층구조의 더 낮은 계층에 써진다.
나중 쓰기 방식은 특히 메인 메모리가 처리할 수 있는 속도보다 프로세서가 쓰기를 더 빠르게 발생시키는 경우에 성능을 향상시킬 수 있다. 그러나 나중 쓰기 방식은 즉시 쓰기 방식보다 구현하기가 더 힘들다.

캐시의 한 예: Intrinsity FastMATH 프로세서

Intrinsity FastMATH는 MIPS 구조와 단순한 캐시 형식을 취한 빠른 임베디드 마이크로프로세서이다. 이 장의 뒷 부분에서는 ARM과 Intel의 마이크로프로세서에 사용되는 더 복잡한 캐시를 살펴볼 예정이다.
그림 5.12는 FastMATH의 데이터 캐시의 구조를 보여준다.
이 프로세서는 4장에서 살펴본 것과 유사하게 열두 단계 파이프라인으로 구성되어 있다. 최고 속도로 동작할 때 프로세서는 각 클럭당 명령어 한 개와 데이터 워드 한 개를 요청할 수 있다.
지연 없는 파이프라인 구현을 위해 분리된 명령어 캐시와 데이터 캐시가 사용되었다.
각 캐시의 크기는 16 KiB(즉 4096 워드)이고, 16워드 크기의 블록을 갖는다.
캐시에 대한 읽기 요청은 쉽다. 데이터 캐시와 명령어 캐시가 분리되어 있기 때문에 각 캐시에 대한 읽기/쓰기 수행을 위한 분리된 제어 신호가 필요하다. (실패 발생시 명령어 캐시를 갱신해야 함을 기억하라) 따라서 각 캐시에 대한 읽기 요청에 대한 처리 단계는 다음과 같다.
1.
주소를 캐시에 보낸다. 주소는 PC(명령어의 경우)나 ALU(데이터의 경우)로부터 나온다.
2.
캐시 적중일 경우 요청된 워드가 캐시의 데이터 선에 나온다. 요청된 블록에는 16개의 워드가 존재하므로 정확한 워드를 선택해야 한다. 블록 인덱스 필드가 멀티플렉서 제어를 위해 사용된다. (그림에서 Block offset 신호) 이 신호는 블록 내 16개 워드 중에서 요청한 워드를 선택한다.
3.
캐시 실패일 경우 메인 메모리로 주소를 보내야 한다. 메모리가 데이터를 보내주면 캐시에 쓰고 난 뒤 요청을 처리하기 위해 읽는다.
Intrinsity FastMATH는 즉시 쓰기와 나중 쓰기 두 가지 방식을 다 지원한다. 어떤 방식을 사용하는지는 운영체제가 선택할 수 있다. 또한 한 항목만 담을 수 있는 쓰기 버퍼를 갖고 있다.
Intensity FastMATH에서 사용되는 캐시의 실패율은 어느 정도일까? 그림 5.13은 명령어 캐시와 데이터 캐시의 실패율을 보여준다. 조합 실패율은 명령어와 데이터 접근 각각의 빈도수를 고려하여 계산한 유효 실패율이다.

요약

이 절에서는 가장 단순한 한 워드 블록의 직접 사상 캐시를 사용하여 설명하였다. 이 캐시에서는 모든 워드가 분리된 태그를 가지고 있고, 각 워드는 단지 한 위치로만 사상되기 때문에 적중과 실패가 매우 단순하다.
캐시와 메모리를 일치시키기 위해 즉시 쓰기 방식이 사용되었다. 이 방식에서는 캐시에 쓰기가 발생할 때마다 메인 메모리에도 똑같은 쓰기가 수행된다.
즉시 쓰기 방식의 대안으로는 캐시 내용이 교체될 때만 블록을 메인 메모리에 쓰는 나중 쓰기 방식이 있다.
공간적 지역성을 이용하기 위해서는 캐시가 한 워드보다 더 큰 크기의 블록을 사용해야 한다. 더 큰 블록의 사용은 실패율을 감소시키며, 캐시의 데이터 저장량에 비해 상대적으로 태그 저장량을 감소시킴으로써 캐시의 효율을 향상시킬 수 있다.
더 큰 블록 크기가 실패율을 감소시키지만 반면에 실패 손실을 증가시키기도 한다. 실패 손실이 블록 크기에 따라 선형적으로 증가한다면 큰 블록은 성능 감소를 가져오게 된다.
성능 저하를 피하기 위해 메인 메모리의 대역폭을 증가시켜 캐시 블록을 더 효과적으로 전송하게 한다.
DRAM 외부의 대역폭을 증가시키기 위한 일밙거인 방법은 메모리 폭을 넓히는 것과 인터리빙(interleaving) 시키는 것이다.
DRAM 개발자는 더 큰 캐시 블록 크기의 비용을 감소시키기 위해 프로세서와 메모리 사이의 인터페이스를 꾸준히 향상시켜 버스트 전송 모드의 대역폭을 증가시켜왔다.

캐시 성능의 측정 및 향상

이 절에서는 캐시의 성능을 측정하고 분석하는 방법을 살펴보는 것으로 싲가해서, 그 다음에는 캐시의 성능을 향상시키는 두 가지 방법을 알아본다.
한 방식은 두 개의 다른 메모리 블록이 하나의 캐시 위치를 두고 경쟁하는 확률을 줄임으로써 실패율을 줄이는 것이고, 다른 방식은 메모리 계층구조에 새로운 계층을 추가함으로써 실패 손실을 줄이는 것이다.
다단계 캐싱(multilevel caching)이라고 불리는 방식은 고급 컴퓨터에서 처음 등장하였으나 나중에는 데스크탑 컴퓨터에서도 일반화 되었다.
CPU 시간은 CPU가 프로그램을 수행하는데 쓰이는 클럭 사이클과 메모리 시스템을 기다리는데 쓰이는 클럭 사이클로 나누어진다. 일반적으로 적중된 캐시 접근 시간은 정상적인 CPU 수행 사이클의 일부로 간주한다. 즉
CPU 시간 = (CPU 클럭 사이클 + 메모리 지연 클럭 사이클) x 클럭 사이클 시간
메모리 지연 클럭 사이클은 주로 캐시 실패 때문에 생긴다. 여기서는 일단 그렇게 가정한다. 또한 여기서는 간략화된 메모리 시스템 모델로만 논의를 제한한다.
실제 프로세서에서 읽기와 쓰기 수행 시 발생되는 지연은 상당히 복잡해 질 수 있으며 정확한 성능 예측에는 대개 프로세서와 메모리 시스템의 아주 자세한 시뮬레이션이 필요하다.
메모리 지연 클럭 사이클은 읽기와 쓰기 시에 발생되는 지연 사이클의 합으로 정의할 수 있다.
메모리 지연 클럭 사이클 = 읽기 지연 사이클 + 쓰기 지연 사이클
읽기 지연 사이클은 프로그램당 읽기 접근의 수, 읽기 시의 실패 손실 클럭 사이클 수, 읽기 실패율에 의해 정의된다.
읽기 지연 사이클 = (읽기 접근 횟수 / 프로그램) x 읽기 실패율 x 읽기 실패 손실
쓰기의 경우는 더 복잡하다. 즉시 쓰기 방식에서는 지연이 두 가지 요소로 구성된다.
즉 쓰기를 수행하기 전에 블록을 인출해야 하는 쓰기 실패와 쓰기를 수행할 때 쓰기 버퍼가 다 채워져서 발생하는 쓰기 버퍼 지연으로 구성된다. 그래서 쓰기 시에 지연되는 사이클은 이 두 가지의 합과 같다.
쓰기 지연 사이클 = (쓰기 접근 횟수 / 프로그램) x 쓰기 실패율 x 쓰기 실패 손실 + 쓰기 버퍼 지연
쓰기 버퍼 지연은 쓰는 횟수가 아닌 쓰기의 집중도에 의존하므로 이러한 지연을 계산할 수 있는 단순한 계산 방법은 존재하지 않는다.
다행스럽게도 적당한 크기의 쓰기 버퍼(4워드 또는 그 이상)와 프로그램의 평균 쓰기 발생 빈도보다 충분히 빠르게 (예컨대 두 배) 쓰기를 수행할 수 있는 메모리를 갖고 있는 시스템에서는 쓰기 버퍼 지연이 매우 작기 때문에 무시할 수 있다.
시스템이 이를 만족시키지 못한다면 설계가 잘못된 것이므로 더 큰 쓰기 버퍼를 사용하거나 나중 쓰기 방식을 사용해야 한다.
나중 쓰기 방식 또한 블록이 교체될 때 메모리에 써야 하므로 추가적인 지연이 발생하게 된다.
대부분의 즉시 쓰기 캐시 구현 방식에서 읽기 실패 손실과 쓰기 실패 손실은 같다. (메모리에서 블록을 가져오는데 걸리는 시간) 쓰기 버퍼 지연이 무시할 수 있을 정도로 작다고 가정하면, 하나의 실패율과 실패 손실을 써서 읽기와 쓰기를 합칠 수 있다.
메모리 지연 클럭 사이클 = (메모리 접근 횟수 / 프로그램) x 실패율 x 실패 손실
또한 다음과 같이 쓸 수도 있다.
메모리 지연 클럭 사이클 = (명령어 / 프로그램) x (실패 / 명령어) x 실패 손실

예제) 캐시 성능의 계산

프로그램 명령어 캐시 실패율이 2%이고, 데이터 캐시 실패율이 4%라고 가정하자. 메모리 지연이 없을 때 CPI가 2이고, 매 실패마다 실패 손실이 100사이클이라면 결코 실패가 발생되지 않는 완벽한 캐시에서는 시스템이 얼마나 빨라지는지 계산하라. 읽기와 쓰기 빈도는 36%로 가정하자.
명령어 개수 (I)를 사용하여 명령어에 대한 메모리 실패 사이클의 수를 계산하면 다음과 같다.
명령어 실패 사이클 = I x 2% x 100 = 2.00 X I
모든 읽기와 쓰기의 빈도는 36%이다. 따라서 데이터 참조에 대한 메모리 실패 사이클의 수는 다음과 같다.
데이터 실패 사이클 = I x 36% x 4% x 100 = 1.44 x I
즉 전체 메모리-지연 사이클의 수는 2.00 I + 1.44 I = 3.44 I이다. 이것은 평균적으로 명령어당 3 사이클 이상의 메모리 지연을 요구한다는 것을 뜻한다.
따라서 메모리 지연을 고려할 경우의 CPI는 2 + 3.44 = 5.44가 된다. 명령어 개수와 클럭 속도에는 변화가 없기 때문에 프로세서 수행 시간의 비율은 다음과 같다.
지연이 있는 경우의 CPU 시간 / 완벽한 캐시의 CPU 시간 = (I x CPI_stall x 클럭 사이클) / (I x CPI_perfect x 클럭 사이클) = CPI_stall / CPI_perfect = 5.44 / 2 = 2.72
즉 완벽한 캐시가 있으면 성능은 2.72배 더 좋아진다.
만약 프로세서가 더 빠르게 동작하고 메모리 시스템은 전과 같다면 어떤 일이 발생할까? 이 경우에 메모리 지연에 쓰이는 시간은 전체 수행 시간 중 더 큰 부분을 차지하게 된다. 1장에서 살펴본 Amdahl의 법칙이 이를 상기시켜준다.
간단한 예 몇 개만 보아도 이 문제가 얼마나 심각한지를 알 수 있다. 앞의 예제에서 클럭 속도는 변화시키지 않고 CPI를 2에서 1로 줄여 시스템의 성능을 증가시켰다고 가정하자. 이는 파이프라인의 개선을 통해 가능하다. 이때 캐시 실패가 있는 시스템의 CPI는 1 + 3.44 = 4.44가 되므로, 완벽한 캐시를 갖는 시스템이 4.44 / 1 = 4.44배 더 빠르게 된다.
메모리 지연에 쓰이는 수행 시간의 양은 3.44 / 5.44 = 63% 에서 3.44 / 4.44 = 77%로 증가한다.
마찬가지로 메모리 시스템의 변화 없이 클럭 속도를 증가시키는 것 또한 캐시 실패로 인한 손실을 증가시키게 된다.
앞의 예제와 식들은 적중 시간이 캐시의 성능을 결정하는 요인이 아니라고 가정하고 있다. 하지만 적중 시간이 증가한다면 메모리 시스템으로부터 워드를 가져오는 전체 시간은 증가되고, 따라서 프로세서 사이클 시간 또한 증가된다.
곧 무엇이 적중 시간을 증가시키는가에 대한 몇 가지 예를 살펴보겠지만 한 가지 예는 캐시의 크기를 증가시키는 것이다. 더 큰 캐시는 당연히 더 긴 접근 시간을 필요로 한다. 만약 도서관의 책상이 아주 크다면 책상에서 책을 찾는데 걸리는 시간이 길어지는 것과 마찬가지다.
파이프라인 단계가 5단계 이상일 때 적중 시간이 증가하면 파이프라인에 새로운 단계가 추가될 수 있다. 캐시 적중에 두 사이클 이상이 소요되기 때문이다. 파이프라인의 깊이가 깊을수록 성능 계산이 어려워지게 된다. 캐시를 어느 정도 이상 크게 하면 적중률의 향상보다 적중 시간의 증가가 더 큰 영향을 미쳐 프로세서 성능은 더 나빠지게 된다.
적중과 실패 시의 데이터 접근 시간이 모두 성능에 영향을 미치므로, 이를 확인하기 위해 설계자는 서로 다른 캐시 구조를 평가하는 방법으로 평균 메모리 접근 시간(AMAT: average memory access time)을 사용한다. 이는 다음의 수식으로 표현된다.
평균 메모리 접근 시간 = 캐시 적중 시간 + 실패율 x 실패 손실

예제) 평균 메모리 접근 시간의 계산

클럭 사이클 시간이 1ns이고 실패 손실은 20클럭, 명령어당 0.05의 실패율을 가지며, 캐시 적중을 포함한 캐시 접근 시간이 1클럭이라고 할 때 평균 메모리 접근 시간을 구하라. 읽기와 쓰기의 실패 손실은 같고 다른 쓰기 지연은 무시한다.
명령어당 평균 메모리 접근시간은
평균 메모리 접근 시간 = 캐시 적중 시간 + 실패율 x 실패 손실 = 1 + 0.05 x 20 = 2 클럭 사이클
또는 2ns이다.

더 유연한 블록 배치를 통한 캐시 실패 줄이기

지금까지는 메모리 블록을 캐시에 넣을 때 각 블록이 캐시의 딱 한 곳에만 들어갈 수 있는 단순한 배치 방법을 사용하였다. 이 방법은 메모리 블록 주소를 상위 계층의 한 곳에 바로 사상시키므로 직접 사상(direct mapped)이라 부른다.
하지만 실제로는 블록을 배치하는 다양한 방식이 존재하는데, 그중 한 극단적 방법이 블록을 한 곳에만 넣을 수 있는 직접 사상 방식이다.
반대쪽 끝에는 블록이 캐시 내의 어느 곳에나 위치할 수 있는 방식이 존재하는데 이를 완전 연관(fully associative) 방식이라 한다.
블록이 어느 곳에나 위치할 수 있기 때문에 완전 연관 캐시에서 주어진 블록을 찾기 위해서는 캐시 내의 모든 엔트리를 검색해야 한다.
검색을 효율적으로 하기 위해서는 각 캐시 엔트리와 연결된 비교기를 이용하여 병렬로 검색한다. 이러한 비교기는 하드웨어 비용을 크게 증가시키므로 완전 연관 방식은 블록을 적게 갖는 캐시에서만 유용하다.
직접 사상과 완전 연관 사상의 중간 방식으로 집합 연관(set associative) 방식이 있다. 집합 연관 사상 캐시에는 한 블록이 들어갈 수 있는 자리의 개수가 고정되어 있다.
각 블록당 n개의 배치 가능한 위치를 갖는 집합 연관 캐시를 n-way 집합 연관 캐시라고 부른다.
n-way 집합 연관 캐시는 각각 n개의 블록으로 이루어진 다수의 집합들로 구성되어 있다. 메모리의 각 블록은 인덱스 필드에 의해 캐시 내의 한 집합으로 사상되고, 선택된 집합 내에서는 아무 위치에나 들어갈 수 있다. 따라서 집합 연관 사상 방식은 직접 사상 방식과 완전 연관 사상 방식의 조합이라고 볼 수 있다.
하나의 블록은 한 집합에 직접 사상되며, 일치하는 것을 찾기 위해 집합 내의 모든 블록들을 검색해야 한다. 예컨대 그림 5.14는 세 가지 블록 배치 방법에 대하여 전체 8개의 블록으로 구성된 캐시에 블록 12가 어디에 위치하는지를 보여준다.
직접 사상된 캐시 내의 메모리 블록의 위치는 다음과 같이 구할 수 있다.
(블록 번호) modulo (캐시 내 블록의 수)
집합 연관 캐시에서 어떤 메모리 블록을 갖고 있는 집합은 다음과 같이 구할 수 있다.
(블록 번호) modulo (캐시 내 집합의 수)
블록이 집합 내 어느 곳에나 배치될 수 있기 때문에, 집합 내의 모든 태그를 다 검색해야 한다. 완전 연관 캐시에서는 블록이 어느 곳에나 위치할 수 있으므로 캐시 내 모든 블록을 다 검색해야 한다.
모든 블록 배치 방식을 집합 연관 방식의 변형이라고 생각할 수 있다. 그림 5.15는 8개 블록을 갖는 캐시에서 가능한 연관 정도(associativity)에 따라 다양한 구조를 보여준다.
직접 사상 캐시는 단순히 1-way 집합 연관 캐시이다. 각 캐시 엔트리는 한 블록을 원소로 갖는 집합으로 구성된다.
m개의 엔트리로 구성된 완전 연관 캐시는 간단히 m-way 집합 연관 캐시라고 볼 수 있다. m개의 블록으로 구성된 한 개의 집합 만을 갖고 엔트리는 그 집합 내 어느 블록에도 위치할 수 있다.
연관 정도를 늘리는 것의 장점은 다음 예가 보여주는 것처럼 대개 실패율이 줄어든다는 것이다. 가장 큰 단점은 적중 시간의 증가이다.

예제) 실패와 캐시의 연관 정도

1워드 크기를 갖는 블록 4개로 구성된 작은 세 종류의 캐시가 있다. 하나는 완전 연관 방식, 다른 하나는 2-way 집합 연관 방식이고, 나머지는 직접 사상 방식이다. 각 캐시 구현에 대해서 블록 주소 0, 8, 0, 6, 8 순으로 블록을 참조할 때 발생하는 실패는 각각 몇 번인가?
직접 사상 캐시의 경우가 가장 쉽다. 먼저 각각의 블록 주소가 어느 캐시 블록으로 사상되는지 결정하자.
Search
Block address
Cache block
(0 modulo 4) = 0
(6 modulo 4) = 2
(8 modulo 4) = 0
이제 각 참조 후 캐시의 내용을 채울 수 있다. 빈칸은 블록이 유효하지 않음을 나타내고 파란색으로 처리된 것은 캐시에 추가된 새로운 엔트리를 보여준다. 검은색으로 쓰여 있는 항목은 전부터 캐시에 있던 엔트리를 보여준다.
Search
Address of memory block accessed
Hit or miss
0
1
2
3
miss
Memory[0]
miss
Memory[8]
miss
Memory[0]
miss
Memory[0]
Memory[6]
miss
Memory[8]
Memory[6]
직접 사상 캐시에서는 5번 접근 시도에 5번의 실패가 발생되었다.
집합 연관 캐시는 집합당 2개 원소를 갖는 2개의 집합(0과 1로 인덱스 됨)으로 구성된다. 각 블록 주소가 어느 집합으로 사상되는지 알아보자.
Search
Block address
Cache block
(0 modulo 2) = 0
(6 modulo 2) = 0
(8 modulo 2) = 0
실패 시 집합 내에서 교체할 엔트리의 선정을 위해선느 교체 방식을 정해야 한다. 집합 연관 캐시는 대개 집합 내에서 가장 오래 전에 사용된 블록을 교체시키는 LRU(least recently used) 교체 방식을 사용한다.
즉 가장 오래 전에 사용된 블록이 교체된다. 이 교체 방식을 사용하면 각 참조 후 집합 연관 캐시의 내용은 다음과 같게 된다.
Search
Address of memory block accessed
Hit or miss
0
1
2
3
miss
Memory[0]
miss
Memory[0]
Memory[8]
hit
Memory[0]
Memory[8]
miss
Memory[0]
Memory[6]
miss
Memory[8]
Memory[6]
블록 6이 참조될 때 블록 8이 교체된다. 블록 8이 블록 0보다 더 오랫동안 참조되지 않았기 때문이다. 2-way 집합 연관 캐시는 전부 4번의 실패를 갖게되고, 직접 사상 캐시보다 실패의 횟수가 1번 적다.
완전 연관 캐시는 4개의 캐시 블록으로 구성된 1개의 집합을 갖는다. 어떠한 메모리 블록도 캐시 내 어느 블록에나 적재될 수 있다. 이 완전 연관 방식 캐시가 단지 3개의 실패를 발생시키며 최고의 성능을 갖는다.
Search
Address of memory block accessed
Hit or miss
0
1
2
3
miss
Memory[0]
miss
Memory[0]
Memory[8]
hit
Memory[0]
Memory[8]
miss
Memory[0]
Memory[8]
Memory[6]
hit
Memory[0]
Memory[8]
Memory[6]
이런 순서를 갖는 참조에서는 세 가지 블록 주소를 사용하기 때문에 3개의 실패가 우리가 가질 수 있는 최상의 것이다. 만약 캐시에 8개의 블록이 있다면 2-way 집합 연관 캐시의 경우 교체는 발생되지 않는다. 따라서 완전 연관 캐시와 실패 횟수가 같게 된다.
마찬가지로 16개의 블록이 있다면 이 3개의 캐시는 모두 같은 개수의 실패를 갖는다. 이와 같이 단순한 예제도 캐시의 크기와 연관 정도가 캐시의 성능을 결정하는데 있어서 서로 독립적이지 않음을 보여준다.
실패율이 연관 정도에 의해 얼마나 줄어드는가? 그림 5.16은 16워드의 블록으로 구성된 64 KiB 데이터 캐시가 얼마나 개선되는지를 보여준다. 연관 정도는 직접 사상에서 8-way 집합 연관까지 다양하다.
1-way에서 2-way 집합 연관 방식으로 바뀌었을 때 실패율이 약 15% 향상됨을 알 수 있다. 그러나 더 높은 연관 정도를 갖는 집합 연관 방식으로 바뀌었을 때는 거의 향상이 없음을 알 수 있다.

캐시에서 블록 찾기

집합 연관 방식인 캐시에서 블록을 찾는 방법을 살펴보자. 직접 사상 캐시에서와 같이 집합 연관 캐시 내의 블록은 블록 주소를 나타내는 주소 태그를 가지고 있다.
선택된 집합 내 모든 블록의 태그는 프로세서로부터 나온 태그와 일치하는지를 검사하게 된다. 그림 5.17은 주소가 어떻게 나누어졌는지 보여준다.
인덱스 값을 이용하여 필요한 주소를 가지고 있는 집합을 선정하고, 선정된 집합 내 모든 태그는 병렬로 검색된다. 병렬이 아닌 순차적인 검색은 완전 연관 캐시에서와 같이 집합 연관 캐시의 적중 시간을 너무 느리게 만든다.
전체 크기가 같다면 연관 정도를 늘리는 것은 집합당 블록의 수를 증가시킨다. 집합당 블록의 수는 병렬로 검색되어 동시에 비교되어야 하는 횟수와 같다. 연관 정도를 2배 증가시키면 집합당 블록의 수가 2배가 되고 집합의 수는 절반이 된다.
따라서 연관 정도를 2배 늘리는 것은 인덱스의 크기를 1비트 줄게 하고 태그의 크기는 1비트 늘게 한다.
완전 연관 캐시의 경우 실제로 한 개의 집합만이 존재하며 모든 블록들은 병렬로 검사되어야 한다. 따라서 인덱스가 필요 없고 블록 변위를 제외한 전체 주소는 모든 블록 태그와 비교된다. 다시 말해 인덱스를 사용하지 않고 전체 캐시를 검색해야 한다.
직접 사상 캐시는 엔트리가 한 블록에만 존재할 수 있으므로 단지 하나의 비교기만이 필요하고 인덱스만을 사용하여 캐시에 접근할 수 있다.
그림 5.18의 4-way 집합 연관 캐시에서는 선정된 집합의 4개 원소 중 하나를 선택하는데 4:1 멀티플렉서와 4개의 비교기가 필요하다.
캐시 접근은 집합을 찾는 것과 집합 내의 태그를 비교하는 것으로 구성된다. 집합 연관 캐시를 사용하려면 많은 비교기가 필요하고 집합의 원소들을 비교하고 선택하는데 걸리는 시간 지연을 감수해야 한다.
직접 사상, 집합 연관, 또는 완전 사상 연관 중 하나를 선택할 때는 시간과 추가되는 하드웨어 측면에서 실패 시 감수해야 하는 비용 대비 연관 정도의 구현 비용을 고려한다.

교체시킬 블록의 선택

직접 사상 캐시에서 실패가 발생되면 요구된 블록은 딱 한 곳으로만 갈 수 있으므로 그 자리를 차지하였던 블록은 교체되어야만 한다. 연관 방식의 캐시에서는 요구된 블록을 어디에 위치시킬지 선택해야 하며 이는 교체시켜야 할 블록을 선택하는 것과 동일하다.
완전 연관 캐시는 모든 블록이 교체의 후보가 된다. 집합 연관 캐시의 경우에는 선정된 집합 내의 블록 중에서 골라야 한다.
가장 일반적으로 사용되는 방식은 이전 예제에서 사용한 바와 같은 LRU(least recently used) 방식이다. LRU 방식에서 교체되는 블록은 가장 오랫동안 사용되지 않은 것이다. 앞의 예제에서 블록 6 대신에 블록 0이 교체된 이유는 LRU를 사용했기 때문이다.
LRU 방식은 집합의 어떤 원소가 집합 내의 다른 원소에 비해 상대적으로 언제 사용되었는지를 추적함으로써 구현 가능하다.
2-way 집합 연관 방식의 캐시에서는 두 원소가 언제 사용되었는지를 추적하는 것은 각 집합마다 한 비트를 두고 원소가 참조될 때마다 원소를 표시하는 값으로 비트를 결정함으로써 구현될 수 있다. 연관 정도가 커지게 되면 LRU를 구현하는 것이 더욱 힘들게 된다.

예제) 태그의 크기 대 집합의 연관 정도

연관 정도를 늘리는 것은 캐시 블록당 더 많은 태그 비트를 요구할 뿐만 아니라, 더 많은 비교기를 필요로 한다.
4096개의 블록을 갖고 하나의 블록은 4개의 워드를 가지며 32비트 주소를 갖는 캐시에 대해 직접 사상, 2-way 집합 연관, 4-way 집합 연관과 완전 연관 방식을 적용하였을 때 각각에 대해 전체 집합의 수와 전체 태그 비트의 수를 구하라.
블록당 16(242^{4})바이트가 존재하므로 32비트 주소 중 인덱스와 태그용으로 32-4 = 28비트를 필요로 한다. 직접 사상 캐시에서는 블록의 개수와 집합의 개수가 같으므로 인덱스로 12비트(log24096=12\log_{2} 4096 = 12)를 갖는다. 따라서 태그 비트들의 총수는 (28-12) x 4096 = 16 x 4096 = 66 K 태그 비트이다.
연관 정도를 높일 때마다 집합의 수는 절반씩 줄어들게 되고, 따라서 캐시를 인덱스하는데 필요한 비트 수도 하나씩 감소하게 된다. 또한 태그에 필요한 비트는 하나씩 증가하게 된다. 따라서 2-way 집합 연관 캐시는 2048개의 집합을 갖게 되고 전체 태그 비트수는 (28-11) x 2 x 2048 = 34 x 2048 = 70 K 태그 비트가 된다.
4-way 집합 연관 캐시는 전체 집합의 수가 1024이고 전체 태그 비트 수는 (28-10) x 4 x 1024 = 72 x 1024 = 74 K 비트가 된다.
완전 연관 캐시의 경우 4096개 블록 크기 집합 하나만 존재하므로 태그는 28비트이며 28 x 4096 x 1 = 115 K 태그 비트가 된다.

다단계 캐시를 이용한 실패 손실 줄이기

현대의 모든 컴퓨터는 캐시를 사용한다. 프로세서의 빠른 클럭 속도와 상대적으로 점점 느려지는 DRAM 접근 시간 사이의 차이를 더욱 줄이기 위해 고성능 마이크로프로세서들은 캐시를 한 계층 더 사용한다.
이 2차 캐시(secondary cache)는 주로 마이크로프로세서에 내장되어 있으며, 1차 캐시(primary cache)에서 실패가 발생할 때 접근된다. 2차 캐시가 원하는 데이터를 가지고 있으면 실패 손실은 2차 캐시의 접근 시간이 되며, 이 값은 메인 메모리의 접근 시간보다 훨씬 작다.
1차 캐시와 2차 캐시 둘 다 데이터를 갖고 있지 않은 경우에는 메인 메모리 접근이 필요하게 되고 더 큰 실패 손실이 발생하게 된다.

예제) 다단계 캐시의 성능

4 GHz에서 동작하고 모든 참조가 1차 캐시에서 적중될 경우의 기본 CPI가 1.0인 프로세서를 가정해 보자. 실패 처리까지 포함하여 메인 메모리 접근 시간이 100ns이고, 1차 캐시에서 명령어당 실패율이 2%라고 가정하자.
실패나 적중 시 접근 시간이 5ns이고 메인 메모리의 실패율을 0.5%까지 낮출 수 있을만큼 충분히 큰 2차 캐시를 추가할 경우 프로세서는 얼마나 빨라지는가?
메인 메모리의 실패 손실은 다음과 같다.
(100 ns / 0.25 ns/clock cycle) = 400 클럭 사이클
하나의 캐시만 갖는 경우 유효 CPI는 다음과 같다.
전체 CPI = 기본 CPI = 명령어당 메모리 지연 사이클 = 1.0 + 명령어당 메모리 지연 사이클 = 1.0 + 2% x 400 = 9
2차 캐시를 가질 경우 1차 캐시에서의 실패는 2차 캐시 또는 메인 메모리에 의해 처리될 수 있다. 2차 캐시 접근에 따른 실패 손실은 다음과 같다.
5 ns / 0.25 ns/clock cycle = 20 클럭 사이클
만약 실패가 2차 캐시에서 처리되면 이 값이 전체 실패 손실이 된다. 실패를 메인 메모리가 처리하게 될 경우 전체 실패 손실은 2차 캐시 접근 시간과 메인 메모리 접근 시간의 합이 된다.
따라서 두 단계 캐시에서의 전체 CPI는 두 캐시로부터의 지연 사이클과 기본 CPI의 합이 된다.
전체 CPI = 1 + 명령어당 1차 캐시 지연 + 명령어당 2차 캐시 지연 = 1 + 2% x 20 + 0.5% x 400 = 1 + 0.4 + 2.0 = 3.4
따라서 2차 캐시를 갖는 프로세서는 다음과 같이 빨라지게 된다.
9.0 / 3.4 = 2.6
다른 방식으로 2차 캐시에 적중된 참조의 지연 사이클 (2% - 0.5%) x 20 = 0.3을 계산할 수 있다. 메인 메모리까지 내려간 참조의 지연 사이클은 2차 캐시 접근 시간과 메인 메모리 접근 시간을 포함해야 하므로 0.5% x (20 + 400) = 2.1이 된다. 그러므로 합은 1.0 + 0.3 + 2.1 즉 다시 3.4가 된다.
1차 캐시와 2차 캐시의 설계 고려사항은 매우 다르다. 다른 캐시가 있기 때문에 최적의 선택이 단일 계층 캐시와는 달라지게 된다.
특히 1차 캐시 설계는 클럭 사이클의 단축이나 파이프라인 단계의 축소가 가능하도록 적중 시간 최소화에 초점을 맞추고, 2차 캐시 설계는 긴 메모리 접근 시간으로 인한 손실을 줄이도록 실패율에 중점을 둘 수 있게 해준다.
각 캐시를 단일 계층 캐시의 최적 설계와 비교해 보면 이러한 변화가 두 캐시에 미치는 영향을 알 수 있다.
단일 캐시와 비교할 때 다단계 캐시(multilevel cache)의 1차 캐시는 대개 더 작다. 게다가 1차 캐시는 크기를 작게 하고 실패 손실을 줄이기 위해 블록 크기가 작다.
반면에 2차 캐시는 단일 캐시와 비교할 때 접근 시간이 덜 중요하기 때문에 크기가 더 크다. 따라서 단일 캐시에 적절한 블록 크기보다 더 큰 블록을 사용할 수 있다. 2차 캐시는 실패율을 줄이는데 집중해야 하므로 1차 캐시보다 더 높은 연관 정도가 많이 사용된다.
정렬은 버블(bubble) 정렬, 퀵(quick) 정렬, 기수(radix) 정렬 등 좀 더 좋은 알고리즘을 찾기 위해 철저히 분석되어 왔다.
그림 5.19(a)는 기수 정렬과 퀵 정렬에 의해 실행된 항목당 명령어 수를 보여주고 있다. 예측한 대로 큰 배열에서는 기수 정렬이 퀵 정렬에 비해 연산 횟수 측면에서 알고리즘상의 장점을 보인다.
그림 5.19(b)는 수행된 명령어 대신 수행된 시간을 보여준다. 이 값은 그림 5.19(a)와 같은 궤적을 갖고 시작 하지만 기수 정렬은 입력 값이 많아질수록 발산함을 알 수 있다.
왜 이런 일이 발생하는 것일까? 그림 5.19(c)는 정렬되는 항목당 캐시 실패 횟수를 보여 줌으로써 이 질문에 답하고 있다. 퀵 정렬이 항상 더 적은 캐시 실패를 발생시킨다.
표준 알고리즘 분석 방법은 메모리 계층구조의 영향을 무시하는 경우가 많다. 더 빠른 클럭과 Moore의 법칙이 컴퓨터 성능의 극대화를 가져왔듯이, 오늘날에는 메모리 계층구조를 잘 이용하는 것이 고성능을 얻는데 있어서 핵심이 된다.
서두에서 이야기 했지만 메모리 계층구조의 동작 원리를 이해하는 것이 오늘날 현존하는 컴퓨터에서 프로그램의 성능을 이해하는데 매우 중요하다.

블로킹을 이용한 소프트웨어 최적화

성능 향상에 메모리 계층구조가 중요하기 때문에 극적인 성능 향상을 이룰 수 있는 소프트웨어 최적화 방법이 많이 제시된 것은 놀랄 일이 아니다. 캐시 내의 데이터를 재사용하여 지역성을 개선하므로 실패율이 감소하게 된다.
배열을 다룰 때는 배열에 대한 접근이 메모리에서 순차적으로 이루어질 수 있도록 저장할 때 좋은 성능을 얻을 수 있다.
어떤 배열들은 행으로 접근되고 어떤 배열들은 열로 접근되는 경우를 가정해 보자. 배열을 행 단위(행 우선 순서)로 저장하거나 열 단위(열 우선 순서)로 저장한다고 해서 문제가 해결되지는 않는다. 순환문을 반복할 떄마다 행도 사용되고 열도 사용되기 때문이다.
블록화 알고리즘은 배열의 전체 행과 열을 처리하는 대신 부행렬 또는 블록 단위로 처리한다. 캐시에 적재된 데이터가 교체되기 전에 최대한 사용하는 것이 목표이다. 즉 캐시 실패를 줄이기 위해 시간적 지역성을 향상시키는 것이다.
예컨대 DGEMM의 내부 순환문은 다음과 같다.
for (int j = 0; j < n; ++j) { double cij = C[i+j*n]; for (int k = 0; k < n; k++) { cij += A[i+k*n] * B[k+j*n]; } C[i+j*n] = cij; }
C#
B의 NxN 원소를 모두 읽고, A의 한 열에 해당하는 같은 원소 N개를 반복적으로 읽고, C의 한 열에 해당하는 원소 N개를 쓴다.
그림 5.20은 세 배열에 대한 접근을 보여준다. 짙은 음영은 최근에 접근한 것들, 밝은 음영은 더 오래전에 접근한 것들, 흰색은 아직 접근하지 않은 것을 보여준다.
용량 실패의 횟수가 N과 캐시 크기에 따라 달라지는 것은 분명하다. 캐시 충돌이 없다면 NxN 행렬 세 개를 다 저장할 수 있다면 아주 좋다.
3장과 4장에서 행렬의 크기가 32x32이면 이 경우에 해당한다. 각 행렬은 32x32=1024개 원소이고 각 원소는 8바이트이다. 이때 3개의 행렬은 24KiB를 차지하므로 Intel Core i7의 32 KiB 데이터 캐시에 들어갈 수 있다.
캐시가 NxN 행렬과 N 원소 행 하나를 저장할 수 있으면 최소한 A의 i번째 행과 배열 B는 캐시에 들어갈 수 있다. 이것보다 작을 경우 실패는 B와 C 양쪽에서 발생할 수 있다.
최악의 경우에는 N3N^{3} 연산에서 2N3+N22 N^{3} + N^{2} 메모리 워드 접근이 발생한다.
접근되는 원소가 모두 캐시에 들어갈 수 있는 것을 보장하기 위해 원래 코드를 부행렬에서 계산되도록 바꾸었다.
BLOCKSIZE x BLOCKSIZE 크기의 행렬에 대해 그림 4.80의 DGEMM을 반복해서 호출한다. BLOCKSIZE는 블로킹 인수(blocking factor)라 한다.
아래 코드는 DGEMM의 블록화 버전을 보여준다. 함수 do_block은 그림 3.21의 DGEMM에 A, B, C의 각 부행렬 시작 위치를 나타내는 si, sj, sk 세 파라미터를 추가한 것이다.
do_block의 두 내부 순환문은 B와 C 전체 길이 대신에 BLOCKSIZE의 크기 단위로 계산한다.
gcc 최적화 프로그램은 함수를 인라인화(inlining)함으로써 함수 호출에 따른 오버헤드를 제거한다.
즉 함수의 코드를 바로 삽입하여 기존의 파라미터 전달과 복귀 주소 관련 잡다한 명령어들을 제거한다.
#define BLOCKSIZE 32 void do_block(int n, int si, int sj, int sk, double *A, double *B, double *C) { for (int i = si; i < si + BLOCKSIZE; ++i) { for (int j = sj; j < sj + BLOCKSIZE; ++j) { double cij = C[i+j*n]; for (int k = sk; k < sk + BLOCKSIZE; k++) { cij += A[i+k*n] * B[k+j*n]; } C[i+j*n] = cij; } } } void dgemm(int n, double* A, double* B, double* C) { for (int sj = 0; sj < n; sj += BLOCKSIZE) { for (int si = 0; si < n; si += BLOCKSIZE) { for (int sk = 0; sk < n; sk += BLOCKSIZE) { do_block(n, si, sj, sk, A, B, C); } } } }
C#
그림 5.22는 블로킹을 사용하여 세 배열에 접근하는 것을 보여준다. 용량 실패만 고려하면 접근되는 메모리 워드 수는 모두 2N3/BLOCKSIZE+N22 N^{3} / \text{BLOCKSIZE} + N^{2} 이다. 이 값은 BLOCKSIZE만큼의 성능 향상이다.
A는 공간적 지역성에서 이점을 취하고, B는 시간적 지역성에서 이점을 취하므로, 블로킹은 공간과 시간 지역성을 모두 이용한다.
캐시 실패를 줄이는데 목표를 두었지만, 블로킹은 레지스터 할당을 돕는데 사용되기도 한다. 블로킹 크기를 작게 해서 블록이 레지스터에 저장될 수 있도록 하면, 프로그램의 적재와 저장의 수를 줄일 수 있고 따라서 성능이 향상될 것이다.
그림 5.23은 행렬 세 개 모두가 캐시에 들어갈 수 없을 때까지 행렬의 크기를 점점 증가시켜서 캐시 블로킹이 최적화되지 않은 DGEMM의 성능에 미치는 영향을 보여준다.
최적화되지 않은 버전의 성능은 가장 큰 행렬에서 반으로 줄어든다. 캐시 블록화 버전은 3장과 4장의 32x32 행렬보다 900배 큰 960x960 행렬에서도 성능 저하가 10% 미만이다.

요약

이 절에서는 1) 캐시의 성능, 2) 실패율을 줄이기 위한 연관 사상의 사용, 3) 실패 손실을 줄이기 위한 다단계 캐시 계층구조의 사용, 4) 캐시의 효율성을 향상시키기 위한 소프트웨어 최적화 사용 등 네 가지 주제에 초점을 맞추었다.
메모리 시스템은 프로그램 수행 시간에 큰 영향을 준다. 메모리 지연 사이클 수는 실패율과 실패 손실에 의해 결정된다. 5.8절에서 살펴보겠지만 문제는 메모리 계층구조상의 다른 중요한 요소들에 영향을 주지 않고 이 요소들 중 하나를 줄이는 것이다.
실패율을 줄이기 위해 연관 배치 방식을 살펴보았다. 이 방식들은 캐시 내부에 보다 유연한 배치 방식을 사용함으로써 실패율을 줄일 수 있었다.
완전 연관 방식에서는 블록이 어디에나 위치할 수 있다. 그러나 읽기나 쓰기 요청을 처리하려면 캐시 내의 모든 블록이 검색되어야만 한다. 그리고 높은 비용은 크기가 큰 완전 연관 캐시를 비실용적으로 만든다.
집합 연관 방식이 실용적인 대안이다. 인덱스를 통해 선택된 집합의 원소들만 검색하면 되기 때문이다. 집한 연관 캐시는 더 높은 실패율을 가지지만 접근 시간이 빠르다. 최고의 성능을 발휘하는 연관 정도는 기술과 자세한 구현 방식에 의해 결정된다.
1차 캐시에서의 실패를 더 큰 2차 캐시가 처리하도록 하여 실패 손실을 줄이는 기술로 다단계 캐시가 소개되었다. 설계자들이 제한된 실리콘의 크기와 고속 클럭 속도 목표를 달성하기 위해서는 크기가 큰 1차 캐시를 사용할 수 없다는 것을 파악하게 되면서 2차 캐시는 일반화 되었다.
1차 캐시보다 10배 또는 그 이상 더 큰 2차 캐시는 1차 캐시에서 실패가 발생한 많은 접ㄱ느을 처리할 수 있다. 이러한 경우에 실패 손실은 2차 캐시 접근 시간(일반적으로 10개의 프로세서 사이클 이내)이 된다. 메모리 접근 시간은 일반적으로 100개 프로세서 사이클 이상이다.
연관 사상에서 적정 연관정도 값이 그랬듯이 2차 캐시의 크기와 접근 시간 간의 상관관계도 구현상의 여러 가지 기술 요소의 영향을 받는다.
마지막으로 성능 향상에 메모리 계층구조가 중요하므로 캐시 성능을 개선하기 위해 알고리즘을 어떻게 바꾸는지 알아보았다. 큰 배열을 처리할 때는 블로킹이 중요한 기술임을 알게 되었다.

신용도 있는 메모리 계층구조

빨라도 믿을 수 없으면 의미가 없다. 1장에서 배운대로 신용도를 확보하는 큰 아이디어는 여분을 사용하는 것이다.

실패의 정의

먼저 적합한 서비스의 명세가 있다고 가정한다. 사용자는 시스템이 서비스 명세를 기준으로 두 가지 상태 사이를 왔다 갔다 하는 것을 볼 수 있다.
1.
서비스 수행, 서비스가 명세대로 제공되는 경우
2.
서비스 중단, 제공되는 서비스가 명세와 다른 경우
상태 1에서 2로 전이하는 것은 장애 때문이고, 상태 2에서 1로 전이하는 것은 복구라고 한다. 장애는 영구적일 수도 있고 일시적일 수도 있다.
이와 같은 정의는 신뢰성과 가용성이라는 용어와 연결이 된다. 신뢰성(reliability)이란 어떤 기준 시점에서부터 서비스 수행의 지속성에 대한 척도로 장애가 발생하기까지의 시간과 같다.
그러므로 평균 무장애시간(MTTF: mean time to failure)은 신뢰성의 척도이다.
관련 용어로 주어진 MTTF에 대하여 1년에 장애를 발생시킬 것으로 예상되는 장치의 비율을 퍼센트로 나타낸 연간장애율(AFR: annual failure rate)이 있다.

예제) 디스크의 MTTF 대 AFR

오늘 날 어떤 디스크들은 MTTF 가 1,000,000시간이라고 주장한다. 1,000,000 시간은 1,000,000 / (365 x 24) = 114년이므로 현실적으로 고장나지 않을 것처럼 보인다. 인터넷 서비스를 제공하는 창고 규모 컴퓨터들의 서버는 50,000대나 된다. 각 서버가 2개의 디스크를 갖는다고 가정할 때, ARF을 사용해서 매년 얼마나 많은 디스크가 고장나는지를 계산하라.
1년은 365 x 24 = 8760 시간이다. 1,000,000 시간 MTTF는 8760/1,000,000 = 0.876%의 AFR을 의미한다. 디스크가 100,000개 있으면 매년 그 중 876개가 고장난다고 예측할 수 있고, 평균적으로 맹리 2개의 디스크가 고장 남을 의미한다.
서비스 중단은 평균 복구시간(MTTR: mean time to repair)으로 측정된다. 장애간 평균시간(MTBF: mean time between failures)은 단순히 평균 무장애시간과 평균 복구시간을 더한 것이다. MTBF가 많이 사용되지만 MTTF가 더 적절한 용어이다.
가용성(availability)은 서비스의 수행과 중단, 두 상태를 왔다 갔다 하는데 관련된 서비스 수행에 대한 척도이다. 가용성은 다음과 같이 통계적으로 정량화 할 수 있다.
가용성 = MTTF / (MTTF + MTTR)
신뢰성과 가용성은 그저 신용도와 비슷한 용어가 아니라 정량화할 수 있는 척도임에 유의하자. MTTR을 줄임으로써 MTTF를 늘리는 것만큼 가용성을 높일 수 있다.
예컨대 결함의 탐지, 진단, 수리에 사용되는 도구는 사람이나 소프트웨어, 하드웨어가 결함을 수리하는데 걸리는 시간을 단축시키는데 도움이 되어서 가용성을 향상시킬 수 있다.
우리는 가용성이 매우 높기를 바란다. 높은 가용성을 나타내는 한 가지 방법은 연간 '가용성의 9(nines of availability)' 개수를 사용하는 것이다.
예컨대 오늘날 매우 안정적인 서비스는 4-5개의 가용성 9를 제공한다. 1년은 365일이므로 365 x 24 x 60 = 526,000 분이 되고
nine: 90% ⇒ 1년간 36.5일의 수리기간
nines: 99% ⇒ 1년간 3.65일의 수리기간
nines: 99.9% ⇒ 1년간 526분의 수리기간
nines: 99.99% ⇒ 1년간 52.6분의 수리기간
nines: 99.999% ⇒ 1년간 5.25분의 수리기간
등이 된다.
MTTF를 증가시키기 위해 부품의 품질을 개선하거나 일부 장애가 발생한 부품이 있더라도 계속 작동하도록 시스템을 설계할 수 있다. 그렇다면 장애를 다시 정의할 필요가 있다. 부품에 장애가 있더라도 시스템에는 장애가 발생하지 않을 수 있다. 이러한 상황을 명확하게 구분하기 위해 부품의 장애에는 결함(fault)이라는 용어를 사용한다. 아래에 MTTF를 개선하는 세 가지를 소개한다.
1.
결함 회피(fault avoidance): 결함 발생을 구조적으로 방지하는 방법
2.
결함 감내(fault tolerance): 결함이 나타나더라도 서비스 명세대로 서비스가 제공될 수 있도록 여유분을 사용하는 방법
3.
결함 예상(fault forecasting): 결함의 존재와 발생을 예측하는 방법으로 구성 요소가 실패하기 전에 교체할 수 있도록 한다.

해밍 단일 에러 정정, 이중 에러 검출 코드(SEC/DED)

Richard Hamming은 메모리에 널리 사용되는 여유분 기법을 발명하였고, 이 업적으로 1968년에 튜링상을 수상하였다. 여유분 코드를 만들기 위하여 비트 패턴들이 얼마나 가까운지를 살펴보는 것이 중요하다.
해밍거리(Hamming distance)는 유효한 두 비트 패턴에서 서로 다른 최소한의 비트 수를 말한다. 예컨대 011011과 001111의 거리는 2이다.
어떤 코드의 원소들 간의 최소 거리가 2일 때 한 개의 비트 에러가 생기면 어떻게 될까? 코드의 유효한 패턴이 잘못된 패턴으로 바뀔 것이다. 따라서 코드의 원소가 유효한지 않은지 검출할 수 있다면 한 개의 비트 에러는 검출할 수 있고 이때 단일 비트 에러 검출 코드(error detection code)가 있다고 말한다.
(컨셉은 섀년의 정보이론이랑 비슷한 듯)
Hamming은 에러 검출을 위해 패리티 코드(parity code)를 사용하였다. 패리티 코드에서는 워드에 있는 1의 개수를 세어서, 1의 개수가 홀수이면 홀수 패리티를 갖고, 짝수 개이면 짝수 패리티를 갖는다고 말한다.
워드를 메모리에 쓸 때 패리티 비트도 함께 쓴다. (홀수이면 1, 짝수이면 0) 즉 N+1 비트의 패리티는 항상 짝수이다. 워드를 읽을 때는 패리티 비트도 같이 읽어서 검사한다. 메모리 워드의 패리티가 저장된 패리티 비트와 다르면 에러가 발생한 것이다.

예제)

한 바이트로 표현된 숫자 31의 패리티를 계산하고 메모리에 저장되는 패턴을 보여라. 패리티 비트는 맨 우측에 있다고 가정한다. 최상위 비트(MSB)가 메모리 내에서 바뀌었는데 그 값을 읽었다고 가정하면 에러를 검출할 수 있는가? 최상위 두 비트가 바뀌었다면 어떻게 되는가?
31은 이진수로 0011111이고 5개의 1이 있다. 패리티를 짝수로 하려면 패리티 비트에 000111111과 같이 1을 써야 한다. 만약 MSB가 바뀌었으면 100111111을 읽게 되어 1이 7개가 된다. 짝수 패리티를 기대하였으나 홀수 패리티가 계산되므로 에러이다.
만약 최상위 두 비트가 바뀌었다면 110111111이 되어 1이 8개가 된다. 짝수 패리티가 되므로 에러를 검출할 수 없다.
두 비트의 에러가 있으면 한 비트 패리티 방식은 에러를 검출하지 못한다. 패리티가 두 개의 에러가 있는 데이터와 일치하기 때문이다.
실제로 한 비트 패리티 방식은 어떤 홀수 개의 에러가 발생하더라도 검출할 수 있다. 그러나 3개의 에러를 가질 확률은 2개를 갖는 것보다 훨씬 작기 때문에 실제로는 한 비트 패리티 코드가 한 비트 에러를 검출하는 것으로 제한된다.
패리티 코드로는 에러를 정정할 수 없지만 Hamming은 검출뿐만 아니라 정정까지도 원했다. 최소 거리가 3인 코드를 사용하면 단일 비트 에러가 생긴 코드는 다른 어떤 유효한 패턴보다 원래의 옳은 패턴에 더 가까워질 것이다.
Hamming은 데이터를 거리 3인 코드로 사상하는 알기 쉬운 방법을 생각해 냈는데, 그의 이름을 따서 이것을 해밍 ECC(Hamming Error Correction Code)라고 부른다.
단일 에러의 위치를 파악할 수 있도록 패리티 비트를 하나 더 사용한다. 해밍 ECC를 계산하는 방법은 다음과 같다.
1.
일반적으로 사용되는 방법인 가장 오른쪽 비트 번호를 0으로 하는 전통적 방식 대신 왼쪽부터 1로 번호를 매긴다.
2.
2의 멱승에 위치한 모든 비트를 패리티 비트로 한다. (위치 1, 2, 4, 8, 16...)
3.
다른 모든 비트 위치는 데이터 비트로 사용한다. (위치 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, ...)
4.
패리티 비트의 위치에 따라 검사하는 데이터 비트가 결정된다. 그림 5.24에 이를 그림으로 보였다.
비트1 (0001)은 비트 (1, 3, 5, 7, 9, 11, ...)을 검사한다. 주소의 맨 오른쪽 값이 1인 것들이다. (0001, 0011, 0101, 0111, 1001, 1011, ...)
비트 2 (0010)는 비트 (2, 3, 6, 7, 10, 11, 14, 15, ...)을 검사한다. 주소의 오른쪽에서 두 번째 값이 1인 것들이다.
비트 4 (0100)은 비트 (4-7, 12-15, 20-23, ...)을 검사한다. 주소의 오른쪽에서 세 번째 값이 1인 것들이다.
비트 8 (1000)은 비트 (8-15, 24-31, 40-47, ...)을 검사한다. 주소의 오른쪽에서 네 번째 값이 1인 것들이다.
각 데이터 비트는 두 개 이상의 패리티 비트 계산에 관여함을 주목하라.
5.
각 그룹에 대해 짝수 패리티가 되도록 패리티 값을 정한다.
약간은 마술처럼 보일 수도 있지만 패리티 비트를 보면 어떤 비트가 잘못되었는지를 알 수 있다.
그림 5.24의 12비트 코드를 사용하여 4개의 패리티 계산(p8, p4, p2, p1)이 0000이면 에러는 없다.
그러나 패턴이 1010이면 십진수로 10이 되고 해밍 ECC는 10(d6)가 에러임을 알려 준다. 이진수 이므로 10번 비트 값을 바꾸어서 바로 잡을 수 있다.
(패턴이 0이 아닌 경우 해당 값을 십진수로 바꾸면 몇 번째 비트가 에러임을 바로 알 수 있다는 것)

예제)

바이트 데이터 값이 10011010 이라고 가정하자 먼저 해밍 ECC를 보여라. 비트 10을 반대로 한 다음 ECC 코드가 단일 비트 에러를 찾아서 정정하는 과정을 보여라
쿼리티 비트를 빈칸으로 하면 12비트 패턴은 __1_001_1010 이다.
워치 1은 비트 1, 3, 5, 7, 9, 11 (__1_001_101)을 검사한다. 이 그룹을 짝수 패리티로 만들기 위하여 비트 1은 0이 된다.
위치 2는 비트 2, 3, 6, 7, 10, 11 (0_1_001_1010)을 검사하고 홀수 패리티이므로 위치 2는 1이 된다.
위치 4는 비트 4, 5, 6, 7, 12 (011_001_101)을 검사하고 패리티는 1이 된다.
위치 8은 비트 8, 9, 11, 12 (0111001_1010)을 검사하고 패리티는 0이 된다.
최종 코드워드는 011100101010이 되고 10번째 비트를 역전시키면 011100101110이 된다.
패리티 비트 1은 0. 검사 비트의 1이 4개라 짝수 패리티이므로 문제 없음
패리티 비트 2는 1. 검사 비트의 1이 5개라 홀수 패리티 이므로 에러가 있음
패리티 비트 4는 1. 검사 비트의 1이 2개라 짝수 패리티이므로 문제 없음
패리티 비트 8은 1. 검사 비트의 1이 3개라 홀수 비트이므로 에러가 있음
패리티 비트 2와 8은 부정확하다. 2+8은 10이므로 비트 10이 잘못된 것이다. 따라서 비트 10을 바꾸면 에러가 정정된 값 011100101010을 얻을 수 있다.
Hamming은 단일 비트 에러 정정 코드에서 멈추지 않았다. 한 비트를 더 사용하면 코드의 최소 해밍 거리를 4로 만들 수 있는데, 이를 이용하여 단일 비트 에러를 정정하고 이중 비트 에러를 검출할 수 있다. 이를 위하여 전체 워드에 대한 패리티 한 비트를 추가한다.
4비트 데이터 워드를 예로 들어보자. 이 경우 7비트만 있으면 단일 비트 에러 검출이 가능하다. 해밍 패리티 비트 H(p1, p2, p3)를 계산하고(늘 그렇듯이 짝수 패리티를 사용함) 전체 워드에 대한 짝수 패리티 p4를 계산한다.
1(p1) 2(p2) 3(d1) 4(p3) 5(d2) 6(d3) 7(d4) 8(p4)
한 개의 에러를 정정하고 두 개를 검출하려면 전과 같이 ECC 그룹에 대한 패리티(H)를 계산하고 전체 그룹에 대한 패리티(p4)를 하나 더 계산하면 된다. 네 가지 경우가 있다.
1.
H가 짝수이고, p4도 짝수이면 에러 없음
2.
H가 홀수이고 p4도 홀수이면 정정 가능한 한 개의 에러가 발생하였음. (에러가 하나 발생하면 p4는 홀수 패리티가 된다.)
3.
H는 짝수이고 p4가 홀수이면 p4비트에 단일 에러가 발생한 것이므로 p4비트를 정정한다.
4.
H는 홀수이고 p4가 짝수이면 에러가 두 개 발생한 것이다. (에러가 두 개 발생하면 p4는 짝수 패리티가 된다.)
단일 에러 정정/이중 에러 검출(SEC/DED)은 오늘날 서버용 메모리에 널리 사용된다. 8바이트 크기의 블록은 SEC/DED 때문에 한 바이트가 더 필요하다. 그래서 크기가 72비트인 DIMM이 많다.

가상 머신

가상 머신(VM: Virtual Machine)은 1960년대 중반에 처음으로 개발되었으며, 수십 년에 걸쳐 메인프레임 컴퓨터의 중요한 부분으로 여전히 남아 있다. 비록 1980년대와 1990년대에는 단일 사용자 컴퓨터 영역에서 전반적으로 경시되었지만 VM 개념은 최근 다음과 같은 이유로 인기를 얻고 있다.
현대 시스템에서의 독립성과 보안성에 관한 중요도 증가
표준 운영체제에서의 보안성과 신뢰성의 실패
관련 없는 많은 사용자들이 하나의 컴퓨터를 공유함. 특히 클라우드 컴퓨팅 분야
지난 수 세기 동안 VM의 오버헤드를 감당할 수 있을만큼의 프로세서 속도의 획기적인 발전
가장 넓은 개념으로서의 VM은 Java의 VM 같은 표준 소프트웨어 인터페이스를 제공하는 모든 에뮬레이션(emulation) 방법들을 포함한다. 이 절에서는 이진 명령어 집합 구조(ISA: instruction set architecture)에서 와벽한 시스템 수준의 환경을 제공하는 VM에 대하여 다룬다.
비록 몇몇 VM은 실제 하드웨어와는 다른 VM의 ISA에서 동작하지만 우리는 그것들이 항상 하드웨어에 적합하다고 가정할 것이다.
이와 같은 VM은 운영체제 가상 머신(Operating System Virtual Machine)이라고 불리며, IBM VM/370, VirtualBox, VMware ESC Server, Xen 같은 것들이 있다.
운영체제 가상 머신은 사용자들이 운영체제를 포함한 전체 컴퓨터를 자신만이 쓰고 있다는 환상을 제공한다. 단일 컴퓨터는 여러 개의 VM을 실행시킬 수 있으며, 여러 개의 다른 OS를 지원할 수 있다.
전통적인 플랫폼에서는 하나의 OS가 모든 하드웨어 자원을 차지하지만, VM을 이용하면 여러 개의 OS가 하드웨어 자원을 공유한다.
VM을 지원하는 소프트웨어를 가상 머신 모니터(VMM: virtual machine monitor) 또는 하이퍼바이저(hypervisor)라고 부르며, 가상 머신 기술의 핵심이다. 기본이 되는 하드웨어 플랫폼을 호스트(host)라고 하고, 호스트의 자원은 손님(guest) VM들에 공유된다.
VMM은 가상 자원(virtual resource)을 어떻게 물리 자원(physical resource)으로 사상할 것인지를 결정한다.
물리 자원은 시분할(time-shared) 방식, 구역별(partitioned) 또는 소프트웨어적으로 에뮬레이트되어 사용될 것이다.
VMM은 전통적인 OS보다 훨씬 작다. VMM의 독립적인 부분은 아마도 10,000개 라인 정도의 코드로 이루어져 있을 것이다.
비록 우리의 관심은 보호를 강화하기 위한 VM에 있지만 VM은 상업적으로 중요한 두 가지 이점을 제공한다.
1.
소프트웨어 관리
VM은 DOS와 같은 오래된 운영체제뿐만 아니라 완벽한 소프트웨어 스택도 동작시킬 수 있는 추상화(abstraction)를 제공한다. 한 예로는 과거에 사용되던 OS, 현재 안정적으로 사용되는 많은 OS, 몇몇 테스트를 위한 새로운 OS를 수행하는 VM이 될 것이다.
2.
하드웨어 관리
다수의 서버를 사용하는 하나의 이유는 각 응용 프로그램이 분리된 컴퓨터의 적합한 운영체제 상에서 돌아가도록 하기 위해서이다. VM은 다양한 소프트웨어 스택이 하드웨어는 공유하면서 독립적으로 동작하는 것을 가능하게 한다.
또 다른 예로 VMM은 부하를 조절하거나 고장 난 하드웨어를 제외시키기 위해 동작하고 있는 VM을 다른 컴퓨터로 옮기는 것을 지원한다.
AWS(Amazon Web Services)는 EC2를 제공하는 클라우드 서비스에서 다섯 가지 이유로 가상 머신을 사용한다.
1.
사용자들이 같은 서버를 공유하는 동안 AWS는 각자를 보호할 수 있도록 해준다.
2.
대형 컴퓨터에서 소프트웨어 배포를 단순화해준다. 고객은 적합한 소프트웨어로 가상 머신 이미지를 설치하고 AWS는 고객이 원하는 소프트웨어를 배포해준다.
3.
고객(그리고 AWS)은 고객이 작업을 끝내면 자원 사용을 조절하기 위하여 VM을 안전하게 종료시킬 수 있다.
4.
가상 머신은 사용자가 어떤 하드웨어를 사용하는지를 숨길 수 있다. 따라서 AWS는 오래된 서버와 새로운 효율적인 서버를 동시에 유지할 수 있다. 고객은 'EC2 Compute Units'를 사용하여 원하는 성능을 기대할 수 있다.
EC2 Compute Units는 1.0-1.2 GHz 2007 AMD Opteron 또는 2007 Intel Xeon 프로세서와 같은 CPU 성능을 제공한다. Moore의 법칙에 따라 새로운 서버는 더 큰 EC2 Compute Units를 제공한다. 그러나 AWS는 오래된 서버도 경제적이기만 하면 계속 빌려준다.
5.
가상 머신 모니터는 VM이 사용하는 프로세서, 네트워크, 디스크 공간의 비율을 조절한다. 이렇게 함으로써 AWS는 같은 서버에서 사용되는 정도에 따라 다양한 가격을 제공할 수 있다. 예컨대 2012년 기준 AWS는 14가지 유형을 제공한다. 시간당 $0.08인 작은 표준형부터 시간당 $3.10인 I/O를 많이 사용하는 4배 더 큰 고가형을 제공한다.
일반적으로 프로세서 가상화의 비용은 작업부하(workload)에 달려 있다. 사용자 수준에서 프로세서를 집중적으로 사용한느 프로그램은 오버헤드가 거의 없다. 왜냐하면 OS가 거의 호출되지 않고 모든 것들이 정상 속도로 동작하기 때문이다.
I/O 관련 작업부하는 일반적으로 많은 시스템 호출, 특권(privileged) 명령어 사용, 운영체제의 관여를 요구하므로 가상화 비용이 많이 들게 된다.
그러나 I/O 관련 작업부하가 I/O를 집중적으로 사용하게 되면, 프로세서는 I/O를 기다리면서 사용되지 않는 시간이 많아지므로 프로세서 가상화 비용을 완전히 감출 수 있다.
오버헤드는 VMM에 의해 에뮬레이트 되어야 하는 명령어의 개수와 각 명령어의 에뮬레이션 시간에 의해 결정된다. 따라서 우리가 가정한 것처럼 손님 VM들이 호스트와 같은 ISA를 수행할 때, VMM과 구조의 공통 목적은 거의 모든 명령어들이 실제 하드웨어에서 바로 수행되는 것이다.

가상 머신 모니터(VMM)의 요구사항

가상 머신 모니터는 무슨 일을 하는가? 손님(guest) 소프트웨어에게 소프트웨어 인터페이스를 제공하고, 손님 소프트웨어의 상태를 다른 것들로부터 분리시켜야 하며, 손님 OS를 포함한 손님 소프트웨어로부터 자기 자신을 보호해야 한다. VMM의 요구사항은 다음과 같다.
손님 소프트웨어는 성능에 관련된 동작이나 여러 개의 VM과 공유하고 있는 고정된 자원의 한계를 제외하고는 마치 실제 하드웨어상에서 동작하는 것과 똑같이 VM 위에서 동작해야 한다.
손님 소프트웨어는 직접적으로 실제 시스템 자원 할당을 변경할 수 없다.
프로세서를 가상화하기 위하여 VMM은 손님 VM과 손님 OS가 일시적으로 사용하고 있더라도 특성 상태 접근, 주소 변환, I/O, 예외, 인터럽트와 같은 모든 것을 직접 제어해야 한다.
예컨대 타이머 인터럽트의 경우 VMM은 현재 동작하고 있는 손님 VM을 일시적으로 중지시키고 현재 상태를 저장한다. 그리고 인터럽트를 처리하고 이어서 어떤 손님 VM을 수행할지 결정하고 그 상태를 적재한다.
타이머 인터럽트와 관련된 손님 VM은 VMM에 의해서 가상 타이머와 에뮬레이트 된 타이머 인터럽트를 제공 받는다.
이러한 역할을 수행하기 위해 VMM은 일반적으로 사용자 모드에서 실행되는 손님 VM보다 높은 권한을 가져야 한다. 또한 이것은 어떠한 특권 명령어도 VMM이 처리할 수 있다는 것을 확실하게 해준다. 운영체제 가상 머신의 기본적인 요구사항은 다음과 같다.
최소한 두 개의 프로세서 모드, 시스템 모드와 사용자 모드
사용자 모드에서 실행하면 트랩을 발생시키는 시스템 모드에서만 유용한 특권 명령어. 모든 시스템 자원은 오직 이 명령어들에 의해서만 제어되어야 한다.

가상 머신을 지원하는 명령어 집합 구조(의 부족)

만약 VM이 ISA를 설계하는 동안 계획되었다면 VMM에서 실행해야만 하는 명령어의 개수와 에뮬레이션 속도를 줄이기가 상대적으로 쉬웠을 것이다.
VM을 하드웨어에서 직접 실행할 수 있는 구조는 가상화 가능(virtualizable)이라고 하며, IBM 370 구조는 자랑스럽게도 그 타이틀을 지니고 있다.
그러나 VM이 비교적 최근에 데스크톱과 PC 기반 서버 응용에 사용되었기 때문에 대부분의 명령어 집합들은 가상화를 염두에 두지 않고 만들어져 있다. 이에는 x86이나 ARM과 MIPS를 포함한 대부분의 RISC 시스템들이 포함된다.
VMM은 손님 시스템이 오직 가상 자원과 상호 작용하는 것만을 보장해야 하기 때문에, 기존의 손님 OS는 VMM 위에서 사용자 모드 프로그램으로 동작하게 된다.
만약 손님 OS가 특권 명령어를 이용하여 하드웨어 자원과 연관된 정보에 접근하거나 조작하려는 시도 —예컨대 페이지 테이블 포인터의 읽기와 쓰기—를 한다면 트랩이 발생한다. VMM은 해당되는 하드웨어 자원에 적절한 변경을 할 수 있다.
따라서 이처럼 중요한 정보를 읽거나 쓰는 시도를 하려는 어떠한 명령어가 사용자 모드에서 실행될 때 트립이 발생하면, VMM은 이를 가로채고 손님 OS가 요구하는대로 중요한 정보의 가상 버전을 지원할 수 있다.
위와 같은 지원 기능이 없을 때, 또 다른 방법들이 취해져야 한다. VMM은 손님 OS에 의해 실행될 때 문제의 소지가 있는 멸영어를 위치시키고 정상적으로 동작하도록 보장하기 위해 특별히 주의를 기울여야 한다. 이로 인해 VMM의 복잡도가 증가하게 되고 VM의 동작 성능이 떨어지게 된다.

보호와 명령어 집합 구조

보호는 구조와 운영체제의 노력이 합쳐진 것이다. 하지만 시스템 설계자들은 가상 메모리가 널리 사용되었을 떄, 현재의 명령어 집합 구조와 맞지 않는 세부 사항들을 수정해야 했다.
예컨대 x86 명령어 POPF는 메모리에 있는 스택의 최상위 값을 플래그 레지스터로 읽어들인다. 플래그들 중의 하나는 인터럽트 허용(IE: Interrupt Enable) 플래그다. 만일 사용자 모드에서 POPF 명령어를 실행시키면 트랩이 발생하는 대신 단순히 IE 플래그를 제외한 모든 플래그를 변경한다.
시스템 모드에서 실행되어야 IE 플래그를 변경한다. VM에서 손님 OS는 사용자 모드로 동작하지만 IE 플래그가 변경되기를 원하기 때문에 문제가 된다.
역사적으로 가상 머신의 성능을 향상시키기 위해 IBM 메인프레임 하드웨어와 VMM은 세 가지 단계를 밟아 왔다.
1.
프로세서 가상화의 비용을 줄인다.
2.
가상화로 인한 인터럽트 오버헤드 비용을 줄인다.
3.
VMM의 호출 없이 적절한 VM에게 인터럽트를 처리하게 하여 인터럽트 비용을 줄인다.

가상 메모리

앞 절에서 최근에 사용한 프로그램의 코드와 데이터 부분을 캐시가 어떻게 빨리 보낼 수 있는지 알아보았다. 이와 유사하게 메인 메모리가 보통 자기 디스크로 구현되는 2차 저장장치(secondary memory)를 위한 캐시로 이용될 수 있다. 이런 기술을 가상 메모리(virtual memory) 라고 부른다.
가상 메모리를 사용하는 두 가지 중요한 이유는 다수의 프로그램을 동시에 수행할 때 메모리를 효과적으로 공유할 수 있게 하고, 작고 제한된 크기의 메인 메모리에서 프로그래밍해야 하는 제약을 제거하기 위해서이다. 이 기법이 탄생한 지 50년이 지난 지금은 첫 번째 이유로 널리 사용되고 있다.
다수의 가상 머신이 같은 메모리를 사용하는 경우를 살펴보자. 가상 머신이 각자 보호될 수 있도록 보장하고 각 프로그램은 자신에게 할당된 메인 메모리의 부분에만 읽고 쓸 수 있도록 보장하여야만 한다.
캐시가 한 프로그램의 활성화된 부분만을 담고 있는 것과 마찬가지로 메인 메모리도 많은 가상 머신의 활성화된 부분만을 담고 있어야 한다. 따라서 지역성의 원칙은 캐시 뿐만 아니라 가상 메모리에도 적용된다. 가상 메모리는 메인 메모리 뿐만 아니라 프로세서까지도 효율적으로 공유하게 해준다.
프로그램을 컴파일할 때는 가상 머신이 다른 어떤 가상 머신과 메모리를 공유할 지는 알 수 없다. 실제로 메모리를 공유하는 가상 머신은 가상 머신들이 수행되는 동안 동적으로 변하게 된다.
이러한 동적 상호작용 때문에 각 프로그램들이 자신만의 주소공간(address space) 즉 프로그램에 의해서만 접근 가능한 분리된 메모리 영역에서 컴파일 되어야 한다.
가상 메모리는 프로그램의 주소공간을 실제 주소(physical address)로 변환해 준다. 이러한 변환 과정이 한 프로그램의 주소공간을 다른 가상 머신으로부터 보호(protection)해 준다.
가상 메모리가 생겨나게 된 두 번째 동기는 사용자 프로그램을 메인 메모리의 크기보다 더 크게 작성할 수 있도록 해주는 것이다.
이전에는 프로그램이 메인 메모리보다 더 클 경우에는 프로그래머가 프로그램을 알맞게 조정해야만 했다. 즉 프로그래머는 프로그램들을 작은 조각으로 나누고 이들이 서로 상관관계가 없더록 작성해야만 했다.
이와 같은 오버레이는 수행 도중 사용자 프로그램 제어하에 적재되거나 제거되어야 한다. 프로그래머는 프로그램이 적재되지 않은 오버레이에 접근하지 않고, 적재된 오버레이는 전체 메모리 크기보다 더 커지지 않도록 보장하여야 한다.
오버레이는 전통적으로 모듈로 구성되었으며 각 모듈은 코드와 데이터를 갖고 있다. 다른 모듈에 속한 프로시저 사이의 호출이 발생하면 한 모듈 위에 다른 모듈이 겹쳐 써질 수 있다.
상상할 수 있겠지만 이와 같은 제약은 프로그래머에게는 매우 큰 부담이다. 이런 어려움으로부터 프로그래머를 해방시킨 가상 메모리는 자동으로 메인 메모리 —때로는 가상 메모리와 구별하기 위해 실제 메모리(physical memory)라고도 부름— 와 2차 기억장치로 구성되는 두 단계의 메모리 계층을 관리한다.
가상 메모리와 캐시에 사용되는 개념이 같을지라도 역사적 배경이 다르기 때문에 다른 용어를 사용하게 되었다.
가상 메모리 블록은 페이지(page)라 불리고, 가상 메모리 실패는 페이지 부재(page fault)라 불린다.
가상 메모리를 갖는 프로세서는 가상 주소(virtual address)를 만들어내고, 가상 주소는 하드웨어와 소프트웨어의 조합에 의해 메인 메모리 접근에 사용되는 실제 주소(physical address)로 변환된다.
그림 5.25는 메인 메모리에 사상된 페이지와 함께 가상 주소로 접근되는 메모리를 보여주고 있다. 이런 작업을 주소 사상(address mapping) 혹은 주소 변환(address translation)이라고 한다.
오늘날 가상 메모리에 의해 제어되는 2개의 메모리 계층은 일반적으로 개인용 휴대기기에서는 DRAM과 플래시 메모리이고 서버에서는 DRAM과 자기 디스크이다. 도서관의 예로 돌아가면 가상 주소를 책의 제목으로 생각할 수 있고, 실제 주소를 의회 도서관의 호출 번호와 같이 도서관 내 그 책의 위치로 비유할 수 있다.
가상 메모리 재배치(relocation) 기능을 제공하여 수행될 프로그램의 적재를 단순화한다. 재배치는 프로그램에 의해 사용되는 가상 주소를 메모리에 접근하는데 사용되기 이전에 다른 실제 주소로 사상시켜 준다. 이 재배치는 메인 메모리 내의 어떤 위치에도 프로그램을 적재할 수 있게 한다.
게다가 오늘날 쓰이는 모든 가상 메모리 시스템은 프로그램을 고정된 크기로 이루어진 블록(페이지)의 집합으로 재배치 시킨다. 따라서 프로그램을 할당하기 위해 메모리에서 연속적인 블록을 찾아낼 필요가 없게 되었다. 대신에 운영체제는 메인 메모리 내에 충분한 페이지가 있는지만을 확인하면 된다.
가상 메모리 시스템의 주소는 가상 페이지 번호(virtual page number) 및 페이지 변위(page offset)로 나누어진다. 그림 5.26은 가상 페이지 번호가 실제 페이지 번호(physical page number)로 변환되는 것을 보여준다.
실제 페이지 번호는 실제 주소의 상위 부분으로 이루어지는 반면에, 변화되지 않은 페이지 변위는 하위 부분으로 구성된다.
페이지 변위 필드의 비트 수는 페이지의 크기를 결정한다. 가상 주소로 참조 가능한 페이지 수는 실제 주소로 참조 가능한 페이지 수와 같지 않아도 된다. 실제 페이지보다 더 많은 가상 페이지 수를 갖는 것은 무제한의 큰 가상 메모리를 갖는 것과 같은 환상을 준다.
가상 메모리에서 전통적으로 페이지 부재(page fault)라고 불리어 온 실패의 처리에 소요되는 높은 비용을 줄이기 위해 많은 설계 방법들이 제시되었다.
페이지 부재는 처리하는데 수백만 사이클이 소요된다. 보통 크기의 페이지의 경우 첫 번째 워드를 꺼내는데 걸리는 시간이 거의 대부분인 이러한 어마어마한 실패 손실 때문에, 가상 메모리를 설계하는데 있어서 다음과 같은 몇 가지 중요한 결정이 내려졌다.
페이지는 큰 접근 시간을 보상할 만큼 충분히 커야 한다. 4 KiB 내지 16 KiB 크기가 오늘날 일반적이다. 새로운 데스크톱과 서버 시스템이 32 KiB와 64 KiB를 지원하도록 개발되고 있다. 그러나 새로운 임베디드 시스템들은 반대 방향으로 발전하고 있어 페이지 크기가 1 KiB 정도이다.
페이지 부재 발생률을 줄이는 구현이 바람직하다. 이를 위해 사용되는 주된 기법은 페이지를 완전 연관 방식으로 배치하는 것이다.
페이지 부재는 소프트웨어로 다루어질 수도 있다. 이 부담이 디스크에 접근하는 시간과 비교할 때 작기 때문이다. 게다가 소프트웨어는 페이지를 어떻게 배치할 것인가를 위해 효율적인 알고리즘을 사용할 수 있게 한다. 왜냐하면 실패율의 작은 감소로도 충분히 그러한 알고리즘의 비용을 보상할 수 있기 때문이다.
가상 메모리에서 쓰기를 수행할 때 즉시 쓰기 방식을 사용하는 것은 시간이 오래 걸리기 때문에 실용적이지 못하다. 대신에 가상 메모리 시스템은 나중 쓰기 방식을 사용한다.

페이지 배치와 다시 찾기

페이지 부재의 손실이 엄청나게 크기 때문에 시스템 설계자는 페이지 배치를 최적화 함으로써 페이지 부재 발생 수를 줄이고자 한다. 가상 페이지가 어떤 실제 페이지로 사상될 수 있게 하면, 운영체제는 페이지 부재 발생 시에 어떤 페이지든 마음대로 선택할 수 있다.
예컨대 운영체제는 페이지 사용을 추적하는 정교한 알고리즘과 복잡한 자료구조를 사용하여 앞으로 오랫동안 필요하지 않을 것 같은 페이지를 선택할 수 있다.
유연하고 효과적인 교체 방식을 사용함으로써 페이지 부재 발생률을 낮출 수 있고 완전 연관 페이지 배치 방식의 사용을 단순화 할 수 있다.
5.4절에서 언급한 것과 같이 완전 연관 방식을 사용하는데 있어서의 가장 큰 어려움은 엔트리의 위치를 알아내는 것이다. 왜냐하면 상위 계층의 어디에도 있을 수 있기 때문이다.
완전 검색은 비실용적이다. 가상 메모리 시스템에서는 메모리를 인덱스하는 표를 사용한다. 이 구조는 페이지 테이블(page table)이라고 불리고 메모리 내부에 존재한다.
페이지 테이블은 가상 주소의 페이지 번호로 인덱스 되어 있고, 대응되는 실제 페이지 번호를 갖고 있다. 각 프로그램은 각자 자신의 페이지 테이블을 갖고 있으며, 페이지 테이블은 그 프로그램의 가상 주소공간을 메인 메모리로 사상한다.
도서관과 비교했을 때, 페이지 테이블은 책 이름과 도서관의 실제 위치 사이의 사상에 해당된다. 한 도서관의 도서카드가 자기 도서관이 아닌 캠퍼스 내 다른 도서관의 도서 목록을 포함하고 있는 것과 같이 페이지 테이블은 메모리에 적재되지 않은 페이지의 엔트리를 포함할 수 있다.
메모리 내 페이지 테이블의 위치를 나타내가 위해 하드웨어는 페이지 테이블의 시작 주소를 나타내는 레지스터를 포함하고 있다. 이 레지스터를 페이지 테이블 레지스터(page table register)라고 부른다. 당분간은 페이지 테이블이 메모리 내부에 고정되고 연속된 영역을 차지하고 있다고 가정하자.
그림 5.27은 페이지 테이블 레지스터, 가상 주소와 페이지 테이블을 이용하여 어떻게 하드웨어가 실제 주소를 만들어 내는지를 보여준다.
유효(valid) 비트는 캐시에서 사용되었던 것처럼 각 페이지 테이블 엔트리에서 사용된다. 만약 이 비트가 0이면 그 페이지는 메인 메모리에 존재하지 않고, 따라서 페이지 부재가 발생된다. 이 비트가 1이면 그 페이지는 메모리 내부에 있으며, 그 엔트리는 실제 페이지 번호를 갖고 있다.
페이지 테이블은 모든 가능한 가상 페이지에 대한 사상을 다 갖고 있기 때문에, 태그가 필요하지 않다. 캐시 용어로 설명하면 페이지 테이블 접근에 사용되는 인덱스는 완전한 블록 주소인 가상 페이지 번호로 되어 있다.
프로그램 카운터 및 레지스터들과 함께 페이지 테이블은 프로그램의 상태(state)를 표시한다. 다른 프로그램이 프로세서를 사용하게 하려면 이 상태를 보존해야만 한다.
나중에 이 상태를 완벽하게 복구한 다음, 그 프로그램의 수행을 계속할 수 있다. 이런 상태를 프로세서(process)라고 한다. 프로세스가 프로세서를 점유하고 있을 때를 활성화 상태(active state)라 하고, 그 반대의 경우를 비활성화 상태(inactive state)라고 한다.
운영체제는 프로그램 카운터를 포함하는 프로세서의 상태를 다시 적재함으로써 프로세스를 활성화 상태로 만들고, 저장된 프로그램 카운터의 값을 이용하여 수행을 다시 시작한다.
프로세스의 주소공간과 사용할 수 있는 메모리 내의 모든 데이터들은 메모리 내부에 존재하는 페이지 테이블에 의해 정의된다.
운영체제는 전체 페이지 테이블을 저장하는 대신, 활성화 하려는 프로세스의 페이지 테이블의 주소를 페이지 테이블 레지스터에 적재한다. 각 프로그램은 그 자신의 페이지 테이블을 갖고 있다.
왜냐하면 다른 프로세스들이 똑같은 가상 주소를 사용하기 때문이다. 운영체제가 실제 메모리를 할당하고 페이지 테이블을 갱신시킬 책임을 지고 있다. 이렇게 함으로써 다른 프로세스들의 가상 주소공간들이 충돌하지 않게 된다. 분리된 페이지 테이블을 사용함으로써 여러 프로세스들 사이에 보호 기능을 제공할 수 있다.

페이지 부재

가상 페이지의 유효 비트가 0이면 페이지 부재가 발생하며, 운영체제가 제어를 넘겨 받게 된다. 이는 이 절의 뒷부분에서 자세히 다루게 될 예외(exception) 메커니즘에 의해 행해진다.
운영체제가 제어를 갖게 되면 계층의 다음 수준(대개 자기 디스크)에서 그 페이지를 찾아야 하며, 요구된 페이지를 메인 메모리의 어디에 배치시킬 것인지 결정해야 한다.
가상 주소 하나만으로는 디스크 내에 그 페이지가 어디에 있는지를 바로 알 수 없다. 도서관 예로 돌아가서 책 이름만으로는 도서관 내 책의 위치를 알 수 없다. 대신 일람표를 뒤져 책을 찾아야만 서가 내 책 위치를 알아낼 수 있다.
이와 같이 가상 메모리 시스템에서는 가상 주소공간 내 페이지의 디스크상 위치를 알고 있어야 한다.
메모리 내의 페이지가 언제 쫓겨날지를 미리 알 수 없기 때문에, 운영체제는 대개 프로세스를 생성시킬 때 프로세스의 모든 페이지를 위한 공간을 플래시 메모리나 디스크 상에 마련한다. 이 디스크상의 공간을 스왑 스페이스(swap space)라고 부른다.
이때 각 가상 페이지가 디스크의 어느 곳에 저장되는지를 기록하기 위한 자료구조를 만든다. 이 자료구조는 페이지 테이블의 일부분일 수 있고 페이지 테이블과 같은 방법으로 인덱스되는 다른 자료구조일 수도 있다.
그림 5.28은 단일 테이블이 실제 페이지 번호나 디스크 주소를 담고 있을 때의 구조를 보여준다.
운영체제는 또한 어떤 프로세스와 어떤 가상 주소가 각 실제 페이지를 사용하는지를 추적하는 자료구조를 만든다. 페이지 부재가 발생했을 때, 메인 메모리 내의 모든 페이지가 사용 중이면 운영체제는 교체할 페이지를 선택해야만 한다.
페이지 부재의 수를 최소화해야 하기 때문에, 대부분의 운영체제는 가까운 시간 내에 사용되지 않을 페이지를 선정하려고 한다. 미래를 예측하기 위해 과거를 사용하여, 운영체제는 LRU(least recently used) 교체 방식을 따른다.
최근에 가장 덜 사용된 페이지가 더 자주 사용된 페이지보다 앞으로 이용될 가능성이 적다는 가정을 이용하여 가장 덜 사용된 페이지를 찾는다. 교체된 페이지는 디스크상의 스왑 스페이스에 쓰인다.
운영체제 또한 또 하나의 프로세스이며 메모리를 제어하는 테이블 또한 메모리에 위치한다.
완벽하게 LRU 방식을 구현하는 것은 메모리를 참조할 때마다 자료구조를 갱신해야 하기 때문에 비용이 매우 많이 든다. 대신에 많은 운영체제는 최근에 어떤 페이지가 참조되고 참조되지 않았는지를 추적하는 LRU 방식을 사용한다.
운영체제가 LRU 페이지를 찾는 것을 돕기 위해, 어떤 시스템에서는 페이지가 접근될 때마다 1 값을 갖는 참조 비트(reference bit) 또는 사용 비트(use bit)를 제공한다.
운영체제는 주기적으로 참조 비트를 0으로 만들고 후에 다시 기록한다. 이렇게 함으로써 특정 시간 동안 어떤 페이지들이 접근되었는지를 알 수 있다.
이 사용 정보를 이용하여 운영체제는 최근에 가장 덜 참조된 것들(참조 비트가 0으로 있는 것들) 중 하나를 선택할 수 있다.
만약 이러한 비트들이 하드웨어적으로 제공되지 않는다면 운영체제는 어떤 페이지가 접근되었었는지를 예측하기 위한 다른 방법을 찾아야만 한다.

쓰기는 어떻게 처리되는가?

캐시의 접근 시간과 메인 메모리의 접근 시간 사이의 차이는 수십에서 수백 사이클 정도이고, 프로세서로부터 쓰기 지연 시간을 줄이기 위해 쓰기 버퍼를 사용함으로써 즉시 쓰기 기법을 이용할 수 있었다.
가상 메모리의 경우 계층구조의 다음 계층(디스크)에 쓰기는 수백만 사이클이 소요된다. 그러므로 디스크에 쓰기 위해 시스템을 즉시 쓰기 방식으로 구현하고 쓰기 버퍼를 첨가하는 것은 매우 비실용적이다.
대신에 가상 메모리 시스템에서는 나중 쓰기 방식을 사용한다. 나중 쓰기 방식에서 각각의 쓰기 동작은 메인 메모리 상의 페이지에만 수행된다. 그리고 페이지가 메모리에서 교체될 때 디스크로 복사가 된다.
나중 쓰기 방식은 가상 메모리 시스템의 또 하나의 큰 장점이다. 디스크의 전송 시간이 디스크 접근 시간보다 짧기 때문에 전체 페이지를 저장하는 것이 각각의 워드를 디스크로 저장하는 것보다 훨씬 더 능률적이다.
나중 쓰기 방식은 각각의 워드를 전송하는 것보다 능률적이지만 역시 추가되는 비용이 있다. 즉 교체할 페이지가 결정되면 이 페이지가 디스크로 저장되어야 하는지를 알 필요가 있다.
메모리에 적재된 이후 페이지가 변화되었는지를 추적하기 위해 페이지 테이블에 갱신 비트(dirty bit)를 추가한다. 페이지 내의 어떤 워드에 변화가 생길 때 이 갱신 비트가 1 값을 갖게 된다.
운영체제가 어떤 페이지를 바꾸기 위해 선택하면 갱신 비트는 새로운 페이지에게 공간을 내주기 전에 그 페이지를 디스크에 써야 할지 여부를 알려준다. 그래서 수정된 페이지를 종종 갱신 페이지(dirty page)라고 부른다.

주소 변환을 빠르게 하기: TLB

페이지 테이블은 메인 메모리에 저장되기 때문에 프로그램에 의한 모든 메모리 접근은 최소한 두 번 필요하게 된다. 실제 주소를 얻기 위한 메모리 접근 한 번과 데이터를 얻기 위한 또 한 번의 접근이 필요하다.
접근 성능을 높이기 위한 핵심은 페이지 테이블에 대한 참조의 지역성에 달려 있다. 어떤 가상 페이지 번호의 변환이 사용되면, 페이지상의 워드 참조는 공간적 지역성과 시간적 지역성을 갖기 때문에 그 페이지는 또 다시 참조될 가능성이 높다.
따라서 요즘의 컴퓨터들은 최근에 사용된 변환을 추적하는 특별한 캐시를 갖고 있다. 이 특별한 주소 변환 전용 캐시는 전통적으로 변환 참조용 버퍼(TLB: translation-lookaside buffer)라고 불린다. 이 버퍼는 변환 캐시라고 부르는게 더 정확한 표현일 수도 있다.
TLB는 도서 카드에서 찾아본 일련의 책들의 위치를 기록하는데 쓰이는 작은 종이에 대응된다. 전체 도서 카드를 계속해서 찾는게 아니라 여러 책들의 위치를 종이에 기록하고 이 종이를 마치 캐시처럼 사용하는 것과 같다.
그림 5.29는 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 실패는 페이지 부재보다 더 빈번히 발생되고 더 값싸게 처리되어야만 하기 때문에, 페이지 부재 시 사용했던 것과 같은 비싼 소프트웨어 알고리즘을 사용할 수 없다.
결론적으로 많은 시스템들은 교체할 엔트리를 임의로 선정하는 기능을 제공한다.

Instrinsity FastMATH TLB

이러한 아이디어들이 실제로 어떻게 동작하는지를 살펴보기 위해 Intrinsity FastMath의 TLB를 자세히 살펴보자. 이 메모리 시스템은 4 KiB의 페이지를 사용하고 32비트 주소공간을 갖는다. 따라서 그림 5.30에 보이는 것과 같이 가상 페이지 번호는 20비트 크기를 갖는다.
실제 주소는 가상 주소와 같은 크기를 갖는다. 16개의 엔트리를 갖는 TLB는 완전 연관 사상 방식을 사용하고, 명령어와 데이터 참조에 공유된다.
각 엔트리는 64비트이며, 20비트 태그(이 TLB 엔트리의 가상 페이지 번호), 대응되는 실제 페이지 번호(20비트), 유효 비트, 갱신 비트 및 다른 보조(book-keeping) 비트들을 갖는다. MIPS 시스템과 같이 TLB 실패를 처리하기 위해 소프트웨어를 사용한다.
그림 5.30은 TLB와 캐시 중 한 개를 보여 주고 그림 5.31은 읽기와 쓰기 요청을 처리하는 단계를 보여준다.
TLB 실패가 발생하면 MIPS 하드웨어는 그 참조의 페이지 번호를 특수 레지스터에 저장하고 예외를 발생시킨다. 예외는 운영체제로 하여금 실패를 소프트웨어로 처리하게끔 한다.
실패가 발생한 페이지의 실제 주소를 찾기 위해 TLB 실패 루틴은 가상 주소의 페이지 번호와 활성화된 프로세스 페이지 테이블의 시작 주소를 갖고 있는 페이지 테이블 레지스터를 사용하여 페이지 테이블을 인덱스 한다.
TLB를 갱신할 수 있는 특수한 시스템 명령어들을 사용하여 운영체제는 실제 주소를 페이지 테이블로부터 TLB로 적재시킨다. 코드는 명령어 캐시에 페이지 테이블 엔트리는 데이터 캐시에 각각 들어 있다고 가정할 때 TLB 실패는 약 13 사이클 정도 소요된다.
진짜 페이지 부재는 페이지 테이블 엔트리가 유효한 실제 주소를 갖고 있지 않을 때 발생한다. 하드웨어는 교체 대상으로 추천된 엔트리를 가리키는 인덱스를 유지한다. 추천 엔트리는 임의로 선택된다.
쓰기 요청 시에는 부가되는 복잡함이 있다. 즉 TLB의 쓰기 접근 비트를 검사하여야만 한다.
이 비트는 프로그램이 읽기 접근만 허용하는 페이지에 쓰는 것을 막는다. 쓰기 접근 비트가 0일 떄 프로그램이 쓰기를 시도하면 예외가 발생한다. 쓰기 접근 비트는 곧 살펴보게 될 보호 기능의 일부분이다.

가상 메모리, TLB와 캐시의 통합

우리의 가상 메모리와 캐시 시스템은 계층구조를 이루며 같이 동작한다. 따라서 데이터가 메인 메모리에 없다면 그 데이터는 캐시에 있을 수가 없다. 운영체제는 페이지를 디스크로 옮기기로 결정하면 캐시에서 해당 페이지를 제거함으로써 이 계층구조를 유지하는 역할을 수행한다.
동시에 운영체제는 페이지 테이블과 TLB를 수정함으로써 해당 페이지의 데이터에 접근하려고 시도하는 경우 페이지 부재를 일으키게 된다.
가장 좋은 경우는 가상 주소가 TLB에 의해 변환되고 캐시로 보내져서 원하는 데이터를 찾아내서 프로세서로 보내는 것이다. 가장 안 좋은 경우는 참조가 메모리 계층구조의 모든 세 가지 요소, 즉 TLB, 페이지 테이블, 그리고 캐시에서 실패를 발생시키는 경우이다.
다음의 예는 이 관계를 더 자세히 설명한다.

예제) 메모리 계층구조의 전체적인 동작

TLB와 캐시로 이루어진 그림 5.30과 같은 메모리 계층구조에서는 메모리 참조시 TLB 실패, 페이지 부재, 캐시 실패의 세 가지 다른 형태의 실패가 존재하게 된다. 이 세가지 종류의 조합(7가지 가능성)을 살펴보자. 각 가능성에 대해 이 사건이 실제로 발생하는지 또는 어떤 환경에서 발생하는지를 답하라.
그림 5.32는 가능한 환경들과 이들이 실제로 발생할 수 있는지 여부를 보여 준다.

가상 메모리의 보호 구현

가상 메모리의 가장 중요한 기능 중의 하나는 여러 프로세스가 하나의 메인 메모리를 공유하도록 허용하는 것이다. 그러나 이 프로세스들과 운영체제 사이에 메모리 보호 기능을 제공해야만 한다.
이 보호 기능은 다수의 프로세스가 같은 메모리를 공유한다 할지라도 어떤 악의를 품은 프로세스가 다른 사용자의 프로세스의 주소공간에 쓰기를 수행하거나 고의적으로 또는 실수로 운영체제의 주소공간에 쓰기를 수행할 수 없도록 보장해야만 한다.
TLB의 쓰기 접근 비트가 페이지를 보호할 수 있다. 이 정도 수준의 보호조차 없다면 컴퓨터 바이러스가 더 빨리 퍼져 나가게 될 것이다.
또한 어떤 프로세스가 다른 프로세스의 데이터를 읽어 오는 것도 막아야 한다. 예컨대 성적이 프로세서의 메모리에 있는 동안 학생의 프로그램이 그 성적을 읽어 올 수 있게끔 만들지 안항야 한다.
한 번 메인 메모리 공유가 허용되면 다른 프로세스가 자신의 데이터를 읽거나 쓰지 못하게 하는 기능이 제공되어야 한다. 그렇지 않으면 메인 메모리 공유는 뒤죽박죽이 될 것이다.
각 프로세스는 각각의 가상 주소공간을 가지고 있음을 기억하라. 그래서 만약 각각의 가상 페이지가 서로 분리된 실제 페이지로 사상 되게끔 운영체제가 페이지 테이블을 구성하면, 어떤 프로세스는 다른 프로세스의 데이터에 접근할 수 없게 된다.
물론 이렇게 되기 위해서는 사용자 프로세스가 페이지 테이블 사상을 변화시키지 못하게 해야 한다. 운영체제가 사용자 프로세스 스스로 자신의 페이지 테이블을 수정할 수 없게 하면 이런 것은 보장할 수 있다.
그러나 운영체제는 페이지 테이블을 수정할 수 있어야만 한다. 페이지 테이블을 운영체제의 보호된 주소공간에 배치함으로써 두 가지 요구를 만족시킬 수 있다.
가상 메모리 시스템에서 운영체제가 보호를 구현할 수 있게 하기 위해서는 하드웨어가 최소한 다음 세 가지 기본적인 능력을 제공해야만 한다. 처음 2개는 가상 머신에서 필요한 것과 같은 요구사항이다.
1.
수행 중인 프로세스가 사용자 프로세스인지 또는 관리자 프로세스(supervisor process), 커널 프로세스(kernel process), 실행 감독 프로세스 등으로 불리는 운영체제 프로세스인지를 나타내 주는 최소한 두 가지 프로세스를 지원한다.
2.
프로세서 상태의 일부를 사용자 프로세스가 읽기만 할 수 있고 쓰기는 불가능 하도록 한다. 이것은 프로세서가 사용자 모드인지 관리자 모드인지인지를 알려 주는 사용자/관리자 모드 비트, 페이지 테이블 포인터와 TLB를 포함한다.
이 요소들을 쓰기 위해 운영체제는 관리자 모드에서만 사용 가능한 특수 명령어를 사용한다.
3.
프로세서가 사용자 모드에서 관리자 모드로 혹은 반대로 변화될 수 있는 메커니즘을 제공한다.
첫 번째 방향으로의 전환은 시스템 호출(system call) 예외 처리 방식으로 실현된다. 이 방법은 관리자 코드 공간의 정해진 위치로 제어를 넘겨줌으로써 구현된다. (MIPS 명령어 집합의 syscall 명령어)
다른 예외 처리와 똑같이 시스템 호출을 할 당시의 PC 값은 EPC에 저장되고, 프로세서는 관리자 모드로 넘어가게 된다. 예외 처리를 끝내고 사용자로 되돌아가는 것은 ERET(return from exception) 명령어를 사용하는데, 이 명령어는 프로세서를 사용자 모드로 바꾸고 EPC에 저장된 주소로 점프하게 된다.
이런 방법을 사용하고 운영체제의 주소 공간에 페이지 테이블을 저장함으로써 운영체제는 페이지 테이블을 변화시킬 수 있다. 동시에 사용자 프로세스가 페이지 테이블을 변환시키는 것을 막을 수 있으며, 또한 사용자 프로세스는 운영체제에 의해 제공되는 저장 공간에만 접근할 수 있게 된다.
프로세스들이 제한된 방법으로 정보를 공유해야 할 때, 운영체제가 이를 지원해 주어야 한다. 다른 프로세스의 정보에 접근하는 것은 접근하는 프로세스의 페이지 테이블의 변경을 요구하기 때문이다.
쓰기 접근 비트는 읽기 공유만을 하도록 제한하는데 사용되고, 나머지 페이지 테이블처럼 이 비트도 운영체제에 의해서만 변경될 수 있다.
예컨대 프로세스 P1이 프로세스 P2 소유의 페이지를 읽을 수 있게 하기 위해서 P2는 운영체제에 공유하기를 원하는 실제 페이지를 가리키는 가상 페이지를 P1의 주소공간에 할당하고 이를 페이지 테입르에 넣도록 요청한다.
P2가 보호받기를 원하면 운영체제는 쓰기 보호 비트로 P1이 데이터를 쓸 수 없게 할 수 있다. 페이지 테이블이 TLB 실패 시에만 접근되기 떄문에, 페이지에 대한 접근 권한을 결정하는 모든 비트들은 페이지 테이블과 TLB 양쪽에 포함되어야만 한다.

페이지 부재와 TLB 실패의 처리

TLB 적중 시에는 TLB에서 가상 주소에서 실제 주소로의 변환이 곧바로 일어나지만 TLB 실패와 페이지 부재 시의 처리는 훨씬 복잡하다. TLB 실패는 TLB 내 엔트리가 가상 주소와 일치하는 것이 없을 때 발생한다. TLB 실패는 다음 두 가지 중의 하나이다.
1.
페이지가 메모리에 있는 경우 실패가 발생한 TLB 엔트리만 만들면 된다.
2.
페이지가 메모리에 없는 경우 페이지 부재를 처리하기 위해 제어를 운영체제로 넘겨야 한다.
MIPS는 전통적으로 TLB 실패를 소프트웨어로 처리하였다. 메모리로부터 페이지 테이블 엔트리를 가져오고 TLB 실패를 발생시킨 명령어를 다시 수행한다. 다시 수행하면 TLB 성공이 될 것이다. 페이지 테이블 엔트리가 페이지가 메모리에 없다고 하면 페이지 부재 예외가 발생한다.
TLB 실패 혹은 페이지 부재 처리는 실행 중인 프로세스를 인터럽트하여 운영체제로 넘기고 중단된 프로세스를 나중에 계속 실행하는 예외 처리 방식을 이용한다.
페이지 부재는 메모리에 접근하는 클럭 사이클 도중에 인식된다. 페이지 부재를 처리하고 난 후 명령어를 다시 시작하기 위해서는 페이지 부재를 일으킨 명령어의 주소를 갖고 있는 프로그램 카운터 값이 저장되어야만 한다. 4장에서 살펴본 것과 같이 EPC가 이 값을 저장하기 위해 사용된다.
또한 TLB 실패 혹은 페이지 부재 예외는 메모리 접근이 발생하는 사이클의 끝 부분에서 처리되어야 한다. 다음 클럭 사이클이 정상적인 명령어 수행을 하는 대신에 예외 처리를 시작할 수 있도록 하기 위함이다.
페이지 부재가 이 클럭 사이클에서 인식되지 못하면 적재 명령어는 레지스터의 내용을 바꾸어 버릴 수 있고, 그 명령어를 다시 시작할 때 큰 혼란을 야기할 수 있다.
예컨대 명령어 lw $1, 0($1)이 수행될 때 시스템은 쓰기 파이프라인 단계가 동작하지 않도록 해야만 한다. 그렇지 않으면 $1의 내용이 지워져 버리기 때문에 그 명령어를 적절히 재수행 시킬 수 없다.
저장 명령어의 경우도 마찬가지다. 페이지 부재가 발생될 때는 메모리로 기록하는 것을 막아야 한다. 이런 것은 쓰기 제어 신호를 메모리에 인가하지 않음으로써 가능하다.
운영체제에서 예외 핸들러를 수행시킬 때부터 운영체제가 프로세서의 모든 상태를 저장하기까지는 프로세서가 매우 취약한 상태이다.
예컨대 첫 번째 예외를 처리하고 있을 때 다른 예외가 발생하면 제어 유닛은 EPC를 갱신하게 되어 페이지 부재를 발생시킨 명령어로 돌아가는 것이 불가능하게 된다. 우리는 예외 활성화(exception enable)나 비활성화로 이 재난을 피할 수 있다.
일단 예외가 발생하면 프로세서는 다른 모든 예외를 비활성화하는 비트를 1로 만든다. 이 비트는 프로세서가 관리자 모드 비트를 1로 하는 것과 같은 시간에 1이 된다. 이제는 운영체제가 다른 예외가 발생하더라도 복구할 수 있도록 EPC와 원인 레지스터를 저장할 수 있다.
EPC와 원인 레지스터는 예외와 TLB 실패 그리고 페이지 부재 처리를 도와주는 두 개의 특수 제어 레지스터이다. 그림 5.33은 나머지를 보여준다. 이제 운영체제는 다시 예외를 활성화할 수 있다.
이러한 과정은 예외가 프로세서의 상태를 잃어버리지 않고 인터럽트를 유발시킨 명령어들 다시 수행할 수 있도록 해준다.
운영체제가 페이지 부재를 일으킨 가상 주소를 알게 되면 다음 세 단계를 수행하게 된다.
1.
가상 주소를 사용해서 페이지 테이블 엔트리를 찾고 디스크 내에서 참조된 페이지의 위치를 찾는다.
2.
교체시킬 실제 페이지를 선정한다. 만약 선정된 페이지의 갱신 비트가 1이면 새로운 가상 페이지를 이 실제 페이지로 가져오기 전에 먼저 디스크에 기록해야 한다.
3.
참조된 페이지를 선정된 실제 페이지로 가져오기 위해 디스크 읽기를 시작한다.
물론 이 마지막 단계는 수백만 프로세서 사이클이 걸린다 *교체될 페이지의 갱신 비트가 설정되어 있으면 단계 2도 마찬가지다) 따라서 운영체제는 디스크 접근이 끝날 때까지 프로세서에서 수행될 다른 프로세스를 선택하는 것이 보통이다.
운영체제가 프로세스의 모든 상태를 저장했기 떄문에 프로세서의 제어를 달느 프로세스로 넘길 수 있다.
디스크로부터 페이지의 읽기가 끝나면 페이지 부재를 일으킨 프로세스의 상태를 복구하고 예외에서 복귀하는 명령어를 수행한다.
이 명령어는 프로그램 카운터를 복구할 뿐만 아니라, 프로세서를 커널 모드에서 사용자 모드로 바꾼다. 사용자 프로세스는 부재를 일으킨 명령어를 재수행하고 요구된 페이지에 접근하여 수행을 계속한다.
데이터 접근 시 발생하는 페이지 부재 예외 처리는 다음 세 가지 특성의 조합 때문에 구현하기가 힘들다.
1.
명령어 페이지 부재와는 달리 명령어 중간에 발생될 수 있다.
2.
예외를 처리하기 전에 그 명령어를 완결할 수 없다.
3.
예외 처리 이후에는 아무 일도 없었던 것처럼 그 명령어 수행을 재개해야 한다.
예외를 처리한 후 중단되었던 명령어 수행을 계속할 수 있게 다시 시작할 수 있는 명령어(restartable instruction)를 만드는 것은 MIPS 같은 구조에서는 비교적 쉽다.
각 명령어는 오직 하나의 데이터만을 쓸 수 있고 이 쓰기 명령어 사이클의 맨 마지막 단계에서 수행되기 때문에, 명령어 수행이 완료되는 것을 막고(즉 쓰기를 못하게 하고) 명령어를 처음부터 다시 수행시키기만 하면 된다.
MIPS를 좀 더 자세히 살펴보자. TLB 실패가 발생하면 MIPS 하드웨어는 BadVAddr이라고 불리는 특수 레지스터에 참조된 페이지 번호를 저장하고 예외를 발생시킨다.
예외는 소프트웨어로 실패를 처리하는 운영체제를 동작시킨다. 제어는 TLB 실패 핸들러(handler)의 위치인 주소 9000 000(hex)로 옮겨진다.
실패 처리된 페이지의 실제 주소를 알기 위해 TLB 실패 처리 루틴은 가상 주소의 페이지 번호와 활성화된 프로세스 페이지 테이블의 시작 주소를 나타내는 페이지 테이블 레지스터를 사용하여 페이지 테이블을 인덱스 한다.
이 인덱스 작업을 빠르게 하기 위해 MIPS 하드웨어는 필요한 모든 것을 Context 레지스터에 넣는다. 상위 12비트는 페이지 테이블의 시작 주소이고 다음 18비트는 실패가 발생한 페이지의 가상 주소이다.
각 페이지 테이블 엔트리의 크기는 한 워드이므로 마지막 2비트는 이다. 따라서 처음 두 명령어는 Context 레지스터 값을 커널 임시 레지스터 $k1에 복사하고 그 주소의 페이지 테이블 항목을 $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
C#
위에 보인 것과 같이 MIPS는 TLB 갱신을 위한 특수 시스템 명령어 집합을 가지고 있다. 명령어 tlbwr은 제어 레지스터 EntryLo로부터 제어 레지스터 Random에 의해 선택되는 TLB 엔트리에 복사한다.
Random은 무작위 교체를 수행하므로 기본적으로 규칙이 없는 카운터라고 보면 된다. TLB 실패는 12 클럭 사이클 정도가 소요된다.
TLB 실패 핸들러는 페이지 테이블 엔트리가 유효한지 검사하지 않는다. TLB 엔트리 실패에 따른 예외는 페이지 부재보다 훨씬 더 자주 발생하므로 운영체제는 페이지 테이블 엔트리를 검사히자 않고 TLB에 넣은 후 명령어를 다시 수행시킨다.
만약 엔트리가 유효하지 않으면 또 다른 예외가 발생하고 운영체제는 페이지 부재로 인삭하게 된다. 이와 같은 방법이 자주 발생하지 않는 페이지 부재에 대해서는 약간의 성능 저하를 초래하지만 자주 발생하는 TLB 실패를 빠르게 처리한다.
페이지 부재를 발생시킨 프로세스가 인터럽트를 당하게 되면 TLB 실패 핸들러와 다른 주소인 8000 0180(hex)로 제어를 옮기게 된다.
이것은 예외 처리를 하는 일반적인 주소이다. TLB 실패는 TLB 실패에 따른 손실을 줄이기 위해 특수한 시작 주소를 갖고 있다.
예외가 페이지 부재이기 때문에 운영체제는 많은 처리를 하여야 한다. 따라서 TLB 실패와는 다르게 활성화된 프로세스의 모든 상태를 저장한다. 이 상태는 모든 범용 레지스터, 부동소수점 레지스터, 페이지 테이블 주소 레지스터, EPC와 예외 원인 레지스터를 모두 포함한다.
예외 핸들러는 일반적으로 부동소수점 레지스터를 사용하지 않으므로 이 레지스터를 사용하는 일부 핸들러들만 부동소수점 레지스터를 저장하고 일반 엔트리 포인트는 이를 저장하지 않는다.
그림 5.34는 예외 핸들러의 MIPS 코드를 보여준다. 언제 예외를 활성화할지 비활성화 할지를 고려하면서 상태를 저장하고 또 복원하기 위해 어셈블리 코드를 사용했다. 그러나 특정 예외를 처리하기 위해서는 C 코드를 사용한다.
페이지 부재를 일으킨 가상 주소를 찾는 바법은 페이지 부재가 명령어 부재인지 데이터 부재인지에 따라 달라진다. 부재를 일으킨 명령어의 주소는 EPC에 있다. 만약 명령어 페이지 부재인 경우 EPC가 부재된 페이지의 가상 주소를 가지고 있다.
데이터 부재의 경우 부재인 가상 주소는 명령어(이 주소는 EPC에 있음)에서 베이스 레지스터와 변위 값을 구해서 계산할 수 있다.

요약

가상 메모리는 메인 메모리와 디스크 사이의 캐싱(caching)을 처리해 주는 메모리 계층의 한 계층을 나타내는 이름이다. 가상 메모리는 하나의 프로그램이 메인 메모리의 한게를 넘어 주소공간을 확장할 수 있도록 해준다.
더 중요한 것은 가상 메모리가 동시에 활성화된 다수의 프로세스들이 서로 보호된 상태에서 메인 메모리를 공유할 수 있도록 한다는 것이다.
메인 메모리와 디스크 사이의 메모리 계층구조를 관리하는 것은 페이지 부재의 높은 비용 때문에 쉽지 않다. 실패율을 줄이기 위해 여러 기법들이 사용된다.
1.
페이지들은 공간적 지역성을 이용하고 실패율을 줄이기 위해 크게 만들어진다.
2.
페이지 테이블로 구현된 가상 주소와 실제 주소의 사상을 완전 연관 방식으로 구현하여 가상 페이지를 메인 메모리 내 어느 곳에나 적재시킬 수 있게 한다.
3.
운영체제는 교체될 페이지를 선정하기 위해 LRU와 참조 비트 같은 기법을 사용한다.
디스크로 쓰기에는 시간이 많이 걸린다. 그래서 가상 메모리는 나중 쓰기 기법을 사용하며, 변화되지 않는 페이지를 디스크에 저장하는 것을 피하기 위해 페이지의 변화 여부(갱신 비트로)를 조사한다.
가상 메모리 시스템은 프로그램에 의해 사용되는 가상 주소를 메모리 접근에 사용되는 실제 주소공간으로 주소 변환한다. 이 주소 변환은 메인 메모리의 보호된 공유를 허락하고 메모리 할당을 단순화하는 것과 같은 추가적인 기능을 제공한다.
프로세스들이 서로 보호되는 것을 보장하기 위해서는 단지 운영체제만이 주소 변환을 변경할 수 있어야 한다. 이는 사용자 프로그램이 페이지 테이블을 변경하지 못하게 함으로써 구현될 수 있다.
프로세스들 사이의 통제된 페이지 공유는 운영체제와 사용자 프로그램이 페이지에 읽기와 쓰기 접근 권한을 갖고 있는지 여부를 말해 주는 페이지 테이블의 접근 비트의 도움으로 가능하다.
만약 프로세서가 모든 주소 변환을 위해 메모리 내에 있는 페이지 테이블에 접근해야 한다면 가상 메모리는 너무나 큰 부담을 갖게 된다. 대신 TLB가 페이지 테이블 변환을 위한 캐시 기능을 한다. 그래서 각 주소는 TLB 내의 변환을 가지고 가상 주소에서 실제 주소로 변환된다.
캐시, 가상 메모리, TLB 모두 공통되는 원칙과 정책에 의존한다. 다음 절은 이들 공통 프레임워크(framework)에 대해 설명한다.
가상 메모리가 작은 메모리를 큰 것처럼 활용할 수 있도록 개발되었음에도 불구하고 어떤 프로그램이 실제 메모리보다 더 많이 가상 메모리에 접근하게 되면 디스크와 메모리의 성능 차이 때문에 매우 느려지게 된다.
이와 같은 프로그램은 메모리와 디스크 사이에서 끊임없이 페이지를 교체하게 되는 스래싱(thrashing)이 발생하게 된다. 스래싱은 자주 발생하지는 않지만 일단 발생하게 되면 손실이 매우 크다.
이를 해결하는 가장 쉬운 방법은 더 큰 메모리를 갖는 컴퓨터를 이용하든지 아니면 컴퓨터에 메모리를 더 보완하는 것이다. 알고리즘과 자료구조를 다시 점검하여 지역성을 바꿈으로써 프로그램이 동시에 사용하는 페이지의 수를 줄이는 복잡한 방법도 있다.
이와 같은 페이지의 집합들을 비공식적으로 워킹셋(working set)이라고 부른다.
성능에 관련된 더 일반적인 문제는 TLB 실패이다. TLB는 한 번에 단지 32-64 페이지만 처리하기 떄문에 프로세서가 직접 접근할 수 있는 크기는 64 x 4 KiB = 0.25 MiB 밖에 되지 않기 때문에 프로그램이 높은 TLB 실패율을 겪는 경우가 흔하다.
예컨대 기수 정렬에서 TLB 실패는 골치 아픈 문제이다. 이 어려움을 경감시키기 위해 대부분의 컴퓨터 구조는 가변 페이지 크기를 지원한다.
예컨대 MIPS 하드웨어는 표준 4 KiB 페이지 외에 16 KiB, 64 KiB, 256 KiB, 1 MiB, 16 MiB, 64 MiB 그리고 256 MiB 페이지를 지원한다. 프로그램이 더 큰 페이지를 사용하면 TLB 실패 없이 직접 접근할 수 있는 메모리가 더 커진다.
실제적인 어려움은 프로그램이 이와 같이 더 큰 페이지 크기를 선택할 수 있도록 운영체제가 도와주는 문제이다. 결국 TLB 실패를 줄이는 더 좋은 해결책은 페이지의 워킹셋을 줄이기 위해 알고리즘과 자료구조를 다시 점검하는 것이다.
메모리 접근 빈도수가 성능과 TLB 실패율에 끼치는 영향의 중요성을 고려해서 여러 개의 워킹셋을 가지는 프로그램들은 이를 위하여 재설계되었다.

메모리 계층을 위한 공통 구조

이제까지 다른 종류의 메모리 계층이 상당 부분 공통점을 갖는다는 것을 알았다. 메모리 계츠으이 많은 부분들이 정량적으로는 다를지라도 어떻게 계층이 동작하는지를 결정하는 원칙과 특징들은 정성적으로 유사하다.
그림 5.35는 메모리 계층의 정량적 특징이 서로 다르다는 것을 보여준다. 이 절의 나머지 부분에서는 메모리 계층의 공통적인 동작 측면과 어떻게 이들이 동작을 결정하는지를 설명한다.
메모리 계층의 어떤 두 계층 간에도 적용될 수 있는 일련의 네 가지 질문으로 이런 원칙들을 조사해 보자.

질문 1: 블록을 어디에 위치시킬 수 있는가?

메모리 계층 구조의 상위 수준에 블록을 위치시키기 위해서는 직접 사상, 집합 연관, 완전 연관 등과 같은 방식을 사용할 수 있음을 살펴보았다. 위에서 언급한 바와 같이 이런 다양한 방법들은 집합의 수와 집합당 블록의 수의 변화에 따른 집합 연관 방식의 변형으로 생각할 수 있다.
Search
방식
집합의 수
집합 당 블록 수
직접 사상
Open
캐시의 블록 수
1
집합 사상
Open
캐시 내 블록 수 / 연관 정도
연관 정도 (일반적으로 2~16)
완전 연관
Open
1
캐시 내 블록의 수
연관 정도를 증가시키는 것의 장점은 일반적으로 실패율을 감소시킨다는 것이다. 실패율의 향상은 같은 위치에 대한 충돌을 줄임으로써 가능하다. 곧 이들 둘에 대해 자세히 살펴보도록 한다.
먼저 얼마나 큰 향상을 얻을 수 있는지 살펴보자. 그림 5.36은 직접 사상으로부터 8-way 집합 연관 방식까지 다양한 연관 정도에 따라 다양한 캐시 크기에서의 실패율을 보여주고 있다. 가장 큰 이득은 직접 사상을 2-way 집합 연관 방식으로 바꾸면서 가능하였고, 실패율을 20% 내지 30% 줄일 수 있다.
캐시가 커짐에 따라 연관 정도에 의한 상대적인 성능 향상은 줄어든다. 큰 캐시에서는 전체 실패율이 낮으므로 실패율을 향상시킬 수 있는 기회는 줄어들게 되고 연관에 의한 실패율의 절대적인 향상이 크게 위축된다. 이미 언급하였지만 연관 정도의 잠재적인 단점은 증가된 비용과 느려진 접근 시간이다.

질문 2: 블록을 어떻게 찾는가?

블록을 어떻게 찾느냐는 블록 배치 방식에 의존한다. 블록 배치 방식이 가능한 위치의 수를 말해 주기 때문이다. 다음과 같이 배치 방식을 요약할 수 있다.
Search
연관 정도
위치 파악 방법
비교 횟수
직접 사상
Open
인덱스
1
집합 연관
Open
집합 인덱스, 집합 내 모든 원소 비교
연관 정도
완전 연관
Open
모든 엔트리 검색
캐시의 크기
완전 연관
Open
별도의 참조 테이블 사용
0
모든 메모리 계층에서 직접 사상 방식, 집합 연관 방식, 완전 연관 방식 중 하나를 선택하는 것은 연관 정도의 구현 비용과 실패 비용에 의해 결정된다. 비용은 시간과 추가 하드웨어로 계산한다.
칩 상의 L2 캐시는 적중 시간이 크게 중요하지 않고 설계자가 빌딩 블록으로 표준 SRAM을 사용하지 않으므로 더 높은 연관 정도를 구현할 수 있게 해 준다.
완전 연관 방식은 작은 크기를 제외하고는 사용하지 않아야 한다. 작은 캐시에서는 비교기 비용이 크지 않으면서 절대적 실패율의 향상은 크기 때문에 써 볼 만하다.
가상 메모리 시스템에서는 메모리를 인덱스하기 위해 별도의 사상 테이블(페이지 테이블)을 사용한다. 인덱스 테이블을 사용하면 테이블을 저장할 공간이 필요할 뿐 아니라 추가 메모리 접근이 필요하다.
다음 사실 때문에 가상 메모리는 페이지 배치에 완전 연관 방식을 사용하고 별도의 인덱스 테이블을 갖는 완전 연관 방식을 사용한다.
1.
실패에 따르는 손실이 크기 때문에 완전 연관 방식이 이롭다.
2.
완전 연관 방식은 실패율을 줄이기 위해 설계된 정교한 교체 방식을 소프트웨어가 사용할 수 있도록 한다.
3.
완전한 사상 테이블이 있기 때문에 추가 하드웨어와 검색 과정 없이 쉽게 인덱스 된다.
그래서 가상 메모리 시스템은 항상 완전 연관 배치 방식을 사용한다.
집합 연관 배치는 캐시와 TLB에 종종 쓰이며, 접근은 인덱스와 선택된 작은 집합 내의 검색을 포함한다. 몇몇 시스템들은 간단함과 접근 시간의 이점 때문에 직접 사상 캐시를 사용한다.
접근 시간의 이점은 요청된 블록을 찾는데 비교가 필요 없기 때문에 생긴다. 이와 같은 설계에서의 선택은 캐시의 온칩 여부, 캐시를 구현하는데 사용한 기술, 그리고 프로세서 사이클 시간을 결정하는데 있어서 캐시 접근 시간의 핵심적인 역할 등과 같은 구현상의 많은 요소들에 의존한다.

질문 3: 캐시 실패 시 어느 블록을 교체시키는가?

연관 방식 캐시에서 실패 발생 시, 어느 블록을 교체시킬 것인가를 결정해야 한다. 완전 연관 캐시에서는 모든 블록이 교체의 후보가 된다. 만약 캐시가 집합 연관 방식이라면 선정된 집합 내의 블록 중에서 선정해야 한다. 물론 직접 사상 방식에서는 오직 하나의 후보만이 존재하므로 선정이 쉽다.
이미 집합 연관과 완전 연관 캐시에서 교체를 위한 두 가지 전략을 살펴보았다.
임의 교체: 후보 블록이 경우에 따라 하드웨어의 지원을 받아서 임의로 선정된다. 예컨대 MIPS는 TLB 실패 시 임의 교체 방식을 사용한다.
LRU 교체: 가장 오랜 시간 동안 사요오디지 않은 블록을 선정한다.
실제로 약간의 연관 정도(일반적으로 2~4) 이상을 갖는 계층구조에서 LRU를 구현하는 것은 각 블록의 사용 정보를 추적하는 비용이 많이 들기 때문에 어렵다. 심지어 4-way 집합 연관 방식에서도 LRU는 가끔 근사 방식을 이용한다
예컨대 블록의 쌍 중 어느 것이 LRU인지 추적하고 (1비트가 요구됨) 그 이후에 각 쌍 중 어느 블록이 LRU인지를 검사한다 (1비트가 요구됨)
큰 연관 방식에서는 LRU의 근사 방식을 이용하거나 임의 교체 방식을 이용한다. 캐시에서는 교체가 하드웨어로 이루어지므로 구현이 쉬워야 한다.
임의 교체 방식은 하드웨어로 간단히 구현될 수 있고, 2-way 집합 연관 캐시에서 LRU 교체보다 실패율이 1.1배 정도 높다. 캐시의 크기가 점점 커지면 이 두 교체 방식의 실패율은 줄어들고 두 값의 절대적인 차이도 작아진다.
실제로 임의 교체 방식은 하드웨어로 쉽게 구현할 수 있는 단순한 LRU 근사 방식보다도 때로는 더 좋다.
가상 메모리에서는 실패 비용이 매우 커서 실패율의 작은 감소조차도 중요하기 때문에 항상 LRU 근사 방식이 사용된다.
운영체제가 가장 오래 전에 사용된 페이지를 쉽게 추적할 수 있도록 하기 위해, 참조 비트 또는 이와 유사한 기능이 종종 제공된다.
실패는 비용이 많이 들고 상대적으로 드물게 발생하기 때문에, 주로 소프트웨어를 사용하여 이 정보를 근사화 하는 것이 가능하다.

질문 4: 쓰기 시에 어떤 일이 발생하는가?