MTH 4355 Concurrency(Threads and Locks)

thread

a subprocess of a process

parallelism

many threads working on a single task together

concurrency

multiple tasks making progress by switching execution(not at same time)

stack, PC, registers

each thread receives its own _

non-deterministic(indeterminate)

can’t tell what comes first each time

non-deterministic(indeterminate)

threads are _ and it is up to scheduler

Data race

two or more threads competing to control a shared variable

critical section

a point in the code that accesses a shared variable(must not be accessed by more than one thread at the same time)

mutual exclusion

one thread executes in a critical section, other threads cannot execute critical section

atomic operation

series of actions that must be done together or not at all

Pthread Create

Pthread_create(pointer to thread object, NULL(Default), pointer to start of function, arguments for the function)

Pthread_join

pthread_join(pointer to thread to wait for, pointer to return value)

creating a lock

1. create lock object

2. initialize lock object

3. lock (referencing the lock you created)

4. unlock(referencing the lock you created)

5. (destroy your lock when done)

trylock

trying to grab a lock. returns failure if lock is held

timelock

return lock after a timeout or after acquiring lock

wrapper

int rc = pthread_mutex_lcok(*lock)
asser(rc ==0) //check for failure

lock struct

struct lock_t {int lock; //free = 0 held = 1}

spin lock

a lock that uses a while with a condition to wait until lock is free in order to grab it

test-and-set

a hardware primitive that returns old value of lock and sets lock to new value at the same time

test-and-set code

int TestAndSet(int old_ptr, int new) {
int old = old_ptr; // fetch old value at old_ptr
*old_ptr = new; // store ’new’ into old_ptr
return old; // return the old value }

void lock(lock_t *mutex) {

while (TestAndSet(&lock->flag, 1) == 1)
; // spin-wait (do nothing) maybe yield() instead?
}

compare-and-exchange

a hardware primitive that checks if a value is equal to expected, if so, update with new value(at the same time)

compare-and-exchange code

int CompareAndSwap(int ptr, int expected, int new) {
int original = ptr;
if (original == expected)
*ptr = new;
return original;}

void lock(lock_t *lock) {
while (CompareAndSwap(&lock->flag, 0, 1) == 1)
; // spin
}

Load Linked

returns a value at an address

Store-Conditional

updates value there was no update to the value since LL

Store-Conditional code

int StoreConditional(int ptr, int value) {
if (no update to ptr since LL to this addr) {
*ptr = value;
return 1; // success!
} else {
return 0; // failed to update
}

LL/SC lock

void lock(lock_t *lock) {
while (1) {
while (LoadLinked(&lock->flag) 1)
; // spin until it’s zero
if (StoreConditional(&lock->flag, 1) 1)
return; // if set-to-1 was success: done
// otherwise: try again
}
}

Fetch and Add

primitive that increments a value by 1, but returns its old value

ticket lock

uses fetch and add primitive to create a lock.

when trying to grab lock, increment ticked # by 1(using fetch and add) and set the previous ticket to your turn

spin until turn == myturn

when unlocking, increment the turn by 1

ticket-lock code

void lock(lock_t lock) {
int myturn = FetchAndAdd(&lock->ticket);
while (lock->turn != myturn){
;}} // spin
void unlock(lock_t lock) {
lock->turn = lock->turn + 1; }

yield

alternative to spinning. give up the CPU when the lock is held by another thread

Queue Lock

threads waiting for a lock to sleep.

Guard lock protects the queue

Flag lock protects the critical section

Test-and-Set and spin is used to acquire guard lock and unlock

we add thread to queue if the flag lock is held by another thread

we wake the next thread on queue when unlocking

Queue lock code

void lock(lock_t m) {
while (TestAndSet(&m->guard, 1) 1)
; // acquire guard lock by spinning
if (m->flag 0) {
m->flag = 1; // lock is acquired
m->guard = 0;
} else {
queue_add(m->q, gettid());
m->guard = 0;
park();}}
void unlock(lock_t m) {
while (TestAndSet(&m->guard, 1) == 1)
; // acquire guard lock by spinning
if (queue_empty(m->q))
m->flag = 0; // let go of lock; no one wants it
else
unpark(queue_remove(m->q)); // hold lock (for next
m->guard = 0;}
Shane Clark MTH-4355 Operating Systems 52 / 121

Queue lock problem

1. test-and-set still uses spin with guard

2. thread can be interrupted when releasing or acquiring lock(small section though so not terrible)

   1. if T1 releases lock just before T2 sleeps(parks), then T2 could sleep forever

Queue Lock fix

add a call setpark() to indicate that the thread was going to go to sleep before the interrupt

two phase lock

if a thread is about to give up a lock, another thread can spin for a certain amount of time. If in that given time, lock is not released, put waiting thread to sleep

Approximate counter

one global counter with lock and multiple local threads(per cpu) and their own lcok

if local counter reaches a threshold value, add it to global value while holding global lock

approximate counter problem

can end in deadlock if you want to retrieve global value at any given time

hand over hand locking

instead of locking entire data structure, lock parts of it

conditional variable

used for a thread to check whether a certain condition is true before execution

Ex. pthread_join

wait() puts thread to sleep and releases lock(assuming lock is held) atomically

when woken, automatically acquires lock

signal() wakes up another thread if>=1 threads are waiting