[Computer Lesson] Memory(2) - Management

지난 시간 컴퓨터의 메모리, 특히 캐시에 대해서 간단하게 알아보았다.

이번 시간에는 운영체제의 대표적인 업무 중 하나인 메모리 관리에 대해서 알아보려고 합니다.

✍ 가상 메모리 관리

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

여기서 주목해야 할 키워드는, 실제와 가상인데, 컴퓨터는 실제 주소와 가상 주소를 생성하여 TLB로 속도 관리를 해주고 메모리 관리 장치를 통해 매핑 및 변환이 되어 있기에 사용자들은 실제 주소를 의식할 필요 없이 프로그램을 구축 할 수 있게 된다.
=> TLB (Translation Lookaside Buffer) : 가상주소와 실제주소의 변환하는 과정에서 속력을 향상 시켜주는 가상 메모리 관리 시스템의 하드웨어 요소 중 하나이다.

📝 스와핑 (Swapping)

만약에 메모리 관리를 하던 중 페이지 폴트 (가상에는 존재하지만 실제에는 없을 때 발생하는 현상)가 일어났을 경우에는 당장 사용하지 않는 영역을 하드 디스크로 옮기고 하드디스크의 일부분을 마치 메모리처럼 불러와 쓰는 것을 스와핑이라고 한다.

위에 정의된 바와 같이, 페이지 폴트가 발생했을 시 스와핑이 일어나게 되는데 다음과 같은 거정을 거치게 된다.

스와핑 과정
물리 페이지 존재 여부 판단 후 없을 시 CPU는 트랩을 발생해서 운영체제에 알린다 => 운영체제는 이를 인지하고 CPU의 동작을 멈춘다 => 가상 메모리의 존재 여부 확인 후 없을 시 프로세스 중단 => 비어있는 프레임 확인 => 스와핑 진행 => 비어 있는 프레임에 해당 페이지 로드 및 최신화 => CPU 재시작.

✍ 스레싱 (Thrashing)

높은 페이지 폴트량으로 인해 스와핑이 일어나 CPU 이용률이 낮아져 가용성을 높이기 위해 메모리에 많은 프로세스를 올리게 되는 현상을 스레싱이라고 하며 스레싱이 일어날 경우, 컴퓨터의 성능은 저하된다.

📝 해결 방법

1. 저장 장치 추가

• 흔히 사용하고 있는 방법으로 메모리를 물리적으로 늘려주거나, HDD를 SSD로 교체 해주는 방법

2. 작업 세트 (Working Set)

• 미리 메모리에 지역성을 통해 만들어진 페이지들을 로드해서 탐색 비용을 줄여주는 방법

3. 페이지 폴트 빈도 수 관리 (Page Fault Frequency)

• 페이지 폴트의 상한선과 하한선을 설정 해줘 프레임 관리를 해주는 방법

✍ 메모리 할당

메모리의 주요 기능 중 하나인 메모리 할당에서는 시작 메모리 위치 및 크기에 따라 방식이 달라진다.

📝 연속 할당

의미 그대로 연속적으로 공간을 할당 하는 것

• 고정 분할 방식 (Fixed Partition Allocation) : 메모리를 미리 나누어 관리 (고정) | 내부 단편화 발생 (미리 쪼개두었기 때문에 프로그램이 들어가지 못하는 공간 발생)

• 가변 분할 방식 (variable Partition Allocation) : 프로그램 크기에 맞게 메모리 분할 | 외부 단편화 발생 (프로그램이이 남아있는 공간보다 커 들어가지 못하는 상황)

📝 불연속 할당

의미 그대로 불연속적으로 공간을 할당 하는 것

=> 현대 운영체제에서 주로 쓰이는 방식

• 페이징 : 동일한 크기의 페이지 단위로 나누어 메모리의 서로 다른 위치에 프로세스 할당
• 세그멘테이션 : 페이지 단위가 아닌 세그먼트로 나누는 방식
• 페이지드 세그멘테이션 : 공유나 보안을 의미 단위의 세그먼트르 나누고 물리적 메모리는 페이지로 나누느 것.

✍ 페이지 교체 알고리즘..

스와핑이 많이 일어나지 않도록 도와주는 알고리즘

사실상..이 부분을 가장 어려웠던 부분이고 아직까지 이해를 하지 못한 부분이기에 나중에 돌아와 공부를 제대로 공부를 해보겠다..

📝 오프라인 알고리즘

• 미래에 사용되는 페이지와 현재 페이지를 바꾸는 알고리즘
  => 가장 좋은 방법이라고 하는데...미래에 사용되는 프로세스를 우리가 알 수 있을까?

function bubbleSort(array) {
  let n = array.length;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (array[j] > array[j + 1]) {
        let temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
  return array;
}

const data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3];
const sortedData = bubbleSort(data);
console.log(sortedData);

📝 FIFO (First in First Out)

큐를 생각하면 됩니다

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.isEmpty()) {
      return "Underflow";
    }
    return this.items.shift();
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

📝 LRU (Least Recentle Used)

참조가 가장 오래된 페이지를 변경한다.

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  get(key) {
    if (!this.cache.has(key)) {
      return -1;
    }
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    }
    this.cache.set(key, value);
    if (this.cache.size > this.capacity) {
      this.cache.delete(this.cache.keys().next().value);
    }
  }
}

📝 LFU (Least Frequently Used)

가장 참조 횟수가 적은 페이지를 교환한다.

이해하지 못한....로직...내가 곧 돌아오겠다..하하하

class Node {
  constructor(key, value, freq) {
    this.key = key;
    this.value = value;
    this.freq = freq;
  }
}

class LFUNode {
  constructor(freq, nodes) {
    this.freq = freq;
    this.nodes = nodes;
  }
}

class LFUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
    this.freqList = new Map();
  }

  get(key) {
    if (!this.cache.has(key)) {
      return -1;
    }
    const node = this.cache.get(key);
    this.update(node);
    return node.value;
  }

  put(key, value) {
    if (this.capacity <= 0) {
      return;
    }
    if (this.cache.has(key)) {
      const node = this.cache.get(key);
      node.value = value;
      this.update(node);
    } else {
      if (this.cache.size >= this.capacity) {
        const minFreqNode = this.freqList.get(this.freqList.keys().next().value);
        const nodeToRemove = minFreqNode.nodes.values().next().value;
        this.cache.delete(nodeToRemove.key);
        minFreqNode.nodes.delete(nodeToRemove.key);
        if (minFreqNode.nodes.size === 0) {
          this.freqList.delete(minFreqNode.freq);
        }
      }
      const newNode = new Node(key, value, 1);
      this.cache.set(key, newNode);
      if (!this.freqList.has(1)) {
        this.freqList.set(1, new LFUNode(1, new Map()));
      }
      this.freqList.get(1).nodes.set(key, newNode);
    }
  }

  update(node) {
    const freqNode = this.freqList.get(node.freq);
    freqNode.nodes.delete(node.key);
    if (freqNode.nodes.size === 0) {
      this.freqList.delete(node.freq);
    }
    node.freq++;
    if (!this.freqList.has(node.freq)) {
      this.freqList.set(node.freq, new LFUNode(node.freq, new Map()));
    }
    this.freqList.get(node.freq).nodes.set(node.key, node);
  }
}