Home PC Games Linux Windows Database Network Programming Server Mobile  
  Home \ Programming \ Common data structures and functions of Linux process scheduling     - Linux operating system security management skills notes (Linux)

- Java reflection technology explain (Programming)

- Java rewrite the hashcode method (Programming)

- Linux platform to prevent hackers to share practical skills (Linux)

- Android Sets the system screen brightness (Programming)

- iOS in Singleton (Programming)

- Spacewalk Linux system configuration and installation (Linux)

- Disable unnecessary services under Linux (Linux)

- The lambda expression Java8 (constructor references) (Programming)

- Management DB2 logs (Database)

- Modify Linux terminal prompt path length (Linux)

- Encrypted with GnuPG signature to verify the authenticity and integrity of downloaded file (Linux)

- Hadoop 2.6.0 stand-alone / pseudo-distributed installation (Server)

- IntelliJ IDEA run in Mac10.9 and JDK7 environment (Linux)

- How to enhance the Nagios server security (Linux)

- JSON data normalization (normalize) (Programming)

- Shell Common Command Summary (Programming)

- Using the Android interface in Parcelable (Programming)

- CentOS / RedHat system partition essential requirements and partition scheme (Linux)

- Ubuntu Install OpenSSL (Linux)

  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;


- Ubuntu user use PPA to install Uget 2.0.5 (Linux)
- Spring AOP custom annotation way to achieve log management (Programming)
- Remove old kernel on Ubuntu (Linux)
- Bash Automated Customization Linux belongs to its own CentOS system (Linux)
- Tip: Use Cryptsetup U disk encryption (Linux)
- Oracle to use full-text indexing (Database)
- Linux Mint brightness adjustment --xrandr command learning (Linux)
- Linux disk virtualization (Linux)
- CentOS installation of the ftp (Linux)
- Linux environment installation of rvm and ruby (Linux)
- Linux how to handle file names that contain spaces and special characters (Linux)
- Use IF NOT EXISTS create a data table (Database)
- Java polymorphic methods inside constructors complete analysis (Programming)
- Python Dir find a folder several files (Programming)
- 30 Practical Linux system administrators will learn the command (Linux)
- C data types is how it is supported by most computer systems (Programming)
- When Linux virtual machine to another copy of the operating system, a static IP NAT mode Invalid (Linux)
- MongoDB uses aggregate, group, match mysql achieve in having (count (1)> 1) features (Database)
- How to install Linux Go Language (Linux)
- Python type way of comparison (Programming)
  CopyRight 2002-2022 newfreesoft.com, All Rights Reserved.