Hey, welcome back for another episode of Code Club. I'm your host, Pat Schloss. In my experience, the gateway to learning more about the tidy verse in R is learning how to make plots using the ggplot2 package. The syntax with ggplot is relatively straightforward and, dare I say, intuitive. If you don't believe me, try making plots that you currently make without ggplot. The generic syntax to building a plot is to have a ggplot line where you define your data frame and your aesthetics. This line is followed by a line with a geome, indicating how you want the data represented in your plot. But did you know that you can use multiple geomes to plot data on top of other data? Not only can you use multiple geomes, but you can also use multiple data frames to generate your plot. In today's episode of Code Club, I'm going to show you how you can display your data using multiple geomes and multiple data frames. We'll see how this plays out in today's episode, where we'll revisit a plot that I made in the last episode that plotted the number of copies of the 16s rRNA gene for each genome in each taxonomic group at any taxonomic level. Even if you have no idea what taxonomic ranks or taxonomy is, and you're only watching this video to learn more about R, I'm sure you'll get a lot out of today's episode. Please take the time to follow along on your own computer. If you haven't been following along but would like to, welcome! Please be sure to check out the blog post that accompanies this video, where you'll get information on catching up, reference notes, and other materials that you'll find useful. The link to the blog post for today's episode is below in the notes. So I've already created an issue branch in my terminal. Again, I can do get status and see we're all good, we're all up to date. I'll go ahead and open up RStudio, and I'll double check that I'm in my working directory, correct working directory, and that's where I want to be. Again, if I look at files, I see in my exploratory data analysis that the file we were working on last time was from October 5th. I'm going to keep working on that and see if I can't make this window a little bit smaller. Okay, so to kind of bring us back to where we were, let me go ahead and rerun this initial code chunk that was at the top, and I can do that in RStudio by hitting this play button. It loads and runs that code chunk, and then if I go ahead and run this here, we see a plot in the lower right. You know what? I'm going to try to live a little and turn off these editor options, chunk output, console, and see what happens if we do it from within the window here. And for some reason it's not putting it there.  Anyway, we can see what it looks like down here in the bottom right. And what I'd like to do, again, is have something on top of this. And up here in this part of the code chunk, let me just come back. So up here we read in our metadata. This had our genome ID taxonomy information, the taxonomic information for every genome we had. We also read in the ASV file. So we know which ASVs correspond to each genome and how many times they show up in each of those genomes. We then joined those together here on line 25. Then we went through a series of steps so that we got a representative average number of copies per species. And we then made our wide data frame tidy to create a series of columns where, again, if we look at rank, taxon, or ends, we see that it has three columns indicating the rank, the taxon within that rank, and the mean number of copies there. And what you'll also notice is that rank is a factor. And so the nice thing is that we see on our x-axis then that our categories are plotted in the order of that factor. So that's great. And so again, as I was looking at this, the points over here get kind of muddled. I'm using GM jitter with an alpha of 0.3. And you'll see that if you have basically three points on top of each other, that's going to be a solid black point. I could go to something like 0.1, but that's really, it's going to make everything else really faint. And it doesn't really help me see where the average is, especially for species or genus. So I'll go ahead and put that back to 0.3. And what I'd like to do is show you again that we can put geomes on top of geomes. So what we'll do is we'll do geom boxplot. And we'll keep that with no arguments. And what this is going to do is it's going to use all the same aesthetics that geom jitter had used. So if we go ahead and run this, we see now that we get our boxplot on top of our geom jitter. So there's a couple things that aren't great here. So first of all, what we notice is that, well, we don't have the same alpha, but it's also double plotting the points. So this solid point for phylum is an outlier in geom boxplot that also shows up for geom jitter. So we're double plotting points, which is not great. The other thing is that our boxplot is on top of our jitter plot. So again, this is why it's really important to remember that we're looking at layers, that if I move geom boxplot ahead of geom jitter in my pipeline here, now all my points will be on top of my geom boxplot to the point where I really can't see what's going on there. All right. So I think I would like to have my geom boxplot on top. And so there's a couple of things that this is white, and it's that the fill color on the box is white. And so it's masking everything else. And also we've got these outlier points. So I always forget how to do this. But if I do question mark geom boxplot, it will tell me how I can turn off those outliers. And so we see there's all these arguments for setting characteristics or attributes of the outlier. And down here, if we look at the section on those arguments, it will see that sometimes it can be useful to hide the outliers, right? So we want to use outlier shape equals na. So again, if I come back and put outlier dot shape equals na as an argument for geom boxplot, we run this, we now see that we no longer have that double plotting going on. And those outliers for the boxplot are gone. So the other thing that again stands out a little bit is that the fill color is white. And I would rather have fill equals na. And so that will say no fill, right? And so that looks pretty decent, although it's really hard to see what's going on. So one thing I might do with my geom jitter, instead of alpha equals point three, maybe what I'll do instead is to do color equals gray, right? So this this looks fairly decent. I don't know that I really like it all that much. It does show kind of the bounds on the distribution, the edges of the rectangle indicate the 25th and 75th percentile. The line in the middle is the median. The line extends as far as one and a half times the difference between the 75th and 25th percentile. So this works, this looks nice. It's one way to do it. I'm not a big fan of over plotting a boxplot on top of a jitter plot. I think it's just kind of, it's kind of messy, kind of noisy. So let's see what else we could do. Okay. So again, this was showing how we could plot one geom on top of another geom. What I will do now is modify this. And what I'd like to do next is perhaps put a single dot on each column to indicate the average, right? So this is going to force us to think differently because our rank tax on our ends contains, you know, a value for every one of these points being a different taxa within that rank. So I need to get, I need to summarize this to get kind of like a mean of means. So I'm going to call this mean of means. And I'm going to remind you from last time what we did, where we grouped by, in this case, we're going to group by rank, and then summarize. And to do mean of means equals the mean of mean, or ends. Okay, maybe I'll call it mean, mean, or ends. Because sometimes it's weird to have the data frame have the same name as one of the columns, but it is what it is, right? So let's see. Ah, it reminded me because I forgot. We'll do dot groups equals drop. And that will go away. I mean, it's effectively the same thing. It's doing the same thing, right? It's getting rid of that last layer of the onion, if you remember my metaphor from last time. So now if we look at mean of means, we see for each taxonomic rank, the average number of copies that we're seeing across all the taxa there. So again, I would like a point at each of these values across my ranks. And I'm going to remove the geom box plot. I kind of like this look with the color gray, thinking of it kind of sitting in the background. What we'll do is we'll add geom point, right? And if we ran geom point with the current AES, the current aesthetics values from up here, then it's going to plot all those x and y values, which you see as a column of the points, whereas the geom jitter is the same thing as geom point, except that it jitters the x position. So I don't really want to do what I have here. I want the geom point to come from my mean of means data frame. So one thing to note about how I have this written here is that these first two lines are really the same as doing this, right? Where I say data equals rank tax on our ends, right? And again, we get the same output. I like to pipe this in, because sometimes I might want to modify that data frame before I start plotting it. And so it's easier to kind of have it outside of that gg plot line. But I want you to look at the structure that we have here, because we can use this structure for any of our geoms to set new aesthetics and to set a new data frame. So what I can do now is say data equals mean of means, and then AES, right? And x will be our rank, and y will be our mean, mean, our ends, right? And I think that looks good. And what we see now is that we get a black point in the middle of our columns, right? And we could do the same type of thing where here we have to, yeah, we can modify other attributes like color, right? And so here we modified the color of the jitter to be gray. Well, we can give a different color to our black point here to say be color equals red, right? And so now we'll have a red dot. Perhaps we'd like, let me break this up a little bit to put on different lines. Perhaps we'd like to say shape equals star. I just learned recently that you can name the shape without actually having to give it a pch number. And so I wanted, I guess, maybe asterisk. Asterisk, asterisk. See how that works? So that kind of works. I think I really like the default solid circle. Maybe what I'll do is I'll make size equals two to make that point a little bit larger, okay? So that's another option. And again, what we're seeing in this example, of course, is that we can have a different data frame that we're plotting, along with a different set of aesthetics that we're going to be using here. And one thing I want to experiment is if I remove that x equals rank, it also works, right? Because it's going to take that x equals rank from the previous aesthetic down to this one. Now, an argument that we could use, if we need, would be to do that ignore AES equals true. Let me look back at geome point. And this is one of those arguments that you wonder, what does that even mean, right? So inherit AES, okay. Inherit equals false. Right. And so what this means is, don't bring down the AES values from the ggplotline or other geomes into this one. And so this should complain inherit dot AES. And so it complains, because it's missing the aesthetic x, right? So you could say x equals rank, y equals mean of means, and we get that. So we don't really need this inherit AES here. Wanted to show it here, show it here. So you can know that perhaps you might set an aesthetic here that you don't want brought down here, right? So maybe I could do, you know, size equals mean or ends. This is going to look really bad. So let me get rid of this. Hold on, this is going to look horrible. So the size of the points is related to the size, the number of copies, right? And so perhaps, that actually isn't doesn't seem to be affecting the size of my mean value too much. Oh, and that's because I have size equal to here. So if I move that, then I think my red circles should also grow. So now it complains, because it says object mean are our ends not found, right? And so because I'm giving it a data frame here, data equals mean of means, it doesn't have a column mean are our ends, right? So again, this would be a perfect place to put in inherit AES equals false. Okay. Right. And so now my circle is, you know, the same size for all values of that average, right? Of course, this looks really ugly. Even me with my bad taste knows that that looks bad. So I'll go ahead and remove that size, and run this. And it looks good. I'll go ahead and leave that inherit AES equals false, because you never know what might happen down the road. It'd be good to turn that off. So we're not worried about getting those errors. Okay. So again, that's putting a point there. What if we put a line across, right? So I'm going to show you that we could put three geomes together. Let's do geom line, right? And we'll do actually, I don't I think it will actually inherit inherit from geom point. So if we run that, then that looks weird. So x equals rank, y equals mean are our ends. Yeah, it's not really doing what I, what I expected. So I think what it's doing is it is going from the rank to the mean are our ends, but it's still using this global declaration at the top of ggplot. So we probably do need all this. So if I copy this down, as an argument to geom line, run that, it's now complaining because it's like you only have one thing in each group. And so what we can do to get rid of that would be to say group equals one, run that. And now we have a line connecting our red points on top of our jittered data, right? We have three geomes here. That's pretty, it's pretty slick. Let me go ahead and remove the line, the geom point though, because I don't know that I really like that. And so that again shows the line on top of our different taxonomic ranks. And again, we could do things like size equals two to make that line a little bit thicker. What happened? I forgot a comma. And so we got a thicker line there, right? I think what I'm ultimately going to like is what we'll do next, which will be to put a segment across the cloud to show the average value. So what we'll use is geome segment. And geome segment is going to require two sets of variables. So it's going to require an x, a x and and a y and y and. And so the the x is the starting point of the segment, x and is the ending point of the segment. So I'll want something from here to here, and then something from here to there, right? And then the y, it'll allow you to make, you know, a diagonal line or a horizontal line or a vertical line. So my y and is going to be the same as my mean mean RNs. And let me go ahead and put in some line breaks to make it easier to read. And my x rank, if I go ahead and put in rank, let's see what happens if I put rank for both of them. Not much happens there, right? And that's because it's starting and ending at the same spot, right? And so we need to give it some separation. But if I notice my width is 0.3, if I do rank minus 0.3 and rank plus 0.3, then hopefully I can get that separation. So that doesn't work. It complains, because plus and minus isn't meaningful for factors, rats. So what we want to give here instead is a number that corresponds to each taxonomic rank, right? So we have kingdom phylum class family order kingdom phylum class order family genus species. So we have seven layers, right? So we can define, we can create a vector with one colon seven. So if I come down to my console here and do one colon seven, I get numbers from one to seven. If I do one colon seven minus 0.3, I get starting positions. If I do one colon seven plus 0.3, I get that spot plus 0.3. And so it's showing the names, but it's really 1234567, right? So we can do one one to seven minus 0.3. And we can also do plus 0.3. And now we see that we have our red segment, something that we can also do as a argument for line geome segment would be line end. And we can say round. So because it has these like squarish ends. And again, I forgot my comma. And so that gives kind of a rounded shape to my line segment. I kind of like this output more than what we've been playing with previously. A couple of things we might do to clean this up. Aside from so I'm going to go ahead and pull this out to pipe that in. Run it every time I change something to make sure it works.  And then I could say width equals 0.3, or equals jitter width minus jitter width plus jitter width. I could say n ranks. And that I could then say, I could get a number. So instead of being one to seven, I could get all the ranks, right? And so I could then say, well, this is really the number of rows in the mean of means, right? So I could say n row mean of means is n ranks. And so n ranks is seven, right? And so if I do one colon n ranks, I get my one through seven, right? So here I can do n ranks. And the reason this would be relevant would be because say I so here I'm not including the strain level, right? Well, maybe I want to go back to the strain level. And instead of having to change the seven to eight and all think about all these things, this will automatically get get it for me. And if I want to do say 0.2 and rerun this whole chunk, then it'll be narrower and my segment will be the right width. And if I do say 0.5, it'll be wider. And my segment will be the same width, right? So I think 0.3 was really what we liked. And I'll go ahead and build that out. And so that looks good. Excellent. So one last thing I want to do because this kind of annoys me across the bottom are these labels. So I can do scale x discrete. And I will say let me I always kind of forget the actual arguments. I think it's breaks and labels. Let's try that. Breaks equals kingdom, phylum, class, order, family, genus, species, right? And my labels, I'll capitalize them, right? So it's the little things that annoy me, like capitalization. And there's probably an easier way to do this title case, probably with like a function of some type. But I think this this will serve us pretty well. And so we see that, yeah, I guess the argument's right. Breaks and labels for scale x discrete to change the names that I have here on my x axis so that they're all capitalized. Good. I'm going to go ahead and save this. Tell me what you think down in the comments below. Which of the four different ways did you like better? So over plotting with the box plot was option one. Option two was putting a dot on top of the cloud to show the average. Option three that we looked at was using a line and a line with a point, perhaps. And option four is what we see here with GM segments. So tell me down below what you think looked better. Next time, we'll talk about a different approach to looking at these distributions. Because we don't really have a sense, I guess we did from the box plot of kind of the shape of the distribution. So next time, we'll talk more about how we can look at the shapes of these distributions beyond just the average. For now, I think we're in good shape. I'll do get status. I'll add our exploratory 2020 5. Yep. And I forgot to knit it actually. So let's knit our whole document. That works. We'll go ahead and close that. And if I come back here, let me control C out of that, get status. Yeah, so I should have noticed that before all I had changed was my RMD document, but now I've updated my image, as well as my markdown file. And I can then go ahead and get add on my exploratory 2020 1005 plus star so I can get all those files and then get commit, add line segment to cloud of points to indicate average closes number 29. And perhaps I could also have improved my subtitle a little bit to show that the the red horizontal bar indicated the average, but I think that's good enough. Again, we're still doing exploratory data analysis. We don't want to get over. We don't want to go overboard with kind of making our plots look too pretty, right? So I'll go ahead and get checkout master, get merge issue 29 on push. And then we'll look up here on GitHub. And we'll see pretty soon here that this issue has closed. And we're in good shape. And we can come back to our code to exploratory. And if we then look at that, we can, the code is still a jumbled mess. But this is what our plot looks like on the website. And I think that looks really nice. One thing I noticed is that the resolution here is kind of crummy. But again, for exploratory data analysis, I think this is great. And it again, iterating through these different ideas gives us a sense of different ways that we might want to represent the data when we go to write a paper. The other thing that, you know, we see is that by iterating through these different ideas really quickly, I think it really shows the power of GG plot that here in just, you know, 20 or 30 minutes, I was able to generate, you know, four or five different plots really quickly to get a sense of how things worked. So again, feel free in the comments down below to tell me what version you like the best. This is what I prefer, but that doesn't mean it's the best way or the only way. See, if you know, you've got applications on the work you're working on, whether or not there are places where you would want to layer different geomes on top of each other, or like we did in this example, layering different data data data frames on top of each other with different geomes. So hopefully this exposed you to something a little bit new than you've seen in the past. And again, love to hear what you're doing with the material that we're covering here in Code Club. Keep practicing, tell your friends about it, be sure that you like this video and you subscribe to the channel, so you know when the next episode is released. Talk to you next time.


Hi, everybody. Sorry for the delay. I need to set up the camera. So, at this point are you finishing? Apparently, there's some sensor here. I cannot close the door. At this point, is everybody finishing up a sum of zero? How many of you have finished a sum of zero? Good. That's more than I expected. Yeah, so basically this year is how we have one bulk deadline for both a sum of zero and one, which will be next Friday. So, at this point, you should be already familiar with the environments, how to compile the kernel, how to run the simulator, and also you should have a pretty good idea of a sum of zero and ready to wrap up and move on to a sum of one. Because a sum of zero is kind of really just warming you up to give you some idea of what the environment looks like and how to play with the kernel code. And a sum of one is the first assignment that you should really you're supposed to write some code. So, as Jeff posted on the Piazza today, I'm going to, I will not talk about the environment setup for sum of zero, which I assume you already know how to do that. And today we mostly covered the basics for a sum of one, which is the synchronization primitives. So, where are you guys on the lecture? Are you talking about the processes? Are you talking about the synchronization primitives? So, do you know what locks and semaphones are? Yes, that's good. Okay. So, today we'll touch some basics for sum of one and show you how the OS 161 already provides some code for you to work on. My name is Jinghao and I will teach recitations this semester. So, first some logistics. The rest of it is today at four, this room, and Friday at 8 a.m. So, you just, you can attend easily when that's your schedule. You don't have to attend the one you registered on the hub. So, it's also open to graduate student. So, but the priority is given to undergrad who have already registered the course. And today we'll talk about the sum of one and concepts and all that. I already talked about that. So, the deadline for a sum of zero and one in next Friday. So, at this point, if you are still doing the sum of zero stuff, you really want to wrap up and move on to a sum of one. Because the initial time allocation for you guys is one week for sum of zero and two weeks for sum of one. This is already the second week. So, in a sum of one, you will be, you will need to understand various kind of synchronization primitives including lock, semaphore, which we will talk about today. And also condition variables and read-write lock, which we will talk about in next week's recitation. And also, you need to solve two synchronization problems, the intersection problem and well-made problem, which we will also talk about next week. So, to do a sum of one, the one basic concept you need to understand is what is a critical section? Basically, the critical section is one piece of code, several lines of code, that both serves these both conditions. One is that this piece of code access the shared resource. If there is no shared resource, then we don't need to do synchronization at all. A second condition is that this shared resource cannot be accessed at the same time. You have to enforce orders. Someone need to access the resource first and then someone access the later. So, one typical or classical example of this critical section, you can imagine that here is the shared printer case, where the shared resource here is a printer. And you have multiple users or computers who want to use this shared resource and do the printing job. So, in this example, our goal here is to design a self-print routine or method or function so that multiple users can safely share this printer. So, a strawman approach or a naive approach will be like this. I do nothing, I just in the self-print function, I just do the print. I don't care about the synchronization at all. So, of course, it doesn't work. Why? Yeah. Yeah, it doesn't do any checks. So, what if I was printing, I have 10 pages, and then some other guy can see, he also wants to print. I have to prevent him from printing, right? Otherwise, our print job will be mixed up. So, this is why we introduce the concept of lock. Basically, the lock is designed to enforce a mutual extruding concurrency control, meaning that once I acquire the lock, somebody else has to wait before I finish, right? So, the interface of the lock is pretty simple. Basically, two main interfaces. One is acquire the lock. Basically, I want to acquire the resource. And then, so, which is indicating I am about to enter the critic section. So, what will happen when I call lock acquire? What are the possibilities there? Well, in the most ideal case, nobody is using it, right? When I call lock acquire, I get the lock immediately, right? That's the most ideal case. What if somebody else has already hold the lock? Somebody else call lock acquire before you, right? Yeah, either you have to wait, otherwise, yeah, because there's only one lock available, right? Depending on how you are going to wait, there are two kinds of locks. Either you keep querying if lock is available, which is called busy waiting, where you just keep querying if lock is available. Another way is, so, you will call lock acquire. Inside lock acquire, you know the lock is not available. Then, instead of keep waiting there, you just sleep, right? And expecting the previous holder to wake you up when the previous holder is done with the lock, right? So, Jeff will talk about all these kind of differences in the lecture. So, all you need to do at this point, all you need to do is there are two kinds of locks. One is the spin lock, where you keep waiting on the lock. Another is called sleep lock or normal lock, where you sleep if lock is not available. And the second interface is pretty straightforward, lock release. You're done with the lock or you're done with the critic section. You just release the resource so somebody else can use the lock or use the resource. So, here's the second version of the self-print. Instead of just do the print inside the function, I first lock acquire the lock. So, if I wish line three, the third line here, I know that I'm the only person that are using this resource. In this case, it's a printer. And I also know that any further users will be blocked in line two, right? So, before I release the lock, I'm the only holder of this lock. Anyone who wants to use the printer has to wait, right? In line two case, wait in line two, the acquire function. So, once I'm done, I release the lock. I'm done with the print job. Somebody else can continue with the printer. Any questions so far? It's kind of pretty straightforward, right? So, the OS161 has already provided a spin lock for you, like I explained. This version lock doesn't do any smart things. It just keeps banging the lock until the lock is available. Then it continues, right? It's defining the header file, that's spinlock.edge, and implement it in the spinlock.c. This one has already implemented for you. You don't have to, you just need to understand how this spinlock works. And you don't have to write any code for this. So, let's take a look at the actual code. So, go to source code, directory, and go to kernel, include spinlock. Where is the header file again? It's not there. Oh, yeah, right. Thanks. Okay, here we go. So, actually, at this point, I mean, before Jeff explained the difference between the spinlock and the spinlock slip lock, all you need to do is understand the interface of the spinlock. Let's see, as we have explained, there are two major interfaces. One is spinlock acquire, which allows you to acquire the resource. And after you are done with the resource, there is a spinlock release function. So, these two are the most important one. At this point, you just need to understand the semantics of these two interfaces. You don't have to go to the details of how the spinlock works. Then, besides these two, there are some helper functions which initialize the spinlock for you here, and clean up the spinlock, and also check, there is a one function that allows you to check if you hold the spinlock. So, the spinlock part is quite simple, mostly because you don't have to understand how it works. You just need to understand the semantics. Now, so, we have already dealt with one printer example. What if you have multiple printers? In that case, how do you coordinate the access to the printers? Will this version two still work? How many no? Why? Why it doesn't work? Not necessary. I mean, it would work in the sense that we...  Well, you have multiple printers. If you use one giant lock to protect all the printers, what will happen? One user acquires a lock, he acquires all the printers. In fact, he only needs one printer. But this will work in the sense that it will provide the correct output, meaning that no printing jobs will be messed up. But it's not the best in the sense that you are wasting the resources. We have multiple printers. Why only allow one user to use all the resources at one time? You should be able to allow different users. As long as there are printers left, you should be able to allow the users to keep using it until all the printers are occupied. So that's why we introduced the concept of semaphore, which is supposed to manage a set of resources instead of just one. And it allows up to a certain number of threads in critical section. In the printer case, suppose we have five printers, we will allow up to five users using the printers, and that's it. If you really think about it, actually the lock is a special case for semaphore, where the resource number is one. If the semaphore number is one, then there's no difference between lock and semaphore. They are both achieved the same effect. And the interface of semaphore is just like lock. It's quite simple. We have p and v. These names are maybe peculiar as the first glance. If you are curious, you can check Wikipedia to see why it's p and v, but let's assume it's no more introvert. p means you want to decrease, or you want to acquire a resource. So you would p the printer semaphore to acquire one resource, and then you do the printing job. So you know that not more than this number of users will be in the critical section. So once you finish the p or acquire, you'll know there will always be at least one printer available for you. And similarly to lock release, we have v, which is to release one resource. So p is basically acquire one resource, and v is to release one resource. And also similar to lock acquire, when you do p, there's a possibility that you need to wait before the previous users release the resource. So as spin lock, semaphore is also provided to you, and it's very important to understand how semaphore works for you to correctly implement another version of a lock, cv and the read and write lock. So let's go over the details of how semaphore works. Here, as I said, semaphore is defined in kernel, include, sync, and edge. And if you look at the interfaces, so here's the definition of semaphore. So everybody knows what a structure is in c, right? How many of you don't know the structure keyword? Okay, if you want to see that it's the best, struct is just a structure. If you don't know c, you can imagine structure as a class without methods. It's just a member fields in Java or any other object-oriented language. So here, we have a string, basically character pointer, called the name, which doesn't play any actual role, but just for humans to know the semaphore well. And we have a wet channel, basically a queue where the threads can slip on if there is no resource left.  So as you can see that, spin lock is actually a building block for any other more complicated primitives, right? The semaphore applies when you try to implement the normal lock or the condition variables. So you should start noticing the building blocks for these synchronization primitives. One is the slipping channel or wet channel, where you can put a stress to wet for something, and another is the spin lock. And finally, we have a semaphore count, which represents how many resources are available that this semaphore manages, right? So this is the structure, and we have helper functions for you to create a semaphore or initialize it, and then also destroy it. So here we have two interfaces, P, well, this is a word, initial for a word, and the decrement of the count and basically acquire the resource and V. So any questions before? Yeah, not a collection. We don't have one spin lock, right? We have a count, right? Suppose we have five resources to manage. How many spin locks do we have? One. So initially, what's the count value? That's a good question. Suppose there are five resources. What do we do in the semaphore create? Basically, when we initialize the semaphore, what's the initial value for count? Five, right? Initially, it should be five. When I do P, so the basic idea is when I do P, I decrease it, right? I keep decreasing until it reaches zero, at which point I will have to wait, right? When I do V, what do I do? I increase the count, right? Basically indicating that one more resource is available. So that's the basic idea of P and V. Sounds very simple, right? When I P, I minus, minus. When I do V, I plus, plus, right? But as you may find out, it's not that simple. There are some corner cases you need to consider. So let's go to the implementations of semaphore and see what the corner case is. So here, first, the create basically initializes a semaphore. What are arguments or parameters this function takes? What does this semaphore call? The name. And what's the initial count? Initial count is basically how many resources that this semaphore are supposed to manage, right? So we just assert initial count should be positive, or although initial count of zero doesn't mean anything, right? And what's that? Exactly, but that's more advanced topics for semaphore. Yeah, you can initialize as zero and later on you can V it, yeah. So here we allocate the space for semaphore and we set up the name, set up the web channel, initialize the spin log, initialize semaphore count, and we're done. So you need to get used to the style of in C, how do you acquire resources? How do you allocate the memory? We have a destroy first. So we just release every resources we just acquired. For each memory we can unlock, we need to carefree and all that. So these are not minor details. So this is the interesting part. In P, we need to basically we want to decrement the count, right? For now, just ignore this part. The first thing we do is actually acquire the spin log. Why is that? Access what? Yeah, that's more or less. That's right in the sense that so in this case, as far as the semaphore concerns, what's the shared resource? Does the semaphore care what resources do you use between P and V? It doesn't know, right? It doesn't care about that. So as far as the semaphore concerns, what's the shared resource? What's that? Semaphore what? The semaphore itself. It's self. Well, it's more general. I want specifics. What's the shared resource in the case? P function. No, that's not function. What? Yeah, well, what I want is a resource to the semaphore. So what's the resource? Function is not a resource. You can always call function. Now. What's that? I heard something. Yeah. Some count. Yeah, some count. Everybody tries to decrement the count. I need to protect that operation. Otherwise, how do I coordinate between the various users or threads? As far as the semaphore concerns, the shared resource is only one int, the count. As long as I protect the count correctly, I can always ensure the correct behavior. Here, another question is, what's the spin-off I supposed to protect? The count. Now you understand why we have a spin-off inside the semaphore, because the spin-off I supposed to protect the access to the count. Because we want to check the count, which is access or read the count, we need to protect the access using the lock. We acquire the spin-off. After this acquire, I know that I'm the only person now looking at the count. And others will be prevented by the spin-off acquire. Now I'm the only person inside this section, so I check the semaphore count. If it's zero, it's a trick to... This here, we do while it's zero, or you can do if it's zero. It doesn't matter. So, suppose I'm the first person coming to the critical section. What's the semaphore count? It should be positive. Like five, so let's say it's five, so we will not enter this while. So we reach here. So after this while loop, I know the semaphore count is positive. So it's set for me to decrement the count. This is the only operation I really want to do, but in order to do that, I need to acquire the spin-off and check it first. Then I release the spin-off. I'm done. I'm the lucky person. I'm the first one. I just grabbed the resource and I go. So I'm the first user. Now the second user comes. The same thing happens. The second user acquire the spin-off. The semaphore count is four now, and meaning that there are still four resources available. And I decrement the count and continue and so on. So suppose all the five resources, suppose five user has caught P without calling any V. Now what's the value of the count? After the fifth thread or user caught this P function, this should be one. There is only one resource left, and I decrement it. Now it's zero, but I don't care. I already grabbed one. So I continue. Now the sixth one comes. What happens? I can acquire the spin-off. No problem, because nobody is using the spin-off. But the semaphore count exists because it's zero, right? Which means there is no resource left. I need to wait. So now you get an idea of why we use a while instead of an if. Because you may need to check the resource multiple times. So in the most simple example, I'm the sixth user, and nobody else is trying to call P. I'm fine, and I wait here. So I lock the web channel, release a spin-off, because I don't need to care about a spin-off anymore. And here is the question. Why do I need to release a spin-off? What if I go to sleep without releasing the spin-off? What will happen? What's that? Well, I really don't care about the seventh one. As long as somebody before me releases a semaphore, or incrementing the count, I can continue. So why do I release the lock? Give up some lock? Yes, exactly. So in order for the previous guys to release the lock, they needed to acquire the... Release some resource by incrementing the count. They needed to acquire the spin-off. If I go to sleep while holding the lock, then how are those guys supposed to increment the count? So they will get stuck. So in order for them to increment the count, I have to give up the spin-off, and then I'll go to sleep. And when I wake up, the first thing I do is I re-acquire the spin-off. Why that's the case? Why do I need to...? I'm already here. Why do I need to acquire the spin-off? What's that? Yeah, so one rule of thumb is that whenever you access a shared resource, in this case, the semaphore count, you always need to protect it by the lock, either spin-off or later on in some other lock you implemented. Another way to interpret this is that, suppose I'm not the only one waiting for this lock, while I was sleeping, the seventh guy coming also goes through the process and also wet on this semaphore. And when the first guy down with the semaphore and incremented the count, we both get to wake up. Then we need to compete for the spin-off to ensure that only one of them can go back to the while loop and check the count. So suppose there are two guys, the sixth and the seventh guy are waiting for the semaphore, and then both get waked up here. But I'm lucky, so I acquire the spin-off. I go back, check the count, which should be one by now. I only got waked up because somebody else waked me up. And somebody else should have already incremented the count already. So semaphore count is one, so it's good. I jump out of the while loop and decrement the count, indicating here, I'm now holding a while resource now, and I'm done with this PE function. I just release and continue. And that unlucky guy will get stuck here. So after the first guy releases the spin-off, the second guy can acquire the spin-off now. But at this point, the semaphore count is zero already, because I already decrement the count. So unfortunately, he has to sleep again, waiting for some other guy to wake him up. So that's how the acquire process works. Let me just quickly go through the release process before we can discuss this, so it'll be much simpler. So the V is actually kind of simpler than P. You first acquire spin-off, one rule of thumb, whenever you access the shared resource, you always grab the lock. Then you wake up somebody, so your first incrementing the count indicating you are done with the resource, now there's one more resource available, and then you wake up some guy in the wedge handle. This is why we need the wedge handle. We need it somewhere where the further acquires have a place to wait, and the previous releases know where to wake up those guys. So we wake up somebody. I don't really care who to wake up, just wake them up, or wake up one or wake them all. It's the same, and then release the spin-off, and I'm done with this V. So now go back to look at the P and V again. Any questions about this? So everybody understand how P and V works? How you can use spin lock, and how you can use the wedge handle? You need a spin lock because you have some shared resource you want to protect. You use the wedge handle because when that resource is not available, you want to have a place where the stress can slip on. So this is how semaphore works, and it's very important for you to understand how it works before you can continue and implement other primitives. So any questions? What's that? Which we don't care. I don't know. I mean, as long as someone is holding the lock, I cannot, holding some resource, I cannot continue. I really don't know who is holding it. There's no way for me to find out. So now do you have any idea how to implement the lock? I mean the normal lock? So as I explained, in the spin lock case, when you acquire a spin lock, but the lock is already hold by somebody else, what do you do? You keep a wild loop on that spin lock, right? Basically the CPU is busy. Now the assignment one requires you to implement a different version of the lock where you find, where you find the lock is not available, instead of you keep buying the spin lock, you go to sleep on a web channel. How are you supposed to implement that? Do you have any ideas now? That's one way. That's cheating actually. Well, it will work, and I don't know if we can detect that. I think we can. Well, in some private conversations, I have recommended people to use it, but as of now, I will still recommend to implement the whole process. Instead of just using the sample form with initial kind of one, you go over the process and implement the logic yourself. It will help you understand how this sample form works. So in the case of lock, or there's one difference though. Lock has a holder. The sample form doesn't have a holder. There's one interface that lock has, but the sample form doesn't. What is that? Lock do I hold? If you just use the sample form with initial kind of one, you can implement the semantics of acquire and release, no problem. But how do you answer lock do I hold? That's one question to consider if you want to go over the easy parts. So let's see what's already there in locks. So basically nothing. We have a NAM which does nothing and add whatever you need. So by now, you should have a pretty good idea of what you need. What do you need? Spill lock. So you need to protect something, right? What else? What does the sample form has? Wedding channel. So where people would wait if the resource is not available. You said count. In this case, I don't really care about count because count will be always one, zero, one, zero or one. You can have a building. Yeah, that basically can implement what sample form can provide. A sample form with initial kind of one, right? But how do you answer lock do I hold? What else do you need to keep in the lock structure? Some kind of identifier, right? So whoever acquired the lock should put his identifier in the structure. So later on, when I call lock do I hold, I can compare my ID with the ID in the lock structure, right? If they're the same, then I know I'm the holder of the lock. Otherwise, I'm not the holder of the lock. Some kind of ID, right? You need to figure out what kind of ID. You said PID. Well, at this point, there is no concept of PID yet in this OS. In OS 161. You're about to implement it in OS 72. So what else can you use? Again, we don't have a thread ID. Some other things you can use to uniquely identify a thread. I will leave you to figure that out. This kind of the most difficult question in OS 71. After that, you'll be fine. So we need a spin lock. We need a web channel. We need a kind of a count, right? Or Boolean to indicate if the lock is held by somebody else or not. And we also need an ID, some sort of ID to indicate the holder of the lock. That's the information we need for lock. And let's go back to the C code. Okay. So you have this many stuff in the lock structure. Then you should initialize them in the lock create, right? You can initialize a spin lock. You will need to initialize the web channel, initialize the status of the lock as unheld or available, or the ID and the ID. So in lock acquire, what do we do? So go think about a semaphore. What does semaphore does at the first thing? Besides our kind of characteristics? What it does in the first step? What's that? Don't remember? Oh, quite a spin lock, right? Because so conceptually, what do you want to do in lock acquire? Check the status of the lock, right? If nobody is holding it, I'm going to grab it. If somebody has already grabbed the lock, I need to go to sleep. That's the two things you need to do in the lock acquire.  In the case of the lock, what's the shared resource? The status of the lock, either acquired or not. And then after acquire the lock, what do you do? Again, similar to semaphore, you can actually copy pass the most of the code of semaphore to lock. It's okay. Just you need to understand what it does. So you check the status. If it's available, just be optimistic and say it's available. I set it to unavailable. And I release the spin lock. I'm done. I'm the first person ever tried to acquire this lock. Now, what about the second person? Acquire the spin lock. Check the status. Oh, I miss one thing in the first person case. What do I miss? I acquire the lock. It's available. I set it to unavailable. I release. Is that everything? Do I miss something? Ownership, right? I need to indicate that I own the lock. Not just the lock is owned by somebody, but it's me. So I acquire the spin lock, check the status. It's available. I set it to unavailable. I set it owner to me. I release the spin lock. I'm done. That's the case for the first person. Now, in the second person case, acquire the spin lock, check the status. Not available. I sleep on the way channel. But before that, ownership. So we are trying to implement some functions for others to use. It's handy to have a lock do I hold? So suppose I just want to poke the system. I don't want to work there. So I can call lock do I hold to check. Oh, sorry. That's not the case. The case is sometimes you have nested locks, which in example would be in function A, you acquire a lock. Then you call function B. Inside function B, function B may be read by some other third party library. And he will also want to acquire the lock. So it's handy for function B to have a piece of code saying, if I already hold the lock, I don't need to acquire the lock again. So we are writing some primitives for others to use. And it's best for us to provide the full functionality to check the ownership of the lock. So if inside of the nested function B, if I already hold the lock, then I don't need to acquire the lock again. It will be a waste. In the sample form, how do you say who owns the sample form? Are you going to? In that case, will the sample form scale? I mean, if the resource initial kind is 1000, are you going to keep 1000 identifiers? Yeah, because the sample form doesn't have ownership concept, but the lock does. So go back to the second person who needed to do all this. Lock the web channel, release the spin lock, sleep on this web channel. And when we wake up, acquire the spin lock again. And then the rest are quite similar to the first. So any questions on that? Does everybody know how to implement the lock? So we have about 10 minutes left. I'm done with all the contents I need to, yeah. Yeah, yeah, yeah. Inside the spin lock acquire, you will keep waiting there. So when you call spin lock acquire, inside this, this is a function, right? The function is somewhere else. Inside that function, you will keep banning the lock to see if it's available. After this function, you just continue execution, right? Then you sleep outside the spin lock. As far as spin lock concerns, it doesn't really know what you do besides acquire and release, right? So you can choose to sleep in between them. So I guess that's what I need to talk about today. Okay, so this is what we talked about today. And we have 10 minutes left. I'll be here. If you have any questions you want me to check, I'll be happy to answer them. Thanks.