스케줄링(Scheduling)

일반적인 스케줄링이란 처리할 일들의 진행순서를 정하는 일이다.

• 프로세스 스케줄링: CPU를 사용하려고 하는 프로세스들 사이의 우선순위를 관리하는 일
• 디스크 스케줄링: 디스크를 사용하려고 하는 프로세스들 사이의 우선순위를 관리하는 일

비선점 스케줄링과 선점 스케줄링

• 스케줄링의 적용 시점에 따라 비선점형, 선점형 2가지로 구분할 수 있다.

1) 비선점형 스케줄링은 프로세스가 (실행 -> 대기), (실행 ->종료) 로의 상태전이가 있을 때 적용

2) 선점형 스케줄링은 (실행 ->대기), (실행 -> 준비), (대기 -> 종료) 모든 상태변화에서 적용

• 비선점

이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법, 선점 방식보다 스케줄러 호출 빈도가 낮고 문맥 교환에 의한 오버헤드도 적다. 일괄처리 시스템에 적합하며, CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스를 오랫동안 대기시킬 우려가 있으므로 처리율이 떨어질 수 있다는 단점이 있다.

• 선점

하나의 프로세스가 CPU를 할당 받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 기법이다. 모든 프로세스에게 CPU 사용시간을 동일하게 부여할 수 있으며 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세스를 제어할 수 있다.

비선점 스케줄링 알고리즘

• FIFO (First In First Out) : 가장 간단한 방식으로 선입선출의 방식이다. 먼저 들어오면 먼저 나가는 방식, FCFS(First Come First Served)라고도 한다.

• SJF(Shortest Job First Scheduling) : 평균 대기 시간을 최소화하기 위해 CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식. 실행 시간이 긴 프로세스는 짧은 프로세스에게 할당 순위가 밀려 연기 상태에 빠질 수 있다는 단점이 있다.

• HRN(Highest Response-ratio Next) : 실행시간이 긴 프로세스에 불리한 SJF기법을 보완하기 위한 것으로 대기 시간과 서비스 시간을 이용하는 방식. 우선순위 = (대기시간 + 서비스시간)/서비스시간 의 공식을 이용하여 우선순위를 계산하여 실행하는 방식.

  이렇게 프로세스가 지원을 기다리고 있는 시간에 비례하여 우선순위를 부여함으로써 무한 대기문제를 방지하는 것을 에이징(aging) 기법이라고 함.

선점 스케줄링 알고리즘

• SRT(Shortest Remaining Time) : 비선점 스케줄링인 SJF기법을 선점 형태로 변경한 기법이다.SJF처럼 CPU점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식으로, 차이점은 단지 ‘선점형’으로 바뀌어 중요한 프로세스가 있으면 점유시간이 길어도 먼저 실행 시킬수 있는 권한이 생긴다라는것이다.
• RR(Round-Robin) : 프로세스들 사이에 우선순위를 두지 않고 순서대로 시간단위로 CPU를 할당하는 방식. 보통 시간 단위는 10ms ~ 100ms 정도이고 시간 단위동안 수행한 프로세스는 준비큐의 끝으로 밀려나게 된다. 문맥 전환의 오버헤드가 큰 반면, 응답시간이 짧아지는 장점이 있어 실시간 시스템에 유리하고, 할당되는 시간이 클 경우 비선점 FIFO기법과 같아지게 됨.
• 다단계 큐(MQ, Multi-level Queue) : 프로세스를 특정 그룹으로 분류할 수 있는 경우 그룹에 따라 각기 다른 분비 상태 큐를 사용하는 기법이다. 프로세스가 특정 그룹의 준비 상태 큐에 들어갈 경우 다른 준비상태 큐로 이동할 수 없음. 하위 준비 상태 큐에 있는 프로세스를 실행하는 도중이라도 상위 준비 상태 큐에 프로세스가 들어오면 상위 프로세스에게 CPU를 할당해야 함.