Unit 3 Flashcards
SAQ 1 - A What are race conditions?
Race conditions are when the final outcome of a process is dependent on the timing or sequence of other processes.
SAQ 1 - B In a circular buffer, if the data is being overwritten by a producer before it is consumed by the consumer, what problem has occurred?
This is an example of a race between the consumer and the producer processes to get to the shared memory: a race condition has occurred.
SAQ 1 - C
In deadlock, a process is blocked while waiting for a resource that is held by another process. In the dining philosophers problem, what would be the resource?
In the dining philosophers problem, forks are the resource
SAQ 1 - D What is the difference between deadlock and livelock?
In deadlock, one or more processes are not able to execute at all. In livelock, a process is executing operations without progressing.
SAQ 2
If a shared Boolean variable, such as busy, were used within entry and exit protocols, would both protocols require a TAS instruction?
The entry protocol consists of at least two instructions, checking the variable, and then setting its value, so this would require a TAS instruction to work properly as an atomic action. On the other hand, the exit protocol consists of resetting the value of the Boolean variable (without the need to check it first), so this does not necessarily require a TAS instruction.
SAQ 3
The two-process software solution in Table 2 is deficient and does not satisfy all the properties for correct concurrent programs. Explain which property in particular is not satisfied.
The liveness property is not satisfied, because one process may end up having to wait indefinitely and unnecessarily.
SAQ 4 - A In what ways can semaphores be used?
Semaphores can be used for: - Ensuring mutual exclusion from critical code; - Controlling access to single or multiple shared resources; - Synchronising cooperating processes.
SAQ 4 - B How can the incorrect use of semaphores lead to problems with safety and liveness?
By forgetting to use semWait it is possible for a resource to become accidentally unprotected (a safety issue). By forgetting to use semSignal it is possible for a resource to become locked indefinitely (a liveness issue).
Exercise 3 Explain why it is important that the semaphore’s operations semWait and semSignal are atomic.
Imagine the scenario where two processes, A and B, use a semaphore for mutual exclusion. Process A reads the value of the semaphore as 1 during asemWait operation and, at the same time, process B also executes this method, reading the value 1. Process A now sets the semaphore’s value to 0 and enters its critical region. Process B does the same – it writes the value of the semaphore as 0 and enters its critical region. Now something bad has happened: the mutual exclusion that the semaphore was supposed to impose has been violated.
SAQ 5 - A How can we achieve mutual exclusion in Java?
In Java, mutual exclusion can be achieved by using synchronised methods, using the synchronized keyword. Fully synchronised objects are objects for which all the methods are synchronised, and that is the safest, but possibly not the most efficient, strategy. For some objects, only certain operations or parts of operations need to be carried out under mutual exclusion, so the objects do not need to be fully synchronised.
SAQ 5 - B What is the wait–notify mechanism designed to assist with?
The wait–notify mechanism provides a way to implement condition synchronisation in synchronised methods – a thread can wait on a condition if the condition is not satisfied, and threads may notify other threads if they have altered the state of the shared data.
SAQ 5 - C What is the distinction between the following three thread states: BLOCKED, WAITING and TIMED_WAITING?
A thread ends up in the BLOCKED state if it attempts to execute a synchronised method, but the lock for the object is already held by another thread. Both WAITING and TIMED_WAITING are states that a thread ends up in as a result of the wait method, and hence as a result of a condition not being satisfied. A thread in the TIMED_WAITING state can be woken up as a result of either a notification or the timeslot having expired.
SAQ 5 - D What is the difference between notify and notifyAll, and which of these two methods is considered safer to use?
With notify only one thread gets selected to receive the notification – but we do not know which thread it will be. With notifyAll all threads get notified. On the whole notifyAll is safer to use, because with notify, if the wrong thread receives the notification, the program may end up deadlocked, as the notification cannot be passed on to other threads.
SAQ 6
In Subsection 2.3 we discussed fairness as a liveness issue. Do you think the algorithm for the writers-preferred policy is fair?
On the face of it, it seems to make sense to give writer processes priority over readers, because the shared resource should always be in the most up-to-date state. This is presumably also in the interest of the reader processes. However, it is possible, in the given scheme, that reader processes never get a chance to run, because writer processes always get priority. This would be unfair not only to the readers, but also it would be unfair to the writers, since they would be wasting their efforts in writing things that never get read!
SAQ 7 - A What are the four conditions for deadlock?
The four conditions for deadlock are: mutual exclusion, hold while waiting, no preemption and a cycle of processes.
