Module 4 - Threads, synchronisation and deadlock Flashcards
How do threads differ from processes?
The threads share heap, data segment, text
segment and the file descriptor table. Different processes do not share these resources.
Why is it more “expensive” to create a new process compared to creating a new thread?
Allocating memory and resources for process creation is costly. Because threads share the resources of the process to which they belong, it is more economical to create and context-switch threads.
In short, explain the many-to-one user level thread model. Also explain what happens if one of the threads makes a blocking system call in the many-to-one user level thread model.
Many user-level threads mapped to
a single kernel thread.
Only one thread can access the kernel at a
time, hence threads cannot run in parallel on multiprocessors.
What is meant by an atomic operation? Give examples of non-atomic operations.
In concurrent programming, an operation (or set of operations) is atomic if it appears to the rest of the system to occur at once without being interrupted.
lw (load), addi (increment), sw (store) are non-atomic operations.
Define the following terms: Race condition, Data race, Critical section and Mutual exclusion.
A race condition or race hazard is the
behaviour of an electronic, software or
other system where the output is dependent on the sequence or timing of
other uncontrollable events.
A data race occurs when two instructions from different threads access the same memory location and:
‣ at least one of these accesses is a write
‣ and there is no synchronization that is
mandating any particular order among these accesses.
A critical section is defined as part of a
program that should not be concurrently
executed by more than one of the program’s concurrent processes or threads at a time.
The requirement of ensuring that no two concurrent processes or threads are in the same critical section at the same time.
What is meant by a spin lock? What is meant by busy waiting?
A spinlock is a lock where a task simply waits in a loop (“spins”) repeatedly checking until the lock becomes available.
While a task is in its critical section, any other task that tries to enter its critical section must loop continuously in the entry code.
In the context of mutual exclusion, what is meant by starvation?
A mutex can encounter starvation issues when it consistently tries to acquire a lock that it is never able to get.
What are the limitations of Petersson’s solution to the mutual exclusion problem?
Software-based solutions such as Peterson’s are not guaranteed to work on modern computer architectures (without using memory barriers).
Peterson’s solution only works for two concurrent tasks.
While Peterson’s original formulation worked with only two processes, the algorithm can be generalized for more than two.
Name two atomic CPU instructions that can be used to implement synchronization locks.
The TestAndSet instruction atomically first sets the value at the target address to True and return the old value stored at the target address.
The Swap instruction atomically
swaps the content of two memory
locations a and b.
How can spin locks be constructed using the two atomic instructions from above?
Check pngs in downloads…
What operations can be performed on a semaphore and how do these operations work?
wait() - if counter > 0, decrement counter,
otherwise wait until counter becomes > 0, then decrement counter.
signal() - Increments the semaphore counter.
init() - create/allocate semaphore.
destroy() - delete/deallocate semaphore.
block() - block caller and add the caller to the semaphore wait list.
wakeup() - remove one task from the semaphore wait list and resume execution of this task.
What operations can be performed on a mutex lock and how do these operations work?
init() - create/allocate mutex lock.
acquire() - busy wait for lock to become false, then grab the lock (set mutex to true).
release() - set lock to false.
destroy() - Maybe same as semaphore (probably).
What is the difference between a mutex lock and a semaphore?
The correct use of a semaphore is to do signaling from one task to another.
A mutex is meant to be taken and released, always in that order, by each task that uses the shared resource it protects.
By contrast, tasks that use semaphores either signal or wait — not both. For example a consumer waits for a producer to produce data, and a producer signals the consumer when data is available.
When implementing semaphores and mutex locks, how can busy waiting be avoided?
By implementing a waiting queue.
Name and explain the necessary conditions for deadlock?
Deadlock will arise iff (if and only if) these four conditions holds simultaneously.
Mutual exclusion: only one task at a time can use a resource instance.
Hold and wait: a task holding at least one resource is waiting to acquire additional resources held by other tasks.
No preemption: a resource can be released only voluntarily by the task holding it, after that task has completed its task.
Circular wait: there exists a set {T0, T1, …, Tn-1} of waiting tasks such that T0 is waiting for a resource that is held by T1, T1 is waiting for a resource that is held by T2, …, …, …., Tn-2 is waiting for a resource that is held by Tn-1, and Tn-1 is waiting for a resource that is held by T0.
