Question

1. (Full Program)Write code that shows how deadlocks work. Then write code that shows a fix using semaphores.

1. (Full program)Write code showing the elevator algorithm.

c++ Language

Answer 1

a) Dining philosophers problem using semaphore in c++:

#include<iostream>

#define n 4

using namespace std;

int compltedPhilo = 0,i;

struct fork{
   int taken;
}ForkAvil[n];

struct philosp{
   int left;
   int right;
}Philostatus[n];

void goForDinner(int philID){ //same like threads concept here cases implemented
   if(Philostatus[philID].left==10 && Philostatus[philID].right==10)
cout<<"Philosopher "<<philID+1<<" completed his dinner\n";
   //if already completed dinner
   else if(Philostatus[philID].left==1 && Philostatus[philID].right==1){
//if just taken two forks
cout<<"Philosopher "<<philID+1<<" completed his dinner\n";

Philostatus[philID].left = Philostatus[philID].right = 10; //remembering that he completed dinner by assigning value 10
int otherFork = philID-1;

if(otherFork== -1)
otherFork=(n-1);

ForkAvil[philID].taken = ForkAvil[otherFork].taken = 0; //releasing forks
cout<<"Philosopher "<<philID+1<<" released fork "<<philID+1<<" and fork "<<otherFork+1<<"\n";
compltedPhilo++;
}
else if(Philostatus[philID].left==1 && Philostatus[philID].right==0){ //left already taken, trying for right fork
if(philID==(n-1)){
if(ForkAvil[philID].taken==0){ //KEY POINT OF THIS PROBLEM, THAT LAST PHILOSOPHER TRYING IN reverse DIRECTION
ForkAvil[philID].taken = Philostatus[philID].right = 1;
cout<<"Fork "<<philID+1<<" taken by philosopher "<<philID+1<<"\n";
}else{
cout<<"Philosopher "<<philID+1<<" is waiting for fork "<<philID+1<<"\n";
}
}else{ //except last philosopher case
int dupphilID = philID;
philID-=1;

if(philID== -1)
philID=(n-1);

if(ForkAvil[philID].taken == 0){
ForkAvil[philID].taken = Philostatus[dupphilID].right = 1;
cout<<"Fork "<<philID+1<<" taken by Philosopher "<<dupphilID+1<<"\n";
}else{
cout<<"Philosopher "<<dupphilID+1<<" is waiting for Fork "<<philID+1<<"\n";
}
}
}
else if(Philostatus[philID].left==0){ //nothing taken yet
if(philID==(n-1)){
if(ForkAvil[philID-1].taken==0){ //KEY POINT OF THIS PROBLEM, THAT LAST PHILOSOPHER TRYING IN reverse DIRECTION
ForkAvil[philID-1].taken = Philostatus[philID].left = 1;
cout<<"Fork "<<philID<<" taken by philosopher "<<philID+1<<"\n";
}else{
cout<<"Philosopher "<<philID+1<<" is waiting for fork "<<philID<<"\n";
}
}else{ //except last philosopher case
if(ForkAvil[philID].taken == 0){
ForkAvil[philID].taken = Philostatus[philID].left = 1;
cout<<"Fork "<<philID+1<<" taken by Philosopher "<<philID+1<<"\n";
}else{
cout<<"Philosopher "<<philID+1<<" is waiting for Fork "<<philID+1<<"\n";
}
}
}else{}
}

int main(){
   for(i=0;i<n;i++)
ForkAvil[i].taken=Philostatus[i].left=Philostatus[i].right=0;

   while(compltedPhilo<n){
       /* Observe here carefully, while loop will run until all philosophers complete dinner
       Actually problem of deadlock occur only thy try to take at same time
       This for loop will say that they are trying at same time. And remaining status will print by go for dinner function
       */
       for(i=0;i<n;i++)
goForDinner(i);
       cout<<"\nTill now num of philosophers completed dinner are "<<compltedPhilo<<"\n\n";
   }

   return 0;
}

*********************************************************************************************************************************************

b) Elevator algorithm in c++:

// C++ program to demonstrate

// SCAN Disk Scheduling algorithm

  

#include <bits/stdc++.h>

using namespace std;

  

int size = 8;

int disk_size = 200;

  

void SCAN(int arr[], int head, string direction)

{

    int seek_count = 0;

    int distance, cur_track;

    vector<int> left, right;

    vector<int> seek_sequence;

  

    // appending end values

    // which has to be visited

    // before reversing the direction

    if (direction == "left")

        left.push_back(0);

    else if (direction == "right")

        right.push_back(disk_size - 1);

  

    for (int i = 0; i < size; i++) {

        if (arr[i] < head)

            left.push_back(arr[i]);

        if (arr[i] > head)

            right.push_back(arr[i]);

    }

  

    // sorting left and right vectors

    std::sort(left.begin(), left.end());

    std::sort(right.begin(), right.end());

  

    // run the while loop two times.

    // one by one scanning right

    // and left of the head

    int run = 2;

    while (run--) {

        if (direction == "left") {

            for (int i = left.size() - 1; i >= 0; i--) {

                cur_track = left[i];

  

                // appending current track to seek sequence

                seek_sequence.push_back(cur_track);

  

                // calculate absolute distance

                distance = abs(cur_track - head);

  

                // increase the total count

                seek_count += distance;

  

                // accessed track is now the new head

                head = cur_track;

            }

            direction = "right";

        }

        else if (direction == "right") {

            for (int i = 0; i < right.size(); i++) {

                cur_track = right[i];

                // appending current track to seek sequence

                seek_sequence.push_back(cur_track);

  

                // calculate absolute distance

                distance = abs(cur_track - head);

  

                // increase the total count

                seek_count += distance;

  

                // accessed track is now new head

                head = cur_track;

            }

            direction = "left";

        }

    }

  

    cout << "Total number of seek operations = "

         << seek_count << endl;

  

    cout << "Seek Sequence is" << endl;

  

    for (int i = 0; i < seek_sequence.size(); i++) {

        cout << seek_sequence[i] << endl;

    }

}

  

// Driver code

int main()

{

  

    // request array

    int arr[size] = { 176, 79, 34, 60,

                      92, 11, 41, 114 };

    int head = 50;

    string direction = "left";

  

    SCAN(arr, head, direction);

  

    return 0;

}

**********************************************************************************************************************************************