-dispatch orders immediately
scheduling is simple(FIFO)
-dispatch simple orders first
maximize # of orders processed over time
-dispatch complex orders first
keep workbenches busy
CPU scheduler
– decide how and when processes (and their threads) access shared CPUs
– schedules tasks running user-level processes/threads as well as kernel-level threads
– runs when
– cpu becomes idle
– new task becomes ready
context switch, enter user mode, set PC and go <- thread is dispatched
"run-to-completion" scheduling
initial assumptions
- group of tasks/ jobs
- known execution times
- no preemption
- single CPU
Metrics
throughput
avg. job completion time
avg. job wait time
First-com First-Serve (FCFS)
-schedules tasks in order of arrived
rungueue == gueue(FIFO)
T1 = 1s, T2 = 10s, T3 = 1s
Throughput = 3/12s = 0.25 tasks/s
Avg. Completion time
=(1+11+12)/3 = 8sec
Avg. wait time
=(0+1+11)/3 = 4sec
Shortest Job First(SJF)
-schedules tasks in order of their execution time
T1(ls) -> T3(ls) ->T2(10s)
runqueue = ordered queue(FIFO)
Throughput Formula:
jobs_completed / time_to_complete_all_job
Avg. Completion Time Formula:
sum_of_times_to_complete_each_job / jobs_completed
Avg. Wait Time Formula:
(t1_wait_time + t2_wait_time + t3_wait_time) / jobs_completed
