Operating Systems Concurrency (PPT 4-5)

Question 1

What is Concurrency?

Answer 1

It is:
-Many independent processes (unknowingly sharing resources)
-Several co-operating processes
-One multi-threaded program
on a machine with one or more processors or in a distributed system

Question 2

What is Synchronisation?

Answer 2

It is when one or more processes is forced to wait until another process has completed a vital task.

Question 3

What is Signalling?

Answer 3

This is when processes can talk to each other with basic signals or use messages. Important part is that processes communicate with each other

Question 4

What are the three problems Concurrency can bring?

Answer 4

• Race Conditions
• Deadlock
• Starvation

Question 5

What is a Race Condition?

Answer 5

It is whenever two or more processes manipulate a global resource in a way that it is possible an incorrect result can be produced

Question 6

How is a critical section of program code defined?

Answer 6

It is any piece of code that has to be run under the assumption that no other process is executing a similar, related piece of code

Question 7

What is mutual exclusion?

Answer 7

The execution of a critical piece of code must be mutually exclusive to the execution of any other such critical piece of code.

Question 8

What are the six requirements of Mutual Exclusion?

Answer 8

• Must allow only one process into a critical section of program code at any one time
• A process halting in non-critical code must do so without interfering with any other process
• Process must (eventually) be allowed into its critical section. No deadlock or starvation.
• First come: Immediately served
• No assumption about speed or quantity of processes involved
• Critical sections must have finite duration

Question 9

How does an Interrupt Oriented Solution to race conditions work?

Answer 9

Just before we run a critical section, all interrupts are disabled. Once the critical section is finished, interrupts are re-enabled.

Question 10

What are Special Machine Instructions?

Answer 10

They are special instructions that help with mutual exclusion. They are atomic so can’t be pre-empted or sub-divided. RAM is also so organised that the CPU can only access a particular memory location any one time so sequential access is guaranteed

Question 11

What is a Test and Set solution to race conditions?

Answer 11

This means that a boolean is tested when arriving at the critical code. If it is 1, the process is blocked and avoid the critical section if possible. If it is 0, the boolean is set to 1 and the process enters the critical section. Once it is finished, the boolean is set to 0

Question 12

What is a Semaphore?

Answer 12

These are a high level implementation of the low level instructions.

Question 13

How do Semaphores work?

Answer 13

Semaphores allow two or more processes to communicate using signals. A process can be forced to stop at a particular point until it receives a signal from another process. To send a signal, use the primitive signal(s). To receive a signal, use the primitive wait(s). If signal is not sent, wait blocks the progress

Question 14

What is the Integer Count and Queue?

Answer 14

A semaphore contains a record with the integer count and a queue. Queue contains a list of waiting processes (if any are waiting). Count can be initialised to any non-negative integer value (often 1 as there is 1 available instance of the resource). Queue will start empty

Question 15

What do wait and signal do in a Semaphore?

Answer 15

Wait
-decrements the semaphore count. If < 0 then process is blocked and added to queue

Signal
-increments the semaphore count. If count =<0, one waiting process is removed from the queue and placed on the ready list

Question 16

What is a binary Semaphore?

Answer 16

It is similar to a normal semaphore except the value can only be 1 or 0.

Question 17

What are the advantages of Semaphores?

Answer 17

• Simple
• Intuitive
• Flexible
• Quick and easy to implement

Question 18

What are the disadvantages of Semaphores?

Answer 18

• Easy to make mistakes
• Difficult to prove processes are correct
• Programmer is responsible for ensuring correct usage
• Processes frequently have to co-operate in their use of Semaphores. This breaks the isolation/modularisation of processes

Question 19

How is test and set used within semaphores?

Answer 19

Both wait and signal are themselves critical code so must be atomic. Need test and set instructions within wait and signal to ensure mutual exclusion. This is dealt with by the low level primitives

Question 20

What is the producer/consumer problem?

Answer 20

• One or more producers are generating data and placing it into a buffer
• One consumer is taking data out of the buffer
• Use semaphores to control access.
• Assume use of bounded buffer

Question 21

What is a bounded buffer?

Answer 21

It is a buffer with a finite size. It has two pointers, in and out. When an item is placed in, in is incremented. When an item is removed, out is decremented. When in and out are equal, there is nothing in the buffer.

Question 22

What is a Monitor?

Answer 22

It is a software module that consists of one or more procedures, an initialisation section and hidden, local data. The outside world can only see the procedures and the local data can only be manipulated within the procedures. Entry into the monitor is through a procedure call. Only one process can be executing in the monitor at any one time. Any other process that is inside the monitor is suspended

Question 23

What is Message Passing?

Answer 23

In both the monitor and semaphores, processes interact by signalling. All processes have to know what the implicit message is behind each signal. Far greater flexibility is achieved if one process can actually pass an explicit message to one or more other processes

Question 24

What are Simple Message Primitives?

Answer 24

The minimum requirement for processes to pass messages to each other is a pair of instructions:
send(destination,message)
receive(source,message)

Message Passing Interface (MPI) is a standard language for passing messages

Question 25

How does message passing link in with synchronisation?

Answer 25

A blocking send or receive means that the calling process waits until a message is received or delivered.

A non blocking send or receive means that the sender posts and forgets while the receiver comes away empty handed if the message is not available immediately.

If a system implements a blocking receive mechanism, there is usually a command to check for available messages

Question 26

What is an Exchange Instruction?

Answer 26

It is something that can exchange contents of an internal register with the contents of a memory location in one action. Means that a processor can set a variable in memory and fetch its previous state from memory in one atomic action.

Question 27

What is Deadlock?

Answer 27

This is the blocking of a set of processes due to an unfortunate distribution of resources between processes. It happens when resources are so divided up between processes that each needs a resource from another and therefore none can finish

Question 28

What is Starvation?

Answer 28

This is the indefinite prevention of a process progressing due to continued denial of access to a resource

Question 29

What are Re-usable Resources?

Answer 29

These are global resources that can be temporarily used exclusively by one process but are eventually released and then available to others

Question 30

What are Consumable Resources?

Answer 30

These are entities that are (continuously) created and made available for processes to uses. When a process acquires such a resource, it usually destroys it and it is not released back for general use

Question 31

What are the four conditions for deadlock to occur?

Answer 31

• Mutual Exclusion: Only one process can use a resource at one time
• Hold and Wait: Once a process has acquired a resource it is not prepared to relinquish it whilst waiting to acquire other resources
• No pre-emption: No process can be forced to relinquish a resource
• Circular Wait: A closed chain of processes in which each one is waiting for another to release a resource

Question 32

How do we prevent the Mutual Exclusion condition for deadlock?

Answer 32

You can’t, it is essential to the running of a modern operating system.

Question 33

How do we prevent Hold and Wait condition for deadlock?

Answer 33

We have to prevent a process from holding onto resources while waiting for others. It could possibly do this by making it get all of resources at one point but this is inefficient

Question 34

How can we prevent the no pre-emption condition for deadlock?

Answer 34

We can make a process periodically record the state of the resource and itself, so it can re-create the scenario and start again from that point. When a process requests unavailable resources, two common things could happen: The process gives up all its resources and attempts again later or the OS forces the process to give up its resources

Question 35

How do we prevent the Circular Wait condition for deadlock?

Answer 35

Resources have to be ordered and “lined up” in some way. Each resource travels along the line at its own pace but must pick resources it wants as it passes them

Question 36

What is Deadlock Detection?

Answer 36

This approach assumes that deadlocks don’t happen often. Preventing a deadlock costs efficiency so this says if one happens, we will deal with it. Many mathematical algorithms for detecting if one has happened

Question 37

How can we break a deadlock?

Answer 37

Four possible ways:

1) Kill all the deadlocked processes. Simple and easy but drastic
2) If check-pointing is implemented, force all processes back to their last state and restart. Random factors will likely stop deadlock
3) Kill processes one at a time until deadlock stops
4) Pre-empt resources until the deadlock is broken

These actions take no account of the possible damage but do try to avoid it

Question 38

How could we avoid a Deadlock?

Answer 38

Can achieve this by controlling allocation of resources. Resources only granted if deadlock is avoided. Have to build a system to keep track of what resources are in use and the maximum requirement each process has for each type of resource

Question 39

What is Process Initiation Denial?

Answer 39

This is when a process can start only if the sum of its and all currently running processes’ maximum requirements is less than or equal to the total available. It is not optimal as it assumes the worse case scenario that all running processes will want all their resources at the same time

Question 40

What is Resource Allocation Denial?

Answer 40

This is a dynamic process which kicks in when a resource is requested. The OS keeps sufficient resources to ensure that there is at least one way in which all processes can complete- a safe state. It involves reserving enough that one process can receive everything it requires.

Question 41

What is the best strategy for preventing Deadlock?

Answer 41

There isn’t a single best way as none of the previous strategies are perfect. The best performance can be achieved by using a combination of techniques