Language:
Free Online Dictionary|3Dict

dining philosophers problem

Source : Free On-Line Dictionary of Computing

Dining Philosophers Problem
     
         (DPP) A problem introduced by {Dijkstra} concerning
        resource allocation between processes.  The DPP is a model and
        universal method for testing and comparing theories on
        resource allocation.  Dijkstra hoped to use it to help create
        a layered {operating system}, by creating a machine which
        could be consider to be an entirely {deterministic}
        {automaton}.
     
        The problem consists of a finite set of processes which share
        a finite set of resources, each of which can be used by only
        one process at a time, thus leading to potential {deadlock}.
     
        The DPP visualises this as a number of philosophers sitting
        round a dining table with a fork between each adjacent pair.
        Each philosopher may arbitrarily decide to use either the fork
        to his left or the one to his right but each fork may only be
        used by one philosopher at a time.
     
        Several potential solutions have been considered.
     
        Semaphores - a simple, but unfair solution where each
        resources is a {binary semaphore} and additional semaphores
        are used to avoid deadlock and/or {starvation}.
     
        Critical Regions - each processor is protected from
        interference while it exclusively uses a resource.
     
        Monitors - the process waits until all required resources are
        available then grabs all of them for use.
     
        The best solution allows the maximum parallelism for any
        number of processes (philosophers), by using an array to track
        the process' current state (i.e. hungry, eating, thinking).
        This solution maintains an array of semaphores, so hungry
        philosophers trying to acquire resources can block if the
        needed forks are busy.
     
        (1998-08-09)
Sort by alphabet : A B C D E F G H I J K L M N O P Q R S T U V W X Y Z