Введение в распределенные


Методы эффективной реализации векторных часов 82



Download 3,3 Mb.
bet3/74
Sana13.07.2022
Hajmi3,3 Mb.
#785639
1   2   3   4   5   6   7   8   9   ...   74
Bog'liq
Косяков ТАТ книга

Методы эффективной реализации векторных часов 82

  1. Дифференциальная пересылка векторного времени 83

  2. Часы, фиксирующие прямую зависимость 85

  3. Адаптивный метод Жарда-Жордана 90

  • Матричное время 93

    1. Основные свойства 95

    Раздел 4. Взаимное исключение в распределенных системах 96

      1. Общие концепции 96

      2. Централизованный алгоритм 101

      3. Алгоритмы на основе получения разрешений 103

        1. Алгоритм Лэмпорта 103

        2. Алгоритм Рикарта-Агравала 109

        3. Алгоритм обедающих философов 114

      4. Алгоритмы на основе передачи маркера 132

        1. Широковещательный алгоритм Сузуки-Касами 133

        2. Алгоритм Реймонда на основе покрывающего дерева 138

    Список литературы 152
    Основная литература 152
    Дополнительная литература 152
  • ВВЕДЕНИЕ


    Сегодняшние реалии таковы, что разработка практически любого программного обеспечения требует хороших знаний параллельного и распределенного программирования. Обе эти области объединяет то, что и параллельное, и распределенное программное обеспечение состоит из нескольких процессов, которые вместе решают одну общую задачу.


    Однако отметим, что понятия параллельной и распределенной обработки данных не являются эквивалентными. Действительно, параллелизм подразумевает одновременное существование и выполнение задач. Распределение же обозначает территориальную удаленность процессов друг от друга. При этом задачи, связанные с распределенной обработкой данных, могут выполняться несколькими последовательными этапами в различные периоды времени. Конечно, в некоторых случаях, параллельная обработка данных может быть эффективно реализована с помощью распределенного программного обеспечения, особенно, при проведении большого объема вычислений, слабо связанных между собой. Поэтому можно сказать, что в общем случае распределенная обработка данных не подразумевает параллелизма, но возможность "параллельного использования" распределенных вычислительных систем существует.
    Также обратим внимание, что для совместной работы процессов им необходим некоторый механизм взаимодействия. В мире параллельных систем обычно считается, что взаимодействие процессов обеспечивается с помощью разделяемых переменных. В этом случае один процесс осуществляет запись в одну из таких переменных, а другой – считывает записанное значение. В свою очередь в распределенных системах процессы взаимодействуют путем пересылки сообщений. Поэтому для обмена данными или координации совместных действий процессы должны использовать механизмы отправки и приема сообщений.
    В настоящее время имеется немало книг, посвященных вопросам параллельного программирования. Тем не менее, по мнению автора, ощущается определенный недостаток в русскоязычной литературе, знакомящей читателей с основными проблемами в области распределенной обработки данных и существующими подходами к их решению. Среди известных автору источников по данной тематике можно выделить переводы книги Э. Таненбаума [2, 6] и монографии Ж. Теля [3, 7]. В книге Э. Таненбаума основное внимание уделяется архитектуре и технологиям построения распределенных систем, а не распределенным алгоритмам, в сущности, образующим ядро практически любого распределенного программного обеспечения. Поэтому, на взгляд автора, эта книга в большей степени ориентирована на инженеров-практиков, нежели на теоретиков, изучающих фундаментальные принципы и модели,
    лежащие в основе всех распределенных систем. В свою очередь монография Ж. Теля посвящена преимущественно распределенным алгоритмам. Материал монографии излагается математическим языком, исследование особенностей распределенной обработки данных проводится на основе понятия системы переходов. Все утверждения и теоремы, приведенные в книге, сопровождаются строгими формальными доказательствами. Как следствие, подобный уровень изложения материала требует от читателя определенной начальной подготовки и, не исключено, что может отпугнуть молодого специалиста, только начинающего изучение распределенных алгоритмов и принципов работы распределенных систем.
    В этой связи автор ставил своей целью написание учебного пособия, направленного на изучение фундаментальных аспектов организации распределенной обработки данных и ориентированного на неподготовленного читателя. С этой же целью описание модели распределенного вычисления и доказательство всех утверждений проводится до определенной степени неформально, но на уровне, достаточном для понимания существенных особенностей функционирования распределенных систем, выделяющих их среди систем других классов.
    Материал учебного пособия следует рассматривать в качестве введения в проблематику распределенных вычислений. В пособии представлено несколько базовых понятий, концепций и алгоритмов, которые послужат основой для дальнейшего изучения предмета распределенных вычислений заинтересованными студентами. В первом разделе обсуждаются цели и задачи распределенных систем, а также сложности их разработки. Во втором разделе представлена модель распределенного вычисления, используемая при дальнейшем изложении. Кроме того, не опираясь на понятие единого физического времени, вводится отношение "произошло раньше", связывающее события процессов между собой. В третьем разделе рассматриваются различные механизмы логических часов, позволяющие упорядочивать события в одну или несколько последовательностей, которые могли бы происходить в системе, и, как следствие, значительно упрощающие разработку алгоритмов для распределенных систем. Четвертый раздел посвящен изучению основных распределенных алгоритмов взаимного исключения, ключевые идеи которых используются и для решения многих других задач в распределенных системах. Представленный в пособии список литературы содержит перечень источников, которые автор рекомендует в первую очередь для получения более подробной информации по рассматриваемым и дополнительным вопросам из области распределенных вычислений [1-7] и материал из которых в той или иной степени был использован при написании данного пособия [1-30].
    Учебное пособие предназначено, прежде всего, для студентов, обучающихся по направлению "Информатика и вычислительная техника" и "Программная инженерия", изучающих дисциплину "Распределенные вычисления" и связанные с ней дисциплины. Пособие может быть полезно для специалистов в области информатики, вычислительной техники и программирования в качестве введения в проблематику распределенных вычислений.
    Автор понимает, что, как и "в любой хорошо отлаженной программе всегда есть хотя бы одна ошибка", так и в любой многократно вычитанной книге она также наверняка присутствует. Поэтому автор будет благодарен за все присланные по адресу mkosyakov@gmail.com обнаруженные ошибки и опечатки, а также критические замечания.

    Download 3,3 Mb.

    Do'stlaringiz bilan baham:
    1   2   3   4   5   6   7   8   9   ...   74




    Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©www.hozir.org 2024
    ma'muriyatiga murojaat qiling

    kiriting | ro'yxatdan o'tish
        Bosh sahifa
    юртда тантана
    Боғда битган
    Бугун юртда
    Эшитганлар жилманглар
    Эшитмадим деманглар
    битган бодомлар
    Yangiariq tumani
    qitish marakazi
    Raqamli texnologiyalar
    ilishida muhokamadan
    tasdiqqa tavsiya
    tavsiya etilgan
    iqtisodiyot kafedrasi
    steiermarkischen landesregierung
    asarlaringizni yuboring
    o'zingizning asarlaringizni
    Iltimos faqat
    faqat o'zingizning
    steierm rkischen
    landesregierung fachabteilung
    rkischen landesregierung
    hamshira loyihasi
    loyihasi mavsum
    faolyatining oqibatlari
    asosiy adabiyotlar
    fakulteti ahborot
    ahborot havfsizligi
    havfsizligi kafedrasi
    fanidan bo’yicha
    fakulteti iqtisodiyot
    boshqaruv fakulteti
    chiqarishda boshqaruv
    ishlab chiqarishda
    iqtisodiyot fakultet
    multiservis tarmoqlari
    fanidan asosiy
    Uzbek fanidan
    mavzulari potok
    asosidagi multiservis
    'aliyyil a'ziym
    billahil 'aliyyil
    illaa billahil
    quvvata illaa
    falah' deganida
    Kompyuter savodxonligi
    bo’yicha mustaqil
    'alal falah'
    Hayya 'alal
    'alas soloh
    Hayya 'alas
    mavsum boyicha


    yuklab olish