7 concurrency models in seven weeks (phần 2)
concurrency model
5
hardcore
18
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

118 bài viết.
1062 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
166 15
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 2 năm trước
166 15
White
156 16
Một ngày đẹp trời, bạn quyết định viết một dịch vụ web dự định sẽ làm thay đổi cả thế giới. Dịch vụ của bạn sẽ kết nối tất cả các thiết bị di động ...
huydx viết 3 tháng trước
156 16
White
135 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
135 15
Bài viết liên quan
White
12 0
Hadoop là cái gì vậy? “Hadoop là một framework nguồn mở viết bằng Java cho phép phát triển các ứng dụng phân tán có cường độ dữ liệu lớn một cách ...
nguyenduyhao1111 viết 2 năm trước
12 0
White
77 34
Bài viết thuộc chủ đề nghiên cứu trong nhóm hardcore của Cộng đồng Ruby Việt Nam Đọc manga trên mobile là một nhu cầu rất lớn, nhưng hiện nay chư...
Huy Trần viết 2 năm trước
77 34
{{like_count}}

kipalog

{{ comment_count }}

bình luận

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


White
{{userFollowed ? 'Following' : 'Follow'}}
118 bài viết.
1062 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á!