Home PC Games Linux Windows Database Network Programming Server Mobile  
  Home \ Programming \ Common data structures and functions of Linux process scheduling     - C ++ Object Model Comments (Programming)

- awk Programming Model (Programming)

- GNU Linux use diff to generate a patch with the patch (Linux)

- Linux virtual machine how to access the Internet in a virtual machine when using NAT mode (Linux)

- Swift used in the application to add a local push at the specified time (Programming)

- Java loop list to solve the problem of Joseph ring (Programming)

- Ubuntu 14.04 install Nmap 6.46.1 (Linux)

- DupeGuru- find and remove duplicate files (Linux)

- Using Oracle for Oracle GoldenGate to achieve a one-way data synchronization (Database)

- How to build a custom exclusive Ubuntu Live CD (Linux)

- Oracle 11g maintenance partitions (eight) - Renaming Partitions (Database)

- CentOS RedHat YUM Source Extensions Supplement (including 32-bit, 64-bit) (Linux)

- To install Xen in Ubuntu 12.04 (Linux)

- C language to view various types of data size (Programming)

- Linux systems use IP masquerading anti-hacker (Linux)

- Ruby and Python simple comparison (Programming)

- Android Action Compendium (Programming)

- Linux configuration Samba server (Server)

- Install RAID 6 (Striping double distributed parity) (Linux)

- fcntl file locking function add (Programming)

  Common data structures and functions of Linux process scheduling
  Add Date : 2018-11-21      
  Linux2.4 kernel process scheduling flaw:

Linux2.4 kernel process scheduling using round-robin scheduling policy and priority combination, but there are several fatal flaws:

1> scheduling algorithm time complexity is O (n). 2.4 kernel scheduling should be carried out once every cycle, with the current number of ready-consuming process, and therefore not reach the real-time requirements; task_struct structure and must be ready to process queue is locked when the time slice recalculation.

2> does not provide preemptive scheduling, it will cause a lot of competition, so that the ready queue to become a significant bottleneck;

3> SMP system, only a ready queue, which causes most of the CPU is idle, thus affecting the efficiency of SMP;

Linux2.6 kernel process scheduling analysis

Timing and cause scheduling process scheduling and process scheduling reasons related to the way process. Start the scheduler works in the following three occasion in the case of 2.6, in addition to the active core application calls the scheduler, the core of the application is still not fully aware of:

1> return from interrupt or system calls to user mode;

2> Allow a process is preempted CPU;

3> Active sleeping;

Scheduling policies:

In Linux2.6, there are still three scheduling policies: SCHED_OTHER, SCHED_FIFO and SCHED_RR.

SCHED_ORHER: a normal process, priority-based scheduling.

SCHED_FIFO: real-time process, to achieve a simple FIFO scheduling algorithm.

SCHED_RR: real-time process, based on the time slice SCHED_FIFO, turn real-time scheduling algorithm.

The former is an ordinary process of scheduling strategy, the latter two are real-time process scheduling policy.

SCHED_FIFO and SCHED_RR difference is:

When scheduling process for the former, the current real-time process will remain occupied until the CPU automatically exit, unless there is a more urgent, higher priority needs to run real-time process, it will be preempted CPU; scheduling policy when the process is the latter, along with other real-time processes in real-time algorithm to turn the common use CPU, running out of time slice into the tail of the queue.

Note: The priority real-time processes than ordinary process, described later.

O (1) scheduler is dynamic priority prio for the scheduling process is based, it is always present, ready to select the highest priority queue process as a candidate process next. Since the priority real-time process is always a higher priority than the ordinary process, it can guarantee real-time process is always better than a normal process to be scheduled.

Linux2.6, the priority prio computing is no longer concentrated on the next selection process scheduler, but scattered in the process

Whenever the state changes, the timing of these are:

1> when the process is created;

2> wake up when the sleep process;

3> from TASK_INTERRUPTIBLE state process is scheduled to be awakened when;

4> or depleted due to the time slice time slice too long segment when deprived CPU;

In these cases, the kernel will call effective_prio () recalculation process dynamic priority prio and adjust its position in the ready queue based on the calculation result.
Scheduling Algorithm:

O (1) scheduler important data structure

(1) the ready queue struct runqueue

runqueue design is O (1) scheduler where the key technology, which is used to store the ready process queue information on a specific CPU, which includes scheduling information for each CPU. The structure is defined in /kernel/sched.c are as follows:

struct runqueue {


prio_array_t * active, * expired, array [2];

active point is an active process queue pointer

expired expired process queue is a pointer to a pointer

array [2] is the actual process of priority queues, one of which is an active expired, expired array storage time slice depletion process



In 2.6, each individual CPU maintains a ready queue, and each has a ready queue spin lock to solve the bottleneck of 2.4 due to only a ready queue caused.

(2) task_struct structure

Linux2.6 kernel uses task_struct structure to represent the process. 2.6 pairs task_struct also made major changes,

The structure is defined in /include/linux/sched.h in:

struct task_struct {


int prio, static_prio;

prio is the dynamic priority, static_prio static priority (nice correlation with the original)


prio_array_t * array;

Record current active CPU ready queue

unsigned long sleep_avg;

The average waiting time for the process, in the range [0, MAX_SLEEP_AVG], the initial value is zero. sleep_avg reflects the urgency of the process needs to run. The process of dormancy value increases, if the process is currently running decrease the value. Process priority is the impact of the most important elements. The higher the value, the more shows that the process needs to be scheduled.



(3) the priority of the group

Each processor has two ready queue priority array (acitve expired arrays and arrays), which are structures prio_array type. Linux2.6 kernel is precisely because of the use of the priority of the group, it was able to achieve O (1) scheduling algorithm. The structure is defined in kernel / sched.c in:

struct prio_array {


unsigned int nr_active;

/ ** Corresponding number of processes runqueue

unsigned long bitmap [BITMAP_SIZE];

/ ** Bitmap index, BITMAP_SIZE default value is 5, 5 long (32-bit) type, each represents a priority, can represent 160 priority, but in practice only 140.

With the underlying queue [] correspond.

0-99 correspond to the distribution of real-time process, 100-140 correspond to the ordinary process

struct list_head queue [MAX_PRIO];

/ ** Each priority queue of processes, MAX_PRIO is the highest priority system allows the series, the default value is 140, the smaller the value, the higher the priority bitmap each bit corresponds to queue [i], when the queue [i ] process queue is not empty, bitmap corresponding bit is 1, otherwise it is zero.


O (1) scheduling algorithm to achieve brief

(1) Select and run the next candidate process that determines the next process should occupy CPU and run, schedule () function is the main function of the completion of the process of scheduling and completion of the process of switching. schedule () code is used to determine the highest priority process is very fast and efficient, its performance has a direct impact on system performance, which is defined in /kernel/sched.c are as follows:


int idx;


preempt_disable ();


idx = sched_find_first_bit (array -> bitmap);

queue = array -> queue + idx;

next = list_entry (queue -> next, task_t, run_list);


prev = context_switch (rq, prev, next);



Wherein, sched_find_first_bit () to quickly locate the highest priority nonempty process list ready, the running time and the number of processes in the ready queue irrelevant, is a key to achieving O (1) scheduling algorithm.

schedule () implementation process: First, call pre_empt_disable (), close the kernel preemption, because at this time to a number of important data structures of the kernel to operate, it must be closed kernel preemption; secondly, calls sched_find_first_bit () to find bitmap the first one bit set to 1, this bit corresponds exactly to the ready queue of the highest priority process list; furthermore, calls context_switch () to perform the process of switching to select the highest priority in the list of processes put into operation the first one;
Grid for the 140 priority array, queue [7] for the priority list of ready processes 7.

Such algorithm ensures that the time limit the scheduler to run, it accelerated the process of positioning the candidate process.
(2) Calculation of the time slice and timing

Linux2.4 scheduling system at a later time sheets all ready processes are depletion-time recalculation scheduler, wherein the weight be used for cycle time-consuming.

Linux2.6 reserved for each CPU two active and expired priority array, active array contains a surplus of time slice task, expired array contains all spent time slice task.

When the time runs out slice of a task will recalculate its time slice, and inserted into the expired queue, active queue when all processes run out of time slice, just exchange a pointer to active and expired queues. This exchange is to achieve O (1) algorithm is the core of the schedule () program to achieve the following:

array = rq -> active;

if (unlikely (! array-> nr_active)) {

rq -> active = rq -> expired;

rq -> expired = array;

array = rq -> active;


- Configuring ftp server and nfs server under Linux (Server)
- Use LKM change the default linux security level (Linux)
- Swift notes - let you two hours to learn Swift (Programming)
- Linux Firewall IPCop Profile (Linux)
- Oracle RMAN-06023 and ORA-19693 errors (Database)
- Linux redirection and piping (Linux)
- Django how to generate content in non-HTML formats (Programming)
- To install Xen in Ubuntu 12.04 (Linux)
- HTTPS Encryption Algorithm (Linux)
- To share some very useful Vim command (Linux)
- MongoDB query statistics grouping remove duplicate records (Database)
- Extended use of the swap file swap space on Linux (Linux)
- Postmodern systems programming language (Programming)
- Linux Mint 17 set up the Ruby environment (Linux)
- CentOS / Linux install VNC Server (Linux)
- CentOS6.0 successful installation and configuration OpenCV (Linux)
- exp / imp Export Import version of the problem and the ORA-6550 error (Database)
- Python several standard types of built-in functions (Programming)
- The most commonly used Linux commands (Linux)
- configuration ssh without password under Linux (Linux)
  CopyRight 2002-2022 newfreesoft.com, All Rights Reserved.