1 00:00:04,520 --> 00:00:13,213 And Dijkstra came up with this naming 2 00:00:13,213 --> 00:00:19,686 nomenclature. So, implementation of sum of force. 3 00:00:19,686 --> 00:00:25,203 this idea is all well and good, but we still need some way to come up with 4 00:00:25,203 --> 00:00:30,002 mutual exclusion. Believe it or not, you can actually do 5 00:00:30,002 --> 00:00:34,326 this with just loads and stores. And we're going to be talking about that a 6 00:00:34,326 --> 00:00:37,569 little bit later in class. But it's really pretty slow. 7 00:00:37,569 --> 00:00:40,752 and it's, it, there are some algorithms that can do 8 00:00:40,752 --> 00:00:45,436 this with just loads and stores. But from an implementation perspective, people 9 00:00:45,436 --> 00:00:48,800 typically try to go faster. So, if you want to go faster, 10 00:00:48,800 --> 00:00:53,327 it might be helpful for your computer architecture, your instructions set 11 00:00:53,327 --> 00:00:57,979 architect, to come up with a special instruction which will allow you to do 12 00:00:57,979 --> 00:01:02,754 something atomically. So, when we say do something atomically, it means there's 13 00:01:02,754 --> 00:01:06,290 nothing else can be interweaved in that, in the meantime. 14 00:01:06,290 --> 00:01:12,658 And the, the simple solution here is that you add an atomic operation which can do 15 00:01:12,658 --> 00:01:16,400 a read, a modify, and a write. 16 00:01:16,400 --> 00:01:20,270 All atomically if nothing else interleaving it. 17 00:01:20,270 --> 00:01:25,640 So going, going back to our locks and sum of fours here. 18 00:01:25,640 --> 00:01:30,366 All inside of this, this P and all inside this V here, you need to somehow, 19 00:01:30,366 --> 00:01:34,381 atomically modify S. You need to be able to read S you need to 20 00:01:34,381 --> 00:01:39,691 be able to write S if you were able to implement this somehow with code inside 21 00:01:39,691 --> 00:01:43,900 of the implementation of, of P and inside the implementation of V. 22 00:01:44,980 --> 00:01:49,819 So, the primitive here that makes this faster is having some read modify write 23 00:01:49,819 --> 00:01:52,486 operation. And we're going to look at a couple 24 00:01:52,486 --> 00:01:59,876 different choices of this. One of the most basic ones is test and 25 00:01:59,876 --> 00:02:03,060 set. x86 has this instruction. 26 00:02:03,060 --> 00:02:09,060 This is the one of the most basic operations on x86 for atomic operations. 27 00:02:09,060 --> 00:02:14,085 lots of other architectures have an instructions which does this. 28 00:02:14,085 --> 00:02:19,035 So, we write here a piece a code. But in reality, this is a piece of pseudo 29 00:02:19,035 --> 00:02:24,510 code, but in reality, this is an instruction which we'll actually do this 30 00:02:24,510 --> 00:02:27,960 atomically relative to the whole rest of the system. 31 00:02:27,960 --> 00:02:33,832 So, let's look at what test and set does. The basic idea of test and set is it, is 32 00:02:33,832 --> 00:02:39,720 it's probably one of the most primitive atomic operations you can do. I've seen 33 00:02:39,720 --> 00:02:45,536 something slightly simpler than this. there's like a test and clear which is a 34 00:02:45,536 --> 00:02:50,580 little bit easier to implement. But, largely the idea is that, 35 00:02:50,580 --> 00:02:57,346 you're going to look at a memory address. And if that memory address is what you 36 00:02:57,346 --> 00:03:04,180 expect it to be, then write some value. 37 00:03:06,920 --> 00:03:11,648 And, implicit in this piece of code here is 38 00:03:11,648 --> 00:03:15,796 that, the piece of code which executed the testing set needs to know whether 39 00:03:15,796 --> 00:03:20,108 it's exceeded and was successfully able to write the value or not to, or to not 40 00:03:20,108 --> 00:03:24,146 write the value. So, it's sort of a status code and that's returned in this 41 00:03:24,146 --> 00:03:28,340 register R here. So, if we look at this piece of code, you 42 00:03:28,340 --> 00:03:32,999 pass into it a memory reference, a memory address, which is the address of the sum 43 00:03:32,999 --> 00:03:36,794 of four or the address lock. And you pass into it and, and, and a 44 00:03:36,794 --> 00:03:42,884 register name. We do a load into that register and that 45 00:03:42,884 --> 00:03:48,940 happens unconditionally. This part here though, 46 00:03:48,940 --> 00:03:54,807 is the, is the the test part. So the test part here is we check whether 47 00:03:54,807 --> 00:03:59,501 the thing we just read from this memory address is zero. 48 00:03:59,501 --> 00:04:03,758 And if so, we're going to write a one to the memory 49 00:04:03,758 --> 00:04:06,389 address. Sometimes these test and set operations 50 00:04:06,389 --> 00:04:10,027 will actually allow you to write something else besides just one. 51 00:04:10,027 --> 00:04:13,554 But, for right now, let's, this is sort of the more basic one here. 52 00:04:13,554 --> 00:04:15,905 So, it writes a one to that memory address. 53 00:04:15,905 --> 00:04:21,069 And what's important here is the architecture guarantees that all of this 54 00:04:21,069 --> 00:04:25,520 happens atomically. But what's interesting is, if you think 55 00:04:25,520 --> 00:04:30,740 about our processors that we built, this requires a load and a store. 56 00:04:31,760 --> 00:04:34,390 Hm. So, we will talk about how we implement 57 00:04:34,390 --> 00:04:38,650 this a little bit in, in a few slides. But, you basically have to stop 58 00:04:38,650 --> 00:04:42,283 everything else, stop all other loads and stores happening 59 00:04:42,283 --> 00:04:47,935 in the system. Do this load, do the test, and possibly 60 00:04:47,935 --> 00:04:53,231 do the store in hardware. One of the more basic ways this is done 61 00:04:53,231 --> 00:04:57,193 or one of the original way this was done actually on some of the SA-6 based 62 00:04:57,193 --> 00:05:00,880 architectures, is there is something called the lock bit on the bus. 63 00:05:00,880 --> 00:05:04,677 So what they did is when one processor was going to go execute a atomic 64 00:05:04,677 --> 00:05:07,318 operation like this, a testing set for instance. 65 00:05:07,318 --> 00:05:11,610 You'd actually broadcast all of the other processors in the system saying, I'm 66 00:05:11,610 --> 00:05:13,756 about to do this. Do not touch anything. 67 00:05:13,756 --> 00:05:16,893 Do not issue any memory [LAUGH] instructions effectively, 68 00:05:16,893 --> 00:05:19,810 or do not issue any bus, based memory instructions. 69 00:05:19,810 --> 00:05:24,146 It would, it would do the load, it would do the test, and it would do the set, and 70 00:05:24,146 --> 00:05:28,700 then it would release the broadcast bit. This is the wire on a multi-drop bus. 71 00:05:28,700 --> 00:05:35,301 that's a pretty big hammer. things have gone a little bit better 72 00:05:35,301 --> 00:05:38,520 since then. But, just to give you an idea of basic 73 00:05:38,520 --> 00:05:45,981 hardware implementation of this. things got a little more sophisticated 74 00:05:45,981 --> 00:05:49,519 this sort of showed up in the, the 70s' here. 75 00:05:49,519 --> 00:05:53,734 These fancier operations or the fancy atomic operations. 76 00:05:53,734 --> 00:06:00,046 So, this whole box here is still a atomic operation. 77 00:06:00,046 --> 00:06:04,366 All the, the code in here happens atomically, and what this basically does 78 00:06:04,366 --> 00:06:08,095 is it's going to take a memory address and add something to it. 79 00:06:08,095 --> 00:06:13,457 So, we're going to add Rv to R and put that into memory at the same memory 80 00:06:13,457 --> 00:06:17,478 address and, so we're going to do the load in the store here, atomically. 81 00:06:17,478 --> 00:06:20,600 So, it's a read modified write operation also. 82 00:06:20,600 --> 00:06:25,232 And having it all the atomic. Note, this still actually returns into 83 00:06:25,232 --> 00:06:30,478 register R here, the original value. And sometimes that's actually very useful 84 00:06:30,478 --> 00:06:35,519 if you're trying to implement a semifor based on this you kind of want to see 85 00:06:35,519 --> 00:06:39,879 what was there before. There's some, there's some jokes around 86 00:06:39,879 --> 00:06:47,106 fetching at here, though. the atomic operation community kind of 87 00:06:47,106 --> 00:06:52,979 push this to the extreme at some point and people started having sort of fetch 88 00:06:52,979 --> 00:06:58,553 and insert something here. So, fetch and multiply, fetch and divide or, or things 89 00:06:58,553 --> 00:07:03,980 like that and people started building some stranger machines that had 90 00:07:03,980 --> 00:07:07,821 fetch and something else. There's this old joke that someone was 91 00:07:07,821 --> 00:07:10,974 going to implement instruction called fetch and FFT. 92 00:07:10,974 --> 00:07:15,961 So, it would be atomic Fourier Transform. I don't think it ever got to that point. 93 00:07:15,961 --> 00:07:20,089 But, in the, in the microcoded days and the, and the early microprocessor 94 00:07:20,089 --> 00:07:24,660 microcoded days, there was some pretty sophisticated atomic operations. 95 00:07:24,660 --> 00:07:28,479 That's largely been decided to not be a good direction to go. 96 00:07:28,479 --> 00:07:33,300 you want to have a little bit of complexity in your atomic operations. so 97 00:07:33,300 --> 00:07:37,746 maybe test and set is a little too simple. But, some of these fancier 98 00:07:37,746 --> 00:07:41,780 fetching FFTs is probably a little bit too complex. 99 00:07:41,780 --> 00:07:48,834 [COUGH] Here's another interesting operation that is atomic. 100 00:07:48,834 --> 00:07:54,528 And this one you can actually build some pretty interesting semaphores out of. 101 00:07:54,528 --> 00:07:58,184 It's called swap. So, it takes a register value and a 102 00:07:58,184 --> 00:08:04,160 memory location, and it'll take what's in the memory location and what's in the 103 00:08:04,160 --> 00:08:10,146 register and swap the two things. And note, we need to use we use a 104 00:08:10,146 --> 00:08:15,320 temporary here because you can't actually swap two things without a temporary. 105 00:08:18,380 --> 00:08:21,962 This is actually not very common because it's kind of hard to use. 106 00:08:21,962 --> 00:08:26,495 so what's a little bit more common to something called compare and swap which 107 00:08:26,495 --> 00:08:30,134 is something between kind of a test and set, and a swap operation. 108 00:08:30,134 --> 00:08:34,880 And that's, that's what commonly used and we'll talk about that in a second. 109 00:08:34,880 --> 00:08:39,588 Okay, so now we go back to the multiple consumers problems that we have, where 110 00:08:39,588 --> 00:08:42,660 multiple people were trying to DQ from a, a Q. 111 00:08:42,660 --> 00:08:50,460 And let's introduce test and set, and we'll look at our critical section here. 112 00:08:53,880 --> 00:08:58,834 We're going to use this term mutex to basically mean a sum of four that only 113 00:08:58,834 --> 00:09:04,534 one thing can enter at a time. So, what happens at the beginning here is 114 00:09:04,534 --> 00:09:10,726 there is a tight loop, and this tight loop will read from a relocation of mutex 115 00:09:10,726 --> 00:09:14,960 into a temporary register, and will compare it to zero. 116 00:09:19,420 --> 00:09:25,760 Note, we define test and set as writing one to memory if it succeeds. 117 00:09:25,760 --> 00:09:31,490 So if it was zero, that means that it was not able to actually modify memory. 118 00:09:31,490 --> 00:09:35,787 The test failed. So if the test failed, it's just going to 119 00:09:35,787 --> 00:09:40,462 sit and spin here. And we'll call this busy waiting or spin 120 00:09:40,462 --> 00:09:44,760 attritional spinlock, it's called. If it acquired the lock, 121 00:09:46,000 --> 00:09:53,381 this read value would have been a one. So, it would not be equal to, or excuse 122 00:09:53,381 --> 00:09:59,780 me, if there, if it acquired the lock through the, the, the, 123 00:09:59,780 --> 00:10:05,720 you just write, if it's one, it's zero. 124 00:10:07,120 --> 00:10:12,340 Okay, sorry we did this wrong. If, if the memory address was a, 125 00:10:18,420 --> 00:10:26,597 if it was a one coming into here, that means someone else already locked 126 00:10:26,597 --> 00:10:31,747 it. If it's a zero coming into here, that 127 00:10:31,747 --> 00:10:35,808 means no one locked it, but we locked it and set it to a one now. 128 00:10:35,808 --> 00:10:40,821 So if we acquired the lock, we're going to atomically set it to a one, and we're 129 00:10:40,821 --> 00:10:44,501 going to read a zero. So, we'll drop into our critical section 130 00:10:44,501 --> 00:10:49,451 and start executing our critical section. And it, under the critical section, we 131 00:10:49,451 --> 00:10:53,702 can do stores, we can do loads, we can do whatever we want because we're 132 00:10:53,702 --> 00:10:58,397 guaranteeing that no other op, no other processor, no other thread is doing 133 00:10:58,397 --> 00:11:01,697 anything to it. And then at some point, we need to do 134 00:11:01,697 --> 00:11:05,992 the, the release here. And that we actually don't need a test 135 00:11:05,992 --> 00:11:11,612 and set for, we just need a store. A store is just going to clear that in a 136 00:11:11,612 --> 00:11:17,612 real location, and some other thread is safe to go and fall into the critical 137 00:11:17,612 --> 00:11:25,382 section here. Okay. So, this can be done with lots of 138 00:11:25,382 --> 00:11:29,005 different implementations. We showed here of test and set, but this 139 00:11:29,005 --> 00:11:32,034 can be done with swap, it can be done with fetch and add. 140 00:11:32,034 --> 00:11:38,110 The code gets a little bit more complex. But, one of the interesting questions 141 00:11:38,110 --> 00:11:43,360 that comes up is, what do you, what happens if you running along some threat 142 00:11:43,360 --> 00:11:49,170 acquires the critical or acquires the law falls into the critical section and let's 143 00:11:49,170 --> 00:11:53,860 say, terminates or gets swapped out for very long period of time? 144 00:11:55,480 --> 00:11:57,663 [SOUND] What's, what's going to happen here? 145 00:11:57,663 --> 00:12:04,140 [SOUND] Well, system crash. I mean, we, we don't reference bad memory 146 00:12:04,140 --> 00:12:07,202 here. This is more, more of a hang. 147 00:12:07,202 --> 00:12:13,905 So, it's going to freeze. So this is actually pretty common in the 148 00:12:13,905 --> 00:12:21,928 old, for instance, if you look at like non-preemptive operating systems. So, 149 00:12:21,928 --> 00:12:27,465 back in the day of like the original Mac OS before Mac OS became Mac OSX, so 150 00:12:27,465 --> 00:12:32,786 versions sort of nine and earlier. That was a cooperative operating system. 151 00:12:32,786 --> 00:12:38,940 And if someone went and grabbed a lock, and then died or took an error case, 152 00:12:38,940 --> 00:12:43,545 the whole machine would crash, crash. if you're pre-emptive, I mean, there's 153 00:12:43,545 --> 00:12:48,454 like a timer going off, it's possible you still you won't be able to make forward 154 00:12:48,454 --> 00:12:52,341 progress. But at least, the OS can interrupt your 155 00:12:52,341 --> 00:12:55,939 process and try and do something about it. 156 00:12:55,939 --> 00:13:01,293 It can detect that one process is hung. But in a cooperative multi-threading 157 00:13:01,293 --> 00:13:05,482 environment, if one process, let's say, just hogs the processor and never gives 158 00:13:05,482 --> 00:13:09,454 back the processor or just dies, and you have some other process, which 159 00:13:09,454 --> 00:13:09,998 say, which, 160 00:13:09,998 --> 00:13:13,371 or, or, let's say, you, you grab the lock and one process and die. 161 00:13:13,371 --> 00:13:17,506 And then, another process is running along and tries to acquire the lock, but 162 00:13:17,506 --> 00:13:21,750 it's just sitting there spinning in this little spin section here for forever. 163 00:13:21,750 --> 00:13:24,389 You're basically just going to hang the processor. 164 00:13:24,389 --> 00:13:26,635 You're not going to see anything else here. 165 00:13:26,635 --> 00:13:30,397 So, you've got to be pretty careful especially in cooperative multi-threading 166 00:13:30,397 --> 00:13:32,700 environments. So, one of the tricks to this actually 167 00:13:32,700 --> 00:13:35,620 is, if you're in a cooperative multi-threaded environment, 168 00:13:35,620 --> 00:13:42,636 they'll typically put inside the spin loop here something which will yield to a 169 00:13:42,636 --> 00:13:46,694 different thread. So, someone else can try to do something 170 00:13:46,694 --> 00:13:50,112 in that time. because if you just sit there spinning, 171 00:13:50,112 --> 00:13:56,021 it's very possible that you won't be fair or no one else can ever go to unlock the 172 00:13:56,021 --> 00:13:59,652 lock, for instance. So, you've got to be a little careful 173 00:13:59,652 --> 00:14:04,724 there. Okay. So, we're going to move forward 174 00:14:04,724 --> 00:14:08,116 here. And look at how to do a slightly 175 00:14:08,116 --> 00:14:15,120 different version of the same piece of code, but now with compare and swap. 176 00:14:15,120 --> 00:14:21,429 So, before we do that, let's talk about the, the semantics of compare and swap. 177 00:14:21,429 --> 00:14:27,026 Compare and swap takes memory and two registers here. 178 00:14:27,026 --> 00:14:35,321 And it's going to compare memory with one of the registers. If it's equal, then its 179 00:14:35,321 --> 00:14:43,719 going to take the other register, put it in memory, and effectively swap them in 180 00:14:43,719 --> 00:14:49,396 return of status. If the compare operation fails, and we 181 00:14:49,396 --> 00:14:53,520 come to this L station statement here, we don't do any swap. 182 00:14:53,520 --> 00:14:58,624 So this would be effectively taking a register and a memory location and 183 00:14:58,624 --> 00:15:01,700 swapping them, dependent on another register. 184 00:15:02,820 --> 00:15:07,725 So, it's a little bit more powerful than just swap. It's a little harder to 185 00:15:07,725 --> 00:15:12,763 implement, as you might imagine. it's probably not as hard to implement as 186 00:15:12,763 --> 00:15:18,191 something like fetch and app. The reason for this is, if you want to do 187 00:15:18,191 --> 00:15:23,104 this operation out of the memory system, you can basically send it as atomic sort 188 00:15:23,104 --> 00:15:24,923 of operation. Go to main memory, 189 00:15:24,923 --> 00:15:28,032 compare this, put a comparitor there and swap the two 190 00:15:28,032 --> 00:15:30,378 things. If you try to have these sort of 191 00:15:30,378 --> 00:15:35,012 increments or arbitrary instructions or adds, you need to put a adder out there 192 00:15:35,012 --> 00:15:37,700 for sure. This only needs a comparator out there. 193 00:15:37,700 --> 00:15:41,301 Still, still, still painful to go implement. But, it might a little bit 194 00:15:41,301 --> 00:15:45,678 better than putting a full adder in your memory controller because that's almost 195 00:15:45,678 --> 00:15:49,944 like duplicating your ALU out in your memory sub-system which doesn't make a 196 00:15:49,944 --> 00:15:53,878 whole lot of sense. But, that's, that's why people used to talk about the 197 00:15:53,878 --> 00:15:58,517 fetching FFT. But, okay. So, let's take a look at the same 198 00:15:58,517 --> 00:16:03,629 piece of the same case here of a multi-reader piece of code. 199 00:16:03,629 --> 00:16:09,129 But instead, what we're going to do is we're not going to have a spin lock at 200 00:16:09,129 --> 00:16:13,003 the beginning. Instead, we're going to have a critical 201 00:16:13,003 --> 00:16:19,277 section, but we can concurrently execute critical sections from different threads 202 00:16:19,277 --> 00:16:23,066 here which we're not going to call it a critical section then. 203 00:16:23,066 --> 00:16:27,593 We're going to say, we'll concurrently execute what was in the other thread's 204 00:16:27,593 --> 00:16:32,304 critical section, and then we're going to atomically try to swap out the head 205 00:16:32,304 --> 00:16:36,158 pointer and replace it. So, we're inspectively doing speculative 206 00:16:36,158 --> 00:16:39,119 work here, and this is called non-blockive, 207 00:16:39,119 --> 00:16:44,824 non-blocking synchronization. So, the synchronization primitive we're 208 00:16:44,824 --> 00:16:48,398 going to do the loads, we talked about that before. 209 00:16:48,398 --> 00:16:51,967 We checked to make sure there's at least something available. 210 00:16:51,967 --> 00:16:54,483 [COUGH] We'll pull the, the head pointer off. 211 00:16:54,483 --> 00:16:58,754 This is all speculative work at this point because we have not check to make 212 00:16:58,754 --> 00:17:03,040 sure that we can validly pull off the head of the queue. 213 00:17:03,040 --> 00:17:08,324 We're going to increment the head pointer into a temporary here that we're going to 214 00:17:08,324 --> 00:17:12,891 call new head or registered new head. And then, we're going to do a, try to 215 00:17:12,891 --> 00:17:17,540 swap the new head with the old head atomically. 216 00:17:18,960 --> 00:17:24,268 So, it's going to take the register that we think is the new head and memory 217 00:17:24,268 --> 00:17:29,785 location where the head pointer is. We're going to try to swap these two things. 218 00:17:29,785 --> 00:17:35,094 And the thing that we're dependent on here is that what we think is the old 219 00:17:35,094 --> 00:17:45,098 head, still is the old head. [SOUND] And if, if something bad happens 220 00:17:45,098 --> 00:17:47,498 here, we can, we can try again. 221 00:17:47,498 --> 00:17:55,358 so, so the idea here is that we're going to spin actually in this effectively 222 00:17:55,358 --> 00:18:02,000 bigger loop, trying to speculatively try to go and change the, the head. 223 00:18:03,780 --> 00:18:15,920 [SOUND] So, one, one question that comes up here is, 224 00:18:19,480 --> 00:18:27,748 what if the head was DQ'd from, added back on to, and, and it just so happens 225 00:18:27,748 --> 00:18:32,288 that we have some sort of, it's called an ABA problem? 226 00:18:32,288 --> 00:18:38,113 The headpointer was a, was changed to be, and later changed back to a, 227 00:18:38,113 --> 00:18:48,874 all in, this short period of time. Yeah. 228 00:18:48,874 --> 00:18:52,115 That, that might be a problem here in this piece of code. 229 00:18:52,115 --> 00:18:55,796 You might need to think about that and carefully reason about that. 230 00:18:55,796 --> 00:19:00,135 Usually, you can protect that in some other way sort of, when the, the pointer 231 00:19:00,135 --> 00:19:03,541 wraps around, maybe. if you think about a normal ray, when it 232 00:19:03,541 --> 00:19:07,167 wraps around, you put something which is not a compare and swap. 233 00:19:07,167 --> 00:19:10,792 You put like more spin lock, or a spin loop sort of lock on it. 234 00:19:10,792 --> 00:19:14,967 So, you only have to worry about that in these sort of circular buffers when 235 00:19:14,967 --> 00:19:18,593 something wraps around. because otherwise, there's no, no other way that 236 00:19:18,593 --> 00:19:21,450 the head pointer can go back to where it was before. 237 00:19:21,450 --> 00:19:25,352 But, you do need to worry about that, that you wrapped all the way around the 238 00:19:25,352 --> 00:19:29,151 array in this very short period of time. So, there's some, there's some race 239 00:19:29,151 --> 00:19:32,900 conditions that happen if these non-blocking synchronizations operations. 240 00:19:35,560 --> 00:19:42,480 Another non-blocking synchronization primitive that 241 00:19:42,480 --> 00:19:48,228 is actually really cool, I think, is, goes by lots of different names. 242 00:19:48,228 --> 00:19:54,222 it goes by load locked, load linked, load reserve, and store conditional. 243 00:19:54,222 --> 00:20:00,052 So, you take your ISA, you take your instruction set, and you add two new 244 00:20:00,052 --> 00:20:05,034 instructions. Something which checks to make sure or 245 00:20:05,034 --> 00:20:13,397 something which doesn't load, and what you then do is store conditional 246 00:20:13,397 --> 00:20:18,740 checks to make sure that no one else did a load. 247 00:20:18,740 --> 00:20:27,160 Or a special load link to that same address in the inter-meeting time. 248 00:20:30,560 --> 00:20:33,867 I can explain that one more time, it's a little confusing. 249 00:20:33,867 --> 00:20:36,420 But the, basically the idea is a flag register here. 250 00:20:38,260 --> 00:20:46,261 And in hardware, you do a load link. Just load the value into your register 251 00:20:46,261 --> 00:20:49,046 and its sort of on the side, somewhere next to the register. 252 00:20:49,046 --> 00:20:52,729 It may not be architecturally visible, or shouldn't be architecturally visible 253 00:20:52,729 --> 00:20:55,300 likely. It will set a bit. 254 00:20:56,700 --> 00:21:01,672 You execute your critical section. And when you come back to it, to go do 255 00:21:01,672 --> 00:21:06,960 the store, we say, for this sort of read modified write operations. 256 00:21:06,960 --> 00:21:13,813 When you go to the store, the store checks to make sure the flag is still set 257 00:21:13,813 --> 00:21:16,820 to one. The flag is one. 258 00:21:16,820 --> 00:21:21,188 If it's still one, that means no one did any memory, memory operations to that 259 00:21:21,188 --> 00:21:25,726 address or did at least any load links or store initials to that address in the 260 00:21:25,726 --> 00:21:27,655 inter meeting time. Actually, sorry. 261 00:21:27,655 --> 00:21:31,740 We'll say that in a more completely. No one else did a store conditional 262 00:21:31,740 --> 00:21:34,690 during that time. So, no one else tried to do a store 263 00:21:34,690 --> 00:21:37,413 update. Other people may have tried to do a load. 264 00:21:37,413 --> 00:21:40,314 But, no one else could of store at that 265 00:21:40,314 --> 00:21:45,218 address, or store conditional at that address. Because if someone else did a 266 00:21:45,218 --> 00:21:50,457 store conditional, what'll happen is that it'll actually cancel the other 267 00:21:50,457 --> 00:21:56,280 processor's reservation, so set their flag bits to zero atomically. 268 00:21:56,280 --> 00:22:01,880 This is a pretty primitive, this is a pretty powerful primitive here such that 269 00:22:01,880 --> 00:22:07,497 you can basically do a load. Try to do a store later in the future. 270 00:22:07,497 --> 00:22:11,787 If no one else try to do a store to that same address in the meantime, or a store 271 00:22:11,787 --> 00:22:15,647 conditional to that address in the meantime, your store goes through and 272 00:22:15,647 --> 00:22:19,991 everybody else's loads. If they do a load in the meantime, will get invalidated or 273 00:22:19,991 --> 00:22:24,900 they'll know that it gets invalidated when they go to do a store conditional. 274 00:22:24,900 --> 00:22:30,525 So, if we take the same example here and we implement with load link and store 275 00:22:30,525 --> 00:22:36,079 conditional, we're going to look at the headpointer here where we normally do the 276 00:22:36,079 --> 00:22:40,101 update. And we're going to do a load into this 277 00:22:40,101 --> 00:22:44,040 register. And, 278 00:22:44,040 --> 00:22:48,665 when we go into a store conditional, if we, someone else had changed this value 279 00:22:48,665 --> 00:22:52,935 in the meantime, we're going to get a fail and we're going to jump back around 280 00:22:52,935 --> 00:22:58,955 and have to redo the load link. And this actually gets rid of the ABA 281 00:22:58,955 --> 00:23:04,184 problem, also. Because if you did have that sort of race, someone else would 282 00:23:04,184 --> 00:23:08,321 have done a store conditional to that address, and the wrap around cases and 283 00:23:08,321 --> 00:23:12,140 all that stuff would actually, and it would even validate your 284 00:23:12,140 --> 00:23:17,432 flag on that bit, if you will. We're flagging that memory address. 285 00:23:17,432 --> 00:23:23,222 One of the reasons that people like this is, when you go to do load link or load 286 00:23:23,222 --> 00:23:29,084 reserve in store conditional, you can, a lot of times sort of piggy back this over 287 00:23:29,084 --> 00:23:33,933 a memory coherence protocol. Such that, you do a load link and it will 288 00:23:33,933 --> 00:23:39,925 add an extra bit in your memory, we'll say. So, if you're doing some sort of 289 00:23:39,925 --> 00:23:44,809 memory coherence protocol, it'll pull it in your cache and you can sort of tag 290 00:23:44,809 --> 00:23:49,755 this little loop line as special, or that's the flag bit here effectively 291 00:23:49,755 --> 00:23:55,140 because this whole line was load linked. [COUGH] And then, 292 00:23:55,140 --> 00:23:59,085 if no one else pushes it out of your cache or fetches it from your cache in 293 00:23:59,085 --> 00:24:01,836 the meantime, so would mean no one else did a load link 294 00:24:01,836 --> 00:24:04,062 on it. By the time you go to do the store, you 295 00:24:04,062 --> 00:24:07,375 know that no one did anything. And what's really nice about this is 296 00:24:07,375 --> 00:24:11,083 there is no communication that has to happen between the processors on the 297 00:24:11,083 --> 00:24:14,990 common case with an uncontained lock. Versus the spin locks are, are generating 298 00:24:14,990 --> 00:24:18,204 memory traffic all the time. They are saying, they're doing loads, 299 00:24:18,204 --> 00:24:22,209 doing stores and trying to like grab the lock, trying to grab lock, trying to grab 300 00:24:22,209 --> 00:24:26,165 lock, trying to grab lock and they just generating all this traffic all over the 301 00:24:26,165 --> 00:24:29,720 place versus this is very quiet. You just pull in your local cash. 302 00:24:29,720 --> 00:24:34,450 And if by the time you get back to it, it was still in your cache and it still has 303 00:24:34,450 --> 00:24:36,706 it's bitset. That's great. 304 00:24:36,706 --> 00:24:40,204 You get to do it. In the contendant case though, you may 305 00:24:40,204 --> 00:24:45,420 actually get traffic ping ponging here, but you can still guarantee correctness. 306 00:24:47,960 --> 00:24:54,680 [SOUND] So, this brings us to performance. 307 00:24:56,020 --> 00:25:01,026 As I said, some of these blocking atomic operations can generate a lot of memory 308 00:25:01,026 --> 00:25:03,904 traffic. So, they'll say they're spinning on 309 00:25:03,904 --> 00:25:06,720 memory and they'll at least be doing lots of loads. 310 00:25:06,720 --> 00:25:11,420 [COUGH] And those lots of loads may be going out to main memory. 311 00:25:11,420 --> 00:25:15,777 Non-walking atomic operations, so like these compare and swamp operations or 312 00:25:15,777 --> 00:25:19,734 load link store conditional. And the load link store conditional, as I 313 00:25:19,734 --> 00:25:23,862 was alluding to many times you can, you can do it against your own cashe. 314 00:25:23,862 --> 00:25:28,507 also these, these things can have sometimes a better performance because 315 00:25:28,507 --> 00:25:31,890 you don't have to sit there sort of spinning in type loops. 316 00:25:31,890 --> 00:25:34,412 You can try to do stuff in, in the mean time. 317 00:25:34,412 --> 00:25:38,885 The down side to, at least the compare and swamp implementation is you have to 318 00:25:38,885 --> 00:25:43,472 sort of speculative work in the meantime. You're sitting there redoing some work 319 00:25:43,472 --> 00:25:48,650 and if you didn't get the lock, that performance can be bad. 320 00:25:48,650 --> 00:25:53,532 There's also, as I alluded to at the beginning of class, there are things that 321 00:25:53,532 --> 00:25:58,097 use ordinary loads and stores, or algorithms that do allow blocking with 322 00:25:58,097 --> 00:26:01,647 just loads and stores. Their performance is, is not, not very 323 00:26:01,647 --> 00:26:06,339 good and we're going to look at an example of that called Dekker's Algorithm 324 00:26:06,339 --> 00:26:10,560 today. Finally, 325 00:26:11,620 --> 00:26:17,878 the performance of these isn't just dependent on the operations themselves. 326 00:26:17,878 --> 00:26:22,520 So, of the, these primitives, harbor primitives, 327 00:26:23,600 --> 00:26:27,620 have better performance or worse performance depending on how highly they 328 00:26:27,620 --> 00:26:30,446 are contended. So, what I mean by contended is I mean 329 00:26:30,446 --> 00:26:34,250 you have multiple threads trying to acquire the lock at the same time. 330 00:26:34,250 --> 00:26:37,965 If you have lots of people trying to fight for the lock, that's high 331 00:26:37,965 --> 00:26:40,752 contention. If you have a lock which there's almost 332 00:26:40,752 --> 00:26:45,015 never contention on, you go to just go to get the lock and you just get it, and 333 00:26:45,015 --> 00:26:49,168 it's there for a really rare case. other locking primitives have better, 334 00:26:49,168 --> 00:26:52,610 better protocols there. And, of course, we're going to talk about 335 00:26:52,610 --> 00:26:56,599 this in a little bit of how do you make these integrate well with caches, 336 00:26:56,599 --> 00:26:59,660 out-of-order processors, and out-of-order memory systems.