Alternating Output Number and Letter in 2 Threads without Lock

In an interview I was asked to use 2 and only 2 threads to print the string 1A2B3C...24X25Y26Z, where one thread only prints numbers and the other only prints letter. I wrote the following code:

public class App {
    static volatile int x = 0;
    static volatile boolean numPrinted = false;

    static class NumThread implements Runnable {
        @Override
        public void run() {
            while (x < 26) {
                if (!numPrinted) {
                    System.out.print(x + 1);
                    numPrinted = true;
                }
            }
        }
    }

    static class LetterThread implements Runnable {
        @Override
        public void run() {
            while (x < 26) {
                if (numPrinted) {
                    System.out.print((char) ('A' + x));
                    ++x;
                    numPrinted = false;
                }
            }
        }
    }


    public static void main(String[] args) {
        Thread foo = new Thread(new NumThread());
        Thread bar = new Thread(new LetterThread());
        foo.start();
        bar.start();
        try {
            foo.join();
            bar.join();
        } catch (InterruptedException ignored) {

        }
        System.out.println();
    }
}

In about 1 out of 10 runs, it will produce

1A2B3C4D5E6F7G8H9I10J11K12L13M14N15O16P17Q18R19S20T21U22V23W24X25Y26Z27

What's the concurrency issue with my code? I avoid AtomicInteger intentionally.

Both threads are busy-waiting. So this is possible:

• LetterThread prints Z
• NumThread checks if x<26, it is
• LetterThread increments x, sets numPrinted=false
• NumThread check numPrinted, it is false, so prints 27

In NumThred check x again after numPrinted.

Your code has a race condition on the two class members x and numPrinted.
You might try implementing a mutex and a condition variable.
The following is an Ada example that works correctly every time.

with Ada.Text_IO;         use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
procedure Main is
protected traffic_Cop is
entry Nums (Val : Positive);
entry Alpha (Val : Character);
private
gate : Boolean := True;
end traffic_Cop;
protected body traffic_cop is
entry Nums (Val : Positive) when gate is
begin
Put (Item => Val, Width => 1);
gate := False;
end Nums;
entry Alpha (Val : Character) when not gate is
begin
Put (Val);
gate := True;
end Alpha;
end traffic_cop;
task printnums;
task printalpha;
task body printnums is
begin
for value in 1 .. 26 loop
traffic_cop.Nums (value);
end loop;
end printnums;
task body printalpha is
subtype chars is Character range 'A' .. 'Z';
begin
for value in chars loop
traffic_Cop.Alpha (value);
end loop;
end printalpha;
begin
null;
end Main;

The example uses one protected object and two tasks. An Ada protected object is protected from inappropriate race conditions. A task is often mapped to an operating system thread.

Protected objects can expose three kinds of methods.

A protected function implicitly establishes and implements a shared read lock, allowing multiple tasks to simultaneously read data from the protected object.

A protected procedure implicitly establishes and implements an exclusive read-write lock, allowing only one task at a time to unconditionally read or modify data within the protected object.

A protected entry implicitly establishes and implements an exclusive read-write lock along with an entry condition. A task calling an entry can read and/or modify the contents of the protected object only when the boundary condition associated with the entry evaluates to True.

The example above uses two entries.

The protected object traffic_cop contains only one variable, a Boolean value named gate which is initialized to the value True.

The protected body contains the implementation of the two entries. The entry Nums can only execute when gate is True. The entry Alpha can only execute then gate is false.

Two tasks are declared.

The task printnums loops through the values 1 through 26. In each loop iteration the task calls traffic_cop.nums then prints the numeric value.

The task printalpha loops through the values 'A' through 'Z'. In each loop iteration the task calls traffic_cop.alpha then prints the alpha value.

Both tasks automatically start when the "begin" statement for the main procedure is reached. The main procedure does nothing, which is explicitly indicated by the "null;" command.

The output of the program is:

1A2B3C4D5E6F7G8H9I10J11K12L13M14N15O16P17Q18R19S20T21U22V23W24X25Y26Z

This problem is easier solved by using just one shared variable, in this case numPrinted. This indicates which thread needs to do something. The threads themselves can keep track of their progress, wait until they need to print something, print it and then flip the numPrinted variable that is visible to both threads. This could look like:

	static volatile boolean numPrinted = false;
static class NumThread implements Runnable {
@Override
public void run() {
for (int number = 1; number <= 26; number++) {
// Wait until we need to print a number
while (numPrinted) {
Thread.yield(); //optional
};
// Print a number
System.out.print(number);
// Set flag that we printed a number
numPrinted = true;
}
}
}
static class LetterThread implements Runnable {
@Override
public void run() {
for (char letter = 'A'; letter <= 'Z'; letter++) {
// Wait until we need to print a letter
while (!numPrinted) {
Thread.yield(); //optional
}
// Print a letter
System.out.print(letter);
//set flag that we printed a letter
numPrinted = false;
}
}
}