CPU Scheduling

http://www.kocw.or.kr/home/cview.do?mty=p&kemId=1046323

해당 강의를 보고 개인적으로 정리를 하는 포스팅 입니다.

운영체제

---

 

프로그램은 CPU Burst -> I/O Burst 가 번갈아가며 일어남.

 

CPU Burst time 이 긴 Job 을 CPU Bound Job -> 적은 양의 긴 CPU 점유

I/O 가 잦아 I/O Bust time 이 긴 Job 을 I/O Bound Job 이라고 한다. -> 많은 횟수의 짧은 CPU 점유

 

"CPU 스케줄링은 이처럼 각기 다른 CPU 점유 시간과 처리 방법을 지닌 프로세스들을

효율적인 시스템 자원 사용과 사용자에게 빠른 응답을 제공하기 위해 필요함"

 

Cpu 스케줄링은 CPU Scheduler 를 통해 어떤 Ready 프로세스에게 CPU 제어권을 줄지 결정하고

CPU Dispatcher 에 의해 실제로 제어권을 넘겨줌 (OS 의 스케줄링하는 소프트웨어를 역할을 나눠 이름 붙인것임)

이때 Context Switching 이 일어남.

 

 

 

Scheduling Algorithm

CPU 스케줄링은 다양한 방법이 있음. 

용도에 따라 적절한 스케줄링 기법을 사용하는 것이 좋음

 

스케줄링 기법의 성능 척도 

CPU 기준

• CPU Utilization - CPU 사용률, 즉 CPU 가 바쁘게 작업을 할 수록 좋은 성능
• Throughput - 처리량, 단위 시간당 프로세스 완료량

유저 기준

• Turnaround time - ready queue 에서의 대기 시간을 포함한 전체 진행 시간
• Waiting time - ready queue 에서 기다린 대기 시간(response time 을 포함한 총 대기시간)
• Response time - 첫 CPU 선점까지 대기한 시간

 

알고리즘 종류

우선 비선점형과 선점형의 차이를 구분해야함.

• 선점형 (preemtive)- CPU 의 제어권을 강제로 빼앗을 수 있음
• 비선점형 (nonpreemtive)- CPU 의 제어권을 강제로 빼앗지 않음

 

1. FCFS - First Come First Second

 

먼저 Ready Queue 에 도착한 순서대로 처리함. 대표적인 비선점형.

작업 처리 시간이 긴 프로세스가 먼저 도착하면 전체적인 Waiting time 이 대폭 늘어남.(Convoy Effect)

 

2.SJF - Shortest Job First

 

처리 시간이 가장 짧은 Job 부터 처리하는 방법.

• 비선점형 SJF : 일단 CPU 를 잡은 후에는, 처리 중에 더 처리 시간이 짧은 Job 이 들어와도 처리를 완료하고 CPU 를 넘김
• 선점형 SJF: CPU 를 잡고 나서도, 처리 중에 남은 처리시간보다 처리시간이 더 짧은 Job 이 들어오면 CPU 를 넘김
  = SRTF - Short Remaining Time First 라고도함

선점형 SJF 는 모든 스케줄링 기법에서 가장 적은 avarage wating time 을 보장함.

하지만 idle 하지는 않음. 

 

문제점.

• Starvation , CPU 사용 시간이 긴프로세스는 영원히 대기 할수도있음.
• CPU Birst time 을 정확히 알 수 없음. 추정해야함

CPU Birst time 추정은 exponential avaraging 기법을 사용함.

 

 

ㄱ

과거의 CPU Birst time 을 이용해서 추정. 최근 이력일 수록 가중치를 줘서 계산하는 기법

 

SJF 의 Starvation 문제는 우선순위 스케줄링의 고질적인 문제점인데,

Aging 즉 오래된 작업일수록 우선순위를 증가시켜 해결할 수 있음.

 

3. Round Robin

동일한 크기의 할당시간 (time quantum) 을 주어, 할당 시간이 지나면 프로세스를 선점 당하고 ready queue 맨뒤로 돌아가게 하는 기법.

즉 CPU를 골고루 사용해라~ (Load Balancer 의 Round Robin 과 이념은 같네)

 

* 최대로 대기해도 (n-1)q 시간 이상은 대기하지 않음  (n= 순번, q= time quantum)

* 적절한 q 를 선정하면 CPU 를 짧게 쓸수록 wait time 도 짧음 (CPU 를 여러번 얻을 필요가 없으니까)

 

q 가 너무 크면? -> FCFS 나 다를바 없어짐

q 가 너무 작으면? -> 잦은 context switching 으로 인한 성능저하

적절한 time quantum 을 지정하는 것이 중요하다.

 

Round Robin 의 핵심은 response time 이 줄어든다는점. -> 사용자에게 최적의 경험을 줄 수 있음

SJF 보다 avg turnaround time 은 길지만, response time 은 적다.

 

 

4. Multilevel Queue Scheduling

Round Robin 만으로는 부족해!

서로 우선 순위가 다른 Ready Queue 를 여러개 두고, 각각의 Queue 에서 우선순위에 따라 꺼냄

 

각각의 큐는 독립적인 스케쥴링 알고리즘을 지님.

우선순위가 높은 큐에는 Round Robin 을 우선순위가 제일 낮은 큐에는 FCFS 알고리즘을 지정하고,

Job 에 따라 각각의 큐에 분배.

 

각각의 큐가 지니는 프로세스 처리에 대한 알고리즘 말고 큐에 대한 스케쥴링도 필요함.

• Fixed Priority : foreground 큐의 모든 처리가 끝나면 background 큐의 처리를 시작. 고정 우선순위의 고질적인 문제점인 Starvation 발생 가능성 존재
• Time slice : 각 큐의 CPU 타임을 우선순위 비율로 나누어 주어 처리. 

 

5. Multilevel Feedback Queue

Multilevel Queue 에서 프로세스가 Queue 간 이동이 가능한 모델.

 

만약 3개의 큐가 존재한다면, 가장 우선순위가 높은 큐에 짧은 time quantum 을

그 다음 우선순위의 큐에 그보단 조금 더 긴 time quantum 을,

최 하위 우선순위의 큐에는 FCFS 를 적용하고 프로세스를 최 상위 우선순위 큐부터 집어넣어 처리.

처리가 완료되지 않으면, 그 하위 큐로 이동

 

--> 처리 시간이 짧은 프로세스는 상위의 큐에서 종료될 것이고, 짧은 대기시간을 지니게 됨

 RR만 사용하는 것보다 더 CPU 사용시간이 짧은 작업에게 우선순위를 주는 방식.

 

6.Real time Scheduling

• Hard real time systems - 반드시 특정 시간안에 끝내야하는 작업을 스케쥴링, n초안에 x초 이상은 무조건 CPU 를 주도록 스케줄링 하는 방법등이 있음.
• Soft real time computing - 반드시는 아님 하지만 특정 시간안에 끝내주면 좋겠음.  일반 프로세스에 비해 높은 priority 를 주어 처리하는 방식을 사용

7. 쓰레드의 스케줄링

• Local Scheduling - User level 쓰레드의 스케줄링. 사용자 수준의 쓰레드 라이브러리에 의해 결정
• Global Scheduling - Kernal level 쓰레드의 스케줄링. 프로세스와 같이 커널의 단기 스케줄러가 스케줄링을 결정