Chapter 5 Operating Systems

What is CPU scheduling?

Selecting a process from the ready queue and allocating the CPU to it.

What is the CPU–I/O Burst Cycle?

A process alternates between CPU execution and I/O waiting.

What does the CPU scheduler do?

Selects a process from the ready queue to run on the CPU.

What is preemptive scheduling?

The OS can interrupt a running process and give the CPU to another process.

What is nonpreemptive scheduling?

A process keeps the CPU until it switches to waiting or terminates.

What does the dispatcher do?

Gives control of the CPU to the process selected by the scheduler.

What is dispatch latency?

The time required to stop one process and start another.

What are the five scheduling criteria?

CPU utilization, throughput, turnaround time, waiting time, and response time.

What is CPU utilization?

Keeping the CPU as busy as possible.

What is throughput?

The number of processes completed per unit of time.

What is turnaround time?

The total amount of time required to execute a particular process.

What is waiting time?

The amount of time a process waits in the ready queue.

What is response time?

The time from submitting a request until the first response is produced.

What is FCFS scheduling?

First-Come, First-Served; processes execute in arrival order.

What is the convoy effect?

A short process has to wait behind a long process.

What is SJF scheduling?

Shortest-Job-First selects the process with the shortest next CPU burst.

Why is SJF considered optimal?

It produces the minimum average waiting time for a given set of processes.

What is the main problem with SJF?

The OS must know or estimate the length of the next CPU burst.

What is SRTF?

The preemptive version of Shortest-Job-First.

What is exponential averaging used for?

Predicting the length of the next CPU burst.

What happens when α = 0?

Recent CPU-burst history does not count.

What happens when α = 1?

Only the actual last CPU burst counts.

What is priority scheduling?

The CPU is given to the process with the highest priority.

In this scheduling system, which priority number is highest?

The smallest integer.

What problem can priority scheduling cause?

Starvation.

What is aging?

Increasing a waiting process's priority over time to prevent starvation.

What is Round Robin scheduling?

Each process receives a small time quantum before being preempted and moved to the end of the ready queue.

What happens when the RR time quantum is large?

RR behaves like FIFO/FCFS.

What happens when the RR time quantum is too small?

Context-switch overhead becomes too high.

What is a multilevel queue?

The ready queue is divided into separate queues for different types of processes.

What is a multilevel feedback queue?

A scheduling system where processes can move between different queues.

What is PCS?

Process-Contention Scope; scheduling competition occurs within a process.

What is SCS?

System-Contention Scope; scheduling competition occurs among all threads in the system.

What is SMP?

Symmetric multiprocessing, where each processor can self-schedule.

What is processor affinity?

A process has a preference for running on a particular processor.

What is load balancing?

Keeping workloads evenly distributed across CPUs.

What is push migration?

An overloaded CPU moves tasks to another CPU.

What is pull migration?

An idle CPU pulls a waiting task from a busy CPU.

What is a soft real-time system?

A system without a guarantee that a real-time process will meet its deadline.

What is a hard real-time system?

A system where tasks must be serviced by their deadlines.

What is interrupt latency?

Time from an interrupt arriving until its service routine starts.

What is Rate Monotonic Scheduling?

A real-time scheduling method where shorter periods receive higher priority.

What is EDF scheduling?

Earliest Deadline First; tasks with earlier deadlines receive higher priority.

What is Little's Formula?

n = λ × W

What do the variables in Little's Formula mean?

n = average queue length, λ = average arrival rate, W = average waiting time.

What is Linux's CFS?

Completely Fair Scheduler.

What does Linux CFS use to choose the next task?

Virtual runtime (vruntime); the task with the lowest vruntime runs next.

How does Windows schedule threads?

Using priority-based preemptive scheduling.

How many priority levels does Windows use?

32 levels.

What are the two POSIX real-time scheduling classes?

SCHED_FIFO and SCHED_RR.

What is SCHED_FIFO?

FCFS scheduling with no time-slicing between threads of equal priority.

What is SCHED_RR?

Similar to SCHED_FIFO but uses time-slicing for equal-priority threads.