Okay, so it's 5.30, it looks like it's about time to start. So quick introduction, my name is Paul Matthews, I'm a system architect at Bluehost. And first off, let's do a quick survey. So how many people here use RabbitMQ for their messaging system? Okay, Cupid? Okay, anybody using 0MQ? Great, you guys don't really count because you're with us. So today we're going to talk about going brokerless, the basically our transition from a Cupid-based system to a brokerless 0MQ-based system.  The problem you're going to run into is very quickly, if your messaging system's not stable, if it doesn't work, that doesn't scale with you as you continue to grow, you're going to run into major issues with the rest of your open-stag installation. The reason why is because many of the core systems that open-stag utilizes depend upon messaging to be reliable and to work at all times. If we look at some of the systems, for example, Compute, open-stag Compute, uses messaging, if you can't do, if you can't get reliable messaging across, you can't start instances, stop instances, reboot, anything like that. Solometer uses it, cells use it, in fact cells, that is the only messaging system that you can use in our cells. BNC, Neutron, Conductor, and if our messaging system goes away, then all these systems cease to work properly for us. And I know it's not just us that have RPC issues. For example, I was at a Rackspace presentation yesterday where they were talking about their issues with monitoring systems. They said one of their major systems that they had falling over was RabbitMQ and how they dealt with it. So for us, we went with a Cupid solution in the first place. Now a lot of people are going to say, well, heck, why did you use Cupid? It seems like most people use RabbitMQ. Well, for us, we use SinoS and Red Hat based, which means that as a result, Red Hat packages up a lot of stuff for us that we just benefit from. One of these things is of course Cupid and because they package it up for us, we have a high degree of certainty that they're going to be stable, that they're going to be performance tested, that the packages are going to work properly, that they're gonna have security patches backported for us. And that's a benefit that we can use. And a second reason is that Cupid offered the possibility of horizontal scaling. At the time, in earlier versions of Cupid, they had a clustering module where you can have multiple Cupid servers acting in a highly available fashion. So you could have two or more servers that are highly available and you could query any one of them and be able to get a response. Unfortunately, this feature was removed in point one of Cupid and is no longer available. So for us, our Cupid experience, first off, we started with a single instance. And a single instance started to be problematic for us very quickly. We found out that around 3,000 to 5,000 nodes, it started presenting problems for us. Now a lot of people are gonna say, well, wait a second. We have thousands of nodes. Rackspace has tens of thousands of nodes. They're doing it just fine. Well, they're using cells. We have a single cell implementation. So we're not using cells to break anything up. And what we found was is that that single instance of Cupid was not able to scale. We would have lots of problems where messages would fail to go through. Messages would be slow and it caused major problems for us. Another issue that we found is that Cupid connections to Nova Compute were lost. So the only thing that we could actually do to get this to fix itself was to restart the entire Nova Compute instance. And it seemed to be something with Eventlet where the message was not being picked up, processed properly. We never really investigated it very much at that time because we're, at that time, we're already moving on to zero MQ. So a lot of people are gonna say, well, hang on a second. You guys use Cupid. A lot of people use RabbitMQ and have great success with it. Why didn't you go with RabbitMQ in the first place? Well, when we looked at RabbitMQ, we saw that it had the same broker design as Cupid does, which kind of scared us away a little bit because the broker model has a lot of drawbacks. You have a single point of failure. You have a single point where all your messages have to go through, and as a result, that one piece has to be able to scale. And we'd also talk to other members in the community who reported many of the same problems with their own RabbitMQ installation, and as a result, we looked at other things. Now, there are a couple of possible solutions that the community has to scale a broker. First off is cells, and the second is using clustering or availability. Now, first off is cells. The biggest problem with cells, the one biggest problem is they do not directly address any of the performance issues with anything. Scheduler, MySQL, messaging, nothing. All they do is they are, it breaks up your installation into smaller pieces. And also cells have a major issue in that if you're using cells, if I have an instance in this one child cell, let's say I wanna move it over to this one. Can't do that with cells. And we did not feel that's, we didn't wanna be bootstrapped by limitations that cells had. And one of the other things is because of the way that brokers are implemented, where they pass messages from one down to the other, they change services, it can magnify problems as they occur. So for instance, if we have this child cell, and we send a message from our API cell down to this grandchild cell, if any issue happens here on our child cell, the grandchild cell is also gone as well. We can't get any messages through to them. Now on clustering, as I mentioned, we started out with a single Cupid instance. We moved on to a clustered solution. What we found is clustering is extremely slow, extremely unreliable. As you actually add nodes, you actually lose performance. You don't gain it. The second thing is is we, actually using a clustered solution with Cupid, we actually saw more problems than we did with a single instance. Lots of times we would look at the instance during the day. We'd have messaging problems. You'd go look at the cluster and what would be happening is one of the clusters had fallen out, was re-syncing for whatever reason it had problems. And during that time, messages are not reliably passed from one machine to the other. They're not reliably responded to or not responded to at all. Another thing was is that we could never get, if we added a node, if we ever tried to add a node into the cluster while it was actually in operation, that one node would never, ever sync up. Now if we added, so basically what we had in that solution, in that instance, is we had to take an outage late at night, take the entire cluster down and bring the entire cluster back up so it would actually sync while we turned off, keep its messaging services. Now as far as RabbitMQ goes with clustering, it does have a highly available solution, but the problem is is it's extremely complicated. You have to have shared storage, something like DRDB, pacemaker, heartbeat, core async to make sure that everything works properly. There's a lot of moving pieces that can cause problems.  And the bottom line is, is we found that scaling a broker is not actually a practical solution. So what do you do? Well, we decided to throw out the broker. Brokers don't actually scale. They're a single point of failure that everything has to pass through. And so we needed a new solution that would work for us and we had a couple of requirements. First off, we had to have no single point of failure. We didn't have to be dependent. We didn't want to be dependent on a single cluster of nodes, a single service for our entire open stack installation to work. We needed the solution we implemented to be something that was horizontally scalable. So as we continued to grow and scale our installation, it would continue to grow and scale with us. And it also had to be reliable for us. So we moved on, as I mentioned earlier, we moved to zero MQ. And zero MQ has no centralized broker. It's more of a peer to peer distributed system. Basically what you're essentially doing is you're moving your installation from a single broker on a single box to brokers on every single machine. Every single machine at that point gets a zero MQ receiver which will actually receive the messages that are passed to it from other nodes. Now a lot of people are gonna say, hang on a second. This doesn't sound like a good solution. I don't wanna have to have all of my nodes knowing where everything is. I like the idea of having just one instance where everything goes to. So I just have to keep it host. Well, zero MQ handles this very gracefully. It has a matchmaker file which I have a little example of here. If you look, we have two queues. We have the scheduler and console off and then a couple of hosts that are defined. And the matchmaker is able to pass through if you get a request for the scheduler. It passes it through the one of those hosts. So as far as messaging topologies goes, if we look at Cupid or Rabbit MQ, basically a broker based solution, you have a start topology where you have a broker in the center and all of your nodes have to pass messages through it. So not only do you have a single point of failure but also you have an issue where any messages that have to go through have to pass through your broker. Zero MQ on the other hand is a partially connected mesh. Now I say partially connected mesh because nodes only communicate with the other endpoints that they're going to talk to. So for instance, a compute node in the current implementation can't pass a message to another compute node then off to the API or whatever else. Now this could be easily implemented because of the way that zero MQ is written but as it is a partially connected mesh. Now as I mentioned, zero MQ we could program this in. Zero MQ has a lot of flexibility inherent in its design. Brokers on one hand have a very inflexible design. You have exchanges, queues, fan outs, subscriptions and there's not a whole lot you can do with that. If you look at zero MQ on the other hand you have four simple methods. Connect, bind, send or receive and with those four methods we can therefore basically implement any kind of messaging topology that we want and because zero MQ is so simple it uses lightweight sockets. The resource utilization is extremely low and as a result we're also able to pass a lot more messages through at any time. So I did a little benchmark testing at zero MQ versus Cupid and Rabbit on a single core VM and as you can see this is the number of casts per second. More here is better and as you can see zero MQ I guess it's not very well shown here but zero MQ is almost three times as fast as rabbit MQ. Now another thing to keep in mind here is rabbit MQ and Cupid are because they're brokered solutions. This is the maximum number of messages that they're going to pass through the system at any given time. Zero MQ on the other hand you're passing messages from host to host. So that's the maximum amount of casts you could pass from one host to another but that is not the capacity of your entire system because it's distributed. Now people are gonna say great zero MQ sounds wonderful how do I use it?  The next thing you need to do is zero MQ has several different matchmaker capabilities that it has. In most cases we're gonna wanna use matchmaker ring. The reason why is because matchmaker ring it actually so for example in this matchmaker file same one as we used before sets up a hash relationship between the Q and the machines defined in it. So if we have a message that passes to the scheduler the matchmaker file will return one of these hosts. Once that's configured all we have to do is start the ZMQ receiver restart Nova compute or whatever services on the controller and we're good to go. Now as far as a migration process goes we're kind of bootstrapped because of Nova's configuration. Because we can only have a single backend at any given time unless we have some way of breaking up our installation unless we have some kind of logical division there's not a good way that we can change from one RPC system to another. As a result we needed a new solution. As I mentioned before we moved from a single qubit cluster or from a single qubit instance to a qubit cluster. The way we did that is we set up another group of compute nodes and we would move nodes from one group of compute nodes to the next. Now obviously this is not an optimal solution. It means that it's very complicated for us to move nodes leaves a lot of room for corruption and it's very complex. We really have to make sure that everything goes through properly. And it's not something that we wanted to go through again. We needed something where we could well obviously at the time we had grown from about 5,000 nodes to tens of thousands of nodes. And in our particular case where we're a budget hosting provider these are all customer instances. Any impacts in messaging are noticed by them and are not good for our credibility. So we needed to find a way to migrate these instances from one messaging system to the next with little or no downtime. And we needed to be able to do this in a slow roll fashion so we could roll it to small number of machines at any given time, make sure that they were working and then expand that out as we gained confidence in it. So we started working on code looking in Nova and what we came up with is dual messaging backends. So what actually happens in this is that nodes can currently connect to both Cupid and RabbitMQ backends and can use either one depending on which messaging system they receive a message on. It means that we can roll out the code separate from the actual configuration so we can roll out the code and enable the configuration at a later time. And once we enable it either messaging backend system can be used. Now I can probably sit up here and talk to you about how this works for the entire 40 minutes and a lot of people would probably never catch on how it actually works. So I figured the best way to do it would be a more graphical representation. So let's say this here is a graphical representation of our OpenStack installation. So first thing we roll out all the code to all these machines. Next, we deploy our configuration to our controller nodes. We deploy that out, start the ZMQ receiver and restart the services on the controllers. Now what happens is a message comes in to go to Compute One. Now obviously Compute One as you can see is not running ZMQ, just the controller is. Now the way that we determine how we're going to broadcast this message via ZMQ or Cupid the first thing we do is we check to see if the ZMQ receiver is listening to an important 9501 of the compute node. We find out that it's not and so we broadcast that message via Cupid, no problem. So next thing, we decide we need to roll this out to some of our compute nodes. So we roll out the configuration, start the ZMQ receiver. Now a message comes in for the second compute node. The first thing the controller does is says, hey, is that receiver listening? In this case, yes he is and so we broadcast that message out. Now a lot of people are gonna say, well hang on a sec, I have a poor CMS system or let's say for whatever reason I want some of my controllers to run Cupid or Rabbit for whatever reason and the other ones to run ZMQ. Well that's no problem. So let's say we have another controller node here that has a broken configuration system or for whatever reason we want it to run Cupid. If it sends a message out to compute two which is running a ZMQ receiver that compute two will respond via Cupid. So whatever messaging system the message comes in on is which messaging system it will be responded to on. So the actual configuration of the dual backends is very simple. Basically the only configuration switch we use in the code is if the RPC backend is configured ZMQ then the dual backends are enabled. Now obviously this code could be prettied up and have a configuration option. It would be relatively easy to implement. It was just something simple for us to implement and so it's not totally clean but it can be cleaned up very easily. Anyway so the only other thing you have to besides implementing ZMQ is you have to make sure that your Cupid host name is there. It's not gonna affect anything. All it means is that the hosts actually have a back end to be able to connect to for their broker. And again once those nodes are switched over they'll respond to whichever message that whichever backend the message came in on. Now as far as our migration to ZMQ the dual backend code for us obviously meant we had minimal downtime. All we had to do was configure, change the configuration restart the services and we're up and going. The actual migration for us was very smooth. There weren't any major issues with rolling it out. We didn't have any major message outages. And a lot of people are gonna wonder about the connection checks between ZMQ and the remote nodes whether that's gonna cause any noticeable load. We didn't notice any. And honestly the first thing we did was we rolled out the code to the compute nodes so those compute nodes were doing ZMQ connection checks to every single node all the time. And we saw no noticeable issues. As far as ZMQ in production now that we're using it it's a lot better than Cupid or than Cupid was for us. It works wonderfully. It's more reliable for us. We're not losing messages all the time anymore. It's a lot faster and allows us to, it's allowed us to scale our open stack installation further than we were before. Now I wish that I could say that there were no issues with anything that we had dancing unicorns and rainbows in our data center but unfortunately I can't say that. There are still some lingering issues with moving to zero MQ. The one issue that we are seeing and fortunately it's very rare, it doesn't happen very often is that the ZMQ receiver receives a message, processes it but Nova actually doesn't consume it. Now in talking to some of the developers at the conference here we think we may have found the issue. It may be related to a bug that is known and has a fix for it but has never been pushed up to mainline. So hopefully that's fixed for us and that would be wonderful. We don't really know that yet though. So a lot of people are gonna be wanting to switch over to ZMQ possibly wanting to look at this code. So there it is. There's a link on GitHub. You can go ahead and use it and finally any questions. Do we notice any issues with the ZMQ driver? None that we have seen. I mean as I say it works for us. It works a lot better than KUPD ever did. It's a lot of the scalar installation and we haven't noticed any larger issues than there were in KUPD. Yes. Yeah, so the question is as far as the dual back end code after it's no longer needed can you switch back and answer is yes. Basically it's only something that you need during the transition period. Once you've switched over then you can just switch over to pure ZMQ and you're done. You don't need to keep it any longer or obviously you can retain it. I mean during our transition phase it didn't cause any issues. So I wouldn't see any issues with maintaining it in production but so how does it work? How does it work? How does it? Redis? Mm-hmm. So currently in the web there is a matchmaker. Mm-hmm. There is some of the installation issues. Mm-hmm. Now the question was with Redis and ZMQ. Now I know there is a Redis back end that you can use. We just used the matchmaker file which is just JSON. So no issues there. I can't really address that because we didn't use it. Okay, go ahead. Yes, go ahead. Which what? Which tool? Did we use for what? Basically I just monitored how many messages were being passed through. I mean nothing complex. Those were against Folsom. All right it looks like we're out of time so thank you very much.


What's up everybody JC over Jaspies case for East comm 2020 hip parade baseball platinum edition series 1710 box hobby case break Ransom number one just sold out and one incredible autograph per box They had numbered a hundred boxes loaded with stars and Hall of Fame's and one hip per box So high risk high reward though featuring Mike trout all the way down a clean kershaw and many more So you give one random team here the customer names here are the teams. Good luck. Let's roll it and it's a full 12 six and a six one two three four five six seven eight nine ten 11 and 12 Adam gonna Chris 12 times one two three four five six seven eight nine ten 11 and 12 Orioles Down to the Marlins. I was gonna say Orioles Adam with the Orioles DJ with the A's Aaron you have the Yankees Rick with the Nationals James with the Rays Jeremy Porter You have the Rockies Adam Wilson with the Phillies Oliver with the Royals Eric with the Giants Logan with the Mets Anthony with the Red Sox DJ with the Angels Adam with the Texas Rangers Blake with the Braves Chris with the D-backs Joshua you had the Tigers last spot mojo Robber with the Cubs Logan with the Blue Jays Chris with the Astros Aaron with the Twins DJ with the Cleveland Indians Justin with the Reds Daniel with the Mariners and Pirates Aaron with the Padres Spiro with the Brewers Dan with the Cardinals Spiro with the Dodgers James with the White Sox and Chris with the Mammie Marlins So again, no technical technically no Checklists, but Of course some of the featured hits you can get out of here. And yeah, usually Yeah, one of these cards will actually be in one of these cases, I believe So hopefully we get a nice one and again Use your imagination guys. It could be a lot of different hits in here for all these teams You know since is that a repack product at least one his represented for every team. So Tray window open Logan saying Mets for trade and then Daniel trying to trade the Pirates for the Indians Let me know guys got a handful of good orders here for the packed filler for chrome baseball Remember that sells out the baseball break as well. We're done to 17 left now That was the last like six orders guys packed filler for baseball. Let's get that jumbo done early guys I'll take about an hour or so that could be the break right after Chronicles fat pack so let me we got the hit parade right now we got Mosaic sell a pack that helps fill up dominion dominion is a pretty quick break after that would do the chronicles fat pack to give away some mixer spots and Then after that we can probably squeeze in that chrome jumbo now, I don't think anybody's got any spots in the basketball mixer. So if Nick hasn't already he might turn that into a filler So pie after this break guys if no more mixture spots, so that we can turn that into a filler And that'll be the last one we do Since no one's grabbed any we left you we left you guys some good time right there To not turn it into another filler, but I'm closing the trade window guys. Sorry. No one wants to trade I guess our way. No, oh That's Daniel trying to squeeze in a trade. Let me know not I'm closing it Pirates for Mets if not, I'm closing it All right. No, thanks Close case two out of ten. All right first one Wow, it's a Nolan Ryan autograph Texas Rangers edition from finest baseball not numbered There you go Nolan Ryan Rangers That is going to Adam Wilson. Oh, is that bow Jackson Kansas City Royals? Look at that Oliver I'll make you feel better, right? this heat wave 41 out of 50 Jackson Actually, I didn't even know she called it Oliver would be nice to see a bow Jackson on them. Very nice Sick, it's a bowman's first of Clark Schmidt Little blue wave to 150. Oh Dallas already taking the lead. I don't want the Vegas Golden. I said that's Screw them. Excellent. Excellent Wow, it's Louise Robert high tech man. I didn't know he wasn't high tech 2000 and I Think 18. Wow Chicago white sauce going to James Connell. Oh, Louise Robert And not numbered but bowman high tech pretty nice White Sox and Louise Robert and all those guys over on the White Sox are just rolling 13 out of 100 Ryan Sandberg 14 out of 15 for the Cubs. So when you get a white dog get that have to have a cup, right? Robert throne Gryffy would be nice Daniel. I hope so Be nice. It's Cody Ballinger 6 out of 25 No, this one 2017 so that is technically a rookie Cody Ballinger from flawless Dodgers, it's going to Spiro. There you go, man Very very nice And Nolan Ryan is very nice Box one one out of a hundred Craig B. Gio Look at that eight out of ten one two three color patch for color patch actually call it Old school dynasty right here 2014 right 2016. Sorry Very nice Houston Chris Walker All right, three more boxes guys degraded nine five Nick sensual and it's a one of one majestic tag One of one. It's a nine five ten. Wow that actually get a nine five ten an inception That's pretty good and it's a one of one That part of the cell sheet that is a cell sheet. Hey, there you go. Very very nice and Justin with the reds Ten is not bad Very nice. All right, two more. I have new roachman. There you go From Bowman chrome Mega ray 2020 very nice Baltimore Orioles going to Adam Wilson This has been a good case guys Very very nice Last one box 43 out of 100 And it's a Pete Alonzo Logan was trying to trade the Mets Try to trade couldn't trade. Oh wait. No Logan wasn't trying to trade the Mets Logan's was trying to trade somebody else wasn't it? Where's it at? Oh, yeah, Logan was trying to trade the Mets. There he was There you go There you go. Little rookie from finest. There you go everybody. That was the break Pete Alonzo, Adley, one-on-one Nick Santel, that's a cell sheet, Craig Bijio, Rookie Cody Ballinger, Ryan Sandberg, Luis Roberts, Clark Schmidt, Bo Jackson out of 50, and Anil and Ryan. Not a bad case guys. Again, this was Platinum Edition Limited Edition Series 17 on Jasper's Case Breaks.com. One more hip parade break on the website if you guys are interested guys Basketball. It's a super high-end one sapphire. Down to 15, we can definitely get that going guys. Jasper's Case Breaks.com


Stop dealing with them, stop worrying about the triggerings that they bring and just try not to deal with them at all. Love you guys, cheers.


Okay, so we know that one of the powerful things about a chemical equation is that it allows us to make predictions about amounts of chemicals. For instance, in this hypothetical reaction we know that if we have two moles of A we will need one mole of B to react completely with it and that when that has happened we'll have three moles of C, the product. But no one has a setup in their lab that automatically measures moles. Design project for you, come up with one that does. What we do have generally are setups to measure mass and volume. So in order to make predictions that are really useful and measurable we need to convert our mole predictions into mass or volume predictions. Happily we already have a strategy for doing this. You know that it's possible to convert moles of a substance into mass or number of particles or volume if it's a gas. The conversion factors are either a proper constant like Avogadro's constant or a constant under defined conditions such as the gas-molar volume or can be calculated from information on the periodic table like the molar mass. So what we need to do is combine this skill with our understanding of mole ratios so that we can move freely between quantities of various reactants and products regardless of what unit we're measuring in. So let me take this conversion map and rearrange it slightly. I'm putting it all over on the left here and I'm going to specify that I'm talking about one particular chemical. Let's just label it A. Then I can reflect the map over to the other side of the page for another chemical B. So on the left hand side of the page I have the conversions that will let me move between mass, particles, volume and moles of A and on the right I have the same thing for B. And how do we relate A and B to each other? Well if they're both involved in a chemical reaction and we can write the equation for that reaction then we know the mole ratio in which they react, the stoichiometric ratio. So what we've done now is summarise what we know so far into a map and I'm going to honour Aaron Sams and Jonathan Bergman here who are the chemistry teachers in the US who came up with the idea of flipped learning in the first place and I'm going to borrow their name for the map which is called the land of the mole. So what this diagram does is map out the calculation path that you would take for any given stoichiometric problem. For instance, if you had a certain mass of reactant and you wanted to know what mass of product it would give you would convert the mass of the reactant to moles, you'd use the mole ratio to calculate the moles of product that would be produced and then you'd convert the moles of product into a mass. Quick tip for you, the most common conversions that you're going to need are the mass mole conversions. You do need to know how to do the particle and volume conversions but in terms of calculations that you're most likely to need as you work in the lab, the mass to mass calculations will be far and away the most useful.


Hello everybody Welcome to a quick little supplemental for a lecture from last night I didn't quite get through all of the topics I wanted to and so I thought I would record this just to help out a little bit maybe for for your laboratory number one and putting do their project one design docs so what we were talking about yesterday was Concurrency and mutual exclusion and we're sort of starting that whole process of how to get synchronization to work properly And I just wanted to finish up that discussion If you remember we sort of introduced this issue that well threads Can give us the ability to have Overlapped from IO and computation and therefore seem like a really nice Efficient way to have multiple things happening at once We run into an interesting issue. So I had introduced this Banking Example where for instance what we did on a deposit was we would get the account information We'd increment it because maybe we were doing a deposit and then we'd store it back and the reason threads were really going to help us out here is because if one user was You know their account was stuck waiting for disk IO another user could be adding to the balance or whatever And so this was our motivation for going to threads except as you see here the threads Encounter the fact that the accounts are shared state and so in this particular instance We show an example here where perhaps thread one gets the balance and then thread two gets to run and it grabs the balance increments and Stores it back and then thread one gets to run again and as a result The whole operation that was thread two is erased because thread ones Overwrites it and if you remember I talked about the malicious scheduler viewpoint, which is you need to view The fact that there there's a malicious Murphy's law scheduler running anytime you have multiple threads working on the shared data that will find a way to Find that sequence that corrupts your data and it will do so at the worst possible time. So in this instance our Malicious scheduler found a way to split up thread one and thread two Okay, and exactly the wrong times now What we clearly need to do is we need to put an atomic section in here Which may basically says that three instructions load add in store all become atomically bound together and can't be interleaved Okay, and so to do that we talked about locks and locks have come up earlier in the in the term as well And a lock is in general prevents somebody from doing something Excuse me and in the context here you imagine locking before entering a critical section Unlocking when you leave and waiting if something's locked and so the important idea that You ought to get from these lectures on synchronization is that pretty much all synchronization problems are solved by waiting So if you look back to our bad example here The fact that thread one started doing something and then thread two popped in and screwed everything up And then thread one got to go again if thread two were to just wait Until thread one was done with this atomic section. We would have resolved this particular bad behavior. Okay, and so all Synchronization problems can be solved by waiting and the trick is to wait only as much as you need to not too much And we'll talk a lot about Examples where you wait too long and of course when we talked about locks yesterday. I mentioned the fact that you need to Allocate and initialize a lock so you could for instance on the left here You might declare a my lock structure and run a lock in it on a pointer to it or on the on the right side You might declare P thread mutex T and then initialize it in one way or another that depends what on Which type of locks you're using but then once you've done that the locks provide a couple of atomic operations One is a choir which you know For instance in C syntax would take a pointer to the lock you're acquiring and when you do that You're wait until the lock is free and then you Grab it and if you try to acquire the lock When somebody else has marked it as busy then you wait and wait in this context is going to mean your thread Is put to sleep so you're not wasting cycles and we'll talk about that in the next lecture and Then when you're done you release the lock which will then free up potentially somebody who might be waiting and so Looking at our banking problem again. What you see here is we identify the critical section So a good critical section here is the fact that we want to have an atomic sequence of this getting of an account incrementing and storing back and we Decorate around it the acquisition and release of the lock And so we acquire the lock at the top and we release it at the bottom and by acquiring and releasing a lock What we've done is we've ensured that only one thread gets to run at any given time in the critical section And that's what we call Asserting mutual exclusion and so just to show you that a little graphically here. We've got an animation Here's the critical section with an acquire and a release and if you have multiple threads that are all trying to get into that critical section So say here thread a b and c what happens is only one of them gets the lock and the other ones Are forced to wait so for instance if thread a is the one that gets the lock What that really means is not only do they mark the lock is busy, but they're allowed through the acquire operation thread b and c are Waiting in a choir. So they their threads the acquire System call or whatever it happens to be we'll talk about many options starting next time They will be waiting there. So they won't emerge from the acquire yet Okay, so that again looking up top here if multiple threads all call deposit at once Only one of them will actually get through the acquire and into the critical section The rest of them will be waiting in the acquire Function call or system call and so what I show you here is that as soon as a exits Then b is allowed to go through and then as soon as b exits then c is allowed to go through And what ordering do things come through the acquire operation? Well, unless it's a special type of block where the semantics are explicitly specified You have to learn Assume that there's a non deterministic choice as to which of the threads that are all waiting on the lock are allowed through it Any given time the important part however being that only one of them is allowed through Okay, and to Circle back and finish up this example in order to make this really work The it's the account that is the shared data here. And so we need to make sure that all All code that accesses the account is protected by the same Lock, okay, so for instance, there might be a Withdraw here or there might be a An initialize Or some other account operations We need to make sure that they all use a lock From an acquire release around a critical section and in particular they need to use the same lock Now some definitions that we had last time last night as well So synchronization is basically using atomic operations where an atomic operation is a sequence of non interruptible Uh, non interruptible instructions to ensure cooperation between threads to make sure that we don't get undefined behavior Okay, and mutual exclusion is the technique that we talked about here where by putting locks around a critical section And making sure that we exclude all but one thread at a time through that critical section Then we can make sure that we have an atomic operation there and that our synchronization works Okay, and so that critical section is typically the piece of code That's being protected by an acquire and release of a lock And uh, we put locks around it to get mutual exclusion to give us our synchronization Okay Now here's another concurrent program example You got two threads a and b they compete with each other one tries to increment the shared counter the other tries to Decrement it And then we've got this kind of a free for all the thread a and thread b Show here. Uh, we have uh, basically they're sharing the same variable i so in this instance It's a global variable, but thread a sets it to zero and thread b sets it to zero So they're both setting the same shared variable to zero then We're in a while loop and sort of while i is less than 10 for a it sort of increments i and b says well while i is greater than minus 10 it decrements And uh, whoever wins gets to say a wins or b wins, okay And we're going to assume that memory loads and stores are atomic But uh incrementing decrementing are not atomic and so from that standpoint There's no difference between i equal i plus one and i plus plus those compiled of the same underlying instructions Which is a multi instruction sequence. Okay in most cases Um and so what happens here is uh, well either of them could win and in fact, we've got kind of A funny scenario where it's not even guaranteed that anyone can win. Okay, because um, if you look at Uh a hand simulation of this example We could look at the inner loop and here we have the example thread a and b thread a Might load from wherever i is and into register One which maybe it's got a zero there thread b does the same thing. We got a zero remember we initialized i to zero and then thread a basically adds one to it and meanwhile thread b Subtracts one And how could we get this perfect interleaving? Well In this perfect interleaving could happen if we have two Two cores that are running or maybe we have hyper threading which we talked about last night as well And then of course thread a goes ahead and stores a one Because it added one to zero and got one but thread b now stores a minus one and notice that because of this interleaving thread b Ended up completely overriding the result of thread a so thread a went to all this trouble and then nothing happened Okay, because thread b overwrote it. So this is clearly a failure of atomic sections You know and you can imagine this race and where off a gets off to an early start b says Better go fast and tries really hard a goes ahead and writes one then b goes and writes minus one and a says I could have sworn I put a one there Okay, this is uh indicative of the types of problems that happen when you've got data races going on Data races. I'll show you in a second here is basically two threads attempting to access the same data So that's basically this memory location m of i Where one of them's a right and here we have a situation where Two of them are rights. Okay, so that's a data race and the notion of simultaneous Is really defined even when you only have a single cpu and you can't have simultaneous execution Like this shows here in this example above but the scheduler could switch out at any time so you have effectively have all of the Liabilities as if you had simultaneous execution So this may be concurrent but not parallel But it still behaves badly even in those instances. Those are race conditions So we could pull out our locks now and we could say well here. I'm going to put a choir and release around the Around the increment or decrement and now did we do better? Okay Well here now we no longer have an example where a thought it was incrementing but ended up Doing nothing because b overrided overwrote it because we've got locks So thread a gets to the acquire first and it's busy incrementing then thread b gets to acquire It's going to have to wait until a is done Then it'll release the lock and then b will get to go through the acquire and do its decrement So each increment and decrement operations now atomic That's good. Okay And in many cases This might be what you want Technically, there's no longer any race condition here because it's never possible for thread a and thread b to be simultaneously accessing I When one of them's a right and why is that? Well, because the simultaneous access Can't happen because the the locking is going on here. All right, but Um, the program is still broken potentially Um, because this is uncontrolled. Okay, uh a and b are just incrementing decrementing incrementing decrementing There's really no Control as to how many loops there are or who wins and so Maybe technically you've gotten rid of the race condition in the middle. Although there is this Looking at it in the wild loop. So I suppose maybe you could still call it a race condition But it's probably not really what you wanted This is really still a bad program The one instance where you might want something like this not with this loop But maybe the i equal i plus one with a lock around it Is for instance when you might have a hundred threads that are all working on some part of a problem And each one of them wants to get a unique number once it starts then they could call An atomic section like this which Does an i equal i plus one and returns the result back to the caller and now each of the threads Some thread will get one from some thread will get two some thread will get three some thread will get a hundred If you do that then this could be an okay use Of something like this And it turns out actually there are atomic instructions that don't even require you to do the lock and unlock in those instances So one more locking example Here is this red black tree that we talked about in one of our early lectures And i also mentioned this last night and in this instance This tree is balanced in a very special way that the red black Algorithm maintains Okay, as you're inserting and deleting elements and if we allow uncontrolled Access the molten 80 or race conditions to to screw up the structure of the tree Then it's not going to work properly anymore. It's not going to have the level of balance It's supposed to have and so what we can do is we can put a single lock at the root and Just make sure that before we touch the tree at all we acquire the lock Here for instance insert the number three and then release it Maybe over on thread b we could we want to insert four we could acquire the lock Insert release maybe want to get the number six we could acquire the lock search for six and release and what we've done is by putting Acquire and release of the same lock around all operations. We make sure that at most Only one thread is ever manipulating the tree Okay, and so our critical sections are Anytime the tree is accessed Either read or written we put locking around it and therefore we make sure That the correctness of the tree algorithm is as good as a uniprocessor non multi-threaded version okay, and so this is A good use of locking even though the threads are busy adding and removing things In this instance it makes sense because the different threads might be grabbing data from the network somewhere adding it to the tree Searching because of some network query looking in the tree, whatever Deleting from the tree that makes some sense if we have all of these threads doing parallel operations And we make sure that the tree that's at the core of that algorithm is stable Okay, and So this makes sense You might say this is a little slow because if you have a lot of threads Maybe most of them are waiting in the acquire of their you know of their operations and so Maybe most of the threads are waiting and so then you can start to ask a question Is there a way to make this faster? While the answer might be yes That answer might be while you lock a certain path in the tree So you put a lock on every node And when you're searching or you're modifying then as you go down the tree You lock the nodes so that anybody else who tries to go there Doesn't encounter the same locks that you do they might be able to work in parallel You got to do that very carefully. Okay Um, for instance, if you always start by locking the top lock and then work your way down Then of course you haven't gained anything so that while there are ways to do locks on Lots of nodes in a tree like structure in a way that keeps the Keeps the data structure consistent under a variety of different simultaneous operations You have to be very careful to do it So this idea of putting a single lock at the root Hopefully makes perfect sense to everybody. You know for a fact that that'll always be consistent the moment you start trying to Parallelize this and allow more than one thread Modifying and into the tree at a time then you got to be really careful And you can start talking about maybe somebody who's reading Does some advisory? Um It does some advisory locking that's all about reads just so that if a writer were to come along They are not allowed to touch the part of the tree that the writer Um that the reader is in and maybe that's an okay way to get some parallelism But I just wanted to warn you that if you go down this path, you got to make sure you're careful what you're doing okay enough on that Let's ask ourselves if locking is going to be the general answer. Okay, and I'll tell you right now. It's not Locking is a way to do synchronization and it's a way to ensure critical sections It's not always the easiest thing to do. So let's look at this producer consumer idea where we have a buffer that's finite size and we may have many Producers of data that want to put the data on the buffer and many consumers And the producers Can produce things and the consumers can consume things running perfectly in parallel And all that we really want to do is we want to make sure that if the buffer is entirely full then producers are put to sleep uh, because they can't put anything in a full buffer and Similarly if the buffer is completely empty then a consumer gets put to sleep because it can't take anything off of an empty buffer So we want to make sure that there's still correctness here Okay, and we certainly don't want the producer and consumer to have to work in lockstep So, uh, we want to do something That's a little more sophisticated than every Uh producer or consumer first grabs a lock That's associated with the whole buffer and then releases the lock. Okay, that's going to put us in that same problem That we kind of saw with the tree data structure. So what are we going to do? Okay, and there's many examples of producer consumer. We talked about pipes Which i'm loosely showing you here with my gcc compiler example Where the c preprocessor and and the first and second phases of the compiler than the assembler and then the loader All feed into each other and one produces results that are forwarded through a Buffer to the next to the next to the next that's a great example of this bounded buffer The example i'm going to do here just because it's fun is a coke machine The producer can put in only a limited number of coke bottles because the machine only holds so many the consumers can't take Coke bottles out of an empty machine. And so, um, what do we do? Okay, and examples other examples are web servers and routers and you name it this bounded buffer is a good example Okay, so here's an example of a circular buffer data structure where we have a right pointer and a read pointer And we set this up so that um the read pointer kind of points to The next thing to be read off the queue And if you keep reading you'll circularly wrap around And if the if the read pointer ever runs into the right pointer, then it knows that there's no data there And similarly if the right pointer ever runs into the read pointer, it knows that things are full Okay And so, uh, the you know the start on this is there's a buffer structure There's two integers a right index and a read index and then there's an array I'm roughly saying, you know of some type star entries that's a buffer size And notice that this is not a valid c code. Obviously, you can't say Arrow type arrow, although you might in some other language And so we might ask some questions. How do we know if it's full on insert or empty on remove? And what do you do if it is? You need to put threads to sleep Put the producer to sleep or the consumer to sleep And what do we actually need for our atomic operations? Okay, so this is a clear question That comes up based on what I said there earlier. And so, uh, here's our first cut Okay, we'll have a mutex which is a lock on the buffer. It's initially unlocked And the producer might do something like this. They grab the lock They sort of spin in a loop saying well, well, the buffer is full Don't do anything. Okay, because remember a producer can't put data into a full buffer And then once it's no longer full we in queue An item on the queue and then we release the buffer lock And then a consumer looks similarly where we acquire the lock on the buffer We wait and as long as it's empty, nothing happens. Otherwise, we know that it's not empty. That means we can dequeue And then we're going to release the buffer lock When we're done and return the item Okay, and so notice that what we've got here is When the producer can't put anything because things are full, we're going to spin And when the consumer can't get anything because it's empty, we'll spin And so that's the weight, right? So remember I said all Synchronization problems The solution has some form of waiting This looks like this helps us. Okay But Not so well if you think about it because look at this the producer Acquires the lock and then goes into a spinning weight loop Then they have the lock acquired and they're in an infinite loop, which means they're waiting for the buffer to Get emptied a little bit except that if a consumer comes along It's not going to be able to acquire the lock because the producer's got the lock So this consumer is going to go to sleep waiting to acquire the lock forever And this producer will be spinning forever and we've effectively got a deadlock here Okay, so or it's really technically a live lock um, but it's a live lock that can't resolve and so This is uh, not a good solution So we got to do something else. Okay, so here might be a solution Uh, and if you notice what's different here is the producer acquires the lock And then says well if the buffer is full i'm going to quickly release and then reacquire the lock And then check again and release and acquire And so notice and the consumer's got a similar idea here And if you notice why is this better? Well, this is better because Let's suppose that the producer is trying to put something on a full queue They first acquire the lock. They notice the queue is full And at that point they release the lock Okay, they reacquire it and then they check again and they keep doing that over and over again until the buffer is not full And then they continue and the reason this works Not very gracefully and not very well is that the consumer Let's suppose that things are full. So the producer acquires the lock notices. They are full The consumer comes along and yes, it could acquire the lock or try remember in our last example They couldn't because the producer was holding the lock but the if the consumer comes along and goes to sleep sleep in the acquire then um The moment that the producer says oh buffer full release It releases the lock at which point the consumer comes out of the acquire and now it has the lock Okay, and it's going to notice probably that the buffer is not empty because we know it was full And then it can dequeue and go on and so that release Is actually going to release and let the consumer go and this reacquire will potentially temporarily go to sleep Until the consumer here Finishes dequeuing and then releasing at which point will come out of the acquire We'll notice the buffers no longer full will enqueue and go on so surprisingly This works okay, and this actually Works in a variety of circumstances, but it's not great because notice that we're we're burning a whole lot of cycles So if there are no consumers what happens with the producer that's Encountering a full buffer is it's busy running release acquire release acquire as fast as it can And it's wasting cpu cycles to do nothing. So this is a form of busy waiting Okay And so this isn't really going to help us much now you almost you you might also ask well, will this work on a single core? uh, and the answer is well if you think of the idea of trying to acquire a lock when You know when somebody else has it as you got to go to sleep Then what happens there as we go into the scheduler we talked about last night And in that scheduler at that point we effectively relinquish The lock excuse me effectively relinquish the cpu and at that point we Somebody else gets to run which could potentially be the consumer in which case if they're ready to run They'll dequeue and then when we get to run again, we'll acquire the lock and enqueue So this is actually going to work on a single core and it's also going to work on a multiple core But this really is wasting a whole bunch of cpu time. So this isn't great either And uh, so what else are we going to do so notice that If we actually go to sleep in an acquire, we're not wasting cpu The problem with this solution is we're spinning Where we're if there's only the producer a single producer and the buffer is full Then we release and acquire and release and acquire and we just keep going wasting cycles forever And uh, those cycles potentially could be used by some other Code that ultimately becomes a consumer which will resolve the producer and we call that a busy wait Talk about that uh next time on monday so That's this little busy wait symbol Okay, we're waiting. We're waiting. We're waiting. We're spinning. We're spinning. We're wasting cycles Okay, so we need something else and this is really just indicative of the general problem that locks while they're generally powerful enough to do pretty much anything aren't quite the right High level api to do what we want. So we would like a way to do something like this That lets us do a better job of managing resources Um Than a lock. Okay And so higher level primitives and locks we're going to talk about a couple of them Uh as we move forward in the next couple lectures But we can ask ourselves what the right abstraction is for synchronizing threads that share memory now clearly we said that a lock could be Used in a way that allows us to share memory under a wide variety of circumstances But uh, you have to admit that this particular Spinning code here is not all that intuitive and certainly isn't all that Good use of resources So maybe we want something else and we want something as high level as possible where I think of locks as lower level Okay, and so good Primitives and practices are going to be very important because the easier the code is to read and understand The more likely you are to have it correct by design um And so this is important Okay, and it's really hard to find bugs in Multithreaded code that shares data and uh, unix, you know different variants of unix are pretty stable now But it was very common That um unix systems would just crash every week or so because of concurrency bugs and that was just what people accepted okay So synchronization is a way of coordinating multiple concurrent activities and um, we're going to talk about In the next several lectures different ways of synchronizing that are a little bit more intuitive and more likely to be correct Okay, so that leads us to semaphores, which is the topic I wanted to get to today in this special segment And if you remember I met I introduced semaphores a bit, uh A couple of lectures ago, but a semaphore is a kind of generalized lock The term comes from these, uh traffic symbols that you see on railways Okay, and it's the main primitive used in the original unix. It's also used in In pittos and several other operating systems as well And a definition here is that a semaphore Has a non negative integer value and supports two operations one which is uh down or p Is the is the uh standard thing to think about which is an atomic operation that waits for the semaphore to become positive and then decrements it by one And notice for instance, I said here that it has a non negative integer value So that could be zero or or higher And so what down or p does is it waits for the semaphore to become positive So if the semaphore is zero and I execute down I wait And that waiting is one where I go to sleep. It's not a spin wait or a busy wait Okay, and then the moment that it becomes non zero Okay, or positive it then decrements by one and and exits the down or p operation Okay, and then up is sort of the opposite of that which is an atomic operation that increments the semaphore by one And if somebody's sleeping on p, uh, it'll wake them up Okay, and that wake up then will try to decrement by one and if they succeed then one thread will get out Okay, and think of this as a signal operation think of p as a weight operation and p Stands for proberan and v for ferrogan, which is proberan is to test and Ferrogan is to increment in dutch, which is where dykstra named these from Okay, so semaphores are just like integers except While one there's no negative values. So there are whole numbers Two only operations allowed are p and v. So you can't actually read or write the values except initially Okay, so you set it to an initial value and then your only interface is p and v And the operations are atomic. So if you have two p operations on two different threads There's no way for them to decrement below zero So those whatever the implementation is and we haven't gotten the implementation yet It will ensure that there's no way for the semaphore to ever get below zero And for instance a thread going to sleep on a p won't miss a wake up from a v So it won't be the case that there'll be a thread sleeping with a p operation But the semaphore itself is one or more. Okay those that uh interface is ensured because p and v are atomic Now posix actually has a semaphore that gives you the ability to read the value After initialization, but technically this is not part of the proper interface Okay, so the proper interface of semaphores have Only p and v after you've initialized, but if you use the posix versions you can read the value as well So the semaphore as I mentioned is from the railway analogy Here is here's an example of a semaphore initialized the two for resource control So this is going to start looking a little different than just locking. So here's a semaphore Here's two tracks and a value of two basically says that we're going to only allow two Trains into the train yard switching yard at once. So when the first one comes along It's going to come along the track and execute a p operation on this semaphore taking its initialized value of two down to one And uh, we'll go from there. So if you notice that first train came along it executed p That succeeded so it got to keep going the next train that comes along will execute p and now the semaphore is equal to zero But that second one succeeded It's only when the third one comes along and tries to execute the p operation that it gets stopped on p So this train here basically executes p and the p hasn't returned yet okay Or the down operation as it's said in some some interfaces hasn't happened yet So what would make it happen? Well when the train exits and executes v Then it's going to increment The uh, so the v operation is going to increment the semaphore and then that incrementing will wake up Uh, somebody's sleeping on the p operation at which point they will decrement back to zero and get to go So if we let the train go this guy increments quickly to one then decrements and now we're back to where we were So what's different here is that we have this idea of more Uh resources like two here. This is basically giving us a way of enforcing the fact that there's only two things that are in this Rail yard. Whereas if you think about what? A lock is about mutual exclusion that allows only one thing into a critical section. Okay, so this is allowing two or more Okay, so there's at least two uses of semaphores. One is mutual exclusion Which is also sometimes called a binary semaphore or a mutex Which is really used, uh, like a lock Okay, and that's why if you look at how do you make a lock in? POSIX they actually call it a mutex. So a mutex in a lock or a mutual exclusion Uh device is essentially a lock Okay, if I set the initial value to one And then I say, uh, I try to do a semaphore p on that semaphore The first one that comes through will decrement it to zero and be busy doing the critical section Any others that come through will now in a counter the fact that the semaphore is equal to zero and won't be able to get through And uh, and therefore they will not be able to go forward Okay Now another use of semaphores is a scheduling constraint So for instance, we saw earlier with the train the idea that we had a scheduling constraint of two Uh items that could be in the rail yard maximum Here for instance, if we set the value to zero of the semaphore Then we get this idea that we can allow a thread to wait for a signal So thread one waits for the signal from thread two What happens is thread two will schedule thread one when the event occurs So here we go. This is kind of like we set the semaphore to zero And then join Basically says, well, I'm going to try to do a semaphore p on the semaphore Assuming that this starts out at zero. That's my initialization Then the thread join operation is going to sleep because it's waiting for that semaphore to become non-zero And then as soon as another thread finishes That will increment the semaphore which will take it above zero Which will wake up the thread join and will get exactly the same behavior as this thread join Okay So revisiting the bounded buffer here for a moment What we see is that we have correctness constraints So the consumer has to wait for the producer to fill buffers Okay, or in the case of thinking about this as a coke machine the You know, you're a student you go to the coke machine. There are no Coke bottles in there. You got to wait. Okay. I don't know. Maybe it's really late So you take a nap in front of the machine until there's somebody to fill the coke machine The producer or the guy bringing the coke bottles has to wait for the consumer to empty the buffers So if they the delivery guy shows up and the machine's full In the in the instance of what we're talking about here for a bounded buffer They're forced to wait until somebody buys a bottle of coke and then they can put another another coke in so we have Two correctness constraints, which are About resources the consumer waits for the producer to fill buffers The producer waits for the consumer to empty buffers and then one more constraint Which is a mutex constraint to make sure that we have correctness on our queue itself And don't have bad behavior And this is going to be just like a lock and it's going to be needed for the same reason We needed a lock at the root of the red black tree in that earlier example Which is for correctness. We want to make sure that the queue doesn't get screwed up Okay, and the reason again, I just said this but we need that mutual exclusion Is because you know computers are stupid And if you have multiple threads both trying to manipulate the the reader and the writer Part of the interface then you're going to get You're going to get bad inconsistent behavior and there might be other more complicated things in this instance Maybe the input puts things into a heap and the output takes the One with the smallest value out of the heap So there's many instances of this bounded buffer That you could think of that are more sophisticated than just FIFO All right, so general rule of thumb you got to use a separate semaphore for each constraint So we have a semaphore for the full buffer constraint a semaphore for the empty buffer constraint and one for the mutex So that's three semaphores And we're going to start out with no full slots because the machine is empty We're going to start out with uh 100 empty slots because the machine is empty And the mutex we're going to start out with it set to one Because uh we're interested in uh using this as a lock or a mutual exclusion And so then our code is pretty simplistic and set straightforward. So the producer Comes along and says oh, let's first execute a semaphore p on empty slots So what this says is if the number of empty slots is Uh zero because they're the machine is full. We're going to sleep here At that semaphore p Okay, so the producer can't actually add any coke machine bottles to the coke machine If there are no empty slots assuming there were empty slots Then what the semaphore p does is it decrements the number of empty slots? Why because we're about to add another uh We're about to add another coke bottle. So there's one less empty slots And then notice that we grab the mutex with a semaphore p and we release it after we're done And that's all to protect this Queuing operation we're going to enqueue a coke into the machine Or enqueue an item on the buffer Okay, and why do we have a semaphore p follow and have semaphore v because the operation on enqueuing We don't we can't afford to have multiple threads screwing it up Okay, so this is think of a mutex as a lock And the consumer is kind of the mirror image of this right so the consumer say you're a student grabbing a bottle of coke Says that if there are no full slots because the number of full slots is zero This semaphore p is going to go to sleep Otherwise if there's more than zero full slots That means there's more than one and more than zero bottles of coke Then the semaphore p operation will decrement the number of full slots exit We have our mutex around the dq operation. So we grab Um the lock by doing a semaphore p and then we release the lock by doing a semaphore v And we correctly do a dq Okay, and then um finally We when we're done we increment the number of empty slots to tell the producer we need more Okay, and I forgot saying we increment the number of full slots down here in the producer case Okay, so think of These uh as critical sections Okay, or maybe just the enqueue and dq that are being protected by mutexes Okay, so that's one use of semaphores Then this producer when it puts a bottle of coke in Not only does it increment the number of bottles of coke by incrementing full slots But if it turned out that there was a consumer waiting for a coke bottle Then this semaphore v on full slots will wake up Uh an item that was sleeping on a semaphore p Okay, and it could be by the way, I'm sure some of you are thinking well, what if there are Five students sleeping on semaphore p What happens is it might be the case that the semaphore v going from zero to one wakes them all up But then the first thing they're going to try to do when they're awake is decrement the semaphore One of them will get a chance just because of the scheduler to decrement it Uh from one to zero and they'll exit semaphore p and get to go on The rest of them will encounter that the semaphore p is back to zero already and they'll have to go immediately back to sleep so this Full slot increment will only wake up one of the sleeping guys if in fact Full slots went from zero to one when we did semaphore v And then the flip side of this is this semaphore v on empty slots will wake up the producer If it turns out that um, there is a producer sleeping on Um the fact that there aren't any empty slots for the bottles of coke Okay So this is there to give you an idea that semaphores are a lot more Sophisticated in what they can do and they do they do both mutex operations Like locking and they all and they do resource operations where you get to track the number of resources And make an action based on that So a little discussion about the symmetry Of this solution. So why Do we do semaphore p on empty buffer and semaphore v on full buffer for the producer? But the consumer does the opposite. Well, that's because the producer is Waiting when there's an empty buffer and signaling that they've filled a buffer Whereas the consumer is waiting when there are no full buffers, but signaling when there's a new empty buffer Okay, so we decrease the number of empty slots. We increase the number of occupied slots Here we decrease the number of occupied slots and increase the number of empty slots Notice by the way, I just want to say this That it's not we have two semaphores for either end of the spectrum Okay for whether we can add items To uh to the front or not and whether we can remove them from the back or not those two semaphores Uh are on opposite ends of the buffer. So we need two of them. We can't just get by with a single Uh semaphore that sells us how many items are in there because then we wouldn't be able to sleep On one or the other side. Okay So we need two one for each side of the buffer The other thing to to notice is is the order of these p's important. So the producer did do semaphore p on empty slots and then And then semaphore p on the mutex and then in q and so on Will this matter if I swap these and the answer is yes, this can actually cause deadlock Okay, why is that? Well, if you look the producer comes in Execute semaphore p on the mutex Okay, so it grabs the lock and then it calls and says, oh, there are no empty slots And so it goes to sleep We've now got a situation where the producer is sleeping While holding the lock Which means that if the consumer comes along And tries to add a bottle of coke or takes to take away a bottle of coke. Excuse me What'll happen is it'll execute semaphore p on full slots It'll try to grab the mutex But it can't because the mutex has been grabbed by the producer after Just before it went to sleep. And so the consumer will be permanently stuck All right, and this is a bad deadlock scenario Okay And then you could come up with a cycle We'll talk more about deadlock later in the term is the order of the v's important That's no and the reason is that Neither of these Block in any way what they do is they increment a value and possibly wake somebody up So you can do those in any order Okay, what if we have two producers and two consumers? Well, if you look back at our solution back here What you'll find is this works for any number of simultaneous producers and consumers and The threads will just go to sleep if there's no space And so this is this particular solution works perfectly well for many producers and many consumers Okay Especially the one producer one consumer case, which we might have started with Okay Don't need to change anything. So where are we going with synchronization? So in the next monday and the the rest of this particular term, we're going to be going To various high-level synchronization primitives using atomic operations You're going to see a bunch of hardware to help us. We're going to start with load and store being Atomic and then we're going to disable interrupts As a way of getting locking and then we'll talk about using test and set and compare and swap And then we're going to start putting in some higher level primitives And what I mean by that is we already know what locks and semaphores are but we're going to start talking about How do you build them? Okay, and we'll talk also then about monitors and send and receive and so on more sophistication And then we'll talk about shared programs All right, so that's all I wanted in this supplement Just wanted to talk to you a little bit more about locking and semaphores We'll repeat some of this material on monday, but I just wanted to give you a little bit of an extra Heads up here in case you were interested in learning something more about semaphores before your design doc was due All right. Have a great Rest of your day and we'll see you on monday. Thank you