Searchable transcript of Mutex Explained - Computerphile — Computerphile (11:42). Search for a phrase, then click its timestamp to jump straight to that moment in the video.
Captions sourced from the original video on YouTube, published by Computerphile. The video, its captions and all related intellectual property remain the property of their respective owners; AINotes claims no ownership. Provided for research, accessibility and search — see the Transcript Notice and Copyright Policy.
00:00 What are we going to look at today? We're going to look at mutual exclusion or mutxes. >> Yeah, we talked before about all the kind of problems that you get in the world when you try and do two things at the same time or rather when two people try and do something at the same time and in our everyday life, we don't typically um have this kind of problem because you know if you go to use a like a a locked door like a bathroom door and it's already locked, you don't go in.
00:23 Someone is busy, you don't want to get involved with that. Once they're finished, they'll come out and then you can use the bathroom, right? And so in computers, how do we how do we do the same thing? How do we achieve this sort of lock where something important can be done without interruption and then when it's finished, the resource is now available for someone else to use?
00:40 I don't know how much I like that analogy, but >> we're going to get into toilet humor quiet at this point. But yeah, know if it's a member of your family might you might ask her, are you going to be long? >> Yes. Right. Right. Which Yeah. which computers luckily don't have such a problem with the primitive we want to build is something that multiple processes threads and even physical computers either locally like physical CPUs inside the same machine or on the same die or you know more generally there's this this
01:13 kind of applies in a distributed system where you want to make sure so we've talked about the the ATM problem where if you have two people trying to withdraw money from the same account like you and your your partner are both synchronized and you both try and take out £10 at the same time. Then you could imagine a situation where the systems check, have you got the money?
01:30 And they both go, "Yep." And then they both withdraw the last £10 at the same time and then all sorts of things go wrong. Right now, something has to make sure that there is something that only happens once across a whole country, which is a whole different thing. But we're going to today we're going to talk about the kind of mutexes you can do on a single chip or a single CPU.
01:47 um let's let's sort of come up with um some ex some reason. Let's let's write the bank version. So let let's do our um the code that we had before was something like um you know a a function to withdraw some amount of money and we say something like if balance is greater than or equal to the money that you want to withdraw then we're okay. We can now remove it.
02:11 So we go balance equals balance minus money and then we sort of like tell the cash machine to dispense that amount. >> So that makes you know magical things happen. Money comes out and then we're done. End if. Right. That's that's the end of else you know print sorry you haven't got enough money in your account. Easy. But of course if two of these are going at the same time they can both go if balance and then they can both go balance equals balance minus money.
02:33 So what we want to do is we want to lock this. Now we're going to assume at the moment that there is exactly one of these systems. cuz I'm not going to have distributed stuff or anything like that. So, what we want to do is say like here we want to say lock and here we want to say unlock. And then what that means that lock and unlock here protects this area in between here.
02:50 And it essentially guarantees that this is the bathroom door lock. Right at this point, either we're waiting outside for the lock because someone else is in there in and there in this instance is this important part of code that we've got or we get the lock and now we're we we we are able to do whatever we like to do and then when we're finished we absolutely have to remember to unlock else we're everyone else is now stuck forever more.
03:15 And the trick is how do we implement this? Because it seems like if if our lock is something like if not locked then lock else wait for it to lock. we're just back to the same problem again. We're going to just be sat going, "Well, hang on a second. What if both of them say, "Oh, it's not locked." And then they both think they've got the lock. So that actually this is the first time we need something physically in the hardware to do something for us.
03:37 Um that is different from just reading and writing to memory. So our our little robot from way back when gains an extra power and that power is not just to read from memory or to write to memory but he can atomically that is with without anyone getting in between he can read and swap in a new value to an area of memory. So he can go to one of the little slots and he can put a new number in and he gets what the old number was and no one else can get in between those.
04:04 It's not like someone else can also write a number in at the same time. they'll either see the number that he has written in um after he's written his in or they beat him and they've already swapped in their number. It's indivisible atomic. And so now what we can do is we can have a lock variable. We call this a mutual exclusion. So I'm going to a mutx for short.
04:25 So we're going to have some area of memory over here. I'm going to draw it as a little box. Mutx over here and in here is going to be the value zero to start with. And then the lock function looks like this. So we get the old value >> is equal to this exchange which I'm going to write as X C HG mutx comma one. So this means write the number one into there and read back what the old value was.
04:54 Okay. So two things could happen. I could be alone and I've just switched the value one in and I get the value zero out which means that no one else had the lock. Brilliant. Okay, if that's the case, we are locked and there's no more to do. However, if I switch in a one and I get a one back, that means that there was a one already in there. Then I know that someone else already held the lock.
05:21 And so I haven't changed the state of the lock cuz I switched a one with a one. But it's not my lock and I have to keep trying. So what I'm going to do here is I'm going to say do is to loop loop forever. I don't if you can read my handwriting there. So we're gonna have some loop over here. Old is equal to exchange that one. And then if old is equal to zero then we can we can return.
05:44 We're done. We're locked. Otherwise we just keep on looping. And so it's just going to sit here forever trying to switch in a one for a zero. Unlocking is easy because we already know well that that the the if unless the programmer has made a mistake you can only unlock something that you definitely locked yourself. So unlock sorry to write this all over my paper here is literally just to say mutx is equal to zero.
06:08 And now we've got a primitive that lets us build our withdraw and in fact any sort of piece of code that requires an atomic update that is bigger than just a single number that we can switch in and out. So the hardware gives us this one primitive. Modern hardware gives us several other primitives which we'll I'm sure we'll talk about another time, but this one allows us to build almost everything else on top of it.
06:28 We can switch in this one. Now, couple of quick things about this. You may notice that if someone else has got the lock, CPUs are really, really, really, really fast. You know, 4 billion instructions a second or whatever. This is like the equivalent of rattling the door in the bathroom continuously going, "How have you are you done yet? Are you done yet?
06:46 Are you done yet?" Obviously, that's that's very irritating for the person on the other side of the door. And it's not free in computer terms as well. This is an expensive operation. You're pegging the CPU 100%. It's doing 100% work. It's not waiting for anything. It's just literally spinning and spinning and spinning and spinning. And for very latency sensitive applications such as my day job, we might choose to do that.
07:05 That might be fine. But in a modern system, the operating system will provide this for you. Internally, it'll do this. But what it'll do is after a couple of times round if it can't get the lock using this this this uh approach it'll put your process to sleep and find someone else who h who can make progress. So this is one of those things where you're like you know hey if I can't get the lock right now might as well be doing something else and then the unlock becomes a bit more complicated as well because when you
07:31 unlock you also tell the operating system oh by the way I'm done now. It's like sort of announcing to the world I'm done. anyone who was waiting for this maybe they should be woken back up now and then they maybe switch back to so the operating system provides a lot more on top of this. Um and another sort of point of note is that we've talked about reordering instructions before and what things happen before other things.
07:51 This is a very very very tricky thing to get right because with our speculative execution and our predictive whatnot. Um, it's entirely possible both either the compiler or the CPU may decide to switch around some instructions that it thinks can otherwise run independently of each other which means that for all we know maybe the instruction that run that updates the balance has been run beforehand because it was correctly predicted hit things like that right so we have to be really really really careful and so usually
08:19 the exchange instruction or similar has a kind of magical barrier that tells the CPU hey don't bring any loads earlier than this because maybe they'll read the wrong value or we will read them before we've got the lock and also the compiler needs to know that it can't reorganize code around uh for for that those purposes and then similarly when we're unlocking as well you know if you unlocked and it decided hey wait a second I could write zero to mutx right now because no one cares about this again there are special um
08:46 things that we have to tell both in terms of the the program and um the the the CPU uh x86 CPUs are very very lenient about this kind of stuff they typically do things in the right order but some of the the more modern ARM processor is a very um very high performance able to reorder things and so you have to be very very careful with this. This is a simple case where we've got one lock.
09:07 But in complicated code, you might have multiple locks. You know, for example, if you're try that, let's imagine this lock is per account. That would make sense. Rather than having a lock for the entire bank, right? We've got a lock per account. And then if I'm transferring money from one account to the other, I actually need to lock both accounts. So if I lock the uh let's say account A and then I lock account B now I can modify both A and B and I can change the balance.
09:35 I can you know switch the balance of one with the balance of the other do whatever I like and then I unlock them. Fine. Brilliant. What if at the same time someone is transferring money back the other way. So now I lock account A. They lock account B. I go to lock account B and I block because I can and I'm waiting for account B to be finished. and the other person other person the other program tries to lock account A and now we are stuck.
09:58 We will never ever ever finish. This is the sort of dining philosophers thing the the people the robots with chopsticks uh example from before. We're now in a deadlock. Neither program can make any progress. And that's a real risk when you're dealing with mutxes is that if you don't if you don't have a discipline about how you how you take them and release them, then you might be in trouble.
10:17 Now, one thing that like databases might do is they might have a timeout and then they roll back the whole thing and try again. That's one thing. The the usual solution for that particular thing is that you use the account number as a sort key and you say whenever I lock a sequence of accounts, I always always always always lock them in numerical order.
10:33 So that means that even when you're transferring from B to A, it'll lock A first and then B and then like one of us will win. You know, you might have to wait a while, but one of us will win. >> Are there better ways than mutexes? >> Right? So a mutx is a powerful construct but it it there are other ways and means of improving um upon this for special cases.
10:52 You know this is the workhorse really of most operations and this can be built out of this simple exchange but yeah there are other primitives that the hardware can provide that lets us do things a little bit more scalably. The problem with this is that the more people we have trying to lock the same thing at the same time you know again only one of them can make progress at a time.
11:10 >> So we need communal bathrooms then. >> That's right. Communal bathrooms as a solution and it's going to be lots of clever instructions that I don't know how to write off off the top of my head that actually calculate the square root of whatever is in t2 as it happens. And we'll come back to that in a sec. And so this instruction at line 103 wouldn't be a square root. It would be something like