Simple Finite State Machine for Beginners

What is FINITE STATE MACHINE?

A finite state Machine is a simply state Machine which composed of different States, events, Actions and Transition of states based on events.

A finite state Machine generally represented in the form of two dimensional Matrix.

The vertical (or horizontal) dimension indicates current states, the horizontal (or vertical) dimension indicates events, and the cells (row/column intersections) in the table contain the next state if an event happens (and possibly the action linked to this state transition).

State Transition Table
Events State	E1	E2	...	En
S1	-	Ay/Sj	...	-
S2	-	-	...	Ax/Si
...	...	...	...	...
Sm	Az/Sk	-	...	-

(S: state, E: event, A: action, -: illegal transition)

Generally in real time code, these action functions are implemented using function pointers.

Real time FSM code contain states and events defined in enums . And there is event handler which handles the events and based on respective events the appropriate action is being taken.

Below you can find a small example of finite state machine and it is implemented in C language. 

I have implemented BULB( or LIGHT) - SWITCH state Machine.

If  the switch is ON, bulb is in OFF then state should change to ON state( Action: Bulb is ON)

If  the switch is ON, bulb is in ON then state should remain in  ON state( No Action is Taken)

If  the switch is OFF, bulb is in ON then state should change to OFF state( Action: Bulb is OFF)  

If  the switch is OFF, bulb is in OFF then state should remain in OFF state( Action: Bulb is OFF)  

STATES/EVENTS	SWITCHOFF_BULB	SWITCHON_BULB
STATE_OFF	STATE_OFF, Action -> Nothing [ Bulb Remain in OFF)	STATE_ON, ACTION-> Bulb is ON
STATE_ON	STATE_OFF, ACTION-> Bulb is OFF	STATE_ON, Action -> Nothing [ Bulb Remain in ON)

 

Implementation of FSM in simple C code:

==============================

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

#define MAX_STATES 2

/* This Program implements a state Machine for
 * simple switch( ON/OFF) Which does the action to switch ON/OFF bulb.
 */

/*
 * Generally FSM Implemented in Two Dimensional Matrix
 */
/*
 * FSM_STATES
 */
typedef enum FSM_STATES
{
    STATE_OFF,
    STATE_ON

}FSM_STATES;

/*
 * FSM_STATES
 */
typedef enum FSM_EVENTS
{
    SWITCHOFF_BULB,
    SWITCHON_BULB       
}FSM_EVENTS;

/*
 *  Event handler function
 */
 void FSM_Event_Handler_Function(FSM_EVENTS fsm_event);

 /*
 *   Action Functions
 */
 
 /* Switch On*/
 void SwitchOn_Bulb(FSM_EVENTS fsm_event,  char *p);
 
 /* Switch off */
 void SwitchOff_Bulb(FSM_EVENTS fsm_event,  char *p);
 
 
 /*
  *    Function Pointer, Declare array of pointers.
  * One way of declaring the Array of pointers by using below syntax
  */
 typedef void (*action_func)(FSM_EVENTS fsm_event,  char *p);
 
 /*
  *  Array of Action Functions
  */
 action_func  array_of_func_Pointers[MAX_STATES] = { SwitchOff_Bulb, SwitchOn_Bulb };
 
 /*
  * Intialise the FSM_STATE Declared it as Global
  */
 FSM_STATES fsm_state = STATE_OFF;
 
/* Declaration Ends Here */
 
 
 /*
  * SwitchOn_Bulb()
  */
 void SwitchOn_Bulb(FSM_EVENTS fsm_event,  char *p)
 {
    printf(" \nBefore Switch On FSM State is :%d\n", fsm_state);
   
    /* Change the fsm_state to switch OFF */
    fsm_state = STATE_ON;
 
    printf(" The Event is :%d\n", fsm_event);   
    printf(" The FSM State changed to :%d\n", fsm_state);   
    printf(" The Trigger from this Function :%s\n", p);
       
 }
 
 /*
  * SwitchOff_Bulb()
  */
 void SwitchOff_Bulb(FSM_EVENTS fsm_event, char *p)
 {
    printf(" \nBefore Switch OFF FSM State is :%d\n", fsm_state);
 
    /* Change the fsm_state to switch OFF */
    fsm_state = STATE_OFF;
   
    printf(" The Received Event is :%d\n", fsm_event);   
    printf(" The FSM State changed to  :%d\n", fsm_state);   
    printf(" The Trigger from this Function :%s\n", p);
       
 }
 
 /*
 *  Event handler function
 */
 void FSM_Event_Handler_Function(FSM_EVENTS fsm_event)
 {
    switch(fsm_event)
    {
        case SWITCHOFF_BULB:
        {
       
            /* State is ON */
            if(fsm_state == STATE_ON)
            {
                /* OFF THE BULB */
                array_of_func_Pointers[SWITCHOFF_BULB](fsm_event, " HEY SWITCH OFF THE BULB, SAVE THE POWER \n");
            }
            else       
            {
                if(fsm_state == STATE_OFF)
                {               
                    printf(" \nHEY  ALREADY BULB is in OFF STATE, SO NO ACTION is TAKEN, RELAX \n");
                   
                }
            }
        }
        break;
   
        case SWITCHON_BULB:
        {
            /* State is OFF */
            if(fsm_state == STATE_OFF)
            {
                /* ON THE BULB */
                array_of_func_Pointers[SWITCHON_BULB](fsm_event,  " HEY SWITCH ON THE BULB, HERE VERY DARK \n");
            }
            else       
            {
                if(fsm_state == STATE_ON)
                {               
                    printf(" \nHEY  ALREADY BULB is in ON STATE, SO No ACTION is TAKEN, RELAX \n");
                }
            }
        }
        break;
   
        default:
            printf("INVALID EVENT RECIEVED \n");
            break;
    }   
 }
 /*
  *  Main() function
  */
 int main()
 {
   
    int triggerEvent;
   
    do
    {
        printf("\n------------------------- \n");
        printf(" Enter the Event to be TRIGGER \n");
        printf(" Enter '0' to Switch Off the BULB \n");
        printf(" Enter '1' to Switch ON the BULB \n");
        printf(" Enter '10' to EXIT \n");
        scanf("%d", &triggerEvent);
        printf("--------------------------- \n");
       
        /* Call the Handler Function */
        FSM_Event_Handler_Function((FSM_EVENTS) triggerEvent );
       
    }while(triggerEvent != 10);
   
 }

MULTIPROCESSING vs. MULTITHREADING

What is Multiprocessing?

In computing, a process is an instance of a computer program that is being executed. Or simply Running program is also called as process.

Multiprocessing means  “ Having Two or more CPU’s in a single computer system”.  

For example, if a computer system has dual core, and there are two process to run(execute) concurrently(at same time),  it can be achieved by assigning each processes to each core of the system. Hence, the two process can execute simultaneously.  

In other words, multiprocessing can defined as multiple process can execute at same time rather than one after other.

In Multiprocessing, each process have different address space and resources.

Different types of Multiprocessing?

SMP(Symmetric multiprocessing): All CPU’s treat equal.

symmetric multiprocessing (SMP) involves a multiprocessor computer hardware architecture where two or more identical processors are connected to a single shared main memory and are controlled by a single OS instance. Most common multiprocessor systems today use an SMP architecture. In the case of multi-core processors, the SMP architecture applies to the cores, treating them as separate processors. Processors may be interconnected using buses, crossbar switches or on-chip mesh networks.

 

Asymmetric multiprocessing (ASMP)

What is Multithreading?

Process is a collection of threads. Thread is a light weight process.  Thread execution is small processing unit of execution.

Each process contains many threads and all threads share the same memory space.

Multiple threads can exist within the same process and share resources such as memory, while different processes do not share these resources.

On a single processor, multithreading generally occurs by time-division multiplexing (as in multitasking): the processor switches between different threads.

This context switching generally happens frequently enough that the user perceives the threads or tasks as running at the same time.

How threads differ from processes

Threads differ from traditional multitasking operating system processes in that:

• processes are typically independent, while threads exist as subsets of a process
• processes carry considerably more state information than threads, whereas multiple threads within a process share process state as well as memory and other resources
• processes have separate address spaces, whereas threads share their address space
• processes interact only through system-provided inter-process communication mechanisms
• context switching between threads in the same process is typically faster than context switching between processes

Scheduling for Multithreading

Operating systems schedule threads in one of two ways:

1. Preemptive multithreading is generally considered the superior approach, as it allows the operating system to determine when a context switch should occur. The disadvantage to preemptive multithreading is that the system may make a context switch at an inappropriate time, causing lock convoy, priority inversion or other negative effects which may be avoided by cooperative multithreading.
2. Cooperative multithreading, on the other hand, relies on the threads themselves to relinquish control once they are at a stopping point. This can create problems if a thread is waiting for a resource to become available.

Protection Mechanism for Threads

A thread will share all global variables and file descriptors of the parent process which allows the programmer to separate multiple tasks easily within a process.

It shares everything, except each thread will have its own program counter, stack and registers. Since each thread has its own stack, local variables will not be shared between threads.

Since all threads of a process share the same global variables, a problem arises with synchronization of access to global variables. For example, let's assume you have a global variable X and two threads A and B. Let's say threads A and B will merely increment the value of X. When thread A begins execution, it copies the value of X into the registers and increments it. Before it gets a chance to write the value back to memory, this thread is suspended. The next thread starts, reads the same value of X that the first thread read, increments it and writes it back to memory. Then, the first thread finishes execution and writes its value from the register back to memory. After these two threads finish, the value of X is incremented by 1 instead of 2 as you would expect.

Errors like this will probably not occur all of the time and so can be very hard to track down. This becomes even more of a problem on a machine equipped with multiple processors, since multiple threads can be running at the same time on different processors, each of them modifying the same variables. The workaround for this problem is to use a mutex (mutual exclusion) to make sure only one thread is accessing a particular section of your code. When one thread locks the mutex, it has exclusive access to that section of code until it unlocks the mutex. If a second thread tries to lock the mutex while another thread has it locked, the second thread will block until the mutex is unlocked and is once more available.

In the last example, you could lock a mutex before you increment the variable X, then unlock X after you increment it. So let's go back to that last example. Thread A will lock the mutex, load the value of X into the registers, then increment it. Again, before it gets a chance to write it back to memory, thread B gets control of the CPU. It will try to lock the mutex, but thread A already has control of it, so thread B will have to wait. Thread A gets the CPU again and writes the value of X to memory from the registers, then frees the mutex. The next time thread B runs and tries to lock the mutex, it will be able to, since it is now free. Thread B will increment X and write its value back to X from the registers. Now, after both threads have completed, the value of X is incremented by 2, as you would expect.