Operating Systems 1 (8/12) - Concurrency

Concurrency
Beuth Hochschule

Summer Term 2014

!
Pictures (C) W. Stallings, if not stated otherwise

Pthread material from http://computing.llnl.gov/tutorials/pthreads

!
!
„When two trains approach each other at a crossing,  
both shall come to a full stop and neither shall start up again  
until the other has gone.“ 
[Kansas legislature, early 20th century]"

ParProg | Introduction PT / FF 14
Abstraction of Concurrency [Breshears]
• Processes / threads represent the execution of atomic statements
• „Atomic“ can be deﬁned on diﬀerent granularity levels, e.g. source code line, 
so concurrency should be treated as abstract concept
• Concurrent execution is the interleaving of atomic statements from multiple
sequential processes

• Unpredictable execution sequence of atomic instructions due to non-deterministic
scheduling and dispatching, interrupts, and other activities

• Concurrent algorithm should maintain properties for all possible inter-leavings

• Example: All atomic statements are eventually included (fairness)

• Some literature distinguishes between interleaving (uniprocessor) and  
overlapping (multiprocessor) of statements - same problem
3

Concurrency
• Management of concurrent activities in an
operating system

• Multiple applications in progress at the
same time, non-sequential operating
system activities

• Time sharing for interleaved execution

• Demands dispatching and
synchronization

• Parallelism: Actions are executed
simultaneously
• Demands parallel hardware

• Relies on a concurrent application
4
Core
Core
time
Thread1
Thread2
Thread1
Thread2
Memory Memory
Core

Concurrency is Hard
• Sharing of global resources

• Concurrent reads and writes on the same variable makes order critical

• Optimal management of resource allocation

• Process gets control over a I/O channel and is then suspended before using it

• Programming errors become non-deterministic

• Order of interleaving may / may not activate the bug

• Happens all with concurrent execution, which means even on uniprocessors

• Race condition

• The ﬁnal result of an operation depends on the order of execution

• Well-known issue since the 60‘s, identiﬁed by E. Dijkstra
5

Race Condition
• Executed by two threads on uniprocessor

• Executed by two threads on multiprocessor

• What happens ?
6
void echo() {
char_in = getchar();
char_out = char_in;
putchar(char_out);
}
This is a
„critical
section“

Terminology
• Deadlock („Verklemmung“)
• Two or more processes / threads are unable to proceed

• Each is waiting for one of the others to do something

• Livelock
• Two or more processes / threads continuously change their states in response to
changes in the other processes / threads

• No global progress for the application

• Race condition
• Two or more processes / threads are executed concurrently

• Final result of the application depends on the relative timing of their execution
7

Potential Deadlock
8
I need quad
A and B
I need quad
B and C
I need quad
C and B
I need quad
D and A

Actual Deadlock
9
HALT until
B is free
HALT until
C is free
HALT until
D is free
HALT until
A is free

Terminology
• Starvation („Verhungern“)
• A runnable process / thread is overlooked indeﬁnitely

• Although it is able to proceed, it is never chosen to run (dispatching / scheduling)

• Atomic Operation („Atomare Operation“)
• Function or action implemented as a sequence of one or more instructions

• Appears to be indivisible - no other process / thread can see an intermediate state
or interrupt the operation

• Executed as a group, or not executed at all

• Mutual Exclusion („Gegenseitiger Ausschluss“)
• The requirement that when one process / thread is using a resource,  
no other shall be allowed to do that
10

Example: The Dining Philosophers (E.W.Dijkstra)
• Five philosophers work in a college, each philosopher has a room for thinking

• Common dining room, furnished with a circular table,  
surrounded by ﬁve labeled chairs

• In the center stood a large bowl of spaghetti, which was constantly replenished

• When a philosopher gets hungry:

• Sits on his chair

• Picks up his own fork on the left and plunges 
it in the spaghetti, then picks up the right fork

• When ﬁnished he put down both forks  
and gets up

• May wait for the availability of the second fork

Example: The Dining Philosophers (E.W.Dijkstra)
• Idea: Shared memory synchronization has diﬀerent standard issues

• Explanation of deadly embrace (deadlock) and starvation (livelock)
• Forks taken one after the other, released together

• No two neighbors may eat at the same time

• Philosophers as tasks, forks as shared resource

• How can a deadlock happen ?

• All pick the left fork ﬁrst and wait for the right

• How can a live-lock (starvation) happen ?

• Two fast eaters, sitting in front of each other

• One possibility: Waiter solution (central arbitration)
12
(C)Wikipedia

Critical Section
• n threads all competing to use a shared resource (i.e.; shared data, spaghetti forks)

• Each thread has some code - critical section - in which the shared data is accessed

• Mutual Exclusion demand
• Only one thread at a time is allowed into its critical section, among all threads that
have critical sections for the same resource.

• Progress demand
• If no other thread is in the critical section, the decision for entering should not be
postponed indeﬁnitely. Only threads that wait for entering the critical section are
allowed to participate in decisions. (deadlock problem)

• Bounded Waiting demand
• It must not be possible for a thread requiring access to a critical section to be
delayed indeﬁnitely by other threads entering the section. (starvation problem)
13

Critical Section
• Only 2 threads, T0 and T1

• General structure of thread Ti (other thread Tj)

• Threads may share some common variables to synchronize their actions
14
do {
enter section
critical section
exit section
reminder section
} while (1);

Critical Section Protection with Hardware
• Traditional solution was interrupt disabling, but works only on multiprocessor

• Concurrent threads cannot overlap on one CPU

• Thread will run until performing a system call or interrupt happens

• Software-based algorithms also do not work, due to missing atomic statements

• Modern architectures need hardware support with atomic machine instructions

• Test and Set instruction -  
read & write memory at once

• If not available, atomic swap  
instruction is enough

• Busy waiting, starvation or  
deadlock are still possible
15
#define LOCKED 1!
int TestAndSet(int* lockPtr) {!
int oldValue;!
oldValue = SwapAtomic(lockPtr, LOCKED);!
return oldValue;!
}
function Lock(int *lock) {!
while (TestAndSet (lock) == LOCKED);!
}

16
„Manual“ implementation!
of a critical section for !
interleaved output

Binary and General Semaphores [Dijkstra]
• Find a solution to allow waiting processes  
to ,sleep‘

• Special purpose integer called semaphore

• P-operation: Decrease value of its argument  
semaphore by 1 as atomic step

• Blocks if the semaphore is already zero - 
wait operation

• V-operation: Increase value of its argument  
semaphore by 1 as atomic step

• Releases one instance of the resource  
for other processes - signal operation

• Solution for critical section shared between N processes

• Binary semaphore has initial value of 1, counting semaphore of N
17
wait (S):
while (S <= 0);
S--; // atomic
signal (S):
S++; // atomic
do {
wait(mutex);
critical section
signal(mutex); 
remainder section
} while (1);

Semaphores and Busy Wait
• Semaphores may suspend/resume threads to avoid busy waiting

• On wait operation

• Decrease value

• When value <= 0, calling thread is suspended and added to waiting list

• Value may become negative with multiple waiters

• On signal operation

• Increase value

• When value <= 0, one waiting thread is 
woken up and remove from the waiting list
18
typedef struct {
int value;
struct thread *L;
} semaphore;

Shared Data Protection by Semaphores
19

POSIX Pthreads
• Part of the POSIX specification collection, defining an API for thread creation and
management (pthread.h)

• Implemented by all (!) Unix-alike operating systems available

• Utilization of kernel- or user-mode threads depends on implementation

• Groups of functionality (pthread_ function prefix)

• Thread management - Start, wait for termination, ...

• Mutex-based synchronization

• Synchronization based on condition variables
• Synchronization based on read/write locks and barriers
• Semaphore API is a separate POSIX specification (sem_ prefix)
20

POSIX Pthreads
21

POSIX Pthreads
22
• pthread_create()
• Create new thread in the process, with given routine and argument

• pthread_exit(), pthread_cancel()
• Terminate thread from inside our outside of the thread

• pthread_attr_init() , pthread_attr_destroy()
• Abstract functions to deal with implementation-speciﬁc attributes 
(f.e. stack size limit)

• See discussion in man page about how this improves portability
int pthread_create(pthread_t *restrict thread,
const pthread_attr_t *restrict attr,
void *(*start_routine)(void *),
void *restrict arg);

23
/******************************************************************************!
* FILE: hello.c!
* DESCRIPTION:!
* A "hello world" Pthreads program. Demonstrates thread creation and!
* termination.!
* AUTHOR: Blaise Barney!
* LAST REVISED: 08/09/11!
******************************************************************************/!
#include <pthread.h>!
#include <stdio.h>!
#include <stdlib.h>!
#define NUM_THREADS! 5!
!
void *PrintHello(void *threadid)!
{!
long tid;!
tid = (long)threadid;!
printf("Hello World! It's me, thread #%ld!n", tid);!
pthread_exit(NULL);!
}!
!
int main(int argc, char *argv[])!
{!
pthread_t threads[NUM_THREADS];!
int rc;!
long t;!
for(t=0;t<NUM_THREADS;t++){!
printf("In main: creating thread %ldn", t);!
rc = pthread_create(&threads[t], NULL, PrintHello, (void *)t);!
if (rc){!
printf("ERROR; return code from pthread_create() is %dn", rc);!
exit(-1);!
}!
}!
!
/* Last thing that main() should do */!
pthread_exit(NULL);!
}

POSIX Pthreads
24
• pthread_join()
• Blocks the caller until the speciﬁc thread terminates

• If thread gave exit code to pthread_exit(), it can be determined here

• Only one joining thread per target is thread is allowed

• By the book, threads should be joinable (old implementations problem)

• pthread_detach()
• Mark thread as not-joinable (detached) - may free some system resources

• pthread_attr_setdetachstate()
• Prepare attr block so that a thread can be created in some detach state
int pthread_attr_setdetachstate(pthread_attr_t *attr, int detachstate);

POSIX Pthreads
25

26
/*****************************************************************************!
* FILE: join.c!
* AUTHOR: 8/98 Blaise Barney!
* LAST REVISED: 01/30/09!
******************************************************************************/!
#include <pthread.h>!
#include <stdio.h>!
#include <stdlib.h>!
#define NUM_THREADS! 4!
!
void *BusyWork(void *t) {!
int i;!
long tid;!
double result=0.0;!
tid = (long)t;!
printf("Thread %ld starting...n",tid);!
for (i=0; i<1000000; i++) {!
result = result + sin(i) * tan(i); }!
printf("Thread %ld done. Result = %en",tid, result);!
pthread_exit((void*) t); }!
!
int main (int argc, char *argv[]) {!
pthread_t thread[NUM_THREADS];!
pthread_attr_t attr;!
int rc; long t; void *status;!
!
pthread_attr_init(&attr);!
pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);!
!
for(t=0; t<NUM_THREADS; t++) {!
printf("Main: creating thread %ldn", t);!
rc = pthread_create(&thread[t], &attr, BusyWork, (void *)t); !
if (rc) {!
printf("ERROR; return code from pthread_create() is %dn", rc);!
exit(-1);}}!
!
pthread_attr_destroy(&attr);!
for(t=0; t<NUM_THREADS; t++) {!
rc = pthread_join(thread[t], &status);!
if (rc) {!
printf("ERROR; return code from pthread_join() is %dn", rc);!
exit(-1); }!
printf("Main: completed join with thread %ld having a status of %ldn",t,(long)status);}!
!
printf("Main: program completed. Exiting.n");!
pthread_exit(NULL); }

POSIX Pthreads
27
• pthread_mutex_init()
• Initialize new mutex, which is unlocked by default

• pthread_mutex_lock(), pthread_mutex_trylock()
• Blocking / non-blocking wait for a mutex lock

• pthread_mutex_unlock()
• Operating system scheduling decides about wake-up preference

• Focus on speed of operation, no deadlock or starvation protection mechanism
int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_trylock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);

Windows vs. POSIX Synchronization
28
Windows POSIX
WaitForSingleObject pthread_mutex_lock()
WaitForSingleObject(timeout==0) pthread_mutex_trylock()
Auto-reset events Condition variables

Spinlocks
29
Processor'B'Processor'A'
do#
####acquire_spinlock(DPC)#
un6l#(SUCCESS)#
#
begin#
####remove#DPC#from#queue#
end#
#
release_spinlock(DPC)#
do#
####acquire_spinlock(DPC)#
un6l#(SUCCESS)#
#
begin#
####remove#DPC#from#queue#
end#
#
release_spinlock(DPC)#
.#
.#
.#
.#
.#
.#
Cri6cal#sec6on#
spinlock#
DPC# DPC#

Spinlocks
30
Try$to$acquire$spinlock:$
Test,$set,$was$set,$loop$
Test,$set,$WAS$CLEAR$
(got$the$spinlock!)$
Begin$updaCng$data$
Try$to$acquire$spinlock:$
Test,$set,$WAS$CLEAR$
(got$the$spinlock!)$
Begin$updaCng$data$
$that’s$protected$by$the$
$spinlock$
$
$
(done$with$update)$
Release$the$spinlock:$
Clear$the$spinlock$bit$
$
CPU$1$ CPU$2$

Windows: Queued Spinlocks
• Problem: Checking status of spinlock via test-and-set creates bus contention
• Idea of queued spinlocks:

• Each spinlock maintain a queue of waiting processors

• First processor acquires the lock directly

• Other processors are added to the queue and spin on a local wait bit

• On release, the according processor resets the wait bit of the next CPU in queue

• Exactly one processor is being signaled

• Pre-determined wait order

• Result: Busy-wait loops of all CPUs require  
no access to main memory

• (Check reading list for details)
31

Linux: Spinlocks
• Common critical section strategy in the Linux kernel

• Uniprocessor system with disabled kernel preemption:

• Kernel threads are never interrupted, so locks are deleted at compile time

• Uniprocessor system with enabled kernel preemption:

• Spinlock code is replaced with disabling / enabling of interrupts

• Multiprocessor system

• Spinlock code compiled into monolithic kernel

• Additional support for reader-writer spinlocks, which favor the reader

• Similar API for portability
32

Linux: Spinlocks
33
• void spin_lock_init(spinlock_t *lock):  
Initializes given spinlock
• void spin_lock(spinlock_t *lock):  
Acquires the speciﬁed lock, spinning if needed until it is available

• void spin_lock_irq(spinlock_t *lock):  
Like spin_lock(), but also disables interrupts on the local processor

• Necessary when the critical section data may be accessed by an interrupt handler

• int spin_trylock(spinlock_t *lock):  
Tries to acquire speciﬁed lock; returns nonzero if lock is currently held and zero otherwise

• int spin_is_locked(spinlock_t *lock):  
Returns nonzero if lock is currently held and zero otherwise

• void spin_unlock(spinlock_t *lock):  
Releases given lock

• void spin_unlock_irq(spinlock_t *lock):  
Releases given lock and enables local interrupts

Operating Systems 1 (8/12) - Concurrency

Recommended

More Related Content

What's hot (20)

Similar to Operating Systems 1 (8/12) - Concurrency (20)

More from Peter Tröger (20)

Recently uploaded (20)

Operating Systems 1 (8/12) - Concurrency