[OS] Scheduling

Introduction to Scheduling

• old days of batch systems and timesharing systems
  - CPU time was a scarce resource on the old machies.
  • A great deal of work has gone into devising clever and efficient scheduling algorithms.
• Advent of PC
• High-end networked workstations and severs
  - Process scheduling matters very much
• Process switching is expensive
  A program was running scheduler choose the other process to run, int is called context switch
  프로세스가 많으면 스케줄링의 중요성이 증대된다.

Process Behavior

• Bursts of CPU usage alternate with periods of I/O wait
  - a CPU bound(or compute-bound) process => CPU burst가 길다.
  • an I/O bound process => CPU burst가 짧다.

when to schedule (참고용)

• when a process created
• when a process exits
• when a process blocks
• when an I/O interrupt occurs
• Scheduling algorithms can be divided into two categories with respect to how they deal with clock interrupts
  - Nonpreemptive
  - picks a process to run and lets it run until it blocks or until it voluntarily releases the CPU => 자발적으로 CPU를 내놓을 때 수행
  • Preemtive
    • picks process and lets it run for a maximum of some fixed time. If it is still running at the end of the time interval, it is suspended and the scheduler picks another process to run => 주어진 시간 만큼만 process 허용

Categories of scheduling algorithms

• batch
• Interactive
• Real time

Schduling algorithm goals

• All systems
  Fairness - giving each process a fair share of the CPU policy enforcement - seeing that stated polict is carried out balance - keeping all parts of the system busy

• Batch systems
  Throughput - maximize jobs per hour
  Turnaround time - minimize time between submission and termination CPU utilization - jeep the CPU busy all the time

• Interactive systems
  Response time - respond to requests quickly
  Proportionality - meet user's expectations

• Real-time systems
  Meeting deadlines - avoid losing data
  Predictability - avoid quality degradation in multimedia systems

• preemtive(선점형)과 non-preemtive(비선점형) 중요함 *
  non-preemtive - 특정 프로세스가 CPU를 독점하는 것이 가능 (프로세스가 스스로 CPU 점유를 포기해야만 다른 프로세스가 실행)
  preemtive - 특정 프로세스가 CPU를 독점하는 것이 불가능(운영체제가 강제로 프로세스의 CPU 점유를 제어)

Scheduling in Batch Systems

First-Come First-Serve

• processes are assigned the CPU in the order they request it.
• single queue of ready processes
• Nonpreemptive
• When the runnong process blocks, the first process on the queue is run next. when a blocked process becomes ready, it is put on the end of the queue.

Shortest Job First (SJF 중요)

• Nonpreemptive (어떤것이 선점형이고 어떤것이 비선점형인지 구분하기)
• Run times are known in advance
• Optimal average turnaround time (when all the jobs are available simultaneously)
  각각의 turnaround time 계산할 줄 알아야한다. 동시에 system에 도착해야한다.

• Average turnaround time
  In (a), (8+12+16+20)/4 = 14 mins.
  In (b), (4+8+12+20)/4 = 11 mins. 더 optimal하게 나온다.

동시에 도착하지 않으면 SJF는 Optimal 보장하지 않는다.

SJF 알고리즘을 토대로 위 문제의 평균 waiting time 계산
-> P1은 바로 수행됐기 때문에 기다린시간 0초
-> P2는 2초에 들어와서 8초에 수행 6초
-> P3는 4초에 들어와서 7초에 수행 3초
-> P4는 5초에 들어와서 12초에 수행 7초

Shortest Remaining Time Next(SRTN)

• preemptive version of SJF
• Chooses the process whose remaining run time is the shortest 남아있는 rt가 짧은 것 선택한다.
• when a new job arrives, its total time is compared to the current process's remaining time. If the new job needs less time to finish than the current process, the current process is suspended and the new job is started. 현재 수행되고 있는 프로세스의 남은 시간과 새로운 job의 남은 시간을 비교하여 더 짧은 job을 수행한다.

Scheduling in Interactive systems

Round Robin Scheduling

• (a) list of runnable processes
• (b) list of runnable processes after B uses up its quantum
  quantum - (time interval 동안)
• length of the quantum
  - too short: causes too many process switches(context switches) and lowers the CPU efficiency
  • too long: causes poor responese to short interactive requests.

Priority Scheduling(우선 순위 스케줄링)

• Each process is assigned a prioritty, and the runnable process with the highest priority is allowed to run
• To prevent high priority processes from running indefinitely,
  - decreases the priority of the currently running process at each clock tick.
  If the priority drops below that of the next highest process, a process switch occurs
  • Assign each process a maximum time quantum that it is allowed to run.
• priority assignment(중요)
  - static :based on the user, price, etc (nice)
  • dynamic :giving good service to I/O bound process: sets the priority to 1/f