I have an assignment question . We need to simulate FCFS scheduling algorithm using C on linux OS.
This is what I need to do
Write a program to simulate FCFS scheduling algorithm using pipes for inter process communication.

  1. Let the parent program be the scheduler.
  2. It takes as input the number of processes to be scheduled. For each process there is additional
    information of arrival time and burst time. According to FCFS, the scheduler must schedule the
    process that enters with the least timestamp first and continue in the order of arrival of
    processes.
  3. Initially the time in scheduler is 0.
  4. For simplicity of time management assume 1 tick of time to be simulated by sleep (10).
  5. Scheduler increments time until the time = arrival time of the first process
  6. The scheduler must schedule the processes that have arrived in the order of their arrival times.
  7. For each process to be scheduled, scheduler:
    i)Creates two pipes Pipe_sched and Pipe_child, forks a child process.
    ii)Pipe_sched from communication from sched to child, Pipe_child for communication
    from child to sched
    iii)Scheduler writes on Pipe_sched, parameters: arrival time and burst time of the new
    process.
    iv)The scheduler must on wait for the process to complete.
    v)Child process reads the parameters on Pipe_Sched and increments time by simulating
    time tick with sleep (10) until burst time has elapsed.
    vi)On completion Child process must send current timestamp to scheduler (parent
    process) by writing on to the pipe Pipe_child.
    vii)The scheduler updates it current time upon reaching from Pipe_Child as the time
    returned by the process and continues scheduling other process
  8. After the simulation of all the processes, the scheduler program must compute the average
    wait time Average wait time and generate the Gant chart and exit.

I understand the concept of fork() and wait(). but I am having problems implementing this program using exec() (which will contain the code for the child process entering the scheduler) and i am havin problem with pipes(We have to use unnamed pipes)

Here is some code to mess with.
The first code chunk is the scheduler-ish program. It forks a child program that receives an amount of time to sleep from a pipe and outputs time slept to another pipe to the parent.
If the current working directory is not in your path put the full path to the sleeper program in the execlp function call.
After you compile the sleeper program be sure that the name of the executable matches what is in the execlp function call below or change it to match whatever you made it.

The code isn't pretty but it will get you started.

I used infor from these links to create it.
http://www.kernel.org/doc/man-pages/online/pages/man2/pipe.2.html
http://www.kernel.org/doc/man-pages/online/pages/man3/exec.3.html
http://www.kernel.org/doc/man-pages/online/pages/man2/dup2.2.html

scheduler-ish program

#include <sys/wait.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
int main(int argc, char *argv[])
{
    int i=0,pipeToChild[2], pipeToParent[2];
    pid_t cpid;
    char buf, sleepTime[64]={0};
    if (argc != 2) {
      fprintf(stderr, "Usage: %s <sleepTime>\n", argv[0]);
      exit(EXIT_FAILURE);
    }
    // Create the two pipes
    if (pipe(pipeToChild) == -1 || pipe(pipeToParent)) {
        perror("pipe");
        exit(EXIT_FAILURE);
    }
    // Fork the child
    cpid = fork();
    if (cpid == -1) {
        perror("fork");
        exit(EXIT_FAILURE);
    }
    // --------------------------------------------------
    // This is the child
    if (cpid == 0) {  
        // Close the pipes the child shouldn't use 
        close(pipeToParent[0]);
        close(pipeToChild[1]);
        // Setup the input and output of child    
        dup2(pipeToChild[0],0);
        dup2(pipeToParent[1],1);
        // Start the sleeper program
        execlp("sleeper", "sleeper",NULL);    // <------------  Sleeper program started
        printf("Error:  Should never get here!!\n");
    } 
    // --------------------------------------------------
    // This is the parent
    else {           
      // Close the pipes the parent shouldn't use
      close(pipeToChild[0]);          
      close(pipeToParent[1]);
      sprintf(sleepTime,"%s\n",argv[1]);
      // Write the amount of time to sleep to the child
      write(pipeToChild[1], sleepTime, strlen(sleepTime));
      // Clear buff
      memset(sleepTime,0,sizeof(sleepTime));
      // The child should send back something
      while ( i< 64 && read(pipeToParent[0],&buf,1)){
        sleepTime[i++]=buf;
      }
      close(pipeToChild[1]);         
      close(pipeToParent[0]);
      // Wait for child
      wait(NULL);            
      printf("Child message:  '%s'\n",sleepTime);
      exit(EXIT_SUCCESS);
    }
}

Sleeper program

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

int main(){
  int sleepTime;
  if ( scanf("%d",&sleepTime) == 1 ){
    sleep(sleepTime);
    printf("slept %d",sleepTime);
  } else {
    printf("Error\n");
  }
  return 0;
}

Output
$ ./a.out 4
Child message: 'slept 4'
$

Edited 4 Years Ago by histrungalot: Added

Thank you for the reply. Can you tell me how i can pass the timestamp(which will be required to make the gantt chart) to the process (which the child process will execute through exec) through execlp() or execvp() with an example.

Its doing it now. The parent code above writes a string to the pipe that contains the number of seconds to sleep in the sleeper program.

 sprintf(sleepTime,"%s\n",argv[1]);
 // Write the amount of time to sleep to the child
 write(pipeToChild[1], sleepTime, strlen(sleepTime));

In what you explained above, you can't pass the arrival time and burst time in the command line parameters:
iii)Scheduler writes on Pipe_sched, parameters: arrival time and burst time of the new
process.
Right now the parent writes one string that has the burst time(sleep time) you just need to add another number which is the arrival time.

Can you clarify:
iii)Scheduler writes on Pipe_sched, parameters: arrival time and burst time

vi)On completion Child process must send current timestamp to scheduler (parent
process) by writing on to the pipe Pipe_child.

vii)The scheduler updates it current time upon reaching from Pipe_Child as the time
returned by the process and continues scheduling other process

iii) should arrival time be schedule time?
vi) what is current timestamp? Is it time in iii + burst time?
vii) if the time in iii is not schedule time I don't know how this makes sense.

If you don't give the schedule time how are the children going to know what the current time is?

If you don't give the schedule time how are the children going to know what the current time is?
In FCFS scheduling the arrival time is schedule time for the first process.For subsequent processes it will depend on whether the burst time of previous process is greater or less than the arrival time of the process.
e.g. say we have processes p1(arrival 0 , burst time 5),p2(arrival time 2, burst time 3) and p3(arrival time 4, burst time 1)
Then the processes will be scheduled acc to arrival time
0 p1 5 p2 8 p3 9
this will be the gannt chart showing that processes have schedule time as 0 for p1, 5 for p2 and so on.
the current timestamp will be 5 after p1 executes and 8 after p2 executes.
Hope this made the question clearer.

the current timestamp will be 5 after p1 executes and 8 after p2 executes.

But according to: vi) On completion Child process must send current timestamp to scheduler (parent process) by writing on to the pipe Pipe_child.
How does the child know the current timestamp if all it was give was arrival and burst time?

        Arrtime       Burst      Schtime       Curtime
p1         0            5           0             5
p2         2            3           5             8
p3         4            1           8             9

"Child process must send current timestamp to scheduler", but the child only has arrival and burst time, it can't send current time.
If the child returned the burst time, the scheduler could increment the time by the burst time to get current time. But that is not the child returning the current time.

I interpret "vii)The scheduler updates it current time upon reaching from Pipe_Child as the time returned by the process and continues scheduling other process" as the time returned by the child as the current time. But again it can't know what current time is with out knowing scheduling time.

This article has been dead for over six months. Start a new discussion instead.