part3

Question 1

What is synchronisation?

Answer 1

The limitation of possible program traces by coordinating execution such that certain conditions are satisfied.

E.g., certain invariant is satisfied and/or execution has some desired property

Question 2

What is an invariant?

Answer 2

an assertion that holds at all control points, such as mutual exclusion being maintained or y being less than or equal to x

Question 3

What does action synchronisation rely on?

Answer 3

Action counting and invariants on the counting

Question 4

If A is an action in a program, what does cA denote?

Answer 4

The number of completed executions of A

Question 5

What is a topology invariant?

Answer 5

An invariant derived directly from the program text

E.g., two actions always occuring one after the other

Question 6

What two things is action synchronisation specified by? What are such inequalities referred to as?

Answer 6

Inequalities on:

1. Action counts
2. Program variables directly related to this counting

Synchronisation conditions or synchronisation invariants

Question 7

What does P(s) refer to? How about V(s)?

Answer 7

P(s): <await(s>0)>; s=s-1;

V(s): <s = s + 1>

Question 8

What are the primary two semaphore invariants? What invariant arises from these two?

Answer 8

S0: S >= 0
S1: s = s0 + cV(s) - cP(s)

S2: cP(s) <= s0 + cV(s)

Question 9

What is the progress property of semaphores?

Answer 9

Blocking is only allowed if the safety properties would be violated

Question 10

What is the action synchronisation solution in general? Specifically, give a collections of tasks/threads executing actions A,B,C,D and the synchronisation:

SYNC: a * cA + c * cC <= b * cB + d * cD + e for non-negative constants a,b,c,d,e

Answer 10

Introduce a semaphore s, s0 = e and replace:

A -> P(s)^a; A
C -> P(s)^c; C
B -> B; V(s)^b
D -> D; V(s)^d

Question 11

What does sem_t *sem declare?

Answer 11

A pointer to a semaphore object, which will be used for synchronization.

Question 12

What function is used to open and create a named semaphore?

Answer 12

sem_open(name, flags, mode, init-val)

Question 13

In sem_open, what does the name parameter represent? What does the flags parameter in sem_open determine? What is the purpose of the mode parameter in sem_open? What does the init-val parameter in sem_open define?

Answer 13

A system-wide unique name for the semaphore.

The operation to be performed.

To specify the file permissions.

The initial value of the semaphore.

Question 14

What function is used to close a semaphore in the current process while keeping it accessible to others?

Answer 14

sem_close(sem)

Question 15

Which function removes a named semaphore from the system? When is a named semaphore fully removed from the system?

Answer 15

sem_unlink(name)

When no process is using it.

Question 16

What does sem_init(sem, pshared, init-val) do? In sem_init, what does the pshared parameter indicate?

Answer 16

Initializes an unnamed semaphore.

Whether the semaphore is shared across processes or just threads within a process.

Question 17

What function is used to destroy an unnamed semaphore? What happens if you use a semaphore after it has been destroyed with sem_destroy?

Answer 17

sem_destroy(sem)

It must not be used, as its resources are released.

Question 18

What does sem_wait(sem) do?

Answer 18

Attempts to decrement (lock) the semaphore; if the semaphore value is greater than zero, it decrements it. If the value is zero, it blocks until the semaphore becomes available.

Question 19

How does sem_trywait(sem) differ from sem_wait(sem)?

Answer 19

sem_trywait does not block; it attempts to decrement/lock the semaphore and returns an error if not possible.

Question 20

What is the purpose of sem_post(sem)?

Answer 20

To increment the semaphore and wake one waiting thread if any are blocked.

Question 21

How can you retrieve the current value of a semaphore? In sem_getvalue, what does a negative semaphore value represent?

Answer 21

By using sem_getvalue(sem, &val).

The number of waiters (the length of the waiting queue).

Question 22

When is busy-waiting accepted? What is the condition for busy-waiting to work as expected?

Answer 22

When:

1. Waiting is guaranteed to be short in comparison to the cost of context switching
2. There is nothing else to do

The tests in the while and locking the mutex are executed atomically

Question 23

What is a deadlock state? How is it typically proven that a deadlock does NOT exist?

Answer 23

A system state in which a set of tasks is blocked indefinitely

Proof by contradiction; Assume deadlock occurs, investigate all task sets that can be blocked at the same time, show a contradiction;

Question 24

What are the three main ways of preventing deadlocks?

Answer 24

Always let critical sections terminate
- always call unlock(m) after lock(m)

Avoid cyclic waiting
- avoid P or lock operations that may block indefinitely between lock(m) and unlock(m)
- use a fixed order when calling P-operations on semaphores or mutexes

Avoid greedy consumers
- P(a)k should be an indivisible atomic operation when tasks compete for limited resources

Question 25

Give an example of cyclic waiting for three tasks T1, T2, T3 with three mutexes m1, m2, m3

Answer 25

T1 blocked on P(m2), T2 blocked on P(m3), T3 blocked on P(m1), leading to deadlock

Question 26

What does the invariant of condition synchronisation refer to? What does it require in terms of different processes?

Answer 26

A combination of execution state

Explicit communication (signalling) between processes

Question 27

What are the two principles of condition synchronisation?

Answer 27

Checking and blocking where a condition may be violated

Signalling waiters where a condition may have become true

Question 28

What does var cv: Condition represent in condition synchronization?

Answer 28

A condition, often associated with a Boolean expression in terms of program variables.

Question 29

What are the four basic operations on a condition variable (cv)?

Answer 29

wait, signal, sigall, and empty.

Question 30

What does the wait(…, cv) operation do?

Answer 30

Suspends the execution of the caller.

Question 31

What does the signal(cv) operation do?

Answer 31

Frees one process/thread suspended on wait(cv); does nothing if there are no suspended processes.

Question 32

What is the effect of the sigall(cv) operation?

Answer 32

Frees all processes suspended on wait(cv).

Question 33

What does the empty(cv) operation check?

Answer 33

Whether there are no processes suspended on wait(cv), returning true or false.

Question 34

What does pthread_cond_t cond = PTHREAD_COND_INITIALIZER; do?

Answer 34

Statically initializes the condition variable cond.

Question 35

What is the purpose of pthread_cond_init(&cond, attr);?

Answer 35

Dynamically initializes cond with optional attributes attr (or NULL for defaults).

Question 36

What does pthread_cond_destroy(&cond); do?

Answer 36

Destroys the condition variable cond, freeing its resources.

Question 37

How does pthread_cond_wait(&cond, m); work?

Answer 37

Blocks the calling thread until cond is signaled, releasing and reacquiring the mutex m.

Question 38

How is pthread_cond_timedwait(&cond, m, exp); different from pthread_cond_wait?

Answer 38

It unblocks after the time exp if no signal is received, returning ETIMEDOUT.

Question 39

What is the purpose of pthread_cond_signal(&cond);?

Answer 39

Wakes up one thread waiting on cond.

Question 40

What does pthread_cond_broadcast(&cond); do?

Answer 40

Wakes up all threads waiting on cond.

Question 41

What is a monitor? What does the data record? Under what condition are the operations of the monitor executed?

Answer 41

An object that contains a combination of data and operations on that data

The state of the monitor

Mutual exclusion, i.e., only one task can be inside the monitor at any one time

Question 42

What three things does a monitor do?

Answer 42

Encapsulate relevant shared variables

Provide well-defined operations on shared variables

Provide exclusion

Question 43

What are the four signalling disciplines?

Answer 43

Signal and exit

Signal and continue

Signal and wait

Signal and urgent wait

Question 44

How does signal and exit work? Is sigall supported? Must the condition hold after the signal?

Answer 44

The task executing a signal exits the monitor immediately, and monitor is given to a waiter on that variable, if any.

No

Yes

Question 45

How does signal and continue work? Must the condition hold after the signal?

Answer 45

Task executing a signal continues to use that monitor until a wait or until the end of the routine. Any task released by signal competes with the other tasks to obtain monitor access again.

No

Question 46

How does signal and wait work? Must the condition hold after the signal?

Answer 46

The task executing a signal is stopped in favour of the signalled process. Signaller waits to access the monitor after the signal and competes with all other tasks. Similar to signal and exit.

Yes

Question 47

How does signal and urgent wait work? Must the condition hold after the signal?

Answer 47

Task executing a signal is stopped in favour of the signalled process. Signaller waits to access the monitor again after the signal but does not compete with all other tasks again, as it has priority over them.

Yes

Question 48

What is the minimum number of semaphores required to enforce 5 synchronization conditions involving 2 global variables and 9 local variables manipulated in 15 threads? Assume we only use action synchronization.

Answer 48

5

Question 49

What is the Dining Philosopher Problem?

Answer 49

A synchronization problem where philosophers share forks to eat. They must acquire two forks but risk deadlock (all waiting), starvation (some never eat), or conflicts over resources.

Use mutexes, semaphores, or resource acquisition strategies to avoid deadlock and starvation.