[OS] CPU 스케줄링(FCFS, SJF, Priority, RR, 멀티레벨 큐) - 운영체제와 정보기술의 원리 6장

 

 

 

이번 정리 내용은 CPU 스케줄링!

그동안 각 스케줄링 알고리즘 자체만 이해하고 이걸 왜 하는지는 이해 못했는데 스터디 덕분에 드디어! 이해할 수 있게 되었다😁

 

운영체제는 학부생 때 전공과목으로 이수했지만 사실 반도 이해 못했던 것 같다.

이번에 스터디를 하면서 완벽하진 않지만 그 때 이해 못했던 부분까지 전체적인 그림을 이해할 수 있게 되었다. 역시 공부는 누군가의 강의를 듣는 것도 좋지만 내가 스스로 공부하는게 큰 도움이 되는 것 같다👍

 

 

 

 

1. CPU 스케줄링이란?

CPU 스케줄링을 이해하기 위해선 우선 컴퓨터 시스템의 명령 처리 프로세스를 이해할 필요가 있다.

 

CPU는 프로그램의 기계어 명령을 수행하는 컴퓨터 내의 중앙처리장치 이다. 프로그램이 메모리에 올라가면 프로그램 카운터(PC)라는 레지스터가 CPU에서 다음에 수행할 메모리 주소값을 가지고 있고, CPU는 매순간 PC가 가리키는 주소 공간의 명령을 하나씩 수행한다.

 

일반적으로 시분할 시스템에서는 여러 프로세스가 CPU를 공유하며 사용되므로 CPU는 효율적으로 관리되어야 한다.

 

 

 

CPU 스케줄링이 왜 필요할까?

사용자 프로그램이 수행되는 과정은 크게 CPU 작업과 I/O 작업의 반복이다. 사용자 프로그램이 CPU를 직접 할당받아 빠른 명령을 수행하는 단계를 CPU 버스트(burst)라고 하고, I/O 요청이 발생하여 CPU 제어권이 커널로 넘어가 입출력 작업을 진행하는 느린 단계를 I/O 버스트라고 한다.

 

프로세스에 따라 어떤 프로세스들은 CPU 버스트가 빈번한 CPU 바운드 프로세스일 수 있고, 어떤 프로세스는 I/O 요청이 빈번한 I/O 바운드 프로세스일 수 있다. 이처럼 프로세스마다 CPU 버스트시간이 균일하지 않기 때문에(CPU를 사용하는 시간이 모두 다름) 시분할 시스템에서 효율적인 CPU 관리를 위해 스케줄링 기법이 필요하다.

 

 

즉, 현대의 시분할 시스템에서는 여러 프로세스들이 동시에 실행되며 CPU를 공유하는데 각 프로세스마다 CPU 사용시간이 다르기 때문에 CPU를 효율적으로 관리하기 위해 CPU 스케줄링이 필요하다.

 

 

보통 프로세스들은 사용자에게 입력을 받아(I/O 작업) 빠르게 연산을 하고(CPU 작업) 결과를 출력하는(I/O 작업) 형태의 짧은 CPU 버스트를 가진다. 이 경우 사용자에 대한 빠른 응답이 중요하므로 CPU 스케줄링을 할 때는 CPU 버스트가 짧은 프로세스에게 우선으로 CPU를 사용할 수 있도록 하는 스케줄링이 필요하다.

 

 

 

CPU 스케줄러

준비 상태의 프로세스 중 어떤 프로세스에게 CPU를 할당할지 결정하는 OS의 코드.

 

CPU 스케줄러가 호출되는 경우

1) 실행 상태의 프로세스가 I/O 요청 등에 의해 봉쇄 상태로 바뀌는 경우(비선점)

2) 시분할 시스템에서 실행 상태의 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우(선점)

3) I/O 요청으로 봉쇄 상태 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하고 프로세스가 준비 상태로 바뀌는 경우(선점)

4) CPU에서 실행 상태의 프로세스가 종료되는 경우(비선점)

 

 

 

 

2. 스케줄링 성능 지표

1) 시스템 관점

* CPU 이용률(CPU utilization)

   전체 시간 중 CPU가 일을 한 시간의 비율. CPU의 휴면상태 시간을 최소화 하는 것이 스케줄링의 중요한 목표

* 처리량(Throughput)

   주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 끝마쳤는지(CPU 버스트를 완료한 프로세스의 수)

 

 

2) 사용자 관점

* 소요시간(turnaround time)

  프로세스가 CPU를 요청한 시점부터 CPU를 모두 사용하고 CPU 버스트가 끝날 때까지 걸린 시간(웨이팅 + 사용 시간)

* 대기시간(waiting time)

  CPU 버스트 기간 중 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합

  시분할 시스템에서는 하나의 CPU 버스트가 여러 번에 걸쳐서 완료될 수 있기 때문에 하나의 CPU 버스트를 끝내기 위해 준비큐에 들어가서 기다린 시간의 총 합 

* 응답시간(response time)

  준비 큐에 들어온 후 첫 번째 CPU를 획득하기까지 기다린 시간

  대화형 시스템에서 사용자 입장에서 가장 중요한 성능 척도

 

 

 

 

 

3. 스케줄링 기법

CPU 스케줄링 방식은 비선점형(nonpreemptive)와 선점형(preemptive) 방식으로 구분된다.

 

* 비선점형 방식 : CPU를 획득한 프로세스가 CPU를 스스로 반납할 때까지 다른 프로세스들이 CPU를 사용하지 못함

   ex) 위의 스케줄러가 호출되는 경우 중 1), 4)

* 선점형 방식 : 프로세스가 CPU를 아직 다 사용하지 못했더라도 강제로 빼앗을 수 있는 스케줄링 기법

   ex) 위의 스케줄러가 호출되는 경우 중 2), 3)

 

 

 

 

4. 스케줄링 알고리즘

1) 선입선출(FCFS: First-Come First-Served) - 비선점

프로세스가 준비 큐에 도착한 순서대로 CPU를 할당하는 방식

먼저 도착한 프로세스의 성격에 따라 평균 대기시간이 크게 영향을 받음.

 

 

ex) CPU 버스트가 긴 프로세스가 CPU 버스트가 짧은 프로세스보다 먼저 들어왔을 경우 평균 대기시간이 길어짐

 

FCFS 프로세스 버스트 시간

 

프로세스 도착 순서에 따른 평균 대기시간 비교

 

 

 

 

2) 최단작업 우선(SJT: Shortest-Job First) - 비선점, 선점

CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식

평균 대기 시간을 가장 짧게 하는 최적의 알고리즘이다.

 

비선점형, 선점형 두 가지로 구현될 수 있다.

비선점형 - 프로세스가 일단 CPU를 획득하면 CPU 버스트가 끝날 때까지 CPU를 뺏기지 않음

선점형 - 프로세스가 CPU를 획득했더라도 더 짧은 CPU 버스트를 가진 프로세스가 준비큐에 들어오면 CPU 버스트가 더 짧은 프로세스에게 CPU를 빼앗김. SRTF(Shortest Remaining Time First)라고도 부름

 

 

SJT 프로세스 도착시간/버스트시간

 

비선점/선점형 평균 대기시간 비교

 

 

 

SJF 방식의 한계

1) CPU 버스트가 짧은 프로세스가 계속 도착할 경우 CPU 버스트가 긴 프로세스가 계속해서 CPU를 할당 받지 못하고 우선순위에서 밀리는 기아현상 발생 위험

2) 현실적으로 프로세스의 CPU 버스트 시간을 미리 알 수 없기 때문에 아래의 공식을 이용하여 CPU 버스트 시간을 예측하고 예측치가 가장 짧은 프로세스에게 CPU를 할당

CPU 버스트 시간 예측 공식

 

 

 

 

3) 우선순위(Priority) 스케줄링 - 비선점, 선점

준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식.

우선순위 선정 방식은 다양하며, 만일 우선순위가 CPU 버스트 시간일 경우 SJF와 동일해진다.

 

우선순위 스케줄링의 한계

SJF 방식과 동일하게 우선순위가 높은 프로세스가 계속해서 도착할 경우 우선순위가 낮은 프로세스는 계속 기다려야 하는 기아현상이 발생할 수 있다 → 노화 기법을 사용하여 해결

 

* 노화(aging) 기법이란

기다리는 시간이 길어질 경우 프로세스의 우선순위를 조금씩 높여 시간이 지남에 따라 우선순위가 높아져 CPU를 할당받을 수 있도록 한다.

 

 

 

 

4) 라운드 로빈(Round Robin) 스케줄링 - 선점

학부 때 CPU 스케줄링에서 가장 먼저 외웠던 스케줄링 기법😁

일정한 할당시간(time quantum)을 두어 할당 시간이 지나면 타이머 인터럽트를 발생시켜 프로세스에게서 CPU를 빼앗아 다음 프로세스가 CPU를 할당받을 수 있도록 하는 기법.

일반적으로 SJF 방식보다 평균 대기시간은 길지만 응답시간은 더 짧다.

 

할당시간이 너무 길면 FCFS에 가까워지고, 할당시간이 너무 짧으면 프로세스가 빈번하게 교체되어 문맥교환 오버헤드가 커진다.

 

 

 

 

 

5) 멀티레벨 큐(multi-level queue)

준비 큐를 여러 개로 분할하여 관리하는 스케줄링 기법

 

성격이 다른 프로세스들을 별도로 관리하고 성격에 맞는 스케줄링을 적용하기 위해 준비 큐를 별도로 두며 일반적으로 전위 큐와 후위 큐로 분할하여 운영된다.

 

ex) 빠른 응답을 필요로 하는 대화형 작업의 경우 응답시간을 짧게 하기 위해 라운드 로빈(RR) 스케줄링을 사용

      계산 위주의 작업은 응답시간이 큰 의미를 가지지 않으므로 FCFS 스케줄링을 사용

 

멀티레벨 큐

 

 

멀티레벨 큐는 여러 개의 준비 큐 중 어떤 큐에 먼저 CPU를 할당할지 별도의 스케줄링이 필요하다.

큐 자체에 고정 우선순위를 두어서 우선수위가 높은 큐의 프로세스를 먼저 할당하는 방법과 타임 슬라이스 방식을 이용하여 각 큐에 적절한 비율의 할당 시간을 두어(ex: 전위 큐(80%), 후위 큐(20%)) CPU를 할당받을 수 있도록 하는 방법이 있다.