7 concurrency models in seven weeks (phần 2)
concurrency model
5
hardcore
17
White

huydx viết ngày 28/08/2016

Tiếp nối phần 1 http://kipalog.com/posts/7-concurrency-models-in-seven-week--phan-1.
Trong phần này chúng ta sẽ tiếp tục tìm hiểu về mô hình Thread-Lock thông qua việc tìm hiểu:

  • Deadlock khi sử dụng nhiều lock cùng một lúc thông qua bài toán nổi tiếng: dining philosophier (hay là bữa ăn tối của các nhà hiền triết)
  • Sử dụng các chức năng của java reentrantlock như là timeout, interrupt
  • Handover locking

Deadlock

Mô tả deadlock không phải là một việc quá đơn giản, mô tả race condition dễ hơn nhiều. Để mô tả được deadlock thì có một bài toán rất hay được sử dụng gọi là dining philosophier. Hãy hình dung là có 5 nhà hiền triết ngồi quanh 1 cái bàn tròn, với 5 (lưu ý là 5 chứ không phải 10) chiếc đũa được đặt ở mỗi giữa 2 người.

alt text

Khi một nhà hiền triết bị đói, ông ta sẽ lấy đũa ở 2 bên của mình để ăn. Khi nào ăn xong ông ta sẽ để xuống. Để mô tả hành động đó chúng ta có đoạn code dưới đây

class Philosopher extends Thread { 
    private Chopstick left, right; private Random random;
    public Philosopher(Chopstick left, Chopstick right) { 
        this.left = left; this.right = right;
        random = new Random();
    }

    public void run() { 
        try {
            while(true) { 
                Thread.sleep(random.nextInt(1000)); 
                synchronized(left) {
                    synchronized(right) {
                        Thread.sleep(random.nextInt(1000));
                    }
                }
            }
         } catch(InterruptedException e) {}
    }
}

Đoạn code trên sử dụng một kĩ thuật gọi là intrinsic lock (lock từ bên trong). Kĩ thuật này trong java sử dụng chính object hiện tại để lock, nhờ việc là những đoạn code trong cùng một scope thì sẽ có chung một object nên sử dụng rất tiện lợi.
Nhìn thoáng qua thì đoạn code trên hoàn toàn không có vấn đề gì, nhưng nếu chạy đoạn code trong một thời gian tương đối dài, có thể là 1 vài giờ, thì sẽ có một thời điểm nào đó xử lý bị ngưng lại. Điều này xảy ra khi cả 5 nhà hiền triết đều muốn ăn cùng một lúc, và đều có ý định lấy chiếc đũa bên phải (hoặc bên trái mình). Việc bị lock do đợi chéo (hoặc vòng tròn) lẫn nhau chính là deadlock.
Deadlock là một tình huống nguy hiểm khi mà một thread có ý định giữ >= 2 lock.

Có một rule đơn giản để tránh deadlock:

Luôn luôn lấy lock theo một thứ tự cố định (nhìn từ global)

Điều đó thể hiện bằng cách sửa lại đoạn code ở trên như dưới đây

class Philosopher extends Thread {
  private Chopstick first, second;
  private Random random;
  private int thinkCount;

  public Philosopher(Chopstick left, Chopstick right) {
    if(left.getId() < right.getId()) {
      first = left; second = right;
    } else {
      first = right; second = left;
    }
    random = new Random();
  }

  public void run() {
    try {
      while(true) {
        ++thinkCount;
        if (thinkCount % 10 == 0)
          System.out.println("Philosopher " + this + " has thought " + thinkCount + " times");
        Thread.sleep(random.nextInt(1000));     // Think for a while
        synchronized(first) {                   // Grab first chopstick
          synchronized(second) {                // Grab second chopstick
            Thread.sleep(random.nextInt(1000)); // Eat for a while
          }
        }
      }
    } catch(InterruptedException e) {}
  }
}

Điểm khác của đoạn code ở dưới so với ở trên chính là thay vì lấy 2 chiếc đũa left và right một cách bừa bãi, thì chúng ta sử dụng hàm getId() (lấy object id trong java) để chỉ cho lock theo thứ tự id từ thấp đến cao.
Việc đó giúp ngăn chặn 2 thread khác nhau lock 2 object theo thứ tự đan chéo, dẫn đến deadlock.

Note rằng sử dụng hàm hashCode thay vì getId cũng là một practice thường thấy, tuy nhiên hashCode có thể bị lặp lại là một điều có thẻ xảy ra, mặc dù tỉ lệ rất thấp.

Một số kĩ thuật locking khác trên java

Intrinsic lock khá tiện tuy nhiên cũng có một vài bất cập:

  • Không có cách nào để interrupt một thread khi đang đợi để truy cập một intrinsic lock
  • Không co cách nào để timeout quá trình đợi đó
  • Chỉ có một cách sử dụng duy nhất thông qua hàm synchronized

Do một vài bất tiện đó nên có một cách khác để sử dụng cho mục đích lock trên java đó là ReentrantLock.
ReentrantLock giải quyết được các bài toán ở trên thông qua một số tính năng thú vị như là interrupt hay là timeout, mà thể hiện ở các đoạn code dưới đây

Interrupt lock


import java.util.concurrent.locks.ReentrantLock;

public class Interruptible {

  public static void main(String[] args) throws InterruptedException {

    final ReentrantLock l1 = new ReentrantLock();
    final ReentrantLock l2 = new ReentrantLock();

    Thread t1 = new Thread() {
      public void run() {
        try {
          l1.lockInterruptibly();
          Thread.sleep(1000);
          l2.lockInterruptibly();
        } catch (InterruptedException e) { System.out.println("t1 interrupted"); }
      }
    };

    Thread t2 = new Thread() {
      public void run() {
        try {
          l2.lockInterruptibly();
          Thread.sleep(1000);
          l1.lockInterruptibly();
        } catch (InterruptedException e) { System.out.println("t2 interrupted"); }
      }
    };

    t1.start(); t2.start();
    Thread.sleep(2000);
    t1.interrupt(); t2.interrupt();
    t1.join(); t2.join();
  }
}

Timeout lock


import java.util.Random;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.ReentrantLock;

class Philosopher extends Thread {
  private ReentrantLock leftChopstick, rightChopstick;
  private Random random;
  private int thinkCount;

  public Philosopher(ReentrantLock leftChopstick, ReentrantLock rightChopstick) {
    this.leftChopstick = leftChopstick; this.rightChopstick = rightChopstick;
    random = new Random();
  }

  public void run() {
    try {
      while(true) {
        ++thinkCount;
        if (thinkCount % 10 == 0)
          System.out.println("Philosopher " + this + " has thought " + thinkCount + " times");
        Thread.sleep(random.nextInt(1000)); // Think for a while
        leftChopstick.lock();
        try {
          if (rightChopstick.tryLock(1000, TimeUnit.MILLISECONDS)) {
            // Got the right chopstick
            try {
              Thread.sleep(random.nextInt(1000)); // Eat for a while
            } finally { rightChopstick.unlock(); }
          } else {
            // Didn't get the right chopstick - give up and go back to thinking
            System.out.println("Philosopher " + this + " timed out");
          }
        } finally { leftChopstick.unlock(); }
      }
    } catch(InterruptedException e) {}
  }
}

Handover Locking

Khi bạn làm việc với các hệ thống song song, sẽ có những trường hợp bạn sẽ có ý định lock cả một data structure to, ví dụ như là một linkedlist hay là một map. Với những trường hợp đó, bạn sẽ có lựa chọn là chỉ cần lock một phần nhỏ của cơ sở dữ liệu thay vì lock toàn bộ. Kĩ thuật lock một phần nhỏ đó gọi là handover locking.

Đoạn code dưới đây mô tả handover locking cho một linkedlist. Do linkedlist này là thread safe nên chúng ta có thể gọi nó là ConcurrentLinkedList

import java.util.concurrent.locks.ReentrantLock;

class ConcurrentSortedList {

  private class Node {
    int value;
    Node prev;
    Node next;
    ReentrantLock lock = new ReentrantLock();

    Node() {}

    Node(int value, Node prev, Node next) {
      this.value = value; this.prev = prev; this.next = next;
    }
  }

  private final Node head;
  private final Node tail;

  public ConcurrentSortedList() {
    head = new Node(); tail = new Node();
    head.next = tail; tail.prev = head;
  }

  public void insert(int value) {
    Node current = head;
    current.lock.lock(); 
    Node next = current.next;
    try {
      while (true) {
        next.lock.lock(); 
        try {
          if (next == tail || next.value < value) { 
            Node node = new Node(value, current, next); 
            next.prev = node;
            current.next = node;
            return; 
          }
        } finally { current.lock.unlock(); } 
        current = next;
        next = current.next;
      }
    } finally { next.lock.unlock(); } 
  }

  public int size() {
    Node current = tail;
    int count = 0;

    while (current.prev != head) {
      ReentrantLock lock = current.lock;
      lock.lock();
      try {
        ++count;
        current = current.prev;
      } finally { lock.unlock(); }
    }

    return count;
  }

  public boolean isSorted() {
    Node current = head;
    while (current.next.next != tail) {
      current = current.next;
      if (current.value < current.next.value)
        return false;
    }
    return true;
  }
}

Các bạn có thể để ý thấy kĩ thuật được sử dụng ở trên thông qua việc mỗi node của một lock riêng, khi chúng ta định insert hay delete ở đâu thì chỉ cần thao tác với lock ở node đó và 2 node lân cận.

Tạm thời dừng lại ở đây nhé, trong bài tiếp theo sẽ là ConcurrentHashMap và CopyOnWrite array.

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

huydx

116 bài viết.
944 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
148 14
Introduction (Link) là một cuộc thi ở Nhật, và cũng chỉ có riêng ở Nhật. Đây là một cuộc thi khá đặc trưng bởi sự thú vị của cách thi của nó, những...
huydx viết gần 2 năm trước
148 14
White
118 15
Happy programmer là gì nhỉ, chắc ai đọc xong title của bài post này cũng không hiểu ý mình định nói đến là gì :D. Đầu tiên với cá nhân mình thì hap...
huydx viết hơn 3 năm trước
118 15
White
95 10
(Ảnh) Mở đầu Chắc nhiều bạn đã nghe đến khái niệm oauth. Về cơ bản thì oauth là một phương thức chứng thực, mà nhờ đó một web service hay một ap...
huydx viết 3 năm trước
95 10
Bài viết liên quan
White
1 3
C++: mutex, recursive_mutex, lock_guard, condition_variable và atomic Nguồn : http://baptistewicht.com/posts/2012/04/c11concurrencytutorialadvance...
Manh Truong Tuan viết hơn 1 năm trước
1 3
White
18 3
Bạn nghe phong thanh người ta nói Elixir chạy nhanh hơn Ruby? Bạn muốn biết làm sao để Whatsapp phục vụ 900 triệu người dùng với chỉ 50 engineers? ...
Cẩm Huỳnh viết 2 tháng trước
18 3
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
116 bài viết.
944 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!