scheduling algorithms limitations

What is the primary function of a CPU scheduling algorithm?

Determining which process is allocated the CPU next.

Name three of the five performance goals mentioned for scheduling algorithms.

Fairness, speed, responsiveness, real-time guarantees, or efficiency.

In First-Come, First-Served (FCFS) scheduling, what determines the execution order?

The order in which processes arrive.

What is a major advantage of the First-Come, First-Served (FCFS) algorithm?

It is very simple and easy to implement.

Which scheduling algorithm is described as fair specifically in terms of arrival order?

First-Come, First-Served (FCFS).

The phenomenon where a long CPU-bound process delays several shorter processes is known as the _____.

Convoy Effect

Why is FCFS typically unsuitable for interactive users?

It can result in poor response times.

What does it mean for an algorithm like FCFS to be 'non-preemptive'?

A process cannot be interrupted once it has started execution.

How does the Shortest Process Next (SPN) algorithm select the next process?

It runs the process with the shortest CPU burst first.

Which scheduling algorithm is specifically designed to minimise average waiting time?

Shortest Process Next (SPN) / Shortest Job First (SJF).

For what type of system is Shortest Process Next (SPN) considered highly efficient?

Batch systems.

How can starvation occur in Shortest Process Next (SPN) scheduling?

Long processes may wait indefinitely if short jobs arrive continuously.

What is the primary practical difficulty for an OS using Shortest Job First (SJF)?

It is difficult to predict actual execution (burst) times in advance.

Why is SPN/SJF unsuitable for real-time environments?

It ignores task importance and deadlines.

In Round Robin (RR) scheduling, what is the name of the fixed time slice allocated to each process?

A quantum.

What are the two primary advantages of using Round Robin (RR) scheduling?

Fair CPU sharing and good responsiveness.

For which specific system type is Round Robin (RR) highly suitable?

Interactive systems.

What is the negative consequence of setting a very small time quantum in Round Robin?

It creates excessive overhead due to too many context switches.

If the time quantum in Round Robin is excessively large, how does the algorithm behave?

It behaves like First-Come, First-Served (FCFS).

Why is Round Robin considered weak for hard real-time systems?

It cannot provide guarantees regarding deadlines.

How does Priority Scheduling determine which process runs first?

Processes are assigned priorities, and the one with the highest priority runs first.

What is a major advantage of Priority Scheduling for real-time systems?

It ensures that important tasks execute earlier.

What is the main limitation of Priority Scheduling regarding low-priority processes?

They may suffer from starvation and never run.

Describe the limitation known as 'Priority Inversion'.

A low-priority process holding a resource blocks a high-priority process.

Which task does the Earliest Deadline First (EDF) algorithm run first?

The task with the nearest deadline.

Identify two advantages of Earliest Deadline First (EDF) in real-time systems.

Excellent for hard real-time and high CPU utilisation.

How does the EDF algorithm handle changing deadlines?

It adapts to deadlines dynamically.

What is a major risk of using EDF during a system overload?

The scheduler becomes unstable and may cause many missed deadlines.

Why does EDF have a higher implementation overhead than simpler algorithms?

It requires continuous deadline tracking and frequent preemption.

What is Rate Monotonic Scheduling (RMS)?

A fixed-priority real-time scheduling algorithm.

How are priorities assigned in Rate Monotonic Scheduling (RMS)?

Shorter periodic tasks receive higher priority.

What is the main benefit of RMS in a Real-Time Operating System (RTOS)?

It is highly predictable.

How does RMS compare to EDF in terms of CPU efficiency?

RMS has lower CPU utilisation because it cannot fully utilise the CPU efficiently.

What is the primary limitation of fixed priorities in RMS?

It is less flexible than dynamic scheduling methods.

What is the core objective of Guaranteed Scheduling?

Giving each process a fair share of total CPU time.

What is the primary advantage of Guaranteed Scheduling?

It prevents a single process from dominating CPU resources.

In Guaranteed Scheduling, why does fairness not guarantee task safety?

Critical tasks may not receive immediate CPU access when needed.

Why is Guaranteed Scheduling considered to have high overhead?

It requires constant tracking of CPU usage for every process.

How does a Lottery Scheduler select the next process?

It randomly chooses a winner from the processes holding lottery tickets.

Identify one advantage of Lottery Scheduling.

Flexible fairness or simple probabilistic control.

Why is Lottery Scheduling considered unpredictable for critical tasks?

Critical tasks may lose the lottery and fail to run.

How is CPU time allocated in Fair Share Scheduling?

It is divided among users or groups rather than individual processes.

What is the main benefit of Fair Share Scheduling for multi-user systems?

It prevents one group or user from monopolising the CPU.

What is a critical limitation of Fair Share Scheduling regarding urgent tasks?

It focuses on fairness rather than urgency, which can delay critical tasks.

How does Multiple Queue Scheduling organise different types of processes?

It divides them into separate queues, such as real-time, interactive, and batch.

What is an advantage of Multiple Queue Scheduling for systems with mixed workloads?

It separates process types and can apply different algorithms to each queue.

What is the risk of having a hierarchy of queues in Multiple Queue Scheduling?

Starvation can occur in the lower-priority queues.

What is the primary goal of a Batch system?

Throughput.

What is the primary goal of an Interactive system?

Fast response.

What is the primary goal of a Real-time system?

Meeting deadlines.

What is the primary goal of a Multi-user system?

Fairness.

Why do modern operating systems typically use hybrid scheduling?

No single algorithm can optimise all goals simultaneously.

In a hybrid system, which algorithm is typically used for interactive tasks?

Round Robin (RR).

In a hybrid system, which algorithm is typically used for batch jobs?

Shortest Process Next (SPN).

Scheduling is described as a trade-off between five factors: fairness, responsiveness, efficiency, predictability, and _____.

Deadline guarantees.

Which limitation is common to FCFS, SPN, and Priority Scheduling?

They can all lead to starvation or delayed execution of specific task types.

Which scheduling algorithm is most associated with periodic real-time tasks?

Rate Monotonic Scheduling (RMS).