Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 144 views

    Classical Problems of Synchronization

    Uploaded by

    veeramat
    The document describes three classical synchronization problems: 1) The bounded buffer problem involves a producer inserting data into a fixed size buffer and a consumer removing data, with conditions to prevent overflow or underflow. 2) The readers-writers problem allows multiple readers to access shared data simultaneously but only one writer at a time using semaphores. 3) In the dining philosophers problem, philosophers take turns thinking and eating with shared chopsticks, requiring synchronization to prevent deadlock.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Classical Problems of Synchronization

    Uploaded by

    veeramat
    144 views10 pages
    The document describes three classical synchronization problems: 1) The bounded buffer problem involves a producer inserting data into a fixed size buffer and a consumer removing data, with conditions to prevent overflow or underflow. 2) The readers-writers problem allows multiple readers to access shared data simultaneously but only one writer at a time using semaphores. 3) In the dining philosophers problem, philosophers take turns thinking and eating with shared chopsticks, requiring synchronization to prevent deadlock.

    Original Description:

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes three classical synchronization problems: 1) The bounded buffer problem involves a producer inserting data into a fixed size buffer and a consumer removing data, with conditions to prevent overflow or underflow. 2) The readers-writers problem allows multiple readers to access shared data simultaneously but only one writer at a time using semaphores. 3) In the dining philosophers problem, philosophers take turns thinking and eating with shared chopsticks, requiring synchronization to prevent deadlock.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    144 views10 pages

    Classical Problems of Synchronization

    Uploaded by

    veeramat
    The document describes three classical synchronization problems: 1) The bounded buffer problem involves a producer inserting data into a fixed size buffer and a consumer removing data, with conditions to prevent overflow or underflow. 2) The readers-writers problem allows multiple readers to access shared data simultaneously but only one writer at a time using semaphores. 3) In the dining philosophers problem, philosophers take turns thinking and eating with shared chopsticks, requiring synchronization to prevent deadlock.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 10

    Classical Problems of Synchronization

    1. Bounded-Buffer Problem
    2. Readers and Writers Problem
    3. Dining-Philosophers Problem
    Bounded-Buffer Problem
    Bounded-Buffer Problem
    Two Process: Fixed Size Buffer

    1. Producer
    2. Consumer

    Producer: Insert one unit of data into the buffer


    Consumer: Remove one unit of data from the buffer
    Condition:
    The producer must not insert data into the buffer when it is full

    The Consumer must not remove the data when the buffer is empty
    Producer:
    do { wait(S) {
    while (S <= 0); // busy wait
    wait(empty); //Decrease the Empty S--;
    wait(mutex); //Acquire the lock }
    ...
    //Insert Data into the Buffer
    ... signal(S) {
    S++;
    signal(mutex); //Release the lock }
    signal(full); // Increase the Full
    } while (true);

    Consumer
    do {
    wait(full); // Decrease the full
    wait(mutex); //Acquire the lock
    ...
    /* Remove an item from the buffer
    ...
    signal(mutex); // Release the lock
    signal(empty); // Increase the empty
    ...
    } while (true);
    Readers and Writers Problem
    Readers and Writers Problem
    • A data set is shared among a number of concurrent processes
    • Readers – only read the data set; they do not perform any updates
    • Writers – can both read and write

    • Problem – allow multiple readers to read at the same time


    • Only one single writer can access the shared data at the same time

    • Several variations of how readers and writers are considered – all involve some form of priorities

    • Shared Data
    • Data set
    • Semaphore rw_mutex initialized to 1
    • Semaphore mutex initialized to 1
    • Integer read_count initialized to 0
    Readers and Writers Problem
    signal(S) {
    S++;
    }

    Reader:
    wait(S) {
    do { while (S <= 0); // busy
    wait(mutex); wait
    read_count++; S--;
    if (read_count == 1) }
    wait(rw_mutex);
    signal(mutex);
    ... Writer Process:
    /* reading is performed */ do {
    ... wait(rw_mutex);
    wait(mutex); ...
    read count--; /* writing is performed */
    if (read_count == 0) ...
    signal(rw_mutex); signal(rw_mutex);
    signal(mutex); } while (true);
    } while (true);
    Dining-Philosophers Problem

    • Philosophers spend their lives alternating thinking and eating


    • Don’t interact with their neighbors, occasionally try to pick up 2 chopsticks
    (one at a time) to eat from bowl
    • Need both to eat, then release both when done
    • In the case of 5 philosophers
    • Shared data
    • Bowl of rice (data set)
    • Semaphore chopstick [5] initialized to 1

    12/28/2023 21CSC202J Operating Systems UNIT 2 8


    Dining-Philosophers Problem Algorithm
    • The structure of Philosopher i:
    do {
    wait (chopstick[i] );
    wait (chopStick[ (i + 1) % 5] );

    // eat

    signal (chopstick[i] );
    signal (chopstick[ (i + 1) % 5] );

    // think

    } while (TRUE);

    • What is the problem with this algorithm?

    12/28/2023 21CSC202J Operating Systems UNIT 2 9


    Dining-Philosophers Problem Algorithm (Cont.)

    • Deadlock handling
    • Allow at most 4 philosophers to be sitting
    simultaneously at the table.
    • Allow a philosopher to pick up the forks only if both
    are available (picking must be done in a critical section.
    • Use an asymmetric solution -- an odd-numbered
    philosopher picks up first the left chopstick and then
    the right chopstick. Even-numbered philosopher picks
    up first the right chopstick and then the left chopstick.

    12/28/2023 21CSC202J Operating Systems UNIT 2 10

    You might also like