[운영체제 OS]CPU 스케줄러의 스케줄링 방법들

앞에서 공부하면서 단기 스케줄러 즉, cpu 스케줄러가 ready Queue에 있는 프로세스들 중 어떤 프로세스에게 CPU를 할당할지를 정한다고 하였다. 여기서는 그 프로세스를 선택하는 여러 가지 스케줄링 방법들을 공부해보자!

 

 

 

스케줄링 (Scheduling)

: CPU스케줄러가 이 스케줄링 알고리즘을 통해 Ready Queue에 있는 프로세스들을 관리한다.

*burst time-cpu 수행 시간 , waiting time-대기시간, turnaround time-수행 시간+대기시간

스케줄링의 목적

• No starvation : 각각의 프로세스들이 오랜 시간 동안 CPU를 할당받지 못하는 상황이 없도록 한다.
• Fairness : 각각의 프로세스에 공평하게 CPU를 할당해준다.
• Balance : Keeping all parts of the system busy

스케줄링 종류

1. FCFS(First Come First Served)

: 먼저 들어온 프로세스부터 순차적으로 처리하는 방식이다. 비선점형 스케줄링이다.

 

문제점으로는 소요시간이 긴 프로세스가 먼저 들어올 경우 효율성이 떨어지게 된다.(convoy-effect)

예를 들어 10초의 수행 시간 P1 3초의 수행시간 P2가 P1→P2순서로 큐에 들어오게 되면 P2는 3초의 수행 시간을 위해 P1이 끝날 때까지 무려 10초나 기다려야 한다. 때문에 P2의 경우 CPU를 요청하여 큐에 들어갔을 때부터 P2의 수행 시간 3초가 끝날 때까지의 시간인 Turnaround시간이 13초가 된다. →따라서 평균 대기 시간(waiting)이 길어지면서 효율성이 떨어질 수 있다.

2.SJF(Shortest - Job - First)

: 다른 프로세스가 먼저 들어왔어도 수행 시간이 짧은 프로세스에 먼저 CPU를 할당함. 비선점형

 

문제점으로는 수행시간이 긴 프로세스의 경우 계속 순서가 밀릴 수 있어 공평하지 못하다.(starvation)

이런 식으로 극단적으로 짧은 수행 시간을 선호하는 스케줄링의 경우 수행 시간이 비교적 긴 P2는 긴 시간 CPU를 할당받을 수 없게 되는 상황이 발생한다.

 

3.SRT(Shortest Remaining time First)

: 현재 수행 중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 뺏긴다. 프로세스가 새로 올 때마다 새로운 스케줄링이 이뤄지는 선점형이다.

 

문제점으로는 새로운 프로세스가 도달할 때마다 스케줄링을 다시 하기 때문에 CPU burst time(CPU 사용시간)을 측정할 수가 없다. (starvation)

예를 들어 이상태에서 2초의 burst time을 가지는 P1이 들어오게 되면

이런 식으로 현재 수행 중이던 P3의 burst time 3초보다 짧은 2초를 갖는 P1이 우선순위를 갖게 된다.

 

4. Priority Scheduling

: 우선순위(숫자로 표현되며 작은 숫자가 높은 우선순위를 가짐)가 높은 프로세스(에게 CPU를 할당하는 방식으로 선점 방식일 경우 CPU를 바로 할당. 비선점 방식일 경우 Ready Queue Head에 넣는다.

문제점으로는 실행할 준비가 되어있으나(Ready Queue에 존재) CPU를 할당받지 못하는 경우가 생겨나 프로세스들이 무기한 대기할 수 있다. (starvation, Indefinite blocking)

해결책으로는 Aging기법을 사용하여 우선순위가 낮아도 오래 기다리면 우선순위를 높여준다.

 

5.RR(Round Robin)

: 현대적인 CPU 스케줄링 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖게 된다. 할당 시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다.

 

CPU 사용시간이 랜덤 한 프로세스들이 섞여있을 경우에 효율적이며 이렇게 프로세스들을 할당 시간마다 선점하게 할 수 있는 이유는 context를 save 할 수 있기 때문이다. →Time Sharing System을 위해 설계된 스케줄링

장점으로는 응답 시간이 빨라진다. →n 개의 프로세스가 ready queue에 있고 할당 시간이 q(time quantum)인 경우 각 프로세스는 q 단위로 CPU 시간의 1/n을 얻는다. 즉, 어떤 프로세스도 (n-1) q time unit 이상 기다리지 않는다. →공정한 스케줄링으로 볼 수 있음.

주의점으로는 할당시간이 너무 커지면 → FCFS와 다를게 없어진다. 반면에 너무 작아지면 → 문맥 교환이 너무 자주 일어나 그에 따른 오버헤드가 발생하게 된다.

↓$선점(Preemptive), 비선점(Non-preemptive) 이란?

선점(Preemptive)

• 우선순위가 높은 프로세스가 실행되고 있던 프로세스의 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법
• 우선순위가 높은 중요한 프로세스를 빠르게 처리가 가능하지만, 선점으로 인한 많은 오버해드를 초래함 →빠른 응답시간 요구하는 대화식 시분할 시스템에 적합
• 또한 선점을 위해 시간 배당을 위한 인터럽트용 타이머 클락이 필요함

비선점(Non-preemptive)

• 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법
• 프로세스가 CPU를 할당받으면 해당 프로세스가 완료될 때까지 사용하게 됨
• 응답시간 예측이 용이함
• 모든 프로세스에 대한 요구를 공정하게 처리가 가능하지만, 중요한 작업이 기다리는 경우가 발생할 수 있음 →일괄 처리 방식에 적합함.

 

선점 스케줄링 종류

: SRT, Priority Scheduling, RR

비선점 스케줄링 종류

: FCFS, SJF, Priority Scheduling