The T2tile project is building an indefinitely scalable computational stack. Follow our progress here on T Tuesday updates. Our top stories this week, like every week in November, still doing NaNoRemo, the national novel writing month. It is now day 19. How do we know that? It's because November 19th. I committed to try to write a 50,000 word novel from scratch in the month of November. I'm not going to make 50,000 words almost surely. But I'm writing the best effort, titled Science Fiction Novels, best effort and it's, you know, every day. It's every day. So here's my current progress. The dotted line is what I would need to do if I was going to be hitting 50,000 words by the end of the month. I'm running about 10,000 words behind. But lately, I'm actually kind of, my slope is improving a little bit. There is a distressing horizontal line here. And in fact, let me see it down here, yeah. So I had been putting my, upload your word count to the NaNoRemo website and it keeps track of your statistics for you. I had much more detailed statistics on my own, but just at the end of each day, I was uploading my number to tell them about it. And so on the 14th day, I was actually kind of getting into it. I was actually kind of getting in a flow rather than just worrying about how many words I had as the day ran out at midnight. And I missed midnight by, you know, a half a minute. I don't know. The clock still said, clock said midnight, not 11.59. So the thing here is I have a tremendous number of words on the 16th and it gave me zero words on the 15th. So what, well, what it means is I have broken my streak. I would have been in line to get the 14 day in a row update badge instead, and I'm back at one day in a row. And so the 21 day in a row badge for NaNoRemo 2019 is now off the plate for Dave. I could still get the 14 by starting a new streak that lasts to the other one.   So that happened. But this is what my own internal graph looked like last week, curling off at around 12,000. This is what it looks like now. We're pushing 20,000 words someplace close to that. I've also added a linear regression that it turns out the new plot, the new plot can compute for me at least in later versions. I didn't know that. It was pretty nice. And that's actually the thing that's really driving me now, you know, am I above my regression line or below it? And so the thing to focus on is this period right here, you know, these two periods of, you know, pretty fast, you know, it was the flow, it was a scene that actually came out relatively easily again and then and then moan and groan and moan and groan and then kind of another scene that was working on today. And so forth. So we'll see again, the whole thing is taking so long that oh yeah, and so I'm at a thousand words a day, it's going up a little bit every time I have more time with the thing above the line, we'll see how it goes. If thousand words a day means 30,000 words in a month in November, that's a lot of words. The goal is to get to something that could somehow finish even if it ends just ends up just being like volume one or something like that, but to pull off an ending, we shall see. So right. And last week it was telling me I was going to be done on December 25th at this rate. This week it's telling me I'll be done on December 16th. That's progress. All right, so that's Nano Remo. What I thought I would do today since I don't have any real other work to talk about is follow up on something from the Gitter, the chat room. Last week I mentioned that Anton Mikhailov was was doing back on hacking the GPU, the graphics processing unit stuff to do this more modern version of the thing to get around the bug that he ran into and so forth. And he posted some pictures of his progress on that. So this was a picture of the initial state of a single cell seed that pops out to, well, I don't know if he's got a seed or not, but this thing has got one content in the middle, a ring about inner membrane, a ring about a membrane around that, which was then growing into this like brain or cauliflower thing because he'd only implemented some of the rules that the total C211 proto cell consists of a bunch of rules. I don't know how many 30, 40 I never actually counted that each do various little bits. And since each event just takes place in a tiny little event window on one of these things, each pattern is concerned with doing something reasonable to make this particular pattern better, make it more like we think it ought to be and so forth, which makes it really difficult to figure out how they're all going to interact once you have them there and they all start up. Now, you know, that could be a criticism of this kind of programming of this kind of spatial programming. But on the other hand, you know, the dirty secret of computer systems, information technology systems is, of course, they actually all their pieces that are supposedly modular, supposedly separate software, they all interact too. But they only interact through the system once you put it all together and that everybody's just pointing fingers at each other that, well, you didn't implement the interface correctly. Well, you didn't interface it, implement the spirit of the interface correctly. In the meantime, you know, the plane crashes or the thing doesn't run whatever it is. So with this approach, the explicitly spatial approach, you know, we're seeing the interactions immediately because we're engineering the interactions. We're asking how do we want to make it go to turn out the way that we're going to like it? And so having the ability, I mean, this was just sort of happening as a matter of experience. Here's a giant picture of the set of rules that Anton had gotten when he was first getting this stuff working. And Luke was coming in and saying, you know, this is really great. And in particular, thanks for showing these work in progress stages, you know, just the growing stuff without the shrinking stuff and so on.  It doesn't work in stages. You know, here's the particular file and so forth. Anton says, maybe once Dave is back, he can give us a tour of what makes it tick. Luke, don't tempt him and so forth. And so, okay, thank you guys. Yes, I thank you. Why am I not writing? Well, I'm not writing for another 10 minutes or eight minutes here because I'm talking to you guys. So, but this gave me an idea. And the idea was wouldn't it be good, just as a debugging thing, as an understanding thing and so forth, if in any SPLAT program, and now I haven't implemented this yet, but to just be able to turn on and off individual rules. So for like any rule in the whole thing, you could say, I want this rule to be enabled, I want this rule to be disabled, which would mean it's just as if that rule failed, even if it didn't, because we won't even do the match, or third case, have the whole thing fail at this point.  Like that. And so I could kind of simulate it by writing actual code. So that's what I did. And so this is Q mem brain dot SPLAT, which is the single file that has the most rules related to the C 211 digital proto cell, which we, you know, goes all the way back to 2017 now, I guess, in its earliest stages and so forth. That is, you know, sort of saying this is what a two dimensional digital cell, something, it's just a framework for holding stuff. Okay. And so each of these rules, I can't go through and explain each one because you actually have to read the code. I mean, these look like they're deceptively simple. So you think you ought to be able to read them off, but in fact, they're code and they're, they're code of a different style. So actually did I have, I had some, yeah, here we are. So here's a few thoughts about how to interpret the C 211 proto cell, what it's doing and how to think about it. So the first one to think about is we're not thinking about stages in time that first do this, then do this, then do this, which again, is much more typical of traditional programming where you have serial determinism step by step through time. Instead, we think in terms of forces, how do we want to push this thing? How do we want to let ourself be pushed on and let the system itself resolve the forces, however it will, and then we'll observe whether they do what we like. So once we say that we're focusing on the forces, then we're going to have to admit that the interactions between the forces matter. That's what I was talking about before. And the key to the C 211 is you look at it, you see the cell membrane, you say, oh, that's a bag containing some stuff. And that's probably not the best way to think about it. The way to think about it is you have some content that has this fence around it, it's not a wall, it's a fence in the sense of good fences making good neighbors. The membrane around it serves to tie up some space between this content and anything on the outer side that allows us to keep score, that this thing is inside, that thing is outside, and so forth. It is not actually in charge of holding the stuff in. In fact, it's the content that decides should we go left, should we go right, it's not the membrane around it that does anything. And the way the content, the way the membrane knows what to do is by estimating the density of the content inside. And so that's all right. So those are those are the general points. And so here are the rules that end up doing it. There's so, for example, here, a given a vote E is an empty means every time we see an E in a rule, we'll count one vote for E. And we can say if is the number of empties greater than, what is that, three halves, is it more than three, one and a half empties, something like that, the total number of sites, E will be true if the number of empties times three is greater than or equal to the number of sites times two. Yeah, okay. So we don't have to be all empty, but we need to have a preponderance of empty. So that check rule is a proxy for saying I think there's low density among the E's. So when we have a rule down here, whereas here's one right here, this is a really important one that says here's a bunch of E's on this side. There's a bunch of F's on the other side, which do a similar thing about measuring fullness. So if it's kind of low density on one side, kind of high density on the other side, that means we should move the membrane further away from the high density. And there's similar rules to say if there's low density on the inside, we should move it in.  Where are they? Here they are. Like P growth, okay, and so forth. So now we can turn on and off individual rules. So let's take a quick look at it before we run out of time here. So I'll make a seed. We'll get it going. And here are my parameters. Okay. So this is a typical thing. Everything is turned on and so forth. But now we can, like, suppose we turn off the grow rules, the rules that have the outer membrane get further away to make more room. Now, in fact, the density starts rising higher and higher and higher, and the thing gets all jammed up. Well, that actually makes sense. So we'll turn that off. What if we turn off the shrink rules that are controlling when the density is low and it wants to move in? Now, unfortunately, the way I implemented the Q membrane, it's got some rules in there which aren't sort of obviously shrink rules. In particular, there's rules that say, you know, every inner membrane should have an outer membrane next to it somewhere. That's part of the beauty of having a two layer membrane is that you get all of these local redundancies. Every outer membrane should have an inner membrane next to it somewhere and vice versa. And that allows us to thin out and simplify things just based on our local views of stuff. So the general shrink rules are actually needed to get those extra inner membrane to go away.  There's another one. So here it is, enable, and this was the rule I was just talking about. This is the rule that says every inner membrane needs an outer membrane next to it, and if an inner membrane finds itself without an outer membrane next to it, it'll actually go away. And we get the same kind of behavior where it starts crowding up. It happens more slowly, but it happens in the same way because all these guys in here, these inner membranes that do not see any outer membranes around them, we're just sitting there clogging it up. And this is an example of the way the forces interact with each other. Just because they don't clean themselves up, that means there isn't enough room for the content to move around. So the thing jams up and so forth. Once again, we turn the invariant rule back on and there we go. So that's not an actual explanation of the whole thing. We would have to actually go through blow by blow code review kind of stuff to make more sense out of it. But it's a little bit of the flavor that you're going to pick the forces that make sense that you can. And then you're going to add enough structured redundancy. I mean, you could have a membrane that was just one layer thick, but by having it two layers thick, you can tell which is inside and which is outside and do all of these invariant checking and testing locally. Okay. For what that's worth. The next update, there's still two more updates. No, one more update during nano-remo, but back in a week. Thanks for coming. Hope to see you next week.


You need a financial advisor with the freedom to focus on your specific needs. Whatever your goals, Reid Potter can create a game plan tailored to you. Call Reid at 432-0777 at Pikeville, Kentucky to learn more. As Eastern Kentucky continues the recovery process from the July 26 flooding, Knott County Sportsplex is continuing to offer food, shelter and water to displaced residents. Now we're kind of going into a recovery stage where we're trying to, you know, everybody's already got their necessities, almost everybody anyway. We have, I think, 30 people that are still in the shelters, about 30 in the shelters. We have 30 state campers at Carstork, no, 30 at MindMade, and 24 at Carstork. They're all filled up and we're hopefully, you know, we may get some more. The Sportsplex is only accepting donations of building materials as many residents are beginning home repairs. There is also a growing need for volunteers as many out-of-state organizations are beginning to leave. You know, it's really important to have quite a few volunteers.  You know, some people can run a forklift. We have a couple guys here, it's been really great. If you would like to volunteer or arrange a donation, call<PHONE_NUMBER>. For Mountain Top News, I'm Breanna Robinson.


All righty, welcome back to Operating Systems. So last lecture, we implemented the world's crappiest lock. Didn't really work. And it wasted a lot of time and resources. And today, we are going to create a better lock that does not suck. So you can actually implement good locks yourself in software with minimal hardware if you really want. So the bare minimum hardware requirements is that just loads and stores need to be atomic. And your CPU needs to execute instructions in order. And using just these primitives, there's two main algorithms you can use. There's like Peterson's algorithm, and then Lampard's bakery algorithm, where basically it simulates you going into a bakery, grabbing a number, and then calling numbers in order to implement a lock. The problem with these is that they're more computer sciency. They don't really scale that well. And any real hardware will not use these algorithms, or any real software will also not use these algorithms. So what is our atomic primitive we usually have on our CPUs in order to implement locks is something like this magical atomic function called compare and swap. So what it will do is it just wants a pointer to some location where an integer is, and then an old value for that integer, and then a new value for that integer. And then atomically what it will do is it will try to change the value pointed to by p here from old to new. And it will always give you the original value of the old value. So this will be atomic, and it will do the compare and swap for you all atomically. And you will know whether it changed from, in this case, a 0 to a 1 if it would turn 0. So here is our compare and swap. So what this will do, it's pointing to our lock, which is just a pointer to an integer. And the other arguments are saying if the value of that is currently 0, please change it to a 1. And then this function will always return 0 if it has successfully made that swap. Otherwise it will always return what the value of that memory location was before this function runs. So if compare and swap return 0 here, it means it successfully changed the 0 to a 1. If it returns just 1, it means the value was 1. And it didn't do the swap. So that is all atomic. And it will make sure that, hey, it atomically checks the value, and then we'll swap it if it matches. So any questions about compare and swap? So with that, we can actually implement a lock. So if we change our implementation to lock to this, well compare and swap, it will return 0 if it has successfully atomically changed that value from a 0 to a 1 to indicate that this thread has the lock, in which case it would return 0 and then break out of this while loop because that's the thread that changed it from 0 to 1. And one thread could pass this lock call. Now, while that value is 1, if another thread tries to call lock, it will do compare and swap at that memory location, and the current value is 1. So it will just get back a 1 and then it will loop here infinitely like we saw before. So in this case, we don't have any data races because this compare and swap is dynamic. So this is a correct but not efficient implementation of a lock. So everyone agree with that? Yeah. So it's not efficient because if one thread acquires a lock, so it changes the value from 0 to 1, and then another thread will just continuously read it over and over and over again, and just keep on trying even though the value we know isn't going to change. So that's why it's not efficient. But it works. So this is a implementation of a lock. This specific implementation is actually used and it's called a spin lock because of that while loop it will just try again and again and again and again and again. So again, any questions before we move on in this? This is a perfectly valid implementation of a lock. It just has a little bit of a deficit where it will just continuously retry over and over again. All right, we're good. So what that is is why I said before, it's essentially a spin lock. And that compare and swap is going to be on any modern CPU hardware, and that's the atomic primitive that everyone depends on. On x86, it's called comp exchange. Weird name, right? But we're bad at naming things. It's basically short for compare and exchange. Might be called that. Might be called compare and swap. They're essentially all doing the same things. Just how you use it might differ a bit. So we still have that busy weight problem for our lock, in which case one thread will just retry over and over and over again if another thread has a lock. So again, if we just have a single core CPU and you don't acquire the lock, if we were smart, we would just yield. So you hopefully have started implementing that in lab four or at least thinking about that. So we could just make this a bit better. And if we don't acquire the lock, the current value is one. We just yield and hopefully another thread can execute that will actually unlock that lock. If you have a multi-processor machine, it might be worthwhile to try again and again and again, depending on how long that other thread will acquire the lock for. So the longer it has the lock, the more time you're going to waste retrying it. But in some cases, it might only have it for a brief amount of time where trying it again and again and again might actually not be that bad. So here is our implementation that just adds a yield. So we just have wall compare and swap. So if it returns one, which means another thread has a lock, I wasn't able to change it from a zero to a one, I will just yield. But now we have another problem, isn't that funny? Every time we try and make something better, we introduce another problem. So our new problem is something called a thundering herd problem. What's that? Say we have eight threads and one thread successfully acquires the lock and then there are seven threads trying to get it after that thread unlocks it. Well, they'll just yield and whenever that first thread unlocks, seven are all going to try to acquire the lock when really only one's going to be able to get it. So why do I have all seven trying to fight for it at once? That's the thundering herd. So as soon as it's unlocked, there's seven immediately trying to unlock it. And also in this case, we don't have any fairness either. So as soon as that thread unlocks the lock, any of them could acquire it. We have no idea and ideally we would like to control it so that you're only waiting for the lock for a set amount of time. You wanna be able to reason about it. So this says, oh well, we should probably introduce a queue so that whenever a thread tries to acquire the lock, it will actually get it in the order it has stood in line for. So what we could do is just do a big code so I'll do this in pseudo code. So in the lock, if I fail the compare and swap, I will add myself to the queue to wait for a lock and then put myself to sleep.  And then in the unlock, whenever the one thread that has the lock calls unlock, it would just set its value to zero and then it would check. If there's any threads in the wait queue, well, I should just wake up whatever is at the front. So I should just wake up one thread and there are two issues with this implementation. One is called a lost wakeup and another one is very well-named. It's just called the wrong thread gets the lock. I don't have much of an imagination. So let's look at that code for a little bit and see if we can argue what conditions would cause something like a lost wakeup or what possible conditions could call or could cause the wrong thread to get the lock. So again, with this, it's essentially the same problem as a data race. So lost wakeup should mean that one thread puts itself to sleep and then it never wakes up. So it's essentially in a coma, which is not good. So let's have a look at that and try and devise a situation in which case one thread will essentially just be in a coma forever. Yep. So it would check if it's in the queue and it's not and the other thread is here. Yeah. All right. Everyone else get that? All right. Let's see that example real quick here. So do, do, do. So what could happen? Let's say thread one. So thread one has a lock. It was the thread that set it from zero to one. So it should be the one that calls unlock. So let's say thread one is going to call unlock, start here and then another thread called thread two is trying to acquire the lock. So what could happen is, let's start executing thread two. Thread two could do this compare and swap. It would see that the current value of the lock is one because thread one has the lock. So it would next want to execute this line and then before it executes that line, what might happen is we might context switch to thread one. Thread one would set the value of the lock to zero. Check if any threads are in the weight queue which currently there are none. And then, so if there's none, it would just go here because that condition's not true and then finish unlock. So now the lock is currently unlocked and if we context switch back to thread two, well it's going to add itself to the weight queue and then put itself to sleep. And now it will be a sleep. Thread one, which is what thread should have woken it up will now not wake it up. So everyone to get that, yep. Yeah, so if say another thread thread three comes in, whoops. So if thread three comes in, it might acquire the lock and then unlock and then it would wake it up. But if you have a giant queue, just one of the wakeups would be lost. There would always be one sleeping. But in this condition, yeah, we could clear it up if just a new thread just did a lock and an unlock.  All right, any other questions about that? So that's the lost wakeup. All right, what about a situation in that the wrong thread will get the lock? So here as a preamble to this, let's assume that thread one has the lock and then thread two is in the, so let's assume thread one has the lock then thread two is in the wake queue. So it should be the next one to acquire the lock. Then say we also have a new thread called thread three. So is there a situation that thread three will acquire the lock before thread two? Yep, everyone agree with that? Got thumbs up, so let's just go over it real quick. So if thread one has the lock, that means the value of the lock is equal to one. So what could happen is thread one starts executing unlock. It changes the value from one to zero and then it gets context switched right there. So now that the value of this lock has now changed to zero and then we might context switch directly to thread three which starts executing this lock call. In this case, well, it would check, compare and swap. The current value is zero, so it would just change it from a zero to a one and now it got the lock. So it just kind of whoop, it just came right in there, stole the lock from thread two. So everyone see how that happened? All right, not good. So now we have to fix those problems. So yeah, here's the last wake up example. So you have it and also the wrong thread getting the lock, although I just named the threads differently. I swapped thread one and thread two, but same difference as long as you're consistent, it doesn't matter. So here's how we fix it. This looks a bit ugly, but essentially all it is, here, let us swap back to this. So this looks a bit ugly, but what we are doing here is we are implementing our mutex. So let's see. So our mutex here is going to hold a bunch of things so that will hold our queue of threads that are waiting for a lock. This is the lock that is external, that all the threads should be using to make sure that there is only one. And then we are adding a new field called a guard. So this guard will be a spin lock that we only internally use to prevent data races in these lock and unlock calls. So this guard variable is used here, so an easier way to read this is that whole line I highlighted there. Well, that is actually equivalent to just locking the guard. And then if I go through, so whenever I set the guard to zero after I do a compare and swap to it, well, if we remember, that's the equivalent of just doing an unlock to the guard. So if we do that, it's kind of like just an internal mutex that we're using to implement lock and prevent data races. So we will lock the guard. Therefore, no other thread can interrupt us because we're in a critical section. Then we will check the value, the current value of the lock. We don't have to use compare and swap in this case internally because while we already acquired the guard lock, so we have mutual exclusion. We have no data races because only one thread can start executing this at a time. So we can check the current value of the lock here. If it is currently zero, we don't need compare and swap, we will just swap it ourselves. So we change it from a zero to a one. We know that we now have the mutex, so we can just return from this function, make sure we unlock the guard so that another thread can call this, and then we carry on. Otherwise, if we cannot acquire the lock, what we will do is we will put ourselves into the waiting queue and we won't have any problems with data races because we have that guard lock. Then we can unlock it and then put ourselves to sleep and that will just wait for something else to wake you up. Now in the unlock, we have the same thing. So we'll use that guard again to prevent data races. So here it's the equivalent of lock guard. And then at the end there, this setting it to zero is the equivalent of locking the guard or unlocking the guard, sorry. So first thing, if a thread wants to unlock, it will get the guard so that we don't have any data races with the queue. So now it will check if the queue is currently empty. If it is empty, I'm good. I can just set the lock from one to zero and that's it, the lock is now free for other threads that might wake up. Otherwise, if there is a thread in the queue, I don't have to, I can just transfer the lock to it. So I don't change the value, so the value of the lock is still one. All I do is wake up that thread and when that one thread wakes up, it will resume from the sleep and then just exit out and then continue with the lock, make it past the lock call and now it has the lock. So any questions about that or any potential issues we see here? Yeah, so this solves our problem. So that one case where we had another thread come in and swoop the lock, well, let's see what happens now. So let's say thread one has the lock. What did we say before? Thread one has the lock and then yeah, thread two is in the queue and then thread three starts. Right, that was our sequence we had before. So what was our problem before? Well, if we immediately started thread one and then change the value to zero and then some other thread swooped in, right? So now if we start executing thread one, while currently the value of the guard is zero because no one has it, so it would essentially acquire the guard spin lock here and then start executing this, right? So as soon as it makes it pass that, it acquires the guard spin lock. Say thread three started to execute. If thread three started to execute, it's essentially at that lock for the guard so it's not gonna pass. There's no way for it to pass and kind of swoop the lock. So because of this thread one has to continue in order to make progress. Here it would check the queue and then oh, okay, there's something in the queue so it would transfer, it would wake up thread two and thread two would get the lock because it was waiting in line. There's no possible way for thread three to swoop in and take it, right? All right, yep, yeah, does everyone see there's still a very slight issue? So there is a situation in that, let's see. Yeah, let's have the same case. So thread one goes here, wakes up the next thread, which is thread two, thread two acquires it and let's see what would happen in the case we get super unlucky. So thread three is trying to acquire the lock. Let's say currently some other thread has the lock so it can pass the guard. Okay, we don't want that highlight to follow us. So it can pass the guard. It would check the current value of the lock if another thread has a lock while the current value is one, so it would put itself in the queue and then do the unlock and then it could get interrupted here right before it puts itself to sleep. So let's say that it's the only thing in the queue right now, whoops. So in our queue, we have thread three and it is currently not yet asleep but it has added itself to the queue. Well, if thread one comes in and thread one tries to call unlock, well, it can currently get the guard because thread three has let it go and added itself to the queue. So it would be able to make thread one can make progress, can you stop it? Stop it. So thread one can make progress and then here, well, oh no, it could check if the queue is empty, it's not, here it would try and wake up a thread but it is currently not asleep. So that is a slight issue. So luckily this is the only kind of data race there is, it's already added on the queue so because it is on the queue and not yet asleep, you know that the next thing it is going to do is put itself to sleep. So easy solution to this is just retry it. So you could just yield yourself, add a bit more code here, yield yourself until you can successfully wake up that thread because you know it's about to go to sleep or you could devise a way to cancel it's sleep or do something else but it is a situation that we can handle. So any questions about that? Because that is the trickiest thing. So that's a mutex, that is the correct implementation of a mutex that works well. So it doesn't have the thundering herd problem, it doesn't have any lost wakeups and it doesn't have the wrong thread stealing the lock. We have solved all of our problems so everyone agree we have solved all our problems? Life is good? All right, life is pretty good, great. So here's what I was saying before that there is still a data race. Oh, question doesn't fail because I don't like the screen. Okay, that doesn't help. So yeah, the one we saw before is failing because of bad context switch and where it didn't get placed in the queue. So in the full implementation that we saw previously so here it is again. There was still a data race where a thread unlocks the guard and gets interrupted right before it puts itself to sleep after it adds it to the queue but we know that that thread is about to put itself to sleep so we could just retry it. So through all this remember what causes the data race because you will have to identify and fix any data races in your program as long as you have multiple threads. So say it again because it's really important. So data race, two concurrent actions, at least one of them is a right. So if we wanted to optimize ourselves for performance well we might notice that we can have as many readers as we want. So as long as each thread is just reading we can have all the readers we want in the world. So it may be the case where your program does a lot of reads and then writes are infrequent in which case you would want to kind of maximize apparelism. So if you want there is another type of lock that has different lock modes depending on whether or not you are reading or writing the variable. So they're very creatively called read write locks. So with mutexes or spin locks they don't care they just make that critical section limited to one thread executing at a time but we want reads to happen in parallel. So how that works is there's this P thread read write lock and then you can lock for reading or you could lock for writing. So how that works is it will allow as many readers as you want and it will also guarantee that when some thread acquires the write lock there is no threads with the read lock and there is only one thread with the write lock and that will happen. So you'll either be at the situation where a bunch of threads have the read lock which is perfectly safe or only one thread will have the write lock in which case you will not have a data race because you essentially just disabled concurrency. So how that looks is it looks pretty similar. So it uses that guard and the two lock implementations are just going to do something different based off whether or not you try to lock it for reading or writing. So if you try to lock it for writing it just functions like our lock we saw previously just our normal mutex it would just try and acquire it and then at the end it would just unlock it. The only difference is for the readers. So for the reader we first lock the guard because internally we are keeping track of the number of readers that are sharing the lock. So there's a plus plus reader here to keep track of the number of readers. So we saw before if we don't have a lock around it while then we have our data races it's like that count example we saw at the very beginning of like lecture 16 or whatever it was. So if we now increment the number of readers and we see that we are the first reader that means we have to acquire this mutex that we are sharing with the writer. So if we acquire it then we have the lock a writer is not possible to it's not possible for the writer to get the lock and then we will unlock the guard because the guard is just protecting this number of readers variable. So the nice thing about this is if we have another reader come in while it could get the guard increase the number of readers from one to two and just keep on going. So it just allows as many readers as you want could share hundreds of readers thousands of readers as many as you want they're all sharing that lock. The only difference is that in the unlock while it will try to acquire the guard lock decrement the number of readers and then there's an if here. So if you are the last reader then you are responsible for unlocking the mutex. So it's like that same I guess this is like the weird bathroom example. So the first person in has to get the key go in the bathroom and then as many people can pile in as you want and the only rule is the last person that leaves has to lock the door. So any questions about this? It'll what sorry. No, so if another thread say some thread has the lock for writing so it would have this internal lock here right. So if we have a reader it would get the guard no problem increase the number of readers from zero to one and then it would reach this lock call so it won't be able to pass until the writer unlocks it right. Because it's the only one at this point that could unlock it. So you're either in the case where there's only one writer or there's a bunch of readers. You can't have a mix of both otherwise you would have data races right because data races concurrent accesses with the least one of them being a right. All right, we're good. We're all experts now. All right, so that's wow that was faster than I expected so we have additional time for lab four stuff if you want to ask me anything. So let's wrap up. So we, what? Oh, okay, so we want critical sections to protect against data races so that's anything between the lock and the unlock. So we should know what data races are to concurrent accesses at least one of them is a right. Also spoiler alert, you have data races in your lab four even if you don't know it yet. So I wrote an additional like common issues because I guarantee that you will have that issue because I had that issue and I thought my implementation was working but it wasn't. So if I had that issue, likely you have that issue. So, but for the purposes of locking so mutexes or spin locks are the most straightforward locks just ensure mutual exclusion. Mutexes have a queue associated with them bit of extra work. Sometimes if things are, if the critical section is small enough you might want something like a spin lock for performance reasons because while they're really, really simple and they essentially pull really, really fast so as soon as it gets unlocked you will acquire it. If you want to implement locks in the real world you need some hardware support so you need that compare and swap atomic instruction. Remember atomic is the important word there otherwise it would have a data race we need to either happen all at once or not. And if you implement mutexes you need some kernel support for waking up threads and putting them to sleep. You could have implemented that and if you really want to you can implement thread sleep and wake up in lab four, up to you. I took that out but if you wanna put it back in that's up to you. And there is also a special type of lock called a read write lock that will share the lock between as many readers as you want and then will only allow a single writer. So for some programs, for performance reasons if you know you have a lot of readers you should probably use that lock. So with that just remember pulling for you we're all in this together.