Проблемы синхронизации в ос. Задача о спящем брадобрее - файл Лр1.doc Проблема спящего брадобрея

Размер: px

Начинать показ со страницы:

Транскрипт

1 Классические задачи синхронизации, ч. 2 Читатели и писатели Производители и потребители Спящий парикмахер

2 Читатели и писатели Дана некоторая разделяемая область память К этой структуре данных может обращаться произвольное количество «читателей» и произвольное количество «писателей» Несколько читателей могут получить доступ одновременно, писатели в этот момент не допускаются Только один писатель может получить доступ, другие писатели и читатели должны ждать

3 Решение 1 Первое решение: читатель может войти в критическую секцию, если нет писателей Это решение несправедливо, так как отдает предпочтение читателям Плотный поток запросов от читателей может привести к тому, что писатель никогда не получит доступа к критической секции: ситуация «голодания» (starvation)

4 Решение 2 Отдадим предпочтение писателям, то есть читатель не входит в критическую секцию, если есть хотя бы один ожидающий писатель pthread_mutex_t m; pthread_cond_t cw, cr; int rcnt, wcnt; int wwcnt; // число ожидающих писателей void rdlock() { pthread_mutex_lock(&m); while (wcnt > 0 wwcnt > 0) pthread_cont_wait(&cr, &m); rcnt++; pthread_mutex_unlock(&m); }

5 Решение 2 void wrlock() { pthread_mutex_lock(&m); while (wcnt > 0 rcnt > 0) { wwcnt++; pthread_cond_wait(&cw, &m); wwcnt--; } wcnt++; pthread_mutex_unlock(&m); } void unlock() { // }

6 Решение 2 Данное решение отдает приоритет писателям, и тоже несправедливо Возможно «голодание» (starvation) читателей Третье решение: не отдавать никому приоритета, просто использовать мьютекс

7 Производители-потребители (producer-consumer problem) Дан буфер фиксированного размера (N), в котором размещается очередь. Производители добавляют элементы в конец очереди, если буфер заполнился, производители засыпают Потребители забирают элементы из начала очереди, если буфер пуст, потребители засыпают

8 Производители-потребители int buf[n]; int head, tail; pthread_mutex_t m; pthread_cond_t cc; // consumer condvar pthread_cond_t pc; // producer condvar void put(int x) { pthread_mutex_lock(&m); while ((tail + 1) % N == head) pthread_cond_wait(&pc, &m); buf = x; tail = (tail + 1) % N; if ((head + 1) % N == tail) pthread_cond_signal(&cc); pthread_mutex_unlock(&m); }

9 Производители-потребители int get(void) { int val; pthread_mutex_lock(&m); while (head == tail) pthread_cond_wait(&cc, &m); val = buf; if ((tail + 1) % N == head) pthread_cond_signal(&pc); head = (head + 1) % N; pthread_mutex_unlock(&m); return val; }

10 Спящий парикмахер (sleeping barber) В парикмахерской имеется одно кресло для стрижки и N кресел для ожидающих посетителей Если нет посетителей, парикмахер спит Если приходит посетитель и кресло для стрижки свободно, посетитель садится в него и парикмахер начинает его стричь В противном случае посетитель садится в кресло для ожидающих Если все кресла заняты, посетитель уходит

11 Спящий парикмахер pthread_mutex_t m; pthread_t chair_thr; // кого стрижем int wait_cnt; // сколько посетителей ожидают pthread_cond_t bc; // barber condvar pthread_cond_t cc; // consumer condvar void barber(void) { while (1) { pthread_mutex_lock(&m); while (chair_thr == NULL && wait_cnt == 0) pthread_cond_wait(&bc, &m); pthread_mutex_unlock(&m); make_haircut(); pthread_mutex_lock(&m); chair_thr = NULL; pthread_cond_signal(&cc); pthread_mutex_unlock(&m); }}

12 Спящий парикмахер int consumer(void) { pthread_mutex_lock(&m); if (chair_thr!= NULL && wait_cnt == N) { // no space, leaving pthread_mutex_unlock(&m); return -1; } while (chair_thr!= NULL) { wait_cnt++; pthread_cond_wait(&cc, &m); wait_cnt--; } chair_thr = pthread_self(); pthread_cond_signal(&bc); pthread_mutex_unlock(&m); get_haircut(); return 0; }

13 Обнаружение тупиков Process 1: lock(&a); lock(&b); Process 2: lock(&b); lock(&a); Process 1 A Process 2 B Захваченный ресурс дуга от процесса к ресурсу Ожидаемый ресурс дуга от ресурса к процессу Если в графе есть цикл, система попала в состояние тупика

14 Группы процессов Группа процессов процессы, объединенные для выполнения задачи (например, для выполнения конвейера) Группа процессов выступает как единое целое при Получении сигналов, в особенности, от терминала (например, Ctrl-C SIGINT) При работе с терминалом (основная и фоновые группы процессов) Идентификатор группы процессов это идентификатор одного из процессов в группе

15 Создание группы #include pid_t getpgid(pid_t pid); int setpgid(pid_t pid, pid_t pgid); Группу процессов можно получить только у процесса из текущей сессии, при этом если pid == 0, возвращается группа процессов текущего процесса Для setpgid pid == 0 означает текущий процесс, pgid == 0 группа процессов с pgid текущего процесса

16 Создание группы, особые случаи setpgid(0, 0); Процесс создает новую группу процессов и помещает в нее себя (выполняется в сыне) setpgid(0, pgid); Процесс помещает себя в существующую группу процессов (в сыне) setpgid(pid, pid); Процесс создает новую группу процессов и помещает туда указанный процесс (в отце)

17 Группы процессов и терминал У терминала может быть одна основная группа процессов и произвольное количество фоновых групп процессов Основная группа процессов: Имеет право чтения с терминала (попытка чтения для фоновой группы процессов вызывает приостановку процесса фоновой группы) Получает сигналы SIGINT, SIGQUIT с терминала

18 Основная группа процессов терминала pid_t tcgetpgrp(int fd); int tcsetpgrp(int fd, pid_t pgrp); fd любой файловый дескриптор терминала (например, 0 стандартный ввод) tcsetpgrp устанавливает основную группу процессов терминала

19 Пример: ls -l wc -l int main(void) { pipe(fds); if (!(pid1 = fork())) { setpgid(0, 0); tcsetpgrp(0, getpid()); dup2(fds, 1); close(fds); close(fds); execlp("/bin/ls", "/bin/ls", "-l", NULL); } setpgid(pid1, pid1); tcsetpgrp(0, pid1); if (!(pid2 = fork())) { setpgid(0, pid1); dup2(fds, 0); close(fds); close(fds); execlp("/usr/bin/wc", "/usr/bin/wc", "-l", NULL); } setpgid(pid2, pid1); close(fds); close(fds); wait(0); wait(0); tcsetpgrp(0, getpgid(0)); return 0; }

20 Процессы-демоны

21 Планирование процессов Планировщик компонента ядра операционной системы Планировщик определяет, какой процесс из числа готовых к выполнению назначается на выполнение на ЦП Типы планировщиков: Пакетный Разделения времени Реального времени

22 Пакетное планирование Цель обеспечить максимальную пропускную способность ВС (то есть максимальное число выполненных задач) Ядро переключается с одного на другой процесс при следующих условиях: Выполнявшийся процесс завершил работу При выполнении возникла фатальная ошибка или процесс исчерпал отведенные ему ресурсы Выполнявший процесс инициировал операцию, которая не может быть выполнена немедленно Процесс запросил добровольное переключение

23 Планирование разделения времени Цель: разделить процессорное время между процессами, готовыми к выполнению Ядро переключается с одного процесса на другой при следующих условиях Процесс завершил работу При выполнении возникла ошибка Процесс инициировал операцию, которая не может быть выполнена немедленно Истек квант времени выполнения процесса Процесс запросил добровольное переключение

24 Классификация процессов По поведению «I/O-bound» - процесс выполняет активный обмен с внешними устройствами и проводит много времени в ожидании ввода-вывода (пример: веб-сервер, редактор текста) «CPU-bound» - процессы, интенсивно занимающие процессорное время (пример: компиляция программ, вычислительные задачи, рендеринг изображений и т. п.)

25 Классификация процессов По назначению: Интерактивные основное время проводят в ожидании пользовательского ввода, при поступлении ввода должны быстро активироваться, чтобы не было ощущения «торможения» Пакетные не ожидают ввода пользователя (компиляторы, численные приложения...)

26 Параметры планирования процессов разделения времени Значение nice: [-20, 19] чем меньше значение, тем выше приоритет. 0 приоритет по умолчанию Приоритет группы процессов: grpnice Приоритет пользователя: usrnice Полный приоритет: nice + grpnice + usrnice отсеченное по интервалу [-20; 19] Нормализованный приоритет normprio = 20 - fullnice, находится в интервале чем больше значение, тем больше приоритет

27 Планирование в Linux Планирование процессов разделено на эпохи В начале каждой эпохи каждому процессу назначается базовый квант base_quantum = normprio/4 + 1 counter число «неотработанных» квантов в эпохе, изначально counter = base_quantum За каждый квант, когда процесс выполняется, значение counter уменьшается на 1 Приоритет: priority = counter + normprio Выбирается процесс с наибольшим приоритетом

28 Планирование в Linux Эпоха заканчивается, когда у всех готовых к выполнению процессов counter == 0 В начале очередной эпохи: base_quantum = counter/2 + normprio/4 + 1 Таким образом приоритет отдается I/O-bound процессам

29 Планирование реального времени Цель: обеспечить минимальное время отклика, то есть время от наступления события до постановки на выполнение процесса, ожидающего этого события Виды планирования реального времени На основе фиксированного расписания На основе статических приоритетов

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

31 Статический приоритет Каждый процесс реального времени имеет статический приоритет Процессы разделения времени имеют статический приоритет 0, то есть назначаются на выполнение, только если нет готовых к выполнению процессов реального времени

32 Типы планирования р.в. SCHED_FIFO нет квантования времени, процесс выполняется, пока не появится более высокоприоритетный процесс, либо процесс не начнет ввод-вывод, либо не будет снят SCHED_RR (round-robin) выполнение квантуется, процессы одного приоритета выполняются по очереди

33 Инверсия приоритета (priority inversion) Предположим, что низкоприоритетный процесс P1 захватил некоторый ресурс R В это время стал готов к выполнению высокоприоритетный процесс P2, которому требуется ресурс R. Процесс P2 ожидает освобождения ресурса R процессом P1 В это время может быть назначен на выполнение среднеприоритетный процесс P3, который еще более отсрочит время освобождения ресурса R процессом P1

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

35 Управление приоритетами в Linux int nice(int inc); void sched_yield(void); int sched_setscheduler(pid_t pid, int policy, const struct sched_param *param);


Содержание 1 Управление заданиями (job control) 1 1.1 Основные концепции................................ 1 1.2 Дополнительность управления заданиями..................... 2 1.3 Управляющий терминал...............................

Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Операционные системы: аспекты параллелизма Планирование ЦП Линёв А.В. Тема обсуждения Потокам

Алгоритмы планирования потоков Вытесняющие и невытесняющие алгоритмы планирования Невытесняющие алгоритмы основаны на том, что активному потоку позволяется выполняться, пока он сам, по собственной инициативе,

ГЛАВА 15 Управление заданиями Управление заданиями возможность, стандартизованная в POSIX.1 и предоставляемая многими другими стандартами позволяет одному терминалу выполнять несколько заданий. Задание

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

Название Лекция 5. Планирование задач Операционные системы 6 ноября 2012 г. Лекция 5 1 / 39 Планирование Начало Цели планирования Основные алгоритмы Определение Политика планирования: (Scheduling Strategy)

Модуль 3. УПРАВЛЕНИЕ ПРОЦЕССАМИ 1. Распределяет процессорное время между несколькими одновременно существующими в системе процессами, а также занимается созданием и уничтожением процессов, обеспечивает

Планирование процессов Многозадачность ОС является многозадачной, если она способна чередовать выполнение нескольких процессов, создавая видимость, что в каждый момент времени работает более одного процесса

Лекция 8. Нити POSIX Эффективное использование IPC - разделяемой памяти и семафоров все таки ограничивается затратами на порождение новых процессов системным вызовом fork/2, даже при использовании технологии

Лекция 2. Подсистема управления процессами. Управление процессами в многозадачной системе заключается в выделении ресурсов ядра для каждого запущенного процесса, осуществлении переключения контекста процессов

UNIX Лекция 4 UNIX. Л.4 1 ПРОЦЕССЫ ОС UNIX Процесс - это задание в ходе его выполнения. П - образ программы, включающий отображение в памяти исполняемого файла, полученного в ходе компиляции, сегментов

Лабораторная работа 4 ЗНАКОМСТВО С ПРОЦЕССАМИ Цель работы Познакомиться с понятием процесса. Научиться получать список имеющихся в системе процессов и управлять их состоянием. 1. Теоретические сведения

Процессы и потоки Операционные системы Лекция 2 Ульяновск, УлГТУ, кафедра «Информационные системы» 1 / 12 Модель процесса Четыре программы, работающие в многозадачном режиме а); концептуальная модель четырех

Основы ОС Unix Сигналы Основы ОС Unix 28.2.08 Слайд 1 из 34 Сегодня Что такое сигнал? Терминология Старые проблемы с сигналами POSIX и Linux сигналы Работа с наборами сигналов Основы ОС Unix 28.2.08 Слайд

НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ЯДЕРНЫЙ УНИВЕРСИТЕТ «МИФИ» Кафедра информатики и процессов управления (17) Курс «Современные операционные системы» Лекция 7 Планирование Москва 2016 Содержание 1. Основные

Сигналы Средство асинхронного взаимодействия процессов Посылаются: Одним процессом другому процессу Ядром ОС процессу для индикации событий, затрагивающих процесс Ядром ОС процессу в ответ на некорректные

4.1 Процессы 4.1.1 Понятие процесса Процесс (задача) - программа, находящаяся в режиме выполнения. С каждым процессом связывается его адресное пространство, из которого он может читать и в которое он может

Операционные системы. Разработка и реализация. Таненбаум Э., Вудхалл А. 3-е изд. - СПб.: Питер, 2007. 704 с. Третье издание классического труда Эндрю Таненбаума " Операционные системы. Разработка и реализация"

Операционные системы Лекция 2 Процессы и потоки (нити). 2.1 Процессы 2.1.1 Понятие процесса Процесс (задача) - программа, находящаяся в режиме выполнения. С каждым процессом связывается его адресное пространство,

Именованные каналы Канал, доступ к которому выполняется через точку привязки файловой системы Ядро создает по одному объекту именованного канала для каждой записи в файловой системе int mkfifo(const char

1 Работа с процессами в POSIX-системах Понятие «процесс» наряду с понятием «файл» относится к основным понятиям операционной системы. Под процессом можно понимать программу в стадии выполнения. С процессом

Занятие 6. Понятие процесса. Состояния процесса. Диспетчеризация. План занятия. 1. Процесс. Классификация процессов. 2. Ресурсы. Классификация ресурсов. 3. Управление процессами. 4. Планирование процессов.

Название Лекция 6. Алгоритмы блокировок Операционные системы 19 ноября 2012 г. Лекция 6 1 / 46 Цели планирования Требования ко взаимным исключениям Требования В любой момент времени в одном критическом

Процессы и потоки Понятия «процесс» и «поток» Процесс (задача) - программа, находящаяся в режиме выполнения. Потоќ выполне ния (thread нить) наименьшая часть программы, исполнение которой может быть назначено

ВСТРОЕННЫЕ ИНФОРМАЦИОННО-УПРАВЛЯЮЩИЕ СИСТЕМЫ РЕАЛЬНОГО ВРЕМЕНИ Лекция 4: Статико-динамическое планирование вычислений в системах интегрированной модульной авионики Кафедра АСВК, Лаборатория Вычислительных

СУПЕРКОМПЬЮТЕРНЫЙ КОНСОРЦИУМ УНИВЕРСИТЕТОВ РОССИИ Проект Создание системы подготовки высококвалифицированных кадров в области суперкомпьютерных технологий и специализированного программного обеспечения

Лекция 10. Подходы к синхронизации. Содержание Задача читателей-писателей Замки Подходы к синхронизации Задача читаталей-писателя Задача читателей-писателей Имеется область памяти, к которой обращаются

Планирование процессов в ОС Windows NT Свойства 1) Процессы Windows NT реализованы в форме объектов, и доступ к ним осуществляется посредством службы объектов. 2) Процесс Windows NT имеет многонитевую

Название Мёртвая блокировка Сети Петри Требования к алгоритмам Лекция 6. Алгоритмы блокировок Операционные системы 11 ноября 2016 г. Лекция 6 1 / 65 Пример: сравнение данных POSIX Название Мёртвая блокировка

Реализация параллелизма с использованием «эффективных объектов» Решение задач организации параллелизма приложения происходит традиционно, применяя вытесняющую многозадачность. Такая схема целесообразна,

Операционные системы Лекция 3 Процессы 1 Понятие процесса Операционная система во время работы выполняет одну или несколько программ, планирует задания (совокупность программы, команд для ее выполнения

UNIX Лекция 6 UNIX. Л.6 1 СИГНАЛЫ Прерывания и особые ситуации Прерывания. Внешние устройства ввода-вывода, системные часы и т.п. асинхронно прерывают работу ЦП. По получении сигнала прерывания ядро операционной

Название Лекция 7. Алгоритмы блокировок Операционные системы 24 марта 2016 г. Лекция 7 1 / 48 Пример: сравнение данных POSIX Мёртвая блокировка Сети Петри Требования к алгоритмам Пример Пример (окончание)

RTOS Операционные системы реального времени Страница 1 План лекции Определение операционной системы Особенности встраиваемых ОС Процессы, задачи, нити Системное время Межпроцессное взаимодействие Обработка

UNIX Лекция 5 UNIX. Л.5 1 Зомби и сироты Добавим к известным четырем состояниям процесса еще одно пятое: выполнение процесса в режиме ядра; выполнение процесса в режиме задачи; приостановка; готовность

Параллельность 1 Введение 2 3 Потоки в языке Java Потоки в языке C# Введение Параллельность может возникать на четырех уровнях Уровень машинных инструкций Уровень инструкций высокоуровневого языка программирования

Рыбинская государственная авиационная технологическая академия имени П.А. Соловьева «УТВЕРЖДАЮ» Декан ФРЭИ А.И. Дворсон РАБОЧАЯ ПРОГРАММА По дисциплине «Операционные системы» для направления 230100 «Информатика

Лабораторная работа 4. Варианты Вариант 1: Необходимо решить проблему "Санта Клаус" с использованием библиотеки PTHREAD с учетом следующих ограничений: Санта все время спит, пока его не будет либо все

1 Средства межпроцессного взаимодействия Поскольку адресные пространства каждого процесса изолированы друг от друга, система должна предоставлять процессам средства взаимодействия. Простейшее взаимодействие

Взаимоотношения между процессами.. Операционные системы 2011/12 Татьяна Романова 17 сентября 2011 г. 1 / 29 План на сегодня Терминалы. Группы процессов. Сессии. Концепция сигналов. Надежные и ненадежные

Объекты ядра Windows Типы объектов ядра маркеры доступа / access token события / event файлы / file проекции файлов / file mapping порты завершения ввода-вывода / I/O completion port задания / Job почтовые

Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Операционные системы: аспекты параллелизма Синхронизация-1 Линёв А.В. Тема обсуждения При

Операционная система FX-RTOS интерфейса HAL Версия 2.2 Содержание Введение... 3 Об этом руководстве... 3 Терминология... 3 Формат описания функций API... 3 Интерфейсы HAL... 5 Управление прерываниями...

Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Операционные системы: аспекты параллелизма Процессы и потоки Линёв А.В. Тема обсуждения

Технология адаптивного квотирования для построения высоконадежных систем Белохвостиков Эдуард инженер отдела сервисов SWD Software Построение комплексных систем Большая команда, местоположение разработчиков

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

Домашняя работа 4 (2015) Problem H41: Синхронное чтение-2 Условие этой задачи практически дословно повторяет условие задачи H32, только вместо сигналов должны быть использованы семафоры. Напишите программу,

КВАЗИПЛАНИРОВЩИК ДЛЯ ИСПОЛЬЗОВАНИЯ ПРОСТАИВАЮЩИХ ВЫЧИСЛИТЕЛЬНЫХ МОДУЛЕЙ МНОГОПРОЦЕССОРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ ПОД УПРАВЛЕНИЕМ СУППЗ А.В. Баранов, Е.А. Киселёв, Д.С. Ляховец Межведомственный суперкомпьютерный

32. Принципы построения операционных систем. Вычислительный процесс и его реализация с помощью ОС. Управление вычислительными процессами, вводом-выводом, реальной памятью. Принципы построения операционных

Параллелизм Многопоточность Зачем создавать параллельные системы? Природные ограничения Невозможно бесконечно наращивать быстродействие одноядерных процессоров. Пример 1 такт 4 ГГц процессора 0.25 нс.

Лекция 6. Использование файловых дескрипторов. Пользовательский файловый дескриптор Cистемныe вызовы для работы с файлом: 1. open/creat 1 открыть/создать файл с заданными опциями и режимом доступа int

ВГКС Кафедра ПОСТ Курс «Системное программное обеспечение» Лабораторная работа 1 (4 часа) Тема: «Создание потоков в Win32 API для ОС MS Windows». Создается поток функцией CreateThread, которая имеет следующий

ГОУВПО «Поволжский государственный университет телекоммуникаций и информатики» Раздел 6. Программное обеспечение управляющих комплексов. Операционные системы Лектор: реального времени проф. кафедры АЭС

Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Операционные системы: аспекты параллелизма Задача "Производители-Потребители" Потребители

«Операционные системы» Контрольная работа. Задание. Управление процессами. Наиболее сложно объясняемое задание, но я постараюсь объяснить, чтобы было хоть коечто понятно. Итак, нам дана таблица и процесса,

Лекция 22 Топологическая сортировка. 22.1. Представление произвольного дерева в виде двоичного. 22.1.1. В отличие от двоичного дерева произвольное дерево не может быть пустым (по определению оно должно

Министерство образования Республики Беларусь Учреждение образования «Белорусский государственный университет информатики и радиоэлектроники» Кафедра электронно-вычислительных средств Д. С. Лихачёв РАЗРАБОТКА

Лабораторная работа 4 Цель: Лабораторная работа предназначена для приобретения практического опыта в создании приложения с использованием языка программирования С++ для математических расчѐтов. Призвана:

Модуль 1. ОБЩИЕ СВЕДЕНИЯ ОБ ОПЕРАЦИОННЫХ СИСТЕМАХ, СРЕДАХ И ОБОЛОЧКАХ 1. Операционная система это 1) комплекс управляющих и обрабатывающих программ 2) компоненты вычислительных машин и вычислительных систем

СИСТЕМНОЕ ПРОГРАММИРОВАНИЕ В WINDOWS Побегайло А. П. Системное программирование в Windows. СПб.: БХВ- Петербург, 2006. - 1056 с: ил. ISBN 5-94157-792-3 Подробно рассматриваются вопросы системного программирования

СОСТАВИТЕЛИ: Рябый В.В., старший преподаватель кафедры математического обеспечения электронно-вычислительных машин Белорусского государственного университета; Побегайло А.П., доцент кафедры технологии

Примитивы синхронизации 2011 В чем основная проблема программных методов взаимоисключения? Невозможно гарантировать неразрывность выполнения отдельных действий: Программа может прерваться в любой момент

И межпроцессного взаимодействия (interprocess communication ) в многозадачной операционной системе . Проблема заключается в обеспечении того, чтобы парикмахер работал, когда есть клиенты и отдыхал, когда клиентов нет.

Энциклопедичный YouTube

    1 / 1

    ✪ Неэффективное собрание. Фильм «Афо́ня»

Субтитры

Проблема

Аналогия основана на гипотетической парикмахерской с одним парикмахером. У парикмахера есть одно рабочее место и приемная с несколькими стульями. Когда парикмахер заканчивает подстригать клиента, он отпускает клиента и затем идет в приёмную, чтобы посмотреть, есть ли там ожидающие клиенты. Если они есть, он приглашает одного из них и стрижет его. Если ждущих клиентов нет, он возвращается к своему креслу и спит в нем.

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

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

Проблема спящего парикмахера часто приписывается Эдсгеру Дейкстра (1965), одному из пионеров информатики.

Решение

Существует несколько возможных решений данной проблемы. Основной элемент каждого из решений - мьютекс - механизм, который гарантирует, что изменить состояние (state ) в данный момент времени может только один из участников. Парикмахер должен захватить мьютекс, прежде чем проверить клиентов, и освободить его, когда он начинает или спать, или работать. Клиент должен захватить тот же мьютекс, прежде чем войти в парикмахерскую, и освободить его, как только он займет место или в приемной, или у парикмахера. Это устраняет обе проблемы, упомянутые в предыдущей секции. Возможно также использование более общего механизма семафоров для указания текущего состояние системы. Например, при помощи семафора можно выразить число людей в приемной.

У варианта той же задачи с несколькими парикмахерами есть дополнительная сложность координирования нескольких парикмахеров среди ждущих клиентов.

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

Проблема обедающих философов

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

Жизнь философа состоит из чередующихся периодов поглощения пищи и размышлений. (Разумеется, это абстракция, даже применительно к философам, но остальные процессы жизнедеятельности для нашей задачи несущественны.) Когда философ голоден, он пытается получить две вилки, левую и правую, в любом порядке. Если ему удалось получить две вилки, он некоторое время ест, затем кладет вилки обратно и продолжает размышления. Вопрос состоит в следующем: можно ли написать алгоритм, который моделирует эти действия для каждого философа и никогда не застревает? (Кое-кто считает, что необходимость двух вилок выглядит несколько искусственно. Возможно, нам следует заменить итальянскую пищу блюдами китайской кухни, спагетти - рисом, а вилки - соответствующими палочками.)

Можно изменить программу так, чтобы после получения левой вилки проверялась доступность правой. Если правая вилка недоступна, философ отдает левую обратно, ждет некоторое время и повторяет весь процесс. Этот подход также не будет работать, хотя и по другой причине. Если не повезет, все пять философов могут начать процесс одновременно, взять левую вилку, обнаружить отсутствие правой, положить левую обратно на стол, одновременно взять левую вилку, и так до бесконечности. Ситуация, в которой все программы продолжают работать сколь угодно долго, но не могут добиться хоть какого-то прогресса, называется зависанием процесса (по-английски starvation, буквально «умирание от голода». Этот

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

Вы можете подумать: «Если философы будут размышлять в течение некоторого случайно выбранного промежутка времени после неудачной попытки взять правую вилку, вероятность того, что все процессы будут продолжать топтаться на месте хотя бы в течение часа, невелика». Это правильно, и для большинства приложений повторение попытки спустя некоторое время не является проблемой. Например, в локальной сети Ethernet в ситуации, когда два компьютера посылают пакеты одновременно, каждый должен подождать случайно заданное время и повторить попытку - на практике это решение хорошо работает. Тем не менее в некоторых приложениях предпочтительным является другое решение, работающее всегда и не зависящее от случайных чисел (например, в приложении для обеспечения безопасности на атомных электростанциях).

Внести улучшение, исключающее взаимоблокировку и зависание процесса: защитить пять операторов, следующих за запросом think, бинарным семафором. Тогда философ должен будет выполнить операцию Down на переменной mutex прежде, чем потянуться к вилкам. А после возврата вилок на место ему следует выполнить операцию Up на переменной mutex. С теоретической точки зрения решение вполне подходит. С точки зрения практики возникают проблемы с эффективностью: в каждый момент времени может есть спагетти только один философ. Но вилок пять, поэтому необходимо разрешить есть в каждый момент времени двум философам.

Решение, исключает взаимоблокировку и позволяет реализовать максимально возможный параллелизм для любого числа философов. Здесь используется массив state для отслеживания душевного состояния каждого философа: он либо ест, либо размышляет, либо голодает (пытаясь получить вилки). Философ может начать есть, только если ни один из его соседей не ест. Соседи философа с номером i определяются макросами LEFT и RIGHT (то есть если i = 2, то LEFT=

Проблема читателей и писателей

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

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

Проблема спящего брадобрея

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

В предлагаемом решении используются три семафора: customers, для подсчета ожидающих посетителей (клиент, сидящий в кресле брадобрея, не учитывается - он уже не ждет); barbers, количество брадобреев (0 или 1), простаивающих в ожидании клиента, и mutex для реализации взаимного исключения. Также используется переменная waiting, предназначенная для подсчета ожидающих посетителей.

Она является копией переменной customers. Присутствие в программе этой переменной связано с тем фактом, что прочитать текущее значение семафора невозможно. В этом решении посетитель, заглядывающий в парикмахерскую, должен сосчитать количество ожидающих посетителей. Если посетителей меньше, чем стульев, новый посетитель остается, в противном случае он уходит.

Когда брадобрей приходит утром на работу, он выполняет процедуру barber, блокируясь на семафоре customers, поскольку значение семафора равно 0. Затем брадобрей засыпает, и спит, пока не придет первый клиент.

Приходя в парикмахерскую, посетитель выполняет процедуру customer, запрашивая доступ к mutex для входа в критическую область. Если вслед за ним появится еще один посетитель, ему не удастся что-либо сделать, пока первый посетитель не освободит доступ к mutex. Затем посетитель проверяет наличие свободных стульев, в случае неудачи освобождает доступ к mutex и уходит.

Если свободный стул есть, посетитель увеличивает значение целочисленной переменной waiting. Затем он выполняет процедуру up на семафоре customers, тем

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

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

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

Действие еще одной классической проблемной ситуации межпроцессного взаимодействия разворачивается в парикмахерской. В парикмахерской есть один брадобрей, его кресло и n стульев для посетителей. Если желающих воспользоваться его услугами нет, брадобрей сидит в своем кресле и спит. Если в парикмахерскую приходит клиент, он должен разбудить брадобрея. Если клиент приходит и видит, что брадобрей занят, он либо садится на стул (если есть место), либо уходит (если места нет). Необходимо запрограммировать брадобрея и посетите­лей так, чтобы избежать состояния состязания. У этой задачи существует много аналогов в сфере массового обслуживания, например информационная служба, обрабатывающая одновременно ограниченное количество запросов, с компьютеризированной системой ожидания для запросов.

В предлагаемом решении используются три семафора: customers, для подсчета ожидающих посетителей (клиент, сидящий в кресле брадобрея, не учитывается); barbers, количество брадобреев (0 или 1), простаивающих в ожидании клиента, и mutex для реализации взаимного исключения. Также используется переменная waiting, предназначенная для подсчета ожидающих посетителей.

Она является копией переменной customers. Присутствие в программе этой переменной связано с тем фактом, что прочитать текущее значение семафора невозможно. В этом решении посетитель, заглядывающий в парикмахерскую, должен сосчитать количество ожидающих посетителей. Если посетителей меньше, чем стульев, новый посетитель остается, в противном случае он уходит.

Планирование процессов. Задачи алгоритмов планирования.

Когда компьютер работает в многозадачном режиме, на нем могут быть активны­ми несколько процессов, пытающихся одновременно получить доступ к процессору. Эта ситуация возникает при наличии двух и более процессов в состоянии готовности. Если доступен только один процессор, необходимо выбирать между процессами. Отвечающая за это часть операционной системы называется планировщиком , а используемый алгоритм - алгоритмом планирования .

Планирование - это разделение вычислительных ресурсов системы между процессами и потоками.

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

данные и т. д.

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

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

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

В-третьих, когда процесс блокируется на операции ввода-вывода, семафоре, или по какой-либо другой причине, необходимо выбрать и запустить другой процесс. Иногда причина блокировки может повлиять на выбор. Например, если А -

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

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

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

1. Системы пакетной обработки данных.

2. Интерактивные системы.

3. Системы реального времени.

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

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

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

Задачи алгоритмов планирования.

Чтобы разработать алгоритм планирования, необходимо иметь представление о том, что должен делать хороший алгоритм. Некоторые задачи зависят от среды (системы пакетной обработки, интерактивные или реального времени), но есть задачи, одинаковые во всех системах. Список задач представлен в таблице.

Планирование в системах пакетной обработки данных.

«Первым пришел - первым обслужен»

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

Основным преимуществом этого алгоритма является то, что его легко понять и столь же легко программировать.

Недостатком является абсолютная неоптимизированность планирования.

«Кратчайшая задача - первая»

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

Преимущество алгоритма заключается в оптимизации задачи.

Недостатком является то, что эта схема работает лишь в случае одновременного наличия задач.


Похожая информация.


Проблема

Аналогия основана на гипотетической парикмахерской с одним парикмахером. У парикмахера есть одно рабочее место и приемная со многими стульями. Когда парикмахер заканчивает подстригать клиента, он отпускает клиента и затем идет в приёмную, чтобы посмотреть, есть ли ждущие клиенты. Если есть, он приглашает одного из них и стрижет его. Если ждущих клиентов нет, он возвращается к своему креслу и спит в нем.

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

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

Проблема спящего парикмахера часто приписывается Эдсгеру Дейкстра (1965), одному из пионеров информатики.

Решение

Доступно множество возможных решений. Основной элемент каждого - mutex , который гарантирует, что изменить состояние (state ) может только один из участников. Парикмахер должен захватить это mutex исключение, прежде чем проверить клиентов, и освободить его, когда он начинает или спать, или работать. Клиент должен захватить mutex, прежде чем войти в магазин, и освободить его, как только он займет место или в приемной, или у парикмахера. Это устраняет обе проблемы, упомянутые в предыдущей секции. Семафоры также обязаны указывать на состояние системы. Например, можно было бы сохранить число людей в приемной.

У варианта с несколькими парикмахерами есть дополнительная сложность координирования нескольких парикмахеров среди ждущих клиентов.

См. также

  • Проблема курильщиков

Ссылки

  • Modern Operating Systems (2nd Edition) by Andrew S. Tanenbaum (ISBN 0-13-031358-0)
  • The Little Book of Semaphores by Allen B. Downey, http://greenteapress.com/semaphores
  • Cooperating sequential processes by E.W. Dijkstra. Technical Report EWD-123, 1965, Technological University, Eindhoven, The Netherlands.

Wikimedia Foundation . 2010 .