(笔记)Linux内核学习(三)之进程调度

时间:2022-12-17 14:36:21

进程调度:

       在可运行态进程之间分配有限处理器时间资源的内核子系统。

一 调度策略

进程类型

       I/O消耗型进程:大部分时间用来提交I/O请求或是等待I/O请求,经常处于可运行状态,但运行时间短,等待请求过程时处于阻塞状态。如交互式程序。

       处理器消耗型进程:时间大都用在执行代码上,除非被抢占否则一直不停的运行。

       综合型:既是I/O消耗型又是处理器消耗型。

       调度策略要在:进程响应迅速(响应时间短)和最大系统利用率(高吞吐量)之间寻找平衡。

调度概念

       优先级:基于进程价值和对处理器时间需求进行进程分级的调度。

       时间片:表明进程被抢占前所能持续运行的时间,规定一个默认的时间片。时间片过长导致系统交互性的响应不好,

      程序并行性效果差;时间片太短增大进程切换带来的处理器耗时。矛盾!

       时间片耗尽进程运行到期,暂时不可运行状态。直到所有进程时间片都耗尽,重新计算进程时间片。

       Linux调度程序提高交互式程序优先级,提供较长时间片;实现动态调整优先级和时间片长度机制。

       进程抢占:Linux系统是抢占式,始终运行优先级高的进程。

调度算法

       可执行队列:runqueue;给定处理器上可执行进程的链表,每个处理器一个。每个可执行进程都唯一归属于一个可执行队列。

 

运行队列是调度程序中最基本的数据结构:    

(笔记)Linux内核学习(三)之进程调度(笔记)Linux内核学习(三)之进程调度
struct runqueue { 

  spinlock_t lock; /* 保护运行队列的自旋锁*/

  unsigned long nr_running; /* 可运行任务数目*/

  unsigned long nr_switches; /* 上下文切换数目*/

  unsigned long expired_timestamp; /* 队列最后被换出时间*/

  unsigned long nr_uninterruptible; /* 处于不可中断睡眠状态的任务数目*/

  unsigned long long timestamp_last_tick; /* 最后一个调度程序的节拍*/

  struct task_struct *curr; /* 当前运行任务*/

  struct task_struct *idle; /* 该处理器的空任务*/

  struct mm_struct *prev_mm; /* 最后运行任务的mm_struct结构体*/

  struct prio_array *active; /* 活动优先级队列*/

  atomic_t nr_iowait; /* 等待I/O操作的任务数目*/

  ……

};
(笔记)Linux内核学习(三)之进程调度(笔记)Linux内核学习(三)之进程调度

 

 

提供了一组宏来获取给定CPU的进程执行队列:  

  #define cpu_rq(cpu)         //返回给定处理器可执行队列的指针

  #define this_rq() //返回当前处理器的可执行队列

  #define task_rq(p) //返回给定任务所在的队列指针

 

 

在操作处理器任务队列时候要用锁:

__task_rq_lock

……

__task_rq_unlock

 

4 schedule

       系统要选定下一个执行的进程通过调用schedule函数完成。

调度时机:

  l  进程状态转换的时刻:进程终止、进程睡眠;

  l  当前进程的时间片用完时(current->counter=0);

  l  设备驱动程序调用;

  l  进程从中断、异常及系统调用返回到用户态时;

睡眠和唤醒:

       休眠(被阻塞)的进程处于一个特殊的不可执行状态。休眠有两种进程状态:

    TASK_INTERRUPTIBLE:接收到信号就被唤醒

    TASK_UNINTERRUPTIBLE:忽略信号

  两种状态进程位于同一个等待队列上,等待某些事件,不能够运行。

进程休眠策略:  

(笔记)Linux内核学习(三)之进程调度(笔记)Linux内核学习(三)之进程调度
//q是我们希望睡眠的等待队列
DECLARE_WAITQUEUE(wait, current);
add_wait_queue(q, &wait);

//condition 是我们在等待的事件
while (!condition)
{
//将进程状态设为不可执行休眠状态 or TASK_UNINTERRUPTIBLE
set_current_state(TASK_INTERRUPTIBLE);

if(signal_pending(current))
//调度进程
schedule();
}

//进程被唤醒条件满足 进程可执行状态
set_current_state(TASK_RUNNING);

//将进程等待队列中移除
remove_wait_queue(q, &wait);
(笔记)Linux内核学习(三)之进程调度(笔记)Linux内核学习(三)之进程调度

 

 

进程通过执行下面几个步骤将自己加入到一个等待队列中:

  1) 调用DECLARE_WAITQUEUE()创建一个等待队列的项。

 

  2) 调用add_wait_queue()把自己加入到队列中。该队列会在进程等待的条件满足时唤醒它。

    当然我们必须在其他地方撰写相关代码,在事件发生时,对等待队列执行wake_up()操作。

 

  3) 将进程的状态变更为 TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE。

 

  4) 如果状态被置为TASK_INTERRUPTIBLE,则信号唤醒进程。这就是所谓的伪唤醒(唤醒不是因为事件的发生),因此检查并处理信号。

 

  5) 检查条件是否为真;如果是的话,就没必要休眠了。如果条件不为真,调用schedule()。

 

  6) 当进程被唤醒的时候,它会再次检查条件是否为真。如果是,它就退出循环,如果不是,它再次调用schedule()并一直重复这步操作。

 

  7) 当条件满足后,进程将自己设置为TASK_RUNNING并调用remove_wait_queue()把自己移出等待队列。

 

二 抢占和上下文切换

       进程切换schedule函数调用context_switch()函数完成以下工作:

    l  调用定义在<asm/mmu_context.h>中的switch_mm(),该函数负责把虚拟内存从上一个进程映射切换到新进程中。

    l  调用定义在<asm/system.h>中的switch_to(),该函数负责从上一个进程的处理器状态切换到新进程的处理器状态。

      这包括保存、恢复栈信息和寄存器信息。在前面看到schedule函数调用有很多种情况,完全依靠用户来调用不能达到

      很好的效果。内核需要判断什么时候调用schedule,内核提供了一个need_resched标志来表明是否需要重新执行一次调度:

    l  当某个进程耗尽它的时间片时,scheduler_tick()就会设置这个标志;

    l  当一个优先级高的进程进入可执行状态的时候,try_to_wake_up()也会设置这个标志。

  每个进程都包含一个need_resched标志,这是因为访问进程描述符内的数值要比访问一个全局变量快

  (因为current宏速度很快并且描述符通常都在高速缓存中)。

用户抢占

       内核即将返回用户空间时候,如果need_resched标志被设置,会导致schedule函数被调用,此时发生用户抢占。

       用户抢占在以下情况时产生:

    l  从系统调返回用户空间。

    l  从中断处理程序返回用户空间。

内核抢占

       只要重新调度是安全的,那么内核就可以在任何时间抢占正在执行的任务。

什么时候重新调度才是安全的呢?只要没有持有锁,内核就可以进行抢占。锁是非抢占区域的标志。由于内核是支持SMP的,

所以,如果没有持有锁,那么正在执行的代码就是可重新导入的,也就是可以抢占的。

  为了支持内核抢占所作的第一处变动就是为每个进程的thread_info引入了preempt_count计数器。该计数器初始值为0,

每当使用锁的时候数值加1,释放锁的时候数值减1。当数值为0的时候,内核就可执行抢占。从中断返回内核空间的时候,

内核会检查need_resched和preempt_count的值。如果need_resched被设置,并且preempt_count为0的话,这说明

有一个更为重要的任务需要执行并且可以安全地抢占,此时,调度程序就会被调用。

内核抢占会发生在:

  l  当从中断处理程序正在执行,且返回内核空间之前。

  l  当内核代码再一次具有可抢占性的时候。

  l  如果内核中的任务显式的调用schedule()。

  l  如果内核中的任务阻塞(这同样也会导致调用schedule())。