📝 Earliest Deadline First Scheduling in Real Time CPU Scheduling (49 MCQs)

📖 From Operating System • 6. CPU Scheduling • 49 questions available

←Previous Topic:Rate Monotonic Scheduling in Real Time CPU Scheduling📝 Earliest Deadline First Scheduling in Real Time CPU SchedulingProportional Share Scheduling in Real Time CPU Scheduling:Next Topic→

What is Earliest Deadline First Scheduling in Real Time CPU Scheduling?

Definition:
EDF is a dynamic-priority algorithm that always schedules the task with the earliest absolute deadline $d_i$ , achieving 100% utilization bound $U \leq 1$ for preemptive uniprocessor systems.

Example:
At time t=5, Task A (deadline=12) and Task B (deadline=8) are ready; EDF runs B first regardless of period or static priority since 8 < 12.

Reason:
EDF is theoretically optimal for uniprocessor real-time scheduling, accepting any feasible task set, though runtime overhead and lack of graceful overload degradation limit practical adoption versus RMS.

Easy

Medium

Hard

📝 All Earliest Deadline First Scheduling in Real Time CPU Scheduling MCQs

Q1. What type of priority assignment does Earliest-Deadline-First (EDF) scheduling use?

A.Static priority assignment

B.Dynamic priority assignment ✅

C.Random priority assignment

D.Fixed priority assignment

💡 Difficulty: easy | ✅ Correct: B

📖 Explanation: EDF uses dynamic priority assignment. This means that priorities are not fixed but change over time based on the deadlines of the processes. The process with the earliest deadline is given the highest priority at any given moment.

Q2. In EDF scheduling, how is priority assigned to a process?

A.Priority is inversely proportional to its period

B.Priority is based on its processing time

C.Priority is based on its deadline (earlier deadline = higher priority) ✅

D.Priority is based on its arrival time

💡 Difficulty: easy | ✅ Correct: C

📖 Explanation: The core rule of EDF is simple: the earlier the deadline, the higher the priority. This ensures that the most urgent tasks, those with the closest deadlines, are executed first to minimize the chance of missing deadlines.

Q3. What is the primary difference between EDF and rate-monotonic scheduling?

A.EDF is for periodic tasks only

B.EDF uses dynamic priorities, while RMS uses static priorities ✅

C.EDF is non-preemptive

D.EDF assigns priorities based on periods

💡 Difficulty: easy | ✅ Correct: B

📖 Explanation: The key difference is in priority assignment. RMS uses static priorities that are fixed and based on periods. EDF uses dynamic priorities that change based on the deadlines of the processes, making it more flexible for varying workloads.

Q4. In EDF scheduling, when must a process announce its deadline requirements?

A.At system boot time

B.When it is created

C.When it becomes runnable ✅

D.When it completes execution

💡 Difficulty: easy | ✅ Correct: C

📖 Explanation: For EDF to work, a process must announce its deadline to the scheduler when it becomes runnable. This allows the scheduler to dynamically adjust priorities and ensure the process with the most urgent deadline gets the CPU first.

Q5. What is a key requirement for EDF scheduling regarding processes?

A.Processes must be periodic

B.Processes must have constant CPU burst times

C.Processes must announce their deadlines when runnable ✅

D.Processes must have the same priority

💡 Difficulty: easy | ✅ Correct: C

📖 Explanation: Unlike RMS, EDF does not require processes to be periodic or to have constant CPU burst times. The only requirement is that a process announces its deadline when it becomes runnable, allowing the scheduler to make dynamic priority decisions.

Q6. What is the theoretical CPU utilization that EDF scheduling can achieve?

A.0.69

B.0.83

C.1 ✅

D.0.5

💡 Difficulty: easy | ✅ Correct: C

📖 Explanation: EDF is theoretically optimal and can achieve 100% CPU utilization. This means that, in theory, it can schedule a set of tasks such that all deadlines are met while using the CPU to its full capacity, leaving no idle time.

Q7. Why is 100% CPU utilization impossible to achieve in practice with EDF?

A.Because the algorithm is not optimal

B.Because of context switching and interrupt handling overhead ✅

C.Because tasks cannot be periodic

D.Because dynamic priorities are too complex

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: While EDF is theoretically optimal, real-world overheads make 100% utilization impossible. Context switching between processes and interrupt handling consume CPU cycles that are not available for useful work, reducing the effective utilization that can be achieved.

Q8. In the EDF example with P1(p=50, t=25) and P2(p=80, t=35), at what time does P2 begin running initially?

A.Time 0

B.Time 25 ✅

C.Time 50

D.Time 60

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: P1 has the earliest deadline initially and runs first, completing its burst at time 25. After P1 completes, P2 begins running at time 25. This demonstrates how EDF prioritizes the task with the earliest absolute deadline.

Q9. In the EDF example, why is P2 allowed to continue running at time 50, whereas in RMS it is preempted?

A.Because P2 has a higher priority in EDF

B.Because P2's deadline (80) is earlier than P1's next deadline (100) ✅

C.Because P1 has completed its work

D.Because EDF is non-preemptive

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: At time 50, P1's next period begins, but its deadline is at 100. P2's deadline is at 80, which is earlier. In EDF, the process with the earlier deadline (P2) gets higher priority, so P1 is not allowed to preempt P2. This dynamic priority adjustment is the key difference from RMS.

Q10. At what time does P1 complete its second CPU burst in the EDF example?

A.Time 50

B.Time 60

C.Time 85 ✅

D.Time 125

💡 Difficulty: medium | ✅ Correct: C

📖 Explanation: P1 starts its second burst at time 60 (after P2 completes at 60). It requires 25ms, so it completes at time 85. This meets its second deadline at time 100, demonstrating how EDF successfully schedules tasks that RMS could not guarantee.

Q11. At what time does P2 complete its first CPU burst in the EDF example?

A.Time 35

B.Time 60 ✅

C.Time 80

D.Time 145

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: P2 runs from time 25 to 60, which is a total of 35ms. This matches its required burst time. By completing at time 60, P2 meets its first deadline at time 80, showing how EDF successfully handles the task set that caused RMS to fail.

Q12. What is the deadline of P1's second period in the EDF example?

A.Time 50

B.Time 80

C.Time 100 ✅

D.Time 150

💡 Difficulty: medium | ✅ Correct: C

📖 Explanation: P1 has a period of 50ms. Its first period starts at time 0 and ends at time 50. Its second period starts at time 50 and ends at time 100. Therefore, the deadline for P1's second CPU burst is at time 100. This is the absolute deadline that must be met.

Q13. What is the deadline of P2's first period in the EDF example?

A.Time 50

B.Time 80 ✅

C.Time 100

D.Time 160

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: P2 has a period of 80ms. Its first period starts at time 0 and ends at time 80. Therefore, the deadline for P2's first CPU burst is at time 80. This earlier deadline (compared to P1's at 100) is what gives P2 higher priority at time 50.

Q14. What happens at time 100 in the EDF example?

A.P2 is preempted by P1 ✅

B.P1 is preempted by P2

C.The system goes idle

D.Both processes miss their deadlines

💡 Difficulty: hard | ✅ Correct: A

📖 Explanation: At time 100, a new period of P1 begins. Its deadline is at time 150. P2 is currently running and its next deadline is at time 160. Since P1 has an earlier deadline (150 vs 160), it has higher priority and preempts P2. This demonstrates how priorities change dynamically.

Q15. What is the state of P2 at time 100 in the EDF example?

A.It has completed its burst

B.It is preempted with some time remaining ✅

C.It is about to start its burst

D.It has missed its deadline

💡 Difficulty: hard | ✅ Correct: B

📖 Explanation: At time 100, P2 has been running but is preempted by P1. P2's next deadline is at 160, and it requires more CPU time to complete. Since P1's deadline (150) is earlier, P1 gets priority, and P2 is preempted with remaining CPU time to be completed later.

Q16. At what time does P2 resume execution after being preempted at time 100?

A.Time 85

B.Time 125 ✅

C.Time 145

D.Time 150

💡 Difficulty: hard | ✅ Correct: B

📖 Explanation: P2 is preempted at time 100 by P1. P1 runs from time 100 to 125 (its required 25ms burst). At time 125, P1 completes, and P2 resumes execution. This demonstrates how EDF switches between tasks based on the relative urgency of their deadlines.

Q17. At what time does P2 complete its CPU burst after resuming at time 125?

A.Time 130

B.Time 135

C.Time 140

D.Time 145 ✅

💡 Difficulty: hard | ✅ Correct: D

📖 Explanation: P2 resumes at time 125. It needs to complete its CPU burst. From the example, it runs from 125 to 145, which is 20ms, finishing its required work. It then meets its deadline at time 160, demonstrating successful completion.

Q18. When is the system idle in the EDF example?

A.From time 75 to 100

B.From time 60 to 100

C.From time 85 to 100

D.From time 145 to 150 ✅

💡 Difficulty: hard | ✅ Correct: D

📖 Explanation: After P2 completes its burst at time 145, the system has no pending tasks until time 150, when P1's next period begins. From 145 to 150, the CPU is idle. This idle time represents spare capacity in the system.

Q19. What is the deadline of P1's third period in the EDF example?

A.Time 100

B.Time 150 ✅

C.Time 160

D.Time 200

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: P1's periods are at 0-50, 50-100, and 100-150. Therefore, the deadline for P1's third CPU burst is at time 150. This is the absolute deadline that P1 must meet for its third execution. The example shows that P1 meets this deadline.

Q20. What is the deadline of P2's second period in the EDF example?

A.Time 80

B.Time 100

C.Time 160 ✅

D.Time 240

💡 Difficulty: medium | ✅ Correct: C

📖 Explanation: P2's periods are at 0-80, and 80-160. Therefore, the deadline for P2's second CPU burst is at time 160. This is later than P1's third deadline at 150, which is why P1 preempts P2 at time 100.

Q21. What is the significance of the example where EDF succeeds and RMS fails?

A.EDF is always better than RMS

B.EDF can schedule tasks with higher utilization than RMS ✅

C.RMS is not a valid scheduling algorithm

D.EDF is simpler to implement

💡 Difficulty: hard | ✅ Correct: B

📖 Explanation: The example demonstrates that EDF can schedule a task set with 94% utilization, while RMS cannot guarantee schedulability for the same task set. This highlights EDF's advantage in being able to handle higher CPU utilizations compared to static priority algorithms like RMS.

Q22. What is the main appeal of EDF scheduling?

A.It is simple to implement in hardware

B.It is theoretically optimal ✅

C.It requires no context switching

D.It can schedule any number of processes

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: The main appeal of EDF is its theoretical optimality. This means that if any algorithm can schedule a set of tasks to meet all deadlines, then EDF can also do so. This property makes it a very attractive scheduling algorithm for real-time systems.

Q23. What is the practical limitation of EDF's theoretical optimality?

A.The algorithm is too complex to implement

B.Context switching and interrupt handling reduce achievable utilization ✅

C.EDF cannot handle periodic tasks

D.EDF requires too much memory

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: While EDF is theoretically optimal and can achieve 100% utilization, practical overheads like context switching between processes and interrupt handling consume CPU cycles. These overheads mean that 100% utilization is not achievable in practice, though EDF remains a very efficient algorithm.

Q24. In EDF scheduling, what happens to priorities when a new process becomes runnable?

A.Priorities remain unchanged

B.Priorities may be adjusted to reflect the new process's deadline ✅

C.All priorities are reset

D.The new process is given the lowest priority

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: Since EDF is dynamic, when a new process becomes runnable, the scheduler may need to adjust priorities. If the new process has an earlier deadline, it will be given a higher priority, potentially causing a preemption. This ensures the system always executes the most urgent task.

Q25. What is required of a process in EDF that is not required in RMS?

A.The process must be periodic

B.The process must have a constant burst time

C.The process must announce its deadline when runnable ✅

D.The process must have a fixed priority

💡 Difficulty: hard | ✅ Correct: C

📖 Explanation: RMS requires processes to be periodic and have constant burst times. EDF does not require either of these; it only requires that a process announces its deadline when it becomes runnable. This makes EDF more flexible and applicable to a wider range of real-time tasks.

Q26. What is the absolute deadline for P1's second burst in the EDF example?

A.Time 50

B.Time 80

C.Time 100 ✅

D.Time 125

💡 Difficulty: medium | ✅ Correct: C

📖 Explanation: The absolute deadline is the specific time by which a process must complete its work. P1's second period starts at time 50 and ends at time 100, so its absolute deadline is 100. This is the time by which P1's second CPU burst must be completed.

Q27. What is the absolute deadline for P2's first burst in the EDF example?

A.Time 60

B.Time 80 ✅

C.Time 100

D.Time 145

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: P2's first period ends at time 80, so its absolute deadline for its first burst is 80. This is the specific time by which P2's first CPU burst must be completed to meet its timing requirements.

Q28. At what time does P2 start its first execution in the EDF example?

A.Time 0

B.Time 20

C.Time 25 ✅

D.Time 50

💡 Difficulty: medium | ✅ Correct: C

📖 Explanation: P1 runs first from time 0 to 25 because it has the earliest deadline. After P1 completes its first burst, P2 begins running at time 25. This is a direct application of the EDF rule: the process with the earliest absolute deadline runs first.

Q29. What is the significance of P2 being able to continue running at time 50 in the EDF example?

A.It shows EDF is non-preemptive

B.It shows EDF dynamically adjusts priorities based on deadlines ✅

C.It shows EDF is a static priority algorithm

D.It shows P2 has a higher period

💡 Difficulty: hard | ✅ Correct: B

📖 Explanation: At time 50, RMS would preempt P2, but EDF does not. This is because EDF compares absolute deadlines: P2's deadline (80) is earlier than P1's next deadline (100). This dynamic priority adjustment is what allows EDF to achieve schedulability where RMS fails.

Q30. Why does P1 preempt P2 at time 100 in the EDF example?

A.Because P1 has a higher priority due to its shorter period

B.Because P1's absolute deadline (150) is earlier than P2's (160) ✅

C.Because P2 has completed its work

D.Because the time quantum for P1 has expired

💡 Difficulty: hard | ✅ Correct: B

📖 Explanation: At time 100, P1's next deadline is at 150, and P2's next deadline is at 160. EDF assigns higher priority to the process with the earlier deadline, which is P1. This causes P1 to preempt P2, demonstrating how priorities change dynamically based on deadlines.

Q31. What is the total CPU utilization in the EDF example with P1(p=50, t=25) and P2(p=80, t=35)?

A.0.75

B.0.83

C.0.94 ✅

D.1

💡 Difficulty: medium | ✅ Correct: C

📖 Explanation: The total utilization is (25/50) + (35/80) = 0.50 + 0.4375 = 0.9375, or approximately 94%. This is the same task set that RMS failed to guarantee, but EDF successfully schedules it, demonstrating EDF's ability to handle higher utilization.

Q32. What is the primary advantage of EDF over RMS in the context of CPU utilization?

A.EDF can guarantee schedulability for higher CPU utilization ✅

B.EDF is simpler to implement

C.EDF requires less context switching

D.EDF is better for periodic tasks

💡 Difficulty: hard | ✅ Correct: A

📖 Explanation: The primary advantage is that EDF can guarantee schedulability for task sets with higher CPU utilization. While RMS has a utilization bound of ~83% for two tasks, EDF can theoretically handle up to 100% utilization, as demonstrated by the example where EDF succeeds at 94% utilization.

Q33. In the EDF example, what is the state of P1 at time 85?

A.It is running

B.It has just completed its second burst ✅

C.It has missed its deadline

D.It is waiting for the next period

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: P1 starts its second burst at time 60 and requires 25ms. It completes at time 85, successfully meeting its second deadline at time 100. This demonstrates how EDF ensures that tasks with earlier deadlines are completed on time.

Q34. What is the state of P2 at time 145 in the EDF example?

A.It is running

B.It has just completed its burst ✅

C.It has missed its deadline

D.It is preempted

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: P2 resumes at time 125 and completes its required work at time 145. This successfully meets its second deadline at time 160. The completion at 145 demonstrates that EDF can schedule the task set effectively, even with high utilization.

Q35. What makes EDF theoretically optimal?

A.It uses the simplest algorithm

B.It can schedule any set of processes that can be scheduled by any algorithm ✅

C.It guarantees the shortest response time

D.It always uses 100% CPU

💡 Difficulty: hard | ✅ Correct: B

📖 Explanation: EDF is theoretically optimal because if any algorithm can schedule a set of processes to meet all deadlines, EDF can also schedule them. This property is based on the concept of dynamic priority assignment based on deadlines, which ensures the most urgent tasks are always executed first.

Q36. What is the relationship between a process's deadline and its priority in EDF?

A.Shorter deadline = higher priority ✅

B.Longer deadline = higher priority

C.Deadline does not affect priority

D.Priority is inversely proportional to deadline

💡 Difficulty: easy | ✅ Correct: A

📖 Explanation: In EDF, the relationship is straightforward: the earlier (shorter) the deadline, the higher the priority. This ensures that the most time-critical processes, those with the earliest absolute deadlines, are executed first to minimize the risk of missing deadlines.

Q37. What happens to P2 when P1 preempts it at time 100?

A.P2 is terminated

B.P2 continues running in the background

C.P2 is preempted and resumes later ✅

D.P2 misses its deadline

💡 Difficulty: hard | ✅ Correct: C

📖 Explanation: When P1 preempts P2 at time 100, P2 is not terminated. Its execution is paused, and its state is saved. P2 will resume execution later, after P1 completes its work. In the example, P2 resumes at time 125 and completes at time 145.

Q38. What is the deadline of P1's first burst in the EDF example?

A.Time 25

B.Time 50 ✅

C.Time 80

D.Time 100

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: P1's first period ends at time 50, so its first absolute deadline is time 50. This is the specific time by which P1's first CPU burst must be completed. In the example, P1 completes at time 25, which is well before its deadline.

Q39. What is the deadline of P2's second burst in the EDF example?

A.Time 80

B.Time 100

C.Time 160 ✅

D.Time 200

💡 Difficulty: medium | ✅ Correct: C

📖 Explanation: P2's second period starts at time 80 and ends at time 160. Therefore, its second absolute deadline is time 160. This is the time by which P2's second CPU burst must be completed. In the example, P2 completes at time 145, meeting this deadline.

Q40. In the EDF example, why does the system go idle from time 145 to 150?

A.Because both processes have completed their work

B.Because the CPU is too busy

C.Because the scheduler is not working

D.Because there are no processes ready to run ✅

💡 Difficulty: hard | ✅ Correct: D

📖 Explanation: The system goes idle because both P1 and P2 have completed their current bursts by time 145. P1's next period doesn't start until time 150, and P2's next period starts at time 160. With no processes ready to run, the CPU is idle, reflecting spare capacity in the system.

Q41. What is the primary reason EDF can achieve higher utilization than RMS?

A.EDF uses a faster algorithm

B.EDF has lower overhead

C.EDF uses dynamic priorities that adapt to deadlines ✅

D.EDF does not use preemption

💡 Difficulty: hard | ✅ Correct: C

📖 Explanation: EDF can achieve higher utilization because its dynamic priority assignment adapts to the current deadlines of processes. This allows it to make more flexible scheduling decisions than static priority algorithms like RMS, which have a fixed priority assignment that cannot adapt to changing conditions.

Q42. What is the critical factor that allows EDF to succeed where RMS fails in the example?

A.EDF assigns higher priority to P1

B.EDF assigns higher priority to P2

C.EDF dynamically adjusts priorities based on deadlines ✅

D.EDF uses a different processing time

💡 Difficulty: hard | ✅ Correct: C

📖 Explanation: The critical factor is dynamic priority adjustment. In the example, at time 50, EDF assigns higher priority to P2 (deadline 80) over P1 (deadline 100), allowing P2 to continue. This dynamic decision is what enables EDF to meet all deadlines in a case where RMS's static priorities cause a deadline miss.

Q43. What is the role of a process announcing its deadline in EDF?

A.It allows the scheduler to assign a fixed priority

B.It allows the scheduler to perform dynamic priority assignment ✅

C.It is used to determine the process's period

D.It is used to calculate CPU utilization

💡 Difficulty: hard | ✅ Correct: B

📖 Explanation: The announcement of the deadline is crucial for EDF's dynamic priority assignment. When a process becomes runnable, it announces its deadline. The scheduler can then compare this deadline with others and dynamically adjust priorities, ensuring that the process with the earliest absolute deadline gets the CPU.

Q44. In the EDF example, at what time does P2 resume after being preempted at time 100?

A.Time 100

B.Time 125 ✅

C.Time 145

D.Time 150

💡 Difficulty: hard | ✅ Correct: B

📖 Explanation: P2 is preempted by P1 at time 100. P1 runs from 100 to 125, requiring 25ms for its third burst. At time 125, P1 completes, and the scheduler switches back to P2, allowing it to resume execution from where it was preempted.

Q45. What is the difference between RMS and EDF in terms of priority assignment?

A.RMS assigns priorities based on deadlines; EDF assigns based on periods

B.RMS assigns static priorities; EDF assigns dynamic priorities ✅

C.RMS assigns dynamic priorities; EDF assigns static priorities

D.Both assign static priorities

💡 Difficulty: easy | ✅ Correct: B

📖 Explanation: The fundamental difference is that RMS uses static priorities (fixed at task creation based on period), while EDF uses dynamic priorities (changing based on the current deadlines of tasks). This gives EDF more flexibility and allows it to achieve higher CPU utilization.

Q46. What is the theoretical optimality of EDF based on?

A.Its ability to handle any number of processes

B.Its ability to schedule any process set that can be scheduled ✅

C.Its ability to use 100% CPU

D.Its ability to handle both periodic and aperiodic tasks

💡 Difficulty: hard | ✅ Correct: B

📖 Explanation: EDF's theoretical optimality is based on the fact that if any algorithm can schedule a set of processes to meet their deadlines, EDF can also do it. This is a strong theoretical property that makes EDF a highly desirable scheduling algorithm for real-time systems.

Q47. What is the practical consequence of context switching overhead in EDF?

A.It makes the algorithm impossible to implement

B.It reduces the achievable CPU utilization below 100% ✅

C.It increases the system's throughput

D.It reduces the number of context switches

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: Context switching overhead consumes CPU cycles. In theory, EDF could achieve 100% utilization, but in practice, the cycles spent on context switching and interrupt handling mean that the effective utilization is always less than 100%. This is a practical limitation of all scheduling algorithms.

Q48. In the EDF example, what is the significance of P1 completing at time 85?

A.It meets its second deadline at time 100 ✅

B.It misses its second deadline

C.It causes P2 to miss its deadline

D.It completes earlier than its period

💡 Difficulty: medium | ✅ Correct: A

📖 Explanation: P1 completing at time 85 is significant because its second absolute deadline is at time 100. By completing at 85, P1 meets its deadline with time to spare. This successful completion is part of the overall success of EDF in scheduling the task set.

Q49. What is the significance of P2 completing at time 145?

A.It meets its second deadline at time 160 ✅

B.It misses its second deadline

C.It causes P1 to miss its deadline

D.It completes later than its period

💡 Difficulty: medium | ✅ Correct: A

📖 Explanation: P2 completing at time 145 is significant because its second absolute deadline is at time 160. By completing at 145, P2 meets its deadline with time to spare. This successful completion demonstrates how EDF can handle high utilization without missing deadlines.

🔗 Related Topics (MCQs)

📝 CPU Scheduling Basic Concepts MCQs 📝 CPU I/O Burst Cycle MCQs 📝 CPU Scheduler in Operating System MCQs 📝 Preemptive Scheduling in Operating System MCQs 📝 Dispatcher in CPU Scheduling MCQs