Posted By

naveenrn on 10/18/13


Tagged

algorithm process scheduling c++ FIFO Bankers SJF LLF


Versions (?)

Bankers Algorithm and Unix Program Scheduling


 / Published in: C++
 

The Bankers Algorithm Implementation using the process scheduling and UNIX pipes usage

  1. /**********************************************************************************************************/
  2. /*Author : Naveen Namashivayam*/
  3. /*Dated : 26-Sep-2013*/
  4. /*Implementation of Banker's Algorithm using pipes with the SJF/LLF Scheduling*/
  5. /**********************************************************************************************************/
  6.  
  7. #include <algorithm>
  8. #include <cstdio>
  9. #include <cstdlib>
  10. #include <cstring>
  11. #include <deque>
  12. #include <fstream>
  13. #include <iostream>
  14. #include <list>
  15. #include <sstream>
  16. #include <stdio.h>
  17. #include <string>
  18. #include <sys/types.h>
  19. #include <unistd.h>
  20. #include <vector>
  21.  
  22. using namespace std;
  23.  
  24. char chars[] = "()-";
  25.  
  26. int scheduleType;
  27. //variable declaration
  28. int numProcess, numResource, childMember, relDeadLine, totalProcessCount;
  29. vector <int> availableResource;
  30. vector < vector<int> > maxResourceDemand;
  31. vector < vector<string> > processList;
  32. vector < vector<string> > processListBuffer;
  33. vector < vector<int> > processListMain;
  34. vector < vector<int> > allocateResource;
  35. vector <int> needResource;
  36. int sortArray[15][15];
  37. int sortArrayRerun[15][15];
  38. int llfArrange[15][15] ;
  39. vector < vector<string> > finalStatement;
  40. int finalCount=0;
  41.  
  42. /*******************************************************/
  43. //Function Name : getInputFromFile
  44. //Functionality : To fetch the data from the input file
  45. // With the data obtained from the input
  46. // file, the text parsing on the same is
  47. // completed.
  48. /*******************************************************/
  49. int getInputFromFile()
  50. {
  51. //buffer variable declaration
  52. vector <string> buffVectorA;
  53. ifstream infile;
  54. int iBuff = 0, countBuff = 0, intBuff;
  55.  
  56. //input.txt file availability check
  57. infile.open("input.txt");
  58. if (!infile)
  59. {
  60. cout << "The Input File is not Open" << endl;
  61. cin.get();
  62. exit(1);
  63. }
  64.  
  65. //obtaining values from input.txt file
  66. string tmpStr;
  67. while ( !infile.eof() )
  68. {
  69. std :: getline (infile, tmpStr);
  70. buffVectorA.push_back(tmpStr);
  71. countBuff++;
  72. }
  73.  
  74. //feeding data to the global variables
  75. char str[20];
  76. istringstream ( buffVectorA[0] ) >> numResource; //getting numResource
  77. istringstream ( buffVectorA[1] ) >> numProcess; //getting numProcess
  78. //getting all the availableResource values
  79. for (iBuff = 2; iBuff < buffVectorA.size(); iBuff++)
  80. {
  81. if ( iBuff < numResource + 2 )
  82. {
  83. unsigned pos = buffVectorA[iBuff].find("=");
  84. string buffStr = buffVectorA[iBuff].substr (pos);
  85. size_t length = buffStr.copy(str, buffStr.length() - 1, 1);
  86. str[length] = '\0';
  87. istringstream ( str ) >> intBuff;
  88. availableResource.push_back(intBuff);
  89. }
  90. else break;
  91. }
  92.  
  93. //getting all the maxResourceDemand value
  94. const int rowsVector = numProcess;
  95. const int columnsVector = numResource;
  96. for ( iBuff = 0; iBuff < buffVectorA.size(); iBuff++ )
  97. {
  98. if ( ( iBuff < ( numProcess * numResource) + 1 ) && ( iBuff >= 2 ) )
  99. { maxResourceDemand.push_back(vector<int>()); } /* Adding an empty row */
  100. }
  101. for (iBuff = 0; iBuff < buffVectorA.size(); iBuff++)
  102. {
  103. if ( ( iBuff < ( numProcess * numResource) + numResource + 2 ) && ( iBuff >= numResource + 2 ) )
  104. {
  105. unsigned pos = buffVectorA[iBuff].find("=");
  106. string buffStr = buffVectorA[iBuff].substr (pos);
  107. size_t length = buffStr.copy(str, buffStr.length() - 1, 1);
  108. str[length] = '\0';
  109. istringstream ( str ) >> intBuff;
  110. int tempInt = ((iBuff - 2) / numResource);
  111. maxResourceDemand[tempInt - 1]. push_back(intBuff);
  112. }
  113. else if ( iBuff <= numResource + 1 )
  114. {}
  115. else break;
  116. }
  117.  
  118. //getting all the process values
  119. int processBuff[10], jBuff, loopBuff = 0;
  120. string strBuff;
  121. for ( iBuff = 0; iBuff < buffVectorA.size(); iBuff++ )
  122. {
  123. if ( ( iBuff > ( ( numProcess * numResource) + numResource + 1 ) ) )
  124. {
  125. strBuff = buffVectorA[iBuff];
  126. if(strBuff.compare (0, 3, "end") == 0)
  127. {
  128. processBuff[loopBuff] = iBuff;
  129. loopBuff = loopBuff + 1;
  130. }
  131. }
  132. }
  133. totalProcessCount = ( buffVectorA.size() - ( ( numProcess * numResource) + numResource + 2 + ( numProcess * 2 ) + ( numProcess * 2 )) );
  134. for ( iBuff = 0; iBuff < totalProcessCount; iBuff++ )
  135. {
  136. processList.push_back( vector<string>() ); // Adding an empty row
  137. }
  138. countBuff = 0; int loop = 0;
  139. string strBuff1, strBuff2, strBuff0;
  140. for ( iBuff = 0; iBuff < buffVectorA.size(); iBuff++)
  141. {
  142. strBuff = buffVectorA[iBuff];
  143. if( strBuff.compare (0, 7, "process") == 0 )
  144. {
  145. strBuff0 = buffVectorA[iBuff];
  146. strBuff1 = buffVectorA[iBuff + 1];
  147. strBuff2 = buffVectorA[iBuff + 2];
  148. }
  149.  
  150. else if( ( strBuff.compare (0, 7, "request") == 0 ) || (strBuff.compare (0, 7, "release") == 0))
  151. {
  152. processList[countBuff].push_back(strBuff0); //Process ID
  153. processList[countBuff].push_back(strBuff1); //deadline
  154. processList[countBuff].push_back(strBuff2); //Computation Time
  155. processList[countBuff].push_back(strBuff); //Request/Releaase Type
  156. countBuff++;
  157. }
  158.  
  159. else
  160. {
  161. continue;
  162. }
  163. }
  164.  
  165. infile.close();
  166. }
  167.  
  168. /*******************************************************/
  169. //Function Name : inputProcessListParsing
  170. //Functionality : To parse the obtained Process List and
  171. // place them in a particular format
  172. // process_name<sp>deadline<sp>compTime<sp>
  173. // process_ID<sp>resource<sp>
  174. // The above format is used for parsing
  175. /*******************************************************/
  176. int inputProcessListParsing()
  177. {
  178. for (int iBuff = 0; iBuff < totalProcessCount; iBuff++ )
  179. {
  180. processListMain.push_back( vector<int>() ); // Adding an empty row
  181. }
  182.  
  183. int intBuff;
  184. string strBuffer;
  185. char str[20];
  186. for (int iBuff = 0; iBuff < totalProcessCount - 1; iBuff++)
  187. {
  188. for (int jBuff = 0; jBuff < 4; jBuff++)
  189. {
  190. strBuffer = processList[iBuff][jBuff];
  191. switch(jBuff)
  192. {
  193. case 0:
  194. {
  195. //processing the process ID and retrieving values accordingly
  196. if( strBuffer.compare (0, 7, "process") == 0 )
  197. {
  198. unsigned pos = strBuffer.find("_");
  199. string buffStr = strBuffer.substr (pos);
  200. size_t length = buffStr.copy(str, buffStr.length() - 1, 1);
  201. str[length] = '\0';
  202. istringstream ( str ) >> intBuff;
  203. processListMain[iBuff].push_back(intBuff);
  204. }
  205. break;
  206. }
  207.  
  208. case 1:
  209. {
  210. istringstream ( strBuffer ) >> intBuff;
  211. processListMain[iBuff].push_back(intBuff);
  212. break;
  213. }
  214.  
  215. case 2:
  216. {
  217. istringstream ( strBuffer ) >> intBuff;
  218. processListMain[iBuff].push_back(intBuff);
  219. break;
  220. }
  221.  
  222. case 3:
  223. {
  224. //processing if the obtained list is a request
  225. if( strBuffer.compare (0, 7, "request") == 0 )
  226. {
  227. //cout << "1" << "\t";//printing request value as 1
  228. processListMain[iBuff].push_back(1);
  229. istringstream ss (strBuffer);
  230. string token;
  231. while(getline(ss, token, ','))
  232. {
  233. if ( token.compare (0, 7, "request") == 0 )
  234. {
  235. unsigned pos = token.find("(");
  236. string buffStr = token.substr (pos);
  237. size_t length = buffStr.copy(str, buffStr.length() - 1, 1);
  238. str[length] = '\0';
  239. istringstream ( str ) >> intBuff;
  240. //cout << intBuff << "\t";
  241. processListMain[iBuff].push_back(intBuff);
  242. }
  243. else
  244. {
  245. string str1;
  246. str1 = token;
  247. for ( unsigned int i = 0; i < strlen(chars); ++i )
  248. str1.erase( remove( str1.begin(), str1.end(), chars[i] ), str1.end());
  249. istringstream ( str1 ) >> intBuff;
  250. //cout << str1 << "\t";
  251. processListMain[iBuff].push_back(intBuff);
  252. }
  253. }
  254. }
  255. //processing if the obtained list is a release
  256. if( strBuffer.compare (0, 7, "release") == 0 )
  257. {
  258. //cout << "0" << "\t";//printing request value as 1
  259. processListMain[iBuff].push_back(0);
  260. istringstream ss (strBuffer);
  261. string token;
  262. while(getline(ss, token, ','))
  263. {
  264. if ( token.compare (0, 7, "release") == 0 )
  265. {
  266. unsigned pos = token.find("(");
  267. string buffStr = token.substr (pos);
  268. size_t length = buffStr.copy(str, buffStr.length() - 1, 1);
  269. str[length] = '\0';
  270. istringstream ( str ) >> intBuff;
  271. //cout << intBuff << "\t";
  272. processListMain[iBuff].push_back(intBuff);
  273. }
  274. else
  275. {
  276. string str1;
  277. str1 = token;
  278. for ( unsigned int i = 0; i < strlen(chars); ++i )
  279. str1.erase( remove( str1.begin(), str1.end(), chars[i] ), str1.end());
  280. //cout << str1 << "\t";
  281. istringstream ( str1 ) >> intBuff;
  282. processListMain[iBuff].push_back(intBuff);
  283. }
  284. }
  285. }
  286. break ;
  287. }
  288. }
  289. }
  290. cout << endl;
  291. }
  292. }
  293.  
  294. /*******************************************************/
  295. //Function Name : initAllocatedResource
  296. //Functionality : Initializing the allocated resource
  297. // values
  298. /*******************************************************/
  299. int initAllocatedResource()
  300. {
  301. int temp = 0;
  302. for (int iBuff = 0; iBuff < numProcess; iBuff++ )
  303. {
  304. allocateResource.push_back( vector<int>() ); // Adding an empty row
  305. }
  306. for (int iBuff = 0; iBuff < numProcess; iBuff++ )
  307. for (int jBuff = 0; jBuff < numResource; jBuff++ )
  308. {
  309. allocateResource[iBuff].push_back(temp);
  310. }
  311. }
  312.  
  313. /*******************************************************/
  314. //Function Name : initFinalStatement
  315. //Functionality : Initializing the final statement
  316. // values
  317. /*******************************************************/
  318. int initFinalStatement()
  319. {
  320. int temp = 0;
  321. for (int iBuff = 0; iBuff < (totalProcessCount + totalProcessCount); iBuff++ )
  322. {
  323. finalStatement.push_back( vector<string>() ); // Adding an empty row
  324. }
  325. }
  326.  
  327.  
  328. /*******************************************************/
  329. //Function Name : ShortJobFirstScheduling
  330. //Functionality : The Process Requests and releases are
  331. // sorted as per the Shortest Path First
  332. // Scheduling
  333. /*******************************************************/
  334. int ShortJobFirstScheduling()
  335. {
  336. vector < vector<string> > SJFBuffer;
  337. int intBuff;
  338. vector < string > strBuff;
  339. char str[20];
  340. int count = 0;
  341.  
  342. for ( int jBuff = 0; jBuff < totalProcessCount - 1; jBuff++)
  343. {
  344. for ( int iBuff = 0; iBuff < totalProcessCount - 1; iBuff++)
  345. {
  346. if ( ( processList[iBuff][2] > processList[iBuff + 1][2] ) && ( iBuff != totalProcessCount ) )
  347. {
  348. strBuff = processList[iBuff];
  349. processList[iBuff] = processList[iBuff + 1];
  350. processList[iBuff + 1] = strBuff;
  351. }
  352. else
  353. {
  354. count++;
  355. if( count == totalProcessCount )
  356. break;
  357. }
  358. }
  359. }
  360.  
  361. int temp1 = 0;
  362. int temp2 = 0;
  363. for(int i=0; i < totalProcessCount; i++)
  364. {
  365. cout << processList[i][0] << endl;
  366. if((i+1) != totalProcessCount )
  367. {
  368. if(processList[i][0] != processList[i+1][0])
  369. {
  370. sortArray[temp1][temp2] = i;
  371. temp2=0;
  372. temp1++;
  373. }
  374. else
  375. {
  376. sortArray[temp1][temp2] = i;
  377. temp2++;
  378. }
  379. }
  380. }
  381. }
  382.  
  383. /*******************************************************/
  384. //Function Name : llfSort
  385. //Functionality : sorting as per LLF and sending the pointer
  386. /*******************************************************/
  387. int llfSort()
  388. {
  389. int strBuff;
  390. int count = 0;
  391. for ( int jBuff = 0; jBuff < numProcess + 1; jBuff++)
  392. {
  393. for ( int iBuff = 0; iBuff < numProcess; iBuff++)
  394. {
  395. if ( ( llfArrange[iBuff][2] > llfArrange[iBuff+1][2]) && ( iBuff != numProcess ) )
  396. {
  397. for(int i = 0; i < 5; i++)
  398. {
  399. strBuff = llfArrange[iBuff][i];
  400. llfArrange[iBuff][i] = llfArrange[iBuff + 1][i];
  401. llfArrange[iBuff + 1][i] = strBuff;
  402. }
  403. }
  404. else
  405. {
  406. count++;
  407. if( count == numProcess )
  408. break;
  409. }
  410. }
  411. }
  412.  
  413. }
  414.  
  415. /*******************************************************/
  416. //Function Name : LeastLaxityFirstScheduling
  417. //Functionality : The Process Requests and releases are
  418. // sorted as per the Least Laxity First
  419. // Scheduling
  420. /*******************************************************/
  421. int LeastLaxityFirstScheduling()
  422. {
  423. vector < vector<string> > SJFBuffer;
  424. int intBuff;
  425. vector < string > strBuff;
  426. char str[20];
  427. int count = 0;
  428.  
  429. for ( int jBuff = 0; jBuff < totalProcessCount - 1; jBuff++)
  430. {
  431. for ( int iBuff = 0; iBuff < totalProcessCount - 1; iBuff++)
  432. {
  433. if ( ( processList[iBuff][2] > processList[iBuff + 1][2] ) && ( iBuff != totalProcessCount ) )
  434. {
  435. strBuff = processList[iBuff];
  436. processList[iBuff] = processList[iBuff + 1];
  437. processList[iBuff + 1] = strBuff;
  438. }
  439. else
  440. {
  441. count++;
  442. if( count == totalProcessCount )
  443. break;
  444. }
  445. }
  446. }
  447.  
  448. int temp1 = 0;
  449. int temp2 = 0;
  450. for(int i=0; i < totalProcessCount; i++)
  451. {
  452. cout << processList[i][0] << endl;
  453. if((i+1) != totalProcessCount )
  454. {
  455. if(processList[i][0] != processList[i+1][0])
  456. {
  457. sortArray[temp1][temp2] = i;
  458. temp2=0;
  459. temp1++;
  460. }
  461. else
  462. {
  463. sortArray[temp1][temp2] = i;
  464. temp2++;
  465. }
  466. }
  467. }
  468.  
  469. int temp11, temp12, temp13;
  470. for(int i=0; i < numProcess; i++)
  471. {
  472. temp11 = sortArray[i][0];
  473. istringstream ( processList[temp11][1] ) >> temp12;
  474. istringstream ( processList[temp11][2] ) >> temp13;
  475. ::llfArrange[i][0] = temp12;
  476. ::llfArrange[i][1] = temp13;
  477. ::llfArrange[i][2] = temp12 - temp13;
  478. ::llfArrange[i][3] = 0;
  479. ::llfArrange[i][4] = i;
  480. }
  481.  
  482. }
  483.  
  484. /*******************************************************/
  485. //Function Name : outputPrint
  486. //Functionality : To print the contents of the output file
  487. // Number of Resource, Number of Process
  488. // Available Resource, Process List are all
  489. // displayed.
  490. /*******************************************************/
  491. int outputPrint()
  492. {
  493. cout << "*****************************************" << endl;
  494. cout << "****INPUT DATA SUMMARY FROM input.txt****" << endl;
  495. cout << "*****************************************" << endl;
  496. cout << "Number of Resource : " << numResource << endl;
  497. cout << "Number of Process : " << numProcess << endl;
  498. cout << "Available Resource" << endl;
  499. for (vector<int>::iterator it = availableResource.begin(); it != availableResource.end(); ++it)
  500. std::cout << *it << " ";
  501. cout << endl;
  502. cout << "*********************************************************" << endl;
  503. cout << "maximum resource" << endl;
  504. cout << "*********************************************************" << endl;
  505. for (int iBuff = 0; iBuff < numProcess; iBuff++)
  506. {
  507. for (int jBuff = 0; jBuff < numResource; jBuff++)
  508. cout << maxResourceDemand[iBuff][jBuff] << " ";
  509. cout << endl;
  510. }
  511. cout << "*********************************************************" << endl;
  512. cout << "initial allocated resource" << endl;
  513. cout << "*********************************************************" << endl;
  514. for (int iBuff = 0; iBuff < numProcess; iBuff++)
  515. {
  516. for (int jBuff = 0; jBuff < numResource; jBuff++)
  517. cout << allocateResource[iBuff][jBuff] << " ";
  518. cout << endl;
  519. }
  520. cout << "**********************************************************" << endl;
  521. cout << "Request and Release Scheduled Run" << endl;
  522. cout << "**********************************************************" << endl;
  523.  
  524. }
  525.  
  526. /*******************************************************/
  527. //Function Name : reqAllocation
  528. //Functionality : As the safety check on the request is
  529. // made and the return value obtained is
  530. // safe, we can allocate the resource for
  531. // the request
  532. /******************************************************/
  533. int reqAllocation(int tokenPt)
  534. {
  535. int temp, i, temp1;
  536. temp1 = processListMain[tokenPt][0];
  537. for (i = 0; i < numResource; i++)
  538. {
  539. temp = ::allocateResource[temp1-1][i];
  540. ::allocateResource[temp1-1][i] = temp + processListMain[tokenPt][i+4];
  541. }
  542.  
  543. for( i = 0; i < numResource; i++)
  544. {
  545. temp = ::availableResource[i];
  546. ::availableResource[i] = temp - processListMain[tokenPt][i+4];
  547. }
  548. cout << "Available Resource" << endl;
  549. for (vector<int>::iterator it = ::availableResource.begin(); it != ::availableResource.end(); ++it)
  550. std::cout << *it << " ";
  551. cout << endl;
  552.  
  553. cout << "Allocated resource" << endl;
  554. for (int iBuff = 0; iBuff < numProcess; iBuff++)
  555. {for (int jBuff = 0; jBuff < numResource; jBuff++)
  556. cout << ::allocateResource[iBuff][jBuff] << " ";
  557. cout << endl;}
  558.  
  559. for (i = 0; i < totalProcessCount - 1; i++)
  560. processListMain[i][1] = processListMain[i][1] - processListMain[i][2];
  561.  
  562. return 0;
  563. }
  564.  
  565. /******************************************************/
  566. //Function Name : reqModification
  567. //Functionality : As the safety check on the request is
  568. // failed and hence the resource is kept
  569. // in que and the modifications are made
  570. // on the computation time
  571. /******************************************************/
  572. int reqModification(int tokenPt)
  573. {
  574. for (int i = 0; i < totalProcessCount - 1; i++)
  575. processListMain[i][1] = processListMain[i][1] - 1;
  576. }
  577.  
  578. /*******************************************************/
  579. //Function Name : reqRelease
  580. //Functionality : When there is a release request made,
  581. // the corresponding Process gets released
  582. /*******************************************************/
  583. int reqRelease(int tokenPt)
  584. {
  585. int temp, i, temp1;
  586. temp1 = processListMain[tokenPt][0];
  587. for (i = 0; i < numResource; i++)
  588. {
  589. temp = ::allocateResource[temp1-1][i];
  590. if(temp > processListMain[tokenPt][i+4]) { ::allocateResource[temp1-1][i] = temp - processListMain[tokenPt][i+4];}
  591. else { ::allocateResource[temp1-1][i] = processListMain[tokenPt][i+4] - temp; }
  592. }
  593.  
  594. for( i = 0; i < numResource; i++)
  595. {
  596. temp = ::availableResource[i];
  597. ::availableResource[i] = processListMain[tokenPt][i+4] + temp;
  598. }
  599. cout << "Available Resource" << endl;
  600. for (vector<int>::iterator it = ::availableResource.begin(); it != ::availableResource.end(); ++it)
  601. std::cout << *it << " ";
  602. cout << endl;
  603.  
  604. cout << "Allocated resource" << endl;
  605. for (int iBuff = 0; iBuff < numProcess; iBuff++)
  606. {for (int jBuff = 0; jBuff < numResource; jBuff++)
  607. cout << ::allocateResource[iBuff][jBuff] << " ";
  608. cout << endl;}
  609.  
  610. for (i = 0; i < totalProcessCount - 1; i++)
  611. processListMain[i][1] = processListMain[i][1] - 1;
  612.  
  613. return 0;
  614. }
  615.  
  616. /*******************************************************/
  617. //Function Name : bankersAlgorithmCheck
  618. //Functionality : To check and verify the deadlock safety
  619. // for the requested process through the
  620. // Bankers Algorithm
  621. /*******************************************************/
  622. int bankersAlgorithmCheck ( int location )
  623. {
  624. int pointValue = location;
  625. int maxAllocated[10][10] = {0};
  626. int allocResource[10][10] = {0};
  627. int needlResource[10][10] = {0};
  628. int availResourceVector[10] = {0};
  629. int requestResourceVector[10] = {0};
  630.  
  631. cout << "******************************" << endl;
  632. cout << processList[pointValue][0] << endl; finalStatement[::finalCount].push_back(processList[pointValue][0]);
  633. cout << processList[pointValue][3] << endl; finalStatement[::finalCount].push_back(processList[pointValue][3]);
  634.  
  635. //Verifying Request or Release
  636. if ( processListMain[pointValue][3] == 0 )
  637. { finalStatement[::finalCount].push_back("Release Request : Released"); return 2; }
  638.  
  639. //Feeding maximum resource table
  640. for(int i = 0; i < numResource; i++)
  641. for(int j = 0; j < numProcess; j++)
  642. maxAllocated[i][j] = maxResourceDemand[i][j];
  643.  
  644. //Feeding allocated resource table
  645. for(int i = 0; i < numResource; i++)
  646. for(int j = 0; j < numProcess;j ++)
  647. allocResource[i][j] = allocateResource[i][j];
  648.  
  649. //Calculating the needResource table from the maxAllocated and allocResource
  650. for(int i = 0; i < numResource; i++)
  651. for(int j = 0; j < numProcess; j++)
  652. needlResource[i][j] = maxAllocated[i][j] - allocResource[i][j];
  653.  
  654. //Feeding the available Resource vector
  655. for(int i = 0; i < numResource; i++)
  656. availResourceVector[i] = availableResource[i];
  657.  
  658. //printf( "\nEnter request vector \n");
  659. for(int i = 0; i < numResource; i++)
  660. requestResourceVector[i] = processListMain[pointValue][i + 4];
  661.  
  662. for(int i = 0; i < numResource; i++)
  663. {
  664. if(requestResourceVector[i] > availResourceVector[i])
  665. {
  666. puts("Error : Available Resource is less than Request");
  667. finalStatement[::finalCount].push_back("Less Available Resource : Queued");
  668. return 3;
  669. }
  670. }
  671.  
  672. //safetyChecking
  673. for(int i = 0; i < numResource; i++)
  674. {
  675. availResourceVector[i] = availResourceVector[i] - requestResourceVector[i];
  676. }
  677. int counter = 10;
  678. bool finish[5] = { false };
  679. while( counter-- )
  680. {
  681. for(int i = 0; i < (numResource - 1); i++)
  682. {
  683. int flag = false;
  684. if ( finish[i] )
  685. continue;
  686. for ( int j = 0; j < (numResource - 1); j++)
  687. {
  688. flag=true;
  689. if( availResourceVector[j] < needlResource[i][j] )
  690. {
  691. flag=false;
  692. break;
  693. }
  694. }
  695. finish[i] = true;
  696. if( finish[i] == true )
  697. {
  698. for( int l = 0; l < (numResource - 1); l++)
  699. availResourceVector[l] += allocResource[i][l];
  700. }
  701. }
  702. }
  703.  
  704. for(int i = 0; i < (numResource - 1); i++)
  705. if(finish[i]==false)
  706. {
  707. finalStatement[::finalCount].push_back("Safety Check : Unsafe - Queued");
  708. return 1;
  709. }
  710. finalStatement[::finalCount].push_back("Safety Check : Safe - Request Processed");
  711. return 0;
  712. }
  713.  
  714. /*******************************************************/
  715. //Function Name : createPipe
  716. //Functionality : To create Pipes and the child process
  717. // calls the Bankers Algorithm, while the
  718. // parent process based on the result
  719. // allocates the resource or misses
  720. // deadline
  721. /*******************************************************/
  722. int createPipe(int iBuff)
  723. {
  724. char string1[] = "The Request is in Safe State. The Resources are allocated as follows";
  725. char string2[] = "The Request is Not in Safe State";
  726. char string3[] = "The Resources are Released Successfully and the resources are available as shown below";
  727. char string4[] = "DeadLine Missed";
  728. int PFState;
  729.  
  730. int i;
  731. i = iBuff;
  732. int n;
  733. int status, pid, pipefds[2];
  734.  
  735. status = pipe(pipefds);
  736.  
  737. if (status == -1)
  738. {
  739. perror("Trouble");
  740. exit(1);
  741. }
  742.  
  743. pid = fork();
  744. if (pid == -1)
  745. {
  746. perror("Trouble");
  747. exit(2);
  748. }
  749.  
  750. else if (pid == 0)//child process
  751. {
  752. close(pipefds[0]);//closing child process to write
  753. write(pipefds[1], &i, sizeof(i));//writing in child process
  754. close(pipefds[1]);
  755. exit(0);
  756.  
  757. }
  758. else//parent process
  759. {
  760. close(pipefds[1]);
  761. read(pipefds[0], &n, sizeof(n));//reading in parent process
  762. PFState = bankersAlgorithmCheck(n);//bankers algorithm check in parent process
  763. if ( PFState==0 )
  764. { cout << string1 << endl; reqAllocation(i); }
  765. if ( PFState==1 )
  766. { cout << string2 << endl; reqModification(i); }
  767. if ( PFState==2 )
  768. { cout << string3 << endl; reqRelease(i); }
  769. if ( PFState==3)
  770. {
  771. int cBuff=0, dBuff=0;
  772. for(int iB=1; iB < 15; iB++)
  773. for(int jB=1; jB < 15; jB++)
  774. {
  775. if( (sortArrayRerun[iB][jB] == 0) )
  776. {
  777. cBuff = iB; dBuff = jB;break;
  778. }if( (cBuff != 0) && (dBuff != 0) ){break;} else {continue;}
  779. }
  780. sortArrayRerun[cBuff][dBuff] = i;
  781. }
  782. if ( PFState==4 )
  783. { cout << string4 << endl; }
  784. sleep(1);
  785. close(pipefds[0]);//closing parent process
  786. }
  787. return PFState;
  788. }
  789.  
  790. /*******************************************************/
  791. //Function Name : releaseAll
  792. //Functionality : Releasing all the allocated vlues
  793. /*******************************************************/
  794. int releaseAll()
  795. {
  796. cout << "*************************************************************************" << endl;
  797. cout << "All the allocated resources will be released and then added to the available resource" << endl;
  798. sleep(5);
  799. for (int i = 0; i < numProcess; i++)
  800. {
  801. for (int j = 0; j < numResource; j++)
  802. {
  803. ::availableResource[j] = ::allocateResource[i][j] + ::availableResource[j];
  804. ::allocateResource[i][j] = 0;
  805. }
  806. }
  807. }
  808.  
  809. /*******************************************************/
  810. //Function Name : releaseAll
  811. //Functionality : Releasing all the allocated vlues
  812. /*******************************************************/
  813. int finalOutputResult()
  814. {
  815. system("clear");
  816. cout << "*****************************************************" << endl;
  817. cout << "****************** Final Result *******************" << endl;
  818. cout << "*****************************************************" << endl;
  819. cout << "AVAILABLE RESOURCE" << endl;
  820. for (vector<int>::iterator it = ::availableResource.begin(); it != ::availableResource.end(); ++it)
  821. std::cout << *it << " ";
  822. cout << endl;
  823. cout << "*****************************************************" << endl;
  824. cout << "ALLOCATED RESOURCE" << endl;
  825. for (int iBuff = 0; iBuff < numProcess; iBuff++)
  826. {for (int jBuff = 0; jBuff < numResource; jBuff++)
  827. cout << ::allocateResource[iBuff][jBuff] << " ";
  828. cout << endl;}
  829. cout << "*****************************************************" << endl;
  830. if(scheduleType == 1) { cout << "SCHEDULING TYPE : Short Job First" << endl; }
  831. else { cout << "SCHEDULING TYPE : Least Laxity First" << endl; }
  832. cout << "NUMBER OF PROCESS : " << numProcess << endl;
  833. cout << "NUMBER OF RESOURCE : " << numResource << endl;
  834. cin.get();
  835. cout << "The requests and releases are scheduled in the following order" << endl;
  836. for (int iBuff = 0; iBuff < (totalProcessCount+totalProcessCount); iBuff++)
  837. {
  838. if(iBuff != finalCount-1)
  839. {cout << endl;
  840. cout << iBuff+1 ;
  841. cout << finalStatement[iBuff][0] ;
  842. cout << finalStatement[iBuff][1] << endl;
  843. cout << finalStatement[iBuff][2] << endl;}
  844. else
  845. break;
  846. }
  847. }
  848.  
  849. /*******************************************************/
  850. //Function Name : llfArrangement()
  851. //Functionality : calculating relative deadlline and
  852. // sending back the location pointer
  853. /*******************************************************/
  854. int llfArrangement()
  855. {
  856. int strBuff;
  857. int count = 0;
  858. for ( int jBuff = 0; jBuff < numProcess + 1; jBuff++)
  859. {
  860. for ( int iBuff = 0; iBuff < numProcess; iBuff++)
  861. {
  862. if ( ( llfArrange[iBuff][2] > llfArrange[iBuff+1][2]) && ( iBuff != numProcess ) )
  863. {
  864. for(int i = 0; i < 5; i++)
  865. {
  866. strBuff = llfArrange[iBuff][i];
  867. llfArrange[iBuff][i] = llfArrange[iBuff + 1][i];
  868. llfArrange[iBuff + 1][i] = strBuff;
  869. }
  870. }
  871. else
  872. {
  873. count++;
  874. if( count == numProcess )
  875. break;
  876. }
  877. }
  878. }
  879.  
  880. }
  881.  
  882. /*******************************************************/
  883. //Function Name : main
  884. //Functionality : The program starts here and all the fucntion
  885. // calls are done.
  886. /*******************************************************/
  887. /*******************************************************/
  888. int main()
  889. {
  890. int schType;
  891. getInputFromFile();
  892. system("clear");
  893. cout << "***************************************************************" << endl;
  894. cout << "****** IMPLEMENTING BANKER'S ALGORITHM USING PIPES ******" << endl;
  895. cout << "****** SCHEDULING PROCESSES USING SJF & LLF ******" << endl;
  896. cout << "***************************************************************" << endl;
  897. cout << "Feed the SCHEDULING TYPE" << endl;
  898. cout << "1. SJF" << endl << "2. LLF" << endl;
  899. cin >> schType;
  900. ::scheduleType = schType;
  901. switch(schType)
  902. {
  903. case 1:
  904. {
  905. ShortJobFirstScheduling();//scheduling the process
  906. inputProcessListParsing();//text parsing and passing the necessary values
  907. initAllocatedResource();//initializing the allocated Resource - Alloc
  908. initFinalStatement();//initializing the final statement vector
  909. system("clear");//clearing system for user reference
  910. outputPrint();//output display
  911. for(int i=0; i < 15; i++)
  912. {
  913. for(int j=0; j < 15; j++)
  914. {
  915. if( (sortArray[j][i] != 0) || ( (i==0) && (j==0) ) )
  916. {
  917. int iBuff = sortArray[j][i];
  918. createPipe(iBuff);//creating pipes and calling Banker's Algorithm from the Parent Process
  919. ::finalCount++;
  920. }
  921. }
  922. }
  923. for(int i=0; i < 15; i++)
  924. {
  925. for(int j=0; j < 15; j++)
  926. {
  927. if( (sortArrayRerun[j][i] != 0) || ( (i==0) && (j==0) ) )
  928. {
  929. int iBuff = sortArrayRerun[j][i];
  930. createPipe(iBuff);//creating pipes and calling Banker's Algorithm from the Parent Process
  931. ::finalCount++;
  932. }
  933. }
  934. }
  935. releaseAll();
  936. finalOutputResult();
  937. break;
  938. }
  939. case 2:
  940. {
  941. int maxResourceValue = 0;
  942. LeastLaxityFirstScheduling();//scheduling the process
  943. inputProcessListParsing();//text parsing and passing the necessary values
  944. initAllocatedResource();//initializing the allocated Resource - Alloc
  945. initFinalStatement();//initializing the final statement vector
  946. system("clear");//clearing system for user reference
  947. outputPrint();//output display
  948. llfSort();//sorting as per the llf and identifing the initial pointer and deadline miss
  949. for(int i=0; i < 15; i++)
  950. {
  951. for(int j=0; j < 15; j++)
  952. {
  953. if ( sortArray[i][j] != 0 )
  954. {
  955. if ( maxResourceValue < j ) { maxResourceValue++; }
  956. }
  957. }
  958. }
  959. for(int i=0; i < maxResourceValue; i++)
  960. {
  961. for(int j=1; j < numProcess+1; j++)
  962. {
  963. if(llfArrange[j][1] != 0)//computation time not less than 0
  964. {
  965. if((llfArrange[j][0] != 0) && (llfArrange[j][0] >0) )//deadline not less than 0
  966. {
  967. int iBuff = sortArray[ llfArrange[j][4] ] [ llfArrange[j][3] ]; cout <<iBuff << endl;
  968. int x = createPipe(iBuff);//creating Pipe and calling Banker's Algorithm from the parent process
  969. for(int iBuffer = 1; iBuffer < numProcess + 1; iBuffer++)
  970. {
  971. if ( (x == 0 ) || ( x == 1) || ( x == 2) )
  972. {
  973. if ( iBuffer == j ) { llfArrange[iBuffer][3]++;}//incrementing pointer
  974. llfArrange[iBuffer][1]--;//decreasing computation time
  975. llfArrange[iBuffer][0]--;//decreasing deadline
  976. }
  977. if ( (x==3) )
  978. {
  979. if ( iBuffer == j ) { llfArrange[iBuffer][3]++;}//incrementing pointer
  980. llfArrange[iBuffer][0]--;//decreasing deadline alone
  981. llfArrangement();
  982. }
  983. }
  984. //for(int k=1; k <numProcess+1; k++) cout <<llfArrange[k][0]<<llfArrange[k][1]<<llfArrange[k][2]<<endl;
  985. ::finalCount++;
  986. }
  987. else
  988. {
  989. int pointValue = sortArray[llfArrange[j][4]][llfArrange[j][3]];
  990. cout << "******************************" << endl;
  991. cout << processList[pointValue][0] << endl; finalStatement[::finalCount].push_back(processList[pointValue][0]);
  992. cout << processList[pointValue][3] << endl; finalStatement[::finalCount].push_back(processList[pointValue][3]);
  993. cout << "Deadline Missed" << endl;
  994. ::finalStatement[::finalCount].push_back("Deadline Missed");
  995. for(int iBuffer = 1; iBuffer < numProcess + 1; iBuffer++)
  996. {
  997. if ( iBuffer == j ) { llfArrange[iBuffer][3]++;}//incrementing pointer
  998. }
  999. //for(int k=1; k <numProcess+1; k++) cout <<llfArrange[k][0]<<llfArrange[k][1]<<llfArrange[k][2]<<endl;
  1000. ::finalCount++;llfArrangement();
  1001. }
  1002. }
  1003. }
  1004. }
  1005. releaseAll();
  1006. finalOutputResult();
  1007. break;
  1008. }
  1009. default:
  1010. {
  1011. cout << "Invalid Entry" << endl;
  1012. }
  1013. }
  1014. cin.get();
  1015. return 0;
  1016. }

Report this snippet  

You need to login to post a comment.