Okay, So i'm gonna start recording now
Okay. Good morning, Everyone Sorry. Few technical glitches there.
First off assignment. 3 has not yet, and then release host.
Tomorrow however. yes.
So yeah. right now, I think it's set to 9 11.
I'll probably put it past that. but I just wanna make sure I need to look at the calendar and decide exactly what it is.
But yeah, but not Don't worry about that what you all should be working on the tutorials tutorial 7 is almost ready.
Yeah.
So you
So you tutorial 7 you can start looking at if you want. if you if you're done with other things.
So if you if you want to. yet. Yeah, exactly. yeah.
So
So you have some more time on 5 and 6 by'm not sure if all the tas know that i'll make sure they they know that.
But still you should mean more stuff's coming so don't just keep push things off, cause you know there you got stuff.
Yeah, there's more material coming along. anyway. so I saw you know a 3 is based on
Okay, So so that's the logistics part now let's
You can make a shortcut for that
So we're now here in lecture 14 what I wanted to bring up here, though.
Was yeah, tutorial 6, because we have some more stuff to talk about in here in particular.
What I wanted to talk about is here. I want to talk a bit about deadlock.
You start talking about concurrency mechanism
I remember
I know there's I was gonna download all these
Okay, I don't know what I did there with it
There we go that's right good yeah
I'm just downloading all these chapters. so i'm trying to remember where they have something.
Okay, so let's bring these up here. So Oh, okay,
So if you look in here. So this is how the chat starts.
It starts talking about this
Good.
So okay, So ,
Creation. This talks about thread. so this is worth so condition.
Variables, bugs.
Here we go. This is what I wanted. want to show that.
So in here they talk about deadlock and that's the thing I actually want to talk about is these requirements
When we talk about deadlock we're talking about a very specific thing, and that's where they are there.
We are for deadlock
So when I talk about deadlock computer talk and currency bugs, right?
So deadlock is one
But it's worth understand deadlock because that's a couple of interesting properties.
So first of all, let me describe to you a problem. This is what I was hoping to find.
The
Okay.
Oh, can you not actually view the dying Floss? Oh, there it is.
Okay, So here is the classic dying philosophers problem and this is what's used to explain the concept of deadlock.
So what the story goes is you have a bunch of philosophers they're sitting around a table.
They're trying to eat spaghetti or noodles.
I personally think this works better is, instead of there being forks.
These are chopsticks. because, the idea is that any of these people to eat need 2 utensils.
You can eat pasta with one fork so but you can't really do much with one chopstick.
So so think of these as chopsticks they're sitting around, and so, but they're all so engrossed in their conversation.
They all want to keep talking, so they're not paying attention to the food, but they need to eat, so the question comes
So she all see this basic problem here that
How do you make sure that the philosophers eat so you could have so so
So consider this this thing of the basic approach. You grab your tens on the left.
You grab one on the right. then you maybe put the one the right down.
They put the one on the left down
So why can this result? in everyone starving what's the scenario?
Oh, yeah, everyone's holding a left for Yes.
Yeah, they all grab left the same. they can never get to.
So
So what if you got a 1 s time out so if you don't put down the if you don't get the right utensil you put the left?
You cancel down. So the problem with this one if you're having a timeout.
It can still repeat.
So this Yeah, you still repeat, you could just have them all just going up, down, up, down, and never making progress
So you can add in random timeout that mostly works
So the pause is an eating. However, the system basically so so the random timeouts work.
But by the nature of randomness, those things you now everyone probably won't, starve.
But you'll have pauses, in the eating of arbitrarily long, so they'll just sit there and all be like kind of doing their dance of things, and no one's eating so so so delays can work you know delays can
work with. So the So this is where we get to the concept of of what is required to do.
You know Why is it dying's philosophers from what Why is it a problem?
It's because there's 4 conditions or hold
Some mutual exclusion, so that wouldn't why mutual exclusion is because each one you know, when you hold the you know, hold the you know chopstick, or whatever you're holding it, and no one else has it as well as
you have it. So you have it you know we don't have in this model that anyone can grab utensil from someone else.
Yeah, to order enough. Yeah, Toby, at 2 side of order.
No. Yeah. So mutual exclusion
So
Keep it in the map
Keep it in the metaphor here
No, you pre have
No! you preemptions.
So all these have to, you know.
They're a real philosophy no forks not real I didn't think some of the time was more mathematicians.
But there's there's a couple of different Silly it's a very silly little problem in concurrency that people talk about.
But it's it's fun to do about and it does make certain concepts very clear.
You know, if you think of this so so so why are we?
You know. Why am I talking about this it's really because if you look at these?
I mean we. This is a metaphor for a lot of situations.
You can think of this as instead of these being, you know, utensil.
These are like locks, and you need a certain number of locks in order to proceed with your thing like, let's say you're accessing 2 data structures, And so you need to have access to both data structures the same time So
you have to lock both, but if you lock one, and then you lock the other, and your weight arbitrary, long, holding one lock waiting for the next one.
Someone else, you know, if it is locked A and lock B.
And so now gets locked B. and then lock a you're in trouble, because both will each of you can end up having the lock and never letting go of it.
So you can. I mean there are definite ways of
Basically, we want to minimize the license of contention intention.
Yeah, you want to minimize the delays due to resource content.
So. So this is why, if you look at
So the classic way to avoid this
So so the deadlock is so so what's deadlock is specifically everyone deadlock is when the company stops.
You know. So this is Yeah. So so everything stops the whole.
The the progress of the computation
Hey, sir?
No good question. so it's a it's a specific situation it's really describing when we say deadlock, we're really seeing a situation where all these things hold
So yeah. So the So. So really, what what you want to do in a but in a parallel system
So that so, in general we want to do is avoid resource, contention.
So you go with one lock to control the resource you don't have any issue with with things being correct.
Things will always work. but you're leaving lots of performance on the floor, because the moment you hit the locked resource, everything everyone else, if they all wanna access in parallel, are gonna have to wait.
So you might say. Well, instead of having one resources, have lots of smaller resources, and so everyone can.
Just, you know, lock what you need. So instead of locking the entire data structure, you put locks on the individual portions of the data structure, for example.
And so now you know now, that makes a little easier, except the problem is, when you grab that if one part grabs part of the day one lock, another one gets another part, and they both are actually need what the other has you get this
conflict and you have, and and the worst case of that is, you get into some, you know you get this sort of thing, and then you get deadlock, and your entire system will freeze up.
You can tear our application, freeze up, and that is very bad.
So you know, there's basic strategies of this is like you know the classic way you avoid the dye phosphorus problem is, you know.
So, if
Is it typically very clear when deadlock occurs in your program?
No! so so
It. It feels like the free situations that exist where processes don't terminate.
But you wouldn't know it because of deadlock or something else. that home?
Yeah, yeah, exactly. it. it's deadlock is a very subtle thing.
Let's go back to the tutorial here
So we go back to the tutorial here and we go back to this code.
Remember we have 3 versions: 3,000 Pc. fiveo works fine.
You know that that that works fine but it's based on a on a fifo on a a pipe.
But you go to
Okay, so resolve the Pc. Fiveo. This was the easy version, this one you remember this one uses You make a pipe right here, and we use that to make our pretty soon consumer.
That both rights to. But then you run 3,000 Pc.
Rendezvous, and this one uses shared memory, and you would go like this.
One should be faster, but this one locks
Yeah, you're not doing async a weight and and c.
No, no, no, yeah, that that is definitely yeah you're not doing it.
Yeah, you you can't easily implement that and see async a weight are actually rather subtle mechanisms.
But but you but you have the right idea that we should be using different abstractions to do this.
And actually, if you look underneath how those abstractions are implement, they often use things like locks enough, but
So here's
Oh, yeah, right a few texts you're talking about it it's just doing a mutex that's what it's.
It's just I forget exactly what the terms is a couple of different versions of it.
So if you look at let's look at that
So you're saying like where is the few checks
That's what to Texas. Okay, until if you check system call queue.
Certain method of meeting question comes true
It's in the s trace so this is what happening. is This is the system call that's the it's happening when you do It's a system Call for waiting on it.
No notice. This is thus not complete. user space is that do not bite my computer.
Please shift.
See who came to visit here. This is shift She likes to come and invite the cables on my computer while I'm here.
When she wants attention. Yes, you do i'm gonna kick you off now.
You must learn.
He's in it letter by no no she'll just she will just she will actually unplug a cable if I she's actually stepped on my power strip before this is like Yeah, my the computer turns off So
don't worry she's fine I always find it funny when I kick her out.
She doesn't look back at me she just runs off it's like, okay moving on.
But yes. so talking about few texts notice few texts is fast.
8 allows for fast things. It is a system call, but it requires shared memory.
Oh, God! turning turning off an xbox! oh that is hilarious!
How do you know you might gain too much that turns off your Xbox to get attention
But but going to this, but so we're using the p thread library
So like the the clone system call is a linux specific that's not something like fork is kind of there.
But there isn't always standardization at the system. call level back and vary between version of unix like to go to Freebsd and potential, sees different system calls the P.
Thread Library is a higher level. Standardized interface is specified, and what knows the posix standards?
So that's just something
So That's just something. so when you look at the code here, and you see all these references. Do you see it includes search p thread.
That's what we're doing is we're including p thread some of for and stuff those are all
So
No that doesn't sound
There we go some weight. This is yeah. So so set some weight, some tri weight.
These things. these are all part of the p thread package.
So when you look at so we're including these we see some weights, and try week, you know all these things we're doing concurrency. We have a semaphore the 74 70 s here it's specified there.
Now, now, the question I have for you is
So 3,000 Pc. rendezvous deadlocks!
Why does it deadlock
So realize when I made 3,000 pc rendezvous.
It. was it shouldn't I didn't expect it to lock, so it's not so much the consumer producer take turns accessing memory space
What's happening is both the producer and consumer go to sleep at the same time.
Why, that seems to happen best I can see is that to be honest.
I'm not gonna be you let's look at
You have the consumer running, they call I mean we if you analyze the behavior of the problem.
The way it deadlocks is it's not in these other parts.
It's because they both go to sleep as they recall and so so.
Where is it there it's the
This con signals this is where you're using condition things somehow. I think this con signal sales i'll be interested to see what you all I think i'd be you know we'll see exactly what happens here.
But I What you have to do in order to fix it is when they go to
So this wait for producer.
So notice the difference here. This is basically the same code.
So in this one to get the next word. So the original version, we first you know, we get the current one, you know.
Basically we get the you know, he is the entry. So this is the entry here, and we basically lock the entry in the queue here.
And so what I you doing here is we're basically saying some weight is basically saying, I want to wait until this is available, and once it's available, I want to take the lock.
No, this is the whole checking the value and Then taking it So some weight is us waiting for the summer for until it's available.
And so at this point in the code the semaphore is available, and and then what you know there we just says, and then we go like, If you were to, as you know, we have the entry we're checking it the end
entry is empty, so that if we get to an empty entry, since they go in a circular thing, we go like, okay.
The buffer must be. there must not be anything less for us to preserve and fill this century.
So we post, which means we release the lock. We wait for the producer to wake us up.
Then we grab the walk again, lock the entry, and when we check it again now, presumably after we wave the producer and do this, then there should be a word there.
So if there isn't we single and error. So this code is, you know, basically pretty straightforward in the sense of you know, each entry in the queue has a lock.
So that's cause what is what is the data structure here so let's look at the
Okay, so? So if you look at the queue what's the queue, how's the queue?
Declared. So here's the queue is part of the shared memory. That's the key entries Queue is is of type entries, and each entry is just a word and a lock, and the idea is we have a you
know we're just cute you know the producer produces words, and the consumer takes the worms out very simplistic.
It's not real work, but again this is a demo program
Well. but this queue, you know, like fewer. Okay, yeah.
So here.
Yes, this is the one we are looking at. So this is the way this is the get next word.
So the consumer's way for producer if there's not a word There it's done in consumer after waiting, and then it does this.
So this is this all. seems, you know, straightforward here.
But look at this version. This version works and here again again we're here and get next word.
It gets the semaphore, and then it checks to see it.
But but instead of an if we have a while, and this while Loop basically keeps shocking to see, Oh, it's an empty entry. and then for that full set, we implement increment our weight count So we have a finite number
of times we're going to do this so we give up the lock.
We sleep for a microsecond so so we don't sleep for a second.
We just leave for a microsecond. excellent
You sleep, or at least microseconds no it's microseconds.
So. Yeah, so it sleeps from one microsecond at least. No, this isn't precise It may sleep for more, but it should sleep at least for that long, and then it calls wait for pretty, sir, and then it locks it again.
and if it turns out we've we've waited for too long.
Then we we exit out of this loop so we're willing to try, however, many times the weight count Max And so way Count Max is by default 2,000 times. So we'll wait basically up to 2,000
microseconds. I eat 2 s
Is it you sleep there for preventing race conditions like the the reason why you have the sleep in here is because otherwise it's gonna Peg the cpu, because it will just keep trying.
Again and again and again. So you want to give the other other process time to do some work.
If it hasn't done it before checking again.
We don't wanna Wait long but we're just it's like, Okay, I'm gonna take a break and then try because that's a basic thing when you're trying to see?
If Something's available it's just like I am my office hours, and you come to see if i'm available, and I'm and i'm busy. You will go and then just say are You busy are You busy.
Are you busy? Are you busy? Are you busy? You go away and come back after some time, because you just kept doing that.
You might actually prevent me from getting i'm busy because i'll be distracted by you.
Keep coming in and bugging me. This is basically the same concept.
You have to left the you have to give up your use of resource to let the other one do that, and we give up our locks.
So we're not locking the entry we're not holding onto it, and
That that's not. It also allows constant which you're trying to do right. Yes, it does.
A lot of contacts, and so
I I will explain. spin locks in a second. That term does not apply here.
So we I I will! I will get to that in a second.
But so, but knows what this this this version works, but it pauses, because whenever it finds that you know this entry has been thing, it it tries it.
But then weights the producer. it then nothing happens. So basically what this means is the wait for producer.
So let's look at the weight for producer where is he
So wait for producer also.
So wait for producers actually very simple in the original one.
You lock the you lock the mute tax, and then, you know.
So now, you basically just you check a lot of the condition you text, basically saying, we're waiting.
And so this is basically just to say where it's a funny little thing with the P.
Thread Api. So basically this lock says we get the we're locking the condition variable, saying we want to have this thing for signaling between the 2 processes.
And then we say, this is the thing We actually wait in the queue, non-empty, that's where we get the message, but we also give it the mutex, so that if it turns out it has to go to sleep
it can release it. so someone else can change it. Yeah, this August get so complicated.
And then, once you, you know, once this actually has occurred, you unlock
But that's not what the working version looks like instead what we do.
Is, we calculate a time in the future. So we basically calculate time for 10 ms, which is tenth, you know, 10 million nanoseconds.
And then we say, we grab it, and then we do the exact same thing of
Sorry. what works? Yeah. So here we do the same mutex lock new checks on lock.
But we do. the version timed weight and we add in a new value a third value the timeout variable.
So that means that we're only going to wait for up to 10 ms that's it
So you look at the code and play with it, and even make changes to it.
If you want
No, I lost you
So. so now I have to explain something.
I have to talk about scheduling in order to explain the rest of this.
So when we talk about locks, there's this con so a spin lock is easy to explain.
So when we talk about a spin lock
So when we talk busy waiting all that means is while one you're just slooping, looping looping until something happens
So you don't actually want to just be doing a while one loop in a tight loop, cause that's just gonna make your cpu hot.
Use no power, it's it's of no use
Okay, so to understand. So so now is that good time to start talking about what the kernel does when you switch between a process.
So this is gonna be a little bit of a a diversion here.
Before I start talking about it. I swear I gotta check in here.
So what am I extracting you to get out of out of this code?
And what are you gonna and you'll see this when I give you the assignment?
I'm not expecting you to understand everything about semaphores and New Texas.
What I want you to understand is mute. Taxes are used to as a lock to prevent the you know, to prevent, you know, 2 things from accessing the same data structure, or whatever resource at the same time, and then condition.
Variables are used as messages to single between 2 things so like if you have, they're basically used to on day boots.
So one processor thread is waiting for a condition and the end.
So I just keep saying, Has this happen yet? Has this happened yet?
The condition variable. let's the other one say yup that's happened.
Yes, this state has changed to this that's Why, we have this Yeah. answering rendezvous.
Yes, so we have these. Yeah, Yeah. exactly.
So these So I want you to get that basic idea, and that this is how things work under the hood.
And we look in the Linux kernel. You will see examples of these things all over the place, because it turns out new taxes in particular are used.
I mean, are necessary all over the place in order to Keep things there, and I'm not sure of condition.
Variables actually use that much, and the Colonel will have to think as much.
But so not. but they do other things that are kind of like that
But what I want you to understand is that your mental model of how things are working is. You should always be suspect when you're talking about a parallel program, because you think you know how your program executes.
If you think of it in a linear sequence, you think it does this.
It does this. it does this. it does this But if you think of 2 things running at the same time. Your mental model is going to break. because those 2 things are going to be doing things that interact in a really weird way, and understand why
they're going to interact a really good way we have to talk about what what Cpu scheduling is.
Now this is where we're really going to start talking about how the kernel works.
So before I start talking about that and we'll be going into this next week.
You know this will be much. This is really why I kind of ordered things this way is that when you start talking about concurrency, you start going like what the heck is happening with the kernel what is it actually doing
this is very confusing, and so that's where you need the more complex mental model of what's happening.
So I see this as much as motivation for understanding how complex things are underneath, and you can't take things for granted.
3,000 Pc. rendezvous time out works because it doesn't take things for granted.
It never assumes that. well, of course, this condition is gonna happen when I wait for this, because i'm waiting this other process hopefully, but it doesn't always work out hence all the complexity of all the time notes oh, but let's talk
about something
So when I do, Ps. And I get all these things here.
These are all the processes running on my system what you'll notice is that there are, you know, as many fields you know there's the user of the process.
There's a process Id there are these things they saying various stats about percent of memory. Cpu.
These. This is all up you relate to memory. We will talk about this more later.
We haven't gotten there yet. But what I want you to pay attention now, and Tty is where is it basically standard in standard out?
Where are those pointing to so most these are all like they don't have a tty associated with them unless you get to cause there are background processes that are interacting the terminal.
But then there, ones like you know my processes here bash and stuff they're interacting with the terminal, and that's why you get pts one.
Those are Ttis that's what we discussed that's the difference price to interact with the user.
I wanna talk about that stop stands for status yeah you'll notice a lot of these are S.
Or hi, and a few other little late little letters here.
I have to look up for all these things I mean i'm curious.
And we're actually gonna see. Okay, so few of these things are the art state, for most of these are on the S.
State e. so no e Max was running Xor was running and the psaux.
So
Yes. Yeah. exactly.
Those the 2 month 2 2 big ones. I have to look up to see what I is, because I is
I think that's inner ions
No, no, no, R is definitely not for users our plus is not for users with root, because this is happening with usersoma, and it's in state.
R plus. So I have to look. I have to check to see what all the status is on.
I kind of forgotten some of these things. yeah, you know Z is for zombie
So, but the 2 states that really matter for us are the sleeping and running
Do. What was there a Z. here? I don't think I saw Z.
Now, would you, you price on these otherwise? So what is the difference between a process sleeping and running
So that's what it really mean what a process is sleeping it's waiting to execute, and when it's running it's actually on a Cpu core.
So the the basic model you should have of of how this works is
Are we trying to Cpu? So so
No, signals and interrupts are different things.
Signals are, have inter our metaphorically, like interrupts, but they are not, interrupts.
I'll i'll explain that difference in a little bit but so so i'm with a process executing it's an it's a it's in the running mode it's there
Oh, I stand for idle kernel thread.
Oh, okay.
That makes sense, actually, because I was noticing. If you look at the things here, if you look where the L. what the I was, the eye is always associated with the things in square rockets and the square bracket actually is is always is
actually a kernel thread it's not user space so yeah, so
Here we go. Yeah, on interoperable sleep, idle kernel thread are runnable or running.
Sleep on entrepreneurs in trouble, sleep waiting for a bed to complete stopped by a job control.
Is that the process, my priority, low priority, is a session leader.
In a multi-threaded Is it a forward process?
Group: Okay, ,
Carson, you ask me, do I have a root kit on my system?
I certainly hope not.
So
It's possible I have a little bit of my system I certainly hope I don't
Oh, there was a user
Oh, rt Kit
Yeah, that's not rude kit
There's a real time, kit that's where we all time cross the stuff.
It was a root kit it wouldn't label itself as a little kit.
Okay, came back. So
So
Or not that's wrong
Okay, So this is all getting to a concept of pro. The
So
Martin, I haven't discussed interrupts Yet i'm going to discuss interrupts very shortly.
This is this is that's not what it is so How does the Cpu switch between running a process and user mode and the kernel in supervisor mode
First off one way that the current. How do you switch between running in user mode and running it?
Supervisor mode on the Cpu, because user mode is running a process.
Supervisor mode is running the kernel because remember user mode, The the process only is access to its own memory.
It's all confined it can't do anything the kernel has access to all the system resources.
So we The reason we make system calls is because we want to ask the kernel to do operations on our behalf.
So the basic, you say, the simplest way to you know.
How do we? How do we switch, you know, from running a process?
Use mode and to the kernel and and going to the kernel. And in in supervisor mode the basic way is the problem.
Process makes a system call, and then the Cisco instruction calls Cpu to switch kernel mode, and it runs A.
You know the Kernel Dispatch
What if the what if the process never makes a system call what if it's just crunching along?
Then, if we didn't have another mechanism to stop the execution, so we would that so interrupt
So when you get an interrupt, is a hardware event that has to be handled by the kernel.
So what kind of things generate, interrupts.
You know. Keyboard
Keyboard, mouse.
So all the hardware in the system every time
So there are ways of minimizing the number of interrupts.
If you really get into how things work and there's buffers, so that they get bunched together. and a few things every hardware event generates.
Ram doesn't generate events because ram is stored well, i'm saying but like i'm talking about things outside the Cpu accept
I everything except for
Yeah, so well, I would mainly devices also.
So there's actually the Cpu itself can generate interrupts the keyboard mouse, when you move your mouth, or things that generates interrupts of the computer has to pay attention to
If if I just move my mouse on the screen, I do not click anything.
Will this action also lead to interrupts? Yes, periodically.
Yes, Now there are different architectures for this and there's ways to reduce the number of interrupts.
It generates. so it's not like every millisecond is just.
It's like setting a signal. But yeah I move my you can see my mouse cursor running across the screen right here as I do this.
The Cpu has to know this happened, so it has to get a little message.
About this
Yeah, we were talking about interrupts we're talking about hardware interrupts.
Yes, exactly so. What I have not discussed at this point
So when I put Sis call over here because that can be considered a software interrupt, That's another another true for
The next time we will talk about scheduling.
So so what happens when your computer freezes and moving the mouse does nothing on your screen.
What that means is probably a device driver has deadlocked it's waiting for a condition that never is going to happen.
And so and that's as well and that's why, it's locked up normally when we say a system is locked up.
It means Parts of the system have reached a condition for which they'll never continue, and that typically means they are waiting on some.
The device device Driver probably has locked up in the rest of the system is now dependent on it, and so the whole system is from it can be very complex, but it's essentially the concurrency bugs that we're
talking about you've hit one of those when your system locks up almost always
You can probably find what happened to Vlogs this long.
Maybe if it wrote successfully to the log no no no when there's a deadlock, the harder interrupts do happen.
It's just that no one's listening no but the deadlock is not so much the interrupts are happening.
It's that this the kernel is it processing them because it's trying to process something else.
Instead.
If you're if your mouse and keep are connected, but you are away from the keyboard, will it be interrupt normally interrupts only happen when there is something to report.
So my mouse just sitting here right now, there's no events is not doing anything.
There's no state change so what is there's no point in bunding the kernel, because there's no update.
It might have some periodic things like hey? i'm still here. but that's that's we don't normally do that we normally do instead is just it's just when there's some change so for example.
you're getting my system getting constant interrupts right now from the microphone and the video camera here.
Now there's another technique for sending data back and forth, but certainly some number of interrupts are being generated by the fact that I am speaking here.
I mean that's one thing about modern computers is they have to handle.
Lots of things happens. they have to handle a huge number of interrupts.
And how to make a system efficient in the face of that is but hardware's fast, anyway.
We're out of time there is much more to discuss here.
But we will we'll continue with this discussion and we'll start talking more about the kernel next week.
Have a great day