通常32位cpu使用2U页表机制就已够，但到64位时代，2U页表会佉K表的Ҏ剧增加Q所以通常会用更多的表U数?br /> ia64/ppc64/alpha使用3U页表，x86_64使用?U页表。ؓ兼容q些模型Q?.6.11之后使用了统一?U页表模?br /> Global Directory
Upper Directory
Middle Directory
Page Table
针对不同的架构，讄每一U不同的地址位数Q?的话是不用这一U页表机制?br />
cache
多cpu环境中，每个cpu有自qcacheQ对cache的更新有g机制保证通知其他的cpuq行同步?真的?)
tlb
用来cache表Q加速地址的{换速度。每个cpu有自qtlbQ但不需要同步，因ؓ地址转换和进E相兟?br />
]]>
NPTL:
2.6后加入的新实玎ͼredhat as?.4可以支持。更W合pthread的规范。用LE和内核U程采取1:1模式Q支持floating stack?br />
]]>
单的例子Qhotspot解析模式中iconst_0的对应汇~代码：
iconst_0 3 iconst_0 [0xb4d98120, 0xb4d98160] 64 bytes
0xb4d98120: sub esp, 0x4
0xb4d98123: fstp dword [esp]
0xb4d98126: jmp 0x1e
0xb4d9812b: sub esp, 0x8
0xb4d9812e: fstp qword [esp]
0xb4d98131: jmp 0x13
0xb4d98136: push edx
0xb4d98137: push eax
0xb4d98138: jmp 0xc
0xb4d9813d: push eax
0xb4d9813e: jmp 0x6
0xb4d98143: push eax
0xb4d98144: xor eax, eax
0xb4d98146: movzx ebx, byte [esi+0x1]
0xb4d9814a: inc esi
0xb4d9814b: jmp dword near [ebx*4+0x6900680]
]]>
1 入节ҎZ个单节点的树 // MAKE_SET
2 Ҏ个子节点Q递归调用该算法完成子树内所有查询，
再将子节点的ancester指向本节点，归ƈl果?nbsp; // UNION
3 处理完所有子节点后，本节点标ؓchecked
4 遍历查询集中和该节点有关的查询，查另一个节Ҏ否已标ؓcheckedQ如果是的话说明
1Q?该节点在本节点的子树
2Q?该节点和本节点在另一节点的子树中Q而且该节点已被查?br /> 无论哪种情况Q检查该节点所在树的根是q两个节点的LCA节点
如果没有标识checkedQ只需单蟩q，当遍历到该节Ҏ可以完成查询了
下面是java的实C码和单测?br />
import java.util.*;
public class Tarjan{
static void lca( Node p, ArrayList<Query> q ){
MAKE_SET(p);
//FIND(p).ancester=p;
for( Node i : p.childs){
lca( i, q );
UNION( p, i );
FIND(p).ancester=p;
}
p.checked=true;
for( Query query : q ){
if( query.p1==p ){
if( query.p2.checked ){
query.result=FIND(query.p2);
}
}else if( query.p2==p ){
if( query.p1.checked ){
query.result=FIND(query.p1);
}
}else{
continue;
}
}
}
static void MAKE_SET( Node p ){
p.ancester = p;
}
static Node FIND( Node p ){
Node r=p;
for( ; r.ancester!=r; r=r.ancester );
return r;
}
static void UNION( Node p, Node q ){
q.ancester=p;
}
public static void main( String args[] ){
// create tree
Node p[]=new Node[24];
p[0]=new Node(0,null); // root
p[1]=new Node(1,p[0]);
p[2]=new Node(2,p[0]);
p[3]=new Node(3,p[0]);
p[4]=new Node(4,p[1]);
p[5]=new Node(5,p[1]);
p[6]=new Node(6,p[1]);
p[7]=new Node(7,p[2]);
p[8]=new Node(8,p[2]);
p[9]=new Node(9,p[3]);
p[10]=new Node(10,p[3]);
p[11]=new Node(11,p[3]);
p[12]=new Node(12,p[4]);
p[13]=new Node(13,p[4]);
p[14]=new Node(14,p[6]);
p[15]=new Node(15,p[8]);
p[16]=new Node(16,p[10]);
p[17]=new Node(17,p[10]);
p[18]=new Node(18,p[14]);
p[19]=new Node(19,p[14]);
p[20]=new Node(20,p[17]);
p[21]=new Node(21,p[17]);
p[22]=new Node(22,p[17]);
p[23]=new Node(23,p[11]);
// make lca query
ArrayList< Query > q= new ArrayList<Query>();
q.add( new Query(p[15], p[19]));
q.add( new Query(p[21], p[16]));
q.add( new Query(p[14], p[14]));
q.add( new Query(p[4], p[23]));
q.add( new Query(p[23], p[16]));
// lca
lca( p[0], q );
// dump results
for( Query item : q ){
System.out.println( item.p1+":"+item.p2+": result is:"+item.result );
}
}
}
class Node{
public Node( int id, Node parent ){
this.id=id;
if( parent != null ){
parent.childs.add(this);
}else{
assert this.id==0;
}
this.checked=false;
this.ancester=null;
this.childs=new ArrayList<Node>();
}
int id;
ArrayList<Node> childs;
public String toString(){
return "Node:<"+id+">";
}
Node ancester; // used for lca search
boolean checked; // used for lca search
}
class Query{
public Query( Node p1, Node p2 ){
assert p1!=null && p2!=null;
this.p1=p1;
this.p2=p2;
this.result=null;
}
Node p1;
Node p2;
Node result;
}
public class Tarjan{
static void lca( Node p, ArrayList<Query> q ){
MAKE_SET(p);
//FIND(p).ancester=p;
for( Node i : p.childs){
lca( i, q );
UNION( p, i );
FIND(p).ancester=p;
}
p.checked=true;
for( Query query : q ){
if( query.p1==p ){
if( query.p2.checked ){
query.result=FIND(query.p2);
}
}else if( query.p2==p ){
if( query.p1.checked ){
query.result=FIND(query.p1);
}
}else{
continue;
}
}
}
static void MAKE_SET( Node p ){
p.ancester = p;
}
static Node FIND( Node p ){
Node r=p;
for( ; r.ancester!=r; r=r.ancester );
return r;
}
static void UNION( Node p, Node q ){
q.ancester=p;
}
public static void main( String args[] ){
// create tree
Node p[]=new Node[24];
p[0]=new Node(0,null); // root
p[1]=new Node(1,p[0]);
p[2]=new Node(2,p[0]);
p[3]=new Node(3,p[0]);
p[4]=new Node(4,p[1]);
p[5]=new Node(5,p[1]);
p[6]=new Node(6,p[1]);
p[7]=new Node(7,p[2]);
p[8]=new Node(8,p[2]);
p[9]=new Node(9,p[3]);
p[10]=new Node(10,p[3]);
p[11]=new Node(11,p[3]);
p[12]=new Node(12,p[4]);
p[13]=new Node(13,p[4]);
p[14]=new Node(14,p[6]);
p[15]=new Node(15,p[8]);
p[16]=new Node(16,p[10]);
p[17]=new Node(17,p[10]);
p[18]=new Node(18,p[14]);
p[19]=new Node(19,p[14]);
p[20]=new Node(20,p[17]);
p[21]=new Node(21,p[17]);
p[22]=new Node(22,p[17]);
p[23]=new Node(23,p[11]);
// make lca query
ArrayList< Query > q= new ArrayList<Query>();
q.add( new Query(p[15], p[19]));
q.add( new Query(p[21], p[16]));
q.add( new Query(p[14], p[14]));
q.add( new Query(p[4], p[23]));
q.add( new Query(p[23], p[16]));
// lca
lca( p[0], q );
// dump results
for( Query item : q ){
System.out.println( item.p1+":"+item.p2+": result is:"+item.result );
}
}
}
class Node{
public Node( int id, Node parent ){
this.id=id;
if( parent != null ){
parent.childs.add(this);
}else{
assert this.id==0;
}
this.checked=false;
this.ancester=null;
this.childs=new ArrayList<Node>();
}
int id;
ArrayList<Node> childs;
public String toString(){
return "Node:<"+id+">";
}
Node ancester; // used for lca search
boolean checked; // used for lca search
}
class Query{
public Query( Node p1, Node p2 ){
assert p1!=null && p2!=null;
this.p1=p1;
this.p2=p2;
this.result=null;
}
Node p1;
Node p2;
Node result;
}
试使用的树Q?br />
0
+--------------+--------------------+
| | |
1 2 3
+-----+------+ +---+ +-------+---------+
| | | | | | | |
4 5 6 7 8 9 10 11
+---+ + + +--+------+ |
| | | | | | 23
12 13 14 15 16 17
+--------+ +----+----+
| | | | |
18 19 20 21 22
PSQ差点忘了，lp生日快乐
]]>
一般来_在堆上分配的效率要低于栈Q。例如堆是全局的，在多U程E序中要使用锁来q行同步Q不巧的是，l大部分的javaE序都是多线E的。另一斚wQ随着对象的生成和销毁，堆上会生碎片，需要一个或多个freelist来维护，q样也造成额外的开销Q以及空间利用的低效?br />
但这是一般cE序员理解的heap理机制Q也因此有cE序员指责java的内存管理效率低下。其实在jvm的实CQ它会用自己的方式来理堆，增强java的效率。以HotspotZQ每个线E都会拥有一D自qI间UCؓTLAB(Thread Local Alloc Buffer)Q这块空间因为属于线E独有，所以在其中分配对象不需要加锁，其实和栈一P分配对象只要一个指针增加sizeof(object)卛_。如果对象太大超Ztlab的剩余空_此时有多U选择Q?br /> 在heap的shareI间中分配，
重新分配一块tlab
在old generation中分?br /> 触发gcQ释攑ַ有空间?br /> 具体选择何种方式由内存的利用情况和jvm的内存管理策略决定。由多个参数可以q行调整。所以在l大部分情况下（?0%Q，jvm中对象的分配和栈一样高效?br />
关于对象的释放，是java中著名的gc来负责了Q关于gc的介l多如牛毛，而且其中的方式和{略层出不穷Q这片文章就不介l了?br />
从上面的介绍可以看出Q这U方式可以加速对象的分配Q但寚w放不能作到象stack那样高效Q其实有很多对象只是生存期很短的临时对象Q如何识别这些对象ƈ在tlab中更有效的释攑ֺ该是jvm可以q一步优化的方向。据我所知，jdk6的jvm已经使用了相关的技术?br />
]]>
回去试用后果然画面有了飞跃。拍摄h像的层次感，立体感都丰富了不。换机如换刀啊?br />
以后大概会在q上面投入不钱吧，为我今后的钱包默哀一下?br />
]]>