Process Synchronisation

• Processes can communicate with other

graph TD;
A[Processes]
B[Independent]
C[Co-operative]
A-->B
A-->C

shubham@SHUBHAMs-MacBook-Air system-design % ps | grep "chrome" | wc
       1       5      37

• Process Synchronisation can occurs in both single processor system and multi processor system.
• In single processor system this happen due to concurrent execution.

Example of Concurrent Execution

gantt
title Shortest Remaining Time First Gantt Chart
dateFormat HH:mm
axisFormat %H:%M
Initial milestone : milestone, m1, 00:00, 0m
P1 :1m
P2:1m
P3:1m
P3:1m
P4:1m
P6:1m
P6:1m
P2:3m
P5:3m
P1:7m
Final milestone : milestone,

• Synchronisation occurs with the help of global variables and shared memory.

#include <iostream>
#include <thread>
#include <chrono>
const int SIZE = 10;
char Buffer[SIZE];
int in = 0, out = 0;
int count = 0;
// P1 processor

bool stopFlag = false;

void producerThread()
{
    while (!stopFlag)
    {
        while (count == SIZE)
            ;
        Buffer[in] = 'a';
        in = (in + 1) % SIZE;
        count++;
    }
}
// P2 processor
void consumerThread()
{
    while (!stopFlag)
    {
        while (count == 0)
            ;
        char item = Buffer[out];
        out = (out + 1) % SIZE;
        count--;
    }
}

int main()
{
    std::thread producer(producerThread);
    std::thread consumer(consumerThread);
    std::this_thread::sleep_for(std::chrono::seconds(1));
    stopFlag = true;
    producer.join();
    consumer.join();
    std::cout << "Finished" << std::endl;
    return 0;
}

Problems in Process Synchronisation

- Sequence of Execution 1

Another Sequence of Execution

• Can lead to deadlocks

int x=10;
void deposit(int x){
// entry section
balance=balance+x;  // critical section //here balance value=90 initially =80
// exit section
}
void withdaw(int x){
// entry section
balance=balance-x;// critical section //here balance value=70 initially =80
//exit section
}
// only one process should be allowed to enter critical section

Goals of Synchronisation Mechanism

• Critical Section: Where we are accessing the value of shared Global variable
• due to this race condition occurs
• We can take example of Single room Washroom

Mutual Exclusion

• Only one process should be present in Critical section
• So only one person will be using the washroom at a time

Progress

• Other processes would we waiting for forst to complete
• other processes would not be blocking anthor processes that is happenning currently
• like not another person will be locking the door while one is inside the washroom and for others that are also waiting

Bounded Waiting(Fair)

• Same processes will not be running multiple times
• like same person will not be using the washrooom who already have used

Performance

• Entered process should be fast
• like entered person will have to do fast his work

Overview of Synchronisation

Disabling Interruption Implementation

• Processors before going to critical section says Hey don't interrupt me i am going to critical section
• but as we know how scheduling mechanism works
• if higher priority process acme then our os assign higher priority process for execution and stops current one
• so it is not possilble to so first statment like Disabling Interruption can not be done
• also we are allowing a process to disable interrupts also allowing an user process to disable interrupt which may cause serious issue and cause damage to system forever.
• so Disabling Interruption is not feasible
• also it is not feasible in multi processor system in single processor system we can implement this

Locks (Mutex) Implementation

• Basic building block to implement synchronisation
• we acquire the lock and go into the critical section and then we will release the lock
• i can be preempted only when lock processes are waiting for me
• Locks can be implemented both in software and hardware(most common impl.) both
• Software Impl.
  • Peterson Implementation
  • Bakery Algorithm

Semphore Implementation

• Higher level implementation than basic lock
• it has two operations wait and signal if any prcess in critical section then wait after end will signal
• for wait and signal we will use locks and will achieve atomicity

Monitors Implementation

• It is a high level language construct
• it is a class with some methods and some variables
• it is a collection of procedures, variables and data structures that are all grouped together in a special kind of module or package
• like java synchronized keyword
• put all the shared variables and methods in a class and then use synchronized keyword

Application of Synchronisation

• Thread Synchronisation
• Process Synchronisation
• Reader Writer Problem
• Dining Philosopher Problem
• Sleeping Barber Problem
• Producer Consumer Problem
• Cigarette Smoker Problem

Locking Mechanism

• Locking mechanism is used to implement synchronisation
• Locking mechanism is used to implement mutual exclusion
• Locking mechanism is used to implement atomicity

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
int mails=0;
int lock=0;
void *resume(void *arg){
    for(int i=0;i<1000000;i++){
        if(lock==1){

        }
        lock=1;
        mails++;
        lock=0;
    }
    return NULL;
}
int main(){
    pthread_t p1,p2;
    pthread_create(&p1,NULL,resume,NULL);
    pthread_create(&p2,NULL,resume,NULL);
    pthread_join(p1,NULL);
    pthread_join(p2,NULL);
    printf("Number of mails: %d\n",mails);
    return 0;

}

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
int mails=0;
pthread_mutex_t lock;
void *resume(void *arg){
    for(int i=0;i<1000000;i++){
        pthread_mutex_lock(&lock);
        mails++;
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}
int main(){
    pthread_t p1,p2;
    pthread_mutex_init(&lock,NULL);
    pthread_create(&p1,NULL,resume,NULL);
    pthread_create(&p2,NULL,resume,NULL);
    pthread_join(p1,NULL);
    pthread_join(p2,NULL);
    printf("Number of mails: %d\n",mails);
    return 0;

}
// Output: always 2000000
// Explanation: The mutex lock ensures that only one thread can access the critical section at a time.
// The other thread has to wait for the first thread to release the lock.
// so here we are working with 2 threads and each thread is incrementing the value of mails 1000000 times.

Semaphore

graph TD;
subgraph Processor 1
end
subgraph Processor 2
end
subgraph Processor 3
end
subgraph Semaphore
C
D
E
F
G
H[count=3]
end

graph TD;
subgraph Processor 1
A[Process 1]
end
subgraph Processor 2
end
subgraph Processor 3
end
subgraph Semaphore
C
D
E
F
G
H[count=2]
end

graph TD;
subgraph Processor 1
A[Process 1]
end
subgraph Processor 2
B[Process 2]
end
subgraph Processor 3
end
subgraph Semaphore
C
D
E
F
G
H[count=1]
end

graph TD;
subgraph Processor 1
A[Process 1]
end
subgraph Processor 2
B[Process 2]
end
subgraph Processor 3
I[Process 3]
end
subgraph Semaphore
C
D
E
F
G
H[count=0]
end

graph TD;
subgraph Processor 1
A[Process 1]
end
subgraph Processor 2
B[Process 2]
end
subgraph Processor 3
I[Process 3]
end
subgraph Semaphore
C
D
E
F
G
H[count=0]
end

graph TD;
subgraph Processor 1
A[Process 1]
end
subgraph Processor 2
B[Process 2]
end
subgraph Processor 3
I[Process 3]
end
subgraph Semaphore
C[C<br> Process 4]
D
E
F
G
H[count=-1]
end

graph TD;
subgraph Processor 1
A[Process 1]
end
subgraph Processor 2
B[Process 2]
end
subgraph Processor 3
I[Process 3]
end
subgraph Semaphore
C[C<br> Process 4]
D[D<br> Process 5]
E
F
G
H[count=-2]
end

graph TD;
subgraph Processor 1
A[Process 1]
end
subgraph Processor 2
B[Process 2]
end
subgraph Processor 3
I[Process 3]
end
subgraph Semaphore
C[C<br> Process 4]
D[D<br> Process 5]
E[E<br> Process 6]
F
G
H[count=-3]
end

graph TD;
subgraph Processor 1
A[Process 1]
end
subgraph Processor 2
B[Process 2 <br> Ended<br> Process 4 Came]
end
subgraph Processor 3
I[Process 3]
end
subgraph Semaphore
C[C<br> Process 4 <br> Migrated ]
D[D<br> Process 5]
E[E<br> Process 6]
F
G
H[count=-3]
end

• Above is basically Counting Semaphore : we are maintaing a count variable which is when positive represents how many processors are empty or ready to use and when negative represents how many processes are waitint in queue to exexute themselves

Binary Semaphore

struct{
  bool val;
   queue q;
}
bool S(true,empty)
void wait(){
if(S.val==1){
// it means critical section is available
S.val=0;
}
else{
// put the process in queue
// and motivate the process to sleep
}
}
void signal(){
if(S.q is empty){
S.val=1;
}
else{
// peak a process from queue
// wake up the process from queue
}
}

Monitors

• Used by JVM (Java Virtual Machine) for multi threading

class Monitor{
  int count=0;
  synchronized void increment(){
    count++;
  }
  synchronized void decrement(){
    count--;
  }
}

• synchronized keyword is used to implement monitors
• synchronized keyword is used to implement mutual exclusion
• better than locks

Priority Inversion

graph LR;
subgraph Low Priority:L
A[Entry Section]
B[Critical Section<br>Aquired by L]
C[Exit Section]
end
subgraph High Priority:H
D[Entry Section]
E[Critical Section]
F[Exit Section]
end
G[so basically here <br>higher priority<br>replace ownself]

graph LR;
subgraph Low Priority:L
A[Entry Section]
B[Critical Section<br>Aquired by L]
C[Exit Section]
end
subgraph High Priority:H
D[Entry Section]
E[Critical Section]
F[Exit Section]
end
subgraph Medium Priority:M
H[if medium will <br>replace the <br>lower then <br>it will be blocking <br>the higher thread<br>so inherit the lower<br>to higher class]
end
G[so basically here <br>higher priority<br>replace ownself]