阿里的一个面试题目：实现一个线程安全的类

今天被阿里面跪了，其中有一个问题我目前还没有想到答案，他们提出的问题是，不要用锁，不要用sychronized块或者方法，也不要直接使用jdk提供的线程安全的数据结构，需要自己实现一个类来保证多个线程同时读写这个类中的共享数据是线程安全的，怎么破？

43 个解决方案

#1

设置标记位。
访问方法先判断标记位是否为false,否的话改为true然后运行，运行完改回来。
大公司就喜欢这个，不需要你懂多少，但是希望你懂原理，具有创新性

#2

引用 1 楼 AA5279AA 的回复:

设置标记位。
访问方法先判断标记位是否为false,否的话改为true然后运行，运行完改回来。
大公司就喜欢这个，不需要你懂多少，但是希望你懂原理，具有创新性

弱弱的问一句用锁是怎么样的？怎么感觉就是这样？

#3

引用 1 楼 AA5279AA 的回复:

设置标记位。
访问方法先判断标记位是否为false,否的话改为true然后运行，运行完改回来。
大公司就喜欢这个，不需要你懂多少，但是希望你懂原理，具有创新性

类似操作系统里面的“信号量”，PV操作。从这里发散

#4

引用 1 楼 AA5279AA 的回复:

设置标记位。
访问方法先判断标记位是否为false,否的话改为true然后运行，运行完改回来。
大公司就喜欢这个，不需要你懂多少，但是希望你懂原理，具有创新性

他用什么数据类型作为这个信号量呢 光读取这个信号量也是需要线程安全的

#5

操作系统里面的信号量机制，我觉得是想考查这个。

话说楼主，你是校招面的阿里么？还是社会招聘面的阿里？回复我下。急需了解下！！！

#6

话说AtomicBoolean算不算线程安全的数据结构？

#7

另外如果不用任何锁就能实现线程安全，那还要锁干啥？AtomicBoolean本质上来说也是一个锁，只不过有时候是操作系统加线程锁模拟，有时候是CPU的一条指令，要看是什么CPU。所以这个问题的答案要么就是AtomicBoolean，要么就是无解了。。

#8

引用 1 楼 AA5279AA 的回复:

设置标记位。
访问方法先判断标记位是否为false,否的话改为true然后运行，运行完改回来。
大公司就喜欢这个，不需要你懂多少，但是希望你懂原理，具有创新性

#9

现在招聘不就是那样吗，其实想想招聘，招到好的人员也不容易。好点的公司肯定会出一些比较耐捉摸的题测试下你，如果从网上直接扒，那就说明那家公司没有什么前景，很容易被淘汰。看似千篇一律，实则道道不同。人也是一样的，人人相似，但人人不同。

#10

觉得就是考察锁的原理吧  设置一个标记   读和写的时候都先判断一下标记

#11

该回复于2013-09-27 08:58:24被管理员删除

#12

题目只要求线程安全共享一个这个数据对象，我觉得这个对象只要是一个不可变对象就行了比如“String“ 对象，我觉得是楼主紧张了吧。

#13

只要你理解 同步代码块的原理，这个应该不难吧，楼上很多都说啦 设置标记，只要不要让多个线程同时使用共享资源就好啦

#14

该回复于2014-11-23 14:47:40被管理员删除

#15

我的思路：
在这个类中维护一个队列，用来记录要访问共享数据的线程。每次只能由队列头部所表示的线程访问这些数据，一旦这个线程访问完毕，就出队。
这是看Python官方文档得到的启示。

#16

引用 15 楼 mayadong7349 的回复:

我的思路：
在这个类中维护一个队列，用来记录要访问共享数据的线程。每次只能由队列头部所表示的线程访问这些数据，一旦这个线程访问完毕，就出队。
这是看Python官方文档得到的启示。

这个队列要不要锁？

#17

引用 16 楼 hejianyuan 的回复:

Quote: 引用 15 楼 mayadong7349 的回复:

我的思路：
在这个类中维护一个队列，用来记录要访问共享数据的线程。每次只能由队列头部所表示的线程访问这些数据，一旦这个线程访问完毕，就出队。
这是看Python官方文档得到的启示。

这个队列要不要锁？

好问题！我确实没考虑到这一点。又看了一下文档，发现其中说道的确要求这个队列是线程安全的。

#18

该回复于2013-09-27 15:46:53被管理员删除

#19

“不要直接使用jdk提供的线程安全的数据结构”能具体讲讲么，什么都不让用我完全想不出啊。。。

#20

引用 楼主 yxz329130952 的回复:

今天被阿里面跪了，其中有一个问题我目前还没有想到答案，他们提出的问题是，不要用锁，不要用sychronized块或者方法，也不要直接使用jdk提供的线程安全的数据结构，需要自己实现一个类来保证多个线程同时读写这个类中的共享数据是线程安全的，怎么破？

首先你这个需要标记是原子的吧？同时原子性和易变性还不同，还得防止这个标记被优化到缓存，所以你的方法应该是需要原子性和用关键字volatile修饰吧？

#21

引用 5 楼 yzw19932010 的回复:

操作系统里面的信号量机制，我觉得是想考查这个。

话说楼主，你是校招面的阿里么？还是社会招聘面的阿里？回复我下。急需了解下！！！

校招哈，刚完，据说今年阿里扩招。

#22

引用 7 楼 lcf 的回复:

另外如果不用任何锁就能实现线程安全，那还要锁干啥？AtomicBoolean本质上来说也是一个锁，只不过有时候是操作系统加线程锁模拟，有时候是CPU的一条指令，要看是什么CPU。所以这个问题的答案要么就是AtomicBoolean，要么就是无解了。。

AtomicBoolean应该是在机器级别的原子性，应该还是和锁不一样。

#23

#24

引用 21 楼 yxz329130952 的回复:

Quote: 引用 5 楼 yzw19932010 的回复:

操作系统里面的信号量机制，我觉得是想考查这个。

话说楼主，你是校招面的阿里么？还是社会招聘面的阿里？回复我下。急需了解下！！！

校招哈，刚完，据说今年阿里扩招。

我这城市没有笔试。好悲剧。祝你好运了。

#25

阿里的面试就是这样的。貌似他们特别喜欢去考察那些底层的东西，比如XX类的实现方式什么的。

#26

volatile boolean flag = true;

这样如何

#27

加个信号量应该就可以了

#28

引用 26 楼 eewcee 的回复:

volatile boolean flag = true;

这样如何

public class Counter {
 
    public volatile static int count = 0;
 
    public static void inc() {
 
        //这里延迟1毫秒，使得结果明显
        try {
            Thread.sleep(1);
        } catch (InterruptedException e) {
        }
 
        count++;
    }
 
    public static void main(String[] args) {
 
        //同时启动1000个线程，去进行i++计算，看看实际结果
 
        for (int i = 0; i < 1000; i++) {
            new Thread(new Runnable() {
               // @Override
                public void run() {
                    Counter.inc();
                }
            }).start();
        }
 
        //这里每次运行的值都有可能不同,可能为1000
        System.out.println("运行结果:Counter.count=" + Counter.count);
    }
}

#29

引用 2 楼 dbj1991 的回复:

Quote: 引用 1 楼 AA5279AA 的回复:

设置标记位。
访问方法先判断标记位是否为false,否的话改为true然后运行，运行完改回来。
大公司就喜欢这个，不需要你懂多少，但是希望你懂原理，具有创新性

弱弱的问一句用锁是怎么样的？怎么感觉就是这样？

这是典型的先询问后执行问题，多线程并发编程最忌这个，你这个设置标志位是行不通的。
你可以将这个共享变量设置为final域就可以了，它这个就是告诉你final域的重要性吧。
否则没有锁是不可想象的

#30

class ThreadSafe{

	private static int toSecond = 5*1000; //超时毫秒数
	private  boolean flag = false;
	private  int source = 1;

	public int printSource(){
		return source;
	}


	public boolean incSource(){
		if (!canAccess()){
			return false;
		}
		flag = true;
		source++;
		flag = false;
		return true;
	}


	public boolean decSource(){
		if (!canAccess()){
			return false;
		}
		flag = true;
		source--;
		flag = false;
		return true;
	}

	/**
	 * 判断能不能访问，不能访问说明在修改,要等待一下
	 */
	private boolean canAccess(){
		int time=0;
		while (flag){
			try{
				Thread.sleep(2);
			}catch(Exception ex){
				//不考虑那么多，不做处理
			}
			time+=100;
			//这里也不考虑那么多，认为循环一次就100毫秒
			if (time>toSecond){
				return false;
			}
		}
		return true;
	}

}

根据各位大牛的意见写个例子让大家喷喷。

#31

引用 29 楼 xby1993 的回复:

Quote: 引用 2 楼 dbj1991 的回复:

Quote: 引用 1 楼 AA5279AA 的回复:

设置标记位。
访问方法先判断标记位是否为false,否的话改为true然后运行，运行完改回来。
大公司就喜欢这个，不需要你懂多少，但是希望你懂原理，具有创新性

弱弱的问一句用锁是怎么样的？怎么感觉就是这样？

这是典型的先询问后执行问题，多线程并发编程最忌这个，你这个设置标志位是行不通的。
你可以将这个共享变量设置为final域就可以了，它这个就是告诉你final域的重要性吧。
否则没有锁是不可想象的

final 域可以做到数据安全，能详细说说是怎么回事吗？我还是第一次听说。

#32

引用 30 楼 yousteely 的回复:

class ThreadSafe{

	private static int toSecond = 5*1000; //超时毫秒数
	private  boolean flag = false;
	private  int source = 1;

	public int printSource(){
		return source;
	}


	public boolean incSource(){
		if (!canAccess()){
			return false;
		}
		flag = true;
		source++;
		flag = false;
		return true;
	}


	public boolean decSource(){
		if (!canAccess()){
			return false;
		}
		flag = true;
		source--;
		flag = false;
		return true;
	}

	/**
	 * 判断能不能访问，不能访问说明在修改,要等待一下
	 */
	private boolean canAccess(){
		int time=0;
		while (flag){
			try{
				Thread.sleep(2);
			}catch(Exception ex){
				//不考虑那么多，不做处理
			}
			time+=100;
			//这里也不考虑那么多，认为循环一次就100毫秒
			if (time>toSecond){
				return false;
			}
		}
		return true;
	}

}

根据各位大牛的意见写个例子让大家喷喷。

你这个应该不行的，多线程并发访问flag就会出现问题。

#33

引用 26 楼 eewcee 的回复:

volatile boolean flag = true;

这样如何

应该是

volatile AtomicBoolean flag = true;

不过如果用

if(flag){
  //临界区
}

貌似也是不可行的，因为当flag=true时如果多个线程同时获取此时flag的值，就会同时进入临界区，这样就做不到互斥访问了。看来还得抽时间写个程序检验一下。

#34

引用 29 楼 xby1993 的回复:

Quote: 引用 2 楼 dbj1991 的回复:

Quote: 引用 1 楼 AA5279AA 的回复:

设置标记位。
访问方法先判断标记位是否为false,否的话改为true然后运行，运行完改回来。
大公司就喜欢这个，不需要你懂多少，但是希望你懂原理，具有创新性

弱弱的问一句用锁是怎么样的？怎么感觉就是这样？

这是典型的先询问后执行问题，多线程并发编程最忌这个，你这个设置标志位是行不通的。
你可以将这个共享变量设置为final域就可以了，它这个就是告诉你final域的重要性吧。
否则没有锁是不可想象的

解释一下呗，我也第一次听说这个。

#35

引用 31 楼 yousteely 的回复:

Quote: 引用 29 楼 xby1993 的回复:

Quote: 引用 2 楼 dbj1991 的回复:

Quote: 引用 1 楼 AA5279AA 的回复:

设置标记位。
访问方法先判断标记位是否为false,否的话改为true然后运行，运行完改回来。
大公司就喜欢这个，不需要你懂多少，但是希望你懂原理，具有创新性

弱弱的问一句用锁是怎么样的？怎么感觉就是这样？

这是典型的先询问后执行问题，多线程并发编程最忌这个，你这个设置标志位是行不通的。
你可以将这个共享变量设置为final域就可以了，它这个就是告诉你final域的重要性吧。
否则没有锁是不可想象的

final 域可以做到数据安全，能详细说说是怎么回事吗？我还是第一次听说。

jvm对final域会做特殊化处理，final域可以保证可见性，由于final域是不可变的，故而无需担心多线程并发导致的数据不一致问题，不过我还得补充一点，就是当final域为对象引用时，final域引用的对象是可变的时，仍然是非线程安全的，
我说的还是有点纠结，说白了就是把这个类设计为不可变类。不可变类绝对是线程安全的。

#36

引用 34 楼 yxz329130952 的回复:

Quote: 引用 29 楼 xby1993 的回复:

Quote: 引用 2 楼 dbj1991 的回复:

Quote: 引用 1 楼 AA5279AA 的回复:

设置标记位。
访问方法先判断标记位是否为false,否的话改为true然后运行，运行完改回来。
大公司就喜欢这个，不需要你懂多少，但是希望你懂原理，具有创新性

弱弱的问一句用锁是怎么样的？怎么感觉就是这样？

这是典型的先询问后执行问题，多线程并发编程最忌这个，你这个设置标志位是行不通的。
你可以将这个共享变量设置为final域就可以了，它这个就是告诉你final域的重要性吧。
否则没有锁是不可想象的

解释一下呗，我也第一次听说这个。

jvm对final域会做特殊化处理，final域可以保证可见性，由于final域是不可变的，故而无需担心多线程并发导致的数据不一致问题，不过我还得补充一点，就是当final域为对象引用时，final域引用的对象是可变的时，仍然是非线程安全的，
我说的还是有点纠结，说白了就是把这个类设计为不可变类。不可变类绝对是线程安全的。

#37

引用 36 楼 xby1993 的回复:

Quote: 引用 34 楼 yxz329130952 的回复:

Quote: 引用 29 楼 xby1993 的回复:

Quote: 引用 2 楼 dbj1991 的回复:

Quote: 引用 1 楼 AA5279AA 的回复:

设置标记位。
访问方法先判断标记位是否为false,否的话改为true然后运行，运行完改回来。
大公司就喜欢这个，不需要你懂多少，但是希望你懂原理，具有创新性

弱弱的问一句用锁是怎么样的？怎么感觉就是这样？

这是典型的先询问后执行问题，多线程并发编程最忌这个，你这个设置标志位是行不通的。
你可以将这个共享变量设置为final域就可以了，它这个就是告诉你final域的重要性吧。
否则没有锁是不可想象的

解释一下呗，我也第一次听说这个。

jvm对final域会做特殊化处理，final域可以保证可见性，由于final域是不可变的，故而无需担心多线程并发导致的数据不一致问题，不过我还得补充一点，就是当final域为对象引用时，final域引用的对象是可变的时，仍然是非线程安全的，
我说的还是有点纠结，说白了就是把这个类设计为不可变类。不可变类绝对是线程安全的。

如果设置为不可变类，就明显和题目的要求不一样了。

#38

我想了想，如果只是简单的变量，可以设置这个共享变量为AtomicInteger等原子类型，同时用volatile进行修饰，即可保证线程安全。但是如果是比较复杂的类作为共享变量，目前还是没有想到有效的解决方案。

#39

引用 38 楼 yxz329130952 的回复:

我想了想，如果只是简单的变量，可以设置这个共享变量为AtomicInteger等原子类型，同时用volatile进行修饰，即可保证线程安全。但是如果是比较复杂的类作为共享变量，目前还是没有想到有效的解决方案。

赞同使用volatile 可以保证基本的线程安全。

#40

这个问题标记法也不行。多个线程肯呢过同时通过校验。因为校验与赋值是2步。

#41

引用 1 楼 AA5279AA 的回复:

设置标记位。
访问方法先判断标记位是否为false,否的话改为true然后运行，运行完改回来。
大公司就喜欢这个，不需要你懂多少，但是希望你懂原理，具有创新性

先判断标记位是否为false,否的话改为true然后运行.
这是2步，所有的线程都可能通过第一步。这个问题如何解决？

#42

引用 13 楼 w215230188 的回复:

只要你理解 同步代码块的原理，这个应该不难吧，楼上很多都说啦 设置标记，只要不要让多个线程同时使用共享资源就好啦

说的对。可以参照《现代操作系统》里讲的Perterson解法

#43

看了只有volatile还算靠谱，其他的都是瞎胡闹