What three general types of scheduling algorithms exist?
• Single-tasking (early Batch systems)
selects one single activity, therefore, one scheduling interval, contains one activity scheduler decides, which activity will be processed next
• Multi-tasking
several activities executed in one scheduling interval
Preemptive
Scheduling OS interrupts running processes to switch
Non-preemptive Scheduling (cooperative)
program that has started won’t be interrupted until completion
− non-preemptive (multiprogrammed Batch systems) − Preemptive (time-slicing)
• Real-time algorithm
Every activity has a starting point and a scheduled time at which results must be done (deadline)
Hard Real-Time
miss causes intolerable damage therefore, avoid/report
Soft Real-Time
deadline misses deadline miss causes penalty therefore, avoid too many penalties
What are the goals of sequencing optimization?
Fairness, Priority assignment, equitable allocation of resources, response time, average waiting time, throughput, processor utilization, predicability, compliance with deadlines, expectation conformity
What is the Single Tasking FCFS algorithm?
How does the Single Tasking SJF algorithm work?
Starvation Risk!
What non-preemptive multi tasking scheduling algorithms do you know?
FCFS, SJF
What preemptive scheduling algorithms for multi task sequencing do you know?
Non-preemptive scheduling!
A program that has been started will not be interrupted until completion.
Preemptive scheduling!
The OS interrupts running processes and switches between them.
Shortest Remaining Time First (SRTF)
Round Robin (load balancing)
Time slots are assigned to each activity in equal portions
Time slots are assigned in circular order and new activities are added to the directly following slot
Blocked activities which get ready are considered new
What other Round Robin versions exist (next to load balancing)?
Preemptive – Round Robin (with Priority)
Frequency-Based Priority: Priority determines how often a process gets a time slot.
Higher priority ➔ more frequent access to the CPU.
Time Slot-Based Priority: Priority determines the length of the time slot a process receives.
Higher priority ➔ longer time slices per execution
What scheduling algorithms exist for Real-Time Operations?
Rate Monotonic Scheduling (RMS)
Used in preemptive periodic systems.
Higher-priority tasks (with shorter periods) can preempt lower-priority tasks.
Priority is fixed, based on the task's period—shorter period ➔ higher priority.
Earliest Deadline First (EDF) / Shortest Deadline First (SDF)
Dynamic scheduling method, suitable for aperiodic tasks or tasks with changing execution times.
The task with the closest deadline is executed first, without interruption (unless a new task with an even earlier deadline arrives).
Priorities are dynamic, based on absolute deadlines.
Last changeda month ago
