(CS) 캐시 메모리, 메모리 관리 기법, 페이지 교체 알고리즘

캐시 메모리

1. 캐시 메모리란?

캐시 메모리(Cache Memory)는 CPU와 RAM 간의 데이터 전송 속도를 높이기 위해 사용되는 중앙 처리 장치(CPU)와 주 기억장치(RAM) 사이에 위치한 고속 기억장치다.

캐시 메모리는 속도가 빠른 장치(CPU)와 느린 장치(RAM) 간의 속도 차이로 발생하는 병목현상을 완화하여 성능을 향상하는 데 중요한 역할을 합니다.

 

주기억장치에 비해 접근이 빠르지만, 용량이 작다는 특징을 가지고 있다.

캐시 메모리는 CPU가 처리할 데이터나 명령어를 저장하여 CPU가 필요할 때 빠르게 액세스 할 수 있도록 해준다.

 

CPU는 일반적으로 계층 구조를 가진 캐시 메모리를 사용한다.

CPU와의 거리에 따라 L1 캐시, L2 캐시, L3 캐시 등 여러 단계로 나뉜다.

숫자가 작을수록 CPU에 가까운 상위 레벨 캐시로 용량이 작고 빠르며, 숫자가 클수록 CPU에서 멀어지며 용량이 크고 느려진다.

 

L1 Cache

•  프로세서와 가장 가까운 캐시
•  속도를 위해 IC와 DC로 나뉨
•  IC(Instruction Cache) : 메모리에서 text 영역의 데이터를 다루는 캐시
•  DC(Data Cache) : 메모리에서 text 영역을 제외한 모든 데이터를 다루는 캐시

L2 Cache

• 용량이 큼
• 크기를 위해 L1 Cache와 같이 나누지 않음

L3 Cache

• 멀티 코어 시스템에서 여러 코어가 공유하는 캐시

2. 캐시 적중률

CPU가 주기억장치 메모리에 접근하기 전에 캐시 메모리에서 원하는 데이터 존재 여부를 확인하는데, 이때 필요한 데이터가 있는 경우 Hit(적중), 없는 경우 Miss(실패)라고 한다.

 

캐시 적중률(Cache Hit Rate)은 CPU가 요청한 데이터 중 메인 메모리에서 캐시 메모리로 이미 옮겨진 후 저장돼 있는 데이터의 비율을 말한다. 예를 들어, 캐시 메모리에 저장된 데이터 중에서 CPU가 요청한 데이터의 80%가 캐시 메모리에 저장되어 있는 경우, 캐시 적중률은 80%이다.

 

캐시 적중률은 CPU와 캐시 메모리의 성능을 평가하는 중요한 지표 중 하나다.

높은 캐시 적중률은 캐시 메모리의 용량과 속도가 적절하게 조정되어 있음을 나타내며, CPU의 작업 속도를 높일 수 있다. 반면에 캐시 적중률이 낮으면 CPU가 데이터를 찾기 위해 메인 메모리나 보조기억장치에서 데이터를 가져와야 하므로 작업 속도가 느려질 수 있다.

 

캐시 적중률은 또한 캐시 메모리의 설계나 알고리즘 개선에 대한 피드백을 제공할 수 있다.

예를 들어, 캐시 적중률이 낮다면 캐시 메모리의 용량을 늘리거나 알고리즘을 개선하여 적중률을 높일 수 있다.

 

또한 적중률을 사용하여 AMAT(Average Memory Access Time, 평균 메모리 액세스 시간)를 계산할 수 있다. 

CPU는 데이터를 가져오기 위해 다음과 같은 순서로 접근한다.

레지스터 -> L1 캐시(SRAM) -> L2 캐시 -> 주기억장치(DRAM) -> 보조기억장치(EEPROM)

아래의 표는 CPU가 요청하는 데이터를 불러오는 방식이다.

캐시 적중	캐시 메모리의 데이터를 CPU 레지스터에 복사합니다.
캐시 실패 & 주기억장치 적중	주기억장치 메모리의 데이터를 캐시 메모리에 복사하고, 캐시 메모리에 복제된 데이터를 CPU 레지스터에 복사합니다.
캐시 실패 & 주기억장치 실패	보조기억장치 메모리의 데이터를 주기억장치 메모리에 복사하고, 주기억장치 메모리에 복제된 데이터를 캐시 메모리에 복사하고, 캐시메모리에 복제된 데이터를 CPU 레지스터에 복사합니다.

이를 활용하여 AMAT를 계산하면 아래와 같다.

AMAT = Hit Ratio * Hit Time + Miss Ratio * Miss Penalty

= (1 - Miss Ratio) * Hit Time + Miss Ratio * (Hit Time + Miss Penalty)

= Hit Time + Miss Ratio * Miss Penalty

 

3. 캐시의 지역성

유형	설명	사례
시간적 지역성 (Temporal Locality)	최근 액세스 된 기억 장소가 가까운 미래에 다시 액세스 될 가능성이 높음	- Super Loop 내 반복 루프 - 서브루틴 (반복되어 사용하는 것을 메모리에 한번 적재하여 여러번 사용할 수 있도록 하는 방법) - 공통 변수 - LRU: Least Recently Used  (가장 오랫동안 참조되지 않은 페이지 교체)
공간적 지역성 (Spatial Locality)	액세스 된 기억장소와 인접한 기억장소가 액세스 될 가능성이 높음	- Sequential Execution  (for 반복문의 변수와 같은 순차적 실행) - 배열 - Prefetch  (연산에 필요한 data를 미리 가져옴)
순차적 지역성 (Sequential Locality)	분기가 발생하지 않는 한 명령어들은 기억장치에 저장된 순서대로 인출되어 실행

메모리 관리 기법

1. 가상 메모리란?

가상 메모리(Virtual memory)는 컴퓨터의 메모리(RAM)를 보조 저장장치(하드디스크 등)의 일부를 활용하여 확장하는 기술이다. 메모리가 실제 메모리보다 많아 보이게 하는 기술로, 어떤 프로세스가 실행될 때 메모리에 해당 프로세스 전체가 올라가지 않더라도 실행이 가능하다는 점에 착안하여 고안되었다.

 

컴퓨터에서 실행되는 프로그램들은 실행에 필요한 데이터와 명령어들을 RAM에 저장하고 사용하는데 모든 프로그램이 RAM에 올라갈 수 있는 용량을 가지고 있지 않기 때문에, 프로그램 실행 중에 RAM의 부족으로 인해 문제가 발생할 수 있다.

이때, 가상 메모리를 사용하면 디스크를 RAM의 보조 기억장치처럼 사용하여 물리적인 메모리보다 더 많은 양의 가상 메모리를 사용할 수 있다.

이를 위해 운영체제는 가상 메모리와 물리 메모리 사이의 매핑(mapping)을 관리하며, 필요한 데이터나 명령어를 필요할 때마다 보조 저장장치에서 가져와 RAM에 올리고 사용합니다.

 

가상 메모리는 프로그램이 사용하는 메모리 공간을 확보하는 데에도 사용된다. 일부 프로그램은 메모리 공간을 미리 예약해 놓지 않으면 실행이 되지 않는 경우도 있다. 이 경우에도 가상 메모리를 사용하여 필요한 공간을 예약해 놓고, 실행 시에는 실제 메모리 공간을 할당받아 사용할 수 있게 한다.

 

가상 메모리를 관리하는 특수 메모리 관리 하드웨어를 MMU(Memory Management Unit)라고 하며, 가상주소를 물리주소로 변환하고, 메모리를 보호하는 기능을 수행한다.

MMU의 역할

 

2. 메모리 단편화란?

메모리 단편화(Memory Fragmentation)는 컴퓨터의 메모리 할당 및 해제 작업에서 발생하는 현상이다.

프로그램이 실행되면서 동적으로 메모리를 할당하고 해제하는 과정이 빈번하게 발생하여 메모리 공간이 분할되고 조각나게 된다. 이때 사용 가능한 메모리가 충분함에도 불구하고 메모리 할당(사용)이 불가능한 상태가 발생하게 되는데, 이를 메모리 단편화라고 한다.

 

메모리 단편화의 종류에는 내부 단편화와 외부 단편화가 있다.

• 내부 단편화
  주기억장치 내의 실행 프로그램보다 사용자 영역이 커서 메모리 할당 후 사용되지 않고 남아있는 공간을 의미한다.
  예를 들어 특정 프로세스를 위해 OS가 60MB만큼의 메모리를 할당해 주었지만 사실 40MB만큼만 사용하고 있다면 필요 이상으로 프로세스가 메모리를 할당받았기 때문에 내부 단편화가 20MB만큼 생김
  
  

내부 단편화

• 외부 단편화
  주기억장치 내의 사용자 영역보다 실행 프로그램이 커서 프로그램이 메모리가 할당되지 않고 남아있는 공간을 의미한다.
  예를 들어 남아있는 메모리 공간이 50MB + 50MB = 100MB로 요청한 메모리 공간 80MB보다 크지만, 남아있는 공간이 연속적이지 않아 Process C를 할당할 수가 없게 된다. 따라서 남아있는 100MB의 메모리 공간이 낭비되게 되는 문제가 발생한다.
  

위의 단편화 문제를 해결하기 위해선 압축 기법을 사용할 수 있다.

압축 기법은 주기억장치 내 분산되어 있는 단편화된 공간들을 통합하여 하나의 커다란 빈 공간을 만드는 작업을 의미한다.

방금 위에서 살펴봤던 외부 단편화의 경우에 아래처럼 단편화된 공간들을 하나로 합쳐 100MB의 빈 공간을 만든다면 프로세스 C를 할당할 수 있게 된다.

단편화를 예방하는 방법으로는 메모리 풀과 메모리 할당기가 있다.

메모리 풀(Memory Pool)은 프로그램이 실행되기 전에 미리 일정한 크기의 메모리 공간을 할당해 두고, 필요할 때마다 이를 재활용하여 메모리 할당과 해제를 반복하는 방식이다.

메모리 할당기(Allocator)는 프로그램에서 동적으로 메모리를 할당할 때 사용하는 기법으로, 메모리 할당 요청에 대해 미리 할당된 메모리 공간 중에서 적절한 크기의 공간을 선택하여 할당한다.

메모리 풀과 메모리 할당기를 통해 메모리 단편화를 최소화하고, 메모리 할당과 해제 작업의 성능을 개선할 수 있다.

 

3. 페이징 기법

페이징 기법(Paging)은 가상 메모리(Virtual memory)를 구현하는 기술 중 하나로, 물리적인 메모리를 일정한 크기의 페이지(page)로 나누고, 가상 메모리도 같은 크기의 페이지로 나누어서 사용한다.

 

예를 들어, MMU를 사용할 때 CPU는 각 메모리에 접근하기 이전에 메모리 주소 번역 작업을 수행한다. 메모리를 일일이 가상 주소에서 물리적 주소로 번역하게 되면 작업 부하가 너무 높아지므로, MMU는 RAM을 여러 페이지로 나누어(페이징) 각 페이지를 하나의 독립된 항목으로 처리한다.

 

페이징 기법에서 각각의 페이지는 고유한 페이지 번호를 가지고 있으며, 가상 메모리에서 사용되는 페이지 번호와 물리 메모리에서 사용되는 페이지 번호를 매핑(mapping)하여 메모리 접근을 가능하게 한다.

이러한 방식으로 메모리를 관리하면 가상 메모리와 물리 메모리의 크기가 달라도, 페이지의 크기는 동일하기 때문에 쉽게 매핑을 할 수 있다. 페이지를 필요한 만큼만 로드하여 사용하기 때문에 메모리 공간을 효율적으로 활용할 수 있다.

또한 페이지 단위로 메모리를 할당하고 해제하기에 프로그램의 실행에 필요한 메모리 공간을 유연하게 할당할 수 있으며, 물리 메모리가 부족한 경우에는 페이지 교체 알고리즘을 이용하여 필요한 페이지만 물리 메모리에 올릴 수 있다.

이를 통해 가상 메모리의 용량을 효과적으로 활용할 수 있다.

 

하지만 위의 그림에서 볼 수 있듯이 원하는 페이지를 얻어오기 위해서 메모리에 두 번 접근해야 한다. 이런 작업은 속도를 크게 낮출 수 있다. 그래서 TLB(Translation Lookasied Buffer)를 활용하여 최근에 읽었던 page table을 매핑하여 저장한다.

이후에 다시 해당 page의 요청이 들어오면 TLB hit이 되어 바로 물리 주소로 접근할 수 있다.

4. 세그멘테이션 기법

세그멘테이션(Segmentation) 기법은 논리적 내용(의미론적 내용)을 기반으로 메모리를 일정한 크기의 블록인 세그먼트(Segment)로 분할하여 각각의 논리적인 주소 공간을 정의하고, 프로세스가 사용하는 메모리 영역을 서로 다른 세그먼트로 구분하여 관리하는 기법이다.

세그먼트 번호를 통해 Segmentation Table에서 시작 주소(base)를 알아내고(base[s]), offset(d)을 사용해 메인 메모리에서의 실제 위치를 알아낸다.

페이징과 달리 페이지 사이즈가 다르기 때문에 Segmentation Table에서 세그먼트 크기(limit)를 엔트리로 갖는다.

 

※ 페이징 vs 세그멘테이션

Paging : 돼지고기를 1cm씩 자르는 것

Segmentation : 삼겹살, 목살, 갈비, 껍데기, 항정살

페이지 교체 알고리즘

필요한 페이지가 메모리에 없을 때 Page-Falut가 발생하면 해당 페이지를 찾아 빈 프레임에 로딩해야 하는데, 이때 빈 프레임이 없을 경우 희생 당할 프레임(victim frame)을 고르는 알고리즘이 페이지 교체 알고리즘이다.

 

1. LRU(Least-Recently-Used) 알고리즘

LRU 알고리즘은 가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘이다.

성능이 좋은 편이기에 많은 운영체제가 채택하는 알고리즘이다.

 

2, FIFO(First-In-First-Out) 알고리즘

FIFO 알고리즘은 이름 그대로 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는 알고리즘이다.

구현이 간단하다는 장점이 있지만, 성능은 좋지 않은 편이다.

들어온 시간을 저장하거나 올라온 순서를 큐를 이용해 저장할 수 있다.

Belady`s Anomaly 현상(페이지 프레임 수를 늘릴 때, 페이지 부재가 더 자주 발생하는 현상)이 발생할 수 있다.

 

3. LFU(Least-Frequently-Used) 알고리즘

LFU 알고리즘은 참조횟수가 가장 적은 페이지를 교체하는 알고리즘이다.

교체 대상이 여러 개라면 가장 오랫동안 사용하지 않은 페이지(LRU 알고리즘)를 교체한다.

출처

캐시(Cache) 메모리와 지역성::하드웨어

[운영체제] 가상 메모리(Virtual Memory System)

운영체제 TLB ( Translation Look-aside Buffer )

[운영체제] 내부 단편화, 외부 단편화란? | 외부단편화 해결 방법

[운영체제 정리] 15: 세그멘테이션 (Segmentation) | 완숙의 에그머니🍳

[운영체제] 페이지 교체 알고리즘 (FIFO/OPT/LRU/LFU/MFU)