无锁2线交替输出数字和字母

Question

在一次采访中，我被要求使用两个线程来打印字符串1A2B3C...24X25Y26Z，其中一个线程只打印数字，另一个线程只打印字母。我编写了以下代码：

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();
    }
}

在大约十分之一的运行中，它将产生

1A2B3C4D5E6F7G8H9I10J11K12L13M14N15O16P17Q18R19S20T21U22V23W24X25Y26Z27

我的代码有什么并发问题？我故意避开AtomicInteger。

Answer 1

两个线程都在忙着等待。所以这是有可能的：

is

• LetterThread

• LetterThread打印Z

• NumThread，如果x<26，它会增加x，设置numPrinted=false

• NumThread check numPrinted，它是假的，所以打印27

在NumThred中，在numPrinted之后再次检查x。

Answer 2

您的代码在两个类成员x和numPrinted上有一个争用条件。您可以尝试实现互斥和条件变量。下面是一个每次正确工作的Ada示例。

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;

该示例使用一个受保护的对象和两个任务。Ada受保护的对象不受不适当的竞争条件的影响。任务通常映射到操作系统线程。

受保护对象可以公开三种方法。

受保护函数隐式地建立和实现共享读锁，允许多个任务同时从受保护对象读取数据。

受保护的过程隐式地建立和实现独占读写锁，每次只允许一个任务无条件地读取或修改受保护对象中的数据。

受保护的条目隐式地建立和实现独占读写锁以及条目条件。调用条目的任务只能在与条目关联的边界条件计算为True时才能读取和/或修改受保护对象的内容。

上面的例子使用了两个条目。

受保护的对象traffic_cop只包含一个变量，一个名为Gate的布尔值，该值被初始化为True值。

受保护的主体包含这两个条目的实现。只有当门为真时，条目Num才能执行。入口Alpha只有在门为false时才能执行。

声明了两个任务。

任务printnum循环遍历值1到26。在每个循环迭代中，任务调用traffic_cop.nums，然后打印数值。

任务printalpha循环遍历值'A‘到'Z’。在每个循环迭代中，任务调用traffic_cop.alpha，然后打印alpha值。

当到达主过程的“开始”语句时，这两个任务都会自动启动。主过程不执行任何操作，这是由"null;“命令显式指示的。

程序的输出是：

1A2B3C4D5E6F7G8H9I10J11K12L13M14N15O16P17Q18R19S20T21U22V23W24X25Y26Z

Answer 3

仅使用一个共享变量(在本例中为numPrinted )就可以更容易地解决这个问题。这表明哪个线程需要做一些事情。线程本身可以跟踪它们的进度，直到它们需要打印一些东西，然后打印出来，然后翻转对两个线程都可见的numPrinted变量。这看起来可能是：

    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;
            }
        }
    }