1 00:00:03,800 --> 00:00:11,800 Okay. So now, we're going to talk about how to implement mutual exclusion without 2 00:00:11,800 --> 00:00:17,143 atomic operations. So, I shall ask here, how many people here have seen mutual 3 00:00:17,143 --> 00:00:23,421 exclusion without atomic operations before? Okay, few. People probably taken 4 00:00:23,421 --> 00:00:29,206 an operating systems class might have seen this before. but it's all tricky and good 5 00:00:29,206 --> 00:00:34,858 to refresh anyway. so we're going to throw out test in site, we're going to throw out 6 00:00:34,858 --> 00:00:40,444 other things. We're going to look how you have locks and mutual exclusion without 7 00:00:40,444 --> 00:00:45,830 any ordering or without having special instructions added to our instruction set. 8 00:00:45,830 --> 00:00:51,416 So, let's, let's take a look at a basic piece of code here that is wrapping around 9 00:00:51,416 --> 00:00:56,754 a critical section, trying to implement a p and a v. And we're going to, we're going 10 00:00:56,754 --> 00:01:01,658 to look at the case where we only have two threads. The n, the n threaded case gets a 11 00:01:01,658 --> 00:01:07,338 lot more complicated. So, in this simple case here, an easy way to go about doing 12 00:01:07,338 --> 00:01:16,997 this is, or, or one way to think about doing this is process one sets its 13 00:01:16,997 --> 00:01:24,653 variable here to one. Then, it checks to see if the other process, process has 14 00:01:24,653 --> 00:01:30,011 written it's lock variable. And these are two different variables, c1 and c2. And 15 00:01:30,011 --> 00:01:40,040 we're assuming sequential consen, consistency for this. If it sees that the 16 00:01:40,040 --> 00:01:45,713 other process wrote that value to two, or to one, c2 to one, it says, oh, process 17 00:01:45,713 --> 00:01:51,166 two already won here. It's going to go execute its critical section. So, it will 18 00:01:51,166 --> 00:01:57,953 sit here and loop until c2 is set to zero at the end of the critical section. Okay, 19 00:01:57,953 --> 00:02:04,368 any one see any problems here? Yeah. So, if they both set their variables to one, 20 00:02:04,368 --> 00:02:10,625 so if we interleave this instruction and this instruction, and then both do the 21 00:02:10,625 --> 00:02:16,384 checks, c1 and c2 are both going to be equal to one. They're both going to check 22 00:02:16,384 --> 00:02:21,322 if, and they're going to say, okay. Yeah, c2 is equal to one, c1 is equal to one. 23 00:02:21,322 --> 00:02:28,070 It's been forever. None of them will ever get to the release of the sum before, and 24 00:02:28,070 --> 00:02:34,843 all of the sudden you have deadlock. that's not great. So, this is why this 25 00:02:34,843 --> 00:02:41,561 stuff is really hard to do. So, let's look at our second attempt here. let's try to, 26 00:02:41,561 --> 00:02:49,112 to make th at better by adding a little more checking in here. So, same thing. c1 27 00:02:49,112 --> 00:02:56,900 is equal to one, c2 is equal to one. It does the same checks to see if the other 28 00:02:56,900 --> 00:03:02,824 person, the other thread set the, the variable. And if it doesn't win, it clears 29 00:03:02,824 --> 00:03:11,630 its own. So, it sets c1 back to zero for, if it fails, and moves back up here. This 30 00:03:11,630 --> 00:03:21,758 looks, looks a lot better. Yeah. We're not getting any deadlocks here, I don't think. 31 00:03:21,758 --> 00:03:27,470 Cuz, let's say we're trying to interleave these things, c1 sets to one, c2 sets to 32 00:03:27,470 --> 00:03:33,039 one, they both do the check at the same time. They both say, oh, the other person 33 00:03:33,039 --> 00:03:39,628 grabbed it, I'll release my variable, set it to zero, and loop back around. So, we 34 00:03:39,628 --> 00:03:45,482 don't deadlock here. And if you perturb the system a little bit, at some point, 35 00:03:45,482 --> 00:03:50,298 one of them's going to fall through we'll say. But what happens if the system's not 36 00:03:50,298 --> 00:04:01,559 perturbed? Well, you can actually hit livelock here. Because they can just sit 37 00:04:01,559 --> 00:04:06,260 there and in lock step if you interleave these three instructions with these three 38 00:04:06,260 --> 00:04:11,042 instructions here they're going to just keep going through the loops, clearing the 39 00:04:11,042 --> 00:04:15,103 variables, setting the variables, clearing the variables, setting the variables, 40 00:04:15,103 --> 00:04:19,113 testing. And none of them, neither of these two processes are ever going to fall 41 00:04:19,113 --> 00:04:23,122 into the critical section. So, livelock here is just as bad as deadlock, in this 42 00:04:23,122 --> 00:04:32,816 case. And, another bad thing here is, we have no guarantees of fairness. So, you 43 00:04:32,816 --> 00:04:40,808 could actually have a case where one process grabs this lock, we'll say. The 44 00:04:40,808 --> 00:04:47,254 other one sits here's in, in loops and it's able to execute its critical section, 45 00:04:47,254 --> 00:04:52,849 clear c1, get back around set c1 before process two is actually able to go around 46 00:04:52,849 --> 00:04:56,915 this loop. then you're going to say processors probably not running at 47 00:04:56,915 --> 00:05:01,082 different speeds. Well, that's true but maybe this one has to take more cache 48 00:05:01,082 --> 00:05:05,688 processes than this one or who knows, you know, you don't have a strong guarantee. 49 00:05:05,688 --> 00:05:10,938 You can't prove that one thread is not going to starve. So, this is a fail. We 50 00:05:10,938 --> 00:05:20,507 can't, we can't have mutual exclusion this way. So instead, we go and we say well, 51 00:05:20,507 --> 00:05:25,907 let's make it more complica ted and this came up, was made by Decker, and is 52 00:05:25,907 --> 00:05:31,250 largely called Decker's Algorithm. And this is actually a protocol from mutual 53 00:05:30,577 --> 00:05:34,675 exclusion which works. We're just using those in stores. And we're introducing 54 00:05:34,675 --> 00:05:38,941 another variable here, and this is a shared variable between process one and 55 00:05:38,941 --> 00:05:45,587 process two and we call this the turn variable. So, this looks pretty similar to 56 00:05:45,587 --> 00:05:53,887 what we had in the previous slide. But now, the turn variable is shared between 57 00:05:53,887 --> 00:05:59,763 the two. And what this is really going to act as is this is going to act as a 58 00:05:59,763 --> 00:06:07,209 tiebreaker in the case where they both set c1 effectively at the same time. And the 59 00:06:07,209 --> 00:06:13,831 tiebreaker is interesting here because, actually it's those two things, it's 60 00:06:13,831 --> 00:06:19,160 tiebreaker and we'll see how it, it's able to solve some problems around starvation. 61 00:06:18,453 --> 00:06:25,181 But the turn variable, one of the two threads here, because its a shared 62 00:06:25,181 --> 00:06:31,033 variable, and were sequentially consistent, is going to execute last, 63 00:06:31,033 --> 00:06:39,156 we'll say. Either through the left side or the right side. so, when you come down to 64 00:06:39,156 --> 00:06:50,488 here and do this check, whoever raced and actually set that turn variable last, the 65 00:06:50,488 --> 00:06:57,628 other thread is going to execute. So, let's say, process two, if we interleave 66 00:06:57,628 --> 00:07:07,760 these and these, process two now sets process two turns equal two happen last. 67 00:07:08,200 --> 00:07:20,050 And when this goes to execute here, we'll see that c1 is set and turn is equal to 68 00:07:20,050 --> 00:07:30,091 two. So, we're just going to sit here and spin. The other thread is going to see 69 00:07:30,091 --> 00:07:38,448 turn equal to two, and c2 is set. But we have a logical end here, so both of these 70 00:07:38,448 --> 00:07:43,414 are not going to be true. So, it's going to fall through and execute its critical 71 00:07:43,414 --> 00:07:51,594 section at this point. At the end, c1 is going to get cleared. And what happens 72 00:07:51,594 --> 00:07:58,520 here is, that's going to allow this other process to enter into its critical 73 00:07:58,520 --> 00:08:04,872 section. So, why is this nice from a starvation perspective is, at least for 74 00:08:04,872 --> 00:08:09,977 two processes, it's going to allow you to alternate here. Because one of them is 75 00:08:09,977 --> 00:08:15,150 going to enter in, and when the other one goes to clear this variable, you're 76 00:08:15,150 --> 00:08:20,050 guaranteed that the other one can go execute that point. So, you're not going 77 00:08:19,642 --> 00:08:39,300 to have starvation. Now, the reason you don't get starvation is actually kind of 78 00:08:39,300 --> 00:08:45,576 subtle. Okay. So, let's look at the starvation case. So, let's say possible 79 00:08:44,751 --> 00:08:54,374 it's really fast. They just loop around and they came, get around this loop and 80 00:08:54,374 --> 00:09:01,797 come to this point before process two can basically loop around here once. That's, 81 00:09:01,797 --> 00:09:08,303 is that the case you want to look at? Yeah. So, what's going to happen at that 82 00:09:08,303 --> 00:09:15,635 point is. Well, two, two things are going to happen. When c1 gets up to zero, what's 83 00:09:15,635 --> 00:09:20,302 going to happen here is, process two will actually see c1 zero is, is what we're 84 00:09:20,302 --> 00:09:25,848 saying here. This is going to set to zero, and then it's going to set to one, before 85 00:09:25,848 --> 00:09:33,651 this track can happen. But, what is interesting here is that at some point, 86 00:09:33,651 --> 00:09:41,970 but c2 is still set to one. Cuz this, this one sitting here waiting. Okay. So, tc2 87 00:09:41,970 --> 00:09:52,673 set to one, and turn gets set to one. That's going to block process two from 88 00:09:52,673 --> 00:10:01,292 entering, at this point. Or rather this being one and that being one is going to 89 00:10:01,292 --> 00:10:10,177 block it from executing. And when turn gets set to one, or, or rather, let's, 90 00:10:10,177 --> 00:10:13,660 let's hold off and look at this. That's going to allow this process one, and its 91 00:10:13,660 --> 00:10:17,144 going to force this process one to sit here and spin forever. And its not going 92 00:10:17,144 --> 00:10:22,281 to be able to race around this second time. Process two on the other hand, c's 93 00:10:22,281 --> 00:10:28,097 going to be set to one. Now, in the mean time, c was one and then it was zeroc and 94 00:10:28,097 --> 00:10:34,843 then it was one again. But, turn is no longer equal to two, at this point. Which 95 00:10:34,843 --> 00:10:40,785 is going to allow process two to fall through, and act as it's critical section. 96 00:10:40,785 --> 00:10:47,113 So, it's the shared turn variable here, which actually allows us to garauntee if 97 00:10:47,113 --> 00:10:53,577 you have a contended case such that, you're basically going to have a round 98 00:10:53,577 --> 00:10:59,201 robin between the two. Okay. So, I think we went through that. [LAUGH] I wanted to 99 00:11:00,165 --> 00:11:07,556 finish all today, talking about one, one last idea here in the last two minutes. 100 00:11:09,140 --> 00:11:16,425 you can, to do Decker's actually with end processes more than two gets pretty 101 00:11:16,425 --> 00:11:22,507 tricky. Dijkstra shows a proof of that there's something that's simpler to reason 102 00:11:22,507 --> 00:11:27,709 about called the Leslie Lamport's Bakery Alg orithm. 103 00:11:27,710 --> 00:11:32,435 And the bakery, I thought is kind of interesting because the idea is, have you 104 00:11:32,435 --> 00:11:37,101 ever gone into a bakery or gone into a deli, there's the little tickets. And you 105 00:11:37,101 --> 00:11:41,471 go in, you take a ticket, and then you wait for them to either call your number 106 00:11:41,471 --> 00:11:46,610 or the little number on the screen to tick up one. And then, once it ticks up, you go 107 00:11:46,610 --> 00:11:52,318 and you like get your bread or get your sliced cheese, or something. Well, it 108 00:11:52,318 --> 00:12:00,220 could use, which is loads and stores. You don't need locks to go implement something 109 00:12:00,220 --> 00:12:05,460 like that. and I don't want to go into complete detail here, but the, the, 110 00:12:05,792 --> 00:12:13,872 basically the idea here is you set a you set that you want to, you want to take the 111 00:12:13,872 --> 00:12:20,965 lock. And then, what you do is you check if all of the people below you are waiting 112 00:12:20,965 --> 00:12:25,124 in the lock, also, in, in order. So, its kind of like you're, you're checking to 113 00:12:25,124 --> 00:12:30,110 see if the number has incremented up to you at this point. And if everyone below 114 00:12:30,110 --> 00:12:35,455 you is, if there is no one below you is waiting for a lock, then your number came 115 00:12:35,455 --> 00:12:40,601 up and you can go execute. When someone is, you, you can't, you can't go execute 116 00:12:40,601 --> 00:12:45,746 this and you, you wait for the, everyone else to release their, their receptive 117 00:12:45,746 --> 00:12:51,159 variables to one effectively, until the point that it's yours and then you can go 118 00:12:51,159 --> 00:12:56,526 and buy your bread or order your, you cheese. Now, that's not enough to actually 119 00:12:56,526 --> 00:13:00,597 work. there are things called ticket taking locks which is actually a more 120 00:13:00,597 --> 00:13:05,249 general class of this sort of idea here. But, you also need a sort of second matrix 121 00:13:05,249 --> 00:13:09,373 here to prevent sort of AVA problems or things running around. But, I don't want 122 00:13:09,373 --> 00:13:13,814 to go into full detail about that. I just wanted to give you an idea that one way to 123 00:13:13,814 --> 00:13:17,991 go implement sort of fast locks is, or ticket taking locks. You walk in and take 124 00:13:17,991 --> 00:13:22,009 a ticket. This prevents multiple people from hoarding up to the front of the 125 00:13:22,009 --> 00:13:26,668 bakery and all trying to order at exactly the same time. and in the bakery, it's a 126 00:13:26,668 --> 00:13:31,582 little bit easier because on the wall, there's like a number and someone tick the 127 00:13:31,582 --> 00:13:36,496 number each up time. If you don't have a central arbiter to go tick the number up, 128 00:13:36,496 --> 00:13:41,410 you ne ed to somehow make the last person who had to lock increase the number. And 129 00:13:41,410 --> 00:13:46,613 that's what this algorithm's actually doing. Okay. Let's stop here for today. 130 00:13:46,613 --> 00:13:51,731 next time we are going to talk about symmetric multiprocessor. We're running a 131 00:13:51,731 --> 00:13:57,110 little bit behind where we were supposed to be from the syllabus perceptive. We're 132 00:13:57,110 --> 00:14:01,900 about a half a class behind. But, I think we'll be able to pick up most of that.