Revision: 65062
Updated Code
at October 18, 2013 06:22 by naveenrn
Updated Code
/**********************************************************************************************************/
/*Author : Naveen Namashivayam*/
/*Dated : 26-Sep-2013*/
/*Implementation of Banker's Algorithm using pipes with the SJF/LLF Scheduling*/
/**********************************************************************************************************/
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <sstream>
#include <stdio.h>
#include <string>
#include <sys/types.h>
#include <unistd.h>
#include <vector>
using namespace std;
char chars[] = "()-";
int scheduleType;
//variable declaration
int numProcess, numResource, childMember, relDeadLine, totalProcessCount;
vector <int> availableResource;
vector < vector<int> > maxResourceDemand;
vector < vector<string> > processList;
vector < vector<string> > processListBuffer;
vector < vector<int> > processListMain;
vector < vector<int> > allocateResource;
vector <int> needResource;
int sortArray[15][15];
int sortArrayRerun[15][15];
int llfArrange[15][15] ;
vector < vector<string> > finalStatement;
int finalCount=0;
/*******************************************************/
//Function Name : getInputFromFile
//Functionality : To fetch the data from the input file
// With the data obtained from the input
// file, the text parsing on the same is
// completed.
/*******************************************************/
int getInputFromFile()
{
//buffer variable declaration
vector <string> buffVectorA;
ifstream infile;
int iBuff = 0, countBuff = 0, intBuff;
//input.txt file availability check
infile.open("input.txt");
if (!infile)
{
cout << "The Input File is not Open" << endl;
cin.get();
exit(1);
}
//obtaining values from input.txt file
string tmpStr;
while ( !infile.eof() )
{
std :: getline (infile, tmpStr);
buffVectorA.push_back(tmpStr);
countBuff++;
}
//feeding data to the global variables
char str[20];
istringstream ( buffVectorA[0] ) >> numResource; //getting numResource
istringstream ( buffVectorA[1] ) >> numProcess; //getting numProcess
//getting all the availableResource values
for (iBuff = 2; iBuff < buffVectorA.size(); iBuff++)
{
if ( iBuff < numResource + 2 )
{
unsigned pos = buffVectorA[iBuff].find("=");
string buffStr = buffVectorA[iBuff].substr (pos);
size_t length = buffStr.copy(str, buffStr.length() - 1, 1);
str[length] = '\0';
istringstream ( str ) >> intBuff;
availableResource.push_back(intBuff);
}
else break;
}
//getting all the maxResourceDemand value
const int rowsVector = numProcess;
const int columnsVector = numResource;
for ( iBuff = 0; iBuff < buffVectorA.size(); iBuff++ )
{
if ( ( iBuff < ( numProcess * numResource) + 1 ) && ( iBuff >= 2 ) )
{ maxResourceDemand.push_back(vector<int>()); } /* Adding an empty row */
}
for (iBuff = 0; iBuff < buffVectorA.size(); iBuff++)
{
if ( ( iBuff < ( numProcess * numResource) + numResource + 2 ) && ( iBuff >= numResource + 2 ) )
{
unsigned pos = buffVectorA[iBuff].find("=");
string buffStr = buffVectorA[iBuff].substr (pos);
size_t length = buffStr.copy(str, buffStr.length() - 1, 1);
str[length] = '\0';
istringstream ( str ) >> intBuff;
int tempInt = ((iBuff - 2) / numResource);
maxResourceDemand[tempInt - 1]. push_back(intBuff);
}
else if ( iBuff <= numResource + 1 )
{}
else break;
}
//getting all the process values
int processBuff[10], jBuff, loopBuff = 0;
string strBuff;
for ( iBuff = 0; iBuff < buffVectorA.size(); iBuff++ )
{
if ( ( iBuff > ( ( numProcess * numResource) + numResource + 1 ) ) )
{
strBuff = buffVectorA[iBuff];
if(strBuff.compare (0, 3, "end") == 0)
{
processBuff[loopBuff] = iBuff;
loopBuff = loopBuff + 1;
}
}
}
totalProcessCount = ( buffVectorA.size() - ( ( numProcess * numResource) + numResource + 2 + ( numProcess * 2 ) + ( numProcess * 2 )) );
for ( iBuff = 0; iBuff < totalProcessCount; iBuff++ )
{
processList.push_back( vector<string>() ); // Adding an empty row
}
countBuff = 0; int loop = 0;
string strBuff1, strBuff2, strBuff0;
for ( iBuff = 0; iBuff < buffVectorA.size(); iBuff++)
{
strBuff = buffVectorA[iBuff];
if( strBuff.compare (0, 7, "process") == 0 )
{
strBuff0 = buffVectorA[iBuff];
strBuff1 = buffVectorA[iBuff + 1];
strBuff2 = buffVectorA[iBuff + 2];
}
else if( ( strBuff.compare (0, 7, "request") == 0 ) || (strBuff.compare (0, 7, "release") == 0))
{
processList[countBuff].push_back(strBuff0); //Process ID
processList[countBuff].push_back(strBuff1); //deadline
processList[countBuff].push_back(strBuff2); //Computation Time
processList[countBuff].push_back(strBuff); //Request/Releaase Type
countBuff++;
}
else
{
continue;
}
}
infile.close();
}
/*******************************************************/
//Function Name : inputProcessListParsing
//Functionality : To parse the obtained Process List and
// place them in a particular format
// process_name<sp>deadline<sp>compTime<sp>
// process_ID<sp>resource<sp>
// The above format is used for parsing
/*******************************************************/
int inputProcessListParsing()
{
for (int iBuff = 0; iBuff < totalProcessCount; iBuff++ )
{
processListMain.push_back( vector<int>() ); // Adding an empty row
}
int intBuff;
string strBuffer;
char str[20];
for (int iBuff = 0; iBuff < totalProcessCount - 1; iBuff++)
{
for (int jBuff = 0; jBuff < 4; jBuff++)
{
strBuffer = processList[iBuff][jBuff];
switch(jBuff)
{
case 0:
{
//processing the process ID and retrieving values accordingly
if( strBuffer.compare (0, 7, "process") == 0 )
{
unsigned pos = strBuffer.find("_");
string buffStr = strBuffer.substr (pos);
size_t length = buffStr.copy(str, buffStr.length() - 1, 1);
str[length] = '\0';
istringstream ( str ) >> intBuff;
processListMain[iBuff].push_back(intBuff);
}
break;
}
case 1:
{
istringstream ( strBuffer ) >> intBuff;
processListMain[iBuff].push_back(intBuff);
break;
}
case 2:
{
istringstream ( strBuffer ) >> intBuff;
processListMain[iBuff].push_back(intBuff);
break;
}
case 3:
{
//processing if the obtained list is a request
if( strBuffer.compare (0, 7, "request") == 0 )
{
//cout << "1" << "\t";//printing request value as 1
processListMain[iBuff].push_back(1);
istringstream ss (strBuffer);
string token;
while(getline(ss, token, ','))
{
if ( token.compare (0, 7, "request") == 0 )
{
unsigned pos = token.find("(");
string buffStr = token.substr (pos);
size_t length = buffStr.copy(str, buffStr.length() - 1, 1);
str[length] = '\0';
istringstream ( str ) >> intBuff;
//cout << intBuff << "\t";
processListMain[iBuff].push_back(intBuff);
}
else
{
string str1;
str1 = token;
for ( unsigned int i = 0; i < strlen(chars); ++i )
str1.erase( remove( str1.begin(), str1.end(), chars[i] ), str1.end());
istringstream ( str1 ) >> intBuff;
//cout << str1 << "\t";
processListMain[iBuff].push_back(intBuff);
}
}
}
//processing if the obtained list is a release
if( strBuffer.compare (0, 7, "release") == 0 )
{
//cout << "0" << "\t";//printing request value as 1
processListMain[iBuff].push_back(0);
istringstream ss (strBuffer);
string token;
while(getline(ss, token, ','))
{
if ( token.compare (0, 7, "release") == 0 )
{
unsigned pos = token.find("(");
string buffStr = token.substr (pos);
size_t length = buffStr.copy(str, buffStr.length() - 1, 1);
str[length] = '\0';
istringstream ( str ) >> intBuff;
//cout << intBuff << "\t";
processListMain[iBuff].push_back(intBuff);
}
else
{
string str1;
str1 = token;
for ( unsigned int i = 0; i < strlen(chars); ++i )
str1.erase( remove( str1.begin(), str1.end(), chars[i] ), str1.end());
//cout << str1 << "\t";
istringstream ( str1 ) >> intBuff;
processListMain[iBuff].push_back(intBuff);
}
}
}
break ;
}
}
}
cout << endl;
}
}
/*******************************************************/
//Function Name : initAllocatedResource
//Functionality : Initializing the allocated resource
// values
/*******************************************************/
int initAllocatedResource()
{
int temp = 0;
for (int iBuff = 0; iBuff < numProcess; iBuff++ )
{
allocateResource.push_back( vector<int>() ); // Adding an empty row
}
for (int iBuff = 0; iBuff < numProcess; iBuff++ )
for (int jBuff = 0; jBuff < numResource; jBuff++ )
{
allocateResource[iBuff].push_back(temp);
}
}
/*******************************************************/
//Function Name : initFinalStatement
//Functionality : Initializing the final statement
// values
/*******************************************************/
int initFinalStatement()
{
int temp = 0;
for (int iBuff = 0; iBuff < (totalProcessCount + totalProcessCount); iBuff++ )
{
finalStatement.push_back( vector<string>() ); // Adding an empty row
}
}
/*******************************************************/
//Function Name : ShortJobFirstScheduling
//Functionality : The Process Requests and releases are
// sorted as per the Shortest Path First
// Scheduling
/*******************************************************/
int ShortJobFirstScheduling()
{
vector < vector<string> > SJFBuffer;
int intBuff;
vector < string > strBuff;
char str[20];
int count = 0;
for ( int jBuff = 0; jBuff < totalProcessCount - 1; jBuff++)
{
for ( int iBuff = 0; iBuff < totalProcessCount - 1; iBuff++)
{
if ( ( processList[iBuff][2] > processList[iBuff + 1][2] ) && ( iBuff != totalProcessCount ) )
{
strBuff = processList[iBuff];
processList[iBuff] = processList[iBuff + 1];
processList[iBuff + 1] = strBuff;
}
else
{
count++;
if( count == totalProcessCount )
break;
}
}
}
int temp1 = 0;
int temp2 = 0;
for(int i=0; i < totalProcessCount; i++)
{
cout << processList[i][0] << endl;
if((i+1) != totalProcessCount )
{
if(processList[i][0] != processList[i+1][0])
{
sortArray[temp1][temp2] = i;
temp2=0;
temp1++;
}
else
{
sortArray[temp1][temp2] = i;
temp2++;
}
}
}
}
/*******************************************************/
//Function Name : llfSort
//Functionality : sorting as per LLF and sending the pointer
/*******************************************************/
int llfSort()
{
int strBuff;
int count = 0;
for ( int jBuff = 0; jBuff < numProcess + 1; jBuff++)
{
for ( int iBuff = 0; iBuff < numProcess; iBuff++)
{
if ( ( llfArrange[iBuff][2] > llfArrange[iBuff+1][2]) && ( iBuff != numProcess ) )
{
for(int i = 0; i < 5; i++)
{
strBuff = llfArrange[iBuff][i];
llfArrange[iBuff][i] = llfArrange[iBuff + 1][i];
llfArrange[iBuff + 1][i] = strBuff;
}
}
else
{
count++;
if( count == numProcess )
break;
}
}
}
}
/*******************************************************/
//Function Name : LeastLaxityFirstScheduling
//Functionality : The Process Requests and releases are
// sorted as per the Least Laxity First
// Scheduling
/*******************************************************/
int LeastLaxityFirstScheduling()
{
vector < vector<string> > SJFBuffer;
int intBuff;
vector < string > strBuff;
char str[20];
int count = 0;
for ( int jBuff = 0; jBuff < totalProcessCount - 1; jBuff++)
{
for ( int iBuff = 0; iBuff < totalProcessCount - 1; iBuff++)
{
if ( ( processList[iBuff][2] > processList[iBuff + 1][2] ) && ( iBuff != totalProcessCount ) )
{
strBuff = processList[iBuff];
processList[iBuff] = processList[iBuff + 1];
processList[iBuff + 1] = strBuff;
}
else
{
count++;
if( count == totalProcessCount )
break;
}
}
}
int temp1 = 0;
int temp2 = 0;
for(int i=0; i < totalProcessCount; i++)
{
cout << processList[i][0] << endl;
if((i+1) != totalProcessCount )
{
if(processList[i][0] != processList[i+1][0])
{
sortArray[temp1][temp2] = i;
temp2=0;
temp1++;
}
else
{
sortArray[temp1][temp2] = i;
temp2++;
}
}
}
int temp11, temp12, temp13;
for(int i=0; i < numProcess; i++)
{
temp11 = sortArray[i][0];
istringstream ( processList[temp11][1] ) >> temp12;
istringstream ( processList[temp11][2] ) >> temp13;
::llfArrange[i][0] = temp12;
::llfArrange[i][1] = temp13;
::llfArrange[i][2] = temp12 - temp13;
::llfArrange[i][3] = 0;
::llfArrange[i][4] = i;
}
}
/*******************************************************/
//Function Name : outputPrint
//Functionality : To print the contents of the output file
// Number of Resource, Number of Process
// Available Resource, Process List are all
// displayed.
/*******************************************************/
int outputPrint()
{
cout << "*****************************************" << endl;
cout << "****INPUT DATA SUMMARY FROM input.txt****" << endl;
cout << "*****************************************" << endl;
cout << "Number of Resource : " << numResource << endl;
cout << "Number of Process : " << numProcess << endl;
cout << "Available Resource" << endl;
for (vector<int>::iterator it = availableResource.begin(); it != availableResource.end(); ++it)
std::cout << *it << " ";
cout << endl;
cout << "*********************************************************" << endl;
cout << "maximum resource" << endl;
cout << "*********************************************************" << endl;
for (int iBuff = 0; iBuff < numProcess; iBuff++)
{
for (int jBuff = 0; jBuff < numResource; jBuff++)
cout << maxResourceDemand[iBuff][jBuff] << " ";
cout << endl;
}
cout << "*********************************************************" << endl;
cout << "initial allocated resource" << endl;
cout << "*********************************************************" << endl;
for (int iBuff = 0; iBuff < numProcess; iBuff++)
{
for (int jBuff = 0; jBuff < numResource; jBuff++)
cout << allocateResource[iBuff][jBuff] << " ";
cout << endl;
}
cout << "**********************************************************" << endl;
cout << "Request and Release Scheduled Run" << endl;
cout << "**********************************************************" << endl;
}
/*******************************************************/
//Function Name : reqAllocation
//Functionality : As the safety check on the request is
// made and the return value obtained is
// safe, we can allocate the resource for
// the request
/******************************************************/
int reqAllocation(int tokenPt)
{
int temp, i, temp1;
temp1 = processListMain[tokenPt][0];
for (i = 0; i < numResource; i++)
{
temp = ::allocateResource[temp1-1][i];
::allocateResource[temp1-1][i] = temp + processListMain[tokenPt][i+4];
}
for( i = 0; i < numResource; i++)
{
temp = ::availableResource[i];
::availableResource[i] = temp - processListMain[tokenPt][i+4];
}
cout << "Available Resource" << endl;
for (vector<int>::iterator it = ::availableResource.begin(); it != ::availableResource.end(); ++it)
std::cout << *it << " ";
cout << endl;
cout << "Allocated resource" << endl;
for (int iBuff = 0; iBuff < numProcess; iBuff++)
{for (int jBuff = 0; jBuff < numResource; jBuff++)
cout << ::allocateResource[iBuff][jBuff] << " ";
cout << endl;}
for (i = 0; i < totalProcessCount - 1; i++)
processListMain[i][1] = processListMain[i][1] - processListMain[i][2];
return 0;
}
/******************************************************/
//Function Name : reqModification
//Functionality : As the safety check on the request is
// failed and hence the resource is kept
// in que and the modifications are made
// on the computation time
/******************************************************/
int reqModification(int tokenPt)
{
for (int i = 0; i < totalProcessCount - 1; i++)
processListMain[i][1] = processListMain[i][1] - 1;
}
/*******************************************************/
//Function Name : reqRelease
//Functionality : When there is a release request made,
// the corresponding Process gets released
/*******************************************************/
int reqRelease(int tokenPt)
{
int temp, i, temp1;
temp1 = processListMain[tokenPt][0];
for (i = 0; i < numResource; i++)
{
temp = ::allocateResource[temp1-1][i];
if(temp > processListMain[tokenPt][i+4]) { ::allocateResource[temp1-1][i] = temp - processListMain[tokenPt][i+4];}
else { ::allocateResource[temp1-1][i] = processListMain[tokenPt][i+4] - temp; }
}
for( i = 0; i < numResource; i++)
{
temp = ::availableResource[i];
::availableResource[i] = processListMain[tokenPt][i+4] + temp;
}
cout << "Available Resource" << endl;
for (vector<int>::iterator it = ::availableResource.begin(); it != ::availableResource.end(); ++it)
std::cout << *it << " ";
cout << endl;
cout << "Allocated resource" << endl;
for (int iBuff = 0; iBuff < numProcess; iBuff++)
{for (int jBuff = 0; jBuff < numResource; jBuff++)
cout << ::allocateResource[iBuff][jBuff] << " ";
cout << endl;}
for (i = 0; i < totalProcessCount - 1; i++)
processListMain[i][1] = processListMain[i][1] - 1;
return 0;
}
/*******************************************************/
//Function Name : bankersAlgorithmCheck
//Functionality : To check and verify the deadlock safety
// for the requested process through the
// Bankers Algorithm
/*******************************************************/
int bankersAlgorithmCheck ( int location )
{
int pointValue = location;
int maxAllocated[10][10] = {0};
int allocResource[10][10] = {0};
int needlResource[10][10] = {0};
int availResourceVector[10] = {0};
int requestResourceVector[10] = {0};
cout << "******************************" << endl;
cout << processList[pointValue][0] << endl; finalStatement[::finalCount].push_back(processList[pointValue][0]);
cout << processList[pointValue][3] << endl; finalStatement[::finalCount].push_back(processList[pointValue][3]);
//Verifying Request or Release
if ( processListMain[pointValue][3] == 0 )
{ finalStatement[::finalCount].push_back("Release Request : Released"); return 2; }
//Feeding maximum resource table
for(int i = 0; i < numResource; i++)
for(int j = 0; j < numProcess; j++)
maxAllocated[i][j] = maxResourceDemand[i][j];
//Feeding allocated resource table
for(int i = 0; i < numResource; i++)
for(int j = 0; j < numProcess;j ++)
allocResource[i][j] = allocateResource[i][j];
//Calculating the needResource table from the maxAllocated and allocResource
for(int i = 0; i < numResource; i++)
for(int j = 0; j < numProcess; j++)
needlResource[i][j] = maxAllocated[i][j] - allocResource[i][j];
//Feeding the available Resource vector
for(int i = 0; i < numResource; i++)
availResourceVector[i] = availableResource[i];
//printf( "\nEnter request vector \n");
for(int i = 0; i < numResource; i++)
requestResourceVector[i] = processListMain[pointValue][i + 4];
for(int i = 0; i < numResource; i++)
{
if(requestResourceVector[i] > availResourceVector[i])
{
puts("Error : Available Resource is less than Request");
finalStatement[::finalCount].push_back("Less Available Resource : Queued");
return 3;
}
}
//safetyChecking
for(int i = 0; i < numResource; i++)
{
availResourceVector[i] = availResourceVector[i] - requestResourceVector[i];
}
int counter = 10;
bool finish[5] = { false };
while( counter-- )
{
for(int i = 0; i < (numResource - 1); i++)
{
int flag = false;
if ( finish[i] )
continue;
for ( int j = 0; j < (numResource - 1); j++)
{
flag=true;
if( availResourceVector[j] < needlResource[i][j] )
{
flag=false;
break;
}
}
finish[i] = true;
if( finish[i] == true )
{
for( int l = 0; l < (numResource - 1); l++)
availResourceVector[l] += allocResource[i][l];
}
}
}
for(int i = 0; i < (numResource - 1); i++)
if(finish[i]==false)
{
finalStatement[::finalCount].push_back("Safety Check : Unsafe - Queued");
return 1;
}
finalStatement[::finalCount].push_back("Safety Check : Safe - Request Processed");
return 0;
}
/*******************************************************/
//Function Name : createPipe
//Functionality : To create Pipes and the child process
// calls the Bankers Algorithm, while the
// parent process based on the result
// allocates the resource or misses
// deadline
/*******************************************************/
int createPipe(int iBuff)
{
char string1[] = "The Request is in Safe State. The Resources are allocated as follows";
char string2[] = "The Request is Not in Safe State";
char string3[] = "The Resources are Released Successfully and the resources are available as shown below";
char string4[] = "DeadLine Missed";
int PFState;
int i;
i = iBuff;
int n;
int status, pid, pipefds[2];
status = pipe(pipefds);
if (status == -1)
{
perror("Trouble");
exit(1);
}
pid = fork();
if (pid == -1)
{
perror("Trouble");
exit(2);
}
else if (pid == 0)//child process
{
close(pipefds[0]);//closing child process to write
write(pipefds[1], &i, sizeof(i));//writing in child process
close(pipefds[1]);
exit(0);
}
else//parent process
{
close(pipefds[1]);
read(pipefds[0], &n, sizeof(n));//reading in parent process
PFState = bankersAlgorithmCheck(n);//bankers algorithm check in parent process
if ( PFState==0 )
{ cout << string1 << endl; reqAllocation(i); }
if ( PFState==1 )
{ cout << string2 << endl; reqModification(i); }
if ( PFState==2 )
{ cout << string3 << endl; reqRelease(i); }
if ( PFState==3)
{
int cBuff=0, dBuff=0;
for(int iB=1; iB < 15; iB++)
for(int jB=1; jB < 15; jB++)
{
if( (sortArrayRerun[iB][jB] == 0) )
{
cBuff = iB; dBuff = jB;break;
}if( (cBuff != 0) && (dBuff != 0) ){break;} else {continue;}
}
sortArrayRerun[cBuff][dBuff] = i;
}
if ( PFState==4 )
{ cout << string4 << endl; }
sleep(1);
close(pipefds[0]);//closing parent process
}
return PFState;
}
/*******************************************************/
//Function Name : releaseAll
//Functionality : Releasing all the allocated vlues
/*******************************************************/
int releaseAll()
{
cout << "*************************************************************************" << endl;
cout << "All the allocated resources will be released and then added to the available resource" << endl;
sleep(5);
for (int i = 0; i < numProcess; i++)
{
for (int j = 0; j < numResource; j++)
{
::availableResource[j] = ::allocateResource[i][j] + ::availableResource[j];
::allocateResource[i][j] = 0;
}
}
}
/*******************************************************/
//Function Name : releaseAll
//Functionality : Releasing all the allocated vlues
/*******************************************************/
int finalOutputResult()
{
system("clear");
cout << "*****************************************************" << endl;
cout << "****************** Final Result *******************" << endl;
cout << "*****************************************************" << endl;
cout << "AVAILABLE RESOURCE" << endl;
for (vector<int>::iterator it = ::availableResource.begin(); it != ::availableResource.end(); ++it)
std::cout << *it << " ";
cout << endl;
cout << "*****************************************************" << endl;
cout << "ALLOCATED RESOURCE" << endl;
for (int iBuff = 0; iBuff < numProcess; iBuff++)
{for (int jBuff = 0; jBuff < numResource; jBuff++)
cout << ::allocateResource[iBuff][jBuff] << " ";
cout << endl;}
cout << "*****************************************************" << endl;
if(scheduleType == 1) { cout << "SCHEDULING TYPE : Short Job First" << endl; }
else { cout << "SCHEDULING TYPE : Least Laxity First" << endl; }
cout << "NUMBER OF PROCESS : " << numProcess << endl;
cout << "NUMBER OF RESOURCE : " << numResource << endl;
cin.get();
cout << "The requests and releases are scheduled in the following order" << endl;
for (int iBuff = 0; iBuff < (totalProcessCount+totalProcessCount); iBuff++)
{
if(iBuff != finalCount-1)
{cout << endl;
cout << iBuff+1 ;
cout << finalStatement[iBuff][0] ;
cout << finalStatement[iBuff][1] << endl;
cout << finalStatement[iBuff][2] << endl;}
else
break;
}
}
/*******************************************************/
//Function Name : llfArrangement()
//Functionality : calculating relative deadlline and
// sending back the location pointer
/*******************************************************/
int llfArrangement()
{
int strBuff;
int count = 0;
for ( int jBuff = 0; jBuff < numProcess + 1; jBuff++)
{
for ( int iBuff = 0; iBuff < numProcess; iBuff++)
{
if ( ( llfArrange[iBuff][2] > llfArrange[iBuff+1][2]) && ( iBuff != numProcess ) )
{
for(int i = 0; i < 5; i++)
{
strBuff = llfArrange[iBuff][i];
llfArrange[iBuff][i] = llfArrange[iBuff + 1][i];
llfArrange[iBuff + 1][i] = strBuff;
}
}
else
{
count++;
if( count == numProcess )
break;
}
}
}
}
/*******************************************************/
//Function Name : main
//Functionality : The program starts here and all the fucntion
// calls are done.
/*******************************************************/
/*******************************************************/
int main()
{
int schType;
getInputFromFile();
system("clear");
cout << "***************************************************************" << endl;
cout << "****** IMPLEMENTING BANKER'S ALGORITHM USING PIPES ******" << endl;
cout << "****** SCHEDULING PROCESSES USING SJF & LLF ******" << endl;
cout << "***************************************************************" << endl;
cout << "Feed the SCHEDULING TYPE" << endl;
cout << "1. SJF" << endl << "2. LLF" << endl;
cin >> schType;
::scheduleType = schType;
switch(schType)
{
case 1:
{
ShortJobFirstScheduling();//scheduling the process
inputProcessListParsing();//text parsing and passing the necessary values
initAllocatedResource();//initializing the allocated Resource - Alloc
initFinalStatement();//initializing the final statement vector
system("clear");//clearing system for user reference
outputPrint();//output display
for(int i=0; i < 15; i++)
{
for(int j=0; j < 15; j++)
{
if( (sortArray[j][i] != 0) || ( (i==0) && (j==0) ) )
{
int iBuff = sortArray[j][i];
createPipe(iBuff);//creating pipes and calling Banker's Algorithm from the Parent Process
::finalCount++;
}
}
}
for(int i=0; i < 15; i++)
{
for(int j=0; j < 15; j++)
{
if( (sortArrayRerun[j][i] != 0) || ( (i==0) && (j==0) ) )
{
int iBuff = sortArrayRerun[j][i];
createPipe(iBuff);//creating pipes and calling Banker's Algorithm from the Parent Process
::finalCount++;
}
}
}
releaseAll();
finalOutputResult();
break;
}
case 2:
{
int maxResourceValue = 0;
LeastLaxityFirstScheduling();//scheduling the process
inputProcessListParsing();//text parsing and passing the necessary values
initAllocatedResource();//initializing the allocated Resource - Alloc
initFinalStatement();//initializing the final statement vector
system("clear");//clearing system for user reference
outputPrint();//output display
llfSort();//sorting as per the llf and identifing the initial pointer and deadline miss
for(int i=0; i < 15; i++)
{
for(int j=0; j < 15; j++)
{
if ( sortArray[i][j] != 0 )
{
if ( maxResourceValue < j ) { maxResourceValue++; }
}
}
}
for(int i=0; i < maxResourceValue; i++)
{
for(int j=1; j < numProcess+1; j++)
{
if(llfArrange[j][1] != 0)//computation time not less than 0
{
if((llfArrange[j][0] != 0) && (llfArrange[j][0] >0) )//deadline not less than 0
{
int iBuff = sortArray[ llfArrange[j][4] ] [ llfArrange[j][3] ]; cout <<iBuff << endl;
int x = createPipe(iBuff);//creating Pipe and calling Banker's Algorithm from the parent process
for(int iBuffer = 1; iBuffer < numProcess + 1; iBuffer++)
{
if ( (x == 0 ) || ( x == 1) || ( x == 2) )
{
if ( iBuffer == j ) { llfArrange[iBuffer][3]++;}//incrementing pointer
llfArrange[iBuffer][1]--;//decreasing computation time
llfArrange[iBuffer][0]--;//decreasing deadline
}
if ( (x==3) )
{
if ( iBuffer == j ) { llfArrange[iBuffer][3]++;}//incrementing pointer
llfArrange[iBuffer][0]--;//decreasing deadline alone
llfArrangement();
}
}
//for(int k=1; k <numProcess+1; k++) cout <<llfArrange[k][0]<<llfArrange[k][1]<<llfArrange[k][2]<<endl;
::finalCount++;
}
else
{
int pointValue = sortArray[llfArrange[j][4]][llfArrange[j][3]];
cout << "******************************" << endl;
cout << processList[pointValue][0] << endl; finalStatement[::finalCount].push_back(processList[pointValue][0]);
cout << processList[pointValue][3] << endl; finalStatement[::finalCount].push_back(processList[pointValue][3]);
cout << "Deadline Missed" << endl;
::finalStatement[::finalCount].push_back("Deadline Missed");
for(int iBuffer = 1; iBuffer < numProcess + 1; iBuffer++)
{
if ( iBuffer == j ) { llfArrange[iBuffer][3]++;}//incrementing pointer
}
//for(int k=1; k <numProcess+1; k++) cout <<llfArrange[k][0]<<llfArrange[k][1]<<llfArrange[k][2]<<endl;
::finalCount++;llfArrangement();
}
}
}
}
releaseAll();
finalOutputResult();
break;
}
default:
{
cout << "Invalid Entry" << endl;
}
}
cin.get();
return 0;
}
Revision: 65061
Initial Code
Initial URL
Initial Description
Initial Title
Initial Tags
Initial Language
at October 18, 2013 06:06 by naveenrn
Initial Code
/**********************************************************************************************************/
/*Author : Naveen Namashivayam UHID : 1266872*/
/*Dated : 26-Sep-2013*/
/*Implementation of Banker's Algorithm using pipes with the SJF/LLF Scheduling*/
/**********************************************************************************************************/
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <sstream>
#include <stdio.h>
#include <string>
#include <sys/types.h>
#include <unistd.h>
#include <vector>
using namespace std;
char chars[] = "()-";
int scheduleType;
//variable declaration
int numProcess, numResource, childMember, relDeadLine, totalProcessCount;
vector <int> availableResource;
vector < vector<int> > maxResourceDemand;
vector < vector<string> > processList;
vector < vector<string> > processListBuffer;
vector < vector<int> > processListMain;
vector < vector<int> > allocateResource;
vector <int> needResource;
int sortArray[15][15];
int sortArrayRerun[15][15];
int llfArrange[15][15] ;
vector < vector<string> > finalStatement;
int finalCount=0;
/*******************************************************/
//Function Name : getInputFromFile
//Functionality : To fetch the data from the input file
// With the data obtained from the input
// file, the text parsing on the same is
// completed.
/*******************************************************/
int getInputFromFile()
{
//buffer variable declaration
vector <string> buffVectorA;
ifstream infile;
int iBuff = 0, countBuff = 0, intBuff;
//input.txt file availability check
infile.open("input.txt");
if (!infile)
{
cout << "The Input File is not Open" << endl;
cin.get();
exit(1);
}
//obtaining values from input.txt file
string tmpStr;
while ( !infile.eof() )
{
std :: getline (infile, tmpStr);
buffVectorA.push_back(tmpStr);
countBuff++;
}
//feeding data to the global variables
char str[20];
istringstream ( buffVectorA[0] ) >> numResource; //getting numResource
istringstream ( buffVectorA[1] ) >> numProcess; //getting numProcess
//getting all the availableResource values
for (iBuff = 2; iBuff < buffVectorA.size(); iBuff++)
{
if ( iBuff < numResource + 2 )
{
unsigned pos = buffVectorA[iBuff].find("=");
string buffStr = buffVectorA[iBuff].substr (pos);
size_t length = buffStr.copy(str, buffStr.length() - 1, 1);
str[length] = '\0';
istringstream ( str ) >> intBuff;
availableResource.push_back(intBuff);
}
else break;
}
//getting all the maxResourceDemand value
const int rowsVector = numProcess;
const int columnsVector = numResource;
for ( iBuff = 0; iBuff < buffVectorA.size(); iBuff++ )
{
if ( ( iBuff < ( numProcess * numResource) + 1 ) && ( iBuff >= 2 ) )
{ maxResourceDemand.push_back(vector<int>()); } /* Adding an empty row */
}
for (iBuff = 0; iBuff < buffVectorA.size(); iBuff++)
{
if ( ( iBuff < ( numProcess * numResource) + numResource + 2 ) && ( iBuff >= numResource + 2 ) )
{
unsigned pos = buffVectorA[iBuff].find("=");
string buffStr = buffVectorA[iBuff].substr (pos);
size_t length = buffStr.copy(str, buffStr.length() - 1, 1);
str[length] = '\0';
istringstream ( str ) >> intBuff;
int tempInt = ((iBuff - 2) / numResource);
maxResourceDemand[tempInt - 1]. push_back(intBuff);
}
else if ( iBuff <= numResource + 1 )
{}
else break;
}
//getting all the process values
int processBuff[10], jBuff, loopBuff = 0;
string strBuff;
for ( iBuff = 0; iBuff < buffVectorA.size(); iBuff++ )
{
if ( ( iBuff > ( ( numProcess * numResource) + numResource + 1 ) ) )
{
strBuff = buffVectorA[iBuff];
if(strBuff.compare (0, 3, "end") == 0)
{
processBuff[loopBuff] = iBuff;
loopBuff = loopBuff + 1;
}
}
}
totalProcessCount = ( buffVectorA.size() - ( ( numProcess * numResource) + numResource + 2 + ( numProcess * 2 ) + ( numProcess * 2 )) );
for ( iBuff = 0; iBuff < totalProcessCount; iBuff++ )
{
processList.push_back( vector<string>() ); // Adding an empty row
}
countBuff = 0; int loop = 0;
string strBuff1, strBuff2, strBuff0;
for ( iBuff = 0; iBuff < buffVectorA.size(); iBuff++)
{
strBuff = buffVectorA[iBuff];
if( strBuff.compare (0, 7, "process") == 0 )
{
strBuff0 = buffVectorA[iBuff];
strBuff1 = buffVectorA[iBuff + 1];
strBuff2 = buffVectorA[iBuff + 2];
}
else if( ( strBuff.compare (0, 7, "request") == 0 ) || (strBuff.compare (0, 7, "release") == 0))
{
processList[countBuff].push_back(strBuff0); //Process ID
processList[countBuff].push_back(strBuff1); //deadline
processList[countBuff].push_back(strBuff2); //Computation Time
processList[countBuff].push_back(strBuff); //Request/Releaase Type
countBuff++;
}
else
{
continue;
}
}
infile.close();
}
/*******************************************************/
//Function Name : inputProcessListParsing
//Functionality : To parse the obtained Process List and
// place them in a particular format
// process_name<sp>deadline<sp>compTime<sp>
// process_ID<sp>resource<sp>
// The above format is used for parsing
/*******************************************************/
int inputProcessListParsing()
{
for (int iBuff = 0; iBuff < totalProcessCount; iBuff++ )
{
processListMain.push_back( vector<int>() ); // Adding an empty row
}
int intBuff;
string strBuffer;
char str[20];
for (int iBuff = 0; iBuff < totalProcessCount - 1; iBuff++)
{
for (int jBuff = 0; jBuff < 4; jBuff++)
{
strBuffer = processList[iBuff][jBuff];
switch(jBuff)
{
case 0:
{
//processing the process ID and retrieving values accordingly
if( strBuffer.compare (0, 7, "process") == 0 )
{
unsigned pos = strBuffer.find("_");
string buffStr = strBuffer.substr (pos);
size_t length = buffStr.copy(str, buffStr.length() - 1, 1);
str[length] = '\0';
istringstream ( str ) >> intBuff;
processListMain[iBuff].push_back(intBuff);
}
break;
}
case 1:
{
istringstream ( strBuffer ) >> intBuff;
processListMain[iBuff].push_back(intBuff);
break;
}
case 2:
{
istringstream ( strBuffer ) >> intBuff;
processListMain[iBuff].push_back(intBuff);
break;
}
case 3:
{
//processing if the obtained list is a request
if( strBuffer.compare (0, 7, "request") == 0 )
{
//cout << "1" << "\t";//printing request value as 1
processListMain[iBuff].push_back(1);
istringstream ss (strBuffer);
string token;
while(getline(ss, token, ','))
{
if ( token.compare (0, 7, "request") == 0 )
{
unsigned pos = token.find("(");
string buffStr = token.substr (pos);
size_t length = buffStr.copy(str, buffStr.length() - 1, 1);
str[length] = '\0';
istringstream ( str ) >> intBuff;
//cout << intBuff << "\t";
processListMain[iBuff].push_back(intBuff);
}
else
{
string str1;
str1 = token;
for ( unsigned int i = 0; i < strlen(chars); ++i )
str1.erase( remove( str1.begin(), str1.end(), chars[i] ), str1.end());
istringstream ( str1 ) >> intBuff;
//cout << str1 << "\t";
processListMain[iBuff].push_back(intBuff);
}
}
}
//processing if the obtained list is a release
if( strBuffer.compare (0, 7, "release") == 0 )
{
//cout << "0" << "\t";//printing request value as 1
processListMain[iBuff].push_back(0);
istringstream ss (strBuffer);
string token;
while(getline(ss, token, ','))
{
if ( token.compare (0, 7, "release") == 0 )
{
unsigned pos = token.find("(");
string buffStr = token.substr (pos);
size_t length = buffStr.copy(str, buffStr.length() - 1, 1);
str[length] = '\0';
istringstream ( str ) >> intBuff;
//cout << intBuff << "\t";
processListMain[iBuff].push_back(intBuff);
}
else
{
string str1;
str1 = token;
for ( unsigned int i = 0; i < strlen(chars); ++i )
str1.erase( remove( str1.begin(), str1.end(), chars[i] ), str1.end());
//cout << str1 << "\t";
istringstream ( str1 ) >> intBuff;
processListMain[iBuff].push_back(intBuff);
}
}
}
break ;
}
}
}
cout << endl;
}
}
/*******************************************************/
//Function Name : initAllocatedResource
//Functionality : Initializing the allocated resource
// values
/*******************************************************/
int initAllocatedResource()
{
int temp = 0;
for (int iBuff = 0; iBuff < numProcess; iBuff++ )
{
allocateResource.push_back( vector<int>() ); // Adding an empty row
}
for (int iBuff = 0; iBuff < numProcess; iBuff++ )
for (int jBuff = 0; jBuff < numResource; jBuff++ )
{
allocateResource[iBuff].push_back(temp);
}
}
/*******************************************************/
//Function Name : initFinalStatement
//Functionality : Initializing the final statement
// values
/*******************************************************/
int initFinalStatement()
{
int temp = 0;
for (int iBuff = 0; iBuff < (totalProcessCount + totalProcessCount); iBuff++ )
{
finalStatement.push_back( vector<string>() ); // Adding an empty row
}
}
/*******************************************************/
//Function Name : ShortJobFirstScheduling
//Functionality : The Process Requests and releases are
// sorted as per the Shortest Path First
// Scheduling
/*******************************************************/
int ShortJobFirstScheduling()
{
vector < vector<string> > SJFBuffer;
int intBuff;
vector < string > strBuff;
char str[20];
int count = 0;
for ( int jBuff = 0; jBuff < totalProcessCount - 1; jBuff++)
{
for ( int iBuff = 0; iBuff < totalProcessCount - 1; iBuff++)
{
if ( ( processList[iBuff][2] > processList[iBuff + 1][2] ) && ( iBuff != totalProcessCount ) )
{
strBuff = processList[iBuff];
processList[iBuff] = processList[iBuff + 1];
processList[iBuff + 1] = strBuff;
}
else
{
count++;
if( count == totalProcessCount )
break;
}
}
}
int temp1 = 0;
int temp2 = 0;
for(int i=0; i < totalProcessCount; i++)
{
cout << processList[i][0] << endl;
if((i+1) != totalProcessCount )
{
if(processList[i][0] != processList[i+1][0])
{
sortArray[temp1][temp2] = i;
temp2=0;
temp1++;
}
else
{
sortArray[temp1][temp2] = i;
temp2++;
}
}
}
}
/*******************************************************/
//Function Name : llfSort
//Functionality : sorting as per LLF and sending the pointer
/*******************************************************/
int llfSort()
{
int strBuff;
int count = 0;
for ( int jBuff = 0; jBuff < numProcess + 1; jBuff++)
{
for ( int iBuff = 0; iBuff < numProcess; iBuff++)
{
if ( ( llfArrange[iBuff][2] > llfArrange[iBuff+1][2]) && ( iBuff != numProcess ) )
{
for(int i = 0; i < 5; i++)
{
strBuff = llfArrange[iBuff][i];
llfArrange[iBuff][i] = llfArrange[iBuff + 1][i];
llfArrange[iBuff + 1][i] = strBuff;
}
}
else
{
count++;
if( count == numProcess )
break;
}
}
}
}
/*******************************************************/
//Function Name : LeastLaxityFirstScheduling
//Functionality : The Process Requests and releases are
// sorted as per the Least Laxity First
// Scheduling
/*******************************************************/
int LeastLaxityFirstScheduling()
{
vector < vector<string> > SJFBuffer;
int intBuff;
vector < string > strBuff;
char str[20];
int count = 0;
for ( int jBuff = 0; jBuff < totalProcessCount - 1; jBuff++)
{
for ( int iBuff = 0; iBuff < totalProcessCount - 1; iBuff++)
{
if ( ( processList[iBuff][2] > processList[iBuff + 1][2] ) && ( iBuff != totalProcessCount ) )
{
strBuff = processList[iBuff];
processList[iBuff] = processList[iBuff + 1];
processList[iBuff + 1] = strBuff;
}
else
{
count++;
if( count == totalProcessCount )
break;
}
}
}
int temp1 = 0;
int temp2 = 0;
for(int i=0; i < totalProcessCount; i++)
{
cout << processList[i][0] << endl;
if((i+1) != totalProcessCount )
{
if(processList[i][0] != processList[i+1][0])
{
sortArray[temp1][temp2] = i;
temp2=0;
temp1++;
}
else
{
sortArray[temp1][temp2] = i;
temp2++;
}
}
}
int temp11, temp12, temp13;
for(int i=0; i < numProcess; i++)
{
temp11 = sortArray[i][0];
istringstream ( processList[temp11][1] ) >> temp12;
istringstream ( processList[temp11][2] ) >> temp13;
::llfArrange[i][0] = temp12;
::llfArrange[i][1] = temp13;
::llfArrange[i][2] = temp12 - temp13;
::llfArrange[i][3] = 0;
::llfArrange[i][4] = i;
}
}
/*******************************************************/
//Function Name : outputPrint
//Functionality : To print the contents of the output file
// Number of Resource, Number of Process
// Available Resource, Process List are all
// displayed.
/*******************************************************/
int outputPrint()
{
cout << "*****************************************" << endl;
cout << "****INPUT DATA SUMMARY FROM input.txt****" << endl;
cout << "*****************************************" << endl;
cout << "Number of Resource : " << numResource << endl;
cout << "Number of Process : " << numProcess << endl;
cout << "Available Resource" << endl;
for (vector<int>::iterator it = availableResource.begin(); it != availableResource.end(); ++it)
std::cout << *it << " ";
cout << endl;
cout << "*********************************************************" << endl;
cout << "maximum resource" << endl;
cout << "*********************************************************" << endl;
for (int iBuff = 0; iBuff < numProcess; iBuff++)
{
for (int jBuff = 0; jBuff < numResource; jBuff++)
cout << maxResourceDemand[iBuff][jBuff] << " ";
cout << endl;
}
cout << "*********************************************************" << endl;
cout << "initial allocated resource" << endl;
cout << "*********************************************************" << endl;
for (int iBuff = 0; iBuff < numProcess; iBuff++)
{
for (int jBuff = 0; jBuff < numResource; jBuff++)
cout << allocateResource[iBuff][jBuff] << " ";
cout << endl;
}
cout << "**********************************************************" << endl;
cout << "Request and Release Scheduled Run" << endl;
cout << "**********************************************************" << endl;
}
/*******************************************************/
//Function Name : reqAllocation
//Functionality : As the safety check on the request is
// made and the return value obtained is
// safe, we can allocate the resource for
// the request
/******************************************************/
int reqAllocation(int tokenPt)
{
int temp, i, temp1;
temp1 = processListMain[tokenPt][0];
for (i = 0; i < numResource; i++)
{
temp = ::allocateResource[temp1-1][i];
::allocateResource[temp1-1][i] = temp + processListMain[tokenPt][i+4];
}
for( i = 0; i < numResource; i++)
{
temp = ::availableResource[i];
::availableResource[i] = temp - processListMain[tokenPt][i+4];
}
cout << "Available Resource" << endl;
for (vector<int>::iterator it = ::availableResource.begin(); it != ::availableResource.end(); ++it)
std::cout << *it << " ";
cout << endl;
cout << "Allocated resource" << endl;
for (int iBuff = 0; iBuff < numProcess; iBuff++)
{for (int jBuff = 0; jBuff < numResource; jBuff++)
cout << ::allocateResource[iBuff][jBuff] << " ";
cout << endl;}
for (i = 0; i < totalProcessCount - 1; i++)
processListMain[i][1] = processListMain[i][1] - processListMain[i][2];
return 0;
}
/******************************************************/
//Function Name : reqModification
//Functionality : As the safety check on the request is
// failed and hence the resource is kept
// in que and the modifications are made
// on the computation time
/******************************************************/
int reqModification(int tokenPt)
{
for (int i = 0; i < totalProcessCount - 1; i++)
processListMain[i][1] = processListMain[i][1] - 1;
}
/*******************************************************/
//Function Name : reqRelease
//Functionality : When there is a release request made,
// the corresponding Process gets released
/*******************************************************/
int reqRelease(int tokenPt)
{
int temp, i, temp1;
temp1 = processListMain[tokenPt][0];
for (i = 0; i < numResource; i++)
{
temp = ::allocateResource[temp1-1][i];
if(temp > processListMain[tokenPt][i+4]) { ::allocateResource[temp1-1][i] = temp - processListMain[tokenPt][i+4];}
else { ::allocateResource[temp1-1][i] = processListMain[tokenPt][i+4] - temp; }
}
for( i = 0; i < numResource; i++)
{
temp = ::availableResource[i];
::availableResource[i] = processListMain[tokenPt][i+4] + temp;
}
cout << "Available Resource" << endl;
for (vector<int>::iterator it = ::availableResource.begin(); it != ::availableResource.end(); ++it)
std::cout << *it << " ";
cout << endl;
cout << "Allocated resource" << endl;
for (int iBuff = 0; iBuff < numProcess; iBuff++)
{for (int jBuff = 0; jBuff < numResource; jBuff++)
cout << ::allocateResource[iBuff][jBuff] << " ";
cout << endl;}
for (i = 0; i < totalProcessCount - 1; i++)
processListMain[i][1] = processListMain[i][1] - 1;
return 0;
}
/*******************************************************/
//Function Name : bankersAlgorithmCheck
//Functionality : To check and verify the deadlock safety
// for the requested process through the
// Bankers Algorithm
/*******************************************************/
int bankersAlgorithmCheck ( int location )
{
int pointValue = location;
int maxAllocated[10][10] = {0};
int allocResource[10][10] = {0};
int needlResource[10][10] = {0};
int availResourceVector[10] = {0};
int requestResourceVector[10] = {0};
cout << "******************************" << endl;
cout << processList[pointValue][0] << endl; finalStatement[::finalCount].push_back(processList[pointValue][0]);
cout << processList[pointValue][3] << endl; finalStatement[::finalCount].push_back(processList[pointValue][3]);
//Verifying Request or Release
if ( processListMain[pointValue][3] == 0 )
{ finalStatement[::finalCount].push_back("Release Request : Released"); return 2; }
//Feeding maximum resource table
for(int i = 0; i < numResource; i++)
for(int j = 0; j < numProcess; j++)
maxAllocated[i][j] = maxResourceDemand[i][j];
//Feeding allocated resource table
for(int i = 0; i < numResource; i++)
for(int j = 0; j < numProcess;j ++)
allocResource[i][j] = allocateResource[i][j];
//Calculating the needResource table from the maxAllocated and allocResource
for(int i = 0; i < numResource; i++)
for(int j = 0; j < numProcess; j++)
needlResource[i][j] = maxAllocated[i][j] - allocResource[i][j];
//Feeding the available Resource vector
for(int i = 0; i < numResource; i++)
availResourceVector[i] = availableResource[i];
//printf( "\nEnter request vector \n");
for(int i = 0; i < numResource; i++)
requestResourceVector[i] = processListMain[pointValue][i + 4];
for(int i = 0; i < numResource; i++)
{
if(requestResourceVector[i] > availResourceVector[i])
{
puts("Error : Available Resource is less than Request");
finalStatement[::finalCount].push_back("Less Available Resource : Queued");
return 3;
}
}
//safetyChecking
for(int i = 0; i < numResource; i++)
{
availResourceVector[i] = availResourceVector[i] - requestResourceVector[i];
}
int counter = 10;
bool finish[5] = { false };
while( counter-- )
{
for(int i = 0; i < (numResource - 1); i++)
{
int flag = false;
if ( finish[i] )
continue;
for ( int j = 0; j < (numResource - 1); j++)
{
flag=true;
if( availResourceVector[j] < needlResource[i][j] )
{
flag=false;
break;
}
}
finish[i] = true;
if( finish[i] == true )
{
for( int l = 0; l < (numResource - 1); l++)
availResourceVector[l] += allocResource[i][l];
}
}
}
for(int i = 0; i < (numResource - 1); i++)
if(finish[i]==false)
{
finalStatement[::finalCount].push_back("Safety Check : Unsafe - Queued");
return 1;
}
finalStatement[::finalCount].push_back("Safety Check : Safe - Request Processed");
return 0;
}
/*******************************************************/
//Function Name : createPipe
//Functionality : To create Pipes and the child process
// calls the Bankers Algorithm, while the
// parent process based on the result
// allocates the resource or misses
// deadline
/*******************************************************/
int createPipe(int iBuff)
{
char string1[] = "The Request is in Safe State. The Resources are allocated as follows";
char string2[] = "The Request is Not in Safe State";
char string3[] = "The Resources are Released Successfully and the resources are available as shown below";
char string4[] = "DeadLine Missed";
int PFState;
int i;
i = iBuff;
int n;
int status, pid, pipefds[2];
status = pipe(pipefds);
if (status == -1)
{
perror("Trouble");
exit(1);
}
pid = fork();
if (pid == -1)
{
perror("Trouble");
exit(2);
}
else if (pid == 0)//child process
{
close(pipefds[0]);//closing child process to write
write(pipefds[1], &i, sizeof(i));//writing in child process
close(pipefds[1]);
exit(0);
}
else//parent process
{
close(pipefds[1]);
read(pipefds[0], &n, sizeof(n));//reading in parent process
PFState = bankersAlgorithmCheck(n);//bankers algorithm check in parent process
if ( PFState==0 )
{ cout << string1 << endl; reqAllocation(i); }
if ( PFState==1 )
{ cout << string2 << endl; reqModification(i); }
if ( PFState==2 )
{ cout << string3 << endl; reqRelease(i); }
if ( PFState==3)
{
int cBuff=0, dBuff=0;
for(int iB=1; iB < 15; iB++)
for(int jB=1; jB < 15; jB++)
{
if( (sortArrayRerun[iB][jB] == 0) )
{
cBuff = iB; dBuff = jB;break;
}if( (cBuff != 0) && (dBuff != 0) ){break;} else {continue;}
}
sortArrayRerun[cBuff][dBuff] = i;
}
if ( PFState==4 )
{ cout << string4 << endl; }
sleep(1);
close(pipefds[0]);//closing parent process
}
return PFState;
}
/*******************************************************/
//Function Name : releaseAll
//Functionality : Releasing all the allocated vlues
/*******************************************************/
int releaseAll()
{
cout << "*************************************************************************" << endl;
cout << "All the allocated resources will be released and then added to the available resource" << endl;
sleep(5);
for (int i = 0; i < numProcess; i++)
{
for (int j = 0; j < numResource; j++)
{
::availableResource[j] = ::allocateResource[i][j] + ::availableResource[j];
::allocateResource[i][j] = 0;
}
}
}
/*******************************************************/
//Function Name : releaseAll
//Functionality : Releasing all the allocated vlues
/*******************************************************/
int finalOutputResult()
{
system("clear");
cout << "*****************************************************" << endl;
cout << "****************** Final Result *******************" << endl;
cout << "*****************************************************" << endl;
cout << "AVAILABLE RESOURCE" << endl;
for (vector<int>::iterator it = ::availableResource.begin(); it != ::availableResource.end(); ++it)
std::cout << *it << " ";
cout << endl;
cout << "*****************************************************" << endl;
cout << "ALLOCATED RESOURCE" << endl;
for (int iBuff = 0; iBuff < numProcess; iBuff++)
{for (int jBuff = 0; jBuff < numResource; jBuff++)
cout << ::allocateResource[iBuff][jBuff] << " ";
cout << endl;}
cout << "*****************************************************" << endl;
if(scheduleType == 1) { cout << "SCHEDULING TYPE : Short Job First" << endl; }
else { cout << "SCHEDULING TYPE : Least Laxity First" << endl; }
cout << "NUMBER OF PROCESS : " << numProcess << endl;
cout << "NUMBER OF RESOURCE : " << numResource << endl;
cin.get();
cout << "The requests and releases are scheduled in the following order" << endl;
for (int iBuff = 0; iBuff < (totalProcessCount+totalProcessCount); iBuff++)
{
if(iBuff != finalCount-1)
{cout << endl;
cout << iBuff+1 ;
cout << finalStatement[iBuff][0] ;
cout << finalStatement[iBuff][1] << endl;
cout << finalStatement[iBuff][2] << endl;}
else
break;
}
}
/*******************************************************/
//Function Name : llfArrangement()
//Functionality : calculating relative deadlline and
// sending back the location pointer
/*******************************************************/
int llfArrangement()
{
int strBuff;
int count = 0;
for ( int jBuff = 0; jBuff < numProcess + 1; jBuff++)
{
for ( int iBuff = 0; iBuff < numProcess; iBuff++)
{
if ( ( llfArrange[iBuff][2] > llfArrange[iBuff+1][2]) && ( iBuff != numProcess ) )
{
for(int i = 0; i < 5; i++)
{
strBuff = llfArrange[iBuff][i];
llfArrange[iBuff][i] = llfArrange[iBuff + 1][i];
llfArrange[iBuff + 1][i] = strBuff;
}
}
else
{
count++;
if( count == numProcess )
break;
}
}
}
}
/*******************************************************/
//Function Name : main
//Functionality : The program starts here and all the fucntion
// calls are done.
/*******************************************************/
/*******************************************************/
int main()
{
int schType;
getInputFromFile();
system("clear");
cout << "***************************************************************" << endl;
cout << "****** IMPLEMENTING BANKER'S ALGORITHM USING PIPES ******" << endl;
cout << "****** SCHEDULING PROCESSES USING SJF & LLF ******" << endl;
cout << "***************************************************************" << endl;
cout << "Feed the SCHEDULING TYPE" << endl;
cout << "1. SJF" << endl << "2. LLF" << endl;
cin >> schType;
::scheduleType = schType;
switch(schType)
{
case 1:
{
ShortJobFirstScheduling();//scheduling the process
inputProcessListParsing();//text parsing and passing the necessary values
initAllocatedResource();//initializing the allocated Resource - Alloc
initFinalStatement();//initializing the final statement vector
system("clear");//clearing system for user reference
outputPrint();//output display
for(int i=0; i < 15; i++)
{
for(int j=0; j < 15; j++)
{
if( (sortArray[j][i] != 0) || ( (i==0) && (j==0) ) )
{
int iBuff = sortArray[j][i];
createPipe(iBuff);//creating pipes and calling Banker's Algorithm from the Parent Process
::finalCount++;
}
}
}
for(int i=0; i < 15; i++)
{
for(int j=0; j < 15; j++)
{
if( (sortArrayRerun[j][i] != 0) || ( (i==0) && (j==0) ) )
{
int iBuff = sortArrayRerun[j][i];
createPipe(iBuff);//creating pipes and calling Banker's Algorithm from the Parent Process
::finalCount++;
}
}
}
releaseAll();
finalOutputResult();
break;
}
case 2:
{
int maxResourceValue = 0;
LeastLaxityFirstScheduling();//scheduling the process
inputProcessListParsing();//text parsing and passing the necessary values
initAllocatedResource();//initializing the allocated Resource - Alloc
initFinalStatement();//initializing the final statement vector
system("clear");//clearing system for user reference
outputPrint();//output display
llfSort();//sorting as per the llf and identifing the initial pointer and deadline miss
for(int i=0; i < 15; i++)
{
for(int j=0; j < 15; j++)
{
if ( sortArray[i][j] != 0 )
{
if ( maxResourceValue < j ) { maxResourceValue++; }
}
}
}
for(int i=0; i < maxResourceValue; i++)
{
for(int j=1; j < numProcess+1; j++)
{
if(llfArrange[j][1] != 0)//computation time not less than 0
{
if((llfArrange[j][0] != 0) && (llfArrange[j][0] >0) )//deadline not less than 0
{
int iBuff = sortArray[ llfArrange[j][4] ] [ llfArrange[j][3] ]; cout <<iBuff << endl;
int x = createPipe(iBuff);//creating Pipe and calling Banker's Algorithm from the parent process
for(int iBuffer = 1; iBuffer < numProcess + 1; iBuffer++)
{
if ( (x == 0 ) || ( x == 1) || ( x == 2) )
{
if ( iBuffer == j ) { llfArrange[iBuffer][3]++;}//incrementing pointer
llfArrange[iBuffer][1]--;//decreasing computation time
llfArrange[iBuffer][0]--;//decreasing deadline
}
if ( (x==3) )
{
if ( iBuffer == j ) { llfArrange[iBuffer][3]++;}//incrementing pointer
llfArrange[iBuffer][0]--;//decreasing deadline alone
llfArrangement();
}
}
//for(int k=1; k <numProcess+1; k++) cout <<llfArrange[k][0]<<llfArrange[k][1]<<llfArrange[k][2]<<endl;
::finalCount++;
}
else
{
int pointValue = sortArray[llfArrange[j][4]][llfArrange[j][3]];
cout << "******************************" << endl;
cout << processList[pointValue][0] << endl; finalStatement[::finalCount].push_back(processList[pointValue][0]);
cout << processList[pointValue][3] << endl; finalStatement[::finalCount].push_back(processList[pointValue][3]);
cout << "Deadline Missed" << endl;
::finalStatement[::finalCount].push_back("Deadline Missed");
for(int iBuffer = 1; iBuffer < numProcess + 1; iBuffer++)
{
if ( iBuffer == j ) { llfArrange[iBuffer][3]++;}//incrementing pointer
}
//for(int k=1; k <numProcess+1; k++) cout <<llfArrange[k][0]<<llfArrange[k][1]<<llfArrange[k][2]<<endl;
::finalCount++;llfArrangement();
}
}
}
}
releaseAll();
finalOutputResult();
break;
}
default:
{
cout << "Invalid Entry" << endl;
}
}
cin.get();
return 0;
}
Initial URL
Initial Description
The Bankers Algorithm Implementation using the process scheduling and UNIX pipes usage
Initial Title
Bankers Algorithm and Unix Program Scheduling
Initial Tags
c++
Initial Language
C++