1.任务调度原则：

• 先执行优先级高的任务，再执行优先级低的任务。
• 优先级相同的任务按时间片轮转的方式调度。
  
   Runqueueu 数组的每一项对应一种优先级，数据越小，优先级越高。只有存在就绪任务的 Runqueue数组项才被链接到以 runqueue_head 为头的链表当中。系统进行任务调度时，通过 runqueue_head 寻找优先级最高的队列，然后从该队列中寻找第一个 TCB 进行调度。当同一个优先级存在多个任务时，则首先调度第一个 TCB 运行，当其运行完自己的时间片后，将它放入到链表的最后，这样使同一级别的其他任务能得到调度机会，从而实现时间片轮转调度。

2.时间片轮转概念：

 在早期的时间片轮转法中，系统将所有就绪态进程按先来先服务的原则，排成一个队列。每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾;然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。

 在单 CPU 系统中，处于运行态的任务只有一个，而在多 CPU 系统中，每个CPU 都有一个处于运行态的任务，处于就绪态和等待状态的任务则可能有多个。

 如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束(内部调用schedule())，则CPU当即进行切换。调度程序所要做的就是维护一张就绪进程列表，当进程用完它的时间片后，它被移到队列的末尾。

---

 对于 TASK_INTERRUPTIBLE 和 TASK_UNINTERRUPTIBLE 补充说明一下：

值	含义	状态
TASK_RUNNING	可执行状态（执行状态、就绪状态）。	执行态或就绪态
TASK_INTERRUPTIBLE	可打断睡眠，可以接受信号并被唤醒，也可以在等待条件全部达成后被显式唤醒(比如wake_up()函数)。	等待状态
TASK_UNINTERRUPTIBLE	不可打断睡眠，只能在等待条件全部达成后被显式唤醒(比如wake_up()函数)。	等待状态

 在Linux中，仅等待CPU时间的进程称为就绪进程，它们被放置在一个就绪队列中，一个就绪进程的状态标志位为TASK_RUNNING。一旦一个运行中的进程时间片用完， Linux 内核的调度器会剥夺这个进程对CPU的控制权，并且从就绪队列中选择一个优先级最高的首进程投入运行。
  当然，一个进程也可以主动释放CPU的控制权。函数 schedule()是一个调度函数，它可以被一个进程主动调用，从而调度其它进程占用CPU。一旦这个主动放弃CPU的进程被重新调度占用 CPU，那么它将从上次停止执行的位置开始执行，也就是说它将从调用schedule()的下一行代码处开始执行。
有时候，进程需要等待直到某个特定的事件发生，例如设备初始化完成、I/O 操作完成或定时器到时等。在这种情况下，进程则必须从运行队列移出（设置当前进程状态为TASK_INTERRUPTIBLE），加入到一个等待队列中（调用schedule()函数），这个时候进程就进入了睡眠状态。

---

3.Linux中进程状态睡眠分类

 在现代的Linux操作系统中，进程一般都是用调用schedule()的方法进入睡眠状态的，下面的代码演示了如何让正在运行的进程进入睡眠状态。

sleeping_task = current;
set_current_state(TASK_INTERRUPTIBLE);
schedule();
func1();
/* Rest of the code ... */

在第一个语句中，程序存储了一份进程结构指针sleeping_task，current 是一个宏，它指向正在执行的进程结构。set_current_state()将该进程的状态从执行状态TASK_RUNNING 变成睡眠状态TASK_INTERRUPTIBLE。
1. 如果schedule()是被一个状态为TASK_RUNNING 的进程调度，那么schedule()将调度另外一个进程占用CPU，当前进程会进入就绪状态，等待下次时间轮转调度。(运行结果会发现，执行当前进程占用的时间会非常少，因为一进来执行到schedule就调度出去了。)
2. 如果schedule()是被一个状态为TASK_INTERRUPTIBLE 或TASK_UNINTERRUPTIBLE 的进程调度，这将导致正在运行的进程进入睡眠，因为它已经不在运行状态中了，被移到了等待状态。（比如运行安装一个驱动程序.ko，结果发现在用户态执行rmmod无法卸载，因为执行卸载的函数进程睡眠了。）
我们可以使用下面的这个函数将刚才那个进入睡眠的进程唤醒:
 wake_up_process(sleeping_task);
在调用了wake_up_process()以后，这个睡眠进程的状态会被设置为TASK_RUNNING，而且调度器会把它加入到就绪状态中去，等待运行。当然，这个进程只有在下次被调度器调度到的时候才能真正地投入运行。

注意：如果当前进程只设置了状态，比如set_current_state(TASK_INTERRUPTIBLE)，而没有执行调度（schedule()），那么时间到达之后仍会将它添加到就绪状态队列，并重置set_current_state(TASK_RUNNING)。

3.1无效唤醒

 设想有两个进程 A和B，A进程正在处理一个链表，它需要检查这个链表是否为空，如果不空就对链表里面的数据进行一些操作，同时B进程也在往这个链表添加节点。当这个链表是空的时候，由于无数据可操作，这时A进程就进入睡眠，当B进程向链表里面添加了节点之后它就唤醒A进程，其代码如下：
A进程：

1 spin_lock(&list_lock);
2 if(list_empty(&list_head)) {
3     spin_unlock(&list_lock);
4     set_current_state(TASK_INTERRUPTIBLE);
5     schedule();
6     spin_lock(&list_lock);
7 }
10 /* Rest of the code ... */
11 spin_unlock(&list_lock);

B进程：

spin_lock(&list_lock);
list_add_tail(&list_head,new_node);
spin_unlock(&list_lock);
wake_up_process(processa_task);

 这里会出现一个问题，假如当A进程执行到第3行后第4行前的时候，B进程被另外一个处理器调度投入运行。在这个时间片内，B进程执行完了它所有的指令，因此它试图唤醒A进程，而此时的A进程还没有进入睡眠，所以唤醒操作无效。在这之后，A进程继续执行，它会错误地认为这个时候链表仍然是空的，于是将自己的状态设置为TASK_INTERRUPTIBLE然后调用schedule()进入睡眠。由于错过了B进程唤醒，它将会无限期的睡眠下去，这就是无效唤醒问题，因为即使链表中有数据需要处理，A 进程也还是睡眠了。

3.2避免无效唤醒

 如何避免无效唤醒问题呢？我们发现无效唤醒主要发生在检查条件之后和进程状态被设置为睡眠状态之前， 本来B进程的wake_up_process()提供了一次将A进程状态置为TASK_RUNNING 的机会，可惜这个时候A进程的状态仍然是TASK_RUNNING，所以wake_up_process()将A进程状态从睡眠状态转变为运行状态的努力 没有起到预期的作用。要解决这个问题，必须使用一种保障机制使得判断链表为空和设置进程状态为睡眠状态成为一个不可分割的步骤才行，也就是必须消除竞争条件产生的根源，这样在这之后出现的wake_up_process ()就可以起到唤醒状态是睡眠状态的进程的作用了。找到了原因后，重新设计一下A进程的代码结构，就可以避免上面例子中的无效唤醒问题了。
A进程:

1 set_current_state(TASK_INTERRUPTIBLE);
2 spin_lock(&list_lock);
3 if(list_empty(&list_head)) {
4 spin_unlock(&list_lock);
5 schedule();
6 spin_lock(&list_lock);
7 }
8 set_current_state(TASK_RUNNING);
9
10 /* Rest of the code ... */
11 spin_unlock(&list_lock);

 可以看到，这段代码在测试条件之前就将当前执行进程状态转设置成TASK_INTERRUPTIBLE了，并且在链表不为空的情况下又将自己置为TASK_RUNNING状态。这样一来如果B进程在A进程进程检查了链表为空以后调用wake_up_process()，那么A进程的状态就会自动由原来TASK_INTERRUPTIBLE变成TASK_RUNNING，此后即使进程又调用了schedule()，由于它现在的状态是TASK_RUNNING，所以仍然不会被从运行队列中移出，因而不会错误的进入睡眠，当然也就避免了无效唤醒问题。

3.3Linux内核的例子

 在Linux操作系统中，内核的稳定性至关重要，为了避免在Linux操作系统内核中出现无效唤醒问题，Linux内核在需要进程睡眠的时候应该使用类似如下的操作：

/* ‘q’是我们希望睡眠的等待队列 */
DECLARE_WAITQUEUE(wait,current);
add_wait_queue(q, &wait);
set_current_state(TASK_INTERRUPTIBLE);
/* 或TASK_INTERRUPTIBLE */
while(!condition) /* ‘condition’ 是等待的条件*/
schedule();
set_current_state(TASK_RUNNING);
remove_wait_queue(q, &wait);

 上面的操作，使得进程通过下面的一系列步骤安全地将自己加入到一个等待队列中进行睡眠：首先调用DECLARE_WAITQUEUE ()创建一个等待队列的项，然后调用add_wait_queue()把自己加入到等待队列中，并且将进程的状态设置为 TASK_INTERRUPTIBLE 或者TASK_INTERRUPTIBLE。然后循环检查条件是否为真：如果是的话就没有必要睡眠，如果条件不为真，就调用schedule()。当进程 检查的条件满足后，进程又将自己设置为TASK_RUNNING 并调用remove_wait_queue()将自己移出等待队列。
 从上面可以看到，Linux的内核代码维护者也是在进程检查条件之前就设置进程的状态为睡眠状态，然后才循环检查条件。如果在进程开始睡眠之前条件就已经达成了，那么循环会退出并用set_current_state()将自己的状态设置为就绪，这样同样保证了进程不会存在错误的进入睡眠的倾向，当然也就不会导致出现无效唤醒问题。

4.总结

 通过上面的讨论，可以发现在Linux 中避免进程的无效唤醒的关键是在进程检查条件之前就将进程的状态置为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE，并且如果检查的条件满足的话就应该将其状态重新设置为TASK_RUNNING。这样无论进程等待的条件是否满足， 进程都不会因为被移出就绪队列而错误地进入睡眠状态，从而避免了无效唤醒问题。