What is the critical section problem in operating systems?

The critical section problem is used to design a protocol followed by a group of processes, so that when one process has entered its critical section, no other process is allowed to execute in its critical section.

The critical section refers to the segment of code where processes access shared resources, such as common variables and files, and perform write operations on them.

Typical structure followed by most processes

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;
}

Explanation

  • Line 10: sem_wait(&semaphore); is a call to the sem_wait function, which is used to wait on a semaphore until it becomes available.

  • Line 14: This line simulates some work being done inside the critical section.

  • Line 24: Initial value of semaphore is 1, representing availability

  • Line 35: We destroy the semaphore.

Condition variables

Utilizes a queue of processes that are waiting to enter the critical section.

#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;
}

Explanation

  • Line 8 & 9: We have a critical section guarded by a mutex (mtx) and a condition variable (cv).

  • Line 10: We make a Queue of processes waiting to access critical section.

  • Line 11: Flag indicating if critical section is being executed and it is set to false.

  • Line 20: Set flag indicating critical section is being executed.

  • Line 31: Reset flag indicating critical section is completed

  • Line 33: Signal the next process to enter critical section.

Copyright ©2024 Educative, Inc. All rights reserved