CPU Scheduling (CPU 스케줄링)

CPU Scheduling

• Process 작업수행을 위해 언제, 어느 Process에 CPU를 할당할 것인지를 결정하는 작업.

CPU Scheduling 요건 (Scheduling Criteria)

• 처리 능력(Throughput) 최대화 : 주어진 시간에 최대한 많은 작업을 처리
• 반환시간(Turnaround time) 최소화 : 프로세스가 시스템으로 진입한 후부터 종료할 때까지 걸린 시간의 최소화
• 대기시간(Waiting time) 최소화 : Ready queue에서 기다리는 시간 최소화
• 응답시간(Response time) 최소화 : 대화형 프로세스가 시스템에 요구를 한 후 이에 대한 시스템으로부터의 첫 번째 응답이 올 때까지의 시간의 최소화
• CPU 이용률(Utilization) 극대화

Process 상태전이도와 Scheduler의 종류 및 역할

• 프로세스 상태 전이도

    

    <출처 : ilifo >

• 스케줄러의 종류 및 역할

        - 장기(Job) Scheduler : 프로세스 선택, 주기억장치 할당 (보류-준비)

        - 중기(Process) Scheduler : 프로세스 수에 따라 디스크에 보냄(대기-보류) , 프로세스들이 CPU를 서로 차지하려고 할 때 프로세스를 기억장소(main memory)에서 잠시 빼내고 다시 메인 메모리에 들여보내 실행시킬 수 있는 교체(Swapping) 기법을 사용한다.

        - 단기 Scheduler : 실행 준비된 프로세스에 CPU 할당 (준비-실행)

CPU Scheduling 기법

• 선점(Preemptive) 스케줄링 

        - 개념 : 어떤 프로세스가 CPU를 할당 받아 실행 중에 있어도 다른 프로세스가 실행 중인 프로세스를 중지시키고 CPU를 강제로 점유할 수 있다.  (우선순위에 따라 CPU를 빼앗을 수 있다.)

                    높은 우선순위를 가진 프로세스들이 빠른 처리를 요구하는 시스템에서 유리

        - 장점 : 비교적 빠른 응답

                   대화식 시분할 시스템에 적합

        - 단점 : 높은 우선순위 프로세스들이 들어오는 경우 오버헤드 초래

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

        - 어떤 프로세스가 CPU를 할당 받으면 그 프로세스가 종료되거나 입출력 요구가 발생하여 자발적으로 중지될 때까지 계속 실행되도록 보장한다. (CPU를 빼앗지 못한다.)

        - 일괄처리 시스템에 적합.

        - 장점 : 응답시간 예상이 용이

                   모든 프로세스에 대한 요구를 공정하게 처리

                   스케줄러 호출 빈도가 낮고 Context switching에 의한오버헤드가 적다.

        - 단점 : CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스를 오랫동안 대기시킬 수 있으므로, 처리율이 떨어질 수 있다.

비선점(Non-Preemptive) 스케줄링 알고리즘

• FCFS(First-Come-First-Served)=FIFO(First-In-First-Out)

        - 프로세스가 대기큐(준비큐)에 도착한 순서대로 CPU 할당하는 스케줄링 알고리즘.

        - Convoy Effect 발생 가능 (Burst time이 긴 프로세스가 CPU 독점)

        - 단독적 사용이 거의 없으며, 다른 스케줄링 알고리즘에 보조적으로 사용 (우선순위 스케줄링, RR 스케줄링 등)

• SJF (Shortest Job First)

        - 준비 큐 내의 프로세스 중 CPU 점유시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 스케줄링 알고리즘.

        - 주어진 프로세스 집합에 대해서 평균 대기시간이 최소가 되는 최적 알고리즘

        - CPU 요구시간이 긴 작업과 짧은 작업간의 불평등이 심하여, CPU 요구시간이 긴 프로세스는 Starvation(기아상태) 발생 가능.

• HRN (Highest Response ratio Next)

        - 프로세스 처리의 우선순위를 CPU 처리 기간과 해당 프로세스의 대기 시간을 동시에 고려해 선정하는 스케줄링 알고리즘

        - Response ratio = (대기시간 + 서비스 시간) / 서비스 시간

        - 대기중인 프로세스 중 현재 Response Ratio가 가장 높은 것을 선택

        - SJF의 약점을 보완한 기법으로 긴 작업과 짧은 작업간의 불평등을 완화

• 우선순위 스케줄링

        - 각 프로세스에 우선순위가 주어지고 우선순위에 따라 CPU 할당하는 스케줄링 알고리즘

        - 동일한 우선순위간은 FCFS 처리

        - 우선순위 결정 : 관리자에 의한 결정, 자원요구량에 의한 결정, CPU처리 시간에 의한 결정, 시스템에서 보낸 시간에 의한 결정 등 사용

        - 우선순위가 높은 작업이 계속적으로 들어오게 될 경우 우선순위가 낮은 프로세스는 starvation 발생 -> Aging 기법으로 해결

선점(Preemptive) 스케줄링 알고리즘

• RR(Round Robin)

        - 시분할 시스템을 위해 설계된 선점형 스케줄링의 하나로서, 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위(Time Quantum)로 CPU를 할당하는 스케줄링 알고리즘

        - 시간 단위동안 수행한 프로세스는 준비 큐의 끝으로 밀려나게 됨

        - 문맥 전환의 오버헤드가 큰 반면, 응답시간이 짧아지는 장점이 있어 실시간 시스템에 유리하다.

        - 시간 단위가 크면 FCFS와 같게 된다.

• SRT(Shortest Remaining Time)

        - 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 실행.

        - 남은 처리 시간이 더 짧다고 판단되는 프로세스가 준비 큐에 생기면 언제라도 프로세스가 선점됨

        - 긴 작업은 SJF 보다 대기 시간이 길다.

• 다단계 큐(Multilevel Queue)

        - 커널 내의 준비 큐를 여러 개의 큐로 분리하여 큐 사이에도 우선순위를 부여하는 스케줄링 알고리즘.

• 다단계 피드백 큐(Multilevel Feedback Queue)

        - 다단계 큐 스케줄링에서 한 단계 발전된 방식으로, 다단계 큐 스케줄링에서는 프로세스가 하나의 큐에 영구적으로 할당되지만, 다단계 피드백 큐 스케줄링에서는 프로세스들이 큐를 갈아탈 수 있다.

        - 작업들이 서로 다른 유형의 작업들로 분류될 경우 사용.

        - 새로운 프로세스는 높은 우선순위, 프로세스의 실행시간이 길어질수록 점점 낮은 우선순위 큐로 이동 (맨 마지막 단계에서는 RR 처리)

        - 하위단계일수록 할당시간은 증가 (공평성 부여)

        <출처 : ilifo >