스미스요원

알고리즘 성능 비교 기준

• CPU 사용률

• 처리량 (단위 시간당 완료된 프로세스의 개수)

• 총 처리 시간 (준비 큐에서 대기한 시간 + CPU에서 실행하는 시간 + I/O 시간)

• 대기 시간 (준비 큐에서 대기하는 시간)

• 응답 시간 (요구를 제출한 후 첫번째 응답이 나올 때 까지 걸린 시간)

FCFS (First Come First Served)

• 선입 선처리 스케줄링 (First Come, First Served Scheduling)

    ◦  CPU를 먼저 요청한 프로세스가 먼저 할당받는다.

    ◦  선입선출(FIFO) 큐를 이용해 구현할 수 있다.

• 장점

    ◦  가장 간단한 알고리즘으로 구현하기 쉽고 이해하기도 쉽다.

    ◦  기아현상이 발생하지 않는다.

    ◦  프로세서가 지속적으로 프로세스를 처리하므로 처리율 자체는 높다.

• 단점

    ◦  대기시간이 최소가 됨을 보장하지 못한다. (호위 효과(convoy effect))

         -  예) 실행 시간이 짧은 프로세스부터 처리할 때 보다 대기 시간이 현저히 길어질 수 있다.

    ◦  비선점 방식이므로 대화식 프로세스에는 부적합하다.

SJF (Shortest Job First)

• 최단 작업 우선 스케줄링 (Shortest Job First Scheduling)

    ◦  실행 시간이 짧은 프로세스부터 CPU를 할당받는다

• 장점

    ◦  평균 대기 시간이 최소가 되는 알고리즘이다.

• 단점

    ◦  프로세스를 실행해보기 전에는 얼마의 시간이 소요되는지 알 수 없기 때문에(예측 불가능한 I/O 대기시간까지 실행시간에

         포함되므로) 이론적으로만 구현 가능한 알고리즘이다.

• 프로세스 실행 시간을 예측하는 방법

    ◦  다음 프로세스 실행 시간을 이전의 프로세스 실행 시간들의 지수평균으로 예측하곤 한다.

    ◦  양 변에 T’n+1 과 T’n 이 있는 재귀식임을 알 수 있다.

         -  t’n = n번째 프로세스의 길이

         -  T’n+1 = 다음 프로세스의 길이

SRF (Shortest Remaining Time First)

• 최소 잔여 시간 우선 스케줄링 (Shortest Remaining Time First Scheduling)

    ◦  프로세스가 실행되고 있는 도중에 새로운 프로세스가 Ready Queue 에 도착할 수 있다.

    ◦  이 때 새로운 프로세스의 실행 시간이 실행중인 프로세스의 잔여 시간보다 짧다면 현재 프로세스를 중단하고

         더 짧은 프로세스를 실행시킨다.

    ◦  도중에 중단된 프로세스는 잔여 시간만큼의 길이로 다시 Ready Queue 에 들어간다.

    ◦  프로세스가 Ready Queue 에 도착한 시기와 각 프로세스의 길이 정보를 고려해야 한다.

• 장점

    ◦  SJF 보다 더 짧은 평균 대기 시간을 갖는다.

• 단점

    ◦  SJF와 동일한 이유로 실 상황에서 구현이 불가능하다.

Round Robin

• 라운드 로빈 스케줄링 (Round Robin Scheduling)

    ◦  프로세스가 도착한 순서대로 실행하되, 정해진 실행 시간 제한을 프로세스에 둔다.

         -  시간 할당량 또는 타임 슬라이스 라고 부른다.

         -  CPU 스케줄러는 할당량이 끝나면 인터럽트를 걸도록 타이머를 설정한다.

    ◦  할당된 시간보다 먼저 완료되는 경우 프로세스가 CPU를 자발적으로 반납한다.

    ◦  할당된 시간 안에 완료되지 못한 프로세스는 Ready Queue 의 맨 마지막에 배치된다.

• 장점

    ◦  특정 프로세스가 CPU 를 독점하지 않고 공평하게 이용할 수 있다.

• 단점

    ◦  대기시간이 최소가 됨을 보장하지 못한다.

    ◦  시간 할당량이 너무 크면 FCFS 알고리즘과 다를게 없어진다.

    ◦  시간 할당량이 너무 작으면 문맥 교환 빈도수가 늘어나고, 그만큼 오버헤드가 누적된다.

         -  적절한 시간 할당량을 잘 정하는 것이 중요하다.

         -  일반적으로 한 프로세스 집합의 80% 정도가 시간 할당량보다 짧거나 같으면 좋다.

Priority Scheduling

• 우선순위 스케줄링 (Priority Scheduling)

    ◦  정해진 우선순위에 따라, 가장 높은 우선순위의 프로세스부터 CPU를 할당한다.

    ◦  우선순위는 다양한 내/외부적 기준에 따라 세워질 수 있다.

         -  시간 제한 / 메모리 요구 / 열린 파일의 수 / I.O 대기시간과 실행 시간의 비율 / 프로세스의 중요성 등

    ◦  새로 도착한 프로세스의 우선순위가 현재 실행중인 프로세스 보다 높은 경우

         -  선점형 : 새로 도착한 프로세스가 CPU를 할당받고, 실행되던 프로세스는 준비 큐로 들어간다.

         -  비선점형 : 선점 없이 Ready Queue 의 맨 앞쪽에 배치된다.

• 장점

    ◦  각 프로세스의 중요성에 따라 작업을 수행하므로 합리적이다.

    ◦  실시간 시스템에서 사용 가능하다.

• 단점

    ◦  기아 상태(Starvation)(무한 봉쇄) 문제

         -  낮은 우선순위의 프로세스가 영원히 실행되지 못하는 문제가 발생할 수 있다.

    ◦  노화(Aging) 기법으로 해결하기

         -  Ready Queue 에서 대기하고 있는 프로세스들의 우선순위를 점차 증가시키는 방법

         -  예) 주기적으로 1초마다 대기중인 프로세스의 우선순위를 1씩 증가시킨다.

MLQ (Multilevel Queue)

• 다단계 큐 스케줄링 (Multilevel Queue Scheduling)

    ◦  우선순위마다 별도의 큐를 가지는 구조

    ◦  각 큐마다 서로 다른 스케줄링 알고리즘이 사용될 수 있다.

    ◦  프로세스가 큐에 한번 할당되면 다른 큐로 이동하지 않는다.

• 장점

    ◦  단일 큐로 프로세스를 관리할 때 드는 O(n) 검색 시간을 단축할 수 있다.

• 단점

    ◦  큐 내부의 프로세스 뿐만 아니라 큐와 큐 사이에서도 스케줄링 필요하다.

         -  고정 우선순위의 선점형 방식으로 스케줄링 될 수 있다.

         -  각 큐마다 CPU 선점 가능 시간을 정해두는 방식으로 스케줄링 될 수 있다. (기아현상 예방)

MFQ (Multilevel Feedback Queue)

• 다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue Scheduling)

    ◦  프로세스가 다른 큐로 이동하는 것을 허용한다.

• 장점

    ◦  융통성있는 프로세스 관리가 가능하다.

         -  프로세스가 CPU 시간을 너무 많이 쓰면 낮은 우선순위 큐로 이동시킨다. (시간 할당량)

         -  낮은 우선순위 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위 큐로 이동시킨다.

    ◦  Aging 기법을 통해 기아현상을 예방할 수 있다.

• 단점

    ◦  프로세스가 큐를 이동하는 과정에서 오버헤드가 발생할 수 있다.

    ◦  결정해야할 요소가 많아 복잡한 판단이 요구된다.

         -  큐의 개수

         -  각 큐에 적용할 스케줄링 알고리즘

         -  특정 프로세스를 높은 우선순위 큐로 올려줄 시기

         -  특정 프로세스를 낮은 우선순위 큐로 내려줄 시기

         -  새로운 프로세스가 들어갈 큐를 선택하는 방법

참고자료