Chapter 5 - Concurrency, Mutual Exclusion, and Synchronization

Operating System design is concerned with the management of what?

Processes and Threads

What is Multiprogramming?

The management of multiple processes within a uniprocessor system

What is Multiprocessing?

The management of multiple processes within a multiprocessor

What is Distributed Processing?

The management of multiple processes executing on multiple distributed computer systems.

What three contexts does concurrency arise?

• Multiple Applications

• Structured Applications

• Operating System Structure

1st context of Concurrency - Multiple Applications:

Invented to allow processing time to be dynamically shared among a number of active applications

2nd context of Concurrency - Structured Applications:

An extension of the principles of modular design and structured programming, some applications can be effectively programmed as a set of concurrent processes.

3rd context of Concurrency - Operating System Structure

Operating Systems themselves implemented as a set of processes or threads.

What is mutual exclusion?

The requirement that when one process is in a critical section that accesses shared resources, no other process may be in a critical section that accesses any of those shared resources

Principals of Concurrency - Interleaving:

The processor acts like it is running multiple tasks at once by rapidly switching between them, often used in single-core systems

Principals of Concurrency - Overlapping

Different tasks genuinely run at the same time, particularly on multicore processors, or I/O operations occur concurrently within CPU processing.

What are the main problems with Interleaving and Overlapping?

Race conditions, deadlocks, and starvation are all common, the relative speed of execution of processes cannot be predicted

In a uniprocessor, what happens with processes?

The relative speed of execution of processes cannot be predicted.

What is concurrency?

The capability of an OS to run more than one task at the same time.

What are the difficulties of concurrency?

• Sharing of global resources

• Difficult for the OS to manage the allocation of resources optimally

• Difficult to locate programming errors as results are not deterministic and reproducible.

What is a race condition?

A situation in which multiple threads or processes read and write a shared data item and the final result depends on the relative timing of their execution. THINK THE ATM EXAMPLE

What are the concerns raised in OS Concurrency?

The OS must:

• Be able to keep track of various processes

• Allocate and de-allocate resources for each active process

• protect the data and physical resources of each process against interference by other processes

• ensure that the processes and output are independent of the processing speed

When processes are unaware of each other, what do they do?

Compete

When processes are indirectly aware of each other, what do they do?

Cooperate by Sharing

When processes are directly aware of each other, what do they do?

Cooperate by communication

Concurrent processes come into conflict when they?

Are competing for the use of the same resource.

In the case of competing processes three control problems must be faced:

• The need for mutual exclusion

• Deadlock

• Starvation

What are the requirements for mutual exclusion?

• It must be enforced

• A process that halts must do so without interfering with other processes

• No deadlock or starvation

• A process must not be denied access to the critical section when it is empty

• No assumptions are made about the process speed or number of processes

• A process remains inside its critical section for a finite time

What are the disadvantages of disabling interrupts to guarantee mutual exclusion?

The efficiency of the execution could be noticeably downgraded and it doesn’t work in a multiprocessor architecture

What are the two major Special Machine Instructions for Mutual Exclusion

Compare and Swap

What are the advantages of Special Machine Instruction?

• Applicable to any number of processes on either a single processor or multiple processors sharing Main Memory

• Simple and easy to verify

• It can be used to support multiple critical sections; each critical section can be defined by its own variable

What are the disadvantages of Special Machine Instruction?

• Busy-waiting is employed; while a processes is waiting for the critical section it consumed processor time

• Starvation is possible with more than one process waiting

• Deadlock is possible

What is a semaphore?

An integer value used for signaling among processes. Only three operations may be performed on a semaphore, all of which are atomic; initialize, decrement, and increment

Semaphore Initialize:

May be initialized to a nonnegative integer value

Semaphore Decrement:

The semWait operation decrements the value (lock)

Semaphore Increment

The semSignal operation increments the value (unlock)

Consequences of Semaphores

• There is no way to know before a process decrements a semaphore whether or not it will block.

• There is no way to know which process will continue immediately on a uniprocessor system when two processes are running concurrently

• When you signal a semaphore, you don't know whether another process is waiting, so the number of unblocked processes may be zero or one.

What is a Strong Semaphore?

The process that has been blocked the longest is released from the queue first (no starvation)

What is a weak Semaphore?

The order in which processes are removed from the queue is not specified (Can have starvation)

What is the producer/consumer problem?

One or more producers are generating data and placing them in a buffer

A single consumer is taking items out of the buffer one at a time

Only one producer or consumer may access the buffer at any one time
The problem is that you must ensure the producer cannot add data when the buffer is full, and the consumer can’t remove from an empty buffer

How does one implement Semaphores?

The semWait and semSignal operations must be implemented as atomic primitives.

They can be implemented in hardware or firmware

Software schemes like Dekker’s or Peterson’s algorithms can also be used

Hardware-supported schemes for mutual exclusion also exist.

What are monitors?

Programming language constructs that provide the functionality of Semaphores while also being easier to control. They are software modules consisting of one or more procedures, an initialization sequence, and local data

Characteristics of Monitors:

• Local data variables are accessible only by the monitors procedures, and not by any external procedure

• Process enters monitor by invoking one of its procedures

• Only one process may be executing in the monitor at a time

How is Synchronization achieved in Monitors?

The use the condition variables only accessible by the monitor: cwait and csignal

What makes Monitors primarily different from Semaphores?

The monitor itself enforces mutual exclusion, not the programmer.

When processes interact with one another, what fundamental requirements must be satisfied?

Synchronization (To enforce mutual exclusion) and Communication (To exchange information)

What is Message Passing?

An approach to provide Synchronization and Communication using a pair of primitives: send (destination, message) and receive (source, message)

A process sends information in the form of a message to another process designated by a destination

A process receives this information using the receive primitive

Communication of a message between two processes implies what?

Synchronization between the two

The receiver cannot receive a message until what?

It has been sent by another process

When a receive primitive is executed in a process, what are the two possibilities?

• If there is no sent, waiting message, the process is blocked until a message arrives or the process continues to executing, abandoning the attempt to receive

• If a message has been previously sent, the message is received and the execution continues

What are Blocking send and receive?

Both sender and receiver are blocked until the message is delivered, allowing for tight synchronization. Sometimes called a rendezvous

In a nonblocking send with a blocking receive:

• Sender continues on but receiver is blocked until the requested message arrives

• Most useful combination

• Sends one or more messages to a variety of destinations as quickly as possible

• Example — A service process that exist to provide a service or resource to other processes

In a Nonblocking send with a nonblocking receive

Neither party is required to wait

What is addressing?

Schemes for specifying processes in send and receive primitives. Fall into two categories: Direct and Indirect

What is Direct Addressing?

• Send primitive includes a specific identifying of the destination process.

• Receive primitive can be handled by either requiring that the process explicitly designate a sending process, or by implicit addressing when it is impossible to specify the anticipated source process

What is Indirect Addressing?

Messages are sent to a shared data structure consisting of queues that can temporarily hold messages. These queues are referred to a mailboxes.

One process sends a message to the mailbox and the other process picks up the message from the mailbox

Allows for greater flexibility in the use of messages

What is the Readers/Writers problem?

A data area is shared among many processes, where some only read the data area, and some only write to the data area. In this case, 3 conditions must be satisfied:

1. Any number of readers may simultaneously read the file

2. Only one writer at a time may write to the file

3. If a writer is writing to the file, no reader may read it.

What is a race condition in concurrent processing?

A race condition occurs when multiple processes read/write shared data such that the final result depends on the unpredictable interleaving of their execution.

Why is mutual exclusion necessary?

To ensure only one process accesses a critical section at a time, preventing inconsistent or corrupted shared data.

What are the key requirements for a correct mutual exclusion mechanism?

Enforced exclusivity, no deadlock, no starvation, no assumptions about speed/number of processors, halted processes don't interfere, and finite critical-section time

How does a semaphore enforce synchronization?

semWait decrements and may block a process; semSignal increments and may unblock a waiting process, controlling access to shared resources.

What is the difference between strong and weak semaphores?

Strong semaphores unblock processes in FIFO order, preventing starvation; weak semaphores do not specify unblocking order.

Why can busy waiting be problematic in hardware-based mutual exclusion?

Because a process waiting for entry still consumes CPU time, causing inefficiency and potential deadlock/starvation.

What is the purpose of condition variables in monitors?

They allow a process to block inside a monitor until a condition is satisfied, using cwait and csignal for controlled synchronization.

How does message passing support mutual exclusion?

Processes use a mailbox as a token: receiving a message grants access to the critical section, and sending it back releases the resource.

What problem does the bounded-buffer producer/consumer solution address?

It ensures producers don’t add to a full buffer and consumers don’t remove from an empty buffer while coordinating buffer access safely.

What conditions define the readers/writers synchronization problem?

Any number of readers may read simultaneously, but only one writer may write, and no reader may read while a writer writes.