CPU SCHEDULING

Basic Concepts

    1. switches from running to waiting state.
    2. switches from running to ready state.
    3. switches from waiting to ready.
    4. terminates.

Dispatcher

Scheduling Criteria

First-Come, First-Served (FCFS) Scheduling

Shortest-Job-First (SJF) Scheduling

Example of SJF

How do we know the length of the next CPU burst?

    1. Tn = actual length of n'th CPU burst
    2. Pn = predicted value of n'th CPU burst
    3. 0 <= W <= 1
    4. Define:
      Pn+1 = W * Tn + (1-W) Pn

Examples:

Priority Scheduling

Round Robin (RR)

Example of RR with time quantum = 20

Multilevel Queue

Multilevel Feedback Queue

Example of multilevel feedback queue

Multiple-Processor Scheduling

Real-Time Scheduling

Algorithm Evaluation

Summary