In this lecture, we will add a scheduler in the process module and see how to switch from one process to another.
In this example, we have two processes running in the system.
After we initialize the processes, we call function launch to run the first process. At this point,
we are in the user mode.
So how do we force the process to give up the cpu resource and pick another process to run.
Remember we have implemented timer interrupt which is configured to fire the interrupts every 10ms.
In the user mode, we enabled interrupt,
so the timer interrupt will be processed by the processor and the control is transferred to trap handler.
In the handler, we will check to see if this is timer interrupt. If it is timer interrupt,
we will go to process module to do the context switch
and then the second process is selected.
When we jump back to user mode, we will actually run the second process. After it runs for a period of time,
10ms in this case,
the timer interrupt is fired and we will get to trap handler again.
Choose the third process and we get to user mode to run the program.
When the time for this process is up, we will select the first process in the handler again.
In the system, we continue doing it to switch among different processes.
In the process module, we save the runnable process in the linked list called ready list.
Suppose we have three processes in the ready list.
The first one is selected in this example
and now we have two processes in the list. The content of process 1 will then be restored
and running until the next timer interrupt occurs.
When the interrupt is fired, the process 2 is removed from the list and we append process 1
to the list.
Then the process 2 is the process we will run in this case.
Ok let’s open the project. First off, we take a look at process header file.
Since we save the runnable processes using linked list, the member list is added in the process structure.
The structure list is implemented in the library module. So let’s see it in lib.h file.
As you see, the structure list includes only one item that is the pointer to the next list structure.
Head list contains the head and tail of the list.
In this example, the field next points to the process which is supposed to be running next.
And we will add the current process at the tail of the list.
the library was implemented in assembly language in the previous lectures.
And now we add the linked list operations in the lib.c file.
In this file, we have three functions, append item to the list, remove the item from the list and check the list status
.
Let's start off with the first function.
It takes two parameters the head list and the item we want to append.
The head list could be ready list which we just talked about. So we take it as an example.
To add the item, we assign the null to the next field of the item. Because the item will be appended to the tail of the list.
Then we check if the list is empty.
Checking the list empty is simple.
Here you can see if the head points to nothing, then the list contains no items.
OK, let's continue.
If it is empty, then the item is the only one in the list, so the head and tail are both pointing to this item.
Otherwise, we just add the item to the last one of the list.
The tail now points to the current last item. And we assign the address of the new item to the next field
to link the item in the list.
Then we change the tail to point to the item.
OK.
Next function removes the first item from the list. If there’s no items in the list, we simple return NULL
.
Otherwise we will retrieve the first element. The head points to the first item,
so we save it in the variable item.
Then we make the head point to the next item by assigning the next item to it.
If the item is the only one in the list, we will also assign NULL to tail. Return item to the caller
and we are done.
Alright.
The next thing we are going to do is we are going to add new functions in the process module to do the context switch
.
So in the init process function,
we use for loop to find the unused process and set the process entry. Notice that set process entry function
takes two arguments in this case,
the process we want to initialize and the address of user programs.
There are two elements in the array which represent the locations of the two programs.
When we setup uvm in the set process entry funtion, we will copy the user program specified by this address
to the new allocated page.
At the end of the function, we change the process state to proc ready.
Remember we have loaded the user program in the physical address 20000 and we will load
another user program in 30000 in this lecture.
After we set these two entries, we add them in the ready list and the scheduler will choose which process to run
using this list.
So let's see the ready list.
As you can see, we add the ready list in the structure process control.
The variable process control is defined here.
OK, back to the function.
we retrieve the ready list in the process control and add the two processes in the ready list.
With the process prepared, we call function launch to run the process. The first thing we will do in this function
is remove the first element in the ready list, set the process state to proc running
and save it in the variable current process of process control for later use.
Then we set tss, switch vm and jump to trap return just as we learned in the last lecture.
At this point, the first program is running.
In this example, it’s the user program we wrote in the last video. Because we want to see that each process is running separately,
we print the message constantly using while loop.
So here we define a variable counter
and then add the print function in the infinite loop. Then we increment the counter.
If the counter is divisible by let’s say 100000,
we will print message
process 1
and the counter value.
The reason we do this is that if we just print message in each iteration,
the messages will be printed on the screen so fast that we cannot see each message clearly on the screen.
Here the value should be adjusted according to the different computers. For example, in the virtual machine
,
we can set it with a relatively small value. In the real machine,
we could use a larger value.
Ok. Now we are running in this program. In the slide, we talked about
timer interrupt is used to switch processes.
In fact, the timer interrupt is working now.
In the trap handler,
you can see we just send end of interrupt and return. So it’s working silently. In the function
set process entry,
the rflags is set to 202.
So the interrupt flag is set when we get to user mode. Meaning that
when we are in the user program, the timer interrupt will be processed by the trap handler.
Therefore, if the handler is called and the trap number is timer interrupt, we will call yield function to
make the current process give up the cpu resource
and choose another process.
Let’s take a look at yield function which is defined in the process.c file.
First off, we get the process control using function get process control.
The function get process control simply returns the address of this variable to the caller.
The ready list in the process control is what we want.
Here we do a test to see if the ready list is empty. If it is empty, we just return and run the same process
because we have no other processes to run.
After we retrieve the process control, we can locate the current process. The current process in the process control
is the process we are currently running.
Since we will choose other process to run, we change the state from proc running to proc ready.
Then we append it to the ready list.
The function schedule is the one which does the process switch. Let’s see what we have in this function.
In the function, we first retrieve the process control and save the current process to the variable previous proc
.
What we are going to do next is we are going to get the next process from ready list by calling function
remove list head.
This process is becoming the current process now and the state should be set to process running.
Don’t forget to save the current process in the process control for later use in the module.
And now we get to switch process function.
The first argument is the previous process and the second one is the new process.
As you see, the switch process is like launch function, such as set tss and switch to current page map.
The difference is that we use swap to do the context switch that is switching process.
Note that this function is not like the normal functions we see in the previous lectures. For example,
if we enter the function as process 1, then after we return from it, we will return as process 2
just as the name swap implies.
This is the mechanism that we use to switch among different processes.
This function is implemented in assembly language and we add it in the trap.asm file.
Here you can see we just push a bunch of registers and pop them back to the same registers.
The essential part is these two instructions. What it does is change the rsp register,
in other word, it changes the kernel stack pointer from one process to another.
In this example, suppose the current process is process 1 and we want to switch process by calling function swap.
The function saves the return address as well as the general-purpose registers on the stack.
Then it saves the rsp value in the process structure.
Next it will copy the rsp value saved in the process 2 to register rsp.
You can see we are at process 2 stack at this point.
Rsp points to the registers and return address saved on the stack the last time it runs.
Restore the previous state of process 2 by popping the values to the registers
and return to where it was called.
So when we enter swap function, we are in the process 1, after we return from swap, we are in the process 2
.
OK, let's back to the project.
In the process header file,
we add the member context which is used to save the rsp value when we switch process.
Alright, let’s examine the swap function,
as you see, when we do the context switch, the first argument is the address of rsp member in the process
and the second one is the rsp value in the new process which is about to run.
So in the swap function,
after we save the registers on the stack, we copy the current stack pointer in field context for later use.
And copy the stack pointer of new process to register rsp.
And now we are at the kernel stack of new process. Rsp is pointing to the general purpose registers this process pushed on the stack
when the last time it runs.
So we restore the registers from the stack and return to where it was called.
Also, we don’t push all the 15 general-purposed registers because in system V amd64 calling convention,
other registers are caller-saved registers.
Another thing we need to do before we finish the kernel part is that the context member
should be initialized to the correct value.
So let's take a look.
As you see, we added two more lines of code.
If we don’t initialize it, we will get to wrong location when we switch to the process for the first time.
Here we add 48 to the rsp value which produces a new address.
In this location we save the address of trap return. 48 is equal to the size of 6 registers.
In the function swap,
you can see, when we copy the context value to rsp and then we pop 6 registers
which will add 48 to rsp register and now we get to the return address.
So when the first time we switch to the process, rsp value will be loaded with context value,
then add 48 to rsp and get to return address which is set to trap return.
Therefore, it will return to the trap return and jump to ring3 using the data we set up in the trap frame
just as we learned in the last lecture.
Don’t forget to declare trap return in the trap assembly
and c file because we reference the trap return in the process module.
Alright, the kernel part is done.
Up to this point, we have only one user application. Let’s create another one.
We change the first one to user1
and create a new folder user2.
In the folder,
most of the files we need are the same, we only do some changes in some main.c file.
In the main function, we change the message to process 2
If everything goes as expected, we should see process 1 and process 2 printed on the screen.
OK, let's build the project.
Now we copy the two binary files to the kernel project.
In the build script of the kernel project,
we write the user 2 files into the boot image staring from 116.
Let’s load the binary file in the loader file.
We use the same code here.
The address we want to load into is 30000.
You can wrap the code as a function and call the function to load the binary files.
let’s build the project and test it out.
OK, you can see the message process1 and process2 are printed on screen.
That's it for this lecture and see you in the video.