Past exam questions

Quote

QUESTION 2 (2004) [10]
Consider the following pre-emptive priority-scheduling algorithm based on dynamically changing priorities:
Do While (jobs in ready queue)
Start the job with the numerically highest priority;
If (end of quantum or request for I/O) then
Suspend the job currently running;
Add 'alpha' to the priority of each waiting job;
Add 'beta' to the priority of the job that has just been running
End_If
Accept any new jobs into the ready queue with priority 0
End_Do

If the number of jobs in the ready queue is n, discuss the scheduling algorithms that result from each of the following settings of 'alpha' and 'beta':
2.1 'alpha' < 'beta' < 0 (3)
2.2 'beta' > 0 and 'alpha' = 'beta'/n (3)
2.3 'alpha' = 'beta'/(n + 1) and 'beta' = (1 - n) (4)

QUESTION 3 (2004) [18]
Consider the following set of processes with arrival times, length of the
CPU-burst times (in milliseconds) and priorities below:
Process : Arrival time : Burst time : Priority
P1 : 0 : 4 : 2
P2 : 3 : 1 : 1
P3 : 4 : 9 : 2
P4 : 10 : 2 : 4
P5 : 12 : 4 : 3
P6 : 13 : 3 : 4
Assume that a smaller priority number indicates a higher priority.

3.1 Draw three GANTT charts, each showing the execution of these processes over time for each of the following scheduling algorithms: (8)
(a) Shortest Job First (SJF) without pre-emption
(b) A non-pre-emptive priority algorithm
(c) Round Robin with the quantum set to 2 /
NOTE: Apply the following two (2) principles when calculating the GANTT chart for Round Robin:
(1) A new job that enters the system is placed at the back of the ready queue, taking its place after the jobs already waiting to execute.
(2) A new job which enters the system for the first time is given preference over a job that has just finished executing a quantum. Such a new job will still be placed at the back of the ready queue, but ahead of a job which is also placed at the back of the queue after finishing a time quantum.
3.2 Give formulas for the turnaround time and waiting time of a process and then use these formulas to calculate the turnaround time and the waiting time for each process under each of the algorithms in 3.1 above. Show all your calculations clearly. (8)
3.3 Calculate which one of the schedulers in 3.1 above results in the minimal average waiting time over all the processes. Again, show all your calculations clearly. (2)

QUESTION 4 (2004) [15]
A particular system uses the deadlock avoidance approach. At time t0 the system state is:
Process : Allocation : Max : Available
P0 : 1 0 0 4 : 1 6 5 6 : 1 5 2 0
P1 : 1 4 2 2 : 2 4 5 7 :
P2 : 0 0 1 2 : 0 0 1 2 :
P3 : 0 2 1 0 : 1 7 5 0 :
P4 : 0 6 3 2 : 0 6 5 2 :
4.1 Give formulas to calculate the Need array as well as the maximum resource vector. (2)
4.2 Use your formulas in 4.1 above to calculate the contents of the array Need as well as the content of the maximum resource vector. (3)
4.3 Determine whether the system is in a safe state by trying to calculate a safe sequence. Show all workings clearly. (8)
4.4 Suppose a request from process P0 arrives for (0, 5, 3, 0). Determine whether the request may be safely granted or not. Show all workings clearly. (2)

QUESTION 3 (2007) [13]
A particular system uses the deadlock avoidance approach. At time t0 the system state is:
Process : Allocation : Need : Available
P0 : 3 0 1 1 : 1 1 0 0 : 1 0 2 0
P1 : 0 1 0 0 : 0 1 2 2 :
P2 : 1 1 1 0 : 3 1 0 0 :
P3 : 1 1 0 1 : 0 0 1 0 :
P4 : 0 0 0 0 : 2 1 1 0 :
3.1 Calculate the contents of the array Max as well as the content of the maximum resource vector. (3)
3.2 Determine whether the system is in a safe state by trying to calculate a safe sequence. Show all workings clearly. (8)
3.3 Suppose a request from process P2 arrives for (2, 0, 0, 0). Determine whether the request may be safely granted or not. Show all workings clearly. (2)

QUESTION 5 (2004)
Similar to Question 4.2 in our exam tut, but with sequence of page references given as:
b, c, e, h, c, f, i, c, g, c, b, c, e, b

QUESTION 7 (2007)
Similar to Question 6 in our exam tut, but with 50 blocks and block 26 in the middle.

QUESTION 6 (2004) [10]
Segmentation is similar to paging, but uses variable-sized segments instead of fixed-sized pages. Define two segment-replacement algorithms based on the FIFO and LRU page replacement schemes. Remember that since segments are of different sizes, the segment that is chosen to be replaced may not be big enough to leave enough consecutive memory locations for the new segment to be loaded. Consider suitable strategies for systems where segments cannot be relocated and for systems where they can be relocated.
Write your 2 algorithms in a suitable block-structured pseudocode language (e.g. Pascal-, C-, or Java-like pseudo code).

QUESTION 7 (2004) [15]
Write a well-planned essay in which you name and discuss the three (3) common routing schemes used to route messages through a network.
Build your essay around the following topics:
(a) the names of the 3 schemes.
(b) how each of these schemes work.
(c) the advantages, disadvantages and problems of each scheme.
(d) the best scheme of the three with justification.
Note: Any good essay starts with an Introduction, followed by the Body and ends with a sensible Conclusion.

QUESTION 8 (2004) [7]
Consider the Banker's resource-request algorithm below:

1. If Request_i <= Need_i
then proceed to step 2.
Else Error.
2. If Request_i <= Available
then proceed to step 3.
Else Wait.
3. Allocate requested resources
to process P_i by
modifying the state as follows:
Available := Available -
Request_i;
Allocation_i := Allocation_i +
Request_i;
Need_i := Need_i - Request_i;

Let n be the number of processes in the system and m be the number of resource types. Prove that the algorithm given above requires an order of mn operations (i.e. complexity is O(mn)).