Operating Systems - Projects and Exercises

Having got the Round Robin dispatcher going from last week, it is now a comparatively simple step to extend your code to make a multi-queue Feedback dispatcher - a working example is given in the course home page (use the feedback.txt file in that directory; e.g. >hostd feedback.txt). Project 2 requires a three level feedback policy with q = 1:

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 theFeedback 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:
   1. 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);
   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 any of the feedback queues:
         1. Send SIGTSTP to suspend it;
         2. Reduce the priority of the process (if possible) and enqueue it on the appropriate feedback queue
   3. If no process currently running && feedback queues are not all empty:
      1. Dequeue a process from the highest priority feedback queue that is not empty
      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! 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:

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

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

Feedback Dispatcher Operation (from Stallings fig 9.5)

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.