Abstract:
A computing device is provided having a central processing unit, random access memory, and read only memory interconnected by a bus. The central processing unit is configured to execute a plurality of programming instructions representing a plurality of software objects. The software objects comprise a read queue for storing unprocessed packets and a write queue for storing processed packets. The software objects include a reader thread for reading packets from the read queue and a lock free queue for receiving packets received via the reader thread. The software objects also include at least one processor thread for performing an operation on the packets in the lock free queue. The software objects include a writer thread for writing packets that have been processed by the at least one processor thread to the write queue.

Description:
FIELD 
       [0001]    The present specification relates generally to computer data processing and more particularly relates to a method and apparatus for data processing using queuing. 
       BACKGROUND 
       [0002]    There is an increasing need for real-time processing. (As used herein, the term “real-time” is also intended to refer to near real-time and substantially real-time.) This need is well illustrated in the telecommunications sector where real-time services are ubiquitous. The class example of a real-time service is traditional voice telephony services, however, as portable wireless communication devices become more powerful, demand is arising for streaming video, audio and other real-time services. 
         [0003]    In telecommunications, concurrent with the demand for real-time services is the demand for real-time billing, which is particularly important in the case of pre-paid services, although is also relevant to post-paid services. Invocation and performance of a real-time service must also take place concurrent with real-time management of a subscriber&#39;s balance. Accordingly, improvements are needed to current data queuing techniques to satisfy such demand, or at least improve satisfaction of such demand. 
       SUMMARY 
       [0004]    A computing device is provided having a central processing unit, random access memory, and read only memory interconnected by a bus. The central processing unit is configured to execute a plurality of programming instructions representing a plurality of software objects. The software objects comprise a read queue for storing unprocessed packets and a write queue for storing processed packets. The software objects include a reader thread for reading packets from the read queue and a lock free queue for receiving packets received via the reader thread. The software objects also include at least one processor thread for performing an operation on the packets in the lock free queue. The software objects include a writer thread for writing packets that have been processed by the at least one processor thread to the write queue. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0005]      FIG. 1  shows an apparatus for data processing using queuing. 
           [0006]      FIG. 2  shows a schematic representation of software executing on the apparatus of  FIG. 1 . 
           [0007]      FIG. 3  shows a flowchart depicting a method of enqueing packets. 
           [0008]      FIG. 4  shows a flowchart depicting a method of dequeing packets. 
           [0009]      FIG. 5  shows a flowchart depicting a method of processing packets. 
       
    
    
     DETAILED DESCRIPTION OF THE EMBODIMENTS 
       [0010]    Referring now to  FIG. 1 , an apparatus for data processing is indicated generally at  50 . In a present embodiment, apparatus  50  is a server, although in other embodiments apparatus  50  can be based on other types of computing environment. Apparatus  50  is typically a computing device such as a server having a keyboard and mouse (or other input devices), a monitor (or other output device) and a desktop-module connecting the keyboard, mouse and monitor and housing one or more central processing units, volatile memory (i.e., random access memory), persistent memory (i.e., hard disk devices) and network interfaces to allow the workstation  54  to communicate over network  60 . For example, apparatus  50  can be a Sun 480R server from Sun Microsystems, Inc. of Palo Alto Calif., with a plurality of CPUs and, because a significant portion of processing is performed in random access memory, such a server could be configured with about eight to about sixteen gigabytes of random access memory. However, it is to be emphasized that this particular server is merely exemplary, a vast array of other types of computing environments for apparatus  50  are within the scope of the invention. 
         [0011]    Apparatus  50  is situated between a data source  54  and a data destination  58 . Thus, apparatus  50  connects to data source  54  via a first link  62  and to data destination  58  via a second link  66 . Links  62  and  66  connect to apparatus  50  via one or more network interfaces within apparatus  50 . Links  62  and  66  are shown separately for convenience and can, in fact, be on the same physical and/or data link and/or network topology as desired. 
         [0012]    Data source  54  can be any source of data packets that are supplied to apparatus  50 , while data destination  58  can be any destination of data packets to which data packets from data source  54  are ultimately addressed or destined. Indeed, data source  54  can represent a plurality of data sources while data destination  58  can represent a plurality of data destinations. Data source  54  and data destination  58  themselves are typically based on computing hardware infrastructure, such as a server or a router or any other network component or the like. 
         [0013]    Apparatus  50  is configured to execute a software application  70  that can process packets originating from data source  54  en route to data destination  58 . As used in the previous sentence, the term “process” is not intended to be limiting, and can refer to any type of operation or algorithm or the like that may be performed on such packets. One specific but non-limiting example of processing is analysis of packets being carried through a telecommunication network. For example, packets from data source  54  can include packets that contain a request for services from a mobile handset (not shown) connected to data source  54 , where the services that are being requested by the mobile handset can be located at an application server (not shown) connected to data destination  58 . Apparatus  50  can be incorporated into the infrastructure of the telecommunication network and configured to determine whether the packet request is authorized and/or otherwise conforms to the agreement between the subscriber operating the mobile handset and the carrier operating the telecommunication network to which the mobile handset connects. In a present embodiment, as part of its function in processing packets, application  70  is thus configured to “drop” packets that originate from data source  54  which are not authorized and to “forward” packets that originate from data source  54  which are authorized on to data destination  58 . 
         [0014]      FIG. 2  shows a schematic representation of application  70 . Application  70 , as shown in  FIG. 2 , makes use of hardware within and/or other software executing on apparatus  50  in order to fulfill its function. Application  70  thus includes an input queue  74  and an output queue  78 . Input queue  74  is associated with data source  54  and thus data packets from data source  54  populate input queue  74  on a first-in-first-out (“FIFO”) (or other desired) basis. Likewise, output queue  78  is associated with data destination  58  and thus data packets that pass through application  70  and placed into output queue  78  with a “forward” flag are passed from output queue  78  to data destination  58 , but those data packets that pass through application  70  and are placed into output queue  78  with a “drop” flag never exit from output queue  78  to data destination  58 . Such packets with the “drop” flag may be stored for subsequent analysis, or used to generate an error message for the mobile handset that sent the dropped packet, or used for some other purpose, and/or those packets can be deleted altogether. 
         [0015]    The components of application  70  that lie between queue  74  and  78  perform the processing function of marking packets with either a “forward” flag or “drop” flag. Such components of application  70  include a reader thread  82  and a writer thread  84 . Reader thread  82  is configured to read data packets from queue  74  and enqueue those packets within an intermediate queue  86 . Writer thread  94  is configured to read packets from queue  86  that have been processed and write them to queue  78 . 
         [0016]    Application  70  also includes a thread controller  90  which is configured to access queue  86  and to coordinate the processing of packets within queue  86  with a plurality of processor threads  94 . 
         [0017]    Each processor thread is in turn configured to coordinate with a FIFO queue  98  which is a memory mapped Iockfree queue used by external application to do post processing of packets. In turn, FIFO queue  98  is accessible to another application  102  that can access FIFO queue  98  and perform operations on packets stored therein. Application  102  can be configured to do further processing but is not necessary. Threads  94  are configured to both dequeue from queue  96  and enqueue into queue  98 . In other embodiments, application  102  and queue  98  can be omitted altogether depending on the desired functionality of apparatus  50 . 
         [0018]    Explaining application  70  in greater detail, queue  86  is a pre-allocated memory buffer. Indices comprised of a plurality of variables is associated with queue  86 , referred to herein as TAIL, WRITHEAD and PROCHEAD are used to enqueue and dequeue data from queue  86 . TAIL is controlled by reader thread  84 . WRITHEAD is controlled by writer thread  86 . PROCHEAD is controlled by thread controller  90  in conjunction with a particular thread  94 . 
         [0019]    (Note that, hereafter, where the term “HEAD” is used herein, it is used to refer to either WRITHEAD or PROCHEAD as the context requires.) 
         [0020]    The size of queue  86  is selected to correspond with queues  74  and  78 . (For example, each element can be aligned with the same size. (i.e., whereby the closest 2̂n&gt;=maxsize(element size). The use of a fixed size that is aligned with 2̂n can improve overall efficiency and performance when the pointer for HEAD and TAIL is moved). As used herein, the term “element” refers to one block of memory with fixed size in a queue, whereas a packet is the content of an element. 
         [0021]    TAIL is the last index used to enqueue elements in queue  86 . WRITHEAD and PROCHEAD are the last index used to dequeue elements from a different processor thread  94 . It is presently preferred that only one of the threads  94  should be enqueuing at any given time, and only two of threads  94  should be dequeuing at the same time at any given time. 
         [0022]    Conceptually, TAIL, and HEAD are only able to move forward but never go back. However, since size of queue  86  is limited, when TAIL, and HEAD hit the limitation of queue  86 , they will be rolled over to zero. When comparing the value of tail and head, the value is adjusted according to the following: 
         [0023]    i) To check if queue  86  is full the following conditions are used: if (tail-head+1)==0; ==queue→maxsize; ==−queue→maxsize, then queue  86  is full. 
         [0024]    ii) To check if queue  86  is empty the following conditions are used: (tail-head)==0; ==queue→maxsize; ==queue→maxsize, then queue  86  is empty. 
         [0025]    Enqueueing into queue  86  by reader thread  82  is performed as follows: 
         [0026]    If WRITHEAD or PROCHEAD is greater or equal than TAIL, then queue  86  is full. A message indicating that queue  86  is FULL is returned immediately. 
         [0027]    If WRITHEAD or PROCHEAD is less than TAIL, the element will be enqueued by copying data from queue  74  to queue  86  and TAIL will be move forward. 
         [0028]    Enqueuing into queue  86  can be performed by reservation, whereby “reservation” refers to the fact that in order to read packets from  74 , a memory block needs to be provided to store packets, but it is not desirable to allocate a temporary memory block when a packet is read from queue  74 . Accordingly, memory is used directly from queue  86 , and before that memory is used, that memory is “reserved” so that it is declared that the reserved memory block will be reserved so that other threads should not use that “reserved” memory block at all. After packets are read, these reserved memory blocks are “committed” and the tail index is moved forward, and the “reservation” can be cancelled so that those memory blocks can be ready to be used by other threads. “Reservation” can be performed as follows: 
         [0029]    If WRITHEAD or PROCHEAD is greater or equal than TAIL, it means the queue is full. A message indicating that queue  86  is FULL is returned immediately. 
         [0030]    If WRITHEAD or PROCHEAD is less than TAIL, then the pointer of current TAIL index for queue  86  will be returned. There is no memory copying or memory allocation. 
         [0031]    When a block of queue  86  is filled with data, a method should be called to move TAIL forward. 
         [0032]    Dequeuing from queue  86  is performed as follows: 
         [0033]    Dequeue function using WRITHEAD or PROCHEAD is the same except each use a different HEAD pointer to dequeue data. 
         [0034]    1. If TAIL is equal to HEAD, it means queue is empty. In this circumstance the dequeue function return NULL immediately. 
         [0035]    2. If TAIL is greater than HEAD, it means queue is not empty. The element referenced by the HEAD index will be removed and HEAD will move forward by 1. 
         [0036]    Dequeing a batch of packets from queue  86  is performed as follows: 
         [0037]    1. If TAIL is equal to HEAD, it means queue is empty. In the circumstance the dequeue returns NULL immediately. 
         [0038]    2. If TAIL is greater than HEAD, it means queue is not empty. The rest of elements in queue which is calculated by the equation TAIL−HEAD, and the pointer of current HEAD index will be returned. The numbers of available elements will be also returned. The numbers of available elements depends on minimum value between TAIL−HEAD and batch size. 
         [0039]    3. After elements are dequeued and data are copied to other memory for processing, DequeueConfirm should be called to move head forward (HEAD=HEAD+AVAIL). 
         [0040]    Referring now to  FIG. 3 , a method for enqueing packets into a queue is depicted in the form of a flowchart and indicated generally at  300 . Method  300  can be performed by reader thread  82 . 
         [0041]    When performed by reader  82 , step  305  of method  300  first verifies whether application  70  is busy enqueueing elements into queue  86 . There is no delay if queue  86  is not full and queue  74  is not empty. When queue  74  is empty, reader  82  is configured to wait for a notification that queue  74  is not empty. When queue  86  is full, reader  82  is configured to advance to step  310  and yield current and keep trying to put packets from into queue  86 . In a present embodiment there is no thread wait (i.e., a notifying or context switch) happening when queue  86  is full, based on a configuration of application  70  whereby at least some other threads (e.g., thread controller  90  or writer  84 ) are running fast enough to continuously try and dequeue elements from queue  86 . (“Yield current” refers to a condition whereby the thread will keep retrying without waiting and/or locking. The only delay is the current thread yield to allow other threads get access to the central processing unit(s) (CPU) in order to continue processing. The delay is the time slice of thread switching.) 
         [0042]    Reader  82  is configured to check if queue  86  is full before reading packets from queue  70 . If queue  86  is full, reader  82  keeps yielding at step  310  to allow processor threads and write thread  84  to dequeue packets until queue is not full. 
         [0043]    Reader  82  is configured to reserve a space (step  315 ), read packets (step  320 ) and move queue head forward (step  325 ). (Note that such reserving at step  315  does not change value of TAIL itself, but a commit will move the TAIL forward.) Reader  82 , in a present embodiment is configured so as to not need to do any memory copying or allocation to make reader  82  as fast as possible. This is effected by the fact that an intermediate buffer is not used to read packets from queue  70 , so that there is no memory allocation or copying and the same memory will be reused by different threads. 
         [0044]    At step  335 , reader  82  is configured to notify those of threads  94  which are sleeping when a predefined condition, referred to herein as “Worker_waiting flag”, is set to true. It is presently preferred that only maximum one process thread  94  on waiting mode at any time. The processor thread  94  is, in a present embodiment, configured to only go into waiting mode only when it is currently the only active process threads  94 . Packets in process thread  94  are all processed and processor thread yielded for NoopTime times. (“NoopTime” refers to an empty loop, that does not do anything but yield the current thread. NoopTime still consumes CPU time to run empty loop. However, in order to prevent 100% CPU usage, a maximum Noop time is configured, thereafter After that, the thread will go to sleep mode. The benefit is that if there is incoming packets during Noop, it will be picked immediately for processing. 
         [0045]    Referring now to  FIG. 4 , a method for dequeuing packets from one queue another queue is depicted in the form of a flowchart and indicated generally at  400 . Method  400  can be performed by writer thread  84 . (Writer thread  84  can also be described as a verdict thread.) 
         [0046]    Writer thread  84  is configured to read packets from queue  86  and forward those packets to queue  78 . Such forwarding from queue  86  will occur typically after a given packet is processed by a processor thread  94 , but will also be forwarded in any event after a predefined time-out period in the event that a processor thread  94  does not process a particular packet  94  within that that predefined time-out period. In the time-out scenario, in a present embodiment writer thread  94  will be configured to make an assumption about how that particular packet  94  would have been processed. For example, in the “forward” or “drop” scenario of a telecommunication environment, thread  94  can be configured to assume that a particular packet  94  was processed to be a “forward” packet. 
         [0047]    In a present embodiment, writer thread  84  is configured to select a time-out period based on how many times thread  84  yields to determine when writer thread  84  should timeout. While use of an absolute time value for the time-out period is possible, it is presently preferred to avoid an absolute time value as the cost of even a loss of one nanosecond can be too great. 
         [0048]    Writer thread  84  is configured so that after an attempt to read a packet by writer thread  84  from queue  86  results in writer thread  84  ascertaining that the packet that has not been processed, then writer thread  84  will assume that the packet will be processed in a very short time by processor thread  94 . Thread  84  and  94  are configured to run concurrently and there is a plurality of threads  94  running concurrently. When thread  84  reads a packet and that has not been processed, then that packet It might be processed by thread  94  at the same time or it might be in queue  86  waiting for next the thread  94  to pick it up and process. Accordingly, it is assumed that the packet should be processed by thread  94  very soon. However, in the event that thread  94  is slow, and it takes long time to process packets in thread  94 , then thread  84  will “time out” and ignore processed flag of the packet and continue. 
         [0049]    In a present embodiment, application  70  is configured so that there is one writer thread  84  to correspond with the single reader thread  82 . Such configuration is made so as to ensure that the writer thread  84  will dequeue from queue  86  in the same order that reader thread  82  enqueues into queue  86 . 
         [0050]    Writer thread  84  is configured to goes into a wait/sleep mode if queue  86  is empty. Writer thread  94  will be notified when queue  86  become non-empty. 
         [0051]    Writer thread  86  is also, in a present embodiment, configured to dequeue packets from queue  86  in a batch mode. In batch modes, a plurality of packets are dequeued from queue  86  rather than dequeuing each packet from queue  86  one at a time. 
         [0052]    Step  405  of  FIG. 4  represents the commencement of the steps of dequeuing, either one at a time or in batch mode, although as noted the batch mode is optional. 
         [0053]    Step  410  of  FIG. 4  represents the determination by writer thread  84  as to whether or not there are actually any packets that are available to be dequeued from queue  86 . 
         [0054]    Step  415  represents the wait or sleep state that writer thread  84  will assume if there are no packets available as determined at step  405 . 
         [0055]    Step  420  represents the commencement of a loop whereby packets are actually dequeued from queue  86 . At step  425  a determination is made as to whether or not a particular packet in queue  86  has been processed. If no, then method  400  advances to step  430  where writer thread  84  yields. At step  435 , if a maximum yield is not achieved then the method returns back to step  425 . If at step  435  a maximum yield is achieved, then the yield times out and the method advances to step  440 . Step  440  can also be reached directly upon a yes determination that a given packet in queue  86  has been processed at step  425 . Note that if method  400  reaches step  440  via step  435 , then writer thread  84  will make an assumption as to how the packet would have been processed. (e.g., writer thread  84  may assume that packets which have not been processed are all “forward” packets and none are “drop” packets.) 
         [0056]    Thus, at step  440 , however step  440  is reached; packet(s) are dequeued from queue  86  and actually placed in to queue  78 , with a particular verdict (e.g., “forward” or “drop”) attached thereto. 
         [0057]    Step  445  represents a termination of the loop commenced at step  420 , whereby the loop at step  420  will recommence until there are no longer any available packets to dequeue from queue  86 . 
         [0058]    At step  450 , there is a Confirmation that packets are dequeued by moving WRITHEAD forward. 
         [0059]    Referring now to  FIG. 5 , a method for processing packets within a queue such as queue  86  is depicted in the form of a flowchart and indicated generally at  500 . Method  400  can be performed by threads  94  in conjunction with thread controller  90 . 
         [0060]    At step  502 , the variable Qsize for thread controller  94  is set to the size of queue  86 . 
         [0061]    At step  504 , at determination is made as to whether the size of the queue has exceeded a maximum value. If the determination at step  504  is ‘yes’, then method  500  advances to step  506  at which point a dequeue with batch is performed according to method  400 . Thus, at step  506 , process  94  will notify writer thread  84  to perform a dequeue with batch according to method  400 . At step  508 , a flag is set to indicate that a particular packet has been processed. Step  508  is the last step in thread  94  to indicate that packets is processed. Note, however, the processed flag could be set after normal processing, or it could be set if system is congested and packets are ignored without processing. 
         [0062]    At step  510  it is determined whether sufficient dequeuing has occurred in order to bring the variable Qsize below a predefined minimum value. If yes, then method  500  advances from step  510  to step  502 . If no, then method  500  cycles from step  510  back to step  506 . 
         [0063]    Returning to step  504 , if a no determination is made then method  500  advances from step  504  to  512  at which point a determination is made as to whether there are any available processing ability from threads  94 . Such a determination can be based on whether QSize is lower than low mark. Packets available for processing, activeWorkers and active flag are used to determine when thread  94  should go to sleep mode. This is a two step determination, where the first step is to use QSize to determine if system is too busy, and the second step is to determine how many thread  94  are required to process packets available in queue  86  or whether all of threads  94  are already engaged in processing. 
         [0064]    If the determination at step  512  is yes then method  500  advances from step  512  to step  514  at which point a dequeue-with-batch is performed according to method  400 . After step  514  method  500  advances to step  516  and AVAIL is returned. 
         [0065]    If the determination at step  512  is no then method  500  advances directly to step  516  bypassing step  514 . 
         [0066]    At step  516  a determination is made (“AVAIL”) as to how many packets returned from queue  86  and whether there are any available processor threads  94 . For example, assume a batch size is one-hundred, and there are more than one-hundred packets available in queue  86 . Accordingly, AVAIL will be one-hundred, and PRODSIZE will be more than one-hundred. (PRODSIZE means how many packets are available in queue  86  ready for processing. PRODSIZE differs from QSize which is how many packets are available in  86  ready for processing or verdicting). In this case, current thread  94  is not capable of processing all packets, and more threads  94  are needed to process all packets. 
         [0067]    If at step  516  it is determined that there is no availability of processor threads  94  (i.e., Avail=0) then method  500  advances from step  516  to step  518 . 
         [0068]    At step  518  a determination is made which checks whether a current thread  94  is the only active thread processing packets and that particular thread  94  has not been idle for a defined period of time. 
         [0069]    If the determination at step  518  is “yes” then method  500  advances from step  518  to step  520  then a dequeue with batch is performed according to method  400  and then method  500  advances from step  520  back to step  516 . 
         [0070]    If the determination at step  520  is “no” then method  500  advances from step  518  to step  522 . At step  522  a determination is made based on the same conditions as previously described in relation to step  512 . 
         [0071]    If the determination at step  522  is “yes” then method  500  advances from step  522  to step  520  and step  520  is performed as previously discussed. 
         [0072]    If the determination at step  522  is “no” then method  500  advances from step  522  to step  524 . At step  524  a determination is made as to whether there are any more packets available in queue  86  for processing and current thread  94  is still active running. If yes, sleep mode is entered. 
         [0073]    Also, if the determination at step  524  is “yes” then method  500  advances from step  524  to step  526  and the variable active worker status is set to false and then at step  528  the variable worker waiting is set to true. These settings are used during subsequent determinations made at step  518  and step  524  and  530 . From step  530  method  500  cycles back to step  516 . 
         [0074]    If the determination at step  524  is “no” then method  500  advances from step  524  to step  532 . 
         [0075]    Returning now to step  516 , If at step  516  it is determined that there are packets available for processing (i.e., Avail &lt;&gt;0) then method  500  advances from step  516  to step  538 . At step  538  a determination is made as to whether a given processor thread  94  is active. If not, them method advances from step  538  to step  540  at which point the active worker variable is incremented and a flag is set that indicates the given processor thread  94  is now active. 
         [0076]    Step  542  is either reached directly by a “yes” determination from step  538  or indirectly via step  540 . However step  542  is reached, the actual processing of a given packet is performed at step  542  by the particular processor thread  94 . Again, as described in the previous telecommunication example, the processing performed can be a determination as to whether a particular packet should be “dropped” or “forwarded” onto another network element for further processing. Thus processor thread  94  can interact with other telecommunication network elements, such as billing and/or subscription information associated with a particular subscriber in order to ascertain whether a particular packet should be “dropped” or “forwarded”. Eventually, writer thread  84  will pass the packet and the particular verdict (“drop” or “forward” along to queue  78  at the appropriate time according to the teachings herein. 
         [0077]    At step  544  a flag is set within queue  86  indicating that a particular packet has been processed. This flag is used at step  425  of method  400  as previously discussed. 
         [0078]    At step  546  the loop that was commenced by step  516  is terminated and method  500  cycles back to step  502 . 
         [0079]    When application  70  is operating, packets can be processed without the need to lock queue  86 . Reproduced below in various Tables are simple examples of how packets in queue  74  can be processed for eventual writing to queue  76  as they pass through queue  86 . 
         [0000]    
       
         
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
             
           
               
                 TABLE I 
               
             
             
               
                   
               
               
                 Normal Packet processing without using queue batch mode. 
               
             
          
           
               
                 Sequence 
                 Status of Queue 86 
               
               
                   
               
               
                 0 
                 Application 70 starts, queue 86 is initialized. 
               
               
                 This is initial state. 
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                   
                 Tail = 0 
                 Queue is pre allocated. 
               
             
          
           
               
                   
                 ProcHead = 0 
                 Processed = 0 
                 0 
                 0 
                 0           
               
               
                   
                 WRITHEAD = 0 
               
             
          
           
               
                 1 
                 Reader thread 82 reads three packets from Queue 74 and 
               
               
                 (Method 300) 
                 Enqueues them into queue 86. 
               
               
                   
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                   
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                   
                 ProcHead = 0 
                 Processed = 0 
                 0 
                 0 
                 0           
               
               
                   
                 WRITHEAD = 0 
                 Packet 
                 Packet 
                 Packet 
               
             
          
           
               
                 2 
                 Process thread 94 start processing packets. Process thread 
               
               
                 (Method 500) 
                 94 dequeues first packet from queue 86 and move 
               
               
                 *means packet is dequeued by 
                 procHead forward 
               
               
                 procHead but that the packet has 
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                 not been dequeued by 
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                 WRITHEADWRITHEAD. 
                 ProcHead = 1 
                 Processed = 0 
                 0 
                 0 
                 0           
               
               
                   
                 WRITHEAD = 0 
                 Packet* 
                 Packet 
                 Packet 
               
             
          
           
               
                 3 
                 Process thread 94 finishes processing packet, and 
               
               
                 Method 500 and step544 
                 processed is flag to 1. 
               
               
                   
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                   
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                 ProcHead = 1 
                 Processed = 1 
                 0 
                 0 
                 0           
               
               
                 WRITHEAD = 0 
                 Packet* 
                 Packet 
                 Packet 
               
             
          
           
               
                 4 
                 Writer thread 84 dequeues first packet from queue 86, and 
               
               
                 Method 400 
                 checks the processed flag. If processed flag is set to 1, the 
               
               
                 **means packet is dequeued by 
                 packet is verdicted by reading the packet from queue 86 
               
               
                 WRITHEAD and it is forwarded to 
                 and writing to queue 78 and WRITHEAD is moved forward. 
               
               
                 queue 78 
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                   
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                   
                 ProcHead = 1 
                 Processed = 1 
                 0 
                 0 
                 0           
               
               
                   
                 WRITHEAD = 1 
                 Packet** 
                 Packet 
                 Packet 
               
             
          
           
               
                 5 
                 Process thread 94 repeats steps 2, 3 and write thread 84 
               
               
                   
                 repeats step 4 for packet 2 and 3. Eventually, all packets will 
               
               
                   
                 be processed. 
               
               
                   
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                   
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                   
                 ProcHead = 3 
                 Processed = 1 
                 1 
                 1 
                 0           
               
               
                   
                 WRITHEAD = 3 
                 Packet** 
                 Packet** 
                 Packet** 
               
               
                   
                   
               
               
                   
                             indicates data missing or illegible when filed 
               
             
          
         
       
     
         [0000]    
       
         
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
               
             
           
               
                 TABLE II 
               
             
             
               
                   
               
               
                 Normal packet processing with batch mode. (batch size = 2). 
               
             
          
           
               
                 Sequence 
                 Status of Queue 86 
               
               
                   
               
               
                 0 
                 Application 70 starts, queue 86 is initialized. 
               
               
                   
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                   
                 Tail = 0 
                 Queue is pre allocated. 
               
             
          
           
               
                   
                 ProcHead = 0 
                 Processed = 0 
                 0 
                 0 
                 0 
                 0 
               
               
                   
                 WRITHEAD = 0 
               
             
          
           
               
                 1 
                 Reader thread reads 3 packets from Queue 74 and Enqueues them into 
               
               
                 (Method 300) 
                 queue 86. 
               
               
                   
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                   
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                   
                 ProcHead = 0 
                 Processed = 0 
                 0 
                 0 
                 0 
                 0 
               
               
                   
                 WRITHEAD = 0 
                 Packet 
                 Packet 
                 Packet 
               
             
          
           
               
                 2 
                 Process thread 94 starts processing packets. 2 packets are dequeued from 
               
               
                 (Method 500) 
                 queue 86. 
               
               
                   
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                   
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                   
                 ProcHead = 2 
                 Processed = 0 
                 0 
                 0 
                 0 
                 0 
               
               
                   
                 WRITHead = 0 
                 Packet* 
                 Packet* 
                 Packet 
               
             
          
           
               
                 3 
                 Process thread 94 finishes processing first packet, and processed flag is set 
               
               
                 (Method 500 
                 to 1. 
               
               
                 including 
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                 step 544) 
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                   
                 ProcHead = 2 
                 Processed = 1 
                 0 
                 0 
                 0 
                 0 
               
               
                   
                 WRITHEAD = 0 
                 Packet* 
                 Packet 
                 Packet 
               
             
          
           
               
                 4 
                 Write thread 84 dequeue first packet from queue, check processed flag. If 
               
               
                 (Method 400 
                 it&#39;s set to 1, the packet is verdicted 
               
               
                 Packets are 
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                 processed 
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                 and 
                 ProcHead = 2 
                 Processed = 1 
                 0 
                 0 
                 0 
                 0 
               
               
                 verdicted.) 
                 WRITHEAD = 0 
                 Packet** 
                 Packet 
                 Packet 
               
             
          
           
               
                 5 
                 Process thread finished processing second packet, it set processed flag to 1. 
               
               
                 (Method 500 
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                 including 
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                 Step 544) 
                 ProcHead = 2 
                 Processed = 1 
                 1 
                 0 
                 0 
                 0 
               
               
                   
                 WRITHEAD = 0 
                 Packet* 
                 Packet* 
                 Packet 
               
             
          
           
               
                 6 
                 Write thread 84 dequeue first packet from queue, check processed flag. If it&#39;s 
               
               
                 (Method 400) 
                 set to 1, the packet is verdicted 
               
               
                   
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                   
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                   
                 ProcHead = 2 
                 Processed = 1 
                 1 
                 0 
                 0 
                 0 
               
               
                   
                 WRITHEAD = 0 
                 Packet** 
                 Packet** 
                 Packet 
               
             
          
           
               
                 7 
                 Verdict is moved forward by 2. 
               
               
                 (Method 400) 
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                   
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                   
                 ProcHead = 2 
                 Processed = 1 
                 1 
                 0 
                 0 
                 0 
               
               
                   
                 WRITHEAD = 2 
                 Packet** 
                 Packet** 
                 Packet 
               
             
          
           
               
                 8 
                 Process thread will repeat same steps and write thread 84 will repeat same 
               
               
                 (Method 
                 steps. Eventually, all packets will be processed. 
               
               
                 500, 400) 
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                   
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                   
                 ProcHead = 3 
                 Processed = 1 
                 1 
                 1 
                 0 
                 0 
               
               
                   
                 WRITHEAD = 3 
                 Packet** 
                 Packet** 
                 Packet** 
               
               
                   
                   
               
             
          
         
       
     
         [0000]    
       
         
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
               
             
           
               
                 TABLE III 
               
             
             
               
                   
               
               
                 Packet processing if verdict process dequeued packet before packet is processed 
               
             
          
           
               
                 Sequence 
                 Status of Queue 86 
               
               
                   
               
               
                 0 
                 Application 70 starts, queue 86 is initialized. 
               
               
                   
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                   
                 Tail = 0 
                 Queue is pre allocated. 
               
             
          
           
               
                   
                 ProcHead = 0 
                 Processed = 0 
                 0 
                 0 
                 0 
                 0 
               
               
                   
                 WRITHEAD = 0 
               
             
          
           
               
                 1 
                 Reader thread 82 reads three packets from Queue 74 and Enqueue them 
               
               
                 (Method 300) 
                 into queue. 
               
               
                   
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                   
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                   
                 ProcHead = 0 
                 Processed = 0 
                 0 
                 0 
                 0 
                 0 
               
               
                   
                 WRITHEAD = 0 
                 Packet 
                 Packet 
                 Packet 
               
             
          
           
               
                 2 
                 Write thread 84 dequeue first packet from queue, check processed flag. It 
               
               
                 (Method 
                 is set to 0, the packet won&#39;t be verdicted, the write thread 84 will yield until 
               
               
                 400)The 
                 processed is set to 1. 
               
               
                 packets is 
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                 dequeued by 
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                 write thread but 
                 ProcHead = 0 
                 Processed = 0 
                 0 
                 0 
                 0 
                 0 
               
               
                 it is waiting for 
                 WRITHEAD = 0 
                 Packet 
                 Packet 
                 Packet 
               
               
                 processed flag. 
               
             
          
           
               
                 3 
                 Process thread 94 starts processing packets. It dequeues first packet from 
               
               
                 (Method 500) 
                 queue 86 and move procHead forward 
               
               
                   
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                   
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                   
                 ProcHead = 1 
                 Processed = 0 
                 0 
                 0 
                 0 
                 0 
               
               
                   
                 VertHead = 0 
                 Packet* 
                 Packet 
                 Packet 
               
             
          
           
               
                 4 
                 Process thread 94 finishes processing packet, and processed flag is set to 
               
               
                 (Method 500) 
                 1. 
               
               
                   
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                   
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                   
                 ProcHead = 1 
                 Processed = 1 
                 0 
                 0 
                 0 
                 0 
               
               
                   
                 WRITHEAD = 0 
                 Packet* 
                 Packet 
                 Packet 
               
             
          
           
               
                 5 
                 Write thread 84 dequeues first packet from queue 86, check processed 
               
               
                 (Method 
                 flag. If processed flag set to one, the packet is verdicted and WRITHEAD 
               
               
                 400)Packets is 
                 is moved forward. 
               
               
                 processed and 
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                 verdicted. 
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                   
                 ProcHead = 1 
                 Processed = 1 
                 0 
                 0 
                 0 
                 0 
               
               
                   
                 WRITHEAD = 1 
                 Packet** 
                 Packet 
                 Packet 
               
             
          
           
               
                 6 
                 Process thread 94 will repeat steps and write thread 84 will repeat steps 
               
               
                 (Method 
                 for packet 2 and 3. Eventually, all packets will be processed. 
               
               
                 400, 500) 
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                   
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                   
                 ProcHead = 3 
                 Processed = 1 
                 1 
                 1 
                 0 
                 0 
               
               
                   
                 WRITHEAD = 3 
                 Packet** 
                 Packet** 
                 Packet** 
               
               
                   
                   
               
             
          
         
       
     
         [0000]    
       
         
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
               
             
               
               
             
               
               
               
             
               
               
               
               
               
               
               
             
           
               
                 TABLE IV 
               
             
             
               
                   
               
               
                 Packet processing times out if processor thread is not fast enough to process packet. 
               
             
          
           
               
                 Sequence 
                 Status of Queue 86 
               
               
                   
               
               
                 0 
                 Application 70 starts, queue 86 is initialized. 
               
               
                   
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                   
                 Tail = 0 
                 Queue is pre allocated. 
               
             
          
           
               
                   
                 ProcHead = 0 
                 Processed = 0 
                 0 
                 0 
                 0 
                 0 
               
               
                   
                 WRITHEAD = 0 
               
             
          
           
               
                 1 
                 Reader thread read 3 packets from Queue 74 and Enqueue them into 
               
               
                 (Method 300) 
                 queue. 
               
               
                   
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                   
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                   
                 ProcHead = 0 
                 Processed = 0 
                 0 
                 0 
                 0 
                 0 
               
               
                   
                 WRITHEAD = 0 
                 Packet 
                 Packet 
                 Packet 
               
             
          
           
               
                 2 
                 Write thread 84 dequeues first packet from queue 86, check processed 
               
               
                 (Method 400) 
                 flag. It is set to 0, the packet won&#39;t be verdicted, the write thread 84 keeps 
               
               
                   
                 yield and eventually it timed out. (Yield times &gt;= MaxYield). 
               
               
                   
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                   
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                   
                 ProcHead = 0 
                 Processed = 0 
                 0 
                 0 
                 0 
                 0 
               
               
                   
                 WRITHEAD = 0 
                 Packet 
                 Packet 
                 Packet 
               
             
          
           
               
                 5 
                 Write thread 84 set processed flag to true and WRITHEAD is moved 
               
               
                 (Method 
                 forward. 
               
               
                 400)Packet 
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                 timed out 
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                 because 
                 ProcHead = 0 
                 Processed = 1 
                 0 
                 0 
                 0 
                 0 
               
               
                 processing 
                 WRITHEAD = 1 
                 Packet* 
                 Packet 
                 Packet 
               
               
                 thread 94 is 
               
               
                 too slow. 
               
               
                 Verdict thread 
               
               
                 set processed 
               
               
                 flag to 1 and 
               
               
                 move 
               
               
                 WRITHEAD 
               
               
                 forward. 
               
             
          
           
               
                 6 
                 Later on, processor thread 94 dequeues first packet, processes the packet 
               
               
                 (Method 
                 and move procHead forward, however, packet has already been verdicted 
               
               
                 500)The 
                 already. 
               
               
                 packet is 
                 Queue Object. (Queue Capacity = 5) 
               
             
          
           
               
                 processed 
                 Tail = 3 
                 Queue is pre allocated. 
               
             
          
           
               
                 later but the 
                 ProcHead = 1 
                 Processed = 1 
                 0 
                 0 
                 0 
                 0 
               
               
                 packets has 
                 WRITHEAD = 1 
                 Packet** 
                 Packet 
                 Packet 
               
               
                 already been 
               
               
                 forwarded to 
               
               
                 queue 78. 
               
               
                   
               
             
          
         
       
     
         [0080]    While the foregoing provides certain embodiments, it is to be understood that such embodiments are merely exemplary and that variations, combinations and/or subsets thereof are contemplated.