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

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

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

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

Для устранения таких ситуаций может быть использован так называемый аппарат событий. С помощью этого средства могут решаться не только проблемы взаимного исключения, но и более общие задачи синхронизации процессов. В разных операционных системах аппарат событий реализуется по своему, но в любом случае используются системные функции аналогичного назначения, которые условно назовем WAIT(x) и POST(x), где x - идентификатор некоторого события. Если ресурс занят, то процесс не выполняет циклический опрос, а вызывает системную функцию WAIT(D), здесь D обозначает событие, заключающееся в освобождении ресурса D. Функция WAIT(D) переводит активный процесс в состояние ОЖИДАНИЕ и делает отметку в его дескрипторе о том, что процесс ожидает события D. Процесс, который в это время использует ресурс D, после выхода из критической секции выполняет системную функцию POST(D), в результате чего операционная система просматривает очередь ожидающих процессов и переводит процесс, ожидающий события D, в состояние ГОТОВНОСТЬ.

Обобщающее средство синхронизации процессов предложил Дейкстра, который ввел два новых примитива. В абстрактной форме эти примитивы, обозначаемые P и V, оперируют над целыми неотрицательными переменными, называемыми семафорами.

Пусть S такой семафор. Операции определяются следующим образом:

V(S): переменная S увеличивается на 1 одним неделимым действием; выборка, инкремент и запоминание не могут быть прерваны, и к S нет доступа другим процессам во время выполнения этой операции.

P(S): уменьшение S на 1, если это возможно. Если S=0, то невозможно уменьшить S и остаться в области целых неотрицательных значений, в этом случае процесс, вызывающий P-операцию, ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение также является неделимой операцией.

В частном случае, когда семафор S может принимать только значения 0 и 1, он превращается в блокирующую переменную. Операция P заключает в себе потенциальную возможность перехода процесса, который ее выполняет, в состояние ожидания, в то время как V-операция может при некоторых обстоятельствах активизировать другой процесс, приостановленный операцией P (сравните эти операции с системными функциями WAIT и POST).

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

Введем два семафора: e - число пустых буферов и f - число заполненных буферов. Предположим, что запись в буфер и считывание из буфера являются критическими секциями (как в примере с принт-сервером в начале данного раздела). Введем также двоичный семафор b, используемый для обеспечения взаимного исключения. Тогда процессы могут быть описаны следующим образом:

// Глобальные переменные

#define N 256

int e = N, f = 0, b = 1;

void Writer ()

{

while(1)

{

PrepareNextRecord(); /* подготовка новой записи */

P(e); /* Уменьшить число свободных буферов, если они есть */

/* в противном случае - ждать, пока они освободятся */

P(b); /* Вход в критическую секцию */

AddToBuffer(); /* Добавить новую запись в буфер */

V(b); /* Выход из критической секции */

V(f); /* Увеличить число занятых буферов */

}

}

void Reader ()

{

while(1)

{

P(f); /* Уменьшить число занятых буферов, если они есть */

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

P(b); /* Вход в критическую секцию */

GetFromBuffer(); /* Взять запись из буфера */

V(b); /* Выход из критической секции */

V(e); /* Увеличить число свободных буферов */

ProcessRecord(); /* Обработать запись */

} }

1.2.4.3 Тупики

Приведенный выше пример поможет проиллюстрировать еще одну проблему синхронизации - взаимные блокировки, называемые также дедлоками (deadlocks), клинчами (clinch) или тупиками.

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

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

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

Проблема тупиков включает в себя следующие задачи:

­ предотвращение тупиков;

­ распознавание тупиков;

­ восстановление системы после тупиков.

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

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

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

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

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

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

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

1.2.4.4 Потоки

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

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

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

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

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

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

Нити иногда называют облегченными процессами или мини-процессами. Действительно, нити во многих отношениях подобны процессам. Каждая нить выполняется строго последовательно и имеет свой собственный программный счетчик и стек. Нити, как и процессы, могут, например, порождать нити-потомки, могут переходить из состояния в состояние. Подобно традиционным процессам (то есть процессам, состоящим из одной нити), нити могут находиться в одном из следующих состояний: ВЫПОЛНЕНИЕ, ОЖИДАНИЕ и ГОТОВНОСТЬ. Пока одна нить заблокирована, другая нить того же процесса может выполняться. Нити разделяют процессор так, как это делают процессы, в соответствии с различными вариантами планирования.

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

Итак, нити имеют собственные: программный счетчик, стек, регистры, нити-потомки, состояние.

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

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

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

1.2.5 Системные вызовы операций управления процессами

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

СИСТЕМНЫЙ ВЫЗОВ FORK

Системный вызов fork (порождение нового процесса) имеет следующий формат:

int pid = fork()

Системный вызов fork служит для создания нового процесса. Новый процесс (процесс-потомок) является полной копией процесса-предка, за исключением того, что процесс-потомок имеет свой уникальный идентификатор процесса (РID). Поскольку новый процесс сам может выступать в качестве порождающего, его идентификатор процесса-предка (РРID), естественно, отличается от соответствующего идентификатора породившего его процесса.

Новый процесс имеет собственную копию таблицы дескрипторов открытых файлов, но эти дескрипторы ссылаются на те же самые файлы, что и дескрипторы процесса-предка, и имеют с ним общие указатели позиций чтения/записи. Так, при выполнении операции 1sееk в порожденном процессе, может измениться и позиция чтения/записи файла в процессе-предке. Это свойство, в частности, используется командными языками SН СSН для переопределения файлов стандартного ввода/вывода и организации конвейеров команд.

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

В случае успешного завершения, системный вызов fork возвращает значение 0 порожденному процессу и идентификатор нового процесса - породившему. При неудачном завершении вызова возвращается значение -1.

СИСТЕМНЫЙ ВЫЗОВ VFORK

Системный вызов vfork (порождение нового процесса) имеет следующий формат:

int pid = vfork()

Системный вызов vfork используется для создания нового процесса без полного копирования адресного пространства процесса-предка, что более эффективно, особенно при страничной организации памяти. В отличие от вызова fork процесс-потомок разделяет память породившего его процесса до своего завершения (см. описание вызова ехit или смены программы (см. описание вызова ехесvе). Процесс-предок временно приостанавливается, когда процесс-потомок использует его ресурсы.

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

Для предотвращения взаимной блокировки, процесс-потомок. в период выполнения вызова vfork никогда не посылает сигналы SIGTTOU и SIGTTIN. Вернее, разрешен вывод на управляющий терминал, но при попытке ввода будет зафиксирован конец файла.

СИСТЕМНЫЙ ВЫЗОВ WAIT

Системный вызов wait (ожидание завершения процесса-потомка) имеет следующий формат:

int pid = wait (int *status)

int pid = wait(0)

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

При успешном завершении вызова wait, значение status всегда не равно нулю и содержит код возврата и статус завершения порождённого процесса. Если порождающий процесс завершается, не ожидая своих потомков, их наследует стартовый процесс (РID=1).

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

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

СИСТЕМНЫЙ ВЫЗОВ EXIT

Системный вызов exit (завершить процесс) имеет следующий формат:

int exit (int arg)

Параметр arg имеет смысл, определенный в описании вызова wait.

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

Ниже приводится пример использования системных вызовов fork, wait, exit

main ()

{

int pid, status, died;

switch (pid=fork()) /* порождаем новый процесс */

{

саsе -1: /* аварийное завершение*/

printf (“Can't fork\n”);

ехit(-1);

саsе 0: /* процесс-потомок */

рrintf (“I am the child\n”);

exit (3);

default: /* процесс предок ожидает окончание процесса-потомка */

died = wait (&status); }

printf (“Child was %d\n”, pid);

printf (“ %d died \n”, died);

printf (“Exit value %d\n”, status>>8);

printf (“Exit status %d\n”, status &0377);

exit (0);

}

СИСТЕМНЫЕ ВЫЗОВЫ ЕХЕС1, ЕХЕС1Е, ЕХЕСV И ЕХЕСVЕ

Системные вызовы ехес1, ехес1е, ехесv и ехесvе (выполнить файл) имеют форматы:

char *name;

char *arg0, *arg1, *arg2, …

execl (name, arg0, arg1, arg2, …, 0)

char *name;

char *arg0, *arg1, *arg2, …

char *envp[ ];

execle (name, arg0, arg1, arg2, …, 0, envp)

char *name, *arg[ ];

execv (name, argv)

char *name, *arg[ ], *envp[ ];

execve (name, argv, envp)

Системные вызовы ехес1, ехес1е, ехесv и ехесvе заменяют программу текущего процесса. Новая программа загружается из файла с именем namе, который либо является исполняемым, либо содержит интерпретируемую программу.

Исполняемый файл должен иметь соответствующий формат. Значения передаваемых параметров содержатся:

- для системных вызовов ехес1 и ехес1е - в списке указателей на строки аrg0, arg1...;

- для системных вызовов ехесv и ехесvе - в массиве argv, в виде текстовых строк.

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

Массив envp содержит имена и значения макропеременных среды процесса. Новая программа наследует все открытые файлы, за исключением тех, для которых установлен флаг с1оsе-оn-ехес. Все сигналы, которые игнорировались до выполнения вызовов ехес1, ехес1е, ехесv и ехесvе, будут игнорироваться и после их выполнения. Однако, все установленные ранее варианты реакций на сигналы заменяются на стандартные.

Каждый процесс имеет реальные и эффективные идентификаторы пользователя и группы. Реальные идентификаторы соответствуют идентификаторам пользователя, который запустил данный процесс, а эффективные определяют права доступа процесса.

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

int argc;

char *argv, *envp;

main (argc, argv, envp),

где argc - количество аргументов в массиве argv;

argv - массив символьных указателей на сами аргументы.

Возврат из системных вызовов ехес1, ехес1е, ехесv, ехесvе всегда означает ошибку. При этом возвращается значение -1 и код ошибки в переменной еггnо. Если данный процесс выполняется в привилегированном режиме, то его полномочия не изменяются, даже если статус файла содержит признак set UID (set-GID).

Ниже приводится пример использования системных вызовов fork, wait, exit, execl.

main()

{

int pid, status;

switch(pid=fork()) /* порождаем новый процесс */

{

case -1: /* аварийное завершение */

printf (“Can' t fork\n”);

exit(1);

case 0: /* процесс-потомок */

printf (“I am the child\n”);

execl (“/bin/echo”, “echo”, “Hello mike!”, 0);

/* запускаем команду echo “Hello mike!” */

printf (“Exec error\n”); /* процесс предок */

wait (&status);

/* ожидаем завершение процесса-потомка */

}

/* Процесс-отец выводит на экран код завершения и статус завершения

процесса-потомка */

printf (“Exit value %d\n”, status>>8);

printf (“Exit status %d\n, status & 0377);

exit(0);}

СИСТЕМНЫЙ ВЫЗОВ GETPID

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

int getpid( )

СИСТЕМНЫЕ ВЫЗОВЫ GETGID, GETEGID

Системные вызовы getgid, getegid (запрос идентификатора группы) имеют форматы:

int getgid( )

int getegid( )

Вызов getgid возвращает реальный идентификатор группы текущего процесса, а вызов getegid - эффективный идентификатор группы. Реальный идентификатор группы определяется при регистрации в системе. Эффективный идентификатор определяет дополнительные права доступа при выполнении программы в режиме set-GID (установка идентификатора группы владельца выполняемого файла).

СИСТЕМНЫЕ ВЫЗОВЫ GETUID, GETEUID

Системные вызовы getuid, geteuid (запрос идентификатора пользователя) имеют следующие форматы:

int getuid ( )

int geteuid ( )

Системный вызов getuid возвращает реальный идентификатор пользователя для текущего процесса, a geteuid возвращает эффективный идентификатор пользователя. Реальный идентификатор пользователя совпадает с идентификатором, под которым пользователь зарегистрировав в системе. Эффективный идентификатор определяет права доступа пользователя в текущий момент.

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

СИСТЕМНЫЙ ВЫЗОВ SETGID

Системный вызов setgid (установить реальный идентификатор группы процесса) имеет формат:

setgid (rgid) int rgid;

Системный вызов setgid устанавливает идентификатор группы текущего процесса в соответствии с значением параметра rgid. Изменять реальный идентификатор группы можно только в процессе, работающем в привилегированном режиме. В обычном режиме допускает только замена эффективного идентификатора на значение соответствующее реальному идентификатору группы процесса. При успешном завершении, возвращается значение 0, иначе -значение -1 и код ошибки в переменной еrrnо. Код ошибки может принимать значение

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

СИСТЕМНЫЙ ВЫЗОВ SETUID

Системный вызов setuid (установить реальный идентификаторы пользователя) имеет следующий формат:

setuid (ruid) int ruid;

Системный вызов setuid устанавливает текущему процессу реальный идентификатор пользователя в соответствии со значением параметра ruid. Изменять реальный идентификатор пользователя можно только в процессе, работающем в привилегированном режиме. В обычном режиме допускается только замена эффективного идентификатора на значение, соответствующее реальному идентификатору. При успешном завершении вызова, возвращается значение О, иначе - значение -1 и код ошибки в переменной еrrnо. Код ошибки:

[EPERM] - текущий процесс не является привилегированным, и были специфицированы изменения, отличные от замены эффективного идентификатора на реальный.

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

main ( )

{

int pid,uid, gid;

int euid, egid;

pid = getpid();

uid *= getuid();

gid = getgid;

euid = geteuid();

egid = getegid();

printf("\tProcess: PID = %d\n", pid);

printf (“uid = %d gid = %d\n", uid, gid);

printf("euid = %d egid = %d\n", euid, egid);

}

СИСТЕМНЫЙ ВЫЗОВ NICE

Системный вызов nice (установить процессу приоритет) имеет следующий формат:

nice (incr)

Системный вызов nice устанавливается текущему процессу новый приоритет, равный текущему приоритету плюс значение аргумента incr. Значение аргумента incr должно лежать в определенном диапазоне, конкретные границы которого зависят от версии ОС UNIX.

UNIX 7. Диапазон значений incr лежит в пределах от -20 до 20. Отрицательное приращение может задавать только привилегированный пользователь.

UNIX System V. Диапазон значений incr лежит в пределах от 0 до 39. Приращения, выходящие за границы этого диапазона, уменьшаются до граничных значений. Чем выше значение аргумента incr, тем ниже устанавливаемый приоритет.

При успешном завершении вызова, возвращается новоезначение приоритета минус 20, иначе - значение -1 и код ошибки в переменной еrrnо.

Код ошибки:

[EPERM] Значение incr не лежит в пределах установленного диапазона и эффективный идентификатор владельца процесса не является идентификатором суперпользователя.

Приведенная ниже программа является исходнымтекстом команды nice UNIX версии System V (вызова какой-либо команды на выполнение с измененным приоритетом):

nice {приращение приоритета} команда

#inc1ude <stdio.h>

#include<ctype.h>

main (argc, argv) int argc; char *argv [];

{

int nicarg = 10; /* приращение приоритета по умолчанию */

extern errno;

/* Разбираем аргументы команды */

if(argc > 1 && argv[l][0] = `-`) { /* если задано приращение приоритета */

register char *p = argv[l];

if(*++p != `-`) --р;

whi1e(*++p)

if(!isdigit(*p)) { /* указано не числовое значение */

fprintf(stderr, "nice: argument must be numeric.\n");

exit(2); }

nicarg == atoi (&argv[l] [1]);

/* в переменной nicarg записываем значение приращения приоритета */

argc--;

argv++;

}

if (argc < 2) { /* если не задана команда */

fprintf(stderr, "nice: usage: nice [-num] command\n");

exit(2);

}

nice(nicarg); /* изменяем приоритет процесса */

execvp(argv [1], &argv[l]); /* выполняем команду */

fprintf(stderr. "%s: %d\n", argv[l], errno);

/* если ошибка при запуске команды, то печатаем переменную errno */

exit(2); }

Контрольные вопросы ко второй главе

1. Что такое процесс?

2. Что такое контекст процесса?

3. Что такое дескриптор процесса?

4. Какие состояния процесса Вы знаете?

5. Охарактеризуйте граф состояний запущенного процесса.

6. В чем отличие заблокированных состояний процесса: "ожидание", "готовность"?

7. Что такое очередь процессов?

8. Какие виды очередей Вы знаете?

9. Каков алгоритм работы операционной системы при вытесняющей многозадачности?

10. Каков алгоритм работы операционной системы при невытесняющей многозадачности?

11. Что такое приоритет процесса? Где хранится информация о нем?

12. Каков алгоритм работы операционной системы при использовании метода абсолютной приоритетности?

13. Каков алгоритм работы операционной системы при использовании метода относительной приоритетности?

14. Что такое гонки процессов?

15. Что такое критическая секция программы?

16. Для чего используются блокирующие переменные?

17. Что такое семафоры? Приведите пример программы с их использованием?

18. Что такое аппарат событий? Каков алгоритм работы планировщика ОС при использовании данного метода?

19. Что такое разделяемые ресурсы?

20. Что такое тупик? Какие существуют методы борьбы с тупиками?

21. Что такое поток?

22. С какой целью используется многопотоковая обработка данных?

23. Какие команды в Unix-системах используются для отображения информации о запущенных в системе процессах?

24. Что такое процесс-демон Unix-системы?

25. Как изменить приоритет процесса в Unix-системе, с какой целью это необходимо делать?

26. Как запустить задачу в плановом режиме в Unix-системе?

27. Как уничтожить запущенный в Unix-системе процесс?

28. Какие используются системные вызовы при работе с процессами в Unix-системе?

1.3 Управление оперативной памятью

1.3.1 Адресация

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

­ отслеживание свободной и занятой памяти;

­ выделение памяти процессам и освобождение памяти при завершении процессов;

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

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

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

Символьные имена присваивает пользователь при написании программы на алгоритмическом языке или ассемблере.

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

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

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

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

1.3.2 Методы распределения памяти

Рисунок 3.1 - Методы распределения оперативной памяти

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

1.3.2.1 Методы распределения памяти без использования дискового пространства

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

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

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

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

Перемещаемые разделы

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

1.3.2.2 Методы распределения памяти с использованием дискового пространства

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

Страничное распределение

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

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

Размер страницы обычно выбирается равным степени двойки: 512, 1024 и т.д., это позволяет упростить механизм преобразования адресов.

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

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

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

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

­ дольше всего не использовавшаяся страница;

­ первая попавшаяся страница;

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

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

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

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

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

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

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

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

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

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

Свопинг

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