Abstract
A method for transmitting structured data between a data-transmitting module and a data-receiving module. The structured data are structured as data blocks. The method uses a memory region for storing the data using the data-transmitting module and for reading the data using the data-receiving module to transmit data from the data-transmitting module to the data-receiving module. Data blocks in each case include a first field with an address, and at least one further field for storing links to further data blocks, so that a list of interlinked data blocks can be formed. An access data memory stores a start pointer to a first data block of the list and stores an end pointer to a last data block of the list.
Claims
1-12. (canceled)
13. A method for transmitting structured data between a data-transmitting module and a data-receiving module, wherein the structured data are structured as data blocks, and the method uses a memory region for storing the structured data using the data-transmitting module and for reading the structured data using the data-receiving module to transmit data from the data-transmitting module to the data-receiving module, wherein the data blocks each include a first field with an address, and at least one further field for storing links to further data blocks, so that a list of interlinked data blocks can be formed, and wherein an access data memory is provided for storing a start pointer to a first data block of the list and for storing an end pointer to a last data block of the list, the method comprising the following step: storing data using the data-transmitting module by first filling data blocks with the data independently of the list, and subsequently, after filling the data blocks, adding the filled data blocks to the list by adjusting pointer memories in the further fields of certain of the data blocks and adjusting the access data memory, wherein the access data memory is adjusted with an atomic operation, wherein an execution of the atomic operation cannot be interrupted by other operations.
14. The method according to claim 13, wherein, when the data are stored by the data-transmitting module, the filled data blocks are linked to one another, independently of the list, by pointers stored in the further fields of the filled data blocks, to form a new sublist before adding to the list takes place.
15. The method according to claim 13, wherein one or more data blocks are added to the list at a first data block of the list or a last data block of the list.
16. The method according to claim 13, the method further comprising: removing certain of the data blocks from the list by adjusting the access data memory with an atomic operation.
17. The method according to claim 16, wherein the removal of the certain data blocks from the list takes place starting from a first data block or a last data block by adjusting the access data memory with an atomic operation.
18. The method according to claim 16, wherein the data-receiving module reads the data blocks of the list in blocks, wherein each of the data blocks of the list has a lock memory in which the data-receiving module sets a reservation as long as the data of the data block are being read.
19. The method according to claim 18, wherein those of the data blocks that are removed from the list initially continue to exist after removal from the list and are released in a subsequent step for deleting the those data blocks when no reservation is set in the lock memory of the those data blocks.
20. The method according to claim 13, wherein each data block has a further second field and a further third field, wherein a pointer in the second field of the data block links to a data block arranged further toward a front of the the list, wherein a pointer in the third field of the data block links to a data block arranged further toward a rear of the list.
21. A data processing system, comprising: a data-transmitting module; a data-receiving module; and a memory region; wherein the data processing system is configured to structured data between the data-transmitting module and the data-receiving module, wherein the structured data are structured as data blocks, and the memory region is used for storing the data using the data-transmitting module and for reading the data using the data-receiving module to transmit data from the data-transmitting module to the data-receiving module, wherein data blocks each include a first field with an address, and at least one further field for storing links to further data blocks, so that a list of interlinked data blocks can be formed, and wherein an access data memory is provided for storing a start pointer to a first data block of the list and for storing an end pointer to a last data block of the list, wherein the data processing system is configured to: store data using the data-transmitting module by first filling data blocks with the data independently of the list, and subsequently, after filling the data blocks, adding the filled data blocks to the list by adjusting pointer memories in the further fields of certain of the data blocks and adjusting the access data memory, wherein the access data memory is adjusted with an atomic operation, wherein an execution of the atomic operation cannot be interrupted by other operations.
22. The data processing system according to claim 22, wherein the data processing system is part of a system for highly automated driving operation of a motor vehicle.
23. A non-transitory computer-readable storage medium on which are stored commands for transmitting structured data between a data-transmitting module and a data-receiving module, wherein the structured data are structured as data blocks, and the method uses a memory region for storing the structured data using the data-transmitting module and for reading the structured data using the data-receiving module to transmit data from the data-transmitting module to the data-receiving module, wherein the data blocks each include a first field with an address, and at least one further field for storing links to further data blocks, so that a list of interlinked data blocks can be formed, and wherein an access data memory is provided for storing a start pointer to a first data block of the list and for storing an end pointer to a last data block of the list, the commands, when executed by a computer, causing the computer to perform the following step: storing data using the data-transmitting module by first filling data blocks with the data independently of the list, and subsequently, after filling the data blocks, adding the filled data blocks to the list by adjusting pointer memories in the further fields of certain of the data blocks and adjusting the access data memory, wherein the access data memory is adjusted with an atomic operation, wherein an execution of the atomic operation cannot be interrupted by other operations.
Description
BRIEF DESCRIPTION OF THE DRAWINGS
[0046] FIGS. 1A and 1B show examples of lists used with the method according to the present invention described.
[0047] FIGS. 2A-2D show a first example of adding data blocks to a list according to the present invention.
[0048] FIGS. 3A-3E show a first example of adding data blocks to a list, according to the present invention.
[0049] FIGS. 4A-4D show a first example of adding data blocks to a list, according to the present invention.
[0050] FIGS. 5A-5D show first example of adding data blocks to a list, according to the present invention.
[0051] FIG. 6 shows a data processing system with which the described method is carried out.
DETAILED DESCRIPTION OF EXAMPLE EMBODIMENTS
[0052] FIG. 1A and FIG. 1B show the basic structure of the lists 5 that can be used for the method described here; FIG. 1A shows a doubly linked list 5. FIG. 1B shows a singly linked list 5.
[0053] The data blocks 1 that have been added to the list 5 and in each case form list nodes 2 of the list 5 can be seen in each case. Three values are stored in the access data memory 3. H stands for head or the beginning of the list. T stands for tail or the end of the list, and S stands for the length of the list.
[0054] The list 5 can be accessed via the access data memory 3. Via the access data memory 3, a data-receiving data processing module can access first the beginning or the end of the list 5 and, via it, all data blocks 1 or list nodes 2 in the list 5.
[0055] Each data block 1 contains a first field 4, which here, by way of example, contains a number as an address to the relevant data block 1 and which stands for the data contained in the relevant data block 1. Each data block 1 also has a second field n and a third field p, in which pointers 17 to the following data block 1 and to the previous data block 1 in the list 5, respectively, are stored, which data blocks also respectively form list nodes 2. Data blocks 1 that are not linked via pointers 17 to the access data memory 3 directly or indirectly via further data blocks 1 do not form list nodes 2 and are not part of the list.
[0056] It is important for the method described here that, in the first data block 1 of the list 5, the third field p, which is provided to point to a preceding data block 1 of the list 5, is unused or undefined. Likewise, in the last data block 1 of the list 5, the second field n, which is provided to point to a following data block 1 of the list, is unused or undefined. For this reason, links to further data blocks 1 that are not yet part of the list 5 but are to be added as list nodes 2 to the list 5 can be inserted here, without this leading to a change in the list 5 from the point of view of a data-receiving data processing module. A lock is not required in this case.
[0057] FIG. 2A to 5D now show various data processing operations with which data blocks 1 can be added as list nodes 2 to the list 5 or can be deleted from the list 5. In FIGS. 2A to 5D, by way of example, simple indices for data sets, pointers 17 and addresses are used in each case, which are used to explain the method and do not restrict the disclosure. Actual pointers 17, indices and addresses can be different and in particular adapted to the respective surroundings (operating system) on which the list 5 is operated.
[0058] FIGS. 2A-2D for example, shows the situation in which a data block 1 is to be added as a new list node 6 to the list 5. [0059] Step a) (FIG. 2A) shows that the new data block 1 is first filled with data externally (without said data block being connected to the list 5) so that a new list node 6 is prepared. [0060] Subsequently, in step b) (FIG. 2B), the pointers 17 in the third field p of the first data block 1 of the list 5 and in the second field n of the data block 1 to be added are adjusted so that the data block 1 to be added or the new list node 6 is already filled so that it is inserted into the list 5. Since the third field p of the first data block 1 of the list 5 is undefined, this third field p can simply be adjusted here without having to consider other processes that access the list 5. Access by other processes to the list 5 takes place only via the access data memory 3. In this case, the third field p of the first data block 1 of the list 5 is irrelevant. Furthermore, in step b) (FIG. 2B), a new access data memory data set 8 is prepared, which becomes applicable when the new list node 6 is added to the list 5. For this purpose, an access data memory copy 9, which is stored securely in such a way that other processes cannot access it, is first created of the access data memory 3. The new access data memory data set 8 is subsequently created on the basis of the data taken from the access data memory 3. It can be seen here that the assignment (first list node=0, list length=3, last list node=2) of the access data memory 3 is updated to the assignment (first list node=3, list length=4, last list node=2). [0061] Step c) (FIG. 2C) is the critical step of adding the new list node 6 to the list 5. For carrying out the method described, it is essential that step c) (FIG. 2C) is carried out with a so-called atomic operation, which is carried out in a processor for carrying out the method as a whole so that no further processes can interrupt the execution of the atomic operation. Used here is an atomic operation that is able to compare a data set to another data set and then to update a data set on the basis of the comparison result. Such an atomic operation is generally also referred to as atomic compare exchange. With this operation, the assignment of the access data memory 3 is compared to the assignment of the securely stored access data memory copy 9. Only if it is found here that the assignment of the copy of the access data memory 9 still corresponds to the access data memory 3, the access data memory 3 is overwritten with the new access data memory data set 8 within the atomic operation. It is important for the described method that the described atomic operation atomic compare exchange is used here, because this ensures that the new list node 6, prepared as in step b) (FIG. 2B), is directly added to the lists 5 only if other processes have not changed the list 5 in the meantime. [0062] In step d) (FIG. 2D), the list 5 is now expanded by the new list node 6.
[0063] FIGS. 3A-3E now shows the same sequence, which is also described in FIGS. 2A-2D. However, the difference here is that the atomic operation atomic compare exchange in step c) (FIG. 3C) fails. As a result, deviations occur starting from step c) (FIG. 3C), which are described below: [0064] In step c) (FIG. 3C), the atomic operation atomic compare exchange fails, for example because, in the meantime, another process has accessed the list 5 and completely deleted the list 5. The comparison of the access data memory 3 to the securely stored access data memory copy 9 has the result that equality no longer exists. The access data memory 3 is not updated with the new access data memory data set 8 already prepared in step b) (FIG. 3B). [0065] For this reason, the access data memory 3 is checked again in step d) (FIG. 3D). In this case, it is determined that the list 5 is now empty. The access data memory 3 has the following assignment (first list node=X=not assigned, list length=0, last list node=X=not assigned). [0066] Now, according to step e) (FIG. 3E), the list 5 is completely newly constructed with the new list node 6 as the sole data set 1 in the list 5 and the following assignment of the access data memory 3 (first list node=3, list length=1, last list node=3). The pointer 17 stored in field n of the new list node 6 in step b) (FIG. 3B) to the former first list node 2 of the list 5 0 is present but not relevant, because this field n is not defined for the list 5. The value in the second field n of the last list node 2 of the list 5 is not taken into account and can simply remain as an undefined value in the list node 2.
[0067] FIGS. 4A-4D show the special case that not only a single new list node 6 is to be added to the list 5, but rather a separate new sublist 7 consisting here of two new list nodes 6 or of two data blocks 1. [0068] The new sublist 7 is prepared here according to step a) (FIG. 4A) without any existing connection to the list 5. The sublist 5 preferably has its own sublist access data memory 10. [0069] According to step b) (FIG. 4B), just as according to FIGS. 2B and 3B, the creation of the access data memory copy 9 and the generation of the new access data memory data set 8 then take place on the basis of the access data memory 3 and the sublist access data memory 10. The first list node 2 of the supplemented list 5 corresponds to the first new list node 6 of the new sublist 7. The list length of the supplemented list 5 corresponds to the sum of the list lengths of the original list 5 and of the new sublist 7. The assignment of the new access data memory data set 8 is thus as follows (first list node=3, list length=5, last list node=2). In addition, the second field n of the last new list node 6 of the new sublist 7 and the third field p of the first list node 2 of the list 5 are adjusted in preparation of later adding the new sublist 7 to the list 5. [0070] In step c) (FIG. 4C), the atomic operation atomatic compare exchange is carried out in order to add the new sublist 7 to the list 5. This operation is successful here as also in the variant shown in FIG. 2C. [0071] In step d) (FIG. 4D), the list 5 with the two new list nodes 6 thus results from the new sublist 7.
[0072] FIGS. 5A-5D show a special addition to the described method, namely the addition that the list 5 has a fixed length, which is here, for example, fixed to three list nodes 2. If a new list node 6 is added at the beginning of the list 5, a list node 2 must also always be deleted from the list 5 at the end of the list so that the length of the list 5 remains constant and, in the example here, corresponds to three list nodes 2. In the following, only the (minor) differences of the method sequence according to FIGS. 5A-5D from the method sequence according to FIGS. 2A-2D, 3A-3E, and 4A-4D are described. Otherwise, for explaining FIGS. 5A-5D, reference is made to the explanations relating to FIGS. 2A-2D, 3A-3E, and 4A-4D and in particular to FIGS. 2A-2D. [0073] Step a) (FIG. 5A) takes place just as according to FIGS. 2A, 3A and 4A. [0074] In step b) (FIG. 5B), the second field n of the new list node 6 is adjusted, wherein the third field p of the first list node 2 of the list 5 is adjusted just as according to FIGS. 2B, 3B, and 4B. The access data memory copy 9 is created. The new access data memory data set 8 is generated somewhat differently than according to FIGS. 2B, 3B, and 4B. With knowledge of the fixed list length (here three list nodes), the address in the first field 4 of the list node 2 of the list 5 that will be the new last list node 2 of the list 5 after adding the new list node 6 is ascertained. This is the address 1 here. This results in the following assignment for the new access data memory data set 8 (first list node=3, list length=3, last list node=1). [0075] In step c) (FIG. 5C), the access data memory 3, and thus the list 5, is adjusted with the atomic operation atomic compare exchange.
[0076] FIG. 6 shows a data processing system 14, which is provided for carrying out the described method. The data processing system 14 has a data-transmitting module 12 and a data-receiving module 13 and a memory region 11 to which the data-transmitting module 12 and the data-receiving module 13 respectively have unlimited access and in which data are to be exchanged without data locks (in a lock-free manner) between the data-transmitting module 12 and the data-receiving module 13 with the described method. The data processing system 14 also has at least one processor 16 on which the processes are executed. Processes here are in particular the data-transmitting module 12 and the data-receiving module 13, which are executed on the processor 16 or which execute commands that can be executed by the processor 16, which commands change the memory region 11. The processor 16 provides a plurality of operations, namely, in particular, also atomic operations. For carrying out the described method, it is essential that the processor 16 provides an atomic operation for exchanging a data set in the access data memory, which operation makes it possible to check the content of the access data memory and to exchange the content for the new data set only if the content matches an expected content (atomic compare exchange).
[0077] FIG. 6 shows that data blocks 1 and the access data memory 3 are provided in the memory region 11. Of six data blocks 1 shown by way of example here, four data blocks 1 are part of the list 5. The six data blocks 1 shown here form the mempool referred to above, in which the list 5 is provided. Via the access data memory 3, the first data block 1 of the list 5 can be accessed, which is here the data block 1 with the index 3. The data blocks 1 in the list 5 are all linked to one another via pointers 17. The index 5 of the last data block 1 of the list 5 and the length of the list 5, which consists of four data blocks here, are stored in the access data memory 3.
[0078] The actual filling of the data blocks 1 takes place externally to the list 5 and is here indicated with the data transfer 15 from the data-transmitting module 12 to the data-receiving module 13. The data-receiving module 13 reads the data from the data blocks 1 after the data-receiving module 13 has ascertained via the access data memory 3 which data blocks 1 are to be read. Data blocks 1 that are currently being read can be blocked by a lock. However, this does not impair the possibility of changing the list 5 by means of the data-transmitting module 12. Data blocks 1 can be deleted from the list 5 by changing the access data memory 3, without this being impaired by a lock on the individual data block 1. The data-receiving module 13 can nevertheless continue to read the data block 1. Only if precisely this data block 1 is to be filled again later is a release of the data block 1 by the data-receiving module 13 necessary. So that the described method is executed smoothly, it is important that sufficient data blocks 1 are available so that new list nodes 6 can always be prepared as data blocks 1 outside the list 5 before the new list nodes 6 or data blocks 1 are added to the list 5 with an atomic operation relating to the access data memory 3.
