[운영체제] CPU 스케줄링 (1)

CPU 스케줄링

# 선점형 VS 비선점형
# 성능척도
# 스케줄링 알고리즘
# FCFS
# SJF
# Priority Scheduling
# 다음 CPU Burst Time의 예측
# Round Robin (RR)

---

✍️ 본 포스팅은 이화여자대학교 반효경 교수님의 "운영체제" 강의를 들으며 정리한 내용입니다.

 

---

＊선점형 VS 비선점형

- 선점형 스케줄링(nonpreempfree)

• 필요 시 동작중인 프로세스의 CPU를 강제로 빼앗는 스케줄링

- 선점형 스케줄링(preempfree)

• CPU를 강제로 빼앗지 않고, 한 번 CPU를 프로세스에 주면 작업이 끝나고 난 뒤에야 제어권 획득

 

＊성능척도

- 시스템 입장에서의 성능 척도

• CPU Utilization(이용률) : 전체 시간 중 CPU가 놀지 않고 일한 비율
• Throughput(처리량) : 주어진 시간 기준 얼마나 처리가 가능한가

- 프로그램 입장에서의 성능 척도

• Turnaround time(소요시간/반환시간) : CPU를 쓰러 들어와서 다쓰고 나갈 때 까지 걸린 시간(대기 시간 포함)
• Waiting time(대기 시간) : CPU를 쓰기 위해 줄서서 기다린 총 시간
• Response time(응답 시간) : CPU 얻으러 들어와서 최초 CPU 얻기 까지 걸린 시간

---

＊스케줄링 알고리즘

- FCFS (First-Come First-Served)

- SJF (Shortest-Job-First)

- SRTF(Shortest-Remaining-Time-First)

- Priority Scheduling

- RR (Round Robin)

- Multilevel Queue

---

＊FCFS (First-Come First-Served)

• 먼저 온 순서대로 처리하는 방법
• 비선점형 스케줄링
• 예시 : P1, P2, P3 모두 0초에 도착(간발의 차로 순서 결정됨)
  • Process : P1 / 24(Burst Time)
  • Process : P2 / 3(Burst Time)
  • Process : P3 / 3(Burst Time)
• Waitin time : P1 = 0 / P2 = 24 / P3 = 27
• Average waiting time : (0 + 24 + 27) / 3 = 17

• Waitin time : P1 = 6 / P2 = 0 / P3 = 3
• Average waiting time : (6 + 0 + 3) / 3 = 3

-> 이처럼 긴 프로세스가 먼저 도착해서 짧은 프로세스들이 지나치게 길게 기다려야 하는 현상을
"Convoy effect"라고 한다.

---

 

＊SJF(Shortest-Job-First)

• CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
• 각 프로세스와 다음번 CPU burst time을 가지고 스케줄링에 활용
• Two schemes
  • Nonpreemptive : 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점 당하지 않음
  • Preemptive : 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 갖는 새 프로세스가 도착하면 CPU를 빼앗는다. 이 방법은 SRTF(Shortest-Remaining-Time-First)라고도 부른다.
• SJF is optimal : 주어진 프로세스들에 대해 minimum average waiting time을 보장(Preemptive 방법 기준)

1. Nonpreemptive 예시

• Average waiting time : 4초

2. Preemptive 예시

• Average waiting time : 3초

- SJF의 문제점

1. 긴 프로세스가 Starvation(영원히 CPU를 얻지 못함) 상태가 될 수 있다

2. CPU 스케줄링 시, 사용시간을 정확히 알 수 없다는 문제(추정해서 보통 사용)

 

---

＊다음 CPU Burst Time의 예측

• 추정만이 가능
• 과거의 CPU burst time을 이용해서 추정

-> n-1 등을 공식에 대입해 점화식을 전개해보면

-> 이와 같이 나온다.

-> a와 1-a는 각각 0보다 작으므로 곱할수록 점점 값이 작아진다.

-> 즉, 해당 예측 방법은 최근일수록 가중치를 높게 반영, 과거일수록 가중치를 적게 반영한다.

---

＊Priority Scheduling

• 우선순위가 높은 프로세스에게 CPU를 할당하는 방법
• 보통 숫자가 작을수록 높은 우선순위를 부여하는 방법을 사용
• SJF는 일종의 Priority Scheduling이다

-> 문제점

• 우선순위가 낮은 프로세스가 Starvation(영원히 CPU를 얻지 못하는 상황) 발생 가능성

-> 해결방법

• Aging(노화) : 아무리 낮은 우선순위를 가졌더라도, 오래 기다리게 되면 우선순위를 높여주는 방법

---

＊Round Robin (RR)

• q= 20인 경우의 예제

• 각 프로세스는 동일한 크기의 할당 시간을 가짐 (일반적으로 10~100 millsecends)
• 할당 시간이 지나면 프로세스는 선점당하여, ready queue의 제일 뒤에 가서 다시 줄을 선다.
• n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n 을 얻는다.
  -> 각 프로세스는 적어도 (n-1)q time unit 이상 기다리지 않는다.
• 작업시간이 길수록, 선점 당하는 횟수도 늘어나 대기시간이 길다는 특징이 있다.
• 장점 : Response Time(응답 시간)이 매우 빠르다는 장점 / 또한 사용시간을 예측할 필요도 없다
• Performence
  • q large(q가 아주 큰 경우) : FCFS
  • q small(q가 아주 작은 경우) : context switch 오버헤드가 커진다(너무 많이 할당이 바뀌니까)