posts - 12,comments - 1,trackbacks - 0
          看understanding linux kernel的一點筆記:
          頁表
          通常32位cpu使用2級頁表機制就已足夠,但到64位時代,2級頁表會使頁表的項急劇增加,所以通常會使用更多的頁表級數(shù)。
          ia64/ppc64/alpha使用3級頁表,x86_64使用到4級頁表。為兼容這些模型,2.6.11之后使用了統(tǒng)一的4級頁表模型
          Global Directory
          Upper Directory
          Middle Directory
          Page Table
          針對不同的架構(gòu),設(shè)置每一級不同的地址位數(shù),0的話就是不使用這一級頁表機制。

          cache
          多cpu環(huán)境中,每個cpu有自己的cache,對cache的更新有硬件機制保證通知其他的cpu進行同步。(真的嗎?)

          tlb
          用來cache頁表,加速地址的轉(zhuǎn)換速度。每個cpu有自己的tlb,但不需要同步,因為地址轉(zhuǎn)換和進程相關(guān)。

          posted @ 2008-11-01 08:27 白色天堂 閱讀(141) | 評論 (0)編輯 收藏
          LinuxThreads:
            舊的pthread實現(xiàn),基于process實現(xiàn)pthread。主要問題是signal不符合規(guī)范,stack size固定???

          NPTL:
            2.6后加入的新實現(xiàn),redhat as中2.4就可以支持。更符合pthread的規(guī)范。用戶線程和內(nèi)核線程采取1:1模式,支持floating stack。

          posted @ 2008-09-09 22:56 白色天堂 閱讀(192) | 評論 (0)編輯 收藏
          今天花了一點時間作了個x86上hotspot vm的disassembler,這樣可以看出jvm生成的本地代碼了。
          代碼比較簡單,主要是用了udis86的庫,這個可以在sf上下載到,它的接口還是比較簡單的。

          簡單的例子,hotspot解析模式中iconst_0的對應(yīng)匯編代碼:
          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,比較容易理解它的用處。它天生就是為實現(xiàn)cache來設(shè)計的。關(guān)于weak reference,好像很少有人說的清楚。有的和soft reference混在一起談,有的就是簡單翻譯java doc中的說明,看得出翻譯的人自己也不是很理解,所以只能一筆帶過。

          我也一直不是很清楚它的實際用途,今天我突然想到WeakReference可能的設(shè)計目的。

          從java的內(nèi)存泄漏說起,以前說到j(luò)ava也會內(nèi)存泄漏的時候往往會舉這樣的例子,對象保存在一個全局表中,造成無法回收。一般的解決方法是不要使用全局表或者記得更新。但在實際開發(fā)中,有時必須要使用全局表,但無法明確知道該對象是否可銷毀,因為對象可能被多個線程共享訪問,所以程序不能確切的更新表中的引用。這時候weak reference就有用武之地,用WeakHashMap構(gòu)造全局表,key和value之間是weak reference,這樣的話程序員就不用考慮更新該表了,只要該對象沒有強引用指向它,gc就可以回收它了。

          回頭去找一個實際的例子對照看看,記得在JDK中,weak reference還是用的很頻繁的。

          posted @ 2008-07-25 22:51 白色天堂 閱讀(612) | 評論 (0)編輯 收藏
          以前用redhat的時候使用rpm管理軟件包,因為不能解決軟件的依賴關(guān)系后來轉(zhuǎn)到debian。apt確實方便了很多,但一直懷念rpm的一個功能,rpm可以查詢一個文件具體屬于哪個包,用apt一直沒有找到對應(yīng)的命令。
          今天想在64位ubuntu上編譯32位程序的時候發(fā)現(xiàn)沒有/usr/include/gnu/stub-32.h,在網(wǎng)上搜索時突然發(fā)現(xiàn)apt也可以根據(jù)文件來搜索包。命令是apt-file(缺省是沒有安裝的)。
          先安裝apt-file
          使用apt-file update同步安裝包內(nèi)部的文件,它會到你定義的source去獲取這些信息,運行會比較慢,而且沒有什么提示,不知道今后會不會都是這樣。
          然后就可以用apt-file find xxx 去查詢了。


          -每天進步一點點, :)

          posted @ 2008-05-21 23:04 白色天堂 閱讀(347) | 評論 (1)編輯 收藏
          代碼生成一般采用tree rewriting的方式,先將源代碼轉(zhuǎn)換成語法樹的形式,通過模式匹配將子樹替換成葉結(jié)點,同時生成代碼指令,當樹全部替換完后代碼即生成了。采用這種方式主要關(guān)心匹配規(guī)則,甚至可以使用lex/yacc之類的工具生成code generator generator,也便于實現(xiàn)可移植的編譯器。

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

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



          posted @ 2008-05-07 05:14 白色天堂 閱讀(264) | 評論 (0)編輯 收藏
          最近看代碼時看到Tarjan算法,搜索了一下,是個經(jīng)典的求LCA(Least Common Ancestor)算法。奇怪的是,網(wǎng)上一般的介紹只會給出偽碼,而且有關(guān)集合的實現(xiàn)都沒有。為理解它還想了半天。目前有些細節(jié)還沒有完全想清楚(主要和wikipedia上給出的偽碼實現(xiàn)并不完全一致),但根據(jù)我的理解,我的實現(xiàn)應(yīng)該是可以完成功能。
          基本描述:
             本身是一個從根開始的深度優(yōu)先搜索
          1 為輸入節(jié)點構(gòu)建一個單節(jié)點的樹 // MAKE_SET
          2 對每個子節(jié)點,遞歸調(diào)用該算法完成子樹內(nèi)所有查詢,
              再將子節(jié)點的ancester指向本節(jié)點,歸并結(jié)果樹  // UNION
          3 處理完所有子節(jié)點后,將本節(jié)點標為checked
          4 遍歷查詢集中和該節(jié)點有關(guān)的查詢,檢查另一個節(jié)點是否已標為checked,如果是的話說明
               1) 該節(jié)點在本節(jié)點的子樹
               2) 該節(jié)點和本節(jié)點在另一節(jié)點的子樹中,而且該節(jié)點已被查詢
               無論哪種情況,檢查該節(jié)點所在樹的根就是這兩個節(jié)點的LCA節(jié)點
               如果沒有標識checked,只需簡單跳過,當遍歷到該節(jié)點時就可以完成查詢了

          下面是java的實現(xiàn)代碼和簡單測試
          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程序都是多線程的。另一方面,隨著對象的生成和銷毀,堆上會產(chǎn)生碎片,需要一個或多個freelist來維護,這樣也造成額外的開銷,以及空間利用的低效。

          但這是一般c程序員理解的heap管理機制,也因此有c程序員指責(zé)java的內(nèi)存管理效率低下。其實在jvm的實現(xiàn)中,它會用自己的方式來管理堆,增強java的效率。以Hotspot為例,每個線程都會擁有一段自己的空間稱為TLAB(Thread Local Alloc Buffer),這塊空間因為屬于線程獨有,所以在其中分配對象不需要加鎖,其實和棧一樣,分配對象只要將一個指針增加sizeof(object)即可。如果對象太大超出了tlab的剩余空間,此時有多種選擇,
              在heap的share空間中分配,
              重新分配一塊tlab
              在old generation中分配
              觸發(fā)gc,釋放已有空間。
          具體選擇何種方式由內(nèi)存的利用情況和jvm的內(nèi)存管理策略決定。由多個參數(shù)可以進行調(diào)整。所以在絕大部分情況下(〉90%),jvm中對象的分配和棧一樣高效。

          關(guān)于對象的釋放,就是java中著名的gc來負責(zé)了,關(guān)于gc的介紹多如牛毛,而且其中的方式和策略層出不窮,這片文章就不介紹了。

          從上面的介紹可以看出,這種方式可以加速對象的分配,但對釋放不能作到象stack那樣高效,其實有很多對象只是生存期很短的臨時對象,如何識別這些對象并在tlab中更有效的釋放應(yīng)該是jvm可以進一步優(yōu)化的方向。據(jù)我所知,jdk6的jvm已經(jīng)使用了相關(guān)的技術(shù)。

          posted @ 2007-10-01 23:10 白色天堂 閱讀(482) | 評論 (0)編輯 收藏
          主站蜘蛛池模板: 五台县| 托里县| 和顺县| 读书| 长顺县| 吕梁市| 原平市| 昆山市| 临江市| 宁武县| 香河县| 呼伦贝尔市| 舟曲县| 河源市| 辰溪县| 遂川县| 西丰县| 泽普县| 宾阳县| 莲花县| 景东| 广昌县| 临夏县| 无为县| 亚东县| 万安县| 广河县| 平江县| 墨脱县| 松原市| 广丰县| 寿光市| 当雄县| 华宁县| 墨玉县| 旺苍县| 肇庆市| 南丰县| 江阴市| 丹东市| 搜索|