Команда goto
Команда GOTO позволяет передавать управление на метку и тем самым осуществлять повторное исполнение участков командного файла или, наоборот, обходить некоторые участки (это имеет смысл в сочетании с командой ветвления IF). Пример. Пусть командный файл PR.BAT имеет вид: echo off :m1 echo Вывод на принтер файла %1 echo Для остановки нажмите CTRL-C copy %1 prn pause goto m1 В данном примере вторая строка содержит метку m1 (признаком метки является двоеточие в начале строчки), а последняя строка - команду перехода на эту метку. Четыре команды внутри повторяемого участка командного файла служат для выдачи на экран поясняющих сообщений (команды ECHO) и копирования на принтер файла, имя которого подставляется вместо формального параметра %1. Команда PAUSE приостанавливает исполнение, чтобы пользователь имел возможность осмотреться и прервать работу или продолжить ее дальше. Допустим, пользователь дает с терминала команду: A:\>pr docum.doc Начинается циклическое исполнение файла PR.BAT с фактическим параметром DOCUM.DOC. На принтер начнут выдаваться одна за другой копии этого текстового файла, прерываемые паузами после каждой очередной копии. Пользователь может прервать исполнение этого командного файла, нажав одновременно клавиши CTRL-C.
Пакетные файлы в MS-DOS. Параметры и их использование в пакетных файлах.
С помощью пакетных файлов возможно создание довольно мощных средств для облегчения выполнения трудоемких операций, например, копирования, создания больших архивов, проверки каких-либо внешних условий и условная обработка данных. Особенно широкий простор здесь открывается для тех, кто знает хотя бы один язык программирования - используя и свои программы, можно создавать прямо-таки гигантские программные комплексы. При описании команд использовались принятые в DOS обозначения:
<параметр> - обязательный параметр.
[параметр] - необязательный параметер.
| - оператор "или".
Все команды и операторы языка являются регистронезависимыми, то есть, команды echo off, ECHO OFF и EcHo oFf являются абсолютно идентичными.
Организация диалога с пользователем в пакетных файлах.
Иногда в командном файле нужно выполнить различные действия по выбору пользователя. Это можно сделать с помощью программы Choice (она содержится в MS-DOS, начиная с версии 6.0). Формат команды:
Choice (/C список-символов) (/Т:символ,число-секунд) сообщение
Параметры:
/C список-символов – указывает допустимые символы, которые может ввести пользователь в ответ на сообщение. Если данный параметр не указан, тогда допустимыми символами будут ‘Y’ и ‘N’. Значение переменной ERRORLEVEL, возвращаемое после завершения команды Choice, устанавливается равным порядковому номеру введенного символа в списке.
/Т:символ,число-секунд – когда этот параметр указан, тогда в качестве ответа принимается указанный символ, если пользователь по истечении времени, заданного параметром число-секунд, не нажал ни на одну клавишу.
Пример. Команда организации диалога с пользователем в пакетном файле при помощи программы Choice:
Choice /C:YN “Запустить программу ALFA”
В результате выполнения данной команды при ответе Y значение переменнойERRORLEVEL будет установлено равным 2, при ответе N – равным 1.
Замечания:
1. Если Вы желаете, чтобы при вводе символов различались прописные и строчные буквы, укажите в команде параметр /S.
2. По умолчанию к сообщению добавляется список символов (через запятую в квадратных скобках), допустимых для ответа и знак вопроса. Для того чтобы избежать этого, нужно указать в команде параметр /N.
3. Если в сообщении, которое нужно вывести на экран, имеются символы ‘/’, тогда его следует заключить в кавычки.
Пример. Покажем, как следует обрабатывать значения, возвращаемые программой Choice. В приведенном ниже примере пользователь по своему выбору запускает одну из трех игр:
@Echo off
Echo Выберите игру: D - DIGGER, Т - TETRIS, С - CAT
Choice /C:DTC "Введите символ"
IF errorlevel 3 goto cat
IF errorlevel 2 goto tet
Digger.exe
goto exit
:tet
Tetris.exe
goto exit
:cat
Cat.exe
:exit
Внимание! Проверку переменной ERRORLEVEL командами IF следует производить в порядке убывания ее возможных значений: сначала нужно проверить ее на самое большое значение, затем - на следующее по убыванию и т.д.
Проблема критической секции. Необходимые условия решения проблемы критической секции по Дейкстра.
Алгоритм Деккера - первое известное корректное решение проблемы взаимного исключения в конкурентном программировании.
Если два процесса пытаются перейти в критическую секцию одновременно, алгоритм позволит это только одному из них, основываясь на том, чья в этот момент очередь. Если один процесс уже вошёл в критическую секцию, другой будет ждать, пока первый покинет её. Это реализуется при помощи использования двух флагов (индикаторов "намерения" войти в критическую секцию) и переменной turn (показывающей, очередь какого из процессов наступила).
Процессы объявляют о намерении войти в критическую секцию; это проверяется внешним циклом «while». Если другой процесс не заявил о таком намерении, в критическую секцию можно безопасно войти (вне зависимости от того, чья сейчас очередь). Взаимное исключение всё равно будет гарантировано, так как ни один из процессов не может войти в критическую секцию до установки этого флага (подразумевается, что, по крайней мере, один процесс войдёт в цикл «while»). Это также гарантирует продвижение, так как не будет ожидания процесса, оставившего «намерение» войти в критическую секцию. В ином случае, если переменная другого процесса была установлена, входят в цикл «while» и переменная turn будет показывать, кому разрешено войти в критическую секцию. Процесс, чья очередь не наступила, оставляет намерение войти в критическую секцию до тех пор, пока не придёт его очередь (внутренний цикл «while»). Процесс, чья очередь пришла, выйдет из цикла «while» и войдёт в критическую секцию.
Алгоритм Деккера гарантирует взаимное исключение, невозможность возникновения deadlock или starvation. Рассмотрим, почему справедливо последнее свойство. Предположим, что p0 остался внутри цикла «while flag[1]» навсегда. Поскольку взаимная блокировка произойти не может, рано или поздно p1 достигнет своей критической секции и установит turn = 0 (значение turn будет оставаться постоянным пока p0 не продвигается). p0 выйдет из внутреннего цикла «while turn = 1» (если он там находился). После этого он присвоит flag[0] значение true и будет ждать, пока flag[1] примет значение false (так как turn = 0, он никогда не выполняет действия в цикле «while»). В следующий раз когда p1 попытается войти в критическую секцию, он будет вынужден исполнить действия в цикле «while flag[0]». В частности, он присвоит flag[1] значение false и будет исполнять цикл «while turn = 0» (так как turn остаётся равной 0). Когда в следующий раз управление перейдёт к p0, он выйдет из цикла «while flag[1]» и войдёт в критическую секцию.
Если модифицировать алгоритм так, чтобы действия в цикле «while flag[1]» выполнялись без проверки условия «turn = 0», то появится возможность starvation. Таким образом, все шаги алгоритма являются необходимыми.
Одним из преимуществ алгоритма является то, что он не требует специальных Test-and-set инструкций (атомарная операция чтения, модификации и записи) и вследствие этого он легко переносим на разные языки программирования и архитектуры компьютеров. Недостатками можно назвать его применимость к случаю только с двумя процессами и использование Busy waiting вместо приостановки процесса (использование busy waiting предполагает, что процессы должны проводить минимальное количество времени внутри критической секции).
Современные операционные системы предоставляют примитивы синхронизации более общие и гибкие по сравнению с алгоритмом Деккера. Тем не менее, следует заметить, что в случае отсутствия реальной конкуренции между двумя процессами, операции входа в критическую секцию и выхода из неё будут являться очень эффективными при использовании этого алгоритма.
Многие современные микропроцессоры исполняют инструкции не по порядку. Алгоритм не будет работать на SMP-машинах, оборудованных такими CPU, если не использоватьбарьеры памяти.
Семафоры и семафорные примитивы. Их использование для решения проблемы критической секции.
Пусть в результате проверки переменной процесс определил, что ресурс свободен, но сразу после этого, не успев установить переменную в 0, был прерван. За время его приостановки другой процесс занял ресурс, вошел в свою критическую секцию, но также был прерван, не завершив работы с разделяемым ресурсом. Когда управление было возвращено первому процессу, он, считая ресурс свободным, установил признак занятости и начал выполнять свою критическую секцию. Таким образом был нарушен принцип взаимного исключения, что потенциально может привести к не желаемым последствиям.
Блокирующие переменные.
При использовании блокирующих переменных с каждым разделяемым ресурсом связывается двоичная переменная, которая принимает значение 1, если ресурс свободен (то есть ни один процесс не находится в данный момент в критической секции, связанной с данным ресурсом), и значение 0, если ресурс занят.
Реализация критических секций с использованием блокирующих переменных
На рисунке показан фрагмент алгоритма процесса, использующего блокирующую переменную F(D) для реализации взаимного исключения доступа к разделяемому ресурсу D. Перед входом в критическую секцию процесс проверяет, свободен ли ресурс D. Если он занят, то проверка циклически повторяется. Если свободен, то значение переменной F(D) устанавливается в 0, и процесс входит в критическую секцию. После того, как процесс выполнит все действия с разделяемым ресурсом D, значение переменной F(D) снова устанавливается равным 1.
Блокирующие переменные могут использоваться не только при доступе к разделяемым данным, но и при доступе к разделяемым ресурсам любого вида. Если все потоки написаны с учетом вышеописанных соглашений, то взаимное исключение гарантируется. При этом потоки могут быть прерваны ОС в любой момент и в любом месте, в том числе в критической секции.
Поэтому для реализации пинципа блокирующих переменных в системе команд многих компьютеров предусмотрена единая, неделимая команда анализа и присвоения значения блокирующей переменной.
Реализация критических секций с использованием блокирующих переменных имеетсущественный недостаток: в течение времени, когда один процесс находится в критической секции, другой процесс, которому требуется тот же ресурс, будет выполнять рутинные действия по опросу блокирующей переменной, бесполезно тратя процессорное время. Для устранения этого недостатка во многих ОС предусматриваются специальные системные вызовы для работы с критическими секциями. Подобный механизм взаимного исключния реализован в ОС Windows NT.
Обобщением блокирующих переменных являются семафоры Дейкстры. Вместо двоичных используются переменные, принимающие только неотрицательные значения. Такие переменные, используемые для синхронизации вычислительных процессов, называются семафорами.Доступ любого процесса к семафору, за исключением момента его синхронизации, может осуществляться только через две атомарные (неделимые) операции P и V Пусть целая, неотрицательная переменная S представляет собой семафор.
Доступ любого процесса к этой переменной может осуществляться только через две атомарные операции V(S) и P(S), определяемые следующим образом.
V(S) : переменная S увеличивается на 1 одним неделимым действием. К переменной S нет доступа другим процессам во время выполнения этой операции.
P(S) : уменьшение S на 1, если это возможно. Если S=0 и невозможно уменьшить S, оставаясь в области целых неотрицательных значений, то в этом случае процесс, вызывающий операцию P, ждет, пока это уменьшение станет возможным (т.е. блокируется). Успешная проверка и уменьшение также является неделимой операцией. Никакие прерывания во время выполнения примитивов V и P недопустимы.
P(S): if S >=1 then S:=S-1
else WAIT(S) {остановить процесс и поместить его в очередь
ожидания к семафору S}
V(S): ifS<0 then RELEASE(S); {поместить один из ожидающих
процессов очереди
семафора S в очередь готовых процессов}
S:=S+1;
Эта запись означает следующее.
Пытаясь пройти через семафор (выполнение операции P над семафором S), процесс пробует вычесть из его значения 1.Проверить значение семафора S. Если это значение больше или равно 1, процесс проходит сквозь семафор успешно (семафор открыт). Если переменная равна нулю (семафор закрыт), процесс останавливается и ставится в очередь до тех пор, пока S не станет больше 0
Закрытие семафора соответствует захвату ресурса, доступ к которому контролируется этим семафором. Процесс, закрывший семафор, захватывает ресурс. Если ресурс захвачен, остальные процессы вынуждены ждать его освобождения.
Закончив работу с ресурсом (выполнение операция V), процесс увеличивает значение семафора на единицу, открывая его. При этом первый из стоявших в очереди процессов активизируется, вычитает из значения семафора единицу и снова закрывает семафор. Если же очередь была пуста, то ничего не происходит, просто семафор остается открытым. Тогда первый процесс, подошедший к семафору, успешно пройдет через него. Это действительно похоже на работу железнодорожного семафора, контролирующего движение поездов по одноколейной ветке.
В момент создания семафор может быть инициализирован любым неотрицательным значением:
InitSem(Имя_семафора, Начальное_значение_семафора);
Наиболее простым случаем семафора являетсядвоичный семафор. Начальное значение переменная такого семафора может принимать только значения 1 и 0. Двоичный семафор соответствует случаю, когда с разделяемым ресурсом в каждый момент времени может работать только одна программа.
Реализация P- и V-операций для однопроцессороной системы:
type Semaphore = record
счетчик : integer;
указатель : pointer; нетипизированный указатель
end;
var S : Semaphore;
begin
procedure P (var S:Semaphore);
begin
ЗАПРЕТИТЬ ПРЕРЫВАНИЯ;
if S.счетчик >=1
then S.счетчик:=S.счетчик-1
else WAIT(S);{вставить обратившийся процесс в список по
S.указатель и установить на процессор
готовый к выполннию процесс}
РАЗРЕШИТЬ ПРЕРЫВАНИЯ;
end;
procedure V (var S:Semaphore);
begin
ЗАПРЕТИТЬ ПРЕРЫВАНИЯ;
ifS.счетчик<0 then RELEASE(S); {деблокировать первый
процесс из списка по
S.указатель}
S:=S+1;
РАЗРЕШИТЬ ПРЕРЫВАНИЯ;
end;
procedure InitSem (var S:Semaphore);
begin
S.счетчик:=1;
S.указатель:=nil; нулевой указатель
end;
end.
Проанализируем на двух конкурирующих процессах ПР1 и ПР2 использование разработанных семафорных примитивов для решения проблемы критической секции.
var S: Semaphore;
begin
InitSem(S);
parbegin
ПР1: while true do
begin
P(S);
CS1 {критическая секция процесса ПР1}
V(S)
end
and
ПР2: while true do
begin
P(S);
CS2 {критическая секция процесса ПР2}
V(S)
end
parend
end.
Начальное значение семафора S равно 1. Если процессы ПР1 и ПР2 попытаются одновременно выполнить примитив P(S), то это удастся успешно сделать тоько одному из них. Пусть ПР2 в некоторый момент это сделал. Тогда он закрывает семафор (S=0) после чего выполняется его критическая секция. Если в это время процесс ПР1 попытается выпонить примитив P(S), то он будет заблокирован на семафоре S. Тем самым будет гарантировано взаимное искючение.
После выполнения своей критической секции ПР2 выполнит операцию V(S). При этом семафор откроется (S=S+1), а процесс ПР1 переведется в очередь готовности. Если через некотрое время ПР1 будет активизирован, он успешно выполнит P(S) и войде в свою критическую секцию.
Семафоры общего вида (N-ичный семафор) могут принимать любые неотрицательные значения. Это соответствует случаю, когда несколько процессов могут работать с ресурсом одновременно, или когда ресурс состоит из нескольких независимых, но равноценных частей - например, несколько одинаковых принтеров.
При работе с такими семафорами часто разрешают процессам вычитать и добавлять к флаговой переменной значения, большие единицы. Это соответствует захвату/освобождению нескольких частей ресурса.
В связи с проблемой тупиков были выполнено много интересных исследований в области информатики и операционных систем.
Основные направления борьбы с тупиками:
- игнорировать данную проблему
- обнаружение тупиков,
- распознавание тупиков и восстановление системы после тупиков.
- предотвращение тупиков.
Семафоры и семафорные примитивы. Использование семафоров для синхронизации процессов.
Смотри вопрос 32
Семафоры и семафорные примитивы. Задача «поставщик-потребитель».
Семафоры и семафорные примитивы. Задача «производители-потребители: разделенные двоичные семафоры».
Рассмотрим систему из двух параллельных процессов, включающую процесс производитель и процесс-потребитель (рис. 5.6). Процессы взаимодействуют через некоторую обобщенную область памяти – буфер сообщений. В эту область процесс-производитель помещает очередное сообщение, а процесс-потребитель считывает очередное сообщение. В общем случае буфер способен хранить несколько сообщений. Необходимо согласовать работу двух процессов при одностороннем обмене сообщениями по мере развития процессов таким образом, чтобы удовлетворить следующим требованиям:
– выполнять требования задачи взаимного исключения по отношению к критическому ресурсу
– учитывать состояние буфера сообщений, характеризующего возможность или невозможность посылки (принятия) очередного сообщения.
Процесс-производитель при попытке поместить очередное сообщение в полностью заполненный буфер должен быть блокирован. Попытка процесса-потребителя чтения из пустого буфера также должна быть блокирована.
Семафоры и семафорные примитивы. Задача «производители-потребители» с использованием кольцевого буфера.
Семафоры и семафорные примитивы. Задача «писатели-читатели» с приоритетом писателей.
Семафоры и семафорные примитивы. Задача «писатели-читатели» с приоритетом читателей.
Функции операционной системы по управлению памятью.
Память является важнейшим ресурсом, требующим тщательного управления со стороны мультипрограммной операционной системы. Распределению подлежит вся оперативная память, не занятая операционной системой. Обычно ОС располагается в самых младших адресах, однако может занимать и самые старшие адреса. Функциями ОС по управлению памятью являются: отслеживание свободной и занятой памяти, выделение памяти процессам и освобождение памяти при завершении процессов, вытеснение процессов из оперативной памяти на диск, когда размеры основной памяти не достаточны для размещения в ней всех процессов, и возвращение их в оперативную память, когда в ней освобождается место, а также настройка адресов программы на конкретную область физической памяти.
Типы адресов. Понятие виртуального адресного пространства.
Для идентификации переменных и команд используются символьные имена (метки), виртуальные адреса и физические адреса (рисунок 2.7).
Символьные имена присваивает пользователь при написании программы на алгоритмическом языке или ассемблере.
Виртуальные адреса вырабатывает транслятор, переводящий программу на машинный язык. Так как во время трансляции в общем случае не известно, в какое место оперативной памяти будет загружена программа, то транслятор присваивает переменным и командам виртуальные (условные) адреса, обычно считая по умолчанию, что программа будет размещена, начиная с нулевого адреса. Совокупность виртуальных адресов процесса называется виртуальным адресным пространством. Каждый процесс имеет собственное виртуальное адресное пространство. Максимальный размер виртуального адресного пространства ограничивается разрядностью адреса, присущей данной архитектуре компьютера, и, как правило, не совпадает с объемом физической памяти, имеющимся в компьютере.
Рис. 2.7. Типы адресов
Физические адреса соответствуют номерам ячеек оперативной памяти, где в действительности расположены или будут расположены переменные и команды. Переход от виртуальных адресов к физическим может осуществляться двумя способами. В первом случае замену виртуальных адресов на физические делает специальная системная программа - перемещающий загрузчик. Перемещающий загрузчик на основании имеющихся у него исходных данных о начальном адресе физической памяти, в которую предстоит загружать программу, и информации, предоставленной транслятором об адресно-зависимых константах программы, выполняет загрузку программы, совмещая ее с заменой виртуальных адресов физическими.
Второй способ заключается в том, что программа загружается в память в неизмененном виде в виртуальных адресах, при этом операционная система фиксирует смещение действительного расположения программного кода относительно виртуального адресного пространства. Во время выполнения программы при каждом обращении к оперативной памяти выполняется преобразование виртуального адреса в физический. Второй способ является более гибким, он допускает перемещение программы во время ее выполнения, в то время как перемещающий загрузчик жестко привязывает программу к первоначально выделенному ей участку памяти. Вместе с тем использование перемещающего загрузчика уменьшает накладные расходы, так как преобразование каждого виртуального адреса происходит только один раз во время загрузки, а во втором случае - каждый раз при обращении по данному адресу.
В некоторых случаях (обычно в специализированных системах), когда заранее точно известно, в какой области оперативной памяти будет выполняться программа, транслятор выдает исполняемый код сразу в физических адресах.
Распределение памяти фиксированными разделами.