Java Volatile

在 Java 多執行緒的環境中 synchronized 是相當常用的關鍵字之一,使用 synchronized 有兩個效果 mutex & visibility
mutex 主要目的是建立 critical section, 而 visibility 的作用是保持記憶體的一致性(memory consistency)

什麼是記憶體一致性呢? 我們知道一般物件是擺在記憶體內的,如果要對物件資料做運算,CPU 通常會將要做運算的資料複製一份到 CPU 的 register 加快處理速度,而運算完的資料有時並不會立刻寫回主記憶體,而是留在 register 內,在多執行緒的環境下,如果此時另一個 CPU 來讀取同一份資料就會產生記憶體不一致的問題,因此 Java 定義了 volatile 關鍵字來處理記憶體資料一致性的問題

Java Language Specification 對 volatile 的定義

• A field may be declared volatile, in which case the Java Memory Model ensures that all threads see a consistent value for the variable
• A write to a volatile field happens-before every subsequent read of that field

Java Specification 裡只定義規範, 也就是使用 volatile 之後可保證所有的 threads 看到變數的值是一致的,並沒有硬性規定如何實作,給了實作 JVM 彈性,因此實作的方式可能有很多種,譬如說如果使用 volatile 關鍵字的變數就不可對變數使用 cache memory,直接對主記憶體資料作讀寫,這也是一種方式,當然實際實作可能沒那麼簡單

引用 Java Concurrency in Practice 的範例

public class NoVisibility {
    private static boolean ready;
    private static int number;

    private static class ReaderThread extends Thread {
        public void run() {
            while (!ready)
                Thread.yield();
            System.out.println(number);
        }
    }

    public static void main(String[] args) {
        new ReaderThread().start();
        number = 42;
        ready = true;
    }
}

這個例子沒有使用 synchronized,有可能會因為記憶體不一致而造成無法預期的結果, 變數 ready 可能一直是 false, 也可能印出 0 的值,但在我的 PC 上怎麼測都測不出印出 0 的結果,正確的寫法是使用 synchronized 或使用 volatile 關鍵字, 將 ready, number 都標示為 volatile

至於在什麼狀況下可使用 volatile 呢? 可參考這篇文章 Java theory and practice: Managing volatility

1. status flags
2. one-time safe publication
3. independent observations
4. volatile bean
5. The cheap read-write lock trick

使用 volatile 可獲得比使用鎖更高的執行效率,例如在讀取動作遠遠大於寫入動作的狀況下,就非常適合使用 volatile,但如果對於 volatile 用法不是很熟悉,使用鎖是比較不容易出錯的方法

參考 : http://www.ibm.com/developerworks/library/j-jtp06197

Read more

Mutex

Mutex 是 mutual exclusion 的縮寫, 中文譯為 "互斥",在多執行緒環境下,防止兩條以上的執行緒對一共用資源做同時存取的動作,一般做法是透過程式代碼 lock 的方式, 建立 critical section, 達到 mutex 的目的

下圖簡單表示 mutual exclusion 的意義

在 Java 1.4 可使用 synchronized 關鍵字來達到 mutex 的目的,但使用 synchronized 有些功能不易做到,例如

1. 如果發現 lock 已被佔用,就只能等待,無法去處理其他的工作
2. 在等待獲取鎖的狀況下,無法被 interrupt
3. 自訂取得鎖的規則(公平鎖,非公平鎖)

Java 1.5 後新增 java.util.concurrent.locks package 補強 synchronized 的不足之處

• ReentrantLock中文翻譯為"重入鎖",就字面上的意義代表當某個 thread 獲取某個鎖後,在未釋放鎖的情況下,可以獲得同一把鎖多次,因為 ReentrantLock 內部存在著一個計數器,計算取得鎖的次數,如果取得 lock 兩次,就必須 unlock 兩次才可真正的釋放鎖,這樣的設計可方便使用遞迴的方式呼叫(recursive call) lock()
  
  基本使用方式
  

  final Lock lock = new ReentrantLock();
  lock.lock();
  try { 
    // do something ...
  }
  finally {
    lock.unlock(); 
  }
  

  遞迴呼叫
  

  private final ReentrantLock lock = new ReentrantLock();
  
  public void execute() {
      try {
          lock.lock();//This lock supports a maximum of 2147483647 recursive locks by the same thread.
  
          System.out.println("lock|HoldCount=" + lock.getHoldCount());
  
          if (lock.getHoldCount() < 10)
              execute();//recursive locking by a single thread
  
      } finally {
          lock.unlock();
          System.out.println("unlock|HoldCount=" + lock.getHoldCount()
              + "|isHeldByCurrentThread=" + lock.isHeldByCurrentThread());
      }
  }
  

  從 Java 的 API Specification 我們可以看到 ReentrantLock 的 constructor 在不傳值的狀況下的狀況下,預設是個非公平鎖,如果我們要讓獲得鎖公平,就必需維持 thread 的排隊順序,這需要額外開銷,對執行效率是不利的,雖然獲取鎖的原則是不公平的,但 JVM 保證所有 thread 最終會獲得它們等待的鎖,避免 thread starvation
  
  ReentrantLock 有 lock, tryLock, lockInterruptibly 幾個獲取 lock 的 method
  
  • lock() : 如果拿不到 lock 就一直等待,直到拿到 lock 為止
  • tryLock() : 如果拿到鎖就 return true, 否則就 return false
  • tryLock(long timeout, TimeUnit unit) : 如果拿不到 lock, 則等待一段時間
  • lockInterruptibly() : 如果拿不到 lock 就一直等待, 在等待的過程中 thread 可以被 interrupted

  public void testLock() throws Exception {
      private final Lock lock = new ReentrantLock();
      lock.lock();
  
      Thread t = new Thread(new Runnable() {
  
          public void run() {
              lock.lock();
              System.out.println(Thread.currentThread().getName() + " acquires the lock");
          }
      });
  
      t.start();
      Thread.sleep(3000);
      t.interrupt();//無作用,因 thread 並非在 wait,join,sleep 狀態
      Thread.sleep(Long.MAX_VALUE);
  }
  

  public void testLockInterruptibly() throws Exception {
      private final Lock lock = new ReentrantLock();
      lock.lock();
  
      Thread t = new Thread(new Runnable() {
  
          public void run() {
              try {
                  lock.lockInterruptibly();
              } catch (InterruptedException e) {
                  System.out.println(Thread.currentThread().getName() + " interrupted.");
              }
          }
      });
  
      t.start();
      Thread.sleep(3000);
      t.interrupt();//thread 在等待獲得 lock 的過程中被中斷
      Thread.sleep(Long.MAX_VALUE);
  }
  

• ReentrantReadWriteLock 讀寫鎖內部維護一對鎖, 一把用於讀取的操作, 另一把用於寫入操作, 讀取鎖可同時被多個讀取者擁有, 而此時鎖所保護的資料處於唯讀狀態, 讀寫鎖是互斥的, 因此當沒有任何讀取或寫入鎖定時, 才可以取得寫入鎖定, 但是對於讀取來說沒有互斥性,可參考 Java Doc 對於 Interface ReadWriteLock 的說明 , 另外使用 ReentrantReadWriteLock 時, 在讀取 thread 很多, 寫入 thread 很少的狀況下, 可能會使得寫入 thread 一直處於等待狀態, 因此必需留意 thread starvation 的問題

Read more

Semaphore

提供平行運算環境中,控制多個 thread 存取共享資源的一種策略模式,semaphore 是一個計數器的概念,用於保護共享的資源

譬如說有多個 thread 想要對同一塊記憶體變數進行讀寫時,在讀寫這塊記憶體之前,先獲得一個保護變數的 semaphore,當獲得這個 semaphore 時,其他人都不能對這塊記憶體進行讀寫,直到 semaphore 持有者釋放 semaphore 為止,在這種狀況下 semaphore 的值只有二進位的 0 或 1,稱為 binary semaphores,當受保護的資源數量大於 1 的任意數量時,稱作 counting semaphores,semaphore 常用於實作 publisher subscriber model & resource pool 中

Java Semaphore example

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Semaphore;
import java.util.concurrent.TimeUnit;

public class TestSemaphore {
    public static void main(String[] args) {

        final int CONSUMER_COUNT = 20;
        final int RESOURCE_COUNT = 10;
        final ExecutorService exec = Executors.newCachedThreadPool();
        final Semaphore semaphore = new Semaphore(RESOURCE_COUNT);

        for (int i = 0; i < CONSUMER_COUNT; i++) {   
            final int INDEX = i;
            Runnable run = new Runnable() {
                public void run() {
                    try {
                        if (!semaphore.tryAcquire(2, TimeUnit.SECONDS))
                        {
                            throw new RuntimeException("timeout");
                        }

                        System.out.println("Acquire:" + INDEX + " / AvailablePermits:" + semaphore.availablePermits());

                        Thread.sleep(1000);
 
                        System.out.println("Release:" + INDEX + " / AvailablePermits:" + semaphore.availablePermits());
                        semaphore.release();
                   } 
                   catch (InterruptedException e) {
                   }
               }
           };

           exec.execute(run);
        }

        exec.shutdown();
    }
}

Read more

CAPTCHA

CAPTCHA 是 Completely Automated Public Turing test to tell Computers and Humans Apart 的縮寫,主要功能防止有人使用惡意程式大量送出網頁表單

網頁 CAPTCHA
最基本的 CAPTCHA 是利用程式產生一組數字或文字圖像,讓使用者辨識,並輸入圖像中看到的文字,連同網頁表單一起送出,Server 判斷使用者輸入的答案是否正確,後來發展出解計算題,選擇題,西洋棋遊戲等等,各式各樣不同的作法,在此我們就基本文字 CAPTCHA 的實作方式做討論,因 HTTP 協定是 Stateless,所以網頁在實作 CAPTCHA 面臨如何記憶 CAPTCHA 答案的問題,常見的實作方式有三種

將答案記憶在

1. web session
實作方便,但如果使用的人多,當 session 量一大,會有拖慢 web server 速度的風險
2. database
使用資料庫相較其他兩種方法,實作較為複雜,建置資料庫也需要額外的開銷
實作資料庫 CAPTCHA 可參考 CodeIgniter
首先建立 Table

CREATE TABLE captcha (
    captcha_id bigint(13) unsigned NOT NULL auto_increment,
    captcha_time int(10) unsigned NOT NULL,
    ip_address varchar(16) default '0' NOT NULL,
    word varchar(20) NOT NULL,
    PRIMARY KEY `captcha_id` (`captcha_id`),
    KEY `word` (`word`)
);
當使用者送出表單時,先刪除舊有驗證碼資料,然後使用 ip_address 和 captcha_time 作條件檢查輸入的驗證碼資料是否正確
3. cookie 或隱藏欄位中
此法網路上也有許多實作的範例可參考,大致上的做法是將答案加密後放在隱藏欄位或 cookie 中,當表單送出的同時將加密後的解答一併送出到 Server 端,Server 端將使用者的答案與解密後的解答做比對,這個作法安全性是三種裡頭最差的,因為只要人工辨識一次後,將辨識後的解答與加密後的密碼記憶下來,未來送出表單時只要填入這一組解答和加密後的密碼即可輕易破解

實作 CAPTCHA 小技巧

• 使用 Data URI scheme,圖檔使用內嵌資料寫法,增加網頁內容檢驗的難度
• 檢查使用者送出的 CAPTCHA Code 不可為空值,避免成為漏洞
• 若使用者輸入錯誤,則重新產生新的 CAPTCHA 圖形
• 隨機產生不同的圖形格式(JPEG,GIF,PNG),或使用 GIF 動畫也是增加破解難度的方式之一

網路上有提供一些免費的 CAPTCHA 服務,若不想自己寫,可考慮使用

• Google reCAPTCHA

實際上現今 CAPTCHA 阻擋惡意程式的效果相當有限,一些 OCR 可輕易的破解(PWNtcha - captcha decoder),只能說防君子不防小人了

Read more

Java Atomic Operation

定義

代表一種不可再分割的操作,在 multithreading 的環境中 Atomic Operation 是達成 thread-safe 的方法之一
至於為什麼會取名 Atomic 呢? 可能是過去原子被認定為物質的最小單位,無法再分割有關

舉例來說,當我們在 Java 中執行宣告 int i = 12 會配置 32 bits 的記憶體空間並將 12 這個值寫到記憶體區塊中,將整數 12 寫入記憶體這個操作是一個 Atomic Operation,不會只做一半就被其他操作中斷,而影響指派(assignment)值的正確性

使用硬體裝置支援的 Atomic Operation 可有效地提高程式效率, Intel Software Developer’s Manual 有說明哪些操作 Guaranteed Atomic Operations

Java 除了 double 和 long 這兩個資料型別以外,所有的 primitive types & reference types 讀取和寫入操作都是 Atomic Operation, 宣告為 volatile 的 double 和 long 讀取和寫入操作也視為 Atomic Operation

http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.7

從 Java 1.5 開始,增加了package java.util.concurrent.atomic,可以在不使用 lock 的狀況下,達到 thread-safe 的目的

舉個例子

我們如果要寫個 thread-safe 的計數器,Java 1.4 的作法

public class Counter {
    private int count = 0;

    public synchronized int incrementCount() {
        return ++count;
    }
}

在 Java 中 ++count 這個操作,不是 atomic operation 因此是 non-thread-safe,做個細部分解,++count至少包含三個以上的動作

1. 讀取count的值
2. 將步驟1讀取出的值加1
3. 將步驟2計算完成的值寫回變數count

從 x86 CPU 的角度來看,會使用三條指令來處理

1. 從 memory 讀取 count 值到 register
2. 對 register 的值加 1
3. 把新值寫回 count 所在的 memory address

在多執行緒的環境下為了 thread-safe,所以必須使用 synchronized 關鍵字,synchronized 可達到 mutex & visibility 的目的

Java 1.5 後就可以使用 AtomicInteger 來替代 lock,相當於使用了 CPU 的 compare and swap 指令,在 x86 的架構中稱作 compare and exchange,使用 AtomicInteger 的另一項優點是 visibility,所以記憶體的值是一致的(memory consistency)

public class Counter {
    private final AtomicInteger count = new AtomicInteger(0);

    public int incrementCount() {
        return count.incrementAndGet();
    }
}

所有 java.util.concurrent.atomic package classes 都使用 Atomic 開頭, 包含以下 classes

• AtomicBoolean
• AtomicInteger
• AtomicIntegerArray
• AtomicIntegerFieldUpdater
• AtomicLong
• AtomicLongArray
• AtomicLongFieldUpdater
• AtomicMarkableReference
• AtomicReference
• AtomicReferenceArray
• AtomicReferenceFieldUpdater
• AtomicStampedReference

參考
Wikipedia - Linearizability
Java theory and practice: Going atomic
Intel Threading Building Blocks User Guide - Atomic Operations

Read more

Java time zone data

今天發現 Java 的 MIT Time Zone 會因為版本的不同而有不同的結果

System.out.println("java version=" + System.getProperty("java.version"));
Date now = new Date();  
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSSZ");  
sdf.setTimeZone(TimeZone.getTimeZone("MIT"));  
System.out.println("MIT time=" + sdf.format(now));

以下為測試各版本JRE跑出來的結果
output
------------------------------------------------------------
java version=1.4.2
MIT time=2014-01-15 14:01:06.937-1100
------------------------------------------------------------
java version=1.5.0_22
MIT time=2014-01-15 14:01:26.025-1100
------------------------------------------------------------
java version=1.6.0_45
MIT time=2014-01-16 15:02:03.133+1400
------------------------------------------------------------
java version=1.7.0
MIT time=2014-01-15 14:02:14.400-1100
------------------------------------------------------------
java version=1.7.0_51
MIT time=2014-01-16 15:02:47.562+1400

在 1.4.2 版時 MIT 時區的 Raw Offset 是 GMT-1100,到了1.6.0_45 版時 MIT 時區的 Raw Offset 改成了 GMT+1400,而 1.7.0 版卻又變成了 GMT-1100, 看起來 Java 版本和時區是並沒有直接相關, 其實 Java 的時區資訊跟使用的 tz database 版本有關,關於 tz database 可參考 http://en.wikipedia.org/wiki/Tz_database

JRE 內部有一份屬於自己的 tz database,在 JRE 安裝目錄下的 lib/zi 目錄內記載著時區相關資料,因此時區資料不會因為OS的更新而改變,JRE 使用的 tzdata 版本資訊可參考 http://www.oracle.com/technetwork/java/javase/tzdata-versions-138805.html
至於如何得知JRE所用的 tzdata 版本,簡易的方法是使用文字編輯器打開JRE安裝目錄下的 lib/zi/ZoneInfoMappings 檔案,如下圖標註紅色的部分即是目前 tzdata 的版本

另外一個方法就是使用 TZupdater 來檢視和更新JRE的時區資訊
關於 TZupdater 用法可參考
http://www.oracle.com/technetwork/java/javase/timezones-137583.html
http://www.oracle.com/technetwork/java/javase/dst-faq-138158.html
http://www.symantec.com/business/support/index?page=content&id=TECH58669

印出所有時區 RawOffset 資訊

for (String id : TimeZone.getAvailableIDs())
{
    TimeZone tz = TimeZone.getTimeZone(id);
    System.out.println("ID:" + tz.getID() + "|Name:"+ tz.getDisplayName(Locale.ENGLISH) + "|RawOffset:" + tz.getRawOffset());
}

TimeZone class 也提供 inDaylightTime 來測試是否使用日光節約時間

MIT 是 Midway Islands Time 的縮寫, 屬於 West Samoa Time 時區,至於 Raw Offset 為什麼會改變,可能是政治或經濟因素而改變的吧

Read more

C# Class and Struct

1.Memory Allocation

Class => Reference Type
Struct => Value Type

new operator on a class => heap
instantiate a struct => stack

以上的差異造成傳遞資料到 method 中會有不同的結果

Class => a reference is passed
Struct => a copy of the struct is passed

以下引用 MSDN 的範例程式 http://msdn.microsoft.com/en-us/library/aa288471(v=vs.71).aspx

// struct2.cs
using System;

class TheClass
{
    public int x;
}

struct TheStruct
{
    public int x;
}

class TestClass
{
    public static void structtaker(TheStruct s)
    {
        s.x = 5;
    }
    public static void classtaker(TheClass c)
    {
        c.x = 5;
    }
    public static void Main()
    {
        TheStruct a = new TheStruct();
        TheClass b = new TheClass();
        a.x = 1;
        b.x = 1;
        structtaker(a);
        classtaker(b);
        Console.WriteLine("a.x = {0}", a.x);
        Console.WriteLine("b.x = {0}", b.x);
    }
}

Struct傳遞的是複本, 所以結果 a.x = 1, 而 b.x = 5

2.Constructors

Struct 不可使用無參數的constructor ,結構成員也不可設定初始值, 也不可使用 destructor

錯誤

public struct TheStruct1
{
    public TheStruct1()
    {      
    }
    public int x = 0;
}

正確

public struct TheStruct1
{
    public TheStruct1(int c)
    {
        x = c;
    }
    public int x;
}

TheStruct1 a = new TheStruct1();
Console.WriteLine("a.x = {0}", a.x);
TheStruct1 b = new TheStruct1(2);
Console.WriteLine("b.x = {0}", b.x);
TheStruct1 c = default(TheStruct1);//use default keyword
Console.WriteLine("c.x = {0}", c.x);
TheStruct1 d;
d.x = 99;//Initialize
Console.WriteLine("d.x = {0}", d.x);

當執行個體化結構且建構子未傳入值時,結構成員會自動初始化

執行結果
a.x = 0
b.x = 2
c.x = 0
d.x = 99

3.Inheritance

結構沒有繼承,但可實作介面

4.自訂結構在記憶體中的安排方式

使用 StructLayout(LayoutKind.Union) 和 FieldOffset

5.使用時機

struct被定義為輕量化的物件,與物件相比較 struct GC 的成本小,微軟建議在下面的狀況下可考慮使用struct

√ CONSIDER defining a struct instead of a class if instances of the type are small and commonly short-lived or are commonly embedded in other objects.
X AVOID defining a struct unless the type has all of the following characteristics:

• It logically represents a single value, similar to primitive types (int, double, etc.).
• It has an instance size under 16 bytes.
• It is immutable.
• It will not have to be boxed frequently.

引用自 http://msdn.microsoft.com/en-us/library/ms229017.aspx

參考
Structs  http://msdn.microsoft.com/en-us/library/saxz13w4.aspx
Classes and Structs  http://msdn.microsoft.com/en-us/library/ms173109.aspx
Class and struct differences  http://msdn.microsoft.com/en-us/library/aa664471(v=vs.71).aspx

Read more