linuxkernel.htm

Linux Kernel中文手册

<P ALIGN="JUSTIFY">　</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">Hash table</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>是一个指向数据结构的指针的数组，它的索引来源于数据结构中的信息。如果你用一个数据结构来描述一个村庄的人口，你可以用年龄作为索引。要找出一个指定的人的数据，你可以用他的年龄作为索引在人口散列表中查找，通过指针找到包括详细信息的数据结构。不幸的是，一个村庄中可能很多人年龄相同，所以散列表的指针指向另一个链表数据结构，每一个元素描述同龄人。即使这样，查找这些较小的链表仍然比查找所有的数据结构要快。</P>
<P ALIGN="JUSTIFY">　</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">Hash table</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>可用于加速常用的数据结构的访问，在</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>里常用</FONT><FONT SIZE=3>hash table</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>来实现缓冲。缓冲是需要快速存取的信息，是全部可用信息的一个子集。数据结构被放在缓冲区并保留在那里，因为核心经常访问这些结构。使用缓冲区也有副作用，因为使用起来比简单链表或者散列表更加复杂。如果数据结构可以在缓冲区找到（这叫做缓冲命中），那么一切很完美。但是如果数据结构不在缓冲区中，那么必须查找所用的相关的数据结构，如果找到，那么就加到缓冲区中。增加新的数据结构到缓冲区中可能需要废弃一个旧的缓冲入口。</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>必须决定废弃那一个数据结构，风险在于废弃的可能使</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>下一个要访问的数据结构。</P>
<P ALIGN="JUSTIFY">　</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">2.3.3 Abstract Interfaces</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>（抽象接口）</P>
<P ALIGN="JUSTIFY">　</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">Linux</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>核心经常将它的接口抽象化。接口是以特定方式工作的一系列例程和数据结构。比如：所有的网络设备驱动程序都必须提供特定的例程来处理特定的数据结构。用抽象接口的方式可以用通用的代码层来使用底层特殊代码提供的服务（接口）。例如网络层是通用的，而它由底层符合标准接口的同设备相关的代码提供支持。</P>
<P ALIGN="JUSTIFY">通常这些底层在启动时向高一层登记。这个登记过程常通过在链接表中增加一个数据结构来实现。例如，每一个连结到核心的文件系统在核心启动时进行登记（或者如果你使用模块，在文件系统第一次使用时向核心登记）。你可以查看文件</FONT><FONT SIZE=3>/proc/filesystems</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>来检查那些文件系统进行了登记。登记所用的数据结构通常包括指向函数的指针。这是执行特定任务的软件函数的地址。再一次用文件系统登记的例子，每一个文件系统登记时传递给</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>核心的数据结构都包括一个和具体文件系统相关的例程地址，在安装文件系统时必须调用。</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">　</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">Chapter 3 </P>
<P ALIGN="JUSTIFY">Memory Management </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>（内存管理）</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">内存管理子系统是操作系统的重要部分。从计算机发展早期开始，就存在对于大于系统中物理能力的内存需要。为了克服这种限制，开发了许多种策略，其中最成功的就是虚拟内存。虚拟内存通过在竞争进程之间共享内存的方式使系统显得拥有比实际更多的内存。</P>
<P ALIGN="JUSTIFY">虚拟内存不仅仅让你的计算机内存显得更多，内存管理子系统还提供：</P>
<P ALIGN="JUSTIFY">　</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">Large Address Spaces</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>（巨大的地址空间）操作系统使系统显得拥有比实际更大量的内存。虚拟内存可以比系统中的物理内存大许多倍。</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">Protection</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>（保护）系统中的每一个进程都有自己的虚拟地址空间。这些虚拟的地址空间是相互完全分离的，所以运行一个应用程序的进程不会影响另外的进程。另外，硬件的虚拟内存机制允许对内存区写保护。这可以防止代码和数据被恶意的程序覆盖。</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">Memory Mapping</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>（内存映射）内存映射用来将映像和数据映射到进程的地址空间。用内存映射，文件的内容被直接连结到进程的虚拟地址空间。</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">Fair Physics Memory Allocation</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>（公平分配物理内存）内存管理子系统允许系统中每一个运行中的进程公平地共享系统的物理内存</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">Shared Virtual Memory</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>（共享虚拟内存）虽然虚拟内存允许进程拥有分离（虚拟）的地址空间，有时你也需要进程之间共享内存。例如，系统中可能有多个进程运行命令解释程序</FONT><FONT SIZE=3>bash</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>。虽然可以在每一个进程的虚拟地址空间都拥有一份</FONT><FONT SIZE=3>bash</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的拷贝，更好的是在物理内存中只拥有一份拷贝，所有运行</FONT><FONT SIZE=3>bash</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的进程共享代码。动态连接库是多个进程共享执行代码的另一个常见例子。共享内存也可以用于进程间通讯</FONT><FONT SIZE=3>(IPC)</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>机制，两个或多个进程可以通过共同拥有的内存交换信息。</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>系统支持系统</FONT><FONT SIZE=3>V</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的共享内存</FONT><FONT SIZE=3>IPC</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>机制。</P>
<P ALIGN="JUSTIFY">　</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">3.1 An Abstract Model of Virtual Memory</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>（虚拟内存的抽象模型）</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">在考虑</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>支持虚拟内存的方法之前，最好先考虑一个抽象的模型，以免被太多的细节搞乱。</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">在进程执行程序的时候，它从内存中读取指令并进行解码。解码指令也许需要读取或者存储内存特定位置的内容，然后进程执行指令并转移到程序中的下一条指令。进程不管是读取指令还是存取数据都要访问内存。</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">在一个虚拟内存系统中，所有的地址都是虚拟地址而非物理地址。处理器通过操作系统保存的一组信息将虚拟地址转换为物理地址。</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">为了让这种转换更简单，将虚拟内存和物理内存分为适当大小的块，叫做页（</FONT><FONT SIZE=3>page</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>）。页的大小一样。（当然可以不一样，但是这样一来系统管理起来比较困难）。</FONT><FONT SIZE=3>Linux</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>在</FONT><FONT SIZE=3>Alpha AXP</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>系统上使用</FONT><FONT SIZE=3>8K</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>字节的页，而在</FONT><FONT SIZE=3>Intel x86</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>系统上使用</FONT><FONT SIZE=3>4K</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>字节的页。每一页都赋予一个唯一编号：</FONT><FONT SIZE=3>page frame number(PFN </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>页编号</FONT><FONT SIZE=3>)</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>。在这种分页模型下，虚拟地址由两部分组成：虚拟页号和页内偏移量。假如页大小是</FONT><FONT SIZE=3>4K</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>，则虚拟地址的位</FONT><FONT SIZE=3>11</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>到</FONT><FONT SIZE=3>0</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>包括页内偏移量，位</FONT><FONT SIZE=3>12</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>和以上的位是页编号。每一次处理器遇到虚拟地址，它必须提取出偏移和虚拟页编号。处理器必须将虚拟页编号转换到物理的页，并访问物理页的正确偏移处。为此，处理器使用了页表（</FONT><FONT SIZE=3>page tables</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>）。</P>
<P ALIGN="JUSTIFY">图</FONT><FONT SIZE=3>3.1</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>显示了两个进程的虚拟地址空间，进程</FONT><FONT SIZE=3>X</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>和进程</FONT><FONT SIZE=3>Y</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>，每一个进程拥有自己的页表。这些页表将每一个进程的虚拟页映射到内存的物理页上。图中显示进程</FONT><FONT SIZE=3>X</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的虚拟页号</FONT><FONT SIZE=3>0</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>映射到物理页号</FONT><FONT SIZE=3>1</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>，而进程</FONT><FONT SIZE=3>Y</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的虚拟页编号</FONT><FONT SIZE=3>1</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>映射到物理页号</FONT><FONT SIZE=3>4</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>。理论上页表每一个条目包括以下信息：</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">有效标志</FONT><FONT SIZE=3>  </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>表示页表本条目是否有效</P>
<P ALIGN="JUSTIFY">本页表条目描述的物理页编号</P>
<P ALIGN="JUSTIFY">访问控制信息</FONT><FONT SIZE=3> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>描述本页如何使用：是否可以写？是否包括执行代码？</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">页表通过虚拟页标号作为偏移来访问。虚拟页编号</FONT><FONT SIZE=3>5</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>是表中的第</FONT><FONT SIZE=3>6</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>个元素（</FONT><FONT SIZE=3>0</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>是第一个元素）</P>
<P ALIGN="JUSTIFY">要将虚拟地址转换到物理地址，处理器首先找出虚拟地址的页编号和页内偏移量。使用</FONT><FONT SIZE=3>2</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的幂次的页尺寸，可以用掩码或移位简单地处理。再一次看图</FONT><FONT SIZE=3>3.1</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>，假设页大小是</FONT><FONT SIZE=3>0x2000</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>（十进制</FONT><FONT SIZE=3>8192</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>），进程</FONT><FONT SIZE=3>Y</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的虚拟地址空间的地址是</FONT><FONT SIZE=3>0x2194</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>，处理器将会把地址转换为虚拟页编号</FONT><FONT SIZE=3>1</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>内的偏移量</FONT><FONT SIZE=3>0x194</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>。</P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY"><IMG SRC="Image2.gif" WIDTH=553 HEIGHT=386></P>
<P ALIGN="JUSTIFY">　</P>
<P ALIGN="JUSTIFY">处理器使用虚拟页编号作为索引在进程的页表中找到它的页表的条目。如果该条目有效，处理器从该条目取出物理的页编号。如果本条目无效，就是进程访问了它的虚拟内存中不存在的区域。在这种情况下，处理器无法解释地址，必须将控制权传递给操