Solved

Ressurecting LinkedListQueue Question

Posted on 2004-10-19
22
317 Views
Last Modified: 2010-04-15
I posted a thread a while ago on LinkedListQueue data structures.  

The queue is a linear list that stores elements in the order they arrive.

If there is only one element in the queue then the rear and front points to it
I have modified my job scheduler program so that it has a time aspect to it. at time = 2 a job arrives and is enqueued, else no jobs to enqueue.  The user can press the enter key to continue.  This is whats wrong in the code - when a job is enqueued it  start its service time but other jobs are not able to enqueue , that is, certain jobs are missed.  A job (process) executing for the cpu is not the same as the readyQueue.  This means a job cannot start running in the ReadyQueue.  A queue is taken off the queue and then serviced one job at a time. So if a job is running and the time aspect is 3 and it is at that time the next job is to enqueue it should enqueue.   In this case the cpu itself.  


When a process is already enqueued and is ready to run, should it dequeue first so that i can run?  Whilst a job is running, my code fails to enqueue jobs.    

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

#define N 2
#define SIZE 5

typedef struct node
{
      void *process[N];
      int size;
      int arrival_time;
      int cpu;
      struct node *next;
} QUEUE_NODE;

typedef struct
{
      QUEUE_NODE *front;
      QUEUE_NODE *rear;
      int count;
} QUEUE;

/* Prototype declarations */

QUEUE *destroyQueue (QUEUE *queue);
QUEUE *createQueue(void);
QUEUE *destroyQueue (QUEUE *queue);

int dequeue (QUEUE *queue, QUEUE_NODE **itemPtr);
int enqueue (QUEUE *queue, QUEUE_NODE *itemPtr);
int emptyQueue (QUEUE *queue);
int store(QUEUE_NODE *itemPtr);
QUEUE *createQueue (void)
{
      QUEUE *queue;

      queue = (QUEUE *) malloc (sizeof (QUEUE));

      if (queue)
      {
            queue->front = NULL;
            queue->rear = NULL;
            queue->count = 0;
      }

return queue;

} /* createQueue() */

/* Jobs arriving in the ready-queue */
int enqueue (QUEUE *queue, QUEUE_NODE *itemPtr)
{
      QUEUE_NODE *newPtr;

      newPtr = (QUEUE_NODE *) malloc(sizeof(QUEUE_NODE));
      if(!newPtr)
            return(0);                  

      newPtr->process[0] = itemPtr->process[0];
      newPtr->size = itemPtr->size;
      newPtr->arrival_time = itemPtr->arrival_time;
      newPtr->cpu = itemPtr->cpu;
      newPtr->next = NULL;

      if (queue->count == 0)
      {
            queue->front = newPtr;
      }
      else
            
            queue->rear->next = newPtr;
            (queue->count)++;
            queue->rear = newPtr;
      
      return 1;

} /* enqueue() */

int dequeue (QUEUE *queue, QUEUE_NODE **itemPtr)
{
      QUEUE_NODE *deleteLoc;
      
      if (!queue->count)
            return(0);

      *itemPtr = queue->front->process[0];
      deleteLoc = queue->front;printf("We're here\n");
      if (queue->count == 1)
                  queue->rear = queue->front = NULL;
      else
            queue->front = queue->front->next;
            (queue->count)--;
            free (deleteLoc);

            return 1;
} /* dequeue() */

QUEUE *destroyQueue(QUEUE *queue)
{
      QUEUE_NODE *deletePtr;

if(queue)
{
      while(queue->front != NULL)
      {
            free (queue->front->process);
            deletePtr = queue->front;
            queue->front = queue->front->next;
            free (deletePtr);
      } /* end while */
      printf("All jobs processed\n");
      printf("Queue destroyed \n\n");
      free (queue);
} /* end if */

return NULL;

} /* destroyQueue */

int emptyQueue(QUEUE *queue)
{
return (queue->count == 0);
}

int main()
{
int ATIME;
int CTIME;
int partitions[SIZE];
int index = 0;
FILE *fp;
QUEUE *queue;
QUEUE_NODE *jobs;
char dummy;

/* Initialise the queue */
createQueue();

if ((fp = fopen("test.dat","r")) == NULL)
{
      printf("Cannot open file for read.\n");
      exit(1);
}
printf("Jobs arrive for scheduling>\n");

queue = (QUEUE *)malloc(sizeof(QUEUE));
jobs = (QUEUE_NODE *)malloc(sizeof(QUEUE_NODE));


int j = 0;
while(fscanf(fp, "%s %d %d %d", jobs->process, &jobs->size, &jobs->arrival_time,
     &jobs->cpu) != EOF)
{
/* using index = 0 in the for loop here would rely on the number of jobs read in from
  the data file.  Using index on its own this way allows the index (timer) to determine
what is happening */

for(index; index <= jobs->arrival_time; index++)
{

      printf("Time is %d \n", index);

      if(index == jobs->arrival_time)
      {
            printf("%s has arrived in the ready queue at time = %d \n", jobs->process,
                  jobs->arrival_time);
            enqueue(queue, jobs);
for(j = jobs->cpu; j >= 1; j--)
            {
                  printf("\tTime remaining %d, Time is now = %d ", j, index);            
                  printf("press <ENTER> to cycle> ");
                  dummy = getchar();
                  index = index + 1;

            /* check that the cpu time is free */

            if(j == 0)
            {             
                  printf("\n%s has completed its service time and is dequeueing\n", jobs->process);
                  
                  /* remove the job from the queue */
                  dequeue(queue, (void *)&jobs);            
      
      }


            } /* end for */

/* should check if the Queue is empty and start processing a new job */

      }
      else
      {
            printf("no jobs to enqueue\n");
      }

/* Statements for jobs occupying a fixed partition and checking for job execution time */

printf("press <ENTER> to continue> \n");
dummy = getchar();

}

}


fclose(fp);
destroyQueue(queue);
return(0);
}

0
Comment
Question by:gbilios
  • 12
  • 10
22 Comments
 
LVL 16

Expert Comment

by:imladris
Comment Utility
HMmm. Your central loop seems to be:

while  there is another job to process
    for   index<=arrival time  increment index
        print time
        if index == arrival time
            enqueue job
            process job for cpu cycles
            dequeue job
        else
            print no jobs to enqueue


So, in your control loop, when a job arrives, it is *immediately* processed, and while it is processing, nothing else is being done.
A more realistic simulation, and what you presumably really want, is when a job arrives, it is processed if the cpu is free, and otherwise it is queued. Then for each "tick" of the clock you check if a job has arrived, and whether the cpu is free. If a job has arrived you queue it. If the cpu is free you check the queue. If there is a job waiting you dequeue it and put the cpu back to work. So you need another node to indicate the job being processed (something like cpujob = (QUEUE_NODE *)malloc(sizeof(QUEUE_NODE));). Then the control loop would look something like:

initialize cpujob to free
initialize index
read next job
while cpu occupied or job queue not empty or jobs left
   if index==job arrival time
      queue job
      read next job
   if index==cpu completion time
      print finish job
      free cpu
   if cpu is free and job in queue
      start next job
   increment index

0
 
LVL 16

Expert Comment

by:imladris
Comment Utility
Unrelated to that, I am concerned about the process element of the node. It is declared as   "void *process[N];" (where N is 2) and it is being read with a "%s" in the fscanf. The %s directive is used to read a string. If a string is being read, I would expect process to have a declaration that can hold a string. The current declaration declares it to have array (of 2 elements) of pointer to void. This is not conducive to holding a string. To hold a string I would expect something like "char process[20];".
0
 

Author Comment

by:gbilios
Comment Utility
When you free the cpu, do you enqueue the job?  is there a differece because the cpu and the readyqueue are not the same thing.

One other thing, should there be a !=EOF in the while loop.

I have tried to write the code corresponding to your psuedocode but not exactly spot on.  The while loop, how is that written then?  When a job is running it should decrement and display a message "Time remaining"  This is why i had that additional for loop.  

queue = (QUEUE *)malloc(sizeof(QUEUE));
jobs = (QUEUE_NODE *)malloc(sizeof(QUEUE_NODE));


j = 0;

while(fscanf(fp, "%s %d %d %d", jobs->process, &jobs->size, &jobs->arrival_time,
     &jobs->cpu) != EOF)
{


for(index; index <= jobs->arrival_time; index++)
{

     printf("Time is %d \n", index);

     if(index == jobs->arrival_time)
     {
/* enqueue the job when the arrival_time is equal to the timer (index) */
          printf("%s has arrived in the ready queue at time = %d \n", jobs->process,
               jobs->arrival_time);
          enqueue(queue, jobs);
/* how exactly is the job read in?? */
if(index == jobs->cpu)
{
jobs->cpu = 0; /* free the cpu */

   }

if((jobs->cpu == 0) && (queue->front != NULL)
{
/* process the next job..dequeue the previous job */
}
}
else
{
printf("no jobs to enqueue \n");
}
index = index + 1;
0
 

Author Comment

by:gbilios
Comment Utility
I've got the right idea about queue datastructures but cant do it in code properly.

This is what the program should be when the program is run

time is now = 0
  no jobs to enqueue
time is now = 1
 no jobs to enqueue
 time is now = 2
j1 has arrived in the ready queue at time = 2
  j1 has the cpu for 3 units
        Time remaining 3, Time is now 2    press <Enter>
        Time remaining 2, Time is now 3    press <Enter>
j2 has arrived in the ready queue at time = 3
       Time remaining 1, Time is now 4    press <Enter>
       j1 has finished
press <ENTER> to continue>
Time is now = 6
  j2 has the cpu for 5 units

.........................
0
 
LVL 16

Accepted Solution

by:
imladris earned 250 total points
Comment Utility
There are of course, as usual, a dozen different ways to do things. The *simplest* structure for such a simulation is one where each iteration of the main loop corresponds to one "tick" of the clock.
In your code, you are trying to do a bunch of things when the job arrives. While it is undoubtedly possible to write it in such a fashion, it will be much more complicated. The psuedo code I presented does everything that is needed for each clock tick:

check if a job has arrived and, if so, enqueue it.
Check if the current job has completed and, if so, free it.
Check if a job new job can be run and, if so, run it.

This structure will remove manifold complications. In your code, for instance, the check for job completion ("if(index==jobs->cpu") is *still* only happening when a new job arrives. You really need to rearrange the loop so that each of the critical events is checked and handled for *every* clock tick.

As for specific questions then:

When you free the cpu, do you enqueue the job?
Not necessarily no. They are unreleated events, and should be treated that way. At any clock tick the cpu may become free; and at any clock tick a job may arrive. The two events are not tied in any way, so they should not be dependant on one another. The cpu is freed when a job is done; and a job is enqueued when it arrives.

Is there a differece because the cpu and the readyqueue are not the same thing?
Exactly. The ready queue is represented by the queue in your program. The cpu is not yet represented in your program. You need to declare a node, as I indicated, that represents the cpu. It needs to indicate whether it is busy with a job or not, and if it is busy, when it will be done.

One other thing, should there be a !=EOF in the while loop.
You certainly should check for EOF. Although, in the structure I'm recommending, it would not be in the while. It would be in the clause that enqueues the job.

The while loop, how is that written then?  
The top of the loop needs to keep going as long as there is something to do. So it would be something like:
while(index<cpujobs->cpu || queue->front!=NULL || jobs!=NULL)

When a job is running it should decrement and display a message "Time remaining"  This is why i had that additional for loop.
There is no need to have a whole loop for that alone. It can be accomplished in the pseudo code I proposed by a print statement when the cpu is occupied. This could be done with another clause at the end of the loop:

if cpu is busy
      print time remaining
0
 

Author Comment

by:gbilios
Comment Utility
One of the questions i was asking when a job is ready to be processed, it is dequeued, right? cos it moves from the readyqueue to the cpu for processing.  
If you say that i should test for EOF in the enqueue clause, i assume you're refering to the if statement that says if index is == arrival tme? or the enqueue algorithm?
Your psuedocode

initialize cpujob to free
initialize index
read next job
while cpu occupied or job queue not empty or jobs left
   if index==job arrival time
      queue job
      read next job
   if index==cpu completion time
      print finish job
      free cpu
   if cpu is free and job in queue
      start next job
   increment index
everything is done in the main loop.

int index;
QUEUE_NODE *cpujob;
QUEUE_NODE *jobs;
QUEUE *queue;

/* additional node */
jobs = (QUEUE_NODE *) malloc(sizeof(QUEUE_NODE));
queue = (QUEUE *) malloc(sizeof(QUEUE));
cpujob = (QUEUE_NODE *) malloc(sizeof(QUEUE_NODE));

index = 0; /* initialise index */
cpujobs = 0;
fscanf(fp, "%s %d %d %d", jobs->process, &jobs->size, &jobs->arrival_time, &jobs->cpu);
while(index<cpujobs->cpu || queue->front!=NULL || jobs!=NULL)
{

if(index == jobs->arrival_time)
{
   printf("%s has arrived in the ready queue at time = %d \n", jobs->process, jobs->arrival_time);
enqueue(queue, jobs);
/* i assume you fscanf to read the next job */
}
/* if the clock tick is 3 (time) and the cpu time is for 4 units, how will they equal to eachother? */
if(index == cpujobs->cpu)
{
  printf("%s has finished \n", jobs->process);
  cpujobs->cpu = 0; /* reset it */
}

if((jobs->cpu == 0) && (queue->front != NULL))
{
    /* starting the next job */
}

index = index + 1;
} /* end while */

I 'm not sure on check for the EOF and starting the next job.
the cpu time can be accessed with jobs->cpu
if(jobs != EOF) //wrong
0
 
LVL 16

Expert Comment

by:imladris
Comment Utility
One of the questions i was asking when a job is ready to be processed, it is dequeued, right? cos it moves from the readyqueue to the cpu for processing.  

Yes, quite right.

If you say that i should test for EOF in the enqueue clause, i assume you're refering to the if statement that says if index is == arrival tme? or the enqueue algorithm?
Yes, no. It would be something like:

if(jobs!=NULL && index == jobs->arrival_time)
{
   printf("%s has arrived in the ready queue at time = %d \n", jobs->process, jobs->arrival_time);
enqueue(queue, jobs);
/* get the next job in the file */
if(fscanf(fp, "%s %d %d %d", jobs->process, &jobs->size, &jobs->arrival_time, &jobs->cpu)==EOF)jobs=NULL;
}

Even though you may have processed the last job in the file, there will be iterations left in which the job must be dequeued and processed. Thus, if no jobs are left, set jobs to NULL, and then you must, of course, check if it is NULL first when checking if the next job has arrived or not.

I 'm not sure on check for the EOF and starting the next job.
The next job can be started when the cpu is free. So that clause would be something like:

if((cpujobs->cpu == 0) && (queue->front != NULL))
{   // dequeue job
    // set cpu to process job
}

the cpu time can be accessed with jobs->cpu
I assume the cpu field in the jobs entry from the queue indicates how much cpu time will be needed. This needs to be manipulated appropriately when it goes to cpujobs so that it indicates at what "time" the job will be finished.

Note also that since cpujobs is a pointer, this line:

cpujobs = 0;

should be:

cpujobs=NULL;
0
 

Author Comment

by:gbilios
Comment Utility
Lets confirm all of this

say, at time = 2 , j1 arrives and is enqueued.
Its the first job in the queue and its starts processing
whilst its processing and time = 3, j2 arrives in the readyqueue
when j1 has finished its processing, j2 will yield the processor (cpu) for n units

When a job is at the head of the queue, you know that it can start.  I will have to dequeue it and  then move it to then process it.  The next job in the queue is waiting for service.
This program i am developing is a non preemptive scheduling mechanism, so no blocked queues here.  

I think there should a way to decrement the cpu time so that the user can press the enter key to determine whats happening.  I put the for loop to count backwards.  The program also simulates variable fixed multiprogramming partitions.  I added an array of say, 200MG in size, so the first job goes in partitions[0] = jobs->size; /* which is 78Meg */


cpujobs = 0; /* zero is a null value */

0
 
LVL 16

Expert Comment

by:imladris
Comment Utility
Lets confirm all of this

Yes, I agree. That is precisely what I am aiming at.

I think there should a way to decrement the cpu time so that the user can press the enter key to determine whats happening.

Yes, and no. The user should certainly be able to see what is happening. But the phrase "a way to decrement the cpu time" seems to imply the separate loop you had in your original code. Such a loop that is "decrementing cpu time" winds up missing the fact that a new job arrives. Precisely the original problem. The loop I have described manages all the events in a straightforward way.
Now you *can*, of course, let the user know what is happening. It just isn't done by "decrementing the cpu*. The way it would be done in the loop I proposed is (as I indicated in the 9:39 message) to add a clause that shows the cpu as busy. So the end of the loop would become something like:

if((cpujobs->cpu == 0) && (queue->front != NULL))
{   //dequeue job
    // set cpu to process job
}
if(cpujobs->cpu!=0)
    printf("Time remaining: %d\n,cpujobs->cpu-index);

dummy=getchar();

index = index + 1;
} /* end while */

Note that cpujobs->cpu is being checked against 0 in the first if there (not jobs). The time remaining is calculated. Note also that getchar is done at the bottom of the loop, not in any of the clauses. The loop is run tick by tick as the user hits the keyboard.
0
 
LVL 16

Expert Comment

by:imladris
Comment Utility
P.S.

cpujobs = 0; /* zero is a null value */

Yes, that is true, more or less, on most systems. Assuming the compiler accepts it, I have no doubt it will work. Nevertheless, it is much better to treat cpujobs as a pointer, rather than as an integer, because it is one. Over 80% of software effort is spent maintaining existing code. Adhering to simple good style has value way beyond its cost in reducing confusion and inadvertent maintenance errors.
0
 

Author Comment

by:gbilios
Comment Utility
if((cpujobs->cpu == 0) && (queue->front != NULL))
{   //dequeue job
    // set cpu to process job
}
This if statement checks if there are no jobs running but there is a job in the job.  queue->front is the next job right after the previous one is dequeued.  Is is where you dequeue the job and process the new job.  

printf("%s has the cpu for %d units \n", jobs->process, jobs->cpu);
printf("press <Enter> \n"); dummy = getchar(); /* cycle the time remaining for the cpu */
jobs->cpu = jobs->->cpu - 1; /* decrementing */

i am about to test this code.  i compile and run my code using the Sun C/C++ compiler.
gcc -ansi -Wall -o test test.c
Okay, you're spot on with the NULL vs 0 in the initialisation
cpujobs = NULL;

0
What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

 

Author Comment

by:gbilios
Comment Utility
Sorry, made a mistake in that last post.
0
 

Author Comment

by:gbilios
Comment Utility
I get segmentation fault..
initialising the cpujobs pointer to NULL causes the program to crash (Segmentation fault).  
I also get segmentation with the dequeue function
the process is declared as void so calling it i used dequeue(queue, (void *)&jobs);
The dequeue algorithm returns a boolean success flag , so correct me if i am wrong i will use an if statement to call the dequeue
if(dequeue(queue, (void *) &jobs) )
dequeue(queue, (void *) &jobs) ;

int main()
{
int partitions[SIZE];
int index;
FILE *fp;
QUEUE *queue;
QUEUE_NODE *jobs;
QUEUE_NODE *cpujobs;
char dummy;

/* Initialise the queue */
createQueue();

if ((fp = fopen("test.dat","r")) == NULL)
{
      printf("Cannot open file for read.\n");
      exit(1);
}
printf("Jobs arrive for scheduling>\n");

queue = (QUEUE *)malloc(sizeof(QUEUE));
jobs = (QUEUE_NODE *)malloc(sizeof(QUEUE_NODE));
cpujobs = (QUEUE_NODE *)malloc(sizeof(QUEUE_NODE));

index = 0; /* initialise index */
cpujobs = NULL;
fscanf(fp, "%s %d %d %d", jobs->process, &jobs->size, &jobs->arrival_time, &jobs->cpu);
while(index<cpujobs->cpu || queue->front!=NULL || jobs!=NULL)
{

if(jobs!=NULL && index == jobs->arrival_time)
{
   printf("%s has arrived in the ready queue at time = %d \n", jobs->process, jobs->arrival_time);
enqueue(queue, jobs);
/* get the next job in the file */
if(fscanf(fp, "%s %d %d %d", jobs->process, &jobs->size, &jobs->arrival_time, &jobs->cpu)==EOF)
      jobs = NULL;
}

if((cpujobs->cpu == 0) && (queue->front != NULL))
{    dequeue(queue, (void *)&jobs);
    printf("%s has the cpu for %d units ", jobs->process, jobs->cpu);
}

if(cpujobs->cpu!=0){
    printf("Time remaining: %d\n",cpujobs->cpu-index);
}

printf("press <ENTER> to continue> \n");
dummy = getchar();


index = index + 1;
} /* end while */

fclose(fp);
return(0);
}
0
 

Author Comment

by:gbilios
Comment Utility
The following statements enqueue a job and then reads in the next job before the first job can do anything.  

The line createQueue(); i think should be queue = createQueue();  i cant set cpujobs to NULL because it causes the program to crash.  cpujobs->cpu = 0; /* free */
I am so confused here and really want to get this application going.
I think the psuedocode should first be if the cpu is idle and if its the first and only job to be queued, process it.  if the clock tick is equal to another job's arrival time, enqueue it.  when a job is finished its processing, set the cpu time back to idle and process the next available job.  The program displays incorrect timer results.  

if(jobs!=NULL && index == jobs->arrival_time)
{
   printf("%s has arrived in the ready queue at time = %d \n", (char *)jobs->process, jobs->arrival_time);
      enqueue(queue, jobs);

if(fscanf(fp, "%s %d %d %d", (char *)jobs->process, &jobs->size, &jobs->arrival_time, &jobs->cpu)==EOF)
{
            jobs = NULL;
}

}

if((cpujobs->cpu == 0) && (queue->front != NULL))
{    
printf("%s has the cpu for %d units \n", (char *)jobs->process, jobs->cpu);
      //if(dequeue(queue, (void *) &jobs))

            //dequeue(queue, (void *)&jobs);                 

}

Executing the above statements only produces this output
Time = 0; press enter
Time = 1; press enter
Time = 2
    j1 has arrived in the ready queue at time = 2
  j2 has the cpu for 5 units /* should be j1 has the cpu for 3 units */
0
 
LVL 16

Expert Comment

by:imladris
Comment Utility
Lots of questions overnight. I guess we're in somewhat different timezones. Anyway, here's a bunch of answers.

>This if statement checks if there are no jobs running but there is a job in the job.  queue->front is the next job right after the previous one is dequeued.  Is is where you dequeue the job and process the new job.  

Yes, and maybe. You would dequeue the next job at that comment. You would *commence* processing it by setting the cpujobs node in the relevant fashion. The processing itself is left to occur tick by tick as the loop progresses. The following code:

printf("%s has the cpu for %d units \n", jobs->process, jobs->cpu);
printf("press <Enter> \n"); dummy = getchar(); /* cycle the time remaining for the cpu */
jobs->cpu = jobs->->cpu - 1; /* decrementing */

should be referencing *cpujobs* (the cpu), not jobs (the queue).

>I get segmentation fault..
initialising the cpujobs pointer to NULL causes the program to crash (Segmentation fault).  

Ah, yes. I was watching the syntax, but not the semantics. The cpujobs variable has been initialized (with the malloc assignment) to point to a node. Subsequenty setting it to NULL will, of course, lose that memory. As I see in a subsequent post "cpujobs->cpu=0" should suffice.

>The dequeue algorithm returns a boolean success flag , so correct me if i am wrong i will use an if statement to call the dequeue
if(dequeue(queue, (void *) &jobs) )
dequeue(queue, (void *) &jobs) ;

Yes, dequeue returns an indication as to whether there was something to dequeue or not., which you can check with an if statement. However, not using the if statement is also reasonable. In your code the dequeue occurs when you are assigning a job to the cpu, and the queue has already been ascertained to contain something; so there is no real need to check. Either way, this would not be related to the seg fault. I suspect that is caused by the reference to process[0]. As I indicated in one of my original posts, there is something wrong with the way process is being treated.

>The line createQueue(); i think should be queue = createQueue();  

Yes, I agree.

>i cant set cpujobs to NULL because it causes the program to crash.  cpujobs->cpu = 0; /* free */

Yes, that should work.

>I am so confused here and really want to get this application going.

Programming can be very frustrating. Getting it going depends on a mass of details all of which are somewhat unnatural, and all of which must be precisely correct. The way through it is to focus on one detail at a time.

>The program displays incorrect timer results.  

More detail issues here. There are a number of different ways arrival time, processor time, time needed, etc. can be represented. Think (step by step) about what is read from the file, how the variables are set, and how that causes your output. To help with details I will need to know the details of your input. A start would be the first 5 or so lines of test.dat.

0
 

Author Comment

by:gbilios
Comment Utility
the program is actual a variable partition memory management simulation program.  I used a previous job scheduling program for this.  The cpu as in jobs->cpu is represented as the execution time a job will execute in memory.  When a job is enqueued it is placed in a memory slot, say for example 56Meg.  Then that job will take up 56MEg of the memory space.  I know i didn't mention this earlier in the context of the program but i think i can handle the partitions[200]; //make enough room

partitions[0] = //a job of size 56Meg goes.  whether its Meg, kb or GB doesn't matter.  its  a simulation

int *p;

while there is still mem left in the array, dequeue the job and put it in a partition.
job will run for n units and then it is deallocated.  This leaves hole in the memory as that is usual with variable partition
possibly use memory compaction or coallascing to reorganise the memory. If two holes are adjacent then they can merge to form a larger hole.

j1 67 2 3
j2 50 3 5
j3 78 5 2
j4 54 8 3
j5 56 16 4


j1 (job) 67 (size) 2(arrival time) 3 (execution time)

i use the cpu as the execution time

as stated above, a job can run concurrently when it occupys a partition in memory (Correct me if i am wrong).  I am sorry to change the context here but its not a big change.

now going back to the list of problems:
I modified the line createQueue(); to
    queue = createQueue();
and obviously cpujobs->cpu = 0;

dequeueing -
if(dequeue(queue, (void *)&jobs) )
{
    printf("%s has been dequeued at time = %d \n", (char *)jobs->process, index);
}
                   

the line in the dequeue algorithm *itemPtr = queue->front->process;

When the last job is processed j5 arrives in the readyqueue at time = 16
segmentation fault..


0
 
LVL 16

Expert Comment

by:imladris
Comment Utility
Uummm, so I assume you now have the correct timer results?

As for the last problem:

>When the last job is processed j5 arrives in the readyqueue at time = 16
segmentation fault..

from that I can't infer much more (with any certainty) than that a segmentation fault occurred *after* j5 arrived at time 16.

What I (and you) need to know, is at precisely what statement did the seg fault occur, and what was the state of various relevant variables at the time. If you have a debugger it should be relatively easy to establish this. If not, you'll have to make do with creative print statements.
0
 
LVL 16

Expert Comment

by:imladris
Comment Utility
Also, the original question looks like it has been answered (When a process is already enqueued and is ready to run, should it dequeue first so that i can run?  Whilst a job is running, my code fails to enqueue jobs. ). The question has now morphed to include a more complicated program (taking memory segments into account), and the task of getting it to run. And we have a lot of rather long postings here.

I recommend that you close and grade this answer, and start a fresh question for the task of debugging the program.
0
 

Author Comment

by:gbilios
Comment Utility
you're right.

the program does enqueue.


When the last job is read in, there are no more jobs to read through and so a null is signified.  The pointers should be deallocated or free back to the system.

Variable partitioning. you would have say 200meg of storage, which is represented as an array - when a job arrives , check for available space and put the job in a partition *not segments*.  remember this is not segmentation mem management.  
In variable partitioning, jobs can run concrrently.  So the cpu time is just the time the job will run for and when it finishes, dequeue it.  ITs a simulation program only.

 I have solved most of my problems and thanks for your help.
0
 

Author Comment

by:gbilios
Comment Utility
I have to add one last thing.  The logic cant be right here

if(jobs!=NULL && index == jobs->arrival_time)
{
   printf("%s has arrived in the ready queue at time = %d \n", (char *)jobs->process, jobs->arrival_time);
      enqueue(queue, jobs);

if(fscanf(fp, "%s%d%d%d", (char *)jobs->process, &jobs->size, &jobs->arrival_time, &jobs->cpu)==EOF)      
 jobs = 0;

}
This if statement checks for EOF and if so, set jobs to NULL. When the last job goes in, it will want to process at some time, but with jobs set to null, it cant do anything 'cos the data is invalid.  This explains the segmentation fault at the end of the program
If you use cpujobs to test for availability, this if statement is never reached and the program goes on and on.  In fact initialising cpujobs->cpu = 0 and checking for completion if index == cpujobs->cpu will be executed at the start of the program when index == 0.

if(fscanf(fp, "%s%d%d%d", (char *)jobs->process, &jobs->size, &jobs->arrival_time, &jobs->cpu)==EOF)      
 jobs = NULL;
0
 
LVL 16

Expert Comment

by:imladris
Comment Utility
HMmm.

Yes, you're partly right. Documentation (and experience) indicate that the fscanf call should not come up with EOF when it reads the last job. It should return, according to the documentation "the number of fields successfully converted and assigned". So it should be returning 4 for the last job read.
Only when that one "arrives" and is placed in the queue, and the program then attempts to read *past* that, should it come up with EOF, set jobs to NULL and so avoid looking for any more jobs to arrive; which would, conceptually, be correct, since there aren't any.

However it is, of course, true that setting "jobs=NULL" is an obvious memory leak. Not likely to have noticeable consequences in this particular case since it is only a single small buffer. But it is hardly good practice to just "lose" memory allocations like that.

In looking at the code again, it would appear that the seg fault would occur when the the program attempted to dequeue the last job into the memory pointed to by jobs (which was then NULL).
Assuming I am right, and you're code is still structured that way, it would appear there is another, more subtle, problem there. It would occur when a job got queued up, and another was waiting (in the jobs buffer). The job waiting to go into the queue would be overwritten by the one coming out of the queue. This would not be noticed if jobs always immediately went to get processed (which, from your description, may be the case (since jobs can run concurrently)).
The dequeue should probably go to cpujobs, not jobs.

Anyway, I'm glad you're on your way, and thanx for closing the question.
0
 

Author Comment

by:gbilios
Comment Utility
if(fscanf(fp, "%s", (char *)jobs->process) != EOF)
      {      /* keep reading for next job */
            fscanf(fp, "%d%d%d", &jobs->size, &jobs->arrival_time, &jobs->cpu);
      }
      else
      {
            if(emptyQueue(queue))
            {      destroyQueue(queue);
                  break; /*  break out of the while loop to end the program */
            }
      } /* end if */
destroyQueue checks if there are jobs left in the queue.  
i tested this and worked when i placed another job in the test.dat file j6 with arrival time = 24 and exec time = 3

copy the data to the linked list (insert it)
 dequeue the job
while a job is in the linked list
start processing the job in its location in mem
cputime--;

if cputime equal to zero
delete the  job and set the deleted job's location in mem to *free*
this *free* indicates that a new job can can take its place but a new job cannot be inserted into it if the size of *free* is greater than the size of the job.  if free is 56Meg and the job requires 76Meg, can't fit, must be placed somewhere else.

What this means that when a job has been removed, the deleted job's location is set to free but the size of *free* remains the size of that job (hole).  When the linkedlist is full and holes start appearing, insert the jobs in the middle.
i cant say if job is <= available free mem .  should be == 'cos there cant be any internal fragmentation in variable partition
This concludes my very lengthy posts.

If all else fails i can do fixed partition - just use an array of fixed partitions (the sizes are hard coded). a job that is 100Meg in size can only be inserted in memory with a partition of exact same size.

0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.

728 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now