Open AccessMultiprocess Time Queue
Author(s) -
Andrej Brodnik,
Johan Karlsson
Publication year - 2001
Publication title -
lecture notes in computer science
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.249
H-Index - 400
eISSN - 1611-3349
pISSN - 0302-9743
ISBN - 3-540-42985-9
DOI - 10.1007/3-540-45678-3_51
Subject(s) - queue , computer science , bounded function , multilevel queue , process (computing) , priority queue , queue management system , discrete time and continuous time , constant (computer programming) , bulk queue , real time computing , mathematical optimization , mathematics , computer network , operating system , statistics , programming language , mathematical analysis
We show how to implement a bounded time queue for two different processes. The time queue is a variant of a priority queue with elements from a discrete universe. The bounded time queue has elements from a discrete bounded universe. One process has time constraints and may only spend constant worst case time on each operation while the other process may spend more time. The time constrained process only has to be able to perform some of the time queue operations while the other process has to be able to perform all operations. We show how to do a deamortization of the deleteMin cost and to provide mutual exclusion for the parts of the data structure that both processes maintain.Godkänd; 2001; 20060922 (ysko
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom