Cache

캐시 메모리 및 메모리 계층성에 대해 설명해 주세요.

캐시 메모리

캐시 메모리는 CPU의 처리 속도와 주기억장치의 접근 속도 차이를 줄이기 위해 사용한다. 데이터 지역성을 활용하여 메인 메모리에 있는 데이터를 캐시 메모리에 불러와 두고, 프로세서가 필요한 데이터를 캐시 메모리에서 먼저 찾도록 하여 시스템 성능을 향상시킨다.

데이터 요청이 들어오면, 먼저 캐시에서 데이터를 탐색한다. 캐시가 없거나 오래된 경우 원본 데이터가 저장된 곳에서 데이터를 조회하게 된다. 이후 캐시에도 데이터를 복사, 갱신하게 되며 오래된 데이터는 삭제한다.

캐시 메모리의 특징은 다음과 같다.

• 캐시는 주기억장치와 CPU 사이에 위치하며, 자주 사용하는 프로그램과 데이터를 기억한다.
• 캐시 메모리는 메모리 계층 구조에서 가장 빠른 소자이며, 처리 속도가 거의 CPU의 속도와 비슷할 정도의 속도를 가지고 있다.
• 캐시 메모리를 사용하면 주기억장치를 접근하는 횟수가 줄어들어 컴퓨터의 처리 속도가 빨라진다.
• 캐시 주소 표는 검색 시간을 단축시키기 위해 주로 연관 기억 장치를 사용한다.
• 캐시의 크기는 보통 수십 KByte 에서 수백 KByte이다.

메모리 계층성

메모리 계층성

• 메모리를 필요에 따라 여러가지 종류로 나누어 두는 것이다.
• 컴퓨터의 설계에 있어 각각의 특징이 있는 서로 다른 여러 종류의 저장 장치를 함께 사용하여 최적의 효율을 낼 수 있게 하는 것이다.
• 상황에 맞게 여러 저장 장치를 각각 사용할 수 있도록 하여 저렴하고 성능 좋은 컴퓨터를 구현하려는 설계이다.

레지스터

• CPU가 요청을 처리하는 데 필요한 데이터를 일시적으로 저장하는 기억 장치이다.
• 컴퓨터에서 4대 주요 기능인 기억, 해석, 연산, 제어에 사용되는 프로세서에 위치한 고속 메모리이다.
• 프로세스가 바로 사용할 수 있는 소량의 데이터, 처리 중인 중간 결과를 담고 있는 영역이다.
• CPU 내부 레지스터 종류

  종류	설명
  프로그램 계수기(PC, Program Counter)	다음에 실행할 명령어(instruction)의 주소를 가지고 있는 레지스터
  누산기(AC, ACcumulator)	연산 결과 데이터를 일시적으로 저장하는 레지스터
  명령어 레지스터(IR, Instruction Register)	현재 수행 중인 명령어를 가지고 있는 레지스터
  상태 레지스터(SR, Status Register)	현재 CPU의 상태를 가지고 있는 레지스터
  메모리 주소 레지스터(MAR, Memory Address Register)	메모리로부터 읽어 오거나 메모리에 쓰기 위한 주소를 가지고 있는 레지스터
  메모리 버퍼 레지스터(MBR, Memory Buffer Register)	메모리로부터 읽어온 데이터 또는 메모리에 써야 할 데이터를 가지고 있는 레지스터
  입출력 주소 레지스터(I/O AR, I/O Address Register)	입출력 장치에 따른 입출력 모듈의 주소를 가지고 있는 레지스터
  입출력 버퍼 레지스터(I/O BR, I/O Buffer Register)	입출력 모듈과 프로세서 간의 데이터 교환을 위해 사용되는 레지스터

캐시

• 데이터의 값을 미리 복사해 놓는 임시 장소이다.
• 시스템의 효율성을 위해 사용한다.
• 속도가 빠른 장치와 속도가 느린 장치 사이에서 속도차에 따른 병목 현상을 완화하기 위한 범용 메모리이다.

주기억장치

• 컴퓨터에서 수치, 명령, 자료 등을 기억하는 컴퓨터 하드웨어 장치이다.
• RAM (Radom Access Memory): 휘발성 기억 장치
  • 컴퓨터가 빠른 액세스를 하기 위해 데이털르 단기간 저장하는 구성 요소이다.
  • 사용자가 요청하는 프로그램이나 문서를 스토리지 디스크에서 메모리로 로드하여 각각의 정보에 액세스한다.
  • 전원이 유지되는 동안 CPU의 연산 및 동작에 필요한 모든 내용이 저장된다.
  • 전원 종료 시 기억된 내용이 삭제된다.
• ROM (Read Only Memory): 고정 기억 장치
  • 컴퓨터에 지시사항을 영구히 저장하는 비휘발성 메모리이다.
  • 전원이 종료되어도 기억된 내용이 유지된다.
  • 변경 가능성이 희박한 기능 및 부품에 사용된다.

보조기억장치

• 비휘발성이며 순차 접근이 가능한 컴퓨터의 보조 기억 장치이다.
• 비휘발성 데이터 저장소 가운데 가장 대중적이며 용량 대비 가격이 가장 저렴하다.

캐시 메모리는 어디에 위치해 있나요?

L1, L2 캐시 메모리는 CPU 내부에 위치하며, 해당 캐시가 소속된 코어의 고유 메모리로 사용된다. L3 캐시는 CPU 외부에 위치한다.

L1, L2 캐시에 대해 설명해 주세요.

시스템에 장착된 캐시의 용량과 성능이 점점 증가하면서 캐시의 캐시로 사용되는 메모리가 추가되었는데, 이것을 적용된 순서대로 L(Level) 1, 2, 3라고 호칭한다.

• L1: 처리된 데이터를 저장하고 수행해야 하는 작업에 대한 정보를 저장한다.
• L2: CPU가 곧 사용할 명령과 데이터를 저장한다.
• L3: 가장 크면서도 가장 느리다. L3 캐시 메모리가 마지막 레벨의 캐시 메모리일 경우 L3 캐시 메모리를 LLC라고 부르기도 한다.

캐시에 올라오는 데이터는 어떻게 관리되나요?

• Key, Value 형태로 저장된다.
• 주소가 Key로 주어지면 해당 공간에 즉시 접근이 가능하다.
• 캐시를 저장할 때 캐시가 만료되는 시간을 명시한다.
  • 데이터베이스의 원본 데이트 변경 시 캐시도 변경되어야 하기 때문이다.

캐시간의 동기화는 어떻게 이루어지나요?

소프트웨어적 해결

• 코드 분석을 통해 안정적이게 공유 변수를 사용할 수 있도록 주기를 설정해 준다.
• 아예 공유 변수 데이터를 캐시에 저장하지 않도록 한다.
• 캐시 이용률 측면에서 다소 비효율적일 수 있다.

하드웨어적 해결

• 스누피 프로토콜
  • 각 CPU 캐시는 공유되는 캐시 데이터를 파악하고 있다.
  • 공유되는 캐시 데이터가 갱신되었을 때 이를 기반으로 갱신되지 않은 나머지 데이터는 다 무효화시키는 것이다.
• 디렉토리 프로토콜
  • 주기억장치의 중앙 제어기가 캐시의 일관성을 관리한다.
  • 주기억장치의 중앙 제어기는 각각 CPU 캐시데이터를 가지고 모든 지역 캐시 제어기의 동작을 제어하고 보고받아 캐시의 일관성을 관리한다.

캐시 메모리의 Mapping 방식에 대해 설명해 주세요.

Direct Mapping

• 메인 메모리를 일정한 크기의 블록으로 나눠서 각각의 블록을 캐시의 정해진 위치에 매핑한다.

Full Associative Mapping

• 캐시 메모리의 빈 공간에 마음대로 저장한다.
• 복잡하고 비용이 비싸며, 데이터를 찾기에 까다롭다.

Set Associative Mapping

• 둘의 장점을 결합한 방식으로 미리 정해 둔 특정 행에 있는 빈 공간에 마음대로 저장하는 방식이다.
• Direct에 비해 검색이 느리지만 저장이 빠르다.
• Full에 비해 저장이 느리지만 검색이 빠르다.

캐시의 지역성에 대해 설명해 주세요.

캐시의 지역성

지역성이란 기억 장치 내의 정보를 균일하게 접근하는 것이 아니라 어느 한순간에 특정 부분을 집중적으로 참조하는 특성이다. 데이터의 접근이 시간적, 공간적으로 가깝게 일어나는 것을 의미하며 캐시가 효율적으로 동작하려면 캐시의 적중률을 극대화시켜야 한다.

• 적중(Hit) = CPU가 주기억장치 메모리에 접근하기 전에 캐시 메모리에서 원하는 데이터가 존재하는 경우
  • 적중률 (Hit Ratio) = 캐시 메모리 적중 횟수 / 전체 메모리 참조 횟수 * 100

시간적 지역성

특정 데이터가 한 번 접근되었을 경우, 가까운 미래에 또 한 번 데이터에 접근할 가능성이 높은 것이다.

공간적 지역성

특정 데이터와 가까운 주소가 순서대로 접근되었을 경우를 말한다.

캐시의 지역성을 기반으로, 이차원 배열을 가로/세로로 탐색했을 때의 성능 차이에 대해 설명해 주세요.

이차원 배열을 가로로 조회했을 경우 공간 지역성의 이점을 활용할 수 있기 때문에 세로로 탐색하는 것보다 성능이 좋다.

캐시의 공간 지역성은 어떻게 구현될 수 있을까요? (힌트: 캐시는 어떤 단위로 저장되고 관리될까요?)

• 캐시는 데이터를 캐시 블록 단위로 저장한다.
• CPU가 특정 메모리 주소를 참조하면, 해당 주소뿐만 아니라 근처의 데이터도 한 번에 가져와서 저장한다.
• 예를 들어 CPU가 주소 0x1000을 접근하면 0x1000 ~ 0x10FF까지 한 번에 캐시에 로드하여 공간 지역성을 구현할 수 있다.
• 인접한 데이터가 함께 캐시에 적재되기 때문에, 연속한 데이터 접근 시 캐시 적중률이 높아진다.

Memory

메모리의 연속할당 방식 세 가지를 설명해주세요. (first-fit, best-fit, worst-fit)

First-fit

• 첫 번째로 적당한 빈 공간을 찾아서 할당하는 방식이다.
• 메모리 내에서 처음 발견된 충분히 큰 빈 공간에 할당을 시도한다.
• 빠르게 할당될 수 있지만, 할당된 공간이 커서 내부 단편화가 일어날 수 있다.

Best-fit

• 가장 작은 빈 공간을 찾아서 할당하는 방식이다.
• 들어갔을 경우 남은 공간이 가장 작은 곳에 할당된다. 따라서 내부 단편화가 적게 일어난다.
• 공간을 찾는 시간이 오래 걸린다.

Worst-fit

• 가장 큰 빈 공간을 찾아서 가는 것이다.
• 나중에 더 큰 크기의 요청이 들어오면 할당할 수 있는 여유분을 남기는 것이기 때문에, 외부 단편화를 줄인다.
• 낭비가 심하고 공간 검색 시간이 오래 걸린다.

worst-fit 은 언제 사용할 수 있을까요?

외부 단편화가 심각하게 발생할 수 있는 시스템에서 사용하면 좋다.

성능이 가장 좋은 알고리즘은 무엇일까요?

성능 측정 측도에 따라 다르다.

• First-fit: 빠른 할당
• Best-fit: 내부 단편화 최소화
• Worst-fir: 외부 단편화 최소화

Virtual Memory

가상 메모리란 무엇인가요?

가상메모리는 운영체제에서 제공하는 기술로, 프로세스가 실제 물리적 메모리보다 더 많은 메모리를 사용할 수 있도록 하는 방법이다. 즉 프로세스는 자신의 메모리 공간을 연속적인 주소 공간처럼 보이게 하여, 실제 메모리보다 더 많은 메모리를 사용할 수 있게 된다. 가상 메모리는 가상 주소와 물리 주소를 매핑하는 방식으로 동작하며, 메모리의 일부는 디스크에 저장되고 필요할 때만 RAM에 로드된다.

가상 메모리가 가능한 이유가 무엇일까요?

가상 메모리가 가능한 이유는 메모리 관리 유닛 때문이다. MMU는 가상 주소를 물리 주소로 변환하는 하드웨어 장치이다. 이를 통해 각 프로세스는 자신만의 독립적인 주소 공간을 가지게 되어 다른 프로세스의 메모리와 격리될 수 있다. 또한 운영체제는 페이지 테이블을 사용하여 가상 메모리와 물리 메모리 사이의 매핑을 관리한다.

• 페이지 테이블: 가상 메모리 주소를 물리 메모리 주소로 매핑하는 데이터 구조이다.

Page Fault가 발생했을 때, 어떻게 처리하는지 설명해 주세요.

Page Fault는 프로그램이 접근하려는 메모리 페이지가 주기억장치에 존재하지 않을 때 발생한다. Page Fault가 발생하면 다음과 같은 과정으로 처리된다.

1. 운영체제 감지: 프로세스가 접근한 가상 페이지가 물리적으로 메모리에 없음을 운영체제가 감지한다.
2. 디스크에 페이지 로딩: 운영체제는 해당 페이지를 디스크에서 스왑 영역 또는 페이지 파일에서 찾아 물리 메모리로 로딩한다.
3. 페이지 테이블 업데이트: 로딩된 페이지 주소 정보를 페이지 테이블에 업데이트하여, 이후 같은 페이지가 필요할 때 물리 메모리에서 바로 접근할 수 있도록 한다.
4. 실행 재개: 페이지가 로딩되면, 페이지 폴트가 발생한 명령을 재시작하고 프로그램 실행을 계속한다.

페이지 크기에 대한 Trade-Off를 설명해 주세요.

페이지 크기가 클 때

• 큰 페이지는 한 번에 더 많은 데이터를 불러들일 수 있어서 디스크 입출력 효율이 좋다.
• 한 페이지에 더 많은 데이터를 포함하기 때문에 페이지 폴트 빈도가 줄어든다.
• 페이지 크기가 크기 때문에 내부 단편화가 커질 수 있다.

페이지 크기가 작을 때

• 페이지 크기가 작기 때문에 내부 단편화가 감소한다.
• 필요한 데이터만 작게 읽어오면 되기 때문에 디스크 입출력 부담이 적다.
• 작은 페이지는 더 많은 페이지가 필요하기 때문에 페이지 폴트 빈도가 증가한다.
• 페이지 테이블 크기가 늘어나 오버헤드가 생길 수 있다.

페이지 크기가 커지면, 페이지 폴트가 더 많이 발생한다고 할 수 있나요?

일반적으로 페이지 크기가 커지면 페이지 폴트가 덜 발생한다고 할 수 있다. 큰 페이지 크기는 한 번에 더 많은 데이터 메모리로 로드하기 때문에, 디스크 I/O를 줄일 수 있다. 그러나 페이지 크기가 너무 커지면 내부 단편화가 증가할 수 있으며 메모리 낭비가 발생할 수 있다.

세그멘테이션 방식을 사용하고 있다면, 가상 메모리를 사용할 수 없을까요?

세그멘테이션과 가상 메모리는 호환될 수 있다. 세그멘테이션은 메모리를 논리적인 단위로 나누는 것이지만, 가상 메모리는 주소 공간을 페이지 단위로 나누는 것이다. 세그먼트 단위로 메모리를 관리하면서, 각 세그먼트 내에서 페이지 단위로 메모리를 관리하며 혼용할 수 있다.