Concurrency & Interprocess Communication

Concurrency & Interprocess Communication

Interprocess Communication (IPC)

• Processes can be:

  • Independent: Cannot affect or be affected by other processes.

  • Cooperating: Can affect or be affected by other processes, requiring IPC mechanisms.

• Reasons for process cooperation:

  • Information sharing

  • Computation speed-up

  • Modularity

  • Convenience

• Issues of process cooperation:

  • Data corruption

  • Deadlocks

  • Increased complexity

  • Requires process synchronization

Models for Inter-Process Communication (IPC)

• Message Passing:

  • Process A sends a message to the Kernel.

  • The Kernel sends the message to Process B.

• Shared Memory:

  • Process A puts a message into shared memory.

  • Process B reads the message from shared memory.

Race Condition

• A race condition is an undesirable situation that occurs when a device or system attempts to perform two or more operations simultaneously.

• The operations must be done in the proper sequence and should be accurate, but the device or system's nature prevents this.

• Processes can execute concurrently but may be interrupted, leading to partial completion.

• Concurrent access to shared data may result in data inconsistency.

• Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes.

Example

Consider two processes, A and B, accessing a shared counter:

Process A:

register1 = counter
register1 = register1 + 1
counter = register1
print counter

Process B:

register2 = counter
register2 = register2 - 1
counter = register2
print counter

The final value of the counter depends on the execution order of A and B, leading to a race condition.

Print Spooler Directory Example

Two processes want to access shared memory (e.g., a print spooler directory) at the same time.

Process A:

1. next_free_slot = in

2. Write the file name at slot (7)

3. next_free_slot += 1

4. in = next_free_slot (8)

Context Switch

Process B:

1. next_free_slot = in

2. Write file name at slot (8)

3. next_free_slot += 1

4. in = next_free_slot (9)

Context Switch

Process A:

1. next_free_slot = in (7)

Context Switch

Process B:

1. next_free_slot = in (7)

2. Write file name at slot (7)

3. next_free_slot += 1

4. in = next_free_slot (8)

Context Switch

Process A:

1. Write file name at slot (7)

2. next_free_slot += 1

3. in = next_free_slot (8)

Basic Definitions

• Race Condition: Processes access the same data concurrently, and the outcome depends on the particular order in which the access takes place.

  • Situations where two or more processes are reading or writing some shared data, and the final result depends on who runs precisely when.

  • Reasons:

    1. Exact instruction execution order cannot be predicted.

    2. Resource (file, memory, data etc.) sharing.

• Inter-Process Communication: Communication between two or more processes.

• Critical Section: The part of a program where shared resources are accessed.

Example

Processes P1, P2, and P3 sending messages to each other.

• Mutual Exclusion: Making sure that if one process is using a shared variable or file, the other process will be excluded (stopped) from doing the same thing.

Critical Section Scenario

• Process A enters the critical region.

• Process B attempts to enter but is blocked.

• Process A leaves the critical region.

• Process B enters the critical region.

• Process B leaves the critical region.

Recap - Basic Definitions

• Race Condition: Situation where two or more processes are reading or writing some shared data, and the final result depends on who runs precisely when.

  • Reasons:

    1. Exact instruction execution order cannot be predicted.

    2. Resource sharing.

• Critical Section: The part of a program where the shared resource is accessed.

• Mutual Exclusion: Ensures that only one process can access a shared resource at a time.

Solving Critical-Section Problem

Any solution must satisfy the following four conditions:

1. Mutual Exclusion: No two processes may be simultaneously inside the same critical section.

2. Bounded Waiting: No process should have to wait forever to enter a critical section.

3. Progress: No process running outside its critical region may block other processes.

4. Arbitrary Speed: No assumption can be made about the relative speed of different processes (though all processes have a non-zero speed).

Mutual Exclusion with Busy Waiting

Mechanisms for achieving mutual exclusion with busy waiting:

1. Disabling interrupts (Hardware approach)

2. Shared lock variable (Software approach)

3. Strict alteration (Software approach)

4. TSL (Test and Set Lock) instruction (Hardware approach)

5. Exchange instruction (Hardware approach)

6. Dekker’s solution (Software approach)

7. Peterson’s solution (Software approach)

Disabling Interrupts

while (true) {
    < disable interrupts >;
    < critical section >;
    < enable interrupts >;
    < remainder section>;
}

Problems:

• Unattractive or unwise to give user processes the power to turn off interrupts.

• If a process disables interrupts and never re-enables them, it can halt the entire system.

• In a multiprocessor system, disabling interrupts affects only one CPU, while others continue running and can access shared memory.

Shared Lock Variable

A shared variable lock having value 0 or 1.

• Before entering the critical region, a process checks the lock's value.

  • If the value is 0, set it to 1 and enter the critical section, then set it to 0 after leaving.

  • If the value is 1, wait until it becomes 0.

Algorithm:

while (true) {
    < set shared variable to 1>;
    < critical section >;
    < set shared variable to 0>;
    < remainder section>;
}

Problem:

• If process P0 sees lock = 0 and a context switch occurs before it can set lock = 1.

• Process P1 runs, finds lock = 0, sets lock = 1, and enters the critical region.

• P0 resumes, sets lock = 1, and enters the critical region.

• Now both processes are in the critical region, violating mutual exclusion.

Strict Alteration

• Integer variable turn keeps track of whose turn it is to enter the critical section.

• Initially, turn = 0. Process 0 enters its critical section.

• Process 1 waits in a loop continually testing turn to see when it becomes 1 (busy waiting).

• When process 0 exits, it sets turn = 1, and process 1 can enter.

• Both processes get alternate turns.

Algorithm:

Process 0:

while (TRUE) {
   while (turn != 0) /* loop */ ;
   {
    sleep();
   }
   critical_region();
   n = n + 1;
   turn = 1;
   noncritical_region();
}

Process 1:

while (TRUE) {
   while (turn != 1) /* loop */ ;
   {
    sleep();
   }
   critical_region();
   n = n – 1;
   turn = 0;
   noncritical_region();
}

Disadvantages:

• Taking turns is not a good idea when one process is much slower than the other.

• A process can be blocked by another process not in the critical region, violating progress.

• It wastes CPU time due to busy waiting.

TSL (Test and Set Lock) Instruction

Entering the region calls enter_region:

TSL REGISTER, LOCK  |copy lock variable to register set lock to 1
CMP REGISTER,#0  |was lock variable 0?
JNE enter_region  |if it was nonzero, lock was set, so loop
RET  |return to caller: critical region entered

Leaving the region calls leave_region:

MOVE LOCK,#0  |store 0 in lock variable
RET  |return to caller

The TSL Instruction:

• Reads the contents of the memory word lock into register RX and then stores a nonzero value at the memory address lock.

• Reading and storing are guaranteed to be indivisible.

• The CPU locks the memory bus to prohibit other CPUs from accessing memory until it is done.

Exchange Instruction

Entering the region calls enter_region:

MOVE REGISTER,#1  |put 1 in the register
XCHG REGISTER,LOCK |swap content of register & lock variable
CMP REGISTER,#0  |was lock variable 0?
JNE enter_region  |if it was nonzero, lock was set, so loop
RET  |return to caller: critical region entered

Leaving the region calls leave_region:

MOVE LOCK,#0  |store 0 in lock variable
RET  |return to caller

Dekker’s Algorithm

variables
wants_to_enter [2]: array of 2 booleans
turn : integer

wants_to_enter[0] ← false
wants_to_enter[1] ← false
turn ← 0 // or 1

P0:
wants_to_enter[0] ← true
while (wants_to_enter[1])
{
    if (turn == 1)
    {
        wants_to_enter[0] ← false
        while (turn == 1)
        {
            // busy wait
        }
        wants_to_enter[0] ← true
    }
}
// critical section ...
turn ← 1
wants_to_enter[0] ← false
// remainder section

P1:
wants_to_enter[1] ← true
while (wants_to_enter[0])
{
    if (turn == 0)
    {
        wants_to_enter[1] ← false
        while (turn == 0)
        {
            // busy wait
        }
        wants_to_enter[1] ← true
    }
}
// critical section ...
turn ← 0
wants_to_enter[1] ← false
// remainder section

Topics to be covered

• IPC, Race Conditions, Critical Section, Mutual Exclusion

• Hardware Solution

• Strict Alternation

• Dekker’s Algorithm

• Peterson’s Solution

• The Producer Consumer Problem

• Semaphores

• Event Counters

• Monitors

• Classical IPC Problems:

  • Reader’s & Writer Problem

  • Dinning Philosopher Problem

• Pipes and Message Passing

• Barrier and Signal

Priority Inversion Problem

• Priority inversion means the execution of a high priority process/thread is blocked by a lower priority process/thread.

• Consider a computer with two processes, H (high priority) and L (low priority).

• Scheduling rules dictate H runs first, then L.

• L is in a critical region, and H becomes ready to run.

• H begins busy waiting.

• H has higher priority, so CPU switches from L to H.

• L never gets scheduled, so L never leaves the critical region, and H loops forever.

Peterson’s Solution

#define FALSE 0
#define TRUE 1
#define N 2 //number of processes
int turn; //whose turn is it?
int interested[N]; //all values initially 0 (FALSE)

void enter_region(int process) {
    int other; // number of the other process
    other = 1 - process; // the opposite process
    interested[process] = TRUE; // this process is interested
    turn = process; // set flag
    while(turn == process && interested[other] == TRUE); // wait
}

void leave_region(int process) {
    interested[process] = FALSE; // process leaves critical region
}

Mutual Exclusion with Busy Waiting (Limitations)

1. Disabling Interrupts

   • Not appropriate as a general mutual exclusion mechanism for user processes

2. Lock Variables

   • Contains the same fatal flaw as the spooler directory example

3. Strict Alternation

   • A process running outside its critical region blocks other processes.

4. Peterson's Solution

5. The TSL/XCHG instruction

   • Both Peterson’s solution and the solutions using TSL or XCHG are correct.

   • Limitations:

     • Busy Waiting: this approach waste CPU time

     • Priority Inversion Problem: a low-priority process blocks a higher-priority one

Sleep and Wakeup

• Peterson’s solution and solution using TSL and XCHG have the limitation of requiring busy waiting.

  • When a process wants to enter its critical section, it checks to see if the entry is allowed.

  • If it is not allowed, the process goes into a loop and waits (i.e., start busy waiting) until it is allowed to enter.

  • This approach wastes CPU-time.

• Interprocess communication primitives (sleep & wakeup).

  • Sleep: System call that causes the caller to be blocked (suspended) until some other process wakes it up.

  • Wakeup: System call that wakes up the process.

  • Both calls have one parameter: memory address used to match up 'sleeps' and 'wakeups'.

Producer Consumer problem

• Multi-process synchronization problem.

• Bounded buffer problem.

• Two processes:

  • Producer: Produces information and puts it into a buffer.

  • Consumer: Consumes information (removes it from the buffer).

• Ensures the producer won’t add data into the buffer if it is full and the consumer won’t remove data from the empty buffer.

• Producer goes to sleep or discards data if the buffer is full.

• Consumer notifies the producer to put data into buffer.

• Consumer goes to sleep if the buffer is empty.

• Producer notifies the consumer to remove data from buffer.

• Buffer states:

  • Empty: Producer wants to produce, consumer wants to consume.

  • Full: Producer wants to produce, consumer wants to consume.

  • Partially filled: Producer wants to produce, consumer wants to consume.

Producer Consumer problem using Sleep & Wakeup

#define N 4
int count=0;
void producer (void) {
    int item;
    while (true) {
        item=produce_item();
        if (count==N) sleep();
        insert_item(item);
        count=count+1;
        if(count==1) wakeup(consumer);
    }
}

void consumer (void) {
    int item;
    while (true)
    {
        if (count==0) sleep();
        item=remove_item();
        count=count-1;
        if(count==N-1) wakeup(producer);
        consume_item(item);
    }
}

Problem in Sleep & Wakeup

• Contains a race condition that can lead to a deadlock.

The consumer has just read the variable count, noticed it's zero and is just about to move inside the if block.

• Just before calling sleep, the consumer is suspended and the producer is resumed.

• The producer creates an item, puts it into the buffer, and increases count.

• Because the buffer was empty prior to the last addition, the producer tries to wake up the consumer.

Unfortunately the consumer wasn't yet sleeping, and the wakeup call is lost.

• When the consumer resumes, it goes to sleep and will never be awakened again. This is because the consumer is only awakened by the producer when count is equal to 1.

• The producer will loop until the buffer is full, after which it will also go to sleep.

• Finally, both the processes will sleep forever. This solution therefore is unsatisfactory.

Semaphore

• A variable that provides an abstraction for controlling the access of a shared resource by multiple processes in a parallel programming environment.

• Types:

  • Binary semaphores:

    • Can take only 2 values (0/1).

    • Have 2 methods associated with it (up, down / lock, unlock).

    • Used to acquire locks.

  • Counting semaphores:

    • Can have possible values more than two.

Semaphore (cont…)

We want functions insert_item and remove_item such that:

• Mutually exclusive access to buffer: Only one process should be executing.

• No buffer overflow: A process executes only when the buffer is not full.

• No buffer underflow: A process executes only when the buffer is not empty.

• No busy waiting.

• No producer starvation: A process does not wait forever.

• No consumer starvation: A process does not wait forever.

Semaphores (Operations)

1. Down Operation

   • Checks if the value is greater than 0.

   • If so, decrements the value.

   • If the value is 0, the process is put to sleep.

   • Checking, changing, and sleeping are done as a single atomic action.

2. Up Operation

   • Increments the value of the semaphore.

   • If processes were sleeping, one is chosen and allowed to complete its down.

   • Incrementing and waking up are also indivisible.

Producer Consumer problem using Semaphore

#define N 4
typedef int semaphore;
semaphore mutex=1; //mutual exclusion
semaphore empty=N; //counting semaphore for empty slots
semaphore full=0; //counting semaphore for full slots

void producer (void) {
    int item;
    while (true)
    {
        item=produce_item();
        down(&empty);
        down(&mutex);
        insert_item(item);
        up(&mutex);
        up(&full);
    }
}

void consumer (void) {
    int item;
    while (true)
    {
        down(&full);
        down(&mutex);
        item=remove_item(item);
        up(&mutex);
        up(&empty);
        consume_item(item);
    }
}

Readers Writer problem

• Competing processes wishing to perform reading and writing operations in a database.

• Multiple processes can read the database at the same time.

• If one process is writing, no other processes may access the database.

Readers Writer problem using Semaphore

typedef int semaphore;
semaphore mutex=1; //control access to reader count
semaphore db=1; //control access to database
int reader_count=0; //number of processes reading database

void Writer (void) {
    while (true) {
        create_data(); //create data to write into DB (non-critical)
        down(&db); //gain access to DB
        write_db(); //write information to DB
        up(&db); //release exclusive access to DB
    }
}

void Reader (void) {
    while (true){
        down(&mutex); //gain access to reader count
        reader_count=reader_count+1; //increment reader counter
        if(reader_count==1) //if this is first process to read DB
            down(&db); //prevent writer process to access DB
        up(&mutex); //allow other process to access reader_count
        read_database();
        down(&mutex); //gain access to reader count
        reader_count=reader_count-1; //decrement reader counter
        if(reader_count==0) //if this is last process to read DB
            up(&db); //leave the control of DB, allow writer process
        up(&mutex); //allow other process to access reader_count
        use_read_data(); //use data read from DB (non-critical)
    }
}

Dinning Philosopher Problem

• Five philosophers sitting around a table, each alternating between thinking and eating.

• Each philosopher needs two forks to eat, but there are only five forks, one between each pair of philosophers.

• Task is to devise a scheme for the "Get 2 forks" step.

Problem

• Deadlock: Each philosopher can pick up the left fork before anyone picks up their right fork, resulting in everyone waiting for the right fork.

Solution 1 (Bad Solution)

Think();
Pick up left fork;
Pick up right fork;
Eat();
Put down right fork;
Put down left fork;

Solution 2 (Global Lock)

Think();
table.lock();
while(!both fork available)
    forkPutDown.await();
Pick up left fork;
Pick up right fork;
table.unlock();
Eat();
Put down right fork;
Put down left fork;
forkPutDown.signal();

Solution 3 (Reactive)

Think();
Pick up left fork;
if(right fork available) {
    Pick up right fork;
} else {
    Put down left fork;
    continue; //Go back to Thinking
}
Eat();

Solution 4 (Global Reactive)

Think();
Pick up “smaller” fork from left and right;
Pick up “bigger” fork from left and right;
Eat();
Put down “bigger” fork from left and right;
Put down “smaller” fork from left and right;

Solution to Dinning Philosopher Problem

#define N 5 //no. of philosophers
#define LEFT (i+N-1)%5 //no. of i’s left neighbor
#define RIGHT (i+1)%5 //no. of i’s right neighbor
#define THINKING 0 //Philosopher is thinking
#define HUNGRY 1 //Philosopher is trying to get forks
#define EATING 2 //Philosopher is eating
typedef int semaphore; //semaphore is special kind of int
int state[N]; //array to keep track of everyone’s state
semaphore mutex=1; //mutual exclusion for critical region
semaphore s[N]; //one semaphore per philosopher

void philosopher (int i) //i: philosopher no, from 0 to N-1
{
    while (true) {
        think(); //philosopher is thinking
        take_forks(i); //acquire two forks or block
        eat(); //eating noodles
        put_forks(i); //put both forks back on table
    }
}

void put_forks (int i) //i: philosopher no, from 0 to N-1
{
    down(&mutex); //enter critical region
    state[i]=THINKING; //philosopher has finished eating
    test(LEFT); //see if left neighbor can now eat
    test(RIGHT); // see if right neighbor can now eat
    up(&mutex); // exit critical region
}

void take_forks (int i) //i: philosopher no, from 0 to N-1
{
    down(&mutex); //enter critical region
    state[i]=HUNGRY; //record fact that philosopher i is hungry
    test(i); //try to acquire 2 forks
    up(&mutex); //exit critical region
    down(&s[i]); //block if forks were not acquired
}

void test (i) //i: philosopher no, from 0 to N-1
{
    if (state[i]==HUNGRY && state[LEFT]!=EATING && state[RIGHT]!=EATING) {
        state[i]=EATING;
        up (&s[i]);
    }
}

Monitor

• Higher-level synchronization primitive.

• A collection of procedures, variables, and data structures grouped together.

• Processes call procedures but cannot directly access internal data structures.

• Only one process can be active in a monitor at any instant.

• Uses condition variables with wait and signal operations.

Producer Consumer problem using Monitor

monitor ProducerConsumer
condition full, empty;
integer count;

procedure insert (item:integer);
begin
    if count=N then wait (full);
    insert_item(item);
    count=count+1;
    if count=1 then signal (empty);
end;

function remove:integer;
begin
    if count=0 then wait (empty);
    remove=remove_item;
    count=count-1;
    if count=N-1 then signal (full);
end;

count=0;
end monitor;

procedure producer;
begin
    while true do
    begin
        item=produce_item;
        ProducerConsumer.insert(item);
    end;
end;

procedure consumer;
begin
    while true do
    begin
        item=ProducerConsumer.remove;
        Consume_insert(item);
    end;
end;

Pipes

• Communication medium between related processes (usually parent and child).

• One process writes into the pipe, and another process reads from the pipe.

• One-way communication only.

• Opens a pipe, which is an area of main memory treated as a “virtual file”.

• It is bounded buffer means we can send only limited data through pipe.

• Accessed by two associated file descriptors:

  • fd[0] for reading from pipe

  • fd[1] for writing into the pipe

Example Code

#include<unistd.h>
#include<fcntl.h>
#include<stdio.h>

char *message = “Hey how are you”;

int main () {
    char buffer[1024];
    int fd[2];
    pipe(fd);
    if (fork() != 0) {
        write (fd[1], message, strlen (message) + 1);
    } else {
        read (fd[0], buffer, 1024);
        printf (“Received from Parent %s\n”, buffer);
    }
    return 0;
}

Message Passing

• Uses two primitives:

  • Send (destination, &message)

    • Sends a message to the specified destination process.

  • Receive (source, &message)

    • Receives a message from the specified source process.

Producer Consumer problem using message passing

#define N 100 //number of slots in buffer

void producer (void) {
    int item;
    message m;
    while (true) {
        item=produce_item();
        receive(consumer, &m); //wait for an empty to arrive
        build_message(&m, item); //construct a message to send
        send(consumer, &m); //send item to consumer
    }
}

void consumer (void) {
    int item, i;
    message m;
    for (i=0; i<N; i++)
        send (producer, &m); //send N empties
    while (true) {
        receive (producer, &m); //get message containing item
        item=extract_item(&m); //extract item from message
        send (producer, &m); //send back empty reply
        consume_item (item); //do something with the item
    }
}

Barrier

• Used to synchronize processes divided into phases.

• No process may proceed into the next phase until all processes complete the current phase.

• A barrier is placed at the end of each phase.

• When a process reaches the barrier, it is blocked until all processes have reached the barrier.

Signal

• Software interrupts sent to a program to indicate that an important event has occurred.

• When a signal is delivered to a process, the process will stop what it's doing and either handle or ignore the signal.

• Signals are mediated by the kernel and handled by processes, while interrupts are mediated by the processor and handled by the kernel.

Questions asked in GTU

1. Define following Terms: Mutual Exclusion, Critical Section, Race Condition

2. What is Semaphore? Give the implementation of Readers-Writers Problem using Semaphore

3. What is Semaphore? Give the implementation of Bounded Buffer Producer Consumer Problem using Semaphore.

4. Explain Dining philosopher solution using Semaphore.

5. What Critical section Problem and list the requirements to solve it. Write Peterson’s Solution for the same.

6. Explain Dining philosopher solution using Monitors.