深入分析Java Web技术内幕-第二章

深入分析Java I/O机制

Java I/O类库的基础架构

类库大概分为四组:

基于字节操作的I/O接口:InputStream 和 OutputStream
基于字符操作的I/O接口: Writer和Reader
基于磁盘操作的I/O接口: File
基于网络操作的I/O接口: Socket
(这尼玛也能划到一起,不过这样好像也行)

Continue reading “深入分析Java Web技术内幕-第二章”

深入分析Java Web技术内幕-第一章

CDN架构图

发起请求

一句话,发起一个HTTP请求的过程就是建立一个Socket通信的过程.
既然本质上就是建立一个Socket连接,那么我们完全可以模拟浏览器发出HTTP请求.(比如PostMan)
-而HTTP协议的内容之前学过了,不再赘述(详见图灵的那本HTTP)

HTTP协议解析

常见HTTP请求头:

Accept-Charset: 用于指定客户端接受的字符集
Accept-Encoding: 用于指定可接受内容编码如Accept-Encoding: gzip.deflate
Accept-Language: 用于指定一种自然语言如 zh-cn
Host: 用于指定被请求资源的主机和端口号
User-Agent: 客户端将他的操作系统、浏览器和其他属性告诉服务器
Connection: 当前连接是否保持,如:Keep-Alive

常见的HTTP响应头

Server: 使用的服务器名称,如 Server: Apache/1.3.6(Unix)
Content-Type: 用于指定发送给接受者的实体正文的媒体类型 如: text/html;charset=GBK
Content-Encoding: 与Accept-Encoding对应,告诉服务端采用什么压缩编码
Content-Language: 描述了资源所用的自然语言,与Accept-Language对应
Content-Length: 指明了实体正文长度.用以字节方存储的十进制数字来表示.
Keep-Alive: 保持连接的时间,如-Keep-Alive: timeout=5,max=120

创建HTTP状态码

200 OK
302 临时跳转/缓存
400 请求有语法错误
403 拒绝
404 不存在
500 不可预期错误

查看HTTP工具

F12

拒绝缓存载入页面

Ctrl+F5

DNS域名解析

分十步进行:
Aaron

但可能不知这十步,因为name server可能会有多级,或者有一个GTM来负载均衡控制.

nslookup可以来看域名的解析结果

linux 可以用dig来查询DNS解析过程

清除缓存的域名

windows下: ipconfig /flushdns
Linux下: /etc/init.d/nscd restart

其他的

JVM也会缓存一些DNS,这个缓存是在InetAddress类中完成的.

几种域名解析方式

有服务器的童鞋一定接触过
A记录

Address,可将多个域名解析到一个地址

MX记录

Mail Exchange,将某域名下的邮件服务器指向自己的Mail Server,DNS会将邮件发向对应的邮件路由

CNAME记录

Canonical Name(别名解析),为一个域名设置一个或多个别名,如,taobao.com解析到xulingbo.net.则xulingbo.net是taobao.net的别名.

NS记录

为某域名指定DNS解析服务器.

TXT记录

为某个主机名或域名设置说明.

CDN工作机制

Content Delivery Network,内容分布网络.
将信息发布到最接近用户的”边缘”,使用户可以就近取得所需的内容.
CDN=镜像(Mirror)+缓存(Cache)+整体负载均衡(GSLB).
CDN可以明显提高Internet中信息流动的效率.

目前CDN都以缓存静态数据为主,如CSS,JS,图片和静态页面等.
淘宝有90%的数据由CDN提供.
通常来说CDN要完成以下几个目标:

可扩展
安全性
可靠性,响应和执行

通常的CDN架构

负载均衡(Load Balance)

负载均衡就是对工作任务进行平衡,分摊到多个操作单元上执行,如图片服务器,应用服务器等,共同完成工作任务。它可以提高服务器响应速度及利用效率.
负载均衡是有DNS解析来完成的.
常用在集群中,分为软件/硬件负载均衡.

计划:技术栈完善2-实战JAVA高并发程序设计-第三章

JDK并发包

多线程间的团队协作: 同步控制

比如之前的synchronized关键字就是一种最简单的控制方法.它决定了一个线程是否可以访问临界资源区.
还有wait和notify.

synchronized的功能扩展: 重入锁

重入锁可以完全替代synchronized关键字.

重入锁使用 java.util.concurrent.locks.ReentrantLock
类来实现.

例:

import java.util.concurrent.locks.ReentrantLock;
public class p31 implements Runnable{

    public static ReentrantLock lock=new ReentrantLock();
    public static int i=0;
    @Override
    public void run(){
        for(int j=0;j<10000000;++j){
            lock.lock();
            try{
                i++;
            }finally{
                lock.unlock();
            }
        }
    }

    public static void main(String[] args) throws InterruptedException{
        // TODO Auto-generated method stub
        p31 tl=new p31();
        Thread t1=new Thread(tl);
        Thread t2=new Thread(tl);
        t1.start();t2.start();
        t1.join();t2.join();
        System.out.println(i);
    }
}

可以看出这段代码是手动加锁的.故重入锁在逻辑控制的灵活性上远高于某关键字.
但一定注意推出临界区要释放锁
为什么叫重入锁呢?因为允许一个线程获得N个锁,所以叫重入锁.
一个线程获取多个锁后,也必须释放相同次数的锁

重入锁的中断响应

如果你一个线程一直等待锁,而拿锁的那个线程始终不放开锁,那不就死锁了么.
它提供了一种机制,即通知等待者无须再等待.即时停止工作.
isHeldByCurrentThread()方法是返回当前线程是否拥有该锁.
lockInterruptibly()方法是获取一个允许中断响应的锁.
lock()方法获取的锁不允许中断.
例:

import java.util.concurrent.locks.ReentrantLock;

public class p32 implements Runnable {
    public static ReentrantLock lock1=new ReentrantLock();
    public static ReentrantLock lock2=new ReentrantLock();

    int lock;
    /*
     * 控制加锁顺序,防止死锁
     */
    public p32(int lock){
        this.lock=lock;
    }

    @Override
    public void run(){
        try{
            if(lock==1){
                lock1.lockInterruptibly();
                try{
                    Thread.sleep(500);
                }catch(InterruptedException e){}
                System.out.println("Lock1 Here IN");
                lock2.lockInterruptibly();
                System.out.println("Lock1 Here OUT");
            }else{
                lock2.lockInterruptibly();
                try{
                    Thread.sleep(500);
                }catch(InterruptedException e){}
                System.out.println("Lock2 Here IN");
                lock1.lockInterruptibly();
                System.out.println("Lock2 Here OUT");
            }
        }catch(InterruptedException e){
            e.printStackTrace();
        }finally{
            if(lock1.isHeldByCurrentThread())
                lock1.unlock();
            if(lock2.isHeldByCurrentThread())
                lock2.unlock();
            System.out.println(Thread.currentThread().getId()+"线程退出");
        }
    }

    public static void main(String[] args) throws InterruptedException{
        p32 r1=new p32(1);
        p32 r2=new p32(2);
        Thread t1 = new Thread(r1);
        Thread t2 = new Thread(r2);
        t1.start();t2.start();
        Thread.sleep(1000);
        t2.interrupt();
    }

}

线程启动后,r1先占用lock1,再请求lock2
r2相反,这也就导致了t1和t2互相等待,形成死锁.
而当我们将r2中断以后,r2释放了所有的锁,r1检测到了,故只有r1完全执行完毕,r2则会抛出一个中断异常.

第二种中断方法

lock.tryLock(5,TimeUnit.SECONDS)

县城在这个锁请求中等待5秒,如果五秒内无法得到锁,则False

公平锁

公平锁的效率不高,所以一般不用,因为公平锁需要维护一个优先队列.

公平锁是通过对谁先获得当前资源进行合理的调度来防止死锁的产生.

使用方法: ReentrantLock

性质:

1.原子状态
2.等待队列(没有请求到锁就进入等待队列)
3.阻塞原语pair()与unpair()

重入锁好搭档: Condition条件

Condition和wait与notify的用法大致相同

package s;

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

public class p31 implements Runnable {

    public static ReentrantLock lock=new ReentrantLock();
    public static Condition condition=lock.newCondition();

    @Override
    public void run(){
        try{
            lock.lock();
            System.out.println("SD");
            condition.await();
            System.out.println("This is going on.");
        }catch(Exception e){
            e.printStackTrace();
        }finally{
            lock.unlock();
        }
    }

    public static void main(String[] args) throws InterruptedException{
        p31 tl=new p31();
        Thread t1=new Thread(tl);
        t1.start();
        Thread.sleep(2000);
        ///通知线程t1继续执行
        lock.lock();
        condition.signal();
        System.out.println("AA");
        lock.unlock();
    }

}

注: Condition只能在lock和unlock保护下才可以解锁.
wait 是等待,notify是返回通知开始执行

允许多个线程同时访问: 信号量(Semaphore)

构造函数:

public Semaphore(int permits)
public Semaphore(int permits,boolean fair)
第二个参数是是否公平

信号量主要逻辑方法

public void acquire() -准入许可,等待
public void acquireUninterruptibly() -不接收中断
public boolean tryAcquire() – 获得许可,不等待
public boolean tryAcquire(long timeout,TimeUnit unit)
public void release() – 释放许可

例子:

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Semaphore;

public class p33 implements Runnable{
    final Semaphore semp=new Semaphore(5);
    public void run(){
        try{
            semp.acquire();
            Thread.sleep(2000);
            System.out.println(Thread.currentThread().getId()+":done!");
            semp.release();
        }catch(Exception e){
            e.printStackTrace();
        }
    }
    public static void main(String[] args) {
        ExecutorService exec =Executors.newFixedThreadPool(20);
        final p33 t1= new p33();
        for(int i=0;i<20;++i){
            exec.submit(t1);
        }
    }

}

为信号量传入的5代表线程队列中课同时存在的线程数量的最大值.
开启程序后,你会发现每一瞬间都会有5个线程执行并打印出数据,但在这5个释放占用的信号量后才会继续向下执行.

ReadWriteLock 读写锁

读操作不会破坏数据完整性,所以当读-读-…操作产生时,不需要加锁即可.这样使得大量读操作的系统会有很明显的效率上的提升.

但写会阻塞读,所以效率由写操作的次数来决定.

锁的创建:

private static ReentrantReadWriteLock readWriteLock=new RenntrantReadWriteLock();
private static Lock readLock=readWriteLock.readLock();
private static Lock WriteLock=readWriteLock.WriteLock();

倒计时器: CountDownLatch

它可以让一个线程在倒计时结束后再执行.
执行方式如下:

必须所有的线程都完成任务后,等待在CountDownLatch上的线程才能继续执行.

例:

import java.util.Random;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class p34 implements Runnable{
    static final CountDownLatch end=new CountDownLatch(10);

    static final p34 demo=new p34();

    public void run(){
        try{
            Thread.sleep(new Random().nextInt(10)*1000);
            System.out.println("check complete");
            end.countDown();
        }catch(Exception e){
            e.printStackTrace();
        }
    }

    public static class now{
        public static void print() throws InterruptedException{
            end.await();
            System.out.println("我来了~~~~");
        }
    }

    public static void main(String[] args) throws InterruptedException{
        // TODO Auto-generated method stub
        final now t1=new now();
        ExecutorService exec=Executors.newFixedThreadPool(10);
        for(int i=0;i<10;++i){
            exec.submit(demo);
        }
        t1.print();
        exec.shutdown();
    }
}

循环栅栏: CyclicBarrier

它比上面那个更加复杂和强大

可以将它理解为一种障碍物.它是用来阻止线程继续执行,并且这个计数器可以反复使用,比如,10个执行完以后,再来一遍.

例:

import java.util.Random;
import java.util.concurrent.CyclicBarrier;

public class p35 {
    public static class Soldier implements Runnable{
        private String soldier;
        private final CyclicBarrier cyclic;
        Soldier(CyclicBarrier cyclic,String s){
            this.cyclic=cyclic;
            this.soldier=s;
        }

        public void run(){
            try{
                //等待所有士兵到齐
                cyclic.await();
                doWork();
                //等待所有士兵完成工作
                cyclic.await();
            }catch(Exception e){
                e.printStackTrace();
            }
        }

        void doWork(){
            try{
                Thread.sleep(Math.abs(new Random().nextInt()%10000));
            }catch(Exception e){
                e.printStackTrace();
            }
            System.out.println(soldier+"任务完成!");
        }

    }

    public static class BarrierRun implements Runnable{
        boolean flag;
        int N;
        public BarrierRun(boolean a,int b){
            this.flag=a;
            this.N=b;
        }
        public void run(){
            if(flag){
                System.out.println("司令:[士兵"+N+"个,任务完成!]");
            }else{
                System.out.println("司令:[士兵"+N+"个,集合完毕!]");
                flag=true;
            }
        }
    }

    public static void main(String[] args) {
        final int N=5;
        Thread[] allSoldier=new Thread[10];
        boolean flag=false;
        CyclicBarrier cyclic=new CyclicBarrier(N,new BarrierRun(flag,N));
        //设置屏障点
        System.out.println("集合队伍!");
        for(int i=0;i<10;++i){
            System.out.println("士兵"+i+"报道!");
            allSoldier[i]=new Thread(new Soldier(cyclic,"士兵 "+i));
            allSoldier[i].start();
        }
    }

}

输出:
集合队伍!
士兵0报道!
士兵1报道!
士兵2报道!
士兵3报道!
士兵4报道!
士兵5报道!
司令:[士兵5个,集合完毕!]
士兵6报道!
士兵7报道!
士兵8报道!
士兵9报道!
司令:[士兵5个,任务完成!]
士兵 8任务完成!
士兵 7任务完成!
士兵 1任务完成!
士兵 0任务完成!
士兵 4任务完成!
司令:[士兵5个,任务完成!]
士兵 5任务完成!
士兵 3任务完成!
士兵 9任务完成!
士兵 2任务完成!
士兵 6任务完成!
司令:[士兵5个,任务完成!]

你会发现是每5个释放一次锁.

LockSupport

它可以在线程内任意位置让其阻塞
之前suspend和resume时,如果resume在suspend前执行,则一定会出现线程被无限挂起,导致无法正常退出.
我们可以用LockSupport解决这一问题.

因为LockSupport是用信号量来实现的.它为每一个线程准备了一个许可,如果许可可用,则park()函数会立即返回,并且消费许可(变为不可用).如果许可不可用,就会被阻塞.
但和信号量不同的是,许可永远只有一个.

LockSupport.park()
LockSupport.unpark(Runnable)
LockSupport.parkNanos()
LockSupport.parkUtil()

此外,如果是用park(Object),则这个阻塞对象会出现在线程Dump中(报错),分析问题就更方便了.

线程复用: 线程池

多线程的软件设计方法确实可以最大限度的发挥现代多核处理器的计算能力,提高生产系统的吞吐量和性能。但是,若不加控制和管理的随意使用线程,对系统的性能反而会产生不利影响.

一种极简的处理方法:

new Thread(new Runnable(){
    public void run(){
        //do sth
    }
}).start();

这样的线程在run完后就会自动回收,但线程量过大时,则会耗尽CPU和内存资源.

而且如果为每一个小程序都创建一个线程,就可能出现销毁时间远大于该线程实际工作所消耗的时间.

其次,可能因线程过多而爆栈/堆.

大量的线程回收也会给GC造成很大压力,延长GC的停顿时间.

什么是线程池

为了避免系统频繁的创建和销毁线程,我们会尽量的让线程复用.
数据库连接池:
为了避免每次数据库查询都重新建立和销毁数据库连接,我们可以使用数据库连接池保护一些数据库连接,让他们长期在激活状态.当系统需要数据库时,并不是真正创建一个新的连接,而是从连接池中获得一个可用的连接即可.反之,当需要关闭连接时,并不是真的把链接关闭,而是将这个链接还给连接池即可.

线程池:
线程池中,总有那么几个活跃线程,当你需要时,可以从池子中随便拿一个空闲线程,当完成工作时,并不着急关闭线程,而是将这个线程退回到池子,方便别人使用.

换言之,创建线程变成了从池子中获得线程,销毁变成了归还.

JDK内置线程池框架: Executor

框架结构图

关于Executor的设计模式: 生产者-消费者模式和工厂方法

例子:

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class p36 {
    public static class MyTask implements Runnable{
        public void run(){
            System.out.println(System.currentTimeMillis()+":Thread ID:"+Thread.currentThread().getId());
            try{
                Thread.sleep(1000);
            }catch(Exception e){
                e.printStackTrace();
            }
        }
    }
    public static void main(String[] args){
        // TODO Auto-generated method stub
        MyTask task=new MyTask();
        ExecutorService es=Executors.newFixedThreadPool(5);
        for(int i=0;i<10;++i){
            es.submit(task);
        }
        es.shutdown();
    }

}

可能我们之前一直对为什么我们传入submit的是一个对象,但他们得ID却不同呢?
这是因为线程的ID与对象并无直接关系,线程的ID是直接分配好的.
我们可以尝试打印出this.toString()来查看是否是同一个对象,结果表明确实是同一个对象,如果不想使用用同一个对象来做测试,那就用new MyTask()作为参数就可以了.
但直接new的话,会出现一个很严重的问题,就是new出来的对象的执行顺序可能产生混乱.因为不是同一个对象,所以就不会按照顺序来执行了.
例:

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.locks.ReentrantLock;

public class p36 { 
    public static ReentrantLock lock=new ReentrantLock();
    public static class MyTask implements Runnable{
        private int kt=0;
        public void cal(int t){
            kt=kt+t;
        }
        public void run(){
            //lock.lock();
            cal(1);
            //lock.unlock();
            //System.out.println(System.currentTimeMillis()+":Thread ID:"+Thread.currentThread().getId());
            if(kt>9990)
                System.out.println(this.toString()+" "+kt);
            try{
                Thread.sleep(1);
            }catch(Exception e){
                e.printStackTrace();
            }
        }
    }
    public static void main(String[] args) throws InterruptedException{
        // TODO Auto-generated method stub
        MyTask tk=new MyTask(); 
        Thread pk=new Thread(tk);
        ExecutorService es=Executors.newFixedThreadPool(10);

        for(int i=0;i<10000;++i){
            es.submit(tk);
        }
        es.shutdown();
        System.out.println("AAAAAA"+tk.kt);
    }

}

打印后会发现,结果并不是正确的,甚至10000的数据前提下9990也不能保证.
当然,加上锁以后就正常了.

刨根问底: 核心线程池的内部实现

拒接策略

P108

扩展线程池

ThreadPoolExecutor是一个可扩展的线程池
它为我们提供了三个接口

beforeExecute()
afterExecute()
terminated()

字面意思

我们重写一下试试:

import java.util.concurrent.ExecutorService;
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.concurrent.TimeUnit;

public class p37 {
    public static class MyTask implements Runnable{
        public String name;

        public MyTask(String name){
            this.name=name;
        }

        public void run(){
            System.out.println("正在执行"+":Thread ID:"+Thread.currentThread().getId()+":Task Name:"+name);
            try{
                Thread.sleep(1000);
            }catch(Exception e){
                e.printStackTrace();
            }
        }
    }
    public static void main(String[] args) throws InterruptedException {
        // TODO Auto-generated method stub
        ExecutorService es=new ThreadPoolExecutor(5,5,0L,TimeUnit.MILLISECONDS,new LinkedBlockingDeque<Runnable>()){
            @Override
            protected void beforeExecute(Thread t,Runnable r){
                System.out.println("准备执行: "+((MyTask)r).name);
            }

            @Override
            protected void afterExecute(Runnable r,Throwable t){
                System.out.println("执行完成: "+((MyTask)r).name);
            }

            @Override
            protected void terminated(){
                System.out.println("线程池退出");
            }
        };
        for(int i=0;i<5;++i){
            MyTask task=new MyTask("TASK-GEYM-"+i);
            es.execute(task);
            Thread.sleep(10);
        }
        es.shutdown();
    }
}

注: shutdown方法会等所有的线程执行结束后才关闭线程池.

合理的选择: 优化线程池线程数量

线程池的大小对系统的性能也有影响.过大或过小都不可以.但也不需要特别精确.
一般来说确定线程池的大小需要考虑CPU的数量,内存大小等因素.

注:线程池可能会吃掉异常

而 execute方法会打印出部分异常,
或者修改submit的使用:
Future re=pools.submit(new DivTask(100,0));
re.get();
这样也可以.

扩展ThreadPoolExecutor以显示异常



分而治之: Fork/Join框架

著名的MapReduce也是采用了分而治之的思想,简单来说,如果你要处理1000个数据,但是你并不具备处理1000个数据的能力,那么你可以只处理10个,然后,分阶段处理100个,将100个结果进行合成.就是1000个结果.
JDK为我们提供了ForkJoinPool线程池.

Fork/join执行逻辑

互相帮助的线程

其中ForkJoinTask有两个重要的子类.关系如下:

RecursiveTask<>
是实现一个compute函数(返回值要与泛型一致)即可.

例:

import java.util.ArrayList;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.RecursiveTask;

public class p38 extends RecursiveTask<Long> {
    private static final int THRESHOLD = 10000;
    private long start;
    private long end;

    public p38(long start,long end){
        this.start=start;
        this.end=end;
    }

    public Long compute(){
        long sum=0;
        boolean canCompute=(end-start)<THRESHOLD;
        if(canCompute){
            ///如果大于THRESHOLD的话才进行分解,否则直接进行即可
            for(long i=start;i<=end;++i){
                sum+=i;
            }
        }else{
            //分成100个小任务(整块)
            long step=(start+end)/100;
            ArrayList<p38> subTasks=new ArrayList<p38>();
            long pos=start;
            for(int i=0;i<100;++i){
                long lastOne=pos+step;
                if(lastOne>end)lastOne=end;
                p38 subTask=new p38(pos,lastOne);
                pos+=step+1;
                subTasks.add(subTask);
                //使用fork提交子任务
                subTask.fork();
            }
            //所有子任务结束后,再次求和
            for(p38 t:subTasks){
                sum+=t.join();
            }
        }
        return sum;
    }


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        ForkJoinPool forkjoinpool=new ForkJoinPool();
        p38 task=new p38(0,200000L);
        ForkJoinTask<Long> result=forkjoinpool.submit(task);
        try{
            long res=result.get();
            System.out.println("sum="+res);
        }catch(Exception e){
            e.printStackTrace();
        }
    }

}

什么时候要加锁?

如果只是读操作,没有写操作,则可以不用加锁,此种情形下,变量加上final关键字;
如果有写操作,但是变量的写操作跟当前的值无关联,且与其他的变量也无关联,则可考虑变量加上volatile关键字,同时写操作方法通过synchronized加锁;
如果有写操作,且写操作依赖变量的当前值(如:i++),则getXXX和写操作方法都要通过synchronized加锁。

线程池是自带锁的.

JDK 并发容器


Tip:

这点有点迷:P128

其中CopyOnWrite是高效的读取,在这个容器中,写入不会阻塞读取.

跳表

跳表是一种可以快速查找的数据结构,它有点类似于平衡树,它只需要部分锁即可,而跳表的时间复杂度也是O(log n)

更多的数据结构可以见线程那个包

Done

计划2-LintCode

(2) 尾部的零(Easy)

因为2的数量远大于5,统计5的数量即可

public class Solution {
    /*
     * @param n: An integer
     * @return: An integer, denote the number of trailing zeros in n!
     */

    public long trailingZeros(long n) {
        // write your code here, try to do it without arithmetic operators.
        long cnt=0,k=n;

        while(k>0){
            cnt+=k/5;
            k/=5;
        }
        return cnt;
    }
}

(3) 统计数字(中等)

伪数位DP

public class Solution {
    /*
     * @param : An integer
     * @param : An integer
     * @return: An integer denote the count of digit k in 1..n
     */

    public int digitCounts(int k, int n) {
        // write your code here
        int cnt=0,mt=1,tmp=0;
        int a=n;
        if(k==0)tmp=1;
        while(a>0){
            int digit=a%10;
            a/=10;
            if(digit>k)cnt+=(a+1-tmp)*mt;
            else if(digit==k) cnt+=(a-tmp)*mt+n%mt+1;
            else cnt+=a*mt;
            mt*=10;
        }
        cnt+=tmp;
        return cnt;
    }
};

(4) 丑数二(中等)

筛法只能过94%

因为他后面的数据超过10亿!….

public class Solution {
    /**
     * @param n: An integer
     * @return: the nth prime number as description.
     */
        int[] ans=new int[767];
        boolean[] is=new boolean[10000000];  
        int tot=0;

        void init(int n){
            for(int i=0;i<10000000;++i) is[i]=false;
            is[1]=true;
            ans[tot++]=1;
            for(int i=1;i<10000000;++i){
                if(is[i]){
                    for(int j=i*2;j<10000000;j*=2){
                        if(!is[j]){
                            is[j]=true;
                            ans[tot++]=j;
                        }
                    }
                    for(int j=i*3;j<10000000;j*=3){
                        if(!is[j]){
                            is[j]=true;
                            ans[tot++]=j;
                        }
                    }
                    for(int j=i*5;j<10000000;j*=5){
                        if(!is[j]){
                            is[j]=true;
                            ans[tot++]=j;
                        }
                    }
                }
            }
        }

    public int nthUglyNumber(int n) {
        // write your code here
            init(n);
            //ans=IntStream.of(ans).boxed().sorted().mapToInt(Integer::intValue).toArray();
            Arrays.sort(ans);
            return ans[n-1];
    }
}

用HashSet+Dfs AC

因为他给数据了,所以在已知数据是INT_MAX的前提下就好做多了

public class Solution {
    /**
     * @param n: An integer
     * @return: the nth prime number as description.
     */
    HashSet<Integer> tSet=new HashSet<>();
    int[] ans=new int[1665];
    int tot=0;
    void dfs(long num){
        if(num>(long)1898437500)return;
        if(tSet.size()>=1665) return;
        if(tSet.contains((int)num)) return;
        else{
            tSet.add((int)num);
            if(tot==1665)return;
            ans[tot++]=(int)num;
            dfs(num*2);
            dfs(num*3);
            dfs(num*5);
        }
    }

    public int nthUglyNumber(int n) {
        // write your code here
        dfs(1);
        Arrays.sort(ans);
        return ans[n-1];
    }
}

找规律的解法

可以发现只需要三个指针指向P1P2P3,同步前移,第n个就是这三个中最小的一个

class Solution {
public:
    /**
     * @param n: An integer
     * @return: the nth prime number as description.
     */
    #define min(a,b) ((a)<(b)?(a):(b))
    #define min3(a,b,c) (min(min(a,b),min(a,c)))
    int nthUglyNumber(int n) {
        int i = 1;
        int p2 = 0;
        int p3 = 0;
        int p5 = 0;
        int uglyNum[6048] = {0};
        uglyNum[0] = 1;
        while ( i < n ) {
            uglyNum[i] = min3(uglyNum[p2] * 2, uglyNum[p3] * 3, uglyNum[p5] * 5);
            if (uglyNum[i] == uglyNum[p2] * 2) {
                p2++;
            }
            if (uglyNum[i] == uglyNum[p3] * 3) {
                p3++;
            }
            if (uglyNum[i] == uglyNum[p5] * 5) {
                p5++;
            }
            i++;
        }
        return uglyNum[n-1];
    }
};

(5) – 第K大(中等)

方法:

利用快速排序的分块算法(Partition)+二分查找的思想解决即可.

public class Topic_5 {
    public static void main(String[] args){
        int[] nums=new int[]{9,3,2,4,8};
        System.out.println(kthLargestElement(3,nums));
    }

    //用首元素做pivot
    private static int partition(int l,int r,int[] nums){
        int pivot=nums[l];
        int temp=nums[l],low=l,high=r;
        while(low<high){
            while(low<high && nums[high]<=temp){
                high--;
            }
            nums[low]=nums[high];
            while(low<high && nums[low]>=temp){
                low++;
            }
            nums[high]=nums[low];
        }
        nums[low]=temp;
        return low;
    }

    public static int kthLargestElement(int n, int[] nums) {
        // write your code here
        int l=0,r=nums.length - 1;
        while(l<r){
            int k=partition(l,r,nums);
            if(k==n-1) break;
            if(k<n-1) l=k+1;
            else if(k>n-1) r=k-1;
        }
        return nums[n-1];
    }
}

(6) – 合并有序数组(简单)

方法:

常规合并

public class Solution {
    /**
     * @param A: sorted integer array A
     * @param B: sorted integer array B
     * @return: A new sorted integer array
     */

    private int[] solve(int A[],int B[]){
        int[] res=new int[A.length+B.length];
        int tagA=0,tagB=0,tot=0;
        while(tagA<A.length && tagB<B.length){
            if(A[tagA]<B[tagB])res[tot++]=A[tagA++];
            else res[tot++]=B[tagB++];
        }
        while(tagA<A.length){
            res[tot++]=A[tagA++];
        }
        while(tagB<B.length){
            res[tot++]=B[tagB++];
        }
        return res;
    }

    public int[] mergeSortedArray(int[] A, int[] B) {
        // write your code here
        return solve(A,B);
    }
}

(7) – 序列化二叉树与反序列化

注意bfs序列化后最简单的反序列化是for循环.
dfs序列化后最简单的反序列是递归.
当然也可以用两序遍历

import sun.reflect.generics.tree.Tree;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class TOPIC_6 {
    public static class TreeNode {
        public int val;
        public TreeNode left, right;
        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }

    public static void main(String[] args){
        TreeNode nt=Solution.deserialize("1,2,3,#,#,#,#,");
        System.out.println(Solution.serialize(nt));
    }

    public static class Solution {
        /**
         * This method will be invoked first, you should design your own algorithm
         * to serialize a binary tree which denote by a root node to a string which
         * can be easily deserialized by your own "deserialize" method later.
         */

        public static void dfs(TreeNode root,StringBuilder data){
            if(root==null){
                data.append("#,");
            }else{
                data.append(String.valueOf(root.val)+",");
                dfs(root.left,data);
                dfs(root.right,data);
            }
        }

        public static String serialize(TreeNode root) {
            // write your code here
            StringBuilder data=new StringBuilder();
            dfs(root,data);
            return data.toString();
        }

        // Decodes your encoded data to tree.
        public static TreeNode deserialize(String data) {
            LinkedList<String> que = new LinkedList<String>();
            que.addAll(Arrays.asList(data.split(",")));
            return deserial(que);
        }

        private static TreeNode deserial(LinkedList<String> que){
            String str = que.pollFirst();
            if(str.equals("#")){
                return null;
            }
            TreeNode root = new TreeNode(Integer.valueOf(str));
            if(que.size()!=0) {
                root.left = deserial(que);
                root.right = deserial(que);
            }
            return root;
        }
    }
}

(8) 旋转字符串

剑指Offer上的一道题

先整体旋转,然后把offset前后各旋转一次即可

public class Solution {
    /**
     * @param str: An array of char
     * @param offset: An integer
     * @return: nothing
     */

    void Reverse(char[] str,int start,int end){
        while(start<end){
            if(end-1<=start)break;
            str[start]^=str[end-1];
            str[end-1]^=str[start];
            str[start]^=str[end-1];
            start++;end--;
        }
    } 

    public void rotateString(char[] str, int offset) {
        // write your code here
        int len=str.length;
        if(len<=0)return;
        int fnos=offset%len;
        Reverse(str,0,len);
        Reverse(str,0,fnos);
        Reverse(str,fnos,len);
    }
}

(9) – 嘶嘶

public class Solution {
    /**
     * @param n: An integer
     * @return: A list of strings.
     */
    public List<String> fizzBuzz(int n) {
        // write your code here
        List<String> ans=new LinkedList<String>();
        for(int i=1;i<=n;++i){
            if(i%3==0 && i%5==0) ans.add("fizz buzz");
            else if(i%3==0) ans.add("fizz");
            else if(i%5==0) ans.add("buzz");
            else ans.add(String.valueOf(i));
        }
        return ans;
    }
}

(114) 不同的路径(中等)

很明显是杨辉三角,求C(n,m)
当然,也可以用动态规划,dp[i][j]=dp[i-1][j]+dp[i][j-1]

public class Solution {
    /**
     * @param m: positive integer (1 <= m <= 100)
     * @param n: positive integer (1 <= n <= 100)
     * @return: An integer
     */
    public int[][] res=new int[204][204];
    public void init(){
        res[0][0]=1;
        for(int i=1;i<=200;++i){
            res[i][0]=1;
            for(int j=1;j<=i;++j){
                res[i][j]=res[i-1][j-1]+res[i-1][j];
            }
        }
    }

    public int uniquePaths(int m, int n) {
        // write your code here
        init();
        return res[m+n-2][m-1];
    }
}

计划:技术栈完善2-实战JAVA高并发程序设计-第二章

Java并行程序基础

进程(Process)

进程:

1.是计算机中的程序关于某数据集合上的一次运行活动.
2.是系统进行资源分配和调度的基本单位
3.是操作系统结构的基础
4.早期,进程是程序的基本执行实体
5.当代,进程是线程的容器
6.程序是指令、数据及其组织形式的描述,进程是程序的实体

我们使用多线程而非使用多进程去进行并发程序的设计,是因为线程间的切换和调度的成本远小于进程.

线程的生命周期

Java中的线程就是继承Runnable,故生命周期如上图所示.

以下是Java.lang.Thread中关于State的枚举定义源码:

    public enum State {
        /**
         * Thread state for a thread which has not yet started.
         */
        NEW,

        /**
         * Thread state for a runnable thread.  A thread in the runnable
         * state is executing in the Java virtual machine but it may
         * be waiting for other resources from the operating system
         * such as processor.
         */
        RUNNABLE,

        /**
         * Thread state for a thread blocked waiting for a monitor lock.
         * A thread in the blocked state is waiting for a monitor lock
         * to enter a synchronized block/method or
         * reenter a synchronized block/method after calling
         * {@link Object#wait() Object.wait}.
         */
        BLOCKED,

        /**
         * Thread state for a waiting thread.
         * A thread is in the waiting state due to calling one of the
         * following methods:
         * <ul>
         *   <li>{@link Object#wait() Object.wait} with no timeout</li>
         *   <li>{@link #join() Thread.join} with no timeout</li>
         *   <li>{@link LockSupport#park() LockSupport.park}</li>
         * </ul>
         *
         * <p>A thread in the waiting state is waiting for another thread to
         * perform a particular action.
         *
         * For example, a thread that has called <tt>Object.wait()</tt>
         * on an object is waiting for another thread to call
         * <tt>Object.notify()</tt> or <tt>Object.notifyAll()</tt> on
         * that object. A thread that has called <tt>Thread.join()</tt>
         * is waiting for a specified thread to terminate.
         */
        WAITING,

        /**
         * Thread state for a waiting thread with a specified waiting time.
         * A thread is in the timed waiting state due to calling one of
         * the following methods with a specified positive waiting time:
         * <ul>
         *   <li>{@link #sleep Thread.sleep}</li>
         *   <li>{@link Object#wait(long) Object.wait} with timeout</li>
         *   <li>{@link #join(long) Thread.join} with timeout</li>
         *   <li>{@link LockSupport#parkNanos LockSupport.parkNanos}</li>
         *   <li>{@link LockSupport#parkUntil LockSupport.parkUntil}</li>
         * </ul>
         */
        TIMED_WAITING,

        /**
         * Thread state for a terminated thread.
         * The thread has completed execution.
         */
        TERMINATED;
    }

初始线程: 线程的基本操作

新建线程

线程启动时的调用顺序
start()->run()
所以,当我们使用start启动线程时是真正启动了一个线程,而在这个线程中调用run方法.
而如果使用了run(),则代表只是调用了一次run函数.

使用匿名内部类修改run方法,然后启动线程


public class p21 { public static void main(String[] args){ Thread t1=new Thread(){ @Override public void run(){ System.out.println("Hello, I'm t1"); } }; t1.start(); } }

使用Runnable接口来作为Thread的构造参数传入

以下是Runnable接口的源码:

@FunctionalInterface
public interface Runnable {
    public abstract void run();
}

可以发现,我们只需要实现run方法即可.
当我们调用Thread的run方法时,他会先判断下是否有Rannable,如果有,则调用Runnable的run方法.

    @Override
    public void run() {
        if (target != null) {
            target.run();
        }
    }

我们来使用Runnable接口实现线程


public class p21 implements Runnable { public static void main(String[] args){ Thread t1=new Thread(){ @Override public void run(){ System.out.println("Hello, I'm t1"); } }; t1.start(); Thread t2=new Thread(new p21()); t2.start(); } @Override public void run(){ System.out.println("Hello,I'm t2."); } }

这样就避免了重载Thread的run()方法,也是最常用的做法

终止线程

当我们在实现某些功能时,可能会让一些线程常驻在内存中.
那么我们该如何停止这些线程呢?
Thread内部有一个Stop()的方法,但他已被标注为将废弃,因为该方法太过暴力,很有可能造成数据不一致的问题.

因为stop方法会在结束线程时,直接终止线程,并且释放掉这个线程的所有锁.而这些锁则是为了保证对象的一致性.如果此时,写线程写到一半,被强行终止,那么对象的完整性就可能会被破坏.
而因为锁被释放了,所以另一个线程就顺理成章的读到了这个不完整的对象…

测试

我们用一个程序来模拟下上面说的情况:
具体思路为->开启读取线程,如果User名字和id不一样,输出->不停地创建修改线程,修改的id和name一样->修改完成后stop()->观察结果


public class p22 { public static User u=new User(); public static class User{ private int id; public int getId() { return id; } public void setId(int id) { this.id = id; } public String getName() { return name; } public void setName(String name) { this.name = name; } private String name; public User(){ id=0; name="0"; } @Override public String toString(){ return "User [id="+id+",name="+name+"]"; } } public static class ChangeObjectThread extends Thread{ @Override public void run(){ while(true){ synchronized(u){ int v=(int)(System.currentTimeMillis()/1000); u.setId(v); //Oh,do sth.else try{ Thread.sleep(100); }catch(InterruptedException e){ e.printStackTrace(); } u.setName(String.valueOf(v)); } Thread.yield(); } } } public static class ReadObjectThread extends Thread{ @Override public void run(){ while(true){ synchronized(u){ if(u.getId()!=Integer.parseInt(u.getName())){ System.out.println(u.toString()); } } Thread.yield(); } } } public static void main(String[] args) throws InterruptedException { new ReadObjectThread().start(); while(true){ Thread t=new ChangeObjectThread(); t.start(); Thread.sleep(100); t.stop(); } } }

输出:

User [id=1529221875,name=1529221874]
User [id=1529221875,name=1529221874]
User [id=1529221875,name=1529221874]
User [id=1529221875,name=1529221874]
User [id=1529221875,name=1529221874]
User [id=1529221875,name=1529221874]
User [id=1529221875,name=1529221874]

我们发现会出现很多如此的错误,为什么呢?和之前一样的原因,指令的顺序在优化中可能被更改,而线程的执行顺序也和调度算法有关,所以就造成了有可能某线程对User数据修改时sleep了一段时间,而这段时间内突然被stop了,其他的线程就拿到了不完整的数据.

当然,如果你将两个sleep都设置为0就不会出现这种错误了.

自定义线程停止

如何解决这种问题呢?

我们自行决定线程何时退出就可以了。

  • volatile关键字
    > 添加该关键字的变量是:
    >> 不同线程访问和修改的变量

即该指令不会因为编译器的优化而忽略,且要求每次直接读值.

我们只需要为ChangeObjectThread添加一个方法stopMe(),
当stopme为true的时候才可以读取,为false的时候就禁止读取.并且直接退出run方法.
这也就保证了不会导致修改中途被撤销.


public class p22 { public static User u=new User(); public static class User{ private int id; public int getId() { return id; } public void setId(int id) { this.id = id; } public String getName() { return name; } public void setName(String name) { this.name = name; } private String name; public User(){ id=0; name="0"; } @Override public String toString(){ return "User [id="+id+",name="+name+"]"; } } public static class ChangeObjectThread extends Thread{ volatile boolean stopme=false; public void stopMe(){ stopme=true; } @Override public void run(){ while(true){ synchronized(u){ if(stopme){ System.out.println("exit by stop me"); break; } int v=(int)(System.currentTimeMillis()/1000); u.setId(v); //Oh,do sth.else try{ Thread.sleep(100); }catch(InterruptedException e){ e.printStackTrace(); } u.setName(String.valueOf(v)); } Thread.yield(); } } } public static class ReadObjectThread extends Thread{ @Override public void run(){ while(true){ synchronized(u){ if(u.getId()!=Integer.parseInt(u.getName())){ System.out.println(u.toString()); } } Thread.yield(); } } } public static void main(String[] args) throws InterruptedException { new ReadObjectThread().start(); while(true){ ChangeObjectThread t=new ChangeObjectThread(); t.start(); Thread.sleep(100); t.stopMe(); } } }

线程中断

为了解决stop可能会导致数据冲突的问题,JDK中提供了三个方法来实现线程中断.

线程中断

即线程中断不会使线程立即退出,而是给线程发一个通知,告知目标线程要中断了,至于如何处理,何时中断,由目标决定.


public class p23 { public static void main(String[] args) throws Exception{ // TODO Auto-generated method stub Thread t1=new Thread(){ @Override public void run(){ while(true){ if(Thread.currentThread().isInterrupted()){ System.out.println("Interruted!"); break; } Thread.yield(); } } }; t1.start(); Thread.sleep(100); t1.interrupt(); } }

Thread.sleep函数

他的签名如下:

Thread.sleep()会让当前线程休眠若干时间,他会抛出一个InterruptedException中断异常,这个异常不是运行时异常,也就是说程序必须捕获并处理它,当线程休眠时,如果被中断,该异常就会产生.


public class p23 { public static void main(String[] args) throws Exception{ // TODO Auto-generated method stub Thread t1=new Thread(){ @Override public void run(){ while(true){ if(Thread.currentThread().isInterrupted()){ System.out.println("Interruted!"); break; } try{ Thread.sleep(2000); }catch(InterruptedException e){ System.out.println("Interrpted When Sleep"); Thread.currentThread().interrupt(); } Thread.yield(); } } }; t1.start(); Thread.sleep(100); t1.interrupt(); } }

所以我们必须在捕捉该异常的同时再次放出中断异常,这样才能保证该线程被正常中断.

wait()与notify()

为了支持多线程间协作,JDK提供了等待wait()和通知notify()两个方法.
但这两个方法不存在Thread类中,而是输出Object类.这也就意味着任意的对象都可以调用该方法.

两个方法签名如下:

public final void wait() throws InterruptedException
public final native void notify()





简单的例子:


public class p24 { final static Object object = new Object(); public static class T1 extends Thread{ public void run(){ synchronized(object){ System.out.println(System.currentTimeMillis()+":T1 start!"); try{ System.out.println(System.currentTimeMillis()+":T1 wait for object"); object.wait(); }catch(InterruptedException e){ e.printStackTrace(); } System.out.println(System.currentTimeMillis()+":T1 end!"); } } } public static class T2 extends Thread{ public void run(){ synchronized(object){ System.out.println(System.currentTimeMillis()+":T2 start! notify one thread"); object.notify(); System.out.println(System.currentTimeMillis()+":T2 end!"); try{ Thread.sleep(2000); }catch(InterruptedException e){ e.printStackTrace(); } } } } public static void main(String[] args) { Thread t1=new T1(); Thread t2=new T2(); t1.start(); t2.start(); } }

结果:

1529292002347:T1 start!
1529292002347:T1 wait for object
1529292002348:T2 start! notify one thread
1529292002348:T2 end!
1529292004348:T1 end!

Tip: wait会释放所有的锁

挂起(suspend)和继续执行(resume)线程

suspend乍看起来和stop或者wait相似简单的用法,但是,值得注意的是,suspend并不会释放任何资源和锁.所以就会导致其他想要索取资源的线程也被牵连.
而且resume也是存在问题,有可能在suspend前执行,这就会导致当前线程的状态被误判.

等待线程结束(join)和谦让(yield)

一个线程需要等待另一个线程的结束才能继续执行(依赖输出)则用join.

public final void join() throws InterruptedExcption

public final synchronized void join(long millis) throws InterruptedException

第一个表示无限等待,他会一直阻塞线程,直到目标线程执行完毕.
第二个表示如果超过一段时间还没等到,则不等待,继续执行.

例:


public class p25 { public volatile static int i=0; public static class AddThread extends Thread{ @Override public void run(){ for(i=0;i<10000000;++i); } } public static void main(String[] args) throws InterruptedException { // TODO Auto-generated method stub AddThread at=new AddThread(); at.start(); at.join(); System.out.println(i); } }

上述主函数中,如果不执行join来等待线程结束,则更多的可能是只会出现在线程结束前输出i的值(比如0)的情况.
如果用join来等待的话,则最终一定会输出1e7.

join的本质是让调用线程wait()在当前线程对象实例上.

另一个: yield()方法是让当前线程让出CPU,然后重新加入到资源的争抢当中.如果觉得一个线程不是很重要,又害怕它占用过多的CPU,可以调用yield方法.

volatile与Java内存模型(JMM)

使用volatitle就表示告诉了虚拟机这个变量很可能被某线程修改.
虚拟机会特别小心的处理这个变量,尤其是当发现修改的顺序是反的时候.
volatile可以很大程度上保证变量的完整性,但不保证操作的原子性,比如i++的原子操作完整性(i为32位下的长整型)

此外,volatile也能保证数据的可见性和有序性.

例:


public class p26 { private volatile static boolean ready; private static int number; private static class ReaderThread extends Thread{ public void run(){ while(!ready); System.out.println(number); } } public static void main(String[] args) throws InterruptedException{ new ReaderThread().start(); Thread.sleep(1000); number=42; ready=true; Thread.sleep(10000); } }

因为指令的优化,在Server下线程无法”看到”ready”被修改.所以会无限的执行下去,这就是典型的可见性问题.

而加了volatiel修饰后的ready就不会出现这种情况了.

线程组

一个系统中如果存在过多的线程,而且分工比较明确,就可以将相同功能的线程放置在一个线程组内.这样会使效率更高些.


public class p27 implements Runnable{ public static void main(String[] args) { // TODO Auto-generated method stub ThreadGroup tg=new ThreadGroup("PrintGroup"); Thread t1=new Thread(tg,new p27(),"T1"); Thread t2=new Thread(tg,new p27(),"T2"); t1.start(); t2.start(); System.out.println(tg.activeCount()); tg.list(); //tg.stop();-慎用 } @Override public void run(){ String groupAndName=Thread.currentThread().getThreadGroup().getName() +"-"+Thread.currentThread().getName(); while(true){ System.out.println("I am "+groupAndName); try{ Thread.sleep(3000); }catch(InterruptedException e){ e.printStackTrace(); } } } }

驻守后台-守护线程(Daemon)

JVM内部的实现是如果运行的程序只剩下守护线程的话,程序将终止运行,直接结束。所以守护线程是作为辅助线程存在的

线程优先级

Java可以自定义线程的优先级.

设置优先级用 (Thread).setPriority(优先级(1~10))

线程安全概念与synchronized

线程安全是并行程序开发的一大重点.
线程安全例子:


public class p28 implements Runnable{ static p28 instance=new p28(); static volatile int i=0; public static void increase(){ i++; } @Override public void run(){ for(int j=0;j<10000000;++j){ increase(); } } public static void main(String[] args) throws InterruptedException{ // TODO Auto-generated method stub Thread t1=new Thread(instance); Thread t2=new Thread(instance); t1.start(); t2.start(); t1.join();t2.join(); System.out.println(i); } }

如果把t1.join()放到t1.start()后面的话,输出就为正常结果.但如上这样子放的话,也就代表了两个线程实际上是一起执行的.但在某一时刻t1.join开启以后t2就暂停执行等待t1执行完再继续.

我们可以使用synchronized关键字来对同步的代码加锁.使得每一次只能有一个线程进入同步块.

代码在书上的-P58,之前写过很多次了.

并发下的ArrayList

ArrayList是线程不安全的,用Vector代替线程不安全的ArrayList即可.

并发下的HashMap

并发下的HashMap可能会出现死循环的现象,为什么?下面来看一段代码

这段代码证明HashMap的插入是按照链表的方法插入的.而当死循环时就代表当前的HashMap链表被破坏成了环.也就导致了死循环.
(但JDK8已经避免了这种情况的产生)

jps和jstack工具

jps是查看当前所有大线程
jstack是定位到对应的线程以及代码

Integer其实使用工厂方法进行赋值的

如果我们想要给Integer加锁时,我们不能直接在Integer(int)变量上加锁,因为Integer是用工厂方法进行赋值,每次给int赋值时都会重新生成一个Integer对象.
所以我们需要在改变量所在的实例化对象上加锁.

比如:
public class k implements Runnable{
int a;
public void run(){
Code here.
}
}
我们就需要在实例化后的k对象上加锁,而不是在a上加锁.

计划:技术栈完善2-实战Java高并发程序设计-第一章

第一章

同步与异步

如图
同步是链式进行:只有当一个任务结束后才可以继续下一个
而异步则是前进->等待消息返回(同时继续前进进行其他的任务)->消息返回,继续前进.

并发(Concurrency)和并行(Parallelism)

如图
并发是以时间片为单位看似同步进行
并行是实际上的同步进行(一般为多核)

临界区

即可以有多个线程来使用它,但同一时刻只能有一个线程来使用它.
一但临界区被一个线程占用,其他线程就必须等待.

阻塞(Blocking)和非阻塞(Non-Blocking)

阻塞: 一个线程占用了临界区资源,那么其他所有需要这个资源的线程就必须在这个临界区中进行等待.
非阻塞: 任何线程都不会阻碍其他线程的执行,所有的线程都会尝试不断向前继续执行.

死锁(Deadlock)、饥饿(Starvation)和活锁(Livelock)

死锁: 如上图,在专业课程中,我们所学到的死锁经常会这样描述-

单行道(堵塞/等待):

线程A需求资源B,占用资源A(资源A最大为1个)
线程B需求资源A,占用资源B(资源B最大为1个)
他俩同时锁住了这两个资源并等待想要的资源.卡掉了.

N个同理.大家都不想放掉自己的资源,又想要别人的.

饥饿: 在每一个线程都有优先级的时候,如果一个线程的优先级始终在下面,他就永远得不到资源了,当然,不一定只有这种情况.

与死锁相比,姐还是有可能在一段时间后自行解决的

活锁: 两人互相谦让,死脑筋的想着从相同的口出/进就是活锁,本来有机会解锁的…

并发级别

由于临界区的存在,多线程之间的并发必须受到控制。根据控制并发的策略,我们可以把并发的级别进行分类,大致可以分为阻塞、无饥饿、无障碍、无锁、无等待几种.

阻塞(Blocking)

当我们使用synchronized关键字,或者重入锁时,我们得到的就是阻塞的线程.

无论哪种情况,都会在试图执行后续代码前,得到的是临界区的锁,如果得不到,都会被挂起等待,知道占用了所需资源为止.

PS:以上均未遇见,书上说在后面

无饥饿(Starvation-Free)

如果线程有优先级,而选用的线程调度算法允许插队,成为非公平,如下图,那么最下面的很大可能会产生饥饿

如果线程是公平的,就不会产生饥饿,不管来的线程优先级多么的高,要想获得资源,就必须 乖 ♂ 乖 ♂ 站 ♂ 好 ♂,所有的线程都会执行.

无障碍(Obstruction-Free)

不对临界区设任何门栏,任何线程想进就进,想出就出,如果出现数据混乱了怎么办

一旦检测到了数据改坏了,就会对自己所做的修改进行回滚.确保数据安全.如果没有竞争发生,数据就会很安全的离开临界区.

故如果有严重的错误时,所有的线程都会不断地会滚自己的操作.导致没有一个线程可以走出来,顾我们会希望至少有一个县城可以安全地走出来.

一致性标记:线程在操作之前,先读取并保存这个标记,在操作完成后,再次读取,检查这个标记是否被更改过.如果两者一致,说明资源访问没又发生冲突,安全.如果不一致,需要重试操作.而任何尝试修改数据的线程,都需要在修改前更改这个一致性标记,表示这个数据不再安全.

如下图

无锁(Lock-Free)

所有线程都可以尝试对临界区进行访问,但不同的是,无锁的并发保证必然有一个线程能够在有限步内完成操作离开临界区.

无锁是一个无穷循环。在这个循环中,线程会不断尝试修改共享变量,如果没有冲突,修改成功,则退出,否则继续尝试修改,但无论如何,无锁一定会有一个线程可以胜出.

但是无锁会出现类似于饥饿的情况.

例:

while(!atomicVar.compareAndSet(localVar,localVal+1)){
    localVar=atomicVar.get();
}

无等待(Wait-Free)

无等待是无锁++

它要求所有的线程都需要在有限步内完成,这样就不会引起饥饿问题。如果限制这个步骤上限,还可以进一步分解成有界无等待和线程数无关的无等待几种,他们之间的区别只是对循环次数的限制不同.

一种常用的方法是RCU(Read-Copy-Update)。它的基本思想是,对数据的读写可以不加控制。因此所有的读线程都是无等待的。

怎么处理数据混乱问题呢?

拿走需要修改的数据的Copy那部分,然后寻找合适的时机回写数据.

有关并行的两个重要定律

主要作用,提高性能

Amdahl定律

加速比定义:
加速比 = 优化前系统耗时 / 优化后系统耗时

加速比越高,表明优化效果越明显

T: 时间
T1: 一个处理器优化前耗时
Tn: n个处理器优化后的耗时
n: 处理器个数1
F: 程序中只能串行执行的比例

公式推导:

通俗来讲: 1/n(1-F)就是将多核时一个核的比

加速比,当n->无穷,那么加速比与系统的串行率成反比,如果系统中必须有50%的代码串行执行,那么系统的最大加速比为2.

例:


Gustafson定律

可以发现Gf定律是通过时间来推导的.

JMM

JVM是Java虚拟机
而JMM是Java的内存模型
故JMM多用于线程/进程管理

JMM是围绕着多线程的原子性,可见性和有序性来建立的

原子性

原子性是指一个程序不可中断,一旦开始执行,就不会被其他线程干扰.

值得一提的是,int是原子性的,而long在32位JVM上的读取和输入是非原子性的.


public class p11 { public static long t=0; public static class ChangeT implements Runnable{ private long to; public ChangeT(long to){ this.to=to; } @Override public void run(){ while(true){ p11.t=to; Thread.yield(); } } } public static class ReadT implements Runnable{ @Override public void run(){ while(true){ long tmp=p11.t; if(tmp!=111L && tmp!=-999L && tmp!=333L && tmp!=-444L) System.out.println(tmp); Thread.yield(); } } } public static void main(String[] args) { new Thread(new ChangeT(111L)).start(); new Thread(new ChangeT(-999L)).start(); new Thread(new ChangeT(333L)).start(); new Thread(new ChangeT(444L)).start(); new Thread(new ReadT()).start(); } }

输出:

会发现根本就不是输入的四个值中的一个,因为他们互相影响了.

可见性(Visibility)

可见性是当一个线程修改了变量后,其他线程是否能够立即知道这个修改,显然,对于船型程序而言,可见性是不存在的.因为你在任何一个操作步骤中修改了某个变量,那么在后续步骤中,读取的这个变量,一定是修改后的(临界区被占用).

但在并行程序中就不同了.有可能知道,也可能不知道.
如:

CPU2和CPU1在一开始读取了cache上的数据,但CPU2在某条路径上更快的修改了cache,而CPU1无法得知,故CPU1内还是一个旧的值.修改则一定会发生错误.

无法保证能够从一个线程中观察另一个线程的变量.

编译器的向前优化

一个复杂一点的例子

对于大部分编译器而言,可能会对线程1进行向前替换优化,也就是r5=r1.x这条指令会被直接替换成r5=r2.因为他们都读取了r1.x,又发生在同一个线程中,因此,编译器可能会认为没必要二次读取.

有序性(Ordering)

程序在执行时,会出现指令重排,重拍后的指令与原指令未必一致.
这就导致了有可能出现在前面的代码后执行,在后面的代码先执行.
如:

指令重排

可以保证与串行语义一致,但没义务保证多线程间的语义也一致.
为什么要进行指令重排呢?
指令的执行分以下几步:
– 取值 IF
– 译码和去寄存器操作数 ID
– 执行或者有效地址计算 EX
– 存储器访问 MEM
– 写回 WB

汇编指令也不是一步就可以执行完的.
ALU:算数逻辑单元,是CPU的执行单元,是CPU的核心组成部分,主要功能是进行二进制算术运算.

因为指令执行的每一步都使用不同的硬件完成,聪明的工程师就发明了流水线技术.

防止流水线中断

流水线满载时,性能很不错,但是一旦中断,所有的硬件设备都会进入一个停顿期,再次满载又需要几个周期.因此,性能的损失蛮大的.

而指令重排则是防止流水线中断的一种方式.
我们来以一个例子看看中断到底是什么意思.
下图展示的是 A=B+C 这个操作的执行过程:
LW: load LW R1,B 将B加载到R1寄存器中
ADD: 加法 ADD R3,R1,R2 将R1+R2的值放到R3寄存器中
SW: store 存储,就是将R3寄存器的值保存到变量A中.

那两个大X代表的是等待R2的值,因为R2还未MEM,WB,所以R2寄存器内还没有值,
这就是一个中断,会直接的导致后面的慢一拍.

如何防止呢?

一个更复杂的例子:

好多中断是吧.为了减少中断,我们将将对程序没有影响的代码放到中断之前,将中断代码往后移一个单位即可,即充分利用时间.

重排后的结果:

哪些指令不能重排: Happen-Before 规则

第一章结束