Структура очереди подзадач в многоуровневой ОС.

Все блоки ТСВ последовательно связаны друг с другом в очередь задач. В момент образования задачи ТСВ заносится в очередь задач, а в момент завершения задачи выводится из нее. Место блока ТСВ в очереди задач определяется диспетчерским приоритетом задачи, который выражается числом от 0 до 255. Когда несколько задач одновременно претендуют на один ресурс, конфликты разрешаются, как правило, на основе сравнения диспетчерских приоритетов. В случае равенства приоритетов, конфликт разрешается в пользу задачи, выдавшей запрос первой. Обычно для разрешения конфликтных ситуаций организуется очередь запросов к ресурсу, упорядоченных по приоритетам. Очередь задач, состоящая из блоков ТСВ, представляет собой очередь запросов к центральному процессору. Все блоки ТСВ в очереди упорядочены в соответствии с диспетчерским приоритетом. Место для блока ТСВ вновь образовавшейся задачи определяется значением ее диспетчерского приоритета. Перед новым ТСВ должны стоять ТСВ с большими или равными диспетчерскими приоритетами, а за новой ТСВ все ТСВ с меньшими диспетчерскими приоритетами. Кроме диспетчерских приоритетов для каждой задачи определяется значение граничного приоритета. В качестве граничного приоритета первоначально устанавливается начальное значение диспетчерского приоритета. Граничный приоритет некоторой задачи определяет максимальное значение диспетчерских приоритетов ее подзадач. Диспетчерский приоритет подзадачи может превысить ее собственный граничный приоритет, но не может быть больше граничного приоритета порождающей задачи, в противном случае подзадаче устанавливается новое значение граничного приоритета, равное максимальному значению диспетчерского приоритета подзадачи. Для организации очереди задач образуется список блоков ТСВ, соответствующий структуре очереди задач. Для организации этого списка имеется четыре поля ТСВ: 1) поле, содержащие адрес ТСВ основной задачи пользователя; 2) поле, содержащие адрес ТСВ порождающей задачи для текущей подзадачи; 3) поле, содержащие адрес ТСВ предыдущей подзадачи (расположенной на одном уровне с текущей подзадачей); 4) поле, содержащие адрес ТСВ последней порожденной подзадачи для данной задачи. Структура и расположение очереди задач в ОЗУ зависит от режима мультипрограммирования управляющей программы. В однопрограммном режиме одна задача один ТСВ. В режиме с фиксированным числом задач одновременно могут существовать системные задачи и одна задача для каждого раздела памяти. Диспетчерский приоритет определяется положением блока ТСВ в очереди задач, наивысший приоритет имеют системные задачи, затем идут задачи разделов памяти с учетом приоритетов разделов. Так как при генерации ОС фиксируется максимальное число разделов и известно число системных задач, то размер очереди задач является фиксированным. Кроме того, известен приоритет задач. Поэтому очередь задач может быть постоянна в ядре ОС. В процессе функционирования ОС очередь не меняется. Когда задача завершается в разделе, то ее блок ТСВ остается, но не подчиняется диспетчеризации. В режиме с фиксированным числом задач допускаются подзадачи. Образование подзадач осуществляется по макрокоманде АТТАСН. В этом случае в системе могут одновременно существовать системные задачи, задачи разделов, подзадачи задач пользователя. Так как при генерации известно количество системных задач и задач пользователя, то диспетчерские приоритеты этих задач определяются так же как и в предыдущем случае. При образовании же подзадачи для нее в области системных очередей, определяемой при генерации и примыкающий ядру системы, строится блок ТСВ и помещается в очередь задач в соответствии со своим диспетчерским приоритетом. Если в режиме без подзадач диспетчерский приоритет определяется положением ТСВ в очереди задач, то в режиме с подзадачами этого мало, т.к. появление подзадачи изменяет структуру очереди и требуется числовое определение диспетчерского приоритета. Для системных задач и задач разделов устанавливаются диспетчерские приоритеты и диапазоны их изменения. Диапазоны изменений диспетчерских приоритетов выбираются так, чтобы они не перекрывались, поэтому никакое изменение приоритетов задач разделов не может изменить относительную последовательность блоков ТСВ системных задач в очереди задач. В начале работы системы диспетчерские приоритеты соседних в очереди задач отличаются на одну и ту же величину

 

34. Планировщик задач. Механизм планирования

 

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

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

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

1. FIFO - очередь задач (First In, First Out)

2. LIFO - очередь задач (стек) (Last In, First Out)

Варианты LIFO и FIFO иллюстрируют статическое планирование исполнения процессов в однопроцессорной системе под управлением операционной системы с монопольным доступом к процессору (операционная система без вытеснения процесса).

3. Круговое обслуживание задач на базе FIFO очереди

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

Можно выделить два подхода к планированию исполнения процессов в многопроцессорных системах:

1. Work Sharing - централизованное планирование, при котором планировщик контролирует единый пул задач в системе и назначает задачи процессорам;

2. Work Stealing - децентрализованное планирование, при котором единый планировщик отсутствует, а процессоры сами выбирают какие задачи им исполнять;