Chap4 进程调度

 

抢占式多任务模式——由调度程序来决定什么时候停止一个进程的运行以便其他进程能够执行；

时间片——进程在被抢占之前能够运行的时间是预先设置好的。

4.1 策略

进程——(1) I/O消耗型：进程大部分时间用来提交I/O请求或等待I/O请求

      (2) 处理器消耗型：进程大部分时间用来执行代码

优先级范围——(1) nice值，-20～+19，值越大优先级越低，获取的时间片越短

       (2) 实时优先级，0～99，实时进程的优先级高于普通进程

进程的时间片耗尽时就会挂起，等到其他所有进程都耗尽各自的时间片后，所有进程的时间片会重新计算

4.2 Linux调度算法

调度程序kernel/sched.c

4.2.1 可执行队列

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

 

    struct runqueue {
        spinlock_t lock; /* spin lock that protects this runqueue */
        unsigned long nr_running; /* number of runnable tasks */
        unsigned long nr_switches; /* context switch count */
        unsigned long expired_timestamp; /* time of last array swap */
        unsigned long nr_uninterruptible; /* uninterruptible tasks */
        unsigned long long timestamp_last_tick; /* last scheduler tick */
        struct task_struct *curr; /* currently running task */
        struct task_struct *idle; /* this processor's idle task */
        struct mm_struct *prev_mm; /* mm_struct of last ran task */
        struct prio_array *active; /* active priority array */
        struct prio_array *expired; /* the expired priority array */
        struct prio_array arrays[2]; /* the actual priority arrays */
        struct task_struct *migration_thread; /* migration thread */
        struct list_head migration_queue; /* migration queue*/
        atomic_t nr_iowait; /* number of tasks waiting on I/O */
};

 

4.2.2 优先级数组

每个运行队列有俩个优先级数组，一个是活跃的，一个是过期的。

struct prio_array {
        int               nr_active;         /* number of tasks in the queues任务数目 */
        unsigned long     bitmap[BITMAP_SIZE];  /* priority bitmap 优先级位图*/
        struct list_head  queue[MAX_PRIO];      /* priority queues 优先级队列*/
};

4.2.3 重新计算时间片

两个优先级数组，当一个进程时间片耗尽时，将之移至过期数组，且新的时间片已经计算好，最终切换两数组。

struct prio_array *array = rq->active;
if (!array->nr_active) {
        rq->active = rq->expired;
        rq->expired = array;
}

4.2.4 schedule()

选定下一个进程并切换去执行之。

判断谁是优先级最高的进程：

struct task_struct *prev, *next;
struct list_head *queue;
struct prio_array *array;
int idx;

prev = current;
array = rq->active;
idx = sched_find_first_bit(array->bitmap);
queue = array->queue + idx;
next = list_entry(queue->next, struct task_struct, run_list);

首先，要在活动优先级数组中找到第一个被设置的位，该位对应着优先级最高的可执行进程，然后，调度程序选择这个级别链表中的头一个进程，即系统中优先级最高的可执行程序，夜就是马上会被调度执行的进程。

4.2.2 优先级数组

每个运行队列有俩个优先级数组，一个是活跃的，一个是过期的。

struct prio_array {
        int               nr_active;         /* number of tasks in the queues任务数目 */
        unsigned long     bitmap[BITMAP_SIZE];  /* priority bitmap 优先级位图*/
        struct list_head  queue[MAX_PRIO];      /* priority queues 优先级队列*/
};

4.2.3 重新计算时间片

两个优先级数组，当一个进程时间片耗尽时，将之移至过期数组，且新的时间片已经计算好，最终切换两数组。

struct prio_array *array = rq->active;
if (!array->nr_active) {
        rq->active = rq->expired;
        rq->expired = array;
}

4.2.4 schedule()

选定下一个进程并切换去执行之。

判断谁是优先级最高的进程：

struct task_struct *prev, *next;
struct list_head *queue;
struct prio_array *array;
int idx;

prev = current;
array = rq->active;
idx = sched_find_first_bit(array->bitmap);
queue = array->queue + idx;
next = list_entry(queue->next, struct task_struct, run_list);

首先，要在活动优先级数组中找到第一个被设置的位，该位对应着优先级最高的可执行进程，然后，调度程序选择这个级别链表中的头一个进程，即系统中优先级最高的可执行程序，夜就是马上会被调度执行的进程。

4.2.6、休眠

       等待队列——wait_queue_head_t

       创建：DECLARE_WAITQUEUE()或者init_waitqueue_head()

唤醒

       函数：wake_up()

       步骤：(1) 调用try_to_wake_up()

                    (2) 设置状态TASK_RUNNING

                    (3) activate_task()放入可执行队列

                    (4) 设置need_resched标志（条件：被唤醒进程优先级高）

 

 

/* 'q' is the wait queue we wish to sleep on */
DECLARE_WAITQUEUE(wait, current);

add_wait_queue(q, &wait);
while (!condition) { /* condition is the event that we are waiting for */
        set_current_state(TASK_INTERRUPTIBLE); /* or TASK_UNINTERRUPTIBLE */
        if (signal_pending(current))
                /* handle signal */
        schedule();
}
set_current_state(TASK_RUNNING);
remove_wait_queue(q, &wait);

 

4.2.7、负载平衡程序

       每个处理器有自己的进程链表 => 调度系统对每个处理器来看是独立的

       多处理器系统，负载不均衡的情况 => 负载平衡程序 => 将繁忙队列中进程抽调到非繁忙队列中

        函数：load_balance()

        两种调用方法：schedule()执行时，当前可执行队列为空；

                               定时器调用（系统空闲或其他情况下）。

        步骤：(1) find_busiest_queue()；

         (2) 从最繁忙可执行队列中选一个优先级数组；

         (3) 寻找含有进程且优先级最高的链表；

         (4) 选择不在执行、不因处理器相关性而不可移动的、不再高速缓存中的进程，pull_task()；

         (5) 重复3、4步，消除不平衡后解锁当前队列。

 


static int load_balance(int this_cpu, runqueue_t *this_rq,
                        struct sched_domain *sd, enum idle_type idle)
{
        struct sched_group *group;
        runqueue_t *busiest;
        unsigned long imbalance;
        int nr_moved;

        spin_lock(&this_rq->lock);//锁定当前执行队列


        group = find_busiest_group(sd, this_cpu, &imbalance, idle);
        if (!group)
                goto out_balanced;

        busiest = find_busiest_queue(group);
        if (!busiest)
                goto out_balanced;

        nr_moved = 0;
        if (busiest->nr_running > 1) {
                double_lock_balance(this_rq, busiest);
                nr_moved = move_tasks(this_rq, this_cpu, busiest,
                                      imbalance, sd, idle);
                spin_unlock(&busiest->lock);
        }
        spin_unlock(&this_rq->lock);

        if (!nr_moved) {
                sd->nr_balance_failed++;

                if (unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2)) {
                        int wake = 0;

                        spin_lock(&busiest->lock);
                        if (!busiest->active_balance) {
                                busiest->active_balance = 1;
                                busiest->push_cpu = this_cpu;
                                wake = 1;
                        }
                        spin_unlock(&busiest->lock);
                        if (wake)
                                wake_up_process(busiest->migration_thread);
                        sd->nr_balance_failed = sd->cache_nice_tries;
                }
        } else
                sd->nr_balance_failed = 0;

        sd->balance_interval = sd->min_interval;

        return nr_moved;

out_balanced:
        spin_unlock(&this_rq->lock);

        if (sd->balance_interval < sd->max_interval)
                sd->balance_interval *= 2;

        return 0;
}

 

 4.4、实时

       两种实时调度策略：

       (1) SCHED_FIFO——不使用时间片；比所有SCHED_NORMAL（普通非实时策略）级进程优先级都高；一直执行；多个同级进程情况下轮流执行；

       (2) SCHED_RR——带时间片的SCHED_FIFO

       这两种实时算法都是静态优先级，内核不计算它们的动态优先级。