State machine is widely used in practical work development. When I first entered the company, I found that I often missed this or that state when I made the flow chart according to the company’s products, which led to problems in the overall process. Later, when I knew something like state machine, I found that the flow of the whole state could be clearly expressed with this diagram.

Yikou Jun has done many network protocol modules, many protocol development must use state machine; a robust state machine can let your program, no matter what kind of emergency, will not suddenly enter an unpredictable program branch.

This article through C language to achieve a simple process 5 state model of state machine, let everyone familiar with the charm of state machine.

What is a state machine?

definition

State machine is the abbreviation of finite state automata, which is a mathematical model abstracted from the running rules of real things.

Let’s first explain what a “state” is. Real things have different states, such as an LED, there are two states: on and off. We usually call the state machine finite state machine, that is to say, the number of states of things described is limited, for example, the state of LED light is two on and off.

State machine, or Statemachine, is not a real machine, but a mathematical model. To put it bluntly, it generally refers to a state transition diagram.

give an example

Taking the light bulb diagram of physics as an example, it is a basic small state machine

The following state machine diagram can be drawn

Here are two states: ① the bulb is on and ② the bulb is off. If the switch is turned on, the status will be switched to the light bulb. When the light bulb is on, if the switch is turned off, the status will be switched to off.

The full name of state machine is finite state automata, and the word “automatic” also contains important meanings. Given a state machine, and given its current state and input, then the output state can be explicitly calculated. For example, for a bulb, given the initial state of the bulb off, given the input “on switch”, then the next state can be calculated.

Four concepts

Here are four concepts of state machine.

State, state. A state machine must contain at least two states. For example, in the example of the light bulb above, there are two states: the light bulb is on and the light bulb is off.

Event, event. An event is a trigger condition or password to perform an operation. For a light bulb, “turn on the switch” is an event.

Action, action. Actions are performed after the event occurs. For example, the event is “on switch” and the action is “turn on light”. In programming, an action usually corresponds to a function.

Transiion, transform. That is, from one state to another. For example, “lighting process” is a transformation.

Application of state machine

State machine is an abstract of the real world, and is a logical mathematical abstraction, so it is obviously very suitable for use in the digital field. It can be applied to all levels, such as hardware design, compiler design, and programming to achieve a variety of specific business logic.

Process 5 state model

Process management is one of the five major subsystems of Linux, which is very important, and it is very complicated to realize in practice. Let’s take a look at how the process switches state.

The following figure shows the five state model of a process:

A brief introduction to the figure is as follows:

Runnable state: a process is said to be running when it is being executed by the CPU or is ready to be executed by the scheduler at any time. Processes can run in kernel mode or user mode. When the system resources are available, the process will be awakened and enter the ready to run state, which is called ready state.

Shallow sleep state (interruptible): the process is sleeping (blocked), waiting for the arrival of resources is wake-up, or through other process signals or clock interrupt wake-up, into the running queue.

Deep sleep state (non interruptible): it is basically similar to shallow sleep, but it can not be awakened by other process signals or clock interrupts. Only by using wake_ Only when the up() function explicitly wakes up can it switch to the ready state for running.

Pause state: when a process receives the signal sigstop, sigstp, sigttin, or sigtou, it enters the pause state. It can be sent a sigmont signal to allow the process to transition to a runnable state.

Deadlock state: when a process has stopped running, but its parent process has not asked its status, and the PCB is not released, the process is said to be in a deadlock state.

The state of the process is switched according to this state diagram.

The state flow is a bit complicated, because our goal is to implement a simple state machine, so we simplify the state machine as follows:

To implement a state machine, first convert the state machine into the following state migration table.The brief description is as follows: assuming that the current process is in the running state, only after the schedule event occurs will the process generate the state migration. If other events, such as wake and wait, occur in this state_ Events do not cause state migration.

As shown in the figure above:

Each column represents a state, and each row corresponds to an event.

This table is the core diagram to realize the state machine. Please compare the relationship between the table and the state transition diagram in detail.

In the actual scene, the process switching will be much more complex than this figure. Fortunately, many gods have helped us solve these complicated problems. We just need to stand on the shoulders of giants.

realization

According to the state transition table, the state of the state machine is defined as follows:

typedefenum{sta_ origin=0,sta_ running,sta_ owencpu,sta_ sleep_ int,sta_ sleep_ unint}State;

The following events occurred:

typedefenum{evt_ fork=0,evt_ sched,evt_ wait,evt_ wait_ unint,evt_ wake_ up,evt_ wake,}EventID;

Both state and event can be adjusted according to the actual situation.

Define a structure to represent the current state transition information

Typestruct {statecurstate; / / current state eventid; / / event idstatenextstate; / / next state callbackaction; / / callback function. After the event occurs, call the corresponding callback function} statetransform;

Event callback function: in practical application, different events need to perform different actions, so different functions need to be defined. For convenience, all events in this example use the same callback function. Function: print the state of the process before and after the event. If the state changes, call the corresponding callback function.

voidaction_ callback(void*arg){StateTransform*statTran=(StateTransform*)arg;if(statename[statTran-》curState]==statename[statTran-》nextState]){printf(“invalidevent,statenotchange\n”);}else{printf(“callbackstatefrom%s–》%s\n”,statename[statTran-》curState],statename[statTran-》nextState]);}}

Define a migration table array for each state:

/*origin*/StateTransformstateTran_ 0[]={{sta_ origin,evt_ fork,sta_ running,action_ callback},{sta_ origin,evt_ sched,sta_ origin,NULL},{sta_ origin,evt_ wait,sta_ origin,NULL},{sta_ origin,evt_ wait_ unint,sta_ origin,NULL},{sta_ origin,evt_ wake_ up,sta_ origin,NULL},{sta_ origin,evt_ wake,sta_ origin,NULL},};/*running*/StateTransformstateTran_ 1[]={{sta_ running,evt_ fork,sta_ running,NULL},{sta_ running,evt_ sched,sta_ owencpu,action_ callback},{sta_ running,evt_ wait,sta_ running,NULL},{sta_ running,evt_ wait_ unint,sta_ running,NULL},{sta_ running,evt_ wake_ up,sta_ running,NULL},{sta_ running,evt_ wake,sta_ running,NULL},};/*owencpu*/StateTransformstateTran_ 2[]={{sta_ owencpu,evt_ fork,sta_ owencpu,NULL},{sta_ owencpu,evt_ sched,sta_ owencpu,NULL},{sta_ owencpu,evt_ wait,sta_ sleep_ int,action_ callback},{sta_ owencpu,evt_ wait_ unint,sta_ sleep_ unint,action_ callback},{sta_ owencpu,evt_ wake_ up,sta_ owencpu,NULL},{sta_ owencpu,evt_ wake,sta_ owencpu,NULL},};/*sleep_ int*/StateTransformstateTran_ 3[]={{sta_ sleep_ int,evt_ fork,sta_ sleep_ int,NULL},{sta_ sleep_ int,evt_ sched,sta_ sleep_ int,NULL},{sta_ sleep_ int,evt_ wait,sta_ sleep_ int,NULL},{sta_ sleep_ int,evt_ wait_ unint,sta_ sleep_ int,NULL},{sta_ sleep_ int,evt_ wake_ up,sta_ sleep_ int,NULL},{sta_ sleep_ int,evt_ wake,sta_ running,action_ callback},};/*sleep_ unint*/StateTransformstateTran_ 4[]={{sta_ sleep_ unint,evt_ fork,sta_ sleep_ unint,NULL},{sta_ sleep_ unint,evt_ sched,sta_ sleep_ unint,NULL},{sta_ sleep_ unint,evt_ wait,sta_ sleep_ unint,NULL},{sta_ sleep_ unint,evt_ wait_ unint,sta_ sleep_ unint,NULL},{sta_ sleep_ unint,evt_ wake_ up,sta_ running,action_ callback},{sta_ sleep_ unint,evt_ wake,sta_ sleep_ unint,NULL},};

Implement the event generation function:

voidevent_ Have (signed in event) function: find the corresponding statetransform structure body according to the event and the current process state, and call do_ action()

voiddo_ Action (statetransform * stattran) function: according to the structure variable statetransform, realize state migration and call the corresponding callback function.

#defineSTATETRANS(n)(stateTran_ ##n)/*changestate&callcallback()*/voiddo_ Action (statetransform * stattran) {if (null = = stattran) {PERROR (“stattranisnull \”); return;} / / state migration globalstate = stattran – > “nextstate; if (stattran -) action! =Null) {/ / call the callback function stattran – 〉 action ((void *) stattran);} else {printf (“invalid event, statenotchange ‘;}} void event_ happen(unsignedintevent){switch(globalState){casesta_ origin:do_ action(&STATETRANS(0)[event]);break;casesta_ running:do_ action(&STATETRANS(1)[event]);break;casesta_ owencpu:do_ action(&STATETRANS(2)[event]);break;casesta_ sleep_ int:do_ action(&STATETRANS(3)[event]);break;casesta_ sleep_ unint:do_ action(&STATETRANS(4)[event]);break;default:printf(“stateisinvalid\n”);break;}}

Test program: function:

The initial state of the initialization state machine is sta_ origin;

Create a sub thread and display the current process status every second;

The sequence of events is: EVT_ fork–》evt_ sched–》evt_ sched–》evt_ wait–》evt_ wake。

Readers can modify the sequence of events according to their own needs and observe the change of state.

main.c

/*Display current status * / void * show_ stat(void*arg){intlen;charbuf[64]={0};while(1){sleep(1);printf(“curstat:%s\n”,statename[globalState]);}}voidmain(void){init_ Machine(); / / creates a child thread, which is mainly used to display the current state pthread_ create(&pid,NULL,show_ stat,NULL);sleep(5);event_ happen(evt_ fork);sleep(5);event_ happen(evt_ sched);sleep(5);event_ happen(evt_ sched);sleep(5);event_ happen(evt_ wait);sleep(5);event_ happen(evt_ wake);}

Operation results: it can be seen from the results that:

evt_ fork–》evt_ sched–》evt_ sched–》evt_ wait–》evt_ wake

The sequence of state transition corresponding to the event sequence is as follows:

origen–》running–》owencpu–》owencpu–》sleep_ int–》running

Leave a Reply

Your email address will not be published. Required fields are marked *