Building reliable competition with FSP and process modeling

Making the parallelism system more reliable

Today we will see how to simulate a competitive program on FSP. First, let’s look at why competitiveness is needed at all. Here’s what you can do with it:

  • To increase the performance of multiprocessor hardware, this is called parallelism;
  • Increase the throughput of the application (an I / O call needs to block only one thread);
  • Make the application more responsive by performing the main tasks in parallel with the background ones (high-priority thread for user requests);
  • To structure the program, increasing its efficiency (programs interacting with the environment manage several actions and process several events).

LTSA-generated state diagram


What is this language – FSP?

Finite state processes (FSP) is an abstract language in which concurrent process systems are designed.

We model the proposed architecture to add confidence in its validity and adequacy. Concurrency, like most complex design tasks, is best disassembled with multiple layers of abstraction.

First, we need to clearly understand the functional requirements for the system, in the sense of what behavior we want from it. Then you need to explore the possible roles of concurrency. The best way to do this is by abstracting streams without being tied to a specific implementation.

The final choice of mechanisms for implementing concurrency should be kept as open as possible to allow fine tuning of the performance and distribution flexibility of components that vary across product configurations.

How to use process algebra (FSP) to describe competitive processes

It is easier to explain concepts and models with an example. Let’s analyze and simulate a situation when there are two students. they share the printer to print the documents and the technician fills out the sheets.

First, let’s analyze the printer

  • The printer only fits three sheets, students can print up to three documents;
  • If there are no sheets, the printer needs to be filled with them.

const MIN_SHEET_COUNT	=	1
const MAX_SHEET_COUNT	=	3
range DOC_COUNT		=	MIN_SHEET_COUNT .. MAX_SHEET_COUNT
range SHEET_STACK	=	0 .. MAX_SHEET_COUNT

PRINTER(SHEETS_AVAILABLE = MAX_SHEET_COUNT) =  ( start -> PRINTER_AVAILABLE[MAX_SHEET_COUNT]),
  PRINTER_AVAILABLE[sheets_available: SHEET_STACK] = 
	if   (sheets_available > 0)
	  then (acquire -> print[DOC_COUNT] -> release -> PRINTER_AVAILABLE[sheets_available - 1])
	  else (empty -> refill_printer -> release -> PRINTER_AVAILABLE[MAX_SHEET_COUNT]).

PRINTER process

When a user (student or technician) receives the printer, the printer prints the document, gives it to the user, and returns to its original state. It is called repetitive behavior

How to animate the process

To animate the process, first compile (compile [1]) code, then go to the draw tab. Press the animate button [2]…

Animation of the PRINTER process

In the animator, you can see that the printer printed three documents and went to the gas station. A technician must charge the printer. We will analyze this part later.

Student typing documents

FSP code can be written using conditional processes (if, then, else). DOCSTOPRINT = 3 is the parameter passed to the process 3. The PRINT process starts at 0. Doc_count is the indexed action label that leads to this action: PRINT [doc_count]…

STUDENT(DOCS_TO_PRINT = 3) =  PRINT[0],
PRINT[doc_count: 0 .. DOCS_TO_PRINT] = 
	if (doc_count < DOCS_TO_PRINT)
	then ( acquire -> print -> release -> PRINT[doc_count + 1]  )
	else ( terminate -> END ).

STUDENT process with conditional process

The same process can be written using protected processes.

STUDENT(DOCS_TO_PRINT = 3) =  PRINT[0],
PRINT[doc_count: 0 .. DOCS_TO_PRINT] = (
  when (doc_count < DOCS_TO_PRINT)  
	acquire -> print -> release -> PRINT[doc_count + 1] |
  when (document_count == DOCUMENTS_TO_PRINT) 
	terminate -> END ).

STUDENT process with protected process

Animation of the STUDENT process

Now let’s analyze the technician who installs the paper into the printer.

TECHNICIAN = (empty -> refill_printer -> release -> TECHNICIAN | terminate -> END) .

The technician’s process has several options. But when the technician and student processes are synchronized, the option of immediate termination is blocked.

Technique process animation

Finally, let’s take a look at the composite process

  • A composite process must be synchronized with all sub-processes, for this you can define a set of actions named PRINT_Actions.
  • terminate / s1.terminate is a re-labeled action. With, we reassign the s1.terminate action to simply terminate the process. Otherwise, the animator will show s1.terminate, s2.terminate, and tcn.terminate.
  • You can use a mutually exclusive share to synchronize users with PRINTER.

|| SHARED_PRINTER = (s1: STUDENT(2) || s2: STUDENT(3) || tcn : TECHNICIAN || All_Users :: PRINTER)

This will allow one user to get the resource and the other to release it. Therefore, when the PRINTER consists of USER processes, this composition ensures that only the user who receives the resource can release it.

const MIN_SHEET_COUNT	=	1
const MAX_SHEET_COUNT	=	3
range DOC_COUNT		=	MIN_SHEET_COUNT .. MAX_SHEET_COUNT
range SHEET_STACK	=	0 .. MAX_SHEET_COUNT

set All_Users = {s1, s2, tcn}
set PRINT_Actions = {acquire, print, release, empty}

PRINTER(SHEETS_AVAILABLE = MAX_SHEET_COUNT) = PRINTER_AVAILABLE[MAX_SHEET_COUNT],
PRINTER_AVAILABLE[sheets_available: SHEET_STACK] = 
		if   (sheets_available > 0)
		then ( acquire -> print -> release -> PRINTER_AVAILABLE[sheets_available - 1]  )
		else ( empty -> release -> PRINTER_AVAILABLE[MAX_SHEET_COUNT] ).

STUDENT(DOCS_TO_PRINT = 1) =  PRINT[0],
PRINT[doc_count: 0 .. DOCS_TO_PRINT] = 
		if   (doc_count < DOCS_TO_PRINT)
		then ( acquire -> print -> release -> PRINT[doc_count + 1]  )
		else ( terminate -> END )+ PRINT_Actions.

TECHNICIAN = (empty -> refill_printer -> release -> TECHNICIAN | terminate -> END) + PRINT_Actions.

|| SHARED_PRINTER = (s1: STUDENT(2) || s2: STUDENT(3) || tcn : TECHNICIAN || All_Users :: PRINTER) 
/ {terminate/s1.terminate,terminate/s2.terminate,terminate/tcn.terminate}.

Composite Process of Printer System

I hope this material helps you learn about concurrency on FSP.


Similar Posts

Leave a Reply