[OS] Process Management (2) _ CPU 스케줄링

CPU 스케줄링

어떤 프로세스에 CPU를 배정할지 결정하고, 모든 프로세스가 공평하게 작업할 수 있도록 합니다.

 

스케줄링 목적

• 공평성 - 모든 프로세스가 자원을 공평하게 배정받아야 합니다.
• 효율성 - 시스템 자원을 비는 시간 없이 스케줄링 해야합니다.
• 안전성 - 우선순위를 사용하여 중요한 프로세스가 먼저 처리되도록 해야합니다.
• 반응 시간 보장 - 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 인식하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 합니다.
• 무한 연기 방지 - 특정 프로세스의 작업이 무한히 연기되어서는 안됩니다.

 

스케줄링의 단계

• 고수준 스케줄링
  시스템 내의 전체 작업 수를 조절합니다. 시스템 과부하를 막기 위해 작업에 따라 승인할지 또는 거부할지를 결정하기 때문에 시스템 내에서 실행 가능한 프로세스의 총 개수를 정합니다.
  
  
• 중간 수준 스케줄링
  중지(Suspend)와 활성화(Active)로 전체 시스템의 활성화된 프로세스의 수를 조절합니다. 저수준 스케줄링이 완만하게 이루어지도록 완충하는 역할을 합니다.
  
  
• 저수준 스케줄링
  가장 작은 단위의 스케줄링으로 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정하는 역할을 합니다. 중간 수준 스케줄링은 프로세스를 보류 상태로 보낼 수 있고, 저수준 스케줄링은 대기 상태로 보낼 수 있습니다.

이미지 출처: https://velog.io/@tnwls2/6.-CPU-스케줄링

 

스케줄링 고려사항

• Preemptive VS Non-Preemptive
  • 선점형 스케줄링은 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 방식입니다. CPU 처리 시간이 매우 긴 프로세스가 CPU 사용 독점을 막을 수 있어 효율적인 운영이 가능합니다. 하지만 잦은 문맥 교환으로 오버헤드가 발생할 수 있습니다.
  • 비선점형 스케줄링은 프로세스가 CPU를 점유하고 있다면 이를 빼앗을 수 없는 방식입니다. 필요한 문맥 교환만 일어나기 때문에 오버헤드가 상대적으로 적지만 프로세스의 배치에 따라 효율성 차이가 많이 납니다.
• CPU bound VS I/O bound
  • CPU bound process는 CPU를 많이 사용하는 프로세스 입니다.
  • I/O bound process는 입출력을 많이 사용하는 프로세스 입니다.
  • 두 프로세스가 대기 상태에 있다면 I/O bound process에 먼저 CPU를 할당시키는 것이 더 효율적입니다. 왜냐하면 I/O bound process는 CPU를 빠르게 쓰고 입출력을 하러 가기 때문에 다른 프로세스가 오래 기다리지 않아도 되기 때문입니다.
• 전면 프로세스 VS 후면 프로세스
  • 전면 프로세스는 GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓여 입출력에 사용됩니다. 사용자와 상호작용이 가능해 상호작용 프로세스라고도 불립니다.
  • 후면 프로세스는 사용자의 입력 없이 작동하여 일괄 작업 프로세스라고도 불립니다.
  • 전면 프로세스는 사용자의 요구에 즉각 반응해야 하지만 후면 프로세스는 그럴 필요가 없습니다. 따라서 전면 프로세스를 먼저 처리해줘야 합니다.
• 프로세스 우선순위
  • 커널 프로세스 > 일반 프로세스
  • 전면 프로세스 > 후면 프로세스
  • 대화형 프로세스 > 일괄 처리 프로세스
  • 입출력 집중 프로세스 > CPU 집중 프로세스

 

스케줄링 성능척도

• CPU 사용률 (CPU Utilization)
  시스템 동작 시간 중 CPU가 사용된 시간을 측정하는 방법으로 최대한 CPU를 바쁘게 만드는 것입니다. 가장 이상적인 수치는 100%입니다.
• 처리량 (Throughput)
  단위 시간당 작업을 마친 프로세스의 수 입니다. 즉 CPU에 접근하는 CPU 버스트를 처리한 수 입니다.
• 반환 시간 (Turn-around Time)
  프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간입니다. 프로세스의 대기 시간 + 실행시간입니다.
• 대기 시간 (Waiting Time)
  프로세스가 CPU를 할당받아 실행되기 전 대기 상태일 때의 시간입니다. 보통 준비 큐에서 대기하는 시간을 말합니다.
• 응답 시간 (Response Time)
  프로세스가 대기 상태에 들어와 CPU를 최초로 얻기까지 걸리는 시간입니다. 대기 시간과의 차이점은 대기 시간은 반환 시간과 마찬가지로 여러번 있을 수 있습니다. 그 총합이 대기 시간이고, 응답 시간은 최초의 한 번을 의미 합니다.

 

스케줄링 알고리즘

• FCFS (First Come First Served)
  선입선출 방식으로, 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식입니다. 모든 프로세스의 우선순위가 동일하고, 프로세스의 CPU 처리시간을 따로 고려하지 않기 때문에 매우 단순합니다.
  
  하지만 CPU 처리시간이 긴 프로세스가 있을 경우 그 뒤에 프로세스는 한없이 기다려야 하기 때문에 비효율적입니다. 이를 콘보이 효과라고 합니다.
  
  
• SJF (Shortest Job First)
  준비 큐에 있는 프로세스 중 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식입니다. 늦게 도착하더라도 CPU 처리 시간이 앞에 대기중인 프로세스보다 짧으면 먼저 CPU를 할당받을 수 있습니다. 이 때문에 콘보이 효과를 완화할 수 있습니다.
  
  하지만 처리 시간이 긴 프로세스의 경우 처리 시간이 짧은 프로세스가 지속적으로 들어온다면 대기 큐에서 CPU를 할당 받지 못할 수도 있습니다. 이를 Starvation 현상이라고 합니다.
  
  
• HRN (Highest Response Ratio Next)
  SJF 스케줄링에서 Aging(오랫동안 대기하는 프로세스의 우선순위를 증가시키는 방법) 기법을 합친 비선점형 방식입니다. Aging은 나이를 먹는다는 의미로 Starvation을 해결하기 위해 대기 시간이 길어지면 우선순위를 높여주는 방식입니다. [우선순위 공식: 대기시간 + 실행시간 / 실행시간]
• SRTF (Shortest Remaning Tiime First)
  SJF의 선점형 방식입니다. 먼저 온 프로세스가 CPU를 할당받고 있더라도 남은 처리 시간이 뒤에 들어온 프로세스의 처리 시간보다 길다면 CPU를 양보합니다. 이 방식은 평균 대기 시간이 가장 짧은 알고리즘입니다.
  
  하지만 선점형 방식이기 때문에 잦은 문맥 교환이 일어나 오버헤드가 커지고 Starvation 현상이 더 심각하게 발생할 수 있습니다.
  
  
• Priority Scheduling
  프로세스의 중요도에 따라 매긴 우선순위를 반영한 알고리즘으로 위에서 알아본 SJF, HRN, SRTF도 우선순위 스케줄링 알고리즘입니다. Starvation 문제가 있습니다.
  
  
• RR (Round Robin)
  프로세스에 각각 동일한 CPU할당 시간(타임 슬라이스)을 부여해서 이 시간 동안만 CPU를 이용하게 합니다. 만약 할당 시간동안 처리를 하지 못하면 CPU를 빼앗고 다음 프로세스에게 넘깁니다. 빼앗긴 프로세스는 준비 큐의 맨 뒤로 가게 됩니다. 따라서 선점형 방식입니다.
  
  우선순위가 없기 때문에 매우 공평한 방식으로 선점형 방식의 가장 단순하고 대표적인 방식입니다.
  
  모든 프로세스가 최초 응답 시간을 빠르게 보장받을 수 있는 장점이 있습니다. 결론적으로 콘보이 효과도 줄어들게됩니다.
  
  
• Multilevel Queue
  우선순위에 따라 준비 큐를 여러 개 사용하는 방식입니다. 당연히 우선순위가 높은 큐에 먼저 CPU가 할당되어 큐에 속한 모든 프로세스가 처리되야 다음 우선순위 큐가 실행될 수 있습니다. 그리고 한 번 우선순위가 정해져 준비 큐에 들어가면 우선순위가 변하지 않습니다.
  
  
• Multilevel Feedback Queue
  우선순위가 변동되기 때문에 큐 사이의 이동이 가능합니다. 한번 CPU를 할당받은 프로세스는 우선순위가 조금 낮아집니다. 따라서 더 낮은 큐로 이동하게 됩니다.
  
  그리고 보완하기 위해 우선순위가 높은 큐보다 우선순위가 낮은 큐에 타임 슬라이스 크기를 크게 해줍니다. 어렵게 얻은 CPU를 좀 더 오랫동안 사용하게 해주기 위함입니다.

 

결론

프로세스 스케줄링에 대한 개념을 정리하는 시간이었습니다. 글만 많은 포스팅이었지만
잘 읽어주셔서 감사합니다. 참고 자료를 보고 제가 잘 이해할 수 있는 방식으로 글을 썼습니다.

이렇게 정리하면서 포스팅하므로써 개념을 정확하게 정리할 수 있었고,
프로세스에 대한 이해를 할 수 있었습니다. 감사합니다.

 

 

[참고]

1. CPU 스케줄링