[OS] CPU Scheduling

✔️ CPU Scheduling (CPU가 1개 있는 시스템)

◾️ CPU를 사용하려는 프로세스 사이에서 우선순위를 관리하는 작업

◾️ CPU스케줄링을 통해 CPU 이용률, 처리량을 향상시킬 수 있다.

◾️ CPU 스케줄링을 통해 프로세스의 소요시간, 대기시간, 응답 시간을 줄일 수 있다. 

◾️ I/O 작업이 빈번하게 이루어지는 프로그램이 있다. (사람하고 인터렉션을 자주하는 프로그램)

◾️ 반면, I/O 작업이 빈번하게 이루어지지 않는 프로그램이 있다. (공학 계산기 프로그램)

◾️ 위 두 프로그램에 대해 CPU를 적절히 할당 해줘야한다. (I/O 작업이 빈번하게 이루어지는 프로그램에 대해 적절히 CPU를 할당해줘야 사람 입장에서 답답하지 않다.)

 

컴퓨터시스템 안에 있는 I/O bound job(사람이랑 인터렉션을 자주하는 프로그램)과 CPU bound job(CPU만 오래쓰는 프로그램)이 공존하기 때문에 CPU Scheduling이 필요하다. 

---

✔️Scheduling Criteria (좋은 스케줄링의 성능 척도)

◾️ CPU utilization (이용률): CPU가 놀지않고 일한 시간의 비율, 가능한 CPU는 바쁘게 일을 시켜라

◾️ Throughput(처리량) : 주어진 시간동안 몇개의 작업을 완료했는가 (작업 완료는 프로그램 전체의 완료가 아님, 그냥 cpu의 관점에서 어떤 프로세스가 cpu를 쓰러와서 i/o 작업을 하러 나갈때까지 걸린시간)

◾️ Trunaround time(소요시간) : cpu를 쓰러들어와서  eady 큐에서기다리고나서 runing하고 나갈떄까지 걸린시간 

◾️ Waiting time(대기시간) : cpu를 사용하기위해 ready 큐에서기다리는 시간

◾️ Response time(응답시간) : ready 큐에 들어와서 처음으로 cpu를 얻기까지 걸린시간 

---

✔️비선점형 스케줄링 (Non-preemptive Scheduling)

◾️ 어떤 프로세스가 CPU를 사용하고 있을때, 다른 프로세스가 강제로 CPU를 빼앗을 수 없는 스케줄링이다.

◾️ 현재 CPU를 잡고 있는 프로세스가 종료된 다음 다른 프로세스가 CPU를 사용할 수 있다. 

1️⃣ FCFS(First-Come First-Served)

◾️ Ready Queue에 먼저 들어온 순서대로 CPU를 할당하는 스케줄링이다. (FIFO)

◾️ CPU를 오래 쓰는 프로세스가 먼저 도착하면, 다른 프로세스들은 모두 오래 기다려야 하는 단점이 있다.

 

2️⃣ SJF(Shortest-Job-First)

◾️ CPU 수행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 스케줄링이다.

◾️ CPU 수행 시간이 긴 프로세스는 영원히 CPU를 할당 받지 못할 수 있다. (Starvation)

실제로 CPU 수행 시간은 미리 알 수 없다. 하지만 과거의 CPU 사용 패턴으로 추정할 수 있다.

◾️ 우선순위 스케줄링의 일종이라고 생각할 수 있다. 

---

✔️선점형 스케줄링(Preemptive Scheduling)

◾️ 어떤 프로세스가 CPU를 사용하고 있을때, 다른 프로세스가 강제로 CPU를 빼앗을 수 있는 스케줄링이다.

◾️ 현재 CPU를 잡고 있는 프로세스가 있더라도, 다른 프로세스가 CPU를 빼앗을 수 있다.

 

1️⃣ SRTF(Shortest-Remaining-Time-First)

◾️ SJF의 선점 버전이다.

◾️ 현재 CPU를 잡고 있는 프로세스의 남은 수행 시간보다 더 짧은 수행시간을 시간 프로세스가 도착하면 그 프로세스에게 CPU를 빼앗아 준다. 

◾️ 수행 시간이 매우 긴 프로세스에 대해 Starvation이 발생할 수 있다.

 

2️⃣ RR(Round Robin)

◾️ 시분할 시스템을 위해 설계된 스케줄링이다. (응답시간이 빠르다.)

◾️ 각 프로세스에게 동일한 크기의 CPU 할당 시간(time quantum)을 부여한다. 

◾️ 기본적으로 FCFS 스케줄링인데, 각 프로세스는 Time Quantum 만큼만 CPU를 사용하고 다시 Ready Queue로 돌아간다.

◾️ Time Quantum이 커지면 FCFS와 같아지고, Time Quantum이 작아지면 Context Switch 오버헤드가 커진다.

 

3️⃣ Priority Scheduling

◾️ 우선순위가 높은 프로세스에게 CPU를 먼저 할당하는 스케줄링이다.

◾️ 현재 수행중인 프로세의 우선순위보다 더 높은 우선순위를 가지는 프로세스가 Ready Queue에 도착하면, CPU를 뺏어준다.

◾️ 우선순위가 낮은 프로세스에 대해 Starvation이 발생할 수 있다.

◾️ 우선순위 스케줄링의 문제점은 기아현상이다. 

 

4️⃣ Multilevel Queue Scheduling

📌 Ready Queue를 여러 개로 분할한다. 각 큐는 우선순위가 존재한다. 

◾️ foreground 큐  : 사용자 인터렉션이 많은 프로그램이 들어가는 큐

◾️ background 큐 : 사용자 인터렉션이 많지 않은 배치 프로그램이 들어가는 큐

📌 각 Queue는 독립적인 스케줄링 알고리즘을 갖는다.

◾️ foreground 큐에는 RR 스케줄링을 적용한다.

◾️ background 큐에는 FCFS 스케줄링을 적용한다.

📌 Queue와 Queue간에 스케줄링이 필요하다.

◾️ Fixed priority scheduling : 큐의 우선순위를 기준으로 CPU를 할당한다. (foreground 큐 serve가 끝난후 background serve가 이루어짐)

◾️ Time slice : 각 큐에 CPU time을 적절한 비율로 할당한다. (80% to foreground in RR, 20% to background in FCFS)

 

MLQ 시각화

 

4️⃣ Multilevel Queue Feedback Scheduling

◾️ MLFQ에서는 프로세스가 다른 큐로 이동할 수 있다.

◾️ CPU burst time이 긴 프로세스는 우선순위가 낮은 큐로 점점 이동된다.

◾️ 우선순위가 낮은 큐에서 너무 오래 대기하는 프로세스가 있다면, 해당 프로세스는 우선순위가 높은 큐로 이동한다. 

 

MLFQ 시각화

 

---

✔️ Multiple Processor Scheduling (CPU가 여러개 있는 시스템)

1️⃣ Homogeneous processor인 경우

◾️ 프로세스들을 Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 한다.

◾️ 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해진다.

2️⃣ Load sharing 

◾️ 특정 CPU만 수행되어서는 안된다. 일부 프로세서 job이 몰리지 않도록 부하를 적절히 공유하는 매커니즘이 필요

◾️ CPU마다 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법

3️⃣ Symmentric Multiprocessing (SMP)

◾️ 모든 CPU가 대등한 경우이다. 각 CPU가 각자 알아서 스케줄링을 결정한다. 

4️⃣ Asymmetric multiprocessing

◾️ 하나의 CPU가 전체적인 컨트롤을 담당한다.

◾️ 하나의 CPU는 시스템 데이터의 접근과 공유를 책임지고 나머지 CPU는 거기에 따른다. 

 

---

✔️ Real-Time Scheduling

◾️ Dead Line을 보장하는 실행을 하기위한 스케줄링

1️⃣ Hard real-time systems

◾️ Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링 해야한다. 

2️⃣ Soft real-time cpmputing

◾️ Soft real-time task는 다른 프로세스에 비해 높은 priority를 갖도록 해야한다. (Dead Line을 꼭 보장 하지는 못함)

 

---

✔️ Thread Scheduling

1️⃣ Local Scheduling

◾️ User level thread의 경우 사용자 수준의 thread libary에 의해 어떤 thread를 스케줄링 할지 결정

◾️ User level thread의 경우 운영체제는 thread를 모른다. 운영체제는 process 스케줄링을 결정할 뿐이다. process는 CPU를 할당받으면, thread를 내부적으로 스케줄링한다.

 

2️⃣ Global Scheduling

◾️ Kernel level thread의 경우 일반 process와 마찬 가지로 Kernel의 단기 스케줄러가 어떤 thread를 스케줄링할지 결정한다. 

 

---

✔️용어정리

◾️ CPU burst : CPU에서 instruction을 실행하는 단계

◾️ I/O burst : 오래걸리는 I/O 작업의 단계

◾️ Aging : 오래 기다린 프로세스의 우선순위를 높여주는것