-multiple processes, but only 1 CPU
-how much CPU time does each process get?
There is NO Single Best Policy!
-depends on the goals of the system
-might have multiple (conflicting) goals!
Arrival Time - time that process is created
Service Time - CPU time needed to complete!
Turnaround time: from arrival to departure
-want to minimize
TT = time waiting + service time
TTavg = sum TTs / #processes
Shortest First Is Provably Optimal
Given n processes with service times S1, …, Sn
Average TT computed as follows:
[S1 + (S1 + S2) + … + (S1 + … + Sn)] / n
How many times does S1 appear? N
[(n x S1) + ((n-1) x S2) + ((n-2) x S3) + … + (1 x Sn)] / n
S1 has the highest weight!
That means to achieve minimal TT, we want to choose the process with the SHORTEST service
FCFS: (First Come First Served)
-allocate CPU to processes in order of arrival
+non-preemptive (CPU not taken away from a process)
+no starvation - whenever a process can get the resources it needs
-poor for short processes
Quantum = “Time-slice”
RR: Round Robin
-every process gets a turn
-cycle through processes in the queue (recent processes are entered in the BACK)
-generally does better than FCFS (why?)
+process waits at most (n-1) x quantum
-preemptive - need a mechanism that “takes away” the CPU