11. Process Scheduling (2)

 

1. Starvation : CPU가 바빠서 프로세스가 CPU를 할당받지 못하는 것
2. Preemptive Scheduling
   1. OS 가 현재 사용하고 있는 프로세스를 멈출 수 있다.
3. Non-Preemptive Scheduling
   1. CPU를 사용하고 있는 프로세스가 자발적으로 CPU 사용을 해제함
   2. 멀티프로그래밍에서는 기본적으로 Preemptive Scheduling 사용
4. Batch System : 최대한 처리를 많이해야 하는 시스템, Throughput, CPU Utilization이 중요한 시스템
5. Interactive System : 성능이 아니라 Response time이 중요한 시스템
6. 스케줄링 기준
   1. 높으면 좋은 것
      1. CPU Utilization
      2. Throughput
   2. 낮으면 좋은 것
      1. Turnaround time : 완료되는 시간
      2. Waiting time : 대기시간
      3. Response time : task가 도착해서 잠깐 기다리다가 assign 되고 실행될 때까지 걸리는 시간 
7. 스케줄링 종류
   1. FCFS (= First Come First Served)
      1. 먼저 온 프로세스부터 처리하는 것
      2. Non-preemptive (뺏지 않음)
      3. Starvation이 없다. 내 순서가 오면 내가 할당되기 때문
   2. SJF (= Shortest Job First)
      1. CPU burst가 가장 짧은 것부터 처리하는 것
      2. Non-preemptive (뺏지 않음)
      3. Starvation 발생할 수 있다. CPU burst 큰 것 계속 들어오면 할당 못해준다.
   3. SRTF (= Short Remaining Time First)
      1. SJF의 preemptive version
      2. Preemtive (뺏음)
      3. CPU를 할당받아 수행중이더라도 CPU Burst time이 현재 남은 시간보다 짧으면 넘겨준다.
   4. Priority Scheduling
      1. 우선순위(Priority)에 따라 CPU를 할당하는 것
      2. Preemtive, Non-preemtive 둘다 존재한다.
      3. 문제점 : 
         1. Starvation : 낮은 Priority를 가지면 할당되지 못할 수 있다.
            • 해결법 :
              • Aging : 기다리는 시간에 따라 Age를 부여하여 Priority를 높여준다.
                             Priority Boosting
         2. Priority Inversion : 제 3의 task가 끼어들어 높은 Priority task를 진행하지 못하게 한다. 
            
            1. 해결법 :
               • Priority Ceiling Protocol (PCP) : Shared resource를 잡으면 priority를 높여주고 필요 없으면 다시 놓아주는 방식
               • Priority Inheritance Protocol (PIP) : Shared resource가 필요하다면 Priority를 높여주는 방식
   5. Round Robin Scheduling
      1. CPU를 time quantum(시간단위)으로 할당하며, 할당한 time quantum이 되면 강제로 CPU 사용을 해제한다.
      2. Preemtive (뺏음)
      3. 특징
         1. Ready quque 내의 프로세스 수 = n
            time quantum = q
            각 프로세스의 대기 시간 = 최대 (n-1)*q
         2. q가 클 경우 FCFS와 같아지게 된다.
            q가 작을 경우 context switching이 많아진다.
   6. Mutilevel Queue Scheduling

 

---

****

Starvation : 모종의 이유로 인해서 CPU를 할당하지 못하는 것 

각 프로세스들이 CPU를 나눠먹어서 골고루 진행할 수 있도록 해야한다.

---

****

Preemptive Scheduling  시험은 영어로 써야한다.

CPU를 잠깐 쓰렴 하고 CPU를 줬는데 다른걸 하기위해 CPU를 다른 프로세스에게 넘겨주는 스케줄링

 

****

Non-preemptive Scehduling

프로세스가 반환할 때 까지 끝까지 기다리는 스케줄링

얌전히 기다리는 스케줄러

 

---

프로세스들이 CPU를 fair하게 가져가야 한다.

최대한 처리를 많이 하는 시스템을 Batch System 이라고 한다.

성능을 뽑아내는게 중요한게 아니라 interrupt 처리를 해서 Response time이 중요한 시스템을 Interactive System이라고 한다.

---

스케줄러의 성능을 얘기할 때 5가지를 중요시 한다.

 

높을수록 좋은 것

CPU utilization

Throughput 이 높을수록 컴퓨터를 더 빨리 쓸 수 있다.

 

낮으면 좋은것

Turnaround time : 어떤 일이 들어왔을 때 완료가 되는 시간

Response time : task가 도착했을 때 조금 기다려야 한다. assign이 됐다가 기다렸다가 실행 될 때까지의 시간

Waiting time : 대기 시간

---

먼저 온 프로세스부터 스케줄링 하는 것.

Non-premptive 하다.

내 순서가 오면 언젠간 나에게 할당되기 때문에 starvation이 없다.

 

 

(P1의 waiting time + P2의 waiting time + P3의 waiting time) / 3 = 17

(P1의 turnaround time + P2의 turnaround time + P3의 turnaround time) / 3 = 27

---

CPU burst가 짧은 것부터 돌리자.

task가 한번 assign이 되면 줬다가 뺏진 않으므로 Non-preemptive하다.

Starvation이 발생할 수 있다. 짧은 CPU burst가 계속 들어온다면 원래 있던 process를 할당할 수 없기 때문이다.

얼마만큼의 CPU burst가 필요할까를 계산할 수 없다.

 

---

새로온 애가 더 짧으면 현재 돌고있는 애를 preemptive 시켜서 더 짧게 걸리는 애를 주자.

Starvation이 있지 않을까?