CPU Scheduling

• FCFS(First Come,First Served)：先来先服务

• SJF：短作业优先

• RR：时间片轮转调度

schedule函数实现

void schedule(void)
{
	...
	while (1) {
		c = -1;
		next = 0;
		i = NR_TASKS;
		p = &task[NR_TASKS];
		while (--i) {
			if (!*--p)
				continue;
			
			// 在就绪队列（state==TASK_RUNNING）中找到最大的的counter进行调度
			// counter是优先级也是时间片
			if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
				c = (*p)->counter, next = i;
		}
		if (c) break;

		// c最大为0 表示所有就绪态进程时间片都用完了
		// 将所有进程的counter置为counter/2 + priority（也是counter的初值）
		for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
			if (*p)
				(*p)->counter = ((*p)->counter >> 1) +
						(*p)->priority;
	}
	switch_to(next);
}

• counter保证了响应时间有界，最大值收敛于2*priority

• 经过IO以后，counter就会变大；IO时间越长，counter越大。照顾了IO进程，相当于照顾了前台进程

• 后台进程一直按照counter轮转，近似SJF调度

• 每个进程只维护一个counter变量，简单高效