CPU Scheduling이 뭔가요?

CPU 스케줄링을 알기 전, 프로세스 관리에 대해 알아야 합니다!

 

프로세스 관리란?

운영체제에서 작동하는 응용 프로그램을 관리하는 기능 입니다.

어떤 의미에서는 프로세서(CPU) 관리하는 것이라고 볼 수도 있습니다. 현재 CPU를 점유해야 할 프로세스를 결정하고, 실제로 CPU를 프로세스에 할당하며, 이 프로세스 간 공유 자원 접근과 통신 등을 관리하게 됩니다.

• 프로세스 : 프로그램을 메모리 상에서 실행중인 작업
• 스레드 : 프로세스 안에서 실행되는 여러 흐름 단위

정리하자면, 아래와 같은 담당을 맡는 기능입니다💁‍

• 프로세스 스케줄링 및 동기화 관리 담당
• 프로세스 생성과 제거, 시작과 정지, 메시지 전달 등의 기능 담당

관리 종류는 다음과 같습니다.

• 프로세스, 스레드
• 스케줄링
• 동기화
• IPC 통신

이 중 오늘은 스케줄링에 관해 공부한 내용을 정리할 예정입니다 !

 

 

CPU Scheduling

프로세스가 실행되는 방식과 순서를 결정하는 CPU에서 수행하는 작업

즉 , 프로그램이 실행될 때는 CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 것인지 결정합니다.

이 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당합니다.

 

왜 사용하는가?

CPU 스케줄링이 없으면 한 번에 하나의 프로세스만 실행할 수 있고 다른 프로세스는 실행되기 전에 현재 프로세스가 완료될 때까지 기다려야 합니다. 즉, 여러 프로세스를 동시에 실행할 수 없게 되는 것입니다.

이로 인해 CPU 리소스 활용도가 떨어지고 프로세스 대기 시간이 길어져 시스템 성능이 저하되고 사용자 생산성이 저하될 수 있습니다.

운영 체제는 CPU 스케줄링 알고리즘을 사용하여 프로세스의 우선 순위, 예상 버스트 시간 및 도착 시간과 같은 다양한 기준에 따라 다음에 실행할 프로세스와 기간을 결정할 수 있습니다. 이렇게 하면 각 프로세스가 CPU 리소스를 공평하게 공유하는 동시에 전체 시스템 처리량을 최대화하고 응답 시간을 최소화할 수 있습니다.

전반적으로 CPU 스케줄링은 CPU 리소스 활용을 최적화하고 효율적이고 응답성이 뛰어난 시스템 성능을 보장하는 데 도움이 되는 운영 체제의 필수 기능입니다.

• 예상 버스트 시간 : 프로세스가 실행을 완료하는 데 걸리는 예상 시간

 

목표와 대상

• 프로그램이 실행될 때는 CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 것인지 결정
• 목표 : CPU 이용률은 높게, 주어진 시간에 많은 일을 하게, 준비 큐(ready queue)에 있는 프로세스는 적게, 응답 시간은 짧게 설정하는 것을 목표로 합니다.
• 대상 : Ready Queue에 있는 프로세스들

 

스케줄링 유형

선점, 비선점 스케줄링 두 가지가 있습니다.

• 선점 (preemptive)
  • CPU 리소스가 제한된 기간 동안만 프로세스에 할당된 후 회수되어 다른 프로세스에 할당됩니다.
  • 라운드로빈
  • SRF
  • 다단계 큐
• 비선점 (non-preeptive)
  • 현재 실행 중인 프로세스가 실행을 완료한 후에만 새 프로세스가 실행됩니다.
  • FCFS
  • SJF
  • 우선순위(HRN)

 

 

비선점형 방식

프로세스가 스스로 CPU 소유권을 포기하는 방식이며, 강제로 프로세스를 중지하지 않는다. 따라서 컨텍스트 스위칭으로 인한 부하가 적다.

1. FCFS(First Come, First Served)
   • 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘
   • 길게 수행되는 프로세스 때문에 ‘준비 큐에서 오래 기다리는 형상(convoy effect)’이 발생하는 단점
2. SJF(Shortest Job First)
   실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘
   • 긴 시간을 가진 프로세스가 실행되지 않는 현상(starvation)이 일어나며 평균 대기 시간이 가장 짧습니다.
   • 하지만 실제로는 실행 시간을 알 수 없기 때문에 과거의 실행했던 시간을 토대로 추측해서 사용합니다.
3. 우선순위(HRN, Hightest Response-ratio Next)
   • 기존 SJF 스케줄링의 경우 긴 시간을 가진 프로세스가 실행되지 않는 현상이 있습니다. 이는 오래된 작업일수록 ‘우선순위를 높이는 방법(aging)’을 통해 단점을 보완하는 알고리즘을 말합니다.
   • 즉, 우선순위를 계산하여 점유 불평등을 보완한 방법(SJF의 단점 보완)
   • 우선순위 = (대기시간 + 실행시간) / 실행시간

 

선점형 방식

현대 운영체제가 쓰는 방식으로 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식을 말합니다.

 

 

1. 라운드 로빈(RR, Round Robin)
   현대 컴퓨터가 쓰는 스케줄링인 우선순위 스케줄링의 일종으로 각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐(ready queue)의 뒤로 가는 알고리즘
   • 할당 시간이 너무 크면 FCFS가 되고 짧으면 컨텍스트 스위칭이 잦아져서 오버헤드, 즉 비용이 커집니다.
   • 일반적으로 전체 작업 시간은 길어지지만 평균 응답 시간은 짧아진다는 특징
   • 이 알고리즘은 로드밸런서에서 트래픽 분산 알고리즘으로도 사용
     • 로드 밸런서 : 사용자와 서버 그룹 사이에 위치하며 보이지 않는 촉진자 역할을 하여 모든 리소스 서버가 동일하게 사용되도록 하는 디바이스
     • 로드 밸런싱 : 여러서버에 트래픽 분산 시켜주는 것

2. SRF(Shortest Remaining Time First)
   • 중간에 실행 시간이 더 짧은 작업이 들어와도 기존 짧은 작업을 모두 수행하고 그 다음 짧은 작업을 이어나가는데, SRF는 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘

3. 다단계 큐(Multilevel-Queue)
   • 우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용한 것을 말합니다. 
     1. 큐 간의 프로세스 이동이 안 되므로 스케줄링 부담이 적지만 유연성이 떨어지는 특성
     2. 우선순위중간 우선순위 - 상호 작용적인 프로세스 - SJF -> CPU
     3. 낮은 우선순위 - 배치 프로세스 - RR -> CPU
     4. 높은 우선순위 - 시스템 프로세스 - FCFS -> CPU

 

이렇게 CPU 스케줄러는 프로세스의 우선 순위, 프로세스의 CPU 버스트 길이, 프로세스가 준비 대기열에서 대기 중인 시간 및 사용 중인 스케줄링 알고리즘과 같은 요소를 기반으로 결정을 내립니다.