Аноним

Моментальные снимки в разделяемой памяти: различия между версиями

Материал из WEGA

Моментальные снимки в разделяемой памяти (посмотреть исходный код)

Версия от 01:58, 25 ноября 2024

173 байта добавлено ,  25 ноября 2024
→‎Литература
 
(не показаны 4 промежуточные версии 1 участника)
Строка 43: Строка 43:




Андерсон [3] предложил реализацию мультирайтерного снимка из однорайтерного. Каждый процесс хранит свое последнее обновление каждого компонента мультирайтерного снимка в однорайтерном снимке с соответствующими данными временной метки, вычисленными путем сканирования однорайтерного снимка. Операция сканирования выполняется с помощью однократного сканирования однорайтерного снимка. Для обновления требуется дважды просканировать и обновить однорайтерный снимок. Реализация предполагает некоторое увеличение размеров компонентов, т. е. для реализации мультирайтерного снимка с областью D требуется однорайтерный снимок с гораздо большей областью D'. Если целью является реализация мультирайтерных снимков из однорайтерных регистров (а не мультирайтерных), то построение Андерсона дает более эффективное решение, чем у Афека и коллег.
Андерсон [3] предложил реализацию мультирайтерного снимка из однорайтерного. Каждый процесс хранит свое последнее обновление каждого компонента мультирайтерного снимка в однорайтерном снимке с соответствующими данными временной метки, вычисленными путем сканирования однорайтерного снимка. Операция сканирования выполняется с помощью однократного сканирования однорайтерного снимка. Для обновления требуется дважды выполнить сканирование и обновление однорайтерного снимка. Реализация предполагает некоторое увеличение размеров компонентов, т. е. для реализации мультирайтерного снимка с областью D требуется однорайтерный снимок с гораздо большей областью D'. Если целью является реализация мультирайтерных снимков из однорайтерных регистров (а не мультирайтерных), то построение Андерсона дает более эффективное решение, чем у Афека и коллег.




Строка 72: Строка 72:


== Открытые вопросы ==
== Открытые вопросы ==
Некоторые нижние границы сложности для реализаций из регистров известны [9], но остаются пробелы между лучшими известными алгоритмами и лучшими нижними границами. В частности, неизвестно, существует ли эффективная реализация моментальных снимков из небольших регистров без ожидания.
Некоторые нижние границы сложности для реализаций из регистров известны [9], но разрыв между лучшими известными алгоритмами и лучшими нижними границами сохраняется. В частности, неизвестно, существует ли эффективная реализация моментальных снимков из небольших регистров без ожидания.


== Экспериментальные результаты ==
== Экспериментальные результаты ==
Строка 83: Строка 83:


См. также обзорную статью Фич о сложности реализации моментальных снимков [11].
См. также обзорную статью Фич о сложности реализации моментальных снимков [11].
== Литература ==


1. Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., Shavit, N.: Atomic snapshots of shared memory. J. Assoc. Comput. Mach. 40,873-890(1993)
1. Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., Shavit, N.: Atomic snapshots of shared memory. J. Assoc. Comput. Mach. 40,873-890(1993)
2. Anderson, J.H.: Composite registers. Distrib. Comput. 6, 141-154(1993)
2. Anderson, J.H.: Composite registers. Distrib. Comput. 6, 141-154(1993)
3. Anderson, J.H.: Multi-writer composite registers. Distrib. Comput. 7,175-195 (1994)
3. Anderson, J.H.: Multi-writer composite registers. Distrib. Comput. 7,175-195 (1994)
4. Aspnes, J., Herlihy, M.: Wait-free data structures in the asynchronous PRAM model. In: Proc. 2nd ACM Symposium on Parallel Algorithms and Architectures, Crete, July 1990. pp. 340-349. ACM, New York, 1990
4. Aspnes, J., Herlihy, M.: Wait-free data structures in the asynchronous PRAM model. In: Proc. 2nd ACM Symposium on Parallel Algorithms and Architectures, Crete, July 1990. pp. 340-349. ACM, New York, 1990
5. Attiya, H., Fouren, A.: Adaptive and efficient algorithms for lattice agreement and renaming. SIAM J. Comput. 31, 642-664 (2001)
5. Attiya, H., Fouren, A.: Adaptive and efficient algorithms for lattice agreement and renaming. SIAM J. Comput. 31, 642-664 (2001)
6. Attiya, H., Fouren, A., Gafni, E.: An adaptive collect algorithm with applications. Distrib. Comput. 15,87-96 (2002)
6. Attiya, H., Fouren, A., Gafni, E.: An adaptive collect algorithm with applications. Distrib. Comput. 15,87-96 (2002)
7. Attiya, H., Herlihy, M., Rachman, O.: Atomic snapshots using lattice agreement. Distrib.Comput.8,121-132 (1995)
7. Attiya, H., Herlihy, M., Rachman, O.: Atomic snapshots using lattice agreement. Distrib.Comput.8,121-132 (1995)
8. Attiya, H., Rachman, O.: Atomic snapshots in O(n log n) operations. SIAM J. Comput. 27, 319-340 (1998)
8. Attiya, H., Rachman, O.: Atomic snapshots in O(n log n) operations. SIAM J. Comput. 27, 319-340 (1998)
9. Ellen, F., Fatourou, P., Ruppert, E.: Time lower bounds for implementations of multi-writer snapshots. J. Assoc. Comput. Mach. 54(6) article 30 (2007)
9. Ellen, F., Fatourou, P., Ruppert, E.: Time lower bounds for implementations of multi-writer snapshots. J. Assoc. Comput. Mach. 54(6) article 30 (2007)
10. Fatourou, P., Kallimanis, N.D.: Single-scanner multi-writer snapshot implementations are fast! In: Proc. 25th ACM Symposium on Principles of Distrib. Comput. Colorado, July 2006 pp. 228-237. ACM, New York (2006)
10. Fatourou, P., Kallimanis, N.D.: Single-scanner multi-writer snapshot implementations are fast! In: Proc. 25th ACM Symposium on Principles of Distrib. Comput. Colorado, July 2006 pp. 228-237. ACM, New York (2006)
11. Fich, F.E.: How hard is it to take a snapshot? In: SOFSEM 2005: Theory and Practice of Computer Science. Liptovsky Jan, January 2005, LNCS, vol. 3381, pp. 28-37. Springer (2005)
11. Fich, F.E.: How hard is it to take a snapshot? In: SOFSEM 2005: Theory and Practice of Computer Science. Liptovsky Jan, January 2005, LNCS, vol. 3381, pp. 28-37. Springer (2005)
12. Guerraoui,  R.,  Ruppert,  E.: Anonymous  and  fault-tolerant shared-memory computing. Distrib. Comput. 20(3) 165-177 (2007)
12. Guerraoui,  R.,  Ruppert,  E.: Anonymous  and  fault-tolerant shared-memory computing. Distrib. Comput. 20(3) 165-177 (2007)
13. Jayanti, P.: An optimal multi-writer snapshot algorithm. In: Proc. 37th ACM Symposium on Theory of Computing. Baltimore, May 2005, pp. 723-732. ACM, New York (2005)
13. Jayanti, P.: An optimal multi-writer snapshot algorithm. In: Proc. 37th ACM Symposium on Theory of Computing. Baltimore, May 2005, pp. 723-732. ACM, New York (2005)
14. Kirousis, L.M., Spirakis, P., Tsigas, P.: Simple atomic snapshots: A linear complexity solution with unbounded time-stamps. Inf. Process. Lett. 58,47-53 (1996)
14. Kirousis, L.M., Spirakis, P., Tsigas, P.: Simple atomic snapshots: A linear complexity solution with unbounded time-stamps. Inf. Process. Lett. 58,47-53 (1996)
15. Mostefaoui, A., Rajsbaum, S., Raynal, M., Roy, M.: Condition-based consensus solvability: a hierarchy of conditions and efficient protocols. Distrib. Comput. 17,1 -20 (2004)
15. Mostefaoui, A., Rajsbaum, S., Raynal, M., Roy, M.: Condition-based consensus solvability: a hierarchy of conditions and efficient protocols. Distrib. Comput. 17,1 -20 (2004)
16. Riany, Y., Shavit, N., Touitou, D.: Towards a practical snapshot algorithm. Theor. Comput. Sci. 269,163-201 (2001)
16. Riany, Y., Shavit, N., Touitou, D.: Towards a practical snapshot algorithm. Theor. Comput. Sci. 269,163-201 (2001)
[[Категория: Совместное определение связанных терминов]]
Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/15480...15656