Unix - UNIX Process Scheduling Algorithms

Operating Systems

UNIX process scheduling algorithms are the methods used by the operating system to decide which process should run on the CPU at any given time. In a multi-user and multitasking environment, many programs may be active simultaneously. Since the CPU can execute only one instruction stream per core at a moment, the operating system must manage how CPU time is shared among all running processes. Scheduling ensures that all tasks receive fair access to system resources while maintaining overall efficiency and responsiveness.

What is Process Scheduling

A process in Unix is an instance of a running program. When multiple processes are running, the kernel determines which process gets CPU access and for how long. This selection process is called scheduling. The scheduler is a part of the kernel that continuously evaluates process priorities, waiting times, and CPU usage to make decisions.

For example, if a user opens a text editor, runs a backup script, and starts a browser at the same time, the scheduler allocates CPU time to each of these processes. It switches rapidly among them, creating the impression that all programs run simultaneously.

Objectives of Scheduling

Unix scheduling aims to achieve several goals:

  • Efficient use of CPU resources

  • Fair distribution of CPU time

  • Quick response for interactive users

  • High throughput for system tasks

  • Balanced performance between short and long jobs

The scheduler tries to reduce idle CPU time while ensuring that no process waits indefinitely.

Basic Scheduling Concepts

Several concepts are important in understanding scheduling.

Process State

A process can exist in different states:

  • Running: currently executing

  • Ready: waiting for CPU allocation

  • Sleeping: waiting for input or event

  • Stopped: temporarily halted

  • Zombie: finished but not removed from process table

The scheduler mainly manages ready processes.

Time Slice

A time slice is a short duration during which a process can use the CPU. Once the time slice ends, the scheduler may switch to another process. This method supports multitasking.

Context Switching

Context switching occurs when the CPU changes from one process to another. The kernel saves the current process state and loads the next one. This allows processes to resume later from the exact point where they paused.

Types of Scheduling in UNIX

Unix uses a combination of scheduling methods depending on the implementation.

Round Robin Scheduling

f(x)=x \bmod n

Round Robin scheduling is one of the simplest techniques. Each process gets a fixed time slice in cyclic order. After one process uses its time slice, the next process in the queue gets CPU access.

This approach is suitable for time-sharing systems because all users get fair access.

Example:

If three processes are in queue:

  • Process A

  • Process B

  • Process C

The CPU serves them in sequence:

A → B → C → A → B → C

Advantages:

  • Fair for all processes

  • Simple to implement

  • Good for interactive systems

Disadvantages:

  • Frequent context switching may reduce efficiency

  • Long jobs may take more total time

Priority Scheduling

In priority scheduling, each process receives a priority value. Higher priority processes are executed before lower priority ones.

Examples:

  • System tasks may have higher priority

  • User background tasks may have lower priority

Unix often recalculates priorities dynamically based on process behavior.

A process that uses too much CPU may have its priority lowered, while a waiting process may gain higher priority.

Multilevel Queue Scheduling

Processes are divided into categories:

  • System processes

  • Interactive processes

  • Batch processes

Each category has its own queue. Different scheduling rules may apply to each queue.

Interactive jobs usually get quicker service than long batch jobs.

Preemptive Scheduling

In preemptive scheduling, the operating system can interrupt a running process and assign the CPU to another process.

This improves responsiveness.

For instance, if a low-priority process is running and a higher-priority task arrives, the scheduler can stop the current process temporarily and run the important one.

Non-Preemptive Scheduling

In non-preemptive scheduling, a process continues until it completes or voluntarily gives up the CPU.

Older Unix versions relied more on non-preemptive behavior, but modern systems use preemptive scheduling.

UNIX Scheduler Architecture

The Unix kernel scheduler maintains process information in internal data structures.

These include:

  • Process control blocks

  • Run queues

  • Priority tables

  • CPU accounting data

Each process has attributes such as:

  • Process ID

  • Priority

  • CPU usage history

  • Scheduling class

  • State information

The scheduler checks these values frequently.

Process Priority in UNIX

Unix assigns priorities to all processes.

There are two major types.

User Priority

This changes dynamically according to process behavior.

Interactive tasks often receive favorable treatment.

Nice Value

Users can manually influence process priority using the nice command.

Example:

nice -10 program

A lower nice value means higher priority.

The renice command changes priority of an already running process.

Scheduling Classes

Modern Unix systems often use scheduling classes.

Examples:

  • Time-sharing class

  • Real-time class

  • Interactive class

Each class follows different rules.

Real-time tasks may bypass ordinary scheduling for guaranteed execution.

CPU Bound vs I/O Bound Processes

The scheduler treats processes differently depending on their behavior.

CPU Bound

These processes use CPU continuously.

Examples:

  • Compilation

  • Mathematical computation

  • Video encoding

I/O Bound

These spend time waiting for disk, keyboard, or network.

Examples:

  • Text editors

  • File transfers

  • Database queries

Unix often favors I/O bound processes because they interact directly with users.

Aging Technique

Aging prevents starvation.

Starvation occurs when low-priority processes never receive CPU time because high-priority tasks dominate.

Aging gradually increases waiting process priority until it eventually runs.

Load Average

Unix measures system load using load average.

It represents the average number of runnable processes over time.

Commands:

uptime

w

These display load statistics.

Higher load indicates more competition for CPU.

Scheduler Performance Metrics

The effectiveness of scheduling can be measured through:

Turnaround Time

Total time from process submission to completion.

Waiting Time

Time spent waiting for CPU.

Response Time

Time until first response.

Throughput

Number of completed processes per unit time.

Commands Related to Scheduling

Several Unix commands help users view and control scheduling.

ps

Displays process details.

Example:

ps -ef

top

Shows active processes and CPU usage.

nice

Starts a process with custom priority.

renice

Changes priority of a running process.

kill

Sends signals to control processes.

Real-Time Scheduling

Some Unix systems support real-time scheduling.

Used in:

  • Industrial control

  • Embedded systems

  • Communication systems

Real-time scheduling guarantees that critical tasks execute within fixed time limits.

Two major types:

  • Hard real-time

  • Soft real-time

Hard real-time requires strict deadlines.

Soft real-time allows slight delay.

Example of Scheduling Flow

Suppose the system has these processes:

  1. Browser

  2. Music player

  3. Backup script

  4. File download

The scheduler may act like this:

  • Browser receives quick service for user input

  • Music player receives steady CPU

  • Download waits for network packets

  • Backup script gets lower priority background execution

The scheduler continuously adjusts based on process activity.

Kernel Role

The Unix kernel performs scheduling by:

  • Tracking process states

  • Managing run queues

  • Assigning priorities

  • Triggering context switches

  • Balancing CPU usage

The scheduler works automatically without user intervention.

Importance of Scheduling

Scheduling is essential because it:

  • Enables multitasking

  • Supports multiple users

  • Improves responsiveness

  • Maximizes CPU efficiency

  • Maintains system stability

Without scheduling, Unix would execute only one process at a time, reducing usability.

Modern UNIX Scheduling

Modern Unix variants such as Linux, FreeBSD, and macOS use advanced scheduling mechanisms.

These systems support:

  • Symmetric multiprocessing

  • Dynamic priorities

  • CPU affinity

  • Fair scheduling

  • Real-time execution

This allows them to handle thousands of processes efficiently.

Conclusion

Unix process scheduling algorithms are fundamental to operating system performance. They control how CPU resources are shared among multiple running tasks. By using methods such as round robin, priority scheduling, and multilevel queues, Unix ensures fairness, responsiveness, and efficient system operation.

The scheduler is a core component of Unix that enables smooth multitasking and supports the reliable execution of user applications, system services, and background operations. Understanding process scheduling helps users and administrators optimize system performance and troubleshoot resource issues effectively.