Module 4: Threads in Go. Topic 2.1: Mutual Exclusion. So, we've been talking about channels. Goroutines are sending data back and forth through channels. Now, sharing variables between goroutines can cause problems. I'll show you an example of this, but two goroutines writing to a shared variable, to the same shared variable, can interfere with each other. So, one will try to write one number, the other will try to write the other number and they will get into an inconsistent state and I'll give you a more concrete example of that in a few slides. A thread program is said to be concurrency safe if it can be executed, be invoked concurrently with other goroutines without interfering improperly with the other goroutines. So, then you say, oh this is concurrency is safe because I know that when this runs it won't mess with the variables of the other goroutines and alter them in some way that will ruin the other goroutines. So, by this I mean, not that one goroutine can mess up the execution of another goroutine, right? To, say this one goroutine is using a variable x, the other goroutine writes to that variable x while the first goroutine is using it, maybe the second goroutine didn't intend for that variable to be written by this first goroutine. So, the first one goroutine can interfere with other goroutines. A function is said to be concurrency safe if you know that that won't happen, that they won't interfere in these unsafe ways. So, let me just give you some example of what I mean by bad sharing, how can that happen and how can they interfere with each other. So let's be a little more concrete. Okay. Here's an example of variable sharing going on. Now, all of this is going to do is, all it really does is it increments the variable i. So, there's this variable i, we're going to start it off at zero, and I'm going to make two threads. In my main I'm going to make two threads which just increment i and each one is going to increment it once. So, by the time they're done, i should equal two. So I should start off as zero, you run these two threads to increment i and then at the end i should equal two. So, just to look at the structure of the code, there are two functions, the main and the inc function for increment. At the very top I'm just declaring this global variable i, also I'm declaring my weight group, remember I make a weight group so that the main doesn't complete before the goroutines or before the sub-goroutines have a chance to execute. So I make the weight group. Now, my increment function all it does is i equals i plus one and then it calls our wg done to know that you don't have to wait for it anymore, it is now done. Now then, my main function I execute wg.add, I call the add method and I add two because I'm going to wait on two goroutines because I'm going to have two goroutine I'm going to create the do incrementing. So I add two, then I invoke the two goroutines. So, go inc, go inc, both of them, should just increment this i. And then, I do weight, wg.Wait, waiting for both of these guys to finish, and then at the end I just print i. So, what I expect is that I should print two. Because i starts off at zero, I initialized the zero at the top, it should be two when it's done. But this doesn't always happen. So, let's explain why this doesn't happen. Sometimes it doesn't happen because of all the possible interleavings. Now at first glance, it would seem like there's no real problem here because there are different interleaving but the interleavings all look reasonable, they look like they don't cause a problem at a glance. So, what I'm showing here is this table, there are two tables, two different interleavings. Each one of these tables has task one on the left, task two on the right, task two in the middle and then on the right is the value of i, I just want to keep track of the value of i as we go through the code. Notice, I'm not showing all task one and task two. I'm not showing the done calls. The ordering of the done calls doesn't really matter for this. But I'm showing that there are two different orderings for the i equals i plus one. So in the first in the top one, the top chart, task one executes i equals i plus one first, then task two executes it's second. In the bottom, task one execute second, task two executes first. But either one of those two orders, the value of i ends up correct. So, if you look at the top ordering look at i, it's zero at first, after the first increment it becomes one, after the second increment it becomes two. Same thing on the bottom even though the task two does this increment first, it doesn't really matter because i is incremented twice still, so it goes from zero to one, one to two. So, it looks like either one of these interleaving is just fine and it shouldn't change the value of i, but that is deceiving. So, really there are a lot more interleaving than we're seeing here. The reason is because of the level at which this concurrency, this interleaving actually happens. So, concurrency is at the machine code level, not the source code level. So, what I mean by this is that the interleaving is not interleaving of go instructions, go source code instructions, where it's actually getting interleaved at the underlying machine code instructions. So remember, the go source code is compiled to machine code on whatever platform you're on. So, these machine instructions which are sort of smaller instructions, those are what are actually getting interleaved. So, what that means is for each one of these go source code instructions, there can be a sequence of machine code instructions that correspond to the go source code instruction. So, the interleaving can basically partition, can chop up, interrupt right in the middle of a go source code instruction, it can start interleaving right in the middle of it. So, let's be more concrete. Let's take i equals i plus one, the instruction that we're basically looking at right now. Now, that might be typically that could map to three machine code instructions. First, a read i where you read the value of i from memory. Because remember that most of these machines they're register-based. So, when you do the increment operation, you can't just increment directly in memory. I mean, there are processes that do that but most of the time you first read the data from memory into a register,, then you do the arithmetic manipulation and then you write the result back to memory. So, those are the three steps I'm showing here. Read i, it goes to memory to wherever the value of i is, brings it into some register, then increment just takes the contents that register as one, then write takes the contents of that register and writes it back to memory wherever i is supposed to go. So, that i equals i plus one, it looks like one instruction, is one go instruction but it's really a sequence of these three machine code instructions. Now, this is important to keep in mind because the interleaving actually happens at that level. So, and that's what gets confusing because see normally, programmers aren't thinking about the machine code when they're writing their code or if they were then they'd be writing machine code directly where assembly go to code straight. Now generally, if you're writing go code you're thinking source code level, go instructions. You're not thinking about the way that the go instructions are subdivided into machine code instructions, not unless you're a hardcore coder, you usually don't think about that. So this is where people can get tripped up. So, let's show the interleaving, the different possible interleavings again. Except this time, instead of just looking at the two interleavings, task one does the increment first or it does the second right those are the two. Now we're going to take these three instructions, these three machine instructions and interleave those and show how it can go wrong. So, here's an example where it goes wrong. So this time you got task one left, I'd say I've the very left column I've just numbered the underlined so I can refer to them. But you got task one and task two and then on the right you got the value of i. Now, task one if you look at just a task one's column, first it's going to do a read in step one, then in step three is going to do the increment, then step four it does the write. Task two it has the same order. In step two is going to do a read, then step six it does an increment, step seven it does a write. So, fine, in each one of these tasks, the ordering stays the same but the relative interleaving can be different. So, notice the interleaving that we've picked and I've highlighted the read instructions, read i, read i. Task one does a read, read i in step one and task two does a read i in step two. So, what happens is both of them have read the same value of i. So, note that the value of i at the beginning is zero. So, task one and task two have both read values as zero for i. Then task one goes ahead in step three and in step four it increments that zero to a one and then it writes it back to the location memory where i goes. So, it writes a one into the location memory where i goes and you can see that i is equal to one. But remember that task two, the read that it did in step two is still read as zero. So, by the time task two does it increment in step six, it's incrementing what it read was a zero, which was a zero. It's not incrementing the actual value of i in memory which is now a one. Remember task one wrote a one back to memory in step four, but that's not what was read by task two. Because of this interleaving, task two read the old value of i zero. So, task two in step six it increments zero to one and then it writes a one in for i. Now, there was already a one in there for i, writes another one in there for i. But at the end of the sequence, i has the value one instead of two. So, think about this for a little while but the idea, the general problem is that when these two goroutines are sharing this i variable, they're both writing to it. The interleaving is happening at a finer granularity, at the machine code level and that adds complications that people don't think about sometimes. So, it's important to be aware of these. Thank you. Module 4: Threads and Go. Topic 2.2: Mutex. So, how we do sharing of data correctly between goroutines? Don't let two goroutines write to a shared variable at the same time, just as a rule of thumb. Don't let that happen because you can get these interleavings that are going to cause the problem that we just saw. So, you need to restrict the possible interleavings of these goroutines. Say there are two goroutines, goroutine one and two, which are both writing to this variable i, to the shared data. Then you have to restrict their interleavings in such a way that you make sure that they can't both write to it at the same time. So, access to the shared variables cannot be interleaved. You have to somehow as a programmer ensure that they can't both do that at the same time. So, how do you do that? That is called mutual exclusion. You need to have code segments, you as a programmer have to declare code segments in these different goroutines which cannot execute concurrently, so that they cannot be interleaved. So, this action of say writing to shared variables. So, say these two goroutines both write to i. i equals i plus one, i equals i plus one. You've got to make sure that this goroutines segment where it writes to i, cannot as mutually exclusive with the writing to i for this other goroutine. So, you have to declare these segments of code that are mutually exclusive with one another, and you have to do that as a programmer. So, there are constructs, of course, built into Golang to do that. So, what we're going to use is in the sync package again, there's this mutex object. Mutex ensures mutual exclusion. There are several methods associated with mutex, but let me just describe it conceptually first. It uses what's generally called a binary semaphore. So, semaphore is like the flag on your mailbox. If you have one of those outdoor mailboxes. So, if the flag is up that means the shared variable is in use. That means that somebody is using the shared variable. So, like specifically, the shared variable, if we're trying to protect this variable i. There are two goroutines that are writing to i. Only one can do it at a time. So, the flag should be up when one goroutine is writing to i. Then the flag being down means the shared variable is available. So, when this one goroutine is done writing to i, then the flag goes back down. Then the other goroutine knows, "Oh! Now I see the flag is down, I can write to i if I want to." So each one of these goroutines has to adhere to this protocol. Meaning, there's a semaphore in this flag and is binary., these are up or down, zero or one 1. If the flag is up then you are not allowed to use the shared variable. Because that means somebody else, some other goroutine is using it. If the flag is down then you are allowed to use the shared variable, but you have to put the flag up first. So, you have to put the flag up and then use a shared variable, and when you're done using the shared variable, you have to put the flag back down so everybody else, all the other goroutines, know they can use a shared variable. So, it is this protocol that the programmer has to write into their code and adhere to in order for this scheme to work. But this is the idea. Thank you. Module four, Threads in Go, Topic 2.3 Mutex Methods. So, we talked about this semaphores inside the mutex. You put the flag up, put it up to declare a goroutine is using the shared data, it's writing to it, and then put the flag down when you're done writing to it. So, these are implemented in a set of methods, lock and unlock. So, lock when you call lock that basically puts the flag up, and when you call unlock, it puts the flag down. Goroutine should call lock before it's about to use the shared data. What'll happen is, if no one has the lock, meaning no goroutines are using the shared data, then that first lock that call to lock will proceed. It'll put the flag up, meaning it sets some binary value from zero to one internally and then it will continue. So, it will not bloc. The code will execute in that mutually exclusive region and it will access the shared variable. Now, while that's going on, say another goroutine comes along and calls lock. Now, remember at this point when the second goroutine comes along and calls lock, the flag is already up. So, when that happens, this lock will block. It won't allow the second goroutine to continue and access the shared data. So it stops the second one. So, whichever goroutine gets into that region calls lock first, it gets the lock and the other guy, whoever the other one is, it has to wait. Notice that we're talking about two goroutines. This could be any number of goroutines. You can have 10 goroutines all try to share the same i variables something like that. One of them gets in there first calls lock first, then there could be nine other ones that try to call lock while the first ones in there and all nine will block. So, that's basically what lock does. Now, unlock is the matching thing. So, unlock is the function that gets called when the goroutine is actually done using the shared data and it's effectively putting that flag down. So, when this one goroutine is done using a shared data, it's got to call unlock if it doesn't that's an error because it'll cause a deadlock. It calls unlock, and then what will happen is, one of the goroutines that are waiting, they're blocked on their lock, will be able to continue. So, if there were like nine goroutines that call lock and are now blocked, as soon as unlock is called, the first one that called lock that is in waiting list, it will be allowed to continue, it'll stop blocking, it'll be allowed to continue, it will access the shared variable. In this way, as long as every goroutine calls lock at the beginning of it's mutually exclusive region and calls unlock at the end, then, it ensures that only one of these goroutines can be inside this region, this mutually exclusive region. Which in our case is basically where the shared variables are being written to. So, this mechanism is sort of generalizable to lots of different goroutines even though we're only talking about two right now. Here's a little example of it, how we would modify this incrementing problem. So this Incrementing problem that we had, I'm fixing it now. I'll go to this increment function and now basically I've done a couple of things, if you look at the second line, I've created a mutex, so call it 'mut'. Then, the increment function is still this i equals i plus one, but before that it calls 'mut.loc' and after that it calls 'mut.unlock'. So, now that region in between the lock and the unlock that is mutually exclusive with any other lock/unlock region. So, remember with this example, these goroutines, I had two goroutines we're calling that would basically execute increment. So both of them have a lock and unlock since they're both executing the same function, increment function, they both have a lock and unlock before and after their regions. So, those regions are exclusive. So, only one of those two goroutines can be executing i equals i plus one at a time. Because once one of them gets in there and calls lock, the other one is blocked on that lock. Until the first one finishes, calls unlock then the second one go through. So, that's a simple example of how you would do mutual exclusion. Thank you.
