Scheduling types and approaches (A1.3: Operating systems and control systems)

I. KEY TERMS

Important terms to keep in mind

Monopolize resources (I. KEY TERMS)

Control of resource use by single process/user

Arrival time (AT) (I. KEY TERMS)

Time that process arrived in CPU

Waiting time (WT) (I. KEY TERMS)

How long process has waited to start executing

Burst time (BT) (I. KEY TERMS)

Time for process to finish

II. TYPES OF SCHEDULING ALGORITHMS

Types of scheduling algorithms/approaches

Preemptive (II. TYPES)

Can stop a process that is currently running

Nonpreemptive (II. TYPES)

Have to wait for process to finish loading before removing

III. SCHEDULING ALGORITHMS

Different approaches for scheduling

First come first serve (FCFS) (III. ALGORITHMS)

Processes execute in order they arrive

- NONPREEMPTIVE

FCFS Advantages (III. ALGORITHMS)

- Simple = easy to implement

- Fair (processes in order of AT)

FCFS Disadvantages (III. ALGORITHMS)

- Convoy effect - short processes delayed by long-running processes

.=^ WT, v system throughput (also caused by non-preemptive nature)

Round robin (III. ALGORITHMS)

Each process assigned quantum (fixed time slice) to execute

- PREEMPTIVE

- Quantum expires = preempts/remove process and placed at end of queue, goes to next process

Round robin advantages (III. ALGORITHMS)

- Fair allocation of CPU time among processes

- ^ responsiveness = ^ system interactivity/user experience

- prevents a process from monopolizing resources

Round robin disadvantages (III. ALGORITHMS)

- Too small quantum = ^ context-switch overhead (switching things over and over, saving and loading process states)

- Too big quantum = processes usually complete all tasks at once = potential inefficiency

Priority scheduling (III. ALGORITHMS)

Assign priority level to each process, CPU to highest priority

- Can be either non/preemptive

- Same priority = follow FCFS

- Goal: critical tasks executed asap

Priority scheduling advantages (III. ALGORITHMS)

- Prioritize important tasks = ^ system responsivness

- Flexible: priorities can be adjusted based on system needs

Priority scheduling disadvantages (III. ALGORITHMS)

- High-priority tasks dominate CPU time = starvation for low-priority processes

- More complex to implement and manage

- Priority inversion - lower priority must process for higher priority to go = deadlock

Multilevel queue scheduling (hybrid) (III. ALGORITHMS)

Separates into several separate queues each with own scheduling algorithm and priority level

- Processes permanently assigned to queue based on characteristics (process type, priority, memory requirements, etc)

- Queues themselves scheduled in specific order, usually priority

Multilevel queue scheduling (hybrid) advantages (III. ALGORITHMS)

- Flexible for different types of processes

- Prioritizes critical and interactive processes = ^ responsiveness

- Each queue has own scheduling algorithm that works best of rit

Multilevel queue scheduling (hybrid) disadvantages (III. ALGORITHMS)

- High-priority queues frequently occupied = starvation for low-priority processes

- Complex to implement and manage

- Processes are permanently assigned: unoptimal if behaviour changes over time