![[인프런 워밍업 클럽 4기 - CS] - 2주차 미션 (자료구조와 알고리즘 심화)](https://cdn.inflearn.com/public/files/blogs/199db9f2-bb75-4e3e-942a-53ab881b442e/337244.png)
[인프런 워밍업 클럽 4기 - CS] - 2주차 미션 (자료구조와 알고리즘 심화)
문제
여러분은 간단한 운영체제를 개발하고 있습니다. 운영체제의 CPU 스케줄링을 구현해야 하는 차례입니다. 여러 프로세스들이 골고루 실행되도록 하기 위해, 프로세스 실행 횟수(executionCount)가 작은 프로세스의 우선순위를 높게 설정하는 CPU 스케줄링 정책을 만들려고 합니다. 또한, 모든 프로세스가 비슷하게 실행될 때는 사용자의 반응성을 높이기 위해 I/O Bound 프로세스들의 처리를 우선적으로 하려고 합니다. I/O Bound 프로세스는 CPU를 사용하다가 자발적으로 CPU를 반납(cpuReturnCount)하는 것으로 판단할 수 있습니다. 따라서 다음 두 가지 조건으로 CPU 스케줄러를 구현해 보세요:
프로세스 실행 횟수가 가장 적은 프로세스가 우선순위가 높습니다.
실행 횟수가 같을 경우, I/O Bound 프로세스가 우선순위가 높습니다.
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()); // 웹브라우저 프로세스 출력
풀이
풀이 1
Process 클래스와 생성자에 필요한 property들을 설정해주었다.
PriorityQueue에 Heap 메서드인 isBigPriority를 오버라이드하여 필요한 함수로 작성해주었다.
조건문을 통해 executionCount가 적은 프로세스 먼저 실행시키고(오름차순) 만약 executionCount가 동일하다면 cpuReturnCount가 높은 값부터 호출한다(내림차순)
//mission.mjs
import { PriorityQueue as CpuScheduler } from "./priorityQueue.mjs";
class Process {
constructor(name, cpuReturnCount, executionCount) {
this.name = name;
this.cpuReturnCount = cpuReturnCount;
this.executionCount = executionCount;
}
}//priorityQueue.mjs
import { Heap } from "./heap.mjs";
export class PriorityQueue {
constructor() {
this.heap = new Heap();
// 첫 번째 우선순위, 두 번째 우선순위 비교
this.heap.isBigPriority = (first, second) => {
if (first.executionCount === second.executionCount) {
return first.cpuReturnCount > second.cpuReturnCount;
}
return first.executionCount < second.executionCount;
};
}
enqueue(data) {
return this.heap.insert(data);
}
dequeue(data) {
return this.heap.remove(data);
}
}하지만 상위 문제 풀이에는 두 가지 문제점이 있다.
첫 번째는 우선 순위의 추가가 불편하다는 점이다. 문제에서는 두 개의 우선순위만 주어졌기에 함수에 isBigPriority 함수에 조건문을 통해 작성하였지만 10개, 100개로 늘어갈 수록 함수의 조건문은 점점 길어져갈 것이다.
두 번째는 우선순위의 변경이 불편하다는 점이다. 만약 문제와 반대로 executionCount와 cpuReturnCount의 우선순위가 바뀐다면 함수에서 조건문 전체를 변경해줘야 한다. 두 개의 우선순위를 변경하는 것도 귀찮은 일인데 만약 이 또한 100개가 되는 우선순위 순서를 변경해야한다면 오랜 시간이 걸릴 것이다.
풀이 2
Process에서 첫 번째 우선순위 priority를 executionCount로 설정하고, 두 번째 우선순위 secondPriority를 cpuReturnCount를 선언하였다.
PriorityQueue에서 Heap 클래스의 isBigPriority를 오버라이드하여 새로운 우선순위 함수로 정의해주었다.
첫 번째 우선순위는 오름차순으로 설정하고 조건문을 통해 첫 우선순위가 동일할 경우, 두 번째 우선순위로 비교하여 내림차순으로 설정하였다.
//mission.mjs
import { PriorityQueue as CpuScheduler } from "./priorityQueue.mjs";
class Process {
constructor(name, cpuReturnCount, executionCount) {
this.name = name;
this.cpuReturnCount = cpuReturnCount;
this.executionCount = executionCount;
// 첫 번째 우선순위
this.priority = executionCount;
// 두 번째 우선순위
this.secondPriority = cpuReturnCount;
}
}//priorityQueue.mjs
import { Heap } from "./heap.mjs";
export class PriorityQueue {
constructor() {
this.heap = new Heap();
// 1. 첫 번째 우선순위 오름차순
// 2. 두 번째 우선순위 내림차순
this.heap.isBigPriority = (first, second) => {
if (first.priority === second.priority) {
return first.secondPriority > second.secondPriority;
}
return first.priority < second.priority;
};
}
enqueue(data) {
return this.heap.insert(data);
}
dequeue(data) {
return this.heap.remove(data);
}
}상위 풀이는 풀이 1의 두 번째 문제를 해결하였다. 각 우선순위의 대상이 되는 변수를 함수에 직접 구현한 것이 아닌 priority, secondPriority와 같이 우선 순위를 담는 변수를 따로 선언하여 함수에 구현하였기 때문에, 우선순위를 변경하려면 간단히 Process 클래스에서 property만 변경해주면 된다는 이점이 있다.
하지만 풀이 1의 첫 번째 문제는 아직 해결되지 못하였다. 여전히 priority가 10개, 100개로 늘어난다면 Process에 선언해야 할 property가 그만큼 늘어나게 될 것이다.
풀이 3
우선순위 큐를 선언하기 전, Priority를 결정하는 rules 배열을 선언해주었다. rules에는 우선순위로 활용할 process 인스턴스의 property와 오름차순, 내림차순을 결정할 type으로 형성된 객체를 배열로 받는다.
이 후, 우선순위 큐를 생성하면서 rules를 매개변수로 생성자에 넘겨주고 isBigPriority에서는 전달받은 각각의 rule들을 비교해가며 해당 property을 비교하여 type에 따라 정렬하게 된다.
isBigPriority에서는 for 반복문을 돌다가 정렬할 수 있는 상태(값이 동일하지 않은 상태)에는 return을 통해 첫 번째 우선순위만 비교하여 정렬을 하고, 만약 첫 번째 우선순위에서 정렬을 할 수 없다면 다음 rule로 넘어가 비교를 하게된다.
// mission.mjs
import { PriorityQueue as CpuScheduler } from "./priorityQueue.mjs";
const rules = [
{ property: "executionCount", type: "ASC" },
{ property: "cpuReturnCount", type: "DESC" },
];
class Process {
constructor(name, cpuReturnCount, executionCount) {
this.name = name;
this.cpuReturnCount = cpuReturnCount;
this.executionCount = executionCount;
}
}
let cpuScheduler = new CpuScheduler(rules);//priorityQueue.mjs
import { Heap } from "./heap.mjs";
export class PriorityQueue {
constructor(rules) {
this.heap = new Heap();
this.rules = rules;
this.heap.isBigPriority = (first, second) => {
for (const rule of this.rules) {
const { property, type } = rule;
if (type === "ASC") {
if (first[property] < second[property]) return true;
if (first[property] > second[property]) return false;
} else {
if (first[property] > second[property]) return true;
if (first[property] < second[property]) return false;
}
}
return false;
};
}
enqueue(data) {
return this.heap.insert(data);
}
dequeue(data) {
return this.heap.remove(data);
}
}미리 rules라는 배열을 선언하여 해당 변수 안에서 우선순위를 선택할 property와 type을 관리해주면 Process 나 PriorityQueue에서는 우선 순위의 변경이 발생하여도 수정을 할 필요가 없어진다. 현재는 rules를 직접 하드코딩하여 관리해주고 있는데 에러처리나 동적으로 삽입해줄 수 있는 메서드를 활용해봐도 좋을 것 같다.
회고
수강하면서 heap과 우선 순위큐를 직접 구현하고 이론을 설명들을 때는 이해가 되지 않는 부분이 많았는데, 이번 미션을 통해서 직접 어떤 상황에서 사용될 수 있는지 이해할 수 있었고 간접적으로 CPU의 우선순위를 구현해보면서 해당 자료구조의 이점을 몸소 체험할 수 있었다. 또한 문제를 풀면서 각각 내가 구현한 방식과 그에 대한 단점들을 발견하면서 이를 개선시키는 과정이 인상깊었던 것 같다.
댓글을 작성해보세요.
