休眠排序法

接下来咱一起来研究一下多线程加上sleep如何给整数类型的序列排序……

友情提醒，这只是我们对并发编程的一次探索和学习，在实际项目里千万可不能这么干。

初步实现

给序列的每个元素num都单独启动一个线程，并且传入这个元素num，线程内部调用：

Thread.sleep(num);

之后在结果序列尾部添加这个元素num，语言描述难，先看看线程类的定义，这里用到的所有类型都在java.util包里。：

class SortThread extends Thread
{
  // 在构造方法里传入元素num， result是排序后的结果
  public SortThread(int num, List<Integer> result)
  {
    super();
    this.num = num;
    this.result = result;
  }
  public void run()
  {
    // 先休眠在添加
    try
    {
      Thread.sleep(num);
    }
    catch (InterruptedException e)
    {
      e.printStackTrace();
    }
    result.add(num);
  }
  private int num;
  private List<Integer> result;
}

上面的SortThread类看着很简单，接下来给它加上一个静态方法：

// 传入一个List序列， 返回排序后的List序列
  public static List<Integer> sort(List<Integer> nums)
  {
    var result = new ArrayList<Integer>();
    var threads = new SortThread[nums.size()];  // nums有多少元素就创建多少线程
    for (int i = 0; i < threads.length; i++)
    {
      threads[i] = new SortThread(nums.get(i), result);
      threads[i].start();
    }
    try
    {
      // 等待所有任务运行结束
      for (var thread : threads)
      {
        thread.join();
      }
    }
    catch (InterruptedException e)
    {
      e.printStackTrace();
    }
    return result;
  }

这样算是把休眠排序写好了，接下来在我们的Main类里测试：

编写测试任务

  // main方法， 第一步初始化一个list序列， 填充随机数
    var nums = new ArrayList<Integer>();
    var random = new Random();
    System.out.println("随机序列长度");
    int len = new Scanner(System.in).nextInt();
    for (int i = 0; i < len; i++)
    {
      nums.add(random.nextInt(1000));
    }
    // 运行排序任务， 顺便记录运行时间
    long beginTime = System.currentTimeMillis();
    var result = SortThread.sort(nums);
    System.out.printf("用时： %d毫秒\n", System.currentTimeMillis() - beginTime);
    // 验证运行后的排序情况， 记录错误排序； 顺便输出错误排序具体数值
    int invalid = 0;
    for (int i = 1; i < result.size(); i++)
    {
      int left = result.get(i - 1);
      int right = result.get(i);
      if (left > right)
      {
System.out.printf("%d, %d\n", left, right);
        invalid++;
      }
    }
    // 输出运行结果
    String fmt = "成功";
    if (invalid != 0) fmt = String.format("排序失败： 比率%.2f%%\n", (invalid + 0.0) / nums.size() * 100);
    // ArrayList线程不安全所以多个线程访问的时候出现问题， 比如丢失元素
    if (nums.size() != result.size()) fmt = String.format("%s丢失率%.2f%%", (fmt.equals("成功")? "失败： ": fmt), (nums.size() - result.size() + 0.0) / nums.size() * 100);
    System.out.println(fmt);

运行看看，错误排序比例高；结果序列的丢失元素比例也相对严重，接下来我们给结果序列加上一把锁。

synchronised关键字

修改SortThread.run方法：

public void run()
{
  // .....
  synchronized (result)
  {
    result.add(num);
  }
}

我们在多个线程同时访问的地方加上代码块，而且用synchronized关键字修饰result变量。

再次编译运行，不会出现结果result丢失元素的情况了。

改用CopyOnWriteArrayList

当然遇到这样的场景优先可以选择java.util.concurrent包下的线程安全的List实现。

比如这里把

var result = new ArrayList<Integer>();
替换为
var result = new CopyOnWriteArrayList<Integer>();

这样可以去掉synchronized快，而且无需改写代码，因为CopyOnWriteArrayList实现了List接口。

最终版本

所以最后我们的程序变成了这样。

  public void run()
  {
.....
    result.add(num);
  }
  public static List<Integer> sort(List<Integer> nums)
  {
    var result = new CopyOnWriteArrayList<Integer>();
.....
  }

虽然解决了数据丢失的情况，但是错误排序还没解决，为此我做了两个改进，结果依然让人不满意, 在run方法里。

// 错误排序比例没有明显减少
      if (result.size() > 1 && result.get(result.size() - 1) > num)
    {
        result.add(result.size() - 2, num);
    }
      else
      {
        result.add(num);
      }

// 这里用2显然影响不了最终结果， 除非用更大的数字
Thread.sleep(num * 2);

结果还是不行，最后做个总结

总结

我电脑CPU4核心8线程；给40到50个元素排序还是能成功的，超过60个元素一次都没有成功过，在双核云主机上运行可能也就给20来个元素排序还差不多，再多就不行了。

首先线程的运行顺序是有操作系统来调度的，有着很大的随机性，然后sleep方法不是特别精确，只要有误差可能就影响到排序结果了。

此外我们通过这个例子看到了在并发编程的时候多个线程共享数据出现的问题。

比如add方法添加元素，这是分成了好几部来完成的， 1.确定索引， 2.保存元素，如果只有一个线程不会出现问题，但是多个线程共享的时候问题就来了。

第一个线程确定第八个位置是空闲的，然后操作系统切换线程，让第一个线程等待，让第二个线程运行，第二个线程也一样确定第8个位置是空闲的，随后这两个线程都把数据放在了第8个位置。

这样以来第一个线程或者第二个线程的数据被对方的数据覆盖了，谁覆盖谁这个也要看操作系统的线程调度，反正先运行的被后面的覆盖掉。

所以出现了线程锁的概念， synchronised不允许两个线程同时访问一个代码块。

好比以前上厕所卫生间锁不了门，有了synchronised就是有了一把锁，现在卫生间里只允许一个人进去，其他人在外面等着，里面的人出来后其他人在按照顺序进去。

此外java也提供了线程安全的并发数据结构，在Java.util.concurrent包里，在并发程序里应该优先使用。

写程序的时候我们需要和两个非常重要的计算机硬件打交道，内存和CPU，随着垃圾回收算法的广泛使用我们如何管理内存这个难题算是非常圆满的解决了，内存空间敞开了用就行了，其他问题无序关心。

但是怎么在多核CPU下编程却越来越紧迫了，似乎还没有出现和垃圾回收算法同等的并发编程技术，这个方面我还有很多东西要探索……

这是我程序和CPU系列文章的第一篇，后续会分享其他有意思的并发编程方面的文章。