| |
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;
...
} |
|
|
|