- •Кафедра программного обеспечения информационных технологий
- •«Операционные системы и системное программирование»
- •40 01 01
- •Содержание
- •Введение
- •Разработка программ в ос unix
- •1.1 Отличительные черты ос unix
- •1.2 Основы архитектуры операционной системы unix
- •1.3 Ядро системы
- •1.4 Пользователи системы, атрибуты пользователя
- •1.5 Системные вызовы и функции стандартных библиотек
- •1.6 Описание программы, переменные окружения
- •1.7 Аргументы и опции программы
- •1.8 Обработка ошибок
- •2 Файлы и файловая система
- •2.1 Файлы
- •2.2 Типы файлов
- •2.2.1 Обычные файлы
- •2.2.2 Каталоги
- •2.2.3 Файлы символичной связи (ссылки)
- •2.2.4 Файлы устройства
- •2.2.5 Именованные каналы
- •2.2.6 Сокеты
- •2.3 Владельцы файлов и права доступа к файлу
- •2.4 Дополнительные атрибуты файла
- •2.5 Файловый ввод/вывод
- •Открытие файла
- •2.6 Мультиплексированный ввод/вывод
- •2.7 Векторный ввод/вывод
- •2.8 Файлы, отображающиеся в памяти
- •2.9 Каталоги, работа с каталогами
- •2.9.1 Создание каталога
- •2.9.2 Удаление каталога
- •2.9.3 Чтение информации из каталога
- •2.9.4 Закрытие каталога
- •2.10 Создание жестких ссылок
- •2.11 Символическая ссылка
- •2.12 Удаление ссылки (или имени файла)
- •2.13 Переименование файла
- •2.14 Файловая система ос unix
- •2.14.1 Организация файловой системы ext2
- •2.15 Файлы устройств
- •3 Процессы
- •3.1 Виды процессов
- •3.2 Создание процесса
- •3.3 Вызовы семейства exec
- •3.4 Функции завершения процесса
- •3.5 Ошибки
- •3.6 Копирование при записи
- •3.7 Системные вызовы ожидания завершения процесса
- •3.8 Системный вызов system
- •3.9 Основные параметры, передаваемые процессу
- •3.10 Сеансы и группы процессов
- •4 Взаимодействие процессов
- •4.1 Сигналы
- •4.1.1 Отправка (генерация) сигнала
- •4.1.2 Наборы сигналов
- •4.1.3 Блокировка сигналов
- •4.2 Неименнованные каналы (трубы)
- •4.2.1 Размер канала и взоимодействие процессов при передаче данных
- •4.3 Именнованные каналы
- •4.4 Дополнительные средства межпроцессного взоимодействия
- •4.5 Механизмы межпроцессорного взаимодействия
- •4.5.1 Очереди сообщений
- •4.5.2 Семафоры Семафоры как теоретическая конструкция
- •4.5.3 Разделяемая память
- •4.5.4 Потоки
- •Int pthread_setschedparam(pthread_t tid, int policy, const struct sched_param *param);
- •Int pthread_getschedparam(pthread_t tid, int policy, struct schedparam *param);
- •5 Операционные системы
- •5.1 Понятие операционной системы
- •5.2 Характеристики современных ос
- •5.2.1 Многопоточность
- •5.2.2 Распределенные ос
- •5.2.3 Концепция ос на основе микроядра
- •5.2.4 Функции микроядра.
- •5.3 Принципы построения ос
- •5.4 Концептуальные основы ос
- •5.4.1 Процессы
- •Модель работы процесса с двумя приостановочными состояниями
- •Варианты решения:
- •Решение задачи взаимного исключения. Алгоритм Деккера.
- •Решение задачи взаимного исключения. Алгоритм Пэтерсона..
- •Синхронизирующие примитивы (семафоры).
- •Задача “производитель-потребитель” Общие семафоры
- •Задача “производитель-потребитель”, буфер неограниченного размера(Спящий парикмахер)
- •Задача “производитель-потребитель”, буфер ограниченного размера
- •5.4.2 Распределение ресурсов. Проблема тупиков
- •Алгоритм банкира
- •Применение алгоритма банкира
- •5.4.3 Монитороподобные средства синхронизации
- •Механизм типа «критическая область»
- •5.4.4 Виртуализация
- •5.4.5 Подсистема управления памятью
- •5.4.6 Виртуальная оперативная память
- •5.5 Аппаратные особенности процессоров Intel-архитектуры, направленных на поддержку многозадачности
- •5.5.1 Сегментация памяти. Ia-32
- •5.5.2 Распределение памяти в реальном режиме
- •5.5.3 Организация защиты в процессоре
- •5.5.4 Поддержка многозадачности в процессорах архитектуры ia-32
Решение задачи взаимного исключения. Алгоритм Деккера.
begin integer С1,С2,очередь;
С1 := 1;
С2 := 1;
очередь := 1;
parbegin
процесс 1: begin
А1: С1 := 0;
L1: if (С2 = 0) then begin
if (очередь = 1) then goto L1;
C1 := 1;
B1: if (очередь = 2) then goto B1;
goto А1;
end;
критический интервал 1;
очередь := 2;
С1 := 1;
остаток цикла 1;
goto А1;
end;
процесс 2: begin
А2: С2 := 0;
L2: if (С1 = 0) then begin
if (очередь = 2) then goto L2;
C2 := 1;
B2: if (очередь = 1) then goto B2;
goto А2;
end;
критический интервал 2;
очередь := 1;
С2 := 1;
остаток цикла 2;
goto А2;
end;
parend;
end;
int flag[2], turn;
void P0()
{
while (1)
{
flag[0]=1;
while (flag[1]);
{
if (turn==1)
{
flag[0]=0;
while (turn==1);
flag[0]=1;
}
}
критический интервал 1;
turn=1;
flag[0]=0;
….
}
}
void P1()
{
while (1)
{
flag[1]=1;
while (flag[0]);
{
if (turn==0)
{
flag[1]=0;
while (turn==0);
flag[1]=1;
}
}
критический интервал 2;
turn=0;
flag[1]=0;
….
}
}
void main()
{
flag[0]=0;
flag[1]=0;
turn=1;
parbegin(P0,P1);}
Решение задачи взаимного исключения. Алгоритм Пэтерсона..
int flag[2], turn;
void P0()
{
while (1)
{
flag[0]=1; turn=1;
while (flag[1] && (turn==1));
критический интервал 1;
flag[0]=0;
….
}
}
void P1()
{
while (1)
{
flag[1]=1; turn=0;
while (flag[0] && (turn==0));
критический интервал 2;
flag[1]=0;
….
}
}
void main()
{
flag[0]=0;
flag[1]=0;
parbegin(P0,P1);
}
Для доказательства корректности задачи взаимного исключения необходимо проверить три положения.
1. Решение безопасно в том смысле, что два процесса не могут одновременно оказаться в своих критических интервалах
2. В случае сомнения, кому из двух процессов первому войти в критический интервал, выяснение этого вопроса не откладывается до бесконечности
3. Остановка какого-либо из процессов в остатке цикла не вызывает блокировки другого процесса.
Обобщенная задача взаимного исключения
Даны N процессов, каждый со своим критическим интервалом. Необходимо организовать их функционирование так, чтобы в любой момент самое большее один процесс находился в критическом интервале. Для проверки правильности решения проверяем три условия.
begin integer array b, c [0..N];
integer очередь;
for очередь = 1 step 1 until N do begin
b [очередь] := 1;
c [очередь] := 1;
end;
очередь := 0;
parbegin
процесс 1: begin … end;
процесс 2: begin … end;
…
процесс N: begin … end;
parend;
end;
процесс i: begin integer j, k;
Ai: b [i] := 0;
Li: if (очередь <> i) then begin
С[i] = 1;
k = очередь;
if (b [k] = 1) then очередь := i;
goto Li;
end;
C[i] := 0;
for j := 1 step 1 until N do
if ((j <> i) and (C[j] = 0)) then goto Li;
Критический интервал i;
очередь := 0;
C[i] := 1;
b[i] := 1;
Oстаток цикла i;
goto Ai;
end;