Question: You need to simulate the execution of a set of tasks that are given to

Question

Question:

You need to simulate the execution of a set of tasks that are given to you. Assume that there are an infinite number of processors available, so that each task starts as soon as it becomes ready. This means that you need to keep track of which tasks are active at any given point in time, and remove them from the active list as they finish.

Assume that the input consists of a set of tasks given in increasing order of start time, and each task has a certain duration associated. First line of the file is number of tasks. For example,

---

3

2 5

4 23

7 4

---

This means that there are 3 tasks. The first one starts at time 2, and ends at 7 (2+5). Second starts at 4, ends at 27. Third starts at 7, ends at 11. We assume each task starts as soon as it is ready, and does not need to wait for a processor or anything else to free up.

This means we can keep track of number of active tasks as follows:

Time #tasks

0 - 2 0

2 - 4 1

4 - 7 2

7 - 11 2

11 - 27 1

* End of simulation timeExpected output is 3 numbers:The simulation ends at T=27.

* Max number of active tasks at any given time

* Average number of active tasks over the entire duration, printed to 4 decimal places (use printf("%.4f"))

So expected output for the above inputs is:

---

27

2

1.1852

---

Average active tasks over entire duration is computed here as :

[ 0x(2-0) + 1x(4-2) + 2x(11-4) + 1x(27-11) ] / 27

Assume number of tasks can be up to 1,000,000. Minimum duration of a task is 1 (all durations and start times integers) and max duration of a task is 1000. Earliest possible start time is 0.

My attempt:

I have used C++ for this. I have been able to get the first output. How do I get the other two?

#include #include "stdio.h" "stdlib.h" typedef struct tong int start; int dur ) task; int main) long int num tasks, endtime; tong int maxtime0 scanf("%ld" ,&num-tasks); task *t new task(num-tasks); scanf("Ald %d",&t [1].start,&t [i].dur); endtime til start +tli,dur: if (endtime » maxtime) maxtime-endtime printf("idn" ,maxtime)

Explanation / Answer

#include <iostream>
#include<stdio.h>
#include<stdlib.h>

typedef struct
{
long int start,end; // new variable end added
int dur;
}task;

using namespace std;

int main()
{
long int num_tasks;
long int endtime;
long int maxtime = 0;
scanf("%ld",&num_tasks);
task *t = new task[num_tasks];
  
for(int i=0;i<num_tasks;i++)
{
scanf("%ld %d",&t[i].start,&t[i].dur);
endtime = t[i].start + t[i].dur;
t[i].end = endtime; // extra code
if(endtime>maxtime)
maxtime = endtime;
}
  
// edited code
  
long int *alltime = new long int[2*num_tasks+1];
alltime[0] = 0;
  
for(int i=1;i<=num_tasks;i++)
{
alltime[i] = t[i-1].start;
}
  
for(int i=num_tasks+1;i<2*num_tasks+1;i++)
{
alltime[i] = t[i-num_tasks-1].end;
}
  
  

for(int i=1;i<2*num_tasks;i++)
{
for(int j=i+1;j<2*num_tasks+1;j++)
{
if(alltime[i]>alltime[j])
{
long int temp = alltime[i];
alltime[i] = alltime[j];
alltime[j] = temp;
}
}
}
  
// alltime for the give case is of the form 0 2 4 7 7 11 27
  
long int **timeinter = new long int*[2]; // for the given case timeinter is 2 2 3 0 4 16
for(int i = 0; i < 2; ++i) // 0 1 2 0 2 1
{
timeinter[i] = new long int[2*num_tasks];
}
  
for(int i=0;i<2*num_tasks;i++)
{
timeinter[0][i] = alltime[i+1] - alltime[i];
timeinter[1][i] = 0;
}


// finding expected value

double expc = 0;
for(int i =0;i<2*num_tasks;i++)
{
for(int j=0;j<num_tasks;j++)
{
if((t[j].start<=alltime[i] && t[j].end>=alltime[i+1])&&(alltime[i+1]>alltime[i]))
{
timeinter[1][i] = timeinter[1][i] + 1;
}
}
expc = expc + timeinter[0][i]*timeinter[1][i];
}
  

// for finding Max number of active tasks
  
expc = expc/27;
long int max_task = timeinter[1][0];
  
for(int i=1;i<2*num_tasks;i++)  
{
if(timeinter[1][i]>max_task)
{
max_task = timeinter[1][i];
}
}
  
// display
  
printf("%ld ", maxtime);
printf("%ld ", max_task);
printf("%.4f ",expc);
  
  
for(int i = 0; i < 2; ++i) {
delete [] timeinter[i];
}
delete [] timeinter;

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.