1. Computer System Overview (2)

Memory Hierarchy

---

컴퓨터 안에 저장할 수 있는 공간의 계층구조

컴퓨터에서 사용되는 저장공간은 계층 구조를 이루고 있다.

위로 올라갈수록 속도는 빠르지만 용량은 줄어들고 비트당 가격은 비싸진다.

=> 접근 횟수가 많은 데이터를 빠른 저장 장치에 저장하는 것이 좋다.

 

이러한 계층 구조가 어떻게 효과를 발휘할까?

CPU가 일을 할 때 접근하는 데이터를 보면 모든 데이터를 균일하게 접근하지 않고 또는 모든 명령어를 균일하게 접근하지 않고 특정 데이터나 특정 명령어들이 더 빈번하게 접근이 되는 것을 확인할 수 있다.

이걸 참조 지역성(Locality of reference) 이라고 한다.

 

예를 들어, Loop문 안에 있는 명령어들은 수행이 반복적으로 이루어진다. 그런데 Loop가 아닌 명령어는 한 번 수행되고 지나간다.

즉, Instruction과 Data는 자주 접근되는 부분 과 자주 접근되지 않는 부분 이 나뉘더라.

자주 접근되는 애들을 빠른 메모리에 올리고 덜 자주 접근되는 애들을 느린 메모리에 올리면 시스템의 속도를 빠르게 만들 수 있다.

어떤 시점에 자주 접근하는 데이터가 반드시 존재하더라.

시점마다 자주 접근되는 데이터가 달라질 수는 있으나 아무튼 반드시 존재한다.

=> 이 자주 접근되는 데이터를 찾아내는 알고리즘은 LRU 알고리즘이고, 이걸 빠르게 처리할 수 있도록 하는 건 하드웨어의 도움을 받아야 하는데, 걔가 바로 캐시다.

 

H/W Speed-up Trends

• 위로 갈수록 큰 간격이기 때문에 A > B 이다.
• 즉, CPU 입장에서 DRAM의 속도가 느린 정도가 DRAM의 입장에서 하드 디스크가 느린 정도보다 더 크게 느껴진다.
• => CPU 입장에서 DRAM은 매우 매우 느린 존재.
• CPU와 DRAM 사이의 속도차이를 줄이기 위해서 Cache가 만들어졌다.
• CPU와 메모리 사이의 속도차이가 A, 메모리와 하드디스크 차이가 B
  • 언뜻 보기엔 B가 간격이 더 커보이지만 y축을 보면 실제로 A가 훨씬 더 큰 간격임을 알 수 있다.
  • 즉, CPU입장에서 메모리는 엄청 엄청 느린 존재다. I/O가 빈번하게 발생하는 경우는 하드디스크가 병목이 되는 것이 맞는데, I/O가 빈번하게 발생하지 않을 경우에는 CPU와 DRAM이 일을 다 하는 것이기 때문에 DRAM이 병목이 된다.
  • 전체 시스템의 병목은 하드 디스크가 맞지만, 상대적으로 CPU의 입장에서 답답한 건 메인 메모리임.
  • 그리고 I/O가 자주 발생하지 않는 애플리케이션이 꽤나 있다.

 

Cache

---

캐시 메모리는 메모리의 속도 때문에 CPU가 수행하는 명령의 속도가 제한될 수 밖에 없다는 문제를 해결하기 위해서 사용되는 CPU와 메모리 사이에 위치하는 빠른 메모리.

• 캐시는 메인 메모리에 사용되는 DRAM보다 빠른 SRAM을 사용한다.

CPU는 메모리에서 Instruction이나 데이터를 가져올 때 Word 단위로 가져온다. 명령어 하나 또는 데이터 하나 이런 식으로.

그러나 캐시 메모리와 메인 메모리 사이에서 데이터가 왔다갔다할 때는 Block 단위로 왔다갔다 한다.

 

왜?

현재 CPU가 1번 Instruction을 접근하고 있다면, 다음에는 2번에 접근하지 않을까? 라는 생각이 가능하다.( Instruction은 순차적으로 시행되니까 )

그래서 매번 메모리에서 가져오면 힘드니까 그냥 통째로 가져온다.

 

캐시 메모리를 사용하는 이유

• 참조 지역성에 따라 메인 메모리의 데이터 중에 자주 접근되는 데이터들을 캐시에 저장해둔다.
• 캐시는 용량이 작아서 메모리의 모든 데이터를 담고 있을 수는 없다. 그래서 메인 메모리의 데이터 중에서 자주 접근되는 데이터들만 캐시에 저장한다.
• 그럼 자주 접근되는 데이터들은 메인 메모리가 아닌 캐시에서 가져오게 되는데 그럼 메인 메모리에서 가져올 때 보다 훨씬 빠르게 가져올 수 있다.

 

Cache Design

---

Cache의 사이즈는 어느 정도로 하는 것이 좋을까?

자주 접근되는 데이터가 모두 캐시에 올라오면 가장 좋을텐데, 자주 접근되는 데이터나 Instruction의 크기가 얼마나 될지 모르니 캐시의 크기를 어떻게 해야할지 정확히 알 수가 없다.

그런데 사람들이 테스트해 본 결과 자주 접근되는 데이터의 크기가 그렇게 크지 않다는 것을 알게 되었다.

즉, 캐시의 크기가 그렇게 크지 않아도 충분히 효과를 발휘한다는 것을 경험적으로 알게 되었음.

=> 애플리케이션의 크기가 커짐에 따라 Locality의 사이즈도 커지고 있는 상황이다. 그래서 SRAM을 점점 늘려가고 있는 추세다.

 

캐시와 메모리 사이에는 Block 단위로 데이터를 주고 받는다고 했다.

왜 주변의 메모리까지 한 번에 Block 단위로 데이터를 읽어들일까?

앞서 말했듯이 참조 지역성에 의해 다음 번 메모리에 접근할 때에는 현재 CPU가 접근하고 있는 데이터 주변에 있는 데이터에 접근할 가능성이 높다.
그렇기 때문에 주변에 있는 데이터까지 통째로 읽어온다.

=> 한 번 가져올 때 많이 가져와서 메모리에 접근하는 빈도를 줄이자!

 

그렇다면 Block의 사이즈는 어느 정도로 하는 것이 좋을까?

Block의 사이즈가 커질수록 캐시 미스 빈도가 줄어드는 것은 맞지만 과도하게 커지면 자주 접근되지 않는 데이터까지 캐시에 읽어들일 가능성이 높아진다.

현재 접근하고 있는 데이터에서 멀어질 수록 이후에 접근될 가능성이 떨어지니까.

그러면 인기없는 데이터가 공간을 차지하게 되어 캐시 메모리를 낭비하게 될 수 있다.

따라서 "적절한" 사이즈로 만들어야 한다.

=> 적절한 사이즈를 이론적으로 구할 순 없고 경험적으로 구해져서 쓰이고 있음.

 

Replacement Algorithm

---

만약 캐시가 가득찬 상태에서 캐시 미스가 발생해서 메모리에서 데이터를 읽어와야 한다면, 기존에 캐시에 있던 Block들 중에 한 Block을 밀어내고 새로운 Block을 읽어와야 한다.

• 이때는 CPU가 다음에 접근할 가능성이 제일 낮은 Block을 밀어내야 하는데, 어떤 Block이 접근될 가능성이 낮을 지 정확히는 알 수 없음.
• 과거 데이터를 이용해서 그 Block을 결정하는 알고리즘이 여러 가지가 있는데 그 중 LRU 알고리즘 이 유명하다.

 

LRU(Least Recently Used) Algorithm?

• 최근에 가장 덜 접근된 데이터 블록을 캐시에서 밀어낸다.
• 최근에 자주 접근된 데이터는 또다시 사용될 가능성이 높을 것이라는 전제를 깔고 사용하는 알고리즘.

 

Write Policy

---

쓰기 연산이 발생했을 때, 캐시와 메모리에 어느 타이밍에 값을 쓸 것인가?

메모리에 값을 쓰는 operation이 발생했을 때, 메모리에 써야 할 데이터가 캐시에도 올라와 있는 데이터라면, 캐시에 있는 값은 당연히 변경해야 하고 메모리에 있는 값도 변경해 주어야 일관성이 유지된다.

 

이때 값을 업데이트 하는 방법에는 두 가지 방법이 존재한다.

1. 매번 캐시에 값을 쓸 때마다, 메모리에도 값을 써준다. (동시에 업데이트)
   => 이러면 write에 대해서는 캐시를 쓰는 효과가 없지 않을까?
2. 캐시에 있는 값만 바꿨다가, 데이터가 캐시에서 밀려날 때 실제 메모리에 가서 값을 바꿔준다.
   => 바뀐 적이 있다는 것은 dirty bit에 기록해둔다.

2번의 방법을 사용할 경우 메모리 접근이 줄어든다는 장점이 있지만, 캐시에 있는 데이터와 메모리에 있는 데이터가 일치하지 않아 메모리의 데이터는 과거 데이터(불필요한 데이터)가 되어버린다는 부작용이 있다.

그리고 2번의 방법을 사용할 경우 Cache Coherence Problem 이라는 또 다른 문제가 발생한다.

2번의 방법을 사용하기 위해서는 이러한 문제를 해결할 매커니즘을 제공해야 하는데, 이미 제시되어 있다.

 

Cache Coherence Problem?

2번의 방법을 사용한다고 했을 때, 만약 CPU 코어가 여러 개인 경우 코어마다 cache를 갖기 때문에 cache 메모리도 여러 개가 존재하게 된다.
이때 캐시에 있는 값만 변경하게 되면 각 코어마다 캐시에 다른 값이 저장되는 상황이 발생할 수 있다.
같은 메모리에 대한 캐시 값이지만 값을 모두 다르게 가지고 있게 되는 셈이다
이러면 무결성이 깨진다.
그렇기 때문에 2번의 방식을 사용하기 위해서는 이 문제를 해결하는 매커니즘을 반드시 제공해야 한다.

그래서 보통 어떻게 하냐면 어떤 데이터가 이쪽 캐시에도 올라와있고 저쪽 캐시에도 올라와 있다면 이쪽 캐시에서 업데이트가 발생하면 다른 쪽 캐시에다가 Cache Invalidation Message를 보내서 너가 가지고 있는 캐시값은 잘못된 값이야 라고 알려준다.
그리고 해당 값을 읽으려 하면 메모리나 값을 변경한 코어의 캐시에서 최신 값을 다시 읽어오도록 하는 방법을 사용한다.

=> 멀티 코어 시스템에서 중요한 문제임

Q. 여기서 나는 한가지 의문이 들었다. 교재와 교수님의 설명을 들으면 2번의 방식 즉, Write-Back 방식을 사용했을 때만 Cache coherence problem이 발생하는 것처럼 들렸다. 그런데 생각해보면 멀티 프로세서의 경우 각 프로세서마다 캐시를 갖고 있기 때문에 Write-through 정책을 사용한다고 하더라도 같은 데이터에 대한 캐시값을 각 프로세서마다 가지고 있다면 결국은 메모리의 값이 즉시 수정된다고 하더라도 잘못된 캐시값을 가지고 있을 것이다.

A. 그래서 교수님께 질문을 드렸더니, 사실은 Write back, Write through 방식 모두 Cache coherence problem을 처리해야 한다고 하셨다. 하지만 요즘은 대부분 Write back 방식을 사용하고 Cache coherence protocol을 설계할 때 Write back 방식에 대한 구현이 훨씬 복잡하기 때문에 Write back 상황을 염두에 두고 말을 하는 경우가 많다고 하셨다.

 

Disk Cache

---

디스크 캐시는 별도의 SRAM을 사용하는 것이 아닌 DRAM을 그대로 사용한다. 메모리와 하드 디스크 사이의 속도 차이를 극복하기 위해 사용.

• 메모리의 특정 영역을 따로 떼서 그 부분은 디스크의 일부 데이터를 저장하는 데에 사용한다.
• 향후에 디스크에 접근하게 될 때 그 데이터가 디스크 캐시에 올라와 있으면, 디스크에 가지 않고 디스크 캐시에서 읽어온 다음 I/O를 수행한 것처럼 처리한다.
• 디스크 I/O가 발생했을 때 메모리에 불러온 데이터를 사용자 프로그램에 넘겨주고 나서, 바로 삭제하는 것이 아니라 Disk Cache에 남겨둔다.

 

Computer System Organization

---

컴퓨터 시스템은 어떻게 구성이 되어 있을까?

컴퓨터 시스템은 CPU와 메모리, 버스 그리고 (I/O를 발생시키는) 나머지 주변 장치들로 이루어져 있다.

이 모든 장치들은 시스템 버스로 연결되어 있고, I/O는 CPU와 장치들 사이에 직접 일어나지 않고, CPU와 장치들 사이에 메모리를 매개로 하여 일어난다.

그렇기 때문에 메모리 사이클을 서로 사용하려고 경쟁이 발생한다.

CPU와 주변의 장치들은 별도로(독립적으로) 돌아간다. CPU가 일을 하니까 주변 장치들은 일을 못 하는 것이 아니라, CPU가 바쁠 때 주변의 장치들도 같이 바쁠 수 있다.

=> 메모리 접근 역시 독립적으로 발생하게 되고 따라서 메모리 사이클에 대해서 경쟁이 발생하게 된다.

 

I/O 디바이스들을 실제로 구동하는 놈은 누구일까?

각각의 I/O 장치들마다 Controller가 반드시 존재한다.

Controller가 I/O 장치를 직접적으로 제어를 하게 되고, 이 Controller가 메모리에 접근해서 데이터를 읽어가거나 쓴다.

각각의 Device controller는 안에 local buffer를 가지고 있다.

예를 들어, 하드디스크라고 하면 하드디스크 안에 controller라는 칩이 들어있고 그 안에 buffer가 있다.

실제로 I/O가 뭐냐하면 메모리에 있는 데이터가 controller의 buffer로 나가는 것을 Output이라고 한다. 반대로 controller의 buffer에 있는 데이터를 메모리로 가져오는 것을 Input이라고 한다.

실제로 "메모리에 있는 몇 번지에 있는 데이터를 저 I/O 장치에 써라"라는 I/O 명령어를 CPU가 수행하게 된다면, CPU가 메모리에 있는 데이터를 I/O 장치의 버퍼로 Output 시켜주고 해당 장치의 controller에게 방금 보내준 데이터를 장치 안에 쓰라고 명령을 내림. 그러면 컨트롤러가 실제 장치에 값을 쓰게 된다.

 

하드 디스크를 예시로 그 과정을 자세하게 살펴보자.

하드디스크에게 Read 명령어가 발생하면 Controller는 마그네틱 디스크에서 읽은 데이터를 자신의 버퍼에 올려두고 CPU에게 Interrupt를 보낸다.

그럼 CPU는 Interrupt를 받아서 핸들러를 수행하게 되고 핸들러를 통해 장치의 버퍼에서 값을 가져가서 메모리에 저장한다.

즉, 컨트롤러는 절대로 메인 메모리에 직접 값을 쓰지 않는다. 그 대신 자신의 버퍼에 값을 올려두고 I/O가 끝났다는 Interrupt를 보낸다.

그러면 그 버퍼에 있는 데이터를 실제로 메모리에 가져오는 역할은 Interrupt handler가 하게 된다.

 

왜 이렇게 할까? 하드디스크가 직접 메모리에 값을 쓰면 되지 않나?? 그리고 CPU가 가져가면 되지 않나?

CPU 입장에서는 하드디스크가 무슨 짓을 저지를지 믿지 못함. 하드디스크는 메인 메모리가 어떻게 생긴지를 모르기 때문에 잘못된 위치에 값을 써버리면 시스템이 망가지게 된다.

그래서 주변 장치들은 메모리에 대한 접근 권한을 가지지 못한다. 오직 CPU만이 접근 권한을 가짐. 안전을 위해서!

 

Programmed I/O

CPU가 I/O module에게 값을 읽어달라고 Issue를 하면, I/O 모듈은 장치에서 값을 읽기 시작한다.

그리고 CPU는 계속해서 값을 다 읽었는지 확인하는 과정을 거친다. I/O module이 다 읽었다는 status를 보내줄 때까지 CPU는 계속 다 읽었냐고 물어봐야 한다.

값을 다 읽었는지 확인하기 위해 CPU를 쓰면서 무한루프를 도는 비효율적인 상황이 발생한다.

또한 CPU는 한 번에 한 워드씩 읽어오기 때문에 만약 1000워드짜리 데이터라고 하면 전체 과정을 1000번 반복해야 한다.

굉장히 비효율적으로 보이지만 왜 이렇게 밖에 할 수가 없냐면, I/O의 최종 종착지는 메모리에 데이터를 올리는 것인데 아까 I/O 장치가 직접 적으로 메모리에 값을 쓰지 못하게 제어를 한다고 했다.

CPU는 I/O 단위가 워드 단위이고 CPU가 직접 I/O 장치 컨트롤러의 버퍼에서 읽어서 메모리에 값을 써야 하기 때문에 어쩔 수 없이 루프를 돌아서 한 워드씩 읽어 I/O를 끝낼 수 밖에 없다.

 

Interrupt를 사용하면 I/O 장치한테 다 읽었냐고 물어보는 동작을 하지 않아도 될 것 같다!

 

Interrupt-Driven I/O

Interrupt-Driven I/O는 CPU가 I/O 장치에게 Read를 하라고 Issue만 해둔 다음 I/O 장치가 다 읽었다고 Interrupt를 보낼 때까지 다른 일을 하면서 기다린다.

=> 아까처럼 다 읽었냐고 물어보는 무한 루프는 돌지 않아도 되기 때문에 훨씬 효율적이다.

 

근데 여전히 바깥쪽 루프는 해결 못 했음

=> CPU가 워드 단위로 읽기 때문에 근본적으로 해결 불가능함.

=> 이걸 해결하려면 I/O 디바이스가 직접 메모리에 값을 쓸 수 있도록 해줘야 한다. 디바이스가 데이터를 메모리에 모두 써둔 다음에 Interrupt를 보내서 다 썼음을 알리면 되는데, 이건 도저히 허락할 수가 없음. I/O 장치는 못 믿기 때문에.

 

이 동작을 꼭 CPU가 해야할까?

일단 I/O 장치에게 메모리 접근을 허용하는 건 절대 불가능. (못 믿기 때문에)

그래서 생각한 방법이 믿을 수 있는 존재를 하나 만들어서 지금 CPU가 하는 일을 대신하게 하면 되지 않을까? 라는 방법이다.

그 존재가 바로 DMA(Direct Memory Access)

=> 이름만 봐도 알 수 있듯이 메모리에 직접 접근할 수 있는 권한을 가진 존재다.

 

DMA

---

CPU를 대신해서 메모리에 값을 써줄 믿을 만한 존재가 바로 DMA

 

I/O를 위해서 메모리에 접근할 권한을 부여할 완전히 독립적인 장치가 DMA Controller다.

DMA가 있으면 CPU 입장에서 I/O가 매우 간단해진다.

DMA controller는 CPU가 해오던 word 단위로 메모리에서 데이터를 읽고 쓰던 일을 대신해주고 일이 다 끝나면 Interrupt를 통해 CPU에게 일이 끝났음을 알려줌.

=> DMA라는 칩을 메인 보드에 박아놓고 DMA를 통해서 모든 I/O를 처리.

=> 그 동안 CPU는 다른 일을 할 수 있으므로 일의 동작 효율이 높아진다.

 

Computer Startup

---

전원을 켰을 때 컴퓨터가 부팅될 때까지의 과정

운영체제를 깔기 전에 컴퓨터를 키면 어떤 일이 벌어질까?

운영체제가 없더라도 처음에 하드웨어를 체크하는 기본적인 과정은 똑같이 일어난다.

DRAM의 사이즈는 얼마인지,, CPU는 뭔지,, 등등 체크해서 화면에 뿌려준다.

=> 그럼 이 과정은 누가 할까?? Bootstrap program이라는 프로그램이 한다.

 

전원이 들어가면 ROM에 저장된 bootstrap program이 메모리에 로드가 되고 그 프로그램을 CPU가 수행을 하게 됨.

(시스템의 하드웨어 장치를 initialize)
=> 이건 운영체제와 상관없이 일어남

하드웨어를 체크하는 과정이 끝나면 OS를 메모리로 로드한다.

OS 코드가 메모리로 올라와서 OS 코드의 제일 첫번째 코드(instruction)를 가리키는 PC가 세팅이 되면 그때부터 이제 OS가 구동이 되기 시작한다.

OS가 구동이 되면 부팅이 완료가 된 것이다.