그림으로 쉽게 배우는 자료구조와 알고리즘: 미션2 | CPU 스케줄링

development-logo

들어가며

소프트웨어가 복잡해질수록, 단순히 알고리즘의 시간복잡도만으로는 모든 문제를 해결할 수 없습니다. 특히 운영체제 수준에서는 다중 프로세스의 공정한 스케줄링과 사용자 반응성 보장이 시스템 안정성과 성능의 핵심이 되는데요.

그림으로 쉽게 배우는 자료구조와 알고리즘 (심화편)

이번 주 “그림으로 쉽게 배우는 자료구조와 알고리즘 (심화편)” 스터디 2주차 미션에서는,
프로세스가 얼마나 자주 CPU를 사용했는지(실행 횟수)와 I/O Bound 여부(자발적 CPU 반납 횟수)를 기준으로
우선순위를 매기는 CPU 스케줄러를 구현해 보았습니다.

미션

여러 프로세스들이 골고루 실행되도록 하기 위해 다음 두 가지 정책을 적용한 CPU 스케줄러를 만들어 보세요.

실행 횟수(executionCount)가 가장 작은 프로세스가 우선순위가 높다.
실행 횟수가 같을 경우, I/O Bound 프로세스(cpuReturnCount가 큰 프로세스) 가 우선순위가 높다.

JavaScript

class Process{
    constructor(name, cpuReturnCount, executionCount){
    }
}

let cpuScheduler = new CpuScheduler();
cpuScheduler.enqueue(new Process("수치계산프로그램", 4, 0)); // cpu반납 4회, 실행횟수 0회
cpuScheduler.enqueue(new Process("뮤직플레이어", 11, 10)); // cpu반납 11회, 실행횟수 10회
cpuScheduler.enqueue(new Process("웹브라우저", 27, 25)); // cpu반납 27회, 실행횟수 25
cpuScheduler.enqueue(new Process("터미널1", 34, 2)); // cpu반납 34회, 실행횟수 2회
cpuScheduler.enqueue(new Process("터미널2", 93, 2)); // cpu반납 93회, 실행횟수 2회

console.log(cpuScheduler.dequeue()); // 수치계산프로그램 프로세스 출력
console.log(cpuScheduler.dequeue()); // 터미널2 프로세스 출력
console.log(cpuScheduler.dequeue()); // 터미널1 프로세스 출력
console.log(cpuScheduler.dequeue()); // 뮤직플레이어 프로세스 출력
console.log(cpuScheduler.dequeue()); // 웹브라우저 프로세스 출력

JavaScript

구현 개요

자료구조

완전 이진 트리 형태의 Heap(힙)을 사용하여 O(log N) 삽입·삭제·조회 성능을 확보합니다.

우선순위 비교 함수(isBigPriority 재정의)

JavaScript

// CpuScheduler 생성자 내부
this.heap.isBigPriority = (first, second) => {
  if (first.executionCount !== second.executionCount) {
    // 실행 횟수가 적은 프로세스가 우선
    return first.executionCount < second.executionCount;
  }
  // 실행 횟수가 같다면 I/O Bound 정도(cpuReturnCount)가 큰 쪽이 우선
  return first.cpuReturnCount > second.cpuReturnCount;
};

JavaScript

executionCount가 작을수록 우선
동률일 때는 cpuReturnCount가 클수록 우선

클래스 구조

JavaScript

import { Heap } from "../../heap/heap.mjs";

class Process {
  constructor(name, cpuReturnCount, executionCount) {
    this.name = name;
    this.cpuReturnCount = cpuReturnCount;
    this.executionCount = executionCount;
  }
}

class CpuScheduler {
  constructor() {
    this.heap = new Heap();
    // 우선순위 정책 정의
    this.heap.isBigPriority = (first, second) => {
      if (first.executionCount !== second.executionCount) {
        return first.executionCount < second.executionCount;
      }
      return first.cpuReturnCount > second.cpuReturnCount;
    };
  }

  enqueue(process) {
    this.heap.insert(process);
  }

  dequeue() {
    const node = this.heap.remove();      // BinaryTree 노드
    return node ? node.getData() : null;   // Process 객체 반환
  }
}

JavaScript

테스트 흐름

프로세스 등록

JavaScript

cpuScheduler.enqueue(new Process("수치계산프로그램", 4, 0)); // cpu반납 4회, 실행횟수 0회
cpuScheduler.enqueue(new Process("뮤직플레이어", 11, 10)); // cpu반납 11회, 실행횟수 10회
cpuScheduler.enqueue(new Process("웹브라우저", 27, 25)); // cpu반납 27회, 실행횟수 25
cpuScheduler.enqueue(new Process("터미널1", 34, 2)); // cpu반납 34회, 실행횟수 2회
cpuScheduler.enqueue(new Process("터미널2", 93, 2)); // cpu반납 93회, 실행횟수 2회

JavaScript

우선순위에 따라 꺼내기

JavaScript

console.log(cpuScheduler.dequeue()); // 수치계산프로그램 프로세스 출력
console.log(cpuScheduler.dequeue()); // 터미널2 프로세스 출력
console.log(cpuScheduler.dequeue()); // 터미널1 프로세스 출력
console.log(cpuScheduler.dequeue()); // 뮤직플레이어 프로세스 출력
console.log(cpuScheduler.dequeue()); // 웹브라우저 프로세스 출력

JavaScript

실행 결과

PowerShell

Process { name: '수치계산프로그램', cpuReturnCount: 4,  executionCount: 0  }
Process { name: '터미널2',        cpuReturnCount: 93, executionCount: 2  }
Process { name: '터미널1',        cpuReturnCount: 34, executionCount: 2  }
Process { name: '뮤직플레이어',    cpuReturnCount: 11, executionCount: 10 }
Process { name: '웹브라우저',      cpuReturnCount: 27, executionCount: 25 }

PowerShell

첫 번째: 수치계산프로그램 (최소 실행횟수 = 0)
두 번째·세 번째: 실행횟수 2인 터미널1, 터미널2 중에서 cpuReturnCount가 큰 터미널2가 앞서 출력
네 번째·다섯 번째: 그 외 프로세스들이 실행횟수 오름차순으로 차례대로

느낀 점

Heap 응용
우선순위 큐로서의 힙은 다양한 스케줄링·경로 탐색·이벤트 관리에 유용함을 다시 한 번 확인했습니다.
정책 설계의 유연성
비교 함수를 바꾸는 것만으로 “실행횟수 우선” → “I/O Bound 우선” 같은 복합 우선순위 정책을 손쉽게 구현할 수 있었습니다.
실전 적용 가능성
간단한 코드 수정으로 다른 스케줄링 알고리즘도 시도해 볼 수 있어, 실제로 확장해 보는 재미가 있을 것 같습니다.

마치며

이번 미션을 통해 Heap 기반 우선순위 큐 하나만으로 실행 횟수와 I/O 빈도를 동시에 고려한 스케줄링 정책을 깔끔하게 구현할 수 있다는 점을 확인했습니다. 비교 함수를 조금만 바꿔도 다양한 스케줄링 알고리즘을 손쉽게 적용해볼 수 있어, 자료구조의 유연성과 실전 활용 가치를 체감할 수 있었습니다. 앞으로 다른 스케줄러도 직접 구현하며 운영체제 설계 감각을 더욱 키워 나가고자 합니다. 감사합니다!

suover