Critical Section Solutions

Lock: The primary purpose of a lock is to enforce mutual exclusion, which means that only one process or thread can hold the lock at any given time and access the critical section. 

  • Locking: When a process or thread wants to enter a critical section, it must first acquire the lock. If the lock is already held by another process or thread, the requesting process must wait until the lock is released. 
  • Unlocking: After the process or thread has finished its operation in the critical section, it releases the lock, allowing other waiting processes or threads to acquire it. 
  • Mutex (Mutual Exclusion Object): A simple binary lock where the lock can either be held (locked) or not held (unlocked). Only the process that locked the mutex (lock) can unlock it.
  • Disadvantages of locks:
  1. A scenario where a lower-priority thread holds a lock that a higher-priority thread needs, causing the higher-priority thread to wait or vice versa.
  2. When a process holding a lock dies or is terminated unexpectedly, the lock it holds may not be released properly. This leaves other processes waiting for the lock in a state of indefinite blocking.
  3. Deadlock occurs when a set of processes are unable to proceed because each process is waiting for a resource held by another process in the set. This creates a cycle of dependencies, where no process can proceed or release resources. For example, process A holds Lock1 and needs Lock2 to proceed. Process B holds Lock2 and needs Lock1 to proceed. Process A and Process B are now in a deadlock situation because each is waiting for the other to release the lock it needs.
Semaphore: A semaphore is similar to a lock, but it's a more advanced solution. A lock (or mutex) is binary—it can be either locked or unlocked, allowing one thread to enter the critical section whereas, a semaphore can have a value (often called a "counter") that allows more than one thread to access the shared resource. 
  • A semaphore helps manage access to resources that have multiple copies or instances. 
  • Imagine you have 3 printers in an office that have a common or single critical section, then up to 3 threads can be sent together to the critical section. If all are in use, others must wait. 
In detail process:
  • A thread that wants to use a printer will "wait" on the semaphore. 
  • If the semaphore value is greater than 0 (meaning there are available printers), the semaphore value is decremented. The thread then enters the critical section (uses a printer). 
  • Semaphore Value 0: If the semaphore value is 0 (meaning all printers are in use), the thread is blocked. It cannot proceed into the critical section because no printers are available. 
  • Blocking and CPU Utilization: When a thread is blocked due to the semaphore value being 0, it doesn't use CPU time while it waits. Instead, the CPU can perform other tasks or handle other threads that are not blocked. The blocked thread remains in a waiting state until a printer becomes available. 
  • When another thread finishes using a printer and signals (increments) the semaphore, the blocked thread is awakened and can then enter the critical section. 

Petersons algorithm: It is a classic solution for achieving mutual exclusion in concurrent programming, specifically in the context of two processes. It ensures that only one process can enter its critical section at a time, preventing race conditions. It is an enhanced version of single flag.


Comments

Post a Comment

Popular posts from this blog

Indexed allocation

Image
  Indexed allocation is a file allocation method used by operating systems to manage how files are stored on disk. The core idea is simple but powerful: instead of storing a file in contiguous blocks or linking blocks one-by-one, the system uses a special index block that contains a list of all the disk block addresses where the file’s data is stored. This removes many limitations of earlier methods like contiguous and linked allocation. In indexed allocation, each file has its own index block . This index block acts like a table of contents. Every entry inside it points to a data block that belongs to that file. When a file is created, the OS allocates an index block and then fills it with pointers to the actual data blocks as the file grows. These data blocks can be located anywhere on the disk , so the file does not need contiguous space. This makes storage much more flexible and avoids external fragmentation. When the system needs to access a particular part of a file, it fir...
Read more

Thrashing

Image
Thrashing occurs in a computer system when the operating system spends a significant amount of time swapping pages in and out of memory, rather than executing actual processes. This typically happens when the system's memory is overcommitted, meaning there are too many processes competing for too little physical memory, leading to frequent page faults. How Memory is Used 1. Initial State: App1 is running, and its two pages are loaded into memory: Frame 1: App1, Page 1 Frame 2: App1, Page 2 Frame 3 and 4 are free. App3's pages are present in swap memory. 2. Switch to App2: Now, you switch to App2, which also requires 2 pages: Frame 3: App2, Page 1 Frame 4: App2, Page 2 Memory is now full with both App1 and App2’s pages. App3's pages are present in swap memory. 3. Switch to App3: You decide to switch to App3, which needs 2 pages as well. Since the memory is full, the system needs to make room: App1’s pages are moved to swap memory: Swap Memory: [App1, Page 1] [App1, Page 2] F...
Read more

Basics of paging

Image
Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory and thus helps in handling fragmentation. It involves breaking down memory into fixed-size blocks called pages and frames. The OS typically decides the page size when the system is configured or during the OS design phase. This page size is constant for the entire system and is determined based on considerations such as hardware architecture, efficiency, and the type of applications running. Common page sizes are 4 KB, 8 KB, or 16 KB. Here's a simple explanation with an example: Basic Concepts Page: A fixed-size block of logical memory (virtual memory) used by a process. Frame: A fixed-size block of physical memory (RAM) where a page is mapped. Page Table: A data structure used by the operating system to keep track of the mapping between pages and frames. The Page Table Base Register (PTBR) is a special register in the CPU that holds the starting address of the page table for ...
Read more