들어가며
소프트웨어가 복잡해질수록, 단순히 알고리즘의 시간복잡도만으로는 모든 문제를 해결할 수 없습니다. 특히 운영체제 수준에서는 다중 프로세스의 공정한 스케줄링과 사용자 반응성 보장이 시스템 안정성과 성능의 핵심이 되는데요.
이번 주 “그림으로 쉽게 배우는 자료구조와 알고리즘 (심화편)” 스터디 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()); // 웹브라우저 프로세스 출력구현 개요
자료구조
완전 이진 트리 형태의 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;
};- executionCount가 작을수록 우선
- 동률일 때는 cpuReturnCount가 클수록 우선
클래스 구조
JavaScript
// cpuScheduler.mjs
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
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
console.log(cpuScheduler.dequeue()); // 수치계산프로그램 프로세스 출력
console.log(cpuScheduler.dequeue()); // 터미널2 프로세스 출력
console.log(cpuScheduler.dequeue()); // 터미널1 프로세스 출력
console.log(cpuScheduler.dequeue()); // 뮤직플레이어 프로세스 출력
console.log(cpuScheduler.dequeue()); // 웹브라우저 프로세스 출력실행 결과
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 }- 첫 번째: 수치계산프로그램 (최소 실행횟수 = 0)
- 두 번째·세 번째: 실행횟수 2인 터미널1, 터미널2 중에서 cpuReturnCount가 큰 터미널2가 앞서 출력
- 네 번째·다섯 번째: 그 외 프로세스들이 실행횟수 오름차순으로 차례대로
느낀 점
- Heap 응용
우선순위 큐로서의 힙은 다양한 스케줄링·경로 탐색·이벤트 관리에 유용함을 다시 한 번 확인했습니다. - 정책 설계의 유연성
비교 함수를 바꾸는 것만으로 “실행횟수 우선” → “I/O Bound 우선” 같은 복합 우선순위 정책을 손쉽게 구현할 수 있었습니다. - 실전 적용 가능성
간단한 코드 수정으로 다른 스케줄링 알고리즘도 시도해 볼 수 있어, 실제로 확장해 보는 재미가 있을 것 같습니다.
마치며
이번 미션을 통해 Heap 기반 우선순위 큐 하나만으로 실행 횟수와 I/O 빈도를 동시에 고려한 스케줄링 정책을 깔끔하게 구현할 수 있다는 점을 확인했습니다. 비교 함수를 조금만 바꿔도 다양한 스케줄링 알고리즘을 손쉽게 적용해볼 수 있어, 자료구조의 유연성과 실전 활용 가치를 체감할 수 있었습니다. 앞으로 다른 스케줄러도 직접 구현하며 운영체제 설계 감각을 더욱 키워 나가고자 합니다. 감사합니다!
