Advanced Scheduling
Advanced Scheduling¶
Overview¶
In this lesson, we learn about advanced scheduling techniques used in real operating systems. We explore MLFQ (Multi-Level Feedback Queue), multiprocessor scheduling, and real-time scheduling.
Table of Contents¶
- MLFQ (Multi-Level Feedback Queue)
- Multiprocessor Scheduling
- Processor Affinity
- Real-time Scheduling
- Linux CFS
- Practice Problems
1. MLFQ (Multi-Level Feedback Queue)¶
Concept¶
MLFQ = Scheduling using multiple ready queues
= Move between queues based on process behavior
= Advantages of SJF + Adaptive scheduling
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β MLFQ Structure β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β High Priority (Short Time Quantum) β
β βββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Queue 0 (TQ=8ms): P1 β P5 β ... β βββ New Process
β βββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β
β βΌ Demote on TQ expiration β
β βββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Queue 1 (TQ=16ms): P2 β P7 β ... β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β
β βΌ Demote on TQ expiration β
β βββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Queue 2 (TQ=32ms): P3 β P8 β ... β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β
β βΌ β
β βββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Queue N (FCFS): P4 β P6 β ... β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββ β
β Low Priority (Long Time Quantum or FCFS) β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
MLFQ Rules¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β MLFQ Basic Rules β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Rule 1: Execute higher priority process first β
β Priority(A) > Priority(B) β Execute A β
β β
β Rule 2: If same priority, use RR β
β Priority(A) = Priority(B) β RR β
β β
β Rule 3: Place new process in highest queue β
β New process β Queue 0 β
β β
β Rule 4: If time quantum is used up, demote β
β TQ exhausted β Priority decreased β
β β
β Rule 5: If CPU is yielded before TQ, maintain queue β
β I/O request etc β Maintain same priority β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
MLFQ Operation Example¶
Scenario: Mix of long job (CPU-bound) and short job (I/O-bound)
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Time 0: Long job A arrives β
β β
β Q0: [A] ββββΆ Execute A (8ms) β
β Q1: [] β
β Q2: [] β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β Time 8: A exhausts TQ β Demoted β
β β
β Q0: [] β
β Q1: [A] ββββΆ Execute A (16ms) β
β Q2: [] β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β Time 10: Short job B arrives (5ms job) β
β β
β Q0: [B] ββββΆ B has higher priority, preempt A β
β Q1: [A] Start executing B β
β Q2: [] β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β Time 15: B completes (finished before TQ β I/O-heavy) β
β β
β Q0: [] β
β Q1: [A] ββββΆ Resume A β
β Q2: [] β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Result: Short job completes first (similar effect to SJF)
Can prioritize short jobs without knowing burst time
MLFQ Problems and Solutions¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β MLFQ Problems and Solutions β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Problem 1: Starvation β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β If high priority jobs keep arriving, β β
β β low queue jobs never execute β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β Solution: Priority Boost β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Periodically move all processes to top queue β β
β β E.g., every S time units, all jobs to Q0 β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β Problem 2: Gaming the Scheduler β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Malicious process requests I/O just before TQ β β
β β β Prevents demotion, monopolizes CPU β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β Solution: Track cumulative time β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Track total time used at each level β β
β β Demote when allotment exhausted (even if split) β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
MLFQ Parameters¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β MLFQ Key Parameters β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β 1. Number of queues β
β β’ Typically 3~5 β
β β’ Too many: overhead, too few: insufficient β
β β
β 2. Time Quantum per queue β
β β’ Usually doubles (8, 16, 32, 64ms...) β
β β’ High queue: Short TQ (fast response) β
β β’ Low queue: Long TQ (reduce context switches) β
β β
β 3. Priority Boost period (S) β
β β’ Too short: CPU-bound jobs advantaged β
β β’ Too long: starvation occurs β
β β’ Typically 1 second ~ 100ms β
β β
β Solaris Time-sharing class example: β
β βββββββββββ¬βββββββ¬βββββββββββ¬ββββββββββββββ β
β β Priorityβ TQ β Demote β Promote β β
β βββββββββββΌβββββββΌβββββββββββΌββββββββββββββ€ β
β β 59 β 20ms β 54 β - β β
β β 40 β 40ms β 35 β 45 β β
β β 20 β 80ms β 15 β 25 β β
β β 0 β 200msβ 0 β 5 β β
β βββββββββββ΄βββββββ΄βββββββββββ΄ββββββββββββββ β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
2. Multiprocessor Scheduling¶
Multiprocessor System Types¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Multiprocessor System Types β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β 1. SMP (Symmetric Multi-Processing) β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β βββββββ βββββββ βββββββ βββββββ β β
β β βCPU 0β βCPU 1β βCPU 2β βCPU 3β β β
β β ββββ¬βββ ββββ¬βββ ββββ¬βββ ββββ¬βββ β β
β β βββββββββ΄ββββββββ΄ββββββββ β β
β β β β β
β β ββββββββ΄βββββββ β β
β β βShared Memoryβ β β
β β βββββββββββββββ β β
β β All processors equal, share memory β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β 2. NUMA (Non-Uniform Memory Access) β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β βββββββββββββββ βββββββββββββββ β β
β β β CPU 0, 1 β β CPU 2, 3 β β β
β β βLocal Memory ββββββΆβLocal Memory β β β
β β βββββββββββββββ βββββββββββββββ β β
β β β β
β β Local memory access: Fast β β
β β Remote memory access: Slow β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Scheduling Approaches¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Multiprocessor Scheduling Approaches β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β 1. Asymmetric Multiprocessing β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β βββββββββββββββββββ β β
β β β Master Processorβ β All scheduling decisions β β
β β β (CPU 0) β β β
β β ββββββββββ¬βββββββββ β β
β β β Assign tasks β β
β β βββββββΌββββββ¬ββββββ β β
β β βΌ βΌ βΌ βΌ β β
β β ββββββββββββββββββββββββββββ β β
β β βCPU 1ββCPU 2ββCPU 3ββCPU 4β β Slaves β β
β β ββββββββββββββββββββββββββββ β β
β β β β
β β Pros: Simple, no data sharing issues β β
β β Cons: Master bottleneck β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β 2. Symmetric Multiprocessing (SMP) β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β βββββββ βββββββ βββββββ βββββββ β β
β β βCPU 0β βCPU 1β βCPU 2β βCPU 3β β β
β β βSchedββSchedββSchedββSchedβ β β
β β ββββ¬βββ ββββ¬βββ ββββ¬βββ ββββ¬βββ β β
β β βββββββββ΄ββββ¬ββββ΄ββββββββ β β
β β βΌ β β
β β ββββββββββββββββ β β
β β β Shared Ready β (sync required) β β
β β β Queue β β β
β β ββββββββββββββββ β β
β β Or: Each CPU maintains own Ready Queue β β
β β β β
β β Pros: Scalability, no bottleneck β β
β β Cons: Complex sync, possible load imbalance β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Load Balancing¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Load Balancing Techniques β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Problem: Load imbalance when each CPU has own queue β
β β
β CPU 0: ββββββββ CPU 1: ββ CPU 2: ββββββββββββ β
β (overload) (idle) (overload) β
β β
β Solution 1: Push Migration β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Periodically check each queue's load β β
β β Move processes from overloaded β idle queue β β
β β β β
β β CPU 0: ββββββββ ββpushβββΆ CPU 1: ββ β β
β β Result: βββββ βββββ β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β Solution 2: Pull Migration β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Idle CPU pulls tasks from other CPUs β β
β β β β
β β CPU 0: ββββββββ βββpullββ CPU 1: (idle) β β
β β Result: βββββ βββ β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β Linux: Uses both β
β β’ Periodic Push (rebalance task) β
β β’ Pull on idle (idle_balance) β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
3. Processor Affinity¶
What is Processor Affinity?¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Processor Affinity β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Definition: Keeping process running on same CPU β
β β
β Reason: Cache efficiency β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Process P runs on CPU 0 β β
β β β CPU 0's cache loaded with P's data β β
β β β β
β β If P moves to different CPU: β β
β β β’ CPU 0 cache: P data invalidated β β
β β β’ CPU 1 cache: P data needs reloading β β
β β β Cache misses increase, performance degrades β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β Cache state visualization: β
β β
β CPU 0 CPU 1 CPU 0 CPU 1 β
β βββββββ βββββββ βββββββ βββββββ β
β βCacheβ βCacheβ βCacheβ βCacheβ β
β β[P's β β[ ]β Move β[ ]β β[P's β β
β βdata]β β β ββββΆ β β βdata]β β
β βββββββ βββββββ βββββββ βββββββ β
β β Warm Cold Cold β Reload β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Affinity Types¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Affinity Types β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β 1. Soft Affinity β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β’ Default: Try to run on same CPU β β
β β β’ Can move if load balancing needed β β
β β β’ Linux default behavior β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β 2. Hard Affinity β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β’ Pin process to specific CPU set β β
β β β’ Won't move even for load balancing β β
β β β’ Set via system call β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β Linux configuration: β
β ```c β
β #define _GNU_SOURCE β
β #include <sched.h> β
β β
β cpu_set_t mask; β
β CPU_ZERO(&mask); β
β CPU_SET(0, &mask); // Run only on CPU 0 β
β CPU_SET(2, &mask); // Also can run on CPU 2 β
β β
β // Set affinity for current process β
β sched_setaffinity(0, sizeof(mask), &mask); β
β ``` β
β β
β Commands: β
β ```bash β
β # Run only on CPU 0,1 β
β taskset -c 0,1 ./program β
β β
β # Change affinity of running process β
β taskset -c 2,3 -p PID β
β ``` β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
4. Real-time Scheduling¶
Real-time System Overview¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Real-time System Overview β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Real-time System = System with time constraints β
β (Deadlines) β
β β
β Classification: β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Hard Real-Time β β
β β β’ Deadline miss = System failure β β
β β β’ Ex: Aviation control, medical devices, ABS brakeβ β
β β β’ Deadline guarantee essential β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Soft Real-Time β β
β β β’ Deadline miss = Performance degradation β β
β β β’ Ex: Video streaming, games, VoIP β β
β β β’ Goal: Meet most deadlines β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Real-time Task Characteristics¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Real-time Task Characteristics β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Periodic Task: β
β β
β Time βββββββββββββββββββββββββββββββββββββββββββββΆ β
β ββββ Period P βββββββ Period P ββββ β
β βββββ βββββ βββββ β
β β C β β C β β C β β
β βββββ βββββ βββββ β
β β β β β β
β Arrive Deadline(D) Arrive Deadline(D) β
β β
β Parameters: β
β β’ P (Period): Task repetition period β
β β’ C (Computation time): Execution time β
β β’ D (Deadline): Completion deadline β
β β’ Utilization U = C/P β
β β
β Example: Video frame β
β β’ P = 33ms (30fps) β
β β’ C = 10ms (frame processing time) β
β β’ D = 33ms β
β β’ U = 10/33 β 0.3 (30%) β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Rate Monotonic Scheduling (RMS)¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Rate Monotonic Scheduling (RMS) β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Principle: Shorter period = Higher priority β
β (Rate = 1/Period, higher Rate = higher priority) β
β β
β Characteristics: β
β β’ Static priority (fixed) β
β β’ Preemptive β
β β’ Optimal (among static priority) β
β β
β Example: β
β βββββββββββ¬ββββββββ¬βββββββββ¬βββββββββββ β
β β Task βPeriod βComp. C β Priority β β
β βββββββββββΌββββββββΌβββββββββΌβββββββββββ€ β
β β T1 β 50 β 20 β High β β
β β T2 β 100 β 35 β Low β β
β βββββββββββ΄ββββββββ΄βββββββββ΄βββββββββββ β
β β
β Gantt Chart: β
β ββββββββββββ¬βββββββββββββββ¬βββββββββββ¬ββββββββββββββ β
β β T1 β T2 β T1 β T2(cont.) β β
β ββββββββββββ΄βββββββββββββββ΄βββββββββββ΄ββββββββββββββ β
β 0 20 55 75 100 β
β T2 starts T1 arrives(preempt) T2 resumes β
β β
β Schedulability condition: β
β Total utilization β€ n(2^(1/n) - 1) β
β β’ n=1: 100% β
β β’ n=2: ~82.8% β
β β’ nββ: ~69.3% β
β β
β Example: U = 20/50 + 35/100 = 0.4 + 0.35 = 0.75 β
β 0.75 < 0.828 β Schedulable β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Earliest Deadline First (EDF)¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Earliest Deadline First (EDF) β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Principle: Nearest deadline = Highest priority β
β β
β Characteristics: β
β β’ Dynamic priority (changes with deadline) β
β β’ Preemptive β
β β’ Theoretically optimal (up to 100% utilization) β
β β
β Example (same data as RMS): β
β βββββββββββ¬ββββββββ¬βββββββββ¬βββββββββββββββββ β
β β Task βPeriod βComp. C β Deadline D β β
β βββββββββββΌββββββββΌβββββββββΌβββββββββββββββββ€ β
β β T1 β 50 β 20 β 50, 100, 150...β β
β β T2 β 100 β 35 β 100, 200... β β
β βββββββββββ΄ββββββββ΄βββββββββ΄βββββββββββββββββ β
β β
β Time 0: β
β β’ T1 deadline: 50, T2 deadline: 100 β
β β’ Execute T1 first β
β β
β Time 50 (T1 second instance): β
β β’ T1 deadline: 100, T2 deadline: 100 (tied) β
β β’ Tie β Arbitrary selection or other criteria β
β β
β RMS vs EDF: β
β ββββββββββββββββ¬βββββββββββββββββ¬ββββββββββββββββββ β
β β Feature β RMS β EDF β β
β ββββββββββββββββΌβββββββββββββββββΌββββββββββββββββββ€ β
β β Priority β Static β Dynamic β β
β β Max Util. β ~69% (nββ) β 100% β β
β β Complexity β Low β High β β
β β Overhead β Low β High β β
β β Overload β Predictable β Domino effect β β
β ββββββββββββββββ΄βββββββββββββββββ΄ββββββββββββββββββ β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
5. Linux CFS¶
CFS Overview¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β CFS (Completely Fair Scheduler) β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Linux default scheduler since 2.6.23 (2007~) β
β β
β Core idea: β
β β’ Fairly distribute CPU time to all processes β
β β’ Track fairness via virtual runtime β
β β’ Efficiently manage with Red-Black tree β
β β
β Virtual runtime (vruntime): β
β β’ Weighted time process has used CPU β
β β’ High priority β increases slowly β
β β’ Low priority β increases quickly β
β β
β Scheduling decision: β
β β’ Always select process with smallest vruntime β
β β’ = Process that has run least β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
CFS Operation¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β CFS Operation β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Red-Black tree (sorted by vruntime): β
β β
β βββββββββ β
β β P2:50 β β
β βββββ¬ββββ β
β βββββββββββ΄ββββββββββ β
β βββββββββ βββββββββ β
β β P1:30 β β P3:80 β β
β βββββ¬ββββ βββββ¬ββββ β
β βββββββ΄ββββββ βββββββ΄ββββββ β
β βββββββββ βββββββββ βββββββββ βββββββββ β
β β P4:10 β β P5:40 β β P6:70 β β P7:100β β
β βββββββββ βββββββββ βββββββββ βββββββββ β
β β β
β Leftmost = Smallest vruntime = Next to execute β
β β
β Over time: β
β 1. Execute P4, vruntime increases (10 β 25) β
β 2. If P4 no longer minimum, switch to another process β
β 3. Restructure tree, select new minimum β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
CFS Timeslice Calculation¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β CFS Timeslice Calculation β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β CFS uses target latency instead of fixed timeslice β
β β
β Target Latency: Default 6ms (adjustable) β
β β
β Calculation: β
β Process timeslice = Target latency Γ (weight/total) β
β β
β Example (n=3, same priority): β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Target latency = 6ms β β
β β Each process weight = 1024 (nice 0) β β
β β Total weight = 1024 Γ 3 = 3072 β β
β β β β
β β Each timeslice = 6ms Γ (1024/3072) = 2ms β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β Example (different priorities): β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β P1: nice -5 (weight 3121) β β
β β P2: nice 0 (weight 1024) β β
β β P3: nice 5 (weight 335) β β
β β Total weight = 4480 β β
β β β β
β β P1 timeslice = 6ms Γ (3121/4480) β 4.2ms β β
β β P2 timeslice = 6ms Γ (1024/4480) β 1.4ms β β
β β P3 timeslice = 6ms Γ (335/4480) β 0.4ms β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β Nice value and weight: β
β β’ nice -20 (highest): weight 88761 β
β β’ nice 0 (default): weight 1024 β
β β’ nice 19 (lowest): weight 15 β
β β’ ~10% difference per nice 1 difference β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
6. Practice Problems¶
Problem 1: MLFQ¶
In an MLFQ system with 3 queues: - Q0: TQ=4ms - Q1: TQ=8ms - Q2: FCFS
Explain the execution for the first 20ms when process A (CPU-bound, 30ms job) and process B (I/O-bound, 3ms CPU + I/O repeat) arrive simultaneously.
View Answer
**Initial state:** - Q0: [A, B] - Q1: [] - Q2: [] **Time 0-3ms:** B executes (3ms), I/O request β B stays in Q0 **Time 3-7ms:** A executes (4ms), TQ exhausted β A demoted to Q1 **Time 7-10ms:** B completes I/O and arrives, B executes (3ms) **Time 10-18ms:** A executes (8ms), TQ exhausted β A demoted to Q2 **Time 18-20ms:** If B returned, B executes... **Result:** - B, being a short job, gets quick service in high queue - A gradually moves to lower queues using long timesliceProblem 2: RMS Schedulability¶
Check if the following task set is schedulable with RMS.
| Task | Period (P) | Execution Time (C) |
|---|---|---|
| T1 | 100 | 20 |
| T2 | 150 | 30 |
| T3 | 350 | 80 |
View Answer
**Total Utilization Calculation:** - U1 = 20/100 = 0.20 - U2 = 30/150 = 0.20 - U3 = 80/350 = 0.23 **Total U = 0.20 + 0.20 + 0.23 = 0.63** **RMS Schedulability Condition (n=3):** - Bound = 3 Γ (2^(1/3) - 1) = 3 Γ 0.26 = 0.78 **Conclusion:** - 0.63 < 0.78 - **Schedulable**Problem 3: Processor Affinity¶
Explain the difference between soft affinity and hard affinity, and provide examples of situations suitable for each.
View Answer
**Soft Affinity:** - Definition: OS tries to run process on same CPU, but can move if load balancing needed - Suitable situations: - General applications - When balance between cache efficiency and load balancing needed - Ex: Web servers, databases **Hard Affinity:** - Definition: Force process to run only on specific CPU set - Suitable situations: - Real-time systems (need predictable performance) - NUMA systems optimizing local memory access - Dedicated CPU core allocation - Ex: Game server physics engine thread, high-frequency trading systemsProblem 4: EDF vs RMS¶
Compare RMS and EDF for the following task set.
| Task | Period | Execution Time |
|---|---|---|
| T1 | 4 | 1 |
| T2 | 5 | 2 |
| T3 | 10 | 3 |
View Answer
**Utilization:** - U = 1/4 + 2/5 + 3/10 = 0.25 + 0.4 + 0.3 = 0.95 **RMS Analysis:** - Bound = 3 Γ (2^(1/3) - 1) β 0.78 - 0.95 > 0.78 β Not guaranteed by RMS - (May actually be schedulable but not guaranteed) **EDF Analysis:** - Bound = 1.0 (100%) - 0.95 < 1.0 β Schedulable with EDF! **Conclusion:** - This task set is not guaranteed schedulable by RMS - But schedulable with EDFProblem 5: Linux CFS¶
When process A has nice value 0 and process B has nice value 5, calculate how much more CPU time A receives compared to B.
View Answer
**Weights (approximate):** - nice 0: weight 1024 - nice 5: weight ~335 (~1.25x per nice 1 difference) **CPU Time Ratio:** - A's ratio = 1024 / (1024 + 335) = 1024 / 1359 β 0.753 (75.3%) - B's ratio = 335 / 1359 β 0.247 (24.7%) **A receives about 3 times more CPU time than B** (Exact ratio: 1024/335 β 3.06x)Next Steps¶
- 07_Synchronization_Basics.md - Race Conditions and Critical Sections