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 白色天堂 閱讀(141) | 評論 (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 白色天堂 閱讀(193) | 評論 (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 白色天堂 閱讀(182) | 評論 (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 白色天堂 閱讀(612) | 評論 (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 白色天堂 閱讀(348) | 評論 (1)編輯 收藏
          代碼生成一般采用tree rewriting的方式,先將源代碼轉換成語法樹的形式,通過模式匹配將子樹替換成葉結點,同時生成代碼指令,當樹全部替換完后代碼即生成了。采用這種方式主要關心匹配規則,甚至可以使用lex/yacc之類的工具生成code generator generator,也便于實現可移植的編譯器。

          dynamic programing
          前面的算法如果只是從左往右依次匹配的話生成的代碼質量不高,DP就是要考慮指令的代價,生成質量較優的代碼。

          自底向上為每個節點計算一系列值存入數組C[],其中index代表使用的register數目,存儲的是相應的代價(要考慮可能增加的store/load指令代價),計算某個節點的C[]時,先找到可能的匹配模式,根據匹配模式選擇可能的寄存器數目組合,計算代價后選擇最小值。這樣遍歷整個樹后可以得到最小代價生成方式。



          posted @ 2008-05-07 05:14 白色天堂 閱讀(264) | 評論 (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 白色天堂 閱讀(2239) | 評論 (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 白色天堂 閱讀(482) | 評論 (0)編輯 收藏
          主站蜘蛛池模板: 耿马| 无为县| 恩平市| 郎溪县| 靖远县| 抚顺县| 巫溪县| 开江县| 利辛县| 永吉县| 大荔县| 九寨沟县| 清丰县| 阿拉善左旗| 会昌县| 巨鹿县| 安多县| 星子县| 泸西县| 海宁市| 贡嘎县| 南宫市| 秭归县| 金沙县| 乌兰察布市| 娄底市| 三都| 吉林省| 东山县| 布拖县| 谢通门县| 滦平县| 游戏| 泽库县| 永胜县| 广安市| 丽水市| 南汇区| 滦南县| 六枝特区| 垦利县|