L15-一个实际的schedule函数

• 以 linux-0.11/kernel/sched.c 中的 schedule 函数为研究对象。

L15 一个实际的schedule函数

• 以 linux-0.11/kernel/sched.c 中的 schedule 函数为研究对象。

  void schedule(void)
  {
  	int i,next,c;
  	struct task_struct ** p;
  	...
  /* this is the scheduler proper: */
  
  	while (1) {
  		c = -1;
  		next = 0;
  		i = NR_TASKS;
  		p = &task[NR_TASKS];
          //求counter最大的处于就绪状态的进程
  		while (--i) {
  			if (!*--p)
  				continue;
  			if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
  				c = (*p)->counter, next = i;
  		}
  		if (c) break;	//找到了counter最大的那个进程
          // 如果没找到：
  		// 所有进程的 counter 值除以 2 衰减后再和 priority 值相加，
  		// 产生新的时间片
  		for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
  			if (*p)
  				(*p)->counter = ((*p)->counter >> 1) +
  								(*p)->priority;
  	}
  	switch_to(next);	//调度counter最大的那个进程，即优先级最大的那个进程
  }

  当没有 counter 值大于 0 的就绪进程（即没找到）时，要对所有的进程做 (*p)->counter = ((*p)->counter >> 1) + (*p)->priority。其效果是对所有的进程（包括阻塞态进程）都进行 counter 的衰减，并再累加 priority 值。这样，对正被阻塞的进程来说，一个进程在阻塞队列中停留的时间越长，其优先级越大，被分配的时间片也就会越大。

★★★counter的作用

• 注意：counter不仅代表了优先级，也代表了时间片。

  运行态进程（即 current）的 counter 数值会随着时钟中断而不断减 1（时钟中断 10ms 一次）。

  虽然对正被阻塞的进程来说，该进程在阻塞队列中停留的时间越长，其优先级越大，被分配的时间片也就会越大，但该进程被分配的时间片并不是一直增大到无穷的，而是会有一个上界，(*p)->counter = ((*p)->counter >> 1) + (*p)->priority 就保证了这个上界，举一个极端的例子，假设有一个进程，从创建以后就一直处于阻塞态，那么由上面代码可知，它的counter值为 p+p/2+p/2^2+p/2^3+...+p/2^n （p是时间片的初始值），是小于 2p 的，即该进程的时间片上限要小于 2p，就保证了在轮到该进程执行时，并不会无止尽地占用 CPU。

• 短短几行代码，兼顾了 SJF 算法（每个进程通过时间片轮转执行，所需总时间短的进程肯定比所需总时间长的进程优先执行完，近似 SJF 调度）、RR时间片轮转调度算法、优先级算法，考虑到短作业优先、前台任务优先（前台任务一般是要和 I/O 设备交互的任务，用 (*p)->counter = ((*p)->counter >> 1) + (*p)->priority 来提高前台任务的优先级），而且每个进程的时间片还设置了一个上界，十分精彩。