Transcript


Search in video
0:00
all right good afternoon everybody let's get started so today's topic is going to
0:06
be a synchronization among multiple processes but before we get started I
0:11
just wanted to remind everybody of a few important things coming up since we're
0:17
about to finish up the term so the first thing is hopefully you're all very much
0:23
aware that all of the labs in six double-o form must be completed and
0:28
passed and checked off in order to pass this class so you have until the end of
0:34
the day on Friday to get all of your labs checked off that does not include the design project which is optional but
0:41
if you're doing any of the design projects and you also must have that complete by Friday you cannot use any
0:48
late days beyond Friday ok we're going
0:53
to have two lectures this week and one more next week and then we'll have the last quiz during finals week on Thursday
1:01
December 20th and I've put here the time and the rooms most of you should come to
1:06
10 to 50 unless we send you an email stating otherwise and the last thing is
1:13
that evaluations for the course have opened and we really really pay very
1:20
close attention to the evaluations and to your comments so please take the time to evaluate the course and give us a
1:27
constructive feedback on how we can make it better for next time all right any
1:33
questions before we get started ok so so
1:41
far we've we've learned about how we can run multiple processes on the same CPU
1:48
where our operating system whereas in charge of switching from one process to
1:55
another via time sharing ok and you can imagine however that even within a
2:02
single process you might want to further subdivide that process into multiple
2:08
computation threads which may or may not be able to be ex Judit in parallel and so especially as
2:16
technology has evolved especially in the last decade or so we've moved to the
2:22
world where instead of continuing to improve upon our single processor cpus
2:28
we've started to implement multi-core CPUs so we have multiple cores sitting
2:34
on the same chip and we want to make use of them and so what we want to do is if possible we want to try to execute
2:42
instructions in parallel and so yeah a core is the main processing component
2:50
of your CPU so you can imagine that it's not the entire CPU and that they might
2:56
be sharing memories and things like that but it's the main processing portions of
3:02
it so you can imagine that you could do you know to add operations if you had two cores rather than just one okay any
3:09
other questions yes each core could have
3:16
its own register file okay all right so so now you know when we have these
3:25
multiple threads of execution there's two different types of threads that we
3:30
might have we might have you know some multiple independent threads where the
3:36
only thing that they're competing for is some kind of shared resource in which case for the most part they can operate
3:42
they might be able to operate in parallel unless they actually need to be using that shared resource at that
3:49
particular point in time and alternatively we could have the multiple cooperating threads so the idea here is
3:57
that they would be communicating data information to each other and they're trying to actually solve a larger
4:03
problem together okay so in the case where we have to have the threads
4:09
communicate with each other we have to alternate of how they can do this communication the first is what we
4:16
called shared memory and so in this model with a the multiple threads are
4:22
using the same address space and so in order to communicate with each other all they have to do is store to a particular
4:29
location in memory and then the other thread can read from that same location in memory alternatively we can have a
4:37
message passing mechanism for sharing information and here the idea is that
4:44
now the address space is different and so in order to communicate from one thread to another you actually have to
4:50
send explicit messages so when we think about you know the pros and cons of these two the implementation in the
4:58
shared memory system is very simple all we're doing is just loads and stores
5:03
which were very familiar with doing the problem with it however is that the
5:08
different threads you know have the potential of stepping on each other's toes if you're not careful okay in the
5:16
message passing system you don't have the issue of stepping on each other's toes but there's a lot more overhead and
5:24
so today we're actually going to focus on the shared memory model but we're going to talk about how can we make sure
5:31
that we have synchronization between our different threads so that they don't step on each other's toes all right so
5:39
whenever you're doing things in parallel you're probably gonna need to do some form of synchronization and there could
5:46
be multiple reasons for why you might need to do the synchronization so for example suppose that you have you know a
5:53
process that wants to fork off a bunch of parallel threads and then before
5:59
continuing it needs to make sure that all of those individual threads completed the task that they were
6:05
assigned to do okay so this is what we call fork and join and so we have to have some kind of synchronization that
6:12
allows you know us to know when it is that all of those processes that were operating in parallel finished their
6:19
tasks another example that's very popular is the producer consumer so the
6:25
way that this this works is basically you have two threads one that's
6:31
producing something which the other one needs to consume and then other one which is consuming what it is
6:36
that the first one produced so clearly just based on the names you know there
6:42
is a dependency between the two where the consumer can't consume something until the producer has produced it and
6:48
so once again you'll have to have some kind of synchronization between the two
6:53
and then the last that we want to talk about is mutual exclusion and so when
6:58
you have shared resources it's potentially the case that you're not going to be able to execute two things
7:04
at the same time and so we need to have a way of specifying which one of the
7:10
threads gets to have access to that shared user to that shared resource so
7:15
that the at any given point in time only they're using that resource and and no
7:21
other threat all right so what does it mean to be thread safe well you can
7:28
think of multi-threaded programs as if it's running on a single processor okay
7:34
if it was running on a single processor then basically our operating system would be responsible for a time sharing
7:41
between the different threads and you would expect a particular output to be
7:47
produced by this unit processor well a thread when we talk about thread safe
7:54
programming we say that even if we have multiple processes operating in parallel
7:59
we expect that the output of the program is going to be exactly the same as if
8:04
you were executing it on a unit processor all right so for the rest of
8:10
today's lecture we'll we're going to assume that we actually have multiple units that can operate in parallel and
8:16
we're going to talk about how do we do synchronization between these two and why why we might need that all right so
8:25
here what we've got is you know a producer and consumer which is a very
8:32
common problem that we have and we see that each thread on its own has a
8:37
sequence of instructions that it's going to execute so the producer is going to
8:42
execute some instructions which we'll call you know X and after it executed those instructions
8:49
its produced a character which it's going to store into the variable c and it's going to send that character to the
8:56
consumer the consumer is going to receive this character C and then it's
9:02
going to use it in order to execute some sequence of instructions what so within
9:07
each of these threads we see that you know first we execute the first set of
9:12
instructions acts to produce the first character and then we send that character then we execute you know the X
9:20
instructions once again to produce a second character and we send that character and so on meaning that we
9:25
execute each of the instructions is sequentially in order similarly for the
9:31
consumer but at the moment we don't have anything that's telling us what's the
9:38
what's the relative ordering of the instructions across these two threats
9:44
alright so in order for things to work correctly we need to be able to specify
9:49
constraints across these threads so specifically we're going to use this
9:55
sort of rounded less than sign to indicate precedence all right and so
10:02
this says that it's we need a to proceed B so let's think about you know what are
10:09
the precedence constraints for this producer consumer model that we have
10:15
right here can anybody think of you know what we need to have be true
10:24
exactly okay so we basically need to make sure that we're not trying to
10:30
consume before we've produced it and so that's indicated with these red arrows and or we can say basically that sense
10:38
of I must proceed receive a lot okay pretty clear do we have any other
10:46
constraints that we see here
10:59
and I'm will happen before Sendai plus one because we know that within a thread
11:04
instructions are executed sequentially but you're close yeah exactly
11:15
okay so because we're using a single variable ski in order to communicate
11:20
between these two threads we need to make sure that our consumer has consumed that a previous value that I produced
11:27
and put into my variable see before I overwrite it with something new okay and
11:33
so we have both of those precedents constraints - to worry about between these threads now we could make the
11:41
precedent constraint be a little more relaxed if instead of using a single
11:47
character or a single memory location to communicate between these two threads we
11:52
use a buffer of size n okay so if I have a buffer of size n what this allows me
11:59
to do is that my producer can get up to n characters ahead of my consumer right
12:05
does everybody see that great so now
12:10
instead of having to have you know receive if I proceed send a via can you
12:16
just it can go up to a proceed of this side receive of I needs to proceed send
12:22
of I plus n okay so the way I would set bookie implement this is what's in
12:29
what's called a ring buffer so let's say that we have a buffer that can hold up to three characters and initially this
12:36
buffer is empty and both our consumer and producer are pointing to the first
12:41
location in this buffer okay so first thing that has to happen is we have to
12:46
produce something right so our producer is gonna run and let's say you produces a character c0 it puts us into the
12:54
buffer now one of two things can happen either the consumer can consume that character or because I still have space
13:00
and my buffer the producer could produce something else and so in this example the producer produces another character
13:06
we put that into my buffer and then it produces a third character now I've gotten to the point
13:12
where my buffer is full okay so if I cannot have the producer run again
13:17
before the consumer runs at least once and so the next thing that happens in our timeline is that the consumer goes
13:24
ahead and reads the c0 which was the first character that was written okay
13:30
and then we proceed in this manner where now it reads c1 at this point we have
13:35
two freed up locations in our buffer and so now the producer can go back to
13:41
writing again and you'll notice that what we mean by your ring buffer is that once you fall off the end you just go
13:47
back to the beginning and so the next time that you write a new character it's
13:53
going to go into that location zero of your buffer okay all right so let's take
14:01
a look at how we would go about implementing the synchronization requirements between our producer and
14:08
consumer using a shared memory model where the variables that are shared between these two threads are our n our
14:17
buffer of size N and our pointers in and out so in is pointing to where the
14:23
producer is going to put something into the buffer and out is pointing to where the consumer is going to read something
14:29
from the buffer okay so our code that I know this is C but hopefully most of you
14:37
can figure out what this relatively simple code is trying to do essentially
14:42
what it's doing is the producer is running a send routine which is going to take the character that it wants to send
14:48
it's going to put it into the buffer in the location indexed by in and then it's going to increment in by one mod n so
14:55
that it can wrap around back to the beginning when it falls off the end similarly the consumer is going to read
15:03
a character from the buffer at location out it's gonna then increment out of mud
15:09
and and it's going to return that character okay so does this code work as
15:15
it is yeah but so why doesn't it work yep sure
15:35
and even before that you know it's possible that the consumer is gonna run
15:40
in this case before I've ever produced anything right so let's try to figure
15:46
out how do we solve this so we introduced a new data structure called semaphores semaphores are basically it's
15:56
an integer that's a value that's greater than or equal to zero and we have two operations that can work on these
16:03
semaphores the first is a wait for a semaphore so what happens with weight is
16:09
it basically makes the thread wait until the semaphore value is greater than zero
16:15
once it's greater than zero then it's going to decrement that semaphore value
16:20
by one and it's going to now proceed with the instructions that follow that weight operation okay the other
16:27
instruction that we use with semaphores is signal so when we're done with some
16:33
point of synchronization or using a shared resource or something like that we're going to signal the semaphore
16:39
which is going to make the value of the semaphore be incremented by one so now somebody that's waiting on the semaphore
16:46
can start running so the semantics
16:52
guarantee that we have is that if we initialize our semaphore to a value K we
16:58
are ensuring that sends that signal of I is not is going to proceed siga
17:05
sorry signal of I is gonna proceed weight of I plus K okay so let's take a
17:11
look at how we can go ahead and use that in our producer-consumer but so just to
17:19
you know make sure we're all on the same page we're going to start with a very you know simple example where what we
17:25
want to do is we want to use semaphores in order to establish some order of precedence between these two threads a and B okay
17:33
so a consists of five instructions a one through a five and we know that within
17:38
thread a their instructions are going to be executed in order similarly B
17:44
consists of five instructions B 1 through B 5 and those are going to be executed in order but we want to add an
17:50
additional constraint that says that a 2 should proceed before in this example
17:57
okay so how would we go about doing that well the first thing we do is we define
18:02
a semaphore okay and so our semaphore is going to be initialized to 0 and we have
18:12
this arrow here which is indicating that precedence constraint it's saying basically I need to complete a 2 before
18:18
I run before and so how do I make use of this semaphore that I just defined it's
18:25
relatively simple basically at the beginning of my arrow I have a signal s
18:31
so as soon as a 2 is done I can Al signal that the 4 can go ahead and start
18:38
running so I use that by signaling the semaphore s and similarly on the other end of my arrow I have a weight for us
18:46
so V 4 will not run until a semaphore s has been signaled ok any questions about
18:52
that yeah and there's potentially yes ok
19:07
is this like blocking and notifying
19:14
similar I mean so yeah and then just one of them though was going to actually get access to that semaphore and we're gonna
19:20
talk a little bit more about the details of that in a moment any other questions okay great so
19:30
another way that we can use semaphores is to deal with resource allocation
19:36
right so we said that sometimes we have you know a limited number of resources that must might must be used amongst a
19:43
number of threads and so what we can do in order to to deal with that is to also
19:49
define a semaphore this time instead of initializing it to zero and signaling
19:54
when you know a particular situation has occurred what we're going to do is we're
20:00
going to initialize it to the number of resources that we have so the number of resources in this example is K and so
20:07
now any process that needs this resource is first going to wait on that semaphore
20:13
so as long as we have resources available the weight is going to succeed and it's going to reduce the value of
20:19
the semaphore by one as soon as we have used up all of our resources then the
20:25
semaphore value is going to be zero and so then the next thread that asks for the semaphore is not going to be able to
20:32
get it until one of the other threads signals the semaphore s because it's now
20:37
done using that resource and so once again we have a resource available for our use alright so let's try to use
20:47
these concepts in order to fix our producer-consumer problem here with our
20:53
size and buffer okay so we're going to introduce a semaphore which we call characters and initially we have zero
21:01
characters okay so in order to specify that I want my producer to produce
21:07
something before my consumer consumes it what I'm going to do is I'm going to
21:12
signal characters at the end of the producers sequence of code so once it's
21:19
produced a character it's going to signal characters which is going to increment the value of the semaphore by
21:25
one similarly on the consumer side it's not going to run until it gets ahold of the
21:32
semaphore characters right so initially the characters semaphore is equal to
21:37
zero it's not going to be equal to one until the producer has produced something and now the consumer can go
21:43
ahead and and run with it so this is going to take care of which precedent
21:51
constraint that we were talking about
21:58
just that sense has to occur before receive and we also have you know a
22:04
buffer of size n and that's going to control you know how many elements we
22:10
can put into our buffer but you know what's still not right about this code
22:20
yep yeah so I could you know produce more
22:29
than n values before my consumer has begun to consume anything okay so we
22:35
need a little bit more synchronization before our code is going to work correctly all right so what we're gonna
22:43
do is we're going to introduce another semaphore okay this semaphore is going to be called spaces so not only do we
22:51
want to indicate how many characters the producer has put into the buffer we also want to know how many spaces do we have
22:58
left in our buffer so that the producer doesn't overflow the buffer okay so
23:04
initially when our buffer is empty we have n spaces in the buffer so we initialize our spaces semaphore to N and
23:11
now before the producer runs it first has to make sure that there's actually space in the buffer okay so if there's
23:19
space in the buffer then it can go ahead and execute if there isn't then it's just not going to be allowed to run and
23:26
so that's gonna prevent overflowing of the buffer before the consumer consumes
23:32
at least one of the characters in the buffer so we start off the producer by
23:37
waiting for space once it has space in the buffer it's going to put a value into the buffer at location in
23:44
increments in and then signal characters and now our consumer is going to wait
23:50
for characters so once it's signaled that there is a character available then
23:55
the consumer can start running it's going to read from location out in the
24:01
buffer and when it's done it's going to say oh now there's an extra space available because I'm done processing
24:07
this particular character okay any questions about this
24:18
good so you'll notice that there is in parentheses at the top of the slide this
24:24
caveat which says that this is going to work but it's only going to work for a single producer and a single consumer so
24:32
who look we're gonna you know try to understand why what can go wrong if I
24:39
have multiple producers or multiple consumers okay now in order to understand that we're
24:46
gonna shift gears for a second and we're gonna take a look at the following problem so suppose that I have two users
24:53
that want to take some money out of an account okay and so let's say you know I
24:59
have two ATMs my account is six double O four and each one of these users wants
25:04
to take $50 out of the account alright so I have this function called debit
25:11
which is basically going to look at the balance in the account it's going to
25:16
decrement it by the amount I'm taking out and then it's going to update that balance accordingly right so when I have
25:23
these two users each trying to get fifty dollars out of the account what's supposed to happen well the first thread
25:30
comes in and assuming that C zero has the address of this balance of account
25:35
it's going to load that balance value into a register it's gonna decrement it
25:41
by a-1 which is the amount that I'm taking out from the ATM and then it's going to store that updated balance back
25:48
into the memory location that's holding the balance okay and so suppose I had
25:54
you know a hundred and fifty dollars initially in my account my thread one comes along it takes out $50 and now it
26:01
updates the balance to be a hundred then thread two comes along and it sees that
26:07
the balance is now a hundred it takes fifty out and we end up with a balance
26:12
of 50 and each one of the users got $50 okay so what we expected is that the
26:20
balance was going to drop by $100 and that you know we now have $100 in cash
26:25
amongst the two users imagine that instead of being executed
26:30
in the order that I just showed you the instructions between the two threads were interleaved okay so let's take a
26:38
closer look at what's going to happen in this situation so what happens here is
26:43
suppose that thread one starts you know and it's going to read the balance
26:48
that's currently in my account and in our example we said that's 150 well it's
26:54
possible that the way the order in which these instructions are going to be executed is such that thread two will
27:02
then execute its first instruction and so it too is going to read that the balance of the accounts is a hundred and
27:09
fifty okay so now each one of the users is going to get their $50 out but what am I going to
27:16
actually update my balance to at the end of this of these two threads is it going
27:25
to be fifty like I expected it'll be a hundred right so I took a hundred
27:31
dollars out by I only decremented my my balance by fifty dollars okay clearly
27:38
this is not how we want our ATMs to work or we're gonna have lots of problems okay so what we want to do here is we
27:48
want to introduce a new notion which is a notion of what's called a critical section okay so the concept here is that
27:56
it's the the three instructions that correspond to the load subtract and
28:03
store all has to happen atomically there's nothing that can come in between them otherwise I might end up with a
28:11
with the wrong value and so what we what
28:17
we use for this is a constraint called mutual exclusion but basically says you
28:22
know I define a critical section of my code and when I'm in this critical section exactly one of the threads can
28:29
be in it okay and so we're going to see how we're going to use that in our producer-consumer example in just a
28:34
second if we go if we now go back to our ATM
28:40
example and we want to fix it using this sum this special mutual exclusion what
28:46
we're going to do is we're going to define a new kind of semaphore where the
28:52
precedence constraints that we need to satisfy is that either a precedes B or B
28:58
precedes a okay we don't care about the order of which thread goes first but only one of them can go at a time okay
29:05
so how do we do that we basically have another semaphore and this semaphore is
29:11
initialized to the value one okay and so what this is saying that is that exactly
29:16
one of my threads can get access to this lock value one okay and so both of my
29:23
threads at the beginning of the code are going to sit there and they're going to wait on lock only one of the threads is
29:30
going to succeed in actually getting that lock and so at that point it makes the lock equal to zero and so the other
29:37
thread cannot get access to that lock and it could not be executing the same sequence of instructions until the first
29:44
thread that got the lock is done so when the first thread is complete then it's
29:49
signals lock and now at this point it's safe for the second thread to go ahead and and and have access to the accounts
29:58
okay and so as long as we use this additional synchronization couldn't lock
30:05
we're going to ensure that even if two different users are trying to take money
30:11
out of that accounts at the same time that that it'll happen in such a way
30:16
that the critical section is not interrupted so that you'll make sure that when the second guy goes to read
30:23
the value of the account it actually sees the updated value which is already deducted the $50.00 yes
30:34
the same time only
30:39
like in the previous example let's switch to the other read and vote
30:45
yeah so so this is actually a difficult
30:50
problem to solve and so in fact if you think about it you you kind of need
30:58
semaphores in order to make sure that I you know check this lock and update it
31:04
at the same time right and so in a moment we'll get to how it's actually
31:10
done but it you know this is it's not a trivial answer okay
31:17
so just before we get to that one other you know comment that I wanted to make
31:22
is to think about you know if we're gonna have these locks we also need to think about you know what should be the
31:28
granularity of this lock right so if I have you know a lock for every single
31:34
account that might introduce you know a tremendous amount of overhead you know on my banking system on the other hand
31:41
if I have you know a single lock for the entire banking system then that means you know I can only access one account
31:49
at a time which would be too prohibited right and so we might have you know some kind of middle ground where you know
31:55
maybe you say that all of the accounts that end in zero zero for you know have
32:01
to share a single lock and so you wouldn't be able to have two accounts that end in zero zero for get the lock
32:08
at the same time but at least I could have an account that's zero zero four and another one that's zero zero three
32:13
accessing their accounts at the same time all right so back to our producer
32:21
consumer problems right so now what we said was the problem was that we had
32:27
solved things for the situation where we had a single producer and a single consumer okay so now we're going to
32:34
augment our problem we're going to think about well what happens if I have multiple producers or consumers and so
32:40
in this example here we have two producers right so just a highlight you
32:46
know what the problem was if the instructions are to be executed in this
32:51
interleaved manner shown here then what's going to happen is both producer 1 and producer 2 are going
32:59
to try to write their character into the same location in the buffer okay not
33:05
what we want right we want to make sure that one of them is writing into it and then immediately incrementing the
33:11
pointer to point to the next location before the other process you know reads
33:17
the value of n so how do we do this we're going to use this new lock mutual
33:25
exclusion semaphore that we just introduced and so we're going to define the semaphore we're gonna have lock
33:32
initialized to 1 and we're going to have this critical section which is you know
33:38
reading or writing to the buffer and incrementing the pointer live within the
33:46
accessing and and giving up of that lock okay so at any point in time only one
33:52
producer or one consumer can be executing the this sequence of
33:58
instructions and so only one of them can be making the pointer change meaning
34:03
that it's going to be impossible for two producers to now write at the same location in my buffer similarly it'll be
34:11
impossible for to consumers to read from the same location okay does everybody
34:16
see that all right so basically we've
34:23
now you know added enough semaphores to ensure that all of our constraints are
34:29
satisfied in a system where we have even multiple producers and multiple
34:34
consumers ok so we had the space in semaphore which made sure that we didn't
34:41
overrun our buffer we had the characters semaphore to make sure that we produce something before we consumed it and we
34:48
have the lock semaphore which takes care of this mutual exclusion requirement in
34:55
the critical section of our code all right so this is pretty cool you know we
35:02
have a single primitive that took care of all of these
35:07
issues right so we were able to deal with both precedence constraints using our semaphores as well as the mutual
35:13
exclusion so now let's get to your question of how do we go about
35:18
implementing these semaphores and so the most common way that these are
35:25
implemented is that we actually augment our instruction set architecture to have a special instruction which is called a
35:33
test and set instruction okay so because a single instruction is atomic by
35:39
definition then what's going to happen is that you're going to be able to both
35:44
look at the value of a memory location and update it within the single
35:49
instruction okay and so you know these tests and set instructions aren't
35:55
they're typically very simple right so
36:01
like they might test is something equal to zero and you know and if it is then
36:06
set it to one all within a single instruction right but the idea is that if you're executing this instruction at
36:14
any point in time you have exactly one process that's executing it and so even
36:19
if you have two processes that are or two threads that are waiting on the same lock only one of them is going to be
36:26
able to get it because it gets it atomically okay all right oops I should have a sari
36:34
shown that okay so this is the most common approach which is to argument our instruction set architecture with this
36:41
new type of instruction and if you look at the details of their risk five
36:46
architecture it has such instructions for this exact purpose an alternative to
36:54
this which is less popular and it's also much more constrained is if you're
36:59
dealing with a unit processor where your kernel just like it when we first
37:06
started talking about operating systems we talked about a unit processor with a kernel that could not be interrupted if
37:13
you have such a system then what you could do is implement your semaphores using a system
37:20
call right so what happens when you do a system call when you do a system call you enter kernel mode if you enter
37:27
kernel mode and your kernel mode is uninterruptible then by definition nobody else is going to be able to come
37:33
and execute anything else during that time and so you guarantee atomicity by
37:40
executing your signal and lock instructions as a system call okay but
37:46
the more common is what I mentioned earlier which is this test and set instruction okay so we're almost there
37:56
but there's still some problems all right so we introduced these semaphores which
38:02
are allowing us to deal with the synchronization issues but let's you
38:08
know now go back to our ATM examples and let's suppose that I want to write a
38:13
function that allows me to transfer money from one account to another okay
38:18
and let's suppose that I have two users and the first one is trying to transfer
38:24
money from 6:03 one to the 60-below for account and my other user is trying to
38:30
transfer from six double-o four to 6:03 one okay so what does my transfer
38:36
function look like well now because I'm dealing with two accounts I have to access to loccs right so I'm going to
38:45
you know trying to get the lock for account 1 also try to get the lock for
38:51
account 2 then I'm going to update the balance for both of those accounts and then I'm going to release those locks so
38:57
does anybody see something that might be a problem here yes
39:13
on this level of course they so everyone was back there trying to eat
39:19
Authority
39:27
that's exactly right okay so this is basically just summarizing that so you
39:34
can imagine that the first thing that happens is thread one you know first asks for the 603 one lock and it gets it
39:42
thread to first asks for is the six double O four lock and it gets it now thread one comes along and it was the
39:49
six double O four lock well it can sit there and wait all day long because it's never gonna get it because the other guy
39:55
already has it right and the other guy's never gonna release it because it's sitting there and waiting for the 603
40:02
one lock which it's never going to get so what we call this situation is deadlock where neither one of the
40:09
processes is going to be able to make any forward progress bad situation which we want to avoid at all costs okay so
40:17
let's take a little bit of a closer look at this problem so there's a very famous
40:24
problem known as the diners to law staffers problem and and it goes like
40:30
this so imagine that you have a bunch of philosophers that are sitting around a
40:35
round table and they're about to you know be fed some delicious food and
40:42
between each of them sits one chopstick and they're all you know very polite and
40:50
they follow a very specific algorithm in order to be able to eat and this algorithm basically says that first they
40:58
pick up the chopstick on their left then they picked up the chopstick on their right and once they have those
41:03
chopsticks they can eat and once they're done eating they put the chopsticks back okay so what can happen in this problem
41:15
good luck right each one of these philosophers could grab you know there
41:21
are left chopstick and now none of them can grab the right chopstick right so
41:27
how do we solve this problem so first before we try to solve it let's try to you know make sure that we understand
41:34
the various conditions which caused us to get into this deadlock condition in
41:40
the first place right so the first is a mutual exclusion which is that only one
41:47
thread can have you know a given chopstick at any point in time right so I can't give the same chopstick to
41:55
multiple threats okay the second is that I'm using what's called a Holden weight model so once I
42:03
get a chopstick I sit there and I hold it until you know I'm ready to be able to use it so I'm not going to give it up
42:10
even though I might not have my other chopstick the third issue is that we
42:15
have no preemption which means that once I got my chopstick nobody can take it
42:20
away from me okay and then finally the last idea is that we're basically
42:26
entering this circular wait where each guy is waiting for the other guy to release their chopstick and the same
42:34
thing is happening to all of them and so none of them are going to release it and so we have deadlock so how do we deal
42:42
with this there's two possible ways of dealing with it the first is to try to avoid it in the first place and the
42:48
second is to actually identify that it happens and then execute some sequence
42:54
of operations in order to recover from it so let's think about how we can avoid
42:59
it in the first place so imagine that you know we have the same diners philosophers problem but now
43:07
we're gonna give them a different algorithm for how to pick up their chopsticks okay so we're going to number
43:13
each one of these chopsticks or each one of these resources and the new algorithm
43:20
that the philosophers are going to use is that they're first going to take the low number
43:25
chopstick then they're gonna take the high number chopstick then if they have
43:30
those chopsticks they get to eat and when they're done they put the chopsticks down so if they follow this
43:37
algorithm are we going to end up in deadlock I see shaking of head no that's
43:47
correct why not yeah that's exactly
44:03
right so the one that you know has the highest number chopstick will be able to eat by
44:10
definition and so by definition you don't have deadlock okay so what this problem is trying to to to make us
44:19
realize is that if we're careful about how we assign the locks for our specific
44:26
shared resources then we can try to avoid deadlock so if we go back to our
44:32
ATM example right where we had two accounts what might we be able to do
44:37
with these two accounts in order to avoid the deadlock problem that we had before where one guy you know got the
44:44
lock for one of the accounts and the other guy got the lock for the other accounts and now we're just stuck what
44:54
could I do instead yep
45:01
yeah exactly so suppose you know that I added these two instructions which
45:07
basically say you know a is the minimum of the accounts and B is the maximum of
45:13
the accounts and so you're always going to try to access the minimum one first and so both of them are going to try to
45:21
access now the six double O four accounts before they try to access the 603 one account and so we won't end up
45:28
in the situation that we had before where one of them gets one lakh and the other gets the other lakh and they're
45:34
just stuck okay and so that's basically
45:40
it for today where you know what we want to you know what we want to get from
45:45
today's lecture is that we can execute multiple things in parallel but the minute that we start to execute things
45:52
in parallel then we have to work read about synchronization and making sure that our threads are not stepping on
45:59
each other's toes and the way that we do that is using these semaphores which can deal with precedence constraints with
46:06
resource constraints and with mutual exclusion and then the last thing you have to worry about a force is to be
46:13
careful about how you assign these resources so that you don't end up with deadlock all right thanks everybody see
46:20
you next time