Scheduling (computing) facts for kids

In computing, scheduling is like being a traffic controller for your computer! It's all about deciding which tasks get to use the computer's resources (like the main brain, called the CPU, or network connections) and when. The tasks can be small bits of a program (called threads) or bigger programs themselves (called processes).

This important job is done by something called a scheduler. Schedulers are designed to keep all parts of the computer busy, make sure many people can share the computer fairly, and help things run smoothly and quickly. Scheduling is super important because it allows your computer to do many things at once, even if it only has one CPU. It's how you can browse the internet, listen to music, and type a document all at the same time!

Why Scheduling Matters: Computer Goals

A scheduler tries to achieve several important goals to make your computer work well:

• Getting Work Done (Throughput): This means finishing as many tasks as possible in a certain amount of time.
• Less Waiting (Wait Time): This is about how long a task has to wait before it even starts running. Schedulers try to keep this time short.
• Quick Responses (Latency/Response Time): This is how fast a task finishes once it starts, or how quickly the computer reacts when you click something.
• Being Fair (Fairness): This means making sure each program gets a fair share of the CPU's time, or the right amount of time based on how important it is.

Sometimes, these goals can conflict. For example, trying to finish a lot of tasks quickly might mean some tasks have to wait longer. So, a scheduler often finds a good balance between these goals, depending on what the computer is being used for.

In special computer systems, like those that control robots, the scheduler also has to make sure tasks finish by a certain time. This is super important to keep the system working correctly and safely.

Types of Computer Schedulers

The scheduler is a part of the computer's operating system (the main software that runs everything). It picks which jobs or programs get to run next. Operating systems can have up to three different types of schedulers, named after how often they make decisions:

• Long-term scheduler
• Medium-term scheduler
• Short-term scheduler

How Programs Get Scheduled

The process scheduler is the part of the operating system that decides which program runs at any given moment. It can often pause a running program, move it aside, and start a new one. This is called a preemptive scheduler. If it can't pause programs and has to wait for them to finish or say they're done, it's called a cooperative scheduler.

We look at long-term, medium-term, and short-term scheduling based on how often these decisions are made.

Long-Term Scheduling

The long-term scheduler (also called the admission scheduler) decides which new programs or jobs are allowed to start running on the computer. When you try to open a program, this scheduler decides if it can join the group of programs currently running.

This scheduler controls how many programs can run at the same time. It also tries to balance different types of programs:

• I/O-bound processes spend more time waiting for input/output (like reading from a disk or network).
• CPU-bound processes spend more time doing calculations on the CPU.

A good long-term scheduler makes sure there's a mix of both types. If there are too many I/O-bound programs, the CPU might be idle. If there are too many CPU-bound programs, the input/output devices might be idle. A good mix keeps the computer busy and balanced.

Medium-Term Scheduling

The medium-term scheduler temporarily moves programs out of the computer's main memory (RAM) and puts them onto slower storage, like a hard disk drive. This is called swapping out. It does this to free up RAM for other programs. Later, it can swap in the program back into main memory when it's needed again or when more memory is free.

This can happen if a program hasn't been active for a while, has a low priority, or is using a lot of memory. It helps the computer manage its memory efficiently.

Short-Term Scheduling

The short-term scheduler (also known as the CPU scheduler) is the busiest of them all! It decides which program, out of those ready in memory, gets to use the CPU right now. It makes these decisions very, very often – sometimes many times a second.

This scheduler can be preemptive, meaning it can stop a program from using the CPU to let another one run. Or it can be non-preemptive (cooperative), meaning it waits for the program to give up the CPU on its own.

The Dispatcher

Another important part of CPU scheduling is the dispatcher. This module is like the actual "switch" that gives control of the CPU to the program chosen by the short-term scheduler.

The dispatcher's jobs include:

• Context switching: Saving the current state of the program that was running and loading the saved state of the new program.
• Switching the CPU from "kernel mode" (where the operating system runs) to "user mode" (where your programs run).
• Starting the new program exactly where it needs to begin.

The dispatcher needs to be super fast because it's used every time the CPU switches between programs. The time it takes to switch is called dispatch latency.

How Schedulers Decide: Scheduling Rules

A scheduling discipline (or algorithm) is a set of rules used to decide how to share computer resources among different programs that need them at the same time. These rules are used in many places, like in internet routers to handle data traffic, or in operating systems to share CPU time.

The main goals of these algorithms are to make sure no program waits forever (no starvation) and that everyone gets a fair chance. There are many different ways to do this.

First Come, First Served

A sample thread pool (green boxes) with a queue (FIFO) of waiting tasks (blue) and a queue of completed tasks (yellow)

This is the simplest rule, just like a line at a store: the first program to arrive in the "ready" queue is the first one to get processed. It's also called First In, First Out (FIFO).

• Simple: It's easy to understand and doesn't need much computer power to manage.
• Can Be Slow: If a very long program arrives first, shorter programs behind it have to wait a long time. This is like a slow person at the front of a long line.
• No Starvation: Every program eventually gets its turn.
• No Priorities: It doesn't care if one program is more important than another.

Priority Scheduling

In this method, programs are given a priority, and the scheduler always picks the program with the highest priority to run next. A common type is "Earliest Deadline First" (EDF), where the program that needs to finish soonest gets the highest priority.

• Good for Deadlines: Programs with urgent deadlines can be given high priority to ensure they finish on time.
• Fairness Depends on Priority: Programs with higher priority get faster service.
• Possible Starvation: If there are always high-priority programs, low-priority programs might never get to run.

Shortest Remaining Time First

This rule is similar to "shortest job first." The scheduler always picks the program that has the least amount of work left to do.

• Fast Throughput: It's good at finishing many small tasks quickly.
• Can Interrupt: If a shorter program arrives while another is running, the running program might be paused (preempted) to let the shorter one go. This can cause extra work for the computer.
• Needs Estimates: The computer needs to guess how long each program will take, which isn't always easy.
• Possible Starvation: Long programs might keep getting interrupted by new, shorter programs and never finish.

Fixed-Priority Pre-emptive Scheduling

The operating system gives each program a set priority level. The scheduler then arranges programs by their priority. If a higher-priority program arrives, it will interrupt a lower-priority one that is currently running.

• Good for Important Tasks: High-priority tasks get done quickly.
• Can Cause Starvation: Lower-priority tasks might struggle to get CPU time if there are always high-priority tasks.

Round-Robin Scheduling

Imagine a carousel where each program gets a short, fixed amount of time (a "time slice") to run. After its time is up, it goes to the back of the line, and the next program gets its turn.

• Fair: Every program gets a turn, so no one waits forever.
• Good Response Time: You feel like all programs are running at the same time because they switch quickly.
• Overhead: Switching between programs often takes a little bit of computer power.
• No Starvation: Everyone gets a turn.

Multilevel Queue Scheduling

This is used when programs can be easily sorted into different groups. For example, interactive programs (like a web browser) might be in one group, and background programs (like a file backup) in another. Each group can then have its own scheduling rules.

• Flexible: Allows different types of programs to be handled differently based on their needs.

Work-Conserving Schedulers

A work-conserving scheduler always tries to keep the computer's resources busy if there are programs waiting to run. It doesn't let the CPU sit idle if there's work to do.

Manual Scheduling

In some special computer systems, especially smaller ones built for specific tasks (like in a washing machine), jobs are scheduled manually by the programmer. This means the programmer decides exactly when each task will run.

• Predictable: You know exactly when things will happen.
• Low Overhead: Doesn't use much computer power for scheduling itself.
• Not Flexible: If the tasks change, the programmer has to manually change the schedule.

Choosing a Scheduling Algorithm

There isn't one "best" scheduling algorithm. Programmers choose the best one based on what the computer system will be used for. Many operating systems use a mix of these algorithms.

For example, Windows NT (and newer Windows versions like XP, Vista, 7, 10, 11) uses a combination of fixed-priority preemptive scheduling, round-robin, and first-in, first-out. This means important programs get high priority, but everyone still gets a turn.

How Different Operating Systems Schedule Programs

Different operating systems use different ways to schedule programs. Here's a look at some popular ones:

Windows

Very old Windows systems (like MS-DOS) couldn't do many things at once. Windows 3.1x used cooperative multitasking, meaning programs had to politely tell the system when they were done using the CPU. Windows 95 introduced preemptive scheduling, which meant the system could interrupt programs, but it still let older programs run cooperatively.

Modern Windows systems (like Windows 10 or 11) use a complex system with many priority levels. The system can change a program's priority based on whether you are actively using it (like typing in a document) or if it's just running in the background. This helps make your computer feel fast and responsive when you're interacting with it.

Classic Mac OS and macOS

Older Mac OS versions (like Mac OS 9) used a mix of cooperative and preemptive scheduling. Newer macOS systems (like the ones on your MacBook) use a preemptive system with different priority levels for threads, similar to Windows. This ensures that important system tasks and your active applications get the CPU time they need.

Linux

A highly simplified structure of the Linux kernel, which includes process schedulers, I/O schedulers, and packet schedulers

Linux has changed its scheduler over the years. Early versions used a simple round-robin. Later, it used more complex schedulers.

From 2007 to 2023, Linux mostly used something called the Completely Fair Scheduler (CFS). This scheduler tries to give every program a "fair" share of the CPU time, making sure no program feels left out. It's like a fair queuing system, where everyone gets their turn, but faster.

In 2023, Linux started moving towards a new scheduler called earliest eligible virtual deadline first scheduling (EEVDF). This new scheduler aims to improve how Linux handles tasks, especially those that need to meet deadlines.

FreeBSD

FreeBSD uses a system with many priority levels, from 0 to 255. Some levels are for system tasks, and others are for user programs. It also uses "active" and "idle" queues for programs.

NetBSD

NetBSD also uses a multilevel feedback queue with priorities, similar to FreeBSD, to manage different types of threads and tasks.

Solaris

Solaris uses a multilevel feedback queue with priorities. It also has special classes for "fixed-priority" threads (whose priority doesn't change) and "fair share" threads, which get CPU time based on how many "shares" they are given.

Summary of Schedulers in Different Operating Systems

See also