Synchronization 1: Semaphores

a semaphore is a synchronization mechanism so synchronization allows two or more processes or threads to communicate in a useful way specifically a semaphore consists of an integer variable s and a Q named Q of processes or threads so Q is a queue of processes or threads and s is an integer now when the semaphore is initialized s must have a non negative value and Q will start out empty now there are two basic operations on a semaphore and these are sem wait and send signal the purpose of sem wait is to tell the currently running thread to claim control the resource and make it wait if that resource is not available the purpose of sem signal is for one process to tell other processes that it is done using a resource and therefore that resource is now available to use to any process that is currently waiting for it now the specific mechanics that make these high-level ideas possible are the following SEM weight decrements s additionally if decrementing s causes s to now be negative then whichever process or thread was running when this command was executed becomes blocked specifically it is placed into the queue queue so the collection of processes in the queue are those that are waiting for some resource to become available signal causes s to increment if after the increment s is less than or equal to zero then that means there are still some blocked processes in the queue and one of them becomes D queued and unblocked and is thus able to run now if the queue queue is a first in first out queue and that means this is a strong semaphore otherwise if we don't have any guarantee about the order that processes are release from this queue then we say this is a weak semaphore now given all of this information the way to interpret it is the following we initialize s to a non negative value and we're essentially saying that s is the number of instances of a given resource that are available for processes or threads to use simultaneously s decrements every time one process claims a unit of that resource eventually s gets decremented to the point where it is negative meaning that all future attempts to claim that resource cause a process or thread to become blocked whenever a process of thread is done using the resource it must use the same signal command so that the waiting processes will know that they can now take a turn using the now available resource this code provides a high-level example of how you might use semaphores to achieve mutual exclusion in a program mutual exclusion is when certain processes are allowed to access a given resource at a time while excluding access to that resource from other processes in particular if you have multiple processes running then there will be some critical section in the code of each process which cannot be executed across all processes at the same time at least not safely the semaphore is what bounds this critical section to provide you with mutual exclusion the idea is this so this is pseudocode and we have this process here this is essentially a function we've defined that is the code that will be running in each of our individual processes or threads now the actual start of the program is here we have a main function so we launched this program we run the main function and this command carb again is executed and this is a simple sudo command that means parallel begin you'll see that when we are actually launching multiple processes using P threads the code is a bit more complicated but for our pseudocode we assume we have a very nice clean command and what it does is it launches the function command process with a parameter of one as one process or thread and it launches the command process with an argument of two in another processor thread and so on up to process n now n is a global integer that is defined as the number of processes we want to have running at the same time so after this main function execute we have one process running one copy of this code where the value of ID is 1 we have another process running another copy of this same code in parallel where the ID value is 2 and another with 3 4 5 and so on up to whatever in is so we have multiple copies of this exact same code running at the same time now what does this code do so this code has an infinite loop that keeps performing some work that is the critical section now this is for a model of computation where we have these processes running forever but of course you may launch processes or threads that are meant to do a little bit of work and then exit and finish so this while true may not be appropriate but it is often the case that if we have multiple threads running we want them all to keep doing work until some greater goal is accomplished or until the program is simply terminated so we have each of these programs running an infinite loop and the critical section is some code that actually does something here I've just put a comment but in not actual computation here but we could be accessing a shared buffer or a shared file or some other resource that we can't have all processes safely messing around at the same time so that what that's what makes this the critical section we bound this access to the critical section with a call to some weight and a call to Sam signal so let's say that inside of this critical section of the code we both access and times change the value of some global variable that all of the processes want to manipulate so I've defined a semaphore s to be initialized to the number of available units of a resource so s is basically the integer part of that semaphore description I provided earlier so let's say that we're accessing the file and only one process should ever access the file at a time in that case s would be initialized to 1 then we have n processes running if one of them says Sam wait then some other process also says Sam wait whichever one's said Sam wait after the first one get blocked and have to go into that queue and wait for their turn to run meanwhile the first one that executed Sam wait go to the critical section execute potentially modify or accesses and potentially modifies that file and then when it's done it says send signal which allows one of the other waiting processes to run and also access that file the following diagram will provide a way of visualizing what's happening here let's say we initialize some values we have s starting off at 1 and the number of processes will be 4 and so we have process 1 2 3 4 will refer to these as a B C and D now this Q is not the semaphore Q this is a queue of processes that are ready to execute so the OS is managing these processes all of them are ready to run this one is at the front of the queue so a gets moved on to the processor and gets to run so we'll move that off of that processor and it runs for a while and because it's running it's going to execute some wait and that will cause the value of s to go from one down to zero so s now equals zero now let's say that this critical section takes a while to run and so a actually has a time out it gets booted off the processor before finishing its work therefore before executing SEM signal so we have this Q of ready processes where a finishes and it's going to go back to the end of this queue now and s is now equal to zero now we also have a Q here and this is the Q associated with the semaphore which we've called Q now this is currently empty there's nothing in here but now that a has been booted off the processor the next process in line is B so we'll put B on the processor B gets to run now B is running this same code B will also execute some weight except s equals zero now so when B executes Sam wait the s goes down to minus one and because this is now negative B is blocked it goes on to this Q and it must wait for its turn to run so after B which was removed from this ready Q we have C and D and each of them are going to execute this same code so C will go on the processor it will also execute some weight that will cause it to get in line here s we'll go down to negative two and similarly D will also go on the processor it'll also execute Sam wait that will decrement s again putting D here as well so notice first that s when it has a negative value this value is the number of processes that are blocked and waiting inside this queue so when s has a value of negative 3 it means that three blocked processes are in this queue so finally a gets to run again because all the other processes are blocked so let me go ahead and clean this up so a has just moved from the ready queue onto the processor now a was already in the middle of executing its critical section eventually it finishes and it executes some signal when a executes Sam signal that allows B to go from the semaphore queue back into the ready queue and increments s to be minus 2 now after executing Sam signal a could timeout it could actually loop around and execute a sin wait again let's say that it times out after this point which puts it back on the ready queue but after B so this means that B now has a chance to run and recall that the reason that B was in the semaphore queue in the first place was because it had just executed some weight so when B gets placed back on the processor it comes back in already having execute this that means it gets to immediately go to its critical section so be execute its critical section and when it's finished with that assuming it doesn't timeout it will execute Sam signal which will once again cause s to increment this time to negative one which puts yet another process from this cue into the ready queue and then let's say at some point the finishes and it also goes back to the ready queue so at a high level that's how semaphores work this is very basic code you might use to have multiple processes that do some sort of mutually exclusive operation but we'll see a more complex example after we've talked about some other synchronization methods

Channel: Jacob Schrum

Views: 82,127

Rating: 4.9210763 out of 5

Keywords: semaphore, counting semaphore, synchronization, semWait, semSignal, wait, signal, decrement, increment, queue, process, thread, mutual exclusion

Id: p0SKPpC5r9U

Length: 16min 34sec (994 seconds)

Published: Thu Jul 28 2016