Home PC Games Linux Windows Database Network Programming Server Mobile  
  Home \ Programming \ Common data structures and functions of Linux process scheduling     - Getting Started with Linux system to learn: How to compress JPEG images on the command line (Linux)

- Using Maven to download Spring (Linux)

- apt-get install openstack pkg Troubleshooting (Linux)

- Linux kernel network subsystem analysis (Programming)

- Oracle database physical file backup / restore (Database)

- C language print various graphic (Programming)

- CentOS 6.5 install Maven and Nexus warehouse agent (Server)

- Android to determine whether the device to open WIFI, GPRS data connection (Programming)

- FastDFS installation and deployment (Server)

- Under CentOS Linux automatic backup MySQL database daily (Database)

- Mind mapping software installed in CentOS 7 in XMind (Linux)

- HTML5 Fundamentals study notes (Programming)

- Linux operating tips: Can not open file for writing or operation not permitted solution (Linux)

- Ubuntu 15.10 install the latest Arduino IDE 1.6.7 (Linux)

- Simple Calendar C language (Programming)

- The basic principle of pointers in C ++ (Programming)

- Installing PHP Memcache extension under Linux (Server)

- Distributed File System using MogileFS (Linux)

- MariaDB 10.1 and MySQL 5.7 in general performance on commodity hardware (Database)

- CentOS 6.5 installation and configuration Cobbler (Server)

  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;


- Transfer MySQL database to MariaDB (Database)
- Execute command sentence can result in equipment permanently bricked in Linux laptop (Linux)
- The Java way to stop a thread of execution (Programming)
- To configure and use multiple Tomcat under Linux environment (Server)
- CentOS 5.10 installed Oracle 11G R2 (Database)
- Install the latest development version of Wine on RedHat and Debian-based systems (Linux)
- Jetty JNDI Development combat (Linux)
- How to network to share files between Windows, MAC and Linux (Linux)
- Netcat Example (Linux)
- ORA-12545: Connection failed because the target host or object does not exist (Database)
- Several Methods of SSH Auto - login (Linux)
- Python Django direct implementation of sql statement (Programming)
- Revive Adserver ad server installation on Ubuntu 15.04 / CentOS7 (Server)
- IntelliJ IDEA common list of shortcuts (Linux)
- CentOS 6.4 installation environment to build Scrapy 0.22 (Linux)
- Linux VMware virtual machine after the cloning of the card can not start to solve (Linux)
- How do you turn on and off IPv6 address on Fedora (Linux)
- How Linux system password security guarantee (Linux)
- Python2 ---- function using dictionaries (Programming)
- Linux system security check notes on performance (Linux)
  CopyRight 2002-2022 newfreesoft.com, All Rights Reserved.