CPU allocation algorithms, Gantt chart scheduling evaluations, and queue strategies.

1. Scheduling Terms & Definitions

2. Numerical Scheduling Trace Examples

Shortest Job First (SJF)

Definition: Non-preemptive scheduling that selects the waiting process with the smallest CPU burst time for the next execution slot.

Pros

Cons

Starvation: Long processes can wait indefinitely if short processes are constantly submitted.
Impossible to know next CPU burst length beforehand (must be predicted).

Use Case: Long-term scheduler in mainframe environments where execution time limits are declared in job attributes.

Gantt Chart (Execution Trace):

At t=4, P2 (BT=3), P3 (BT=1), and P4 (BT=2) are ready. P3 is selected first because it has the shortest burst time.

P1 | P3 | P4 | P2

0 4 5 7 10

• CT: P1=4, P3=5, P4=7, P2=10.
• TAT: P1=4, P2=9, P3=3, P4=4. (Avg: 5.00)
• WT: P1=0, P2=6, P3=2, P4=2. (Avg: 2.50)

Preemptive Priority Scheduling

Definition: CPU scheduling where tasks are assigned priorities, and a higher priority process preempts a lower priority running process.

Pros

Cons

Indefinite Blocking / Starvation: Low priority processes may never run if high priority tasks stream in.
Requires complex priority assignment; solved by aging (gradually increasing priority over wait time).

Use Case: Real-time operating systems (RTOS) or critical daemon process scheduling inside modern operating kernels.

Gantt Chart (Execution Trace):

At t=1, P2 (priority 1) arrives and preempts P1 (priority 2).

P1 | P2 | P1 | P4 | P3

0 1 4 7 9 10

• CT: P2=4, P1=7, P4=9, P3=10.
• TAT: P1=7, P2=3, P3=8, P4=6. (Avg: 6.00)
• WT: P1=3, P2=0, P3=7, P4=4. (Avg: 3.50)