Понятие процесса и ресурса. Классификация процессов

Процесс - абстракция, описывающая выполняющуюся программу

Процесс - совокупность алгоритма, вх и вых данных, ресурсов системы, находящиеся под управлением ОС в текущий момент времени

Классификация процессов:

1) По генеалогическим признакам: родительские и дочерние

2) По временным характеристикам: трасса процесса—набор состояний, которые процесс последовательно проходит в течении своего жизненного цикла. Если трассы не пересекаются, то процессы последовательны, иначе параллельны

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

4) По внешним хар-кам: параллельные, последовательные.

5) По принадлежности к CPU: внешние и внутренние

6) По принадлежности к ОС: системные и пользовательские

7) По связности: процессы, обменивающиеся инфо, называются взаимодействующими;в противном случае – информационно независимыми.

Диаграмма состояний процесса

 

Г отовность: состояние, в котором процессу достаточно для выполнения всех нужных ресурсов кроме процессорного времени

В ыполнение: состояние, в котором в данный момент находится только один процесс—тот, которому выделено процессорное время

О жидание(Б локировка): состояние, в котором процессу не хватает для выполнения каких-либо ресурсов и он ждет какого-либо события.

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

Из состояния В в Г процесс может перейти в системах с вытесняющим планированием. Невытесняющее планирование – системы пакетной обработки.

Контекст и дескриптор процесса.

Контекст процесса состоит из пользовательского контекста и контекста ядра.

Под пользовательским контекстом понимают код и данные процесса, стек пользователя, расположенные в адресном пространстве процесса.

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

Данные ядра содержат такую инф-цию о процессе, как: идентификатор пользователя — UID, групповой идентификатор пользователя — GID, идентификатор процесса — PID, идентификатор родительского процесса — PPID.

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

 

Классификация процессов.

По генеалогическим признакам: родительский и дочерний.

По результативности:

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

· Тождественные – эквивалентные, выполняющиеся по одинаковым программам.

· Равные – тождественные, трассы которых совпадают.

Все остальные различны.

По временным хар-кам: параллельные и последовательные.

По связности:

· Процессы обменивающиеся инфо – взаимодействующие.

· Иначе – информационно независимые.

Понятие потока. Способы реализации потоков. Планирование потоков.

Поток (_en. stream) - абстрактная последовательность инструкций или данных вообще, привязанная к соответствующему дескриптору (может быть представлен именем потока).

Многопоточность – это

1. Способность процесса выполняться в более чем одном потоке команд.

2. Квазимногозадачность в рамках одного процесса.

Достоинства использования потоков:

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

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

3. Скорость создания и удаления потоков тоже на порядок выше.

Недостатки: Усложнение планирования потоков и процессов.

Способы реализации потоков

Типы:

1) Потоки на уровне ядра

2) Потоки на уровне пользователя

3) Смешанный поток (комбинированный)

Потоки на уровне пользователя.

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

Достоинства:

- такая схема может быть реализована в системе не поддерживающей многопоточность;

- потоки внутри каждого процесса могут использовать свой алгоритм планирования

Недостатки:

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

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

Потоки на уровне ядра

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

Недостатки:

- нельзя реализовать в системе не поддерживающей многопоточность

- частые переключения между потоков различных процессов приводит к частой смене контекста процесса, тем самым увеличивая прикладные расходы на управление

Смешанная реализация

1) Потоки на уровне пользователя: при блокирующем вызове переводятся на уровень ядра

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

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

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

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

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

 

8. Планирование и диспетчеризация процессов. Стратегии планирования.

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

Планирование - это организация процессов в некоторую последовательность, согласно заданной стратегии.

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

3 уровня планирования:

1. Долгосрочное планирование - выбор процесса на запуск системы.

2. Краткосрочное планирование (диспетчеризация) - определяет поведение системы в ближайшее время вплоть до нескольких тиков таймера.

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

Вытесняющее планирование – в системе есть возможность возврата процесса из выполнения непосредственно в готовность.

Невытесняющее планирование – из выполнения можно перейти только в ожидание.

Планирование производится в вынужденных и не вынужденных случаях:

1. Выполняющийся процесс завершил работу и покинул систему

2. Выполняющийся процесс перешел в состояние ожидания

3. Поступление нового процесса в очередь готовности

4. Окончание кванта времени выполняющегося процесса

Невытесняющее планирование - только в вынужденных случаях.

Диспетчеризация– поочередное выделение планировщиком операционной система процессам квантов процессорного времени.

 

Планирование в системах пакетной обработки данных. Дисциплины FCFS, SJN, SNR.

Используются следующие алгоритмы:

FCFS(первым пришел первым обслужился)

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

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

Достоинства: Простота реализации

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

SJN(Shortest Job Next)

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

Алгоритм близок к оптимальному

Недостатки:

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

SRN(Shortest remain next)

Модификация алгоритма SJN c вытеснением выполняющегося процесса в случае поступления в систему нового процесса,которому необходимо для выполнения меньше времени, чем осталось выполниться текущему.

Достоинства:

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

Недостатки:

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

10. Планирование в интерактивных системах. Дисциплина RR (круговое планирование), дисциплины приоритетного планирования.

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

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

 

Планирование в системах реального времени.

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

Алгоритм 1: RMS – статический алгоритм планирования реального времени. Используется понятие дэдлайн – момент времени, к которому должно быть обработано событие. Если событие не обработано до наступления своего дэдлайна, то алгоритм терпит крах. Приоритеты процессов пропорциональны частоте поступления их событий.

Алгоритм 2: EDF – динамический алгоритм. На выполнение выбирается тот процесс, у которого выше дэдлайн. На сильно загруженных системах, статический алгоритм может не справляться с планированием, в то время как динамический может даже периодически дать системе простаивать.