- •1. Операционная система и ее основные функции
- •2. Основные этапы развития ос Первый период (1945–1955 гг.). Операционных систем нет
- •Второй период (1955 г.–начало 60-х). Пакетные операционные системы
- •Третий период (начало 60-х – 1980 г.). Компьютеры на основе интегральных микросхем. Первые многозадачные ос
- •Четвертый период (с 1980 г. По настоящее время). Персональные компьютеры. Классические, сетевые и распределенные системы
- •3. Классификация операционных систем
- •4. Принцип модульности при построении ос
- •5. Принцип особого режима работы при построении ос
- •6. Принцип виртуализации при построении ос
- •7. Принцип мобильности при построении ос
- •8. Принцип совместимости при построении ос
- •9. Принцип генерируемости при построении ос
- •10. Принцип открытости при построении ос
- •11. Принцип обеспечения безопасности вычислений при построении ос
- •12. Макроядерная структура операционных систем
- •13. Микроядерная структура операционных систем
- •14. Среды и оболочки операционных систем
- •15. Понятие потока, процесса, задачи Понятия «процесс» и «поток»
- •16. Понятие прерывания, исключительной ситуации
- •17. Функции ос по управлению памятью. Простейшие схемы управления памятью.
- •Простейшие схемы управления памятью
- •18. Управление памятью. Схема с фиксированными разделами
- •Один процесс в памяти
- •Оверлейная структура
- •Динамическое распределение. Свопинг
- •19. Управление памятью. Схема с переменными разделами
- •20. Управление памятью. Страничная организация памяти Страничная память
- •21. Управление памятью. Сегментная организация памяти
- •22. Прерывание. Обработка прерываний. Исключительные ситуации
- •Обработка прерываний и ошибок
- •23. Управление вводом-выводом в ос. Разделяемые и неразделяемые ресурсы Структура системы ввода-вывода
- •24. Буферизация и кэширование Буферизация и кэширование
- •25. Понятие спулинга, его назначение Spooling и захват устройств
- •26. Алгоритмы планирования запросов к жесткому диску. Алгоритм fcfs Алгоритмы планирования запросов к жесткому диску
- •Алгоритм First Come First Served (fcfs)
- •27. Алгоритмы планирования запросов к жесткому диску. Алгоритм sstf Алгоритмы планирования запросов к жесткому диску
- •Алгоритм Short Seek Time First (sstf)
- •28. Алгоритмы планирования запросов к жесткому диску. Алгоритм sсan и look Алгоритмы планирования запросов к жесткому диску
- •Алгоритмы сканирования (scan, look)
- •29. Управление процессами. Основные состояния процесса
- •Состояния процесса
- •30. Планирование процессов (задач). Алгоритмы планирования
- •31. Дисциплина диспетчеризации процессов (задач) fcfs
- •32. Дисциплина диспетчеризации процессов (задач) rr
- •33. Проблемы организации параллельных вычислений.
- •34. Тупиковые ситуации и способы их разрешения.
- •Способы предотвращения тупиков
- •Способы предотвращения тупиков путем тщательного распределения ресурсов. Алгоритм банкира
- •Предотвращение тупиков за счет нарушения условий возникновения тупиков Нарушение условия взаимоисключения
- •Нарушение условия ожидания дополнительных ресурсов
- •Нарушение принципа отсутствия перераспределения
- •Hарушение условия кругового ожидания
- •35. Страничная недостаточность («голодание» процессора) и ее обработка
- •36. Файловая система. Основные функции файловой системы
- •37. Простейшая таблица оглавления тома и её элементы
- •38. Логическая структура разделов диска на примере ibm- и ms-совместимых файловых систем
33. Проблемы организации параллельных вычислений.
Обычный подход при организации вычислений для подобных систем – создание новых параллельных версий на основе обычных последовательных программ, в которых или автоматически компилятором, или непосредственно программистом выделяются участки независимых друг от друга вычислений. Возможности автоматического анализа программ для порождения параллельных вычислений достаточно ограничены, и второй подход является преобладающим. При этом для разработки параллельных программ могут применяться как новые алгоритмические языки, ориентированные на параллельное программирование, так и уже имеющиеся языки программирования, расширенные некоторым набором операторов для параллельных вычислений.
Первый вариант параллельного алгоритма Гаусса – Зейделя
Как следует из текста программы, параллельные области в данном примере задаются директивой parallel for, являются вложенными и включают в свой состав операторы цикла for. Компилятор, поддерживающий технологию OpenMP, разделяет выполнение итераций цикла между несколькими потоками программы, количество которых обычно совпадает с числом процессоров в вычислительной системе. Параметры директивы shared и private определяют доступность данных в потоках программы – переменные, описанные как shared, являются общими для потоков, для переменных с описанием private создаются отдельные копии для каждого потока, которые могут использоваться в потоках независимо друг от друга.
Наличие общих данных обеспечивает возможность взаимодействия потоков. В этом плане разделяемые переменные могут рассматриваться как общие ресурсы потоков, и, как результат, их применение должно выполняться с соблюдением правил взаимоисключения (изменение каким-либо потоком значений общих переменных должно приводить к блокировке доступа к модифицируемым данным для всех остальных потоков). В данном примере таким разделяемым ресурсом является величина dmax, доступ потоков к которой регулируется специальной служебной переменной (замком) dmax_lock и функциями omp_set_lock (разрешение или блокировка доступа) и omp_unset_lock (снятие запрета на доступ). Подобная организация программы гарантирует единственность доступа потоков для изменения разделяемых данных. Участки программного кода (блоки между обращениями к функциям omp_set_lock и omp_unset_lock ), для которых обеспечивается взаимоисключение, обычно именуются критическими секциями.
Второй вариант параллельного алгоритма Гаусса – Зейделя
Как результат выполненного изменения схемы вычислений, количество обращений к общей переменной dmax уменьшается с N2 до N раз, что должно приводить к существенному снижению затрат на синхронизацию потоков и уменьшению проявления эффекта сериализации вычислений. Результаты экспериментов с данным вариантом параллельного алгоритма, приведенные в табл. 11.1, показывают существенное изменение ситуации – ускорение в ряде экспериментов оказывается даже большим, чем используемое количество процессоров (такой эффект сверхлинейного ускорения достигается за счет наличия у каждого из процессоров вычислительного сервера своей быстрой кэш-памяти). Следует также обратить внимание, что улучшение показателей параллельного алгоритма достигнуто при снижении максимально возможного параллелизма (для выполнения программы может использоваться не более N процессоров).