EEE8068: Concurrent Programming
Dr. Bystrov
School of Electrical Electronic and Computer Engineering Newcastle University
EEE8068: Concurrent Programming – p. 1/29
Copyright By PowCoder代写 加微信 powcoder
Schedulers – Embedded OS
EEE8068: Concurrent Programming – p. 2/29
Concurrent programming
Concept Modelling Examples
Threads (underlined topics examined)
Concept Modelling Examples
Shared data
Condition variables Semaphores
EEE8068: Concurrent Programming – p. 3/29
Concurrent programming – baseline
The baseline idea is very simple:
CPU switches fast between the concurrent activities (tasks, threads or processes)
mechanisms and libraries for task control means for data communication
means of protecting the shared data from access conflicts
The details are not simple and need to be discussed…
EEE8068: Concurrent Programming – p. 4/29
operator “;”
shell script examples:
Process as an instance of the executed program.
The same program can be started several times before any instance of it finishes.
serial or sequential execution
ls ; ls ../
echo “process_1” ; echo “process_2”
Parallel (concurrent) execution operator “&”
(sleep 1; echo “proc_1”) & echo “proc_2” &
EEE8068: Concurrent Programming – p. 5/29
Fork-join example
EEE8068: Concurrent Programming – p. 6/29
to finish;
exit – stops the process.
Processes in C
fork – creates a new child process, the exact copy of the parent process;
exec – replaces the task of the process by overwriting it; wait – primitive synchronisation by waiting for the process
fork + exec – creates a new process, different from the parent.
EEE8068: Concurrent Programming – p. 7/29
print (“One”);
pid=fork(); print(“Two”);
AB print (“One”);
print (“One”); pid=fork(); print(“Two”); PC
pid=fork(); print(“Two”); PC
Before After
EEE8068: Concurrent Programming – p. 8/29
print (“One”);
execl(“/bin/ls”); print(“Two”);
/*1st line of ls*/
Before After
EEE8068: Concurrent Programming – p. 9/29
EEE8068: Concurrent Programming – p. 10/29
Read YoLinux Tutorial: POSIX thread (pthread) libraries http://www.yolinux.com/TUTORIALS/LinuxTutorialPosixThreads.html
The POSIX threads standard API for C/C++. Spawning a concurrent process flow.
Most effective on multiprocessor systems;
gaining speed through parallel processing.
Less overhead than “forking” or spawning a new process
the system does not initialise a new system virtual memory space and environment
threads within a process share the same address space.
EEE8068: Concurrent Programming – p. 11/29
Thread operations include
data management and process interaction.
Thread Basics
thread creation,
termination,
synchronisation (joins,blocking), scheduling,
A thread does not maintain a list of created threads, nor does it know the thread that created it.
pthread functions return “0” if OK.
EEE8068: Concurrent Programming – p. 12/29
Threads in the same process share: address space;
process instructions;
most data;
open files (descriptors); signals and signal handlers; current working directory; user and group id.
Threads share
Exiting the process ends all its threads!
EEE8068: Concurrent Programming – p. 13/29
Each thread has a unique: thread ID;
Threads don’t share
set of registers, stack pointer;
stack for local variables, return addresses; signal mask;
return value: errno .
#include
pthread_attr_t * attr,
void * (*start_routine)(void *),
void * arg);
EEE8068: Concurrent Programming – p. 14/29
Thread joining
#include
void **thread_return);
pthread_join suspends the execution of the calling thread until the thread identified by th terminates, either by calling pthread_exit or by being cancelled.
The joined thread th must be in the joinable state: it must not have been detached.
pthread_join must be called once for each joinable thread created to avoid memory leaks.
At most one thread can wait for the termination of a given thread.
EEE8068: Concurrent Programming – p. 15/29
Fork-join example
EEE8068: Concurrent Programming – p. 16/29
Thread synchronisation
The threads library provides three synchronisation mechanisms (we focus on the first two):
join – Make a thread wait until others are completed (illustrated earlier).
mutex – Mutual exclusion lock: Block access to variables by other threads. This enforces exclusive access by a thread to a variable or set of variables.
conditionvariables –datatypepthread_cond_t
EEE8068: Concurrent Programming – p. 17/29
are used to prevent data inconsistencies due to race conditions.
A race condition often occurs when two or more threads need to perform operations on the same memory area, but the results of computations depends on the order in which these operations are performed.
Mutexes are used for serialising shared resources.
Anytime a global resource is accessed by more than one thread the resource should have a Mutex associated with it.
One can apply a mutex to protect a segment of memory (“critical region”) from other threads.
EEE8068: Concurrent Programming – p. 18/29
Mutex example
EEE8068: Concurrent Programming – p. 19/29
Modelling a thread or a process
a place may lose a token only after its successor becomes enabled (remember the JOIN structure!!!);
threads/processes finish when they “want”, but
it is still possible to make the successor process wait for some concurrent process to finish. . .
2 phases: a critical section and pending. start finish
critical section pending
EEE8068: Concurrent Programming – p. 20/29
Construct a PN model
Fork-join example programme above Mutex example programme above
EEE8068: Concurrent Programming – p. 21/29
Experiments on fairness
Run two threads with the following thread function. Distinguish between them by passing them different parameters.
Output: 11111111112222222222 Uncomment the delay.
Output: 12121212121212121212
EEE8068: Concurrent Programming – p. 22/29
Condition variables
A condition variable is used with the appropriate functions for waiting and later, process continuation.
A condition variable must always be associated with a mutex.
A deadlock when one thread is preparing to wait and another thread signals the condition. The thread will be perpetually waiting for a signal that is never sent.
Any mutex can be used, there is no explicit link between the mutex and the condition variable.
EEE8068: Concurrent Programming – p. 23/29
Functions used with condition variables
Creating/Destroying:
pthread_cond_init
pthread_cond_t cond =
PTHREAD_COND_INITIALIZER;
pthread_cond_destroy
Waiting on condition:
pthread_cond_wait pthread_cond_timedwait – bloking time limit
Waking thread based on condition:
pthread_cond_signal
pthread_cond_broadcast – wake up all threads blocked by the condition variable.
EEE8068: Concurrent Programming – p. 24/29
Condition wait example
EEE8068: Concurrent Programming – p. 25/29
mutex_lock
mutex_lock
mutex_unlock
mutex_unlock
Condition wait model
* cond_signal
EEE8068: Concurrent Programming – p. 26/29
Semaphore operations:
Semaphores
Built upon mutexes and condition variables.
An integer value is associated with a semaphore.
semaphore_init – create a semaphore with value 1
semaphore_up – increments the semaphore
semaphore_down – blocks if its value ≤ 0, decrements the semaphore value
semaphore_decrement – decrements without blocking
semaphore_destroy – destroys a semaphore
EEE8068: Concurrent Programming – p. 27/29
Semaphore example
EEE8068: Concurrent Programming – p. 28/29
Conclusions
We are now familiar with the basic concepts of concurrent programming
The schedulers implement the mechanism of concurrency – we have started this topic and the following 4 hours of seminars will be dedicated to it.
Fork-join, choice-merge, arbitration when accessing common resource
Two types of dependency between threads/processes
imposed by start-termination control imposed by data communication
Modelling concurrent computations with Petri nets Interesting effects – fairness
EEE8068: Concurrent Programming – p. 29/29
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com