운영체제 강의 14

📌 Scheduling Algorithms

• FCFS (First-Come First-Served)

• SJF (Shortest-Job-First)

• SRTF (Shortest-Remaining-Time-First)

• Priority Scheduling

• RR (Round Robin)

• Multilevel Queue

• Multilevel Feedback Queue

 

1. FCFS (First-Come First-Served)

◎ FCFS : nonpreemptive

◎ Convoy effect : short process behind long process

 

2. SJF (Shortest-Job-First)

‣ 각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용

‣ CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄

‣ Two schemes:

      ✓ Nonpreemptive : 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점 당하지 않음

      ✓ Preemptive : 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면                                       CPU를 빼앗김

                                 이 방법을 Shortest-Remaining-Time-First (SRTF)이라고도 부른다

‣ SJF is optimal : 주어진 프로세스들에 대해 minimum average waiting time을 보장

 

---

 

♦️ 다음 CPU Burst Time의 예측

다음번 CPU burst time을 어떻게 알 수 있는가?

추정만이 가능하다

과거의 CPU burst time을 이용해서 추정 (exponential averaging)

 

1 : 실제 과거의 CPU burst값 (n번째)     2 :  다음 CPU burst 예측값

 

(직전 것을 더 많이 반영, 그 전꺼는 점점 더 적게 반영한다)

 

3. Priority Scheduling

• highest priority를 가진 프로세스에게 CPU 할당 (smallest integer = highest priority)

       ✓ Preemptive

       ✓ Nonpreemptive

• SJF는 일종의 priority scheduling이다 (priority = predicted next CPU burst time)

• Problem

       ✓ Starvation : never execute

• Solution

       ✓ Aging : as time progresses increase the priority of the process

 

4. Round Robin (RR)

각 프로세스는 동일한 크기의 할당시간을 가지고 그 시간이 지나면 선점당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다

n개의 프로세스, q의 할당 시간인 경우, 어떤 프로세스도 (n-1)q 이상 기다리지 않는다

 

• q large → FCFS와 같다

• q small → context switch 오버헤드가 커진다

 

📌 일반적으로 SJF보다 average turnaround time이 길지만 response time은 더 짧다