# Problem Solving

## Group - 03

| Name | Roll No. |
| ------------------ | --------- |
| Chirayu Vithalani | AU1940160 |
| Darsh Patel | AU1940150 |
| Devanshu Magiawala | AU1940190 |

# 1.Dinning Philosopher Problem
*Solved using Semaphore and threads*

The Dining Philosopher Problem states that K philosophers seated around a circular
table with one chopstick between each pair of philosophers. There is one chopstick
between each philosopher. If a philosopher can pick up the two chopsticks next to him, he can eat. One of the adjacent followers may take up one of the chopsticks, but not both.

# Approach

One way is to use a semaphore to symbolise each chopstick.

The Philosopher tries to grasp the chopstick by using the semaphore's wait() function.

By using the signal() operation on the proper semaphores, the Philosopher can release the chopsticks.

Although the above method ensures that no two philosophers eat at the same time, it may still result in a deadlock.

Now to prevent this deadlock from happening the approach used in the code is, only allow a philosopher to pick up his chopsticks if both chopsticks are accessible.

Generic
| Philosopher | Si | S(i+1)mod5 |
| ----------- | ---- | ---------- |
| P0 | S0 | S1 |
| P1 | S1 | S2 |
| P2 | S2 | S3 |
| P3 | S3 | S4 |
| P4 | S4 | S0 |

To Remove deadlock
| Philosopher | Si | S(i+1)mod5 |
| ----------- | ---- | ---------- |
| P0 | S0 | S1 |
| P1 | S1 | S2 |
| P2 | S2 | S3 |
| P3 | S3 | S4 |
| P4 | S0 | S4 |
And so on changes will take place.

In the above table it can be seen that Si(i=0 to 4) are the semaphore for the respective philosopher here Si is the left chopstick and S(i+1)mod5 is the right chopstick.

Generic function

void Philosopher(void)
{
    while(true)
    {
    Thinking();
    take_chopstick(i);
    take_chopstick((i+1)%N);
    Eat();
    put_chopstick(i);
    put_chopstick((i+1)%N);
    }
}

Semaphore function

void Philosopher(void)
{
    while(true)
    {
    Thinking();
    wait(take_chopstick(i));
    wait(take_chopstick((i+1)%N));
    Eat();
    signal(put_chopstick(i));
    signal(put_chopstick((i+1)%N));
    }
}

Here the Si values are all initialized as 1. Now as P0 takes S0 the initialized value changes to 0 and when it is put back it changes to 1 again.

*Note: Here two independent philosopher can always eat as the have no common chopstick to use*

# Algorithm

1. Define the No. of philosophers
2. Declare one thread per philosopher
3. Declare one semaphore per philosopher (Here semaphore represents chopstick)
4. When a philosopher is hungry
1. See if chopsticks on both sides are free
2. Acquire both chopsticks or
3. eat
4. restore the chopsticks
5. If chopsticks aren’t free
5. Wait till they are available

# Code

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>  
#include <pthread.h> 
#define Count_Phil 5


// Binary Semaphores to keep track of Philosopher
int chopsticks[Count_Phil];

// Functions for philosophers
void *Phil_Behave(void* id)
{   
    int no_of_phil = *((int*)id);

    // loop for philosopher
    while(1)
    {
        // Thinking
        printf("PID : (%ld)  Philosopher %d is THINKING\n", pthread_self(), no_of_phil+1);
        sleep(1);
        
        // Hungry
        printf("PID : (%ld)  Philosopher %d is Hungry\n", pthread_self(), no_of_phil+1);

        //Philosopher eating with chopstick
        while(1)
        {
            // Check for Chopsticks Availability
            // Check n pick left chopstick
            if(chopsticks[no_of_phil] == 1)
                continue;            
            // check n pick right Chopstick
            if(chopsticks[(no_of_phil+1)%Count_Phil] == 1)
                continue;

            chopsticks[no_of_phil] = 1;
            chopsticks[(no_of_phil+1)%Count_Phil] = 1;

            printf("PID : (%ld)  Philosopher %d picks #%d and #%d chopsticks up\n", pthread_self(), no_of_phil+1, no_of_phil+1, 1 + ((no_of_phil+1)%Count_Phil));
            printf("PID : (%ld)  Philosopher %d is Eating Noodles\n", pthread_self(), no_of_phil+1);
            sleep(1);

            //Free the Chopsticks
            chopsticks[no_of_phil] = 0;
            chopsticks[(no_of_phil+1)%Count_Phil] = 0;
            
            printf("PID : (%ld)  Philosopher %d puts #%d and #%d chopsticks down\n", pthread_self(), no_of_phil+1, no_of_phil+1, 1 + ((no_of_phil+1)%Count_Phil));
            break;
        }
    }
}

// This function reverses the Semaphores for the last of the philosopher to prevent a deadlock situation 
void *Phil_Behave_rev(void* id)
{
    int no_of_phil = *((int*)id);

    // Endless loop for philosopher
    while(1)
    {
        // Thinking
        printf("PID : (%ld)  Philosopher %d is THINKING\n", pthread_self(), no_of_phil+1);
        sleep(1);
        
        // Hungry 
        printf("PID : (%ld)  Philosopher %d is Hungry\n", pthread_self(), no_of_phil+1);

        //Philosopher eating with chopstick
        while(1)
        {
            // Check for Chopsticks Availability

            // check n pick right Chopstick
            if(chopsticks[(no_of_phil+1)%Count_Phil] == 1)
                continue;

            // Check n pick left chopstick
            if(chopsticks[no_of_phil] == 1)
                continue;            
            
            chopsticks[(no_of_phil+1)%Count_Phil] = 1;
            chopsticks[no_of_phil] = 1;

            printf("PID : (%ld)  Philosopher %d picks #%d and #%d chopsticks up\n", pthread_self(), no_of_phil+1, no_of_phil+1, 1 + ((no_of_phil+1)%Count_Phil));

            
            printf("PID : (%ld)  Philosopher %d is Eating Noodles\n", pthread_self(), no_of_phil+1);
            sleep(1);

            // Free the Chopsticks
            chopsticks[no_of_phil] = 0;
            chopsticks[(no_of_phil+1)%Count_Phil] = 0;
            
            printf("PID : (%ld)  Philosopher %d puts #%d and #%d chopsticks down\n", pthread_self(), no_of_phil+1, no_of_phil+1, 1 + ((no_of_phil+1)%Count_Phil));

            break;
        }
    }
}

int main(int argc, char const *argv[])
{
    // Declare thread array
    pthread_t thread_ids[Count_Phil];
    int no_of_phils[Count_Phil];
    
    // Setting the Philosopher Numbers
    for (int i = 0; i < Count_Phil; i++)
    {
        no_of_phils[i] = i;
    }

    // Setting the state of all Chopsticks as 0
    for (int i = 0; i < Count_Phil; i++)
    {
        chopsticks[i] = 0;
    }

    // Thread Creation
    for (int i = 0; i < Count_Phil-1; i++)
    {
        pthread_create(&thread_ids[i], NULL, Phil_Behave, (void*)&no_of_phils[i]); 
    }

    // Reversing the last philosophers semaphore to prevent deadlock
    pthread_create(&thread_ids[Count_Phil-1], NULL, Phil_Behave_rev,(void*) &no_of_phils[Count_Phil-1]); 

    // Wait equivalent
    for (int i = 0; i < Count_Phil; i++)
    {
        pthread_join(thread_ids[i], NULL); 
    }

    exit(0);
}

# Output

PID : (1)  Philosopher 1 is THINKING
PID : (3)  Philosopher 3 is THINKING
PID : (5)  Philosopher 5 is THINKING
PID : (2)  Philosopher 2 is THINKING
PID : (4)  Philosopher 4 is THINKING
PID : (5)  Philosopher 5 is Hungry
PID : (1)  Philosopher 1 is Hungry
PID : (3)  Philosopher 3 is Hungry
PID : (1)  Philosopher 1 picks #1 and #2 chopsticks up
PID : (1)  Philosopher 1 is Eating Noodles
PID : (4)  Philosopher 4 is Hungry
PID : (3)  Philosopher 3 picks #3 and #4 chopsticks up
PID : (2)  Philosopher 2 is Hungry
PID : (3)  Philosopher 3 is Eating Noodles
PID : (3)  Philosopher 3 puts #3 and #4 chopsticks down
PID : (3)  Philosopher 3 is THINKING
PID : (4)  Philosopher 4 picks #4 and #5 chopsticks up
PID : (4)  Philosopher 4 is Eating Noodles
PID : (1)  Philosopher 1 puts #1 and #2 chopsticks down
PID : (1)  Philosopher 1 is THINKING
PID : (2)  Philosopher 2 picks #2 and #3 chopsticks up
PID : (2)  Philosopher 2 is Eating Noodles
PID : (4)  Philosopher 4 puts #4 and #5 chopsticks down
PID : (4)  Philosopher 4 is THINKING
PID : (5)  Philosopher 5 picks #5 and #1 chopsticks up
PID : (5)  Philosopher 5 is Eating Noodles
PID : (1)  Philosopher 1 is Hungry
PID : (3)  Philosopher 3 is Hungry
PID : (2)  Philosopher 2 puts #2 and #3 chopsticks down
PID : (2)  Philosopher 2 is THINKING
PID : (3)  Philosopher 3 picks #3 and #4 chopsticks up
PID : (3)  Philosopher 3 is Eating Noodles

# Note

The strength could be that no deadlock will occur in any situation. Because if philosopher 1 is eating now and philosopher 2 wants to eat, philosopher 1 will move into a thinking mode and philosopher 2 will begin eating. No philosopher will perish as a result of hunger in this solution.

One flaw could be that no two philosophers can eat at the same time.
Another flaw could be that we haven't given philosophers enough credence. In the beginning, we're simply giving the 0th philosopher priority over the other four.

# 2.Producer-consumer Problem

Producer consumer problem is also recognised as bounded buffer problem. Here, There are 2 processes. These two are consumer and producer, here they share a fixed size buffer.The function that is to be performed by the producer is to produce data (item) and place them inside buffer. The function of consumer is simply just to remove data (items) from buffer and consume it. The resitriction here is that the producer when the buffer is full the data production by the producer should be halted and when the buffer is empty, the consumer shouldn't destry any data.

Potential Problems in Producer-Consumer:
- The producer only produces data when the buffer is not filled. If the buffer is filled, the producer shouldn't allowed put any data inside the buffer.
- The consumer consumes data when the buffer is not empty. In case the buffer is empty, the the consumer isn't allowed to take any data from inside the buffer.
- The buffer shouldn't be accessed the producer and consumer at the same time.

# Understanding the Problem:

- "in" used inside producer code portrayes the next empty buffer
- "out" used inside consumer code portrayes that first filled buffer
- "count" keeps the track of the number of elements inside buffer
- "count" is again separated into 3 lines code that is present inside block (both the producer and consumer code)

# Approach:
- We will be using Semaphore and Mutex
We will utilize the header file and also declare a semaphore of type sem_t (in c)
Methods that are used with semaphore (in c)
-> Initialising the semaphore to some initial value
-> Using wait() operation
-> The next step is Signal() operation (from library)
-> Followed by destroying the semaphore to avoid memory leak

Again using header file and declaring a mutex of type pthread_mutex_t (in c).
- Semaphore can be utilized in some important methods that (in c)
1. pthread_mutex_init is used for initialising the mutex
2. pthread_mutex_lock() is similar to wait() operation
3. pthread_mutex_unlock() resembles Signal() operation
4. pthread_mutex_destroy() also destroys the mutex to avoid memory leak

# Code:

#include <stdio.h>
#include <semaphore.h>
#include <stdlib.h>
#include <pthread.h>

#define MaxItems 5 
#define BufferSize 5 // Size 

sem_t empty;
sem_t full;
int in = 0;
int out = 0;
int buffer[BufferSize];
pthread_mutex_t mutex;

void *producer(void *pno)
{   
    int item;
    for(int i = 0; i < MaxItems; i++) {
        item = rand(); // Produce an random item
        sem_wait(&empty);
        pthread_mutex_lock(&mutex);
        buffer[in] = item;
        printf("Producer %d: Insert Item %d at %d\n", *((int *)pno),buffer[in],in);
        in = (in+1)%BufferSize;
        pthread_mutex_unlock(&mutex);
        sem_post(&full);
    }
}
void *consumer(void *cno)
{   
    for(int i = 0; i < MaxItems; i++) {
        sem_wait(&full);
        pthread_mutex_lock(&mutex);
        int item = buffer[out];
        printf("Consumer %d: Remove Item %d from %d\n",*((int *)cno),item, out);
        out = (out+1)%BufferSize;
        pthread_mutex_unlock(&mutex);
        sem_post(&empty);
    }
}

int main()
{   

    pthread_t pro[5],con[5];
    pthread_mutex_init(&mutex, NULL);
    sem_init(&empty,0,BufferSize);
    sem_init(&full,0,0);

    int a[5] = {1,2,3,4,5}; //Just used for numbering the producer and consumer

    for(int i = 0; i < 5; i++) {
        pthread_create(&pro[i], NULL, (void *)producer, (void *)&a[i]);
    }
    for(int i = 0; i < 5; i++) {
        pthread_create(&con[i], NULL, (void *)consumer, (void *)&a[i]);
    }

    for(int i = 0; i < 5; i++) {
        pthread_join(pro[i], NULL);
    }
    for(int i = 0; i < 5; i++) {
        pthread_join(con[i], NULL);
    }

    pthread_mutex_destroy(&mutex);
    sem_destroy(&empty);
    sem_destroy(&full);

    return 0;
    
}

# Output:


# 3. Readers and Writers problem

## Problem Statement

If one notebook exists where writers may write information, only one writer may write at a time. Confusion may arise if a reader is trying to read at the same time as a writer is writing. Since readers only look at the data but do not modify the data, we can allow more than one reader to read at the same time. The main complexity of these problems stems from allowing more than one reader to access the data at the same time.

## Solution

- Let’s assume there is a shared resource which can be accessed by both readers and the writers. However, the constraint is that no two writers can write on the shared resource at the same time as well as no reader will be allowed to read the resource if a writer is updating the value of the resource. Multiple readers will be allowed to read the resource at the cost of starving the writer.
- Thus, preference is given to the reader in this situation and it is defined as “no reader shall be kept waiting if the shared resource is currently opened for reading”

## Approach

- We will keep two semaphores “rw” and “m”, one will be shared between readers and writers for maintaining synchronization while the other one will keep track of the current number of readers reading the shared resource.
- Let’s assume a reader accesses the resource and if it is the only reader at the current time, the semaphore “rw” will be locked which will prohibit the entry of writers.
- The semaphore “m” will be locked and released every time there is a new reader for the shared resource.
- When the last reader is about to leave, it will release the “rw” semaphore which will allow the writer to access the shared resource
- When a writer accesses the shared resource, it will lock the “rw” semaphore which will prevent any reader or writer from gaining the access to the shared resource.
- As soon as the writer is done updating the value of the shared resource, it will release the “rw” semaphore so any reader or writer in the queue can access it.


### Reference :- Operating System Concepts with Java - 8th Edition

## Code

#include <bits/stdc++.h>
#include <pthread.h>
#include <mutex>
#include <semaphore.h>
using namespace std;

sem_t rw; //This semaphore is the reader writer semaphore which allow syncronization between readers and writers 
sem_t m;  // This semaphore protects the variable which counts the current number of readers of the shared variable
int numOfReaders = 0;
int numOfWriters = 0;

void *reader(void *x);  //Function for reader thread
void *writer(void *y);  //Function for writer thread
int valOfResource = 7;  //Initial value of the resource which will be shared by readers and writers
int currReader=1;
int currWriter=1;

int main()

{
    sem_init(&rw, 0, 1);
    sem_init(&m, 0, 1);
    int r = 5, w = 2;
    cout << "There are total 5 readers and 2 writers"
         << "\n";

    pthread_t readerThread[5];
    pthread_t writerThread[2];

    pthread_attr_t attr;
    pthread_attr_init(&attr);

    //The following thread creation is the sequence in which readers and writers are in the queue to access the shared variable
    //Reader1, Reader2, Writer1, Reader3, Reader4, Writer2, Reader5

    pthread_create(&readerThread[0], &attr, reader, (void *)1);
    pthread_create(&readerThread[1], &attr, reader, (void *)2);
    pthread_create(&writerThread[0], &attr, writer, (void *)1);
    pthread_create(&readerThread[2], &attr, reader, (void *)3);
    pthread_create(&readerThread[3], &attr, reader, (void *)4);
    pthread_create(&writerThread[1], &attr, writer, (void *)2);
    pthread_create(&readerThread[4], &attr, reader, (void *)5);

    pthread_join(readerThread[0], NULL);
    pthread_join(readerThread[1], NULL);
    pthread_join(writerThread[0], NULL);
    pthread_join(readerThread[2], NULL);
    pthread_join(readerThread[3], NULL);
    pthread_join(writerThread[1], NULL);
    pthread_join(readerThread[4], NULL);

    return 0;
}

void *reader(void *x)
{

    sem_wait(&m); 
    numOfReaders++;
    if (numOfReaders == 1)
    {
        sem_wait(&rw);  //This semaphore will prohibit the writers to access shared resource as it is the only reader currently accessing the resource.
    }

    cout << "Reader" << currReader << " is reading the value of the resource "
         << "\n";
         currReader++;

    cout << "Value of the resource = ";
    cout << valOfResource << "\n";

    sem_post(&m);
    sem_wait(&m);

    numOfReaders--;

    if (numOfReaders == 0)
    {
        sem_post(&rw); //This semaphore will allow the writers to access shared resource as there are no readers currently
    }

    sem_post(&m);

    pthread_exit(0);
}

void *writer(void *y)

{
    sem_wait(&rw); //This semaphore will prohibit any reader from reading the value and any writer from updating the value
    cout << "Current value of the resource is ";
    cout << valOfResource << "\n";
    cout << "Writer" << currWriter << " is updating the value of resource"
         << "\n";
    currWriter++;

    numOfWriters++;
    valOfResource += 8;
    cout << "Updated value of the resource is ";
    cout << valOfResource << "\n";

    sem_post(&rw);

    pthread_exit(0);
}

## Output


## Note

- This algorithm provides preference to the readers and may starve the writers if the readers are in large numbers.
- Hence, writers may starve in this situation as each writer has to individually access the entry to the shared resource.