cas

发表于 2019-05-10

##什么是CAS

Compare-and-swap In computer science, compare-and-swap (CAS) is an atomic instruction used in multithreading to achieve synchronization 用来在多线程中获取同步的一个原子指令

##解决什么问题比如比较常见的例子,计数的问题 public class IntegerTest { private static Integer count = 0; synchronized public static void increment() { count++; } }

uml

By logan

发表于 2017-06-28

UML

科普下uml，全称Unified Modeling Language统一建模语言 , 还是看wiki吧 (https://zh.wikipedia.org/wiki/%E7%BB%9F%E4%B8%80%E5%BB%BA%E6%A8%A1%E8%AF%AD%E8%A8%80)

类图

类图(https://zh.wikipedia.org/wiki/%E9%A1%9E%E5%88%A5%E5%9C%96)

用的最多的就是类图之间的关系

Generalization ———

>

Realization ____

>

Dependency(use a) —->

Association(has a) _____>

Aggregate(owns a) _____<> 空心

Composition(is part of) _____<> 实心

编码

By logan

发表于 2017-06-19

code 真是一本好书呀

近期工作之余抽出时间完整了看了一遍 [Code:The Hidden Language of Computer Hardware and Software]

计算机这个神秘的机器，在作者笔下无处遁形，无论是从技术实现，还是计算机的发展简史写的详细而生动。

读完这本书，让我改变了对程序的思维方式，任何程序，包含各种语言程序，操作系统，虚拟机等等

最终全部被解释成计算机硬件上各种可支持的指令，而这些指令的执行就是不同的电路实现，

实际上从第十章才真正开始动手搭建计算机了，强调了布尔逻辑对计算机的重要性，前面几章比较简单，但是书中自始至终贯穿着独立思考的精神

第17章自动操作，才真正提到了computer一词 , 接着出现了我们熟悉的中央处理器，RAM，ROM，编程的概念也呼之欲出，机器指令，汇编语言，低级语言和高级语言

汇编和编译，汇编其实是一对一的翻译成机器指令，而编译就比较复杂了

接下来还想再看看编译原理，还有操作系统两本书(操作系统的主要作用是管理内存和管理多线程？)

以下是一些常用的电路或者技术：

各种逻辑门的实现，2-4译码器, 8-1选择器, 半加器，全加器，振荡器，电平触发器

8位随机存储器基于继电器的实现，从继电器，真空管，再到集成电路的发展，摩尔定律的预言等等

computerNetwork

By logan

发表于 2017-04-21

计算机网络 Wiki

读书开始

最近开始回顾一些知识，在看[计算机网络(第5版)谢希仁]这本书，

OSI模型，TCP/IP协议

当然最重要的是OSI模型了，现在实际使用的是TCP/IP协议栈。

书里面有个图很直观，第32页，沙漏形状的TCP/IP协议族表示，谢先生表示最核心的是网络层的IP，

看图就能看出来，所谓的everything over IP and IP over everything

其中最底层的是物理层(其实就是通信原理课程所讲的内容)

20170509更新

断断续续的读到了传输层了，简单回顾下之前章节的知识点

网络层

为什么前面作者说核心是网络层，已有体会，并不是说物理层和链路层不重要，而是因为网络层的作用使得计算机真正的

互相连接在了一起，起至关作用的就是路由器了，为了使得从A到B能够联通，网络的构建者先后定义了一系列的协议

以及这些遇到问题之后的应对策略，

比如以下一些概念

IP地址 IP地址的设计是层级设计的，比如物流配送，先是XX市，然后XX区，XX街道，XX小区

只不过IP是两个层级的。前面是网络号，后面是主机号，

整个IP地址共4个字节，在此基础上又分成了4大类，

4大类的划分是按照ip地址二进制最高位几位划分的

00000000 XXXXXXXX XXXXXXXX XXXXXXXX 10000000 XXXXXXXX XXXXXXXX XXXXXXXX 11000000 XXXXXXXX XXXXXXXX XXXXXXXX 11100000 XXXXXXXX XXXXXXXX XXXXXXXX

A类的网络号是第一个字节

B类的网络号是前二个字节

C类的网络号是前三个字节

D类的网络号是前四个字节

子网掩码二级划分不够灵活，使用子网掩码成功可以划分成三级
ARP协议功能，根据IP地址查找MAC地址，为啥要解析为MAC地址，因为链路层的frame(帧结构)使用的MAC硬件地址
路由选择协议

大的分类有两个

内部网关协议 IGP (Interior Gateway Protocol) 也叫作域间路由选择 (interdomain routing)

外部网关协议 EGP (External Gateway Protocol)

上面的协议名称是统称，具体的实现，

内部网关协议有RIP (Routing Information Protocol), 是一种分布式的基于距离向量的路由选择协议

还有OSPF(Open Shortest Path First ) 最短路径优先

外部网关协议有，最新的叫做边界网关协议BGP

其中的路由算法有距离向量算法，最短路径算法，

还有路由信息的交换策略等这些知识有时间都可以研究下，挺有意思的。

IP多播
VPN 和NAT 其中有个规定，RFC 1918 规定了一些专用地址

(1) 10.0.0.0 到 10.255.255.255

(2) 172.16.0.0. 到 172.31.255.255

(3) 192.168.0.0 到 192.168.255.255

并且规定，在因特网中的所有路由器，对目的地址是专用地址的数据报一律不进行转发。

(看到这里就有疑问了，我们基本上都是在局域网中，那么我们是怎么和其他公网服务器通信呢，

计算机通过路由交互，上面说的全都是根据公网IP地址做为源地址和目的地址交换信息的，我们局域网是怎么通信的？

就有了下面的NAT了)

NAT使用是最广泛了，他对匮乏的IPV4地址资源绝对起了很大的缓解作用。

想到了我家里接入运营商的网络，感觉应该不是公网地址，应该是在ISP里大的局域网中了，

而且对于个人用户来说不需要用公网地址，因为公网地址就是来提供服务的，只有公司或者组织才有需求使用这些公网地址。

传输层

传输层离不开两个重要的协议TCP和UDP

其中，UDP是面向报文的，TCP是面向字节流的，

what？怎么理解面向报文和面向字节流，后面还有HTTP是面向字符的。

其实这得从各自协议的内部原理说起，

UDP是比较简单的，不需要连接，直接发送UDP报文，相比TCP真是简单快捷。

TCP是需要先进行连接的。其实连接不是物理通道上的连接，只是逻辑上的连接，著名的三次握手，四次挥手，

TCP的核心是如何实现可靠传输，注意是可靠，听起来很简单的词，实现起来可不简单，除了可靠还要效率，

可以看书中的‘停止等待协议’和‘连续ARQ协议’

还有书中在这一章提到了socket，指出是TCP连接的端点。IP+端口。socket本身的含义比较模糊，而且中文翻译也没有很好表达本身的意思。

我认为应该就是传输层的一个接口吧。

可以重点看下6.8应用进程跨网络的通信这一节，

因为TCP和IP协议目前都已经在操作系统内核中实现了，我们应用层使用比如http调用的是操作系统暴露出来的传输层（比如TCP和UDP）的接口，就是面向

socket编程了，不同的系统有自己的实现

unix：socket interface

windows：winSocket

总结一下

关于本书，虽然书的出版时间比较老一些，但是不影响理解网络，毕竟一些基础的东西都是不变的，

而且凭借作者深厚的功底，对计算机网络的一步步发展，和期间遇到的每个问题，以及由此网络专家提出的解决方案等

介绍的很准确，理解起来很容易，没有废话，都是干货很好。

关于自己，越读书越发现自己知识不够，其中关于每个协议，以及如何实现协议，都可以作为一个专题研究下，比如TCP如何实现可靠传输，怎么做到的TCP拥塞

控制等等。

regularExpression

By logan

发表于 2017-02-10

#Wiki

What is regularExpression:

  A regular expression, regex or regexp[1] (sometimes called a rational expression)[2][3] is, in theoretical computer science and formal language theory, 
  a sequence of characters that define a search pattern. 
  Usually this pattern is then used by string searching algorithms for "find" or "find and replace" operations on strings.
  public void static main () {
      logger.info();
  }

有什么作用

Regular expressions are used in search engines, search and replace dialogs of word processors 
and text editors, in text processing utilities such as sed and AWK and in lexical analysis.
 Many programming languages provide regex capabilities, built-in, or via libraries.

Patterns

正则表达式组成结构，参看wiki，两部分:meta character or regular character

如何实现

汤姆森构造，不确定性有限自动机

 A regex processor translates a regular expression in the above syntax into an internal representation 
 
 which can be executed and matched against a string representing the text being searched in.
 
  One possible approach is the Thompson's construction algorithm to construct a nondeterministic finite automaton (NFA), 
  
  which is then made deterministic and the resulting DFA is run on the target text string 
  
  to recognize substrings that match the regular expression. The picture shows the NFA scheme N(s*) 
  
  obtained from the regular expression s*, where s denotes a simpler regular expression in turn, 
  
 which has already been recursively translated to the NFA N(s).

Standards 标准

主要是BRE和ERE

 The IEEE POSIX standard has three sets of compliance: BRE (Basic Regular Expressions),[25] ERE (Extended Regular Expressions), 
 
 and SRE (Simple Regular Expressions). SRE is deprecated,[26] in favor of BRE, 
 
 as both provide backward compatibility. The subsection below covering the character classes applies to both BRE and ERE

linux 的grep命令有选项，-E 和 -G 就是选择哪个标准
perl正则已经演化为真正意义上的标准了，由于其丰富和强大的自动化表达式。 perl还提供了很多功能，比如懒加载，回溯，命名式捕获组和循环模式等，所有这些都是都对POSIX BRE/ERE强有力的补充 Java, JavaScript, Python等众多语言都是使用的perl like ``` java Perl regexes have become a de facto standard, having a rich and powerful set of atomic expressions.

Perl has no “basic” or “extended” levels, where the ( ) and { } may or may not have literal meanings.

They are always metacharacters, as they are in “extended” mode for POSIX. To get their literal meaning, you escape them.

Other metacharacters are known to be literal or symbolic based on context alone.

Perl offers much more functionality: “lazy” regexes, backtracking, named capture groups,

and recursive patterns, all of which are powerful additions to POSIX BRE/ERE. (See lazy matching below.)

  
  详细的可以细读[Wiki](https://en.wikipedia.org/wiki/Regular_expression)
  
  
  
  - java Pattern里的special constructs 
  看例子好像是对表达式匹配的值的二次限定，即对后面正则的二次限定范围
  比如：
``` java
  we wanted to know if our input string contains the word “incident” 
  but that the word “theft” should not be found anywhere. We can use a negative look-ahead to 
  ensure that there are no occurrences.
  “(?!.*theft).*incident.*”

http://www.ocpsoft.org/opensource/guide-to-regular-expressions-in-java-part-2/

    Look-ahead/behind constructs (non-capturing)
  (?:X) 			X, as a non-capturing group
  (?=X) 			X, via zero-width positive look-ahead
  (?!X) 			X, via zero-width negative look-ahead
  (?<=X) 			X, via zero-width positive look-behind
  (?<!X) 			X, via zero-width negative look-behind
  (?<X) 			X, as an independent, non-capturing group
  So what does this all mean? What does a look-ahead really do for me? Say, for example, 
  we wanted to know if our input string contains the word “incident” but that the word “theft” 
  should not be found anywhere. We can use a negative look-ahead to ensure that there are no occurrences.
  “(?!.*theft).*incident.*”
  This expression exhibits the following behavior:
  "There was a crime incident"			matches
  "The incident involved a theft"			does not match
  "The theft was a serious incident"		does not match

– java的量词

http://blog.csdn.net/carolzhang8406/article/details/6726546

贪婪量词：
先看整个字符串是不是一个匹配。如果没有发现匹配，它去掉最后字符串中的最后一个字符，并再次尝试。如果还是没有发现匹配，那么    再次去掉最后一个字符串，这个过程会一直重复直到发现一个匹配或者字符串不剩任何字符。简单量词都是贪婪量词。
    惰性量词：
先看字符串中的第一个字母是不是一个匹配，如果单独着一个字符还不够，就读入下一个字符，组成两个字符的字符串。如果还没有发现匹配，惰性量词继续从字符串中添加字符直到发现一个匹配或者整个字符串都检查过也没有匹配。惰性量词和贪婪量词的工作方式恰好相反。
    支配量词：
只尝试匹配整个字符串。如果整个字符串不能产生匹配，不做进一步尝试。

javaMemoryModel

By logan

发表于 2017-02-06

#jsr133 what is java memoryModel memoryModel

What is a memory model, anyway?
Do other languages, like C++, have a memory model?
What is JSR 133 about?
What is meant by reordering?
What was wrong with the old memory model?
What do you mean by incorrectly synchronized?
What does synchronization do?
How can final fields appear to change their values?
How do final fields work under the new JMM?
What does volatile do?
Does the new memory model fix the “double-checked locking” problem?
What if I’m writing a VM?
Why should I care?

比较有代表性的介绍 What is javaMemoryModel:

The Java Memory Model defines the behavior of volatile and synchronized, and, more importantly,

ensures that a correctly synchronized Java program runs correctly on all processor architectures;

The Java Memory Model was an ambitious undertaking;

it was the first time that a programming language specification

attempted to incorporate a memory model which could provide consistent semantics

for concurrency across a variety of architectures. Unfortunately,

defining a memory model which is both consistent and intuitive proved far more difficult than expected.

JSR 133 defines a new memory model for the Java language which fixes the flaws of the earlier memory model.

In order to do this, the semantics of final and volatile needed to change.

线上CPU过高-threadDump分析

By logan

发表于 2016-11-17

#问题现象一台机器的cpu过高首先想到是dump线上thread日志

kiil -3 PID ，默认会出输出到catalina.out日志里

 kill -3 389

or 可以指定日志输出

 sudo jstack -l 389 | tee -a jstack.log

出现以下异常用-F替代

1099: Unable to open socket file: target process not responding or HotSpot VM not loaded The -F option can be used when the target process is not responding

可以使用以上任意命令，一定多运行几遍获取数据。

然后使用 top -ac -H 获取到cpu最高的线程pid，计算器转为16进制，在文件里搜索

#问题分析

日志

出现了非常频繁的ParallelGC日志

"GC task thread#0 (ParallelGC)" prio=10 tid=0x00007fb428021800 nid=0x263d runnable 

"GC task thread#1 (ParallelGC)" prio=10 tid=0x00007fb428023000 nid=0x263e runnable 

"GC task thread#2 (ParallelGC)" prio=10 tid=0x00007fb428025000 nid=0x263f runnable 

"GC task thread#3 (ParallelGC)" prio=10 tid=0x00007fb428027000 nid=0x2640 runnable

出现次数非常多的RUNABLE状态的业务日志

"http-8000-10" daemon prio=10 tid=0x00007fb3f8025000 nid=0x276c runnable [0x00007fb398c82000]
   java.lang.Thread.State: RUNNABLE
   ...
   ArAccrualDetailServiceImpl.queryByIds
   ...

jstat监控GC：

[l-qreaper.dev.cn0 ~]$ sudo jstat -gccause 29781 1000
  S0     S1     E      O      P     YGC     YGCT    FGC    FGCT     GCT    LGCC                 GCC                 
 75.48   0.00  53.94  93.55  35.02    504   37.875   121  287.080  324.955 Allocation Failure   No GC               
  0.00  66.57  96.87  95.04  35.02    505   38.002   121  287.080  325.081 Allocation Failure   No GC               
  0.00  54.69   0.00  98.51  35.02    507   38.214   122  287.080  325.294 Allocation Failure   Ergonomics          
  0.00  54.69   0.00  98.51  35.02    507   38.214   122  287.080  325.294 Allocation Failure   Ergonomics          
  0.00  54.69   0.00  98.51  35.02    507   38.214   122  287.080  325.294 Allocation Failure   Ergonomics          
  0.00  54.69   0.00  98.51  35.02    507   38.214   122  287.080  325.294 Allocation Failure   Ergonomics          
  0.00  21.30 100.00  99.99  35.01    507   38.214   123  290.270  328.484 Allocation Failure   Ergonomics          
  0.00  21.30 100.00  99.99  35.01    507   38.214   123  290.270  328.484 Allocation Failure   Ergonomics          
  0.00  21.30 100.00  99.99  35.01    507   38.214   123  290.270  328.484 Allocation Failure   Ergonomics          
  0.00  21.30 100.00  99.99  35.01    507   38.214   123  290.270  328.484 Allocation Failure   Ergonomics          
  0.00   0.00 100.00 100.00  35.01    507   38.214   124  293.612  331.826 Allocation Failure   Ergonomics          
  0.00   0.00 100.00 100.00  35.01    507   38.214   124  293.612  331.826 Allocation Failure   Ergonomics          
  0.00   0.00 100.00 100.00  35.01    507   38.214   124  293.612  331.826 Allocation Failure   Ergonomics          
  0.00   0.00 100.00 100.00  35.01    507   38.214   124  293.612  331.826 Allocation Failure   Ergonomics

可以看到youngGc非常频繁，我设置的是每秒监控一次

#调优很详细 (http://www.importnew.com/22336.html)

#参考：

GC专家系列目录索引(推荐阅读) (https://segmentfault.com/a/1190000004369048)

堆内存分配(GC算法逻辑)： (http://www.blogjava.net/fancydeepin/archive/2013/09/29/jvm_heep.html) 官方 (http://www.oracle.com/technetwork/java/javase/tech/vmoptions-jsp-140102.html)

[https://my.oschina.net/dabird/blog/691692] [http://blog.csdn.net/rachel_luo/article/details/8920596]

二叉树

By logan

发表于 2016-11-08

先来一堆概念 #二叉树定义wiki

二叉树（英语：Binary tree）是每个节点最多有两个子树的树结构
与树不同，树的节点个数至少为1，而二叉树的节点个数可以为0；树中节点的最大度数没有限制，而二叉树节点的最大度数为2

#满二叉树

#完全二叉树

#二叉搜索树wiki

二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树（英语：ordered binary tree），排序二叉树（英语：sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
任意节点的左、右子树也分别为二叉查找树；
没有键值相等的节点。

#平衡二叉树典型的代表有avl和红黑树红黑树参照： https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md

LEFT-ROTATE(T, x)  
1  y ← right[x] ▹ Set y.  
2  right[x] ← left[y]      ▹ Turn y's left subtree into x's right subtree.  
3  p[left[y]] ← x  
4  p[y] ← p[x]             ▹ Link x's parent to y.  
5  if p[x] = nil[T]  
6     then root[T] ← y  
7     else if x = left[p[x]]  
8             then left[p[x]] ← y  
9             else right[p[x]] ← y  
10  left[y] ← x             ▹ Put x on y's left.  
11  p[x] ← y