welcome to unit 3 of our lectures in it synchronization this one is about locks the learning objective for this lecture is first to learn how to apply locks to illuminate race conditions in a multi-threaded application and second to understand some of the difficulties in implementing locks we'll talk more about these during the lecture itself so first of all that's learn what a lock is a lock is an operating system structure that has two States it can be held this represents the case when a thread is in a critical section and no one else should enter
or not held which means a critical section is not currently in use and a thread can enter the critical section to represent these two states there are two operations to move the lock between the states the first is the acquire operation when a thread calls acquire it marks the lock is held if no one is currently holding it and allows the thread to proceed by returning immediately if a thread has already called acquire then the acquire operation does not return but instead waits until that first thread that called acquire subsequently called release release therefore marks
the lock is not held and let's one other thread that is currently calling acquire proceed this means that if many many threads call acquire own at the same time only one thread can get through and hold the lock all the other threads will keep waiting until the first thread calls release at that point one of the waiting threads will return from acquire and keep going when that thread the second threat calls release it will allow a third thread to make progress and so forth until all the threads have returned from acquire and can enter the
critical section code so how do we use locks well first of all locks are usually declared like a variable most programming languages or operating systems have a lock have a lock datatype that you can use to declare lock variables and as an example here lock l furthermore program can have multiple locks so you might have two locks named ln m and a program can then when it acquires a lock will explicitly say which lock it wants lock acquire L or acquire m to use a lock within a critical section is simple protocol to acquire a
lock at the start of the critical section this makes sure that only one thread can enter the critical section at a time put a call to release at the end of a critical section this allows other threads to enter the critical section because this first thread is done this achieves our requirements of mutual exclusion and progress for implementing critical sections as we've described in the previous lecture one thing to note that's important though is that acquiring a lock only blocks other threads trying to acquire the same lock so if one thread acquires lock L it
doesn't stop another thread from acquiring lock m and vice-versa it will stop threads that want to require lock L though this means that we can have different threads in different critical sections at the same time the question then comes up is well is it safe to have different locks protecting different critical sections what if we need to stop all threads well the thing to remember about using locks is that you have to use the same lock for two critical sections that access the same data this means you might have different functions that access the same
data such as withdraw a function and a deposit function for a bank account they use the same lock this is important because we want to make sure that while we're doing the withdraw nobody does a deposit and modifies the bank balance so this means that we need to use the same lock within the withdraw in the deposit function however if you have withdrawn a deposit function and then another function to print the hours the bank is open we don't need to use the same lock we use for withdrawn deposit on the function that prints the
bank hours because that's accessing different data it's not accessing the bank account balance so let's see how we'd use this in a code recall our example from before of the bank transaction and the code to do the withdraw we said there was a critical section where we read the old account balance modified it and wrote back a new account balance to protect this critical section with the lock we'd put a call to acquire lock before entering this critical section and a call to release a lock when we're done in the critical section we don't need
to hold the lock once we're done modifying the data because after that we're just accessing a local variable in this case the balance variable so let's look at how this works suppose we start with an account balance of $100 and again we'll have the pink and green thread the pink thread enters calls acquiring the lock and begins updating the balance when a green thread enters and then tries to call acquire it will be stalled it'll be stuck here inside the acquire function until the pink thread calls release the pink food can then start executing again
a bit the balance and call release leaving the balance of $90 at this point and only at this point is the green thread allowed to run again when it runs it sees that the balance is $90 as it should be it updates the balance to $70 and then releases the lock and returns at the end the bank account balance is $70 as it should be now let's look at what happens if the green thread runs first in this case it will call acquire on the lock that'll update the balance to be $80 when the pink
thread starts running in cause acquire it will again be blocked and won't be allowed to run until the green thread calls release only after the green thread calls release and updates the balance to be $80 can the pink thread start running it will see the balances $80 subtract $10 updated to $70 release the lock in return and this way no matter which thread runs first we have the same balance which is $70 this means that we don't have a race condition anymore because we don't have code that depends on which thread runs first without the
locks we had a race condition where we could get different values depending on when the threads ramp so how do you implement locks well a simple way to do it would be to have a boolean variable lock be just a boolean variable when we're trying to acquire a lock we can just sit in a while loop reading the lock variable and waiting until it's set to false so lock arrow held is not true in the wild loop drops out we could then send lock held to be true this would very simply just sit there in
the wild loop while anybody is in the critical section and after another thread calls release and sets the hell to false this while loop will drop out and we can update the lock so this seems like a very reasonable way to implement locks however it doesn't work let's see why suppose we start with lock held is false we run the pink a pink thread and a green thread come at exactly the same time they will both execute the code for a while lock held they will both see that it's false and so both threads will
set lock held to be true in return from the lock function in this case both threads think that they have the lock but the rule for lock is only run thread could acquire it so this means that this is not a safe implementation of locks this is actually a very very difficult problem to solve and most computer systems at this point solve it with hardware support almost all processors now have a special instruction called test and set here is shown the code the C code for what test and set does it takes a boolean flag
it first saves the old value of the flag and it then sets the flag to true and returns the old value what's important about this is reading the old value and updating it to true are done atomically meaning that you you're guaranteed to return the old value and no one can modify the value between reading it and updating the value to true this atom this atomic property of test and set is what makes it easy to build a lock out of it let's look at how to build a lock with the test and set variable
it looks almost the same we still have a lock structure at the boolean variable the code to release the lock still just sets a lock variable to be false what's different is that when we acquire the lock we don't just have a while loop instead of just instead of a while loop looking at lock held we call while test and set unlock held what this will do is remember test and set will read the old lock value and then set the lock to one so let's suppose the lock the variable was initially false when a
thread comes in it will call test and set it'll set the variable to be true test and set will return the old value which is false the while loop will break out and that thread will acquire the lock when a threat second thread comes in now and tries to acquire the lock while it's currently held it will call test and set it will again set the lock to be one to be true but it will return the old value in this case the old value was also true because the lock was held this will cause
the while loop to keep spinning when the first thread releases the lock this will set the lock to be false so when the second thread called test and set the next time it will again set the lock to be true but this time test and set will return false as the old value and this thread will break out of the loop and return note that if multiple threads call acquire at the same time the hardware guarantees that only one thread will see the value of false return from test and set this is what the item
is city property returns we'll talk more about using spin locks in class this is the end of part 3 of unit on lock please take the quiz unlocking before going to class