Completely Fair Scheduler

lastmod 2018-08-17created 2015-03-0711 edits

File list

• kernel/sched.c: Core scheduler code.
• kernel/sched_fair.c: Linux's scheduler class for normal processes.

Time accounting

Since each process must use the processor only for its fairly allotted share, the process's running time must be recorded. The related information is stored using a scheduler entity structure called struct sched_entity, defined in linux/sched.h.

It is defined as the se member of the struct task_struct structure, which is used as the process descriptor.

The vruntime variable of the struct task_struct structure stores the process's virtual runtime, which means the actual runtime (the time the process has run) normalized (or weighted) by the number of runnable processes. Virtual runtime is measured in nanoseconds.

Virtual runtime is handled by the update_curr() function defined in kernel/sched_fair.c.

Process selection

A Red–black tree¹ keyed by virtual runtime (vruntime) is used.

• pick_next_entity()
• enqueue_entity(): Adds a process to the tree when it is created via frok().
• dequeue_entity(): Removes a process from the tree when it enters a waiting state(an unrunnable state) or terminates(when it goes away).

Scheduler entry point

Process scheduling starts in the schedule() function, defined in the kernel/sched.c file.

• pick_next_task(): Iterates through the scheduler classes starting from the highest priority one, and finds the highest-priority process in the highest-priority class.

Wait queues

Sleeping is handled using wait queues. A wait queue is a simple list of processes waiting for a particular condition to occur. In the kernel, wait queues are defined with the wake_queue_head_t type.

• DECLARE_WAITQUEUE(): Creates a wait queue statically.
• init_waitqueue_head(): Creates a wait queue dynamically.

If sleeping and waking are not implemented correctly, a race condition can occur.

Sleeping

There are a few simple interfaces widely used for sleeping. However, these interfaces can be subject to race conditions. A task may go to sleep after the condition that should wake it has already occurred. If that happens, the task can never leave the sleeping state. That is why the sleeping procedure recommended by the kernel is somewhat complicated.

DEFINE_WAIT(wait); /* 매크로를 이용해 대기열에 추가할 항목을 만든다. */

/* 'q'는 휴면 상태인 작업이 들어갈 대기열이다. */

add_wait_queue(q, &wait);
while (!condition) { /* condition은 기다리는 조건이 발생한 경우를 뜻한다. */
    prepare_to_wait(&q, &wait, TASK_INTERRUPTIBLE);
    if (signal_pending(current)) {
        /* Signal process. */
    }
    schedule();
}
finish_wait(&q, &wait);

Adding a task to a wait queue goes through the following steps.

A direct example of using wait queues is the inotify_read() function in the fs/notify/inotify/inotify_user.c file, which handles reads from an inotify file descriptor.

Waking up

Waking tasks is handled by the wake_up() function, which wakes all tasks in the given wait queue.

The wake_up() function goes through the following steps.

1. try_to_wake_up(): Changes the task state to TASK_RUNNING.
2. enqueue_task(): Adds the task back to the rbtree.
3. If the priority of the awakened task is higher than that of the currently running task, sets need_resched.

Preemption and context switching

Context switching, which means switching from one running task to another, is handled by the context_switch() function defined in kernel/sched.c.

The context_switch() function handles the following two tasks.

• Calls the switch_mm() function defined in asm/mmu_context.h to switch the virtual memory mapping of the previous process to that of the new process.
• Calls the switch_to() function defined in asm/system.h to switch the processor state of the previous process to that of the current process. This involves saving and restoring the following information.
  • Stack information that must be managed per processor
  • Specific hardware-related information such as processor registers

need_resched flag

The need_resched flag tells the kernel when a reschedule is needed. Below is a list of functions that check and adjust the value.

• set_tsk_need_resched(): Sets the flag for the given process.
• clear_tsk_need_resched(): Clears the flag for the given process.
• need_resched(): Checks the flag value.

The need_resched flag value is checked whenever returning to user space or returning after handling an interrupt.

User preemption and kernel preemption

User preemption occurs in the following cases.

• When returning to user space from a system call
• When returning to user space after handling an interrupt

Kernel preemption occurs in the following cases.

• When returning to kernel space after handling an interrupt
• When kernel code becomes preemptible again
• When a task in the kernel explicitly calls the schedule() function
• When a task in the kernel blocks and enters a waiting state, and so ends up calling the schedule() function

More specific details needed.

Real-time scheduling policies

Real-time policies are managed using a separate special scheduler defined in kernel/sched_rt.c.

• SCHED_FIFO: A simple FIFO scheduling algorithm with no timeslice allocation.
• SCHED_RR: Identical to SCHED_FIFO, except that each process runs only until it uses up a predetermined timeslice. In other words, SCHED_RR is SCHED_FIFO with timeslices.
• SCHED_NORMAL: Non-real-time scheduling policy.

Real-time behavior

Real-time scheduling policies have the following behaviors.

• Soft real-time behavior (Soft reall-time behavior): The kernel tries to schedule applications within a certain deadline, but does not guarantee that it always will.
• Hard real-time behavior (Hard reall-time behavior): Refers to a system that always meets all scheduling requirements within the given deadline.

Linux makes no guarantees about real-time task scheduling. ²

Real-time priorities can range from 0 to MAX_RT_PRIO - 1. The default value of MAX_RT_PRIO is 100.

Scheduler-related system calls

Favorite site

• Description of CFS
• linux kernel lecture 1 - CFS ( Completely Fair Scheduler ) scheduler

References