Round-Robin (RR): Jobs are processed using a fixed time-slice. The jobs are init
ID: 3803706 • Letter: R
Question
Round-Robin (RR): Jobs are processed using a fixed time-slice. The jobs are initially kept in a queue based on the order of arrival. The job at the front of the queue is removed and served similar to the FIFO algorithm. However, unlike the FIFO algorithm, each job is served up to the pre-defined slice of time. If job can be completed within the allotted time it is fully served and removed from the queue. If the job cannot be completed in the allotted time, it is served for the allotted time and then added to the end of the queue to be served later for the remaining time. This process is continued until the queue is empty. The total turnaround time is the total time a job spends in the system: Turnaround time = processing time + waiting time (time spend in queue) For example, it the work load is 15 units, but it spends 50 units of time in queue, waiting to be processed, then the tumaround time is equal to 65 units. A) Write a program to test the effectiveness of these algorithms. Create 100 jobs, each with a random processing time of 0 to 100 time units. Then process the jobs according to the above scheduling methods. You can use an Array List for the FIFO and RR scheduling schemes. Implement the SJF using a binary heap (priority heap). Use a time slice of 20 units. Compare the average turnaround time for the different strategies. B) Experiment with different time slices for the RR strategy and compare the results. Use time slices in increments of 5 units and sec if there are any differences in the average turnaround time.Explanation / Answer
import java.util.Random;
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author Surya
*/
public class Schedulingtester {
//fcfs method which returns the average turn around time on applying fcfs on 100 processes
double fcfs(int n,int AT[],int BT[],int WT[],int TAT[])
{
double AWT=0;//average waiting time
double ATT=0;//average turnaround time
WT[0]=0;
for(int i=1;i<n;i++)
{
WT[i]=WT[i-1]+BT[i-1];
WT[i]=WT[i]-AT[i];
}
for(int i=0;i<n;i++)
{
TAT[i]=WT[i]+BT[i];
AWT=AWT+WT[i];
ATT = ATT+TAT[i];
}
System.out.println(" PROCESS BT WT TAT ");
for(int i=0;i<n;i++)
{
System.out.println(" "+ i + " "+BT[i]+" "+WT[i]+" "+TAT[i]);
}
AWT=AWT/n;
ATT=ATT/n;//calculating ATT
System.out.println("***********************************************");
System.out.println("Avg waiting time="+AWT+" ***********************************************");
return ATT;
}
double round_robin(int a[],int wt[],int tat[],int bt[],int q,int n)//round robin method which returns the average turn around time
{
int i,j,k,sum=0;
for(i=0;i<n;i++)
a[i]=bt[i];
for(i=0;i<n;i++)
wt[i]=0;
do
{
for(i=0;i<n;i++)
{
if(bt[i]>q)
{
bt[i]-=q;
for(j=0;j<n;j++)
{
if((j!=i)&&(bt[j]!=0))
wt[j]+=q;
}
}
else
{
for(j=0;j<n;j++)
{
if((j!=i)&&(bt[j]!=0))
wt[j]+=bt[i];
}
bt[i]=0;
}
}
sum=0;
for(k=0;k<n;k++)
sum=sum+bt[k];
}
while(sum!=0);
for(i=0;i<n;i++)
tat[i]=wt[i]+a[i];
System.out.println("process BT WT TAT");
for(i=0;i<n;i++)
{
System.out.println("process"+(i+1)+" "+a[i]+" "+wt[i]+" "+tat[i]);
}
float avg_wt=0;
float avg_tat=0;
for(j=0;j<n;j++)
{
avg_wt+=wt[j];
}
for(j=0;j<n;j++)
{
avg_tat+=tat[j];
}
System.out.println("average waiting time "+(avg_wt/n)+" Average turn around time"+(avg_tat/n));
return avg_tat;
}
public static void main(String argv[])
{
//variable declaration
int n=100;//number of processes
int a[]=new int[n];//to store arrival time of 100 processes
int b[]=new int[n];//to store service/burst/processing time of 100 processes
int w[]=new int[n];//to store waiting time of 100 processes
int tat[]=new int[n];//to store turaround time of 100 processes
int i,j;
int quanta;//time slice for round robin
double round_robin,fcfs;
Schedulingtester s = new Schedulingtester ();
Random r= new Random();//to generate random number
//generating randomly arrival times from 0 to 100
//if you want to generate arrival times randomly then uncomment it
/*for(i=0;i<n;i++)
{
a[i]=r.nextInt()%101;//random number between 0 to 100 inclusive
}*/
//generating randomly burst/processing times from 0 to 100
for(i=0;i<n;i++)
{
b[i]=(int)r.nextInt()%101;//random number between 0 to 100 inclusive
if(b[i]<0)b[i]=-1*b[i];
}
quanta =20;//using quanta as 20 units
//duplicate
int A[]=new int [n],B[]=new int [n],TAT[]=new int [n],W[]=new int [n];
//copying...
for(i=0;i<n;i++)
{
A[i]=a[i];
B[i]=b[i];
W[i]=w[i];
TAT[i]=tat[i];
}
//calling roundrobin function;
System.out.println(" Round robin:-");
round_robin = s.round_robin(A, W, TAT, B, quanta, n);
//calling fcfs function..
//copying...
for(i=0;i<n;i++)
{
A[i]=a[i];
B[i]=b[i];
W[i]=w[i];
TAT[i]=tat[i];
}
System.out.println(" FCFS:-");
fcfs = s.fcfs(n, A, B, W, TAT);
//comparing round robing average turnaround time to fcfs average turn around time..
System.out.println(" Round robin average turnaround time "+round_robin+" FCFS average turnaroundtime :"+fcfs+" ");
if(fcfs>round_robin)
{
System.out.println("Round robin generates better turnaround time than fcfs");
}
else
{System.out.println("fcfs generates better turnaround time than Round robin");
}
//incrementing round_robin quanta by 5
quanta =25;
double rr1;//after increasing quanta tat
//copying...
for(i=0;i<n;i++)
{
A[i]=a[i];
B[i]=b[i];
W[i]=w[i];
TAT[i]=tat[i];
}
//calling function
System.out.println(" Round robin:-");
rr1=s.round_robin(A, W, TAT, B, quanta, n);
//printing output
System.out.println("After increasing quanta by 5 units ,The turn around time: "+rr1);
}
}
OUTPUT:-
run:
Round robin:-
process BT WT TAT
process1 85 4715 4800
process2 76 4151 4227
process3 6 40 46
process4 38 1838 1876
process5 44 3239 3283
process6 4 86 90
process7 20 90 110
process8 79 4167 4246
process9 77 4186 4263
process10 55 3283 3338
process11 78 4203 4281
process12 46 3318 3364
process13 82 4720 4802
process14 9 230 239
process15 14 239 253
process16 1 253 254
process17 97 4722 4819
process18 96 4739 4835
process19 69 4281 4350
process20 90 4755 4845
process21 29 2076 2105
process22 41 3424 3465
process23 38 2105 2143
process24 48 3425 3473
process25 26 2143 2169
process26 81 4765 4846
process27 54 3453 3507
process28 0 0 0
process29 78 4330 4408
process30 18 494 512
process31 39 2209 2248
process32 26 2228 2254
process33 48 3487 3535
process34 58 3495 3553
process35 84 4766 4850
process36 26 2294 2320
process37 70 4368 4438
process38 55 3553 3608
process39 10 672 682
process40 58 3568 3626
process41 17 702 719
process42 88 4770 4858
process43 43 3606 3649
process44 67 4398 4465
process45 82 4778 4860
process46 55 3649 3704
process47 86 4780 4866
process48 5 839 844
process49 96 4786 4882
process50 87 4802 4889
process51 25 2520 2545
process52 18 904 922
process53 26 2525 2551
process54 42 3724 3766
process55 23 2551 2574
process56 44 3726 3770
process57 41 3730 3771
process58 46 3731 3777
process59 70 4485 4555
process60 81 4809 4890
process61 89 4810 4899
process62 99 4819 4918
process63 95 4838 4933
process64 32 2714 2746
process65 1 1162 1163
process66 70 4575 4645
process67 16 1183 1199
process68 42 3857 3899
process69 25 2766 2791
process70 64 4585 4649
process71 7 1259 1266
process72 45 3879 3924
process73 94 4853 4947
process74 42 3904 3946
process75 62 4609 4671
process76 13 1346 1359
process77 85 4867 4952
process78 70 4631 4701
process79 100 4872 4972
process80 55 3986 4041
process81 52 4001 4053
process82 53 4013 4066
process83 36 2991 3027
process84 28 3007 3035
process85 21 3015 3036
process86 98 4892 4990
process87 49 4046 4095
process88 25 3056 3081
process89 39 3061 3100
process90 13 1619 1632
process91 54 4055 4109
process92 81 4910 4991
process93 44 4089 4133
process94 29 3140 3169
process95 6 1712 1718
process96 58 4093 4151
process97 27 3169 3196
process98 92 4911 5003
process99 74 4721 4795
process100 23 3216 3239
average waiting time 3291.57
Average turn around time3341.6
FCFS:-
PROCESS BT WT TAT
0 85 0 85
1 76 85 161
2 6 161 167
3 38 167 205
4 44 205 249
5 4 249 253
6 20 253 273
7 79 273 352
8 77 352 429
9 55 429 484
10 78 484 562
11 46 562 608
12 82 608 690
13 9 690 699
14 14 699 713
15 1 713 714
16 97 714 811
17 96 811 907
18 69 907 976
19 90 976 1066
20 29 1066 1095
21 41 1095 1136
22 38 1136 1174
23 48 1174 1222
24 26 1222 1248
25 81 1248 1329
26 54 1329 1383
27 0 1383 1383
28 78 1383 1461
29 18 1461 1479
30 39 1479 1518
31 26 1518 1544
32 48 1544 1592
33 58 1592 1650
34 84 1650 1734
35 26 1734 1760
36 70 1760 1830
37 55 1830 1885
38 10 1885 1895
39 58 1895 1953
40 17 1953 1970
41 88 1970 2058
42 43 2058 2101
43 67 2101 2168
44 82 2168 2250
45 55 2250 2305
46 86 2305 2391
47 5 2391 2396
48 96 2396 2492
49 87 2492 2579
50 25 2579 2604
51 18 2604 2622
52 26 2622 2648
53 42 2648 2690
54 23 2690 2713
55 44 2713 2757
56 41 2757 2798
57 46 2798 2844
58 70 2844 2914
59 81 2914 2995
60 89 2995 3084
61 99 3084 3183
62 95 3183 3278
63 32 3278 3310
64 1 3310 3311
65 70 3311 3381
66 16 3381 3397
67 42 3397 3439
68 25 3439 3464
69 64 3464 3528
70 7 3528 3535
71 45 3535 3580
72 94 3580 3674
73 42 3674 3716
74 62 3716 3778
75 13 3778 3791
76 85 3791 3876
77 70 3876 3946
78 100 3946 4046
79 55 4046 4101
80 52 4101 4153
81 53 4153 4206
82 36 4206 4242
83 28 4242 4270
84 21 4270 4291
85 98 4291 4389
86 49 4389 4438
87 25 4438 4463
88 39 4463 4502
89 13 4502 4515
90 54 4515 4569
91 81 4569 4650
92 44 4650 4694
93 29 4694 4723
94 6 4723 4729
95 58 4729 4787
96 27 4787 4814
97 92 4814 4906
98 74 4906 4980
99 23 4980 5003
***********************************************
Avg waiting time=2487.09
***********************************************
Round robin average turnaround time 334160.0
FCFS average turnaroundtime :2537.12
fcfs generates better turnaround time than Round robin
Round robin:-
process BT WT TAT
process1 85 4597 4682
process2 76 4607 4683
process3 6 50 56
process4 38 2245 2283
process5 44 2258 2302
process6 4 106 110
process7 20 110 130
process8 79 4608 4687
process9 77 4612 4689
process10 55 3824 3879
process11 78 4614 4692
process12 46 2377 2423
process13 82 4617 4699
process14 9 280 289
process15 14 289 303
process16 1 303 304
process17 97 4624 4721
process18 96 4646 4742
process19 69 3929 3998
process20 90 4667 4757
process21 29 2523 2552
process22 41 2527 2568
process23 38 2543 2581
process24 48 2556 2604
process25 26 2579 2605
process26 81 4682 4763
process27 54 3998 4052
process28 0 0 0
process29 78 4688 4766
process30 18 604 622
process31 39 2655 2694
process32 26 2669 2695
process33 48 2670 2718
process34 58 4027 4085
process35 84 4691 4775
process36 26 2743 2769
process37 70 4060 4130
process38 55 4080 4135
process39 10 822 832
process40 58 4085 4143
process41 17 857 874
process42 88 4700 4788
process43 43 2844 2887
process44 67 4118 4185
process45 82 4713 4795
process46 55 4160 4215
process47 86 4720 4806
process48 5 1024 1029
process49 96 4731 4827
process50 87 4752 4839
process51 25 1079 1104
process52 18 1104 1122
process53 26 3012 3038
process54 42 3013 3055
process55 23 1172 1195
process56 44 3030 3074
process57 41 3049 3090
process58 46 3065 3111
process59 70 4240 4310
process60 81 4764 4845
process61 89 4770 4859
process62 99 4784 4883
process63 95 4808 4903
process64 32 3211 3243
process65 1 1420 1421
process66 70 4360 4430
process67 16 1446 1462
process68 42 3243 3285
process69 25 1487 1512
process70 64 4380 4444
process71 7 1537 1544
process72 45 3285 3330
process73 94 4828 4922
process74 42 3330 3372
process75 62 4419 4481
process76 13 1644 1657
process77 85 4847 4932
process78 70 4456 4526
process79 100 4857 4957
process80 55 4501 4556
process81 52 4506 4558
process82 53 4508 4561
process83 36 3522 3558
process84 28 3533 3561
process85 21 1857 1878
process86 98 4882 4980
process87 49 3561 3610
process88 25 1928 1953
process89 39 3585 3624
process90 13 1978 1991
process91 54 4536 4590
process92 81 4905 4986
process93 44 3649 3693
process94 29 3668 3697
process95 6 2091 2097
process96 58 4565 4623
process97 27 3697 3724
process98 92 4911 5003
process99 74 4598 4672
process100 23 2197 2220
average waiting time 3250.02
Average turn around time3300.05
After increasing quanta by 5 units
,The turn around time: 330005.0
BUILD SUCCESSFUL (total time: 0 seconds)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.