- •Билет 1
- •1. Основы ос Unix, возможности, стандартизация (1) – 4
- •Отличительные черты ос unix
- •2. Взаимодействие процессов. Задача взаимного исключения. Вариант 4 (1, 16, 18) – 146
- •3. Последовательность действий по преобразованию адреса в защищенном режиме
- •Билет 2
- •1. Понятие системного вызова в ос unix. Обработка ошибок (2) – 9
- •Обработка ошибок
- •Void perror (s)
- •Void perror (const char *s);
- •2. Взаимодействие процессов. Задача взаимного исключения. Вариант 2 (2, 6, 15, 27) – 143
- •3. Особенности современных операционных систем (2, 28) – 122
- •Концепция ос на основе микроядра
- •Многопоточность
- •Cимметричная многопроцессорность.
- •Распределенные ос
- •Int chmod(const char *path, mode_t mode);
- •Int fcmod(int fd, mode_t mode);
- •2. Взаимодействие процессов. Задача взаимного исключения. Вариант 3 (3, 28) – 144
- •3. Концепция слоистой операционной системы и системы на основе микроядра.
- •Билет 4
- •1. Владельцы файлов. Права доступа к файлам. Атрибуты файлов (4, 18) – 23
- •Атрибуты файла
- •Int chmod(const char *path, mode_t mode);
- •Int fcmod(int fd, mode_t mode);
- •Int chown (const char *path, uid_t owner, gid_t group);
- •Int lchown (const char *path, uid_t owner, gid_t group);
- •Int fchown (int fd, uid_t owner, gid_t group): ,
- •2. Взаимодействие процессов. Задача взаимного исключения. Вариант 1 (4, 26) – 142
- •3. Функции микроядра (4, 12, 15, 27) – 126
- •Билет 5
- •1. Неименованные каналы в ос unix (5) – 77
- •Int pipe(int fd[2]);
- •2. Взаимодействие процессов. Задача взаимного исключения. Алгоритм Деккера (5) – 147
- •3. Понятие процесса, модели процессов (5) – 132
- •Билет 6
- •Метаданные файлов в ос unix (7) – 36
- •Int stat(const char *path, struct stat *buf);
- •Int fstаt(int fd, struct stat *buf);
- •Int lstat(const char *path, struct stat *buf);
- •2.Взаимодействие последовательных процессов. Задача взаимного исключения. Вариант2.
- •3. Описание процесса, таблица процесса (6) – 136
- •Билет 7
- •1. Процессы в ос unix. Типы процессов. (7, 23) – 56
- •2. Синхронизирующие примитивы. Решение задачи взаимного исключения с использованием семафоров (7, 8, 19, 20) - 152
- •3. Принципы построения ос (7, 19, 26) – 128
- •Билет 8
- •1. Атрибуты процессов в unix (8) – 66
- •2.Применение общего семафора для решения задачи "производитель-потребитель" с неограниченным буфером.
- •3. Концепция потока, как составной части процесса (8) – 139
- •Билет 9
- •1. Разработка программ в ос unix. Обработка ошибок, переменные окружения (9)
- •Int putenv(const char *string);
- •Int setenv(const char * name, const char * value, int ov );
- •Int unsetenv(const char * name);
- •Обработка ошибок
- •Void perror (const char *s);
- •2. Применение двоичных семафоров для решения задачи «производитель» - «потребитель» (буфер неограниченный) (9, 21)
- •3. Концепция виртуализации (9, 17) –
- •Билет 10
- •1. Файлы, отображаемые в память (10) – 33
- •Void *mmap(void *addr, size_t len, int prot, int flags, int fd, off_t offset);
- •2. Применение семафоров для решения задачи «производитель» - «потребитель» с неограниченным буфером. Решение «спящий парикмахер». (10, 22) – 155
- •3. Подсистема управления памятью, требования, предъявляемые к ней (10)
- •1. Процессы в ос unix. Порождение процесса (11, 25) – 57
- •2. Применение общих семафоров для решения задачи «производитель-потребитель» с ограниченным буфером (11, 23) – 157
- •3. Виртуальная память. Задачи управления виртуальной памятью (11, 25)
- •Билет 12
- •1. Сигналы в ос unix. Их назначение и обработка (12) – 70
- •Void (*sa_handler)(int);
- •Void (*sa_sigaction)(int, siginfo_t *, void *);
- •Int sa_flags;
- •Int pause (void);
- •2. Взаимодействие процессов через переменные состояния. Пример приоритетного правила (12) – 157
- •3. Функции микроядра (4, 12, 15, 27) – 126
- •Билет 13
- •1. Функции для работы с сигналами (13) – 70
- •Void (*sa_handler)(int);
- •Void (*sa_sigaction)(int, siginfo_t *, void *);
- •Int sa_flags;
- •Int pause (void);
- •Наборы сигналов
- •Блокировка сигналов
- •Int sigprocmask(int how, const sigset_t *set, sigset_t, *oldset);
- •Int sigaсtion(int signo, const struct sigactoin *act, struct sigaction *oldact);
- •Void my_handler(int signo)
- •Void my_handler(int signo, siginfo_t *si, void ucontext )
- •2. Проблема тупиков. Алгоритм банкира (13)
- •3. Задача замещения при управлении виртуальной памятью, часовой алгоритм.
- •Билет 14
- •Int chmod(const char *path, mode_t mode);
- •Int fcmod(int fd, mode_t mode);
- •2. Задача взаимного исключения. Алгоритм Петерсона (14, 25) – 148
- •3.Распределение памяти. Система двойников.
- •Система двойников при распределении памяти.
- •Билет 15
- •1. Файловая система в ос unix ext2 (15) – 51
- •Организация файловой системы ext2
- •2. Взаимодействие процессов. Задача взаимного исключения. Вариант 2 (2, 6, 15, 27) – 143
- •3. Функции микроядра (4, 12, 15, 27) – 126
- •Билет 16
- •1.Каналы в ос unix (16) – 80
- •Int pipe(int fd[2]);
- •Int mkfifo(const char *pathname,mode_t mode);
- •Размер канала и взоимодействие процессов при передаче данных
- •2. Взаимодействие процессов. Задача взаимного исключения. Вариант 4 (1, 16, 18) – 146
- •3. Организация защиты в процессорах ia32
- •Билет 17
- •1. Процессы в ос unix, системные вызовы wait, exit (17) – 60, 63
- •Void _exit(int exit_code);
- •Void exit(int status);
- •Int atexit(void(*func)(void));
- •2. Монитороподобные средства синхронизации для решения задачи взаимного исключения (17) – 160
- •Механизм типа «условная критическая область»
- •3. Концепция виртуализации
- •Билет 18
- •1. Владельцы файлов. Права доступа к файлам. Атрибуты файлов
- •Атрибуты файла
- •Int chmod(const char *path, mode_t mode);
- •Int fcmod(int fd, mode_t mode);
- •Int chown (const char *path, uid_t owner, gid_t group);
- •Int lchown (const char *path, uid_t owner, gid_t group);
- •2. Взаимодействие процессов. Задача взаимного исключения. Вариант 4 (1, 16, 18) – 146
- •3. Схемы распределения памяти
- •Билет 19
- •1. Взаимодействие процессов в ос unix, очереди сообщений (19) – 83
- •Int msgget (key_t key, int permflags);
- •Int msgsnd(int mqid, const void *message, size_t size, int flags);
- •Int msgrcv(int mqid, void *message, size_t size, long msg_type, int flags);
- •Int msgctl(int mqid, int command, struct msqid_ds *msq_stat);
- •2. Синхронизирующие примитивы. Решение задачи взаимного исключения с использованием семафоров (7, 8, 19, 20) - 152
- •3. Принципы построения ос (7, 19, 26) – 128
- •Билет 20
- •1 Взаимодействие процессов в ос unix с применением семафоров (20) – 93
- •V(sem) или signal (sem)
- •Int semget(key_t key, int nsems, int permflags);
- •Int semctl (int semid, int sem_num, int command, union semun ctl_arg);
- •Int semop(int semid, struct sembuf *op_array, size_t num_ops);
- •2. Применение общего семафора для решения задачи "производитель-потребитель" с неограниченным буфером.
- •3. Механизмы поддержки многозадачности в процессорах ia32 (20)
- •Билет 21
- •1. Работа с файлами в ос unix. Системные вызовы (21) – 25
- •Int open(const char *name, int flags);
- •Int open(const char *name, int flags, mode_l mode);
- •2. Применение двоичных семафоров для решения задачи "производитель-потребитель" (буфер неограниченный).
- •3. Страничная организация памяти в процессоре ia32
- •Билет 22
- •1. Взаимодействие процессов в ос unix. Разделяемая память (22) – 100
- •Int shmget(key_t key, size_t size, int permflags);
- •Void *shmat(int shmid, const void *daddr, int shmflags);
- •Int shmctl(int shmid, int command, struct shmid ds *shm_stat);
- •2. Применение семафоров для решения задачи «производитель» - «потребитель» с неограниченным буфером. Решение «спящий парикмахер». (10, 22) – 155
- •3. Организация защиты в процессорах ia32
- •Билет 23
- •1. Процессы в ос unix. Типы процессов. (7, 23) – 56
- •2. Применение общих семафоров для решения задачи «производитель-потребитель» с ограниченным буфером (11, 23) – 157
- •3. Задача замещения при управлению виртуальной памятью, часовой алгоритм.
- •Билет 24
- •1. Понятие потока в ос unix. Создание потока, завершение потока (24) – 106
- •Int pthread_create(pthread_t *tid, const pthread_attr_t *tattr,
- •Void*(*start_routine)(void *), void *arg);
- •Функция для завершения нити (потока) исполнения
- •Int pthread_join(thread_t tid, void **status);
- •Int pthread_detach(thread_t tid);
- •Досрочное завершение потока
- •Int pthread_cancel(pthread_t thread);
- •2. Синхронизирующие примитивы. Решение задачи взаимного исключения с использованием семафоров (7, 8, 19, 20, 24) - 152
- •3. Схемы распределения памяти (18, 24)
- •1. Процессы в ос unix. Порождение процесса (11, 25) – 57
- •2. Задача взаимного исключения. Алгоритм Петерсона
- •3. Виртуальная память. Задачи управления виртуальной памятью (11, 25)
- •Билет 26
- •1. Поток в ос unix. Синхронизация потоков, получение информации о потоке.
- •Int pthread_key_create(pthread_key_t *key, void(*destructor)(void *));
- •Int pthread_setschedparam(pthread_t tid, int policy,
- •Int pthread_getschedparam(pthread_t tid, int policy, struct schedparam *param);
- •Int pthread_sigmask(int how, const sigset_t *new, sigset_t *old);
- •2. Взаимодействие процессов. Задача взаимного исключения. Вариант 1 (4, 26) – 142
- •3. Принципы построения ос (7, 19, 26) – 128
- •Билет 27
- •1. Применение мьютексов при взаимодействии потоков в ос unix.
- •2. Взаимодействие процессов. Задача взаимного исключения. Вариант 2 (2, 6, 15, 27) – 143
- •3. Функции микроядра (4, 12, 15, 27) – 126
- •1. Применение блокировок чтения-записи при взаимодействии потоков в ос unix.
- •2. Взаимодействие процессов. Задача взаимного исключения. Вариант 3 (3, 28) – 144
- •3. Особенности современных операционных систем (2, 28) – 122
- •Концепция ос на основе микроядра
- •Многопоточность
- •Cимметричная многопроцессорность.
- •Распределенные ос
Наборы сигналов
Понимается некоторое множество сигналов, к которым оперирует процесс. Есть действия системные вызовы, которые позволяют создавать наборы сигналов, и проверять наличие какого-то сигнала в наборе сигналов. Для определения набора сигналов есть специальный тип: sigset_t
#include <signal.h>
int sigemptyset(sigset_t *set);//инициализирует набор сигналов, и помечает его как пустой. Возвращает 0
int sigfillset(sigset_t *set); //инициализирует набор сигналов, и помечает его как полный(все присутствуют). Возвращает 0
int sigaddset(sigset_t *set, int signo);//добавить сигнал в набор
int sigdelset(sigset_t *set, int signo);//удалить сигнал из набора. Возвращает 0 – успешно. -1 если ошибка.
int sigismember(const sigset_t *set, int signo)// 1 – если проверяемый сигнал находится в наборе. 0 если сигнал отсутствует в наборе. -1 при ошибке.
Блокировка сигналов
Для реализации блокировки сигналов используется сигнальная маска. Это набор сигналов, принятие которых будет блокироваться (не обрабатываться) до тех пор, пока они не будут обратно разблокированы. Для управления используется функция
Int sigprocmask(int how, const sigset_t *set, sigset_t, *oldset);
выполнение функции зависит от первого аргумента:
SIG_SETMASK маска меняется на значение второго аргумента.
SIG_BLOCK маска set добавляется к текущему (маски объединяются по ИЛИ)
SIG_UNBLOCK сигналы из set удаляются из вызывающего процесса.
Третий аргумент может быть равен NULL. Если третий аргумент указан явно, то по этому адресу помещается предыдущее значение. Если второй аргумент равен NULL, то в третий помещается текущий набор.
#include <signal.h>
Int sigaсtion(int signo, const struct sigactoin *act, struct sigaction *oldact);
устанавливает действие при получении сигнала. Это действие описывается структурой, передаваемой вторым параметром. Третий параметр, если он не является нулевым, сохраняет предыдущую реакцию на сигнал. При успешном завершении возвращает 0, при ошибке -1;
Void my_handler(int signo)
Void my_handler(int signo, siginfo_t *si, void ucontext )
siginfo_t
{int si_signo;//номер сигнала
int si_errno;//значение ошибки
int si_code;//информация о том, откуда процесс получил сигнал.
…
}
Поле si_code может иметь значения:
SI_KERNEL//сигнал был сгенерирован ядром
SI_TIMER//был сгенерирован по истечении временного интервала.
SI_USER //сигнал был отправлен SIGKILL & raise
Если обрабатывался сигнал SIGCHLD:
CLD_EXITED//потомок завершился нормально, через exit()
CLD_KILLED //потомок был уничтожен
CLD_STOPPED//потомок был остановлен.
2. Проблема тупиков. Алгоритм банкира (13)
Рассматривается логическая задача, которая возникает при взаимодействии различных процессов, когда они должны делить ресурсы. Под процессами понимаются программы, описывающие некоторый вычислительный процесс, выполняемый ЭВМ. Выполнение такого вычислительного процесса требует времени, в течение которого в памяти ЭВМ хранится информация. О процессах известно следующее.
1. Их требования к объему памяти не будут превышать определенного предела.
2. Каждый вычислительный процесс завершится при условии, что требуемый процессу объем памяти будет предоставлен в его распоряжение. Завершение вычислительного процесса будет означать, что его требование к памяти уменьшилось до нуля.
Имеющаяся память поделена на страницы фиксированного размера, эквивалентные с точки зрения программы. Фактическое требование нужного процессу объема памяти является функцией времени, то есть изменяется по мере протекания процесса, но не превышает заранее заданную границу. Отдельные процессы запрашивают и выделяют память единицами в одну страницу. Однажды начатый процесс получает возможность рано или поздно завершиться, и исключается ситуация, когда процесс может быть уничтожен в ходе выполнения, напрасно истратив свои ресурсы.
Если на вычислительной машине выполняется один процесс, или они последовательно следуют один за другим, единственным условием является то, чтобы запрашиваемый процессом объём памяти не превышал доступный объём памяти вычислительной машины. Если параллельно развиваются несколько процессов, то могут возникнуть проблемы с выделением им ресурсов и надо предусмотреть выделение памяти таким образом, чтобы все начатые процессы смогли завершить свое выполнение. Ситуация, когда какой-либо из процессов может быть завершён лишь при условии уничтожения какого-либо другого процесса, называется «смертельными объятиями» или тупиком(рис.).
Ситуация, приведенная выше, является тупиковой. Из этой ситуации невозможно выйти без уничтожения какого-либо из процессов.Решаемая проблема состоит в том, как избежать попадания в тупик, не накладывая слишком больших ограничений.
Алгоритм банкира
Банкир обладает конечным капиталом, например, талерами. Он решает принимать клиентов, которые могут занимать у него талеры на следующих условиях:
1. Клиент делает заем для совершения сделки, которая будет завершена за определенный промежуток времени.
2. Клиент должен указать максимальное количество талеров для этой сделки.
3. Пока заем не превысит заранее установленную потребность, клиент может увеличивать или уменьшать свой заем.
4. Клиент, который просит увеличить свой текущий заем, без недовольства воспринимает ответ о том, что необходимо подождать с получением очередного талера, но через некоторое время талер будет обязательно выдан.
5. Гарантия для клиента, что такой момент наступит, основана на предусмотрительности банкира и на том факте, что остальные клиенты работают по таким же правилам.
Основными вопросами при решении такой задачи являются:
1. При каких условиях банкир может заключить контракт с новым клиентом?
2. При каких условиях банкир может выплатить (следующий) запрашиваемый талер клиенту, не опасаясь попасть в тупик?
Ответ на первый вопрос достаточно прост: банкир может принять любого клиента на обслуживание, чья максимальная потребность не превышает капитал банкира. Ответ на второй вопрос достаточно сложный. Сначала нужно формализовать задачу.
потребность[i] <= капитал, для всех i.
0 <= заем[i] <= потребность[i], для всех i.
требование[i] = потребность[i] - заем[i], для всех i.
наличные = капитал - СУММА_по_i заем[i].
0 <= наличные <= капитал.
В такой ситуации алгоритм принятия решения о том, будет ли безопасной выдача следующего талера, выглядит след образом:
integer Св_Деньги; boolean Безопасно;
boolean array Завершение_под_сомнением [1..N];
Св_Деньги := наличные;
for i := 1 step 1 until N do Завершение_под_сомнением[i] := true;
L: for i :=1 step 1 until N do
begin
if ( (Завершение_под_сомнением [i]) and
(Требован[i] <= Св_Деньги) ) then
begin
Завершение_под_сомнением [i] := false;
Св_Деньги := Cв_Деньги + Заем[i];
goto L;
end;
end;
if (Св_Деньги = капитал) then Безопасно := true
else Безопасно := false;
Проверка возможности выплаты, то есть положение Безопасно, означает, могут ли с гарантией быть завершены все сделки. Алгоритм начинается с проверки, имеет ли, по крайней мере, один клиент требование, не превышающее наличные деньги. Если это так, то этот клиент может завершить свою сделку, и далее исследуются оставшиеся клиенты с учетом того, что первый клиент завершил свою сделку и возвратил свой заём полностью.
Безопасность положения означает, что могут быть закончены все сделки, то есть банкир видит способ получения обратно всех своих денег.
В полном варианте алгоритма банкира эта ситуация должна быть удовлетворена для всех клиентов, принятых на обслуживание и если после завершения цикла, отмеченного меткой L окажется, что капитал банкира полностью восстановлен, то ситуация считается безопасной, в противном случае она определяется как тупиковая и, следовательно, удовлетворять запрос клиента не представляется возможным.
Если более глубоко анализировать эту проблему, то можно показать, что решение о выделении следующего запрашиваемого талера клиенту будет принято тогда, когда хотя бы для одного клиента выполниться условие ((Завершение_под_сомнением[i]) and (Треб[i]<=Св_Деньги)) и это говорит о безопасности ситуации и проверку можно приостановить.