I'm the assignment has not been released. but let me start recording, and then I'll
morning everyone, I'm still morning.
So I start with my stage lecture 13.
So first off.
So great, it's great, sir.
od.
I'm not sure so right now it's currently saying it's do November 9. I'm going to extend that.
Guys, lb do at least the 11th hasn't been finalized that but it won't be do before the 11th I'll update it once the assignment is
what what's up okay so.
All right.
Okay, so, um, so So last week.
I was, I was at a workshop, it was a very good workshop.
But I didn't get anything else done. So, I'm a little behind right now. Up.
Anyway, let's.
So what the thing I know from talking to the TA is that most of you are still getting up
there, a lot of you are just getting how far you all with tutorial six missing all you should be losing all you should have basically done with tutorial five.
tutorial six is. Yeah.
Case yeah starting yes I figured a lot of you haven't really done much time on six.
Why want to do is talk about tutorial six. But before talking about the tutorial directly, there's some concepts that I need to discuss.
And so you'll notice at the beginning of the tutorial six it talks about the producer consumer problem.
And so there's a nice little Wikipedia page, talking about this and I'm going to talk about this.
So, Now one thing you should make sure I'll.
If you're thinking tutorial six is a breeze. Um, I don't think you're paying attention enough to it because doing all, so remember doing the tasks for tutorial six like doing all these tasks.
They're not hard.
The tasks are not hard at all, understanding what the code is doing is another question entirely. I'll be honest some parts of this code are still for me I kind of like, Oh man does weird.
And let me explain why.
So, what we're talking about this week and talk about with his tutorial is so.
Well I think I'll pick up today we will talk about his.
So concurrency is me.
So why is concurrency such a hard problem, what is what is with, you know, the problem. What we're really talking about we're talking currency is to.
So we're talking about compressor tour more process of threads running at the same time.
So, When we talk about concurrency.
We're talking about two or more properties interacting with some shared resources. So, what what's hard about this. What, what is the real difference when you're talking about concurrency from how we've been doing programming.
Up to this point, and most of your classes.
Um, yeah. Actually, I mean the only time I can think of concurrency really fitting into the curriculum before this is all you have it some with Event Driven Programming.
and you should have it in 24 six.
So, efficiency is is actually not the hard part. It's the coordination that's the hard part. So, so the.
When we say that when we say resources, resources,
files are typically files, or
mostly files on.
So basically this typically we think of it as a file, we're talking about a resource because most resources abstract as files but you can use a device or really up almost anything.
But the shared and but, no,
but shared memory is the probably the most tricky form of this is this gearing towards a new tech summer for kind of thing. Yeah, exactly.
Um, so.
Okay so so the stock part of that that's Car Wash talking about here. So when we say running at the same time, the interactive interacting. So, what makes this hard about this is, is really.
The interacting. So, what makes this hard about this is, is really.
So what's hard about this is the relative order of execution affects the outcome.
So, as a little side note here it's worth talking about. I've talked a bit about threads I think at this point I haven't I did talk about trends.
So, to recall though.
This, when we say execution context, we're talking about registers and the stack.
So now you've seen assembly language.
I do hate multi threading, and I'm going to explain why I hate multi threading up. So, a multi threaded process is a process that really has multiple execution context in it truly means you have multiple stacks, and each doc has its own set of registers.
So that means that it can the same process can be doing more that can be executing.
So remember, a multi threaded process is executing two or more instructions. At the same time, always. So I mean basically one execution is being executed for every thread.
Yeah, so it's so it's so it's very annoying now.
Alright.
So the real reason why don't like multiple, multiple.
That which other resources.
So, a multi threaded process is sharing it all its memory.
So yeah, multi threading and implementation of concurrency it is, but it's not the only implementation of concurrency.
So,
so do I dislike, it's not so much I concurrency is necessary.
And why and the reason why it is necessary because our computers are doing lots things that you have to deal with concurrency, but you want to do it in a way that's controlled.
We just think you have enough space two or more things just executing and then one rights to one variable another rights to a variable and they all like modify this data structure, I mean,
just to get an idea of the level of chaos here Just think of a very simple thing. You all know about linguists.
What happens if two threads are modifying a linked list at the same time.
So, um.
So, George.
What do you mean by this idea of atomic.
So, that is an important thing.
I don't think it means what you, what you're saying because it's high. Exactly.
So, there's a concept we talked about not I'll get to this in a second here but when you're talking about a topic that template so that's indivisible.
actually move the orange.
for older.
So, so just for example let's say when you do.
Um, I don't want to. I don't want to get into it I don't want to talk about assembly in detail. I'm just saying, because then that's going to get complicated I think will be much more confusing.
So,
so, so remember.
so I,
The easiest way to see this I mean I could talk, it turns out there is issues the micro level and it's actually more complicated I'm actually getting too detailed there I just want you to have this idea that instruction is actually a very complex thing
at the seat at how its implemented inside the CPU, that in order to.
It provides the illusion that one thing happens after the other happens after the other, but it's actually much more complicated modern CPUs it's when you start looking at what modern CPUs dude in order to run fast, it's just insanity.
Yeah, like, so I we don't even have talked about, you know, complex, you know things to really see the problem here so.
So think about this.
If you have two threads.
And they're both trying to modify a variable x, x is stored. You could say, in some memory address.
But it's also going to be in a register. So you're going to load x the value of x into a register, you'll change its value and then write it back to memory.
But if another thread is modifying it, which x is that going to get.
Will it see the same value as acts like it may in fact have been implemented but then if two reads from memory, it's going to get the on incremental value, they won't have a consistent view.
So I more than thinking about complex x you know instructions and stuff, just think about the this fact here of the registers alone store and in fact, just think about the ways the instructions can get interleaved between each other.
And you're going to have that state in one, but x is in ax as a concept as much as being stored in memory. That's one reason I wanted to talk about assembly, because a variable at the source code level.
That data is in multiple places it'll be in RAM, but it'll also be in a register and where it is will vary over time and the compiler keeps track of it, but because it has multiple places that can be.
That also means that can have multiple values at the same time is possible for x, to have a value of both five and six. At the same time, in a sense, you looked at a memory it's five look in the register at six.
The two arms synchronize the compiler knows which one is the correct value, but another thread right at the same time, witness I see a consistent value of memory.
And so if we want things.
So.
Oh yes, it can also cause me and also cause cooperating Yes.
Oh, Jason that's a really good example like that concurrency of two machines, modifying the likes variable.
The thing you can actually lose it, but it should be.
Well, when you club or something, just means you override it and lose data.
So, so can you use, so you have to coordinate. So what the.
So what was the key way we coordinate.
So, so you can separate data so if you, there are ways to do concurrency so that you just keep things separate not sure ideally that's what you do most times have private versions of the data you don't actually have have interactions, and then you don't
have to deal with this but if you do have to coordinate, you typically.
You know, so you know you have to do something that prevents. So what we want to do is.
if you're accessing a variable in that variable that you think it has one value up. So, the classic example this is and this actually turns into a security problem is
Tao.
No, no, all CPU cores have their own set of registers, there is no inherent coherence, unless you do something specific.
That's the whole point of this. So, when we say time of check to time of use. What the idea of that is, is what's this thing of some simple cover.
So, if x equals five
x equals one.
So let's look at this code right here.
So here's just some simple code here that just says, If walk is equal to zero.
So classically when we talk about locks. This is a binary semaphore in technical terms is what we want to implement here although this is not this is just an ordinary variable here that we're calling lock.
And so the idea is we say if lock is zero then. Okay, now we've set locked to one we do something that requires access.
And then you set the lock to zero.
William yes they're definitely read this. So, so, me I was I'm me I'm talking about what does it mean to lock things locking is what you do to prevent, you know, you know wrong access.
But question is what's actually happening here. So, This code is wrong.
In a concurrent context, this will not do what you want it to do.
What's wrong with this code.
Yeah, the operator. So when we say the operation is not atomic. What do we want to have be atomic what does that actually mean we want so when we talk about saving atomic we want something to be indivisible.
Um, so, I will tell you, each of these lines of code is atomic
in the sense of when we do the check for is a lock zero. It is an atomic operation that in the sense of, you're going to get a value of one, whether it's zero not
the first two lines together need to be atomic. Yes, that is the key idea, it's, you have to understand what we, you know.
Or is this just a new tax.
We want to meet tax.
Yes, we want a new tax, but this is not a new tax.
This is, this is not a new tax at all.
Could you not do you need the if statement, could you not just say lock equals one. Yeah, you need to check to see if the locks is disengaged first and your first say if the law, you have to check to see it zero because otherwise, you're taking a lot,
away from another thread, someone else is holding it.
Now what you know the real way you do this is you say.
So here I've just enhanced this a little bit so just me a little clear if lock. While lock is zero, you know, while lock is one.
You know we just wait here. And then we track it, and then we set it we do our thing. So, if we assume all this is kind of happening at the same time this kind of makes sense you know we spend was awkward lucky was one they could lock and only be 01 so
we're just spinning here waiting. And then once we get past here it's not one so it must be zero. And then we're just checking it here.
So we couldn't even change this to being, you know,
we gave and changed with this.
So this is
what I'm going to keep out there.
I'm going to.
So for this.
Yeah, I'm getting deadlocks yeah yes.
So this first one, while lock equals one means, this means this is just an. This is just an empty loop.
So right here this will sit here and wait for as long as we need, as long as long as one someone else is holding it when you get here, locked is not people one, and so on.
And so.
Oh, no.
This is wrong, sorry.
That's what you want here.
Sorry, that was so yeah so while this is zero.
So.
Yes, I should be,
what happens there multiple yeah So Alex you're seeing the problems here. There's lots of little subtleties with this. So I'm saying is this code is this code is wrong, because someone can come in and check.
So, Remember between the time.
So.
so this is the big thing you should know, you can't write this code correctly and see.
So P threads. so yeah so so.
so don't write your own because there's some deeper side.
So let me give you an idea here. So in the Linux kernel. They of course have implementation. So, just I'm kind of throwing around this term of some before.
I said before, is just a
while I'm going to show you in which go to my textbook here.
Okay so,
see if I can bring up that compare and swap.
No, It's not what I wanted to do.
Oh my. Sorry, I'm just.
right.
Let's go. Let's go to.
So, just want to talk a lot.
Oh no, it's just confusing.
So, have you ever seen out a.
So you normal roads, you have two lanes going by each other.
And then, let's say one lane gets into a more like let's say one lane is occupied. And so, because let's say someone's cutting down a tree or something and so you'll have these people sitting there with signs and those signs have two things that two states
one says stop.
And the other one basically says go.
And there are two typically people think on either end of this and ones and one of them says, Yeah, they're basically making sure that traffic only goes in one direction on there because otherwise, of course you'd have a head on collision, so you'd have.
So right now let's say they're going going north and going south. So the cars that want to go north, are they gonna wait while the cars going south go.
And then once you know things are clear, then the guys switch their signs and the cars want to go north can go into cars one and go south, have to wait.
That is exactly the same thing as a train semaphore, which is where you have two trains coming, they get to a shared piece of track, and they need to pass each other, how do they.
How do they make link, how do you make sure all the one train goes Let's share a piece of track, you have lights basically controlling things make sure that you stop you go.
It's a signaling mechanism.
So, A so that so accounting some before.
So we talked about a binary summer for a binary so for his most common thing we talked about a lock. We're talking about a binary so far but it can also be used as a signal to do things.
William I'm not sure about this lock prefix
comparisons mean that's not typically used in the assembly language code but again I haven't done much currency assembly language programming and it would probably depend upon the CPU whether you do that, but I wouldn't have a conceptual way of talking
about because, yeah, there are certain compare and swap a topic isn't a topic instruction Yes, you'll feel that that is that is that is exactly a comparison.
Yeah, in some, it depends on the depends on the CPU exactly what sort of it's either testing set, or it's an atomic swap of two variables, because if you do in a swamp of two values atomic Lee.
Then you just can check to see what the old value is, after you've grabbed a lot so you do a swap of the lock and you know and and to another variable you check it it's like if you after the swap the value is one it's like, Oh, darn it.
The lock is currently taken I can't do anything but if you have to do the swap. And then the value zero, like, Oh, it was unlocked and now it's locked.
So, I have the lock yay me, I can go do it.
So, we normally use binary some a force for locks.
They're also counting some, you know, counting some of wars.
But this is what he called a new tax.
But we're not wrong about that
is a specific need to use accounting so former binary some before. Well, it lets you count things.
When our side.
So let's see ever counter. If that you want to have multiple threads increment it.
No, no.
Don't ignore this this is like she she she she, because you can just use an atomic atomic variable for that up. We will be using counting Salesforce have uses when you want to see how many people in like a number of readers and number of writers and you
have multiple ones in different roles and then counting some of course can be useful.
It's not source number number. If you just need an atomic variable for keeping track of how many are there but this game too complicated.
Oh.
So, there are many standard prompts and currency and you can if you want to learn really how to solve concurrent problems, you probably they have these standard problems and you learn like well how can I make an algorithm to solve this problem, and they're
really nice little puzzles like force you really to think about it and they can be very tricky to understand exactly why one solution works by one solution doesn't.
If you want to see something.
you want to learn something complicated look up access.
That's a, that's actually an algorithm for solving,
kind of,
When you try to edit a file that is open I get an error the online regulations safety is so important. Definitely not.
It's not a sin before, that's a file lock.
What I mean so.
remember a similar for only. It's only something that makes sense if there's a shared memory.
So, in modern distributed systems. So I teach a class on distributed operating systems and if you look at how distributed systems do concurrency.
That's always through message passing, because you don't have, if you have many computers trying to work together, they don't have shared memory that they can just coordinate these have to exchange messages in order to coordinate.
So, so far as what we're with two different proxies, because no shared memory.
We're not necessarily because you can make shared memory. And in fact, in the tutorial, you make two processes that have shared memory.
But the.
But the basic idea so.
So the basic idea of a. No, that's a good question. those good question. um,
so the.
data.
So there's nothing for one with a producer to do it, you go to sleep and wait, and be woken up when there's Oh, I should now.
Do I now have no discipline to produce. So the key idea is a buffer.
So the consumer, the producer puts things into the buffer and the consumer takes things out.
So when the buffer is full.
There's no room for the producer to produce any more. So it just needs to wait until, you know, this I don't know how will, how will it not be full because the consumer is taking some stuff out.
When the buffer is empty.
The consumer should wait until it isn't empty.
Now, when we play with. Now, it turns out Unix
Unix actually is very good support for the producer consumer, you don't problem between two processes.
So in Unix, we have really good support for.
So, so what if both process need to rewrite a read, that's not that's not producer consumer. That's a, that's a different pattern. Well, yeah, you can just use a lock.
Yeah, you can just lock the file, and that's that's a separate thing. Um, But yeah, Unix. So
when do we see a pipe.
Remember when we do.
So if I do.
So if I, if I do.
So if I type this LS slash, then, and then I pipe it to less. This is a producer consumer problem. So now, let Ben is a large directory.
User because I use it and then now as a similar, I guess to use them. So, I do this.
So notice the coordination that happens when we, when we're running this
wild This is while this is happening.
Let LS has done a bunch of reads and now was doing a bunch of rights to say here's all my output here.
The rights are being paused.
Until less is ready for more data now let's go like I got this up. There we go.
And so as we hit the spacebar.
It is getting more data from LS.
Now, of course, less can also read a bunch more and then there's different ways of doing this I think actually what, um, what else does here is no sorry what what last year is may actually allow us to finish completely dump all this data and then it just
hasn't a buffer moving things but when we do the pipe Hopper, when we do this pipe.
Yeah, they do have file descriptors exactly, they do have also so in the terminal we use the.
notes that's.
What does I think it actually yeah
yeah this it's a system call.
So,
you call pipe, you give it an array of, you know, for two integers, and then it just, it puts the.
It puts the two file descriptors in there that are linked to each other, your actual data channel that we use for inter process communication right by is using return to file descriptors for the ends of the pipe.
Zero first read into the pipe pipe it wonderful is the right end of the pipe
up.
The man pages. So if it's a Eunice did kh. This is basically a system call.
other actual use cases for two pipes for bi directional communication between process. I know that's actually true if.
you could use two pipes. But really, there's also sockets sockets are actually bi directional, which is a network abstraction which we will, we might talk about the end but basically networking is abstract as sockets, and there but yeah if you want them
talk to us advice directionally then give us two pipes up.
If we're right called doesn't finish.
It's not so much. If it doesn't finish Why.
Why say it doesn't finish until it basically means that it's pause, it's literally sitting there in the middle of a right.
what's possible to send an option to read and write to basically how do you try doing a right and you can't do a right instead of waiting until the right as possible for to return error.
Yeah, so it's it's paused, but up, but you can make it so that when you do a read.
For example, and the buffer is empty, it's possible to set the reader basically make it a synchronous is the is the option you're looking for, you know, so if you allow for a serious thing that you will read it goes out there's no data and so you have
to try again. But by default, reading writers synchronous. That means they only return when the operation is completed.
And if there's a reason for the curl to think, Oh, this might be completed.
Then know if there's another process running so.
the technical term is block.
So, when, When you have a pipe.
And you try writing to it, and the other end of the pipe is no longer there. The other processes gone.
What, how do you think the colonel signals the error.
I just gave it away.
signal here, you get a sick pipe signal.
binding Listen, is by your listeners referring to sockets, which is a bit more of a more complex mechanism pipes are much simpler the unidirectional.
We talked about binding to a socket it's a bi directional communication thing but there's definitely some, you know, same ideas but more, it's more complex.
I don't understand kosher when you see the descriptor that causes the pipe to read write a file descriptor is just the name of the file that's open.
Pray for a six as web dev Yes.
Three Four sixes web dev Yes. Where's this option get passes over.
Oh, the option, it takes us when you open the file. The, the options are taking that as part of read of right it's options and how it opened.
So.
yo, specify your do not walking on a pipe, it would make no sense. It's kind of a point.
So, um, let's start looking, as I've talked to the high level let's start looking at the code here. So what's happening with.
So I've downloaded 3000 PC so let's look so when you're doing this tutorial, you really should understand exactly what 3000 pc FIFO does. Because what 3000 pc FIFO is is a producer consumer implementation that runs using pipes.
So the producer consumer problem the buffer is, yes. Well, it's not always locked, it's there's locking that happens and lots of different ways.
And that's part of things looking at the code to see how it works.
So, for this code here, this program basically just has a word list and it just sort of outputs random words from this.
And when you look at the usage what it says is, you give a number of event count, you should give it, give it single large give it at least 10,000.
You don't want to have it be too small, because otherwise you're not really seeing the proper things. I would recommend you potentially output this to a file so redirect output so you don't want to see 100,000 things output to your screen.
So, I'll put it to a file. The producer, the interval, and this thing's basically saying well the pauses between pause after each reader right so these this is basically a simple way of just, you know, this one's this opening every second or two seconds
so you can see the coordination between the producer and consumer but initially I can just run, if you want run this full speed is putting zeros and for both things.
Oh, yes classes been going on sorry I did not know about the fire alarm.
Oh, that sucks.
Anyway, it's recorded so you can see what you missed.
But let's look at how this code works. So first thing we do is we create we we create a random number. This is not a good way of doing random numbers, by the way, don't use it for anything we do this is really, I think I do have some code elsewhere that
does proper random numbers, fix it but as I got Yeah, we got a stupid round number here, and we do an argument like check and make sure you have arguments.
We set the counts protein consumption intervals these things. And then we make a pipe.
So, so we make a pipe here, and we give it the pipe file descriptors which are right up here as local variables are rare arrays here.
And then after we make the pipe. We do a fork.
So this is important to know that the file descriptors will be shared between the producer and consumer, which are now we have you know, so the producer is running is in the parent knows that he's in the child is the producer and the consumer is actually
the parents and see it gets here the file server it gets, and he gets this interval. and then we have these two functions that are running now at the same time in two separate processes.
The producer process. Also, if you look at the consumer process all it does is it just picks a word puts it in the queue.
And, and if there's a, you know, and then it sleeps for as long as the interval.
And then once it and then it just keeps doing this for as many events as and told it to and then it closes the pipe, and then says producer finished.
Producer does exactly the same thing.
Pigalle picking the queuing the word is just writing it to the pipe gang The next word is just reading from the pipe.
That's it.
Yeah pseudo random yeah it's not, it's when I say, whenever you say something pseudo random, when it's gentlemen it looks random, but it's actually generated by an algorithm.
I can be predicted.
Thank you.
We only want to call pipe in the child and no we have to call up.
So we don't want to call pipe in the child need to call pipe remit notice here, we have to call pipe. Before we do the fork.
This is very important.
The pipe happens here.
And then we have a fork here.
So, both the parent and child have the same file descriptors file descriptors are preserved over forks. So it means you both the parent and child have access to the same open files, but the producer just uses one end of the pipe and the consumer use the
other end. So this is very important that they use the different ones.
Because if they both, both writes the same one but just, well,
actually you, you can have multiple processes right to the same file descriptor. So you could, I think you can make this a multiple reader writer by having them both right to the same to the same pipe.
Just different time but I'm not sure if it actually works. I think that does.
Yeah.
So this is how you should be able to understand every line of this.
Doesn't matter if we change the ends of the pipe.
Change it how the pipe is rather critical so changes to it are likely to break the code
of your exchange the end of the child apparent yes that will very much mess things up because one end is meant for reading, and the other is meant for writing actually wait.
Yes. So, I'm
Sophie look here on pipe.
Hi ft zero first to read end of the pipe pipe ft one refers the right end of the pipe.
Oh yeah no yeah so yeah so what do I do this right in the.
If you look here, the consumer got zero, which is the end.
And the right end went to the producer,
doesn't mean it's necessary for the child of the producers apparently the consumer adapt doesn't matter.
That doesn't matter what does matter is that the consumer users zero, and the producer uses one.
This is definitely a FIFO.
And in fact, I'm.
all these same index per standard it's dinner. You're right. wait.
I know it does.
Yep. Yes, because found triple zero standard in, which is what you read from files group or one is what you write two which is standard out.
So producer needs to write before the consumer reads, technically No. But if the consumer reads before the producer has written the consumer is going to sleep until the producer is produced it will just block that read will not finish until the producer
is actually written sign so the consumer can read whenever it wants. It's just that read won't complete until the producer has put something into the pipe.
So,
now, this is 3000 pc FIFO this code is pretty simple. You should understand this, right I understand every line.
But
system calls we get from s trace are the calls that have finished as trace will actually tell you when a system call is in the middle of something.
So the colonel manages the rewrites system calls and puts process to sleep when appropriate.
Yes.
Exactly, that's exactly what happens.
So let's now.
Let's find.
So now if you go to 3000 pc rendezvous.
This is a problem, this is a much more complex program because instead of communication happening via pipe.
It's done using shared memory we still have two processes, we still do, you know, we still get the same command line we still do this, but notice instead of setting up a pipe.
We do an MMO. And this m map is very important to notice what it does, it does.
You know, protection read protection right but map shared this map shared map and all this means we're allocating memory.
I suppose mapping and file, but this map shared is opposed to map private. So this means that after a fork, this memory is shared between the between the parent and child, normally when you do an employee do a monologue for a large thing, it will do an
M map but it will save now, private, so that means that after a fork, it will be copied the shared memory allows for a shared address a portion of a shared space between the parent and child, and then we use that to do a shared data structure will walk
through that. On Thursday, because I am out of time now. Um,
so yeah because we are we are out of time here but look through this this whole thing here we have to initialize the shared data structure, What will you get asked.
And you notice the top it shared does a lot of things with this piece read library.
And so we're doing these things are so P thread is a library for doing threading, but in this case we're using it for communication team to process, there's really p threads all about interactions over shared memory.
So, thanks a lot guys I will see you on Thursday and will continue talking about this, and I actually have office hours right now after class, so feel free to come by.If you want to chat about things.Have a good day.