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

Проце́сс — выполнение пассивных инструкций компьютерной программы на процессоре ЭВМ. Стандарт ISO 9000:2000 Definitions определяет процесс как совокупность взаимосвязанных и взаимодействующих действий, преобразующих входящие данные в исходящие.

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

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

Процесс – это объединение нескольких нитей. А объединяет эти нити единое виртуальное адресное пространство. В этом пространстве размещаются код и данные приложения (обычно это один exe- и несколько dll-модулей). Именно единство этого пространства и делает обмен данными между нити приложения предельно простым.

1. Нить(thread) определяет последовательность исполнения кода в процессе.

Процесс ничего не исполняет, он просто служит контейнером нитей.

2. Нить всегда создаются в контексте какого-либо процесса, и вся их жизнь проходит только в его границах.

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

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

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

Волокна (fibers) — аналогичны нитям, но используют кооперативную многозадачность (Тип многозадачности, при котором следующая задача выполняется только после того, как текущая задача явно объявит себя готовой отдать процессорное время другим задачам)

Какие есть подходы к созданию многопоточных программ

Есть две основные парадигмы создания многопоточных прогамм: парадигма, основанная на использовании общего адресного пространства и парадигма на использовании разделенного адресного пространства

9. Опишите жизненный цикл процесса. Назовите требования к алгоритмам планирования процессов.

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

Системный вызов fork обладает уникальным свойством: он возвращает сразу два значения. В порожденном процессе эта функция возвращает 0, а в родительском — идентификатор потомка. Поскольку в остальном процессы идентичны, они должны проверять это значение, чтобы определить, в какой роли следует выступать дальше.

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

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

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

Эффективность – постараться занять процессор на все 100% рабочего времени, не позволяя ему простаивать в ожидании процессов, готовых к исполнению. В реальных вычислительных системах загрузка процессора колеблется от 40 до 90%.

Сокращение полного времени выполнения (turnaround time) – обеспечить минимальное время между стартом процесса или постановкой задания в очередь для загрузки и его завершением.

Сокращение времени ожидания (waiting time) – сократить время, которое проводят процессы в состоянии готовность и задания в очереди для загрузки.

Сокращение времени отклика (response time) – минимизировать время, которое требуется процессу в интерактивных системах для ответа на запрос пользователя.

10. ПЕРЕЧИСЛИТЕ ОСНОВНЫЕ АЛГОРИТМЫ ПЛАНИРОВАНИЯ ПРОЦЕССОВ. СФОРМУЛИРУЙТЕ АЛГОРИТМ “КАРУСЕЛЬ” (ROUND ROBIN) И ОХАРАКТЕРИЗУЙТЕ ЕГО. ПРИВЕДИТЕ ПРОСТОЙ ПРИМЕР. В КАКИХ СИСТЕМАХ ОН МОЖЕТ ПРИМЕНЯТЬСЯ НА ПРАКТИКЕ?

Round-robin — алгоритм распределения нагрузки распределённой вычислительной системы методом перебора её элементов по круговому циклу.

[править]

Суть алгоритма

Пусть имеется N объектов, способных выполнить заданное действие, и M задач, которые должны быть выполнены этими объектами. Подразумевается, что объекты n равны по своим свойствам между собой, задачи m имеют равный приоритет. Тогда первая задача (m = 1) назначается для выполнения первому объекту (n = 1), вторая — второму и т. д., до достижения последнего объекта (m = N). Тогда следующая задача (m = N+1) будет назначена снова первому объекту и т. п. Проще говоря, происходит перебор выполняющих задания объектов по циклу, или по кругу (round), и по достижении последнего объекта следующая задача будет также назначена первому объекту. Решение задач может быть дополнительно разбито на кванты времени, причем для продолжения решения во времени нумерация объектов (и, соответственно, назначенные задачи) сдвигается по кругу на 1, то есть задача первого объекта отдается второму, второго — третьему, и т. д., а первый объект получает задачу последнего, либо освобождается для приема новой задачи. Таким образом, алгоритм Round-robin становится алгоритмом распределения времени или балансировки нагрузки.

[править]

Применение

балансировка нагрузки вычислительных сетей (см. Round robin DNS)

управление задачами в системах с распределением времени (см. Round-robin scheduling)

коллективная игра в написании книг, вышивке и иных хобби (см. Round-robin (игра)

Алгоритмы планирования

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

First-Come, First-Served (FCFS)

Простейшим алгоритмом планирования является алгоритм, который принято обозначать аббревиатурой FCFS по первым буквам его английского названия – First-Come, First-Served (первым пришел, первым обслужен). Представим себе, что процессы, находящиеся в состоянии готовность, выстроены в очередь. Когда процесс переходит в состояние готовность, он, а точнее, ссылка на его PCB помещается в конец этой очереди. Выбор нового процесса для исполнения осуществляется из начала очереди с удалением оттуда ссылки на его PCB. Очередь подобного типа имеет в программировании специальное наименование – FIFO1), сокращение от First In, First Out (первым вошел, первым вышел).

Shortest-Job-First (SJF)

При рассмотрении алгоритмов FCFS и RR мы видели, насколько существенным для них является порядок расположения процессов в очереди процессов, готовых к исполнению. Если короткие задачи расположены в очереди ближе к ее началу, то общая производительность этих алгоритмов значительно возрастает. Если бы мы знали время следующих CPU burst для процессов, находящихся в состоянии готовность, то могли бы выбрать для исполнения не процесс из начала очереди, а процесс с минимальной длительностью CPU burst. Если же таких процессов два или больше, то для выбора одного из них можно использовать уже известный нам алгоритм FCFS. Квантование времени при этом не применяется. Описанный алгоритм получил название "кратчайшая работа первой" или Shortest Job First (SJF).

При приоритетном планировании каждому процессу присваивается определенное числовое значение – приоритет, в соответствии с которым ему выделяется процессор. Процессы с одинаковыми приоритетами планируются в порядке FCFS. Для алгоритма SJF в качестве такого приоритета выступает оценка продолжительности следующего CPU burst. Чем меньше значение этой оценки, тем более высокий приоритет имеет процесс. Для алгоритма гарантированного планирования приоритетом служит вычисленный коэффициент справедливости. Чем он меньше, тем больше у процесса приоритет.

Главная проблема приоритетного планирования заключается в том, что при ненадлежащем выборе механизма назначения и изменения приоритетов низкоприоритетные процессы могут не запускаться неопределенно долгое время. Обычно случается одно из двух. Или они все же дожидаются своей очереди на исполнение (в девять часов утра в воскресенье, когда все приличные программисты ложатся спать). Или вычислительную систему приходится выключать, и они теряются (при остановке IBM 7094 в Массачусетском технологическом институте в 1973 году были найдены процессы, запущенные в 1967 году и ни разу с тех пор не исполнявшиеся). Решение этой проблемы может быть достигнуто с помощью увеличения со временем значения приоритета процесса, находящегося в состоянии готовность. Пусть изначально процессам присваиваются приоритеты от 128 до 255. Каждый раз по истечении определенного промежутка времени значения приоритетов готовых процессов уменьшаются на 1. Процессу, побывавшему в состоянии исполнение, присваивается первоначальное значение приоритета.

Многоуровневые очереди (Multilevel Queue)

Для систем, в которых процессы могут быть легко рассортированы по разным группам, был разработан другой класс алгоритмов планирования. Для каждой группы процессов создается своя очередь процессов, находящихся в состоянии готовность (см. рис. 3.5). Этим очередям приписываются фиксированные приоритеты. Например, приоритет очереди системных процессов устанавливается выше, чем приоритет очередей пользовательских процессов. А приоритет очереди процессов, запущенных студентами, ниже, чем для очереди процессов, запущенных преподавателями. Это значит, что ни один пользовательский процесс не будет выбран для исполнения, пока есть хоть один готовый системный процесс, и ни один студенческий процесс не получит в свое распоряжение процессор, если есть процессы преподавателей, готовые к исполнению. Внутри этих очередей для планирования могут применяться самые разные алгоритмы. Так, например, для больших счетных процессов, не требующих взаимодействия с пользователем (фоновых процессов), может использоваться алгоритм FCFS, а для интерактивных процессов – алгоритм RR. Подобный подход, получивший название многоуровневых очередей, повышает гибкость планирования: для процессов с различными характеристиками применяется наиболее подходящий им алгоритм.