1
00:00:00,660 --> 00:00:06,270
In this lecture, we will add a scheduler in the process module and see how to switch from one process to another.

2
00:00:06,270 --> 00:00:13,240
In this example, we have two processes running in the system. 

3
00:00:13,290 --> 00:00:18,870
After we initialize the processes, we call function launch to run the first process. At this point, 

4
00:00:18,900 --> 00:00:20,640
we are in the user mode. 

5
00:00:21,360 --> 00:00:27,490
So how do we force the process to give up the cpu resource and pick another process to run.

6
00:00:28,440 --> 00:00:35,190
Remember we have implemented timer interrupt which is configured to fire the interrupts every 10ms. 

7
00:00:36,030 --> 00:00:38,220
In the user mode, we enabled interrupt, 

8
00:00:38,670 --> 00:00:44,250
so the timer interrupt will be processed by the processor and the control is transferred to trap handler. 

9
00:00:45,170 --> 00:00:50,720
In the handler, we will check to see if this is timer interrupt. If it is timer interrupt, 

10
00:00:50,720 --> 00:00:53,600
we will go to process module to do the context switch 

11
00:00:53,900 --> 00:00:56,060
and then the second process is selected. 

12
00:00:57,440 --> 00:01:02,930
When we jump back to user mode, we will actually run the second process. After it runs for a period of time, 

13
00:01:02,930 --> 00:01:04,560
10ms in this case, 

14
00:01:04,580 --> 00:01:09,320
the timer interrupt is fired and we will get to trap handler again. 

15
00:01:10,810 --> 00:01:14,500
Choose the third process and we get to user mode to run the program. 

16
00:01:15,590 --> 00:01:22,110
When the time for this process is up, we will select the first process in the handler again. 

17
00:01:22,220 --> 00:01:25,880
In the system, we continue doing it to switch among different processes. 

18
00:01:28,060 --> 00:01:33,220
In the process module, we save the runnable process in the linked list called ready list. 

19
00:01:33,760 --> 00:01:36,480
Suppose we have three processes in the ready list. 

20
00:01:36,980 --> 00:01:39,190
The first one is selected in this example 

21
00:01:42,040 --> 00:01:48,760
and now we have two processes in the list.  The content of process 1 will then be restored 

22
00:01:48,760 --> 00:01:51,010
and running until the next timer interrupt occurs.

23
00:01:51,610 --> 00:01:57,760
When the interrupt is fired, the process 2 is removed from the list and we append process 1 

24
00:01:57,760 --> 00:01:58,300
to the list.

25
00:01:58,990 --> 00:02:02,200
Then the process 2 is the process we will run in this case.

26
00:02:03,350 --> 00:02:08,630
Ok let’s open the project. First off, we take a look at process header file. 

27
00:02:12,500 --> 00:02:18,470
Since we save the runnable processes using linked list, the member list is added in the process structure. 

28
00:02:20,080 --> 00:02:26,320
The structure list is implemented in the library module. So let’s see it in lib.h file. 

29
00:02:31,620 --> 00:02:37,470
As you see, the structure list includes only one item that is the pointer to the next list structure. 

30
00:02:39,390 --> 00:02:42,120
Head list contains the head and tail of the list.

31
00:02:43,160 --> 00:02:49,360
In this example, the field next points to the process which is supposed to be running next. 

32
00:02:49,370 --> 00:02:52,040
And we will add the current process at the tail of the list. 

33
00:02:52,990 --> 00:02:58,480
the library was implemented in assembly language in the previous lectures.

34
00:02:58,480 --> 00:03:00,870
And now we add the linked list operations in the lib.c file. 

35
00:03:05,000 --> 00:03:12,020
In this file, we have three functions, append item to the list, remove the item from the list and check the list status

36
00:03:12,020 --> 00:03:13,040
.

37
00:03:13,730 --> 00:03:15,620
Let's start off with the first function.

38
00:03:16,920 --> 00:03:21,780
It takes two parameters the head list and the item we want to append. 

39
00:03:22,720 --> 00:03:30,100
The head list could be ready list which we just talked about. So we take it as an example. 

40
00:03:30,190 --> 00:03:35,770
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.

41
00:03:36,440 --> 00:03:38,440
Then we check if the list is empty. 

42
00:03:39,340 --> 00:03:41,110
Checking the list empty is simple. 

43
00:03:43,610 --> 00:03:48,270
Here you can see if the head points to nothing, then the list contains no items. 

44
00:03:49,100 --> 00:03:50,140
OK, let's continue.

45
00:03:53,210 --> 00:03:59,810
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. 

46
00:03:59,810 --> 00:04:04,090
Otherwise, we just add the item to the last one of the list. 

47
00:04:04,730 --> 00:04:11,030
The tail now points to the current last item. And we assign the address of the new item to the next field 

48
00:04:11,030 --> 00:04:12,470
to link the item in the list. 

49
00:04:12,950 --> 00:04:15,240
Then we change the tail to point to the item. 

50
00:04:15,950 --> 00:04:16,360
OK.

51
00:04:18,700 --> 00:04:24,520
Next function removes the first item from the list.  If there’s no items in the list, we simple return NULL

52
00:04:24,520 --> 00:04:24,880
.

53
00:04:25,960 --> 00:04:30,810
Otherwise we will retrieve the first element. The head points to the first item, 

54
00:04:30,820 --> 00:04:33,040
so we save it in the variable item.

55
00:04:33,430 --> 00:04:37,930
Then we make the head point to the next item by assigning the next item to it. 

56
00:04:38,740 --> 00:04:44,500
If the item is the only one in the list, we will also assign NULL to tail. Return item to the caller 

57
00:04:44,500 --> 00:04:45,250
and we are done.

58
00:04:46,030 --> 00:04:46,660
Alright.

59
00:04:46,810 --> 00:04:52,600
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

60
00:04:52,610 --> 00:04:52,990
.

61
00:04:55,890 --> 00:04:58,440
So in the init process function,

62
00:05:01,030 --> 00:05:07,590
we use for loop to find the unused process and set the process entry. Notice that set process entry function 

63
00:05:07,600 --> 00:05:09,130
takes two arguments in this case,

64
00:05:09,140 --> 00:05:14,920
the process we want to initialize and the address of user programs. 

65
00:05:15,820 --> 00:05:21,720
There are two elements in the array which represent the locations of the two programs. 

66
00:05:21,750 --> 00:05:28,330
When we setup uvm in the set process entry funtion, we will copy the user program specified by this address 

67
00:05:28,330 --> 00:05:29,950
to the new allocated page.  

68
00:05:30,990 --> 00:05:34,740
At the end of the function, we change the process state to proc ready.

69
00:05:37,130 --> 00:05:42,920
Remember we have loaded the user program in the physical address 20000 and we will load 

70
00:05:42,920 --> 00:05:45,740
another user program in 30000 in this lecture. 

71
00:05:46,620 --> 00:05:53,250
After we set these two entries, we add them in the ready list and the scheduler will choose which process to run 

72
00:05:53,250 --> 00:05:54,570
using this list. 

73
00:05:55,770 --> 00:05:57,180
So let's see the ready list.

74
00:05:59,710 --> 00:06:04,090
As you can see, we add the ready list in the structure process control. 

75
00:06:05,770 --> 00:06:08,230
The variable process control is defined here.

76
00:06:09,360 --> 00:06:10,710
OK, back to the function.

77
00:06:12,900 --> 00:06:17,850
we retrieve the ready list in the process control and add the two processes in the ready list. 

78
00:06:19,520 --> 00:06:25,640
With the process prepared, we call function launch to run the process. The first thing we will do in this function

79
00:06:25,640 --> 00:06:32,590
is remove the first element in the ready list, set the process state to proc running 

80
00:06:32,600 --> 00:06:36,260
and save it in the variable current process of process control for later use. 

81
00:06:37,250 --> 00:06:43,700
Then we set tss, switch vm and jump to trap return just as we learned in the last lecture. 

82
00:06:45,090 --> 00:06:47,460
At this point, the first program is running. 

83
00:06:52,300 --> 00:06:58,810
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, 

84
00:06:58,810 --> 00:07:02,320
we print the message constantly using while loop. 

85
00:07:04,670 --> 00:07:07,640
So here we define a variable  counter 

86
00:07:12,030 --> 00:07:17,520
and then add the print function in the infinite loop. Then we increment the counter.

87
00:07:21,010 --> 00:07:25,360
If the counter is divisible by let’s say 100000, 

88
00:07:29,600 --> 00:07:30,830
we will print message 

89
00:07:31,990 --> 00:07:32,830
process 1 

90
00:07:35,900 --> 00:07:36,980
and the counter value. 

91
00:07:38,470 --> 00:07:44,350
The reason we do this is that if we just print message in each iteration, 

92
00:07:44,350 --> 00:07:49,110
the messages will be printed on the screen so fast that we cannot see each message clearly on the screen. 

93
00:07:50,300 --> 00:07:55,750
Here the value should be adjusted according to the different computers.  For example, in the virtual machine

94
00:07:55,760 --> 00:07:56,190
,

95
00:07:56,510 --> 00:08:01,040
we can set it with a relatively small value. In the real machine, 

96
00:08:01,070 --> 00:08:02,450
we could use a larger value.

97
00:08:03,380 --> 00:08:07,970
Ok. Now we are running in this program. In the slide, we talked about 

98
00:08:08,120 --> 00:08:11,020
timer interrupt is used to switch processes. 

99
00:08:11,540 --> 00:08:13,970
In fact, the timer interrupt is working now.

100
00:08:16,630 --> 00:08:17,830
In the trap handler, 

101
00:08:19,800 --> 00:08:26,640
you can see we just send end of interrupt and return. So it’s working silently.  In the function 

102
00:08:26,640 --> 00:08:27,810
set process entry,

103
00:08:28,980 --> 00:08:30,650
the rflags is set to 202. 

104
00:08:30,800 --> 00:08:37,559
So the interrupt flag is set when we get to user mode. Meaning that 

105
00:08:37,559 --> 00:08:42,120
when we are in the user program, the timer interrupt will be processed by the trap handler. 

106
00:08:42,659 --> 00:08:49,050
Therefore, if the handler is called and the trap number is timer interrupt, we will call yield function to 

107
00:08:49,140 --> 00:08:52,050
make the current process give up the cpu resource 

108
00:08:52,320 --> 00:08:53,760
and choose another process. 

109
00:08:55,250 --> 00:08:59,710
Let’s take a look at yield function which is defined in the process.c file.

110
00:09:05,330 --> 00:09:11,270
First off, we get the process control using function get process control. 

111
00:09:11,270 --> 00:09:15,080
The function get process control simply returns the address of this variable to the caller. 

112
00:09:17,220 --> 00:09:21,120
The ready list in the process control is what we want.

113
00:09:21,150 --> 00:09:27,930
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 

114
00:09:27,930 --> 00:09:30,090
because we have no other processes to run.

115
00:09:32,440 --> 00:09:37,750
After we retrieve the process control, we can locate the current process. The current process in the process control

116
00:09:37,750 --> 00:09:40,750
is the process we are currently running. 

117
00:09:41,230 --> 00:09:46,620
Since we will choose other process to run, we change the state from proc running to proc ready. 

118
00:09:47,500 --> 00:09:49,420
Then we append it to the ready list. 

119
00:09:50,110 --> 00:09:56,080
The function schedule is the one which does the process switch. Let’s see what we have in this function.

120
00:09:58,600 --> 00:10:03,910
In the function, we first retrieve the process control and save the current process to the variable previous proc

121
00:10:03,910 --> 00:10:05,050
.

122
00:10:06,260 --> 00:10:11,660
What we are going to do next is we are going to get the next process from ready list by calling function 

123
00:10:11,840 --> 00:10:13,100
remove list head. 

124
00:10:14,360 --> 00:10:19,880
This process is becoming the current process now and the state should be set to process running. 

125
00:10:21,070 --> 00:10:26,890
Don’t forget to save the current process in the process control for later use in the module.  

126
00:10:26,890 --> 00:10:28,870
And now we get to switch process function. 

127
00:10:30,010 --> 00:10:34,480
The first argument is the previous process and the second one is the new process. 

128
00:10:36,180 --> 00:10:45,360
As you see, the switch process is like launch function, such as set tss and switch to current page map. 

129
00:10:45,360 --> 00:10:49,830
The difference is that we use swap to do the context switch that is switching process.

130
00:10:50,870 --> 00:10:56,660
Note that this function is not like the normal functions we see in the previous lectures. For example, 

131
00:10:56,660 --> 00:11:04,070
if we enter the function as process 1, then after we return from it, we will return as process 2 

132
00:11:04,070 --> 00:11:05,690
just as the name swap implies. 

133
00:11:06,470 --> 00:11:10,540
This is the mechanism that we use to switch among different processes.

134
00:11:11,840 --> 00:11:17,810
This function is implemented in assembly language and we add it in the trap.asm file. 

135
00:11:19,830 --> 00:11:25,050
Here you can see we just push a bunch of registers and pop them back to the same registers. 

136
00:11:26,440 --> 00:11:31,850
The essential part is these two instructions. What it does is change the rsp register, 

137
00:11:32,050 --> 00:11:36,520
in other word, it changes the kernel stack pointer from one process to another. 

138
00:11:37,610 --> 00:11:43,640
In this example, suppose the current process is process 1 and we want to switch process by calling function swap. 

139
00:11:43,880 --> 00:11:50,810
The function saves the return address as well as the general-purpose registers on the stack. 

140
00:11:50,810 --> 00:11:55,100
Then it saves the rsp value in the process structure. 

141
00:11:55,790 --> 00:12:01,310
Next it will copy the rsp value saved in the process 2 to register rsp. 

142
00:12:01,970 --> 00:12:05,300
You can see we are at process 2 stack at this point. 

143
00:12:05,960 --> 00:12:09,680
Rsp points to the registers and return address saved on the stack the last time it runs. 

144
00:12:09,680 --> 00:12:17,060
Restore the previous state of process 2 by popping the values to the registers 

145
00:12:17,180 --> 00:12:19,010
and return to where it was called.  

146
00:12:19,970 --> 00:12:26,360
So when we enter swap function, we are in the process 1, after we return from swap, we are in the process 2

147
00:12:26,360 --> 00:12:27,230
.

148
00:12:29,020 --> 00:12:31,030
OK, let's back to the project.

149
00:12:31,720 --> 00:12:33,340
In the process header file, 

150
00:12:36,300 --> 00:12:42,150
we add the member context which is used to save the rsp value when we switch process. 

151
00:12:43,440 --> 00:12:45,780
Alright, let’s examine the swap function, 

152
00:12:47,000 --> 00:12:53,900
as you see, when we do the context switch, the first argument is the address of rsp member in the process 

153
00:12:53,900 --> 00:12:59,440
and the second one is the rsp value in the new process which is about to run. 

154
00:13:00,290 --> 00:13:01,880
So in the swap function, 

155
00:13:03,620 --> 00:13:09,410
after we save the registers on the stack, we copy the current stack pointer in field context for later use.

156
00:13:09,410 --> 00:13:14,600
And copy the stack pointer of new process to register rsp. 

157
00:13:15,300 --> 00:13:21,650
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 

158
00:13:21,680 --> 00:13:24,770
when the last time it runs. 

159
00:13:25,490 --> 00:13:30,020
So we restore the registers from the stack and return to where it was called. 

160
00:13:31,350 --> 00:13:37,410
Also, we don’t push all the 15 general-purposed registers because in system V amd64 calling convention, 

161
00:13:37,410 --> 00:13:40,800
other registers are caller-saved registers.

162
00:13:42,220 --> 00:13:47,620
Another thing we need to do before we finish the kernel part is that the context member 

163
00:13:47,620 --> 00:13:49,600
should be initialized to the correct value.

164
00:13:50,560 --> 00:13:51,570
So let's take a look.

165
00:13:54,630 --> 00:13:57,360
As you see, we added two more lines of code.

166
00:13:58,350 --> 00:14:04,110
If we don’t initialize it, we will get to wrong location when we switch to the process for the first time. 

167
00:14:04,890 --> 00:14:10,190
Here we add 48 to the rsp value which produces a new address. 

168
00:14:10,740 --> 00:14:17,340
In this location we save the address of trap return. 48 is equal to the size of 6 registers. 

169
00:14:18,150 --> 00:14:19,260
In the function swap, 

170
00:14:19,890 --> 00:14:25,980
you can see, when we copy the context value to rsp and then we pop 6 registers 

171
00:14:25,980 --> 00:14:30,810
which will add 48 to rsp register and now we get to the return address. 

172
00:14:31,900 --> 00:14:37,610
So when the first time we switch to the process, rsp value will be loaded with context value, 

173
00:14:38,020 --> 00:14:44,680
then add 48 to rsp and get to return address which is set to trap return. 

174
00:14:45,400 --> 00:14:50,770
Therefore, it will return to the trap return and jump to ring3 using the data we set up in the trap frame 

175
00:14:50,770 --> 00:14:53,320
just as we learned in the last lecture. 

176
00:14:54,430 --> 00:14:58,450
Don’t forget to declare trap return in the trap assembly 

177
00:15:00,810 --> 00:15:05,490
and c file because we reference the trap return in the process module.

178
00:15:06,470 --> 00:15:08,270
Alright, the kernel part is done.

179
00:15:09,490 --> 00:15:14,410
Up to this point, we have only one user application. Let’s create another one. 

180
00:15:15,720 --> 00:15:17,880
We change the first one to user1 

181
00:15:22,190 --> 00:15:24,770
and create a new folder user2. 

182
00:15:26,130 --> 00:15:26,960
In the folder,

183
00:15:28,980 --> 00:15:35,700
most of the files we need are the same, we only do some changes in some main.c file.

184
00:15:38,770 --> 00:15:42,430
In the main function, we change the message to process 2

185
00:15:44,170 --> 00:15:49,500
If everything goes as expected, we should see process 1 and process 2 printed on the screen.

186
00:15:50,460 --> 00:15:52,020
OK, let's build the project.

187
00:16:01,420 --> 00:16:04,390
Now we copy the two binary files to the kernel project.

188
00:16:20,880 --> 00:16:23,190
In the build script of the kernel project,

189
00:16:25,710 --> 00:16:33,130
we write the user 2 files into the boot image staring from 116. 

190
00:16:34,050 --> 00:16:36,930
Let’s load the binary file in the loader file.

191
00:16:42,310 --> 00:16:43,870
We use the same code here.

192
00:16:50,820 --> 00:16:55,060
The address we want to load into is 30000.

193
00:16:56,050 --> 00:17:00,010
You can wrap the code as a function and call the function to load the binary files. 

194
00:17:00,950 --> 00:17:02,960
let’s build the project and test it out.

195
00:17:12,540 --> 00:17:18,030
OK, you can see the message process1 and process2 are printed on screen.

196
00:17:19,349 --> 00:17:22,040
That's it for this lecture and see you in the video.