컴퓨터의 요소

  • CPU
  • DMA (Direct Memory Access) 컨트롤러
  • 메모리
  • 타미머
  • 디바이스 컨트롤러

CPU (Central Process Unit)

  • 산술논리연산장치, 제어장치, 레지스터로 구성 된 컴퓨터 장치
  • 인터럽트(Interrupt)에 의해 단순히 메모리에 존재하는 명령어를 해석하여 실행
  • 운영체제의 커널이 프로그램을 메모리에 올려 프로세스로 만들면 CPU가 이를 실행 처리

산술논리연산장치

  • ALU (Arithmetic Logic Unit)
  • 덧셈 뺄셈 같은 두 숫자의 산술연산과, 배타적 논리합, 논리곱 같은 논리 연산을 계산하는 디지털 회로

제어장치

  • CU (Control Unit)
  • 프로세스 조작을 지시라는 CPU의 한 부품
  • 입출력장치 간 통신을 제어하고 명령어들을 읽고 해석하며 데이터 처리를 위한 순서를 결정

레지스터

  • CPU안에 있는 매우 빠른 임시기억장치
  • CPU와 직접 연결되어 있어 메모리보다 연산 속도가 매우 빠른 것이 특징
  • CPU는 자체적으로 데이터를 저장할 방법이 없기 때문에 레지스터를 거쳐 데이터를 전달

CPU의 연산처리

  1. CU가 메모리에 계산할 값을 로드, 레지스터에도 로드
  2. CU가 레지스터에 있는 값을 계산하기 위해 ALU에 명령
  3. CU가 계산된 값을 다시 레지스터에서 메모리로 계산한 값을 저장

인터럽트 (Interrupt)

  • 어떤 신호가 들어왔을 때 CPU를 잠깐 정지시키는 것을 말함
  • 키보드, 마우스 등 I/O 디바이스로 인한 인터럽트, 0으로 숫자를 나누는 산술 연산에서의 인터럽트, 프로세스 오류 등으로 발생
  • 인터럽트가 발생되면 인터럽트 핸들러 함수가 모여 있는 인터럽트 벡터로 가서 인터럽트 핸들러 함수가 실행
  • 인터럽트 간에는 우선순위가 있고 우선순위에 따라 실행되며 인터럽트는 하드웨어 인터럽트, 소프트웨어 인터럽트 두 가지로 나뉨

인터럽트 핸들러 함수

  • 인터럽트가 발생할을 때 이를 핸들링하기 위한 함수
  • 커널 내부의 IRQ를 통해 호출되며, request_irq()를 통해 인터럽트 핸들러 함수를 등록할 수 있음

하드웨어 인터럽트

  • 키보드, 마우스를 연결하는 일 등의 I/O 디바이스에서 발생하는 인터럽트를 말함
  • 인터럽트 라인이 설계된 이후 순차적인 인터럽트 실행을 중지하고 운영체제에 시스템콜을 요청해서 원하는 디바이스로 향해 디바이스에 있는 작은 로컬 버퍼에 접근하여 일을 수행

    소프트웨어 인터럽트

  • 트랩(trap) 이라고도 함
  • 프로세스 오류 등으로 프로세스가 시스템콜을 호출할 때 발동

DMA Controller

  • I/O 디바이스가 메모리에 직접 접근할 수 있도록 하는 하드웨어 장치를 뜻함
  • CPU에만 너무 많은 인터럽트 요청이 들어오기 때문에 CPU 부하를 막아주며, CPU의 일을 부담하는 보조 컨트롤러
  • 하나의 작업을 CPU / DMA 컨트롤러가 동시에 하는 것을 방지

메모리

  • 전자회로에서 데이터나 상태, 명령어 등을 기록하는 장치를 말함
  • RAM(Random Access Memory) 이라고 함
  • 메모리는 작업장이며, 작업장의 크기가 곧 메모리의 크기
  • 메모리가 크면 그만큼 더 많은 일을 할 수 있음

타이머

  • 몇 초 안에는 작업이 끝나야 한다는 것을 정하고 특정 프로그램에 시간 제한을 다는 역할
  • 시간이 많이 걸리는 프로그램이 작동할 때 제한을 걸기 위해 존재

디바이스 컨트롤러 (Device Controller)

  • 컴퓨터와 연결되어 있는 I/O 디바이스들의 작은 CPU

로컬 버퍼 (Local Buffer)

  • 디바이스 컨트롤러 옆에 붙어 있는 로컬 버퍼는 각 디바이스에서 데이터를 임시로 저장하기 위한 작은 메모리를 뜻함

메모리

메모리 계층

| 구성 | 설명 | 휘발성 | 속도 | 기억용량 | | :–: | :— | :–: | :–: | :— | | 레지스터 | CPU 안에 있는 작은 메모리 | O | 가장 빠름 | 가장 작음 | | 캐시 | L1, L2,L3 캐시를 지칭 | O | 빠름 | 적음 | | 주기억장치 | RAM | O | 보통 | 보통 | | 보조기억장치 | HDD, SDD 등 | X | 느림 | 가장 많음 |

  • RAM은 보조기억장치로부터 일정향의 데이터를 복사해여 임시 저장하고 이를 필요 시마다 CPU에 빠르게 전달하는 역할
  • 계층 위로 올라갈수록 가격은 비싸지고 용량은 작아짐

캐시 (Cache)

  • 데이터를 미리 복사해 놓는 임시 저장소이자 빠른 장치와 느린 장치에서 속도 차이에 따른 병목 현상을 줄이기 위한 메모리
  • CPU 와 메모리 사이에 솓고 차이가 크기 때문에 중간에 레지스터 계층을 두어 속도 차이를 해결
  • 계층과 계층 사이에 있는 계층을 캐싱 계층이라고 함

지역성의 원리

  • 캐시를 계층에 두는 것인 아닌 직접 설정시 고려해야 하는 문제
  • 자주 사용하는 데이터를 기반으로 설정 해야함
  • 자주 사용되는 데이터에 대한 기준을 나눌 때 근거가 바로 지역성 (locality)
  • 시간 지역성 (temporal locality)
  • 공간 지역성 (spatial locality)

시간 지역성 (temporal locality)

int[] arr = new int[10];

for (int i = 0; i < 10; i++)
{
	arr[i] = i;
}
  • 최근 사용한 데이터에 다시 접근하려는 특성

    for loop 를 예로들면, 코드 안의 변수 i 에 계속적인 접근이 이루어지며, 여기서 데이터는 변수 i이며 최근에 사용 된 변수 이기 때문에 메모리는 ++ 될 때마다 i 에 접근하게 됨

공간 지역성

  • 최근 접근한 데이터를 이루고 있는 공간, 가까운 공간에 접근하는 특성

    for loop 에서 공간을 나타내는 arr 의 각 요소들에 i가 할당 되면서 배열에 연속적으로 접접근함

캐시히트 / 캐시미스

  • 캐시에서 원하는 데이터를 찾으면 캐시히트
  • 캐시에서 원하는 데이터를 찾지 못하면 캐시미스

  • 캐시히트를 하게 되면 데이터를 제어장치를 거쳐 데이터를 가져옵니다.
  • 이 경우 위치 및 CPU 내부 버스를 기반으로 작동하기 때문에 속도가 빠름
  • 반면 캐시미스의 경우 메모리에서 가져와야 하는데 이때 시스템 버스를 기반으로 작동하여 느린편 입니다.

캐시 매핑

  • 캐시가 히트되기 위해 매핑하는 방법을 말함
  • CPU 레지스터와 RAM 간에 데이터를 주고받을 때를 기반으로 설정
  • 레지스터는 RAM에 비해 굉장히 작기때문에 해당 레지스터가 계층으로서 역할을 수행 하기 위해서는 매핑이 필요함
이름 설명
직접 매핑
(Directed Mapping)
  • 메모리가 1 ~ 100이 있다면,
    - 캐시가 1 : 1~10, 2 : 1 ~ 20 ∙∙∙ 직접 매핑 하는 것을 말함
    - 처리가 빠르지만 충돌이 잦음
연관 매핑
(Associative Mapping)
  • 순서를 일치시키지 않고 관련 있는 캐시와 메모리를 매핑
    - 충돌이 적지만 모든 블럭을 탐색해야 하여 속도가 느림
집합 연관 매핑
(Set Associate Mapping)
  • 직접 매핑과 연관 매핑을 합쳐놓은 것
    - 순서는 일치시키지만 집합을 두어 저장
    - 블록화 되어 있기 때문에 검색은 좀 더 효율적
    - 메모리가 1 ~ 100이 있다면,
    - 캐시 1 ~ 5에는 , 1 ~ 50 의 데이터를 무작위로 저장하는 것을 말함

데이터베이스의 캐싱 계층

  • Main DB 의 위에 redis를 두어 캐싱 계층역할을 수행 하도록 하여 성능 향상을 함

메모리 관리

  • OS의 대표적 역할인 메모리 관리
  • 한정된 메모리를 극한으로 활용하는 것

가상 메모리 (Virtual Memory)

  • 실제로 사용 가능한 메모리 자원을 추상화하여 이를 사용하는 사용자들에게 매우 큰 메모리로 보이게 만드는 것을 말함

  • 가상적으로 주어진 주소를 가상 주소(Logical Adress)
  • 실제 메모리상에 있는 주소를(Physical Address)
  • 가상 주소는 메모리관리장치(MMU)에 의해 실제 주소로 변환
  • 사용자는 실제 주소를 의식할 필요 없이 프로그램을 구축할 수 있음
  • 가상 메모리는 가상 주소와 실제 주소가 매핑되어 있어 주소 정보가 들어 있는 페이지 테이블로 관리 됨
  • 속도 향상을 위해 TLB를 사용

TLB 메모리와 CPU 사이에 이쓴 주소 변환을 위한 캐시 페이지 테이블에 있는 리스트를 보관하여 CPU가 페이지 테이블까지 가지 않도록 해 속도를 향상시킬 수 있는 캐싱 계층

스와핑 (Swapping)

  • 가상 메모리에는 존재하지만, 실제 메모리 RAM에 현재 없는 데이터나 코드에 접근할 경우 Page Fault 가 발생됨
  • 이때 메모리에서 당장 사용하지 않은 영역을 하드디스크로 옯기고 하드디스크의 일부분을 메모리처럼 불러와 쓰는 것을 Swapping이라고 함
  • 마치 Page Fault 가 발생하지 않은 것 처럼 보이게 만듬

Page Fault

프로세스 주소 공간에는 존재하지만, 지금 RAM에 없는 데이터에 접근 했을 때 발생 페이지 폴트와 스와핑은 아래 과정으로 이루어짐

  1. 어떤 명령어가 유효한 가상 주소에 접근했으나 해당 페이지가 만약 없다면 트랩이 발생되어 운영체제에 알림

  2. 운영체제는 실제 디스크로부터 사용하지 않는 프레임을 찾음

  3. 해당 프레임을 실제 메모리에 가져와서 페이지 교체 알고리즘을 기반으로 특정 페이지와 교체 (Swapping)

  4. 페이지 테이블을 갱신 후 해당 명령어를 다시 시작

  • Page : 가상 메모리를 사용하는 최소 크기 단위
  • Frame : 실제 메모리를 사용하는 최소 크기 단위

스레싱 (Thrashing)

  • 메모리의 Page Fault 가 높은 것을 의미
  • 심각한 성능 하락을 초래함

  • Page Fault가 발생하면, CPU 사용률이 낮아짐
  • CPU 사용률이 낮아지면 OS는 가용성을 높이기 위해 더 많은 프로세스를 메모리에 올림
  • 반복
  • 이러한 문제로 스레싱이 발생 됨
  • 해결을 위해 Working Set, PFF가 존재

작업 세트

  • Working Set 은 프로세스의 과거 사용 이력인 지역성(Locality)를 통해 결정된 페이지의 집합을 만들어 메모리에 로드
  • 미리 메모리에 로드라여 탐색에 드는 비용을 줄일 수 있음
  • 그로 인해 스와핑도 줄어듬

PFF

  • Page Fault Frequency 는 페이지 폴트의 빈도를 조정하는 방법으로 상한/하한선을 만드는 방법
  • 상한선 도달 시 프레임을 늘리고, 하한선에서는 프레임을 줄임

메모리 할당

  • 메모리에 프로그램을 할당 시 시작 메모리 위치, 메모리 할당 크기를 기반으로 할당
  • 연속 할당 / 불연속 할당으로 나뉨

연속 할당

  • 메모리에 연속적으로 공간을 할당 하는 것

  • 프로세스 A, 프로세스 B, 프로세스 C가 순차적으로 공간에 할당하는 것을 볼 수 있음
  • 이는 메모리를 미리 나누어 관리하는 고정 분할 방식과
  • 매 시점 프로그램의 크기에 맞게 메모리를 분할아혀 사용하는 가변 분할 방식이 있음

고정 분할 방식 (Fixed Partition Allocation)

  • 메모리를 미리 나누어 관리하는 방식
  • 메모리가 미리 나위어 있기 때문에 융통성이 없음
  • 내부 단편화가 발생

내부 단편화 (Internal Fragmentation) 메모리를 나눈 크기보다 프로그램이 작아서 들어가지 못하는 공간이 많이 발생하는 현상

가변 분할 방식 (Variable Partition Allocation)

  • 매 시점 프로그램의 크기에 맞게 동적으로 메모리를 나눠 사용
  • 내부 단편화는 발생하지 않고 외부 단편화는 발생할 수 있음
  • 최초적합 (First Fit), 최적적합 (Best Fit), 최악적합 (Worst Fit)이 있음

| 이름 | 설명 | | :— | :— | | FirstFit | - 위쪽이나 아래쪽부터 시작해서 Hole을 찾으면 바로 할당 | | Best Fit | - 프로세스 크기 이상인 공간 중 작은 Hole 부터 할당 | | Worst Fit | - 프로세스의 크기와 가장 많이 차이가 나는 Hole에 할당 |

외부 단편화 (External Fragmentation) 메모리를 나눈 크기보다 프로그램이 커서 들어가지 못하는 공간이 발생하는 현상 예를 들어, 100MB 를 55MB, 45MB로 나눴지만 프로그램 크기는 70MB 일 때 들어가지 못하는 현상

홀 (Hole) 할당할 수 있는 비어 있는 메모리 공간

불연속 할당

  • 메모리를 연속적으로 할당하지 않는 불연속 할당은 현대 운영체제가 쓰는 방법으로 Paging 기법이 있음
  • 메모리를 동일한 크기의 Page (보통 4KB)로 나누고 프로그램 마다 페이지 테이블을 두어 이를 통해 메모리에 프로그램을 할당하는 것
  • 세그멘테이션, 페이지드 세그멘테이션 도 있음

페이징 (Paging)

  • 동일한 크기의 Page 단위로 나누어 메모리의 서로 다른 위치에 프로세스를 할당
  • Hole의 크기가 균일하지 않은 문제가 없어지지만 주소 변환이 복잡해짐

세그멘테이션 (Segmentation)

  • Page 단위가 아닌, 의미 단위의 Segment로 나누는 방식
  • 프로세스를 이루는 메모리는 Code, Data, Stack, Heap영역으로 이루어져 있는데, Code와 Data로 나누거나, 코드 내의 작은 함수를 Segment로 놓고 나눌 수 있음
  • 이는 공유와 보안 측면에서 장점을 가지지만, Hole의 크기가 균일하지 않은 단점이 있음

페이지드 세그멘테이션 (Paged Segmentation)

  • 프로그램을 의미 단위인 Segment로 나눠 공유나 보안 측면에 강점을 두고 임의 길이가 아닌 동일한 크기의 페이지 단위로 나누는 것을 말함

페이지 교체 알고리즘

  • 메모리는 한정되어 있기 때문에 스와핑이 많이 일어남
  • 스와핑은 많이 일어나지 않도록 설계되어야 하며, 이는 페이지 교체 알고리즘을 기반으로 스와핑이 일어남

오프라인 알고리즘 (Offline Algorithm)

  • 먼 미래에 참조되는 Page와 현재 할당하는 Page를 바꾸는 알고리즘
  • 가장 좋은 방법
  • 하지만 미래에 사용되는 알고리즘을 알 수 없어 사용이 불가능한 알고리즘
  • 다른 알고리즘의 성능 비교에 대한 상한기준(Upper_Bound)을 제공

FIFO (First In First Out) 선입 선출 가장 먼저 온 Page를 교체 영역에 가장 먼저 놓는 방법

LRU (Last Recently Used) 참조가 가장 오래된 페이지를 바꿈 오래된 것을 파악하기 위해 각 Page 마다 계수기, 스택을 두어야 하는 문제가 있음

LRU 구현

LRU 구현

  • 보통 두개의 자료구조로 구현
  • Hash Table, Doubly Linked List (이중 연결 리스트)
  • 해시 테이블은 이중 연결 리스트에서 빠르게 찾을 수 있도록 쓰고, 이중 연결 리스트는 한정된 메모리를 나타냄

C# 의 HashTable 과 Dictionary

  • C#에서 LRU(Least Recent Used) 캐시를 구현하는 맥락에서 사전 대신 해시 테이블을 사용하는 것이 실행 가능한 접근 방식입니다.
  • 두 데이터 구조 모두 비슷한 목적으로 사용되기 때문입니다.
  • 그러나 이들 간의 차이점과 이러한 차이점이 구현에 어떤 영향을 미칠 수 있는지 이해하는 것이 중요합니다.

  1. C#의 HashTable과 사전

    • HashTable: 키-값 쌍을 저장하는 컬렉션입니다.
      • 여러 판독기 스레드와 단일 쓰기 스레드에서 사용하기에 스레드로부터 안전합니다.
      • 이는 이전 버전의 .NET으로 거슬러 올라가는 레거시 컬렉션입니다.
      • HashTable의 키와 값은 ‘객체’ 유형입니다.
      • 이는 모든 데이터 유형을 저장할 수 있다는 의미이지만 값 유형에 대한 박싱 및 언박싱 오버헤드도 의미합니다.
    • Dictionary: .NET 2.0에 도입된 일반 컬렉션입니다. 
    • Dictionary<TKey, TValue>는 스레드로부터 안전하지 않습니다(추가 동기화 없음).
    • 키와 값 모두에 대한 유형을 지정할 수 있으므로 더 나은 유형 안전성과 성능(값 유형에 대한 boxing/unboxing 없음)을 제공합니다.

  2. LRU 캐시 구현에 대한 의미

    • HashTable을 사용하는 경우 LRU 캐시가 키와 값에 대한 특정 유형을 처리하는 경우가 많기 때문에 유형 안전성을 잃고 박싱 및 언박싱으로 인해 잠재적으로 성능 비용이 발생할 수 있습니다.

    • Dictionary<TKey, TValue>는 형식 안전성과 더 나은 성능 특성으로 인해 일반적으로 최신 C# 애플리케이션에서 더 성능이 좋고 선호됩니다.

  3. 기타 고려사항

    • HashTable과 Dictionary 중 하나를 선택해도 LRU 캐시 구현의 전반적인 논리는 크게 바뀌지 않습니다.
    • 항목 사용 순서를 추적하려면 이중 연결 리스트를 관리해야 합니다.
    • LRU 캐시의 핵심 측면은 항목에 빠르게 액세스하고(가져오기 및 넣기 작업) 사용량에 따라 항목 순서를 효율적으로 유지하는 기능입니다.
    • 이를 위해서는 순서를 관리하기 위한 키-값 저장소(해시 테이블이나 딕셔너리 등)뿐만 아니라 구조(이중 연결 리스트 등)도 필요합니다.

요약하자면, C#에서 LRU 캐시 구현을 위해 ‘Dictionary’ 대신 ‘HashTable’을 사용할 수 있지만 일반적으로 유형 안전성, 더 나은 성능 및 최신 버전과 일치하기 때문에 ‘Dictionary’를 사용하는 것이 좋습니다.

LRU 캐시 구현의 중요한 부분은 항목 사용 순서를 유지하기 위해 키-값 저장소와 함께 이중 연결 목록을 관리하는 방법입니다.

using System;
using System.Collections.Generic;

public class LRUCache<TKey, TValue>
{
    private readonly int _capacity;
    private Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>> _cache;
    private LinkedList<KeyValuePair<TKey, TValue>> _lruList;

    public LRUCache(int capacity)
    {
        _capacity = capacity;
        _cache = new Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>>(capacity);
        _lruList = new LinkedList<KeyValuePair<TKey, TValue>>();
    }

    public TValue Get(TKey key)
    {
        if (_cache.TryGetValue(key, out var node))
        {
			// 항목을 찾으면 목록의 맨 앞으로 이동시켜 최근 사용된 것으로 표시합니다.
            _lruList.Remove(node);
            _lruList.AddFirst(node);
            return node.Value.Value;
        }

        return default(TValue);
    }

    public void Put(TKey key, TValue value)
    {
        if (!_cache.TryGetValue(key, out var node))
        {
            if (_cache.Count == _capacity)
            {
				// 캐시가 최대 용량에 도달하면, 가장 최근에 사용되지 않은 항목을 제거합니다.
                _cache.Remove(_lruList.Last.Value.Key);
                _lruList.RemoveLast();
            }

			// 새 항목을 캐시 및 목록에 추가합니다.
            var newNode = new LinkedListNode<KeyValuePair<TKey, TValue>>(new KeyValuePair<TKey, TValue>(key, value));
            _lruList.AddFirst(newNode);
            _cache[key] = newNode;
        }
        else
        {
			// 값을 업데이트하고 목록의 맨 앞으로 이동시킵니다.
            node.Value = new KeyValuePair<TKey, TValue>(key, value);
            _lruList.Remove(node);
            _lruList.AddFirst(node);
        }
    }
}

public class Program
{
    public static void Main()
    {
        var cache = new LRUCache<int, string>(2);
        cache.Put(1, "A");
        cache.Put(2, "B");
        Console.WriteLine(cache.Get(1)); // "A" 반환
        cache.Put(3, "C"); // 키 2("B")를 제거합니다.
        Console.WriteLine(cache.Get(2)); // null 반환 (string의 기본값)
    }
}
  • LRUCache<TKey, TValue>는 모든 키 및 값 유형과 함께 사용할 수 있는 일반 클래스입니다.
  • Get 메소드는 캐시에서 항목을 검색하여 목록 맨 앞으로 이동하여 최근에 사용한 항목으로 표시합니다.
  • Put 메소드는 캐시에 항목을 추가합니다.
  • 캐시가 용량에 도달하면 새 항목을 추가하기 전에 가장 최근에 사용된 항목을 제거합니다.
  • ‘LinkedList<KeyValuePair<TKey, TValue»‘는 항목의 순서를 유지하는 데 사용됩니다.
  • 가장 최근에 사용한 항목이 항상 목록 맨 앞에 표시됩니다.

NRU 구현

NRU (Not Used Recently)

  • Clock Algorithm 이라고 하며, 0과 1을 가진 비트를 둡니다.
  • 1은 최근에 참조되었고 0은 참조괴지 않음을 의미 합니다.
  • 시계방향으로 돌면서 0을 찾고, 0을 찾은 순간 해당 프로세스를 교체하고, 해당 부분을 1로 바꾸는 알고리즘

using System; 

public class ClockAlgorithm 
{ 
	private int[] pages; 
	private bool[] referenceBits; 
	private int capacity; 
	private int pointer; 
	
	public ClockAlgorithm(int capacity) 
	{ 
		this.capacity = capacity; 
		pages = new int[capacity]; 
		referenceBits = new bool[capacity]; 
		pointer = 0; 
		for (int i = 0; i < capacity; i++) 
		{ 
			pages[i] = -1; // 유효하지 않은 페이지 번호로 초기화 
		} 
	} 
	
	private int FindPage(int page) 
	{ 
		for (int i = 0; i < capacity; i++) 
		{ 
			if (pages[i] == page) 
			{ 
				return i; 
			} 
		} 
		return -1; 
	} 
	
	public void AccessPage(int page) 
	{ 
		int pageIndex = FindPage(page); 
		if (pageIndex == -1) // 페이지를 찾지 못한 경우, 클럭 알고리즘을 사용하여 페이지 교체 
		{ 
			while (true) 
			{ 
				if (!referenceBits[pointer]) // 참조 비트가 false인 경우 
				{ 
					pages[pointer] = page; 
					referenceBits[pointer] = true; // 참조 비트 설정 
					pointer = (pointer + 1) % capacity; // 클럭 핸드 이동 break; 
				} 
				else 
				{ 
					referenceBits[pointer] = false; // 두 번째 기회 제공 
					pointer = (pointer + 1) % capacity; // 클럭 핸드 이동 
				} 
			} 
		} 
		else // 페이지를 찾은 경우, 참조 비트 설정 
		{ 
			referenceBits[pageIndex] = true; 
		} 
	} 
	
	public void PrintPages() 
	{ 
		Console.WriteLine("메모리 내 페이지:"); 
		for (int i = 0; i < capacity; i++) 
		{ 
			Console.WriteLine($"페이지: {pages[i]}, 참조 비트: {referenceBits[i]}"); 
		} 
	} 
} 

public class Program 
{ 
	public static void Main() 
	{ 
		var clockAlgorithm = new ClockAlgorithm(4);
		clockAlgorithm.AccessPage(1); 
		clockAlgorithm.AccessPage(2); 
		clockAlgorithm.AccessPage(3); 
		clockAlgorithm.AccessPage(4); 
		clockAlgorithm.PrintPages(); 
		clockAlgorithm.AccessPage(1); 
		clockAlgorithm.AccessPage(5); // 페이지 교체 발생 
		clockAlgorithm.PrintPages(); 
		} 
	}
  • ClockAlgorithm은 메모리 페이지와 해당 참조 비트를 나타냅니다.
  • AccessPage는 페이지 액세스를 시뮬레이션합니다.
  • 페이지가 메모리에 없으면 시계 알고리즘을 사용하여 페이지를 교체합니다.
  • FindPage는 배열에서 페이지를 검색하고 해당 색인을 반환합니다.
  • 포인터는 페이지를 원형으로 이동하는 시계 바늘을 시뮬레이션합니다.
  • PrintPages는 페이지의 현재 상태와 참조 비트를 표시하는 유틸리티 방법입니다.

LFU 구현

LFU (Least Frequently Used)

  • 가장 참조 횟수가 적은 페이지를 교체
  • 많이 사용되지 않은 것을 교체하는 것
using System; 
using System.Collections.Generic; 

public class LFUCache<TKey, TValue> 
{ 
	private class CacheItem 
	{ 
		public TValue Value { get; set; } 
		public int Frequency { get; set; } 
	} 
	
	private Dictionary<TKey, CacheItem> _cache; 
	private int _capacity; 
	
	public LFUCache(int capacity) 
	{ 
		_capacity = capacity; 
		_cache = new Dictionary<TKey, CacheItem>(capacity); 
	} 
	
	public TValue Get(TKey key) 
	{ 
		if (_cache.TryGetValue(key, out CacheItem item)) 
		{ 
			// 사용 빈도 수 증가
			item.Frequency++; 
			return item.Value; 
		} 
		// 키를 찾지 못하였을 때 기본값 반환
		return default(TValue); 
	} 
	
	public void Put(TKey key, TValue value) 
	{ 
		if (_cache.ContainsKey(key)) 
		{ 
			// 사용 빈도 업데이트
			_cache[key].Value = value; 
			_cache[key].Frequency++; 
		} 
		else 
		{ 
			if (_cache.Count == _capacity) 
			{ 
				// 적게 사용한 아이템 제거
				RemoveLeastFrequentlyUsedItem(); 
			} 
			// 새로운 아이템 추가
			_cache[key] = new CacheItem 
			{ 
				Value = value, 
				Frequency = 1 
			}; 
		} 
	} 
	
	private void RemoveLeastFrequentlyUsedItem() 
	{ 
		TKey leastFrequentKey = default; 
		int minFrequency = int.MaxValue; 
		foreach (var pair in _cache) 
		{ 
			if (pair.Value.Frequency < minFrequency) 
			{ 
				minFrequency = pair.Value.Frequency; 
				leastFrequentKey = pair.Key; 
			} 
		} 
		_cache.Remove(leastFrequentKey); 
	} 
} 

public class Program 
{ 
	public static void Main() 
	{ 
		var cache = new LFUCache<int, string>(2); 
		cache.Put(1, "A"); 
		cache.Put(2, "B"); 
		Console.WriteLine(cache.Get(1)); // "A" 반환 
		cache.Put(3, "C"); // 사용 빈도가 적은 "B" 제거
		Console.WriteLine(cache.Get(2)); // Null 반환
	} 
}

각 알고리즘에 적합한 게임 시스템

LFU(Least Frequently Used)

  • Object Pooling
    • 다양한 객체(예: 적, 총알, 효과)가 포함된 게임에서 LFU는 자주 사용하는 객체를 준비하고 자주 사용하지 않는 객체를 처리하여 객체 풀을 관리할 수 있습니다.
    • 예를 들어 특정 적 유형이 다른 유형보다 더 자주 나타나는 경우 LFU는 이러한 유형이 풀에 유지되도록 할 수 있습니다.
  • Asset Caching
    • LFU는 자주 사용되는 텍스처나 모델과 같은 에셋을 캐싱하는 데 유용합니다.
    • 대규모 오픈 월드 게임에서는 특정 에셋이 특정 영역에서 더 일반적일 수 있습니다.
    • LFU는 더 빠른 액세스를 위해 이러한 에셋을 캐시된 상태로 유지합니다.
  • Audio Management
    • 광범위한 사운드 효과나 음악 트랙이 포함된 게임에서 LFU는 자주 재생되는 사운드에 대한 빠른 액세스를 유지하여 오디오 재생 성능을 향상시키는 데 도움이 됩니다.

LRU(Least Recently Used)

  • Scene Management
    • LRU는 장면 또는 레벨과 관련된 데이터를 관리하는 데 이상적입니다.
    • 플레이어가 뒤로 돌아갈 수 있는 게임의 경우 LRU는 더 빠르게 다시 로드하기 위해 최근 방문한 씬을 메모리에 유지할 수 있습니다.
  • Texture and Material Caching
    • 동적 환경 또는 스트리밍 콘텐츠가 있는 게임의 경우 LRU를 사용하여 최근 사용량을 기반으로 텍스처와 재료를 캐시 및 릴리스하여 메모리 사용량을 최적화할 수 있습니다.
  • Data Caching
    • 대규모 데이터 세트(예: 대화, 퀘스트 정보 등)가 있는 게임에서 LRU는 가장 최근에 액세스한 데이터를 캐시하여 빠른 액세스와 효율적인 메모리 사용을 보장합니다.

NRU(Not Recently Used)

  • Memory Management for AI
    • NRU는 AI 시스템에서 의사결정 트리 캐싱 또는 데이터 경로 찾기에 사용될 수 있습니다.
    • AI 동작에 지속적인 업데이트가 필요하지 않은 게임에서 특히 효과적입니다.
  • Resource Management in Large Maps
    • 대규모 전략 또는 시뮬레이션 게임에서 NRU는 자주 상호 작용하지 않는 지도의 리소스나 개체를 관리하여 메모리를 효율적으로 사용할 수 있습니다.
  • Particle Effect Management
    • 파티클 효과(예: 주문, 폭발 등)가 많은 게임의 경우 NRU는 이러한 리소스를 효과적으로 관리하여 최근에 사용되지 않은 효과를 제거할 수 있도록 준비할 수 있습니다.

LFU는 시간이 지남에 따라 반복적으로 사용되는 요소에 적합합니다.

LRU는 최근 사용에 관한 것이므로 플레이어나 게임이 곧 다시 방문하거나 재사용할 수 있는 요소에 적합합니다.

NRU는 LRU보다 덜 정확하지만 더 간단하고 많은 게임 개발 시나리오에 충분한 균형을 제공합니다.