Hardware Instructions for Synchronization

 

Hardware Instructions for Synchronization

Why Hardware Instructions Are Needed

Software-only solutions to the critical-section problem cannot be relied upon on modern processors. This is because:

  • Instructions may be reordered

  • Multiple cores may access memory simultaneously

To solve this, modern systems provide special hardware instructions that execute atomically, meaning:

They complete as a single, indivisible operation and cannot be interrupted.

These instructions form the foundation of synchronization mechanisms in operating systems.

Atomic Operations

An atomic operation ensures that:

  • No other process can observe a partial update

  • Concurrent executions are serialized in some order

Two commonly used atomic instructions are:

  1. Test-and-Set

  2. Compare-and-Swap (CAS)

Test-and-Set Instruction

Concept

The test-and-set() instruction:

  • Reads the value of a variable

  • Sets it to true

  • Returns the old value

  • All in one atomic step

How It Works

  • A shared boolean variable lock is initialized to false

  • A process repeatedly executes test-and-set on lock

  • If the old value was false, the process enters the critical section

  • If it was true, the process keeps waiting (busy waiting)

Why It Works

  • Only one process at a time can change lock from false to true

  • This guarantees mutual exclusion




Limitation

  • It causes busy waiting

  • It does not guarantee bounded waiting

    • A process may starve indefinitely



Compare-and-Swap (CAS) Instruction

Concept

The compare-and-swap() instruction operates on three values:

  1. A memory location

  2. An expected value

  3. A new value

It performs the following atomically:

  • Compares the memory value with the expected value

  • Updates the memory only if they match

  • Returns the original value



Mutual Exclusion Using CAS

How It Works

  • A shared integer variable lock is initialized to 0

  • A process tries to change lock from 0 to 1

  • The first process succeeds and enters the critical section

  • Others fail and continue waiting

  • When the process exits, it resets lock to 0

Why It Works

  • CAS ensures only one process can acquire the lock

  • Atomic execution prevents race conditions


Bounded Waiting with CAS

Problem

Simple CAS-based locking:

  • Guarantees mutual exclusion

  • But does not guarantee bounded waiting

Solution

  • Use an additional array waiting[n]

  • Each process announces its intention to enter the critical section

  • When a process exits, it explicitly hands off the lock to the next waiting process in a cyclic order

Result

This enhanced CAS-based algorithm satisfies all three critical-section requirements:

  1. Mutual exclusion

  2. Progress

  3. Bounded waiting

Hardware Support for Atomicity

How CAS Is Made Atomic in Practice

  • On Intel x86 systems, CAS is implemented using the cmpxchg instruction

  • The lock prefix ensures:

    • Exclusive access to the memory bus

    • Atomic execution across multiple processors

Key Takeaways

Feature    Test-and-Set        Compare-and-Swap
Atomic    Yes            Yes
Mutual Exclusion    Yes            Yes
Bounded Waiting    No            Yes (with extra logic)
Busy Waiting        Yes            Yes
Hardware Support    Required            Required

Final Summary

Hardware synchronization instructions provide:

  • Atomicity, which software alone cannot guarantee

  • A reliable way to implement mutual exclusion

  • The building blocks for higher-level synchronization tools like mutexes and semaphores

Without hardware instructions such as test-and-set and compare-and-swap, modern operating systems cannot safely support concurrency.

Comments

Post a Comment

Popular posts from this blog

Operating Systems OS PCCST403 Semester 4 BTech KTU CS 2024 Scheme

 About Me Scheme and Syllabus Module-1 Introduction and CPU Scheduling Introduction to OS - 3 important pieces- virtualization, concurrency, persistence Operating System Services Operating System and Kernel Linux Versus Classic Unix Kernels Difference between Linux and Unix Kernels Process and Process Creation- overview Process States in Operating System Data Structures in Operating Systems Key Aspects of a Program and Process in an Operating System-Summary Sharing the Processor Among Processes System Boot Sequence Threads and Concurrency Case Study: Linux Kernel Process management Case Study: Linux Implementation of Threads CPU Scheduling Multi-level feedback Queue ( MLFQ) Scheduler How MLFQ Approximates Shortest Job First (SJF) I/O in MLFQ Problems With the Basic MLFQ Scheduler Solving the Issues with MLFQ Scheduler Case Study: Linux Completely Fair Scheduler (CFS) Module-2 Concurrency and Synchronization Tools Concurrency and Synchronization- Basic principles Critical secti...
Read more

Introduction to Operating System -Virtualization, Concurrency, and Persistence

  How Operating Systems Really Work: Virtualization, Concurrency, and Persistence Have you ever wondered how your laptop can play music, run a web browser, download files, and open a Word document—all at the same time—without melting down? It might look simple, but beneath the surface, your operating system (OS) is doing incredibly sophisticated work. In this , we’ll break down the three most important ideas that make modern operating systems possible: Virtualization Concurrency Persistence These concepts are the foundation of how computers manage programs(applications), memory, and data.  1. Virtualization: Making One Computer Look Like Many Virtualization is all about creating useful illusions . You might have Spotify playing, Instagram open, and a browser loading—all on one phone. It feels like all apps run simultaneously, but the phone is rapidly switching between them so smoothly you don’t notice. Virtualization = making one CPU appear like many. Ev...
Read more

Differences Between Linux and Classic UNIX Kernels

  Differences Between Linux and Classic UNIX Kernels Although Linux and classic UNIX kernels share a common heritage and a similar system-call interface, Linux introduces several important design improvements that distinguish it from traditional UNIX systems. 1. Dynamic Kernel Modules Linux supports dynamic loading and unloading of kernel modules at runtime. Even though Linux is a monolithic kernel , new functionality (such as device drivers) can be added without rebooting. Classic UNIX kernels are mostly static , requiring recompilation and reboot for changes. 2. Symmetric Multiprocessing (SMP) Support Linux has strong SMP support , allowing efficient use of multiple CPUs. Traditional UNIX implementations had limited or no SMP support. Many modern UNIX variants added SMP later, but Linux was designed with scalability in mind. 3. Kernel Preemption The Linux kernel is fully preemptive , meaning a running kernel task can be interrupted to improve r...
Read more