Программы, написанные на языках программирования высокого уровня перед выполнением на ЭВМ должны транслироваться в эквивалентные программы, написанные на машинном коде. icon

Программы, написанные на языках программирования высокого уровня перед выполнением на ЭВМ должны транслироваться в эквивалентные программы, написанные на машинном коде.


1 чел. помогло.
Смотрите также:
Рабочая программа по курсу “Программирование на языках высокого уровня” Факультет экономический...
Основные разделы программы Программирование на языке высокого уровня Операционные системы...
Роль и значение языка паскаль в эволюции языков программирования...
Данное пособие поможет написать сочинения для школьников. Внем собраны лучшие сочинения...
Эти произведения автора не относятся к относительно совершенным в литературно духовном и т п...
Параллельные программы главный тормоз 11 2 mpi 11 3 Реализации mpi 12 4 Средства...
«Теория игр и исследование операций» Направления нк, нп 4 курс, 1-й семестр (2008/09 уч год)...
Программы Организации Объединенных Наций по окружающей среде комитет высокого уровня министров...
Рабочая программа по дисциплине Основы алгоритмизации и программирования (язык С/C++) Для...
Составление программы на языке программирования...
Литература [Абрамов89] Абрамов С. А., Зима Е. В...
Алгоритмизация и программирование. Языки программирования высокого уровня...



Загрузка...
страницы: 1   2   3   4   5   6   7   8
вернуться в начало
скачать
^

Проблемы семафоров


Во-первых, можно написать программу с «утечкой семафора», вызвав enter() и забыв вызвать leave(). Реже встречаются ошибки, когда дважды вызывается leave().

Во-вторых, семафоры чреваты взаимной блокировкой потоков.

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

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

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

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

Изобретён Пером Бринчем Хансеном, впервые воплощён в языке Concurrent Pascal и использован для структурирования межпроцессного взаимодействия в операционной системе Solo.

Монитор состоит из:

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

Чтобы избегать состояния активного ожидания, процессы должны сигнализировать друг другу об ожидаемых событиях. Мониторы обеспечивают эту возможность с помощью условных переменных. Когда процедура монитора требует для дальнейшей работы выполнения определённого условия, она ждёт связанную с ним условную переменную. Во время ожидания она временно отпускает мьютекс и выбывает из списка исполняющихся процессов. Любой процесс, который в дальнейшем приводит к выполнению этого условия, использует условную переменную для оповещения ждущего её процесса. Оповещённый процесс захватывает мьютекс обратно и может продолжать. Семантика Хоара и Mesa


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

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

В самых современных реализациях (известных как семантика Mesa), оповещение не прерывает работающий процесс, а просто переводит некоторые ждущие процессы в состояние готовности. Оповещающий процесс продолжает держать блокировку до тех пор, пока не выйдет из процедуры монитора. Побочные эффекты этого подхода в том, что оповещающий процесс не обязан соблюсти инвариант перед оповещением, а ожидающий процесс — должен повторно проверить условие, которого он дожидается. В частности, если процедура монитора включает выражение if test then wait(cv), другой процесс может войти в монитор после момента оповещения и изменить значение test до того, как ждущий процесс возобновит работу. Выражение нужно переписать так: while test do wait(cv), чтобы условие было пере-проверено после ожидания.



9. Классические задачи синхронизации. «Обедающие философы».


Использование сообщений – один из способов межпроцессного и межпоточного

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

данными. Важным свойством механизма сообщений является возможность его

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

различных узлах сети.

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

При асинхронной доставке поток, посылающий сообщение, инициирует процесс

доставки сообщения, после чего продолжает свою работу (сообщение доставляется

операционной системой параллельно деятельности потока). При синхронной доставке

поток, пославший сообщение, дожидается подтверждения его получения

принимающим потоком.


Сообщения позволяют организовать синхронизацию выполнения потоков.

Например, пусть имеются разделяемые данные, над которыми требуется многократно


выполнить некоторую операцию и есть два потока, которые выполняют данную

операцию над частями разделяемых данных. Предположим также, что каждое

следующее выполнение операции требует, чтобы предыдущее было полностью

завершено обоими потоками.


Задача «Обедающие философы»


Предположим, имеется некоторая совокупность ресурсов, которые могут

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

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

обеспечения согласованного доступа к некоторому подмножеству имеющихся

ресурсов. Задача об обедающих философах представляет частную постановку такой


61


задачи, имеющую ограничениями относительно общего случая, но допускающая

расширения своего решения.


Оригинальная постановка задачи, предложенная Э. Дийкстрой, звучит следующим

образом. На круглом столе расставлены тарелки, по одной на каждого философа. В

центре стола – большое блюдо спагетти, а на столе лежат пять вилок — каждая между

двумя соседними тарелками. Каждый философ находится только в двух состояниях —

либо он размышляет, либо ест спагетти. Начать думать после еды философу ничто не

мешает. Но чтобы начать есть, необходимо выполнить ряд условий. Предполагается,

что любой философ, прежде чем начать есть, должен положить из общего блюда

спагетти себе в тарелку. Для этого он одновременно должен держать в левой и правой

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

начать есть. Закончив еду, философ кладет вилки слева и справа от своей тарелки и

опять начинает размышлять до тех пор, пока снова не проголодается.

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

ограничение состоит в том, что каждая вилка используется только двумя сидящими

рядом с ней философами.


Задача «Обедающие философы» заключается в обеспечении согласованного

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

удовлетворять следующим условиям:

- потоки выполняются параллельно;


- во время использования «вилок» потоком данные «вилки» не должны

использоваться его соседями;

- потоки должны завершить работу в течение конечного времени.


Можно предположить следующие типичные недостатки, присущие различным

решениям задачи об обедающих философах:


- если все философы проголодались, взяли левую вилку и не желают ее отдавать, то

они все будут ожидать правые вилки в течение бесконечного времени; предложенное

решение не допускает возникновения подобной ситуации;


- если имеется голодный философ, то его непосредственные соседи могут по

очереди блокировать его левую и правую вилку таким образом, что в каждый момент

времени хотя бы одна из необходимых ему вилок занята – в результате возможно

голодание отдельного философа; предложенное решение допускает возможность

такого голодания.


Имеется простое расширение предложенного решения на случай, когда каждый

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

необходимо добавить массив признаков занятости ресурсов и описания множеств

ресурсов, затребованных каждым потоком, во-вторых, при освобождении ресурсов

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


случае, если запросы одного или нескольких потоков могут быть удовлетворены,

резервировать за ними ресурсы и разрешать им продолжить выполнение.


Подобное решение будет лишено первого недостатка (по причине того, что все

потоки требуют все необходимые им ресурсы сразу, а впоследствии их все

возвращают), но будет подвержено второму, как и оригинальное решение.


10. Классические задачи синхронизации. «Читатели и писатели».


Вторая типовая задача – проблема читателей и писателей (Readers-Writers problem).

Предположим, у нас есть хранилище данных, с которым работают несколько потоков.

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


Клиенты потоки, Сервер БД

обращающиеся к

записям БД


Запись База

данных

Запись 1


Запись 2


Чтение Запись 3





Запись N


Чтение


Рис. 29 Несколько потоков, обращающихся к базе данных


Если несколько потоков одновременно обращаются к разным записям базы

данных, то никаких проблем не возникает. Проблема синхронизации доступа к данным

возникает при обращении нескольких потоков к одной и той записи. К тому же,

организация согласованного доступа для потоков-читателей и потоков писателей

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

несколькими потоками не приводит к возникновению проблем, в то время как операция

записи требует эксклюзивного доступа.

Задача «Читатели-Писатели» заключается в обеспечении согласованного доступа

нескольких потоков к разделяемым данным. Корректное решение должно

удовлетворять следующим условиям:

- потоки выполняются параллельно;

- во время выполнения потоком операции записи, данные не могут использоваться

другими потоками;

- во время выполнения потоком операции чтения, другие потоки также могут

выполнять операцию чтения;

- потоки должны завершить работу в течение конечного времени.


ля защиты разделяемых критических данных используется двоичный семафор

Access. Функция писателя просто получает доступ к критическим данным (уменьшая

семафор Access) и использует их.


Функция читателя должна обеспечить одновременный доступ к критическим

данным нескольких читателей, поэтому она использует дополнительную переменную

ReadCount – количество читателей, выполняющих операцию чтения в настоящий

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

несколькими читателями (для этого введен двоичный семафор RC), но ее

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

первому читателю (остальные будут заблокированы при попытке уменьшить семафор

RC), а освобождение данных оставить последнему читателю, завершившему операцию

чтения. Обратим внимание, что вследствие подобного подхода функция читателя

содержит 3 критических секции: одну, связанную с чтением критических данных, и

две, связанных с изменением переменной ReadCount и организации процесса входа и

выхода из первой критической секции.


Отметим также, что если потоки-читатели постоянно входят в критическую

секцию, возможно голодание (starvation) потоков-писателей. (Голодание – ситуация,

когда поток не может приступить к выполнению своей задачи в течение

неограниченного периода времени). Для решения этой проблемы можно использовать

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

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

данное решение).






11. Классические задачи синхронизации. «Задача о спящем парикмахере».

«Спящий брадобрей».
Имеется парикмахерская с двумя дверями и несколькими креслами. Посетители входят в одну дверь и выходят через другую. Парикмахер всю жизнь обслуживает клиентов. Когда клиентов нет, он спит в своем кресле. Когда посетитель приходит в салон и видит спящего парикмахера, он будит его, садится в кресло и спит, пока тот занят стрижкой. Если во время стрижки приходит еще один клиент, он садится в одно из свободных кресел и засыпает. Если свободных мест нет, клиент уходит. После стрижки парикмахер открывает клиенту выходную дверь и закрывает ее за ним. Если есть ожидающие посетители, парикмахер будит одного из них и ждет, пока тот сядет в кресло, после чего стрижет его. Если посетителей нет, парикмахер идет спать до следующего клиента.
Таким образом, эта задача описывает отношения в системах «клиент-сервер», когда клиент посылает запрос и ждет ответа сервера. В свою очередь сервер ожидает запросы клиентов, обрабатывает их и посылает ответ.
Множество запросов клиентов образуют очередь, длина которой ограничена.

При решении учесть, что длительность каждой операции составляет некоторую случайную величину.
Предоставить решение в двух вариантах:
1.с использованием семафоров в условиях разделяемой памяти;
2.с использованием сообщений в условиях распределенной памяти.


У препода в лекциях, например, приведено.
Приведем решение, использующее семафоры:
#define CHAIRS 5 //количество стульев
semaphore customers=0; // количество ожидающих посетителей
semaphore barbers=0; // количество парикмахеров, ждущих клиентов
mutex m; // контроль доступа к waiting
int waiting=0; // и это количество ожидающих посетителей
process barber() // процесс - парикмахер
{
while(true)
{
down(customers); // если посетителей нет – уйти в ожидание
lock(m); // войти в критическую область
waiting--; // уменьшить количество ожидающих клиентов
up(barbers); // разбудить парикмахера
unlock(m); // выйти из критической области
// обслуживание клиента
}
}
process customer() // процесс - клиент
{
lock(m); // войти в критическую область
if (waiting{
waiting++; // увеличить счетчик ожидающих клиентов
up(customers); //при необходимости – разбудить парикмахера
unlock(m); // выйти из критической области
down(barbers); // если парикмахер занят – уйти в ожидание
// обслуживание клиента
} else // нет свободных стульев - уйти
unlock(m);
}
12. Файловые системы. Определение, свойства, типовые методы организации.


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

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




оставить комментарий
страница4/8
Дата02.10.2011
Размер0.79 Mb.
ТипДокументы, Образовательные материалы
Добавить документ в свой блог или на сайт

страницы: 1   2   3   4   5   6   7   8
хорошо
  1
отлично
  1
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх