Recap

• Concurrency = when two or more units of execution are run out-of-order, interleaved, potentially in parallel, and sharing resources
• Multiple tasks in progress at the same time
• We’ve been talking mostly about thread-based concurrency using the pthread library
• Threads: multiple units of execution within a single process
  • Shared global memory (heap + data)
  • Separate stack and register state
  • Can run on different cores, taking advantage of parallel execution
• Shared memory means risk of data races
• Critical sections of code are parts that access shared resources (memory) and are susceptible to data races
• We’ve seen one way of protecting critical sections: mutexes – 2-state locks (locked/unlocked)
• Downsides to mutexes: degraded performance, potential deadlocks
• In the lab, we’ve explored using locks to avoid data races and how to avoid deadlocks
• Conditions for data races:
  1. Concurrent execution of two or more threads/processes
  2. Shared data that both processes access (read or write)
  3. At least one thread/process writes

When do deadlocks happen?

• Happen when we introduce more than one lock and we end up in a “circular wait”
• Process 1: acquire lock A -> wait for lock B
• Process 2: acquire lock B -> wait for lock A
• No process can make any progress because they are waiting for each other to release the other lock
• “Easy” solution: enforce order on locks
• If lock A is ordered before lock B, then lock A cannot be acquired after lock B, that is, if we want both, we must acquire A first, and B only if we have A already
• See lock.c for an artificial example of a deadlock

Aside: When is data shared?

• Forked processes: Shared memory (mmap with MAP_SHARED)
• Threads: global variables, local static variables

1. Global variables
   • declared outside of a function
   • stored in the .data segment (if initialized)
   • fork: not shared
   • threads: shared
2. Local variables
   • declared inside of a function (no static keyword)
   • fork: not shared
   • threads: not shared (each thread has its own stack)
3. Local static variables
   • declared inside of a function with the static specifier
   • fork: not shared
   • threads: shared (only visible in the function it’s declared in)

Implementing a Concurrent Queue

• Let’s look at a queue implementation (queue.c)
• The idea: we have a queue using a linked list
• Note that there’s a weird little thing where we insert a dummy element at the beginning
• If we run this with a single reader and a single writer, things will look okay
• What if we introduce multiple readers and multiple writers?
• We will get intermittent errors
• How can we fix this?
• Add a lock!
• Can we do better than a single lock?
• Do we need to lock the whole queue?

Semaphores

• A more general primitive

• A semaphore - just an integer with some ops associated

• A lock (mutex) is just a special case of a semaphore

• Idea: if the semaphore is 0, we have to wait, if the semaphore > 0, we’re good to go

• sem_init - initialize a semaphore

• sem_wait - waits for semaphore to become != 0, decrements it by 1 atomically

• sem_post - increments semaphore by one atomically

• If we want the semaphore to be shared, we need to allocate it as a shared variable

• Example - using a semaphore as a lock (max value 1)

  sem = 1
  
  proc A             proc B             sem
  sem_wait(sem)                         1
  do_work();         sem_wait(sem);     0        // sem_wait blocks in B
  do_more_work();    .                  0
  .                  .                  0
  .                  .                  0
  .                  .                  0
  sem_post(sem);     .                  1        // sem_wait returns in B
  .                  do_work();         0
  sem_wait(sem);     do_more_work();    0        // sem_wait blocks in A
  .                  .                  0
  .                  sem_post(sem);     1        // sem_wait returns in A
  do_work();         .                  0

• See sum_semaphores.c

• Try

  $ time ./sem-sum

  and observe how much time is spent in the kernel. Compare this to the other versions

• Semaphores with higher values are used, for example, for counting resources

Basic Concurrency with Fork

• Take a sequential sum program: seq_sum.c
• Make it concurrent by summing up in two processes
• Doh! We need some way of sharing information - a shared variable!
• How do we do this? - Remember: processes have separate address spaces
• mmap has an option to allocate a shared piece of memory
• Now, did we get a speed-up?
• Okay, maybe let’s try more than two processes?
• How about a large number? E.g., 2,000,000 or 10,000,000
• Is the result correct?
• What we see is a data race - one of the problems connected with concurrent programming