Scribd Logo
Upload

Welcome to Scribd!

  • 83 views

    Bounded-Buffer Problem

    Uploaded by

    Sri Kanth
    The Bounded Buffer Problem document describes a problem where there are N buffers that can each hold one item. It uses semaphores - mutex, full, and empty - to coordinate access between producer and consumer processes. The producer waits on empty and mutex to add an item, then signals full and mutex. The consumer waits on full and mutex to remove an item, then signals empty and mutex.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPTX, PDF, TXT or read online from Scribd

    Bounded-Buffer Problem

    Uploaded by

    Sri Kanth
    83 views9 pages
    The Bounded Buffer Problem document describes a problem where there are N buffers that can each hold one item. It uses semaphores - mutex, full, and empty - to coordinate access between producer and consumer processes. The producer waits on empty and mutex to add an item, then signals full and mutex. The consumer waits on full and mutex to remove an item, then signals empty and mutex.

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The Bounded Buffer Problem document describes a problem where there are N buffers that can each hold one item. It uses semaphores - mutex, full, and empty - to coordinate access between producer and consumer processes. The producer waits on empty and mutex to add an item, then signals full and mutex. The consumer waits on full and mutex to remove an item, then signals empty and mutex.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    83 views9 pages

    Bounded-Buffer Problem

    Uploaded by

    Sri Kanth
    The Bounded Buffer Problem document describes a problem where there are N buffers that can each hold one item. It uses semaphores - mutex, full, and empty - to coordinate access between producer and consumer processes. The producer waits on empty and mutex to add an item, then signals full and mutex. The consumer waits on full and mutex to remove an item, then signals empty and mutex.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    You are on page 1of 9

    Bounded-Buffer Problem

    • N buffers, each can hold one item


    • Semaphore mutex initialized to the value 1
    • Semaphore full initialized to the value 0
    • Semaphore empty initialized to the value N.
    Bounded Buffer Problem (Cont.)
    • The structure of the producer process

    do {
    // produce an item in nextp
    wait (empty);
    wait (mutex);
    // add the item to the buffer
    signal (mutex);
    signal (full);
    } while (TRUE);
    The structure of the consumer process
    do {
    wait (full);
    wait (mutex);
    // remove an item from buffer to nextc
    signal (mutex);
    signal (empty);
    // consume the item in nextc
    } while (TRUE);
    Readers-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
    Shared Data
    – Data set
    – Semaphore mutex initialized to 1
    – Semaphore wrt initialized to 1
    – Integer readcount initialized to 0
    Readers-Writers Problem

    • The structure of a writer process


    do {
    wait (wrt) ; // writing is performed
    signal (wrt) ;
    } while (TRUE);
    The structure of a reader process
    do {
    wait (mutex) ;
    readcount ++ ;
    if (readcount == 1)
    wait (wrt) ;
    signal (mutex) //reading is performed wait (mutex) ;
    readcount - - ;
    if (readcount == 0)
    signal (wrt) ;
    signal (mutex) ;
    } while (TRUE);
    Dining-Philosophers Problem
    • Shared data
    – Bowl of rice (data set)
    – Semaphore chopstick [5] initialized to 1
    do {
    • wait ( chopstick[i] );
    • wait ( chopStick[ (i + 1) % 5] );
    •
    • // eat

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

    • } while (TRUE);
    Monitors

    • A high-level abstraction that provides a convenient and


    effective mechanism for process synchronization
    • Only one process may be active within the monitor at a
    time
    monitor monitor-name
    {
    // shared variable declarations
    procedure P1 (…) { …. }
    …

    procedure Pn (…) {……}

    Initialization code ( ….) { … }


    …
    }
    }
    Solution to Dining Philosophers

    monitor DP
    { enum { THINKING; HUNGRY, EATING) state [5] ;
    condition self [5];
    void pickup (int i) {
    state[i] = HUNGRY;
    test(i);
    if (state[i] != EATING) self [i].wait;
    }
    void putdown (int i) {
    state[i] = THINKING;
    // test left and right neighbors
    test((i + 4) % 5);
    test((i + 1) % 5);
    }
    void test (int i) {
    if ( (state[(i + 4) % 5] != EATING) &&
    (state[i] == HUNGRY) &&
    (state[(i + 1) % 5] != EATING) ) {
    state[i] = EATING ;
    self[i].signal () ;
    } }
    initialization_code() {
    for (int i = 0; i < 5; i++)
    state[i] = THINKING;
    } }
    • Each philosopher I invokes the operations pickup() and putdown() in the following
    sequence:
    DiningPhilosophters.pickup (i);
    EAT
    DiningPhilosophers.putdown (i);
    Monitor Implementation Using Semaphores Variables
    semaphore mutex; // (initially = 1)
    semaphore next; // (initially = 0)
    int next-count = 0;
    Each procedure F will be replaced by
    • wait(mutex);
    …
    body of F;
    …
    if (next_count > 0)
    signal(next)
    else
    signal(mutex);

    • Mutual exclusion within a monitor is ensured.


    Monitor Implementation
    • For each condition variable x, we have:

    semaphore x_sem; // (initially = 0)


    int x-count = 0;

    • The operation x.wait can be implemented as:

    x-count++;
    if (next_count > 0)
    signal(next);
    else
    signal(mutex);
    wait(x_sem);
    x-count--;

    You might also like