Soban Khan
UW-22-AI-BS-052
BS AI 5th Semester
OS
Assignment: 3
Submitted To:
Ma’am Sadia
Solution to the Reader-Writer Problem:
Design:
The proposed solution implements several strategies to effectively manage access to the shared
database while ensuring fairness, preventing deadlocks, and allowing for efficient reader-writer
synchronization.
1. Fairness:
Writers are given mechanisms to ensure they are not starved by continuously arriving
readers.
A turnstile mechanism is introduced to ensure that readers and writers take turns
accessing the shared database.
2. Deadlock Prevention:
Proper ordering of semaphore acquisition and release is enforced to avoid circular
dependencies, thus preventing deadlocks.
3. Reader-Writer Synchronization:
Multiple readers can read simultaneously, but they must wait if a writer is currently
accessing the database.
Writers are granted exclusive access to the database.
4. Priority Management:
Readers have higher priority by default, but the turnstile semaphore ensures fairness
between readers and writers, preventing indefinite delays for writers.
Synchronization Mechanisms:
Semaphores:
reader_mutex: Protects the reader_count variable, ensuring no race conditions while
tracking active readers.
resource_access: Controls access to the shared database, allowing either one writer or
multiple readers.
write_queue: Ensures that writers get a fair chance to write without indefinite delays.
turnstile: Prevents writer starvation by queuing readers and writers fairly.
Rules for Access:
1. Reader:
Use the turnstile to prevent starvation of writers.
Increment reader_count using reader_mutex.
The first reader locks the resource_access semaphore.
After reading, decrement reader_count, and the last reader releases
the resource_access.
2. Writer:
Use write_queue to wait for its turn.
Use resource_access for exclusive access to the database.
Release resource_access and write_queue after writing.
Reader Algorithm
Acquire the reader_mutex semaphore.
Acquire the lock mutex.
Increment the reader_count variable.
If reader_count is 1, acquire the writer_mutex semaphore to prevent writers from accessing the
critical section.
Release the lock mutex.
Release the reader_mutex semaphore.
Access the critical section (read from the database).
Acquire the lock mutex.
Decrement the reader_count variable.
If reader_count is 0, release the writer_mutex semaphore to allow writers to access the critical
section.
Release the lock mutex.
Writer Algorithm
Acquire the writer_mutex semaphore.
Access the critical section (write to the database).
Release the writer_mutex semaphore.
Implementation:
import threading
# Shared variables
reader_count = 0 # Tracks number of active readers
reader_mutex = threading.Semaphore(1) # Mutex for reader_count access
resource_access = threading.Semaphore(1) # Access control for the database
write_queue = threading.Semaphore(1) # Ensures writers' fairness
turnstile = threading.Semaphore(1) # Prevents writer starvation
def ReadData():
print(f"Reader {threading.current_thread().name} is reading.")
def WriteData():
print(f"Writer {threading.current_thread().name} is writing.")
def Reader():
global reader_count
# Ensure writers aren't starved
turnstile.acquire()
turnstile.release()
# Lock reader_count
reader_mutex.acquire()
reader_count += 1
if reader_count == 1:
# First reader locks the resource
resource_access.acquire()
reader_mutex.release()
# Critical Section (Reading)
ReadData()
# Lock reader_count
reader_mutex.acquire()
reader_count -= 1
if reader_count == 0:
# Last reader releases the resource
resource_access.release()
reader_mutex.release()
def Writer():
# Wait for its turn
write_queue.acquire()
# Exclusive access to the database
resource_access.acquire()
# Critical Section (Writing)
WriteData()
# Release resource
resource_access.release()
write_queue.release()
# Example of creating threads for readers and writers
def main():
readers = [threading.Thread(target=Reader, name=f"Reader-{i}") for i in range(3)]
writers = [threading.Thread(target=Writer, name=f"Writer-{i}") for i in range(2)]
# Start all threads
for r in readers:
r.start()
for w in writers:
w.start()
# Wait for all threads to complete
for r in readers:
r.join()
for w in writers:
w.join()
if __name__ == "__main__":
main()
Description of the Solution:
1. Fairness:
The turnstile semaphore ensures that readers and writers access the database in the
order they arrive, preventing starvation of writers.
The write_queue semaphore ensures that writers wait in a fair queue, allowing them to
access the database when it is their turn.
2. Concurrency:
Multiple readers can read simultaneously by incrementing the reader_count variable,
allowing for efficient concurrent access.
Writers gain exclusive access to the database using the resource_access semaphore.
3. Synchronization:
The reader_mutex ensures that updates to the reader_count variable are atomic,
preventing race conditions.
Proper acquisition and release of semap
