emm-principle_1.htm

编写自己的操作系统

<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt">所有的线性空间的内容只有被放置到物理内存中才能够被真正的运行和操作。所以，尽管OS 
Kernel和进程都被放在线性空间中，但它们最终必须被放置到物理内存中。所以OS 
Kernel和所有的进程都最终共享物理内存。在现阶段，物理内存远没有线性空间那么大——线性空间是4 
GB，而物理内存空间往往只有几百兆，甚至更小。另外即使物理内存有4 GB，但由于每个进程都可以有3 GB线性空间（假如进程私有线性空间是3 
GB的话），如果把所有进程的线性空间内容都放在物理内存中，明显是不现实的。所以OS 
Kernel必须将某些进程暂时用不到的数据或代码放在物理内存之外，将有限的内存提供给当前最需要的进程。另外，由于OS 
Kernel在任何时候都有可能运行，所以OS Kernel最好被永远放在物理内存中。我们仅仅将进程数据进行换入换出。</DIV>
<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt">&nbsp;</DIV></DIV>
<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt">从线性空间到物理空间的映射需要映射表，映射表的内容是将某段线性空间映射到相同大小的物理内存空间上。从理论上，我们可以使用两种映射方法：变长映射，和定长映射。变长映射指的是根据不同的需要，将一个一个变长段映射到物理内存上，其格式可以如下(线性空间段起始地址，物理空间段起始地址，段长度)。假如一个进程有3个段：10M的数据段，5M的代码段，和8K的堆栈段，那么就可以在映射表中建立3项内容，每一项针对一个段。这看起来没有问题。但假如现在我们的实际的内存只有32M，其中10M被内核占用，留给进程的物理空间只有22M，那么此进程在运行时，就占据了10M+5M+8K的内存空间。随后当进程发生切换时，假如另一个进程和其有相同的内存要求，那么剩余的22M-(10M+5M+8K)明显就不够用了，这时只能将原进程的某些段换出，并且必须是整段的换出。这就意味着我们必须至少换出一个10M的数据段，而换出的成本很高，因为我们必须将这10M的内容拷贝到磁盘上，磁盘I/O是很慢的。</DIV>
<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt">&nbsp;</DIV>
<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt">所以，使用变长的段映射的结果就是一个段要么被全部换入，要么被全部换出。但在现实中，一个程序中并非所有的代码和数据都能够被经常访问，往往被经常访问的只占全部代码数据的一部分，甚至是一小部分。所以更有效的策略是我们最好只换出那些并不经常使用的部分，而保留那些经常被使用的部分。而不是整个段的换入换出。这样可以避免大块的慢速磁盘操作。</DIV>
<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt">&nbsp;</DIV>
<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt">这就是定长映射策略，我们将内存空间分割为一个个定长块，每个定长块被称为一个页。映射表的基本格式为（物理空间页起始地址），由于页是定长的，所以不需要指出它的长度，另外，我们不需要在映射表中指定线性地址，我们可以将线性地址作为索引，到映射表中检索出相应的物理地址。当使用页时，其策略为：当换出的时候，我们只将那些不活跃的，也就是不经常使用的页换出，而保留那些活跃的页。在换入的时候，只有被请求访问的页才被换入，没有被请求访问的页将永远不会被换入到物理内存。这就是请求页（Demand 
Page）算法的核心思想。</DIV>
<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt">&nbsp;</DIV>
<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt">这就引出一个页大小的问题：首先我们不可能以字节为单位，这样映射表的大小和线性空间大小相同——假如整个线性空间都被映射的话——我们不可能将全部线性空间用作存放这个映射表。由此，我们也可以得知，页越小，则映射表的容量越大。而我们不能让映射表占用太多的空间。但如果页太大，则面临着和不定长段映射同样的问题，每次换出一个页，都需要大量的磁盘操作。另外，由于为一个进程分配内存的最小单位是页，假如我们的页大小为4 
MB，那么即使一个进程只需要使用4 KB的内存，也不得不占用整个4 MB页，这明显是一种很大的浪费。所以我们必须在两者之间进行折衷，一般平台所规定的页大小为1 
KB到8 KB，IA-32所规定的页大小为4 KB。（IA-32也支持4 MB页，你可以根据你的OS的用途进行选择，一般都是使用4 KB页）。</DIV>
<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt"><STRONG><FONT 
face="Times New Roman" size=5>
<HR width="100%" SIZE=2>
</FONT></STRONG>
<P></P>
<P><FONT face="Times New Roman" size=5><STRONG></STRONG></FONT></P><SPAN 
lang=EN-US><SPAN style="mso-tab-count: 1">
<P class=MsoNormal 
style="MARGIN: 0cm 0cm 0pt 21pt; TEXT-INDENT: -21pt; tab-stops: list 21.0pt; mso-list: l5 level1 lfo3"><SPAN 
style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><SPAN 
lang=EN-US><FONT face="Times New Roman" size=5><STRONG>4.&nbsp;Page 
Table</STRONG></FONT></SPAN></SPAN></SPAN></SPAN></P></DIV>
<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt">&nbsp;</DIV>
<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt">假如使用4 KB的页，那么对于4 
GB的线性空间，则需要1,048,576个页表实体，每个表项占用4个字节，则需要4,194,304个字节。仅仅页表就占用4 
MB空间，这是一个很大的需求。但如果确确实实一个进程需要使用全部线性空间的话，那么这4 MB的页表空间投入也是必要的。</DIV>
<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt">&nbsp;</DIV>
<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt">但在现实中，很少有那个程序需要使用这么大空间，一般的程序往往很小，从几KB到几MB，再使用这么大的页表就纯粹是一种浪费。那我们该怎么办？</DIV>
<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt">&nbsp;</DIV>
<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt">一种策略是建立变长页表——我们只建立所需长度的页表。但这种策略带来很大的限制，并且仍然会造成比较大的空间浪费。由于页表机制是使用线性地址作为索引，到页表中进行检索。那么如果我们想让OS 
Kernel使用C0000000h-FFFFFFFFh，也就是3 GB-4 GB之间的线性空间，那么页表的3 
MB以上部分肯定被使用，那么页表还是不得不占用大于3 MB空间的空间，即使这个进程仅仅使用1 KB的线性空间。除非我们把OS 
Kernel放在0h-3FFFFFFFh，也就是第一个1 GB线性空间。即使是这样，我们的页表也必须至少占用1 MB的空间，尽管实际上我们的内核可能只有4 
MB，只需要1024个表项，也就是4 
KB表项空间——因为进程私有的线性空间是从40000000h开始的。另外，对于共享库而言，它们一般被放在物理内存的某个位置，同时映射到某个线性空间位置，这个映射关系对所有的进程都是一致的。每个进程都将所需共享库的映射关系放在自己的页表中。为了给用户进程留出足够的空间，共享库一般被映射到较高的线性空间，比如2 
GB的位置。那么页表则至少需要2 MB以上的空间。总之，变长页表无法真正解决页表空间浪费的问题。</DIV>
<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt">&nbsp;</DIV>
<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt">另外一种策略是使用多级页表。我们以4 
KB页的二级页表为例来说明多级页表的原理。</DIV>
<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt">&nbsp;</DIV>
<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt">二级页表的第一级称为页目录(Page 
Directory)，第二级称为页表(Page Table)。</DIV>
<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt">&nbsp;</DIV>
<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt">如果使用一级页表，则对于4 
KB页的来说，其起始地址都是以4 
KB=2^12对齐的，所以一个线性地址的低12-bit用来做页内寻址。高20-bit被用来做页表索引。而如果使用2级页表，则将其高20-bit分为两部分，比如我们分为2个10-bit，高位的10-bit用来做Page 
Directory的索引，用于定位Page Table；低位10-bit用来做Page 
Table的索引，用于定位Page；最低的12-bit用于定位页内Offset。所以通过3部分的组合，一个32-bit的线性地址就最终转化为一个32-bit的物理地址。</DIV>
<DIV class=Section1 
style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt">&nbsp;</DIV>
<P class=Section1 style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt" 
align=center><IMG src="emm-principle_1.files/pt-2.gif" 
tppabs="http://pagoda-ooos.51.net/os_book/emm/principle/pt-2.GIF"></P>
<P class=Section1 style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt" 
align=left>在整个2级页表架构中，只存在一个Page 
Directory，由于页目录索引是10-bit，所以页目录中有2^10=1024个页目录表项（Directory Entry）。一个Directory 
Entry占4个字节，所以页目录大小为1024*4 = 4&nbsp;KB，恰好被放在一个页中。每一个Directory 
Entry指向一个页表，所以最多有1024个Page Table，但并非所有Page Table都需要存在。每一个Page 
Table的索引也是10-bit，所以一个Page Table中有2^10=1024个页表表项（Page-Table 
Entry）；一个Page-Table&nbsp;Entry占4个字节，所以一个Page Table大小为1024*4 = 
4&nbsp;KB，也恰好被放在一个页中。所以一个Directory Entry的高20-bit加上全为0的低12-bit，就是其所指向的Page 
Table所在页的起始地址。一个Page-Table Entry的高20-bit加上全为0的低12-bit，就是其所指向的Page的起始地址。</P>
<P class=Section1 style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt" 
align=left>这样，当我们给出一个32-bit的线性地址时，首先取出高10-bit作为Page Directory的索引，找到相应的Directory 
Entry，然后根据此Directory Entry的高20-bit找到相应的Page 
Table所在的Page，再根据线性地址的中间10-bit作为索引，在此Page Table中找到相应的Page-Table 
Entry，然后根据此Page-Table Entry的高20-bit找到相应的Page，最后根据线性地址的低12-bit作为Offset，加上Page 
Base Address就转化成了32-bit的物理地址。</P>
<P class=Section1 style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt" 
align=left>这就是2级页表的线性地址到物理地址的映射机制。在2级页表中，Page Directory占用4 
KB字节，这是2级页表的最小内存需求。Page Table则根据实际的需要而创建。假如OS Kernel被放在3 GB的位置，大小为4 
MB，则只需要创建一个Page Table，然后将Page Directory的第768个Directory Entry设为指向此Page 
Table所在的页基地址。如果进程自身占用4 MB，占用线性地址0-4MB，则只需要再创建一个Page Table，然后将Page 
Directory的第0个Directory Entry设为指向此Page Table所在的页基地址。其它的线性地址没有被使用，所以不需要再创建其它的Page 
Table，而将Page Directory中的其它Directory Entry都设为空。这种情况下，页表所占据的空间就是4 KB*3=12 
KB。而如果使用1级页表，即使是变长的，也需要3M+4K。所以使用2级页表很大的节省了页表空间。</P>
<P class=Section1 style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt" 
align=left>基于绝大多数程序都是几百KB或一两兆的事实，为了更进一步的节省页表空间，可以使用三级或多级页表。但这样同时也造成对一个线性地址到物理地址的转换层次过多。另外，对于大型程序来说，其占用的页表空间可能更多。所以，很少有系统使用3级以上页表。</P>
<P class=Section1 style="LAYOUT-GRID-CHAR: none; LAYOUT-GRID-LINE: 15.6pt" 
align=left>&nbsp;</P></BODY></HTML>