[운영체제] 비선점 스케줄링

1. 비선점 스케줄링의 개요

- 비선점 스케줄링에는 FCFS, SJF, HRN, 우선순위, 기한부 알고리즘이 있다.

2. FCFS(First Come First Service, 선입선출) = FIFO(First In First Out)

- FCFS는 준비상태 큐(대기 큐, 준비 완료 리스트, 작업 준비 큐, 스케줄링 큐)에 도착한 순서에 따라 차례로 CPU를 할당하는 기법으로, 가장 간단한 알고리즘이다.

- 먼저 도착한 것이 먼저 처리되어 공평성은 유지되지만 짧은 작업이 긴 작업을, 중요한 작업이 중요하지 않은 작업을 기다리게 된다.

- 대기 시간 : 프로세스가 대기한 시간으로, 바로 앞 프로세스까지의 진행 시간으로 계산

- 반환 시간 : 프로세스의 대기 시간과 실행 시간의 합

3. SJF(Shorted Job First, 단기 작업 우선)

- SJF는 준비상태 큐에서 기다리고 있는 프로세스들 중에서 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 기법이다.

- 가장 적은 평균 대기 시간을 제공하는 최적 알고리즘이다.

- 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에게 할당 순위가 밀려 무한 연기 상태가 발생할 수 있다.

4. HRN(Hightest Response-ratio Next)

- 실행 시간이 긴 프로세스에 불리한 SJF 기법을 보완하기 위한 것으로, 대기 시간과 서비스(실행) 시간을 이용하는 기법이다.

- 우선순위 계산 공식을 이용하여 서비스(실행) 시간이 짧은 프로세스나 대기 시간이 긴 프로세스에게 우선순위를 주어 CPU를 할당한다.

- 서비스 실행 시간이 짧거나 대기 시간이 긴 프로세스일 경우 우선순위가 높아진다.

- 우선순위를 계산하여 그 숫자가 가장 높은 것부터 낮은 순으로 우선순위가 부여된다.

- 우선순위 계산식 = (대기시간 + 서비스시간) / 서비스시간

5. 기한부(Deadline)

- 프로세스에게 일정한 시간을 주어 그 시간 안에 프로세스를 완료하도록 하는 기법이다.

- 프로세스기 제한된 시간 안에 완료되지 않을 경우 제거되거나 처음부터 다시 실행해야 한다.

- 시스템은 프로세스에게 할당할 정확한 시간을 추정해야 하며, 이를 위해서 사용자는 시스템이 요구한 프로세스에 대해 정확한 정보를 제공해야 한다.

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

6. 우선순위(Priority)

- 준비상태 큐에서 기다리는 각 프로세스마다 우선순위를 부여하여 그 중 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법이다.

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

- 우선순위는 프로세스의 종류나 특성에 따라 다르게 부여될 수 있다.

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