-
Notifications
You must be signed in to change notification settings - Fork 8
/
greedy.c
263 lines (224 loc) · 6.26 KB
/
greedy.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* My teacher did not supply me the inputs, so I generated the service
times randomly */
int *genjobs ( int n )
{
int *t, i;
t = (int *)malloc(n * sizeof(int));
for (i=0; i<n; ++i) {
t[i] = 1 + rand() % 30;
printf("%3d", t[i]);
if (i % 25 == 24) printf("\n");
}
if (n % 25) printf("\n");
return t;
}
/* Returns the running time of the kth counter having schedule s */
int runtime ( int *t, int *s, int k )
{
int i, T = 0;
for (i=0; i<k; ++i) T += t[s[i]];
return T;
}
/* Returns the maximum of the running times of the p processors */
int makespan ( int *t, int **S, int p )
{
int i, ms = -1, rt;
for (i=0; i<p; ++i) {
rt = runtime(t,S[i]+1,S[i][0]);
if (rt > ms) ms = rt;
}
return ms;
}
/* Returns the total waiting time of customers scheduled to counter k */
int waittime ( int *t, int *s, int k )
{
int i, rt = 0, wt = 0;
for (i=0; i<k; ++i) {
wt += rt;
rt += t[s[i]];
}
return wt;
}
/* Returns the sum of waittime() for all k */
int totalwaittime ( int *t, int **S, int p )
{
int i, wt = 0;
for (i=0; i<p; ++i) wt += waittime(t,S[i]+1,S[i][0]);
return wt;
}
/* Function to neatly print the schedule S on p counters. S contains
only the token numbers, so t also needs to be passed. */
void printschedule ( int **S, int p, int *t )
{
int i, j;
for (i=0; i<p; ++i) {
printf("Counter %2d: ", i);
for (j=1; j<=S[i][0]; ++j) {
printf("%3d (%2d) ", S[i][j], t[S[i][j]]);
if ((j < S[i][0]) && (j % 7 == 0)) printf("\n ");
}
printf("\n");
}
}
int **schedule1 ( int *t, int n, int p )
{
int **S, *freeat, i, j, min, minidx;
/* Allocate memory to S */
S = (int **)malloc(p * sizeof(int *));
for (j=0; j<p; ++j) {
/* No more than n entries are necessary for each processor including
the count at index zero. In fact, an allocation size of
1+(n-(p-1)) is safe. */
S[j] = (int *)malloc(n * sizeof(int));
S[j][0] = 0;
}
/* Array to store the f_j vales */
freeat = (int *)malloc(p * sizeof(int));
for (j=0; j<p; ++j) freeat[j] = 0;
for (i=0; i<n; ++i) {
/* Compute p-fold minimum. This takes O(p) time. This can be improved
to O(log p) time by using a min priority queue. But it is difficult
to break ties using a min priority queue in the fashion described
in the assignment. */
min = freeat[0]; minidx = 0;
for (j=1; j<p; ++j) {
if (freeat[j] < min) {
min = freeat[j];
minidx = j;
}
}
++S[minidx][0];
S[minidx][S[minidx][0]] = i;
freeat[minidx] += t[i];
}
free(freeat);
return S;
}
/* We want to merge sort t[] in the non-increasing order. But relocation
of elements in t[] lets us lose the initial association of the token
number i with t[i]. So we do not change t[] at all. We instead look
into t[] via the index array idx[]. Initially, we have idx[i] = i for
all i. When merge sort wants to relocate t[i] to index j, we put
idx[j] = i. This means that t[idx[j]] is supposed to contain t[i].
At the end, t[idx[0]], t[idx[1]], ..., t[idx[n-1]] is the desired
sorted sequence. */
void mergesort ( int *t, int L, int R, int *idx )
{
int L1, R1, L2, R2, i, j, k, *idxcpy;
if (R <= L) return;
L1 = L; R1 = (L + R) / 2; L2 = R1 + 1; R2 = R;
mergesort(t,L1,R1,idx);
mergesort(t,L2,R2,idx);
idxcpy = (int *)malloc((R - L + 1) * sizeof(int));
i = L1; j = L2; k = 0;
while ((i <= R1) && (j <= R2)) {
if (t[idx[i]] >= t[idx[j]]) {
idxcpy[k] = idx[i];
++i;
} else {
idxcpy[k] = idx[j];
++j;
}
++k;
}
while (i <= R1) {
idxcpy[k] = idx[i];
++i; ++k;
}
while (j <= R2) {
idxcpy[k] = idx[j];
++j; ++k;
}
for (i=0; i<=R-L; ++i) idx[L+i] = idxcpy[i];
free(idxcpy);
}
/* This is same as schedule1() with the exception that we look into t[]
via the index array idx[]. */
int **schedule2 ( int *t, int n, int p )
{
int **S, *freeat, *idx, i, j, min, minidx;
idx = (int *)malloc(n * sizeof(int));
for (i=0; i<n; ++i) idx[i] = i;
mergesort(t,0,n-1,idx);
S = (int **)malloc(p * sizeof(int *));
for (j=0; j<p; ++j) {
S[j] = (int *)malloc(n * sizeof(int));
S[j][0] = 0;
}
freeat = (int *)malloc(p * sizeof(int));
for (j=0; j<p; ++j) freeat[j] = 0;
for (i=0; i<n; ++i) {
min = freeat[0]; minidx = 0;
for (j=1; j<p; ++j) {
if (freeat[j] < min) {
min = freeat[j];
minidx = j;
}
}
++S[minidx][0];
S[minidx][S[minidx][0]] = idx[i];
freeat[minidx] += t[idx[i]];
}
free(freeat);
return S;
}
/* Modifies the schedule of Part 2 inline */
void schedule3 ( int **S, int p )
{
int i, j, tmp;
/* Reverse the schedule of each counter */
for (i=0; i<p; ++i) {
for (j=1; j<=S[i][0]/2; ++j) {
tmp = S[i][j];
S[i][j] = S[i][S[i][0]+1-j];
S[i][S[i][0]+1-j] = tmp;
}
}
}
/* Courtesy */
void freeall ( int **S1, int **S2, int p, int *t )
{
int i;
for (i=0; i<p; ++i) {
free(S1[i]);
free(S2[i]);
}
free(S1);
free(S2);
free(t);
}
int main ( int argc, char *argv[] )
{
int n, p;
int *t;
int **S1, **S2;
srand((unsigned int)time(NULL));
if (argc >= 3) {
n = atoi(argv[1]); p = atoi(argv[2]);
} else {
printf("Enter n and p: ");
scanf("%d%d", &n, &p);
}
printf("\nn = %d\np = %d\n\nEnter customer times:\n\n", n, p);
t = genjobs(n);
printf("\n+++ Schedule 1\n");
S1 = schedule1(t,n,p);
printschedule(S1,p,t);
printf("+++ Bank finishes at time %d\n", makespan(t,S1,p));
printf("+++ Total waiting time = %d\n", totalwaittime(t,S1,p));
printf("\n+++ Schedule 2\n");
S2 = schedule2(t,n,p);
printschedule(S2,p,t);
printf("+++ Bank finishes at time %d\n", makespan(t,S2,p));
printf("+++ Total waiting time = %d\n", totalwaittime(t,S2,p));
printf("\n+++ Schedule 3\n");
schedule3(S2,p);
printschedule(S2,p,t);
printf("+++ Bank finishes at time %d\n", makespan(t,S2,p));
printf("+++ Total waiting time = %d\n\n", totalwaittime(t,S2,p));
freeall(S1,S2,p,t);
exit(0);
}