试译 Kernel-Scheduled Entities for FreeBSD

DarkBlueSea

Kernel-Scheduled Entities for FreeBSD
FreeBSD中的“内核调度实体”
Jason Evans

jasone@freebsd.org

January 1, 2003

译者： DarkBlueSea

感谢风丝片雨斑竹和gvim的鼓励与修正

Abstract:
摘要
FreeBSD has historically had less than ideal support for multi-threaded application programming. At present, there are two threading libraries available. libc_r is entirely invisible to the kernel, and multiplexes threads within a single process. The linuxthreads port, which creates a separate process for each thread via rfork(), plus one thread to handle thread synchronization, relies on the kernel scheduler to multiplex "threads" onto the available processors.
从前FreeBSD一直缺乏对多线程编程的良好支持。目前，有两个线程库可以使用。libc_r对于内核来说完全不可见，它就在单个进程内部完成多个线程的复用。devel/linuxthreads port是内核线程库，它使用rfork()为每个线程创建一个独立的进程，再额外创建一个线程，来处理线程间的同步，依靠内核调度器在所有可供使用的处理器上复用多个线程。

Both approaches have scaling problems. libc_r does not take advantage of multiple processors and cannot avoid blocking when doing I/O on "fast" devices. The linuxthreads port requires one process per thread, and thus puts strain on the kernel scheduler, as well as requiring significant kernel resources. In addition, thread switching can only be as fast as the kernel's process switching.
两种方法都存在扩展性的问题。libc_r在多处理器上没有优势，并且进行“快速设备”I/O操作无法避免阻塞。devel/linuxthreads port 需要为每个线程创建进程，因此，加重了内核调度器的负担，同时还需要大量的内核资源，另外，线程切换只能达到内核进程切换的速度。

This paper summarizes various methods of implementing threads for application programming, then goes on to describe a new threading architecture for FreeBSD, based on what are called kernel-scheduled entities, or scheduler activations.
这篇文章概括了多种为应用程序编程实现线程的方法，接着描述一个新的FreeBSD线程结构，基于内核调度实体(KSE),或者叫“激活调度”。

1 Background 背景
FreeBSD has been slow to implement application threading facilities, perhaps because threading is difficult to implement correctly, and the FreeBSD Project's general reluctance to build substandard solutions to problems. Instead, two technologies originally developed by others have been integrated.
FreeBSD在实现应用程序线程工具方面的进展很慢，也许这是因为线程很难被正确的实现，而且FreeBSD项目一般不原意用低于标准的方案解决问题，而用一种新的技术来取而待之，这种技术整合了原来的两种技术。

libc_r is based on Chris Provenzano's userland pthreads implementation, and was significantly re-worked by John Birrell and integrated into the FreeBSD source tree. Since then, numerous other people have improved and expanded libc_r's capabilities. At this time, libc_r is a high-quality userland implementation of POSIX threads.
libc_r 基于 Chris Provenzano 所开发的用户空间pthreads，经过 John Birrell 的重要修正后，加入了FreeBSD的源代码树中。之后，许多人提高和扩展了libc_r的性能。现在，它已经是POSIX threads的一个高品质的用户态实现

The linuxthreads port is based on Xavier Leroy's LinuxThreads, which is now an integral part of GNU libc. The linuxthreads port is completely compatible with LinuxThreads as it runs on Linux.
linuxthreads port基于 Xavier Leroy 所开发的LinuxThreads，LinuxThreads现在已经成为了GNU libc的一个重要组成部分，linuxthreads port和linux下运行的LinuxThreads 完全兼容

Both of these libraries have scalability and performance problems for certain types of threaded programs.
对于某些类型的线程化的程序而言，这两个库都存在扩展性和性能方面的问题。

2 Threading Architectures 线程结构
Following is a short description of several threading architectures, along with a representative implementation for each of the more common ones. In all cases, threading is preemptive.
下面是对几种线程结构的简短的描述，每一个类型都选择一个典型的实现，在所有的情况下，线程是可抢占的。

2.1 Userland (ala FreeBSD's libc_r) 用户空间
Userland threads are implemented entirely in an application program, with no explicit support from the kernel. In most cases, a threading library is linked in to the application, though it is also possible to hand code user threading within an application.
用户级线程完全是在应用程序内部实现的，并不需要内核提供显式的支持。在大多数情况下都是直接把一个线程库链接到应用程序中的，当然，你也可以在应用程序中自己动手编写用户级线程的代码。

In order for userland threading to work, two main issues have to be resolved:
为了让用户态线程可以使用，两个重要的问题必须解决

Preemptive scheduling: 抢占式调度

    Threads must be periodically preempted so that all runnable threads of sufficient priority get to run. This is done by a combination of a timer signal (SIGALARM for libc_r), which allows the userland threads scheduler (UTS) to run, and setjmp()/ longjmp() calls to switch between threads.
    线程必须进行周期性的被抢占，来保证所有有足够优先级的可运行线程可以运行，这是通过把一个定时器信号（libc_r的SIGALARM）和setjmp()/logjmp()调用结合起来完成的，其中，定时器信号使得用户级线程调度器（UTS）可以运行，而setjmp()/longjmp()调用则用于在线程之间进行切换。

Process blocking: 进程阻塞

    Normally, when a process makes a system call that cannot be completed immediately, the process blocks and another process is scheduled in order to make full use of the processor. However, a threaded program may have multiple runnable threads, so blocking in a system call should be avoided. This is accomplished by converting potentially blocking system calls to non-blocking. This works well in all cases except for operations on so-called fast devices such as local filesystems, where it is not possible to convert to a non-blocking system call. libc_r handles non-blocking and incomplete system calls by converting file descriptors to non-blocking, issuing I/O requests, then adding file descriptors to a central poll()-based event loop.
通常，当一个进程进行系统调用不能立即完成时，为了保证处理器的高利用率，这个进程就会被阻塞，其他的进程会被调度执行。但是，一个线程化的程序可能含有多个可运行的线程，所以在系统调用过程中，应该避免阻塞。这个问题通过将可能阻塞的系统调用转换为非阻塞来实现。在绝大多数情况下，这样做是没问题的，但是如果要操作所谓的“高速设备”比如本地文件系统时，在这里不可能将系统调用转换为非阻塞。libc_r处理非阻塞的和未完成的系统调用的方法是先把文件描述符转换成非阻塞，然后发出I/O请求，最后再把文件描述符加到一个核心的基于poll()的事件循环中。(The poll() system call examines a set of file descriptors to see if some of them are ready for I/O.).

Userland threads have the advantage of being very fast in the simple case, though the complexities of call conversion eats into this performance advantage for applications that make many system calls.
用户级线程的优势是在一般情况下速度非常快，不过在应用程序需要许多系统调用时，调用转换的复杂性抵消了这种性能上的优势。

As libc_r currently exists, there are several problems:
当前的libc_r,有几个问题

   1. The central poll() loop does not scale well to large numbers of threads. This could probably be solved by converting to the kqueue() interface [Lemon].
1.核心的poll()循环在线程数目很大的情况下的扩展性不是很好。不过这或许可以通过改用kqueue()接口来解决。

2. The entire process blocks on I/O to fast devices. This problem could probably be solved by integrating asynchronous I/O into libc_r, which would first require stabilizing the AIO implementation, then require switching from a poll()-based event loop to a kqueue()-based event loop in order to be able to integrate I/O completion notifications into the same loop.
在“快速设备”I/O操作时，整个进程被阻塞，这个问题可能可以通过在libc_r 中整合异步I/O来解决，解决方案首先要求稳定AIO实现，接着从基于poll()调用的事件循环交换到基于kqueue()调用的事件循环中，以便将I/O完成通告整合到同一个循环中。

3.Since all threads are multiplexed onto a single process, libc_r cannot take advantage of multiple CPUs in an SMP system. There is no reasonable retrofit to libc_r which solves this scalability problem.
因为所有线程并发的使用一个处理器，libc_r在对称多处理器系统中没有优势，没有合适的修改可以使libc_r 解决这个可扩展性问题

Figure 1: Userland threading model
图1：用户空间线程模型


2.2 Process-based (ala Linux's LinuxThreads) 基于进程的线程
Process-based threading is confusingly referred to as kernel threading much of the time. True kernel threads are threads that run within the kernel in order to run various portions of the kernel in parallel. Process-based threads are threads that are based on some number of processes that share their address space, and are scheduled as normal processes by the kernel. LinuxThreads implements process-based threading.
多数情况下，基于进程的线程作为内核线程让人感到很混乱，真正的内核线程是在运行在内核中的线程，让线程并行的运行在内核的不同部分。基于进程的线程是一些共享地址空间的进程，这些进程被内核作为普通进程来调度，LinuxThreads就是基于进程的线程实现。

New processes are created such that they share the address space of the existing process(es), as shown in Figure 2. For Linux, this is done via the clone() system call, whereas for FreeBSD it is done via a special form of the rfork() system call.
新进程创建时，它们共享一个已经存在的进程的地址空间，在表2中可以看出。对于Linux，这些进程通过clone()系统调用完成，但在FreeBSD下，通过rfork()完成。

As soon as a second thread is created via pthread_create(), LinuxThreads creates an additional process that is used exclusively for synchronization among processes. This means that for a program with n threads, there are n + 1 processes (if at some point in time n > 1).
当第二个进程创建后，LinuxThreads 会通过pthread_create()调用额外创建一个进程，专门用于同步其他进程，那就是说，对于一个有n个线程的程序，一共有你n+1个进程（如果当前n>1）

LinuxThreads is elegant in that it is simple. However, it has at least the following POSIX compliance issues that cannot be easily addressed:
LinuxThreads 在普通情况下很优雅，但是至少在下面的与POSIX一致性上，不是很容易处理

Each thread runs in a separate process. Each process has a unique process ID (pid), but POSIX requires all threads to appear to have the same pid. Fixing this would require significant modifications to the kernel's data structures.
每一个线程运行在一个独立的进程里，每一个进程有一个唯一的进程ID但是POSIX要求，所有的线程中要出现同一个pid，修复这个问题需要大量的修改内核的数据结构。

The thread priority semantics specified by POSIX cannot be implemented, because each thread is actually a process, which makes thread contention at the application level impossible. All thread contention is by definition at the system level. This has the additional disadvantage that multi-threaded applications compete unfairly with single-threaded applications, which makes running a mixture of applications difficult on a single machine.
POSIX指定的线程的优先级的语义不能实现，因为每一个线程实际上是一个进程，这使得线程不可能在应用程序级别上相互竞争，所有线程的竞争都被定义在系统级别上。这就带来了额外的缺点，多线程程序和单线程程序的竞争明显的不公平，这会使一台机器上运行多种混合程序有困难。

Process-based threading also has some inherent performance and scalability issues that cannot be overcome:
基于进程的线程同样有一些先天的性能和可扩展优势无人能及

Switching between threads is a very expensive operation. It requires switching to kernel mode, switching the old thread (process) out, and then running the new thread (process). There is no solution to this problem except to optimize process switching, which defies optimization beyond a certain point. This problem is aggravated by cache locality considerations.
线程间的切换是代价非常高的操作，需要换入内核态，换下原来的线程接着运行新的线程。现在没办法解决这个问题，只能通过优化进程切换来缓解，挑战最优化，以超过一个点。这个问题由于缓存击中率的因素更加尖锐化。

Each thread (process) requires all the kernel resources typically associated with a process. This includes a kernel stack, which means that applications with many threads require large amounts of kernel resources.
每一个线程（进程）需要所有的与进程相关联的内核资源。包括内核堆栈，这意味着多线程程序需要大量的内核资源。

[ 本帖最后由 DarkBlueSea 于 2006-4-10 13:08 编辑 ]

DarkBlueSea

Figure 2: Process-based threading model
基于进程的线程模型



2.3 Multi-level (ala Solaris's LWPs) 多级线程
Multi-level threading is a hybrid of user-level and process-based threading. Threads are multiplexed onto a pool of processes. The size of the process pool is normally determined automatically by heuristics internal to the threading library that take into account issues such as the number of processors, number of threads, and processor binding of threads.
多级线程是用户空间和基于进程线程的结合。线程在一个进程池上多路复用。进程池的大小通常由线程库内部自动决定，考虑的因素有处理器数目，线程数目和处理器捆绑线程数目。

The idea of multi-level threading is to achieve the performance of userland threading and the SMP scalability of process-based threading. Ideally, most thread scheduling is done by a UTS to avoid the context switch overhead of kernel calls, but multiple threads can run concurrently by running on more than one process at the same time.
多级线程的设计目标是，即达到了用户线程的性能，又能实现类似基于进程线程在SMP下的可扩展性，理论上，多数线程调度用UTS完成来避免上下文切换进行系统调用的开支，但是多个线程可以并行的运行在多个处理器上。

In practice, multi-level threading's main shortcoming is its complexity. Ideally, the advantages of userland and process-based threading are combined, without any of the disadvantages, but in practice, some of the disadvantages tend to slip in. The overhead of the multi-level scheduling compounds this.
事实上，多级线程的主要缺点就是它的复杂性，理论上，它同时拥有用户空间线程和基于进程线程的优点，没有任何缺点，但在实际中，一些缺点被忽略了，多级线程调度的开销就是其中之一。

Multi-level threading does not require light-weight processes (LWPs) in order to work, but Solaris uses LWPs to address the POSIX compliance issues mentioned above for purely process-based threading. Also, in theory, LWPs are light-weight, though Solaris's LWPs no longer generally meet this criterion. That is, by the time Sun got the kinks worked out, LWPs were no longer light-weight.
多级线程不需要轻量级进程（LWPs）来支持其运行，但是Solaris使用LWPs来实现POSIX中的提到的纯基于进程的线程。同样，在理论上，LWPs是轻量级的，虽然Solaris的LWPs不再完全符合这个尺度。就是说，Sun在让LWPs向POSIX的标准靠近时遇到了障碍，LWPs也不再是轻量级的了。

Figure 3: Light-weight process-based threading model
轻量级基于进程的线程模型


2.Scheduler Activations 激活调度

This is a very brief overview of scheduler activations (SAs) as presented in [Anderson], and is meant only as a basis for the more complete treatment of kernel-scheduled entities (KSEs) for FreeBSD later in this paper. There are many details left out in this section, which are treated in detail in the original paper.
激活调度的的简短概述，这里只是基本介绍FreeBSD中的KSE的内容。许多细节都会被忽略，下一节将会详细说明。

The SAs approach, like multi-level threading, strives to merge the advantages of userland and process-based threading while avoiding the disadvantages of both approaches. SAs differ from multi-level scheduling in that additional kernel facilities are added in order to provide the UTS with exactly the information and support it needs in order to control scheduling. Simply put, SAs allow the kernel and the UTS to do their jobs without any guess work as to what the other is doing.
SAs方法，类似于多级线程，尽力融合用户级线程和基于进程线程的优点，同时避免二者的缺点。SAs不同于多级调度通过增加额外的内核工具提供UTS需要的准确的信息和支持来控制调度。简单的说，SAs允许内核和UTS做自己的事，而不用关心对方在干什么。

A process that takes advantage of SAs has a significantly different flow of control than a normal process, from the perspective of the kernel. A normal process has a number of data structures associated with it in the kernel, including a stack and process control block (PCB). When a process is switched out, its machine state is saved in the PCB. When the process is run again, the machine state is restored from the PCB and the process continues running, whether in kernel or user mode.
一个进程用SAs得到的好处是，在内核透视中，有一个和普通进程显著不同的控制流程。在内核中，普通进程有若干数据结构与之关联，包括一个堆栈，进程控制块（PCB）。当一个进程被换出时，它的执行状态保存在PCB中，当进程继续运行时，执行状态从PCB中恢复，进程继续执行，无论内核进程和用户进程都是如此。

A process that is using SAs does not have a kernel stack or PCB. Instead, every time a process is run, a SA is created that contains a kernel stack and thread control block (TCB), and the process runs in the context of the SA. When the SA is preempted or blocked, machine state is stored in the SA's TCB, and the kernel stack is optionally used for completion of a pending system call. See Figure 4.
使用SAs的进程没有系统堆栈和PCB，取而代之的是，每次一个进程要运行时系统创建一个SA，SA中包含一个系统堆栈和线程控制块（TCB），进程运行在SA上下文中，当这个SA被抢占或是阻塞，机器状态被保存在SA的TCB中，系统堆栈可以用来完成一个未完成的系统调用。见图4

It is possible to run more than one SA for the same process concurrently on multiple processors. However, the UTS needs to know at all times exactly what processors it is running on, so that it can make informed scheduling decisions. As part of the solution to this problem, every time a SA is started, it initially starts executing in the UTS. Additionally, the kernel makes upcalls to the process to notify it of important events that may affect thread scheduling decisions. The following upcalls are necessary:
一个进程可能同时运行多个SA在多个处理器上，但是，UTS需要每时每刻准确的知道处理器上是谁在运行，以便做出正确的调度决定。作为这个问题解决方案的一部分，每次一个SA启动，它首先在UTS中启动执行。另外，内核会进行回调来通知进程去修改一些会影响线程调度决定的重要事件，下面的回调是必须的：

sa_new(cpu_id):
    Execute a thread on the processor with ID cpu_id.

sa_preempt(sa_id):
    A thread was preempted, with SA ID sa_id.

sa_block(sa_id, pcb):
    A thread blocked in the kernel, with SA ID sa_id and machine state pcb.

sa_unblock(sa_id, pcb):
    A thread that was blocked in the kernel has completed, with SA ID sa_id and machine state pcb.

Also, the following system calls are necessary:

sa_alloc_cpus(ncpus):
    Allocate ncpus additional CPUs, if possible.

sa_dealloc_cpu():
    Remove a CPU (reduce concurrency by one).

Figure 4: Scheduler activations
激活调度



3 Kernel-scheduled entities 内核调度实体

Kernel-scheduled entities (KSEs) are similar in concept to scheduler activations, but support for threads with system-level scheduling contention is added. Figure 5 shows how KSEs and userland interact. Scheduling contention is controlled via KSE groups (KSEGs). A process has one or more KSEGs associated with it. Each KSEG has a concurrency level associated with it, which controls the maximum number of concurrent KSEs that can be run for that KSEG. Each KSEG is a separate entity from a timesharing perspective.
内核调度实体（KSEs）和激活调度是类似的概念。但是加入了线程进行系统级调度的支持。图5表示了KSEs如何和用户空间交互。调度竞争通过KSE组（KSEGs）来控制。一个进程拥有一个或多个的KSEGs，每一个KSEG有一个并发级别，这个级别控制在这个KSEG中可以并发执行的最大KSEs的数量。在一个分时的透视中，每一个KSEG是一个独立的实体

Figure 5: Kernel-scheduled entities


A process starts out with one KSEG that has a concurrency level of one. As new threads are created, the concurrency level of that KSEG can be adjusted, up to the maximum number of CPUs available for execution of the process. If a thread with system-level scheduling contention is desired, a new KSEG with a concurrency level of one can be created for that thread.
一个进程启动时有一个并发级别为一的KSEG，随着新线程的创建，它的并发级别也会做相应的调整，直到达到该进程的最大可用CPU数。如果进程希望创建一个系统级调度的线程，会为这个线程创建一个新的并行级别为一的KSEG。

Since each KSEG is a separate entity from a timesharing perspective, allowing a process to create an arbitrary number of KSEGs would give the process an unfair scheduling advantage. Therefore, instead of enforcing process limits, KSEG limits are enforced. In the common case of single-threaded applications, there is a one to one correspondence between the two methods of enforcing resource limits, but in the case of multi-threaded applications, this prevents a single user from being able to gain a larger portion of the CPU time than would be possible with multiple single-threaded applications.
因为对于分时的透视，每一个KSEG是一个单独的实体，允许进程创建任意数目的KSEGs将会使进程的调度不公平，因此，系统没有限制进程，而是限制了KSEG。在通常的单线程程序中，两个方法在限制资源的权限内进行一对一的通信，但在多线程的程序中，这样防止一个用户获得比多个单线程程序更多的CPU时间。

The KSE architecture makes a distinction between a KSE and a thread. KSEs are used in the kernel in the scheduler queues, and as a general handle, much the same way as a process is used in current BSD kernels. Given a pointer to a KSE, it is possible to access its associated KSEG, proc, and it's current thread. A Thread contains the state of a suspended thread of execution. When a running KSE is blocked, the execution state is saved in the Thread so that when it is possible to continue execution, the thread can be re-attached to a KSE and continued. When a KSE is preempted, the execution state is saved in a Thread so that any userland state can be handed to the UTS.
KSE的结构使KSE和线程间存在不同，KSEs在内核调度队列中使用，作为一般处理，和现在BSD中使用的进程相同。给一个指向KSE的指针，KSEG，proc和当前线程通过这个指针来引用KSE。一个线程包含停止时的执行状态。当一个运行的KSE被阻塞时，执行状态将会保存在线程中，以便于线程在以后运行时使用，线程可以被重新联接一个KSE后继续执行。当一个KSE被抢先时，执行状态也会被保存，以便任意的用户级状态可以被UTS处理。

[ 本帖最后由 DarkBlueSea 于 2006-4-10 13:09 编辑 ]

DarkBlueSea

KSEs are only evident within the kernel. The interface with userland only deals with processes, KSEGs, and Threads. KSEs themselves are irrelevant to userland because they serve essentially as an anonymous handle that binds the various kernel structures together.
KSEs运行在内核中，由进程来处理它的用户空间接口，KSEGs，线程，KSEs和用户空间是不相干的，因为他们实质上被匿名的和不同的内核结构捆绑在一起，向用户空间提供服务。

3.Operation without upcalls 无回调操作

Unless upcalls are explicitly activated by a program, execution is almost identical to the traditional BSD process model. The proc structure is still broken into four components, and the KSE is used as the handle to the process most places in the kernel, but otherwise, little is changed. Figure 6 shows the linkage between the four data structures that comprise the single-threaded component. The dashed lines denote linkage that only exists if upcalls are not activated.
除非程序明确的激活回调，否则进程的执行还是按照BSD传统模型进行。Proc结构还是分为四部分，KSE在内核的大多数地方作为进程的把手，但因此，有一点点改变。图6显示了单线程程序四个数据结构之间的关联，虚线部分只有在回调没有被激活时才存在。

Figure 6: KSE data structure linkage for a single-threaded process



3.Operation with upcalls 有回调操作

At the time upcalls are activated via a system call, program flow changes radically. Non-blocking system calls will behave normally, but blocking system calls, preemption, and running will cause the program to receive upcalls from the kernel. Figure 7 shows the data structure linkage for a process running on a 4 CPU machine that has real-time, system scope, and timeshared threads. The KSEs that have an associated Thread are currently running.
在任何系统调用中，一旦回调被激活，程序流程会发生根本的变化，非阻塞系统调用会很常见，但是可阻塞系统调用有优先权，并且运行时程序会收到内核发出的回调。图7显示了一个运行在四个CPU上的进程，其各个数据结构之间的关联，这个进程有实时，系统级，分时的三种线程。和KSE关联的线程正在运行。

Figure 7: KSE data structure linkage for a multi-threaded process on a 4 CPU machine


3.APIs

KSEs require the ability to make upcalls to userland. This is a very different flow of control than normal process execution uses. Normal processes don't know when they are preempted or resumed; execution appears seamless. With KSEs, the process can be notified of every preemption and resumption, which requires upcalls.

Basically, there is only one upcall, with information as to what events caused it available from a pre_agreed mailbox.
KSEs需要有能力对用户态进行回调。这个完全不同于控制进程正常执行所用的的流程。正常的进程不知道被抢先或是被恢复运行，运行几乎是无缝的，有了KSEs，当进程被抢先或是恢复运行时系统会通过回调通知进程。基本上，只有一个回调，带着来自一个预先设定的信箱信息，信息说明在什么事件发生时，线程可用。
The following system calls (or versions thereof) are necessary:

void kse_new(mailbox_addr, flags):
    Start using a new KSE. mailbox_addr points to a structure that contains the necessary data for the kernel to make upcalls. Initially, there is only one KSEG (ID 0), which has a concurrency level of 1. If the flags specify, a new KSEG is created to hold the new KSE.

int kse_yield():
    The KSE returns to the kernel and does not return.

int kse_wakeup(kse_id):
    Trigger an upcall from this KSE if is is currently inactive.

int thread_cancel(thread_id):
    If the thread in question is stopped somewhere an attempt is made to abort the operation. (Similar to signals).

int kse_bind(int kse_id, int cpu_id):
    Bind the KSE with ID kse_id to the CPU with ID cpu_id. This system call returns the CPU ID that the KSE is bound to, or -1 if there is an error (e.g. invalid CPU ID)

Figure 7 shows the basic linkage between processes (proc), KSEGs (kseg), KSEs (kse), and Threads (thread). The diagram corresponds to a four processor machine. Two of the processors are running KSEs on behalf of bound KSEGs, and the other two processors are running KSEs on behalf of a softly-affined KSEG.
图7显示了proc，KSEGs，KSEs和线程之间的关联。那个图显示了一台有四个CPU的机器。两个CPU正在运行绑定KSEG，另两个CPU在运行软亲缘（softly-affined） KSEG.

In addition to the new system calls, the getpriority() and setpriority() system calls need to be extended to handle KSEGs. It may be necessary to do so in a way that is not backward compatible, since at a system level, a KSEG can only be uniquely specified using the process ID and the KSEG ID.
此外，对于新的系统调用，getpriority()和 setpriority()系统调用需要被扩展来处理KSEGs。也许必须这么做，所以从某种程度上不能实现向后兼容，因为在系统级上，KSEG通过进程ID和KSEG Id来保证唯一性。
3.Kernel Scheduler 内核调度

A number of changes to the kernel scheduler are mandatory in order to support KSEs. Chief among these changes are:
内核调度为了支持KSEs进行了许多修改。主要有下面的一些修改

    * KSEs are are placed in the scheduler queues, rather than processes. This enables concurrent execution of KSEs that are associated with the same process.
KSEs被放置在调度队列，取代了进程。这样就允许一个进程的多个KSE可以并发执行。

    * Timesharing calculations are done with KSEGs, rather than processes. This allows multiple KSEGs in one process to compete for CPU time at a system-wide level.
分时计算由KSEGs完成，取代了进程。一个进程中可以有多个KSEGs在系统级上共同竞争CPU时间

    * The state for blocked (incomplete) system calls is stored in Threads. This means that this queue consists of Threads rather than KSEs. In other words, the scheduler deals with KSEs in some places, and Threads in other places.
系统调用的阻塞状态被存储在线程中，阻塞队列由线程组成，而不是KSE换句话说，调度程序在一个地方处理KSE，另一个地方处理线程。

Additionally, soft processor affinity for KSEs is important to performance. KSEs are not generally bound to CPUs, so KSEs that belong to the same KSEG can potentially compete with each other for the same processor; soft processor affinity tends to reduce such competition, in addition to well-known benefits of processor affinity.
另外，软处理器亲缘对KSE的性能非常重要。KSE不能全部被绑定在CPU上，所以KSE所属的KSEG之间可能会竞争同一个处理器，软处理器亲缘倾向于减少这种竞争，除了众所周知的处理器亲缘带来的好处。

3.5 Userland threads scheduler 用户空间调度

The KSE-based UTS is actually simpler than is possible for a userland-only threads implementation, mainly because there is no need to perform call conversion. The following is a simplified representation of the core UTS logic.
实际上，基于KSE的UTS比用户空间的UTS实现要简单，主要的原因是不再需要进行调用转换。下面是一个简单的核心UTS逻辑处理的内容说明
   1. Find the highest priority thread that is mapped to the kseg that this Thread is part of. Optionally heuristically try to improve cache locality by running a thread that may still be partially warm in the processor cache.
在KSEG中找到一个优先级最高的线程，把这个线程放在一个还有部分该线程的缓存仍然的没有被清除的处理器上，通过这种可选的试探性方法提高缓存的击中率。
   2. Set a timer that will indicate the end of the scheduling quantum.
设置一个指示调度时间片结束的计时器
   3. Run the thread.
运行这个线程
Of course, there are a number of ways to enter this code, such as getting a new Thread, running a thread to the end of a quantum, or rescheduling due to another thread blocking. However, the fact remains that the UTS logic is quite simple.
当然，有很多种办法进入这段代码，比如创建一个新线程时，在一个运行线程的调度时间片结束时，或者由于另一个线程的阻塞而重新调度。但是UTS的逻辑仍然很简单

3.5.1 Temporary priority inversion 临时优先级倒置
The UTS always has the information it needs to make fully informed scheduling decisions. However, in the case of priority-based thread scheduling, there are some circumstances that can cause temporary scheduling inversions, where a thread may continue to run to the end of its quantum despite there being a higher priority runnable thread. This can happen when:
UTS总是有它需要的信息来做一个明智的调度决定，但是，就一个基于优先级的线程调度而言，有一些情况可能导致暂时的调度倒置，那种情况下，一个线程也许会在它的时间片结束后继续运行，即使有一个有一个优先级更高的可运行线程，这种情况会在下列情形下发生。

   1. A new thread is created that has a lower priority than its creator, but a higher priority than a thread that is concurrently running on another processor.
一个线程创建了一个比自己优先级低的线程，但是一个有更高优先级的线程正在另一个处理器上运行。

   2. A KSE (running thread A) is preempted by the kernel, and the upcall notification causes preemption of thread B, which is higher priority than thread A, though thread C is also running on another processor and has a lower priority than both A and B. In this case, A will be scheduled and C will continue to run, even though thread B is higher priority than C. Note that there are much more convoluted examples of this same basic idea.
一个KSE（运行线程A）被内核抢先，回调通知一个比A优先级高的B线程取得优先权，虽然线程C比A的优先级更低，它仍然运行在另一个CPU上，在这种情况下，虽然B的优先级比C高，但是被调度的是A而不是C注意还有很类似的多错综复杂的例子

Such temporary inversions are technically violations of the policy that lower priority threads never run in the presence of higher priority threads, but there are two reasons not to do anything about it:
这种暂时的倒置理论上会干扰优先级调度策略，但有两个原因不用去管它

   1. Solutions to this problem require additional system calls in which the UTS explicitly asks the kernel to preempt KSEs. This is expensive.
解决这个问题，UTS为了抢先KSE，需要额外的系统调用去查询内核得到准确的KSE优先级。这样的开销很大。
   2. Temporary inversions are logically equivalent to the race condition where the UTS determines that a thread should be preempted in favor of scheduling another thread, while the thread races to complete its quantum. It is not important whether the UTS or the thread wins the race; allowing the lower priority thread to complete its quantum without competition from the UTS simply allows the thread to always win.
暂时倒置逻辑上等同与竞争情形，UTS决定一个线程应该被抢先，调度另一个线程更有利，同时线程与UTS竞争完成它的时间片。最终获胜的是UTS还是线程并不重要，在没有UTS竞争的情况下允许低优先级的线程完成它的时间片的简单性使线程总是会获胜。

3.6 Initialization and upcalls 初始化和回调
The code that is necessary to start up KSEs in a userland program looks something like:

void
foo(void)
{
        struct kse_mailbox       km;

        kse_init(&km);
        /* Handle upcall and longjmp() to UTS. */
}

Each upcall appears to be a return from kse_init(). The stack on which kse_init() is called must never be unwound, since the kernel fakes up a context at the point where kse_init() is called for each upcall. The argument to kse_init() points to a data structure that contains enough information for the kernel to determine where to write events. Due to the asynchronous completion of blocked Threads, it is possible for a single upcall to report a large number of thread_unblock() events, the number of which is only (potentially) bounded by the resource limit settings for the process.
每个回调作为kse_init()产生一个返回值。调用kse_init()的堆栈永远不能被释放，因为在调用kse_init()的地方，内核为每一个回调伪造了一个上下文。kes_init()的参数指向一个数据结构，这个数据结构包含的信息足够内核决定要把事件写在哪里。由于线程阻塞是异步完成的，一个回调可能会报告大量的 thread_unblock()事件，事件的数量由进程的资源限制设置决定。

Since thread_unblock() events include the userland Thread execution state, the amount of space needed to report all events during an upcall can vary wildly; static event buffers are inadequate for such a dynamic problem. Therefore, km contains a pointer to a chain of objects with embedded TCBs, and the kernel stores the TCBs from thread_preempt() and thread_unblock() events in the chain elements. Figure 8 shows the basics of how struct kse_mailbox is laid out.
因为thread_unblock()事件包含用户空间的线程执行状态，在一次回调中，报告所有事件所用的空间可能很大，静态事件缓存不能满足这样一个动态问题。因此km包含指向一链内嵌TCB的对象的指针，内核把TCB保存在thread_preempt()和thread_unblock()事件形成的对象链元素中。图8 简单的显示了kse_mailbox结构是如何放置的。

Figure 8: TCB chaining for upcall event storage

[ 本帖最后由 DarkBlueSea 于 2006-4-10 13:10 编辑 ]

DarkBlueSea

3.6.1 Per-upcall event ordering 回调前的事件次序

The techniques described in the previous section for storing events separate the event types that pass TCBs from those that don't. This means that event ordering is not implicit, and would require extra work to preserve. However, it turns out that in most cases, order doesn't matter, and in the cases that it does matter, the UTS can always determine order.
前面的章节描述了存储事件，区分事件类型的技术忽略了TCB来自那些禁止事项。这意味着事件的顺序不是固定的，可能需要额外的工作去保护。但是在大多数情况下，顺序没关系，即使在顺序有关系的情况下，UTS总能决定顺序

As an example, suppose thread_block() and thread_unblock() events occur for the same Thread ID in the same upcall. In one interpretation, where the thread_block() event occurred first, the UTS last knew the corresponding thread to be running, so the two events simply mean that the thread can be continued. In the other interpretation, where the thread_unblock() event occurred first, the Thread ID has been recycled. However, this isn't possible, since there must have been an intervening thread_new() event, which couldn't have happened until after the Thread unblocked.
举个例子，假设一个线程在一次回调是thread_block()和thread_unblock()事件都发生了。一种情况，如果thread_block()先发生，UTS最后知道通信的线程在运行，所以两个事件表示该线程可以继续执行。另一种情况，如果thread_unblock事件先发生，线程的ID可以被重新利用，但是，这不可能，因为它一定是一个在thread_new()事件之间，在一个线程被解锁之前是不可能发生的。

3.7 Upcall parallelism 回调对应
This section is not yet adequately fleshed out. Issues to consider:
这部分还有没适当的充实，关键要考虑
How do upcalls from multiple processors keep from stomping on each other? For example, if we have only one chain of TCBs, how does it get safely used?
怎么才能避免回调在多个处理器上跳来跳去，比如，如果只有一链TCB，怎么能让它被安全的使用。
What if the UTS doesn't process the TCBs before another upcall happens? Do we run the risk of overflowing the TCB chain?
如果在新的回调发生时，UTS不能处理TCB怎么办，要运行这个存在溢出危险的TCB链吗
    * How do we handle races between the UTS and the kernel? For example, signals cannot be cleared until delivered to a thread, and the kernel must look at the userland bitmap to see if a signal is still pending.
怎么处理UTS和内核间的竞争呢，比如，在信号传递给线程前不能被清空，那么内核必须检查用户空间的位图，去看是否信号还在传递中。
3.8 Kernel scheduler 内核调度
The kernel scheduler needs a major overhaul in order to support KSEs. Support for the following features is necessary:
内核调度需要进行仔细检查以便支持KSE，下面的特征是必须支持的
    * Soft affinity. The scheduler should try to keep processes running on the same processors if there is the possibility of reaping benefits from increased cache locality.
        软亲缘。调度程序应该尽力保证一个进程在被调度前后运行在同一个CPU        上，这样可以通过增加缓存的击中率提高性能。
    * Hard affinity (binding). Some programs may wish to bind a KSE (pedantically speaking, a KSEG is bound) to a particular processor in order to improve cache locality, or to tighten the bounds on a real-time task. Bound KSEs are run only on one CPU, unless priority inheritance forces it to be run on another CPU in order to avoid deadlock due to priority inversion.
硬亲缘（绑定）。一些程序可能希望把KSE绑定在一个单独的CPU上（准确的说，KSEG）来提高缓存的击中率，或是让实时任务更严密，被绑定的KSE只运行在一个CPU上，除非在优先级倒置时，为了避免死锁，优先级继承迫使它运行在另一个CPU上。

    * Increased parallelism. The current scheduler can only be executed by one processor at a time, which makes it a severe bottleneck, depending on the type of system load.
对应增长。在同一时刻内，调度程序只能运行在一个处理器上，随着系统的负载量增大，这产生了严重的瓶颈。
Part of the solution is to implement per-CPU scheduling queues. Each CPU has an associated queue for softly affined KSEs, as well as a queue for bound KSEs. In addition, there is a global queue for fixed-priority KSEs, such as interrupt threads and real-time KSEs. Fixed-priority KSEs prefer to run on the same CPU as the last time they were run, but scheduling issues keep more complex affinity algorithms from being beneficial for this class of KSEs. See Figure 9 for a simplistic representation of the various scheduling queues. The diagram ignores some details such as split queues for various priorities.
这个问题的解决方案是实现单CPU调度队列。每个CPU有一个软亲缘KSE队列和一个绑定KSE队列。此外，还有一个为固定优先级KSE设的全局队列。比如中断处理线程和实时KSE。确定优先级的KSE更希望运行在他们上次运行的CPU上，但是调度算法有更多对这类KSE有益的负杂亲缘算法。图9显示了一个十分简单的各种调度队列的代表。图忽略了某些细节，比如把队列分成不同优先级

Each CPU schedules from its own queues, and resorts to stealing runnable softly affined KSEs from other CPUs if there are no runnable KSEs. Every so often (exact number to be determined by benchmarking, but a likely number is 5 seconds), CPU loads are calculated, and if the loads are too disparate, the under-loaded CPU(s) steal additional KSEs from the overloaded CPU(s) in an attempt to balance the load. Instantaneous per-CPU load is defined as the number of runnable timesharing KSEs in a CPU's queues. Instantaneous system load is the sum of the instantaneous per-CPU loads. Note that normal (non-balancing) KSE stealing is adequate to keep the system busy if there is enough work to do, but that without periodic load balancing, time sharing becomes unfair if there aren't approximately equal CPU loads.
每个CPU在自己的队列中进行调度，如果没有可运行的KSE，则从其他CPU那里取一些有软亲缘的KSE，并且重新排序。每过一段时间（确切得数子通过测试决定，但是可能的是5秒）会计算CPU负载，如果CPU之间的负载差别很大低负载的CPU从高负载CPU的调度队列里取一些KSE加入自己的队列，以达到负载平衡。瞬间单CPU负载定义为在当前CPU的队列里，可运行的分时KSE的数量。瞬间系统负载是瞬间单CPU负载的和。注意，正常的KSE获取是适量的，为了保证在有足够工作时，系统的繁忙。如果不进行周期性的负载平衡，如果没有大致均衡的CPU负载，分时就会变得不公平。

This is essentially the approach that was taken in DEC OSF/1 3.0 [Denham], and it seems to have worked well there. One notable difference between our kernel and OSF/1 is that our interrupts are backed by threads, whereas OSF/1 keeps spl()s (IPLs in their terminology). However, this doesn't affect the design, since OSF/1 already has to handle real-time scheduling.
这个在本质上和DEC 的OSF/1.3.0相似，这种方法在OSF上好象很有效，一个值得注意的不同是，我们的中断是基于线程的，虽然OSF/1拥有spl，但是，这个没有影响设计，因为OSF/1必须处理实时调度。
Figure 9: Kernel scheduler queues 内核调度队列


4 Summary
Discussion about improved threads support in FreeBSD has been ongoing for several years. The KSE project aims to implement a kernel mechanism that allows the kernel and userland to support threaded processes and communicate with each other effectively so that the necessary information is available for both to do their jobs efficiently and correctly.
讨论在FreeBSD中增加线程支持已经进行了几年。KSE项目的目标是实现一个内核结构，允许内核和用户空间支持线程处理以及相互间有效的通信以便它们有效和正确的完成工作所必要的信息对两者来说都是可用的。
Glossary

KSE:
    Kernel-scheduled entity. This gets scheduled.

Thread:
    A runnable context. This gets suspended.

KSEG:
    Kernel-scheduled entity group.

PCB:
    Process control block.

SA:
    Scheduler activation.

TCB:
    Thread control block.

UTS:
    Userland threads scheduler. Userland, multi-level, and scheduler activation-based threads libraries all have a UTS.

Bibliography

Anderson
    Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska, and Henry M. Levy, Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism, ACM Transactions on Computer Systems, Vol. 10, No. 1, February 1992, Pages 53-79.

Boykin
    Joseph Boykin, David Kirschen, Alan Langerman, and Susan LoVerso, Programming under Mach, Addison-Wesley Publishing Company, Inc. (1993).

Butenhof
    David R. Butenhof, Programming with POSIX threads, Addison Wesley Longman, Inc. (1997).

Denham
    Jeffrey M. Denham, Paula Long, and James A. Woodward, DEC OSF/1 Symmetric Multiprocessing, Digital Technical Journal, Vol. 6, No. 3.

Kleiman
    Steve Kleiman, Devang Shah, and Bart Smaalders, Programming with Threads, SunSoft Press (1996).

Lemon
    Jonathan Lemon, Kqueue: A generic and scalable event notification facility, BSDcon Conference Proceedings (2000), http://people.freebsd.org/~jlemon/kqueue.pdf.

Mauro
    Jim Mauro and Richard McDougall, Solaris Internals, Sun Microsystems Press (2001).

McKusick
    Marshall Kirk McKusick, Keith Bostic, Michael J. Karels, and John S. Quarterman, The Design and Implementation of the 4.4BSD Operating System, Addison-Wesley Publishing Company, Inc. (1996).

Vahalia
    Uresh Vahalia, UNIX $^{TM}$ Internals: The New Frontiers, Prentice-Hall, Inc. (1996).

About this document ...
Kernel-Scheduled Entities for FreeBSD

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -dir html -no_navigation -no_white -show_section_numbers freebsd_kse.tex

The translation was initiated by Chris Knight on 2003-01-01
Chris Knight 2003-01-01

[ 本帖最后由 DarkBlueSea 于 2006-4-10 13:11 编辑 ]

DarkBlueSea

因为内容较多，理论性强，小弟到现在对很多细节也没有把握，望各位大虾指点

lileding

直接用代码展示也许更好的

gvim

原帖由 DarkBlueSea 于 2006-4-2 01:37 发表
Kernel-Scheduled Entities for FreeBSD
FreeBSD中的“内核调度实体”
Jason Evans

jasone@freebsd.org

January 1, 2003

译者： DarkBlueSea

Abstract:
摘要
FreeBSD has histori ...

FreeBSD has historically had less than ideal support for multi-threaded application programming
第一句就有问题，ideal是理想的。原文大意为“以前的FreeBSD缺乏对多线程应用程序编程的良好支持”

不过我还是支持楼主分享自己的翻译成果，暂时翻译的不准确没关系，大家一起完善

gvim

原帖由 lileding 于 2006-4-2 10:47 发表
直接用代码展示也许更好的

代码虽然可以说明一切，但是现在有可以使自己理解更深刻，学习更方便的论文，没必要老拿代码分析出来压人吧。
不过，我并不介意你写一篇代码分析出来给大伙看看。

DarkBlueSea

谢谢楼上的兄弟
莫大的鼓励

antijp

摘要
FreeBSD has historically had less than ideal support for multi-threaded application programming. At present, there are two threading libraries available. libc_r is entirely invisible to the kernel, and multiplexes threads within a single process. The linuxthreads port, which creates a separate process for each thread via rfork(), plus one thread to handle thread synchronization, relies on the kernel scheduler to multiplex "threads" onto the available processors.
从前，FreeBSD缺乏对多线程编成的良好支持。目前，有两个线程库可以使用了。libc_r线程库，是内核完全不可见的，并且一个进程中可以有多个线程。devel/linuxthreads port线程库,它使用rfork()为每个线程创建一个独立的进程，再创建一个线程，来处理线程间的同步，依赖内核调度器，使多个“线程”能在可用的处理器上执行。

A process that is using SAs does not have a kernel stack or PCB. Instead, every time a process is run, a SA is created that contains a kernel stack and thread control block (TCB), and the process runs in the context of the SA. When the SA is preempted or blocked, machine state is stored in the SA's TCB, and the kernel stack is optionally used for completion of a pending system call. See Figure 4.
使用SAs的进程没有系统堆栈和PCB，取而代之的是，每次一个进程要运行时系统创建一个SA，SA中包含一个系统堆栈和线程控制块（TCB），进程运行在SA上下文中，当这个SA被强占或是阻塞，机器状态被保存在SA的TCB中，系统堆栈可以用来完成一个未完成的系统调用。见图4

错字了……

[ 本帖最后由 antijp 于 2006-4-2 14:49 编辑 ]