Запрограммируйте псевдокодом (синтаксически основанным на паскале или си) решение проблемы производителя и потребителя

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

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

В 1965г. Дейкстра (E.W. Dijkstra) предложил использовать специальную переменную целого типа, получившую название — семафор. Семафор связывается с совместно используемым ресурсом. Каждое обращение к ресурсу абстрактно будем называть сигналом активизации.

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

Над семафорами определены две операции:

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

2. up(sem) — увеличивает значение семафора на 1. При этом если с этим семафором связаны один или более ожидающих процессов, которые не могут завершить более раннюю операцию down(), а это означает что значение семафора равно 0, один из ожидающих процессов будет выбран системой и ему будет разрешено завершить down().

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

Решение проблемы производителя и потребителя с помощью семафоров #define N 100; /* Определяем размер буфера(в ячейки) */ typedef int semaphore; /* Задаём тип "семафор" как целый */ semaphore mutex = 1; /* Контроль входа в критическую область */ semaphore empty = N; /* Число свободных ячеек буфера */ semaphore full = 0; /* Число занятых ячеек буфера */ void producer(){ /* Переменная "элемент", в неё будем класть вновь созданный элемент, для дальнейшей отправки в буфер */ int item; /* Бесконечный цикл */ while (TRUE){ /* Создать элемент */ item=produce_item(); /* Уменьшить empty */ down(empty); /* Войти в критическую область*/ down(mutex); /* Поместить в буфер созданный элемент */ put_item(item); /* Выход из критической области */ up(mutex); /* Увеличить full */ up(full); } } void consumer(){ /* Переменная "элемент", в неё будем класть взятый из буфера для обработки элемент */ int item; /* Бесконечный цикл */ while (TRUE){ /* Уменьшить full */ down(full); /* Войти в критическую область*/ down(mutex); /* Поместить в буфер созданный элемент */ item=get_item(); /* Выход из критической области */ up(mutex); /* Увеличить empty */ up(empty); /* Обработка элемента */ consum_item(item); } }

В представленном в примере решении используются три семафора: один для подсчета заполненных сегментов буфера (full), другой для подсчета пустых сегментов (empty), а третий предназначен для исключения одновременного доступа к буферу произ­водителя и потребителя (mutex). Значение счетчика full исходно равно нулю, счетчик empty равен числу сегментов в буфере, a mutex равен 1. Рассмотрим действия обоих процессов пошагово.

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

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

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

Для ОС Linux задайте режим доступа к файлу, позволяющий владельцу файла чтение, запись и исполнение, группе — только чтение, прочим пользователям — ничего. Постройте соответствующий 8-чный код. Объясните, будет работать такой режим доступа, если установить его для каталога.

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

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

Выполнив команду ls –l рассмотрим листинг

[user]$ ls -l /bin/ls

-rwxr-xr-x 1 root root 49940 Sep 12 1999 /bin/ls

В данном случае владельцем файла является пользователь root и группа root. Первое поле в выводе показывает тип файла и права доступа к файлу. Это поле в приведенном примере представлено цепочкой символов -rwxr-xr-x. Эти символы можно условно разделить на 4 группы.

Первая группа, состоящая из единственного символа, определяет тип файла. Этот символ в соответствии с возможными типами файлов, рассмотренными в предыдущем разделе, может принимать такие значения:

· - — обычный файл;

· d — каталог;

· b — файл блочного устройства;

· c — файл символьного устройства;

· s — доменное гнездо (socket);

· p — именованный канал (pipe);

· l — символическая ссылка (link).

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

Вообще говоря, права доступа и информация о типе файла в UNIX-системах хранятся в индексных дескрипторах в отдельной структуре, состоящей из двух байтов, т. е. из 16 бит (это естественно, ведь компьютер оперирует битами, а не символами r, w, x). Четыре бита из этих 16-ти отведены для кодированной записи о типе файла. Следующие три бита задают особые свойства исполняемых файлов, о которых мы скажем чуть позже. И, наконец, оставшиеся 9 бит определяют права доступа к файлу. Эти 9 бит разделяются на 3 группы по три бита. Первые три бита задают права пользователя, следующие три бита — права группы, последние 3 бита определяют права всех остальных пользователей (т. е. всех пользователей, за исключением владельца файла и группы файла).

При этом, если соответствующий бит имеет значение 1, то право предоставляется, а если он равен 0, то право не предоставляется. В символьной форме записи прав единица заменяется соответствующим символом (r, w или x), а 0 представляется прочерком.

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

Для каталогов тоже определены права доступа, причем они задаются теми же самыми символами rwx. Рассмотрим пример каталога:

drwxr-xr-x 2 root root 2048 Jun 21 21:11 bin

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

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

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

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

Основываясь на битовом представлении прав доступа используем команду chmod для изменения прав доступа к файлу. Для этого мы кодируем символ r цифрой 4, символ w — цифрой 2, а символ x — цифрой 1. Для того, чтобы предоставить пользователям какой-то набор прав, надо сложить соответствующие цифры. Получив, таким образом, нужные цифровые значения для владельца файла, для группы файла и для всех остальных пользователей, задаем эти три цифры в качестве аргумента команды chmod (ставим эти цифры после имени команды перед вторым аргументом, который задает имя файла). Например, если надо дать все права владельцу (4+2+1=7), право на чтение и запись — группе (4+2=6), и не давать никаких прав остальным, то следует дать такую команду:

[user]$ chmod 760 file_name

Также файл может иметь ещё три возможных атрибута, устанавливаемых с помощью той же команды chmod. Это те самые атрибуты для исполняемых файлов, которые в индексном дескрипторе файла в двухбайтовой структуре, определяющей права на файл, занимают позиции 5-7, сразу после кода типа файла.

Первый из этих атрибутов — так называемый "бит смены идентификатора пользователя". Смысл этого бита состоит в следующем.

Обычно, когда пользователь запускает некоторую программу на выполнение, эта программа получает те же права доступа к файлам и каталогам, которые имеет пользователь, запустивший программу. Если же установлен "бит смены идентификатора пользователя", то программа получит права доступа к файлам и каталогам, которые имеет владелец файла программы (таким образом, рассматриваемый атрибут лучше называть "битом смены идентификатора владельца"). Это позволяет решать некоторые задачи, которые иначе было бы трудно выполнить. Самый характерный пример — команда смены пароля passwd. Все пароли пользователей хранятся в файле /etc/passwd, владельцем которого является суперпользователь root. Поэтому программы, запущенные обычными пользователями, в том числе команда passwd, не могут производить запись в этот файл. А, значит, пользователь как бы не может менять свой собственный пароль. Но для файла /usr/bin/passwd установлен "бит смены идентификатора владельца", каковым является пользователь root. Следовательно, программа смены пароля passwd запускается с правами root и получает право записи в файл /etc/passwd (уже средствами самой программы обеспечивается то, что пользователь может изменить только одну строку в этом файле).

Установить "бит смены идентификатора владельца" может суперпользователь с помощью команды

[root]# chmod +s file_name

Аналогичным образом работает "бит смены идентификатора группы".

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

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

[root]# chmod 4775 file_name

При этом веса этих битов для получения нужного суммарного результата задаются следующим образом:

· 4 — "бит смены идентификатора пользователя",

· 2 — "бит смены идентификатора группы",

· 1 — "бит сохранения задачи (sticky bit)".

Если какие-то из этих трех битов установлены в 1, то несколько изменяется вывод команды ls -l в части отображения установленных атрибутов прав доступа. Если установлен в 1 "бит смены идентификатора пользователя", то символ "x" в группе, определяющей права владельца файла, заменяется символом "s". Причем, если владелец имеет право на выполнение файла, то символ "x" заменяется на маленькое "s", а если владелец не имеет права на выполнение файла (например, файл вообще не исполняемый), то вместо "x" ставится "S". Аналогичные замены имеют место при задании "бита смены идентификатора группы", но заменяется символ "x" в группе атрибутов, задающих права группы. Если равен 1 "бит сохранения задачи (sticky bit)", то заменяется символ "x" в группе атрибутов, определяющей права для всех остальных пользователей, причем "x" заменяется символом "t", если все пользователи могут запускать файл на выполнение, и символом "T", если они такого права не имеют.

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

[root]# ls -l prim1

-rwSrwsrwT 1 user root 12 Dec 18 23:17 prim1