当程序未正确同步时，就会存在数据竞争。Java内存模型规范对数据竞争的定义如下：
当代码中包含数据竞争时，程序的执行往往产生违反直觉的结果。如果一个多线程程序能正确同步，这个程序将是一个没有数据竞争的程序。
JMM对正确同步的多线程程序的内存一致性做了如下保证：
如果程序是正确同步的，程序的执行将具有顺序一致性（sequentially consistent）–即程序的执行结果与该程序在顺序一致性内存模型中的执行结果相同。这里的同步是指广义上的同步，包括对常用同步原语（lock，volatile和final）的正确使用。
当我们声明共享变量为volatile后，对这个变量的读/写将会很特别。
理解volatile特性的一个好方法，把对volatile变量的单个读/写，看成是使用同一个监视器锁对这些单个读/写操作做了同步。下面我们通过具体的示例来说明，请看下面的示例代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class VolatileFeaturesExample {
volatile long vl = 0L; //使用volatile声明64位的long型变量
public void set(long l) {
vl = l; //单个volatile变量的写
}
public void getAndIncrement () {
vl++; //复合（多个）volatile变量的读/写
}
public long get() {
return vl; //单个volatile变量的读
}
}
假设有多个线程分别调用上面程序的三个方法，这个程序在语意上和下面程序等价：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class VolatileFeaturesExample {
long vl = 0L; // 64位的long型普通变量
public synchronized void set(long l) { //对单个的普通 变量的写用同一个监视器同步
vl = l;
}
public void getAndIncrement () { //普通方法调用
long temp = get(); //调用已同步的读方法
temp += 1L; //普通写操作
set(temp); //调用已同步的写方法
}
public synchronized long get() {
//对单个的普通变量的读用同一个监视器同步
return vl;
}
}
如上面示例程序所示，对一个volatile变量的单个读/写操作，与对一个普通变量的读/写操作使用同一个监视器锁来同步，它们之间的执行效果相同。
监视器锁的happens-before规则保证释放监视器和获取监视器的两个线程之间的内存可见性，这意味着对一个volatile变量的读，总是能看到（任意线程）对这个volatile变量最后的写入。
监视器锁的语义决定了临界区代码的执行具有原子性。这意味着即使是64位的long型和double型变量，只要它是volatile变量，对该变量的读写就将具有原子性。如果是多个volatile操作或类似于volatile++这种复合操作，这些操作整体上不具有原子性。
简而言之，volatile变量自身具有下列特性：
volatile变量的读，总是能看到（任意线程）对这个volatile变量最后的写入。volatile变量的读/写具有原子性，但类似于volatile++这种复合操作不具有原子性。volatile的简单变量如果当前值由该变量以前的值相关，那么volatile关键字不起作用，也就是说如下的表达式都不是原子操作。1
2n=n+1 ;
n++;
只有当变量的值和自身上一个值无关时对该变量的操作才是原子级别的，如n = m + 1，这个就是原子级别的。
在并发编程中，我们需要处理两个关键问题：线程之间如何通信及线程之间如何同步。通信是指线程之间以何种机制来交换信息。在命令式编程中，线程之间的通信机制有两种：共享内存和消息传递。
在共享内存的并发模型里，线程之间共享程序的公共状态，线程之间通过写-读内存中的公共状态来隐式进行通信。
在消息传递的并发模型里，线程之间没有公共状态，线程之间必须通过明确的发送消息来显式进行通信。
同步是指程序用于控制不同线程之间操作发生相对顺序的机制。在共享内存并发模型里，同步是显式进行的。程序员必须显式指定某个方法或某段代码需要在线程之间互斥执行。在消息传递的并发模型里，由于消息的发送必须在消息的接收之前，因此同步是隐式进行的。
Java的并发采用的是共享内存模型（主内存共享），Java线程之间的通信总是隐式进行，整个通信过程对程序员完全透明。如果编写多线程程序的Java程序员不理解隐式进行的线程之间通信的工作机制，很可能会遇到各种奇怪的内存可见性问题。
转帖：一致性哈希算法
Consistent Hashing算法早在1997年就在论文《Consistent hashing and random trees》 (https://dl.acm.org/citation.cfm?id=258660)中被提出，目前在cache系统中应用越来越广泛。
比如你有N个cache服务器（后面简称cache），那么如何将一个对象object映射到N个cache 上呢，你很可能会采用类似下面的通用方法计算object的hash值，然后均匀的映射到到N个cache；hash(object)%N
一切都运行正常，再考虑如下的两种情况；
hash(object)%(N-1)。N+1台，映射公式变成了hash(object)%(N+1)意味着什么？这意味着突然之间几乎所有的cache都失效了。对于服务器而言，这是一场灾难，洪水般的访问都会直接冲向后台服务器；
再来考虑第三个问题，由于硬件能力越来越强，你可能想让后面添加的节点多做点活，显然上面的 hash算法也做不到。
有什么方法可以改变这个状况呢，这就是Consistent Hashing。
有很多个无序的数，怎么选出其中最大的若干个数？
即，从n个数中选出最大的K个数。
先假设元素的数量不大，例如在几千个左右，在这种情况下，我们就排序吧。
在这里，快速排序或堆排序都是不错的选择，他们的平均时间复杂度都是$O(n\log_2n)$，然后取出前K个，O(K)。
总的时间复杂度仍然是$O(n\log_2n)$。
可以注意到，即便是K=1的情况，上面的算法复杂度仍然是$O(n\log_2n)$，而显然，我们可以通过n-1此的比较和交换得到结果，不需要对整个数组进行排序。
要避免做后面n-K个数的排序，可以使用部分排序算法，选择排序和冒泡排序都是不错的选择。
把n个数中的前K个数排序出来，复杂度是O(n*K)。
哪一个更好呢？$O(n\log_2n)$和O(n*K)？这取决于K的大小，在K<$\log_2n$的情况下，可以选择部分排序。
回忆一下快速排序，快排中的每一步，都是将数据分为两组，其中一组的任何数都小于另一组中的任何数，不断地对数据进行分割直到不能再分即完成排序。
假设n个数存储在数组S中，从S中找出一个元素X，它把数组分为比它大的和比它小的两部分，假设比它大的一部分数组是$S_{max}$，比它小的部分是$S_{min}$。
这时有两种可能：
这样递归下去，问题的规模不断地变小，平均时间复杂度O(n * $\log_2K$)。
Java技术允许使用finalize()在垃圾收集器将对象从内存中清除出去之前做必要的清理工作。
这个方法是由垃圾收集器在确定这个对象没有被引用时，对这个对象调用的。它是在Object类中定义的，因此所有的类都继承了它。子类覆盖finalize()以整理系统资源或者执行其他清理工作（要不然会引起资源泄露，有可能导致程序崩溃）。finalize()是在垃圾收集器删除对象之前被自动调用的。
垃圾收集器只知道释放那些由new分配的内存，所以不知道如何释放对象的“特殊”内存。为解决这个问题，Java提供了一个名为finalize()，它的工作原理应该是这样的：一旦垃圾收集器准备好释放对象占用的存储空间，它首先调用finalize()，而且只有在下一次垃圾收集过程中，才会真正回收对象的内存（垃圾回收需要2次）。
所以如果使用finalize()，就可以在垃圾收集期间进行一些重要的清除或清扫工作(如关闭流等操作)。但JVM(Java虚拟机)不保证此方法总被调用。finalize()抛出的未捕获异常只会导致该对象的finalize()执行退出。
用户可以自己调用对象的finalize()，但是这种调用是正常的方法调用，和对象的销毁过程无关。
一个简单的对象生命周期为，Unfinalized、Finalizable、Finalized、Reclaimed。
在对象的销毁过程中，按照对象的finalize()的执行情况，可以分为以下几种，系统会记录对象的对应状态。
没有执行finalize()，系统也不准备执行。
可以执行finalize()了，系统会在随后的某个时间执行finalize。
该对象的finalize()已经被执行了。
GC怎么来保持对finalizable()的对象的追踪呢。GC有一个Queue，叫做F-Queue，所有对象在变为finalizable的时候会加入到该Queue，然后等待GC执行它的finalize()。
这时我们引入了对对象的另外一种记录分类，系统可以检查到一个对象属于哪一种：
从活动的对象引用链可以到达的对象。包括所有线程当前栈的局部变量，所有的静态变量等等。
除了reachable外，从F-Queue可以通过引用到达的对象。
其它的对象，不可达对象。
Reachable+Unfinalized（没有执行finalize()，对象可达）走向死亡之路的。Reachable状态变到F-Reachable（进入F-Queue，对象变成finalizable状态）或者Unreachable状态。Reachable+Unfinalized时，GC会把它移入F-Queue，状态变为F-Reachable+Finalizable（进入F-Queue，可达，finalizable状态）。F-Queue中拿到一个Finalizable的对象，标记它为Finalized，然后执行它的finalize()，由于该对象在这个线程中又可达了，于是该对象变成Reachable了（并且Finalized）。而finalize()执行时，又有可能把其它的F-Reachable（进入F-Queue，finalizable状态）的对象变为一个Reachable的，这个叫做对象再生。Unreachable+Unfinalized时，如果该对象使用的是默认的Object的finalize，或者虽然重写了，但是新的实现什么也不干（子类覆写一个空方法）。为了性能，GC可以把该对象之间变到Reclaimed状态直接销毁，而不用加入到F-Queue等待GC做进一步处理。（不可达，不执行finalize()）finalize只至多执行一次，一旦对象变为Finalized（执行过finalized()），就怎么也不会在回到F-Queue（finalizable状态）去了。当然没有机会再执行finalize了。Unreachable+Finalized时，该对象离真正的死亡不远了。GC可以安全的回收该对象的内存了。进入Reclaimed。给定N个物品和一个容量为C的背包，物品i的重量是Wi，其价值为Vi，背包问题是如何选择入背包的物品，使得装入背包的物品的总价值最大，但不能超过总容量。在背包问题中可以将物品的一部分装入背包（物品可以拆分的装入背包），但不能重复装入。
用贪心法求解背包问题的关键是如何选定贪心策略，使得按照一定的顺序选择每个物品，并尽可能的装入背包，直到背包装满。
至少有三种看似合适的贪心策略。
因为这可以尽可能快的增加背包的总价值，但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗的太快，使得装入背包的物品个数减少，从而不能保证目标函数达到最大。
因为这可以装入尽可能多的物品，从而增加背包的总价值。但是，虽然每一步选择使背包的容量消耗的慢了，但背包的价值却没能保证迅速的增长，从而不能保证目标函数达到最大。
最大价值和最大重量两种贪心策略或者只考虑背包价值的增长，或者只考虑背包容量的消耗，而为了求得背包问题的最优解，需要在背包价值增长和背包容量消耗二者之间寻找平衡。正确的贪心策略是选择单位重量价值最大的物品。
例如：有三个物品，其重量分别为{20,30,10}，价值分别为{60,120,50}，背包的容量为50，应用三种贪心策略装入背包的物品和获得的价值如下图所示：
基于JDK7
Java -verbose:gc中参数-verbose:gc表示输出虚拟机中GC的详细情况。
使用后输出如下：[Full GC 168K->97K(1984K)，0.0253873 secs]
解读如下：箭头前后的数据168K和97K分别表示垃圾收集GC前后所有存活对象使用的内存容量，说明有168K-97K=71K的对象容量被回收，括号内的数据1984K为堆内存的总容量，收集所需要的时间是0.0253873秒（这个时间在每次执行的时候会有所不同）。
通过JVM启动参数设置来启用verbose gc，并指定了名字和gc日志文件存储路径。
Java线程是JVM基础的一部分。你的Java堆空间内存占用不仅仅是由于静态对象和长生命的对象导致，还有可能因为短生命对象。
OutOfMemoryError问题经常被误认为是内存泄露引起。我们经常忽略错误的线程执行模型和它们持有的JVM里的短生命对象，直到它们的执行完成我们才发现。
在这种问题情形下：
你的应用此时被停掉，你很疑惑到底怎么回事。最后，你考虑增加Java堆空间或者寻找哪里有内存泄露，你真的找对路了么？
避免在线程栈大小（虚拟机栈）和Java堆内存占用之间产生混淆是非常重要的。线程栈（虚拟机栈）大小是一种特殊的内存空间，它被JVM用于存储每个方法调用。当一个线程调用方法A，它将这个调用入栈。如果方法A调用方法B，同样也会入栈。一旦方法执行完毕，这个调用便从栈里出栈。
这种线程方法调用会导致Java对象产生，并分配在Java堆里。增加线程栈的大小是没有任何效果的（对象最终在堆得年轻代（Eden）产生）。而调整线程栈大小通常是要处理java.lang.stackoverflowerror错误或者OutOfMemoryError: unable to create new native thread错误的时候才会需要。
设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间$s_i$和一个结束时间$f_i$，且$s_i$<$f_i$。如果选择了活动i，则它在半开时间区间[$s_i$, $f_i$)内占用资源。若区间[$s_i$, $f_i$)与区间[$s_j$, $f_j$)不相交，则称活动i与活动j是相容的。也就是说，当$s_i$≥$f_j$或$s_j$≥$f_i$时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。
假定活动已按结束时间的单调递增顺序排序（小到大排序）：f1 ≤ f2 ≤ f3 ≤....≤ fn-1 ≤ fn
用i代表第i个活动，s[i]代表第i个活动开始时间，f[i]代表第i个活动的结束时间。按照从小到大排序，挑选出结束时间尽量早的活动，并且满足后一个活动的起始时间晚于前一个活动的结束时间，全部找出这些活动就是最大的相容活动子集合。
事实上系统一次检查活动i是否与当前已选择的所有活动相容。若相容活动i加入已选择活动的集合中，否则，不选择活动i，而继续i位置的下一个活动与集合A中活动比较相容性（集合A中的活动也就是上次比较的活动）。若活动i与之相容，则i成为最近加入集合A的活动，并取代活动j的位置（迭代方法）。
每次总是选择具有最早完成时间的相容活动加入集合A中（默认第1个加入集合A中）。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间（因为添加到集合A中的时间最短，剩余的时间就长）。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。
迭代方法的计算过程如下图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。
若被检查的活动i的开始时间$s_i$小于最近选择的活动j的结束时间$f_i$，则不选择活动i，否则选择活动i加入集合A中。
迭代方法的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。
Update your browser to view this website correctly. Update my browser now