Use of queues in Linux process scheduling

Process Status


Description

TASK_RUNNING

The process is running or will be running.

TASK_INTERRUPTIBLE

The process is sleeping, waiting for the completion of a condition.

TASK_UNINTERRUPTIBLE

Deep sleep, will not be disturbed by the signal.

TASK_STOPPED

The process run is stopped.

TASK_TRACED

The process is stopped by the debugger and tracked by another process.

two additional states are EXIT_ZOMBIE and EXIT_DEAD, it represents real progress in a dead state or death. A process that is in a dead state will wait for the adoption of its parent process (otherwise it will be adopted by the init process), and the process that is actually dead will be deleted directly.

state TASK_RUNNING process will be placed in the run queue (runqueue), this is by task_struct (defined in include /linux /sched.h) run_list members to links. However, in order for the kernel to pick the most appropriate priority process each time, Linux builds a queue for each priority. This is achieved by a struct prio_array, struct prio_array defined in kernel /sched.c, as follows:

struct prio_array {
int nr_active;
unsigned long bitmap [BITMAP_SIZE];
struct list_head queue [MAX_PRIO];
};

queue is a queue member array. Each CPU has its own runqueue, and each runqueue has two prio_arrays, one for the active queue and one for the time-depleted queue. When the run queue is empty, the kernel swaps the pointers of the two queues, and the original exhaust queue becomes the new active queue! This and the bitmap in the prio_array are the key to determining the scheduling algorithm as O(1).

status process TASK_STOPPED, EXIT_ZOMBIE or EXIT_DEAD not be placed in a special queue, they are directly accessed via pid or child of the parent process queue. Process

TASK_INTERRUPTIBLE TASK_UNINTERRUPTIBLE state and will be placed in the waiting queue. The difference is that each wait event has a wait queue, and the process in the queue waits for the completion of the same event. ( quo;Event” A dynamic process, it is not easy to define an "event" through a specific structure. Waiting for an event here is to see if a condition is true, such as whether a flag variable is true.) wait_queue_head_t defined in include /linux /wait.h as follows:

typedef struct _ _wait_queue_head {
spinlock_t lock;
struct list_head task_list;
} wait_queue_head_t;

wait_queue_t defined as follows:

typedef struct _ _wait_queue {
unsigned int flags;
struct task_struct * task;
wait_queue_func_t func;
struct list_head task_list;
} wait_queue_t;

into a wait state of the interface there are two types:

prepare_to_wait * () /finish_wait ()
wait_event * ()

fact wait_event * () call is internal Prepare_to_wait*(), put it in a loop. And wait_event*() will automatically call finish_wait() when the event completes. Decide which one to use depending on the situation. (sleep_on*() is an abandoned interface that is no longer used, although it is also supported.) There are two types of processes waiting in the queue, one is exclusive and the other is nonexclusive. The so-called exclusive means that the resources waiting for the wake-up process are mutually exclusive, and only wake up one at a time (wake up multiples, but only one will wake up in the end, and the rest will be added to the waiting queue again, so the efficiency will be Great discount). In general, the wait function will set the process to nonexclusive and uninterruptible, and the "interruptible" will specifically specify the state as interruptible; and the "timeout" will exit after the timeout, because it will call schedule_timeout(); with “ Exclusive” will set the process to exclusive.

wake of the interface, although only wake_up * (), but it is also divided into several interior. The wake-up function with "interruptible" will only wake up the process whose state is TASK_INTERRUPTIBLE, without the process of waking up TASK_INTERRUPTIBLE and TASK_UNINTERRUPTIBLE; all wake-up functions will wake up all nonexclusive processes waiting for the same event, or one of them exclusive The process wakes up; and with "nr", it will wake up the specified number of exclusive processes, with “all” will wake up all exclusive processes. With “sync” will ignore the priority check, high priority processes may be delayed. Finally, only wait_up_locked() can be called when holding a spin lock.

Linux kernel process management is the most critical part, its performance is almost directly determines the quality of the kernel, some of the design and the use of algorithms which are very complex. This is just to introduce the use of the queue in it, and further exploration is still to be explored.