Monday, December 14, 2015

JUC 多线程顺序执行



http://www.obsidianscheduler.com/blog/java-concurrency-part-1-semaphores/
So what is semaphore? The simplest way to think of a semaphore is to consider it an abstraction that allows n units to be acquired, and offers acquire and release mechanisms. It safely allows us to ensure that only n processes can access a certain resource at a given time.
The number one thing to remember is, always release what you acquire. This is done by using try..finally constructs.
There are other less obvious problems that can befall you when using semaphores. The following class shows a deadlock that only the luckiest of you will avoid. You’ll notice that the two threads which acquire the two semaphore permits do so in opposite order. (try..finally is left out for the sake of brevity).
   Thread t = new Thread(new DoubleResourceGrabber(s1, s2));
   // now reverse them ... here comes trouble!
   Thread t2 = new Thread(new DoubleResourceGrabber(s2, s1));

If you run this, you will more than likely have a hung process. Issues of lock ordering apply to semaphores as much as regular mutexes or synchronization in Java. In some cases, timeouts (see note on tryAcquire() later in the article) can be used to prevent deadlocks from causing a process to hang up, but typically a deadlock is a symptom of a logic error which can be avoided. 

The main things that you should be careful of when using semaphores (including binary semaphores, i.e. mutexes) are:
  • Not releasing after acquire (either missing release call or an exception is thrown and there is no finally block)
  • Long held semaphores, causing thread starvation
  • Deadlocks (as seen above)
One interesting property of Semaphores in Java is that release doesn’t have to be called by the same thread as acquire. This means you could have a thread limiter that pools or creates threads based on a semaphore by calling acquire(). Then, the running thread could release its own semaphore permit when it completes. This is a useful property that we don’t have with normal mutexes in Java.
Another trick is to increase the number of permits at runtime. Contrary to what you might guess, the number of permits in a semaphore isn’t fixed, and a call to release() will always increment the number of permits, even if no corresponding acquire() call was made. Note that this can also result in bugs if you are incorrectly calling release() when no acquire() was made.
https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Semaphore.html
A counting semaphore. Conceptually, a semaphore maintains a set of permits. Each acquire() blocks if necessary until a permit is available, and then takes it. Each release() adds a permit, potentially releasing a blocking acquirer. However, no actual permit objects are used; the Semaphore just keeps a count of the number available and acts accordingly.
Semaphores are often used to restrict the number of threads than can access some (physical or logical) resource. For example, here is a class that uses a semaphore to control access to a pool of items:
 class Pool {
   private static final int MAX_AVAILABLE = 100;
   private final Semaphore available = new Semaphore(MAX_AVAILABLE, true);

   public Object getItem() throws InterruptedException {
     available.acquire();
     return getNextAvailableItem();
   }

   public void putItem(Object x) {
     if (markAsUnused(x))
       available.release();
   }

   // Not a particularly efficient data structure; just for demo

   protected Object[] items = ... whatever kinds of items being managed
   protected boolean[] used = new boolean[MAX_AVAILABLE];

   protected synchronized Object getNextAvailableItem() {
     for (int i = 0; i < MAX_AVAILABLE; ++i) {
       if (!used[i]) {
          used[i] = true;
          return items[i];
       }
     }
     return null; // not reached
   }

   protected synchronized boolean markAsUnused(Object item) {
     for (int i = 0; i < MAX_AVAILABLE; ++i) {
       if (item == items[i]) {
          if (used[i]) {
            used[i] = false;
            return true;
          } else
            return false;
       }
     }
     return false;
   }

 }

http://my.oschina.net/ambitor/blog/532338
  小陈、小韦、小罗 三个人打牌,手里各有一张牌,分别是A、B、C三张牌,三人出牌是异步的,怎么保证三人出牌的顺序始终是ABC?

题目分析

  题目考的是多线程之间的通信,线程通信一般有几种方式:
  • 共享内存
  • 回调函数
  • 管道流
  • 信号量(Semaphore)
  因为了节省CPU资源当一个人出牌的时候需要保证其他人是阻塞,而不是轮询的去检查是不是该自己出牌了(上面的共享内存、回调函数等方式),另外这个地方也不能用互斥锁,互斥锁对控制超过2个以上线程的顺序执行是比较困难和繁琐的,当然也可以用thread.join() ,但实际情况中一般不会有线程B内部已知线程A的情况。而Semaphore是可以很容易实现这种控制多线程按顺序执行的场景。

实现

Semaphore介绍

  信号量(Semaphore):Semaphore实现的功能就类似厕所有5个坑,假如有10个人要上厕所,那么同时只能有多少个人去上厕所呢?同时只能有5个人能够占用,当5个人中 的任何一个人让开后,其中等待的另外5个人中又有一个人可以占用了。另外等待的5个人中可以是随机获得优先机会(不公平),也可以是按照先来后到的顺序获得机会(公平:链表维护的顺序,每次取链表头部Node,Node中保存了Thread),这取决于构造Semaphore对象时传入的参数选项(但其实我理解公平不公平的意义好像不大,因为操作系统线程调用是随机的,所以哪个线程先到还不一定,这个不知道基于什么场景设计的*) 。单个信号量的Semaphore对象可以实现互斥锁的功能,并且可以是由一个线程获得了“锁”,再由另一个线程释放“锁”(这个特性很重要),这可应用于死锁恢复的一些场合,另外Semaphore底层是CAS实现的,无锁,无线程上下文切换消耗,性能高。

Semaphore原理

  实际上Semaphore的原理比较简单,就是CAS,如果不成功就一直尝试,他是没有锁的,看看源码
?
1
2
3
4
5
6
7
8
9
10
11
final int nonfairTryAcquireShared(int acquires) { 
       for (;;) {    
       //当前还有多少个资源可用        
       int available = getState();
       //可用资源减去线程索取,如果少于0说明资源不够 进入下一轮循环,直到资源够
       int remaining = available - acquires;
       if (remaining < 0 || 
            compareAndSetState(available, remaining))//CAS原子性操作
            return remaining;
        }
    }

代码实现

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
public class SemaphoreTest2 {
private final Semaphore semaphoreA = new Semaphore(1);
private final Semaphore semaphoreB = new Semaphore(1);
private final Semaphore semaphoreC = new Semaphore(1);
public void start() throws InterruptedException {
    //ABC线程启动之前 获取SemaphoreB的1个资源,保证线程A最先执行
    semaphoreB.acquire();
    //ABC线程启动之前 获取SemaphoreC的1个资源,保证线程A最先执行
    semaphoreC.acquire();
     
    Thread a=new Thread(new Runnable(){      
        @Override
        public void run() {           
           while (true){                
                try {
                    semaphoreA.acquire();
                    System.out.print("A");
                    //之前说的特性:可以在ThreadA释放ThreadB的Semaphore资源, 下同
                    semaphoreB.release();
                catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    });
     
    Thread b=new Thread(new Runnable(){        
        @Override
        public void run() {           
            while (true){             
               try {
                    semaphoreB.acquire();
                    System.out.print("B");
                    semaphoreC.release();
                catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    });
     
    Thread c=new Thread(new Runnable(){       
        @Override
        public void run() {            
             while (true){                
                try {
                    semaphoreC.acquire();
                    System.out.println("C");
                    semaphoreA.release();
                catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    });
    c.start();
    b.start();
    a.start();
}
public static final void main(String arsg[]) throws InterruptedException {
    SemaphoreTest2 semaphoreTest2=new SemaphoreTest2();
    semaphoreTest2.start();
  }
}

Semaphore总结

  Semaphore常用的场景:

  • 高性能的互斥锁实现(本题有涉及)
  • 限制访问公共资源的线程个数,如只有5个资源,那么同时执行的线程就只能是5个
  • 控制多线程执行流程控制,如:主线程等待所有异步线程执行完毕后再执行、或者多个异步线程的执行顺序(类似本题目)

Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts