Operating Systems - Projects and Exercises

Exercise 8 - Round Robin Dispatcher

Having got the FCFS dispatcher going from last week - a working example is given in the course home directory (use the fcfs.txt file in that directory; e.g. >hostd fcfs.txt). We now need to develop a Round Robin dispatcher. Since the Feedback dispatcher required for the low priority job streams described in Project 2 is essentially multiple Round Robin dispatcher queues, it makes sense to walk before we can run.

round robin
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 in the same way as described in Stallings Figure 9.5 (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:

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

This should produce the sequence shown in Stallings Figure 9.5 (RR q=1):

round robin
Round Robin Dispatcher Operation (from Stallings fig 9.5)

Signals

Signals provide one way of communicating with and controlling processes. A standard process has 'handlers' to field all the UNIX/POSIX signals. The default action of these handlers is sometimes to do nothing, or, for others to suspend or terminate the process with or without a core dump etc.

The program in sigtrap.c in the course home directory is an example of a program that traps some of the major process control signals and reports them on the terminal. This is in fact the process process that is to be executed by your dispatcher for project 2.

sigtrap (& process) is similar to sleepy in that it takes a command line argument to signify how many ticks it should tock. However, when exec'ed with no arguments (as for the project) it will 'tick' for a maximum of 20 seconds.

If you execute it as sigtrap 1000, and then apply the standard tcsh job control commands of ^Z, fg, ^Z, kill %1, etc you will get some idea of the signals that the shell is passing to it's execed children.

If you start up another terminal, you can pass your own signals to the sigtrap process by using the system utility kill. Again if you start up sigtrap 1000 and it reports a process ID of nnnnn, then try the command lines:

kill -TSTP nnnnn
kill -CONT nnnnn
kill -INT nnnnn

while observing the terminal window running the sigtrap process.

You can achieve the same effect inside a process that has forked sigtrap as a child:

#include <sys/types.h>
#include <signal.h>
    ...
    child_pid = fork();
    ...
    sleep(1);
    kill(child_pid, SIGTSTP);
    sleep(1);
    kill(child_pid, SIGCONT);
    sleep(1);
    kill(child_pid, SIGINT);

It is these last three signals we should be using for process control in the HOST dispatcher.

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.

Go home top

For use only by students and instructors using the supplementary material available with the text book: "Operating Systems - Internals and Design Principles", William Stallings, Prentice Hall, 5th Edition, 2004. Not to be printed out or copied by any other persons or used for any other purpose without written permission of the author(s).

©