OS CH5 - CPU Scheduling

What is the CPU scheduler?

The component of the OS that selects a process from the ready queue and allocates the CPU to it.

Define preemptive scheduling.

A scheduling method where the CPU can be taken away from a running process before it completes, typically for higher-priority tasks.

What is non-preemptive scheduling?

A scheduling method where the CPU is allocated to a process until it terminates or switches to a waiting state.

Define the dispatcher.

The OS module that gives control of the CPU to the process selected by the CPU scheduler, involving context switching and mode switching.

What is dispatch latency?

The time taken by the dispatcher to stop one process and start another.

Define turnaround time.

The total time taken to execute a process, from submission to completion.

What is waiting time?

The total time a process spends waiting in the ready queue.

Define response time.

The time from when a request is submitted until the first response is produced (important for interactive systems).

What is FCFS scheduling?

A non-preemptive scheduling algorithm where processes are executed in the order they arrive in the ready queue.

Define SJF scheduling.

A scheduling algorithm that selects the process with the shortest next CPU burst. It can be preemptive (SRTF) or non-preemptive.

What is priority scheduling?

A scheduling algorithm where each process is assigned a priority, and the CPU is allocated to the highest-priority process.

Define Round Robin scheduling.

A preemptive scheduling algorithm where each process is given a fixed time slice (quantum) to execute before being preempted.

What is multilevel queue scheduling?

A scheduling method where processes are divided into multiple queues based on priority or type, each with its own scheduling algorithm.

Define multilevel feedback queue scheduling.

A scheduling method where processes can move between queues based on their behavior (e.g., CPU-bound vs. I/O-bound).

What is processor affinity?

The tendency of a process to run on the same CPU it previously ran on, improving cache performance.

Define load balancing.

Distributing workloads evenly across multiple CPUs to improve system efficiency.

What is real-time scheduling?

Scheduling algorithms designed to meet strict timing constraints, ensuring tasks are completed by their deadlines.

Define Rate Monotonic Scheduling.

A real-time scheduling algorithm where tasks are assigned priorities based on their periods (shorter period = higher priority).

What is Earliest Deadline First scheduling?

A real-time scheduling algorithm where tasks are prioritized based on their deadlines (earlier deadline = higher priority).

Define proportional share scheduling.

A scheduling method where each process receives a share of CPU time proportional to its allocated shares.

What is the convoy effect in FCFS scheduling?

When a long process holds up shorter processes behind it, leading to poor average waiting times.

Why is SJF optimal for minimizing average waiting time?

It always selects the shortest next CPU burst, reducing the total waiting time for all processes.

What is priority inversion?

When a low-priority process holds a resource needed by a high-priority process, causing the high-priority process to wait.

How does aging prevent starvation in priority scheduling?

Gradually increasing the priority of waiting processes ensures they eventually get CPU time.

What happens if the time quantum in RR is too small or too large?

• Too small: High context-switching overhead.

• Too large: Degenerates to FCFS, increasing response time.

Give an example of a multilevel queue setup.

• Foreground queue: Interactive processes (RR scheduling).

• Background queue: Batch processes (FCFS scheduling).

How does a multilevel feedback queue work?

Processes start in the highest-priority queue (e.g., RR with small quantum). If they don’t finish, they move to lower-priority queues (e.g., RR with larger quantum).

Compare soft and hard processor affinity.

• Soft affinity: The OS tries to keep a process on the same CPU but may move it.

• Hard affinity: The process is fixed to a specific CPU.

Compare push and pull migration in load balancing.

• Push migration: A central task periodically redistributes processes.

• Pull migration: Idle CPUs pull processes from busy CPUs.

What are the challenges in real-time scheduling?

Ensuring tasks meet deadlines, handling interrupt and dispatch latencies, and avoiding priority inversion.

How does RMS assign priorities?

Tasks with shorter periods get higher priorities. For example, a task with a 10ms period has higher priority than one with a 20ms period.

How does EDF prioritize tasks?

Tasks with earlier deadlines get higher priorities. For example, a task with a deadline in 5ms has higher priority than one with a deadline in 10ms.

How does proportional share scheduling allocate CPU time?

If a process has 2 shares out of 10 total shares, it gets 20% of the CPU time.

How does the Linux Completely Fair Scheduler (CFS) work?

It allocates CPU time based on a process’s virtual runtime, ensuring fairness by prioritizing processes with the least CPU usage.

How does Windows prioritize threads?

Uses 32 priority levels (1-31), with real-time threads (16-31) having higher priority than variable threads (1-15).

What are the scheduling classes in Solaris?

Time Sharing (TS), Interactive (IA), Real Time (RT), System (SYS), Fair Share (FSS), and Fixed Priority (FP).

What is deterministic modeling in algorithm evaluation?

Evaluating scheduling algorithms using a specific, predetermined workload to calculate performance metrics.

How are simulations used to evaluate CPU schedulers?

By modeling the system and workload, simulations can predict performance metrics like throughput and waiting time.

Why is context switching overhead important in scheduling?

Frequent context switching reduces CPU efficiency, so schedulers must balance responsiveness with overhead.

Compare RR and FCFS in terms of response time and turnaround time.

RR provides better response time but may have worse turnaround time due to preemption. FCFS has poor response time but better turnaround time for short processes.

How can priority scheduling lead to starvation?

Low-priority processes may never get CPU time if higher-priority processes continuously arrive.

What is User-Mode Scheduling in Windows?

Applications manage threads independently of the kernel, improving efficiency for large numbers of threads.

What are queueing models used for in scheduling?

To probabilistically describe process arrivals and CPU bursts, enabling calculation of metrics like average waiting time.

List methods for evaluating CPU scheduling algorithms.

Deterministic modeling, queueing models, simulations, and real-world implementation.