Process Dispatcher Lab

Inspired by Operating System Concepts, 8^th Edition, Silberschatz, Galvin, Gagne

Adapted by M.D Doman 2013

For the second project you will need to implement both a First-Come-First-Served process dispatcher, and, effectively, a Round-Robin dispatcher (more about this soon).

1. Design a dispatcher that satisfies the criteria defined below.

a. The dispatcher will be created as a child process from your shell program. To do this, you will replace the system() function call with fork() and exec() calls.

b. Because the shell will be the session leader it will have control and access to the terminal input. The dispatcher must accept a file with list of the programs to ‘dispatch’.For the dispatcher process, redirect the stdin and stdout to files.

c. Write the dispatcher. Design help for each dispatcher algorithm is given below.

2. In a formal design document:
   
1. Describe and discuss the structures or classes used by the dispatcher for queuing, dispatching and allocating memory and other resources.
2. If your design required memory allocation: Describe and discuss what memory allocation algorithms you could have used and justify your final design choice.
3. Describe and justify the overall structure of your program, describing the various modules and major functions (descriptions of the function 'interfaces' are expected).
4. Discuss the possible use of a multilevel dispatching scheme, which would combine FCFS for real-time processes and RR or Feedback for prioritized processes.
5. Include results from your run and an explanation or interpretation of the output.
6. Diagram the flow of control (Gantt diagram) that illustrates the execution of the dispatched processes.
7. Discuss turnaround time for each algorithm.
1. Determine (and show how it was calculated) the turnaround time of each process (i.e., how long was it in the system?)
2. Determine the average turnaround time.
8. Include the source of our code.
9. Include instructions on how to compile and run your code.

The formal design document is expected to have in-depth discussions, descriptions and arguments.

fork() and exec() calls from shell program

So far, our shell has used the system call to pass on command lines to the default system shell for execution. Since we need to control what open files and file descriptors are passed the dispatcher, we need more control over there execution. To do this we need to use the fork and exec system calls.

1. In your Shell program, replace the use of system with fork and exec
2. You will now need to more fully parse the incoming command line so that you can set up the argument array (char *argv[] in the above examples).
3. You will find that while a system function call only returns after the program has finished, the use of fork means that two processes are now running in foreground. In most cases you will not want your shell to ask for the next command until the child process has finished. This can be accomplished using the wait or waitpid functions. e.g.

switch (child_pid = fork()) {

// error condition

case -1:

syserrmsg("fork",NULL);

break;

// I am the dispatcher (child) process

case 0:

execvp(args[0], args);

syserrmsg("exec failed -",args[0]);

exit(127);

// I am the shell (parent) process

default:

if (!dont_wait)

waitpid(pid, &status, WUNTRACED);

Obviously, in the above example, if you wanted to run the child process 'in background', the flag dont_wait would be set and the shell would not wait for the child process to terminate.

I/O Redirection

Your project shell must support I/O-redirection on both stdin and stdout. i.e. the command line:

programname arg1 arg2 < inputfile > outputfile

will execute the program programname with arguments arg1 and arg2, the stdin FILE stream replaced by inputfile and the stdout FILE stream replaced by outputfile.

With output redirection, if the redirection character is > then the outputfile is created if it does not exist and truncated if it does. If the redirection token is >> then outputfile is created if it does not exist and appended to if it does.

Note: you can assume that the redirection symbols, < , > & >> will be delimited from other command line arguments by white space - one or more spaces and/or tabs. This condition and the meanings for the redirection symbols outlined above and in the project differ from that for the standard shell.

I/O redirection is accomplished in the child process immediately after the fork and before the exec command. At this point, the child has inherited all the file-handles of its parent and still has access to a copy of the parent memory. Thus, it will know if redirection is to be performed, and, if it does change the stdin and/or stdout file streams, this will only affect the child not the parent.

The easiest way to do this is to use freopen. freopen opens a specified file on a specified stream, closing the stream first if it is already open. This function is typically used to open a specified file as one of the predefined streams, stdin, stdout, or stderr.

Freopen (“filename”, “type”, stdin/stdout/stderr)

The type string is the standard open argument:

type	Description
r or rb w or wb a or ab r+ or r+b or rb+ w+ or w+b or wb+ a+ or a+b or ab+	open for reading truncate to 0 length or create for writing append; open for writing at end of file, or create for writing open for reading and writing truncate to 0 length or create for reading and writing open or create for reading and writing at end of file

where b as part of type allows the standard I/O system to differentiate between a text file and a binary file.

Thus:

freopen("inputfile", "r", stdin);

would open the file inputfile and use it to replace the standard input stream, stdin.

. ***********************************************************************/

switch (child_pid = fork()) {

// error condition

case -1:

syserrmsg("fork",NULL);

break;

// I am the dispatcher (child) process

case 0:

// I/O redirection: stdin */

if (myINfile.txt) {

if (!freopen((myINfile.txt, "r", stdin))

errmsg((myINfile.txt,"can't be open for i/p redirect.");

}

if (myOUTfile.txt) {

if (!freopen(myOUTfile.txt, sstatus.outmode, stdout))

errmsg(myOUTfile.txt,"can't be open for o/p redirect.");

}

execvp(args[0], args);

syserrmsg("exec failed -",args[0]);

exit(127);

// I am the shell (parent) process

default:

if (!dont_wait)

waitpid(pid, &status, WUNTRACED);

Process to be dispatched:

The process to be dispatched can be as simple as the following. In fact, it can be the following. The idea is to have the process sleep for a period to ensure the process will run for an allotted time. The sleep function causes the calling process to be suspended until either the amount of wall clock time specified by seconds has elapsed, or a signal is caught by the process and the signal handler returns. The return value from sleep is either 0 or the number of un-slept seconds if the sleep has been interrupted by a signal interrupt.

#include <iostream>

#include <stdlib.h>

#include <unistd.h>

using namespace std;

int main (int arg, char *argv[])

{

int n = atoi(argv[2]);

while (0 < n)

{

printf("Process Executing: %s; PID: %lu\n”, argv[1], (unsigned long)getpid());

sleep(1);

n--;

}// end of while

}//end of main

First-Come-First-Served Dispatcher

The input file will associate an arrival time for each program so that execution of the program can not start until at least that time elapses. e.g.

<arrival time>,program name, <priority>,<cputime>

0,P1,0,3 1^st Job: Arrival time 0, priority 0 (Real-Time), requiring 3 seconds of CPU time

2,P2,0,6 2^st Job: Arrival time 2, priority 0 (Real-Time), requiring 6 seconds of CPU time
4,P3,0,4
6,P4,0,5
8,P5,0,2

You will need to create a queue of job structures so that you only dequeue a job when the appropriate time has elapsed and there is no longer a current job running. (There is a guarantee that the jobs presented in the input dispatch file will be in chronological order of arrival).

The first thing to do is to define a process control block structure or class such as:

struct pcb {

pid_t pid; // system process ID

char * args[MAXARGS]; // program name and args

int arrivaltime;

int remainingcputime;

struct pcb * next; // links for PCB handlers

};

typedef struct pcb PCB;

typedef PCB * PcbPtr;

This structure/class can be used for all the queues (linked lists) needed for the project (with a few extra elements in the structure).

Dispatcher algorithm:

The basic First-Come-First-Served (FCFS) dispatcher algorithm can be reduced to the following pseudo-code. Note that the tests may appear to be out of order (shouldn't one be doing the test at 4.i after the sleep rather than before it?). With the current model it makes no difference, but there are reasons for doing it in this order as we shall see when we come to the multiple dispatcher models later on.

1. Initialize dispatcher queue;

2. Fill dispatcher queue from dispatch list file;

3. Start dispatcher timer (dispatcher timer = 0);

4. While there's anything in the queue or there is a currently running process:

i. If a process is currently running;

a. Decrement process remainingcputime;

b. If times up:

A. Send SIGINT to the process to terminate it;

B. Free up process structure memory

ii. If no process currently running &&
dispatcher queue is not empty &&
arrivaltime of process at head of queue is <= dispatcher timer:

a. Dequeue process and start it (fork & exec)

b. Set it as currently running process;

iii. sleep for one second;

iv. Increment dispatcher timer;

v. Go back to 4.

5. Exit.

or something like that!

Be sure to include: #include <sys/types.h> and #include <signal.h>

There are a number of ways to terminate a job. Since we know its process ID, the easiest way to do this is to send the process a terminating signal using the kill function. The one we need to use here is SIGINT, which is the equivalent of the Ctrl-C keyboard interrupt fielded by the shell. Use waitpid will check the termination of your child process.

kill (pid, SIGINT);

process_status = PCB_TERMINATED;

Round-Robin Dispatcher

Round Robin Dispatcher (from Stallings)

To suspend and restart processes as required by the Round Robin dispatcher will require the use of the SIGTSTP and SIGCONT signals as well as SIGINT that we used for the FCFS dispatcher.(see below).

To make the Round Robin dispatcher work (RR q=1) the logic should be:

1. Initialize dispatcher queues (input queue and RR queue);
2. Fill input queue from dispatch list file;
3. Start dispatcher timer (dispatcher timer = 0);
4. While there's anything in any of the queues or there is a currently running process:
1. Unload any pending processes from the input queue:
   While (head-of-input-queue.arrival-time <= dispatcher timer)
   dequeue process from input queue and enqueue on RR queue;
2. If a process is currently running:
1. Decrement process remainingcputime;
2. If times up:
1. Send SIGINT to the process to terminate it;
2. Free up process structure memory;
3. else if other processes are waiting in RR queue:
1. Send SIGTSTP to suspend it;
2. Enqueue it back on RR queue;
3. If no process currently running && RR queue is not empty:
1. Dequeue process from RR queue
2. If already started but suspended, restart it (send SIGCONT to it)
   else start it (fork & exec)
3. Set it as currently running process;
4. sleep for one second;
5. Increment dispatcher timer;
6. Go back to 4.
5. Exit.

or something like that!

Try this with the following job list with a quantum of 1 sec:

<arrival time>,program name, <priority>,<cputime>

0,P1,1,3 1^st Job: Arrival time 0, priority 1, requiring 3 seconds of CPU time

2,P2,1,6 2^st Job: Arrival time 2, priority 1, requiring 6 seconds of CPU time
4,P3,1,4
6,P4,1,5
8,P5,1,2

Feedback Dispatcher

Having got the Round Robin dispatcher going, it is now a comparatively simple step to extend your code to make a multi-queue

Three Level Feedback Dispatcher (from Stallings Fig 9.10)

The logic is very similar to the previous exercise except that instead of enqueueing an incomplete process back onto the same (RR) queue that the process came from, the process is enqueued onto a lower priority process queue (if there is one to receive it). Obviously, the lowest priority queue operates in exactly the same way as a simple Round Robin queue.

To make the Feedback dispatcher work in the same way as described in Stallings Figure 9.5 (Feedback q=1) the logic should be:

1. Initialize dispatcher queues (input queue and feedback queues);

2. Fill input queue from dispatch list file;

3. Start dispatcher timer (dispatcher timer = 0);

4. While there's anything in any of the queues or there is a currently running process:

i. Unload pending processes from the input queue:
While (head-of-input-queue.arrival-time <= dispatcher timer)
dequeue process from input queue and enqueue on highest priority feedback queue (assigning it the appropriate priority);

ii. If a process is currently running:

a. Decrement process remainingcputime;

b. If times up:

A. Send SIGINT to the process to terminate it;

B. Free up process structure memory;

c. else if other processes are waiting in any of the feedback queues:

A. Send SIGTSTP to suspend it;

B. Reduce the priority of the process (if possible) and enqueue it on the appropriate feedback queue

iii. If no process currently running && feedback queues are not all empty:

a. Dequeue a process from the highest priority feedback queue that is not empty

b. If already started but suspended, restart it (send SIGCONT to it)
else start it (fork & exec)

c. Set it as currently running process;

iv. sleep for one second;

v. Increment dispatcher timer;

vi. Go back to 4.

5. Exit.

or something like that! As you can see, there is really not much difference between this and the Round Robin we completed last week.

Try this with the following job list with a quantum of 1 sec:

<arrival time>,program name, <priority>,<cputime>

0,P1,3,3 1^st Job: Arrival time 0, priority 1 (Real-Time), requiring 3 seconds of CPU time

2,P2,3,6 2^st Job: Arrival time 2, priority 1 (Real-Time), requiring 6 seconds of CPU time
4,P3,3,4
6,P4,3,5
8,P5,3,2