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

Потоки

Состояние процесса

Процесс может находиться в одном из трех состояний:

- Очередь готовых процессов

- Выполнение процесса

- Ожидание

Состояние процесса можно представить в виде:

Выполнение – это активное состояние процесса, в это время происходит счет процесса.

Блокирование – это пассивное состояние процесса. Процесс ожидает завершения некоторого события, например, окончания операции ввода-вывода.

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

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

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

В однопроцессорных системах в состоянии готовности или ожидания может одновременно находиться несколько процессов, а в состоянии выполнения – один. Эти процессы образуют очереди путем объединения в списки блоки управления про­цессами (дескрипторов процессов). Каждый дескриптор содержит дополнительную ссылку на соседа по очереди. Такая организация позволяет легко переупорядочивать, включать и исключать процессы, переводить их из одного состояния в другое. На рисунке ___ показана очередь процессов, установленных в порядке A, B, D, E, C.

Рисунок 2.2 - Очередь процессов

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

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

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

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

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

- ThreadSwitch — поток, вызвавший эту функцию, считает себя готовым к немед­ленному выполнению, но отдает управление для того, чтобы могли выпол­няться и другие потоки;

- ThreadSwitchWithDelay — функция аналогична предыдущей, но поток считает, что будет готов к выполнению только через определенное количество пере­ключений с потока на поток;

- Del ay — функция аналогична предыдущей, но задержка дается в миллисекундах;

- ThreadSwItchLowPriority — функция отдачи управления, отличается от Thread-Switch тем, что поток просит поместить его в очередь готовых к выполнению, но низкоприоритетных потоков.