[운영체제] 스케줄링 알고리즘 ( Scheduling Algorithm)

1.스케쥴링 (Scheduling)?

- Ready Queue에 올라온 프로세스가 여러개일 때, 자원 할당을 조절하는 것

- 선점형 ( Preemptive) , 비선점형(Non- Preemptive)가 있다.

* 선점형 (Preemptive)

: 우선순위 높은 프로세스 먼저.

: 현재 실행중인 프로세스를 강제로 멈추고 (CPU를 뺏고) 우선순위 높은 프로세스에게 CPU 할당 ( 인터럽트 )

-> Context Switching 비용 증가

* 비선점형(Non- Preemptive)

: 현재 실행중인 프로세스가 먼저.

: 현재 실행중인 프로세스가 자발적으로 CPU 사용을 중단 할 때만 다른 프로세스에게 CPU 할당.

현재 실행중인 프로세스 A보다 높은 우선순위의 프로세스 B가 Ready Queue에 대기 중일 때

- 선점형 : A를 Ready상태로 보내고 B를 Running 상태로 바꾼다.

- 비선점형 : A의 작업이 Terminate 하거나 Wating 상태일 때만  다른 프로세스에 CPU 할당.

2. 선입선처리 ( FCFS ) - 비선점형

: Ready Queue에 들어온 순서대로 CPU 할당.

문제점 : 평균 대기 시간이 길어질 수 있음.

3. 최단작업 우선 ( SJF )

: 작업시간(CPU Burst Tim)이 짧은 프로세스를 먼저 수행

: 평균 대기 시간 기준, 최적의 스케줄링 알고리즘.

But, Process CPU Burst Time을 정확히 알 수 없어서 실제 구현은 어려움.

-> 시간을 예측하는 방법으로 구현.

4. 우선순위 ( Priority ) - 선점형

- 각 프로세스에 우선순위를 부여함

- Ready Queue에서 우선순위가 높은 프로세스를 우선 수행.

- 우선 순위가 같을 경우 FCFS 방식으로 처리.

문제점 : 무한대기 (기아상태) 문제 발생 가능.

해결책 : Aging기법 ( 오래 대기하는 프로세스의 우선순위를 점진적으로 증가 시켜주는 방식) 사용.

5. 라운드로빈 ( Round-Robin) - 선점형

: 시분할 시스템의 스케줄링 알고리즘

: Time Quantum (=Time Slice) 기준으로 정해진 시간마다 CPU 할당.

: 할당 시간이 끝나면 강제로 다른 프로세스에 CPU 할당. (인터럽트)

: Time Quantum

- 매우 클때 : FCFS와 같아짐

- 매우 작을때 :  응답시간은 줄어들지만 잦은 문맥교환 (Context Switching) 으로 인해 비용이 증가 , 성능 저하

- CPU burst보다 작으면  문맥 교환 시간 때문에 실행 시간이 점점 늘어남.

- 전체 CPU burst시간의 80%보다 큰게 적절하다고 함

+ 우선순위 역전 현상?

Ready Queue에 프로세스 A, B, C 가 있다.

우선순위는 A > B > C 이다.

A는 C의 작업 결과물이 필요하다.

이 때, A는 작업 중 C의 결과를 받기 위해 기다린다. (Waiting)

우선 순위에 의해 다음 CPU 할당은 B가 되고, A는 다시 Ready Queue에 A>C 상태로 존재한다.

때문에 C는 실행되지 못하고 A가 다시 실행된다.

B와 같은 우선순위의 프로세스가 계속 Ready Queue에 들어온다면 C는 계속해서 실행되지 못하고, A 역시 작업을 끝내지 못하게 된다. 

위와 같은 현상을 우선순위 역전 현상이라 한다.

해결 방법은 A가 Wating 상태로 갈때 자신의 우선순위를 C에게 상속해주는 방법이 있다.