Solved

LinkedList Queue

Posted on 2004-09-08
60
1,644 Views
Last Modified: 2012-06-27
I am using example code to read in data from a file to a LinkedList Queue, which simulates jobs going into the ready queue and execute for N units in the cpu.  I am having compile errors with this lif statement.
if (!(newPtr = (QUEUE_NODE *)malloc(sizeof(QUEUE_NODE))))
            return 0;

The error says LValue required in enqueue function

another thing that i am not sure of is do i need to create a pointer for each field (QUEUE_NODE struct) in the enqueu function

QUEUE_NODE *newPtr, *newPtr1, *newPtr2;

There are three fields in the files j1, 3, 4. j1 is the job number, 3 is the arrival time and 4 is the amount of time j1 can execute for.



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

#define N 2
typedef struct node
{
      struct node *process[N];
      struct node *arrival_time;
      struct node *cpu;
      struct node *next;
} QUEUE_NODE;

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

/* Prototype declarations */

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

int dequeue (QUEUE *queue, void **itemPtr);
int enqueue (QUEUE *queue, void *itemPtr);
int queueFront (QUEUE *queue, void **itemPtr);
int queueRear (QUEUE *queue, void **itemPtr);
int queueCount (QUEUE *queue);

int emptyQueue (QUEUE *queue);
int fullQueue (QUEUE *queue);

QUEUE *createQueue (void)
{
      QUEUE *queue;

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

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

return queue;

} /* createQueue() */


int enqueue (QUEUE *queue, void *itemPtr)
{
      QUEUE_NODE *newPtr;

      if (!(newPtr = (QUEUE_NODE *)malloc(sizeof(QUEUE_NODE))))
            return 0;
      
      newPtr->process = itemPtr;
      newPtr->arrival_time = itemPtr;
      newPtr->cpu = itemPtr;
      newPtr->next = NULL;

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


int main()
{
int CPU;

struct node *jobs;
File *fp;
.
.
/* may need to create variables for the delimiter  '%c'*/
while(fscanf(stdin, "%s%d"%d", jobs->process, &jobs->arrival_time, &jobs->cpu ) != EOF)
{.....}

fp.close();
return(0);

} /* end main */
0
Comment
Question by:gbilios
  • 33
  • 26
60 Comments
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12005267
> if (!(newPtr = (QUEUE_NODE *)malloc(sizeof(QUEUE_NODE))))
First of all, don't cast the result of malloc, that should never be needed, this is better:
> if (!(newPtr = malloc(sizeof(QUEUE_NODE))))

Second, why are all three poibters in that QUEUE_NODE pointing to the same thing (itemPtr) ?  THat seems senseless, maybe you wanted to do something different ?
And in the same line of thought::
> newPtr->process = itemPtr;
Isn't QUEUE.process defined as an array (of size N) ?  Then the previous line will give an error.
0
 

Author Comment

by:gbilios
ID: 12005391
i am modifying example code.  i want it to read a file (jobs.dat)
// jobs.dat file
j1 2 4
j2 3 2
j3 4 3

Not sure if the code in the enqueue function is correct.  i am lost here. you mentioned why the three things are pointed to the same thing (itmPtr) .  I am using example code, i don't know how to correct it.  As i mentioned, i have to enqueue data from a file.  Its a simulation of jobs going into the ready queue and execute for n units in the cpu.  

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

#define N 2

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

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

/* Prototype declarations */

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

int dequeue (QUEUE *queue, void **itemPtr);
int enqueue (QUEUE *queue, void *itemPtr);
int queueFront (QUEUE *queue, void **itemPtr);
int queueRear (QUEUE *queue, void **itemPtr);
int queueCount (QUEUE *queue);

int emptyQueue (QUEUE *queue);
int fullQueue (QUEUE *queue);

QUEUE *createQueue (void)
{
      QUEUE *queue;

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

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

return queue;

} /* createQueue() */


int enqueue (QUEUE *queue, void *itemPtr)
{
      QUEUE_NODE *newPtr;

       if (!(newPtr = malloc(sizeof(QUEUE_NODE))))
      
            return 0;
      
      newPtr->process[N] = itemPtr;
      newPtr->arrival_time = itemPtr;
      newPtr->cpu = itemPtr;
      newPtr->next = NULL;

      if (queue->count == 0)
      
            queue->front = newPtr;
      else
            queue->rear->next = newPtr;
            (queue->count)++;
            queue->rear = newPtr;
printf("%s%d%d\n",newPtr->process[N], newPtr->arrival_time, newPtr->cpu);

      return 1;
}


int main()
{

int CPU;
int TIME;
FILE *fp;
char delimeter1;
char delimeter2;
struct QUEUE *queue;
struct node *jobs;
createQueue();

if ((fp = fopen("jobs.dat","r")) == NULL)
{
      printf("Cannot open file.\n");
      exit(1);
}

//while(fscanf(fp, "%s%d%d", jobs->process[N],&jobs->arrival_time, &jobs->cpu) !=
//EOF){
//enqueue(&queue,&jobs);
//}

fclose(fp);
return(0);

} /* end main */



0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12005813
This is even worse, what do you suppose this statement does:
> newPtr->process[N] = itemPtr;

How much C experience do you have so far ?  It seems like you don't really know what a lot of the statements are doing.

Where do you have the definition of this 'QUEUE_NODE' type from ?  What do each of the members mean ?

First of all, I think you shouldn't have a 'void' pointer as argument to the 'enqueue' function, but a 'QUEUE_NODE' pointer.
Like so: int enqueue (QUEUE *queue, QUEUE_NODE *itemPtr)
0
 

Author Comment

by:gbilios
ID: 12006978
i dont hava alot of experience in programming , especially C programming.  I used the example code and see i could modify it.

process[N] is the placeholder for the job that is read from the jobs.data file
example j1, j3

arrival_time is the placeholder the job arrives, say for example j1 arrives at 3
cpu is a placeholder for how long the job executes for

i understand that the createQueue initialises the queue and enqueue inserts the data to the LinkedListQueue.  I am having problems getting around C so please guide me in the right direction

gbilios
0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12007130
Okay.. I think you first need to know what this code is doing, before you start modifying it.  How about you go over the code statement by statement, and ask yourself what that statement does, and why it's there in the code.  Pick out the statements where you can't answer those questions and post them here.  Sound like a plan ?

I'll start with a few beforehand:

      if (!(newPtr = malloc(sizeof(QUEUE_NODE))))    //  Allocate memory for one node, and let 'newPtr' point to that memory.
          return 0;                                                                     //  If that fails, return 0 to let the caller know something went wrong.
                                                                                              //  newPtr points to a structure, with the -> you get at its members.
     newPtr->process[N] = itemPtr;                                   //  let the Nth entry of the array 'process' point to the same place 'itemPtr' points.
     newPtr->arrival_time = itemPtr;                                //  let the member 'arrival_time' point to the same place 'itemPtr' points'
     newPtr->cpu = itemPtr;                                                //  You get the idea.

What it probably should read like is this:

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

(Later on, you can simplify this with the 'memcpy' function, but lets not do that just yet.)
0
 

Author Comment

by:gbilios
ID: 12007940
Are the following lines correct?

int TIME = 0
FILE *fp;

if(fp=fopen("jobs.dat","r")) == NULL)
{

 printf("Error: Cannot open file for read\n");
}

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

} /* End While */
0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12008556
All but one of those look correct to me.  Here's the one I have problems with:

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

Problem 1:   You need to look at what 'jobs' is defined as (looks like a struct), to see if this is correct.  From this, it looks like 'jobs' pounts to a struct with (at least) three members.  I assume that it's a QUEUE_NODE (which is a 'struct node'), like in your previous code.  Let's copy the definition of that here, shall we ?

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

All the members are of type 'struct node *', which looks suspicious to say the least.  And combined with that 'while', it's quite obvious that this definition is wrong.

Take a look at the following bit of code:

char chars[100];
int an_integer;
int another_integer;

fscanf(fp, "%s %d %d\n", chars, &an_integer, _another_integer);

Now think about the types of those three variables, and compare it to your code.
0
 

Author Comment

by:gbilios
ID: 12012684
you mean

typedef struct node
{
     char process[N];
     int arrival_time;
     int cpu;
     struct node *next;
} QUEUE_NODE;
0
 
LVL 7

Expert Comment

by:aib_42
ID: 12013014
if(fp=fopen("jobs.dat","r")) == NULL)

This is clearly incorrect. Count the number of parantheses.
0
 

Author Comment

by:gbilios
ID: 12013289
i made a mistake..

if ((fp = fopen("jobs.dat", "r")) == NULL)
{
   printf("Cannot open file.\n");
   exit(1);
}





0
 

Author Comment

by:gbilios
ID: 12014025
various text would say that  its not necassary to put the ampersand in the scanf if its a string, yet lecturer says that it must be in there or segmentation fault occurs.

which is correct?

QUEUE_NODE jobs;
while(fscanf(fp, "%s%d%d", &jobs.process[N], &jobs.arrival_time,  &jobs.cpu) != EOF){..}

I changed jobs.process[N] to &jobs.process...probably ran with no segmenation fault but doesn't mean its correct.

0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12014534
The lecturer is wrong.  scanf wants pointers, and a string is already a pointer to char.
But the way you have it it's wrong:
In C, the [] brackets are used to point to a certain member of an array.  For example, process[0] would be the first  member, process[1] would be the second, etc.  So if you do process[N], you're accessing the Nth member of the array 'process'.

0
 

Author Comment

by:gbilios
ID: 12014742
I use the Sun C/C++ Compiler just to mention...  

yes, I noticed that in my debugging.  I made the changes.  
I used a print statement in main to test whether the data was read in successfully and tested it in the enque function as well.  
What is the difference between
   enqueue(queue, jobs); and enqueue(&queue, &jobs);  
All i know is that the ampersand is used to point to a memory address space.

I am developing code to allow the jobs to execute for the cpu one job at a time (Nonpreemptive).  Jobs will leave the cpu when their cpu time expires.  Correct me if i'm wrong, i can use an if statement and say if arrival time for j1 is equal to 2, j1 executes for n units, and leaves the queue when cpu time expires.  
First i'll figure out how to go about this on my own before SOS the forum.  

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

#define N 2

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

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

/* Prototype declarations */

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

int dequeue (QUEUE *queue, void **itemPtr);
int enqueue (QUEUE *queue, QUEUE_NODE *itemPtr);
int queueFront (QUEUE *queue, void **itemPtr);
int queueRear (QUEUE *queue, void **itemPtr);
int queueCount (QUEUE *queue);

int emptyQueue (QUEUE *queue);
int fullQueue (QUEUE *queue);

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;

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

        newPtr->process[0] = itemPtr->process[0];
      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;


/*printf("%s %d %d\n",itemPtr->process, newPtr->arrival_time, newPtr->cpu);
*/
      return 1;
}

int main()
{

int CPU;
int TIME;
FILE *fp;
QUEUE *queue;

createQueue();
QUEUE_NODE *jobs;

if ((fp = fopen("jobs.dat","r")) == NULL)
{
      printf("Cannot open file.\n");
      exit(1);
}

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

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

/* test if the file was read in successfully */
printf("%s %d %d\n",jobs->process, jobs->arrival_time, jobs->cpu);

      enqueue(queue,jobs);
}

/* close the file */
fclose(fp);

return(0);

} /* end main */
0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12014819
The following lines don't look quite right to me:

> while(fscanf(fp, "%s%d%d", &jobs->process,&jobs->arrival_time, &jobs->cpu) != EOF)
Still an ampersand too many there..  What exactly will 'jobs->process' contain ?  A string of two characters ?

> newPtr->process[0] = itemPtr->process[0];
Why only copy the first element ?  'process' contains more than one element, doesn't it ?
0
 

Author Comment

by:gbilios
ID: 12014960
while(fscanf(fp, "%s%d%d", &jobs->process,&jobs->arrival_time, &jobs->cpu) != EOF)

i changed it to jobs->process
i forgot to do this, sorry

newPtr->process[0] = itemPtr->process[0];

i am getting a better understanding and thanks for your consideration and help.  Its alot easier than i thought.  
You will probably disagree from a beginner's perspective using a an if statement like this to place the job in the ready-queue.
TIME is variable to count how many units the job can execute for the CPU example, j1 executes 3 units for the CPU.

if (jobs->process[0] && arrival_time == 2)
{
    enqueue(queue, jobs);
}
TIME = TIME + 1
enqueue function

if queue->count == 0 then add the job to the queue(front).

I assume i wont be needing the else clause 'cos the jobs go in one job at a time.

0
 

Author Comment

by:gbilios
ID: 12014983
sorry let me rephrase the if statement

the if statement just verifies that the job has arrived at a particular time (arrival_time). I haven't mentioned anywhere in the if statement cpu_time.

0
 

Author Comment

by:gbilios
ID: 12015721
Okay, SOS now.

using a for loop like this :
   int ATIME = 1; 'Arrival time
   int CTIME = 1; 'Cpu time
   for (ATIME; TIME < newPtr->arrival_time; ATIME++);
   
         for (CTIME; CTIME < newPtr->cpu; CTIME++);
         
                   printf("%s has arrived at ATIME the ready queue and is executing %d units for the cpu",
                               itemPtr->process, newPtr->cpu
                          enqueue(queue, jobs);

the idea of the double for loop was to indicate when the job has arrived (ATIME) and for how long the the job can execute for (CTIME).  This would happen for each job as it gets in the ready queue.  not sure how to go about the dequeue
i have the dequeue function implemented but i dont think it is efficient to say if CTIME == 3 or CTIME == 4.  
Any suggestions???

gbilios
0
 

Author Comment

by:gbilios
ID: 12015752
made a typo in the first forloop

using a for loop like this :
   int ATIME = 1; 'Arrival time
   int CTIME = 1; 'Cpu time
   for (ATIME; ATIME < newPtr->arrival_time; ATIME++);
   
         for (CTIME; CTIME < newPtr->cpu; CTIME++);
         
                   printf("%s has arrived at ATIME the ready queue and is executing %d units for the cpu",
                               itemPtr->process, newPtr->cpu
                          enqueue(queue, jobs);
0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12016096
I don't understand why you have a for loop that does nothing but increase the ATIME and CTIME vars..  Are you planning on doing something in there later ?  I'm assuming that you want to dequeue jobs when they are ready, and jobs start at ATIME and are executed for CTIME units of time..  I think you want something like a *global* time counter, and do all of your work based on that.  (That is, add jobs to the queue when their arrival_time equals the global time, and then remove them from the queue after cpu_time units have passed.)

By the way, what are you doing this for ?  Programming class ?  Self teaching ?
0
 

Author Comment

by:gbilios
ID: 12016745
i am doing this in programming class , learning Operating Systems

What the for loop is saying for example, ATIME (arrival_time) displays a heading "Arrival Time 2", Job 1 has arrived.
The CTIME (cpu time) was another for loop to control the cpu time so that it would automatically detect how long the job can run for.  Because i dont know how to do it efficiently as you experienced programmers would, i use if statements for each job.  Not the best way but its better staying up all night.  in main i would use the if statement again to say when each job has arrived at a particular time.  Lecturer says that its just a simulation - just has to demonstrate how processes get into the readyqueue.

I did it in the enqueue function

if(itemPtr->process[0] && newPtr->cpu == 3) /* job one */
{
printf('%s is leaving the ready queue", itemPtr->process);
dequeue(queue, &newPtr);

another problem i ran into is the dequeue.  it uses pointer to pointer

int dequeue (QUEUE *queue, QUEUE_NODE **itemPtr)
{
      QUEUE_NODE *deleteLoc;


      if (!queue->count)
            return 0;
//      *itemPtr = queue->front->process[0]; // causing type cast error

/* temporarily changed it to *itemPtr = Null; queue->front->process[0];

      deleteLoc = queue->front;
      if (queue->count == 1)
      
                  queue->rear = queue->front = NULL;
      else
            queue->front = queue->front->next;


            (queue->count)--;
            free (deleteLoc);

            return 1;
}
0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12016884
Do you have experience in other programming languages ?  I think that if you're doing a class on operating systems, the professor assumes that you already know a fair bit about programming, and don't have troubles with linked lists and stuff.

In any case, you can't have separate CTIME and ATIME counters, what you want is one single counter that counts how much time has elapsed since the beginning.  Each time a job is executed, you increase it by the 'cpu_time'.  And when the next jobs' 'arrival_time' is larger than the current time, you have to wait and do nothing for a while.

What exactly is it the professor wants you to do ?
0
 
LVL 2

Accepted Solution

by:
sneeuw_chan earned 250 total points
ID: 12017003
And about the dequeue function, if it only removes the first element of the queue, the 'itemPtr' is useless.
IIRC, the enqueue function puts the new entry at the front of the list, right ?  So it's not a queue, it's a stack.
Maybe you should first create your own linked list, so you understand what's going on.  It's not as hard as ik looks, you know, you just need to 'get' it.
0
 

Author Comment

by:gbilios
ID: 12017252
thanks for your help
i have enough to get my by

very much appreciated

gbilios
0
 

Author Comment

by:gbilios
ID: 12017765
Prefessors can assume we know everything just because we did the basics.   I have more experience in Java.  Doing it in Java beats the purpose of learning C in the first place.  Its just a simulation program (Not using real processes/threads).  He said that even though the calculations may not be correct but demonstrates how processes get into the ready queue is what he's looking for.  

You mean

CTIME = newPtr->cpu;

CTIME = CTIME + 1

this is the output i get

Arrival Time is 2
j1 arrives in the ready queue
j1 executes 2 units for the cpu at time = 2
j1 finishes and dequeues

Arrival Time is 3
j2 arrives in the ready queue
j2 executes 3 units for the cpu at time = 6
j2 finishes and dequeues


data from jobs.dat

j1 2 3
j2 3 2

Here is program that i wrote using a for loop to create 4 child processes.  Nothing wrong with it, but letting you know where my competencies lie.   Fourth chlid terminates due to segmenation fault (Deliberately).

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>

#define children 4

    void showstatus( int stat )
   {
      if (WIFEXITED(stat))
      {
         fprintf(stderr, "\nNormal termination, exit "  
            "status %d\n", WEXITSTATUS(stat) );
      }
      else
         if (WIFSIGNALED(stat))
         {
            fprintf( stderr, "\nAbnoral termination, "  
               "signal number %d\n", WTERMSIG(stat) );
         }
         else
         {
            fprintf(stderr, "\n Unknown "
               "problem detected\n" );
         }
   } /* showstatus() */

    int main()
   {
      pid_t pid;
      int index;
      int status;
      int num;
      char *buf;
           
      for(index = 0; index < children; index++)
      {
         pid = fork();
     
         if(pid < 0)
         {
            perror("fork error");
         }
         else if(pid == 0)
         {
            printf("\nCreated Child n. %d "
               "with pid %d\n", index+1, pid);
               
           /* children do this */
         
            switch(index)
            {
               case 0:                        /* Create first child process */
                  exit(1);                        /* Child process - terminate normally */
                  break;
               case 1:                        /* Create second child process */                                                                                                          
                  abort();                         /* Generate SIGABRT */
                  exit(2);                                                      
                  break;                                                  
               case 2:                         /* Create third child process */
                  num = 20;
                  num = num / (num - 20); /* Generate SIGFPE */
                  exit(3);
                  break;
               case 3:                         /* Create fourth child process */      
                  buf = malloc(1 << 31);
                  fgets(buf, 1024, stdin); /* Generate SIGABRT - Segmentation fault */
                  printf("%s", buf);
                          exit(2);
                  break;
               default:
                  exit(0);      
                       
            } /* end switch */
         }
         else
         {
           /* Parent process -- wait for child */
         
            if(wait(&status) != pid)
            {
               perror("wait error");
            }
            else
            {
               showstatus(status);
            }
         } /* end if */
     
      } /* end for */
   
   } /* end main */
0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12017974
> Arrival Time is 2
> j1 arrives in the ready queue
> j1 executes 2 units for the cpu at time = 2
> j1 finishes and dequeues
>
> Arrival Time is 3
> j2 arrives in the ready queue
> j2 executes 3 units for the cpu at time = 6
> j2 finishes and dequeues
>
>
> data from jobs.dat
>
> j1 2 3
> j2 3 2

Err, shouldn't that be that j1 executes 3 units, and j2 executes 2 units ?
And a few more questions to ponder:
Can processes execute simultaneously, or does each process have to wait until the previous one is finished ?
If they execute simultaneously, shouldn't they have to share the cpu time amongst themselves ?
And if they execute simultaneously, what about that sometimes j1 arrives before j2, but j1 is still busy when j2 is finished ?
0
 

Author Comment

by:gbilios
ID: 12018335
jobs.dat

j1 2 3
j2 3 2

j1 (job) 2 (arrival time) 3 (the time the job executes for the cpu)

I am designing a nonpreemptive scheduling system, i.e., a job cannot preempt a job that is in the active state.
What you're referring to is preemptive scheduling.  

(Nonpremptive) j1 arrives at 2 and executes 3 units for the cpu. when it finishes, j2 which is in the ready queue will move to the active or running state.  These processes will not perform any IO, they're not meant to in my simulation program.

Theres probably a missunderstanding
j1 executes 3 units for the cpu at time = 2
j1 yields the processor straightaway when it arrives but it runs for three units for the cpu.
when j2 arrives at time = 3 it cannot preempt j1 because j1 is executing, so j2 remains in readyqueue.  j2 will have to wait when j1 finishes.  By the time j1 finishes, it'll be time = 6 when j2 yields the processor.  you calculate the arrival time with the  cpu time and one - correct me if i am wrong.  

I am okay with the theory simply 'cos i read more than i code.

thanks for your help.

gbilios
0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12021308
Ah okay.  So you need the linked list to put jobs in a sort of waitinglist.

So, what happens is this:

- At time 2, j1 is started.
- At time 3, j2 is put in the waiting queue.
- At time 5, j1 is finished, and j2 is taken from the queue and started.
- At time 7, j2 is finished.

You can do this two ways:  In the easy way, you just do a for-loop that increments a 'time' variable by one, and then checks if a new job has arrived, or if the current job has finished running.
The harder way would be to check which of the two (new job arriving, or current job finishing) is going to happen first and then jumping to that time.
But in both cases you have one global time variable, which is counting upwards in the main loop.

By the way, if you use a linked list as a queue, you want to be adding jobs at one end, and removing them from the other end.
The best way is probably to be adding them at the rear, and removing them from the front.
That is: your enqueue function should be working with the queue->rear pointer, setting queue->rear->next to the new item, and then setting queue->rear to that same new item.
0
 

Author Comment

by:gbilios
ID: 12024357
i managed that today.

this is the output of the first two processes.

j1 arrves at ARRIVAL TIME = 2 and is in the read queue
j1 executes 3 units for the cpu at time = 2
j1 finishes and dequeues

j2 arrves at ARRIVAL TIME = 3 and is in the read queue
j2 executes 2 units for the cpu at time = 6
j2 finishes and dequeues

i used a for loop and a timer variable you suggested

0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12024413
Okay.  But isn't j2 supposed to arrive before j1 finishes and dequeues ?
And if I got it correctly, j2 should be executing at time = 5 already, shouldn't it ?

Does it also work correctly with a larger job list file like this:

j1 2 5
j2 3 2
j3 5 3
0
 

Author Comment

by:gbilios
ID: 12024560
j1 arrives in the ready queue and automatically executes for the cpu, simply because its the first job in the list and the cpu is idle.  j1 executes for the cpu for 3 units of time (seconds).
While j1 is running, j2 arrives at the ready queue at time = 3 but cannot yield the processor while j1 is running, then j2 must remain in the ready queue.  By the time j1 finishes execution, j2 will move from the ready queue and execute for the cpu (Active).  jobs can only do this one job at a time. This is one strategy of nonpreemptive scheduling.
j2 never arrives before j1.  There is no blocking in my program.

you can have jobs with larger cpu time

gbilios
0
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12024675
Yeah, I got all that already.
What I meant was that your program never actually seems to use the linked list structure, because it only looks at the next job to arrive when the current one has finished.  How about you test with a larger file so that multiple jobs arrive and have to wait in a queue ?

Take the following jobs.dat file for example:

j1 2 3
j2 3 5
j3 5 2
j4 8 3
j5 16 4

How would you go about letting the program print the following (in that order):

j1 arrves at ARRIVAL TIME = 2 and is in the read queue
j1 executes 3 units for the cpu at time = 2
j2 arrves at ARRIVAL TIME = 3 and is in the read queue
j1 finishes and dequeues at time = 5
j2 executes 5 units for the cpu at time = 5
j3 arrives at ARRIVAL TIME = 5 and is in the read queue
j4 arrives at ARRIVAL TIME = 8 and is in the read queue
j2 finishes and dequeues at time = 10
j3 executes 2 units at time = 10
j3 finishes and dequeues at time = 12
j4 executes 3 units at time = 12
j4 finishes and dequeues at time = 15
j5 arrives at ARRIVAL TIME = 16
j5 executes 4 units at time = 16
j5 finishes and dequeues at time = 20
0
 

Author Comment

by:gbilios
ID: 12024871
the output is the same except that j2 executes at time = 6 , not time = 5. j1 dequeues at time = 5
incase i am wrong i can change the newATIME variable.

i compiled and ran it and got the same results as your output

you will obviously disagree with the way i did :

newATIME = ATIME + CTIME;
for loop;
if (itemPtr->process[0] && ATIME == newPtr->arrival_time){

.. .
}
if (CTIME == newPtr->cpu){
....
}
0
 

Author Comment

by:gbilios
ID: 12024875
are you from aust
if you are you can email me
gbilios@iprimus.com.au and arrange a time to discuss it further
0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12024917
Nope, I'm Dutch, so I don't think our waking times overlap much...
In any case, you're welcome to keep this discussion going here.  I'd be interested to see what code you have at the moment, and I'll be happy to comment on it if you want.
0
 

Author Comment

by:gbilios
ID: 12025220
#include <stdio.h>
#include <stdlib.h>

#define N 2

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

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

/* Prototype declarations */

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

int dequeue (QUEUE *queue, QUEUE_NODE **itemPtr);
int enqueue (QUEUE *queue, QUEUE_NODE *itemPtr);

int ATIME = 1;
int CTIME = 1;
int newATIME = 1;

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;

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

      newPtr->process[0] = itemPtr->process[0];
      newPtr->arrival_time = itemPtr->arrival_time;
      newPtr->cpu = itemPtr->cpu;
      newPtr->next = NULL;
int time = 0;
      if (queue->count == 0)
      {
         
      for (ATIME; ATIME < itemPtr->arrival_time; ATIME++);
            /* Job has arrived */
            printf("\n");

            CTIME = newPtr->cpu;
            
            newATIME = CTIME + ATIME;  


                  if(newPtr->cpu == CTIME)
                  {            
printf("%s arrives at ARRIVAL TIME = %d and is now in the ready-queue\n"
                  ,itemPtr->process, newPtr->arrival_time);
                        printf("%s executes %d units for the cpu at time = %d\n",
                              itemPtr->process, CTIME, ATIME);      
      
                        printf("%s has finished executing for the cpu and dequeues\n\n"
                              ,itemPtr->process);
                              dequeue(queue, &newPtr);
                        ATIME = newATIME;

                   }
 
            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 = NULL; queue->front->process[0];
      deleteLoc = queue->front;
      if (queue->count == 1)
                  queue->rear = queue->front = NULL;
      else
            queue->front = queue->front->next;
            (queue->count)--;
            free (deleteLoc);

            return 1;
}

int main()
{

FILE *fp;
QUEUE *queue;
QUEUE_NODE *jobs;

/* Initialise the queue */
createQueue();

if ((fp = fopen("jobs.dat","r")) == NULL)
{
      printf("Cannot open file.\n");
      exit(1);
}

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

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

enqueue(queue, jobs);

} /* end while */

/* memory deallocation */
//free(queue);
//free(jobs);

/* close the file */
fclose(fp);

return(0);

} /* end main */
0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12025335
Okay..  It looks like you're dequeueing each item inside the enqueue function...
I don't think that's quite how you want it, because then a new job can't arrive until the previous job is finished, can it ?  I don't think they way you have it, there won't be a job in the queue because you run it and then dequeue it immediately.

I'd say you need a main loop that looks more like this:

Start with ATIME = 1.
- Check to see if a new job arrived (with arrival_time == ATIME)
   If so, put it at the rear of the queue
- If there is a running job, check if it's finished.
  If so dequeue it, and start the next job in the queue (if there is any)
- In crease ATIME by 1 and repeat until there are no jobs waiting.

So the work is done in the main loop, and the enqueue function only puts jobs in the queue.
0
 

Author Comment

by:gbilios
ID: 12025422
you mean one big loop in the enqueue function?

i was using a for loop.  the way you put it, i assume you mean a do while?


0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12025446
No.  I don't mean a loop in the enqueue function.  The enqueue function should only enqueue jobs, not do lots of other things.
The loop should be in main(), IMO, and use the enqueue and dequeue functions for enqueueing and dequeueing *only*.

And I don't care how you do loops, a do while, a for loop, or whatever is technically the same thing, only different in some small details.
0
 

Author Comment

by:gbilios
ID: 12025536
i have already submitted my work so to me its just finding where i went wrong.

you say that ATIME should start with one in the main loop and then insert the job at the rear of the queue.  The enqueue already does that when a job is already in there.
0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12025576
Yes, I know.  But there will never *be* a job in the queue the way you did it.  The only place a job gets dequeued is in the enqueue function, and there it will always be dequeued.  So, effectively, after the enqueue function is finished, the queue will always be empty.
What I'm saying is that the enqueue function should not be *running* the job.  (Well, simulating that it's running...)
0
 

Author Comment

by:gbilios
ID: 12025691
What does the code to add the job at the rear?.  technically it goes in the front as the first job and subsequent insert at the rear of the queue, right?

ATIME = 1;
while(fscanf(fp, "%s%d%d", jobs->process, &jobs->arrival_time,
      &jobs->cpu) != EOF)
{
      if(itemPtr->process[0] && ATIME == jobsr->arrival_time)
                  {            
printf("%s arrives at ARRIVAL TIME = %d and is now in the ready-queue\n"
                  ,itemPtr->process, jobs->arrival_time);
                        printf("%s has finished executing for the cpu and dequeues\n\n"
                              ,jobs->process);
                              enqueue(queue, jobs);//dequeue(queue, &newPtr);
                        
                   }

ATIME = ATIME + 1;

} /* end while */

fclose(fp);
0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12025846
Well, if the queue is empty, then the front and the rear are the same, right ?
In any case, maybe you want an extra variable that tells when the current job is finished.

Something like this for example:

CTIME = 0;  /* CTIME is the time the current job will end */
ATIME = 1;
while(fscanf(fp, "%s%d%d", jobs->process, &jobs->arrival_time,
     &jobs->cpu) != EOF)
{
     if(jobs->process[0] && ATIME == jobsr->arrival_time)
               {          
printf("%s arrives at ARRIVAL TIME = %d and is now in the ready-queue\n"
               ,jobs->process, jobs->arrival_time);
/* The process is not going to finish immediately, is it ? So no dequeueing here */
//                    printf("%s has finished executing for the cpu and dequeues\n\n"
//                         ,jobs->process);
                         enqueue(queue, jobs);//dequeue(queue, &newPtr);
                   
                }
/* Here, you want to check if the current process has finished yet, like so: */
      if (CTIME == ATIME) {
          /* Dequeue the current job: */
          ...
          CTIME = 0;  /* Indicate that there is no job running */
      }
/* Now, if there is no job running (CTIME == 0) but there is a job in the queue (queue->head != NULL), you start running the job at the head of the queue */
      if ((CTIME == 0) && (queue->head != NULL)) {
                 /* Set CTIME to the time that this job will end */
                 ...
      }

ATIME = ATIME + 1;

} /* end while */
0
 

Author Comment

by:gbilios
ID: 12026114
i dont get any output from the program
if ((CTIME == 0) && (queue->head != NULL)) {

should be

if ((CTIME == 0) && (queue->front != NULL)) {

there is no head declared anywhere

 if(itemPtr->process[0] && ATIME == jobsr->arrival_time)

is there anything wrong with the above if statement?

added a line just below the while loop  printf("TIME IS %d", ATIME);
i get output from this line but nothing else





0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12026232
Yeah, sorry, I got mixed up with head/tail and front/rear there..

And in that if statement, somehow an extra 'r' got added.  'jobsr' should be 'jobs'.

I wrote it pretty hastily, just to get the idea across, I didn't mean for you to just copy it like that..

Oh, and one thing I forgot, you don't want to be doing that 'fscanf' in every cycle of the loop, but only when you actually used the previous 'job' that it scanned.

Something like: "while (jobs || (fscanf( ... ) != EOF)" and then set 'jobs' to NULL after you enqueue it.
0
 

Author Comment

by:gbilios
ID: 12026317
that still didn't do anything.

the cursor sits ideling.

I added a for loop just below the modified while loop

for (ATIME; ATIME < jobs->arrival_time; ATIME++);

i know you said that i doesn't do anything but when i compiled it and ran it, i got the output

gbilios
0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12026454
Yes, but if you do it like that, then won't you sometimes skip past the current job's finishing time ?
In any case, that for loop is basically the same as doing 'ATIME = jobs->arrival_time;'

I think if you change the while loop like this:

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

Then it should work like it's supposed to.
0
 

Author Comment

by:gbilios
ID: 12026494
fair enough.

can you explain why you suggested modifying the while loop like this
while(jobs || (fscanf(fp, "%s%d%d", jobs->process, &jobs->arrival_time, &jobs->cpu) != EOF))


now that you have re-modified the while loop, do i still set jobs to NULL after i enqueue.

gbilios
0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12026528
Because I stupidly forgot that you could already see if a job was running from CTIME. ^^;
0
 

Author Comment

by:gbilios
ID: 12026630
tried that, still no ouptut
0
 

Author Comment

by:gbilios
ID: 12027066
i re-modified the while loop: heres the code below incase i have missed anything.

int main()
{
int ATIME;
int CTIME;
int newATIME;

FILE *fp;
QUEUE *queue;
QUEUE_NODE *jobs;

/* Initialise the queue */
createQueue();

if ((fp = fopen("jobs.dat","r")) == NULL)
{
      printf("Cannot open file.\n");
      exit(1);
}

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



//CTIME = ATIME;  /* CTIME is the time the current job will end */

ATIME = 1;
CTIME = ATIME;
while((CTIME != 0) || fscanf(fp, "%s%d%d", jobs->process, &jobs->arrival_time,
     &jobs->cpu) != EOF)
{

     if(jobs->process[0] && ATIME == jobs->arrival_time)
               {          
printf("%s arrives in the ready-queue\n"
               ,jobs->process);
/* The process is not going to finish immediately, is it ? So no dequeueing here */
//                    printf("%s has finished executing for the cpu and dequeues\n\n"
//                         ,jobs->process);
                         enqueue(queue, jobs);
            jobs = NULL;    
                }
/* Here, you want to check if the current process has finished yet, like so: */
      if (CTIME == ATIME) {
          /* Dequeue the current job: */
         
          CTIME = 0;  /* Indicate that there is no job running */
dequeue(queue, &jobs);
 
     }
/* Now, if there is no job running (CTIME == 0) but there is a job in the queue (queue->head != NULL), you start
running the job at the head of the queue */
      if ((CTIME == 0) && (queue->front != NULL)) {
                 /* Set CTIME to the time that this job will end */
                CTIME = jobs->cpu;
     
}

ATIME = ATIME + 1;

} /* end while */
fclose(fp);

return(0);

} /* end main */
0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12027075
Maybe there's a mistake somewhere.
Try to read through the loop, seeing what it does step by step, and try to understand what it's doing.
If you know what it's supposed to do, you should also be able to easily spot what's going wrong.
0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12027212
Aha, You should initialize CTIME = 0, not to = ATIME.

And when starting the job, don't set CTIME to cpu_time, set it to the time the job will end running.

Oh, and I realised that you *do* need to check against 'jobs != NULL' in the 'while' loop.  (And of course initialize it to NULL.)  You only want to get a new job when the last job has been enqueued (i.e. has actually arrived.  The 'jobs' variable holds the next job, that hasn't 'arrived' yet, that is, whose arrival time is larger than the current time.)
0
 

Author Comment

by:gbilios
ID: 12027557
i added this to test , CTIME = ATIME. forgot to remove.  

okay, if (jobs != NULL){.....}

you mention initialising it to NULL after it enqueues, right?

0
 

Author Comment

by:gbilios
ID: 12027600
you still havent explained this line

while(jobs || fscanf(fp, "%s%d%d", jobs->process, &jobs->arrival_time,
     &jobs->cpu) != EOF)
0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12032384
An error of thinking on my part.  Somehow you have to indicate that the values in 'jobs' have not been enqueued yet, because the 'arrival_time' isn't equal to the current time yet.  But of course, you can't do that by setting 'jobs' to NULL; that was a stupid mistake on my part, my apologies.  And setting 'jobs' to NULL is a mistake as well.  Forget the whole bit of setting 'jobs' to NULL.  (That would have worked if you had a separate function called 'get_new_job' or something like that, which mallocs a new pointer and fills in the values from an fscanf (And returns NULL if there are no more values to be gotten).)

Still, you need a way to know if the values in 'jobs' have been put in the queue yet, because you can't put them in the queue until the arrival_time is equal to ATIME.  And as long as that's not the case, you don't want to be fscanf-ing for new values.  Now, there is an easy way to see if those values have been enqueued or not, because you know when they will be enqueued (and therefore when they will have been enqueued.)
0
 

Author Comment

by:gbilios
ID: 12032542
it still doesn't output

let me explain something

the code in the enqueue function first checks that the queue is empty, if it is then it adds at the head(front) of the equeue, otherwise insert it at the rear.  you telling me before to do it in the main loop is therefore wrong as it is unnecessary.

thanks for your help i'll go back to it some other time

gbilios
0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12033546
Nope, what I told you to do in the main loop is to *dequeue* the jobs that are ready.

Basically, what you want to happen is something like this:

j1 2 3
j2 3 5
j3 5 2
j4 8 3
j5 16 4

queue is: ()
1, 2,  j1 arrives, queue is:  (j1)
3, j2 arrives, queue is: (j1, j2)
4, 5, j1 is finished, queue is: (j2)
j3 arrives, queue is: (j2, j3)
6, 7, 8, j4 arrives, queue is: (j2, j3, j4)
9, 10, j2 is finished, queue is: (j3, j4)
11, 12, j3 is finished, queue is: (j4)
13, 14, 15, j4 is finished, queue is: ()
16, j5 arrives, queue is: (j5)
17, 18, 19, 20, j5 is finished, queue is: ()
finish.
0
 

Author Comment

by:gbilios
ID: 12033690
This is what you posted previously

"No.  I don't mean a loop in the enqueue function.  The enqueue function should only enqueue jobs, not do lots of other things.
The loop should be in main(), IMO, and use the enqueue and dequeue functions for enqueueing and dequeueing *only* "

in the enqueue function if count == 0 then add it to the front else add it to the rear

never mind , i'll study more on C and come up with my own answers
0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12035738
> in the enqueue function if count == 0 then add it to the front else add it to the rear

If you look more closely, you'll see that what actually happens is this:

Add it to the rear, if count == 0 then add it to the front *and* rear.
Which is logical, because if the queue is empty, when you add an element it is both the first and the last element.

If you think of it as 'add it to the rear, and if count == 0, also set the front', then it's more logical.
0
 

Author Comment

by:gbilios
ID: 12037119
thanks
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

757 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

21 Experts available now in Live!

Get 1:1 Help Now