[운영체제] 스케줄링 Scheduling

스케줄링이란?

"여러 프로세스가 실행될 때 제한된 자원(CPU, 메모리, I/O 장치 등)을 효율적으로 사용하기 위해 작업(task)이나 프로세스(process)의 실행 순서를 정하는 기법"

여러 자원을 활용하기 위한 스케줄링 방법이 있지만 다음은 그 중 운영체제 CPU 스케줄링을 정리하는 내용이다.

 

스케줄링 종류

스케줄링 종류는 크게 3가지로 나뉜다.

1. 장기 스케줄링 (Long-Term Scheduling)

• 어떤 프로세스를 메모리에 올릴지 결정하는 단계
• 주로 배치 시스템에서 사용되며, CPU가 과부하되지 않도록 적절한 프로세스 개수를 유지

2. 중기 스케줄링 (Medium-Term Scheduling)

• 실행중인 프로세스를 일시적으로 중단(suspend)하거나 다시 실행하도록 결정
• 메모리 부족 시 일부 프로세스를 디스크로 보내는 스와핑(swaping)과 관련

3. 단기 스케줄링 (Short-Term Scheduling, CPU 스케줄링)

• 현재 실행 중인 프로세스를 관리하며, 어떤 프로세스가 CPU를 사용할지 결정
• ex) FCFS, SJF, RR, Priority, Mulit-Level Queue 등

 

프로세스(Process)란?

프로세스는 컴퓨터에서 실행 중인 프로그램을 말한다. 하나의 CPU는 한 번에 하나의 프로세스만 실행시킬 수 있으므로, 어떻게 프로세스를 배분할지가 중요하다.
운영체제에서 프로세스는 다음과 같은 상태를 가지고, 이 과정에서 스케줄링이 필수적으로 개입한다.

 

어떤 프로세스 상태에 어느 스케줄링이 필요한가?

운영체제에서 하나의 프로세스는 다음과 같은 상태를 가진다. 이 과정에서 스케줄링이 필수적으로 개입한다.

1. New (생성)
  - 프로세스가 생성되었지만 아직 실행되지 않은 상태
  - 운영 체제는 어떤 프로세스를 실행할지 결정해야 한다. → 장기 스케줄러 필요

2. Ready (준비)
  - CPU를 사용할 수 있기를 기다리는 상태
  - CPU가 여러 개의 프로세스 중 어느 것을 실행할지 결정해야 한다. → 단기 스케줄러 필요

3. Running (실행)
  - 프로세스가 CPU를 할당받아 실행되는 상태
  - 스케줄러가 없으면 한 프로세스가 CPU를 독점하여 다른 프로세스가 실행될 기회를 얻지 못할 수도 있다. → CPU 스케줄링을 통해 공정한 분배가 필요하다.

4. Waiting (대기)
  - 프로세스가 입출력(I/O) 작업을 수행하기 위해 기다리는 상태
  - 입출력 작업이 끝난 후 다시 CPU를 사용해야 한다. → 스케줄러가 CPU 재할당을 결정

5. Terminated (종료)
  - 프로세스 실행이 완료된 상태

위처럼 프로세스의 상태가 변할 때마다 운영체제가 어떤 프로세스를 실행할지 결정하는 역할을 하는 것이 스케줄링이다.
3(실행) → 4(대기) 상태로 전환(switching) 되거나, 5(종료)될 때만 스케줄링이 발생하는 것을 비선점형(non-preemptive) 스케줄링이라고 하고, 그 외 모든 스케줄링은 선점형(preemitive) 스케줄링이라고 한다.

 

왜 프로그램을 실행시키는데 스케줄링이 필요한가? (스케줄링의 이점)

1. CPU 자원을 효율적으로 활용하기 위해
   • CPU는 한 번에 하나의 프로세스만 실행할 수 있기 때문에 여러 개의 프로세스를 번갈아 실행해야 한다.
   • 만약 스케줄링이 없다면 한 프로세스가 CPU를 독점하여 다른 프로세스가 실행되지 못하는 등과 같은 문제가 발생할 수 있다.
2. 사용자 응답 속도를 빠르게 하기 위해
   • 라운드 로빈(Round Robin)과 같은 스케줄링 방식을 통해 각 프로세스의 짧은 시간 동안 CPU를 할당하여 빠르게 실행된다.
   • 사용자가 키보드를 입력하면 해당 작업이 즉시 반응해야 하기 때문에 스케줄링은 필수적이다.
3. 우선순위가 높은 작업을 먼저 실행하기 위해
   • 모든 작업은 동등하지 않다. 예를 들어 금융 거래 시스템 등 당장 실행시켜야 하는 작업이 있다면 먼저 실행해야 한다.
4. 다중 프로세스 환경에서 공정한 실행을 보장하기 위해
   • 여러 사용자가 동시에 프로그램을 실행하면 운영체제는 모든 사용자가 CPU를 공평하게 사용할 수 있도록 해야 한다.
   • 시분할 시스템에서는 라운드 로빈과 같은 스케줄링을 사용하여 일정 시간마다 다른 프로세스로 교체한다.
5. 교착 상태(Deadlock)를 방지하기 위해
   • 특정 프로세스가 계속 기다리면서 CPU를 할당받지 못하면 데드락이 발생할 수 있다.
   • 스케줄러가 적절히 프로세스의 실행 순서를 조정하여 이런 문제를 해결할 수 있다.

 

다음은 이 중 단기 스케줄링인 CPU 스케줄링의 종류를 정리한 내용이다.

---

스케줄링 평가 항목

효율적인 스케줄링을 평가하기 위해 다음과 같은 평가 항목을 고려할 수 있다.

대기 시간 (Waiting Time)
프로세스가 CPU를 할당받지 못하고 Ready Queue에서 기다리는 총 시간 →낮을 수록 좋다. 즉, 오래 기다리지 않고 실행될 수록 좋은 성능임을 의미한다.

(대기 시간) = (총 실행 시간 - 실제 CPU 사용 시간)
Waiting Time = Turnaround Time − Burst Time

반환 시간 (Turnaround Time)
프로세스가 생성된 순간부터 종료될 때까지 걸린 총 시간 →낮을 수록 좋다. 즉, 프로세스가 빨리 끝날 수록 사용자는 더 좋은 경험을 한다.

(반환 시간) = (작업 완료 시간) - (작업이 시스템에 도착한 시간)
T_turnaround = T_completion - T_arrival

응답 시간 (Response Time)
프로세스가 실행을 요청한 후 처음으로 CPU를 할당받을 때까지 걸리는 시간
즉, 사용자가 키보드를 눌렀을 때 화면에 반응이 나타날 때까지의 시간 → 당연히 짧을 수록 좋다.

(응답 시간) = (작업 도착 시간) - (작업 처음 스케줄되는 시간)
T_response = T_firsturn - T_arrival

 

CPU 스케줄링

스케줄링은 우선 크게 비선점형과 선점형 스케줄링으로 나뉜다. 앞서 프로세스의 상태 변화를 정리할 때
"3(실행) → 4(대기) 상태로 전환(switching) 되거나, 5(종료)될 때만 스케줄링이 발생하는 것을 비선점형(non-preemptive) 스케줄링이라고 하고, 그 외 모든 스케줄링은 선점형(preemitive) 스케줄링이라고 한다."
와 같이 언급하였다. 그 비선점형과 선점형이 뭔지 알아보고 각 스케줄링 방식에 어떤 스케줄링이 있는지 알아보자

비선점형 스케줄링 알고리즘

어떤 프로세스가 CPU를 점유하고 있을 때 이를 뺏을 수 없는 스케줄링을 비선점형 스케줄링이라고 말한다. 
따라서 강제로 프로세스를 종료하지 않고 한 번 프로세스가 실행되며 종료될 때까지 CPU를 선점하고 있다.
이는 문맥 교환(Context Switching)으로 인한 부하가 상대적으로 적다는 장점이 있지만, 프로세스 배치에 따라 효율성 차이가 많이 나게 된다. 

 

(1) FCFS (First Come, First Served) = FIFO (First In, First Out)

먼저 도착한 프로세스가 먼저 실행되는 스케줄링 방식이다. 큐 알고리즘을 떠올릴 수 있다. (선착순)

단순하고 공정하지만 Convoy Effect(호위 효과)가 발생할 수 있다.
Convoy Effect란, 실행시간이 긴 프로세스를 우선적으로 처리하게 되면 다른 프로세스들이 대기하는 기간이 길어져 전체적은 효율이 떨어지는 상황을 의미한다.

결국 단점은 앞에 긴 프로세스가 오더라도 끝날 때까지 기다려야 함으로, 대기 시간이 기다릴 수 있다는 점이다.

 

(2) SJF (Shortest Job First, 최단 작업 우선)

마트 계산대에서 줄을 섰을 때, 앞 사람이 물건이 많을 때 뒤에 물건을 적게 계산하려는 사람이 있다면, 뒤 사람을 먼저 계산하는 것이 효율적이라는 생각이 든다.
예와 같이 실행 시간이 짧은 프로세스를 먼저 실행하는 스케줄링 방식이다.

평균 대기 시간이 짧아 효율적이지만 짧은 스케줄링을 계속 먼저 하게 되면 긴 시간을 필요로 하는 프로세스의 우선순위가 계속 밀려 실행되지 못하고 무기한 대기하게 되는 기아(starvation) 현상이 일어날 수 있다.
그리고 실제로는 프로세스의 CPU 실행 시간을 예측하기 어렵다는 문제가 존재한다.

 

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

프로세스마다 우선순위를 부여하고, 높은 우선순위를 가진 프로세스를 먼저 실행하는 스케줄링 방식이다.

SJF 스케줄링의 경우 낮은 우선 순위의 프로세스가 실행되지 않아 기아 문제가 발생할 수 있다. 이러한 문제를 해결하기 위해 시간이 지나면 우선순위를 자동으로 증가시켜주는 노화(Aging) 기법을 사용한다.

 

선점형 스케줄링 알고리즘

어떤 프로세스가 CPU를 할당받아 실행 중이더라도 더 높은 우선 순위의 프로세스가 등장하면 운영체제가 알고리즘에 따라 강제로 중단시키고 다른 프로세스를 CPU에 할당할 수 있는 스케줄링 방식이다.

(1) SRTF (Shortest Remaining Time First, 최단 남은 시간 우선)

실행 중인 프로세스보다 더 짧은 실행 시간을 가진 프로세스가 도착하면 현재 프로세스를 중단하고 새 프로세스를 실행하는 방식이다.

SJF의 선점형 방식으로, SJF와 같이 평균 대기 시간을 줄일 수 있지만 다음 프로세스의 CPU 실행 시간을 예측하는 것이 어렵다는 문제가 있다.
마찬가지로 실행 시간이 짧은 작업이 먼저 끝나 효율적이지만, 짧은 프로세스가 계속 우선순위를 선점하여 긴 프로세스가 대기만하다 실행되지 못하는 기아 현상이 발생할 수 있다.
또한 높은 빈도의 문맥 교환(Context Switching)이 발생할 수 있다.

 

(2) 라운드 로빈 (RR, Round Robin)

각 프로세스에 동일한 시간(타임 슬라이스)을 할당하여 순차적으로 실행하는 방식이다.

모든 프로세스가 일정 시간 동안 CPU를 사용 가능하여 공정성을 보장하지만, 너무 짧은 타임 슬라이스를 설정하면 문맥 교환(Context Switching)이  많이져 오버헤드가 발생할 수 있다는 단점이 있다.
또한 적절한 타임 슬라이스를 설정하는 것에 있어 어려움이 있다.

 

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

우선순위가 높은 프로세스가 도착하면 현재 실행 중인 프로세스를 중단하고 실행하는 방식이다.

비선점형 우선순위 스케줄링과 달리 더 높은 우선순위의 작업이 오면 기존 작업을 중단한다.
긴급한 작업을 즉시 실행할 수 있지만 기아 현상이 발생할 수 있다.

 

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

프로세스를 여러 개의 우선순위 큐로 나누고, 각각 다른 방식으로 스케줄링을 적용하는 방식이다.
예를 들어, 시스템 프로세스, 대화형 프로세스, 배치 프로세스 등으로 구분하고 각 큐에 다른 스케줄링 방식 적용한다.

 

낮은 우선순위 큐는 높은 우선순위 큐가 비어있어야 실행 가능하기 때문에 낮은 큐의 프로세스가 처리되지 않는 기아 현상이 발생할 수 있으며, 각 큐 사이에서 프로세스들이 이동할 수 없어 유연성이 떨어지는 특징이 있다.

 

Reference

https://velog.io/@qq7455/CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9A%94%EC%95%BD%EC%A0%95%EB%A6%AC

CPU 스케줄링 알고리즘 요약정리