OS - CPU Scheduling 1

---

🚀 OS - Process Management 2 에서 이어지는 내용입니다.

🧩 CPU Scheduling

컴퓨터 프로그램이 실행될 때는 위와 같은 단계를 거친다. CPU에서 instruction을 실행하는 단계를 CPU burst라고 한다. I/O 작업이 중간에 많이 끼게되면 CPU burst가 짧아지고, 그와 반대로 CPU burst가 길어지는 순간도 존재한다.

이렇듯 컴퓨터 프로그램의 실행은 CPU burst가 길수도 있고, 짧을수도 있게 다양하게 나타난다. 따라서 이러한 다양한 것들을 통제하기 위해 스케줄링이 필요하다.

여기서 CPU 스케줄링은 현재 ready queue에 들어와 있는 프로세스중에 어떤 프로세스에 CPU를 줄 것인지를 결정하는 것이다.

CPU 스케줄링엔 두가지 주요한 이슈가 있다.

• CPU를 어떤 프로세스에게 줄 것인가.
• CPU burst가 길어지면 CPU를 뺏을 수 있게 할 것인가.

🧩 CPU Scheduling의 종류

CPU Scheduling에는 크게 두 종류가 있다. 비선점형과 선점형이다.

• 비선점형은 I/O 작업이 들어오기 전까지 CPU를 보장해주는 방법이다.
• 선점형은 timer를 두고 CPU를 강제로 빼앗을 수 있게 하는 방법이다.

여기서 일정한 기준을 두고 CPU Scheduling을 정해야 하는데 이것을 Scheduling criteria(성능 척도)라고 한다.

• CPU utilization(이용률) : 전체 시간 중에서 CPU가 쉬지 않고 일한 비율
• Throughout(처리량) : 주어진 시간동안 몇 개의 작업을 처리했느냐
• Turnaround time(소요시간) : CPU를 쓰러 들어와서 다 쓰고 나갈때까지 걸린 시간
• Waiting time(대기시간) : CPU를 기다린 시간
• Response time(응답시간) : ready queue에 들어오고 난 후 처음으로 CPU를 얻기 전까지 걸린 시간

위의 두가지는 시스템 입장에서 성능 척도이고, 나머지 세개는 프로그램 입장에서의 성능 척도이다. 시스템 입장에서의 성능 척도는 시스템 입장에서 CPU 하나를 가지고 최대한 많은 일을 처리시키면 좋은거고, 프로그램 입장에서의 성능 척도는 내가 CPU를 빨리 얻어서 빨리 끝내면 좋은 것이다.

위에서 대기시간과 응답시간의 차이는 선점형 스케줄링에서 한번 CPU를 얻었다고 해서 무한정 CPU를 쓰는 것이 아니다. 이런 상황에서 기다린 시간을 전부 합친 시간이 대기시간이고, 응답시간은 최초에 CPU를 얻게 된 시간을 말한다.

또 여기서 착각하면 안되는게 위에서 말한 요소들은 매 CPU burst마다 측정하는 요소이다. 전원을 켜고 끌때까지의 얘기가 아니다.

이제 스케줄링의 종류마다 알아볼 차례이다.

🧩 FCFS(First-Come First-Served)

• 가장 먼저 요청한 프로세스에 CPU를 할당해주는 방식
• 비선점형 스케줄링
• 그다지 효율적이지 않음
• 제일 먼저 들어온 프로세스가 CPU를 오래잡을수도 있음
• 앞에 어떤 프로세스가 먼저 오냐에 따라 평균 대기 시간과 응답 시간이 길어질 수 있다.
• convey effect : 긴 프로세스 하나때문에 짧은 프로세스들이 오래 기다려야 하는 현상

🧩 SJF(Shortest-Job-First) 스케줄링

비선점형 SJF

선점형 SJF

• 다음 CPU burst time의 길이를 고려해서 스케줄링을 결정하는 알고리즘
• 비선점형과 선점형이 따로 존재
• 비선점형에서 실행되고 있는 프로세스는 끝까지 실행한다.
• 선점형에서는 현재 실행되고 있는 프로세스의 남은 시간보다 도착한 다음 프로세스가 더 빨리 끝날 수 있는 프로세스라면 다음 프로세스를 실행하도록 바꾼다. SRTF(Shortest Remaining Time First)라고도 부른다.
• 주어진 프로세스들에 대해 최소한의 평균 대기 시간을 보장한다. (선점형에서)

SJF 단점

• Starvation : 만약 CPU사용시간이 긴 프로세스이면 앞에 CPU 사용시간이 짧은 프로세스들을 기다리다가 영원히 실행되지 않을 수도 있다.(중간중간에 CPU 사용시간이 짧은 프로그램이 계속 들어오면)
• 다음 프로세스의 CPU burst time을 예측하는 것이 어렵다.(과거 CPU사용량으로 어느정도 예측은 가능하지만 정확하지는 않음 / Exponential Averaging 수식)

🧩 Priority Scheduling

• 각각의 프로세스에 우선순위 넘버가 있다.
• 작은 숫자가 우선순위가 높은 것이다.
• 가장 높은 우선순위의 프로세스에 CPU를 할당한다.
• 선점형과 비선점형이 나뉜다.
• SJF도 일종의 priority 스케줄링이라고 할 수 있다.
• Starvation이 발생할 수 있다.(우선순위가 낮은 프로세스가 영원히 CPU를 얻지 못할 가능성)
• Starvation을 해결하기 위해 Aging을 사용할 수 있다. 여기서 Aging이란 시간이 지날수록 프로세스의 우선순위를 높여주는 것이다.

🧩 Round Robin(RR)

• 대부분 현대적 컴퓨팅 시스템에서 사용하는 스케줄링
• 각각의 프로세스에 동일한 CPU 할당 시간을 부여해서 해당 시간 동안만 CPU를 이용하게 한다.
• 할당 시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다.
• n개의 프로세스가 ready queue에 있고 할당시간이 q time인 경우 각 프로세스는 최대 q time 단위로 CPU시간의 1/n을 얻는다. => 어떤 프로세스도 (n-1)q time 이상 기다리지 않는다.
• 기다리는 시간이 본인이 CPU를 사용하는 시간에 비례하게 된다.
  - 일반적으로 SJF보다 average turnaround time이 길지만 response time은 더 짧다. (하지만 일반적으로는 짧은 프로세스와 긴 프로세스가 섞여있어서 RR방식이 더 효율적이다.)

q large => FCFS
q small => context switch의 오버헤드가 커진다.