ProgrammingParadigms-Lecture16

Instructor (Jerry Cain):Hello, welcome. I donít have any handouts for you today. You have plenty of handouts from Monday that we still have to spend the next few lectures on. Youíre not getting an assignment today, so you have this grace period from tonight at 10:00 p.m. until Friday, where you have no responsibility for 107 whatsoever. Remember, the exam is this evening at 7:00. Itís in Hewlett 200, which is this huge auditorium in the building across the Ė beyond the fountain from gates. Iím going to send an email out after lecture, but just in case SUPD students are watching this before the TV exam tonight, Iím planning on posting the exam as a handout at 7:01 p.m. tonight, and then remote students just download it, self-administer, call in if they have questions and then fax it in when theyíre done. They donít need a proctor. I donít need any of that business. I just assume people are well suited to just sit by themselves and take an exam without somebody of authority hanging over their shoulder. And then, SUPD students actually have the option to take it tomorrow morning as well, and I actually prefer that SUPD students take it, because if thereís a disaster during the exam tonight, people in the room can be dealt with immediately, where as itís very difficult to probably get that information outward. So, I actually prefer SUPD students to take it tomorrow and then fax it in sometime before 5:00 tomorrow so we can grade them.

Okay, Iím going to try to get the graded exams back to you and available by Sunday evening. I canít promise that. Okay, I actually have not dealt with a class this large in a long time, so weíre dealing with Ė I know it looks like itís this cozy little family here, but itís not. Itís actually 230 some people and itís been a while since I have had to manage a grading effort that involved that many people. Itís also complicated by the fact that I am out of town this weekend, so my CAs are grading it and it might be difficult for them to get you the exams back by Sunday evening, but weíll do our best to make sure that that happens, okay? When I left you last time, I had focused specifically on the first multi-threaded example where we had to introduce this notion of a semaphore in order to control access to what we called a critical region. So, if you remember last time, the threaded function, the one itís the recipe that ten different dogs follow while theyíre trying to get their work done. It looked like this. Sell tickets, token INT, agent, it took an INT star called non-tickets and non-tickets P and then it also took this semaphore, I call lock. Just to review, since this was kind of a fleeting comment in the last ten minutes of Mondayís lecture, the semaphore Ė it is more less like a Ė basically letís say a synchronized counter variable that is always greater than or equal to zero, okay? And so if I construct a semaphore around the number one, and I levy a semaphore weight call against the semaphore, this as a function figures out how to atomically reduce this one to a zero. Okay, and so this is basically equivalent to the minus minus but it does the minus minus in such a way that it actually fully commits to the demotion of the number to one thatís one lower than it, okay? Semaphore signal on the same exact semaphore would actually bring this back up to a one, okay? If this were followed by a semaphore weight call followed by another semaphore weight call, then something more interesting happens, where this one right here decrements the one down to a zero. This one right here would have a very hard time.

Because semaphores at least in our library Ė this isnít the case in all systems, but our semaphores are not allowed to go negative. So, when you do a semaphore weight against a zero variable, then this thread actually says oh, I canít decrement that, at least not now. I need somebody else in another thread to actually plus plus this so that I can actually pass through a minus minus without making the number negative. Does that make sense to people? Okay, so programmatically, the implementation of semaphore weight is in touch with the thread library and so it actually when itís attached to a zero behind the scenes, it immediately says ok, I canít make any progress right now. It pulls itself off the processor. It records itself as something thatís called blocked and it puts it in this cue of threads are not allowed to make progress until some other thread signals a semaphore theyíre waiting on, okay? Does that sit well with everybody? Okay, this is not constrained to go between one and zero. It can Ė this can be set to either be zero or one or five or ten. The only example weíve seen so far is where the semaphore thatís coming in is initialized to surround the one because we really want it to function not so much as one as we want it to function as a true, and itís basically a light switch that goes on and off, on and off, and on and off, and itís used. And, we use semaphore weight and semaphore signal against that semaphore to protect access to the non-tickets variable that we have been addressed to.

So, in a nutshell, while itís the case that true is true, I want this right here to be marked as a critical region. What that means is that I want to be able to do surgery on that non-tickets variable, without anyone else bothering it, okay? And the way you do that is to do a semaphore. Iíll spell it out here. Semaphore weight on the lock, you do the check to see whether or not non-tickets of P is equal to zero and if so, you donít do the surgery. Okay, on the end, somebody else has done it a hundred times already and there is no reason to do it again. Otherwise, you want to go through and do this, thatís true surgery on what functions as a global variable, at least from the perspective of all the threads running this and then you want to release the lock. You might do some printing here, okay? You might sleep for a little bit. Down here there was an extra semaphore signal call against the lock to accommodate the scenario where the person who breaks out of the wild loop does so after securing the lock, so they actually have to release the lock kind of as they go outside the bathroom window, as the analogy I used on Monday, okay?

This is considered to be Ė Iím sorry, this right here is considered to be a critical region. Itís supposed to be something that when theyíre inside there, they cannot have any other threads during their time slices mucking around with this type of stuff, okay? As an arbitrary thread actually gets here, given that this thing was initialized to one, and because every single semaphore weight call is balanced by a semaphore signal, itís going to toggle up and down between zero and one. When a thread gets here, there is one of two scenarios. Itís staring at a one and so it actually successfully does the minus minus and is allowed to pass in here and do the work or the thread blocks on this. You may say, well, how would that happen? A thread could potentially block on this if thereís a zero, if another thread saw a one here decremented to a zero, made partial progress through this but the time slice ended before it got to the signal call. Does that make sense to people? Yes? No? Okay, just because a thread owns a lock doesnít mean that it canít be pulled off the processor. It might acquire the lock; get two-thirds of the way through this final instruction here, okay? And then be pulled off the processor so that other threads can actually say, oh maybe I can make some progress, but if they get this far, theyíre still seeing a zero because of the thread that owns the lock hasnít released it yet.

Okay, so as other threads hit this semaphore weight call and it surrounds a zero, they are pulled off the processor. That is kind of what you want. If they canít do any meaningful work, you want the thread manager to say you canít do any meaningful work. Iím not going to let you even use your full time slice and eventually itíll get back to the only thread that can do work, which in particular would be the one that owns the lock right here, okay? Does that make sense? Okay, so thereís that right there. Typically, try to keep the critical regions as small as possible. If youíre going to lock down access to code, you donít want to make it arbitrarily long. Thatís basically like saying I want to do all the work in the world, so Iím just going to acquire a lock and Iím going to run this triple four loop. Okay, you only do that if you have to because itís a critical region. This print up in particular, if itís just logging information, it might not be imperative that you actually print to the console while you hold the lock, so you could release the lock and let other people make some progress, and then without holding the lock, just go ahead and print to this screen, okay? Does that make sense? Okay, there are a couple of other things. Somebody asked a very good question at the end of a lecture on Monday and I think I want to go over it. Some people were concerned with the case where non-tickets paid minus minus takes a one down to a zero, I donít mean the lock, I mean the actual number of tickets and they thought that was the one problem we were worrying about.

The answer is thatís not the case and I can actually tell you a little bit more about what happens as threads get swapped off the processor and where all of their data gets stored, and show you that if the number of tickets is originally 100, there is as much of a race condition without the semaphore weight and semaphore signal calls in the minus minus bringing the 100 down to a 99, as there is in bringing a one down to a zero. So, this is what would happen and this is going to be the most important line to concern ourselves with. Forget about the fact that there are ten or 15 ticket agents. Just think about the scenario where thereís two. Okay, it is subdivided and this is the main stack frame. Okay, itís the thing that sets up the two threads and caldronal threads. Letís say that this is ticket agent one and this is ticket agent two. Okay, these little like tornadoes are actually stack frames, okay, that each of the threads has. So, each of these things right here have their own activation records for their own call to sell tickets, okay? Declare someone a name is the number of tickets variable that will set equal to a hundred. That make sense? Each of these stack frames stores a pointer to that one hundred, okay? Imagine the scenario where the semaphore weight and semaphore signal are not there. This is how the two ticket agents could each sell one ticket even though itís only globally reported as a single sale, as opposed to the two tickets that were really sold. Coming down from here, la la la la, you see that itís not equal to zero, so you go in and try to sell a ticket. You know that this type of instruction actually expands to quite a number of assembly code instructions. Okay, does that make sense to people? So, in a local register set, this R1 may be set to .2, that right there, or two may be set to 100, because you do R2 is equal to that of R1.

Okay, then maybe you go in and you do a minus minus on R2, and bring it down to a 99, but now youíre swapped off the processor. So, youíve actually committed to the sale of a ticket, right? But, youíre swapped off the processor. What happens is that the entire register state, all 32 registers, including the PC and the SP and the RV registers, if this is the binary state of all those registers, itís actually copied to the bottom of the thread thatís being swapped out, little stack frame. Okay, and is that image that I just drew, that is used to restore the register set for that thread when it gets the processor back, okay? Embedded inside this image is the 99 thatís going to be used to flush back to this space right here. Does that make sense? Okay, but this has just left the processor and so this thing does exactly the same thing with the register set as if it owns it. It sets R1 equal to that right there. The 100 still resides there because we didnít successfully flush back. We didnít get to the point where we actually update it to be the decremented value. So, R2 gets set equal to 100, gets set equal to a 99. This one is prepared to flush with a 99 back to the global space when this thing gets the processor back; itís going to flush a 99 back to the same space. So, this 99 is designed to override a 100. So, is this one, but unless you have semaphore weight and semaphore signal in place the way we do right here, one of the 99s is going to override a 100 and one of the 99s is going to overwrite the other threadís 99. Does that make sense to people the way Iím saying that?

Yes? No? You gotta nod your head, okay. If you put that there, and you put that there to balance it, and basically unlock the door, then only one thread is allowed to go through and actually pull the global value into the local register, decrement it locally, and then flush it back out to the global integer, the thing that functions as a global integer, because everybody has a pointer to the same integer. Before any of the thread is allowed to do any part of that, okay, so that is what I mean when I say that this is more or less committed to atomically, okay? Now, that is the overarching principle that is in place when you have threads, and in particular, you have threads accessing shared information, okay? This is the programmatic equivalent of the two Wells Fargo ATM machines where me and my best friend try to take out the last remaining $100.00 in my account at the same time, thinking weíre going to get $200.00. Okay, make sense? Okay, if I were to initialize this semaphore to zero, then I would actually block all threads from entering this critical region right here. Okay, so Iíd get deadlock. If I initialize the semaphore not to one but to two, thatís as bad in principle as initializing it to ten, because you donít want any more than one thread in this region at any one time, okay. Does that sit well with everybody? Okay, good.

Okay, so let me move on and give you another example using threads and a different way to use semaphores. The handout actually uses global variables more than I like to, but this next example, I am going to use globals just so the code matches up a little bit more cleanly with the handout version. I actually like it better if you declare all of the shared variables in main and pass addresses to them, to the threads, because at least everything has a scope to it, whereas globals, itís a free for all and for two and a half quarters, we have been saying globals are awful. Oh, except for when itís convenient, okay, and I donít like that. But, this one next one, I want to frame it in terms of globals. Iím trying to model right now the Internet, where in all the world thereís only server that serves up all the web pages and you have the only other computer with the only browser in the world. Okay, I know you know enough about the HTML server process. You may not know all the mechanics at the low level, but fundamentally, you know that you request a web page from another server. It serves up text in the form of HTML normally. It could be XML, but normally itís HTML, and as the HTML comes over, it does a partial and eventually a full rendering of the HTML in your browser page. That make sense?

You know and you felt this before where a page is loaded like 70 percent but itís not quite done yet, you see the progress bar at the bottom, the bottom right, where itís like three-fourths of the way through and you know thereís more to come. Thatís usually because the server has only delivered 75 percent of the content and so this thing has to block in much the same way that the threads up there block, this has to block and stop its rendering process until it gets more data from the server. Does that make sense? So, just use that as a guiding principle for this example. Iím going to insult all the Internet and Iím going to reduce it to a character buffer of size eight, okay? And what I want to do is I want to write a program that simulates the writing and the reading process and Iím just going to reduce the server to something that has to populate that buffer as a ring buffer. In other words, itís going to write 40 bytes of information, but itís going to cycle through the same array five to five times and Iím going to write another thread that consumes the information by cycling through the same array five times and digesting all the characters that are written there. Does that make sense to people? Okay, so the main function Ė I donít care about those. I have to emit all threads, Iím sorry, thatís not right. Itís the hybrid of two functions. I want to emit thread package of [inaudible] meaning I donít care about the debug information, and then I want to do this. I want to call thread new twice. Iím going to give them both names. This one is going to be called Writer. This oneís going to be called Reader. Okay, Iím going to call the function writer and Iím going to call the function reader. I only have one instance of each one and neither one of them takes any arguments. Okay, it doesnít need to take arguments if you use global variables. Then, I do this. Run all threads. This is somewhat pathetically, but on the well intentioned Ė it is trying to emulate the fact that the server and the client as computers are both running at the same time.

Okay, programmatically I want the writer thread to cycle through and write 40 characters to the Internet. Okay, I want this reader thread to consume the 40 characters that are written in the Internet. Okay, this is what the writer function looks like at the moment. Four INT I is equal to zero, I less than 40, I plus plus, da da da, what I want to do is with these iteration, I want to call some function. Iíll assume itís thread safe. Prepare random car and then I want to write to buffer of IMOG eight, whatever, letís give that variable a name, C. Whatever C happened to become bound to and so as an isolation function, I think you can look at this and understand that itís going to write down random characters in this loop over the buffer five times. Okay, I write this with hopes that it writes data down before the reader consumes it but it doesnít go so far that it clobbers data that has yet to be read. Does that make sense to people? Okay, let me write the reader, which has the same exact structure: I less than 40, I plus plus, there you have that. What I want to do is I want to basically do this and then I want to basically like, you know, process car, which I donít care about the details of what process does. This is the consumption line. This is the thing that takes a meaningful piece of data in shared space and brings it into local space, so it kind of owns it. It can do whatever it wants to with it. Okay, let me draw the Internet. That was easy. There you have it. Now, you know, without concurrency, you know exactly how you want writer and reader to behave, so that everything is preserved and the data integrity is respected, and that the reader processes all the character data in the order that the writer writes it.

So, think about the scenario where the writer gets to run first and its first several time slices, it writes those three characters down. Okay, and internally it has a variable of I that is associated with that index, so thatís where itíll carry on next time. Okay, but it writes those three variables down. And, then the reader gets a time slice and for whatever reason, process character is a little bit more time consuming. It actually has to like open a file or a network connection or whatever it has to do, just pretend that it actually is slower Ė its [inaudible] is slower, so it only really consumes that A. It doesnít really remove the A, but it just consumes it so it doesnít matter whatís there anymore. Okay, so this is where the writer will pick up and this is where the reader gets swapped off, okay? I think itís pretty clear that if the writer is able to make more progress per time slice than the reader, then thereís the danger that this might happen. And that on the very next iteration, it gets far enough in its time slice that it overwrites data that the reader has yet to deal with. Does that make sense? Okay, you canít have that obviously. Now, clearly, Iím simplifying things here, but the idea that someone is providing content and someone else is digesting it, thatís not an unfamiliar one with large systems. Itís also in theory possible. Just because I spawn off and set up writer to be the first thing that runs and this the second thing that runs, it might be the case that the reader gets the processor first. In which case, it will be digesting information that has never even been written or created. Does that make sense?

So, what I want to do. I want to create Internet so I can put some more global variables here. I have to make sure that the writer never gets so far ahead that itís clobbering data that has yet to be consumed. I have to also make sure that the reader never gets Ė never catches up or passes the writer and consumer information programmatically that isnít really there. Does that make sense? Okay, so what I could do is I could introduce two global integers and have semaphores that walk them down, but Iím actually going to use semaphores a little bit differently. Iím going to declare two semaphores here. Iím going to call one empty buffers and Iím going to call one full buffers. And, Iím going to let them actually manage integers that are always, almost always, but weíre going to pretend always, are always in sync with the number of slots that can be written to and the number of slots that can be read from. Okay, I also want to enforce that the writer is also just a little bit ahead of the reader in terms of thread progress and that the reader can get and catch up to the writer, but it canít pass them, and that the writer canít get so far ahead of the reader that he actually is more than a cycle ahead of him. That make sense?

Okay, so what I want to do, Iím not going to do the semaphore new column. Iím just going to say that this is going to be initialized to eight as a semaphore. That is not the syntax floor but thatís conceptually what I want to happen. Okay, I want to mention that up front that there are absolutely no full buffers whatsoever. Okay, make sense? Iím going to change this function right here to do this. Now, this is a slightly different pattern with the semaphores, but I think itís really fun. Before I go ahead and write to this buffer, I better make sure that Iím allowed to do that, okay? What Iím going to do is Iím going to semaphore weight on empty buffers. Now, initially, empty buffers is equal to eight, which is consistent with the fact that we donít care if the writer makes a lot of initial progress. Okay, but if for whatever reason and the writer makes so much more progress than the reader that he gets really far ahead, this eight will have been demoted to a seven, to a six, to a four, to a two, to a one, and it really is just about the clobbered data that has yet to be consumed. It will be waiting on something that will have been demoted so many times that itís actually zero, okay? So, it will be a victim of its own aggression and it will be blocked out and be pulled off the processor, so that the reader can actually do some work. Okay, the balance here is a semaphore signal call but itís not against the same semaphore. After you write something down, you want to communicate to the reader that there is even one more piece of information that itís allowed to consume. So, Iím going to wait for something to be empty. Iím going to change from empty to full and Iím going to signal the full buffer semaphore, okay? The pattern over here is somewhat symmetric.

Let me rewrite it, is that I want to do the same thing, semaphore weight, but I want to wait for there to be a full buffer. When I know that thereís at least one and I pass it that semaphore weight call, I can consume the character that is in global space and pull it down and then after I bring it to local space, I can immediately tell the writer that itís okay to write there if theyíre waiting, and then process car pass the C. Okay, thereís that. Whoops, so itís like each thread has a little buzzer. Each of them are twittering each other as far as when theyíre allowed to proceed to read or write information. Does that make sense? This right here is sending a little buzzer that allows that to execute and return with much more likelihood. This right here is really communicating to the thread at that point and promoting full buffers so that the writer can actually write down more data, if it was previously blocked. Does that make sense? Okay, so think about what happens now. Empty buffers is eight, full buffers is zero. That means the writer has all of this free space to write to. Itís going to have a very easy time passing through the semaphore weight call initially. Whole buffers is zero. The reader thread is bumming because the very first thing it has to do is semaphore weight on something that is set to zero. So, imagine the scenario where the reader actually gets the processor first. Itís going to execute this much. Itís going to declare I, itís going to consider to zero. Itís going to pass the test. Itís going to come down here and itís going to be immediately blocked from this line right here because itís going to be waiting on something that is in fact zero.

Okay, so the reader thread is actually being blocked right up front just like we want it to be. Okay, the other scenario is that the writer thread really fast and very efficient, it actually cycles through this thing eight times and then it hits a wall. Okay, so pair the character out before it actually went to bother on waiting on the lock, but Ė and it blocks here, itís because itís been a processor hog and itís actually done a lot of work whereas the reader hasnít really been able to do much at all. Okay, or at least comparatively. That make sense, people? Okay, so the ticket agents example where it uses a semaphore weight and a balance semaphore signal on exactly the same semaphore, and it brackets this thing called a critical region, that semaphore pattern or that semaphore is being used as a binary lock. Okay, binary meaning itís toggling between zero and one, true and false; however we want to think about it. Thatís not the pattern thatís being used here. We certainly have thread communication. We use the semaphore for rudimentary thread communication, okay, but right here whatís happening is weíre actually using these as basically two telephone calls. Okay, between the two threads, okay, this one calls this one whenever it can make more progress. This one calls this one whenever the writer can make more progress.

That is a pattern; itís what called a rendezvous pattern. Like Iím syncing up with you, that kind of thing, okay? There are more complicated examples of this. This is whatís called binary rendezvous which really just Ė one thread to one thread communication. This basically says as this type of semaphore weight call means I cannot make any progress until some other thread makes some required amount of progress in order for me to move forward. This thing does the same thing on behalf of this semaphore. This says that I have to wait for some other thread that makes enough progress in order for me to pass, okay, or else the work I will be doing will be meaningless, okay? Make sense? Okay, so what I want to do is I want to just experiment. What happens if I make that a four? It doesnít change the correctness of the code or it depends on how you define correctness, but you will not get deadlock, okay? And you will not have any integrity data issues, all youíre constraining is that the writer and reader stay within more of a delta of one another than they would have been able to otherwise. When it was an eight, it allowed some more degrees of freedom. It allowed the writer to go much further ahead if thatís just the way thread scheduling worked out. When I made it a four, it just means that the writer can be no more than half of an Internet ahead of the reader, okay? Does that make sense? If I do that right there, Iím really pushing the limits of whatís useful from a threading standpoint. If Iím going to do that, I also will just actually write the reading and writing in the same function and have it alternate between read and write, but if I really let these two threads run with those two initial values, all thatís going to need Ė this is my W finger, this is my read finger. It just means itís going to run like this. Okay, does that make sense to people? And really if it tries to like run forward two slots, itíll be blocked by a semaphore weight call.

Okay? If I do this and I have a different form of deadlock, but deadlock is deadlock. I have a reader saying I canít do anything because I have no place to read from. The writer says well, I canít do anything because I have no place to write to. Okay, so you would have deadlock. You look at that and you say I would never do that, yes, you would. You just have, like when youíre writing down all of the semaphore values, maybe you have like 20 semaphores in a real program, itís very easy for you to cut and paste a zero in place where you really wanted a one or a four or an eight, okay? So, if you have deadlock and youíve never had that before, maybe you have because youíve been in some wild true loop, but thatís not the same thing. You really are making progress, you just donít see it. With threads, if you have deadlock, everything seemingly stops. You get nothing published to the console at all. It doesnít return. You donít get your command line prompt back, so things just expand and then you go okay, that probably means that two threads are waiting on each other.

Okay, or that nobody released a lock or something like that. Okay, if I do this, just think about whether thatís damaging or not. You may think that initially [inaudible] should be more than full buffers. Let me do this. You could say well, I just want to kind of constrain full buffers plus empty buffers to always be eight. Okay? But if you do that, that actually allows the reader thread to get one hop ahead of the writer. Okay, so thatís a kind of contrived example, but nonetheless thatís exactly what it will be permitted to do. It doesnít mean it would actually happen, but it means programmatically itís possible. Another scenario is when I get this one right, but I do something like that. Okay, you may think that youíre limiting things because you have semaphores in both directions but that thing has to be between one and eight for it to be programmatically correct. To put a 16 means that the writer is allowed to make two loops and take two tracks or two loops on the reader thread and thatís not allowed. Itís supposed to be at most eight slots ahead of, not 16 slots ahead of the reader, okay? Now, I had one and four and eight there before, my argument is that it should be the eight. Okay, if you have multiple options as to what you can initialize your semaphores to be, you always error on the side Ė although error is not the right word Ė you always kind of move toward the decision that grants the thread manager the most flexibility as to how he schedules threads, okay? And it also improves the likelihood that every single thread will be able to use all of its time slice. Okay, to the extent that you artificially constrain the threads, if you were to make that eight a one again and you get this again, it probably means that each thread is being hiccupped and pulled off a thread prematurely. Iím pulled off the processor prematurely. Does that make sense? Okay, and so you usually try to maximize throughput and you choose your semaphore values accordingly. Okay, does that sit well with everybody? Yeah?

Student:[Inaudible] semaphore weight?

Instructor (Jerry Cain):Which one is this? This is on the semaphore you mean?

Student:So, you called your semaphores, so now [inaudible] semaphore weight, so Ė

Instructor (Jerry Cain):Thatís actually not. You mean you call semaphore here before you wrap around and wait on empty buffers?

Student:[Inaudible]

Instructor (Jerry Cain):Well, this one never waits on full buffers. That one does.

Student:[Inaudible] signal before you call semaphore weight?

Instructor (Jerry Cain):Which semaphore weight are you talking about? Oh, I see what youíre saying. In other words, if the reader doesnít agree with the processor, what happens here Ė is it the writer just happens to go first? It brings an eight down to a seven and it promotes a zero up to a one. But thatís okay because it really is one slot ahead of where the reader is. The reader hasnít even started yet.

Okay, and so if this makes, letís say four full iterations and it brings empty buffers down up to four and full buffers down to four, thatís fine, because if it gets swapped with the processor here, this thing just discovers a world that itís born into Ė it says wow, there are four characters I can read right away. Okay, and so it doesnít matter that it hasnít blocked Ė it hasnít called weight yet.

If it calls weight it only means weight if full buffers is zero. Otherwise, it just means decrement. Does that make sense? The words weight and signal are really, I think, were adopted with the binary lock metaphor in mind. I also hear when the thing is really a lock, Iíll hear acquire and release as the verbs. Some versions of thread libraries actually define a lock type that things that lock acquire and lock release, which are really just the wrappers for semaphore weight and semaphore signal with the understanding that theyíre protecting ones and zeroes, okay? But itís not like this thing has to wait on that before this thing is allowed to signal it. Okay, sometimes you arrive at the bathroom and the door is open already. Okay, it just happens. Make sense to people?

As far as I have a single writer and I have a single reader, if you have Ė I wonít write code for this but Iíll just let you think about it. A lot of times when you are loading a web page, the HTML is often being sourced from multiple servers. Okay, maybe the primary HTML is being served from I donít know, facebook.com, but all the images actually reside on some other servers that are residing elsewhere, okay? And so all the information is pulled simultaneously.

Okay, imagine the scenario where you have not one of these things right here but you have three writers and theyíre all kind of competing to write and prepare the information thatís actually sent over the wire to the single client. Well, then all of a sudden, you would have to Ė you would still want to use this empty buffers thing but then you would have to have an extra global, okay, or either that or something that is declared in main and shared with all the writers, so that they can all agree on what the next insertion point into the Internet is. Do you understand what I mean when I say that? And you have to have some kind of binary lock in place to make sure that no one, no two threads try to write to in this race condition matter to the same slot in the Internet or some piece of data will be lost, okay? Does that sit well with everybody? In the scenario where you have multiple readers consuming the information, maybe itís not really a web page but maybe itís just content thatís being sent up from an FTP server and itís being handled by threads and that actually takes several different files simultaneously. You could use the same exact type of thing for the readers. Okay, does that make sense? Okay, so thereís that. Let me work on one more example. This is a canonical problem that I think appears in all courses that teach concurrency. This next example is whatís called the dining philosophy problem, where itís kind of a ludicrous setup, but nonetheless it is the setup. So, at the center of a table, Iíve drawn this picture 18 times now, there is at the center of the table youíre looking down from the heavens at this table which has a plate of spaghetti at the center. Okay, and surrounding the table are five philosophers with their big brains, okay? And, in between each philosopher is a fork and every single philosopher follows the same formula every single day. They wake up, they think for a while and they eat and they think for a while and they eat and they think for a while and they eat, and of course they think for a while before they go to bed. Okay? So, there is four think sessions [inaudible] by three eat sessions, but the interesting part and philosophers are actually confused by this idea that they actually need to grab both forks on either side of them in order to eat the spaghetti. So, they are these geniuses who have to eat like this, okay? If I model each of these philosophers as C threads, so each one follows the same think, eat, think, eat, think, eat, think pattern, it might be the case that they both decide to stop thinking.

Two neighboring philosophers decide to stop thinking at the same time and will eat but I can tell you right now that this one and this one will never be eating at the same time, because they both demand the fork in between them to be in his hand, in their hands before they actually eat spaghetti, okay? But let me not worry about that, let me just write the code and pretend that everything just works out and that will illustrate the deadlock problem. Okay, I want to model the forks as an array of semaphores and Iím going to write them down this way. This is shorthand. You actually would have to prepare them with five calls to semaphore new. But that just means that every single fork initially before they all wake up, there are five forks sitting on the table waiting to be grabbed by philosophers. Okay, and thatís all I need. Iím actually going to write a thread, one philosopher, and each philosopher knows where he sits around the table, okay? And so the formula I want them to all follow is the following: four, oh, I canít use I there, Iím going to use ID. My first stab at this is this right here where they think for a while, just assume that thatís some thread safe function that doesnít require any kind of interaction with other think calls, and then they want to eat but that isnít going to happen. There is actually a think call down there but thatís not that important. What has to happen is that the four of the philosopher calls in his thread space, he needs to acquire fork I and fork I plus one, being sensitive of the fact that fork I plus one may be fork of zero is I is really high. Okay, does that make sense?

So, what I want to do is I want to semaphore weight on two different forks. Forks of I and forks of I plus one mod five, if a philosopher is able to pass through those two things then he just realizes brilliantly that he has two forks in his hands, so he is permitted to eat and call this function. He is a polite philosopher, so that when he is done eating, he is aggressive about putting the forks down by calling semaphore signal of I and I plus one mod five, and it is perfectly possible that if I spawn off five of these functions in main. I set up the forks full array of semaphores and it is four loop from I is equal to zero up to but not including five, I call thread new and I pass in zero, one, two, three and four, so they all have an ID number between zero and five and everyone has a unique number. It is possible for this to work. Okay, some philosophers think more enthusiastically about a problem before they eat. Some just really Ė they have like I donít know philosophy block and they actually Ė and they want to eat right away but this is technically programmatically encoded into this as a possibility. I am philosopher number zero and I thought for a while, but I would like to eat now. And so I do grab fork number zero and Iím holding fork number zero and then I get swapped off the processor. Okay, make sense? This as a resource is not available.

That first zero, first one is now decremented to a zero at the time that the thread is swapped off. Make sense? Maybe the processor gets, Iím sorry, philosopher, the second philosopher gets the processor next, thinks for a while, gets this fork, okay, gets swapped off the processor. And then it happens again, and then it happens again, and then it happens again and then maybe this one wants to grab the right fork and itís like oh, canít do it because itís blocked. Okay, itís semaphore weighting on something that isnít available as a resource. So, it gets swapped off the processor, right? Maybe thread two, philosopher two says oh, I have the processor again, Iím going to grab the fork. Oh, Iím blocked. Okay, everybody is holding a right fork that is somebody elseís left fork. So, when this slightly more obscure way, I think itís still pretty clear though, you have this mutual deadlock among all five threads because every single one of them is waiting on some resource held by the philosopherís to his left. Okay, does that make sense to people? So, you have deadlock. We can certainly overcome it. Itís not a disastrous problem. There are multiple ways to solve it. You could actually alternate and have philosophers alternate between whether they grab the odd indexed fork first or the even indexed fork first, that could help solve things. But, Iím not going to take that approach. Iím going to take something else. Somebody had a question? Yeah?

Student:[Inaudible]

Instructor (Jerry Cain):Oh yeah, Iím sorry, it should be. This is just three iterations. Every single one of these should be IDs, that is correct. Sorry about that. So, I have to let you go in a minute, but I can really just communicate the problem I think pretty clearly. Remember earlier I said I wanted to do the minimum amount of work to prevent deadlock?

Okay, I want to implant the least amount of functionality to make something possible while still maximizing the amount of thread, amount of work that any particular thread can do during its time slice. Well, I could actually make this a critical region and that would be really rude because that would require that at most one philosopher can eat at any one moment, and that in itself is rude because youíre not supposed to eat while others cannot.

Okay, but that isnít really the problem. What you could do is say you know what, I actually know that given that there are five forks and ten forks need to be held in order for everybody to eat, I can tell that at most two philosophers are going to be allowed to eat at any one time. Because if three philosophers are eating, that requires six forks to be held and we just donít have that many. Okay, we could also say that as long as we just prevent one philosopher from grabbing any forks whatsoever, itís technically possible to let four philosophers grab forks. Three of them may be blocked, but since Iím only allowing four philosophers to grab forks, exactly one of them will be able to grab two forks as opposed to one, okay? Does that make sense?

Now, two being allowed to eat, allowing four to try to eat, there are two different heuristics for solving the deadlock problem. I think both of them are very clear, are wise heuristics to go with. I will in the parting comments Ė I will tell you that I will at the handout take this approach. None allowed to eat, and that itís initialized to four. Okay, and the idea is that you have to be one of the graced four who is allowed to grab forks in the first place and try and semaphore weight on them allowed to eat right there. Most of them will be able to pass through it immediately. The only philosopher that would be blocked on a call to semaphore weight on none allowed to eat right there will be the one who is the only one who hasnít tried to start eating yet. Does that make sense?

After you release the forks, you could call semaphore signal right there on none allowed to eat. You may think itís really weird to allow four to try but all Iím trying to do is remove the deadlock. Okay, and I technically will remove the deadlock if I limit the number of philosophers trying to simultaneously eat, to not be five, but to be four. Okay, does that sit well with everybody? Okay, I will go over the actual code for that on Friday, okay, and then I will give you some more intense examples than that. Okay, have a good night. I will Ė

[End of Audio]

Duration: 51 minutes