全部博文（28）
分类： LINUX
2010-02-07 01:29:51
The previous chapter discussed processes, the operating system abstraction of active program code. This chapter discusses the process scheduler, the chunk of code that puts those processes to work.
前面的章节讨论了进程，那是运行程序的操作系统的抽象。本章讨论进程调度，这使进程有效工作的一组代码。
The process scheduler is the component of the kernel that selects which process to run next. The process scheduler (or simply the scheduler, to which it is often shortened) can be viewed as the subsystem of the kernel that divides the finite resource of processor time between the runnable processes on a system. The scheduler is the basis of a multitasking operating system such as Linux. By deciding what process can run, the scheduler is responsible for best utilizing the system and giving the impression that multiple processes are executing simultaneously.
进程调度程序是内核的组成部分，它选择下一个要运行的进程。进程调度程序（或者简称调度程序，有时这样简称）可以被视为内核的子系统，它能在一个系统的可运行态进程之间分配有限的处理器时间资源。进程调度程序是诸如Linux这样的操作系统的基础。决定哪个进程运行，进程调度负责将操作系统最优化，让多进程有并发执行的效果。
The idea behind the scheduler is simple. To best utilize processor time, assuming there are runnable processes, a process should always be running. If there are more runnable processes than processors in a system, some processes will not be running at a given moment. These processes are waiting to run. Deciding what process runs next, given a set of runnable processes, is a fundamental decision that the scheduler must make.
调度程序的目的很简单。最大限度的优化处理器时间原则是：如果有运行态的程序，进程将一直可运行。如果在系统里很多运行态的进程超过处理器个数，有些进程在一个给定的片刻将不会运行。这些进程将等待运行。在给定的一组运行态的进程中决定哪一个进程执行，这是调度程序所需完成的基本工作。
A multitasking operating system is one that can simultaneously interleave execution of more than one process. On single processor machines, this gives the illusion of multiple processes running concurrently. On multiprocessor machines, this also enables processes to actually run concurrently, in parallel, on different processors. On either machine, it also enables many processes to run in the background, not actually executing until work is available. These tasks, although in memory, are not runnable. Instead, such processes utilize the kernel to block until some event (keyboard input, network data, some time in the future, and so on) occurs. Consequently, a modern Linux system may have 100 processes in memory but only one in a runnable state.
多任务操作系统是一个能够并发地交互地执行多进程的操作系统。在单处理机上，能产生多进程同时运行的幻觉。在多处理机上，能让多进程让程序在不同的处理器上同时的，平行的执行。在任何一台机器上，也能让多进程运行在后台，直到它实际招待的时候。这些任务，虽然在内存中执行，但都处理非运行态。相反，这些进程利用内核阻塞自己，直到某一事件发生（键盘输入，网络数据，过一段时间等）。因此，在现代的操系统中可能有100条进程在内存中，但是仅仅只有一条处于可运行状态。
Multitasking operating systems come in two flavors: cooperative multitasking and preemptive multitasking. Linux, like all Unix variants and most modern operating systems, provides preemptive multitasking. In preemptive multitasking, the scheduler decides when a process is to cease running and a new process is to resume running. The act of involuntarily suspending a running process is called preemption. The time a process runs before it is preempted is predetermined, and it is called the timeslice of the process. The timeslice, in effect, gives each runnable process a slice of the processor's time. Managing the timeslice enables the scheduler to make global scheduling decisions for the system. It also prevents any one process from monopolizing the processor. As we shall see, this timeslice is dynamically calculated in the Linux process scheduler to provide some interesting benefits.
多任务操作系统可化分为两类：非抢占式多任务和抢占式多任务。所有像Unix的变种系统和很多现代操作系统一样，Linux提供抢占式的多任务模式。在抢占式多任务模式中，调度程序决定什么时候进程中止，新的进程能够开始获得运行。 这个被强制挂起的动作就叫做抢占。进程在被抢占前，运行的时间是预知的，这个时间叫做时间片。事实上，时间片是为每个运行态的进程分配处理器的时间的一片。管理时间片，使能调度程序为系统做好全局调度决定。时间片也能阻止任何一个进程垄断处理器。正如我们看到的，在Linux进程调度程序中时间片是动态计算出来的，这样带来很多好处。
Conversely, in cooperative multitasking, a process does not stop running until it voluntary decides to do so. The act of a process voluntarily suspending itself is called yielding. Processes are supposed to yield often, but the operating system cannot enforce this. The shortcomings of this approach are numerous: The scheduler cannot make global decisions regarding how long processes run, processes can monopolize the processor for longer than the user desires, and a hung process that never yields can potentially bring down the entire system. Thankfully, most operating systems designed in the last decade have provided preemptive multitasking, without Mac OS 9 and earlier being the most notable (and embarrassing) exceptions. Of course, Unix has been preemptively multitasked since the beginning.
相反的，在非抢占式任务中，进程是不会退出，直到它自愿放弃执行。进程自愿挂起自己的操作叫做让步。进程通常被认为让步，但是操作系统不会强制去做这些。让步有很多缺点：调度程序不会做出决定让进程运行多少时间、进程会独占处理器时间比用户期望的要长、大量的进程不会做出让步可能会让整个系统性能下降。幸运的是，在近十年很多操作系统被设计成抢占式多任务模式，除了Mac OS 9和早期的版本。当然，Unix从出生时都被设计成为抢占式多任务模式。
During the 2.5 kernel development series, the Linux kernel received a scheduler overhaul. A new scheduler, commonly called the O(1) scheduler because of its algorithmic behavior, solved the shortcomings of the previous Linux scheduler and introduced powerful new features and performance characteristics. This chapter discusses the fundamentals of scheduler design and how they apply to the new O(1) scheduler and its goals, design, implementation, algorithms, and related system calls.
在2.5内核的开发版本中，Linux内核做了很大的调整。开始采用了一种叫0（1）调度程序的新调度程序—它是由于其算法而得名。解决了早期Linux调度程序，引入了很多强大的新特征和性能特性。本章讨论调度程序设计的原理和怎样应用0(1)调度程序和它的目标设计、实现、运算和相关的系统调用。
O(1) is an example of big-o notation. In short, it means the scheduler can do its thing in constant time, regardless of the size of the input. A full explanation of big-o notation is in , "Algorithmic Complexity," for the curious.
[1] O(1) 用的是大O表示法。简而言之，它意味着调度程序在一定的时间内做自己的事情，不管输入有多大。附录中的大O表示法是为好奇的人准备的。
