CPU Schduling:

CPU Schduling

          > 5 State Transition

                    > Ready-Queue에 있는 프로세스 선택 -> CPU에 올린다

                    > 모든 프로세스가 메모리에 올라가 있다고 가정, 실행 중인 프로세스는 CPU에 올라가있다 가정

                    > Multiprogramming 에서 필수적(CPU utilization)

          > Non-Preemptive Scheduling 

                    > 프로세스가 "Terminated" 일때 다음 프로세스 실행

                    > 프로세스가 "Running" 에서 "Blocked" 되었을 때 실행

                    > 프로세스 우선순위가 더 높은 프로세스가 있다 하더라도 현제 프로세스가 종료가 되어야 함

          > CPU Scheduling Goals

                    > CPU 가 결정하는 사항

                              > 프로세스가 얼마나 실행될 지

                              > 어떤 순서로 프로세스가 실행될 지

                    > User-Oriented Policy

                              > Average Response Time(요청시부터 프로세스 시작까지) 을 최소화 하고 number of interactive users                                        를 최대로

                              > Turnaround Time 최소화 (프로세스 실행부터 완료까지)

                              > Variance of Average Response Time 최소화

                                        > 예측을 해야 한다

                    > System-oriented Policy

                              > Throughput(처리율) 최대화

                              > Processor Utilization(CPU가 얼마나 사용되는가) 최대화

                    > Other System-Oriented Policy

                              > Fairness: 모든 프로세스는 동일하게 취급 (starvation이 일어나서는 안된다)

                              > Balance Resources: 시스템의 모든 자원이 쉬지 않도록 (최대한)     

          > Preemptive vs. Non-Preemptive

                    > Non-Preemptive Executes when

                              > Process terminated

                              > Process switches from running to blocked

                    > Preemptive Executes when

                              > Process 가 생성 되었을 때

                              > Blocked 에서 ready 되었을 때

                              > Timer interrupt 발생

                    > Preemptive 방식은...

                              > 오버해드가 더 크지만 긴 프로세스가 CPU 독점 하는 것을 방지

                              > Syscall 을 처리할 때 OS kernel을 선점 x                       

                    

 

Process Execution Behavior

          > 다음 사항들을 가정한다

                    > One process per user

                    > One thread per process

                    > 각 프로세스는 독립적이며 자원을 할당 받으려 함(compete)

          > 프로세스는 CPU 내부에서 실행(I/O burst cycle)

                    > 입출력을 해야 계산이 가능하기 때문에 CPU burst - I/O burst를 반복한다

          > 프로세스의 두 종류

                    > CPU-bound: I/O를 적게 수행, 많은 계산 ( long CPU burst)

                    > I/O-bound: I/O를 많이 수행, 적은 계산 (short CPU burst)

 

First-Come-First-Served(FCFS)

          > Run until done

          > Ready-Queue에 있는 프로세스중 non-preemptively 하게 먼저 온 순서로 선택

         

FCFS Example

          > FCFS Eval

                    > Non-Preemptive 하다

                    > Response time 이 느리다

                              > 긴 프로세스 이후 짧은 프로세스들이 온다면 짧은 프로세스들은 대기 시간이 길다

                              > 하나의 CPU-bound 프로세스 이후에 많은 I/O-bound 프로세스들이 온다면 "convoy effect"

                                        > Low CPU, I/O utilization

                    > Throughput: 최대화 x

                    > Fairness: 짧은 프로세스, I/O-bound 프로세스에 페널티 부여

                    > Starvation: 불가능

                    > Overhead: 최소화

 

Round-Robin

          > 정해진 time slice 가 있다

          > Ready Queue에 가장 최상위에 있는 프로세스 선택

          > 선택한 프로세스를 최대 하나의 time slice 동안 돌리고 완료되지 않을 시, ready queue 로 보낸다.

          > 선택한 프로세스가 time slice가 끝나기 전, terminate 되거나 blocked 된다면, ready queue에 head에 있는 다른 프로세스 선택

          > 하드웨어 타이머, FIFO ready queue

RR Example

 

          > RR Eval

                    > Preemptive 하다

                    > Response time: Good for short process

                    > Throughput: Time slice에 의해 결정됨

                              > Too small: Too many context switch

                              > Too large: Approximates FCFS

                    > Fairness: Penalizes I/O-bound processes

                    > Starvation: Not possible

                    > Overhead: Low (다음 프로세스 선택에 고민 x)

 

Shortest-Job-First(SJF)

          > 가장 짧은 CPU-burst를 가지고 있는 프로세스를 선택, non-preemptively 하게 프로세스 실행

          > Tie 일 경우, FCFS를 사용

          > 다음 CPU-burst를 결정하는데 어려움

SJF Example

          > SJF Evaluation

                    > Non-Preemptive

                    > Response Time: Good for short processes

                              > Long Processes may have to wait until large number of short processes finish

                              > Probably optimal: Avg waiting time 최소화

                    > Throughput: high

                    > Fairness: Penelizes long processes

                    > Starvation: Possible for long processes

                    > Overhead: can be high

 

 

Shortest Remaining Time (SRT)

          > Preemptive version of SJF

          > 다음 smallest CPU burst 를 가지고 있는 프로세스 선택

                    > Until termination or blocking

                    > until a process enters that the ready queue

          > At that point, choose another process to run if one has a smaller expectd CPU burst than what is left of the current process' CPU burst

 

SJF Example

          > SRT Eval

                    > Preemptive

                    > Response Time: Good, Probably optimal

                    > Throughput: High

                    > Fairness: Penalizes long processes

                    > Starvation: Possible for long processes

                    > Overhead: can be high

 

Priority Scheduling

          > Externally defined: based on importance, money, politics

          > Internally defined: based on mem, requirements, file requirements, CPU req vs. I/O req

          > SJF is priority scheduling

          > Choose the process that has the highest priority and run that processes either

                    > preemptively or non-preemptively

          Eval

                    > Starvation: possible for low priority processes

                    > Avoided by Aging: increase priority as they spend time in system