Processes, Threads and CPU Scheduling

Introduction

A computer system may appear to execute many activities simultaneously: a web browser displays a page, an operating system saves a file, and an antivirus program scans data. The processor, however, can execute only a limited number of instruction streams at a time. The operating system creates the impression of simultaneous activity by organizing programs as processes and threads and by rapidly allocating CPU time among them.

Process management is therefore central to operating-system design. It determines how programs become running activities, how the operating system records their status, how execution is interrupted and resumed, how independent activities communicate, and how processor time is distributed fairly and efficiently. Poor process management can cause low utilization, long response times, data corruption, or system-wide deadlock.

Learning Objectives

After studying this chapter, you should be able to:

• explain processes, process states, and the process control block;
• distinguish processes from threads;
• describe context switching and concurrency;
• explain major forms of inter-process communication;
• calculate and interpret basic CPU-scheduling measures;
• compare important scheduling algorithms;
• identify the necessary conditions for deadlock and describe prevention, avoidance, detection, and recovery approaches.

1. The Process Concept

A program is a passive collection of instructions stored on secondary storage. A process is a program in execution. It includes the program code, current instruction, CPU-register values, memory areas, open files, and other resources required for execution. Thus, one program can produce several processes. For example, opening two independent instances of a text editor normally creates two processes, each with its own execution context.

A process typically contains:

• a text section containing executable instructions;
• a data section containing global and static variables;
• a heap used for dynamically allocated memory;
• a stack containing function calls, parameters, and local variables;
• a current program counter and CPU-register values;
• operating-system resources such as files, devices, and communication endpoints.

The operating system manages a process from its creation until its termination. A process may create child processes, request services from the operating system, wait for input or another process, and eventually return an exit status.

Process States

A process does not remain continuously on the CPU. It moves through states as events occur. The standard five-state model contains the following states:

A new process normally enters the ready state after creation. The scheduler selects a ready process and dispatches it to a processor. If its time slice expires, or if a higher-priority process must run, it may move from running back to ready. If it requests input/output, it moves to waiting. When the operation completes, it returns to ready. A running process enters terminated when it finishes or is forcibly ended.

The state model is useful because it separates two different reasons for non-execution. A ready process is waiting for the CPU, whereas a blocked process is waiting for an event and would not benefit from being given the CPU.

Process Control Block

The process control block (PCB) is an operating-system data structure containing the information needed to manage and resume a process. It is sometimes called a task control block. A PCB commonly includes:

• process identification number and parent-process information;
• current process state;
• program counter;
• CPU registers and processor-status information;
• scheduling information, including priority and queue links;
• memory-management information, such as page-table references or segment details;
• accounting information, including CPU time used and ownership;
• input/output status and a list of open files.

The PCB is essential during an interruption. When the operating system stops a running process, it saves the process's execution information in its PCB. Later, the saved information is restored so that the process continues as if it had not been interrupted. A corrupted or incomplete PCB could cause incorrect execution, security failures, or loss of data.

2. Threads and Concurrency

A thread is the smallest unit of CPU execution that can be scheduled independently. A process may contain one thread or multiple threads. Threads belonging to the same process share its code, data, heap, and open resources, but each thread has its own program counter, register set, and stack.

A single-threaded process performs one instruction sequence at a time. A multithreaded process can perform several related activities concurrently. For example, a business application might use one thread to receive user input, another to calculate a report, and another to communicate with a database.

Benefits and Costs of Threads

Threads provide several benefits:

1. Responsiveness: A user interface can remain responsive while another thread performs a lengthy operation.
2. Resource sharing: Threads naturally share data within their process.
3. Economy: Creating and switching between threads is often less expensive than creating and switching between separate processes.
4. Scalability: On a multicore processor, different threads may execute in parallel.

Threads also create risks. Shared data can be changed simultaneously, producing a race condition. For example, if two threads read the same bank-balance value, both add a deposit, and both write back their results, one update may overwrite the other. Synchronization mechanisms such as mutexes, semaphores, monitors, and atomic operations are used to protect critical sections.

A critical section is a part of a program that accesses shared data or a shared resource and must not be executed by conflicting threads at the same time. Correct synchronization should provide mutual exclusion, progress, and bounded waiting. Excessive locking, however, can reduce performance and create deadlock.

Concurrency and Parallelism

Concurrency means that multiple activities make progress during overlapping periods. On a single-core processor, this is achieved by interleaving execution: the CPU runs one activity briefly, then another. Parallelism means that activities execute at the same instant on different processing cores. Concurrency is therefore possible on one core, while true hardware parallelism requires multiple execution resources.

Concurrency improves responsiveness and resource utilization, but it makes program behavior more difficult to predict. The result may depend on the order in which threads are scheduled. This is why shared state must be carefully synchronized and why developers should prefer clear ownership, immutable data where practical, and well-defined communication protocols.

3. Context Switching

A context switch occurs when the operating system changes the CPU from one process or thread to another. The operating system saves the context of the currently running activity in its PCB or thread-control structure and restores the saved context of the selected activity. The context includes the program counter, registers, stack pointer, and relevant scheduling and memory information.

A context switch does not directly perform useful application work. It is overhead required to support multitasking. Its cost depends on processor architecture, operating-system design, cache behavior, memory-management mechanisms, and whether the switch is between threads in the same process or between separate processes. Frequent switching can reduce throughput and disturb processor caches, while infrequent switching can make interactive systems feel unresponsive.

Context switching should be distinguished from a mode switch. A mode switch changes the processor between user mode and kernel mode, usually when an application requests an operating-system service. A mode switch does not necessarily change the running process; a context switch does.

4. Inter-Process Communication

Processes are normally isolated from one another. Inter-process communication (IPC) provides controlled methods for exchanging data and coordinating activity. Two fundamental models are shared memory and message passing.

Shared Memory

In shared-memory IPC, the operating system establishes a memory region that multiple processes can access. The processes then read and write the region directly. Shared memory can be fast because, after setup, data need not be copied through the kernel for every exchange. However, the processes must coordinate access using synchronization tools such as semaphores or mutexes. Without synchronization, simultaneous updates can cause race conditions.

A producer-consumer buffer illustrates the issue. The producer places items into a shared buffer, while the consumer removes them. The producer must not insert into a full buffer, and the consumer must not remove from an empty one. Empty and full counters, together with mutual exclusion, can coordinate the operations.

Message Passing

In message passing, processes communicate through operating-system-managed operations such as send and receive. Messages may be exchanged through:

• Direct communication, where a sender names a receiver;
• Indirect communication, where messages are placed in a mailbox or port;
• Blocking communication, where a sender or receiver waits;
• Non-blocking communication, where the operation returns immediately.

Message passing is often easier to protect because processes do not directly share memory. It can also work across a network. Its disadvantages may include kernel overhead, copying costs, message-size limitations, and the need to design suitable protocols.

Other IPC mechanisms include pipes, named pipes, sockets, signals, and remote procedure calls. A pipe commonly provides a one-way stream between related processes. A socket supports communication between processes on the same machine or across a network. The appropriate mechanism depends on data volume, security, performance, distance, and synchronization requirements.

5. CPU Scheduling

CPU scheduling is the operating system's method of selecting a process or thread from the ready queue for execution. The short-term scheduler makes frequent decisions, so it must be efficient. A dispatcher gives control of the CPU to the selected activity, performs the necessary context switch, and transfers execution to the correct location.

Scheduling policies are evaluated using several measures:

• CPU utilization: the proportion of time the CPU is busy;
• Throughput: the number of processes completed per unit of time;
• Turnaround time: completion time minus arrival time;
• Waiting time: total time spent in the ready queue;
• Response time: time from arrival until the process first receives CPU service;
• Fairness: the extent to which processes receive appropriate and non-discriminatory service.

For process i, if A_i is arrival time, C_i is completion time, and F_i is the first time it receives the CPU, then:

where T_i is turnaround time, and:

where R_i is response time. If B_i is the total CPU burst time, then, assuming waiting time excludes execution time:

Average values are calculated by summing the relevant measure for all n processes and dividing by n. These formulas assume that times use the same unit, such as milliseconds, and that the stated CPU-burst definition is consistent.

Scheduling Algorithms

#### First-Come, First-Served

First-Come, First-Served (FCFS) schedules processes in arrival order. It is simple and non-preemptive: once a process receives the CPU, it normally keeps it until its burst finishes or it blocks.

FCFS is easy to implement and appears fair by arrival order. Its major weakness is the convoy effect, in which a long CPU-bound process delays many short processes. This can produce poor average waiting and response times.

#### Shortest-Job-First

Shortest-Job-First (SJF) selects the ready process with the smallest next CPU burst. When burst lengths are known accurately, SJF minimizes average waiting time for a given set of processes under the standard single-processor model. In practice, the next burst must be estimated, often from past behavior. Long processes may experience starvation if short jobs continue to arrive.

The preemptive version is Shortest-Remaining-Time-First (SRTF). If a newly arriving process has a shorter remaining burst than the running process, the operating system preempts the current process.

#### Priority Scheduling

In priority scheduling, each process is assigned a priority and the highest-priority ready process is selected. It may be preemptive or non-preemptive. Priority scheduling is useful when urgent tasks must receive rapid service, but low-priority processes may starve. Aging gradually increases the priority of a waiting process and is a common remedy.

#### Round Robin

Round Robin (RR) is designed for interactive systems. Each ready process receives a time quantum, or time slice, in circular order. If the process does not finish before the quantum expires, it is preempted and returned to the ready queue.

A very small quantum increases context-switch overhead. A very large quantum makes RR approach FCFS and can worsen response for newly arrived interactive tasks. The quantum should therefore balance responsiveness and switching cost.

#### Multilevel Queue and Multilevel Feedback Queue

A multilevel queue divides the ready queue into classes, such as interactive, system, and batch processes. Each queue may use a different algorithm, and fixed priorities may be assigned among queues. This design is efficient when process categories are stable but may starve lower queues.

A multilevel feedback queue (MLFQ) allows processes to move between queues. Short or interactive jobs may remain in high-priority queues, while CPU-intensive jobs move to lower-priority queues. Aging or periodic priority boosts can improve fairness. MLFQ is flexible but complex to configure because its behavior depends on queue priorities, time quanta, and promotion rules.

Worked Scheduling Example

Consider three processes arriving at time 0:

Under FCFS, the order is P1, P2, P3. Completion times are 8, 12, and 14 ms. Because all arrive at time 0, waiting times are 0, 8, and 12 ms. Average waiting time is (0 + 8 + 12) ÷ 3 = 6.67 ms.

Under non-preemptive SJF, the order is P3, P2, P1. Completion times are 2, 6, and 14 ms. Waiting times are 0, 2, and 6 ms. Average waiting time is (0 + 2 + 6) ÷ 3 = 2.67 ms. This example demonstrates why SJF can reduce average waiting time, although it requires burst-time knowledge and may be unfair to long jobs.

6. Deadlocks

A deadlock is a condition in which a set of processes is permanently blocked because each process is waiting for a resource or event that another process in the same set must provide. For example, Process A holds a printer lock and waits for a file lock, while Process B holds the file lock and waits for the printer lock.

Four conditions must hold simultaneously for a classical resource deadlock:

1. Mutual exclusion: At least one resource is non-shareable; only one process can use it at a time.
2. Hold and wait: A process holds one or more resources while waiting for additional resources.
3. No preemption: Resources cannot be forcibly removed; they must be released voluntarily.
4. Circular wait: A circular chain exists in which each process waits for a resource held by the next process.

If any one condition is prevented, that particular deadlock cannot occur.

Deadlock Management

Deadlock prevention designs the system so that at least one necessary condition cannot hold. Examples include requiring a process to request all resources at once, imposing a global order on resource acquisition, or permitting preemption where safe. Prevention can reduce resource utilization or cause long waits.

Deadlock avoidance permits the conditions but evaluates each request before granting it. The system grants a request only if the resulting allocation leaves the system in a safe state, meaning some order of process completion exists in which every process can obtain its remaining resources and finish. The Banker's algorithm is a classic avoidance method, but it requires advance information about maximum resource needs.

Deadlock detection and recovery allow deadlocks to occur, then periodically search for cycles or unsatisfied resource claims. Recovery may terminate one or more processes, preempt resources, or roll processes back to earlier checkpoints. The choice should consider lost work, process priority, restart cost, and data consistency.

Deadlock differs from starvation. In deadlock, a group of processes waits permanently for one another. In starvation, an individual process waits indefinitely because scheduling or allocation repeatedly favors others. Aging can reduce starvation, but it does not by itself solve every deadlock.

Applied Case: Scheduling and Locking in a Retail Order System

Background

This illustrative case concerns an online retailer whose order-processing application uses several threads: an order-entry thread, a payment thread, an inventory thread, and a reporting thread.

Problem

Customers report slow checkout during peak periods. Occasionally, payment and inventory operations stop responding. Investigation shows that payment threads lock the order record and then request the payment resource, while inventory threads lock the payment resource and then request the order record.

Analysis

The checkout delay is partly a scheduling problem. Long report-generation bursts enter the same ready queue as interactive checkout threads, increasing response time. The stoppage is a deadlock: the order lock and payment resource are mutually exclusive; each thread holds one resource while waiting for the other; resources are not preempted; and the two waits form a cycle.

Approach and Solution

The company uses a priority-aware feedback scheduler so that interactive checkout work receives prompt service while long reports gradually move to a lower queue. Developers also impose one global lock order: every operation must acquire the payment resource before the order lock. Timeouts and deadlock monitoring are added as secondary safeguards. Shared data updates are placed in short critical sections, and communication between services uses messages with transaction identifiers.

Outcome and Learning Points

Response time improves because interactive work is not forced to wait behind long batch jobs. The fixed lock order removes the circular-wait condition. The case demonstrates that scheduling, synchronization, IPC, and deadlock management are related but distinct responsibilities. A scheduling policy cannot repair an incorrectly designed locking protocol, and a lock protocol cannot compensate for an unsuitable scheduling policy.

Challenges, Governance, and Best Practices

Process management involves more than performance. Excessive privileges can allow a process to interfere with other processes, so operating systems should apply least privilege, memory protection, authentication, and audit logging. IPC channels should validate inputs and protect confidential data. Administrators should monitor CPU usage, queue lengths, process creation, and abnormal termination without collecting unnecessary personal information.

Practical best practices include selecting scheduling policies according to workload; measuring response time as well as throughput; keeping critical sections short; documenting lock order; avoiding unnecessary shared state; handling failed or terminated processes; using timeouts carefully; and testing under realistic concurrency. Modern systems also combine CPU scheduling with multicore placement, energy management, containers, and virtual machines. These developments increase flexibility but make performance diagnosis more complex because several schedulers may operate at different layers.

Chapter Summary

A process is a program in execution, while a PCB stores the state and management information required to control it. Processes move among new, ready, running, waiting, and terminated states. Threads are independently schedulable execution units that share resources within a process; they improve responsiveness and scalability but introduce race conditions and synchronization challenges. Concurrency involves overlapping progress, whereas parallelism involves simultaneous execution on multiple cores.

Context switching saves one execution context and restores another, enabling multitasking at a cost of overhead. IPC allows processes to exchange information through shared memory, message passing, pipes, sockets, and related mechanisms. CPU scheduling aims to balance utilization, throughput, turnaround time, waiting time, response time, and fairness. FCFS is simple but can suffer from the convoy effect; SJF minimizes average waiting under suitable assumptions; priority scheduling supports urgency but may cause starvation; Round Robin supports interactive responsiveness; and feedback queues adapt to process behavior.

Deadlock requires mutual exclusion, hold and wait, no preemption, and circular wait. Operating systems manage it through prevention, avoidance, detection and recovery. Effective process management therefore combines scheduling policy, synchronization, communication design, security, and performance measurement.

Key Terms

Process: A program in execution.

Program: Passive instructions stored for execution.

Process state: The current condition of a process, such as ready or blocked.

Process control block: Operating-system record containing process management information.

Thread: Independently schedulable execution unit within a process.

Concurrency: Overlapping progress of multiple activities.

Parallelism: Simultaneous execution on multiple processing resources.

Context switch: Saving one execution context and restoring another.

Critical section: Code that accesses shared data and requires controlled execution.

Race condition: Incorrect behavior caused by timing-dependent concurrent access.

Inter-process communication: Mechanisms that allow processes to exchange data and coordinate.

Shared memory: IPC using a memory region accessible to multiple processes.

Message passing: IPC using explicit send and receive operations.

CPU scheduling: Selecting a ready process or thread for processor service.

Turnaround time: Completion time minus arrival time.

Response time: First service time minus arrival time.

Starvation: Indefinite waiting caused by repeated preference for other activities.

Deadlock: Permanent blocking caused by circular resource waiting.

Safe state: A resource-allocation state from which all processes can still complete in some order.

Review Questions

Short Answer Questions

1. What is the difference between a program and a process?
2. List the five states in the standard process-state model.
3. What information is stored in a process control block?
4. Distinguish concurrency from parallelism.
5. Why can a very small Round Robin time quantum reduce performance?

Long Answer Questions

1. Explain process creation, state transitions, scheduling, and termination using the process-state model.
2. Compare processes and threads, including their resource-sharing benefits and synchronization risks.
3. Explain shared-memory and message-passing IPC and identify suitable applications for each.
4. Compare FCFS, SJF, priority, Round Robin, and multilevel feedback-queue scheduling.
5. Explain the four necessary conditions for deadlock and compare prevention, avoidance, detection, and recovery.

Analytical / Application Questions

1. Three processes arrive at time 0 with CPU bursts of 6 ms, 3 ms, and 1 ms. Calculate the average waiting time under FCFS in the listed order and under non-preemptive SJF. Explain the difference.
2. A payment thread holds a customer-record lock while waiting for a payment-service lock, while another thread holds the payment-service lock while waiting for the customer-record lock. Identify the deadlock conditions and propose two remedies.
3. An organization reports poor user response whenever large analytical reports run. Recommend a scheduling strategy and two programming or IPC practices that could improve responsiveness without causing unfair starvation.

Multiple Choice Questions with Answers

Question 1

Which structure stores a process's program counter, registers, state, and scheduling information?

A. File allocation table

B. Process control block

C. Message queue

D. Page frame

Correct Answer: B. Process control block

Question 2

A process that is waiting for disk input/output is normally in which state?

A. Ready

B. Running

C. Waiting or blocked

D. New

Correct Answer: C. Waiting or blocked

Question 3

Which statement correctly distinguishes concurrency from parallelism?

A. Concurrency requires multiple processors, but parallelism does not

B. Concurrency means overlapping progress, while parallelism means simultaneous execution

C. They are exactly identical concepts

D. Parallelism can occur only in a single-threaded process

Correct Answer: B. Concurrency means overlapping progress, while parallelism means simultaneous execution

Question 4

What is a major risk of two threads updating shared data without synchronization?

A. Dead code elimination

B. Race condition

C. File compression

D. Guaranteed fairness

Correct Answer: B. Race condition

Question 5

Which scheduling algorithm gives each ready process a repeating time quantum?

A. First-Come, First-Served

B. Shortest-Job-First

C. Round Robin

D. Static partitioning

Correct Answer: C. Round Robin

Question 6

A process arrives at time 2 ms and completes at time 11 ms. What is its turnaround time?

A. 2 ms

B. 9 ms

C. 11 ms

D. 13 ms

Correct Answer: B. 9 ms

Question 7

Which scheduling method is most directly associated with the convoy effect?

A. FCFS

B. Round Robin

C. Shortest-Remaining-Time-First

D. Multilevel feedback queue

Correct Answer: A. FCFS

Question 8

Which condition is necessary for a classical deadlock?

A. Unlimited preemption

B. Circular wait

C. Guaranteed aging

D. A single process with no resources

Correct Answer: B. Circular wait

Question 9

Which technique gradually increases the priority of a waiting process?

A. Aging

B. Spooling

C. Paging

D. Polling

Correct Answer: A. Aging

Question 10

Which IPC method requires explicit synchronization to prevent conflicting direct updates to shared data?

A. Shared memory

B. Program counter

C. Context switch

D. CPU burst

Correct Answer: A. Shared memory