分类目录: Java

关于Java中Random的一些使用细节

Random类相信大家都不陌生,但是必须掌握一些特定的细节才能在要求较高的场合用好该变量。这里分析一个多线程环境下Random的使用。

现在面临一个问题:有多个线程需要按照随机的方式取一个令牌,尽量让每个线程取得的令牌不一样,可以认为令牌就是一个数字,如1~100之内的一个整数。那么怎样实现能最好的解决这个问题呢?首先想到的是用一个同步的变量,使用一个getAndIncrement接口,这样每个线程调用这个接口时都能获得一个与其他同时访问该接口不一样的值。当然这不是本帖想要讨论的问题。本帖希望用随机数生成器的方式给每一个线程提供这个接口。

于是一位粗心的同学有了下面这样的接口:

阅读全文 »

| 1 分2 分3 分4 分5 分 (4.86- 7票) Loading ... Loading ... | 同时归档在:多线程编程, 语言基础 | 标签: , , |

广度优先搜索解决“营救公主”问题

在之前的一篇文章(迷宫营救公主算法)中提供了一个半成品的解决方案,之所以说他是半成品,是因为首先选择的算法就不对,采用的是深度优先搜索,其次也没有真正的用对深度优先算法,走过的点应该标记为已经走过,而不应该重复遍历该节点。下面的文章对于广度优先和深度优先两种算法的解释非常到位。今天准备把这个问题再完整的用正确的算法解答一遍。

文章链接:【图论】广度优先搜索和深度优先搜索

就营救公主的问题而言,这里不再重复描述问题了,请点击这里查看题目分析:链接。这次选用广度优先算法来解决该问题。上面的算法介绍文章中对该算法已经分析得非常清晰了。先给解决本问题的算法伪代码:

这里每个节点有三种状态:

阅读全文 »

| 1 分2 分3 分4 分5 分 (5.00- 3票) Loading ... Loading ... | 同时归档在:算法数据结构 | 标签: , , , , , |

JVM并发机制的探讨——内存模型、内存可见性和指令重排序

转自oschina

并发本来就是个有意思的问题,尤其是现在又流行这么一句话:“高帅富加机器,穷矮搓搞优化”。从这句话可以看到,无论是高帅富还是穷矮搓都需要深入理解并发编程,高帅富加多了机器,需要协调多台机器或者多个CPU对共享资源的访问,因此需要了解并发,穷矮搓搞优化需要编写各种多线程的代码来压榨CPU的计算资源,让它在同一时刻做更多的事情,这个更需要了解并发。

在我前一篇关于并发的文章http://my.oschina.net/chihz/blog/54731中提到过管程,管程的特色是在编程语言中对并发的细节进行封装,使程序员可以直接在语言中就得到并发的支持,而不必自己去处理一些像是控制信号量之类容易出错且繁琐的细节问题。一些语言是通过在编译时解开语法糖的方式去实现管程,但Java在编译后生成的字节码层面上对并发仍然是一层封装,比如syncrhonized块在编译之后只是对应了两条指令:monitorenter和monitorexit。更多的并发细节是在JVM运行时去处理的,而不是编译。这篇文章主要是针对JVM处理并发的一些细节的探讨。

JAVA内存模型

阅读全文 »

| 1 分2 分3 分4 分5 分 (5.00- 3票) Loading ... Loading ... | 同时归档在:多线程编程 | 标签: |

一个明显的jetty-8大文件传输性能大幅降低问题分析

这个问题很早就分析、修改和验证过了,一直没有来得及总结整理。今天突然想起来了,首先用我那蹩脚的英语给jetty的维护团队提了一个问题单,在等待他们回复的同时,我也把我发现问题的过程分享一下。

问题单链接:https://bugs.eclipse.org/bugs/show_bug.cgi?id=415282

经过打断点和调试,发现如下调用占用了性能下降(相对于jetty7版本)的绝大多数处理耗时:

public class HttpOutput extends ServletOutputStream 
{
/* ------------------------------------------------------------ */
private void write(Buffer buffer) throws IOException
{
if (_closed)
throw new IOException("Closed");
if (!_generator.isOpen())
throw new EofException();

// Block until we can add _content.
while (_generator.isBufferFull())
{
_generator.blockForOutput(getMaxIdleTime());
if (_closed)
throw new IOException("Closed");
if (!_generator.isOpen())
throw new EofException();
}

// Add the _content
_generator.addContent(buffer, Generator.MORE);

// Have to flush and complete headers?

if (_generator.isAllContentWritten())
{
flush();
close();
}
else if (_generator.isBufferFull())
_connection.commitResponse(Generator.MORE);

// Block until our buffer is free
while (buffer.length() > 0 && _generator.isOpen())
{
_generator.blockForOutput(getMaxIdleTime());
}
}
}
具体的耗时消耗在:_generator.blockForOutput(getMaxIdleTime());
从函数名字都可以看出来,当网络繁忙时,会走到这个流程,在blockForOutPut中,首先会注册一个socket可写的事件,当该socket上面可以写数据时,通知当前业务线程,随后业务线程投入休眠。等待事件分发线程检查可读事件,并唤醒自己。这样在这个交互中不可避免的会损失部分数据传输性能,每一包数据虽然只会损失一点点性能,但是传输一个很大的文件时,就会发现这个损失的巨大,在10GE的网卡上面,数据传输的性能降低到了原来的1/10,这个影响太明显了。
 
那么问题到底出在哪里呢?
看下面的代码:
public class HttpGenerator extends AbstractGenerator
{
public void addContent(Buffer content, boolean last) throws IOException
{
if (_noContent)
throw new IllegalStateException("NO CONTENT");

if (_last || _state==STATE_END)
{
LOG.warn("Ignoring extra content {}",content);
content.clear();
return;
}
_last = last;

// Handle any unfinished business?
if (_content!=null && _content.length()>0 || _bufferChunked)
{
if (_endp.isOutputShutdown())
throw new EofException();
flushBuffer();
if (_content != null && _content.length()>0)
{
if (_bufferChunked)
{
Buffer nc=_buffers.getBuffer(_content.length()+CHUNK_SPACE+content.length());
nc.put(_content);
nc.put(HttpTokens.CRLF);
BufferUtil.putHexInt(nc, content.length());
nc.put(HttpTokens.CRLF);
nc.put(content);
content=nc;
}
else
{
Buffer nc=_buffers.getBuffer(_content.length()+content.length());
nc.put(_content);
nc.put(content);
content=nc;
}
}
}

_content = content;
_contentWritten += content.length();

// Handle the _content
if (_head)
{
content.clear();
_content=null;
}
else if (_endp != null && (_buffer==null || _buffer.length()==0) && _content.length() > 0 && (_last || isCommitted() && _content.length()>1024))
{
_bypass = true;
}
else if (!_bufferChunked)
{
// Yes - so we better check we have a buffer
if (_buffer == null)
_buffer = _buffers.getBuffer();

// Copy _content to buffer;
int len=_buffer.put(_content);
_content.skip(len);
if (_content.length() == 0)
_content = null;
}
}
}
 
问题出在下面这段代码上面:
// Handle the _content
if (_head)
{
content.clear();
_content=null;
}
else if (_endp != null && (_buffer==null || _buffer.length()==0) && _content.length() > 0 && (_last || isCommitted() && _content.length()>1024))
{
_bypass = true;
}
else if (!_bufferChunked)
{
// Yes - so we better check we have a buffer
if (_buffer == null)
_buffer = _buffers.getBuffer();

// Copy _content to buffer;
int len=_buffer.put(_content);
_content.skip(len);
if (_content.length() == 0)
_content = null;
}
我的理解,_bypass变量标志不使用缓存,直接将数据刷到客户端,如果这是jetty8的新增特性,那么也不应该是到外层再调用blockforoutput方法,而是直接flushbuffer即可。很明显这是一个bug,bypass的判断条件有误,_buffer为空,这是不使用缓存的条件,但是_buffer.length() == 0并不是该特性的条件,每一次初始化的时候都会默认操作_buffer使得_buffer.length() == 0。这样就导致了每一包数据都走进了blockforoutput流程。应该是一个明显的笔误,问题的修改方法即是去掉该不当的判断条件,只保留_buffer==null的判断。
 
同前面的jetty若干性能问题的分析一样,这个问题的分析也耗费了大量的时间和精力,最终是借助于比对jetty7和jetty8的代码和不停的加日志打点调试得出的。每一个问题的解决都是一段辛酸的故事。
| 1 分2 分3 分4 分5 分 (5.00- 18票) Loading ... Loading ... | 同时归档在:Jetty | 标签: , |

Java网络应用程序(Geronimo、Jetty)调试及问题定位方法简介

Java网络应用程序调试及问题定位方法简介

| 1 分2 分3 分4 分5 分 (5.00- 3票) Loading ... Loading ... | 同时归档在:Geronimo, Jetty, 实用脚本 | 标签: , , |

迷宫营救公主算法

今天下班前在公司的技术题库中看到这道题目,思路很快就有了,递归遍历每一条可能的路径,然后找出最短的路径。回家把代码写出来了。发现算法效率实在是太低了,在矩阵较小的时候还好,当矩阵稍微大一点时根本算不过来,感觉复杂度像是O((N*M)^(N*M))这个数值太庞大了,也完全没有意义。公主等到花儿都谢啦。。

貌似这位同学的算法还不错,还没来得及研究,先做个链接:http://blog.csdn.net/joseph_1118/article/details/9390301

应付较小的矩阵下面的方法还是能蒙混过关的。先发到这里,后面再继续研究优化。题目和代码都在一起:

/**
* 公主被魔王抓走了,王子需要拯救出美丽的公主。他进入了魔王的城堡,魔王的城堡是一座很大的迷宫。
* 为了使问题简单化,我们假设这个迷宫是一个N*M的二维方格。迷宫里有一些墙,王子不能通过。王子只
* 能移动到相邻(上下左右四个方向)的方格内,并且一秒只能移动一步。地图由’S’,’P’,’.’,’*’
* 四种符号构成,’.’表示王子可以通过,’*’表示墙,王子不能通过;’S’表示王子的位置;’P’表示公主
* 的位置;T表示公主存活的剩余时间,王子必须在T秒内到达公主的位置,才能救活公主。如下图所示:
*/

阅读全文 »

| 1 分2 分3 分4 分5 分 (5.00- 9票) Loading ... Loading ... | 同时归档在:算法数据结构 | 标签: , |

Netty和Jetty的Java NIO 网络框架模型分析

Netty的NIO框架模型。在以前的文章中,为解决Jetty的问题,分析过Java NIO基于多路事件分离器的异步IO框架模型。一直都没有系统分析Netty和Jetty的网络模型,这两天将二者的网络框架部分的代码仔细读了一下,整理了二者的网络模型,画出了Netty的模型图:

netty_network_frame_model

在图中,每个侦听都会创建一个Acceptor Reactor,由Boss线程来监控多路分离器,这里只关注连接事件,当有新的建立连接请求达到时,该线程会第一时间响应,将接收到的请求注册到事件多路分离器中,事件多路分离器有多个,默认情况下其个数为CPU核心数的两倍,应该是CPU超线程的数目。这里会给每一个达到的连接编一个序号,将序号对分离器个数取模(hash到0~3的一维空间),根据模值分配给相应的分离器。事件分离器开始监听新的连接上面的读写事件。检查线程为NioWorker。读写数据会通过回调用户注册的handler的相应接口来实现。因此,处理耗时数据的情况下,需要用户将其提交给后台线程,而不应该阻塞事件分离器,否则会导致新的连接无法建立,其他并发请求无法处理。

Jetty在代码风格上面跟Netty差别很大,看jetty代码感觉更清晰一点,可能是因为以前处理问题已经看得非常多了。前面的文章也说过,Jetty是在一个线程中调用一个同步的accept()方法来等待新的连接请求,等到新的连接到来时,就生成新的change事件放到多路分离器中,同样也是有多个多路分离器,选取原则与Netty完全一样。简单的轮询实现负载均衡。这是典型的半同步半异步(Half-Sync/Half-Async)的模式。在只使用1个事件分离器时,会发现分发线程通常会引入很多问题。前面两篇文章中提到的问题分析都跟这个有关。

不知道Jetty与Netty为什么在接受新请求这里有差别,难道Netty的方式更利于处理短连接,而Jetty则更利于处理长连接,比如Http连接?优待进一步的并发测试才能说明问题。如果netty的方式很好,那么Jetty应该也早就改成了该方式。

| 1 分2 分3 分4 分5 分 (5.00- 9票) Loading ... Loading ... | 同时归档在:IO编程, Jetty, Netty | 标签: , , |

分布式存储知识学习清单(完善中)

分布式存储是云存储和云计算的基石。没有特别深入的存储基础知识,但是对分布式存储比较感兴趣。希望以不同的开源存储系统的架构特点和细节组成一条学习的主线,以点带面的掌握主流的架构、算法和适用场景。

1、DRBD

1)磁盘IO的截获和处理流程;
2)同步和异步IO复制流程
3)内核态与用户态交互流程
4)文件系统、VFS和块IO之间的关系

2、Ceph

1)对象接口
2)分布式存储的元数据与数据节点分离架构

3、VFS

1)内核知识点
2)本地文件系统

4、关系数据库

1)PostgreSQL、Sqlite,SQL语法,DB文件组织的数据结构

5、算法

1)PAXOS算法:Chubby、BigTable、GFS论文
2)NoSQL、Cassandra、Voldemort,节点间消息通讯模型,多副本一致性保障。
3)CAP定理相关

| 1 分2 分3 分4 分5 分 (4.80- 10票) Loading ... Loading ... | 同时归档在:C/C++, Linux内核, 算法数据结构 |

通过/proc/stat文件信息,java实现计算cpu使用率

/proc/stat 文件内容:
[root@Shentar ~]# cat /proc/stat
cpu 602 0 2164 11445 2294 0 17 0 0
cpu0 306 0 1232 4553 2125 0 15 0 0
cpu1 295 0 932 6891 169 0 1 0 0
intr 7110 269 7 0 1 1 0 5 0 1 0 0 0 91 0 0 106 0 6521 0 108 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
ctxt 38984
btime 1368275792
processes 2713
procs_running 1
procs_blocked 0
[root@Shentar ~]#

第一行的数值表示的是CPU总的使用情况,所以我们只要用第一行的数字计算就可以了。下表解析第一行各数值的含义:

参数 解析(单位:jiffies)

(jiffies是内核中的一个全局变量,用来记录自系统启动一来产生的节拍数,在linux中,一个节拍大致可理解为操作系统进程调度的最小时间片,不同linux内核可能值有不同,通常在1ms到10ms之间)

user (38082) 从系统启动开始累计到当前时刻,处于用户态的运行时间,不包含 nice值为负进程。

nice (627) 从系统启动开始累计到当前时刻,nice值为负的进程所占用的CPU时间

system (27594) 从系统启动开始累计到当前时刻,处于核心态的运行时间

idle (893908) 从系统启动开始累计到当前时刻,除IO等待时间以外的其它等待时间iowait (12256) 从系统启动开始累计到当前时刻,IO等待时间(since 2.5.41)

irq (581) 从系统启动开始累计到当前时刻,硬中断时间(since 2.6.0-test4)

softirq (895) 从系统启动开始累计到当前时刻,软中断时间(since 2.6.0-test4)stealstolen(0) which is the time spent in other operating systems when running in a virtualized environment(since 2.6.11)

guest(0) which is the time spent running a virtual CPU for guest operating systems under the control of the Linux kernel(since 2.6.24)

结论:总的cpu时间totalCpuTime = user + nice + system + idle + iowait + irq + softirq + stealstolen + guest

计算时,采样两个时间点的数据,对于时间点1,记录总的cpu时间total1,记录空闲时间idle1,对于时间2,同样记录total2和idle2。

菜谱使用率为:cpuusage = 1 – (idle2 – idle1) / (total2 – total1)

注意,如果时间点1和时间点2间隔足够小(小于10ms),则可能出现total2 – total1为0,这样cpu使用率应该为0,而不是采用除法计算。

java代码如下:

阅读全文 »

| 1 分2 分3 分4 分5 分 (5.00- 3票) Loading ... Loading ... | 归档目录:Java |

Jetty误判长连接为超时连接的问题

在上一篇中介绍了jetty的反映器模型,selector线程与业务子线程交互的点有:

1、分发事件给子线程做,启动子线程;

2、子线程发现阻塞或者连接关闭等时间时,注册内部changes,等待selector线程调度;

3、检测超时连接,并且关闭连接。

阅读全文 »

| 1 分2 分3 分4 分5 分 (5.00- 8票) Loading ... Loading ... | 同时归档在:Jetty | 标签: |
返回顶部