Operating Systems - Projects and Exercises

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).

First-Come-First-Served Dispatcher

A First-Come-First-Served (FCFS) dispatcher is essentially the same as a Batch Process Monitor. For the second project you will have a list of processes which you will need to schedule for execution depending on the time of submission and the priority of the process.

As always, we should start off simply - How would you go about accepting a list of programs from a file and executing them in a FCFS manner? e.g.

gcc -Wall -g sleepy.c -o sleepy
sleepy 20 > junk
cat junk

That's easy, you've esssentially just done that with a batch file for your first project! However, now associate an arrival time for each program so that execution of the program can not start until at least that time elapses. e.g.

0,sleepy 3
2,sleepy 6
4,sleepy 4
6,sleepy 5
8,sleepy 2

Or using the process list format defined for the second project and using sensible default values:

<arrival time>,<priority>,<cputime>,<memory alloc>,<res1 alloc>,<res2>,<res3>,<res4>

0, 0, 3, 64, 0, 0, 0, 0
2, 0, 6, 64, 0, 0, 0, 0
4, 0, 4, 64, 0, 0, 0, 0
6, 0, 5, 64, 0, 0, 0, 0
8, 0, 2, 64, 0, 0, 0, 0

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 structure 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 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;
4. While there's anything in the queue or there is a currently running process:
   1. 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
   2. If no process currently running &&
      dispatcher queue is not empty &&
      arrivaltime of process at head of queue is <= dispatcher timer:
      1. Dequeue process and start it (fork & exec)
      2. Set it as currently running process;
   3. sleep for one second;
   4. Increment dispatcher timer;
   5. Go back to 4.
5. Exit.

or something like that!

For the purposes of this exercise (and the 2nd project) you should use the process process supplied for the first project - it will tell you what signals you have sent it as well as ticking away for the length of time you allow it to run. In the structure above, you would initialise the structure to:

PcbPtr newPcb = (PcbPtr) malloc(sizeof(Pcb));
...
newPcb->args[0] = "process";
newPcb->args[1] = NULL;
newPcb....

and then, when doing the exec all you need to do is:

execvp(activePcb->args[0], activePcb->args);

There are a number of ways to terminate a job. Since we know it's 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. You could also send SIGKILL but SIGINT is preferred. i.e. to terminate the process with Process ID activePcb->pid, you would call the function:

if(kill(activePcb->pid,SIGINT))
    fprintf(stderr,"terminate of %d failed",
            (int)activePcb->pid);

For the queue management, you may find the following function list useful:

PcbPtr startPcb(PcbPtr process)
- start a process
returns:
  PcbPtr of process
  NULL if start failed

PcbPtr terminatePcb(PcbPtr process)
- terminate a process
returns:
  PcbPtr of process
  NULL if terminate failed

PcbPtr createnullPcb(void)
- create inactive Pcb.
returns:
  PcbPtr of newly initialised Pcb
  NULL if malloc failed

PcbPtr enqPcb (PcbPtr headofQ, PcbPtr process)
- queue process (or join queues) at end of queue
- enqueues at "tail" of queue list.
returns:
  (new) head of queue

PcbPtr deqPcb (PcbPtr * headofQ);
- dequeue process - take Pcb from "head" of queue.
returns:
  PcbPtr if dequeued,
  NULL if queue was empty
  & sets new head of Q pointer in adrs at 1st arg

The last three functions should be able to be dragged (kicking and screaming) from your earlier Programming unit(s). We have used a simple specific queue implementation here rather than a generic one, but there is nothing to stop you using your own implementation provided that it operates as a proper FIFO queue.

To see the sort of sequence of output you should be getting, run the following command line on the course home directory (this should have the reference hostd and process applications)

>hostd fcfs.txt

and compare the output with the top example of Figure 9.5 of Stalling's Operating Systems textbook:

Code should be in 'straight' C using the compiler of your choice (cc or gcc).

Always use nice to execute your test programs at lower priority to ensure they do not inconvenience other users if they go 'haywire'. e.g.:
 
   >nice a.out

The descriptions of the system functions above are drawn from sources that include manuals on the Sun Solaris system and the MAC OS X Darwin/BDS system, and also from 'Advanced Programming in the UNIX Environment', W. Richard Stevens, Addison-Wesley, 1993.