a_pramanik

CPU scheduling all together

Feb 24th, 2018
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 17.44 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct gt
  5. {
  6.     int pro;
  7.     int time;
  8. };
  9.  
  10. int arr[1000], bur[1000], pr[1000], wt[1000], tmp[1000], n, tq;
  11. bool inputTaken;
  12. vector<double>vFcfs, vSjfP, vSjfNP, vPriority, vRoundRobin;
  13. bool isAllDone()
  14. {
  15.     int cnt=0;
  16.     for(int i=0; i<n; i++){
  17.         if(tmp[i]==0)cnt++;
  18.     }
  19.     if(cnt==n)return true;
  20.     return false;
  21. }
  22.  
  23. void takeInput()
  24. {
  25.     printf("Enter number of processes : ");
  26.     cin>>n;
  27.  
  28.     for(int i=0; i<n; i++){
  29.         printf("Enter arrival time,burst time and priority of process p%d : ", i);
  30.         cin>>arr[i]>>bur[i]>>pr[i];
  31.     }
  32.     printf("Enter time slice for Round-Robin algorithm : ");
  33.     cin>>tq;
  34.     inputTaken=true;
  35.  
  36. }
  37.  
  38. void fcfs()
  39. {
  40.     if(inputTaken==false){
  41.         printf("\n\tNo input data detected, Give input first!\n");
  42.         return;
  43.     }
  44.     memset(wt, 0, sizeof wt);
  45.     vFcfs.clear();
  46.     int arrTemp[1000];
  47.     int burTemp[1000];
  48.     int process[1000];
  49.     int i, j, k;
  50.     for(i=0; i<n; i++){
  51.         process[i]=i;
  52.         arrTemp[i]=arr[i];
  53.         burTemp[i]=bur[i];
  54.     }
  55.  
  56.     for(i=0; i<n; i++){
  57.         for(j=i+1; j<n; j++){
  58.             if(arrTemp[i]>arrTemp[j]){
  59.                 swap(arrTemp[i], arrTemp[j]);
  60.                 swap(burTemp[i], burTemp[j]);
  61.                 swap(process[i], process[j]);
  62.             }
  63.         }
  64.     }
  65.  
  66.     printf("\t##Results for FCFS Algorithm ##\n");
  67.  
  68.     wt[process[0]]=0;
  69.  
  70.     printf("\t\t****Gantt Chart****\n");
  71.     printf("%d__[p%d]__%d  ", arrTemp[0], process[0], arrTemp[0]+burTemp[0]);
  72.  
  73.     int presentTime=arrTemp[0]+burTemp[0];
  74.  
  75.  
  76.     double sum=0.0;
  77.  
  78.  
  79.  
  80.     for(i=1; i<n; i++){
  81.         int strt, endd;
  82.  
  83.         if(presentTime>arrTemp[i]){
  84.             wt[i]=presentTime-arrTemp[i];
  85.             strt=presentTime;
  86.             endd=presentTime+burTemp[i];
  87.             presentTime=endd;
  88.         }
  89.         else{
  90.             wt[i]=0;
  91.             strt=arrTemp[i];
  92.             endd=arrTemp[i]+burTemp[i];
  93.             presentTime=endd;
  94.         }
  95.  
  96.         printf("%d__[p%d]__%d   ", strt, process[i], endd);
  97.         sum+=(double)wt[i];
  98.     }
  99.     printf("\n");
  100.  
  101.     printf("\t****Individual Waiting time****");
  102.     printf("\n Process       Waiting time\n");
  103.  
  104.     for(i=0; i<n; i++){
  105.         printf("    p%d            %d\n", i, wt[i]);
  106.         vFcfs.push_back((double)wt[i]);
  107.     }
  108.     vFcfs.push_back(sum/n);
  109.     //printf("\n****Average of waiting time : %.2lf\n", sum/n);
  110.     cout<<"\n****Average of waiting time : "<<setprecision(3)<<sum/n<<endl;
  111. }
  112.  
  113.  
  114. void sjfPreem()
  115. {
  116.     if(inputTaken==false){
  117.         printf("***\tNo input data detected, Give input first!\n");
  118.         return;
  119.     }
  120.     memset(wt, 0, sizeof wt);
  121.     vSjfP.clear();
  122.     int i, j, k, x, y, min1, min2, st, flg;
  123.     struct gt temp;
  124.     vector<gt>v;
  125.  
  126.     for(i=0; i<n; i++)
  127.     {
  128.         tmp[i]=bur[i];
  129.     }
  130.  
  131.     min1=99999999;
  132.  
  133.     for(i=0; i<n; i++)
  134.     {
  135.         if(arr[i]==0)
  136.         {
  137.             if(bur[i]<min1)
  138.             {
  139.                 min1 = bur[i];
  140.                 st=i;
  141.             }
  142.         }
  143.     }
  144.  
  145.     memset(wt, 0, sizeof wt);
  146.  
  147.     temp.pro=st;
  148.     temp.time=0;
  149.     v.push_back(temp);
  150.  
  151.     int t=1;
  152.     int now = st;
  153.     tmp[now]--;
  154.  
  155.     while(1)
  156.     {
  157.         min1=tmp[now];
  158.         for(i=0; i<n; i++)
  159.         {
  160.             if(i!=now && tmp[i]<min1 && tmp[i]>0 && arr[i]<=t)
  161.             {
  162.                 min1=tmp[i];
  163.                 now=i;
  164.             }
  165.         }
  166.  
  167.         for(i=0; i<n; i++)
  168.         {
  169.             if(i!=now && tmp[i]>0 && arr[i]<=t)
  170.             {
  171.                 wt[i]++;
  172.             }
  173.         }
  174.  
  175.         temp.pro=now;
  176.         temp.time=t;
  177.         v.push_back(temp);
  178.  
  179.         tmp[now]--;
  180.         t++;
  181.  
  182.         if(tmp[now]==0)
  183.         {
  184.  
  185.             min1 = 99999999;
  186.             flg=0;
  187.             for(i=0; i<n; i++)
  188.             {
  189.                 if(arr[i]<=t && tmp[i]!=0 && min1>tmp[i])
  190.                 {
  191.                     flg=1;
  192.                     min1=tmp[i];
  193.                     now=i;
  194.                 }
  195.             }
  196.  
  197.             if(flg==0)
  198.             {
  199.                 min1=99999999;
  200.                 min2=99999999;
  201.                 for(i=0; i<n; i++)
  202.                 {
  203.                     if(tmp[i]>0 && arr[i]<=min1 && tmp[i]<min2)
  204.                     {
  205.                         min1=arr[i];
  206.                         min2=tmp[i];
  207.                         t=arr[i];
  208.                         now=i;
  209.                     }
  210.                 }
  211.  
  212.             }
  213.  
  214.         }
  215.  
  216.         int koyta=0;
  217.  
  218.         for(i=0; i<n; i++)
  219.         {
  220.             if(tmp[i]==0)koyta++;
  221.         }
  222.         if(koyta==n)break;
  223.     }
  224.  
  225.     printf("\t##Results for SJF(Preemptive) Algorithm##\n");
  226.  
  227.  
  228.     printf("\t****Individual Waiting time****\n");
  229.     printf("\t  Process            Waiting Time\n");
  230.  
  231.     for(i=0; i<n; i++)
  232.     {
  233.         printf("\t      p%d                 %d\n", i, wt[i]);
  234.         vSjfP.push_back((double)wt[i]);
  235.     }
  236.     printf("\n");
  237.  
  238.  
  239.  
  240.     double sum = 0.0;
  241.  
  242.     for(i=0; i<n; i++)
  243.     {
  244.         sum+=(double)wt[i];
  245.     }
  246.     //printf("****Average waiting time : %.3lf\n", sum/n);
  247.     cout<<"\n****Average of waiting time : "<<setprecision(3)<<sum/n<<endl;
  248.     vSjfP.push_back(sum/n);
  249.  
  250.     printf("\t\t*****Gantt Chart*****\n\n");
  251.  
  252.  
  253.     int process, startTime, endTime;
  254.     int cnt=0;
  255.     for(i=0; i<v.size();){
  256.             cnt++;
  257.         process = v[i].pro;
  258.         startTime = v[i].time;
  259.         endTime;
  260.         for(j=i+1; j<v.size(); j++){
  261.             if(v[j].pro!=process){
  262.                 i=j;
  263.                 endTime=v[j-1].time+1;
  264.                 break;
  265.             }
  266.         }
  267.         if(j>=(v.size()-1)){
  268.             endTime=v[v.size()-1].time+1;
  269.             i=v.size();
  270.         }
  271.         printf("%d__[p%d]__%d  ", startTime, process, endTime);
  272.     }
  273.  
  274.  
  275.      printf("\n");
  276. }
  277.  
  278. void sjfNonPreem()
  279. {
  280.  
  281.     if(inputTaken==false){
  282.         printf("\n\tNo input data detected, Give input first!\n");
  283.         return;
  284.     }
  285.     memset(wt, 0, sizeof wt);
  286.     vSjfNP.clear();
  287.     int arrTemp[1000];
  288.     int burTemp[1000];
  289.     int process[1000];
  290.     int i, j;
  291.     for(i=0; i<n; i++){
  292.         arrTemp[i]=0;
  293.         process[i]=i;
  294.         burTemp[i]=bur[i];
  295.     }
  296.  
  297.     for(i=0; i<n; i++){
  298.         for(j=i+1; j<n; j++){
  299.             if(burTemp[i]>burTemp[j]){
  300.                 swap(burTemp[i], burTemp[j]);
  301.                 swap(process[i], process[j]);
  302.             }
  303.         }
  304.     }
  305.  
  306.     wt[process[0]]=0;
  307.  
  308.     printf("##Results for SJF(Non-Preemptive) Algorithm##\n");
  309.  
  310.     printf("\t\t****Gantt Chart****\n");
  311.     printf("%d__[p%d]__%d  ", arrTemp[0], process[0], arrTemp[0]+burTemp[0]);
  312.     int presentTime=arrTemp[0]+burTemp[0];
  313.  
  314.     double sum=0.0;
  315.  
  316.  
  317.  
  318.     for(i=1; i<n; i++){
  319.         int strt, endd;
  320.  
  321.         if(presentTime>arrTemp[i]){
  322.             wt[i]=presentTime-arrTemp[i];
  323.             strt=presentTime;
  324.             endd=presentTime+burTemp[i];
  325.             presentTime=endd;
  326.         }
  327.         else{
  328.             wt[i]=0;
  329.             strt=arrTemp[i];
  330.             endd=arrTemp[i]+burTemp[i];
  331.             presentTime=endd;
  332.         }
  333.  
  334.         printf("%d__[p%d]__%d   ", strt, process[i], endd);
  335.         sum+=(double)wt[i];
  336.     }
  337.     printf("\n");
  338.  
  339.     printf("\t****Individual Waiting time****");
  340.     printf("\n Process       Waiting time\n");
  341.  
  342.     for(i=0; i<n; i++){
  343.         printf("    p%d            %d\n", i, wt[i]);
  344.         vSjfNP.push_back((double)wt[i]);
  345.     }
  346.     vSjfNP.push_back(sum/n);
  347.     //printf("\n*****Average of waiting time : %.2lf\n", sum/n);
  348.     cout<<"\n****Average of waiting time : "<<setprecision(3)<<sum/n<<endl;
  349. }
  350.  
  351. void priorityScheduling()
  352. {
  353.     if(inputTaken==false){
  354.         printf("\t****No input data detected, Give input first!\n");
  355.         return;
  356.     }
  357.     memset(wt, 0, sizeof wt);
  358.     vPriority.clear();
  359.     int i, j,k, x, y;
  360.  
  361.     int min1, min2, mx, st, flg;
  362.  
  363.     struct gt temp;
  364.     vector<gt>v;
  365.  
  366.     for(i=0; i<n; i++)
  367.     {
  368.         tmp[i]=bur[i];
  369.     }
  370.  
  371.     mx = 0;
  372.     st=0;
  373.     for(i=0; i<n; i++)
  374.     {
  375.         if(arr[i]==0)
  376.         {
  377.             if(pr[i]>mx)
  378.             {
  379.                 mx = pr[i];
  380.                 st=i;
  381.             }
  382.         }
  383.     }
  384.  
  385.     memset(wt, 0, sizeof wt);
  386.  
  387.     temp.pro=st;
  388.     temp.time=0;
  389.  
  390.     v.push_back(temp);
  391.  
  392.     int t=1;
  393.     int now = st;
  394.     tmp[now]--;
  395.  
  396.     while(1)
  397.     {
  398.  
  399.         min1=t;
  400.         mx = pr[now];
  401.         for(i=0; i<n; i++)
  402.         {
  403.             if(i!=now && arr[i]<min1 && tmp[i]>0 && arr[i]<=t && pr[i]>mx)
  404.             {
  405.                 min1=arr[i];
  406.                 mx = pr[i];
  407.                 now=i;
  408.             }
  409.         }
  410.  
  411.         for(i=0; i<n; i++)
  412.         {
  413.             if(i!=now && tmp[i]>0 && arr[i]<=t)
  414.             {
  415.                 wt[i]++;
  416.             }
  417.         }
  418.  
  419.         temp.pro=now;
  420.         temp.time=t;
  421.         v.push_back(temp);
  422.  
  423.         tmp[now]--;
  424.         t++;
  425.  
  426.         if(tmp[now]==0)
  427.         {
  428.  
  429.             mx = 0;
  430.             min1=t;
  431.             flg=0;
  432.             for(i=0; i<n; i++)
  433.             {
  434.                 if(arr[i]<=t && tmp[i]>0 && pr[i]>mx && arr[i]<=min1)
  435.                 {
  436.                     flg=1;
  437.                     min1 = arr[i];
  438.                     mx = pr[i];
  439.                     now=i;
  440.                 }
  441.             }
  442.  
  443.             if(flg==0)
  444.             {
  445.                 min1=99999999;
  446.                 mx=0;
  447.                 for(i=0; i<n; i++)
  448.                 {
  449.                     if(tmp[i]>0 && arr[i]<min1 && pr[i]>mx)
  450.                     {
  451.                         min1=arr[i];
  452.                         mx=pr[i];
  453.                         t=arr[i];
  454.                         now=i;
  455.                     }
  456.                 }
  457.  
  458.             }
  459.  
  460.         }
  461.  
  462.         int koyta=0;
  463.  
  464.         for(i=0; i<n; i++)
  465.         {
  466.             if(tmp[i]==0)koyta++;
  467.         }
  468.         if(koyta==n)break;
  469.     }
  470.  
  471.     printf("\t##Results for Priority Scheduling Algorithm##\n");
  472.  
  473.  
  474.     printf("\t****Individual Waiting time****\n");
  475.     printf("\t  Process            Waiting Time\n");
  476.  
  477.     for(i=0; i<n; i++)
  478.     {
  479.         printf("\t      p%d                 %d\n", i, wt[i]);
  480.         vPriority.push_back((double)wt[i]);
  481.     }
  482.     printf("\n");
  483.  
  484.  
  485.  
  486.     double sum = 0.0;
  487.  
  488.     for(i=0; i<n; i++)
  489.     {
  490.         sum+=(double)wt[i];
  491.     }
  492.     //printf("****Average waiting time : %.3lf\n", sum/n);
  493.     cout<<"\n****Average of waiting time : "<<setprecision(3)<<sum/n<<endl;
  494.     vPriority.push_back(sum/n);
  495.  
  496.  
  497.     printf("\t\t*****Gantt Chart*****\n\n");
  498.  
  499.  
  500. int process, startTime, endTime;
  501.     int cnt=0;
  502.     for(i=0; i<v.size();){
  503.             cnt++;
  504.         process = v[i].pro;
  505.         startTime = v[i].time;
  506.         endTime;
  507.         for(j=i+1; j<v.size(); j++){
  508.             if(v[j].pro!=process){
  509.                 i=j;
  510.                 endTime=v[j-1].time+1;
  511.                 break;
  512.             }
  513.         }
  514.         if(j>=(v.size()-1)){
  515.             endTime=v[v.size()-1].time+1;
  516.             i=v.size();
  517.         }
  518.         printf("%d__[p%d]__%d  ", startTime, process, endTime);
  519.     }
  520.  
  521.  
  522.      printf("\n");
  523.  
  524. }
  525.  
  526. void roundRobin()
  527. {
  528.     if(inputTaken==false){
  529.         printf("\t****No input data detected, Give input first!\n");
  530.         return;
  531.     }
  532.     memset(wt, 0, sizeof wt);
  533.     vRoundRobin.clear();
  534.     int i, j, k, flg, min1;
  535.     struct gt tt;
  536.     vector<gt>v;
  537.     for(i=0; i<n; i++){
  538.         tmp[i]=bur[i];
  539.     }
  540.  
  541.     int now;
  542.  
  543.     for(i=0; i<n; i++){
  544.         if(arr[i]==0){
  545.             now=i;
  546.             break;
  547.         }
  548.     }
  549.  
  550.     int tq2=0;
  551.  
  552.     for(i=0;isAllDone()==false ;i++){
  553.  
  554.         if(tq2==tq || tmp[now]==0){
  555.             flg=0;
  556.  
  557.             for(j=now+1; j<n; j++){
  558.                 if(arr[j]<=i && tmp[j]>0){
  559.                     flg=1;
  560.                     now=j;
  561.                     break;
  562.                 }
  563.             }
  564.  
  565.             if(flg==0){
  566.                 for(j=0; j<now; j++){
  567.                     if(arr[j]<=i && tmp[j]>0){
  568.                         flg=1;
  569.                         now=j;
  570.                         break;
  571.                     }
  572.                 }
  573.             }
  574.  
  575.             if(flg==0){
  576.                 min1=99999;
  577.                 for(j=0; j<n; j++){
  578.                     if(arr[j]<min1 && tmp[j]>0){
  579.                         min1=arr[j];
  580.                         now=j;
  581.                     }
  582.                 }
  583.             }
  584.             tq2=0;
  585.         }
  586.         if(i<arr[now])i=arr[now];
  587.  
  588.        tt.pro=now;
  589.        tt.time=i;
  590.  
  591.          for(j=0; j<n; j++){
  592.         if(arr[j]<=i && j!=now && tmp[j]>0){
  593.             wt[j]++;
  594.         }
  595.        }
  596.        tq2++;
  597.        v.push_back(tt);
  598.        tmp[now]--;
  599.     }
  600.  
  601.     printf("\t****##Results for Round Robin Algorithm##\n");
  602.  
  603.     double sum=0.0;
  604. printf("\t***Individual Waiting time***\n");
  605.  
  606.  printf("\tProcess       waiting time\n");
  607.  for(i=0; i<n; i++){
  608.     printf("\t  p%d            %d\n",i,wt[i]);
  609.     vRoundRobin.push_back((double)wt[i]);
  610.     sum+=(double)wt[i];
  611.  }
  612.  vRoundRobin.push_back(sum/n);
  613.  //printf("***Average of waiting time = %.3lf s\n", sum/n);
  614.  cout<<"\n****Average of waiting time : "<<setprecision(3)<<sum/n<<endl;
  615.  
  616.  printf("\t\t***Gantt Chart***\n");
  617.  
  618.     int process, startTime, endTime;
  619.     int cnt=0;
  620.     for(i=0; i<v.size();){
  621.             cnt++;
  622.         process = v[i].pro;
  623.         startTime = v[i].time;
  624.         endTime;
  625.         for(j=i+1; j<v.size(); j++){
  626.             if(v[j].pro!=process){
  627.                 i=j;
  628.                 endTime=v[j-1].time+1;
  629.                 break;
  630.             }
  631.         }
  632.         if(j>=(v.size()-1)){
  633.             endTime=v[v.size()-1].time+1;
  634.             i=v.size();
  635.         }
  636.         printf("%d__[p%d]__%d  ", startTime, process, endTime);
  637.     }
  638.  
  639.      printf("\n");
  640.  
  641.  
  642. }
  643.  
  644. void compare()
  645. {
  646.  
  647.     fcfs();
  648.     sjfPreem();
  649.     sjfNonPreem();
  650.     priorityScheduling();
  651.     roundRobin();
  652.                                            printf("\t\t\t     ______________________\n");
  653.     printf("----------------------------| Comparing Algorithms |-------------------------\n");
  654.     printf("_____________________________________________________________________________\n");
  655.     printf("Process\t|  FCFS  |  SJF(P)  |  SJF(NP)  |  Priority  |  Round Robin  |\n");
  656.     printf("-----------------------------------------------------------------------------\n");
  657.     int i;
  658.     for(i=0; i<n; i++){
  659.             printf("  p%d   \t|", i);
  660.             if(vFcfs[i]<=9)printf("   %.0lf    |", vFcfs[i]);
  661.             else printf("   %.0lf   |",vFcfs[i]);
  662.             if(vSjfP[i]<=9)printf("    %.0lf     |", vSjfP[i]);
  663.             else printf("    %.0lf    |", vSjfP[i]);
  664.             if(vSjfNP[i]<=9)printf("     %.0lf     |", vSjfNP[i]);
  665.             else printf("     %.0lf    |", vSjfNP[i]);
  666.             if(vPriority[i]<=9)printf("     %.0lf      |", vPriority[i]);
  667.             else printf("     %.0lf     |", vPriority[i]);
  668.             if(vRoundRobin[i]<=9)printf("       %.0lf      |\n", vRoundRobin[i]);
  669.             else printf("       %.0lf     |\n", vRoundRobin[i]);
  670.     //printf("   %d   \t|\t %.0lf  \t|\t   %.0lf   \t|\t   %.0lf   \t|\t   %.0lf    \t|\t     %.0lf     \t|\n", i,vFcfs[i],vSjfP[i],vSjfNP[i],vPriority[i],vRoundRobin[i]);
  671.     }
  672.     printf("-----------------------------------------------------------------------------\n");
  673.     printf("Avg. of\t|");
  674.     if(vFcfs[i]<=9.0)printf("  %.2lf   |", vFcfs[i]);
  675.             else printf("  %.2lf  |",vFcfs[i]);
  676.             if(vSjfP[i]<=9.0)printf("   %.2lf   |", vSjfP[i]);
  677.             else printf("   %.2lf  |", vSjfP[i]);
  678.             if(vSjfNP[i]<=9.0)printf("    %.2lf   |", vSjfNP[i]);
  679.             else printf("   %.2lf   |", vSjfNP[i]);
  680.             if(vPriority[i]<=9.0)printf("    %.2lf    |", vPriority[i]);
  681.             else printf("    %.2lf   |", vPriority[i]);
  682.             if(vRoundRobin[i]<=9.0)printf("      %.2lf    |\n", vRoundRobin[i]);
  683.             else printf("      %.2lf   |\n", vRoundRobin[i]);
  684.     printf("Wt. Time|");
  685.     printf("--------------------------------------------------------------------\n");
  686. }
  687.  
  688.  
  689. int main()
  690. {
  691.  
  692.     int choice;
  693.  
  694.     inputTaken=false;
  695.  
  696.     printf("\t\t****CPU Scheduling Algorithms****\n");
  697.  
  698.     do
  699.     {
  700.  
  701.         printf("\n\tPlease select any one from below: \n");
  702.         printf("\t1. Take input\n");
  703.         printf("\t2. Show results for FCFS algorithm\n");
  704.         printf("\t3. Show results for SJF(Preemptive) algorithm\n");
  705.         printf("\t4. Show results for SJF(Non-preemptive) algorithm\n");
  706.         printf("\t5. Show results for Priority Scheduling algorithm\n");
  707.         printf("\t6. Show results for Round Robin algorithm\n");
  708.         printf("\t7. Compare Algorithms\n");
  709.         printf("\t8. Quit\n");
  710.  
  711.         scanf("%d", &choice);
  712.  
  713.         switch(choice)
  714.         {
  715.         case 1:
  716.             takeInput();
  717.             break;
  718.         case 2:
  719.             fcfs();
  720.             break;
  721.         case 3:
  722.             sjfPreem();
  723.             break;
  724.         case 4:
  725.             sjfNonPreem();
  726.             break;
  727.         case 5:
  728.             priorityScheduling();
  729.             break;
  730.         case 6:
  731.             roundRobin();
  732.             break;
  733.         case 7:
  734.             compare();
  735.             break;
  736.         case 8:
  737.             printf("\t####Thank You####\n");
  738.             break;
  739.  
  740.         default:
  741.             printf("\t***Invalid choice! Try again!***\n");
  742.             break;
  743.         }
  744.  
  745.     }while(choice!=8);
  746.  
  747. }
  748.  
  749. /*4
  750. 0 4 3
  751. 1 10 1
  752. 1 2 2
  753. 2 5 5
  754. 2*/
Add Comment
Please, Sign In to add comment