Critical resources software and control modeling with finite automata

• Autorzy: Schreyer B. , Kosiński K.

Warianty tytułu

PL

Automaty skończone w modelowaniu sterowania ruchem w systemach transportowych z zasobami krytycznymi

• Języki publikacji: EN

Abstrakty

EN

There are analogies between modeling the transportation systems with critical resources (CR) and a critical section (CS) problem in operating systems. This article is developing this analogy in the direction of using the finite automata. The article analyses Peterson’s algorithm [4], [5] and Lamport’s algorithm [2] using deterministic finite automata (DFA) as well as it takes into consideration the problem of modeling traffic with binary semaphore using nondeterministic finite automata (NFA). Introduction of finite automata makes traffic control modeling much clearer on programming side and brings hardware application closer to such control.

PL

Problem poruszany w artykule dotyczy modelowania ruchu w systemie transportowym ze środkami krytycznymi (CR). Jest oparta na analogii z podobnym problemem sekcji krytycznej (CS) w systemach operacyjnych. Niniejszy artykuł jest rozwinięciem tej idei w naturalnym kierunku uogólnienia tj. z zastosowaniem automatów skończonych. Artykuł analizuje algorytm Petersona oraz algorytm Lamporta przy użyciu deterministycznych automatów skończonych, jak również problem modelowania ruchu przy pomocy semaforu binarnego przy użyciu niedeterministycznych automatów skończonych. Wprowadzenie automatów skończonych czyni modelowanie sterowania ruchem na drodze programowej bardziej przejrzystym jak również przybliża zastosowanie hardwaru do tego sterowania. W artykule dokonano analizy trzech algorytmów krytycznej sekcji w systemach operacyjnych w zastosowaniu do sterowania jednostkami transportowymi w kontroli przyznawania środków krytycznych. W analizie zastosowano skończone automaty deterministyczne oraz niedeterministyczne. Jak wynika z tej analizy, wszystkie trzy warunki (1) poprawnej kontroli JT zostały spełnione. Jednocześnie automaty skończone pozwoliły na zwarte i przejrzyste modelowanie problemu CR w systemach transportowych.

Słowa kluczowe

EN

critical resources; finite automata; traffic control

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2010
• Tom: Vol. 22, No. 3
• Strony: 155--163
• Opis fizyczny: Bibliogr. 5 poz., rys.

Twórcy

autor

Schreyer B.

autor

Kosiński K.

• Nipissing University, North Bay, Kanada

Bibliografia

• 1. L. Lamport: A new solution of Dijkstra’s Concurrent Programming Problem. Communications of the ACM 17, 8 (August 1974), pp. 453-455.
• 2. M. Sipser: Introduction to the theory of computation, PWS Publishing Company (1997).
• 3. G.L. Peterson: Myths about the mutual exclusion problem. Information Processing Letters, Vol. 12, no 3 (1981).
• 4. B. Schreyer, V. Bozic: Deterministic finite automata for critical section modeling. ACM SIGCSE 11th Annual Conference on Innovation and Technology in computer Science Education, Bologna, Italy, June 26-28, 2006.
• 5. V. Bozic: Application of finite state automata to bakery Algorithm in critical section modeling. ACM SIGCSE 11th Annual Conference on Innovation and Technology in computer Science Education, Bologna, Italy, June 26-28, 2006.