Lecture Notes: Scheduling and Scheduling Algorithms

Introduction to Scheduling

• Scheduling is crucial in multitasking operating systems to manage execution of multiple tasks.
• Multitasking: Multiple threads in a single program or multiple programs run simultaneously.
• Examples include:
  • Computer games: moving player and enemy objects, playing music, updating statistics.
  • Multi-user environments: multiple users need simultaneous servicing.

Role of the Scheduler

• Scheduler: Manages which processes execute next and for how long.
• Processes can:
  • Move to a running state when the current process is blocked or suspended.
  • Finish execution or get blocked if more data/input is required.
  • Run out of allotted time, then suspended and moved back to the ready queue.

Scheduling Algorithms

1. First Come First Serve (FCFS)

• Concept: Processes executed in the order they arrive, similar to a supermarket queue.
• Processes wait for the current process to finish before being processed.

2. Shortest Job First (SJF)

• Concept: Processes with the shortest execution time are processed first.
• Scheduler must know how long each process will take.

3. Round Robin

• Concept: Each process is given a fixed time slice (quantum).
• If not completed, the process returns to the back of the ready queue.

4. Shortest Remaining Time (SRT)

• Type: Preemptive algorithm.
• Concept: Similar to SJF but can suspend a process if a higher priority process arrives.

5. Multi-Level Feedback Queues

• Concept: Uses multiple queues based on processor need.
• Design Principles:
  • Separates processes into different queues.
  • Prefers short CPU burst processes and high I/O burst processes.
• Features:
  • Processes that take too much CPU time are demoted.
  • I/O bound or interactive processes are promoted.
  • Long-waiting processes are moved to higher priority queues.
• Different queues can use different scheduling algorithms.

Process Blocking

• Occurs when a process requires data from slow input (e.g., hard disk).
• Blocked process waits until the input request is serviced.
• Process can be interrupted to alert scheduler when ready to rejoin queue.

Summary of Algorithms

• Understanding of preemptive vs. non-preemptive processes.
• Importance of knowing scheduling algorithms for exams.

Key Question

• From all open programs in memory, how does the CPU decide which process to execute?