CN100403739C - Interprocess Message Passing Method Based on Linked List - Google Patents

Abstract

The invention discloses an inter-process message transfer method based on a linked list, comprising: a main control process creates a message queue, and the message queue includes an allocated node queue and an idle node queue; Apply for an idle node in the message queue, and link the beginning and end of the message fields into a shared memory linked list, and then send the head pointer of the linked list to the second processing process; after receiving the shared memory linked list head pointer passed by the first processing process, the second processing The process converts the pointer passed by the first processing process into a memory address in the address space of the process. The second processing process accesses the shared memory linked list in the memory address, updates the result to the linked list after processing, and then sends the head pointer of the linked list to the subsequent processing process. The message delivery technology based on the shared memory pointer and the data structure of the shared memory linked list are adopted to effectively improve the efficiency of message delivery under the streaming service processing framework.

Description

Interprocess Message Passing Method Based on Linked List

technical field

The invention relates to an inter-process message transmission method, in particular to an inter-process message transmission method based on a linked list.

Background technique

In the prior art, the service framework is composed of service components and message events. Among them, the service components can be independent processes or threads, each service component usually includes an input message queue and an output message queue, and each service component knows its next service name, thus forming a logical end-to-end service list. After the message event flows through each service component, a new message event will be generated and input to the next connected service component.

A "message" is a unit of data transferred between computers. Messages can be as simple as just text strings, or more complex and may contain embedded objects. Messages are sent to the queue. A "message queue" is a container that holds messages during their transmission. A message queue manager acts as a middleman in relaying a message from its source to its destination. The main purpose of a queue is to provide routing and guarantee delivery of messages; a message queue holds a message until it can be delivered successfully.

When using Inter-Process Communication (IPC) mechanisms such as socket sockets and pipes (FIFO) to transmit messages, messages need to be transmitted between multiple processes. Usually, each processing process must complete the following processing steps: Read the received message from the receiving buffer and decode it into an internal data structure; complete the processing process and save the processing result; encode the processed result into a message stream, write it into the sending buffer and send it to the peer process. For example, as shown in Figure 1, the processing process 1 copies the message data from the receiving buffer, and then needs to decode the message data, perform corresponding processing on the decoded data, encode the processed message data, and copy to the send buffer so that the next process (i.e. process 2) can receive the message data. Both the processing process 2 and the processing process 3 repeat similar steps to process the message data.

In the above-mentioned traditional inter-process message passing mechanism, messages are copied between the buffer and the memory when they are passed between different processes, and the encoding and decoding of the message event fields are relatively small in terms of the number of concurrent messages and the amount of data carried by message events. Under certain circumstances, the above operations will not cause performance bottlenecks, but in applications with a large number of concurrent messages or a large amount of data carried by message events (such as a real-time billing system), the above operations occur frequently, which will cause serious system performance. decline.

According to the above description, it can be concluded that the technical solution of the prior art has the following disadvantages: the message is copied multiple times between the receiving buffer, the sending buffer and the memory, and the data transmission efficiency is low in the case of a large amount of data; To complete the encoding or decoding process, consume system CPU resources;

Contents of the invention

The problem solved by the present invention is that in the prior art, the processing of message transfer between processes consumes a large amount of resources, resulting in a decrease in system performance. The invention provides a link list-based inter-process message transmission method capable of improving message transmission efficiency.

The interprocess message transfer method based on linked list provided by the present invention includes:

a) The master control process creates a shared memory area, and the shared memory area is used to store message data for inter-process communication;

The main control process creates a message queue, and the message queue includes an allocated node queue and an idle node queue;

b) The first processing process receives an external message, applies for an idle node from the message queue, and links the message fields head to tail to form a shared memory linked list, and then sends the head pointer of the linked list to the second processing process;

c) After receiving the head pointer of the shared memory linked list delivered by the first processing process, the second processing process converts the pointer delivered by the first processing process into a memory address in the address space;

d) The second processing process accesses the shared memory linked list in the memory address, updates the result to the linked list after processing, and then sends the head pointer of the linked list to the subsequent processing process.

According to the above inter-process message passing method, the shared memory area allocates a memory block of predetermined length for each field of the message,

According to the above inter-process message transfer method, there are multiple processing processes for processing external messages.

According to the above inter-process message transfer method, the last processing process in the processing processes releases the processed message node to the idle node queue.

According to the above inter-process message transfer method, the nodes include: the size of the message queue, the head pointer of the linked list of idle nodes of the message queue and the head pointer of the linked list of allocated nodes of the message queue.

According to the above inter-process message transfer method, the first-in-first-out FIFO mechanism is used to send the head pointer of the shared memory linked list between processing processes.

According to the above inter-process message transfer method, the message queue node data includes: at least one of the head pointer of the shared memory linked list, the tail pointer of the shared memory linked list and the number of message data fields.

In particular, the present invention also provides a method for passing messages between processes in a billing system based on a linked list, including:

A) the master control process creates a shared memory area, and the shared memory area is used to store message data for inter-process communication; the master control process creates a message queue, and the message queue includes an allocated node queue and an idle node queue;

b) The authentication process receives a message from an external process, and applies for an idle node from the message queue, and links the message fields head to tail into a shared memory linked list, and then sends the head pointer of the linked list to the billing process;

c) After receiving the shared memory linked list head pointer passed by the authentication process, the billing process converts the pointer passed by the authentication process into a memory address in the address space;

d) The billing process accesses the shared memory linked list in the memory address, updates the processed result to the linked list after completing the processing, and then sends the head pointer of the linked list to the accounting process;

e) The bookkeeping process pointer is converted into a memory address in the address space, and the shared memory linked list in the memory address is accessed.

Since the present invention adopts the message transmission technology based on the shared memory and the data structure of the shared memory linked list, the efficiency of message transmission under the streaming service processing framework is effectively improved.

In the present invention, since the transmitted data is only the pointer of the linked list, the load of inter-process data transmission is reduced and the transmission efficiency is improved. And because the linked list itself has the characteristics of fast and flexible insertion and deletion of nodes, and uses a dynamic memory linked list as the data structure of the message, it can solve the performance problem caused by the dynamic change of the message field data. Using the linked list structure can make full use of the computer memory space and realize flexible memory dynamic management.

Description of drawings

FIG. 1 is a schematic diagram of IPC mechanism message delivery in the prior art;

Fig. 2 is the schematic diagram of the example prototype system of the present invention;

Fig. 3 is the flow chart of the interprocess message transmission method based on linked list of the example of the present invention;

Fig. 4 is a schematic diagram of a memory pool mechanism adopted by an example of the present invention;

Fig. 5 is a schematic diagram of a billing system processing framework according to an example of the present invention;

Fig. 6 is a schematic diagram of the application of the example of the present invention in the billing system;

Fig. 7 is a flow chart of the message delivery method in the billing system of the present invention.

Detailed ways

Fig. 2 is a schematic diagram of the prototype system of the present invention. As shown in the figure, the prototype system includes a main control process, a processing process and an external process. Wherein, the main control process is responsible for creating the message queue, and at the same time, the main control process also controls each processing process.

The external process inputs the message event into the processing process, and the data structure of the message queue is maintained in the shared memory by the main control process and the processing process. The data structure of the message queue includes: the size of the message queue, the head pointer of the idle node list of the message queue, and the head pointer of the allocated node list of the message queue.

In this embodiment, for convenience of description, only three processing processes are involved: process 1 , process 2 and process 3 . These three processing processes can perform corresponding message processing, and the specific process of message processing is different according to different applications. For example, the three message processing processes may be processing processes such as "identification and authentication", "billing", and "accounting" in the communication billing system. Incoming messages from external processes "flow" among the three processing processes and are processed. In practical applications, the system may include more processing processes.

FIG. 3 is a flowchart of a method for passing messages between processes based on a shared memory linked list according to an embodiment of the present invention. In step 301, the master control process creates a shared memory area. When the system is started, a global shared memory area is firstly created by the main control process. The size of the shared memory is calculated according to the processing capability of the system, and can also be adjusted through a dynamic increase method.

In order to improve the efficiency of memory allocation, this system adopts the shared memory pool mechanism to realize the allocation and recovery management of shared memory. As shown in FIG. 4 , the shared memory linked list is a data structure adopted by the present invention to solve the dynamic change of messages. The message data consists of several fields. A fixed-length memory block is allocated for each message data field in the shared memory, and these fields are linked end to end to form a shared memory linked list. Each allocated node stores pointers to the shared The head pointer of the memory linked list. In order to avoid memory fragmentation caused when small memory blocks are allocated, the present invention adopts memory pool technology. In the memory pool, there are multiple memory blocks, and each memory block has a storage unit of a predetermined length, such as a 16-byte memory block, a 32-byte memory block, a 4k-byte memory block, and the like. Fields with message data of different lengths are stored in memory blocks of corresponding lengths respectively.

In step 302, the master control process creates a message queue. Creating a message queue provides resources that can interact with individual processing processes. The message queue is composed of multiple shared memory linked lists, including the allocated node linked list and the free node linked list.

In step 303, processing process 1 receives an external message, and applies for an idle node from the message queue. Process 1 receives messages from external processes through IPC mechanisms such as SOCKET or FIFO, and applies for an idle node from the message queue. The message queue node data structure includes the following information: the head pointer of the shared memory linked list; the tail pointer of the shared memory linked list; the number of message data fields. Applying for an idle message queue node is to apply for a memory block for the processed message.

In step 304, process 1 processes the message received from the external process. Process 1 and process 2 and process 3 mentioned later are processing processes. The processing of the message is different according to different applications. For example, the three message processing processes may be processing processes such as "authentication", "billing", and "accounting" in the communication billing system.

In step 305, process 1 links the fields of the processed message into a shared memory linked list, and then sends the head pointer of the linked list to processing process 2. Referring to Figure 4 again, field 1, field 2, field 3, and field 4 are four fields processed by process 1, wherein the length of field 1, field 3, and field 4 is 32 bytes, and the length of field 2 is 64 bytes. bytes, so the four fields are stored in 32-byte and 64-byte long memory blocks, respectively. Process 1 links the four fields end to end to form a shared memory linked list, and then uses an IPC mechanism (eg, FIFO mechanism) to send the head pointer of the linked list (ie, the pointer to the message queue node) to process 2. The head pointer of the linked list is the head pointer of the shared memory linked list of the idle node applied for by process 1. Since the head pointer pointing to the shared memory linked list is stored, this node becomes an allocated node.

In step 306, after receiving the head pointer of the shared memory linked list passed by process 1, process 2 converts the pointer passed by process 1 into a memory address in the address space. Process 2 converts the pointer data to a memory address within the address space. Process 2 can obtain the message data stored in the relevant address by accessing the memory address for further processing, thus avoiding copying of the message data and saving system resources.

In step 307, the processing process 2 accesses the shared memory linked list in the memory address, performs corresponding processing on the message data, and after completing the processing, updates the processed field results into the linked list, and then the head pointer of the linked list Sent to process 3.

In step 308, process 3 obtains the shared memory linked list by accessing the memory address mapped by the linked list pointer.

In step 309, process 3 releases the processed message nodes to the idle node queue. In this embodiment, process 3 is the last processing process. After the message data is processed, the message queue nodes that have been applied for can be released to the idle node queue.

The billing system is a typical application case of the present invention. In order to make the billing system have better processing performance, it is necessary to bind the data and the processing process on the same physical host for processing, so as to facilitate the nearby reading of data and improve the performance of the billing system. Data read efficiency.

Since billing events usually contain dozens or even hundreds of billing feature fields, if the data copy method is used to transfer these data between processes, the system performance will drop sharply. Moreover, each processing process of the billing system needs to constantly modify the data structure of the billing event message and pass it to the next processing process during the processing process, such as identifying the billing feature field (such as the calling party) from the original billing message. location, called location, family number sign, etc.), so the method for directly quoting the pointer of the present invention is more suitable for use in the billing system.

In the billing system shown in FIG. 5 , three processing processes are included, namely, authentication process, billing process, and accounting process. All three processes are controlled by the dynamic rule engine, and in this embodiment, the dynamic rule engine is the main control process of the system. In the actual billing system, there will be multiple processing processes for message data processing. For ease of description, in this embodiment, only the above authentication, charging, and accounting processes are described.

First, the message data of the standard call list is input into the authentication process. The standard call list message data includes characteristic fields such as the type of traffic, the subject, the object, the call start time, the call location, and the traffic volume. After the message data is processed, the processed results, such as characteristic fields such as product ID, are added to the shared memory linked list, and the pointer of the linked list is sent to the billing process. After the billing process obtains the content in the memory address mapped by the linked list pointer, similarly, after further processing the message data field, the result generated in this step (for example, cost item, cost) is added to the shared memory linked list , and send the pointer of the linked list to the next processing process (that is, the accounting process) for processing.

Fig. 7 is a flow chart of the message delivery method in the billing system of the present invention. in:

In step 701, the master control process creates a shared memory area. The size of the shared memory is calculated according to the processing capability of the system, and can also be adjusted dynamically.

As shown in Figure 6, in order to avoid memory fragmentation caused when allocating smaller memory blocks, the present invention adopts the memory pool technology, in the memory pool, there are a plurality of memory blocks, each memory block has a storage unit of predetermined length , the fields of various message data of the billing system with different lengths are respectively stored in memory blocks of corresponding lengths.

In step 702, the master control process creates a message queue. Creating a message queue provides resources that can interact with individual processing processes. The message queue is composed of multiple shared memory linked lists, including the allocated node linked list and the free node linked list.

In step 703, the authentication process receives the standard bill message data from the external process, and applies for an idle node from the message queue. The standard bill message data includes characteristic fields such as the type of traffic, subject, object, call start time, call location, and traffic volume. The authentication process receives the standard bill message from the external process through the IPC mechanism such as SOCKET or FIFO, and applies for an idle node from the message queue. The data structure of the message queue node usually includes the following information: the head pointer of the shared memory linked list; The tail pointer of the linked list; the number of message data fields. Applying for an idle message queue node is to apply for a memory block for the processed message.

In step 704, the authentication process processes the message received from the external process. The authentication process performs identification and authentication processing on the message data of the input standard bill, and a new characteristic field (such as product ID) is generated after processing.

In step 705, the authentication process links the processed message fields (including the processed feature fields and the original input standard bill message fields) end-to-end into a shared memory linked list, and then sends the head pointer of the linked list to the billing process. The authentication process uses the IPC mechanism (eg, FIFO mechanism) to send the head pointer of the linked list (ie, the pointer of the message queue node) to the accounting process. The head pointer of the linked list is the head pointer of the shared memory linked list of the idle node applied for by the authentication process. Since the head pointer pointing to the shared memory linked list is stored, the node becomes an allocated node.

In step 706, after receiving the head pointer of the shared memory linked list passed by the authentication process, the accounting process converts the pointer passed by the authentication process into a memory address in the address space. The billing process converts the pointer data into a memory address in the address space, so that the billing process can obtain the standard bill message data stored in the relevant address and the fields generated by the authentication process by accessing the memory address, so as to make Further processing avoids copying of message data and saves system resources.

In step 707, the billing process accesses the shared memory linked list in the memory address, and processes the message data accordingly. The message data field input by the authentication process is updated into the linked list, and then the head pointer of the linked list is sent to the accounting process.

In step 708, the accounting process obtains the shared memory linked list by accessing the memory address mapped by the linked list pointer, and performs corresponding processing to generate fields such as account, amount, accumulated item, accumulated value, and the like. The resulting output will be processed through the associated output process.

In step 709, after the processing is completed, the accounting process releases the processed message nodes to the idle node queue. As the last processing process, the accounting process needs to release the applied message queue node to the idle node queue after the processing is completed to further improve the utilization efficiency of the system.

Although the present invention discloses the above-mentioned embodiments, the specific embodiments are not used to limit the present invention, and any skilled person can make some modifications and modifications without departing from the spirit and scope of the present invention, so the present invention The scope of protection should be determined by the scope defined in the appended claims.

Claims (13)

1. A linked list-based interprocess message delivery method, characterized in that, comprising: a) The master control process creates a shared memory area, and the shared memory area is used to store message data for inter-process communication; The main control process creates a message queue, and the message queue includes an allocated node queue and an idle node queue; b) The first processing process receives an external message, applies for an idle node from the message queue, and links the message fields head to tail to form a shared memory linked list, and then sends the head pointer of the linked list to the second processing process; c) After receiving the head pointer of the shared memory linked list delivered by the first processing process, the second processing process converts the pointer delivered by the first processing process into a memory address in the address space; d) The second processing process accesses the shared memory linked list in the memory address, updates the result to the linked list after processing, and then sends the head pointer of the linked list to the subsequent processing process. 2. The inter-process message transfer method according to claim 1, wherein the shared memory area allocates a memory block of a predetermined length for each field of the message. 3. The inter-process message transfer method according to claim 1, characterized in that there are multiple processing processes for processing external messages. 4. The inter-process message transfer method according to claim 1, wherein the last processing process in the processing processes releases the processed message node into the idle node queue. 5 . The inter-process message transfer method according to claim 1 , wherein the nodes include: the size of the message queue, the head pointer of the linked list of idle nodes of the message queue, and the head pointer of the linked list of assigned nodes of the message queue. 6. The inter-process message transfer method according to claim 1, characterized in that FIFO or other inter-process communication IPC mechanisms are used between processing processes to send the head pointer of the shared memory linked list. 7. The inter-process message transfer method according to claim 1, wherein the message queue node data comprises: at least one of a head pointer of a shared memory linked list, a tail pointer of a shared memory linked list, and the number of message data fields. 8. A linked list-based billing system inter-process message delivery method, characterized in that it comprises: a) The master control process creates a shared memory area, and the shared memory area is used to store message data for inter-process communication; The main control process creates a message queue, and the message queue includes an allocated node queue and an idle node queue; b) The authentication process receives a message from an external process, and applies for an idle node from the message queue, and links the message fields head to tail into a shared memory linked list, and then sends the head pointer of the linked list to the billing process; c) After receiving the shared memory linked list head pointer passed by the authentication process, the billing process converts the pointer passed by the authentication process into a memory address in the address space of the process; d) The billing process accesses the shared memory linked list in the memory address, updates the processed result to the linked list after completing the processing, and then sends the head pointer of the linked list to the accounting process; e) The bookkeeping process pointer is converted into a memory address in the address space of the process, and the shared memory linked list in the memory address is accessed. 9. The inter-process message transfer method according to claim 8, wherein the shared memory area allocates a memory block of a predetermined length for each field of the message. 10. The inter-process message delivery method according to claim 8, wherein the last processing process in the processing processes releases the processed message node to the idle node queue. 11. The inter-process message transfer method according to claim 8, wherein the node comprises: the size of the message queue, the head pointer of the linked list of idle nodes of the message queue, and the head pointer of the linked list of assigned nodes of the message queue. 12. The inter-process message transfer method according to claim 8, characterized in that FIFO or other inter-process communication IPC mechanisms are used between each process to send the head pointer of the shared memory linked list. 13. The inter-process message transfer method according to claim 8, wherein the message queue node data comprises: at least one of a head pointer of a shared memory linked list, a tail pointer of a shared memory linked list, and the number of message data fields.

Images