Computer Science. OPERATING SYSTEM - TOPIC: SEMAPHORES 1. Find a creative exampl

Question

Computer Science. OPERATING SYSTEM - TOPIC: SEMAPHORES

1. Find a creative example of synchronization that can demonstrate the difficulty of developing a semaphore-based solution similar to the “Pigeon Network.” Make sure that you develop your solution (in pseudocode) step by step, And vigorously discuss the Correctness and Pitfalls of each solution. PLEASE WRITE LEGIBLY, THANK YOU

This is just an example, It is not a complete answer. The simple implementation is missing (pseudo code).

EXAMPLE The Pigeon Network Scenario .Pigeons are good message carriers Reasonably reliable Relatively fast for less developed rural areas . Can sense magnetic field lines Here is the Story... .There are two towns-Mars and Venus Mars has all male pigeons Venus has all female pigeons Each town delivers messages to the other By sending a pigeon through the shared flving path And waiting for the same pigeon to fly back as an acknowledgement . Based on experience .Whenever both towns send messages simultaneously, the reliability drops significantly .Pigeons of opposite genders decide to take excursions . Goals of a pigeon network: .Efficiency .Fairness Developing the Solution Can we map it to already solved problems? Standard synchronization problems: Bounded buffer (producers and consumers) Fairness (readers and writers) Resource allocation (dining philosophers) Pigeon network is under the reader-writer category

Explanation / Answer

The shared resource in the above problem is “flying path”

Semaphore flyingPath =1;

P(flyingPath); //wait operation

// send message

V(flyingpath);    //send signal

+ Simple solution

+ Fair

Implementation 2: allow multiple pigeons from Venus

Shared resources : flying path

Counter- number of Venus pigeons

Semaphore flyingpath=1;

P(flyingPath); //wait operation

// send message

V(flyingpath);    //send signal

Semaphore venusLock=1;

Int venusPigeon =0;

++venusPigeon;

If(venusPigeon ==1){

    P(flyingPath);

}

//send message

-- venusPigeon;

If(venusPegion == 0 ) {

     V(flyingPath);

}

When venusPigeon = 2 , P(flyingpath) is not set while the pigeon is sending message another pigeon from Mars starts as P(flyingpath) is not set. So Mutual exclusion is violated

Implementation 3: allow multiple pigeons from Venus

Shared resources : flying path , venusLock

    Counter- number of Venus pigeons in transit

Semaphore flyingpath=1;

P(flyingPath); //wait operation

// send message

V(flyingpath);    //send signal

Int venusPigeon =0;

Semaphore venusLock =1;

P(venusLock);

++venusPigeon;

If(venusPigeon ==1){

    P(flyingPath);

}

//send message

-- venusPigeon;

If(venusPegion == 0 ) {

     V(flyingPath);

}

V(VenusLock);

Problem here is once the venusLock is set another pigeon in venus can’t transit

Implementation 4: allow multiple pigeons from Venus

Shared resources : flying path , venusLock

    Counter- number of Venus pigeons in transit

               

Semaphore flyingpath=1;

P(flyingPath); //wait operation

// send message

V(flyingpath);    //send signal

Int venusPigeon =0;

Semaphore venusLock =1;

P(venusLock);

++venusPigeon;

If(venusPigeon ==1){

    P(flyingPath);

}

V(venusLock);

//send message

P(venusLock);

-- venusPigeon;

If(venusPegion == 0 ) {

     V(flyingPath);

}

V(VenusLock);

This method is efficient for Venus pigeons but not for pegions from Mars

Efficient Solution : Allow multiple venus and mars pigeon to transit

Shared resources : flying path , venusLock MarsLock

    Counter- VenusPigeon: number of Venus pigeons in transit

                                MarsPigeon: number of Mars pigeon in transit

               

Semaphore flyingpath=1;

Semaphore MarsLock=1;

Int MarsPigeon =0;

P(marsLock);

++marsPigeon;

If(marsPigeon ==1){

      P(flyingPath);             //wait operation

}

V(MarsLock);

// send message

P(marsLock);

--MarsPigeon;

If( marsPigeon ==0) {

         V(flyingpath);           //send signal

}

V(marsLock);

Int venusPigeon =0;

Semaphore venusLock =1;

P(venusLock);

++venusPigeon;

If(venusPigeon ==1){

        P(flyingPath);

}

V(venusLock);

      //send message

P(venusLock);

-- venusPigeon;

If(venusPegion == 0 ) {

     V(flyingPath);

}

V(VenusLock);

+ the efficiency is more for both cities

+ the traffic from the other city can be stopped from from one city

+ Both get equal chances

+ No starvation

Mutual Exclusion: Atmost one process is inside the critical section at any point of time

                                   All locks required are collected at the entry section

Progress: No deadlock; if more than one process is waiting, they will eventually get the chance

Bounded waiting: No starvation;

Semaphore flyingpath=1;

P(flyingPath); //wait operation

// send message

V(flyingpath);    //send signal

Semaphore venusLock=1;

Int venusPigeon =0;

++venusPigeon;

If(venusPigeon ==1){

    P(flyingPath);

}

//send message

-- venusPigeon;

If(venusPegion == 0 ) {

     V(flyingPath);

}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.