제코베 JS 100제 / 93 / 페이지 교체 - 선입선출 알고리즘

페이지 교체 알고리즘은 메모리를 관리하는 운영체제에서, 페이지 부재가 발생하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것을 교체할지를 결정하는 방법입니다.

이 알고리즘이 사용되는 시기는 페이지 부재(Page Fault)가 발생해 새로운 페이지를 적재해야 하지만 페이지를 적재할 공간이 없어 이미 적재되어 있는 페이지 중 교체할 페이지를 정할 때 사용됩니다.

빈 페이지가 없는 상황에서 메모리에 적재된 페이지와 적재할 페이지를 교체함으로 페이지 부재 문제를 해결할 수 있습니다.

 

이 중 선입선출(FIFO) 알고리즘은 가장 먼저 들어와서 가장 오래있었던 페이지를 우선으로 교체시키는 방법을 의미합니다. 아래의 그림을 참고해주세요.

메모리의 크기가 i로 주어지고 들어올 페이지들이 n으로 주어졌을 때, 전체 실행시간을 구해주세요.

 

만약 스택 안에 같은 스케줄이 있다면 hit 이라고 하며 실행시간은 1초 입니다. 스택 안에 스케줄이 없다면 miss라고 하며 실행시간은 6초 입니다.

• 예제 1번을 보면 페이지 프레임의 개수는 3개이고 스케줄은 'BCBAEBCE' 입니다. 6번의 miss를 기록하므로 6번 * 6초 = 36초가 되고 2번의 hit을 기록하므로 2번 * 1초 = 2초입니다. 2개를 합한 값이 실행시간이므로, 38초가 됩니다.

 

/**
 * 적재할 페이지, 메모리 크기,
 * hit와 miss 일 때의 실행시간이 담긴 객체를 받아,
 * FIFO 페이지 교체 알고리즘을 실행할 때 총 실행시간을 구하는 함수
 *
 * @param {string} PAGE_LIST 적재할 페이지를 나열한 문자열
 * @param {number} MEMORY_SIZE 메모리의 크기
 * @param {Object} RUNTIME_INFO hit와 miss 일 때의 실행시간이 담긴 객체
 * @returns {number} 총 실행시간
 */
function getRuntimeWithFIFO(PAGE_LIST, MEMORY_SIZE, RUNTIME_INFO) {
  const { HIT, MISS } = RUNTIME_INFO;
  let memory = [];
  let runTime = 0;

  let oldestPageIndex = 0;
  for (const PAGE of PAGE_LIST) {
    // PAGE가 메모리에 이미 있다면, HIT
    if (memory.includes(PAGE)) runTime += HIT;
    // PAGE가 메모리에 없다면,
    else {
      // 메모리가 꽉 찼을 경우는 제일 오래된 것 교체
      if (memory.length === MEMORY_SIZE) {
        memory[oldestPageIndex] = PAGE;
        oldestPageIndex += 1;
        oldestPageIndex %= MEMORY_SIZE;
      } else memory.push(PAGE);
      runTime += MISS;
    }

    console.log(memory);
  }

  return runTime;
}

function solution() {
  const PAGE_LIST = 'BCBAEBCE';
  const MEMORY_SIZE = 3;
  const RUNTIME_INFO = {
    HIT: 1,
    MISS: 6,
  };

  const result = getRuntimeWithFIFO(PAGE_LIST, MEMORY_SIZE, RUNTIME_INFO);
  console.log(result); // 38
}

solution();

---

메모리에서 가장 오래된 페이지의 인덱스를 찾는 곳에서 주의해야 한다.

마지막 인덱스 다음은 다시 처음으로 돌아와야 하기 때문에 마치 원형 큐의 인덱스를 구현할 때처럼 해야한다. 따라서 modular operator(%)를 사용해서 마치 원형 큐 처럼 접근할 수 있도록 해주었다.