JP3823878B2 - Queue control system, queue control method, and queue control program - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a queue control system, a queue control method, and a queue control program for a computer system, and more particularly to a queue control system, a queue control method, and a queue control program that are preferably used for interprocess communication.
[0002]
[Prior art]
Conventionally, as a queue control system for sequentially registering and retrieving asynchronously generated data in, for example, a FIFO (first-in first-out) method, a one-way chain having a head chain entry and a forward chain pointer in each entry, an index Systems and methods using keys are known. The following are referenced as publications on queue management:
(A) Japanese Patent Laid-Open No. 4-130929
(B) JP-A-4-259040
(C) Japanese Patent Laid-Open No. 11-184716
(D) Japanese Patent Laid-Open No. 6-68040
The system described in the publications (a) to (d) is outlined below.
[0003]
Japanese Patent Laid-Open No. 4-130929 discloses a skip search means for grouping events having the same key value and skipping search processing by using the same key pointer by providing the same key pointer that can be searched corresponding to the group. And a queue management method that includes a new group when an event having the same key value is added, and the same key pointer management means for adding the event to the group when the group is already configured Is disclosed. The same key pointer is a pointer for grouping data having the same key value and chaining the data so that search processing can be performed.
[0004]
In the queue management system having such a configuration, even when a lot of data with the same key value is registered, the search for data with different key values can be skipped by using the same key pointer by the skip search means. The search process can be performed quickly. In addition, when registering new data, the same key pointer management means configures a new group or adds data to an existing group, thereby keeping the key values of all data constituting the group equal. be able to.
[0005]
Japanese Patent Laid-Open No. 4-259040 discloses determination means for determining whether or not a new queue block needs to be acquired using management data of a circular queue management means for managing the queuing state of the circular queue. A queue management means having an acquisition means for acquiring a new queue block and a setting means for queuing the new queue block to the circular queue when the determination means determines that the acquisition is necessary; In addition, an automatic expansion of the queue block of the circular queue is realized.
[0006]
In the queue management method having such a configuration, queue management can be executed simply by switching chained queues. Therefore, processing steps for queue management are reduced compared to queues that do not employ a circular configuration, and Management can be speeded up. In addition, when all the queue blocks are in use, if new data is registered, a new queue block is acquired by the acquisition unit, and the queue block acquired by the setting unit is queued in the circular queue. This makes it possible to automatically add a queue block for the circular queue.
[0007]
Japanese Patent Application Laid-Open No. 11-184716 has a multitask that separately executes queuing processing and queuing out processing of event queue elements, and a head pointer that always points to the head of an event queue composed of event queue elements And two pairs of final pointers dedicated to queuing and dedicated to queuing at all times, and a forward chain pointer and a backward chain pointer for concatenating consecutive event queue elements in the event queue element A queue management system having a configuration provided is disclosed. In other words, a queuing task, a queue-out task, a confirmation type inter-task notification means, a queue buffer, a queuing event queue head pointer, a queuing event queue last pointer, and a queue-out The event queue includes a head pointer of the dedicated event queue, a final pointer of the queue queue dedicated to the queue, a queue queue dedicated event queue, a queue queue dedicated event queue, and individual event queue elements constituting the event queue. Each event queue element has a forward chain pointer and a backward chain pointer.
[0008]
In the queue management method having such a configuration, when registering data in the queue, the queuing processing task operates, registers the data at the end of the queuing dedicated head pointer, and the order in the preceding and succeeding event queue elements. Reposition the direction chain pointer and the reverse chain pointer. When retrieving data from the queue, the queue-out processing task operates, retrieves data from the end of the queue-dedicated final pointer, and re-stretches the forward and backward chain pointers in the preceding and succeeding event queue elements. In this way, data is registered at the point destination of the first pointer dedicated for queuing during queuing, and data is extracted from the point destination of the final pointer dedicated for cueing out during cueing. Processing is possible.
[0009]
In addition, if there is a data registration request during the operation of the queue-out processing task, the queuing processing task creates another event queue for processing, and uses the confirmation type inter-task notification means as the timing. Switch event queue. For this reason, the queuing process and the queue-out process do not occur at the same time for one event queue, and the memory exclusive control is not necessary even in multitasking, and an efficient queue process is possible.
[0010]
Japanese Laid-Open Patent Publication No. 6-68040 describes a queue control method using a ring buffer type communication queue. Similarly, Japanese Patent Application Laid-Open No. 1-129345 (invention name: “multiprocessor system”), Japanese Patent Application Laid-Open No. 60-1116064 (invention name: “communication method between distributed processors”), and Japanese 58-501740 (Title of the Invention: “Interface Mechanism of Paired Processors such as Host and Peripheral Control Processor in Data Processing System”) adopts a ring buffer type queue for interprocessor communication Thus, a technique for performing communication control is described.
[0011]
Japanese Patent Laid-Open No. 6-68040 writes a resource number, which is transmission data, at a location indicated by a write pointer in a communication queue at the time of transmission between processors, and at reception, a resource number, which is reception data, from the location indicated by a read pointer. A queue control method for inter-processor communication configured to take out data is disclosed. The communication queue includes a reception read pointer, a transmission write pointer, and communication resources.
[0012]
In the queue control system having such a configuration, at the time of data registration, data is written to the point destination of the write pointer and the write pointer is updated. At the time of data extraction, data is extracted from the point destination of the read pointer and the read pointer is updated. For this reason, the processing time of the communication queue can be advanced as compared with the chain method, and the control of the communication queue can be simplified.
[0013]
However, the conventional systems described in the above publications have the following problems.
[0014]
As a first problem, in the chain-type queue management method, it is necessary to reset the forward chain pointer or the backward chain pointer of the preceding and following queue entries at the time of data registration and data retrieval, which slows down the processing. That is.
[0015]
The reason is that queue management is performed by connecting each queue entry with a chain pointer.
[0016]
The second problem is that the queue cannot be expanded at an arbitrary point of time in the ring buffer type queue management method.
[0017]
The reason for this is that in the ring buffer method, the end of the buffer is connected to the beginning, and the end of the buffer is used continuously until it reaches the end. This is because an area cannot be inserted. Although the queue can be expanded by extending the end of the buffer, it is impossible to expand the queue at any point in the system.
[0018]
The third problem is that when a queue is used for inter-process communication, if there is no empty entry at the time of data registration, or if there is no data registered at the time of data retrieval, the waiting control is performed by the user himself / herself. Is a heavy burden on users.
[0019]
This is because the conventional queue management method does not have a function of waiting for data registration or retrieval.
[0020]
[Problems to be solved by the invention]
Accordingly, the present invention has been made in view of the above problems, and an object of the present invention is to provide a queue control system capable of performing data registration in a queue and data retrieval from the queue at high speed. is there.
[0021]
Another object of the present invention is to expand the queue automatically when the number of registered data temporarily increases, and degenerate the queue when the number of data decreases, so that resources can be used efficiently. To provide a queue control system.
[0022]
Still another object of the present invention is to provide a queue control system that can easily realize interprocess communication by waiting for data and empty entries.
[0023]
[Means for Solving the Problems]
A queue control system according to one aspect of the present invention that achieves at least one of the above objects is a segment used as a queue, and a queue control information section for storing queue control information in the segment, and data is registered A plurality of segments each having a data portion made up of a plurality of entries, a circular link is set for each segment, and one of the plurality of segments linked in a circular manner (referred to as a “first segment”) Queue generating means for setting an initial value in the queue control information section of the first segment, and the queue control information section of the first segment holds at least a registration pointer and a retrieval pointer indicating a data registration destination entry and a retrieval entry, The entry pointed to by the registration pointer in the queue control information section of the first segment contains data. And it includes a data registration means for registering, and data retrieval means for retrieving the data from the entry extraction pointer queue control information part of the first segment pointed to, and queues the exclusive means for performing exclusive control of the queue.
[0024]
More specifically, a queue control information unit that stores queue control information in the queue segment, and a data unit in which data is registered, a plurality of queue segments are generated, and a circular link is set for each segment. A queue initialization unit that sets an initial value in the queue control information unit, a queue generation unit, a data registration unit that registers data in the entry pointed to by the registration pointer in the queue control information unit, and a retrieval pointer in the queue control information unit Data fetching means for fetching data from the entry, data reverse fetching means for fetching data from the entry immediately before the entry pointed to by the registration pointer of the queue control information section, and queue exclusion means for excluding the queue so that it cannot be used simultaneously by a plurality of processes Then, the queue is stopped, and subsequent data registration and data retrieval are performed. Queue stop means for stopping, Queue erasure means for erasing queue segments, and queue re-initialization for re-initializing the queue control information section of the queue stopped by the queue stop means so that the queue can be used again And a queue is created or deleted in response to a request from the user program, and data is registered in the queue and fetched from the queue at high speed.
[0025]
In addition, the queue control system of the present invention uses a queue expansion unit that generates a new segment to be used as a queue and resets a link between segments when there is no empty entry at the time of data registration, and is used for data retrieval. Queue degeneration means to delete unused segments and re-establish links between segments. When the number of registered data temporarily increases, the queue is automatically expanded. Operates to degenerate the queue.
[0026]
Also, the queue control system according to the present invention waits for data to be taken out by another process when there is no free entry at the time of data registration, and when there is no data registered at the time of data fetching Has a waiting means for waiting for data to be registered by other processes, and if there is no entry that can be registered at the time of data registration or if there is no data registered at the time of data retrieval, the registration of data and the empty space of the entry are cleared. Operates to wait.
[0027]
A queue control method according to another aspect of the present invention includes:
(A) A segment used as a queue, and a plurality of segments each including a queue control information section for storing queue control information in the segment and a data section including entries in which data is registered, A step of setting an annular link to the segment, and setting an initial value in a queue control information part of one segment (referred to as “first segment”) of the plurality of segments linked in a ring, The queue control information part of the segment holds at least a registration pointer and a retrieval pointer that point to a data registration destination entry and a retrieval entry,
(B) registering data in an entry indicated by a registration pointer in the queue control information section of the first segment;
(C) extracting data from the entry indicated by the extraction pointer in the queue control information section of the first segment;
(D) exclusive control of the queue.
[0028]
A program according to another aspect of the present invention is a program for managing a queue by a computer, a segment used as a queue, a queue control information section for storing queue control information in the segment, and a data A plurality of segments each having a data portion made up of registered entries, a circular link is set for each of the segments, and one of the plurality of segments linked in a circular manner (“first segment”) The queue control information part of the first segment stores at least a registration pointer and a retrieval pointer indicating the data registration destination entry and the retrieval entry. The data pointed to the entry pointed to by the registration pointer in the queue control information section of the first segment. A process of registering, and processing to retrieve data from the entry extraction pointer queue control information part of the first segment pointed consists program for executing a process of exclusive control of the queue, to the computer.
[0029]
DETAILED DESCRIPTION OF THE INVENTION
Next, embodiments of the present invention will be described in detail with reference to the drawings. FIG. 1 is a diagram showing the configuration of an embodiment of the present invention. Referring to FIG. 1, the system according to the first embodiment of the present invention includes a computer system 100 that operates under program control, a queue control system 110, a queue segment 130, and a user program 140. It is configured.
[0030]
The queue control system 110 includes a queue generation unit 111, a queue stop unit 112, a queue deletion unit 113, a queue reinitialization unit 114, a data registration unit 115, a data extraction unit 116, and a data reverse extraction unit 117. And queue exclusion means 118.
[0031]
The queue segment 130 includes a queue control information unit 131 and a queue data unit 132.
[0032]
Each of these means generally operates as follows.
[0033]
The queue generation unit 111 generates a plurality of queue segments and sets a circular link to each segment.
[0034]
In addition, the queue generation unit 111 provides a queue control information section in the generated queue segment and sets an initial value.
[0035]
The queue stop unit 112 stops the queue and prohibits subsequent registration and retrieval of data.
[0036]
The queue erasure unit 113 erases each queue segment of the queue that has been stopped by the queue stop unit 112.
[0037]
The queue reinitializing unit 114 reinitializes the queue control information unit 131 of the queue that has been stopped by the queue stopping unit 112. After that, the queue reinitialization unit 114 sets the queue to a busy state so that the queue can be used again.
[0038]
In response to a request from the user program 140, the data registration unit 115 registers the data passed from the user program 140 in the entry indicated by the registration pointer in the queue control information unit 131.
[0039]
In response to a request from the user program 140, the data retrieval unit 116 retrieves data from the entry indicated by the retrieval pointer in the queue control information unit 131 and returns it to the user program 140.
[0040]
In response to a request from the user program 140, the data reverse extraction unit 117 extracts data from the entry immediately before the entry indicated by the registration pointer in the queue control information unit 131 and returns the data to the user program 140.
[0041]
The queue exclusion unit 118 is used by the units 111 to 117 of the queue control system 110 and performs exclusive control so that the queue segment is not referred to or updated by other processes.
[0042]
In the queue control system 110, the queue generation unit 111, the queue stop unit 112, the queue deletion unit 113, the queue reinitialization unit 114, the data registration unit 115, the data extraction unit 116, the data reverse extraction unit 117, and the queue exclusion unit 118 are computers. Each function and process is realized by the program executed above.
[0043]
Next, the overall operation of the present embodiment will be described in detail with reference to the flowcharts of FIGS. 1, 2, 3, and 4 to 11. FIG. 2 is a diagram schematically showing a queue segment in the first embodiment of the present invention. FIG. 3 is a diagram illustrating an example of the queue control information unit. FIG. 4 is a flowchart for explaining an example of the operation of the queue generation unit 11 according to the first embodiment of the present invention.
[0044]
First, the user program 140 uses the queue generation unit 111 to generate the queue segment 130 in order to use the queue.
[0045]
The user program 140 informs the queue generation unit 111 of information such as the number of segments and the data length.
[0046]
The queue generation unit 111 first acquires the initial number of segments transmitted from the user program 140 (step S11 in FIG. 4).
[0047]
Next, the queue generation unit 111 generates segments for the initial number of segments (step S12), and sets a circular link between the generated segments (step S13).
[0048]
As shown in FIG. 2, the queue segment has a structure linked in a ring shape for each segment.
[0049]
Subsequently, the queue generation unit 111 sets an initial value in the queue control information unit 131 of the first segment (step S14), acquires a semaphore such as an exclusion semaphore or a notification semaphore, and stores it in the queue control information unit 131. Store (step S15).
[0050]
Finally, the queue generating unit 111 sets a status flag (not shown) to the “in use” state (step S16), and returns the address of the first segment to the user program 140 (step S17). The status flag is set in an arbitrary storage device such as a rewritable memory or register in the computer constituting the queue control system of FIG. 1, and the status of the queue (for example, status of use, stop, etc.) is set. .
[0051]
Thereafter, when the user program 140 operates the queue, it informs the queue control system 110 of the address of the returned first segment. That is, the address of the first segment is used as a key.
[0052]
Also, as shown in FIG. 3, information is stored in the queue control information unit 131 only in the first segment, and only the address of the next segment is held after the second segment. In other words, as shown in FIG. 3, the segment 1 includes registration pointer, fetch pointer, data length, number of data, next segment, number of used segments, number of initial segments, maximum number of segments, exclusive semaphore, notification semaphore, and number of waits. Segment 2 is initialized in the next segment column of segment 1, segment 3 is initialized in the next segment column of segment 2, and segment 1 is initialized in the next segment column of segment 3. In the queue control information sections of segments 2 and 3, only the next segment column is set.
[0053]
FIG. 5 is a flowchart for explaining an example of the operation of the queue stopping unit 112 according to the first embodiment of the present invention. When the user program 140 ends the use of the queue, the queue stop unit 112 is used to stop the queue, and the queue deletion unit 113 is then used to delete the queue segment 130. In addition, the queue can be used again by using the queue reinitialization unit 114 after the queue is stopped.
[0054]
First, the queue stopping unit 112 uses the queue exclusion unit 118 to exclude the queue from being used simultaneously by other processes (step S21 in FIG. 5).
[0055]
Next, the queue stopping unit 112 checks a state flag indicating the state of the queue. If the state is “in use” (YES in step S22), the queue stopping unit 112 sets the state flag to the “stopped” state.
[0056]
Finally, the queue stopping unit 112 releases the queue exclusion using the queue exclusion unit 118 (step S24).
[0057]
If the status flag is not “in use” (NO in step S22), it is in a state where it cannot be stopped, so that the stop fails (step S25).
[0058]
FIG. 6 is a flowchart for explaining an example of the operation of the queue erasing unit 113 in the first embodiment of the present invention. The queue erasure unit 113 first excludes the queue using the queue exclusion unit 118 (step S31 in FIG. 6).
[0059]
Next, the queue erasing unit 113 checks the status flag, and if the status is “stopped” (YES in step S32), the queue erasing unit 113 erases all the queue segments used (step S33).
[0060]
Next, the queue erasure unit 113 releases the exclusion of the queue using the queue exclusion unit 118 (step S34), releases the semaphore (step S35), and ends.
[0061]
If the status flag is not in the “stop” state (NO in step S32), the deletion is impossible because the state cannot be deleted (step S36), the queue exclusion unit 118 releases the exclusion of the queue (step S37), and the process ends. .
[0062]
FIG. 7 is a flowchart for explaining an example of the operation of the queue reinitialization means 114 in the first embodiment of this invention. First, the queue reinitialization unit 114 uses the queue exclusion unit 118 to exclude the queue (step S41 in FIG. 7).
[0063]
Next, the queue reinitialization unit 114 checks the status flag, and if the status is “stopped” (YES in step S42), sets an initial value in the queue control information unit 131 of the first segment. (Step S43). In the queue control information section 131 of the first segment, the area that the queue reinitialization unit 114 sets to the initial value is only the area whose value is updated by using the queue.
[0064]
Subsequently, the queue reinitialization unit 114 sets the status flag to the “in use” state (step S44).
[0065]
Finally, the queue reinitialization unit 114 releases the queue exclusion by the queue exclusion unit 118 (step S45), and the process ends.
[0066]
In the state flag check, if the state flag is not in the “stop” state (NO in step S42), the reinitialization fails because the queue reinitialization unit 114 cannot perform reinitialization (step S46). ).
[0067]
When the user program 140 registers data in the queue, the data registration unit 115 is used. Further, when the user program 140 retrieves data from the queue, the data retrieving unit 116 or the data reverse retrieving unit 117 is used. Here, when the user program 140 retrieves data using the LILO (Last In Last Out) method, the data retrieving unit 116 is used. When the user program 140 retrieves data using the LIFO (Last In First Out) method, the data reverse retrieval is performed. Means 117 is used.
[0068]
FIG. 8 is a flowchart for explaining an example of the operation of the data registration unit 115 in the first embodiment of the present invention. The data registration unit 115 first uses the queue exclusion unit 118 to exclude the queue (step S51 in FIG. 8).
[0069]
Next, the data registration unit 115 checks the status flag. If the status is “in use” (YES in step S52), the data registration unit 115 subsequently checks the entry. If the entry pointed to by the registration pointer in the queue control information section 131 (referred to as “registration entry”) is not the last entry in the segment (NO in step S53), the next entry of the registration entry is set in the next registration pointer (step S54). ). The entry next to the registration entry can be easily obtained by adding the value of the data length of the queue control information section 131 to the intra-segment offset of the registration pointer.
[0070]
If the registration entry is the last entry in the segment (YES in step S53), the data registration unit 115 sets the first entry of the next segment in the next registration pointer (step S55). The next registration pointer is a work area used only by the data registration unit 115.
[0071]
Next, when the entry pointed to by the next registration pointer is not the same as the entry pointed to by the take-out pointer of the queue control information section 131 (NO in step S56), the data registration unit 115 determines that data can be registered. Then, the data transmitted from the user program 140 is transferred to the registration entry (step S57).
[0072]
Subsequently, the data registration unit 115 updates the registration pointer of the queue control information unit 131 to point to the entry pointed to by the next registration pointer (step S58), and adds 1 to the number of data in the queue control information unit 131 (step S58). S59).
[0073]
Finally, the data registration unit 115 releases the queue exclusion using the queue exclusion unit 118 (step S60) and ends.
[0074]
If the entry pointed to by the next registration pointer is the same as the entry pointed to by the take-out pointer in the queue control information section 131 (YES in step S56), this means that the registration pointer catches up with the take-out pointer. There is no state. In this case, since there is no empty entry, data registration is failed (step S61).
[0075]
In the status flag check, if the status flag is not in the “in use” state (NO in step S52), the registration fails because the data cannot be registered (step S62).
[0076]
FIG. 9 is a flowchart for explaining an example of the operation of the data fetching unit 116 in the first embodiment of the present invention. First, the data extraction unit 116 uses the queue exclusion unit 118 to exclude the queue (step S71 in FIG. 9).
[0077]
Next, the data fetching means 116 checks the status flag, and if the status is “in use” (YES in step S72), it checks the number of data registered next. If the number of data in the queue control information section 131 is greater than 0 (YES in step S73), this means that data exists, and the user points to the entry pointed to by the retrieval pointer in the queue control information section 131 ("retrieve entry"). Data is transferred to the data return area transmitted from the program 140 (step S74).
[0078]
Next, the data extraction unit 116 subtracts 1 from the number of data in the queue control information unit 131 (step S75).
[0079]
Subsequently, when the fetch entry is not the last entry in the segment (NO in step S76), the data fetch unit 116 updates the data fetch pointer of the queue control information unit 131 to point to the entry next to the fetch entry ( Step S77).
[0080]
If the fetch entry is the last entry in the segment (YES in step S76), the data fetch means 116 updates the data fetch pointer to point to the first entry of the next segment (step S78).
[0081]
Finally, the data fetch unit 116 releases the queue exclusion using the queue exclusion unit 118 (step S79), and the process ends.
[0082]
If the number of data is 0 (NO in step S73), there is no registered data, and data fetching fails (step S80).
[0083]
In the status flag check, if the status flag is not in the “in use” state (NO in step S72), the data cannot be extracted, and the extraction fails (step S81).
[0084]
FIG. 10 is a flowchart for explaining an example of the operation of the data reverse extraction unit 117 according to the first embodiment of the present invention. First, the data reverse extraction unit 117 uses the queue exclusion unit 118 to exclude the queue (step S91 in FIG. 10).
[0085]
Next, the data reverse extraction means 117 checks the status flag, and if the status is “in use” (YES in step S92), it checks the number of data registered next.
[0086]
If the number of data in the queue control information unit 131 is greater than 0 (YES in step S93), this means that registered data exists in the queue segment.
[0087]
If the entry (registration entry) pointed to by the registration pointer in the queue control information section 131 is not the first entry in the segment (NO in step S94), the data reverse extraction means 117 points to the entry immediately before the registration entry. The registration pointer is updated (step S95).
[0088]
The entry immediately before the registration entry can be easily obtained by subtracting the data length value of the queue control information section 131 from the intra-segment offset of the registration pointer.
[0089]
If the registration entry is the first entry in the segment (YES in step S94), the data reverse extraction unit 117 obtains the segment immediately preceding the segment pointed to by the registration pointer (step S96), and The registration pointer is updated to point to the final entry (step S97).
[0090]
Here, the segment queue control information section 131 does not have a link to the previous segment, but since each segment constituting the queue is linked in a ring shape, the data reverse fetching means 117 is linked to the next segment. By following the above, it is possible to reach the previous segment.
[0091]
Subsequently, the data reverse extraction means 117 transfers the data from the entry indicated by the updated registration pointer to the data return area transmitted from the user program 140 (step S98).
[0092]
Next, the data reverse extraction means 117 subtracts “1” from the number of data in the queue control information unit 131 (step S99).
[0093]
Finally, the data reverse extraction unit 117 releases the exclusion of the queue using the queue exclusion unit 118 (step S100) and ends.
[0094]
When the number of data is “0” (NO in step S93), there is no registered data, and data fetching fails (step S101).
[0095]
In the status flag check, if the status flag is not “in use” (NO in step S92), registration is failed because data cannot be registered (step S102).
[0096]
Next, the effect of this Embodiment is demonstrated.
[0097]
In this embodiment, at the time of data registration, the data is transferred to the entry pointed to by the registration pointer, the registration pointer is updated to point to the next entry, and at the time of data fetching, the data is fetched from the entry pointed to by the fetching pointer and fetched. Since the pointer is updated so that it points to the next entry, it is not necessary to search the queue or replace the forward chain at the time of data registration and data retrieval, and register and retrieve data at high speed. It can be carried out.
[0098]
Further, in the present embodiment, since there are two means for extracting data in the forward direction and means for extracting in the reverse direction, the FIFO method and the LIFO method can be mixed. Yes. As a result, the LIFO method can be normally used when canceling data once registered using the FIFO method.
[0099]
Further, in the present embodiment, a queue is generated in response to a request from the user program, and subsequent queue operations are performed using the address of the first segment as a key. Thus, a plurality of queues can be used.
[0100]
Further, in the present embodiment, the configuration is such that the queues that have been used can be deleted and reused, so that memory resources can be used efficiently.
[0101]
【Example】
Next, the operation of this embodiment will be described using specific examples.
[0102]
When the user program 140 starts using the queue, it requests the queue generation unit 111 to generate a queue with a data length of 48 bytes, an initial number of segments of 3, and a maximum number of segments of 10.
[0103]
The queue generation unit 111 acquires “3” as the initial number of segments (step S11 in FIG. 4), and generates three segments (step S12).
[0104]
Subsequently, an annular link is set between the generated segments (step S13).
[0105]
The segments are connected in a ring by the “next segment” region as shown in FIG. Subsequently, an initial value is set in the queue control information section 131 of the first segment (segment 1 in FIG. 2) (step S14).
[0106]
The queue control information unit 131 is configured with the contents shown in FIG. 3, and the initial values of the registration pointer and the retrieval pointer are set so as to point to the first entry of the segment 1.
[0107]
“48 bytes” transmitted from the user program 140 is set as the data length, and “0” is set as the number of data.
[0108]
The next segment area is not set here because the circular link is set earlier.
[0109]
The initial segment number and the maximum segment number are set to “3” and “10”, which are values transmitted from the user program, and the current segment number, that is, the initial segment number “ 3 ”is set.
[0110]
A null value is set for the exclusive semaphore and the notification semaphore, and the number of waiting processes is set to “0”.
[0111]
Next, the queue generating unit 111 acquires the exclusive semaphore and the notification semaphore and stores them in the queue control information unit 131 (step S15).
[0112]
Subsequently, the queue generation unit 111 sets the status flag to “in use” and returns the address A of the segment 1 to the user program 140.
[0113]
Thus, the generation of the queue is completed, and thereafter, the user program 140 can operate this queue using the address A of the returned first segment.
[0114]
Next, an operation for registering data will be described.
[0115]
As shown in FIG. 2 and FIG. 3, when the registration pointer points to “segment 1 entry 4”, the retrieval pointer points to “segment 2 entry 6”, and the number of registered data is “9” If registration of new data is requested, the data registration means 115 first excludes the queue (step S51 in FIG. 8), and if the status flag is checked, the status is “in use” (YES in step S52). .
[0116]
Here, as shown in FIG. 2, segment 1 has entries 1 to 6 and the registered entry is entry 4, so it is not the last entry in segment 1 (NO in step S 53). Therefore, “Segment 1 entry 5” is set in the next registration pointer of the work area (step S54).
[0117]
Further, since the takeout pointer is “entry 5 of segment 2”, it is different from the next registration pointer (NO in step S56).
[0118]
Therefore, the data registration unit 115 transfers the registration data to “entry 4 of segment 1” (step S57), sets “entry 5 of segment 1” to the registration pointer (step S58), and sets the number of data to “ “1” is added to “10” (step S59).
[0119]
Finally, the data registration unit 115 cancels the exclusion of the queue (step S60). This completes registration of new data.
[0120]
Next, the operation for extracting data will be described.
[0121]
As shown in FIG. 2 and FIG. 3, when the registration pointer points to “segment 1 entry 4”, the retrieval pointer points to “segment 2 entry 6”, and the number of registered data is “9” In addition, when data extraction is requested in the FIFO method, the data extraction means 116 first excludes the queue (step S71 in FIG. 9), and when the status flag is checked, the state is “in use” (in step S72). YES). Since the number of data is “9” (YES in step S73), data is transferred from the entry 6 of segment 2 to the data return area (step S74), and “1” is subtracted from the number of data to “8”. (Step S75).
[0122]
Here, as shown in FIG. 2, the segment 2 includes the entries 1 to 6 and the take-out entry is the entry 6, and is the last entry in the segment 2 (YES in step S76). Therefore, “Segment 3 entry 1” is set in the extraction pointer of the queue control information section (step S78).
[0123]
Finally, the data extraction unit 116 releases the exclusion of the queue (step S79). Thus, data could be extracted by the FIFO method.
[0124]
Similarly, as shown in FIGS. 2 and 3, the registration pointer points to “entry 4 of segment 1”, the take-out pointer points to “entry 6 of segment 2”, and the number of registered data is “9”. If the data retrieval is requested by the LIFO method, the data reverse retrieval unit 117 first excludes the queue (step S91 in FIG. 10), and checks the status flag, the status is “in use”. (YES in step S92). The number of data is “9” (YES in step S93). Here, as shown in FIG. 2, segment 1 has entries 1 to 6 and the registered entry is entry 4, so there is no head entry in segment 1 (NO in step S 94).
[0125]
Therefore, the data reverse extraction unit 117 sets “entry 3 of segment 1” (the last registered entry), which is the entry immediately before the registered entry, as a registration pointer (step S95). Data is transferred from the entry 3 ”to the data return area (step S98), and“ 1 ”is subtracted from the number of data to obtain“ 8 ”(step S99).
[0126]
Finally, the data reverse extraction unit 117 releases the queue exclusion (step S100). Thus, data could be extracted by the LIFO method.
[0127]
Next, a second embodiment of the present invention will be described in detail with reference to the drawings. FIG. 11 is a diagram showing the configuration of the second exemplary embodiment of the present invention. In this embodiment, a queue expansion means 219 and a queue degeneration means 220 are added to the configuration of the embodiment shown in FIG.
[0128]
Referring to FIG. 11, the second embodiment of the present invention comprises a computer system 200 that operates under program control, a queue control system 210, a queue segment 230, and a user program 240. Yes.
[0129]
The queue control system 210 includes a queue generation unit 211, a queue stop unit 212, a queue deletion unit 213, a queue reinitialization unit 214, a data registration unit 215, a data extraction unit 216, and a data reverse extraction unit 217. , A queue exclusion means 218, a queue expansion means 219, and a queue degeneration means 220.
[0130]
The queue segment 230 includes a queue control information unit 231 and a queue data unit 232.
[0131]
Each of these means generally operates as follows. Here, an operation different from that of the first embodiment will be described.
[0132]
The queue re-initialization unit 214 re-initializes the queue control information part of the queue that has been stopped by the queue stop unit 212, and erases the segment so that the number of queue segments becomes the initial segment number, and creates a circular link. Reset it. Thereafter, the queue re-initialization unit 214 sets the queue to a busy state so that the queue can be used again.
[0133]
In response to a request from the user program 240, the data registration unit 215 registers the data passed from the user program 240 in the entry indicated by the registration pointer in the queue control information unit 231. In addition, when there is a shortage of segments when registering data, the data registration unit 215 uses the queue expansion unit 219 to generate a new segment and expand the queue.
[0134]
In response to a request from the user program 240, the data retrieval unit 216 retrieves data from the entry indicated by the retrieval pointer in the queue control information unit 231 and returns it to the user program. Further, the data fetching unit 216 uses the queue degeneration unit 220 to erase a segment for which no data is registered.
[0135]
In response to a request from the user program 240, the data reverse extraction unit 217 extracts data from the entry immediately before the entry indicated by the registration pointer in the queue control information unit 131, and returns the data to the user program 240. In addition, the data reverse extraction unit 217 uses the queue degeneration unit 220 to delete a segment in which no data is registered.
[0136]
The queue expansion means 219 newly generates one segment and sets the generated segment as the “next segment” of the previous segment. The “next segment” of the generated segment was originally set as the previous segment. Add a queue segment and extend the queue by setting the segment.
[0137]
The queue degeneration means 220 deletes one segment, sets the segment set as the “next segment” of the deleted segment as the “next segment” of the previous segment, reduces the queue segments, and degenerates the queue. Let
[0138]
Queue generation unit 211, queue stop unit 212, queue deletion unit 213, queue reinitialization unit 214, data registration unit 215, data extraction unit 216, data reverse extraction unit 217, queue exclusion unit 218, queue expansion in queue control system 210 The means 219 and the queue degeneration means 220 have their functions and processes realized by a program executed on the computer.
[0139]
Next, the overall operation of the present embodiment will be described in detail with reference to the flowcharts of FIGS. 11 and 14 to 19. Here, means different in operation from those of the first embodiment will be described.
[0140]
FIG. 14 is a flowchart for explaining an example of the operation of the queue reinitialization means 214 in the second embodiment of the present invention. When the queue reinitialization unit 214 reinitializes the queue, the number of used segments in the queue control information section 231 is compared with the number of initial segments, and the number of used segments> the number of initial segments is satisfied (step in FIG. 14). YES in S113) means that the queue has been expanded, and processing for returning to the initial state is executed.
[0141]
First, the queue reinitialization unit 214 deletes the expanded segment number, that is, the (number of used segments−initial segment number) segment from the second segment onward (step S114).
[0142]
Next, the queue reinitialization means 214 resets the circular link between the remaining segments (step S115). Thus, the queue segment state becomes the initial state.
[0143]
When the number of used segments ≦ the number of initial segments (NO in step S113), since the queue is not expanded, the process of returning to the initial state (steps S114 and S115) is unnecessary.
[0144]
FIG. 15 is a flowchart for explaining an example of the operation of the data registration unit 215 according to the second embodiment of the present invention.
[0145]
When the user program 240 registers data in the queue, the data registration means 215 determines that the entry pointed to by the registration pointer in the queue control information section 231 (referred to as “registered entry”) is the last entry in the segment (FIG. 15). In step S123), the next segment of the segment pointed to by the registration pointer (hereinafter referred to as registration segment) is the segment pointed to by the takeout pointer (YES in step S125). If it does not exceed, that is, “number of used segments + 1 ≦ maximum number of segments” (YES in step S126), the queue is expanded by specifying the registered segment in the queue expansion means 219 (step S127).
[0146]
The queue expansion means 219 generates one new segment (step S181 in FIG. 18), and resets the circular link so that the specified segment, here, the segment next to the registered segment becomes the generated segment (step S181). S182), 1 is added to the number of used segments (step S183).
[0147]
Thus, in the data registration unit 215, a new queue segment is added as the next segment of the registered segment.
[0148]
Subsequently, the next segment, that is, the top entry of the added segment is set in the “next registration pointer” (step S128), and the subsequent processing is performed.
[0149]
If there is no segment pointed out by the fetch pointer next to the registered segment (NO in step S125), this means that there is at least one segment in which no data is registered, and expansion at that time is necessary. There is no new segment.
[0150]
Also, “number of used segments + 1> maximum number of segments”
(NO in step S126), the maximum number of segments specified at the time of generation is exceeded, so no new segment is generated.
[0151]
FIG. 16 is a flowchart for explaining an example of the operation of the data fetching means 216 in the second embodiment of the present invention.
[0152]
When the user program 240 retrieves data from the queue by the FIFO method, the data retrieving means 216 determines that the entry pointed to by the retrieval pointer in the queue control information section 231 is the last entry in the segment (YES in step S146 in FIG. 16). ), The data fetch pointer is updated to point to the first entry of the next segment (step S148).
[0153]
Here, the segment pointed to by the registration pointer is not a segment from which data has been extracted (hereinafter referred to as “extraction segment”) (NO in step S149), and the extraction segment is not the first segment (NO in step S150). If the queue has been expanded in the past and the segment is deleted, the number of initial segments will not fall below.
"Number of segments used-1 = number of initial segments"
If YES (YES in step S151), the queue degeneration means 220 is designated as an extraction segment and the queue is degenerated (step S152).
[0154]
The queue degeneration means 220 deletes the designated segment, here the fetched segment (step S191 in FIG. 19), and resets the circular link so that the previous segment of the designated segment points to the next segment (step S192). Then, 1 is subtracted from the number of used segments (step S193).
[0155]
If the segment pointed to by the registration pointer is an extracted segment (YES in step S149), the segment is not deleted because other data exists in the extracted segment. When the take-out segment is the first segment (YES in step S150), the first segment is a segment used as a key in the user program 240, and is a segment in which control information is stored, so it is not deleted.
[0156]
In addition, “number of used segments−1 <number of initial segments”
If it is (NO in step S151), the number of segments in the initial state will be less, so the segment is not deleted.
[0157]
FIG. 17 is a flowchart for explaining an example of the operation of the data reverse extraction means 217 in the second embodiment of the present invention.
[0158]
When the user program 240 retrieves data from the queue by the LIFO method, the data reverse retrieval means 217 determines that the entry pointed to by the registration pointer in the queue control information unit 231 is the first entry in the segment (step S164 in FIG. 17). YES), the registration pointer is updated to point to the last entry of the previous segment (steps S166 and S167 in FIG. 17).
[0159]
Here, the segment pointed to by the registration pointer before the update (hereinafter referred to as the original segment) is not the segment pointed to by the extraction pointer (NO in step S168), and the original segment is not the first segment (in step S169). No), queue expansion has happened in the past,
"Number of segments used-1 = number of initial segments"
If this is the case (YES in step S170), the queue is degenerated by designating the original segment in the queue degeneration means 220 (step S171). The original segment is deleted by the queue degeneration means 220.
[0160]
If the segment pointed to by the registration pointer before update (referred to as “original segment”) is the segment pointed to by the extraction pointer (YES in step S168), there is another data in the original segment. , Do not delete the segment.
[0161]
If the original segment is the first segment (YES in step S169), the first segment is not deleted.
[0162]
In addition, “number of used segments−1 <number of initial segments”
If this is the case (NO in step S170), the number of segments in the initial state is less than the number of segments, so the segments are not deleted.
[0163]
Next, the effect of this Embodiment is demonstrated.
[0164]
In the embodiment of the present invention, a segment is added when data entry is likely to be insufficient at the time of data registration, and a segment is deleted when a segment without data is detected at the time of data retrieval. When the number of data temporarily increases, the queue is automatically expanded. When the number of data decreases, the queue can be degenerated, and memory resources can be used efficiently.
[0165]
Further, in the present embodiment, when data is registered, a segment is added when the registration pointer and the extraction pointer point to the same segment, that is, when there is a possibility that the registration pointer catches up with the extraction pointer and there is a possibility of insufficient entries. Because of the configuration, the queue can be expanded in advance before the entry becomes insufficient.
[0166]
Next, the operation of this embodiment will be described using specific examples.
[0167]
As shown in FIGS. 2 and 3, the registration pointer points to “segment 1 entry 4”, the takeout pointer points to “segment 2 entry 6”, and the number of registered data is “9”. Assume that the number of used segments is 3, the number of initial segments is 3, and the maximum number of segments is 10. When two pieces of data are registered by the user program, the registration pointer points to “entry 6 of segment 1” and the number of data is 11. In this state, if further data registration is requested, the registration entry is entry 6 and is the last entry of segment 1 (YES in step S123 in FIG. 15), and the segment pointed to by the fetch pointer is “segment 2”. This is the next segment of “Segment 1” (YES in step S125).
[0168]
Also,
Number of segments used + 1 = 4 ≦ 10
(YES in step S126), the data registration unit 215 adds the segment 4 as the next segment of the segment 1 by the queue expansion unit 219 (step S127).
[0169]
In this way, the queue is expanded to the state shown in FIGS.
[0170]
Next, as shown in FIGS. 12 and 13, the registration pointer points to “entry 1 of segment 4”, the take-out pointer points to “entry 6 of segment 2”, and the number of registered data is “ It is assumed that 13 ″, the number of used segments is 4, the number of initial segments = 3, and the maximum number of segments = 10.
[0171]
In this state, when requesting the data extraction by the FIFO method, the data extraction means 216 is the entry 6 and is the last entry of the segment 2 (step S146 in FIG. 16). “Segment 3 entry 1” is set (step S148).
[0172]
Here, the segment pointed to by the registration pointer is “segment 4”, not “segment 2” (NO in step S149), and “segment 2” is not the first segment (NO in step S150).
[0173]
Also,
Number of segments used-1 = 3 ≥ 3
Therefore (YES in step S151), the data extraction unit 216 deletes the segment 2 by the queue degeneration unit 220 (step S152).
[0174]
In this way, the queue is degenerated and the state shown in FIG. 12 and FIG.
[0175]
Similarly, as shown in FIG. 12 and FIG. 13, the queue indicates that the registration pointer points to “entry 1 of segment 4”, the take-out pointer points to “entry 6 of segment 2”, and the number of registered data is It is assumed that “13”, the number of used segments is “4”, the initial number of segments is “3”, and the maximum number of segments is “10”.
[0176]
In this state, when requesting data extraction by the LIFO method, the data reverse extraction means 217 determines that the entry pointed to by the registration pointer is the first entry of the segment 4 (YES in step S164 in FIG. 17). An entry 6 of segment 1 is set (steps S166 and S167).
[0177]
Here, the takeout pointer points to segment 2 instead of segment 4 (NO in step S168), segment 4 is not the first segment (NO in step S169),
Number of segments used-1 = 3 ≥ 3
Therefore (YES in step S170), the data reverse extraction unit 217 deletes the segment 4 by the queue degeneration unit 220 (step S171). Thus, the segment 4 of the queue is degenerated, and the state shown in FIGS. 2 and 3 is obtained.
[0178]
Next, a third embodiment of the present invention will be described in detail with reference to the drawings.
[0179]
Referring to FIG. 20, the third embodiment of the present invention includes a computer system 300 that operates under program control, a queue control system 310, a queue segment 330, a user program 340, and a user program 341. It is configured.
[0180]
The queue control system 310 includes a queue generation unit 311, a queue stop unit 312, a queue deletion unit 313, a queue reinitialization unit 314, a data registration unit 315, a data extraction unit 316, and a data reverse extraction unit 317. Queue exclusion means 318, queue expansion means 319, queue degeneration means 320, and waiting means 321.
[0181]
The queue segment 330 includes a queue control information unit 331 and a queue data unit 332.
[0182]
Each of these means generally operates as follows. Here, means different in operation from the first and second embodiments will be described.
[0183]
The queue stopping unit 312 uses the waiting unit 321 to start a process waiting for data or an entry, and prohibits subsequent registration and retrieval of data by setting the queue to a stopped state.
[0184]
The data registration unit 315 registers the data passed from the user program in the entry indicated by the registration pointer in the queue control information unit 331 in response to a request from the user program (340/341).
[0185]
At this time, if there is a process waiting for data registration, the waiting process is started using the waiting means 321. That is, when the number of waiting for data registration is 1 or more, the notification semaphore is notified and the waiting is released. If there is no empty entry at the time of data registration, the waiting means 321 is used to wait for an empty entry.
[0186]
In response to a request from the user program, the data retrieval unit 316 retrieves data from the entry indicated by the retrieval pointer in the queue control information unit 231 and returns it to the user program. At this time, if there is a process waiting for an empty entry, the waiting process is started using the waiting canceling means 323. That is, when the number of waits for empty entries is 1 or more, a notification is sent to the notification semaphore and the wait is released. If there is no data registered at the time of data retrieval, the waiting unit 321 is used to wait for data registration.
[0187]
In response to a request from the user program, the data reverse fetch unit 217 fetches data from the entry immediately before the entry indicated by the registration pointer of the queue control information unit 331 and returns it to the user program. At this time, if there is a process waiting for an empty entry, the waiting process is started using the waiting means 321. That is, when the number of waiting is 1 or more, the notification semaphore is notified and the waiting is released. If there is no data registered at the time of data retrieval, the waiting unit 321 is used to wait for data registration.
[0188]
The waiting unit 321 adds 1 to the number of waiting, and after canceling the exclusion of the queue using the queue exclusion unit 318, waits for the cancellation notification using the notification semaphore. When the notification is received, the waiting unit 321 uses the queue exclusion unit 318 to exclude the queue and subtracts 1 from the number of waiting.
[0189]
Queue generation unit 311, queue stop unit 312, queue deletion unit 313, queue reinitialization unit 314, data registration unit 315, data extraction unit 316, data reverse extraction unit 317, queue exclusion unit 318, queue expansion in queue control system 310 The function 319, the queue degeneration unit 320, and the waiting unit 321 have their functions and processes realized by a program executed on the computer.
[0190]
Next, the overall operation of the present embodiment will be described in detail with reference to the flowcharts of FIGS. 20 and 23 to 27. In the following, this embodiment will be described with respect to differences from the operations of the first and second embodiments.
[0191]
FIG. 23 is a flowchart for explaining an example of the operation of the queue stopping unit 312 in the third embodiment of the present invention. When the queue stop unit 312 stops using the queue, the queue stop unit 312 determines the number of waiting in the queue control information unit 331 of the first segment after checking the status flag.
[0192]
If the number of waiting in the queue control information section 331 of the first segment is larger than 0 (YES in step S213 in FIG. 23), it means that there is a process waiting for notification, so the number of notification semaphores corresponding to that number Notification is made (step S214), and then the status flag is set to “stop” (step S215).
[0193]
All processes waiting in this way are activated and continue their respective processes. However, in the subsequent status check, since they are not “in use”, all processes fail and the queue is not used. If the number of waiting is 0 (NO in step S213), there is no need to notify because there is no waiting process.
[0194]
FIG. 24 is a flowchart for explaining an example of the operation of the data registration unit 315 according to the third embodiment of the present invention.
[0195]
When the user program 340 registers data in the queue, the data registration unit 315 determines that the entry pointed to by the set next registration pointer is the same as the entry pointed to by the extraction pointer in the queue control information section 331 (FIG. 24). In step S229, YES), the registration pointer catches up with the take-out pointer, and there is no entry that can be registered next.
[0196]
In this case, the data registration unit 315 uses the waiting unit 321 to wait for another process to extract data and make a free entry (step S236).
[0197]
FIG. 27 is a flowchart for explaining an example of the operation of the waiting means in the third embodiment of the present invention. The queuing means 321 adds 1 to the queuing number in the queue control information part 331 of the first segment (step S281 in FIG. 27), and cancels the exclusion of the queue using the queue exclusion means (step S282). Waiting is performed with the notification semaphore of the control information unit 331 (step 283).
[0198]
The waiting is canceled by a notification from the data registration unit 315, the data extraction unit 316, the data reverse extraction unit 317, or the data stop unit 312.
[0199]
Thereafter, the waiting means 321 excludes the queue by the queue exclusion means (step S284), subtracts 1 from the number of waiting (step S285), and ends.
[0200]
When the data registration unit 315 cancels the waiting, that is, when an empty entry is made, the data registration unit 315 re-executes the processing from the status flag check (step S222 in FIG. 24).
[0201]
If the data can be registered (executed up to step S232) and the number of waiting is greater than 0 (YES in step S233), this means that there is a process waiting for data registration.
[0202]
Therefore, the data registration unit 315 notifies the notification semaphore (step S234), and starts the waiting process. When the number of waiting is 0 (NO in step S233), there is no need to notify because there is no waiting process.
[0203]
FIG. 26 is a flowchart for explaining an example of the operation of the data fetching means 316 in the third embodiment of the present invention.
[0204]
When the user program 340 retrieves data from the queue by the FIFO method, the data retrieving means 316 registers if the number of data in the queue control information section 331 of the first segment is 0 (NO in step S243 in FIG. 25). Since there is no data being processed, the waiting unit 321 is used to wait for data registration by another process (step S256).
[0205]
When waiting is canceled, that is, when data is registered, the data fetching unit 316 re-executes the processing from the status flag check (step S242). Further, when the data is extracted and the pointer update is completed (up to step S247), if the wait number of the queue control information section 331 of the first segment is larger than 0 (YES in step S253), the entry is empty. This means that there is a process waiting.
[0206]
Therefore, the data extraction unit 316 notifies the notification semaphore of the queue control information unit 331 of the first segment (step S254), and starts the waiting process. On the other hand, when the number of waits in the queue control information section 331 of the first segment is 0 (NO in step S253), there is no process waiting, so there is no need to notify.
[0207]
FIG. 26 is a flow chart for explaining an example of the operation of the data reverse extraction means in the third embodiment of the present invention.
[0208]
In the case where the user program 340 retrieves data from the queue by the LIFO method, the data reverse retrieval means 317 is registered if the number of data in the queue control information unit 331 is 0 (NO in step S263 in FIG. 26). Since no data is present, the waiting unit 321 is used to wait for data registration by another process (step S277). When the waiting is released, that is, when the data is registered, the data reverse extraction means 317 re-executes the processing from the status flag check (step S262). In addition, when the data extraction is completed (up to step S275), if the number of waiting in the queue control information section 331 of the first segment is greater than 0 (YES in step S274), there is a process waiting for an empty entry. It means to do.
[0209]
Therefore, the data reverse extraction means 317 notifies the notification semaphore of the queue control information section 331 of the first segment (step S275), and starts the waiting process. When the number of waiting is 0 (NO in step S274), there is no need to notify because there is no waiting process.
[0210]
Next, the effect of this embodiment will be described.
[0211]
In this embodiment, when there is no empty entry at the time of data registration, it is configured to wait for another process to take out data and automatically wait for the entry to be empty, so it is necessary to be aware of queue overflow. You can use the queue without.
[0212]
Further, in the present embodiment, it is configured to automatically wait for registration of data by another process when there is no data at the time of data retrieval, so the number of registered data is conscious. You can use the queue without having to.
[0213]
[Example 2]
Next, the operation of this embodiment will be described using specific examples.
[0214]
For example, as shown in FIG. 21 and FIG. 22, the queue indicates that the registration pointer points to “entry 4 of segment 1”, the retrieval pointer points to “entry 5 of segment 1”, and the number of registered data is “17”. It is assumed that the number of used segments is 3, the number of initial segments is 3, and the maximum number of segments is 3. When the user program 340 registers data in this state, the data registration means 315 indicates that the registration pointer points to “entry 4 of segment 1” and is not the last entry (NO in step S223 in FIG. 25). “Segment 1 entry 5” is set in the registration pointer (step S224).
[0215]
Then, since the next registration pointer = the extraction pointer (YES in step S229), the waiting unit 236 waits for an empty entry (step S236). The waiting unit 321 sets the waiting number of the queue control information unit 331 of the first segment to 1 (step S281 in FIG. 27), cancels the exclusion of the queue (step S282), and waits for notification (step S283).
[0216]
Here, when the user program 341 retrieves data by the FIFO method, the data retrieving unit 316 retrieves data from “entry 5 of segment 1” (steps S244 and S245 in FIG. 25). Since entry 5 is not the last entry (NO in step S246), “segment 6 entry 6” is set in the extraction pointer (step S247).
[0217]
Subsequently, the data fetching unit 316 notifies the notification semaphore of the queue control information section 331 of the first segment because the queue number of the queue control information section 331 of the first segment is 1 (YES in Step S253) ( Step S254).
[0218]
The waiting unit 321 receives the notification from the data extracting unit 316 in the user program 341 and continues the processing. The waiting unit 321 excludes the queue (step S284 in FIG. 27), and subtracts 1 from the number of waiting in the queue control information unit 331 of the first segment (step S285).
[0219]
Subsequently, when the data registration unit 315 re-executes the processing from the status check (step S222 in FIG. 24), “entry 5 of segment 1” is set as the next registration pointer (step S224), and the next registration pointer ≠ take out. Since it is a pointer (NO in step S229), data registration is completed (steps S230, S231, and S232).
[0220]
Subsequently, since the number of waiting in the queue control information section 331 of the first segment is 0 (NO in step S233), the data registration unit 315 cancels the exclusion of the queue without performing notification (step S235), finish.
[0221]
The queue control system of each embodiment described above is suitable for segment management of a computer that employs a virtual storage system and manages virtual storage space by segmentation.
[0222]
In addition, the burden on the user can be reduced in realizing interprocess communication. That is, in the above-described embodiment, by performing data registration in the queue and waiting for empty entries within the queue control system, data empty and overflow do not occur in the queue operation, and on the user program side, There is no need to build a complicated program that takes error handling into consideration. In addition to this, an arbitrary queue having a data entry for holding information data and a queue control information section such as dynamic buffer management for obtaining a buffer from the buffer pool when necessary and returning the buffer after use. Of course, it can be applied to a management system. Although the present invention has been described with reference to the above-described embodiment, the present invention is not limited to the above-described embodiment, and can be made by those skilled in the art within the scope of the invention of each claim. Of course, various modifications and corrections will be included.
[0223]
【The invention's effect】
As described above, the present invention has the following effects.
[0224]
The first effect of the present invention is that data can be registered and retrieved from a queue at high speed.
[0225]
The reason is that in the present invention, the entry to be processed is determined in advance by the registration pointer or the retrieval pointer, and it is not necessary to search the queue or change the chain between entries when registering and retrieving data. Because.
[0226]
The second effect of the present invention is that memory resources can be used efficiently.
[0227]
The reason for this is that in the present invention, a queue that has been used can be deleted or reused, and when the number of registered data temporarily increases, the queue is automatically set. This is because when the number of registered data decreases, the queue is degenerated.
[0228]
The third effect of the present invention is that the burden on the user can be reduced in realizing inter-process communication.
[0229]
The reason for this is that in the present invention, registration of data to the queue and waiting for empty entries are performed inside the queue control system, so that there is no data empty or overflow in the queue operation, and the user program side. This is because there is no need to be aware of abnormalities, that is, there is no need to build a program that takes into account error processing, for example.
[Brief description of the drawings]
FIG. 1 is a diagram showing a configuration of a first exemplary embodiment of the present invention.
FIG. 2 is a diagram schematically showing a queue segment in the first embodiment of the invention.
FIG. 3 is a diagram illustrating an example of a queue control information unit according to the first embodiment of this invention.
FIG. 4 is a flowchart for explaining an example of the operation of the queue generation unit according to the first embodiment of the present invention.
FIG. 5 is a flowchart for explaining an example of the operation of the queue stopping means in the first embodiment of the invention.
FIG. 6 is a flowchart for explaining an example of the operation of the queue erasing unit in the first embodiment of the invention.
FIG. 7 is a flowchart for explaining an example of the operation of the queue reinitialization means in the first embodiment of the invention;
FIG. 8 is a flowchart for explaining an example of operation of data registration means in the first exemplary embodiment of the present invention.
FIG. 9 is a flowchart for explaining an example of the operation of the data fetching unit in the first embodiment of the present invention.
FIG. 10 is a flowchart for explaining an example of the operation of the data reverse extraction means in the first embodiment of the invention.
FIG. 11 is a diagram showing a configuration of a second exemplary embodiment of the present invention.
FIG. 12 is a diagram schematically illustrating a queue segment according to the second embodiment of the present invention.
FIG. 13 is a diagram illustrating an example of a queue control information unit according to the second embodiment of the present invention.
FIG. 14 is a flowchart for explaining an example of the operation of the queue reinitialization means in the second embodiment of the present invention;
FIG. 15 is a flowchart for explaining an example of operation of data registration means in the second exemplary embodiment of the present invention.
FIG. 16 is a flowchart for explaining an example of the operation of the data fetching unit in the second embodiment of the present invention;
FIG. 17 is a flowchart for explaining an example of the operation of the data reverse extraction means in the second embodiment of the present invention;
FIG. 18 is a flowchart for explaining an example of the operation of the queue extension means in the second exemplary embodiment of the present invention.
FIG. 19 is a flowchart for explaining an example of the operation of the queue degeneration means according to the second embodiment of the present invention.
FIG. 20 is a diagram showing a configuration of a third exemplary embodiment of the present invention.
FIG. 21 is a diagram schematically illustrating a queue segment according to the third embodiment of the present invention.
FIG. 22 is a diagram illustrating an example of a queue control information unit according to the third embodiment of the present invention.
FIG. 23 is a flowchart for explaining an example of the operation of the queue stopping means in the third embodiment of the present invention;
FIG. 24 is a flowchart for explaining an example of the operation of the data registration means in the third embodiment of the invention.
FIG. 25 is a flowchart for explaining an example of the operation of the data fetching unit in the third embodiment of the present invention;
FIG. 26 is a flowchart for explaining an example of the operation of the data reverse extraction means in the third embodiment of the present invention;
FIG. 27 is a flowchart for explaining an example of the operation of the waiting means in the third embodiment of the present invention;
[Explanation of symbols]
100, 200, 300 Computer system
110, 210, 310 Queue control system
111, 211, 311 Queue generation means
112, 212, 312 Queue stop means
113, 213, 313 Queue erasing means
114, 214, 314 Queue re-initialization means
115, 215, 315 Data registration means
116, 216, 316 Data retrieval means
117, 217, 317 Data reverse extraction means
118, 218, 318 Queue exclusion means
219,319 Queue expansion means
220, 320 Queue degeneration means
321 Meeting means
130, 230, 330 Queue segment
131, 231 and 331 Queue control information section
132, 232, 332 Queue data part
140, 240, 340 User program

Claims (57)

A segment to be used as a queue, and a plurality of segments having a queue control information part for storing queue control information in the segment and a data part including entries in which data is registered are generated. A queue generating means for setting an initial value in a queue control information section of one segment (referred to as a “first segment”) of a plurality of segments linked in a ring,
The queue control information portion of the first segment holds at least a registration pointer and a retrieval pointer that point to a data registration destination entry and a retrieval entry,
Data registration means for registering data in the entry pointed to by the registration pointer of the queue control information section of the first segment;
Data fetching means for fetching data from the entry pointed to by the fetch pointer of the queue control information section of the first segment;
A queue exclusion means for performing exclusive control of the queue;
A queue control system comprising: 2. The queue control system according to claim 1, further comprising a data reverse extracting means for extracting data from an entry immediately before the entry indicated by the registration pointer of the queue control information section of the first segment. A queue stop means for stopping the use of the queue and suppressing data registration and data retrieval after the stop of the use of the queue;
A queue clearing means for clearing a segment used as a queue,
The queue control system according to claim 1, further comprising: The queue re-initialization means for re-initializing the queue control information part of the queue whose use has been stopped by the queue stop means so that the queue can be used again. Queue control system. 5. The apparatus according to claim 1, further comprising queue expansion means for generating a new segment to be used as a queue and resetting a circular link between segments when there is no empty entry at the time of data registration. The queue control system according to any one of the above. The queue control according to any one of claims 1 to 5, further comprising queue degeneration means for deleting a segment that is not used at the time of fetching data and resetting a circular link between segments. system. The queue control according to any one of claims 1 to 6, further comprising a waiting unit for waiting for data to be taken out by another process and making a free entry when there is no free entry at the time of data registration. system. 8. The queue control system according to claim 7 , wherein said waiting means includes means for waiting for data to be registered by another process when there is no data registered at the time of fetching data. A segment to be used as a queue, a plurality of segments having a queue control information section for storing queue control information in the segment and a data section including entries in which data is registered, and each segment is circular And setting an initial value in a queue control information part of one segment (referred to as “first segment”) of a plurality of segments linked in a ring shape,
The queue control information portion of the first segment holds at least a registration pointer and a retrieval pointer that point to a data registration destination entry and a retrieval entry,
Registering data in an entry indicated by a registration pointer in the queue control information section of the first segment;
Extracting data from the entry indicated by the extraction pointer in the queue control information section of the first segment;
A step of controlling the queue exclusively;
A queue control method comprising: The queue control method according to claim 9, further comprising a step of fetching data from an entry immediately before an entry indicated by a registration pointer of the queue control information section of the first segment. Stopping the use of the queue and suppressing subsequent data registration and retrieval;
Deleting a segment that was used as a queue;
The queue control method according to claim 9 or 10, characterized by comprising: 12. The queue control method according to claim 9, further comprising a step of reinitializing the queue in the stopped state and enabling the queue again. 13. The queue control method according to claim 9, further comprising a step of generating a new segment to be used as a queue when there is no empty entry at the time of data registration. The queue control method according to claim 9, further comprising a step of deleting a segment that is not used at the time of fetching data. If there is no free entry when registering data, waiting for data to be taken out by another process and a free entry to be created;
A step of releasing the waiting by notifying the process waiting for a free entry when the data is fetched that the entry is free;
The queue control method according to claim 9, further comprising: Waiting for data to be registered by another process if no data is registered at the time of data retrieval;
Informing the process that is waiting for data registration at the time of data registration that the data has been registered and releasing the wait;
The queue control method according to claim 9, further comprising: A program that allows a computer to manage queues,
(A) A segment used as a queue, and a plurality of segments each including a queue control information section for storing queue control information in the segment and a data section including entries in which data is registered, A process of setting an initial value in a queue control information section of one segment (referred to as a “first segment”) of a plurality of segments linked in a ring, and setting a circular link to the segment, The queue control information part of the segment holds at least a registration pointer and a retrieval pointer that point to a data registration destination entry and a retrieval entry,
(B) processing for registering data in the entry pointed to by the registration pointer of the queue control information section of the first segment;
(C) processing for fetching data from the entry pointed to by the fetch pointer in the queue control information section of the first segment;
(D) processing for exclusive control of the queue;
Have
A program for causing the computer to execute the processes (a) to (d). 18. The program according to claim 17, further causing the computer to execute a process of extracting data from an entry immediately before an entry indicated by a registration pointer of the queue control information part of the first segment. The program according to claim 17 or 18, wherein the use of the queue is stopped, and the subsequent data registration and data retrieval are suppressed;
A program for causing the computer to further execute a process of deleting a segment used as a queue. The program according to any one of claims 17 to 19,
A program for causing the computer to further execute a process of reinitializing a queue control information part of a queue whose use has been stopped and allowing the queue to be used again. The program according to any one of claims 17 to 20,
A program for causing the computer to further execute a process of generating a new segment to be used as a queue and resetting a link between segments when there is no empty entry at the time of data registration. The program according to any one of claims 17 to 21,
A program for causing the computer to further execute a process of deleting unused segments and resetting links between segments when data is fetched. The program according to any one of claims 17 to 22,
If there is no free entry when registering data, the process of waiting for the data to be taken out by another process and creating a free entry,
A process of releasing the wait by notifying the process that is waiting for an empty entry when fetching data that the entry is empty;
For causing the computer to further execute. The program according to any one of claims 17 to 23,
When there is no data registered at the time of data retrieval, processing to wait for data to be registered by another process,
A program for causing the computer to further execute a process of notifying a process that waits for data registration when registering data that the data has been registered and releasing the wait. The queue generation means generates a ring-shaped link and initializes the queue control information part of the first segment, and then sets a status flag indicating the status of the queue during use,
Means for returning the address of the first segment to the user program;
With
The user program requests registration and retrieval of data from the data registration unit and the data retrieval unit, respectively, using the address as a key when registering and retrieving data. The queue control system according to any one of 1 to 8. As information set for the first segment in the queue control information section, a registration pointer indicating an entry of a segment for registering data, an extraction pointer indicating an entry of a segment from which data is extracted, and the data registered in the queue And at least link information consisting of the address of the next segment,
The queue control system according to any one of claims 1 to 8, wherein the remaining segment has link information including an address of a next segment as information set in the queue control information section. The first segment has, as a queue control information part, a registration pointer indicating a segment entry for registering data, a fetch pointer indicating a segment entry for extracting data, the number of data registered in the queue, In addition to link information consisting of segment addresses, the number of currently used segments, the initial segment number that is the initial value of the segment, the maximum segment number that indicates the maximum value of the segment, and the exclusive control of the queue It includes columns for storing the exclusive semaphore used, the notification semaphore for inter-process notification, and the number of waiting for managing the number of waiting processes,
9. The queue control system according to claim 1, wherein only the link information including the address of the next segment is set in the queue control information section of the segment excluding the first segment. The queue stop means checks the status flag indicating the state of the queue, if the status flag is in use, and a means for setting the state flag in the stop state, it claim 3, wherein Queue control system. The queue erasure means checks a status flag indicating a queue status, and when the status flag is in a stopped state, erases a queue segment being used, and when the status flag is not in a stopped state, 4. The queue control system according to claim 3 , further comprising means for controlling not to perform the operation. The queue re-initialization means checks a status flag indicating a queue status, and when the status flag is in a stopped state, sets an initial value in the queue control information section of the first segment, and sets the initial value The area where the value is set is only the area where the value is updated by using the queue, the state flag is set to in use,
5. The queue control system according to claim 4 , further comprising means for controlling not to re-initialize the queue when the status flag is not in the stopped state. The data registration means, when a status flag indicating the status of the queue is in use, means for checking whether the entry pointed to by the registration pointer of the queue control information section of the first segment is the last entry in the segment;
If the result of the check is the last entry, the next registration pointer is the first entry of the next segment, and if it is not the last entry, the next registration pointer is the next entry of the entry pointed to by the registration pointer;
Means for determining whether or not the next registration pointer matches a take-out pointer of the queue control information section;
If the result of the determination is that there is no match, there is no empty entry, data registration is not performed, and if there is no match, means for controlling the transfer of registered data to the entry pointed to by the registration pointer;
Means for setting a registration pointer of the queue control information part of the first segment to an entry indicating a next pointer;
Means for adding 1 to the number of data in the queue control information section of the first segment;
The queue control system according to any one of claims 1 to 8, further comprising: The data fetching means, if a status flag indicating the status of the queue is in use, means for checking whether the number of data in the queue control information part of the first segment is a positive integer;
If the data number is a positive integer, means for obtaining data from the take-out pointer of the queue control information part of the first segment, and subtracting the data number by one;
Means for setting the fetch pointer to point to the first entry of the next segment if the entry from which the data was fetched is the last entry in the segment;
Means for setting the fetch pointer to point to the next entry if the entry that fetched the data is not the last entry in the segment;
The queue control system according to any one of claims 1 to 8, further comprising: The data reverse fetching means, when a status flag indicating a queue status is in use, means for checking the number of data in the queue control information part of the first segment;
When the number of data is a positive integer, if the entry pointed to by the registration pointer in the queue control information section of the first segment (referred to as “registration entry”) is not the first entry in the segment, the entry immediately before the registration entry is Means for updating the registration pointer to point;
If the registration entry is the first entry in the segment, a means for obtaining a previous segment of the segment pointed to by the registration pointer and updating the registration pointer to point to the last entry of the segment;
Means for transferring data from the entry indicated by the updated registration pointer to a data return area transmitted from the user program;
Means for subtracting 1 from the number of data in the queue control information section of the first segment;
The queue control system according to claim 2 , further comprising: When the entry (referred to as “registered entry”) pointed to by the registration pointer in the queue control information part of the first segment is the last entry in the segment, the data registration means If the next segment is the segment pointed to by the fetch pointer and the number of used segments increases by one or less, the registered segment is designated in the queue extension means. Means to control the queue to expand,
The queue extension means includes means for generating one new segment, resetting the circular link so that the next segment of the registered segment is the generated segment, and adding 1 to the number of used segments.
A new queue segment is added as the next segment of the segment,
6. The queue control system according to claim 5 , wherein the data registering means sets the first entry of the segment added to the next registration pointer and enters the registration data into the registration entry. The data fetching means updates the data fetch pointer to point to the first entry of the next segment when the entry pointed to by the fetch pointer of the queue control information part of the first segment is the last entry in the segment, When the segment pointed to by the registration pointer is not a segment from which data has been extracted (referred to as “extracted segment”), the extracted segment is not the one segment, but is a value obtained by subtracting one from the number of segments used in the queue control information section of the first segment When the number of segments is equal to or greater than the initial number of segments, the queue degeneration means includes means for controlling the degeneration of the queue by designating the take-out segment,
The queue degeneration means comprises means for erasing a fetch segment that is a designated segment and resetting the circular link so that the previous segment of the designated segment points to the next segment. The queue control system according to claim 6 . When the entry pointed to by the registration pointer of the queue control information part of the first segment is the first entry in the segment, the data reverse fetching means updates the registration pointer to point to the last entry of the previous segment, If the segment pointed to by the registration pointer before the update (referred to as “original segment”) is not the segment pointed to by the fetch pointer, the original segment is not the first segment, and queue expansion has occurred in the past. When the value obtained by subtracting one used segment number of the queue control information part is equal to or greater than the initial segment number, the queue degeneration means includes means for controlling the queue to degenerate by designating an original segment. The queue control system according to claim 6 . When the entry pointed to by the set next registration pointer is the same as the entry pointed to by the takeout pointer of the queue control information section of the first segment, the data registration means uses the waiting means to allow other processes to Wait for the data to be retrieved and a free entry to be made,
When the waiting is canceled and a free entry is made, the data registration means re-executes the processing from the check of the status flag, and when the data can be registered, the queue control information section of the first segment waits. 8. If the number is larger than 0, the data registration means notifies the notification semaphore of the queue control information section of the first segment, and controls to start a waiting process. The queue control system described in. The waiting means adds 1 to the number of waiting in the queue control information section of the first segment, releases the exclusion of the queue using the queue exclusion means, and uses the notification semaphore in the queue control information section of the first segment. Make a meeting,
Waiting is canceled by notification from at least one of the data registration unit, the data extraction unit, the data reverse extraction unit, and the queue stop unit,
8. The queue control system according to claim 7, wherein the waiting means excludes the queue by the queue exclusion means and subtracts 1 from the waiting number in the queue control information section of the first segment. The data fetching means waits for registration of data by another process using the waiting means when the number of data in the queue control information part of the first segment is 0,
When the waiting is released and the data is registered, the data fetching unit re-executes the processing from the status flag check, fetches the data, and when the pointer update is completed, the queue control information part of the first segment If the number of waiting times is greater than 0, the data fetching means performs control to notify the notification semaphore of the queue control information section of the first segment and to start the waiting process. The queue control system according to claim 7. When the user program fetches data from the queue, the data reverse fetching means uses the waiting means when the number of data in the queue control information section of the first segment is 0, and is determined by another process. Wait for data registration,
When the waiting is released, that is, when the data is registered, the data reverse fetching means re-executes the processing from the status flag check, and when the data fetching is completed, the queue control information part of the first segment When the number of waiting is larger than 0, the data reverse fetching means performs control to notify the notification semaphore of the queue control information part of the first segment and to start the waiting process. The queue control system according to claim 7. An information processing apparatus comprising the queue control system according to any one of claims 1 to 8 and 25 to 40. In a system that uses a virtual storage method and manages computer segments that manage virtual storage space by segmentation in a queue,
A queue control system comprising the queue control system according to any one of claims 1 to 8 and 25 to 40. In generating the queue, after initial setting the queue control information portion of the first segment, set the status flag to in use, returning the address of the first segment to the user program;
The user program requests registration and retrieval of data using the address as a key;
The queue control method according to claim 9, further comprising: The first segment, as a queue control information section, includes a registration pointer indicating a segment entry for registering data, a fetch pointer indicating a segment entry for extracting data, the number of registered data, the number of segments, and the address of the next segment. Have link information,
The queue control method according to any one of claims 9 to 16, wherein the remaining segment has link information including an address of a next segment as a queue control information section. The first segment has, as a queue control information part, a registration pointer indicating a segment entry for registering data, a fetch pointer indicating a segment entry for extracting data, the number of data registered in the queue, In addition to link information consisting of segment addresses, the number of currently used segments, the initial segment number that is the initial value of the segment, the maximum segment number that indicates the maximum value of the segment, and the exclusive control of the queue It includes columns for storing the exclusive semaphore used, the notification semaphore for inter-process notification, and the number of waiting for managing the number of waiting processes,
The queue control method according to any one of claims 9 to 16, wherein only the link information including the address of the next segment is set in the queue control information section of the segment excluding the first segment. 17. The method according to claim 9, further comprising: checking a status flag indicating a status of the queue when the queue is stopped, and setting the status flag to a stopped status if the status is in use. The queue control method according to claim 1. 17. When deleting a queue, a state flag indicating the state of the queue is checked, and if the state is in a stopped state, a step of deleting all segments of the queue being used is included. The queue control method according to any one of the above. Checking if the status flag indicating the status of the queue is stopped when reinitializing the queue;
When the state is a stopped state, the method includes a step of setting an initial value in the queue control information part of the first segment,
The area where the initial value is set is only the area where the value is updated by using a queue,
Setting the state flag to a busy state;
The queue control method according to any one of claims 9 to 16, wherein In registering the data, checking whether a status flag indicating the status of the queue is in use;
If the status is in use, checking whether the entry pointed to by the registration pointer in the queue control information section of the first segment is the last entry in the segment;
In the case of the last entry, the step of setting the next registration pointer as the first entry of the next segment,
If it is not the last entry, the step of setting the next registration pointer as the next entry of the entry pointed to by the registration pointer;
Determining whether the next registration pointer matches the take-out pointer of the queue control information section of the first segment; if not, transferring registration data to the entry pointed to by the registration pointer;
Have
On the other hand, if the next registration pointer matches the take-out pointer of the queue control information part of the first segment, data registration is not performed as no empty entry,
Setting a registration pointer of the queue control information part of the first segment to an entry indicating a next pointer;
Adding 1 to the number of data in the queue control information section of the first segment;
The queue control method according to claim 9, further comprising: In retrieving the data, checking whether a status flag indicating the status of the queue is in use;
If the state is in use, checking whether the number of data in the queue control information part of the first segment is a positive integer;
When the number of data is a positive integer, obtaining data from a takeout pointer of the queue control information portion of the first segment;
Subtracting 1 from the number of data in the queue control information section of the first segment, and setting the fetch pointer to point to the first entry of the next segment if the entry from which the data was fetched is the last entry in the segment When,
If not the last entry in the segment, setting the fetch pointer to point to the next entry;
The queue control method according to claim 9, further comprising: Checking whether the status flag of the first segment is in use when retrieving data from the entry immediately before the entry pointed to by the registration pointer of the queue control information part of the first segment;
If the status is in use, checking the number of data in the queue control information part of the first segment;
When the number of data is a positive integer, if the entry pointed to by the registration pointer in the queue control information part of the first segment (referred to as “registered entry”) is not the first entry in the segment, it points to the entry immediately before the registered entry Updating the registration pointer so that
When the registration entry is the first entry in the segment, obtaining a segment immediately preceding the segment pointed to by the registration pointer, and updating the registration pointer to point to the last entry of the segment;
Transferring the data from the entry indicated by the updated registration pointer to the data return area transmitted from the user program;
Subtracting 1 from the number of data in the queue control information section of the first segment;
The queue control method according to claim 10 , further comprising: In the data registration step when the user program registers data in the queue,
When the entry (referred to as “registered entry”) pointed to by the registration pointer in the queue control information part of the first segment is the last entry in the segment, the next segment of the segment pointed to by the registration pointer (referred to as “registered segment”) If the fetch pointer in the queue control information section of the first segment is the segment pointed to, and the number of segments used is increased by one, the maximum number of segments that has been set in advance will not be exceeded. Expanding steps,
In the queue extension step, a new segment is generated, and the circular link is reset so that the next segment of the registered segment is the generated segment;
Adding 1 to the number of used segments in the queue control information section of the first segment, and adding a new queue segment as the next segment of the registered segment;
Setting the first entry of the segment added to the next registration pointer;
Have
If the next segment of the registered segment is not the segment pointed to by the fetch pointer, no new segment is generated, and the value obtained by adding 1 to the number of used segments in the queue control information section of the first segment is the maximum segment. The queue control method according to claim 9, further comprising a step of controlling not to generate a new segment when the number is larger than the number. In the data fetching step when the user program fetches data from the queue, if the entry pointed to by the fetch pointer in the queue control information part of the first segment is the last entry in the segment, the first entry of the next segment is pointed to Updating the data retrieval pointer;
At this time, if the segment pointed to by the registration pointer in the queue control information section of the first segment is not a segment from which data has been extracted (referred to as “extracted segment”), the extracted segment is not the one segment but the queue of the first segment. If the number of used segments in the control information section is subtracted by 1 and does not fall below the initial number of segments in the queue control information section of the first segment, the take-out segment is designated to degenerate the queue,
The queue degeneration step comprises erasing a fetch segment that is a designated segment and resetting the circular link so that the previous segment of the designated segment points to the next segment;
When the segment pointed to by the registration pointer is a fetch segment, when the fetch segment is the one segment, and the value obtained by subtracting 1 from the number of used segments is smaller than the initial segment number of the queue control information section of the first segment The queue control method according to claim 9, further comprising a step of controlling not to delete the segment. In the data reverse retrieval step when the user program retrieves data from the queue in the LIFO (Last In First Out) format,
When the entry pointed to by the registration pointer in the queue control information section of the first segment is the first entry in the segment, the registration pointer is updated to point to the last entry of the previous segment, and at this time, the registration pointer before the update points to When the segment that has been stored (referred to as “original segment”) is not the segment pointed to by the fetch pointer, the original segment is not the first segment, queue expansion has occurred in the past, and the queue control information portion of the first segment is used If the value obtained by subtracting 1 from the number of segments is equal to or greater than the initial number of segments, the step of degenerating the queue by designating the original segment in the queue degeneration step;
When the segment pointed to by the registration pointer before the update (referred to as “original segment”) is the segment pointed to by the extraction pointer, the segment used by the queue control information section of the first segment when the original segment is the first segment The queue according to any one of claims 10 to 16, further comprising a step of controlling not to delete a segment when a value obtained by subtracting 1 from the number is smaller than an initial segment number. Control method. When the user program registers data in the queue, in the data registration step, when the entry pointed to by the set next registration pointer is the same as the entry pointed to by the take-out pointer of the queue control information section of the first segment, Waiting for another process to retrieve data and make a free entry;
In the data registration step, when waiting is canceled and a free entry is made, the process is re-executed from the check of the status flag indicating the status of the queue;
When the data can be registered and the number of waiting in the queue control information part of the first segment is larger than 0, the data registration step notifies the notification semaphore of the queue control information part of the first segment, Starting a process that is waiting,
The queue control method according to claim 9, further comprising: In the waiting step, adding 1 to the number of waiting in the queue control information part of the first segment, releasing the exclusion of the queue, and waiting in the notification semaphore of the queue control information part of the first segment;
Waiting is canceled by notification from data registration, data retrieval, data reverse retrieval, or queue stop step,
55. The queue control method according to claim 54, further comprising: excluding the queue and subtracting 1 from the number of waiting in the queue control information section of the first segment. When the user program retrieves data from the queue,
In the data reverse extraction step, when the number of data in the queue control information part of the first segment is 0, waiting for data registration by another process;
When waiting is canceled and data is registered, in the data reverse fetching step, the process is re-executed from the status flag check;
When the data fetching is completed, if the number of waiting in the queue control information part of the first segment is greater than 0, the data reverse fetching step notifies the notification semaphore of the queue control information part of the first segment. And launching the waiting process,
The queue control method according to claim 10, further comprising:

Images