Hey guys, this is Dr. Ahmed Ergin. Today we are going to do something really interesting and scary. My heart rate is already up and I didn't think that it was going to be like like that nerve wrecking and but what I'm trying to do today is I'm going to give myself insulin. I am going to drop my blood sugars. I had, don't worry about it, I have, I have a nurse by me. Something happens. She's gonna intervene if I pass out or anything like that. She's gonna give me the glucagon. You found my responsive, which by the way, every diabetic on insulin should have this glucagon. This is a new glucagon ready to go called GVAC. I am not diabetic. My goal is not go down to 10. By the time I'm down to 7 or 60, I will start feeling it and my goal is to go below 50 and I want to feel what my patients feel when they go low and now I understand how my patients feel when I tell them that I'm going to put you on insulin. I can feel the fear that they're going through. That's real and I am going to give that shot to myself and I'm going to put myself to hypoglycemia, which is low blood sugar. I always teach them how it feels and how to fix it and let's see if I can take it. I'm going to do that and today my other goal in addition to putting myself into low blood sugar situation and feeling it, I also want to test continuous glucose monitoring systems in the market. So Freestyle Libre, Dexcom G6, and Guardian from Metronik. These are the three leading brands and I want to see in a real life situation with the real low blood sugar if they're accurate because that's what I prescribe for my patients and I want to know which one works best. I am going to do a finger stick of course from a quality brand that I know is very reliable and of course you can tell by my symptoms. I'm going to start feeling sweaty, shaky, heart racing and I'll probably lose my collar. I may feel dizzy. So I decided to use Fiasp. So Fiasp is the fastest acting insulin analogue right now or for the among the short acting insulin. So I decided to use this because guess what I'm not going to wait another two three hours for my blood sugar to drop. I'm going to be really generous with this insulin. So let's do the priming first. Okay two units did work but I'm going to a little more okay just to make sure.  All right I'm gonna okay wow that's going to be big. It's going to be 30 units. Now don't do that at home guys especially if you're diabetic you know you know I'm healthy that's why my body is trying to fight it but this 30 units I think we'll bring it down. Okay let's go. Alrighty okay so that's gonna oh yeah oh what I like about this Fiasp the push that plunger is so easy compared to himalogue and let's see if it is as fast as they say the studies say that it starts in in two minutes to act and it peaks relatively faster but uh we'll see guys. Okay so my blood sugar right now on the Libre is 94 and on the Dexcom is 110 and on the Guardian it is 118. Again Freestyle Libre 2 is reading everything considerably lower compared to other CGMs. Good thing or a bad thing we'll see but I think in the you know if you remember it gave me a couple false alarms false low alarms we'll see how that's gonna go this time and I'm hoping that I'm gonna really go low and we'll see which one picks up faster I'll keep you posted I'll keep you updated in a second. I think Fiasp is working faster so it's been 40 minutes and I already got a low alert from this guy from Freestyle Libre. Yeah let's see scan it scan it okay oh it says 56 I can't believe it's 56 I don't feel like 56 I'm sorry Freestyle that's cannot be true because I don't even feel it as a healthy individual if it was 56 I would be like perspiring right now now Guardian showed that you're not low but it's predicted so you're going low and as you can see here it says 76 and there's one arrow down it shows me that I'm going down now super fast but I'm going down one arrow down which means that you know right around one to two milligram per deciliter in 30 minutes that's gonna be 30 to 50 lower than this 76 so if it goes like this that's how you interpret this you may be down to at least 46 within 30 minutes now that's not good so if you were to have bad if you should do something about this right so let's let's look at the dexcom of course let's look at what the dexcom says here dexcom says it's 95 and it is stable not so sure about that I used to really love dexcom and people love dexcom but I'm surprised that dexcom didn't pick up on that that my blood sugar is actually going low now I also feel like a little butterfly healing like a little bit of anxiety feeling and I think that's my contrary hormones are kicking in right now and I want to see what my finger stick shows I think that's probably we'll see which one is the closest um that's the whole point of doing this experiments today all right so I'm excited let's see what it shows oh wow it is 60 guys can't believe it it is 60 uh well here's the deal guys I'm gonna give some credit to freestyle libero 2 because this says 55 and this says 60 which means that I'm low maybe because I'm normally running around 90 60 may not be a big difference I mean a lot of people if they are going from 200 down to 90 they're gonna feel it you know your body read your body doesn't understand numbers your body knows a difference so um but that's good fias put me down in 40 minutes I like that so it's gonna actually peak around an hour so I'm hoping to go really really low uh and I'll see if dexcom picks up on this uh I'm hoping that it will because if it doesn't it will be a big disappointment so we'll see what it how it goes I'll keep you posted okay guys I start feeling funny so uh dexcom is picked up right after I uh it was 110 and after that it went down to 82 and it's showing the arrow as you can see it's not totally down but it's showing oblique um which shows you you know pretty much the same thing as one arrow down with the metronik um so what I feel right now is um it's kind of funny it's kind of a funny feeling it's kind of a panic feeling you know that I don't know when the rush that comes to you that's how you feel um and let's see what that is right now it says 53 I think that's a little exaggerated I don't think I'm 53 um I'm gonna do another finger stick just to see yeah I feel uh busy it says 43 okay well am I 43 I know I feel busy I feel like the lights are are kind of too shiny a little too bright uh it says 43 here on the meter and it says 52 on the librae 2 librae 2 this is the new librae dexcom says it's 82 and according to guardian it is 63 and going down so I think um I feel low right now and I'm sure I'm below at least 70 and dexcom shows that it's 82 right now and it's going down um it's predicted that according to dexcom and I would be low down to below 60 in the next 20 minutes according to this and let's see if I have any hand shaking a little bit a little bit my heart rate yeah it's up let's have let's find out what it is according to this my heart rate is 116 124 yeah I feel the shaking I guess gonna go lower we'll see let's see how low I will go before I pass out that is the deal and if I pass out uh I have the guca going here I chose g-vote because I don't have to you know reconstitute the whole thing and I can inject to myself uh so that's the beauty of it because if you're down to 77 on dexcom and I think dexcom is probably closest to how I feel and I think the librae 2 let's see what it is it's 51 and I think a little over exaggerated um it's predicting low which is good but I think it is um predicting a little too low let's see what the guardian shows according to guardian I'm down to 58 and maybe it's true I don't know maybe it's true uh dexcom shows that I'm 77 still it checks it every five minutes of this shows now the freestyle librae 2 it says 50 and I'm going down so we'll see what happens when I'm down to 40 the point that I'm trying to make here number one is I'm trying to feel how you guys feel and number two um although as I said you know I may not feel exactly how you feel but at least I want to understand um how a nasty feeling is the the bottom line is it's a horrible feeling uh no matter what you feel it doesn't feel good when you choose a meter and then I told you about the guardian right guardian shows I'm gonna give you my final comments on this um it says 59 on on the uh on the guardian metroni and I'm gonna do this one more time I think it's gonna come around the same probably older remember blood sugar drops faster than your inserthitial fluid all the time so um monitoring your blood sugar in a situation like this is your best bet I'm back up to 71 once it's almost midnight till 2345 and uh gee I was like getting into bed and I felt like something weird and like something in my chest feeling like anxiety my I'm feeling extremely tired and weak I was like oh that was a long day I know that but then I uh start feeling hot and I'm like oh god let me check my blood sugar and then it was like below 60 I just had some food uh and it's like trying to come up but uh that was the guardian that I just showed you here uh well vexcom shows 71 as it's again dragging their feet trying to trying to come up I want to see what my finger stick is yeah 67 so it's coming up um but I I think when I felt it was below 60 so another lesson so if you had a low check your blood sugar again uh after you fix it with simple sugars not with chocolate not with uh candy bars like uh sneakers and stuff but I would go with the finger stick as close as the truth 67 vexcom says 72 pretty close the guardian says 61 is more dramatic I don't know if that's correct or not but the bottom line I think I went down to at least 60 maybe 50 um and freestyle libre was the first one to pick up on that uh but I didn't even feel that I was low uh so if you are concerned and if you want to know and never want to go low maybe freestyle libre is the way to go uh if you want to know that you're going low um but you know you don't want to be all ordered all the time or or you know 70 60 blood sugar is not only that dangerous you don't want to know that you're you're you're getting false alerts for example when it's when it's in reality 70 for example this now says 74 on dexcom um but you know with um with the guardian for example it said 60 the dexcom says you're right around 70 the finger stick showed 71 dexcom shows 74 maybe dexcom maybe your choice if you for example the really do not want to get too many false alarms and get like if you get an alarm that's just pretty much real uh so I think they made the freestyle libre and guardian a little too sensitive um the problem with the guardian you still have to do you still have to do two finger sticks to calibrate and if you don't calibrate it just quits on you and that's the problem and you still have to do finger sticks with guardian now of course another big competitor to dexcom is freestyle libre 2 which is new uh doesn't have an app yet that's a problem um but they have this and I've measured on this according to this I mean it's uh it picks up low sugar I think it gives too many false alerts but I think sort of overall still a good product if if your budget allows this and if your insurance covers this whatever uh it is still a good product if you want to pump definitely go for dexcom um but if you are just wanting to monitor your blood sugars and you know you just want to know that you're not going to danger zone uh you want to keep your blood sugars about 100 um then that's maybe then freestyle libre maybe your choice um but again I think overall um dexcom has the best features right now um and I think it is still a very accurate uh better little false alarms if you get a low blood sugar alerts that's going to be a real low uh so I hope that video helps guys and uh again make sure that you leave comments uh we want to hear from you as well uh and we will uh talk to you and see you in the next video


End of the week. So we're going to hopefully finish up our synchronization primitives and synchronization problems week this week, which will allow us to move on to thread scheduling and maybe even get into some memory management next week. So it's a little bit of a thin crowd this morning. This is about that time in the semester, I guess. Friday at 9 starts to become a little bit of a heavier lift. OK, so today we're going to talk a little bit about one of the problems you can run into using locks, which is deadlock. And then we're going to walk through two other synchronization primitives. And I've changed the flow a little bit this year so that we'll look at each primitive and then we'll do an example. So we're going to look at condition variables, which are quite useful, something that you guys will want to use for assignment 2 and probably for assignment 3 as well. And then we'll talk a little bit about semaphors, which are probably the least useful primitive of the ones that you guys are, well, I guess you're not asked to implement, but of the ones that are implemented or will be implemented on your system. But there are some cases where semaphors are useful. And then we'll talk just a couple sides about more general advice about how to choose the right primitive for you or probably more accurately for the problem you're trying to solve. All right, so assignment 1 grading should work. Again, if you guys submit patches that you think should apply and they don't or things that you think should work and don't, please let us know and we'll look at it. I think what's up there works. But who knows? There's always a possibility that there's something broken. And if I was you and I was taking this class and nobody had forced me to complete things by any particular point in time, but I was still hoping to be able to complete things by the one point in time where you do have to complete things, I would probably be working on assignment 1 at this point and hoping to wrap that up next week so I can get on to assignment 2. So if how many people are working on assignment 1? How many people have submitted a patch for assignment 1? I have. Mine worked. OK, so yeah, let's get to that point that that part is open so you guys should be able to. And look, again, you can submit that as many times as you want. I'm not encouraging you guys to bang against it, to do incremental grading. But if you guys have a lock implementation you think works, run the lock test. I mean, our testing doesn't do anything that you can't do yourself. In fact, it does exactly the same things that you would do yourself.  So it shouldn't be a big surprise when you submit things. Again, we're not doing anything that you can't do locally. So do some testing first, but please get on to starting assignment 1. All right, any questions on last time? So last time we looked at two different ways to implement locks. We looked at spin locks, which are busy waiting, which involve busy waiting and force threads to wait actively until some condition changes. And then we also looked at sleep locks, which are, in many cases, a more efficient solution that allow threads to sleep and wait to be awakened. So any questions about that material before we do a very brief review? Any questions? OK. So spinning is almost never a good idea on a Kevin. What kind of machine would I never want to spin on, or almost never want to spin on? Sure. Frank, can you help him out? Yeah, on a single processor system, because frequently the thing I'm waiting for is for some other thread to finish. And if I am holding the CPU, I'm preventing that thread from finishing what it's doing. So the longer I sleep, the longer I will have to wait. And when I'm designing which synchronization primitive to use, whether to wait actively or wait passively, what might I want to consider about the length of the critical section? Honorar. Yeah, so if the critical section is short, then I might spin. It's still some other cases where I wouldn't want to spin. But if the critical section is short, I might want to spin. And if I know the critical section is long, then I probably definitely want to sleep. OK? Why? And what's kind of like a constant here that creates this design decision? What's the thing? What's the overhead I'm worried about, Andrew? Yeah, see, he's smart. He's got slides from last year or notes or something open. The answer is all right. If the critical section is short, then the context which overhead waste cycles, because I switched off the CPU, something else has to run, the scheduler runs, and very quickly into that process, whatever I was waiting for became available, and I could have continued. What's the interface to a lock? Wembley, you're way in the back today. Boy, my mind a little bit. Sorry, what's the interface to a lock? What are the functions that I used to? What's one of them? Test and set? Well, that's the interface to a test and set. Manish? Yeah, acquire and release. Grab the lock. I lock the resource when I begin using it or at the top of a critical section, and then I unlock the resource when I complete using it. And what's one very common use of locks, which I just slipped up and set? Robert, what specific resource? A critical section. A critical section, a portion of code that I do not want more than one thread executing. And I use a lock, and I acquire the lock at the top and I drop it at the bottom. All right, any other questions about this before we continue on? Questions about locks? Let's start playing the jeopardy theme music during these awkward pauses. OK, so frequently what's going to happen, and this is a question that kind of dovetails when I say with Brian's question last time about lock granularity. So locks protect access to these shared resources, but frequently in order to perform some useful function on your system, a thread will have to access multiple shared resources. And those shared resources may each have their own lock. And at this point, I can run into problems. So whenever I start using multiple locks, you have to be aware of the classic lock problem. So consider these two threads, A and B, that they both need access to shared resources, one and two, that are both protected by a lock. So thread A runs first. It grabs the lock for resource one. Now I have a contact switch. Thread B runs. Do you like that? It's like, whoo. There should be a big graphic. Boom. So thread B runs, grabs the lock for resource two. So now what's going to happen? Contact switch. What happens next?  Yeah, thread A runs, tries to acquire the lock for resource two. And here I'm still OK except for what's going to happen next shot. Thread A is going to sleep, right? Because thread B has the lock for resource two. So thread has to wait for it. And again, I'm OK here, but you can tell right on the edge of the cliff because what's about to happen, Sarah? Yep. Thread A and thread B are both now sleeping. And they may be the only threads on the system, in which case nothing will ever happen again. And yeah, in some cases, nothing. And in fact, I hope in recitation next week, Aditya will show you how to use. There's a tool called stat161 that you can hook up to your running kernel. And it's a nice tool for identifying deadlocks because in certain cases, if your system is sitting there not doing anything and you're trying to figure out, is it not responding? Is it not like painting? Is it actually trying to finish something? Or is it just waiting for nothing to happen, right? And you can use stat161 to demonstrate the fact that your system is in fact sitting there doing nothing, which usually means that all of your threads are sleeping waiting for something that's never going to happen because the thing they're waiting for is asleep, right? So this is this classic condition which is called deadlock. So deadlock occurs when a thread or a set of threads are waiting for each other to finish, and thus nobody ever does. So deadlock always involves some kind of circularity, right? And that circularity can be quite tight, right? Very small. So how can a single thread deadlock? Sam, I mean, in that case, it would probably just wait and assuming that resource is held by somebody else, it would eventually run. Sirach, how could this happen? A single thread deadlocks. I mean, this isn't a trick question. You guys will wonder why this happens, and we'll talk about that in a second.  That will deadlock, right? So this is called self-deadlock. Thread A acquires a resource, and then thread A acquires, tries to reacquire the resource. But why would this happen?  Why would I ever have a piece of code that said acquire lock a, and then the next line said acquire lock a? How would this happen, Spencer? Is this something that's super easy to fix? Like, oh, duh. It was like those bugs where you get where it's like you had a null pointer exception, and you went and found it, and it was like, dereference null, right? So is this this easy to fix, you think, all the time? You're going to say no, it's a good answer. So what could happen here that would cause this that would make it very difficult to find? Or why does this happen at all? Sean, I'm going to argue that this can happen even if the save and restore state's correct. So you're saying there's the correctest problem in the kernel, and I'm going to say even if there isn't a correctest problem in the kernel, this can happen. Yeah, right? Was it down you have to apply it? You're getting closer. Yeah, assume it. Well, again, I would say that would be a programming error. Don't acquire a lock in a loop, unless the loop is for i equals 0, i less than 0, then you're OK. Less than or equal to 0, AJ. Yeah, so again, this seems to be an aim. But think about what happens here.  So you acquire a lock. So foo, foo locks resource 1. And then it calls bar. But foo doesn't know what bar does. Your partner wrote bar. Your partner said, hey, I wrote this great function bar. I don't know what it does. Ghost of the bar, maybe. But anyway, so that's a good function. Maybe that's what your partner is doing too much of. So yeah, and he said, you can use this when you need to do this thing. He said, great, OK, so I'm writing foo, and I need to do the thing that bar does, and I call bar. But it turns out that bar, what does bar do? Bar tries to acquire the lock for resource 1, right? Whoops, right? And this is really complicated. I mean, if you look at real operating system kernels, they're like, I don't know. I shouldn't know the answer to this question. Probably hundreds of thousands of lines of code that are being simultaneously developed by potentially hundreds if not thousands of people. So you're not always going to know, and you're not supposed to know what certain functions do or how they do it. You're just supposed to be able to call them and rely on the interface guarantees to make your life easier as a program. Now, there is a solution to this. Not everybody loves this solution or endorses it. So there is this idea of a recursive lock. And these are a primitive that are offered by most modern kernels. And essentially, what recursive locks do is they just keep a recursion count on the lock, so the lock can be acquired multiple times. To release the lock, what do you have to do then? Let's say I have a lock where I can call lock a choir, lock a choir, lock a choir, and I just keep going if I can tell that the thread has already locked the resource. What do I have to do with the release calls? Tom? Yeah, I have to pair the releases with the choirs. So if I had a recursive lock that, as soon as I called release, it just released the whole lock, then I'd be very sad because I'd be popping up the call stack and the thread at the top would think that it held the lock, but the thread at the bottom released it. So when I write recursive locks in order to get them correct, I need to pair calls to a choir and release, but you can do this. And you may want to implement recursive locks. I at least found one place in your code base where David Holland has a mean and an unpleasant comment about recursive locks. So he may or may not like them, right? But you may or may not decide that they were a good idea. So you can implement these if you would like. I just want to make one thing clear here. Don't change the semantics of the locks that we gave you. Those are not recursive locks. If you want to write recursive locks, write them as a separate set of problems. Okay, so in order for there to be a deadlock on the system, there are a series of conditions that have to be met. And the reason why we discuss this is because preventing deadlock means making sure that one of these conditions is not true. So all of these conditions have to be true, and if you want to prevent deadlock, you need to relax or remove one of these conditions, right? So first of all, you have to have protective access to shared resources. This is pretty basic, right? That implies waiting, right? So threads don't go to sleep ever, then you can't have deadlock, okay? That's kind of obvious. No resource preemption, which means that the system doesn't have a mechanism for taking resources away from threads that already hold. So once a thread has a resource, the kernel or the system that's providing the lock primitive doesn't have a good way to like rip it out of its hands and give it to somebody else, right? Multiple independent requests, which means that I can acquire some subset of the available resources on the system. So when we looked at things before, the thread A and thread B were both requesting resource one and resource two independently, okay? If I had to request them together, then I wouldn't have had the problem that I ran into, okay? And finally, and this is one of the things that's frequently used, so these top three are, I would say the least common ways to remove deadlock conditions, right? The circular dependency graph is the most common way of avoiding deadlock, right? This is the most common way of getting yourself out of a deadlock situation because most of the time you want these top three things.  Like once a thread has a lock, like what do I do to get it away? And how do I let it know that I took the lock away from you, sorry, you know? So these things are usually kind of difficult to do but the circular dependency graph is one of the things that you can usually do, right? But a circular dependency graph means that when I look at the resources that are trying to be acquired and the threads that are trying to acquire them, there's a circularity that I can identify, right? In the self-deadlock case, again, that circularity is on the same thread, right? Normally on your system you'll see deadlocks occurring between multiple threads, right? So and it'll be like what we showed you before where thread one had resource A, wanted resource B, thread two had resource B, wanted resource A, right? So I have a circle there with two nodes, okay? So here's the classic dining philosopher synchronization problem that is, which I feel obligated to discuss, I don't know why, it's not such a bad problem. If anybody can identify any of these philosophers, extra credit, I'm not even sure, I know who they are. Well, I think I know who two of them are. Well, maybe three, maybe only two. Okay, so I have a series of philosophers that have sat down at dinner together and each to their left and right is a single chopstick. Apparently, this table was not set by the crew from Downton Abbey and because there isn't enough silverware here, right? But anyway, so and as they start to eat, what they happen is that they each first pick up the chopstick or the dining utensil to their left, right? And, but once they do this, what happens? So now they're gonna try to get their other chopstick, right? Because they need two chopsticks.  Maybe they'll put them in the same hand, I don't know whatever. But so what do I have here, right? What is this condition, right? Everyone has one chopstick, right? Can anybody make forward progress? This is a deadlock, right? So I have a deadlock and I have a circular dependency graph that just kind of winds its way around the table, right? This guy has this resource, wants this resource.  In this case, I have five different threads or philosophers that have caused a deadlock, okay? And so again, we can talk about how to address this deadlock and any deadlock by relaxing one of those four requirements, right? Relaxing or eliminating one of the four conditions that are requirements for deadlock, right? So, oops, I didn't wanna go back to this again. Okay, so the first one is that there's protected access to shared resources that involves waiting, okay? So for example, if I had a way so that if I couldn't get the second chopstick, I would just put down the first chopstick. I wouldn't wait for the second chopstick, I would just drop the first one, right? So if I had a way to do this, right? Then this problem would solve itself, right? Because somebody would realize that they couldn't get the second chopstick, drop the first chopstick and that would break the cycle, right? And then somebody would get two and a couple of people would end up with two and a couple of people would end up with one. But the problem is that when you look at the semantics of the locks on your system, for example, lock acquires sleeps if it can't acquire the resource. There's no option not to sleep, right? Like you are going to be put to sleep and woken up when the resource becomes available, right? So again, this requires some change to the semantics of locks as they're usually implemented, right? So this might require a new primitive, right?  I can request both chopsticks at once, right? I could have some and it wouldn't necessarily mean that I would have to have a lock for each pair of chopsticks, right? It could just mean that there was some, you know, there's some lock acquire call on my system that tries to lock both locks, right? And does it return unless it can lock both locks, right? And that would be kind of interesting to see if you can implement something like that. But again, this is a new mechanism, right? We don't have that, right? Our lock acquire locks one lock, okay? So again, this is the most common way of getting out of deadlock, right? Is to break cycles. And the normal way that we break cycles is we impose some kind of ordering on the requests, okay? That ordering can be entirely arbitrary, but there has to be a well-defined order for a set of locks. If you have an ordering for a set of locks in which those locks are always acquired, you cannot deadlock, right? Because you cannot have a circular graph, right? So for example, if I numbered the chopsticks zero through four, right? And I always grabbed the higher numbered chopstick first then this case wouldn't deadlock. And I'll go back and show you this on the picture in a second, right? And then the final way is to figure out a way to detect deadlock and essentially take a resource away from a thread, right? So the system had a way of identifying that there was this deadlock condition that we had just seen. And it essentially went to like Isaac Newton. It was like, boom, I'm taking your chopstick. That would also work, right? So let's look at each one of these, right? So at least a couple of them. Where did my philosophers go? Yeah, there, okay. So here's where we got to, right? Okay, so again, there's a couple of options here. One option is I can take, you know, I can take somebody discard and I can go whack, right? I could just take his chopstick away and I could give it to Isaac Newton and then essentially some of these other things would also fall down, right? So that's one way of getting out of this cycle, right? Another way to do this would be to number the chopsticks, right? So if I numbered these chopsticks zero through four, and my rule was that I always grab the higher numbered chopstick first, then what's gonna happen is that there, or somebody, sorry, I always grab chopsticks in the order of their numbers, right? So I always start at the higher number and then go to lower number. What's gonna happen is that one of these guys is not going to grab the same chopstick as everybody else. Four people will grab the chopstick on their left. One guy will grab the chopstick on his right, okay? And that will break me out of this cycle. Let me see if I can describe how this would work, right? So this is zero, one, two, three, four, okay? So this guy has chopsticks, so this guy is the one who's gonna help us, right? Because he has chopsticks zero and four, right? Everybody else is gonna grab the same chopstick. This guy has one zero, this guy has two one, this guy is three two, this guy is four three, right? So all four of these guys, I wish I knew this guy's name, he's got great hair. But all these guys are gonna grab the same chopstick, okay? This guy has chopsticks zero and four, right? He is going to try to grab this chopstick first, okay? And depending on who wins between him and this other guy's name, I don't know, who has big hair or hair so dark it blends in with the background of the painting. One of them will win and get this chopstick, right? And the other one will fail and not have a chopstick and then several other people will be able to acquire the chopsticks they want, right? So this is the one guy at the table, right? Who will no longer be grabbing the chopstick on his left. So this ordering has got us out of this circular dependency graph, right? And a deadlock will not occur. There is a problem on assignment one that is suspiciously similar to this problem. It has a little bit more subtlety to it, but there's a similarly good solution in terms of establishing a consistent order and always locking in that order, okay? Any questions about this example? All right, good. So there's another problem with synchronization permitism. This is something else that we ask you guys to address and we're gonna look at for assignment one, which is called starvation. So in starvation what happens is that there are, so deadlock is a condition where a number of threads can get to a point where nobody is able to make progress, right? Starvation is a case where some threads can be prevented from making progress for an arbitrary long period of time if certain conditions are true, okay? So in a starvation case, some threads are making progress. Other threads are not. And particularly when you guys are designing your reader-writer locks, you should be careful to make sure that starvation can't happen, because reader-writer locks are a classic case where it's very easy to starve one class of requests, right? Normally with reader-writer locks, if they're not implemented carefully, it's very easy to starve writers, because writers require exclusive access to the resource and if I have a steady stream of readers that are coming in and reading, the writer may never get access, okay? Now of course by never, I just mean for an unbounded period of time, right? But the point is there shouldn't be a case where I can create a series of requests that would cause some threads to not make progress for an potentially unbounded period of time, right? You know, again, at the limit, the system shuts off, right? So something is gonna stop happening and that one writer who's been waiting for weeks will finally get a chance to write, right? But that's not acceptable in our normal definition of what starvation is, right? So it's not forever, but just needs for some unbounded period of time, okay? So we talked last time a little bit about race conditions. We talked a little bit about Monday about race conditions, cases where I have problems with correctness, okay? So race conditions are on one end of my spectrum where I don't have enough synchronization to produce a correct solution. Now I've come to the other limit where potentially if I start throwing locks all over my system, right? Locking everything that could potentially be a shared resource and even things that don't need to be locked, I might have these deadlock conditions that start to occur. So let me ask you as a programmer, what would you prefer? Nick, race conditions or deadlock? Why? What's true about a deadlock compared with the race condition? I think Nick got onto it, but not strongly as I wanted. Okay, so, right, so deadlocks, and what does that mean about a deadlock? What's, so let me just give the answer away. What's easier to detect? A deadlock, because the system stops running, right? With a race condition, you might have some weird thing that happens where some data gets corrupted and eventually normally in the kernel race conditions lead to some kind of fatal error, right? But that error might occur much later. And it might take you a while, so this will be devil you guys for assignment two and assignment three because you'll have cases where you have not synchronized things properly and stuff will just go wrong, right? Like weird things will happen, right? You'll run a user program that's supposed to be binCP and it'll have some pages in it from bincat, right?  It's gonna just do something dumb, right? And you'll be scratching your head like what is happening here, right? Where it was with a, I don't know, what did you get when you made CP and cat? I don't know, like CP that spits out output as it's copying, I don't know, whatever. So anyway, the point is that what happens is that something wrong will happen but then it's gonna be quite difficult to trace back whereas as soon as you have a deadlock, right? You know that something bad happened, right? You can see the systems in doing anything. Potentially, you have state about the threads that have deadlocked. You might, on modern systems, with good deadlock detection you might have, you know, exactly what resources they were trying to acquire, right? So, you know, you don't necessarily know exactly how they got there and it might be tricky to figure out what happened but the system is kind of frozen in the state where the problem happened as opposed to a race condition where something doesn't end up calculated correctly but the system just goes on and blunders on until something weird happens, right? So I'll take the deadlock over the race but I'll leave this up to you guys to decide. All right, so so far we've talked primarily about locks, okay, and locks are largely designed to protect critical sections and other pieces of shared state. Locks have, and I mentioned this a little bit on Wednesday too, I mean, locks in some ways have their own explicit, bluh, not explicit, implicit communication built in, right? So lock release can be thought of as a signal, to some degree, a certain kind of signal from a thread that it's done using a resource and that resource is now available or it exited the critical section and another thread can now enter, okay? And in order to receive the signal, the thread has to be sleeping, right? So a thread has to have tried to acquire the lock and release can be thought of as a signal from the thread that has released the resource to the ones that are waiting on it, right? Remember when we talked about synchronization parameters, we said we had two goals. One was to enable correctness and locks are a tool for doing that but another goal was to enable communication and there are other types of signals that I might want to deliver between threads that are coordinating access to the same resource, right? So here are some examples. There's a buffer that has data in it now, right? Maybe that data came from a network socket or a file but maybe there's some other threads on the system that are responsible for doing something with the data once the data is in the buffer, okay? Or your child has exited, right? My parent called wait and it blocked and the child kept running and then at some point later the child exits and the colonel wants a way of telling the thread that the parent process that was waiting to receive the child's exit code, hey, your child exited and you can continue, okay? So we refer to a certain type of signaling mechanism within the colonel and this is one that you guys will get to implement is a condition variable, okay? And a condition variable, when I started using condition variables I probably spent five years before I really thought about what it meant like what, because sometimes we call them CVs, right? Which is probably not a good thing to do, right?  It is not, on the other hand, condition variables maybe have a confusing name because a condition variable is not a variable, right? It is a signaling mechanism that is designed to allow threads to safely communicate when certain changes to a variable have occurred, right? So conditions involving this variable, right? So CV weight is, so this is part of the condition variable interface. CV weight is a call that allows me to wait until a condition is true, right? And CV weight is usually used in a block of code that tests the condition to ensure it is true. And then there's usually a call called CV notify that is used to alert other threads that the condition is true, okay? And the condition, again, is usually represented as some change to shared state that's significant to certain threads, right? So the buffer has data in it, which I can measure by having a variable called buff size is greater than zero, then some threads that are waiting for data in the buffer are able to run, right? So when those threads are going to CV weight until the buff size is greater than zero and threads that put things into the buffer are gonna call CV notify to let those threads know that there is data in the buffer, right? There's also a third part of the CV interface which is called CV signal, right? Wait, sorry. Oh, well, so there are three calls to the CV interface, which waits for the condition to become true, there's a notify or broadcast mechanism that alerts every thread that's waiting and then there's usually a way to alert only one thread, right? So when the condition changes, the thread that has changed the condition has the choice of waking up everybody who's waiting or waking up one thread, right? And this can be used in certain cases as an optimization mechanism, right? If I know, for example, that I don't need to wake up everybody because only one person's going to be able to get access to the resource then it might be safe to only wake up one thread, right? So we'll look at an example of this, okay? So again, CV condition variables represent and are used to convey more information than locks, right? Locks are just locked unlocked, right? They can't represent more complex state, right? Whereas condition variables are used to represent state that usually can be in two, three and different states, right? And where threads want to know when certain things have changed, right? So again, a buffer can be full, it can be empty or it can just have data in it, right? If the buffer is full, then certain threads may want to know that because they can't do certain things. If the buffer is empty, certain threads may want to know that because they can't do certain things. And if the buffer has some data in it, then maybe everybody can make progress, right? Right, exactly. So this is what I just said. Sometimes I feel like I'm reading the slide's mind. All right, so, okay. So here's the example we're going to work through, right? This is a classic example using CVs. It's the bounded buffer producer-consumer problem. I have a buffer of data that contains a certain number of data items. It's a fixed-size buffer. And I have threads that are withdrawing and inserting items into that buffer, okay? Clearly I can't withdraw an item if the buffer is empty. Clearly I can't insert an item if the buffer is full, right? So I have two different types of threads, three different states, right? This is, again, what I just said, right? So whenever you guys start working on a synchronization problem like that, it's like this, particularly if you're using condition variables, it's a good idea to write down what the conditions are that you're tracking, right? So in this case, we're tracking the state of the buffer. And we have these three states, full, empty, or in between, right? And here are some invariants that we want to make sure are true, right? So if the buffer is full, the producers cannot put more items into it, right? So producers must sleep if the buffer is full. Consumers must sleep if the buffer is empty because they can't withdraw items, okay? The final two things that we also need to think about, right? This is kind of like designing recursive base cases or something like that. So if there is room in the buffer, producers should not be sleeping, right? And if there is data in the buffer, consumers should not be sleeping. So this is a condition that we want, okay? So here's our example. I have this produce function. I have this consume function. We assume that producer threads run produce, consume threads run consume, okay? And at some point, the producer thread is just going to put the item into the buffer and the consume thread is going to get the item from the buffer. There's other code in here, clearly, right? But let's think about how we're gonna design it. So the first question I have to ask is, we're gonna have, we look back there and there's probably what we're gonna end up having, right? Is some, maybe it comes up pretty quickly, right? Account, right? How many items are in the buffer, right? This count allows me to test what state the buffer is in. If the count is zero, the buffer is empty. If the count is equal to the buffer size, it's full. And if it's not one of those cases, then it's in between, right? What is true about this global count? What's that? Well, is it going to be atomic yet? I mean, I like that as an aspirational goal, right? So why would I want this to be atomic? Bart, who is gonna be modifying this variable? When does the count go up and when does it go down? So will this variable be modified by multiple threads? Potentially at the same time. Okay, and what does that mean? If I have a piece of shared state potentially modified by multiple threads, I need to make sure those modifications, they're safe by doing what? What other synchronization primitive do I need here, Tom? I need a lock, right? This is shared state. It's a shared state that's accessed by multiple threads. And this is an important thing to note with conditioned variables, right? A conditioned variable, and in fact, on your system, a conditioned variable requires that you pass it a lock, right? Because a conditioned variable is always associated with a conditioned, right? Expressed by a variable, which is shared state, and that condition is always protected by a lock, okay? Yeah, so yeah, it will be, but the conditioned variable we're gonna use the CV interface, right? So the conditioned variable is itself shared state, but that's okay, right? This, on the other hand, is not explicitly synchronized, right? So this is just a piece, if I had both people changing this, right?  They're not, right? They're not necessarily atomic operations. So we have to lock this count, okay? So CVs are always associated with that condition, that condition is always shared, that condition is always protected by a lock, right? So CVs are always associated with the lock, right? You can have multiple conditioned variables associated with the same lock, right? So multiple conditioned variables indicating different things about a single condition, but there is always at least one lock associated with the conditioned variable, okay? So I don't even know if I have the lock in here. I've stalked about it so much, maybe I forgot to put it up, right? Okay, so my producer, right? Essentially, again, what I said is, when the count, when the buffer is full, the producer cannot continue, right? So what is the producer going to do? What does the producer have to do if the count is full? But what was my requirement? If the producer, if the count is full, the producer should do what? I hear muttering, but no answers. For real? It has to wait, okay? Now, after the producer puts an item into the buffer, it's gonna bump the count, right? So this is still just kind of the control flow here, right? The consumer starts to look very similar, right? So when the buffer is empty, the consumer is going to wait. Once the consumer is able to make through, it's going to decrement the count, right? So this is, you know, again, without any synchronization, right? This is basically the solution to this problem, right? Now let's look at how we protect the shared state and use condition variables to enable communication between these threads, right? Actually, sorry, when I used these originally, I was setting this up as a way to use condition variables, but clearly we're using condition variables, that's what we've been talking about, okay? All right. So let's rewrite this using condition variables. So this is the basic control flow we want, right? But we have a couple of requirements, right? First of all, we need to protect the count. Protect this house, protect this count, right? Secondly, we need to enable communication between the producer and consumer. So the consumer, now, see, the consumer knows when to wait, but the consumer doesn't know when to stop waiting or when to wake up, right? When the condition has changed in a way that's significant for it, right? Same thing for the producer. The producer knows when to wait, but it doesn't know when to wake up, okay? So I'm gonna add my condition variable, right? That's associated with this count. And remember, for every condition variable, I have a lock, right? This lock exists to protect the count. So if I have a lock for the count, where do I need to lock here? Where are places where I'm going to need to lock around the count? I have a count, right? It's shared state. I have this lock that's associated with it. Where do I need to acquire and release the lock? Bethany, give me one place. There's like four. Yeah, so whenever I change the count, I definitely have to lock around it, right? So I have a plus plus here, okay? And I have a minus minus here. So I need to make sure that when I adjust the count, I'm holding the lock, right? So that those adjustments are safe. Jeremy, yeah. Yeah, and whenever I read the count, right? So again, remember I had this requirement that said, I don't want the consumer to be sleeping if there are items in the buffer, right? If I didn't protect the count, here's what could happen, right? Let's say the count is zero. Consumer comes in here. It checks that the count is zero. Then it's going to sleep, right? But let's say that right after it checks that the count is zero, the producer runs and puts an item into the buffer, right? It runs all the way through, bumps the count, but I'm already going to sleep, right? Now the consumer is asleep, but there's an item in the buffer, right? So this is the type of thing that can happen if I don't lock around the count, right? You need to make sure that access to the count is atomic, okay? So I definitely need to acquire it, oh, okay, so I definitely need to acquire it before I check, right? And here's how I use CV weight, right? So this is the classic design pattern for using CV weight, okay? What's CV weight? Oh, whoa, whoa, whoa, whoa, come back. I didn't want to do that, I want to do this, okay? So CV weight, and this is the semantics that are used by your system, right? Takes the condition variable to weight on, and it takes a lock associated with the condition that I'm checking. CV weight will check that I hold the lock and blow up if I don't. So if I call CV weight and I don't hold the lock so that I pass in, CV weight should die, right? Because that's a programming error. What CV weight will do is it will sleep on the condition variable and drop the lock, right? So when I call CV weight, two things happen kind of simultaneously, right? The first one is I drop count lock. The second thing is I sleep on the condition variable, okay? When CV weight returns, I hold the lock. So the idea is that CV weight drops the lock before it sleeps so other things can happen, right? But when I wake up, I grab the lock again, okay? So the idea is every time I come through this condition, I hold the lock, right? And as soon as I exit this, I still hold the lock, okay? So CV weight, you can think of as not altering the fact that you hold the lock. When CV weight returns, you still have the lock so it's safe to check the condition, okay? And what I do here is that I just sit in this loop, right? Because it's possible in the scenario we're about to describe that, so here's a good question. Why do I need to check the count every time, right? Why not just have if count equals full, CV weight? And then I just keep going, right? Why would I need to check the count every time? That's on a high level that is true, right? Because there's multiple threads going on. But what's like an example of a case where I might wake up but then I might check the count and it might still be full, amen? Well, so we haven't looked at where we're gonna put in the calls to CV signal yet, right? But here's a case where this could happen, right? So let's say there's, the buffer is full, okay? But there's five producers that are waiting. And let's say one consumer comes through and takes one item out of the buffer. And potentially all five consumers, sorry, all five producers now wake up. But how many of them are gonna get to put an item in the buffer? One, right? And for the other four, they're gonna check the count again and it's gonna be full, they're gonna go back to sleep, right? So almost always when you see condition variables used, they're used in a loop like this, right? That checks the condition every time I come out of a loop, right? Okay. So I know I need to release the lock, so let's put in the calls to lock release, right? So, and this is essentially almost close to correct, right? So I grab the lock, I wait till the buffer, I wait while the buffer is full. Now when I exit this loop, I know that the count is not equal to full so I can put in my item, bump the count and release the lock, right? The consumer ends up looking very similar, right? I acquire the lock, I wait while the count is zero and after I deck the count, I drop the lock. So this looks good. Does this work? Any one adventure, I guess? What's usually the answer when I ask that question, Dan? No, I gotta start messing with you guys more. No, this is perfect, this is exact. Right, so what's missing here? Tim, I have calls to wait.  Like this guy runs through and decks the count and the producer's still waiting, right? So I need to put in calls to CV signal or CV broadcast in here somewhere, right? But where am I gonna do that? Where is the right place to call CV signal or CV broadcast, yeah, Brian? Well, okay, so actually that's a, so I don't wanna go down that path. I have one CV here, right? I could have two CVs. I could have one producers and one for consumers, right? But I don't, I only have one condition variable, right? So you're right that the producers need to notify consumers or consumers need to notify producers. But it turns out that that ends up looking very similar in this particular example, right? So essentially both threads need to have some call to CV broadcast here, right? So now the, so again, the calls to broadcast are supposed to be where the condition changes, right? And so I change the condition here and I change the condition here, right? Or I change the count. See, this is interesting, right? And then I call CV broadcast, right? So this example works. I'm not lying, right? But does it work well? Masakaze, what do you think? So this example will run and it is safe, right? This example will work properly, but what's a problem with it? This is where we'll end today. Yeah, so what have, okay, so that's a good question. What happens if there's a context which between my put and changing the count? Is that, is this safe in this particular example? Yeah, so whatever thread is doing the put or get still has the lock, right? So it turns out in this particular example that the lock that I'm acquiring is not just protecting the count. It's also protecting the buffer, right? So once I grab the lock, nobody else can make a change to the buffer, right? So the idea is that these two lines of code, this whole thing is now a critical section, right? Both of them are, right? So these two lines of code and these two lines of code cannot be executed, cannot be interleaved, right? That's a good question, right? But what's another problem with this fruit? Yeah, yep? So CV weight will not return until it can get the lock, right? So CV weight will grab the lock and if it has to wait for the lock, it waits for the lock, right? It's a good question, okay? So remember we talked about the count is representing a condition, right? But that condition had three states, right? The states were full, empty, and in between. So if I increment or decrement the count, am I necessarily changing the state of the buffer? Yes or no? No, because if I'm in between, let's say the buffer has four items in it and the buffer has a size of eight and I bump the count. I haven't changed the buffer from full to empty or from full to neither, from neither empty, right? I haven't made a change in the state, right? So what's gonna happen here is that if I broadcast every time I change the count, right? So let's say that the buffer is in this in between state, I'm calling broadcast every time, right? That's not necessarily a potential problem because again, I will call broadcast when I need to, but what are the cases when I need to call broadcast? There are two cases where I need to call broadcast, smoke down, what's one of them? Well, when it goes from neither to full, sorry, when it goes from full to other and from empty to other, right? So a better way to do this is the following, right? So when I'm the producer, the only time I call broadcast is if I just put the first item into the buffer, right? Because in this case, the consumer should wake up, right? If I'm the consumer, the only time I call broadcast is if I've just consumed the, I've just created the first empty space in the buffer, right? Because that's when the producer should wake up, right? So this is a better way of writing this example. Yeah, Dan, you have to hold it. It's just a CV broadcast and CV signal will just check to make sure you hold the lock, right? But you're right, they don't manipulate the lock at all. So they don't necessarily have to hold. No, so the idea with, this is a good question, right? So the idea with CV broadcast is that it's a programming error to call it if you don't hold the lock, right? Remember, both threads that call CV broadcast here hold the lock because when CV wait returned, they had the lock, right? And they haven't released it yet. So if I put the release up here and the reason for this, right? Why, so this is a good question, right? And Dan's raised a good point. Why would CV broadcast and CV signal check to make sure I hold the lock? Let's say I didn't hold the lock and I called CV broadcast or CV signal, right? This CV broadcast or CV signal are supposed to express the fact that I know something about the condition of the variable, right? I know that it's in a certain state and I want to tell people about it. But if I don't hold the lock, what's wrong with that, what's wrong with that claim? Yeah, I'm, yeah, the condition might have changed, right? The thing that's preventing the condition changing when I call CV broadcast is I hold the lock, right? If I drop the lock, let's say I put the lock release up here, right, okay, and then I called CV broadcast. The problem is that other threads could have run in there and so my version of the count may not be right. So the idea with CV broadcast is that I have to hold the lock because the holding the lock is what's supposed to be preventing that condition from changing, right? And if I don't hold the lock, then I really don't know anything about the condition, right, as soon as I drop the lock here, I don't know necessarily what count is, right? Okay, good, so we will, I will see you back on Monday and we'll talk a little bit about semaphores.


Hey, it's Monday and it's 2020, so that means another week Working from home, I guess But we're getting used to it now, aren't we? I want to to use this video a couple of minutes to Talk about some some of the positive aspects of remote work Now for me the way a work week would usually start I'm a public speaker so that meant an alarm early, I mean really early in the morning to To get to the airport before rush hour I Used to fly more than a pilot the way you know that is They send you this Secret level above the frequent flyer card We are the ones with these cool black luggage tags. This is the sign of pleasure and Guilt Well, I guess I won't be getting these much longer now These days a Monday morning typically starts With an hour of trail running or so and then on to a long slow breakfast So for someone like me cutting away That chunk all that travel means oceans of time for whatever I want And of course, this is good. This is good for my health For my carbon footprint. I'm many reasons Then after breakfast, I'm usually here in my office Or these days we refer to it as the home studio. There are cameras and cables and Text stuff everywhere. So I can't even find my desk anymore But this is where I work. I do recordings meetings presentations live streams It's it's amazing when you think about it I mean I can broadcast live from home to an unlimited number of people anywhere in the world That was just impossible and 10 15 years ago to do something like this. You needed a broadcasting studio Satellite equipment hundreds of thousands of dollars in a budget It's kind of funny because last year if you follow me, you know that One year ago that that's one year BC as we say I recorded this a job is only a what What do I do and more importantly? What do I do to get paid? My answer to that is that I am a speaker I stand in front of people and I talk to bring your food for thought to challenge them and inspire them That's what I do for money But as you know, you need to start from the opposite direction You need to start with a why if you're not familiar with this Check out the link down below and listen to Simon Sinek in his world famous speech about how to start with why and why? That is important to you or read his book My why is to help people embrace change and then how I do that and What I get paid to do have changed many times throughout my life and career and will continue to change Just like any other job. Maybe I can meet more people like you now here online And then I don't need to travel as much anymore and maybe in the future I will be referred to as a youtuber rather than a speaker. Who knows Here we are And with all that money now pouring into streaming companies we can expect these Services all the platforms to become much better in the coming years I fully expect the option for virtual reality meetings in just two years time so that we can all have the experience of Being together in the same physical space even though we're not and of course this will set a new standard I mean sure We are social animals, so we will meet again I even believe the business conferences and the whole meeting industry will set new record highs by the end of next year Think of it two years of social distancing That means that everyone will try to grab the opportunity as soon as possible to host the best social gathering But that's also a new standard our expectations and our demands for In real life meetings means the bar is up here You don't ask me to do it old style like Like I told you the alarm at five in the morning and the hassle and the cost of traveling and Staying away from home from family for something we could have done In the virtual world just as well. That's just not going to be acceptable anymore The days of traveling to hear someone just read a PowerPoint are finally over Great events. However, great experiences created to connect social gatherings that makes Everything we do online easier just because we already Connected so we know each other these events These are the ones we will we will all look forward to just like a cool vacation plan or something like this That will be the new standard 21st century events that will be part of the reason we work so hard Another way of thinking about this trend or remote work is Is to think about what it might mean for us in the long term? Society how will this impact society and I don't mean like real estate prices when corporate offices can be smaller or any other Like industry trend. I mean for real. How do we live our lives today? And how will that change? think of Transformation like from farmers to industrial workers if we Again if we are in this transformation now from office workers to Out-of-office workers wouldn't that mean that you can now climb that career ladder by spending a Lot of time somewhere else you don't necessarily need to be in the office Maybe this is a great opportunity for us to raise gender Imbalance the fact that that no one now have to choose between work at home or away from home When you think of it still today in 2020 so many women had to make that choice between a professional life and a family life But if we can all work from home and Managers instead have to start to learn how to measure employees by by results and contributions rather than from how many Hours they spend in the office, then maybe no one have to make that choice anymore Well, like always the future is not to be predicted. It is to be created. These are just opportunities I mentioned the two two new opportunities a booming event the industry for the ones who Create awesome social gatherings aimed at connection and a new manual for managers To to learn how to evaluate employees who aren't in the office and Someone out there right now will spot these opportunities and act to create a future success story It's Monday, and it's 2020 I'll see you in the future and Hey, hey, hey if you want more videos Hit that like button and make sure to subscribe