[CS] CPU스케줄링 알고리즘

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

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

이용률은 높게, 주어진 시간에 많은 일을 하게, 준비 큐(ready que)에 있는 프로세스는 적게, 응답시간은 짧게 설정하는것을 목표로 함.

 

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

    - 프로세스가 스스로 CPU 소유권을 포기하는 방식이며, 강제로 프로세스를 중지하지 않음.

      ㄴ컨텍스트 스위칭으로 인한 부하가 적음.

    1) FCFS(First Come, Fist Served): 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘

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

       ㄴconvoy effect :  p1이 오래걸리면 p4가 오래 기다리는 현상

2) SJF(Shortest Job First) : 실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘

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

      ㄴ 실제로는 실행 시간을 알 수 없기 때문에 과거의 실행했던 시간을 토대로 추측해서 사용. (과거에 내가 롤을 한시간 정도를 한다고 하면 그 시간을 토대로 추측.)

      ㄴstarvation(기아)현상은 aging을 통해 우선순위를 높여 해결 가능.

convoy effect와 starvation의 차이
--> convoy effect는 몇개의 시간이 오래 걸리는 프로세스로 인해 전체 OS가 느려지는 FCFS 알고리즘과 관련된 현상. (예를 들어, P1이 100, P2가 5 정도의 시간이 걸린다고 할때 P2는 적어도 100의 시간을 기다려야 한다.)

3) 우선순위 : 오래된 작업일수록 우선순위를 높이는 방법(aging)

    - 기존 SJF 스케줄링의 경우 긴 시간을 가진 프로세스가 실행되지 않는 현상을 해결.
    ㄴFCFS를 활용하여 만들기도 하며 선점형, 비선점형적인 우선순위 스케줄링 알고리즘을 말함.

2. 선점형 방식(preemptive)

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

    - 현대 운영체제가 쓰는 방식.

 

    1) 라운드 로빈(RR, Round Robin) : 현대 컴퓨터가 쓰는 스케줄링 방법이며 단순한 선점형 알고리즘

각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐(ready queue)의 뒤로 감.

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

        - 일반적으로 전체 작업 시간은 길어지지만 평균 응답 시간은 짧아짐.

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

 

    2) SRF : SJF와 유사

        - SRF : 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행.

            ㄴSJF는 중간에 실행 시간이 더 짧은 작업이 들어와도 기존 짧은 작업을 끝까지 수행하고 그다음 짧은 작업을 이어나감.

 

    3) 다단계 큐 : 우선순위에 따른 준비 큐를 여러개 사용하고, 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용한 것 (비선점형 알고리즘도 있다.)

        - 우선순위가 높은 큐부터 처리

        ㄴ낮은 큐의 프로세스가 처리가 안되는 기아현상(starvation)이 발생할 수도 있음.

큐 간의 프로세스 이동이 안되므로 스케줄링 부담이 적지만 유연성이 떨어짐.