posts - 12,comments - 1,trackbacks - 0
看understanding linux kernel的一点笔记:
页表
通常32位cpu使用2级页表机制就已足够,但到64位时代,2级页表会使页表的项急剧增加,所以通常会使用更多的页表级数。
ia64/ppc64/alpha使用3级页表,x86_64使用到4级页表。为兼容这些模型,2.6.11之后使用了统一的4级页表模型
Global Directory
Upper Directory
Middle Directory
Page Table
针对不同的架构,设置每一级不同的地址位数,0的话就是不使用这一级页表机制。

cache
多cpu环境中,每个cpu有自己的cache,对cache的更新有硬件机制保证通知其他的cpu进行同步。(真的吗?)

tlb
用来cache页表,加速地址的转换速度。每个cpu有自己的tlb,但不需要同步,因为地址转换和进程相关。

posted @ 2008-11-01 08:27 白色天堂 阅读(130) | 评论 (0)编辑 收藏
LinuxThreads:
  旧的pthread实现,基于process实现pthread。主要问题是signal不符合规范,stack size固定???

NPTL:
  2.6后加入的新实现,redhat as中2.4就可以支持。更符合pthread的规范。用户线程和内核线程采取1:1模式,支持floating stack。

posted @ 2008-09-09 22:56 白色天堂 阅读(183) | 评论 (0)编辑 收藏
今天花了一点时间作了个x86上hotspot vm的disassembler,这样可以看出jvm生成的本地代码了。
代码比较简单,主要是用了udis86的库,这个可以在sf上下载到,它的接口还是比较简单的。

简单的例子,hotspot解析模式中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]

posted @ 2008-08-24 00:28 白色天堂 阅读(170) | 评论 (0)编辑 收藏
对soft reference,比较容易理解它的用处。它天生就是为实现cache来设计的。关于weak reference,好像很少有人说的清楚。有的和soft reference混在一起谈,有的就是简单翻译java doc中的说明,看得出翻译的人自己也不是很理解,所以只能一笔带过。

我也一直不是很清楚它的实际用途,今天我突然想到WeakReference可能的设计目的。

从java的内存泄漏说起,以前说到java也会内存泄漏的时候往往会举这样的例子,对象保存在一个全局表中,造成无法回收。一般的解决方法是不要使用全局表或者记得更新。但在实际开发中,有时必须要使用全局表,但无法明确知道该对象是否可销毁,因为对象可能被多个线程共享访问,所以程序不能确切的更新表中的引用。这时候weak reference就有用武之地,用WeakHashMap构造全局表,key和value之间是weak reference,这样的话程序员就不用考虑更新该表了,只要该对象没有强引用指向它,gc就可以回收它了。

回头去找一个实际的例子对照看看,记得在JDK中,weak reference还是用的很频繁的。

posted @ 2008-07-25 22:51 白色天堂 阅读(594) | 评论 (0)编辑 收藏
以前用redhat的时候使用rpm管理软件包,因为不能解决软件的依赖关系后来转到debian。apt确实方便了很多,但一直怀念rpm的一个功能,rpm可以查询一个文件具体属于哪个包,用apt一直没有找到对应的命令。
今天想在64位ubuntu上编译32位程序的时候发现没有/usr/include/gnu/stub-32.h,在网上搜索时突然发现apt也可以根据文件来搜索包。命令是apt-file(缺省是没有安装的)。
先安装apt-file
使用apt-file update同步安装包内部的文件,它会到你定义的source去获取这些信息,运行会比较慢,而且没有什么提示,不知道今后会不会都是这样。
然后就可以用apt-file find xxx 去查询了。


-每天进步一点点, :)

posted @ 2008-05-21 23:04 白色天堂 阅读(337) | 评论 (1)编辑 收藏
代码生成一般采用tree rewriting的方式,先将源代码转换成语法树的形式,通过模式匹配将子树替换成叶结点,同时生成代码指令,当树全部替换完后代码即生成了。采用这种方式主要关心匹配规则,甚至可以使用lex/yacc之类的工具生成code generator generator,也便于实现可移植的编译器。

dynamic programing
前面的算法如果只是从左往右依次匹配的话生成的代码质量不高,DP就是要考虑指令的代价,生成质量较优的代码。

自底向上为每个节点计算一系列值存入数组C[],其中index代表使用的register数目,存储的是相应的代价(要考虑可能增加的store/load指令代价),计算某个节点的C[]时,先找到可能的匹配模式,根据匹配模式选择可能的寄存器数目组合,计算代价后选择最小值。这样遍历整个树后可以得到最小代价生成方式。



posted @ 2008-05-07 05:14 白色天堂 阅读(254) | 评论 (0)编辑 收藏
最近看代码时看到Tarjan算法,搜索了一下,是个经典的求LCA(Least Common Ancestor)算法。奇怪的是,网上一般的介绍只会给出伪码,而且有关集合的实现都没有。为理解它还想了半天。目前有些细节还没有完全想清楚(主要和wikipedia上给出的伪码实现并不完全一致),但根据我的理解,我的实现应该是可以完成功能。
基本描述:
   本身是一个从根开始的深度优先搜索
1 为输入节点构建一个单节点的树 // MAKE_SET
2 对每个子节点,递归调用该算法完成子树内所有查询,
    再将子节点的ancester指向本节点,归并结果树  // UNION
3 处理完所有子节点后,将本节点标为checked
4 遍历查询集中和该节点有关的查询,检查另一个节点是否已标为checked,如果是的话说明
     1) 该节点在本节点的子树
     2) 该节点和本节点在另一节点的子树中,而且该节点已被查询
     无论哪种情况,检查该节点所在树的根就是这两个节点的LCA节点
     如果没有标识checked,只需简单跳过,当遍历到该节点时就可以完成查询了

下面是java的实现代码和简单测试
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;
}

测试使用的树:

                                             0
                         +--------------+--------------------+
                          |                  |                          |
                         1                  2                        3
                  +-----+------+     +---+       +-------+---------+
                   |       |         |       |      |        |          |             |
                   4     5        6      7      8       9       10           11
            +---+               +              +          +--+------+   |
             |     |                 |              |            |               |   23
          12   13              14             15         16         17
                        +--------+                                +----+----+
                         |           |                                 |       |       |
                        18       19                               20   21   22


PS,差点忘了,祝lp生日快乐


posted @ 2008-01-07 23:15 白色天堂 阅读(2216) | 评论 (0)编辑 收藏
众所周知,java和c++不一样,在java中,对象只能用new操作符在heap中分配,不可以象c++一样在栈上分配。

一般来说,在堆上分配的效率要低于栈,。例如堆是全局的,在多线程程序中要使用锁来进行同步,不巧的是,绝大部分的java程序都是多线程的。另一方面,随着对象的生成和销毁,堆上会产生碎片,需要一个或多个freelist来维护,这样也造成额外的开销,以及空间利用的低效。

但这是一般c程序员理解的heap管理机制,也因此有c程序员指责java的内存管理效率低下。其实在jvm的实现中,它会用自己的方式来管理堆,增强java的效率。以Hotspot为例,每个线程都会拥有一段自己的空间称为TLAB(Thread Local Alloc Buffer),这块空间因为属于线程独有,所以在其中分配对象不需要加锁,其实和栈一样,分配对象只要将一个指针增加sizeof(object)即可。如果对象太大超出了tlab的剩余空间,此时有多种选择,
    在heap的share空间中分配,
    重新分配一块tlab
    在old generation中分配
    触发gc,释放已有空间。
具体选择何种方式由内存的利用情况和jvm的内存管理策略决定。由多个参数可以进行调整。所以在绝大部分情况下(〉90%),jvm中对象的分配和栈一样高效。

关于对象的释放,就是java中著名的gc来负责了,关于gc的介绍多如牛毛,而且其中的方式和策略层出不穷,这片文章就不介绍了。

从上面的介绍可以看出,这种方式可以加速对象的分配,但对释放不能作到象stack那样高效,其实有很多对象只是生存期很短的临时对象,如何识别这些对象并在tlab中更有效的释放应该是jvm可以进一步优化的方向。据我所知,jdk6的jvm已经使用了相关的技术。

posted @ 2007-10-01 23:10 白色天堂 阅读(471) | 评论 (0)编辑 收藏