Шпаргалка по "Системное програмное обеспечение"

Нить 1

Нить 2

Создать нить 2

Переключение контекста нитей

Ожидание ввода a и b

Переключение контекста нитей

Ввести массив a

Ожидание окончания операции ввода

Ввести массив b

Ожидание окончания операции ввода

Ввести массив с

Ожидание окончания операции ввода    

Переключение контекста нитей

a = a + b

Переключение контекста нитей

c = a + c

Вывести массив с

Ожидание окончания операции вывода

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

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

19. Преимущества и недостатки потокового обмена данными

На предыдущем семинаре мы познакомились с механизмами, обеспечивающими потоковую передачу данных между процессами в операционной системе UNIX, а именно с pip'ами и FIFO. Потоковые механизмы достаточно просты в реализации и удобны для использования, но имеют ряд существенных недостатков:

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

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

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

20. Дескрипторы System V IPC

Мы говорили (см. семинар 5 раздел "Файловый дескриптор" ), что информацию о потоках ввода-вывода, с которыми имеет дело текущий процесс, в частности о pip'ах и FIFO, операционная система хранит в таблице открытых файлов процесса. Системные вызовы, осуществляющие операции над потоком, используют в качестве параметра индекс элемента таблицы открытых файлов, соответствующего потоку, – файловый дескриптор. Использование файловых дескрипторов для идентификации потоков внутри процесса позволяет применять к ним уже существующий интерфейс для работы с файлами, но в то же время приводит к автоматическому закрытию потоков при завершении процесса. Этим, в частности, объясняется один из перечисленных выше недостатков потоковой передачи информации.

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

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

21. Синхронизация процессов и нитей исполнения

Все рассмотренные на этом семинаре примеры являются не совсем корректными. В большинстве случаев они работают правильно, однако возможны ситуации, когда совместная деятельность этих процессов или нитей исполнения приводит к неверным и неожиданным результатом. Это связано с тем, что любые неатомарные операции, связанные с изменением содержимого разделяемой памяти, представляют собой критическую секцию процесса или нити исполнения. Вернемся к рассмотрению программ /ftp/pub/sem6-7/stud/06-1a.c и /ftp/pub/sem6-7/stud/06-1b.c. При одновременном существовании 2-х процессов в операционной системе может возникнуть следующая последовательность выполнения операций во времени:

...
Процесс 1: array[0] += 1;
Процесс 2: array[1] += 1;
Процесс 1: array[2] += 1;
Процесс 1: printf("Program 1 was spawn %d times, program 2 - %d times, total - %d times\n", array[0], array[1], array[2]);
...

Тогда печать будет давать неправильные результаты. Естественно, что воспроизвести подобную последовательность действий практически нереально. Мы не сможем подобрать необходимые времена старта процессов и степень загруженности вычислительной системы. Но мы можем смоделировать эту ситуацию, добавив в обеих программах достаточно длительные пустые циклы перед оператором array[2] += 1; Это проделано в программах /ftp/pub/sem6-7/stud/06-3a.c и /ftp/pub/sem6-7/stud/06-3b.c. Откомпилируем их, запустим любую из них один раз для создания и инициализации разделяемой памяти. Затем запустим другую и, пока она находится в цикле, запустим, например, с другого виртуального терминала, снова первую. Мы получим неожиданный результат. Как видим, для написания корректно работающих программ необходимо обеспечивать взаимоисключение при работе с разделяемой памятью и, может быть, взаимную очередность доступа к ней. Это можно сделать с помощью рассмотренных на лекции алгоритмов синхронизации, например, алгоритма Петерсона или алгоритма булочной.

22. Семафоры в UNIX

В материалах предыдущего семинара речь шла о необходимости синхронизации работы процессов для их корректного взаимодействия через разделяемую память. Как упоминалось в лекции 6, одним из первых механизмов, предложенных для синхронизации поведения процессов, стали семафоры, концепцию которых описал Дейкстра (Dijkstra) в 1965 году. При разработке средств System V IPC семафоры вошли в их состав как неотъемлемая часть. Следует отметить, что набор операций над семафорами System V IPC отличается от классического набора операций {P, V}, предложенного Дейкстрой. Он включает три операции:

•A(S, n) – увеличить значение семафора S на величину n;

•D(S, n) – пока значение семафора S < n, процесс блокируется. Далее S = S - n;

•Z(S) – процесс блокируется до тех пор, пока значение семафора S не станет равным 0.

Изначально все IPC-семафоры инициируются нулевым значением.

Мы видим, что классической операции P(S) соответствует операция D(S,1), а классической операции V(S) соответствует операция A(S,1). Аналогом ненулевой инициализации семафоров Дейкстры значением n может служить выполнение операции A(S,n) сразу после создания семафора S, с обеспечением атомарности создания семафора и ее выполнения посредством другого семафора. Мы показали, что классические семафоры реализуются через семафоры System V IPC. Обратное не является верным. Используя операции P(S) и V(S), мы не сумеем реализовать операцию Z(S).

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

23. Создание очереди сообщений или доступ к уже существующей

Системный вызов msgget()

Для создания очереди сообщений, ассоциированной с определенным ключом, или доступа по ключу к уже существующей очереди используется системный вызов msgget(), являющийся аналогом системных вызовов shmget() для разделяемой памяти и semget() для массива семафоров, который возвращает значение IPC-дескриптора для этой очереди. При этом существуют те же способы создания и доступа, что и для разделяемой памяти или семафоров (см. семинары 6–7 раздел "Разделяемая память в UNIX. Системные вызовы shmget(), shmat(), shmdt()" и см. семинар 8 раздел "Создание массива семафоров или доступ к уже существующему. Системный вызов semget()", соответственно).

Системный вызов msgget()

Прототип системного вызова

#include <types.h>

#include <ipc.h>

#include <msg.h>

int msgget(key_t key, int msgflg);

Описание системного вызова

Системный вызов msgget предназначен для выполнения операции доступа к очереди сообщений и, в случае ее успешного завершения, возвращает дескриптор System V IPC для этой очереди (целое неотрицательное число, однозначно характеризующее очередь сообщений внутри вычислительной системы и использующееся в дальнейшем для других операций с ней).

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

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

•IPC_CREAT — если очереди для указанного ключа не существует, она должна быть создана;

•IPC_EXCL — применяется совместно с флагом IPC_CREAT. При совместном их использовании и существовании массива с указанным ключом доступ к очереди не производится и констатируется ошибочная ситуация, при этом переменная errno, описанная в файле <errno.h>, примет значение EEXIST;

•0400 — разрешено чтение для пользователя, создавшего очередь;

•0200 — разрешена запись для пользователя, создавшего очередь;

•0040 — разрешено чтение для группы пользователя, создавшего очередь;

•0020 — разрешена запись для группы пользователя, создавшего очередь;

•0004 — разрешено чтение для всех остальных пользователей;

•0002 — разрешена запись для всех остальных пользователей;

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

ipcs -l Возвращаемое значение

Системный вызов возвращает значение дескриптора System V IPC для очереди сообщений при нормальном завершении и значение -1 при возникновении ошибки.

24. Сообщения как средства связи и средства синхронизации процессов

В материалах предыдущих семинаров были представлены такие средства организации взаимодействия процессов из состава средств System V IPC, как разделяемая память (семинары 6–7) и семафоры (семинар 8). Третьим и последним, наиболее семантически нагруженным средством, входящим в System V IPC, являются очереди сообщений. В лекции 6 говорилось о модели сообщений как о способе взаимодействия процессов через линии связи, в котором на передаваемую информацию накладывается определенная структура, так что процесс, принимающий данные, может четко определить, где заканчивается одна порция информации и начинается другая. Такая модель позволяет задействовать одну и ту же линию связи для передачи данных в двух направлениях между несколькими процессами. Мы также рассматривали возможность использования сообщений с встроенными механизмами взаимоисключения и блокировки при чтении из пустого буфера и записи в переполненный буфер для организации синхронизации процессов.

25. Операции над очередями сообщений

В справочной статье msgop синтаксис упомянутых системных вызовов описан так:

#include <sys/types.h>

#include <sys/ipc.h>

#include <sys/msg.h>

int msgsnd (int msqid, struct msgbuf * msgp, int msgsz, int msgflg)

int msgrcv (int msqid, struct msgbuf * msgp, int msgsz, long msgtyp,

    int msgflg)

При успешном завершении системного вызова msgsnd() результат равен нулю; в случае неудачи возвращается -1. В качестве аргумента msqid должен выступать идентификатор очереди сообщений, предварительно полученный при помощи системного вызова msgget. Аргумент msgp является указателем на структуру в области памяти пользователя, содержащую тип посылаемого сообщения и его текст. Аргумент msgsz специфицирует длину массива символов в структуре данных, указываемой аргументом msgp, то есть длину сообщения. Максимально допустимый размер данного массива определяется системным параметром MSGMAX.

Отметим, что значение поля msg_qbytes у ассоциированной структуры данных может быть уменьшено с предполагаемой по умолчанию величины MSGMNB при помощи управляющего действия IPC_SET системного вызова msgctl, однако впоследствии увеличить его может только суперпользователь. Аргумент msgflg позволяет специфицировать выполнение над сообщением ``операции с блокировкой''; для этого флаг IPC_NOWAIT должен быть сброшен (msgflg & IPC_NOWAIT = 0). Блокировка имеет место, если либо текущее число байт в очереди уже равно максимально допустимому значению для указанной очереди (то есть значению поля msg_qbytes или MSGMNB), либо общее число сообщений во всех очередях равно максимально допустимому системой (системный параметр MSGTQL). Если в такой ситуации флаг IPC_NOWAIT установлен, системный вызов msgsnd() завершается неудачей и возвращает -1.