Module 2; Concurrency basics, topic 2.1, interleaving. So, writing concurrent code is hard. Part of the reason why it's hard, a big chunk of the reason why it's hard, is because it's hard to have a mental model of the state of the program at any particular time. So, what do I mean by that is if you're writing sequential code, regular old code and it crashes on line 10, then you know what's been executed before that, you know it must execute line 9,8,7,6, and so on, and you know basically what order, right? So, it helps you figure out what the state of the program should be where it crashed. You implicitly depend on that when you're debugging. You say, "Well, I know I got to hear, so it must have done that, right?" That helps you zero knowing what the problem is. With concurrent code, is much harder to get a bead on the state of the machine. So, when it crashes, maybe crashes on line 10 in task one, but where is it in test 2, 3,4,5, right? It can be in different places. So, the state, the overall state of the machine is as not deterministic. Meaning, so by that I mean, say you got a crash, you crash on line 10 and task one every time. But every time it can be at a different point and test two or three or four, right? So, every time you run it, even though it crashed at the same line in task one, it may be a different overall system states every time. So, it makes it confusing to keep in your mind this variable should be that, and this variable should be that because maybe this task has done something or maybe it hasn't and you don't know what's been done what hasn't, okay? So, this is really, to me, the hardest part about programming concurrent or writing concurrent code in any language. So, just to show you what the complexity is here, you have what are called these interleaving, the interleaving are the instructions in two different tasks. So, the order of execution of statements in the task is known. So, for instance, I got task one test two, and each one has three instructions in order one, two and three, and these are just random instructions, it doesn't matter what they do. But you know that in task one the instructions are executed in order one, two, three, test two there execute in order one, two, three, but the order of execution between concurrent tasks is not known, is not determined, meaning it is not deterministic, it could be different every time. So, what that means is these instructions can be interleaved in different ways. So, I might execute the first instruction for test one, then the first instruction for test two, then the second instruction for test one, then test two second instruction and so on. But that's one possible interleaving of instructions. But there are many possible interleavings and all of them could happen. So, every time you run it, you might get a different interleaving. So, it makes it harder for you for a program to keep in your mind because you have to consider all these interleaving when you're thinking about the correctness of the system. Now hopefully, not all, there're techniques to minimize it, but you have to consider many different interleaving in order to reason about how the system behaves. So, here's an example of a couple of possible interleavings. So, on the left, the left column. So, you got two little tables, one at the top one at the bottom. The top is showing one into leaving the bottom showing another. The left column are the instructions in the test one. The right column are the instructions in test two. Now, the top interleaving, the top one is showing is just alternating between instructions in one task versus the next. So, task one instruction one, task two instruction one. So, it's one instruction two, test two instruction two and so on. Now, the bottom interleaving is saying, look it fully execute task one, one, two and three, and then it fully execute test two, right? One, two and three. That is possible too, and there are many more. So, there are many interleavings that are possible and you have to consider all these possibilities, at least some subset of these possibilities when you're thinking about, does current code worked correctly or not. Now, one other thing that I'd like to mention is that these interleaving, the interleaving problem is even a little more difficult because the interleaving doesn't happen at the level of the sea and coders or Go Code, right? There so you write these instructions, let's say these are Go instructions, right? So, the interleaving isn't happening at the Go instruction level, is happening to the machine code instruction level. So, what I mean by that is that first instruction a equals b plus c. That, and Go, maybe that's all it is. But if I were to look at the machine code for that, that might be several four instructions long. I might be doing a load b from memory, load c from memory, add them together and then do our store a, right? So, it might be for machine code instructions long, and the same thing with each one of these instructions. So, the interleaving is happening even at the machine code level. So, what that means is you're not guaranteed that it finishes task one before it starts instruction one and test two. So, take that a equals b plus c and the top interleaving, right? The first line and task one. The essay that takes four instructions, for a machine code instructions. You might execute the first two and then it stops and goes to task two, right? So, you might not even finish the first instruction. So, these instructions, the interleaving is happening even in-between these instructions because it's happening at the machine code level rather than the source code level that we're looking at right here. So, that makes it even harder to get a handle on all the possibilities. Module two, concurrency basics, topic 2.2, race conditions. So, a race condition is a problem that can happen as a result of all these possible interleaving that you have to consider. Race condition is technically, is usually defined as a program that runs, a problem where the outcome of the program depends on the interleaving, right? Now, the interleaving, remember, is non-deterministic, it's determined by the operating system and the Go-runtime. So, the interleaving can change every time you run it, and in a lot of ways, it has a lot of freedom. So, you have basically a non-deterministic interleaving, but you never want to program or almost never, do you want a program that whose result is non-deterministic? Okay. You want to be that if you run a program and you give it a set of inputs, it always produces the same outputs, okay? That's determinism, right? If a program is non-deterministic, you take that program, you run it with a set of inputs, sometimes it gets one answer, sometimes gets another, that is almost always a failure, okay? That's non-determinism and you don't want that. But remember that the interleavings are not deterministic, you don't know what the interleaving are. So, you have to make sure that your program and it's outcome does not depend on these interleavings, if it does, that's called a race condition. So, what I'm showing here is a little example, just toys. We got these two tasks and we're showing two different interleaving two task. Now, the first task all it does is instruction one says, x equals one and instruction two says, x equals x plus one, okay? it's a real simple. On the right-hand side, you got test two and all it does is print x. Now, in the first interleaving on top, it's going to print a one because x is equal to one at the time when the print happens. While the second interleaving, x is going to print the two, x will be printed as two because it's a different interleaving. This is a race condition. The outcome depends on the interleaving and the interleaving is non-deterministic, so this thing has non-deterministic output and that's basically broken. So, this needs to be avoided, this is one of those complexities that happens because of all these interleavings. Now, race conditions, there are ways to avoid this type of thing to make sure it doesn't happen, and we will talk about that in Go. Race conditions occur due to communication. Communication between tasks or Goroutines that we're going to talk about. So, there's communication between these two tasks, I don't know if you see it, but they're communicating on variable x. So, the one task on the left is writing to x, is assigning x to one, is assigning x plus one to two. Where at the other task on the right is reading from x, is reading from it and then printing it. So, they are communicating through this shared variable called x, and that's communication, and that's where race conditions occur. See, if you had no communication between two different tasks you would never have a race condition because the ordering would be completely independent of each other. Meaning, when I say completely independent, the outcome would be completely independent of the ordering of the interleaving. But when you have some kind of communication going on between the two, then it matters which instructions in task one say, which instructions that write to this shared variable? Which ones happen before test two reads from the shared variable? So, communication is a source of race conditions, but communication is very common between these different Goroutines. So, different tasks they generally communicate. Now, threads in general, whatever language, threads are largely independent. They're independent of one another but not completely independent. So, what does that mean? They're largely independent, meaning, they mostly don't have to communicate with each other. The whole reason why you've made two different threads, or Goroutines is we're going to call them in Go. Reason why you've made two different threads is because you feel like these two things can be executed concurrently at the same time without caring which one to execute first, or second, they can just execute it at the same time. But they are never completely independent because if you've got multiple threads all in one process, they're sharing information. Remember how threads have they share common data. They share the virtual space and all these. The fact that they're different threads in the same process means that they are sharing. So, it's very common there's some level of sharing between threads, and the sharing of information is communication. So, for instance, web servers a really common multithreaded application. In this picture the web server, you got in the middle, you got this web server. Now, the right you've got these clients, these are web browsers. They're connecting to the web server over the network, and I'm showing three but there can be any number of them. Then, on the left I've got the web page data. So, this web server say it's UCI's webpage, is UCI web server. It's that orange data is all the data on all the pages that we have. That's going to be together with the web server and some disk or something. Now, as these clients come in, as they make connections, so one browser comes to the website it wants to look at one page. Another browser connects, it wants to look at a different page, different sub-UCI page. Another client comes in and wants to look at a different one. So, this web server program it makes a lot of sense for it to make a thread for every client that comes in. Because each one of these communications, like if this communication with one particular client, it's likely to do different things, its client maybe it wants to look at this web page where the next client wants to use another web page, all within UCI but different sub-pages. So, it makes a lot of sense, and to room in as multiple threads because these clients are all coming in at the same time. So, it's a type of thing where you have to handle all these clients all concurrently. You don't want to have a web page that handles one browser at a time. You got to handle them all concurrently. So, it makes a lot of sense to make this a multithreaded application, you got one thread for each client. Now, these threads are largely independent but they do share data sometimes. You can have two clients come in and look at the same web page. They might both be looking at the top of the web page. Also, you can have notice arrows between these blocks are two way. So, for instance, you can have web page where the client sends data, basing post data of the web page. We don't want to get into a web page too much but the client may posted to a web page actually changing the web page. Like the most obvious place where you see this is sometimes you see a web page where has a counter like a visit counter. That data is changed every time a client connects the counter goes up one. So, that counter value says there is other client who comes into that same page. He's got to see the updated counter value. So, in this way one client is writing to the web page increasing the counter value, and the next client is reading from that same page reading the new count value, and then writing back to it increasing the counter value again. So, the point though is that there is some level of communication between these clients, they are not completely independent, they can be looking at the same sub-page, look into same files and data and so on. So, periodically, they have to communicate with each other. Now, it shouldn't happen too often. If there's too much communication between two threads you probably don't have them in separate threads. If they're communicating all the time, then you should probably just make them one Goroutine, don't separate them. But if they're separate, mostly, but every once in while having communication then two Goroutines makes a lot of sense because they can execute concurrently most of the time. Now, another example I have is this image processing example. Image processing tasks are often what they call embarrassingly parallel. So, image processing, say you got some big image, you got some images, a megapixel. It's got a million pixels in it. You want to do some processing, you want to do a blur or something like this. Maybe you want to blur the pixels. So, with a blur is a pretty localize operation, you look at a pixel, you look at surrounding pixels, you average out the values. But this same task you going to do it on every single pixel. So, this type of thing it makes a lot of sense to have multiple threads. You got one thread dealing with some pixels, another thread dealing with the next set of pixels, another thread dealing with the next set I'm only showing two threads right here. Actually, this is an extreme, this is what a GPU does, a graphics processing unit, this is exactly what a GPU does. You might have a thousand cores on this GPU, and it'll take an image with a million pixels, and they'll just divide up all the pixels between the different cores that are all running on different threads on each core. So, this is the common thing where it's easily paralyzable, one thread can work on one set of pixels, one can work on another. But not completely paralyzable because take like a blur. A blur, you look at your analyzing a pixel you got to analyze the neighbouring pixels and average their values. So, you are not completely independent of the neighbor. If there's another thread working on your neighbor pixel, those two have to share information. This guy has to know the pixel value on the neighbor, this guy has to know the pixel value on the neighbour. So, there is some communication between these threads, they got to share what are the pixel values of the neighbors had to share. So, even though image processing is you can largely paralyze and shuffle it up amongst different threads, there's always some level communication between the threads, and you have to be able to support that. So, remember that this communication, if you don't support it correctly, it can be the source of race conditions. Where if one happens first before the other one is some weird interleaving you get different results. So, this is part of what makes concurrent programming very difficult. Thank you.
