Annotation of embedaddon/strongswan/src/libstrongswan/processing/scheduler.h, revision 1.1
1.1 ! misho 1: /*
! 2: * Copyright (C) 2009-2015 Tobias Brunner
! 3: * Copyright (C) 2005-2007 Martin Willi
! 4: * Copyright (C) 2005 Jan Hutter
! 5: * HSR Hochschule fuer Technik Rapperswil
! 6: *
! 7: * This program is free software; you can redistribute it and/or modify it
! 8: * under the terms of the GNU General Public License as published by the
! 9: * Free Software Foundation; either version 2 of the License, or (at your
! 10: * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
! 11: *
! 12: * This program is distributed in the hope that it will be useful, but
! 13: * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
! 14: * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
! 15: * for more details.
! 16: */
! 17:
! 18: /**
! 19: * @defgroup scheduler scheduler
! 20: * @{ @ingroup processing
! 21: */
! 22:
! 23: #ifndef SCHEDULER_H_
! 24: #define SCHEDULER_H_
! 25:
! 26: typedef struct scheduler_t scheduler_t;
! 27:
! 28: #include <library.h>
! 29: #include <processing/jobs/job.h>
! 30:
! 31: /**
! 32: * The scheduler queues timed events which are then passed to the processor.
! 33: *
! 34: * The scheduler is implemented as a heap. A heap is a special kind of tree-
! 35: * based data structure that satisfies the following property: if B is a child
! 36: * node of A, then key(A) >= (or <=) key(B). So either the element with the
! 37: * greatest (max-heap) or the smallest (min-heap) key is the root of the heap.
! 38: * We use a min-heap with the key being the absolute unix time at which an
! 39: * event is scheduled. So the root is always the event that will fire next.
! 40: *
! 41: * An earlier implementation of the scheduler used a sorted linked list to store
! 42: * the events. That had the advantage that removing the next event was extremely
! 43: * fast, also, adding an event scheduled before or after all other events was
! 44: * equally fast (all in O(1)). The problem was, though, that adding an event
! 45: * in-between got slower, as the number of events grew larger (O(n)).
! 46: * For each connection there could be several events: IKE-rekey, NAT-keepalive,
! 47: * retransmissions, expire (half-open), and others. So a gateway that probably
! 48: * has to handle thousands of concurrent connections has to be able to queue a
! 49: * large number of events as fast as possible. Locking makes this even worse, to
! 50: * provide thread-safety, no events can be processed, while an event is queued,
! 51: * so making the insertion fast is even more important.
! 52: *
! 53: * That's the advantage of the heap. Adding an element to the heap can be
! 54: * achieved in O(log n) - on the other hand, removing the root node also
! 55: * requires O(log n) operations. Consider 10000 queued events. Inserting a new
! 56: * event in the list implementation required up to 10000 comparisons. In the
! 57: * heap implementation, the worst case is about 13.3 comparisons. That's a
! 58: * drastic improvement.
! 59: *
! 60: * The implementation itself uses a binary tree mapped to a one-based array to
! 61: * store the elements. This reduces storage overhead and simplifies navigation:
! 62: * the children of the node at position n are at position 2n and 2n+1 (likewise
! 63: * the parent node of the node at position n is at position [n/2]). Thus,
! 64: * navigating up and down the tree is reduced to simple index computations.
! 65: *
! 66: * Adding an element to the heap works as follows: The heap is always filled
! 67: * from left to right, until a row is full, then the next row is filled. Mapped
! 68: * to an array this gets as simple as putting the new element to the first free
! 69: * position. In a one-based array that position equals the number of elements
! 70: * currently stored in the heap. Then the heap property has to be restored, i.e.
! 71: * the new element has to be "bubbled up" the tree until the parent node's key
! 72: * is smaller or the element got the new root of the tree.
! 73: *
! 74: * Removing the next event from the heap works similarly. The event itself is
! 75: * the root node and stored at position 1 of the array. After removing it, the
! 76: * root has to be replaced and the heap property has to be restored. This is
! 77: * done by moving the bottom element (last row, rightmost element) to the root
! 78: * and then "seep it down" by swapping it with child nodes until none of the
! 79: * children has a smaller key or it is again a leaf node.
! 80: */
! 81: struct scheduler_t {
! 82:
! 83: /**
! 84: * Adds a event to the queue, using a relative time offset in s.
! 85: *
! 86: * @param job job to schedule
! 87: * @param time relative time to schedule job, in s
! 88: */
! 89: void (*schedule_job) (scheduler_t *this, job_t *job, uint32_t s);
! 90:
! 91: /**
! 92: * Adds a event to the queue, using a relative time offset in ms.
! 93: *
! 94: * @param job job to schedule
! 95: * @param time relative time to schedule job, in ms
! 96: */
! 97: void (*schedule_job_ms) (scheduler_t *this, job_t *job, uint32_t ms);
! 98:
! 99: /**
! 100: * Adds a event to the queue, using an absolute time.
! 101: *
! 102: * The passed timeval should be calculated based on the time_monotonic()
! 103: * function.
! 104: *
! 105: * @param job job to schedule
! 106: * @param time absolute time to schedule job
! 107: */
! 108: void (*schedule_job_tv) (scheduler_t *this, job_t *job, timeval_t tv);
! 109:
! 110: /**
! 111: * Returns number of jobs scheduled.
! 112: *
! 113: * @return number of scheduled jobs
! 114: */
! 115: u_int (*get_job_load) (scheduler_t *this);
! 116:
! 117: /**
! 118: * Remove all scheduled jobs.
! 119: */
! 120: void (*flush)(scheduler_t *this);
! 121:
! 122: /**
! 123: * Destroys a scheduler object.
! 124: */
! 125: void (*destroy) (scheduler_t *this);
! 126: };
! 127:
! 128: /**
! 129: * Create a scheduler.
! 130: *
! 131: * @return scheduler_t object
! 132: */
! 133: scheduler_t *scheduler_create(void);
! 134:
! 135: #endif /** SCHEDULER_H_ @}*/
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to scheduler.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / strongswan / src / libstrongswan / processing