Problemă la roller coaster

Problema roller coaster (mai bine cunoscută sub numele de problema roller coaster ) este o problemă de sincronizare între procese .

Descrierea problemei

Să presupunem că există n pasageri ( fire ) și un cărucior cu role (alt fir). Pasagerii sosesc la carusel și să aștepte căruciorul care poate transporta pasageri C cu C <n. Căruciorul începe doar când este plin.

Detalii restrictive:

pasagerii invocă board și unboard
coșul de apeluri load , run și unload
pasagerii nu pot monta până când trăsura nu a invocat load
căruciorul nu poate pleca până când pasagerii C nu sunt montați la bord
pasagerii nu pot unload până când trăsura nu a invocat unload

Este evident că această problemă poate cauza blocaje .

Soluție cu semafoare

Pentru a rezolva această problemă, folosim semafoarele . Vom folosi următoarele variabile partajate între toate procesele inițiale astfel inițiate:

 pensionari = 0
unboarders = 0
mutex1 = Semafor (1)
mutex2 = Semafor (1)
boardQueue = Semafor (0)
unboardQueue = Semafor (0)
allAboard = Semaphore (0)
allAshore = Semaphore (0)

Dove mutex protejează pasagerii numărând numărul de pasageri care s-au bazat pe board . Pasagerii așteaptă în boardQueue înainte de a se monta în cărucior și unboardQueue înainte de a demonta. allAboard indică faptul că căruciorul este plin și allAshore că toți pasagerii sunt descărcați.

În acest pseudo-cod, wait echivalentă cu clasicul P și signal lui V. Dijkstra . Pseudo-codul pentru coșul de cumpărături poate fi structurat după cum urmează:

 sarcină ()
boardQueue.signal (C)
allAboard.wait ()
alerga ()
descărca ()
unboardQueue.signal (C)
allAshore.wait ()

Când ajunge căruciorul, raportați pasagerii C , apoi așteptați ca ultimul să se prezinte la allAboard . Începeți-vă turul și când vine vorba de C, permite pasagerilor să îndepărteze allAshore care așteaptă semnalul către allAshore .

Pe de altă parte, pseudo-codul pentru pasageri poate fi structurat după cum urmează: boardQueue.wait ()

 bord ()
mutex1.wait ()
pensionari + = 1
dacă pensionari == C:
  allAboard.signal ()
  pensionari = 0
mutex1.signal ()
unboardQueue.wait ()
unboard ()
mutex2.wait ()
unboarderi + = 1
dacă unboarders == C:
  allAshore.signal ()
  unboarders = 0
mutex2.signal ()

Pasagerii așteaptă căruciorul înainte de montare. Ultimul pasager care urcă semnalizează căruciorul că poate pleca și resetează ghișeul de boarders .

Această soluție nu este bună dacă există mai multe căruțe în joc.

Implementare în C

Iată codul C care rezolvă problema cu metoda semaforului. Am folosit pithreads și semaforuri POSIX .

 / ************************************************** ************
* Pentru a compila cu gcc pe Linux: *
* gcc file.c -lpthread *
*************************************************** *********** /

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>

#define NUM_PASS 200

typedef struct
{
  boarderi int, unboarders;
  Semafor * mutex1 , * mutex2 ;
  Semafor * boardQueue , * unboardQueue ;
  Semafor * allAboard , * allAshore ;
} Partajat ;

// Unele funcții de utilitate //

nul
eroare ( char * msg )
{
  perror ( msg );
  ieșire ( 1 );
}

nul *
check_malloc ( dimensiune int )
{
  gol * p = malloc ( dimensiune );
  if ( p == NULL )
    eroare ( "malloc a eșuat \ n " );
  retur p ;
}

Semafor *
new_semaphore ( int n )
{
  Semaphore * sem = check_malloc ( sizeof ( Semaphore ));
  int ret = sem_init ( sem , 0 , n );
  if ( ret == -1 )
    eroare ( "sem_init a eșuat \ n " );
  retur sem ;
}

nul
join_thread ( pthread_t thread )
{
  int ret = pthread_join ( thread , NULL );
  if ( ret == -1 )
    eroare ( "pthread_join a eșuat \ n " );
}

// Problemă la roller coaster //

nul *
rollercoaster ( void * arg )
{
  int id = id_counter ++ ;
  int i , turn = 1 ;
  Shared * shared = ( Shared * ) arg ;

  for ( turn = 1 ; turn <= TURN ; turn ++ )
    {
      printf ( " \ n R: Acesta este numărul de rând% d \ n " , rândul său );
      printf ( "R: Încărcarea pasagerilor ... \ n " );
      pentru ( i = 0 ; i < SEATS ; i ++ )
	sem_post ( partajat -> boardQueue );
      sem_wait ( shared -> allAboard );
      
      printf ( "R: Roller coaster start \ n " );
      somn ( 1 );
      printf ( "R: Roller coaster stop \ n " );
      
      printf ( "R: Descărcarea pasagerilor ... \ n " );
      pentru ( i = 0 ; i < SEATS ; i ++ )
	sem_post ( partajat -> unboardQueue );
      sem_wait ( shared -> allAshore );
    }

  printf ( " \ n R: Este ora 18:00, serviciul este aproape! \ n " );
  pthread_exit ( NULL );
}

nul *
pasager ( nul * arg )
{
  int id = id_counter ++ ;
  Shared * shared = ( Shared * ) arg ;

  sem_wait ( partajat -> boardQueue );
  printf ( "P: Pasagerul% d se îmbarcă \ n " , id );

  sem_wait ( partajat -> mutex1 );
  partajat -> pensionari ++ ;
  if ( partajat -> pensionari == SEATS )
    {
      sem_post ( shared -> allAboard );
      partajat -> pensionari = 0 ;
    }
  sem_post ( partajat -> mutex1 );
  
  sem_wait ( partajat -> unboardQueue );
  printf ( "P: Pasagerul% d se dezbarcă \ n " , id );
  
  sem_wait ( partajat -> mutex2 );
  partajat -> unboarders ++ ;
  if ( shared -> unboarders == SEATS )
    {
      sem_post ( shared -> allAshore );
      partajat -> unboarders = 0 ;
    }
  sem_post ( partajat -> mutex2 );
	 
  pthread_exit ( NULL );
}

int
main ()
{
  int i ;
  pthread_t pasageri [ NUM_PASS ];
  pthread_t roller_coaster ;
  
  id_counter = 0 ;
  Shared * shared = new_shared ();

  roller_coaster = new_thread ( rollercoaster , shared );

  pentru ( i = 0 ; i < PASS_NUM ; i ++ )
    fir_ nou ( pasager , partajat );

  join_thread ( roller_coaster );

  retur 0 ;
}

Modelare în CCS

Calculul sistemelor de comunicare (CCS) este un limbaj teoretic care permite studierea sistemelor reactive. Mai jos este modelarea CCS a problemei noastre (sintaxa concurenței WorkBench ) pentru un coș cu capacitate 2 (C = 2):

 agent P = 'board.'unboard.P;
 agent BOARDQUEUE = board.board.'allAboard.0;
 agent UNBOARDQUEUE = unboard.unboard.'allAshore.0;
 agent RC = 'load.allAboard.RC1 | load.BOARDQUEUE;
 agent RC1 = run.RC2;
 agent RC2 = 'unload.allAshore.RC | descărcați.UNBOARDQUEUE;
 set L = {încărcare, descărcare, bord, deconectare, allAboard, allAshore};
 agent SYS = (RC | P | P | P | P) \ L;

Elemente conexe

linkuri externe

( RO ) Cartea Mică a Semaforelor , pe greenteapress.com . Adus la 7 martie 2008 (arhivat din original la 14 iunie 2016) .
( RO ) The Edinburgh Concurrency Workbench , la homepages.inf.ed.ac.uk .

Portal IT : accesați intrările Wikipedia care se ocupă cu IT