ITMO-Operational-Systems-labs-4-sem

Labs | Tests

Labs (1-3)	Labs (4-6)	Tests (1-3)	Tests (4-6)
lab 1	lab 4	test 1	test 4
lab 2	lab 5	test 2	test 5
lab 3	lab 6	test 3	test 6

---

За тесты большое спасибо Паше❤️

Lab 1

task

Extra task

manual

Lab 2

task

Extra task

manual

Lab 3

task

Extra task

manual

Lab 4

task

Extra task

manual

Lab 5

task

Extra task

manual

Lab 6

task

Extra task

manual

Test 1

1. Перечислите основные функции программ-диспетчеров - предшественников операционных систем на этапе однопрограммной пакетной обработки

Лекция:

• Повторное использование кода, линковки и загрузки
• Оптимизация хранения системы ввода/вывода
• Прерывание
• Однопрограммная пакетная обработка???

Файл со Studfiles:

• Автоматизация линковки (связи приложений с ячейками памяти)
• Оптимизация взаимодействия с устройствами ввода/вывода

2. Перечислите основные фукнции операционных систем, появившихся на этапе мультипрограммной обработки

Вроде бы лекция:

• Разделение процессорного времени (processor sharing)

• Виртуальная память

• Защита памяти

• Планирование комплексного использования ресурсов

• Универсальный доступ к информации на внешних устройствах

• Обеспечение коммуникации между программами

  Файл со Studfiles:

  1. Разделение времени между программы привело к созданию таймера и смене контекста, выполнения нескольких программ.
  2. Виртуализация памяти: только ОС имеет право писать физические адреса памяти, ПО может работать только с выделенной памятью.
  3. Системные вызовы - обращение программного обеспечения к операционной системе с просьбой предоставить какие-либо возможности.
  4. Мульти планирование времени
  5. Синхронизация и коммуникация между программами
  6. Разделение доступа к внешней информации, файлам

3. Дайте определение или объясните сущность механизма

"системный вызов" Лекция: Системный вызов - обращение пользователей программы к ядру ОС с просьбой предоставить дополнительный ресурс или выполнить привелигированную операцию

4. Дайте определение или объясните сущность механизма

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

5. Дайте определение или объясните сущность механизма

"виртуальная память" Лекция: Виртуальная память - абстракция, позволяющая при создании или компиляции программы использовать адреса, отсчитываемые от нуля, а при исполнении заменять их на физические Файл со Studfiles: Виртуальная память - это явление когда часть физической памяти выделяется для определенного процесса и ее адреса для данного процесса преобразуются в новые, начинающиеся с нуля

6. Дайте определение понятия

"Операционная система" Файл со Studfiles: Операционная система - базовое системное программное обеспечение, управляющее работой компьютера и являющееся интерфейсом между аппаратурой, прикладным программным обеспечением и пользователем.

Test 2

1. Перечислите основные цели работы современной ОС

Лекция:

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

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

• Управление исполнением программы
• Обнаружение и обработка ошибок
• Высокоуровневый доступ к устройствам ввода/вывода
• Управление хранилищем данных
• Мониторинг ресурсов

3. Основной принцип обеспечения ОС эффективного использования ресурсов (PDCA)

PDCA - адаптивное управление

4. Какие основные механизмы используются под системой управления процессами

• Дескрипторы процессов, PCD
• Планировщик

5. Какие основные механизмы используются подсистемой управления файлами?

• Преобразование имен
• Каталоги

6. Два основых способа реализации пользовательского интерфейса в системе

• CLI - Command Line Interface
• GUI - Graphic User Interface

Test 3

1. В чем отличие программного кода, исполняемого в режиме ядра ОС от программного кода, исполняемого в режиме пользовательского приложения

Файлик:

Режим ядра - Выполнение в привелигированном режиме. Код ядра при этом полностью резидентен.

ПО - не всегда резидентно. Нет привелигерованного режима

Бинг:

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

2. Перечислите основные принципы (подходы), заложенные в основу архитектур современных ОС

Файлик:

1. Модульная организация
2. Функциональная избыточность
3. Функциональная избирательность
4. Параметрическая универсальность
5. Поддержка концепции многоуровневой иерархической системы
6. Разделение всех модулей ОС на модули ядра и выполняющиеся в пользовательском режиме

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

3. Перечислите названия слоев в многослойной монолитной архитектуре ОС

Файлик:

1. Поддержка аппаратных средств ядра
2. Машинно-зависимые уровни (HAL)
3. Базовые механизмы ядра
4. Менеджер ресурсов (слой принятий решений)
5. Системные вызовы и API

4. Каково назначение слоя “Средства аппартной поддержки ядра” в многослойной монолитной архитектуре ОС и где физически реализуются его функции?

Файлик:

1. Система прерываний (сигналов, сообщающий процессору о наступлении какого-либо события)
2. Средства поддержки привелигированного режима (обычно основаны на системном регистре процессора)
3. Средства поддержки виртуальной памяти
4. Средства переключения контекстов процессов (данные о состоянии процесса в момент его приостановки)
5. Средства защиты памяти
6. Системный таймер

5. Какие функции ОС реализуются в микроядре при использовании микроядерной архитектуры?

Файлик:

В ядре есть два слоя:

• Машинно-зависимые модули
• Базовые механизмы ядра

В пользовательские режимы будут входить сервера (память, вычисление), ПО. При этом они все равноправно могут вызывать ядро.

Идея заключается в том, что есть вещи, которые обязательно нужно выполнять в ядре. Например - выделение памяти. А принятие решений будет существовать отдельно как пользовательское ПО. Сервера не находятся в оперативной памяти и появляются там только по требованию

????Системные вызовы????:

• Базовые механизмы ядра
• Машинно-зависимые модули (HAL)

6. Перечислите достоинства и недостатки многослойной монолитной архитектуры ОС в сравнении с микроядерной архитектурой ОС

Файлик: Плюсы:

• Организация ядра легче
• Выше процессорная производительность

Минусы:

• Огромные накладные расходы по оперативной памяти
• ПО не может выполняться на нескольких аппаратных средствах, т.е. ядра не взаимодействуют друг с другом

Test 4

(Два вопроса скорее всего не совпадут. По итогу у нас только 3 не совпал, там было про зомби-процессы)

1. Объясните в чем отличие понятий “процесс”, “поток” и “волокно”?

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

2. Перечислите, какие функции выполняет подсистема управления процессами ОС

1. Создание процессов: Подсистема управления процессами позволяет создавать новые процессы в системе. Это может быть выполнено пользовательскими программами или самой операционной системой.
2. Управление ресурсами процесса: Она отвечает за выделение и управление ресурсами, необходимыми для выполнения процесса, такими как память, центральный процессор (ЦП), файловые дескрипторы и другие ресурсы.
3. Планирование процессов: Эта функция определяет, какие процессы получают доступ к процессорным ресурсам в конкретный момент времени. Подсистема управления процессами включает в себя планировщик, который определяет порядок выполнения процессов в системе.
4. Контроль и мониторинг процессов: Она обеспечивает механизмы для контроля и мониторинга активных процессов, включая информацию о их состоянии, использовании ресурсов и т. д.
5. Синхронизация процессов: Подсистема управления процессами обеспечивает механизмы для синхронизации выполнения процессов, такие как мьютексы, семафоры, условные переменные и другие примитивы синхронизации.
6. Коммуникация между процессами: Она предоставляет средства для обмена данными и взаимодействия между процессами, например, через сокеты, каналы, сигналы и разделяемую память.
7. Завершение процессов: Подсистема управления процессами отслеживает завершение процессов и освобождает связанные с ними ресурсы после завершения выполнения.

3. Перечислите, какие действия осуществляет ОС при диспетчеризации процессов

1. Выбор процесса для выполнения: ОС выбирает один из готовых к выполнению процессов для запуска на процессоре. Этот выбор может осуществляться на основе различных критериев, таких как приоритет процесса, время ожидания, использование процессора и другие факторы.
2. Сохранение контекста: Перед переключением на новый процесс ОС сохраняет контекст (состояние) текущего процесса. Контекст включает в себя значения регистров процессора, указатель стека, счетчик команд и другие регистры состояния процесса.
3. Загрузка контекста нового процесса: ОС загружает сохраненный контекст выбранного процесса, чтобы возобновить его выполнение. Это включает восстановление значений регистров процессора, указателя стека и других регистров состояния.
4. Переключение процессорного режима: В некоторых случаях, например, при переходе между процессами с разными уровнями привилегий, ОС может также выполнять переключение между режимами работы процессора, например, между пользовательским и привилегированным режимами.
5. Выделение процессорного времени: ОС назначает процессу определенное количество процессорного времени для выполнения. Это может быть квант времени в планировщике по времени или выполнение до события в случае событийного планирования.
6. Управление событиями: ОС также может обрабатывать различные события, такие как сигналы, исключения, запросы ввода-вывода и другие, в процессе диспетчеризации процессов. Это может привести к изменению состояния процесса или переключению на другой процесс в случае необходимости обработки события.

3 В каком сдучае может получиться процесс пребыв в состоянии zombie длительное время?

Процесс в состоянии “zombie” или “зомби-процесс” в Unix-системах - это процесс, который завершил свое выполнение, но все еще присутствует в списке процессов операционной системы. Это происходит, когда родительский процесс не считывает статус завершения дочернего процесса с помощью системного вызова wait().

Процесс может оставаться в состоянии “zombie” длительное время в следующих случаях:

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

4. Охарактеризуйте, какая информация хранится в дескрипторе процессора (PCB)

1. Идентификатор процесса (PID): Уникальный числовой идентификатор, который используется для идентификации процесса в системе.
2. Состояние процесса: Состояние, в котором находится процесс, такое как выполнение, ожидание, готовность и т. д.
3. Контекст процесса: Это включает в себя информацию о текущем состоянии процесса на момент приостановки его выполнения. В контексте процесса могут быть сохранены значения регистров процессора, указатель стека, счетчик команд и другие регистры состояния.
4. Информация о памяти: PCB может содержать информацию о выделенных для процесса областях памяти, таких как адрес начала и размеры сегментов кода, данных и стека.
5. Информация о приоритете: Это значение, определяющее приоритет выполнения процесса в системе относительно других процессов.
6. Информация об управлении ресурсами: PCB может содержать информацию о ресурсах, выделенных процессу, таких как файловые дескрипторы, открытые сокеты и другие ресурсы.
7. Сведения о расписании: Это информация о времени, когда процесс был создан, последний раз запущен, количество процессорного времени, использованного процессом, и другие характеристики, связанные с его выполнением.
8. Информация об управлении процессом: Это может включать в себя информацию о родительском процессе, список дочерних процессов, обработчики сигналов и другие атрибуты управления процессом.

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

1. Создание (Creation): Процесс создается операционной системой или существующим процессом. На этом этапе операционная система выделяет необходимые ресурсы для процесса.
2. Готовность (Ready): Процесс готов к выполнению, но ожидает выделения процессорного времени. Это происходит, когда все необходимые ресурсы доступны, и процесс ожидает своей очереди на выполнение.
3. Выполнение (Running): Процесс активно выполняется на процессоре. Он использует процессорные ресурсы для выполнения своих инструкций.
4. Ожидание (Waiting): Процесс временно приостановлен и ожидает наступления определенного события или ресурса, например, завершения операции ввода-вывода или получения сигнала от другого процесса.
5. Завершение (Termination): Процесс завершается и освобождает все выделенные ему ресурсы. Это может произойти по завершении своей работы или в результате принудительного завершения операционной системой или пользователем.

Разрешенные переходы:

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

• Из состояния Готовность процесс может перейти в состояние Выполнение, когда ему выделено процессорное время операционной системой.

• Процесс может перейти из состояния Выполнение в состояние Ожидание, если он ожидает завершения какой-то операции или наступления события.

• Из состояния Ожидание процесс может вернуться в состояние Готовность, когда требуемое событие произойдет или ресурс станет доступным.

• Процесс может завершиться и перейти в состояние Завершение после завершения своей работы или в результате принудительного завершения операционной системой или пользователем.

  

Test 5

1. Перечислите виды планирования ОС и укажите для каждого вида планирования его место в жизненном цикле процесса ОС: из какого состояния (состояний) в какое состояние переводится процесс по существующему плану

1. Планирование задач (Job Scheduling): Это планирование на самом высоком уровне, которое определяет, какие процессы будут загружены из очереди задач в очередь готовности. Процесс переходит из состояния “новый” в состояние “готовый”.
2. Планирование процессора (CPU Scheduling): Это планирование на среднем уровне, которое определяет, какие процессы в очереди готовности будут выполняться (или получат CPU). Процесс переходит из состояния “готовый” в состояние “выполнение”.
3. Планирование ввода/вывода (I/O Scheduling): Это планирование на низком уровне, которое определяет, какие операции ввода/вывода будут выполняться. Процесс переходит из состояния “ожидание” в состояние “готовый” после завершения операции ввода/вывода.

2. Перечислите основные критерия планирования процессов

Файлик:

• Справедливость: гарантировать каждому заданию или процессу определенную часть времени использования процессора в компьютерной системе, стараясь не допустить возникновения ситуации, когда процесс одного пользователя постоянно занимает процессор, в то время как процесс другого пользователя фактически не приступал к выполнению.
• Эффективность: постараться занять процессор на все 100% рабочего времени, не позволяя ему простаивать в ожидании процессов готовых к исполнению. В реальных вычислительных системах загрузка процессора колеблется от 40 до 90 процентов.
• Сокращение полного времени выполнения (turnaround time): обеспечить минимальное время между стартом процесса или постановкой задания в очередь для загрузки и его завершением.
• Сокращение времени ожидания (waiting time): минимизировать время, которое проводят процессы в состоянии готовность и задания в очереди для загрузки.
• Сокращение времени отклика (response time): минимизировать время, которое требуется процессу в интерактивных системах для ответа на запрос пользователя.

Бот:

1. Производительность (Throughput): Количество процессов, которые успешно выполняются за единицу времени.
2. Время оборота (Turnaround Time): Общее время, которое проходит с момента поступления процесса до момента его завершения.
3. Время ожидания (Waiting Time): Общее время, которое процесс проводит в очереди, ожидая доступа к процессору.
4. Время отклика (Response Time): Время, которое проходит с момента поступления запроса до момента, когда процесс начинает выполняться.
5. Справедливость (Fairness): Гарантия того, что каждый процесс получит справедливую долю процессорного времени.
6. Предсказуемость (Predictability): Степень, в которой можно предсказать, когда процесс будет выполнен.
7. Балансировка нагрузки (Load Balancing): Распределение работы равномерно между процессорами в многопроцессорной системе.
8. Эффективность использования ресурсов (Resource Utilization): Максимизация использования процессора и других системных ресурсов.

3. В чем разность невытесняющих и вытесняющих алгоритмов планирования

Файлик (кратко):

• вытесняющие, когда решение о прекращении выполнения потока (процесса) принимает ОС;
• невытесняющие, когда это решение принимается самим потоком, а не ОС, и даже не пользователем.

Другой файлик/первая ссылка в гугле:

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

Бот:

1. Невытесняющие (Non-preemptive) алгоритмы:
   • В невытесняющих алгоритмах процесс сохраняет ЦПУ до тех пор, пока он не завершится или не перейдет в состояние ожидания, например, по событию ввода-вывода или по запросу блокировки.
   • Пока процесс выполняется, он может обращаться к ЦПУ без прерывания другими процессами, даже если появляется более приоритетный процесс.
   • Примеры невытесняющих алгоритмов включают FCFS (First-Come, First-Served) и SJF (Shortest Job First).
2. Вытесняющие (Preemptive) алгоритмы:
   • В вытесняющих алгоритмах операционная система может прерывать выполнение текущего процесса и передавать управление более приоритетному процессу.
   • Процесс может быть вытеснен с ЦПУ по истечении кванта времени (time slice) или при появлении более приоритетного процесса.
   • Вытесняющие алгоритмы обычно реализуются в многозадачных операционных системах, где целью является обеспечение отзывчивости системы и справедливого распределения ресурсов.
   • Примеры вытесняющих алгоритмов включают Round Robin, Priority Scheduling, и Multilevel Queue.

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

4. В каком случае алгоритм First-Come, First-Served окажется эффективнее алгоритма Round Robin и почему?

Бот (1 вариант):

Алгоритм First-Come, First-Served (FCFS) эффективнее алгоритма Round Robin в случае, когда процессы имеют различные времена выполнения и относительно небольшие кванты времени в алгоритме Round Robin.

Вот почему:

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

Однако, важно отметить, что если все процессы имеют примерно одинаковые времена выполнения или если время выполнения процессов слишком велико по сравнению с квантом времени в алгоритме Round Robin, то алгоритм Round Robin может быть предпочтительнее, поскольку он обеспечивает более равномерное распределение процессорного времени между процессами и может обеспечить более предсказуемую отзывчивость системы.

Бот (2 вариант):

Алгоритм First-Come, First-Served (FCFS) оказывается более эффективным, чем алгоритм Round Robin, когда задачи имеют различные времена исполнения и некоторые из них требуют значительного времени для завершения.

FCFS прост: он выполняет задачи в порядке их поступления, не прерывая выполнение ни одной из задач до её завершения. Если одна или несколько задач требуют длительного времени для завершения, FCFS может завершить их быстрее, чем Round Robin, который вынужден переключаться между задачами через фиксированные интервалы времени.

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

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

5. Для приведенных данных о CPU-burst и времени рождения процессов постройте диаграмму выполнения процессов на процессоре, используя вытесняющий алгоритм Short Job First: буква “И” в клетки таблицы обозначает, что процесс в этот момент времени находится в состоянии “Исполнение”; буква “Г” в таблице обозначает, что процесс в этот момент времени находится в состоянии “Готовность”; пустая ячейка обозначает, что процесс еще не родился или завершил выполнение. Квант непрерывного выполнения состовляет три единицы времени (Нуждается в апруве)

---

---

Для построения диаграммы выполнения процессов по алгоритму Shortest Job First (SJF) необходимо учитывать время их появления в очереди и продолжительность CPU-burst.

Время	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23
p0	Г	Г	Г	Г	Г	Г	Г	Г	Г	Г	И	И	И	Г	Г	Г	Г	И	И	И	И	И
p1		Г	Г	И	И	И
p2	И	И	И	Г	Г	Г	И	И	И	И
p3													Г	И	И	И	И

Пояснение:

• p0 появляется в момент времени 0 и имеет продолжительность 8, поэтому он выполняется до момента времени 8.
• p1 появляется в момент времени 1 и имеет продолжительность 3. Он выбирается следующим, так как это кратчайший процесс.
• p2 появляется в момент времени 0 и имеет продолжительность 7. Он становится следующим после p1, так как это кратчайший процесс.
• p3 появляется в момент времени 12 и имеет продолжительность 4. После завершения p2, p3 становится следующим, так как это кратчайший процесс среди оставшихся.

Это диаграмма выполнения процессов с использованием алгоритма SJF.

Test 6

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

shared int lock = 0;
	while (lock); lock = 1;
	critical section
	lock = 0;

---

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

1. Ожидание (Busy Waiting): При использовании такого метода поток, пытающийся войти в критическую секцию, будет активно ожидать освобождения блокировки, проверяя состояние переменной (в данном случае, проверяя lock). Это приводит к затрате процессорного времени, даже если поток неактивен и простаивает.
2. Возможность возникновения голодания (Starvation): Если несколько потоков пытаются войти в критическую секцию, но один из них постоянно блокирует остальные, они могут никогда не получить доступ к критической секции. Это может привести к голоданию потоков, которые никогда не смогут выполнить свою работу.
3. Возможность возникновения состояния гонки (Race Condition): Если два или более потока пытаются одновременно установить переменную lock в значение 1, может возникнуть состояние гонки, когда ни один из них не получит доступ к критической секции, или когда два или более потока войдут в нее одновременно.

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

---

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

shared int turn = 0;
	while (turn != i);
		critical section
	turn = 1 - i;

---

Этот алгоритм реализует строго чередование между двумя процессами, помеченными индексами 0 и 1. В данном алгоритме переменная turn используется для определения того, какой процесс должен войти в критическую секцию. Если turn равно i, то процесс с индексом i имеет право на вход в критическую секцию.

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

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

---

3. Какого рода проблемы и в какой момент исполнения кода могут возникнуть при использовании приведенного ниже алгоритма флагов готовности?

shared int ready[2] = {0, 0};
	ready[i] = 1;
	while (ready[1 - i]);
		critical section
	ready[i] = 0;

---

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

1. Гонки данных (Race conditions): Не существует гарантии, что оба потока будут видеть изменения в флаге ready одновременно. Если два потока установят свои флаги ready в 1 одновременно и попытаются войти в критическую секцию, возникнет гонка данных.
2. Deadlock (Взаимная блокировка): Если один поток устанавливает свой флаг ready, а другой поток не сможет установить свой флаг ready (например, из-за ошибки или блокировки), то первый поток останется заблокированным в цикле while, и программа зависнет.
3. Starvation (Голодание): Если один поток постоянно устанавливает и сбрасывает свой флаг ready, другой поток может оказаться постоянно блокированным и никогда не получить доступ к критической секции.
4. Порядок доступа: Поскольку порядок выполнения потоков не определен, могут возникнуть проблемы, связанные с порядком доступа к критической секции.

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

---

4. Сформулируйте формальные определения операций P(S) и V(S) над переменной-семафором S

Бот (1 вариант):

Операции P(S) и V(S) используются для работы с семафорами и обычно используются для синхронизации доступа к ресурсам в многозадачных и параллельных системах. Вот их формальные определения:

1. Операция P(S), также известная как "захват" (acquire) или "ожидание" (wait):

   P(S):
     Если значение семафора S больше нуля, уменьшить значение семафора S на единицу и продолжить выполнение.
     Иначе, приостановить выполнение текущего процесса (или потока) до тех пор, пока значение семафора S не станет положительным, а затем уменьшить его значение на единицу и продолжить выполнение.
   
   

2. Операция V(S), также известная как "освобождение" (release) или "увеличение" (signal):

   V(S):
     Увеличить значение семафора S на единицу.
     Если есть процессы (или потоки), которые ждали на семафоре S (путем выполнения операции P), один из них должен быть разблокирован, чтобы продолжить выполнение.
   
   

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

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

Бот (2 вариант):

Операции P(S) и V(S), также известные как операции захвата (acquire) и освобождения (release) для семафора S, могут быть формально определены следующим образом:

1. Операция P(S):
   • Если значение S больше нуля, то уменьшить значение S на 1.
   • Если значение S равно нулю, то поток, выполняющий операцию P(S), блокируется до тех пор, пока другой поток не выполнит операцию V(S) и увеличит значение S.
2. Операция V(S):
   • Увеличить значение S на 1.
   • Если есть потоки, заблокированные на операции P(S), один из этих потоков разблокируется.

Формально можно представить эти операции следующим образом:

P(S):
  while (S <= 0) {
    // Блокировать поток
  }
  S = S - 1;

V(S):
  S = S + 1;
  // Разблокировать один из заблокированных потоков, если такие есть

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

5. Перечислите условия возникновения тупиков

Эмин:

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

Бот:

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

1. Взаимная блокировка (Mutual Exclusion): Каждый ресурс либо уже занят, либо доступен только одному процессу в определенный момент времени. Если процесс занял ресурс и запрашивает другой, который уже занят другим процессом, он может блокироваться и ждать освобождения этого ресурса.
2. Удержание и ожидание (Hold and Wait): Процесс может удерживать один или несколько ресурсов и одновременно запрашивать доступ к другим ресурсам. Если запрошенные ресурсы не доступны, процесс может ожидать их освобождения, но при этом не освобождает ресурсы, которые уже удерживает. Это создает возможность для возникновения тупика.
3. Отсутствие вытеснения (No Preemption): Ресурсы не могут быть вытеснены у процесса, который их удерживает, а могут быть освобождены только процессом, который их удерживает. Если процесс запрашивает ресурс, удерживаемый другим процессом, и не может быть вытеснен, он может быть блокирован до тех пор, пока ресурс не будет освобожден.
4. Циклическая зависимость (Circular Wait): Два или более процесса ждут друг друга таким образом, что создается циклическая зависимость. Например, процесс A ожидает ресурс, удерживаемый процессом B, в то время как процесс B ожидает ресурс, удерживаемый процессом A. Это создает цикл зависимостей и ведет к блокировке всех процессов в тупике.

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