CSE 120 Lecture Notes - Lecture 4: Priority Queue

62 views4 pages
CPU Scheduling
-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!
Example:
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
time
FCFS: (First Come First Served)
-allocate CPU to processes in order of arrival
+non-preemptive (CPU not taken away from a process)
+simple
+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
+simple
+no starvation
Unlock document

This preview shows page 1 of the document.
Unlock all 4 pages and 3 million more documents.

Already have an account? Log in

Get OneClass Notes+

Unlimited access to class notes and textbook notes.

YearlyBest Value
75% OFF
$8 USD/m
Monthly
$30 USD/m
You will be charged $96 USD upfront and auto renewed at the end of each cycle. You may cancel anytime under Payment Settings. For more information, see our Terms and Privacy.
Payments are encrypted using 256-bit SSL. Powered by Stripe.