welcome to part two of the lecture on synchronization this part we'll be talking about a race condition the learning objectives for this piece are to First understanding what Behavior by processes and threads can lead to a race condition second identify when race conditions can arise during execution and whether they arise from an atomicity problem or an ordering problem so let's first talk about a race condition a race condition occurs when the output of a sequence of code is dependent on the The Ordering of different threads or the timing of uncontrolled events for example if you
have code that two threads can execute at the same time and the order in which they run makes a difference in the output that's called a race condition for example consider the case of the bank account we looked at in the last lecture in that case we showed that if both threads ran at the same time the output of the the output of the code could leave the balance at $80 which is incorrect however a different possible inter leaving can lead a different result in this case the first thread runs up to the point where
it updates the balance field of the bank account to $90 in this case when the second thread runs it sees the first thread is already reduced the balance to $90 and then takes out an additional $20 this leaves the bank account balance at the correct value of $70 what we see here is that we have a race condition because the ordering in which the two threads inter leave affects the outcome $80 in one case and $70 in the other so this result is indeterminate and it makes it very difficult to debug your code because depending
on when threads run and what they do you get different results in contrast the terministic cont computation would produce the same result every time it's run and is much easier to understand this is what we want to achieve through our concurrency through our synchronization mechanisms so what can we do about race conditions we need some way for programmers to control access to shared resources when there's concurrency this allows them to reason about the order in which different pieces of the program will run and effectively reintroduces determinism by making sure that the right thing always happens
what this means is that some kind of synchronization mechanism is necessary for every shared data structure where at least some thread is modifying that data structure so the basic some basic definitions a critical section is a piece of code that accesses a shared resource um we want critical sections to run with what we call Mutual exclusion to synchronize its execution with other threads Mutual exclusion means that only one thread can run in the critical section at a time Mutual meaning um related to others and exclusion meaning one thread will exclude others so suppose we have
this code with the bank account balance what code do we want to have here that should be within the critical section here we want to have the code that reads the old balance updates the balance and writes it back to be part of the critical section we really want to make sure that the balance of the account doesn't change between the time when we read the balance and we write the New Balance back because if the balance did change we would write back the wrong balance therefore the code that does sort of a read update
modify and then write the value back we need that to go in the critical section the code that Returns the New Balance however does not need to be in the critical section because it's returning a thread local variable here um and it doesn't matter if the threads start running at this point so to implement critical sections properly there's some properties we'd like our solutions to have one is mutual exclusion this is the most important property and make sure that only one thread executes in a critical section of code at a time this makes sure that
other threads aren't modifying data while it runs second we'd like to have a guarantee of progress which means that a thread outside a critical section can't stop another thread from entering this means that once threads exit the inter once threads exit a critical section other threads can keep going so even if that thread outside the critical section starts waiting on iO or something like that other threads keep going we would also like bounded waiting which means that when a thread is waiting to enter a critical section it will eventually enter it won't starve and sit
there forever this also requires though that threads that are in the critical section eventually leave and release Mutual exclusion if a thread can stay in the critical section forever other threads will wait forever we would like to solutions that are high performance so the overhead of entering and exiting the critical section are small particularly compared to the amount of work doing in there so we don't slow programs down a lot by using critical sections finally we'd like the solution to be fair meaning that we don't want to make some threads wait much longer than other
threads because um this would lead to programs that run incorrectly so there are two major top ways to do synchronization which we mentioned in the last lecture the first is atomicity make making sure that we have mutual exclusion and the second is conditional synchronization which provides ordering making sure that one thread runs before another thread so let's look at how atomicity solves our problem here we'll look at an example from the real world suppose that person A and B are working together on a paper and they're both writing the paper at the same time what
they need here is to make sure that while they're working they don't edit the same section at the same time they need to make sure that when they edit they are the only person editing that section and if they read a section and then modify it there won't be modifications from the other person this is called atomicity because they want to make sure that they read and write the same version of the paper another way to solve this is using conditional synchronization again suppose we have two people working together on a paper the solution here
is person a is going to write a rough draft of the paper and then person B does the final edits in this case we don't have to worry about A and B writing at the same time because they're working on different versions of the paper we do however have to make sure that person a completes writing before person B begins so person B isn't overwriting what person a has done so the difference here is we care that the order of the tooth people B goes after a not whether A and B are editing the same
code so there's a number of different methods for be in critical sections we'll look at in future lectures next we'll talk about locks which are very primitive and just provide Mutual exclusion but they're useful as a building block for other kinds of synchronization mechanism we'll then talk about semaphor which are a very basic mechanism and very powerful but can be difficult to program with we'll also look at monitors which are a highlevel approach to for specifically for providing uh both atomicity and conditional synchronization this is built into Java with its synchronized methods and a final
method we won't talk about is to write all your code using messages to send messages back and forth instead of having shared data this is the end of part two on Race conditions please take the quiz on Race conditions before watching the next lecture