What is the critical section problem in operating systems?

Since processes execute concurrently, any process can be interrupted mid-execution. In the case of shared resources, partial execution of processes can lead to data inconsistencies. When two processes access and manipulate the shared resource concurrently, and the resulting execution outcome depends on the order in which processes access the resource; this is called a race condition.

Race conditions lead to inconsistent states of data. Therefore, we need a synchronization protocol that allows processes to cooperate while manipulating shared resources, which essentially is the critical section problem.

Solutions to the critical section problem

Any solution to the critical section problem must satisfy the following requirements:

Mutual exclusion: When one process is executing in its critical section, no other process is allowed to execute in its critical section.
Progress: When no process is executing in its critical section, and there exists a process that wishes to enter its critical section, it should not have to wait indefinitely to enter it.
Bounded waiting: There must be a bound on the number of times a process is allowed to execute in its critical section, after another process has requested to enter its critical section and before that request is accepted.

Most solutions to the critical section problem utilize locks implemented on software. The solutions include:

test_and_set

Uses a shared boolean variable lock and the test_and_set instruction that executes atomically and sets the passed parameter value to true.

#include <iostream>
#include <thread>
#include <atomic>
std::atomic<bool> lock(false); // Test-and-set lock
void critical_section(int id) {
    while (lock.exchange(true)){}; // Keep trying to acquire the lock until it's successfully obtained
    std::cout << "Thread " << id << " entered critical section" << std::endl;
    
    // Critical section
    std::this_thread::sleep_for(std::chrono::seconds(1)); // Simulating some work
    std::cout << "Thread " << id << " performing critical work" << std::endl;
    
    std::cout << "Thread " << id << " exited critical section" << std::endl;
    lock.store(false); // Release the lock
}
int main() {
    std::thread t1(critical_section, 1);
    std::thread t2(critical_section, 2);
    t1.join();
    t2.join();
    return 0;
}

Explanation

Line 5: We define an std::atomic<bool> named lock to serve as a test-and-set lock.
Line 7 & 8: The critical_section function makes attempts to acquire the lock using a while loop with lock.exchange(true). The exchange method atomicallyThis ensures that the lock operation appears to happen instantaneously and cannot be interrupted or interleaved by other threads. sets the value of the atomic variable to true and returns its previous value.
Line 16: The lock is released by setting the value of the atomic variable back to false using lock.store(false).

compare_and_swap

Same as test_and_set, except that the passed parameter value is set to true if it is equal to expected in the parameter of the compare_and_swap instruction.

#include <iostream>
#include <atomic>
#include <thread>
#include <vector>
int main() {
    // Shared variable
    std::atomic<int> critical_section_variable(0);
    // Function representing the critical section
    auto critical_section = [&critical_section_variable](int id) {
        // Non-critical section
        std::cout << "Thread " << id << " is outside the critical section" << std::endl;
        // Enter the critical section using CAS operation
        bool lock_acquired = false;
        int retry_limit = 100; // Set a retry limit
        int retries = 0;
        while (!lock_acquired && retries < retry_limit) {
            // Attempt to acquire the lock using CAS operation
            int expected_value = 0;
            lock_acquired = critical_section_variable.compare_exchange_strong(expected_value, 1);
            // If the lock is acquired, enter the critical section
            if (lock_acquired) {
                std::cout << "Thread " << id << " entered the critical section" << std::endl;
                // Critical section:
                for (int i = 0; i < 1000000; ++i) {
                    critical_section_variable += 1;
                }
                // Exit the critical section by releasing the lock
                critical_section_variable = 0;
                std::cout << "Thread " << id << " exited the critical section" << std::endl;
            } else {
                // If the lock is not acquired, retry
                std::cout << "Thread " << id << " failed to acquire the lock, retrying..." << std::endl;
                retries++;
            }
        }
        if (retries == retry_limit) {
            std::cout << "Thread " << id << " reached retry limit. Exiting..." << std::endl;
        }
    };
    // Create two threads
    std::vector<std::thread> threads;
    for (int i = 0; i < 2; ++i) {
        threads.emplace_back(critical_section, i);
    }
    // Join the threads
    for (auto& thread : threads) {
        thread.join();
    }
    return 0;
}

Explanation

Line 8: We define a shared variable critical_section_variable of type std::atomic<int> to ensure atomicity Atomic operations are essential to ensure that data accessed by multiple threads is properly synchronized and prevents race conditions. in accessing and modifying its value across threads.
Line 10-45: We define a lambda function critical_section . It represents the critical section of our code. Inside this function, each thread try to acquire the critical section while ensuring exclusive access using a compare-and-swap (CAS) operation.
- Inside the critical_section function, in the loop thread makes attempt to acquire the lock using compare_exchange_strong. If the attempt fails (i.e., the CAS operation returns false), the thread retries.
- The compare-and-swap (CAS) operation is performed by compare_exchange_strong, which atomically compares the current value of critical_section_variable with the expected value (0) and updates it to 1 if the comparison succeeds.
- To avoid the infinite tries to acquire the critical section, we introduce a retry_limit. If a thread reaches this limit without acquiring the lock, it prints a message and exits.
Line 48-56: We create two threads and pass their IDs to the critical section function. We join all the threads and ensure that all threads finish before exiting.

Mutex locks

Software method that provides the acquire() and release() functions that execute atomically.

#include <iostream>
#include <thread>
#include <mutex>
std::mutex mtx; // Mutex for critical section
void critical_section(int id) {
    // Entry section
    mtx.lock(); // Lock the mutex to enter the critical section
    std::cout << "Thread " << id << " entered critical section" << std::endl;
    
    // Critical section
    std::this_thread::sleep_for(std::chrono::seconds(1)); // Simulating some work
    std::cout << "Thread " << id << " performing critical work" << std::endl;
    
    // Exit section
    std::cout << "Thread " << id << " exited critical section" << std::endl;
    mtx.unlock(); // Unlock the mutex to exit the critical section
}
int main() {
    std::thread t1(critical_section, 1);
    std::thread t2(critical_section, 2);
    t1.join();
    t2.join();
    return 0;
}

Explanation

Line 5: We declare mutex mtx; to synchronize access to the critical section.
Line 7: We define critical_section and we pass the thread id.
Line 13: It pauses the execution of the thread for 1 second using std::this_thread::sleep_for.
Line 21-29: We create two threads t1 and t2 . Then, the main thread waits for t1 and t2 to finish executing by calling join() on each thread.

Semaphores

More sophisticated methods that utilize the wait() and signal() operations that execute atomically on Semaphore S, which is an integer variable.

#include <iostream>
#include <thread>
#include <semaphore.h>
// Define semaphore
sem_t semaphore;
void critical_section(int id) {
    // Entry section
    sem_wait(&semaphore); 
    std::cout << "Thread " << id << " entered critical section" << std::endl;
    
    // Critical section
    std::this_thread::sleep_for(std::chrono::seconds(1)); 
    std::cout << "Thread " << id << " performing critical work" << std::endl;
    
    // Exit section
    std::cout << "Thread " << id << " exited critical section" << std::endl;
    sem_post(&semaphore); // Release semaphore
}
int main() {
    // Initialize semaphore
    sem_init(&semaphore, 0, 1); 
    // Create threads
    std::thread t1(critical_section, 1);
    std::thread t2(critical_section, 2);
    // Join threads
    t1.join();
    t2.join();
    
    sem_destroy(&semaphore);
    return 0;
}

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <queue>
#include <chrono>
std::mutex mtx;  // Mutex for critical section
std::condition_variable cv;  
std::queue<int> processQueue; 
bool inCriticalSection = false;  
void process(int id) {
    // Entry section
    {
        std::unique_lock<std::mutex> lock(mtx);
        processQueue.push(id);  
        cv.wait(lock, [id] { return (processQueue.front() == id) && !inCriticalSection; });
        processQueue.pop();  
        inCriticalSection = true;  
    }
    // Critical section
    std::cout << "Process " << id << " entered critical section." << std::endl;
    std::this_thread::sleep_for(std::chrono::seconds(1));  // Simulate critical section work
    std::cout << "Process " << id << " completed critical section." << std::endl;
    // Exit section
    {
        std::lock_guard<std::mutex> lock(mtx);
        inCriticalSection = false;  
        if (!processQueue.empty()) {
            cv.notify_one(); 
        }
    }
}
int main() {
    std::thread t1(process, 1);
    std::thread t2(process, 2);
    std::thread t3(process, 3);
    t1.join();
    t2.join();
    t3.join();
    return 0;
}

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

What is the critical section problem in operating systems?

Solutions to the critical section problem

test_and_set

Explanation

compare_and_swap

Explanation

Mutex locks

Explanation

Semaphores

Explanation

Condition variables

Explanation