Chap 1

1.1互斥算法

进程vs线程

• 计算机需要能够同时执行多个任务
• 可以并行执行，也可以在执行过程中反复切换任务，或者两者混合执行
• 重量级进程有自己的代码、数据内存(全局变量和堆空间)和执行堆栈(局部变量和方法调用的激活记录)
  • 进程可以独立运行，提供对外部资源(如文件)的访问是协调的(如由操作系统)
• 一个线程的执行(轻量级进程)共享代码和数据内存，但有自己的执行堆栈
  • 线程可以在同一代码的不同点运行
  • 需要仔细协调对全局变量/字段的访问(共享状态)，以避免竞争条件
• 不同的应用程序通常在不同的进程中执行，但在应用程序中，线程通常用于执行多个任务
  • 操作系统需要时间在进程之间上下文切换(必须保存/恢复进程状态每个开关)
  • 在线程之间切换比在进程之间切换快得多

原子操作

• 一个原子操作，保证一个线程在一瞬间完全执行

• 没有其他线程可见的中间状态

• 不是很明显什么操作是原子的，比如x++不是原子的，因为它可能变成多个机器指令

  LOAD R,x
  INC R
  STORE R,x
  

• 每个线程都有自己的执行堆栈，所以使用相同寄存器变量R的两个线程没有问题(它们在交换线程时被保存/恢复)

非原子操作期间的线程交换

• 如果线程通过非原子操作进行交换，可能会发生“奇怪的事情”(竞态条件)

• 如果一个线程试图读取一个全局变量/字段，而另一个线程正在更改它的值，读取的值取决于线程交换执行时的精确时间

  • 场景1:线程A开始执行x++，但线程B在线程A存储新值之前读取了x(线程B获得了原始值)

    LOAD R,x
    INC R
    							LOAD R,x
    STORE R,x
    

  • 场景2:线程A执行x++，然后线程B随后读取x(线程B获得增量值)

    LOAD R,x
    INC R
    STORE R,x
    							LOAD R,x
    

更新丟失

• 当两个线程修改相同的共享状态时，也会发生更糟糕的“奇怪的事情”

• 示例:线程A执行x++，而线程B也执行x++

  • 场景1:线程A执行x++然后线程B执行x++ (x加2)

    LOAD R,x
    INC R
    STORE R,x
    							LOAD R,x
    							INC R
    							STORE R,x
    

  • 场景2:线程A开始执行x++，但是线程B在线程A存储新值之前读取了x (x只加1)

    LOAD R,x
    INC R
    							LOAD R,x
    							INC R
    							STORE R,x
    STORE R,x
    

• 被称为“更新丟失问题”

  • 即使多个线程执行代码来更新共享状态，有时只出现一些更新

  • 调试可能非常具有挑战性

  • 示例代码LostUpdate

    /**
       A class that demonstrates the lost update problem in concurrency
       by creating two threads that concurrently try to increment x
       each a total of ITERATIONS times.
       Sometimes the final value of x is not 2*ITERATIONS
    */
    
    public class LostUpdate implements Runnable
    {
            
       private int x;
       private static final int ITERATIONS = 20000000; // multiple of 10
       
       public LostUpdate()
       {
              x = 0;
       }
       
       // repeatedly increment the value of x 
       public void run()
       {
              System.out.println("Thread " + Thread.currentThread()
             + " started with x = " + x);
          int loopIterations = ITERATIONS/10;
          for (int i=0; i<loopIterations; i++)
          {
              x++; x++; x++; x++; x++; x++; x++; x++; x++; x++;
          }
          System.out.println("Thread " + Thread.currentThread()
             + " finishing with x = " + x); 
       }
       
       public static void main(String[] args)
       {
              // create two concurrent threads
          LostUpdate lostUpdate = new LostUpdate();
          Thread threadA = new Thread(lostUpdate);
          Thread threadB = new Thread(lostUpdate);
          threadA.start();
          threadB.start();
          try
          {
              // wait for both threads to finish
             threadA.join();
             threadB.join();
          }
          catch (InterruptedException e)
          {
              System.out.println("Interrupted " + e);
          }
          System.out.println("The final value of x is " + lostUpdate.x);
       }
    }
    
    

临界区代码 Critical Sections of Code

• 临界区是一个代码块，一次只能由一个线程执行
• 临界区有访问或更新共享状态的代码
• 互斥是指线程想要访问一个或多个使用相同共享状态的临界区
• 强制线程在临界区段内执行代码之前获取锁
• 在任何时刻，只有一个线程可以持有
• 当线程不再需要在临界区段内执行代码时，线程必须释放锁
• 互斥锁与共享状态相关
• 每个共享状态可能有自己的锁，控制访问或更新共享状态的任何临界区

互斥算法的软件方法

互斥算法

• ***互斥算法***是一种实现互斥的算法

  • 大大多数互斥锁算法会延迟“Acquire-Lock”中的线程，直到它被允许访问
  • 互斥锁算法在如何正确工作方面非常微妙

• 如何不写互斥算法(因为它并不总是保证互斥对于线程t，使用一个名为***exclude***的布尔标志

  **Incorrect-Acquire-Lock(t)**
  1 while exclude do
  2 delay
  3 exclude <- true
  
  **Incorrect-Release-Lock(t)**
  1 exclude <- false
  

• 简单地使用布尔标志可能无法进行测试，并且设置标志可能不是原子的

  • 一个线程可能完成while循环，然后在它设置exclude之前切换到另一个线程

Dekker的算法：单标志法

Dekker 's Algorithm是第一个正确处理(仅)两个线程的互斥的算法：

• 为每个线程维护一个请求标志，当线程请求锁时设置该标志

• 维护一个优先级变量，以指示在平局情况下，两个线程中接下来应该访问哪个线程

  **Dekker-Acquire-Lock(t)**
  1 s <- the other thread than t
  2 requested[t] <- true
  3 while requested[s] do
  4 if priority = s then
  5 requested[t] <- false
  6 while priority = s do
  7 delay
  8 requested[t] <- true
  
  **Dekker-Release-Lock(t)**
  1 s <- the other thread than t
  2 priority <- s 3 requested[t] <- false
  

  • 两个线程都可以并发调用Dekker-Acquire-Lock，但只有一个线程会返回
  • 另一个线程将延迟while循环，直到第一个线程调用Dekker-Release-Lock

皮特森算法/Peterson Algorithm

• Peterson算法简化了Dekker算法

  • 为每个线程维护一个请求的标志字段，该字段在线程请求锁时设置
  • 维护一个回合变量来控制在平局情况下下一个线程必须等待

• 在变量回合中利用竞争条件

  **Peterson-Acquire-Lock(t)**
  1 s <- the other thread than 
  2 requested[t] <- true
  3 turn <- t 4 while turn = t and requested[s] do
  5 delay
  
  **Peterson-Release-Lock(t)**
  1 requested[t] <- false
  

• 可以修改为也工作在两个以上的线程(过滤算法)

  • 每个线程都将进入更高的级别，以便最终获得锁

兰波特面包店算法/ Lamport’s Bakery Algorithm

• Lamport的bakery算法可以处理任意数量的线程

  • 每个想要访问的线程被分配一个数字
  • 数量增加，因为请求(但可能不是唯一的，如果竞争条件)
  • 线程的最低数字是下一个给定的访问权限
  • 每个线程有一个唯一的Id，以防领带
  • 为每个线程维护选择标志，以确保当前线程选择数字时不会提供锁

  Lamport-Acquire-Lock(t)
  1 choosing[t] <- true
  2 assign a number to thread t one larger than currently assigned maximum
  3 choosing[t] <- false
  4 for each thread s do
  5 while choosing[s] do
  6 delay
  7 while (num[s]≠0 and num[s]<num[t]) or
  (num[s]=num[t] and Id[s]<Id[t]) do
  8 delay
  Lamport-Release-Lock(t)
  1 num[t] <- 0
  

互斥锁算法的硬件辅助

• 许多进程支持测试和设置指令

  • 硬件保证是原子的
  • 将内存位置设置为新值，返回原来的值

• 原子测试和设置操作有助于创建简单的互斥锁算法

  • 维护排除标志

  TestAndSet-Acquire-Lock(t)
  1 while TestAndSet(exclude, true) do
  2 delay
  TestAndSet-Release-Lock(t)
  1 TestAndSet(exclude, false)
  

线程旋转、阻塞和等待

• 最简单的延迟线程的方法是让它旋转(忙等待)时间
  • 线程在有处理器时间的时候反复检查条件，看看是否可以继续
    一旦线程有条件，它就会进行
  • 但是如果条件持续失败很长时间，线程会浪费处理器时间
• 最好让线程块阻塞(睡眠）
  • 线程检查条件，如果不能进行，就放弃当前的时间片，这样其他线程就可以使用处理器时间
  • 将再次检查条件时，下一次分配的时间片
• 最好但更复杂的解决方案可能是让线程等待
  • 线程检查条件，如果不能进行，它放弃当前的时间片，并被放入一个等待集
  • 线程不能做任何事情，没有得到处理器时间，直到它被从等待集删除
  • 需要与另一个线程协调，该线程可以通知自己何时从等待集中删除

更多reference

互斥：https://en.wikipedia.org/wiki/Mutual_exclusion

Leslie Lamport的面包店算法论文：http://lamport.azurewebsites.net/pubs/bakery.pdf