CPU Scheduling

1.Basic Concepts

    - 다중프로그래밍의 목적은 CPU 이용률을 최대화하기 위해 항상 실행 중인 프로세스를 가지게 하는데 있다.

    - CPU가 유휴 상태가 될 때마다, OS는 준비 완료 큐에 있는 프로세스들 중에서 하나를 실행해야한다. *반드시 FIFO 방식의 큐가 아니어되 된다.

    - CPU scheduling decisions may take place when a process.

       :Switches from running to waiting state.(입/출력 요청, 자식프로세스중 하나가 종료되기 위해 wait를 호출) ->Non preemptive.

       :Switches from running to ready state.(인터럽트 발생) ->preemptive.

       :Switches from waiting to ready(입/출력 종료) ->preemptive.

       :Terminates ->Non preemptive.

2.Dispatcher

    - CPU의 제어를 단기 스케줄러가 선택한 프로세스에게 주는 모듈, 다음을 호함.

       :switching context.

       :switching to user mode.

       :프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동하는 일.

     - dispatch latency : 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는 데까지 소요되는 사간.

3.Scheduling Criteria(스케쥴링 기준)

     - CPU 이용률(utilization): 가능한 한 CPU를 최대로 바쁘게 유지하기를 원함.(40~90%까지 범위를 갖는다.)

     - 처리량(throughput): 단위 시간당 완료된 프로세스의 개수.

     - 총처리 시간(turnaround time): 프로세스의 제출 시간과 완료 시간의 차이(메모리에 들어가기 위해 기다린시간, ready queue에서 대기한시간, CPU에서 실행한 시간, 입/출력 시간의 합)

     - 대기 시간(waiting time): ready queue에서 대기하면서 보낸 시간의 합.

     - 응답 시간(response time): 요구를 제출한 후 첫번째 응답이 나올 때까지의 시간(응답이 시작되는 데 까지 걸리는 시간이지, 그 응답을 출력하는 데 걸리는 시간이 아니다.)

4.Optimization Criteria

     - Max CPU utilization

     - Max throughput

     - Min turnaround time.

     - Min waiting time.

     - Min response time.

5.First - Come, First - Served(FCFS)

     - 도착 순서대로 nonpreemptive 하게 처리 -> ready queue에 들어있는 순서대로 처리 -> I/O때문에 CPU 를 반납할 때만.

     - Time sharing 곤란.

6.Shortest - Job-First(SJF)

     - 증명된 성능최적.

 

7.Priority Scheduling(우선순위 스케쥴링)

     - CPU는 가장 높은 우선순위를 가진 프로세스에게 할당된다.

     - Problem : Starvation - 낮은 우선순위를 가진 프로세스는 CPU를 계속 얻지 못할 수 있다.

     - Solution : Aging -  오래 기다리면 우선순위를 높여준다.

8.Round-Robin

     - 각 프로세스에게 시간할당량(quantum)을 준다. 일반적으로 10-100milliseconds이다.

     - 라운드 로빈 스케줄링을 구현하기 위해, 준비 완료 큐를 프로세스들의 FIFO 큐로 유지한다.

     - 할당량 이후에는 인터럽트가 걸려 프로세스를 Dispatch 한다.

     - quantum Large -> FCFS와 다를게 없다.

     - quantum small -> context switching time이 많아져 비효율적이다.

     - 성능 : SJF > FCFS > RR  - 성능이 떨어지더라도 앞의 두개의 단점을 해결할 수 있다.

9.Multilevel Queue

     - 프로세스는 foreground(interacive)와 background(batch)로 구분될수 있다.

     - 준비완료 큐를 다수의 별도 큐로 나눈다, 큐 사이에는 스케줄링이 반드시 있어야 한다.

     - foreground는 RR방식 background는 FCFS방식을 사용한다.

     - 우선순위 높은것 먼저 실행하면 starvation이 발생할 수 있다.->80% to foreground in RR, 20% to background in FCFS.

     - 시간안에 process를 끝내지 못하면 다시 같은 큐로 들어간다.

10.Multilevel Feedback Queue Scheduling

    

     - 프로세스가 큐들 사이로 이동한다. 어떤 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위의 큐로 이동한다. 이 방법에서는 입/출력 중심의 프로세스와 대화형 프로세스들을 높은 우선순위에 넣는다. 마찬가지로 낮은 우선순위으 큐에서 너무 오래 대기 하는 프로세스는 높은 우선순위의 큐로 이동할 수 있다.(starvation 방지)

11.Multiple-Processor Scheduling

     - 여러개의 CPU를 사용 하면 스케줄링 문제는 복잡해진다.

     - 각 프로세서가 독자적으로 스케줄링을 하면 프로세스가 여러 프로세서에게 뽑히기도 하고 큐에서 사라져 버리기도한다.

     - 비대칭 다중처리는 대칭적 다중처리보다 간단하지만 병목 현상이 될수 있다.

12.Real - Time Scheduling

     - hard real time system - 스케줄러는 프로세스가 dead line을 지킬 수 있으면 받아들인다.

     - Soft real time computing - 우선순위 스케줄링 기법을 반드시 제공해야한다. 실시간 프로세스들이 가장 높은 우선순위를 갖는다. 비 실시간 프로세스들의 우선순위가 시간에 따라 낮아진다 할지라도, 실시간 프로세스들은 낮아저서는 안된다. 디스패치 지연이 반드시 작아야 한다.