Limitations of Dijkstra's Semaphore Primitives and Petri nets

Publisher Website
Google Scholar
Abstract
Recently various attempts have been made to study the limitations of Dijkstra's Semaphore Primitives for the synchronization problem of cooperating sequential processes [3,4,6,8]. Patil [8] proves that the semaphores with the P and V primitives are not sufficiently powerful. He suggests a generalization of the P primitive. We prove that certain synchronization problems cannot be realized with the above generalization and even with arrays of semaphores. We also show that even the general Petri nets will not be able to handle some synchronization problems, contradicting a conjecture of Patil (P.28 [7]).

This publication has 2 references indexed in Scilit: