preface

Now that multiple processes are introduced, which is essentially switching back and forth between processes, there will be scheduling problems between processes. It is actually a kernel subsystem that distributes limited processor time resources between runnable processes.

A few simple CPU scheduling algorithms

  • First Come, First Served(FCFS)

It’s basically a first-in, first-out queue, which means the process that applies first, executes first. When the CPU is free, it is allocated to the process at the head of the queue, and the running process is removed from the queue. FCFS scheduling code is simple to write and easy to understand.

However, for a process that needs to interact with the user, this scheduling algorithm will cause a very bad experience, because the turnaround time needs to complete a whole queue of tasks, which is very long

However, FCFS scheduling algorithm is non-preemptive. Once a CPU is allocated to a process, the process uses the CPU until it is released, when the program terminates or requests I/O.

  • Shortest Job First (SJF)

SJF scheduling algorithm refers to the algorithm of priority scheduling for short jobs or short processes. It associates each process with its estimated running time and selects the job with the shortest estimated computing time to run. This will shorten the turnaround time

The shortest Job First (SJF) scheduling algorithm associates each process with the length of its next CPU execution. When the CPU becomes idle, it is assigned to the process with the shortest CPU execution. If two processes have the same length of CPU execution then FCFS can handle it.

  • RR

In this algorithm, a small time unit is defined as a time quantity or time slice. The time slice size is usually 10 to 100ms. The ready queue acts as a circular queue. The CPU scheduler loops through the ready queue, allocating no more than one time slice of CPU to each process.

To implement RR scheduling, we again treat the ready queue as a FIFO queue for the process. The new process is added to the end of the ready queue. The CPU scheduler selects the first process from the ready queue, sets the timer to interrupt after a time slice, and dispatches the process.

A compromise of scheduling algorithms

In many running processes, some are more concerned with response time and some are more concerned with turnaround time, so the scheduling algorithm needs to compromise, but how to compromise is another question.

Linux0.11 scheduling algorithm

schedule

Schedule is the main scheduling algorithm in Linux0.11, but it is very concise

  • Task_struct is a structure used to describe a process

    The counter of task_struct is a key element of the scheduling algorithm’s tradeoff, as it represents both the allocated time slice and the priority of the process

  • First, loop through some fields starting with the last task in the task array

    If the timer alarm of the task has been set and is out of date (alarm<jiffies), the SIGALRM signal is placed in the signal bitmap to send the SIGALARM signal to the task. Then clear the alarm. There are some semaphore related ones that we’ll talk about later

  • Find the couter with the highest value, that is, the process with the least running time, and switch to its process

  • When a round is completed, the time slice will be reassigned. In this case, the time slice will be set to the initial value for the already round process, but for the blocked process, the time slice will be increased, which is a compromise scheduling.

void schedule(void)
{
	int i,next,c;
	struct task_struct ** p;

/* check alarm, wake up any interruptible tasks that have got a signal */

	for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
		if (*p) {
			if ((*p)->alarm && (*p)->alarm < jiffies) {
					(*p)->signal |= (1<<(SIGALRM- 1));
					(*p)->alarm = 0;
				}
			if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&
			(*p)->state==TASK_INTERRUPTIBLE)
				(*p)->state=TASK_RUNNING;
		}

/* this is the scheduler proper: */

	while (1) {
		c = - 1;
		next = 0;
		i = NR_TASKS;
		p = &task[NR_TASKS];
		while (--i) {
			if(! *--p)continue;
			if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
				c = (*p)->counter, next = i;
		}
		if (c) break;
		for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
			if (*p)
				(*p)->counter = ((*p)->counter >> 1) +
						(*p)->priority;
	}
	switch_to(next);
}
Copy the code

init

We’ll take a look at sched_init, the function that initializes the kernel scheduler’s subroutine, which initializes interrupts and descriptors

  • First call set_tSS_desc and set_LDT_DESC to set the TSS and LDT of process 0

  • Clear the task array and descriptor entries

  • Then initialize timer 8253

  • Finally, set up clock interrupts and system call interrupts

void sched_init(void)
{
	int i;
	struct desc_struct * p;

	if (sizeof(struct sigaction) ! =16)
		panic("Struct sigaction MUST be 16 bytes");
	set_tss_desc(gdt+FIRST_TSS_ENTRY,&(init_task.task.tss));
	set_ldt_desc(gdt+FIRST_LDT_ENTRY,&(init_task.task.ldt));
	p = gdt+2+FIRST_TSS_ENTRY;
	for(i=1; i<NR_TASKS; i++) { task[i] =NULL;
		p->a=p->b=0;
		p++;
		p->a=p->b=0;
		p++;
	}
/* Clear NT, so that we won't have troubles with that later on */
	__asm__("pushfl ; andl $0xffffbfff,(%esp) ; popfl");
	ltr(0);
	lldt(0);
	outb_p(0x36.0x43);		/* binary, mode 3, LSB/MSB, ch 0 */
	outb_p(LATCH & 0xff , 0x40);	/* LSB */
	outb(LATCH >> 8 , 0x40);	/* MSB */
	set_intr_gate(0x20,&timer_interrupt);
	outb(inb_p(0x21) & ~0x01.0x21);
	set_system_gate(0x80,&system_call);
}
Copy the code

Setting descriptors

_set_tsSLdT_desc is set according to the function of each bit of the descriptor

#define set_tss_desc(n,addr) _set_tssldt_desc(((char *) (n)),((int)(addr)),"0x89")
#define set_ldt_desc(n,addr) _set_tssldt_desc(((char *) (n)),((int)(addr)),"0x82")

#define _set_tssldt_desc(n,addr,type) \
__asm__ ("movw $104,%1\n\t" \
	"movw %%ax,%2\n\t" \
	"rorl $16,%%eax\n\t" \
	"movb %%al,%3\n\t" \
	"movb $" type ",%4\n\t" \
	"movb $0x00,%5\n\t" \
	"movb %%ah,%6\n\t" \
	"rorl $16,%%eax"\ : :"a" (addr), "m" (*(n)), "m" (*(n+2)), "m" (*(n+4)), \
	 "m" (*(n+5)), "m" (*(n+6)), "m" (*(n+7)) \
	)
Copy the code

Set the interrupt

#define _set_gate(gate_addr,type,dpl,addr) \
__asm__ ("movw %%dx,%%ax\n\t" \
	"movw %0,%%dx\n\t" \
	"movl %%eax,%1\n\t" \
	"movl %%edx,%2"\ \ :"i" ((short) (0x8000+(dpl<<13)+(type<<8))), \
	"o" (*((char *) (gate_addr))), \
	"o" (*(4+(char *) (gate_addr))), \
	"d" ((char *) (addr)),"a" (0x00080000))

#defineSet_intr_gate (n, addr) \ _set_gate (& idt [n], 14, 0, addr)

#defineSet_system_gate (n, addr) \ _set_gate (& idt [n], 15, 3, addr)
Copy the code

summary

This article mainly looked at the scheduling algorithm in Linux0.11, which is very simple, but takes care of the response time, and takes care of the turnaround time.

Then I mentioned the initialization subroutine of the kernel scheduler, which is to set up some descriptors and interrupt handling as described earlier