Sobre o Emprego de Tabelas Hash em Sistemas Operacionais de Tempo Real
Resumo
Sistemas operacionais empregam tabelas hash para diversas finalidades. Tabelas hash apresentam excelente comportamento no caso médio mas, no pior caso, degradam para algo semelhante a uma lista encadeada. Em função disto, tabelas hash não são usuais em sistemas operacionais de tempo real onde existe a necessidade de garantir deadlines. Este artigo discute o emprego de tabelas hash em sistemas de tempo real, considerando que, quando a probabilidade de um comportamento indesejado for suficientemente baixa, ele pode ser ignorado. Também são comparadas as abordagens simples e 2-choice para a construção da tabela.Referências
Azar, Y., Broder, A. Z., Karlin, A. R., Upfal, E. (1994) “Balanced Allocations”, Proceedings of the 26th Annual ACM Symposium on the Theory of Computing (STOC 94), pages 593-602.
Carter, J. L. and Wegman, M. N. (1979) “Universal classes of hash functions”, Journal of Computer and System Sciences, 18(2), pages 143–154.
Cormen, T. H., Leiserson, C. E., Rivest, R. L. (1990) “Introduction to Algorithms”, The MIT Press, Cambridge, United States.
Friedman, S., Krishnan, A., Leidenfrost, N., Brodie, B. C., Cytron, R. K., and Niehaus, D. (2003) “Hash tables for embedded and real-time systems”, Technical Report 2003-15, Department of Computer Science & Engineering, Washington University in Saint Louis.
Gonnet, G. H. (1981) “Expected Length of the Longest Probe Sequence in Hash Code Searching”, Journal of the ACM, 28(2), pages 289-304.
Liu, J. (2000) “Real-Time Systems”, Prentice-Hall, United States.
Karp, R. M., Luby, M., Heide, F. M. (1996) “Efficient PRAM Simulation on a distributed memory Machine”, Algorithmica, 16, pages 245-281.
Mitzenmacher, M., Richa, A., and Sitaraman, R. (2000) “The power of two random choices: A survey of the techniques and results”, In Handbook of Randomized Computing, P. Pardalos, S. Rajasekaran, and J. Rolim, Eds. Kluwer.
Parson, D. (2004) “Incremental Reorganization of Open Hash Tables”, Work-in-progress Section of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), May 25 - May 28, 2004.
Carter, J. L. and Wegman, M. N. (1979) “Universal classes of hash functions”, Journal of Computer and System Sciences, 18(2), pages 143–154.
Cormen, T. H., Leiserson, C. E., Rivest, R. L. (1990) “Introduction to Algorithms”, The MIT Press, Cambridge, United States.
Friedman, S., Krishnan, A., Leidenfrost, N., Brodie, B. C., Cytron, R. K., and Niehaus, D. (2003) “Hash tables for embedded and real-time systems”, Technical Report 2003-15, Department of Computer Science & Engineering, Washington University in Saint Louis.
Gonnet, G. H. (1981) “Expected Length of the Longest Probe Sequence in Hash Code Searching”, Journal of the ACM, 28(2), pages 289-304.
Liu, J. (2000) “Real-Time Systems”, Prentice-Hall, United States.
Karp, R. M., Luby, M., Heide, F. M. (1996) “Efficient PRAM Simulation on a distributed memory Machine”, Algorithmica, 16, pages 245-281.
Mitzenmacher, M., Richa, A., and Sitaraman, R. (2000) “The power of two random choices: A survey of the techniques and results”, In Handbook of Randomized Computing, P. Pardalos, S. Rajasekaran, and J. Rolim, Eds. Kluwer.
Parson, D. (2004) “Incremental Reorganization of Open Hash Tables”, Work-in-progress Section of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), May 25 - May 28, 2004.
Publicado
12/07/2008
Como Citar
OLIVEIRA, Rômulo Silva de.
Sobre o Emprego de Tabelas Hash em Sistemas Operacionais de Tempo Real. In: WORKSHOP DE SISTEMAS OPERACIONAIS (WSO), 5. , 2008, Belém/PA.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2008
.
p. 111-122.
