Race Conditions on a Human Scale - Computerphile Transcript, AI Summary & Key Points

00:00 Matt, welcome back to Computer File. What What are we looking at today? >> Um, well, what what would you like us to talk about today? >> We talked about CPUs a few times. So, maybe if we start talking about, I don't know, time or something like that. I don't know. And we've done time. We've done time. >> We've done time. So, how about H? >> Well, I think one of the things about Hang on.

00:20 >> No, >> if we talk about that. >> Uh, you said about the mute. >> All right. I think we got a problem. All right. Hopefully. [laughter] >> So, what's this? What's going on here then? This is like a backing off thing, right? >> This is a problem that computers have where they try and do more than one thing at the same time. Uh, typically called race conditions, but we're going to talk about a whole bunch of problems that come up when more than one thing tries to happen at the same time.

00:50 And what we were just doing then obviously was a classic example of the kind of uh awkward couple in a restaurant. uh trying to make conversation, you both want to talk, you wait and then you end up talking at the same time just by bad luck and then you know the human algorithm is oh no you go and then you wait a bit and then they don't go and then you you both go again right and eventually the vagaries of the way that you know humans work means that one somebody is going to win and you end up having a conversation

01:19 which is great right with computers though because they're programmed it's quite possible that if you programmed a computer to do the same thing that is start talking and if while you're talking you start hearing someone else talking then stop and wait a period of time that period of time is likely to be the same in both computers. So, they're both just going to wait the same.

01:38 And then they'll be stuck forever just trying to talk and then backing off and trying to talk and back off. And even if you do clever things like let's back off, like let's wait 1 second, then let's wait 2 seconds, and then let's wait 4 seconds, every if everyone's clocks are synchronized, which they could well be, you'll be waiting forever. And then you might say, well, what wait a random amount of time, but as we know, computers can be deterministic as well, which means that they might all choose the same random

02:01 number every time. So you have to kind of uh think about these things in a in a slightly more um thoughtful way. Typically though, a random number generator can pick up noise from the environment and so then typically you don't have this problem. But yeah, you need to think about this and there are a whole bunch of human cases where race conditions happen and um I'd like to kind of go through some of them with you today so that we can kind of humanize this and make give people an instinct and an intuition about the

02:28 kind of things that that maybe um you hadn't really thought of before. A bug bear of mine is one of those podbased coffee machines. So, I start my day with a little pod-based coffee thing. And, you know, you pull a random cup from the drawer uh or the cupboard, put it under the the pod-based thingamajig, and the one that I've got is uh is very uh minimalist in design.

02:49 It has one button that's both the start and the stop button. And so, you put your cup under it, you press the start button, and then you know, you're having your morning, I haven't had coffee yet, so I can't really think moment. And then it starts filling up. And then you start to panic because you the coffee machine doesn't know how big the random mug you picked is up is.

03:06 So as it starts getting nearer and nearer to the top, you think, "Oh, I better stop it." And then you press stop. And then nine times out of 10, that was exactly when the machine was stopping itself. And so all you've just done is guaranteed it will overflow by starting it up again. And that's another example of one of these kind of race conditions where um you you have uh two things that are trying to happen at once.

03:28 The machine's trying to stop and you're trying to stop, but you've only got one button that toggles. So, it's a human thing. I know, right? Obviously, the easy solution is to have a both a start button and a stop button so that even if they both happen, the you press the stop button the same time that the the the the pod machine stops. Um, we talk about things that doesn't matter if it happens again, it doesn't have another effect as being item potent, which means that like I could stop as many times as I like and if I

03:58 was already stopping, it doesn't change the state of the system. And that that's one of the things you can do to to make some of these race conditions go away in some circumstances. Another example is if you, you know, you share a flat with someone, you go into you open up the fridge and you're like, "Oh, there's no milk." So you close the fridge and you pop to Tesco's and then you come back with a bottle of milk.

04:19 But now by this time your flatmate who has also done exactly the same thing but gone to sainsburries has come back and you now got twice as much milk as you asked for which you know probably not a disaster in most places as long as there's enough room to wedge another milk bottle in the fridge. That's not such a big deal. But there's another variation variation there's another variation of a similar thing which has a bit more of a a sinister uh problem.

04:44 So like imagine um quite reasonably you're a programmer who works at the bank and you know you're doing the ATM code that is you know the machine that you you know get your money out and you write code that looks like this something like this. So this is for you know withdraw withdraw function that takes uh and takes some amount of cash. I'm just going to call it cash here.

05:07 If account balance is greater than or equal to the cash then you've got enough money to take out the amount of cash that's been asked. So we say dispense cash account balance which I won't write out longand again because it's too long and I'm silly. uh minus equals which is a shortcut equals uh I'll write it out long equals account balance minus cash and then we're done.

05:35 Otherwise, you know, you've got you print out, you know, else print sorry, no money. This seems reasonable, right? So, you can imagine this is how um you might write the code for a bank. And I'm sure there's some other obvious bug I've written in there, but you know, that's how it is when you write stuff down. Um but um you got a joint account with your wife, right?

05:53 And then you synchronize clocks and you and your wife go to different ATMs and you both go and take out the last £100 in your account. Yeah. Exactly. Yeah. Right. All right. You ready? Go. The pair of you both try and take out £100 at the same time. And so you can imagine somewhere over here there is another cash machine running the same code. They both say, "Is the account balance greater or equal to the amount of cash that you've got?"

06:16 They both go, "Yeah, you want [clears throat] £100?" And you've got £100. Excellent. Move to the next line. dispense a100 pounds, right? I now have a hundred quid in my my pocket as does uh Ness, right? And now we subtract and now unfortunately one of two I mean there's a whole bunch of things that happen even with the subtract part here, right? Because maybe we've even lost money at this point because in the system because you know both of them could read 100 and subtract and write back at zero in which case magically

06:42 £100 has been created out of nowhere or maybe you're now £100 in a rears as one of them did win and whatever. So all these things are possible and there's a whole bunch of solutions to this kind of problem. But this is another sort of human problem. Obviously the bank doesn't do this. Do not try this at home please. [laughter] And then just sort of a last example.

07:05 This one's a little bit more contrived as if these aren't contrived already. But um you know if you've got like you could imagine like a staff rotor or something uh uh like where you know everyone's Monday Tuesday Wednesday Thursday Friday whatever and it's posted on a common notice board and it says Monday, Tuesday, Wednesday, Thursday, Friday and it's everyone's shifts or whatever.

07:23 And now you're the kind of person who wants to make sure that you um you turn up on time. So you're copying down into your own diary the uh the details of the shift, right? But it takes you a while because you got to go day today to day today to day and then um by the end of it perhaps what's happened is that the manager while you were doing this has been gone has gone oh hang on a second Matt needs to work on a Friday as well but I'll take him off Monday.

07:45 I've already copied down Monday and then by the time he's changed out Monday and put me on Friday. Um I'm now also on Friday by the time I'm copying out Friday. And then suddenly now I've got two shifts that and I'm like wait a second that doesn't seem right. I only was meant to do one shift this week. or or the reverse, you know, if you were on Friday and you switch with Monday, now you're like, "Hey, I've got a week off, right?"

08:05 And that's not okay. Obviously, now I mean, in a human situation, you probably spot the manager going and changing the pieces of paper, but like from a computer point of view, there's not an obvious way of how to solve that particular problem. Um, there are some other ways that you can get stuck or come acer as well. I mean, we haven't talked about many solutions to any of these things here.

08:26 Hopefully we'll we'll we'll at least cover a couple of these, but we'll start with these. All all those ones are races where nobody kind of gets stuck. There was no problem. I mean, I suppose you could argue that us, you know, talking over each other. We were sort of stuck. There's there's a sort of different name for the ways that that computer programs can get stuck.

08:44 Um, if you're stuck, but you're both still running a program, we call that live lock. We're both locked. And that's sort of similar to how we are if we were both backing off and if we would have carried on forever, we'd have been stuck in a loop. Um, other times you can be stuck in something called a deadlock. And an example of a deadlock is you pull up to a three-way mini roundabout.

09:04 For Americans, that would be like a stop sign. And you arrive at the mini roundabout exactly the same time as two other people. And now you're all waiting for the person like to your right to go or to go so that you can go. And now again, humans, somebody somewhere is going to be, you know, edging out and will disappear off, you know, ahead of everyone else.

09:22 Probably the person with the uh uh actually I shan say I was going to make a comment about which cars might might do what. But no, let's not go there. [laughter] But yeah, so somebody will will will will pull out in front. But again, with computers, if you're if the rule is look to your right, if there's someone there, wait for them to go. You're stuck.

09:40 for our American viewers and also our Brits, I suppose. Like, so roundabout, you give way to your right, with the stop signs, it's whoever arrived first. And again, if you can't see because everyone appears to have arrived at the same time, you're all waiting for someone else to think that they're the person who was first. And again, there's a lot of waving that happens between humans and nodding and flashing of lights and whatever.

09:59 But again, with computers, you have to design that in. But absent of anything designed in, you are all stuck now for all eternity. And I'm sure you've also been in a case in like a car park when someone's trying to pull out of a space, but someone's now coming behind them and then there's someone around the corner who's trying to get into that space and then you're like again, we're in complete gridlock and we can't make progress.

10:18 And that's kind of the definition of of deadlock. You know, processes or computer programs that cannot make any further progress um at all. Uh the the sort of the classic example of this is called the dining philosophers problem, but there's a better example of this. And this is again now more contrived, but imagine we have a bunch of robots around a round table.

10:39 And for whatever reason, because robots don't care about hygiene, they're going to be sharing utensils as you do. They've got a bowl of noodles in front of them that they want to eat. Again, why would a robot eat? I don't know. The analogy is not great. uh they've got a chopstick either side of them, but there's only enough for one either side. So effectively, they're they're sharing the chopstick with the person to the side of them.

11:00 Now, if the computer, if the robots are programmed to pick up the left chopstick and then pick up the right chopstick and then eat once they've got two chopsticks, we're back to where we were before. This is like the mini roundabout problem, right? Everyone's stuck. And so the solution for them is to just some at le if one robot picks up the right one first then we're probably okay because they will get the second chopstick they'll eat their thing they put them down and now things will carry on you know everyone will

11:27 be able to continue um uh uh eating right so again a sort of randomness is a solution to that problem solution is kind of again strong there it feels a bit unsatisfying to >> a way to mitigate it is it I suppose rather than a solution I guess >> right Right. Um, and then there's there's the last one is a is a kids game that actually came up rather amusingly on my one of my feeds and it was a a little video of something called Rob the Nest, which I've never heard of before, but it was like so perfect, especially given

11:58 that we were going to do this particular episode. And so the game is this. Um, you got three children at uh the points of a triangle. They each have a traffic cone and their job is to rob the other two traffic cones and end up with three traffic cones in their nest, right? In their base. They're not allowed to interfere with the other person. They can only run and grab another cone and then get back to their base and whatever.

12:22 So, there's no defense that they can do, but it's absolutely hilarious to watch. It's like a It was a two-minute long video. And the kids, you can't win, right? You can't win. So you're always >> around and moving them backwards. Yeah. Okay. >> Yeah. You can imagine what it looks like, you know, like and and eventually the kids basically have to understand that they can't win this.

12:42 It's not a winnable game. You either have to collaborate in some way or or uh or accept that you're just going to be running around for all eternity. And that's that's another example of a live lock. Everyone is making some kind of progress at each time. Like, hey, I got that traffic cone, but then I came back and my own traffic cone's gone. Now I'm going to go and get the other one because their their base is undefended because they're taking the other traffic cone.

13:03 And so it feels like you're doing work and you know and your CPU or whatever is churning away, you know, but at no point will you ever complete the task that you've been been given? Uh so what do we do about these things? How do we solve these problems? I mean some of them are design issues. So the coffee machine, for example, put a second button on that.

13:26 That just seems to make sense, right? you know or or you know have a small window when it stops that it doesn't immediately start if you press it again or beep three times or something like that. Now that's a very human solution to the problem. That's there there is uh you know in in software we try and make things item potent if we can. Uh, for example, um, uh, sometimes when you're on a web page, uh, the web page will give you a unique magic token that's made up just for that one transaction.

13:53 And then if your browser either reloads or restarts or, you know, the the connection goes down and comes back up again, then the same you, you know, your post when you've clicked a button of like, no, post my my comment, you always give the last token that you were given from the web server. And if it sees the same one twice, it just ignores the second one.

14:12 It goes, "Well, I already saw this one. I know that you've already done this." So, that's another solution. Making it item potent means that like the the duplication and that's slightly to the side of like race conditions, but it's a a an approach you can do. Um, and then, you know, for for buying milk when you're when you're uh in the flat, maybe you leave a note when you go out, but then there's another race as to whether or not you both see the note at the same time or whatever.

14:36 Obviously, I think with humans, you would spot the other thing, the other person being there. Uh but typically we use things called locks. And a lock sounds like a security thing. It sounds like you know you're making something safe by locking it. But in this instance it is a mutual exclusion. It says um for this part of a piece of code we have taken some magical token that says only this program can run this bit of the code that all so in this instance the the lock would be like okay I take out the lock.

15:05 No one else is in the house now right and no one is outside to doing it. the the u sorry no one's outside buying milk right now. Now I will both check the fridge. If there's no milk, I will leave a note on the fridge and then I will go out to Tesco's and then drop the lock. And then as long as everybody follows the same principles, they will either discover that there is milk in the fridge or there is no milk in the fridge and no note, which means that they definitely 100% can go and buy milk or they open the fridge

15:32 and there is a note and they go, well, someone else is doing this, I'll wait for it. But the lock guarantees that. sort of necessarily the lock reduces the concurrency that you have. So you know there is one lock it's a bottleneck but it's hopefully it's just a short time and then that that just guarantees correctness. Uh again with our joint account over here uh the first thing that will happen is uh the you know take a lock out on that account.

15:57 We can't obviously lock the entire bank here and say hey the entire bank every transaction must stop now. That would probably be bad. And this is simplified. Obviously, there are much more scalable ways of doing this. And then we unlock at the end here. And that means that nobody else uh you know there will be a short pause while um my my wife who's trying to take out the money that she won't be able to get this lock or rather the ATM that she's at won't be able to get the lock and it will pause there.

16:24 What typically happens is a lock actually just suspends the program until the lock is available and then obviously she will now discover that she doesn't have enough money to take it out. So >> do do I can I be that guy? What if you both go for the lock at the same time? >> Right. So that is that is no that's a great question. There is magic and I'm going to put my air quotes here.

16:43 We we will talk about this perhaps another time as to how this works. There are some primitives at the CPU level that let you I mean obviously this is a distributed problem with two ATMs, right? But but somewhere there is a machine somewhere there's a computer somewhere where these requests come in and somebody gets the lock and somebody doesn't get the lock.

16:59 But there is a guarantee even in a machine where there are multiple CPUs all on the same um board all sharing the same memory, there are mechanisms inside the circuitry that allow this to happen. It's a primitive that has to be baked into the CPU and the me memory system and everything. So yeah, but very good question. uh and typically somebody loses uh you don't get the lock and then you can choose to do something like just keep polling until the lock becomes available or in the case of like your desktop operating

17:30 system you go to sleep for a little bit and let someone else's process run you know like your video ed video editing system comes up for a bit longer you get to 16 milliseconds of video editing and then it goes back and tries again and goes oh how there we are or more more sophisticated things but yeah we'll go into the actual CPUess of that some other time and some other tricks that you can do the staff wrote a thing with people copying down.

17:50 You could imagine that being using a lock as well, but that now speaks to this sort of bottleneck I spoke about because if you need to take the lock just to even read the, you know, copying down things, you're blocking everyone else from being able to even read things. And so there are some techniques which we'll talk about another time where when you have some shared information that's mostly read by people and very infrequently updated, there are some tricks to doing that efficiently and effectively.

18:14 And then all of our other cases, the mini roundabouts and the robots with chopsticks and things, you just have to design an algorithm to be thoughtful about how the um the locking uh or rather how they will interact with each other. And that's what makes this stuff really difficult to get right in [laughter] cuz you know a lot of this stuff is emergent, right?

18:32 Until you actually run it in production with lots of things trying to do this thing at the same thing at the same time, you won't find these things, especially modern CPUs, right? The gap between each of these instructions is like a third of a nancond. though like the the window of getting it of actually discovering that you've locked and moved into the other thing is so tiny but it's there.

18:49 One thing we uh I didn't mention obviously is when we were talking over each other at the beginning is that that is a very much a problem with um cell phone devices and with older Ethernet cables where you would share one Ethernet cable amongst all the computers that like they would want to talk uh to say send a packet and then they would discover that actually someone else was already using the line and obviously there's a delay between discovering that someone's on the line and you starting talking.

19:13 So they have to have this sort of chatter this back off problem. >> I think Wi-Fi as well isn't it? We I think you feel like we've talked about that at some point on the channel anyway. >> Exactly. Yeah. No, Wi-Fi has the same thing. You're like broadcasting on the same frequency. You're trying to get into a a slot um in the time that's like allocated to you, but someone else might not know that you're there.

19:33 There's a Yeah, it's it's a whole it's a whole thing. It's it's it happens for real all the time. Like literally, while we're talking now, all of the bites are are competing with everyone else in my house's uh Wi-Fi to try and get through to the internet to talk to you. So, yeah. 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.

20:04 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