20100525

如果你不是真心，就不要闯进我的世界

下午2:51:00

我可以
一个人吃饭；
一个人睡觉；
一个人逛街；
一个人游戏；
一个人上班；
一个人回家；
一个人发呆；
一个人思考；
一个人欣赏路过的风景；
一个人遗憾错过的精彩；
一个人读着别人的故事；
一个人打发无聊的时间；
一个人赶走寂寞的侵袭；
一个人抵挡北风的严寒；
一个人在跌倒后站起来拍拍身上的灰尘；
一个人在受伤后躲起来默默治疗心的创伤；
一个人在繁华的都市里找回迷失的自己；
一个人在残酷的现实里伪装保护着自己...............

所以

如果你不是真心，就不要轻易插足我的旅程，我很容易感动，很容易满足，也许你不经意对我的好我都会一直记得，也许会因为你不在意的举动会伤心很久；

如果你不是真心，就不要轻易进入我的世界，我不会坚强，不会防备，你说的每句话我都会相信，我能给你的就是绝对的信任；

如果你不是真心，就不要轻易跨进我的国度，我会固执，会小气，
我很珍惜每个进来的人，就算碰得头破血流我也不会轻易放手，我不想留给自己太多遗憾...... 等待那个人我投入的会是我全部的真心

20100521

自書遺囑範例

晚上8:04:00

自書遺囑範例

遺囑

立遺囑人○○，民國○○年○月○日生，○○市人，身分證字號○○○，茲依民法之規定，自書遺囑內容如后：

一、不動產部份

(一)座落於○○市○○區○○段○○地號土地及地上建物〈門牌號碼○○○○〉○樓住宅，所有持分由配偶○○單獨全部繼承。

(二)座落於○○市○○區○○段○○地號土地，面積○○平方公尺，所有持分由長子○○〈民國○○年○月○日生，○○市人，身分證字號○○○〉單獨全部繼承。

二、動產部份

(一)本人所有股票及名下汽車由長女○○〈民國○○年○月○日生，○○市人，身分證字號○○○〉單獨全部繼承。

(二)銀行存款及其他一切財產，由全體繼承人平均繼承。

三、本人指定地政士曹慶好(Z100026159)為遺囑執行人。

四、俗話說風吹雞蛋殼財去人安樂，希望子女們不要為身外之物起爭執，要善盡孝道做一個有用的人。

(遺囑內容要全程親自書寫)

立遺囑人：○○○〈一定要親自簽名，不能只蓋印鑑或倷指印〉

中華民國○○年○月○日(日期一定要有且也須親自書寫)

[不知死，焉知生] 預立遺囑讓你今生不留遺憾

晚上7:59:00

[不知死，焉知生] 預立遺囑讓你今生不留遺憾

李進成律師

我國已邁入老年化社會，年老除安享退休生活外，對身後財產之分配若能事先規畫，不僅可免子女紛爭於身後，亦可對子女有教示或表彰之功用。在我們無法避免年老之到來，如能對生平所願作一交代，這樣就可以更了無牽掛、康健而耐老的享受年老生活。所以今天我們來談遺囑的重要法律規定。

壹．遺囑方式之種類
自書遺囑、公證遺囑、密封遺囑、代筆遺囑、口授遺囑（民法第1189條）。
除上述五種方式外，其他方式之遺囑，法律上不承認其效力。故遺囑應注意其要式性。
茲將上述五種遺囑之方式及利弊得失，簡單說明如後：

一、自書遺囑：遺囑人親筆自書之遺囑
◎方式：
依民法第1190條之規定「自書遺囑者，應自書遺囑全文記明年月日，並親自簽名。如有增減、塗改，應註明增減塗改之處所及字數，另行簽名。」故自書遺囑須具備由遺囑人自己書寫遺囑全文（不可以打字方式或請別人代寫），且應記明寫完本文之年月日，並須親自簽名等三要件，否則無效。又於書寫時，難免有筆誤或變更內容的情形，在這種情形，須註明增減塗改之處所及字數，並簽名。
◎利弊得失：
利：可秘密為之（因不須有見證人），又可節省費用。
弊：其方式太過簡單，一般人常因缺乏法律智識，致內容有矛盾、曖昧或不適法之情形，或
......因方式（例如以打字方式）不完備而無效；且因無見證人，易發生偽造或變造之情形。

二、公證遺囑：遺囑人於公證人面前所作成之遺囑
◎方式：
依第1191條規定「公證遺囑，應指定二人以上之見證人，在公證人前口述遺囑意旨，由公證人筆記、宣讀、講解，經遺囑人認可後，記明年月日，由公證人、見證人及遺囑人同行簽名。遺囑人不能簽名者，由公證人將其事由記明，使按指印代之。前項所定公證人之職務，在無公證人之地，得由法院書記官行之，僑民在中華民國領事駐在地為遺囑時，得由領事行之。」故其方式為：
1.須指定二人以上之見證人。須由遺囑人指定二人以上，非未成年人、禁治產人、繼承人及
...其配偶或直系血親、受遺贈及其配偶或直系血親，或公證人或代行證人職務人之同居人、
...助理人或受僱人為見證人。又該見證人須自口述至完成時在場見證，無二人以上之見證，
...無見證人資格之人為見證人，或見證人不自開始口述迄自完成時在場見證，其所作之遺囑
...均屬無效。
2.須在公證人前口述遺囑意旨。應由遺囑人直接以言語向公證人為之，不得由他人代為轉達
... ，亦不得以其他舉動表達，故不能口述者（啞者或有言語障礙者），不能為公證遺囑。
... 由公證人筆記、宣讀、講解：筆記如有錯誤，遺囑人得請求更正之；宣讀亦可由第三人
... ，在見證人面前為之。須經遺囑人認可後，記明年月日，由公證人、見證人及遺囑人同
... 行簽名。
◎利弊得失：
利：文盲或不熟習法律之人，得藉以訂立遺囑，且就內容之真實以及證據力而言，遠勝自書
......遺囑。
弊：不如自書遺囑可以嚴守秘密，且關於費用及作成之便利，均屬短處。

三、密封遺囑：遺囑人將其秘密作成之遺囑，加以密封後，於見證人之會同之下，提經公證人證明之遺囑
◎方式：
自書遺囑若要更慎重，可以以密封遺囑之方式為之。依民法第1192條規定「密封遺囑，應於遺囑上簽名後將其密封，於封縫處簽名，指定二人以上之見證人，向公證人提出，陳述其為自己之遺囑，如非本人自寫並陳述繕寫人之姓名、住所，由公證人於封面記明遺囑提出之年、月、日及遺囑人所為之陳述，與遺囑人及見證人同行簽名。」前條第二項之規定，於前項情形準用之。是其方式為：
1.須遺囑人於遺囑上簽名。密封遺囑不必遺囑人自書，他人代筆亦可，但必須遺囑人於遺囑
...上簽名。
2.須遺囑人密封之，並於封縫處簽名。為保守秘密，防止他人啟視，以免有偽造或變造而設
... 。
3.須遺囑人指定二人以上之見證人，向公證人提出，陳述其為自己之遺囑，如非本人自寫，
...並陳述繕寫人之姓名、住所。所謂陳述，僅說明該遺囑確係自己所作者而已，不必涉及遺
...囑之內容。
4.須公證人於封面記明遺囑提出之年、月、日及遺囑人所為之陳述。
5.公證人與遺囑人及見證人同行簽名。
如不具備前述方式，而具備自書遺囑之方式者，有自書遺囑之效力。
◎利弊得失：
利：因有見證人及公證人之證明，較為確實，而其內容又可保守秘密，似兼有自書遺囑及公
......證遺囑之所長，且自己能簽名者，可不必自書，得使代筆人作成遺囑。
弊：自書之密封遺囑，則仍有如自書遺囑之缺點。

四、代筆遺囑：即由他人代筆之遺囑
◎方式：
第1194條規定「代筆遺囑，由遺囑人指定三人以上之見證人，由遺囑人口述遺囑意旨，使見證人之一人筆記、宣讀、講解，經遺囑人認可後，記明年月日，及代筆人之姓名，由見證人全體及遺囑人同行簽名，遺囑人不能簽名者，應按指印代之。」
故其方式為：
1.由遺囑人指定三人以上之見證人，由遺囑人口述遺囑意旨，使見證人之一人筆記、宣讀、
...講解，經遺囑人認可後，記明年月日，及代筆人之姓名：代筆人得為見證人之一。
2.由見證人全體及遺囑人同行簽名，遺囑人不能簽名者，應按指印代之。
◎利弊得失：
利：無法書寫者，簡便易行。
弊：因非由公證人作成，見證人尤其代筆見證人，可能左右遺囑人之意思。

五、口授遺囑：此乃遺囑人生命危急時，以緊急方式所為之遺囑
◎方式：
第1195條規定「遺囑人因生命危急或其他特殊情形，不能依其他方式為遺囑者，得依左列方式之一為口授遺囑：由遺囑人指定二人上之見證人，並口授遺囑意旨，由見證人中之一人，將該遺囑意旨，據實作成筆記，並記明年、月、日，與其他見證人同行簽名。由遺囑人指定二人以上之見證人，並口述遺囑意旨、遺囑人姓名及年、月、日，由見證人全體口述遺囑之為真正及見證人姓名，全部予以錄音，將錄音帶當場密封，並記明年、月、日，由見證人全體在封縫處同行簽名。」
由上可知口授遺囑之緊急性。又倘日後立遺囑人又康復，此時依第1196條規定「口授遺囑，自遺囑人能依其他方式為遺囑之時起，經過三個月而失其效力。」即口授遺囑，有效期間三個月經過，即喪失效力。再者，口授遺囑，須於為遺囑人死亡後三個月內，經親屬會議認定其真偽，故非不得已應儘量少用口授遺囑之方式，因其爭議性較大。
◎利弊得失：
利：因應緊急或特殊情形，方式簡單。
弊：成立出於倉促，方式又簡略，難以確保遺囑人之真意及遺囑之公正確實。

貳．遺囑之限制
遺囑人生前將其財產全部處分本即其個人自由，惟倘不生前處分，要以遺囑方式為之，應注意「遺囑人於不違反關於特留分規定之範圍內，得以遺囑自由處分遺產。」之規定，倘剝奪某繼承人之應繼分，日後該繼承人可以訴訟的方式主張在其特留分之範圍內仍有效。所稱特留分乃規定在第1223條「繼承人之特留分，依下列各款之規定：直系血親卑親屬之特留分，為其應繼分二分之一。父母之特留分，為其應繼分二分之一。配偶之特留分，為其應繼分二分之一。兄弟姊妹之特留分，為其應繼分三分之一。袓父母之特留分，為其應繼分三分之一。」

參．遺囑之生效及撤回
遺囑自遺囑人死亡時發生效力。故立遺囑後非立即生效，乃可以撤回，其方式有：
1. 遺囑人得隨時依遺囑之方式，撤回遺囑之全部或一部。
2. 前後遺囑有相牴觸之部分，前遺囑視為撤回。
3. 遺囑人於為遺囑後所為之行為與遺囑有相牴觸者，其牴觸部分，遺囑視為撤回。
4. 遺囑人故意破毀或塗銷遺囑，或在遺囑上記明廢棄之意思，其遺囑視為撤回。

20100519

台股股市操作行事曆

晚上9:13:00

台股股市操作行事曆

1月：	可買進	年初資金充沛
2月：	可買進	農曆過年，紅包行情，醞釀董監事改選行情
3月：	可賣出	達停利點就賣出
4月：	宜賣出	股東會行情，股東回補股票
5月：	不操作	窮，電子淡季、大股東賣股報稅
6月：	不操作	絕，電子淡季
7月：	不建議操作	除權/除息旺季，外資放暑假、增資股陸續上市，通常會量縮整理
8月：	不建議操作	除權/除息旺季，外資放暑假、增資股陸續上市，通常會量縮整理
9月：	可小量買進	電子旺季，但須擇優布局，留意中秋變盤
10月：	可買進、賣出	財報已明朗，擇優布局
11月：	可買進、賣出
12月：	可買進、賣出

20100518

How do I add a warning Logon message?

下午5:09:00

How do I add a warning Logon message?

John Savill

Windows IT Pro

InstantDoc ID #14878

A. You need to use the registry editor

Start the registry editor (regedit)
Move to HKEY_LOCAL_MACHINE/SOFTWARE/Microsoft/Windows NT/CurrentVersion/Winlogon
Double Click the "LegalNoticeCaption", and enter the text to be in the title bar, click OK
Double Click the "LegalNoticeText", and enter the warning text and click OK
Close the registry and logoff, when you logon you will see the warning

In Windows 2000 step 2 would be to move to HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\policies\system instead.

This can also be done via the policy editor (poledit.exe) for NT 4.0

Start the policy editor (poledit.exe)
Open the default Computer Policy
Open the Windows NT System tree and then Logon
Put a tick in the "Logon banner" and enter the caption and text
Click OK and save the policy

For Windows 2000 Group Policy Objects move to Computer Configuration - Windows Settings - Security Settings - Local Policies - Security Options and set the 'Message text for users attempting to log on' and 'Message title for users attempting to log on'.

Alternatively, a text message can be displayed by creating the key LogonPrompt in HKEY_LOCAL_MACHINE/SOFTWARE/Microsoft/Windows NT/CurrentVersion/Winlogon

Windows Scripting Host can also be used to create these messages as follows:

<font class="10v" color="#000000" face="Arial, Helvetica, VERDANA" size="3">Set WSHShell = CreateObject("WScript.Shell") s1 = "HKLM\Software\Microsoft\Windows\CurrentVersion\WinLogon\" s2 = "LegalNoticeCaption" s3 = "LegalNoticeText" objShell.RegWrite s1+s2, "SavillTech Ltd" objShell.RegWrite s1+s3, "Only Authorized Access Allowed!"</font>

Rate It:

20100517

聯徵知識

凌晨1:12:00

聯徵知識

　　銀行在調閱當事人的信用資料其最主要的目的是要了解當事人之債、信部分有無異常或信用擴張等狀況!

Ａ．債：與金融機構借貸情形(個人主債務+保證債務) ,例如信用卡現金卡貸款 !
其中負債比過高也會影響信用評分。

Ｂ．信: 繳款是否正常,有無不良信用紀錄!等等。

　　聯徵中心都使用所謂的信用評分機制,來針對當事人債信部分作評分，會影響信用評分的高低除了債信部分之外, 還包含當事人近期被查詢的紀錄就是人家所謂的拉聯徵，所謂近期查詢指的是: 最近三個月(不包含查詢當日) 被金融機構查詢聯徵的次數;只要超過三次, 短期內就無法辦理消費金融商品!對銀行來說當事人近期聯徵次數過高 ,有信用擴張或資金需求甚多的情形,在徵審上都會被扣很多分數!

而有可能被拉聯徵的可能性大多為：

Ａ．銀行方面

一、你曾在該銀行有使用他們的信用卡、現金卡、信貸、房貸、開戶、各種金融商品。

二、你要申辦新的各種金融商品。

Ｂ．一般情形申請聯徵應提出下列證明：

一、客戶的身份證（有些銀行需要另附第二證件）影印本
二、客戶的申請書（需客戶親筆簽名，不需正本，傳真也可）
三、客戶的同意（某些銀行在拉聯徵之時會照會本人，本人同意才會動作）

在這三個要件都成立前提之下才可以拉聯徵，而有些銀行也要求再附上進件資料（工作證明、收入證明）才可拉聯徵。

Ｃ．銀行不正常調閱情況：業務未經客戶之同意，調閱其聯徵。發生些狀況之原因有二：

一、如某家知名代辦公司將客戶資料亂送，多家查訊，是在客戶不知情之下。導致客戶聯徵過多（六或七家以上算過多），需等三個月之後調閱次數註消後，才可再申請。（為假設性請勿對號入座）
二、如某家銀行行員，試著互送他家銀行業務，試圖用他家銀行來申辦銀行商品，這情況比較少見。

目前聯徵中心已開放個人查詢聯徵紀錄,相關查詢的方式你可以上聯徵中心網站查看!

網址如下http://www.jcic.org.tw/index.htm

以下是個人查詢聯徵紀錄的總表項目:

1.台瑞在國內金融機構借款情形: 貸款類別剩餘金額逾期金額
2.台瑞在近三年有無逾期催收或近五年有無呆帳紀錄: 主債務部份( 貸款現金卡)等
3.保證債務: 若有擔任保證人在這項目中就會秀出, 若有逾期狀況也會秀出!
4.票據資訊: 台最在近三年有無跳票紀錄近五年有無拒往紀錄
5.信用卡資訊: 台瑞近五年信用卡持用情形: 申辦銀行以及使用情形(有無強停紀錄一般停卡)
6.台瑞近一年信用卡使用狀況: 主要秀出發卡銀行額度預借現金金額循環利息以及有無遲繳狀況
7.台瑞近三各月被國內金融機構查詢次數以及查詢理由( 若自調閱也會秀出,但不影響聯徵次數)
8.台瑞加註訊息:
9. 信用評分以及百分比區位: 此欄位是以聯徵中心評分機制為主, 基本上信用評分最低是200分最高是860分!( 若沒有往來紀錄則是不予評分)

上開為個人調閱聯徵紀錄的簡介, 而銀行調閱的會更詳細!

補充說明：（法令規定）

(一)聯徵記錄留多久？債務清除後紀錄就會消失

　　聯徵中心根據電腦處理個人資料保護法第21條規定，並依據金管會規定，個人資料紀錄期間為，逾期、催收紀錄，自清償日起揭露三年；呆帳紀錄，自轉銷日起揭露五年；退票紀錄三年，拒絕往來紀錄自通報日起揭露三年。

　　但對退票已清償並辦妥註記的人，自辦妥清償註記日起揭露六個月；拒絕往來提前解除者，自拒絕往來提前解除之日起揭露六個月。

　　其實註記的時間不會很長，而且通常都是在信用不良期間，且多半在3~5年之間，若提早清償債務，註記時間更只會有半年而已，對於有心清償債務，以及珍惜自己信譽的人，其實很輕易就可以從紀錄上消失。

　　而信用卡資料，自停卡之日起揭露五年，但是有強制停卡行為，且未清償則是揭露七年，不正常繳款資料自繳款截止日起揭露一年。反而是信用卡不良紀錄會保留較久，因此在使用信用卡時需要更注意小心。至於最近許多人熱烈討論的破產問題，聯徵中心則是規定，破產宣告紀錄自宣告日起揭露十年。

　　至於許多人關注的，加入卡債協商後，這個資料會留多久，而根據聯徵中心的表示，卡債協商只是在當事人信用紀錄上備註，表示這個人有加入債權協商，適用於「其他資料之揭露至特定目的消失為止」，當協商結束時，這個註記也就消失了。

　　聯徵中心也一再表示，聯徵中心只是一個資料庫，是根據各銀行送達的資料作處理，只是提供銀行個人信用資料交換。因此，並無權更改任何信用資料。另外，當不良信用資料未出現在個人信用資料時，其實並不代表銀行就看不到這些資料，銀行還是可以進入資料庫中調閱個人過去的信用資料，因此善加保護個人信用紀錄，才是最重要的事。

(二)個人信用如何評？聯徵中心有一套評比項目五大類！繳款負債信用卡含在內

　　自從聯徵中心推出個人信用評等後，許多人都把它當作能否跟銀行順利借錢、辦信用卡的指標，銀行的確也會依據聯徵中心提供的數據，做為是否貸款及核發信用卡的參考值，雖然不是百分之百由個人信評決定，但是卻有指標性意義。因此，處理個人信用問題時，的確不能不小心。

　　聯徵中心將個人信用評分，區分為「不予評分者」、「給予固定評分者」、「實際評分者」三大類。不予評分者主要原因是，非本國籍、未成年或是銀行之間無往來紀錄，或是異常情形。例如在訴訟中或是已經宣告破產的人；給予固定評分者則是有信用問題，但是仍處於正常信用交易的人，其他就列為實際評分者。

　　據聯徵中心表示，信用評等計算方式，是一套由聯徵中心研究的複雜計算公式。算出的結果，會以數據呈現，絕大部分數字會介於200分至860分之間。除了數字本身代表個人信用好壞之外，該數值與其他人相比較位置區間。也是參考依據。例如，某人評分數字在整體評估人中的區間為70%~80%，即代表這個分數優於70%~80%的所有評分樣本，也是透過種種比較，讓銀行了解此人實際的信用狀況。

　　而聯徵中心列入評比的信用項目，包括五大類：繳款行為類、負債類、新信用申請類、信用長度類、信用型態類。其中信用長度類是指，個人使用信用的歷史長短，例如信用卡有效卡開卡距今月份數資料；信用型態類則是指使用信用型態及其組合，例如房貸戶、信用卡循環信用使用者、現金卡戶等。

　　信用對一個人非常重要，尤其是當要辦信用卡或是貸款買房子、做生意時，但是聯徵中心也不是完全不會出錯，聯徵中心已經開放個人查詢自己的信用狀況，也建議每個人一年調閱一次自己的信用紀錄，看看有無錯誤，保護好自己的信用。

(三)為信用加分的七大要訣

(1)最重要的當然就是繳款行為
(2)選擇2~3家銀行做長期的往來
(3)千萬不要為了贈品而拼命辦卡
(4)隨時留意自己的負債比
(5)存款集中在一家銀行
(6)增加自己的資產明細
(7)每年固定向聯徵中心申請自己的信用報告

20100513

让bsodhook检查任意hook

晚上8:54:00

让bsodhook检查任意hook

BSODHOOK非要开个驱动检查SHADOW TABLE和ssdt table
没有HOOK的就不让检查，于是写了个驱动让他能检查任意SSDT/SHADOW HOOK~
先打开bsodhook,load driver,再加载这个驱动即可

要检查的HOOK ID请在need_check_ssdt_id 和need_check_shadow_id里填写~
已测试版本 2.0.0.0

代码：
=================================

#include "ntddk.h"
#include "stdafx.h"
#include "zwfunc.h"
#include "ntifs_48.h"

ULONG oldBsodHookDevCtl ;
ULONG need_check_ssdt_id[] = {0x1 , 0xffffffff};

ULONG need_check_shadow_id[] = {0x1001,0xffffffff };

NTSTATUS NewBsodHookDevCtl(PDEVICE_OBJECT devobj , PIRP irp)
{
NTSTATUS stat ;
PIO_STACK_LOCATION irpstack = IoGetCurrentIrpStackLocation(irp);
ULONG iocontrolcode = irpstack->Parameters.DeviceIoControl.IoControlCode;
PVOID userbuffer = irp->UserBuffer;
ULONG len = irpstack->Parameters.DeviceIoControl.InputBufferLength ;

__asm
{
push irp
push devobj
call oldBsodHookDevCtl
mov stat ,eax
}

if (!NT_SUCCESS(stat))
{
return stat ;
}

//irp 已经完成了~

//这里是get ssdt
if (iocontrolcode == 0xB50D800B)
{
__try
{
ULONG i = 0 ;
while(need_check_ssdt_id[i] != 0xffffffff)
{
*(ULONG*)((ULONG)userbuffer + need_check_ssdt_id[i] * 4 + 4 ) = 0xffffffff;
i++;
}

}
__except(EXCEPTION_EXECUTE_HANDLER)
{
return stat ;
}
}
//这里是get shadow ssdt
else if (iocontrolcode == 0xB50D800F)
{
__try
{
ULONG i = 0 ;
while(need_check_shadow_id[i] != 0xffffffff)
{
*(ULONG*)((ULONG)userbuffer + (need_check_shadow_id[i] - 0x1000) * 4 + 4) = 0xffffffff;
i++;
}

}
__except(EXCEPTION_EXECUTE_HANDLER)
{
return stat ;
}
}

return stat ;

}
NTSTATUS DriverEntry( IN PDRIVER_OBJECT pDriverObject, IN PUNICODE_STRING pRegistry )
{
UNICODE_STRING Name ;
PDRIVER_OBJECT DriverObject ;
NTSTATUS stat ;

RtlInitUnicodeString(&Name , L"\\Driver\\BSODhook");

stat = ObReferenceObjectByName(&Name ,
OBJ_CASE_INSENSITIVE,
NULL,
0,
*IoDriverObjectType ,
KernelMode ,
NULL,
&DriverObject
);

if (!NT_SUCCESS(stat))
{
return STATUS_UNSUCCESSFUL ;
}

oldBsodHookDevCtl = DriverObject->MajorFunction[IRP_MJ_DEVICE_CONTROL];
InterlockedExchangePointer(&DriverObject->MajorFunction[IRP_MJ_DEVICE_CONTROL] , NewBsodHookDevCtl);

ObfDereferenceObject(DriverObject);

return STATUS_SUCCESS ;

20100511

Implementing thread-safe unordered sets without reducers

晚上11:42:00

http://software.intel.com/en-us/articles/Implementing-thread-safe-unordered-sets-without-reducers/

Implementing thread-safe unordered sets without reducers

Submit New Article

Published On :	October 29, 2009 12:00 AM PDT
Rate Please login to rate! Current Score: 0 out of 0 users Please login to rate! Current Score: 0 out of 0 users Please login to rate! Current Score: 0 out of 0 users Please login to rate! Current Score: 0 out of 0 users Please login to rate! Current Score: 0 out of 0 users

by Alex Zatsman

Races and Reducers: the Risks and Rewards

One of the biggest challenges in building a parallel program is dealing with data races. Cilk++ offers several tools and techniques to find and eliminate races from your program. Reducers provide a a powerful mechanism for eliminating races, but as Spiderman said, "with great power comes great responsibility."

The Problem

I recently looked at a customer problem that at first looked like an obvious application for reducers. Briefly, the task was to sort a collection of objects into separate bins based on certain properties of the objects. The simplest parallel implementation, converting the for loop to a cilk_for loop, introduces data races on the bins if two or more objects can be put into the same bin.

At first look, this seemed like a good opportunity to use reducers. The contents of each bin is a list of elements, so why not just have each bin hold a list reducer? Reducers are extremely efficient when used sparingly, but unfortunately can become expensive if you create thousands or even millions of reducers, as would be needed in this case.

The other safe approach to handling races is to use locks to protect access to the shared memory locations. In this case, that would either mean using a single lock to protect the entire collection (safe, but bad because the high contention on this lock would eliminate all advantages of parallelism) or to create and acquire a lock for each bin (also safe, but bad because it requires thousands or millions of expensive locks.)

Luckily, there is another way.

The Approach

Mutex locks provided by the operating system are expensive to create and acquire, and are generally more heavy weight than is required for this problem. However, there is a much lower-cost alternative. The underlying hardware offers atomic instructions, which are effectively locks around single hardware instructions. These are the same instructions that are used to implement mutexes, but we can use them directly to save a significant amount of overhead for our problem at hand. It is important to note that there is no free lunch - atomic instructions require a memory barrier that can cost 40 or more instruction cycles. This is far more expensive than the few cycles used by an unlocked read/write, but still much less than the thousands required to create and acquire mutexes. You can think of these as small locks that lock just the read/write hardware operation to ensure that no other processor can race on the memory between the read and the write.

My approach is to use the atomic instruction to safely update the bins in a way that will not create data races. As with any use of locks, this approach prevents data races, but does not guarantee a deterministic result. In this case, each bin will hold the correct list of elements, but the order of the elements in the list is indeterminate.

The Solution

An atomic swap operation for pointers is available under different names in both Gnu and Windows C/C++ compilers:

GNU:	`__sync_lock_test_and_set`
MSVC:	`InterlockedExchangePointer`

An implementation of a thread-safe sets can be implemented as a template with the class C of the set element as the template parameter:

#ifdef __GNUC__
#include
#define AtomicSwap(A,X) __sync_lock_test_and_set (A, X)

[How to solve the linking errors when using the ATOMIC functions?]

晚上11:34:00

[How to solve the linking errors when using the ATOMIC functions?]

When some new atomic functions of GCC are used in the i386 platform, the linking errors maybe take place. It takes me troubles in some time even if I have updated GCC to the latest version (GCC-4.3.3). Herein, I will give my solution to overcome it, and share the experience with you in the Linux OS.