Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Parallell computing > Chapter 4 - Pthreads > Flashcards

Chapter 4 - Pthreads Flashcards

1
Q

What is a shared memory, from the programmers point of view?

A

All cores can access all the memory locations.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is a critical section?

A

The code that updates a shared resource, that can only be updated by one thread at a time.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What are threads?

A

An instance of a program running on a processor. (In MPI this is called a process)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Draw a shared-memory system.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Why is a thread a “lighter-weight” process?

A

It contains just an instance of the running program, not the additional components (memory, descriptors, etc.).

They do have their own stack and local variables

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What does a process consist of?

A

A process is an instance of a running program.

Stack- and heap memory

Descriptors of resources allocated for process (stdin, stdout)

Security info

State info (ready, waiting, register contents, …)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are POSIX threads?

A

Standard for unix-like OS’es

It specifies an API for multithreaded programming.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How are pthread files compiled?

A

Like normal C files
Might need to link pthread library

gcc -o hello hello.c -lpthread

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the pthread header file?

A

include <pthread.h></pthread.h>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What are global variables in thread-programs?

A

Variables that are shared between all threads.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

How are threads started in pthread programs?

A

Threads are started by the program executable - meaning code needs tostart the threads itself.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is the datastructure of threads?

A

pthread_t

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What function is used to start threads?

A

pthread_create(
pthread_t* thread,
const pthread_attr_r* attr,
void* (start_routine)(void),
void* args_p
)

attr: Can pass NULL
start_routine: The function to be run by the thread
args_p: arguments to pass to the function being run, thread rank is often passed here.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

How should functions being run by threads be declared?

A

void* thread_function(void* args_p)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Give an example of how threads can be created and how their rank is passed to them

A

int rank=0;

pthread_t thread = malloc(sizeof pthread_t);

pthread_create(&thread, NULL, &func, (void*) rank)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What kind of parallelism is most often used with pthreads?

A

SIMD, but there is no technical reason for threads only to run the same programs. It just is most often done.

Threads still do thread-branching within a thread.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is a main thread?

A

Thread that runs the main-function

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Does threads need to return something?

A

They do not need to return something useful, but because pthread_create have the return type(void*), the thread should return something. This can be NULL

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

How is threads stopped?

A

pthread_join(
thread_t* t,
void** ret_val
)

When join is called by main thread, the program will wait until the corresponding thread has completed.

Join also frees the resources associated with the thread.

ret_val: Used to retrieve return value

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What are zombie threads?

A

Threads that are never joined, and their resources never freed. These wastes resources

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What does pthread_detach do?

A

Used when a program does not need to wait for a thread to finish.

The function call indicates to the htread that its resources should be freed upon termination.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

How can error checking be done using pthreads?

A

The pthread_create function have several return values that indicate different errors

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is a thread pool?

A

The main threads start all threads it think it will be needing, at the beginning of the program.

The threads sit idle when they finish their work, instead of terminating. When a new requests comes, an idle thread can respond to it.

This reduces thread-creation overhead

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is a race condition?

A

When multiple threads access the same shared memory, and at least one thread execute an update, the result may be unpredictable and we can get errors.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

How can we ensure that a critical section is only entered by one thread at the time?

A

Flag + busy waiting: Can e.g. keep value of rank that is allowed in critical section

mutexes

semaphores

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is busy-waiting?

A

A thread repeatedly tests a condition, but does not do any useful work until the condition has been met.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

How can busy-waiting be coded?

A

while(flag != my_rank);

No loop body

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Is there a situation where using while loops to busy work might not work?

A

If a compiler optimizes the code and changes the order of instructions in a way that the critical section is executed before the while-loop checks the condition.

If while loops are used to busy wait, compiler optimizations should be turned off. The compiler does not know about multiple threads being used.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

What is a spinlock?

A

When a thread is spinning on the while-loop condition, eating up CPU resources.
This can happen if the thread that is currently accessing the critical section gets preempted by the CPU and thereby delayed.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Why is busy-waiting not optimal for performance?

A

Can get spinlocks

Turning off compiler optimizations can hurt performance alot.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Howcan serial execution be faster than using multiple threads and busy-waiting?

A

Thread creation/joining has overhead. This is not the main factor though.

When using busy waiting, all the threads are alternating between execution and waiting. This can increase the run time alot.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

Why does critical sections reduce performance?

A

Because execution must effectively be serialized in critical sections.

To increase performance, we should try to minimize the number of times a critical section is entered.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

What is a mutex?

A

Mutual exclusion

Guarantees exclusive access to critical section.

A data type consisting of a variable and a couple functions used to achieve this.

pthread_mutex_t

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

How is a mutex created?

A

int pthread_mutex_init(
pthread_mutex_t* m,
const pthread_mutexattr_t* attr
)

Attr: Can be NULL

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

What is a static mutex initialization?

A

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER

easier initialization method, fine in many cases

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

What is pthread_mutex_destroy?

A

Method called when a program finishes using a mutex

pthread_mutex_destroy(
pthread_mutex_t* m
)

37
Q

How are mutexes used to access critical sections

A

A thread will lock the mutex

A thread will do the work

A thread unlocks the mutex

38
Q

What is pthread_mutex_lock?

A

pthread_mutex_lock(
pthread_mutex_t* m
)

used by threads to lock a mutex

Causes the thread to lock until the critical section is clear.

39
Q

What is pthread_mutex_unlock

A

pthread_mutex_unlock(
pthread_mutex_t* m
)

Used by threads to unlock mutexes

Notifies system that the thread has left the critical section.

40
Q

What is a difference between busy-waiting and using mutexes?

A

Busy-waiting requires specific conditions, for example specifies what rank can execute the section.

The order of which mutexes are required can be random. Nothing specifies rank. Accesses are scheduled by the system. Not necessarily in the order they called lock().

41
Q

What is a property that can be useful with busy-waiting?

A

We know the order in which threads will complete the critical section.

42
Q

What are semaphores?

A

Special type of unsigned int.

43
Q

What is a binary semaphore?

A

A semaphore that only take on the values 0 and 1

0: Corresponds to locked mutex
1: Correspond to unlocked

44
Q

How do you use a binary semaphore as a mutex?

A

Initialize semaphore to 1

Before critical section: sem_wait

After critical section: sem_post

45
Q

What does sem_wait do?

A

If semaphore is non-zero, it gets decremented

If semaphore is 0, thread waits until it is not

46
Q

What does sem_post do?

A

Increments semaphore

47
Q

What is the difference between a semaphore and a mutex?

A

There is no owner of a semaphore

48
Q

How are semaphores initialized?

A

int sem_init(
tem_t* s,
int shared,
unsigned init_val
)

shared: Whether semaphore shall be shared between threads or processes.

if we pass constant 0: shared amongst threasds

49
Q

What does sem_destroy do?

A

int sem_destroy(sem_t* semaphore)

50
Q

What header file does semaphores need?

A

include <semaphore.h></semaphore.h>

51
Q

What is producer-consumer synchronization?

A

When one thread cannot proceed until another has finished some work.

Does not necessarily mean involving a critical section.

52
Q

In what situations can counting semaphores be useful (more values than binary)

A

For example when we want to restrict the amounts of resources used.

If we only have 4 cores, we can create a semaphore that allows creating maximum 4 threads. This is an alternative to thread pooling.

53
Q

What is a barrier?

A

A point of synchronization to make sure all threads are at the same place in the program.

No process can proceed without everyone having reached it.

54
Q

When can barriers be useful?

A

Debugging

When timing an application. Synchronize all threads and then start timer. Use the longest time

55
Q

How can a barrier be implemented using a mutex and busy-waiting?

A

Use a shared counter protected by mutex.

When counter equals number of threads - threads can leave busy wait loop

while(counter < thread_count);

56
Q

What are the downsides of using mutex+busy wait to create barriers?

A

Wastes CPU resources.
If more threads than cores - can significantly reduce performance.

If we cant to reuse the counter to create a second barrier, resetting it to 0 will most likely lead to some threads getting stuck in the first while loop.

This means we need one counter for each barrier

57
Q

How can barriers be created using semaphores?

A

Counter to indicate how many threads are in the barrier.

2 semaphores:
- count_sem: protects counter
- barrier_sem: blocks threads that have entered barrier

count_sem is initialized to 1

When a thread has access to the counter - it checks if it is less than thread_count, and possibly increments it, and releases lock (sem_post(&count_sem))

Then it proceeds to block in sem_wait(&barrier_sem)

If the counter is n_thread - 1, the thread is the last to enter barrier. So it can reset the counter to 0 and unlock count_sem calling sem_post(&count_sem). To notify all other threads that they can proceed, it calls sem_post(&barrier_sem) for each thread that are blocked in sem_wait(&barrier_sem).

58
Q

What pros has semaphores to mutexes when implementing barriers

A

Does not cause CPU cycles to be wasted.

Counter can be reused because it is reset before other threads are released.

count_sem can be reused because it too gets reset

barrier_sem cannot be reused

59
Q

What is the code to create barriers using semaphores

A

int counter; // init to 0
sem_t count_sem; // init to 1
sem_t barrier_sem; // init to 0

void* thread_func() {
…

sem_wait(&count_sem);
if(counter === n_threads - 1){
     counter = 0; // Reset counter
     sem_post(&count_sem); // This is the last thread to call post on this semaphore, meaning it gets reset to 0

    for(int j = 0; j < n_thread - 1; j++) {
            sem_post(&barrier_sem);
    }
} else {
    counter++;
    sem_post(&count_sem);
    sem_wait(&barrier_sem);
} }
60
Q

What are condition variables?

A

A data object that allows a thread to suspend execution until a certain event or condition occurs.

When this event occurs, another thread can signal the thread to “wake up”.

A condition variable is always associated with a mutex.

61
Q

What is the pseudo code of a construct where condition variables are used?

A

int mutex;
if condition
signal threads()
else
unlock mutex and block
unlock mutex

62
Q

What does pthread_cond_signal do?

A

pthread_cond_signal(
pthread_cond_t *c
)

unblocks one of the blocking threads

63
Q

What does pthread_cond_broadcast do?

A

pthread_cond_broadcast(
pthread_cond_t* c
)

unblocks all waiting threads

Semaphores would need a for-loop for this

64
Q

What does pthread_cond_wait do?

A

pthread_cond_wait(
pthread_cond_t* c,
pthread_mutex_t m
)

unlocks the mutex and cause executing thread to block until someone else calls signal/broadcast.

65
Q

What happens when a thread is unblocked when using condition variables?

A

It reaquires the mutex.

66
Q

What instructions does pthread_cond_wait in effect implement?

A

pthread_mutex_unlock(&m)
wait_on_signal(&c)
pthread_mutex_lock(&m)

67
Q

What is the code to implement barriers using condition variables?

A

int counter = 0;
pthread_mutex_t m;
pthread_cond_t c;

void func(){
pthread_mutex_lock(&m)
counter++;

 if(counter == n){
      counter = 0;
      pthread_cond_broadcast(&c)
 } else {
      while(pthread_cond_wait(&c, &m) != 0)
 }
 pthread_mutex_unlock(&m);

}

wait() needs to be in a while loop because of spurious wake-up

68
Q

What is a spurious wake-up?

A

When events other than cond_signal/cond_broadcast wakes up a thread.

69
Q

How are cond variables initialized?

A

pthread_cond_init(
pthread_cond_t* c,
const pthread_condattr_t* a
)

70
Q

How are cond variables destroyed?

A

pthread_cond_destroy(
pthread_cond_t* c
)

71
Q

How can cond variables be initialized with default attributes?

A

pthread_cond_t c = PTHREAD_COND_INITIALIZER

72
Q

When is conditional variables preferable to semaphores?

A

When protected application state cannot be represented by an unsigned integer counter

73
Q

What are read-write locks?

A

Provides 2 lock functions.

1: Lock for reading: Allows multiple threads to obtain the lock for reading

2: Lock for writing: Only one thread can obtain the lock when writing.

If a thread want to write, but other threads have read-lock. It blocks

If one thread has write block, and other want read/write-lock, they wait

74
Q

What are the read-write lock functions syntax?

A

pthread_rwlock_init(
pthread_rwlock_t* l,
cont pthread_rwlockattr_t* attr
)

pthread_rwlock_rdlock(
pthread_rwlock_t* l
)

pthread_rwlock_wrlock(
pthread_rwlock_t* l
)

pthread_rwlock_unlock(
pthread_rwlock_t* l
)

pthread_rwlock_destroy(
pthread_rwlock_t* l
)

75
Q

What is the syntax of static init of rw-locks?

A

pthread_rwlock_t lock = PTHREAD_RWLOCK_INITIALIZER

76
Q

What are the implemented functionality of read-write locks?

A

Data structure of 2 cond. variables, (readers/writers), and a mutex. The structure also include members that indicates:

How many readers own the lock (currently reading)

How many readers are waiting to obtain the lock

Whether a writer owns the lock

How many writers are waiting

77
Q

How does the read-write lock functionality work?

A
78
Q

What is the cache coherence problem?

A

If two threads access the same data, one then updates it, and then the next reads it. What value does the second read?

There are 3 possible versions of the variable now, the one in main memory, the one in thread 1 and the one in thread 2.

For the second thread to know the value it has in cache is updated, and therefor invalid, we need to implement invalid bits and policies for memory updates.

Cache coherence can have big performance consequences for multithreaded systems.

79
Q

What is false sharing?

A

Two threads with separate caches access different variables that are stored within the same cache line.

If one of the threads update their value, the whole cache line will be invalid.

The other thread needs to fetch the cache line from memory, even though it is not using the same variable.

Threads aren’t sharing a variable, but the behaviour of the threads are as if they were.

80
Q

When is a block of code thread safe?

A

When it can be executed by multiple threads without causing problems.

81
Q

What is oversubscription?

A

Running more threads/processes than available cores

82
Q

What resources does a thread have access to?

A

Its own stack and local variables

Shared heap and data segment

83
Q

What is the PRAM model?

A

proposes 4 policies on how to handle multiple threads accessing/writing to shared resources

Common value: allows execution if all assign same value

Arbitrary value: Assigns the value from one of the attempts, can be any of them

Priority: Each thread have ranking, highest ranked assignment writes to value

Reduction: A commutative operation is applied to all attempts, result is stored

84
Q

What flag is added when compiling pthread programs?

A

-pthread

85
Q

What does void in func_name(void) mean?

A

Exactly zero arguments

86
Q

What are atomic instructions?

A

Instructions wired into the CPU and interconnect fabric, in a way that they cannot be interrupted

87
Q

What is pthread_barrier_t

A

Behaves like broadcast barrier

pthread_barrier_init(&var, NULL)

pthread_barrier_destroy(&var)

pthread_barrier_wait(&var)
- When every thread reaches wait, var is reset, and threads are resumed

88
Q

What needs to be included in the file to use pthread barriers?

A

define _GNU_SOURCE before

#include <pthread.h></pthread.h>

Parallell computing (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions