Home PC Games Linux Windows Database Network Programming Server Mobile  
  Home \ Programming \ Common data structures and functions of Linux process scheduling     - Java generate two-dimensional code by Zxing (Programming)

- JavaScript function part (Programming)

- Actual custom yum repository ---- gem commands commonly used parameters (Linux)

- Ubuntu study notes and related problem solving (Linux)

- CentOS 5.3 under broadcom NIC dual activation issues (Linux)

- Android custom controls create the simplest skid menu in the history (Programming)

- Ftp user to create multiple virtual machines to support different access rights Examples (Server)

- Additional SQL Server 5123 database reported error (Database)

- Linux environmental performance data acquisition system (Linux)

- Python decorators to learn and practice the actual usage scenarios (Programming)

- Linux Quick Install MongoDB (Database)

- Is Linux the most secure operating system (Linux)

- Running the open-source Swift under Linux platform (Linux)

- MySQL uses mysqld_multi to deploy stand-alone multi-instance detail procedures (Database)

- ASM Management - How to Rename diskgroup (Database)

- To configure and use multiple Tomcat under Linux environment (Server)

- Ubuntu 10.10 install Oracle 10g Installation Guide (Database)

- CentOS installation Percona Server 5.5.42 compiling problem solve one case (Linux)

- Oracle 11g em start newspaper site's security certificate has a solution to the problem (Database)

- Java loop list to solve the problem of Joseph ring (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;


- Java multi-threaded communications pipeline flow (Programming)
- Docker Basic Concepts (Linux)
- 30 Practical Linux system administrators will learn the command (Linux)
- OpenSUSE / Linux network configuration (Linux)
- The method to mount the CD under Linux (Linux)
- How to update the Linux kernel to improve system performance (Linux)
- Linux, MySQL / MariaDB Galera Cluster Setup Process (Database)
- NFS installation process under the CentOS (Linux)
- Detailed Linux su command to switch users Mistakes (Linux)
- IP Security Policy is to learn how to prevent Ping and closed ports (Linux)
- How to understand the difference between synchronous and asynchronous non-blocking blocking (Programming)
- How to configure security services under Linux (Linux)
- Python2 ---- function using dictionaries (Programming)
- Json Applications of FastJson (Programming)
- Install Open vSwitch under CentOS 6.5 (Linux)
- CentOS 7.1 install NTFS-3G (Linux)
- CentOS 6.6 install Oracle 11gR2 database (Database)
- Math objects easily overlooked but very convenient method --JavaScript (Programming)
- To modify the existing user ID and comments GPG key (Linux)
- RegExp object implements regular match --JavaScript (Programming)
  CopyRight 2002-2020 newfreesoft.com, All Rights Reserved.