컴퓨터 구조 파헤치기 ... (CPU 스케줄링)

CPU 스케줄링

CPU 스케줄링은 언제 어떤 프로세스에 CPU를 할당할지 결정하는 작업이라고 할 수 있습니다.

이 때, CPU 스케줄러는 메모리에 있는 프로세스들 중 어떤 프로세스를 실행할지 선택하고 CPU를 할당해주는 역할을 합니다.

CPU 스케줄러는 프로세스들이 다음과 같은 상황에 있을 때 스케줄링을 결정한다.

1. 실행(running) 상태에서 대기(waiting) 상태로 전환(switching)될 때 ( ex : I/O 발생 )
2. 실행(running) 상태에서 준비(ready) 상태로 전환(switching)될 때 ( ex : intterupt 발생 )
3. 대기(waiting) 상태에서 준비(ready) 상태로 전환(switching)될 때 ( ex : I/O 완료 시 )
4. 종료(Terminated)될 때

1번과 4번 상황에서만 스케줄링이 발생하는 것을 비선점형(non-preemptive) 스케줄링이라고 하고,

이외의 모든 스케줄링은 선점형(preemptive) 스케줄링이라고 합니다.

CPU 스케줄러

위에서 언급한 대로 CPU 스케줄러는 프로세스를 선택하고 CPU를 할당해주는 역할을 합니다.

그렇다면 스케줄러의 종류는 무엇이 있을까요?

스케줄러는 장기, 중기, 단기 3가지 종류가 있습니다.

• 장기
  • 어떤 프로세스를 준비 큐에 삽입할지 결정합니다. (메모리와 디스크 사이의 스케줄링을 담당) 디스크에서 하나의 프로그램을 가져와 커널에 등록하면 프로세스가 되는데, 이때 디스크에서 어떤 프로그램을 가져와 커널에 등록할지(준비 큐에 등록할지) 결정합니다.
  • 프로세스의 상태 : new -> ready (in memory)
• 중기
  • 너무 많은 프로세스에게 메모리를 할당해서 시스템의 성능이 저하되는 경우 이를 해결하기 위해 메모리에 적재된 프로세스의 수를 동적으로 조절하기 위해 추가된 스케줄러
  • 프로세스의 상태 : ready -> suspended
• 단기
  • 준비 상태의 프로세스 중에서 어떤 프로세스를 다음 순서로 실행할 것인지 결정 (cpu와 메모리 사이의 스케줄링을 담당)
  • 프로세스의 상태 : ready -> running -> waiting -> ready

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

CPU 스케줄링은 선점형 스케줄링 방식과 비선점형 스케줄링 방식으로 나뉩니다.

선점형 스케줄링과 비선점형 스케줄링의 차이점을 보면 아래와 같습니다.

• 선점형 스케줄링
  • 실행중인 프로세스나 스레드를 강제로 중단시키고 다른 프로세스를 실행시킵니다.
  • 프로세스가 CPU를 독점 할 수 없어 대화형이나 시분할 시스템에 적합합니다.
  • 컨텍스트 스위칭 오버헤드가 많습니다.
• 비선점형 스케줄링
  • 실행 상태에 있는 작업이 완료될 때까지 다른 작업이 불가능합니다.
  • 작업량이 적고 컨텍스트 스위칭 오버헤드가 적습니다.
  • 기다리는 프로세스가 많아 처리율이 떨어집니다.

기아 상태

특정 프로세스의 우선 순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태를 뜻합니다.

기하 상태인 프로세스는 자원을 할당 받기 위해 무한히 대기 중입니다.

기아 상태는 시스템의 공정성 문제를 초래할 수 있습니다.

그렇다면 기아 상태를 해결하려면 어떻게 해야 할까요?

기아 상태를 해결하기 위한 방법은 많지만 대표적인 4가지 방법을 소개하겠습니다.

1. 에이징(Aging):
   • 에이징은 우선순위를 가진 스케줄링 알고리즘에서 주로 사용됩니다.
   • 대기 중인 프로세스의 우선순위를 점진적으로 증가시켜 오랫동안 대기한 프로세스가 실행될 수 있도록 합니다.
   • 이 방법은 오랜 시간 동안 대기한 프로세스의 우선순위를 높여 기아 상태를 예방합니다.
2. 라운드 로빈(Round Robin) 스케줄링:
   • 모든 프로세스에 동일한 실행 시간 할당량(time quantum)을 부여하여 공정하게 CPU 시간을 할당합니다.
   • 각 프로세스는 자신의 할당량만큼 실행된 후, 다음 프로세스에게 CPU를 양보합니다.
   • 이 방법은 각 프로세스에 일정한 시간을 할당함으로써 기아 상태를 예방합니다.
3. 피드백 큐(Feedback Queue) 스케줄링:
   • 여러 개의 대기 큐를 사용하고, 프로세스가 각 큐에서 얼마나 대기해야 하는지에 따라 우선순위를 조정합니다.
   • 오래 대기한 프로세스는 높은 우선순위의 큐로 이동되어 기아 상태를 방지합니다.
4. 자원 요청과 할당 전략 변경:
   • 기아는 리소스 경쟁 때문에 발생할 수 있습니다.예를 들어, 여러 리소스를 동시에 요청하는 대신 하나씩 순차적으로 요청할 수 있습니다.
   • 특정 리소스에 대한 요청 전략을 변경하여 기아 상태를 방지하거나 완화할 수 있습니다.

스케줄링 알고리즘

CPU 스케줄링은 다양한 알고리즘 방식을 사용하고 있습니다.

대표적인 몇 가지 알고리즘을 소개해드리려고 합니다.

 

1. 선입선출 스케줄링 (FCFS)

먼저 요청한 프로세스가 먼저 자원을 제공받으며 이미 사용중이라면 사용이 끝날때까지 기다려야하는 스케줄링 방식입니다.

• 장점
  • 스케줄링의 이해와 구현이 단순하다.
  • 준비 큐에 있는 모든 프로세스가 결국 실행되므로 기아 없는 공정한 정책이다.
  • 프로세서가 지속적으로 유용한 프로세스를 수행하여 처리율이 높다
• 단점
  • 비선점 방식이므로 대화식 프로세스에는 부적합하다.
  • 장기 실행 프로세스가 있으면 뒤에 있는 모든 프로세스를 대기시켜 평균 대기 시간이 길어지며 최악의 대기시간이 될 수 있다.
  • 긴 프로세스가 실행되는 동안 짧은 프로세스가 긴 대기시간으로 호위효과가 발생할 수 있다.

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

프로세스의 실행 시간을 이용하여 가장 짧은 시간을 갖는 프로세스가 먼저 자원을 할당받는 방식입니다.

이 방식은 선점할 수도 있는 스케줄링 방식입니다.

이전에 FCFS 방식은 중간에 다른 프로세스가 들어오면 그 프로세스는 대기해야했지만

이 스케줄링 방식은 선점 또는 비선점이 가능합니다.

 

3. 우선순위 스케줄링 

우선순위 스케줄링은 프로세스마다 우선순위라는 속성이 붙게 됩니다.

우선순위 스케줄링도 역시 선점, 비선점형으로 스케줄링이 가능합니다.

숫자가 높을 수록 우선순위가 높고 만약 우선순위가 같다면 FCFS 방식으로 동작합니다.

 

4. 라운드 로빈 스케줄링

라운드 로빈 스케줄링은 시분할 시스템을 위해 설계된 스케줄링 기법입니다.

이 스케줄링은 작은 단위의 시간인 시간 할당량(Time-Slice)을 정의하여 그 시간 만큼 자원을 할당하는 방식입니다.

그래서 그 시간안에 작업을 끝내지 못하면 다음 프로세스가 다시 그 시간만큼 자원을 할당 받아 사용합니다.

 

5. 멀티 레벨 큐 스케줄링 

 프로세스들이 우선순위 스케줄링과 동일하게 각각의 우선순위 값을 가지고 있습니다. 

여러 개의 큐 자료구조가 우선 순위 별로 존재하는데, 프로세스들은 자신의 우선순위 값에 해당하는 큐에 들어갑니다.

우선순위가 낮은 하위 단계의 큐가 실행 중이더라도 만약 상위 단계의 큐에 프로세스가 도착하면

하위 단계의 큐는 상위 단계 큐에게 CPU를 뺏기는 선점 방식의 스케줄링입니다.

프로세스가 생성될 때 부여된 우선순위가 프로세스가 완료될 때까지 변하지 않는 정적 우선순위이기 때문에

큐 사이에서의 프로세스 이동은 불가능합니다.

 

6. 멀티 레벨 피드백 큐 스케줄링

멀티 레벨 피드백 큐는 각각의 프로세스가 얼마나 CPU를 요구하는지는 모르더라도,

짧은 프로세스들을 좀 더 우대할 수 있는 스케줄링 기법입니다.

지금 실행 중인 프로세스가 완료될 때까지 얼마나 시간이 필요한지 모르지만 지금까지 실행된 시간을 활용해

짧은 프로세스에게 유리하도록, 자원의 활용도를 높이고, 시스템의 성능까지 높일 수 있는 기법입니다.

 다단계 큐와 다르게 시스템에 있는 동안 프로세스의 우선순위가 조정될 수 있는 동적 우선순위 기반의 선점 방식입니다.