[go: up one dir, main page]

WO2003001353A2 - Ameliorations dans la gestion de temporisateurs - Google Patents

Ameliorations dans la gestion de temporisateurs Download PDF

Info

Publication number
WO2003001353A2
WO2003001353A2 PCT/GB2002/002791 GB0202791W WO03001353A2 WO 2003001353 A2 WO2003001353 A2 WO 2003001353A2 GB 0202791 W GB0202791 W GB 0202791W WO 03001353 A2 WO03001353 A2 WO 03001353A2
Authority
WO
WIPO (PCT)
Prior art keywords
time
array
unidimensional
timer
significant
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/GB2002/002791
Other languages
English (en)
Other versions
WO2003001353A3 (fr
Inventor
Steve Jones
Graham Finney
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Marconi Communications Ltd
Marconi UK Intellectual Property Ltd
BAE Systems Electronics Ltd
Original Assignee
Marconi Communications Ltd
Marconi Co Ltd
Marconi UK Intellectual Property Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Marconi Communications Ltd, Marconi Co Ltd, Marconi UK Intellectual Property Ltd filed Critical Marconi Communications Ltd
Priority to CA002450030A priority Critical patent/CA2450030A1/fr
Priority to JP2003507680A priority patent/JP2005506730A/ja
Priority to EP02730526A priority patent/EP1454215A2/fr
Priority to AU2002302844A priority patent/AU2002302844A1/en
Publication of WO2003001353A2 publication Critical patent/WO2003001353A2/fr
Anticipated expiration legal-status Critical
Publication of WO2003001353A3 publication Critical patent/WO2003001353A3/fr
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F1/00—Details not covered by groups G06F3/00 - G06F13/00 and G06F21/00
    • G06F1/04—Generating or distributing clock signals or signals derived directly therefrom
    • G06F1/14—Time supervision arrangements, e.g. real time clock

Definitions

  • This invention relates to improvements in timer management, and in particular to applications where many timers are managed, for example, in telecommunication systems .
  • FSM Finite State Machine
  • timers are not" an issue when the time period required to manage the timer is significantly less than the time slices available in the environment in which the imers are operating.
  • Present systems use timers which are held in a unidimensional array, or a single linked list.
  • timers may vary from a few milliseconds to a number of days, and so a timer covering comparatively long periods of time may need allocation in the array/list.
  • the process of allocating the timer to a queue of timers depends on the type of array or list being used by the system.
  • timers are ordered into a simple queue. Less memory is required for this type of array, however the timer manager has to sort through the array to find a correct allocation. Furthermore, any timer in the array that is positioned behind the newly allocated timer has to be shuffled back to make a space in the array in which the timer is allocated. This shuffling can be very time consuming if there are many timers in the array.
  • a telecommunication system might operate over
  • a sorted single linked list is comparable to a simple linear array, except that it has a variable size; when a new timer is allocated to the sorted linked list, the list increases in size.
  • a pointer in the list points to the entry that is next to expire.
  • a binary tree approach might be considered, and works best when the data is random. Timer data is not always random. A binary tress system is likely to be more efficient than the single linked list, however, the binary tree occupies more memory since two links are required for each entry.
  • the present invention aims to ameliorate the problems associated with managing a large number of timers, and in its broadest form provides a timer management system that allocates timers in multidimensional array, the position of the timer in the array being determined by the units in the timer.
  • a method for setting a timer in a system comprising determining an expiry time value from a timer time value, allocating the expiry time value to a first unidimensional array of a multidimensional array, the multidimensional array having a plurality of linked unidimensional arrays, each unidimensional array corresponding to a different significant unit of time, the first unidimensional array corresponding to a first significant unit of the expiry time, and reallocating any remaining significant units of expiry time to another of the plurality of unidimensional arrays when the first significant unit of the expiry time has expired, whereby the timer times out when all significant units of the expiry time have expired.
  • a system for setting a timer comprising a multidimensional array, the multidimensional array comprising a plurality of linked unidimensional arrays, each unidimensional array corresponding to a different significant unit of time, an expiry time value being determined from the timer value, a first allocator for allocating the expiry time value into a unidimensional array corresponding to a first significant unit of the expiry value, and a second allocator for reallocating any remaining value of the expiry time into any other unidimensional array when the first significant unit of the expiry time has expired, wherein the timer times out when all significant units of the expiry time have expired.
  • Embodiments of the present invention have the advantages of reducing the time and memory required for managing timers in systems . The reduction in time spent allocating timers results in systems that are able to handle many more timers without suffering from the problems associated with prior art systems .
  • Figure 1 is a representation of a multidimensional array embodying the present invention.
  • Figure 2 is a flow diagram of a process embodying the present invention .
  • a two dimensional array 10 is split into 3 columns , each column relating to a significant unit of time .
  • Column P 12 relates to hours
  • column Q 14 relates to minutes
  • column R 16 relates to seconds .
  • the columns are unidimensional arrays of linked lists , and each column is linked to the next preferably in an hierarchical order .
  • Each element in each column relates to a standard unit of time of the significant unit of time that the column represents . For example , there are twenty four elements in the P hours column, sixty elements in the minutes Q column, and sixty elements in the seconds R column; one hour is a standard unit of time in the P column .
  • a process 30 for allocating a timer in array 10 is shown .
  • the machine , or instantaneous time 32 has discrete significant units of time , A hours , B minutes and C seconds .
  • a timer 34 requires allocation in an array (not shown) .
  • the timer is set to expire after XX hours , YY minutes and ZZ seconds .
  • the instantaneous time and timer values are combined at 36 to calculate a value 39 for an expiry time 38 .
  • the timer therefore, expires at A+XX hours, B+YY minutes and C+ZZ seconds .
  • the combined system time and timer details 30 are then inserted at 40 into the appropriate element in the array of the most significant unit of the expiry time; in this example, the expiry time is input in the A+XX element in the hour column P 12 in the array 10. So, if the instantaneous time is 00:02:12 and the time being allocated expires after 01:10:03, the A+XX value is equal to 1 and the timer is allocated the 01 element 18 in the array.
  • the remaining significant units of the expiry time that is B+YY minutes and C+ZZ seconds 41, are placed in the A+XX element of column P.
  • the C+ZZ value 45 is inserted at 44 into the B+YY element of column Q 14. In the example given B+YY is equal to 12 minutes so the C+ZZ remaining value 45 is inserted into the 12 th element of the column Q 20.
  • timers can occupy the same element of any column.
  • the remaining value for that timer is passed to the next column in the array when the system clock component reaches the element in the array to which that component corresponds .
  • clock component we mean the hours, minutes, seconds, etc. of the system clock.
  • Other columns for different time values are available, for example, the array may have columns for days, hours, minutes, seconds, milliseconds, and so on.
  • b is the number of bytes required for information about each timer
  • r is the timer resolution
  • the maximum and minimum time to allocate the timer is equal to a, where a is the allocation time
  • the sorted array approach is used to store the timers in the order in which they expire. This requires an array which occupies a multiple of the number of timers in the system. So, number of timers in the system;
  • the single link list is similar to the sorted array, except that the timer entries are all linked to one another, that is each timer contains information about the location in the array of the next timer to expire .
  • the binary tree method is designed to minimise the searching and sorting by putting the timers into a flatter structure and not into a single string. Each entry in this method has at least two branches
  • a method embodying the present invention is designed to minimise the time and memory required for allocating, and searching for, the timers.
  • the formula used to calculate the memory and time values are as follows :
  • e is the initial number of elements in the array at the start of each linked list.
  • n is the number of arrays holding the single linked list.
  • the values used in these calculations are typical of a real-time telecommunications system
  • the results in the table show how the prior art systems are either memory efficient but time consuming, or memory consuming but time efficient.
  • the embodiment of the present invention is, in comparison, both memory and time efficient.
  • the skilled person will envisage alternatives to the exampled embodiment without leaving the scope of the invention.
  • the timer units can be placed in any element of the array corresponding to the value in the timer to that element, with the remainder value being passed to the next appropriate element in the cell when the value expires .

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Measurement Of Unknown Time Intervals (AREA)
  • Communication Control (AREA)

Abstract

L'invention concerne un procédé de gestion de temporisateurs dans un système, permettant de réduire la mémoire et le temps requis pour affecter et trouver un temporisateur dans un réseau. Un temps d'expiration est calculé par combinaison d'un temps d'horloge instantané avec la valeur de temps du temporisateur, et le temps d'expiration est en unité de temps significatives. Un réseau multidimensionnel comporte une pluralité de réseaux monodimensionnels. Chaque réseau monodimensionnel correspond à unité de temps significative et est divisé en éléments. Chaque élément du réseau monodimensionnel correspond à une unité de temps standard pour l'unité de temps significative du réseau monodimensionnel. La valeur d'ordre le plus élevé d'unités significatives du temps d'expiration sert à déterminer la position du temporisateur dans le réseau. S'il reste du temps dans la valeur du temps d'expiration, ce temps est placé dans le réseau avec le temporisateur. Lorsque le temps d'expiration de cette unité de temps significative est arrivé à expiration, la valeur restante sert à déterminer la position du temporisateur dans le réseau monodimensionnel suivant. Lorsque la valeur du temps d'expiration est nulle, le temporisateur effectue une temporisation.
PCT/GB2002/002791 2001-06-21 2002-06-13 Ameliorations dans la gestion de temporisateurs Ceased WO2003001353A2 (fr)

Priority Applications (4)

Application Number Priority Date Filing Date Title
CA002450030A CA2450030A1 (fr) 2001-06-21 2002-06-13 Ameliorations dans la gestion de temporisateurs
JP2003507680A JP2005506730A (ja) 2001-06-21 2002-06-13 タイマー管理における改良
EP02730526A EP1454215A2 (fr) 2001-06-21 2002-06-13 Ameliorations dans la gestion de temporisateurs
AU2002302844A AU2002302844A1 (en) 2001-06-21 2002-06-13 Improvements in timer management

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
GB0115271A GB0115271D0 (en) 2001-06-21 2001-06-21 Improvements in timer management
GB0115271.9 2001-06-21

Publications (2)

Publication Number Publication Date
WO2003001353A2 true WO2003001353A2 (fr) 2003-01-03
WO2003001353A3 WO2003001353A3 (fr) 2004-05-21

Family

ID=9917139

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/GB2002/002791 Ceased WO2003001353A2 (fr) 2001-06-21 2002-06-13 Ameliorations dans la gestion de temporisateurs

Country Status (6)

Country Link
EP (1) EP1454215A2 (fr)
JP (1) JP2005506730A (fr)
AU (1) AU2002302844A1 (fr)
CA (1) CA2450030A1 (fr)
GB (1) GB0115271D0 (fr)
WO (1) WO2003001353A2 (fr)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7160266B2 (en) 2000-01-19 2007-01-09 Cordis Neurovascular, Inc. Inflatable balloon catheter with purge mechanism and method
WO2013079097A1 (fr) * 2011-11-29 2013-06-06 Huawei Technologies Co., Ltd. Dispositif de mesure de temps de retard, procédé pour gérer une pluralité de retards et appareil pour retarder une pluralité de paquets de données

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
R.BROWN: "Calendar queues: a fast 0(1) priority queue implementation for the simulation event set" COMMUNICATIONS OF THE ACM, vol. 31, no. 10, October 1988 (1988-10), pages 1220-1227, XP002272555 *
S. BOCKING,V. SEIDEL,P. VINDEBY: "CHANNELS: a run-time system for multimedia protocols " 4TH INTERNATIONAL CONFERENCE ON COMPUTER COMMUNICATIONS AND NETWORKS (ICCCN '95) , 20 - 23 September 1995, pages 178-185, XP002272556 *
VARGHESE G ET AL: "HASHED AND HIERARCHICAL TIMING WHEELS: EFFICIENT DATA STRUCTURES FOR IMPLEMENTING A TIMER FACILITY" IEEE / ACM TRANSACTIONS ON NETWORKING, IEEE INC. NEW YORK, US, vol. 5, no. 6, 1 December 1997 (1997-12-01), pages 824-834, XP000734410 ISSN: 1063-6692 *

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7160266B2 (en) 2000-01-19 2007-01-09 Cordis Neurovascular, Inc. Inflatable balloon catheter with purge mechanism and method
WO2013079097A1 (fr) * 2011-11-29 2013-06-06 Huawei Technologies Co., Ltd. Dispositif de mesure de temps de retard, procédé pour gérer une pluralité de retards et appareil pour retarder une pluralité de paquets de données
CN104115457A (zh) * 2011-11-29 2014-10-22 华为技术有限公司 时延计时设备、管理多个时延的方法及延迟多个数据包的装置
US9391904B2 (en) 2011-11-29 2016-07-12 Huawei Technologies Co., Ltd. Delay timer device, method for managing a plurality of delays, and apparatus for delaying a plurality of data packets
CN104115457B (zh) * 2011-11-29 2017-08-25 华为技术有限公司 时延计时设备、管理多个时延的方法及延迟多个数据包的装置

Also Published As

Publication number Publication date
JP2005506730A (ja) 2005-03-03
CA2450030A1 (fr) 2003-01-03
WO2003001353A3 (fr) 2004-05-21
AU2002302844A1 (en) 2003-01-08
EP1454215A2 (fr) 2004-09-08
GB0115271D0 (en) 2001-08-15

Similar Documents

Publication Publication Date Title
US7779413B2 (en) Method of assigning available resources for internal and external users at start time of scheduled time period based on program reservations information
EP3553657A1 (fr) Procédé et dispositif permettant d'attribuer une tâche de système distribué
US20050081208A1 (en) Framework for pluggable schedulers
CN111813513A (zh) 基于分布式的实时任务调度方法、装置、设备及介质
US8769543B2 (en) System and method for maximizing data processing throughput via application load adaptive scheduling and context switching
GB2194086A (en) Job scheduling
US5758137A (en) Method and system for processing timer requests within a computer
CN110941602A (zh) 数据库的配置方法、装置、电子设备及存储介质
Yu et al. CaaS-LSM: compaction-as-a-service for LSM-based key-value stores in storage disaggregated infrastructure
US6912712B1 (en) Real time control system for multitasking digital signal processor using ready queue
WO2014046885A2 (fr) Identification de simultanéité pour le traitement de workflows à phases multiples
WO2002101997A1 (fr) Procede et systeme d'arbre binaire de programmation par multiplexage
WO2003001353A2 (fr) Ameliorations dans la gestion de temporisateurs
US7167969B2 (en) Apparatus and method for writing data to mirrored storage using multiple tasks working in parallel
CN112181498A (zh) 并发控制方法、装置和设备
US7930489B2 (en) Techniques for optimizing configuration partitioning
CN114338694B (zh) 一站式云数据中心服务器调度方法及系统
US8032543B2 (en) Sorting apparatus and method
US11461132B2 (en) Time based priority queue
CN111597392B (zh) 一种索引处理方法、装置、设备及存储介质
Jette et al. Gang scheduler-timesharing the cray t3d
US6829763B1 (en) Partitioned executive structure for real-time programs
US6724404B1 (en) Cluster tool reporting system
EP1630671A1 (fr) Struture pour module ordonnanceur
JPH0667899A (ja) タスクスケジューリング装置の複数タスク周期起動方法

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A2

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX MZ NO NZ OM PH PL PT RO RU SD SE SG SI SK SL TJ TM TN TR TT TZ UA UG US UZ VN YU ZA ZM ZW

AL Designated countries for regional patents

Kind code of ref document: A2

Designated state(s): GH GM KE LS MW MZ SD SL SZ TZ UG ZM ZW AM AZ BY KG KZ MD RU TJ TM AT BE CH CY DE DK ES FI FR GB GR IE IT LU MC NL PT SE TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG

121 Ep: the epo has been informed by wipo that ep was designated in this application
DFPE Request for preliminary examination filed prior to expiration of 19th month from priority date (pct application filed before 20040101)
WWE Wipo information: entry into national phase

Ref document number: 2450030

Country of ref document: CA

WWE Wipo information: entry into national phase

Ref document number: 2003507680

Country of ref document: JP

WWE Wipo information: entry into national phase

Ref document number: 028122798

Country of ref document: CN

WWE Wipo information: entry into national phase

Ref document number: 2002730526

Country of ref document: EP

ENP Entry into the national phase in:

Ref document number: 2004106531

Country of ref document: RU

Kind code of ref document: A

ENP Entry into the national phase in:

Ref document number: 2004106620

Country of ref document: RU

Kind code of ref document: A

Ref document number: 2004106784

Country of ref document: RU

Kind code of ref document: A

REG Reference to national code

Ref country code: DE

Ref legal event code: 8642

WWP Wipo information: published in national office

Ref document number: 2002730526

Country of ref document: EP

WWW Wipo information: withdrawn in national office

Ref document number: 2002730526

Country of ref document: EP