(8) CPU Scheduling

1. CPU 스케줄링이란?

1-1) 정의

CPU를 잘 사용하기 위한 프로세스 우선순위 배정

최고의 성능을 내기 위해 자원을 어떤 프로세스에 얼마나 할당하는지 정책을 만드는 것을 CPU스케줄링이라고 함

 

1-2) 좋은 스케줄링 조건

1) 오버헤드 ↓
2) 사용율(CPU를 최대로 바쁘게) ↑

3) 기아 현상(starvation) ↓

 

1-3) 스케줄링의 필요성

(a) 프로세스의 생명주기

[프로세스 생명주기 설명▼]

프로세스의 상태 전이

 

✓ 승인 (Admitted) : 프로세스 생성이 가능하여 승인됨.

✓ 스케줄러 디스패치 (Scheduler Dispatch) : 준비 상태에 있는 프로세스 중 하나를 선택하여 실행시키는 것.

✓ 인터럽트 (Interrupt) : 예외, 입출력, 이벤트 등이 발생하여 현재 실행 중인 프로세스를 준비 상태로 바꾸고, 해당 작업을 먼저 처리하는 것.

✓ 입출력 또는 이벤트 대기 (I/O or Event wait) : 실행 중인 프로세스가 입출력이나 이벤트를 처리해야 하는 경우, 입출력/이벤트가 모두 끝날 때까지 대기 상태로 만드는 것.

✓ 입출력 또는 이벤트 완료 (I/O or Event Completion) : 입출력/이벤트가 끝난 프로세스를 준비 상태로 전환하여 스케줄러에 의해 선택될 수 있도록 만드는 것.

추가 참조 : https://korshika.tistory.com/138

(4) 인터럽트

> main program으로 복귀할 때 ( 선점 방식 ) 혹은 process termination 이후 ( 비선점 방식)

   스케줄링을 PCB(Process Control Block)에서 데이터를 보고 알고리즘으로 선택하여 process 수행을 결정

 

(b) 스케줄링 필요성

※ CPU 스케줄링의 필요성

I/O, interrupt(trap)등이 발생하면 해당 원인 선처리 후, main program으로 복귀하는데

이 때 waiting 상태로 바뀐 main program 혹은 다른 wait 상태의 program 들을 우선순위를 결정하여

(wait 상태이어도 CPU를 점유하고 있음)
최종적으로 가장 효율적인 process 우선순위를 결정하는 것이 CPU 스케줄링의 의미

 

https://korshika.tistory.com/141

(6) PCB & Context Switching

에서 확인할 수 있듯, I/O, interrupt 등이 발생하면 PCB가 저장되고, context swtching이 일어나 overhead가 발생하기 때문에 효율적인 작업순서가 고려되어야 한다

 

1-4) 스케줄링의 목표

1. Batch System : 가능하면 많은 일을 수행, 시간(time) 보다는 처리량(through-out)이 중요
2. Interactive System : 빠른 응답시간, 적은 대기시간
3. Realtime System : 기한(deadline) 맞추기

 

 

2. 선점 / 비선점 스케줄링

• 선점( Preemptive )
  OS가 CPU의 사용권을 선점할 수 있는 경우, 강제 회수하는 경우
  - CPU 이용을 우선순위 높은 프로세스가 강제로 차지할 수 있음
  - 우선순위 높은 프로세스 처리가 먼저 일어나야할 경우 유용, 추가적인 overhead 발생으로 처리시간 예측 힘듦
  - IO요청 / 응답, Interrupt, 작업완료 시점에서 스케줄링이 일어날 수 있음
• 비선점( Non-Preemptive )
  프로세스 종료 OR I/O 등의 이벤트가 있을 때까지 실행 보장
  - 작업 완료시에만 스케줄링

 

 

3. 스케줄링 알고리즘

3-1) 선점 스케줄링

1-1. SRT(Shortest Remaining Time) 스케줄링: 짧은 시간 순서대로 프로세스를 수행한다. 남은 처리 시간이 더 짧은 프로세스가 Ready 큐에 들어오면 그 프로세스가 바로 선점됨. 아래에 소개할 SJF의 선점 버전이라고 할 수 있다.

 

1-2. 라운드로빈(Round-Robin)스케줄링: 각 프로세스는 같은 크기의 CPU 시간을 할당 받고 선입선출에 의해 행된다. 할당시간이 너무 크면 선입선출과 다를 바가 없어지고, 너무 작으면 오버헤드가 너무 커진다.

 

1-3. 다단계 큐(Multi-level Queue) 스케줄링: Ready큐를 여러 개 사용하는 기법. 각각의 큐는 자신의 스케줄링 알고리즘을 수행하며, 큐와 큐 사이에도 우선순위를 부여한다.

 

1-4. 다단계 피드백 큐 스케줄링: 다단계 큐와 비슷하나 프로세스들이 큐를 이동할 수 있다.

 

3-2) 비선점 스케줄링

1-1.  HRN(Highest response ratio next) 스케줄링: 긴 작업과 짧은 작업간의 지나친 불평등을 어느 정도 보완한 기법. 수행시간의 길이와 대기 시간을 모두 고려해 우선순위를 정한다.

 

1-2. SJF(Shortest Job First) 스케줄링: 큐 안에 있는 프로세스 중 수행시간이 짧은 것을 먼저 수행. 평균 대기 시간을 감소시킨다.

 

1-3. 우선순위(priority) 스케줄링: 프로세스에게 우선순위를 정적, 혹은 동적으로 부여하여 우선순위가 높은 순서대로 처리한다. 동적으로 부여할 경우, 구현이 복잡하고 오버헤드가 많다는 단점이 있으나, 시스템의 응답속도를 증가시킨다.

 

1-4. 기한부(Deadline) 스케줄링: 작업을 명시된 시간이나 기한 내에 완료하도록 계획.

 

1-5. FIFO 스케줄링: 프로세스들은 Ready큐에 도착한 순서대로 CPU를 할당 받는다. 작업 완료 시간을 예측하기 매우 용이하다. 하지만 덜 중요한 작업이 중요한 작업을 기다리게 할 수도 있다.

출처: https://preamtree.tistory.com/19 [Preamtree의 행복로그]

 

 

4. 스케줄링의 척도

1. Response Time
   • 작업이 처음 실행되기까지 걸린 시간
2. Turnaround Time
   • 실행 시간과 대기 시간을 모두 합한 시간으로 작업이 완료될 때 까지 걸린 시간

---

참조

https://gyoogle.dev/blog/computer-science/operating-system/CPU%20Scheduling.html

CPU Scheduling | 👨🏻‍💻 Tech Interview

https://preamtree.tistory.com/19

[IT 기술면접 준비자료] CPU 스케줄링 기법 (선점 스케줄링, 비선점 스케줄링)