集合的线程安全类

遗留的线程安全类

Hashtable，Vector直接把同步加到方法上

修饰的安全集合

装饰器模式，Syncronize*

JUC安全集合

Blocking型

大部分实现基于锁并提供阻塞的方法

JUC

AQS

   AbstractQueuedSynchronizer 是阻塞式的锁和相关的同步器工具的框架

ReentrantLock

如何重入

   用一个变量记录重入了多少次

NonfairSync

lock

   cas ,成功就吧ouner改为自己，否则acquire，把自己放进链表中

acquire

   tryacquire，成功就结束，失败的话还会尝试几次，然后才park，并为前驱标记，让前驱记得唤醒自己,如果曾经被打断的话，会被忽略，再次进入aqs队列，得到锁以后会打断自己来再次重新打断

异步模式-工作线程

线程不足导致饥饿

有两个线程A，B，任务有两种，上菜和做菜，显然上菜要等待做菜，如果AB都在执行上菜，就没有更多的线程做菜了，这就导致了AB在死等，注意这不是死锁，
所以不同的任务类型应该用不同的线程池

JDK的线程池

线程池状态，RUNNING，SHUTDOWN(不会再接受新任务了)，STOP(立刻停止)，TIDYING(任务执行完毕，即将TERMINATED)，TERMINATED

构造函数

1

public ThreadPollExecutor(int corePoolsize,int maximumPoolSize,long keepAliveTime,TimeUnit unit,BlockingQueue<Runnable> workQueue,ThreadFactory threadFactory,RejectedExecutionHandler handler)

• 核心线程数量
• 最大线程数量
• 就急线程生存时间
• 时间单位
• 阻塞队列
• 线程工厂: 给线程起个名字
• 拒绝策略

自定义线程池

把main看作任务的生产者，把线程看作任务的消费者，这时候模型就建立出来了
于是我们需要一个缓冲区，采取消费正生产者模式，然后让消费者不断消费，并在适当的时候创建新的消费者，如果所有任务都做完了，就取消消费者

给一个数字字符串S，一个数字m，
你需要计算出S有多少个划分，讲他划分为S1，S2，S3，。。 且每个数都是m的倍数，答案对1e9+7取模
例如 123456 2
可以划分为
123456
1234|56
12|3456
12|34|56

最近发现这题不对劲，有新想法，先上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

string s;
int m;
cin>>s>>m;
const int mod = 1e9+7;
int cnt=0;
int cur=0;
for(char ch:s){
   cur = (cur*10ll+ch-'0')%m;
   if(cur==0) cnt++;
}
int ans=0;
if(cur=0) ans=0;
else ans=1;
for(int i=1;i<cnt;i++) ans=(ans*2)%mod;
cout<<ans<<endl;

• 约定S下标从1开始到n结束，即S=S[1,n]
• 定义一个大数S的子串为S[l,r] 代表从l开始，到r结束，包含l和r，
• 定义一个大数S的划分序列为数组$${k_1,k_2,…k_i}$$, 表示S被划分为了$S[k_1,k_2-1],S[k_2,k_3-1]…$ ,显然这里有$$1=k_1\lt k_2\lt k_3…$$
• 我们不难贪心，每次都找靠左最短的序列，即在$$S[1,n]$$中找最短前缀$$S[1,k_2-1]$$,然后再到$$S[k_1,n]$$中找第二个前缀，于是我们找到了cnt个
• 于是我们可以在序列$${k_1,k_2,…k_i}$$中任意取一个子序列，他们都是合法的划分，
• 假设某个划分序列$${t_1,t_2,…t_j}$$不是$${k_1,k_2,…k_i}$$的子序列,我们先在t中找到一个最小的$$t_u$$, 他没有出现在k中,我们考虑他左边的是$$t_{u-1}$$,我们在k中找到最大的小于$$t_u$$的数$$k_v$$
• 现在$$t_{u-1}\lt k_v\lt t_u\lt k_{v+1}$$
• 现在我们来推翻这个假设，t说$$S[t_{u-1},t_u-1]%m=0$$,k说$$S[t_{u-1},k_v-1]%m=0$$, 那么我们可以推出$$S[k_v,t_u-1]%m=0$$,这个结论显然不成立，因为$$k_{v+1}\ne t_u$$

不可变就是线程安全

如String

拷贝构造函数

之间赋值

char[]构造

拷贝一份(保护性拷贝)

子串

如果下标起点和母串起点相同，则之间引用过去，否则保护性拷贝(不明白为啥不共用)

享元模式

最小化内存的使用，共用内存

包装类

valueOf, 比如Long如果在-128到127之间，就使用一个cache数组，又如String串池，BigDecimal和BigInteger的某些数组

保护

千万要注意这些类的函数组合起来操作就不一定安全了，需要用原子引用类来保护

CAS

compareAndSet(prev,next);无锁，无阻塞

为什么效率高

失败的话会重新尝试，但是锁会进行上下文切换，代价大

原子整形

AtomicInteger

1
2
3

incrementAndGet();
getAndAdd(5);
updateAndGet(value -> value*10);

JMM

Java Memory Model

• 原子性: 保证指令不会收到线程上下文切换的影响
• 可见性: 保证指令不会受到cpu缓存的影响
• 有序性: 保证指令不会受到cpu指令并行优化的影响

synchronized

锁住对象，放在静态方法前为锁类，放在普通方法前为锁类的对像。使用管程实现

线程安全类

String, Integer, StringBuffer,Random,Vector,Hashtable,juc;

加锁

把对象头的hash、Age和对象的指针放进自己的栈中，让对象头的hash、Age,位置指向自己的栈，
这时候来了另一个线程也想拿到锁，但是他肯定会失败，失败以后他就申请重量级锁，让对象头再次改变为指向管程，
当原来当线程想要释放锁的时候，依然使用cas，但是肯定失败，他发现现在的锁已经变成了重量级锁了。