24.01.26 CPU 스케쥴링 알고리즘

1. CPU 스케줄러

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

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

    - 이 알고리즘은 CPU 이용률은 높게, 주어진 시간에 많은 일을 하게 준비 큐(ready queue) 에 있는

      프로세스는 적게, 응답 시간은 짧게 설정하는 것을 목표로 함

 

  1) 비 선점형 방식 (non-preemptive)

       - 프로세스가 스스로 CPU 소유권을 포기하는 방식

       - 강제로 프로레스를 중지하지 않기 때문에 컨텍스트 스위칭으로 인한 부하가 적다

 

     (1) FCFS (First Come, First Served)

           - 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘

           - 길게 수행되는 프로세스 때문에 준비 큐에서 오래 기다리는 현상(convoy effect)이 발생한다는 단점이 있다

 

     (2) SJF (Shrtest Job First) 

           - 실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘

           - 긴 시간을 가진 프로세스가 실행되지 않는 현상(starvation)이 일어나며 평균 대기시간이 가장 짧다

           - 실제로는 실행 시간을 알 수 없기 때문에 과거의 실행했던 시간을 토대로 추측하여 사용

 

     (3) 우선순위

           - SJF 스케줄링의 경우 긴 시간을 가진 프로세스가 실행되지 않는 현상이 있었다 이는 오래된 작업일 수록

             우선순위를 높이는 방법(aging)을 통해 단점을 보완한 알고리즘

 

  2) 선점형 방식 (preemptive)

       - 현대 운영체제가 사용하고 있는 방식

       - 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고 강제로 다른 프로세스에 CPU 소유권을

         할당하는 방식

 

     (1) 라운드 로빈 (RR, Round Robin)

           - 현대 컴퓨터가 쓰는 스케줄링인 우선순위 스케줄링(priority scheduling)의 일종

           - 각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐의 뒤로 가는 알고리즘

           - 예) q 만큼의 할당 시간이 부여되었고 N 개의 프로세스가 운영된다고 하면 (N-1) * q 시간이 지나면

                   자기 차례가 오게됨

           - 할당 시간이 너무크면 FCFS 가 되고 짧으면 컨텍스트 스위칭이 잦아져서 오버헤드, 즉 비용이 커짐

           - 일반적으로 전체 작업시간은 길어지지만 평균 응답 시간은 짧아진다는 특징이 있다

           - 로드밸런서에서 트래픽 분산 알고리즘으로도 쓰임

 

     (2) SRF (Shortest Remaining Time First)

           - SJF 는 중간에 실행 시간이 더 짧은 작업이 들어와도 기존 짧은 작업을 모두 수행하고 그 짧은 작업을

             이어나가는데 SRF 는 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를

             수행하는 알고리즘

 

     (3) 다단계 큐

           - 우선순위에 따른 준비 큐를 여러개 사용하고 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을

             적용한 것

           - 큐 간의 프로세스 이동이 안되므로 스케줄링 부담이 적지만 유연성이 떨어지는 특징이 있다