Unit 03

Question 1

atomic action

Answer 1

An indivisible action – that is, either the action happens completely, or it does not happen at all. See also fine-grained and coarse-grained atomic actions.

Question 2

atomic objects

Answer 2

Also known as fully synchronised objects, atomic objects are objects which have all their methods declared as synchronized. The data is fully encapsulated and there is no public access to the data fields of the object apart from through such synchronized methods.

Question 3

binary semaphore

Answer 3

A semaphore used to guard exclusive access to a shared resource.

Question 4

blocking semaphore

Answer 4

A semaphore used for the synchronisation of cooperating processes.

Question 5

buffer

Answer 5

An area of temporary storage to allow a reader and writer to operate at different rates.

Question 6

busy-waiting

Answer 6

A technique whereby a process repeatedly checks to see if a condition is true such as waiting for keyboard input or waiting for a lock to become available.
See also spin lock.

Question 7

circular buffer

Answer 7

A buffer (data storage area) which is logically said to be circular – when a process gets to the end of the buffer, it can start again at the beginning.

Question 8

coarse-grainedatomic action

Answer 8

An atomic action implemented by a sequence of finegrained atomic actions.

Question 9

condition synchronisation

Answer 9

A mechanism for ensuring that a process is blocked if some condition is not fulfilled (for example, a producer process requires a buffer to be not full for it to be able to proceed).

Question 10

condition variables

Answer 10

Used in the operations of a monitor to provide conditional synchronisation.

Question 11

consistent state

Answer 11

A sensible state for a system as a whole (or the individual objects within the system) to be in, such that it conforms to a given specification. It usually refers to the values that are held by the variables in the system and whether these are within the range as set out by the specification.

Question 12

counting semaphore

Answer 12

A semaphore used to control access to shared resources – may be used for any number of resources.

Question 13

critical region

Answer 13

A sequence of instructions that access shared data.

Question 14

deadlock

Answer 14

A situation in which a process is prevented, for all time, from continuing because it is waiting for an event that will never happen, or for a resource that will never become free.

Question 15

entry protocol

Answer 15

The code that must be executed by a process prior to entering its critical region – it is designed to prevent the process from entering its critical region if another process is already in its associated critical region. An entry protocol together with its associated exit protocol should ensure mutual exclusion.

Question 16

exit protocol

Answer 16

The code that a process must execute immediately on completion of its critical region to ensure that other waiting processes may now enter their associated critical regions. Together, entry protocols and exit protocols are designed to ensure mutual exclusion.

Question 17

fairness

Answer 17

Fairness is concerned with guaranteeing that a process will be given the chance to proceed, regardless of how other processes behave.

Question 18

fine-grained atomic action

Answer 18

An atomic action implemented directly by an indivisible machine instruction.

Question 19

fully synchronised objects (See atomic objects.)

Answer 19

Are objects which have all their methods declared as synchronized. The data is fully encapsulated and there is no public access to the data fields of the object apart from through such synchronized methods.

Question 20

guarded suspension

Answer 20

A method invocation is suspended until a condition (i.e. guard) holds. Equivalent to condition synchronisation.

Question 21

inconsistent state

Answer 21

The state a system as a whole, or the individual objects within it, may end up in as a result of a violation of the specification for that system.

Question 22

interrupt disabling

Answer 22

When interrupts are disabled, the current executing process cannot be interrupted and will complete its execution.

Question 23

livelock

Answer 23

A situation where a process is continually executing an operation without getting nearer to a condition becoming true.

Question 24

liveness

Answer 24

This property asserts that a program must make some form of progress, and not come to a halt or run indefinitely without achieving its goal.

See also safety.

Question 25

lock

Answer 25

A file or object is said to be locked when processes are prevented from accessing it (usually because another client/process is accessing it). In Java, each object has a lock.

Question 26

lost update problem

Answer 26

The situation arising when a result made by one process has been overwritten (and hence lost) by another process. This occurs if uncontrolled access to a shared resource has been allowed.

Question 27

monitors

Answer 27

So-called Hoare monitors are data structures that provide operations which access encapsulated shared data under mutual exclusion.

The concurrency mechanism implemented by the Java language, with use of a lock and synchronised methods, is said to be based on monitors.

Question 28

multi-party operation

Answer 28

An operation that involves access to several objects. Since a synchronised multi-party operation requires several locks (one for each object in the operation), the programmer should be aware of the potential for deadlock.

Question 29

multiple readers, single writer

Answer 29

A classic problem in the study of mutual exclusion and condition synchronisation, in which only one writer is allowed to write at a time, but multiple readers are allowed to read.

Question 30

mutual exclusion

Answer 30

An approach that ensures only one process at a time can access a shared resource.

Question 31

mutual exclusion protocol

Answer 31

A set of rules (protocol) which, if obeyed by a number of processes that wish to access a shared resource, will enforce mutual exclusion.

Question 32

producer–consumer model

Answer 32

A model in which two processes work together and share data in such a way that one process assumes the role of producer (i.e. writes to the data resource) and the other assumes the role of consumer (i.e. reads from the resource).

Question 33

protocol

Answer 33

The rules that govern an interaction between different components.

Question 34

race conditions

Answer 34

Race conditions exist if the final outcome of a process is dependent on the timing or sequence of other processes (as if the processes are ‘racing’ each other).

Question 35

re-entrant locking

Answer 35

The locking mechanism used in Java. If a thread holds the lock for an object, and it invokes another synchronized method for the same object, it is allowed to continue. This means that under these circumstances no deadlock will arise.

Question 36

rolling back state

Answer 36

The act of returning the system’s state (usually the variables) back to how it was before an event occurred (such as an exception).

Question 37

safety

Answer 37

This property asserts that nothing bad happens during the execution of a program.

See also liveness.

Question 38

semaphore

Answer 38

A type of object that is used to protect a resource from concurrent access by multiple processes. It does this through the use of two operations semWait and semSignal. Internally, a semaphore has a data field that holds its value and a queue that is used to hold blocked processes.

Question 39

shared resources

Answer 39

A resource, which may be either data (in the form of variables or files) or hardware, that a number of processes have access to.

Question 40

single anonymous condition variable

Answer 40

Java’s concurrency mechanism allows just one wait set for all the threads that have called wait on a given object’s lock. This acts as the condition variable. This is in contrast to so-called Hoare monitors which can have multiple condition variables, and a queue for each specific condition. Therefore, we say that Java has a single condition variable, which is anonymous as it does not belong to any particular condition.

Question 41

spin lock

Answer 41

A lock where the thread simply waits in a loop (‘spins’), repeatedly checking until the lock becomes available. This is also known as busy-waiting because the thread remains active but is not performing a useful task.

Question 42

starvation

Answer 42

Starvation occurs when a runnable process is overlooked indefinitely by the scheduler.

Question 43

synchronisation

Answer 43

The need for different processes to synchronise their operations by waiting for each other. In Java, the keyword synchronized is used for methods, so that only one thread can execute the method at a time, forcing the other threads to wait.

Question 44

test-and-set (TAS)

Answer 44

A special atomic operation that tests and sets a Boolean, provided by the operating system as an indivisible machine instruction.

Question 45

thread safety

Answer 45

A class is thread safe if it can be executed concurrently by multiple threads without the shared data getting into an inconsistent state.

Question 46

wait set

Answer 46

The set of threads that have called wait and are waiting to be notified. Each object in Java has one wait set.

Question 47

wait–notify mechanism

Answer 47

The Java mechanism to implement condition synchronisation. A thread calls wait and will be blocked as long as the condition it is waiting on is not satisfied. Another thread calling notify or notifyAll can release this thread from its blocked state.