Lecture 8 Summary: Traditional Algorithms

1. First-Come, First-Served (FCFS)

• Logic: The process that requests the CPU first gets it first (Non-preemptive).
• Problem: Convoy Effect: Short processes wait for a very long process to finish, leading to poor CPU and device utilization.
• Performance: Simple but usually results in high average waiting times.

2. Shortest-Job-First (SJF)

• Logic: Associate each process with the length of its next CPU burst. Use these lengths to schedule the process with the shortest time.
• Optimality: SJF is optimal because it gives the minimum average waiting time for a fixed set of processes.
• Varieties:
  1. Non-Preemptive SJF: Once the CPU is given to a process, it cannot be stopped until it finishes its burst.
  2. Preemptive SJF (Shortest-Remaining-Time-First - SRTF): If a new process arrives with a CPU burst shorter than the remaining time of the current process, the current process is stopped (preempted).

3. Important Formulas

• Start Time: When the process actually begins using the CPU.
• Exit/Completion Time (CT): When the process finishes.
• Averages: Sum of (WT or TAT) of all processes / Total number of processes.