07concurrency/concurrency

   1 %Concurrency
   2 %Thadeu Cascardo
   3
   4 # Races
   5
   6 # Classical increment examples
   7
   8 * Threads are incrementing a counter
   9 * Thread A reads the counter from memory
  10 * Thread A is interrupted
  11 * Thread B reads the counter from memory
  12 * Thread B increments the counter
  13 * Thread B saves the counter to memory
  14 * Thread A executes and now has the wrong value in its registers
  15
  16 # Critical section
  17
  18 In the last example, the section of code that increments the *global*
  19 counter is a critical section.
  20
  21 # Shared data
  22
  23 The problem in here is sharing data with multiple threads. When sharing,
  24 we need to serialize the access, that is, only one thread may execute
  25 the critical section at a time.
  26
  27 # Classical problems
  28
  29 * The Philosophers' Dinner
  30 * The Barber Shop
  31 * Consumer and Producer
  32
  33 # Linux historical race handling
  34
  35 * cli/sti
  36 * BKL
  37 * semaphores/old mutexes
  38 * spinlocks
  39 * RCU
  40 * new mutexes
  41
  42 # Semaphores and mutexes
  43
  44 # Semaphores
  45
  46 * include linux/semaphore.h
  47 * kernel/semaphore.c
  48 * down(sem)
  49 * up(sem)
  50 * sema\\_init(sem, val)
  51 * init\\_MUTEX(sem)
  52 * init\\_MUTEX\\_LOCKED(sem)
  53 * DECLARE\\_MUTEX(varname)
  54 * down\\_interruptible(sem)
  55
  56 # New mutex
  57
  58 * Ingo Molnar's design
  59 * Documented at Documentation/mutex-design.txt
  60
  61 # How to use the new mutex
  62
  63 * struct mutex
  64 * mutex\\_init(mtx)
  65 * DEFINE\\_MUTEX(varname)
  66 * mutex\\_lock
  67 * mutex\\_unlock
  68
  69 # When you should or should not use them
  70
  71 * They both sleep, so take care: no atomic contexts
  72 * When the critical section may sleep
  73
  74 # Spinlocks
  75
  76 * include linux/spinlock.h
  77 * Documentation/spinlocks.txt
  78
  79 # How to declare them
  80
  81 * DEFINE\\_SPINLOCK
  82 * spinlock\\_t
  83 * spin\\_lock\\_init
  84
  85 # How to use them
  86
  87 * spin\\_lock
  88 * spin\\_unlock
  89 * spin\\_lock\\_irqsave
  90 * spin\\_unlock\\_irqrestore
  91
  92 # When you should and should not use them
  93
  94 * They can be used in atomic contexts
  95 * They lock the processor when "waiting", so use for fast critical
  96   sections
  97 * They create an atomic context themselves, so *do not* sleep while
  98   using them
  99
 100 # Atomic
 101
 102 * atomic\\_t
 103 * ATOMIC\\_INIT(val)
 104 * atomic\\_read(v)
 105 * atomic\\_set(v, i)
 106 * atomic\\_add\\_return(i, \\&v)
 107 * atomic\\_add(i, \\&v)
 108 * atomic\\_inc(i, \\&v)
 109 * atomic\\_sub
 110 * atomic\\_dec
 111 * atomic\\_dec\\_and\\_test
 112
 113 # Bitmap
 114
 115 May be used for locking, but spinlocks are better nowadays.
 116
 117 # Per-CPU
 118
 119 * linux/percpu.h
 120 * DEFINE\\_PER\\_CPU(type, name)
 121 * get\\_cpu\\_var(name)
 122 * put\\_cpu\\_var(name)
 123 * per\\_cpu(name, cpu)
 124 * alloc\\_percpu(type)
 125 * free\\_percpu
 126 * cpu = get\\_cpu()
 127 * per\\_cpu\\_ptr(var, cpu)
 128 * put\\_cpu()
 129
 130 # RCU
 131
 132 * rcu\\_read\\_lock
 133 * rcu\\_dereference
 134 * rcu\\_read\\_unlock
 135 * rcu\\_assign\\_pointer
 136 * synchronize\\_rcu
 137 * call\\_rcu
 138
 139 # RCU for lists
 140
 141 * linux/rculist.h
 142 * list\\_add\\_rcu
 143 * list\\_add\\_tail\\_rcu
 144 * list\\_del\\_rcu
 145 * list\\_for\\_each\\_entry\\_rcu