Skip to main content

C Introductory threading notes

Threads

Compiling threads-
<pthread.h>
clang -pthread x.c

Thread functions
1. int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
 void *(*start_routine) (void*), void* arg);

EXAMPLE :
pthread_create (&threads[i], NULL, thread_function, NULL);

Starts a new thread while calling, starts execution by invoking start_routine()
Arg is passed as sole argument of start_routine
Terminates via
1. pthread_exit
2. Returns from start_routine, equivalent to calling pthread_exit
3. pthread_cancel
4. Threads call exit(), or main returned, this calls termination of all threads in process
If attr is NULL, thread is created with default attributes
Else, it points to a structure whose contents are used at thread creation time to determine attributes to new thread
Successful call stores ID of new thread in buffer pointed to by thread, used to refer to thread in subsequent calls to other pthreads functions
Successful call returns 0, on error returns error number, threads contents are undefined

2. int pthread_join(pthread_t thread, void ** retval)
EXAMPLE:
pthread_join(threads[x],NULL)
Awaits for the thread specified by thread to terminate and then return
Specified thread must be joinable
If retval not NULL, then pthread_join copies exit status of target thread into location pointed by retval
If thread canceled, PTHREAD_CANCELED is placed in location pointed to by retval
If multiple thread simultaneously try to join with same thread, results undefined
If the thread calling pthread_join is canceled, target thread will remain joinable
Returns upon success, else returns error number
Race condition: multiple threads read and write a shared data item and final result depends on relative timing (which ends later)
Critical section: two or more code parts that access and manipulate shared data (shared resource)
To prevent races, avoid 2 threads concurrently execute within critical section(mutual exclusion)
Syncronize: to make things happen at the same time

Mutexes
Tran.互斥体
Used to syncronize access to shared global variables (shared between threads)

EXAMPLE:
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

for()
pthread_mutex_lock(&lock);
//critical section
pthread_mutex_unlock(&lock);

Before threads enter critical section, mutex locked
When thread leaves, unlocks mutex
Mutex ensures one thread is allowed into critical section at once
All other threads have to wait until critical section is free

The first line was a static declaration, standard way of doing so
Mutexes have attributes, initially free (unlocked)
When locked, other threads that call pthread_mutex_lock are blocked
But will not return before calling thread was given lock
Kept in waiting queue, have to wait until cs unlocked
No fairness is guaranteed by pthread library

pthread_mutex_trylock(lock)

Attempts to acquire lock, if lock not free, returns immediately
If free, calling thread acquires
On success returns 0

If thread unlocking other threads mutex, undefined behavior, only unlock if success call

pthread_mutex_t can be used to dynamically create mutexes
pthread_mutex_init used to initialize
EXAMPLE:
lock = (pthread_mutex_t) malloc (sizeof(pthread_mutex_t);
pthread_mutex)_init(lock,NULL)
NULL uses default settings
pthread_mutex_destroy() destroys mutex, memory must be freed after destroy


Monitor
ADT + Synchronization
Hiding variable from direct access by the programmer
Access via functions
Locking responsibility now shifted from user of variable to maintainer of variable

Serialization
All other threads waiting until critical section becomes free
Threads execute critical section one after the other, no parallelism
Unshared data can be placed outside critical section to reduce serialization, more parallelism

Multiple mutexes
Threads may have to acquire more than one mutex
Eg. Splitting counter value between node S and its predecessor P
Both nodes have to be locked - else race

Splitting in pseudo //int ctr for counter
1- lock(pPtr->lock)
2- lock(sPtr->lock)
3- pPtr->ctr += sPtr->ctr/2
4- sPtr->ctr += sPtr->ctr/2
5- unlock(pPtr->lock)
6- unlock(sPtr->lock)

Deadlock
Each thread is waiting for resources, but all resources are held to system locks, no progress possible

Self-deadlock: thread attempting to acquire mutex it already has
EXAMPLE:
pthread_mutex_lock(&lock)
pthread_mutex_lock(&lock) //executing twice

Code above would wait for lock to be available again

ABBA-Deadlock
2 threads attempting to acquire A and B, t1 gets in order A->B, t2 in order B->A

Multiple mutexes must always be obtained in same order
Or else may deadlock

Conditions for deadlock
Mutual exclusion
Resource assigned to at most one thread
Eg. One chopstick is a resource, assigned to at most one person at a time
Hold and wait
Threads both hold resources and request other resources
Eg. Person holds left chopstick, wants right chopstick
No preemption
Resource only be released by thread that holds it
Eg. No way of forcibly taking chopstick away from person
Circular wait
Cycle exists in which each thread waits for a resource that is assigned to another thread


Preventing deadlock
Prevent cycles via locking hierarchy
1. Impose ordering on mutexes
a) One thread acquiring that mutex at a time, others blocked
b) Blocked thread only continues when other mutexes released
c) can use waiting between threads or splitting of subsets
2. Require all threads acquire mutexes in same order

Need to know what mutexes are needed for thread
Order of unlock is not important
If infinite loop entered, thread will also stop and wait forever even with locking hierarchy
Ps may be ignored depending on algorithm, pick up the smaller index then the higher for complete cycle

Synchronization via locks - lock based synchronization

Lock contention: lock currently in use, another thread attempts to acquire
If lock is highly contended, many threads waits to for acquiring
Locks serialize activities, highly contended lock limits parallelism
Scalability: measurement of how well system can be expanded (?)
Highly contended lock limits scalability
Worst to Better
Coarse-grained lock  ----  Medium grained lock ---  Fine grained lock



Barrier
A synchronization point which a certain number of threads must arrive before any participating thread can continue
Participating threads call pthread_barrier_wait()
Threads block until specified number of threads called pthread_barrier_wait()

int pthread_barrier_init(barrier* bar, const barrier attribute, unsigned count)
NULL for default attributes
Count specifies number of threads needed to open the barrier

int pthread_barrier_wait(barrier* bar)

int pthread_barrier_destroy(barrier* bar)

Semaphores
sem_t s;
Non negative integer synchronization variables
--sem_wait(&s);
--sem_post(&s);
--sem_init(&s,0,1);
Basic operations on semaphore s
P(s): [while(s==0) wait();
s--;] //只要s还是0,等待成为非0,非0后减一

--A thread has to wait until value of s is greater than 0, then s is decremented by 1 and thread is allowed to continue execution

V(s): [s++;] //s加一

--increment s

Guaranteed the statements between brackets are executed indivisibly
Statements between brackets are atomic operation
-at any time, only one of P or V can modify s
Semaphore variant: (s>=0)

Can be used to synchronize threads

Semaphore vs Mutexes
- Mutex provides mutual exclusion similar to binary semaphore (semaphore init = 1)
-one thread at a time to execute critical section
-Mutexes are less flexible than semaphores
-locked mutex has owner, semaphores dont
-mutex initially unlocked, semaphore can be anything including 0 (to say locked)
-mutex can assume 2 states, unlocked and locked, can be represented by 1 bit
-semaphore is a counter


Consumer & producer
Consumer waits for producer to give data to queue, vice versa
Only consume when queue is not null
Only give data when not full

Comments

Popular posts from this blog

Understanding database [9] : Choosing indexes

Understanding database 9 : Choosing indexes When choosing indexes, we choose the best plan that suits for the queries, and look for additional indexes that may potentially upgrade upon that. Before creating, we must also consider the impact on updates in the workload, such that indexes take disk space. For a query, the WHERE clause are the main focus point to make indexes on, where exact matches suggest a hash index and range queries suggest a tree index. Clustering is extremely helpful when it comes to range queries, and may also help with equality queries if there are duplicates. Search keys with multiple attribute should be considered if a WHERE clause contains multiple conditions, and the order of attributes is important for range queries. Searching may become ‘index-only’ with such indexes.

Understanding database [6] : Clustered Index

A clustered index is what is good for a range search over a range of search key values, and the index entries and the rows are ordered the same way, which is different from unclustered indexes (secondary indexes). To use a clustered index, we use the index to locate the first index entry at the start of the range, which where the first row is located at. If the index is clustered, subsequent rows will be stored in successive locations with the ordering , therefore it may minimize the page transfers and maximizes cache hits. For one table, there may only be one clustered index, whereas there can be as many unclustered indexes as you may want  to create. Unclustered indexes aren ’ t as good as clustered, but they might become necessary when it comes to finding for other attributes apart from the primary key. Smaller topics : Dense index & Sparse index When we say sparse index, we mean that there is an index entry for each page of the data file. With this structuring