CPU Scheduling

CPU Scheduling

 여러 종류의 job(=process)이 섞여 있기 때문에, CPU 스케줄링 필요. Interactive job에게 적절한 response 제공 요망.(I/O가 자주 끼어듬.) CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용.

  CPU bound job이 한번 점유하면 다른 job이 사용 x

  CPU를 공평하게 주는 것이 아니라 효율성이 중요하다.

  I/O bound job 오래 기다리지 않게 하는 것이 중요하다.

- I/O-bound process

  CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job

  many short CPU bursts

  ex)  사용자와 친한 마우스 클릭을 예로 들 수 있다.(interactive job). 빈도가 짧아 왔다갔다 하는거지 많다는 것은 아님.

- CPU-bound process

  계산 위주의 job

  few very long CPU bursts

  CPU Scheduler

 - Multiprogramming environment

 - CPU Scheduler selects processes in memory that are ready to execute, and allocates the CPU to one of them.

 - CPU scheduling decisions may take place when a process

   1. Running -> Blocked (ex : I/O 요청하는 시스템 콜)

   2. Running -> Ready (ex : 할당시간만료로 timer interrupt)

   3. Blocked -> Ready (ex : I/O 완료 후 인터럽트)

   4. Terminate

   1, 4에서의 스케줄링은 nonpreemptive(강제로 뺏기지 않고 자진 반납), 나머지 다른 스케줄링은 preemptive(강제로 빼앗음)

  Scheduling Criteria Performance Index

 - CPU utilization(사용률) : keep the CPU as busy as possible

 - Throughput(처리량) : Throughput of processes that complete their execution per time unit.( 일정기간 일 얼마나 했는지.)

 - Turnaround time : amount of time to execute a particular process.(Ready+Run,  CPU쓰기 시작, 끝나고 나갈때까지의 시간)

 - Waiting time : amount of time a process has been waiting in the ready queue.(Ready. 대기시간, 기다린 시간)

 - Response time : amount of time it takes from when a request was submitted until the first response is produced, not output(for time-sharing environment). (응답시간. CPU 사용하기 위해 처음 값을 받은 시간. instruction 수행시간 + ready 시간)

  Dispatcher

 - Dispatcher module gives control of the CPU to the process selected by the short-term scheduler; this involves: switching context, switching to user mode, Jumping to the proper location in the user program.

 

 Scheduling Algorithms

 - FCFS (First-Come First-Service)

   비선점방식.(뺏기지 않기 때문에).

   Convoy effect : short process behind long process. 처음에 긴 프로세스가 오면 나중 프로세스가 기다려야한다.

 - SJF (Shortest-Job-First)

   각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용. CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄. 

    1. No preemptive : 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점(preemption) 당하지 않음.

    2. Preemptive : 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김. 이 방법을 SRTF 라고도 부른다.

    SJF is optimal : 주어진 프로세스들에 대해 minimum average waiting time을 보장한다.(preemptive버전)

 - SRTF(Shortest-Remaining-Time-First)

   만약 p1 burst time이 1000이고, p2가 1초씩이면 무조건 p2가 먼저 실행이기 때문에 p1이 실행을 못할 수 도 있다.

   단점 1. CPU burst가 너무 크면 사용 못함.(starvation)  2. CPU 사용시간을 알 수 없다.

 - Priority Scheduling

   SJF의 경우 일종의 prioriyy scheduling 이다. CPU 사용시간이 우선순위 값. 우선순위가 낮으면 실행하지 못하는 starvation 문제를 Aging으로 해결가능. (너무 오래기다리면 조금씩 우선순위가 높아짐. -> 언젠가 실행)

 - Round Robin

   각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가진다. (일반적으로 10-100 milliseconds). 할당 시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다. n 개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우, 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다. -> 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.

   응답시간이 빠르고, 예측할 필요가 없다. CPU를 길게쓰는 프로세스는 대기시간이 길어지고, 짧게쓰는 프로세스는 대기시간이 짧아진다. -> 대기시간이 CPU burst time에 비례한다.

   q large -> FCFS

   q small -> context switch가 자주 발생해서 오버헤드가 매우 높다.

   q must be large with respect to context switch.

 - Multilevel Queue

   Ready queue를 여러 개로 분할.

   각 큐는 독립적인 스케줄링 알고리즘을 가짐.

   - foreground(interactive) : RR -> I/O 많으니 FCFS로 하면 끝나기 힘들다. 처리량은 SJF 또는 FCFS가 더 빠를수도 있으나 응답시간이 빠르기 때문에 RR. timer로 끊고 I/O가는 시간 넣어주면 된다. SJF의 경우 실제적으로 CPU가 얼마나 일하는지 모른다. 현실적으로 불가하기 때문에, FCFS 쓴다.

   - background(batch - no human interaction) : FCFS -> 이 경우 계속 CPU만 사용하기 때문에 굳이 timer로 끊을 필요가 없다.

    큐에 대한 스케줄링이 필요.

    - Fixed priority scheduling : 우선순위 먼저 처리. serve all from foreground then from background. Possibility of starvation.

    - Time Slice : 각 큐에 CPU time을 적절한 비율로 할당. eg) 80% to foreground in RR, 20% to background in FCFS.

 - Multilevel Feedback Queue

   프로세스가 다른 큐로 이동이 가능하다 : Aging을 이와 같은 방식으로 구현할 수 있다. 

   Lower level queue executes only when higher level queues are empty at all time. (preemptive)

 - Multiple-Processor Scheduling

   CPU가 여러 개인 경우 스케줄리은 더욱 복잡해진다.

   - Homogeneous processor : 하나의 ready 큐에서 cpu 두개인 경우.  Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다. 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해진다.

   - Load sharing : 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요. 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법.

   - Symmetric Multiprocessing (SMP) : 각 프로세서가 각자 알아서 스케줄링 결정.

   - Asymmetric multiprocessing : 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름.

  - Thread Scheduling

    Local Scheduling : User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄 할지 결정. -> 이 경우, A 프로세스가 1,2,3 thread를 가지고 있다고 가정하면 OS가 1,2,3 있는 것을 모르기 때문에 A를 넘겨준다. 그 후에 CPU에서 1번~ 실행하게 된다.

    Global Scheduling : Kernel level thread의 경우 일반 프로세서와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄 할지 결정. -> 이 경우 OS가 1,2,3 있는거 알아서 A의 1을 넘겨준다.