CSE 120 Lecture Notes - Lecture 5: Context Switch, Busy Waiting, Mutual Exclusion

44 views3 pages
Back to EDF:
-expensive: requires ORDERING by deadlines
-at EVERY decision step, we have HIGH complexity computation (sorting)
-theoretically, EDF meets ALL deadlines
-requires a LOT of overhead
RMS: Rate Monotonic Scheduling
-IF periodic processes, prioritize based on rates
-when a burst is done (time process uses CPU), wait til next period
-guaranteed to work (ie all deadlines met) IF U1 + … + Un <= n(21/n - 1)
-if you don’t meet the constraint, it may or may not work! (does NOT mean it will NOT
-priority is given to the process that is awoken from its sleep after its deadline
RMS Optimal BUT Limited
-static priority scheduling based on rates
-optimal for static priority algs
-limited in what it guarantees
-if n = 1 100% guaranteed
-if n = infinity → RMS is guaranteed to work if processes use <= ln(20 = 69%
-limited to periodic processes
-low overhead
-events happen at the same time
-in process:
-events in process that occur “at the same time”
-prevent race conditions
Credit/Debit Problem
-assume $1000 in your back account
-you withdraw $100 at the same exact time your friend also withdraws $100
Avoid Race Conditions
-identify related “critical sections”
-code executed by multiple processes
-must run atomically (indivisible - cannot be divided) with respect to each other
-enforce mutual exclusion
How to Achieve Mutual Exclusion?
-surround critical section with entry/exit code
-entry code is a barrier:
Unlock document

This preview shows page 1 of the document.
Unlock all 3 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
$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.