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
