超能女人用超能:关于kernel和reentrancy

理解linux内核(1)----关于kernel和reentrancy 来源: ChinaUnix博客 　日期：2006.04.30 17:27　(共有条评论) 我要评论  
Utlk, kernel & reentrancy

All Unix kernels are reentrant. This means that several processes may be executing in Kernel Mode at the same time. Of course, on uniprocessor systems, only one process can progress, but many can be blocked in Kernel Mode when waiting for the CPU or the completion of some I/O operation. For instance, after issuing a read to a disk on behalf of some process, the kernel lets the disk controller handle it, and resumes executing other processes. An interrupt notifies the kernel when the device has satisfied the read, so the former process can resume the execution.

所有的UNIX kernel都是可重入的。这意味着可以有很多进程同时以Kernel mode执行。当然，在单CPU系统上任一时刻只能有一个进程在CPU上执行，但是同时可以另外有很多进程阻塞在kernel mode，等待CPU或者I/O操作的完成。例如kernel可以代表一个进程请求磁盘操作，这个操作由磁盘控制器完成，kernel可以调度其他进程继续执行。磁盘操作完成的时候会有一个interruption通知kernel，kernel即可调度刚才请求磁盘操作的进程继续执行。

One way to provide reentrancy is to write functions so that they modify only local variables and do not alter global data structures. Such functions are called reentrant functions. But a reentrant kernel is not limited just to such reentrant functions (although that is how some real-time kernels are implemented). Instead, the kernel can include nonreentrant functions and use locking mechanisms to ensure that only one process can execute a nonreentrant function at a time. Every process in Kernel Mode acts on its own set of memory locations and cannot interfere with the others.

提供可重入性的一种方式，是保证所有函数都只访问局部变量而不更改全局数据。这样的函数被称为可重入的函数。有些实时kernel是通过只用可重入函数来实现的，但一个可重入的kernel并不限于这一种实现方法。Kernel code可以包含不可重入的函数，同时用一些加锁机制来保证不可重入的函数不会被并发执行。Kernel mode的全部进程，都在各自的内存区域上工作并且互不影响。

If a hardware interrupt occurs, a reentrant kernel is able to suspend the current running process even if that process is in Kernel Mode. This capability is very important, since it improves the throughput of the device controllers that issue interrupts. Once a device has issued an interrupt, it waits until the CPU acknowledges it. If the kernel is able to answer quickly, the device controller will be able to perform other tasks while the CPU handles the interrupt.

当一个硬件中断出现的时候，一个可重入的kernel能够挂起当前正在执行的进程，即使那个进程处在kernel mode。这个能力是很重要的，因为它提高了发出中断的硬件控制器的吞吐量。为什么这么说呢，因为一旦一个设备发出一个终端，它会等待CPU作出确认。如果kernel能够及时确认，这个设备的控制器就可以在CPU处理这个中断的时候，继续进行后续操作。

A kernel control path denotes the sequence of instructions executed by the kernel to handle a system call, an exception, or an interrupt.

一个Kernel control path指的是kernel处理一个系统调用，或一个异常，或者一个中断的时候，所执行的指令序列。

In the simplest case, the CPU executes a kernel control path sequentially from the first instruction to the last. When one of the following events occurs, however, the CPU interleaves the kernel control paths:

最简单的情况下，CPU对一个kernel control path的执行，是从头到尾顺序执行其中全部指令。但是，在此过程中如果下列事件发生，CPU可能会交替执行不同的kernel control path：

·         A process executing in User Mode invokes a system call, and the corresponding kernel control path verifies that the request cannot be satisfied immediately; it then invokes the scheduler to select a new process to run. As a result, a process switch occurs. The first kernel control path is left unfinished and the CPU resumes the execution of some other kernel control path. In this case, the two control paths are executed on behalf of two different processes.

o. 一个在User mode执行的进程发出一个system call，处理这个系统调用的kernel control path发现该请求不能被立即满足，于是这个kernel control path调用scheduler来选择另外一个进程继续执行，导致一个进程交换动作。前一个kernel control path并未执行结束且CPU恢复执行另外的某个kernel control path。在这种情况下，两个不同kernel control path代表两个不同进程被执行。

·         The CPU detects an exception—for example, access to a page not present in RAM—while running a kernel control path. The first control path is suspended, and the CPU starts the execution of a suitable procedure. In our example, this type of procedure can allocate a new page for the process and read its contents from disk. When the procedure terminates, the first control path can be resumed. In this case, the two control paths are executed on behalf of the same process.

o. CPU在执行某kernel  control path检测到一个异常——例如试图访问一个不存在的RAM页面。这个情况下引发异常的kernel control path会被挂起，CPU开始执行另外一个kernel control path来应对这个异常。在这个例子中，CPU也许会通过另外一个kernel control path来分配一个新的RAM页面来满足这个内存访问操作。当这个用于异常处理的kernel control path执行结束，引发异常的kernel control path就可以恢复执行。这种情况下，两个不同的kernel control path代表同一个进程被执行。

·         A hardware interrupt occurs while the CPU is running a kernel control path with the interrupts enabled. The first kernel control path is left unfinished and the CPU starts processing another kernel control path to handle the interrupt. The first kernel control path resumes when the interrupt handler terminates. In this case, the two kernel control paths run in the execution context of the same process, and the total elapsed system time is accounted to it. However, the interrupt handler doesn't necessarily operate on behalf of the process.

o. 如果CPU在执行一个kernel control path的时候被某个interrupt打断，那么被打断的kernel control path就会停止执行，CPU开始执行另外一个kernel control path来处理这个中断。处理中断的kernel control path执行结束后，被打断的那个kernel control path恢复执行。这种情况下，这两个kernel control path在同一个进程上下文中得到执行，两个kernel control path消耗的全部时间都被计入这个进程消耗掉的时间。

Implementing a reentrant kernel requires the use of synchronization. If a kernel control path is suspended while acting on a kernel data structure, no other kernel control path should be allowed to act on the same data structure unless it has been reset to a consistent state. Otherwise, the interaction of the two control paths could corrupt the stored information.

实现一个可重入的kernel一定会用到同步机制。如果一个kernel control path在修改一个内核数据结构的过程中被挂起，其它的kernel control path必须被禁止修改同一个内核数据结构，除非此前已经把这个数据结构恢复到了一个一致的状态。否则，这两个kernel control path的相互作用，就可能让这个内核数据结构保存的信息变得不一致。

For example, suppose a global variable V contains the number of available items of some system resource. The first kernel control path, A, reads the variable and determines that there is just one available item. At this point, another kernel control path, B, is activated and reads the same variable, which still contains the value 1. Thus, B decrements V and starts using the resource item. Then A resumes the execution; because it has already read the value of V, it assumes that it can decrement V and take the resource item, which B already uses. As a final result, V contains -1, and two kernel control paths use the same resource item with potentially disastrous effects.

例如一个全局变量v保存了当前某种系统资源的空闲量。kernel control path A读取这个变量发现这种资源还有1个单位空闲，此时另外一个kernel control path B读取同一个变量，也发现该变量的值是1，B令v的值减一，并且开始使用这个资源。然后A恢复执行，因为它此前已经读取过v的值，所以它认为这种资源还有1单位可用，就也令v的值减一，并且开始使用这个资源。这样最后结果就是v的值是-1，并且两个kernel control path同时使用同一个资源，可能导致严重后果。

When the outcome of some computation depends on how two or more processes are scheduled, the code is incorrect. We say that there is a race condition.

当计算结果依赖于两个或更多进程被调度的顺序，我们说这段代码是错的，这种情况被称为竞态条件，也叫竞态或竞争。

In general, safe access to a global variable is ensured by using atomic operations. In the previous example, data corruption is not possible if the two control paths read and decrement V with a single, noninterruptible operation. However, kernels contain many data structures that cannot be accessed with a single operation. For example, it usually isn't possible to remove an element from a linked list with a single operation because the kernel needs to access at least two pointers at once. Any section of code that should be finished by each process that begins it before another process can enter it is called a critical region

一般说来，对全局变量的安全访问必须是通过原子操作进行的。在前一个例子里，如果“读取v的值”和“令v减一”是作为一个不能被打断的操作执行的，那么数据就不会有被破坏的危险。但是kernel包含了很多不能用一个操作访问的数据结构，比如不可能用一个操作来删除链表中的一个元素，因为kernel必须同时访问两个指针才能做到这一点。任何代码段如果必须被某个进程完全执行结束才能再被另外的进程执行，那么这个代码段就被称为关键区(critical region)。