If you've got multiple processors either that's multiple cores virtual cores
in a
hypothetically a multi-core processor you want to run your algorithm or on
Multiple CPU instances so you need to split it up and the operating system needs to find some way of controlling all those different instances
actually you can still be beneficial on a single CPU
system because it might be times where part of your program is waiting for say network input so the operators will then schedule it in
another thread of execution
To do something
So let's start by thinking about what the operating system sees
when it's running a program and this is what's called a process and that's got a series of instructions and it's going to be
Executing this is the program this is actually not part of the operating system is it's the program but it needs to know we're inside
The program that is so that instruction say
But there's, also lots of other information that the operating system needs to keep track for a process a things like
list of open files
Configuration of memory and so on if you've got virtual memory
involved or
Paging there's various things that the operating system needs to keep track each of them has got a unique ID and you can then run
multiple processes at the same time
so one way you could break your program up into multiple chunks is to actually have multiple processes running in
for a while people did this they sort of
Will use the command a function in UNIX for example called fork you would split the program into 1/2 which would run off as
it was the other would have a new process identifier and the operating system would copy that block and
Create a new list of what memory uses a new list of the files they had open now these are point back to the same
files the same blocks memory allocations and things so that if you change one memory location it updated on the other side and things if
You changed a file seat to a different part of a file for example it would update in the others but
They would be separate processes and they'd have to have all the storage required to do that and that worked but
if you're breaking your program up so you can run your task on multiple CPUs
most of them are going to have the same list of files the same memory configuration the
Everything else that the operating system needs to keep track of the only thing that's going to be different is
Where it is in the program what bit of code is running from what part and so the idea that came along was ok let's
Have something lighter weight than a process and they called it a thread because you've got your thread of execution through the instructions
And what we have is that each process will have at least one thread of execution but could have many
So you have multiple threads of execution in your program so your programs running one thread
Which it starts off with that will then create another thread
Which does something and then another thread pratik and so on can do different parts they made last for the whole length of the program
they
may only last for a short part while that task being completed and so on
You may have multiple ones that get jobs from different things and so on how you structure your program
Doesn't matter but from the operating system point of view it's now
Scheduling different threads onto the different cause whether that's one to four however many you've got in your system so the idea behind
Multi-threading is a sort of lightweight way of saying to the operating system these are the different things I want running on my computer
Whether that's always part of one program
or multiple threads through multiple programs and the operating systems choosing which one of them actually gets CPU times on any of the CPU calls
physical or virtual that they have
available
Now that it produces if you were actually one program that you've split into multiple threads that introduces some interesting issues
Because you can get to the point where your programs can no longer do the task that you expect them to do a program which
Was just one single stream of instructions executing one after the other and so he knew the order they'd execute in two
to multiple strengths of instruction that are executing
Sometimes in parallel sometimes one after the other but you no longer have any
Control over the order that would happen because the operating system might put two of their threads on at the same time
Or I might let one thread run and then put the other thread on after the other and then go back and you can all
Control, where it's switch from one
to the other I can show this with an interesting program on my laptop
So what I've got here is I'm going to write a program that
adds up all the numbers from 1 to 1 million but I'm going to do that in two
Threads so I've written two with the Reds here creating threads the first one is this routine here
Which is called the hopefully thread function?
We've got a variable a which we're going to initialize to be 0 and I've declared this as a volatile
Variable just to tell the C compile and it will change
While it's running because otherwise you'd have even more problems so split in two so the first one is adding up the first
500,000 the second one
exactly the same so it's adding at the second
500,000 so what it's doing is it's adding up from
500,000 to 1 million and they're adding that's the same variable so go instruction he's going to fetch one
Adder on the next one and write it back and then the other one's going to fetch it
Add on the value and write it back and so on so then we then run our program
When we create both threads and then we wait for them to complete which is what this P
Throw joint is doing and then we print out the number that
We've got so if you just like to add up all the numbers between 1 and a million while I run the program
Then we'll see what result we get 500 times you'd billion so let's just compile this up
Not making mistakes the problems would compile this up and let's just run this program
and it's giving me the answer to eight six six eight nine seven four eight two two six zero
if I run it again I
now get the answer three three three nine six three eight two six seven two six I'll run it again I
get the answer three two six eight seven, oh four oh nine five Q one I run it again I get two for 307
501 five 490 which sounds like a phone number
Well this all this all converge on the right answer all leverage out or is this just one of those
completely
Well if you think about it
Should always be the same you've got you're adding up all the numbers between one and a million you should always get the same answer
It shouldn't be converging on something you should always be producing the same answer so something very very odd is going on on my computer
Something very very bizarre is going on we could write the program less in fact let's just write the program normally
let's comment out all this and we'll just write a very quick program that adds up all the values from 1
to a million so what I is less than or equal to 1
I'm sorry so it may be a single-threaded program now it's just going to run on one thread
And if we do that we compile it
We now get the same value each time
500 and whatever those so now we've done single-threaded
we're getting around certain we're getting the same answer each time so what's going on here well you need to think about what's happening in
This program, so let's just put it back to where it was
if we look at this instruction here a
equals a plus I then what this was telling this program to do is to fetch the value of a
whatever that is
then add on the value of I to it and
Then store the result back in a now if I just put that to one side and find my paper
Which is over here with my pens if we? Were to write that in machine code
I'll use the arm ship to do that because it just makes things slightly easy to see what's going on
We would have this is thread 1 so we'll call this t1 we're going to say that this is going to be an LDR instruction
To load a value from memory so they're loading to be registered let's use our 0
the value of a
We're then going to add onto
Our 0
The value of r1
Which is a register containing our loop counter that's the same as I on there and then we're going to store
the value of R 0
Back you know so that one Caesars have become 3 machine code instructions
so the way that the program is executing in one thread is it's loading the value from memory and
It's making a local copy of it and then it adds a value onto it
updates its local copy and stores it back
into the actual location and that thread keeps doing that into the loop so it loads it I
Had something onto it and stores it back loads it add something else to it
Stores it back now if we've got a multi-threaded system, which is what we had there, we?
also have another Steve hi Steve hi Steve and
in that case
I'm going to be here
loading the value I think value onto it storing it back
And I'm gonna be here loading a value adding something onto it and storing it back so I'm loading value
adding something on to it I'm loading value
loading a value adding something on to it
adding something on to it storing it back storing it back
and what's just happened Because other Steve had added something else on to it, while I'd load it on when I storm my back his update
doesn't get changed gets lost
Well that wasn't nice
So if we look at what's happening on the papal it's loading the value in it's adding the value onto it and then it's doing
It back but of course, we've got multiple systems and so at some point
this pro
Was going to start excusing the same code so let's cross this instruction out for now we'll put it back in a bit later on
And assume that at this point we load the value into the other thread
into our zero in
there
And then we do the add on in the same way
Dot and then we do the store back here
of our zero into a and we've got one a
Up here there an Singh and then this store actually happens after this store here
So what happens here is that these both end up getting the same value of a
And this has its value on in its local register this adds its value one in its local register this stores it back
Then this stores it back and of course because this is just story back here
It's overwritten the value that was stored there so the value that was added on here
gets lost so what we need to do is find a way to
synchronize these two things so that as soon as this is loaded the value in
And it's going to add something on to it it stops
This one from doing it and so there's a couple of ways, we can do that
The easiest way is that we have something that
both divide both Steve's or both CPUs have to access and so we could have a token let's use a floppy disk Microsoft Office Professional
1995 and what we're going to say is that I can only access an update variable a if
I have the token so let's bring back
Friendly Steve so we've now got a token and we?
What we're going to say is it unless I've got the token I cannot access a variable a so I'm going to execute those three
Instructions whenever I've got the token so I'll get a load of runny win
add something onto it and store it back and
gonna hand the token to Steve now I've got the token so I can load a value in
add the value from I've merged her into it and
store it back and hand the target and now I've got the token again I can load something into
It into my register add something onto it
Back and pass the token on and I've got it so I can load the value in add the value from a register
Story back and pass the token on
And because I've got the token again I can do the same again but because only one of us can hold the token at any
one time it means that only a can get updated
When we've got the token and so we never lose that right because we're saying that unless you've got the token
You can't access that very that's great so if we turn back to the laptop we can see
How we can implement that in our program we're gonna use the same idea, we're gonna have something that we need to have before
We can run that code in this case we're going to have what's called a mutex and mute an area mutual exclusion
that we need to lock
Before we can run, the code after it and then when
we finished we unlock that and so if it's
Locked and we try and acquire it our program will pause until it is able to lock it
So I'm going to do is I've created the variable for it here and I've
Also initialized it down here so it's all set up
Ready to go so before I add onto a that the value of the instructions I'm going to lock that
mutex
like so and then afterwards
if I could type I'm going to unlock that mutex
Like so and I need to do the same in the other thread as well so I'm going to lock the mutex
I'm going to unlock it afterwards
So if I can pile this version up
we still got two threads we're still getting them to add up the things as we go through it and then at the end
We're going to add the result and it should this time give us the right answer
so let's run it and
It gives us the right answer we now split the problem into it's running on two CPUs and because we're locking that variable so
We can only access it by one thread or the other
So, we did with the two Steve's then we can get the right result and it produces the same result every time
now the downside to this is that locking the thread each time slows the running of the program down
But we can be clever if we think about addition if we add six numbers together
That's the same as adding
Three numbers together then adding three numbers together and having the results of both together and we can do the same thing here
so, we can take this mutex and
Move it outside of our main loop and instead of rounding on the value of I each time
we have a local variable we'll call it local a which we add everything on to so we say local a equals local a
plus I
So inside our thread we're just going around adding all the values on as we did before which didn't work because we're putting in a
Local variable that's local to that thread and this function
It's not gonna be a problem because only this function can access it well do the same in the other thread and then we'll do
The same thing outside it and the advantage of doing this is that we now only have to acquire that lock
Once in each thread rather having to acquire it for every single addition, whether you have to acquire it once if we time the program
Beforehand and I should say at this point the program may be running so fast that we won't better get an accurate time and it
Wouldn't try anyway so use the time coming to time it
We see it takes about nine point eight two seconds let's just run it again nor point seven one
Nor point seven one
We seem to have standardized around that sort of things about naught point seven so let's compile up our faster version now
Not made any mistakes and we'll time it again, well let's see produces the right value will time it as well
And it's taking around the same time
It's dropping a bit and it doesn't really make any difference in time I think that's just because of how fast the computers are
That we're dealing with but with a bigger program we're doing more calculations
Reducing the number of times we require that a lot would actually make the system run
Faster so multi-threading is the idea breaking our program up into multiple threads of execution that run for different lengths of time but
We have to be careful that we do things in the right order and we avoid having
multiple threads accessing the same variable at the same time
Particularly if they're writing if they're just reading from it it doesn't matter if one's writing and several the reading from it and it doesn't
matter if they perhaps get an. Older value at a time then it works fine and so on
That same
A1 so that he can decrypt the message and read it right so Alice maybe wants to send another one so she's going to tick
This KDF function again she's going to produce a new key and a2
she's going to send that to Bob he's going to take this receiving function a2
Now Bob wants to send a message so he's going to tick