Ласло Белади

Ласло Белади (венг. Belády László; 29 апреля 1928, Будапешт — 6 ноября 2021, там же) — венгерский и американский учёный в области информатики, известный прежде всего работами по управлению виртуальной памятью и теории алгоритмов. Один из создателей алгоритма замещения страниц, названного его именем (алгоритм Белади), а также автор парадокса Белади.

Биография

Ласло Белади родился в Будапеште в 1928 году. В 1952 году окончил Будапештский университет технологии и экономики (BME) по специальности «инженер-строитель». После окончания университета работал в Научно-исследовательском институте транспорта (Közlekedéstudományi Kutató Intézet), где занимался вопросами автоматизации проектирования дорог и мостов.

В 1956 году, после подавления Венгерского восстания, Белади эмигрировал в США. Первоначально работал в компании General Motors, затем перешёл в исследовательскую лабораторию IBM в Йорктаун-Хайтс (штат Нью-Йорк). В IBM он проработал с 1961 по 1994 год, дослужившись до должности ведущего научного сотрудника (IBM Fellow).

В 1960-х годах Белади получил степень магистра (1960) и доктора философии (1963) по математике в Нью-Йоркском университете. Его диссертация была посвящена теории графов и её приложениям в компьютерных науках.

После выхода на пенсию в 1994 году Белади вернулся в Венгрию, где продолжил научную деятельность в качестве почётного профессора Будапештского университета технологии и экономики. Скончался 6 ноября 2021 года в возрасте 93 лет.

Научные достижения

Алгоритм замещения страниц Белади

Наиболее известная работа Белади — алгоритм замещения страниц, разработанный в 1966 году совместно с Робертом Нельсоном и Джеральдом Шедлером. Алгоритм, получивший название «алгоритм Белади» (Belady’s algorithm), является оптимальным алгоритмом замещения страниц, минимизирующим количество страничных ошибок при условии полного знания будущих обращений к памяти.

Алгоритм работает следующим образом: при необходимости загрузить новую страницу в память, из всех страниц, находящихся в оперативной памяти, выбирается та, обращение к которой произойдёт позже всего. Этот алгоритм является теоретическим эталоном для сравнения с другими алгоритмами замещения (например, LRU, FIFO).

Парадокс Белади

В 1969 году Белади обнаружил и описал явление, получившее название «парадокс Белади» (Belady’s anomaly). Парадокс заключается в том, что при использовании некоторых алгоритмов замещения страниц (в частности, FIFO) увеличение количества доступных страниц памяти может привести к увеличению числа страничных ошибок.

Этот парадокс имеет важное практическое значение, так как демонстрирует, что простое увеличение объёма оперативной памяти не всегда улучшает производительность системы, если используется неоптимальный алгоритм замещения. Парадокс также стимулировал разработку более совершенных алгоритмов, таких как LRU (Least Recently Used) и LFU (Least Frequently Used), которые не подвержены этому эффекту.

Другие работы

Помимо работ по управлению памятью, Белади внёс вклад в следующие области:

• Теория графов: разработка алгоритмов для поиска кратчайших путей и минимальных остовных деревьев.
• Анализ производительности вычислительных систем: методы моделирования и оценки производительности компьютерных систем.
• Операционные системы: исследования по организации виртуальной памяти, файловых систем и планирования процессов.
• Компьютерная архитектура: работы по кэшированию и организации памяти в многопроцессорных системах.

Награды и признание

• Член Ассоциации вычислительной техники (ACM Fellow) с 1994 года.
• IBM Fellow (1973) — высшее техническое звание в компании IBM.
• Премия имени Джона фон Неймана от IEEE (1995) за вклад в теорию и практику управления памятью.
• Почётный доктор Будапештского университета технологии и экономики (1993).

Публикации

Ласло Белади является автором более 80 научных статей и нескольких книг. Наиболее значимые публикации:

• Belady L. A. A study of replacement algorithms for a virtual-storage computer // IBM Systems Journal. — 1966. — Vol. 5, № 2. — P. 78–101.
• Belady L. A., Nelson R. A., Shedler G. S. An anomaly in space-time characteristics of certain programs running in a paging machine // Communications of the ACM. — 1969. — Vol. 12, № 6. — P. 349–353.
• Belady L. A., Lehman M. M. A model of large program development // IBM Systems Journal. — 1976. — Vol. 15, № 3. — P. 225–252.

Влияние на информатику

Работы Белади оказали значительное влияние на развитие операционных систем и систем управления памятью. Алгоритм Белади до сих пор используется как теоретический эталон при оценке эффективности алгоритмов замещения страниц, а парадокс Белади является классическим примером, демонстрирующим неочевидные свойства компьютерных систем.

Исследования Белади также заложили основы для дальнейших работ в области виртуальной памяти, которые привели к созданию современных операционных систем, таких как Linux, Windows и macOS, использующих различные варианты алгоритмов, свободных от парадокса Белади.

Источники

• Belady L. A. A study of replacement algorithms for a virtual-storage computer // IBM Systems Journal. — 1966.
• Belady L. A., Nelson R. A., Shedler G. S. An anomaly in space-time characteristics of certain programs running in a paging machine // Communications of the ACM. — 1969.
• Tanenbaum A. S. Modern Operating Systems. — 4th ed. — Pearson, 2014.
• Silberschatz A., Galvin P. B., Gagne G. Operating System Concepts. — 10th ed. — Wiley, 2018.
• Некролог Ласло Белади на сайте Будапештского университета технологии и экономики, 2021.