threads

Question 1

Thread Motivation

Answer 1

• Processes are expensive to create and maintain
  – Context switch overhead between processes
  – Process synchronization cumbersome
  – Communication between processes must be done through an external structure
• Files
• Pipes
• Sockets
• Shared memory

Question 2

Processes and Threads

Answer 2

• Process considered to be heavyweight
  – Ownership of memory, files, other resources
• Threads
  – A thread can be seen as lightweight process
  – A unit of execution associated with a particular process, using many of the process’ resources
  – Multithreading
• Allowing multiple threads per process
  – Benefits of multithreading
• Responsiveness (minimize time, concurrency)
• Resource sharing (i.e., shared memory)
• Economy (creation, switch)
• Scalability (explore multi-core CPUs)

Question 3

Process Properties

Answer 3

• Each process has its own:
  – Program Counter (PC)
  – Stack
  – Stack Pointer (SP)
  – Address space
• Processes may share:
  – Open files
  – Pipes

Question 4

Thread View

Answer 4

• Operating System Perspective
  – An independent stream of instructions that can be scheduled to be run by the OS
• Programmer Perspective
  – Can be seen just as a “function” that executes independently from the main program
  – A single stream of instructions in a program
• Multiple threads can share a process
  – Multiple flows of control within a process
  – Share code and data space of process
  – Lower overhead, avoid context switches

Question 5

Thread Execution Environment

Answer 5

The process is the execution environment for a family of threads
– A group of threads share the same resources (files, memory space, etc.)
* Since threads are associated with their process, they are able to use the resources belonging to the process and duplicate only the required resources, such as the PC, stack, and SP, needed by the OS to schedule threads independently from their processes

– This makes creating and switching between threads belonging to same process very simple and much more efficient than creating or switching between processes
* Although switching for threads belonging to different processes is still as complex as classic process switch

Question 6

Thread Properties

Answer 6

• Each thread has its own:
  – Program Counter (PC)
  – Stack
  – Stack Pointer (SP)
  – Registers
  – Scheduling properties
  – Set of pending/blocked signals
  – Thread specific data
• Threads share:
  – Address space
• Variables
• Code
  – Open files

Since a thread exists within a process, if a process terminates, so does the thread

Question 7

Thread Consequences

Answer 7

• Since threads within the same process share resources
• Changes made by one thread to shared system resources (such as closing a file) will be seen by all other threads
  – Any files opened inside a thread will remain open (unless explicitly closed) even after the thread is terminated
• Two pointers having the same value point to the same data
• Reading and writing to the same memory locations is possible
  – Therefore requires explicit synchronization by the programme

Question 8

POSIX Threads

Answer 8

• The most commonly used thread package on Linux is POSIX threads (also known as pthreads)
  – Standards-based API to create, manage, and synchronize threads
• Thread package includes library calls for
  – Thread management (creation, destruction)
  – Mutual exclusion (synchronization, short-term locking)
  – Condition variables (waiting on events of unbounded duration)
• A run-time system manages threads in a transparent manner so that the user is unaware
  – Robust programs should not depend upon threads executing in a specific order

Question 9

The pthreads Library

Answer 9

The pthread.h library includes the following operations:
– pthread_create create a new thread
– pthread_detach detach a thread, to release its resources when thread terminates
– pthread_exit terminate calling thread, without terminating process
– pthread_join wait for a specified thread to terminate
– pthread_equal compare thread IDs
– pthread_kill send a specified signal to a thread
– pthread_self obtain the ID of the calling thread

Question 10

Creating Threads

Answer 10

int pthread_create(pthread_t tid, const pthread_attr_t tattr, void (start_routine)(void *), void *arg);
– tid: an unsigned long integer that indicates a thread’s id
– tattr: attributes of the thread – usually NULL
– start_routine: the name of the function the thread starts executing
– arg: the argument to be passed to the start routine – only one

• pthread_create( tid, NULL, void (*start_routine), void *arg);
• After this function gets executed, a new thread has been created and is executing the function indicated by start_routine
• Once created, threads are peers, and may create other threads
• There is no implied hierarchy or dependency between threads

Question 11

Joining Threads

Answer 11

Joining is one way to accomplish synchronization between threads where the process waits for all threads to complete
– We call the function pthread_join() once for each thread

Question 12

Wait for Completion of a Thread

Answer 12

int pthread_join(thread_t tid, void **status);
– tid: identification of the thread to wait for
– status: the exit status of the terminating thread – can be NULL

• The process that calls this pthread_join function blocks its own execution until the thread indicated by tid terminates its execution
  – Finishes the function it started with, or
  – Issues a pthread_exit() command

Question 13

Exiting a Thread

Answer 13

• pthreads exist in user space and are seen by the kernel as a single process
  – If one issues an exit() system call, all the threads are terminated by the OS
  – If the main() function exits, all of the other threads are terminated
• To have a thread exit, use pthread_exit()

void pthread_exit(void *status);
– status: the exit status of the thread – passed to the status variable in the pthread_join() function of a thread waiting for this one

Question 14

Detaching a Thread

Answer 14

• Indicates that system resources for the specified thread should be reclaimed when thread ends
  – If the thread has already ended, resources are reclaimed immediately
  – This routine does not cause the thread to end!
• Threads are detached
  – After a pthread_detach() call
  – After a pthread_join() call
  – If a thread terminates and PTHREAD_CREATE_DETACHED attribute was set on creation
• Failure to join or detach threads – memory and other resources will leak until the process ends

int pthread_detach(pthread_t tid);
– tid: identification of the thread to detach

Question 15

Memory in Processes vs Threads

Answer 15

• Each thread will have its own stack, but all the threads in a process will share the heap.
• Threads are sometimes called lightweight processes because they have their own stack but can access shared data.
• Because threads share the same address space as the process and other threads within the process, the operational cost of communication between the threads is low, which is an advantage.

Question 16

Thread Safety

Answer 16

• The threads for a process share the entire address space of the process
• This means, threads can modify global variables, access open file descriptors, etc.
  – Be careful when reusing variables passed by reference
• So, we need to ensure that multiple threads do not interfere with each other – synchronize thread execution
• A program or function is said to be thread safe if it can be called from multiple threads without unwanted interaction between the threads
  – That is, it should be able to execute multiple threads simultaneously without “clobbering” shared data or creating “race” conditions

Question 17

Race condition

Answer 17

• A race condition occurs when two or more threads can access shared data and they try to change it at the same time.
• Because the thread scheduling algorithm can swap between threads at any time, you don’t know the order in which the threads will attempt to access the shared data.
• Therefore, the result of the change in data is dependent on the thread scheduling algorithm, i.e. both threads are “racing” to access/change the data.

Question 18

Thread-Safe Functions

Answer 18

• Not all functions can be called from threads
  – Many use global/static variables
  – Many functions have thread-safe replacements with _r suffix
• Safe:
  – ctime_r(), gmtime_r(), localtime_r(), rand_r(), strtok_r()
• Not safe:
  – ctime(), gmtime(), localtime(), rand(), strtok()
• Could use semaphores to protect access, but this generally results in poor performance

Question 19

Data Race Example

Answer 19

• Also called a critical section problem
• A race condition or data race occurs when
  – Two processors (or two threads) access the same variable, and at least one does a write
  – The accesses are concurrent (not synchronized) so that could happen simultaneously

Question 20

Synchronizing Threads

Answer 20

3 basic synchronization primitives / constructs / operations

– Mutex Locks (like a gatekeeper)
* Control thread’s access to the data with simple mutual exclusion

– Condition Variables
* More complex synchronization
* Let threads wait until a user-defined condition becomes true (i.e., based on the value of the data
* Removes polling requirement

– Semaphores
* Signal-based synchronization
* Allows sharing (not wait unless semaphore = 0)
* Access to data granted/blocked based on semaphore value

Question 21

Mutex Locks definition

Answer 21

Mutex (mutual exclusion) is a special type of variable used to restrict access to a critical section to a single thread at a time
– Guarantee that one thread “excludes” all other threads while it executes the critical section
– When a thread waits on a mutex/lock, CPU resource can be used by others

Question 22

mutex locks implementation

Answer 22

• A mutex lock is created like a normal variable
  – pthread_mutex_t mutex;
• Easier to use than standard semaphores
• Only the thread (say tid = 1) that locks a mutex can unlock it
• Mutexes are often declared as global variables
• Mutexes must be initialized before being used
  – A mutex can only be initialized once

int pthread_mutex_init(pthread_mutex_t *mp, const pthread_mutexattr_t *mattr);
* mp: a pointer to the mutex lock to be initialized
* mattr: attributes of the mutex – usually NULL

Question 23

Locking a Mutex

Answer 23

To ensure mutual exclusion to a critical section, a thread should lock a mutex

1.When locking function is called, it does not return until the current thread owns the lock
2.If the mutex is already locked, calling thread blocks
3.If multiple threads try to gain lock at the same time, the return order is based on priority of the threads
* Higher priorities return first
* No guarantees about ordering between same priority threads

int pthread_mutex_lock(pthread_mutex_t *mp);
* mp: mutex to lock

Question 24

Unlocking a Mutex

Answer 24

When a thread is finished within the critical section, it needs to release the mutex
– Calling the unlock function releases the lock
– Then, any threads waiting for the lock compete to get it
– Very important to remember to release mutex

int pthread_mutex_unlock(pthread_mutex_t *mp);
* mp: mutex to unlock

Question 25

Condition Variables

Answer 25

* Condition variables provide yet another way for threads to synchronize. While mutexes implement synchronization by controlling thread access to data, condition variables allow threads to synchronize based upon the actual value of data. * Without condition variables, the programmer would need to have threads continually polling (possibly in a critical section), to check if the condition is met. * This can be very resource-consuming since the thread would be continuously busy in this activity. A condition variable is a way to achieve the same goal without polling. * A condition variable is always used in conjunction with a mutex lock * A condition variable is an explicit queue (a data structure) that threads can put themselves in when some state of execution (i.e., some condition) is not as desired (by waiting on the condition) * Another thread, when it changes the condition, can wake one (or more) of those waiting threads to allow them to continue (by signaling on the condition) * A condition variable has two operations associated with it: – The wait() call is executed when a thread wishes to put itself to sleep – The signal() call is executed when a thread has changed something in the program and now wants to wake a sleeping thread waiting on this condition

Question 26

Spurious Wakeup

Answer 26

For performance reasons, the POSIX API allows the OS to wake up your thread even if the condition has not been fulfilled – This is called spurious wakeup, a complication that arises from the use of condition variables as provided by certain multithreading APIs where even after a condition variable appears to have been signaled from a waiting thread's point of view, the condition that was awaited may still be false – A thread might be awoken from its waiting state even though no thread signaled the condition variable – For correctness it is necessary, then, to verify that the condition is indeed true after the thread has finished waiting – Because spurious wakeup can happen repeatedly, this is achieved by waiting inside a loop that terminates when the condition is true

Question 27

Semaphores

Answer 27

* Semaphores are a good way to learn about synchronization, but they are not as widely used, in practice, as mutexes and condition variables. * A semaphore is a data structure used to help threads work together without interfering with each other. * pthreads allow the specific creation of semaphores – Semaphore is an integer variable and can be initialized to any value * Can do increments and decrements of semaphore value – Thread blocks if semaphore value is less than or equal to zero when a decrement is attempted – As soon as semaphore value is greater than zero, one of the blocked threads wakes up and continues * No guarantees as to which thread this might be

Question 28

Creating Semaphores

Answer 28

* Semaphores are created like other variables – sem_t semaphore; (POSIX semaphores have type sem_t) * Semaphores must be initialized int sem_init(sem_t *sem, int pshared, unsigned int value); * sem: the semaphore value to initialize * pshared: share semaphore across processes – usually 0 * value: the initial value of the semaphore

Question 29

Decrementing a Semaphore

Answer 29

int sem_wait(sem_t *sem); – sem: semaphore to try and decrement * If the semaphore value is greater than 0, the sem_wait call return immediately – Otherwise it blocks the calling thread until the value becomes greater than 0 * The sem_wait() atomic operation has the following semantics sem_wait(S) { while S <= 0 wait in a queue; S--; }

Question 30

Incrementing a Semaphore

Answer 30

int sem_post(sem_t *sem); – sem: the semaphore to increment * Increments the value of the semaphore by 1 – If any threads are blocked on the semaphore, they will be unblocked * Doing a post (i.e., sem_post) to a semaphore always raises its value – even if it shouldn’t! * The sem_post() atomic operation has the following semantics sem_post(S) { S++; Wake up a thread that waits in the queue; }

Question 31

Destroying a Semaphore

Answer 31

int sem_destroy(sem_t *sem); – sem: the semaphore to destroy * Destroys the semaphore at the address pointed to by sem * Only a semaphore that has been initialized by sem_init should be destroyed using sem_destroy * Destroying a semaphore that other processes or threads are currently blocked on produces undefined behavior – Same with using a semaphore that has already been destroyed

Question 32

What is the primary advantage of using threads in a multi-threaded application?

Answer 32

Threads allow for concurrent execution and better resource utilization

Question 33

Which of the following is true about thread synchronization?

Answer 33

Thread synchronization is used to ensure that threads do not interfere with each other when accessing shared resources

Question 34

A condition variable is used to wait until a particular condition is true. Condition variables must be used in conjunction with a mutex lock. (t/f)

Answer 34

True

Question 35

Suppose P, Q and R are co-operating processes satisfying Mutual Exclusion condition. If the process Q is executing in its critical section then, .................

Answer 35

'P’ does not executes in critical section, 'R’ does not executes in critical section

Question 36

Which are true of the (counting) semaphore operation called "wait()"? it decrements the value of the semaphore it increments the value of the semaphore if the value becomes negative, the calling process is blocked if the value is not positive, another process is unblocked A lower-level mutual exclusion mechanism is needed, to ensure that the fetching and storing of the semaphore value are done atomically.

Answer 36

it decrements the value of the semaphore if the value becomes negative, the calling process is blocked A lower-level mutual exclusion mechanism is needed, to ensure that the fetching and storing of the semaphore value are done atomically.

Question 37

Which of the following are true of the pthread_mutex_lock() operation? it takes a reference to a condition variable as a parameter it takes a reference to a mutex as a parameter it is intended to provide mutual exclusion it is intended for waiting for a condition or event

Answer 37

it takes a reference to a mutex as a parameter it is intended to provide mutual exclusion

Question 38

If one thread of a process is holding the lock on a mutex, and another thread of the process attempts to lock the mutex, the whole process is blocked. (t/f)

Answer 38

false

Question 39

In a system that supports multithreaded processes, which of the following are likely to be associated with an individual thread (i.e., different for different threads within the process)? Execution state (running, ready, etc.) Virtual address space Saved context (when not running) Protections/permissions to access system resources Execution stack Set of accessible open files

Answer 39

Execution state (running, ready, etc.) Saved context (when not running) Execution stack Set of accessible open files

Question 40

Because the thread scheduling algorithm can swap between threads at any time, you must program the order in which the threads will attempt to access the shared data

Answer 40

false

Question 41

A "strong" semaphore is one that always achieves mutual exclusion. (t/f)

Answer 41

true

Question 42

Match the following Counting Mechanism for Resource Allocation Used to Coordinate Threads' Execution Non-deterministic events Threads make no progress because of this circular chain of dependency mechanism An atomic increment and decrement operation is

Answer 42

Counting Mechanism for Resource Allocation Correct match: Semaphore Used to Coordinate Threads' Execution Correct match: Condition variables Non-deterministic events Correct match: Spurious wakeup Threads make no progress because of this circular chain of dependency mechanism Correct match: Deadlock An atomic increment and decrement operation is Correct match: Thread-safe