4

This is a job interview question.

Implement the singleton pattern with a twist. First, instead of storing one instance, store two instances. And in every even call of getInstance(), return the first instance and in every odd call of getInstance(), return the second instance.

My implementation is as follows:

public final class Singleton implements Cloneable, Serializable {
    private static final long serialVersionUID = 42L;
    private static Singleton evenInstance;
    private static Singleton oddInstance;
    private static AtomicInteger counter = new AtomicInteger(1);

    private Singleton() {
        // Safeguard against reflection
        if (evenInstance != null || oddInstance != null) {
            throw new RuntimeException("Use getInstance() instead");
        }
    }

    public static Singleton getInstance() {
        boolean even = counter.getAndIncrement() % 2 == 0;
        // Make thread safe
        if (even && evenInstance == null) {
            synchronized (Singleton.class) {
                if (evenInstance == null) {
                    evenInstance = new Singleton();
                }
            }
        } else if (!even && oddInstance == null) {
            synchronized (Singleton.class) {
                if (oddInstance == null) {
                    oddInstance = new Singleton();
                }
            }
        }

        return even ? evenInstance : oddInstance;
    }

    // Make singleton from deserializaion
    protected Singleton readResolve() {
        return getInstance();
    }

    @Override
    protected Object clone() throws CloneNotSupportedException {
        throw new CloneNotSupportedException("Use getInstance() instead");
    }
}

Do you see a problem? The first call may enter getInstance and the thread get preempted. The second call may then enter getInstance but will get the oddInstance instead of the evenInstance.

Obviously, this can be prevented by making getInstance synchronized, but it's unnecessary. The synchronization is only required twice in the lifecycle of the singleton, not for every single getInstance call.

Ideas?

Improve this question
2
  • To answer your previous comment: the double check pattern is broken, since the evaluation of conditional statements is a set of individual instructions that can be executed independently. The OS can and will switch between the threads (effectively between their call stacks) between any instruction and resume execution according to the current call stack's instruction pointer. This is used to realize scheduling. This also makes the order of execution and hence the composed conditional statement nondeterministic. This will add randomness to the NULL checks that even synchronized can't prevent Commented Jul 1, 2019 at 7:46
  • Yes you are right, there already exists an equal answer. Didn't realize that. Shame on me. I deleted the post. Commented Jul 1, 2019 at 7:47

3 Answers 3

Reset to default
8

Most importantly, the evenInstance and oddInstance variables need to be declared volatile. See the famous "Double-Checked Locking is Broken" declaration: https://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html

Also, you should really use different objects in the synchronization blocks for the even and odd instances so they can be constructed simultaneously.

Finally, the check in the Singleton constructor is broken and will throw an exception in the second call to getInstance()

Other than that it's fine, but it's better if you don't do the concurrency work yourself:

public final class Singleton implements Cloneable, Serializable {
    private static AtomicInteger counter = new AtomicInteger(1);


    public static Singleton getInstance() {
        if (counter.getAndIncrement() % 2 == 0) {
            return EvenHelper.instance;
        } else {
            return OddHelper.instance;
        }
    }

    private static class EvenHelper {
        //not initialized until the class is used in getInstance()
        static Singleton instance = new Singleton();
    }

    private static class OddHelper {
        //not initialized until the class is used in getInstance()
        static Singleton instance = new Singleton();
    } 
}
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

How does this solve the problem I described in the question, and in my comments to @Bohemian's answer?
That problem doesn't really exist. If the two calls are not in the same thread, then the "first" call is the one that does getAndIncrement first, and that order determines which one gets the even instance. There is no other definition of "first" that could apply.
"There is no other definition of "first" that could apply." Of course there is another definition. First is the thread that enters the getInstance method first. However, since the interpretation depends on who you ask, I think what you say can be considered as a viable alternative.
I like to add, that when using this pattern, the memory management of the JVM guarantees true thread safety, as multiple (concurrent) invocations of the inner class' EvenHelper.instance are blocked (or synchronized) until the class was created. In addition, this approach is implicitly lazy loading the actual singleton instances. Another side effect is that this approach eliminates the unsafe if-statements (Double Check Pattern).
@Abhijit, "entering the method" is actually a multi-step process, not an atomic operation, and none of its memory effects are necessarily ordered w.r.t. operations on other cores except by memory barriers like the one in getAndIncrement. Furthermore, if you were to synchronize getInstance, you would only be adding a lock operation with a memory barrier in exactly the same place where getAndIncrement is now.
3

You don't say the singleton must be lazily initialized, so I'll assume not...

You could be over-thinking it. Try this:

public final class Singleton implements Cloneable, Serializable {
    private static Singleton[] instances = new Singleton[]{new Singleton(), new Singleton()};
    private static AtomicInteger counter = new AtomicInteger();

    private Singleton() {} // further protection not necessary

    public static Singleton getInstance() {
        return instances[counter.getAndIncrement() % 2];
    }

    // Make singleton from deserializaion
    protected Singleton readResolve() {
        return getInstance();
    }

    @Override
    protected Object clone() throws CloneNotSupportedException {
        throw new CloneNotSupportedException("Use getInstance() instead");
    }
}

If you're worried about reflection attacks, just use an enum, which is bullet-proof, something like:

public final class Singleton implements Cloneable, Serializable {
    private static AtomicInteger counter = new AtomicInteger();
    private enum SingletonInstance implements Cloneable, Serializable {
        ODD, EVEN;
        private Singleton instance = new Singleton();
    }

    private Singleton() {} // further protection not necessary

    public static Singleton getInstance() {
        return SingletonInstance.values()[counter.getAndIncrement() % 2].instance;
    }

    // Make singleton from deserializaion
    protected Singleton readResolve() {
        return getInstance();
    }
}
Improve this answer

8 Comments

This doesn't solve the race condition that I described. You can still have thread 1 preempted, while thread 2 comes along and gets the wrong instance.
@AbhijitSarkar no, there's no race condition with this code, because both instances are created (by the class loader when the class is loaded) before the getInstance() method is allowed to be called.
That's not what I'm talking about, my code handles the creation just fine without your changes. The requirement is that the first call gets the instance meant for the odd calls, and second call gets the even instance. The bug in my code, that also exists in yours, is that the second call may get the odd instance.
In my opinion the enum approach is very clever, but not practicable. It will always appear like a hack and is not very convenient. If you would give me your library and this library declares an enum SingletonInstance I would expect it to be an enum. Maybe this enum is used to control the returned instance of a method. I definetly wouldn't expect a complex class like singleton (e.g. database connector) behind it. This means to this approach is a convention attached, probably a naming convention. This requires the consumer of your library to know this convention.
@BionicCode I agree with you that the enum Singleton pattern feels like a hack, because it isn’t an actual enum, but A) OP seems to be worried about defence against reflective hacks (fire with fire) and B) ppl keep shoving the pattern down our necks :(
|
0

Do you see a problem? The first call may enter getInstance and the thread get preempted. The second call may then enter getInstance but will get the oddInstance instead of the evenInstance.

Obviously, this can be prevented by making getInstance synchronized, but it's unnecessary. The synchronization is only required twice in the lifecycle of the singleton, not for every single getInstance call.

If you really want to "fix" this "problem", your only option is to synchronize getInstance. But how would one really see this problem? What if the first thread is preempted right after getInstance?

In multithreading, the absolute order of events is not completely deterministic. So you always have the risk that actions seem to be out-of-order.

btw: The against the "reflection attack" has a serious flaw! It prevents the construction of evenInstance! I guess you should change || to &&. But that still doesn't give you any guarantees, because the "reflection attack" could be between the first and second call. You have to preconstruct both instances at class loading time to be 99% sure.

And if you're worried about it, you should definitely implement neither Cloneable nor Serializable!

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.