当前位置: 技术问答>linux和unix
2.6 调度，初级问题，大家指教
来源: 互联网 发布时间：2016-08-21
本文导语: 调度策略： 在 Linux2.6 中,仍有三种调度策略: SCHED_OTHER、SCHED_FIFO 和 SCHED_RR。 SCHED_ORHER:普通进程，基于优先级进行调度。 SCHED_FIFO：实时进程，实现一种简单的先进先出的调度算法。 SCHED_RR：实时进...
调度策略：
在 Linux2.6 中,仍有三种调度策略: SCHED_OTHER、SCHED_FIFO 和 SCHED_RR。
SCHED_ORHER:普通进程，基于优先级进行调度。
SCHED_FIFO：实时进程，实现一种简单的先进先出的调度算法。
SCHED_RR：实时进程，基于时间片的SCHED_FIFO,实时轮流调度算法。
前者是普通进程调度策略,后两者都是实时进程调度策略。
SCHED_FIFO 与 SCHED_RR 的区别是:
当进程的调度策略为前者时,当前实时进程将一直占用 CPU 直至自动退出,除非有更紧迫的、
优先级更高的实时进程需要运行时,它才会被抢占 CPU;当进程的调度策略
为后者时,它与其它实时进程以实时轮流算法去共同使用 CPU，用完时间片放到运行队列尾部。
kernel：2.6.22
1.SCHED_FIFO的情况下，如果没有比当前更高的优先级，那么当前进程会一直运行下去。 问：那么如果来了一个更高的，那么抢占是如何发生的？当前cpu要运行哪段代码才知道有更高的进程，并让他运行的呢，我看了一下schedule（）里并没有涉及到SCHED_FIFO宏， 也没发现有什么抢占的痕迹.
2.SCHED_FIFO SCHED_RR 是如何实现的呢, 搜了一下代码，之后很少几个地方有SCHED_FIFO SCHED_RR
以上问题，希望大家能够那代码说话，如果是理论，那么Google就可以了，right？
在 Linux2.6 中,仍有三种调度策略: SCHED_OTHER、SCHED_FIFO 和 SCHED_RR。
SCHED_ORHER:普通进程，基于优先级进行调度。
SCHED_FIFO：实时进程，实现一种简单的先进先出的调度算法。
SCHED_RR：实时进程，基于时间片的SCHED_FIFO,实时轮流调度算法。
前者是普通进程调度策略,后两者都是实时进程调度策略。
SCHED_FIFO 与 SCHED_RR 的区别是:
当进程的调度策略为前者时,当前实时进程将一直占用 CPU 直至自动退出,除非有更紧迫的、
优先级更高的实时进程需要运行时,它才会被抢占 CPU;当进程的调度策略
为后者时,它与其它实时进程以实时轮流算法去共同使用 CPU，用完时间片放到运行队列尾部。
kernel：2.6.22
1.SCHED_FIFO的情况下，如果没有比当前更高的优先级，那么当前进程会一直运行下去。 问：那么如果来了一个更高的，那么抢占是如何发生的？当前cpu要运行哪段代码才知道有更高的进程，并让他运行的呢，我看了一下schedule（）里并没有涉及到SCHED_FIFO宏， 也没发现有什么抢占的痕迹.
2.SCHED_FIFO SCHED_RR 是如何实现的呢, 搜了一下代码，之后很少几个地方有SCHED_FIFO SCHED_RR
以上问题，希望大家能够那代码说话，如果是理论，那么Google就可以了，right？
|
以下内容摘自经典的书籍ULK第三版：
第7章第1节，由于中文的pdf版本，不能复制，所以贴出原版内容，网友可以对照中文版看。
7.1. Scheduling Policy
The scheduling algorithm of traditional Unix operating systems must fulfill several conflicting objectives: fast process response time, good throughput for background jobs, avoidance of process starvation, reconciliation of the needs of low- and high-priority processes, and so on. The set of rules used to determine when and how to select a new process to run is called scheduling policy .
Linux scheduling is based on the time sharing technique: several processes run in "time multiplexing" because the CPU time is divided into slices, one for each runnable process.[*] Of course, a single processor can run only one process at any given instant. If a currently running process is not terminated when its time slice or quantum expires, a process switch may take place. Time sharing relies on timer interrupts and is thus transparent to processes. No additional code needs to be inserted in the programs to ensure CPU time sharing.
[*] Recall that stopped and suspended processes cannot be selected by the scheduling algorithm to run on a CPU.
The scheduling policy is also based on ranking processes according to their priority. Complicated algorithms are sometimes used to derive the current priority of a process, but the end result is the same: each process is associated with a value that tells the scheduler how appropriate it is to let the process run on a CPU.
In Linux, process priority is dynamic. The scheduler keeps track of what processes are doing and adjusts their priorities periodically; in this way, processes that have been denied the use of a CPU for a long time interval are boosted by dynamically increasing their priority. Correspondingly, processes running for a long time are penalized by decreasing their priority.
When speaking about scheduling, processes are traditionally classified as I/O-bound or CPU-bound. The former make heavy use of I/O devices and spend much time waiting for I/O operations to complete; the latter carry on number-crunching applications that require a lot of CPU time.
An alternative classification distinguishes three classes of processes:
Interactive processes
These interact constantly with their users, and therefore spend a lot of time waiting for keypresses and mouse operations. When input is received, the process must be woken up quickly, or the user will find the system to be unresponsive. Typically, the average delay must fall between 50 and 150 milliseconds. The variance of such delay must also be bounded, or the user will find the system to be erratic. Typical interactive programs are command shells, text editors, and graphical applications.
Batch processes
These do not need user interaction, and hence they often run in the background. Because such processes do not need to be very responsive, they are often penalized by the scheduler. Typical batch programs are programming language compilers, database search engines, and scientific computations.
Real-time processes
These have very stringent scheduling requirements. Such processes should never be blocked by lower-priority processes and should have a short guaranteed response time with a minimum variance. Typical real-time programs are video and sound applications, robot controllers, and programs that collect data from physical sensors.
The two classifications we just offered are somewhat independent. For instance, a batch process can be either I/O-bound (e.g., a database server) or CPU-bound (e.g., an image-rendering program). While real-time programs are explicitly recognized as such by the scheduling algorithm in Linux, there is no easy way to distinguish between interactive and batch programs. The Linux 2.6 scheduler implements a sophisticated heuristic algorithm based on the past behavior of the processes to decide whether a given process should be considered as interactive or batch. Of course, the scheduler tends to favor interactive processes over batch ones.
Programmers may change the scheduling priorities by means of the system calls illustrated in Table 7-1. More details are given in the section "System Calls Related to Scheduling."
Table 7-1. System calls related to scheduling System call
Description
nice( )
Change the static priority of a conventional process
getpriority( )
Get the maximum static priority of a group of conventional processes
setpriority( )
Set the static priority of a group of conventional processes
sched_getscheduler( )
Get the scheduling policy of a process
sched_setscheduler( )
Set the scheduling policy and the real-time priority of a process
sched_getparam( )
Get the real-time priority of a process
sched_setparam( )
Set the real-time priority of a process
sched_yield( )
Relinquish the processor voluntarily without blocking
sched_get_ priority_min( )
Get the minimum real-time priority value for a policy
sched_get_ priority_max( )
Get the maximum real-time priority value for a policy
sched_rr_get_interval( )
Get the time quantum value for the Round Robin policy
sched_setaffinity( )
Set the CPU affinity mask of a process
sched_getaffinity( )
Get the CPU affinity mask of a process
7.1.1. Process Preemption
As mentioned in the first chapter, Linux processes are preemptable. When a process enters the TASK_RUNNING state, the kernel checks whether its dynamic priority is greater than the priority of the currently running process. If it is, the execution of current is interrupted and the scheduler is invoked to select another process to run (usually the process that just became runnable). Of course, a process also may be preempted when its time quantum expires. When this occurs, the TIF_NEED_RESCHED flag in the thread_info structure of the current process is set, so the scheduler is invoked when the timer interrupt handler terminates.
For instance, let's consider a scenario in which only two programsa text editor and a compilerare being executed. The text editor is an interactive program, so it has a higher dynamic priority than the compiler. Nevertheless, it is often suspended, because the user alternates between pauses for think time and data entry; moreover, the average delay between two keypresses is relatively long. However, as soon as the user presses a key, an interrupt is raised and the kernel wakes up the text editor process. The kernel also determines that the dynamic priority of the editor is higher than the priority of current, the currently running process (the compiler), so it sets the TIF_NEED_RESCHED flag of this process, thus forcing the scheduler to be activated when the kernel finishes handling the interrupt. The scheduler selects the editor and performs a process switch; as a result, the execution of the editor is resumed very quickly and the character typed by the user is echoed to the screen. When the character has been processed, the text editor process suspends itself waiting for another keypress and the compiler process can resume its execution.
Be aware that a preempted process is not suspended, because it remains in the TASK_RUNNING state; it simply no longer uses the CPU. Moreover, remember that the Linux 2.6 kernel is preemptive, which means that a process can be preempted either when executing in Kernel or in User Mode; we discussed in depth this feature in the section "Kernel Preemption" in Chapter 5.
7.1.2. How Long Must a Quantum Last?
The quantum duration is critical for system performance: it should be neither too long nor too short.
If the average quantum duration is too short, the system overhead caused by process switches becomes excessively high. For instance, suppose that a process switch requires 5 milliseconds; if the quantum is also set to 5 milliseconds, then at least 50 percent of the CPU cycles will be dedicated to process switching.[*]
[*] Actually, things could be much worse than this; for example, if the time required for the process switch is counted in the process quantum, all CPU time is devoted to the process switch and no process can progress toward its termination.
If the average quantum duration is too long, processes no longer appear to be executed concurrently. For instance, let's suppose that the quantum is set to five seconds; each runnable process makes progress for about five seconds, but then it stops for a very long time (typically, five seconds times the number of runnable processes).
It is often believed that a long quantum duration degrades the response time of interactive applications. This is usually false. As described in the section "Process Preemption" earlier in this chapter, interactive processes have a relatively high priority, so they quickly preempt the batch processes, no matter how long the quantum duration is.
In some cases, however, a very long quantum duration degrades the responsiveness of the system. For instance, suppose two users concurrently enter two commands at the respective shell prompts; one command starts a CPU-bound process, while the other launches an interactive application. Both shells fork a new process and delegate the execution of the user's command to it; moreover, suppose such new processes have the same initial priority (Linux does not know in advance if a program to be executed is batch or interactive). Now if the scheduler selects the CPU-bound process to run first, the other process could wait for a whole time quantum before starting its execution. Therefore, if the quantum duration is long, the system could appear to be unresponsive to the user that launched the interactive application.
The choice of the average quantum duration is always a compromise. The rule of thumb adopted by Linux is choose a duration as long as possible, while keeping good system response time.
第7章第1节，由于中文的pdf版本，不能复制，所以贴出原版内容，网友可以对照中文版看。
7.1. Scheduling Policy
The scheduling algorithm of traditional Unix operating systems must fulfill several conflicting objectives: fast process response time, good throughput for background jobs, avoidance of process starvation, reconciliation of the needs of low- and high-priority processes, and so on. The set of rules used to determine when and how to select a new process to run is called scheduling policy .
Linux scheduling is based on the time sharing technique: several processes run in "time multiplexing" because the CPU time is divided into slices, one for each runnable process.[*] Of course, a single processor can run only one process at any given instant. If a currently running process is not terminated when its time slice or quantum expires, a process switch may take place. Time sharing relies on timer interrupts and is thus transparent to processes. No additional code needs to be inserted in the programs to ensure CPU time sharing.
[*] Recall that stopped and suspended processes cannot be selected by the scheduling algorithm to run on a CPU.
The scheduling policy is also based on ranking processes according to their priority. Complicated algorithms are sometimes used to derive the current priority of a process, but the end result is the same: each process is associated with a value that tells the scheduler how appropriate it is to let the process run on a CPU.
In Linux, process priority is dynamic. The scheduler keeps track of what processes are doing and adjusts their priorities periodically; in this way, processes that have been denied the use of a CPU for a long time interval are boosted by dynamically increasing their priority. Correspondingly, processes running for a long time are penalized by decreasing their priority.
When speaking about scheduling, processes are traditionally classified as I/O-bound or CPU-bound. The former make heavy use of I/O devices and spend much time waiting for I/O operations to complete; the latter carry on number-crunching applications that require a lot of CPU time.
An alternative classification distinguishes three classes of processes:
Interactive processes
These interact constantly with their users, and therefore spend a lot of time waiting for keypresses and mouse operations. When input is received, the process must be woken up quickly, or the user will find the system to be unresponsive. Typically, the average delay must fall between 50 and 150 milliseconds. The variance of such delay must also be bounded, or the user will find the system to be erratic. Typical interactive programs are command shells, text editors, and graphical applications.
Batch processes
These do not need user interaction, and hence they often run in the background. Because such processes do not need to be very responsive, they are often penalized by the scheduler. Typical batch programs are programming language compilers, database search engines, and scientific computations.
Real-time processes
These have very stringent scheduling requirements. Such processes should never be blocked by lower-priority processes and should have a short guaranteed response time with a minimum variance. Typical real-time programs are video and sound applications, robot controllers, and programs that collect data from physical sensors.
The two classifications we just offered are somewhat independent. For instance, a batch process can be either I/O-bound (e.g., a database server) or CPU-bound (e.g., an image-rendering program). While real-time programs are explicitly recognized as such by the scheduling algorithm in Linux, there is no easy way to distinguish between interactive and batch programs. The Linux 2.6 scheduler implements a sophisticated heuristic algorithm based on the past behavior of the processes to decide whether a given process should be considered as interactive or batch. Of course, the scheduler tends to favor interactive processes over batch ones.
Programmers may change the scheduling priorities by means of the system calls illustrated in Table 7-1. More details are given in the section "System Calls Related to Scheduling."
Table 7-1. System calls related to scheduling System call
Description
nice( )
Change the static priority of a conventional process
getpriority( )
Get the maximum static priority of a group of conventional processes
setpriority( )
Set the static priority of a group of conventional processes
sched_getscheduler( )
Get the scheduling policy of a process
sched_setscheduler( )
Set the scheduling policy and the real-time priority of a process
sched_getparam( )
Get the real-time priority of a process
sched_setparam( )
Set the real-time priority of a process
sched_yield( )
Relinquish the processor voluntarily without blocking
sched_get_ priority_min( )
Get the minimum real-time priority value for a policy
sched_get_ priority_max( )
Get the maximum real-time priority value for a policy
sched_rr_get_interval( )
Get the time quantum value for the Round Robin policy
sched_setaffinity( )
Set the CPU affinity mask of a process
sched_getaffinity( )
Get the CPU affinity mask of a process
7.1.1. Process Preemption
As mentioned in the first chapter, Linux processes are preemptable. When a process enters the TASK_RUNNING state, the kernel checks whether its dynamic priority is greater than the priority of the currently running process. If it is, the execution of current is interrupted and the scheduler is invoked to select another process to run (usually the process that just became runnable). Of course, a process also may be preempted when its time quantum expires. When this occurs, the TIF_NEED_RESCHED flag in the thread_info structure of the current process is set, so the scheduler is invoked when the timer interrupt handler terminates.
For instance, let's consider a scenario in which only two programsa text editor and a compilerare being executed. The text editor is an interactive program, so it has a higher dynamic priority than the compiler. Nevertheless, it is often suspended, because the user alternates between pauses for think time and data entry; moreover, the average delay between two keypresses is relatively long. However, as soon as the user presses a key, an interrupt is raised and the kernel wakes up the text editor process. The kernel also determines that the dynamic priority of the editor is higher than the priority of current, the currently running process (the compiler), so it sets the TIF_NEED_RESCHED flag of this process, thus forcing the scheduler to be activated when the kernel finishes handling the interrupt. The scheduler selects the editor and performs a process switch; as a result, the execution of the editor is resumed very quickly and the character typed by the user is echoed to the screen. When the character has been processed, the text editor process suspends itself waiting for another keypress and the compiler process can resume its execution.
Be aware that a preempted process is not suspended, because it remains in the TASK_RUNNING state; it simply no longer uses the CPU. Moreover, remember that the Linux 2.6 kernel is preemptive, which means that a process can be preempted either when executing in Kernel or in User Mode; we discussed in depth this feature in the section "Kernel Preemption" in Chapter 5.
7.1.2. How Long Must a Quantum Last?
The quantum duration is critical for system performance: it should be neither too long nor too short.
If the average quantum duration is too short, the system overhead caused by process switches becomes excessively high. For instance, suppose that a process switch requires 5 milliseconds; if the quantum is also set to 5 milliseconds, then at least 50 percent of the CPU cycles will be dedicated to process switching.[*]
[*] Actually, things could be much worse than this; for example, if the time required for the process switch is counted in the process quantum, all CPU time is devoted to the process switch and no process can progress toward its termination.
If the average quantum duration is too long, processes no longer appear to be executed concurrently. For instance, let's suppose that the quantum is set to five seconds; each runnable process makes progress for about five seconds, but then it stops for a very long time (typically, five seconds times the number of runnable processes).
It is often believed that a long quantum duration degrades the response time of interactive applications. This is usually false. As described in the section "Process Preemption" earlier in this chapter, interactive processes have a relatively high priority, so they quickly preempt the batch processes, no matter how long the quantum duration is.
In some cases, however, a very long quantum duration degrades the responsiveness of the system. For instance, suppose two users concurrently enter two commands at the respective shell prompts; one command starts a CPU-bound process, while the other launches an interactive application. Both shells fork a new process and delegate the execution of the user's command to it; moreover, suppose such new processes have the same initial priority (Linux does not know in advance if a program to be executed is batch or interactive). Now if the scheduler selects the CPU-bound process to run first, the other process could wait for a whole time quantum before starting its execution. Therefore, if the quantum duration is long, the system could appear to be unresponsive to the user that launched the interactive application.
The choice of the average quantum duration is always a compromise. The rule of thumb adopted by Linux is choose a duration as long as possible, while keeping good system response time.
|
我在上班，没太多时间check整个内核的代码来检查代码的逻辑，只是简单的写一下，希望能对楼主有帮
助。你前面说的那些我就不重复了
1、实际上在每个进程创建的时候，它本质上都是以线程的形态存在的，大于或等于一个。在PC上，线程
默认的调度policy是SCHED_OTHER，在这种policy下，是没有prority一说的，你可以用
sched_get_priority_max()和sched_get_priority_min()函数来验证一下，返回值全是0。
而后两种的优先级范围是1-99，至少在我的系统上是这样，同样是上面的两个函数或得到。
2、因为现在Linux的线程库多是NPTL，而它的实现机制和POSIX的标准还有些不同。如果是用SCHED_FIFO
或者SCHED_RR的调度policy，那么肯定会在线程创建之前设置线程的调度policy，这个是用这个函数实现
的pthread_attr_setschedpolicy()。既然这样，那问题就简单了，只要跟进这个函数看下，就知道它是
怎么作用给内核的了。以下是在Glibc 2.10.1中的源代码：
这个函数没必要讲了，内容很简单，注释也很详细。关键的一点就是将新的调度policy保存到thread的属
性结构体中。接下来再看一下这个属性结构体是用来干嘛的，如下：
注意这个结构体的第一个field，
/* The official definition. */
struct sched_param
{
int __sched_priority;
};
它是一个调度参数，也就是说在调度器调度的时候，它会check这个参数的值，然后来决定怎么调度。
接下来的分析，就是你在内核中看到了的。简单的总结一下这套流程就是：
进程创建的时候，以线程的形态来执行，进程只是负责申请、分配资源
如果线程是实时调度的，那就会通过glibc里提供的POSIX接口来动态设置自己的policy，然后作用于调度参数上
调度器在调度的时候，又会参照调度参数中的值来决定该怎么做。
PS:匆匆写的东西，未必正确。有问题可以跟帖拍砖
助。你前面说的那些我就不重复了
1、实际上在每个进程创建的时候，它本质上都是以线程的形态存在的，大于或等于一个。在PC上，线程
默认的调度policy是SCHED_OTHER，在这种policy下，是没有prority一说的，你可以用
sched_get_priority_max()和sched_get_priority_min()函数来验证一下，返回值全是0。
而后两种的优先级范围是1-99，至少在我的系统上是这样，同样是上面的两个函数或得到。
2、因为现在Linux的线程库多是NPTL，而它的实现机制和POSIX的标准还有些不同。如果是用SCHED_FIFO
或者SCHED_RR的调度policy，那么肯定会在线程创建之前设置线程的调度policy，这个是用这个函数实现
的pthread_attr_setschedpolicy()。既然这样，那问题就简单了，只要跟进这个函数看下，就知道它是
怎么作用给内核的了。以下是在Glibc 2.10.1中的源代码：
int
__pthread_attr_setschedpolicy (attr, policy)
pthread_attr_t *attr;
int policy;
{
struct pthread_attr *iattr;
assert (sizeof (*attr) >= sizeof (struct pthread_attr));
iattr = (struct pthread_attr *) attr;
/* Catch invalid values. */
if (policy != SCHED_OTHER && policy != SCHED_FIFO && policy != SCHED_RR)
return EINVAL;
/* Store the new values. */
iattr->schedpolicy = policy;
/* Remember we set the value. */
iattr->flags |= ATTR_FLAG_POLICY_SET;
return 0;
}
这个函数没必要讲了，内容很简单，注释也很详细。关键的一点就是将新的调度policy保存到thread的属
性结构体中。接下来再看一下这个属性结构体是用来干嘛的，如下：
struct pthread_attr
{
/* Scheduler parameters and priority. */
struct sched_param schedparam;
int schedpolicy;
/* Various flags like detachstate, scope, etc. */
int flags;
/* Size of guard area. */
size_t guardsize;
/* Stack handling. */
void *stackaddr;
size_t stacksize;
/* Affinity map. */
cpu_set_t *cpuset;
size_t cpusetsize;
};
注意这个结构体的第一个field，
/* The official definition. */
struct sched_param
{
int __sched_priority;
};
它是一个调度参数，也就是说在调度器调度的时候，它会check这个参数的值，然后来决定怎么调度。
接下来的分析，就是你在内核中看到了的。简单的总结一下这套流程就是：
进程创建的时候，以线程的形态来执行，进程只是负责申请、分配资源
如果线程是实时调度的，那就会通过glibc里提供的POSIX接口来动态设置自己的policy，然后作用于调度参数上
调度器在调度的时候，又会参照调度参数中的值来决定该怎么做。
PS:匆匆写的东西，未必正确。有问题可以跟帖拍砖
您可能感兴趣的文章:
本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术，将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外，均为转载、整理或搜集自网络。欢迎任何形式的转载，转载请注明出处。
本站(WWW.)站内文章除注明原创外，均为转载、整理或搜集自网络。欢迎任何形式的转载，转载请注明出处。