프로세스 스케줄링

🧐 운영체제는 CPU를 어떻게 프로세스에 분배할까?

모든 프로세스는 CPU를 사용하고 싶어해요. 운영체제는 공정하고 합리적으로 CPU를 프로세스에게 할당해 주어야 합니다.

CPU 스케줄링 : 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것

CPU를 스케줄링은 컴퓨터 성능과 직결되는 대단히 중요한 문제에요! 😊

프로세스 우선순위

CPU를 사용하고 싶은 프로세스가 넘쳐나고 있는 상황…

먼저 CPU를 사용하겠다고 한 프로세스에게 할당하는 것은 좋지 않아요 ❌

프로세스마다 우선순위가 다르기 때문입니다.

💡 우선 순위가 높은 프로세스의 예
: 입출력 작업이 많은 프로세스
: 실시간 프로세스
: 일부 백그라운드 프로세스

🤔 왜 입출력 작업이 많은 게 우선순위가 높을까?

이를 이해 하기 위해서는 프로세스가 어떤 과정을 거치면서 실행되는지 알아야 해요

대부분의 프로세스들은 CPU와 입출력장치를 모두 사용하며 실행됩니다.

실행 상태와 대기 상태를 반복하면서 실행되죠.

그런데! 프로세스 종류마다 입출력장치를 이용하는 시간, CPU를 이용하는 시간에 차이가 있어!

입출력 집중 프로세스

: 비디오 재생, 디스크 백업 작업과 같이 입출력 작업이 많은 프로세스
입출력 버스트가 많은 프로세스

CPU 집중 프로세스

: 복잡한 수학 연산, 컴파일, 그래픽 처리 작업과 같이 CPU 작업이 많은 프로세스
CPU 버스트가 많은 프로세스

➡️ 각 프로세스 특징이 다른데 모두 동일한 빈도로 CPU를 사용하는 것은 비합리적이야 😒

따라서, 모든 프로세스가 CPU를 차례대로 돌아가며 사용하는 것보다는 각각의 상황에 맞게 CPU를 배분하는 것이 더 효율적이에요 😊

💡 운영체제는 각 프로세스의 PCB에 우선순위를 명시하고, 그 우선순위를 기준으로 먼저 처리할 프로세스를 결정한다.

스케줄링 큐

PCB에 우선순위가 적혀 있다고는 하지만, 운영체제가 CPU를 사용할 다음 프로세스를 일일이 찾는 것은 비효율적이다.

🤩 운영체제는!
프로세스들에게 “줄을 서서 기다릴 것”을 요구해요 💂

이 줄을 스케줄링 큐로 구현하고 관리합니다. 자원을 사용하려는 프로세스 별로 줄을 세워요

이 큐에는 다양한 종류가 있다. 대표적으로는 준비 큐(ready queue), 대기 큐(waiting queue)가 있다.

• 준비 큐 : CPU를 이용하고 싶은 프로세스들이 서는 줄
• 대기 큐 : 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄

😛 우선순위는 어떻게 판별하지?
준비 상태의 프로세스의 PCB는 준비 큐의 마지막에 삽입되어서 CPU 사용 차례를 기다려요.
운영체제는 큐에 삽입된 순서대로 하나씩 꺼내서 실행하되, 그 중 우선순위가 높은 것부터 실행해요.
우선순위가 낮은 프로세스가 먼저 큐에 들어왔어도 우선순위가 높은 프로세스가 먼저 처리될 수 있어요

입출력이 완료되어 완료 인터럽트가 발생하면…
운영체제는 대기 큐에서 완료된 PCB를 준비 상태로 변경하고, 대기 큐에서 제거합니다.
해당 PCB는 준비 큐로 이동하겠죠?

선점형과 비선점형 스케줄링

❗ 만약 운영체제가 어떤 프로세스에 CPU 사용을 허락하여 사용하고 있는데 갑자기 다른 급한 프로세스가 CPU를 지금 당장 사용하길 요청하고 있다면?

방법은 두가지 😖

• CPU를 사용 중인 프로세스로부터 빼앗아서 할당해주기
• CPU를 사용 중인 프로세스 작업이 끝날 때까지 급한 프로세스가 기다리기

선점형 스케줄링

: 운영체제가 프로세스로부터 자원을 강제로 빼앗아서 다른 프로세스에 할당하는 방식

• 장점
  • 프로세스의 독점을 막고 프로세스들에 골고루 자원을 배분 할 수 있다.
• 단점
  • 문맥 교환 과정에서 오버헤드가 발생할 수 있다.

비선점형 스케줄링

: 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지는 다른 프로세스가 끼어들 수 없는 방식

• 장점
  • 문맥 교환에서 발생하는 오버헤드가 선점형 보다 적다.
• 단점
  • 모든 프로세스가 골고루 자원을 사용할 수 없다.

스케줄링 알고리즘의 종류

선입 선처리 스케줄링(FCFS 스케줄링)

: 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식

때로는 프로세스들이 기다리는 시간이 매우 길어질 수 있다.
만약, CPU를 오래 사용하는 프로세스가 먼저 들어오면 다른 프로세스들은 무작정 기다린다.
➡️ 호위 효과(convoy effect)

최단 작업 우선 스케줄링(SJF 스케줄링)

: CPU 이용 시간의 길이가 짧은 프로세스부터 실행하는 스케줄링 방식

선점형, 비선점형 둘로 모두 구분될 수 있다.

라운드 로빈 스케줄링

선입 선처리 스케줄링 + 타임 슬라이스

: 정해진 타임 슬라이스만큼의 시간 동안 돌아가면서 CPU를 이용하는 선점형 스케줄링 방식

타임 슬라이스가 지나치게 크면 선입 선처리 스케줄링과 다를게 없어 호위 효과 발생 가능
타임 슬라이스가 지나치게 작으면 문맥 교환 발생이 많아진다.

최소 잔여 시간 우선 스케줄링(SRT 스케줄링)

최단 작업 우선 스케줄링 + 라운드 로빈 알고리즘

: 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시작이 가장 적은 프로세스를 선택하는 방식

우선 순위 스케줄링

: 가장 높은 우선순위를 가진 프로세스부터 실행 하는 스케줄링 방식

우선순위가 같으면 선입 선처리로 스케줄링 한다.
우선 순위가 높은 프로세스만 계속 먼저 실행되어서 우선순위가 낮은 프로세스의 실행이 계속해서 연기될 수 있다.
➡️ 기아(starvation) 현상

🧐 기아 현상을 방지하기 위해서는 어떻게 하지?

에이징(aging) : 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식

다단계 큐 스케줄링

우선순위 스케줄링의 발전된 형태

: 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식

우선순위가 가장 높은 큐를 먼저 처리하고, 큐가 비면 그 다음 우선순위 큐를 처리한다.
프로세스 유형별로 우선순위를 구분해서 실행하는 것이 편리해진다.
큐별로 타임 슬라이스를 여러 개 지정할 수 있고, 큐별로 다른 스케줄링 알고리즘을 사용할 수 있다.

다단계 피드백 큐 스케줄링

💡 가장 일반적인 CPU 스케줄링 알고리즘이에요

다단계 큐 스케줄링의 발전된 형태

: CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 낮은 우선순위 큐에서 너무 오래기다리면 높은 우선순위 큐로 이동시키는 알고리즘

프로세스들이 큐 사이를 이동할 수 있다.
새롭게 프로세스가 들어오면 우선순위가 가장 높은 큐에 삽입되고 타임 슬라이스 동안 실행한다.
해당 큐에서 실행이 끝나지 않으면 다음 우선순위 큐에 삽입되어 실행된다.
➡️ CPU를 오래 사용해야 하는 CPU 집중 프로세스들은 자연스럽게 우선순위가 낮아진다.
만약, 낮은 우선순위 큐에서 너무 오랫동안 기다리고 있으면 우선순위가 높은 큐로 이동시키는 에이징 기법으로 기아 현상을 예방한다.