***************************
Chapter 5: CPU Scheduling
***************************

-----------------
Basic Concepts
-----------------

* **CPU Scheduling** is the process of deciding which process in the ready queue should be allocated to the CPU next.
* The **CPU Scheduler** selects from among the processes in memory that are ready to execute and allocates the CPU to one of them.
* CPU scheduling is necessary because:
  
  - Multiple processes compete for CPU time.
  - It helps maximize CPU utilization and system throughput.

**Types of Scheduling:**
  
* **Long-term (Job Scheduling)** – selects which processes are admitted to the system.
* **Short-term (CPU Scheduling)** – decides which process gets the CPU next.
* **Medium-term Scheduling** – temporarily removes processes from memory (swapping).

**Scheduling Events:**
  
CPU scheduling decisions occur when a process:
  
1. Switches from running to waiting state.
2. Switches from running to ready state.
3. Switches from waiting to ready state.
4. Terminates.

Scheduling can be:

* **Preemptive** – process can be interrupted.
* **Non-preemptive** – process runs until completion or waits voluntarily.

--------------------------
Scheduling Criteria
--------------------------

* **CPU Utilization:** Keep the CPU as busy as possible.
* **Throughput:** Number of processes completed per time unit.
* **Turnaround Time:** Total time to execute a particular process.
* **Waiting Time:** Time a process spends waiting in the ready queue.
* **Response Time:** Time from request submission until the first response is produced.
* **Fairness:** Ensuring all processes get a reasonable share of CPU time.

**Goals of Scheduling:**

* Maximize throughput and CPU utilization.
* Minimize waiting time, turnaround time, and response time.

------------------------------------
Scheduling Algorithms
------------------------------------

1. **First-Come, First-Served (FCFS):**
   - Processes are scheduled in the order they arrive.
   - Non-preemptive.
   - Simple but can cause the *convoy effect* (long jobs delay shorter ones).

2. **Shortest Job First (SJF):**
   - Selects the process with the smallest CPU burst time.
   - Can be preemptive (Shortest Remaining Time First) or non-preemptive.
   - Optimal in minimizing average waiting time, but requires burst-time prediction.

3. **Priority Scheduling:**
   - Each process has a priority; the CPU is assigned to the highest-priority process.
   - Can be preemptive or non-preemptive.
   - May lead to *starvation*; use *aging* to prevent it.

4. **Round Robin (RR):**
   - Each process gets a small *time quantum*.
   - After the quantum expires, the process is preempted and moved to the end of the ready queue.
   - Ensures fairness; suitable for time-sharing systems.
   - Performance depends on the size of the time quantum.

5. **Multilevel Queue Scheduling:**
   - Ready queue is partitioned into multiple queues (e.g., foreground and background).
   - Each queue has its own scheduling algorithm.
   - Processes are permanently assigned to a queue.

6. **Multilevel Feedback Queue:**
   - Similar to multilevel queue, but allows processes to move between queues.
   - Used to dynamically adjust priorities.

------------------------------------
Multiprocessor Scheduling
------------------------------------

* Involves scheduling processes across multiple CPUs or cores.
* Two main approaches:

  - **Asymmetric Multiprocessing:** One processor handles scheduling and I/O; others execute user code.
  - **Symmetric Multiprocessing (SMP):** Each processor is self-scheduling; processes are in a common ready queue.

**Load Balancing:**
  
* Ensures that work is evenly distributed across all processors.
* Can be achieved by:
  - **Push Migration:** A process periodically checks for imbalance and moves processes from busy CPUs.
  - **Pull Migration:** Idle CPUs pull processes from busy ones.

**Processor Affinity:**
  
* Keeps a process on the same processor to improve cache performance.
* Types:
  - **Soft Affinity:** Preference but not enforced.
  - **Hard Affinity:** Process bound to a specific processor.

**Real-Time Scheduling:**
  
* Used in systems requiring strict timing constraints.
* Common algorithms: *Rate Monotonic (RM)*, *Earliest Deadline First (EDF)*.

--------------------------
Algorithm Comparison Table
--------------------------

.. list-table:: **Comparison of CPU Scheduling Algorithms**
   :widths: 20 10 15 15 15 25
   :header-rows: 1
   :align: center

   * - **Algorithm**
     - **Preemptive**
     - **Type**
     - **Fairness**
     - **Complexity**
     - **Remarks**
   * - FCFS (First-Come, First-Served)
     - No
     - Non-preemptive
     - Low (convoy effect)
     - Simple
     - Long jobs delay short ones
   * - SJF (Shortest Job First)
     - Optional
     - Both
     - Medium
     - Moderate
     - Optimal average waiting time
   * - Priority Scheduling
     - Optional
     - Both
     - Low (can starve low)
     - Moderate
     - Use aging to prevent starvation
   * - Round Robin (RR)
     - Yes
     - Preemptive
     - High
     - Simple
     - Depends on time quantum
   * - Multilevel Queue
     - Both
     - Preemptive/Non
     - Medium
     - High
     - Separate queues by type
   * - Multilevel Feedback Queue
     - Yes
     - Preemptive
     - High
     - Very High
     - Dynamic priority adjustment

--------------------------
Summary
--------------------------

* CPU scheduling is key to system performance and responsiveness.
* Algorithms differ in fairness, complexity, and efficiency.
* In multiprocessor systems, additional factors like load balancing and processor affinity come into play.