Geum.ru

The design of the unix operating system by Maurice J

Вид материалаРеферат
Подобный материал:
1   ...   44   45   46   47   48   49   50   51   ...   55

│ char *addr1, *addr2; │

│ extern char *shmat(); │

│ extern cleanup(); │

│ │

│ for (i = 0; i < 20; i++) │

│ signal(i,cleanup); │

│ shmid = shmget(SHMKEY,128*K,0777│IPC_CREAT); │

│ addr1 = shmat(shmid,0,0); │

│ addr2 = shmat(shmid,0,0); │

│ printf("addr1 Ox%x addr2 Ox%x\n",addr1,addr2); │

│ pint = (int *) addr1; │

│ │

│ for (i = 0; i < 256, i++) │

│ *pint++ = i; │

│ pint = (int *) addr1; │

│ *pint = 256; │

│ │

│ pint = (int *) addr2; │

│ for (i = 0; i < 256, i++) │

│ printf("index %d\tvalue %d\n",i,*pint++); │

│ │

│ pause(); │

│ } │

│ │

│ cleanup() │

│ { │

│ shmctl(shmid,IPC_RMID,0); │

│ exit(); │

│ } │

L-------------------------------------------------------------

Рисунок 11.11. Присоединение процессом одной и той же области

разделяемой памяти дважды


------------------------------------------------------┐

│ #include │

│ #include │

│ #include │

│ │

│ #define SHMKEY 75 │

│ #define K 1024 │

│ int shmid; │

│ │

│ main() │

│ { │

│ int i, *pint; │

│ char *addr; │

│ extern char *shmat(); │

│ │

│ shmid = shmget(SHMKEY,64*K,0777); │

│ │

│ addr = shmat(shmid,0,0); │

│ pint = (int *) addr; │

│ │

│ while (*pint == 0) │

│ ; │

│ for (i = 0; i < 256, i++) │

│ printf("%d\n",*pint++); │

│ } │

L------------------------------------------------------

Рисунок 11.12. Разделение памяти между процессами


аварийного завершения или перезагрузки.

Дийкстрой был опубликован алгоритм Деккера, описывающий реа-

лизацию семафоров как целочисленных объектов, для которых опреде-

лены две элементарные операции: P и V (см. [Dijkstra 68]). Опера-

ция P заключается в уменьшении значения семафора в том случае,

если оно больше 0, операция V - в увеличении этого значения (и

там, и там на единицу). Поскольку операции элементарные, в любой

момент времени для каждого семафора выполняется не более одной

операции P или V. Связанные с семафорами системные функции явля-

ются обобщением операций, предложенных Дийкстрой, в них допуска-

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

ции уменьшения и увеличения выполняются над значениями,

превышающими 1. Ядро выполняет операции комплексно; ни один из

посторонних процессов не сможет переустанавливать значения сема-

форов, пока все операции не будут выполнены. Если ядро по ка-

ким-либо причинам не может выполнить все операции, оно не выпол-

няет ни одной; процесс приостанавливает свою работу до тех пор,

пока эта возможность не будет предоставлена.

Семафор в версии V системы UNIX состоит из следующих элемен-

тов:

* Значение семафора,

* Идентификатор последнего из процессов, работавших с семафо-

ром,

* Количество процессов, ожидающих увеличения значения семафора,

* Количество процессов, ожидающих момента, когда значение сема-

фора станет равным 0.

Для создания набора семафоров и получения доступа к ним ис-

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

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

значениями семафоров - функция semop.

Таблица семафоров Массивы семафоров

--------┐

│ │ ----T---T---T---T---T---T---┐

│ +------->│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │

│ │ L---+---+---+---+---+---+----

+-------+

│ │ ----T---T---┐

│ +------->│ 0 │ 1 │ 2 │

│ │ L---+---+----

+-------+

│ │ ----┐

│ +------->│ 0 │

│ │ L----

+-------+

│ │ ----T---T---┐

│ +------->│ 0 │ 1 │ 2 │

│ │ L---+---+----

+-------+

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

L--------

Рисунок 11.13. Структуры данных, используемые в работе над

семафорами


Синтаксис вызова системной функции semget:

id = semget(key,count,flag);

где key, flag и id имеют тот же смысл, что и в других механизмах

взаимодействия процессов (обмен сообщениями и разделение памяти).

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

на массив семафоров и содержащую счетчик count (Рисунок 11.13). В

записи также хранится количество семафоров в массиве, время пос-

леднего выполнения функций semop и semctl. Системная функция

semget на Рисунке 11.14, например, создает семафор из двух эле-

ментов.

Синтаксис вызова системной функции semop:

oldval = semop(id,oplist,count);

где id - дескриптор, возвращаемый функцией semget, oplist - ука-

затель на список операций, count - размер списка. Возвращаемое

функцией значение oldval является прежним значением семафора, над


-------------------------------------------------------------┐

│ #include │

│ #include │

│ #include │

│ │

│ #define SEMKEY 75 │

│ int semid; │

│ unsigned int count; │

│ /* определение структуры sembuf в файле sys/sem.h │

│ * struct sembuf { │

│ * unsigned shortsem_num; │

│ * short sem_op; │

│ * short sem_flg; │

│ }; */ │

│ struct sembuf psembuf,vsembuf; /* операции типа P и V */│

│ │

│ main(argc,argv) │

│ int argc; │

│ char *argv[]; │

│ { │

│ int i,first,second; │

│ short initarray[2],outarray[2]; │

│ extern cleanup(); │

│ │

│ if (argc == 1) │

│ { │

│ for (i = 0; i < 20; i++) │

│ signal(i,cleanup); │

│ semid = semget(SEMKEY,2,0777│IPC_CREAT); │

│ initarray[0] = initarray[1] = 1; │

│ semctl(semid,2,SETALL,initarray); │

│ semctl(semid,2,GETALL,outarray); │

│ printf("начальные значения семафоров %d %d\n", │

│ outarray[0],outarray[1]); │

│ pause(); /* приостанов до получения сигнала */ │

│ } │

│ │

│ /* продолжение на следующей странице */ │

L-------------------------------------------------------------

Рисунок 11.14. Операции установки и снятия блокировки


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

имеет следующий формат:

* номер семафора, идентифицирующий элемент массива семафоров,

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

* код операции,

* флаги.


-------------------------------------------------------------┐

│ else if (argv[1][0] == 'a') │

│ { │

│ first = 0; │

│ second = 1; │

│ } │

│ else │

│ { │

│ first = 1; │

│ second = 0; │

│ } │

│ │

│ semid = semget(SEMKEY,2,0777); │

│ psembuf.sem_op = -1; │

│ psembuf.sem_flg = SEM_UNDO; │

│ vsembuf.sem_op = 1; │

│ vsembuf.sem_flg = SEM_UNDO; │

│ │

│ for (count = 0; ; count++) │

│ { │

│ psembuf.sem_num = first; │

│ semop(semid,&psembuf,1); │

│ psembuf.sem_num = second; │

│ semop(semid,&psembuf,1); │

│ printf("процесс %d счетчик %d\n",getpid(),count); │

│ vsembuf.sem_num = second; │

│ semop(semid,&vsembuf,1); │


│ vsembuf.sem_num = first; │

│ semop(semid,&vsembuf,1); │

│ } │

│ } │

│ │

│ cleanup() │

│ { │

│ semctl(semid,2,IPC_RMID,0); │

│ exit(); │

│ } │

L-------------------------------------------------------------

Рисунок 11.14. Операции установки и снятия блокировки

(продолжение)


Ядро считывает список операций oplist из адресного пространс-

тва задачи и проверяет корректность номеров семафоров, а также

наличие у процесса необходимых разрешений на чтение и корректи-

ровку семафоров (Рисунок 11.15). Если таких разрешений не имеет-

ся, системная функция завершается неудачно. Если ядру приходится

приостанавливать свою работу при обращении к списку операций, оно

возвращает семафорам их прежние значения и находится в состоянии

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


-------------------------------------------------------------┐

│ алгоритм semop /* операции над семафором */ │

│ входная информация: (1) дескриптор семафора │

│ (2) список операций над семафором │

│ (3) количество элементов в списке │

│ выходная информация: исходное значение семафора │

│ { │

│ проверить корректность дескриптора семафора; │

│ start: считать список операций над семафором из простран- │

│ ства задачи в пространство ядра; │

│ проверить наличие разрешений на выполнение всех опера- │

│ ций; │

│ │

│ для (каждой операции в списке) │

│ { │

│ если (код операции имеет положительное значение) │

│ { │


│ прибавить код операции к значению семафора; │

│ если (для данной операции установлен флаг UNDO)│

│ скорректировать структуру восстановления │

│ для данного процесса; │

│ вывести из состояния приостанова все процессы, │

│ ожидающие увеличения значения семафора; │

│ } │

│ в противном случае если (код операции имеет отрица-│

│ тельное значение) │

│ { │

│ если (код операции + значение семафора >= 0) │

│ { │

│ прибавить код операции к значению семафо- │

│ ра; │

│ если (флаг UNDO установлен) │

│ скорректировать структуру восстанов- │

│ ления для данного процесса; │

│ если (значение семафора равно 0) │

│ /* продолжение на следующей страни- │

│ * це */ │

L-------------------------------------------------------------

Рисунок 11.15. Алгоритм выполнения операций над семафором


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

ций над семафорами в глобальном списке, оно вновь считывает этот

список из пространства задачи, когда перезапускает системную

функцию. Таким образом, операции выполняются комплексно - или все

за один сеанс или ни одной.

Ядро меняет значение семафора в зависимости от кода операции.

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

значение семафора и выводит из состояния приостанова все процес-

сы, ожидающие наступления этого события. Если код операции равен

0, ядро проверяет значение семафора: если оно равно 0, ядро пере-

ходит к выполнению других операций; в противном случае ядро уве-

личивает число приостановленных процессов, ожидающих, когда зна-

чение семафора станет нулевым, и "засыпает". Если код операции

имеет отрицательное значение и если его абсолютное значение не

превышает значение семафора, ядро прибавляет код операции (отри-

цательное число) к значению семафора. Если результат равен 0, яд-

ро выводит из состояния приостанова все процессы, ожидающие обну-

ления значения семафора. Если результат меньше абсолютного


-------------------------------------------------------------┐

│ вывести из состояния приостанова все │

│ процессы, ожидающие обнуления значе-│

│ ния семафора; │

│ продолжить; │

│ } │

│ выполнить все произведенные над семафором в │

│ данном сеансе операции в обратной последова- │

│ тельности (восстановить старое значение сема- │

│ фора); │

│ если (флаги не велят приостанавливаться) │

│ вернуться с ошибкой; │

│ приостановиться (до тех пор, пока значение се- │

│ мафора не увеличится); │

│ перейти на start; /* повторить цикл с самого │

│ * начала * / │

│ } │

│ в противном случае /* код операции равен нулю */│

│ { │

│ если (значение семафора отлично от нуля) │

│ { │

│ выполнить все произведенные над семафором │

│ в данном сеансе операции в обратной по- │

│ следовательности (восстановить старое │

│ значение семафора); │

│ если (флаги не велят приостанавливаться) │

│ вернуться с ошибкой; │

│ приостановиться (до тех пор, пока значение│

│ семафора не станет нулевым); │

│ перейти на start; /* повторить цикл */ │

│ } │

│ } │

│ } /* конец цикла */ │

│ /* все операции над семафором выполнены */ │

│ скорректировать значения полей, в которых хранится вре-│

│ мя последнего выполнения операций и идентификаторы │

│ процессов; │

│ вернуть исходное значение семафора, существовавшее в │

│ момент вызова функции semop; │

│ } │

L-------------------------------------------------------------

Рисунок 11.15. Алгоритм выполнения операций над семафором

(продолжение)


значения кода операции, ядро приостанавливает процесс до тех пор,

пока значение семафора не увеличится. Если процесс приостанавли-

вается посреди операции, он имеет приоритет, допускающий прерыва-

ния; следовательно, получив сигнал, он выходит из этого состоя-

ния.

Перейдем к программе, представленной на Рисунке 11.14, и

предположим, что пользователь исполняет ее (под именем a.out) три

раза в следующем порядке:

a.out &

a.out a &

a.out b &

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

бор семафоров из двух элементов и присваивает каждому семафору

значение, равное 1. Затем процесс вызывает функцию pause и приос-

танавливается для получения сигнала, после чего удаляет семафор

из системы (cleanup). При выполнении программы с параметром 'a'

процесс (A) производит над семафорами в цикле четыре операции: он

уменьшает на единицу значение семафора 0, то же самое делает с

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

вает значения семафоров 0 и 1. Если бы процесс попытался умень-

шить значение семафора, равное 0, ему пришлось бы приостановить-

ся, следовательно, семафор можно считать захваченным (недоступным

для уменьшения). Поскольку исходные значения семафоров были равны

1 и поскольку к семафорам не было обращений со стороны других

процессов, процесс A никогда не приостановится, а значения сема-

форов будут изменяться только между 1 и 0. При выполнении прог-

раммы с параметром 'b' процесс (B) уменьшает значения семафоров 0

и 1 в порядке, обратном ходу выполнения процесса A. Когда про-

цессы A и B выполняются параллельно, может сложиться ситуация, в

которой процесс A захватил семафор 0 и хочет захватить семафор 1,

а процесс B захватил семафор 1 и хочет захватить семафор 0. Оба

процесса перейдут в состояние приостанова, не имея возможности

продолжить свое выполнение. Возникает взаимная блокировка, из ко-

торой процессы могут выйти только по получении сигнала.

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

могут выполнять одновременно несколько операций над семафорами. В

последнем примере желаемый эффект достигается благодаря использо-

ванию следующих операторов:

struct sembuf psembuf[2];

psembuf[0].sem_num = 0;

psembuf[1].sem_num = 1;

psembuf[0].sem_op = -1;


psembuf[1].sem_op = -1;

semop(semid,psembuf,2);

Psembuf - это список операций, выполняющих одновременное уменьше-

ние значений семафоров 0 и 1. Если какая-то операция не может вы-

полняться, процесс приостанавливается. Так, например, если значе-

ние семафора 0 равно 1, а значение семафора 1 равно 0, ядро оста-

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

и то, и другое.

Установка флага IPC_NOWAIT в функции semop имеет следующий

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

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

мафора выше определенного уровня или, наоборот, снижения этого

значения до 0, и если при этом флаг IPC_NOWAIT установлен, ядро

выходит из функции с извещением об ошибке. Таким образом, если не

приостанавливать процесс в случае невозможности выполнения от-

дельной операции, можно реализовать условный тип семафора.

Если процесс выполняет операцию над семафором, захватывая при

этом некоторые ресурсы, и завершает свою работу без приведения

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

Причинами возникновения таких ситуаций могут быть как ошибки

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

нию выполнения процесса. Если после того, как процесс уменьшит

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

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

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

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

ны, хотя сам заблокировавший их процесс уже прекратил свое су-

ществование. Чтобы избежать возникновения подобных ситуаций, в

функции semop процесс может установить флаг SEM_UNDO; когда про-

цесс завершится, ядро даст обратный ход всем операциям, выполнен-

ным процессом. Для этого в распоряжении у ядра имеется таблица, в

которой каждому процессу в системе отведена отдельная запись. За-

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


Заголовки частных структур

восстановления Структуры восстановления

-------┐

│ │

│ │

│ │

│ │ -----------┐ -----------┐ -----------┐

+------+ │Дескриптор│ │Дескриптор│ │Дескриптор│

│ +-->│ Номер +-->│ Номер +-->│ Номер │

+------+ │ Значение │ │ Значение │ │ Значение │

│ │ L----------- L----------- L-----------

│ │ -----------┐

+------+ │Дескриптор│

│ +-->│ Номер │

+------+ │ Значение │

│ │ L-----------

│ │

│ │

│ │

│ │

│ │

L-------

Рисунок 11.16. Структуры восстановления семафоров


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

(Рисунок 11.16). Каждая структура восстановления состоит из трех

элементов - идентификатора семафора, его порядкового номера в на-

боре и установочного значения.

Ядро выделяет структуры восстановления динамически, во время

первого выполнения системной функции semop с установленным флагом

SEM_UNDO. При последующих обращениях к функции с тем же флагом

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

ках структуры с тем же самым идентификатором и порядковым номером

семафора, что и в формате вызова функции. Если структура обнару-

жена, ядро вычитает значение произведенной над семафором операции

из установочного значения. Таким образом, в структуре восстанов-

ления хранится результат вычитания суммы значений всех операций,

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

SEM_UNDO. Если соответствующей структуры нет, ядро создает ее,

сортируя при этом список структур по идентификаторам и номерам

семафоров. Если установочное значение становится равным 0, ядро

удаляет структуру из списка. Когда процесс завершается, ядро вы-

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