370CT: Concurrency

Dr Carey Pridgeon

Created: 2017-06-21 Wed 14:09

Concurrency Part One

Serial programs

  • Data is can be shared between functions because the operations are serial.
  • If two functions need the same variable, they can't access it in unexpected order.
  • For Loops can have operations that depend on the outcome of calculations in previous loop iterations (order dependancy).
  • Program operation, and thus resource access is predictable.
  • The program may be making random choices, but only one choice will have context at a time.

Threaded Programs - 1

  • Threaded programs can perform multiple tasks simultaniously.
  • OS mediated predictability is no longer present, so order must be enforced by the developer.
  • In concurrent programs this control is provided by Critical Sections, which utilise Mutexes

Mutexes: Binary Locks

  • There are several different types of mutex. The simplest is a Binary Lock. These (perhaps predictably), can hold one of two values:
    • 1 - unlocked, can be obtained by a thread.
    • 0 - locked, requesting threads must wait in a queue outside the lock waiting for the currently owning thread to release it.
  • This type of Mutexes allows for periodic tests of the lock, but threads must wait a while after a test before trying again.
  • Blocked means it cannot progress beyond the code that needs to obtain the lock.

Mutexes: Semaphores 1

  • Semaphores (known usually as Counting Semaphores) can hold multiple values, from 0..N.
  • This type of mutex is used when there is more than one resource available to which the critical section is allowing access. The max value of the semaphore will reflect the number of resources available.
  • Printers/sockets/array elements.

Mutexes: Semaphores 2

  • Threads can obtain access to a semaphore protected resource as long as the value of the counting semaphore is non zero.
  • Each thread, on obtaining the semaphore, decrements it by one. On releasing it they increment it again. Threads awaiting access will test and wait until they can decrement the semaphore and gain access.
  • If the initial value of the counting semaphore is 1, then it functions in an equivalent manner to a lock.

Mutexes: Spinlocks

  • Spinlocks can prevent queues getting too long, because they test the lock constantly, so there is no wait time between tests.
  • However, Spinlocks are meant to work at the OS level, where they serve to prevent slowdown.
  • Spinlocks aren't designed to work in User Space, because the constant checking would eat up runtime, slowing your program to a crawl.
  • Most OS manufacturers advice strongly against their use in anything but embedded single task systems, and then sparingly.

Threaded Programs - 2

  • Faliure to assert access control causes what is called a Race Condition.
  • If data is shared by multiple threads, it must have the access control which was formally provided inherently in serial programs explicitally set.
  • If this is not done you will find that the various threads will update the shared var out of order and mess it up.

Critical Sections

  • These are the means by which we prevent multiple threads updating the same variable simultaneously and breaking our program by causing incorrect values to be stored.
  • Threads must wait in a queue to access any resource protected by a critical section.
  • These constructs are protected by a lock. While waiting for a lock, the thread is blocked.
  • Queues are both a solution to a problem and the cause of a more serious problem in parallel programming.

Critical Section example

  • Mutex Lock
    • Code in protected region.
  • Mutex Unlock
  • Python code to acheive this:

    from Threading import Lock
    lock = Lock()
    def thread(lock, ):
     lock.acquire()
     # code
     lock.release()
    

Queues

  • Criticial Sections enforce read access rights.
  • Threads sit in queues waiting for their turn in the section.
  • Threads test the lock intermitantly (depending on the type of the mutex in use).
  • Queues solve the access order problem, but cause another problem by placing an upper limit on scaling.

What is Deadlock

  • Deadlock occurs when a shared resource is needed by a thread to continue, but is being held by another.

    deadlock.png

Resolving Deadlock

  • The usual method is to design them out, or try to.
  • Gödel's incompleteness theorems say you can't actually do this, but we can hum real loud and pretend.
  • The more a system shares resources, the more likely Deadlocks are to occur, and the harder they are to prevent.
  • Deadlock breaking algorithms do exist, but they are computationally costly.
  • Generally only used in faliure intolerant real time systems.
    • Fighters.
    • Spacecraft/Robotic Explorers.
    • Self Driving Cars.

Thread Safety - 1

  • Thread safety refers to the capability of an operation to be run simultaniously in multiple threads.
  • If doing so will cause consistancy problems, then the operation lacks thread safety.
  • You need to know what is, and what isn't, thread safe.
  • Thread safety an be created by applying critical sections to problematic code, but critical sections are expensive.

Thread Safety - 2

  • What isn't threadsafe?
    • Class methods with that manipulate mutable member variables.
    • Functions/Procedures with pointer perameters.
    • Variables shared between threads that isn't critical section protected.
    • Printing to screen.
    • Writing to files.
    • Global Variables.

Thread Safety - 3

  • Minimising thread safety issues.
    • If using OOP avoid overly complex classes with lots of data members.
    • Wherever possible, eliminate mutable types.
    • Where possible, avoid procedures/functions that manipulate data passed by reference.

Thread Safety - 4

  • Any non thread safe operation must either occur inside a critical section, or be eliminated from your program.
  • Critical Sections are expensive and their use should be minimised.
  • The more critical sections you are forced to use, the worse your program design is.
  • There are languages designed to minimise the need to use mutexes, but time constraints mean we won't be using any of them.

What is an Atomic Operation - 1

  • Atomic operations are those which occur in a single clock tick.
  • Because of this property, they cannot be interupted by processor context switching.
  • Mutexes (Mutual Exclusion variables) have their state changed in atomic operations.

What is an Atomic Operation - 2

  • A normal variable would be tested in one operation, and set in the next.
  • If we used this to control access to a critical section, what would happen?

What is an Atomic Operation - 3

  • Processors can do this comparison and setting operation in one go, via 'compare and exchange'.
  • If a mutex is compared to its unobtained state (where unobtained = 1 and obtained = 0 ) and already is obtained, then compare and exchange will fail.
  • If the state is 1, then compare and exchange's attempt to set to mutex 0 will succeed, and the thread that ran compare and exchange will own the mutex.

Ordering Operations in Concurrent Programs

  • Thus far we have discussed ordering operations only as applied to variable read/write updates.
  • Programs usually need to do actions in a specific order.
  • Threads alone have no concept of order beyond the critical section.

How Serial programs do it

  • Serial programs have inherent order control conditions.
  • All operations are sequential, so the condition is primarily that one operation must complete for another to start.
  • Boolan switches and the like enforce logical control too.
  • An operation activated by a button click won't start till that button is clicked.

How Concurrent programs do it - 1

  • You can use Booleans, or other logical controls if you like, but this is bad because:
    • As program complexity increases, so do the amount of variables you need.
    • State is very hard to monitor in a concurrent program.
    • Normal variables will not pause a thread. This means threads which aren't in use will keep thrashing the processor.

How Concurrent programs do it - 2

  • A better method is Condition Variables
  • Condition variables will block a thread till the condition it needs is met.
  • Conceptually these are similar to event handlers in programs with a GUI.

How Concurrent programs do it - 3

  • Here's some sample Python code for condition variables (no you can't just copy and paste this and have it work).

    # declare a condition variable:
    cv = threading.Condition()
    cv.acquire() # Obtain the condition when available, or block.
    do_the_codes()
    cv.notifyAll() # tell all waiting threads the condition is free
    cv.release()   # free the condition
    
  • Using this functionality you can tell threads when to run, thus restoring order control.

So you have order back, what next? - 1

  • Using Condition variables you can control the order of operations, but how do you say which thing gets to run?
  • You need some kind of normal variable that the condition can check to see if it is it's turn, or the turn of another thread testing the condition.

    cv.acquire() 
    if (access==2):
     print "\nI can do a thing.\n"
     secs = random.randint(1, 4)
     time.sleep(secs)
     cv.notifyAll()
     cv.release()
     access=3
    else:
     cv.notifyAll()
     cv.release()
    

So you have order back, what next? - 2

  • In C I'd use ennumerated types, here I've just used an int. The value of the int tells the program which thread to hand control to.
  • In the assignment you'd need one condition variable, and one int to control all the order within your program.
  • Note: the normal int is inside the condition test, so checking it doesn't thrash the processor.