[OS] CPU 스케줄링

스케줄링(Scheduling)

다중 프로그래밍을 가능하게 하는 운영 체제의 동작 기법이다. 운영체제는 프로세스들에게 CPU 등의 자원 배정을 적절히 함으로써 시스템의 성능을 개선할 수 있다.

유형

• 1단계 스케줄링 : 장기 스케줄링 = 작업 스케줄링 = Job scheduling
  • 작업이 시스템에 들어오는 것을 승인.
  • 프로세스가 준비큐(ready queue)로 들어간다.
• 2단계 스케줄링 : 중기 스케줄링
  • 프로세스들이 프로세서를 서로 차지하려고 할 때 어느 프로세스부터 CPU를 차지할 수 있게 할지 결정
  • 프로세스들을 보류시키고 다시 활성화하는 기법을 사용하여(스와핑) 시스템에 대한 단기적인 부하를 조절한다. 이로써 시스템을 적절히 운영한다.
  • 스왑은 작업의 혼합을 개선하거나 프로세스가 가지고 있던 메모리를 사용할 수 있게 하는 데 필요하다.
• 3단계 스케줄링 : 단기 스케줄링 = CPU 스케줄링
  • CPU가 사용 가능한 경우 어느 프로세스에게 배당할지 결정

목표

• 단위시간당 처리량 최대화
  
• 자원할당의 공정성 보장
  • 균등하지 않다면 무한대기에 빠질 수 있다.
• 적절한 반환시간 보장
• 자원 사용의 균형 유지
• 서비스 사용기회 확대
• 예측 가능성 보장
• 실행 대기 방지
• 서비스 수 감소 방지
• 오버헤드 최소화
• 우선순위 배정

평가 기준

• CPU 사용률(CPU Utilization) : 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율.
• 처리량(Throughput) : CPU가 단위 시간당 처리하는 프로세스의 개수.
• 응답 시간(Response Time) : 대화식 시스템에서 요청 후 응답이 오기 시작할 때까지의 시간.
  • 대화식 시스템(시분할 시스템) : 일괄 처리 방법에 대응되는 처리 방법으로써, 시스템과 사용자가 모니터와 입력 장치를 통해 대화하듯이 일을 처리하는 방식
• 대기 시간(Waiting Time) : 프로세스가 준비 큐 내에서 대기하는 시간의 총합.
• 반환 시간(Turnaround Time) : 프로세스가 시작해서 끝날 때까지 걸리는 시간.

 

CPU 스케줄링

자원을 어떤 프로세스에 얼마나 할당하는지 정책을 만드는 것을 CPU 스케줄링이라고 한다.

• 목적 : 프로세스들이 CPU를 효율적으로 사용하게 하기 위함

CPU 스케줄링은 크게 두 가지로 분류된다.

1. 비선점(Non-Preemptive) 스케줄링
2. 선점(Preemptive) 스케줄링

결정 시점

CPU 스케줄링의 결정 시점은 다음과 같은 프로세스의 상태 변화가 있을 때이다.

1. 실행 → 대기
2. 실행 → 준비
3. 대기 → 준비
4. 실행 → 종료

 

비선점 스케줄링(Non-Preemptive Scheduling)

이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없게 하는 기법

1번과 4번 상황에서만 수행된다.

장점

• 순서대로 처리되므로 공정성이 있다.
• 다음에 처리해야 할 프로세스와 관계없이 응답 시간을 예상할 수 있다.
• 선점 방식보다 스케줄러 호출 빈도가 낮고 문맥 교환에 의한 오버헤드가 적다.
• 일괄 처리 시스템에 적합

단점

• 공정성은 갖췄지만 융통성은 없음.
  • CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스를 오랫동안 대기시킬 수 있으므로 처리율이 떨어질 수 있다.

스케줄링 알고리즘

1. FCFS 스케줄링(First Come First Served Scheduling)
   • FIFO(First In First Out)라고도 함
   • 준비상태 큐에 도착하는 순서대로 차례대로 CPU를 할당
   • 먼저 도착한 작업이 먼저 처리되는 공정성
   • 융통성이 없음
   • 가장 간단함
2. SJF 스케줄링(Shortest Job First Scheduling)
   • 최단시간 작업 우선 ,SJN이라고도함
   • 준비상태 큐에서 기다리는 프로세스 중에서 실행시간이 가장 짧은 프로세스에게 CPU를 할당
   • 가장 적은 평균대기 시간을 제공 - 짧은 작업시간을 갖는 프로세스에게 유리
   • 긴 작업시간의 작업은 무한정 연기될 수 있음
3. HRRN 스케줄링(Highest Response Ratio Next Scheduling)
   • 실행시간이 길어서 상대적으로 대기시간도 길었던 SJF기법을 보완한 기법
   • 실행시간과 대기시간을 이용한 우선순위를 공식을 이용하여 우선 순위를 정함 - 우선순위를 계산한 값이 큰 수 부터 우선함
   • 우선순위 계산식 : 우선순위 = (대기시간+실행시간) / 실행시간
   • 실행시간이 짧거나 대기시간이 긴 프로세스에게 우선순위가 높음

 

선점 스케줄링(Preemptive Scheduling)

하나의 프로세스가 CPU를 할당받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법

1번 부터 4번까지 모든 상황에서 수행된다.

장점

• 프로세스 하나가 장시간 동안 프로세서를 독점하려는 것을 방지하기 때문에 모든 프로세스에 프로세서를 서비스할 기회를 늘릴 수 있다.
  • 모든 프로세스에게 CPU 사용 시간을 동일하게 부여할 수 있다.
• 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세서를 제어할 수 있다.
  • 우선순위가 높은 프로세스들이 긴급 처리를 요청할 때 용이하다.

단점

• 오버헤드가 커질 수 있어 효과적으로 이용하려면, 메모리에 프로세스가 많이 적재되어 있어야 한다.
  • 즉, 프로세서를 사용 가능할때마다 실행할 수 있는 프로세스들이 준비 상태에 있어야 효과적이다.
• 따라서 선점 스케줄링에는 우선순위라는 개념을 반드시 고려해야 하는데, 우선순위는 의미 있게 부여하지 않으면 효과가 없다.

스케줄링 알고리즘

1. RR 스케줄링(Round Robin Scheduling)
   • 시분할 시스템에서 효과적으로 사용됨
   • 시분할에 의한 동작을 하므로 할당하는 시간의 크기에 따라 CPU를 사용하는 효과에 대한 영향이 큼
     • 할당시간(Time Quantum)이 크면 FCFS와 같은 동작을 함
     • 할당시간(Time Quantum)이 작으면 잦은 문맥교환으로 인한 오버헤드가 자주 발생함
   • 준비상태 큐에 도착하는 순서의 차례대로 CPU를 할당 받아 실행하지만 할당된 일정시간 동안 실행을 완료하지 못한 경우 → 다음 순위의 프로세스에게 CPU를 비워주고 준비상태 큐의 맨 뒤로 들어감
     • 준비큐에 도착하는 순서의 차례대로 CPU를 할당 받아 실행하는 기법은 FCFS와 같음
2. SRTF 스케줄링(Shortest Remaining-Time First Scheduling)
   • 선점 SJF기법이라고도 함
   • 비선점 SJF기법을 선점 형태로 변형한 기법
   • 현재 실행중인 프로세스의 남은 실행시간과 준비큐에 새로 들어온 프로세스의 실행시간을 비교하여 더 짧은 실행시간을 갖는 프로세스에게 CPU를 할당하는 기법
   • ​시분할 시스템에 효과적
   • 실행중인 프로세스와 준비상태 큐에 있는 프로세스의 실행시간을 추적하여 보유하고 있어야하므로 오버헤드 발생이 증가함
   • 긴 작업을 요구하는 프로세스는 SJF보다 대기시간 긺
3. 다단계 큐 스케줄링(MLQ, Multilevel Queue Scheduling)
   

   

   • 프로세스를 여러개의 그룹으로 나눠서 각각의 그룹마다 각각의 준비상태 큐를 사용하는 기법
     
     • 우선순위가 낮은 큐들이 실행 못하는 걸 방지하고자 각 큐마다 다른 Time Quantum을 설정 해주는 방식 사용
     • 우선순위가 높은 큐는 작은 Time Quantum 할당. 우선순위가 낮은 큐는 큰 Time Quantum 할당.
   • 시스템 프로세스, 대화형 프로세스, 편집 프로세스 일괄처리 프로세스 등으로 나누고 각 프로세스 별로 준비큐를 배치함
     • 각각의 준비상태 큐는 독자적인 스케줄링 기법 사용함
     • 프로세스가 여러 준비큐 중 하나에 진입하면 다른 준비큐로 이동할 수 없음
   • 항상 가장 높은 우선순위 큐의 프로세스에 CPU를 할당
     • 우선순위가 낮은 큐에서 작업 실행 중이더라도 상위 단계의 큐에 프로세스가 도착하면 CPU를 빼앗는 선점형 스케줄링
4. 다단계 피드백 큐 스케줄링(MFQ, Multilevel Feedback Queue Scheduling)
   

   

   

   1. • 다 단계 큐 + 동적인 프로세스 우선 순위 변화 적용
      • 프로세스 생성 시 가장 높은 우선 순위 준비 큐에 등록되며 등록된 프로세스는 FCFS 순서로 CPU를 할당받아 실행된다. 해당 큐의 CPU 시간 할당량(Time Quantum)이 끝나면 한 단계 아래의 준비 큐에 들어간다.
      • 단계가 내려갈수록 시간 할당량(Time Quantum)이 증가한다.
      • 큐 사이의 프로세스 이동 가능하며 CPU Burst는 낮은 우선순위의 큐, I/O Burst는 높은 우선순위의 큐에 배치한다.
      • 가장 하위 큐는 FCFS 스케줄링
      • 맨 아래 큐에서 너무 오래 대기하면 다시 상위 큐로 이동 (에이징 기법을 통한 기아상태 예방)
      • 다단계 피드백 큐 스케줄링의 경우 큐의 수, 각 큐에 대한 알고리즘, 우선순위 격상 또는 격하 시기 결정, 처음 프로세스들이 진입해야 할 큐 등등 매우 복잡한 판단을 요구한다.

CPU burst : CPU 명령을 실행하는 것
I/O burst : I/O를 요청한 다음 기다리는 시간을 말한다.

만약, 어떤 프로세스의 CPU burst time이 10초라면, 이 프로세스의 어떤 특정 작업이 완료되기 위해서 CPU가 10초 동안 이 프로세스를 작업해야 한다는 뜻이다.
I/O burst가 왔다는 것은 CPU 작업 후 키보드로부터 입력을 받는 작업이 뒤따라온다든가, 어떤 I/O 작업이 수행되어야 다음 CPU가 작업할 수 있다는 것을 뜻한다.

따라서 프로세스는 CPU Bound process 와 I/O bound Process로 크게 두 종류로 나눌 수 있다.
CPU burst가 큰 프로세스가 CPU Bound process,
I/O burst가 큰 프로세스를 I/O bound process라고 한다.

 

MLQ와 MFQ의 차이점

가장 큰 차이점은 MLQ 스케줄링의 경우 큐와 큐 사이에 프로세스들이 이동을 할 수 없는 반면, MFQ 스케줄링의 경우 큐 사이에 프로세스들이 이동을 할 수 있다. 따라서 MFQ 스케줄링에 비해 MLQ 스케줄링은 스케줄링 부담이 적지만 유연성은 떨어진다.

또한 MLQ 스케줄링의 경우 하위 단계의 큐에 있을수록 CPU 할당을 받지 못하여 기아 현상이 발생할 수도 있지만 MFQ 스케줄링의 경우는 에이징 기법을 통해 기아 현상을 예방할 수 있습니다.

 

참고

• https://preamtree.tistory.com/19
• https://ko.wikipedia.org/wiki/%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81_(%EC%BB%B4%ED%93%A8%ED%8C%85) 
• https://blackjellybear.tistory.com/45
• https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=dkwlsrhstm&logNo=221513533099 
• https://m.blog.naver.com/dkwlsrhstm/221513540640
• https://cocoon1787.tistory.com/124
• https://jhnyang.tistory.com/25