[OS] Ch6_Process Scheduling

Process Scheduling

---

• 컴퓨터에 있는 여러 개의 프로세서를 그것보다 적은 수의 프로세서로 mapping하여 concurrent하게 실행시키기 위한 방법
• 현재 시스템의 ready process중에 다음에 돌려야 되는 프로세스를 찾아서 돌려준다.
• scheduling points
  state transition 할때마다 scheduler가 관여한다.
• 컴퓨터가 프로세스를 관리하는데 effective하게 해야한다. 반드시 효과적인 방식이 필요하다. 보통 queue(linked list)를 사용하여 관리한다.
  

Scheduler와 관련된 concept

---

Starvation
CPU가 있고 프로세스들이 여러개가 있는 상태에서 하나를 돌리다가 다음애를 돌리려고 할때 스케쥴링 되지 못하여 실행하지 못하는 상태

Preemptive Scheduling
resource를 줬다가 갑자기 뺏어갈 수 있느냐 없느냐

• Non-preemptive scheduling
  어떤 프로세스에게 CPU를 할당하고 반환할때까지 온전히 기다리는 스케쥴러
• Preemptive scheduling
  스케쥴러가 CPU를 쓰고 있었던 프로세스를 중단시키고 다른 프로세스에게 넘긴다.

Scheduling Criteria
스케줄링 알고리즘에는 FCFS, SJF, SRTF, RR 방식이 있고, 알고리즘을 평가할 때는 수행 시간(Burst time)과 CPU 사용량(CPU utilization), 단위 시간 당 끝마친 프로세스 개수(Throughput), 하나의 프로세스가 대기한 시간부터 완료될 때까지 걸리는 시간(Turnaround time), 프로세스가 ready queue에서 기다리는 시간(Waiting time), 프로세스가 처음으로 CPU를 할당받기까지 걸리는 시간(Response time)을 기준으로 한다.

FCFS(First-Come, First-Served)

Queue의 FIFO와 동일하다. 먼저 들어온 프로세스를 먼저 프로세서에 할당한다. 앞의 프로세스가 끝나야 뒤 프로세스를 진행하는 non-preemptive이다. 따라서 starvation이 없다. 수행시간이 큰 프로세스가 먼저 들어오면 average turnaround time이 길어진다. 그 뒤에 들어온 프로세스들이 불필요하게 오랜 시간을 기다리는 convoy effect가 발생한다.

SJF(Shortest Job First)

---

가장 실행이 적게 걸릴 거 같은 것(작업 시간이 짧은 것)부터 한다. 따라서 average waiting time이 최소이다. FCFS에서 발생하는 convoy effect를 해결할 수 있다. Burst time이 큰 프로세스는 계속 밀려나 starvation이 발생한다. 프로세스가 끝날 때까지 운영체제가 개입하지 않으므로 non-preemptive이다. Future CPU burst를 다 알고 있어야 한다. (얼마동안 실행될지) Priority scheduling이다.

SRTF(Shortest Remaining Time First)

---

수행 중인 다른 프로세스보다 남은 수행 시간이 적어지면 운영체제가 개입하여 더 적게 남은 프로세스가 실행된다. Preemptive version of SJF으로 priority scheduling이다.

RR(Round Robin)

Time slice(scheduling quantum)라는 일정시간동안 돌리고 안끝나면 다음 프로세스를 돌린다. 프로세스가 끝나지 않아도 time quantum을 다 썻을 때 프로세스를 중단시키므로 preemptive이다. 따라서 starvation이 발생하지 않는다. Response time을 개선한다.

Priority Scheduling

---

• Task에 우선순위를 매겨서 highest부터 처리한다.
• preemptive, non-preemptive 둘 다 가능
• starvation problem
  낮은 priority는 계속 기다리게 된다.
  solution
  • Aging : 너무 오랫동안 안하고 있는 것에 age를 높여 처리한다.
  • priority boosting을 통해 priority를 동적으로 조정한다.
• Priority inversion problem
  프로세스 A, B, C가 존재하고 우선순위가 A>B>C 상태로 A가 가장 높다. 현재 프로세스 A가 running 상태이고 프로세스 B, C가 ready 상태에 있다고 가정한다. 그리고 프로세스 A가 프로세스 C의 결과같을 기다려야 하는 상황이라고 가정한다.(C의 리턴값이 A에게 필요하다.) 그렇게 되면 A는 C로부터 결과값을 받아야지만 나머지 작업을 진행할 수 있으므로, C의 결과값을 기대하면서 Blocked상태로 들어간다. 하지만 A가 CPU를 놓게 되면 우선순위에 따라 프로세스 B가 running 상태로 가서 CPU를 할당받게 된다. 이러면 우선순위가 제일 높은 A가 blocked에서 한없이 기다리고 A보다 낮은 B가 running 상태에서 작업을 진행하는 상태를 의미한다.
  ex)
  
  Task 우선 순위가 Task A > Task B > Task C 3개의 Task가 있다고 가정한다. Task C가 먼저 실행이 되어서 공유 자원을 사용하고 있는 상황에서 Task A가 실행되면 선점을 할 수는 있지만 실행이 되지 못해서 우선순위 역전 현상이 발생한다. 이때 Task B가 실행이 되면 당연히 Task C보다 Task B가 우선수위가 높기 때문에 Task B가 실행이 될테고 Task B가 끝날 때까지 Task C는 실행이 되지 않아서 공유 자원을 반납하지 못한다. 그러던 중 Task B가 실행이 끝나고 Task C가 작업을 마저 끝낸 후 공유자원을 반납한 뒤에야 Task A가 실행된다. 이렇게 되면 우선순위역전되는 시간이 길어지게 되고 Task가 많은 시스템에서 아주 큰 문제가 될 수 있다.
  solution
  • Priority Inheritance Protocol(PIP)
    높은 process가 낮은 process의 resource를 원할 때 낮은 process의 priority를 확 올려줌(A가 blocked 상태로 가면서 프로세스 C에게 자신의 우선순위를 상속한다.)
    ex)
    
    Task C가 공유자원을 사용하고 있는 도중 Task B, Task A가 실행이 되어서 공유자원에 Lock을 걸지 못하게 되면 가장 우선순위가 높은 Task의 Priority를 Task C가 상속을 받는다. 그러면 Task C가 가장 우선순위가 높아서 Task C 처리가 먼저 실행을 완료하고 공유자원을 반납하면 우선순위에 의해 Task가 선점되어서 Task A, Task B가 실행이 완료된다.
  • Priority Ceiling Protocol(PCP)
    resource를 잡을 때 임시적으로 priority를 확 올린다. 다른 프로세스 진행 안한다.
    ex)
    
    Task C가 공유자원을 사용하고 있을 때 우선순위가 높은 Task 가 실행이 되면 처리를 완료하고 공유 자원을 반납할 때까지 Task의 Priority를 늘려서 Task C 처리를 완료한다. 그 뒤 우선순위에 의해서 Task B, Task A가 실행이 완료된다.
    
    

Multilevel Queue Scheduling

---

• 서로 다른 queue에 넣고 각각에 다른 scheduling 방식을 적용하는 것이다.
• Multilevel feedback queue(MLFQ)
  
  

Proportional Share Scheduling

---

• Advanced Scheduling Topics
• 전체 CPU resource time중에 A가 전체 60프로, B가 30프로 나머지가 10프로로 세개의 프로세스가 비율을 가지고 resource를 사용하게 하는 것이다.
• 전체 시스템에 T개 정도의 share가 있는데 N개를 가져가서 쓰는 것이다.
  
  

Real-time CPU scheduling

---

• Advanced Scheduling Topics
• 돌아가는 시스템이 있을 때 각각의 task들이 실행이 완료되어야 하는 deadline이 있는 시스템
  
• Soft real-time systems : 일반 프로세스에 비해 높은 priority를 갖도록 해야한다.
• Hard real-time systems : 정해진 시간 안에 반드시 끝내도록 스케줄링 해야한다.
• 어떻게 scheduling을 해야 모든 프로세스들이 시스템에서 잘 돌 수 있을까, 수많은 scheduling 방법이 존재한다.

1. RMS
   • Rate Monotonic Scheduling
   • 각 프로세스에 rate를 가지고 가장 높은 애부터 스케줄링하고 preemption을 하겠다.
   • Priority = the inverse of its period
   • p=d
   • Example
     
     Example2는 deadline을 맞추지 못했다.
     U = 50+43 = 93% -> 프로세스 2개일때 83% -> RMS 스케줄링이 안 될 수 있다.
2. EDF
   • Earliest Deadline First
   • 프로세스들이 시스템에 도착했을 때 각각의 deadline을 보고 deadline이 가까운거 빨리 돌아올 것부터 미리하겠다.
   • Example