CyclicBarrier 使用不当导致死锁问题

先上代码:


import java.util.concurrent.*;

public class App {

	public static ExecutorService pool = Executors.newFixedThreadPool(5);
	public static ExecutorService pool2 = Executors.newCachedThreadPool();

	public static void main(String[] args) {
		// 使用 CyclicBarrier 出现死锁问题
		// new GenTaskUseBarrier(pool, 10).start();
		// 使用 CachedThreadPool 解决 CyclicBarrier 死锁问题
		// new GenTaskUseBarrier(pool2, 10).start();
		// 使用 CountDownLatch 解决 CyclicBarrier 死锁问题
		// new GenTaskUseCountDown(pool, 10).start();

		// 模拟5个并发共享一个线程池
		// new MockConcurrence(pool, 5).start();
	}
}

class MockConcurrence extends Thread {
	ExecutorService pool;
	int count;

	public MockConcurrence(ExecutorService pool, int count) {
		super();
		this.pool = pool;
		this.count = count;
	}

	@Override
	public void run() {
		for (int i = 0; i < count; i++) {
			new GenTaskUseBarrier(pool, 5, false).start();
		}
	}
}

class GenTaskUseCountDown extends Thread {

	ExecutorService pool;

	int taskSize;

	public GenTaskUseCountDown(ExecutorService pool, int taskSize) {
		this.pool = pool;
		this.taskSize = taskSize;
	}

	@Override
	public void run() {
		CountDownLatch latch = new CountDownLatch(taskSize);
		for (int i = 0; i < taskSize; i++) {
			pool.submit(new MyTask(latch));
		}
		try {
			latch.await();
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
		pool.shutdown();
		System.out.println("All task done!");
	}
}

class GenTaskUseBarrier extends Thread {

	ExecutorService pool;

	int taskSize;

	boolean autoClose = true;

	public GenTaskUseBarrier(ExecutorService pool, int taskSize) {
		this.pool = pool;
		this.taskSize = taskSize;
	}

	public GenTaskUseBarrier(ExecutorService pool, int taskSize, boolean autoClose) {
		this(pool, taskSize);
		this.autoClose = autoClose;
	}

	@Override
	public void run() {
		CyclicBarrier barrier = new CyclicBarrier(taskSize, new Runnable() {
			@Override
			public void run() {
				if (autoClose) {
					pool.shutdown();
				}
				System.out.println("All task done!");
			}
		});
		for (int i = 0; i < taskSize; i++)
			pool.submit(new MyTask(barrier));
	}
}

class MyTask extends Thread {

	CyclicBarrier barrier;

	CountDownLatch latch;

	public MyTask(CyclicBarrier barrier) {
		this.barrier = barrier;
	}

	public MyTask(CountDownLatch latch) {
		this.latch = latch;
	}

	@Override
	public void run() {
		try {
			System.out.println("线程" + Thread.currentThread().getName() + "正在执行同一个任务");
			// 以睡眠来模拟几个线程执行一个任务的时间
			Thread.sleep(1000);
			System.out.println("线程" + Thread.currentThread().getName() + "执行任务完成,等待其他线程执行完毕");
			// 用来挂起当前线程,直至所有线程都到达barrier状态再同时执行后续任务;
			if (barrier != null) {
				barrier.await();
			}
			if (latch != null) {
				latch.countDown();
			}
		} catch (InterruptedException e) {
			e.printStackTrace();
		} catch (BrokenBarrierException e) {
			e.printStackTrace();
		}
		System.out.println("所有线程写入完毕");

	}

}

输出结果:

线程pool-1-thread-3正在执行同一个任务
线程pool-1-thread-4正在执行同一个任务
线程pool-1-thread-2正在执行同一个任务
线程pool-1-thread-1正在执行同一个任务
线程pool-1-thread-5正在执行同一个任务
线程pool-1-thread-2执行任务完成,等待其他线程执行完毕
线程pool-1-thread-3执行任务完成,等待其他线程执行完毕
线程pool-1-thread-4执行任务完成,等待其他线程执行完毕
线程pool-1-thread-1执行任务完成,等待其他线程执行完毕
线程pool-1-thread-5执行任务完成,等待其他线程执行完毕

//卡死在这个地方

原因分析:
1.提交了10个任务,但是只有5个调度线程、每次只能执行一个解析任务;
2.前面5个任务执行后由于调用了 barrier.await 被阻塞了,需要等待其他两个任务都达到栅栏状态;
3.前面5个任务的线程被阻塞了,导致没有空闲的调度线程去执行另外两个任务;
4.前面5个任务等待其他两个任务的栅栏唤醒,而其他5个任务则等待第一个任务的线程资源,从而进入死锁状态。

解决方案 [修改Main方法注释 可以逐个测试]:
1、调整线程池调度线程个数,提交多少个任务开多少个资源,如果并发调用的时候共享同一个线程池调度非常容易出现问题,一定要小心
2、使用 CachedThreadPool,或者自定义线程池
3、更换协作工具类为 CountDownLatch,将主线程阻塞直到所有的解析任务都被执行完成。

缓存的使用和设计

原文地址 [本文整理发布]

缓存的一些基本常识

  • Cache(缓存): 从cpu的一级和二级缓存、Internet的DNS、到浏览器缓存都可以看做是一种缓存。(存贮数据(使用频繁的数据)的临时地方,因为取原始数据的代价太大了,所以我可以取得快一些)
  • Cache hit(缓存命中) Cahe miss(缓存未命中)

  • 缓存算法:缓存容量超过预设,如何踢掉“无用”的数据。例如:LRU(Least Recently Used) FIFO(First Input First Output)Least Frequently Used(LFU) 等等

  • System-of-Record(真实数据源): 例如关系型数据库、其他持久性系统等等。 也有英文书叫做authority data(权威数据)

  • serialization-and-deserialization(序列化与反序列化):可以参考:序列化与反序列化(美团工程师写的,非常棒的文章)
    serialization-and-deserialization

  • Scale Up (垂直扩容) 和 Scale out (水平扩容), 驴拉车,通常不是把一头驴养壮(有极限),而通常是一群驴去拉(当然每个个体也不能太差)。

    64258e75-ad29-32ef-ac55-45d95278ff0a

  • Write-through 和 write-behind
    154e49f4-f223-3b4f-9346-fa378dd2efd1

  • 阿姆而达定律:用于计算缓存加速比

  • LocalCache(独立式): 例如Ehcache、BigMemory Go
    (1) 缓存和应用在一个JVM中。
    (2) 缓存间是不通信的,独立的。
    (3) 弱一致性。

  • Standalone(单机):
    (1) 缓存和应用是独立部署的。
    (2) 缓存可以是单台。(例如memcache/redis单机等等)
    (3) 强一致性
    (4) 无高可用、无分布式。
    (5) 跨进程、跨网络

  • Distributed(分布式):例如Redis-Cluster, memcache集群等等
    (1) 缓存和应用是独立部署的。
    (2) 多个实例。(例如memcache/redis等等)
    (3) 强一致性或者最终一致性
    (4) 支持Scale Out、高可用。
    (5) 跨进程、跨网络

  • Replicated(复制式): 缓存数据时同时存放在多个应用节点的,数据复制和失效的事件以同步或者异步的形式在各个集群节点间传播。(也是弱一致性)这种用的不太多。

  • 数据层访问速度
    082dfcc7-1a06-3116-886f-055d4af98cf8
    继续阅读“缓存的使用和设计”

Memcached 总结

总结 memcached 教程 [必看]

Memcached 二三事 [版权归 原文链接,本文修改一些引用资源地址]

实际应用Memcached时,我们遇到的很多问题都是因为不了解其内存分配机制所致,下面就让我们以此为开端来开始Memcached之旅吧!官方wiki

为了规避内存碎片问题,Memcached采用了名为SlabAllocator的内存分配机制。内存以Page为单位来分配,每个Page分给一个特定长度的Slab来使用,每个Slab包含若干个特定长度的Chunk。实际保存数据时,会根据数据的大小选择一个最贴切的Slab,并把数据保存在对应的Chunk中。如果某个Slab没有剩余的Chunk了,系统便会给这个Slab分配一个新的Page以供使用,如果没有Page可用,系统就会触发LRU机制,通过删除冷数据来为新数据腾出空间,这里有一点需要注意的是:LRU不是全局的,而是针对Slab而言的。

一个Slab可以有多个Page,这就好比在古代一个男人可以娶多个女人;一旦一个Page被分给某个Slab后,它便对Slab至死不渝,犹如古代那些贞洁的女人。但是女人的数量毕竟是有限的,所以一旦一些男人娶得多了,必然另一些男人就只剩下咽口水的份儿,这在很大程度上增加了社会的不稳定因素,于是乎我们要解放女性。

好在Memcached已经意识到解放女性的重要性,新版本中Page可以调配给其它的Slab:

memcached -o slab_reassign,slab_automove

换句话说:女人可以改嫁了!这方面,其实Memcached的儿子Twemcache革命得更彻底,他甚至写了一篇大字报,以事实为依据,痛斥老子的无能,有兴趣的可以继续阅读:Random Eviciton vs Slab Automove

了解Memcached内存使用情况的最佳工具是:Memcached-tool。如果我们发现某个Slab的Evicted不为零,则说明这个Slab已经出现了LRU的情况,这通常是个危险的信号,但也不能一概而论,需要结合Evict_Time来做进一步判断。Replacing the cache replacement algorithm in memcached

在Memcached的使用过程中,除了会遇到内存分配机制相关的问题,还有很多稀奇古怪的问题等着你呢,下面我选出几个有代表性的问题来逐一说明:

Cache失效后的拥堵问题

通常我们会为两种数据做Cache,一种是热数据,也就是说短时间内有很多人访问的数据;另一种是高成本的数据,也就说查询很很耗时的数据。当这些数据过期的瞬间,如果大量请求同时到达,那么它们会一起请求后端重建Cache,造成拥堵问题,就好象在北京上班做地铁似的,英文称之为:stampeding herd,老外这里的用词还是很形象的。

一般有如下几种解决思路可供选择:

首先,我们可以主动更新Cache。前端程序里不涉及重建Cache的职责,所有相关逻辑都由后端独立的程序(比如CRON脚本)来完成,但此方法并不适应所有的需求。

其次,我们可以通过加锁来解决问题。以PHP为例,伪代码大致如下:

<?php
function query()
{
    $data = $cache->get($key);

    if ($cache->getResultCode() == Memcached::RES_NOTFOUND) {
        if ($cache->add($lockKey, $lockData, $lockExpiration)) {
            $data = $db->query();
            $cache->set($key, $data, $expiration);
            $cache->delete($lockKey);
        } else {
            sleep($interval);
            $data = query();
        }
    }

    return $data;
}
?>

不过这里有一个问题,代码里用到了sleep,也就是说客户端会卡住一段时间,就拿PHP来说吧,即便这段时间非常短暂,也有可能堵塞所有的FPM进程,从而使服务中断。于是又有人想出了柔性过期的解决方案,所谓柔性过期,指的是设置一个相对较长的过期时间,或者干脆不再直接设置数据的过期时间,取而代之的是把真正的过期时间嵌入到数据中去,查询时再判断,如果数据过期就加锁重建,如果加锁失败,不再sleep,而是直接返回旧数据,以PHP为例,伪代码大致如下:

<?php
function query()
{
    $data = $cache->get($key);

    if (isset($data['expiration']) && $data['expiration'] < $now) {
        if ($cache->add($lockKey, $lockData, $lockExpiration)) {
            $data = $db->query();
            $data['expiration'] = $expiration;
            $cache->set($key, $data);
            $cache->delete($lockKey);
        }
    }

    return $data;
}
?>

问题到这里似乎已经圆满解决了,且慢!还有一些特殊情况没有考虑到:设想一下服务重启;或者某个Cache里原本没有的冷数据因为某些情况突然转换成热数据;又或者由于LRU机制导致某些键被意外删除,等等,这些情况都可能会让上面的方法失效,因为在这些情况里就不存在所谓的旧数据,等待用户的将是一个空页面。

好在我们还有Gearman这根救命稻草。当需要更新Cache的时候,我们不再直接查询数据库,而是把任务抛给Gearman来处理,当并发量比较大的时候,Gearman内部的优化可以保证相同的请求只查询一次后端数据库,以PHP为例,伪代码大致如下:

<?php

function query()
{
    $data = $cache->get($key);
    //说明:如果多个并发请求的$unique参数一样,那么实际上Gearman只会请求一次。
    if ($cache->getResultCode() == Memcached::RES_NOTFOUND) {
        $data = $gearman->do($function, $workload, $unique);
        $cache->set($key, $data, $expiration);
    }

    return $data;
}
?>

Multiget的无底洞问题

Facebook在Memcached的实际应用中,发现了Multiget无底洞问题,具体表现为:出于效率的考虑,很多Memcached应用都已Multiget操作为主,随着访问量的增加,系统负载捉襟见肘,遇到此类问题,直觉通常都是通过增加服务器来提升系统性能,但是在实际操作中却发现问题并不简单,新加的服务器好像被扔到了无底洞里一样毫无效果。

为什么会这样?让我们来模拟一下案发经过,看看到底发生了什么:

我们使用Multiget一次性获取100个键对应的数据,系统最初只有一台Memcached服务器,随着访问量的增加,系统负载捉襟见肘,于是我们又增加了一台Memcached服务器,数据散列到两台服务器上,开始那100个键在两台服务器上各有50个,问题就在这里:原本只要访问一台服务器就能获取的数据,现在要访问两台服务器才能获取,服务器加的越多,需要访问的服务器就越多,所以问题不会改善,甚至还会恶化。

不过,作为被告方,Memcached官方开发人员对此进行了辩护:

请求多台服务器并不是问题的症结,真正的原因在于客户端在请求多台服务器时是并行的还是串行的!问题是很多客户端,包括Libmemcached在内,在处理Multiget多服务器请求时,使用的是串行的方式!也就是说,先请求一台服务器,然后等待响应结果,接着请求另一台,结果导致客户端操作时间累加,请求堆积,性能下降。

如何解决这个棘手的问题呢?只要保证Multiget中的键只出现在一台服务器上即可!比如说用户名字(user:foo:name),用户年龄(user:foo:age)等数据在散列到多台服务器上时,不应按照完整的键名(user:foo:name和user:foo:age)来散列的,而应按照特殊的键(foo)来散列的,这样就保证了相关的键只出现在一台服务器上。以PHP的 Memcached客户端为例,有getMultiByKey和setMultiByKey可供使用。

Nagle和DelayedAcknowledgment的延迟问题

老实说,这个问题和Memcached没有半毛钱关系,任何网络应用都有可能会碰到这个问题,但是鉴于很多人在写Memcached程序的时候会遇到这个问题,所以还是拿出来聊一聊,在这之前我们先来看看Nagle和DelayedAcknowledgment的含义:

先看看Nagle:

假如需要频繁的发送一些小包数据,比如说1个字节,以IPv4为例的话,则每个包都要附带40字节的头,也就是说,总计41个字节的数据里,其中只有1个字节是我们需要的数据。为了解决这个问题,出现了Nagle算法。它规定:如果包的大小满足MSS,那么可以立即发送,否则数据会被放到缓冲区,等到已经发送的包被确认了之后才能继续发送。通过这样的规定,可以降低网络里小包的数量,从而提升网络性能。

再看看DelayedAcknowledgment:

假如需要单独确认每一个包的话,那么网络中将会充斥着无数的ACK,从而降低了网络性能。为了解决这个问题,DelayedAcknowledgment规定:不再针对单个包发送ACK,而是一次确认两个包,或者在发送响应数据的同时捎带着发送ACK,又或者触发超时时间后再发送ACK。通过这样的规定,可以降低网络里ACK的数量,从而提升网络性能。

Nagle和DelayedAcknowledgment虽然都是好心,但是它们在一起的时候却会办坏事。下面我们举例说说Nagle和DelayedAcknowledgment是如何产生延迟问题的:

客户端需要向服务端传输数据,传输前数据被分为ABCD四个包,其中ABC三个包的大小都是MSS,而D的大小则小于MSS,交互过程如下:

首先,因为客户端的ABC三个包的大小都是MSS,所以它们可以耗无障碍的发送,服务端由于DelayedAcknowledgment的存在,会把AB两个包放在一起来发送ACK,但是却不会单独为C包发送ACK。

接着,因为客户端的D包小于MSS,并且C包尚未被确认,所以D包不会立即发送,而被放到缓冲区里延迟发送。

最后,服务端触发了超时阈值,终于为C包发送了ACK,因为不存在未被确认的包了,所以即便D包小于MSS,也总算熬出头了,可以发送了,服务端在收到了所有的包之后就可以发送响应数据了。

说到这里,假如你认为自己已经理解了这个问题的来龙去脉,那么我们尝试改变一下前提条件:传输前数据被分为ABCDE五个包,其中ABCD四个包的大小都是MSS,而E的大小则小于MSS。换句话说,满足MSS的完整包的个数是偶数个,而不是前面所说的奇数个,此时又会出现什么情况呢?答案我就不说了,留给大家自己思考。

知道了问题的原委,解决起来就简单了:我们只要设置socket选项为TCP_NODELAY即可,这样就可以禁用Nagle,以PHP为例:

<?php
$memcached->setOption(Memcached::OPT_TCP_NODELAY, true);
?>

如果大家意犹未尽,可以继续浏览:TCP Performance problems caused by interaction between Nagle’s Algorithm and Delayed ACK。

一次Memcached使用问题

收到群里反馈很多PHP请求执行超时,服务已经不可用。

查看服务器监控数据

发现 CPU 负载 在那段时间一直爬坡。 查询fpm slow 日志 发现请求都卡在了 memcache get 的方法上面。

发现出问题的请求有一个方法 频繁的读写一个key 这个 key 保存的内容 内存已经大于1MB, 一秒内有 500 多个请求,同时读写会导致memcache 的性能急剧下降。

自己写代码重现这个问题:
php 脚本 test-memcached.php:

<?php
$time_start = microtime(true);

$ac = new Memcached();
$ac->addServer('localhost', 11211);

#$ac->setOption(Memcached::OPT_SOCKET_SEND_SIZE, 1024*512);
#$ac->setOption(Memcached::OPT_SOCKET_RECV_SIZE, 1024*512);
#$ac->setOption(Memcached::OPT_RECV_TIMEOUT, 5);
#$ac->setOption(Memcached::OPT_SEND_TIMEOUT, 5);

$data = [];

for($i = 0; $i<30000; $i++){
  $data[] = md5($i);
}

$r = $ac->set('key', $data, 3600);
$set_time_end = microtime(true);
$set_time = $set_time_end - $time_start;
echo "Set Key Done in $set_time seconds \n";
$result = $ac->get('key');
$read_time_end = microtime(true);
$read_time = $read_time_end - $time_start;
echo "Read key Done in $read_time seconds \n";
$time_end = microtime(true);
$time = $time_end - $time_start;
echo "Did nothing in $time seconds\n";
?>

shell 测试脚本:

#!/bin/bash
date
for i in `seq 1 300`
do
{
 php test-memcached.php
 sleep 1
}&
done
wait #等待执行完成
date

分别修改 memcache key 保存内容的大小得到结果:

A:

for($i = 0; $i<30000; $i++){
  $data[] = md5($i);
}

B:

for($i = 0; $i<3; $i++){
  $data[] = md5($i);
}

测试结果:

A:

Did nothing in 18.769073009491 seconds
Did nothing in 14.950340032578 seconds
Did nothing in 19.823235034943 seconds
Did nothing in 20.014719009399 seconds
Did nothing in 20.894814014435 seconds
Did nothing in 20.827455997467 seconds
Did nothing in 15.345555067062 seconds
Did nothing in 18.984731197357 seconds
Did nothing in 21.08841586113 seconds

B:

Did nothing in 0.39238500595093 seconds
Did nothing in 0.42710494995117 seconds
Did nothing in 0.34245300292969 seconds
Did nothing in 0.084210872650146 seconds
Did nothing in 0.41426110267639 seconds
Did nothing in 0.12554693222046 seconds
Did nothing in 0.10487604141235 seconds
Did nothing in 0.60212993621826 seconds
Did nothing in 0.054439067840576 seconds
Did nothing in 0.11286902427673 seconds
Did nothing in 0.69583892822266 seconds
Did nothing in 0.14684200286865 seconds
Did nothing in 0.082473993301392 seconds
Did nothing in 0.34351587295532 seconds
Did nothing in 0.10698294639587 seconds


看结果可以得知 但 memcache 保存的内容变大的时候速度会非常慢,所以使用memcache 的时候要注意缓存值得大小。

memcache 缓存值最大大小是1M 引用 Oracle 网站的一个 FAQ

The default maximum object size is 1MB. In memcached 1.4.2 and later, you can change the maximum size of an object using the -I command line option.

For versions before this, to increase this size, you have to re-compile memcached. You can modify the value of the POWER_BLOCK within the slabs.c file within the source.

In memcached 1.4.2 and higher, you can configure the maximum supported object size by using the -I command-line option. For example, to increase the maximum object size to 5MB:

$ memcached -I 5m

If an object is larger than the maximum object size, you must manually split it. memcached is very simple: you give it a key and some data, it tries to cache it in RAM. If you try to store more than the default maximum size, the value is just truncated for speed reasons.

出现服务不可用的一个重要原因也有写缓存的次数和读缓存次数一样多。

最后修改测试脚本 依然保存很大的缓存值,但是只写入一次,测试并发的读取,基本都可以在1秒左右的读取到数据。

结论:
1.使用memcache的要注意缓存内容的大小,不要保存太大的内容在一个key上
2.缓存是读的次数远远大于写的次数,如果代码中发现写缓存的次数和读缓存的次数一样的时候要提高警惕
3.千万不要在数据库事务未提交的时候删除缓存

QA:
1.为啥使用MD5字符串?
因为memcache会自动压缩内容,如果用普通重复字符串测试效果不明显,线上出现问题的场景也是MD5串的缓存值,可以开启和关闭压缩选项?

测试代码下载

打印杨辉三角

构造杨辉三角逻辑并不难,主要打印格式的对齐比较困难.

public class Main {

	/**
	 * 计算行应该占得宽度
	 * 每个数字额外加了一个空格,数字的宽度加空格的宽度
	 * @param lastIntegers
	 * @return
	 */
	static int width_of(int[] lastIntegers) {
		int width = 0;
		int length = 0;
		for (int lastInteger : lastIntegers) {
			if (lastInteger > 0) {
				width += numWidth(lastInteger);
				length++;
			}
		}
		width += length;
		return width;
	}

	static int numWidth(int num) {
		int count = 0;
		while (num > 0) {
			num = num / 10;
			count++;
		}
		return count;
	}

	public static void main(String[] args) {
		int n = 10;
		int[][] result = new int[n][n];
		result[0][0] = 1;
		result[1][0] = 1;
		result[1][1] = 1;
		//构造杨辉三角
		for (int i = 2; i < n; i++) {
			result[i][0] = 1;
			result[i][i] = 1;
			for (int j = 1; j <= i - 1; j++) {
				result[i][j] = result[i - 1][j - 1] + result[i - 1][j];
			}
		}
		int maxWidth = width_of(result[n - 1]);
		for (int i = 0; i < n; i++) {
			int[] temp = result[i];
			int temp_width = width_of(temp);
			int wihteBlankLength = (maxWidth - temp_width) / 2;
			for (int k = 0; k < wihteBlankLength; k++) {
				System.out.print(" ");
			}
			for (int j = 0; j < temp.length; j++) {
				if (temp[j] > 0)
					System.out.print(String.format("%d", temp[j]) + " ");
			}
			System.out.println();
		}
	}

}

JAVA 引用学习

JDK1.2 之前,Java 中引用的定义很传统:如果 reference 类型的数据存储的数值代表的是另一块内存的起始地址,就称这块内存代表一个引用。

JDK1.2 以后,Java 对引用的概念进行了扩充,将引用分为强引用、软引用、弱引用、虚引用四种(引用强度逐渐减弱)

1.强引用

以前我们使用的大部分引用实际上都是强引用,这是使用最普遍的引用。如果一个对象具有强引用,那就类似于必不可少的生活用品,垃圾回收器绝不会回收它。当内存空间不足,Java 虚拟机宁愿抛出 OutOfMemoryError 错误,使程序异常终止,也不会靠随意回收具有强引用的对象来解决内存不足问题。

2.软引用(SoftReference)

如果一个对象只具有软引用,那就类似于可有可无的生活用品。如果内存空间足够,垃圾回收器就不会回收它,如果内存空间不足了,就会回收这些对象的内存。只要垃圾回收器没有回收它,该对象就可以被程序使用。软引用可用来实现内存敏感的高速缓存。

软引用可以和一个引用队列(ReferenceQueue)联合使用,如果软引用所引用的对象被垃圾回收,JAVA 虚拟机就会把这个软引用加入到与之关联的引用队列中。

3.弱引用(WeakReference)

如果一个对象只具有弱引用,那就类似于可有可无的生活用品。弱引用与软引用的区别在于:只具有弱引用的对象拥有更短暂的生命周期。在垃圾回收器线程扫描它所管辖的内存区域的过程中,一旦发现了只具有弱引用的对象,不管当前内存空间足够与否,都会回收它的内存。不过,由于垃圾回收器是一个优先级很低的线程, 因此不一定会很快发现那些只具有弱引用的对象。

弱引用可以和一个引用队列(ReferenceQueue)联合使用,如果弱引用所引用的对象被垃圾回收,Java 虚拟机就会把这个弱引用加入到与之关联的引用队列中。

4.虚引用(PhantomReference)

“虚引用”顾名思义,就是形同虚设,与其他几种引用都不同,虚引用并不会决定对象的生命周期。如果一个对象仅持有虚引用,那么它就和没有任何引用一样,在任何时候都可能被垃圾回收。

虚引用主要用来跟踪对象被垃圾回收的活动。

虚引用与软引用和弱引用的一个区别在于: 虚引用必须和引用队列(ReferenceQueue)联合使用。当垃圾回收器准备回收一个对象时,如果发现它还有虚引用,就会在回收对象的内存之前,把这个虚引用加入到与之关联的引用队列中。程序可以通过判断引用队列中是否已经加入了虚引用,来了解被引用的对象是否将要被垃圾回收。程序如果发现某个虚引用已经被加入到引用队列,那么就可以在所引用的对象的内存被回收之前采取必要的行动。

特别注意,在程序设计中一般很少使用弱引用与虚引用,使用软引用的情况较多,这是因为软引用可以加速 JVM 对垃圾内存的回收速度,可以维护系统的运行安全,防止内存溢出(OutOfMemory)等问题的产生。

继续阅读“JAVA 引用学习”

斐波那契数列


import java.util.HashMap;
import java.util.Map;

public class Fibonacci {

	// F(0)=0, F(1)=1, n>1时,F(n)=F(n-1)+F(n-2)。
	public static int fibonacci(int n) {
		if (n == 0 || n == 1) {
			return n;
		}
		return fibonacci(n - 1) + fibonacci(n - 2);
	}

	/**
	 * 缓存执行结果
	 */
	static Map<Integer, Integer> cacheList = new HashMap<>();
	static {
		cacheList.put(0, 0);
		cacheList.put(1, 1);
	}

	public static int fibonacciUseCache(int n) {
		int r = cacheList.containsKey(n) ? cacheList.get(n) : 0;
		if (r == 0) {
			r = fibonacci(n - 1) + fibonacci(n - 2);
		}
		cacheList.put(n, r);
		return r;
	}

	/**
	 * 动态规划:从底部开始解决问题,将所有小问题解决掉,然后合并成一个整体解决方案,从而解决掉整个大问题;
	 * 递归:从顶部开始将问题分解,通过解决掉所有分解的小问题来解决整个问题;
	 * 
	 * @param n
	 * @return
	 */
	public static int fibonacciDynamic(int n) {
		int current = 0;
		int next = 1;
		int temp;
		for (int i = 0; i < n; i++) {
			temp = current;
			current = next;
			next += temp;
		}
		return current;
	}

	public static int fibonacciDynamic2(int n) {
		int a = 1; // n-1
		int b = 0; // n-2
		for (int i = 0; i < n; i++) {
			if (i > 1) {
				int newA = a + b;
				int newB = a;
				b = newB;
				a = newA;
			}
		}
		return a + b;
	}

	/**
	 * 尾调用优化
	 * @param n
	 * @param curr
	 * @param next
	 * @return
	 */
	public static int fibonacciWithNext(int n, int curr, int next) {
		if (n == 0) {
			return 0;
		}
		if(n==1){
			return next;
		}
		return fibonacciWithNext(n - 1, next, curr + next);
	}

	public static void main(String[] args) {
		System.out.println(fibonacciUseCache(15));
		System.out.println(fibonacciDynamic(15));
		System.out.println(fibonacciDynamic2(15));
		System.out.println(fibonacciWithNext(15, 0, 1));
	}

}


ThreadLocal可能引起的内存泄露

threadlocal里面使用了一个存在弱引用的map,当释放掉threadlocal的强引用以后,map里面的value却没有被回收.而这块value永远不会被访问到了. 所以存在着内存泄露.
** 最好的做法是将调用threadlocal的remove方法.**: 把当前ThreadLocal从当前线程的ThreadLocalMap中移除。(包括key,value)

/**
 * Remove the entry for key.
 */
private void remove(ThreadLocal<?> key) {
    Entry[] tab = table;
    int len = tab.length;
    int i = key.threadLocalHashCode & (len-1);
    for (Entry e = tab[i];
         e != null;
         e = tab[i = nextIndex(i, len)]) {
        if (e.get() == key) {
            e.clear();// 将entry的对threadlocal的引用赋值为null
            expungeStaleEntry(i);//将 entry的value赋值为null
            return;
        }
    }
}

在threadlocal的生命周期中,都存在这些引用. 看下图: 实线代表强引用,虚线代表弱引用

继续阅读“ThreadLocal可能引起的内存泄露”

StampedLock 学习

StampedLock是并发包里面jdk8版本新增的一个锁,
该锁提供了三种模式的读写控制,三种模式分别如下:

      写锁writeLock,是个排它锁或者叫独占锁,同时只有一个线程可以获取该锁,当一个线程获取该锁后,其它请求的线程必须等待,当目前没有线程持有读锁或者写锁的时候才可以获取到该锁,请求该锁成功后会返回一个stamp票据变量用来表示该锁的版本,当释放该锁时候需要unlockWrite并传递参数stamp。
      悲观读锁readLock,是个共享锁,在没有线程获取独占写锁的情况下,同时多个线程可以获取该锁,如果已经有线程持有写锁,其他线程请求获取该读锁会被阻塞。这里讲的悲观其实是参考数据库中的乐观悲观锁的,这里说的悲观是说在具体操作数据前悲观的认为其他线程可能要对自己操作的数据进行修改,所以需要先对数据加锁,这是在读少写多的情况下的一种考虑,请求该锁成功后会返回一个stamp票据变量用来表示该锁的版本,当释放该锁时候需要unlockRead并传递参数stamp。
      乐观读锁tryOptimisticRead,是相对于悲观锁来说的,在操作数据前并没有通过CAS设置锁的状态,如果当前没有线程持有写锁,则简单的返回一个非0的stamp版本信息,获取该stamp后在具体操作数据前还需要调用validate验证下该stamp是否已经不可用,也就是看当调用tryOptimisticRead返回stamp后到到当前时间间是否有其他线程持有了写锁,如果是那么validate会返回0,否者就可以使用该stamp版本的锁对数据进行操作。由于tryOptimisticRead并没有使用CAS设置锁状态所以不需要显示的释放该锁。该锁的一个特点是适用于读多写少的场景,因为获取读锁只是使用与或操作进行检验,不涉及CAS操作,所以效率会高很多,但是同时由于没有使用真正的锁,在保证数据一致性上需要拷贝一份要操作的变量到方法栈,并且在操作数据时候可能其他写线程已经修改了数据,而我们操作的是方法栈里面的数据,也就是一个快照,所以最多返回的不是最新的数据,但是一致性还是得到保障的。

一个小的案例:
继续阅读“StampedLock 学习”