운영체제 스케줄링 기법

1. 비선점 스케줄링

- 할당된 CPU를 다른 프로세스가 강제로 빼앗을 수 없는 기법

- 필요성이 떨어지는 긴 프로세스가 선점하고 있을 때 기다리는 점이 발생

- 종류 : FCFS(FIFO), SJF(Shortest Job First), HRN, 기한부(DeadLine)

2. 선점 스케줄링

- 할당된 CPU를 다른 프로세스가 강제로 뺴앗아 사용할 수 있는 기법

- 빠른 응답시간을 요구하는 시분할 시스템에 사용

- 많은 오버헤드

- 인터럽트용 타이머 클럭필요( 프로세스가 자원을 독점하는 것을 방지)

- 종류 : RR(Round Robin, SRT, 선점 우선순위, 다단계 큐(MQ), 다단계 피드백 큐(MFQ)

3. 비전섬 스케줄링 종류

* FCFS( first Come First Service, 선입선출)

- 준비 상태 큐에 도착한 순서에 따라 차례로

* SJF 짧은 작업 우선

- 평균 대기시간이 가장 짧다.

- 실행시간이 긴 프로세스는 무기한 연장될 수 있다.

* HRN( Highest Response-ratio Next )

- SJF 기법의 보완

- 우선순위 공식을 이용해서 실생 시간이 짧은 프로세스나 대시시간이 긴 프로세스에게 우선 순위를 줌

- 우선순위 계산식 = ( 대기시간 + 실행시간 ) / 실행시간

* 기한부 ( Deadline )

- 일정시간동안 프로세스를 완료하는 기법

- 제한된 시간안에 프로세스들이 동시에 실행되면 스케줄링이 복잡해지며 실행시 직중적으로 요구되는 자원관리에 오버헤드가 발생한다.

* 우선순위 ( Priority )

- 프로세스마다 우선순위 부여

- 우선순위가 동일한경우 FCFS 기법으로 할당

- 가장 낮은 순위를 부여받은 프로세스는 무한 연기 또는 기아상태가 발생할 수있다.

4. 선점 스케줄링 종류

* Round Robin

- 시분할 시스템을 위해 고안한 방식, FCFS기법의 변형

- 각 프로세스는 시간 할당량 동안만 실행한 후 완료되지 않으면 다음 프로세스에게 CPU를 넘겨주고 준비상태 큐의 가장 뒤로 배치

- 할당된 시간이 클수록 FCFS와 같다

- 시간이 작을 수록 문맥교환과 오버헤드가 자주 발생

* SRT( Shortest Remaining Time )

- SJF기법의 번형

- 실행중인 프로세스의 남은 시간과 준비상태 큐에 새로 도착한 프로세스의 실행 시간을 비교하여 짧은 실행 시간을 요구하는 프로세스에게 CPU를 할당

- 준비상태 큐에 있는 프로세스의 실행 기간 추적으로 오버헤드 증가

* 다단계 큐

- 프로세스를 특정 그룹으로 분류할 수 있을 경우 그룹에 따라 각기 다른 준비단계 큐 사용

- 시스템, 대화형, 편집, 일괄처리 프로세스 등으로 분류

- 준비상태 큐마다 다른 스케줄링 기법 사용가능

- 다른 준비상태 큐로 이동 불가

- 하위 단계 준비큐에 있는 프로세스를 실행하는 도중이라도 상위 단계 준비상태 큐에 프로세스가 들어오면 상위단계 프로세스에게 CPU 할당

* 다단계 피드백 큐

- 다단계 큐 기법 개선하여 다른 준비상태 큐로 이동가능

- 각 큐마다 시간 할당량부여 시간동안 완료 되지 못한 프로세스는 다음 단계 큐로 이동

- 마지막 단계 큐에서는 RR스케줄링으로 할당

에이징(aging) = 시간이 지날수록 우선순위를 높혀주는것

참고 : http://visu4l.tistory.com/184