看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) |
編輯 收藏