[OS] - CPU Scheduling

CPU Scheduling

---

Processor(CPU)가 Process를 적절하게 배정하여 사용률을 높이고 Overhead와 Starvation을 낮추기 위함

 

목표

1. Batch System : 가능하면 많은 일을 수행한다. (일을 한개씩 하는 것보다 100개씩 처리하는것이 좋다)

2. Interactive System : 빠른 응답 시간, 적은 대기 시간

3. Real-time System : Deadline

 

Preemptive vs NonPreemtive

Preemptive

• OS가 Cpu를 Process를 선점할 수 있는 경우 강제로 변경 가능하다.

 

NonPreemptive

• Process Exit , I/O Event가 있을 때 까지는 Process의 실행을 보장하여 준다.

 

Process State

• Process는 Preemptive와 Nonpreemtive 차이에 따라 State 변경이 달라질 수 있다.
• Preemptive는 Interrupt와 EventCompletion이 발생하면 바로바로 처리가 가능하다.
• 그에 반면에 NonPreemptive는 현재 Process가 동작이 완료되거나 Event가 발생할 때까지 대기해야한다.

 

CPU Scheduling

---

Non-Preemptive Scheduling

1. FCFS (First Come FisrtServed)

Q에 도착한 순서대로 처리한다.

뒤에 온 Process들은 대기 시간이 길어진다.

 

2. SJF (Shortest Job First)

수행시간이 짧다고 판단되는 작업을 먼저 수행

FCFS보다 평균 대기 시간 감소

수행시간이 길면 처리시간이 계속 밀리게 된다.

 

3. HRN(Highest Response-ratio Next)

우선 순위를 계산하여 SJF의 단점을 보완

우선 순위 = (실행시간+대기시간)/실행시간

 

문제점 : 수행시간을 어떻게 알것인가?

 

Preemptive Scheduling

1. Prioirty Scheduling

• 우선 순위를 부여하여 우선순위가 높은 작업부터 처리
• 우선 순위가 낮으면 Starvation 발생 -> Aging ( 시간이 오래 되면 우선순위를 올려준다 )

 

2. Round Robin

• FCFS에 의해 Process들이 보내지면, 동일한 시간의 Time Quantum 만큼 Processor(CPU)를 할당
• Time Quantum에 따라 커지면 FCFS와 유사하고 너무 낮으면 Context-swithing으로 Overhead가 많이 발생

 

3. Multi-Level Q

• 각 Q는 Round-Robin 형태로 동작
• 작업들을 여러 종류로 나누어 Q마다 Time Quantum을 다르게 설정
• 우선순위가 높은 큐는 작은 Time Quantum 할당. 우선순위가 낮은 큐는 큰 Time Quantum 할당.
• 프로세스는 한번 정해진 Q에서 다른 Q로 이동이 불가

4. Multi-Level Feedback Q

• 큐에서 자신의 Time Quantum을 다 채운 프로세스는 밑으로 내려가고 자신의 Time Quantum을 다 채우지 못한 프로세스는 원래 큐 그대로
• 짧은 작업에 유리, 입출력 위주의 Interrupt가 잦은 Job에 대해 우선권
• 처리 시간이 짧은 프로세스를 먼저 처리하기 때문에 Turnaround 평균 시간이 줄어든다.
•  

 

 

Scheduling 기준 척도

1. Response time

• 대기 시간 = 작업되기 까지 걸린 시간

2. Turnaround time

• 실행 시간 + 대기 시간을 합한 시간으로 작업이 완료될 때 까지 걸린 시간