Menu
Problem: I have 3 machines, each machine have a limit of 30 ms time, each machine have 3 zones that a task can't be executed there. The tasks have a P (priority) and W (weight, which is the time to complete the task in this setup), tasks must be first ordered by a priority, from lower to higher like this:
Task 01 {6, 2} // P/W = 3 this task executed last (3)
Task 02 {7, 7} // P/W = 1 this task executed first (1)
Task 03 {4, 2} // P/W = 2 this task executed second (2)
Now, in order to execute a tasks(I have 6), I must check all 3 machines to find the first fit to the task, to chose a fit for task, it must be the optimal in the 3 machines, example:
Machine 01; |-----5----9-------16-17--19-20|
Machine 02: |----4-5--7-8---------17-18--|
Machine 03: |-----5---8--10---13--15---18--|
(1)Task 02 executed in machine 02 (We look for P ms to execute task, and the minimum time to start a task, since both machine 01 (starting from 9 ms) and 02 (starting from 8 ms) have a 7 ms free time, machine 02 can start a task first then the machine 01).
(2)Task 03 executed in machine 02 (We look for P ms to execute task).
(3)Task 01 executed in machine 01 (We look for P ms to execute task).
Certain periods of time are defined as critical, and cannot be used to schedule a job. These periods (for instance 5-9, 7-8), are stored in the dedicated struct z_indispo.
The bfeet struct is used to store in witch the task start and in witch machine.
I implemented mostly the entire algorithm in C, but my results are different than expected:
#include <stdio.h>
typedef struct _z_indispo {
int t1;
int t2;
} z_indispo;
typedef struct _machines {
int t[20]; // array represent time
z_indispo zone[2];
} machines;
typedef struct _tache {
int p;
int w;
int c; // p/w
int i; // Task number
} tache;
typedef struct _bfeet {
int t; // Store the time to of ending execution by a task
int m; // The machine responsible for executing a task.
} bfeet;
int main(int argc, char **argv)
{
machines m[4];
tache j[6];
tache j_tmp;
bfeet b[4];
int i = 0;
int n = 0;
int u = 0;
int k = 0;
int count = 0;
int trouver = 0;
int f_totale = 0;
int f[3] = {0};
m[0].zone[0].t1 = 7;
m[0].zone[0].t2 = 9;
m[0].zone[1].t1 = 14;
m[0].zone[1].t2 = 15;
m[1].zone[0].t1 = 8;
m[1].zone[0].t2 = 9;
m[1].zone[1].t1 = 16;
m[1].zone[1].t2 = 17;
m[2].zone[0].t1 = 7;
m[2].zone[0].t2 = 8;
m[2].zone[1].t1 = 18;
m[2].zone[1].t2 = 19;
/*
* Initialise all machines
* 0: Represent free time.
* -1: Represent critical zone range.
* -2: Represent a task already executed.
*/
for(i = 0; i< 3; ++i)
{
for(count = 0; count < 20; ++count)
{
if((count >= m[i].zone[0].t1 - 1 && count <= m[i].zone[0].t2 - 1) ||
(count >= m[i].zone[1].t1 - 1 && count <= m[i].zone[1].t2 - 1))
{
m[i].t[count] = -1;
}
else
{
m[i].t[count] = 0;
}
}
}
for(i = 0; i< 3; ++i)
{
if(i == 0)
printf(" D(1,1) t1 s1 D(1,2) t2 s2 D(1,3)\n");
else if(i == 1)
printf(" D(2,1) t1 s1 D(2,2) t2 s2 D(2,3)\n");
else if(i == 2)
printf(" D(3,1) t1 s1 D(3,2) t2 s2 D(3,3)\n");
printf("|");
for(count = 0; count < 20; ++count)
{
printf("%3d", m[i].t[count]);
}
printf(" |\n\n");
}
j[0].p = 5;
j[0].w = 2;
j[0].i = 1;
j[1].p = 9;
j[1].w = 3;
j[1].i = 2;
j[2].p = 6;
j[2].w = 3;
j[2].i = 3;
j[3].p = 6;
j[3].w = 4;
j[3].i = 4;
j[4].p = 7;
j[4].w = 7;
j[4].i = 5;
/*
* Calc C = P/W .
*/
for(count = 0; count < 5; ++count)
{
j[count].c = j[count].p / j[count].w;
}
/*
* Sort tasks from low to hight
*/
for(count = 0; count < 5; ++count)
{
for(k = 0; k < 5 - count; ++k)
{
if(j[k].c > j[k + 1].c)
{
j_tmp = j[k + 1];
j[k + 1] = j[k];
j[k] = j_tmp;
}
}
}
/*printf("|%2J |%2 P |%2 W | C |\n");
printf("_____________________\n");
for(count = 0; count < 5; ++count)
{
printf("|%-4d|%-4d|%-4d|%-4d|\n", j[count].i, j[count].p, j[count].w, j[count].c);
}
printf("\n");*/
/*
* Execute tasks
*/
while(n < 5)
{
for(count = 0; count < 3; ++count)
{
i = 0;
trouver = 0;
while(i <= 20 && trouver != 1)
{
if(m[count].t[i] == 0) // We have a free time to start with it.
{
u = 0; // num of available indexs.
while(m[count].t[i] != -1 && m[count].t[i] != -2)
{
if(u == j[n].p)
break;
++u;
++i;
}
if(u < j[n].p)
{
while(m[count].t[i] == -1 && m[count].t[i] == -2) // bypass unfree unites
++i;
}
else if(u == j[n].p)
{
b[count].t = i - u;
b[count].m = count; //
trouver = 1; // we find the Necessary unites to start a task
}
}
else
++i;
}
}
if(u < j[n].p)
printf("There is no free time to execute task %d", j[n].i);
else
{
// Find the minimum time in all machines to start a task
b[3].t = b[0].t;
b[3].m = b[0].m;
for(count = 0; count < 3; ++count)
{
if(b[3].t > b[count + 1].t)
{
b[3].t = b[count + 1].t;
b[3].m = b[count + 1].m;
}
}
// Put -2 to indicate that index is unfree
u = b[3].t + j[n].p;
for(count = b[3].t; count < u; ++count)
{
m[b[3].m].t[count] = -2;
}
if(b[3].m == 0)
f[0] = (b[3].t + j[n].p);
else if(b[3].m == 1)
f[1] = (b[3].t + j[n].p);
else if(b[3].m == 2)
f[2] = (b[3].t + j[n].p);
printf("Task %d end at %-2d, machine %d.\n", j[n].i, b[3].t + j[n].p, b[3].m + 1);
}
++n;
}
printf("\n");
f_totale = f[0] + f[1] + f[2];
printf("F of machine 01: %d.\n", f[0]);
printf("F of machine 02: %d.\n", f[1]);
printf("F of machine 03: %d.\n", f[2]);
printf("Total F: %d.\n", f_totale);
printf("\n");
/*printf("\n");
for(i = 0; i< 3; ++i)
{
if(i == 0)
printf(" D(1,1) t1 s1 D(1,2) t2 s2 D(1,3)\n");
else if(i == 1)
printf(" D(2,1) t1 s1 D(2,2) t2 s2 D(2,3)\n");
else if(i == 2)
printf(" D(3,1) t1 s1 D(3,2) t2 s2 D(3,3)\n");
printf("|");
for(count = 0; count < 20; ++count)
{
printf("%3d", m[i].t[count]);
}
printf(" |\n\n");
}*/
return 0;
}
UPDATE: I have now only two unavailability zones in each machine. I also updated the code to fix some errors, but I still get a different output then this example: I have this unavailability zones:
m[0].zone[0].t1 = 7;
m[0].zone[0].t2 = 9;
m[0].zone[1].t1 = 14;
m[0].zone[1].t2 = 15;
m[1].zone[0].t1 = 8;
m[1].zone[0].t2 = 9;
m[1].zone[1].t1 = 16;
m[1].zone[1].t2 = 17;
m[2].zone[0].t1 = 7;
m[2].zone[0].t2 = 8;
m[2].zone[1].t1 = 18;
m[2].zone[1].t2 = 19;
5 tasks:
p | 6 9 5 7 6
w | 3 3 2 7 4
_______________
c | 2 3 2 1 1
After ordering by c:
p | 7 6 5 6 9
w | 7 4 2 3 3
_______________
c | 1 1 2 2 3
The execution of tasks should be like this:
J4
|_______7__9_____14_15__________| ms
Task 04 should end at 7, P represent the time necessary to execute a task.
J5
|________8_9__________16_17_____| ms
Task 05 should end at 7.
J1 J3
|_______7_8_______________18_19_| ms
Task 01 should end at 6, task 03 should end at 14.
UPDATE 02: (This problem fixed)
I noticed a strange behavior in my program, after I initializing m[i].t[count] array, I found that variables responsible for storing unavailability zones changed: NOTE: This problem fixed.
UPDATE03: (This problem fixed but with new issue)
I have situation when a task can't find the necessary unites to start, I never get this message "There is no free time to execute task ", witch I should receive it for task 2, since it has 9 unites, and all machines have no such of free time like that. The code responsible for this test:
for(count = 0; count < 3; ++count) // search on all machines
{
i = 0;
trouver = 0;
while(i < 20 && trouver != 1)
{
if(m[count].t[i] == 0) // We have a free time to start with it.
{
u = 0; // num of available indexs.
while(m[count].t[i] != -1 && m[count].t[i] != -2)
{
if(u == j[n].p)
break;
++u;
++i;
}
if(u < j[n].p)
{
while(m[count].t[i] == -1 && m[count].t[i] == -2) // bypass unfree unites
++i;
}
else if(u == j[n].p)
{
b[count].t = i - u;
b[count].m = count; //
trouver = 1; // we find the Necessary unites to start a task
}
}
else
++i;
}
}
/* u represent the number of continuous free time,
j[n].p represent the necessary time to execute the current task, n is the current task
if(u < j[n].p)
printf("There is no free time to execute task %d", j[n].i);
else
{
// Find the minimum time in all machines to start a task
b[3].t = b[0].t;
b[3].m = b[0].m;
UPDATE04:
Now I can see excluded task when there is no free time to execute a task, however, the output is not right, because I see a task override the period time on another task:
while(n < 5)
{
k = 0;
for(count = 0; count < 3; ++count)
{
i = 0;
u = 0;
trouver = 0;
while(i < 20 && trouver != 1)
{
if(m[count].t[i] == 0) // We have a free time to start with it.
{
//u = 0; // num of available indexs.
if(u == j[n].p)
break;
else
{
++u;
++i;
}
}
if(u != j[n].p)
{
if((m[count].t[i] == -1 || m[count].t[i] == -2))// bypass unfree unites
{
u = 0;
++i;
}
}
if(u == j[n].p)
{
++k;
b[count].t = i - u;
b[count].m = count; //
trouver = 1; // we find the Necessary unites to start a task
}
}
}
if(u != j[n].p)
{
printf("There is no free time to execute task %d.\n", j[n].i);
}
else
{
// Find the minimum time in all machines to start a task
b[3] = b[0];
for(count = 0; count < 3; ++count)
{
if(b[count].t != 0)
if(b[3].t > b[count + 1].t)
{
b[3] = b[count + 1];
}
}
// Put -2 to indicate that index is unfree
u = b[3].t + j[n].p;
for(count = b[3].t; count < u; ++count)
{
m[b[3].m].t[count] = -2;
}
if(b[3].m == 0)
f[0] = (b[3].t + j[n].p);
else if(b[3].m == 1)
f[1] = (b[3].t + j[n].p);
else if(b[3].m == 2)
f[2] = (b[3].t + j[n].p);
printf("Task %d end at %-2d, machine %d.\n", j[n].i, b[3].t + j[n].p, b[3].m + 1);
}
++n;
}
Output:
D(1,1) t1 s1 D(1,2) t2 s2 D(1,3)
| 0 0 0 0 0 0 -1 -1 -1 0 0 0 0 -1 -1 0 0 0 0 0 |
D(2,1) t1 s1 D(2,2) t2 s2 D(2,3)
| 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 -1 -1 0 0 0 |
D(3,1) t1 s1 D(3,2) t2 s2 D(3,3)
| 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 -1 -1 0 |
| J | P | W | C |
_____________________
|1 |5 |2 |2 |
|2 |7 |3 |2 |
|3 |8 |3 |2 |
|5 |17 |7 |2 |
|4 |16 |4 |4 |
Task 1 end at 5 , machine 1.
Task 2 end at 7 , machine 1.
Task 3 end at 8 , machine 1.
There is no free time to execute task 5.
There is no free time to execute task 4.
F of machine 01: 8.
F of machine 02: 0.
F of machine 03: 0.
Total F: 8.
D(1,1) t1 s1 D(1,2) t2 s2 D(1,3)
| -2 -2 -2 -2 -2 -2 -2 -2 -1 0 0 0 0 -1 -1 0 0 0 0 0 |
D(2,1) t1 s1 D(2,2) t2 s2 D(2,3)
| 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 -1 -1 0 0 0 |
D(3,1) t1 s1 D(3,2) t2 s2 D(3,3)
| 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 -1 -1 0 |
230
First Fit Algorithm is the simplest technique of allocating the memory block to the processes amongst all. In this algorithm, the pointer keeps track of all the free blocks in the memory and accepts the request of allocating a memory block to the coming process.
The first fit memory allocation scheme checks the empty memory block in a sequential manner. This means that the memory block found empty at the first attempt is checked for size. If the size is not less than the required size, it is allocated.
Since only the Best-fit can allocate all processes in the memory, it is the best algorithm to make the most efficient use of memory.
What is Best Fit Algorithm? Best Fit is a memory management algorithm; it deals with allocating smallest free partition which meets the requirement of the requesting process.
I found that the problem was in how I search for the minimum starting time in the machines to start task:
....
// Find the minimum time in all machines to start a task
b[3] = b[0]; // this cause the problem
for(count = 0; count < 3; ++count)
{
if(b[count].t != 0)
if(b[3].t > b[count + 1].t)
{
b[3] = b[count + 1];
}
}
b[3] as start could refer to a machine that can't start the current task, so I made a little change:
// Find the minimum time in all machines to start a task
for(count = 0; count < 3; ++count) // search only in the machines that can execute the current task
{
if(b[count].m != -1)
{
b[3] = b[count];
break;
}
}
for(count = 0; count < 3; ++count) // search for the first machines that can execute the current task
{
if(b[count].m != -1)
{
if((b[3].t > b[count + 1].t) && (b[count + 1].m != -1)) // make sure the next machine can start the current task
{
b[3] = b[count + 1];
}
}
}
The complete algorithm:
#include <stdio.h>
typedef struct _z_indispo {
int t1;
int t2;
} z_indispo;
typedef struct _machines {
int t[20]; // array represent time
z_indispo zone[2];
} machines;
typedef struct _tache {
int p;
int w;
int c; // p/w
int i; // Task number
} tache;
typedef struct _bfeet {
int t; // Store the time to of ending execution by a task
int m; // The machine responsible for executing a task.
} bfeet;
int main(int argc, char **argv)
{
machines m[4] = {0};
tache j[6];
tache j_tmp;
bfeet b[4] = {0};
int i = 0;
int n = 0;
int u = 0;
int k = 0;
int count = 0;
int trouver = 0;
int f_totale = 0;
int f[3] = {0};
m[0].zone[0].t1 = 7;
m[0].zone[0].t2 = 9;
m[0].zone[1].t1 = 14;
m[0].zone[1].t2 = 15;
m[1].zone[0].t1 = 8;
m[1].zone[0].t2 = 9;
m[1].zone[1].t1 = 16;
m[1].zone[1].t2 = 17;
m[2].zone[0].t1 = 7;
m[2].zone[0].t2 = 8;
m[2].zone[1].t1 = 18;
m[2].zone[1].t2 = 19;
/*
* Initialise all machines
* 0: Represent free time.
* -1: Represent critical zone range.
* -2: Represent a task already executed.
*/
for(i = 0; i< 3; ++i)
{
for(count = 0; count < 20; ++count)
{
if((count >= m[i].zone[0].t1 - 1 && count <= m[i].zone[0].t2 - 1) ||
(count >= m[i].zone[1].t1 - 1 && count <= m[i].zone[1].t2 - 1))
{
m[i].t[count] = -1;
}
else
{
m[i].t[count] = 0;
}
}
}
for(i = 0; i< 3; ++i)
{
if(i == 0)
printf(" D(1,1) t1 s1 D(1,2) t2 s2 D(1,3)\n");
else if(i == 1)
printf(" D(2,1) t1 s1 D(2,2) t2 s2 D(2,3)\n");
else if(i == 2)
printf(" D(3,1) t1 s1 D(3,2) t2 s2 D(3,3)\n");
printf("|");
for(count = 0; count < 20; ++count)
{
printf("%3d", m[i].t[count]);
}
printf(" |\n\n");
}
j[0].p = 5;
j[0].w = 2;
j[0].i = 1;
j[1].p = 7;
j[1].w = 3;
j[1].i = 2;
j[2].p = 4;
j[2].w = 1;
j[2].i = 3;
j[3].p = 6;
j[3].w = 4;
j[3].i = 4;
j[4].p = 7;
j[4].w = 7;
j[4].i = 5;
/*
* Calc C = P/W .
*/
for(count = 0; count < 5; ++count)
{
j[count].c = j[count].p / j[count].w;
}
/*
* Sort tasks from low to hight
*/
for(count = 0; count < 5; ++count)
{
for(k = 0; k < 5 - count; ++k)
{
if(j[k].c > j[k + 1].c)
{
j_tmp = j[k + 1];
j[k + 1] = j[k];
j[k] = j_tmp;
}
}
}
printf("|%2J |%2 P |%2 W | C |\n");
printf("_____________________\n");
for(count = 0; count < 5; ++count)
{
printf("|%-4d|%-4d|%-4d|%-4d|\n", j[count].i, j[count].p, j[count].w, j[count].c);
}
printf("\n");
/*
* Execute tasks
*/
while(n < 5)
{
k = 0;
for(count = 0; count < 3; ++count)
{
i = 0;
u = 0;
trouver = 0;
while(i < 20 && trouver != 1)
{
if(m[count].t[i] == 0) // we find a free unite
{
while(m[count].t[i] == 0 && u != j[n].p && i < 20) // count a continues free time, quit when u equal the necessary time to execute the current task
{
++u;
++i;
}
if(u == j[n].p) // we found a free continues time
{
b[count].t = i - u; // save the starting index
b[count].m = count; // save the machine responsible for executing the current task
++k;
trouver = 1;
}
else if(u != j[n].p) // if we encounter zone unavailability or index reserved by another task
{
u = 0; // restart u counter
while((m[count].t[i] == -1 || m[count].t[i] == -2) && (i < 20)) // bypass reserved/unavailability index's
++i;
}
}
else
++i; // bypass reserved/unavailability index's
}
if(trouver != 1) // we mark this machine as it can't execute the current task
{
b[count].m = -1;
}
}
if(k == 0)
printf("There is no free time to execute task %d.\n", j[n].i);
else
{
// Find the minimum time in all machines to start a task
for(count = 0; count < 3; ++count) // search only in the machines that can execute the current task
{
if(b[count].m != -1)
{
b[3] = b[count];
break;
}
}
for(count = 0; count < 3; ++count) // search only in the machines that can execute the current task
{
if(b[count].m != -1)
{
if((b[3].t > b[count + 1].t) && (b[count + 1].m != -1))
{
b[3] = b[count + 1];
}
}
}
// Put -2 to indicate that index as unfree
u = b[3].t + j[n].p;
for(count = b[3].t; count < u; ++count)
{
m[b[3].m].t[count] = -2;
}
if(b[3].m == 0)
f[0] = f[0] + (b[3].t + j[n].p) * j[n].w;
else if(b[3].m == 1)
f[1] = f[1] + (b[3].t + j[n].p) * j[n].w;
else if(b[3].m == 2)
f[2] = f[2] + (b[3].t + j[n].p) * j[n].w;
printf("Task %d end at %-3dms, machine %d.\n", j[n].i, b[3].t + j[n].p, b[3].m + 1);
}
++n;
}
printf("\n");
f_totale = f[0] + f[1] + f[2];
printf("F of machine 01: %d.\n", f[0]);
printf("F of machine 02: %d.\n", f[1]);
printf("F of machine 03: %d.\n", f[2]);
printf("Total F: %d.\n", f_totale);
printf("\n");
printf("\n");
for(i = 0; i< 3; ++i)
{
if(i == 0)
printf(" D(1,1) t1 s1 D(1,2) t2 s2 D(1,3)\n");
else if(i == 1)
printf(" D(2,1) t1 s1 D(2,2) t2 s2 D(2,3)\n");
else if(i == 2)
printf(" D(3,1) t1 s1 D(3,2) t2 s2 D(3,3)\n");
printf("|");
for(count = 0; count < 20; ++count)
{
printf("%3d", m[i].t[count]);
}
printf(" |\n\n");
}
return 0;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With