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:15,488 atomic operations. So, I shall ask here, how many people 3 00:00:15,488 --> 00:00:21,360 here have seen mutual exclusion without atomic operations before? 4 00:00:21,360 --> 00:00:24,285 Okay, few. People probably taken an operating 5 00:00:24,285 --> 00:00:27,078 systems class might have seen this before. 6 00:00:27,078 --> 00:00:30,403 but it's all tricky and good to refresh anyway. 7 00:00:30,403 --> 00:00:35,723 so we're going to throw out test in site, we're going to throw out other things. 8 00:00:35,723 --> 00:00:41,309 We're going to look how you have locks and mutual exclusion without any ordering 9 00:00:41,309 --> 00:00:45,830 or without having special instructions added to our instruction set. 10 00:00:45,830 --> 00:00:50,951 So, let's, let's take a look at a basic piece of code here that is wrapping 11 00:00:50,951 --> 00:00:54,710 around a critical section, trying to implement a p and a v. 12 00:00:54,710 --> 00:00:59,265 And we're going to, we're going to look at the case where we only have two 13 00:00:59,265 --> 00:01:01,892 threads. The n, the n threaded case gets a lot 14 00:01:01,892 --> 00:01:05,220 more complicated. So, in this simple case here, 15 00:01:05,220 --> 00:01:10,728 an easy way to go about doing this is, or, or one way to think about doing this 16 00:01:10,728 --> 00:01:19,820 is [COUGH] process one sets its variable here to one. 17 00:01:21,060 --> 00:01:26,025 Then, it checks to see if the other process, process has written it's lock 18 00:01:26,025 --> 00:01:29,292 variable. And these are two different variables, c1 19 00:01:29,292 --> 00:01:32,167 and c2. And we're assuming sequential consen, 20 00:01:32,167 --> 00:01:41,513 consistency for this. If it sees that the other process wrote 21 00:01:41,513 --> 00:01:46,892 that value to two, or to one, c2 to one, it says, oh, process two already won 22 00:01:46,892 --> 00:01:49,766 here. It's going to go execute its critical 23 00:01:49,766 --> 00:01:55,587 section. So, it will sit here and loop until c2 is set to zero at the end of the 24 00:01:55,587 --> 00:02:00,567 critical section. Okay, any one see any problems here? 25 00:02:00,567 --> 00:02:05,952 Yeah. So, if they both set their variables to one, so if we interleave 26 00:02:05,952 --> 00:02:11,920 this instruction and this instruction, and then both do the checks, 27 00:02:11,920 --> 00:02:14,693 c1 and c2 are both going to be equal to one. 28 00:02:14,693 --> 00:02:18,413 They're both going to check if, and they're going to say, okay. 29 00:02:18,413 --> 00:02:20,037 Yeah, c2 is equal to one, 30 00:02:20,037 --> 00:02:23,140 c1 is equal to one. It's been forever. 31 00:02:23,140 --> 00:02:29,525 None of them will ever get to the release of the sum before, and all of the sudden 32 00:02:29,525 --> 00:02:33,390 you have deadlock. that's not great. 33 00:02:33,390 --> 00:02:36,804 So, this is why this stuff is really hard to do. 34 00:02:36,804 --> 00:02:40,400 So, let's look at our second attempt here. 35 00:02:40,400 --> 00:02:47,466 let's try to, to make that better by adding a little more checking in here. 36 00:02:47,466 --> 00:02:52,900 So, same thing. c1 is equal to one, c2 is equal to one. 37 00:02:52,900 --> 00:02:59,054 [COUGH] It does the same checks to see if the other person, the other thread set 38 00:02:59,054 --> 00:03:03,860 the, the variable. And if it doesn't win, it clears its own. 39 00:03:03,860 --> 00:03:09,520 So, it sets c1 back to zero for, if it fails, and moves back up here. 40 00:03:11,260 --> 00:03:18,116 This looks, looks a lot better. [SOUND] Yeah. 41 00:03:18,116 --> 00:03:21,758 We're not getting any deadlocks here, I don't think. 42 00:03:21,758 --> 00:03:26,684 because, let's say we're trying to interleave these things, c1 sets to one, 43 00:03:26,684 --> 00:03:30,611 c2 sets to one, they both do the check at the same time. 44 00:03:30,611 --> 00:03:35,895 They both say, oh, the other person grabbed it, I'll release my variable, set 45 00:03:35,895 --> 00:03:40,921 it to zero, and loop back around. So, we don't deadlock here. 46 00:03:40,921 --> 00:03:44,640 [SOUND] And if you perturb the system a little bit, 47 00:03:44,640 --> 00:03:48,070 at some point, one of them's going to fall through we'll say. 48 00:03:48,070 --> 00:03:50,900 But what happens if the system's not perturbed? 49 00:03:52,240 --> 00:04:02,295 Well, you can actually hit livelock here. Because they can just sit there and in 50 00:04:02,295 --> 00:04:06,260 lock step if you interleave these three instructions with these three 51 00:04:06,260 --> 00:04:10,373 instructions here they're going to just keep going through the loops, 52 00:04:10,373 --> 00:04:12,687 clearing the variables, setting the variables, 53 00:04:12,687 --> 00:04:15,103 clearing the variables, setting the variables, 54 00:04:15,103 --> 00:04:18,856 testing. And none of them, neither of these two processes are ever going to 55 00:04:18,856 --> 00:04:22,249 fall into the critical section. So, livelock here is just as bad as 56 00:04:22,249 --> 00:04:26,680 deadlock, in this case. And, 57 00:04:26,680 --> 00:04:32,175 another bad thing here is, we have no guarantees of fairness. 58 00:04:32,175 --> 00:04:39,320 So, you could actually have a case where one process grabs this lock, we'll say. 59 00:04:40,480 --> 00:04:46,701 The other one sits here's in, in loops and it's able to execute its critical 60 00:04:46,701 --> 00:04:52,365 section, clear c1, get back around set c1 before process two is actually able to go 61 00:04:52,365 --> 00:04:55,599 around this loop. then you're going to say processors 62 00:04:55,599 --> 00:05:00,041 probably not running at different speeds. Well, that's true but maybe this one has 63 00:05:00,041 --> 00:05:04,372 to take more cache processes than this one or who knows, you know, you don't 64 00:05:04,372 --> 00:05:07,827 have a strong guarantee. You can't prove that one thread is not 65 00:05:07,827 --> 00:05:12,322 going to starve. So, this is a fail. We can't, we can't 66 00:05:12,322 --> 00:05:20,897 have mutual exclusion this way. So instead, we go and we say well, let's 67 00:05:20,897 --> 00:05:26,428 make it more complicated and this came up, was made by Decker, and is largely 68 00:05:26,428 --> 00:05:30,577 called Decker's Algorithm. And this is actually a protocol from 69 00:05:30,577 --> 00:05:34,001 mutual exclusion which works. We're just using those in stores. And we're 70 00:05:34,001 --> 00:05:38,492 introducing another variable here, and this is a shared variable between process 71 00:05:38,492 --> 00:05:41,880 one and process two and we call this the turn variable. 72 00:05:41,880 --> 00:05:48,738 So, this looks pretty similar to what we had in the previous slide. 73 00:05:48,738 --> 00:05:54,243 But now, the turn variable is shared between the 74 00:05:54,243 --> 00:05:57,912 two. And what this is really going to act as 75 00:05:57,912 --> 00:06:03,036 is this is going to act as a tiebreaker in the case where they both set c1 76 00:06:03,036 --> 00:06:09,570 effectively at the same time. And the tiebreaker is interesting here 77 00:06:09,570 --> 00:06:13,831 because, actually it's those two things, it's 78 00:06:13,831 --> 00:06:18,453 tiebreaker and we'll see how it, it's able to solve some problems around 79 00:06:18,453 --> 00:06:23,080 starvation. But the turn variable, one of the two 80 00:06:23,080 --> 00:06:27,098 threads here, because its a shared variable, and were sequentially 81 00:06:27,098 --> 00:06:34,974 consistent, is going to execute last, we'll say. Either through the left side 82 00:06:34,974 --> 00:06:40,282 or the right side. so, when you come down to here and do this 83 00:06:40,282 --> 00:06:44,086 check, whoever raced and actually set that turn 84 00:06:44,086 --> 00:06:53,854 variable last, the other thread is going to execute. 85 00:06:53,854 --> 00:07:00,060 So, let's say, process two, if we interleave these and these, 86 00:07:00,060 --> 00:07:08,200 process two now sets process two turns equal two happen last. 87 00:07:08,200 --> 00:07:18,581 And when this goes to execute here, [COUGH] we'll see that c1 is set and turn 88 00:07:18,581 --> 00:07:23,012 is equal to two. So, we're just going to sit here and 89 00:07:23,012 --> 00:07:30,693 spin. The other thread is going to see turn 90 00:07:30,693 --> 00:07:38,682 equal to two, and c2 is set. But we have a logical end here, so both of these are 91 00:07:38,682 --> 00:07:42,187 not going to be true. So, it's going to fall through and 92 00:07:42,187 --> 00:07:44,700 execute its critical section at this point. 93 00:07:46,660 --> 00:07:53,586 At the end, c1 is going to get cleared. And what happens here is, that's going to 94 00:07:53,586 --> 00:07:59,280 allow this other process to enter into its critical section. 95 00:08:00,380 --> 00:08:05,144 So, why is this nice from a starvation perspective is, at least for two 96 00:08:05,144 --> 00:08:08,479 processes, it's going to allow you to alternate here. 97 00:08:08,479 --> 00:08:14,061 Because one of them is going to enter in, and when the other one goes to clear this 98 00:08:14,061 --> 00:08:18,689 variable, you're guaranteed that the other one can go execute that point. 99 00:08:18,689 --> 00:08:38,026 So, you're not going to have starvation. Now, the reason you don't get starvation 100 00:08:38,026 --> 00:08:40,064 is actually kind of subtle. Okay. 101 00:08:40,064 --> 00:08:45,576 So, let's look at the starvation case. So, let's say possible it's really fast. 102 00:08:48,600 --> 00:08:56,115 They just loop around and they came, get around this loop and come to this point 103 00:08:56,115 --> 00:09:01,155 before process two can basically loop around here once. 104 00:09:01,155 --> 00:09:05,462 That's, is that the case you want to look at? Yeah. 105 00:09:05,462 --> 00:09:09,128 So, what's going to happen at that point is. 106 00:09:09,128 --> 00:09:12,794 Well, two, two things are going to happen. 107 00:09:12,794 --> 00:09:17,560 When c1 gets up to zero, what's going to happen here is, process two will actually 108 00:09:17,560 --> 00:09:20,302 see c1 zero is, is what we're saying here. 109 00:09:21,674 --> 00:09:26,146 This is going to set to zero, and then it's going to set to one, before this 110 00:09:26,146 --> 00:09:32,605 track can happen. But, what is interesting here is that at 111 00:09:32,605 --> 00:09:38,997 some point, but c2 is still set to one. because this, this one sitting here 112 00:09:38,997 --> 00:09:41,205 waiting. Okay. 113 00:09:41,205 --> 00:09:45,900 So, tc2 set to one, and turn gets set to one. 114 00:09:49,440 --> 00:09:54,580 That's going to block process two from entering, at this point. 115 00:09:56,840 --> 00:10:03,680 Or rather this being one and that being one is going to block it from executing. 116 00:10:03,680 --> 00:10:11,015 And when turn gets set to one, or, or rather, let's, let's hold off and 117 00:10:11,015 --> 00:10:13,308 look at this. That's going to allow this process one, 118 00:10:13,308 --> 00:10:16,350 and its going to force this process one to sit here and spin forever. 119 00:10:16,350 --> 00:10:19,680 And its not going to be able to race around this second time. 120 00:10:19,680 --> 00:10:23,812 Process two on the other hand, c's going to be set to one. 121 00:10:23,812 --> 00:10:29,781 Now, in the mean time, c was one and then it was zeroc and then it was one again. 122 00:10:29,781 --> 00:10:34,380 But, turn is no longer equal to two, at this point. 123 00:10:34,380 --> 00:10:40,168 Which is going to allow process two to fall through, and act as it's critical 124 00:10:40,168 --> 00:10:43,718 section. So, it's the shared turn variable here, 125 00:10:43,718 --> 00:10:49,721 which actually allows us to garauntee if you have a contended case such that, 126 00:10:49,721 --> 00:10:55,344 you're basically going to have a round robin between the two. 127 00:10:55,344 --> 00:11:01,530 Okay. So, I think we went through that. [LAUGH] I wanted to finish all today, 128 00:11:01,530 --> 00:11:09,140 talking about one, one last idea here [SOUND] in the last two minutes. [SOUND] 129 00:11:09,140 --> 00:11:13,688 you can, to do Decker's actually with end 130 00:11:13,688 --> 00:11:16,957 processes more than two gets pretty tricky. 131 00:11:16,957 --> 00:11:22,963 Dijkstra shows a proof of that there's something that's simpler to reason about 132 00:11:22,963 --> 00:11:27,710 called the Leslie Lamport's Bakery Algorithm. 133 00:11:27,710 --> 00:11:32,435 And the bakery, I thought is kind of interesting because the idea is, have you 134 00:11:32,435 --> 00:11:36,628 ever gone into a bakery or gone into a deli, there's the little tickets. 135 00:11:36,628 --> 00:11:40,763 And you go in, you take a ticket, and then you wait for them to either call 136 00:11:40,763 --> 00:11:44,425 your number or the little number on the screen to tick up one. 137 00:11:44,425 --> 00:11:49,407 And then, once it ticks up, you go and you like get your bread or get your 138 00:11:49,407 --> 00:11:54,896 sliced cheese, or something. [COUGH] Well, it could use, which is 139 00:11:54,896 --> 00:11:59,388 loads and stores. You don't need locks to go implement 140 00:11:59,388 --> 00:12:04,129 something like that. and I don't want to go into complete 141 00:12:04,129 --> 00:12:09,120 detail here, but the, the, basically the idea here is you set a 142 00:12:10,840 --> 00:12:14,272 you set that you want to, you want to take the lock. 143 00:12:14,272 --> 00:12:21,131 And then, what you do is you check if all of the people below you are waiting in 144 00:12:21,131 --> 00:12:24,458 the lock, also, in, in order. So, its kind of like you're, you're 145 00:12:24,458 --> 00:12:28,640 checking to see if the number has incremented up to you at this point. 146 00:12:28,640 --> 00:12:33,985 And if everyone below you is, if there is no one below you is waiting for a lock, 147 00:12:33,985 --> 00:12:37,193 then your number came up and you can go execute. 148 00:12:37,193 --> 00:12:42,071 When someone is, you, you can't, you can't go execute this and you, you wait 149 00:12:42,071 --> 00:12:46,882 for the, everyone else to release their, their receptive variables to one 150 00:12:46,882 --> 00:12:52,228 effectively, until the point that it's yours and then you can go and buy your 151 00:12:52,228 --> 00:12:54,940 bread or order your, you cheese. Now, 152 00:12:54,940 --> 00:12:58,588 that's not enough to actually work. [LAUGH] there are things called ticket 153 00:12:58,588 --> 00:13:03,029 taking locks which is actually a more general class of this sort of idea here. 154 00:13:03,029 --> 00:13:06,571 But, you also need a sort of second matrix here to prevent sort of AVA 155 00:13:06,571 --> 00:13:10,589 problems or things running around. But, I don't want to go into full detail 156 00:13:10,589 --> 00:13:13,232 about that. I just wanted to give you an idea that 157 00:13:13,232 --> 00:13:16,880 one way to go implement sort of fast locks is, or ticket taking locks. 158 00:13:16,880 --> 00:13:20,317 You walk in and take a ticket. This prevents multiple people from 159 00:13:20,317 --> 00:13:24,441 hoarding up to the front of the bakery and all trying to order at exactly the 160 00:13:24,441 --> 00:13:27,336 same time. and in the bakery, it's a little bit 161 00:13:27,336 --> 00:13:32,310 easier because on the wall, there's like a number and someone tick the number each 162 00:13:32,310 --> 00:13:35,344 up time. If you don't have a central arbiter to go 163 00:13:35,344 --> 00:13:39,954 tick the number up, you need to somehow make the last person who had to lock 164 00:13:39,954 --> 00:13:43,716 increase the number. And that's what this algorithm's actually 165 00:13:43,716 --> 00:13:44,908 doing. Okay. 166 00:13:44,908 --> 00:13:49,697 Let's stop here for today. next time we are going to talk about symmetric 167 00:13:49,697 --> 00:13:53,305 multiprocessor. We're running a little bit behind where 168 00:13:53,305 --> 00:13:56,717 we were supposed to be from the syllabus perceptive. 169 00:13:56,717 --> 00:14:01,571 We're about a half a class behind. But, I think we'll be able to pick up most of 170 00:14:01,571 --> 00:14:01,900 that.