Пояснение к выполнению курсовой работы.

Состоит из двух частей:

1. Теоретиеской

2. Практической

Оформление обложки:

Название министерства(министерство образования и науки).

ФГБОУ ВПО "МГТУ при Г.И.Носова"

Кафедра вычислительной техники и прикладной математики.

Курсовая работа(шрифт +1 к основному)

По дисциплине "Теория вычислительных процессов".

На тему: "Тема теоретической части. Практическая часть"

Выполнил студент группы АВБ 11-1

Проверила к.т.н., доцент кочержинская Ю.В.

Магнитогорск 2012.

Содержание

1)Теоретический вопрос:...................3.

1.N)Выводы.

2)Решение задачи

2.1)Постановка задачи.

2.2)Схема решения задачи с использовнием методологии К.Петри.

2.3)Листинг основных рабочих процедур.

2.4)Выводы.

3)Список использованных источников и литературы.

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

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

1. Пропускная способность. Исполнение максимального количества задач в единицу времени.

2. Минимизация времени затрачиваемого на обработку задачи и ожидания её обслуживания.

3. Поддержка постоянной занятости процессора.

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

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

1. Задача завершается выполнением в нормальном режиме.

2. Задача завершается

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

Кроме того не возможно гарантировать и исполнение задачи за определенное время. Система с разделением каждой задачи из очереди назначается временной интервал. Timeslice в течении которого задача получает доступ к процессору(unex os/2 Free BSD).

Если в системе есть центральный планировщик планирования потока и если какой-либо поток больше не может выполнятся и переходит в режим ядра обращается к планировщику в следующих случаях:

1. Поток блокируется на семафоре, мьетексе в будущем событии операции ввода/вывода(см след тему).

2. Поток сигнализирует каким-либо объектом(симофор).

3. Истекает квант времени работающего потока.

4. Завершается операция ввода/вывода.

5. Истекает таймер.

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

Приоритеты потока.

Thread_Priority_Idle.

Thread_Priority_Lowest.

Thread_Priority_Below_Normal.

Thread_Priority_Normal.

Thread_Priority_Above_Normal.

Приоритет устанавливается в 1 несмотря на класс приоритета родительского потока. Приоритет потока на 2 меньше чем приоритет родительского процесса.

Thread_Priority_Below_Normal приоритет потока на 1 меньше приоритета родительского процесса.

Thread_Priority_Normal приоритет потока равен приоритету процесса.

Thread_Priority_Above_Normal приоритет потока на единицу больше чем приоритет род процесса.

Соотношения значений приоритета процесса и потока при расчете базвого приоритета(не динамически изменяющийся) приведено в таблице: см распечатку.

Системы реального времени.

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

1. Эффективность поддержки многозадачности (для таких систем подходит только вытесняющая многозадачность).

2. Предотвращение блокировок.

3. Эффективная обработка прерываний(основанная на частом переопределении приоритетов и частом перерасчете динамической составляющей).

Например QNX применяется диспетчерезация FIFO.

Синхронизация процесса.

Решение проблемы множественного взаимодействия-задача первостепенной важности при проектировании информационной системы.

Задача некорректно ведущая себя по отношению к другим способна остановить выполнение в том числе ядра системы, т.е заблокировать ее. Данная проблема стоит особенно остро при проектировании СУБД. Встречаются следующие требования к построению СУБД:

1. Гарантированное поддержание базы.

Главным определение является определением транзакции. Транзакция это логическая единица выполняемой работы требующая обязательного завершения перед переходом к следующей операции главным свойством транзакции является ее атомарность. Есть две главных задачи иллюстрирующие проблемы синхронизации СУБД, первая называется проблемой потерянного обновления. Предположим что одновременно выполняется две операции, первая операция снятия денег со счета в количестве 100руб Т1 и операция занесения денег на тот же расчетный счет Т2 +1000руб, перед началом работы на расчетном счету находится так же 1000руб, оператор начинает операцию снятия денег, перед этим считывает состояние счета (1000руб) и в этот момент отрабатывается операция занесения денег на счет, если все отрабатывается верно на счету должно остаться 1900руб, но в этот момент завершается первая операция которая заносит на счет модифицированная ее значение суммы. Решением в данном случае является обеспечение атомарности каждой из транзакций, проблема зависимости от незафиксированных результатов, если выполнение начнется с операции Т2 а в процессе работы пользователь решит отменить эту операцию, но при этом если операция Т1 успела использоть незавершенные транзакции по Т2 то в этом случае она перезапишет содержимое счета.

Следующая.

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

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

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

Существуют следующие приемы синхронизации, первый называется синхронизация нижнего уровня, взаимное исключение реализуется аппаратно при том что операции над памятью делаются не делимыми, т.е если каждый из двух процессов пытается поместить какие-то значения в одну и ту же ячейку памяти, то такой спор решается на аппаратном уровне: одному процессу разрешается выполнить операцию помещения данных памяти немедленно, другому приходится ждать завершения операции первого. Такое разрешение спора называется блокировкой памяти и дает возможность реализации взаимного исключения двух и более процессов, алгоритмически это реализуется следующим образом, каждый процесс связывается со своим критическим участком через флаг, значение которого истина если процесс находится в своем критическом участке и ложь в противном случае. Прежде чем войти в критически участок процесс проверяет переключатель другого процесса, чтобы убедится в безопасности входа, если переключатели всех процессов установлены в значение ложь, процесс выполняет вход в критический участок, если хотя бы один из переключателей имеет значение ИСТИНА заинтересованный во входе в критический участок процесс переводится системой в состояние ожидания и его собственный переключатель остается в состоянии ложь, периодически производится повторный опрос состояния всех переключателей и когда значение всех их устанавливается в ЛОЖЬ, процесс устанавливает значение переключателя в ИСТИНА и входит в критический участок. Флаг ИСТИНА поднимается до входа в критический участок и опускается после выхода процесса из критического участка. Улучшенный вариант этого алгоритма был предложен Датским математиком Деккером: этот алгоритм основан на использовании трех переменных П1 П2 и очередь. Если П1 хочет войти в критический интервал, значение переменных П1 устанавливается ИСТИНА, значение переменная очередь указывает чье сейчас право входить в критический интервал, 0 или 1. Если П1 имеет значение ИСТИНА, а П2 ЛОЖЬ, то выполняется П1 не зависимо от значения переменной очереди, если обе переменные П1 и П2 имеют значение истина, то исполняемый процесс определяется значением переменной очереди. Завершив процесс сбрасывает свой флаг в ЛОЖЬ и изменяет значение переменной очередь на обратное. Возможное программное решение представлено в виде:

Begin integer c1,c2, очередь;

C1=0;

C2=0;

Очередь=1;

Begin

Процесс 1 : begin c1=1;

Do while(c2=1)

If очередь=2

Then begin

Do while (очередь=2)

End;

C1=1

End;

End;

C2=0;

Очередь =1;

End; end; end;

Процесс 2: begin c2=1

Do while (c1=1)

If очередь =2

Then begin

Do while (очередь=1)

End;

C2=1;

End;

End;

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

#define False 0

#define true 1

#define N 2

Int turn;

Int interested [N];

Void enter_region (int process)

{

int other;

Other =1-process;

Interested [process]=True;

Turn=process;

While (turn==process &&interested[other]==True)

{}//пустой цикл

}

Void leave_region (int process)

{interested [process]=False;}

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: