University of Tehran
Faculty of Sciences
Faculty of Mathematics, Statistics, and Computer Science
OS: Assignment 4
CPU Scheduling
Author: Yousef Azizi Movahed
Problem 1
The Nature of Bursts and Preemption
Consider a legacy operating system that utilizes a strictly Non-preemptive schedul-
ing algorithm. A user reports a frustrating experience: while working with a text editor,
the system frequently "freezes" for several seconds, becoming unresponsive to keyboard
inputs. It is noted that a heavy video processing application is running in the background
simultaneously.
Questions:
(a) Using the concepts of CPU Burst and I/O Burst discussed in Chapter 5, explain
the underlying cause of this unresponsiveness. Specifically, categorize the typical
burst behavior of a "Text Editor" versus a "Video Processing Application."
(b) Explain how switching the scheduling algorithm to a Preemptive approach would
resolve this issue. Describe the mechanism the OS uses to interrupt the running
process.
Page 1
Problem 2
Round Robin Efficiency and Time Quantum Analysis
You are the system architect for a new server operating system. You have implemented
a Round Robin (RR) scheduling algorithm. However, performance metrics indicate a
significant drop in system Throughput. Upon investigation, the engineering team finds
the following parameters:
• The hardware Context Switch overhead is 10 microseconds.
• The Time Quantum (q) is currently set to 12 microseconds.
Questions:
(a) Analyze why the current configuration has led to poor performance. Discuss the
relationship between the time quantum and the context switch overhead.
(b) Conversely, if you were to increase the Time Quantum significantly (e.g., to 100
milliseconds), the RR algorithm would effectively behave like which other classic
algorithm? What specific problem (mentioned in the lectures regarding short in-
teractive processes behind long ones) might arise in this case?
Page 2
Problem 3
Prediction Challenges in SJF/SRTF
Theoretically, Shortest-Job-First (SJF) and Shortest-Remaining-Time-First
(SRTF) are considered optimal algorithms because they minimize the average waiting
time. However, they are rarely implemented in their pure form in general-purpose oper-
ating systems.
Questions:
(a) What is the fundamental difficulty in implementing SJF/SRTF in a real-world CPU
scheduler?
(b) The Exponential Averaging formula is used to predict the next CPU burst:
τn+1 = αtn + (1 − α)τn
Suppose a process has had a stable history of short CPU bursts (10ms), but its
behavior suddenly changes, and it begins executing long bursts (40ms).
• How does the prediction behave if α = 0?
• How does the prediction behave if α = 1?
• Which α value is more suitable for an environment where process behavior
changes rapidly? Justify your answer.
Page 3
Problem 4
Comprehensive Calculation and Algorithm Analysis
Data: Consider the following set of processes arriving at the Ready Queue at the
indicated times. (Note: Lower priority numbers imply higher priority.)
Process ID Arrival Time (ms) Burst Time (ms) Priority
P1 0 8 3
P2 1 4 1 (High)
P3 2 9 4
P4 3 5 2
Part I: Gantt Charts and Metrics
For each of the following scheduling algorithms, draw the Gantt Chart and create a
table showing the Completion Time, Turnaround Time, and Waiting Time for
each process. Finally, calculate the Average Waiting Time.
1. FCFS (First-Come, First-Served)
2. SJF (Non-Preemptive)
Note: Once a process starts, it cannot be interrupted even if a shorter job arrives.
3. SRTF (Shortest Remaining Time First - Preemptive SJF)
Note: Compare remaining times upon every new arrival.
4. Round Robin (Time Quantum q = 4 ms)
5. Preemptive Priority Scheduling
Part II: Analytical Discussion
Based on your calculations in Part I, answer the following:
(a) Which algorithm provided the minimal Average Waiting Time? Does this result
align with the theoretical claims regarding SJF/SRTF?
(b) In the Priority Scheduling scenario, did any process suffer from Starvation? If
new processes with Priority 1 continued to arrive indefinitely, what would happen
to P3 , and how can the OS solve this?
(c) Compare the Response Time of process P2 in the FCFS algorithm versus the
Preemptive Priority algorithm. Why is FCFS generally considered unsuitable for
interactive systems?
Page 4