Skip to content

MoreOnSemaphores.md

Latest commit

 

History

History
48 lines (38 loc) · 1003 Bytes

MoreOnSemaphores.md

File metadata and controls

48 lines (38 loc) · 1003 Bytes

Semaphors

Standard Synchronization Problems

  • Bounded buffer (producer & consumer)
  • Fairness (readers and writers)
  • Resource allocation (dining philosophers)

Flying Pigeon Problem

semaphore flyingPath=1; // scheduling
P(flyingPath);
// sending message
V(flyingPath);
  • Simple solution
  • The biggest issue is efficiency
    • one pigeon can fly at a time

Multi Pigeon

semaphore flyingPath= 1;
P(flyingPath);
// send the message
V(flyingPath);

/* ------------------------------------------------ */

int BirdsInTransit = 0;
++BirdsInTransit;

if(BirdsInTransit == 1){
    P(flyingPath);
}

// sends message

--BirdsInTransit;
if(BirdInTransit == 0){
    V(flyingPath);
}

Definitions

  • Liveness (progress)
    • if more than one thread is interested in executing within the critical section, some process will eventually do so (deadlock free)
  • Fairness (bounded waiting)
    • every thread that wants to execute the critical section will do so (no starvation)