Process Scheduling

프로세스 스케쥴링의 종류(level)

 

Long-term Scheduling ( job scheduler )

- 시스템에서 처리할 수 있는 프로그램을 결정한다.

 

Medium-term Scheduling ( swapper )

- 메인 메모리 안에 있는 부분적이거나 완전한 프로세스들의 수를 추가할지 결정한다.

 

Short-term Scheduling ( CPU scheduler )

- 프로세서에 의해 실행될 사용 가능한 프로세스를 결정한다.

 

I/O Scheduling

- 프로세스의 보류중인 I/O 요청에 대한 결정은 사용 가능한 I/O 장치에서 처리한다.

 

선택 함수 ( Select Function )

- 준비 프로세스 중 실행을 위해 다음에 선택할 프로세스를 결정한다.

w : 지금까지 시스템에서 보낸 시간

e : 지금까지 실행에 소요된 시간

s : 프로세스에 필요한 총 서비스 시간 ( e포함 ) 일반적으로 이 양은 유저에 의해 추정되거나 공급되어야 한다.

 

Ex. max[W] => FIFO

 

Decision Mode

- 선택 함수가 사용되는 시간을 지정한다.

- 일반적으로 두가지 카테고리가 있다.

Nonpreemptive(비선점 방식)

- 이 경우 실행 상태에 있는 한 종료되거나, I/O를 기다리거나 또는 I/O를 위해 스스로 차단할 때 까지 운영체제에 서비스를 요청하여 프로세스를 계속해서 실행한다 

Preemptive(선점 방식)

- 현재 실행중인 프로세스는 운영체제에 의해 준비 큐로 이동되거나 인터럽트 된다.

- 선점에 대한 결정은 새 프로세스가 도착할 때 수행된다. (차단된 프로세스를 준비 상태로 두는 인터럽트가 발생하는 경우나 주기적으로 클럭 인터럽트를 기준으로)

 

Scheduling Algorithms

 

1.FIFO ( First In, First Out )

- 현재 프로세스가 실행 중지되면, 준비 큐에서 가장 긴 프로세스가 선택된다. ( FCFS )

- 선택 함수 : Max[W]

- 결정 모드 : 비선점방식

- 장단점 : 가장 간단한 스케줄링 정책 / 짧은 프로세스보다 긴 프로세스에서 더 나은 수행결과를 보임 / FCFS는 convoy effect로 인해 어려움을 겪을 수 있음

 

2.SPN( Shortest-Process-Next )

- 기대 처리 시간이 가장 짧은 프로세싱을 다음에 선택하는 비선점 정책이다.

- FCFS(FIFO)에서 긴 프로세스에 대한 편향을 줄이기 위한 또 다른 접근 방식으로 제시된 방식.

- 짧은 프로세스는 큐의 head로 이동한다.

- SJF(Shortest-Job-First)로도 불림.

- 선택 함수 : min[s]

- 결정 모드 : 비선점방식

- 장단점 : 전반적인 수행은 turnaround time 관점에서 훨씬 개선됨 / 긴 프로세스들은 비중이 적어질 가능성이 있음 / 한가지 어려움은 각 프로세스마다 요구되는 시간을 아는것이 필요함.

3. Round-Robin

- 인터럽트가 발생할 때, 현재 실행중인 프로세스는 준비 큐 안으로 배치되고, 다음 준비된 작업은 FCFS 기준으로 선택된다.

- 가장 중요한 이슈는 타임 퀀텀(Time Quantum)의 길이를 디자인 하는 것이다.

- 선택 함수 : constant

- 결정 모드 : 선점방식

q가 클 경우 => FIFO

q가 작을 경우 => 내용에 switch와 관련하여 q가 커야함. 그렇지 않으면 오버헤드가 너무 높음.

 

4. SRT( Shortest-Remaining-Time )

- 이 스케줄러는 항상 남은 시간이 짧은 프로세스를 선택한다.

- SPN의 선점 방식 버전

- 선택 함수 : min[s-e]

- 결정 모드 : 선점 방식

- 장단점 : SPN보다 뛰어난 처리 시간 성능을 제공한다 / 오버헤드가 높을 수 있다 / Starvation이 발생할 수 있다.

 

5. HRRN( Highest-Response-Ratio-Next )

- R의 밸류가 가장 큰 준비 프로세스를 선택한다.

- R = Response ratio : 정규화된 turnaround time. R = (q+s)/s

- 선택 함수 : max[(q+s)/s]

- 결정 모드 : 비선점방식

- 장단점 : 긴 프로세스는 결국 더 짧은 job을 가짐 / 예상 서비스 시간을 반드시 추정해야함.