java 实现共享锁和排它锁

一直对多线程有恐惧，在实现共享锁和排它锁之后，感觉好了很多。

共享锁就是查询的时候，如果没有修改，可以支持多线程查询；

排它锁就是修改的时候，锁定共享锁，停止查询，同时，锁定排它锁，只允许一个线程进行修改，修改完成后，再解开共享锁；

心路历程：一开始的想法是，绝对不调用 sleep ，要用到sleep 的地方我觉得都可以用 notify() 和 wait() 替换，sleep（T）我觉得T 的大小压根是无法算出来的，如果非要用sleep 我觉得T 的时间应该是一个动态的值，这个值是通过函数的执行时间的一个平均值（每N次执行算一个平均值出来）但个人觉得还是不如notify() 和wait(); 我为了简单，操作的是一颗字典树代替B树；如何实现读支持多线程，写单线程呢！当各种查询和修改的操作以多线程的方式提交给线程池的时候，程序会从阻塞队列里面不断的取任务，当前面取到的任务是查询的时候，不要管他，没有修改表结构，直接丢给一个线程，当取到的下任务是一个修改或者更新的任务时，首先必须等待前面的查询全部查询完，然后再停掉阻塞队列不断的添加任务，要让我修改完成之后，再唤醒阻塞队列添加任务；由于我不知道如何停掉线程池的阻塞队列添加任务，所以干脆自己模拟线程池这个过程；（理论上这个方法是可行的）主要的卡是在notify() 和 wait()的理解上面，这两个方法执行时都必须在锁里面；所以在查询的代码里面，你不能wait() 那样会变成单线程；

1 insert; 2 remove; 3 query; -1 stopRun

  1 package com.trafree;
  2 
  3 import java.io.File;
  4 import java.io.IOException;
  5 import java.util.*;
  6 import java.util.concurrent.atomic.AtomicInteger;
  7 
  8 /**
  9  * Created by on_the_way on 2014/12/31.
 10  */
 11 public class AboutThread {
 12 
 13     public static boolean insert(String str) {
 14         int len = str.length();
 15         Trie p = root;
 16         for (int i = 0; i < len; i++) {
 17             int num = str.charAt(i) - 'a';
 18             if (p.next[num] == null) {
 19                 p.next[num] = new Trie();
 20             }
 21             p = p.next[num];
 22         }
 23         if (p.end) return false;
 24         return p.end = true;
 25     }
 26 
 27     public static boolean remove(String str) {
 28         int len = str.length();
 29         Trie p = root;
 30         for (int i = 0; i < len; i++) {
 31             int num = str.charAt(i) - 'a';
 32             if (p.next[num] == null) {
 33                 return false;
 34             }
 35             p = p.next[num];
 36         }
 37         if (!p.end) {
 38             return false;
 39         }
 40         p.end = false;
 41         return true;
 42     }
 43 
 44     public static boolean query(String str) {
 45         int len = str.length();
 46         Trie p = root;
 47         for (int i = 0; i < len; i++) {
 48             int num = str.charAt(i) - 'a';
 49             if (p.next[num] == null) {
 50                 return false;
 51             }
 52             p = p.next[num];
 53         }
 54         return p.end;
 55     }
 56 
 57     public static Trie root = new Trie();
 58 
 59     public static class Trie {
 60         public Trie next[] = new Trie[26];
 61         public boolean end;
 62 
 63         public Trie() {
 64             for (int i = 0; i < 26; i++) {
 65                 this.next[i] = null;
 66             }
 67             this.end = false;
 68         }
 69     }
 70 
 71     public static class Consumer implements Runnable {
 72         public void run() {
 73             try {
 74                 MyThread.process();
 75             } catch (Exception e) {
 76                 e.printStackTrace();
 77             }
 78         }
 79     }
 80 
 81     public static class MyThread implements Runnable {
 82 
 83         public int sequence;
 84         public int action;
 85         public String str;
 86         public boolean res;
 87 
 88         public static Object lock1 = new Object();
 89         public static Object lock2 = new Object();
 90         public static Object lock3 = new Object();
 91 
 92         public static boolean needNotify1 = false;
 93         public static boolean needNotify2 = false;
 94         public static boolean needNotify3 = false;
 95         public static boolean runModify = false;
 96 
 97         public static AtomicInteger queryNum = new AtomicInteger(0);
 98         public static Queue<MyThread> pool = new LinkedList<MyThread>();
 99 
100         public MyThread(int sequence, int action, String str) {
101             this.sequence = sequence;
102             this.action = action;
103             this.str = str;
104             this.res = false;
105         }
106 
107         public static void process() throws InterruptedException {
108 
109             boolean needBreak = false;
110             while (true) {
111                 if( pool.size() == 0 && needBreak ){
112                     break;
113                 }
114                 synchronized (lock1) {
115                     if (pool.size() == 0) {
116                         needNotify1 = true;
117                         lock1.wait();
118                     }
119                 }
120                 synchronized (lock3) {
121                     if (runModify) {
122                         needNotify3 = true;
123                         lock3.wait();
124                     }
125                 }
126                 MyThread myThread = pool.poll();
127 
128                 if (myThread.action == -1){
129                     needBreak = true;continue;
130                 }
131                 if (myThread.action == 1 || myThread.action == 2) {
132                     synchronized (lock2) {
133                         if (queryNum.get() != 0) {
134                             needNotify2 = true;
135                             runModify = true;
136                             lock2.wait();
137                             new Thread(myThread).start();
138                         } else {
139                             runModify = true;
140                             new Thread(myThread).start();
141                         }
142                     }
143                 } else {
144                     queryNum.incrementAndGet();
145                     new Thread(myThread).start();
146                 }
147             }
148         }
149 
150         public void run() {
151             if (this.action == 1) {
152                 this.res = insert(this.str);
153                 synchronized (lock3) {
154                     needNotify1 = false;
155                     runModify = false;
156                     if( needNotify3 )lock3.notify();
157                 }
158                 System.out.println(sequence+" "+action+" "+str+" "+res);
159             } else if (this.action == 2) {
160                 this.res = remove(this.str);
161                 synchronized (lock3) {
162                     needNotify1 = false;
163                     runModify = false;
164                     if( needNotify3 )lock3.notify();
165                 }
166                 System.out.println(sequence+" "+action+" " + str+" "+res);
167             } else {
168                 this.res = query(str);
169                 System.out.println(sequence+" "+action+" "+str+" "+res);
170                 synchronized (lock2) {
171                     if (queryNum.decrementAndGet() == 0 ) {
172                         if(needNotify2)lock2.notify();
173                     }
174                 }
175             }
176         }
177 
178     }
179 
180     public static void main(String arg[]) throws IOException {
181 
182         File file = new File("F:" + File.separator + "in.txt");
183         Scanner cin = new Scanner(file);
184         int N = cin.nextInt();
185         int M = cin.nextInt();
186 
187         for (int i = 0; i < N; i++) {
188             insert(cin.next());
189         }
190 
191         new Thread(new Consumer()).start();
192         for (int i = 0; i < M; i++) {
193             MyThread myThread = new MyThread(i, cin.nextInt(), cin.next());
194             synchronized (MyThread.lock1) {
195                 MyThread.pool.add(myThread);
196                 if (MyThread.needNotify1) {
197                     MyThread.needNotify1 = false;
198                     MyThread.lock1.notify();
199                 }
200             }
201         }
202     }
203 }

View Code

40 45
what
make
you
so
beautiful
have
think
cell
green
red
java
hand
forum
discuss
online
contests
teaching
exercise
contest
recent
icpc
authors
ranklist
problem
achive
exams
university
judge
register
new
fortunately
old
behind
locked
the
feature
find
by
alphabet
more

3 what
3 more
3 old
3 find
3 exams
3 achive
3 icpc
3 recent
3 ranklist
2 ranklist
3 ranklist
1 ranklist
3 ranklist
3 find
3 alphabet
2 find
2 find
3 find
2 alphabet
1 alphabet
3 alphabet
3 find
1 find
3 find
3 what
3 more
3 old
3 find
3 exams
3 achive
3 icpc
3 recent
3 ranklist
3 ranklist
3 what
3 more
3 old
3 find
3 exams
3 achive
3 icpc
3 recent
3 ranklist
3 ranklist
-1 end