Module 4, Threads in Go. Topic 3.1, Once Synchronization. So, we've been talking about Goroutines and we're going to talk about some of the features of the sync package. So sync packages gives you a set of methods that we can use to do synchronization between different Goroutines and here's another useful idiom that people form a lot, is initialization. So, say you've got some multithreaded i.e. multigo routine program running and you need to perform some initialization task. Now, by definition initialization is something that should happen once, happen only one time and it has to happen before everything else happens. It should be the first thing, it's initial. So sometimes that's a little bit hard to guarantee when you have multithreaded, when you have lots of Goroutines that are running in parallel because you don't know in exactly which order they're going to execute. So which Goroutine should you put the initialization in because you can't guarantee the order of execution of these multiple Goroutines? So, how do you do initialization guaranteeing that there's some initialization function that happens one time, happens before everything else happens, how do you guarantee that when you have multiple Goroutines? Well, one way is to actually perform initialization before starting the Goroutine. So maybe you can do your initialization inside the main, which will be the first Goroutine. You can do at the beginning and only then create the Goroutines. But sometimes you may or may not have that option. So, another facility that allows you to do this as part of the sync package is sinc.once. So this once method, once object, it has this method do. One method do, and you pass it some function as an argument. So, you can see there once.Do(f), whatever that function f is, and you can put this, called once.do in lots of different Goroutines, and this function f though will only be executed one time. So, the Goroutine guarantees that even if this once that Do is called in 20 different Goroutines, only one of them will actually execute, and it also guarantees that all calls to once.do inside any Goroutine, they block until the first one, the one that executes actually returns. So that makes sure that the initialization execute first before anything else can proceed. So you can put this once.do at the beginning of all your Goroutines, let's say. One of them will actually execute and the other ones will block until it finishes executing. So sync.once using once.do, it allows you to guarantee that first, initialization happens only one time because only one of these once.do's is actually going to execute. Also, it ensures that initialization happens before everything else because all the other once.do calls will block until the first one actually returns. So, this sync.once is useful when you need to do initialization and you have multiple Goroutines executed. So let's show an example of where we might use that. So let's say we've got two Goroutines and we're going to start two Goroutines in addition to the main Goroutine. We're going to start two Goroutines and we want them to do some initialization process, initialization function and do it only once. So, each Goroutine is going to be associated with this code dostuff so if you look at the main right there. I have go dostuff twice. So I'm starting two different Goroutines and both are running dostuff, whatever that is and I'll show that in the next slide. Also just notice, we've done this before, but notice that I put the wait group. So, I create a weight group at the top and then I call wg.Add(2) to say I'm going to wait for two functions, wait to two Goroutines rather, and then I call wg.Wait at the end. This is to make sure that the main Goroutine waits until these two sub-Goroutines actually complete. Otherwise, the main Goroutine will just exit before the dostuff actually gets to do anything. So, that's not the point of this, but I just want to mention that so you understand the code. All right. So, we've got these two Goroutines that are going to dostuff, and one of them is going to have to do initialization. We need initialization done at the beginning of the stuff that's going to be done. So let's go to the next slide. So now, first you can see on this slide a few things. First the top, we're defining our sync.once object, var on sync.once, ON I called it called it, call it whatever you want. Then I define this function called setup. So this function called setup is what I want to execute once, think of this as my initialization. Now this could be whatever I want it to be. In this case, I just had it print init just to do something. But you can have any sort of initialization operations in there that you want. So setup is a function that we want to have happen once. Now func dostuff down below is what's being executed by each one of the Goroutines. So, you can look at each Goroutine, look at dostuff. First thing it does is it calls on.do setup. Then it says print hello. So, we should see "Hello" printed twice on the screen at some point because there are two Goroutines. And then it calls wg.done just to let the wait group know that this Goroutine is finished doing what it's doing. So, now notice that both of these Goroutines are executing the same code, dostuff. So both these Goroutines have this on.do calling setup at the beginning of them. But what's going to happen is that only one of those is actually going to execute, not both those Goroutines are going to execute, only one is going to execute. So, when we execute the code, we get this appearing on the screen. You get Init first because that's the result of setup, setup prints Init. So that's the initialization process and I noticed that that happens first which is what we expected. Then "Hello, hello" you get twice because both of the Goroutines do execute both. Excuse me for the capitalization on one of the hellos, but both of them execute and they both print "Hello." So, this works. So Init appears once. Init appears before "Hello" so the initialization is done before any of the other stuff in the Goroutines are actually executed, which is what we want of an initialization. Thank you. Module 4: Threads in Go. Topic 3.2: Deadlock. So right now what we're going to talk about are problems that come with synchronization. So, we've been talking about synchronization, synchronization facilities provided in the sync package, also even outside the sync package with channels too. They also provide synchronization. But this synchronization, you get into problems with synchronization if you're not careful, specifically deadlock. So, this is something that you have to avoid when you're coding. You don't want to basically build deadlock in your system. So deadlock comes from synchronization dependencies. So, what I mean by that is, you can have multiple Goroutines and synchronization can cause one Goroutine's execution to depend on the other. So as example here, we've got G1, G2, these two Goroutines, and let's start look at the top row. So I got in G1, there's a channel CH and G1 is writing the number one onto the channel. Now, on the other side on G2, G2 is reading from that channel. Is taking CH, reading something from it, assigning it to x. So, there is a dependency here because G1 is writing onto the channel and G2 is reading from the channel. So that's the dependency and it's a blocking dependency in the sense that G1- It writes to the channel, but G2 can't continue pass that line, that read line until G1 does the write because since it has to read from the channel, it's going to wait right there until G1 actually does the write. So, there's dependency G2 depends on G1, it's execution depends on G1. Also, this data dependency here too, data is been passed from G1 and G2 also, but we're less interested in that in terms of deadlock. But we're more worried about the execution dependency. G1's execution cannot continue until G1 executes a statement. You can see the same thing on the bottom, and this time, instead of using channels, were using mutexes. So say I've got a mutex object. In G1 It unlocks that mutex, and G2 locks it. So, in this case, again, you can get a dependency because G2 can't accept the lock until G1 unlocks. G2 can't care to get the lock until G1 unlocks. So G2 again, its execution is dependent on G1. G2 can't continue past that lock until G1 gives up the lock. So, in both cases, you get G2's execution depending on G1's execution. So, G2 can't continue until G1 does something. So, four in one case, it's writing into a channel, the other case is it's unlocking a mutex, but either way. So, the synchronization causes the dependencies, the blocking dependencies. Now, when you can get into a problem, when you get into deadlock is when the dependencies are circular. So, what I mean by circular is if G1 is waiting for G2, and G2 is waiting for G1. So, G1 is waiting for G2 to do something like unlock a mutex or something like that, and maybe G2 is waiting for G1 to write onto a channel, and they're both waiting for each other to do something, but they're both blocked. So, neither one of them can progress, and that's called deadlock, nothing can happen at that point. So, it can be caused by waiting on channels, it can also be caused by mutex, waiting on mutexes too, waiting for unlocking of mutex, but it can also be caused by on waiting on channels too. So, this type of circular dependency where G1 waits for G2 and G2 waits for G1, that's what you need to avoid in your code. So, this is up to the programmer to avoid making such dependencies. So, let's show an example of a dependency like that. So, we're going to make a couple of goroutines in the main. I'm not showing you main right now. Right now I'm showing you dostuff, this is the code that each goroutine is going to execute. They're both going to execute same code. This dostuff, it takes two channels, channel one C1 and C2. Two channels as input and dostuff. First thing it does is it waits to receive something on the first channel, on C1, and then, it writes a one on the second channel. So, that's all it does. It waits to receive something on the first channel, and it writes to the second channel. Both of these goroutines are going to do the same thing. Now, they're going to have different arguments as I'll show you in a second, but that's basically what they're going to do, wait on the first channel, write to the second channel. So now, in the main, this is the main, I'll make two channels CH1, CH2. They have integers, then I have the weight groups, so we don't have to worry about that, but the main point is the go dostuff. I've got two calls of that. So, I'm creating these two goroutines. Now, notice they both take two arguments, CH1, CH2. But the first call, the first goroutine, the first go dostuff, it takes the order of the arguments is CH1 first, CH2 second. Then the second go dostuff, the order's changed, CH2 first, CH1 second. So, what this means is that, so remember dostuff that we just saw. What it does is, it waits to receive something on the first channel argument, and then it writes something to second. So, what that means is that the first goroutine is going to wait to receive something on channel one and write something on channel two in that order. Now then the second goroutine is going to wait to receive something on channel two, then write on channel one. Notice how they're depending on each other. So, the second goroutine is going to write on the channel one, while the first one is waiting to receive something on channel one. So, the first one's going to be blocked. Then the second one is waiting to receive something on channel two where the first one is writing on the channel two. So, the second one is going to be blocked, both goroutines are blocked and nothing can progress. So, this is an example of a deadlock. So, you have to avoid this as a programmer. Now, if you were to run that code that I just showed you filled in with the details, if you run that code, golang runtime actually detects this deadlock. So, if there's a situation where all goroutines are locked, which is what we just saw, all goroutines are stopped, then the golang runtime automatically detects it, and you get an error like what I'm showing here. These are just the first few lines the error, but basically it gets an error that says this is a deadlock and let you know, which is a good thing. However, the golang runtime cannot detect when only a subset of goroutines are deadlocked. So when that happens, then it'll lock those, they'll be deadlocked, and you won't know it in any obvious way. It's just your program won't operate correctly, and you'll notice it's somewhere down the line, it's harder to debug. So, this type of deadlock, these type of circular dependencies have to be avoided by the programmer. Thank you. Module four, Threads and Go, Topic 3.3, Dining Philosophers. So now we're going to talk about the dining philosophers problem. This is one of these classic concurrency problems that people use to talk about synchronization and show basically possibility of deadlock problems in synchronization. So this is one of the classics. I mean you always teach this when you talk about concurrency. So, we're going to talk about it, and show how deadlock can sneak up on you. You have to be careful to avoid it. So, in this problem, you got five philosophers sitting at a round table. Each one has a plate in front of them, a plate of rice, and they're chopsticks they're going to use to eat this rice. So, one chopstick is placed between each adjacent pair of philosophers. So, there are five philosophers in a circle, there also five chopsticks between them. Now, everybody wants to eat their rice from the plate, but you need two chopsticks to eat the rice. So, every philosopher in order to eat is going to have to pick up the chopstick I'm going left, pick up the chopstick on the right and then eat. But only one philosophy can hold a chopstick at a time. So, when one philosopher is eating, his neighbors can't eat because he's got both of the chopsticks so the neighbors don't have their neighboring chopsticks, so at least one of them, so they can't eat. So, there are not enough chopsticks for everyone to eat at once, and this is key. So not necessarily one can eat a time, you can have multiple people eating at a time, but they can't all eat at a time. So they have to be properly ordered in order to all eat. So, the problem with this is if you implement this in a naive way or I wouldn't even call naive, but in a way without thinking through, you can easily cause possibility of deadlock in the system. So, here's a picture of our table. That is a round table, there's five plates for the five philosophers, and then you see this little sticks between, those chopsticks so there is five chopsticks. So, in our model when we code this, we're going to make each chopstick a mutex. That makes sense because a chopstick can only be held, taken or locked by one philosopher. So, a philosopher, so this a chopstick and one at the top, there's a philosopher to the left of it, philosopher to the right, only one of them can read that chopstick at a time. So, they can only have mutually exclusive access, so it makes sense to represent a chopstick as a mutex. So chopsticks are mutex, and then each philosopher is going to be associated with a goroutine because it's going to be eating. It's goroutine is going to be the action of eating, but it's also associated with two chopsticks, one on the left, one on the right. So every philosopher is going to have a left chopstick and a right chopstick. So, let's look at how we might code this in an obvious way. First, we will define our chopS as chopstick, our type, and that's just a sync mutex, sync.Mutex, so that's a mutex like we were saying. Then we make our philosopher type and that's a struct with two things, leftCS, left chopstick and a rightCS, right chopstick, and those are both pointers to chopsticks. So, we've got a philosopher, we got a chopstick. Now, the philosopher is going to have to have associated with a method for eating. So, this is what we're going to say the eating method looks like. So, it's an infinite loop, see that for the top, and what it does is it basically, the philosopher, first thing it does is it locks the left chopstick, then it locks the right chopstick. So then it's got both chopsticks. Locking is basically picking up the chopsticks off the table. Then it's it eats. So format, I just print eating to represent the act of eating. So, it eats. Then when it's done, it puts down the chopstick, puts down the right, puts down the right chopstick, puts down the left chopstick. By the way, the order of putting down chopsticks doesn't really matter for us. So, that's what eating is, and it's an infinite loop. It's just going eat over and over and over. Each one of these five philosophers is basically executing the same code. So, now in the main, I'm omitting some of these details, weights, and such, but the main, I'm just getting into the heart of it. First thing, if we look at this code, we're initializing, we're doing some initialization in the main. For its initialization, the first few lines are creating the chopsticks, and the next few lines are creating the philosophers. So, we got to make five chopsticks and five philosophers. So, if you look at the top, we make this slice for five chopsticks pointers and then in that loop, from I equals zero to less than five, we create these chopsticks and filling this array. So, we create these new chopsticks, five of them, all numbered CSticks zero through four. Then we do the same thing with the philosopher. So, we make this philosopher slice right there enough for five then we have another for loop and we curate the philosophers. We fill in the philosopher. Now, notice philos i equals ampersand, because these are pointers, and then the constructor base when I construct it, when I call philo I'm passing it two things. Now, remember the order of the structure feels, so philosophers structure. It's got left chopstick, right chopstick. That's the order. So, in the curly brackets there after philo, you can see two things. The first thing is going to be the left chopstick. The second is going to be the right chopstick. So, the first thing, the left chopstick is CSticks i. So, if this is philosopher zero, left chopstick is going to be chopstick zero. Then notice that the right chopstick is i plus one, modular five. So, you have to do the modular five to account for the last philosopher, philosopher four. So, what this means is that philosopher zero is going to have chopstick zero as its left chopstick, chopstick one is its right. Philosopher two is going to have chopstick two as its left chopstick, chopstick three as its right. But philosopher four, he has chopstick four as his left chopstick and chopstick zero as its right chopstick. It's in a circle. That's why you have to do the modular five because there's no chopstick five. He gets chopstick zero. So, we had to do i plus one modular five in there, but basically you get the idea. So, we've created in here, we've initialized the set of chopsticks, five of them, then we made five philosophers and associated their left and right chopsticks with each one of the philosophers. Now, this program, so this, basically, this is almost it. One more thing we have to do in the main after doing this initialization is we have to actually create the Goroutines. The Goroutine for every philosopher and get him eating. So, we have right after that, they start the eating. We say four loop i equal zero to five because we want to make five Goroutines one for each philosopher. We just say philosopher i dot eat and he calls this eat which is an infinite execution. So, this will start each philosopher eating and so starting these five Goroutines. We would also, I'm not putting this in here, but we'd also have to add some weighting in the main. Some form of weight in the main so that the main doesn't complete before these philosophers complete. Because the philosopher is the way I've written it. These Philosopher Goroutines will never complete, they're in an infinite loop. So, we've got to make sure that the main doesn't complete either. So, we'd have to put it in a little synchronization in there, a weight or something like that but I just want to focus on the philosophers for the moment. So, this is how you would write the code in a naive way. So, the place where deadlock can happen is if all philosophers, if they all grab their left chopsticks at the same time. Now, if you remember that code. So, this is a little summary of the code that each one of the eat code for a philosopher. First, he grabs his left chopstick, it locks his left then it locks the right, then it eats, then it unlocks the two chopsticks. So, now we don't know what interleaving is going to happen between these different philosophers, but there is an interleaving where each one of these five philosophers it executes its first lock, locking the left chopstick without going on and then the next philosopher does that, grabs its left. The next one grabs its left. Each one of these five could grab its left chopstick before they continue. In that state, if they all grab their left chopstick, meaning they lock the left chopstick, then all five chopsticks are locked. So, then when they try to execute the next instruction, locking the right chopstick, they won't be able to because all the chopsticks are locked. Because your right chopstick is somebody else's left chopstick so everybody's locked all the left chopsticks, they're all locked and we would be in a deadlock situation. So, there's an interleaving here, at least one interleaving, where you can get into this deadlock situation and it's easy not to see that. It would be easy to code this the way I just coded it and run into that type of deadlock. Now, this is a fundamental problem. There are lots of solutions that have been proposed, ways to fix this. One way to fix this, so Dykstra's way. In this particular case, Dykstra is a genius. Anyway Dykstra, he decided to fix it by basically modifying the code and I want show you the modification, really, but he wants to modify the code so that each philosopher picks the lowest numbered chopstick first. Now, what I'm showing there in the blue is the code that we have. Our code does not do that. Our code, the first one that you pick up is the one to your left, which is for most of the philosophers that's the lowest number. So, if you're talking about philosopher zero, to his left is chopstick zero, to his right is chopstick one. So, the lowest numbered chopstick is chopstick zero. So, that's the one that he picks up first, the left one. So, that's true for all of them except for philosopher four. Philosopher four, on his left he has chopstick four, on his right he has chopstick zero and four picks up chopstick zero first. Sorry, according to our code, four would pick up chopstick four first and then pick up chopstick zero. So, the code that we have violates this rule that I haven't read, picking up the lowest numbered chopstick first. If you change the ordering so it always picks up the lowest chopstick first, then philosopher four would pick up chopstick zero before chopstick four and it would try to pick it up and if they were about to be in a deadlock situation, if everybody else had picked up their left chopstick, then plus a four would be blocked because it would try to pick up chopstick zero but it would already had been picked up by philosopher zero. So, then you wouldn't get into the blocking, you wouldn't get to the absolute deadlock state that we would have. Then it wouldn't pick up this chopstick since it tried to pick up chopstick zero first, it would never get to pick then chopstick four, which means philosopher four would block and philosopher three would be allowed to eat because philosopher three could then grab its right chopstick, chopstick four, and they could eat and then we could continue. So, there is no deadlock in this situation but philosopher four may starve. So, what that means is that philosopher four in this setup gets lowest priority. He's the one who ends up having to wait on others most of the time. So, that's called starvation. He would, it's literal starvation in this example but that can happen in other scenarios, too, where you have multiple threads, multiple Goroutines, they are all executing but some number of them don't get to execute as often as the other ones because of the way you've set up your synchronization. So, starvation is another issue but deadlock is the worst and you can avoid it in several ways but just be careful of these circular dependencies. So, this is a case where you have a circular dependency but the circle is five philosophers long. The dependency it has to go through all five philosophers, the four, the circular dependency completes itself. So, it's a little more subtle to see. Thank you.
