5. Deadlock and Exec

Question 1

What do locks do?

Answer 1

Locks protect access to a shared resource.

Question 2

Walk through the steps of acquiring deadlock with two threads and two shared resources.

Answer 2

Thread A runs and grabs the lock for Resource 1. Thread B runs and grabs the lock for Resource 2. Context switch to thread A which tries to grab lock for Resource 2 and goes to sleep. Context switch to thread B which tries to grab the lock for Resource 1 and goes to sleep.

Both threads are asleep with no thread capable of waking either up. Deadlock.

Question 3

What is deadlock?

Answer 3

Deadlock occurs when a thread or set of threads are waiting for each other to finish and thus nobody ever does.
(Circular dependency; cycle of dependencies)

Question 4

How can a single thread deadlock?

Answer 4

Thread A acquires the lock for Resource 1 and then tries to reacquire Resource 1.

Question 5

How do you implement a recursive lock?

Answer 5

You allow a thread to reacquire a lock that it already holds, as long as calls to acquire are matched by calls to release.

Question 6

Why would you want to implement a recursive lock?

Answer 6

In case a single thread needs to acquire a lock through a function call foo() and then acquire it again within foo() through another call.

Question 7

What four conditions must be in place to result in a deadlock?

Answer 7

1. Protected access to shared resources (which implies waiting).
2. No resource preemption, meaning that the system cannot forcibly take a resource from a thread holding it.
3. Multiple independent requests, meaning a thread can hold some resource while requesting others.
4. Circular dependency graph, meaning that Thread A is waiting for Thread B which is waiting for Thread C which is waiting for Thread D which is waiting for Thread A

Question 8

Describe the “Dining Philosophers” problem.

Answer 8

5 philosophers come to a dinner party, each carrying one chop stick. Two chop sticks are required to eat, so no philosopher is able to make progress on their meal with their own single chop stick. They must come up with a synchronization plan so that they can all eat using the shared resources available to them.

Question 9

What is starvation?

Answer 9

The condition in which one or more threads do not make progress.

Question 10

How is starvation different than deadlock?

Answer 10

Starvation differs from deadlock in that some threads make progress and it is, in fact, those threads that are preventing the “starving” threads from proceeding

Question 11

Which is better, deadlock or a race condition?

Answer 11

Deadlock, because the problem is much easier to detect. Progress stops as soon as the issue arrises, pointing directly to the culprits.

Question 12

What are the four stages of the process lifecycle?

Answer 12

1. Birth w/ fork(). 2. Change w/ exec(). 3. Death w/ exit(). 4. Afterlife w/ wait()

Question 13

What does exec() do?

Answer 13

The exec() family of system calls replaces the calling process with a new process loaded from a file

Question 14

What does ELF stand for?

Answer 14

Executable and Linkable Format

Question 15

What must the executable file that exec() remakes a process with contain?

Answer 15

A complete blueprint indicating how the address space should look when exec() completes.

It should lay out what the contents of memory should be and where the first thread starts executing.

Question 16

How does argument passing work when calling exec()?

Answer 16

The process calling exec() passes arguments to the process that will replace it through the kernel.

The kernel retrieves the arguments from the process after the call to exec() is made.

It then pushes them in to the memory of the process where the replacement process can find them when it starts executing.

(This is where main gets argc and argv)

Note: exec() does not return (on success)

Question 17

Does exec() mess with file handles when modifying a process?

Answer 17

No. Exec() does not modify the file table of the calling process. Fork() did work to duplicate the file table and possibly set up pipes between the parent and child processes, so it would be counterproductive to upend any work fork() accomplished through manipulation of the file table.