<프로세서 스케줄링 종류>
비선점(Non-Preemptive) 스케줄링
•
이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법
•
프로세스가 CPU를 할당받으면 해당 프로세스가 완료될 때까지 CPU를 사용
•
모든 프로세스에 대한 요구를 공정하게 처리 가능
•
일괄 처리 방식에 적합, 중요한 작업이 기다리는 경우가 발생할 수 있음
•
응답시간 예측이 용이
•
종류 : FCFS(FIFO), SJF, 우선순위, HRN, 기한부 등 알고리즘
선점(Preemptive) 스케줄링
•
하나의 프로세스가 CPU를 할당받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법
•
우선순위가 높은 프로세스를 빠르게 처리할 수 있음
•
주로 빠른 응답시간을 요구하는 대화식 시분할 시스템에 사용
•
선점으로 인한 많은 오버헤드를 초래함
•
선점을 위해 시간 배당을 위한 인터럽트용 타이머 클럭(Clock)이 필요
•
종류 : SRT, 선점 우선순위, RR(Round Robin), 다단계 큐, 다단계 피드백 큐 등 알고리즘
비선점(Non-Preemptive) 스케줄링 종류
•
FCFS(First-Come First-Service) = FIFO(First In First Out)
◦
준비상태 큐에 도착한 순서에 따라 차례로 CPU를 할당먼저 도착한 것이 먼저 처리되어 공평성 유지, 짧은 작은이 긴 작업을 기다리는 경우 발생
•
SJF(Shortest Job First)
◦
실행시간이 가장 짧은 프로세스에 먼저 CPU를 할당하는 기법가장 적은 평균 대기 시간을 제공하는 최적 알고리즘
•
HRN(Hightest Responseratio Next)
◦
실행시간이 긴 프로세스에 불리한 SJF 기법을 보완하기 위한 것으로, 대기 시간과 서비스 시간을 이용하는 기법우선순위 계산 공식 = 대기시간 + 서비스시간 / 서비스시간우선 순위 계산 결과값이 높은 것부터 우선 순위가 부여, 대기 시간이 긴 프로세스일 경우 계산 결과값이 높게 나옴
•
기한부(Deadline)
◦
프로세스에게 일정한 시간을 주어 그 시간 안에 프로세스를 완료하도록 하는 기법시스템은 프로세스에게 할당할 정확한 시간을 추정해야함사용자는 시스템이 요구한 프로세스에 대한 정확한 정보를 제공해야함
•
우선순위(Priority)
◦
준비상태 큐에서 기다리는 각 프로세스마다 우선순위를 부여하여 그 중 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법
◦
프로세스 자체적으로 우선순위를 정해두고, 우선순위 값이 제일 큰 프로세스에게 CPU를 할당한다. 순위가 같을 경우 FCFS를 적용한다.
◦
SJF도 결국엔 우선 순위 스케줄링에 포함된다고도 할 수 있다. (우선순위가 CPU Burst Time의 역수)
◦
내부적 우선순위 고려 : 제한시간, 메모리 요구량, 사용하는 파일 수, 평균 CPU Burst에 대한 평균 I/O Burst 비율
◦
일반적으로 연산 위주(CPU-Bound) 프로세스보다 입출력 위주(I/O-Bound) 프로세스에게 높은 우선순위를 부여하여 대화성을 증진시킨다.
◦
기아 상태(Starvation)가 유발될 수 있다. 우선순위가 높은 작업이 계속적으로 들어올 경우 우선순위가 낮은 작업이 준비 상태에서 보장없이 머물 수 있다.
◦
이러한 기아 상태는 에이징(Aging)으로 해결할 수 있다. 시스템에 머무는 시간이 증가하면 우선순위를 높여주는 것이다. 아무리 우선순위가 낮았던 프로세스라도 시간이 지나면서 우선순위가 높아져 결국은 CPU를 할당받을 수 있게 된다.
에이징(Aging) 기법
•
시스템에서 특정 프로세스의 우선순위가 낮아 무한정 기다리게 되는 경우, 한 번 양보하거나 기다린 시간에 비례하여 일정 시간이 지나면 우선순위를 한 단계씩 높여 가까운 시간 안에 자원을 할당받도록 하는 기법
•
SJF나 우선순위 기법에서 발생할 수 있는 무한 연기 상태, 기아 상태를 예방할 수 있다.
선점(Preemptive) 스케줄링 종류
•
선점과 동적 우선순위
◦
준비 상태 큐의 프로세스들 중에서 우선순위가 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법
◦
선점(Preemption) : 현 프로세스로부터 CPU를 회수하여 다른 프로세스에게 할당하는 행위
◦
동적 우선순위 : 프로세스 실행 중 시스템의 성능, 프로세스의 특성을 고려해 우선순위를 재조정할 수 있다. 결과적으로 스케줄링에 의해 선점이 발생할 수 있다.
◦
동적 우선순위 스케줄링은 dynamic priority scheduling이라 하고 고정 우선순위 스케줄링은 fixed priority scheduling이라 한다.
◦
전체적인 시스템 성능의 향상 및 프로세스 속성을 고려하여 커널의 여러 곳에서 우선 순위를 조정하는 원칙과 기법이 필요하다.
•
SRT(Shortest Remaining Time)
◦
비선점 기법 SJF 알고리즘을 선점 형태로 변경한 기법현재 실행중 프로세스의 남은 시간과 준비상태 큐에 새로 돛가한 프로세스의 실행시간을 비교해 가장 짧은 실행 시간을 요구하는 프로세스에게 CPU를 할당하는 기법
•
RR(Round Robin)
◦
시분할 시스템(Time Sharing System)을 위해 고안된 방식, FCFS 알고리즘을 선점 형태로 변형한 기법
◦
FCFS(FIFO) 기법과 같이 준비상태 큐에 먼저 들어온 프로세스가 먼저 CPU를 할당받지만 각 프로세스는 할당된 시간(Time Slice Quantum)동안만 실행한 후 실행이 완료되지 않으면 다음 프로세스에게 CPU를 넘겨주고 준비상태 큐의 가장 뒤로 배치함
◦
할당되는 시간이 클 경우 FCFS 기법과 같아지고, 할당되는 시간이 작을 경우 문맥 교환 및 오버헤드가 자주 발생
•
다단계 큐(Multi level Queue)
◦
프로세스를 특정 그룹으로 분류할 수 있는 경우 그룹에 따라 각기 다른 준비상태 큐를 사용하는 기법
•
다단계 피드백 큐(Multi level Feedback Queue)
◦
특정 그룹의 준비상태 큐에 들어간 프로세스가 다른 준비상태 큐로 이동할 수 없는 다단계 큐기법을 준비상태 큐 사이를 이동할 수 있도록 개선한 기법