Разрабатываем алгоритмы действий и создаем блок-схемы. Алгоритм работы программы

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

Инструкция

Как правило, вначале алгоритма производится ввод исходных данных для решения поставленной задачи. Нарисуйте параллелограмм ниже линии так, чтобы он непрерывным продолжением схемы. В параллелограмме напишите производимое действие, обычно это операции данных с экрана (Read nInp) или других устройств. Важно, что введенные вами переменных в данном шаге будут использоваться в дальнейшем во всем теле блок-схемы.

Выполнение одной или группы операций, любая обработка данных (изменение значения или формы представления) обозначается в виде прямоугольника. Нарисуйте данную фигуру в нужном месте алгоритма при составлении блок-схемы. Внутри прямоугольника запишите производимые действия , например, операция присваивания записывается следующим образом: mOut = 10*nInp b + 5. Далее также для продолжения блок-схемы нарисуйте линию вниз.

Важной составляющей любого алгоритма и соответственно блок-схемы являются условные и цикличные операторы. У данных операторов один вход и два и или более альтернативных выхода. После вычисления условия, заданного оператором, дальнейший переход осуществляется лишь по одному пути. Нарисуйте вход в элемент в виде линии входящей в верхнюю вершину элемента.

Для задания оператора условия нарисуйте от данной линии ромб. Внутри фигуры укажите само условие и проведите линии, указывающие дальнейший переход в зависимости от его выполнения. Условие задается в общем случае операциями сравнения (>, <, =). Переход по линии вниз осуществляется при истинном условии, назад – при ложном. Укажите около выходных линий фигуры результаты условия (true, false). Невыполнение условия (false) возвращает к определенному шагу выше по телу алгоритма. Проведите линии под прямым углом от выхода с условия и до нужного оператора.

). Разработка программы с помощью такой системы программирования состоит из двух этапов: 1) создание в визуальном режиме элементов графического интерфейса программы; 2) разработка программного кода. Такой подход существенно облегчает создание программ, так как разработка графического интерфейса вручную (в процедурных языках) сложный и трудоёмкий процесс.

Первый шаг к пониманию важности изучения и знания алгоритмов это дать точное определение тому, что понимается под алгоритмом. Алгоритм в программировании- это понятная и точная последовательность действий , записанных на языке программирования.Согласно популярной книге Алгоритмы: построение и анализ (Кормен, Лейзерсон, Ривест, Штайн)"алгоритм (algorithm) - это любая корректно определенная вычислительная процедура, на вход (input) которой подается некоторая величина или набор величин, и результатом выполнения которой является выходная (output) величина или набор значений". Другими словами, алгоритмы похожи на дорожные карты для достижения четко определенной цели. Код, для вычисления членов последовательности Фибоначчи - это реализация конкретного алгоритма. Даже простая функция сложения двух чисел является алгоритмом, хотя и простым.

Для создания алгоритма (программы) необходимо знать:

полный набор исходных данных задачи (начальное состояние объекта);

цель создания алгоритма (конечное состояние объекта);

систему команд исполнителя (то есть набор команд, которые исполнитель понимает и может выполнить).

Полученный алгоритм (программа) должен обладать следующим набором свойств:

дискретность (алгоритм разбит на отдельные шаги - команды);

однозначность (каждая команда определяет единственно возможное действие исполнителя);

понятность (все команды алгоритма входят в систему команд исполнителя);

результативность (исполнитель должен решить задачу за конечное число шагов).

Большая часть алгоритмов обладает также свойством массовости (с помощью одного и того же алгоритма можно решать множество однотипных задач).

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

Язык программирования - набор правил записи алгоритмических структур и данных.

Анализ времени выполнения алгоритма

Одним из наиболее важных аспектов алгоритма является его скорость. Часто бывает легко придумать алгоритм решающий задачу, но если алгоритм слишком медленный, то он возвращается на доработку. Поскольку точная скорость алгоритма зависит от того где запускается алгоритм, а также деталей реализации, компьютерные специалисты обычно говорят о времени выполнения относительно входных данных. Например, если вход состоит из N целых чисел, то алгоритм может иметь время выполнения пропорциональное N 2 , что представляется как O(N 2). Это означает, что если вы запустите реализацию алгоритма на компьютере с входом размером в N, то это займет C*N 2 секунд, где C-некоторая константа, которая не меняется с изменением размера входа.

Тем не менее, время выполнения многих сложных алгоритмов зависит не только от размера входных данных, но и от множества других факторов. Например, алгоритм сортировки множества целых чисел может работать намного быстрее, если это множество уже отсортировано. Принято говорить о наихудшем случае выполнения, и среднем случае выполнения. Наихудшее время выполнения - это максимальное время работы алгоритма при самом "плохом" из всех возможных входов. Средний случай выполнения - это среднее время работы алгоритма на всех возможных входах. Из этих двух типов времени выполнения, легче всего рассуждать о наихудшем случае и поэтому его используют чаще в качестве эталона для заданного алгоритма. Процесс определения наихудшего и среднего случая времени выполнения алгоритма может быть достаточно сложным, т.к. обычно невозможно запустить алгоритм для всех возможных входов.

Выше отмечалось, что один и тот же алгоритм может быть записан по-разному. Можно записывать алгоритм естественным языком. В таком виде мы используем рецепты, инструкции и т.п. Для записи алгоритмов, предназначенных формальным исполнителям, разработаны специальные языки программирования . Любой алгоритм можно описать графически в виде блок-схемы . Для этого разработана специальная система обозначений:

Приведем пример описания алгоритма суммирования двух величин в виде блок-схемы:

Такой способ описания алгоритм наиболее нагляден и понятен человеку. Поэтому, алгоритмы формальных исполнителей обычно разрабатывают сначала в виде блок-схемы, и только затем создают программу на одном из языков программирования .

Сортировка

Сортировка является хорошим примером алгоритма, который часто используется программистами. Самый простой способ отсортировать группу элементов это начать с удаления наименьшего элемента из группы, и поставить его первым. Затем удаляется второй по величине элемент и ставится вторым и т.д. К сожалению, время работы этого алгоритма составляет O(N 2), а это означает, что потребуется количество времени пропорциональное количеству элементов в квадрате. Если бы нам пришлось сортировать млрд. элементов, то этот алгоритмы бы потребовал 10 18 операций. Если считать что обычные настольные ПК делают примерно 10 9 операций в секунду, то потребуются годы чтобы закончить сортировку этого млрд. элементов.

К счастью существует ряд более совершенных алгоритмов, например, быстрая сортировка (quicksort), пирамидальная сортировка (heapsort) и сортировка слияния(mergesort). Эти алгоритмы имеют время выполнения O(N * Log(N)). Таким образом, число операций необходимых для сортировки млрд. элементов сокращается до таких разумных пределов, что даже самый дешевый настольный ПК способен провести такую сортировку. Вместо млрд. в квадрате операций (10 18) эти алгоритмы требуют только 10 млрд. операций (10 10), т.е. в 100 млн. раз быстрее.

Кратчайший путь

Алгоритмы поиска кратчайшего пути из одной точки в другую исследуются уже на протяжении многих лет. Примеров прикладного применения этих алгоритмов предостаточно, однако для простоты изложения будем придерживаться следующей постановки: требуется найти кратчайший путь из точки А в точку Б в городе с несколькими улицами и перекрестками. Существует много разных алгоритмов для решения этой задачи и все они со своими преимуществами и недостатками. Прежде чем мы углубимся в их изучение, давайте рассмотрим время выполнения простого алгоритма перебором. Если алгоритм рассматривает каждый возможный путь от А до Б (который не образует циклов) он вряд ли закончится при нашей жизни, даже если А и Б находятся в маленьком городке. Время выполнения этого алгоритма является экспоненциальным, что обозначается как O(C N) для некоторого C. Даже для малых значений C, C N становится астрономическим числом, когда N принимает умеренно большое значение.

Один из самых быстрых алгоритмов для решения этой задачи имеет время выполненияO(E+V*Log(V)), где E число дорожных сегментов, а V число пересечений. Алгоритм займет около 2 секунд времени, для поиска кратчайшего пути в городе из 10000 пересечений и 20000 дорожных сегментов (обычно бывает около 2 дорожных сегментов на одно пересечение). Этот алгоритм известен как алгоритм Дейкстры, он является довольно таки сложным и требует использования структуры данных очередь с приоритетом (priority queue). Однако в некоторых случаях даже такое время выполнения является слишком медленным (взять например нахождение кратчайшего пути от Нью-Йорка до Сан-Франциско - в США есть миллионы пересечений), в таких случаях программисты пытаются улучшить время выполнения с помощью так называемой эвристики. Эвристика - это приближенное значение чего-то, что имеет отношение к задаче. В задаче поиска кратчайшего пути, например, может оказаться полезным знать, как далеко находится точка от пункта назначения. Зная это можно разработать более быстрый алгоритм (например алгоритм поиска А* в некоторых случаях работает значительно быстрее чем алгоритм Дейкстры). Такой подход не всегда улучшает время выполнения алгоритма в наихудшем случае, но в большинстве реальных приложений алгоритм начинает работать быстрее.

Приближенные алгоритмы

Иногда даже самый продвинутый алгоритм с самой продвинутой эвристикой работает слишком медленно на самом быстром компьютере. В таких случаях приходится снижать точность конечного результата. Вместо того чтобы пытаться получить кратчайший путь, можно ограничиться путем, который например на 10% больше чем кратчайший путь.

На самом деле есть немало важных задач, для которых известные на сегодня алгоритмы выдают оптимальный результат слишком медленно. Наиболее известная группа из этих задач называется NP (non-deterministic polynomial). Если задача называется NP-полной или NP-трудной, то это означает, что никто не знает достаточно хорошего способа для получения оптимального решения. Кроме того, если кто-то разработает эффективный алгоритм для решения одной NP-трудной задачи, то этот алгоритм можно будет применить ко всем NP-трудным задачам.

Хорошим примером NP-трудной задачи является задача коммивояжёра. Продавец хочет посетить N городов, и он знает, сколько времени занимает перемещение из одного города в другой. Вопрос в том насколько быстро он сможет посетить все города? Самый быстрый из известных алгоритмов для решения этой задачи является слишком медленным - и многие считают, что так будет всегда - поэтому программисты ищут достаточно быстрые алгоритмы, дающие хорошее решение, но часто не оптимальное.

Случайные алгоритмы

Еще один подход, применяемый для решения некоторых задач, заключается в том, чтобы сделать алгоритм случайным. Данный подход не улучшает время алгоритма в худшем случае, но довольно часто хорошо работает в среднем случае. Алгоритм быстрой сортировки является хорошим примером использования рандомизации. В худшем случае, алгоритм быстрой сортировки сортирует группу элементов за O(N 2), где N количество элементов. Если в этом алгоритме использовать рандомизацию, то шансы на худший случай становятся незначительно малыми, и в среднем случае алгоритм быстрой сортировки работает за время O(N*Log(N)). Другие алгоритмы даже в худшем случае гарантируют время работы O(N*Log(N)), однако они медленнее в среднем случае. Хотя оба алгоритма имеют время работы пропорциональное N*Log(N), алгоритм быстрой сортировки имеет более меньший постоянный коэффициент (constant factor) - т.е. он требует C*N*Log(N), в то время как другие алгоритмы требуют более 2*C*N*Log(N) операций.

Другой алгоритм, использующий случайные числа ищет медиану для группы чисел и его время работы в среднем случае составляет O(N). Это намного быстрее по сравнению с алгоритмом, который сортирует числа и выбирает среднее, и работает за O(N*Log(N)). Существуют детерминированные алгоритмы (не случайные) которые позволяют найти медиану за время O(N), однако случайный алгоритм проще для понимания и часто работает быстрее этих детерминированных алгоритмов.

Основная идея алгоритма поиска медианы это выбрать среди чисел случайное, и посчитать, сколько чисел в группе меньше чем выбранное число. Допустим, есть N чисел, K из них меньше или равно выбранному числу. Если K меньше чем половина N, тогда мы знаем что медиана это (N/2-K)-е число которое больше чем случайно выбранное число, так что мы отбрасываем K чисел меньших или равных случайному числу. Теперь допустим мы хотим найти (N/2-K)-е наименьшее число, вместо медианы. Алгоритм такой же, мы просто случайно выбираем число и повторяем описанные шаги.

Сжатие

Еще один класс алгоритмов предназначен для сжатия данных. Этот алгоритм не имеет ожидаемого результата (как например, алгоритм сортировки), но вместо этого делается оптимизация по некоторым критериям. В случае сжатия данных, алгоритм (например, LZW) пытается сделать так чтобы данные занимали как можно меньше байтов, но в то же время, чтобы можно было распаковывать их до первоначальной формы. В некоторых случаях этот тип алгоритмов использует те же методы что и другие алгоритмы, что приводит к хорошему результату, но неоптимальному. Например, JPG и MP3 сжимают данные таким образом, что конечный результат получается более низкого качества, чем оригинал, однако и размер меньше. MP3 сжатие не сохраняет каждую особенность оригинального аудио файла, но пытается сохранить достаточно деталей, чтобы обеспечить приемлемое качество и в то же время значительно сократить размер файла. Формат JPG следует тому же принципу, но детали существенно отличаются, т.к. целью является сжатие изображения, а не аудио.

Зачем нужно знать всякие алгоритмы

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

Конечно, будут моменты, когда вы будете натыкаться на ранее не изучавшиеся проблемы. В таких случаях нужно придумать новый алгоритм, или по-новому применить старый алгоритм. Чем больше вы знаете об алгоритмах, тем больше у вас шансов найти хорошее решение проблемы. Во многих случаях новая задача легко сводится к старой, но для этого нужно иметь фундаментальное понимание старых задач.

В качестве примера можно рассмотреть, как работают сетевые коммутаторы. Коммутатор имеет N подключенных к нему кабелей, и принимает пакет данных, поступающих по этим кабелям. Коммутатор должен сначала проанализировать пакеты, а затем отправить их обратно по правильному кабелю. Коммутатор также как и компьютер работает в дискретном режиме - пакеты отправляются дискретными интервалами, а не непрерывно. Быстрый коммутатор стремится послать, как можно больше пакетов в течение каждого интервала иначе они накопятся и коммутатор "упадет". Цель алгоритма отправлять максимальное количество пакетов в течение каждого интервала, а также обеспечить порядок, при котором пакеты, пришедшие раньше других отправлялись тоже раньше других. В этом случае оказывается, что для решения этой задачи подходит алгоритм известный как "stable matching", хотя на первый взгляд это может быть не очевидно. Такие связи между задачей и решением можно обнаружить только с помощью уже имеющихся алгоритмических знаний.

Реальные примеры

Примеров решений реальных задач требующих новейших алгоритмов предостаточно. Почти все, что вы делаете на компьютере зависит от алгоритмов, которые кто-то очень долго разрабатывал. Даже самых простых программ не существовало бы без алгоритмов, которые работают "за сценой" управляя памятью и загружая данные с жесткого диска.

Существуют десятки примеров применения сложных алгоритмов, но обсудим две задачи, решение которых требует таких же навыков, как для решения некоторых задач на TopCoder. Первая задача известна как задача о максимальном потоке, а вторая связана с динамическим программированием - методом который часто позволяет решать задачи с казалось бы невозможной молниеносной скоростью.

Алгоритм поиска максимального потока

Задача поиска максимального потока состоит в том, чтобы посредством имеющейся сети наилучшим образом переместить что-то из одного места в другое. Конкретно такая проблема впервые возникла в 1950-х в связи с железнодорожными путями Советского Союза. США хотели знать, как быстро Советский Союз может подвозить материалы к государствам-сателлитам в Восточной Европе через свою сеть железных дорог.

Кроме того США хотели знать какую часть рельсов можно наиболее легко уничтожить чтобы отрезать государства-сателлиты от остальной части Советского Союза. Оказалось, что эти две задачи тесно связаны и что решение задачи поиска максимального потока также решает задачу о минимальном разрезе, что, в конечном счете, позволит выяснить самый дешевый способ отрезать Советский Союз от своих спутников.

Первый эффективный алгоритм для поиска максимального потока был придуман учеными Фордом и Фалкерсоном. Алгоритм впоследствии был назван алгоритмом Форда - Фалкерсона и является одним из наиболее известных алгоритмов в области компьютерной науки. В последние 50 лет алгоритм претерпел ряд улучшений, что сделало его быстрее (правда, некоторые из этих улучшений устрашают своей сложностью).

Поскольку задача была четко поставлена, обнаружилось множество различных применений. Алгоритм напрямую связан с Интернетом, где важно транспортировать максимум данных из одной точки в другую. Задача также возникает во множестве бизнес-процессов, и является важной частью исследования операций. Например, если есть N сотрудников и N задач, которые должны быть сделаны, но не каждый сотрудник может справиться с каждой задачей, то поиск максимального потока выдаст решение, как назначить N сотрудников на задачи таким образом, чтобы каждая задача была выполнена при условии что это возможно. Задача Graduation из TopCoder SRM 200является хорошим примером задачи на поиск максимального потока.

Сравнение последовательностей

Многим кодерам за всю свою карьеру ни разу не приходилось реализовывать алгоритм, использующий динамическое программирование. Тем не менее, динамическое программирование применяется в ряде важных алгоритмов. Один из алгоритмов это нахождение различий между двумя последовательностями, который большинство программистов наверняка использовали, хотя возможно и не разбирались в нем. Этот алгоритм вычисляет минимальное количество вставок, удалений, редактирований необходимых для преобразования последовательность A в последовательность B.

Например, рассмотрим последовательности "AABAA" и "AAAB". Для преобразования первой последовательности во вторую самое простое, что нужно сделать это удалить B в середине и изменить последнюю A на B. Этот алгоритм имеет множество применений, включая некоторые задачи связанные с ДНК и обнаружением плагиата. Однако многие программисты используют его в основном для сравнения версий одного и того же файла с исходным кодом. Если элементы последовательности это строки в файле, тот этот алгоритм позволяет узнать какие строки надо удалить, вставить, изменить чтобы преобразовать одну версию файла в другую.

Без динамического программирования приходится перебирать экспоненциальное число преобразований, чтобы перейти от одной последовательности к другой. Однако динамическое программирование сокращает время выполнения алгоритма до O(N*M), где N и M количество элементов в двух последовательностях.

Заключение

Сколько существует различных задач, столько существует и различных алгоритмов для их решения. Тем не менее есть большая вероятность того что задача которую вы пытаетесь решить в некотором смысле похожа на другую задачу. Развивая глубокое понимание широкого диапазона алгоритмов, вы сможете выбрать верный алгоритм и применить его для решения задачи. Кроме того решение задач в соревнованиях на TopCoder поможет вам отточить свои навыки в этой области. Многие из этих задач кажутся искусственными и не реалистичными, но они требуют такого, же набора алгоритмических знаний который требуется каждый день в реальном мире.

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

Алгоритм1 -- одно из фундаментальных понятий информатики. Этим словом обозначают точное и безотказное предписание последовательности действий, переводящей автоматическое устройство из исходного состояния в результирующее. Т.е. мы можем считать алгоритмом любую инструкцию, если:

ее команды не допускают различных вариантов исполнения;

указания предусмотрены для всех возможных вариантов развития событий.

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

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

Какими свойствами должен обладать алгоритм? Перечислим их:

дискретность2 -- алгоритм делится на отдельные элементарные шаги;

определенность -- каждая команда однозначно определяет действие исполнителя;

конечность(результативность) -- алгоритм должен завершаться за конечное число шагов.

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

С определенностью непосредственно связана существенная особенность, о которой нельзя забывать: исполнитель выполняет алгоритм формально3, абсолютно не задумываясь над смыслом производимых действий. Поэтому не стоит обижаться на компьютер, "не догадавшийся", что вы подразумевали, -- он честно делает то, что вы написали.

Существует много разных способов записи алгоритмов: графические (например, в виде блок-схем), с помощью естественного языка, какими-нибудь условными знаками идр. Но если мы хотим, чтобы алгоритм был исполнен компьютером, он должен быть обязательно записан на особом языке. Такая запись называется программой4, а язык -- языком программирования.

Вы знаете, что вся информация в компьютере представляется в виде двоичных кодов. В кодах, каждый из которых обозначал одно простейшее действие (вроде, "перенести число из одной ячейки памяти в другую"), приходилось писать и программы для первых ЭВМ. Но это занятие очень сложное и кропотливое, а кроме того, требующее глубокого знания особенностей конкретной машины. Поэтому были придуманы языки программирования высокого уровня. Программа на таком языке -- это последовательность команд, обозначаемых словами естественного языка или их сокращениями. Каждая из них соответствует последовательности из десятков, а то и сотен машинных команд. В результате запись получается гораздо более компактной и понятной.

Но процессор не понимает команд языков высокого уровня, поэтому их предварительно нужно "перевести". Для этого служат особые программы -- трансляторы5.

Сейчас в мире существует множество языков программирования, рассчитанных на различные области применения. Мы в нашем курсе будем использовать Лого6 -- язык, специально созданный для обучения основам программирования. Этот язык очень простой (кстати, в отличие от профессиональных языков программирования, он позволяет записывать команды на русском языке), но, в то же время, способствует формированию навыков, позволяющих затем, при желании, без особых проблем перейти к работе с такими популярными языками, как Си или Паскаль. Особо знаменит язык Лого своей "черепашьей графикой". О том, что это такое, мы и поговорим в следующей главе.

Примечания

Algorithmi (лат.) -- искаженное имя математика IX века аль-Хорезми, предложившего способ выполнения арифметических вычислений с многозначными числами.

Заметим, что подход к определению алгоритма как последовательности операций -- не единственно возможный. Кроме такого -- процедурного (императивного), возможен и функциональный подход, когда алгоритм рассматривается как система функций.

Discrete (англ.) -- состоящий из отдельных частей

Formalis (лат.) -- строго по установленным правилам

Programma (греч.) -- распоряжение

Translator (англ.) -- переводчик

Язык Лого (Logo, от греч. Logos -- слово, мысль) разработан в 1972 г. Сеймуром Пейпертом (Массачусетский Технологический институт, США). "Прародителем" его был наиболее известный из языков функционального программирования -- Лисп, однако, в процессе развития Лого приобрел ряд особенностей, позволяющих использовать при работе с ним как функциональный, так и процедурный подходы.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

1. Алгоритм Деккера и Петерсона

Взаимоисключение - возможность одному процессу приостановить остальные.

Критическая секция - участок кода, в котором должен находиться только один процесс.

1. процесс может войти в свой критический участок тогда и только тогда, когда другие процессы не находятся в своих критических участках

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

3. многие процессы захотят войти в свой критический участок, но это может сделать только один

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

5. процессы вне своих критических участков не должны мешать другим процессам входу в свои критические участки

Собственно алгоритм:

shared int ready = {0,0}; // готовность ко входу

shared int turn; // чья очередь

while (условие) {

ready[i] = 1; // сообщаем о желании войти в КС

turn = 1 - i; // даем возможность входа другому процессу

while (ready && (turn == 1-i)); // если очередь оказалась не нашей, ждем пока он не выйдет из КС

// критическая секция

ready[i] = 0; // сообщаем о выходе из КС

Требования к программной реализации:

* Не используется аппаратная поддержка

* Нет предположений о скорости процессоров и их количестве

* В критической секции только один процесс

* Условие ограниченного ожидания - если один процесс решил войти в свою критическую секцию, это не должно продолжаться неограниченно долго.

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

2. М еханизм синхронизации. Семафоры

В 1965 разработан Дейкстрой (Dijkstra). Семафор - представляет из себяя целочисленную переменную, принимающую неотрицательные значения, доступ любого процесса к которой, за исключением момента её инициализации осуществляется только через две атомарные операции:

* P(S) - операция пролога критической секции

Пока S=0 процесс блокируется

Когда S>0, S=S-1

* V(S) - операция эпилога критической секции

Операция V атомарна автоматически, атомарность P надо обеспечивать - программистом, аппаратным обеспечением или ОС.

Для задачи «потребитель-производитель» критической операцией будет любая работа с буфером.

semaphore mutex = 1; // бтв, я нихуц не понял почему переменные названы

semaphore empty = N; // именно так, ибо смысл у них обратный их

semaphore full = 0; // названиям. Так что я бы full empty.

void Prod() { // производитель

while (1) {

Произвести() ; // производим нечто

P(empty) ; // проверяем наличие места в буфере. Если полон ( empty==0 ) , залипаем, иначе уменьшаем количество места в нем на единицу

P(mutex) ; //

ПоложитьВБуфер() ;

V(mutex) ; // освобождаем mutex

V(full) ; // увеличиваем количество элементов в буфере. Это разлепляет ожидающих потребителей

void Cons() { // потребитель

while (1) {

P(full) ; // проверяем есть ли в буфере что-нибудь. Если пуст ( full==0 ) , залипаем, иначе уменьшаем количество элементов на единицу.

P(mutex) ; // залипаем если сейчас между P(mutex) и V(mutex) находится другой процесс

ИзвлечьИзБуфера() ;

V(mutex) ; // освобождаем mutex . Остальные процессы могут ходить сюда отныне

V(empty) ; // увеличиваем количество свободного места на единицу. Это разлепляет производителей

ИспользоватьПолученныеДанные() ; // радостно съедаем полученую из буфера нямку

3. М еханизм синхронизации. Мониторы

Появились в 1974. Хор.

Являются более высокоуровневым механизмом чем семафоры. Были созданы для устранения недостатков семафоров.

Строятся на основе языков ООП.

Монитор - особый тип данных, класс, содержащий ряд данных, работа с которыми может осуществляться только функциями и методами самого монитора.

описание данных

void m1 (…) {…}

void mN(…) {…}

{инициализация /* выполняется один раз при создании монитора */}

Только один процесс может в один момент времени работать с монитором (находиться в состоянии исполнения или готовности к исполнению).

Это реализуется компилятором, путем добавления пролога и эпилога для входа и выхода из монитора. Однако, этого недостаточно для задач синхронизации, поэтому в мониторе есть две дополнительных операции - signal и wait. Обе операции выполняются над условной переменной, которая описывается в мониторе.

Если процесс выполняет wait(), он блокируется и переходит в состояние ожидания.

Если процесс выполняет signal(), он разблокирует процесс, который был ранее заблокирован операцией wait(). Разблокируется только один процесс. Если процессов в ожидании не было, ничего не происходит и информация о возникновении сигнала теряется.

condition full, empty;

if (count==N) full.wait();

ПоложитьВБуфер(el);

if (count==1) empty.signal(); // если раньше очередь была пуста, сигналим

if (count==0) empty.wait();

ИзвлечьИзБуфера();

if (count==(N-1)) full.signal();

// инициализация:

Prod() { // производитель

ПРОИЗВОДИТ!

Cons() { // потреблятель

ПОТРЕБЛЯТ!}}

4. Механизм синхронизации процессов. Сообщения, эквивален тность механизмов синхронизации

При параллельной работе нескольких процессов или потоков могут возникать конфликты при использовании разделяемых ресурсов. Такие ресурсы называются критическими.

Критическая секция (КС) - часть кода программы, которая может привести к конфликтам.

Для избежания данного явления применяют различные механизмы взаимоисключений, т.е. один процесс при работе в КС блокирует другой.

Структура КС: пролог, КС, эпилог.

Требования к алгоритмам взаимоисключений:

1. Решение программным путем.

2. Отсутствие предположений о количестве процессоров и их быстродействии.

3. Условие взаимоисключения, т.е. в КС находится только один процесс.

4. Условие прогресса - если процесс находится вне КС, он не должен препятствовать другим процессам входить в свои КС.

5. Условие ограниченного ожидания - если процесс захотел войти в КС это не должно откладываться бесконечно долго.

Механизмы синхронизации - высокоуровневые варианты реализации синхронизации с использованием средств ОС. Достоинством является возможность учета времени ожидания входа в КС. Реализуются компиляторами программно или с использованием аппаратных средств (семафоры, мониторы, сообщения).

Сообщения.

Наиболее простой механизм синхронизации. Реализуется с использованием 2х примитивов:

send (Q, mess) - отправить сообщение mess, процессу / объекту Q.

receive (Q, mess) - получить сообщение mess, от процесса / объекта Q.

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

- : медленно.

+: возможно использование для общения удаленных процессов.

Эквивалентность механизмов синхронизации.

Можно показать, что в рамках одной вычислительной системы, когда процессы имеют возможность использовать разделяемую память, все механизмы синхронизации эквивалентны. Т.е. любые два из механизмов могут быть реализованы на базе третьего.

Реализация мониторов с помощью семафоров.

Для этого нам нужно реализовывать взаимоисключения при входе в монитор и условные переменные. Возьмем семафор mutex с начальным значением 1 для реализации взаимоисключения при входе в монитор и по одному семафору ci для каждой условной переменной. Кроме того, для каждой условной переменной заведем счетчик fi для индикации наличия ожидающих процессов. Когда процесс входит в монитор, компилятор будет генерировать вызов функции monitor_enter, которая выполняет операцию P над семафором mutex для данного монитора. При нормальном выходе из монитора (то есть при выходе без вызова операции signal для условной переменной) компилятор будет генерировать вызов функции monitor_exit, которая выполняет операцию V над этим семафором.

Для выполнения операции wait над условной переменной компилятор будет генерировать вызов функции wait, которая выполняет операцию V для семафора mutex, разрешая другим процессам входить в монитор, и выполняет операцию P над соответствующим семафором ci, блокируя вызвавший процесс. Для выполнения операции signal над условной переменной компилятор будет генерировать вызов функции signal_exit, которая выполняет операцию V над ассоциированным семафором ci (если есть процессы, ожидающие соответствующего события), и выход из монитора, минуя функцию monitor_exit.

01 Semaphore mutex = 1;

02 void monitor_enter()

06 void monitor_exit()

10 Semaphore ci = 0;

19 void signal_exit(i)

Заметим, что при выполнении функции signal_exit, если кто-либо ожидал этого события, процесс покидает монитор без увеличения значения семафора mutex, не разрешая тем самым всем процессам, кроме разбуженного, войти в монитор. Это увеличение совершит разбуженный процесс, когда покинет монитор обычным способом или когда выполнит новую операцию wait над какой-либо условной переменной.

Реализация сообщений через семафоры.

Для простоты опишем реализацию только одной очереди сообщений. Выделим в разделяемой памяти достаточно большую область под хранение сообщений, там же будем записывать, сколько пустых и заполненных ячеек находится в буфере, хранить ссылки на списки процессов, ожидающих чтения и памяти. Взаимоисключение при работе с разделяемой памятью будем обеспечивать семафором mutex. Также заведем по одному семафору ci на взаимодействующий процесс, для того чтобы обеспечивать блокирование процесса при попытке чтения из пустого буфера или при попытке записи в переполненный буфер. Рассмотрим работу механизма:

Процесс, желающий получить сообщение.

Процесс-получатель с номером i прежде всего выполняет операцию P(mutex), получая в монопольное владение разделяемую память. После чего он проверяет, есть ли в буфере сообщения. Если нет, то он заносит себя в список процессов, ожидающих сообщения, выполняет V(mutex) и P(ci). Если сообщение в буфере есть, то он читает его, изменяет счетчики буфера и проверяет, есть ли процессы в списке процессов, ожидающих записи. Если таких процессов нет, то выполняется V(mutex), и процесс-получатель выходит из КС. Если такой процесс есть (с номером j), то он удаляется из этого списка, выполняется V для его семафора cj, и выходим из КС. Проснувшийся процесс начинает выполняться в КС, так как mutex имеет значение 0 и никто более не может попасть в КС. При выходе из КС разбуженный процесс производит вызов V(mutex).

Работа процесса-отправителя (номером i). Процесс, посылающий сообщение, ждет, пока не сможет иметь монополию на использование разделяемой памяти, выполнив операцию P(mutex). Далее он проверяет, есть ли место в буфере, и если да, то помещает туда сообщение, изменяет счетчики и смотрит, есть ли процессы, ожидающие сообщения. Если нет, выполняет V(mutex) и выходит из КС, если есть, то «будит» один из них (с номером j), вызывая V(cj), с одновременным удалением этого процесса из списка процессов, ожидающих сообщений, и выходит из КС без вызова V(mutex), предоставляя тем самым возможность разбуженному процессу прочитать сообщение. Если места в буфере нет, то процесс-отправитель заносит себя в очередь процессов, ожидающих возможности записи, и вызывает V(mutex) и P(ci).

Реализация семафоров с помощью мониторов

Самый простой способ такой реализации выглядит следующим образом. Заведем внутри монитора переменную-счетчик, связанный с эмулируемым семафором списком блокируемых процессов и по одной условной переменной на каждый процесс. При выполнении операции P над семафором вызывающий процесс проверяет значение счетчика. Если оно больше нуля, уменьшает его на 1 и выходит из монитора. Если оно равно 0, процесс добавляет себя в очередь процессов, ожидающих события, и выполняет операцию wait над своей условной переменной. При выполнении операции V над семафором процесс увеличивает значение счетчика, проверяет, есть ли процессы, ожидающие этого события, и если есть, удаляет один из них из списка и выполняет операцию signal для условной переменной, соответствующей процессу.

Реализация семафоров с помощью очередей сообщений.

Для этого введем новый синхронизирующий процесс (СП). Этот процесс имеет счетчик и очередь для процессов, ожидающих включения семафора. Для того чтобы выполнить операции P и V, процессы посылают СП сообщения, в которых указывают свои потребности, после чего ожидают подтверждения от него.

После получения сообщения СП проверяет значение счетчика, чтобы выяснить, можно ли совершить требуемую операцию. Операция V всегда может быть выполнена, в то время как операция P может потребовать блокирования процесса. Если операция может быть совершена, то она выполняется, и СП посылает подтверждающее сообщение. Если процесс должен быть блокирован, то его идентификатор заносится в очередь блокированных процессов, и подтверждение не посылается. Позднее, когда какой-либо из других процессов выполнит операцию V, один из блокированных процессов удаляется из очереди ожидания и получает соответствующее подтверждение.

Т.о. все эти конструкции являются эквивалентными, т.е., используя любую из них, можно реализовать две оставшиеся.

5 . Ра спределение памяти раз делами, перемещаемыми разделами

Распределение памяти фиксированными разделами.

Наиболее простой способ управления оперативной памятью (ОП). При этом вся память разделяется на некоторое количество разделов фиксированной величины, рзделение осуществляется либо оператором, либо при старте системы (запуске ОС). Очередной запущенный процесс поступивший на выполнение, помещается в общую очередь, либо в очередь к некоторому разделу.

Подсистема управления памятью выполняет задачи: выбор подходящего раздела, загрузка программы и настройка адресов.

Варианты определения раздела для загрузки:

1. первый попавшийся.

2. Наиболее подходящий.

3. Наименее подходящий.

+: простота реализации, запуск нескольких процессов, отсутствует внешняя фрагментация (вся память распределена по разделам)

- : большая внутренняя фрагментация (часть раздела остается неиспользованой), размер программы не может превышать размер раздела.

Распределение памяти разделами переменной длины.

При таком варианте ОП заранее не делится на разделы. Для каждого запущенного процесса выделяется раздел необходимого ему размера. По завершении процесса память освобождается и на ее место может быть загружен новый процесс.

Т.о. память представляет собой случайную последовательность свободных и занятых разделов произвольной длины.

Задачи управления памятью: ведение таблиц свободных и занятых областей с указанием начальных адресов и размеров; выбор свободных областей достаточных для загрузки программы; загрузка программы и настройка ее адресов; корректировка таблиц.

+: количество одновременно загруженных программ жестко не ограничено; отсутствует внутренняя фрагментация.

- : большая внешняя фрагментация.

Распределение памяти перемещаемыми разделами.

Для устранения недостатка предыдущего способа применяют дефрагментацию (сжатие). При этом происходит перемещение всех разделов к старшим или младшим адресам образуя непрерывную последовательность занятых и свободных областей.

Сжатие может производиться при каждом завершении процесса, либо когда для вновь поступившей задачи нет раздела достаточного размера.

Так как в данном случае программы становятся перемещаемыми в ходе выполнения, то связывание логических и физических адресов должно быть динамическим (во время выполнения).

+: отсутствие внутренней фрагментации; малая внефняя фрагментация.

- : большие накладные расходы, во время сжатия работа всех программ приостанавливается

6 . Ст раничное распределение памяти

Память разделяется на страницы фиксированного размера (кратные степени 2, для х86 - 4Кб).

Логическое адресное пространство состоит из логических страниц, а физическое из физических.

Адрес представляет собой пару (p, d), где p - номер логической страницы, а d - смещение в ней.

Схема преодразования логического адреса (ЛА) в физический (ФА):

синхронизация код программный алгоритм

Для каждого процесса имеется своя таблица страниц, таким образом решается вопрос защиты памяти (процесс не может обратиться за пределы своей таблицы). Атрибуты позволяют организовать дополнительную защиту отдельных страниц (права rwx) и часть страниц сделать разделяемыми (библиотеки).

Реализуется программно или аппаратно (процессор имеет регистр с адресом таблицы страниц текущего процесса)

+:размещение произвольного количества процессов; процессы в физической памяти расположены произвольно, но для программиста память линейна; отсутствует внешняя фрагментация; минимальная внутренняя фрагментация (только в последней странице программы); защита памяти.

- : большие накладные расходы без аппаратной поддержки.

Для уменьшения накладных расходов таблицу страниц можно хранить в кэше процессора.

7. Сегментное распределение памяти

При сегментной организации памяти, память разбивается на сегменты. Сегменты могут иметь переменный размер, могут задаваться программистом или по умолчанию компилятором. Адрес сегмента двухкомпонентный. Максимальный размер сегмента определяется разрядностью адресной шины (т.е. при 32-разрядной шине использовать можно сегмент размерностью 2 32 бит).

Адресное пространство процесса представляет собой набор сегментов, располагающихся непрерывно в памяти.

Преобразование адресов производится следующим образом (не для DOS):

Рисунок 1. Преобразование адресов при сегментной адресации

На данный момент аппаратная поддержка сегментов реализована только в Intel.

Достоинства сегментной организации памяти:

Защита памяти (имеется атрибут сегмента в таблице);

Недостатки:

Сегменты должны храниться непрерывно.

8. Сегментно-страничное распределение памяти

Заключается в том, что сегмент состоит из страниц (см. вопрос 6,7 СПО).

Адрес состоит из трех полей:

Достоинства:

Возможно совместное использование памяти процессами;

Гибкая настройка прав доступа, т.к. у каждой таблицы имеются атрибуты.

Недостатки:

Для доступа к данным необходимо три обращения.

9. Виртуальная память на основе сегментно-с траничного распределения памяти

Виртуальная память.

Виртуальная память используется в качестве расширения доступной памяти. Ее особенность состоит в том, что она использует несколько уровней памяти (например, винчестер и ОП).

Появилась в 1959 г.

Суть состоит в следующем. Активный процесс располагается в ОП. Сам процесс разбивается на несколько частей (страниц, сегментов и т.п.). Автоматически происходит преобразование логического адреса в физический. Если страница отсутствует в ОП, то она должна быть в нее загружена. Присутствие страницы в той или иной памяти определяется битом присутствия.

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

1) Программа не ограничена объемом ОП.

2) Есть возможность частичного размещения программ, что позволяет увеличить количество выполняемых программ.

3) Объем ввода / вывода информации значительно меньше, чем в классическом swapping"е (суть swapping"а - страницы копируются на винчестер при отсутствии места в ОП).

4) Объем адресуемой памяти становится равным максимальному объему для данной разрядности (к примеру, 32 разряда = 4 Гб).

Виртуальная память может быть распределена как:

а) страничная;

б) сегментная;

в) странично-сегментная.

Технология виртуализации памяти может быть полностью реализована программно.

Виртуальная память на основе сегментно-страничного разделения.

Основана на таблице страниц, куда добавляются биты:

1) Бит модификации (была ли изменена страница).

2) Бит присутствия (где страница лежит - в ОП или на винчестере).

3) Бит обращения (происходило ли обращение к странице).

Исключительные ситуации при работе с виртуальной памятью (к примеру, отсутствует страница в памяти) обрабатываются операционной системой и их относят к особому типу прерываний.

Программное обеспечение для управления памятью связано с реализацией следующих стратегий:

1) Стратегия выборки - в какой момент следует переписать страницу из вторичной памяти в первичную. Существует два основных варианта выборки - по запросу и с упреждением. Алгоритм выборки по запросу вступает в действие в тот момент, когда процесс обращается к отсутствующей странице, содержимое которой находится на диске. Его реализация заключается в загрузке страницы с диска в свободную физическую страницу и коррекции соответствующей записи таблицы страниц.

Алгоритм выборки с упреждением осуществляет опережающее чтение, то есть кроме страницы, вызвавшей исключительную ситуацию, в память также загружается несколько страниц, окружающих ее (обычно соседние страницы располагаются во внешней памяти последовательно и могут быть считаны за одно обращение к диску). Такой алгоритм призван уменьшить накладные расходы, связанные с большим количеством исключительных ситуаций, возникающих при работе со значительными объемами данных.

2) Стратегия размещения - в какой участок первичной памяти поместить поступающую страницу.

3) Стратегия замещения - какую страницу нужно вытолкнуть во внешнюю память, чтобы освободить место в оперативной памяти. Для данной стратегии используются алгоритмы FIFO и др.

Размещено на Allbest.ru

Подобные документы

Основные понятия о процессах. Взаимное исключение критических интервалов. Общий подход к построению механизмов синхронизации с использованием концепции критических участков. Основные преимущества алгоритма Декера. Графическое решение задачи о стрелках.

курсовая работа , добавлен 16.12.2014


Управление процессами - часть операционной системы, влияющая на функционирование вычислительной машины. Контекст дескриптор процесса и алгоритм его планирования. Средства синхронизации и взаимодействия процессов. Критическая секция, тупики и нити.

лекция , добавлен 05.02.2009


Осуществление работы разрабатываемой программы на основе алгоритма, использующего Z-буфер. Аналитическое описание программной реализации. Алгоритмы основных функций программы. Содержание руководства пользователя. Файлы программы, пункты главного меню.

курсовая работа , добавлен 15.04.2015


Структура, классификация и требования к реализации компилятора. Проектирование и реализация анализирующей части компилятора языка С++. Способы реализации лексического анализа. Алгоритм работы синтаксического анализатора. Принципы программной реализации.

курсовая работа , добавлен 26.01.2013


Разработка программной реализации решения задачи о минимальном покрывающем дереве графа (построение минимального остова), используя алгоритмы Прима и Крускала. Подсчет времени работы алгоритмов. Их программная реализация на практике с помощью Delphi 7.

курсовая работа , добавлен 29.08.2010


Концептуальная, логическая и физическая модели данных, ее внутренняя структура и содержание, предъявляемые функциональные требования и сфера практического использования. Описание реализации программного кода, дерево моделей и функций, тестирование.

курсовая работа , добавлен 02.06.2015


Понятие и назначение штрихового кода, его разновидности и сферы применения. Параметры символики и структура символа в кодах. Алгоритм преобразования числовых данных в знаки Interleaved 2 of 5. Распознавание штрих-кода и вычисление контрольной цифры.

контрольная работа , добавлен 23.08.2009


Общее описание разрабатываемого программного обеспечения, требования к его функциональности и сферы практического применения. Выбор инструментальных средств разработки. Проектирование структур баз данных и алгоритмов, пользовательского интерфейса.

дипломная работа , добавлен 19.01.2017


Понятие процесса и потока, характеристика их свойств и особенности создания. Требования к алгоритмам синхронизации, суть взаимного исключения на примере монитора и семафора. Методика изучения элективного курса "Процессы в операционной системе Windows".

дипломная работа , добавлен 03.06.2012


Назначение и цели создания системы. Требования к программе или программному изделию, к информационной и программной совместимости, к составу и параметрам технических средств. Алгоритм Rijndael. Назначение и условия применения программного продукта.

Вы когда-нибудь задумывались о том, как здорово было бы самому писать программы? Но учить языки программирования не возникает желания? Тогда сегодня мы рассмотрим визуальную среду программирования, которая не требует никаких знаний в области разработки проектов и приложений.

Алгоритм – это конструктор, из которого вы по кусочкам собираете свою программу. Разработанный в России, Алгоритм постоянно обновляется и расширяет свои возможности. Здесь нет необходимости писать код – вам просто нужно кликать мышью на необходимые элементы. В отличии от , Алгоритм является более простой и понятной программой.

С помощью Алгоритма вы можете создавать самые разнообразные программы: от простейшего “Hello world” до интернет-браузера или сетевой игры. Довольно часто к Алгоритму обращаются люди, профессия которых тесно связана с математическими расчетами, так как его очень удобно использовать для решения математических и физических задач. Все зависит только от вашего терпения и желания учиться.

Большой набор объектов

Алгоритм обладает большим набором объектов для создания программ: кнопки, лейблы, разнообразные окна, бегунки, меню и многое другое. Это дает возможность сделать проект более продуманным, а также создать удобный для пользователя интерфейс. Для каждого объекта можно задать действие, а также задать уникальные свойства.

Справочный материал

Справочный материал Алгоритма содержит в себе ответы на все вопросы. Вы можете найти информацию о каждом элементе, просмотреть примеры, а также вам будет предложено просмотреть видео-обучение.

Достоинства

1. Возможность создавать программы без знаний языка программирования;
2. Большой набор инструментов для создания интерфейса;
3. Удобный и понятный интерфейс;
4. Возможность работать с файлами, папками, реестром и т.д;
5. Русский язык.

Недостатки

1. Алгоритм не предназначен для серьезных проектов;
2. Компилировать проект в.exe можно только на сайте разработчика;
3. Довольно долго работает с графикой.

Алгоритм – это интересная среда разработки, которая подтолкнет вас к изучению языков программирования. Здесь вы сможете проявить фантазию, создать что-то уникальное, а также разобраться с принципом работы программ. Но Алгоритм нельзя назвать полноценной средой – все же это просто конструктор, где вы можете изучить основы. Если с ее помощью вы научитесь разрабатывать проекты, то в дальнейшем сможете перейти к изучению Delphi и C++ Builder.