Banker's Algorithm Implementation in CPN Tools

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216275%3A25510%2F08%3A00007125" target="_blank" >RIV/00216275:25510/08:00007125 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Banker's Algorithm Implementation in CPN Tools

Original language description

When constructing discrete simulation models of complex transportation systems, their designers face problems of deadlock states occurring in the course of simulation. When analyzing it, the issue was transformed to a problem of solving deadlock states in resource allocation systems (RAS) with non-sequential processes with flexible routing and use of resources of multiple types at once. As a suitable deadlock-avoidance policy, the banker's algorithm (BA) has been chosen. The task was to modify the basicversion of the BA and to test the developed algorithm on a sample transportation system with the outlined properties. As a suitable environment for this, the CPN Tools were chosen, what led to an implementation of the modified version of the BA in the CPN ML, language used by the CPN Tools. The paper explains modifications of the algorithm, describes an implementation of it in the CPN ML and shows its use on a coloured Petri net model of a small example from the outlined category of the

Czech name

Implementace bankéřova algoritmu v nástroji CPN Tools

Czech description

Při konstrukci diskrétních simulačních modelů složitých dopravních systémů se jejich tvůrci potýkají s problémy stavů uváznutí, které sa vyskytují během simulace. Při analýze byl problém transformován na problém řešení stavů uváznutí v systémech přidělování prostředků (RAS) s nesekvenčními procesy s pružným směrováním a použitím prostředků vícero typů najednou.Vhodnou strategií vyhýbání se uváznutí byl zvolen algoritmus bankéře (BA). Úlohou bylo upravit základní verzi BA a otestovat vyvinutý algoritmusna vzorovém dopravním systému se jmenovanými vlastnostmi. Jako vhodné prostředí byl vybrán systém CPN Tools, co vedlo k implementaci upravené verze BA v CPN ML, jazyce používaném v CPN Tools. Příspěvek vysvětluje úpravy algoritmu, opisuje její implementaci v jazyce CPN ML a demonstruje jeho použití v modelu barvené Petriho sítě pro malý příklad ze jmenované kategorie RAS.

Type

D - Article in proceedings

CEP classification

JO - Land transport systems and equipment

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2008

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Ninth Workshop and Tutorial on Practical Use of Coloured Petri Nets and the CPN Tools

ISBN

—

ISSN

0105-8517

e-ISSN

—

Number of pages

20

Pages from-to

—

Publisher name

University of Aarhus

Place of publication

Aarhus

Event location

Aarhus

Event date

Oct 22, 2008

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—