ProgrammingParadigms-Lecture17

Instructor (Jerry Cain):I have one handout for you today. I expected to have two but we had photocopier drama this morning so I havenít photocopied your assignment yet.

Iíll post it as a handout after class today. You have plenty of time to do it. Iím not gonna make this due until two Mondayís from now. So itís not like youíre in any immediate rush to get started on it, so thatís why I wasnít stressing about it. But nonetheless the assignment will formally go out today and youíll have two weekends to do it.

Itís actually not too bad. It certainly involves some of the new threading stuff, youíre revisiting Assignment 4. Youíre implanting some thread directives to make a lot of stuff that was running sequentially before and you felt the pain of that sequential execution before. Make it so that lots of things run in parallel and things run really, really quickly, really, really beautifully. Itís very impressive, itís a good end result once you actually get that thing up and coded.

When I left you on Wednesday, you were all stressed because you had a midterm in seven hours. But I was just getting through the dining philosopherís example. Let me review the picture. The idea is that there is food, a big plate of spaghetti, at the center of a table and there are Ė Iíll be less caricature about it this time Ė there are four philosophers Ė and Iíll put P0 there Ė sitting in a circle, and there are actually what look like pitchforks but just regular forks in between each of them.

And each of those philosophers is designed to run in his own thread and they follow the recipe, that is, they think, they eat, they think, they eat, they think, they eat, and then they think again, and then they exit as a thread. That is their day. In fact, thatís their entire life because they only live for one day, okay.

So I set this up as a global resource, because thatís the way the handout deals with it. I will emphasize again that the way Iím writing this Ė this is shorthand, all Iím really saying here is this is a gesture to the fact that I have five global semaphores and an array of link five that are all initialized to one. There really are some semaphore new calls that are involved to build that thing up but I donít want to focus on that other than just mentioning it.

Each one of those ones basically represents the availability of a resource. If I call this Fork 0 and this is Fork 1 and Fork 2 and Fork 3 and Fork 4, when this particular semaphore is locked up in this synchronized manner at a 1, I know that this particular fork is available. And that is of interest to Philosopher 1 and Philosopher 2 because both of those have to contend for that fork in order to pass into the eating phase of the thread, okay.

So without concerning ourselves with the deadlock scenarios that was outlined last time, this is basically the thread I want them to follow. Each philosopher knows their subscript or their ID number and that influences which forks they grab, or they try to grab.

And so if Ė where did if come from? For N to I is equal to 0, I less than 3, I++, I want each philosopher to grab the fork to the right, fork to the left, that grabbing happens via two semaphore wait calls against forks of ID. I messed that up last time, I wrote I, forks of ID and then forks of ID + 1 but we want to modify 5 just so it wraps around. And letís Ė there we go, there, okay. And as long as they pass through those and return from those two semaphore wait calls in sequence theyíre allowed to eat. This is after they think for a while.

Okay, and after that happens, they eat for a while, they semaphore signal these things. I donít really care about the order in which they free them. It doesnít really impact execution in an interesting way. Forks of ID plus 1, mod 5 and that is more or less what they do. Thereís an isolated think after the last meal and then they return.

And I did my little choreography last time where in principal because each of these five threads may be running in round robin fashion, they probably will be, each one might get to the point where they grab the right fork. Theyíre enough through this call that theyíve effectively acquired the fork because the 1 has gone done to the 0, but they get swapped out sometime between the actual demotion there and the time they actually demote the 1 to a 0 inside. Does that make sense?

So itís possible, I donít want to say itís unlikely, itís actually unlikely unless you force it happen but actually I donít want to say that. Because itís possible itís a problem. If all five threads could be swapped out right here and all be experiencing mutual deadlock because theyíre all depending on the philosopher to his or her left to be releasing the fork that is their right but your left fork, okay. Does that make sense?

Normally what you do, put all your semicolons in, but normally what you do is you implant the minimum amount of work to remove the possibility of deadlock. We made some observations in the final ten minutes of lecture on Monday Ė or Wednesday rather, where we know because of 5 div 2 is 2 that at most four forks can be held while philosophers are eating, okay.

So we could recognize that there are at most two philosophers gonna be able to eat at any one time so we could actually put something out of the generalized counter right there and right there and actually force each philosopher to become one of the blessed two thatís allowed to go ahead and grab forks. Does that make sense to people, okay.

So what I did is I did this semaphore, a single semaphore, none allowed to eat, and I could initialize it to two. Let me get rid of these arrows. And I could sneak in a call right here where I say, ďPlease wait for me to be one of the two that is allowed to eat.Ē

Okay, itís something of a critical region. Itís not the same type of critical region we saw before. Critical region normally means at most one because they are concurrency Ė there are race condition possibilities. This is a different type of critical region. In fact, most people wouldnít call it a critical region but Iíll call it that. But we only want two threads to be somewhere between here and this part right here, okay, because if we have any more than that then weíre nearing the scenario where we might have deadlock, okay. Does that make sense to people?

So let them go ahead grab forks, eat, release the two forks and when theyíre doing saying basically, ďI have left the table.Ē So that means I should signal all the other threads or all the other philosophers that might be waiting to Ė for permission to grab forks and do a final semaphore signal call right there, okay. Does that make sense?

Now, if you push two there I would completely understand why you did that. I personally, even though I recognize that there are at most two threads allowed to be in there, okay, or the way weíve actually programmed it up that at most two philosophers will really be calling the eat function. My preference, just because Iím a purist about it, is that this be a 4 instead. Okay? Now a really terrible value would be 5. If I have 5 philosophers then basically the semaphore wait is just this gratuitous semaphore that everyone has to consume but there will always be one there.

The reason the 4 works is because as long as somebodyís prevented from grabbing either fork then thereís at least one philosopher thread thatís capable of grabbing two forks. Maybe the other three or blocked, okay? But itís always the case that exactly Ė at least one philosopher will be able to grab two forks. Does that make sense to people?

Thatís the minimum amount of a fix that I need to implant into the code to make sure I donít have deadlock. So concurrency and multithreading purists usually like to do the minimum amount of work to prevent deadlock. There is a reason for that, because the minimum amount that you implant there Ė you remove the deadlock but you still grant the thread manager as much flexibility in how they schedule threads as possible, okay.

When I put a 2 there Iím taking more control over how threads are scheduled. That means up to three threads can block on this line right here as opposed to just one. Does that make sense? Okay, if you make this a 4 that means that up to four threads can make as much progress as is really possible before theyíre blocked and pulled off the processor, whereas if I make it a 2 weíre blunting some threads prematurely, okay. Does that make sense?

Okay, so thatís what I liked about that and this is why I prefer the 4. If you put 2, 3 or 4 there it will be programmatically correct. If you put 2 or 4 there I think Iíd be correct from a design standpoint. I prefer the 4. Yeah?

Student:Are there Ė I mean, maybe this is a dumb question but why would we use a semaphore as opposed to, like, an if statement on the global variable? Is there any really good reason to?

Instructor (Jerry Cain):We could. In fact, Iím gonna talk about that specifically. You could Ė rather than doing this where you actually have the integer. Basically this tracks a resource. I like to think of this as the number of shopping carts that are available in front of Safeway, okay. And if there are five people that approach the store and itís a requirement that all of them have a shopping cart, they all flash mob the four shopping carts but only four walk away with one. So one is blocked until at least one shopping cart comes out the exit door. Does that make sense?

I could Ė and I think this is actually a really good question so pay attention to my beautiful answer here. That I could have just put a global integer here and said it equaled to 4. I could have had this check to see whether or not it was greater than 0 and if so, acted on it, but then I have the separation between test and action that was problematic in the ticket agents example. Does that make sense?

Well, you could solve that by having an exposed global integer and a binary lock like we did for the ticket agentís example but then what happens Ė and you have to think about this. I donít really want to write any code because I donít think I have to.

Rather than just blocking on this semaphore and letting the thread manager decide when you can get the processor back, what youíd have to do is youíd have to do some little while loop, okay, around and repeatedly check to see whether or not the global variable went positive from 0 if you were blocked on it. Does that make sense?

Youíd have to keep acquiring a lock and releasing it, acquiring the lock and releasing it because you canít check that variable unless you actually are the only one looking at it. And Ė Iím losing my train of thought here. Whereíd it go? The problem with that from a programmatic standpoint, and this is I think is a pretty good point, is that if youíre basically while looping you really arenít allowed to do anything meaningful until you get beyond the while loop.

So whatís gonna happen is youíre gonna be hogging the processor, maybe in the same time slice youíre gonna just keep reacquiring and releasing the lock just to confirm that itís still 0. Does that make sense?

Thatís whatís called busy waiting. There are some scenarios where busy waiting is actually fine. It usually is in the case where you have multiple processors and you expect some other thread running on another processor to release a resource pretty quickly. But in a single processor environment, which is what weíre pretending we have, thereís no reason for a thread to spinlock and keep checking the value of a global variable because itís not gonna change until somebody else gets it. Does that make sense?

So this right here is this very clean way to say, ďYou know what? Iím not making progress. Let the thread manager pull me off; put me on the blocked queue. Only when someone signals the semaphore that Iím blocked on will the thread thatís blocked on this thing ever be considered for the processor.Ē

The alterative is to use the global Ė exposed global with binary lock, programmatically correct but it encourages busy waiting and busy waiting is like the Ė probably the Ė I donít want to say the worst thing, the worst thing is having, like, a race condition exposed, but itís as far as correct coding is concerned itís the least good in terms of design because it wastes processor time that could otherwise be shared with people who Ė for the threads that really can get the work done, okay. Does that make sense?

Two second question, four-minute answer. Okay, you guys are good with this right here, okay. Thereís that. I want to start talking about a couple other things. I have two related examples. One Iíll actually write code for and then the other one Iíll just talk about the design.

I want to start thinking about more practical problems. Iím gonna frame the next example in terms of just FTP downloads, okay. I know FTP is kind of this 1990ís technology, but we all still use it, okay. We actually go and fetch files. We actually use programs that use FTP, but let me just assume the existence of this function.

I have this function and Iíll call it download single file. And what Iíll do is Iíll give it two things. Iíll give it a const Rstar. I call it a server and Iíll give it a second name called path. I know you know what this means. Server is basically about the computer thatís hosting the file that youíre trying to get and path is basically relative to where the web directory or the FTP server is behind the scenes, how to get to the particular file of interest, okay.

So this is basically the computer it lives on and this is effectively the file name with directory structures, nested directory structures funneling down and drilling down to where the file lives on the server, okay. The return value here is the number of bytes that weíre downloaded to pull the entire file over. Does that make sense?

Okay, what I want to do is I want to write this function called download all files. I want it to return the total number of bytes that were downloaded as basically the sum of all the sizes of the files that are downloaded. Iíll call it download all files. Iím gonna assume all the files are hosted on the same server.

Okay, but I am going to give you Ė thatís Rstar, the files an array of files on that server, and the number of files in that array. Now, two weeks ago Ė or a week ago for that matter, if I asked you to write this certainly on an exam youíd be dancing a jig because itís just a four loop, okay, with a plus equals going up and building up a return value.

But in spite of the fact that itís the same computer thereís some problems with that. But just pretend that the server is capable of hosting as many simultaneously requests as possible, okay. Does that make sense? What youíd rather do is youíre rather spawn off N different threads, okay. Does that make sense? N threads where each one is dedicated to pulling over one of these files, okay. Does that sit well with everybody?

Okay, so Iím gonna assume that run all threads has already been called and this is running as part of some thread that was spawned in the main function, okay. So Iím already dealing with a multithreaded environment. What I could do is I could declare something called total bytes and said it equaled to 0 and I can be prepared to return total bytes.

Youíre not necessarily sure how thatís updated yet but you can be sure that each of the N threads that Iím gonna spawn off to download a single file is gonna somehow do a plus equals against this thing right here, okay. This is functioning somewhat as a num tickets in the very first example except weíre adding to it instead of minus minusing from it, okay.

Now thread new doesnít return anything, okay. So what has to happen is that I have to spawn off N threads in addition to passing the server and one of the file names to the thread, okay, so that the thread can call this function.

I also want to pass the address of this integer right here, okay. Does that make sense? And a lock thatís designed to protect access to this because youíre gonna have several threads trying to plus equals potentially at the same time, okay.

So Iím gonna do this semaphore, Iíll call it lock. Iím gonna set it equal to 1 and thatís Ė this is just shorthand for what would really have to be there. And then Iím gonna do this, 4 int I is equal to 0, I less than N, I ++. What Iím gonna do is Iím gonna call thread new. I donít care about the debug name but Iím gonna call this function called download helper.

You may ask why I donít call this function directly. The function thatís passed right here to thread new has had the void return type. But even if it didnít have a void return type thereíd be no way to actually catch the return value from the thread new environment. Okay?

So what really has to happen is I have to call this proxy function that sits in between this one and that one that knows to call this one and also to accept its return value and do a plus equals against this thing right here, okay. I have to pass in a few arguments. I have to pass in server. I have to pass in files of I. I should pass in address of total bytes and I should pass in lock. That means I should pass in four parameters, okay. And thatís all I want.

Now there is a problem with this, the setup already, but Iím just gonna implement it like this is the okay thing to do. But conceptually you know whatís happening here. Basically this thread is being the typical manager at a company where he doesnít want to do anything except delegate, okay.

And this thread has the responsibility of pulling into these files. It happens to have N employees or N people it can hire on an instant like it just does right here. And it gives each one of them a task of downloading each of these things in succession. Does that make sense?

This download helper has to be a function that returns void. Iíll call it DH for download helper. And it takes these arguments, const car star server const car star path int star, letís say, num bytes p, for pointer, and then it has this semaphore Iíll call lock.

Now the semaphores, remember, are pointers themselves so they donít have to Ė you donít have to pass the ampersands there, you can just pass lock itself, okay. So you have a hook on the master copy of the integer that needs to be plus equaled against. What has to happen is that you want to do this, letís say, bytes downloaded and you wanted to clear that ahead of time because you want to do Ė actually, I donít have to do that. Iím sorry.

And you want to set it equal to the result of that function. Download single file where you pass in server and you pass in pass. It looks like itís being done sequentially but itís not. There are several there Ė there are N minus 1 of the threads trying to call this same exact function to download the files in parallel, okay. Does that make sense?

Itís in the same spirit as the type of thing you have to do for Assignment 6, okay. The reason you catch the return value is because after you let this thing run and do its work, as a side effect of this function youíre just supposed to assume itís on file and full appeared on your host machine.

But afterwards what you want to do is you want to semaphore wait on the lock and all the other threads are quite possibly waiting on because once you acquire that lock you are the blessed thread thatís allowed to plus equals against the single integer that you have a pointer to.

So num bytes p plus equals bytes download. Then you go ahead and you release the lock and then you return. Thereís no explicit return value here. The thing that feels like a return value is actually a return value via reference via this point that you have a side effect of downloading the one file youíre supposed to and youíre also supposed to update this variable to be that much higher so that when the thing is returned it returns presumably because all threads have returned and contributed to this thing, okay.

So when this happens it really is the accumulation of all the bytes that have been downloaded, okay. Does that make sense? Okay. If Iím silly and I accidentally acquire the lock before I call download single file itíll still return but itíll be even slower than it would have been had you just not used threading at all and just done the download single files sequentially.

Because this just means if I put this up there and this is serving as a binary lock then youíre putting the very important time consuming function inside the critical region so that at most one thread can be involved in the downloading of a file. Does that make sense?

So itís imperative that this be outside the critical region and we only have one critical region that it has to come after because it has to appear somewhere it has to come after you download the file, okay. Does that make sense? Okay, now thereís one problem with this right here. Do you have a question?

Student:If you had, like, 10,000 files to download would it make all 10,000 threads at once?

Instructor (Jerry Cain):It will in principal it would. Thatís a scalability issue that Iím not concerning myself with. Iím assuming that weíre dealing with something like 40, okay? Or even 100. Most thread systems, including our own, actually has a limit on the number of threads that can be reused. Iím sorry, that can be spawned off.

Our system is like 500. Some systems itís like 1000. And in principal really sophisticated systems can actually reclaim threads that have completed and reuse that thread space for something thatís created afresh, okay. Does that make sense?

There is a little bit of a problem with this. Iíve framed this in a way that might not make sense to you but I just want to make sure you understand it is that Iím assuming that run all threads has already been called and this is a function, itís actually running in some of the thread.

And so what I really want to happen is this is a child thread of main to really be spawning grandchildren threads, okay? If run all threads is already Ė has already been called and this is running, as soon as this is called it actually sets this up for all Ė or all N of these up on the ready queue immediately so that they start running immediately, okay.

I used the analogy Monday, I think, of a dog thatís already in the race giving to N dogs and throwing them back to the beginning of the race and letting them run, okay. The problem here is that the way this is coded up the job here is actually very easy. This isnít the equivalent of the manager of a company whoís delegating all of his work basically going home before the work gets done. You understand what I mean?

Itís one thing for you to delegate work and then to go home for lunch and then never come back. Itís another thing for you to delegate the work but then to wait for all of it to be done even if youíre just in your office surfing the Internet. You can actually just Ė you should hang out until all the work is done so that you can properly return the total bytes value, okay.

The way this is technically coded up at the moment it says, ďOkay, Iím gonna declare a local variable. Iím gonna Ė yeah, yeah, yeah, Iím gonna share a lock with all of my underlings over here so that they all have atomic synchronized access to the shared global right here.Ē

And I spawn them off and then I return immediately. Itís quite possible that I would return a 0 here because I may advance from the very last iteration of the for loop to this return statement. Okay? Does that make sense? Before any one of these threads makes any partial progress whatsoever.

Presumably this is a time consuming function, like, on the order of, like, milliseconds or even seconds. It would take milliseconds for it to advance from the very last thread to this one right here. Okay? Itís quite possible that maybe even one or two time slices all of these threads could be spawned off and it could return before that makes any work whatsoever.

So what really has to happen is right there I really need the manager thread, the download all files thread, to really block and not go anywhere and certainly not advance to the return statement until it has verification that all of these guys have completed. Because if theyíve completed then the manager knows that this thing has really been built up to have the true return value. Does that make sense to people? Yes? No?

Okay, so what do you do? Well, not surprisingly you use concurrency and you use semaphores. So basically implant thread communication, thread-to-thread communication. The reader-writer example we had the reader and the writer communicating in this binary rendezvous way. When I do this Iím talking about the crisscross of semaphore signal and semaphore wait calls so that each one can tell the other one that there was an empty buffer or a full buffer, okay.

There was this one to one relationship between reader and writer there. I really have a 1 to N relationship with this setup. I have a single master thread right here thatís supposed to do all the work. It elected to spawn off N threads to get the jobs done because it can take advantage of parallel computing right here, okay, and download many of the files simultaneously.

What really has to happen is I need about six inches more of board space. What I want to do is I want to declare a semaphore up here and Iíll say a children done and Iím gonna set it equal to 0. Iíll do the same thing there just to make Ė there really is a semaphore new call.

What I want to do is I want to use this children done semaphore basically as this connection to each of the threads that itís spawning off. I wanted to do this for hence I is equal to 0, I less than N, I ++. I wanted to semaphore wait on children done.

Now I havenít passed children done to that thing yet, but I will in a second. What I want to do instead is to change this to a 5. I want to pass down children done as an extra parameter. I have to abbreviate because Iím out of room there, okay?

So what Iím basically doing is Iím giving, like, itís almost like a little baby monitor to each of the threads, okay, that Iím spawning off. And when each one of them is done they go, ďWah,Ē into the baby monitor in the form of a semaphore signal and when I hear N of those, okay, I know that all of the threads have completed. Does that make sense to people?

So the signature for this has to move over a little bit, semaphore, Iíll give it a different name here. Iíll call it parent signal and then before I return over here I will semaphore signal the parent to signal. This is the ďwahĒ into the baby monitor and this thing is actually aggressively for looping, okay, and a semaphore waits on this thing not once, but N times, once for each of the threads itís spawned off.

Programmatically each thread signals this thing exactly one time. So I expect this thing to be signaled exactly N times. I need all N of those signals in order for this thread to know that itís done. Does that sit well with everybody?

And then once I have that I can advance to the return statement knowing that itís safe to return total bytes there because all of the N threads I gave birth to have actually done their work and died. But as a side effect their legacy was to plus equals my total bytes integer, okay.

Yeah.

Student:Is there any way that thereís a way Ė it seems like thereís a way to increase the number of N semaphore and is there a way to decrease it [inaudible]?

Instructor (Jerry Cain):Well, semaphore wait certainly does decrease it. If this is surrounding a 7, semaphore wait brings it to a 6, okay. So semaphore wait is like a minus minus thatís guaranteed to be atomic and itís also a block if the number inside happens to be 0. Semaphore signal is an atomic plus plus and not much more than that. Okay?

Student:So you could initiate it to N semaphore children have not done, I guess? And then [inaudible] until the lock is Ė

Instructor (Jerry Cain):Right, but I have the Ė our version of the semaphore, some more recent libraries have decided to do this even though this is an argument against it, youíll notice Ė and this is mentioned in the handout. We donít provide a get value within method on the semaphore. We could ask for the value of a semaphore, okay. And we could say, ďOh, what is the value now?Ē And it tells you 7. And you go, ďOh, Iím gonna act on that 7.Ē Right?

But it may have changed by the time you get a chance to act on it because in theory if you have a lot of threads the time between the return of get value within and the code that acts on that value could be separated by seconds, okay. Exaggerate it. Think about it in terms of years, which is what it really effectively feels like at the processor level, okay.

A lot can happen in years, okay. So you donít necessary Ė you canít trust a value that was acquired from within the semaphore and act on it until youíve actually released a lock on the check, okay. Does that make sense? Now actually getting a 0, there are some situations where it would be okay. You could keep on looping and only break out once you get the value out thatís a 0, but thatís a busy waiting thing that I was arguing against when I answered her question earlier. Does that make sense?

Technically this is a little bit of busy waiting but it makes as progress as is possible until it blocks because not enough children threads have completed. There are some versions of semaphores. The one Iím thinking about are the ones that come with the 1.5 version and later of Java, which youíll learn all about in the autumn when you take 108.

Do you notice the semaphore wait right here, itís an implicit request to just do a minus minus; a minus equals 1, right? There are some flavors, not in our library but some more modern libraries where you can actually for a total of, like, N or 12 or 20 or 3 dozen or whatever, decrements against the semaphore and just call this once as opposed to exposing the for loop as an internal for loop instead. Does that make sense?

Okay, ours itís exposed. I think thatís fine at this stage of the game because I want you to understand the mechanics of whatís involved in order for this thread to block, okay. And itís not technically busy waiting so itís not really a bad design, okay. Make sense? Okay, question.

Student:Yeah, there is nothing to prevent all the threads from downloading into the same portion of Ė

Instructor (Jerry Cain):I didnít Ė not the same portion of the file. My assumption is that each of these files is actually different. And Iím just assuming Ė I didnít mention it explicitly but Iím assuming the download single file is the thread save function that doesnít actually interact with other calls of the same function at the same time, okay, which is technically not true because two download single files may have to create at the same directory on the host machine, and that would be a little bit problematic except that the make directory command is implicitly atomic on the operating system anyway.

Iím sure it is. Iíve never read that but Iím sure it is, okay. You got the setup here? Yep.

Student:Is there any reason not to, like, in [inaudible] when you secrement it there and just semaphore wait once at the end?

Instructor (Jerry Cain):But the thing is Ė if you semaphore wait you might wait on Ė you want it to semaphore wait after itís become 0. Thereís no way to do that. Like, semaphore wait will succeed if itís positive and youíre making it initially positive. All youíre gonna do is make it N + 1, okay, or take it from 0 to 1 at the end. But itís, like, you actually want it to Ė the only way you can block if itís semaphore waiting on a value of 0 and you really do want this thing to halt, okay. Does that make sense? Okay.

Some version of the library, and actually we canít initialize Ė even though a semaphore in our world can never go from 0 to a negative number, some versions Ė the Java library does this as well, allows you to initialize a semaphore with a negative number, okay. That seems a little weird but if I were to initialize this semaphore to be negative N + 1, and then I had a single semaphore wait call here, it would have to be signaled N times before it became positive. Does that make sense?

So thatís what I think the two of you are trying to get at. Itís just not supported by our version of the library or our particular thread library. Yep?

Student:So you can [inaudible] the function together you make it one of the semaphores like with positive have a [inaudible] of counters and some of the counters at the end?

Instructor (Jerry Cain):Iím sorry, what? Oh, I see what youíre saying. So in other words youíre thinking, like, some how do a Ė

Student:[Inaudible] or is it thereís an each [inaudible] thatís in reference to one [inaudible] so you donít really need to have a global counter.

Instructor (Jerry Cain):Iím still Ė Iím not quite understanding. I think I know what youíre saying. Are you just asking this thing to pull, like, an array of Booleans or something like that?

Student:Thatís [inaudible].

Instructor (Jerry Cain):Into an array, yeah.

Student:Of elements?

Instructor (Jerry Cain):Right.

Student:Each?

Instructor (Jerry Cain):I see what youíre saying, yes. I have seen that before. What he is suggesting, I think itís pretty clever although I donít Ė I think itís clever but I think itís just a little bit more work than it needs to be. Heís setting aside not just one integer but an array of length N where each of these things can write without fear of race conditions to a slot in the array thatís dedicated to that thread.

And then once you get past this point youíd still need the childrenís done semaphore, you can go through and safely do all the addition yourself there. Right? Thatís actually a fine idea. I actually Ė I canít even say that itís a bad thing. In many ways itís actually pretty good. The only thing about it that it might be problematic is that, I mean, the number N here is huge. But even thatís not that big of a deal. So thatís a great idea. Yep?

Student:Reference you back to the question two questions ago, if you made children done equals N and you replace the for loop with while children done does not equal 0, would it work then and just like a closed while loop?

Instructor (Jerry Cain):Well, you canít do equals 0 on childís done. Iím writing this as shorthand but itís not really an exposed integer. This one doesnít actually Ė if the semaphore did provide a get value of method or function there are a lot of scenarios where that method Ė that type of functionality breaks down. But this would be one where it would work because itís only gonna hit 0 once.

So that is true but itís interesting to spoil that. If you want, like, after youíve done this Assignment 6, you should go Ė you already know enough Java to digest the syntax, just go and read, like, the two or three pages of the concurrency model in Java 1.5. Youíre gonna read it anyway if you take 108 in the autumn, just so you understand all the things that are available and more sophisticated for our libraries, okay.

I just wanted to minimilize I wanted to. Basically weíve used this package for so long because it really is lean and clean and very easy to digest in full. So you have to do all the interesting things in terms of the atomics, okay. You guys doing okay?

Okay, I do want to make it clear that when I initialized this to 0 I may get down here and I may spawn all these things off and in theory semaphore wait against a 0 and block immediately. Does that make sense? I may actually get swapped off right after this closed curly brace but not get inside the for loop immediately. I could get swapped with the processor as this download all files thread.

It might be the case that 50 percent of these things actually complete and promote this from say 0 to 6 because there were 12 child threads, okay. And this thing would come down right here and it would happen to notice Ė or not notice but it would benefit from the fact that this thing had been promoted 6 times. So it would make 6 immediate for loop iterations Ė or carry through all 6 of the iterations immediately before itís blocked on the seventh.

Itís not a problem, okay. Itís technically possible for the download all files thread to exit before the download helper thread does. Iím sorry, before any of the 12 download helper threads exit. Now you would think thatíd be a problem but this is the scenario. This one blocks the 12 different threads that I spawned off all get this far and they get swapped off just after theyíve returned from semaphore signal here but before they actually call the return instruction to emulate the closing curly brace. Do you understand what I mean when I say that?

So all swapped threads could, like, right before here be swapped off the processor. And this thing could get the time slice after thatís happened; get the processor back and say, ďOh, wow. Look, I actually went through this thing 12 times and I can return an I do.Ē Okay?

Youíre not Ė I mean, if you want to be as completely realistic about the emulation as possible you can do it. But you have to effectively understand that this function is really over when SS Ė semaphore signal returns. And that to the extent that you needed the information to flow and be synchronized the way it is it still works, okay. Does that make sense?

In Java you actually have the option of releasing the lock after the closed curly brace. Thereís a key word in that language that doesnít exist in C and C++ called synchronized. Youíll become very familiar with it next autumn, that releases the lock after youíve formally finished the method. And I say formally finished after youíve gone past the closed curly brace, okay.

But I donít care in this situation because all I really use the semaphore for was to get a meaningful full total bytes value. Make sense? Okay, so thatís Ė oh, go ahead.

Student:[Inaudible] blocks before the [inaudible], right?

Instructor (Jerry Cain):This one right here? Yeah. Itís a one line body of a for loop, so just this is right here and like that. Is that what youíre asking?

Student:Yeah.

Instructor (Jerry Cain):Okay, very good. Okay, so what I want to do is I want to set up a big example for Monday, okay. All of the examples have been focused primarily on either one or maybe two synchronization directives. The handout that I have you out today Ė gave out today Ė has this great first 2 or 3 pages that was written ten years ago but it hasnít changed. It hasnít changed in 50 years, really, much less the last ten years.

It describes all of the different patterns that you have to be sensitive to or situations you have to be sensitive to and the patterns you use to be sensitive to actually make sure that you donít have race conditions and you avoid deadlock. Itís all about protecting global variables in a binary lock Ė or a critical regions situation and implanting directives for two threads to communicate with one other Ė two or more threads to communicate with one other, okay.

And so itís good stuff to read. Iíve hit on all of it in the past three days Ė or past three lectures rather. The large example and itís kind of Ė itís a little intimidating. Itís actually larger than any exam problem. Itís probably the merging of two past final exam questions from, like, ten years ago. Itís a great problem, okay?

It is the ice cream store simulation and all Iíll do is Iíll set it up so that you know what all the players will be in this big grandiose ice cream store, okay. Weíre going to have ten customers, okay. Thereís going to be a customer function. Weíre gonna spawn off ten of those things and weíre gonna actually know how many ice cream cones each of the customers order. Itís gonna be between 1 and 4, okay?

Thereís gonna be a cashier that each of the ten customers approaches as theyíre ready to pay. So thereís a little bit of contention and I think thereís already clearly a flavor of currency and race condition going on because these ten customers have to approach this cashier and the best metaphor I can think of is when your mom, when you were going with her a little kid to the market sheíd have to go to the deli and sheíd have to potentially edge out and get atomic access to that little number thing.

She pulled 33 or the 94 or whatever it was, and you always looked at the number and it was like 22 away and you go, ďOh, my God, weíre gonna be here forever.Ē Okay? But there certainly is gonna be thread-to-thread communication between all the customers, okay, and this one cashier. Make sense?

Thereís gonna be a single manager thread Ė Iím being very cynical about managers but this manager doesnít do very much either. What he does is he approves or disapproves of ice cream cones, okay. He doesnít make them himself, he just approves and disapproves of them with a Ė like a coin flip is what really happens.

Theyíre gonna be between 10 and 40 clerks. The reason itís 10 and 40 is because every single customer is going to give birth to a clerk thread Ė one clerk for every single ice cream cone that needs to be made. So the people who are ordering, theyíre really impatient, this is real life. They want Ė they have four ice cream cones to be made, they want all four to be made in parallel, okay.

So the customer never sees the manager but these ten customers interact with 10 to 40 clerks, order the ice cream cones, they accept the money, make the ice cream cones, but all the clerks interact with the manager. They have to acquire a lock on the managerís time, okay, because the manager is overwhelmed if more than two people are in his office at any one moment.

So he can only accept one person in the office with one ice cream cone so thereís no confusion as to which ice cream cone heís approving or disapproving of, okay. Does that make sense? So weíre gonna run a simulation where there are up to 52 threads running simultaneously and thereís certainly gonna be 4 different types of threads, okay.

I want the manager to basically arrive at the store and not to leave the store until heís approved the number of ice cream cones that he needs to approve. I want each thread Ė the clerk, to only Ė to live as long as is necessary to make a good ice cream cone and hand it over to the customer. I want the customers to be able to order their ice cream cone, get it, go and pay for it, and leave the store. I want the cashier to know that heís rung up ten different customers. Does that make sense?

Okay, so to the extent that you can read the problem statement between now and Monday, thatís great, although donít worry if you canít because Iíll certainly review this at the beginning of Monday.

But even though parts of the simulation are certainly a little contrived, theyíre contrived specifically to bring out some scenario where you have to deal with concurrency properly, okay, and use semaphores to either foster thread communication or to manage binary lock or access to a resource, okay. You have a good weekend. I will see you next week.

[End of Audio]

Duration: 49 minutes