A Worked Practical Paper: Q.1 and Q.2

Copy the output from the screen, not from your head. It is the single thing most likely to be checked against the program, and the reason this whole book was written with a checker that runs every listing.

Q.1, worked: round robin scheduling

Q.1 Write a program to simulate Round Robin CPU scheduling for the following set of

processes with a time quantum of 3. Display the Gantt chart, and compute the waiting time and

turnaround time of each process and their averages. [15] | Process | Arrival time | Burst time

| | --- | ---: | ---: | | P1 | 0 | 5 | | P2 | 1 | 4 | | P3 | 2 | 2 | | P4 | 3 | 1 |

The algorithm, which goes on the paper first

1. Set left[i] to the burst time of every process, and the clock to 0.
2. Put every process that has arrived by the clock on to the ready queue, in arrival order.
3. If the queue is empty, the processor is idle: move the clock to the next arrival and go to 2.
4. Take the process at the front of the queue. Run it for the quantum, or for what it has left,

whichever is less. Add that to the clock.

1. Put on to the queue every process that arrived while it was running.
2. If it has finished, record the clock as its completion time. Otherwise put it at the back of

the queue.

1. Repeat from 2 until every process has finished.
2. For each: turnaround time is completion minus arrival, waiting time is turnaround minus burst.

Average each over the number of processes.

Step 5 is the one that carries a mark and is the one most often left out: a process that arrives during a slice joins the queue before the process that has just been preempted.

The program

/* Q.1  Round robin CPU scheduling with a given time quantum.
   Compute the Gantt chart, waiting time and turnaround time.        */

#include <stdio.h>

#define N 4                 /* processes */
#define Q 3                 /* the time quantum                      */

int main(void)
{
    char name[N][4]     = { "P1", "P2", "P3", "P4" };
    int  arrival[N]     = {  0,    1,    2,    3  };
    int  burst[N]       = {  5,    4,    2,    1  };
    int  left[N], finish[N];
    int  queue[64], head = 0, tail = 0, count = 0;
    int  now = 0, done = 0, arrived = 0, i;

    for (i = 0; i < N; i++)
        left[i] = burst[i];

    printf("Gantt chart\n  ");

    while (done < N) {
        while (arrived < N && arrival[arrived] <= now) {
            queue[tail++] = arrived++;
            count++;
        }
        if (count == 0) {                      /* the processor is idle */
            printf("|idle %d", now);
            now = arrival[arrived];
            continue;
        }

        i = queue[head++];
        count--;

        int run = left[i] < Q ? left[i] : Q;
        printf("|%s %d", name[i], now);
        now += run;
        left[i] -= run;

        while (arrived < N && arrival[arrived] <= now) {
            queue[tail++] = arrived++;
            count++;
        }
        if (left[i] == 0) {
            finish[i] = now;
            done++;
        } else {
            queue[tail++] = i;
            count++;
        }
    }
    printf("| %d\n\n", now);

    printf("  P   AT  BT  CT  TAT  WT\n");
    int tat_total = 0, wt_total = 0;
    for (i = 0; i < N; i++) {
        int tat = finish[i] - arrival[i];
        int wt  = tat - burst[i];
        tat_total += tat;
        wt_total  += wt;
        printf("  %-3s %2d  %2d  %2d  %3d  %2d\n",
               name[i], arrival[i], burst[i], finish[i], tat, wt);
    }
    printf("\n  average turnaround time = %d / %d = %.2f\n",
           tat_total, N, (double) tat_total / N);
    printf("  average waiting time    = %d / %d = %.2f\n",
           wt_total, N, (double) wt_total / N);
    return 0;
}

Gantt chart
  |P1 0|P2 3|P3 6|P4 8|P1 9|P2 11| 12

  P   AT  BT  CT  TAT  WT
  P1   0   5  11   11   6
  P2   1   4  12   11   7
  P3   2   2   8    6   4
  P4   3   1   9    6   5

  average turnaround time = 34 / 4 = 8.50
  average waiting time    = 22 / 4 = 5.50

Checking it by hand, which is what you do while the write-up dries

The Gantt chart says P1 from 0 to 3, P2 from 3 to 6, P3 from 6 to 8, P4 from 8 to 9, P1 from 9 to 11, P2 from 11 to 12.

• average turnaround time = (11 + 11 + 6 + 6) / 4 = 34 / 4 = 8.50
• average waiting time = (6 + 7 + 4 + 5) / 4 = 22 / 4 = 5.50

And a check that costs nothing: the last completion is 12, and the total burst time is 5 + 4 + 2 + 1 = 12. They agree, so the processor was never idle and no time was lost. If the last completion time exceeds the total burst time and no idle gap appears in your chart, something is wrong.

The conclusion for the write-up

Round robin scheduling was simulated with a time quantum of 3 over four processes with different

arrival times, using a queue of process indices as the ready queue. The Gantt chart shows six

slices and the processor never idle, the last completion at 12 equalling the total burst time of

12. The average turnaround time was 8.50 and the average waiting time 5.50 units. A process

arriving during a slice was added to the queue before the preempted process, which is what

determines the order of the chart.

Q.2, worked: a binary search tree and its traversals

Q.2 Write a program to create a binary search tree from the dataset 55, 30, 80, 20, 45, 70,

90, 35 and to perform the in-order, pre-order and post-order traversals. Also search for a key

that is present and one that is not. [15]

The algorithm

1. A node holds a key, a left child and a right child, both None at first.
2. To insert a key: if the subtree is empty, the key becomes a new node. If the key is smaller

than the node's, insert into the left subtree; if larger, into the right; if equal, do nothing.

1. In-order: the left subtree, then the node, then the right subtree.
2. Pre-order: the node, then the left subtree, then the right.
3. Post-order: the left subtree, then the right, then the node.
4. To search: compare with the node; go left if smaller, right if larger, stop when equal or when

the subtree is empty.

The program

# Q.2  Create a binary search tree from a dataset and perform the
#      in-order, pre-order and post-order traversals.

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


class BST:
    def __init__(self):
        self.root = None

    def insert(self, key):
        self.root = self._insert(self.root, key)

    def _insert(self, node, key):
        if node is None:
            return Node(key)
        if key < node.key:
            node.left = self._insert(node.left, key)
        elif key > node.key:
            node.right = self._insert(node.right, key)
        return node                      # a duplicate is ignored

    def search(self, key):
        here = self.root
        while here is not None:
            if key == here.key:
                return True
            here = here.left if key < here.key else here.right
        return False

    def in_order(self, node, out):
        if node is not None:
            self.in_order(node.left, out)
            out.append(node.key)
            self.in_order(node.right, out)
        return out

    def pre_order(self, node, out):
        if node is not None:
            out.append(node.key)
            self.pre_order(node.left, out)
            self.pre_order(node.right, out)
        return out

    def post_order(self, node, out):
        if node is not None:
            self.post_order(node.left, out)
            self.post_order(node.right, out)
            out.append(node.key)
        return out

    def height(self, node):
        if node is None:
            return -1
        return 1 + max(self.height(node.left), self.height(node.right))


data = [55, 30, 80, 20, 45, 70, 90, 35]
t = BST()
for k in data:
    t.insert(k)

print("dataset      :", data)
print("in-order     :", t.in_order(t.root, []))
print("pre-order    :", t.pre_order(t.root, []))
print("post-order   :", t.post_order(t.root, []))
print("height       :", t.height(t.root), "edges")
print("search 45    :", t.search(45))
print("search 60    :", t.search(60))
print("in-order is sorted:", t.in_order(t.root, []) == sorted(data))

dataset      : [55, 30, 80, 20, 45, 70, 90, 35]
in-order     : [20, 30, 35, 45, 55, 70, 80, 90]
pre-order    : [55, 30, 20, 45, 35, 80, 70, 90]
post-order   : [20, 35, 45, 30, 70, 90, 80, 55]
height       : 3 edges
search 45    : True
search 60    : False
in-order is sorted: True

The tree, which goes on the paper

            55
          /    \
        30      80
       /  \    /  \
     20    45 70    90
          /
        35

Read the three traversals off it and check them against the program:

• in-order, left, node, right: 20, 30, 35, 45, 55, 70, 80, 90. Sorted, which is the mark

to make in the conclusion.

• pre-order, node, left, right: 55, 30, 20, 45, 35, 80, 70, 90. The root first, at every

level.

• post-order, left, right, node: 20, 35, 45, 30, 70, 90, 80, 55. The root last.

The height is 3 edges, because 35 is at depth 3.

The conclusion for the write-up

A binary search tree was built from the eight given keys by inserting each into the subtree

determined by comparison with the current node. The three depth-first traversals were performed

recursively. The in-order traversal gave 20, 30, 35, 45, 55, 70, 80, 90, which is the dataset in

sorted order, and that is a consequence of the search property: every key in a left subtree is

smaller than its node and every key in a right subtree is larger. The tree has height 3, and a

search took at most 4 comparisons, one per level.

A bank of likely questions

MU sets one question per module, so an examiner picks from a list of this kind. For each: the chapter to revise, what the answer has to contain, and the trap.

Module 1

Module 2

What an examiner is marking

Out of 15, in about these proportions. Your college may weight them differently and the shape will be the same.

The largest single avoidable loss is output that does not match the program. It is three marks and it is the easiest thing in the paper to get right: copy the screen.

Result

MU's printed paper pattern was set out, two questions of 15 marks each with no viva question, and a plan for the two hours given. One question from each module was answered in full at examination length: round robin scheduling in C with the Gantt chart, the per-process figures and the two averages, checked by hand and against the total burst time; and a binary search tree in Python with the three traversals, the tree drawn and the in-order walk shown to be the dataset in sorted order. A bank of twenty-six likely questions was tabulated with the chapter to revise and the trap in each.

Quick revision

• The paper is 2 hours, 30 marks: Q.1 on Module 1 for 15, Q.2 on Module 2 for 15.

No viva question in this scheme.

• A certified journal and 16 of the 20 practicals are conditions of sitting it.
• Read both questions first and answer the easier one first, completely.
• Write the aim and the algorithm on paper before typing. It carries marks and it prevents a

half-designed program.

• Get something running early, then extend. Compile every ten lines.
• Copy the output from the screen. Output a program cannot produce is the largest avoidable loss.
• For a scheduling answer, check that the last completion time equals the total burst time when

there is no idle gap.

• For a tree answer, check that the in-order traversal is the dataset sorted.
• Leave five minutes for your name, roll number and the question numbers on every sheet.

Questions you should be able to answer

1. What is the paper pattern for this practical? Two hours, 30 marks: Q.1 a practical question on Module 1 for 15 marks and Q.2 one on Module 2 for

1. There is no separate viva question in this scheme.

2. What are the two conditions for being allowed to sit it? A certified journal, and at least 80 per cent of the practicals completed, which is 16 of the 20.

3. Which question should be answered first? Whichever is easier for you. Read both before starting; the numbering is not an instruction.

4. What is the cheapest check on a CPU scheduling answer? That the last completion time equals the sum of the burst times, when the Gantt chart shows no idle gap. If it is larger and there is no gap, something is wrong.

5. What is the cheapest check on a binary search tree answer? That the in-order traversal is the dataset in sorted order. If it is, the search property holds at every node.

6. What is the largest avoidable loss of marks? Output that the program above it could not have produced. It is worth about three marks and it is prevented by copying the screen.

7. Why write the algorithm when time is short? Because it carries about two marks of its own, takes four minutes, and stops the commonest disaster, which is a program half written to two different designs.