CS537 10/14

Brief

• What is concurrency?
• What are the major issues? (atomicity and ordering)
• To begin:
  • Abstraction of running program
    • Process (Virtual address space, Registers)
      • One thing at at time
    • Multi-Threaded Process
      • To do many things at a time (concurrently)
      • 
      • When context switch - no need to change page table base ptr

Why Have Multi-threaded Program?

• Parallelism:
  • to use $N$ CPUs ($N$ > 1), to work on one problem faster
• I/O:
  • Waiting for an I/O => thread blocked (but others can run)

Problems: (Synchronization)

Atomicity

• sequence of actions: happen “all at once” (not interrupted)

Ordering

• one thing happens before the other

Atomicity

• Sequence of instructions:

•   load addr, reg
    add 1, reg
    store reg, addr
  

  copy
• Problem: Data Race (Race condition)
• Outcome: indeterminate (outcome is not deterministic)

• CPU1	CPU2	Memory
  load => reg (100)	load => reg (100)	balance: 100
  add 1 => reg(101)	add 2 => reg (101)
  store => 101	store => 101	balance: 101

• Can even happen on 1 CPU

• Thread1	Thread2
  load => reg (100)
  add 1 => reg (101)
  OS: Switch Thread
  	load => reg (100)
  	add => 101
  	store 101
  	OS: Switch Tread
  store => 101

• Desire: section of code (Critical Section)=> atomically (all at once)
  • Use lock: (lock/unlock or acquire/release)
  • How to build?
  • What is it?
    • Lock ensures that only 1 thread is running with in critical section at a time

Building a Lock

First Try: Spin Lock

• Simple implementation in C Wont Work