크래프톤 정글 week07, day53 - CPU 스케줄링 알고리즘, 잔디심기

CPU 스케줄링 알고리즘

• CPU 스케줄링은 다중 프로그램 환경에서 CPU의 사용 시간을 효율적으로 분배하기 위한 방법이다.
• 이를 통해 시스템의 성능을 최적화하고, 대기 시간을 최소화하며, CPU 사용률을 극대화하는 것이 목표이다.
• 알고리즘 종류

선입선출 스케줄링(First-Come, First-Served Scheduling - FCFS)

• 이 알고리즘은 먼저 도착한 프로세스부터 처리하는 알고리즘이다.
• 프로세스 실행 시간을 예측하기 쉽고 단순하고 공평하지만 CPU 버스트 시간이 긴 프로세스가 먼저 도착하면 다른 프로세스들은 긴 대기 시간을 감수해야 하는 ‘호흡성’ 문제가 발생할 수 있다.

최단 작업 우선 스케줄링(Shortest Job Next Scheduling- SJN)

• 이 알고리즘은 CPU 버스트 시간이 가장 짧은 프로세스부터 처리하는 알고리즘이다.
• 평균 대기 시간을 최소화 할 순 있지만, CPU 버스트 시간을 미리 알 수 없기 때문에 예측에 의존하게 된다.

우선순위 스케줄링(Priority Scheduling)

• 이 알고리즘은 각 프로세스에 우선순위를 부여하고, 우선 순위가 높은 프로세스부터 처리한다.
• 하지만 우선순위가 낮은 프로세스가 계속 대기 상태에 머무르는 ‘기아’ 상태가 발생할 수 있다.

라운드 로빈 스케줄링(Round Robin Scheduling - RR)

• 이 알고리즘은 각 프로세스에게 동일한 시간 할당량(타임 퀀텀)을 부여하고, 그 시간 동안만 CPU를 사용하도록 한다.
• 모든 프로세스가 공평하게 CPU를 사용할 수 있어 멀티 프로그래밍 환경에 적합하다.

다단계 큐 스케줄링(Multilevel Queue Scheduling)

• 이 알고리즘은 프로세스를 여러 대기열로 분류하고, 각 대기열에 다른 스케줄링 알고리즘을 적용한다.
• 프로세스가 시스템에 도착하면 우선적으로 가장 높은 우선순위를 가진 큐 대기열에 배치된다.
• 그리고 주어진 시간동안 작업을 완료하지 못했을 시 한 단계 낮은 우선순위의 대기열로 이동하게 된다.

최단 잔여 시간 우선 스케줄링(Shortest Remaining Time First, SRT)

• SJN 방식을 선점 스케줄링 방식으로 변경한 기법
• 실행중인 프로세스보다 남은 처리 시간이 짧은 프로세스가 들어오면 실행 중인 프로세스를 중단하고 교체한다.
• 평균 대기 시간이 가장 짧은 알고리즘이지만, 기본적으로 선점형 방식이기 때문에 잦은 Context Switching이 일어나고 그에 따른 오버헤드가 커진다.
  • 기아 현상도 더 심하게 발생할 수 있다.

다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)

• 다단계 큐 스케줄링 방식에 aging기법을 적용한 방식이다.
• 우선순위가 변동되기 때문에 프로세스가 큐 사이의 이동이 가능하다.
• I/O 중심의 프로세스와 대화형 프로세스들은 높은 우선순위의 큐에 넣는다.
• CPU를 좀 더 오랫동안 사용하게 해주기 위해, 우선순위가 높은 큐보다 낮은 큐에 타임퀀텀 크기를 크게 해준다.

 

버스트(Burst)

• CPU 스케줄링에서 중요한 개념이며 CPU 버스트와 I/O 버스트 두 가지 주요 형태가 있다.
• CPU 버스트
  • 프로세스가 CPU를 연속적으로 사용하는 시간을 의미하며, 연산이나 명령 실행과 같은 작업을 수행하는데 필요한 시간을 나타낸다.
  • CPU 버스트의 길이는 프로세스마다 다르며, 이를 기반으로 CPU 스케줄링 알고리즘이 작업 순서를 결정하게 된다.
• I/O 버스트
  • 프로세스가 입출력 작업을 수행하는 데 걸리는 시간을 의미하며, 디스크 액세스, 네트워크 통신과 같은 I/O 작업을 수행하는데 필요한 시간을 나타낸다.
  • I/O 버스트 동안에는 CPU가 다른 프로세스를 실행할 수 있으므로, 다른 프로세스에서 CPU 버스트를 처리할 수 있다.

 

호흡성 문제(convoy effect)

• 특히 선입선출 알고리즘에서 주로 발생하는 CPU 스케줄링 문제이다.
• CPU 버스트 시간이 긴 프로세스가 먼저 CPU를 점유하게 되면, 그 뒤에 대기하고 있는 CPU 버스트 시간이 짧은 프로세스들이 불필요하게 오랫동안 대기해야 하는 상황을 말한다.
  • 이로 인해 전체적인 시스템 효율이 저하되며, 평균 대기 시간이 증가하게 된다.

 

기아 상태(Starvation)

• 운영체제에서 특정 프로세스가 필요한 자원을 무한정 기다리고 있지만, 다른 프로세스들이 계속해서 그 자원을 점유하고 있어서 원하는 작업을 수행할 수 없게 되는 상태를 말한다.
• 기아 상태는 특히 우선순위 스케줄링에서 발생할 수 있으며, 우선순위가 높은 프로세스가 계속 도착하게 되면, 낮은 우선순위를 가진 프로세스는 CPU를 사용할 기회를 얻지 못하고 무한히 기다리게 될 수도 있다.
  • 기아 상태를 해결하기 위한 방법 중 하나는 **에이징(Aging)**이 있다.

 

에이징(Aging)

• 프로세스가 시스템에서 대기하는 시간이 길어질수록 그 프로세스의 우선순위를 점차 높여주는 방법이다.
• 이를 통해 모든 프로세스가 언젠가는 CPU를 사용할 수 있는 기회를 얻게 되어 기아 상태를 방지할 수 있다.

 

타임퀀텀(Time Quantum)

• 운영체제에서 프로세스 스케줄링에 사용되는 시간 단위를 의미하며, 특히 라운드 로빈 스케줄링에서 중요한 역할을 한다.
• 타임 퀀텀의 길이는 너무 짧으면, 프로세스 간에 자주 전환되어 오버헤드가 증가하게 되고, 반대로 너무 길면, 특정 프로세스가 CPU를 오랫동안 점유하게 되어 다른 프로세스들이 불필요하게 대기하는 상황이 발생할 수 있다.
  • 따라서 적절한 타임퀀텀의 설정이 필요하다.

 

Q&A

Q. 기아 상태와 호흡성 문제의 차이

A. 기아 상태는 프로세스가 자원을 아예 할당받지 못하는 상태를 의미하고, 호흡성 문제는 프로세스가 자원을 할당 받는데 필요한 대기 시간이 길어지는 상태를 의미한다.

 

Q. 라운드 로빈의 선입 방식

A. 우선 순위가 아닌 시스템에 도착한 순서대로 처리한다.

 

Q. 선점과 비선점의 차이

A. 선점형과 비선점형은 프로세스 스케줄링에서 사용되는 두 가지 주요 방법이다.

• 선점형 스케줄링
  • 한 프로세스가 CPU를 점유하고 있을 때, 우선순위가 더 높은 다른 프로세스가 도착하면 현재 프로세스를 중단하고 새로운 프로세스를 실행할 수 있다.
  • 이 방식은 실시간 운영체제에서 많이 사용되며, 라운드 로빈 스케줄링이나 최단시간 우선 스케줄링 같은 알고리즘에서 사용된다.
• 비선점형 스케줄링
  • 한 프로세스가 CPU를 점유하게 되면, 그 프로세스는 작업을 완료하거나 자발적으로 CPU를 반납하기 전까지 CPU를 계속 사용하게 된다.
  • 이 방식은 프로세스의 실행을 중단하고 다시 시작하는 오버헤드를 줄일 수 있지만, 우선순위가 높은 프로세스가 도착했을 때 즉시 처리하지 못하는 단점이 있다.
  • 선입선출 스케줄링이나 최단작업 우선 스케줄링 같은 알고리즘에서 사용된다.

 

Q. 스케줄링으로 프로세스만이 아닌 쓰레드도 적용이 되는가

A. 쓰레드들도 CPU의 사용을 경쟁하기 때문에, 어떤 쓰레드를 먼저 실행할 지 결정하는 스케줄링이 필요하다. 그래서 CPU 뿐만 아니라 쓰레드에도 적용이 된다.

• 프로세스 단위 스케줄링
  • 일부 운영체제에서는 프로세스를 스케줄링의 기본 단위로 사용하며, 하나의 프로세스 내에서 여러 쓰레드가 동시에 실행될 수 있다. 이 경우, 프로세스 스케줄링이 먼저 이루어진 후, 각 프로세스 내부에서 쓰레드 스케줄링이 이루어진다.
  • 이 말은 프로세스를 실행 단위로 보며, 프로세스 안에 여러 개의 쓰레드가 있고 쓰레드가 다 실행되면 다음 프로세스로 이동하며 순차적으로 실행된다.
• 쓰레드 단위 스케줄링
  • 다른 운영체제에서는 쓰레드를 스케줄링의 기본단위로 사용하며, 이 경우, 각 쓰레드는 독립적으로 스케줄링되며, 프로세스 경계를 넘어서 스케줄링이 이루어진다.
  • 이 말은 쓰레드를 독립적인 실행 단위로 보며, 프로세스 별로 쓰레드가 개별적으로 실행된다.

 

---

오늘의 잔디심기

백준

30701

자바스크립트

실버3

돌아온 똥게임

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().split("\n");

const comback_ddongGame = () => {
    let [N, D] = input[0].split(" ").map(Number);
    let kunhoPower = D;
    let battleRoom = [];
    let weaponRoom = [];
    let clearRoom;

    for(let i = 1; i <= N; i++) {
        let [type, x] = input[i].split(" ").map(Number);
        if(type == 1) {
            battleRoom.push(x);
        } else {
            weaponRoom.push(x);
        }
    }

    battleRoom.sort((a, b) => a - b);
    weaponRoom.sort((a, b) => a - b);

    clearRoom = weaponRoom.length;
    while (battleRoom.length > 0) {
        while (weaponRoom.length > 0 && kunhoPower <= battleRoom[0]) {
            kunhoPower *= weaponRoom.shift();
        }
        if (kunhoPower > battleRoom[0]) {
            clearRoom++;
            kunhoPower += battleRoom.shift();
        }
        else break;
    }
    console.log(clearRoom);
}

comback_ddongGame();

 

 

학습 시간 : 10 ~ 25시