HackThisSite - Extended Basic Mission 14

Posted on In Views: Disqus:

Challenge

Sam was trying to make a program to show how 1337 he is. But the output isn't always correct. Help him fix his program so he can impress his friends.

Sam 写了个程序想显得自己很 1337，但输出总是不对；帮他把程序修好。

关卡页给出完整的类源码：

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
package org.hackthissite.missions.extbasic;

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

public class ExtBasic14 {

        private final ExecutorService executorService = Executors.newFixedThreadPool(100);
        private static final int MAX = 1337;
        private int timeToGetLeet = 0;

        ExtBasic14() throws InterruptedException {
                for (int i = 0; i < MAX; i++) {
                        executorService.execute(new Runnable() {
                                public void run() {
                                        incrementLeetness();
                                }
                        });
                }
                executorService.shutdown();
                while (!executorService.isTerminated()) {
                        Thread.sleep(500);
                }
                System.out.println(timeToGetLeet);
        }

        private void incrementLeetness() {
                int obfusticatedIncremental = timeToGetLeet;
                obfusticatedIncremental = obfusticatedIncremental + 1;
                timeToGetLeet = obfusticatedIncremental;
        }

        /**
         * @param args
         */
        public static void main(String[] args) throws InterruptedException {
                new ExtBasic14();
        }

}

Solution

MAX = 1337，构造函数把 1337 个任务提交进一个 100 线程的固定池，每个任务只调用一次 incrementLeetness()，shutdown 等池终止后打印 timeToGetLeet。程序想要的输出是 1337。

被点名的 incrementLeetness() 是一个三步的读-改-写：

1
2
3
4
5
private void incrementLeetness() {
        int obfusticatedIncremental = timeToGetLeet;
        obfusticatedIncremental = obfusticatedIncremental + 1;
        timeToGetLeet = obfusticatedIncremental;
}

而且 timeToGetLeet 是普通实例字段，没有 volatile，整个方法也没有任何锁。

多线程交错执行这段代码时会出现经典的丢失更新：

1
2
3
4
5
6
线程 A: obfusticatedIncremental = timeToGetLeet    // 读到 0
线程 B: obfusticatedIncremental = timeToGetLeet    // 也读到 0
线程 A: obfusticatedIncremental = 0 + 1
线程 A: timeToGetLeet = 1
线程 B: obfusticatedIncremental = 0 + 1
线程 B: timeToGetLeet = 1

A、B 各做了一次自增，计数却只从 0 走到 1：B 读到的旧值 0 在 A 写回之后仍然被写回，A 的那次增量被覆盖。100 个线程争抢同一个三段序列，丢失的更新累积起来，System.out.println 打出的值就稳定地低于 1337。

用 OpenJDK 17.0.20.1：原始类原样编为 broken，只把方法声明改成 private synchronized void 编为 fixed，各跑 10 次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
$ javac -d broken/out broken/org/hackthissite/missions/extbasic/ExtBasic14.java
$ javac -d fixed/out  fixed/org/hackthissite/missions/extbasic/ExtBasic14.java
$ for i in $(seq 1 10); do java -cp broken/out org.hackthissite.missions.extbasic.ExtBasic14; done
1333
1336
1332
1335
1337
1335
1335
1335
1337
1335
$ for i in $(seq 1 10); do java -cp fixed/out org.hackthissite.missions.extbasic.ExtBasic14; done
1337
1337
1337
1337
1337
1337
1337
1337
1337
1337

broken 十次落在 1332–1337 之间（只有两次偶然凑满），fixed 十次全是 1337。两份源码的唯一差异是那个 synchronized：

1
2
3
4
5
private synchronized void incrementLeetness() {
        int obfusticatedIncremental = timeToGetLeet;
        obfusticatedIncremental = obfusticatedIncremental + 1;
        timeToGetLeet = obfusticatedIncremental;
}

synchronized 加在实例方法上，等价于整段方法体在 this 的监视器锁内执行：同一时刻只有一个线程能进入读-改-写序列，丢失的更新随之消失。

Key points

  • 递增（x = x + 1）不是原子操作，多线程下必须用锁或原子类型保护；synchronized 方法等价于用 this 做互斥。
  • 只加 volatile 不够：它保证可见性与有序性，但不会让读-改-写变成原子操作，两个线程仍能交错读走同一个旧值。
  • AtomicInteger.incrementAndGet() 用 CAS 免锁达到同样的原子性；本例只需修 incrementLeetness，加 synchronized 是最小改动。
  • 竞争窗口越小越难复现：broken 十次里有两次恰好是 1337，判断修好没有要多跑几次，不能只看单次输出。