📌 CPU Scheduling 1

📖 01. Scheduling Algorithms

• 크게 두가지로 나누어 보면
  -> noncreemptive (=자진 반납)
  -> creemptive (=강제로 빼앗음) : Timer를 통해

📖 02. Scheduling Criteria -> Performance Index (= Performance Measure, 성능 척도)

• 어떤 알고리즘이 좋은지 평가 할 수 있는 방법이 필요함.

크게 두가지로 나눌 수 있다.
1) 시스템 입장
-> CPU utilization, Throughput

2) 프로그램 입장

• Utilization : CPU가 놀지 않고 일한 시간의 비율을 나타냄
  -> 가능한 바쁘게 일시켜라

• Throughput : 주어진 시간동안에 몇개의 작업을 완료했느냐

• Turnaround time : 프로세스가 시작해서 끝날 때까지 걸리는 시간 걸리는 시간 (CPU burst + waiting : 실행시간 + 대기시간)

• Waiting Time : 프로세스가 준비 큐(Ready Queue)에서 대기한 시간의 총합

• Response Time : 레디큐에 들어와서 처음으로 CPU를 얻기까지 걸리는 시간

• Ready Queue에 들어온 프로세스를 대상으로 관심있는 것들이다.
  -> ready queue에 들어온 프로세스의 Throughput이 어땟는지 utilization 어땟는지를 고려하여 스케쥴링을 한다!!

📖 03. FCFS (First-Come First-Served)

• 첫번째 온 손님에게 첫 서비스 해주기
• nonpreemptive 스케줄링이다.
  -> 효율적이지 않다.
  -> CPU를 오래쓰는 친구가 도착하면 다른친구들이 기다려야 한다.

• 앞에있는 프로세스의 영향을 많이 받는다.

📖 04. SJF (Shortest-Job-First)

• CPU가 조금 필요한 친구한테 먼저 제어권을 주자!

• Nonpreemptive방식 : 자신보다 빨리 끝낼 수 있는 프로세스가 오더라도 CPU birst 보장

• preemptive : CPU를 줬다고 하더라고 더 짧은 프로세스가 도착하면 CPU제어권을 넘겨줌

• 이전에 CPU를 사용했기 때문에 남은 시간을 비교해서 CPU제어권을 넘겨줄지 말지 결정(Shortest-Remaining-Time-First라고 부른다.)

• SJF is optimal -> preemptive 스케줄러일 때 최소 보장

📖 05. Example of Non-Preemptive SJF

📖 06. Example of Preemptive SJF

-> 이와 같은 예제에서 어떤 알고리즘을 사용하더라도 3초 미만이 될 수 없다 (최소이다)

• 두가지 문제점이 존재한다.

1. starvation(기아 현상) : CUP 사용시간이 긴 프로세스는 영원히 실행이 되지 않을 수 있다.
2. CPU 사용시간을 미리 알 수 없다.

1. T : 실제 CPU burst 사용시간
2. 타우 : CPU burst 예측시간

📖 07. Exponential Averaging

마지막 : 다 적은 가중치 값을 가진다.

📖 08. Priority Scheduling

• 우선순위가 제일 높은 프로세스에게 CPU를 주겠다

• Preemptive : 우선순위가 더 높은 프로세스가 도착하면 원래 프로세스에서 CPU제어권을 빼앗고 우선순위가 더 높은 프로세스에게 CPU제어권을 넘겨준다.

• Nonpreemptive : 더 높은 우선순위가 도착하더라도 CPU제어권을 가지고 있는 프로세스가 계속 CPU제어권을 갖고 있는다.

• 작은 정수일수로 높은 우선순위를 갖는다.

• 영원히 CPU를 얻지 못하는 경우가 존재 할 수 있다.

• Solution : 우선순위가 낮더라도 오래 기다렸다면 우선순위를 높여주자.
  -> Aging

📖 09. Round Robin (RR)

• 응답시간이 빨라진다는 장점!
  -> q에 대기시간을 줄이면 빨리 CPU제어권을 얻을 수 있고 CPU를 필요로 하는 시간이 적다면 빨리 종료 될 수 있다.
  -> q의 길이가 짧아짐

• 극단적인 상황 : 대기시간을 아주 크게 잡는다면
  -> FCFS

• 너무 작게 잡는다면 context swich오버헤드가 커진다.

📖 10. Example: RR with Time Quantum = 20

• RR은 프로세스의 종료시간을 모를 때 사용하기 좋다.
  -> 길고 짧은게 섞여있을 때 유리

• Response Time이 빨라진다는 것이 장점이다.

📖 11. Turnaround Time Varies With Time Quantum

[출처] 반효경 교수님 강의