corresponding


  • 首页

  • 标签

  • 分类

  • 归档

compare and swap

发表于 2018-09-11 | 分类于 多线程

悲观锁 VS. 乐观锁

在并发编程中,由于多线程同时处理同一数据会发生冲突,需要我们设定机制去解决这个冲突。通常是用锁的方式,锁又可以分成悲观锁和乐观锁。
1.顾名思义,前者是从悲观角度判断当前并发情况,认为多线程处理同一数据极有可能发生冲突。无论是否发生冲突,我们都会给数据前后加锁,组织其他线程修改。
2.后者从乐观角度判断当前并发情况,认为多线程处理同一数据几乎不会发生冲突。先按照预设的不冲突方式去处理数据,如果发现数据已被其他线程修改的话再做额外处理。
通过上面的描述,可以大概明确悲观锁和乐观锁的使用场景。悲观锁适用于冲突概率比较高的环境,乐观锁适用于冲突概率比较低的环境。
因为加锁解锁需要额外的开销,如果数据没有冲突仍加解锁,会多了平白无故的开销。在这样的场景下,乐观锁效率就会高得多。
常见的悲观锁有Synchronized、Lock等,乐观锁主要为CAS。接下去我们讲解下CAS。

CAS

CAS全称为Compare And Swap,直译过来就是比较和替换
适用的类:AtomicInteger,AtomicLong等基础数据类型
先看下AtomicInteger的调用函数

1
2
3
4
5
6
/*
* expect:期望值
* update:如果当前值等于期望值,则将当前值更新为update
* return:返回是否更新成功
*/
public final boolean compareAndSet(int expect, int update)

这里加入了expect,用来判断当前值是否等于预期值。因为在并发环境下,当前线程记录的值和实际值不一定相同(在之前记录和现在调用cas的间隔中被其他线程修改,而当前线程并不能感知到实际值的变化)。
简单的使用一次compareAndSet并不能完成任务。假设当前线程的任务是将值加一:

1
2
3
int current = get();
int expect = current + 1;
compareAndSet(current, expect);

因为如果值被其他线程修改,则不会触发更新。常用的操作方式是在外面包裹着循环:

1
2
3
4
5
6
7
8
public final int incrementAndGet() {
for (;;) {
int current = get();
int expect = current + 1;
if (compareAndSet(current, expect))
return next;
}
}

如果检测到冲突,数据更新失败,则重新开始新的一遍CAS,直至有一次数据没有冲突。
这里也能发现,如果冲突发生概率过高,函数可能会一直在循环中,效率会非常低下,应证了CAS适合在冲突发生概率不高的情况下调用。

CAS原理

CAS在底层是通过调用JNI(Java Native Interface)实现

1.oldvalue放在eax寄存器中,newvalue放在ecx中,addr(pointer)放在edx中。
2.cmpxchg指令首先比较addr指向的内存与oldvalue(eax),如果二者相等,将newvalue(ecx)放到addr所指向的内存中,同时设置Z标志1。
3.setne与andl 指令的操作的结果很简单:如果Z标志被设置,则eax为0,否则为1。程序执行最终eax放到xchg变量里。

通过底层的汇编代码给与CAS原子性,使得CAS的操作不能被分割,即在调用中值不能被其他线程修改。

CAS问题

接下去看下使用CAS出现的一些问题

ABA问题

A->B->A // 前面的A和后面A状态不一致,但是CAS无法识别
回到刚才的场景,当前线程需要将值加一,假设获取值和调用CAS中间有额外两个线程对数据都做了修改,一个线程加一,另外一个线程减一。在CAS判断是current仍旧与当前值相同,CAS的更新会生效。但是我们无法得知这中间有数据加一再减一的变化。当然在这个场景中,这不影响程序的结果,因为我们的程序设定就是将当前值并发的加一。
我们考虑再考虑一个现实场景,妈妈和爸爸为了奖励勤工俭学的孩子,发现到其银行卡账号金额等于100元就给孩子10元奖励,最多只有一位家长发放奖励。这里的CAS中current为100时,我们无法区分这两种情况:
1.孩子自己赚到100元;
2.赚到100元后其中一位父母给与10元奖励而后迅速消费掉,余额还是100元。
这时就需要使用AtomicStampedReference,可以理解成为各个状态打上stamp,在CAS判断时以stamp和值为准。

1
public boolean compareAndSet(V expectedReference, V newReference, int expectedStamp, int newStamp)

大家在git使用也会遇到类似问题,即使本地文件和服务端文件内容一致,中间也有可能有变更,所以git中使用文件版本号去判断文件一致性。

复合数据的CAS

在我们之前的讨论中,只针对一个共享变量的原子操作,无法同时保持多个变量的一致性。
在银行账号中,如果开通了美元账号,用户就同时有美元余额和人民币余额,必须保持两个变量的一致性。
这时候我们就需要AtomicReference去解决这个问题,这是AtomicReference的主要源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class AtomicReference<V>  implements java.io.Serializable {
private static final long serialVersionUID = -1848883965231344442L;

// 获取Unsafe对象,Unsafe的作用是提供CAS操作
private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long valueOffset;

static {
try {
valueOffset = unsafe.objectFieldOffset
(AtomicReference.class.getDeclaredField("value"));
} catch (Exception ex) { throw new Error(ex); }
}

// volatile类型
private volatile V value;

public final V get() {
return value;
}

public final boolean compareAndSet(V expect, V update) {
return unsafe.compareAndSwapObject(this, valueOffset, expect, update);
}
}

它是通过volatile和”Unsafe提供的CAS函数”实现原子操作。
1.value是volatile类型。这保证了当某线程修改value的值时,其他线程看到的value值都是最新的value值,即修改之后的volatile的值。
2.通过CAS设置value。这保证了当某线程池通过CAS函数(如compareAndSet函数)设置value时,它的操作是原子的,即线程在操作value时不会被中断。

ConcurrentLinkedQueue

在java中CAS典型的使用就是ConcurrentLinkedQueue,大家有兴趣的话去看下源码,非常精简高效。
这里就简单提一下要点,Queue队列最关键处理head和tail,如果每次加锁开销会比较高,所以分别用CAS去控制更新。

浅析IO

发表于 2018-07-02 | 分类于 IO

I/O

因为库文件的良好封装,我们在开发中可能不会直接使用IO读写,不过程序底层还是离不开IO。这里就来简单介绍下IO吧。
全称:Input/Output,顾名思义就是输入和输出。
场景:涉及到数据交换的地方,通常是磁盘读写、网络数据传输等。
磁盘读写场景:我们记录服务器的日志,最终都要写入文件中保存。如果我们想要分析这些日志,也需要重新从磁盘中读取这些文件。
网络传输场景:在浏览器中输入google.com这个地址,会向google的服务器发送一个请求,google服务器处理后传回google的首页,浏览器会把其中数据解析出来显示给用户。

挑战

I/O读写的核心逻辑很简单,主要是传输数据。但是在实际IO中还有一些挑战,就是我们需要花很多时间去等待IO传输。例如,我们浏览一个网页,需要花1s才能将服务端数据传到浏览器中,在浏览器中渲染和显示只需要0.01s。如果不做其他处理,从点击地址后一直等待页面显示,那就非常浪费时间。

出现这个现象的原因是:CPU和内存的速度远远高于外设传输数据的速度。
短期内这个矛盾没有办法从根源上来解决,但是聪明的程序员想出很多策略去优化I/O场景。

同步IO

原始场景

这是最原始的场景:我们只运行一个线程,服务端接收到浏览器请求后,等待IO读取结束再进行操作,中间无法处理任何响应。这样的体验一定是非常糟糕的,因为整个服务器无法处理其他请求。在刚才的例子中,点击网页后1s内都无法响应其他任何请求,这会让用户非常沮丧。

多线程

我们再稍微改善下,我们点击一个网页后,服务端新开一个线程去处理IO和其他操作。这时服务端还可以有其他线程去处理其他请求,这比原来好很多。

昂贵的线程

但是线程是一种非常昂贵的资源,有以下四个原因:
1.每个空线程就占512k~1M的内存,如果线程增加太多JVM压力会变大;
2.在Linux中线程就是进程,无论是新建和销毁都要调用重量级系统函数,非常占用CPU;
3.线程切换时,需要更新线程的上下文,原先线程缓存的指令和数据都需要重新加载。这会影响整个程序的运行效率,就像我们看英文文献时发现陌生单词后,打开字典去查,查询完毕后再继续阅读。需要重新回想之前前后文,影响阅读效率;
4.有可能会有大量请求同时返回,CPU占有率变得锯齿状,服务器不稳定。

线程池

了解到线程的昂贵开销后,我们考虑接入线程池,可以重复利用原有线程。例如实时性要求不高的情况下,服务端同时有100个请求,线程池有20个线程,用着20个线程反复利用处理请求。这样只需要创建和销毁20个线程。而不用线程池的情况下,需要创建和销毁100个线程。这样大大降低的线程的开销,但是还是不能根治问题。因为始终需要线程去解决问题,我们需要换一种新的策略去解决问题。

异步IO

异步IO,Asynchronous Input and Output,简称AIO
异步IO从新的角度解决问题,用户只发出IO请求,并不等待IO结果,然后就去执行其他代码了。一段时间后,当IO返回结果后,再通知用户进行处理。
举个例子,服务器接受到一个浏览器的请求,发送读取其请求的IO请求,但是并不等待IO结果,而是去处理其他操作。当IO请求返回结果后,服务端再去处理这段IO。

这样操作的好处非常明显:用户不需要新开线程去处理IO。而且用户不用维护数据读不齐时的逻辑,因为操作系统将处理好的数据交给用户。
按照上面说的种种好处,大家肯定会觉得现在主流处理的IO肯定是AIO。但是其实不然,因为一个很现实的原因,纯正支持AIO的操作系统比较少。

各种IO对比

上面是一张特别经典的IO对比图,上面将各种IO都列出来了。我们一个个分析:

阻塞IO

阻塞IO就是上面所说的同步IO,这里不继续讨论。
举个例子,我在奶茶店点了一杯奶茶,点好后就一直在柜台等着,直到奶茶做好。

非阻塞IO

非阻塞IO与阻塞IO不同,发起IO请求后,不需要一直等待,在拿到IO数据之前还可以做一些别的操作。那怎么知道何时能拿到IO数据呢?一般会采用轮询的方法。
轮询就是每隔一段时间去检查是否IO进入可读状态,如果发现数据不可读则立即返回不会阻塞。但是轮询浪费CPU资源,因为大部分时间是无数据可读,但是仍会不间断的反复地去查询。
举个例子,我在奶茶店点了一杯奶茶,没有选择一直等着,而是选择去边上的商店逛逛,每隔一分钟回奶茶店看看奶茶是否完成。但是这仍然会浪费你的时间,因为可能有多次查询的结果都是奶茶没完成。

IO复用

IO复用是基于非阻塞IO的,可以理解成多个IO请求委托给一个对象,让它去统一检查IO是否进入可读状态。这会带来效率的提升,因为不需要所有对象都去轮询。
把例子展开下,一个班级中每个同学都在奶茶店点了一杯奶茶,全权委托班长去轮询奶茶是否已经做好。每一杯奶茶做好了,班长就去通知对应的同学。

信号驱动IO

信号驱动IO就比较好理解。IO进入可读状态后,系统直接通知用户。
对应的例子是,我在奶茶店点了一杯奶茶,而且给店员留了手机号码。然后我就去边上商店逛逛,店员在制作完奶茶后会打电话通知我。不用每隔一段时间再去查看(轮询),也不需要委托给其他人让他去查看(IO复用),非常开心。

异步IO

异步IO和信号驱动IO模式比较接近,但是告知的时间点不同。信号驱动IO在操作系统内核读取完数据后告知用户,用户接到通知后还需要从内核中读取到用户空间,之后才可以使用IO传输过的数据。而异步IO中,操作系统已经把上面的两步全部做完,放到用户空间后再告知用户,用户可以直接使用IO传输过的数据。
这两个IO的对比再举个例子,我们在网上点了一台冰箱,有以下两个不同的场景。
信号驱动IO:快递员送到小区门口,然后快递员给我们打电话(内核空间中数据读取完成,进入可读状态),我们还需要从小区门口搬到房间(将数据从内核空间中读取到用户空间),然后再安装冰箱(使用IO的接收到的数据)。
异步IO:快递员直接将冰箱送到家,这里包含了仓库到小区门口和小区门口到房间两步(包括读取到内核空间,内核空间到用户空间),送到房间门口时再通知我,我直接可以安装冰箱。

NIO

NIO全称为Non-blocking I/O(在Java领域,也称为New I/O)
与上面所说的IO复用模式相同,其中一个重要的角色就是监控管理IO是否可读的对象,在NIO中这个对象是Selector。Selector有一个重要方法select,select维护一张监听套接字的列表(使用前需要注册Selector上),一直阻塞直到其中有一个套接字有数据可供读写。

上图中一个Selector管理着多个Channel,一个Channel代表一个IO通道。

我们用一个交通管理系统去类比下NIO中的主要对象:
Channel:车辆
Selector:调度系统
Buffer:车辆上的货物
Stream:货物

我们再看下主干代码,注意其中的注释:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 1.Channel注册到Selector中
channel.register(selector, opType);
// 2.Selector阻塞等待Channel变化
Set selectedKeys = selector.selectedKeys();
while(keyIterator.hasNext()) {
SelectionKey key = keyIterator.next();
keyIterator.remove();
// 3.按照类型做对应操作
if(key.isAcceptable()) {
// 注册新的Channel到Selector中
} else if (key.isReadable()) {
// 读操作
} else if (key.isWritable()) {
// 写操作
}
}

多线程基础小问

发表于 2018-06-22 | 分类于 java

对于多线程我自认为有所了解,但是到探究其中细节还是会一脸懵逼。
在经过一段时间系统学习后,回头去看多线程的基础知识,发现之前有很多地方理解错误。
这里提出多线程的几个小问题,希望能抛砖引玉,让大家借此有更加深入的思考。

wait和sleep的差异?

这个问题看上去很简单,大家都能说出一二三来。
a.wait是Object的方法;sleep是Thread方法。
b.wait只能在同步代码中调用。
c.wait会释放出锁;sleep不会释放出锁。

这次我们就展开深入下:

为什么要设置wait是Object的方法;sleep是Thread方法?

个人理解是这样的,java语言的创造者在设计时考虑这两个函数的使用场景。
在运行一个线程中,我们只需要对Thread这个对象使用sleep函数(用来休眠线程),但是我们可能会用多个对象进行锁管理(即在一个线程中使用多个锁)。
如果把wait设置成Thread方法,那么在一个线程中只能用Thread对象的wait和notify,非常有局限性(相当于一个线程中只能使用一个锁)。

例如下面这样的场景,银行给用户开金卡需要两个条件:存款10000,今年消费次数超过5次。我们在这两个条件未达到的时候,分别使用wait(),等待对应notify。
如果wait是Thread方法的话,就不能实现这样的需求。

1
2
3
4
5
6
7
8
9
10
11
synchronized (notEnoughDeposit) {
while(deposit < 10000) {
notEnoughDeposit.wait();
}
synchronized (notEnoughConsumeCount) {
while(consumeCount < 5) {
notEnoughConsumeCount.wait();
}
}
// 办理金卡
}

sleep只能在Thread中使用,不需要考虑多个对象嵌套的调用。同时结合“最小职责”的设计原则,sleep()就设置成Thread的方法。

为什么wait只能在同步代码中调用?

我们看下wait使用的具体场景,下面代码是没有加入同步块:

1
2
3
4
5
6
7
while(deposit < 10000) {
notEnoughDeposit.wait();
}
while(consumeCount < 5) {
notEnoughConsumeCount.wait();
}
// 办理金卡

这里就会存在一个问题,如果没有在wait()外围加入同步块,在办理金卡的时候deposit可能会变化。用户在中间的时间空隙(条件判断和真正办卡中间)中可能再去消费,导致卡中余额小于10000,不符合金卡办理条件。
在java规范中,如果wait和notify外围没有同步块,会抛出ILLegalMonitorStateException。
所以java程序设计总是需要保证 notify 和 wait 操作的原子性,这也就是为什么wait只能在同步代码中调用的原因。

怎么理解wait会释放出锁;sleep不会释放出锁?

wait调用后,会释放出锁。如果当前其他线程正在阻塞状态的话会被唤醒,唤醒后其他线程就继续操作。
sleep就相当于当前线程休眠一段时间,不会释放出锁,其他阻塞的线程自然也获取不到锁。这里特别要注意的是,sleep并不代表会一直占用系统CPU。因为操作系统底层也有对应的优化机制,检查到当前线程sleep,会转而执行那些非阻塞的线程。

锁的机制?

我们先来看下这张图,再理清其中的概念:

什么是锁?

锁是对象内存堆头部的一部分数据。

什么是监视器(monitor)?

监视器是一种虚拟的概念,一个锁只能被一个线程持有,其他线程阻塞等待。获得这个锁的线程处于监视器中。

什么是等待池(wait set)?

调用了某个对象的wait()方法,线程就会释放该对象的锁后,进入到了该对象的等待池中。

什么是阻塞队列(entry set)?

线程获取锁失败后,进入到阻塞队列。当持有锁的线程释放锁后,阻塞队列中一个线程会获取该锁,然后进入监视器。

明白这些概念后,我们再看一张图,这里面表示锁操作的关键流程

下面是每一步对应的操作(注:下面第x步不是顺序执行)
第1步:线程A尝试获取object锁,获取锁成功,进入Monitor成功
第2步:线程A持有锁,线程B尝试获取object锁,获取锁失败,进入Monitor失败
第3步:线程A持有锁,完成操作释放object锁,线程B离开阻塞队列,尝试获取object锁
第4步:线程A持有锁,在运行过程中调用wait,释放object锁,同时进入等待池
第5步:线程B持有锁,在运行过程中调动notify或者notifyAll,会触发第6步操作,等待线程其他操作完毕,才释放object锁
第6步:线程A之前调用wait,处于等待池中,在接受notify或者notifyAll后,会进入阻塞队列,在之后进行第3步操作

以上就是常见的锁操作,包括获取锁、释放锁、wait、notify。

notify和notifyAll的差异?

从字面上理解,notify就是随机唤醒一个wait的线程,notifyAll唤醒所有wait的线程。

那么继续问下去,两者是否可以调换使用?

我们先来看下面的代码:

1
2
3
4
5
6
7
if(!condition) {
obj.wait();
}

while (!condition) {
obj.wait();
}

这里有两种写法在一种情况下有差别,就是一个线程被错误的唤醒后,if代码块会继续执行下去,但是后续执行都是错误的。而while代码块会再次验证条件是否满足,发现没有满足条件的话,选择再次wait。

这个有个建议:永远在while循环里而不是if语句下使用wait。
这样,循环会在线程睡眠前后都检查wait的条件,并在条件实际上并未改变的情况下处理唤醒通知。

假死的情况

在while的基础上,如果使用notify错误的唤醒了一个wait的线程。它在接下去的while判断中,发现仍旧没有达到条件,这个线程重新选择wait。同时其他线程没有被唤醒,这就会导致所有线程一直假死在那边。
而使用notifyAll则不会出现这种情况,因为所有wait的线程都会被唤醒,总有一个线程能重新通过条件判断(这一点要开发者自己保障),程序会继续运行下去。

用 6 个栈实现一个 O(1) 队列

发表于 2018-02-06 | 分类于 Algorithm

原文链接 转载已授权

《算法(第四版)》中的题目是这样的:
用有限个栈实现一个队列,
保证每个队列操作(在最坏情况下)都只需要常数次的栈操作。

那么这里就使用六个栈来解决这个问题。

这个算法来自于这篇论文
原文里用的是 Pure Lisp,不过语法很简单,还是很容易看懂的。

先导知识——用两个栈模拟一个队列

如何使用两个栈来模拟一个队列操作?
这是一道很经典的题目,答案也有很多种,这里只介绍之后会用到的一种方法。
首先我们有两个栈,H 和 T,分别用作出队和入队用。

这样,入队操作等同于向 T 添加元素,T 的入栈操作只需要 O(1) 时间。

如果 H 不为空,出队操作等同于 H 弹栈,H 的弹栈操作也只需要 O(1) 时间。

但如果 H 为空,则需要将 T 中的元素依次弹出并压入到 H 中,这是一个 O(n) 的操作。

显然,这种方式中,出队操作的最坏时间复杂度是 O(n),并不满足题目要求。

分摊 O(n)

那么,怎么解决这个问题呢?

一个很自然的想法是,如果在栈 H 变为空之前,我们就能逐步将栈 T 的内容弹出并压入到另一个栈 H’ 中,等到栈 H 为空时,直接交换 H 和 H’ 即可。
假设目前的队列状态是这样,有三个元素等待出队,还有三个元素等待入队。

现在依次让三个元素出队,与此同时我们让栈 T 中的元素依次进入 H’ 中。
每一次出队都执行两个操作,元素出队和元素复制(Pop & Push),时间复杂度 O(1) + O(1) + O(1) = O(1)。

第一次操作(出队)

第二次操作(出队)

第三次操作(出队)

现在栈 H 和栈 T 都为空,下一次出队操作时,我们直接交换栈 H 和栈 H’(由于是交换引用,因此时间复杂度仍为 O(1))。

之后再进行出队操作。

这就是这个算法基本想法,在栈 H 变为空之前,分步将栈 T 中的内容分步复制到另一个栈中。
当栈 H 为空时直接用准备好的栈 H’ 替代 H,保证时间复杂度为常数。

对复制时 Enqueue 的支持和 T’ 的引入

刚才是一种理想情况,显然我们的队列在复制时不可能只发生出队操作,为了增加对入队操作的支持,我们引入临时栈 T’。

例如我们有队列状态如下,现在启动复制进程,入队操作全部由 T’ 完成。

我们进行一次入队操作和两次出队操作,如下组图所示:

第一次操作(入队)

第二次操作(出队)

第三次操作(出队)

现在 H 和 T 均为空,下一次操作时(不论入队还是出队),我们先交换 H 和 H’ 以及 T 和 T’,同时让入队操作控制权回到 T。

这样,我们增加了对复制时入队操作的支持,但还并不完全,只有在理想情况下才可以做到。

h 与 HR ,对复制时出入队序列支持的扩展

在之前的例子中,当复制结束时 H 总是为空的,现在我们来讨论一下复制结束时 H 不为空的情况。
如果复制结束时 H 不为空,直接交换的结果是我们丢失了原来栈 H 中的数据。
因此,在翻转 T 的同时,我们还应翻转 H 到 HR,并在最后将 HR 的内容再度翻转并添加到 H’ 上。

这个过程可以以下图方式进行:

初始状态:

第一次操作(入队),H->HR ,T->H’,时间复杂度 O(1) + O(1) + O(1) + O(1) + O(1) = O(1)。

第二次操作(入队)

第三次操作(入队)

第四次操作(入队)

第五次操作(入队)

第六次操作(出/入队执行前)

这样我们就解决了 H 复制结束后不为空的问题,代价是引入了两个额外的问题:

操作次数增加到了 2k 次,k 代表栈 T 中的元素数量。(如果当 T 中元素数量大于 H 中元素数量时开始复制)
由于 H 被用于复制进程,我们无法在复制过程中支持出队操作。第一个问题解决方案比较简单,我们可以在每一次出/入队操作执行时进行两次的复制步骤(对 T 和 H 进行两次的 Pop 操作),时间复杂度仍为 O(1)。

第二个问题我们通过引入栈 h 来解决。
h 用于在复制时代替 H 执行出队功能,它会在复制开始时自动变为栈 H 的一个浅拷贝(也就是说,h 和 H 共用同一片内存空间,但它们用于指示栈顶位置的指针相互独立)。

现在我们有了全部 6 个栈,它们的功能如下图所示(为了方便介绍我将一些栈的位置做了调换)。

由于我们并不能预知接下来会发生的操作,因此当 H 栈中的元素数量第一次小于 T 栈中的元素数量时,我们就必须启动复制进程了(总是假设接下来全部都是出队操作)。我们引入一个布尔类型变量 IsCopying 来指示复制进程。

现在我们进行第一次入队操作,IsCopying = true,开始复制。
首先 h 变为 H 的浅拷贝,这个过程是 O(1) 的。

如果在复制过程中有出队操作,作为 H 的翻转 HR 中就有一个元素不再需要复制,我们引入一个变量 needcopy 来记录 HR 中需要复制的元素数量。

接下来是两次复制操作,T 和 H 分别有两个元素进入了 H’ 和 HR 。

然后是第二次出/入队操作,这次我们选择出队,1 出队后显然 HR 中的 1 不再需要复制,needcopy – 1。

随后再是两次复制操作,第一次将 H 中的 3 移到 HR 中,needcopy + 1,T 中的 5 移到 H’ 中;第二次只将 T 中的 4 移到 H’ 中。

第三次出/入队操作我们选择入队,8 入队。随后 HR 中的两个元素进入了 H’,needcopy – 2。

由于 needcopy 变成了 0,我们再额外进行一次交换操作,并将 IsCopying 置为 false。

至此,完整的算法运行完毕。

有关复制开始时机的证明

这里我们选择了在第 k + 1 个元素入队时开始复制,现在证明一定能够在 h 空之前完成复制:

假设复制开始时 H 有 k 个元素,T 有 k + 1个元素。
完成第一轮复制(H->HR , T->H’)需要 k + 1 次操作,
完成第二轮复制(H->H’)需要 k 次操作,总共需要 2k + 1 次操作才能完成复制。
而 h 的长度为 k,能够提供 2k 次的操作机会。第 k + 1 个元素入队时也能提供 2 次操作机会,因此一共是 2k + 2 次操作机会。

由于 2k + 1 < 2k + 2,我们证明了该算法能够及时完成复制工作。

程序设计

根据之前的内容,我们可以开始设计程序了。主要实现三个功能,Enqueue(), Dequeue() 和 Peek()。

根据算法要求我们添加一个进行复制时操作的函数 OneStep(),用于执行元素的复制,栈交换等操作。

Peek() 只需要根据是否在进行复制选择栈 h 或栈 H 进行 Peek()。

Enqueue()

如果不处于复制状态
如果 H.Length – T.Length > 0,直接将元素压入栈 T。
否则令 IsCopying = true,h 进行浅拷贝,进行两次的 OneStep。
如果处于复制状态,将元素压入 T’,进行两次的 OneStep。

Dequeue()

如果不处于复制状态
如果 H.Length – T.Length > 0,直接从 H 弹出元素。
否则从 H 弹出元素,IsCopying = true,h 进行浅拷贝,进行两次的 OneStep。
如果处于复制状态,从 h 弹出元素,needcopy - 1,进行两次的 OneStep。

OneStep()

如果不处于复制状态,什么也不做。
如果处于复制状态。
如果 H 和 T 都不为空,从 H 搬运一个元素至 HR ,从 T 搬运一个元素至 H’ ,needcopy + 1。
如果 H 为空但 T 不为空,从 T 搬运一个元素至 H’ 。
如果 H 和 T 都为空,但 needcopy > 1,从 HR 搬运一个元素至 H’ ,needcopy – 1。
如果 H 和 T 都为空,但 needcopy = 1,从 HR 搬运一个元素至 H’ ,needcopy – 1,交换 H 和 H’ 以及 T 和 T’,其他栈置空,退出复制状态。
如果 H 和 T 都为空,但 needcopy = 0,交换 H 和 H’ 以及 T 和 T’,其他栈置空,退出复制状态。

程序实现(C#)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
using Generics;

namespace _1._3._49
{
class StackQueue<Item>
{
Stack<Item> H;
Stack<Item> T;
Stack<Item> h;
Stack<Item> HH;
Stack<Item> TT;
Stack<Item> Hr;

bool isRecopying;
int nowcopying;

public StackQueue()
{
this.isRecopying = false;
this.nowcopying = 0;

this.H = new Stack<Item>();
this.T = new Stack<Item>();
this.h = new Stack<Item>();
this.HH = new Stack<Item>();
this.TT = new Stack<Item>();
this.Hr = new Stack<Item>();
}

public Item Peek()
{
if (this.isRecopying)
{
return h.Peek();
}
else
{
return H.Peek();
}
}

public void Enqueue(Item item)
{
if (!this.isRecopying && Lendiff() > 0)
{
this.nowcopying = 0;
this.T.Push(item);
}
else if (!this.isRecopying && Lendiff() == 0)
{
this.T.Push(item);
this.isRecopying = true;
this.h = this.H.Copy();
OneStep(OneStep(this));
}
else if (this.isRecopying)
{
this.TT.Push(item);
OneStep(OneStep(this));
}
}

public int Lendiff()
{
return this.H.Size() - this.T.Size();
}

public Item Dequeue()
{
if (!this.isRecopying && Lendiff() > 0)
{
return this.H.Pop();
}
else if (!this.isRecopying && Lendiff() == 0)
{
Item temp = this.H.Pop();
this.h = this.H.Copy();
this.isRecopying = true;
OneStep(OneStep(this));
return temp;
}
else
{
Item temp = this.h.Pop();
this.nowcopying--;
OneStep(OneStep(this));
return temp;
}
}

private static StackQueue<Item> OneStep(StackQueue<Item> q)
{
if (q.isRecopying && !q.H.IsEmpty() && !q.T.IsEmpty())
{
q.nowcopying++;
q.HH.Push(q.T.Pop());
q.Hr.Push(q.H.Pop());
}
else if (q.isRecopying && q.H.IsEmpty() && !q.T.IsEmpty())
{
q.isRecopying = true;
q.HH.Push(q.T.Pop());
}
else if (q.isRecopying && q.H.IsEmpty() && q.T.IsEmpty() && q.nowcopying > 1)
{
q.isRecopying = true;
q.nowcopying--;
q.HH.Push(q.Hr.Pop());
}
else if (q.isRecopying && q.H.IsEmpty() && q.T.IsEmpty() && q.nowcopying == 1)
{
q.isRecopying = false;
q.nowcopying--;
q.HH.Push(q.Hr.Pop());
q.H = q.HH;
q.T = q.TT;
q.HH = new Stack<Item>();
q.TT = new Stack<Item>();
q.Hr = new Stack<Item>();
q.h = new Stack<Item>();
}
else if (q.isRecopying && q.H.IsEmpty() && q.T.IsEmpty() && q.nowcopying == 0)
{
q.isRecopying = false;
q.H = q.HH;
q.T = q.TT;
q.HH = new Stack<Item>();
q.TT = new Stack<Item>();
q.Hr = new Stack<Item>();
q.h = new Stack<Item>();
}
return q;
}
}
}

像奥利奥一样的双重安全措施,尽在 Android Oreo

发表于 2018-01-10 | 分类于 译文
  • 原文地址:Double Stuffed Security in Android Oreo
  • 原文作者:Gian G Spicuzza
  • 译文出自:掘金翻译计划
  • 本文永久链接:https://github.com/xitu/gold-miner/blob/master/TODO/double-stuffed-security-in-android-oreo.md
  • 译者:一只胖蜗牛
  • 校对者:corresponding,SumiMakito

像奥利奥一样的双重安全措施,尽在 Android Oreo

由 Android 安全团队的 Gian G Spicuzza 发表

Android Oreo 中包含很多安全性提升的更新。几个月以来,我们讨论了如何增强 Android 平台及应用的安全性: 从提供更安全的获取应用渠道,移除不安全的网络协议,提供更多用户控制符,加固内核,使 Android 更易于更新,直到加倍 Android 安全奖励奖励项目的支出。如今 Oreo 终于正式和大家见面了,让我们回顾下这其中的改进。

扩大硬件安全支持

Android 早已支持开机验证模式(Verified Boot),旨在防止设备软件被篡改的情况下启动。在 Android Oreo 中,我们随着 Project Treble 一同运行的验证开机模式(Verified Boot),称之为 Android 验证开机模式2.0(Android Verified Boot 2.0)(AVB)。AVB 有一些使得更新更加容易、安全的功能,例如通用的分区尾部(AVB 中位于文件系统分区尾部的结构)以及回滚保护。回滚保护旨在保护 OS 降级的设备,防止降级到到低版本的系统后被人攻击。为此,设备将通过专用的硬件保存系统版本信息或使用可信执行环境(Trusted Execution Environment, TEE)对数据进行签名。 Pixel 2 和 Pixel 2 XL 自带这种保护,并且我们建议所有设备制造商将这个功能添加到他们的新设备中。

Oreo 还包括新的原始设备制造商锁(OEM Lock)硬件抽象层(HAL)使得设备制造商能够更加灵活的保护设备,无论设备处于锁定、解锁或者可解锁状态。例如,新的 Pixel 设备通过硬件抽象层命令向启动引导程序(bootloader)传递命令。启动引导装载程序会在下次开机分析这些命令并检查安全存储于有重放保护的内存区(Replay Protected Memory Block, RPMB)中对锁更改的信息是否合法。如果你的设备被偷了,这些保护措施旨在保护你的设备被重置,从而保护你的数据安全。新的硬件抽象层(HAL)甚至支持将锁移动到专用的硬件中。

谈到硬件,我们添加了防伪硬件支持,例如在每一个 Piexl 2 和 Piexl 2 XL 设备中内嵌的安全模块。这种物理芯片可以防止很多软硬件攻击,并且还抵抗物理渗透攻击. 安全模块防止推导设备密码及限制解锁尝试的频率,使得很多攻击由于时间限制而失效。

新的 Pixel 设备配有特殊的安全模块,所有搭载Android Oreo 的谷歌移动服务(GMS)的设备也需要实现密钥验证。这提供了一种强验证标识符机制,例如硬件标识符。

我们也为企业管理设备添加了新的功能。当配置文件或者公司管理员远程锁定配置文件时,加密密钥会从内存(RAM)中移除.这有助于保护企业数据的安全。

平台加固及进程隔离

作为 Project Treble 的一部分,为了使设备厂商可以更简单、低成本地更新,我们对 Android 的框架也进行了重构。将平台和供应商代码分离的目的也是为了提高安全性,根据最小特权原则,这些硬件抽象层(HALs)运行在自己的沙盒中,只对有权限的驱动设备开放。

追随着Android Nougat 中媒体堆栈加固,我们在Android Oreeo 媒体框架中移除了许多直接访问硬件的模块,从而创造了更好的隔离环境。此外,此外我们启用了所有媒体组件中的控制流完整性(Control Flow Integrity, CFI)保护。这种缺陷可以通过破坏应用的正常控制流,从而利用这种特权执行恶意的活动。 CFI 拥有健全的安全验证机制,不允许随意更改原来编译后二进制文件的控制流程图,也使得这样的攻击难以执行。

除了这些架构改变和CFI以外,Android Oreo 还带来了其他平台安全性相关的提升:

  • Seccomp(Secure computing mode, 安全计算模式)过滤: 一些系统层的调用不再对应用开放,从而减少潜在损害应用途径。
  • 加固用户拷贝: 一个最新的 Android 安全漏洞掉渣显示:在内核漏洞中,失效的或者无边界检查情况约占 45%。在 Android 内核 3.18 及以上版本中,我们新增了一个边界检查的补丁,使得利用这个漏洞变得更困难,同时还同帮助开发者在他们代码中查找问题并修复问题。
  • Privileged Access Never(PAN)仿真: 同时针对 3.18 以上的内核新增了补丁,这个功能禁止内核直接访问用户空间,同时确保开发者利用加固后的方式开访问用户空间。
  • 内核地址空间布局随机化(KASLR):虽然Android已经支持地址空间布局随机化(ASLR)好多年了,我们仍针对 Android 内核 4.4 及以上版本提供了内核地址空间布局随机化(KASLR)补丁减少风险。内核地址空间布局随机化(KASLR)将在每次设备启动加载内核代码时随机分配地址,使得代码复用攻击,尤其是远程攻击更加难以执行。

应用程序安全性及设备标示变更

Android 即时运行应用运行在一个受限制的沙盒中,因此限制了部分权限和功能,例如访问设备内应用列表或者着明文传递数据。虽然是从 Android Oreo 才发布,但是即时运行应用支持在 Android Lollipop 及以上版本的设备上运行。

为了更安全的处理不可信内容,我们通过将渲染引擎放到另一个进程中并将它运行在一个独立的资源受限的沙盒中来隔离 WebView。此外,WebView 还支持安全浏览,从而保护使用者浏览含有潜在危险的网站。

最后,我们针对设备标识做了重大的改变开放给用户更多的控制权,包括:

  • 静态的 Android ID 和 Widevine 将变为基于应用变化的值,这有助于限制设备中无法重置的标识符的使用。
  • 依照 IETF RFC 7844,现在 net.hostname 将为空且 DHCP 客户端也将不再发送主机名称(hostname)。
  • 对于需要设备标识符的应用,我们新增了一个 Build.getSerial() API 并且通过权限对其进行保护。
  • 我们与安全研究人员一起 1 在各种芯片组固件中的 Wi-Fi 扫描环节中新增一个健全的MAC地址随机化功能.

Android Oreo 带来远不止这些改进,还有更多。一如既往,如果您有关于 Android 的反馈或是改进建议。欢迎发送邮件至 security@android.com。


开发者须知-女性玩家和手机游戏

发表于 2018-01-02 | 分类于 译文
  • 原文地址:Women and mobile games: learnings for developers
  • 原文作者:Tobias Knoke
  • 译文出自:掘金翻译计划
  • 本文永久链接:https://github.com/xitu/gold-miner/blob/master/TODO/women-and-mobile-games-learnings-for-developers.md
  • 译者:corresponding
  • 校对者:hanliuxin5,tanglie1993

开发者须知:女性玩家和手机游戏

Women and mobile games: learnings for developers

让手机游戏变得更加多元化,更具包容性,更具吸引力的市场机遇

The market opportunity in making mobile gaming more diverse, more inclusive, and more engaging

目前世界上有二十多亿部活跃的安卓设备,这意味着比起过去更多的人在玩手机游戏。手机游戏玩家的增长导致了这些游戏玩家的特点,需求和动机的多样性在不断扩大。我们之前文章 谁在玩手机游戏 讨论过,现在需要以满足在玩家玩游戏时的需求来对待玩家,而不是根据一些刻板印象和像人口统计那样的死板数据。与此同时,现在在游戏界有很多关于性别和包容的讨论,而关于女性手机游戏玩家的研究和讨论却很少。
There are now over two billion active Android devices which means more people are playing mobile games than ever before. The growth of the mobile games audience had led to an expansion of diversity in characteristics, needs, and motivations of those playing games. In our previous post Who plays mobile games we discussed the opportunity to think of players in terms of the needs met by playing games, rather than in terms of stereotypes and demographics. At the same time, there is a lot of conversation in the gaming community about gender and inclusivity, but relatively little research or discussion about the experiences of women who play mobile games.

我们想更多的了解这方面,所以我们和游戏情报商 NewZoo 合作,进行定量的研究,希望以此了解美国女性玩家的体验和看法。我们和数十位游戏作者,测评人员,玩家和学者一起合作,把我们的研究场景化。通过 交互性的体验 和 在总结中收获更多 ,我们深入研究。请继续读下去,了解开发者如何让游戏更具包容性,并吸引近在咫尺的玩家。
We wanted to understand more about this so we partnered with gaming intelligence provider Newzoo to produce a quantitative research study to understand the experiences and perceptions of women who play games in the United States. We worked with dozens of game makers, critics, players, and academics to contextualize our research. Dive deeper into the insights through this interactive experience or discover more learnings in a summary of our findings. Read on to find out how you as a developer can make your game more inclusive and appealing to all players out there.

了解你的用户

Know your audience

无论从人数上和偏好上来说,女性手机游戏玩家有巨大市场潜力。在我们的调查中,美国有大量女性手机游戏玩家(其中 65% 都处于 10 - 65 岁年龄段)。在过去的一年里,这比去电影院看过电影的比例(62%)或读过一本书的比例(44%)更加高。这里可以清晰的看出,比起其他娱乐活动,女性更愿意玩手机游戏。报告还表明,女性就和男性一样喜欢玩手机游戏 — 有一半的玩家是女性!相比其他平台,女性不仅更喜欢在手机上游戏,而且女性玩的频率比男性更高。
There is significant market potential in women who play mobile games, both in terms of volume and preference for the platform. In our research we found a significant number of women in the US play mobile games today (65% of those aged between 10–65 years). This is a higher percentage than those who have watched a movie at a movie theater (62%), or read a book (44%), in the last year. It’s clear that women engage significantly more in mobile gaming than in other forms of entertainment, and that’s not it… Research has shown that they are just as likely to play mobile games as men — women represent half of all mobile game players! They are not only more likely to prefer mobile compared to other platforms, women also tend to play more frequently than men.

作为游戏开发者,你意识到女性游戏的机会了吗?这可能是个通过了解这些用户而进入这个未开发的市场的机会。第一步,你可能要衡量和评估女性玩家的占比。在你的用户群体中,女性是否被很好的代表了?她们和男性是否有不同的游戏体验?
As a games developer, do you consider the opportunity presented women for your games? There may be an opportunity for you to grow your business in untapped markets by better understanding your players. As a starting point you might want to measure and evaluate the percentage of players who are women. Are women well represented in your player base? Is there a difference in their user experience compared to your male players?

对开发新游戏时的建议:当你在设计游戏或者思考未来的发展方向时,多去想想那些目标用户,而不用去讨好那些你所认为的”典型”用户。不同用户的游戏体验可能会不同吗?通过彻底分析和研究用户,你可以从那些尚未被顾及的用户(比如那些女性游戏玩家)中寻找商机。
The same goes for new developments: when designing your game, or thinking of future development, it can be a useful exercise to think of the range of people who may play your game, rather than gravitating to the ‘typical’ player. Could there be a difference in the user experience of some players? By thoroughly analysing and researching user audiences you can potentially make a strong business case to capture an underserved audience — such as women who play games.

制作更具包容性的游戏

Build more inclusive games

如果你观察 Google 应用市场 中受欢迎的游戏,部分图像和图标的性质暗示着女性玩家在游戏世界中是一个相对较小的群体。在Google应用市场收入前 100 的游戏中,以男性角色作为图标的游戏数量比以女性角色作为图标的游戏数量多 44%。所以在我们的调查中,尽管女性玩家玩的更多,但是她们还是认为自己不属于现在的游戏社区。在推广游戏时,更换更合适的图标和形象,会让你从竞争中脱颖而出,也会减少你错过潜在玩家的可能。请尝试以下几点:
If you look at popular games on Google Play, the nature of much of the imagery and icons would imply women are a relatively niche group in the world of gaming: among the top 100 revenue generating games on Google Play, characters who are men are featured in their app icons 44% more often than characters who are women. Consequently our research found women often do not feel like they belong to this community although they are playing games very actively. Using alternative, or less alienating, iconography, characters, and imagery when promoting your game could help differentiate it clearly from your competition, and ensure you don’t miss out on reaching potential players. Try the following quick tips:

  • 在做 商店列表 时,测试更有包容性的图像。
    Test more inclusive imagery when running store listing experiments.
  • 多关注应用的图标,截图和视频,并考虑测试不同图像对转换率的影响。
    Pay attention to your icon, screenshots, and videos, and consider testing the impact of different imagery on conversion rates.
  • 考虑下使用女性角色来体验游戏,或者在运行电话回访时尝试新的可能性。
    Think of launching with characters who are women, or testing new ones when running LiveOps.
  • 追踪用户对游戏角色的共鸣,同时倾听用户群体的反馈也很重要。
    Track how people are resonating with the characters, and, invaluably, listen to the feedback of your community.

发展一个多样化的开发团队

Grow a diverse team

在一大群人中提取共同需求很难。我们都想开发自己想玩的游戏。为了减少偏见,在游戏生命周期的几个阶段,都需要获取潜在用户的反馈。
It is very difficult to have the empathy and perspective needed to build a product that meets the needs of a wide range of potential people. It’s human nature to build games you want to play. To reduce potential bias, request feedback from a broad representation of your potential players at several stages throughout your game’s lifecycle.

你的开发团队的形象也影响能否取到悦更多的用户。尽管有如此多的女性玩家,游戏行业仍然只关注男性用户: IDGA的调查发现,女性、跨性别者和其他只占 全球 27.8% 的游戏产业 。这种不平衡的现象呼应我们的研究结果,只有 23% 的女性和 40% 的男性认为在游戏行业中人人享有平等的待遇和机会。
The profile of your development team also impacts your ability to build games that appeal to a wide spectrum of players. Despite the high proportion of women playing mobile games, men are overrepresented in the gaming industry: according to the IDGA, only 27.8% of the gaming industry globally are women, transgender, or other people. This imbalanced representation is felt by players who responded to our research with only 23% of women and 40% of men believing there is equal treatment and opportunity for all in the games industry.

来自团队成员多样化的观点将帮助您开发真正创新且有意思的游戏,并且吸引更多的潜在玩家。现在就看下自己的团队和游戏的用户构成的差别。你的团队成员能代表你的受众吗?您的团队是否已经整装待发,来帮助您最大化的捕获潜在受众,并且让您的游戏吸引所有人?
Diversity of perspectives from your team members will help you build truly innovative and exciting games that will appeal to a broad spectrum of potential players. Look at your team and compare it with the user composition of your game. Is your team truly representative of your audience? Is it well equipped to help you capture the maximum potential audience possible by making your game appealing to everyone?

把握这个机遇

Take advantage of this opportunity

尽管未来女性玩家数量巨大,但研究结果却让人惊讶,他们比男性更难以真正接受自己的游戏爱好。大部分女性玩家不属于游戏世界。一般女性玩家不太喜欢和朋友交谈游戏内容,为游戏付费,以及享受付费所带来的快乐。
While there is great potential in the sheer volume of women playing mobile games, it is striking from the research how less likely they are than men to truly embrace their play habits. With a few notable exceptions, there is a sense that women don’t belong in the world of gaming. They are less likely to talk about games with their friends, pay for content, or feel good when they do pay.

我们相信,这是一个游戏产业真正与女性玩家互动的绝佳机会。随着用户获取成本的上升,需要想想如何能开发出与所有玩家产生共鸣并且能病毒式传播的游戏。只有让女性玩家参与到游戏中,你才能解决这个问题。
We believe this represents a great opportunity for the industry to truly engage with women who play games. As user acquisition costs rise, think of the potential virality of building a game that resonates with and excites all players. This can only be achieved by recognizing and addressing the barriers for women to engage with your game.

着眼未来

The road ahead

我们相信,游戏市场还有很大的空间,能让我们使手机游戏更加多元化,更具包容性,更吸引所有玩家。为了把握这个机会,您的第一步是:
We believe there is a great opportunity in market growth and making mobile gaming more diverse, more inclusive, and more engaging for all players. The first steps for you in order to take advantage of this opportunity are:

  • 了解你的用户:当前用户和潜在用户
    Know your audience: current and potential
  • 研究你的游戏是怎样把一些潜在用户排除在外的
    Consider how your games may exclude some potential players
  • 评估你团队观点的多样性,这将如何影响你开发的游戏
    Assess the range of perspectives in your team, and how this affects the games you build
  • 头脑风暴,你可能会想出一款所有人都喜欢的游戏
    Brainstorm how you may produce the next game that all players could embrace

手机游戏生为大众。为了褒奖和激励女性玩家和女性开发者,我们启动了 改变游戏 的计划。这是 Google 应用商店的一项旨在促进游戏多样性的计划,同时这项计划也褒奖所有女性玩家,并通过正在进行的研究和合作为下一代游戏开发者提供支持。
Mobile games are for everyone. To celebrate and empower women who play games and creators, we’re launching CHANGE THE GAME; a new Google Play initiative to promote diversity in games, celebrate all women who play games, and empower the next generation of game-makers through ongoing research, development programs, and partnerships.

作为一个应用开发者,你能影响未来游戏的走向。我希望你能参与到我们活动中,和我们一起让游戏世界变得更加包容性。如果我们一起努力,手机游戏的世界会变得更加有趣。
As a mobile developer, you have a major influence on how future games will look like. We hope you can join our efforts of making the gaming world a more inclusive community; if we all contribute to this, mobile games will bring us even more joy than they do today.


你是怎么想的呢?

What do you think?

你有没有想过开发人员怎样去设计更有包容性的游戏呢?在文章下面留言或者 twitter 中添加#AskPlayDev标签后发言,我们会通过 @GooglePlayDev (那里我们会展示在 Google 应用商店获得成功的窍门)回复。
Do you have thoughts on how developers can build more inclusive games? Join the discussion in the comments below or tweet using the hashtag #AskPlayDev and we’ll reply from @GooglePlayDev, where we regularly share news and tips on how to be successful on Google Play.


Okio源码解析

发表于 2017-12-20 | 分类于 Android

大家一定听说或者使用过鼎鼎大名的OKHttp和Retrofit,它们内部都调用了Okio。
它们三个都是Square团队开源的库,主要处理I/O操作和网络请求。
今天我们就来读下Okio的源码,看看Okio有什么神奇之处。

Okio是什么?

Okio是一个完善java.io和java.nio的库,可以更方便的读、写、处理数据。

看到上面的官方介绍,我们可以发现两个重点:
1.完善java.io和java.nio;
2.Okio的主要功能是,读、写、处理数据。

再深入思考下,java.io和java.nio有哪些尚未完善的地方?Okio有做了哪些优化?

java.io能处理所有的IO信息,但是还是有些不完美之处:
1.需要自己去管理byte数组;
2.java.io类和继承关系过于复杂,使用起来更加不便;
3.java.io操作可能会某些原因读取速度特别慢,甚至一直等待无法返回;
4.操作字符流和字节流方法不同,需要区别对待;
5.涉及到多个流之间的数据传递,需要反复拷贝,效率不高。

被Android官方青睐的IO库,Okio一一解决了这些问题:
1.使用ByteString去封装byte数组;
2.简化类关系,主要使用Buffer、Sink、Source等类,相互关系简单;
3.使用Timeout去控制超时;
4.可用相同方法去操作字符流和字节流;
5.提高多个流之间的数据传递速度。

带着这些问题,我们继续前进。

ByteString

记得我最开始编程时,C语言中没有字符串类型,只能使用char*的方式存储字符串,而且经常涉及数组和指针的转换,
需要使用memcpy和memset等等函数,容易出错,而且还需要加入大量的检测。
后面使用面向对象语言后,发现用String对象直接管理字符串,良好的封装char数组的常用方法,使用起来各种清爽。

同样使用过java.io的开发者,肯定会想起被byte数组笼罩的恐惧。
需要不厌其烦的处理一串串byte数组,完成encode和decode函数,还要特别关注编码问题。
这个时候就希望,能有一个对象来管理byte数组,并且帮我们封装好各种函数,使用时直接调用下即可。

Okio就满足开发者这个愿望,提供了ByteString类,把对字节数组的常用方法都封装好了。
使用Okio库后,开发者可以以ByteString作为最小粒度进行操作。

先来看下ByteString的组成

1
2
3
4
5
6
7
8
9
// 0.实现了Serializable和Comparable接口
public class ByteString implements Serializable, Comparable<ByteString> {
// 1.byte数组,所以为ByteString
final byte[] data;
// 2.hashCode,在需要时才计算出。不会被序列化
transient int hashCode;
// 3.data utf8化后生成的String,在需要时才计算出。不会被序列化
transient String utf8;
}

ByteString的内部也不复杂,主要就是byte数组。
这里要看下String的结构,其实String可以命名为CharString。
因为一般开发中,字符串用的比较多,所以java官方直接命名为String。

1
2
3
4
5
6
7
// 0.同样实现了Serializable和Comparable接口,额外实现了CharSequence处理常规char数组数据
public final class String implements Serializable, Comparable<String>, CharSequence {
// 1.char数组,所以String等于CharString
private final char value[];
// 2.hashCode
private int hash;
}

接下去看下,ByteString的读和写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static ByteString read(InputStream in, int byteCount) throws IOException {
// 1.检查合法性
if (in == null) throw new IllegalArgumentException("in == null");
if (byteCount < 0) throw new IllegalArgumentException("byteCount < 0: " + byteCount);
// 2.分配空间
byte[] result = new byte[byteCount];
// 3.循环读取inputStream中的数据
for (int offset = 0, read; offset < byteCount; offset += read) {
// 3.1.每次尽可能多的读取inputStream数据,放入result中
read = in.read(result, offset, byteCount - offset);
// 3.2.读取inputStream异常
if (read == -1) throw new EOFException();
}
// 4.生成ByteString
return new ByteString(result);
}

1
2
3
4
5
6
public void write(OutputStream out) throws IOException {
// 1.检查合法性
if (out == null) throw new IllegalArgumentException("out == null");
// 2.直接写入byte数组
out.write(data);
}

Buffer

IO操作的最重要部分就是对流的处理,所以定义好一个流非常关键。
Okio中,就是用Buffer去表示流。

先看下翻译
source:来源;水源;
sink:水槽;洗涤槽;
一下子就明白了Source表示输入源,Sink表示输出源。
对应java.io中的inputStream和outputStream。

1
2
3
4
public final class Buffer implements BufferedSource, BufferedSink, Cloneable {
Segment head;
long size;
}

size表示Buffer中的字节数量。
主要成员变量也非常简单,就是segment。
源码上注释非常简洁清晰:A segment of a buffer,翻译过来就是Buffer的片段。

1
2
3
4
5
6
7
8
9
10
final class Segment {
Segment prev; // 指向双向链表上一节点
Segment next; // 指向双向链表下一节点
final byte[] data; // data表示本segment存储的数据
int pos; // pos表示data中下一个读取字节的index
int limit; // limit表示data中下一个写入字节的index。为什么用limit命名呢,因为这个index也是读取字节的上限
boolean shared; // 是否共享。Okio为了提高效率,在某些时候不拷贝整个segment,而是采用弱引用方式指向segment
boolean owner; // 因为加入共享功能后,就需要确定持有者,只有持有者才能往这个segment中写数据
...
}

从prev和next就可以发现这是双向链表。在Buffer中就持有head,通过head去访问整个链表。
通过后续的代码阅读,发现这是一个双向循环链表。

我们分析下Okio中是如何写入和读取byte数据的。

Buffer.writeByte

先来看看Buffer怎么样写入一个byte

1
2
3
4
5
6
7
8
9
10
// 0.注意入参是int格式,不过其中有效数据的只有8 bit
@Override public Buffer writeByte(int b) {
// 1.寻找可供写入的segment
Segment tail = writableSegment(1);
// 2.在segment中写入字节byte。limit的含义在上文提及,表示下一个写入字节的index
tail.data[tail.limit++] = (byte) b;
// 3.buffer中size变化
size += 1;
return this;
}

writeByte函数的代码都很简单,我们继续看看如何寻找可供写入的segment。

Buffer.writableSegment

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 0.入参minimumCapacity表示允许写的最小空间
Segment writableSegment(int minimumCapacity) {
// 1.检查合法性
if (minimumCapacity < 1 || minimumCapacity > Segment.SIZE) throw new IllegalArgumentException();
// 2.当前head为空时,先新建一个
if (head == null) {
// 2.1.从SegmentPool中取出一个segment
head = SegmentPool.take();
// 2.2.设置为双向循环链表
return head.next = head.prev = head;
}
// 3.选择链表最尾部的segment
Segment tail = head.prev;
// 4.如果尾部segment中没有足够的可写空间,或者当前Buffer不是尾部segment的持有者,重新从SegmentPool取出segment插入链表
if (tail.limit + minimumCapacity > Segment.SIZE || !tail.owner) {
tail = tail.push(SegmentPool.take());
}
return tail;
}

这里引入了SegmentPool这个类,主要用来管理Segment对象,回收旧segment,分配segment。
SegmentPool减少了segment的新建和释放次数,缓解java GC的压力。

注:类似于Handler中message.obtain(),其背后也有一个pool去管理所有的message对象。

SegmentPool

这个类代码很短,全部贴出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
final class SegmentPool {
// pool 容量上限,最大为64KiB
static final long MAX_SIZE = 64 * 1024;
// 单向链表
static Segment next;
// pool中总字节数
static long byteCount;

private SegmentPool() {
}

static Segment take() {
// take和recycle中next都被synchronize包含,所以是线程安全的
synchronized (SegmentPool.class) {
// 如果当前pool不为空,链表还有数据,从链表头取出segment
if (next != null) {
Segment result = next;
next = result.next;
result.next = null;
byteCount -= Segment.SIZE;
return result;
}
}
// 如果当前pool部为空,链表中没有数据,新建一个segment
return new Segment();
}

static void recycle(Segment segment) {
if (segment.next != null || segment.prev != null) throw new IllegalArgumentException();
// 如果当前segment被共享,则放弃回收
if (segment.shared) return;
// take和recycle中next都被synchronize包含,所以是线程安全的
synchronized (SegmentPool.class) {
// pool达到上限的,放弃回收
if (byteCount + Segment.SIZE > MAX_SIZE) return;
byteCount += Segment.SIZE;
segment.next = next;
next = segment;
// 重新设置segment的pos和limit
segment.pos = segment.limit = 0;
}
}
}

segmentPool这个类非常简单,内部维护一个单向列表。
take()会从头部取出segment,recycler()将待回收的segment放回到链表头部。

Buffer.readByte

我们来看下readByte,其方法和writeByte完全对称。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public byte readByte() {
// 1.检查合法性
if (size == 0) throw new IllegalStateException("size == 0");
// 2.取出segment中数据
Segment segment = head;
int pos = segment.pos;
int limit = segment.limit;
byte[] data = segment.data;
byte b = data[pos++];
size -= 1;
// 3.如果当前segment中数据被读取完毕
if (pos == limit) {
// 3.1.从双向链表中pop出来
head = segment.pop();
// 3.2.回收这个segment,放入到segmentPool中
SegmentPool.recycle(segment);
} else {
// 4.如果当前segment中数据未被读取完毕,只更新pos信息
segment.pos = pos;
}
return b;
}

Source

IO最重要的就是对流的处理,Okio中对应的数据结构是Source和Sink

1
2
3
4
5
6
7
8
9
// 0.Closeable接口中方法为close()
public interface Source extends Closeable {
// 1.读取Buffer中byteCount长度的数据,返回值为本次读取的字节长度
long read(Buffer sink, long byteCount) throws IOException;
// 2.超时控制
Timeout timeout();
// 3.关闭source并且释放资源,允许调用多次
@Override void close() throws IOException;
}

这是一个接口,后续都是使用其实现类作为输入流。

Okio.Source

我们看下Okio.Source,开发者一般都使用这个函数生成Source。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
private static Source source(final InputStream in, final Timeout timeout) {
// 1.检查合法性
if (in == null) throw new IllegalArgumentException("in == null");
if (timeout == null) throw new IllegalArgumentException("timeout == null");
// 2.新建了一个匿名类,实现Source接口
return new Source() {
@Override public long read(Buffer sink, long byteCount) throws IOException {
// 2.1.检查合法性
if (byteCount < 0) throw new IllegalArgumentException("byteCount < 0: " + byteCount);
if (byteCount == 0) return 0;
try {
// 2.2.检查是否超时
timeout.throwIfReached();
// 2.3.寻找可供写入的segment,在之前详细解释过
Segment tail = sink.writableSegment(1);
// 3.3.当前segment剩余可以写入大小,和byteCount两者间选择较小的值,设置为maxToCopy
int maxToCopy = (int) Math.min(byteCount, Segment.SIZE - tail.limit);
// 3.4.从InputStream中尽可能的提取maxToCopy长度,写入到segment中
int bytesRead = in.read(tail.data, tail.limit, maxToCopy);
// 3.5.读取异常
if (bytesRead == -1) return -1;
// 3.6.调整segment和buffer中的参数
tail.limit += bytesRead;
sink.size += bytesRead;
return bytesRead;
} catch (AssertionError e) {
if (isAndroidGetsocknameError(e)) throw new IOException(e);
throw e;
}
}

@Override public void close() throws IOException {
in.close();
}

@Override public Timeout timeout() {
return timeout;
}

@Override public String toString() {
return "source(" + in + ")";
}
};
}

以上代码逻辑非常清晰,流水型执行下去即可。
这里出现了一个新的对象timeout,用来管理超时,我们看看其内部结构。

Timeout

1
2
3
4
5
6
7
8
public class Timeout {
// 1.判断deadlineNanoTime是否被定义。如果缺少该变量的话,deadlineNanoTime或者timeoutNanos为0时,无法判断是未设置还是设置为0
private boolean hasDeadline;
// 2.截止时间,单位为纳秒
private long deadlineNanoTime;
// 3.设定的超时时间间隔,单位为纳秒
private long timeoutNanos;
}

Timeout主要用来设置超时时间,对Stream的读取超过指定时间后,认定为失败,开发者需要选择close或者重新操作这个Stream。

注:读取网络Socket流时,有时会陷入无限等待中,需要使用AsyncTimeout。AsyncTimeout会新开线程监听超时,当前线程无限等待也没有关系。

继续看下上面被调用的throwIfReached()

1
2
3
4
5
6
7
8
9
10
public void throwIfReached() throws IOException {
// 1.判断当前线程是否被中断
if (Thread.interrupted()) {
throw new InterruptedIOException("thread interrupted");
}
// 2.判断当前是否超时
if (hasDeadline && deadlineNanoTime - System.nanoTime() <= 0) {
throw new InterruptedIOException("deadline reached");
}
}

Okio.buffer

1
2
3
4
5
// 0.这里传入上面通过Okio.source生成的Source
public static BufferedSource buffer(Source source) {
// 1.生成BufferSource,真正处理输入流,你看命名中都写着real
return new RealBufferedSource(source);
}

RealBufferedSource

终于找到开发者最后操作的Source类,先来看下它的成员吧。

1
2
3
4
5
6
7
8
9
// 0.实现BufferedSource接口
final class RealBufferedSource implements BufferedSource {
// 1.初始化时自动生成
public final Buffer buffer = new Buffer();
// 2.Okio.Buffer中传入的source对象
public final Source source;
// 3.判断source是否关闭
boolean closed;
}

RealBufferedSource.read

对于输入流来说,我们需要紧紧抓住read方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@Override public int read(byte[] sink, int offset, int byteCount) throws IOException {
// 1.检查合法性
checkOffsetAndCount(sink.length, offset, byteCount);
// 2.当前buffer为空时
if (buffer.size == 0) {
// 2.1.尽可能读取一个segment放入到buffer中
long read = source.read(buffer, Segment.SIZE);
// 2.2.读取异常
if (read == -1) return -1;
}
// 3.选择buffer中数据和byteCount中较小值
int toRead = (int) Math.min(byteCount, buffer.size);
// 4.将buffer中数据输出到byte数组
return buffer.read(sink, offset, toRead);
}

主要流程就是,现将source数据读取到buffer中,再将buffer提取到byte数组中。buffer.read()这个函数这里就不展开讨论了,其原理和buffer.readByte非常相近。

Sink

同理,完全对应的,也可以按照Okio.sink-> Okio.buffer(Sink)-> RealBufferedSink-> RealBufferedSink.write()流程走完一遍Okio中关于写的操作。

总结,Okio这个库本身并不复杂,将常用的流和字节数据进行良好的封装,加之源码中相近的注释,阅读起来非常流畅,想必使用起来的体验也会非常棒。

缩小APK,增加下载量

发表于 2017-12-14 | 分类于 译文
  • 原文地址:Shrinking APKs, growing installs: How your app’s APK size impacts install conversion rates
  • 原文作者:Sam Tolomei
  • 译文出自:掘金翻译计划
  • 本文永久链接:https://github.com/xitu/gold-miner/blob/master/TODO/shrinking-apks-growing-installs.md
  • 译者:tanglie1993
  • 校对者:swants, corresponding

缩小APK,增加下载量

你的APK大小是如何影响下载转化率的

自从 Android Marketplace (Google Play 的前身)在 2012 年 3 月上线以来,app 的平均大小增长了四倍。随着移动 app 的不断成熟,开发者们不断增加新的特性来服务和吸引用户,这使不少人从中受益。然而,随着 app 的特性越来越多——更多 SDK、更高分辨率的图片、更好的图形—— APK 也变得越来越大。在本文中,我讨论了 APK 大小的重要性,并且分析了 Google 在过去 2 年中所做的用户体验研究的结果。

下载的 APK 的平均大小随时间的变化(Google 内部数据)

发现 APK 在变大之后,我们分析了 APK 大小对下载转化率的影响。我们发现,更小的 APK 对应着更高的下载转化率,对于新兴市场中的用户而言尤其如此。在许多开发者把注意力投入到向新市场(特别是新兴市场)扩张中去的情况下,关注 app 的大小就显得很重要。

APK 大小是否会影响下载转化率?

为了研究 APK 大小对用户的选择是否有显著影响,我们分析了用户在浏览了 Play store 中的一个项目之后成功下载这个 app 的百分比。

在 App store 的相应页面中,你可以通过点击“Read More”看到一个 app 的大小。

这看起来还是有些意义的!总的来说,我们发现在小于 100 MB 的情况下,APK 大小和下载转化率之间存在负相关。一个 APK 的大小每增长 6 MB,下载转化率就有 1% 的降低。在市场团队使用 A/B 测试来优化下载转化率的情况下,APK 大小会有重大影响。

这个下降中的一个重要部分不是因为用户选择了不下载,而是下载由于种种原因没有成功。我们发现,一个 10MB 的 app 的下载完成率将比 100MB 的 app 高大约 30%。

这可能是因为:

  1. 用户考虑了需要下载的数据量(以及数据的价格)。
  2. 在他们的移动网络或 wifi 中的 下载所需时间 (人们经常陷入“我现在就要这个 app!”的思维模式)。
  3. 下载过程中的 网络连接性问题。

人们对 APK 大小的偏好和下载转化率是否会因地域而异?

这是一个好问题,答案是肯定的。在新兴市场中,有许多没能使用到稳定 wifi 的用户,他们需要支付流量的费用。

超过 50% 的印度和印尼安卓智能手机用户完全没有 wifi。所以如果一个用户需要下载一个 app,他很可能要为 APK 的每一 MB 付费(Google 内部数据,2017年)。

印度 wifi 普及率调查 (Google 内部安卓用户调查)

与之相似, 出于流量价格和存储空间的考虑,新兴市场中大约 70% 的用户会在下载前考虑 app 的大小。

被调查的印尼用户中会在安装时考虑 app 大小的人所占百分比 (Google 内部安卓用户调查)

安装时会考虑 app 大小的用户这样做的原因 (Google 内部安卓用户调查)

我们可以看到,这些市场偏好非常显著。比如,新兴市场(如中东、非洲和东南亚)用户下载的 APK 的平均大小,是发达市场(如美国和西欧)的四分之一。

APK 大小中位数,根据下载量加权,按市场分类。绿色 = 更大的中位数 APK 大小,红色 = 更小的 中位数 APK 大小(Google 内部数据)。

研究下载转化率数据,就可以发现新兴市场(如印度和巴西)和发达市场(如日本、美国和德国)相比,在面对越来越大的 APK 时会有不同的反应。

APK 每缩小 10MB 对应下载转化率的增加,按市场分类(Google 内部数据)。

从上图中,我们可以看到 APK 缩小 10MB,在印度和巴西造成的影响会比德国、美国和日本更大。从 APK 中移除 10MB 内容,在新兴市场中对应着 下载转化率 2.5% 的增长。

让我们把实际的数字填入下载转化率的增长中:如果你的 app 在印度每个月有 10000 下载量,转化率 20%,缩小 10MB 可以使得下载量每月增加 1140 左右。

最后,当把非游戏的 app 和游戏比较时,我们可以在下载转化率和 APK 大小之间看到类似的关系。但是,对于超过 500MB 的游戏而言,用户们对于 APK 大小的微小变化更不敏感。对于 500-3000MB 的游戏而言,APK 每缩小 200MB,下载转化率只增加 1%。

那么,我是否应该缩小 APK?如果应该,该怎么做?

根据以上数据很容易看出,对于全世界人民来说 APK 大小都是很重要的。

“这很重要,” 你说,“但是我具体可以如何缩小 APK 呢?” 我很高兴你这样问了!缩小 APK 有以下几个入门要点:

  • 缩小 APK安卓开发者网站上的入门教材,它包含了移除不使用的资源和压缩图片文件。

  • Building for Billions 指南, 在安卓开发者网站上,它讨论了缩小 APK,以及其它针对新兴市场的措施。

  • 如何针对新兴市场优化你的应用, 我们团队的另一篇 medium 文章。针对新兴市场,通过三个 app 去分析优化带来的好处。

至于其他的针对新兴市场的考虑,可以去 Google Play 的 Building for Billions 网站上寻找指导。

我花很多篇幅讨论了在新兴市场中缩小 APK 的好处。还有一个另外的缩小 APK 的原因,
这就是 Android Instant App 要求更小的 APK。Instant App 允许安卓用户不经过安装直接使用,是另一种让你的用户发现你的 app 的方式。关于开始使用 Android Instant App,你可以在这里找到更多信息。你也可以学习更多 管理下载内容大小的最佳实践。


浅谈Binder通信原理

发表于 2017-12-06 | 分类于 Android

主要成员

我们先来梳理下Binder通信的几个重要的成员:
1.Binder驱动
2.应用
3.系统服务
4.Binder
其中应用和系统服务处于不同的进程,由靠Binder驱动进行信息交互。

在网购如此发达的现在,人人都清楚淘宝上的聊天流程。
在这个过程中,也有对应的部分:
1.淘宝
2.用户
3.店家
4.聊天窗口

注:真实的淘宝通信系统肯定有所不同,这里仅提取与Binder通信相近之处。
再注:本来想举微信聊天的例子,但是微信聊天中客户端和服务端的属性没那么明显,所以选择淘宝聊天流程。

1
2
3
4
5
6
7
应用和系统服务处于不同进程              用户没在商家身边
应用无法直接调用系统服务中函数 用户直接和商家口头对话
应用需要通过Binder驱动去与系统服务通信 用户需要通过淘宝去和店家联系
Binder驱动中管理各个Binder 淘宝管理用户和商家的“聊天窗口”对象
应用可以访问到指定地址 用户可以访问到指定“聊天窗口”
系统服务也可以访问到同一个地址 商家可以访问到同一个“聊天窗口”
应用和系统服务都监听这个地址中内容变化 用户和商家都关注这个“聊天窗口”,看到对方发信息过来,处理后回复

聊天窗口

在用户和商家通信过程中,什么东西最重要呢?其实就是“聊天窗口”。
假设我们设计一个聊天系统,“聊天窗口”会有哪些重要的属性?
1.它是一个对象;
2.淘宝系统内部有一个地址k可以访问到它;
3.一端是用户,可以通过地址c访问到它;
4.另一端是商家,可以通过地址s访问到它。

同时也要需要解决很多问题,比如:
1.如何让用户联系到商家;
2.一个用户需要同事联系多个商家;
2.一个商家需要同时服务多个用户;
3.会不会有人把自己伪造成其他人等等。

Binder

与“聊天窗口”类似,Binder也有对应的属性:
1.它是一个对象;
2.Binder驱动有一个地址k可以访问到它;
3.一端是应用,可以通过地址c访问到它;
4.另一端是系统服务,可以通过地址s访问到它。

同样也需要解决很多问题,比如:
1.如何让应用联系到系统服务;
2.一个应用需要同事联系多个系统服务;
2.一个系统服务需要同时服务多个应用;
3.会不会有应用把自己伪造成其他应用等等。

主要流程

让我们看看,用户如何联系到商家:

同样在Binder中,也有一套这样的流程:

这张图片清晰表述了整个流程
1.打开Binder驱动;
2.将系统服务中地址s和Binder驱动中地址k指向同一地址;
3.将应用地址c和Binder驱动中地址k指向同一地址。
整个过程结束后,应用中地址c和系统服务中地址s也指向同一地址。这样两个不同的进程就关联成功了。

ServiceManager

其中有一个重要的问题,应用如何找到Binder驱动中的地址k?
在每次Android重启后,Binder驱动中地址k都不相同,应该怎么办?

怎么解决这个问题呢?
首先想到的方法,每次都记录下这些服务,下次启动时从备份文件中读取。
这个方法看上去很干脆利落,但是有一个风险。
如果上次服务发生异常,备份文件中也记录错误的数据,那这个手机就完了,永远无法启动。

需要改变下策略,希望每次Android系统重启时,这些系统服务都是新生成的。
这些系统服务启动时没有历史包袱一身轻松,然后愉快的注册到服务管理中心中。
应用只需要向服务管理中心查询服务名,就可以获取到地址k。

在Binder通信,这个服务管理中心就是ServiceManager,它管理所有的服务。
主要完成这两项任务:
1.所有的系统服务启动时,需要把服务名字和服务记录到ServiceManager中;
2.所有的应用使用指定系统服务前,先根据服务名称去向ServiceManager索要服务。

注:上面步骤中,按照C/S架构中划分:
1.系统服务是客户端,ServiceManager是服务端;
2.应用是客户端,ServiceManager是服务端。

我们看下Binder通信流程图:

再加入Binder驱动元素:

回到我们的例子,淘宝也有一个ServiceManager的角色,就是店铺黄页。
店铺黄页管理所有的店铺,也完成两项任务:
1.每个商家上线后都会去淘宝黄页注册,比如Nike店铺注册Nike;
2.用户去淘宝黄页询问Nike的商家,获取聊天窗口中店铺的地址。

这时细心的读者会发现一个问题,ServiceManager呢,这些系统服务和应用怎么找到它呢?
为了解决这个问题,Android系统不得不做例外处理:
1.在Android启动后,ServiceManager第一个初始化;
2.将自己编号设为0。
之后,无论是应用或者系统服务,都可以通过编码0访问到ServiceManager。


后记:在上大学时去图书馆随便翻书看过到多米尼克,感慨这个世界群星璀璨,有各种天才。
他发明的多米尼克训练法,告知人们需要用串联、转化、联想等等法则去记忆。
在学习Android底层中,有太多的对象和函数,如果能将其中主要流程和真实生活产生对应,会加速学习过程,而且印象深刻。

Brien

多米尼克·奥布莱恩,1957年8月10出生于英国。1991年,他参加了由“世界大脑先生”托尼·布赞发起的第一届世界记忆锦标赛,凭其独创的“多米尼克记忆系统”,38秒记住一副扑克牌的顺序,30分钟记住2385个随机产生的数字,1个小时记住110种元素的原子序数、符号、类别和精确到4位小数的原子量,一时技惊四座,横扫所有对手,获得第一届世界记忆锦标赛的总冠军。此后十余年间,他先后获得8次世界记忆冠军,几乎打破所有记忆领域的世界纪录,成为举世公认的“世界首席记忆大师”。

追溯Android的根源

发表于 2017-11-28 | 分类于 Android

某日进去一小区被保安拦住,被问了三个哲学问题:
“你是谁?”
“你从哪里来?”
“你要到哪里去?”
于是我陷入了深深的沉思。

同样,学习Android也有三个终极问题:
什么是Android?
Android世界的起源?
Android中APP是怎么运行的?

对于第一个问题,大家都能很快的回答出来。简单来说,Android是一种基于Linux,主要用于移动设备的操作系统。
第三个问题这样回答:APP的屏幕显示、输入事件获取、视频、音频等各个功能,在Android底层都有其对应的系统服务。
当然其中涉及到ActivityManagerService,WindowManagerService等等,后续有空会展开分析。
今天,我们来好好地看下第二个问题,Android系统是如何启动的,探讨下Android系统的起源。


启动

main()

就像我们编写的第一行代码helloworld一样,main()是helloworld世界的入口。
在Android中,main()也是Android世界的第一个入口,这个入口的位置在system\core\init\init.cpp。

main()主要工作:
1.参数校验
2.挂载一些设备,设置权限(与传统Linux程序相同)
3.初始化环境
4.LoadBootScripts()加载待启动项
5.处理待启动项

LoadBootScripts()

作用就是,加载引导的脚本init.rc,所有开机需要启动的配置读写在这里面。
像Android这样完善而又庞大的系统,在开机时肯定要启动有无数的服务。
如果全部都写到函数中,想必会变成硬编码,不方便于配置,所以这里用脚本方式配置启动内容。

1
2
3
4
5
6
static void LoadBootScripts(ActionManager& action_manager, ServiceList& service_list) {
// 生成解析器
Parser parser = CreateParser(action_manager, service_list);
// 解析文件内容后,放入action_manager和service_list中
parser.ParseConfig("/init.rc");
}

init.rc

该文件放在system\core\rootdir目录下
节选下其中重要的片段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
service zygote /system/bin/app_process -Xzygote /system/bin --zygote --start-system-server
class main
priority -20
user root
group root readproc
socket zygote stream 660 root system
onrestart write /sys/android_power/request_state wake
onrestart write /sys/power/state on
onrestart restart audioserver
onrestart restart cameraserver
onrestart restart media
onrestart restart netd
onrestart restart wificond
writepid /dev/cpuset/foreground/tasks

这段代码表示:启动名为zygote的Service。zygote翻译过来是“受精卵”,可以孕育出新生命。
在Android中,zygote也是万物的起源。
这段代码清晰的指出了Zygote的代码入口:app_process。

app_process

上面同样表示app_process是在目录/system/bin/中,不过因为这应该是软链接后的位置,
真实的位置在frameworks\base\cmds\app_process\App_main.cpp,而且入口也是main()。
这里截取其中的重要代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main(int argc, char* const argv[]) {
// 这里有两个变量去控制新进程的诞生
bool zygote = false; // 是否为zygote进程
bool startSystemServer = false; // 是否启动系统服务,例如ActivityManagerService等

while (i < argc) {
const char* arg = argv[i++];
if (strcmp(arg, "--zygote") == 0) {
zygote = true;
} else if (strcmp(arg, "--start-system-server") == 0) {
startSystemServer = true;
}
}
// 按照之前的入参--zygote --start-system-server分析,发现zygote和startSystemServer都被设置为true

if (zygote) {
runtime.start("com.android.internal.os.ZygoteInit", args, zygote); // 终于接近zygote真实本体了!
}
}

这里看下runtime,是AppRuntime类。我们赶紧去寻找下它的start方法吧。
发现AppRuntime继承于AndroidRuntime,AndroidRuntime中提供start()方法

AndroidRuntime

位于frameworks\base\core\jni\AndroidRuntime.cpp中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void AndroidRuntime::start(const char* className, const Vector<String8>& options, bool zygote) {
/*
* 开启virtual machine,这里env是JNIEnv*类型,指向整个Android的JNI世界
*/
startVm(&mJavaVM, &env, zygote);
/*
* 给虚拟机注册JNI的函数
*/
startReg(env);
/*
* 调用JNI static方法,启动zygote
* 这里startClass是com.android.internal.os.ZygoteInit类
* startMeth是startClass中的main()方法
*/
env->CallStaticVoidMethod(startClass, startMeth, strArray);
}

startVm()

这个函数有一超级长的check,最关键是最后一句JNI_CreateJavaVM(pJavaVM, pEnv, &initArgs);
完成这个函数后,VM正式创建成功,后续可以开始通过JNI对native底层代码进行调用了。

startReg()

这个函数中,最重要的是register_jni_procs(gRegJNI, NELEM(gRegJNI), env)
其中gRegJNI表示待注册的JNI函数,截取一段给大家看看

1
2
3
4
5
static const RegJNIRec gRegJNI[] = {
REG_JNI(register_android_os_Process),
REG_JNI(register_android_os_SystemProperties),
REG_JNI(register_android_os_Binder),
REG_JNI(register_android_os_Parcel),

发现原来Parcel、Binder等等Android独有的特性都在此处被注册,后面就可以通过JNI方式直接调用。

env->CallStaticVoidMethod

根据这个函数的入参,可以得知最后调用com.android.internal.os.ZygoteInit的main()函数。
从类名上可以推测出,这负责zygote的生成。

zygoteInit.main()

对应的文件为frameworks\base\core\java\com\android\internal\os\ZygoteInit.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void main(String argv[]) {
// 注册server socket,这里采用socket方式和其他进程通信
zygoteServer.registerServerSocket(socketName);
// 加载classes,opengl,textsource等各种资源
preload(bootTimingsTraceLog);
// 开启新进程,用以启动system server
if (startSystemServer) {
Runnable r = forkSystemServer(abiList, socketName, zygoteServer);
r.run();
return;
}
// 初始化zygote
caller = zygoteServer.runSelectLoop(abiList);
caller.run();
}

说了这么多,大家一定被绕晕了吧,这里整理一张流程图,大家可以对着看。

这里走向两个分支,我们接下去也分开去介绍zygote和System server初始化。

zygote

zygote,这是一个平凡而又伟大的进程,以后Android的所有进程都由他诞生。
我们继续来看下zygoteInit.main()中走向zygote分支的流程,后续调用zygoteServer.runSelectLoop()。

zygoteServer.runSelectLoop()

对应的文件为frameworks\base\core\java\com\android\internal\os\zygoteServer.java
其主要功能是,不断接受请求并作出响应。

1
2
3
4
5
6
7
8
9
10
11
12
13
Runnable runSelectLoop(String abiList) {
// 不断循环,接受并处理新请求
while (true) {
// 监听数据源
Os.poll(pollFds, -1);
for (int i = pollFds.length - 1; i >= 0; --i) {
// 解析出数据源的命令
ZygoteConnection connection = peers.get(i);
final Runnable command = connection.processOneCommand(this);
return commond;
}
}
}

zygote是采用poll的方式去监听数据源。
注:poll 是 Linux API 提供的复用方式。IO多路复用是指内核一旦发现进程指定的一个或者多个IO条件准备读取,它就通知该进程。
至此,zygote会处于runSelectLoop()的循环中,不断监听外部请求并作出响应,fork出进程。

system server

在android的启动过程中,我们也需要启动各种应用服务,我们来找下有他们是怎样诞生的。

forkSystemServer()

这个也在zygoteInit.main()中被调用到,上面已经有提及,这里就不重复列出了。
在这里发现了zygote的作用,zygote把自己的进程fork一份,用来启动各大系统服务。
zygote进程就像受精卵一样,慢慢分裂诞生出整个Android系统,并且在后续中,新进程的诞生也依赖与zygote的fork。
截取其中的重要代码

1
2
3
4
5
6
7
8
9
10
11
12
13
private static Runnable forkSystemServer(){
pid = Zygote.forkSystemServer(
parsedArgs.uid, parsedArgs.gid,
parsedArgs.gids,
parsedArgs.runtimeFlags,
null,
parsedArgs.permittedCapabilities,
parsedArgs.effectiveCapabilities);

if (pid == 0) {
return handleSystemServerProcess(parsedArgs);
}
}

handleSystemServerProcess()

handleSystemServerProcess()这个函数完成了fork后的剩余工作

1
2
3
4
5
6
private static Runnable handleSystemServerProcess(ZygoteConnection.Arguments parsedArgs) {
// 加载system server dex的option
performSystemServerDexOpt(systemServerClasspath);
// 启动system server
return ZygoteInit.zygoteInit(parsedArgs.targetSdkVersion, parsedArgs.remainingArgs, cl);
}

ZygoteInit.zygoteInit()

从函数命名来看,这是各大应用服务的初始化地址。

1
2
3
4
5
6
public static final Runnable zygoteInit(int targetSdkVersion, String[] argv, ClassLoader classLoader) {
// native层的初始化system server
ZygoteInit.nativeZygoteInit();
// 返回java层初始化system server的runnable,后续必然有run()的操作
return RuntimeInit.applicationInit(targetSdkVersion, argv, classLoader);
}

RuntimeInit.applicationInit()

越来越接近真相了,再坚持一会。

1
2
3
4
5
6
protected static Runnable applicationInit(int targetSdkVersion, String[] argv, ClassLoader classLoader) {
// 未来app调用exit()会直接退出,不会清理进程
nativeSetExitWithoutCleanup(true);
// 寻找最终的类以及方法
return findStaticMain(args.startClass, args.startArgs, classLoader);
}

findStaticMain()

从函数命名可以看出,这回找到服务的main()函数并调用。
这里说明良好的说明有多重要,可以让其他开发者在阅读纯代码时就能get到函数的含义。
这里列下findStaticMain()的重要片段

1
2
3
4
5
private static Runnable findStaticMain(String className, String[] argv, ClassLoader classLoader) {
Class<?> cl = Class.forName(className, true, classLoader); // 找到对应的类SystemServer
Method m = cl.getMethod("main", new Class[] { String[].class }); // 找到其中的main()函数
return new MethodAndArgsCaller(m, argv);
}

MethodAndArgsCaller

这是一个实现runnable的类,里面主要的run()就是去执行之前找到的method

1
2
3
4
5
static class MethodAndArgsCaller implements Runnable {
public void run() {
mMethod.invoke(null, new Object[] { mArgs });
}
}

ZygoteInit.main()

我们继续回到ZygoteInit.main()

1
2
3
4
5
6
7
8
9
public static void main(String argv[]) {
// 回到最开始出发的地方,这里r
Runnable r = forkSystemServer(abiList, socketName, zygoteServer);
// 接下去果然是run,其中运行SystemServer.main()
if (r != null) {
r.run();
return;
}
}

SystemServer.main()

这个函数里面就一句话,调用同一个类的run()

1
2
3
public static void main(String[] args) {
new SystemServer().run();
}

SystemServer().run()

看来这个是SystemServer的启动地了,看下其中的关键代码

1
2
3
4
5
6
7
8
9
10
11
12
private void run() {
// 准备主线程的Looper
Looper.prepareMainLooper();
// 加载native的服务
System.loadLibrary("android_servers");
// 开启各项系统服务
startBootstrapServices();
startCoreServices();
startOtherServices();
// 开启Looper循环,不断监听事件
Looper.loop();
}

至此,system server全部启动成功,并且开启Looper循环,会不断监听外来的请求并响应。

这里也梳理下system server整个启动过程。


我们已经清晰的梳理出Android的大致的启动流程。
可以结合上一篇文章《浅谈Android底层》一起看。上篇文章,在用户角度从表面慢慢推进到底层system server(包括ServiceManager、AMS、WMS等等)。再进一步,就是追溯这些zygote和system server的起源。

作为应用开发者,只需要完成两部:
1.配置AndroidManifest.xml的启动项
2.实现对应的Activity
就能完成最简单的应用。但是我始终会好奇其背后的神秘而又精密的机制。

我们身上始终留着追溯根源的血液。就像在遥远的古代,刀耕火种的人类在漫天星空下去追溯祖先的由来,构想了无数种文明的起源。此时,作为应用开发者,我们也在追溯Android系统的起源。

12
corresponding

corresponding

12 日志
7 分类
12 标签
GitHub
© 2018 corresponding
由 Hexo 强力驱动
|
主题 — NexT.Muse v5.1.3
访问人数 总访问量 次