ECM 1413 Scheduling Flashcards
Shortest Job First (SJF)
- Select the process with the shortest execution time
- Non-preemptive - Preemptive (Shortest Remaining time
Pros and cons of SJF
+Better average waiting time
+responsiveness
-estimating process execution time
-May lead to starvation (a long process that doesn’t get executed for an extended period of time as many shorter processes go first)
Round Robin
- Time-sliced FIFO execution
- Preemptive
Pros and cons of Round Robin
+Fair CPU allocation
+Responsiveness
+No Starvation
-Time Quantum Sensitivity
-Context Switch overhead
First Come First Serve
- FIFO - processes get executed in the order they arrive
- Non-preemptive - Not interrupted until finishes or reaches a wait state
Pros and Cons of FCFS
+Simple and easy to implement
+reduced context switching
+Intuitively fair
+no starvation
-Convoy effect (poor responsiveness, long average wait times)
Multi-level queuing
Mapping processes to queues
Fixed Priority Scheduling
- High priority queues are executed first
- May lead to starvation
Time slicing
- A time slice for each queue
- e.g: 60% for interactive, 30% system, 10% batch
Pros and cons of Multi-level feedback queues
+Supports different performance objectives
-Difficult to calibrate and complex
Scheduling criteria
- User-oriented
○ Turnaround time
○ Response time - System-oriented
○ Throughput
○ Processor utilization
Multi core processors
- Has multiple processing units on a single cpu chip
- Each with its own l1 cache unit
- There is a cache hierarchy
For efficient multi-processor scheduling:
Load balancing
Processor affinity
Load balancing
Evenly distribute processes among cpu cores. Common ready queues automatically enforce load balancing
Processor Affinity
Keep a process on the same CPU core(s)
○ Soft affinity: only processes move if there is a good reason
○ Private queues automatically enforce processor affinity
○ Process data saved on the cache, so it must stay on that core
The Linux scheduler
The linux scheduler is multi-queue (there are also private queues)
Bottom up load balancing among domains
Processor affinity - only perform load balancing if three are severe imbalances
Scheduling domain
A set of cpu cores that can be balanced against each other
How does the Linux scheduler group processor cores for scheduling?
Aggregate a set of CPU cores into one scheduling domain
In which order does the Linux Scheduler perform load balancing across scheduling domains?
Load balancing is first performed in the smallest scheduling domains, then in successively larger domains
What is the Linux scheduler’s approach to balancing load balancing and processor affinity/
Load balancing is enforced only when imbalances between cpu groups are severe (soft affinity)
