Планирование заданий

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

Задача – одна или несколько программ, связанных общим назначением, ресурсами.

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

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

Все потоки в рамках одного процесса имеют одно и то же адресное пространство.

Все потоки одного процесса всегда решают общую задачу одного пользователя.

Вытесняющие и невытесняющие алгоритмы планирования

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

Невытесняющие (non-preemptive) алгоритмы основаны на том, что активному потоку позволяется выполняться, пока он сам, по собственной инициативе, не отдаст управление операционной системе для того, чтобы она выбрала из очереди другой, готовый к выполнению поток. (Невытесняющее планирование используется, например, в MS Windows 3.1 и ОС Apple Macintosh.)
Вытесняющие (preemptive) алгоритмы – это такие способы планирования потоков, при которых решение о переключении процессора с выполнения одного потока на выполнение другого потока принимается операционной системой, а не активной задачей.

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

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

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

1.Алгоритмы планирования, основанные на квантовании

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

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

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

Поток завершен или ошибка

Потоку предоставлен квант

Поток инициировал ввод - вывод

Поток исчерпал квант

Ввод-вывод завершен

Рис.8. Алгоритмы планирования, основанные на квантовании.

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

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