Tracing Algorithms: Banker's and CPU Scheduling
This exercise asks you to trace two families of algorithms by hand, so that you can see how they work step by step rather than only describing them. You will trace Banker’s algorithm for deadlock avoidance and detection, and you will trace FCFS, SJF, and RR scheduling on the same task set.
Part 1: Banker’s Algorithm
Compose a data set (or locate one in the textbook) for Banker’s algorithm. The data set must include:
Available: a vector of lengthm, the number of available instances of each resource type.Max: ann × mmatrix, the maximum claim of each process.Allocation: ann × mmatrix, what each process currently holds.Need: ann × mmatrix, computed asMax − Allocation.
Choose a data set with at least four processes and at least three resource types, and with at least one resource type that has more than one instance.
1a. Deadlock Avoidance (Safety Algorithm)
Run the safety algorithm on your data set. Show:
- The initial
WorkandFinishvectors. - At each step, which process is found (the one with
Finish[i] == falseandNeed[i] ≤ Work), and the updatedWorkandFinish. - The safe sequence if one exists, or the statement that the system is in an unsafe state if no sequence completes.
1b. Deadlock Detection (Detection Algorithm)
Run the detection algorithm on the same data set, but using the
Request matrix instead of Need. Show:
- The initial
WorkandFinishvectors, withFinish[i] = truefor any process withAllocation[i] == 0. - At each step, which process is found (the one with
Finish[i] == falseandRequest[i] ≤ Work), and the updatedWorkandFinish. - The set of processes that remain unfinished, which is the set of deadlocked processes.
If your data set is safe under the safety algorithm but deadlocked
under the detection algorithm, explain why the two answers differ. If
the two answers agree, explain why the Request matrix produces the
same result as the Need matrix for this data set.
Part 2: CPU Scheduling
Compose a data set (or locate one in the textbook) for CPU scheduling. The data set must include, for each task:
- an arrival time,
- a burst time,
- (for priority scheduling, if you include it) a priority.
Choose a data set that distinguishes the algorithms: at least one pair of algorithms must produce different average waiting times. A data set where all arrival times are zero will make FCFS and SJF produce the same result, so avoid that.
2a. Trace FCFS, SJF, SRTF, and RR
For each of the three algorithms, trace the schedule on your data set:
- Draw the Gantt chart, showing which task runs in each time interval.
- Compute, for each task:
- turnaround time = completion time − arrival time,
- waiting time = turnaround time − burst time,
- response time = first time the task runs − arrival time.
- Compute the average turnaround time, waiting time, and response time across all tasks.
- For RR, state the time quantum you used, and explain why you chose it.
2b. Compare the Algorithms
Answer the following:
- Which algorithm has the lowest average waiting time on your data set? Which has the highest? Explain why, in terms of the algorithm’s rule.
- Which algorithm has the lowest average response time? Which has the highest? Explain why.
- If your data set produces the same average waiting time for two of the algorithms, explain why. (If it does not, skip this question.)
Deliverable
A concise presentation:
- Your Banker’s data set and the trace for the safety algorithm and the detection algorithm.
- Your scheduling data set and the Gantt charts for FCFS, SJF, and RR.
- The comparison of the three algorithms on the same data set: which one wins on waiting time, which one wins on response time, and why.
- One thing that surprised you when you traced the algorithms by hand.
The last item is required and is graded. A presentation with no surprise to report is incomplete: tracing by hand usually reveals something that is not obvious from the algorithm’s definition, and that is the point of the exercise.
Reference for Response Time
The lecture defines response time as the time from submission to the first time the task runs. This is the definition to use in Part 2a. (If you use a different definition, state it and use it consistently.)