Process scheduling is done in the clock interrupt, and the core statement is mov ESP, [proc_ready], which means the stack that selects the next process to execute when the user process returns from the clock interrupt.

How do YOU select the stack for the next process to execute? That’s what process scheduling does. The so-called scheduling is the arrangement.

This paper only implements scheduling algorithm based on process priority.

8253

Clock interrupt frequency

Clock interruptions occur every X time units. This X can be set with 8253. The 8253, like the 8259A, is programmable hardware.

The 8253 provides a 16-bit counter with a maximum value of 65535. The default initial value of the 8253 counter is 65535. Every second, the counter will decrease by 1 until it reaches 0, and then it will resume its initial value and continue the previous round of decrement. In X seconds from the initial value to 0, 1193180 clock interrupts occur.

Clock interrupts occur at frequency = 1193180/ the initial value of the counter, therefore, the initial value of the counter = 1193180/frequency.

If you want to set the clock interrupt frequency to 100 hz, that is, every 10ms, the initial value of the counter should be 1193180/100.

BCD

A decimal number, 345, in BCD code, 0003 0004 00005. There are many kinds of BCD codes, and this is the most common one.

The use of 8253

The function of 8253 is to set the initial value of the counter, to set the purpose of clock interrupt frequency.

Four ports

The 8253 has four ports:

  1. 0 x40. 8253 Counter0.
  2. 0 x41. 8253 Counter1.
  3. 0 x42. 8253 Counter2.
  4. 0 x43. 8253 Mode control register.

We use ports 0x40 and 0x43 this time.

Set the value of port 0x43 and then 0x40.

The value of 0x43 port consists of eight bits divided into several parts, each of which has a specific meaning. It’s well documented in the book. I’m not going to memorize it. It’s not a common point.

In general, fill in the eight bits as required, write the digits as binary or hexadecimal, and write to port 0x43.

Note that a word (the data in this word is the initial value of the counter we calculated above) is written to port 0x40 twice, one byte at a time, first the low byte, then the high byte.

Scheduling algorithm

delay

The pseudocode is as follows:

void 		delay(int milli_second)
{
  			// Obtain the current clock interrupt count through the system call
  			int ticks = get_ticks();
  			while((get_ticks()-ticks)*10 < milli_second)
        {
          		// do nothing}}Copy the code

Process scheduling

The pseudocode is as follows:

typedef 	struct {
  		// The number of clock interrupts that the process can execute. The initial value is priority
  		int	 ticks;
  		// Process priority
  		int	 priority;	
  		// Process name
  		char	name[16];
}Process;

Process  A = {150.150."TestA"};
Process  B = {50.50."TestB"};
Process  C = {30.30."TestC"};

Process	 procs = {A,B,C};
int	N = 3;

void 	TestA(a)
{
  		while(1) {// get_ticks() gets the number of times a clock interrupt has occurred
        		// Prints the number of clock interrupts
        		disp_str(get_ticks());
        		/ / delay 200 ms
        		delay(200); }}void 	TestB(a)
{
  		while(1){
        		disp_str(get_ticks());
        		delay(200); }}void 	TestC(a)
{
  		while(1){
        		disp_str(get_ticks());
        		delay(200); }}// Clock interrupt processing
void	clockHandler(a)
{
  	// When a clock interrupt occurs, the number of available clock interrupts remaining for the current process is subtracted by 1
  	current_process->ticks--;	
  	schedule()
}
// Process scheduling algorithm, allocate scheduling times according to process ticks. All processes are reinitialized after the ticks run out
void	schedule(a)
{
  		int greastTicks = 0;
  		
  		while(! greastTicks){for(Process p = procs; p < procs + N; p++){
              	if(p->ticks > greastTicks){ current_process = p; greastTicks = p->ticks; }}if(! greastTicks){for(Process p = procs; p < procs + N; p++){ p->ticks = p->priority; }}}}Copy the code

Operation result interpretation

Below are the results of the three processes. The code to run looks like this:

  1. Ticks of process A, B and C are respectively30, 30, 30.
  2. In each process, it prints the current ticks in the form ofticks; Then print the respective process name:A, B, C.
  3. Every process is delayed20Two clock interrupts.
  4. A clock interrupt occurs every 10 milliseconds.
  5. In the scheduler, each tick that enters the alternative scheduler process is printed in the form<ticks>.

The red letters in the figure, such as B, are the process names printed in the process.

The execution process is as follows:

  1. The current process is A. The execution is completerestart, process A is about to run, and the clock is interrupted.
  2. performsaveThe snapshot of process A is saved.
  3. Enter the scheduling function.
    1. Process ticks
      1. Ticks = 30, ticks = 30,C->ticks = 30.
      2. Fixed A – > ticks. Before entering the scheduling function, when entering the clock interrupt handler, A->ticks–.
      3. Therefore, the data of step 1 is corrected as A-> Ticks = 29,B-> Ticks = 30, and C->ticks = 30.
        1. According to the scheduling algorithm,greatesTicksAfter comparing with B, the value is 30, so C will not enter the alternative scheduling process, which is different from that in the figure<0x1D><0x1E>It’s a match.
    2. Obviously, the result of the scheduling algorithm is process B.
  4. Clock interrupt occurs
    1. Ticks: A->ticks = 29,B->ticks = 29,C->ticks = 30
    2. The result of the scheduling algorithm is process C.
  5. Clock interrupt occurs
    1. Ticks: A->ticks = 29,B->ticks = 29,C->ticks = 29.
    2. The result of the scheduling algorithm is process A.
  6. Several clock interrupts occur, all in the system call interrupt reentrant, not scheduled process.
    1. It is difficult to simulate the results. It is best not to speculate on this execution process, it is very futile!
  7. In processdelayAfter that, the subsequent implementation has been difficult to simulate. No more analysis.

Key points of key points

Method for calculating the number of times a process executes

Use pseudocode to set the number of clock interrupts the process can execute

Process  A = {150.150."TestA"};
Process  B = {50.50."TestB"};
Process  C = {30.30."TestC"};
Copy the code

The number of times process A executes is :(100 + 20 * 2 + 30 * 3)/20.

The number of times process B executes is :(20 * 2 + 30 * 3)/20.

The number of times process C executes is :(30 * 3)/20.

why

The execution time

Suppose there are only two processes and conditions are as follows:

Process  A = {20.20."TestA"};
Process  B = {20.20."TestB"};
Copy the code

How many total clock interrupts would it take to complete two processes? The answer is 20*2 = 40.

In our scheduling algorithm, the scheduling ends only when ticks of both processes become 0. Each clock interrupt reduces the ticks of only one process by 1. The number of clock interrupts required to make both processes tick to 0 is the sum of the ticks of both processes.

Why divide by 20

When the priority of each process is equal, every 20 clock interrupts occur, the delay function of the process that acquired the CPU ends execution, meaning that the process has completed one execution. Because of our scheduling algorithm, each process gets the CPU sooner or later, so for every 20 clock interrupts, each process completes one execution sooner or later.

The system call get_ticks, which gets the number of clock interrupts that have currently occurred, gets roughly the same value across processes (with one or two differences), similar to a global variable.

This is not easy to say, and I have spent a great deal of time here, so let me say as many words as possible.

Three process execution processes are simulated as follows:

  1. Process A enters the loop and gets the current Ticks =3.
  2. Process B enters the loop and gets the current ticks=4.
  3. Process C enters the loop and gets the current ticks=5.
  4. After several clock interrupts.
    1. Process A runs, loop, get the current ticks=23, loop ends, process completes one execution.
    2. Process B runs, loop, gets the current ticks=24, loop ends, and the process completes one execution.
    3. Process C runs, loop, get the current ticks=25, loop ends, process completes one execution.
    4. That’s it.

Twenty clock interrupts allow all three processes to execute at once.

The myth was that each process consumes 20 clock interrupts, so every 20 clock interrupts can only be executed once by one process.

In fact, there have always been 20 clock interrupts in which one process’s delay function will end execution, and other processes’ delay function will end execution when scheduled to other processes. That is, the delay functions of all three processes are “under the same time”. When A has delayed 20 clock interrupts, B and C are also about to delay 20 clock interrupts. All processes live under the same clock.