CONCURRENCY : Mutual Exclusion & Synchronization

Get Started. It's Free
or sign up with your email address
Rocket clouds
CONCURRENCY : Mutual Exclusion & Synchronization by Mind Map: CONCURRENCY : Mutual Exclusion & Synchronization

1. Multiple Process

1.1. OS design is concerned with management of process & thread

1.1.1. multiprogramming

1.1.2. multiprocessing

1.1.3. distributed processing

2. Concurrency

2.1. Arises in context

2.1.1. multiple app.

2.1.2. structured app.

2.1.3. OS structure

2.2. Shared data

2.2.1. may cause problems

2.2.2. process may shared data

2.2.3. thread in same process can share global address space

2.3. Principle

2.3.1. interleaving & overlapping

2.3.2. in multiprogramming, relative speed of execution of processes cannot predicted

2.4. Difficulty

2.4.1. sharing of global resources

2.4.2. manage allocation of resources optimally

2.4.3. locate programming error

3. Race Condition

3.1. Read & write shared data

3.1.1. multiple process

3.1.2. thread

3.2. Final result depends on execution order

4. Mutual Exclusion

4.1. Need

4.1.1. no controlled access to shared data

4.1.2. result of concurrent execution will depend on order in which instruction interleaved

4.1.3. error in timing dependent, usually not reproducible

4.2. Enforced it on execution of critical sections

4.2.1. process execute code that manipulated shared data

4.3. Data coherence

4.3.1. ensures if properly used

4.4. Requirement

4.4.1. non interference

4.4.2. must be enforced

4.4.3. no deadlock & starvation

4.4.4. progress

4.4.5. no assumption

4.4.5.1. relative process speed

4.4.5.2. no. of processes

4.4.6. a process remain inside its critical section for a finite only

4.5. Hardware support

4.5.1. interrupt disabling

4.5.1.1. uni-processor system

4.5.1.2. guarantees mutual exclusion

4.5.2. not work in multiprocessor architecture

5. Semaphore

5.1. Variable that has an int. value upon which 3 operations defined

5.1.1. may be initialized to non-negative int. value

5.1.2. semWait operation decrements the value

5.1.3. semSignal operation increments the value

5.2. Strong sem.

5.2.1. process that has been blocked the longest is released from the queue first (FIFO)

5.3. Weak sem.

5.3.1. order in which processes are removed from the queue is not specified

5.4. Implementation

5.4.1. imperative that the semWait & semSignal operation be implemented as atomic primitives

5.4.2. in hardware / firmware

6. Monitors

6.1. Programming language construct that provides equivalent functionality to that of semaphore & is easier to control

6.2. Characteristic

6.2.1. local data variable are accessible only by the monitor's procedures & not by any external procedure

6.2.2. process enters monitor by invoking one of its procedures

6.2.3. only 1 process may be executing in the monitor at a time

6.3. Implemented in a no. of programming languages

6.3.1. Concurrent Pascal

6.3.2. Pascal - Plus

6.3.3. Java

6.3.4. Modula-2

6.3.5. Modula-3

7. Synchronization

7.1. To enforce mutual exclusion

7.2. To exchange information

7.3. Achieved by the use of condition variables that are contained within the monitor & accessible only within the monitor

8. Blocking Send, Blocking Receive

8.1. Blocking receive

8.1.1. both sender & receiver are blocked until the message is delivered

8.1.2. sometimes refered to as a rendezvous

8.2. Non-blocking send

8.2.1. non-blocking send,blocking receive

8.2.2. non-blocking send, non-blocking received

9. Addressing

9.1. Direct add.

9.1.1. send primitive includes a specific identifier of destination process

9.1.2. receive primitive can be handled in 1 of 2 ways

9.1.2.1. require that the process explicitly designate a sending process

9.1.2.2. implicit add.

9.2. Indirect add.

9.2.1. messages are sent to a shared data structure consisting of queues that can temporarily hold messages

9.2.2. queues are referred to as mailboxes

9.2.3. 1 process sends a message to the mailbox & the other process picks up the message from the mailbox

9.2.4. allows for greater flexibility in the use of message